Strongly Polynomial Time Complexity of Policy Iteration for L ∞ L_{\infty} Robust MDPs
Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano · 2026
Read Strongly Polynomial Time Complexity of Policy Iteration for L ∞ L_{\infty} Robust MDPs by Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-23229.txt.
Description
Ali Asadi and five co-authors bound the running time of policy looping for robust decision problems. Markov decision problems model sequential choices under doubt. Robust versions allow transition probabilities to vary within a set, and optimize against the worst case in that set.
For the L-infinity doubt model studied, they prove policy looping runs in strongly polynomial time. The model is expressive, covering classical problems and stochastic games. A firm time bound tells planners the method will finish predictably, not just eventually. Strongly polynomial bounds are the strong form of guarantee, independent of the numerical size of the inputs.
Catalog record
| CREATOR | Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-23229