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

Excerpt

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 polynomia