Policy Iteration

344. Policy Iteration

An alternative to value iteration for infinite-horizon MDPs. Alternates between evaluating the current policy and improving it.

344.1. Algorithm

Initialize π(s) ← arbitrary action

Repeat:
    # Policy evaluation: compute J^π by solving the linear system
    #     J^π(s) = c(s, π(s)) + γ Σ_{s'} P(s' | s, π(s)) J^π(s')
    # i.e., (I - γ P_π) J^π = c_π        (|S| × |S| linear system)

    # Policy improvement: greedy w.r.t. J^π
    For each s ∈ S:
        π'(s) ← argmin over a of { c(s, a) + γ Σ_{s'} P(s' | s, a) J^π(s') }

    If π' = π: stop
    π ← π'

Return π*

344.2. Two phases per iteration

Policy evaluation: solve $(𝐼 - 𝛾 𝑃_{𝜋}) 𝐽^{𝜋} = 𝑐_{𝜋}$ for the value function of the current policy $𝜋$ . This is a $| 𝒮︀ | \times | 𝒮︀ |$ linear system — exact, no approximation.
Policy improvement: greedy update — pick the action minimizing the Bellman expression using the current $𝐽^{𝜋}$ .

If policy improvement changes nothing, the current $𝜋$ is optimal (Bellman optimality is satisfied).

344.3. Why it terminates in finite steps

Each iteration strictly improves the policy (in value) unless already optimal. There are only $| 𝒜︀ |^{| 𝒮︀ |}$ deterministic policies, so the algorithm must terminate. In practice, it converges in very few iterations — often $𝑂 (| 𝒮︀ |)$ or fewer, regardless of $𝛾$ .

344.4. Cost per iteration

Policy evaluation: $𝑂 (| 𝒮︀ |^{3})$ (solve linear system) or fewer with iterative methods
Policy improvement: $𝑂 (| 𝒮︀ |^{2} \cdot | 𝒜︀ |)$

So per iteration, policy iteration is more expensive than value iteration. But it needs fewer iterations. Total cost is comparable.

344.5. Modified policy iteration

A middle ground: don’t fully solve the linear system in step 1. Instead, do $𝑘$ value-iteration-like sweeps to approximate $𝐽^{𝜋}$ :

Repeat k times:
    For each s ∈ S:
        J(s) ← c(s, π(s)) + γ Σ_{s'} P(s' | s, π(s)) J(s')

Then improve. With $𝑘 = 1$ : equivalent to value iteration. With $𝑘 = \infty$ : full policy iteration. Tuning $𝑘$ trades off per-iteration cost vs number of iterations.

344.6. Comparison with value iteration

	Value iteration	Policy iteration
Per-iter cost	low	high
Number of iterations	many	few
Convergence	asymptotic ( $𝐽 \to 𝐽^{*}$ )	exact terminator (finite policy space)
Memory	$\| 𝒮︀ \|$ for $𝐽$	$\| 𝒮︀ \|$ for $𝐽$ and $𝜋$
Practical	simpler, more common in DP literature	favored for small / mid state spaces

344.7. Why policy iteration converges fast

The policy improvement theorem says that greedy update produces a policy with value at least as good componentwise — strictly better at some state if the policy wasn’t already optimal. In high-discount problems, value iteration can take thousands of iterations; policy iteration usually takes 10–50.

344.8. Linear-programming reformulation

Both value iteration and policy iteration solve the same fixed-point problem:

min_{𝐽} \sum_{𝑠} 𝜇_{0} (𝑠) 𝐽 (𝑠) s.t. 𝐽 (𝑠) \leq 𝑐 (𝑠, 𝑎) + 𝛾 \sum_{𝑠^{'}} 𝑃 (𝑠^{'} | 𝑠, 𝑎) 𝐽 (𝑠^{'}), \forall (𝑠, 𝑎)

This LP has $| 𝒮︀ |$ variables and $| 𝒮︀ | \cdot | 𝒜︀ |$ constraints. Solving it directly is a third approach (and the connection to LP duality reveals deep structure of MDPs).

344.9. See also

Value Iteration — the alternative
Bellman Equation
Stochastic DP
Linear Programming — LP reformulation