Foundations T20 / 27 · Decision and Optimization
Dynamic Programming: The Accounting for Two Iterations
Value iteration is cheap per step but needs many steps; policy iteration is expensive per round but needs few rounds. The policy improvement theorem guarantees strict non-decrease each round — which one is faster is a computable question on any concrete problem.
One-line takeaway
The policy improvement theorem (each round's new policy is no worse than the old one) + exact policy evaluation (solving a linear system) = policy iteration. It is the exact version of the «generalized policy iteration» framework, and actor-critic is its stochastic-approximation version.
Many design decisions in deep RL are projections of these two classic algorithms: why should the critic converge somewhat before the actor updates (evaluation before improvement)? Why does PPO stop after a few epochs (to keep the improvement theorem's premises from failing)? This lesson gives the precise provenance of these intuitions.
Why this tool exists
T7/T5 left one option unexplored: since V* is the fixed point of the Bellman operator, you can iterate directly (value iteration); or you can go two-phase — fix a policy and solve for its value exactly (this step is a linear system, no iterating-to-death needed), then use the value to improve the policy (policy iteration). Both roads lead to V*, but the ledgers differ.
Value iteration: O(|S|²|A|) per step (one Bellman backup), needing O(log(1/ε)/log(1/γ)) steps (T5's bound). Policy iteration: each round's policy evaluation solves an |S|-unknown linear system (O(|S|³), expensive), but the number of rounds is astonishingly small — often exact convergence within a handful of rounds.
Why so few rounds? The policy improvement theorem guarantees the value strictly rises each round, and the total number of policies is finite (|A|^|S|), so a never-repeating policy sequence must reach «no further improvement» within finitely many rounds — which is exactly the optimal policy. This is a combinatorial argument, independent of how tight γ's bound is.
Definitions
Definition 8.1 Policy evaluation
Fix π and solve the linear system V^π(s) = Σs' p(s'|s,π(s))[r + γV^π(s')] — |S| equations, |S| unknowns, coefficient matrix I−γP_π invertible (diagonally dominant for γ<1). Iterative methods also work (the modified Bellman operator, a γ-contraction; T5 applies).
Why define it this wayIn the finite case, «evaluation» means solving equations, not iterating — that is why each policy-iteration round is expensive, and also why it needs so few rounds (the evaluation is exact).
Definition 8.2 Generalized policy iteration (GPI)
Any framework alternating «approximate evaluation + improvement». Value iteration, policy iteration, actor-critic, and Q-learning are all members of GPI; they differ only in how accurately each phase is carried out.
Why define it this wayGPI is the framework diagram connecting classical DP to modern RL. When judging a new algorithm, the first question is: how accurate is its evaluation? Is its improvement step faithful?
Theorems and proofs
Theorem 8.1 The policy improvement theorem (full proof)
If for all s: Σs' p(s'|s,π'(s))[r+γV^π(s')] ≥ V^π(s), then Vπ' ≥ V^π (state by state), and it is strictly better wherever there is a strict inequality.
Proof
Denote by Tπ'V^π the «one-step backup operator» of the improved policy applied to V^π; the premise is Tπ'V^π ≥ V^π (pointwise).
Key identity: Tπ' is a γ-contraction and Vπ' is its fixed point (the Bellman equation for a fixed policy, a special case of T5's Theorem 5.2).
Here Pπ' is the policy's transition matrix. Substitute repeatedly and expand k times:
Let k→∞: the first term → 0 (γ^k crushes it). Each term of the second: P^j preserves nonnegativity (stochastic matrix), γ^j ≥ 0, and (Tπ'V^π − V^π) ≥ 0 is the premise. So the sum ≥ 0, i.e. Vπ' ≥ V^π. If some state's backup is strictly larger and that state can reach the goal states (irreducibility), the strict inequality propagates. ∎
NoteProof structure: split «fixed point − current point = contraction term + improvement term», then make the contraction term vanish. The same muscle as T5's proof. Note that it holds for expected values — the sample version where «improvement can temporarily get worse» is one source of the off-policy high variance in /fund/.
Theorem 8.2 Comparing convergence speeds
Value iteration's error decays geometrically like γ^k (T5); policy iteration's number of rounds ≤ |A||S| (a combinatorial upper bound from non-repeating policies), and in practice exact convergence usually occurs within 3~10 rounds.
Proof
Round-count bound: by Theorem 8.1 the value strictly rises each round ⇒ the policy sequence has no repeats ⇒ at most |A||S| rounds (finitely many policies). ∎
NoteThis bound is extremely loose (combinatorial explosion), but it establishes the qualitative difference: policy iteration's convergence does not rely on γ's leniency as it approaches 1; it is «finite-step in the combinatorial sense». With large state spaces, evaluation becomes unsolvable (O(|S|³)) and you fall back to value iteration or function approximation — this trade-off has no free lunch.
Work it by hand
Still use T7's two-state MDP (γ=0.9). Run policy iteration from the poor policy π₀ = «choose a in state 0 (stay put)» and count the rounds; then compare how many steps value iteration needs for the same accuracy.
- Round 1 evaluation of π₀ (choose a in state 0): V(s0) = 0+0.9V(s0) → V(s0)=0; V(s1)=10. So V^π₀ = (0, 10).
- Round 1 improvement: at s0 compare a: 0+0.9×0 = 0 vs b: 0.5+0.9×10 = 9.5 → switch to b. s1 unchanged. π₁ = (b, stay).
- Round 2 evaluation of π₁: V(s1)=10, V(s0)=0.5+0.9×10=9.5. So V^π₁ = (9.5, 10). Round 2 improvement: at s0, a: 0+0.9×9.5=8.55 < b: 9.5, no change → converged.
- [object Object]
Policy iteration: 2 rounds vs value iteration: 176 steps. The per-step costs are reversed (solving equations O(|S|³) vs one backup O(|S|²|A|)), so the conclusion holds only for small state spaces. This «rounds vs steps» ledger replays in function approximation: a few critic updates per actor update in actor-critic is fundamentally the same trade-off.
Run the numbers
Where the numbers come from
Measured on the two-state MDP (γ=0.9):
- Value iteration to error 1e−8: 176 steps
- Policy iteration (starting from the poor policy a): converged in 2 rounds, V = [9.5000, 10.0000]
- Improvement monotonicity measured: V^b(s0)=9.5000 > V^a(s0)=0.0000 — strictly rising every round
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| Policy evaluation | The critic's update (approximate evaluation) | used in → |
| Policy improvement | The actor's update (approximate improvement) | used in → |
| Improvement theorem premises | PPO limits the KL per update — keeping the improvement theorem from failing in its sample version | used in → |
| Evaluation-accuracy trade-off | The direct provenance of «update the critic a few steps before touching the actor» | used in → |
Boundaries: where this article stops
Where this lesson stops: asynchronous DP, convergence conditions for infinite state spaces, and the error-accumulation theory of approximate policy iteration (propagation bounds for |V−V*|) — none covered. A first-order result for the approximate version can be given: with evaluation error ε, the improved policy's performance loss is ≤ 2γε/(1−γ)² — this formula reappears in another guise in /fund/approx/.
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01What is the role of the «splitting» step in the proof of the policy improvement theorem?
It splits Vπ'−V^π into a «contraction term (the γ^k P^k term, vanishing on its own)» plus an «improvement term (nonnegative, from the one-step comparison)». This move reduces a «global comparison» to a «local one-step comparison» — the universal pattern of all fixed-point convergence proofs.
02Why doesn't policy iteration's round count depend on γ?
The convergence argument is combinatorial: values strictly rise + policies are finite ⇒ no repeats ⇒ finitely many rounds. Nothing to do with geometric decay. γ affects how hard each round's «evaluation» is (the linear system becomes ill-conditioned as γ→1), not the round count.
03Value iteration: 176 steps vs policy iteration: 2 rounds — can we say policy iteration is always faster?
No. Each round's evaluation solves an |S|-unknown linear system (O(|S|³)), infeasible once states multiply; and with approximate evaluation the round advantage shrinks. The correct reading: small state spaces use PI, large ones use VI/function approximation — do the accounting, don't memorize conclusions.
04Which concept in this lesson corresponds to «update the critic a few more steps before touching the actor» in actor-critic?
Policy evaluation precedes policy improvement (GPI's two phases). When evaluation is too crude, the actor «improves» on a noisy value function, the improvement theorem's premises fail, and things can get worse — which is why unstable training often calls for raising the critic's learning rate or lowering the actor's (T10's two time scales).