Iterative Policy Evaluation

For a fixed policy $\pi$ in a Markov Decision Process with state set $\mathcal{S}$, action set $\mathcal{A}$, transition dynamics $p(s', r \mid s, a)$, and discount factor $\gamma \in [0, 1)$, the state-value function is defined as the expected discounted return from state $s$ under $\pi$:

This expectation satisfies the Bellman expectation equation, a recursive relationship connecting $v_\pi(s)$ to the values of successor states:

If $\mathcal{S}$ has $n$ states, this is a system of $n$ linear equations in $n$ unknowns $\{v_\pi(s)\}$. It can, in principle, be solved directly using linear algebra, but this requires forming and inverting an $n \times n$ matrix, an $O(n^3)$ operation that is impractical for large state spaces. Iterative Policy Evaluation instead treats the right-hand side of the Bellman equation as an update rule rather than a system to solve algebraically. Define the Bellman expectation backup operator $T^\pi$ acting on any candidate value function $v$:

Starting from an arbitrary initial guess $v_0$ (commonly all zeros), the algorithm computes the sequence

for every state simultaneously, and this sequence provably converges to $v_\pi$, the unique fixed point of $T^\pi$, as $k \to \infty$. In practice the iteration halts once successive value functions differ by less than a small threshold $\theta$.

The algorithm maintains a table of value estimates, one per state, and repeatedly sweeps through all states applying the backup. There are two standard implementation styles.

Two-array (synchronous) version. Keep an old array $V$ and compute a new array $V'$ entirely from $V$, then swap. This exactly matches the mathematical definition $v_{k+1} = T^\pi v_k$, since no update within a sweep uses another update from the same sweep.

In-place (asynchronous) version. Update the single array $V$ directly, so later updates within the same sweep already see newer values. This is not the textbook operator applied literally, but it still converges to $v_\pi$ under the same conditions, usually faster in practice, and uses half the memory. ```text ALGORITHM IterativePolicyEvaluation(pi, MDP, theta, gamma) Input: pi -- policy: pi(a | s) for all s, a MDP -- transition model p(s', r | s, a), state set S, action set A(s) theta -- small positive threshold for convergence check gamma -- discount factor in [0, 1) Output: V -- array approximating v_pi(s) for all s Initialize V(s) <- 0 for all s in S // any finite initialization works Initialize V(terminal) <- 0 for all terminal states, held fixed loop Delta <- 0 for each s in S (non-terminal): v_old <- V(s) // Bellman expectation backup new_value <- 0 for each a in A(s): q_sa <- 0 for each (s', r) reachable from (s, a): q_sa <- q_sa + p(s', r | s, a) (r + gamma V(s')) new_value <- new_value + pi(a | s) q_sa V(s) <- new_value // in-place: uses fresh V(s') if s' already updated Delta <- max(Delta, |v_old - V(s)|) if Delta < theta: break return V ``` For the strict two-array version, replace the line `V(s) <- new_value` with `V_new(s) <- new_value`, use `V(s')` from the old* array everywhere in the inner loops, and swap `V <- V_new` at the end of each sweep. The following diagram shows one backup at a single state: the value of $s$ is updated as a weighted average over actions (policy probabilities), and over each action's possible successor states (transition probabilities), pulling in the discounted value already stored for each successor.

Per-sweep time complexity. For each of the $n = |\mathcal{S}|$ states, the algorithm loops over all actions available in that state, and for each action loops over all possible successor states and rewards. If $|\mathcal{A}|$ bounds the number of actions per state and $n$ bounds the number of possible successors per action (worst case, a dense transition model), one sweep costs

time. In sparse MDPs, where each action has only $b$ possible successors (a branching factor much smaller than $n$), one sweep costs $O(n \cdot |\mathcal{A}| \cdot b)$, which is the practically relevant bound for most structured environments like gridworlds.

Space complexity. The two-array version needs $O(n)$ for the current values, $O(n)$ for the new values, plus $O(n \cdot |\mathcal{A}| \cdot b)$ to store the transition model itself (which is usually given, not built by the algorithm). The in-place version needs only a single $O(n)$ array for values, halving the value-storage cost.

Number of sweeps to converge. This is the subtler question, addressed by a contraction-mapping argument. Define the max-norm distance between two value functions as $\lVert u - v \rVert_\infty = \max_s |u(s) - v(s)|$. The key claim is that the Bellman expectation operator $T^\pi$ is a $\gamma$-contraction in this norm:

Proof sketch. For any state $s$,

since the reward terms cancel identically (they do not depend on $u$ or $v$). Taking absolute values and using the fact that $\pi(a\mid s)$ and $p(s'\mid s,a)$ are nonnegative and each sum to $1$,

because each successor's deviation is bounded by the max deviation over all states, and the weights average to at most $1$. Taking the max over $s$ gives the contraction inequality. $\blacksquare$ Because $\gamma < 1$ and the space of bounded value functions with the max-norm is complete, the Banach fixed-point theorem guarantees: 1. $T^\pi$ has a unique fixed point — and one can check directly that $v_\pi$ satisfies $T^\pi v_\pi = v_\pi$, so that fixed point must be $v_\pi$ itself; 2. iterating $v_{k+1} = T^\pi v_k$ from any starting point converges to $v_\pi$; 3. the convergence rate is geometric: $\lVert v_k - v_\pi \rVert_\infty \le \gamma^k \lVert v_0 - v_\pi \rVert_\infty$. This last bound is what justifies stopping early: once $\lVert v_{k+1} - v_k \rVert_\infty < \theta$, the remaining error is bounded by roughly $\frac{\gamma}{1-\gamma}\theta$, so a small threshold gives a provably small final error, not just an ad hoc heuristic stopping point.

Honest tradeoffs. The geometric rate constant is $\gamma$ itself: if $\gamma$ is close to $1$ (long-horizon problems), convergence can require very many sweeps, since $\gamma^k$ shrinks slowly. Exact linear-algebra solution avoids this issue entirely but costs $O(n^3)$ up front, which is worse than iteration whenever $n$ is large and only moderate precision is needed. The in-place variant is not literally applying $T^\pi$ each sweep (it is a mix of old and new estimates within one pass), yet it remains provably convergent under the same discount condition and is almost always faster in wall-clock terms because information propagates within a sweep rather than only across sweeps.

Consider a tiny $1 \times 4$ corridor gridworld with states $\{1, 2, 3\}$ and a terminal state $T$ to the right of state $3$ (state $0$, off the left edge, does not exist — state $1$'s left move bounces back to state $1$). The policy is fixed: always move right, deterministically. Reward is $-1$ per step until reaching the terminal state, where the episode ends. Discount $\gamma = 0.9$. Bellman expectation equations under this deterministic policy simplify to:

since $v_\pi(T) = 0$ by definition of terminal states. Tracing in-place iterative policy evaluation, sweeping states in order $1, 2, 3$ each pass, initialized at $V_0 = (0,0,0)$:

Notice the values stabilize after sweep 3 in this case (state 3 is correct after one sweep since it is one step from termination, state 2 needs two sweeps, state 1 needs three), matching the intuition that value information propagates backward from the terminal state by roughly one state per sweep in a chain-like MDP with in-place updates in the favorable sweep order. Check against the exact solution by back-substitution: $v_\pi(3) = -1$, $v_\pi(2) = -1 + 0.9(-1) = -1.9$, $v_\pi(1) = -1 + 0.9(-1.9) = -2.71$. The iteration has converged to the exact answer, confirming the contraction argument: with a deterministic policy and this small chain, convergence is exact after enough sweeps for information to propagate the full length of the chain, here 3 sweeps because sweeps go in the same direction as value propagation. If instead states had been swept in the order $3, 2, 1$, in-place updates would converge even faster (in a single sweep for this deterministic chain), illustrating why sweep order matters for in-place asynchronous updates even though the two-array synchronous version is order-independent by construction.

Iterative Policy Evaluation descends directly from dynamic programming, a general method for solving multistage decision problems by recursive decomposition, formalized for stochastic control problems in the 1950s.

Iterative Policy Evaluation is rarely deployed by itself in large-scale industrial systems, because it requires a fully known transition model $p(s', r \mid s, a)$, which most real-world environments do not provide explicitly. Its true importance is pedagogical and structural: it is the cleanest instance of the prediction problem in reinforcement learning, and every model-free prediction method — Temporal-Difference Learning, Monte Carlo policy evaluation, and eventually deep value networks — can be understood as an attempt to approximate the same Bellman expectation backup using samples instead of a known model. Where exact transition models are available — inventory management, queueing systems, small robotic navigation grids, board games with known rules, and operations-research scheduling problems — iterative policy evaluation (or its close relative, direct linear solution) is used as a subroutine inside Policy Iteration to evaluate candidate policies before improving them. It also underlies the evaluation step used conceptually inside AlphaZero-style planning, where a learned or simulated model stands in for the true transition function, and inside model-based reinforcement learning pipelines that alternate between learning a model and dynamic-programming over it.

Ask the tutor: How does truncating Iterative Policy Evaluation to a single sweep turn it into Value Iteration?