Unit 11: Learning by Reward

A third kind of learning

With labels, somebody wrote the answer next to every example. With clustering there were no answers at all, only things that were near each other.

Now there is something in between: nobody ever says what to do, but every so often the world says how that went. Learn to get more of it. That is reinforcement learning, and it is how programs learn to play games and how robots learn to walk.

A corridor with treasure at the end

Five squares. The robot starts at 0, can step left or right, and there is a wall at the left-hand end. Stepping onto square 4 finds the treasure and is worth 10. Every other step is worth nothing at all.

Python

def move(square, action):
    if action == "left":
        nxt = square - 1
    else:
        nxt = square + 1
    if nxt < 0:
        nxt = 0
    return nxt

def reward(square):
    if square == 4:
        return 10
    return 0

print(move(0, "left"), move(0, "right"))
print(reward(3), reward(4))

It prints

0 1
0 10

What makes this hard

The reward turns up at the end. When the robot took its first step, nothing happened — and that step was every bit as necessary as the last one.

So the problem is not "which move was rewarded" but "which of the moves I made ages ago deserve the credit". That is the whole subject, and it has a name: the credit assignment problem.

What it is trying to learn

Not a label and not a group, but a policy: what to do in each square. Ours is going to end up as five instructions — go right, go right, go right, go right — and the robot has to work them out from nothing but the treasure.

Ten numbers, all zero

Keep a table: for each square, what going left is worth and what going right is worth. Five squares, two moves, ten numbers — and the robot starts believing nothing is worth anything.

The table is called Q, and finding it is called Q-learning.

Python

Q = []
for square in range(5):
    Q.append([0.0, 0.0])

print(Q[0])
print(len(Q), "squares, each with a left and a right")

It prints

[0.0, 0.0]
5 squares, each with a left and a right

The one rule

After stepping from one square to the next, the robot asks what that move was really worth:

what I just got, plus what the next square is worth — knocked down a bit, because later is worth less than now — and then it nudges its old guess a fraction of the way towards that.

The knocking-down number is the discount, 0.9 here. The fraction is the learning rate from unit 4, and this is the same nudge: move a little towards what you now believe.

Python

RATE = 0.5
DISCOUNT = 0.9

old = 0.0
got = 10
next_worth = 0.0

new = old + RATE * (got + DISCOUNT * next_worth - old)
print(new)

It prints

5.0

Watch the treasure crawl back down the corridor

Walk right every time, four runs. After the first, only the last square before the treasure is worth anything. After the second, the one before it has caught some. The reward spreads backwards, one square per run.

Python

Q = []
for square in range(5):
    Q.append([0.0, 0.0])

RATE = 0.5
DISCOUNT = 0.9

for episode in range(4):
    square = 0
    while square < 4:
        nxt = square + 1
        got = 10 if nxt == 4 else 0
        best_next = max(Q[nxt])
        Q[square][1] = Q[square][1] + RATE * (got + DISCOUNT * best_next - Q[square][1])
        square = nxt
    print("run", episode + 1, [round(q[1], 2) for q in Q[0:4]])

It prints

run 1 [0.0, 0.0, 0.0, 5.0]
run 2 [0.0, 0.0, 2.25, 7.5]
run 3 [0.0, 1.01, 4.5, 8.75]
run 4 [0.46, 2.53, 6.19, 9.38]

That is credit being assigned

Nobody told square 2 that it was on the way to anything. It learned it from square 3, which learned it from the treasure — each square picking up a discounted echo of what comes after it.

Give it enough runs and every square knows what it is worth.

Let it choose for itself, and watch

Until now we marched it to the right. Let it pick whatever its table says is best instead — and remember that its table is all zeros, so left and right look equally good and it takes the first.

Python

Q = []
for square in range(5):
    Q.append([0.0, 0.0])

RATE = 0.5
DISCOUNT = 0.9
square = 0
where = []

for step in range(8):
    action = 0 if Q[square][0] >= Q[square][1] else 1
    nxt = square - 1 if action == 0 else square + 1
    if nxt < 0:
        nxt = 0
    got = 10 if nxt == 4 else 0
    Q[square][action] = Q[square][action] + RATE * (got + DISCOUNT * max(Q[nxt]) - Q[square][action])
    square = nxt
    where.append(square)

print(where)

It prints

[0, 0, 0, 0, 0, 0, 0, 0]

Eight steps into a wall

It is not broken and it is not stupid. It is doing the best thing it knows, and it knows nothing — so it will do the best thing it knows until the sun goes out.

Nothing can be worth anything until something has been tried.

So make it try things

Half the time, ignore the table and move at random. The rest of the time take the best move it knows. Being random is not carelessness here — it is the only way to find out about a square you have never stood on.

The randomness is our own seeded generator from unit 7, so this run comes out the same for everybody.

Python

seed = 7

def rand():
    global seed
    seed = (seed * 75 + 74) % 65537
    return seed

Q = []
for square in range(5):
    Q.append([0.0, 0.0])

RATE = 0.5
DISCOUNT = 0.9

for episode in range(30):
    square = 0
    for step in range(40):
        if square == 4:
            break
        if rand() % 2 == 0:
            action = rand() % 2
        else:
            action = 0 if Q[square][0] >= Q[square][1] else 1
        nxt = square - 1 if action == 0 else square + 1
        if nxt < 0:
            nxt = 0
        got = 10 if nxt == 4 else 0
        Q[square][action] = Q[square][action] + RATE * (got + DISCOUNT * max(Q[nxt]) - Q[square][action])
        square = nxt

for square in range(4):
    print(square, [round(v, 2) for v in Q[square]])

It prints

0 [6.47, 7.29]
1 [6.56, 8.1]
2 [7.29, 9.0]
3 [8.07, 10.0]

Look at the right-hand column

10, then 9, then 8.1, then 7.29. Each square is worth exactly 0.9 of the one in front of it — which is the discount, appearing all by itself. The robot was never told the treasure was at square 4, and it has worked out precisely how far away everything is from it.

And in every square, going right is now worth more than going left. That is the policy, learned.

Python

print(round(10 * 0.9, 2))
print(round(10 * 0.9 * 0.9, 2))
print(round(10 * 0.9 * 0.9 * 0.9, 2))

It prints

9.0
8.1
7.29

Explore or exploit

Always taking the best move you know is exploiting. Trying something else is exploring. Too much exploiting and you never find the treasure; too much exploring and you never walk to it.

Every game-playing program in the world is somewhere on that dial, usually exploring wildly at first and settling down later.

A small, sensible-looking change

The robot was slow to get going, so let us encourage it: 2 for every step it takes, and the treasure still worth 10.

That sounds like nothing more than a nudge in the right direction.

It stops collecting the treasure

Same code, same corridor, one number changed. Look at square 3 — one step from the treasure, and it has decided to turn round.

Python

seed = 7

def rand():
    global seed
    seed = (seed * 75 + 74) % 65537
    return seed

Q = []
for square in range(5):
    Q.append([0.0, 0.0])

RATE = 0.5
DISCOUNT = 0.9

for episode in range(60):
    square = 0
    for step in range(40):
        if square == 4:
            break
        if rand() % 2 == 0:
            action = rand() % 2
        else:
            action = 0 if Q[square][0] >= Q[square][1] else 1
        nxt = square - 1 if action == 0 else square + 1
        if nxt < 0:
            nxt = 0
        got = 10 if nxt == 4 else 2
        Q[square][action] = Q[square][action] + RATE * (got + DISCOUNT * max(Q[nxt]) - Q[square][action])
        square = nxt

for square in range(4):
    print(square, "left" if Q[square][0] > Q[square][1] else "right", [round(v, 2) for v in Q[square]])

It prints

0 right [20.0, 20.0]
1 right [20.0, 20.0]
2 left [20.0, 20.0]
3 left [20.0, 10.0]

Do the sum it did

Walking about for ever, at 2 a step with everything later discounted by 0.9, is worth 2 + 1.8 + 1.62 + … which comes to exactly 20.

The treasure is worth 10 and then the episode ends and the money stops. So 20 beats 10, and the robot is right. It is not cheating, it is not confused, and it has not misunderstood: it has understood perfectly and done what you paid it to do.

Python

total = 0
payment = 2
for step in range(200):
    total = total + payment
    payment = payment * 0.9
print(round(total, 2))

It prints

20.0

This has a name, and it happens constantly

It is called reward hacking: the model finds a way to score highly that has nothing to do with what you wanted. A boat-racing program that learned to spin in circles collecting the same bonus over and over instead of finishing the race is the famous one.

The bug is never in the learning. It is in the sentence somebody wrote about what counts as doing well.

Which is how chatbots are finished off

A language model out of unit 7 has only learned to continue text. To make it helpful, people are shown pairs of answers and asked which is better, and the model is then trained by reward to produce the sort of answer that gets picked.

So bear the corridor in mind. A model rewarded for answers people like learns to produce answers people like — which is very nearly, but not the same as, answers that are true. That is part of why a wrong answer can arrive sounding so confident and so helpful.