What if every square on a map could learn how good it is to stand there? That is the Bellman equation.
Introduction
How Good Is Each Square?
Every square on this map is secretly asking one question: how good is it to stand here?
- Every state has a value
- Value means future reward
Start With Zeros
We start by knowing nothing. Every value is zero, except the goal, which pays a reward of plus one.
- All values begin at zero
- Goal pays plus one
Average Over Next States
Now the key idea. Each state looks at where it can go next, and averages reward plus discounted value.
- Look at every next state
- Average reward plus discounted value
The Bellman Equation
Here is the equation. V of s equals the sum over actions of pi, times the sum over next states of p, times reward plus gamma times V of s prime.
- V of s equals expected return
- Gamma discounts the future
Gamma Discounts the Future
Gamma is the discount. A reward far away counts a little less than a reward right now.
- Gamma is between zero and one
- Sooner rewards count more
Sweep One
Sweep one. The squares touching the goal light up with new values, and everything else is still zero.
- Value starts next to the goal
Values Ripple Backward
Sweep two, sweep three. The value spreads backward, like ripples from a stone dropped in water.
- Each sweep spreads the signal
- Repeat until nothing changes
Converged: Follow the Values
After enough sweeps, the numbers stop changing. Following the biggest value from each square gives you the best path.
- Values stop changing
- Greedy arrows reveal the policy
Next: Lesson 59
Want the full derivation, with real numbers and Python? That is lesson fifty-nine. Follow, and see you there.
- Full derivation and Python
- Follow the course