# Robust Average-Reward Markov Decision Processes

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 57 references that are in the map.
- First posted on arXiv 2 Jan 2023.

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

- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Adversarial Attacks on Neural Network Policies](https://mlsanity.com/paper/1702.02284/) (2017)
- [Maximum Entropy RL (Provably) Solves Some Robust RL Problems](https://mlsanity.com/paper/2103.06257/) (2021)
- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Tactics of Adversarial Attack on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1703.06748/) (2017)
- [Robust Deep Reinforcement Learning with Adversarial Attacks](https://mlsanity.com/paper/1712.03632/) (2017)
- [EPOpt: Learning Robust Neural Network Policies Using Model Ensembles](https://mlsanity.com/paper/1610.01283/) (2016)
- [Delving into adversarial attacks on deep policies](https://mlsanity.com/paper/1705.06452/) (2017)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Robust Reinforcement Learning using Adversarial Populations](https://mlsanity.com/paper/2008.01825/) (2020)
- [Wasserstein Robust Reinforcement Learning](https://mlsanity.com/paper/1907.13196/) (2019)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Reinforcement Learning under Model Mismatch](https://mlsanity.com/paper/1706.04711/) (2017)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Distributionally Robust Counterpart in Markov Decision Processes](https://mlsanity.com/paper/1501.07418/) (2015)
- [On-Policy Deep Reinforcement Learning for the Average-Reward Criterion](https://mlsanity.com/paper/2106.07329/) (2021)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Robust Markov Decision Process: Beyond Rectangularity](https://mlsanity.com/paper/1811.00215/) (2018)
- [Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertainty](https://mlsanity.com/paper/2010.04870/) (2020)
- [Robust Reinforcement Learning with Wasserstein Constraint](https://mlsanity.com/paper/2006.00945/) (2020)
- [Steady-State Planning in Expected Reward Multichain MDPs](https://mlsanity.com/paper/2012.02178/) (2020)
- [Effective Scenarios in Multistage Distributionally Robust Optimization with a Focus on Total Variation Distance](https://mlsanity.com/paper/2109.06791/) (2021)

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

- [Model-Free Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2305.10504/) (2023)
- [Single-Trajectory Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2301.11721/) (2023)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Constrained Reinforcement Learning Under Model Mismatch](https://mlsanity.com/paper/2405.01327/) (2024)
- [Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning](https://mlsanity.com/paper/2502.16816/) (2025)
- [Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain](https://mlsanity.com/paper/2509.14203/) (2025)
- [Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.07040/) (2025)
- [Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems](https://mlsanity.com/paper/2303.12981/) (2023)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Planning and Learning in Average Risk-aware MDPs](https://mlsanity.com/paper/2503.17629/) (2025)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)
- [Beyond expected value: geometric mean optimization for long-term policy performance in reinforcement learning](https://mlsanity.com/paper/2508.21443/) (2025)
- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)
- [Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation](https://mlsanity.com/paper/2608.24146/) (2026)
- [Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs](https://mlsanity.com/paper/2511.05758/) (2025)
- [Robust Verification of Concurrent Stochastic Games](https://mlsanity.com/paper/2601.12003/) (2026)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [Solving Robust MDPs through No-Regret Dynamics](https://mlsanity.com/paper/2305.19035/) (2023)
- [Robust Offline Reinforcement Learning for Non-Markovian Decision Processes](https://mlsanity.com/paper/2411.07514/) (2024)
- [Robust Transfer Learning with Side Information](https://mlsanity.com/paper/2603.07921/) (2026)
- [Stationary Robust Mean-Field Games under Model Mismatches](https://mlsanity.com/paper/2606.22579/) (2026)
- [Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games](https://mlsanity.com/paper/2608.24986/) (2026)

## Abstract (arXiv)

In robust Markov decision processes (MDPs), the uncertainty in the transition kernel is addressed by finding a policy that optimizes the worst-case performance over an uncertainty set of MDPs. While much of the literature has focused on discounted MDPs, robust average-reward MDPs remain largely unexplored. In this paper, we focus on robust average-reward MDPs, where the goal is to find a policy that optimizes the worst-case average reward over an uncertainty set. We first take an approach that approximates average-reward MDPs using discounted MDPs. We prove that the robust discounted value function converges to the robust average-reward as the discount factor γ goes to 1, and moreover, when γ is large, any optimal policy of the robust discounted MDP is also an optimal policy of the robust average-reward. We further design a robust dynamic programming approach, and theoretically characterize its convergence to the optimum. Then, we investigate robust average-reward MDPs directly without using discounted MDPs as an intermediate step. We derive the robust Bellman equation for robust average-reward MDPs, prove that the optimal policy can be derived from its solution, and further design a robust relative value iteration algorithm that provably finds its solution, or equivalently, the optimal robust policy.