mlsanityData to 7 Oct 2026

Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time

arXiv 2305.15546 ↗First posted 24 May 2023cs.LG math.ST stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

A crucial problem in reinforcement learning is learning the optimal policy. We study this in tabular infinite-horizon discounted Markov decision processes under the online setting. The existing algorithms either fail to achieve regret optimality or have to incur a high memory and computational cost. In addition, existing optimal algorithms all require a long burn-in time in order to achieve optimal sample efficiency, i.e., their optimality is not guaranteed unless sample size surpasses a high threshold. We address both open problems by introducing a model-free algorithm that employs variance reduction and a novel technique that switches the execution policy in a slow-yet-adaptive manner. This is the first regret-optimal model-free algorithm in the discounted setting, with the additional benefit of a low burn-in time.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 33 of its 49 references that are in the map. First posted on arXiv 24 May 2023.

Builds on

33 of 49 references.

References · 33

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  5. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  6. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  7. 2018Stochastic Variance-Reduced Policy Gradientcited by 103
  8. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  9. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  10. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  11. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  12. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
21 more
  1. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  2. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  3. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  4. 2020Q-learning with Logarithmic Regretcited by 59
  5. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  6. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  7. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  8. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  10. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  12. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  13. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  14. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  15. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  16. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
  17. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  18. 2020Regret Bounds for Discounted MDPscited by 19
  19. 2019Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimizationcited by 15
  20. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  21. 2017Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Timecited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 2; 2026: 2.

8 papers.

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  2. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  3. 2025Emoti-Attack: Zero-Perturbation Adversarial Attacks on NLP Systems via Emoji Sequencescited by 5
  4. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  5. 2024Enhancing Classification Performance via Reinforcement Learning for Feature Selectioncited by 2
  6. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  7. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscited by 1
  8. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0