Eligibility traces unify and generalize:

• MC methods
• TD methods

When TD methods are augmented with eligibility traces, they produce a family of methods spanning a spectrum that has:

• MC methods at one end (𝜆=1)
• one-step TD methods at the other (𝜆=0)
• in between are intermediate methods that are often better than either extreme method

Eligibility Traces

For each time step 𝑡, eligibility traces are updated as:

Accumulate Trace Form (most common)

• $e_t(s)=\{\begin{array}{ll}1& \text{if }s=S_t\\ \lambda \gamma e_{t-1}(s)& \text{otherwise}\end{array}$

Or, more compactly:

• $e_t(s)=\gamma \lambda e_{t-1}(s)+1(s=S_t)$

Where:

• γ = discount factor
• λ = trace decay parameter (0 → short memory, 1 → long memory)
• 1(s=St)\mathbf{1}(s = S_t)1(s=St​) = 1 if you visited the state, 0 otherwise

Thus:

• If you just visited the state, its trace spikes to 1
• On every following step, it shrinks by factor 𝛾𝜆

λ-return

𝜆-return is defined as:

• $G_t^{\lambda }=(1-\lambda ){\sum }_{n=1}^{\inf }{\lambda }^{n-1}{G}_{t:t+n}$

𝜆-return (separated post-termination terms):

• $G_t^{\lambda }=(1-\lambda ){\sum }_{n=1}^{T-t-1}{\lambda }^{n-1}{G}_{t:t+n}+{\lambda }^{T-t-1}{G}_t$

offline 𝜆-return algorithm:

• ${\mathbf{w}}_{t+1}=\mathbf{w}\alpha [G_t^{\lambda }-\hat{v}(S_t,{\mathbf{w}}_t)]\nabla \hat{v}(S_t,{\mathbf{w}}_t),\text{ for }t=0,...,T-1$

TD(λ)

• TD(λ) is literally averaging all n-step TD methods with geometric weights λ
• it approximates the offline λ-return algorithm

the eligibility trace vector is initiated to zero at the beginning of the episode, is incremented on each time step by the value gradient, and then fades away by 𝛾𝜆:

• ${\mathbf{z}}_{-1}=0$
• ${\mathbf{z}}_t=\gamma \lambda {\mathbf{z}}_{t-1}+\nabla \hat{v}(S_t,{\mathbf{w}}_t),\text{ 0 <= t <= T}$

The TD error for state-value prediction is:

• ${\delta }_t=R_{t+1}+\gamma \hat{v}(S_{t+1},{\mathbf{w}}_t)-\hat{v}(S_t,{\mathbf{w}}_t)$

weight vector is updated proportional to the scalar TD error and the vector eligibility trace:

• ${\mathbf{w}}_{t+1}={\mathbf{w}}_t+\alpha {\delta }_t{\mathbf{z}}_t$

Semi-Gradient TD(𝜆) for estimating 𝑣̂ ~ 𝑣_𝜋:

Input: the policy 𝜋 to be evaluated
Input: a di↵erentiable function 𝑣̂ : Sxℝ^d -> ℝ such that 𝑣̂(terminal,·) = 0
Algorithm parameters: step size 𝛼 > 0, trace decay rate  𝜆=[0, 1]
Initialize value-function weights 𝐰 arbitrarily (e.g., 𝐰 = 0)

loop for each episode:
	initialize 𝑆
	𝐳 = 0
	loop until 𝑆 is terminal:
		choose 𝐴 ~ 𝜋(|𝑆)
		take action 𝐴, observe 𝑅,𝑆'
		𝐳 = 𝛾𝜆𝐳 + ????̂(𝑆,𝐰)
		𝛿 = 𝑅 + 𝛾𝑣̂(𝑆',𝐰) - 𝑣̂(𝑆,𝐰)
	 	𝐰 = 𝐰 + 𝛼𝛿𝐳
		𝑆 = 𝑆'

for values of 𝜆:

• 𝜆=0 then algorithm simplifies to TD(0)
• 𝜆=? then
• 𝜆=1 then algorithm BEHAVES like MC

SARSA(λ)

If you use them for action-values:

• $e_t(s,a)=\gamma \lambda e_{t-1}(s,a)+1(s=S_t,a=A_t)$

Update:

• $Q(s,a)\leftarrow Q(s,a)+\alpha {\delta }_t{e}_t(s,a)$