# Solving Long-run Average Reward Robust MDPs via Stochastic Games

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 36 references that are in the map.
- First posted on arXiv 21 Dec 2023.

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

- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [Safe Policy Improvement by Minimizing Robust Baseline Regret](https://mlsanity.com/paper/1607.03842/) (2016)
- [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)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality](https://mlsanity.com/paper/2312.03618/) (2023)

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

- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs](https://mlsanity.com/paper/2405.04941/) (2024)
- [Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPs](https://mlsanity.com/paper/2601.23229/) (2026)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)
- [Robust Verification of Concurrent Stochastic Games](https://mlsanity.com/paper/2601.12003/) (2026)
- [Quantifying Risk Under Evolving Uncertainty: Belief-Dependent Robustness for Safe Sequential Decision Making](https://mlsanity.com/paper/2608.17574/) (2026)
- [Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games](https://mlsanity.com/paper/2608.24986/) (2026)
- [Quantitative Analysis of ω-Regular Robust MDPs](https://mlsanity.com/paper/2608.25968/) (2026)

## Abstract (arXiv)

Markov decision processes (MDPs) provide a standard framework for sequential decision making under uncertainty. However, MDPs do not take uncertainty in transition probabilities into account. Robust Markov decision processes (RMDPs) address this shortcoming of MDPs by assigning to each transition an uncertainty set rather than a single probability value. In this work, we consider polytopic RMDPs in which all uncertainty sets are polytopes and study the problem of solving long-run average reward polytopic RMDPs. We present a novel perspective on this problem and show that it can be reduced to solving long-run average reward turn-based stochastic games with finite state and action spaces. This reduction allows us to derive several important consequences that were hitherto not known to hold for polytopic RMDPs. First, we derive new computational complexity bounds for solving long-run average reward polytopic RMDPs, showing for the first time that the threshold decision problem for them is in NP cap coNP and that they admit a randomized algorithm with sub-exponential expected runtime. Second, we present Robust Polytopic Policy Iteration (RPPI), a novel policy iteration algorithm for solving long-run average reward polytopic RMDPs. Our experimental evaluation shows that RPPI is much more efficient in solving long-run average reward polytopic RMDPs compared to state-of-the-art methods based on value iteration.