RobotGuide
Math foundations/Dynamic Programming: The Accounting for Two Iterations

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.

≈ 50 min2 theorems7 proof steps4 self-test questions

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).

Vπ' − V^π = (Vπ' − Tπ'V^π) + (Tπ'V^π − V^π) = γ Pπ'(Vπ' − V^π) + (Tπ'V^π − V^π)

Here Pπ' is the policy's transition matrix. Substitute repeatedly and expand k times:

Vπ' − V^π = γ^k Pπ'^k (Vπ'−V^π) + Σj=0k−1 γ^j Pπ'^j (Tπ'V^π − V^π)

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.

  1. 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).
  2. 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).
  3. 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.
  4. [object Object]
Answer

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 hereThe counterpart in RLUsed in
Policy evaluationThe critic's update (approximate evaluation)used in →
Policy improvementThe actor's update (approximate improvement)used in →
Improvement theorem premisesPPO limits the KL per update — keeping the improvement theorem from failing in its sample versionused in →
Evaluation-accuracy trade-offThe 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).

Up next

The full series · 27 articles

T1The Matrix Is a Ledger for Rotation≈ 25 minT2From Slope to Gradient: The First Line of Every Robot Learning Algorithm≈ 25 minT3Vectors and forces: the physical reading of the dot productAbout 20 minT4Two Rulers and a Better Rulerabout 25 minT5The Ledger of One Motor Revolution: Radians, Speed, and Powerabout 20 minT6Complex multiplication is rotation: the one-dimensional version of quaternionsAbout 20 minT7Bases and coordinates: why robots put everything in matrices45 minT8Matrix Multiplication: Chaining Transformations, Not a Table OperationAbout 40 minT9The Jacobian: Rotate a Joint One Degree — How Far Does the End Effector Move?About 45 minT10Eigenvectors: The Directions a Matrix Dare Not Touchabout 45 minT11SVD and the Pseudoinverse: When There Is No Exact Solution, Find the Nearest Oneabout 50 minT12Taylor expansion: putting a straight line to work in place of a curveAbout 40 minT13Probability spaces: why «random» needs axioms50 minT14Expectation: A Rigorous Construction of «Average»About 55 minT15Conditional Expectation: What the Vertical Bar Really Means≈ 60 minT16Four inequalities: the quantitative answer to «how many samples are enough»45 minT17Norms and fixed points: where «it always converges» comes from55 minT18Markov Chains: When the Time Average Equals the Ensemble Averageabout 55 minT19The Mathematical Construction of the MDP: What One Axiom Is Worthabout 50 minT20Dynamic Programming: The Accounting for Two Iterations≈ 50 minT21Optimization: why constraints cannot rely on penalties aloneAbout 55 minT22Stochastic Approximation: Every Term in the Learning-Rate Formulaabout 55 minT23The Mathematics of Contact: Hertz Theoryabout 45 minT24Friction and the Friction Cone: The Geometry of Constraintsabout 40 minT25Force Closure and Grasp Metrics: ε Is a Linear ProgramAbout 50 minT26Contact Kinematics: Why Rolling Is Not «Sliding Along»≈ 45 minT27Slip detection: from «I felt it» to «I computed it»About 50 min