Value Iteration Algorithm
What you'll learn: How value iteration streamlines dynamic programming by merging policy evaluation and improvement into a single, efficient update step.
The Core Idea
Unlike policy iteration, which alternates between fully evaluating a policy and then improving it, value iteration takes a shortcut. It combines both steps into one update by directly applying the Bellman optimality equation. Instead of waiting to converge on values for the current policy, you immediately update toward the optimal value function.
Think of it like navigation: policy iteration is like fully exploring every road under your current route plan, then switching plans. Value iteration is like constantly updating to the best possible next move at each step—you're always improving toward the optimal path without dwelling on intermediate policies.
The Algorithm
At each iteration, for every state, value iteration performs:
V(s) ← max_a [R(s,a) + γ Σ P(s'|s,a) V(s')]
This is the Bellman optimality backup: you look at all possible actions, compute the expected return for each (immediate reward plus discounted future value), and take the maximum. You're essentially asking: "What's the best I could do from here?"
You repeat this for all states until the value function converges (changes become negligibly small). Once converged, you've found V*, and extracting the optimal policy is straightforward—just act greedily with respect to V*.
Why It Matters
Value iteration is often faster than policy iteration because it doesn't wait for complete policy evaluation. Each sweep through the state space simultaneously evaluates and improves, making it particularly efficient for problems where policy improvement happens quickly.
Key Takeaway: Value iteration combines evaluation and improvement using the Bellman optimality equation, converging directly to the optimal value function V* without explicit policy iteration steps.