Value Iteration

Why Does This Exist?

In reinforcement learning, when an agent possesses complete knowledge of the environment's transition dynamics and reward model—formalized as a Markov Decision Process—it can compute the optimal policy directly using dynamic programming.

The classic approach, Policy Iteration, decomposes this goal into two strict, alternating phases:

1. Policy Evaluation: Compute the exact state values $V^\pi$ for the current policy $\pi$, which requires either inverting a $|\mathcal{S}| \times |\mathcal{S}|$ transition matrix or running many iterative sweeps until values converge to high precision.
2. Policy Improvement: Greedily update the policy with respect to the freshly calculated $V^\pi$.

In practice, full policy evaluation is computationally wasteful. The greedy action choices often lock into their optimal choices after only a few sweeps, long before the numerical value estimates converge to multiple decimal places.

Value Iteration solves this inefficiency by truncating policy evaluation after exactly one sweep. Instead of evaluating a candidate policy to convergence before improving it, Value Iteration merges evaluation and greedy improvement into a single update. Every sweep directly applies the Bellman optimality equation with a $\max$ operator over all possible actions. The algorithm operates entirely in value space, deferring explicit policy extraction until the value function has contracted to near-optimality.

Think of It Like This

How It Actually Works

The Bellman optimality operator and truncated policy evaluation

Consider a finite Markov Decision Process $(\mathcal{S}, \mathcal{A}, p, \gamma)$, where:

• $\mathcal{S}$ is the finite set of environmental states.
• $\mathcal{A}(s)$ is the set of actions available in state $s$.
• $p(s', r \mid s, a) = \mathbb{P}(S_{t+1} = s', R_{t+1} = r \mid S_t = s, A_t = a)$ is the joint transition and reward probability function.
• $\gamma \in [0, 1)$ is the temporal discount factor.

The optimal state-value function $V^*(s)$ represents the maximum expected discounted return attainable from state $s$ under any policy. It satisfies the non-linear Bellman Optimality Equation:

$V^*(s) = \max_{a \in \mathcal{A}(s)} \sum_{s' \in \mathcal{S}} \sum_{r} p(s', r \mid s, a) \left[ r + \gamma V^*(s') \right]$

Equivalently, letting expected immediate reward be $\mathcal{R}(s, a) = \sum_{s', r} r\, p(s', r \mid s, a)$ and transition dynamics be $\mathcal{P}(s' \mid s, a) = \sum_{r} p(s', r \mid s, a)$:

$V^*(s) = \max_{a \in \mathcal{A}(s)} \left[ \mathcal{R}(s, a) + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}(s' \mid s, a) V^*(s') \right]$

Value Iteration turns this mathematical identity into an iterative update rule. Starting with an arbitrary initial value array $V_0$ (typically all zeros), it repeatedly updates each state:

$V_{k+1}(s) \leftarrow \max_{a \in \mathcal{A}(s)} \left[ \mathcal{R}(s, a) + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}(s' \mid s, a) V_k(s') \right] \quad \forall s \in \mathcal{S}$

The Bellman optimality operator ($\mathcal{T}^*$)

We can define the Bellman optimality backup as an operator $\mathcal{T}^*: \mathbb{R}^{|\mathcal{S}|} \to \mathbb{R}^{|\mathcal{S}|}$:

$(\mathcal{T}^* V)(s) = \max_{a \in \mathcal{A}(s)} \left[ \mathcal{R}(s, a) + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}(s' \mid s, a) V(s') \right]$

Value iteration is simply the successive application of this operator: $V_{k+1} = \mathcal{T}^* V_k$.

Contraction mapping and convergence guarantee

Under the supremum norm (infinity norm) $\|V\|_\infty = \max_{s \in \mathcal{S}} |V(s)|$, the operator $\mathcal{T}^*$ is a $\gamma$-contraction mapping:

$\|\mathcal{T}^* U - \mathcal{T}^* V\|_\infty \le \gamma \|U - V\|_\infty \quad \forall U, V \in \mathbb{R}^{|\mathcal{S}|}$

Because $0 \le \gamma < 1$, the Banach Fixed-Point Theorem delivers three vital guarantees:

1. Uniqueness: There is exactly one fixed-point value function $V^*$ such that $\mathcal{T}^* V^* = V^*$.
2. Global convergence: Starting from any arbitrary initial vector $V_0$, the sequence $V_{k+1} = \mathcal{T}^* V_k$ converges to $V^*$ as $k \to \infty$.
3. Geometric rate: The distance to the optimal value function shrinks by at least factor $\gamma$ on every sweep:

$\|V_{k+1} - V^*\|_\infty \le \gamma \|V_k - V^*\|_\infty \le \gamma^{k+1} \|V_0 - V^*\|_\infty$

Stopping threshold and policy extraction

In practice, sweeps continue until the maximum change across all states falls below a small positive tolerance $\theta$:

$\Delta = \max_{s \in \mathcal{S}} |V_{k+1}(s) - V_k(s)| < \theta$

Once convergence is reached, the deterministic optimal policy $\pi^*(s)$ is extracted through a single one-step greedy lookahead:

$\pi^*(s) = \arg\max_{a \in \mathcal{A}(s)} \left[ \mathcal{R}(s, a) + \gamma \sum_{s' \in \mathcal{S}} \mathcal{P}(s' \mid s, a) V(s') \right]$

Worked numerical example

Consider an MDP with 3 states $\mathcal{S} = \{s_1, s_2, s_3\}$ and discount factor $\gamma = 0.8$.

• State $s_3$ is a terminal absorption state: $V(s_3) \equiv 0.0$.
• Actions available in non-terminal states are $\mathcal{A} = \{a_1, a_2\}$:
  • From $s_1$:
    • Action $a_1$ advances to $s_2$ with $r = 0.0$: $Q(s_1, a_1) = 0.0 + 0.8\, V(s_2)$.
    • Action $a_2$ exits immediately to terminal $s_3$ with $r = 2.0$: $Q(s_1, a_2) = 2.0 + 0.8\, V(s_3) = 2.0$.
  • From $s_2$:
    • Action $a_1$ exits directly to terminal $s_3$ with high reward $r = 10.0$: $Q(s_2, a_1) = 10.0 + 0.8\, V(s_3) = 10.0$.
    • Action $a_2$ loops back to $s_1$ with minor reward $r = 1.0$: $Q(s_2, a_2) = 1.0 + 0.8\, V(s_1)$.

Initialization ($k = 0$)

$V_0(s_1) = 0.0, \quad V_0(s_2) = 0.0, \quad V_0(s_3) = 0.0$

Sweep 1 ($k = 1$)

Calculate candidate action values for each state:

• For $s_1$: $Q_0(s_1, a_1) = 0.0 + 0.8 \times V_0(s_2) = 0.0 + 0.8(0.0) = 0.0$ $Q_0(s_1, a_2) = 2.0 + 0.8 \times V_0(s_3) = 2.0 + 0.8(0.0) = 2.0$ $V_1(s_1) = \max(0.0, 2.0) = 2.0 \quad (\text{Greedy choice: } a_2)$
• For $s_2$: $Q_0(s_2, a_1) = 10.0 + 0.8 \times V_0(s_3) = 10.0 + 0.8(0.0) = 10.0$ $Q_0(s_2, a_2) = 1.0 + 0.8 \times V_0(s_1) = 1.0 + 0.8(0.0) = 1.0$ $V_1(s_2) = \max(10.0, 1.0) = 10.0 \quad (\text{Greedy choice: } a_1)$

Max change: $\Delta_1 = \max(|2.0 - 0.0|, |10.0 - 0.0|) = 10.0$.

Sweep 2 ($k = 2$)

Apply the Bellman optimality backup using updated values $V_1 = [2.0, 10.0, 0.0]$:

• For $s_1$: $Q_1(s_1, a_1) = 0.0 + 0.8 \times V_1(s_2) = 0.0 + 0.8(10.0) = 8.0$ $Q_1(s_1, a_2) = 2.0 + 0.8 \times V_1(s_3) = 2.0 + 0.8(0.0) = 2.0$ $V_2(s_1) = \max(8.0, 2.0) = 8.0 \quad (\text{Greedy choice flips to } a_1!)$
• For $s_2$: $Q_1(s_2, a_1) = 10.0 + 0.8 \times V_1(s_3) = 10.0 + 0.8(0.0) = 10.0$ $Q_1(s_2, a_2) = 1.0 + 0.8 \times V_1(s_1) = 1.0 + 0.8(2.0) = 1.0 + 1.6 = 2.6$ $V_2(s_2) = \max(10.0, 2.6) = 10.0 \quad (\text{Greedy choice: } a_1)$

Max change: $\Delta_2 = \max(|8.0 - 2.0|, |10.0 - 10.0|) = 6.0$.

The high downstream reward at $s_2$ has backed up into $s_1$. The greedy choice at $s_1$ flipped from the immediate short-term reward of $a_2$ ($r = 2.0$) to the delayed path $a_1$ ($Q = 8.0$).

Sweep 3 ($k = 3$)

• For $s_1$: $V_3(s_1) = \max(0.0 + 0.8(10.0), 2.0) = 8.0$.
• For $s_2$: $V_3(s_2) = \max(10.0, 1.0 + 0.8(8.0)) = \max(10.0, 7.4) = 10.0$.

Max change: $\Delta_3 = \max(|8.0 - 8.0|, |10.0 - 10.0|) = 0.0$.

The values have converged exactly in 3 sweeps:

• Optimal values: $V^*(s_1) = 8.0, \; V^*(s_2) = 10.0, \; V^*(s_3) = 0.0$.
• Optimal policy: $\pi^*(s_1) = a_1, \; \pi^*(s_2) = a_1$.

Code

1from typing import Dict, List, Tuple2
3def value_iteration(4    states: List[int],5    actions: List[int],6    transitions: Dict[Tuple[int, int], List[Tuple[float, int, float]]],7    gamma: float = 0.8,8    theta: float = 1e-6,9) -> Tuple[Dict[int, float], Dict[int, int]]:10    """11    Computes the optimal value function and policy using Value Iteration.12
13    Args:14        states: List of state identifiers.15        actions: List of action identifiers.16        transitions: Mapping of (s, a) -> list of (probability, s_next, reward).17        gamma: Discount factor in range [0, 1).18        theta: Convergence threshold for stopping sweeps.19
20    Returns:21        V: Optimal state values mapping state to value.22        policy: Optimal deterministic policy mapping state to best action.23    """24    V: Dict[int, float] = {s: 0.0 for s in states}25
26    while True:27        delta: float = 0.028        V_new = V.copy()29
30        for s in states:31            q_values: Dict[int, float] = {}32            for a in actions:33                outcomes = transitions.get((s, a), [])34                if outcomes:35                    q_values[a] = sum(36                        prob * (reward + gamma * V[s_next])37                        for prob, s_next, reward in outcomes38                    )39
40            if q_values:41                best_value = max(q_values.values())42                delta = max(delta, abs(best_value - V[s]))43                V_new[s] = best_value44
45        V = V_new46        if delta < theta:47            break48
49    # Extract optimal policy via 1-step greedy lookahead50    policy: Dict[int, int] = {}51    for s in states:52        q_values = {}53        for a in actions:54            outcomes = transitions.get((s, a), [])55            if outcomes:56                q_values[a] = sum(57                    prob * (reward + gamma * V[s_next])58                    for prob, s_next, reward in outcomes59                )60        if q_values:61            policy[s] = max(q_values, key=lambda a: q_values[a])62
63    return V, policy64
65
66# Environment configuration: 3-state MDP matching worked example67# States: 0 (s1), 1 (s2), 2 (s3 terminal)68# Actions: 0 (a1), 1 (a2)69transitions: Dict[Tuple[int, int], List[Tuple[float, int, float]]] = {70    (0, 0): [(1.0, 1, 0.0)],   # (s1, a1) -> s2, r=0.071    (0, 1): [(1.0, 2, 2.0)],   # (s1, a2) -> s3, r=2.072    (1, 0): [(1.0, 2, 10.0)],  # (s2, a1) -> s3, r=10.073    (1, 1): [(1.0, 0, 1.0)],   # (s2, a2) -> s1, r=1.074}75
76states = [0, 1, 2]77actions = [0, 1]78
79optimal_values, optimal_policy = value_iteration(80    states=states,81    actions=actions,82    transitions=transitions,83    gamma=0.8,84    theta=1e-6,85)86
87print("Optimal Values:", {f"s{s+1}": round(v, 2) for s, v in optimal_values.items()})88print("Optimal Policy:", {f"s{s+1}": f"a{a+1}" for s, a in optimal_policy.items()})89# -> Optimal Values: {'s1': 8.0, 's2': 10.0, 's3': 0.0}90# -> Optimal Policy: {'s1': 'a1', 's2': 'a1'}

Watch Out For

The Quick Version

• Value Iteration truncates policy evaluation after a single sweep, directly combining evaluation and greedy improvement into a single Bellman optimality backup.
• It operates strictly in value space without maintaining or evaluating intermediate policies; an optimal policy is extracted via greedy lookahead once values converge.
• The Bellman optimality operator $\mathcal{T}^*$ is a $\gamma$-contraction mapping under the infinity norm, guaranteeing geometric convergence to a unique optimal value function $V^*$.
• Calibrate the stopping threshold $\theta$ against $\frac{\delta(1 - \gamma)}{2\gamma}$ to prevent terminating prematurely when $\gamma$ is close to 1.

What to Read Next

• Policy Iteration
• Bellman Equations
• Dynamic Programming in RL
• Asynchronous Dynamic Programming
• Tabular Solution Methods