Q-learning

The big idea

Value iteration ( Sequential decisions: MDPs (bridge to RL) ) computes how good each state is, but it needs the full model: every transition probability and every reward. A robot, a game-playing program or a trading agent usually has no such model. It can only act and see what happens.

Q-learningA reinforcement learning algorithm that learns Q(s, a), the value of each action in each state, from experienced transitions, by nudging each estimate toward the reward plus the discounted best value of the next state. learns from that experience directly. It keeps a table with one number per state and action, Q(s, a): "how much total reward do I expect if I do this here and act well afterwards?" After every single step it nudges one entry toward a better guess. Think of learning the fastest routes in a new city with no map. Each time you take a street, you update your estimate of how long it takes to get home from that corner by taking that street, using your estimate for the corner where you ended up. Good estimates near home spread outward, one street at a time, until every corner knows its best turn.

How it works

Step 1: The Bellman equation for Q

The optimal action values $Q^{\ast }$ satisfy a recursive equation. Taking action $a$ in state $s$ is worth the immediate reward plus the discounted value of the best action in the state you land in:

If you knew $Q^{\ast }$, acting optimally would be trivial: in every state, pick $\arg {\max }_a{Q}^{\ast }(s,a)$. Q-learning finds $Q^{\ast }$ without knowing the transition probabilities, by replacing the expectation with samples.

Step 2: The temporal-difference update

The agent is in $s$, takes $a$, receives $r$ and lands in $s^{\prime }$. That one transition gives a sample of the right-hand side, the TD targetThe value an estimate is moved toward in a temporal-difference update: the observed reward plus the discounted estimated value of the next state.. Move the current estimate a fraction $\alpha$ of the way toward it:

The bracket is the TD errorThe difference between the TD target and the current estimate; the learning signal of temporal-difference methods.: how surprised the agent was. $\alpha$ is the learning rate. A worked example with $\alpha =0.5$ and $\gamma =0.9$: $Q(s,\text{right})=0.2$, the step pays $r=0$, and the best action in $s^{\prime }$ has $Q=0.6$. The target is $0+0.9\times 0.6=0.54$, the error is $0.34$, and the new estimate is $0.2+0.5\times 0.34=0.37$.

This is called temporal-differenceLearning value estimates from other value estimates one step later, instead of waiting for the final outcome of an episode. learning because it updates a guess from a later guess, without waiting for the episode to end. It is the sampled, one-entry-at-a-time version of the value iteration sweep.

Step 3: Exploring while learning

The agent must try actions to learn their values, so it behaves epsilon-greedily ( Multi-armed bandits ): usually the action with the highest Q, sometimes a random one. Notice the max in the target. Whatever the agent actually does next, Q-learning updates toward the value of the best next action. It learns about the greedy policy while following an exploring one, which makes it an off-policyA learning method that evaluates or improves a different policy (here, the greedy one) from the one generating its experience (here, an exploring one). method. Its close relative SARSAAn on-policy temporal-difference method that updates Q(s, a) toward r plus gamma times Q(s', a'), where a' is the action actually taken next. uses the action it really takes next instead of the max, so it learns the value of the exploring policy itself.

Step 4: Convergence and its conditions

Watkins and Dayan (1992) proved that Q-learning converges to the optimal action values with probability 1, as long as every action is tried repeatedly in every state and the values are stored in a table (one entry per state-action pair), with suitably decreasing learning rates. Two practical consequences follow. Exploration is not optional, and a table only works when you can list the states. A 5 by 5 grid has 25; a chess board or a screen of pixels has more than you could ever visit, which is where Deep Q-Networks comes in.

Try it

• Press 1 episode. The agent wanders for 17 steps before the episode ends, and only one triangle lights up: the move that ended it. Every other update had a target of 0, because nothing else was known yet.
• Press 10 episodes a few times and watch brightness spread back from the goal, one cell further each time the agent passes. After 50 episodes the best Q at the start is 0.478, which is $0.9^7$: the reward of the goal, 8 moves away, discounted 7 times. That is the optimal value.
• Reset, set the discount to 0.5 and run 100 episodes. The best Q at the start is only 0.008 ($0.5^7$): the agent still finds the goal, but from far away it barely matters.

Going deeper

Code: Q-learning against SARSA on a cliff

import numpy as np

# Cliff walking: a 4 x 12 grid. Start bottom-left, goal bottom-right, the cells between them are a
# cliff (-100 and back to start). Every other step costs -1. Actions: up, right, down, left.
ROWS, COLS = 4, 12
START, GOAL = (3, 0), (3, 11)
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def step(s, a):
    r, c = s[0] + MOVES[a][0], s[1] + MOVES[a][1]
    r, c = min(max(r, 0), ROWS - 1), min(max(c, 0), COLS - 1)
    if r == 3 and 0 < c < 11: return START, -100.0             # fell off the cliff
    return (r, c), -1.0

def learn(method, episodes=500, alpha=0.1, gamma=1.0, eps=0.1, seed=0):
    rng = np.random.default_rng(seed)
    Q = np.zeros((ROWS, COLS, 4))
    pick = lambda s: rng.integers(4) if rng.random() < eps else int(np.argmax(Q[s]))
    totals = []
    for _ in range(episodes):
        s, a, total = START, None, 0.0
        a = pick(s)
        while s != GOAL:
            s2, r = step(s, a)
            a2 = pick(s2)
            if method == "Q-learning":                          # target uses the best next action
                target = r + gamma * Q[s2].max() * (s2 != GOAL)
            else:                                               # SARSA: the action actually taken next
                target = r + gamma * Q[s2][a2] * (s2 != GOAL)
            Q[s][a] += alpha * (target - Q[s][a])               # temporal-difference update
            s, a, total = s2, a2, total + r
        totals.append(total)
    return Q, np.array(totals)

for method in ["Q-learning", "SARSA"]:
    Q, totals = learn(method)
    s, path = START, [START]
    while s != GOAL and len(path) < 60:                         # follow the greedy policy
        s, _ = step(s, int(np.argmax(Q[s]))); path.append(s)
    rows = sorted({r for r, _ in path})
    print(f"{method:10s} reward per episode while learning (last 100): {totals[-100:].mean():6.1f}   "
          f"greedy path: {len(path) - 1} steps through rows {rows}")
    print(f"           Q at start: up {Q[START][0]:.1f}, right {Q[START][1]:.1f}")

Q-learning reward per episode while learning (last 100):  -40.9   greedy path: 13 steps through rows [2, 3]
           Q at start: up -13.0, right -109.0
SARSA      reward per episode while learning (last 100):  -22.6   greedy path: 15 steps through rows [1, 2, 3]
           Q at start: up -15.8, right -103.3

The cliff-walking grid from Sutton and Barto's textbook: 4 by 12 cells, start and goal at the two bottom corners, and a cliff between them that costs -100 and sends you back to the start. Every step costs -1. Both methods use epsilon 0.1 and learning rate 0.1 for 500 episodes.

• Q-learning learns the optimal path: 13 steps along the row just above the cliff, and $Q(\text{start},\text{up})=-13.0$ exactly, the cost of that path. Stepping right from the start, into the cliff, is valued at -109.
• SARSA learns a safer path, 15 steps, one row further from the edge.
• But SARSA earns more while learning: -22.6 per episode against -40.9 over the last 100 episodes. Q-learning's path is optimal for a greedy agent, but its agent still explores 10 percent of the time, and a random step next to the cliff is a fall. SARSA's values include its own exploration, so it keeps its distance.

Which is right depends on whether exploration continues after learning. If the deployed agent acts greedily, Q-learning's answer is the one you want. If it keeps exploring, or mistakes are expensive, SARSA's caution is worth having.

Practical details

• Learning rate. A constant $\alpha$ keeps adapting to change but never fully settles; a decaying one converges. In the code, $\alpha =0.5$ left noisy values on cells the agent rarely visits, so the greedy path sometimes bumped into walls; 0.1 was stable.
• Initial values. Starting Q at an optimistic value makes untried actions look attractive, a cheap form of exploration.
• Reward scale and discount. They set the size of values. With a discount near 1, a long chain of states must be updated before the start learns anything.

Trade-offs

Common mistakes

• Forgetting to stop bootstrapping at terminal states: the target there is just $r$.
• No exploration, so actions that were never tried keep their initial value forever.
• A learning rate of 1 in a random environment, so each estimate just copies the last sample.
• Judging a learned policy by the reward earned while exploring (or the reverse) without saying which.
• Using a table for continuous states by rounding them coarsely, which hides important differences.

Where you will see this

Tabular Q-learning appears wherever states and actions are few: small control problems, routing and scheduling toys, game levels with discrete positions, and as the teaching example in every RL course. Its real legacy is the update rule. Replace the table with a neural network and the same TD target trains deep Q-networks, which learned to play Atari games from pixels ( Deep Q-Networks ).

Check yourself

Recap