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

arXiv: https://arxiv.org/abs/2106.07046 · HTML: https://mlsanity.com/paper/2106.07046/

## Key facts

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

## Builds on (most cited first, 9 of 9)

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Regret Bounds for Reinforcement Learning via Markov Chain Concentration](https://mlsanity.com/paper/1808.01813/) (2018)
- [Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More](https://mlsanity.com/paper/1608.03270/) (2016)

## Built on by (most cited first, 30 of 33)

- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs](https://mlsanity.com/paper/2403.11477/) (2024)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Logarithmic regret bounds for continuous-time average-reward Markov decision processes](https://mlsanity.com/paper/2205.11168/) (2022)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Examining average and discounted reward optimality criteria in reinforcement learning](https://mlsanity.com/paper/2107.01348/) (2021)
- [Optimal Sample Complexity of Stable Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.07477/) (2023)
- [Infer and Adapt: Bipedal Locomotion Reward Learning from Demonstrations via Inverse Reinforcement Learning](https://mlsanity.com/paper/2309.16074/) (2023)
- [Span-Based Optimal Sample Complexity for Average Reward MDPs](https://mlsanity.com/paper/2311.13469/) (2023)
- [Provable Policy Gradient Methods for Average-Reward Markov Potential Games](https://mlsanity.com/paper/2403.05738/) (2024)
- [Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL](https://mlsanity.com/paper/2502.11238/) (2025)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Auto-exploration for online reinforcement learning](https://mlsanity.com/paper/2512.06244/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Faster Fixed-Point Methods for Multichain MDPs](https://mlsanity.com/paper/2506.20910/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Finite-Time Bounds for Average-Reward Fitted Q-Iteration](https://mlsanity.com/paper/2510.17391/) (2025)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Towards Blackwell Optimality: Bellman Optimality Is All You Can Get](https://mlsanity.com/paper/2510.13476/) (2025)

## 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.