Later experience after a nongreedy choice does not follow the greedy target policy used by the backup.

Does a cut remove previous Q updates?

No; it clears eligibility for future propagation.

What happens at lambda equal to zero?

The tabular accumulating-trace method reduces to one-step Q-learning.

AI Glossary / Reinforcement learning and robotics / Advanced

Watkins Q(lambda)

Definition

Watkins Q(lambda) is an off-policy reinforcement-learning control method that combines Q-learning with eligibility traces. Its TD target uses the largest estimated next-state action value, while its traces are cut when the next behavior action is nongreedy. This prevents later rewards following a nongreedy decision from continuing to propagate through earlier traces as though the greedy target policy had been followed.

What it means

Q-learning evaluates a greedy target policy even when the behavior policy explores. Extending its credit assignment across several decisions therefore requires attention to whether the observed later actions match that target policy.

Watkins Q(lambda) retains multi-step traces while the behavior follows greedy choices. When the behavior deviates, the current one-step maximum-based backup still occurs, but older traces are removed before further rewards are propagated through that deviation.

This makes it different from on-policy SARSA(lambda), which includes the selected next action in its target and ordinarily keeps traces through exploration. It also differs from other Q(lambda) variants that use alternative corrections. Name the algorithm precisely when comparing results.

How it works

In the tabular accumulating-trace version, initialize state-action traces to zero at episode start. After observing reward and next state, choose the next behavior action and identify the maximum next-state action value using the pre-update estimates.

Compute delta as reward plus gamma times that maximum, minus the current Q estimate. Use zero continuation on genuine termination. Increment the current state-action trace by one, then update every Q entry by alpha times delta times its trace.

If the selected next action is greedy, multiply all traces by gamma times lambda. If it is strictly nongreedy, set all traces to zero. Continue by executing the selected behavior action. An action tied for the maximum counts as greedy; its selection need not match an arbitrary single tie-breaking label.

This rule limits the usable multi-step span when exploration is frequent. Lambda cannot preserve a trace after the algorithm explicitly clears it. Replacing-trace and true-online variants need their own stated update conventions. General function approximation and changing data distributions also require analysis beyond a short tabular update description.

Three practical examples

1. A grid-world learner backs delayed rewards through a run of greedy actions while resetting earlier traces after a nongreedy exploration choice.

2. A developer checks whether an epsilon-greedy action that happens to attain the maximum is incorrectly treated as a reason to clear traces.

3. A research comparison measures how often exploration shortens effective trace length even when lambda is close to one.

Think of it this way

Think of following a route recommended by a planner. Evidence can be carried backward along the recommended route until a traveler chooses a different turn. The planner can still evaluate the decision immediately before that turn using its best estimate of available continuations, but it does not treat all subsequent experience as evidence from following the original recommendation.

Worked example

Consider an original three-transition episode with distinct visited state-action pairs X, Y and Z. Initially their Q values are 1, 2 and 3. Use alpha equal to 0.1, gamma equal to 0.9, lambda equal to 0.8 and accumulating traces.

Taking X gives reward 0. At the next state, the maximum action value is 4, but the behavior selects Y with value 2. The TD error for X is 0 plus 0.9 times 4 minus 1, or 2.6. Its trace is one, so Q(X) becomes 1.26. Because Y is nongreedy, clear the traces after this update.

Taking Y gives reward 1. The next selected action Z has value 3 and is greedy at its state. The TD error is 1 plus 0.9 times 3 minus 2, or 1.7. Y's trace becomes one and Q(Y) becomes 2.17. Decay the trace by 0.72, leaving e(Y) equal to 0.72.

Taking Z gives terminal reward 5. Its TD error is 5 minus 3, or 2. Increment e(Z) to one. The update adds 0.1 times 2 times 0.72, or 0.144, to Q(Y), producing 2.314. Q(Z) becomes 3.2. Q(X) remains 1.26 because its trace was cut earlier.

The example shows that the nongreedy transition does not erase the already performed one-step update to X. It stops later corrections from flowing through that older trace. It also shows that new traces can begin immediately after a cut; exploration does not disable learning for the rest of the episode.

Illustrative case study

In a fictional project, Pine Navigation compares trace-based controllers in a simulator. An implementation clears traces whenever its exploration branch is used, even if the sampled action ties for the maximum Q value.

The team changes the test to compare the selected action with the greedy set under the intended pre-update estimates. It then examines episodes with explicit ties and checks that older traces survive those selections but disappear after strictly nongreedy choices.

This fictional case illustrates implementation, not deployment or improved performance. Repeated-run evaluation remains necessary to compare controllers.

Common misconceptions and mistakes

Do not replace the maximum next-state value with the selected action value and still call the target Watkins Q(lambda). Do not clear traces before applying the current TD correction if following the convention described here. Do not assume every action chosen through random exploration is nongreedy.

Another mistake is describing all methods called Q(lambda) as identical. Trace cutting, importance corrections and true-online bookkeeping can define materially different algorithms.

Business use

The method is useful as an interpretable off-policy trace baseline in manageable sequential-decision models. Record exploration settings, tie handling and the proportion of updates that cut traces. If cuts are common, increasing lambda may do little to extend credit assignment. Compare actual return and learning variability rather than inferring effective horizon from lambda alone.

Check your understanding

Why does Q(X) stay at 1.26 after the terminal reward?

Answer: Its trace was cleared when Y was selected nongreedily.

How much does the final error add to Q(Y)?

Answer: 0.144.

Should an action tied for the maximum cause a cut?

Answer: No, it is a greedy action under the stated convention.

Related terms

Learn next

Study one-step Q-learning and SARSA first, then accumulating traces. Work through an episode with one nongreedy action and one tie. Compare more advanced off-policy trace methods only after the cutoff rule is clear.

Sources

Sutton and Barto, Reinforcement Learning: An Introduction, author draft, section 7.6: https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf.

Van Seijen and colleagues, True Online Temporal-Difference Learning, section 6.2, discusses the original trace-cutting rule and a separate true-online extension: https://www.jmlr.org/papers/volume17/15-599/15-599.pdf. The numerical episode and fictional case are original illustrations.

Previous: Watershed segmentation Next: Wavefront coding