Course contentsShow
← Machine Learning and Deep Learning
Lesson 2170 of 3,53846. Reinforcement Learning: FundamentalsFree lesson

Implementing Value Iteration from Scratch

Build a complete implementation of value iteration for a grid world MDP, visualizing convergence and policy extraction.

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:

  1. Initialize all state values to zero (or arbitrarily)
  2. Iterate through each state, computing the maximum expected value across all actions
  3. Update the value of that state using the Bellman optimality equation
  4. Repeat until changes fall below a threshold (convergence)
  5. 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.