# Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 1 Oct 2026.

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

- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [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)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [Sample Complexity of Variance-reduced Distributionally Robust Q-learning](https://mlsanity.com/paper/2305.18420/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation](https://mlsanity.com/paper/2402.15399/) (2024)
- [Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2403.09621/) (2024)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPs](https://mlsanity.com/paper/2601.23229/) (2026)
- [Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial](https://mlsanity.com/paper/1310.4953/) (2013)
- [On the Complexity of Robust Markov Decision Processes and Bisimulation Metrics](https://mlsanity.com/paper/2604.26748/) (2026)
- [The Simple Strategy-Iteration Method is Strongly Polynomial for the Turn-Based Deterministic Forward Game](https://mlsanity.com/paper/2606.29568/) (2026)
- [Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy](https://mlsanity.com/paper/2609.40147/) (2026)

## Abstract (arXiv)

We study linear programming (LP) representations and strongly polynomial algorithms for robust Markov decision processes (RMDPs) with rational polyhedral state-action rectangular uncertainty in rewards and transitions. By encoding a finite sequence of robust policy-iteration steps, we construct a single LP whose optimal solutions recover the robust optimal value and all optimal stationary randomized policies. At fixed discount, the LP has polynomial dimension and encoding length and can be constructed in strongly polynomial time. We also develop a general complexity analysis of robust policy iteration that combines the cost of minimizing over uncertainty sets with the number of iterations needed to evaluate a policy. For a fixed discount factor, we use this analysis to improve the known complexity bounds for ℓ1 and ℓ_∞ RMDPs and establish new strongly polynomial bounds for general interval, weighted ℓ1, and Wasserstein RMDPs, as well as turn-based stochastic games with these uncertainty sets.