Expected SARSA
Imagine training an agent to navigate a cliff-edge gridworld with an epsilon-greedy policy. SARSA learns cautiously, hugging the safe path. This is because it accounts for the exploration noise baked into its own action choices. Q-learning learns the risky optimal path but its updates swing wildly. This happens because a single unlucky random action can drag the target value far from what the greedy policy would actually experience. Both algorithms sample the next action and then use its value. That sampling step injects variance into every single update. This slows learning and destabilizes training in noisy or stochastic environments. Expected SARSA fixes this by removing the sample. Instead of asking "what value did the next action we happened to draw have?", it asks a different question. It asks "what value do we expect, averaged exactly over the policy's action distribution?" This single change replaces a stochastic next-action sample with its exact expectation. This turns out to unify SARSA and Q-learning as special cases. It generally outperforms both in practice. The cost is modest: one extra sum over the action space per update. This matters far beyond toy gridworlds. Any system that learns action-values online inherits target variance from the SARSA/Q-learning update rule. This includes recommendation engines doing bandit-style exploration, robotic controllers using epsilon-greedy exploration, or off-policy evaluation pipelines. Reducing that variance without introducing bias has a direct benefit. It means fewer environment interactions are needed to reach a given performance level. That is often the scarcest resource in real-world reinforcement learning. This article gives you the precise update rule. It offers a full step-by-step derivation of why it interpolates between SARSA and Q-learning. It also provides a worked numeric trace showing the variance reduction directly. Finally, it gives an honest complexity accounting of the extra cost incurred per step. It builds directly on SARSA: On-Policy TD Control and Q-Learning: Off-Policy TD Control. It also sets up the variance-vs-bias tradeoffs revisited in n-Step Bootstrapping Methods.
- Expected SARSA replaces the sampled next-action value in the TD target with an exact expectation over the current policy's action distribution.
- The update is: add the expected value under the behavior/target policy instead of `Q(S', A')` for a sampled `A'`.
- It strictly reduces the variance of the TD target relative to SARSA, without changing its expected value — a free variance reduction.
- It can run on-policy (like SARSA) or off-policy (like Q-learning), because Q-learning is the special case where the expectation collapses to a max over a greedy target policy.
- Per-step cost rises from `O(1)` to `O(|A|)` due to the sum over actions, which is usually negligible compared to environment interaction cost.
- Empirically, Expected SARSA dominates SARSA at the same step size, and often matches or beats Q-learning, especially with larger step sizes and higher exploration noise.
Expected SARSA replaces a sampled next action with the exact expectation over next-action values, eliminating sampling variance from the TD target while leaving its expected update unchanged.
The idea
In temporal-difference control, every update moves an action-value estimate `Q(S, A)` toward a target: a bootstrapped estimate of the true return. SARSA's target is ``` R + γ Q(S', A') ``` where `A'` is sampled from the current policy `π(·|S')` — typically `ε`-greedy with respect to `Q`. That sampling step is the source of a subtle problem: `A'` is a random variable, so the target itself is noisy even if `Q` were exact. Two different rollouts from the same `(S, A, R, S')` can produce different targets purely because a different `A'` happened to be drawn, and this extra randomness is pure noise — it carries no additional information about the environment's dynamics or reward structure.
Expected SARSA removes this specific source of noise by replacing the sampled `Q(S', A')` with its expectation under the policy used at state `S'`: ``` E_π[Q(S', A') | S'] = Σ_a π(a|S') Q(S', a) ``` The update rule becomes ``` Q(S, A) ← Q(S, A) + α [ R + γ Σ_a π(a|S') Q(S', a) − Q(S, A) ] ``` Everything else — the state transition sample `S'`, the reward sample `R`, the step size `α`, the bootstrapping structure — is identical to SARSA. Only the next-action term is de-randomized by summing exactly rather than sampling. This single substitution unifies several algorithms you already know. If `π` is the deterministic greedy policy (`π(a|S') = 1` for `a = argmax_a Q(S', a)`), the sum collapses to `max_a Q(S', a)`, and Expected SARSA becomes exactly Q-Learning: Off-Policy TD Control. If instead you use the same `ε`-greedy behavior policy inside the expectation that generated the trajectory, Expected SARSA is an on-policy method in the spirit of SARSA: On-Policy TD Control, but with the sampling noise in the target removed. This is why Expected SARSA is sometimes described as a strict generalization: it can be run on-policy (target policy = behavior policy) or off-policy (target policy = greedy, behavior policy = exploratory), simply by choosing which distribution `π` appears inside the expectation.
How it works
The mechanics of Expected SARSA mirror SARSA almost line for line — the only structural change is computing an expectation over the action set instead of using a sampled next action. Because the next action is never actually needed for the update (only its distribution and the `Q`-values), the algorithm does not need to select `A'` before updating, though it still must select and execute an action to continue the episode. ``` Algorithm: Expected SARSA (on-policy control) Input: step size α ∈ (0, 1] exploration parameter ε (for ε-greedy policy) discount factor γ ∈ [0, 1] number of episodes N Initialize Q(s, a) arbitrarily for all s, a; Q(terminal, ·) = 0 for episode = 1 to N: initialize S choose A from S using policy derived from Q (e.g., ε-greedy) repeat until S is terminal: take action A, observe reward R and next state S'
# --- the key step: expectation, not a sample --- expected_value ← 0 for each action a in A(S'): expected_value ← expected_value + π(a | S') * Q(S', a)
# π is ε-greedy w.r.t. Q:
# π(a | S') = 1 - ε + ε/|A(S')| for the greedy action a
# π(a | S') = ε/|A(S')| for every other action target ← R + γ expected_value Q(S, A) ← Q(S, A) + α (target − Q(S, A)) choose A' from S' using policy derived from Q (e.g., ε-greedy) S ← S' A ← A' ``` Two implementation notes matter in practice. First, ties in the greedy action must be broken consistently between the policy used to act and the policy used inside the expectation, otherwise the expectation is computed for a slightly different policy than the one actually generating behavior — this introduces a subtle bias in on-policy variants. Second, the inner loop over actions is only over the feasible actions at `S'`; in environments with large or continuous action spaces this sum is intractable and Expected SARSA is typically restricted to small, discrete action sets or approximated (e.g., via the induced expectation of a parametric policy). The off-policy variant simply changes which distribution is used in the sum: ``` Algorithm: Expected SARSA (off-policy control, target policy greedy) ... identical to above, except: expected_value ← max_a Q(S', a) # π_target is greedy target ← R + γ expected_value Q(S, A) ← Q(S, A) + α (target − Q(S, A))
# action selection for continuing the episode still uses
# the exploratory behavior policy, e.g. ε-greedy ``` Notice this is exactly the Q-learning update — confirming that Q-learning is the degenerate, zero-entropy case of Expected SARSA's target policy.
Complexity & correctness
Per-step time complexity. SARSA and Q-learning perform an update in `O(1)` time (excluding action selection), since the target uses a single `Q(S', A')` lookup. Expected SARSA must compute `Σ_a π(a|S') Q(S', a)`, a sum over all `|A|` actions at state `S'`. This raises the per-update cost to `O(|A|)`. For an episode of length `T` this gives a total of `O(T · |A|)` instead of `O(T)`. In most tabular or small-discrete-action settings (`|A|` in the tens), this is negligible compared to the cost of interacting with the environment. In large or continuous action spaces the sum becomes the dominant cost or intractable, which is the main practical limitation of the method — this is the honest tradeoff for the variance reduction.
Space complexity. Identical to SARSA and Q-learning: `O(|S| · |A|)` to store the action-value table, since Expected SARSA introduces no new persistent data structures — it changes only how a target is computed at update time.
Correctness — target is unbiased and has lower variance. Let `A'` denote SARSA's sampled next action distributed according to `π(·|S')`, and let `Q` be fixed (held constant while examining a single update, as is standard in TD analysis). Define the two random targets ``` G_SARSA = R + γ Q(S', A'), A' ~ π(·|S') G_ExpSARSA = R + γ Σ_a π(a|S') Q(S', a) ``` Note that `G_ExpSARSA` is a deterministic function of `S'` and `R` (no residual randomness from action choice), while `G_SARSA` is random through `A'`. Taking expectations over `A'`: ``` E_{A'}[G_SARSA] = R + γ E_{A'}[Q(S', A')] = R + γ Σ_a π(a|S') Q(S', a) = G_ExpSARSA ``` So Expected SARSA's target equals the conditional expectation of SARSA's target given `(S, A, R, S')`. By the law of total variance, ``` Var(G_SARSA) = Var(E[G_SARSA | S']) + E[Var(G_SARSA | S')] = Var(G_ExpSARSA) + E[Var(G_SARSA | S')] ≥ Var(G_ExpSARSA) ``` since the second term is a variance and therefore non-negative. This proves Expected SARSA's target has variance less than or equal to SARSA's, with strict inequality whenever `Q(S', ·)` is not constant across actions with positive probability under `π` (i.e., whenever the sampled next action actually matters). Crucially, the two targets have the same mean, so this variance reduction is not a bias-variance tradeoff — it is a Rao–Blackwellization: replacing a random variable by its conditional expectation given more information (here, given `S'` and the full policy, rather than given a single realized draw).
Convergence. Under the standard stochastic approximation conditions — the Robbins–Monro step-size schedule (`Σ α_t = ∞`, `Σ α_t^2 < ∞`), all state-action pairs visited infinitely often, and bounded rewards — Expected SARSA converges to the true action-value function of the policy being evaluated, by the same general TD fixed-point argument used for SARSA and Q-learning (contraction of the Bellman expectation or optimality operator in expectation, combined with the Robbins–Monro theorem for stochastic approximation of a fixed point). Because Expected SARSA's target is an unbiased, lower-variance estimator of the same Bellman backup that SARSA and Q-learning use, it converges under no additional assumptions beyond those already required for SARSA, and empirically converges faster in the sense of requiring fewer episodes to reach a given estimation error, precisely because each individual update is more informative (lower variance means less noise is injected into `Q` at every step).
Tradeoff, stated honestly. The variance reduction is not free: it costs `O(|A|)` instead of `O(1)` per update. When `|A|` is large — or the action space is continuous, requiring a costly integral or Monte-Carlo approximation of the expectation — this overhead can outweigh the benefit, and vanilla SARSA or Q-learning (or Expected SARSA with a Monte-Carlo approximation of the sum) may be preferable.
Worked example
Consider a single state `S'` with three actions and current estimates ``` Q(S', a₁) = 2.0 Q(S', a₂) = 6.0 Q(S', a₃) = 4.0 ``` with `ε = 0.3` (so `ε/|A| = 0.1` per non-greedy action) and the greedy action being `a₂` (highest value). The `ε`-greedy policy is ``` π(a₁|S') = 0.1 π(a₂|S') = 1 − 0.3 + 0.1 = 0.8 π(a₃|S') = 0.1 ``` Suppose `R = 1`, `γ = 0.9`.
SARSA (sampled). Over many independent draws of `A' ~ π(·|S')`, the target `R + γQ(S', A')` takes one of three values:
| Sampled A' | Probability | Q(S′,A′) | Target R+γQ(S′,A′) |
|---|---|---|---|
| a₁ | 0.1 | 2.0 | 1 + 0.9(2.0) = 2.80 |
| a₂ | 0.8 | 6.0 | 1 + 0.9(6.0) = 6.40 |
| a₃ | 0.1 | 4.0 | 1 + 0.9(4.0) = 4.60 |
The realized target on any given step is one of `{2.80, 6.40, 4.60}`, chosen randomly. Its mean and variance (over the randomness in `A'`, with `R`, `S'`, `Q` fixed) are: ``` E[target] = 0.1(2.80) + 0.8(6.40) + 0.1(4.60) = 0.28 + 5.12 + 0.46 = 5.86 ``` ``` Var(target) = 0.1(2.80−5.86)² + 0.8(6.40−5.86)² + 0.1(4.60−5.86)² = 0.1(9.3636) + 0.8(0.2916) + 0.1(1.5876) = 0.93636 + 0.23328 + 0.15876 = 1.3284 ```
Expected SARSA (summed). The target is computed once, deterministically: ``` Σ_a π(a|S') Q(S',a) = 0.1(2.0) + 0.8(6.0) + 0.1(4.0) = 0.2 + 4.8 + 0.4 = 5.4 target = R + γ · 5.4 = 1 + 0.9(5.4) = 1 + 4.86 = 5.86 ``` The Expected SARSA target is exactly 5.86, matching the mean of SARSA's target precisely (as the correctness argument predicts), but with zero variance across repeated visits to the same `(S, A, R, S')` — compared to SARSA's variance of `1.3284`. Every single update to `Q(S,A)` under Expected SARSA moves toward this same value `5.86`; under SARSA, updates thrash between `2.80`, `6.40`, and `4.60` depending on which action got sampled, even though `Q(S', ·)` never changes. This is the concrete mechanism behind Expected SARSA's empirically smoother learning curves.
Common pitfalls & traps
| Pitfall | Why it happens | Fix | ||||
|---|---|---|---|---|---|---|
| Using different `ε` (or different policies) for acting vs. the expectation | Breaks the on-policy guarantee; the target no longer matches the policy generating data | Use identical `π` for behavior and for the expectation in on-policy mode | ||||
| Assuming Expected SARSA is always cheaper or always better | The `O( | A | )` sum can dominate cost with large action spaces; benefit shrinks when `Q(S',·)` is nearly uniform | Profile against ` | A | `; fall back to sampled SARSA/Q-learning when action space is large |
| Forgetting tie-breaking consistency in the greedy action | Different tie-breaks between acting policy and expectation policy silently bias the on-policy target | Fix a deterministic tie-break rule (e.g., lowest index) used everywhere | ||||
| Confusing Expected SARSA with Q-learning | Q-learning is a special case (deterministic greedy target policy), not identical in general | Check whether the target policy inside the expectation is stochastic (ε-greedy) or deterministic (greedy) | ||||
| Applying the exact sum to continuous action spaces | The sum becomes an intractable integral | Approximate with Monte-Carlo samples from `π`, or use a policy with closed-form expectation (e.g., Gaussian) |
Pioneers & history
Expected SARSA emerged from the broader lineage of temporal-difference control methods developed to unify and improve on SARSA and Q-learning. It was formally analyzed and popularized as a distinct algorithm by Harm van Seijen and colleagues, who proved the variance-reduction property and demonstrated its empirical advantages across a range of control tasks, situating it explicitly as a generalization bridging on-policy and off-policy TD control.
Origins · 1 minRichard S. Sutton and how this was discovered
Sutton's foundational work on TD methods, alongside Andrew Barto, established the SARSA/Q-learning family of control algorithms whose target-construction tradeoffs — sampling versus expectation — motivated the later development of Expected SARSA as a variance-reducing refinement.
Where this matters
Expected SARSA appears wherever tabular or small-action-space TD control is used and update variance is a bottleneck: classic control benchmarks (gridworlds, cliff-walking, mountain car with discretized actions), early-stage reinforcement learning curricula that build intuition before moving to function approximation, and as a component inside more elaborate architectures. Its core idea — replacing a sampled bootstrap target with an exact or approximate expectation — generalizes directly to modern deep RL: distributional and expectation-based critics in actor-critic methods, the use of target networks with averaged or expected next-state values, and double-estimator tricks that similarly aim to reduce the variance (and sometimes bias) of bootstrapped targets. Any system where an agent's next action is stochastic due to exploration — recommendation systems using epsilon-greedy exploration over a small catalog of actions, dialogue systems selecting among a discrete set of response templates, or resource allocators choosing among a bounded menu of policies — can, in principle, apply the same expectation trick to stabilize learning, provided the action space is small enough for the sum to remain cheap.
Ask the tutor: How would you adapt the Expected SARSA target when the action space is continuous and the exact expectation can't be computed in closed form?
Is Expected SARSA on-policy or off-policy?
It can be either, depending on which distribution is used inside the expectation. If the same policy that generates behavior (e.g., ε-greedy) is used inside the expectation, Expected SARSA is on-policy, evaluating and improving the policy it actually follows — directly analogous to SARSA. If a different, typically deterministic greedy policy is used inside the expectation while a more exploratory policy generates behavior, Expected SARSA is off-policy, and in the fully greedy case it becomes exactly Q-learning. This flexibility is why Expected SARSA is often presented as a unifying generalization rather than a single fixed algorithm.
Does Expected SARSA converge faster than SARSA in terms of episodes?
Empirically yes, in most benchmark tasks, because each update injects strictly less variance into the Q-table while targeting the same expected value. Since the update rule is a stochastic approximation toward a fixed point, lower per-update variance generally means the running estimate oscillates less and settles closer to its target with fewer samples, though the exact speedup depends on the step-size schedule, the entropy of the exploration policy, and the structure of the environment's reward and transition noise. It does not change the asymptotic fixed point being approximated, only the smoothness of the path toward it.
Why doesn't Expected SARSA introduce any bias despite changing the target?
Because the new target is exactly the conditional expectation of the old target, given all the information available at the time of the update. Formally, `E[G_ExpSARSA] = E[G_SARSA]` when both expectations are taken over the same randomness in the next action; Expected SARSA simply computes this expectation exactly instead of estimating it with one Monte-Carlo sample. This is a textbook Rao–Blackwellization: replacing a noisy statistic with its conditional expectation given a sufficient statistic never changes the mean but can only reduce or leave unchanged the variance.
What happens to Expected SARSA when the action space is continuous?
The exact sum over actions becomes an integral that generally has no closed form, making the algorithm intractable in its literal form. Practical workarounds include drawing a small number of Monte-Carlo samples from the policy to approximate the expectation (trading some variance reduction for tractability), restricting to policy families with closed-form expectations under the current Q-function approximation (e.g., certain parametric actor distributions), or switching to actor-critic methods where the critic explicitly targets an expectation via a separate mechanism, such as in soft actor-critic style algorithms.
How does Expected SARSA compare to Double Q-learning, which also targets variance and bias issues?
They address different problems. Expected SARSA reduces the variance of the target coming from sampling the next action, without touching the maximization bias that arises when the same Q-values are used both to select and to evaluate the greedy action. Double Q-learning specifically addresses that maximization (overestimation) bias by decoupling action selection and evaluation across two independently estimated value functions. The two ideas are complementary and can, in principle, be combined — using an expectation instead of a max, computed on a separate value estimate — though this compound approach is not the default in either the SARSA/Q-learning or the double-estimator literature.
Can Expected SARSA be used with function approximation instead of a table?
Yes, in the same way SARSA and Q-learning extend to function approximation: `Q(s,a)` is replaced by a parameterized `Q(s,a;θ)`, and the TD target `R + γ Σ_a π(a|S') Q(S',a;θ)` is used to form a squared-error loss whose gradient updates `θ`. The sum over actions still requires enumerating the (typically discrete and small) action set, so this variant is most natural in settings like Atari-style discrete-action deep Q-networks, where computing `Q(s, a; θ)` for every action is already required to select the greedy action.
Why is Expected SARSA not the universal default over Q-learning and SARSA if it strictly reduces variance?
Because the variance reduction is bought with extra computation — the `O(|A|)` sum — and with an added assumption that computing the full expectation over `π(·|S')` is feasible. When action spaces are very large, when environments already dominate wall-clock cost so the update cost is irrelevant, or when the exploration policy is nearly deterministic (making the sum reduce to almost a single term anyway), the benefit shrinks while the implementation complexity and per-step cost stay. In such regimes, plain SARSA or Q-learning remains a perfectly reasonable and simpler choice.