Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908800788725760 |
|---|---|
| author | Asadi, Ali Chatterjee, Krishnendu Goharshady, Ehsan Karrabi, Mehrdad Montaseri, Alipasha Pagano, Carlo |
| author_facet | Asadi, Ali Chatterjee, Krishnendu Goharshady, Ehsan Karrabi, Mehrdad Montaseri, Alipasha Pagano, Carlo |
| contents | Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly--polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_23229 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs Asadi, Ali Chatterjee, Krishnendu Goharshady, Ehsan Karrabi, Mehrdad Montaseri, Alipasha Pagano, Carlo Artificial Intelligence Computational Complexity Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly--polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question. |
| title | Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs |
| topic | Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2601.23229 |