rlbook.ai
Chapter 21
📝Draft

Policy Evaluation

Computing the value of a policy when you know the model

Prerequisites:

What You'll Learn

  • Implement iterative policy evaluation from scratch
  • Explain why policy evaluation is guaranteed to converge
  • Choose appropriate stopping criteria for practical applications
  • Trace through policy evaluation on a simple MDP step by step
  • Understand the computational requirements and trade-offs

We have the Bellman equations. We know that the value function VπV^\pi must satisfy them. But how do we actually compute VπV^\pi for a given policy?

The answer: just keep applying the Bellman equation until the values stop changing.

Initialize
set all values to zero
Sweep
Bellman update for every state
Check
did any value change much?
Repeat
until changes fall below θ

The Big Idea

📖Policy Evaluation

The task of computing the state-value function VπV^\pi for a given policy π\pi. Also called “prediction” because we are predicting the expected return from each state under that policy.

Imagine you want to know how valuable each state is, but you have no idea where to start. So you guess: set all values to zero. Now ask yourself, “If my values were correct, what would the Bellman equation tell me?” The Bellman equation combines immediate rewards with future values to give you a new, better estimate.

Repeat this process. Each round, your estimates become more accurate. Eventually, they stop changing because you have found the values that exactly satisfy the Bellman equation. Those are the true values under policy π\pi.

This process is called iterative policy evaluation, and it is our first Dynamic Programming algorithm.

What is Dynamic Programming?

ℹ️Note

Dynamic Programming (DP) refers to a collection of algorithms that compute optimal policies given a perfect model of the environment. The term comes from Richard Bellman, who developed these techniques in the 1950s.

The “dynamic” refers to the sequential, multi-stage nature of the decision problem. The “programming” means optimization in the mathematical sense, not computer programming.

DP methods work by using the Bellman equations to iteratively improve value estimates. They matter for three reasons:

  1. They are exact: When we know the MDP, DP finds the true values
  2. They are foundational: TD learning, Q-learning, and other RL methods are approximations of DP ideas
  3. They build intuition: Seeing DP work clearly prepares you for more complex methods

Chapter Overview

Iterative Policy Evaluation
The algorithm: initialize, sweep, repeat until convergence
Convergence and Stopping
Why it converges, when to stop, and computational costs

A Preview: The Update Rule

The heart of policy evaluation is the Bellman expectation backup. In plain terms: the new estimate for a state is the expected immediate reward plus the discounted value of wherever you land next, averaged over the actions the policy might take.

∑Mathematical Details

Vk+1(s)=∑aπ(a∣s)[R(s,a)+γ∑s′P(s′∣s,a)Vk(s′)]V_{k+1}(s) = \sum_a \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_k(s') \right]

The outer sum averages over actions according to π\pi; the inner sum averages over next states according to the transition model.

We apply this update to every state, creating a “sweep” through the state space. After enough sweeps, the values converge to VπV^\pi.

Key Questions We Will Answer

  • How does the iterative algorithm work, step by step?
  • Why is convergence guaranteed? What property ensures we reach the right answer?
  • How do we choose when to stop? What is a good threshold?
  • What is the computational cost, and how does it scale with the MDP size?

The Path Ahead

Once we can evaluate any policy, the natural next question is: How do we find a better policy? That is the subject of the next chapter on Policy Improvement, where value functions become the tool for constructing better and better policies until we reach the optimum.

Check Your Understanding

Check your understanding
1. What does policy evaluation compute?
2. Why can we initialize the values to anything (zeros, random numbers, old estimates) and still get the right answer?
3. The algorithm stops when the largest value change in a sweep falls below a threshold θ. What does that actually tell you?
4. In-place policy evaluation reuses freshly updated values within the same sweep instead of keeping a separate old-values array. What happens to convergence?
5. What does Dynamic Programming require that model-free RL methods do not?

Key Takeaways

  1. Policy evaluation computes the value of a fixed policy
    Given a policy π and the full MDP model, it finds V(s) for every state — the "prediction" problem.
  2. The algorithm is: initialize, sweep, repeat
    Apply the Bellman expectation backup to every state, over and over, until the values settle.
  3. Convergence is guaranteed from any starting point
    The Bellman operator is a contraction, so repeated application always reaches the unique fixed point.
  4. Stop when the largest change falls below θ
    Small per-sweep changes mean you are near the fixed point; the residual error is bounded in terms of γ and θ.
  5. This is the first step toward optimal policies
    Evaluation tells you how good a policy is; the next chapter uses that to make policies better.
Next ChapterPolicy Improvement→