Value-Based Methods

Imagine you're designing an autonomous navigation system. Your robot stands at the entrance of an unfamiliar building, tasked with finding the shortest path to a specific room while avoiding obstacles and minimizing energy consumption. How should it decide which direction to move at each intersection? What makes one policy—a mapping from situations to actions—better than another?

Value iteration answers these questions by computing the optimal value of every possible state: the maximum expected cumulative reward an agent can achieve starting from that state and acting optimally thereafter. Once we know these optimal values, the optimal policy falls out naturally—simply choose actions that lead to states with the highest values.

This elegant algorithm, rooted in the principle of dynamic programming, was formalized by Richard Bellman in the 1950s and remains foundational to modern reinforcement learning. It provides both a theoretical cornerstone and a practical algorithm that, under the right conditions, provably converges to optimal solutions.

Value iteration is built upon one of the most profound insights in sequential decision-making: Bellman's Principle of Optimality.

"An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision." — Richard Bellman, 1957

This principle states that optimal behavior decomposes recursively. If you're taking the optimal path from A to C through B, then the segment from B to C must also be optimal. This self-consistency is captured mathematically by the Bellman equations.

Formal Definition of Optimal Value Functions

Recall from the MDP framework that a policy $\pi: S \to A$ (or more generally $\pi: S \to \Delta(A)$ for stochastic policies) specifies how an agent selects actions. The state-value function under policy $\pi$ is:

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

This measures the expected cumulative discounted reward starting from state $s$ and following policy $\pi$ thereafter.

The optimal value function $V^*$ represents the best achievable value:

$$V^*(s) = \max_\pi V^\pi(s) \quad \text{for all } s \in S$$

Similarly, the optimal action-value (Q) function is:

$$Q^*(s, a) = \max_\pi Q^\pi(s, a)$$

where $Q^\pi(s, a)$ denotes the expected return when taking action $a$ in state $s$ and following $\pi$ thereafter.

The Bellman Optimality Equations

The optimal value function satisfies a remarkable self-consistency condition—the Bellman optimality equation:

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

Let's unpack each component:

The equation says: the optimal value of a state equals the immediate reward plus the discounted expected optimal value of the next state, maximized over all possible actions.

The Bellman optimality equation defines $V^*$ implicitly—but how do we actually compute it? Value iteration is the answer: an iterative algorithm that repeatedly applies the Bellman optimality operator until convergence.

The Bellman Optimality Operator

Define the Bellman optimality operator $T^*$ that maps a value function $V$ to a new value function:

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

The optimal value function $V^$ is a fixed point of this operator: $T^ V^* = V^*$.

The Algorithm

Value iteration repeatedly applies $T^*$ starting from an arbitrary initialization:

1. Initialize $V_0(s)$ arbitrarily for all states (commonly to 0)
2. Repeat for $k = 0, 1, 2, \ldots$:
   • For each state $s \in S$: $$V_{k+1}(s) = \max_{a \in A(s)} \left[ R(s, a) + \gamma \sum_{s' \in S} P(s' | s, a) V_k(s') \right]$$
   • Compute $\delta = \max_s |V_{k+1}(s) - V_k(s)|$
3. Until $\delta < \theta$ (convergence threshold)
4. Extract policy: $\pi^(s) = \arg\max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s' | s, a) V^(s') \right]$

A critical question: does value iteration actually converge to $V^*$? The answer is yes, and the proof relies on the contraction mapping theorem.

The Bellman Operator is a Contraction

Definition (Contraction Mapping): A mapping $T: X \to X$ on a metric space $(X, d)$ is a contraction if there exists $\gamma \in [0, 1)$ such that for all $x, y \in X$: $$d(Tx, Ty) \leq \gamma \cdot d(x, y)$$

Theorem: The Bellman optimality operator $T^$ is a $\gamma$-contraction under the sup-norm (infinity norm): $$|T^ V_1 - T^* V_2|\infty \leq \gamma |V_1 - V_2|\infty$$

Proof: For any state $s$, $$ \begin{aligned} |(T^* V_1)(s) - (T^* V_2)(s)| &= \left| \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_1(s') \right] - \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_2(s') \right] \right| &\leq \max_a \gamma \left| \sum_{s'} P(s'|s,a) (V_1(s') - V_2(s')) \right| &\leq \gamma \max_a \sum_{s'} P(s'|s,a) |V_1(s') - V_2(s')| &\leq \gamma |V_1 - V_2|_\infty \end{aligned} $$

The second step uses the property $|\max f - \max g| \leq \max |f - g|$.

Convergence Rate Analysis

Since $T^$ is a $\gamma$-contraction, we have: $$|V_k - V^|\infty \leq \gamma^k |V_0 - V^*|\infty$$

This gives us linear convergence with rate $\gamma$. The number of iterations needed to achieve $\epsilon$-accuracy is:

$$k \geq \frac{\log(|V_0 - V^*|_\infty / \epsilon)}{\log(1/\gamma)}$$

Practical implication: When $\gamma$ is close to 1 (e.g., 0.99 for long-horizon problems), convergence is slow. Each iteration multiplies the error by $\gamma$, so at $\gamma = 0.99$, we need approximately $\log(1/\epsilon) / 0.01 \approx 460$ iterations to reduce error by a factor of 100.

Let's apply value iteration to a concrete problem: the classic Gridworld environment. This example illuminates how value iteration propagates value information through the state space.

Problem Setup

Consider a 4×4 grid with:

• States: 16 cells, numbered 0–15 (row-major order)
• Actions: North, South, East, West (deterministic movement)
• Terminal states: Cell 0 (top-left) and Cell 15 (bottom-right)
• Rewards: -1 for each step (incentivizes reaching terminal states quickly)
• Boundaries: Moving into a wall keeps the agent in place

This is an episodic task: episodes end when reaching a terminal state.

Iteration-by-Iteration Analysis

Let's trace value propagation through iterations:

Iteration 0 (Initial $V_0 = 0$ everywhere):

• All non-terminal states update to $V_1(s) = -1$ (immediate reward)
• Terminal states remain $V(0) = V(15) = 0$

Iteration 1:

• States adjacent to terminals: $V_2(1) = V_2(4) = -1 + 1 \cdot 0 = -1$ (can reach terminal)
• States two steps away: $V_2(5) = -1 + 1 \cdot (-1) = -2$

Subsequent iterations:

• Value propagates outward from terminal states
• Each iteration extends the "horizon" of foresight by one step
• States learn their true distance (in expected steps) to terminals

Understanding the computational requirements of value iteration is essential for practical deployment. Let's analyze time and space complexity rigorously.

Time Complexity

Per-iteration cost: For each state $s$, we compute: $$V_{k+1}(s) = \max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V_k(s') \right]$$

• Inner sum over $s'$: $O(|S|)$ per action
• Max over actions: $O(|A|)$
• Total per state: $O(|A| \cdot |S|)$
• Total per iteration: $O(|S| \cdot |A| \cdot |S|) = O(|S|^2 \cdot |A|)$

Number of iterations: From convergence analysis, approximately $O\left(\frac{1}{1-\gamma} \log\frac{1}{\epsilon}\right)$ iterations.

Total time complexity: $$O\left(\frac{|S|^2 \cdot |A|}{1-\gamma} \log\frac{1}{\epsilon}\right)$$

Space Complexity

Value iteration is remarkably space-efficient:

• Value function storage: $O(|S|)$
• Transition model: $O(|S|^2 \cdot |A|)$ if stored explicitly
• Total: $O(|S|^2 \cdot |A|)$ dominated by the MDP model

Sparse transitions: Many real MDPs have sparse transitions—each action leads to only a few possible next states. With sparsity factor $k$ (average non-zero transitions per state-action):

• Per-iteration: $O(|S| \cdot |A| \cdot k)$
• Model storage: $O(|S| \cdot |A| \cdot k)$

This makes value iteration practical for much larger state spaces when dynamics are sparse.

Several techniques can accelerate value iteration or improve its practicality:

1. Gauss-Seidel (In-Place) Updates

Instead of computing all new values before any update, use new values immediately:

for s in range(num_states):
    V[s] = max_a [R(s,a) + gamma * sum_s' P(s'|s,a) * V[s']]

This in-place variant often converges faster because updates propagate immediately. The convergence guarantee still holds (asynchronous DP), though the convergence rate analysis differs.

2. Prioritized Sweeping

Not all states need equal attention. Prioritized sweeping maintains a priority queue based on the magnitude of the last update (Bellman error):

1. Update the state with the highest priority
2. For states that could be affected (predecessors), update their priority based on how much the current update could change them
3. Repeat

This focuses computation where it matters most—states with large value changes that will propagate to others.

3. Policy Iteration vs Value Iteration

An alternative algorithm, policy iteration, separates policy evaluation (computing $V^\pi$ for fixed $\pi$) from policy improvement (finding a better policy).

Policy iteration often converges in fewer iterations but each iteration is more expensive.

Deploying value iteration in practice requires attention to implementation details that theory often glosses over.

Numerical Stability

Reward scaling: If rewards are very large or very small, numerical precision issues can arise. Normalize rewards to a reasonable range (e.g., [-1, 1] or [0, 1]).

Discount factor near 1: When $\gamma \approx 1$, values can grow very large. Consider using undiscounted episodic formulations where possible, or track value differences rather than absolute values.

Initialization: While any initialization converges, starting close to the true values (if you have a heuristic) speeds convergence.

When to Use Value Iteration

Good fit:

• Small to medium state spaces (< 10^6 states)
• Known, tabular MDP model (P and R available)
• High accuracy required
• Offline planning (compute once, execute many times)

Poor fit:

• Large/continuous state spaces → function approximation needed
• Unknown dynamics → model-free methods (Q-learning, policy gradient)
• Online learning → sample-based methods
• Continuous actions → policy-based methods

Value iteration is the cornerstone algorithm for computing optimal value functions in Markov Decision Processes. Let's consolidate what we've learned:

What's next: Value iteration requires a complete model of the environment—transition probabilities and rewards. But what if we don't have this model and must learn from experience? The next page introduces Q-learning, a model-free algorithm that learns optimal action-values directly from observed transitions.