Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 37 ยท Q-learning and SARSA

Expected SARSA and Double Q-learning

Learn two upgrades to tabular TD control: Expected SARSA lowers update variance, and Double Q-learning removes maximization bias. Runnable Python experiments included.

Q-learning and SARSA differ in one term: the value used as the "next" estimate. Q-learning uses the best next action, SARSA uses the next action that was actually taken. That small choice has consequences, and two refinements fix real weaknesses of each: Expected SARSA reduces the noise of the update, and Double Q-learning removes a systematic optimism called maximization bias.

In this lesson you will build both, compare them with their parents and see the bias with your own eyes. If you have not met the originals yet, read the Q-learning algorithm and SARSA first.

One family, three targets

Every one-step TD control method updates Q(s, a) toward a target:

Method Target
SARSA r + gamma * Q(s', a') where a' was sampled from the behavior policy
Q-learning r + gamma * max_a Q(s', a)
Expected SARSA r + gamma * (sum over a of pi(a given s') * Q(s', a))

Expected SARSA replaces the random sample Q(s', a') with its expectation under the policy. Nothing is left to chance in the choice of the next action, so the update has lower variance than SARSA. It can also be used off-policy: if the target policy pi is greedy, the expectation collapses to max, and Expected SARSA is Q-learning.

For an epsilon-greedy policy over n actions, the expectation is simple: (epsilon / n) * sum(Q(s', .)) + (1 - epsilon) * max(Q(s', .)).

Expected SARSA in practice

Let us train all three on a small stochastic task: a one-dimensional corridor where the agent slips (moves the wrong way) 20 percent of the time. Slips make single samples noisy, which is where Expected SARSA shines.

Python SARSA vs Q-learning vs Expected SARSA

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On a task this small the three methods finish close together, and with only a few seeds the ordering can change from run to run. The difference Expected SARSA makes is in the variance of the updates: raise alpha toward 0.9 or add more seeds and compare how steady each curve is. Its real advantage grows on larger, noisier problems.

Maximization bias

Now to the second problem. Q-learning takes a max over noisy estimates. The maximum of several noisy numbers is, on average, bigger than the true maximum of their means. Imagine ten actions that all truly pay about zero; your estimates wobble around zero, and the largest wobble is positive. Q-learning bootstraps from that inflated number, so the optimism spreads backwards through the table.

flowchart LR
    A["State A"] -->|right| T1["terminal, reward 0"]
    A -->|left| B["State B"]
    B -->|"10 actions, each reward N(-0.1, 1)"| T2["terminal"]

Going left is a bad idea on average (every reward is about -0.1), but B's maximum looks attractive.

Double Q-learning

Double Q-learning keeps two tables, Q1 and Q2. On each step, flip a coin. Say it picks Q1: use Q1 to choose the best next action, but use Q2 to evaluate it:

TEXT
a* = argmax_a Q1(s', a)
Q1(s, a) += alpha * (r + gamma * Q2(s', a*) - Q1(s, a))

Because the two tables see different samples, an estimate that was lucky in Q1 is not usually lucky in Q2, so the bias disappears. Acting uses Q1 + Q2.

Python Maximization bias: how often does the agent go left?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ordinary Q-learning goes left far more often than it should in the first hundred episodes (going right is always better); Double Q-learning goes left only about as often as exploration forces it to. The effect is strongest when rewards are noisy and there are many actions.

When to use what

  • Q-learning is the simplest and has the weakest requirements; fine when rewards are nearly deterministic.
  • Expected SARSA is a great default for tabular problems: lower variance, no extra tables, works on- or off-policy.
  • Double Q-learning helps when rewards are noisy or the action space is large. The same idea scales up as Double DQN in deep RL.

Common mistakes

  • Using the sampled next action in the Expected SARSA target instead of the policy-weighted average.
  • Forgetting that the policy used in the expectation must match the epsilon used for acting if you want it on-policy.
  • Updating both tables on every step in Double Q-learning. Update one, chosen at random.
  • Using Q1 alone to act; use the sum or average of both.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does Expected SARSA use as the next-state value in its target?

    It averages Q(s', a) over the policy's action probabilities, removing the variance from sampling a'.
  2. 2. If the target policy of Expected SARSA is greedy, which algorithm do you get?

    A greedy policy puts probability 1 on the best action, so the expectation equals the max.
  3. 3. Why does taking a max over noisy estimates cause maximization bias?

    Positive estimation errors are the ones the max picks, so the result is biased upward.
  4. 4. In Double Q-learning, how are the two tables used in one update?

    Decoupling selection from evaluation removes the correlation that creates the upward bias.

Summary

  • One-step TD control methods differ in their target: SARSA samples, Q-learning maximizes, Expected SARSA averages.
  • Expected SARSA has lower variance than SARSA and can run off-policy.
  • Taking a max over noisy estimates makes Q-learning overestimate values.
  • Double Q-learning selects with one table and evaluates with the other, which cancels the bias.
  • The same trick returns in deep RL as Double DQN.

Next: Dyna-Q: Learning and Planning