Value iteration

Optimal Value Function $V^{*}$

V^{*} (s) = max_{π} E [\sum_{t = 0}^{H} γ^{t} R (s_{t}, a_{t}, s_{t + 1}) | π, s_{0} = s]

Expected sum of discounted rewards when starting from state $s$ and acting optimally.

A four-column, three-row Gridworld with plus-one reward at (4,3) and minus-one reward at (4,2)

Let’s assume:

Actions are deterministically successful.
$γ = 1, H = 100$

$V^{*} (4, 3) = 1$
$V^{*} (3, 3) = 1$
$V^{*} (2, 3) = 1$
$V^{*} (1, 1) = 1$
$V^{*} (4, 2) = - 1$

From (4,2), the agent must exit and receive −1; the true terminal state reached afterward has value 0.

V^{*} (4, 2) = - 1 + 1 \times 0 = - 1

Let’s assume:

Actions are deterministically successful.
$γ = 0.9, H = 100$

$V^{*} (4, 3) = 1$
$V^{*} (3, 3) = 0.9$
$V^{*} (2, 3) = 0.9 \times 0.9 = 0.81$
$V^{*} (1, 1) =$ $0.9 \times 0.9 \times 0.9 \times 0.9 \times 0.9$ $\approx 0.59$
$V^{*} (4, 2) = - 1$

Let’s assume:

Actions successful w/probability 0.8.
$γ = 0.9, H = 100$

$V^{*} (4, 3) = 1$

\begin{array}{ll} V^{*} (3, 3) & = 0.8 \times 0.9 \times V^{*} (4, 3) \\ + 0.1 \times 0.9 \times V^{*} (3, 3) \\ + 0.1 \times 0.9 \times V^{*} (3, 2) \end{array}

$V_{0}^{*} (s) =$ optimal value for state $s$ when $H = 0$

V_{0}^{*} (s) = 0 \forall s

$V_{1}^{*} (s) =$ optimal value for state $s$ when $H = 1$

V_{1}^{*} (s) = max_{a} \sum_{s^{'}} P (s^{'} | s, a) (R (s, a, s^{'}) + γ V_{0}^{*} (s^{'}))

$V_{k}^{*} (s) =$ optimal value for state $s$ when $H = k$

V_{k}^{*} (s) = max_{a} \sum_{s^{'}} P (s^{'} | s, a) (R (s, a, s^{'}) + γ V_{k - 1}^{*} (s^{'}))

Bellman Update

Algorithm:

Start with $V_{0}^{*} (s) = 0$ for all $s$ .

For $k = 1, \dots, H$ :

For all states $s \in S$ :

V_{k}^{*} (s) \leftarrow max_{a} \sum_{s^{'}} P (s^{'} | s, a) (R (s, a, s^{'}) + γ V_{k - 1}^{*} (s^{'}))

π_{k}^{*} (s) \leftarrow \underset{a}{arg max} \sum_{s^{'}} P (s^{'} | s, a) (R (s, a, s^{'}) + γ V_{k - 1}^{*} (s^{'}))

This is called a value update or Bellman update/back-up.

max returns the best value; argmax returns the action that achieves it. Since the remaining steps use optimal values, choosing this action in each state gives the optimal policy for the remaining horizon.

Value Iteration Convergence

Theorem. For a finite MDP with bounded rewards and $0 \leq γ < 1$ , value iteration converges to the optimal value function $V^{*}$ for the discounted infinite-horizon problem, which satisfies the Bellman optimality equation:

\forall s \in S : V^{*} (s) = max_{a} \sum_{s^{'}} T (s, a, s^{'}) [R (s, a, s^{'}) + γ V^{*} (s^{'})]

T (s, a, s^{'}) = P (s^{'} | s, a)

T is the transition probability used in every update. At convergence, both $V_{k}$ and $V_{k - 1}$ approach $V^{*}$ , so the update becomes the Bellman optimality equation.

The Bellman update contracts the maximum value error by a factor of at most $γ$ each iteration.

Convergence: Intuition

As in the slide, assume $0 \leq R (s) \leq R_{max}$ and $0 \leq γ < 1$ . Here, H is the last included reward index.

γ^{H + 1} R (s_{H + 1}) + γ^{H + 2} R (s_{H + 2}) + \dots \overset{\begin{matrix} R (s) \leq R_{max} \\ ↓ \end{matrix}}{\leq} γ^{H + 1} R_{max} + γ^{H + 2} R_{max} + \dots \overset{\begin{matrix} Geometric series \\ ↓ \end{matrix}}{=} \frac{γ^{H + 1}}{1 - γ} R_{max}

{\frac{γ^{H + 1}}{1 - γ}}_{\begin{matrix} ↑ \\ Fixed and positive \end{matrix}}^{\begin{matrix} γ^{H + 1} \to 0 \\ ↓ \end{matrix}} R_{max} \overset{H \to \infty}{⟶} 0

This bound holds for every policy, so it also bounds the difference between the optimal values:

0 \leq | V^{*} (s) - V_{H + 1}^{*} (s) | \leq \frac{γ^{H + 1} R_{max}}{1 - γ} \overset{H \to \infty}{⟶} 0

The error is squeezed to 0, so the finite-horizon optimal value converges to $V^{*}$ .

If rewards can be negative, use the maximum absolute reward and bound the error from both sides.

Convergence and Contractions

For the same finite MDP with bounded rewards, take $0 < γ < 1$ . The idea is that each update brings value estimates closer together, until they reach the same answer.

Definition: max-norm

$∥ U ∥ = max_{s} | U (s) |$

Think of U as a table with one value per state. Take the absolute value of every entry, then pick the largest. If the entries are 1, −3, and 2, the max-norm is 3.

For $∥ U - V ∥$ , compare the two tables state by state and take the largest absolute difference. It measures their biggest disagreement.
Definition: An update operation is a γ-contraction in max-norm if and only if

$for all U_{i}, V_{i} : ∥ U_{i + 1} - V_{i + 1} ∥ \leq γ ∥ U_{i} - V_{i} ∥$

Start with any two value tables, Uᵢ and Vᵢ, and apply the same update to both. Their biggest disagreement afterward is at most γ times what it was before. The index i counts update rounds.

With γ = 0.9, a disagreement of 10 becomes at most 9 after one update, then at most 8.1 after another. “For all” means this must hold for every pair of tables; “if and only if” says this inequality is exactly the definition.
Theorem: A contraction converges to a unique fixed point, no matter initialization.

A fixed point is a value table that stays unchanged when the update is applied again. “Converges” means the tables approach it as updates continue. You can initialize the values to 0, 10, or any other finite values and still approach the same table.

There cannot be two different fixed points: the update would have to leave both unchanged while also shrinking the distance between them. Both conditions can hold only when that distance is zero.
Fact: the value iteration update is a γ-contraction in max-norm

The Bellman update has exactly this shrinking property. Both tables use the same rewards, so their differences come from the future-value estimates. Taking a probability-weighted average and choosing the best action cannot enlarge the biggest disagreement; multiplying the future value by γ shrinks its bound.
Corollary: value iteration converges to a unique fixed point

Combine the theorem with the fact: value iteration is a contraction, so it approaches one fixed point from any finite initialization. That fixed point satisfies the Bellman optimality equation and is the optimal value function V*. The value function is unique; equally good actions can still give multiple optimal policies.
Additional fact:

$∥ V_{i + 1} - V_{i} ∥ < ε, \Rightarrow ∥ V_{i + 1} - V^{*} ∥ < 2 ε γ / (1 - γ)$

The left side is something we can measure: every state changed by less than ε between the last two rounds. The right side bounds something we do not yet know: the biggest difference between the current table and the optimal table.

Later updates can still change the values, but each change is at most γ times the previous one. Adding all those possible future changes gives the geometric-series factor γ/(1 − γ). The factor 2 makes the slide’s upper bound more conservative.

For γ = 0.9 and ε = 0.001, the slide guarantees an error below 0.018. This gives a stopping rule. As γ gets closer to 1, later changes fade more slowly, so the same ε gives a larger error bound.

Example: Gridworld

Gridworld with a wall at (2,2), plus-one exit at (4,3), and minus-one exit at (4,2)

Noise = 0.2
Discount = 0.9

$k = 0$

0.00	0.00	0.00	0.00
0.00		0.00	0.00
0.00	0.00	0.00	0.00

The speed of convergence often depends on the discount factor: as it gets closer to 0, value iteration generally converges faster.

Run value iteration until convergence, then extract the policy:

π^{*} (s) = \underset{a \in A}{arg max} \sum_{s^{'}} T (s, a, s^{'}) [R (s, a, s^{'}) + γ V^{*} (s^{'})]

An optimal policy can be chosen stationary: the selected action at a state is the same at all times.

Exercise 1: Effect of Discount and Noise

DiscountGrid with a yellow starting square, a close plus-one exit, a distant plus-ten exit, and a minus-ten cliff. The red path runs near the cliff; the green path travels along the top.

Behavior	γ	Noise
(a) Prefer the close exit (+1), risking the cliff (−10)	0.1	0
(b) Prefer the close exit (+1), but avoiding the cliff (−10)	0.1	0.5
(c) Prefer the distant exit (+10), risking the cliff (−10)	0.99	0
(d) Prefer the distant exit (+10), avoiding the cliff (−10)	0.99	0.5

Q-Values

$Q^{*} (s, a) =$ expected utility starting in s, taking action a, and (thereafter) acting optimally.

Bellman Equation:

Q^{*} (s, a) = \sum_{s^{'}} P (s^{'} | s, a) (R (s, a, s^{'}) + γ max_{a^{'}} Q^{*} (s^{'}, a^{'}))

The first action a is fixed. After reaching s′, choose the action a′ with the highest Q-value. Average the immediate reward plus the discounted future value over all possible next states.

Q-Value Iteration:

Q_{k + 1}^{*} (s, a) \leftarrow \sum_{s^{'}} P (s^{'} | s, a) (R (s, a, s^{'}) + γ max_{a^{'}} Q_{k}^{*} (s^{'}, a^{'}))

The Bellman equation describes the converged Q-values. Q-value iteration computes them: update every state-action pair using the previous round’s Q-values on the right-hand side, and repeat until convergence.

Example: Gridworld

Gridworld Q-values after 100 iterations. Each ordinary cell has four triangles for up, right, down, and left. At (3,2), the values are 0.57, minus 0.60, 0.30, and 0.53, respectively. — $k = 100$

Noise = 0.2, Discount = 0.9, Living reward = 0.

The top, right, bottom, and left triangles show the Q-values for moving up, right, down, and left. At (3,2), their values are approximately 0.57, −0.60, 0.30, and 0.53. Moving up has the highest Q-value.

Optimal Value Function V*

Let’s assume:

Algorithm:

Definition: max-norm

Definition: An update operation is a γ-contraction in max-norm if and only if

Theorem: A contraction converges to a unique fixed point, no matter initialization.

Fact: the value iteration update is a γ-contraction in max-norm

Corollary: value iteration converges to a unique fixed point

Additional fact:

Bellman Equation:

Q-Value Iteration:

Example: Gridworld

Optimal Value Function $V^{*}$