Pearl
Lab

Chapter 03 · Foundations

Dynamic Programming

Abstract. Dynamic Programming (DP) turns Bellman equations into algorithms under a strong assumption: the model \(P\) and \(R\) are known exactly, and the state space is small enough to sweep. Policy Iteration alternates exact (or approximate) evaluation of \(V^{\pi}\) with greedy improvement. Value Iteration repeatedly applies the Bellman optimality operator and reads the policy off only at the end. Both converge to \(\pi^*\) for finite discounted MDPs. This chapter states the updates, sketches why improvement never hurts, compares the two algorithms, and runs them live on a grid. The same backup structure reappears in TD — only the source of the next-state expectation changes from “sum over \(P\)” to “sample \(s'\).”

1. Overview

Chapters 01–02 gave you the MDP and the Bellman equations. Dynamic Programming is what you do when you are allowed to compute those equations instead of estimating them.

“Dynamic programming” here is Bellman’s classical sense: break a sequential decision problem into recursive subproblems whose solutions compose. In RL textbooks the phrase almost always means tabular planning with a known model — Policy Evaluation, Policy Iteration, Value Iteration, and their asynchronous cousins.

Keep one slogan in mind for the rest of the course:

Slogan

TD / Q-learning = DP with the expectation over \(P\) replaced by a sample. If you understand the backups in this chapter, every later “learning” update is a stochastic approximation of the same operator.

2. Planning, not learning

DP assumes:

  1. You can evaluate \(P(s'\mid s,a)\) and \(R(s,a,s')\) for every triple you need.
  2. You can iterate over all \(s \in S\) (and often all \(a \in A\)) in memory.

No interaction with the environment is required — you never “explore.” You are solving a known Markov decision process as a computational problem. That is planning. Learning begins when \(P\) or \(R\) (or both) are unknown and must be inferred from experience.

Remark · Full backup vs sample backup

A full backup for a state uses the entire distribution \(P(\cdot\mid s,a)\) — every successor contributes. A sample backup uses one drawn \(s'\). DP uses full backups. Monte Carlo and TD use sample backups. The quadrant from your notes (full/sample × bootstrap/depth) places DP in the “full backup + one-step bootstrap” corner.

3. Iterative policy evaluation

Fix a policy \(\pi\). We want \(V^{\pi}\), the unique solution of the Bellman expectation equation (Chapter 02). Iterative policy evaluation applies the operator \(\mathcal{T}^{\pi}\) repeatedly:

(1) \[ V_{k+1}(s) \;\leftarrow\; \sum_{a}\pi(a\mid s) \sum_{s'}P(s'\mid s,a) \Big[ R(s,a,s') + \gamma V_{k}(s') \Big]. \]

Equivalently \(V_{k+1} = \mathcal{T}^{\pi} V_k\). Because \(\mathcal{T}^{\pi}\) is a \(\gamma\)-contraction in \(\|\cdot\|_\infty\), \(V_k \to V^{\pi}\) from any start, geometrically fast. In practice one stops when \(\|V_{k+1}-V_k\|_\infty < \theta\) for a small threshold \(\theta\).

For tiny MDPs one can also solve the linear system \(V = r^{\pi} + \gamma P^{\pi} V\) in closed form: \(V = (I - \gamma P^{\pi})^{-1} r^{\pi}\). Iteration is preferred pedagogically and scales better when \(|S|\) is large but still tabular.

Definition 3.1 · Sweep

A sweep is one pass that updates every state once (synchronously using a frozen copy of \(V_k\), or asynchronously in place). Synchronous sweeps match the pure operator view; asynchronous updates often converge faster in wall-clock time on large tables.

4. Policy improvement

Given \(V^{\pi}\) (or \(Q^{\pi}\)), define a new policy by acting greedily with respect to the one-step lookahead:

(2) \[ \pi'(s) \in \arg\max_{a} \sum_{s'}P(s'\mid s,a) \Big[ R(s,a,s') + \gamma V^{\pi}(s') \Big]. \]

In terms of action values this is simply \(\pi'(s) \in \arg\max_a Q^{\pi}(s,a)\).

Theorem 4.1 · Policy Improvement Theorem

Let \(\pi\) and \(\pi'\) be deterministic policies such that for all \(s\), \[ Q^{\pi}\big(s,\pi'(s)\big) \;\ge\; V^{\pi}(s). \] Then \(V^{\pi'}(s) \ge V^{\pi}(s)\) for all \(s\). If strict inequality holds at any state, \(\pi'\) is strictly better somewhere. In particular, the greedy policy with respect to \(Q^{\pi}\) is always at least as good as \(\pi\).

Proof sketch (why the escalator only goes up)

The inequality \(Q^{\pi}(s,\pi'(s)) \ge V^{\pi}(s)\) says that taking \(\pi'\)’s action once, then following \(\pi\), is already no worse than following \(\pi\) forever. Unrolling that one-step improvement repeatedly — \(\pi'\) then \(\pi'\) then \(\pi'\) … — produces an infinite-horizon return at least as large as \(V^{\pi}\). Formally one shows \(V^{\pi} \le \mathcal{T}^{\pi'} V^{\pi} \le (\mathcal{T}^{\pi'})^2 V^{\pi} \le \cdots \to V^{\pi'}\).

5. Policy Iteration

Policy Iteration (PI) alternates the two blocks until the policy stops changing:

(3) \[ \underbrace{\pi_0 \;\xrightarrow{\;\mathrm{eval}\;}\; V^{\pi_0} \;\xrightarrow{\;\mathrm{greedy}\;}\; \pi_1 \;\xrightarrow{\;\mathrm{eval}\;}\; V^{\pi_1} \;\xrightarrow{\;\mathrm{greedy}\;}\; \cdots}_{\text{Policy Iteration}} \]
  1. Policy Evaluation: compute \(V^{\pi_k}\) (iterate (1) to convergence, or solve the linear system).
  2. Policy Improvement: set \(\pi_{k+1}\) greedy w.r.t. \(V^{\pi_k}\) via (2).
  3. Stop when \(\pi_{k+1} = \pi_k\) (then \(\pi_k\) is optimal).

Because each improvement is monotonically nondecreasing in value and there are finitely many deterministic policies, PI reaches \(\pi^*\) in finitely many outer iterations. Each outer iteration may itself require many evaluation sweeps.

Remark · Truncated / modified policy iteration

Exact evaluation is unnecessary. Stopping evaluation after a few sweeps (truncated PI) still works in practice and interpolates toward Value Iteration, which can be seen as truncation to a single backup before improving.

6. Value Iteration

Value Iteration (VI) never maintains an explicit policy during the loop. It applies the Bellman optimality operator directly:

(4) \[ V_{k+1}(s) \;\leftarrow\; \max_{a} \sum_{s'}P(s'\mid s,a) \Big[ R(s,a,s') + \gamma V_{k}(s') \Big]. \]

That is \(V_{k+1} = \mathcal{T}^* V_k\). As \(\mathcal{T}^*\) is a \(\gamma\)-contraction, \(V_k \to V^*\). After convergence (or approximate convergence), extract

(5) \[ \pi^*(s) \in \arg\max_{a} \sum_{s'}P(s'\mid s,a) \Big[ R(s,a,s') + \gamma V^*(s') \Big]. \]

Intuition: each sweep is “one step of greedy lookahead using the current value guess.” You do not wait to finish evaluating a policy before re-greedifying — evaluation and improvement are fused.

Proposition 6.1 · Stopping rule

If \(\|V_{k+1} - V_k\|_\infty < \varepsilon(1-\gamma)/(2\gamma)\), then the greedy policy with respect to \(V_{k+1}\) is \(\varepsilon\)-optimal: \(\|V^{\pi} - V^*\|_\infty < \varepsilon\). (Constants vary slightly by reference; the point is that small Bellman residual ⇒ near-optimal greedy policy.)

7. Policy Iteration vs Value Iteration

PI
Few outer iterations; each needs thorough evaluation. Exact policy sequence with monotone improvement.
VI
Cheap sweeps; many of them. Policy is implicit until the end. Often faster wall-clock on large tables.
MPI
Modified/truncated PI sits between: \(m\) evaluation sweeps then improve. \(m=1\) ≈ VI-style; \(m\to\infty\) ≈ classical PI.

Both compute the same \(V^*\) / \(\pi^*\) in the limit. Choice is computational taste, not a different solution concept.

Analysis · Where “greedy” formally enters

Greedy improvement is equation (2)/(5): replace the average over \(\pi\) by \(\max_a\). That single change turns evaluation into control. Q-learning’s target \(r + \gamma \max_{a'} Q(s',a')\) is the sample version of the same max. The word “greedy” in RL almost always means this \(\arg\max\), not the \(\gamma\to 0\) sense of myopic discounting.

8. Asynchronous and in-place DP

Synchronous VI updates all states from a frozen copy of \(V_k\). Asynchronous DP updates states in any order, immediately overwriting \(V(s)\), possibly prioritizing states with large Bellman error (prioritized sweeping). Convergence still holds if every state is updated infinitely often and the usual contraction conditions apply.

These variants matter as conceptual bridges: experience replay with TD updates is morally “asynchronous sample-backed DP on visited states.”

9. Limits — and why TD is next

DP collapses outside toy tabular worlds for two independent reasons:

  1. Model. Real robotics gives you a simulator to sample, not a closed-form \(P(s'\mid s,a)\) for continuous \(s'\).
  2. Scale. Sweeping every state is impossible when \(S\) is continuous or astronomically large.

Temporal-Difference learning keeps the one-step bootstrapping backbone of (1) and (4) but replaces \(\sum_{s'}P(s'\mid s,a)\,f(s')\) with \(f(s')\) at a sampled successor. Exploration (\(\varepsilon\)-greedy, entropy bonuses, …) appears because, unlike DP, you only learn about states and actions you actually visit.

Bridge · Four corners (recap)

Exhaustive search: full model, full depth (game trees).
DP: full model, one-step bootstrap.
Monte Carlo: samples, full depth (episode returns).
TD: samples, one-step bootstrap — the scalable corner.

10. Laboratory · PI and VI on a grid

5×5 grid, rewards aligned with Chapter 01 (step \(-0.1\), goal \(+10\), pit \(-5\)), walls as before. Toggle slip to replace the deterministic backup with \(\sum_{s'}P(s'\mid s,a)[R+\gamma V(s')]\) — the full transition sum from the text. \(\gamma\) is adjustable. Watch \(V\) and the greedy arrows evolve.

Policy Iteration / Value Iteration

Known model · full backups
Discount

Rewards match Ch 01: step −0.1, goal +10, pit −5.

Policy Iteration
Value Iteration
Reset

Value table \(V(s)\) + greedy policy

Arrows = current policy (PI) or greedy w.r.t. \(V\) (always shown).

Modeidle
Outer / sweeps0
‖Δ‖∞—
π stable?n/a

Backup log

Run Evaluate / VI to apply Bellman backups with the known model.

11. Worked example · one improvement step

Suppose three actions from state \(s\), \(\gamma=0.9\), and the current \(V^{\pi}\) gives successor values \(V(s_1)=2\), \(V(s_2)=5\), \(V(s_3)=4\). Deterministic transitions, rewards \(R=0\) for all three. Lookahead scores:

(6) \[ \begin{aligned} a_1 &:\; 0 + 0.9\cdot 2 = 1.8,\\ a_2 &:\; 0 + 0.9\cdot 5 = 4.5,\\ a_3 &:\; 0 + 0.9\cdot 4 = 3.6. \end{aligned} \]

Greedy improvement sets \(\pi'(s)=a_2\). If the old \(\pi(s)\) was \(a_3\), the policy changed and Theorem 4.1 guarantees values cannot get worse. If every state already selected its maximizing action, PI has converged.

  1. Compute \(Q^{\pi}(s,a)=\sum_{s'}P(s'|s,a)[R+\gamma V^{\pi}(s')]\) for each \(a\).
  2. Here \(Q(s,a_1)=1.8\), \(Q(s,a_2)=4.5\), \(Q(s,a_3)=3.6\).
  3. Set \(\pi'(s)=\arg\max_a Q(s,a)=a_2\).
  4. Policy Improvement Theorem ⇒ \(V^{\pi'}(s)\ge V^{\pi}(s)\) ∀s.
  5. Re-evaluate \(V^{\pi'}\) with sweeps of equation (1).
  6. Repeat until \(\pi'=\pi\); then \(\pi=\pi^*\) for finite MDPs.

For a full pencil walkthrough — random \(\pi\) → evaluate → improve → Value Iteration — on a \(2\times 3\) grid with every intermediate number: Open the Practice notebook →

12. What follows

Temporal-Difference learning keeps bootstrapping (\(r + \gamma V(s')\)) but drops the requirement that you know \(P\). You will meet TD(0), SARSA (on-policy control), Q-learning (off-policy control), and the exploration problem DP never had to face.

See also

  • Sutton & Barto, Ch. 4 — DP chapter.
  • Chapter 02 — Bellman operators \(\mathcal{T}^{\pi}\), \(\mathcal{T}^*\).
  • Practice notebook — full PI / VI by hand on a \(2\times 3\) grid.
  • Chapter 01 — MDP model assumptions.

Previous

← Value & Bellman

Next chapter

Temporal-Difference Learning

TD(0), SARSA, Q-learning — DP from samples.

Continue →