Home / Curated / Algorithms / Sarsa

Sarsa

Algorithms AIMech:Sarsa DRAFT

Aliases: State-action-reward-state-action

An on-policy temporal-difference control algorithm that updates the current state-action value toward the observed reward plus the discounted estimated value of the next action selected by the same behavior policy.

Identity Notes & Concept Scope This record specifies one-step Sarsa through the tabular control formulation. The historical Modified Connectionist Q-Learning report supplies the selected-next-action target in a broader neural and eligibility-trace method; its lambda=0 case shares the one-step error, but the entire trace-based neural method is not made an exact alias of this record. Sarsa(lambda), expected Sarsa, Q-learning and GAE have distinct scopes. The available Cambridge PDF bears a September 1994 cover and already mentions Sutton’s proposed SARSA name in footnote 3; the later book draft credits the name to Sutton (1996). These source statements are preserved without resolving the naming chronology. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 298 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 20 and 20 lines respectively. All 17 unique hit contents were inspected: prior TD(lambda) and Q-routing leads, GAE and AntNet boundary statements, and their saved reports/reviews. These were references to methods rather than existing candidate records. Six exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and six native neighboring mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.

Claims & Grounded Evidence

1 Claim

Mechanism #method

Maintain Q(s,a), choose the current action A using the current policy derived from Q, execute it, and observe reward R and next state S_next. For a nonterminal next state, choose A_next from that same policy before updating, then set Q(S,A)=Q(S,A)+alpha*(R+gamma*Q(S_next,A_next)−Q(S,A)), using pre-update values. Carry the selected A_next forward as the next executed action; it is not replaced with a fresh sample after the update. For a terminal next state, the continuation value is zero and no next environment action is executed. Control improves the policy from Q while retaining its declared exploration rule, such as epsilon-greedy selection. The sample target uses the actual selected next action, not a maximum over actions and not an expectation over all policy actions. Rummery and Niranjan’s Eq.9 uses this error multiplied by an eligibility-weighted sum of neural-output gradients; at lambda=0 only the current gradient remains. That historical extension does not make neural networks or nonzero traces necessary for one-step tabular Sarsa.

supports Source: Reinforcement Learning: An Introduction · Locator: Section 6.4, PDF pp.155–156 / printed pp.137–138, Equation 6.7, terminal convention and Sarsa control pseudocode; bibliographical notes for Section 6.4, PDF p.166 / printed p.148
supports Source: On-Line Q-Learning Using Connectionist Systems · Locator: Section 3.2, PDF pp.7–8 / printed pp.6–7, Equation 9 and footnote 3; Section 4, PDF pp.8–10 / printed pp.7–9; Section 6.1, PDF p.17 / printed p.16; cover PDF p.1

⚠️ Curated Limitations & Negative Results

A persistently exploratory behavior policy changes the values being estimated; an exploratory next action can lower or raise the sampled target relative to another action. Greedy Sarsa and Q-learning can coincide on a transition, but such a special case does not equate the methods.
Convergence requires a specified setting, sampling policy and step-size assumptions. The inspected book draft attributes its tabular control convergence statement to personal communication, and the 1994 neural report discusses parameter sensitivity and missing general guarantees. Neither source is treated as an independently verified complete proof for arbitrary function approximation.
The September 2016 book draft is versioned as a draft. Its retrospective naming attribution differs from the SARSA footnote in the available 1994-covered report; no first-use date or explanation of that discrepancy is asserted.
Trace choice, replacing versus accumulating traces, n-step targets and expected backups define extensions requiring their own evidence. No robot-navigation or gridworld performance result is curated here.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:ReinforcementLearning` Reinforcement Learning	related_match	The inspected source defines Sarsa as an on-policy reinforcement-learning control algorithm. The pinned AIO class denotes the learning task rather than this particular action-value update, so the relation is neither equivalence nor an asserted algorithm-class hierarchy.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Reinforcement Learning: An Introduction Richard S. Sutton, Andrew G. Barto	author technical report full_text	ID: http://incompleteideas.net/book/bookdraft2016sep.pdf sha256:94b195c3d5f7…
`original-report`	On-Line Q-Learning Using Connectionist Systems G. A. Rummery, M. Niranjan	author technical report full_text	ID: CUED/F-INFENG/TR 166 sha256:c9434f056d17…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T14:02:32Z

Updated: 2026-10-11T14:02:32Z

Source File: data/curated/Sarsa.yaml