Eligibility Traces

n-step bootstrapping already unified temporal-difference learning and Monte Carlo: one integer $n$ slides from a one-step bootstrap to the full return, and an intermediate $n$ usually beats both extremes. But the $n$ -step algorithm costs memory and lag: to form the target for time $t$ it must wait $n$ steps and keep the last $n$ feature vectors on hand. Eligibility traces produce nearly the same updates from a single short-term memory vector, updated online, with the memory of just one feature vector.¹

The mechanism is a vector $z_{t} \in R^{d}$ , the same shape as the weight vector $w_{t}$ . Where $w_{t}$ is a long-term memory accumulating over the life of the agent, $z_{t}$ is short-term, lasting less than one episode. When a component of $w$ helps produce an estimate, the matching component of $z$ is bumped up; then it fades. If a nonzero TD error arrives before the trace decays away, that component of $w$ is eligible for learning, by an amount proportional to its remaining trace. The trace-decay parameter $λ \in [0, 1]$ sets the fade rate; the same $λ$ reappears below to index the family of returns.

n-step methods versus eligibility traces. The n-step algorithm buffers the last

n

feature vectors and waits

n

steps before it can form a target; the trace collapses all of that history into one vector

z

updated every step, so it needs the memory of a single feature vector and no lag.

Two views of the same idea run through the whole lesson. The forward view is theoretical: to update a state, look ahead to all the future rewards and combine them. The backward view is mechanistic: at each step, propagate the current TD error back to the recently visited states, in proportion to their remaining traces. The forward view specifies the target; the backward view is how a real algorithm computes it, online and with bounded memory.

The λ-return

The $n$ -step return for a parameterized value function bootstraps after $n$ real rewards,

G_{t : t + n} ≐ R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} \overset{v}{^} (S_{t + n}, w_{t + n - 1}), 0 \leq t \leq T - n,

where $\overset{v}{^} (s, w)$ is the approximate value under weights $w$ . A valid update can aim at any one of these returns — but it can also aim at an average of several. Any weighted average of $n$ -step returns is a legitimate target, as long as the weights are nonnegative and sum to $1$ , because the average inherits the error-reduction property of its components. An update toward such an average is a compound update, and averaging over different $n$ opens a whole new range of algorithms.

A compound update averages several

n

-step returns. Each backup diagram (one, two, three steps deep) yields a target; a weighted average of them, with nonnegative weights summing to 1, is itself a valid target. The λ-return is the special compound update that averages all

n

with geometric weights.

The λ-return is one particular compound update: it averages every $n$ -step return, weighting the $n$ -step return by $λ^{n - 1}$ and normalizing by $1 - λ$ so the weights sum to $1$ ,

G_{t}^{λ} ≐ (1 - λ) n = 1 \sum \infty λ^{n - 1} G_{t : t + n} .

The one-step return gets the largest weight, $1 - λ$ ; the two-step return gets $(1 - λ) λ$ ; the three-step return $(1 - λ) λ^{2}$ ; and so on. Each additional step of lookahead is discounted by another factor of $λ$ . Because $\sum_{n = 1}^{\infty} (1 - λ) λ^{n - 1} = 1$ , the whole thing is a genuine weighted average.

Weighting in the λ-return. Each

n

-step return

G_{t : t + n}

receives weight

(1 - λ) λ^{n - 1}

, a geometric decay by a factor of

λ

per step; the areas sum to

1

. After termination at

T

all remaining weight,

λ^{T - t - 1}

, collapses onto the actual full return

G_{t}

The sum simplifies at termination. Once the episode ends at step $T$ , every $n$ -step return with $t + n \geq T$ equals the ordinary full return $G_{t}$ . Peeling those post-termination terms out of the infinite sum collapses their combined weight onto $G_{t}$ ,

G_{t}^{λ} = (1 - λ) n = 1 \sum T - t - 1 λ^{n - 1} G_{t : t + n} + λ^{T - t - 1} G_{t} .

This finite form makes the two boundary cases obvious. At $λ = 0$ the whole main sum vanishes except its first term, and $G_{t}^{λ} = G_{t : t + 1}$ — the one-step TD target. At $λ = 1$ the main sum goes to zero and the residual term takes over, $G_{t}^{λ} = G_{t}$ — the Monte Carlo return. The parameter $λ$ dials continuously between them, playing exactly the role that the integer $n$ played before, but averaging over all horizons at once rather than committing to a single one.

Worked example: a λ-return by hand

Take an undiscounted episode ( $γ = 1$ ) that terminates after three steps, with rewards $R_{1} = 2$ , $R_{2} = 0$ , $R_{3} = 1$ , and current value estimates $\overset{v}{^} (S_{1}) = 3$ , $\overset{v}{^} (S_{2}) = 4$ (with $\overset{v}{^}$ of the terminal state $0$ ). Compute the λ-return for $t = 0$ with $λ = 0.5$ .

First the $n$ -step returns from $t = 0$ . The one-step return bootstraps after $R_{1}$ : $G_{0 : 1} = R_{1} + \overset{v}{^} (S_{1}) = 2 + 3 = 5$ . The two-step return: $G_{0 : 2} = R_{1} + R_{2} + \overset{v}{^} (S_{2}) = 2 + 0 + 4 = 6$ . The three-step return reaches the terminal, so it is the full return: $G_{0 : 3} = R_{1} + R_{2} + R_{3} = 2 + 0 + 1 = 3$ , and every $n \geq 3$ return equals this same $G_{0} = 3$ .

Now use the finite post-termination form with $T = 3$ , $t = 0$ , $λ = 0.5$ :

G_{0}^{λ} = (1 - λ) [λ^{0} G_{0 : 1} + λ^{1} G_{0 : 2}] + λ^{2} G_{0} = 0.5 [1 \cdot 5 + 0.5 \cdot 6] + 0.25 \cdot 3.

That is $0.5 (5 + 3) + 0.75 = 0.5 \cdot 8 + 0.75 = 4 + 0.75 = 4.75$ . Check the weights sum to one: $(1 - λ) λ^{0} = 0.5$ on the one-step return, $(1 - λ) λ^{1} = 0.25$ on the two-step, and the residual $λ^{2} = 0.25$ on the full return, total $1.0$ . The λ-return $4.75$ sits between the aggressive one-step target $5$ and the full return $3$ , leaning toward the shorter horizons because $λ = 0.5$ decays quickly. Set $λ = 0$ and the same formula collapses to $G_{0}^{λ} = G_{0 : 1} = 5$ ; set $λ = 1$ and it collapses to $G_{0}^{λ} = G_{0} = 3$ — the two extremes drop out of the one expression.

The offline λ-return algorithm uses this target directly. It changes nothing during the episode; then, once $G_{t}^{λ}$ is known for every $t$ , it makes the usual semi-gradient updates,

w_{t + 1} ≐ w_{t} + α [G_{t}^{λ} - \overset{v}{^} (S_{t}, w_{t})] \nabla \overset{v}{^} (S_{t}, w_{t}), t = 0, \dots, T - 1.

On the 19-state random walk this offline algorithm performs about as well as the best $n$ -step method, and slightly better at the best settings — an intermediate $λ$ beats both $λ = 0$ and $λ = 1$ , just as an intermediate $n$ beat both its extremes.

The forward view

The offline λ-return algorithm is the theoretical, or forward, view of a learning method. For each state visited, we look forward in time to all the future rewards and decide how to combine them into a single target. From each state in the sequence, we look forward once to determine its update, then move on and never touch that state again. Future states, by contrast, are processed repeatedly, once from every vantage point that precedes them.

The forward view. Standing at

S_{t}

, the algorithm looks ahead along the trajectory to the future rewards

R_{t + 1}, R_{t + 2}, \dots

and states

S_{t + 1}, S_{t + 2}, \dots

, combining them into the target

G_{t}^{λ}

. Each state is updated once from its own forward look; every later state is viewed again from each earlier vantage point.

Forward views are always somewhat awkward to implement, because the update at $S_{t}$ depends on rewards and states that do not exist yet at time $t$ . You can compute $G_{t}^{λ}$ only after the episode ends. That is the practical defect the backward view repairs: it produces nearly the same updates — and, for true online TD(λ), exactly the same updates — using only quantities available at the current step.

TD(λ) and the backward view

TD(λ) is the backward-view counterpart. It improves on the offline algorithm in three ways at once. It updates $w$ on every step rather than only at the end, so estimates get better sooner; its computation is spread evenly across time rather than piled up at termination; and it applies to continuing problems, not just episodic ones.

TD(λ) maintains the trace vector. Initialize it to zero at the start of the episode, increment it each step by the value gradient, and fade the old value by $γ λ$ ,

z_{- 1} ≐ 0, z_{t} ≐ γ λ z_{t - 1} + \nabla \overset{v}{^} (S_{t}, w_{t}), 0 \leq t \leq T .

The trace keeps a running record of which components of $w$ have contributed to recent state valuations, where recent means measured against the $γ λ$ decay. In the linear case $\nabla \overset{v}{^} (S_{t}, w_{t})$ is just the feature vector $x_{t}$ , so the trace is a sum of past, fading, input vectors — a moving snapshot of the features the agent has lately depended on.

The reinforcing event that drives learning is the moment-by-moment one-step TD error,

δ_{t} ≐ R_{t + 1} + γ \overset{v}{^} (S_{t + 1}, w_{t}) - \overset{v}{^} (S_{t}, w_{t}),

and the weight vector moves proportional to the scalar error times the whole trace vector,

w_{t + 1} ≐ w_{t} + α δ_{t} z_{t} .

The single scalar $δ_{t}$ is broadcast back across every component with a nonzero trace. A component with a large remaining trace (one that helped value a recently visited state) moves a lot; a component whose trace has mostly decayed barely moves at all. This is the backward view in one equation: a present error, credited to the past in proportion to how recently each state contributed.

The backward, or mechanistic, view of TD(λ). At

S_{t + 1}

the current TD error

δ_{t}

is fed back along the trajectory to recently visited states, each carrying a trace

z

that has faded by

γ λ

per step. Nearer states hold a larger trace and are credited more; distant states, whose traces have decayed, are barely touched.

The trace update explains both limits directly. At $λ = 0$ the trace at $t$ reduces to the current gradient $\nabla \overset{v}{^} (S_{t}, w_{t})$ , because the $γ λ$ factor kills everything older. The update then changes only the one state just visited, and TD(λ) collapses to the one-step semi-gradient TD(0) of the previous chapter. This is why the one-step method is written TD(0): it is TD(λ) with the trace switched off. For $0 < λ < 1$ more of the preceding states are changed, but each more distant one gets less credit, because its trace is smaller — earlier states are given less credit for the TD error.

At $λ = 1$ the credit given to earlier states falls only by $γ$ per step — Monte Carlo behavior. A reward $R_{t + 1}$ carried back $k$ steps needs discounting by $γ^{k}$ , and a trace decaying by $γ$ per step supplies that $γ^{k}$ . With $λ = 1$ (and, for an undiscounted episodic task, $γ = 1$ ) the trace never decays with time and the method behaves as Monte Carlo does — but incrementally and online, so it can even run on continuing tasks where classical Monte Carlo cannot. This case is also called TD(1), and unlike offline Monte Carlo it can learn from and alter its own behavior during an episode rather than only after it ends.

Algorithm:

\textsc{Semi-Gradient-TD}(\lambda)

— estimate

\hat v \approx v_\pi

1
input: a policy $\pi$ , a differentiable $\hat v$ with $\hat v(\text{terminal},\cdot) = 0$
2
$\mathbf{w} \gets$ arbitrary (e.g. $\mathbf{0}$ )
3
for each episode do
4
initialize $S$
5
$\mathbf{z} \gets \mathbf{0}$
6
repeat
7
choose $A \sim \pi(\cdot \mid S)$ , take it, observe $R$ , $S'$
8
$\mathbf{z} \gets \gamma\lambda\,\mathbf{z} + \nabla\hat v(S,\mathbf{w})$
9
$\delta \gets R + \gamma\,\hat v(S',\mathbf{w}) - \hat v(S,\mathbf{w})$
10
$\mathbf{w} \gets \mathbf{w} + \alpha\,\delta\,\mathbf{z}$
11
$S \gets S'$
12
until $S$ is terminal

On the random walk, TD(λ) closely tracks the offline λ-return algorithm when $α$ is chosen well for each. At larger-than-optimal step sizes TD(λ) degrades more, and can even become unstable, but those settings are not ones you would use anyway. In the on-policy linear case, TD(λ) is proven to converge, to a weight vector whose asymptotic error is bounded by $\frac{1 - γ λ}{1 - γ}$ times the smallest achievable error — a bound that tightens toward the minimum as $λ \to 1$ .

The bias-variance tradeoff in

λ

. Small

λ

leans on the bootstrap: low variance but biased by the current (wrong) value estimates. Large

λ

leans on real returns: unbiased but high variance. Prediction error, the sum of the two, is lowest at an intermediate

λ

, which is why an in-between value usually wins.

Worked example: a trace over three steps

Take a single scalar feature that is $1$ at every visited state (so $\nabla \overset{v}{^} = 1$ each step), $γ = 1$ , $λ = 0.8$ . Start $z_{- 1} = 0$ . Step $0$ : $z_{0} = γ λ \cdot 0 + 1 = 1$ . Step $1$ : $z_{1} = 0.8 \cdot 1 + 1 = 1.8$ . Step $2$ : $z_{2} = 0.8 \cdot 1.8 + 1 = 2.44$ . Step $3$ : $z_{3} = 0.8 \cdot 2.44 + 1 = 2.95$ . The trace grows because the same feature keeps firing, but each past contribution is discounted: the increment from step $0$ has faded to $0. 8^{3} = 0.512$ by step $3$ , the step- $1$ increment to $0. 8^{2} = 0.64$ , and so on. When a TD error $δ_{3} = - 0.5$ arrives, the weight moves by $α δ_{3} z_{3} = α (- 0.5) (2.95)$ — the whole trajectory's accumulated eligibility scaled by one scalar error. A component whose feature last fired three steps ago still contributes, but only through the surviving $0.512$ fraction of its original bump.

Accumulating, replacing, and dutch traces

The trace above is the accumulating trace, $z_{t} = γ λ z_{t - 1} + x_{t}$ , which keeps adding the feature each visit and so can grow past $1$ for a feature that fires repeatedly. That unbounded growth is sometimes a problem: a state revisited many times in quick succession piles up trace and can overshoot. The older fix, defined only for binary features, is the replacing trace — instead of adding, reset each active component to $1$ :²

z_{i, t} ≐ {1 γ λ z_{i, t - 1} if x_{i, t} = 1, otherwise.

A replacing trace caps every component at $1$ , so a repeatedly visited feature no longer accumulates without bound. The dutch trace used in true online TD(λ) below,

z_{t} = γ λ z_{t - 1} + (1 - α γ λ z_{t - 1}^{⊤} x_{t}) x_{t},

interpolates between the two: it adds the feature but scaled down by a term depending on the step size and the surviving trace — exactly the correction that makes the backward view match the forward view identically (the true online TD(λ) below). Modern practice treats the replacing trace as a crude approximation to the dutch trace, which usually performs better; accumulating traces stay relevant mainly for nonlinear approximation, where the dutch trace has no derivation.

The three trace types for one binary feature that fires at steps 0, 1, 2 then stops (decay

γ λ

). The accumulating trace (blue) adds 1 each visit and climbs above 1; the replacing trace (red) resets to 1 on each visit and never exceeds it; the dutch trace (black) sits between them. All decay identically once the feature stops firing.

Forward and backward, side by side

The forward and backward views are two descriptions of the same computation: what the update is for (aim each state at its λ-return) versus how it happens (spread each incoming TD error back across the states the trace remembers). Neither is more correct; the whole chapter is the claim that they nearly coincide.

	Forward view	Backward view
Character	theoretical, conceptual	mechanistic, algorithmic
Target	the λ-return $G_{t}^{λ}$	the current TD error $δ_{t}$
Direction	looks ahead to future rewards	credits past states
State of memory	needs the whole future	one trace vector $z_{t}$
Timing	update computable only at episode end	update on every step, online

For the plain TD(λ) above, the equivalence is only approximate: its total updates over an episode approximate, but do not equal, the offline λ-return algorithm's, and the gap grows as $α$ grows. Exact equivalence, and the extension of the trace apparatus to control, continues in true online TD(λ) and Sarsa(λ).

Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), Ch. 12 — Eligibility Traces: the trace vector $z_{t}$ as a short-term memory paralleling $w_{t}$ (chapter intro). §12.1 — The λ-return: the compound average (12.2), its finite post-termination form (12.3), the weighting figure (Fig. 12.2), and the offline λ-return update (12.4). §12.2 — TD(λ): the accumulating trace (12.5), the TD error (12.6), the weight update (12.7), and the forward/backward views (Figs. 12.4–12.5). ↩
Sutton & Barto, §12.5 — the accumulating trace (12.5) versus the replacing trace (12.12, binary-feature only) versus the dutch trace (12.11), and the modern view of replacing traces as crude approximations to dutch traces, with accumulating traces retained for nonlinear approximation. ↩