Does the trace store learned knowledge permanently?

No; the value parameters retain the learning.

Does a nonzero trace always cause a change?

No; the learning error may be zero.

Can traces update earlier states immediately?

Yes, while their relevant components remain active.

AI Glossary / Reinforcement learning and robotics / Advanced

Eligibility trace

Definition

An eligibility trace is a temporary memory used by a learning algorithm to determine which recently active states, actions or features should be updated when a new learning signal arrives. In temporal-difference learning, it allows a current prediction error to influence earlier parts of an experience sequence. The exact trace rule depends on the algorithm and representation.

What it means

A delayed outcome may be relevant to several earlier predictions, not just the most recent one. A trace carries a fading record of those earlier contributions so that the learner can update them without storing and replaying the entire history at every step.
The trace is distinct from the learned value itself. In a parameterized predictor, the weights hold the accumulated learning, while the trace temporarily determines where a new update is directed.

How it works

For an accumulating trace in linear state-value prediction, let x_t be the current feature vector. Starting with z = 0 at the beginning of an episode, update z <- gamma lambda z + x_t. Here gamma is the reward discount factor and lambda controls trace decay.
Compute the temporal-difference error delta = reward + gamma V(next_state) - V(current_state), using zero future value at an actual terminal state. Update the parameter vector by w <- w + alpha delta z. Thus, the scalar error is distributed across the components represented in the current trace.
In tabular prediction, each state has its own component and its current indicator is added to the trace. Replacing traces and Dutch traces use different recurrences; the accumulating formula is one important example, not the definition of every trace method.

Three practical examples

Delayed feedback: a simulated task provides a reward several steps after an earlier state was visited, and traces allow the resulting error to update that state's estimate immediately.
Shared features: a linear predictor adjusts features that contributed to recent predictions, even when the exact state has changed.
Learning diagnostics: a researcher compares trace settings to see how quickly an error spreads backward and how that affects the stability and accuracy of learning.

Think of it this way

Imagine leaving fading marks beside recently used information. A new prediction error adjusts entries according to the marks still present. A stronger mark means a larger contribution to that update, but it does not certify that the marked information is responsible for the outcome in a causal sense.

Worked example

Consider an original episode visiting three distinct states, A, B and C, followed by termination. Rewards on the three transitions are 0, 0 and 5. Use tabular accumulating traces, initialize every value and trace to zero, and set alpha = 0.2, gamma = 0.9 and lambda = 0.8. The decay factor gamma lambda is 0.72.
On the transition from A to B, the trace becomes (1,0,0), listed in A, B, C order. Both relevant values are zero, so the TD error is 0 + 0.9 times 0 - 0 = 0. No value changes.
On the transition from B to C, the trace becomes (0.72,1,0). The TD error is again zero, and values remain unchanged.
On the transition from C to termination, the trace becomes (0.5184,0.72,1). The TD error is 5 because the terminal future value and current estimate of C are both zero. Multiplying the trace by alpha times delta, which is 0.2 times 5 = 1, gives the value increments directly: A increases by 0.5184, B by 0.72 and C by 1.
All three values change during the final update, although only C was the current state. At the start of a new episode, the episodic trace is reset; the learned values are retained.
If lambda were zero, only the current state's trace would remain active. The final update would raise C to 1 while leaving A and B at zero on this first episode. If lambda were one, the final trace would instead be (0.81,0.9,1), producing increments 0.81, 0.9 and 1 under the same initial conditions.
The exact discounted returns on this deterministic episode are 4.05 from A, 4.5 from B and 5 from C. The first estimates differ from those returns. The trace controls how an error is allocated; it does not make learning instantaneous or remove the effect of the step size.
Because this example has distinct states, zero starting values and no earlier nonzero errors, its arithmetic is particularly simple. Repeated visits and values that change during an episode require following every intermediate trace and prediction update. Broad claims of exact forward-view equivalence need the appropriate algorithm and assumptions.

Illustrative case study

Fictional company Maple Simulation tests a predictor for a task with delayed rewards. Its team records traces, TD errors and value changes separately on short episodes. It checks that the final reward can affect earlier estimates and that episode resets clear traces without erasing learned values.
The analysts then compare several lambda settings under the same training conditions. They report prediction error and variability rather than treating a longer trace as automatically better. This fictional workflow reports no measured performance result.

Common misconceptions and mistakes

A trace is not the reward itself. The update also depends on the TD error and step size. A large trace can produce no update when the error is zero, and a negative error can reduce an estimate.
Another mistake is assuming that traces always lie between zero and one. Accumulating traces can grow with repeated activation, and feature-based traces reflect the representation's values. Trace decay also involves gamma as well as lambda in the displayed recurrence. Finally, longer-lasting traces can change the trade-off between learning speed, variability and approximation effects; they are not universally superior.

Business use

Eligibility traces help explain how an incremental learner handles delayed feedback. Evaluation should document the trace variant, representation, step size and reset rules. The mechanism supports credit assignment in a learning algorithm, but its updates should not be presented as causal explanations of business outcomes.

Check your understanding

Why did A change on the final transition?

Answer: Its trace was still 0.5184.

Why did the first two transitions change no values?

Answer: Their TD errors were zero.

What is reset between episodes here?

Answer: The trace, not the learned value table.

Related terms

TD(lambda)
Temporal-difference error
Lambda return
Accumulating trace
Replacing trace
Dutch trace
Credit assignment

Learn next

Insert a repeated visit into the example and recompute each accumulating trace before comparing it with a replacing trace.

Sources

Sutton and Barto, Reinforcement Learning: An Introduction, second edition, Sections 12.1–12.2: https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf . The three-state episode and company scenario are original illustrations.

Previous: Elias omega coding Next: Elitism