mlsanityData to 7 Oct 2026

Variance-reduced Q-learning is minimax optimal

arXiv 1906.04697 ↗First posted 11 Jun 2019cs.LG math.OC stat.MLcited by 72

Not on the map. Why?

Abstract (arXiv)

We introduce and analyze a form of variance-reduced Q-learning. For γ-discounted MDPs with finite state space X and action space U, we prove that it yields an ε-accurate estimate of the optimal Q-function in the ℓ_∞-norm using O left(left(fracD ε2 (1-γ)3 right) ; log left( fracD(1-γ) right) right) samples, where D = |X| × |U|. This guarantee matches known minimax lower bounds up to a logarithmic factor in the discount complexity. In contrast, our past work shows that ordinary Q-learning has worst-case quartic scaling in the discount complexity.

Key facts. Cited by 72 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 13; 2023: 12; 2024: 13; 2025: 8; 2026: 9.

72 papers.

Sort:

By area:

  1. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  2. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  3. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  4. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  5. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  6. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  7. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  8. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  9. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 35
  10. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  11. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  12. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
38 more
  1. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  2. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  3. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
  4. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  5. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  6. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  7. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
  8. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  9. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  10. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  11. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  12. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  13. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  14. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  15. 2022Optimal variance-reduced stochastic approximation in Banach spacescited by 14
  16. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13
  17. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  18. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 11
  19. 2022Statistically Efficient Advantage Learning for Offline Reinforcement Learning in Infinite Horizonscited by 10
  20. 2023A Concentration Bound for TD(0) with Function Approximationcited by 10
  21. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  22. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  23. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  24. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  25. 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
  26. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  27. 2024Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorizationcited by 6
  28. 2025Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimationcited by 6
  29. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5
  30. 2022Instance-Dependent Confidence and Early Stopping for Reinforcement Learningcited by 5
  31. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  32. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  33. 2021Robust Risk-Sensitive Reinforcement Learning Agents for Trading Marketscited by 3
  34. 2022Algorithm for Constrained Markov Decision Process with Linear Convergencecited by 3
  35. 2025A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policiescited by 3
  36. 2024Asymptotic Analysis of Sample-averaged Q-learningcited by 2
  37. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2
  38. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2

50 most cited of 72 All 72 (JSON)