An algorithm for solving sequential decision problems (typically Markov decision processes) that alternates between evaluating the value of a current policy and improving the policy greedily with respect to that value until convergence to an optimal policy.

Principle

Alternate exact or approximate policy evaluation and policy improvement: compute state-action or state values for the current policy, then update the policy to choose actions that maximize those values, repeating until no improvement occurs.

Demonstration

In a finite-state Markov decision process, start with an arbitrary deterministic policy, compute the policy's value function by solving linear Bellman equations, then produce a new policy by choosing actions that maximize the one-step expected return; iterate these steps until the policy stabilizes.

Misapplication

Using full policy iteration with exact evaluation on extremely large or continuous state spaces without approximation can be computationally infeasible and lead to excessive memory use or runtime; applying greedy improvement when evaluation is severely biased can cause oscillation.

Consequence

When applied correctly to finite MDPs or with stable approximations, policy iteration converges in a finite number of steps to an optimal policy and typically requires fewer iterations than naive value iteration.

Reversal

Reversing the concept yields value iteration: repeatedly apply Bellman optimality updates to value estimates without maintaining an explicit evaluated policy, deriving a policy only after values converge.

Boundary

Applies to sequential decision processes where policies and value functions are well-defined; excludes non-sequential optimization problems, games with adversarial agents unless reformulated, and settings without a Markovian structure or well-defined transition probabilities.

Semantic Tension

Tension exists between exact policy evaluation (which is stable but costly) and approximate or sample-based evaluation (which is scalable but can introduce bias and instability in the improvement step).

Synthesis

Policy iteration is an alternating-evaluation scheme: evaluate a fixed decision rule, then improve the rule by greedy selection using the evaluated values; repeated alternation drives the system toward optimal sequential decisions under the assumed model.