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

Han Zhong; Yinyu Ye

cs.LGOct 1, 2026

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

Authors: Han Zhong, Yinyu Ye

Organizations: Shanghai Jiao Tong University · Shanghai Jiao Tong University, SIMIS, and Stanford University

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.

Figures & tables

Panel of Figure 1 — Figure 1: We give an exact LP representation for the blue class and strongly polynomial algorithms for the green classes under structural conditions (Sections 3 – 5 ). Here $\geq_{\mathrm{sp}}$ denotes a strongly polynomial reduction from general LP to RMDPs. The arrows summarize the boundaries in Section 6 .

\bigl([\mathbf{r}^{\tau^{t+1}}]_{s},[\mathbf{P}^{\tau^{t+1}}]_{s,:}^{\top}\bigr)\in\operatorname*{arg\,min}_{(r,\mathbf{p})\in\mathcal{M}_{s,\pi(s)}}\{r+\gamma\mathbf{p}^{\top}\mathbf{u}^{\tau^{t}}\},\quad\forall s\in\mathcal{S}.

(4.2)

Algorithm 2 Robust policy evaluation by policy iteration

Result	Model	Complexity bound
Theorem 4.2	Polyhedral RMDPs	$O\bigl((A-S+1)[(1+\mathsf{G})(S^{3}+\mathsf{C}_{\rm in})+\mathsf{C}_{\rm out}]\bigr)$
Corollary 5.4	$\ell_{1}$ RMDPs Interval RMDPs (including weighted $\ell_{\infty}$ RMDPs)	$O\bigl((A-S+1)[S^{4}+AS]\bigr)$
Corollary 5.6	Weighted $\ell_{1}$ RMDPs Wasserstein RMDPs	$O\bigl((A-S+1)[S^{7}+AS\log(2+S)]\bigr)$
Theorem 5.9	Turn-based stochastic games	$O\bigl((1+\mathsf{G}_{\max})[(1+\mathsf{G}_{\min})(S^{3}+\mathsf{C}_{\min})+\mathsf{C}_{\max}]\bigr)$

Table 1: Summary of our arithmetic complexity bounds at fixed discount.

\displaystyle\left\{\begin{aligned} \tau^{0}(s)&=\pi^{k}(s),&&s\in\mathcal{S}_{\max},\\ \tau^{0}(s)&\in\operatorname*{arg\,min}_{(r,\mathbf{p})\in\mathcal{M}_{s}}r,&&s\in\mathcal{S}_{\min}.\end{aligned}\right.

(5.14)

Algorithm 3 Strategy iteration for turn-based stochastic games

Explore similar work

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Jun 12, 2026Tianhao Wu, Matthew Zurek, Weina Wang +1Markov Decision Processes Sample Complexity
Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University
Robust Parameter Learning for Uncertain MDPs
May 2, 2026Yannik Schnitzer, Alessandro Abate, David ParkerMarkov Decision Processes Learning-Augmented Algorithms
University of Oxford, Oxford, United Kingdom
Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games
Aug 25, 2026Durgam Latha, Dion Reji, S. Akshay +2Partially Observable Markov Decision Process Observable Stochastic Game
Indian Institute of Technology Bombay Mumbai, India · Nanyang Technological University Singapore, Singapore

Jun 12, 2026, cs.LGJ/K move · Enter open · S save

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie

Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University

Markov Decision Processes Sample Complexity Lyapunov Function

Open paper AskPDF arXiv

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms

N

. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in

N

. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an

O(1/\sqrt{N})

optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

Abstract

Explore similar work

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Robust Parameter Learning for Uncertain MDPs

Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games