mlsanityData to 14 Oct 2026

Is Q-learning Provably Efficient?

arXiv 1807.03765 ↗First posted 10 Jul 2018cs.LG cs.AI math.OCcited by 487

Not on the map. Why?

Cited by 119 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

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 tildeO(√H3 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 √H factor. To the best of our knowledge, this is the first analysis in the model-free setting that establishes √T regret without requiring access to a "simulator."

Key facts. Cited by 487 papers in the map (data through 14 Oct 2026). First posted on arXiv 10 Jul 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 129; 2022: 92; 2023: 104; 2024: 57; 2025: 56; 2026: 48.

487 papers.

Sort:

By area:

  1. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  4. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  5. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  6. 2022Jump-Start Reinforcement Learningcited by 112
  7. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  8. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  9. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  10. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  11. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  12. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
38 more
  1. 2025Outcome-based Exploration for LLM Reasoningcited by 83
  2. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 80
  3. 2021A Survey of Exploration Methods in Reinforcement Learningcited by 73
  4. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
  5. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  6. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  7. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 62
  8. 2021Reinforcement Learning, Bit by Bitcited by 59
  9. 2025UFT: Unifying Supervised and Reinforcement Fine-Tuningcited by 59
  10. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 58
  11. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  12. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  13. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  14. 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
  15. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  16. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  17. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  18. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  19. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  20. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  21. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
  22. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  23. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  24. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  25. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  26. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  27. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  28. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  29. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  30. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  31. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 43
  32. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 43
  33. 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 43
  34. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 43
  35. 2021Heuristic-Guided Reinforcement Learningcited by 42
  36. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  37. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  38. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42

50 most cited of 487 All 487 (JSON)