rlbook.ai
Chapter 22
📝Draft

Policy Improvement

Finding better policies through value functions

Prerequisites:

What You'll Learn

  • Explain the policy improvement theorem and why it guarantees progress
  • Implement policy iteration from scratch
  • Implement value iteration from scratch
  • Compare policy iteration and value iteration on the same MDP
  • Solve simple MDPs to find optimal policies using DP methods

We can now evaluate any policy, computing VπV^\pi for any choice of π\pi. But our goal is not just to evaluate policies. We want to find the best policy.

The insight of this chapter is that once we have VπV^\pi, we can construct a better policy. And by alternating between evaluation and improvement, we can climb all the way to the optimum. Try it below: run sweeps and watch the optimal values and policy emerge.

Value Iteration Visualization

Watch value iteration solve the GridWorld problem step by step.

0.0
S
0.0
0.0
0.0
0.0
🧱
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
🎯
Click "Step" or "Play" to start value iteration
0
Iteration
0.0000
Max Delta
0.90
Gamma
🎯Goal (+10)
🧱Obstacle
High Value
Low Value
How it works: Value iteration repeatedly applies the Bellman equation V(s) = max_a [R(s,a) + γ V(s')] until values converge. Each cell shows its estimated value, and arrows show the optimal policy. Higher gamma values make the agent care more about future rewards. More negative step rewards encourage shorter paths.

The Core Insight

📖Policy Improvement

The process of constructing a new policy that is at least as good as the current policy, by acting greedily with respect to the current value function.

Suppose you know Vπ(s)V^\pi(s) for all states. From any state ss, you can ask: “What if I took a different action just once, then followed π\pi afterward? Would I do better?”

The greedy action is the one that maximizes this one-step lookahead. The policy improvement theorem tells us something remarkable: if we switch to always taking the greedy action, we are guaranteed to do at least as well as before, and usually better.

This leads to two algorithms, both of which converge to the optimal policy π∗\pi^* and optimal value function V∗V^*:

Policy Iteration
  • Evaluate the current policy completely
  • Improve: make the policy greedy with respect to those values
  • Repeat until the policy stops changing
  • Very few rounds, but each needs a full evaluation
Value Iteration
  • Apply the Bellman optimality backup to all states
  • Repeat until the values converge
  • Extract the greedy policy at the end
  • Cheap per sweep, but may need many sweeps
ℹ️Note

Both algorithms find the same optimal policy. They differ in how they organize computation. The best choice depends on the problem structure and computational constraints.

Chapter Overview

The Policy Improvement Theorem
The theoretical foundation: why greedy improvement always works
Policy Iteration
Alternating evaluation and improvement until convergence
Value Iteration
Finding optimal values directly with a single update rule

The Greedy Policy

The key operation in both algorithms is constructing a greedy policy from a value function: in every state, pick the action with the best one-step lookahead — immediate reward plus discounted value of the state you land in.

∑Mathematical Details

Given a value function VV, the greedy policy selects:

π′(s)=arg⁡max⁡a[R(s,a)+γ∑s′P(s′∣s,a)V(s′)]\pi'(s) = \arg\max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right]

This picks the action that maximizes expected immediate reward plus discounted future value. This is the one-step lookahead from the Bellman optimality equation, applied as a decision rule.

The greedy policy answers: “Looking one step ahead and using my current value estimates for what comes after, which action looks best?”

It is called “greedy” because it always takes what looks best right now. Surprisingly, this myopic approach leads to globally optimal behavior when combined with accurate value estimates.

Why This Matters

Dynamic Programming gives us exact solutions to MDPs. When we have access to the complete model (all transitions and rewards), DP finds the true optimal policy.

But DP has limitations:

Despite these limitations, DP is essential:

  1. It provides the theoretical foundation for understanding RL
  2. Many RL algorithms are approximate versions of DP methods
  3. For small MDPs, DP gives the ground truth to compare against

Key Questions We Will Answer

  • Why does greedy improvement never make things worse?
  • How many policy iterations are typically needed?
  • When should you use policy iteration vs. value iteration?
  • What is the relationship between these algorithms and Q-learning?

Check Your Understanding

Check your understanding
1. When is the greedy policy guaranteed to be at least as good as the current policy π?
2. Value iteration never stores a policy during its sweeps. How can it still find the optimal one?
3. Why must policy iteration terminate (rather than improve forever)?
4. Policy iteration stops when the improvement step leaves the policy unchanged. What does that condition mean?
5. What is the basic computational trade-off between policy iteration and value iteration?

Key Takeaways

  1. Greedy improvement never makes a policy worse
    The policy improvement theorem: acting greedily with respect to the exact value function of the current policy produces a policy that is at least as good in every state.
  2. Policy iteration alternates evaluation and improvement
    Evaluate, greedify, repeat. It terminates in finitely many rounds, and only at an optimal policy.
  3. Value iteration folds improvement into the value update
    The max over actions in the Bellman optimality backup improves implicitly; the policy is extracted once at the end.
  4. Both algorithms reach the same optimum
    For finite MDPs with a known model, they differ in computational path, not in the answer.
  5. DP needs the full model — RL removes that requirement
    Everything here assumes known transitions and rewards. Monte Carlo and TD methods estimate the same quantities from experience.
Next ChapterMulti-Armed Bandits→