Is SARSA(lambda) on-policy?

Yes; its sampled continuation follows the policy generating actions.

What happens at lambda equal to zero?

The accumulating-trace tabular method reduces to one-step SARSA.

Can lambda replace exploration?

No. Traces distribute learning signals; they do not ensure that useful actions are tried.

AI Glossary / Reinforcement learning and robotics / Advanced

SARSA(lambda)

Definition

SARSA(lambda) is an on-policy reinforcement-learning control method that extends one-step SARSA with eligibility traces. A temporal-difference error updates recently visited state-action pairs as well as the current pair. Lambda controls how strongly credit persists across successive decisions. The method learns action values for the policy used to select actions, including that policy's exploration behavior.

What it means

SARSA takes its name from a transition containing state, action, reward, next state and next action. The next action matters: its estimated value supplies the continuation term in the update. This differs from Q-learning, which uses the largest next-state action value regardless of the action actually selected.

Eligibility traces retain a fading record of earlier state-action visits. A later success or failure can therefore influence preceding decisions immediately, without waiting for many separate episodes to propagate the signal one step at a time.

Lambda is not an exploration probability. Exploration may be controlled separately through an epsilon-greedy or another stochastic policy. A larger lambda extends credit assignment, while also changing sensitivity to noise and the choice of step size.

How it works

For tabular SARSA(lambda) with accumulating traces, initialize all traces to zero at the start of an episode. Execute the current action and observe the reward and next state. Unless the episode truly terminates, choose the next action using the current behavior policy.

Compute delta as reward plus gamma times Q of that next state-action pair, minus Q of the current pair. For a genuine terminal transition, the continuation is zero. Increment the current pair's trace by one, update every pair by alpha times delta times its trace, then multiply every trace by gamma times lambda.

Continue with the next state and the action already selected. That action should actually be executed; selecting a different action after updating would no longer match the sample used in the SARSA target.

Replacing traces reset a visited pair's trace rather than accumulating another unit. True-online variants use additional corrections. These are distinct algorithms, so an implementation should identify its trace convention. Ordinary online accumulating-trace updates are not generally identical to a fixed-weight forward-view calculation when values change during an episode.

Three practical examples

1. A small navigation learner propagates a delayed destination reward to several earlier movements during the same episode.

2. A scheduling simulator evaluates behavior that includes occasional exploratory actions, so the continuation value includes the consequences of that exploration.

3. A teaching experiment compares lambda equal to zero with longer traces while keeping the action sequence, initial values and learning rate fixed.

Think of it this way

Think of leaving fading bookmarks along a decision sequence. When a useful correction arrives, every remaining bookmark receives a share according to its strength. Revisiting a decision can strengthen its bookmark with accumulating traces. The bookmarks record eligibility for an update; they do not establish that every bookmarked decision caused the final outcome.

Worked example

Consider an original two-transition episode with distinct state-action pairs X and Y. Initially Q(X) is 1 and Q(Y) is 2. Set alpha to 0.2, gamma to 0.9 and lambda to 0.5. All traces start at zero, and use accumulating traces.

Taking X produces reward 0 and reaches the state where action Y is selected. The first TD error is 0 plus 0.9 times 2 minus 1, or 0.8. Increment X's trace to one. Its value becomes 1 plus 0.2 times 0.8, or 1.16. Decaying the trace multiplies it by 0.45, leaving e(X) equal to 0.45.

Taking Y then produces reward 4 and terminates. The terminal TD error is 4 minus 2, or 2. Increment Y's trace to one. Updating both pairs gives Q(X) equal to 1.16 plus 0.2 times 2 times 0.45, or 1.34, and Q(Y) equal to 2 plus 0.2 times 2, or 2.4.

With lambda equal to zero, X's earlier trace would have vanished and its final value would remain 1.16. The additional 0.18 is the backward propagation enabled by the trace.

Suppose the next state also offered an unselected action with Q equal to 5. SARSA's first target would still use the selected Y value of 2. A max-based Q-learning target would instead be 4.5. The distinction persists even when the unselected action currently appears better.

Illustrative case study

In a fictional project, Cedar Routes studies a delivery robot in a grid simulator. Rewards arrive mainly when the robot completes a route, and one-step updates spread that information slowly through earlier decisions.

The researchers compare accumulating-trace SARSA settings using matched random seeds and the same exploration rule. They record return, route length, value magnitude and unsuccessful runs, rather than selecting a lambda solely from one favorable trial.

They also verify that terminal transitions use zero continuation and that an exploratory next action remains in the learning target. The exercise illustrates method selection and implementation checks; it does not report a real robot deployment or claim that traces always improve sample efficiency.

Common misconceptions and mistakes

Do not replace the selected next action with the maximum while still calling the update SARSA. Do not clear traces merely because an exploratory action was selected; that resembles a particular off-policy trace-cutting rule, not ordinary SARSA(lambda).

Do not confuse traces indexed by state with traces indexed by state-action pair. Finally, lambda equal to one does not make every online implementation identical to a particular Monte Carlo update at finite learning rates.

Business use

The method is useful as an interpretable baseline for sequential decisions with delayed feedback and manageable state-action representations. Compare return variability and sensitivity to alpha and lambda alongside average performance. For large representations, trace storage and update cost matter, and general function approximation requires additional care rather than inheriting every tabular guarantee.

Check your understanding

What is the terminal TD error in the example?

Answer: 2.

How much does the second update add to Q(X)?

Answer: 0.18.

Why is the unselected action value of 5 excluded?

Answer: The SARSA target uses the next action actually selected by the policy.

Related terms

Learn next

Learn one-step SARSA first, then trace bookkeeping and lambda returns. Compare accumulating, replacing and true-online methods using the same short episode before moving to function approximation or off-policy algorithms.

Sources

Sutton and Barto, Reinforcement Learning: An Introduction, author draft, section 7.5: https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf. The state-action update and on-policy distinction were checked against this primary textbook account. The arithmetic and fictional case are original illustrations using accumulating traces.

Previous: SARSA Next: SAT