Cliff Walk
Bellman · v(s) = maxₐ [R(s, a) + γ v(s′)]
. . . . . . . . . . . . . . . . . . . . . S -100 -100 -100 -100 -100 +1
Open in the app The dials and keys named below are the app's.
What it draws
The grid is seven cells wide and four high. The bottom row is the cliff: the start S at its left end, the goal, a terminal worth +1, at its right end, and five terminals worth −100 between them. The other three rows are open ground. Moves are certain here, Slip is 0, every step earns the Step reward of −0.05, and Discount γ is 0.95.
One sweep of v(s) = maxₐ [R(s, a) + γ·v(s′)] covers every empty cell at once, and the values settle after nine of them. A cell d steps from the goal ends up worth 2·0.95ᵈ − 1: the discounted goal, 0.95ᵈ, less the discounted cost of getting there, 1 − 0.95ᵈ. So the cell above the goal reads 0.900, and the start, eight steps away, 0.327. The walk from the start goes one step up, straight along the edge of the cliff, then one step down onto +1, the shortest route there is.
The edge
Value iteration is handed the model, so it knows the cliff exactly and walks its edge without fear. With no slip, a cell beside a −100 is worth just what its distance says and nothing less. The picture changes the moment moves can go wrong, which is the point of the classic version of this task, where an agent learns the values from its own steps and its own exploration makes the edge dangerous.
History
The cliff-walking task is Example 6.6 in Sutton and Barto's Reinforcement Learning: An Introduction (1998), where it separates two learning rules. Q-learning learns the values of the optimal policy and walks the edge. Sarsa learns the values of the policy it actually follows, exploration included, and keeps to the safer rows above. In the book, stepping off the cliff sends the walker back to the start; here the cliff cells simply end the walk.
Try
- Top shows the walk as the book draws it, hugging the cliff.
- Set Slip to 0.1: a step along the edge now carries a one-in-twenty chance of falling in, so the arrows above the cliff turn away from it and take the safe path of the book.
- Set Step reward to −0.5: the far tiles sink below the floor, since from there the walk costs more than the goal pays, and the arrows still point along the edge.
- Rewind, then Step one sweep at a time: the goal's value arrives one column per press, and the start rises back above the floor on the eighth.