5.Dynamic Programming: Planning with a Known Model

5.1 The blueprint changes everything

Overnight, Rusty receives the warehouse blueprint — the exact MDP from Chapter 4. The $12 \times 9$ grid, $p_{\text{slip}} = 0.2$, rewards of $+25$ at the dock, $-1$ per step, $-10$ per shelf bump, and $\gamma = 0.95$.

With $p$ and $r$ in hand, "what should Rusty do?" is no longer an experimental question. It is arithmetic. But which arithmetic?

The direct approach is to enumerate every deterministic policy, evaluate each, and keep the best. With roughly 80 states and four actions that is $4^{80} \approx 10^{48}$ policies. At a billion evaluations per second you would finish some $10^{30}$ times after the heat death of the universe.

Dynamic programming is the family of methods that exploits Bellman structure to replace that enumeration with iteration. The key insight is Bellman's own principle of optimality, quoted above: an optimal policy's tail must itself be optimal. That means we can build the answer up from local consistency conditions rather than searching the space of whole policies.

5.2 Iterative policy evaluation

Start with the easier problem: given a policy $\pi$, what is $v_\pi$?

Chapter 4 showed this is a linear system solvable by matrix inversion, at cost $O(|\mathcal{S}|^3)$. Iteration is cheaper. Turn the Bellman expectation equation into an assignment:

$v_{k+1}(s) \leftarrow \sum_a \pi(a\mid s) \sum_{s',r} p(s',r\mid s,a)\left[r + \gamma\, v_k(s')\right],$

which is exactly applying the operator $T_\pi$. Theorem 4.3 proved $T_\pi$ is a $\gamma$-contraction, so by Banach the sequence converges to the unique fixed point $v_\pi$ from any initialization — including all zeros.

When do we stop? Track $\Delta = \max_s |v_{k+1}(s) - v_k(s)|$ and halt when it falls below a threshold $\theta$. Banach's bound converts $\Delta$ into a guarantee: if the greedy policy with respect to $v_k$ is $\pi$, then

$\|v_\pi - v_*\|_\infty \le \frac{2\gamma\,\Delta}{1 - \gamma}.$

This is not decoration. It is the difference between "the numbers stopped changing much" and "my policy is provably within $\epsilon$ of optimal", and the dashboard below displays it live.

5.3 The policy improvement theorem

Now the result that makes everything work. Suppose we have $v_\pi$ and construct a new policy $\pi'$ that acts greedily with respect to it:

$\pi'(s) = \arg\max_a q_\pi(s,a) = \arg\max_a \sum_{s',r} p(s',r\mid s,a)\left[r + \gamma\, v_\pi(s')\right].$

Is $\pi'$ better? It is locally better by construction — but each state's improvement changes which states you visit, so the argument is not obvious. It is, however, true.

5.4 Policy iteration and value iteration

Policy iteration alternates the two operations to convergence:

$\pi_0 \xrightarrow{\text{evaluate}} v_{\pi_0} \xrightarrow{\text{improve}} \pi_1 \xrightarrow{\text{evaluate}} v_{\pi_1} \xrightarrow{\text{improve}} \cdots \to \pi_*$

Since each improvement strictly increases the value of at least one state unless the policy is already optimal, and there are finitely many deterministic policies, policy iteration terminates in finitely many iterations at an exactly optimal policy. In practice it converges in a handful — often fewer than ten, even on large problems.

The cost is that each evaluation runs to convergence, which is many sweeps of work to answer a question ("which action is best here?") that may not need that precision.

Value iteration takes the opposite extreme: truncate evaluation after a single sweep, folding the improvement into it by using a max instead of a policy average:

$v_{k+1}(s) \leftarrow \max_a \sum_{s',r} p(s',r\mid s,a)\left[r + \gamma\, v_k(s')\right].$

This is just repeated application of $T_*$, which Theorem 4.3 proved is a $\gamma$-contraction. It converges geometrically, though — unlike policy iteration — it approaches optimality asymptotically rather than hitting it exactly.

Watch what happens when you press play on value iteration. Value appears first at the dock, then bleeds outward one cell per sweep. That is not an artifact of the visualization: with $\gamma = 0.95$ and a one-step backup, information about the goal can travel exactly one cell per sweep. Cells far from the dock cannot know anything about it until the wave arrives.

Then switch to policy iteration and watch a different rhythm: long stretches of evaluation where the arrows barely move, punctuated by improvement steps where large regions of the policy flip at once.

use rl_core::Mdp;
 
pub struct Sweep {
    pub index: usize,
    pub values: Vec<f64>,
    pub delta: f64,
    /// Bellman-error bound on ‖v_π − v*‖∞ implied by this Δ.
    pub suboptimality: f64,
}
 
/// Value iteration with in-place (Gauss–Seidel) sweeps.
pub fn value_iteration<M: Mdp>(mdp: &M, theta: f64, max_sweeps: usize) -> Vec<Sweep> {
    let gamma = mdp.gamma();
    let mut v = vec![0.0; mdp.states().len()];
    let mut history = Vec::new();
 
    for index in 1..=max_sweeps {
        let mut delta: f64 = 0.0;
 
        for (i, state) in mdp.states().iter().enumerate() {
            if mdp.is_terminal(state) { continue; }
            let old = v[i];
 
            // max_a Σ p(s′,r|s,a)[r + γ v(s′)] — the Bellman optimality backup.
            v[i] = mdp
                .actions(state)
                .iter()
                .map(|&a| {
                    mdp.transitions(state, a)
                        .iter()
                        .map(|&(next, reward, prob)| prob * (reward + gamma * v[next]))
                        .sum::<f64>()
                })
                .fold(f64::NEG_INFINITY, f64::max);
 
            delta = delta.max((old - v[i]).abs());
        }
 
        history.push(Sweep {
            index,
            values: v.clone(),
            delta,
            suboptimality: 2.0 * gamma * delta / (1.0 - gamma),
        });
 
        if delta < theta { break; }
    }
    history
}

5.5 Generalized policy iteration

Step back and notice that policy iteration and value iteration are the same algorithm with a dial set differently.

Both maintain a value estimate and a policy. Both push the value toward consistency with the policy (evaluation) and push the policy toward greediness with respect to the value (improvement). They differ only in how much evaluation happens between improvements: everything, one sweep, or — in modified policy iteration — some number in between.

Generalized policy iteration (GPI) is the name for this pattern in the abstract: any interleaving of evaluation and improvement, at any granularity, in any order, including asynchronously and on subsets of states.

5.6 Asynchronous DP, and the wall

Nothing requires sweeping states in order, or sweeping all of them equally. Asynchronous DP updates states in any order, as long as every state is updated infinitely often in the limit. Convergence still holds.

This licenses genuinely useful strategies: back up states along a trajectory the robot actually visits, prioritize states whose values just changed a lot (Chapter 7's prioritized sweeping), or focus computation near the goal where it does most good.

But no ordering saves dynamic programming for a real robot. The problem is not the sweep order — it is that a sweep must touch every state, and the number of states is exponential in the robot's degrees of freedom.

Set the widget to 7 degrees of freedom with 10 bins per dimension — a deliberately crude discretization of a modest research arm — and read the time for a single sweep. No faster computer rescues this; the curve is exponential in the exponent.

This is the first of Kober's four curses, and Chapter 14 develops all four properly. Its consequence for us is immediate and structural: we must stop enumerating states and start generalizing across them. That is Part II.

5.7 What DP still buys you

Before leaving, it is worth being clear that dynamic programming is not merely a pedagogical stepping stone.

It remains the correct tool whenever the state space is genuinely small — inventory control, discrete task planning, the high-level layer of a hierarchical robot controller. It is the ground truth against which approximate methods are measured: every algorithm in Chapters 6 through 12 is trying to approximate what DP computes exactly. And its theory transfers wholesale: the contraction argument, the improvement theorem, and GPI survive into the approximate setting, sometimes weakened but always recognizable.

Chapter 12 will bring DP back in a new guise, planning against a learned model rather than a given one — Bellman backups over dynamics the robot discovered for itself.

5.8 Chapter bridge

We assumed the blueprint. Rusty does not have one.

Real robots are handed no transition probabilities. Friction is unmeasured, payloads change, and the only access to the dynamics is to act and observe what happens. Chapter 6 removes the model entirely and asks whether anything survives. The answer is that a great deal does — Monte Carlo methods learn from complete episodes, temporal-difference methods learn from single transitions by bootstrapping from their own estimates, and the GPI pattern from this chapter carries over intact with sampling in place of expectation.

References