Maze
Bellman · v(s) = maxₐ [R(s, a) + γ v(s′)]
S . . # . . . # # . # . # . . . . . . # . . # # # . # . . # . . . # . . # . # # # . . . . # . . +1
Open in the app The dials and keys named below are the app's.
What it draws
A seven-by-seven maze. The start S is in the top-left corner, the goal, a terminal worth +1, in the bottom-right, and the walls are the # cells. Moves are certain, Slip is 0, every step earns the Step reward of −0.02, and Discount γ is 0.9. Each open cell rises to its value v(s), the discounted reward of the best walk from there.
The shortest route from the start to the goal is 16 steps, so the start ends up worth 0.9¹⁶ − 0.02·(1 − 0.9¹⁶)/0.1 ≈ 0.02: the discounted goal, 0.185, less the discounted cost of the steps, 0.163. Cells farther out are worth less than nothing, and the dead end in the bottom-left corner reads −0.02. From there the step costs outweigh what the goal is still worth by the time it is reached.
A flood from the goal
On a maze, value iteration is a flood. At sweep 1 every open cell takes the step cost and sinks just below the floor, and only the two cells beside the goal feel the goal at all. At sweep k the goal's discounted value has reached every cell within k steps of it, decaying with distance. Once the flood arrives the arrows point downhill along the shortest path: each cell's best move is to the neighbour one step nearer the goal, so the greedy walk is a shortest path. The residual falls to nothing once the farthest cell has been reached, after 18 sweeps here.
Run with γ = 1 and a step cost, the same recursion is the relaxation of the Bellman–Ford algorithm (Bellman, 1958). A cell is then worth 1 − 0.02·d, which is a distance map to the goal with the walls in the way.
Try
- Rewind, then Step one sweep at a time: the flood advances one cell per press, and the start rises above the floor on the sixteenth.
- Set Discount γ to 1: every value becomes 1 − 0.02·d, the start reads 0.68, and the tiles step down evenly along the route.
- Set Step reward to 0: the discount alone shapes the values, the start reads 0.9¹⁶ ≈ 0.185, and no cell goes negative.
- Open a wall: in the third row, change the # in the sixth column to a ., and the walk cuts through, four steps shorter.
- Top shows the maze as a map, with the walk threading it.