Eligibility traces interpolate between one-step TD and Monte Carlo returns. They assign credit backward through recently visited states or features.
Lambda returns
The \(\lambda\)-return averages \(n\)-step returns geometrically.
Definition. The \(n\)-step return is \[ G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^nv(S_{t+n}). \] The forward-view \(\lambda\)-return is \[ G_t^\lambda=(1-\lambda)\sum_{n=1}^\infty\lambda^{n-1}G_t^{(n)},\qquad 0\le\lambda<1. \]
Proposition. When \(\lambda=0\), \(G_t^\lambda\) is the one-step TD target. As \(\lambda\uparrow1\), it approaches the Monte Carlo return when the discounted return is finite.
Proof. At \(\lambda=0\), only \(n=1\) has positive weight. As \(\lambda\uparrow1\), the geometric weighting shifts mass to longer horizons; with bounded discounted returns, Abelian convergence gives the full return limit.
Backward eligibility traces
The backward view computes the same credit assignment online.
Definition. For tabular TD, the accumulating trace is \[ e_t(s)=\gamma\lambda e_{t-1}(s)+\mathbf 1\{S_t=s\}. \] The update is \[ v_{t+1}(s)=v_t(s)+\alpha_t\delta_t e_t(s). \]
Remark. The trace marks which previous states are eligible to receive the current TD error. Larger \(\lambda\) makes credit assignment more persistent.
Forward-backward equivalence
For fixed value estimates within an episode, the forward and backward views agree.
Theorem. In the episodic tabular case with offline updates, summing TD errors with eligibility traces gives the same total update as using forward-view \(\lambda\)-returns.
Proof. Expand the backward update as a double sum over times and traces: \[ \sum_t\delta_te_t(s)=\sum_{k:S_k=s}\sum_{t\ge k}(\gamma\lambda)^{t-k}\delta_t. \] The inner discounted sum telescopes into \(G_k^\lambda-v(S_k)\), which is precisely the forward-view error for visit \(k\).
Bias-variance continuum
The trace parameter tunes between bootstrapping and full returns.
Remark. Small \(\lambda\) uses more bootstrapping and often lower variance; large \(\lambda\) uses longer returns and often lower bootstrap bias. The best value depends on mixing, reward noise, and approximation error.
Lambda returns
The \(n\)-step return from time \(t\) is \[ G_t^{(n)} =\sum_{k=0}^{n-1}\gamma^kR_{t+k+1} +\gamma^nV(S_{t+n}). \] For \(0\le\lambda<1\), the forward lambda return is \[ G_t^\lambda =(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)}. \] It interpolates between one-step TD at \(\lambda=0\) and Monte Carlo return as \(\lambda\uparrow1\), when episodes or discounting make the limit meaningful.
Proposition (lambda operator). For a fixed policy, \[ T_\lambda^\pi V =(1-\lambda)\sum_{n\ge1}\lambda^{n-1}(T^\pi)^nV =V+(I-\gamma\lambda P_\pi)^{-1}(T^\pi V-V). \] Its fixed point is \(V^\pi\), and its sup-norm contraction modulus is \[ \kappa_\lambda =\frac{\gamma(1-\lambda)}{1-\gamma\lambda}. \]
Proof. Expand \((T^\pi)^nV=\sum_{k=0}^{n-1}\gamma^kP_\pi^kr_\pi +\gamma^nP_\pi^nV\), interchange absolutely convergent sums, and recognize the resolvent. The reward terms cancel when taking differences, giving \[ T_\lambda^\pi V-T_\lambda^\pi W =(1-\lambda)\gamma P_\pi (I-\lambda\gamma P_\pi)^{-1}(V-W), \] whose operator norm is at most the displayed geometric sum.
Backward eligibility traces
For linear prediction, accumulating traces satisfy \[ z_t=\gamma\lambda z_{t-1}+\phi(S_t), \qquad w_{t+1}=w_t+\alpha_t\delta_tz_t. \] The trace records a geometrically decaying memory of past features, assigning the current TD error backward to recently visited states.
Theorem (forward--backward equivalence). For a fixed finite trajectory, fixed value estimates during the episode, and offline accumulation of updates, the total update generated by TD errors and eligibility traces equals \[ \sum_t\alpha\{G_t^\lambda-V(S_t)\}\phi(S_t). \]
Proof. The identity \[ G_t^\lambda-V(S_t) =\sum_{k=t}^{\infty}(\gamma\lambda)^{k-t}\delta_k \] follows by expanding TD errors and telescoping value terms. Substitute it into the forward update and interchange the two sums. The coefficient of \(\delta_k\) becomes \(\sum_{t\le k}(\gamma\lambda)^{k-t}\phi(S_t)=z_k\).
Bias, variance, and effective horizon
Larger \(\lambda\) weakens bootstrapping and reduces approximation bias but propagates more reward noise. The effective trace horizon is roughly \((1-\gamma\lambda)^{-1}\). In continuing tasks with large \(\gamma\), even a moderate \(\lambda\) can create long memory and substantial temporal correlation.
Off-policy traces
Naive traces are biased off-policy. Per-decision importance sampling inserts ratios \(\rho_t=\pi(A_t\mid S_t)/\mu(A_t\mid S_t)\), but products can explode. Algorithms such as Retrace and V-trace use truncated coefficients \[ c_t=\lambda\min(\bar c,\rho_t) \] to preserve a contractive multistep operator while trading exact correction for controlled bias. Their guarantees depend on the exact operator induced by the clipping rule, not on the trace recursion alone.