TD Control: Sarsa, Q-learning, and Double Learning

This builds on Temporal-Difference Learning, which developed TD(0) prediction, the TD error, and the optimality of batch TD. Here we turn from predicting a fixed policy's values to improving the policy — control — by slotting TD into the same generalized-policy-iteration loop as every other tabular method, now over state-action values.

Sarsa: on-policy control

Turn now from prediction to control. As with the other tabular methods, we follow generalized policy iteration, this time with TD for the evaluation step. The first change is to learn an action-value function rather than a state-value function: for the current behavior policy $\pi$ we estimate $q_{\pi }(s,a)$ for all $s$ and $a$. This is done with the very TD idea from prediction, applied to state–action pairs. An episode is an alternating chain of states and state–action pairs, and we now consider transitions from one state–action pair to the next:

This update runs after every transition from a nonterminal state $S_t$; if $S_{t+1}$ is terminal, $Q(S_{t+1},A_{t+1})$ is defined as zero. The rule uses every element of the quintuple $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$ that makes up a transition from one state–action pair to the next — and it is that quintuple that gives the algorithm its name, Sarsa.¹

Building control on top is straightforward. As in all on-policy methods, we continually estimate $q_{\pi }$ for the behavior policy $\pi$ while nudging $\pi$ toward greediness with respect to $Q$ — typically an $\epsilon$-greedy policy, which takes the greedy action most of the time but with probability $\epsilon$ explores a random one.

Sarsa is on-policy: the action $A^{\prime }$ that appears in the target is the action the policy actually takes next, exploration and all. It converges to an optimal policy and action-value function as long as all state–action pairs are visited infinitely often and the policy converges in the limit to greedy — arranged, for example, by an $\epsilon$-greedy policy with $\epsilon =1/t$.

Windy gridworld

The windy gridworld (Example 6.5) shows Sarsa learning control where Monte Carlo cannot easily be applied. The agent moves on a $7\times 10$ grid from a start $S$ to a goal $G$, with the four standard moves, but a crosswind blows upward through the middle columns: the wind strength (in cells shifted up) is $0,0,0,1,1,1,2,2,1,0$ across the ten columns, added to the move's result. Every step costs $-1$ until the goal is reached; the task is undiscounted and episodic.²

The wind makes the shortest path indirect — a straight rightward march is blown past the goal, so the agent must aim below and let the wind carry it up. Run $\epsilon$-greedy Sarsa with $\epsilon =0.1$, $\alpha =0.5$, and initial $Q=0$. Early episodes are long (the agent wanders), but the slope of episodes-completed against time steps steepens as $Q$ sharpens; by about $8000$ time steps the greedy policy is optimal, reaching the goal in the minimum $15$ steps, and continued $\epsilon$-greedy exploration holds the average around $17$.

Some policies in the windy gridworld never terminate: a policy that pushes the agent into a wall it cannot escape loops forever, so Monte Carlo, which needs an episode to end before it can learn, would hang. Sarsa learns during the episode that such a policy is bad and moves off it, so it never gets stuck. Online, incremental learning is what makes control possible here at all.

Q-learning: off-policy control

One of the early breakthroughs in reinforcement learning was Q-learning, an off-policy TD control method.³ Its update looks almost like Sarsa's, but with one change in the target:

Where Sarsa bootstraps from $Q(S_{t+1},A_{t+1})$ — the value of the action it will take — Q-learning bootstraps from ${\max }_{a}Q(S_{t+1},a)$ — the value of the best action available next, whether or not the policy takes it. The learned $Q$ therefore approximates $q_{\ast }$, the optimal action-value function, directly and independently of the policy being followed. The policy still governs which pairs are visited, but all that is required for convergence is that all pairs keep being updated. Under that condition and the usual step-size schedule, $Q$ converges with probability 1 to $q_{\ast }$.

The difference shows up on the cliff-walking gridworld. The agent walks from start to goal along the edge of a cliff; stepping off costs $-100$ and resets it to the start, every other step costs $-1$. Q-learning learns the values of the optimal policy, which hugs the cliff edge — but because it still explores $\epsilon$-greedily while acting, it occasionally steps off and its online return suffers. Sarsa, learning the values of the policy it actually follows, accounts for the exploration and prefers the longer but safer path away from the edge; its online return is better even though the policy it learns is not optimal. Reduce $\epsilon$ toward zero over time and both converge to the optimal policy.³ The lesson generalizes: off-policy Q-learning learns the optimal target policy but can behave worse online than on-policy Sarsa, which learns a policy that is safe given its own exploration.

Expected Sarsa

Between Sarsa and Q-learning sits a third method. Take the Q-learning schema but replace the maximum over next actions with the expected value under the current policy — weighting each next action by how likely the policy is to take it:

This is Expected Sarsa. Given the next state $S_{t+1}$ it moves deterministically in the same direction that Sarsa moves in expectation — the move its name records. It costs more computation than Sarsa — a sum over actions rather than a single sample — but in return it removes the variance that comes from sampling $A_{t+1}$ at random. Given the same experience it generally performs slightly better than Sarsa, and it can safely use $\alpha =1$ on deterministic problems, where Sarsa needs a small $\alpha$ and pays for it in slow early learning.

Expected Sarsa also subsumes Q-learning. If the policy used to compute the expectation is the greedy policy while behavior is more exploratory, the expected value is just the max, and Expected Sarsa becomes Q-learning exactly. In this sense, Expected Sarsa is a single algorithm with Sarsa and Q-learning as two endpoints: on-policy when the target policy is the behavior policy, off-policy (and equal to Q-learning) when the target policy is greedy.⁴

Maximization bias and Double Q-learning

Every control method so far builds its target policy by maximizing: Q-learning's target is greedy, and Sarsa's $\epsilon$-greedy policy maximizes too. A maximum over estimated values is being used, implicitly, as an estimate of the maximum of the true values — and that introduces a positive bias.

Consider a single state with many actions whose true values $q(s,a)$ are all exactly zero, but whose estimates $Q(s,a)$ are noisy, scattered above and below zero. The true maximum is zero. The maximum of the estimates is almost surely positive, because the max picks out whichever action happened to be overestimated. This systematic overshoot is maximization bias: the same sample is used both to choose the maximizing action and to estimate its value, and that double use tilts the estimate upward.

To address this, break the coupling by keeping two independent estimates. Split the experience into two sets and learn $Q_1(a)$ and $Q_2(a)$, each an unbiased estimate of the true $q(a)$. Use one to pick the maximizing action, $A^{\ast }=\arg {\max }_a{Q}_1(a)$, and the other to read off its value, $Q_2(A^{\ast })$. Because $Q_2$ was not used to select $A^{\ast }$, its estimate is unbiased: $\mathbb{E}[Q_2(A^{\ast })]=q(A^{\ast })$. Swap the roles to get a second unbiased estimate. This is double learning. It doubles the memory but not the computation per step — only one of the two estimates is updated on each step.

Applied to full MDPs this gives Double Q-learning. On each step, flip a coin. If heads, update $Q_1$ using $Q_1$ to select the next action and $Q_2$ to value it:

If tails, do the same with $Q_1$ and $Q_2$ swapped. The behavior policy can use both estimates — for instance $\epsilon$-greedy in $Q_1+Q_2$.⁵

On the small MDP where plain Q-learning strongly favors a spuriously positive-looking action, Double Q-learning is essentially unaffected by the bias and finds the optimal policy. There are double versions of Sarsa and Expected Sarsa too; the principle — decouple the action selected from the estimate used to value it — is general.

Beyond the table: TD in deep reinforcement learning

The four updates above are one-step, tabular, and model-free. Drop tabular — represent $Q$ by a neural network $Q(s,a;\theta )$ instead of a lookup table — and the same TD error drives deep reinforcement learning. This has a cost: bootstrapping, function approximation, and off-policy training together form what Sutton and Barto later call the deadly triad, a combination that can make the learning process diverge. Much of the practical work in deep RL addresses this instability.

Deep Q-Networks. Mnih and colleagues' DQN learned to play Atari 2600 games from raw pixels using exactly the Q-learning update, with $Q$ a convolutional network.⁶ Two ideas stabilize the network's TD updates. An experience replay buffer stores past transitions and samples them at random for each update, breaking the temporal correlations that would otherwise make the gradient steps dependent. And a periodically-frozen target network supplies the bootstrap value ${\max }_{a}Q(S^{\prime },a;{\theta }^{-})$ from an old copy ${\theta }^{-}$ of the weights, so the target does not move with the parameters being trained — the same concern that motivates the warm-started, slow-moving targets throughout tabular DP, now made explicit because a network's fast, correlated updates would otherwise destabilize the fixed point.

Maximization bias, at scale. The bias that Double Q-learning fixes is worse with networks, because the $\max$ over a noisy network's outputs is systematically optimistic. Van Hasselt, Guez, and Silver's Double DQN ports double learning directly: select the maximizing next action with the online network $\theta$ but read its value from the target network ${\theta }^{-}$, cutting the overestimation and improving scores on many Atari games.⁷ This is the same decoupling of selection from evaluation as in the tabular section, applied to two networks that already exist for a different reason.

Combining improvements. Expected Sarsa's variance-reduction motive, TD's $n$-step generalization, and prioritized replay (drawing high-TD-error transitions more often — the same backward-focusing logic as prioritized sweeping) all reappear as components. Hessel and colleagues' Rainbow combined six such extensions — double Q-learning, prioritized replay, dueling networks, multi-step returns, distributional value learning, and noisy exploration — and showed they largely add up, each addressing a distinct weakness of plain DQN.⁸ Nearly every idea in deep value-based RL is a neural restatement of a one-step tabular update from this lesson.

What TD unifies, and where it points

TD learning is central to the whole subject. It keeps Monte Carlo's freedom from a model and gains DP's ability to learn before an outcome is known, all in a handful of single-equation updates that a small program can run online. The four methods here are one family under generalized policy iteration: Sarsa evaluates on-policy, Q-learning targets the optimal policy off-policy, Expected Sarsa spans the two, and Double Q-learning removes the maximization bias that afflicts all of them.

These are the one-step, tabular, model-free special cases. The next lesson, n-step bootstrapping, loosens the one-step by backing up from $n$ steps ahead, forming a bridge on which TD($n=1$) and Monte Carlo ($n=\infty$) are the two ends of a continuum. Planning and learning loosens model-free by folding a learned model back into the same updates. Later the tabular restriction falls away under function approximation, carrying TD into deep reinforcement learning.

The TD error also appears outside algorithms. The quantity ${\delta }_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$ — a reward-prediction error, the gap between the prediction and what one observed step delivered — closely matches the phasic firing of the brain's dopamine neurons. That correspondence is the subject of dopamine and the TD error.