Is Q-learning Provably Efficient?

By Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck, Michael I. Jordan. 2018

921 citations recorded by the source corpus.

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."

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “There is a parallel strand of work deriving regret and complexity bounds for model-free algorithms, primarily based on extensions of Q-learning [23, 58, 26].”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “Under Assumption 3.1, a line of work has attempted to provide tight sample complexity bounds [Azar et al., 2017, Dann and Brunskill, 2015, Dann et al., 2017, 2019, Jin et al., 2018, Osband and Van Roy, 2017].”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “Previous sample complexity bounds for RL has primarily focused on the online setting [Azar et al., 2017, Jin et al., 2018, Zanette and Brunskill, 2019, Simchowitz and Jamieson, 2019, Efroni et al., 2019, Cai et al., 2019] or the generative model (simulator) setting [Azar et al., 2013, Sidford et…”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, methodology): “For tabular MDPs, a number of sample-efﬁcient RL approaches exist, mostly model-based (Kearns and Singh, 2002; Jaksch et al., 2010; Dann and Brunskill, 2015; Szita and Szepesvári, 2010; Azar et al., 2017), but some are model-free (Strehl et al., 2006; Jin et al., 2018).”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “…for promoting exploration in online RL (Jaksch et al., 2010; Abbasi-Yadkori et al., 2011; Russo and Van Roy, 2013; Osband and Van Roy, 2014; Chowdhury and Gopalan, 2017; Azar et al., 2017; Jin et al., 2018; 2020; Cai et al., 2020; Yang et al., 2020b; Ayoub et al., 2020; Wang et al., 2020b).”
A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces (2020, background): “Related work Regret bounds for RL in stationary environments have been extensively studied in finite (tabular) MDPs [1, 2, 3, 4, 5], and also in metric spaces under Lipschitz continuity assumptions [6, 7, 8, 9, 10].”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, methodology): “These algorithms are based on optimistic Q-learning (Jin et al., 2018), to which we refer as OptQL, and achieve a regret of order Õ ( H 5 2K d+1 d+2 ) .”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, methodology): “…in standard episodic reinforcement (Jaksch et al., 2010; Osband et al., 2013; Gopalan and Mannor, 2015; Osband and Van Roy, 2017; Azar et al., 2017; Jin et al., 2018; Dann et al., 2017; Zanette and Brunskill, 2019; Simchowitz and Jamieson, 2019; Efroni et al., 2019; Pacchiano et al., 2020).”
Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, methodology): “and b∆, where bh is a standard Hoeffding-based optimism that is commonly used in upper confidence bounds (Jin et al., 2018; Zhang et al., 2020), and b∆ is the extra optimism that we need to take into account the non-stationarity of the environment.”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, methodology): “Learning adversarial MDPs with changing dynamics is computationally hard even under full-information feedback (Yadkori et al., 2013).”
Provable Rich Observation Reinforcement Learning with Combinatorial Latent States (2021, background): “There is a rich literature on sample-efficient reinforcement learning in tabular MDPs with a small number of observed states (Brafman & Tennenholtz, 2002; Strehl et al., 2006; Kearns & Singh, 2002; Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018).”
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes (2019, background): “For instance, the Bellman structure of variances in an MDP, observed in Azar et al. (2013) has subsequently formed a crucial component of minimax optimal exploration algorithms (Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019; Wainwright, 2019).”
Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition (2020, methodology): “While one may refer to Appendix C for the details of the theorem, the notion of local switching cost for RL is recently introduced and studied by Bai et al. [2019], where the authors integrate a lazy update scheme with the UCB-Bernstein algorithm [Jin et al., 2018] and achieve Õp ?”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, methodology): “Strehl et al. [30] and Jin et al. [18] showed with proper exploration techniques, one can obtain a near-optimal Q -function (and so a near-optimal policy) using polynomial number of trajectories, in terms of number of states, actions and planning horizon.”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “…setting where S and A are ﬁnite sets, there exist algorithms that achieve asymptotic regret O ( |S||A| T ) (e.g. (Jaksch et al., 2010; Osband and Van Roy, 2016; Osband et al., 2017; Agrawal and Jia, 2017; Azar et al., 2017; Dann et al., 2018; Jin et al., 2018)), where T is the number of time steps.”
Provably Efficient Exploration in Policy Optimization (2019, background): “…learning in tabular (Jaksch et al., 2010; Osband et al., 2014; Osband and Van Roy, 2016; Azar et al., 2017; Dann et al., 2017; Strehl et al., 2006; Jin et al., 2018) and linear settings (Yang and Wang, 2019a,b; Jin et al., 2019), as well as nonlinear settings involving general function…”
Influence-Based Multi-Agent Exploration (2019, methodology): “Provably efﬁcient methods are proposed, such as upper conﬁdence bound (UCB) (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018) and posterior sampling for reinforcement learning (PSRL) (Strens, 2000; Osband et al., 2013; Osband & Van Roy, 2016; Agrawal & Jia, 2017).”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, methodology): “The proof is based on a standard online-to-batch conversion (e.g. (Section 3.1, Jin et al., 2018).)”
Exploration with Unreliable Intrinsic Reward in Multi-Agent Reinforcement Learning (2019, background): “…reward is somewhat justified, as for one-hot coded φ(st), the intrinsic reward is r+t = σ/ √ Nt(st, ut), which corresponds to the tabular case (e.g., in Jin et al., 2018) with scaling factor σ. 1To condition on trajectories τat , we follow Hausknecht & Stone (2015) and use a recurrent network of…”