Bellman 3×3
Bellman · v(s) = maxₐ [R(s, a) + γ v(s′)]
. . +1 # . -1 S . .
Open in the app The dials and keys named below are the app's.
What it draws
The grid is written one row per line: . is an empty cell, # a wall, a number a terminal worth that reward, S the start. This one is three cells by three. The top-right cell is worth +1, the cell below it −1, the middle-left cell is a wall, and the start is the bottom-left corner with that wall above it. From an empty cell an agent moves up, right, down or left; into a wall or off the grid it stays put.
Each tile rises to its value v(s), the discounted reward it can expect from there under the best play. The walk from the start goes right one, up the middle column past the wall, then right onto +1. The bottom-right arrow points left, away from the pit above it.
The update
One sweep applies Bellman's optimality equation v(s) = maxₐ [R(s, a) + γ·v(s′)] to every empty cell at once: a state is worth the best immediate reward plus the discounted value of the state that move lands in. Terminals keep their reward. Here the step reward is r = 0 and the discount γ = 0.9, and one press of Step is one sweep.
At sweep 0 only the two terminals stand. After one sweep the cell left of +1 is worth 0.9, after two its neighbours 0.81, then 0.729 and 0.656, each ring a factor of 0.9 further back. After the fourth sweep nothing changes at all. This is value iteration, and it converges because γ is below 1: a sweep shrinks the largest remaining error by at least that factor. So the residual reads 0.9, 0.81, 0.729, 0.656 and then nothing.
History
Richard Bellman set out dynamic programming at the RAND Corporation through the 1950s, and published the book of that name in 1957. The recursion that breaks a long decision into one step plus the value of what remains carries his name. The same equation with a maximum over actions is the foundation of reinforcement learning.
Try
- Rewind, then Step four times: each press carries the values one ring further out, and the fourth changes nothing.
- Set Discount γ to 0.5: the values halve with every step, 0.5, 0.25, 0.125, 0.063, and the far corners come to almost nothing.
- Set Slip to 0.2, the classic 0.8 / 0.1 / 0.1 world: the corner beside the pit falls from 0.656 to 0.276, and settling now takes dozens of sweeps rather than four.
- Set Step reward to −0.1: every step now costs, so the bottom corners drop to 0.312, and the walk stays the shortest one.
- Edit the grid: make the bottom-right cell a second +1, and the walk turns to it, two steps instead of four.