Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Abstract
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.
Related
- Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
- Synthesis of the Transient Behaviour of Optimization Algorithms for Strongly Convex Objective Functions
- Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
- Strongly regular graph, strongly polynomial sequences, and two-level polynomials
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
BibTeX
@misc{zhong2026linear,
title = {{Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes}},
author = {Han Zhong and Yinyu Ye},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02131},
eprint = {2610.02131},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02131},
}
RIS
TY - UNPB
TI - Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
AU - Han Zhong
AU - Yinyu Ye
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02131
UR - https://arxiv.org/abs/2610.02131
AB - 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.
ER -