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

Value Iteration Algorithm

Learn value iteration, which combines evaluation and improvement in a single update step using the Bellman optimality equation.

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.