mlsanityData to 7 Oct 2026

Settling the Sample Complexity of Online Reinforcement Learning

arXiv 2307.13586 ↗First posted 25 Jul 2023cs.LGcited by 44

Not on the map. Why?

Abstract (arXiv)

A central issue lying at the heart of online reinforcement learning (RL) is data efficiency. While a number of recent works achieved asymptotically minimal regret in online RL, the optimality of these results is only guaranteed in a ``large-sample'' regime, imposing enormous burn-in cost in order for their algorithms to operate optimally. How to achieve minimax-optimal regret without incurring any burn-in cost has been an open problem in RL theory. We settle this problem for the context of finite-horizon inhomogeneous Markov decision processes. Specifically, we prove that a modified version of Monotonic Value Propagation (MVP), a model-based algorithm proposed by citezhang2020reinforcement, achieves a regret on the order of (modulo log factors) beginequation* minbig √SAH3K, ,HK big, endequation* where S is the number of states, A is the number of actions, H is the planning horizon, and K is the total number of episodes. This regret matches the minimax lower bound for the entire range of sample size K≥ 1, essentially eliminating any burn-in requirement. It also translates to a PAC sample complexity (i.e., the number of episodes needed to yield varepsilon-accuracy) of fracSAH3varepsilon2 up to log factor, which is minimax-optimal for the full varepsilon-range. Further, we extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances. The key technical innovation lies in the development of a new regret decomposition strategy and a novel analysis paradigm to decouple complicated statistical dependency -- a long-standing challenge facing the analysis of online RL in the sample-hungry regime.

Key facts. Cited by 44 papers in the map (data through 7 Oct 2026). Builds on 62 of its 87 references that are in the map. First posted on arXiv 25 Jul 2023.

Builds on

62 of 87 references.

References · 62

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  5. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  9. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  12. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
38 more
  1. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  2. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  3. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  4. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  5. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  8. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  9. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  10. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  11. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  12. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  13. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  14. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  15. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  16. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  17. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  18. 2020Q-learning with Logarithmic Regretcited by 59
  19. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  20. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  21. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  22. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  23. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  24. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  25. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  26. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  27. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  28. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  29. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  30. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  31. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  32. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  33. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  34. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  35. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  36. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  37. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  38. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27

50 most cited of 62 All 62 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 16; 2025: 13; 2026: 14.

44 papers.

Sort:

By area:

  1. 2025Outcome-based Exploration for LLM Reasoningcited by 79
  2. 2025Horizon Reduction Makes RL Scalablecited by 55
  3. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  4. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  5. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  6. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  7. 2024Reinforcement Learning with Lookahead Informationcited by 8
  8. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  9. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  10. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  11. 2024Hybrid Reinforcement Learning from Offline Observation Alonecited by 5
  12. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
32 more
  1. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  2. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  3. 2024Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learningcited by 3
  4. 2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
  5. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  6. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  7. 2026Towards Cold-Start Drafting and Continual Refining: A Value-Driven Memory Approach with Application to NPU Kernel Synthesiscited by 3
  8. 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexitycited by 2
  9. 2024Scale-free Adversarial Reinforcement Learningcited by 2
  10. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  11. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  12. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  13. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  14. 2026Learning in Markov Decision Processes with Exogenous Dynamicscited by 2
  15. 2024HARP: Human-Assisted Regrouping with Permutation Invariant Critic for Multi-Agent Reinforcement Learningcited by 1
  16. 2025A Refined Analysis of UCBVIcited by 1
  17. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  18. 2026Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptationcited by 1
  19. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  20. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  21. 2024State-free Reinforcement Learningcited by 0
  22. 2025When a Reinforcement Learning Agent Encounters Unknown Unknownscited by 0
  23. 2025Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approachcited by 0
  24. 2026Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batchingcited by 0
  25. 2026Adapting Actively on the Fly: Relevance-Guided Online Meta-Learning with Latent Concepts for Geospatial Discoverycited by 0
  26. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0
  27. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  28. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0
  29. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0
  30. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0
  31. 2026From Experience to Expertise: Adoption-Aware Memory Learning for Data-Scarce NPU Kernel Synthesiscited by 0
  32. 2026Optimal Multi-Reward Reinforcement Learningcited by 0