Policy Evaluation: How Good Is This Policy?

The question

Policy evaluation answers one thing: for a fixed policy, what is its state-value function — the expected discounted return from each state if you follow that policy forever? This is the prediction problem. We are not asking whether the policy is good in some absolute sense; we are computing the exact number that says how much total reward each starting state is worth under it.

The Bellman expectation equation says the value of a state equals the expected immediate reward plus the discount factor gamma times the expected value of the next state. That is one equation per state — a big system of linear equations. You could solve it directly with linear algebra, but for anything beyond a handful of states that is impractical. Instead we iterate.

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

The Bellman expectation equation: a state's value under policy pi equals the expected immediate reward plus the discounted value of the next state.

Iterative policy evaluation

Iterative policy evaluation starts from any guess (often all zeros) and repeatedly applies the Bellman backup for the policy. Each pass over all states is a sweep. The trick is bootstrapping: each new value is built from the current estimates of neighbouring states, not from a true return. The estimates start wrong, but every sweep shrinks the error.

# Iterative policy evaluation for a fixed policy pi
# Inputs: states S, policy pi(a|s), model p(s', r | s, a), discount gamma
V = {s: 0.0 for s in S}            # initial guess
repeat:
    delta = 0
    for s in S:
        v_old = V[s]
        # full backup: expectation over actions and next states
        V[s] = sum(
            pi(a, s) * sum(
                p(s_next, r, s, a) * (r + gamma * V[s_next])
                for (s_next, r) in transitions(s, a)
            )
            for a in actions(s)
        )
        delta = max(delta, abs(v_old - V[s]))
until delta < theta            # stop when no value moves much
return V                       # approx v_pi

One backup per state, repeated until values stop moving (theta is a small tolerance).

In-place or two-array?

There are two ways to run a sweep. The textbook 'synchronous' version keeps two copies of the value array — read from the old, write to the new — so every state in a sweep is updated from the same snapshot. The in-place version overwrites a single array as it goes, so later states in the sweep already see the freshly updated earlier ones. In-place uses half the memory and usually converges faster, because good information propagates within a single sweep instead of waiting for the next one.

When to stop

In theory the values converge to the true value function only in the limit of infinitely many sweeps. In practice you stop when the largest change in any state across a full sweep drops below a small threshold. The remarkable thing is that this iteration is guaranteed to converge to a single, unique answer no matter where you start — a fact that comes from the contraction property we will meet in guide 4.

\Delta=\max_{s}\,\bigl|v_{k+1}(s)-v_k(s)\bigr|<\theta

Stop the sweeps when the largest value change in any state falls below the small tolerance theta.