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

arXiv:2610.02131v1 Announce Type: new 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 ell_1 and ell_infty RMDPs and establish new strongly polynomial bounds for general interval, weighted ell_1, and Wasserstein RMDPs, as well as turn-based stochastic games with these uncertainty sets.

Related

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
• Policy Gradient for Continuous-Time Robust Markov Decision Processes
• Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes

Source: arXiv cs.LG | 2026-10-02