Eligibility Traces

One reward should credit the whole trail that led to it, with recent steps getting more credit than old ones. Eligibility traces are that fading memory.

A reward of 10 at the end updates every visited state at once, scaled by traces 1.09 for A, 0.52 for B, and 1.0 for C

Why Does This Exist?

A reward often arrives long after the choices that caused it. One-step temporal-difference learning updates only the last state, so credit crawls back one step per episode. Monte Carlo waits until the episode ends and then credits everything, which fails when episodes never end and jumps around a lot.

Eligibility traces split the difference. Each state keeps a trace $z(s)$ that marks how recently and how often it was visited. When the one-step error $\delta_t$ arrives, every state learns at once in proportion to its trace. You get multi-step credit on every step without waiting.

Think of It Like This

Footprints filling with gold dust

You walk across a beach and each step leaves a print. Wind softens old prints while fresh ones stay sharp. Stepping twice in the same spot digs it deeper.

When you find a coin at the end, someone sprinkles gold dust over the whole trail. Deep fresh prints catch a lot, faint old prints catch a little, untouched sand catches nothing. The dusting happens once, right when the coin appears.

Where it stops: beach prints fade unevenly. Traces fade by exactly $\gamma \lambda$ each step, where $\gamma$ discounts the future and $\lambda$ sets how far credit reaches.

How It Actually Works

Start each episode with $z_0(s) = 0$ for all states $s$ . On step $t$ in state $S_t$ , decay every trace by $\gamma \lambda$ and bump the visited state. Two bump rules are standard.

Accumulating traces add one on every visit:

z_t(s) = \gamma \lambda z_{t-1}(s) + 1 \quad \text{if } s = S_t, \text{ else } \gamma \lambda z_{t-1}(s)

Replacing traces reset the visited state to one, which stops loops from piling up:

z_t(s) = 1 \quad \text{if } s = S_t, \text{ else } \gamma \lambda z_{t-1}(s)

The one-step error uses reward $R_{t+1}$ , discount $\gamma$ , and current value estimates $V$ :

\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)

Then every state moves a little along the error, scaled by step size $\alpha$ and its trace:

V(s) = V(s) + \alpha \delta_t z_t(s)

Setting $\lambda = 0$ keeps credit for one step and recovers one-step TD. Setting $\lambda = 1$ spreads credit across the whole episode like Monte Carlo but still updates online. Values in between blend the two.

Worked example

Use $\gamma = 0.9$ , $\lambda = 0.8$ , so decay is $0.72$ , with $\alpha = 0.5$ and all values starting at 0. The agent walks $S_A$ to $S_B$ to $S_A$ to $S_C$ , then earns 10 and terminates.

After visiting $S_A$ : $z(S_A) = 1.00$ .
After $S_B$ : $z(S_A) = 0.72$ , $z(S_B) = 1.00$ .
After revisiting $S_A$ : accumulating gives $0.72 \times 0.72 + 1 = 1.5184$ , replacing gives $1.00$ . For $S_B$ : $0.72$ .
Final step to termination with $R = 10$ : decay once more. Accumulating ends at $z(S_A) = 1.0932$ , $z(S_B) = 0.5184$ , $z(S_C) = 1.00$ . Replacing ends at $z(S_A) = 0.72$ with the other two the same.

The final error is $\delta = 10.0$ , so each update is $0.5 \times 10.0 \times z = 5.0 \times z$ :

Accumulating: $V(S_A) = 5.466$ , $V(S_B) = 2.592$ , $V(S_C) = 5.000$ .
Replacing: $V(S_A) = 3.600$ , the other two match.

One reward updated three states at once. Revisiting $S_A$ earned extra credit under accumulating traces and capped credit under replacing traces. The forward and backward views prove this backward broadcast matches the forward lambda return offline.

Code

Three lines carry the method: decay all traces, bump the visited state, then scale one error by every trace.

1def step_traces(z: dict, state: str, decay: float, mode: str) -> dict:2    for s in z:  # fade every trace by gamma times lambda3        z[s] *= decay4    z[state] = z[state] + 1.0 if mode == "accumulating" else 1.05    return z6
7
8z = step_traces({"A": 1.5184, "B": 0.72, "C": 0.0}, "C", 0.72, "accumulating")9print(f"{z['A']:.4f} {z['B']:.4f} {z['C']:.4f}")10# -> 1.0932 0.5184 1.0000

The printout is the final trace row from the worked example. Multiply by $5.0$ and you get the value updates above.

Watch Out For

Letting accumulating traces blow up in loops

Each revisit adds another 1.0 before decay removes it. In a task with tight cycles and $\gamma \lambda$ near 1, traces climb past 5 or 10 and sit there. The next nonzero error then hits like a huge step size and values swing wildly.

Use replacing traces when states recur often, or keep $\gamma \lambda$ clearly below 1 so the geometric bound $1 / (1 - \gamma \lambda)$ stays small. Zero all traces at each terminal state.

Carrying traces across episode boundaries

Traces are episode memory, not lifetime memory. If you forget to reset $z$ to zero at termination, the first states of the next episode inherit credit from the last episode's reward. Values leak across unrelated episodes and early states drift.

Reset unconditionally on done. If your loop has timeout truncations as well as true terminations, reset on both unless your algorithm treats them differently on purpose.

The Quick Version

Eligibility traces store recency and frequency for every state in a vector $z(s)$ .
Each step decays traces by $\gamma \lambda$ and bumps the visited state.
One TD error updates all states through $V(s) = V(s) + \alpha \delta_t z_t(s)$ .
Accumulating traces add on revisits while replacing traces reset to 1.0.
Lambda 0 is one-step TD and lambda 1 behaves like Monte Carlo, done online.