Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

Technical Summary: Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

Problem Statement
The paper addresses a fundamental open problem in sequential decision-making under uncertainty: the existence of strongly polynomial-time algorithms for Robust Markov Decision Processes (RMDPs) with $L_\infty$ uncertainty sets and a fixed discount factor. While classical MDPs admit strongly polynomial algorithms for exact value computation (Ye, 2011), and polynomial-time algorithms exist for RMDPs via linear programming, the question of whether RMDPs admit strongly polynomial algorithms (where the number of arithmetic operations is independent of the bit-length of input coefficients) remained unresolved. Specifically, previous attempts to reduce $(s, a)$-rectangular RMDPs to turn-based stochastic games failed to yield polynomial-time reductions due to the exponential number of actions required to represent $L_\infty$ uncertainty polytopes.

Model and Definitions
The authors focus on $(s, a)$-rectangular RMDPs with $L_\infty$ uncertainty sets.

• $(s, a)$-rectangularity: The environment selects transition probabilities independently for each state-action pair, preserving a dynamic programming structure.
• $L_\infty$ Uncertainty: For each state-action pair $(s, a)$, the true transition vector lies within an $L_\infty$ ball of radius $\delta_{s,a}$ around a nominal estimate $\hat{P}_{s,a}$.
• Objective: The agent seeks a policy $\sigma$ that minimizes the worst-case expected discounted cost against an adversarial environment policy $\tau$.
• Strongly Polynomial Time: An algorithm is strongly polynomial if the number of arithmetic operations is bounded by a polynomial in the number of variables and constraints, and the size of numbers during computation is polynomial in the input size, independent of the numerical values of the coefficients.

Methodology
The paper analyzes the Robust Policy Iteration (PI) algorithm, which alternates between Policy Evaluation and Policy Improvement.

1. Robust Markov Chains (RMCs): The authors first analyze the simpler case where the agent has a single action per state (RMC-PI).

   • Policy Improvement: Instead of solving a Linear Program (LP) which depends on bit precision, the authors utilize a Homotopy Algorithm (Behzadian et al., 2021) to compute the optimal environment response. This algorithm runs in $O(n \log n)$ and produces policies with a specific structural property: the transition probabilities are adjusted by moving mass from "donor" states to "receiver" states until boundaries (0, 1, or the uncertainty radius) are hit.
   • Potential Function: A novel potential function $f_\tau(s, s', s'')$ is introduced to track the probability mass transfer allowed by the homotopy algorithm. This function measures the potential improvement in value by shifting mass from a state with lower optimal value to one with higher optimal value.
   • Combinatorial Bounds: The authors prove that the "discrepancy" between the current policy's transition probabilities and the optimal ones decreases geometrically. Crucially, they establish a combinatorial lemma (Lemma 8) regarding the number of distinct Most Significant Bits (MSBs) in signed subset sums of real numbers. This lemma, derived from a more general theorem (Theorem 20/21), bounds the number of possible MSBs by $O(|X| \log |X|)$.
   • Convergence Argument: By combining the geometric contraction of the value error (Lemma 2) with the finite number of possible MSBs for the discrepancy (Lemma 8), the authors show that the algorithm cannot make arbitrarily small updates indefinitely. The MSB of the discrepancy must change a polynomial number of times.

2. Robust MDPs (RMDPs): The analysis is extended to the general RMDP case (RMDP-PI).

   • The algorithm iteratively solves the RMC subproblem for the current agent policy to find the worst-case environment response, then updates the agent policy to minimize the resulting cost.
   • A similar potential function is defined for actions, tracking the cost of deviating from the optimal agent action.
   • The same logic applies: the action with the maximum potential cannot persist for more than a logarithmic number of iterations before the value error contraction forces a change.

Key Contributions and Results

• Strongly Polynomial RMC-PI: The authors prove that Robust Policy Iteration for RMCs with $n$ states and a constant discount factor $\gamma$ terminates in $O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ iterations. Since each iteration involves polynomial-time operations (matrix inversion and homotopy steps), the total runtime is strongly polynomial.
• Strongly Polynomial RMDP-PI: The result is generalized to RMDPs with $n$ states and $m$ actions. The algorithm terminates in $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ iterations, establishing that RMDP-PI is also strongly polynomial.
• Combinatorial Lemma: The paper introduces Lemma 8, a novel combinatorial result bounding the number of distinct MSBs in signed subset sums, which is central to the complexity proof. The authors note that a stronger version of this theorem was independently derived by an AI research agent (Aletheia), highlighting a contribution of AI to mathematics.

Significance and Claims
The paper claims to resolve a major open problem in the theory of robust optimization. By demonstrating that a robust policy iteration algorithm runs in strongly polynomial time for $(s, a)$-rectangular $L_\infty$ RMDPs, the authors generalize the seminal result of Ye (2011) for classical MDPs to the robust setting. This result is significant because:

1. It provides a theoretical guarantee for computing exact values (rather than approximations) for RMDPs without dependence on the bit-length of input parameters.
2. It overcomes the limitations of previous reduction techniques that failed due to exponential blow-up in the number of actions.
3. It establishes that the robust Bellman operator, despite the infinite uncertainty set, can be navigated efficiently using combinatorial properties of the homotopy algorithm.

The authors conclude that while the theoretical foundations are now established, future work could explore empirical studies on data-driven uncertainty sets and whether these potential-based arguments can lead to improved practical variants or stopping criteria. They also note that the question of polynomial bounds for standard MDP policy iteration variants remains open.