Learning by reward

Q-learning: a table of how good each action is, filled in by trying.

8.5LearningRobot club30 min

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Types of machine learning explained

No labels this time. Nobody tells the robot what the right action is. It tries things, and afterwards something tells it how well that went: a reward. Driving forward pays a little. Turning costs a little. Bumping into something costs a lot. From nothing but that, the robot works out how to wander a cluttered mat without hitting anything. This is reinforcement learning, and the method is called Q-learning.

States and actions

The robot cannot learn about every possible position, so it summarises its situation into a few states. Here there are three: how far the nearest thing anywhere in front is, near (under 20 cm), mid (under 40 cm) or far. It looks across the whole width of the depth grid, not just straight ahead, because a box off to one side still catches the robot as it passes.

Two actions: forward for 0.25 s, or turn for 0.2 s. A turn goes towards the side with more room, and once the robot has started turning it keeps going the same way until it drives forward again. That matters. A robot allowed to pick left or right afresh every step finds a corner where turning left shows a nearer wall and turning right shows the first one again, and it swaps between the two for ever.

The robot's view from above, with a box off to its right: the nearest reading anywhere in front gives the state, and a turn goes towards the side with more roomnearmidfar20 cm40 cmboxnearest: 28 cmthe statenearest is 28 cm:midthe two actionsforwardfor 0.25 sturnfor 0.2 s, to the sidewith more roomhere: the left. It keepsturning that way until itnext drives forward.
The robot looks across the whole width of the two level rows and keeps only the nearest reading. The box is off to the right, but it is still the nearest thing, 28 cm away, so the state is mid. There is more room on the left, so a turn would go left.
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def state():
    # the two level rows of the depth grid, all eight columns
    level = tof_grid()[16:32]
    # cm to the nearest thing anywhere in front
    ahead = min(level)
    return "near" if ahead < 20 else ("mid" if ahead < 40 else "far")

def room_left():
    level = tof_grid()[16:32]
    # the three left columns against the three right columns
    return min(level[0:3] + level[8:11]) >= min(level[5:8] + level[13:16])

# spin anticlockwise on the spot at 40
turn_left(40)
# do this 8 times (tick counts from 0)
for tick in range(8):
    # pause 0.4 s (the robot keeps doing what it was told)
    wait(0.4)
    print(round(heading()), "->", state(), "room left" if room_left() else "room right")
# all motors off
stop()

Run this in the simulator

The table

Q is a table with a number for every state and action: how good, as far as the robot knows so far, that action is in that state. It starts at zero. Learning means filling it in.

Choosing an action: mostly pick the best known one, but sometimes pick at random. The random ones are how it discovers anything; the fraction is called epsilon. It starts at 0.3 and is multiplied by 0.985 every step, so by the second half of the run the robot has all but stopped experimenting and just uses what it learned.

The reward, and the rule

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# random numbers
import random
random.seed(1)
ACTIONS = ["forward", "turn"]

def act(a):
    if a == "forward":
        forward(60); wait(0.25)
    else:
        turn_right(100); wait(0.2)

bumps, was_bumped = 0, False
# do this 30 times (step counts from 0)
for step in range(30):
    a = random.choice(ACTIONS)
    act(a)
    reward = 1.0 if a == "forward" else -0.2
    hit = bumped()
    # a new bump
    if hit and not was_bumped:
        reward = -20.0
        bumps += 1
    # still pushing against it
    elif hit:
        reward = -5.0
    was_bumped = hit
    print(a, "reward", reward)
# all motors off
stop()
print("bumps:", bumps)

Run this in the simulator

Random actions, and the reward each one earned. Forward pays 1 and a turn costs 0.2. A bump costs -20, once: bumped() stays true for a third of a second after a touch, so was_bumped makes sure one bump is paid for once. After that, every step still in contact costs -5, so pressing on against a box is never worth it either.

The learning rule is one line:

Q[s][a] += 0.3 * (reward + 0.8 * max(Q[s2].values()) - Q[s][a])

s is the state before the action, s2 the state after. The bracket is the surprise: what the action turned out to be worth (the reward now, plus 0.8 of the best the next state offers) minus what the table thought. Move the table's number 0.3 of the way towards the truth. The 0.8 is what makes it plan: an action that leads somewhere good is itself worth something.

The learning loop: the state, an action chosen from the table, the reward it earns, and the update to the table, then round again1. statenear, mid or far2. actionbest in the table,or at random now and then3. rewardforward +1, turn −0.2new bump −20, touching −54. updatemove Q[s][a] 0.3 ofthe way to reward+ 0.8 × best nextthe table Q, at the startforwardturnnear00mid00far00
One step of learning, round and round. The action is chosen from the table, the reward says how it went, and the update nudges one number in the table, the one for that state and that action. The state after the action becomes the state for the next step.

What it learns

Run the task and read the table at the end. One run learned this:

near {'forward': -0.9, 'turn': 2.7}
mid {'forward': 4.3, 'turn': 0.4}
far {'forward': 4.4, 'turn': 1.4}

Close to something, turn; otherwise, drive. Turning scores well in near even though it costs -0.2, because it leads to mid or far, where the table knows forward pays. Nobody wrote that rule. The robot bumped into things until the table said it. Each run learns a slightly different table, because the random tries differ.

Task: learn to wander

Let the robot learn for 88 seconds. It may bump early on. After 60 seconds it must not bump at all, and it must keep getting about the mat: rocking back and forth or spinning in one spot does not count. It must drive at least 250 cm in total. Print bumps: <n> at the end.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
bumps = 0
# do this 880 times (tick counts from 0)
for tick in range(880):
    # drive forward at 60 (keeps going until the next command)
    forward(60)
    # pause 0.1 s (the robot keeps doing what it was told)
    wait(0.1)
    if bumped():
        bumps += 1
        # spin clockwise on the spot at 60
        turn_right(60)
        # pause 0.5 s (the robot keeps doing what it was told)
        wait(0.5)
# all motors off
stop()
print('bumps:', bumps)

Challenges

  1. Keep epsilon at 0.3 for the whole run. How many bumps now?
  2. Give it three actions, forward, left and right, each choosing afresh. Watch what it does the first time it meets a corner.
  3. Make a bump cost 0 instead of -20. What does the table say about forward in near now, and where does the robot end up?