Watkins's Q(lambda) Algorithm

Watkins's Q lambda lets one reward teach a whole trail of past moves at once with eligibility traces. The moment the agent tries something exploratory, the trail wipes clean so detours never rewrite the optimal plan.

Greedy steps decay traces by 0.72 while teaching past states, then one exploratory action zeroes every trace and quarantines its reward

Why Does This Exist?

One-step Q-learning moves reward backward one state per visit. A goal a hundred steps away needs a hundred episodes before the start state hears about it. On-policy methods fixed this with eligibility traces: each visit leaves a fading memory, so one error updates the whole recent trail at once.

Traces clash with Q-learning's off-policy nature. Q-learning learns the greedy policy while behaving exploratorily, and rewards collected after a random detour describe the detour, not the optimal plan. Crediting the trail with them corrupts every value upstream.

Watkins's answer, from his 1989 thesis, is a cutoff rule: traces decay by $\gamma \lambda$ while actions stay greedy and reset to zero the instant an exploratory action is taken. Fast credit along the optimal path, quarantine everywhere else.

This page covers the five-step update and the cutoff, with a hand-computed three-step trail. The on-policy origin is SARSA lambda, the gentler modern fix is the tree backup algorithm, and the one-step base is Q-learning.

The one idea you need first

Q-learning's error is $\delta_t = R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)$ : reward plus the best next value minus the current estimate. Traces decide how far back that error travels. The max is what makes the method off-policy, and the cutoff is what keeps the max honest.

Think of It Like This

Grading a relay team, ignoring the lap someone jogged

A coach grades relay legs by the team's finishing time, sharing credit down the whole order of runners. That works while everyone sprints. But on one lap a runner decides to jog sideways to test new shoes. The slow finish says nothing about the sprinters before him, so the coach draws a line: legs before the jog keep the credit they already banked, and the jogging lap is graded alone.

Watkins's cutoff is that line. Greedy legs share each error through decaying traces; the exploratory leg starts a fresh page. Earlier legs are protected from blame for a detour they did not choose.

Where the analogy stops: the coach's line is judgment, while the cutoff is arithmetic. A non-greedy action provably breaks the multi-step return's claim to estimate optimal values, so the zeroing is a correctness rule, not mercy.

How It Actually Works

Each step computes the Q-learning error $\delta_t$ with the max over next actions, bumps the current pair's trace by one, updates every pair by $\alpha \, \delta_t \, z_t(s, a)$ , then carries traces forward. While the next action is greedy they shrink by $\gamma \lambda$ ; the first exploratory action zeroes all of them:

$z_{t+1}(s, a) = \gamma \lambda \, z_t(s, a) \quad \text{greedy next action}, \qquad z_{t+1}(s, a) = 0 \quad \text{otherwise}$

Here $\alpha$ is the step size, $\gamma$ discounts the future, and $\lambda$ in $[0, 1]$ sets how hungrily credit reaches back. The zeroing is mandatory because an $n$ -step return estimates optimal values only when every intermediate action was optimal; one detour voids the warranty for the whole trail behind it.

Worked example

States $S_0 \to S_1 \to S_2 \to$ terminal, $\gamma = 0.9$ , $\lambda = 0.8$ so traces decay by $0.72$ , $\alpha = 0.2$ . Values: $Q(S_0) = 4.0$ , $Q(S_1) = 5.0$ , $Q(S_2, \text{explore}) = 1.0$ , all traces zero.

Step 0, greedy: reward $2.0$ , next best $5.0$ . Error $2.0 + 0.9 \times 5.0 - 4.0 = 2.5000$ . Trace for $S_0$ goes $0 + 1 = 1.0$ , so $Q(S_0) = 4.0 + 0.2 \times 2.5 \times 1.0 = 4.5000$ . Next action is greedy, trace decays to $0.7200$ .

Step 1, greedy: reward $1.0$ , next best $6.0$ . Error $1.0 + 0.9 \times 6.0 - 5.0 = 1.4000$ . Both traces active: $Q(S_1) = 5.0 + 0.2 \times 1.4 = 5.2800$ , and $Q(S_0) = 4.5 + 0.2 \times 1.4 \times 0.72 = 4.7016$ . Then the next action is exploratory, so every trace resets to $0.0$ .

Step 2, exploratory: reward $3.0$ at the terminal. Error $3.0 - 1.0 = 2.0000$ , and $Q(S_2, \text{explore}) = 1.0 + 0.2 \times 2.0 = 1.4000$ . The older pairs sit at $4.7016$ and $5.2800$ , untouched: the detour's reward never reaches them.

Code

The three steps in plain Python, with type hints, matching the hand computation:

1Q: dict[str, float] = {"S0": 4.0, "S1": 5.0, "S2e": 1.0}2z: dict[str, float] = {"S0": 0.0, "S1": 0.0, "S2e": 0.0}3alpha, gamma, lam = 0.2, 0.9, 0.84
5def step(key: str, reward: float, next_best: float, greedy_next: bool) -> float:6    delta = reward + gamma * next_best - Q[key]7    z[key] += 1.08    for k in Q:9        Q[k] += alpha * delta * z[k]10    for k in z:11        z[k] = z[k] * gamma * lam if greedy_next else 0.012    return delta13
14print(f"d0 {step('S0', 2.0, 5.0, True):.4f}")  # -> d0 2.500015print(f"Q0 {Q['S0']:.4f} trace {z['S0']:.4f}")  # -> Q0 4.5000 trace 0.720016print(f"d1 {step('S1', 1.0, 6.0, False):.4f}")  # -> d1 1.400017print(f"Q0 {Q['S0']:.4f} Q1 {Q['S1']:.4f}")  # -> Q0 4.7016 Q1 5.280018print(f"d2 {step('S2e', 3.0, 0.0, True):.4f}")  # -> d2 2.000019print(f"Q0 {Q['S0']:.4f} Q2e {Q['S2e']:.4f}")  # -> Q0 4.7016 Q2e 1.4000

Watch Out For

Keeping traces alive across exploratory actions

Porting SARSA lambda code to Q-learning and leaving plain decay $z \leftarrow \gamma \lambda z$ is the classic bug: no greedy check, no reset. Earlier optimal decisions then absorb credit and blame from random detours, and values converge to a corrupted hybrid instead of the optimum. The symptom is control that plateaus below tabular Q-learning on the same task despite the fancier machinery.

Fix it with an explicit branch: compare the taken next action against the greedy set, and on mismatch zero every trace before the next step.

Exploring so much that traces never survive

The cutoff has a price: with heavy exploration, traces die every few steps and the method collapses to one-step Q-learning, losing the speed it was built for. The symptom is trace lifetimes averaging two or three steps in the logs while the algorithm was sold as multi-step.

Fix it by decaying exploration as values settle, or switch to tree backup, which scales traces by target probabilities instead of killing them outright.

The Quick Version

Watkins's Q lambda adds eligibility traces to off-policy Q-learning for multi-step credit in a single error.
Greedy next actions decay traces by $\gamma \lambda$ ; the first exploratory action zeroes all of them.
In the worked trail, errors 2.5 and 1.4 lift $Q(S_0)$ to 4.7016 and $Q(S_1)$ to 5.2800, then the cutoff quarantines reward 3.0.
Zeroing is a correctness rule: post-detour rewards cannot evaluate the optimal plan.
Check the greedy branch first when values corrupt, and watch exploration rates that silently reduce the method to one step.