Value Iteration

A Markov Decision Process is a tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ with states $\mathcal{S}$, actions $\mathcal{A}$, transition kernel $P(s'\mid s,a)$, reward function $R(s,a,s')$, and discount factor $\gamma \in [0,1)$. The optimal value function $v_*(s)$ is defined as the maximum expected discounted return achievable from state $s$, and it satisfies the Bellman Optimality Equation:

Policy Iteration solves for $v_*$ indirectly: it picks a policy $\pi$, computes $v_\pi$ exactly (or to convergence) by solving the linear Bellman expectation equations, then improves $\pi$ greedily with respect to $v_\pi$, and repeats. The evaluation step is the expensive part — it is itself an iterative or linear-algebraic sub-procedure nested inside the outer improvement loop. Value Iteration observes that you do not need to fully evaluate a policy before improving it. Define the Bellman optimality operator $T^*$ acting on any value function $v$ by

Value Iteration simply iterates $v_{k+1} = T^* v_k$ starting from an arbitrary $v_0$ (commonly all zeros). Each application of $T^*$ is exactly one truncated policy-evaluation sweep in which the policy used is always "act greedily with respect to the current value estimate" — improvement and evaluation happen in the same line of arithmetic. There is no separate policy object maintained during the main loop; the policy is only extracted once, at the end, by taking $\arg\max_a$ against the converged (or near-converged) value function.

The algorithm operates entirely on a value table indexed by state. On each sweep, every state's value is replaced by the best one-step lookahead value, using the current estimates of successor states (this can be done synchronously, storing new values in a separate array, or asynchronously/in-place, updating a single array as you go — both converge, in-place typically faster in practice). ``` ALGORITHM ValueIteration(S, A, P, R, gamma, theta) Input: states S, actions A, transition model P, reward R, discount gamma in [0,1), small threshold theta > 0 Output: value function V approximating v, greedy policy pi // Initialization for each s in S: V[s] <- 0 // or any bounded initial guess // Main loop: repeated Bellman optimality backups repeat delta <- 0 for each s in S: v_old <- V[s] // Bellman optimality backup: evaluate every action, take the best V[s] <- max over a in A of ( sum over s' of P(s' | s, a) ( R(s, a, s') + gamma V[s'] ) ) delta <- max(delta, |v_old - V[s]|) until delta < theta // Policy extraction: one greedy sweep using the (near-)converged V for each s in S: pi[s] <- argmax over a in A of ( sum over s' of P(s' | s, a) ( R(s, a, s') + gamma * V[s'] ) ) return V, pi ``` Two implementation variants matter in practice:

• Synchronous (Jacobi-style) updates: compute all new values from a frozen copy of $V$, then swap buffers. Easier to reason about, matches the textbook contraction proof exactly per sweep.
• Asynchronous / in-place (Gauss–Seidel-style) updates: overwrite $V[s]$ immediately and let subsequent states in the same sweep use the fresh value. This still converges to $v_*$ under standard conditions (every state updated infinitely often) and typically converges faster because information propagates within a single sweep instead of waiting a full iteration.

The stopping rule `delta < theta` is a practical proxy for "close enough to the fixed point." Because $T^*$ is a contraction (proved below), the sequence $V$ is guaranteed to keep shrinking its distance to $v_*$, and the sweep-to-sweep change `delta` gives a computable, machine-checkable stand-in for the (unobservable) true error $\|V - v_*\|_\infty$.

Per-sweep time complexity. For a tabular MDP with $|\mathcal{S}|$ states and $|\mathcal{A}|$ actions, each state's backup evaluates every action, and each action's evaluation sums over all possible successor states. In the worst case (dense transitions) this is $O(|\mathcal{S}|)$ work per action, so one sweep costs

If the transition model is sparse — each $(s,a)$ pair has at most $b$ possible successors (a branching factor) — the cost drops to $O(|\mathcal{S}| |\mathcal{A}| b)$ per sweep. Space is $O(|\mathcal{S}|)$ for the value table (plus the transition model storage, which is input-dependent and not part of the algorithm's own footprint).

Number of sweeps. Unlike a comparison sort or graph search, Value Iteration does not have a finite exact termination bound in general — convergence is asymptotic. To get within $\epsilon$ of $v_*$ in max-norm, the number of sweeps needed is

derived directly from the contraction rate below. As $\gamma \to 1$, $\log(1/\gamma) \to 0$ and $K \to \infty$ — long-horizon, near-undiscounted problems are the slow case. Total time to reach $\epsilon$-accuracy is therefore $O(|\mathcal{S}|^2|\mathcal{A}| \cdot K)$.

Correctness — the contraction mapping argument. Correctness rests on showing $T^*$ is a contraction mapping in the max-norm $\|u\|_\infty = \max_s |u(s)|$. For any two value functions $u, w$:

where $Q_v(s,a) = \sum_{s'}P(s'\mid s,a)[R(s,a,s')+\gamma v(s')]$, and the inequality uses the standard fact that $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a)-g(a)|$. Continuing,

since $P(\cdot\mid s,a)$ is a probability distribution summing to 1. Taking the max over $s$ gives

Because $\gamma < 1$, $T^*$ is a $\gamma$-contraction. By the Banach fixed-point theorem, a contraction on a complete metric space (here, $\mathbb{R}^{|\mathcal{S}|}$ with the max-norm, which is complete) has a unique fixed point, and iterating the map from any starting point converges to that fixed point:

That the fixed point of $T^*$ actually equals $v_*$ follows from the Bellman optimality equation itself: $v_*$ is defined as satisfying $v_* = T^*v_*$, so $v_*$ is a fixed point, and uniqueness of fixed points under a contraction guarantees it is the only one Value Iteration can converge to, regardless of initialization.

Policy correctness. Once $\|V_k - v_*\|_\infty \le \epsilon$, the greedy policy $\pi_k$ extracted from $V_k$ is not merely near-optimal in value but can be shown to be exactly optimal once $\epsilon$ is small enough relative to the gap between the best and second-best action at each state (a standard result: greedy policies with respect to sufficiently accurate value estimates are exactly greedy with respect to $v_*$, because $\arg\max$ is locally constant away from ties). In practice this means Value Iteration typically discovers the optimal policy well before the value function has converged numerically to high precision — a useful fact when deciding when to stop.

Tradeoffs versus Policy Iteration. Policy Iteration's evaluation phase can also be run inexactly (this is precisely the family of algorithms interpolating between the two, called modified or generalized policy iteration), but pure Policy Iteration solves each evaluation step exactly via linear algebra in $O(|\mathcal{S}|^3)$ per iteration and typically needs fewer outer iterations, since each is a full evaluation-plus-improvement. Value Iteration needs more sweeps but each is cheap and matrix-free — no linear system to solve — making it the default choice when $|\mathcal{S}|$ is large or the transition matrix is sparse.

Consider a tiny 1-D corridor MDP with three non-terminal states $\{1, 2, 3\}$ and a terminal goal state $G$ to the right of state 3, with a terminal pit $H$ to the left of state 1. Actions are `Left` and `Right`; each action succeeds deterministically. Reward is $-1$ for every step except entering $G$ (reward $+10$) or entering $H$ (reward $-10$); both are absorbing (episode ends, value $0$ thereafter). Discount $\gamma = 0.9$. Layout: `H — [1] — [2] — [3] — G` Transitions:

Initialize $V_0(1)=V_0(2)=V_0(3)=0$. Apply synchronous Bellman optimality backups.

Sweep 1 (using $V_0$, all zeros for non-terminal successors, and $V(H)=V(G)=0$ fixed):

Sweep 2 (using $V_1 = (-1,-1,10)$):

Sweep 3 (using $V_2 = (-1.9,\ 8.0,\ 10)$):

wait — recompute carefully: $V_3(2)$ uses $V_2(1)=-1.9$ and $V_2(3)=10$:

So $V_3 = (6.2,\ 8.0,\ 10)$.

Sweep 4 (using $V_3$):

Values have stabilized: $V_4 = (6.2, 8.0, 10) = V_3$. `delta = 0`, so the loop terminates.

Policy extraction from $V_4$:

• State 1: `Left` gives $-10$; `Right` gives $-1+0.9(8.0)=6.2$ → $\pi(1)=$ Right.
• State 2: `Left` gives $-1+0.9(6.2)=4.58$; `Right` gives $-1+0.9(10)=8.0$ → $\pi(2)=$ Right.
• State 3: `Left` gives $6.2$; `Right` gives $10$ → $\pi(3)=$ Right.

The recovered optimal policy is "always move Right toward the goal" everywhere — matching intuition, and obtained in just 4 sweeps for this small chain despite $\gamma$ being close to 1.

Value Iteration's roots lie in the mathematics of dynamic programming developed for sequential decision-making under uncertainty, later formalized specifically as MDP algorithms and adopted wholesale by reinforcement learning.

Value Iteration is the workhorse of planning when a full model of the environment (transition and reward functions) is available. Classical robotics motion-planning systems use it (or its variants) to compute cost-to-go functions over discretized state spaces before a robot ever executes a trajectory. Operations-research applications — inventory control, admission control in queueing systems, maintenance scheduling — rely on exactly this fixed-point iteration to compute optimal policies offline. In reinforcement learning specifically, Value Iteration is the conceptual ancestor of Q-learning: replacing the exact expectation $\sum_{s'} P(s'\mid s,a)[\cdots]$ with a sampled transition turns the tabular Bellman optimality backup into an online, model-free update. Deep Q-Networks (DQN) and its successors approximate the same backup with a neural network in place of a table, inheriting the same fixed-point intuition (though losing the clean contraction guarantee due to function approximation and sampling noise). Value Iteration Networks, a differentiable neural architecture, even embed the Value Iteration computation itself as a layer inside a learned planner. Anywhere an agent needs to compute "the best achievable value from every state, given known dynamics," some form of this algorithm — or a sampled, function-approximated relaxation of it — is doing the work.

Ask the tutor: How does replacing the exact expectation in the Bellman optimality backup with a single sampled transition turn Value Iteration into Q-learning?