Policy Evaluation

Why Does This Exist?

In reinforcement learning, an agent cannot systematically improve its behavior without knowing the exact long-term return its current behavior produces. If an agent modifies its decisions arbitrarily without a reliable baseline, it risks choosing actions that yield immediate gratification but precipitate catastrophic long-term failure. Policy evaluation solves this foundational problem by computing the state-value function $V^\pi(s)$—the expected discounted cumulative reward from every state $s$ when following a specified policy $\pi$.

Without policy evaluation, the foundational paradigm of Generalized Policy Iteration (GPI) breaks down. An agent must evaluate where it currently stands before it can identify which actions are genuinely superior.

Policy evaluation occupies a specific theoretical niche distinguishable from neighboring techniques:

• Versus Value Iteration: Value iteration computes the optimal value function $V^*(s)$ directly by embedding a greedy policy maximization operator ($\max_a$) into every single update sweep. Policy evaluation, by contrast, evaluates an arbitrary, fixed policy $\pi$ using the expectation over actions $\sum_a \pi(a \mid s)$, decoupling evaluation from policy improvement.
• Versus Monte Carlo Evaluation: Monte Carlo methods estimate values by simulating sample trajectories until terminal episodes, requiring zero knowledge of environment transition dynamics but suffering from high sampling variance and failing on non-terminating horizons. Policy evaluation leverages full dynamic programming models to compute exact expectations across all branching paths in single-step sweeps with zero sample variance.
• Versus Temporal Difference (TD) Learning: TD methods update online from single observed state-action transitions $(s, a, r, s')$, whereas dynamic programming policy evaluation performs an exhaustive, full-width expectation backup across all possible transitions simultaneously.

Think of It Like This

How It Actually Works

The Bellman Expectation Backup and Contraction Mapping

Iterative policy evaluation operates on a Markov Decision Process (MDP) defined by the tuple $(\mathcal{S}, \mathcal{A}, p, \gamma)$, where $\mathcal{S}$ is the finite set of states, $\mathcal{A}$ is the action space, $p(s', r \mid s, a)$ represents the environment dynamics, and $\gamma \in [0, 1)$ is the discount factor.

For a fixed policy $\pi(a \mid s) = \mathbb{P}(A_t = a \mid S_t = s)$, the true state-value function $V^\pi$ satisfies the Bellman expectation equation:

When the state space is large, solving this system of $|\mathcal{S}|$ linear equations directly via matrix inversion has time complexity $\mathcal{O}(|\mathcal{S}|^3)$, which quickly becomes prohibitive. Iterative policy evaluation turns this recursive equation into an iterative update rule. Starting with an arbitrary initial value vector $V_0$ (with $V_0(\text{terminal}) = 0$), the algorithm computes successive approximations:

Convergence is guaranteed by the Banach Fixed-Point Theorem. Defining the Bellman expectation operator $T^\pi: \mathbb{R}^{|\mathcal{S}|} \to \mathbb{R}^{|\mathcal{S}|}$ as:

Under the supremum (infinity) norm $\|V\|_\infty = \max_{s \in \mathcal{S}} |V(s)|$, the operator satisfies:

Because $\gamma < 1$, $T^\pi$ is a strict $\gamma$-contraction mapping on the complete metric space $\mathbb{R}^{|\mathcal{S}|}$. This mathematical property guarantees:

1. $T^\pi$ has a single, unique fixed point satisfying $T^\pi V^\pi = V^\pi$.
2. The sequence generated by $V_{k+1} = T^\pi V_k$ converges geometrically at rate $\mathcal{O}(\gamma^k)$ to $V^\pi$ from any arbitrary initialization $V_0$.

The iteration halts when the maximum change across all states between consecutive sweeps is strictly bounded by a small threshold $\theta > 0$:

By contraction properties, terminating at $\Delta < \theta$ guarantees that the distance between the current estimate and the true value function satisfies:

Worked numerical example

Consider a 3-state linear Markov chain: $\mathcal{S} = \{s_1, s_2, s_3\}$ leading to an absorbing terminal state $s_T$ where $V(s_T) \equiv 0$. The discount factor is $\gamma = 0.9$, and the stopping threshold is $\theta = 0.05$.

Under policy $\pi$, the agent transitions deterministically to the right:

• From $s_1$, the agent steps to $s_2$ with reward $r = 0$.
• From $s_2$, the agent steps to $s_3$ with reward $r = 0$.
• From $s_3$, the agent steps into $s_T$ with reward $r = +10.0$.

Initialize all state values to zero at $k = 0$:

Iteration 1 ($k = 1$):

• $V_1(s_1) = 0 + 0.9 \cdot V_0(s_2) = 0 + 0.9(0.0) = 0.0$
• $V_1(s_2) = 0 + 0.9 \cdot V_0(s_3) = 0 + 0.9(0.0) = 0.0$
• $V_1(s_3) = 10.0 + 0.9 \cdot V_0(s_T) = 10.0 + 0.9(0.0) = 10.0$

Compute the maximum update delta:

Since $\Delta_1 = 10.0 \ge \theta$, the algorithm executes sweep 2 with value vector $V_1 = [0.0, 0.0, 10.0]$.

Iteration 2 ($k = 2$):

• $V_2(s_1) = 0 + 0.9 \cdot V_1(s_2) = 0 + 0.9(0.0) = 0.0$
• $V_2(s_2) = 0 + 0.9 \cdot V_1(s_3) = 0 + 0.9(10.0) = 9.0$
• $V_2(s_3) = 10.0 + 0.9 \cdot V_1(s_T) = 10.0 + 0.9(0.0) = 10.0$

Compute the maximum update delta:

Since $\Delta_2 = 9.0 \ge \theta$, values continue to propagate upstream with value vector $V_2 = [0.0, 9.0, 10.0]$.

Iteration 3 ($k = 3$) and Final Convergence:

• $V_3(s_1) = 0 + 0.9 \cdot V_2(s_2) = 0 + 0.9(9.0) = 8.1$
• $V_3(s_2) = 0 + 0.9 \cdot V_2(s_3) = 0 + 0.9(10.0) = 9.0$
• $V_3(s_3) = 10.0 + 0.9 \cdot V_2(s_T) = 10.0 + 0.9(0.0) = 10.0$

On iteration 4 ($k = 4$), evaluating all states yields identical values $V_4 = [8.1, 9.0, 10.0]$, producing $\Delta_4 = 0.0 < \theta$. The iteration terminates at the exact analytical fixed point $V^\pi = [8.1, 9.0, 10.0]$.

Code

1from typing import List, Tuple2
3def iterative_policy_evaluation(4    grid_size: Tuple[int, int] = (4, 4),5    terminals: List[Tuple[int, int]] = [(0, 0), (3, 3)],6    gamma: float = 1.0,7    theta: float = 1e-4,8) -> Tuple[List[List[float]], int]:9    """Computes state values for an equiprobable random policy on a Gridworld.10    11    Args:12        grid_size: Dimensions of the grid (rows, columns).13        terminals: List of coordinate tuples marking terminal states.14        gamma: Discount factor in [0, 1].15        theta: Precision threshold for stopping condition.16        17    Returns:18        Tuple containing the converged 2D value grid and the iteration count.19    """20    rows, cols = grid_size21    # Initialize state values to zero22    V: List[List[float]] = [[0.0 for _ in range(cols)] for _ in range(rows)]23    24    # Actions: Up, Down, Left, Right25    actions: List[Tuple[int, int]] = [(-1, 0), (1, 0), (0, -1), (0, 1)]26    prob_a: float = 1.0 / len(actions)27    iterations: int = 028
29    while True:30        delta: float = 0.031        # Create a copy for synchronous value updates32        new_V: List[List[float]] = [row[:] for row in V]33
34        for r in range(rows):35            for c in range(cols):36                if (r, c) in terminals:37                    continue38
39                v_expected: float = 0.040                for dr, dc in actions:41                    nr, nc = r + dr, c + dc42                    # Wall bounce: staying in place if move goes off grid43                    if not (0 <= nr < rows and 0 <= nc < cols):44                        nr, nc = r, c45                    reward: float = -1.046                    v_expected += prob_a * (reward + gamma * V[nr][nc])47
48                new_V[r][c] = v_expected49                delta = max(delta, abs(new_V[r][c] - V[r][c]))50
51        V = new_V52        iterations += 153
54        if delta < theta:55            break56
57    return V, iterations58
59
60if __name__ == "__main__":61    converged_V, num_sweeps = iterative_policy_evaluation()62    print(f"Converged after {num_sweeps} sweeps:")63    for row in converged_V:64        print([round(val, 1) for val in row])65
66    # Expected output:67    # Converged after 173 sweeps:68    # [0.0, -14.0, -20.0, -22.0]69    # [-14.0, -18.0, -20.0, -20.0]70    # [-20.0, -20.0, -18.0, -14.0]71    # [-22.0, -20.0, -14.0, 0.0]

Watch Out For

The Quick Version

• Policy evaluation computes the true state-value function $V^\pi(s)$ for an unvarying policy $\pi$ without modifying agent decisions.
• It iteratively applies the Bellman expectation backup operator across all states: $V_{k+1}(s) \leftarrow \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)[r + \gamma V_k(s')]$.
• Because the Bellman expectation operator is a contraction mapping in the infinity norm, convergence to a unique fixed point $V^\pi$ is guaranteed for any initial values when $\gamma < 1$.
• The sweep loop terminates once the maximum single-state variation $\Delta = \max_s |V_{k+1}(s) - V_k(s)|$ falls below a specified tolerance threshold $\theta$.

What to Read Next

• Dynamic Programming in RL
• Policy Improvement
• Policy Iteration