Dynamic Programming

Dynamic programming (DP) is the collection of algorithms that compute optimal policies given a perfect model of the environment as a Markov decision process.¹ That assumption — that the dynamics $p(s^{\prime },r\mid s,a)$ are fully known — names what a learning agent lacks, so classical DP is of limited direct use in reinforcement learning. Its importance is theoretical. DP defines, exactly and by construction, the optimal value functions and policies that every model-free method in the rest of the course only approximates. Read this way, Monte Carlo and temporal-difference learning are attempts to achieve the same effect as DP with less computation and without a model. To understand what they approximate, first see how DP computes it directly.

Throughout, assume a finite MDP: the state, action, and reward sets $\mathcal{S},\mathcal{A},\mathcal{R}$ are finite, and the dynamics are a known set of probabilities $p(s^{\prime },r\mid s,a)$. The single idea behind DP, and behind reinforcement learning generally, is to use value functions to organize the search for good policies.

The plan, in outline: a value function scores how good each state is. If we knew the best possible score for every state, acting optimally would be easy: at each state, take the action that leads to the best-scored successors. So the whole problem reduces to computing those best scores. We already have optimal policies the moment we have the optimal value functions $v_{\ast }$ or $q_{\ast }$, because they satisfy the Bellman optimality equations

DP algorithms are obtained by turning Bellman equations like these into assignments — into update rules for improving approximations of the desired value functions. That one move, equation becomes assignment, is the whole method.

Policy evaluation (prediction)

Start with the easier of the two tasks: given a fixed policy $\pi$, compute its state-value function $v_{\pi }$. In the DP literature this is policy evaluation; it is also the prediction problem. Recall the Bellman equation for $v_{\pi }$,

for all $s\in \mathcal{S}$. If the dynamics are completely known, this is a system of $|\mathcal{S}|$ simultaneous linear equations in $|\mathcal{S}|$ unknowns — the values $v_{\pi }(s)$. In principle its solution is a straightforward, if tedious, linear-algebra computation. For our purposes an iterative method is more suitable, and it is the same move applied to a whole sequence of approximations.

The intuition: start with a rough guess for every state's value, then repeatedly sharpen it. Each pass replaces every state's guess with a better one computed from its neighbors' current guesses. Do this enough times and the guesses stop moving — they have settled onto $v_{\pi }$. Here is that loop written out.

Consider a sequence of approximate value functions $v_0,v_1,v_2,\dots$, each a map from ${\mathcal{S}}^{+}$ (the states plus, in an episodic task, a terminal state) to the reals. The initial $v_0$ is chosen arbitrarily, except that a terminal state must be given value $0$; each successive approximation is obtained by using the Bellman equation for $v_{\pi }$ as an update rule:

Clearly $v_k=v_{\pi }$ is a fixed point of this rule, because the Bellman equation for $v_{\pi }$ asserts equality in exactly this case. And the sequence $\{v_k\}$ can be shown to converge to $v_{\pi }$ as $k\to \infty$ under the same conditions that guarantee the existence of $v_{\pi }$ (either $\gamma <1$ or guaranteed eventual termination under $\pi$). This algorithm is iterative policy evaluation.²

The expected update is what separates DP from the sampling methods to come. A Monte Carlo or TD update pushes value toward one sampled successor; the DP update sweeps every successor, weighted by its probability. That is only possible because the model $p$ is in hand.

To turn the update into a program you might keep two arrays, one for the old $v_k(s)$ and one for the new $v_{k+1}(s)$, computing each new value from the old ones. It is simpler, and usually faster, to use one array and update in place, overwriting each value as soon as it is computed, so later updates in the same pass already see some fresh values. We think of one pass over the whole state set as a sweep. For the in-place version the order of states within a sweep affects the rate of convergence, and it is the in-place version we normally have in mind.

Formally the iteration converges only in the limit, so in practice we stop it short: after each sweep, test the largest change in any state's value, ${\max }_s|v_{k+1}(s)-v_k(s)|$, and halt when it drops below a small threshold $\theta$.

A gridworld sweep

Take the $4\times 4$ gridworld below. The nonterminal states are $\mathcal{S}=\{1,2,\dots ,14\}$; the two shaded corner cells are one terminal state. Four actions — up, down, right, left — move the agent deterministically one cell, except that any move off the grid leaves the state unchanged. Every transition pays reward $-1$ until termination. This is an undiscounted ($\gamma =1$), episodic task.

Evaluate the equiprobable random policy — each action with probability $\frac{1}{4}$. Initialize $v_0(s)=0$ everywhere and apply the expected update in place, sweep after sweep. The first sweep sets every nonterminal state to $-1$ (each of the four equally likely moves costs $-1$ and lands on a state still valued $0$). Later sweeps let the $-1$ penalties accumulate outward from the terminal corners, and the estimates fan out toward $v_{\pi }$.

The limit $v_{\pi }$ gives, at each state, the negation of the expected number of steps to termination under the random policy. Every one of those numbers satisfies the Bellman equation exactly: a state's value equals $-1$ plus the average of its four (in-place, deterministic) neighbors' values.

Policy improvement

We compute $v_{\pi }$ in order to find better policies. Suppose we have $v_{\pi }$ for a deterministic policy $\pi$, and at some state $s$ we consider deviating — taking an action $a\ne \pi (s)$ once, then following $\pi$ ever after. The value of that deviation equals the action-value

The test is whether this is greater or less than $v_{\pi }(s)$. If it is greater — taking $a$ once and then following $\pi$ beats following $\pi$ from the start — then one would expect it to be better still to take $a$ every time $s$ comes up. That this intuition is correct is the content of a general result.

The idea of the proof is simple even if the algebra looks dense. If deviating to ${\pi }^{\prime }$ for one step and then reverting to $\pi$ never hurts, then deviating for two steps cannot hurt either — apply the same fact at the next state. Keep pushing the revert to $\pi$ point one step further into the future and, in the limit, the agent follows ${\pi }^{\prime }$ forever. That limit is $v_{{\pi }^{\prime }}$. Here is the same argument as a telescoping expansion: start from the premise $v_{\pi }(s)\le q_{\pi }(s,{\pi }^{\prime }(s))$, expand $q_{\pi }$ by its definition, and reapply the premise at the successor, again and again.

Each application of the premise trades one step of $\pi$'s continuation for one step of ${\pi }^{\prime }$'s, and in the limit the entire tail is ${\pi }^{\prime }$'s — which is $v_{{\pi }^{\prime }}(s)$.

The natural way to use the theorem is to improve at every state at once. Consider the new greedy policy ${\pi }^{\prime }$ that, in each state, takes the action that looks best under one step of lookahead on $v_{\pi }$:

By construction $q_{\pi }(s,{\pi }^{\prime }(s))={\max }_a{q}_{\pi }(s,a)\ge v_{\pi }(s)$, so the greedy policy meets the theorem's condition and is at least as good as $\pi$. Making a new policy greedy with respect to the value function of the old one is policy improvement.³

What if the greedy ${\pi }^{\prime }$ is only as good as $\pi$, not strictly better? Then $v_{{\pi }^{\prime }}=v_{\pi }$, and the greedy equation reads

which is precisely the Bellman optimality equation. So $v_{{\pi }^{\prime }}=v_{\ast }$, and both $\pi$ and ${\pi }^{\prime }$ are optimal. Policy improvement gives a strictly better policy unless the original one is already optimal. (Everything here extends to stochastic policies; when several actions tie for the max, any apportioning of probability among them is a valid greedy policy.)

Policy iteration

Once a policy $\pi$ is improved to a better ${\pi }^{\prime }$, we can evaluate ${\pi }^{\prime }$ and improve it again, and again. This produces a chain of monotonically improving policies and value functions:

where $\stackrel{E}{\to }$ is an evaluation and $\stackrel{I}{\to }$ an improvement. Each policy is a strict improvement over the last (unless already optimal). A finite MDP has only finitely many deterministic policies, so this chain must reach an optimal policy and value function in a finite number of iterations. This is policy iteration.⁴

The evaluation of each policy is itself the iterative sweep from before, and it is started from the value function of the previous policy rather than from scratch. Because the value function usually changes little from one policy to the next, this warm start makes evaluation converge much faster.

On the $4\times 4$ gridworld above, greedy-with-respect-to-$v_k$ policies point toward the terminal corners along shortest paths, and in that small case the greedy policy becomes optimal after only a few evaluation sweeps — well before $v_k$ has converged to $v_{\pi }$. That observation is precisely the opening for the next algorithm.

A policy iteration solved by hand

For example, take a two-state MDP with states $\{L,R\}$ and two actions, stay and switch, discount $\gamma =0.9$. The dynamics are deterministic: stay keeps the current state, switch moves to the other. Rewards depend only on the landing state — arriving in $L$ pays $0$, arriving in $R$ pays $+1$ — so from $L$, stay pays $0$ and switch pays $+1$; from $R$, stay pays $+1$ and switch pays $0$. The optimal policy is obviously reach $R$ and stay, but watch policy iteration discover it.

Start from the deliberately bad policy ${\pi }_0$: switch in both states, so the agent oscillates $L\to R\to L\to \cdots$. Evaluate it. Since the policy is deterministic the Bellman equations are two linear equations,

Substitute the second into the first: $v_{{\pi }_0}(L)=1+0.81v_{{\pi }_0}(L)$, so $v_{{\pi }_0}(L)=1/0.19\approx 5.263$ and $v_{{\pi }_0}(R)=0.9\times 5.263\approx 4.737$. Now improve. Compute both action values at each state from $v_{{\pi }_0}$:

The greedy choice at $L$ is switch (unchanged), but at $R$ it is stay ($5.263>4.737$) — the policy changed, so ${\pi }_1=(\text{switch},\text{stay})$. Evaluate ${\pi }_1$: now $R$ is absorbing under the policy, giving $v_{{\pi }_1}(R)=1+0.9v_{{\pi }_1}(R)=10$ and $v_{{\pi }_1}(L)=1+0.9(10)=10$. Improve again: $q_{{\pi }_1}(L,\text{switch})=1+0.9(10)=10$ ties $q_{{\pi }_1}(L,\text{stay})=0+0.9(10)=9$, so $L$ keeps switch; and $q_{{\pi }_1}(R,\text{stay})=10>q_{{\pi }_1}(R,\text{switch})=9$, so $R$ keeps stay. No action changed: the policy is stable, and ${\pi }_1={\pi }_{\ast }$ with $v_{\ast }=(10,10)$. Two evaluations and two improvements, and the chain terminated.

The same problem run as value iteration from $v_0=(0,0)$ needs several sweeps to crawl the value up toward $10$ ($v_1=(1,1)$, $v_2=(1.9,1.9)$, $v_3=(2.71,2.71)$, converging geometrically to $10$ as ${\sum }_{k}0.9^k$), but the greedy policy it reads off is already $(\text{switch},\text{stay})$ after the very first sweep. This is the general pattern: the greedy policy stabilizes long before the values do.

Jack's car rental: policy iteration at scale

The two-state solve fits on a napkin; policy iteration also handles problems with thousands of states in a handful of iterations. In Jack's car rental (Example 4.2), Jack runs two rental locations. Each night he may move up to five cars between them at a cost of USD 2 per car; each morning, customers arrive at each location as Poisson random variables (means $3$ and $4$ for requests, $3$ and $2$ for returns) and each car rented pays USD 10. With at most $20$ cars per location, the state is the pair of overnight inventories — $21\times 21=441$ states — and the action is the signed number of cars moved, from $-5$ to $+5$. Discount $\gamma =0.9$; the task is continuing.⁵

Policy iteration starts from the do-nothing policy (never move a car), evaluates it by solving the $441$-state Bellman system to tolerance, then improves greedily — each state's new action is the transfer that maximizes expected reward-plus-value under the known Poisson dynamics. The policy that emerges after the first improvement already moves cars from the busier location toward the one more likely to run dry; a few more evaluate–improve rounds refine the transfer thresholds, and the process converges to the optimal policy in about four iterations.

Jack's rental is the standard demonstration that policy iteration's finite-step guarantee is not just theoretical comfort: on a $441$-state problem with a nontrivial stochastic model, it converges in single-digit iterations. That Poisson-dynamics model carries the arbitrary nonlinearity that direct optimization struggles with but DP handles without difficulty, because DP only ever queries the model for one-step transition probabilities.

Value iteration

A drawback of policy iteration is that each round waits for a full policy evaluation, itself a protracted iterative computation. Must we wait for exact convergence to $v_{\pi }$ before improving? The gridworld says no: the greedy policy often stops changing long before the values do. So truncate the evaluation.

The extreme case stops policy evaluation after just one sweep — one update of each state. The result is value iteration, which folds improvement and truncated evaluation into a single update by simply putting a $\max$ where policy evaluation had a policy-weighted average:

For arbitrary $v_0$, the sequence $\{v_k\}$ converges to $v_{\ast }$ under the same conditions that guarantee $v_{\ast }$ exists. This is nothing but the Bellman optimality equation turned into an update rule — the same equation-becomes-assignment move, now applied to the optimality equation rather than the policy Bellman equation. The update is identical to iterative policy evaluation's except that it takes the maximum over all actions instead of averaging over the policy's.

Like policy evaluation, value iteration formally needs infinitely many iterations, so in practice we stop when a sweep changes the values by less than $\theta$ and read off a deterministic policy greedy with respect to the final $V$.

Value iteration effectively does one sweep of policy evaluation and one sweep of policy improvement per pass. More generally, one can interpose several evaluation sweeps between improvement sweeps; the whole family of truncated policy iteration algorithms is a sequence of sweeps, some using evaluation updates and some using value-iteration updates. Since the $\max$ is the only difference, they all converge to an optimal policy for discounted finite MDPs.

The gambler's problem: value iteration on a probability

A worked value-iteration example that yields a surprising policy is the gambler's problem (Example 4.3). A gambler bets on coin flips: on each flip he stakes some integer number of dollars from his current capital; heads pays even money (he gains his stake), tails loses it. The game ends when his capital reaches USD 100 (win) or USD 0 (lose). The state is the capital $s\in \{1,2,\dots ,99\}$; the actions are stakes $a\in \{0,1,\dots ,\min (s,100-s)\}$. All rewards are zero except on the transition that reaches USD 100, which pays $+1$. The task is undiscounted and episodic, so $v_{\ast }(s)$ gives the probability of eventually winning from capital $s$ under optimal play.⁶

Let $p_h$ be the probability of heads. The value-iteration update at each capital sweeps over all stakes:

with $v_k(0)=0$ and $v_k(100)=1$ held fixed. Run this to convergence for $p_h=0.4$ (a losing coin). The value function rises monotonically from $0$ to $1$ in a scalloped curve, and the optimal policy is jagged and non-obvious: at capital $50$ the gambler stakes everything (a stake of $50$ gives one shot at the goal), at $51$ he stakes only $1$, and the stake pattern repeats a self-similar structure at $25$, $75$, and their subdivisions.

The lesson of the gambler's problem is that value iteration recovers optimal behavior even when that behavior is counterintuitive. A human might bet a steady fraction; the optimal policy for a losing coin is to make aggressive lump bets that reach the goal in as few flips as possible, because every extra flip of an unfavorable coin loses probability. Value iteration finds this by mechanically sweeping the Bellman optimality update — no insight about coin-flip strategy is programmed in.

This continues in Dynamic Programming: Asynchronous DP and Generalized Policy Iteration, which loosens the full-sweep schedule, names the evaluation-improvement pattern that underlies almost every RL method, and traces DP forward to its modern approximate and neural descendants.