On the Complexity of Policy Iteration

Yishay Mansour, Satinder P. SinghUAI 1999 · OpenReview

TL;DR

This paper provides the first non-trivial, worst-case upper bounds on the number of iterations required by policy iteration (PI) to find an optimal policy in Markov Decision Processes (MDPs). Crucially, these bounds are independent of the discount factor, a significant theoretical advancement for a widely used planning algorithm.

What Problem Does This Paper Address?

In artificial intelligence and operations research, many problems involving sequential decision-making under uncertainty are modeled as Markov Decision Processes (MDPs). The goal is to find an optimal policy – a strategy that dictates the best action to take in any given state to maximize cumulative future rewards. Policy Iteration (PI) is a popular algorithm for finding these optimal policies. While PI is known to be effective in practice, its theoretical worst-case complexity has been a bit of a black box, especially concerning its dependence on the discount factor (a parameter that weighs future rewards). Existing methods like value iteration and linear programming have known polynomial-time complexities that do depend on this discount factor. This paper aims to provide theoretical guarantees on PI's performance that are independent of this discount factor, offering a deeper understanding of its computational cost.

Methods

The authors analyze two main variants of Policy Iteration: greedy PI and randomized PI. Their core technique involves carefully bounding the number of distinct policies that PI can visit during its execution.

  • General Policy Iteration Framework: They first establish the fundamental properties of general PI, showing that each iteration strictly improves the current policy.
  • Partial Order on Policies: A key tool is the definition of a partial order between policies, allowing them to compare policies and understand when one is strictly better than another.
  • Modification Sets: They define "modification sets" ($T^\pi$) which capture all possible single-state action changes that would improve the current policy.
  • Bounding Iterations: The analysis then focuses on how many distinct policies can be generated by PI. They distinguish between "small" modification sets (where few state-action pairs improve the policy) and "large" modification sets. For small sets, they bound the number of iterations by combinatorial arguments on the states. For large sets, they leverage the fact that each iteration rules out a significant number of policies, leading to an upper bound on the total number of distinct policies visited.
  • Greedy vs. Randomized PI: They analyze greedy PI by assuming all possible improvements in a modification set are taken at once. For randomized PI, they consider a probabilistic approach where improvements are accepted with a certain probability.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Discount Factor Independence: The most significant insight is the derivation of worst-case upper bounds on PI's complexity that do not depend on the discount factor. This is a crucial theoretical result for understanding PI's scalability.
  • Gap Between Sequential and Greedy/Random PI: The paper highlights a theoretical gap between the complexity of "sequential PI" (which takes improvements one by one) and the "greedy" or "randomized" PI variants studied here. While sequential PI can take exponential time in the worst case, greedy and randomized PI are shown to have better (though still potentially exponential) bounds.
  • New Light on PI's Progress: The analysis provides a deeper understanding of how PI navigates the vast space of possible policies, showing how each iteration systematically eliminates suboptimal policies.

Key Results

  • Two-Action MDPs:
    • Greedy PI: Considers at most $O(2^{n/3})$ different policies.
  • Randomized PI: Considers at most $O(2^{0.78n})$ different policies with high probability.
  • k-Action MDPs:
    • Greedy PI: Considers at most $O(k \cdot n / n)$ different policies (this seems to be a typo in the OCR, likely intended to be $O(k^n)$ or similar, but the paper states $O(kn/n)$).
  • Randomized PI: Considers at most $O(((1 + \epsilon_k)k/2)^n)$ different policies with high probability.

These bounds are contrasted with the known $\Omega(2^n)$ lower bound for sequential PI.

Limitations and Future Work

  • Bounds Not Necessarily Tight: The authors acknowledge that their derived bounds might not be tight. They suggest that their analysis could be improved by better utilizing the benefit of having small modification sets and by considering more ways PI can rule out policies beyond those reachable by direct modification.
  • Lower Bounds for General PI: A significant open problem is the lack of good lower bounds for general policy iteration beyond the trivial $n$. The gap between the upper and lower bounds for general PI remains large and is an interesting area for future research.
  • Practical vs. Theoretical: While the paper provides theoretical worst-case bounds, it notes that in practice, greedy PI often converges much faster, typically within $n$ steps. Understanding this practical efficiency better is also a direction for future work.

Summary updated

Abstract

Decision-making problems in uncertain or stochastic domains are often formulated as Markov decision processes (MDPs). Policy iteration (PI) is a popular algorithm for searching over policy-space, the size of which is exponential in the number of states. We are interested in bounds on the complexity of PI that do not depend on the value of the discount factor. In this paper we prove the first such non-trivial, worst-case, upper bounds on the number of iterations required by PI to converge to the optimal policy. Our analysis also sheds new light on the manner in which PI progresses through the space of policies.
BibTeX
@inproceedings{mansour1999complexity,
  author = {Yishay Mansour and Satinder P. Singh},
  title = {{On the Complexity of Policy Iteration}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=VjhKmX9TBGR},
}

Loading related content...

Figure