# Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 1 Dec 2022.

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

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [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)
- [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)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint](https://mlsanity.com/paper/1812.03565/) (2018)
- [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)

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

- [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)
- [Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints](https://mlsanity.com/paper/2212.13861/) (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)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning](https://mlsanity.com/paper/2502.16816/) (2025)
- [Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach](https://mlsanity.com/paper/2505.19986/) (2025)
- [Optimal Sample Complexity of Stable Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.07477/) (2023)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [Span-Based Optimal Sample Complexity for Average Reward MDPs](https://mlsanity.com/paper/2311.13469/) (2023)
- [Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL](https://mlsanity.com/paper/2502.11238/) (2025)
- [Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.07040/) (2025)
- [Near-Optimal Sample Complexity Bounds for Constrained Average-Reward MDPs](https://mlsanity.com/paper/2509.16586/) (2025)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (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)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Faster Fixed-Point Methods for Multichain MDPs](https://mlsanity.com/paper/2506.20910/) (2025)
- [Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs](https://mlsanity.com/paper/2603.23926/) (2026)
- [Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions](https://mlsanity.com/paper/2608.06545/) (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)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective](https://mlsanity.com/paper/2605.28675/) (2026)
- [Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs](https://mlsanity.com/paper/2606.14095/) (2026)
- [Learning in Markovian bandits with non-observable states and constrained decision epochs](https://mlsanity.com/paper/2606.27448/) (2026)
- [Average-Reward Policy Identification from a Single Continuing Trajectory](https://mlsanity.com/paper/2610.20486/) (2026)

## Abstract (arXiv)

This work considers the sample complexity of obtaining an varepsilon-optimal policy in an average reward Markov Decision Process (AMDP), given access to a generative model (simulator). When the ground-truth MDP is weakly communicating, we prove an upper bound of widetilde O(H varepsilon-3 ln frac1δ) samples per state-action pair, where H := sp(h^*) is the span of bias of any optimal policy, varepsilon is the accuracy and δ is the failure probability. This bound improves the best-known mixing-time-based approaches in [Jin & Sidford 2021], which assume the mixing-time of every deterministic policy is bounded. The core of our analysis is a proper reduction bound from AMDP problems to discounted MDP (DMDP) problems, which may be of independent interests since it allows the application of DMDP algorithms for AMDP in other settings. We complement our upper bound by proving a minimax lower bound of Omega(|mathcal S| |mathcal A| H varepsilon-2 ln frac1δ) total samples, showing that a linear dependent on H is necessary and that our upper bound matches the lower bound in all parameters of (|mathcal S|, |mathcal A|, H, ln frac1δ) up to some logarithmic factors.