mlsanityData to 7 Oct 2026

Towards Tight Bounds on the Sample Complexity of Average-reward MDPs

arXiv 2106.07046 ↗First posted 13 Jun 2021cs.LG cs.DS math.OCcited by 32

Not on the map. Why?

Abstract (arXiv)

We prove new upper and lower bounds for sample complexity of finding an ε-optimal policy of an infinite-horizon average-reward Markov decision process (MDP) given access to a generative model. When the mixing time of the probability transition matrix of all policies is at most tmix, we provide an algorithm that solves the problem using widetildeO(tmix ε-3) (oblivious) samples per state-action pair. Further, we provide a lower bound showing that a linear dependence on tmix is necessary in the worst case for any algorithm which computes oblivious samples. We obtain our results by establishing connections between infinite-horizon average-reward MDPs and discounted MDPs of possible further utility.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 9 of its 25 references that are in the map. First posted on arXiv 13 Jun 2021.

Builds on

9 of 25 references.

References · 9

  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. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  4. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  5. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  6. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  7. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  8. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  9. 2016Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and Morecited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 6; 2024: 5; 2025: 10; 2026: 5.

32 papers.

Sort:

By area:

  1. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  2. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  3. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 25
  4. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  5. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  6. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  7. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 13
  8. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 11
  9. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  10. 2022Logarithmic regret bounds for continuous-time average-reward Markov decision processescited by 7
  11. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  12. 2021Examining average and discounted reward optimality criteria in reinforcement learningcited by 6
20 more
  1. 2023Optimal Sample Complexity of Stable Discounted Markov Decision Processescited by 6
  2. 2023Infer and Adapt: Bipedal Locomotion Reward Learning from Demonstrations via Inverse Reinforcement Learningcited by 5
  3. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  4. 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Gamescited by 5
  5. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 3
  6. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
  7. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2
  8. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  9. 2025Faster Fixed-Point Methods for Multichain MDPscited by 2
  10. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  11. 2025Auto-exploration for online reinforcement learningcited by 2
  12. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  13. 2025Towards Blackwell Optimality: Bellman Optimality Is All You Can Getcited by 1
  14. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  15. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
  16. 2022Data-Driven Evaluation of Training Action Space for Reinforcement Learningcited by 0
  17. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  18. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
  19. 2026Mathematical methods of reinforcement learningcited by 0
  20. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0