Value Iteration

343. Value Iteration

The standard algorithm for solving infinite-horizon Markov Decision Processes. Iteratively applies the Bellman equation until the value function converges.

343.1. Infinite-horizon discounted MDP

States $𝒮︀$ , actions $𝒜︀$ , transition $𝑃 (𝑠^{'} | 𝑠, 𝑎)$ , immediate cost $𝑐 (𝑠, 𝑎)$ , discount factor $𝛾 \in (0, 1)$ .

Objective: minimize expected discounted total cost over an infinite horizon:

𝐽^{𝜋} (𝑠) = 𝐸 [\sum_{𝑡 = 0}^{\infty} 𝛾^{𝑡} 𝑐 (𝑠_{𝑡}, 𝜋 (𝑠_{𝑡})) | 𝑠_{0} = 𝑠]

Since rewards / costs in the far future are exponentially discounted, the sum converges.

343.2. Bellman optimality equation (infinite horizon)

𝐽^{*} (𝑠) = min_{𝑎 \in 𝒜︀} {𝑐 (𝑠, 𝑎) + 𝛾 \sum_{𝑠^{'}} 𝑃 (𝑠^{'} | 𝑠, 𝑎) 𝐽^{*} (𝑠^{'})}

This is a fixed-point equation: $𝐽^{*} = 𝒯︀ 𝐽^{*}$ where $𝒯︀$ is the Bellman operator. The operator is a contraction (with contraction factor $𝛾$ ), so the fixed point is unique and reachable by iteration.

343.3. Algorithm

Initialize J(s) ← 0 (or any function)

Repeat until convergence:
    For each s ∈ S:
        J'(s) ← min over a of { c(s, a) + γ Σ_{s'} P(s' | s, a) J(s') }
    J ← J'

Return optimal policy:
    π*(s) ← argmin over a of { c(s, a) + γ Σ_{s'} P(s' | s, a) J(s') }

Convergence test: stop when ${max}_{𝑠} | 𝐽^{'} (𝑠) - 𝐽 (𝑠) | < 𝜀$ .

343.4. Why it converges

The Bellman operator $𝒯︀$ is a $𝛾$ -contraction under the sup-norm:

‖ 𝒯︀ 𝐽_{1} - 𝒯︀ 𝐽_{2} ‖_{\infty} \leq 𝛾 ‖ 𝐽_{1} - 𝐽_{2} ‖_{\infty}

By Banach fixed-point theorem, iterating from any starting $𝐽$ converges geometrically to the unique fixed point $𝐽^{*}$ :

‖ 𝐽^{(𝑘)} - 𝐽^{*} ‖_{\infty} \leq 𝛾^{𝑘} ‖ 𝐽^{(0)} - 𝐽^{*} ‖_{\infty}

343.5. Convergence rate

Geometric in $𝛾$ . To get within $𝜀$ of $𝐽^{*}$ takes about

𝑘 = \frac{log 𝜀}{log 𝛾} iterations

If $𝛾$ is close to 1 (long-horizon problems), convergence is slow. Acceleration tricks:

Gauss-Seidel updates (update $𝐽 (𝑠)$ in-place using already-updated neighbors)
Prioritized sweeping (update states with large Bellman residuals first)
Approximate value iteration (function approximation for large state spaces)

343.6. Cost per iteration

$𝑂 (| 𝒮︀ |^{2} \cdot | 𝒜︀ |)$ — for each state ( $| 𝒮︀ |$ ), for each action ( $| 𝒜︀ |$ ), sum over next states ( $| 𝒮︀ |$ ).

343.7. Value iteration vs policy iteration

	Value iteration	Policy iteration
Iterates on	Value function $𝐽$	Policy $𝜋$
Per iteration cost	Cheap ( $𝑂 (\| 𝒮︀ \|^{2} \| 𝒜︀ \|)$ )	Expensive (full policy evaluation: solve linear system)
Iterations to converge	Many (geometric in $𝛾$ )	Few (often $\leq \| 𝒮︀ \|$ iterations)
Total cost	Comparable in practice	Comparable
Anytime?	Yes — returns a usable $𝐽$ at any point	Only at policy-iteration end

See Policy Iteration for the alternative.

343.8. Example application

Inventory management with infinite horizon: state = on-hand inventory, action = order quantity, transition = stochastic demand. Value iteration finds the optimal $(𝑠, 𝑆)$ policy.