SARSA

Also known as: State–action–reward–state–action

On this page 7

SARSA (State–action–reward–state–action) is an on-policy temporal difference control algorithm that learns an action-value function Q(s, a) by updating each estimate toward the reward received plus the value of the next action the agent actually chooses. In reinforcement learning, it is one of the foundational tabular methods, and it remains a standard teaching and baseline algorithm across artificial intelligence research.

The name lists the five quantities used in every update: the current state and action, the reward, and the next state and next action. Because the next action comes from the same exploratory policy that the agent follows, SARSA evaluates and improves the policy it is actually executing, including its exploration.

How the SARSA update works

SARSA improves its estimates after every single step by moving Q(s, a) toward a one-step target. The update rule is Q(s, a) becomes Q(s, a) + alpha times [r + gamma Q(s’, a’) minus Q(s, a)], where the bracketed term is the temporal difference error.

The algorithm repeats a short loop for every time step of every episode:

  1. Observe state s and choose action a with the current policy, typically epsilon-greedy over Q.
  2. Execute a, then observe the reward r and the next state s’.
  3. Choose the next action a’ from s’ with the same policy.
  4. Update Q(s, a) with the target r + gamma Q(s’, a’), then set s to s’ and a to a’.

The following table explains the parameters that control the update and their usual ranges.

ParameterTypical rangeEffect
Learning rate alpha0.01 to 0.5Step size toward the target; higher values adapt faster but add noise
Discount factor gamma0.9 to 0.999Weight of future rewards relative to immediate ones
Exploration rate epsilon0.01 to 0.2, often decayedProbability of a random action
Trace decay lambda0 to 1Used in SARSA(lambda) to spread credit over earlier steps
Main SARSA parameters

On-policy learning and convergence

SARSA is on-policy because the policy that generates behavior is the same policy whose value it estimates. The learned Q-function therefore reflects the expected return under exploration, not under ideal greedy play.

For lookup tables, SARSA reaches the optimal action values almost surely provided three requirements hold. Each pair of state and action must keep being tried, step sizes must shrink at a suitable rate, and the behavior must turn greedy in the limit with infinite exploration (GLIE), which a slowly decaying epsilon achieves. In practice, epsilon is often held at a small constant, so the result is the best policy among epsilon-soft policies rather than the strictly optimal one.

With function approximation, such as linear features or neural networks, the guarantees weaken. Linear SARSA usually behaves well but can chatter around a solution, and nonlinear approximators offer no general convergence guarantee.

What separates SARSA from its closest relatives is the bootstrap target each one plugs into its update. SARSA looks up the estimate for a’ as sampled, whereas its off-policy counterpart takes the highest estimate available in s’. That one substitution decides whether a method is on-policy or off-policy.

AlgorithmTarget usedPolicy typeTypical behavior
SARSAr + gamma Q(s’, a’)On-policySafer paths that account for exploration
Q-learningr + gamma max Q(s’, a)Off-policyLearns optimal values, riskier during training
Expected SARSAr + gamma expected Q under policyOn- or off-policyLower variance than SARSA
SARSA(lambda)Lambda-return via eligibility tracesOn-policyFaster credit assignment
Monte Carlo controlFull episode returnOn- or off-policyUnbiased but high variance
SARSA and neighboring algorithms

A grid world with a hazardous edge, often called cliff walking, makes the contrast visible. SARSA settles on a longer, safer route that keeps its distance from the hazard, since its estimates already price in the cost of its own random actions. The off-policy learner prefers the tight route beside the edge and, while still exploring, suffers more penalties, so SARSA earns more reward per episode during training.

Variants and practical use

Several extensions keep the on-policy idea of SARSA while addressing its weaknesses in variance, speed and scale. The table below summarizes when each variant is a sensible choice.

SituationRecommended variantReason
Small discrete state spaceTabular SARSASimple, transparent, convergent
Delayed or sparse rewardsSARSA(lambda)Eligibility traces propagate credit quickly
Noisy updates from stochastic policyExpected SARSAAverages over next actions to reduce variance
Large or continuous state spaceSemi-gradient SARSA with tile coding or linear featuresGeneralizes across similar states
Very high-dimensional observationsDeep on-policy methods such as actor-criticNeural networks with more stable training schemes
Choosing a SARSA variant

SARSA is a natural choice when mistakes during learning are costly, for example in online control of physical systems or simulations where the agent must keep operating while it learns. It is also popular in teaching and benchmarking, because its behavior is easy to inspect in grid worlds and small control tasks such as Mountain Car.

Limitations and common mistakes

SARSA shares the general weaknesses of one-step bootstrapping methods and adds a few of its own. The most common problems and their remedies are listed below.

SymptomCauseRemedy
Policy never becomes fully greedyConstant epsilonDecay epsilon on a GLIE schedule
Very slow learning with sparse rewardsOne-step credit assignmentUse SARSA(lambda) or reward shaping
Wrong next action in the updatea’ chosen after the updateSelect a’ before updating Q(s, a)
Unstable values with deep networksCorrelated on-policy samplesPrefer actor-critic or PPO-style methods
Frequent SARSA problems

A frequent conceptual error is to treat SARSA as a version of Q-learning with experience replay. Because SARSA is on-policy, replaying old transitions generated by outdated policies violates its assumptions, which is why deep reinforcement learning systems built on replay buffers normally use off-policy algorithms instead.

The simple explanation

SARSA is a way for a computer agent to learn good habits by trial and error. After each move, it asks a simple question. How good was that move, given what I actually did next? It then nudges its estimate a little in that direction.

Think of a new driver who sometimes takes a wrong turn by accident. A careful driver plans routes that stay safe even with occasional mistakes. SARSA learns in the same cautious way, because it remembers that it will sometimes act randomly while it is still learning.

How it is used in practice

A robotics team trains a small warehouse robot to move between shelves in a simulated layout of 400 grid cells. Some cells lie next to a loading dock edge, where a fall costs a penalty of minus 100, while each ordinary step costs minus 1. The team uses tabular SARSA with alpha 0.1, gamma 0.99 and epsilon decayed from 0.2 to 0.02 over 5,000 episodes.

A parallel Q-learning run finds a route about 10 percent shorter, but during training it falls off the edge far more often. The SARSA agent learns a route that keeps one cell of distance from the edge. Because the real robot will keep a small amount of exploration after deployment, the team chooses the SARSA policy, accepting slightly longer trips in exchange for far fewer costly incidents.