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:
- Observe state s and choose action a with the current policy, typically epsilon-greedy over Q.
- Execute a, then observe the reward r and the next state s’.
- Choose the next action a’ from s’ with the same policy.
- 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.
| Parameter | Typical range | Effect |
|---|---|---|
| Learning rate alpha | 0.01 to 0.5 | Step size toward the target; higher values adapt faster but add noise |
| Discount factor gamma | 0.9 to 0.999 | Weight of future rewards relative to immediate ones |
| Exploration rate epsilon | 0.01 to 0.2, often decayed | Probability of a random action |
| Trace decay lambda | 0 to 1 | Used in SARSA(lambda) to spread credit over earlier steps |
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.
SARSA compared with Q-learning and related methods
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.
| Algorithm | Target used | Policy type | Typical behavior |
|---|---|---|---|
| SARSA | r + gamma Q(s’, a’) | On-policy | Safer paths that account for exploration |
| Q-learning | r + gamma max Q(s’, a) | Off-policy | Learns optimal values, riskier during training |
| Expected SARSA | r + gamma expected Q under policy | On- or off-policy | Lower variance than SARSA |
| SARSA(lambda) | Lambda-return via eligibility traces | On-policy | Faster credit assignment |
| Monte Carlo control | Full episode return | On- or off-policy | Unbiased but high variance |
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.
| Situation | Recommended variant | Reason |
|---|---|---|
| Small discrete state space | Tabular SARSA | Simple, transparent, convergent |
| Delayed or sparse rewards | SARSA(lambda) | Eligibility traces propagate credit quickly |
| Noisy updates from stochastic policy | Expected SARSA | Averages over next actions to reduce variance |
| Large or continuous state space | Semi-gradient SARSA with tile coding or linear features | Generalizes across similar states |
| Very high-dimensional observations | Deep on-policy methods such as actor-critic | Neural networks with more stable training schemes |
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.
| Symptom | Cause | Remedy |
|---|---|---|
| Policy never becomes fully greedy | Constant epsilon | Decay epsilon on a GLIE schedule |
| Very slow learning with sparse rewards | One-step credit assignment | Use SARSA(lambda) or reward shaping |
| Wrong next action in the update | a’ chosen after the update | Select a’ before updating Q(s, a) |
| Unstable values with deep networks | Correlated on-policy samples | Prefer actor-critic or PPO-style methods |
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.