M4-T6 — Q-Learning and SARSA

Learning objectives

After this lesson, you should be able to:

• Write the Q-learning and SARSA updates side by side and say which term differs.
• Explain off-policy against on-policy learning and why the Q-learning target uses a max while the SARSA target uses the action actually taken.
• State the conditions under which tabular Q-learning converges, and say honestly where they do not hold in practice.
• Work one update by hand, set the target to the reward alone at a terminal state, and say why a table stops being enough.

The intuition

Imagine Scout walking beside the stairwell. It plans to take the edge route, but one time in ten it takes a random step. A random step beside the edge can go over it. Two kinds of learner can look at that same history. One asks: what would be the value of this cell if I behaved perfectly from now on? That is Q-learning, and the answer says the edge is fine. The other asks: what is the value of this cell given how I really behave, random steps included? That is SARSA, and the answer says the edge is dangerous, so it learns a route that keeps a margin.

Both are right, about different questions. Q-learning estimates the best policy while following another. SARSA estimates the policy it is following. The figure shows what each one learns on the stairwell corridor, a four-by-eight grid.

The mathematics

The two updates

After one step from state s, action a, reward r and next state s′, both methods move Q(s, a) a fraction α toward a target:

Q(s, a)

the table entry: estimated discounted return of taking a in s and behaving well afterwards (lesson M4-T3).

α

step size (learning rate), between 0 and 1. The TD error is target − Q(s, a), the quantity from lesson M4-T5.

γ

discount factor (lesson M4-T2).

a′

the next action. For SARSA it is the action the agent will really take next; the name comes from the tuple State, Action, Reward, State′, Action′.

terminal

a state that ends the episode. Nothing is earned after it, so its value is 0 by definition.

Why the targets differ

The Bellman optimality equation (lesson M4-T3) says Q*(s, a) = E[ r + γ · max_a′ Q*(s′, a′) ]. Q-learning is a stochastic, sample-by-sample version of that equation, so its target contains the max. The Bellman expectation equation for a policy π says Q^π(s, a) = E[ r + γ · Q^π(s′, a′) ] with a′ drawn from π. SARSA is the sample version of that one, so its target contains the next action taken.

Convergence: what is proved, and what is not

For tabular Q-learning, Watkins and Dayan (1992) proved that Q converges to Q* with probability 1 if every state-action pair is visited infinitely often and the step sizes α_n for each pair satisfy the Robbins–Monro conditions: the sum of α_n is infinite and the sum of α_n² is finite (for example α = 1 / n(s, a)). The behaviour policy can be anything that keeps visiting every pair. SARSA converges to Q* only if the policy also becomes greedy in the limit while still exploring enough, for instance ε_t = 1 / t; with a fixed ε it converges (under the same conditions) to the value of the ε-greedy policy, which is the point of the example below.

The honest reading: the theorem is about a table, an infinite run and a step size that decays. The labs and the example use a constant α of 0.5 and a few hundred episodes. A constant α never stops being moved by noise, and a finite run has not visited every pair equally. What is observed is that the greedy policy settles, usually on the right route, not that Q equals Q*. Expect an occasional seed to settle on a worse route.

Maximisation bias

The max in Q-learning’s target is taken over noisy estimates, and the maximum of noisy numbers is higher on average than the true maximum. If four actions all have true value 0 and each estimate is one sample with standard deviation 1, the max of the four averages 1.03 (200,000 simulated draws), and of eight, 1.42. The target is therefore optimistic wherever the table is noisy, and that optimism is pushed backwards through the bootstrapping. Double Q-learning (van Hasselt, 2010) keeps two tables and uses one to choose the action and the other to value it. In the small deterministic worlds of this module the bias is small; it matters with noisy rewards and many actions, and it returns in the deep methods of lesson M6.

The terminal-state target

At the step that ends the episode there is no s′ to bootstrap from: the target is r alone. Code that always computes r + gamma * max(Q[s2]) reads a row of the table for the terminal state. That row is 0 only if nobody ever wrote to it and the table was initialised to 0. Initialise optimistically, or let one update touch it, and the goal is worth more than its reward, the error leaks to every cell that leads there, and the agent’s values grow without bound or it hovers near the goal. This is the classic Q-learning bug and the first thing lab M4-L4 asks you to find.

• Check done before bootstrapping, using the flag the environment reports for this step, not a lookup that depends on the table.
• Truncating an episode at a step limit is not a terminal state of the task: there the target should still bootstrap. Only real terminals cut the bootstrap (lesson M4-T1).

A worked example

Every number below was computed by running RLCore’s Q-learning on the cliff corridor (4 × 8, step reward −1, goal +10, stairwell −100 and back to the start, γ = 0.99, α = 0.5, ε = 0.1, 500 episodes) and on small hand-chosen tables.

1. One update by hand. Scout is at some cell s, takes action a, and Q(s, a) is currently −2.0. It receives r = −1 and lands in s′, whose row is Q(s′, ·) = [−3.0, −1.5, −4.0, −2.0] for up, right, down, left. The ε-greedy rule at s′ happens to explore and pick left (a′ = 3, value −2.0). The numbers are chosen to make the arithmetic visible; they are not read from a run.

The exploring step made SARSA’s estimate worse than Q-learning’s by 0.2475 in one update. Had the agent picked up (−3.0), Q-learning would have produced the same −2.2425 and SARSA −2.9. That is the whole difference between the algorithms.

2. The terminal target. Scout steps onto the goal: r = −1 + 10 = 9, Q(s, a) = 0. The correct target is 9, so the new value is 0 + 0.5 × (9 − 0) = 4.5. If the table row of the goal holds 5 (an optimistic initial value) and the code bootstraps anyway, the target is 9 + 0.99 × 5 = 13.95 and the new value is 6.975: a cell next to the goal that is worth more than anything achievable in the world, and the excess keeps being fed back.

3. Cliff walking, one seed. With seed 1, Q-learning’s greedy policy is the optimal route up, 7 right, down (nine moves, exact discounted value of the start 0.579, the value iteration optimum from lesson M4-T4). Its online return, the mean undiscounted return over the last 100 training episodes while still exploring, is −23.9, because exploring steps fall down the stairs (about 109 falls per 500-episode run, averaged over the 20 seeds below), and each fall costs 100. SARSA’s online return is −10.2 and its greedy policy takes the upper route (up 3, 7 right, down 3, thirteen moves) with value −3.38: twelve step costs and the goal reward, discounted. Q-learning knows the better route; SARSA lives better while learning.

4. Twenty seeds. Seeds 1 to 20, everything else equal:

The ordering is the same on every one of the 20 seeds: SARSA’s online return is higher than Q-learning’s, while Q-learning’s greedy route is better. If ε is decayed toward 0 SARSA is supposed to approach the edge route too. Running ε from 0.5 down to 0.001 over 2,000 episodes, 19 of 20 SARSA seeds still ended on a −3.38 route and one on −1.42: with a constant α the table does not always re-plan once it has settled, so this is slower than the theory suggests. Q-learning under the same schedule gave 0.58 in 18 seeds and −1.42 in 2.

What the simulation simplifies. The corridor is deterministic and tiny (32 cells). The real hospital has people stepping into the corridor, slip on wet floors, and a stairwell that does not reset Scout to the start. Whether fall costs of −100 and a reset reflect how a real robot should be penalised is a design choice (lesson M5 on reward design).

Engineering implications and limitations

Which one to use

Use Q-learning when you want the best policy and can afford exploratory mistakes: in simulation, or when exploration is separated from deployment. Use SARSA, or expected SARSA, when the data are collected by the policy that will be deployed and its mistakes matter: the learned values then already include the cost of its own exploration. Because Q-learning learns about the greedy policy while behaving differently, it can also learn from stored or demonstrated transitions, which is why deep methods favour it (lesson M6).

Measure two returns

Always log the online return (what the agent earned while learning) and the greedy return (what the table would earn if exploration stopped). The cliff shows they can disagree by 24 points. Lesson M4-T7 returns to this.

Step size and initial values

A constant α near 0.1 to 0.5 is the usual practical choice for small tables; a decaying 1 / n(s, a) matches the proof but learns slowly. Start the table at 0 unless you mean to use optimistic initial values (lesson M4-T7), and remember that 0 is optimistic whenever every step costs something.

When tables stop working

The ward has 25 open cells and the cliff 32: a table with four actions has about 100 to 130 numbers. Discretise Scout’s reach task (a 10 m × 6 m hall) into 0.1 m cells and the position alone gives 6,000 cells, and 24,000 table entries for four moves, each of which needs many visits; add the pillar position or a heading and the count multiplies again. A 64 × 64 grey-scale camera image has about 10⁹⁸⁶⁴ possible values. Two problems follow: most cells are never visited, and nothing learned in one cell helps its neighbour. The cure is to replace the table by a function with parameters that generalises, so that Q(s, a; θ) is a neural network (lesson M6, deep reinforcement learning). Everything in this lesson, the targets, the terminal rule and maximisation bias, carries over; the convergence proof does not.

Debugging checklist (lab M4-L4)

1. Is the target r alone at a terminal step, using the done flag of this step?
2. Is the update applied to Q[s][a], with the s and a that were used, not to Q[s′][a]?
3. Is γ multiplying the bootstrapped value, not the reward?
4. For SARSA, is a′ chosen once, before the update, and then actually taken?
5. Does the greedy return improve while the online return is flat? That is an exploration question (lesson M4-T7), not an update bug.

Lab M4-L2 has you implement the epsilon-greedy choice, the update and the full training loop.

Common misconceptions

Engineering takeaways

1. Q-learning bootstraps from max Q(s′, ·); SARSA bootstraps from Q(s′, a′) with the action actually taken. That one term makes one off-policy and the other on-policy.
2. On the cliff, Q-learning learns the edge route (greedy 0.58) but its online return is about −21 over 20 seeds; SARSA learns a safer route (−3.38) with online return about −11.
3. Tabular Q-learning converges when every pair is visited infinitely often and the step sizes decay (Robbins–Monro); constant-α runs only approximate this.
4. At a terminal step the target is r alone. Bootstrapping through the goal is the classic bug.
5. Tables do not generalise and explode with the state count, so Module 6 replaces Q(s, a) with a function.

References and further reading

Sutton and Barto give both algorithms and the cliff-walking example; the others are the original papers.

• R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018 (chapter 6: SARSA, Q-learning, Example 6.6 Cliff Walking, and the discussion of maximisation bias).
• C. J. C. H. Watkins and P. Dayan, “Q-learning”, Machine Learning 8(3–4), 279–292, 1992.
• G. A. Rummery and M. Niranjan, “On-line Q-learning using connectionist systems”, Technical Report CUED/F-INFENG/TR 166, Cambridge University Engineering Department, 1994.
• H. van Hasselt, “Double Q-learning”, Advances in Neural Information Processing Systems 23 (NIPS), 2010.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: Q-learning only learns about the pairs it tries, so how Scout chooses what to try, and how much to risk, is the subject of exploration versus exploitation.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T5: Monte Carlo and Temporal-Difference Learning

  Estimate values from experience with Monte Carlo and TD(0), and compare their bias and variance.

• Lab
  M4-L2: Implement Q-Learning

  Scout does not know the map: learn a route from trial and error with a tabular Q-learning agent.

• Lab
  M4-L4: Debug a Q-Learning Agent

  The agent's return stays flat for 5,000 episodes: find the terminal-state, discount and update bugs.