Sparse Rewards, Playable

EP 01

A coin at the exit — and silence everywhere else

Reinforcement learning has one feedback channel: reward. Put the only reward at the exit and every step before it is silence — the agent literally cannot tell a good move from a bad one, so random wandering is the best it can do. Drop the walker, then grow the maze and watch the step counter explode.

Maze size 5 × 5

steps: 0 · reward so far: 0

The walker is brainless on purpose: with zero signal anywhere except the coin, uniform random exploration is genuinely all a fresh agent has. Gold haze = how often each square was visited.

Why it matters: good case — on a tiny maze, dumb luck is enough. Bad case — steps needed blow up brutally with size. This is Montezuma's Revenge in miniature, the Atari game DQN scored ~0 on for years: when reward is one coin far away, pure sparse exploration simply does not scale.

EP 02

The first win changes everything — watch value trickle backward

Now give the walker a brain: Q-learning. Every step it updates a map of “how good is this square”. The catch: updates can only move value around — and until the coin is touched once, there is no value to move. Train it and watch the map stay pitch black… then catch the moment of the first success.

Real tabular Q-learning running live (α 0.6, γ 0.92, ε 0.25). Gold glow = learned value of each square; white dots = the last episode's path. Before the first success every update is 0 ← 0 + 0.

The pattern: bad case — episode after episode, nothing (learning rate × zero signal = zero learning). Good case — one success, and value starts flowing backward from the coin, a square at a time, until a gold road connects start to exit. Sparse-reward RL before the first win isn't slow. It's nothing at all.

EP 03

Breadcrumbs — shaping turns silence into a slope

Reward shaping pays small bonuses for progress — here, a bonus whenever the agent gets closer to the exit (true distance, computed by BFS). Below, two identical brains race on the same maze: one on pure sparse reward, one with breadcrumbs. The chart shows steps-to-coin per episode for both.

press the race button — you can keep pressing to train further

Shaping here is potential-based: r' = r + 0.5·(γ·φ(s′) − φ(s)) with φ = closeness to the goal. That exact form is the provably safe one — remember it for the next episode.

Good case: the shaped agent gets a gradient from step one and collapses to a short path in a handful of episodes, while pure sparse burns whole episodes finding the coin even once. This is why robot-arm papers pay “distance to object” bonuses and why AlphaGo bootstrapped from human games: dense signal buys you the discovery phase.

EP 04

The trap you built yourself — when shaping teaches the wrong lesson

Shaping is a loaded gun. Here the designer placed a +0.5 “hint” bonus on a tile halfway to the coin — payable every time the agent steps onto it. The coin at the end pays +5. Train with the naive hint and watch what the agent actually learns; then train with the same hint expressed the safe, potential-based way.

both buttons train 200 episodes of Q-learning, then replay the learned (greedy) policy

γ = 0.95, 120-step episodes. Camping on the hint earns ≈0.5 again and again; the +5 coin, discounted over the walk to reach it, is worth less. The agent does the math you didn't.

Bad case: the naive hint out-bids the coin, so the trained policy camps at the hint tile forever — reward hacking, the same failure as the CoastRunners boat looping over turbo pads instead of finishing the race. Good case: potential-based shaping pays the same hint as a difference you must give back when you leave — loitering nets zero, so the optimal policy stays “go to the coin”.

EP 05

Curiosity — get paid for novelty (and the noisy-TV trap)

Instead of hand-placed hints, curiosity pays a universal bonus: reward for states you haven't seen much. Compare a random walker with a curious one (it prefers its least-visited neighbour) hunting a sparse coin in the far corner. Then switch on the noisy TV — a screen that always looks new — and watch curiosity's own failure mode.

coverage: 0% · goal: not found

Count-based novelty stands in for curiosity bonuses (ICM / RND). The TV cell's visit count is treated as permanently zero — like a screen of static, it never stops being “novel”.

Good case: curiosity sweeps the map and finds the coin in a fraction of the random walker's time — count-based and RND bonuses are how agents finally beat Montezuma's Revenge with no hand-made hints. Bad case: an agent paid for surprise will happily watch static forever. The noisy-TV problem is a real, named pathology of curiosity-driven RL.