# Finding good policies in average-reward Markov Decision Processes without prior knowledge

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 26 references that are in the map.
- First posted on arXiv 27 May 2024.

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

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [No-Regret Exploration in Goal-Oriented Reinforcement Learning](https://mlsanity.com/paper/1912.03517/) (2019)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error](https://mlsanity.com/paper/2201.12417/) (2022)
- [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)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [A Provably Efficient Sample Collection Strategy for Reinforcement Learning](https://mlsanity.com/paper/2007.06437/) (2020)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes](https://mlsanity.com/paper/1807.02373/) (2018)
- [Span-Based Optimal Sample Complexity for Average Reward MDPs](https://mlsanity.com/paper/2311.13469/) (2023)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)

## Built on by (most cited first, 13 of 13)

- [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)
- [Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL](https://mlsanity.com/paper/2506.20904/) (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)
- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Asymptotically Optimal Sequential Testing with Markovian Data](https://mlsanity.com/paper/2602.17587/) (2026)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Towards Blackwell Optimality: Bellman Optimality Is All You Can Get](https://mlsanity.com/paper/2510.13476/) (2025)
- [Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs](https://mlsanity.com/paper/2606.14095/) (2026)
- [Average-Reward Policy Identification from a Single Continuing Trajectory](https://mlsanity.com/paper/2610.20486/) (2026)

## Abstract (arXiv)

We revisit the identification of an varepsilon-optimal policy in average-reward Markov Decision Processes (MDP). In such MDPs, two measures of complexity have appeared in the literature: the diameter, D, and the optimal bias span, H, which satisfy H≤ D. Prior work have studied the complexity of varepsilon-optimal policy identification only when a generative model is available. In this case, it is known that there exists an MDP with D simeq H for which the sample complexity to output an varepsilon-optimal policy is Omega(SAD/varepsilon2) where S and A are the sizes of the state and action spaces. Recently, an algorithm with a sample complexity of order SAH/varepsilon2 has been proposed, but it requires the knowledge of H. We first show that the sample complexity required to estimate H is not bounded by any function of S,A and H, ruling out the possibility to easily make the previous algorithm agnostic to H. By relying instead on a diameter estimation procedure, we propose the first algorithm for (varepsilon,δ)-PAC policy identification that does not need any form of prior knowledge on the MDP. Its sample complexity scales in SAD/varepsilon2 in the regime of small varepsilon, which is near-optimal. In the online setting, our first contribution is a lower bound which implies that a sample complexity polynomial in H cannot be achieved in this setting. Then, we propose an online algorithm with a sample complexity in SAD2/varepsilon2, as well as a novel approach based on a data-dependent stopping rule that we believe is promising to further reduce this bound.