No More Bit-Length Anxiety: Policy Iteration Goes Strongly Polynomial
Opening — Why this matters now Robust decision-making has always lived with an uncomfortable footnote: yes, the model is elegant, but the algorithms might be painfully sensitive to numerical precision. For practitioners building safety-critical or adversarial systems, that footnote matters. A lot. This paper closes one of those footnotes. Quietly, rigorously, and without hand-waving, it proves that policy iteration for a broad and expressive class of robust MDPs runs in strongly polynomial time—not just polynomial in bit-length, but polynomial in the structure of the problem itself. ...