mlsanityData to 7 Oct 2026

Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL

arXiv 2502.11238 ↗First posted 16 Feb 2025cs.LG cs.IT math.ITcited by 3

Not on the map. Why?

Abstract (arXiv)

We study the sample complexity of finding an varepsilon-optimal policy in average-reward Markov Decision Processes (MDPs) with a generative model. The minimax optimal span-based complexity of widetildeO(SAH/varepsilon2), where H is the span of the optimal bias function, has only been achievable with prior knowledge of the value of H. Prior-knowledge-free algorithms have been the objective of intensive research, but several natural approaches provably fail to achieve this goal. We resolve this problem, developing the first algorithms matching the optimal span-based complexity without H knowledge, both when the dataset size is fixed and when the suboptimality level varepsilon is fixed. Our main technique combines the discounted reduction approach with a method for automatically tuning the effective horizon based on empirical confidence intervals or lower bounds on performance, which we term horizon calibration. We also develop an empirical span penalization approach, inspired by sample variance penalization, which satisfies an oracle inequality performance guarantee. In particular this algorithm can outperform the minimax complexity in benign settings such as when there exist near-optimal policies with span much smaller than H.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 15 of its 27 references that are in the map. First posted on arXiv 16 Feb 2025.

Builds on

15 of 27 references.

References · 15

  1. 2016Variance-based regularization with convex objectivescited by 153
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  3. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  4. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  5. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  6. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  7. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  8. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  9. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  10. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  11. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  12. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
3 more
  1. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  2. 2024The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscited by 7
  3. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6

Built on by

Cited by year (2026 to 7 Oct)

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

3 papers.

  1. 2025Faster Fixed-Point Methods for Multichain MDPscited by 2
  2. 2025Towards Blackwell Optimality: Bellman Optimality Is All You Can Getcited by 1
  3. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0