Policy Iteration

Policy iteration alternates full policy evaluation with greedy improvement, converging to an optimal policy in a finite number of steps.

Evaluate, then improve

Policy iteration solves an MDP by alternating two phases. First it fully evaluates the current policy, computing its value function. Then it improves the policy by acting greedily with respect to that value function. The cycle repeats until the policy stops changing.

Policy evaluation

Kronos motion — learning physics

Given policy pi, compute V^pi by iterating the Bellman expectation update V(s) <- sum over a of pi(a | s) sum over s' of P(s' | s, a) [ R + gamma V(s') ] until it converges. This yields exact values for the current policy.

Policy improvement

Given V^pi, form a new policy pi'(s) = argmax over a of sum over s' of P(s' | s, a) [ R + gamma V^pi(s') ]. The policy improvement theorem guarantees pi' is at least as good as pi, and strictly better unless pi is already optimal.

Convergence

Because each improvement step produces a strictly better policy and a finite MDP has finitely many deterministic policies, policy iteration converges to an optimal policy in a finite number of iterations. This finite-step guarantee is stronger than value iteration's asymptotic convergence.

Comparison with value iteration

Policy iteration: fewer iterations, each expensive (a full evaluation loop inside).
Value iteration: more iterations, each cheap (one sweep, no inner loop).
Modified policy iteration: run only a few evaluation sweeps per improvement, blending the two.

Both belong to the broader pattern of generalized policy iteration, in which evaluation and improvement interact until they reach mutual consistency at the optimal policy and value function.