mlsanityData to 7 Oct 2026

Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis

arXiv 2102.06548 ↗First posted 12 Feb 2021stat.ML cs.IT cs.LGcited by 89

Not on the map. Why?

Abstract (arXiv)

Q-learning, which seeks to learn the optimal Q-function of a Markov decision process (MDP) in a model-free fashion, lies at the heart of reinforcement learning. When it comes to the synchronous setting (such that independent samples for all state-action pairs are drawn from a generative model in each iteration), substantial progress has been made towards understanding the sample efficiency of Q-learning. Consider a γ-discounted infinite-horizon MDP with state space S and action space A: to yield an entrywise varepsilon-approximation of the optimal Q-function, state-of-the-art theory for Q-learning requires a sample size exceeding the order of frac|S||A|(1-γ)5varepsilon2, which fails to match existing minimax lower bounds. This gives rise to natural questions: what is the sharp sample complexity of Q-learning? Is Q-learning provably sub-optimal? This paper addresses these questions for the synchronous setting: (1) when |A|=1 (so that Q-learning reduces to TD learning), we prove that the sample complexity of TD learning is minimax optimal and scales as frac|S|(1-γ)3varepsilon2 (up to log factor); (2) when |A|≥ 2, we settle the sample complexity of Q-learning to be on the order of frac|S||A|(1-γ)4varepsilon2 (up to log factor). Our theory unveils the strict sub-optimality of Q-learning when |A|≥ 2, and rigorizes the negative impact of over-estimation in Q-learning. Finally, we extend our analysis to accommodate asynchronous Q-learning (i.e., the case with Markovian samples), sharpening the horizon dependency of its sample complexity to be frac1(1-γ)4.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). Builds on 28 of its 63 references that are in the map. First posted on arXiv 12 Feb 2021.

Builds on

28 of 63 references.

References · 28

  1. 2018Is Q-learning Provably Efficient?cited by 485
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  4. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  5. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  6. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  7. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
  8. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  9. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  10. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  11. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  12. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
16 more
  1. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  2. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  3. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  4. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  5. 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
  6. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  7. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  8. 2018Q-learning with Nearest Neighborscited by 37
  9. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  10. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  11. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  12. 2020Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learningcited by 13
  13. 2020Finite-Time Analysis for Double Q-learningcited by 12
  14. 2020The Mean-Squared Error of Double Q-Learningcited by 11
  15. 2018Stochastic Primal-Dual Q-Learningcited by 7
  16. 2020Momentum Q-learning with Finite-Sample Convergence Guaranteecited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 11; 2023: 15; 2024: 19; 2025: 16; 2026: 18.

89 papers.

Sort:

By area:

  1. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  2. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  3. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  4. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  5. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  6. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 35
  7. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  8. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  9. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  10. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
  11. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  12. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
38 more
  1. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  2. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  3. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
  4. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  5. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  6. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  7. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  8. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  9. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  10. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13
  11. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  12. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  13. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  14. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Setcited by 11
  15. 2022Statistically Efficient Advantage Learning for Offline Reinforcement Learning in Infinite Horizonscited by 10
  16. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  17. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  18. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  19. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  20. 2022Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structurecited by 7
  21. 2023Off-policy Evaluation in Doubly Inhomogeneous Environmentscited by 7
  22. 2024Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorizationcited by 6
  23. 2021Convergence Results For Q-Learning With Experience Replaycited by 5
  24. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  25. 2022Towards Global Optimality in Cooperative MARL with the Transformation And Distillation Frameworkcited by 5
  26. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coveragecited by 5
  27. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
  28. 2024Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximationcited by 5
  29. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 5
  30. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  31. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  32. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 5
  33. 2022A Note on Target Q-learning For Solving Finite MDPs with A Generative Oraclecited by 4
  34. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samplescited by 4
  35. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  36. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  37. 2025Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Boundscited by 4
  38. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4

50 most cited of 89 All 89 (JSON)