Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
Robust Markov decision processes with polyhedral uncertainty lack exact convex representations because the natural robust Bellman inequalities become bilinear or union-of-polyhedra constraints. This paper shows how to encode a finite sequence of robust policy-iteration steps into a single exact LP whose optimal face recovers the robust optimal value and all optimal stationary randomized policies. At fixed discount, the LP has polynomial dimension and encoding length, and the authors use this representation together with a unified complexity analysis to prove strongly polynomial bounds for several standard uncertainty sets—including $\ell_1$, weighted $\ell_1$, interval, and Wasserstein—that previously lacked such guarantees.
The paper delivers a significant theoretical advance: the first exact LP representation for polyhedral SA-rectangular RMDPs that can be constructed in strongly polynomial time at fixed discount, alongside improved or new strongly polynomial algorithms for several uncertainty classes. However, the positive results are tightly circumscribed. The authors prove that the general problem without structural conditions is at least as hard as general LP (Proposition 4.1), that exact LP representations uniform in the discount factor would solve parity games (Corollary 6.1), and that state-rectangular instances can have irrational optimal values and policies (Proposition 6.2). Thus the guarantees apply only under the fixed-discount, state-action rectangular assumptions.
The LP construction in Theorem 3.1 is the clearest contribution. By unrolling robust policy iteration into a compact sequence of linear constraints and collapsing lexicographic priorities into a single weighted objective, the authors bypass the exponential enumeration of deterministic policies and keep the LP size at $O(AN T_\gamma)$ variables and constraints. The complexity framework in Theorem 4.2 is also well-architected: it cleanly bounds total arithmetic operations by separating the outer policy-iteration count from the inner cost of minimizing over uncertainty sets, yielding a unified template that specializes to strongly polynomial bounds for $\ell_1$, interval, weighted $\ell_1$, and Wasserstein cases.
The strongly polynomial headline comes with meaningful limitations. First, the dimension bound depends on $T_\gamma = O\bigl(1 + \frac{1}{1-\gamma}\log\frac{2}{1-\gamma}\bigr)$, so the construction is only polynomial when the discount factor is fixed; as $\gamma \to 1$ the LP grows without bound. Second, the general policy-evaluation bound requires the structural condition (4.4) with a parameter $\mathsf{G}$ controlling the number of distinct gap scales; this is not automatic and the paper verifies it only for specific uncertainty models. Third, the state-rectangular and discount-as-input settings are explicitly excluded by hardness and irrationality results, limiting the scope of exact rational LP recovery.
The evidence is rigorous and the comparisons are fair. The authors directly answer the open question of Grand-Clément and Petrik (2025) by providing an exact convex formulation without entropy regularization, and they improve the bounds of Asadi et al. (2026b) for $\ell_1$ and $\ell_\infty$ RMDPs. The reduction in Proposition 4.1 carefully justifies the need for structural assumptions, while the application section derives explicit bounds for each uncertainty model from the general template. Citations to Ye (2011), Hansen et al. (2013), and the stochastic-games literature are accurate and appropriately scoped.
Reproduction is theoretically possible from the text but nontrivial in practice. The paper supplies explicit pseudocode (Algorithms 1 and 2), the full LP formulation (3.18), and constructive bounds in the appendices for all constants ($V$, $M$, $\varepsilon$, $W$). However, no code or data repository is mentioned. An independent implementation would require exact rational arithmetic for the lexicographic LP, careful construction of the uniform gap bound $\varepsilon$, and exact solution of the policy-evaluation linear systems $(\mathbf{I}-\gamma\mathbf{P}^\tau)\mathbf{u}^\tau = \mathbf{r}^\tau$.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.