Chapter 4 · Book pp. 73–90

Dynamic Programming

Algorithms that compute optimal policies given a perfect model of the MDP. Of limited direct use (perfect model, heavy computation) but the theoretical foundation for everything after: every later method tries to achieve the same effect as DP with less computation and no model.

Policy evaluation Policy improvement theorem Policy iteration Value iteration Asynchronous DP GPI Bootstrapping

Exam focus for this chapter

DP = Bellman equations turned into update rules (assignments). Expected updates vs sample updates.
Iterative policy evaluation (4.5): in-place vs two-array, the stopping threshold θ.
Policy improvement theorem (4.7)–(4.8) and why greedy improvement can only fail to improve when already optimal.
Policy iteration vs value iteration — what each sweep does, pros/cons, convergence.
Asynchronous DP and generalized policy iteration (GPI).
Computational efficiency: polynomial in $n$ states and $k$ actions vs $k^n$ policies; the curse of dimensionality.
Bootstrapping — DP updates estimates from other estimates.

Assume a finite MDP with known dynamics $p(s',r\mid s,a)$. DP algorithms are obtained by turning the Bellman optimality equations into assignments:

$$v_*(s)=\max_a\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma v_*(s')\big] \qquad q_*(s,a)=\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma\max_{a'}q_*(s',a')\big]$$

Bellman optimality equations — DP's targets(4.1), (4.2)

4.1 Policy evaluation (prediction)

Policy evaluation (the prediction problem): compute $v_\pi$ for a given π. $v_\pi$ exists and is unique if $\gamma<1$ or termination is guaranteed from all states under π. With known dynamics, (4.4) is a system of $|\mathcal S|$ linear equations — solvable directly, but iterative methods suit us better:

$$v_{k+1}(s) \doteq \E_\pi[R_{t+1}+\gamma v_k(S_{t+1})\mid S_t=s] = \sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma v_k(s')\big]$$

Iterative policy evaluation update(4.5)

$v_0$ arbitrary (terminal state = 0). $v_\pi$ is a fixed point; $\{v_k\}\to v_\pi$ as $k\to\infty$ under the same conditions that guarantee existence of $v_\pi$.
This is an expected update: it uses an expectation over all possible next states (vs. a sample next state in MC/TD).
Two-array (Jacobi, synchronous) version keeps old $v_k$ and new $v_{k+1}$. In-place (Gauss–Seidel) overwrites immediately — also converges, usually faster (uses new data as soon as available); the sweep order then matters. DP usually means in-place.

Iterative Policy Evaluation, for estimating V ≈ vπneeds modelbootstrapsexpected update

Input π, the policy to be evaluated
Algorithm parameter: a small threshold θ > 0 determining accuracy of estimation
Initialize V(s) arbitrarily, for s ∈ S, and V(terminal) to 0
Loop:
    Δ ← 0
    Loop for each s ∈ S:
        v ← V(s)
        V(s) ← Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [r + γ V(s')]
        Δ ← max(Δ, |v − V(s)|)
until Δ < θ

Converges only in the limit; stopped when the largest change in a sweep falls below θ. Smaller θ → more accurate, more sweeps.

Example 4.1 — the 4×4 gridworld

Non-terminal states 1–14; the two shaded corners are one terminal state. Actions up/down/left/right move deterministically (off-grid = stay). Reward −1 on every transition, undiscounted, episodic. Under the equiprobable random policy, $v_\pi(s)$ = −(expected number of steps to termination).

Try it: Figure 4.1 — iterative policy evaluation and greedy policies

Sweep k 0 Update style

v_k for the random policy

greedy policy w.r.t. v_k

What Figure 4.1 teaches

The greedy policy w.r.t. $v_k$ is already optimal from k = 3, long before $v_k$ converges. Evaluation beyond that point does not change the greedy policy — motivation for truncating policy evaluation (value iteration, §4.4).

4.2 Policy improvement

Given $v_\pi$, is it better to pick $a\ne\pi(s)$ in $s$ and follow π thereafter?

$$q_\pi(s,a)\doteq\E[R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s,A_t=a] = \sum_{s',r}p(s',r\mid s,a)\big[r+\gamma v_\pi(s')\big]$$

Value of deviating once(4.6)

Policy improvement theorem

For deterministic policies π, π′: if $\;q_\pi(s,\pi'(s))\ge v_\pi(s)\;$ for all $s\in\mathcal S$ (4.7), then $\;v_{\pi'}(s)\ge v_\pi(s)\;$ for all $s$ (4.8). Strict inequality in (4.7) at any state ⇒ strict inequality in (4.8) at that state.

Proof idea: keep expanding $q_\pi$ with (4.6) and reapplying (4.7):

$$\begin{aligned} v_\pi(s) &\le q_\pi(s,\pi'(s)) = \E_{\pi'}[R_{t+1}+\gamma v_\pi(S_{t+1})\mid S_t=s]\\ &\le \E_{\pi'}[R_{t+1}+\gamma q_\pi(S_{t+1},\pi'(S_{t+1}))\mid S_t=s] = \E_{\pi'}[R_{t+1}+\gamma R_{t+2}+\gamma^2 v_\pi(S_{t+2})\mid S_t=s]\\ &\le \dots \le \E_{\pi'}[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\dots\mid S_t=s] = v_{\pi'}(s) \end{aligned}$$

Proof of the policy improvement theorem§4.2

Applying this at every state gives the greedy policy:

$$\pi'(s)\doteq\argmax_a q_\pi(s,a) = \argmax_a\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma v_\pi(s')\big]$$

Policy improvement (greedification)(4.9)

By construction π′ satisfies (4.7), so it is as good as or better than π.
If π′ is no better ($v_{\pi'}=v_\pi$), then $v_{\pi'}(s)=\max_a\sum p[r+\gamma v_{\pi'}(s')]$ — the Bellman optimality equation — so both are optimal. Policy improvement gives a strictly better policy unless the original is already optimal.
Extends to stochastic policies; with ties, any split of probability among maximising actions is allowed, as long as sub-maximal actions get 0.

4.3 Policy iteration

$$\pi_0\xrightarrow{E}v_{\pi_0}\xrightarrow{I}\pi_1\xrightarrow{E}v_{\pi_1}\xrightarrow{I}\pi_2\xrightarrow{E}\cdots\xrightarrow{I}\pi_*\xrightarrow{E}v_*$$

Policy iteration: alternate Evaluation and Improvement§4.3

Each policy is a strict improvement (unless optimal). A finite MDP has finitely many deterministic policies ⇒ convergence to $\pi_*$ and $v_*$ in a finite number of iterations. Starting each evaluation from the previous $V$ greatly speeds things up.

Policy Iteration (using iterative policy evaluation) for estimating π ≈ π*needs modelbootstraps

1. Initialization
   V(s) ∈ ℝ and π(s) ∈ A(s) arbitrarily for all s ∈ S;  V(terminal) ≐ 0

2. Policy Evaluation
   Loop:
       Δ ← 0
       Loop for each s ∈ S:
           v ← V(s)
           V(s) ← Σ_{s',r} p(s',r|s,π(s)) [r + γ V(s')]
           Δ ← max(Δ, |v − V(s)|)
   until Δ < θ   (a small positive number determining the accuracy of estimation)

3. Policy Improvement
   policy-stable ← true
   For each s ∈ S:
       old-action ← π(s)
       π(s) ← argmax_a Σ_{s',r} p(s',r|s,a) [r + γ V(s')]
       If old-action ≠ π(s), then policy-stable ← false
   If policy-stable, then stop and return V ≈ v* and π ≈ π*; else go to 2

Exercise 4.4 — the bug: if several actions tie, π may keep switching between equally good policies and never become "stable". Fix: only change π(s) if the old action is not among the maximising actions (or break ties in a fixed order), or stop when V stops changing.

Example 4.2 — Jack's car rental

Two locations, ≤ 20 cars each; rent = +$\$10$; moving a car overnight = −$\$2$ (≤ 5 cars). Requests and returns are Poisson ($\lambda$ = 3, 4 requests; 3, 2 returns). γ = 0.9, continuing. State = cars at each location at day's end; action = net cars moved (−5…+5). Policy iteration from "never move" finds the optimal policy in 4 improvements ($\pi_0\to\pi_4$). Moral: policy iteration often converges in surprisingly few iterations. (Exercise 4.7 adds a free shuttle and a parking cost — nonlinearities DP handles easily but other optimisers do not.)

4.4 Value iteration

Policy evaluation inside policy iteration may need many sweeps. It can be truncated without losing convergence. Stopping after one sweep gives value iteration:

$$v_{k+1}(s)\doteq\max_a\E[R_{t+1}+\gamma v_k(S_{t+1})\mid S_t=s,A_t=a]=\max_a\sum_{s',r}p(s',r\mid s,a)\big[r+\gamma v_k(s')\big]$$

Value iteration update(4.10)

= the Bellman optimality equation turned into an update rule; identical to (4.5) except for the max.
For arbitrary $v_0$, $v_k\to v_*$ under the conditions that guarantee $v_*$ exists.
Each sweep combines one sweep of evaluation and one of improvement. Truncated policy iteration = sequences of sweeps, some with max (VI) and some without (PE). All converge for discounted finite MDPs.

Value Iteration, for estimating π ≈ π*needs modelbootstraps

Algorithm parameter: a small threshold θ > 0 determining accuracy of estimation
Initialize V(s), for all s ∈ S⁺, arbitrarily except that V(terminal) = 0
Loop:
    Δ ← 0
    Loop for each s ∈ S:
        v ← V(s)
        V(s) ← max_a Σ_{s',r} p(s',r|s,a) [r + γ V(s')]
        Δ ← max(Δ, |v − V(s)|)
until Δ < θ
Output a deterministic policy, π ≈ π*, such that
    π(s) = argmax_a Σ_{s',r} p(s',r|s,a) [r + γ V(s')]

$$q_{k+1}(s,a) = \sum_{s',r}p(s',r\mid s,a)\Big[r+\gamma\max_{a'}q_k(s',a')\Big]$$

Value iteration for action valuesEx 4.10

Policy iteration vs value iteration

	Policy iteration	Value iteration
Each iteration	Full policy evaluation (many sweeps) + one improvement	One sweep with a max = truncated evaluation + improvement
Update used	Bellman expectation (4.5) for current π	Bellman optimality (4.10)
Explicit policy during run?	Yes	No — extracted at the end
Number of iterations	Few (finite: policies strictly improve)	Many cheap sweeps; converges in the limit
Cost per iteration	High	Low ($O(\|\mathcal S\|^2\|\mathcal A\|)$ per sweep)
Which is better?	Neither in general; both widely used. Interposing several PE sweeps between improvements (modified/truncated PI) is often fastest.

Example 4.3 — the gambler's problem

Capital $s\in\{1,\dots,99\}$; stake $a\in\{0,\dots,\min(s,100-s)\}$. Heads (prob. $p_h$) wins the stake, tails loses it. Reward +1 only on reaching $\$100$; undiscounted, episodic. So $v_*(s)$ = probability of winning from $s$, and the optimal policy maximises that probability.

Try it: value iteration on the gambler's problem (Figure 4.3, Exercise 4.9)

p_h (probability of heads) 0.40 θ

Value estimates after successive sweeps

Final policy (stake)

Many policies are optimal (ties in the argmax). This plot breaks ties toward the smallest stake; the book's Figure 4.3 shows another member of the same optimal family.

Exercise 4.8 — why such a curious policy?

With $p_h<0.5$ every bet has negative expected value, so the gambler wants to reach $\$100$ in as few flips as possible ("bold play"). At $\$50$, one all-in bet wins with probability $p_h$ directly. At $\$51$, betting $\$1$ keeps a chance to reach a better position (e.g. $\$52$, or back to $\$50$ where the all-in option still exists) — so betting all $\$49$ needed would waste the extra dollar. The spikes at 25, 50, 75 reflect positions from which one or two bold bets reach the goal. Many optimal policies exist (ties). With $p_h>0.5$ the game is favourable and small "timid" bets become optimal. As θ → 0 the value function is stable, but the plotted policy may flicker among tied actions due to floating-point ties.

4.5 Asynchronous dynamic programming

Major drawback of the methods above: they sweep the entire state set. Backgammon (10²⁰ states) at a million updates/s would take over a thousand years per sweep.
Asynchronous DP: in-place updates in any order, using whatever values are available; some states updated many times before others once.
To converge, it must keep updating all states (cannot ignore any after some point). E.g. asynchronous VI updating one state $s_k$ per step converges (for $0\le\gamma<1$) if every state appears in $\{s_k\}$ infinitely often.
Doesn't necessarily reduce total computation, but avoids being locked into long sweeps; lets us order updates to propagate value efficiently and skip irrelevant states.
Easy to intermix with real-time interaction: update the states the agent actually visits — focusing computation on relevant parts of the state space (a recurring RL theme).

4.6 Generalized policy iteration (GPI)

GPI: evaluation drives V toward $v_\pi$; improvement makes π greedy w.r.t. V. They compete (each change invalidates the other) yet cooperate to reach the single joint solution $v_*,\pi_*$.

GPI = letting policy-evaluation and policy-improvement processes interact, independent of their granularity. Policy iteration (each process runs to completion), value iteration (one evaluation sweep), asynchronous DP (single-state interleaving) are all GPI — and so are almost all RL methods. If both processes stabilise, the policy is greedy w.r.t. its own value function ⇒ Bellman optimality holds ⇒ both are optimal.

4.7 Efficiency of dynamic programming

Worst-case time to find an optimal policy is polynomial in $n$ (states) and $k$ (actions), although there are $k^n$ deterministic policies — exponentially faster than direct policy search.
Linear programming can also solve MDPs (sometimes better worst-case guarantees) but becomes impractical at ~100× fewer states. For the largest problems only DP is feasible.
The curse of dimensionality (states grow exponentially with state variables) is a property of the problem, not of DP; DP handles large spaces better than direct search or LP. Millions of states are solvable today.
In practice both PI and VI converge much faster than worst case, especially from good initial values or policies. For very large problems, asynchronous methods are preferred.

4.8 Summary — and the key idea of bootstrapping

Bootstrapping

All DP methods update estimates of state values based on estimates of successor-state values — "updating estimates on the basis of other estimates". Chapter 5 (Monte Carlo) needs no model and does not bootstrap; Chapter 6 (TD) needs no model but does bootstrap. These properties are separable and can be mixed.

Value function	Bellman equation	Corresponding DP expected update
$v_\pi$	$v_\pi(s)=\sum_a\pi(a\|s)\sum_{s',r}p\,[r+\gamma v_\pi(s')]$	Iterative policy evaluation
$v_*$	$v_(s)=\max_a\sum_{s',r}p\,[r+\gamma v_(s')]$	Value iteration
$q_\pi$	$q_\pi(s,a)=\sum_{s',r}p\,[r+\gamma\sum_{a'}\pi(a'\|s')q_\pi(s',a')]$	Q-policy evaluation
$q_*$	$q_(s,a)=\sum_{s',r}p\,[r+\gamma\max_{a'}q_(s',a')]$	Q-value iteration

Parameters in this chapter

Parameter	Role	Effect
θ (threshold)	Stop evaluation / VI when the max change in a sweep is below θ	Smaller θ → more accurate, more sweeps. A loose θ in PI is fine because improvement only needs the greedy policy to be right (Fig 4.1: k = 3 already suffices).
γ	Problem's discount	Smaller γ → faster convergence (contraction factor γ); γ = 1 requires guaranteed termination.
Number of evaluation sweeps per improvement	1 = VI, ∞ = PI, in between = truncated / modified PI	Trade-off between cost per iteration and number of iterations.
Sweep order (in-place)	Order in which states are updated	Strongly affects convergence speed (e.g. backward from goal propagates fastest).
Initial V / π	Starting point	Good starts converge much faster; terminal must be 0.

Self-test

Ex 4.1 — In Example 4.1 (random policy), what is $q_\pi(11,\text{down})$? $q_\pi(7,\text{down})$?

$q_\pi(11,\text{down}) = -1 + v_\pi(\text{terminal}) = \mathbf{-1}$. $q_\pi(7,\text{down}) = -1 + v_\pi(11) = -1 + (-14) = \mathbf{-15}$.

Ex 4.2 — Add state 15 below 13 (left→12, up→13, right→14, down→15). What is $v_\pi(15)$? What if 13's "down" now leads to 15?

$v(15) = -1 + \tfrac14[v(12)+v(13)+v(14)+v(15)] = -1+\tfrac14[-22-20-14+v(15)]$ ⇒ $\tfrac34v(15)=-15$ ⇒ $v(15)=\mathbf{-20}$. If 13's down goes to 15: since $v(15)=-20=v(13)$, state 13's equation is unchanged (down used to keep it at 13 with value −20), so all values stay the same: $v(15)=-20$.

Ex 4.3 — Equations analogous to (4.3)–(4.5) for action values.

$q_\pi(s,a)=\E_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]=\sum_{s',r}p(s',r|s,a)[r+\gamma\sum_{a'}\pi(a'|s')q_\pi(s',a')]$; update: $q_{k+1}(s,a)=\sum_{s',r}p(s',r|s,a)[r+\gamma\sum_{a'}\pi(a'|s')q_k(s',a')]$.

Ex 4.5 — Policy iteration for action values (computing $q_*$).

Init $Q(s,a)$, π arbitrarily. Evaluation: repeat $Q(s,a)\leftarrow\sum_{s',r}p(s',r|s,a)[r+\gamma Q(s',\pi(s'))]$ for all $(s,a)$ until Δ < θ. Improvement: $\pi(s)\leftarrow\argmax_aQ(s,a)$; if unchanged for all $s$, stop. Note improvement needs no model once Q is known — this is why later model-free control methods learn Q.

Ex 4.6 — If restricted to ε-soft policies, what changes in steps 3, 2, 1 of policy iteration?

Step 3: improvement makes π ε-greedy: each action gets $\varepsilon/|\mathcal A(s)|$, the greedy action gets the rest $1-\varepsilon+\varepsilon/|\mathcal A(s)|$. Step 2: evaluation must use the stochastic policy: $V(s)\leftarrow\sum_a\pi(a|s)\sum p[r+\gamma V(s')]$. Step 1: initialise π to any ε-soft policy. (The result is the best ε-soft policy, cf. §5.4.)

Why does the in-place version of policy evaluation usually converge faster than the two-array version?

It uses newly computed values immediately within the same sweep, so information propagates further per sweep. The order of updates then matters.

State the policy improvement theorem and explain why policy iteration terminates.

If $q_\pi(s,\pi'(s))\ge v_\pi(s)\ \forall s$, then $v_{\pi'}\ge v_\pi$. Greedy improvement satisfies this; each new policy is strictly better unless optimal; finitely many deterministic policies ⇒ finite termination.

What exactly is the difference between the policy-evaluation update and the value-iteration update?

PE averages over actions with π(a|s); VI takes the max over actions. Everything else is identical.

What two conditions must asynchronous DP satisfy to converge?

Updates may be in any order, but every state must continue to be updated (infinitely often in the limit); for single-state async VI, $0\le\gamma<1$ (undiscounted episodic needs care with ordering).

Define GPI and explain "competing and cooperating".

GPI: any interleaving of evaluation (V → $v_\pi$) and improvement (π → greedy(V)). They compete: improving π makes V wrong for the new π; evaluating makes π no longer greedy. They cooperate: jointly they converge to the unique fixed point where π is greedy w.r.t. its own value — optimal.

Why is DP said to be exponentially faster than direct policy search?

DP is polynomial in $n$ and $k$; direct search must examine up to $k^n$ policies for the same guarantee.

What two properties of DP do MC and TD methods each drop?

DP needs a model and bootstraps. MC needs no model and does not bootstrap. TD needs no model but bootstraps.

Chapter quiz — check your understanding

Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.