Chapter 30: Learning by trial and error
No right answers given: just rewards. Watch a creature learn a maze.
Think back to learning to ride a bike. Nobody handed you a list of the correct lean angle for every moment. You wobbled, tipped over and tried again. Staying up felt great. Hitting the pavement did not. From nothing more than that, your body worked out what to do.
Now compare that with every network in this book so far. They all learned like a student getting homework back from a teacher: here is the question, here is the right answer, here is how far off you were. The flower sorter had labels. The name model was told which letter really came next. Even the picture maker in chapter 29 was told exactly which static it should have guessed.
This chapter is about the other way to learn, the bike way. It is called reinforcement learning: learning what to do by trying things and seeing how many points you get, with nobody ever showing you the right answer.
Two things make it harder than marked homework.
- You get a score, not a correction. A teacher's red pen says "the answer was 7". A score only says "that went well" or "that went badly". It never says what you should have done instead.
- The score arrives late. Chapter 14 had a soccer team that lost 3–2 and asked whose fault it was. This is the same puzzle stretched out over time. When the ball finally goes in, which of the last fifty passes deserves the credit?
A creature, a maze and nothing else
Just below is a 7 × 7 maze with a small orange creature in the bottom-left corner. Here is everything the creature can sense: which cell it is standing on. That's all. It can't see the walls, the lava or the star. It has no map.
And here are all the rules of its world:
- Each turn it picks one of four moves: up, right, down or left. If it walks into a wall or the edge, it stays where it is.
- Landing on the star is worth +10 points and ends the attempt.
- Stepping into lava costs 10 points. It can climb back out.
- Every other move is worth 0.
- If it hasn't found the star after 200 moves, we pick it up and put it back at the start.
One attempt, from the start until the star or the 200th move, is called an episode.
All the creature keeps from one episode to the next is a small table of numbers. For every cell it has four numbers, one for each move. Each is its current guess at one question: if I make this move from here, how many points will it lead to in the end? We'll call that number the move's value. At the beginning every value is 0, because it knows nothing.
After a lot of wandering, the creature stumbles onto the star and gets its +10. In the next episode it starts from the same corner again. What happens?
It keeps its table, so it hasn't forgotten. But it has no memory of its path at all. When the +10 arrived, the only number it changed was the one for the move it had just made. One cell, right beside the star, now knows something. The other 34 are still blank. Watch for that single green cell.
Teach a creature a maze
Take it in four steps. 1. Press one move a few times and read the panel under the maze: it shows the sum the creature does after every move. 2. Press ▶ watch and follow it for an episode or two. 3. Press ▶▶ fast, which plays a whole episode in a blink and draws where it went. Watch for the first green cell, then watch the green spread. 4. When the scribble has turned into one clean line, press 1,000 episodes.
- episode
- 1
- moves so far
- 0
- points so far
- 0
- its plan from the start
- none yet
- shortest lava-free route
- 12 moves
- average moves, last 20
- —
- average points, last 20
- —
What its last move taught it
Arrow: the move it currently rates best in that cell. Black arrows are its whole plan from the start. Number and green: the points it expects from that cell onward. Red bar: a move it has learned costs points. Orange line: where it went this episode.
How many moves each episode took. Light orange is every single episode, dark orange is the average of the last 20, and gray is the shortest route that avoids lava. An episode that runs out of time counts as 200, which is off the top.
What just happened
The page starts with its dice set the same way every time. So if you pressed nothing but the run buttons, your creature's story went exactly like this:
- Episode 1: stumbling. 200 moves of wandering, three of them into lava, and no star. It finishes on −30 points without a single green cell. All it has learned is three things that hurt: the red bars.
- Episode 2: luck. On move 86 it blunders onto the star. One cell turns green: D5, right beside the star, now says 5.00.
- Episode 3. It needs 130 moves, but it gets there again. D5 rises to 7.50, and its neighbor E5 gets 2.25.
- Episodes 4 to 16: mostly failing. Ten of these thirteen episodes run out of time. But each success drags the green a cell or two further from the star: along row 5, then down column G.
- Episode 17 onward: it never fails again. Once it wanders into the green, it just follows the arrows home.
- Episode 25: the route locks in. The green reaches the start cell, and "its plan from the start" reads 12 moves for the first time. That took 3,125 moves of experience.
After that the chart goes flat at around 13 moves. The plan is 12 moves, the shortest route there is without touching lava. The extra move or so comes from the creature still trying something random now and then, which we'll get to.
Notice what it did not learn. After 1,000 episodes, 18 of the 35 cells it could stand on are still blank. It never needed the top of the maze, so it never worked it out.
Honesty note: after erase its memory the dice are different every time, so the story changes. Of 1,000 fresh creatures we ran, half had a plan by episode 28 and nine in ten by episode 39. For 983 it was the 12-move route. The other 17 stumbled on the long way round the top first, 16 moves, and never found the shorter one. If your plan says 16, that happened to you.
The four pieces
You have now watched every part of reinforcement learning. The parts have names, and the names are the same for a creature in a maze and a program playing chess.
- The agent is the learner, the one making the choices. Here that's the creature.
- The state is the situation the agent is in right now, as far as it can tell. Here that's the cell it is standing on, such as D5.
- An action is one of the things the agent can choose to do. Here there are four: up, right, down, left.
- The reward is the number that comes back right after an action: +10, −10 or 0. It is the only feedback the agent ever gets.
Together they make a loop: look at the state, choose an action, receive a reward and a new state, repeat. The agent isn't after a big reward on its next move. It wants as much reward as it can get over the whole episode.
The map of arrows has a name too: a rule that says which action to take in every state is a policy. Nobody wrote the creature's policy. It fell out of the numbers.
How one move changes one number
The creature never looks back over its whole trip. After every single move it fixes one number, the value of the move it just made, by asking: did that go better or worse than I expected?
- What it expected: the value already in its table for that move.
- What it got: the reward, plus the best value in the cell it has just landed on. Landing somewhere promising is nearly as good as being paid.
The gap between those two is its surprise. It then moves the old value part of the way toward what it got:
surprise = reward + γ × (best value where it landed) − old value new value = old value + α × surprise
The Greek letters are two of the sliders. With α (alpha) at 0.5 it moves halfway. With γ (gamma) at 0.9, whatever comes next counts for 90% of its face value.
Here is the real arithmetic from the run above. In episode 2, on move 86, the creature was on D5 and tried "left". The old value of that move was 0. The reward was +10. It landed on the star, the episode was over, and so nothing came next.
surprise = 10 + 0.9 × 0 − 0 = 10 new value = 0 + 0.5 × 10 = 5.00
That is the one green cell. Now the important one. In episode 3 it wandered onto E5 and tried "left", which took it to D5. The reward was 0. Nothing happened. But the best value on D5 was now 5.00.
surprise = 0 + 0.9 × 5.00 − 0 = 4.50 new value = 0 + 0.5 × 4.50 = 2.25
E5 earned 2.25 for a move that paid nothing at all. It got credit for leading to a cell that leads to the star. One move later the creature stepped from D5 onto the star again, and D5 went from 5.00 to 7.50, halfway to 10.
Check it yourself: press reset everything, then finish episode three times, reading "what its last move taught it" each time.
Credit, passed backwards through time
That small sum explains everything you watched. The +10 itself only ever touches D5. But once D5 has a value, stepping onto D5 is worth something, so E5 gains a value. Then F5. Then G5. Every visit can hand the value back one more cell, until it has seeped the whole way to the start. The creature in the corner, 12 moves from the star, ends up knowing that "right" is worth 3.14 points, though no reward has ever been paid anywhere near that corner.
You have seen this shape before. In chapter 14 the blame for a wrong answer started at the output and was handed backwards, layer by layer, until every weight had its share. Here the credit for a reward starts at the goal and is handed backwards, move by move, until every step of the route has its share. Backprop passes blame back through the layers of a network. This passes credit back through time. Both are answers to the same puzzle of credit assignment.
The method is called Q-learning. The numbers in the table are Q-values and the table is a Q-table. A British researcher, Chris Watkins, described it in his PhD thesis in 1989.
Try something new, or do what works?
Now the first slider. Most of the time the creature takes the move its table rates highest. That is exploitation: using what you already know. But with the slider at 10%, one move in ten it ignores the table and picks a move at random. That is exploration: trying something to find out what happens. The slider's Greek letter is ε (epsilon).
Exploring has a price. The trained creature's plan should score 10 points in 12 moves every time, but a random move now and then sends it into a wall, or into the lava. We trained 1,000 creatures at each setting and averaged their last 100 episodes:
| exploring | moves per episode | points per episode |
|---|---|---|
| 0% | 12.1 | 10.0 |
| 10% | 13.3 | 9.2 |
| 30% | 17.1 | 6.9 |
| 100% | 152 | −73 |
So why not train it, then set exploring to 0% and enjoy the perfect score forever?
Suppose you train the creature for 1,000 episodes, and then the lava at D6 dries up. The star is now only 6 moves from the start, straight through where the lava used to be. You set exploring to 0% and run another 1,000 episodes. What does the creature do?
It walks the long way round forever. We tried this 500 times and it never once took the shortcut. Its table still says that "up from D7" is worth about −1.9, a number it wrote down back when D6 was lava. A creature that only does what it believes is best never tests whether a belief is still true.
See it for yourself. Press reset everything, then 1,000 episodes. Choose empty and click D6 to dry up the lava. "Shortest lava-free route" drops to 6. Set exploring to 0%, press 1,000 episodes again, and its plan stays stuck on 12.
Now give it back some curiosity: slide exploring up to 10% and press 1,000 episodes once more. Sooner or later a random move takes it up from D7. No lava. It corrects the number, and after a few more accidents the shortcut is worth more than the old route. The black arrows snap over and the chart drops from 12 to 6. In our 500 tries a 10% explorer made the switch in 499, usually after about 70 episodes. A 30% explorer needed about 18.
That is the trade you are always making. Exploring costs points today. Not exploring can cost you a better route forever.
Honesty note: you might expect a creature set to 0% from the very beginning to learn nothing. Try it. It learns fine, and the reason is how it breaks ties. With an empty table all four moves are worth 0, a four-way tie, and it settles ties at random. A creature that knows nothing explores without being told to. Exploring on purpose only starts to matter once it believes something, because beliefs can be out of date.
Pull the rug out
The creature has no idea that you can change its world. So change it. Leave exploring at 10% and use ▶▶ fast to watch.
- Block its route. Press reset everything, train it, then choose wall and click F7. It marches to E7 and walks into the new wall, again and again. Every bump is a small disappointment, so the value drains a little each time and the green fades back along row 7. Eventually it finds the other way: up the left side, across row 3 and down the right, 16 moves. In 500 tries it settled on that route in 499, usually within about 80 episodes.
- Move the star. Train a fresh creature, choose move goal and click G1, the top-right corner. It trots to where the star used to be and dithers there while its old values leak away. In 500 tries it always found the new shortest route, usually within about 35 episodes.
How fast it changes its mind is the job of α, the learning rate, the same idea as in chapter 4. With α = 0.1 the blocked route took about 280 episodes to recover from. With α = 1, where each experience simply replaces the old value, it took about 60. That only works so well because nothing in the maze is left to chance. In a world with luck in it, like a slippery floor or an opponent, one experience can mislead, and a smaller α averages over many.
How much the future counts
The third slider, γ, is the discount factor: how much a reward one move in the future is worth compared with the same reward right now.
Press reset everything, train the creature, and read the numbers along its route, starting beside the star and walking back to the corner:
10.00 9.00 8.10 7.29 6.56 5.90 5.31 4.78 4.30 3.87 3.49 3.14
Each one is 0.9 times the one before. A prize twelve moves away is worth 10 × 0.9 × 0.9 × … eleven times over, which is 3.14.
This is the only thing that makes the creature hurry. Nothing in the rules charges it for dawdling: a 12-move trip and a 40-move trip both pay exactly 10 points. But a prize that is further off is worth less now, so the arrows always point down the quickest road. When the lava dried up, the corner cell's value could rise from 3.14 to 5.90, and that is why it switched.
Push the slider to either end and the creature breaks. Press erase its memory before each one.
- γ = 0: only the next move counts. D5 learns that "left" pays 10, and no other cell ever gets a value, because nothing that comes later counts. In 500 runs, not one creature ever formed a plan.
- γ = 1: later is exactly as good as now. Press 1,000 episodes three times. At first it usually looks fine. But every move that avoids lava is creeping toward a value of exactly 10, and once they are all 10 there is no reason to prefer the move that gets there sooner. By 3,000 episodes the plan had dissolved into circles in all 300 of our runs.
Real systems usually pick a γ just under 1, such as 0.99: patient, but not infinitely patient.
From a table to a network
So what is this chapter doing in a book about neural networks? A table only works when you can list every state the agent could ever be in. The maze has 49 cells. That's easy.
Now think about a video game. In the early 2010s, researchers at a London company called DeepMind wanted an agent to learn old Atari games straight from the screen. An Atari screen is 210 × 160 pixels and each pixel can be any of 128 colors. The number of different pictures it could show is over 70,000 digits long. A real game shows only a tiny fraction of them, and even that is far too many for a table. The board game Go is just as hopeless: its 19 × 19 board has about 2 followed by 170 zeros legal positions, and the universe we can see holds only about 1 followed by 80 zeros atoms.
The way out is to stop storing the values and start estimating them. Replace the table with a neural network. The state goes in, as the pixels of the screen, and out come the values, one for each action: exactly what one row of the creature's table holds. Then train it with the rule you already know. After each move, work out "reward + γ × best next value" and use backprop to nudge the weights so the network's answer moves a little toward it.
A network also does something no table can. Remember the 18 blank cells? A table has nothing to say about a state until the agent has been there. A network shares its weights across all states, so what it learns in one situation carries over to similar ones it has never seen: the difference chapter 16 drew between learning a rule and memorizing the homework.
DeepMind called their version a deep Q-network, or DQN. In 2013 they showed it learning seven Atari games from nothing but the screen and the score. In 2015, in the journal Nature, the same network with the same settings was set loose on 49 different games. On 29 of them it reached at least three-quarters of the score of a professional human games tester. Nobody told it the rules of any of them.
In March 2016, in Seoul, DeepMind's Go program AlphaGo beat Lee Sedol, one of the best players in the world, by four games to one. Many experts had expected that to take at least another ten years.
Honesty note: AlphaGo was more than Q-learning with a big network. Its networks first learned to copy moves from strong human players, which is marked-homework learning. Then they improved by reinforcement learning, playing millions of games against copies of itself, and during a real game the program also searched ahead through possible moves. A year later its successor, AlphaGo Zero, skipped the human games completely. It learned by self-play alone and beat the version that had beaten Lee Sedol by 100 games to 0.
The same loop inside a chatbot
Remember the third stage of a chatbot's training in chapter 23? The model writes answers, a judge trained on people's preferences scores them, and the weights are nudged toward the kind of answer that scores well.
That is reinforcement learning, and you can now name its parts. The agent is the language model. The state is the conversation so far. The action is the answer it writes. The reward is the judge's score. Nobody shows the model the one right answer. Like the creature, it only finds out how well each attempt went.
Be careful what you reward
Suppose you want to encourage a trained creature, so you put a snack on B7, the first cell of its route. A snack is worth 1 point and grows back every time. The star is still worth 10. After another 1,000 episodes, what is the creature doing?
It never goes near the star again. That happened in all 500 of our tries. Count the points and it makes perfect sense. The star pays 10, once, and then the episode is over. The snack pays 1 every second move for as long as you like: 100 points in a 200-move episode.
Try it: reset everything, 1,000 episodes, choose snack +1, click B7, and press 1,000 episodes again. Then set exploring to 0% and watch one episode. It scores exactly 100.
The creature didn't malfunction. It found the best possible strategy for the reward we actually wrote down. We meant "go to the star, and here's a treat on the way". We said "collect points". An agent does what earns reward, which is not always what you had in mind.
This happens to real researchers. In 2016 a team at OpenAI trained an agent on a boat-racing video game called CoastRunners. The game gives points for hitting targets along the course, not for finishing. The agent found a lagoon where three targets kept reappearing and drove in circles there forever, crashing and catching fire, without finishing a single race. It scored about 20% more than human players did. People call this reward hacking.
It matters for chatbots too. Researchers at Anthropic looked at what people's ratings actually reward, and found that answers agreeing with the person's own opinion tend to be preferred. Train on those ratings and you can get a model that tells you what you want to hear. As chapter 25 put it, a model learns whatever its score rewards, which isn't always what you meant. Writing a reward that says exactly what you mean is one of the hard, unsolved parts of building AI.
Run the maze in Python
This is maze.py: the same maze and the same learning rule in plain Python, with nothing extra to install. It prints how each of the first few episodes went, then how many moves episodes took on average in blocks of 50, then a map of arrows and the route it settled on. Its dice are different from the widget's, so the story is different too, but it ends at the same 12 moves.
In reinforcement learning nobody marks the homework. An agent acts, collects rewards, and passes the credit backwards through time, one step per visit, until even its first move knows where it leads. It will chase exactly the reward you wrote, so write it carefully.
1. Set exploring to 100%, erase its memory and press 1,000 episodes. The chart is terrible. Now look at the arrows, then set exploring to 0% and press ▶ watch. How did it learn the route without ever once following it? 2. Reset, train, and put a snack on E5. It eats it and carries on to the star. Now slide γ up to 0.95 and train again. Why does a creature that cares more about the future stop finishing? 3. In maze.py, set STEP_REWARD to -1 so that every ordinary move costs a point, and set GAMMA = 1. It still finds the 12-move route. What is making it hurry now?
What is the main difference between reinforcement learning and the way the other networks in this book were trained?
Every other model in the book was shown the right answer for each example. An agent only gets rewards, and has to work out for itself which of its earlier moves earned them.
The creature starts 12 moves from the star. Why does it take many episodes before the start cell has any value at all?
A move's value is updated from the reward plus the value of the very next cell. So the cell beside the star learns first, then its neighbor, and so on back along the route.
A robot vacuum is given +1 for every bit of dirt it sucks up. It learns to tip its dirt back onto the floor and suck it up again. What went wrong?
The reward said "pick up dirt", not "leave the floor clean". Like the creature and its snack, the robot found the best strategy for the reward as written.