Q-learning explained

How Q-learning works: states, actions, rewards, the Q table, the update rule and epsilon-greedy exploration, shown on a robot learning to wander a cluttered mat without bumping. Change the reward or the exploration and watch what it learns instead.

Guidefree, runs in your browser

Q-learning is a way for a machine to learn what to do by trying things and being scored, with nobody telling it the right answer. It keeps a table of how good each action is in each situation, and after every move it nudges one number in that table. Chris Watkins described it in his PhD thesis in 1989. In 2015 a team at DeepMind replaced the table with a neural network and used it to learn Atari video games from the pixels on the screen, and the same ideas (states, actions, rewards and exploring) sit under the reinforcement learning used to train robots in simulation. On this page a small robot on a 1.5 metre mat with four boxes learns, in 88 seconds, to drive about without bumping into anything, and each demo below is a real program you can change and run.

In the overhead view of each demo, the blue line is where the robot has been and each red dot is a place where it bumped into a box or the edge of the mat. The chart shows two lines: bumps, the number of bumps so far (scale on the left), and epsilon, the chance that the next action is picked at random (scale on the right). A robot that is learning has a bumps line that climbs early on and then goes flat. At the end each program prints its Q table.

The idea in one loop

each step:
    look, and sum up the situation as a state s
    pick an action a: usually the best one in the table,
        but with chance epsilon a random one
    do it, and get a reward r
    look again: the new state s2
    Q[s][a] += rate × (r + discount × (best Q in s2) − Q[s][a])

Four words carry the whole method: state, action, reward and the Q table. The sections below take them in turn, then the rule on the last line, then the random picks.

States and actions

A state is the robot's summary of its situation. The table needs a row for every state, and the robot has to visit each state many times to learn what to do there, so there cannot be many of them.

This robot has three. It reads the two level rows of its 8 by 8 depth grid, tof_grid(), across all eight columns, and takes the nearest reading: under 20 cm is near, under 40 cm is mid, anything further is far. It looks across the whole width, and not just straight ahead, because a box off to one side still catches the robot as it drives past.

There are 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 next drives forward. One step, with the looking and the learning, takes about a quarter of a second, so an 88 second run is about 360 steps.

Choosing the states and actions is the biggest decision in a Q-learning program, and small details matter. Set COMMIT = False in any demo below and a turn picks its side afresh every step. In a corner, turning left brings the other wall into view, so the next turn goes right, which brings the first wall back, and so on. Seed 1 gets away with it, but over seeds 1 to 20, 9 of the 20 runs spent their last 30 seconds swapping between left and right turns in one spot.

Rewards

After each action the program hands out a reward, one number that says how that went:

The robot is never told to avoid the boxes. It is paid for driving forward and fined for bumping, and avoiding the boxes is what it has to work out for itself. bumped() stays true for a third of a second after a touch, so the program remembers whether it was already bumped: a new bump costs 20, and after that every step still in contact costs 5, so pressing on against a box never pays either.

The Q table

Q[s][a] is the robot's current guess at how much reward it will collect, from now on, if it does action a in state s and then carries on doing the best it knows. Three states and two actions make six numbers. They all start at 0.

To act, the robot looks along the row for the state it is in and picks the action with the bigger number. When the two are tied, as they are at the start, Python's max picks the first action in the list, which is forward.

The update rule

After each step, one number in the table changes:

Q[s][a] += RATE * (reward + DISCOUNT * best_next - Q[s][a])

reward + DISCOUNT * best_next is what the action turned out to be worth: the reward it just earned, plus the best the table offers in the state it landed in. Take away what the table thought, Q[s][a], and what is left in the bracket is the surprise. The rule moves the number a fraction RATE of the way towards the new estimate. The surprise is often called the temporal difference error.

Here is the rule at work in the first demo below. The very first step is forward, in far. The reward is +1, the robot is still in far, and every number there is 0:

Q = 0 + 0.3 × (1 + 0.8 × 0 − 0) = 0.3

A few steps later it drives forward in mid for the second time. That number is 0.3 now, and so is the best number in mid, where it lands:

Q = 0.3 + 0.3 × (1 + 0.8 × 0.3 − 0.3) = 0.58

By 9.1 s, forward in near has climbed to 1.55, because until then driving forward had always paid. Then the robot drives forward in near into the edge of the mat. The best number in the state it lands in is also 1.55:

Q = 1.55 + 0.3 × (−20 + 0.8 × 1.55 − 1.55) = −4.54

One bump, and forward in near is the worst number in the table.

The learning rate (RATE, usually written α, alpha) sets how far one surprise moves the table. At 0.3 it moves 30 percent of the way. Close to 1, the table believes whatever happened last. Close to 0, it learns slowly, but one lucky or unlucky step does not throw it.

The discount (DISCOUNT, usually written γ, gamma) sets how much the future counts. It is what lets the robot plan: an action that leads somewhere good is worth something, even if it pays nothing itself. At 0.8, a reward one step away counts 0.8 of its size, two steps away 0.64, and so on. A robot that earns +1 on every step for ever has a value of

1 + 0.8 + 0.64 + 0.512 + ... = 1 / (1 − 0.8) = 5

so 5 is the most any number in this table can reach. Look out for it in the last two demos.

Exploring: epsilon-greedy

If the robot always picked the bigger number, it would never try anything the table does not already rate, and at the start the table rates nothing. So with a chance epsilon (ε) it picks an action at random instead. This is called epsilon-greedy: greedy (take the best) most of the time, random a fraction ε of the time. Choosing between trying something new and using what you know is called the exploration and exploitation trade-off.

Epsilon starts at 0.3 and is multiplied by 0.985 after every step, which is called decay. In the first demo it is 0.16 after 10 s, 0.09 after 20 s, 0.05 after 30 s and 0.02 after 40 s. Early on the robot tries things. By the second half of the run it has all but stopped experimenting and uses what it has learned.

The learner

This is the whole program. The numbers at the top are the ones the rest of the page changes.

from bugbot import *
import random
connect()

# change these numbers and press Run
RATE = 0.3           # learning rate: how far each surprise moves the table
DISCOUNT = 0.8       # how much the next state's best value counts
EPSILON = 0.3        # the chance of a random action at the start
DECAY = 0.985        # epsilon is multiplied by this every step
FORWARD = 1.0        # the reward for driving forward
TURN = -0.2          # the reward for turning
BUMP = -20.0         # the reward for a new bump
PUSH = -5.0          # the reward for each step still touching it
COMMIT = True        # keep turning the same way until the next forward

random.seed(1)
ACTIONS = ["forward", "turn"]
STATES = ["near", "mid", "far"]
# the Q table: one number for each state and action
Q = {s: {a: 0.0 for a in ACTIONS} for s in STATES}

def state():
    level = tof_grid()[16:32]  # the two level rows, all 8 columns
    ahead = min(level)         # the nearest thing anywhere in front
    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])

way = None                     # the way the robot is turning, or None
def act(a):
    global way
    if a == "forward":
        forward(60); wait(0.25)
        way = None
        return
    if way is None or not COMMIT:  # a new turn: towards more room
        way = "left" if room_left() else "right"
    if way == "left":
        turn_left(100)
    else:
        turn_right(100)
    wait(0.2)

bumps, was_bumped = 0, False
epsilon = EPSILON
trail, hits = [], []
while clock() < 88:
    s = state()
    if random.random() < epsilon:
        a = random.choice(ACTIONS)            # explore
    else:
        a = max(Q[s], key=Q[s].get)           # exploit
    act(a)
    reward = FORWARD if a == "forward" else TURN
    hit = bumped()
    x, y = position()
    if hit and not was_bumped:                # a new bump
        reward = BUMP
        bumps += 1
        hits.append((75 + x, 75 + y))
    elif hit:                                 # still pushing against it
        reward = PUSH
    was_bumped = hit
    s2 = state()
    # the update rule
    best_next = max(Q[s2].values())
    Q[s][a] += RATE * (reward + DISCOUNT * best_next - Q[s][a])
    epsilon = epsilon * DECAY

    trail.append((75 + x, 75 + y))
    draw("path", trail, "blue", "line")
    draw("bumps", hits, "red", size=4)
    plot("bumps", bumps)
    plot("epsilon", epsilon)
stop()
print("bumps:", bumps)
for s in STATES:
    print(s, {a: round(v, 1) for a, v in Q[s].items()})

The bumps line climbs once, at 9.1 s, and stays flat for the next 79 seconds. The table it prints at the end:

Close to something, turn; otherwise, drive. Turning scores well in near although it costs 0.2, because it leads to mid or far, where the table knows forward pays. That is the discount at work. Nobody wrote that rule. The robot bumped into something once and the table did the rest.

It also keeps going somewhere. After 60 s it drives forward on 103 steps and turns on 13, and its path covers most of the mat. The task checks for that: after 60 s the robot's positions have to spread at least 40 cm, so a robot that only rocks, spins or pushes in one spot fails, however few bumps it has.

Each run learns a different table, because the random tries differ. Change random.seed(1) to other numbers and run it again. Over seeds 1 to 20, the robot bumped 1.75 times on average, none of the 20 runs touched anything after 60 s, and all 20 passed the task.

Never stop exploring

The same program with DECAY = 1.0, so epsilon stays at 0.3 for the whole run.

from bugbot import *
import random
connect()

# change these numbers and press Run
RATE = 0.3           # learning rate: how far each surprise moves the table
DISCOUNT = 0.8       # how much the next state's best value counts
EPSILON = 0.3        # the chance of a random action at the start
DECAY = 1.0          # epsilon is multiplied by this every step
FORWARD = 1.0        # the reward for driving forward
TURN = -0.2          # the reward for turning
BUMP = -20.0         # the reward for a new bump
PUSH = -5.0          # the reward for each step still touching it
COMMIT = True        # keep turning the same way until the next forward

random.seed(1)
ACTIONS = ["forward", "turn"]
STATES = ["near", "mid", "far"]
# the Q table: one number for each state and action
Q = {s: {a: 0.0 for a in ACTIONS} for s in STATES}

def state():
    level = tof_grid()[16:32]  # the two level rows, all 8 columns
    ahead = min(level)         # the nearest thing anywhere in front
    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])

way = None                     # the way the robot is turning, or None
def act(a):
    global way
    if a == "forward":
        forward(60); wait(0.25)
        way = None
        return
    if way is None or not COMMIT:  # a new turn: towards more room
        way = "left" if room_left() else "right"
    if way == "left":
        turn_left(100)
    else:
        turn_right(100)
    wait(0.2)

bumps, was_bumped = 0, False
epsilon = EPSILON
trail, hits = [], []
while clock() < 88:
    s = state()
    if random.random() < epsilon:
        a = random.choice(ACTIONS)            # explore
    else:
        a = max(Q[s], key=Q[s].get)           # exploit
    act(a)
    reward = FORWARD if a == "forward" else TURN
    hit = bumped()
    x, y = position()
    if hit and not was_bumped:                # a new bump
        reward = BUMP
        bumps += 1
        hits.append((75 + x, 75 + y))
    elif hit:                                 # still pushing against it
        reward = PUSH
    was_bumped = hit
    s2 = state()
    # the update rule
    best_next = max(Q[s2].values())
    Q[s][a] += RATE * (reward + DISCOUNT * best_next - Q[s][a])
    epsilon = epsilon * DECAY

    trail.append((75 + x, 75 + y))
    draw("path", trail, "blue", "line")
    draw("bumps", hits, "red", size=4)
    plot("bumps", bumps)
    plot("epsilon", epsilon)
stop()
print("bumps:", bumps)
for s in STATES:
    print(s, {a: round(v, 1) for a, v in Q[s].items()})

The table learns the same lesson, turn when near and drive otherwise. But three steps in ten the robot ignores the table and picks at random, and half of those random picks are forward, whatever is in front. It bumps 3 times, the last at 50.2 s, into a box it was already close to.

On this seed it gets through the last 30 seconds without a bump. Over seeds 1 to 20 it was not so lucky: 8 of the 20 runs bumped into something after 60 s, and the average number of bumps doubled, from 1.75 to 3.5. Exploring is how a learner finds anything out, and every random step has a cost. That is the trade-off.

How fast epsilon decays changes the balance. Over seeds 1 to 20:

A fast decay stops exploring before the table has seen enough, so a run can lock into its first mistake: at 0.97, three runs spent the last 30 seconds turning round in one small patch, and at 0.95 one ended pushing into a corner. No decay never stops paying for random steps. 0.985 was the best of these, and it is the value the task's model answer uses.

Reward design

Q-learning finds whatever collects the most reward. It has no idea what you meant. The reward is the only description of the task the robot ever gets, so any gap in it is a gap the robot can find. This is called reward hacking, or specification gaming.

An earlier version of this learner is a good example. It had six states and a fourth action, backing off, which cost only 0.1. Forward paid +1 whether or not the robot got anywhere, so a forward step and a back step together earned 0.9 and never risked a bump. Over seeds 1 to 20, 8 runs spent their last 30 seconds driving up to a box, backing off and driving up again, without a bump and without going anywhere. That is why the learner on this page has no back action, and why the task now checks that the robot keeps getting about.

When bumping costs nothing

The same program with BUMP = 0.0 and PUSH = 0.0, so touching things is free.

from bugbot import *
import random
connect()

# change these numbers and press Run
RATE = 0.3           # learning rate: how far each surprise moves the table
DISCOUNT = 0.8       # how much the next state's best value counts
EPSILON = 0.3        # the chance of a random action at the start
DECAY = 0.985        # epsilon is multiplied by this every step
FORWARD = 1.0        # the reward for driving forward
TURN = -0.2          # the reward for turning
BUMP = 0.0           # the reward for a new bump
PUSH = 0.0           # the reward for each step still touching it
COMMIT = True        # keep turning the same way until the next forward

random.seed(1)
ACTIONS = ["forward", "turn"]
STATES = ["near", "mid", "far"]
# the Q table: one number for each state and action
Q = {s: {a: 0.0 for a in ACTIONS} for s in STATES}

def state():
    level = tof_grid()[16:32]  # the two level rows, all 8 columns
    ahead = min(level)         # the nearest thing anywhere in front
    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])

way = None                     # the way the robot is turning, or None
def act(a):
    global way
    if a == "forward":
        forward(60); wait(0.25)
        way = None
        return
    if way is None or not COMMIT:  # a new turn: towards more room
        way = "left" if room_left() else "right"
    if way == "left":
        turn_left(100)
    else:
        turn_right(100)
    wait(0.2)

bumps, was_bumped = 0, False
epsilon = EPSILON
trail, hits = [], []
while clock() < 88:
    s = state()
    if random.random() < epsilon:
        a = random.choice(ACTIONS)            # explore
    else:
        a = max(Q[s], key=Q[s].get)           # exploit
    act(a)
    reward = FORWARD if a == "forward" else TURN
    hit = bumped()
    x, y = position()
    if hit and not was_bumped:                # a new bump
        reward = BUMP
        bumps += 1
        hits.append((75 + x, 75 + y))
    elif hit:                                 # still pushing against it
        reward = PUSH
    was_bumped = hit
    s2 = state()
    # the update rule
    best_next = max(Q[s2].values())
    Q[s][a] += RATE * (reward + DISCOUNT * best_next - Q[s][a])
    epsilon = epsilon * DECAY

    trail.append((75 + x, 75 + y))
    draw("path", trail, "blue", "line")
    draw("bumps", hits, "red", size=4)
    plot("bumps", bumps)
    plot("epsilon", epsilon)
stop()
print("bumps:", bumps)
for s in STATES:
    print(s, {a: round(v, 1) for a, v in Q[s].items()})

The reward pays for choosing forward, whether or not the robot moves. So the robot drives into a corner and holds forward for the rest of the run, earning +1 every step while going nowhere. The table shows it: forward in near ends at 5.0, the most any number can reach at a discount of 0.8. The bumps line stops at 4 because pushing without ever letting go counts as one bump.

Over seeds 1 to 20, 14 of the 20 runs ended pushing against the edge of the mat or a box, and only 4 passed the task. Putting back just the −5 for each step in contact, with BUMP = 0.0 and PUSH = -5.0, brought that down to 6 stuck and 10 passing. Putting back just the −20 for a new bump, with PUSH = 0.0, was enough on its own: 19 of 20 passed. A bump that costs far more than pushing could ever earn back is what teaches the robot to keep clear.

When turning pays as well as driving

The same program with TURN = 1.0.

from bugbot import *
import random
connect()

# change these numbers and press Run
RATE = 0.3           # learning rate: how far each surprise moves the table
DISCOUNT = 0.8       # how much the next state's best value counts
EPSILON = 0.3        # the chance of a random action at the start
DECAY = 0.985        # epsilon is multiplied by this every step
FORWARD = 1.0        # the reward for driving forward
TURN = 1.0           # the reward for turning
BUMP = -20.0         # the reward for a new bump
PUSH = -5.0          # the reward for each step still touching it
COMMIT = True        # keep turning the same way until the next forward

random.seed(1)
ACTIONS = ["forward", "turn"]
STATES = ["near", "mid", "far"]
# the Q table: one number for each state and action
Q = {s: {a: 0.0 for a in ACTIONS} for s in STATES}

def state():
    level = tof_grid()[16:32]  # the two level rows, all 8 columns
    ahead = min(level)         # the nearest thing anywhere in front
    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])

way = None                     # the way the robot is turning, or None
def act(a):
    global way
    if a == "forward":
        forward(60); wait(0.25)
        way = None
        return
    if way is None or not COMMIT:  # a new turn: towards more room
        way = "left" if room_left() else "right"
    if way == "left":
        turn_left(100)
    else:
        turn_right(100)
    wait(0.2)

bumps, was_bumped = 0, False
epsilon = EPSILON
trail, hits = [], []
while clock() < 88:
    s = state()
    if random.random() < epsilon:
        a = random.choice(ACTIONS)            # explore
    else:
        a = max(Q[s], key=Q[s].get)           # exploit
    act(a)
    reward = FORWARD if a == "forward" else TURN
    hit = bumped()
    x, y = position()
    if hit and not was_bumped:                # a new bump
        reward = BUMP
        bumps += 1
        hits.append((75 + x, 75 + y))
    elif hit:                                 # still pushing against it
        reward = PUSH
    was_bumped = hit
    s2 = state()
    # the update rule
    best_next = max(Q[s2].values())
    Q[s][a] += RATE * (reward + DISCOUNT * best_next - Q[s][a])
    epsilon = epsilon * DECAY

    trail.append((75 + x, 75 + y))
    draw("path", trail, "blue", "line")
    draw("bumps", hits, "red", size=4)
    plot("bumps", bumps)
    plot("epsilon", epsilon)
stop()
print("bumps:", bumps)
for s in STATES:
    print(s, {a: round(v, 1) for a, v in Q[s].items()})

Now a turn pays as much as a forward step and can never lead to a bump. By 30 s the robot has turned on 134 steps and driven forward on 12, and from 36.7 s to the end it does nothing but turn. Turn ends at 5.0 in both mid and far: spinning for ever is worth as much as anything can be. It scores well, it never bumps, and it is not wandering.

Over seeds 1 to 20, 4 runs spun like this one and 15 passed, because with forward and turn paying the same, which one wins depends on which the table happened to rate first. A reward that leaves the outcome to luck is not a specification. The fix is to pay for what you want rather than for a command: here, driving forward.

The learning rate and the discount

The same kind of test, over seeds 1 to 20, with one number changed at a time from the first demo:

A high learning rate lets one unlucky step rewrite a number, and a low one averages the luck out, at the cost of learning slowly. On this task 0.1 and 0.3 did about equally well, and 0.9 was worse.

With DISCOUNT = 0.0 the robot counts only the reward it gets right now, so each number is just the average of the next reward. That still works here, because turning away from a box is the better choice even judged one step at a time: a turn costs 0.2 and a bump costs 20. Seed 1 learns near turn −0.2 against forward −2.1. What it loses is the reason to prefer states with room ahead, which the discount supplies.

How to set up a Q-learning problem

1. Choose a few states that separate the situations needing different actions. Start with fewer than you think you need.
2. Choose a few actions, each long enough to change the state, and check that no pair of them can undo each other for ever.
3. Write the reward for the outcome you want, and charge for everything you do not want. Pay for results rather than for commands.
4. Start epsilon somewhere between 0.1 and 0.3 and decay it, so that exploring has mostly stopped before the part of the run you judge.
5. A learning rate between 0.1 and 0.5 and a discount between 0.8 and 0.99 are common starting points.
6. Watch what the robot does, not only the score. A robot that never bumps may be rocking, spinning or pushing in one spot.
7. Run several seeds before you believe a result. One run is one set of dice rolls.

Questions

What is Q-learning in simple terms?

It is a way for a program to learn which action to take in each situation from rewards alone. It keeps a table with a number for every situation (state) and action, meaning how much reward that action will lead to. After every step it moves that number a little towards what actually happened, and it mostly picks the action with the biggest number, with a few random picks so that it keeps trying new things.

What does the Q in Q-learning stand for?

Q is the name of the function the table stores, Q(s, a): the value of taking action a in state s and then acting as well as possible. It is often read as the quality of that action in that state.

What is the Q-learning formula?

Q(s, a) ← Q(s, a) + α × (r + γ × max Q(s', a') − Q(s, a)), where s is the state, a the action, r the reward, s' the next state, and the max is over the actions a' in the next state. α is the learning rate and γ the discount. In Python on this page it is Q[s][a] += RATE * (reward + DISCOUNT * max(Q[s2].values()) - Q[s][a]).

What is epsilon-greedy exploration?

A rule for choosing actions: with chance epsilon, pick an action at random; otherwise pick the action with the best value in the table. The random picks are how the learner finds out about actions it has not tried. Epsilon usually starts fairly high and decays, so the learner explores early and uses what it knows later. On this page, keeping epsilon at 0.3 for the whole run doubled the average number of bumps, from 1.75 to 3.5, and 8 runs in 20 were still bumping after 60 s.

What do the learning rate and discount factor do?

The learning rate (alpha) sets how far each new experience moves the table: 1 replaces the old value with the new estimate, 0 never changes it. The discount (gamma) sets how much future rewards count compared with the reward now: 0 cares only about the next reward, and values close to 1 plan a long way ahead. With a reward of 1 on every step for ever, the total value is 1 / (1 − γ), which is 5 at γ = 0.8.

Why does my Q-learning agent get stuck in a loop?

Usually because the loop earns reward, or costs less than getting out. An earlier version of the learner on this page learned to drive forward and back in front of a box, because forward paid +1 and backing off cost only 0.1. With turning paid as well as driving, it spun on the spot. With a turn that picked its side afresh every step, it swapped between left and right in a corner. Look at what the reward pays for and what the actions allow, and pay for the result you want rather than for an action.

What is reward hacking?

When a learner finds a way to score well that is not the behaviour you wanted, because the reward did not say exactly what you meant. On this page, with bumping made free, the robot learned to push into a corner of the mat for the last 44 seconds, earning +1 a step for choosing forward while going nowhere. The learner is doing its job; the reward is the thing that is wrong.

What is the difference between Q-learning and SARSA?

Both update a table of action values after every step. Q-learning uses the best value in the next state, whatever action is actually taken next, so it learns the value of acting as well as possible. SARSA uses the value of the action it actually takes next, random picks included, so it learns the value of the way it actually behaves. The names for this are off-policy (Q-learning) and on-policy (SARSA).

What is the difference between Q-learning and deep Q-learning?

Q-learning stores one number for every state and action in a table, which only works when there are few states. Deep Q-learning replaces the table with a neural network that takes the state in and gives a value for each action out, so it can handle states that are far too many to list, such as the pixels of a game screen. The update rule is the same idea: move the prediction towards the reward plus the discounted best value of the next state.

Is Q-learning supervised or unsupervised learning?

Neither. It is reinforcement learning. Supervised learning is given the right answer for each example, and unsupervised learning is given no score at all. A reinforcement learner is never told the right action, only a reward after it acts, and it has to work out from that which actions were good.

How do you write Q-learning in Python?

Store the table as a dictionary of dictionaries, Q[state][action], all starting at 0. In a loop: work out the state from the sensors, pick an action (random with chance epsilon, otherwise max(Q[s], key=Q[s].get)), do it, work out the reward, read the new state, and apply Q[s][a] += RATE * (reward + DISCOUNT * max(Q[s2].values()) - Q[s][a]). Multiply epsilon by a number just under 1 each step. Every demo on this page is a complete program of about 80 lines that does exactly this.

Is Q-learning on the GCSE or A level specification?

Not by name. None of the GCSE or A level Computer Science specifications (AQA, OCR, Pearson Edexcel, Eduqas) ask for Q-learning or reinforcement learning. Pearson Edexcel GCSE Computer Science does ask students to know about the issues raised by artificial intelligence, machine learning and robotics, and a robot that learns from rewards is a concrete example to discuss. Q-learning also makes a good A level Computer Science programming project: the table is a dictionary of dictionaries, and the whole method fits in one loop.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. 8.5 Learning by reward Learning, Robot club
2. U12.1 Learning a behaviour Learning, and the capstone, University
3. U12.4 Policy search on a robot Learning, and the capstone, University
4. U12.5 Reward is a specification Learning, and the capstone, University