Expected SARSA

Why Does This Exist?

Temporal difference learning bootstraps: it updates a guess from another guess. SARSA builds its target from the exact next action the agent happened to sample:

Because $A_{t+1}$ is one random draw from an exploratory policy, this single sample injects noise into every update. Two identical visits to the same state can give wildly different targets: one step samples the good action, the next samples an exploratory blunder. To survive that noise you must shrink the learning rate, and learning crawls.

Q-learning dodges the noise by taking the greedy maximum, $\max_a Q(S_{t+1}, a)$. But that assumes perfect future play. In a risky environment where the agent keeps exploring, Q-learning ignores its own future blunders and can march straight into penalties it should have priced in.

Expected SARSA takes the middle path that keeps the honesty without the noise. Instead of rolling the dice on one sampled action, compute the exact average over every next action, weighted by the policy:

One draw becomes an expectation. The sampling noise disappears, but the exploratory risk stays in the price.

The one idea you need first: an $\epsilon$-greedy policy. With probability $1 - \epsilon$ it picks the current best action, and with probability $\epsilon$ it picks uniformly at random. So the best action gets probability $1 - \epsilon + \epsilon / |\mathcal{A}|$ and every other action gets $\epsilon / |\mathcal{A}|$.

Think of It Like This

How It Actually Works

Write $S_t$ for the state, $A_t$ for the action taken, $R_{t+1}$ for the reward, and $S_{t+1}$ for where you land. The update is:

Here $\alpha$ in $(0, 1]$ is the step size, $\gamma$ in $[0, 1)$ discounts the future, and $\pi(a \mid S_{t+1})$ is the probability of each next action under the target policy. The sum is the expected next value, $\mathbb{E}_{\pi}[Q(S_{t+1}, \cdot)]$.

Why the variance vanishes

Condition on the transition $(S_t, A_t, R_{t+1}, S_{t+1})$. Standard SARSA's target varies with the sampled action, so whenever the policy gives positive probability to actions with different values, its variance is positive:

Expected SARSA replaces the draw with its mean, and a mean has no sampling variance:

Only environment noise remains (random transitions and rewards). Lower variance means you can run a larger $\alpha$ without blowing up, which is why Expected SARSA converges faster than SARSA on tabular benchmarks.

One rule, two policies

Expected SARSA separates the behavior policy $b$ (what picks actions in the world) from the target policy $\pi$ (what the expectation uses). Set $\pi = b$ and you get on-policy control: with $\epsilon$-greedy behavior the expectation is $(1 - \epsilon) \max_a Q + (\epsilon / |\mathcal{A}|) \sum_a Q$. Set $\pi$ to pure greedy (probability 1 on the best action) and the sum collapses to $\max_a Q$: that is exactly Q-learning, with no importance sampling correction needed on the next action.

Worked example: the cliff state

The agent takes action East from $S_0$, lands in $S_1$, and gets reward $R = -1.0$. Settings: $\alpha = 0.5$, $\gamma = 0.9$, current $Q(S_0, \text{East}) = 2.0$. State $S_1$ has three actions:

• $a_1$ (safe path): $Q = 20.0$, the greedy action
• $a_2$ (detour): $Q = 10.0$
• $a_3$ (cliff edge): $Q = -100.0$

Behavior is $\epsilon$-greedy with $\epsilon = 0.3$ and $|\mathcal{A}| = 3$: $\pi(a_1) = 1 - 0.3 + 0.3/3 = 0.8$, $\pi(a_2) = 0.1$, $\pi(a_3) = 0.1$.

Expected SARSA first averages the next values:

$\mathbb{E}_\pi[Q(S_1, \cdot)] = 0.8 \times 20.0 + 0.1 \times 10.0 + 0.1 \times (-100.0) = 16.0 + 1.0 - 10.0 = 7.0$

Then the target, the error, and the update:

$Y^{\text{Exp}} = -1.0 + 0.9 \times 7.0 = 5.3, \quad \delta = 5.3 - 2.0 = 3.3$

$Q(S_0, \text{East}) \leftarrow 2.0 + 0.5 \times 3.3 = 3.65$

Compare. If SARSA samples the safe action: $Y = -1.0 + 0.9 \times 20.0 = 17.0$, so $Q \leftarrow 2.0 + 0.5 \times 15.0 = 9.5$. If it samples the cliff: $Y = -1.0 + 0.9 \times (-100.0) = -91.0$, so $Q \leftarrow 2.0 + 0.5 \times (-93.0) = -44.5$. Q-learning always takes the max: $Y = 17.0$ and $Q \leftarrow 9.5$. SARSA swings between $9.5$ and $-44.5$ on pure dice luck, Q-learning prices the cliff at zero despite a 10 percent fall chance, and Expected SARSA lands once, deterministically, at $3.65$.

Code

A pure-Python transcription of the worked example, with all three updates side by side.

1q_next = [20.0, 10.0, -100.0]2probs = [0.8, 0.1, 0.1]3reward = -1.04gamma = 0.95alpha = 0.56q_current = 2.07
8expected = sum(p * q for p, q in zip(probs, q_next))9target = reward + gamma * expected10updated = q_current + alpha * (target - q_current)11
12sarsa_safe = q_current + alpha * ((reward + gamma * q_next[0]) - q_current)13sarsa_cliff = q_current + alpha * ((reward + gamma * q_next[2]) - q_current)14qlearn = q_current + alpha * ((reward + gamma * max(q_next)) - q_current)15
16print(round(expected, 2))  # -> 7.017print(round(target, 2))  # -> 5.318print(round(updated, 2))  # -> 3.6519print(round(sarsa_safe, 2))  # -> 9.520print(round(sarsa_cliff, 2))  # -> -44.521print(round(qlearn, 2))  # -> 9.5

Watch Out For

The Quick Version

• Expected SARSA replaces the single sampled next action $Q(S_{t+1}, A_{t+1})$ with the policy-weighted mean $\sum_a \pi(a \mid S_{t+1}) Q(S_{t+1}, a)$.
• Killing action-sampling variance lets it train stably with larger step sizes than standard SARSA.
• The cliff example averages 20, 10 and $-100$ with weights 0.8, 0.1 and 0.1 to get 7.0, and updates $2.0$ to $3.65$ in one deterministic step.
• Setting the target policy to greedy reproduces Q-learning exactly, with no importance sampling correction.
• The price is a full pass over the action set per step, so huge or continuous action spaces need the split-sum trick or a sampled approximation.

What to Read Next

• Q-Learning vs SARSA in RL
• Q-Learning
• Temporal Difference Learning