Is Q-learning Provably Efficient?

Abstract

Model-free reinforcement learning (RL) algorithms, such as Q-learning, directly parameterize and update value functions or policies without explicitly modeling the environment. They are typically simpler, more flexible to use, and thus more prevalent in modern deep RL than model-based approaches. However, empirical work has suggested that model-free algorithms may require more samples to learn [Deisenroth and Rasmussen 2011, Schulman et al. 2015]. The theoretical question of "whether model-free algorithms can be made sample efficient" is one of the most fundamental questions in RL, and remains unsolved even in the basic scenario with finitely many states and actions. We prove that, in an episodic MDP setting, Q-learning with UCB exploration achieves regret $\tilde{O}(\sqrt{H^{3}SAT})$, where $S$ and $A$ are the numbers of states and actions, $H$ is the number of steps per episode, and $T$ is the total number of steps. This sample efficiency matches the optimal regret that can be achieved by any model-based approach, up to a single $\sqrt{H}$ factor. To the best of our knowledge, this is the first analysis in the model-free setting that establishes $\sqrt{T}$ regret without requiring access to a "simulator."

Best paper in ICML 2018 workshop "Exploration in RL"

References in corpus (4)

• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Temporal Difference Models: Model-Free Deep RL for Model-Based Control
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Variance Reduction Methods for Sublinear Reinforcement Learning

Cited by in corpus (11)

• Policy Certificates: Towards Accountable Reinforcement Learning
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
• Conservative Exploration in Reinforcement Learning
• Preference-based Reinforcement Learning with Finite-Time Guarantees
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver
• Reinforcement Learning with Feedback Graphs
• Stateful Offline Contextual Policy Evaluation and Learning
• Can Q-Learning be Improved with Advice?