--- title: "TD Control: Sarsa, Q-learning, and Double Learning" module: Tabular Solution Methods moduleNumber: 2 lessonNumber: 6 order: 206 summary: > With TD prediction in hand, control follows the generalized-policy-iteration pattern with TD as the evaluation step. We build Sarsa (on-policy), Q-learning (off-policy, targeting the optimal policy), and Expected Sarsa that spans the two, then confront the maximization bias every max-based method inherits and fix it with Double Q-learning. We close past Sutton & Barto, following each one-step tabular update into its deep-RL descendant — DQN, Double DQN, and Rainbow. topics: [Tabular Methods] sources: - book: Sutton & Barto ref: "§6.4 Sarsa; §6.5 Q-learning; §6.6 Expected Sarsa; §6.7 Maximization Bias and Double Learning" --- This builds on [Temporal-Difference Learning](/reinforcement-learning/tabular-methods/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: $$ Q(S_t, A_t) \;\leftarrow\; Q(S_t, A_t) + \alpha\big[\,R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)\,\big]. $$ 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**.[^sb-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 **$\varepsilon$-greedy** policy, which takes the greedy action most of the time but with probability $\varepsilon$ explores a random one. ```algorithm caption: $\textsc{Sarsa}$ — on-policy TD control, estimate $Q \approx q_\ast$ $Q(s,a) \gets$ arbitrary, with $Q(\text{terminal}, \cdot) = 0$, for all $s \in \mathcal{S}, a \in \mathcal{A}$ for each episode do initialize $S$ choose $A$ from $S$ using a policy derived from $Q$ (e.g. $\varepsilon$-greedy) repeat take action $A$, observe $R$, $S'$ choose $A'$ from $S'$ using a policy derived from $Q$ (e.g. $\varepsilon$-greedy) $Q(S,A) \gets Q(S,A) + \alpha[R + \gamma Q(S',A') - Q(S,A)]$ $S \gets S'$ $A \gets A'$ until $S$ is terminal ``` Sarsa is **on-policy**: the action $A'$ 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 $\varepsilon$-greedy policy with $\varepsilon = 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.[^sb-windy] 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 $\varepsilon$-greedy Sarsa with $\varepsilon = 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 $\varepsilon$-greedy exploration holds the average around $17$. $$ % caption: The windy gridworld. The agent goes from S to G on a 7-by-10 grid; the % number under each column is the upward wind that displaces the agent after each % move. The blue path is the optimal 15-step route Sarsa learns: it must aim % below the goal and ride the wind up. Monte Carlo struggles here because some % policies never terminate. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} % grid 10 wide x 7 tall, scaled \foreach \x in {0,...,10} \draw[black] (\x*0.6,0) -- (\x*0.6,4.2); \foreach \y in {0,...,7} \draw[black] (0,\y*0.6) -- (6.0,\y*0.6); % S at col0 row3, G at col7 row3 (0-indexed rows from bottom) \node[font=\scriptsize] at (0.3,2.1) {S}; \node[font=\scriptsize] at (4.5,2.1) {G}; % optimal path (schematic): right along bottom, then wind carries up to G \draw[acc, thick, ->] (0.3,1.8) -- (0.3,0.3) -- (3.9,0.3) -- (3.9,1.2) -- (4.5,1.2) -- (4.5,1.8); % wind strengths under columns \foreach \c/\w in {0/0,1/0,2/0,3/1,4/1,5/1,6/2,7/2,8/1,9/0} { \node[font=\scriptsize, anchor=north] at (\c*0.6+0.3,-0.05) {\w}; } \node[anchor=west, font=\scriptsize, text=black] at (6.2,3.5) {wind (up) per column}; \node[anchor=west, font=\scriptsize, text=black] at (6.2,2.9) {reward -1 per step}; \node[acc, anchor=west, font=\scriptsize] at (6.2,2.3) {optimal path: 15 steps}; \end{tikzpicture} $$ 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.[^sb-ql] Its update looks almost like Sarsa's, but with one change in the target: $$ Q(S_t, A_t) \;\leftarrow\; Q(S_t, A_t) + \alpha\Big[\,R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)\,\Big]. $$ 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$. $$ % caption: Sarsa versus Q-learning at the same next state $S'$. Both take one % real step to $S'$; Sarsa bootstraps from the value of the action the policy % will actually take there (following the same exploratory policy), while % Q-learning bootstraps from the maximum over next actions — the greedy value, % regardless of what is taken. \begin{tikzpicture}[>=stealth, font=\footnotesize, st/.style={circle, draw, fill=white, minimum size=5mm, inner sep=0pt}, ac/.style={circle, draw, fill=black, minimum size=2.4mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % ===== Sarsa ===== \begin{scope} \node[ac, label={[text=acc]above:(S A)}] (sa) at (0,3) {}; \node[st] (sp) at (0,1.6) {}; \draw[acc, thick] (sa) -- (sp) node[midway, right, font=\scriptsize] {R}; \node[anchor=east, font=\scriptsize] at (-0.2,1.6) {S'}; \node[ac] (b1) at (-1.0,0.4) {}; \node[ac] (b2) at (0,0.4) {}; \node[ac] (b3) at (1.0,0.4) {}; \draw[black] (sp) -- (b1); \draw[acc, thick] (sp) -- (b2); \draw[black] (sp) -- (b3); \node[acc, anchor=north, font=\scriptsize] at (0,0.28) {A' taken}; \node[anchor=north, font=\footnotesize] at (0,-0.15) {Sarsa}; \end{scope} % ===== Q-learning ===== \begin{scope}[xshift=5.4cm] \node[ac, label={[text=acc]above:(S A)}] (sa) at (0,3) {}; \node[st] (sp) at (0,1.6) {}; \draw[acc, thick] (sa) -- (sp) node[midway, right, font=\scriptsize] {R}; \node[anchor=east, font=\scriptsize] at (-0.2,1.6) {S'}; \node[ac] (b1) at (-1.0,0.4) {}; \node[ac] (b2) at (0,0.4) {}; \node[ac] (b3) at (1.0,0.4) {}; \draw[black] (sp) -- (b1); \draw[black] (sp) -- (b2); \draw[black] (sp) -- (b3); % max arc across next actions \draw[red, thick] (-1.3,0.85) arc[start angle=205, end angle=335, radius=1.14]; \node[red, anchor=north, font=\scriptsize] at (0,0.82) {max over a}; \node[anchor=north, font=\footnotesize] at (0,-0.15) {Q-learning}; \end{scope} \end{tikzpicture} $$ 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 $\varepsilon$-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 $\varepsilon$ toward zero over time and both converge to the optimal policy.[^sb-ql] 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: $$ Q(S_t, A_t) \;\leftarrow\; Q(S_t, A_t) + \alpha\Big[\,R_{t+1} + \gamma \sum_a \pi(a \mid S_{t+1})\, Q(S_{t+1}, a) - Q(S_t, A_t)\,\Big]. $$ 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.[^sb-exp] ## 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 $\varepsilon$-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. > **Definition (Maximization bias).** The positive bias that arises when a > maximum over noisy estimates is used to estimate the maximum of the true > values. Because one sample both selects the apparently-best action and reports > its value, the reported value is biased high. 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. $$ % caption: Maximization bias and its fix. With a single noisy estimate (left), % the max picks the action that happened to be overestimated, so the reported max % is biased above the true value 0. Double learning (right) uses Q1 to pick the % action and the independent Q2 to value it, decoupling selection from evaluation. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % ===== LEFT: single estimate, biased ===== \begin{scope} \draw[black] (-0.3,0) -- (4.2,0); \node[anchor=east, font=\scriptsize] at (-0.35,0) {0}; % noisy estimates around zero, some above \foreach \x/\h in {0.3/0.5, 0.9/-0.4, 1.5/0.9, 2.1/-0.3, 2.7/0.6, 3.3/-0.5} { \draw[black, fill=black!8] (\x,0) rectangle (\x+0.4,\h); } % the max (overestimate) \draw[red, very thick] (1.5,0) rectangle (1.9,0.9); \draw[red, dashed, thick] (0.2,0.9) -- (4.0,0.9); \node[red, anchor=south east, font=\scriptsize] at (4.0,0.98) {biased max}; \node[anchor=north, font=\footnotesize] at (2.0,-0.7) {single estimate}; \end{scope} % ===== RIGHT: double learning ===== \begin{scope}[xshift=6.4cm] \draw[black] (-0.3,0) -- (4.2,0); \node[anchor=east, font=\scriptsize] at (-0.35,0) {0}; % Q1 selects, Q2 evaluates \node[acc, anchor=south west, font=\scriptsize] at (0.0,1.55) {Q1: pick argmax}; \node[anchor=south west, font=\scriptsize] at (0.0,1.15) {Q2: read its value}; \draw[acc, thick, ->] (1.9,1.5) -- (1.9,0.5); \fill[acc] (1.9,0.5) circle (2.4pt); \node[acc, anchor=west, font=\scriptsize] at (2.05,0.5) {unbiased}; \draw[black, dashed] (0.2,0.0) -- (4.0,0.0); \node[anchor=north, font=\footnotesize] at (2.0,-0.7) {double learning}; \end{scope} \end{tikzpicture} $$ 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: $$ Q_1(S_t, A_t) \;\leftarrow\; Q_1(S_t, A_t) + \alpha\Big[\,R_{t+1} + \gamma\, Q_2\big(S_{t+1}, \arg\max_a Q_1(S_{t+1}, a)\big) - Q_1(S_t, A_t)\,\Big]. $$ If tails, do the same with $Q_1$ and $Q_2$ swapped. The behavior policy can use both estimates — for instance $\varepsilon$-greedy in $Q_1 + Q_2$.[^sb-double] ```algorithm caption: $\textsc{Double-Q-Learning}$ — estimate $Q_1 \approx Q_2 \approx q_\ast$ $Q_1(s,a),\, Q_2(s,a) \gets$ arbitrary, with $Q(\text{terminal}, \cdot) = 0$, for all $s \in \mathcal{S}, a \in \mathcal{A}$ for each episode do initialize $S$ repeat choose $A$ from $S$ using the policy $\varepsilon$-greedy in $Q_1 + Q_2$ take action $A$, observe $R$, $S'$ with probability $0.5$ do $Q_1(S,A) \gets Q_1(S,A) + \alpha\big[R + \gamma\, Q_2(S', \arg\max_a Q_1(S',a)) - Q_1(S,A)\big]$ else $Q_2(S,A) \gets Q_2(S,A) + \alpha\big[R + \gamma\, Q_1(S', \arg\max_a Q_2(S',a)) - Q_2(S,A)\big]$ $S \gets S'$ until $S$ is terminal ``` 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.[^dqn] 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', 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. $$ % caption: DQN adapts tabular Q-learning to a neural network. The Q-learning % target still bootstraps from the next state, but the value comes from a frozen % target network (theta-minus), and transitions are drawn from a replay buffer % rather than the live stream, decorrelating the updates. \begin{tikzpicture}[>=stealth, font=\footnotesize, box/.style={draw, minimum width=24mm, minimum height=9mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \node[box] (env) at (0,2.2) {environment}; \node[box] (buf) at (0,0.4) {replay bu\/f\/fer}; \node[box, draw=acc, text=acc, thick] (net) at (4.6,1.3) {Q-network\\theta}; \node[box, draw=red, text=red] (tgt) at (9.2,1.3) {target net\\theta-minus}; \draw[->, thick] (env) -- (buf) node[midway, right, font=\scriptsize] {store}; \draw[->, acc, thick] (buf) -- (net) node[midway, above, font=\scriptsize] {sample batch}; \draw[->, red, thick] (tgt) -- (net) node[midway, above, font=\scriptsize] {max-Q target}; \draw[->, black, dashed] (net) to[bend right=30] node[midway, below, font=\scriptsize] {copy every C steps} (tgt); \end{tikzpicture} $$ **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.[^ddqn] 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.[^rainbow] Nearly every idea in deep value-based RL is a neural restatement of a one-step tabular update from this lesson. $$ % caption: The tabular-to-deep map. Each tabular idea on the left has a direct % descendant in deep value-based RL on the right: Q-learning becomes DQN, Double % Q-learning becomes Double DQN, Expected Sarsa's variance control and n-step % returns feed multi-step targets, and prioritized sweeping's focus becomes % prioritized replay. \begin{tikzpicture}[>=stealth, font=\footnotesize, lft/.style={draw, minimum width=32mm, minimum height=7mm, align=center, font=\scriptsize}, rgt/.style={draw, draw=acc, text=acc, minimum width=32mm, minimum height=7mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[lft] (ql) at (0,3.0) {Q-learning}; \node[lft] (dql) at (0,1.8) {Double Q-learning}; \node[lft] (esn) at (0,0.6) {Expected Sarsa / n-step}; \node[lft] (psw) at (0,-0.6) {prioritized sweeping}; \node[rgt] (dqn) at (6.4,3.0) {DQN}; \node[rgt] (ddqn) at (6.4,1.8) {Double DQN}; \node[rgt] (ms) at (6.4,0.6) {multi-step targets}; \node[rgt] (pr) at (6.4,-0.6) {prioritized replay}; \draw[->, acc, thick] (ql) -- (dqn); \draw[->, acc, thick] (dql) -- (ddqn); \draw[->, acc, thick] (esn) -- (ms); \draw[->, acc, thick] (psw) -- (pr); \end{tikzpicture} $$ ## 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](/reinforcement-learning/tabular-methods/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](/reinforcement-learning/tabular-methods/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](/reinforcement-learning/approximation/on-policy-prediction), 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](/reinforcement-learning/minds-and-brains/dopamine-and-td-error). [^sb-sarsa]: **Sutton & Barto**, §6.4 — Sarsa: On-policy TD Control: the action-value update (6.7) over the quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$, the Sarsa control box, and convergence under $\varepsilon$-greedy exploration with $\varepsilon = 1/t$; Example 6.5 (Windy Gridworld). [^sb-ql]: **Sutton & Barto**, §6.5 — Q-learning: Off-policy TD Control (Watkins, 1989): the update (6.8) with $\max_a Q(S_{t+1}, a)$, direct approximation of $q_\ast$ independent of the behavior policy, and Example 6.6 (Cliff Walking) contrasting the online performance of Sarsa and Q-learning. [^sb-exp]: **Sutton & Barto**, §6.6 — Expected Sarsa: the update (6.9) using $\sum_a \pi(a \mid S_{t+1}) Q(S_{t+1}, a)$, its reduced variance relative to Sarsa, safe use of $\alpha = 1$ on deterministic tasks, and how it becomes Q-learning when the target policy is greedy. [^sb-double]: **Sutton & Barto**, §6.7 — Maximization Bias and Double Learning: maximization bias from using a max of estimates as an estimate of the max, Example 6.7's small MDP, and the Double Q-learning algorithm (6.10) with its box, using independent estimates $Q_1, Q_2$ to decouple action selection from value estimation. [^sb-windy]: **Sutton & Barto**, §6.4, Example 6.5 (Windy Gridworld): the $7 \times 10$ grid with column winds $0,0,0,1,1,1,2,2,1,0$, constant $-1$ rewards, and $\varepsilon$-greedy Sarsa ($\varepsilon = 0.1$, $\alpha = 0.5$, $Q_0 = 0$) reaching the optimal 15-step policy by about 8000 time steps; the note that Monte Carlo is hard to apply because some policies never terminate. [^dqn]: **Mnih, V., et al.** (2015), "Human-level Control through Deep Reinforcement Learning," _Nature_ 518:529–533 (DQN) — Q-learning with a convolutional $Q$-network learning Atari 2600 from pixels, stabilized by experience replay and a periodically-updated target network. [^ddqn]: **van Hasselt, H., Guez, A., & Silver, D.** (2016), "Deep Reinforcement Learning with Double Q-learning," _AAAI_ — porting Double Q-learning to DQN by selecting the next action with the online network and evaluating it with the target network, reducing overestimation. [^rainbow]: **Hessel, M., et al.** (2018), "Rainbow: Combining Improvements in Deep Reinforcement Learning," _AAAI_ — the combination of double Q-learning, prioritized replay, dueling networks, multi-step returns, distributional RL, and noisy nets, showing the extensions are largely complementary.