SARSA Lambda

SARSA lambda gives every recent action a fading trace, so one reward updates the whole trail at once instead of one step at a time.

Why Does This Exist?

One-step SARSA learns slowly over long trails. It updates only the last state-action pair $(S_t, A_t)$ from reward $R_{t+1}$ and the next value $Q(S_{t+1}, A_{t+1})$ . Walk a 20-step corridor to a goal and the first episode teaches only the final step; the start must succeed 20 times before the news reaches it.

Monte Carlo fixes the reach but adds waiting and noise: it holds every update until the episode ends, then averages whole returns with high variance. N-step methods sit between but need trajectory buffers and delayed updates.

SARSA lambda (Sutton and Barto; Rummery and Niranjan, 1994) removes the wait. Each pair keeps a trace $z(s, a)$ marking how recently it was chosen. When the on-policy error $\delta_t$ arrives, every pair learns at once in proportion to its trace. One reward crosses the whole trail in a single episode, online, with no buffer. For the state-value version of the same idea see eligibility traces, for the one-step comparison see Q-learning versus SARSA, and for the one-step engine underneath see temporal-difference learning.

Think of It Like This

Praising the whole soccer move, not just the tap-in

A team scores after a 60-yard counter. One-step SARSA praises only the striker who tapped it in. Monte Carlo waits for the full 90 minutes, then praises everyone equally, including the throw-ins. SARSA lambda watches the replay at once: striker gets full credit at 1.0, the winger who crossed gets 0.63, the midfielder who launched it gets 0.40, and the bench gets nothing.

Point for point: the goal is the TD error, the replay weights are the traces, and bench players are unvisited pairs with trace zero. Fresh actions earn more because their traces decayed less.

Where it stops: a coach judges style. Traces multiply by exactly $\gamma \lambda$ each step, where $\gamma$ discounts the future and $\lambda$ sets the reach, and the update evaluates the action actually taken next, not the best action imaginable.

How It Actually Works

Work with discrete states $\mathcal{S}$ and actions $\mathcal{A}$ . Let $\gamma$ in $[0, 1]$ discount the future, $\lambda$ in $[0, 1]$ set the trace reach, and $\alpha$ in $(0, 1]$ be the step size. $Q(s, a)$ estimates action value and $z(s, a)$ stores its trace. All traces start at zero each episode.

The trace memory

Replacing traces reset the visited pair to 1 and decay the rest by $\gamma \lambda$ :

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

Accumulating traces add instead of resetting, which can exceed 1 in loops and swing values. Replacing caps eligibility at 1.0 and suits control tasks, so the worked example uses replacing.

The on-policy error

After taking $A_t$ in $S_t$ , the agent banks $R_{t+1}$ , lands in $S_{t+1}$ , and draws $A_{t+1}$ from its own behavior policy such as epsilon-greedy. The error evaluates the action actually drawn:

$\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$

At termination $Q(S_{t+1}, A_{t+1})$ is zero. Using the max over actions here would turn the update into Q-learning; SARSA lambda must use the sampled $A_{t+1}$ to stay on-policy.

One error updates everything

The scalar $\delta_t$ scales every pair by its trace:

$Q(s, a) = Q(s, a) + \alpha \delta_t z_t(s, a)$

With $\lambda = 0$ only the current pair carries trace 1 and the rest sit at zero, which recovers one-step SARSA. With $\lambda = 1$ traces decay by $\gamma$ alone and the method behaves like online Monte Carlo. Values between blend speed against variance.

Worked example

Three moves with $\gamma = 0.9$ , $\lambda = 0.7$ , so decay is $0.9 \times 0.7 = 0.63$ , plus $\alpha = 0.1$ and all $Q$ starting at 0:

Step 0 visits $(S_0, \text{right})$ with reward $0.0$ . Trace becomes $1.0$ , error is $0.0$ , no learning. Decay leaves $0.63$ .
Step 1 visits $(S_1, \text{up})$ with reward $0.0$ . Traces are $1.0$ for the new pair and $0.63$ for the old one. Error is $0.0$ . Decay leaves $0.63$ and $0.63 \times 0.63 = 0.3969$ .
Step 2 visits $(S_2, \text{right})$ and banks $R = 10.0$ at termination. Traces are $1.0$ , $0.63$ , and $0.3969$ . Error is $\delta = 10.0 + 0.9 \times 0.0 - 0.0 = 10.0$ . With $\alpha \delta = 0.1 \times 10.0 = 1.0$ , updates are $1.0 \times 1.0 = 1.0$ for $(S_2, \text{right})$ , $1.0 \times 0.63 = 0.63$ for $(S_1, \text{up})$ , and $1.0 \times 0.3969 = 0.3969$ for $(S_0, \text{right})$ . Unvisited pairs hold trace zero and stay at zero.

One-step SARSA with $\lambda = 0$ would learn only the first number ( $1.0$ ) and leave the other two at zero. SARSA lambda teaches all three in the same episode. Those three numbers are what the diagram draws.

Code

Three operations carry the method: decay traces, set the visited pair, then scale one error by every trace.

1gamma, lam, alpha = 0.9, 0.7, 0.12decay = gamma * lam3print(f"decay: {decay:.2f}")4# -> decay: 0.635
6z0, z1 = 0.63, 0.63 * 0.637print(f"traces: 1.0 {z1 / 1.0:.2f} {z1:.4f}")8# -> traces: 1.0 0.63 0.39699
10delta = 10.011step = alpha * delta12print(f"updates: {step * 1.0:.2f} {step * 0.63:.2f} {step * 0.3969:.4f}")13# -> updates: 1.00 0.63 0.3969

Multiply each trace by $\alpha \delta = 1.0$ and you get the $Q$ changes from the worked example.

Watch Out For

Swapping in the max and silently building Q-learning

The symptom: you write the SARSA lambda loop but compute the error with $\max_a Q(S_{t+1}, a)$ instead of the sampled $Q(S_{t+1}, A_{t+1})$ , keep traces running, and watch values oscillate. Past actions earn credit for a greedy move they never committed to, which breaks the on-policy guarantee.

Always use the action the behavior policy actually drew. Reset all traces to zero at each episode start, and prefer replacing traces in looping tasks so eligibility never piles past 1.0.

Carrying traces across episode boundaries

The symptom: early states of a new episode drift even though nothing rewarding happened yet. Last episode leftovers are still nonzero, so the next reward pays ghosts from the previous run.

Reset unconditionally on done, including timeout truncations unless your setup treats them differently on purpose. Traces are episode memory, not lifetime memory.

The Quick Version

SARSA lambda keeps one trace $z(s, a)$ per pair that decays by $\gamma \lambda$ each step and marks the visited pair.
Its error is on-policy: $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$ with the sampled next action.
One error updates all pairs through $Q = Q + \alpha \delta z$ , so a single reward crosses multi-step trails at once.
With decay 0.63 and reward 10, three actions update by 1.0, 0.63 and 0.3969 together; one-step SARSA would update only the last one.
Lambda 0 recovers one-step SARSA and lambda 1 behaves like online Monte Carlo.
Reset traces every episode and use replacing traces when states recur.