# Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 50 references that are in the map.
- First posted on arXiv 6 Aug 2026.

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

- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Discounted Reinforcement Learning Is Not an Optimization Problem](https://mlsanity.com/paper/1910.02140/) (2019)
- [Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.07040/) (2025)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)

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

- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)
- [Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication](https://mlsanity.com/paper/2609.32727/) (2026)

## Abstract (arXiv)

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an varepsilon-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over (s,a)-rectangular total-variation uncertainty sets of radius at most σ. Let H0 and Hσ denote the nominal and robust optimal bias spans, respectively. We identify σ H0 as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is  NSA asymp fracSAvarepsilon2begincases minH0,Hσ, & varepsilongtrsimσ H0, minH0,Hσ+σ Hσ2, & varepsilonlesssimσ H0. endcases  Here S and A are the numbers of states and actions, and N is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.