SARSA: On-Policy TD Control

In reinforcement learning, control means finding a good policy, as opposed to prediction, which means evaluating a given policy's value function. SARSA solves the control problem by interleaving two ideas: (1) TD-style bootstrapped estimation of an action-value function $Q(s,a)$, and (2) generalized policy iteration, where the policy is improved greedily (or $\varepsilon$-greedily) with respect to the current $Q$ estimate while the estimate itself is being updated from experience generated by that same improving policy. Formally, the agent observes a stream of experience $S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, \dots$ At each step it has a quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ — this is the origin of the name SARSA. The update rule is

where $\alpha \in (0,1]$ is the step size and $\gamma \in [0,1]$ is the discount factor. The bracketed term is the TD error $\delta_t$, measuring the discrepancy between the current estimate $Q(S_t,A_t)$ and the one-step bootstrapped target $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$. The crucial detail is that $A_{t+1}$ is sampled from the agent's actual behavior policy (typically $\varepsilon$-greedy with respect to the current $Q$), not chosen to maximize $Q(S_{t+1}, \cdot)$. This makes SARSA's update target an unbiased (in expectation, given the behavior policy) sample of the value of the policy being executed, so SARSA is evaluating and improving one and the same policy — the defining feature of on-policy learning. Contrast this with Q-learning's target $R_{t+1} + \gamma \max_a Q(S_{t+1}, a)$, which estimates the value of the greedy policy regardless of what action is actually taken next; that decoupling of target-policy from behavior-policy is what makes Q-learning off-policy. Because the policy used to generate actions is derived from the same $Q$ that is being updated, and because that policy is continually improving (assuming $\varepsilon$-greedy or similar), SARSA performs a data-driven, sample-based version of generalized policy iteration: partial policy evaluation via the TD update, interleaved step-by-step with partial policy improvement via the greedy/$\varepsilon$-greedy action selection.

SARSA operates episode by episode (or continuously, for non-terminating tasks), maintaining a table (or function approximator) $Q(s,a)$ for all state-action pairs. At the start of each episode, an initial action is chosen from the initial state using the current policy; then, at every step, the next action is chosen before the update is applied, so that it can be plugged directly into the TD target. ``` Algorithm: SARSA (on-policy TD control), tabular version Input: step size α ∈ (0,1], exploration rate ε ∈ (0,1], discount γ ∈ [0,1] Initialize: Q(s, a) ← arbitrary values for all s, a # e.g. 0, or optimistic value Q(terminal, ·) ← 0 for each episode: S ← initial state of episode A ← action chosen from S using policy derived from Q (e.g. ε-greedy: with prob ε pick random action, else pick argmax_a Q(S,a)) loop for each step of episode: take action A, observe reward R and next state S' if S' is terminal: A' ← undefined target ← R else: A' ← action chosen from S' using policy derived from Q # ε-greedy target ← R + γ Q(S', A') δ ← target − Q(S, A) Q(S, A) ← Q(S, A) + α δ S ← S' A ← A' if S is terminal: break

# policy is implicitly improved every step since it is ε-greedy wrt current Q ``` Two implementation details deserve emphasis. First, the next action $A'$ must be selected before the update, using the current (not-yet-updated) $Q$, and it is this same $A'$ that both gets plugged into the TD target and gets executed on the following iteration — there is no re-sampling. Second, terminal states are handled by defining $Q(\text{terminal}, \cdot) = 0$, so the target collapses to just the reward $R$, correctly terminating the bootstrap chain. The policy used for action selection is usually $\varepsilon$-greedy: with probability $1-\varepsilon$ pick $\arg\max_a Q(s,a)$, and with probability $\varepsilon$ pick a uniformly random action. This guarantees continual exploration, which is essential both to visit all state-action pairs infinitely often (needed for convergence) and to make the on-policy target actually reflect exploratory behavior.

Time and space complexity. In the tabular setting with $|\mathcal{S}|$ states and $|\mathcal{A}|$ actions, SARSA stores a $Q$-table of size $O(|\mathcal{S}| \cdot |\mathcal{A}|)$. Each step performs $O(1)$ work: one table lookup for $Q(S_{t+1}, A_{t+1})$, one arithmetic update, and one $\varepsilon$-greedy action selection, which costs $O(|\mathcal{A}|)$ to find the greedy action by scanning (or $O(1)$ amortized with a cached max). Over an episode of length $T$, total work is $O(T \cdot |\mathcal{A}|)$; over $N$ episodes, $O(N \cdot T \cdot |\mathcal{A}|)$. This is asymptotically identical to Q-learning and to TD(0) prediction — SARSA adds no algorithmic overhead over plain TD, only the bookkeeping of carrying $A_{t+1}$ forward as $A_t$ for the next iteration. With function approximation (e.g., a neural network estimating $Q_\theta(s,a)$), each update costs one forward and backward pass, $O(|\theta|)$, replacing the table lookup — this is the basis of SARSA-style deep RL variants, though Q-learning-style off-policy methods (DQN and successors) are far more common in that regime because they permit experience replay, which is explored in Q-Learning: Off-Policy TD Control.

Correctness (convergence argument). SARSA is proven to converge to the optimal action-value function $Q^*$ (and hence an optimal policy) under the following conditions, established by Singh, Jaakkola, Littman, and Szepesvári (1999-2000) building on stochastic approximation theory: 1. Every state-action pair is visited infinitely often. This ensures the estimate $Q(s,a)$ receives infinitely many updates for every pair, which is necessary for any sample-based estimate to converge. 2. The policy converges to the greedy policy in the limit (GLIE — Greedy in the Limit with Infinite Exploration). A standard way to satisfy both (1) and (2) is $\varepsilon$-greedy with $\varepsilon_t \to 0$, e.g. $\varepsilon_t = 1/t$, which explores infinitely often early on but eventually acts greedily. 3. Robbins-Monro step-size conditions: $\sum_t \alpha_t(s,a) = \infty$ and $\sum_t \alpha_t(s,a)^2 < \infty$ for every state-action pair, ensuring updates are large enough to overcome any initialization but small enough to eventually stabilize (a constant $\alpha$ violates the second condition and yields convergence only to a neighborhood of $Q^*$, useful for non-stationary problems but not exact convergence). Under these conditions, the sequence of $(Q_t, \pi_t)$ pairs performs a stochastic approximation of policy iteration: because the policy is GLIE, the TD target's expectation converges to the Bellman optimality operator's action, i.e.

as $t \to \infty$, since $\pi_t$ becomes greedy with respect to $Q_t$ and $Q_t \to Q^*$. Intuitively: SARSA is always evaluating the current policy $\pi_t$ (an on-policy fixed point for whatever $\pi_t$ currently is), but because $\pi_t$ is simultaneously being pulled toward greedy-in-$Q_t$, the moving target and the moving estimate co-converge to the fixed point of the Bellman optimality equation, $Q^* = \mathcal{T}^* Q^*$. This is a genuinely different proof structure from Q-learning, where convergence follows more directly from $\mathcal{T}^*$ being a contraction under any behavior policy that guarantees sufficient exploration — SARSA's proof must additionally track the policy's convergence to greediness.

Honest tradeoffs. SARSA's convergence guarantee is asymptotic and requires $\varepsilon \to 0$; in practice with fixed small $\varepsilon$, SARSA converges to the value function of the $\varepsilon$-greedy policy, not the fully optimal deterministic policy — it is evaluating the policy it runs, exploration included, which is exactly the point but means its "optimal" policy is optimal-subject-to-continued-exploration. This makes SARSA naturally more risk-aware near catastrophic states, at the cost of typically slower and sometimes lower asymptotic performance if the environment truly permits a risk-free optimal policy.

Consider a minimized cliff-walking-style corridor: states $\{S_0, S_1, S_2, S_G\}$ in a line, with $S_G$ terminal (goal, reward $+10$ then episode ends), and a cliff action from $S_1$ that leads to $S_{\text{fall}}$ (terminal, reward $-10$). From each non-terminal state the agent picks between action R (move right, safely, reward $-1$) and action C (only available at $S_1$: attempt a risky cliff shortcut, reward $-10$ if it falls, but let's say with probability governed by exploration it's occasionally chosen). We use $\alpha = 0.5$, $\gamma = 1$, $\varepsilon = 0.1$, and initialize all $Q(s,\cdot) = 0$. Suppose one training episode produces this trajectory (actions chosen $\varepsilon$-greedily, with the shown random draws having selected the risky action once for illustration):

Update at $t=1$ (terminal next state, so target is just the reward):

Update at $t=0$ uses the actual next action $A_1 = C$, even though it turned out to be the risky one:

Note the crucial contrast: Q-learning, observing the same transition from $S_0$, would have used $\max_a Q(S_1,a)$ instead of $Q(S_1, C)$. If the safe action's value $Q(S_1,R)$ were already, say, $-1$ from earlier learning, Q-learning's update would be $0.5[-1 + \max(-1, 0)] = 0.5[-1+0]=-0.5$ — much less pessimistic, because Q-learning assumes the agent will not actually take the risky action next time, even though during training it sometimes will. SARSA's estimate at $S_0$ is dragged down because it correctly accounts for the fact that, under the current $\varepsilon$-greedy policy, sometimes the agent really does wander into the cliff action next. Over many episodes this systematically teaches SARSA to prefer routes that stay farther from the cliff, while Q-learning's greedy-target learns the objectively shortest path and can appear reckless during training (frequently falling off) even though its final greedy policy, once exploration is turned off, would be optimal.

:::warning[Silently swapping SARSA's target for Q-learning's target is the single most common implementation bug — and it changes the algorithm's fundamental behavioral character, not just a minor detail. Writing `max(Q[S_next])` where the algorithm calls for `Q[S_next][A_next]` turns an on-policy, exploration-aware learner into an off-policy one, which can make an agent appear to work fine in simulation yet behave far more recklessly than expected once deployed with real exploration noise, exactly the cliff-walking discrepancy shown above.]

SARSA's name and tabular convergence analysis were popularized in the classic reinforcement learning textbook tradition associated with Richard Sutton, though the algorithm itself was first described by Gavin Rummery and Mahesan Niranjan in a 1994 technical report on "online Q-learning using connectionist systems" — where it was originally called "Modified Connectionist Q-Learning" before the SARSA acronym, coined by Rich Sutton, took hold.

SARSA and its on-policy philosophy underpin systems where the deployed policy's exploration behavior has real consequences during learning, not just at test time. In robotics, on-policy TD control (and its policy-gradient cousins) is preferred for physical systems where an off-policy method's assumption of eventual pure-greedy behavior can be dangerously optimistic mid-training. In classic control benchmarks — grid worlds, cliff-walking, mountain car — SARSA remains the standard teaching baseline for demonstrating the behavioral gap between on-policy and off-policy TD control. Its extensions, SARSA($\lambda$) with eligibility traces and Expected SARSA (which replaces the sampled $Q(S_{t+1},A_{t+1})$ with an expectation over the policy's action distribution to reduce variance), are used in production-grade RL libraries as lower-variance alternatives when full off-policy correction is unnecessary or undesirable. The on-policy vs. off-policy distinction that SARSA crystallizes also directly informs the design of modern deep-RL algorithms, including why methods like PPO and A2C (on-policy) and DQN/SAC (off-policy) trade off differently between sample efficiency, stability, and safety — a lineage traceable back to the SARSA-versus-Q-learning contrast.

Ask the tutor: How would the SARSA update rule and its convergence guarantees change if we used a fixed constant step size instead of a decaying one, and why might that be a deliberate design choice in non-stationary environments?