mlsanityData to 7 Oct 2026

Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs

arXiv 2603.23926 ↗First posted 25 Mar 2026cs.LG cs.IT math.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-in'' costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the γ-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in both settings take the form tildeO( √SA,Var + lower-order terms), where S,A are the state and action space sizes, and Var captures cumulative transition variance. This implies minimax-optimal average-reward and γ-regret bounds in the worst case but also adapts to easier problem instances, for example yielding nearly constant regret in deterministic MDPs. Furthermore, our algorithm enjoys significantly improved lower-order terms for the average-reward setting. With prior knowledge of the optimal bias span Vert h^starVertsp, our algorithm obtains lower-order terms scaling as Vert h^starVertsp S2 A, which we prove is optimal in both Vert h^starVertsp and A. Without prior knowledge, we prove that no algorithm can have lower-order terms smaller than Vert h^star Vertsp2 S A, and we provide a prior-free algorithm whose lower-order terms scale as Vert h^starVertsp2 S3 A, nearly matching this lower bound. Taken together, these results completely characterize the optimal dependence on Vert h^starVertsp in both leading and lower-order terms, and reveal a fundamental gap in what is achievable with and without prior knowledge.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 30 of its 36 references that are in the map. First posted on arXiv 25 Mar 2026.

Builds on

30 of 36 references.

References · 30

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  3. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  4. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  5. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  6. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  7. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  9. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  10. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  11. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  12. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
18 more
  1. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  2. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  3. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  4. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  5. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 15
  6. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraintscited by 15
  7. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  8. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  9. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  10. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  11. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 11
  12. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  13. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  14. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  15. 2024The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscited by 7
  16. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 3
  17. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 2
  18. 2025EUBRL: Epistemic Uncertainty Directed Bayesian Reinforcement Learningcited by 2

Built on by

Not cited yet.