Click any cell to see, at full precision, exactly how its value was computed.
Each arrow points from a cell to its best (least-negative) neighbour; the orange path follows those arrows from S to G. See “How it works” below for the maths.
This is iterative policy evaluation, the loop at the heart of value-based reinforcement learning. Here is the whole idea, built up from scratch.
An agent walks the maze one step at a time. Give it a reward of −1 on every step. Now “get to the goal quickly” and “lose the least reward” are the same objective — that is the core trick of RL: encode the task as a reward and let the maths chase it.
Define the value of a cell as the expected total reward collected from until reaching the goal. Because every step costs −1 and nothing is discounted, this has a concrete meaning:
So at the goal and grows more negative the farther away a cell is. That is exactly the heatmap: light = near, dark = far.
The simplest one: the uniform random policy — from any cell the agent is equally likely to try each direction, . We are not acting well yet, only measuring how good each cell is under this behaviour.
The value of a cell is the average, over the four moves, of “the step cost now, plus the value of wherever you land”:
where each neighbour is the cell you move into — or the cell itself if a wall blocks that move (bumping a wall keeps you put). The goal is pinned at . This is a fixed point the true value function must satisfy.
Start with everywhere and apply the equation as an update, once per cell, over and over. Each full pass is one epoch:
The goal’s “how far am I” signal floods outward one ring of cells per epoch, and converges to the true value function. The epoch slider scrubs through these snapshots — watching it play is watching that signal spread through the maze.
The right-hand grid turns those values into advice. From each cell, the best move is simply to step to the neighbour with the highest value — the least-negative one, i.e. the neighbour closest to the goal. That is the greedy policy, and it is what every arrow shows:
So the arrow is decided by a difference. Look at each neighbour’s value minus this cell’s value: a neighbour that is less negative (closer to 0) gives a positive change — a step toward the goal — and the arrow points there. A neighbour that is more negative gives a negative change — a step away — so the arrow never points that way. Walls are not candidates at all.
Now start at S and keep following the arrow out of each cell. That chain of cells is the orange greedy path — the actual route the agent takes to G. Once the values settle it is the shortest way through the maze.
Why the path shows up “late.” Under a random policy the signal diffuses slowly, so on a 20×20 maze the path often doesn’t connect until a few hundred epochs in. That is honest behaviour, not a bug — raise the speed or shrink the grid to get there faster.