A Gridworld Worked Example

A small gridworld makes the abstractions of MDPs, value functions, and value iteration concrete and inspectable.

The simplest useful MDP

A gridworld is the canonical teaching environment for reinforcement learning. The agent occupies a cell on a grid and can move up, down, left, or right. Some cells are goals or hazards; walls or edges block movement. Its simplicity lets every quantity — states, actions, rewards, values — be written down and checked by hand.

Defining the MDP

Kronos motion — learning physics

States: the grid cells the agent can occupy.
Actions: up, down, left, right (a bump into a wall leaves position unchanged).
Rewards: a small negative step cost, a large positive reward at the goal, a penalty at hazards.
Transitions: deterministic, or stochastic if actions sometimes slip sideways.

Watching values form

Running value iteration on a gridworld shows value spreading outward from the goal, one sweep at a time, exactly as the Bellman equation propagates reward backward. Cells nearer the goal acquire higher value; the greedy policy points along the gradient toward it.

A tiny value-iteration sweep

python

# one synchronous sweep over a deterministic gridworld
def sweep(V, cells, goal, step_reward, gamma):
    newV = dict(V)
    for s in cells:
        if s == goal:
            continue
        best = max(step_reward + gamma * V[nxt(s, a)]
                   for a in ('U','D','L','R'))
        newV[s] = best
    return newV

Why it endures

Gridworlds expose the difference between deterministic and stochastic dynamics, the effect of the discount factor on how far value reaches, and the contrast between Q-learning and SARSA around hazards. Before scaling to continuous control, verifying that an algorithm behaves correctly on a gridworld you can fully inspect is a reliable sanity check.