mlsanityData to 7 Oct 2026

Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments

arXiv 2301.13446 ↗First posted 31 Jan 2023cs.LG stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

We study variance-dependent regret bounds for Markov decision processes (MDPs). Algorithms with variance-dependent regret guarantees can automatically exploit environments with low variance (e.g., enjoying constant regret on deterministic MDPs). The existing algorithms are either variance-independent or suboptimal. We first propose two new environment norms to characterize the fine-grained variance properties of the environment. For model-based methods, we design a variant of the MVP algorithm (Zhang et al., 2021a). We apply new analysis techniques to demonstrate that this algorithm enjoys variance-dependent bounds with respect to the norms we propose. In particular, this bound is simultaneously minimax optimal for both stochastic and deterministic MDPs, the first result of its kind. We further initiate the study on model-free algorithms with variance-dependent regret bounds by designing a reference-function-based algorithm with a novel capped-doubling reference update schedule. Lastly, we also provide lower bounds to complement our upper bounds.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 35 of its 72 references that are in the map. First posted on arXiv 31 Jan 2023.

Builds on

35 of 72 references.

References · 35

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2016OpenAI Gymcited by 1,684
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  12. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
23 more
  1. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  2. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  3. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  4. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  5. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  6. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  7. 2020Q-learning with Logarithmic Regretcited by 59
  8. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  10. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  11. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  12. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  13. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  14. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  15. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  16. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  17. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  18. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  19. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  20. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  21. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  22. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  23. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14

Built on by

Cited by year (2026 to 7 Oct)

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

17 papers.

Sort:

By area:

  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  2. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  3. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  4. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  5. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  6. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  7. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  8. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  9. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 3
  10. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  11. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  12. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
5 more
  1. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  2. 2024Utilizing Maximum Mean Discrepancy Barycenter for Propagating the Uncertainty of Value Functions in Reinforcement Learningcited by 0
  3. 2024State-free Reinforcement Learningcited by 0
  4. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  5. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0