Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 51 references that are in the map. First posted on arXiv 1 Oct 2026.
Builds on
17 of 51 references.
References · 17
- 2022Robust Reinforcement Learning using Offline Datacited by 95
- 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
- 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
- 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
- 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
- 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
- 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
- 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
- 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
- 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
- 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
- 2022On the convex formulations of robust Markov decision processescited by 8
5 more
- 2026Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPscited by 5
- 2013Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomialcited by 3
- 2026On the Complexity of Robust Markov Decision Processes and Bisimulation Metricscited by 1
- 2026The Simple Strategy-Iteration Method is Strongly Polynomial for the Turn-Based Deterministic Forward Gamecited by 1
- 2026Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchycited by 1
Built on by
Not cited yet.