Learning from experience: Q-learning

When you move to a new city, nobody hands you a model of the traffic. You learn the streets by walking them. A shortcut that saved you ten minutes gets remembered; an alley that ended at a fence gets avoided. Over time you build up a sense of which turn is good from each corner, without ever drawing a map.

Value iteration, in the last lesson, needed the map: every transition probability and reward, in advance. This lesson’s agent learns from experience instead.

Values for actions

Without a model, knowing how good each square is does not tell you what to do: to pick a move from state values you would need to know where each move leads. So the agent learns the value of each move directly. The action valueAction valueThe return an agent can expect from taking a given action in a given state and acting well afterwards, written Q(s, a). The best action is the one with the highest Q.Open in glossary $Q(s, a)$ is the return you can expect from taking action $a$ in state $s$ and acting well afterwards. With a table of Q-values, choosing is easy: take the move with the highest Q.

The agent starts with every Q at 0 and improves them by trying moves.

Learning one move at a time

Suppose the agent is in state $s$, takes action $a$, receives reward $r$, and lands in $s'$. Before the move it believed $Q(s, a)$. After the move it has a better guess: the reward it actually got, plus the discounted value of the best move from where it landed:

The difference between the target and the old belief is the temporal difference errorTemporal difference learningLearning a value estimate from the next step's reward plus the estimate at the next state, instead of waiting for the final outcome. The gap between the two is the TD error.Open in glossary. The agent nudges its belief part of the way toward the target:

The learning rate $\alpha$ sets how far each nudge goes. This is Q-learningQ-learningA temporal difference method that learns action values from experience, updating toward the reward plus the discounted value of the best next action, whatever action the agent actually takes next.Open in glossary, introduced by Chris Watkins in his 1989 PhD thesis. It is the Bellman equation again, but with one sampled move standing in for the average over all possible outcomes. It needs no model at all: just the move, the reward, and where it landed. Watkins and Dayan (1992) proved that Q-learning converges to the optimal action values as long as every action keeps being tried in every state and the learning rate shrinks suitably over time.

The idea of learning a guess from a later guess, without waiting for the final outcome, is temporal difference learning, developed by Richard Sutton in the 1980s.

Watch it learn

The agent below acts with epsilon-greedyEpsilon-greedyAn exploration rule: with a small probability epsilon take a random action, otherwise take the action that currently looks best.Taught in Explore or exploit: banditsOpen in glossary exploration: usually the move with the highest Q, sometimes a random one. Every move costs −0.04; the exits pay +1 and −1 and end the episode, after which the agent starts again. Each cell is split into four triangles, one per move, colored by that move’s current Q-value.

import numpy as np

# A small cliff: start S bottom left, goal G bottom right, cliff C between.
# Every move costs 1; stepping onto the cliff costs 100 more and ends the episode.
H, W = 3, 6
start, goal = (2, 0), (2, 5)
cliff = {(2, c) for c in range(1, 5)}
moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # up, right, down, left

def step(s, a):
    r, c = s[0] + moves[a][0], s[1] + moves[a][1]
    nxt = (min(max(r, 0), H - 1), min(max(c, 0), W - 1))
    if nxt in cliff:
        return nxt, -101, True
    return nxt, -1, nxt == goal

def train(method, episodes=500, alpha=0.5, epsilon=0.1, seed=0):
    rng = np.random.default_rng(seed)
    Q = np.zeros((H, W, 4))
    def choose(s):  # epsilon-greedy, ties broken at random
        if rng.random() < epsilon:
            return int(rng.integers(4))
        q = Q[s]
        return int(rng.choice(np.flatnonzero(q == q.max())))
    for _ in range(episodes):
        s, a, done = start, choose(start), False
        while not done:
            s2, r, done = step(s, a)
            a2 = choose(s2)
            if done:
                target = r
            elif method == "q-learning":
                target = r + Q[s2].max()   # value of the best next action
            else:
                target = r + Q[s2][a2]     # value of the action it will take
            Q[s][a] += alpha * (target - Q[s][a])
            s, a = s2, a2
    return Q

def greedy_route(Q):
    s, route = start, [start]
    while s != goal and len(route) < 30:
        s, _, _ = step(s, int(np.argmax(Q[s])))
        route.append(s)
    return route

for method in ["q-learning", "sarsa"]:
    route = greedy_route(train(method))
    rows = sorted({r for r, _ in route})
    print(f"{method:10s}: {len(route) - 1} moves, uses rows {rows}")

q-learning: 7 moves, uses rows [1, 2]
sarsa     : 9 moves, uses rows [0, 1, 2]

What you just watched

Reward flows backward. At first only the move into the +1 learns that it is good. On a later visit, the cell before it sees a neighbor with a high Q, so its target rises too. Episode by episode, the news travels back toward the start until every cell on the way points home. With the default settings the agent finds the 9-move shortest route within about 30 episodes.

Exploring fades on a schedule. Exploration starts at 0.3 and shrinks a little after every episode. Early on, random moves discover the world; later they would only waste moves, so the agent leans more and more on what it knows. Exploration that never fades keeps paying a cost, as it did for epsilon-greedy in the bandits lesson.

Optimism explores too. With exploration at 0, a fresh agent still wanders. Every estimate starts at 0, and each move it tries costs −0.04, so the moves it has tried look slightly worse than the ones it has not. Picking the highest estimate keeps sending it somewhere new until it finds a reward. Here 0 is optimistic only compared with what the agent has experienced so far; the true values along the route to the +1 are above 0. Starting every estimate deliberately above any value the agent could reach, called optimistic initial values, uses the same effect on purpose.

Q-learning learns about the perfect walker. The target uses the best next move, whatever move the agent will actually make. So Q-learning learns the values of acting perfectly, even while it explores. That makes it off-policyOff-policy learningLearning about one policy (often the best one) while behaving according to another (often an exploring one). Q-learning is off-policy; SARSA is on-policy, learning about the policy it follows.Open in glossary: it learns about one policy (the best) while following another (the exploring one). It can even learn the optimal values while acting completely at random, given enough time.

SARSA and the cliff

SARSASARSAA temporal difference method like Q-learning, except it updates toward the value of the action the agent will actually take next, exploration included. Named for state, action, reward, state, action.Open in glossary changes one thing: its target uses the move it will actually take next, chosen with the same epsilon-greedy rule, instead of the best move.

The name lists what each update uses: state, action, reward, next state, next action. Rummery and Niranjan described it in 1994 and called it modified connectionist Q-learning; the name SARSA was Richard Sutton’s suggestion. SARSA is on-policy: it learns the value of the policy it is following, exploration included.

On the cliff, every move costs 1 and stepping off the edge costs 100 more. Q-learning learns the shortest route, right along the edge: perfect for a walker who never slips. But the agent does explore, so about one move in ten is random, and next to the edge a random move can be a fall. SARSA’s values include those falls, so it learns a longer route, well away from the edge. In our runs SARSA collected more reward per episode while learning than Q-learning did, even though Q-learning’s route is shorter. This is Example 6.6 in Sutton and Barto’s Reinforcement Learning: An Introduction. If exploration is gradually reduced to zero, both methods eventually learn the edge route.

From tables to networks

A table needs one entry per state and action, and it learns nothing about a cell it has never visited. That is fine for a 30-cell maze and hopeless for a video game, where the state is the screen.

The fix is to estimate values with a neural network that takes the state as input. Gerald Tesauro’s TD-Gammon (1992) trained a network with temporal difference learning on games of backgammon against itself, learning only from the outcomes of those games; later versions, with some hand-designed inputs added, played at a strong master level. In 2013 and 2015, DeepMind’s deep Q-network (DQN) used a convolutional network to estimate Q-values from raw screen pixels and the score, and one set of settings learned to play dozens of Atari 2600 games, many at a level comparable to a professional games tester. It needed extra machinery to stay stable, such as replaying stored past experience instead of learning only from the latest move.