mlsanityData to 14 Oct 2026

Minimax Optimal Reinforcement Learning with Quasi-Optimism

arXiv 2503.00810 ↗First posted 2 Mar 2025cs.LG stat.MLcited by 2

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In our quest for a reinforcement learning (RL) algorithm that is both practical and provably optimal, we introduce EQO (Exploration via Quasi-Optimism). Unlike existing minimax optimal approaches, EQO avoids reliance on empirical variances and employs a simple bonus term proportional to the inverse of the state-action visit count. Central to EQO is the concept of quasi-optimism, where estimated values need not be fully optimistic, allowing for a simpler yet effective exploration strategy. The algorithm achieves the sharpest known regret bound for tabular RL under the mildest assumptions, proving that fast convergence can be attained with a practical and computationally efficient approach. Empirical evaluations demonstrate that EQO consistently outperforms existing algorithms in both regret performance and computational efficiency, providing the best of both theoretical soundness and practical effectiveness.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 42 of its 56 references that are in the map. First posted on arXiv 2 Mar 2025.

Builds on

42 of 56 references.

References · 42

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2023Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Taskscited by 327
  5. 2017Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agentscited by 269
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  10. 2017Deep Exploration via Randomized Value Functionscited by 156
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
30 more
  1. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  2. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  3. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  4. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  5. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  8. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  9. 2020Adaptive Reward-Free Explorationcited by 77
  10. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  11. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  12. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  13. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  14. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  15. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  16. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  17. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  18. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 40
  19. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 34
  20. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  21. 2023Foundations of Reinforcement Learning and Interactive Decision Makingcited by 33
  22. 2023Bridging RL Theory and Practice with the Effective Horizoncited by 31
  23. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  24. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  25. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  26. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  27. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  28. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  29. 2022A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Banditscited by 4
  30. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Group Distributionally Robust Optimization with Flexible Sample Queriescited by 2
  2. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Optimistic Q-learning for average reward and episodic reinforcement learning
  2. 2024Beyond Optimism: Exploration With Partially Observable Rewards
  3. 2025Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL
  4. 2024NeoRL: Efficient Exploration for Nonepisodic RL
  5. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  6. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning
  7. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  8. 2026Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation