Chapter 3: Dynamic Programming

Week 3

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.

Topics: 5
Videos: 5
Min read: 19

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

Explainer video

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

Topics

5 topics in this chapter

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.

Mathematical Intuition

If the current estimate is within $\delta$ of the true values everywhere, every one-step action value computed from it is within $\gamma\delta$ of the truth, because the estimate enters only through the term $\gamma\, v(s')$ . So whenever the best action at a state beats the runner-up by more than $2\gamma\delta$ , the greedy choice there is already correct. Orderings settle once $\delta$ drops below half the smallest action gap, which is usually long before $\delta$ itself is small.

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?

Papers

A Markovian Decision Process (Bellman, 1957)Distributed Dynamic Programming (Bertsekas, 1982)

Blogs

Sutton & Barto — Chapter 4: Dynamic Programming Dynamic Programming exercises and solutions — dennybritz/reinforcement-learning

Definition

Policy improvement constructs a new policy that acts greedily with respect to the current policy's value function. The policy improvement theorem guarantees the result is at least as good in every state, and strictly better somewhere unless the original policy was already optimal.

In this topic

1The Policy Improvement Theorem
2When Improvement Stops

1 of 2

The Policy Improvement Theorem

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

The theorem states that if $q_\pi(s, \pi'(s)) \ge v_\pi(s)$ for all states, then $v_{\pi'}(s) \ge v_\pi(s)$ for all states. The subtle part is that the premise only compares a single-step deviation while the conclusion is about following $\pi'$ forever. The proof unrolls the inequality repeatedly, replacing one step at a time, which is why a purely local improvement yields a global guarantee. This matters practically because it means greedy improvement can never make things worse — an unusual property in optimization, where a locally attractive step routinely degrades the global objective.

Mathematical Intuition

The proof is one inequality applied over and over: $v_\pi(s) \le q_\pi(s, \pi'(s)) = \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = \pi'(s)]$ . The $v_\pi(S_{t+1})$ inside is again at most $q_\pi(S_{t+1}, \pi'(S_{t+1}))$ , so substitute and expand. After $k$ substitutions the first $k$ actions follow $\pi'$ and only the tail still uses $\pi$ ; that tail is weighted by $\gamma^k$ , so in the limit the right-hand side is exactly $v_{\pi'}(s)$ . TRPO's monotonic-improvement bound is the same argument with an extra penalty for how far $\pi'$ moves from $\pi$ .

Example:

The greedy step only looks one action ahead. Why doesn't that produce a short-sighted policy?

2 of 2

When Improvement Stops

If a greedy step leaves the policy unchanged, then $v_\pi$ satisfies the Bellman optimality equation, and since that equation has a unique solution, $\pi$ must be optimal. This gives a clean termination test — stop when the policy is stable — and it also explains why the algorithm cannot stall at a suboptimal fixed point: the only policy that is greedy with respect to its own value function is the optimal one. That is a much stronger guarantee than gradient methods offer, where a zero gradient signals only a local optimum and says nothing about the global one.

Mathematical Intuition

If the greedy step returns $\pi$ itself, then for every state $v_\pi(s) = \max_a \sum_{s',r} p(s',r \mid s,a)[r + \gamma v_\pi(s')]$ . That is the Bellman optimality equation, whose unique solution is $v_*$ , so $v_\pi = v_*$ . Termination is guaranteed because values never decrease and a finite MDP has at most $|\mathcal{A}|^{|\mathcal{S}|}$ deterministic policies; a strictly improving sequence can never revisit one.

Example:

Could policy improvement cycle forever between two policies of equal value?

Papers

An Upper Bound on the Loss from Approximate Optimal-Value Functions (Singh & Yee, 1994)Trust Region Policy Optimization (Schulman et al., 2015)

Blogs

Policy iteration — Mastering Reinforcement Learning (Tim Miller)A (Long) Peek into Reinforcement Learning — Lil'Log

Definition

Policy iteration alternates full policy evaluation with greedy policy improvement until the policy stops changing. It terminates at the exact optimum in finitely many iterations, typically very few, because each greedy sweep changes the action at many states at once.

In this topic

1The Algorithm and Its Cost
2Modified (Truncated) Policy Iteration

1 of 2

The Algorithm and Its Cost

Policy iteration converges in remarkably few iterations — often fewer than ten even on large problems — because each greedy step changes the policy at many states simultaneously. The cost is that every iteration requires a full policy evaluation, itself many sweeps over the state space. So it performs few, very expensive iterations, which is exactly the tradeoff value iteration inverts. The empirical observation that the iteration count is roughly independent of state-space size is what keeps the algorithm competitive: the per-iteration cost grows with the problem, but the number of iterations largely does not.

Mathematical Intuition

Each iteration costs one evaluation, which is a linear solve of order $|\mathcal{S}|^3$ or a run of sweeps of order $|\mathcal{S}|^2|\mathcal{A}|$ each, plus one greedy pass. The iteration count is what stays small. Ye (2011) proved that for a fixed discount it is bounded by a polynomial in the numbers of states and actions, growing like $1/(1-\gamma)$ times a logarithm, and in practice it is far below even that bound. On Jack's Car Rental the evaluations took 126, 91, 80, 45 and 14 sweeps, shrinking as the policies stopped changing.

Example:

Jack's Car Rental has about 441 states. Policy iteration solves it in four policy improvements. Why so few?

2 of 2

Modified (Truncated) Policy Iteration

Nothing requires evaluation to run to convergence before improving. Truncating it after a fixed number of sweeps gives modified policy iteration, which still converges to the optimum. Setting the budget to a single sweep recovers value iteration exactly; setting it to infinity recovers classic policy iteration. The whole family is therefore parameterized by one quantity — how much evaluation you are willing to pay for per improvement — and recognizing that the two named algorithms are endpoints of a spectrum rather than rival methods makes the design space much easier to reason about.

Mathematical Intuition

Write the update as $\pi_{k+1} = \text{greedy}(v_k)$ followed by $v_{k+1} = (T_{\pi_{k+1}})^m v_k$ , where $T_\pi$ is one sweep of policy evaluation. With $m = 1$ this is $T^* v_k$ , value iteration. As $m \to \infty$ the inner loop converges to $v_{\pi_{k+1}}$ , which is policy iteration. Puterman and Shin proved convergence for every fixed $m$ , so the budget changes only the cost, never the answer.

Example:

How would you choose the evaluation budget in practice?

Papers

Modified Policy Iteration Algorithms for Discounted Markov Decision Problems (Puterman & Shin, 1978)The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the MDP with a Fixed Discount Rate (Ye, 2011)

Blogs

Policy iteration — Mastering Reinforcement Learning (Tim Miller)Dynamic Programming exercises and solutions — dennybritz/reinforcement-learning

Definition

Value iteration performs a single evaluation sweep per improvement by folding the max over actions directly into the Bellman update. It converges geometrically to $v_*$ from any initialization, and the optimal policy is extracted at the end with one greedy pass.

In this topic

1The Optimality Update
2Asynchronous Variants

1 of 2

The Optimality Update

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

Each sweep replaces every state's value with the best one-step lookahead rather than the policy-weighted average. Like its expectation counterpart, the Bellman optimality operator is a $\gamma$ -contraction, so the values converge geometrically to $v_*$ from any initialization. The optimal policy is extracted once at the end by a single greedy pass, which is why no policy is stored during the loop at all. That absence is the algorithm's real economy: it removes the bookkeeping of maintaining and comparing policies, leaving a single array of numbers and one update rule.

Mathematical Intuition

Because $T^*$ is a $\gamma$ -contraction, $\lVert v_k - v_* \rVert_\infty \le \gamma^k \lVert v_0 - v_* \rVert_\infty$ . Cutting the initial error by a factor of 1,000 takes 66 sweeps at $\gamma = 0.9$ and 688 at $\gamma = 0.99$ , which is why long horizons make value iteration slow. Undiscounted shortest-path problems can finish much sooner: on the 4x4 gridworld with $-1$ per step, value iteration reaches the exact $v_*$ after 3 sweeps, one per step of the longest shortest path.

Example:

Value iteration converges to $v_*$ only in the limit. When can you safely stop and extract the policy?

2 of 2

Asynchronous Variants

Nothing requires sweeping states in a fixed order or even updating them equally often. Asynchronous dynamic programming updates states one at a time in any order and still converges, provided every state continues to be selected eventually. This matters because it severs the link between making progress and completing a full sweep: computation can be concentrated where it is most useful. On a large problem a full sweep may never finish in reasonable time, yet a well-ordered asynchronous method can produce a good policy over the states that actually matter long before that point.

Mathematical Intuition

The max-norm contraction is what makes any order safe. Updating a single state $s$ moves its error to at most $\gamma \lVert v - v_* \rVert_\infty$ and leaves the others untouched, so the worst-case error never grows. Bertsekas showed that convergence needs only that every state keeps being updated. Prioritized sweeping ranks states by the size of their pending change, $\lvert \max_a \sum_{s',r} p(s',r \mid s,a)[r + \gamma V(s')] - V(s) \rvert$ , and updates the largest first.

Example:

How does asynchronous DP let you make progress on a problem far too large to sweep even once?

Papers

Learning to Act Using Real-Time Dynamic Programming (Barto, Bradtke & Singh, 1995)Prioritized Sweeping: Reinforcement Learning with Less Data and Less Time (Moore & Atkeson, 1993)

Blogs

Value Iteration — Mastering Reinforcement Learning (Tim Miller)Markov decision process (value and policy iteration) — Wikipedia

Definition

Generalized policy iteration is the pattern of maintaining a value function and a policy while making each more consistent with the other. Any interleaving converges to the optimal pair, and the pattern survives when evaluation is approximate, improvement is partial, or the model is unknown.

In this topic

1Competing and Cooperating Processes
2Why This Pattern Survives Without a Model

1 of 2

Competing and Cooperating Processes

Evaluation and improvement pull in opposite directions. Making the value function consistent with the policy usually breaks the policy's greediness; making the policy greedy invalidates the value function. The alternation still settles, but not because both steps are contractions. Evaluation is one: the Bellman expectation operator pulls $v$ toward $v_\pi$ . Improvement is monotone instead: by the policy improvement theorem it never lowers the value of any state. Values can therefore only rise, and in a finite MDP they stop rising exactly at a policy that is greedy with respect to its own value function, which is optimal. The competition is real locally but harmless globally.

Mathematical Intuition

Policy iteration produces a chain $v_{\pi_0} \le v_{\pi_1} \le v_{\pi_2} \le \dots \le v_*$ , holding state by state, with strict improvement somewhere at each step until the policy stops changing. Every link is a policy, and a finite MDP has finitely many, so the chain must end; it can only end at a policy for which the greedy step changes nothing, which the previous topic showed is optimal.

Example:

In what sense do evaluation and improvement 'compete'?

2 of 2

Why This Pattern Survives Without a Model

Generalized policy iteration never actually requires that evaluation be exact, that improvement be fully greedy, or that either use a known model. Those are properties of the dynamic-programming implementation, not of the pattern. Replace exact evaluation with sampled returns and you get Monte Carlo control; replace it with bootstrapped one-step estimates and you get SARSA and Q-learning; replace greedy improvement with a gradient step on a parameterized policy and you get actor-critic and PPO. Recognizing this makes the remaining chapters far easier, because each is a substitution into a structure you already understand.

Mathematical Intuition

Approximate policy iteration has a clean error bound. If each evaluation is within $\epsilon$ of the true $v_{\pi_k}$ and each improvement is exactly greedy, then eventually $\lVert v_{\pi_k} - v_* \rVert_\infty \le 2\gamma\epsilon/(1-\gamma)^2$ . Sampled or learned evaluation therefore does not break the pattern; it only limits how close to optimal the final policy can get, and the $(1-\gamma)^2$ shows why long horizons make that limit loose.

Example:

Given that GPI is so general, what actually distinguishes the algorithms in Chapters 4 through 8?

Papers

Approximate Modified Policy Iteration (Scherrer et al., 2012)Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm (Silver et al., 2017)

Blogs

Spinning Up, Part 2: Kinds of RL Algorithms — OpenAI A (Long) Peek into Reinforcement Learning — Lil'Log

Chapter 3: Dynamic Programming

Chapter Overview

Chapter Roadmap

Policy Evaluation

Policy Improvement

Policy Iteration

Value Iteration

Generalized Policy Iteration

5 topics in this chapter

Policy Evaluation

Definition

In this topic

Iterative Policy Evaluation

When to Stop

Related Problems on PixelBank

Policy Improvement

Definition

In this topic

The Policy Improvement Theorem

When Improvement Stops

Related Problems on PixelBank

Policy Iteration

Definition

In this topic

The Algorithm and Its Cost

Modified (Truncated) Policy Iteration

Related Problems on PixelBank

Value Iteration

Definition

In this topic

The Optimality Update

Asynchronous Variants

Related Problems on PixelBank

Generalized Policy Iteration

Definition

In this topic

Competing and Cooperating Processes

Why This Pattern Survives Without a Model

Related Problems on PixelBank