Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

The gist: Howard’s policy iteration performs at least an exponential number of iterations on deterministic discounted Markov decision processes even when each state has at most two actions, revealing a price of algorithmic anarchy compared to strongly polynomial methods like Dantzig’s pivoting rule

The core finding regarding iteration complexity

The paper establishes an exponential iteration lower bound for Howard’s policy iteration on deterministic discounted Markov decision processes, with at most two actions per state. This rules out strong polynomiality of Howard’s policy iteration when the discount factor is part of the input and yields an exponential separation from the simplex method with Dantzig’s pivoting rule, which is proved to be strongly polynomial on this class. Even when each reward is restricted to logarithmic bit length, we obtain a stretched-exponential iteration lower bound.

The construction of hard instances

The paper constructs families of deterministic discounted MDPs to demonstrate these lower bounds.

1. Theorem 1.1 shows an exponential iteration lower bound for deterministic discounted MDPs, even when each state has at most two actions per state.

2. Theorem 1.2 provides a stretched-exponential lower bound with nonnegative integer rewards smaller than 4N, showing that superpolynomial iteration complexity persists with O(log N) bits per reward.

The mechanism of algorithmic anarchy

The gap between Howard’s decentralized and simultaneous selfish improvements and Dantzig’s coordinated selection of a single action with the largest gain across all states reveals a “price” of algorithmic anarchy. This occurs because Howard’s rule makes simultaneous local greedy updates using the same policy values, whereas Dantzig’s rule coordinates updates across states and re-evaluates after each switch.

The binary encoding and value ordering

The construction involves encoding a vector b in the first group of states with binary numbers, where the state si and s¯i represent the i-th bit. Lemma 2.1 proves that there exists a common threshold γ0 such that for all γ in (γ0, 1) and b not equal to 1, Vπ[b+] (s0) > V π[b] (s0), demonstrating the strict ordering of policies.

The policy iteration process

The paper details the five iterations required to transition from policy π[b] to π[b+]. The proof shows that each increment requires at least 5 iterations, yielding an iteration bound of at least 5(2d - 2) ≥ 2d iterations.

The price of optimality

Corollary 5.2 demonstrates that Howard’s rule can require exponentially many iterations even to halve the initial optimality gap at s0, while Dantzig’s rule reaches an optimal policy in polynomially many iterations. This highlights how the price of algorithmic anarchy also affects progress toward optimality.

Explicit constructions and bounds

Proposition 5.1 provides an explicit construction under the same reward restriction, showing that Howard’s policy iteration performs at least Nomega(log N) iterations from a specified initial policy. This result is achieved by setting d = m squared and using specific reward polynomials. The lower bound of 2d iterations therefore implies the claimed exp(omega(N 1/4)) bound.

Conclusion on complexity

The paper concludes that Howard’s rule can require exponentially many iterations even to halve the initial optimality gap at s0, while Dantzig’s rule reaches an optimal policy in polynomially many iterations. This highlights how the price of algorithmic anarchy also affects progress toward optimality. The discount requires O(N + log rmax) bits.

The role of AI assistance

We used generative AI to assist with some derivations, literature searches, proof checking, language editing, and LATEX formatting. The authors carefully reviewed all AI-assisted material and independently verified the mathematical arguments. The authors take full responsibility for this paper.

References

Asadi, A., Chatterjee, K. and de Raaij, J. (2025). Lower bound on Howard policy iteration for deterministic Markov decision processes. In Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, vol. 286 of Proceedings of Machine Learning Research. PMLR.

Fearnley, J. (2010). Exponential lower bounds for policy iteration. In Automata, Languages and Programming, vol. 6199 of Lecture Notes in Computer Science. Springer.

Goenka, R., Gupta, E., Khyalia, S. and Kalyanakrishnan, S. (2026). Upper bounds for all and max-gain policy iteration algorithms on deterministic MDPs. Mathematics of Operations Research, 51 806–828.

Hansen, T. D. (2012). Worst-case Analysis of Strategy Iteration and the Simplex Method. Ph.D. thesis, Aarhus University.

Hansen, T. D. and Zwick, U. (2010). Lower bounds for Howard’s algorithm for finding minimum mean-cost cycles. In Algorithms and Computation, vol. 6506 of Lecture Notes in Computer Science. Springer.

Hollanders, R., Delvenne, J.-C. and Jungers, R. M. (2012). The complexity of policy iteration is exponential for discounted Markov decision processes. In Proceedings of the 51st IEEE Conference on Decision and Control.

Howard, R. A. (1960). Dynamic Programming and Markov Processes. Technology Press of Massachusetts Institute of Technology, Cambridge, MA.

Mukherjee, D. and Kalyanakrishnan, S. (2025). Howard’s policy iteration is subexponential for deterministic Markov decision problems with rewards of fixed bit-size and arbitrary discount factor. In Proceedings of the International Conference on Automated Planning and Scheduling, vol. 35. AAAI Press.

Post, I. and Ye, Y. (2015). The simplex method is strongly polynomial for deterministic Markov decision processes. Mathematics of Operations Research, 40 859–868.

Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York.

Scherrer, B. (2016). Improved and generalized upper bounds on the complexity of policy iteration. Mathematics of Operations Research, 41 758–774.

Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. 2nd ed. MIT Press, Cambridge, MA.

Ye, Y. (2005). A new complexity result on solving the Markov decision problem. Mathematics of Operations Research, 30 733–749.

Ye, Y. (2011). The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research, 36 593–603.

--- Page 1 ---

The gist: Howard’s policy iteration performs at least an exponential number of iterations on deterministic discounted Markov decision processes even when each state has at most two actions, revealing a price of algorithmic anarchy

How it works

The paper constructs families of deterministic discounted MDPs to demonstrate these lower bounds <ref:2609.

1. The improved system can achieve an exponential iteration lower bound on Howard’s policy iteration for deterministic discounted MDPs with at most two actions per state, specifically at least exp(omega(N)) iterations (Theorem 1.1). This allows the system to rigorously prove that Howard's algorithm is not strongly polynomial when the discount factor is input, providing a theoretical justification for why it may fail to converge quickly in complex scenarios.

2. The system can generate instances of deterministic discounted MDPs where each state has at most two actions and each reward uses O(log N) bits, allowing it to test the limits of policy iteration complexity under bit-length constraints (Theorem 1.2 and Proposition 5.1). This capability is essential for developing robust reinforcement learning agents that operate in environments with high state/action complexity but constrained input representations.

3. The improved system can simulate the behavior of Howard's policy iteration against Dantzig’s pivoting rule, revealing a price of algorithmic anarchy where Howard’s rule makes simultaneous local greedy updates using the same policy values, whereas Dantzig’s rule coordinates updates across states and re-evaluates after each switch (Remark 3.2). This insight helps in designing decentralized learning systems that understand the trade-off between immediate local gain and coordinated global improvement.

4. The system can implement a method to determine the next policy in Howard's iteration, which involves comparing action values using the unscaled action values Qπ for the unshifted rewards, leading to comparisons such as "lim γ→1− ∆πt(s) ≥ 16fd−1 − (8fd−1 + fi) − 4fd−1 = 4fd−1 − fi > 0" (Step 4.1). This provides a precise mechanism for decision-making in the iteration process, ensuring that policy updates are based on rigorous value comparisons.

5. The system can be used to verify the convergence of Howard's policy iteration by showing that πt = π[b] implies πt+5 = π[b+] for the specified discount (Section 3.6). This confirms that the algorithm correctly implements binary counting, which is crucial for ensuring that sequential learning algorithms can effectively explore and reach optimal policies in structured environments.