mlsanityData to 7 Oct 2026

Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs

arXiv 2403.11477 ↗First posted 18 Mar 2024cs.LG cs.IT math.ITcited by 16

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. For weakly communicating MDPs, we establish the complexity bound widetildeO(SAfracHvarepsilon2 ), 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. We also initiate the study of sample complexity in general (multichain) average-reward MDPs. We argue a new transient time parameter B is necessary, establish an widetildeO(SAfracB + Hvarepsilon2) complexity bound, and prove a matching (up to log factors) minimax lower bound. Both results are based on reducing the average-reward MDP to a discounted MDP, which requires new ideas in the general setting. To optimally analyze this reduction, we develop improved bounds for γ-discounted MDPs, showing that widetildeO(SAfracH(1-γ)2varepsilon2 ) and widetildeO(SAfracB + H(1-γ)2varepsilon2 ) samples suffice to learn varepsilon-optimal policies in weakly communicating and in general MDPs, respectively. Both these results circumvent the well-known minimax lower bound of widetildeOmega(SAfrac1(1-γ)3varepsilon2 ) for γ-discounted MDPs, and establish a quadratic rather than cubic horizon dependence for a fixed MDP instance.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 15 of its 28 references that are in the map. First posted on arXiv 18 Mar 2024.

Builds on

15 of 28 references.

References · 15

  1. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  2. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  3. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  4. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  5. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  6. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  7. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  8. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  9. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  10. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  11. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  12. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 15
3 more
  1. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  2. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  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: 2024: 2; 2025: 8; 2026: 6.

16 papers.

Sort:

By area:

  1. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 11
  2. 2024The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscited by 7
  3. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 6
  4. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 3
  5. 2025Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPscited by 3
  6. 2025Faster Fixed-Point Methods for Multichain MDPscited by 2
  7. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  8. 2025Towards Blackwell Optimality: Bellman Optimality Is All You Can Getcited by 1
  9. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  10. 2026Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotientscited by 1
  11. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  12. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 1
4 more
  1. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  2. 2025Near-Optimal Reinforcement Learning for Constrained Recurrence Objectivescited by 0
  3. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  4. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0