11  Value Iteration

Core idea. Value iteration solves an optimal control problem by repeatedly applying the optimal Bellman operator

\[ (TV)(s)=\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right]. \]

Instead of fully evaluating one policy and then improving it, value iteration performs a one-step optimality backup at every iteration. Mathematically, it is fixed-point iteration for the nonlinear equation

\[ V^*=TV^*. \]

For a finite discounted Markov decision process, \(T\) is a contraction in the sup norm. This gives existence, uniqueness, convergence, computable error bounds, and a clear stopping rule.

11.1 Learning goals

After reading this chapter, students should be able to:

1. define the optimal Bellman operator for a finite discounted MDP;
2. prove that the Bellman optimality operator is a contraction in \(\|\cdot\|_\infty\);
3. implement value iteration from first principles;
4. distinguish value error, Bellman residual, and greedy-policy error;
5. derive practical stopping criteria from mathematical error bounds;
6. explain why large discount factors slow convergence;
7. interpret value iteration as finite-horizon dynamic programming with a moving horizon;
8. compare value iteration, policy iteration, and modified policy iteration;
9. use Python to compute values, residuals, and greedy policies in small finite MDPs;
10. use AI tools to check derivations, debug code, and critique stopping criteria.

11.2 8.1 Why value iteration?

Policy iteration alternates two steps:

\[ \text{evaluate }\pi_k \quad\longrightarrow\quad \text{improve greedily to obtain }\pi_{k+1}. \]

Exact policy evaluation can be expensive because it requires solving a linear system

\[ (I-\gamma P_{\pi_k})V^{\pi_k}=r_{\pi_k} \]

at every outer iteration. Value iteration avoids exact evaluation. It directly applies the optimal Bellman update

\[ V_{k+1}=TV_k. \]

Each iteration combines two operations:

1. expectation over next states, using \(P(s'\mid s,a)\);
2. optimization over actions, using \(\max_a\).

Thus value iteration is both a probabilistic computation and an optimization computation.

Value iteration is the cleanest first example of nonlinear fixed-point computation in reinforcement learning. The nonlinearity comes from the maximum over actions. The contraction comes from discounting.

11.3 8.2 Setup: finite discounted MDPs

Let

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

be a finite discounted MDP. Here:

• \(\mathcal S=\{1,\ldots,n\}\) is a finite state space;
• \(\mathcal A\) is a finite action set;
• \(P(s'\mid s,a)\) is the transition probability;
• \(r(s,a)=\mathbb E[R_{t+1}\mid S_t=s,A_t=a]\) is the expected one-step reward;
• \(0\leq \gamma<1\) is the discount factor.

For a stationary deterministic policy \(\pi\), the value function satisfies

\[ V^\pi(s)=r(s,\pi(s))+\gamma\sum_{s'}P(s'\mid s,\pi(s))V^\pi(s'). \]

The optimal value function is

\[ V^*(s)=\sup_\pi V^\pi(s). \]

In finite discounted MDPs, the supremum is achieved by at least one stationary deterministic policy. Therefore it is enough to search over deterministic greedy policies, although randomized policies are still useful for exploration and statistical learning.

11.4 8.3 The optimal Bellman operator

For any vector \(V\in\mathbb R^{|\mathcal S|}\), define

\[ (TV)(s) = \max_{a\in\mathcal A(s)} \left[ r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s') \right]. \]

The quantity inside the maximum is the one-step lookahead value of action \(a\) if \(V\) is used as the continuation value.

It is often useful to define action-specific affine operators

\[ (T_aV)(s) = r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s'). \]

Then

\[ (TV)(s)=\max_a (T_aV)(s). \]

The Bellman optimality equation is the fixed-point equation

\[ V^*=TV^*. \]

A greedy policy with respect to \(V\) is any policy \(\pi_V\) satisfying

\[ \pi_V(s)\in \arg\max_a \left[ r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s') \right]. \]

If \(V=V^*\), then any greedy policy \(\pi_{V^*}\) is optimal.

11.4.1 Interactive demonstration: contraction speed

The next figure shows the basic contraction scale \(\gamma^k\). It is not the actual value error for every MDP, but it explains the dominant phenomenon: when \(\gamma\) is close to \(1\), value iteration can need many more iterations.

11.5 8.4 Contraction theorem

The main mathematical fact behind value iteration is that \(T\) is a contraction in the sup norm.

Theorem 8.1: Bellman optimality operator is a contraction. For any \(V,W\in\mathbb R^{|\mathcal S|}\),

\[ \|TV-TW\|_\infty\leq \gamma \|V-W\|_\infty. \]

Therefore, for \(0\leq \gamma<1\), the operator \(T\) has a unique fixed point \(V^*\) and the sequence \(V_{k+1}=TV_k\) converges to \(V^*\) from every initial vector \(V_0\).

Proof. For a fixed state \(s\), define

\[ f_a(V)=r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s'). \]

Then

\[ (TV)(s)=\max_a f_a(V), \qquad (TW)(s)=\max_a f_a(W). \]

For any two finite collections \(\{x_a\}\) and \(\{y_a\}\),

\[ \left|\max_a x_a-\max_a y_a\right|\leq \max_a |x_a-y_a|. \]

Hence

\[ \begin{aligned} |(TV)(s)-(TW)(s)| &\leq \max_a \left| \gamma\sum_{s'}P(s'\mid s,a)(V(s')-W(s')) \right|\\ &\leq \gamma \max_a \sum_{s'}P(s'\mid s,a)|V(s')-W(s')|\\ &\leq \gamma\|V-W\|_\infty. \end{aligned} \]

Taking the maximum over \(s\) gives the contraction inequality. The Banach fixed-point theorem gives existence, uniqueness, and convergence to the unique fixed point. \(\square\)

The proof uses two special facts: the transition probabilities are nonnegative and sum to one, and \(\gamma<1\). Without discounting, \(T\) may fail to be a contraction in the ordinary sup norm.

11.6 8.5 The value iteration algorithm

Value iteration starts from an arbitrary vector \(V_0\) and repeats

\[ V_{k+1}(s)=\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V_k(s')\right]. \]

Algorithm 8.1: Value iteration for a finite discounted MDP

Input: transition probabilities \(P(s'\mid s,a)\), rewards \(r(s,a)\), discount factor \(\gamma\), tolerance \(\varepsilon\).

1. Initialize \(V_0(s)\) for each state \(s\).

2. For \(k=0,1,2,\ldots\):

   • for each state \(s\), compute

     \[ V_{k+1}(s)=\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V_k(s')\right]; \]

   • compute a stopping diagnostic, such as \(\|V_{k+1}-V_k\|_\infty\) or \(\|TV_k-V_k\|_\infty\);

   • stop when the diagnostic is small enough.

3. Extract a greedy policy:

   \[ \pi(s)\in\arg\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right]. \]

The update is called a Bellman optimality backup. It replaces the current value of a state by the best one-step expected return plus discounted continuation value.

11.7 8.6 Error bound from contraction

Since \(V^*=TV^*\) and \(V_{k+1}=TV_k\), the contraction property gives

\[ \|V_{k+1}-V^*\|_\infty = \|TV_k-TV^*\|_\infty \leq \gamma\|V_k-V^*\|_\infty. \]

By induction,

\[ \boxed{ \|V_k-V^*\|_\infty \leq \gamma^k\|V_0-V^*\|_\infty. } \]

This is a clean theoretical bound but it contains the unknown quantity \(\|V_0-V^*\|_\infty\). For actual computation, we need bounds that can be evaluated from the iterates.

11.8 8.7 Bellman residual and computable stopping rules

For any candidate value vector \(V\), the Bellman residual is

\[ \operatorname{Res}(V)=\|TV-V\|_\infty. \]

If \(\operatorname{Res}(V)=0\), then \(V\) is a fixed point of \(T\), so \(V=V^*\).

Theorem 8.2: Residual error bound. For any \(V\in\mathbb R^{|\mathcal S|}\),

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

Proof. Since \(V^*=TV^*\),

\[ \begin{aligned} \|V-V^*\|_\infty &=\|V-TV^*\|_\infty\\ &\leq \|V-TV\|_\infty+\|TV-TV^*\|_\infty\\ &\leq \|V-TV\|_\infty+\gamma\|V-V^*\|_\infty. \end{aligned} \]

Move the last term to the left-hand side:

\[ (1-\gamma)\|V-V^*\|_\infty\leq \|TV-V\|_\infty. \]

This proves the result. \(\square\)

A common stopping rule uses the difference between consecutive iterates:

\[ \Delta_k=\|V_{k+1}-V_k\|_\infty=\|TV_k-V_k\|_\infty. \]

Thus the residual bound gives

\[ \|V_k-V^*\|_\infty\leq \frac{\Delta_k}{1-\gamma}. \]

If the user wants value error at most \(\varepsilon\), a sufficient condition is

\[ \Delta_k\leq (1-\gamma)\varepsilon. \]

11.8.1 Interactive demonstration: residual bounds

11.9 8.8 Greedy-policy performance bounds

In control, the final goal is not merely a good value estimate; the goal is a good policy. Suppose \(\pi_V\) is greedy with respect to an approximate value vector \(V\). How bad can \(\pi_V\) be?

Theorem 8.3: Performance bound for a greedy policy. Let \(\pi_V\) be any policy greedy with respect to \(V\). Then

\[ \|V^*-V^{\pi_V}\|_\infty \leq \frac{2\gamma}{1-\gamma}\|V-V^*\|_\infty. \]

Using the residual bound, this implies

\[ \|V^*-V^{\pi_V}\|_\infty \leq \frac{2\gamma}{(1-\gamma)^2}\|TV-V\|_\infty. \]

Proof idea. Because \(\pi_V\) is greedy with respect to \(V\),

\[ T_{\pi_V}V=TV. \]

Let \(L=\|V^*-V^{\pi_V}\|_\infty\) and \(e=\|V-V^*\|_\infty\). Using monotonicity and contraction of the policy-specific Bellman operator,

\[ L\leq \gamma e+\gamma\|V-V^{\pi_V}\|_\infty \leq \gamma e+\gamma(e+L). \]

Therefore

\[ (1-\gamma)L\leq 2\gamma e, \]

which gives the first inequality. The second follows from Theorem 8.2. \(\square\)

The factor \((1-\gamma)^{-2}\) can be large. When \(\gamma\) is close to one, a small Bellman residual may still be needed to guarantee a strong policy-performance bound.

11.10 8.9 Python example: a small finite MDP

Consider an MDP with three states and two actions. The transition array has shape

\[ |\mathcal A|\times |\mathcal S|\times |\mathcal S|. \]

The reward matrix has shape

\[ |\mathcal S|\times |\mathcal A|. \]

import numpy as np

# P[a, s, s_next]
P = np.array([
    # action 0: cautious
    [[0.75, 0.25, 0.00],
     [0.10, 0.70, 0.20],
     [0.00, 0.20, 0.80]],
    # action 1: aggressive
    [[0.20, 0.80, 0.00],
     [0.05, 0.15, 0.80],
     [0.00, 0.05, 0.95]],
])

# r[s, a]
r = np.array([
    [0.0, 0.4],
    [0.2, 0.1],
    [1.0, 0.6],
])

gamma = 0.90
n_actions, n_states, _ = P.shape

def bellman_optimality_backup(V):
    """Return T V and one greedy action for each state."""
    Q = np.zeros((n_states, n_actions))
    for a in range(n_actions):
        Q[:, a] = r[:, a] + gamma * P[a] @ V
    return Q.max(axis=1), Q.argmax(axis=1), Q

V = np.zeros(n_states)
history = []
for k in range(200):
    V_new, greedy, Q = bellman_optimality_backup(V)
    delta = np.max(np.abs(V_new - V))
    history.append(delta)
    V = V_new
    if delta < 1e-10:
        break

print("iterations:", k + 1)
print("V* approximately:", np.round(V, 6))
print("greedy policy:", greedy)
print("Bellman residual:", history[-1])

iterations: 200
V* approximately: [7.009368 7.427336 8.346145]
greedy policy: [1 1 0]
Bellman residual: 6.370122207499662e-10

The greedy policy is extracted after the value vector is close to a fixed point. The last number is the Bellman residual \(\|TV_k-V_k\|_\infty\).

We can evaluate the greedy policy exactly by solving a linear system.

def evaluate_deterministic_policy(policy):
    P_pi = np.zeros((n_states, n_states))
    r_pi = np.zeros(n_states)
    for s in range(n_states):
        a = policy[s]
        P_pi[s] = P[a, s]
        r_pi[s] = r[s, a]
    return np.linalg.solve(np.eye(n_states) - gamma * P_pi, r_pi)

V_pi = evaluate_deterministic_policy(greedy)
print("V of greedy policy:", np.round(V_pi, 6))
print("sup-norm difference between V estimate and V_pi:", np.max(np.abs(V - V_pi)))

V of greedy policy: [7.009368 7.427336 8.346145]
sup-norm difference between V estimate and V_pi: 5.733101993143919e-09

If the greedy policy is optimal, then \(V^{\pi}=V^*\) up to numerical error.

11.11 8.10 Visualizing value iteration on a small gridworld

A gridworld is useful because the value function can be visualized as a surface or heatmap. The following interactive display shows a stylized value function after increasing numbers of value-iteration sweeps.

The purpose of this figure is conceptual: Bellman backups propagate information backward from rewarding terminal or goal states. Early iterations only affect nearby states. Later iterations propagate long-range consequences.

11.12 8.11 Python example: gridworld value iteration

The next example implements value iteration for a small deterministic gridworld. The agent receives a step cost and a positive reward at the goal.

import numpy as np

height, width = 4, 4
goal = (3, 3)
gamma = 0.95
step_reward = -0.04
goal_reward = 1.0
actions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right

def state_index(i, j):
    return i * width + j

def move(i, j, action):
    if (i, j) == goal:
        return i, j
    di, dj = action
    ni = min(max(i + di, 0), height - 1)
    nj = min(max(j + dj, 0), width - 1)
    return ni, nj

def value_iteration_grid(tol=1e-8, max_iter=10_000):
    V = np.zeros(height * width)
    for k in range(max_iter):
        V_new = np.zeros_like(V)
        policy = np.zeros(height * width, dtype=int)
        for i in range(height):
            for j in range(width):
                s = state_index(i, j)
                if (i, j) == goal:
                    V_new[s] = goal_reward
                    policy[s] = 0
                    continue
                q_values = []
                for a, action in enumerate(actions):
                    ni, nj = move(i, j, action)
                    sp = state_index(ni, nj)
                    q_values.append(step_reward + gamma * V[sp])
                V_new[s] = np.max(q_values)
                policy[s] = int(np.argmax(q_values))
        delta = np.max(np.abs(V_new - V))
        V = V_new
        if delta < tol:
            break
    return V.reshape(height, width), policy.reshape(height, width), k + 1, delta

V_grid, policy_grid, num_iter, last_delta = value_iteration_grid()
print("iterations:", num_iter)
print("last delta:", last_delta)
print("value grid:")
print(np.round(V_grid, 3))
print("policy action indices: 0=up, 1=down, 2=left, 3=right")
print(policy_grid)

iterations: 8
last delta: 0.0
value grid:
[[0.523 0.593 0.666 0.743]
 [0.593 0.666 0.743 0.824]
 [0.666 0.743 0.824 0.91 ]
 [0.743 0.824 0.91  1.   ]]
policy action indices: 0=up, 1=down, 2=left, 3=right
[[1 1 1 1]
 [1 1 1 1]
 [1 1 1 1]
 [3 3 3 0]]

This example is intentionally simple. More realistic gridworlds may include stochastic movement, obstacles, terminal states with negative reward, and absorbing boundaries.

11.13 8.12 Finite-horizon interpretation

When \(V_0\) is interpreted as a terminal value function, the iterates

\[ V_{k+1}=TV_k \]

can be interpreted as optimal values for problems with one more decision step. For example, if \(V_0(s)=0\), then \(V_1\) is the best expected one-step reward, \(V_2\) is the best expected two-step discounted reward, and so on.

Thus value iteration can be viewed in two equivalent ways:

1. infinite-horizon fixed-point iteration: \(V_k\to V^*\);
2. finite-horizon dynamic programming: \(V_k\) solves a \(k\)-step lookahead problem with terminal value \(V_0\).

This interpretation explains why value iteration gradually propagates reward information across the state space.

11.13.1 Interactive demonstration: horizon expansion

11.14 8.13 Monotone value iteration

The Bellman operator \(T\) is monotone: if \(V\leq W\) componentwise, then

\[ TV\leq TW. \]

This follows because expectations and maxima preserve order.

If \(V_0\leq TV_0\), then

\[ V_0\leq V_1\leq V_2\leq \cdots \leq V^* \]

under appropriate boundedness assumptions. Similarly, if \(V_0\geq TV_0\), then the sequence decreases toward \(V^*\) from above.

Monotone initialization is useful when one can construct simple lower and upper bounds. For example, if rewards satisfy

\[ r_{\min}\leq r(s,a)\leq r_{\max}, \]

then

\[ \frac{r_{\min}}{1-\gamma} \leq V^*(s) \leq \frac{r_{\max}}{1-\gamma}. \]

These bounds can be loose, but they are often enough to sanity-check numerical output.

11.15 8.14 Asynchronous and Gauss-Seidel value iteration

The standard update computes all entries of \(V_{k+1}\) from the old vector \(V_k\). This is a Jacobi-style update. An alternative is to update states one at a time and immediately use the newest available values. This is a Gauss-Seidel-style or asynchronous update.

For a sweep order \(s_1,s_2,\ldots,s_n\), an in-place update replaces

\[ V(s_i)\leftarrow \max_a\left[r(s_i,a)+\gamma\sum_{s'}P(s'\mid s_i,a)V(s')\right]. \]

Under standard conditions for finite discounted MDPs, asynchronous value iteration converges if every state is updated infinitely often.

Practical note. In-place value iteration can converge faster in wall-clock time because new information is used immediately. However, the exact sequence of iterates depends on the state update order, so reproducibility requires recording the order.

11.16 8.15 Computational complexity

Suppose there are \(n\) states and \(m\) actions per state. A full Bellman backup requires computing

\[ \sum_{s'}P(s'\mid s,a)V(s') \]

for each state-action pair. If transitions are dense, one sweep costs approximately

\[ O(mn^2). \]

If transitions are sparse and each state-action pair has at most \(d\) possible next states, one sweep costs

\[ O(mnd). \]

The number of iterations needed to achieve a value error of order \(\varepsilon\) scales roughly like

\[ \frac{\log(1/\varepsilon)}{1-\gamma} \]

when \(\gamma\) is close to one. This explains why high-discount problems are computationally harder.

11.16.1 Interactive demonstration: discount factor and iteration count

11.17 8.16 Value iteration versus policy iteration

Value iteration and policy iteration solve the same optimality problem but take different computational routes.

Method	Main step	Strength	Weakness
Policy iteration	exact or near-exact policy evaluation plus greedy improvement	often few outer iterations	linear system or many evaluation sweeps can be costly
Value iteration	repeated optimal Bellman backups	simple and stable	can be slow when \(\gamma\) is close to one
Modified policy iteration	partial evaluation plus improvement	interpolates between both	requires choosing evaluation depth

A useful mental model is:

\[ \text{value iteration} \approx \text{policy iteration with one-step partial evaluation before improvement}. \]

This is not an exact identity in every implementation, but it captures the algorithmic relationship.

11.18 8.17 Statistical viewpoint

So far value iteration has assumed that \(P\) and \(r\) are known. In many reinforcement learning problems they must be estimated from data. Suppose we have estimates \(\widehat P\) and \(\widehat r\). The empirical Bellman operator is

\[ (\widehat T V)(s)= \max_a\left[ \widehat r(s,a)+\gamma\sum_{s'}\widehat P(s'\mid s,a)V(s') \right]. \]

The computed fixed point \(\widehat V\) solves

\[ \widehat V=\widehat T\widehat V, \]

not necessarily \(V^*=TV^*\). Therefore the error has two components:

\[ \widehat V-V^* = \underbrace{\widehat V-V_{\widehat M}^*}_{\text{optimization / numerical error}} + \underbrace{V_{\widehat M}^*-V_M^*}_{\text{statistical model error}}. \]

Here \(\widehat M\) is the estimated MDP and \(M\) is the true MDP. For MS Statistics students, this decomposition is important: even perfect convergence for the estimated model does not eliminate sampling error.

11.19 8.18 AI-assisted learning components

Modern AI tools can help students learn value iteration, but they should be used to check mathematical reasoning rather than to replace it.

AI prompt: deriving the contraction proof

Ask an AI system:

Prove that the optimal Bellman operator for a finite discounted MDP is a contraction in the sup norm. Make every inequality explicit, especially the step involving the maximum over actions.

Then check whether the proof uses \(\gamma<1\) and whether it correctly handles the maximum operation.

AI prompt: debugging value iteration code

Paste a value-iteration implementation and ask:

Check this code for mathematical and programming mistakes. In particular, verify the shape of the transition array, whether the maximum is taken over actions rather than states, whether the stopping rule uses the correct norm, and whether the greedy policy is extracted from the final value vector.

Then verify the answer with a small hand-computable MDP.

AI prompt: explaining the residual bound

Ask:

Explain why a small Bellman residual implies that a value vector is close to the optimal value function. Derive the factor \(1/(1-\gamma)\) and explain why this factor becomes large when \(\gamma\) is close to one.

A good answer should use the contraction inequality and should not confuse residual error with policy-performance error.

AI prompt: creating examples

Ask:

Construct a three-state, two-action MDP where value iteration converges slowly when \(\gamma=0.99\). Explain which transition structure and rewards make the slow convergence visible.

Then implement the example and compare \(\gamma=0.7\), \(0.9\), and \(0.99\).

11.20 8.19 Common mistakes

1. Maximizing over the wrong axis. In code, the action dimension must be clear. If \(Q\) has shape (states, actions), use Q.max(axis=1).
2. Using transition rows that do not sum to one. Every \(P(\cdot\mid s,a)\) must be a probability distribution.
3. Stopping too early when \(\gamma\) is large. The residual bound divides by \(1-\gamma\).
4. Confusing value convergence with policy convergence. The greedy policy may stabilize before the value vector is highly accurate, or it may change because of tiny numerical ties.
5. Ignoring tie-breaking. Deterministic tie-breaking makes results reproducible.
6. Forgetting terminal-state modeling. Terminal states should be represented consistently, often as absorbing states.

11.21 8.20 Summary

Value iteration is a central dynamic programming algorithm for finite discounted MDPs.

• The optimal Bellman operator is

  \[ (TV)(s)=\max_a\left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right]. \]

• The optimal value function is the unique fixed point \(V^*=TV^*\).

• The contraction inequality

  \[ \|TV-TW\|_\infty\leq \gamma\|V-W\|_\infty \]

  gives convergence from any initial value vector.

• The Bellman residual provides a computable error bound:

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

• A greedy policy extracted from an approximate value vector has a performance bound controlled by the value approximation error.

• Large \(\gamma\) makes value iteration slower and makes residual tolerances more demanding.

11.22 8.21 Conceptual exercises

1. Explain why value iteration can be viewed as fixed-point iteration.
2. In your own words, explain why the maximum over actions makes the Bellman optimality operator nonlinear.
3. Why does discounting create a contraction? What goes wrong when \(\gamma=1\)?
4. Compare value iteration and policy iteration. Which one would you try first for a small dense MDP? Which one for a very large sparse MDP?
5. Explain why a small change in the value vector can sometimes change the greedy policy.

11.23 8.22 Mathematical exercises

1. Prove that \(T\) is monotone: if \(V\leq W\), then \(TV\leq TW\).

2. Prove the residual error bound

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

3. Suppose \(|r(s,a)|\leq R_{\max}\) for all \(s,a\). Prove that

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

4. Let \(\pi_V\) be greedy with respect to \(V\). Prove

   \[ \|V^*-V^{\pi_V}\|_\infty \leq \frac{2\gamma}{1-\gamma}\|V-V^*\|_\infty. \]

5. Show that if \(V_0\leq TV_0\), then the sequence \(V_{k+1}=TV_k\) is monotone nondecreasing.

11.24 8.23 Computational exercises

1. Implement value iteration for the three-state MDP in Section 8.9. Plot \(\|V_{k+1}-V_k\|_\infty\) versus iteration number on a log scale.
2. Repeat the experiment with \(\gamma=0.5,0.8,0.95,0.99\). How does the number of iterations change?
3. Modify the gridworld so that one state has a negative terminal reward. How does the greedy policy change?
4. Implement Gauss-Seidel value iteration. Compare the number of sweeps with standard value iteration.
5. Add random transition noise to the gridworld: with probability \(0.8\) the intended action occurs, and with probability \(0.2\) a random action occurs. Recompute the value function and policy.
6. Estimate \(P\) and \(r\) from simulated samples, run value iteration on the estimated MDP, and compare the result with the true model-based solution.

11.25 8.24 AI-assisted exercises

1. Ask an AI system to write value iteration code for a finite MDP. Identify at least three possible bugs or ambiguous modeling assumptions in the code.
2. Ask an AI system to prove the contraction theorem. Rewrite the proof in your own words and check every inequality.
3. Ask an AI system to explain the difference between Bellman residual and policy loss. Provide a counterexample or numerical example showing that the two are not identical.
4. Ask an AI system to design a small MDP where tie-breaking matters. Implement it and test two different tie-breaking rules.
5. Ask an AI system to propose a stopping tolerance for \(\gamma=0.99\) and desired value error \(0.01\). Check whether the proposed tolerance follows the residual bound.

11.26 8.25 Notes for instructors

For MA Applied Math students, emphasize:

• nonlinear contraction mappings;
• fixed-point iteration;
• monotone operators;
• sup-norm estimates;
• computational complexity.

For MS Statistics students, emphasize:

• conditional expectations inside the Bellman backup;
• plug-in estimation of \(P\) and \(r\);
• model error versus optimization error;
• residual diagnostics and uncertainty.

A good lecture sequence is:

1. derive \(T\) from one-step optimal lookahead;
2. prove contraction;
3. implement value iteration on a three-state MDP;
4. discuss residual stopping rules;
5. visualize value propagation in a gridworld;
6. compare with policy iteration.

11.27 References

Classic references for this chapter include Bellman’s dynamic programming principle, Puterman’s treatment of Markov decision processes, Bertsekas’s dynamic programming texts, and Sutton and Barto’s reinforcement learning presentation. The contraction and residual arguments are also standard in numerical analysis through the Banach fixed-point theorem.