14  SARSA

Core idea. SARSA is the basic on-policy temporal-difference control algorithm. It learns an action-value function while following the same policy that is being improved. The update uses one observed transition tuple

\[ (S_t,A_t,R_{t+1},S_{t+1},A_{t+1}), \]

which gives the algorithm its name:

\[ Q(S_t,A_t) \leftarrow Q(S_t,A_t)+\alpha \left[ R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t) \right]. \]

Unlike Q-learning, SARSA evaluates the action that the current behavior policy actually takes at the next state. This makes SARSA sensitive to exploration. Mathematically, it learns the value of the policy being followed, not only the value of the greedy policy that would be followed after learning.

14.1 Learning goals

After reading this chapter, students should be able to:

  1. define the on-policy control problem precisely;
  2. explain why action values \(Q(s,a)\) are central when the transition model is unknown;
  3. derive the SARSA update from the Bellman expectation equation for \(Q^\pi\);
  4. distinguish SARSA from Q-learning using conditional expectations;
  5. implement tabular SARSA with an \(\epsilon\)-greedy policy;
  6. explain the role of exploration in the learned value function;
  7. describe GLIE conditions for convergence intuition;
  8. compare SARSA and Expected SARSA;
  9. analyze cliff walking as a mathematical example of on-policy risk sensitivity;
  10. use AI tools to audit RL code without confusing on-policy and off-policy targets.

14.2 11.1 Why action values are needed for control

In the prediction problem, a policy \(\pi\) is fixed and the goal is to estimate

\[ V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s]. \]

For control, the policy is not fixed. The goal is to improve behavior. If the transition law \(P(s'\mid s,a)\) and reward function \(r(s,a)\) are known, then one can improve a policy using the one-step lookahead

\[ \sum_{s'}P(s'\mid s,a)\left[r(s,a,s')+\gamma V^\pi(s')\right]. \]

Without a model, this lookahead cannot be computed directly. The action-value function solves this problem by attaching value to state-action pairs:

\[ Q^\pi(s,a) = \mathbb E_\pi\left[G_t\mid S_t=s,A_t=a\right]. \]

Once \(Q^\pi\) is available, policy improvement can be performed without knowing the transition probabilities:

\[ \pi_{\mathrm{new}}(s)\in \arg\max_a Q^\pi(s,a). \]

Thus the transition from prediction to control is also a transition from state values to action values.

State values answer the question: how good is a state under a policy? Action values answer the control question: how good is an action in a state under a policy?

14.3 11.2 The Bellman equation for action values

For a fixed policy \(\pi\), the action-value function satisfies a Bellman expectation equation. Starting from \(S_t=s\) and \(A_t=a\), decompose the return as

\[ G_t=R_{t+1}+\gamma G_{t+1}. \]

Conditioning on the next state and next action gives

\[ Q^\pi(s,a) = \mathbb E\left[ R_{t+1}+\gamma Q^\pi(S_{t+1},A_{t+1}) \mid S_t=s,A_t=a \right], \]

where \(A_{t+1}\sim \pi(\cdot\mid S_{t+1})\). Written in finite-sum form, this is

\[ Q^\pi(s,a) = \sum_{s'}P(s'\mid s,a) \left[ r(s,a,s')+ \gamma\sum_{a'}\pi(a'\mid s')Q^\pi(s',a') \right]. \]

This equation has the same structure as the value Bellman equation, but the state space has been enlarged from states \(s\) to state-action pairs \((s,a)\).

Define the action-value Bellman operator

\[ (T^\pi_Q Q)(s,a) = \sum_{s'}P(s'\mid s,a) \left[ r(s,a,s')+ \gamma\sum_{a'}\pi(a'\mid s')Q(s',a') \right]. \]

Then \(Q^\pi\) is the unique fixed point of

\[ T^\pi_Q Q = Q. \]

With the supremum norm on state-action functions,

\[ \lVert Q\rVert_\infty=\max_{s,a}|Q(s,a)|, \]

\(T^\pi_Q\) is a \(\gamma\)-contraction:

\[ \lVert T^\pi_Q Q_1-T^\pi_Q Q_2\rVert_\infty \leq \gamma\lVert Q_1-Q_2\rVert_\infty. \]

This fixed-point result is the mathematical basis for both expected action-value iteration and sample-based SARSA.

14.4 11.3 From the Bellman equation to SARSA

Suppose we observe one transition under policy \(\pi\):

\[ S_t=s, \qquad A_t=a, \qquad R_{t+1}=r, \qquad S_{t+1}=s', \qquad A_{t+1}=a'. \]

The Bellman equation suggests the one-sample target

\[ Y_t^{\mathrm{SARSA}} = R_{t+1}+\gamma Q(S_{t+1},A_{t+1}). \]

The temporal-difference error for SARSA is

\[ \delta_t = R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t). \]

The tabular SARSA update is

\[ Q_{t+1}(s,a)= \begin{cases} Q_t(s,a)+\alpha_t\delta_t, & (s,a)=(S_t,A_t),\\ Q_t(s,a), & \text{otherwise}. \end{cases} \]

When the next state is terminal, the future value term is set to zero:

\[ \delta_t=R_{t+1}-Q(S_t,A_t). \]

14.4.1 Interactive: SARSA target and TD error

The SARSA target uses the next action that the current policy actually chooses. This figure compares the current estimate \(Q(s,a)\), the bootstrapped target, and the one-step update.

14.5 11.4 On-policy control

SARSA is called on-policy because the data-generating policy and the policy being evaluated are the same. At time \(t\), the agent has a current action-value table \(Q_t\). It defines a behavior policy \(\pi_t\), commonly \(\epsilon\)-greedy with respect to \(Q_t\):

\[ \pi_t(a\mid s)= \begin{cases} 1-\epsilon+\dfrac{\epsilon}{|\mathcal A(s)|}, & a\in\arg\max_b Q_t(s,b),\\ \dfrac{\epsilon}{|\mathcal A(s)|}, & \text{otherwise}. \end{cases} \]

If there are multiple maximizing actions, the greedy probability is usually split among them. The simplest implementation breaks ties randomly.

SARSA repeatedly performs two coupled operations:

  1. policy evaluation step: update \(Q_t\) toward the value of the current exploratory policy;
  2. policy improvement step: redefine \(\pi_t\) as an \(\epsilon\)-greedy policy with respect to the updated \(Q_t\).

This is a sample-based version of generalized policy iteration.

Tabular SARSA with an \(\epsilon\)-greedy policy

  1. Initialize \(Q(s,a)\) arbitrarily.
  2. For each episode:
    1. initialize \(S_0\);
    2. choose \(A_0\sim \epsilon\)-greedy\((Q,S_0)\);
    3. for \(t=0,1,2,\ldots\) until termination:
      1. take action \(A_t\);
      2. observe \(R_{t+1}\) and \(S_{t+1}\);
      3. choose \(A_{t+1}\sim \epsilon\)-greedy\((Q,S_{t+1})\);
      4. update

\[ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)\right]; \]

  5. set $S_t\leftarrow S_{t+1}$ and $A_t\leftarrow A_{t+1}$.

14.6 11.5 Expected update for fixed-policy SARSA

To see why SARSA is a legitimate stochastic approximation, temporarily freeze the policy \(\pi\). Conditional on \(S_t=s\) and \(A_t=a\),

\[ \mathbb E_\pi[\delta_t\mid S_t=s,A_t=a] = (T_Q^\pi Q)(s,a)-Q(s,a). \]

Thus SARSA is a noisy asynchronous fixed-point iteration for

\[ T_Q^\pi Q=Q. \]

For a changing \(\epsilon\)-greedy policy, the target operator changes over time because \(\pi_t\) changes with \(Q_t\). This makes the control analysis more delicate than fixed-policy prediction. The key intuition is that SARSA alternates between making \(Q_t\) more accurate for the current exploratory policy and making the policy more greedy with respect to \(Q_t\).

A common convergence framework uses GLIE conditions: greedy in the limit with infinite exploration.

A policy sequence \(\pi_t\) is GLIE if:

  1. every state-action pair continues to be visited infinitely often;
  2. the policy becomes greedy in the limit.

For example, one may use a decreasing exploration sequence satisfying

\[ \epsilon_t\downarrow 0 \]

while keeping enough exploration so that all relevant state-action pairs are sampled. With suitable learning rates,

\[ \sum_{t=0}^{\infty}\alpha_t(s,a)=\infty, \qquad \sum_{t=0}^{\infty}\alpha_t(s,a)^2<\infty, \]

and standard finite-MDP assumptions, tabular SARSA converges to an optimal action-value function in the limit. In finite-time practical learning, constant \(\epsilon\) and constant \(\alpha\) are often used, but then the algorithm tracks an exploratory policy rather than exactly converging to a deterministic optimal policy.

14.6.1 Interactive: On-policy target versus greedy target

SARSA uses the value of the next action sampled from the current policy. Q-learning uses the greedy next action. This distinction is small in deterministic safe problems but large in risky environments.

14.7 11.6 Expected SARSA

Expected SARSA replaces the sampled next action \(A_{t+1}\) by its conditional expectation under the current policy. The update target is

\[ Y_t^{\mathrm{ExpSARSA}} = R_{t+1}+\gamma\sum_{a'}\pi(a'\mid S_{t+1})Q(S_{t+1},a'). \]

The update is

\[ Q(S_t,A_t) \leftarrow Q(S_t,A_t)+\alpha \left[ R_{t+1}+\gamma\sum_{a'}\pi(a'\mid S_{t+1})Q(S_{t+1},a')-Q(S_t,A_t) \right]. \]

Expected SARSA removes randomness from the choice of \(A_{t+1}\) in the target, conditional on \(S_{t+1}\). It may have lower variance than SARSA, but it requires summing over all actions at the next state.

The three closely related targets are:

\[ \text{SARSA target:}\quad R_{t+1}+\gamma Q(S_{t+1},A_{t+1}), \]

\[ \text{Expected SARSA target:}\quad R_{t+1}+\gamma\sum_{a'}\pi(a'\mid S_{t+1})Q(S_{t+1},a'), \]

\[ \text{Q-learning target:}\quad R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a'). \]

The difference is not merely computational. It expresses three different mathematical objects: a sampled on-policy target, an expected on-policy target, and an off-policy optimality target.

14.8 11.7 A minimal finite MDP example in Python

The following example implements SARSA on a tiny MDP with three nonterminal states and two actions. The code is intentionally explicit so that the update can be inspected line by line.

import numpy as np

rng = np.random.default_rng(7339)

n_states = 4
terminal = 3
actions = [0, 1]
gamma = 0.9
alpha = 0.15
epsilon = 0.15

# Deterministic transition and reward model for simulation.
# Pairs map (state, action) to (next_state, reward).
model = {
    (0, 0): (1, 0.0),
    (0, 1): (2, 0.0),
    (1, 0): (3, 1.0),
    (1, 1): (0, 0.0),
    (2, 0): (0, 0.0),
    (2, 1): (3, 2.0),
}

def epsilon_greedy(Q, s, epsilon, rng):
    if rng.random() < epsilon:
        return int(rng.choice(actions))
    q = Q[s, actions]
    best = np.flatnonzero(q == q.max())
    return int(rng.choice(best))

Q = np.zeros((n_states, len(actions)))
returns = []

for episode in range(500):
    s = 0
    a = epsilon_greedy(Q, s, epsilon, rng)
    total = 0.0
    steps = 0

    while s != terminal and steps < 100:
        s_next, reward = model[(s, a)]
        total += (gamma ** steps) * reward

        if s_next == terminal:
            target = reward
            Q[s, a] += alpha * (target - Q[s, a])
            break

        a_next = epsilon_greedy(Q, s_next, epsilon, rng)
        target = reward + gamma * Q[s_next, a_next]
        Q[s, a] += alpha * (target - Q[s, a])
        s, a = s_next, a_next
        steps += 1

    returns.append(total)

print(np.round(Q, 3))
print("Greedy actions:", np.argmax(Q[:terminal], axis=1))
print("Average return over last 50 episodes:", round(np.mean(returns[-50:]), 3))
[[0.863 1.796]
 [1.    0.614]
 [1.343 2.   ]
 [0.    0.   ]]
Greedy actions: [1 0 1]
Average return over last 50 episodes: 1.721

This small example illustrates a central feature of tabular control: the transition model is used only to simulate experience. The learning update itself does not know \(P\) or \(r\).

14.9 11.8 Cliff walking and risk under exploration

The classic cliff-walking example shows why SARSA and Q-learning can learn different behavior when exploration remains active. Consider a grid. The start state is at the lower-left corner and the goal is at the lower-right corner. The cells between them form a cliff. Stepping into the cliff gives a large negative reward and sends the agent back to the start.

The shortest path goes close to the cliff. A greedy optimal policy for the deterministic environment may choose this path. But under an \(\epsilon\)-greedy behavior policy, there is always a chance of accidentally stepping into the cliff. SARSA evaluates the exploratory behavior policy, so it often learns a safer path farther from the cliff. Q-learning evaluates the greedy target policy, so it often learns the shortest risky path.

SARSA does not simply learn a worse solution. With persistent exploration, it learns values for the behavior that will actually be executed. In risky environments, this distinction is mathematically meaningful.

14.9.1 Interactive: Exploration level and learned action values

Increasing \(\epsilon\) changes the policy being evaluated. With more exploration, actions near risky states receive lower on-policy values.

The following Python example implements a compact cliff-walking environment.

import numpy as np

rng = np.random.default_rng(7340)

height, width = 4, 12
start = (3, 0)
goal = (3, 11)
cliff = {(3, c) for c in range(1, 11)}
action_names = ["U", "R", "D", "L"]
move = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def state_id(pos):
    return pos[0] * width + pos[1]

def step(pos, action):
    dr, dc = move[action]
    nr = min(max(pos[0] + dr, 0), height - 1)
    nc = min(max(pos[1] + dc, 0), width - 1)
    new_pos = (nr, nc)
    if new_pos in cliff:
        return start, -100.0, False
    if new_pos == goal:
        return new_pos, -1.0, True
    return new_pos, -1.0, False

def eps_greedy(Q, s, epsilon, rng):
    if rng.random() < epsilon:
        return int(rng.integers(4))
    q = Q[s]
    best = np.flatnonzero(q == q.max())
    return int(rng.choice(best))

def train_sarsa(episodes=600, alpha=0.5, gamma=1.0, epsilon=0.1):
    Q = np.zeros((height * width, 4))
    episode_returns = []
    for ep in range(episodes):
        pos = start
        s = state_id(pos)
        a = eps_greedy(Q, s, epsilon, rng)
        total = 0.0
        for t in range(1000):
            new_pos, reward, done = step(pos, a)
            total += reward
            s_next = state_id(new_pos)
            if done:
                target = reward
                Q[s, a] += alpha * (target - Q[s, a])
                break
            a_next = eps_greedy(Q, s_next, epsilon, rng)
            target = reward + gamma * Q[s_next, a_next]
            Q[s, a] += alpha * (target - Q[s, a])
            pos, s, a = new_pos, s_next, a_next
        episode_returns.append(total)
    return Q, episode_returns

Q_sarsa, ret_sarsa = train_sarsa()
print("Average return over last 50 episodes:", round(np.mean(ret_sarsa[-50:]), 2))

policy_symbols = []
for r in range(height):
    row = []
    for c in range(width):
        pos = (r, c)
        if pos == start:
            row.append("S")
        elif pos == goal:
            row.append("G")
        elif pos in cliff:
            row.append("C")
        else:
            row.append(action_names[int(np.argmax(Q_sarsa[state_id(pos)]))])
    policy_symbols.append(row)

for row in policy_symbols:
    print(" ".join(row))
Average return over last 50 episodes: -30.1
R R R R R R R R R R D D
U U R R U R U U U U R D
U L U U R U L R L L R D
S C C C C C C C C C C G

14.9.2 Interactive: Cliff walking intuition

The heatmap below gives a qualitative picture of safe and risky regions in cliff walking. SARSA tends to account for exploratory slips near the cliff.

14.10 11.9 Statistical interpretation

For MS Statistics students, it is helpful to view SARSA as recursive estimation of a conditional expectation. For fixed \(\pi\),

\[ Q^\pi(s,a) = \mathbb E_\pi\left[R_{t+1}+\gamma Q^\pi(S_{t+1},A_{t+1})\mid S_t=s,A_t=a\right]. \]

SARSA replaces this conditional expectation by a single observation. The update has the stochastic approximation form

\[ Q_{t+1}(S_t,A_t) = Q_t(S_t,A_t)+\alpha_t\left[h(Q_t;S_t,A_t)+M_{t+1}\right], \]

where the mean drift is approximately

\[ h(Q;s,a)=(T_Q^\pi Q)(s,a)-Q(s,a), \]

and \(M_{t+1}\) is a martingale-difference noise term under suitable filtration assumptions.

Several statistical issues appear immediately:

  • state-action pairs are not sampled iid;
  • the sampling distribution depends on the current policy;
  • the target depends on the current estimate \(Q_t\);
  • exploration controls both bias and variance of the learned policy;
  • rare but severe negative rewards can dominate practical performance.

These issues explain why empirical learning curves in RL often have high variability across random seeds.

14.11 11.10 SARSA, Expected SARSA, and Q-learning side by side

The following table summarizes the main target used by three action-value TD control methods.

Method Target Policy type
SARSA \(R_{t+1}+\gamma Q(S_{t+1},A_{t+1})\) on-policy sampled target
Expected SARSA \(R_{t+1}+\gamma\sum_{a'}\pi(a'\mid S_{t+1})Q(S_{t+1},a')\) on-policy expected target
Q-learning \(R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')\) off-policy greedy target

14.11.1 Interactive: SARSA, Expected SARSA, and Q-learning targets

For a fixed next-state action-value vector, the three targets can differ substantially depending on the policy’s exploration probability.

14.12 11.11 AI-assisted learning components

14.12.1 AI prompt: derive the update carefully

Ask an AI assistant:

Starting from the Bellman expectation equation for \(Q^\pi\), derive the SARSA update. Clearly state which conditional expectation is replaced by a single sample, and explain why the next action \(A_{t+1}\) is sampled from the same policy being evaluated.

A good answer should explicitly show the transition

\[ \mathbb E_\pi[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})\mid S_t=s,A_t=a] \quad\leadsto\quad R_{t+1}+\gamma Q(S_{t+1},A_{t+1}). \]

14.12.2 AI prompt: audit SARSA code

Ask an AI assistant to check whether the following errors occur in a SARSA implementation:

  1. using \(\max_{a'}Q(S_{t+1},a')\) instead of \(Q(S_{t+1},A_{t+1})\);
  2. choosing \(A_{t+1}\) after the update rather than before the target is formed;
  3. forgetting to set the future value term to zero at terminal states;
  4. treating \(\epsilon\)-greedy probabilities incorrectly when there are ties;
  5. evaluating performance using only the greedy policy when the learned behavior remains exploratory.

14.12.3 AI prompt: explain the cliff-walking difference

Ask:

In cliff walking, why does SARSA often learn a safer route than Q-learning when both use \(\epsilon\)-greedy exploration? Explain using the distinction between on-policy and off-policy Bellman targets.

A mathematically sound answer should mention that SARSA’s target includes the consequences of exploratory actions under the behavior policy, while Q-learning’s target uses the greedy action value.

14.13 11.12 Summary

SARSA is the first major TD control algorithm in the book. It combines:

  • action-value learning;
  • sample-based Bellman updates;
  • \(\epsilon\)-greedy exploration;
  • on-policy evaluation and improvement;
  • stochastic approximation.

The defining equation is

\[ Q(S_t,A_t) \leftarrow Q(S_t,A_t)+\alpha \left[ R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t) \right]. \]

The phrase on-policy means that the next action \(A_{t+1}\) is sampled from the same policy that generated the data and is being evaluated. This single detail explains the main conceptual difference between SARSA and Q-learning.

14.14 Exercises

14.14.1 Conceptual exercises

  1. Explain why SARSA needs action values rather than only state values.
  2. Explain why SARSA is on-policy.
  3. Compare the SARSA target and the Q-learning target in one sentence.
  4. In cliff walking, why can the shortest path be a poor on-policy choice under persistent exploration?
  5. Explain the difference between sampling \(A_{t+1}\) and averaging over \(A_{t+1}\).

14.14.2 Mathematical exercises

  1. Starting from the definition of \(Q^\pi(s,a)\), derive the Bellman expectation equation for action values.
  2. Prove that \(T_Q^\pi\) is a \(\gamma\)-contraction in the supremum norm.
  3. Show that Expected SARSA is obtained by taking the conditional expectation of the SARSA target with respect to \(A_{t+1}\sim\pi(\cdot\mid S_{t+1})\).
  4. For a two-action state with \(Q(s,0)=1\) and \(Q(s,1)=3\), compute the \(\epsilon\)-greedy action probabilities for \(\epsilon=0.2\).
  5. Derive the expected SARSA target for the values in Exercise 4 when \(\gamma=0.9\) and \(R_{t+1}=2\).

14.14.3 Computational exercises

  1. Modify the tiny MDP example so that rewards are stochastic. Compare learning curves over 20 random seeds.
  2. Implement Expected SARSA for the same tiny MDP and compare it with SARSA.
  3. Implement Q-learning and compare its learned policy with SARSA in cliff walking.
  4. Run cliff walking for \(\epsilon=0.01\), \(0.1\), and \(0.3\). Explain how the learned greedy path changes.
  5. Add a decaying exploration schedule \(\epsilon_t=1/(1+t/100)\) and plot the episode returns.

14.14.4 AI-assisted exercises

  1. Ask an AI assistant to generate SARSA pseudocode. Identify whether it accidentally gives Q-learning.
  2. Ask an AI assistant to explain GLIE. Then rewrite the explanation in terms of state-action visit counts.
  3. Ask an AI assistant to debug your cliff-walking code. Verify every suggested correction manually.
  4. Ask an AI assistant to compare SARSA and Expected SARSA. Require it to state the target equations.
  5. Ask an AI assistant to design a small MDP where on-policy and off-policy control behave differently. Then implement the example.

14.15 Notes for instructors

This chapter is a natural bridge from TD prediction to control. For MA Applied Math students, emphasize fixed points, contraction mappings, and stochastic approximation. For MS Statistics students, emphasize conditional expectation, non-iid sampling, exploration-driven data collection, and high-variance learning curves. The cliff-walking example is especially useful because it shows that the distinction between on-policy and off-policy methods is not cosmetic; it changes the mathematical object being estimated.

14.16 References

SARSA and related temporal-difference control methods are standard topics in reinforcement learning; see (sutton2018reinforcement?) and (szepesvari2010algorithms?). For dynamic programming and Markov decision process background, see (puterman1994markov?) and (bertsekas2012dynamic?).