TD control: SARSA, Q-learning and the maximization bias

Before this lesson: lesson 02 (Bellman optimality operator, policy improvement, generalized policy iteration), lesson 03 (ε-greedy exploration, incremental means), lesson 04 (TD(0) and the TD error); Jensen's inequality (information theory 03). Time: about 70 minutes, plus the notebook.

---

Why this matters #

Q-learning is the simplest RL method that learns to act from experience alone, and it is the base of DQN, the network that learned to play Atari games from pixels (lesson 06). The difference between on-policy and off-policy learning, which you first meet here, decides which data an algorithm may use: off-policy methods can learn from old data, from other agents or from logs, on-policy methods cannot without corrections. The maximization bias explains why every modern value-based method has some "double" trick: double DQN, and the clipped double Q-learning of TD3 and SAC (lesson 08). It also explains why Q-learning on a fixed dataset (offline RL) overestimates so badly.

1. Predict first #

2. The picture #

From prediction to control: generalized policy iteration with $Q$ #

Lesson 02 showed generalized policy iteration (GPI): evaluate the policy a little, improve it a little, and repeat. Two changes make GPI work without a model.

1. Learn $Q$, not $V$. Greedy improvement with $V$ needs the model: $\pi'(s) = \arg\max_a \big[R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s')\big]$. With action values, the improvement step is just $\pi'(s) = \arg\max_a Q(s, a)$. No $P$, no $R$.

2. Keep exploring. A greedy policy never tries the actions it thinks are worse, so it never learns that they may be better. So we act ε-greedily, as in the bandits of lesson 03: with probability $1 - \varepsilon$ take a greedy action, otherwise a uniformly random action. With $|\mathcal A|$ actions and one greedy action,

The greedy action also gets its share of the random choice. With 4 actions and $\varepsilon = 0.1$, the greedy action has probability $0.925$, not $0.9$; each other action has $0.025$. A policy with $\pi(a \mid s) \ge \varepsilon / |\mathcal A|$ for every action is called ε-soft.

So the loop of every method in this lesson is: in state $s$, pick $a$ ε-greedily from $Q$; observe $r$ and $s'$; move $Q(s, a)$ towards a one-step target $y$:

The policy improves by itself: it is always ε-greedy with respect to the newest $Q$.

Three targets for one transition #

The three methods use the same reward $r$ and differ only in how they value $s'$:

• SARSA: the action $a'$ the agent really takes next: $y = r + \gamma\,Q(s', a')$. The name lists the five things the update uses: $s, a, r, s', a'$.
• Expected SARSA: the average over the agent's own policy: $y = r + \gamma \sum_{a'} \pi(a' \mid s') Q(s', a')$.
• Q-learning: the best action, whatever the agent does next: $y = r + \gamma \max_{a'} Q(s', a')$.

When the episode ends at $s'$, all three targets are just $y = r$ (the value after the end is 0).

Interactive figure: loading…

Cliff walking: careful or bold? #

Cliff walking (Sutton and Barto, Example 6.6) is a $4 \times 12$ grid. The agent starts at S (bottom left) and must reach G (bottom right). The ten cells between them are a cliff. Every step gives $-1$; a step into the cliff gives $-100$ and sends the agent back to S, and the episode goes on. There is no discounting ($\gamma = 1$). The shortest path walks along the edge of the cliff: 13 steps, return $-13$.

Interactive figure: loading…

What you see (and what Sutton and Barto report):

• Q-learning learns $Q^*$. Its greedy path walks along the edge: 13 steps.
• SARSA and expected SARSA learn the values of the ε-greedy policy they follow. Next to the cliff, a random step "down" (probability $\varepsilon / 4 = 0.025$ in each step) costs $-100$. So states next to the edge get low values, and the greedy path keeps a distance from the cliff.
• Online return: SARSA and expected SARSA collect more reward per episode (about $-25$ and $-21$ in the widget, episodes 400–500) than Q-learning (about $-52$), because Q-learning's random steps on the edge often fall into the cliff.
• With $\varepsilon = 0$ the three methods are the same (the ε-greedy policy is greedy), and all learn the edge path here, because the initial values $Q = 0$ are optimistic and drive exploration.

3. Definitions and main results #

On-policy and off-policy #

Two policies play a role in learning. The behaviour policy $\pi_b$ chooses the actions that produce the data. The target policy $\pi$ is the policy whose values we learn.

• A method is on-policy if the target policy is the behaviour policy: it evaluates and improves the same policy that acts. SARSA is on-policy: its target uses $a' \sim \pi_b$, so it learns $Q^{\pi_b}$ of the ε-greedy policy.
• A method is off-policy if the target policy differs from the behaviour policy. Q-learning is off-policy: the data come from the ε-greedy policy, but the target uses the greedy action, so it learns $Q^*$.

Expected SARSA can be either. With $\pi = \pi_b$ in its sum it is on-policy. With a different target policy it is off-policy; with the greedy target policy, $\sum_{a'} \pi(a' \mid s') Q(s', a') = \max_{a'} Q(s', a')$, and expected SARSA is Q-learning.

Why does Q-learning need no importance sampling, unlike off-policy Monte Carlo (lesson 04)? Its target uses only $(s, a, r, s')$. The action $a$ is given (we learn $Q(s, a)$ for that action), and $r, s'$ come from the environment, not from the policy. The next action $a'$ is not sampled at all: the max replaces it. So the target has the same distribution whatever policy chose $a$.

The three updates in one table #

All three use $Q(s, a) \leftarrow Q(s, a) + \alpha\,[y - Q(s, a)]$, with $y = r$ when the episode ends at $s'$:

method	target $y$	needs the next action $a'$?	learns
SARSA	$r + \gamma\,Q(s', a')$, $a'$ = the next action taken	yes	$Q^{\pi_b}$ (on-policy)
expected SARSA	$r + \gamma \sum_{a'} \pi(a' \mid s')\,Q(s', a')$	no	$Q^{\pi}$; less variance than SARSA
Q-learning	$r + \gamma \max_{a'} Q(s', a')$	no	$Q^*$ (off-policy)

Each target is one sample of a Bellman operator. Recall the operators of lesson 02, written for $Q$:

For a fixed table $Q$, the Q-learning target $r + \gamma \max_{a'} Q(s', a')$ has expectation $(TQ)(s, a)$: only $r$ and $s'$ are random. So Q-learning is sampled value iteration. The SARSA target and the expected SARSA target both have expectation $(T^\pi Q)(s, a)$: they are sampled policy evaluation. Expected SARSA removes one source of noise, the random choice of $a'$, so its target has lower variance. This is why it can use larger step sizes (on cliff walking it works even with $\alpha = 1$).

ε-greedy improvement and GLIE #

Is acting ε-greedily with respect to $Q^\pi$ really an improvement? Yes, among ε-soft policies.

Theorem (ε-greedy policy improvement; Sutton and Barto §5.4). Let $\pi$ be ε-soft, and let $\pi'$ be ε-greedy with respect to $Q^\pi$. Then $V^{\pi'}(s) \ge V^\pi(s)$ for every state $s$.

Proof (one line of algebra, then lesson 02)

1. By the policy improvement theorem of lesson 02, it is enough to show $\sum_a \pi'(a \mid s)\,Q^\pi(s, a) \ge V^\pi(s)$ for every $s$.
2. Write $m = |\mathcal A|$. By the definition of $\pi'$, $\sum_a \pi'(a \mid s) Q^\pi(s, a) = \frac{\varepsilon}{m} \sum_a Q^\pi(s, a) + (1 - \varepsilon) \max_a Q^\pi(s, a)$.
3. The weights $w_a = \big(\pi(a \mid s) - \frac{\varepsilon}{m}\big)/(1 - \varepsilon)$ are $\ge 0$ (because $\pi$ is ε-soft) and sum to $\big(1 - \varepsilon\big)/(1 - \varepsilon) = 1$. A maximum is at least any weighted average, so $\max_a Q^\pi(s, a) \ge \sum_a w_a Q^\pi(s, a)$.
4. Put step 3 into step 2: $\sum_a \pi'(a \mid s) Q^\pi(s, a) \ge \frac{\varepsilon}{m} \sum_a Q^\pi(s, a) + \sum_a \big(\pi(a \mid s) - \frac{\varepsilon}{m}\big) Q^\pi(s, a) = \sum_a \pi(a \mid s) Q^\pi(s, a) = V^\pi(s)$. $\blacksquare$

So GPI with ε-greedy policies converges to the best ε-soft policy, not to the optimal policy. To reach $\pi^*$, exploration must fade out, but not too fast. A schedule is GLIE (greedy in the limit with infinite exploration) if

1. every state–action pair is visited infinitely often, and
2. the policy becomes greedy in the limit, $\pi_k(a \mid s) \to 1$ for $a = \arg\max_b Q_k(s, b)$.

For example, ε-greedy with $\varepsilon_k = 1/k$ in episode $k$ is GLIE. Under GLIE and suitable step sizes, tabular SARSA converges to $Q^*$ with probability 1 (Singh, Jaakkola, Littman and Szepesvári, 2000).

Convergence of Q-learning #

Theorem (Watkins and Dayan, 1992). Take a finite MDP with bounded rewards and $\gamma < 1$. Suppose that every pair $(s, a)$ is updated infinitely often, and that the step sizes $\alpha_t(s, a)$ of each pair satisfy the Robbins–Monro conditions

Then tabular Q-learning converges to $Q^*$ with probability 1.

The behaviour policy does not appear in the theorem, apart from visiting every pair: this is what off-policy means. The first condition lets the steps add up to any distance; the second makes the noise die out. For example, $\alpha_t = 1/n_t(s, a)$, where $n_t$ counts the updates of the pair, satisfies both. A constant $\alpha$ violates the second condition: then $Q$ keeps moving around $Q^*$ but stays close when $\alpha$ is small. The proof writes Q-learning as a noisy version of $Q \leftarrow TQ$ and uses the contraction of $T$ from lesson 02 (stochastic approximation; see Jaakkola, Jordan and Singh, 1994).

Theorem: the maximization bias #

Q-learning's target takes a max over estimates that contain noise. This creates a systematic error.

Theorem (maximization bias). Let $\hat X_1, \dots, \hat X_k$ be unbiased estimates of $\mu_1, \dots, \mu_k$, that is $\mathbb E[\hat X_i] = \mu_i$. Then

and the inequality is usually strict.

Proof.

1. For every $j$: $\max_i \hat X_i \ge \hat X_j$.
2. Take expectations: $\mathbb E[\max_i \hat X_i] \ge \mathbb E[\hat X_j] = \mu_j$, for every $j$.
3. The left side does not depend on $j$, so it is also $\ge \max_j \mu_j$. $\blacksquare$

The same result follows from Jensen's inequality, because $x \mapsto \max_i x_i$ is convex (information theory 03). Why is it usually strict? Equality needs $\max_i \hat X_i = \hat X_{j^*}$ almost surely for a best $j^*$. With noise, some other estimate is often the largest, and then the max is above $\hat X_{j^*}$.

In Q-learning. $\max_{a'} Q(s', a')$ is a max of noisy estimates, so the target is too high on average, and bootstrapping carries the error to earlier states. When all actions are equally good, the bias is largest; when one action is much better than the rest, the max almost always picks it and the bias is small.

Interactive figure: loading…

The double estimator and double Q-learning #

The bias comes from using the same noise to choose the maximiser and to evaluate it: the max picks the estimate whose noise happens to be large. The fix is to separate the two jobs.

Double estimator (van Hasselt, 2010). Use two independent sets of unbiased estimates $\hat X$ and $\hat Y$. Choose $i^* = \arg\max_i \hat X_i$ with the first and evaluate it with the second: return $\hat Y_{i^*}$.

Why it is not biased upward. $i^*$ depends only on $\hat X$, and $\hat Y$ is independent of $\hat X$. So, given $i^*$, the expectation of $\hat Y_{i^*}$ is $\mu_{i^*}$, and

It can be biased downward (when $\hat X$ picks a worse action), but never upward.

Double Q-learning keeps two tables $Q_A$ and $Q_B$. At each step, with probability $1/2$ update $Q_A$:

otherwise update $Q_B$ with the roles of $A$ and $B$ swapped. The agent acts ε-greedily with respect to $Q_A + Q_B$. Each sample updates only one table, so the two tables stay (roughly) independent. Double DQN (lesson 06) applies the same idea with the online and target networks.

Sutton and Barto, Example 6.7. From state A, "right" ends the episode with reward 0; "left" goes to state B with reward 0. From B, each of 10 actions ends the episode with a reward drawn from $N(-0.1, 1)$. So "left" is worse on average ($-0.1 < 0$). With $\varepsilon = 0.1$ the best possible frequency of "left" is $\varepsilon / 2 = 5\%$. Q-learning chooses "left" in most early episodes (over 80% around episode 10 in our runs), because $\max_b Q(B, b)$ is overestimated; double Q-learning comes close to 5%. The notebook reproduces this.

Answers to section 1. (1) For SARSA, yes: it learns the values of the policy it follows, random steps included, and so it learns to keep away from the cliff. Q-learning's values ignore its own exploration. Which is right depends on the goal: if the agent will keep exploring (or a robot will keep slipping), SARSA's values are the honest ones. (2) Clearly above 0: about $+0.49$ (section 4).

4. Worked example #

(a) One transition, three targets. $Q(s, a) = 0$, $r = 1$, $\gamma = 0.9$, $\alpha = 0.1$. In $s'$ there are two actions with $Q(s', \cdot) = (1.0, 3.0)$, and $\varepsilon = 0.2$.

1. ε-greedy probabilities in $s'$: action 2 is greedy, so $\pi(a_2 \mid s') = 1 - 0.2 + 0.2/2 = 0.9$ and $\pi(a_1 \mid s') = 0.2/2 = 0.1$.
2. The agent's next action is the exploratory one, $a' = a_1$ (value 1.0).
3. SARSA: $y = 1 + 0.9 \cdot 1.0 = 1.9$, so $Q(s, a) \leftarrow 0 + 0.1\,(1.9 - 0) = 0.19$.
4. Q-learning: $y = 1 + 0.9 \cdot \max(1.0, 3.0) = 1 + 2.7 = 3.7$, so $Q(s, a) \leftarrow 0.37$.
5. Expected SARSA: $\sum_{a'} \pi(a' \mid s') Q(s', a') = 0.1 \cdot 1.0 + 0.9 \cdot 3.0 = 2.8$, so $y = 1 + 0.9 \cdot 2.8 = 3.52$ and $Q(s, a) \leftarrow 0.352$.

SARSA is pulled down by the exploratory action; Q-learning ignores it; expected SARSA uses its probability instead of the sample. If the agent had picked $a' = a_2$, SARSA would give $y = 3.7$, the same as Q-learning. Averaged over $a'$, SARSA's target is $0.1 \cdot 1.9 + 0.9 \cdot 3.7 = 3.52$: exactly the expected SARSA target.

(b) Why Q-learning loses reward on the cliff. On the edge path, the agent spends 11 steps in cells where one action leads into the cliff (S and the ten cells above the cliff). In each of them, the random action is "the wrong one" with probability $\varepsilon/4 = 0.025$. So the chance to fall at least once in one pass is

and each fall costs $-100$ and a restart. Policy evaluation on the grid gives exact numbers: the ε-greedy policy around $Q^*$ (what Q-learning's agent does in the long run) has expected return $-45.8$ per episode; the best ε-greedy policy, which keeps two rows away from the cliff (15 steps), has $-20.7$. This is the policy that SARSA's values aim for; expected SARSA finds it in our runs, and SARSA with $\alpha = 0.5$ often takes the top row (17 steps).

(c) The size of the maximization bias. Ten actions, all with true value 0. Each estimate is the mean of 10 samples from $N(0, 1)$, so it is $N(0, 1/10)$, with standard deviation $1/\sqrt{10} = 0.316$.

1. The expected maximum of 10 independent standard normals is $\mathbb E[\max_i Z_i] = \int x \cdot 10\,\varphi(x)\,\Phi(x)^9\,dx = 1.5388$ (the density of the max of 10 is $10\,\varphi\,\Phi^9$).
2. Scale by the standard deviation: $\mathbb E[\max_i \hat X_i] = 1.5388 / \sqrt{10} = 0.487$.

Every true value is 0, but the max is $0.49$ on average. The double estimator gives 0 on average.

5. In code #

The cells below check the worked example. The notebook adds the full SARSA and Q-learning agents on cliff walking and double Q-learning on Example 6.7.

import numpy as np
from scipy import integrate, stats

def epsilon_greedy_probs(q, eps):
    p = np.full(len(q), eps / len(q))
    best = np.flatnonzero(q == q.max())
    p[best] += (1 - eps) / len(best)            # ties share the greedy mass
    return p

# (a) one transition
r, gamma, alpha, q_next, eps = 1.0, 0.9, 0.1, np.array([1.0, 3.0]), 0.2
pi = epsilon_greedy_probs(q_next, eps)
print(pi)                                        # [0.1 0.9]
y_sarsa = r + gamma * q_next[0]                  # a' = a_1, the exploratory action
y_exp = r + gamma * pi @ q_next
y_q = r + gamma * q_next.max()
print(alpha * np.array([y_sarsa, y_exp, y_q]))   # [0.19  0.352 0.37 ]

# (b) chance to fall at least once on the edge path
print(1 - 0.975 ** 11)                           # 0.2431

# (c) maximization bias: E[max of k standard normals] = ∫ x k φ(x) Φ(x)^(k-1) dx
k = 10
e_max = integrate.quad(lambda x: x * k * stats.norm.pdf(x) * stats.norm.cdf(x) ** (k - 1), -np.inf, np.inf)[0]
print(e_max, e_max / np.sqrt(10))                # 1.5388 0.4866

rng = np.random.default_rng(0)
A = rng.normal(0, 1, (100_000, 10, 10)).mean(axis=2)   # 100k repetitions, 10 actions, 10 samples each
B = rng.normal(0, 1, (100_000, 10, 10)).mean(axis=2)   # an independent second set
single = A.max(axis=1)
double = B[np.arange(len(B)), A.argmax(axis=1)]
print(single.mean().round(3), double.mean().round(3))  # 0.487 0.0 (up to Monte Carlo noise)

6. Where it shows up #

• Deep Q-learning. DQN is Q-learning with a neural network, a replay buffer and a target network; double DQN uses the double estimator (lesson 06).
• Actor-critic methods for continuous control. TD3 and SAC train two critics and use the smaller of the two in the target ("clipped double Q"), a direct answer to the maximization bias (lesson 08).
• Learning from logs. Because it is off-policy, Q-learning can learn from data collected by another policy: recommendation, ad placement, resource allocation. On a fixed dataset the max picks actions the data never tried, the extreme case of the maximization bias (offline RL, lesson 06).
• Safe exploration. SARSA's caution is useful when exploration is costly during learning: a robot or a control system that must not fall while it learns. Expected SARSA is a common default for tabular problems.
• ML for science. Value-based RL is used for sequential experimental design and for the control of physical systems, where each step is an experiment or a control action. There the reward is often a noisy measurement, so the maximization bias makes the learned values too optimistic; double estimators or an evaluation on fresh data give honest numbers.

7. Common mistakes #

• Wrong $a'$ in SARSA. It must be the action you actually take next, and you must then execute that same action. Choosing a fresh action for the next step makes it a different algorithm.
• Bootstrapping at the end. At a terminal transition the target is $r$. A target $r + \gamma \max_{a'} Q(s', \cdot)$ with a terminal $s'$ adds a value that should be 0.
• Wrong ε-greedy probabilities. The greedy action has $1 - \varepsilon + \varepsilon/|\mathcal A|$, not $1 - \varepsilon$. With ties, the greedy mass is shared among the tied actions.
• Mixing up greedy path and online return. Q-learning's greedy path is better on cliff walking, but its online return is worse. Say which one you mean.
• "Q-learning needs importance sampling because it is off-policy." One-step Q-learning does not: its target does not depend on which policy chose $a$. (Multi-step off-policy targets do need corrections.)
• Updating both tables with the same sample in double Q-learning. Then they are no longer independent and the bias comes back. Update one table per sample, chosen at random.
• Mixing reward conventions. Here $r_t$ follows $(s_t, a_t)$; Sutton and Barto write $R_{t+1}$. The updates are the same.

8. Check yourself #

1. Why does control without a model learn $Q$ and not $V$?
   Answer

   The greedy step with $V$ needs the model: $\arg\max_a [R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s')]$. With $Q$ the greedy step is $\arg\max_a Q(s, a)$, with no $P$ and no $R$.
2. With 5 actions and $\varepsilon = 0.2$, what are the ε-greedy probabilities? And with two tied greedy actions?
   Answer

   One greedy action: $1 - 0.2 + 0.04 = 0.84$ for it and $0.04$ for each other action. Two tied greedy actions: each gets $0.04 + 0.8/2 = 0.44$, the other three get $0.04$ each (sum $0.88 + 0.12 = 1$).
3. Why is Q-learning off-policy and SARSA on-policy?
   Answer

   Q-learning's target uses $\max_{a'} Q(s', a')$, the value of the greedy policy, whatever the behaviour policy does, so it learns $Q^*$ from ε-greedy data. SARSA's target uses the action the behaviour policy really takes, so it learns the values of that policy.
4. Expected SARSA uses the greedy policy as its target policy. What algorithm is it?
   Answer

   Q-learning: under the greedy policy, $\sum_{a'} \pi(a' \mid s') Q(s', a') = \max_{a'} Q(s', a')$.
5. Does $\alpha_t = 1/\sqrt{n}$ satisfy the Robbins–Monro conditions? And $\alpha_t = 1/n^2$?
   Answer

   Neither. For $1/\sqrt n$ the first condition holds ($\sum 1/\sqrt n = \infty$), but $\sum (1/\sqrt n)^2 = \sum 1/n = \infty$, so the second fails: the noise never dies out. For $1/n^2$, $\sum 1/n^2 < \infty$, so the first fails: the steps cannot add up to any distance. $\alpha = 1/n^p$ satisfies both for $1/2 < p \le 1$.
6. Show in one line that $\mathbb E[\max_i \hat X_i] \ge \max_i \mu_i$, and say why the double estimator is not biased upward.
   Answer

   $\max_i \hat X_i \ge \hat X_j$ for every $j$; take expectations, then the max over $j$. The double estimator chooses $i^*$ with $\hat X$ and evaluates with an independent $\hat Y$, so $\mathbb E[\hat Y_{i^*}] = \mathbb E[\mu_{i^*}] \le \max_i \mu_i$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Write the SARSA, expected SARSA and Q-learning targets.

   Show answer

2. What is the difference between an on-policy and an off-policy method?

   Show answer

3. What probability does ε-greedy give to the greedy action, with $|\mathcal A|$ actions and no ties?

   Show answer

4. Compute the expected SARSA target for $r = 1$, $\gamma = 0.9$, $Q(s', \cdot) = (1, 3)$, $\varepsilon = 0.2$.

   Show answer

5. Under which conditions does tabular Q-learning converge to $Q^*$?

   Show answer

6. Why does Q-learning have a worse online return than SARSA on cliff walking?

   Show answer

7. State the maximization-bias inequality.

   Show answer

8. Why is the double estimator not biased upward?

   Show answer

9. What is GLIE?

   Show answer

10. Ten actions all have true value 0; each estimate is $N(0, 1/10)$. About how large is the expected max?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "SARSA vs Q-learning?" On-policy vs off-policy target; SARSA learns the values of the exploring policy, Q-learning learns $Q^*$. Tell the cliff-walking story: Q-learning's greedy path is optimal, SARSA's online return is better.
• "Why is Q-learning off-policy, and why does it not need importance sampling?" The target uses the max, not the behaviour action; $a$ is conditioned on and $r, s'$ come from the environment.
• "Where does overestimation in Q-learning come from, and how do you fix it?" The max over noisy estimates (Jensen), carried backwards by bootstrapping. Double Q-learning, double DQN, clipped double Q.
• "When does tabular Q-learning converge?" Every pair visited infinitely often and Robbins–Monro step sizes; it is stochastic approximation of the contraction $T$.
• "Why does expected SARSA have lower variance than SARSA?" It averages over $a'$ exactly instead of sampling it; both have the same expected target.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. epsilon_greedy_probs: the exact action distribution of ε-greedy, with ties; compare with sampled frequencies.
2. q_learning and sarsa on cliff walking: reproduce the greedy paths and the online-return plot.
3. expected_sarsa: check that its greedy path is safe and its online return is the best of the three.
4. max_estimates: single and double estimators by simulation; the single one averages $+0.49$, the double one 0.
5. double_q_learning on Example 6.7: the fraction of "left" actions with Q-learning and with double Q-learning.

11. Watch and read #

RL Course by David Silver - Lecture 5: Model Free ControlGoogle DeepMind · David Silver, UCL RL course · 96 min

GPI with Q, ε-greedy improvement and GLIE, SARSA and Q-learning, with the cliff-walking example.

Temporal Difference Learning (including Q-Learning) | Reinforcement Learning Part 4Mutual Information · 29 min

A visual walk from TD prediction to SARSA and Q-learning; watch the part on on-policy vs off-policy targets.

Q-Learning: Model Free Reinforcement Learning and Temporal Difference LearningSteve Brunton · 36 min

Q-learning as sampled value iteration, explained on the board, with links to control engineering.

DeepMind x UCL RL Lecture Series - Model-free Control [6/13]Google DeepMind · Hado van Hasselt · 101 min

A more recent lecture by the author of double Q-learning; the overestimation part explains the double estimator.

• Richard Sutton and Andrew Barto, Reinforcement Learning: An Introduction, 2nd ed., free PDF: §5.3–5.4 (ε-soft policies and the ε-greedy improvement theorem), §6.4–6.7 (SARSA, Q-learning, expected SARSA, maximization bias and double learning). Example 6.6 is cliff walking, Example 6.7 the maximization-bias MDP.
• Hado van Hasselt, Double Q-learning, NeurIPS 2010: the double estimator and its bias.
• Shangtong Zhang, Python code for Sutton and Barto, cliff walking: compare it with your notebook after you finish the exercises.