Implementing Value Iteration from Scratch
What you'll learn: You'll build a complete value iteration algorithm for a grid world MDP and watch it learn the optimal policy through iterative refinement.
The Core Implementation
Value iteration repeatedly applies Bellman backups until the value function converges. For a grid world, this means:
- Initialize all state values to zero (or arbitrarily)
- Iterate through each state, computing the maximum expected value across all actions
- Update the value of that state using the Bellman optimality equation
- Repeat until changes fall below a threshold (convergence)
- Extract the greedy policy from the converged values
Think of it like water finding its level: values "flow" from high-reward states to their neighbors until equilibrium is reached.
Implementation Structure
Your code needs:
- A grid environment with walls, rewards, and terminal states
- A transition function returning next states and probabilities for each action
- The value iteration loop performing Bellman backups
- Convergence tracking to monitor the maximum value change (delta)
- Policy extraction by choosing the action maximizing expected value at each state
- Visualization showing value heatmaps and policy arrows over iterations
Watching It Learn
As iterations progress, you'll see values propagate backward from goal states. States near rewards update first, then their neighbors, creating expanding "waves" of value. The policy arrows initially point randomly, then gradually align toward optimal paths as values stabilize.
Track both the value function (how good is each state?) and the extracted policy (what action should I take?). Convergence typically happens when max_delta < threshold (often 0.001).
Key Takeaway: Value iteration transforms the Bellman optimality equation into a practical algorithm—initialize, iterate Bellman backups across all states, check convergence, and extract the greedy policy from converged values.