# Bellman 3×3

Bellman · v(s) = maxₐ [R(s, a) + γ v(s′)]

```
. . +1
# . -1
S . .
```

[Open in the app](https://www.wavelace.com/app#p=93) · [This page](https://www.wavelace.com/presets/bellman-3-3)

### 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.

### Read more

- [Bellman equation](https://en.wikipedia.org/wiki/Bellman_equation)
- [Markov decision process](https://en.wikipedia.org/wiki/Markov_decision_process)
- [Dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming)
- [Richard E. Bellman](https://en.wikipedia.org/wiki/Richard_E._Bellman)
- [Reinforcement learning](https://en.wikipedia.org/wiki/Reinforcement_learning)