Week 3

Chapter 3: Dynamic Programming

Solve known MDPs by planning: iterative policy evaluation, policy improvement and the policy improvement theorem, policy iteration, value iteration, and the generalized policy iteration pattern that underlies every later algorithm.

Chapter Overview

Dynamic programming (DP) answers the question Chapter 2 set up: given the transition dynamics, how do we actually compute the optimal policy? The answer is to turn the Bellman equations into assignment statements and apply them repeatedly until the values stop changing. Because the Bellman operators are contractions, this is guaranteed to converge.

DP has a strong assumption — you need a complete model of the environment — and a fatal weakness: it sweeps over every state, so it is unusable when the state space is large. It is nonetheless the most important chapter in the course. Every model-free method that follows is best understood as a way of approximating a DP update using sampled experience instead of a known model, and the alternation between evaluation and improvement introduced here is the skeleton of Q-learning, actor-critic and PPO alike.

Chapter Roadmap

Click any topic to jump in

Policy Evaluation

Repeatedly apply the Bellman expectation update to compute how good a fixed policy is.

Iterative Policy EvaluationWhen to Stop

Evaluation and improvement compose

Policy Improvement

Acting greedily with respect to a policy's own value function is guaranteed never to make it worse.

The Policy Improvement TheoremWhen Improvement Stops

Both are special cases of one idea

Full evaluation or a single sweep are just two points on a spectrum.

Policy Iteration

Alternate full evaluation and greedy improvement until the policy stops changing — converges in surprisingly few iterations.

The Algorithm and Its CostModified (Truncated) Policy Iteration

Value Iteration

Collapse evaluation to a single sweep by folding the max directly into the update.

The Optimality UpdateAsynchronous Variants

The pattern outlives the assumptions

Generalized Policy Iteration

The unifying pattern: any interleaving of partial evaluation and partial improvement converges to the optimum.

Competing and Cooperating ProcessesWhy This Pattern Survives Without a Model

Policy evaluation, also called the prediction problem, computes $v_\pi$ for a given policy. Chapter 2 showed this is a linear system solvable by matrix inversion, but at cubic cost in the number of states, which rules it out for anything real. The practical alternative is to treat the Bellman expectation equation as an assignment rather than an identity: initialize the values arbitrarily, apply the equation to every state, and repeat. The sequence converges to $v_\pi$ from any starting point, and it does so geometrically. The reason it works is worth stating precisely, because the same argument underwrites every algorithm in this chapter. The Bellman expectation operator is a contraction in the max norm: applying it to any two value functions brings them closer together by at least a factor $\gamma$ . Since $v_\pi$ is a fixed point of that operator, repeated application drives any initial guess toward it, with the error shrinking by $\gamma$ per sweep and the number of sweeps needed for a given accuracy scaling like $1/(1-\gamma)$ .

Definition

Policy evaluation is the problem of computing the value function $v_\pi$ for a fixed policy. Solved iteratively, it repeatedly applies the Bellman expectation equation as an update rule until the values stop changing, converging geometrically from any initialization because the operator is a contraction.

In this topic

1Iterative Policy Evaluation

2When to Stop

1 of 2

Iterative Policy Evaluation

$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]$

Each sweep replaces the value of every state with the one-step lookahead computed from the previous sweep's values. Successive approximation works because the Bellman expectation operator is a $\gamma$ -contraction in the max norm: every application shrinks the distance to the true $v_\pi$ by at least a factor $\gamma$ . Convergence is therefore geometric with a rate set entirely by the discount factor, and it is guaranteed regardless of initialization — a useful practical property, since it means a warm start from a previous policy's values is always safe and usually much faster than starting from zero.

Mathematical Intuition

The contraction property is $\lVert T_\pi v - T_\pi u \rVert_\infty \le \gamma \lVert v - u \rVert_\infty$ . Applying it $k$ times gives error $\gamma^k$ times the initial error, so the number of sweeps needed for a fixed accuracy grows like $1/(1-\gamma)$ .

Example:

Should the sweep use the previous iteration's values throughout (synchronous), or the freshest values available (in-place)?

2 of 2

When to Stop

In theory convergence takes infinitely many sweeps; in practice you stop when the largest value change across a sweep falls below a threshold. The genuinely useful insight is that you rarely need accurate values at all — you need values accurate enough that the greedy policy derived from them is correct. Because the greedy step depends only on the ordering of action values rather than their magnitudes, that policy typically stabilizes long before the numbers do. The gap between good enough to act on and numerically converged is the single most exploited fact in dynamic programming, and value iteration is built directly on it.

Example:

In the 4x4 gridworld from Sutton & Barto, how many sweeps does the greedy policy need to become optimal, versus how many the values need to converge?

Blogs

Sutton & Barto — Chapter 4: Dynamic Programming

Chapter 3: Dynamic Programming

Chapter Overview

Chapter Roadmap

Policy Evaluation

Policy Improvement

Policy Iteration

Value Iteration

Generalized Policy Iteration

Policy Evaluation

Definition

In this topic

Iterative Policy Evaluation

When to Stop

Related Problems on PixelBank

Policy Improvement

Policy Iteration

Value Iteration

Generalized Policy Iteration