---
title: Eligibility Traces
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 7
order: 307
summary: >
  n-step methods unify TD and Monte Carlo by storing the last n feature vectors;
  eligibility traces do the same job with a single short-term memory vector.
  The λ-return averages every n-step return under a geometric weighting; the
  forward view looks ahead to that average, and the backward view produces
  nearly the same updates online through a decaying trace vector. We build the
  λ-return, TD(λ) with its trace, the two ways λ recovers TD(0) and Monte Carlo,
  a note on the exact equivalence of true online TD(λ), and Sarsa(λ) for control.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 12 — Eligibility Traces; §12.1 The λ-return; §12.2 TD(λ)"
  - book: Sutton & Barto
    ref: "§12.5 True Online TD(λ); §12.6 Dutch Traces; §12.7 Sarsa(λ)"
---

[n-step bootstrapping](/reinforcement-learning/tabular-methods/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.[^sb-intro]

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

$$
% caption: 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 $\mathbf{z}$ updated every
% step, so it needs the memory of a single feature vector and no lag.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  slot/.style={draw, minimum width=7mm, minimum height=6mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % n-step: buffer of n vectors
  \node[anchor=east, font=\scriptsize] at (-0.2,0.3) {n-step:};
  \foreach \i/\x in {1/0.1, 2/0.9, 3/1.7, 4/2.5} {
    \node[slot] at (\x,0.3) {x};
  }
  \node[anchor=west, font=\scriptsize] at (3.35,0.3) {buf\/fer of n vectors, wait n steps};
  % trace: one vector
  \node[anchor=east, font=\scriptsize] at (-0.2,-0.9) {traces:};
  \node[slot, draw=acc, text=acc] at (0.1,-0.9) {z};
  \node[acc, anchor=west, font=\scriptsize] at (0.9,-0.9) {one vector, updated every step};
\end{tikzpicture}
$$

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} \;\doteq\; R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^{n}\, \hat v(S_{t+n}, \mathbf{w}_{t+n-1}),
\qquad 0 \le t \le T-n,
$$

where $\hat v(s, \mathbf{w})$ is the approximate value under weights
$\mathbf{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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  nd/.style={circle, draw, fill=black, minimum size=2.2mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % one-step backup
  \begin{scope}
    \node[nd] (a0) at (0,1.6) {};
    \node[nd] (a1) at (0,0.9) {};
    \draw[black] (a0) -- (a1);
    \node[anchor=north, font=\scriptsize] at (0,0.75) {1-step};
    \node[acc, anchor=south, font=\scriptsize] at (0,1.75) {w1};
  \end{scope}
  % two-step
  \begin{scope}[xshift=1.6cm]
    \node[nd] (b0) at (0,1.6) {};
    \node[nd] (b1) at (0,1.0) {};
    \node[nd] (b2) at (0,0.4) {};
    \draw[black] (b0) -- (b1) -- (b2);
    \node[anchor=north, font=\scriptsize] at (0,0.25) {2-step};
    \node[acc, anchor=south, font=\scriptsize] at (0,1.75) {w2};
  \end{scope}
  % three-step
  \begin{scope}[xshift=3.2cm]
    \node[nd] (c0) at (0,1.6) {};
    \node[nd] (c1) at (0,1.1) {};
    \node[nd] (c2) at (0,0.6) {};
    \node[nd] (c3) at (0,0.1) {};
    \draw[black] (c0) -- (c1) -- (c2) -- (c3);
    \node[anchor=north, font=\scriptsize] at (0,-0.05) {3-step};
    \node[acc, anchor=south, font=\scriptsize] at (0,1.75) {w3};
  \end{scope}
  \node[font=\small] at (0.8,0.95) {+};
  \node[font=\small] at (2.4,0.95) {+};
  \draw[->, acc, thick] (4.2,0.9) -- (5.2,0.9);
  \node[acc, anchor=west, font=\scriptsize] at (5.25,0.9) {compound target};
  \node[anchor=north, font=\scriptsize] at (6.4,0.6) {(weights sum to 1)};
\end{tikzpicture}
$$

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

$$
G_t^\lambda \;\doteq\; (1-\lambda) \sum_{n=1}^{\infty} \lambda^{\,n-1}\, G_{t:t+n}.
$$

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

$$
% caption: Weighting in the λ-return. Each $n$-step return $G_{t:t+n}$ receives
% weight $(1-\lambda)\lambda^{n-1}$, a geometric decay by a factor of $\lambda$
% per step; the areas sum to $1$. After termination at $T$ all remaining weight,
% $\lambda^{T-t-1}$, collapses onto the actual full return $G_t$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (8.2,0);
  \node[anchor=north, font=\scriptsize] at (4.0,-0.15) {Time};
  \draw[->, black] (0,0) -- (0,3.4);
  \node[align=center, font=\scriptsize, anchor=east] at (-0.15,2.4) {Weighting};
  % decay curve  y = 2.9 * lambda^x  with lambda chosen for a nice fall
  \draw[acc, very thick, domain=0:7.0, samples=80, smooth]
    plot (\x, {2.9*exp(-0.42*\x)});
  % initial-weight bracket 1 - lambda
  \draw[black] (-0.05,2.9) -- (0.0,2.9);
  \node[anchor=east, font=\scriptsize] at (-0.05,2.9) {1-lambda};
  % highlighted 3-step bar
  \fill[acc!18] (2.0,0) rectangle (2.5,{2.9*exp(-0.42*2.25)});
  \draw[acc] (2.0,0) rectangle (2.5,{2.9*exp(-0.42*2.25)});
  \node[align=center, font=\scriptsize, anchor=south] at (2.25,2.15)
    {weight on the\\3-step return};
  \draw[black, ->] (2.25,2.1) -- (2.25,{2.9*exp(-0.42*2.25)+0.05});
  % decay label riding the curve
  \node[acc, anchor=south west, font=\scriptsize] at (3.3,{2.9*exp(-0.42*3.6)+0.05})
    {decay by lambda};
  % terminal marker T and the residual weight
  \draw[black, dashed] (6.2,0) -- (6.2,{2.9*exp(-0.42*6.2)});
  \node[anchor=north, font=\scriptsize] at (6.2,-0.02) {T};
  \fill[red!16] (6.2,0) rectangle (7.0,{2.9*exp(-0.42*6.6)});
  \draw[red] (6.2,0) rectangle (7.0,{2.9*exp(-0.42*6.6)});
  \node[red, align=center, font=\scriptsize, anchor=west] at (7.05,0.85)
    {residual weight on\\the f\/inal return};
\end{tikzpicture}
$$

The sum simplifies at termination. Once the episode ends at step $T$, every
$n$-step return with $t+n \ge 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^\lambda \;=\; (1-\lambda)\sum_{n=1}^{T-t-1} \lambda^{\,n-1}\, G_{t:t+n} \;+\; \lambda^{\,T-t-1}\, G_t.
$$

This finite form makes the two boundary cases obvious. At $\lambda = 0$ the whole
main sum vanishes except its first term, and $G_t^\lambda = G_{t:t+1}$ — the
one-step TD target. At $\lambda = 1$ the main sum goes to zero and the residual
term takes over, $G_t^\lambda = G_t$ — the Monte Carlo return. The parameter
$\lambda$ 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.

> **Definition (λ-return).** The λ-return $G_t^\lambda = (1-\lambda)\sum_{n\ge 1}
> \lambda^{n-1} G_{t:t+n}$ is the geometrically weighted average of every
> $n$-step return, with the $n$-step return receiving weight
> $(1-\lambda)\lambda^{n-1}$. At $\lambda=0$ it is the one-step TD target
> $G_{t:t+1}$; at $\lambda=1$ it is the full Monte Carlo return $G_t$. The
> half-life of the weighting, not $n$, now controls how far the target looks
> ahead.

### Worked example: a λ-return by hand

Take an undiscounted episode ($\gamma = 1$) that terminates after
three steps, with rewards $R_1 = 2$, $R_2 = 0$, $R_3 = 1$, and current value estimates
$\hat v(S_1) = 3$, $\hat v(S_2) = 4$ (with $\hat v$ of the terminal state $0$). Compute
the λ-return for $t = 0$ with $\lambda = 0.5$.

First the $n$-step returns from $t = 0$. The one-step return bootstraps after $R_1$:
$G_{0:1} = R_1 + \hat v(S_1) = 2 + 3 = 5$. The two-step return: $G_{0:2} = R_1 + R_2 +
\hat 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 \ge 3$ return
equals this same $G_0 = 3$.

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

$$
G_0^\lambda = (1-\lambda)\big[\lambda^0 G_{0:1} + \lambda^1 G_{0:2}\big] + \lambda^{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-\lambda)\lambda^0 = 0.5$ on the one-step return, $(1-\lambda)\lambda^1
= 0.25$ on the two-step, and the residual $\lambda^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 $\lambda = 0.5$ decays quickly.
Set $\lambda = 0$ and the same formula collapses to $G_0^\lambda = G_{0:1} = 5$; set
$\lambda = 1$ and it collapses to $G_0^\lambda = 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^\lambda$ is known for every $t$, it
makes the usual semi-gradient updates,

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha \big[\, G_t^\lambda - \hat v(S_t, \mathbf{w}_t) \,\big]\, \nabla \hat v(S_t, \mathbf{w}_t),
\qquad t = 0, \ldots, 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
$\lambda$ beats both $\lambda=0$ and $\lambda=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.

$$
% caption: The forward view. Standing at $S_t$, the algorithm looks ahead along
% the trajectory to the future rewards $R_{t+1}, R_{t+2}, \ldots$ and states
% $S_{t+1}, S_{t+2}, \ldots$, combining them into the target $G_t^\lambda$. Each
% state is updated once from its own forward look; every later state is viewed
% again from each earlier vantage point.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % baseline of time
  \draw[->, black] (-0.3,0) -- (9.7,0);
  \node[anchor=north west, font=\scriptsize] at (7.3,-0.1) {Time};
  % the current state, larger, at the left
  \node[st, minimum size=11mm, draw=acc, text=acc, thick] (s0) at (0.2,0.55) {St};
  % subsequent states
  \node[st] (s1) at (2.6,0.35) {St+1};
  \node[st] (s2) at (5.0,0.35) {St+2};
  \node[st] (s3) at (7.3,0.35) {St+3};
  % terminal
  \node[rectangle, draw, fill=black!25, minimum size=6mm] (sT) at (9.4,0.35) {};
  \node[anchor=south, font=\scriptsize] at (9.4,0.75) {RT};
  % reward labels between states
  \node[anchor=south, font=\scriptsize] at (1.4,0.55) {Rt+1};
  \node[anchor=south, font=\scriptsize] at (3.8,0.5) {Rt+2};
  \node[anchor=south, font=\scriptsize] at (6.15,0.5) {Rt+3};
  % the forward looks: curved arrows from S_t reaching ahead
  \draw[acc, ->, thick] (s0) to[bend left=32] (s1);
  \draw[acc, ->, thick] (s0) to[bend left=40] (s2);
  \draw[acc, ->, thick] (s0) to[bend left=46] (s3);
  \draw[acc, ->, thick, dashed] (s0) to[bend left=50] (8.6,1.0);
  % dots toward terminal
  \foreach \dx in {0,0.22,0.44} \fill[black] (8.15+\dx,0.35) circle (0.9pt);
\end{tikzpicture}
$$

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^\lambda$ 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 $\mathbf{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
$\gamma\lambda$,

$$
\mathbf{z}_{-1} \doteq \mathbf{0},
\qquad
\mathbf{z}_t \;\doteq\; \gamma\lambda\, \mathbf{z}_{t-1} + \nabla \hat v(S_t, \mathbf{w}_t),
\qquad 0 \le t \le T.
$$

The trace keeps a running record of which components of $\mathbf{w}$ have
contributed to recent state valuations, where "recent" means measured against
the $\gamma\lambda$ decay. In the linear case $\nabla \hat v(S_t, \mathbf{w}_t)$
is just the feature vector $\mathbf{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,

$$
\delta_t \;\doteq\; R_{t+1} + \gamma\, \hat v(S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t),
$$

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

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\, \delta_t\, \mathbf{z}_t.
$$

The single scalar $\delta_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.

$$
% caption: The backward, or mechanistic, view of TD(λ). At $S_{t+1}$ the current
% TD error $\delta_t$ is fed back along the trajectory to recently visited
% states, each carrying a trace $\mathbf{z}$ that has faded by $\gamma\lambda$
% per step. Nearer states hold a larger trace and are credited more; distant
% states, whose traces have decayed, are barely touched.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % time baseline
  \draw[->, black] (-1.0,0) -- (9.4,0);
  \node[anchor=north east, font=\scriptsize] at (9.4,-0.05) {Time};
  % ellipsis on far left (older states)
  \foreach \dx in {0,0.22,0.44} \fill[black] (-0.9+\dx,0.35) circle (0.9pt);
  % visited states with fading trace magnitude (label z)
  \node[st, minimum size=5mm] (s3) at (0.6,0.35) {St-3};
  \node[st, minimum size=6mm] (s2) at (2.6,0.35) {St-2};
  \node[st, minimum size=7mm] (s1) at (4.7,0.35) {St-1};
  \node[st, minimum size=8.5mm] (s0) at (7.0,0.35) {St};
  % trace labels above each
  \node[anchor=south, font=\scriptsize] at (0.6,0.75) {z small};
  \node[anchor=south, font=\scriptsize] at (2.6,0.85) {z};
  \node[anchor=south, font=\scriptsize] at (4.7,0.9) {z};
  \node[anchor=south, font=\scriptsize] at (7.0,1.05) {z large};
  % the current update point S_{t+1} to the right, delta emitter
  \node[st, minimum size=9mm, draw=red, text=red, thick] (sn) at (9.0,0.35) {St+1};
  % delta error radiating backward
  \node[red, font=\small] at (7.7,1.6) {delta-t};
  \draw[red, ->, thick] (sn) to[bend left=20] (s0);
  \draw[red, ->, thick] (sn) to[bend left=28] (s1);
  \draw[red, ->, thick] (sn) to[bend left=34] (s2);
  \draw[red, ->, thick, dashed] (sn) to[bend left=38] (s3);
\end{tikzpicture}
$$

The trace update explains both limits directly. At $\lambda = 0$ the trace at
$t$ reduces to the current gradient $\nabla \hat v(S_t, \mathbf{w}_t)$, because
the $\gamma\lambda$ 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 < \lambda < 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 $\lambda = 1$ the credit given to earlier states falls only by $\gamma$ per
step — Monte Carlo behavior. A reward $R_{t+1}$
carried back $k$ steps needs discounting by $\gamma^k$, and a trace decaying by
$\gamma$ per step supplies that $\gamma^k$. With $\lambda=1$ (and, for
an undiscounted episodic task, $\gamma=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
caption: $\textsc{Semi-Gradient-TD}(\lambda)$ — estimate $\hat v \approx v_\pi$
input: a policy $\pi$, a differentiable $\hat v$ with $\hat v(\text{terminal},\cdot) = 0$
$\mathbf{w} \gets$ arbitrary (e.g. $\mathbf{0}$)
for each episode do
  initialize $S$
  $\mathbf{z} \gets \mathbf{0}$
  repeat
    choose $A \sim \pi(\cdot \mid S)$, take it, observe $R$, $S'$
    $\mathbf{z} \gets \gamma\lambda\,\mathbf{z} + \nabla\hat v(S,\mathbf{w})$
    $\delta \gets R + \gamma\,\hat v(S',\mathbf{w}) - \hat v(S,\mathbf{w})$
    $\mathbf{w} \gets \mathbf{w} + \alpha\,\delta\,\mathbf{z}$
    $S \gets S'$
  until $S$ is terminal
```

On the random walk, TD(λ) closely tracks the offline λ-return algorithm when
$\alpha$ 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-\gamma\lambda}{1-\gamma}$
times the smallest achievable error — a bound that tightens toward the minimum as
$\lambda \to 1$.

$$
% caption: The bias-variance tradeoff in $\lambda$. Small $\lambda$ leans on the
% bootstrap: low variance but biased by the current (wrong) value estimates. Large
% $\lambda$ leans on real returns: unbiased but high variance. Prediction error, the
% sum of the two, is lowest at an intermediate $\lambda$, which is why an in-between
% value usually wins.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.6,0);
  \node[anchor=north, font=\scriptsize] at (5.2,-0.15) {lambda};
  \foreach \x/\lab in {0.2/0, 6.0/1} \node[anchor=north, font=\scriptsize] at (\x,-0.05) {\lab};
  \draw[->, black] (0,0) -- (0,3.4);
  \node[anchor=east, font=\scriptsize] at (-0.1,2.9) {error};
  % bias: high at small lambda, drops toward 0 at lambda=1
  \draw[red, thick] plot[domain=0.2:6.0, samples=40] (\x, {2.3*exp(-0.55*(\x-0.2))});
  \node[red, anchor=south west, font=\scriptsize] at (0.3,2.35) {bias (bootstrap)};
  % variance: low at small lambda, rises toward lambda=1
  \draw[acc, thick] plot[domain=0.2:6.0, samples=40] (\x, {0.15*exp(0.45*(\x-0.2))});
  \node[acc, anchor=east, font=\scriptsize] at (5.9,2.55) {variance};
  % total: U-shape, min in middle
  \draw[black, thick] plot[domain=0.2:6.0, samples=50] (\x, {2.3*exp(-0.55*(\x-0.2)) + 0.15*exp(0.45*(\x-0.2)) + 0.2});
  \node[anchor=south east, font=\scriptsize] at (5.9,2.95) {total};
  \fill[black] (2.65,1.05) circle (1.8pt);
  \draw[black, dashed] (2.65,0) -- (2.65,1.05);
  \node[anchor=north, font=\scriptsize] at (2.65,-0.05) {best};
\end{tikzpicture}
$$

### Worked example: a trace over three steps

Take a single scalar feature that is $1$ at every
visited state (so $\nabla\hat v = 1$ each step), $\gamma = 1$, $\lambda = 0.8$. Start
$\mathbf{z}_{-1} = 0$. Step $0$: $z_0 = \gamma\lambda \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 $\delta_3 = -0.5$ arrives, the weight moves by $\alpha \delta_3 z_3 =
\alpha(-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**, $\mathbf{z}_t = \gamma\lambda
\mathbf{z}_{t-1} + \mathbf{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$:[^sb-traces]

$$
z_{i,t} \;\doteq\;
\begin{cases}
1 & \text{if } x_{i,t} = 1, \\
\gamma\lambda\, z_{i,t-1} & \text{otherwise.}
\end{cases}
$$

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,

$$
\mathbf{z}_t = \gamma\lambda\,\mathbf{z}_{t-1} + \big(1 - \alpha\gamma\lambda\,\mathbf{z}_{t-1}^\top\mathbf{x}_t\big)\,\mathbf{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.

$$
% caption: The three trace types for one binary feature that fires at steps 0, 1, 2
% then stops (decay $\gamma\lambda$). 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (7.2,0);
  \node[anchor=north, font=\scriptsize] at (3.5,-0.2) {step};
  \draw[->, black] (0,0) -- (0,3.0);
  \node[anchor=east, font=\scriptsize] at (-0.1,2.6) {trace};
  \draw[black, dashed] (0,1.0) -- (7.0,1.0);
  \node[anchor=east, font=\scriptsize] at (-0.1,1.0) {1};
  % x positions for steps 0..6; feature fires at steps 0,1,2 then stops
  % accumulating: 1, 1.8, 2.44, then decay 0.8x
  \foreach \s/\v in {0/1.0, 1/1.8, 2/2.44, 3/1.95, 4/1.56, 5/1.25, 6/1.0} {
    \fill[acc] ({\s*1.05+0.15},{\v}) circle (1.6pt);
  }
  \draw[acc, thick] (0.15,1.0) -- (1.2,1.8) -- (2.25,2.44) -- (3.3,1.95) -- (4.35,1.56) -- (5.4,1.25) -- (6.45,1.0);
  \node[acc, anchor=west, font=\scriptsize] at (6.5,1.0) {accumulating};
  % replacing: capped at 1 while firing, then decay 0.8x
  \foreach \s/\v in {0/1.0, 1/1.0, 2/1.0, 3/0.8, 4/0.64, 5/0.51, 6/0.41} {
    \fill[red] ({\s*1.05+0.15},{\v}) circle (1.6pt);
  }
  \draw[red, thick] (0.15,1.0) -- (1.2,1.0) -- (2.25,1.0) -- (3.3,0.8) -- (4.35,0.64) -- (5.4,0.51) -- (6.45,0.41);
  \node[red, anchor=west, font=\scriptsize] at (6.5,0.41) {replacing};
  % dutch: between, e.g. 1, 1.4, 1.65, then decay
  \foreach \s/\v in {0/1.0, 1/1.4, 2/1.65, 3/1.32, 4/1.06, 5/0.85, 6/0.68} {
    \fill[black] ({\s*1.05+0.15},{\v}) circle (1.6pt);
  }
  \draw[black, thick] (0.15,1.0) -- (1.2,1.4) -- (2.25,1.65) -- (3.3,1.32) -- (4.35,1.06) -- (5.4,0.85) -- (6.45,0.68);
  \node[anchor=west, font=\scriptsize] at (6.5,0.68) {dutch};
\end{tikzpicture}
$$

## 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^\lambda$ | the current TD error $\delta_t$ |
| Direction | looks ahead to future rewards | credits past states |
| State of memory | needs the whole future | one trace vector $\mathbf{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 $\alpha$ grows. Exact equivalence, and the
extension of the trace apparatus to control, continues in
[true online TD(λ) and Sarsa(λ)](/reinforcement-learning/approximation/true-online-and-sarsa-lambda).

[^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 12 — Eligibility Traces: the trace vector $\mathbf{z}_t$ as a short-term memory paralleling $\mathbf{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).
[^sb-traces]: **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.