Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 37 ยท Dynamic Programming

Iterative Policy Evaluation (Prediction with DP)

Compute the value function of a policy by sweeping the Bellman expectation backup: learn expected updates, convergence tests, in-place sweeps and see it work on a grid world.

Dynamic programming (DP) in reinforcement learning means algorithms that compute optimal behavior from a complete model of the MDP, that is, when you know p(s', r | s, a). Real problems rarely hand you the model, so pure DP is seldom the final tool, but it is the theoretical backbone: Monte Carlo, TD and deep RL methods are all approximations of what DP does exactly. Understand DP and the rest becomes variations on a theme.

The DP story has two parts: prediction (given a policy, compute its value function) and control (find the best policy). This lesson covers prediction.

The idea

We know that v_pi satisfies the Bellman expectation equation. Turn it into an update rule:

v_{k+1}(s) = sum over a of pi(a|s) * sum over s', r of p(s', r | s, a) * [ r + gamma * v_k(s') ]

Start from an arbitrary v_0 (zeros are fine, terminal states must stay 0). Apply the update to every state, again and again. Each pass is called a sweep. The sequence v_0, v_1, v_2, ... converges to v_pi, because the update is a contraction when gamma < 1 (and also for episodic tasks that surely terminate).

Because each update uses an expectation over all possible next states rather than a single sample, it is called an expected update. Contrast this with the sampled updates of Monte Carlo and TD learning later.

flowchart LR
    A["v_0 = zeros"] --> B["sweep: update every state"]
    B --> C{"largest change below theta?"}
    C -->|"no"| B
    C -->|"yes"| D["return v โ‰ˆ v_pi"]

Writing it in code

We store the model as P[s][a] = [(prob, next_state, reward), ...], the same layout as before, using integer states. The function below builds the 4x4 grid world model and runs policy evaluation for the uniform random policy, printing the table after a few sweeps so you can watch information spread outward from the terminals.

Python Policy evaluation sweeps on the grid world

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After one sweep every non-terminal state is -1 (one step costs 1 and the old values were zero). After two sweeps the squares next to a terminal become about -1.75, and so on: the values propagate outward from the terminal states one step per sweep. At convergence they match the exact solution from the Bellman equations lesson: -14, -20, -22 and friends.

Stopping rule

You cannot wait for exact convergence, so pick a small threshold theta and stop when the biggest change in a sweep is below it:

delta = max over s of |v_{k+1}(s) - v_k(s)|, stop when delta < theta.

A typical theta is 1e-6 to 1e-3. Smaller is more accurate but needs more sweeps. For a sense of scale, the error shrinks roughly like gamma^k, so with gamma = 0.9 each sweep removes about 10% of what is left.

In-place sweeps

The version above keeps two arrays, v_k and v_{k+1}, and reads only from the old one. A common variation updates in place: it uses the newest available values as soon as they exist. It saves memory and usually converges faster, because new information is used immediately. Its result depends on the order in which you visit states, a theme we pick up in Asynchronous DP.

Python Two arrays versus in-place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In-place needs noticeably fewer sweeps and gives the same fixed point.

Evaluating action values

The same idea works for q_pi: replace the state update by one over state-action pairs. In practice DP implementations usually compute v_pi first and derive q_pi(s, a) = sum p * (r + gamma * v(s')) with one extra lookahead, as you saw before.

Cost and limits

One sweep costs about |S| * |A| * (number of outcomes) operations. For 16 states that is nothing; for backgammon (about 10^20 states) a full sweep is impossible. DP is still polynomial in the number of states, vastly better than the |A|^|S| policy enumeration, but the curse of dimensionality limits it to small or structured problems.

Common mistakes

  • Updating terminal states. Their value must stay 0; skip them or give them zero-valued absorbing transitions.
  • Reading and writing the same array while believing you use two arrays (a subtle bug that silently turns your code into the in-place variant).
  • Using gamma = 1 on a policy that never terminates (for instance, a policy that always walks into a wall): the values then diverge.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does one sweep of iterative policy evaluation do?

    A sweep updates each state's value from its successors' current values using the policy and model.
  2. 2. Why is it called an expected update?

    DP uses the full distribution p(s', r | s, a), not sampled transitions.
  3. 3. What is the usual stopping rule?

    The max change across states tells us how far we are from the fixed point.
  4. 4. What is true of in-place updates?

    Both variants reach v_pi, but in-place reuses fresh values and tends to be faster.

Summary

  • DP needs a model; policy evaluation computes v_pi by repeating the Bellman expectation update.
  • Values spread outward from terminal states by one step per sweep; stop when delta < theta.
  • In-place sweeps use fresh values immediately, saving memory and often sweeps.
  • A sweep costs time proportional to the number of states and actions, which limits DP to moderate problems.

Next: Policy Improvement and Policy Iteration