Russell–Norvig 4×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 textbook grid world is four cells wide and three high. A terminal worth +1 sits in the top-right corner and a terminal worth −1 below it, with one wall in the middle row and the start S in the bottom-left corner. Moves are unreliable. Slip is 0.2, so a move goes the intended way with probability 0.8 and to either side with 0.1 each; into a wall or off the grid it stays put. Every step that does not end the walk earns the Step reward of −0.04, and there is no discount, γ = 1.
Each sweep applies v(s) = maxₐ [R(s, a) + γ·v(s′)] to every empty cell, the expectation taken over the slip. After about twenty sweeps the residual is under 0.001 and the tiles read the numbers the book prints: 0.812, 0.868, 0.918 along the top, 0.762 and 0.660 either side of the wall, 0.705, 0.655, 0.611, 0.388 along the bottom. The walk from the start runs up the left column and right along the top.
Why the long way round
With the slip, the short route is not the best one. Take the bottom cell two below +1, worth 0.611. Moving up leads toward the cell beside the pit, where every step risks a slip into −1; its arrow points left instead, and the walk goes round three sides of the wall.
The cell right of the wall, worth 0.660, does point up even though a slip from there falls into the pit one time in ten, because up aims at the 0.918 cell above. Pressing left into the wall, which simply keeps it where it is, comes a close second at 0.641. What sets the balance is the step cost: cheap steps make caution worth paying for.
History
Stuart Russell and Peter Norvig use this world throughout the decision-making chapters of Artificial Intelligence: A Modern Approach, first published in 1995. Its best-known figure shows the optimal policy changing with the step reward: running for the nearest exit when steps are very expensive, going the long way round when they are cheap, never leaving at all when a step pays.
Try
- Set Step reward to −2: steps this expensive send the agent to the nearest exit even when it is the pit, and the arrow right of the wall turns into −1.
- Set Step reward to 0: with nothing to lose by waiting every cell is worth 1, and the bottom-right corner points down into the edge to stay put.
- Set Slip to 0: the caution disappears, each value is exactly 1 − 0.04·d for a cell d steps from +1, and the start reads 0.80.
- Set Discount γ to 0.9: distant rewards count for less, so the start sinks from 0.705 to 0.296 and the cell two below +1 turns to point up.