9 Policy Evaluation

Core idea. Policy evaluation asks a precise mathematical question: if the agent follows a fixed policy \(\pi\), what is the long-run value of each state? Once the policy is fixed, the control problem disappears. The Markov decision process becomes a Markov reward process, and the value function is the unique fixed point of a linear Bellman operator.

For a finite discounted MDP, policy evaluation is the problem of computing

\[ V^\pi(s)=\mathbb E_\pi\left[\sum_{t=0}^\infty \gamma^t R_{t+1}\mid S_0=s\right] \]

from the Bellman expectation equation

\[ V^\pi=r_\pi+\gamma P_\pi V^\pi. \]

This chapter explains policy evaluation as linear algebra, fixed-point iteration, conditional expectation, simulation, and statistical estimation.

9.1 Learning goals

After reading this chapter, students should be able to:

state the policy evaluation problem for a finite discounted MDP;
construct the policy-induced transition matrix \(P_\pi\) and reward vector \(r_\pi\);
solve policy evaluation exactly by the linear system \((I-\gamma P_\pi)V^\pi=r_\pi\);
prove that the Bellman expectation operator \(T^\pi\) is a contraction under the sup norm;
derive convergence and stopping bounds for iterative policy evaluation;
compare direct linear solution, Jacobi iteration, Gauss-Seidel iteration, and asynchronous updates;
interpret Monte Carlo and temporal-difference evaluation as sample-based approximations to the Bellman equation;
connect policy evaluation with statistical estimation and uncertainty;
use AI tools to check Bellman equations, debug algorithms, and explain assumptions.

9.2 6.1 The policy evaluation problem

Let

\[ \mathcal M=(\mathcal S,\mathcal A,P,r,\gamma) \]

be a finite discounted Markov decision process. Here \(\mathcal S\) is the state space, \(\mathcal A(s)\) is the set of admissible actions in state \(s\), \(P(s'\mid s,a)\) is the transition law, \(r(s,a)\) is the expected one-step reward, and \(0\leq \gamma<1\) is the discount factor.

A stationary randomized policy is a collection of probability distributions

\[ \pi(\cdot\mid s)\in \Delta(\mathcal A(s)), \]

where

\[ \pi(a\mid s)\geq 0, \qquad \sum_{a\in\mathcal A(s)}\pi(a\mid s)=1. \]

Policy evaluation asks for the value of following this fixed policy. The state-value function is

\[ V^\pi(s)=\mathbb E_\pi[G_0\mid S_0=s], \]

where

\[ G_0=R_1+\gamma R_2+\gamma^2R_3+\cdots. \]

The key phrase is fixed policy. We are not yet trying to improve the policy. We are only measuring it.

Policy evaluation is the mathematical bridge between Markov reward processes and control. It is also the inner subroutine of policy iteration, actor-critic methods, approximate dynamic programming, and many modern reinforcement learning algorithms.

9.3 6.2 From an MDP and a policy to an MRP

Once the policy \(\pi\) is fixed, the agent’s action randomness is absorbed into the transition and reward model. Define the policy-induced transition matrix

\[ P_\pi(s'\mid s) = \sum_{a\in\mathcal A(s)}\pi(a\mid s)P(s'\mid s,a) \]

and the policy-induced expected reward

\[ r_\pi(s) = \sum_{a\in\mathcal A(s)}\pi(a\mid s)r(s,a). \]

Then the controlled process under policy \(\pi\) becomes the Markov reward process

\[ (\mathcal S,P_\pi,r_\pi,\gamma). \]

This reduction is one of the most important mathematical simplifications in reinforcement learning:

\[ \boxed{\text{MDP} + \text{fixed policy }\pi \quad \Longrightarrow \quad \text{MRP}.} \]

For a deterministic policy, \(\pi(s)\) selects one action in each state, so

\[ P_\pi(s'\mid s)=P(s'\mid s,\pi(s)), \qquad r_\pi(s)=r(s,\pi(s)). \]

For a randomized policy, each row of \(P_\pi\) is a convex combination of action-specific transition rows.

9.4 6.3 Running example: a study-planning policy

We continue the three-state study-planning MDP:

\[ \mathcal S=\{\text{Review},\text{Practice},\text{Mastery}\}. \]

The two actions are:

\(C\): Consolidate, a safer action that reinforces current understanding;
\(H\): Challenge, a more aggressive action that may move the learner faster but can be unstable.

The transition matrices are

\[ P^{C}= \begin{pmatrix} 0.70 & 0.25 & 0.05\\ 0.15 & 0.70 & 0.15\\ 0.05 & 0.10 & 0.85 \end{pmatrix}, \qquad P^{H}= \begin{pmatrix} 0.45 & 0.45 & 0.10\\ 0.20 & 0.40 & 0.40\\ 0.10 & 0.20 & 0.70 \end{pmatrix}. \]

The reward vectors are

\[ r^{C}=\begin{pmatrix}1\\2\\5\end{pmatrix}, \qquad r^{H}=\begin{pmatrix}0\\4\\6\end{pmatrix}. \]

Consider the randomized policy

\[ \pi(H\mid \text{Review})=0.20, \qquad \pi(H\mid \text{Practice})=0.70, \qquad \pi(H\mid \text{Mastery})=0.90. \]

Equivalently,

\[ \pi(C\mid s)=1-\pi(H\mid s). \]

For each state \(s\), the induced row of \(P_\pi\) is

\[ P_\pi(\cdot\mid s) = (1-\pi(H\mid s))P^C(\cdot\mid s)+\pi(H\mid s)P^H(\cdot\mid s), \]

and the induced reward is

\[ r_\pi(s) = (1-\pi(H\mid s))r^C(s)+\pi(H\mid s)r^H(s). \]

9.4.1 Python example: constructing \(P_\pi\) and \(r_\pi\)

import numpy as np
import pandas as pd

states = ["Review", "Practice", "Mastery"]

P_C = np.array([
    [0.70, 0.25, 0.05],
    [0.15, 0.70, 0.15],
    [0.05, 0.10, 0.85]
])

P_H = np.array([
    [0.45, 0.45, 0.10],
    [0.20, 0.40, 0.40],
    [0.10, 0.20, 0.70]
])

r_C = np.array([1.0, 2.0, 5.0])
r_H = np.array([0.0, 4.0, 6.0])

p_H = np.array([0.20, 0.70, 0.90])
P_pi = (1 - p_H)[:, None] * P_C + p_H[:, None] * P_H
r_pi = (1 - p_H) * r_C + p_H * r_H

pd.DataFrame(P_pi, index=states, columns=states)

	Review	Practice	Mastery
Review	0.650	0.29	0.060
Practice	0.185	0.49	0.325
Mastery	0.095	0.19	0.715

pd.Series(r_pi, index=states, name="r_pi")

Review      0.8
Practice    3.4
Mastery     5.9
Name: r_pi, dtype: float64

9.5 6.4 Exact policy evaluation by linear algebra

The Bellman expectation equation for a fixed policy is

\[ V^\pi(s)=r_\pi(s)+\gamma\sum_{s'\in\mathcal S}P_\pi(s'\mid s)V^\pi(s'). \]

In vector form,

\[ V^\pi=r_\pi+\gamma P_\pi V^\pi. \]

Rearranging gives the linear system

\[ (I-\gamma P_\pi)V^\pi=r_\pi. \]

Because \(P_\pi\) is stochastic, its spectral radius satisfies

\[ \rho(P_\pi)\leq 1. \]

Since \(0\leq \gamma<1\),

\[ \rho(\gamma P_\pi)<1. \]

Therefore \(I-\gamma P_\pi\) is invertible and

\[ V^\pi=(I-\gamma P_\pi)^{-1}r_\pi. \]

The inverse also has the Neumann-series representation

\[ (I-\gamma P_\pi)^{-1} = \sum_{t=0}^\infty \gamma^t P_\pi^t. \]

Thus

\[ V^\pi = \sum_{t=0}^\infty \gamma^t P_\pi^t r_\pi. \]

This formula has a direct probabilistic meaning: \(P_\pi^t r_\pi\) is the expected reward \(t\) steps in the future under policy \(\pi\), and \(\gamma^t\) discounts that future contribution.

9.5.1 Python example: exact policy evaluation

gamma = 0.90
I = np.eye(len(states))
V_exact = np.linalg.solve(I - gamma * P_pi, r_pi)

pd.Series(V_exact, index=states, name="V_exact")

Review      30.599306
Practice    36.976881
Mastery     41.624929
Name: V_exact, dtype: float64

The values are large because \(\gamma=0.90\) means the agent cares about many future rewards. The effective horizon is roughly

\[ \frac{1}{1-\gamma}=10. \]

9.5.2 Interactive: exact values for different policies and discount factors

The interactive below shows how \(V^\pi\) changes when the policy becomes more likely to choose the Challenge action and when the discount factor changes.

9.6 6.5 Bellman operator viewpoint

Define the Bellman expectation operator

\[ (T^\pi V)(s)=r_\pi(s)+\gamma\sum_{s'}P_\pi(s'\mid s)V(s'). \]

Then the policy evaluation equation is simply

\[ V^\pi=T^\pi V^\pi. \]

That is, \(V^\pi\) is a fixed point of \(T^\pi\).

For any two value functions \(V,W\in\mathbb R^{|\mathcal S|}\),

\[ \begin{aligned} |(T^\pi V)(s)-(T^\pi W)(s)| &=\gamma\left|\sum_{s'}P_\pi(s'\mid s)(V(s')-W(s'))\right|\\ &\leq \gamma\sum_{s'}P_\pi(s'\mid s)|V(s')-W(s')|\\ &\leq \gamma \|V-W\|_\infty. \end{aligned} \]

Taking the maximum over \(s\) gives

\[ \|T^\pi V-T^\pi W\|_\infty \leq \gamma\|V-W\|_\infty. \]

Thus \(T^\pi\) is a contraction under the sup norm.

The contraction proof is one of the cleanest mathematical arguments in discounted reinforcement learning. It gives existence, uniqueness, and convergence of iterative algorithms in one step through the Banach fixed point theorem.

9.7 6.6 Iterative policy evaluation

Instead of solving a linear system directly, we can use the fixed-point iteration

\[ V_{k+1}=T^\pi V_k. \]

In scalar form,

\[ V_{k+1}(s)=r_\pi(s)+\gamma\sum_{s'}P_\pi(s'\mid s)V_k(s'). \]

This is called iterative policy evaluation. It is the prediction version of dynamic programming.

Iterative policy evaluation

Input: policy-induced model \((P_\pi,r_\pi)\), discount factor \(\gamma\), tolerance \(\varepsilon\).

Initialize \(V_0\) arbitrarily, often \(V_0=0\).
For \(k=0,1,2,\ldots\) update

\[ V_{k+1}=r_\pi+\gamma P_\pi V_k. \]
Stop when \(\|V_{k+1}-V_k\|_\infty\) is sufficiently small.
Return \(V_{k+1}\) as an approximation to \(V^\pi\).

By the contraction property,

\[ \|V_k-V^\pi\|_\infty \leq \gamma^k\|V_0-V^\pi\|_\infty. \]

A practical stopping bound uses the Bellman residual. If

\[ \|T^\pi V - V\|_\infty\leq \varepsilon, \]

then

\[ \|V-V^\pi\|_\infty \leq \frac{\varepsilon}{1-\gamma}. \]

This bound explains why high discount factors make evaluation harder: when \(\gamma\) is close to one, the factor \(1/(1-\gamma)\) is large.

9.7.1 Python example: iterative policy evaluation

def iterative_policy_evaluation(P, r, gamma, tol=1e-10, max_iter=10_000):
    V = np.zeros_like(r, dtype=float)
    history = []
    for k in range(max_iter):
        V_new = r + gamma * P @ V
        residual = np.max(np.abs(V_new - V))
        error_to_exact = np.max(np.abs(V_new - V_exact))
        history.append((k + 1, residual, error_to_exact, *V_new))
        V = V_new
        if residual < tol:
            break
    return V, pd.DataFrame(
        history,
        columns=["iteration", "residual", "error_to_exact", *states]
    )

V_iter, hist_iter = iterative_policy_evaluation(P_pi, r_pi, gamma)
V_iter

array([30.59930601, 36.97688054, 41.62492913])

hist_iter.tail()

	iteration	residual	error_to_exact	Review	Practice	Mastery
227	228	1.523404e-10	1.371056e-09	30.599306	36.976881	41.624929
228	229	1.371099e-10	1.233950e-09	30.599306	36.976881	41.624929
229	230	1.233929e-10	1.110557e-09	30.599306	36.976881	41.624929
230	231	1.110578e-10	9.995063e-10	30.599306	36.976881	41.624929
231	232	9.995205e-11	8.995542e-10	30.599306	36.976881	41.624929

9.7.2 Interactive: convergence of iterative policy evaluation

9.8 6.7 Jacobi, Gauss-Seidel, and asynchronous policy evaluation

The update

\[ V_{k+1}=r_\pi+\gamma P_\pi V_k \]

updates all states from the old vector \(V_k\). This is a Jacobi-style update.

A Gauss-Seidel-style update sweeps through states one at a time and immediately uses the newest values already computed during the same sweep:

\[ V(s_i) \leftarrow r_\pi(s_i)+\gamma\sum_{j<i}P_\pi(s_j\mid s_i)V_{\text{new}}(s_j) +\gamma\sum_{j\geq i}P_\pi(s_j\mid s_i)V_{\text{old}}(s_j). \]

This often converges faster in practice because new information is propagated immediately.

An asynchronous update only updates selected states at each step. Under appropriate conditions, if every state is updated infinitely often and \(0\leq\gamma<1\), asynchronous policy evaluation still converges to \(V^\pi\).

9.8.1 Python example: Jacobi vs Gauss-Seidel

def jacobi_evaluation(P, r, gamma, num_sweeps=30):
    V = np.zeros_like(r, dtype=float)
    residuals = []
    for _ in range(num_sweeps):
        V_new = r + gamma * P @ V
        residuals.append(np.max(np.abs(V_new - V_exact)))
        V = V_new
    return np.array(residuals)


def gauss_seidel_evaluation(P, r, gamma, num_sweeps=30):
    V = np.zeros_like(r, dtype=float)
    residuals = []
    n = len(r)
    for _ in range(num_sweeps):
        for i in range(n):
            V[i] = r[i] + gamma * P[i, :] @ V
        residuals.append(np.max(np.abs(V - V_exact)))
    return np.array(residuals)

comparison = pd.DataFrame({
    "sweep": np.arange(1, 31),
    "Jacobi error": jacobi_evaluation(P_pi, r_pi, gamma),
    "Gauss-Seidel error": gauss_seidel_evaluation(P_pi, r_pi, gamma)
})
comparison.head()

	sweep	Jacobi error	Gauss-Seidel error
0	1	35.724929	35.052352
1	2	31.278479	30.028823
2	3	27.699784	26.161008
3	4	24.694373	23.312094
4	5	22.101288	20.870528

9.8.2 Interactive: residual decay under different update schedules

9.9 6.8 Truncated-return interpretation

The exact value can be written as

\[ V^\pi=\sum_{t=0}^\infty \gamma^t P_\pi^t r_\pi. \]

The \(k\)th iterative evaluation from \(V_0=0\) gives

\[ V_k=\sum_{t=0}^{k-1}\gamma^t P_\pi^t r_\pi. \]

Thus iterative policy evaluation computes the expected discounted reward over longer and longer horizons. The missing tail is

\[ V^\pi-V_k =\sum_{t=k}^{\infty}\gamma^t P_\pi^t r_\pi. \]

If \(|r_\pi(s)|\leq R_{\max}\) for all \(s\), then

\[ \|V^\pi-V_k\|_\infty \leq \frac{\gamma^k}{1-\gamma}R_{\max}. \]

This bound is conservative, but it gives useful intuition: the effective horizon grows like \(1/(1-\gamma)\).

9.9.1 Interactive: truncation error bounds

9.10 6.9 Policy evaluation from samples

So far, we assumed that \(P_\pi\) and \(r_\pi\) are known. In reinforcement learning, this is often false. The agent may only observe trajectories

\[ S_0,A_0,R_1,S_1,A_1,R_2,S_2,\ldots. \]

There are two important sample-based viewpoints.

9.10.1 Monte Carlo evaluation

Monte Carlo evaluation estimates

\[ V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s] \]

by averaging sampled returns observed after visits to state \(s\):

\[ \widehat V(s) = \frac{1}{N(s)}\sum_{i=1}^{N(s)}G_i(s). \]

This is a direct conditional-mean estimator. It does not bootstrap from current value estimates, but it may have high variance.

9.10.2 Temporal-difference evaluation

Temporal-difference evaluation uses the Bellman relation locally. The TD(0) update is

\[ V(S_t) \leftarrow V(S_t)+\alpha_t \left[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\right]. \]

The quantity

\[ \delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t) \]

is the TD error. It measures the one-step inconsistency of the current value estimate.

Monte Carlo methods estimate the full return. TD methods estimate the Bellman fixed point by bootstrapping.

9.10.3 Python example: Monte Carlo and TD evaluation

rng = np.random.default_rng(7243)

def sample_next_state(P, s, rng):
    return rng.choice(len(P), p=P[s])


def simulate_episode(P, r, start_state, gamma, horizon, rng):
    s = start_state
    states_seen = []
    rewards = []
    for _ in range(horizon):
        states_seen.append(s)
        rewards.append(r[s])
        s = sample_next_state(P, s, rng)
    G = 0.0
    returns = []
    for reward in reversed(rewards):
        G = reward + gamma * G
        returns.append(G)
    returns.reverse()
    return states_seen, returns

# First-visit Monte Carlo estimates
num_episodes = 5_000
horizon = 50
returns_by_state = {s: [] for s in range(len(states))}

for _ in range(num_episodes):
    start = rng.integers(len(states))
    episode_states, episode_returns = simulate_episode(P_pi, r_pi, start, gamma, horizon, rng)
    visited = set()
    for s, G in zip(episode_states, episode_returns):
        if s not in visited:
            returns_by_state[s].append(G)
            visited.add(s)

V_mc = np.array([np.mean(returns_by_state[s]) for s in range(len(states))])

# TD(0) estimates
V_td = np.zeros(len(states))
alpha = 0.05
s = 0
for _ in range(100_000):
    s_next = sample_next_state(P_pi, s, rng)
    td_error = r_pi[s] + gamma * V_td[s_next] - V_td[s]
    V_td[s] += alpha * td_error
    s = s_next

pd.DataFrame({
    "state": states,
    "exact": V_exact,
    "Monte Carlo": V_mc,
    "TD(0)": V_td
})

	state	exact	Monte Carlo	TD(0)
0	Review	30.599306	30.173187	30.935650
1	Practice	36.976881	36.875831	38.163226
2	Mastery	41.624929	41.430077	42.808034

9.10.4 Interactive: sample-based policy evaluation

9.11 6.10 Statistical estimation viewpoint

For MS Statistics students, policy evaluation can be viewed as a two-stage statistical problem:

estimate the policy-induced transition matrix and reward vector from data;
solve the plug-in Bellman equation.

Suppose we observe transitions under the fixed policy \(\pi\). Let

\[ N(s,s')=\#\{t:S_t=s,S_{t+1}=s'\} \]

and

\[ N(s)=\sum_{s'}N(s,s'). \]

A natural transition estimator is

\[ \widehat P_\pi(s'\mid s)=\frac{N(s,s')}{N(s)}. \]

If \(\bar r(s)\) is the sample average reward following visits to state \(s\), then the plug-in value estimator is

\[ \widehat V=(I-\gamma \widehat P_\pi)^{-1}\widehat r. \]

This estimator is intuitive, but it is nonlinear in \(\widehat P_\pi\). Estimation error in \(\widehat P_\pi\) can be amplified when \(\gamma\) is close to one, because the inverse \((I-\gamma P_\pi)^{-1}\) becomes more sensitive.

9.11.1 Python example: plug-in policy evaluation

rng = np.random.default_rng(5110)

num_steps = 20_000
counts = np.zeros_like(P_pi)
reward_sums = np.zeros(len(states))
visits = np.zeros(len(states))

s = 0
for _ in range(num_steps):
    reward_sums[s] += r_pi[s] + rng.normal(0, 0.5)
    visits[s] += 1
    s_next = sample_next_state(P_pi, s, rng)
    counts[s, s_next] += 1
    s = s_next

P_hat = counts / counts.sum(axis=1, keepdims=True)
r_hat = reward_sums / visits
V_hat = np.linalg.solve(np.eye(len(states)) - gamma * P_hat, r_hat)

pd.DataFrame({
    "state": states,
    "V_exact": V_exact,
    "V_plugin": V_hat,
    "absolute_error": np.abs(V_hat - V_exact)
})

	state	V_exact	V_plugin	absolute_error
0	Review	30.599306	30.464965	0.134341
1	Practice	36.976881	36.864394	0.112486
2	Mastery	41.624929	41.561553	0.063377

Note

In finite problems, model-based plug-in evaluation may be statistically efficient when enough data are available for every state. In large problems, rare states and function approximation become central. Later chapters replace the table \(V(s)\) by an approximating family \(V_\theta(s)\).

9.12 6.11 A preview of approximate policy evaluation

In large state spaces, storing one value per state is impossible. We may approximate the value function by

\[ V_\theta(s)=\phi(s)^T\theta, \]

where \(\phi(s)\in\mathbb R^d\) is a feature vector. A common statistical target is the weighted least-squares projection

\[ \min_\theta \sum_{s\in\mathcal S}d_\pi(s) \left(V^\pi(s)-\phi(s)^T\theta\right)^2, \]

where \(d_\pi\) is a state weighting distribution, often related to the stationary or discounted occupancy distribution under \(\pi\).

This leads to projected Bellman equations and stochastic approximation algorithms. These topics are developed in detail in Chapter 13 on function approximation and Chapter 14 on stochastic approximation.

9.13 6.12 AI-assisted learning components

Modern AI tools can be helpful in this chapter, but they should be used as mathematical assistants rather than as black boxes.

AI prompt: checking a Bellman equation

Give an AI system a finite policy-induced transition matrix \(P_\pi\), reward vector \(r_\pi\), and discount factor \(\gamma\). Ask it to:

write the Bellman expectation equation in scalar form;
write the same equation in matrix form;
check whether each row of \(P_\pi\) sums to one;
solve the linear system;
verify the solution by computing the Bellman residual.

Then independently verify the output in Python.

AI prompt: debugging iterative policy evaluation

Paste a short implementation of iterative policy evaluation and ask:

Find any mathematical or programming mistakes. In particular, check whether the update uses the old value vector or accidentally mixes old and new values. Also check whether the stopping rule controls the Bellman residual or only the change between iterates.

This prompt helps students distinguish Jacobi, Gauss-Seidel, and residual-based stopping criteria.

AI prompt: explaining assumptions

Ask:

In discounted finite-state policy evaluation, why does \(0\leq\gamma<1\) guarantee a unique value function? Which parts of the proof fail if \(\gamma=1\)?

The expected answer should mention contraction, invertibility of \(I-\gamma P_\pi\), and the need for additional recurrence or average-reward assumptions in the undiscounted case.

9.14 6.13 Summary

Policy evaluation is one of the foundational problems in reinforcement learning.

A fixed policy \(\pi\) turns an MDP into an MRP with transition matrix \(P_\pi\) and reward vector \(r_\pi\).
The value function satisfies

\[ V^\pi=r_\pi+\gamma P_\pi V^\pi. \]
In finite discounted problems,

\[ V^\pi=(I-\gamma P_\pi)^{-1}r_\pi. \]
The Bellman expectation operator is a contraction:

\[ \|T^\pi V-T^\pi W\|_\infty\leq \gamma\|V-W\|_\infty. \]
Iterative policy evaluation repeatedly applies \(T^\pi\).
Gauss-Seidel and asynchronous variants can improve computational efficiency.
Monte Carlo and TD methods evaluate policies from samples rather than from a known model.
Statistical estimation matters because value estimates depend on estimated rewards, transitions, and sampling coverage.

9.15 Exercises

9.15.1 Conceptual exercises

Explain why policy evaluation is easier than optimal control.
In your own words, explain the meaning of the reduction

\[ \text{MDP}+\pi\Rightarrow\text{MRP}. \]
Why is the Bellman expectation equation linear for a fixed policy?
Why does a large discount factor make policy evaluation harder?
Compare Monte Carlo and TD evaluation in terms of bias, variance, and bootstrapping.

9.15.2 Mathematical exercises

Let \(P_\pi\) be a stochastic matrix and \(0\leq\gamma<1\). Prove that \(I-\gamma P_\pi\) is invertible using the Neumann series.
Prove that \(T^\pi\) is a contraction under \(\|\cdot\|_\infty\).
Starting from \(V_0=0\), prove that

\[ V_k=\sum_{t=0}^{k-1}\gamma^t P_\pi^t r_\pi. \]
Suppose \(|r_\pi(s)|\leq R_{\max}\) for all \(s\). Prove that

\[ \|V^\pi-V_k\|_\infty \leq \frac{\gamma^k}{1-\gamma}R_{\max}. \]
Derive the residual bound

\[ \|V-V^\pi\|_\infty \leq \frac{\|T^\pi V-V\|_\infty}{1-\gamma}. \]

9.15.3 Computational exercises

Implement iterative policy evaluation for the study-planning MDP using \(\gamma=0.50,0.80,0.90,0.97\). Compare the number of iterations required for a fixed tolerance.
Implement Gauss-Seidel policy evaluation and compare it with Jacobi iteration.
Simulate trajectories under the fixed policy and estimate \(V^\pi\) using first-visit Monte Carlo.
Implement TD(0) for the same policy. Compare different learning rates.
Estimate \(\widehat P_\pi\) and \(\widehat r_\pi\) from simulated data, then compute the plug-in value estimate. Repeat the experiment many times and estimate the sampling distribution of \(\widehat V(s)\).

9.15.4 AI-assisted exercises

Ask an AI system to derive the Bellman expectation equation from the return identity \(G_t=R_{t+1}+\gamma G_{t+1}\). Check every conditional expectation step manually.
Ask an AI system to generate a small four-state policy-induced Markov reward process. Verify that the transition matrix is stochastic and compute the value function in Python.
Ask an AI system to explain why TD(0) is called a bootstrapping method. Compare the explanation with the update formula.
Ask an AI system to create a bug in policy evaluation code. Then identify and fix the bug.
Ask an AI system to compare direct linear algebra, iterative dynamic programming, and sample-based TD evaluation for large state spaces. Identify which statements are mathematical facts and which are practical heuristics.

9.16 Notes for instructors

This chapter is a good place to slow down and emphasize mathematical structure. For MA Applied Math students, focus on fixed points, contractions, linear systems, and iterative methods. For MS Statistics students, emphasize conditional expectations, Monte Carlo estimation, plug-in estimators, sampling variability, and the statistical meaning of the TD error.

A useful lecture sequence is:

derive \(P_\pi\) and \(r_\pi\);
solve \(V^\pi=(I-\gamma P_\pi)^{-1}r_\pi\);
prove contraction;
implement iterative policy evaluation;
compare exact, iterative, Monte Carlo, and TD estimates.