mlsanityData to 7 Oct 2026

Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning

arXiv 2110.04645 ↗First posted 9 Oct 2021cs.LG math.ST stat.MLcited by 51

Not on the map. Why?

Abstract (arXiv)

Achieving sample efficiency in online episodic reinforcement learning (RL) requires optimally balancing exploration and exploitation. When it comes to a finite-horizon episodic Markov decision process with S states, A actions and horizon length H, substantial progress has been achieved towards characterizing the minimax-optimal regret, which scales on the order of √H2SAT (modulo log factors) with T the total number of samples. While several competing solution paradigms have been proposed to minimize regret, they are either memory-inefficient, or fall short of optimality unless the sample size exceeds an enormous threshold (e.g., S6A4 ,poly(H) for existing model-free methods). To overcome such a large sample size barrier to efficient RL, we design a novel model-free algorithm, with space complexity O(SAH), that achieves near-optimal regret as soon as the sample size exceeds the order of SA,poly(H). In terms of this sample size requirement (also referred to the initial burn-in cost), our method improves -- by at least a factor of S5A3 -- upon any prior memory-efficient algorithm that is asymptotically regret-optimal. Leveraging the recently introduced variance reduction strategy (also called em reference-advantage decomposition), the proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences with upper and lower confidence bounds. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings that involve intricate exploration-exploitation trade-offs.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). Builds on 40 of its 96 references that are in the map. First posted on arXiv 9 Oct 2021.

Builds on

40 of 96 references.

References · 40

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  4. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  7. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  12. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
28 more
  1. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  2. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  3. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  4. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  5. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  6. 2020Variance-Reduced Methods for Machine Learningcited by 79
  7. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  8. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  9. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  10. 2020Q-learning with Logarithmic Regretcited by 59
  11. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  12. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  13. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  14. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  15. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  16. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  17. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  18. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  19. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  20. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  21. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  22. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  23. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  24. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  25. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  26. 2020Finite-Time Analysis for Double Q-learningcited by 12
  27. 2020A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regretcited by 7
  28. 2020Momentum Q-learning with Finite-Sample Convergence Guaranteecited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 11; 2023: 12; 2024: 8; 2025: 15; 2026: 5.

51 papers.

Sort:

By area:

  1. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  2. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  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. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  7. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  8. 2022Curriculum Reinforcement Learning using Optimal Transport via Gradual Domain Adaptationcited by 28
  9. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  10. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  11. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  12. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
38 more
  1. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  2. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  3. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  4. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  5. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  6. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  7. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  8. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  9. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  10. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  11. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  12. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  13. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  14. 2025Learning to Answer from Correct Demonstrationscited by 6
  15. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
  16. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  17. 2023Sample Efficient Reinforcement Learning with Partial Dynamics Knowledgecited by 4
  18. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  19. 2022Multi-armed Bandit Learning on a Graphcited by 3
  20. 2025Data-Efficient Multi-Agent Spatial Planning with LLMscited by 3
  21. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  22. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
  23. 2026Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Modelscited by 3
  24. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  25. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  26. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  27. 2025Provably Efficient and Agile Randomized Q-Learningcited by 2
  28. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  29. 2025Q-learning with Posterior Samplingcited by 1
  30. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  31. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  32. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  33. 2022Off-Policy Deep Reinforcement Learning Algorithms for Handling Various Robotic Manipulator Taskscited by 0
  34. 2024State-free Reinforcement Learningcited by 0
  35. 2025Increasing Information for Model Predictive Control with Semi-Markov Decision Processescited by 0
  36. 2025When a Reinforcement Learning Agent Encounters Unknown Unknownscited by 0
  37. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  38. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0

50 most cited of 51 All 51 (JSON)