Policy Evaluation

Given a fixed policy, policy evaluation scores every state by the return that policy earns from there, sweeping Bellman backups until the numbers stop moving.

Why Does This Exist?

You cannot improve a policy you have not measured. If you change actions without knowing what the current ones earn, you might trade a slow starter for a fast loser. Policy evaluation is the measuring step: for a fixed policy it computes the state value function, the expected discounted return from every state.

This is the prediction half of control. Dynamic programming splits control into two jobs, and this page covers the first. Its sibling, policy improvement, covers the second: acting greedily on the values found here. Alternating the two gives policy iteration.

The one idea you need first

A state value $V^\pi(s)$ is the expected return from state $s$ while following policy $\pi$ . Return means discounted cumulative reward, $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$ , where the discount factor $\gamma$ in $[0, 1)$ says a reward tomorrow is worth less than one today. The Bellman equations page writes this expectation recursively; here we turn that recursion into an algorithm.

Think of It Like This

Grading a fixed bus timetable

A transport inspector must grade a bus timetable she cannot change. Every bus runs its posted route, and she rides each one, noting fares collected now plus the fares the same timetable will collect later, discounted because late money counts less.

Her first pass records only fares collected today. Her second pass adds the discounted fares those same buses collect tomorrow. Each pass reaches one stop further back along the route. The adjustments shrink every pass, and when no stop's grade moves by more than a cent, she stops. She never changed a single departure. She just knows exactly what the timetable is worth from every stop.

The analogy stops where models stop: it assumes she knows every fare and transfer probability exactly. Real agents usually must learn them from samples.

How It Actually Works

For a fixed policy $\pi(a \mid s)$ , the true values satisfy the Bellman expectation equation. The symbol $\pi(a \mid s)$ is the probability of taking action $a$ in state $s$ , $p(s', r \mid s, a)$ is the probability of landing in $s'$ with reward $r$ , and $\gamma$ is the discount factor:

V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \, [r + \gamma V^\pi(s')]

In words: average over the actions your policy takes, then over everything the environment might do, of immediate reward plus discounted successor value. Solving this linear system directly costs $O(|S|^3)$ , so we iterate instead. Start anywhere, $V_0$ arbitrary with terminal states at zero, and sweep:

V_{k+1}(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \, [r + \gamma V_k(s')]

The backup is a contraction with factor $\gamma$ : the worst error shrinks by at least $\gamma$ each sweep, so the sequence converges to the unique $V^\pi$ from any start. Stop when the largest single-state move falls below a small threshold $\theta$ :

\Delta = \max_s |V_{k+1}(s) - V_k(s)| < \theta

The final error is bounded by $\gamma \theta / (1 - \gamma)$ , so pick $\theta$ with that multiplier in mind.

Worked example

Three stops in a line lead to a terminal: $s_1 \to s_2$ paying $0$ , $s_2 \to s_3$ paying $0$ , $s_3 \to$ terminal paying $10$ . Discount $\gamma = 0.9$ , threshold $\theta = 0.05$ . Start at $V_0 = [0.0, 0.0, 0.0]$ .

Sweep 1 uses only immediate rewards, so $V_1 = [0.0, 0.0, 10.0]$ and $\Delta_1 = 10.0$ . Only the stop beside the payout knows anything yet.

Sweep 2 backs the payout one stop further: $V_2(s_2) = 0 + 0.9 \times 10.0 = 9.0$ , giving $V_2 = [0.0, 9.0, 10.0]$ and $\Delta_2 = 9.0$ .

Sweep 3 reaches the far stop: $V_3(s_1) = 0 + 0.9 \times 9.0 = 8.1$ , giving $V_3 = [8.1, 9.0, 10.0]$ . Sweep 4 changes nothing, so $\Delta_4 = 0.0 < \theta$ and we stop at $V^\pi = [8.1, 9.0, 10.0]$ . One sweep per stop of distance: that is the rhythm to remember.

Code

This snippet runs the worked example with plain sweeps, so you can watch the values propagate one stop per pass.

1def evaluate_chain(gamma: float = 0.9, theta: float = 0.05):2    """Bellman sweeps on s1 -> s2 -> s3 -> terminal(+10)."""3    values = [0.0, 0.0, 0.0]  # [V(s1), V(s2), V(s3)]4    rewards = [0.0, 0.0, 10.0]5    successors = [1, 2, None]6    sweep = 07    while True:8        sweep += 19        delta = 0.010        nxt = values[:]11        for i in range(3):12            target = rewards[i] if successors[i] is None else rewards[i] + gamma * values[successors[i]]13            delta = max(delta, abs(target - values[i]))14            nxt[i] = target15        values = nxt16        if delta < theta:17            break18    return sweep, [round(v, 1) for v in values]19
20
21print(evaluate_chain())

Watch Out For

Stopping before distant rewards arrive

Each sweep carries reward information back exactly one transition. With a loose threshold the loop quits while far states still read zero, and the next improvement step then acts on ignorance.

Symptom: states far from any reward keep value zero while near ones look settled. Fix: watch $\Delta$ per sweep and confirm it decayed geometrically near rate $\gamma$ before trusting the values. Inside policy iteration you can stop early on purpose, but then do it knowingly, not by accident.

Setting the threshold without the gamma multiplier

A threshold of $0.01$ sounds precise, but the true error can be $\gamma \theta / (1 - \gamma)$ , which is $0.09$ when $\gamma = 0.9$ and $0.99$ when $\gamma = 0.99$ .

Symptom: greedy actions flip between runs that differ only in $\gamma$ . Fix: divide your error budget by that multiplier first, then set $\theta$ . High discount demands a far tighter threshold for the same accuracy.

The Quick Version

Policy evaluation computes $V^\pi$ , the expected discounted return of a fixed policy from every state.
It sweeps the Bellman expectation backup until the largest single-state change drops below $\theta$ .
The backup is a contraction with factor $\gamma$ , so convergence from any start is guaranteed.
Reward news travels one transition per sweep, as 0.0 became 8.1, 9.0 and 10.0 across three passes here.
True error can reach $\gamma \theta / (1 - \gamma)$ , so tighten $\theta$ as $\gamma$ nears 1.