mlsanityData to 7 Oct 2026

Optimal Sample Complexity for Average Reward Markov Decision Processes

arXiv 2310.08833 ↗First posted 13 Oct 2023cs.LG math.OC stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

We resolve the open question regarding the sample complexity of policy learning for maximizing the long-run average reward associated with a uniformly ergodic Markov decision process (MDP), assuming a generative model. In this context, the existing literature provides a sample complexity upper bound of widetilde O(|S||A|tmix2 ε-2) and a lower bound of Omega(|S||A|tmix ε-2). In these expressions, |S| and |A| denote the cardinalities of the state and action spaces respectively, tmix serves as a uniform upper limit for the total variation mixing times, and ε signifies the error tolerance. Therefore, a notable gap of tmix still remains to be bridged. Our primary contribution is the development of an estimator for the optimal policy of average reward MDPs with a sample complexity of widetilde O(|S||A|tmixε-2). This marks the first algorithm and analysis to reach the literature's lower bound. Our new algorithm draws inspiration from ideas in Li et al. (2020), Jin and Sidford (2021), and Wang et al. (2023). Additionally, we conduct numerical experiments to validate our theoretical findings.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 13 of its 26 references that are in the map. First posted on arXiv 13 Oct 2023.

Builds on

13 of 26 references.

References · 13

  1. 2016CAD2RL: Real Single-Image Flight without a Single Real Imagecited by 227
  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. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  5. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  6. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  7. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  8. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  9. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
  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. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
1 more
  1. 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: 2023: 1; 2024: 5; 2025: 4; 2026: 3.

13 papers.

Sort:

  1. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 16
  2. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  3. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  4. 2023Span-Based Optimal Sample Complexity for Average Reward MDPscited by 5
  5. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  6. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
  7. 2025Policy Testing in Markov Decision Processescited by 1
  8. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  9. 2025Towards Blackwell Optimality: Bellman Optimality Is All You Can Getcited by 1
  10. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0
  11. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  12. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPscited by 0
1 more
  1. 2026Mathematical methods of reinforcement learningcited by 0