Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 37 ยท Dynamic Programming

Policy Improvement and Policy Iteration

Learn the policy improvement theorem and policy iteration: alternate evaluation and greedy improvement until the policy is stable, implemented step by step on a slippery grid world.

Evaluating a policy tells us how good it is. The natural next question: can we use that knowledge to make it better? Yes, and the recipe is simple enough to fit in a sentence: look at each state's action values and become greedy. Repeat evaluation and greedy improvement and you reach an optimal policy. That algorithm is policy iteration.

Policy improvement

Suppose we have v_pi for some policy. In state s we currently take the action prescribed by pi. Could another action be better? Compute its action value with one step of lookahead:

q_pi(s, a) = sum over s', r of p(s', r | s, a) * [ r + gamma * v_pi(s') ]

If q_pi(s, a) > v_pi(s) for some a, then taking a in s and following pi afterwards beats following pi all the way. The policy improvement theorem generalizes this: if a new policy pi' satisfies q_pi(s, pi'(s)) >= v_pi(s) in every state, then pi' is at least as good as pi everywhere. The easiest way to satisfy it is the greedy policy:

pi'(s) = argmax over a of q_pi(s, a)

If the greedy policy is no better (values stay the same), pi already satisfies the Bellman optimality equation and is optimal.

Policy iteration

Alternate the two steps:

  1. Evaluate the current policy to get v_pi.
  2. Improve by acting greedily with respect to v_pi.
  3. Stop when the policy no longer changes.
flowchart LR
    P0["pi_0 (arbitrary)"] -->|"evaluate"| V0["v_pi0"]
    V0 -->|"greedy improve"| P1["pi_1"]
    P1 -->|"evaluate"| V1["v_pi1"]
    V1 -->|"greedy improve"| P2["... pi* (stable)"]

A finite MDP has finitely many deterministic policies and every step improves (or keeps) the policy, so the process must end, and in practice it takes surprisingly few iterations, often fewer than ten.

One improvement step on the grid world

Using the 4x4 grid from the previous lessons, evaluate the random policy and then make it greedy. Arrows show the new action in each square (several arrows mean a tie).

Python Evaluate, then become greedy

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.

One improvement of the random policy is already optimal for this grid: every square points along a shortest path to a terminal corner. That happens often in small deterministic problems, but not in general.

The full loop on a harder problem

Let us make life harder. The version below makes moves slippery: with probability slip the agent moves sideways instead of where it intended. We also use gamma = 0.95 instead of 1. Now we run the whole loop, printing how often the policy changed, until it is stable. We start from a deliberately bad policy that always goes up, and note that evaluating it with gamma = 1 would diverge; discounting rescues us.

Python Full policy iteration with a slippery grid

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.

Even from a poor start, the policy usually stabilizes within a handful of iterations. Notice that each iteration includes a full evaluation: that is the expensive part. Do we really need to evaluate to convergence before improving? Value iteration answers no.

Why it works, and when it fails

  • Monotonic improvement. Each new policy is at least as good everywhere, so values never decrease.
  • Termination. Finitely many deterministic policies; no policy repeats because values strictly improve until optimal.
  • Ties. Choosing among equally good actions can make the policy flip forever if you use "changed" as the stopping test on tied actions. Break ties consistently (for example, lowest index) as np.argmax does, and round values before comparing.
  • Known model. Policy iteration needs p(s', r | s, a) for the lookahead. Without it you need the sampling methods of the next chapter.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the policy improvement theorem guarantee?

    If q_pi(s, pi'(s)) is at least v_pi(s) everywhere, pi' is at least as good as pi in every state.
  2. 2. When does policy iteration stop?

    A stable policy is greedy with respect to its own value function, so it satisfies the optimality equation.
  3. 3. What are the two alternating steps?

    Evaluate the current policy, then improve it greedily, and repeat.
  4. 4. Why can ties between equal action values cause problems?

    Use a deterministic tie-break and compare policies after rounding values to avoid endless flipping.

Summary

  • Improvement: make the policy greedy with respect to v_pi; the theorem says this cannot hurt.
  • Policy iteration alternates full evaluation and greedy improvement until the policy is stable; the result is optimal.
  • It usually needs only a few iterations but each one runs a complete evaluation.
  • Break ties consistently, and discount (or ensure termination) so evaluation converges.

Next: Value Iteration