Eligibility Trace

When a reward arrives late, the hard question is not just “was this good?” but “which earlier decisions helped cause it?” An eligibility trace is a short-lived memory that keeps recently visited states—or state-action pairs—ready to receive credit when new information arrives.

How the trace works
In ordinary TD(0), the value estimate for the current state is updated using a one-step prediction error, called the TD error. Eligibility traces spread that same error backward across recent experience. Each visited state has a trace value e: visiting it raises its eligibility; at every later step, the trace fades by a factor of γλ, where γ discounts future reward and λ controls how far credit reaches.

λ = 0 gives TD(0): only the current state is updated.
λ near 1 gives much more credit to earlier states, resembling an update based on a long return.
In accumulating traces, repeat visits add to a trace; in replacing traces, a visited state’s trace is reset to 1.

Why this is useful
Imagine an agent navigating a maze and receiving reward only at the exit. Once it reaches the goal, a trace lets the success signal strengthen not only the final move, but also the corridor choices leading to it. This is the online, “backward-view” implementation of TD(λ): rather than waiting to compute every possible multi-step return, the agent updates eligible earlier states immediately when each TD error appears. SARSA(λ) applies the same idea to action values, so recently chosen actions receive credit or blame.

The trade-off
Eligibility traces make learning faster when rewards are delayed because useful information travels farther per interaction. But a large λ also spreads a noisy or misleading TD error across more past decisions. In tabular problems this mechanism is clean and effective; with neural value functions, overlapping updates and bootstrapping can amplify instability, so modern methods such as PPO usually use other forms of multi-step advantage estimation. The central idea remains the same: preserve a fading record of the past so delayed feedback can teach the decisions that made it possible.

An eligibility trace is a temporary, decaying record of how recently and how strongly each state or state–action pair was visited. When a temporal-difference error occurs, it updates all traced entries in proportion to their eligibility, assigning credit backward through recent experience. Eligibility traces connect one-step TD updates with multi-step returns, speeding reward propagation and improving learning when rewards are delayed.

Imagine learning a new route home. If you arrive quickly, you do not just praise the final turn—you also give some credit to the turns you made a few moments earlier. But the farther back a turn was, the less clearly it deserves credit.

An eligibility trace is an AI learner’s short-lived memory of recent choices. When a reward or disappointment appears, it lets the learner spread that feedback backward across those recent choices, giving strongest credit or blame to the newest ones and less to older ones. This matters because many actions have consequences only later, such as moves in a game that set up a win several turns afterward.