39Learning by trial and error: reinforcement learning

Nobody learns to ride a bicycle from instructions. You get on, wobble, fall, and get on again, and after enough falls your body knows something no one could have told it. All you had was the trying, and a blunt verdict at the end of each try: still rolling, or on the ground.

The last module's robot was shown its job. The cart-pole of the balancing module was told its job: a person worked out four pushes and chose their sizes. This module's robot is neither shown nor told. It gets the same cart, the same pole, and a score.

Points instead of instructions

Learning what to do by trying things and keeping what scores well is called reinforcement learning. The score is called the reward: a number the robot is handed, bigger when things are going the way its builder wants. Here it starts as one point for every second the pole stays up.

The reward does not say which way to push, or that a leaning pole has to be chased, or that there is a pole. It says how well things went.

In this box a try begins with the cart at the middle of the rail and the pole standing, leaning up to a degree one way or the other. It ends when the pole leans past 20 degrees, when the cart gets 70 centimeters from the middle, most of the way to a bumper, or when 10 seconds are up. Then everything is put back and the next try begins. One try, from the putting back to the end, is called an episode.

What is doing the learning

Every reinforcement learner, whatever it is learning, goes round one loop of five steps.

1. 1SeeWhat situation is it in? Whatever its sensors report.
3. 2ChoosePick what to do: usually what looks best so far, now and then something else, to find out.
5. 3ActDo it, and the world moves on.
7. 4Get paidThe reward: a number that says how well that went.
9. 5CorrectAdjust its guesses toward what happened, so the next choice is a little better.
11. And round again, until the try ends. Then everything is put back and the next try begins.

This page's learner is a table of numbers, small enough that each step can be told in full.

1. See. The balancing module's four numbers, the rig's state, arrive from the sensors: the pole's lean, how fast the lean is changing, where the cart is, how fast it is moving. The learner does not use them as numbers. It sorts each into a few bands: the lean into eight (under a degree to the right, one to three, three to eight, more, and the same to the left), the lean's speed into six, the cart's position into six, the cart's speed into four. One band of each makes a situation, and there are 1,152 of them. To the learner, a lean of 4 degrees and a lean of 7 are the same thing.

2. Choose. It has two pushes to choose between: 3 newtons to the left or 3 newtons to the right, a quarter of what the motor has. It cannot push gently, and it cannot do nothing. The table holds one number for every situation and each push, 2,304 numbers in all. Each is the learner's current guess at one question: if I am in this situation and push this way, how many points will I collect from here on? Its policy, the last module's word for a robot's rule for acting, is one line long: look up the situation, and make the push with the bigger number. Where the two are equal, as they all are before the first try, it pushes left.

3. Act. The push is held for a fiftieth of a second, and the cart and the pole move.

4. Get paid. The learner is told the points the push earned: while the pole is up, a fiftieth of a point.

5. Correct. This is where the numbers get to be right. The learner sees which situation it has landed in, and can now make a better guess at what the push was worth: the points it got, which are a fact, plus the table's number for the push it is about to make, which stands for all the points after that. It moves the old number a tenth of the way toward that guess, and only a tenth, because one situation covers a range of leans and speeds, and the same push does not always end the same way. When the pole falls there is no next push and nothing to add. The guess is no points at all, far below what the table held, so the number for the last push drops, and next time the other push looks better. A try stopped at 10 seconds is not a fall: the table is corrected as if it had gone on.

A fall is rarely the fault of the last push alone. The pole was lost several pushes earlier. So every correction is also handed back to the pushes that came before, a little weaker for each step back.

One more thing happens at step 2, and it is called exploration. A learner that always made the push with the bigger number would never find out that the other push was better than its number said. So some of the time it pushes at random: one push in five at first, fading to almost none as the tries add up. And every number in the table starts high, higher than most pushes will turn out to deserve, so that a push it has never made looks worth making.

Nothing in the loop knows what a pole is.

The box

The rig is drawn at the top, and it moves only while a try is running. The two switches are what the robot is paid. The first is on to begin with: a point for every second the pole stays up. The second takes points away for straying: 3 points a second for every meter the cart is from the middle, so about a third of a point a second at 10 centimeters. Changing a switch starts the learning over with a fresh table, because numbers learned under one pay mean nothing under another.

Watch a try runs the next try at its real speed. Practice 200 tries runs the next 200 as fast as your computer can work them out. The chart gains one reading for every try: how many seconds the pole stayed up, and under it how far the cart got from the middle. The colored line in each is the average of the last twenty tries. The words underneath give the last try with its points, and how many of its 1,152 situations it has met. Start over gives it a fresh table.

Loading the simulation. The robot runs in your browser, so the first one takes a few seconds to arrive.

This is easier on a larger screen, but it works here too.

Those 400 tries were about 40 minutes of practice, run in a few seconds, and about 270 of them ended in failure. Here is what it found, read out of its table for this page (the box does not show the table). To hold a pole up, the cart has to be pushed toward the side the pole leans: the lean push of the balancing module. Many situations share one band of lean. Counted by the time it spent in each, the ones with the pole leaning three to eight degrees to the right have the bigger number on the push to the right nearly nine-tenths of the time, and the ones leaning as far left have it on the push to the left eight-tenths of the time. The exceptions are mostly situations where the pole is already swinging back toward upright. About half of those favor the other push, so a pole passing through them is pushed both ways, which with two fixed pushes is the only way to push less. It is easing off the catch as the pole comes back: the lean brake, found the same way.

And here is what it did not find. With its cart pull switched off, the balancing module's cart stood wherever the last catch left it. This cart wanders for the same reason. Nothing it is paid for mentions the middle. Inside the 70 centimeter line every place on the rail pays the same point a second, and seconds are what it delivers.

The same table going round the same loop, under a different pay, gives a different robot. You do not write what the robot does. You write what it is paid, and the behavior grows out of that. Which makes the pay the place where things go wrong.

It does what you pay for

It is tempting to call that a failure to learn. It is the opposite. Under this pay there are no points to win, only points to lose, a little for every moment the cart is off center, and a cart that is holding a pole up is never exactly at the center. A try that has ended can lose nothing more. So the best possible try keeps the cart at the middle and gets itself over with, and the quickest way to end a try is to let the pole drop. The learner found the best answer to the question it was asked. The question was wrong.

Every reward is its writer's guess at what they want, put into arithmetic, and a learner searches for the highest score that arithmetic allows, by roads its writer never pictured. A well-known case comes from a boat-racing video game. A learner paid for the markers it hit along the course found a spot where three markers kept coming back, and circled there for good, never finishing a race, and outscoring the people who did. Much of the work of reinforcement learning is finding out what a reward really asked for.

What a real one changes

This learner needed some 400 tries to do what the balancing module's controller did from its first second, because that controller's author knew how poles fall and the learner knew nothing. Not needing to know is the attraction. But a real walking robot cannot fall 270 times without breaking. So real robots do nearly all of their trial and error in a simulation, often thousands of copies at once and faster than real time, and only the finished policy is moved to the machine, where everything the simulation got wrong is waiting for it.

A table also works only when the situations can be listed. A robot that sees through a camera has more situations than it could ever visit, so in place of the table it uses a neural network, the last module's formula with millions of adjustable numbers, which gives an answer for a situation it has never met exactly. The loop is unchanged: see, choose, act, get paid, correct.

And the two ways of learning in this part are usually mixed: a policy copied from demonstrations is the place to start, and trial and error then improves on the copy.

What the simulation leaves out

A person chose the bands, the two pushes and the rules for when a try ends, and each of those is a quiet way of telling the learner something. With bands too coarse to tell which side of the middle the cart was on, or which way it was rolling, this same learner under the first pay kept the pole up and, try after try, let the cart roll out to the 70 centimeter line. The sensors here are exact, and putting everything back costs nothing. And the random pushes come from a fixed list, so the box learns the same way every time you load the page. A real learner's luck differs every time it starts from nothing, and sometimes it learns late.