mlsanityData to 7 Oct 2026

Span-Based Optimal Sample Complexity for Average Reward MDPs

arXiv 2311.13469 ↗First posted 22 Nov 2023cs.LG cs.IT math.ITcited by 5

Not on the map. Why?

Abstract (arXiv)

We study the sample complexity of learning an varepsilon-optimal policy in an average-reward Markov decision process (MDP) under a generative model. We establish the complexity bound widetildeOleft(SAfracHvarepsilon2 right), where H is the span of the bias function of the optimal policy and SA is the cardinality of the state-action space. Our result is the first that is minimax optimal (up to log factors) in all parameters S,A,H and varepsilon, improving on existing work that either assumes uniformly bounded mixing times for all policies or has suboptimal dependence on the parameters. Our result is based on reducing the average-reward MDP to a discounted MDP. To establish the optimality of this reduction, we develop improved bounds for γ-discounted MDPs, showing that widetildeOleft(SAfracH(1-γ)2varepsilon2 right) samples suffice to learn a varepsilon-optimal policy in weakly communicating MDPs under the regime that γ ≥ 1 - frac1H, circumventing the well-known lower bound of widetildeOmegaleft(SAfrac1(1-γ)3varepsilon2 right) for general γ-discounted MDPs. Our analysis develops upper bounds on certain instance-dependent variance parameters in terms of the span parameter. These bounds are tighter than those based on the mixing time or diameter of the MDP and may be of broader use.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 9 of its 18 references that are in the map. First posted on arXiv 22 Nov 2023.

Builds on

9 of 18 references.

References · 9

  1. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  2. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  3. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  4. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  5. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  6. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  7. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  8. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  9. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 2.

5 papers.

  1. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  2. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  3. 2024The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscited by 7
  4. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  5. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1