Tabular Q-Learning, Explained by a Snake
Q-learning is a model-free reinforcement-learning algorithm: it learns the value of taking each action in each state purely from experienced transitions, without ever knowing the environment's dynamics. The tabular version stores those values in a literal lookup table Q(s, a) and improves them with a one-line temporal-difference update after every single step. The interesting engineering is not the update — it is everything around it: how the state is encoded, how the reward is shaped, and how exploration is scheduled.
The running example throughout is the Snake agent from this site's game page: a snake on a 20×20 grid that must eat food without hitting the walls or its own body. It is a good test case precisely because the naive formulation is hopeless — the raw board has more configurations than atoms in the universe — so every design decision below is forced, not decorative. The final section retrains the same agent from scratch on a smaller board, inside this page.
🧭 What the snake actually sees
A tabular method must visit each state many times to learn its values, so the state space has to be tiny. The full board is out: even a modest 20×20 grid has on the order of 10100 snake configurations. The fix is to describe the situation relative to the snake's head, keeping only what matters for the immediate decision:
- Danger bits (3): would moving straight, turning left, or turning right cause a collision on the very next step?
- Heading (4): up, right, down, or left.
- Food direction (9): the signs of the food's horizontal and vertical offset from the head — not the distance, just which way.
That is 2³ × 4 × 9 = 288 possible states (fewer in practice, since some combinations never occur — the trained agent on the game page visits about 250). Actions are relative too: turn left, go straight, turn right. With only relative turns available, reversing into the own neck is not even expressible, which removes an entire class of instant deaths from the learning problem.
Drive the snake below with the three relative actions and watch the state it perceives. Click any cell to move the food. Note how radically different board positions collapse into the same state key — that collapsing is what makes the table small enough to learn.
The highlighted cells are the agent's entire sensory field: the square straight ahead (S), to its left (L), and to its right (R). Everything else on the board — including most of its own body — is invisible to it.
🍎 Rewards, and why shaping is asymmetric
The reward function defines the task. Eating and dying are the obvious signals, but on their own they are too sparse: a random snake takes hundreds of steps to stumble into its first food, and until then every action looks equally worthless. A small shaping reward based on Manhattan distance to the food gives the agent a gradient to follow from step one.
| Event | Reward | Purpose |
|---|---|---|
| Eats the food | +10 | the actual objective |
| Hits a wall or its body | −10 | terminal; ends the episode |
| Too many steps without eating | −10 | starvation cutoff — stops endless wandering episodes |
| Step that moves closer to food | +0.3 | shaping: dense progress signal |
| Step that moves away from food | −0.45 | shaping, deliberately larger — see below |
The asymmetry between +0.3 and −0.45 is not an accident. With symmetric shaping (+0.3 / −0.3), a snake that circles forever near the food breaks even on shaping and never risks the −10 of a crash — so cowardly orbiting becomes a decent policy, and early training gets stuck in it. Making retreat cost 1.5× what approach earns turns any closed loop into a strict net loss: every circle contains equally many approaching and retreating steps, so circling bleeds value and the only way to profit is to actually reach the food.
📐 The temporal-difference update
Q(s, a) estimates the total discounted reward from taking action a in state s and acting optimally afterwards. After each transition (s, a, r, s′) the table is nudged toward a better estimate of itself:
The bracket is the TD error: the gap between what the table predicted, Q(s,a), and the fresher one-step estimate r + γ·max Q(s′,·) — one real reward plus the table's own best guess about the future. The learning rate α controls how far each nudge goes; the discount γ controls how much the future is worth relative to the present. When the transition is terminal (a crash), there is no future: the target is just r.
Pick a scenario and drag the sliders to see one concrete update. The snake is in some state s with stored values Q(s,·) = [1.2, 2.4, −0.5] for [left, straight, right], it goes straight, and the best action in the resulting state s′ is worth 4.6.
Two things worth internalizing from playing with it. First, the crash update ignores γ entirely — death has no future to discount, which is why terminal states anchor the whole table: their −10 is ground truth, and it propagates backwards through the max. Second, α is a compromise: at α = 1 each update overwrites the cell with a noisy one-sample estimate; at α → 0 learning stalls. The agent on the game page uses α = 0.15, γ = 0.9.
🎲 ε-greedy exploration, on a schedule
A greedy agent exploits whatever the half-learned table currently says and can lock into bad habits before ever trying the better move. The standard fix is ε-greedy: with probability ε act uniformly at random, otherwise take the argmax action. Crucially, ε is scheduled: it starts at 1.0 (pure random exploration, since the initial table knows nothing worth exploiting) and decays multiplicatively after every episode — ε ← max(εmin, ε · d) — down to a floor of 0.01 that keeps a sliver of lifelong exploration.
Drag the slider to see how the decay constant d shapes the schedule over the first 1000 episodes.
The schedule has to match the state space. With ~288 states and 3 actions there are under a thousand table cells, and episodes are short early on, so d = 0.995 (mostly greedy after roughly 500 episodes — under a minute of fast training) is enough to cover the table. A big state space with the same schedule would go greedy long before exploration had touched most of it.
🐍 The full loop, from scratch
All four pieces — relative state, shaped rewards, TD updates, decaying ε — assembled into the complete algorithm, running here on a 12×12 board with a fresh, empty table. Press Start and switch to fast mode: the early episodes are near-random flailing, then the shaping gradient kicks in, then food-seeking becomes reliable and the rolling average climbs. The curve is the whole story of the algorithm compressed into one line.
Score = food eaten per episode. Thin line: raw episodes. Thick line: 20-episode rolling average. The table lives only on this page — reload and it forgets.
A few hundred numbers in a lookup table, one line of arithmetic per step, and no knowledge of the rules of Snake beyond what the reward says — that is the entire algorithm. Its limits are equally visible: the relative state cannot see the body's global layout, so the learned policy still traps itself inside its own coils at high scores, and no amount of further training fixes what the state cannot represent. Fixing that is where function approximation and deep Q-networks come in. The persistent version of this agent — same state, same rewards, same update, on the full 20×20 board with its table saved in the browser — lives on the game page.