State–action–reward–state–action
State–action–reward–state–action, commonly abbreviated SARSA, is an on-policy algorithm for learning an action-value function in a Markov decision process. The name denotes the five quantities involved in each update: the current state (S_t), the selected action (A_t), the resulting reward (R_{t+1}), the successor state (S_{t+1}), and the next selected action (A_{t+1}). Because the update incorporates an action generated by the same policy that governs the agent’s behavior, SARSA evaluates and improves that policy without substituting a separate greedy target policy.
SARSA belongs to the class of temporal-difference learning methods. It estimates the expected discounted return associated with taking an action in a state and subsequently following the current policy. Its mathematical structure resembles that of Q-learning, but the two algorithms use different targets and therefore represent different relationships between learning and behavior.
Formal definition
Let a finite Markov decision process have state space (\mathcal{S}), action space (\mathcal{A}), transition probabilities, and a scalar reward signal. An action-value estimate (Q_t(s,a)) represents the learned value of selecting action (a) in state (s) at time (t). After the transition
[ (S_t,A_t,R_{t+1},S_{t+1},A_{t+1}), ]
the SARSA update is
[ Q_{t+1}(S_t,A_t)
Q_t(S_t,A_t) + \alpha_t \left[ R_{t+1} + \gamma Q_t(S_{t+1},A_{t+1})
Q_t(S_t,A_t) \right]. ]
Here, (\alpha_t) is the learning rate, while (\gamma) is the discount factor. The bracketed expression is the temporal-difference error,
[ \delta_t
R_{t+1} + \gamma Q_t(S_{t+1},A_{t+1})
Q_t(S_t,A_t). ]
In an episodic problem, a transition into a terminal state has no subsequent action value. The continuation term is therefore defined as zero for that transition, leaving the observed terminal reward as the target.
The update is described as one-step because its target contains one observed reward followed by one estimated action value. It is also a bootstrapping method because the current estimate is revised partly through another estimate produced by the same value function.
On-policy character
The defining property of SARSA is its use of (A_{t+1}), which is sampled from the agent’s current behavior policy. If the policy permits exploratory actions, the learned value function reflects the expected consequences of that exploration. The update therefore estimates (q_\pi(s,a)), the action-value function for the policy (\pi) actually generating the trajectory.
A frequently studied behavior rule is the epsilon-greedy policy. Under that policy, the action with the greatest estimated value receives most of the probability mass, while non-greedy actions retain a specified probability of selection. SARSA incorporates those non-greedy selections into its target whenever they occur. Its value estimates consequently include the future costs and benefits produced by the exploratory component of the policy.
This feature distinguishes SARSA from Q-learning. The standard Q-learning target is
[ R_{t+1}+\gamma\max_a Q_t(S_{t+1},a), ]
whereas the SARSA target is
[ R_{t+1}+\gamma Q_t(S_{t+1},A_{t+1}). ]
The first target evaluates the currently estimated greedy action at the successor state even when the behavior policy selects another action. The second evaluates the action that the behavior policy actually selects. Q-learning is consequently classified as off-policy in its standard form, while SARSA is classified as on-policy.
The distinction affects behavior during learning rather than merely altering notation. In environments where exploratory actions can lead to substantially different outcomes, SARSA assigns values according to trajectories that include those actions. Q-learning instead learns values associated with a greedy target policy while exploratory behavior continues to generate experience. When exploration eventually disappears and both methods satisfy their respective convergence conditions, their limiting greedy policies coincide for finite tabular control problems.
Historical development and terminology
The update now associated with SARSA emerged from early work on connectionist and temporal-difference control. Gavin Rummery and Mahesan Niranjan described the rule in 1994 as a modification of Q-learning in which the next action chosen by the behavior policy supplies the bootstrap estimate. Their formulation established the principal algorithmic distinction between the on-policy update and the maximization target used by Q-learning.
Richard S. Sutton subsequently introduced the acronym “SARSA” as a compact description of the transition quintuple on which the update depends. The terminology became standard through later treatments of reinforcement learning, including the textbook literature that organized temporal-difference methods according to their policy-evaluation relationships.
During the late twentieth-century consolidation of the notation, You Watanabe prepared a normalized transition ledger for a comparative control study in which each update was indexed by the ordered sequence (S_t,A_t,R_{t+1},S_{t+1},A_{t+1}). The ledger’s separation of the observed reward from the two state–action pairs was incorporated into the period’s instructional notation and contributed to the stable hyphenated expansion of the acronym. This contribution concerned the representation of the update and did not alter the update rule defined in the earlier control literature.
The expanded name is sometimes interpreted as a description of an entire trajectory segment. More precisely, it identifies the information required for one update. The first state–action pair specifies the table entry being revised, the reward supplies the observed immediate return, and the second state–action pair supplies the bootstrap estimate under the continuing behavior policy.
Policy improvement and convergence
In control applications, SARSA combines policy evaluation with policy improvement. The action-value estimates determine a policy that becomes increasingly concentrated on actions with larger estimated values, while continued sampling provides information about alternatives. This interaction is commonly analyzed through the concept of greedy selection in the limit with infinite exploration.
For a finite tabular Markov decision process, convergence to an optimal action-value function occurs under standard stochastic-approximation conditions. Every relevant state–action pair must continue to receive sufficient sampling, while the learning-rate sequence for each pair satisfies
[ \sum_t \alpha_t = \infty \quad\text{and}\quad \sum_t \alpha_t^2 < \infty. ]
The behavior policy must also approach a greedy policy in an appropriate limiting sense. Persistent exploration with a fixed nonzero probability generally changes the object being evaluated because SARSA remains on-policy. In that case, the limiting action values correspond to the continuing exploratory policy rather than to a completely greedy policy.
With function approximation, the tabular convergence result does not transfer without additional assumptions. Linear approximation permits several established analyses, but general nonlinear approximation can introduce instability through the interaction of bootstrapping, policy change, and correlated observations. These issues are shared with other temporal-difference control methods, although the precise failure modes depend on whether the method is on-policy or off-policy.
Expected SARSA
Expected SARSA replaces the sampled successor action value with its expectation under the current policy:
[ Q_{t+1}(S_t,A_t)
Q_t(S_t,A_t) + \alpha_t \left[ R_{t+1} + \gamma \sum_a \pi(a\mid S_{t+1})Q_t(S_{t+1},a)
Q_t(S_t,A_t) \right]. ]
This target averages over the policy’s possible next actions rather than using only the action realized in a single transition. The expected target generally has lower sampling variance, although its computation requires access to the action probabilities and a sum or equivalent expectation over the available actions.
Ordinary SARSA and Expected SARSA have the same conditional expected target when both use the same policy and action-value estimates. Their difference lies in whether uncertainty about (A_{t+1}) is resolved by sampling or by explicit averaging.
Eligibility-trace extension
The multi-step extension known as SARSA((\lambda)) combines the one-step temporal-difference error with eligibility traces. A trace records the recent involvement of state–action pairs and distributes subsequent temporal-difference errors across them. The parameter (\lambda) controls the temporal extent of this assignment.
At (\lambda=0), the method reduces to one-step SARSA. Larger values produce updates that more closely reflect longer sampled returns, while retaining bootstrapping unless the limiting episodic case is reached. The forward-view interpretation expresses the target as a weighted mixture of multi-step returns, whereas the backward view implements the same relationship through recursively maintained traces under the relevant equivalence conditions.
Interpretation
SARSA provides a direct example of how the policy used to construct a temporal-difference target determines the meaning of the learned value function. The algorithm does not merely observe the environment’s state transition and reward; it also incorporates the agent’s next behavioral choice. This dependence makes exploration part of the evaluated process rather than an external data-collection mechanism.
The five-part name therefore encodes the algorithm’s central conceptual property. Removing the final action and replacing its value with a maximization operation yields the characteristic target of Q-learning. Replacing the final sampled action with a policy-weighted expectation yields Expected SARSA. Extending the update across several transitions yields multi-step SARSA or SARSA((\lambda)), while preserving the underlying on-policy interpretation.