ML10.3 · LESSON 3 OF 6

Q-learning

Distinguish sequential decision-making, temporal prediction, recommendation and causal estimation.

THE IDEA

Learning values from experience instead of from a model

Value iteration needed the rules of the world. Q-learning works without them. It stores a table Q[state][action]: the return the agent expects if it takes that action now and then behaves well. It fills the table in by trying things and nudging each entry toward what actually happened.

the Q-learning update

target = r + gamma * max over a' of Q[next state][a']      (the move is not terminal)
target = r                                                 (the move ended the episode)

Q[s][a] = Q[s][a] + alpha * (target - Q[s][a])

Worked example: current Q is 2, the reward is 1, gamma is 0.9 and the best next-state value is 4. The target is 1 + 0.9 × 4 = 4.6. With alpha = 0.5 the new Q is 2 + 0.5 × (4.6 − 2) = 3.3. The estimate moved half-way toward the target.

Predict first. The move ends the episode (terminal). Current Q is 0, reward is 1, alpha is 0.5. What is the new Q?

Watch the table fill in

In a small grid world every reward starts at zero, so the first updates change nothing. The first real learning happens when the agent stumbles into the goal or the pit. That information then spreads backward one step per visit, because each update uses the next state's current value.

alpha (learning rate)0.5epsilon (exploration)0.3gamma (discount)0.9

Press Step. Each step picks a move (random with probability epsilon, otherwise the best Q, ties at random), then updates one table entry.

steps 0 · episodes 0 · reached goal 0x · fell in pit 0x

green arrow = single best move; dot = tie or nothing learned yet

Step through single updates or run whole episodes. The arithmetic of the latest update is written out, and the greedy arrows appear as values form.

Two details matter. The agent must still explore: with epsilon-greedy it sometimes acts at random, otherwise it can repeat a mediocre route forever. And the target uses the best next action, not the one the agent will actually take, which is why Q-learning is called off-policy.

Chapter context

These topics change the structure of the learning problem. Their first lesson is to identify what a prediction or action is allowed to depend on and how feedback is produced. Each section is a bridge to a larger specialist subject.

TRY IT YOURSELF

Part 1. Do it hands-on

You control alpha, gamma and epsilon and decide when to take single steps or run episodes. The goal is a table whose greedy arrows lead safely to the goal.

alpha (learning rate)0.5epsilon (exploration)0.3gamma (discount)0.9

Press Step. Each step picks a move (random with probability epsilon, otherwise the best Q, ties at random), then updates one table entry.

steps 0 · episodes 0 · reached goal 0x · fell in pit 0x

green arrow = single best move; dot = tie or nothing learned yet

To do: Take a step whose TD update actually changes a Q value (the reward finally shows up in a target)
To do: Teach the agent the last move: Q(state 1, right) above 0.5, meaning one step left of the goal
To do: Make the agent fear the pit: some Q entry below -0.4 for a move into the pit
To do: Train until following the greedy arrows from the start reaches the goal without entering the pit

Part 2. Do it in code

Write q_update(Q, s, a, r, s2, done, alpha, gamma): update Q[s, a] in place with Q[s,a] += alpha * (target - Q[s,a]), where target = r for a terminal transition (done is True) and r + gamma * max(Q[s2]) otherwise. Return the new value.
Write greedy_action(Q, s): the best action in row s, ties going to the lowest index.
Write train(episodes, alpha, gamma, epsilon, seed): with Q = np.zeros((9, 4)) and rng = random.Random(seed). Each episode starts at state 6 and takes at most 30 steps. Each step: if rng.random() < epsilon pick rng.randrange(4), else greedy_action. Use env_step(s, a) -> (s2, r, done) (given), call q_update, and stop the episode when done. Return Q.

import random
import numpy as np

# Given: a 3x3 grid, states 0..8 row by row, actions 0 up, 1 right, 2 down, 3 left.
# State 2 (top right) is the goal (+1), state 4 (centre) is a pit (-1). Both end the episode.
def env_step(s, a):
    r, c = divmod(s, 3)
    dr, dc = [(-1, 0), (0, 1), (1, 0), (0, -1)][a]
    nr, nc = r + dr, c + dc
    if nr < 0 or nr > 2 or nc < 0 or nc > 2:
        nr, nc = r, c
    s2 = nr * 3 + nc
    if s2 == 2:
        return s2, 1.0, True
    if s2 == 4:
        return s2, -1.0, True
    return s2, 0.0, False

def q_update(Q, s, a, r, s2, done, alpha, gamma):
    pass

def greedy_action(Q, s):
    pass

def train(episodes, alpha, gamma, epsilon, seed):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Should a terminal transition always add a next-state bootstrap term?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

G_t=\sum_{k\ge0}\gamma^k r_{t+k+1},\quad Q(s,a)\leftarrow Q(s,a)+\alpha[r+\gamma\max_{a'}Q(s',a')-Q(s,a)].

For a terminal transition the continuation term is zero. A policy-gradient estimator uses a term proportional to $\nabla\log\pi_\theta(a\mid s)$ times a return or advantage estimate.

Worked example

For a nonterminal transition, current Q=2, reward=1, discount=0.9 and best next Q=4 give target 1+0.9×4=4.6. With alpha=0.5, updated Q is 2+0.5×(4.6−2)=3.3. Reusing the same target for a terminal transition would be incorrect.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
q, reward, discount, next_q, rate = 2, 1, .9, 4, .5
target = reward + discount*next_q
assert isclose(target, 4.6)
assert isclose(q+rate*(target-q), 3.3)
terminal_target = reward
assert q+rate*(terminal_target-q) == 1.5

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Prediction is not intervention. Randomly splitting overlapping time windows can leak future information. An environment reward is a modeling choice and may omit important real-world consequences.