When the MDP is fully known, that is, when the transitions and rewards are known, the way to compute the optimal policy is dynamic programming (DP). Since we find the answer from the model alone, without interacting with the environment, this is called planning. DP works because the Bellman equation breaks the problem into subproblems (the principle of optimality) and those partial solutions can be stored in the value function and reused.

Lecture slides: PDF

What dynamic programming is

The name misleads from the start. Here “programming” is not writing code, but mathematical optimization for finding an optimal solution, as in linear programming. “Dynamic” means a sequential problem over time. There is a famous story that Richard Bellman, who coined the name, deliberately chose a plausible, hard-to-object-to name to slip past the Secretary of Defense of the day, who disapproved of mathematical research. So there is no need to be intimidated by the weight of the name.

The core idea is simple. Break a large problem into small subproblems, solve those, and combine their answers to solve the large one. For this to work, two conditions are needed.

  • Optimal substructure: the optimal solution of the whole decomposes into optimal solutions of subproblems (the principle of optimality).
  • Overlapping subproblems: the same subproblem appears many times, so an answer solved once can be stored and reused.

An MDP satisfies both exactly. The Bellman equation gives the recursive decomposition “the answer at the current state = the current reward + the answers at the next states” (optimal substructure), and those partial solutions are written into a table called the value function, pulled out again whenever a neighbour is computed (overlapping subproblems). Just as memoizing earlier values when counting Fibonacci by hand turns exponential time into polynomial time, here too the moment we memoize the values, the computation becomes manageable.

So DP is the most ideal case in reinforcement learning. Under the premise that the environment (transitions and rewards) is perfectly known, the optimal policy comes out simply by solving the Bellman equation iteratively. The lectures ahead strip away this perfect knowledge one piece at a time, and ask whether we can still learn.

Policy evaluation

The problem of finding the value $v_\pi$ of a given policy $\pi$ (prediction). We turn the Bellman expectation equation into an update rule and iterate.

$$v_{k+1}(s) = \sum_a \pi(a\mid s)\left(\mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_k(s')\right)$$

Growing $k$ with a synchronous backup that updates all states at once converges to $v_\pi$.

Silver’s example is a small grid world. On a 4×4 grid, the two corner squares are terminal states, and each step gives a reward of −1. Put a policy that picks up/down/left/right uniformly at random and run iterative evaluation, and the values, all 0 at first, settle over the iterations into ever larger negative numbers the farther a square is from a terminal. After just a few sweeps, a map of “how far each square is from a terminal” emerges.

The top-left and bottom-right are terminal states, and each step is −1. Each press of “one iteration” updates all squares simultaneously, and the values converge. The arrows are the greedy policy at that moment. Remarkably, the policy arrows are already optimal long before the values fully converge. Switching the mode to “value iteration” shows the version that updates with the maximum value.

One curious point. From this evaluation alone, if you extract the greedy policy that moves to the higher-valued neighbour at each square, it is often already the optimal policy. This is where evaluation and improvement naturally connect.

Policy iteration

The problem of finding the optimal policy (control). We alternate evaluation and improvement.

  1. Evaluate: find $v_\pi$ of the current policy.
  2. Improve: build a new policy greedily with respect to $v_\pi$. $\pi'(s) = \arg\max_a q_\pi(s,a)$.

The improved policy is never worse (the policy improvement theorem). Alternating these two steps converges to the optimal policy $\pi_*$.

Silver’s example of policy iteration is Jack’s Car Rental. Cars are moved between two offices overnight (at a cost per car moved), and renting them out during the day generates income. Demand and returns are stochastic (Poisson). Run policy iteration, and the policy map of “how many cars to move given how many are at each office” is refined, over the iterations, into a clear staircase shape.

Evaluation and improvement need not be alternated all the way to the end. As we saw in the grid above, it converges whether you do evaluation a few times and then improve, or even just once and then improve. The big picture in which mixing evaluation and improvement in any way still converges to the optimum is called generalised policy iteration (GPI). Nearly every reinforcement learning method to come is a variation on this GPI.

Value iteration

Without holding a policy explicitly, we iterate the Bellman optimality equation directly.

$$v_{k+1}(s) = \max_a\left(\mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_k(s')\right)$$

It converges to $v_*$, and extracting the greedy policy at the end gives the optimal policy. Since it does evaluation just once and immediately takes the maximum, it is more concise than policy iteration. The difference is that the intermediate values may not be the value of any actual policy.

The intuition is the same as finding the shortest path. The value of the terminal (goal) square is certain. From there, exact values spread out like ripples to the squares one step away, two steps away. Each iteration widens this ripple by one square. Run value iteration on the grid and you can see the values settle first around the goal, then the ripple spread outward.

Why it converges

The Bellman operator is a $\gamma$-contraction mapping. Iterating shrinks the distance between two value functions by a factor of $\gamma$ each time, converging to a unique fixed point. That fixed point is the true value function. Policy evaluation, policy iteration, and value iteration all converge for the same reason.

Summary and limits

All three methods are based on state values $v$, and each iteration is a synchronous backup that sweeps the entire state space. When there are many states, a single sweep is expensive, so Silver also points to asynchronous DP, which updates only the states that need it. Variants include overwriting in place (in-place), updating states with large error first (prioritised sweeping), and updating from the states the agent actually visits (real-time DP).

And DP’s update is a full-width backup. When updating one state, it considers every possible next state without exception. Accurate, but expensive by the branching factor, and it requires knowing the transitions. The model-free methods of the next lecture put a sample backup in its place. They update using just one actually-experienced next state. Cheap, no model needed, and it scales to large problems.

DP is powerful, but two things hold it back. It requires knowing the transitions and rewards, and computation grows in proportion to the number of states. From the next lecture on, we move to model-free methods that learn from experience alone, without a model of the environment.