# Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 51 of its 98 references that are in the map.
- First posted on arXiv 18 May 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 51)

- [Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World](https://mlsanity.com/paper/1703.06907/) (2017)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [Sim-to-Real Transfer of Robotic Control with Dynamics Randomization](https://mlsanity.com/paper/1710.06537/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Survey](https://mlsanity.com/paper/2009.13303/) (2020)
- [A Study on Overfitting in Deep Reinforcement Learning](https://mlsanity.com/paper/1804.06893/) (2018)
- [EPOpt: Learning Robust Neural Network Policies Using Model Ensembles](https://mlsanity.com/paper/1610.01283/) (2016)
- [Off-Dynamics Reinforcement Learning: Training for Transfer with Domain Classifiers](https://mlsanity.com/paper/2006.13916/) (2020)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Reinforcement Learning in Economics and Finance](https://mlsanity.com/paper/2003.10014/) (2020)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [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)
- [Sample Complexity of Variance-reduced Distributionally Robust Q-learning](https://mlsanity.com/paper/2305.18420/) (2023)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Honor of Kings Arena: an Environment for Generalization in Competitive Reinforcement Learning](https://mlsanity.com/paper/2209.08483/) (2022)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2305.10504/) (2023)

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

- [Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions](https://mlsanity.com/paper/2608.06545/) (2026)
- [Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotients](https://mlsanity.com/paper/2602.00474/) (2026)
- [Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximation](https://mlsanity.com/paper/2510.01721/) (2025)

## Abstract (arXiv)

Robust reinforcement learning (RL) under the average-reward criterion is essential for long-term decision-making, particularly when the environment may differ from its training dynamics. However, most existing studies focus on model-based settings and provide only asymptotic guarantees, hindering their principled understanding and practical deployment, especially in data-limited scenarios. We aim to close this gap by proposing a model-free algorithm, Robust Halpern Iteration (RHI). We first design our algorithm based on a black-box sampling oracle, which can estimate the worst-case performance accurately. We then derive the finite sample complexity of RHI under the generative model setting, assuming the sampling oracle. To concretely design such an oracle, we propose a K-order multi-level Monte-Carlo estimator, which is shown to have a lower bias compared to prior methods. We further instantiate our design for multiple uncertainty models, including KL and chi2 divergence sets, and show that our RHI algorithm achieves an varepsilon-optimal robust policy with a sample complexity of tildeOleft( fracSAH2varepsilon(2+o(1))right), where S,A are the number of states and actions, and H is the robust optimal span. Our result asymptotically matches the best complexity in robust average reward RL.