Reinforcement learning playgroundMiddleLesson 2916 min read

Q-learning step by step

A treasure hunt with rocks and traps. Build the Q-learning update line by line, see why it passes reward backwards, and read the map your agent learns.

✦ Ask the tutor 🧪 Lab · 30 min 📝 Lesson test

Speed

Lesson in motion

In 60 seconds

Q-learning step by step

A treasure hunt with rocks and traps. Build the Q-learning update line by line, see why it passes reward backwards, and read the map your agent learns.

1/4

In simple words

Imagine a treasure hunt where you only get a prize at the very end. The first time, you wander around. But next time you remember: "the square next to the treasure was great", then "the square next to that one was good too". Slowly the good feeling spreads backwards from the treasure to the start, like a trail of breadcrumbs.

A bandit has one state. A real game has many, and a good move now may only pay off later. Q-learning handles this. It keeps a table Q[state][action]: the agent's estimate of the total discounted reward it will collect if it takes that action in that state and then plays well afterwards.

If you took Simulation and sim-to-real, you saw the update in one line and a small grid robot. Here we slow down, pull the update apart, and look at what the table learns.

The update, one piece at a time

1
Act
In state s, take action a. See reward r and the next state s2.
2
Build a target
If the game ended, target = r. Otherwise target = r + gamma x (the best Q in s2).
3
Measure the surprise
error = target - Q[s][a]. Positive means "better than I thought".
4
Nudge
Q[s][a] = Q[s][a] + alpha x error. Alpha (0 to 1) is the learning rate: how big the nudge is.
5
Move on
s = s2 and repeat until the episode ends.

One update, with numberspython

alpha, gamma = 0.5, 0.9
Q_here = 0.0              # Q[s][a]: what we believed before
reward = -1.0             # one step cost us a point
best_next = 5.0           # the best Q in the next state, s2

target = reward + gamma * best_next      # -1 + 0.9 * 5 = 3.5
error = target - Q_here                  # 3.5: better than we thought!
Q_here = Q_here + alpha * error          # 0 + 0.5 * 3.5 = 1.75
print("target", target, "error", error, "new Q", Q_here)

The key idea is the target. It uses the agent's own current guess about the next state (best_next) instead of waiting for the end of the game. Learning from your own next guess is called temporal-difference (TD) learning. It is why the reward from the treasure spreads backwards, one square per visit.

Watch out

A common bug: when the episode has ended, there is no next state. Then the target must be just the reward. If you add gamma * max(Q[s2]) for the treasure square, the agent believes the game continues after it has finished.

Why Q-learning can learn from exploring

The target uses the best action in the next state, even if the agent will actually explore and do something random there. So Q-learning learns the value of playing well, while it behaves partly randomly. This is called off-policy learning. It is why an agent can explore with epsilon-greedy and still learn the best route.

Reading the table

After training, the agent's greedy policy is: in each state, pick the action with the highest Q. You can draw it as arrows on the map. The lab prints exactly that, so you can see the route the agent learned.

Setting	What it controls	If too small	If too large
alpha (learning rate)	How far each update moves Q	Learning is very slow	Estimates jump around with every lucky or unlucky step
gamma (discount)	How much later rewards count	Agent is short-sighted and may not value a far treasure	Values grow large and learning can be slower
epsilon (exploring)	How often to act randomly	May never find the treasure	Keeps stumbling into traps while learning
episodes	How many games to practise	Values have not spread back to the start yet	Wasted time, but no harm in a small game

Note

A table works when there are few states: here, 30 squares. A game of chess, or a robot's camera image, has far too many states for any table. Then a neural network is trained to estimate Q from the state. That is deep Q-learning. The update idea stays the same; only the table is replaced.

Try this. After you finish the lab, set gamma = 0.1 and train again. Print Q[START]. Why are the numbers near the start so small, and does the agent still find the treasure?

Watch and read more

Lab

A Q-learning agent that learns a safe, short route to the treasure on a 6 x 5 map with rocks and traps.

~30 min

The problem

The map has a start S, a treasure T (+10), traps X (-10, game over) and rocks # you cannot enter. Every move costs -1. The training loop, the map and the epsilon-greedy choice are ready. Only the learning is missing.

Press Run. q_update does nothing, so the Q table stays at zero and the learned route goes nowhere.
Write q_update: build the target (just r if done, else r + gamma * max(Q[s2])), then move Q[s][a] toward it by alpha times the error.
Run again. Read the arrow map and the route. Does it reach T without touching an X?
Press Check. (It uses the original map, so you may experiment freely afterwards.)
Experiments: train with only 20 episodes; then with gamma = 0.1. Write what changed and why.

Practice lab

Edit the code and run it. Python runs in your browser — nothing is sent to our server.

Ctrl + Enter to run

import random

# S start, T treasure (+10), X trap (-10), # rock. Every move costs -1.
MAP = [
    "S...#",
    ".#X..",
    "...#.",
    "#X...",
    "...X.",
    "#..#T",
]
ROWS, COLS = len(MAP), len(MAP[0])
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]    # up, down, left, right
ARROWS = "^v<>"
START = (0, 0)

def step(state, a):
    r, c = state
    nr, nc = r + ACTIONS[a][0], c + ACTIONS[a][1]
    if not (0 <= nr < ROWS and 0 <= nc < COLS) or MAP[nr][nc] == "#":
        nr, nc = r, c                         # bumped a rock or the edge: stay
    cell = MAP[nr][nc]
    if cell == "T":
        return (nr, nc), 10.0, True
    if cell == "X":
        return (nr, nc), -10.0, True
    return (nr, nc), -1.0, False

def q_update(Q, s, a, r, s2, done, alpha, gamma):
    # TODO: target = r if done, else r + gamma * max(Q[s2])
    #       then move Q[s][a] toward the target by alpha * (target - Q[s][a])
    pass

def train(episodes=500, alpha=0.5, gamma=0.9, epsilon=0.2, seed=0):
    rng = random.Random(seed)
    Q = {(r, c): [0.0] * 4 for r in range(ROWS) for c in range(COLS)}
    for _ in range(episodes):
        s = START
        for _ in range(100):
            if rng.random() < epsilon:
                a = rng.randrange(4)
            else:
                a = max(range(4), key=lambda i: (Q[s][i], rng.random()))  # random tie-break
            s2, r, done = step(s, a)
            q_update(Q, s, a, r, s2, done, alpha, gamma)
            s = s2
            if done:
                break
    return Q

def greedy_path(Q, max_steps=30):
    s, path = START, [START]
    for _ in range(max_steps):
        s, r, done = step(s, max(range(4), key=lambda i: Q[s][i]))
        path.append(s)
        if done:
            break
    return path

Q = train()
for r in range(ROWS):
    print(" ".join(MAP[r][c] if MAP[r][c] in "#XT" else ARROWS[max(range(4), key=lambda i: Q[(r, c)][i])]
                   for c in range(COLS)))
path = greedy_path(Q)
end = MAP[path[-1][0]][path[-1][1]]
print("Route ends on", repr(end), "after", len(path) - 1, "moves")
print("Q at start (up, down, left, right):", [round(q, 2) for q in Q[START]])

Output

No output. Add print(...) to see values.

You are done when

q_update uses only the reward as the target when done is True
Otherwise the target adds gamma times the best Q of the next state, and Q moves by alpha times the error
The arrow map leads from S to T around the traps in 9 moves
The experiments explain that 20 episodes is too few for reward to spread back, and gamma 0.1 makes far rewards almost invisible

Hard questions

Try to answer before you reveal. If you can answer these, you understood the lesson.

Q1The shortest route to the treasure passes right next to a trap. Q-learning takes it. Why might a real robot prefer a slightly longer route?Reveal

Q-learning learns the value of playing perfectly. In real life, a robot's moves can slip, or it may still explore, and one slip next to the trap costs -10. A longer route away from the trap is safer when actions are unreliable. SARSA, or adding random slips to training, tends to learn that safer route. For real robots, safety limits should also be enforced outside the learned policy.

Q2After training, the best Q value at the start is about -1.4. Can you explain that number?Reveal

The best route takes 9 moves: eight moves costing -1 and a final +10. With gamma = 0.9 the discounted return is -1 - 0.9 - 0.81 - ... (eight terms) + 0.9^8 x 10. The eight costs add up to about -5.70 and the prize is worth about 4.30, so the total is about -1.4. If your number differs a little, the values may not have fully settled yet. Working this out by hand is a great way to check that your update is right.

Please sign in to continue.

Questions people ask

Why is it called Q?

It comes from the original research, where Q stood for the "quality" of an action in a state. People still use the letter.

Does Q-learning always find the best route?

In a small game like this, with enough exploring, enough episodes and a sensible learning rate, it reliably finds it. The theory has conditions, such as trying every action in every state again and again. With too few episodes or too little exploring, it may settle for a worse route.

Why do all the Q values start at zero?

Zero is a simple, neutral guess. Some people start values high to encourage exploring early, like the optimistic trick from the bandit lesson. With a -1 cost per step, zero is already a little optimistic, which helps.

What is the difference between Q-learning and SARSA?

SARSA is a close cousin. Its target uses the action the agent actually takes next, including random exploring ones, instead of the best one. So SARSA learns the value of the way it really behaves, and near traps it often learns a safer route that stays further away.

Lesson test

5 questions. Get 3 right (60%) to pass and complete this lesson.

Q-learning step by step

Q-learning step by step

The update, one piece at a time

Act

Build a target

Measure the surprise

Nudge

Move on

Why Q-learning can learn from exploring

Reading the table

Watch and read more

The problem

Practice lab

You are done when

Hard questions

Questions people ask