More Like this

1. Is Long Horizon RL More Difficult Than Short Horizon RL?

   Wang, Ruosong; Du, Simon S.; Yang, Lin; Kakade, Sham (January 2020, Advances in neural information processing systems)

   null (Ed.)

   Learning to plan for long horizons is a central challenge in episodic reinforcement learning problems. A fundamental question is to understand how the difficulty of the problem scales as the horizon increases. Here the natural measure of sample complexity is a normalized one: we are interested in the \emph{number of episodes} it takes to provably discover a policy whose value is eps near to that of the optimal value, where the value is measured by the \emph{normalized} cumulative reward in each episode. In a COLT 2018 open problem, Jiang and Agarwal conjectured that, for tabular, episodic reinforcement learning problems, there exists a sample complexity lower bound which exhibits a polynomial dependence on the horizon --- a conjecture which is consistent with all known sample complexity upper bounds. This work refutes this conjecture, proving that tabular, episodic reinforcement learning is possible with a sample complexity that scales only \emph{logarithmically} with the planning horizon. In other words, when the values are appropriately normalized (to lie in the unit interval), this results shows that long horizon RL is no more difficult than short horizon RL, at least in a minimax sense. Our analysis introduces two ideas: (i) the construction of an eps-net for near-optimal policies whose log-covering number scales only logarithmically with the planning horizon, and (ii) the Online Trajectory Synthesis algorithm, which adaptively evaluates all policies in a given policy class and enjoys a sample complexity that scales logarithmically with the cardinality of the given policy class. Both may be of independent interest. 

   more » « less
2. Verifying Deep-RL-Driven Systems

   https://doi.org/10.1145/3341216.3342218  

   Kazak, Yafim; Barrett, Clark; Katz, Guy; Schapira, Michael (August 2019, Proceedings of the 2019 Workshop on Network Meets AI & ML (NetAI '19))

   null (Ed.)

   Deep reinforcement learning (RL) has recently been successfully applied to networking contexts including routing, flow scheduling, congestion control, packet classification, cloud resource management, and video streaming. Deep-RL-driven systems automate decision making, and have been shown to outperform state-of-the-art handcrafted systems in important domains. However, the (typical) non-explainability of decisions induced by the deep learning machinery employed by these systems renders reasoning about crucial system properties, including correctness and security, extremely difficult. We show that despite the obscurity of decision making in these contexts, verifying that deep-RL-driven systems adhere to desired, designer-specified behavior, is achievable. To this end, we initiate the study of formal verification of deep RL and present Verily, a system for verifying deep-RL-based systems that leverages recent advances in verification of deep neural networks. We employ Verily to verify recently-introduced deep-RL-driven systems for adaptive video streaming, cloud resource management, and Internet congestion control. Our results expose scenarios in which deep-RL-driven decision making yields undesirable behavior. We discuss guidelines for building deep-RL-driven systems that are both safer and easier to verify. 

   more » « less
3. Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes

   Wagenmaker, Andrew J; Chen, Yifang; Simchowitz, Max; Du, Simon; Jamieson, Kevin (January 2022, Proceedings of Machine Learning Research)
4. Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes

   Wagenmaker, Andrew; Chen, Yifang; Simchowitz, Max; Du, Simon S; Jamieson, Kevin (January 2022, International Conference on Machine Learning)
5. Offline RL Without Off-Policy Evaluation

   Brandfonbrener, David; Whitney, William F.; Ranganath, Rajesh; Bruna, Joan (December 2021, Advances in neural information processing systems)

   null (Ed.)

   Most prior approaches to offline reinforcement learning (RL) have taken an iterative actor-critic approach involving off-policy evaluation. In this paper we show that simply doing one step of constrained/regularized policy improvement using an on-policy Q estimate of the behavior policy performs surprisingly well. This one-step algorithm beats the previously reported results of iterative algorithms on a large portion of the D4RL benchmark. The simple one-step baseline achieves this strong performance without many of the tricks used by previously proposed iterative algorithms and is more robust to hyperparameters. We argue that the relatively poor performance of iterative approaches is a result of the high variance inherent in doing off-policy evaluation and magnified by the repeated optimization of policies against those high-variance estimates. In addition, we hypothesize that the strong performance of the one-step algorithm is due to a combination of favorable structure in the environment and behavior policy. 

   more » « less