THE POLICY ITERATION

Evaluate a policy exactly, then greedily improve it — and repeat. On a finite Markov decision process this reaches the optimal policy in a finite number of steps, because every improvement is monotone (values never fall) and there are only so many policies to try. Rendered, not quoted.

source Ronald A. Howard, Dynamic Programming and Markov Processes, Technology Press / Wiley, 1960 — archive.org/details/dynamicprogrammi0000howa

Blue Team · builds & defends
3

The Model

A tiny MDP: 3 states, 2 actions each, discount γ=0.9, deterministic transitions. Only state 2 under action 0 pays a reward (+5) and loops on itself.

Policy evaluation solves the linear Bellman equation exactly: Vπ = (I − γPπ)−1 Rπ by Gaussian elimination — a closed-form value, not an iterated approximation.

5

The Lineage

the-value-iteration's cousin. Both descend from the-bellman-equation.

Value iteration nudges the value function toward the fixed point one Bellman backup at a time. Policy iteration moves whole policies: evaluate exactly, then swap the entire policy for its greedy improvement. Fewer, larger steps — both land on the same V*.

7

The Witness · live

Re-runs the policy-improvement theorem and the optimality equation against the live table below.

checking…
The Machine
4

Data In  in ↓

S = {0,1,2}, A = {0,1}, γ = 0.9
R(2,0)=+5   (all other R = 0)
0: a0→0, a1→1
1: a0→0, a1→2
2: a0→2, a1→1

Start policy π0 = [0, 0, 0] — the do-nothing default.

↓
0

The Panel  lit

Each row: a policy and the exact values it earns. Improvement is greedy w.r.t. those values; the loop halts when the policy stops changing.

↓
8

Data Out  out ↓

Proven optimum:

π* pending…

Red Team · attacks & breaks
1

The Adversary  wall

“Policy iteration must converge, so any improvement rule works.”

False. Convergence rides entirely on the policy-improvement theorem: greedy w.r.t. Vπ gives Q ≥ Vπ, hence Vπ' ≥ Vπ. Break that inequality and the guarantee is void — values fall and the loop can cycle forever.

2

The Graveyard

  • “Policy iteration is just value iteration.”
    → No: it solves Vπ exactly between improvements, not one backup at a time.
  • “It can loop forever.”
    → No: argmax improvement is monotone, and there are only finitely many deterministic policies (23=8), so it halts in ≤8 steps.
  • “You need γ<1 for it to converge.”
    → AMBER: γ<1 guarantees a unique Vπ. Proper/absorbing rewards can converge undiscounted too, but that needs extra conditions — assumed away here.
6

The Tamper

Replace argmax with argmin in improvement — greedily pick the worst action. The inequality reverses (Q ≤ Vπ), values drop each step, and π* is never reached. The Witness (7) catches the first non-monotone step.