Policy iteration alternates exact policy evaluation with greedy improvement. In finite discounted MDPs it terminates in an optimal policy after finitely many strict improvements.
Policy improvement
The improvement theorem is the reason greedy steps are safe.
Theorem. Let \(\pi'\) be greedy with respect to \(v_\pi\), so \(T_{\pi'}v_\pi=T_*v_\pi\ge T_\pi v_\pi=v_\pi\). Then \(v_{\pi'}\ge v_\pi\) pointwise.
Proof. Since \(T_{\pi'}\) is monotone, \[ v_\pi\le T_{\pi'}v_\pi\le T_{\pi'}^2v_\pi\le\cdots. \] The iterates converge to the fixed point \(v_{\pi'}\) by contraction, so \(v_{\pi'}\ge v_\pi\).
Exact policy iteration
Exact policy iteration repeats evaluation and improvement.
Definition. Policy iteration constructs \(\pi_{k+1}\) greedy with respect to \(v_{\pi_k}\), after exactly evaluating \(v_{\pi_k}\).
Theorem. In a finite discounted MDP, exact policy iteration reaches an optimal policy in finitely many iterations.
Proof. The policy improvement theorem gives monotone improvement in value. If the value does not improve, the current policy is greedy with respect to its own value, hence satisfies the optimality equation and is optimal. Otherwise at least one state action changes to yield strict improvement. There are only finitely many deterministic stationary policies.
Modified policy iteration
Practical dynamic programming often evaluates only approximately before improving.
Definition. Modified policy iteration applies \(m\) evaluation sweeps \(T_{\pi_k}\) before taking a greedy policy-improvement step. Value iteration and policy iteration are limiting cases with \(m=0\) and exact evaluation.
Remark. The method trades computation per iteration against the number of improvement steps. Error bounds combine contraction during partial evaluation with approximate-greedy error.
Policy oscillation
Tie-breaking matters when several greedy actions have the same value.
Remark. Consistent tie-breaking prevents cycling among equivalent optimal policies in exact finite policy iteration. The value sequence remains monotone even when policies are not unique.
Evaluation and greedy improvement
Exact policy iteration alternates \[ V_k=V^{\pi_k}, \qquad \pi_{k+1}(s)\in\arg\max_a \{r(s,a)+\gamma P_aV_k(s)\}. \] Its key fact is global policy improvement from a one-step local comparison.
Theorem (policy improvement). If \(T^{\pi'}V^\pi\ge V^\pi\), then \[ V^{\pi'}\ge V^\pi. \] If the inequality is strict at a state reachable under \(\pi'\), improvement is strict there.
Proof. By monotonicity, \[ V^\pi\le T^{\pi'}V^\pi \le(T^{\pi'})^2V^\pi\le\cdots. \] Contraction sends the right side to \(V^{\pi'}\). Strictness propagates through states reached with positive discounted probability.
Theorem (finite termination). In a finite discounted MDP, exact policy iteration with a deterministic tie-breaking rule terminates after finitely many strict policy improvements at an optimal policy.
Proof. There are finitely many deterministic stationary policies. Policy improvement never decreases value. If the selected policy changes and tie-breaking avoids cycling among equal greedy policies, at least one reachable state's value improves. Hence no policy can recur. Termination means the current policy is greedy with respect to its own value, so \(T^\pi V^\pi=TV^\pi\); uniqueness of the optimal fixed point gives \(V^\pi=V^*\).
Modified policy iteration
Exact evaluation may be expensive. Modified policy iteration applies \(m_k\) evaluation sweeps after improvement: \[ V_{k+1}=(T^{\pi_{k+1}})^{m_k}V_k. \] \(m_k=1\) resembles value iteration; \(m_k=\infty\) is policy iteration. Under bounded evaluation errors, performance follows from contraction and approximate-greedy bounds. This continuum separates the computational cost of solving a linear system from the number of policy improvements.
Newton interpretation
The optimality equation is \(F(V)=V-TV=0\), a piecewise affine nonsmooth system. When the greedy action is locally unique, selecting that action fixes one affine piece: \[ F_{\pi}(V)=(I-\gamma P_\pi)V-r_\pi. \] Solving the policy-evaluation equation is the Newton step on that piece. Policy iteration is therefore a semismooth Newton method for Bellman's equation, which helps explain its often much faster local convergence than value iteration.