Q-Learning, in depth: the Bellman target, off-policy updates, a hand-worked example, convergence conditions, SARSA, Double Q-learning and DQN

The problem: action values and the Bellman equation

The setting is a Markov decision process: states s, actions a, a transition distribution P(s-next given s, a), a reward r and a discount factor gamma between 0 and 1. A policy chooses actions; its return is the discounted sum of future rewards. The action value Q of a policy at (s, a) is the expected return from taking a in s and following the policy afterwards.

The optimal action value Q* satisfies the Bellman optimality equation:

Q*(s, a) = E[ r + gamma * max_a' Q*(s', a') | s, a ]

If you knew Q*, acting optimally would be trivial: in each state pick the action with the largest Q*. If you knew P and r, you could compute Q* by value iteration, applying the right-hand side repeatedly until it stops changing, because that operator is a contraction with factor gamma. Q-learning keeps the iteration and drops the model: it replaces the expectation with a single sampled transition and moves a little towards it.

This is the difference from bandits, where an action's reward does not depend on future states; see multi-armed bandits for that simpler case. In an MDP the value of an action includes everything it makes possible later, which is what the max over next actions captures.

The update rule and why it is off-policy

Observe a transition (s, a, r, s-next). Form the target r plus gamma times the largest Q value at s-next, or just r if s-next is terminal. Move Q(s, a) a fraction alpha towards it:

Q[s, a] += alpha * (r + gamma * max(Q[s_next]) * (not done) - Q[s, a])

The bracketed quantity is the temporal-difference error: how surprised the estimate was. Alpha is the learning rate, a step size between 0 and 1.

The target uses the max over next actions, not the action the agent will actually take next. The agent can therefore behave however it likes, randomly, cautiously, from a log of someone else's play, and still learn the value of the greedy policy. That property, learning about one policy while following another, is called off-policy learning. It is why Q-learning can reuse old experience, and why it combines with replay buffers in DQN.

Worked example: a four-state corridor by hand

Take a corridor of states S0, S1, S2 and a terminal goal G. Actions are left and right; left from S0 stays put. Entering G gives reward 1 and every other step gives 0. Use gamma 0.9, alpha 0.5, and start all Q values at 0.

Episode 1 starts at S2 and moves right into G. The target is 1, since G is terminal, so Q(S2, right) becomes 0 + 0.5 times (1 - 0) = 0.5.

Episode 2 starts at S1. Moving right gives reward 0 and lands in S2, whose best value is 0.5. The target is 0 + 0.9 times 0.5 = 0.45, so Q(S1, right) becomes 0.225. Then from S2, right into G: the target is 1 again and Q(S2, right) moves from 0.5 to 0.75.

Keep going and Q(S2, right) approaches 1, Q(S1, right) approaches 0.9 and Q(S0, right) approaches 0.81. Two lessons generalise. Value propagates backwards one transition per update, so long horizons with sparse rewards learn slowly. And the discount does the real work of preferring short paths: with gamma 1 every path that reaches G is worth 1, and nothing makes the agent hurry.

A complete tabular implementation

The implementation below is complete and dependency-free apart from NumPy. The environment is the cliff-walking grid from Sutton and Barto: 4 rows by 12 columns, start bottom-left, goal bottom-right, the cells between them a cliff that costs -100 and sends you back to the start; every step costs -1.

import numpy as np

ROWS, COLS = 4, 12
START, GOAL = (3, 0), (3, 11)
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]          # up, right, down, left

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

def q_learning(episodes=500, alpha=0.5, gamma=1.0, eps=0.1, seed=0):
    rng = np.random.default_rng(seed)
    Q = np.zeros((ROWS, COLS, 4))
    returns = []
    for _ in range(episodes):
        s, done, total = START, False, 0.0
        while not done:
            if rng.random() < eps:
                a = int(rng.integers(4))
            else:                                    # break ties randomly
                a = int(rng.choice(np.flatnonzero(Q[s] == Q[s].max())))
            s2, r, done = step(s, a)
            target = r if done else r + gamma * Q[s2].max()
            Q[s][a] += alpha * (target - Q[s][a])
            s, total = s2, total + r
        returns.append(total)
    return Q, returns

Q, returns = q_learning()
print("mean return, last 100 episodes:", np.mean(returns[-100:]))

Random tie-breaking matters more than it looks: with Q initialised to zero, a argmax that always picks the first action makes the agent push into the same wall for a long time. The greedy path this learns runs along the cliff edge, the shortest route, 13 steps.

What the convergence guarantee requires

Watkins and Dayan proved that tabular Q-learning converges to Q* with probability 1, under conditions worth reading carefully, because each one maps to a practical failure when violated:

• Every state-action pair is visited infinitely often. Exploration must never stop completely. A greedy agent that never tries an action can never correct its estimate of it.
• Step sizes satisfy the Robbins-Monro conditions. For each pair, the sum of alphas diverges and the sum of their squares converges, for example alpha equal to 1 over the visit count. A constant alpha, which almost everyone uses, does not converge exactly; it keeps tracking with noise proportional to alpha. In deterministic environments such as the cliff that noise is small, and in stochastic ones it is not.
• The table is exact. The proof is for lookup tables. With function approximation the guarantee disappears, which is the story of DQN below.
• Rewards are bounded and gamma is below 1, or episodes terminate.

The guarantee is also asymptotic. It says nothing about how many samples you need, and for large state spaces the answer is far too many: tabular Q-learning is practical when the states fit in memory and each is visited many times.

Exploration schedules

Epsilon-greedy is the default: with probability epsilon act randomly, otherwise greedily. Decay epsilon over time, from 1.0 to something like 0.05, so early learning explores widely and later learning refines. Never decay to exactly zero during training if you want the convergence conditions to hold.

Two alternatives are worth knowing. Optimistic initialisation sets Q values above any achievable return so every untried action looks attractive until tried; it is free and effective in small deterministic problems. Boltzmann or softmax exploration picks actions with probability proportional to exp(Q / temperature), so near-ties are explored more than clearly bad actions. In sparse-reward problems all of these struggle, because random actions rarely reach the reward at all; count-based bonuses and curiosity methods exist for that case.

Q-learning versus SARSA on the cliff

SARSA differs by one term: its target uses the action the agent actually takes next, r + gamma * Q[s_next, a_next], instead of the max. That makes it on-policy: it learns the value of the exploratory policy it is following.

On the cliff, with epsilon 0.1, the difference is visible. Q-learning learns the optimal path along the edge, but while it still explores, random steps knock it off the cliff, so its online return during training is worse. SARSA learns a safer path one or two rows up, because its values account for its own random steps; its online return is better, and its final greedy path is longer. Sutton and Barto use exactly this example. The practical rule: if the agent's exploratory behaviour has real costs while learning, as on a physical robot, the on-policy answer may be the one you want.

Maximisation bias and Double Q-learning

The max in the target is taken over noisy estimates, and the expected maximum of noisy estimates is larger than the maximum of their expectations. Q-learning therefore overestimates, and the bias compounds through bootstrapping. In stochastic environments this can make an agent prefer actions whose payoffs are merely high-variance.

Double Q-learning (van Hasselt, 2010) keeps two tables, A and B. On each step it updates one at random, choosing the best next action with that table and evaluating it with the other:

if rng.random() < 0.5:
    a_star = QA[s2].argmax()
    QA[s][a] += alpha * (r + gamma * QB[s2][a_star] * (not done) - QA[s][a])
else:
    b_star = QB[s2].argmax()
    QB[s][a] += alpha * (r + gamma * QA[s2][b_star] * (not done) - QB[s][a])
# act with QA + QB

Separating selection from evaluation removes most of the upward bias. The same idea became Double DQN for neural networks.

From tables to networks: DQN

When states are images or continuous vectors, a table is impossible and a network Q(s, a; theta) replaces it. Naively applying the update to network weights is unstable, because Sutton and Barto's deadly triad is present: function approximation, bootstrapping and off-policy learning together can diverge. DQN (Mnih and colleagues, Nature 2015) stabilised it with two devices: an experience replay buffer that samples past transitions at random to break correlations, and a target network, a periodically copied snapshot used to compute targets so they do not move with every gradient step.

q = online(s).gather(1, a.unsqueeze(1)).squeeze(1)
with torch.no_grad():
    target = r + gamma * (1 - done) * target_net(s2).max(dim=1).values
loss = torch.nn.functional.smooth_l1_loss(q, target)

Value-based methods like this dominate discrete-action problems. Policy-gradient methods such as PPO dominate continuous control and LLM fine-tuning; see RL for LLMs for where those fit.

Failure modes

• No learning signal. Sparse rewards plus epsilon-greedy means the goal is never reached. Check that random episodes ever see a nonzero reward.
• Terminal handling bugs. Bootstrapping from a terminal state, or treating a time-limit cutoff as terminal, biases values. Distinguish terminated from truncated.
• Overestimation. Values that climb past any achievable return signal maximisation bias or divergence; use Double Q-learning and check against rollouts.
• Constant alpha in stochastic environments. Values keep oscillating. Decay alpha per state-action, or average over the final episodes.
• Argmax tie bias. Deterministic tie-breaking with zero-initialised tables stalls exploration.
• Gamma too high or too low. Near 1 slows learning and inflates variance; too low makes the agent myopic.

Trade-offs

What to do next

1. Run the cliff-walking code, plot the episode returns, and print the greedy path.
2. Change the target to SARSA and compare online returns and the learned path.
3. Add the corridor as a unit test: after training, Q(S0, right) should be close to 0.81.
4. Make the cliff slippery, with random moves 10 percent of the time, then compare Q-learning and Double Q-learning value estimates against Monte Carlo rollouts.
5. Replace epsilon-greedy with optimistic initialisation and measure episodes to convergence.
6. Move to a small DQN on a gymnasium environment once the tabular version behaves.