Part V · 第 20 章强化学习 · 20.2Part V · Ch. 20 Reinforcement Learning · 20.2

Value-based 方法：Q-learning 与 DQNValue-Based Methods: Q-Learning & DQN

值迭代要先知道环境模型 $P(s'\mid s,a)$，而机器人几乎从不知道它：轮子怎么打滑、物体怎么被推开，只能试了才知道。Value-based 方法直接从一条条经验 $(s,a,r,s')$ 里学动作价值 $Q(s,a)$，每一步都用"一步奖励 + 下一状态的估计"去修正当前估计（时序差分）。本课在浏览器里现场训练：随机游走上的 TD 与蒙特卡洛、格子世界里的 Q-learning 与探索陷阱、悬崖边的 SARSA 与 Q-learning、最大化偏差与 Double Q、"致命三元组"导致的发散，以及一个带经验回放和目标网络的 DQN。 Value iteration needs the model $P(s'\mid s,a)$ up front, and a robot almost never has it: how the wheels slip or how an object slides when pushed is known only by trying. Value-based methods learn the action value $Q(s,a)$ directly from experience tuples $(s,a,r,s')$, correcting each estimate with "one step of reward plus the estimate at the next state" (temporal-difference learning). This lesson trains everything live in the browser: TD versus Monte Carlo on a random walk, Q-learning and an exploration trap in a grid world, SARSA versus Q-learning at the cliff, maximization bias and double Q-learning, divergence from the "deadly triad", and a DQN with a replay buffer and a target network.

约 45 分钟~45 min 前置：20.1 MDP 与 Bellman 方程 · 6.12 动态规划 · 6.4 随机梯度下降 · 16.2 损失函数Prereqs: 20.1 MDPs & Bellman equations · 6.12 Dynamic programming · 6.4 SGD · 16.2 Losses 6 个交互6 interactives

1为什么机器人需要它Why robots need this

6.12 节的值迭代和 20.1 节的策略迭代都在解 Bellman 方程，但它们要先拿到环境模型：每个状态、每个动作之后会以多大概率到达哪里、得到多少奖励。对一个在仓库里跑的移动机器人、一只在杂物堆里抓东西的机械臂来说，这张表根本写不出来：地面摩擦、物体质量、接触时的滑动，都只能试了才知道。

无模型 (model-free) 方法放弃写出 $P$，只用机器人亲身经历的一条条转移 $(s,a,r,s')$：在状态 $s$ 做了动作 $a$，拿到奖励 $r$，到了 $s'$。Value-based 方法用这些样本去学动作价值函数 $Q(s,a)$（"在 $s$ 做 $a$，之后一直做得最好，能拿到的期望折扣回报"），策略就直接读出来：$\pi(s)=\arg\max_a Q(s,a)$，不需要模型，也不需要单独的策略网络。

这一族方法还有一个对真实机器人非常宝贵的性质：off-policy。Q-learning 学的是最优策略的价值，但数据可以来自任何行为：昨天的随机探索、旧版本的策略、人类遥操作。所有采到的数据都能存起来反复用（经验回放），这正是 DQN 能从像素玩 Atari 游戏、QT-Opt 能用真实抓取数据训练抓取策略的原因。本课从最小的表格开始，一路走到神经网络版本 DQN，并看清楚它在哪里会坏掉：探索不足、高估、以及函数逼近带来的发散。

The value iteration of Lesson 6.12 and the policy iteration of Lesson 20.1 both solve the Bellman equation, but they need the environment model first: for every state and action, where you land with what probability and what reward you get. For a mobile robot in a warehouse or an arm picking from clutter, that table simply cannot be written down: floor friction, object masses and slipping contacts are known only by trying.

Model-free methods give up on writing $P$ and use only the transitions $(s,a,r,s')$ the robot actually experiences: in state $s$ it took action $a$, received reward $r$ and landed in $s'$. Value-based methods use these samples to learn the action-value function $Q(s,a)$ ("the expected discounted return from doing $a$ in $s$ and acting optimally afterwards"), and the policy is read off directly, $\pi(s)=\arg\max_a Q(s,a)$, with no model and no separate policy network.

This family has one more property that is precious on real robots: it is off-policy. Q-learning learns the value of the optimal policy, but its data can come from any behaviour: yesterday's random exploration, an older policy, human teleoperation. Everything collected can be stored and reused (experience replay), which is how DQN learned Atari games from pixels and how QT-Opt trained grasping from real grasp attempts. This lesson starts from the smallest table, goes all the way to the neural version, DQN, and shows exactly where it breaks: too little exploration, overestimation, and divergence under function approximation.

2直觉：从样本里学价值，等回合结束还是只看一步？Intuition: learning a value from samples, wait for the end or look one step ahead?

先只学"一个状态有多好"（固定策略下的 $V(s)$），不选动作。一个机器人在 5 格走廊 A–E 上随机漂移（各一半概率向左、向右），从中间 C 出发；走出右端到达充电桩得奖励 $+1$，走出左端得 0，回合结束。不打折 ($\gamma=1$)，所以 $V(s)$ 就是"从 $s$ 出发最终到右端的概率"，真值是 $1/6,\dots,5/6$。机器人不知道这些，只看到一条条回合。

有两种自然的学法。蒙特卡洛 (MC)：等回合结束，拿到真实回报 $G$（这里是 0 或 1），把这一回合访问过的每个格子的估计往 $G$ 拉一点：$V(s)\leftarrow V(s)+\alpha\,[\hl{mcret}{G}-V(s)]$。时序差分 TD(0)：不等结局，每走一步就用"一步奖励 + 下一个格子现在的估计"当目标：$V(s)\leftarrow V(s)+\alpha\,[\hl{tdtarget}{r+\gamma V(s')}-V(s)]$。后者叫自举 (bootstrapping)：用估计去更新估计。

Start by learning only "how good a state is" ($V(s)$ under a fixed policy), with no action choice. A robot drifts randomly along a 5-cell corridor A–E (left or right with probability one half each), starting in the middle at C; leaving the right end reaches the charger for a reward of $+1$, leaving the left end gives 0, and the episode ends. There is no discount ($\gamma=1$), so $V(s)$ is "the probability of eventually leaving on the right", with true values $1/6,\dots,5/6$. The robot knows none of this; it only sees episodes.

There are two natural ways to learn. Monte Carlo (MC): wait until the episode ends, take the actual return $G$ (here 0 or 1) and pull the estimate of every cell visited in that episode a little toward it: $V(s)\leftarrow V(s)+\alpha\,[\hl{mcret}{G}-V(s)]$. Temporal difference, TD(0): don't wait for the outcome; after every step use "one step of reward plus the current estimate at the next cell" as the target: $V(s)\leftarrow V(s)+\alpha\,[\hl{tdtarget}{r+\gamma V(s')}-V(s)]$. The latter is called bootstrapping: updating an estimate from an estimate.

FIG 1走廊上的随机游走：TD(0) 与蒙特卡洛A random walk on a corridor: TD(0) versus Monte Carlo

均方根误差 vs 回合数RMS error vs. episodes

上：走廊，琥珀色圆点是机器人。下：每个格子的估计，蓝色柱是 TD(0)，紫色柱是 MC，绿色虚线是真值；有琥珀色描边的柱子是上一回合被改动过的。右图：粗线是 100 次独立运行的平均均方根误差（当前步长下），细线是你正在看的这一次运行。两种方法看到的是同一串回合。估计的初值都是 0.5。 Top: the corridor; the amber dot is the robot. Bottom: each cell's estimate, blue bars for TD(0), purple bars for MC, green dashes for the true value; bars outlined in amber were changed by the last episode. Right: thick lines are the RMS error averaged over 100 independent runs (at the current step sizes), thin lines are the single run you are watching. Both methods see the same sequence of episodes. All estimates start at 0.5.

试一试Try this

按"重置"再按"1 个回合"，只走一个回合：数一数每种方法改了几个格子。MC 改了所有访问过的格子；TD 只改了最后一格，因为其余每一步的目标 $0+V(s')=0.5$ 恰好等于当前估计。Press "Reset", then "1 episode" to play a single episode, and count how many cells each method changed. MC changes every visited cell; TD changes only the last one, because at every other step the target $0+V(s')=0.5$ equals the current estimate.
把 $\alpha_{\rm TD}$ 拖到 0.3 以上：蓝色粗线一开始降得更快，但停在更高的误差上（第 100 回合约 0.11，而 $\alpha=0.1$ 时约 0.05）。大步长学得快，但噪声也更大。Drag $\alpha_{\rm TD}$ above 0.3: the thick blue line drops faster at first but levels off at a higher error (about 0.11 at episode 100, against about 0.05 for $\alpha=0.1$). A large step learns fast but is noisier.

默认步长下（$\alpha_{\rm TD}=0.1$，$\alpha_{\rm MC}=0.02$），100 个回合后 TD 的平均误差约 0.053，MC 约 0.079。把 $\alpha_{\rm MC}$ 在整个范围里调一遍，你会发现 MC 在第 100 回合最好也只到 0.08 左右。原因在于方差：MC 的目标 $G$ 是一整个回合的随机结局，它对 C 的估计要等很多回合"抛硬币"的结果平均下来；TD 的目标只依赖一步的随机性，其余部分由邻居的估计提供，而邻居的估计已经平均过许多回合了。代价是偏差：在估计还不准时，TD 的目标也不准。

At the default step sizes ($\alpha_{\rm TD}=0.1$, $\alpha_{\rm MC}=0.02$) TD's average error after 100 episodes is about 0.053 and MC's about 0.079. Sweep $\alpha_{\rm MC}$ over its whole range and MC never gets much below 0.08 at episode 100. The reason is variance: MC's target $G$ is the random outcome of a whole episode, so its estimate of C must average many "coin flips" of whole episodes; TD's target depends on the randomness of one step, and the rest comes from the neighbour's estimate, which has already averaged over many episodes. The price is bias: while the estimates are still wrong, so is TD's target.

核心洞见Key insight

TD(0) 就是 6.12 节里的 Bellman 备份，只是把对 $s'$ 的期望 $\sum_{s'}P(s'|s,a)[\cdots]$ 换成了一个样本，再用小步长 $\alpha$ 在许多样本上做平均。环境自己"掷骰子"代替了我们不知道的 $P$。这是本课所有方法的共同骨架。

TD(0) is the Bellman backup of Lesson 6.12 with the expectation over $s'$, $\sum_{s'}P(s'|s,a)[\cdots]$, replaced by one sample, and a small step $\alpha$ averaging over many samples. The environment "rolling its own dice" stands in for the $P$ we do not know. This is the common skeleton of every method in this lesson.

3动手：机器人用 Q-learning 找充电桩Play: a robot finds its dock with Q-learning

要选动作，光有 $V$ 不够（没有模型就不知道哪个动作通向哪个 $s'$），所以我们学 $Q(s,a)$。Q-learning（Watkins, 1989）对每个转移 $(s,a,r,s')$ 做一次 TD 更新，目标里取下一个状态最好的动作：

To choose actions, $V$ alone is not enough (without a model we don't know which action leads to which $s'$), so we learn $Q(s,a)$. Q-learning (Watkins, 1989) applies one TD update per transition $(s,a,r,s')$, taking the best action at the next state in the target:

$$ \hl{qsa}{Q(s,a)}\ \leftarrow\ Q(s,a)+\alpha\Big[\,r+\gamma\,\hl{qmax}{\max_{a'}Q(s',a')}-Q(s,a)\,\Big] $$

下面是一个仓库：机器人从 S 出发，每步可以上下左右走一格（撞墙原地不动），$\gamma=0.9$。左下角有一个小充电点（奖励 $+0.3$，3 步可达），右边墙后有正式充电桩（奖励 $+1$，最短 8 步）。到达任何一个都结束回合。哪个更好？从 S 出发，小充电点值 $0.3\cdot0.9^2=0.243$，充电桩值 $0.9^7\approx0.478$：远的更好。机器人按 ε-greedy 行动：以概率 $\varepsilon$ 随机走一步，否则走当前 $Q$ 最大的动作。

每个格子被分成 4 个三角形，分别是向右、上、左、下 4 个动作的 $Q$ 值，蓝色越浓 $Q$ 越大。先按"单步"看几次更新的具体数字，再按"训练"。

Below is a warehouse: the robot starts at S and each step moves one cell up, down, left or right (bumping into a wall leaves it in place), with $\gamma=0.9$. In the bottom-left corner is a small charging pad (reward $+0.3$, 3 steps away); behind the wall on the right is the proper dock (reward $+1$, at least 8 steps away). Reaching either ends the episode. Which is better? From S the pad is worth $0.3\cdot0.9^2=0.243$ and the dock $0.9^7\approx0.478$: the far one wins. The robot acts ε-greedily: with probability $\varepsilon$ it takes a random step, otherwise the action with the largest current $Q$.

Each cell is split into 4 triangles holding the $Q$ values of its 4 actions (right, up, left, down); more saturated blue means larger $Q$. Press "Step" a few times to read the numbers of individual updates, then press "Train".

FIG 2格子世界里的 Q-learningQ-learning in a grid world

每回合结束后，贪心策略从 S 出发的回报return of the greedy policy from S after each episode

琥珀色圆点是机器人，细琥珀色线是它这一回合走过的路；紫色粗线是按当前 $Q$ 贪心地从 S 走出的路线。实线琥珀色框住的三角形是刚刚更新的 $Q(s,a)$，虚线琥珀色框住的是目标里用到的 $\max_{a'}Q(s',a')$。青色格是小充电点，绿色格是充电桩，填满的实心格是墙。"显示 $Q^\star$"会换成用模型做值迭代得到的正确答案（机器人本身看不到它）。右图绿色虚线是最优值 0.478，青色虚线是去小充电点的 0.243。 The amber dot is the robot and the thin amber line its path in this episode; the thick purple line is the route taken greedily from S under the current $Q$. The triangle with a solid amber outline is the $Q(s,a)$ just updated; the one with a dashed amber outline is the $\max_{a'}Q(s',a')$ used in its target. The cyan cell is the small pad, the green cell the dock, solid cells are walls. "Show $Q^\star$" swaps in the right answer computed by value iteration with the model (which the robot never sees). In the right chart the green dashes mark the optimum 0.478 and the cyan dashes the pad's 0.243.

按"单步"，看右上角的更新公式：只要机器人还没碰到任何充电点，每次更新都是 $0\to0$（奖励是 0，下一格的 $Q$ 也都是 0）。一直按到出现第一个非零更新为止。Press "Step" and read the update formula at the top right: until the robot touches a charger, every update is $0\to0$ (the reward is 0 and so are the next cell's $Q$ values). Keep pressing until the first nonzero update appears.
保持默认（初值 $Q=0$，$\varepsilon=0.1$），按"训练"跑满 200 个回合：机器人学会了去小充电点，贪心回报停在 0.243，而最优是 0.478。再把 $\varepsilon$ 提到 0.5 多跑几百回合，它通常还是找不到充电桩。With the defaults (initial $Q=0$, $\varepsilon=0.1$), press "Train" and run 200 episodes: the robot has learned to go to the small pad; the greedy return is stuck at 0.243 while the optimum is 0.478. Raise $\varepsilon$ to 0.5 and run a few hundred more episodes: it usually still never finds the dock.
在图头把初值换成"乐观初值 $Q=1$"（会自动重置），再训练：不到 30 个回合贪心路线就变成了去充电桩的 8 步最优路线（右图回报到达 0.478）。In the figure header switch to "optimistic $Q = 1$" (this resets), then train: within 30 episodes the greedy route becomes the optimal 8-step route to the dock (the chart's return reaches 0.478).

注意价值是怎么传播的：第一次碰到充电点时只有最后那一个 $Q(s,a)$ 变成非零；下一次走到它前一格，目标里的 $\max_{a'}Q(s',a')$ 已经非零了，价值又往回传一格。这和 6.12 节 FIG 1 里"从目标向外涨水"是同一件事，只不过这里水只沿着机器人实际走过的路涨。

第二件事是探索陷阱。初值 $Q=0$ 时，机器人一旦碰到小充电点，那里的 $Q$ 就成了全图唯一的正数，贪心动作全都指向它；要发现充电桩，得连续很多步都随机地走对方向，ε-greedy 这种"每步独立抖一下"的探索几乎做不到（在本图里，20 个随机种子、500 个回合、$\varepsilon$ 最大到 0.5，一次都没有让贪心策略改去充电桩）。乐观初值把所有没试过的动作都假设成"很好"（$Q=1$ 不小于任何真实值），贪心策略自己就会去试每一个还没被证明不好的动作，于是 $\varepsilon=0$ 也能系统地探索整个仓库。

Watch how value propagates: the first time the robot touches a charger only that last $Q(s,a)$ becomes nonzero; the next time it passes the cell before, the $\max_{a'}Q(s',a')$ in its target is already nonzero and the value moves one cell further back. This is the "water rising outward from the goal" of FIG 1 in Lesson 6.12, except that here the water rises only along paths the robot actually walked.

The second lesson is the exploration trap. With initial $Q=0$, once the robot touches the small pad, its $Q$ is the only positive number on the map and every greedy action points toward it; to discover the dock the robot must take the right random direction many steps in a row, which ε-greedy's "independent jitter at each step" almost never does (in this figure, 20 random seeds, 500 episodes and $\varepsilon$ up to 0.5 never once made the greedy policy switch to the dock). Optimistic initialization assumes every untried action is "great" ($Q=1$ is at least any true value), so the greedy policy itself tries every action not yet proven bad, and even $\varepsilon=0$ explores the whole warehouse systematically.

核心洞见Key insight

Q-learning 保证收敛到 $Q^\star$，前提是每个状态–动作对都被无限次地访问（再加上合适递减的步长）。这个前提不是自动成立的：学到什么，取决于机器人去过哪里。在大状态空间里，探索往往比更新公式本身更难。

Q-learning is guaranteed to converge to $Q^\star$ provided every state–action pair is visited infinitely often (plus suitably decaying step sizes). That premise does not hold by itself: what is learned depends on where the robot has been. In large state spaces exploration is often harder than the update rule itself.

4两个视角：on-policy 与 off-policy，以及"取最大"的偏差Two views: on-policy versus off-policy, and the bias of taking a max

SARSA 与 Q-learning：在悬崖边学习SARSA versus Q-learning: learning next to a cliff

只改目标里的一项，就得到另一个算法。SARSA（名字来自它用到的五元组 $s,a,r,s',a'$）不取最大，而用机器人下一步真的要做的动作 $a'$（同样按 ε-greedy 选出）：

Change one term in the target and you get another algorithm. SARSA (named after the quintuple $s,a,r,s',a'$ it uses) does not take the max; it uses the action $a'$ the robot will actually take next (chosen ε-greedily as well):

左边是 SARSA，右边是 Q-learning，只有目标里的一项不同：

SARSA on the left, Q-learning on the right; they differ in a single term of the target:

$$ Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma\,\hl{sarsa}{Q(s',a')}-Q(s,a)\big]\qquad\qquad Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma\,\hl{qmax}{\max_{a'}Q(s',a')}-Q(s,a)\big] $$

SARSA 估计的是"我这个（会探索、偶尔犯错的）策略"的价值，叫 on-policy；Q-learning 估计的是"如果以后都做最优动作"的价值，与产生数据的行为无关，叫 off-policy。区别在 6.12 节那种悬崖旁边最明显：Sutton & Barto 的悬崖行走，$12\times4$ 的格子，每步奖励 $-1$，掉下悬崖 $-100$ 并被送回起点。两种算法都用 $\varepsilon=0.1$、$\alpha=0.5$、$\gamma=1$。

SARSA estimates the value of "this (exploring, occasionally clumsy) policy of mine": it is on-policy. Q-learning estimates the value of "acting optimally from now on", whatever behaviour produced the data: it is off-policy. The difference is starkest next to a cliff like the one in Lesson 6.12: Sutton & Barto's cliff walking, a $12\times4$ grid, reward $-1$ per step, $-100$ for falling off the cliff and a trip back to the start. Both algorithms use $\varepsilon=0.1$, $\alpha=0.5$, $\gamma=1$.

FIG 3悬崖行走：SARSA（紫）与 Q-learning（蓝）Cliff walking: SARSA (purple) and Q-learning (blue)

每回合的训练回报（50 次运行平均，10 回合滑动平均）online return per episode (mean of 50 runs, 10-episode moving average)

红色格是悬崖。左图画的是第 1 次运行学到的贪心路线（不再探索时会走的路）：紫色是 SARSA，蓝色是 Q-learning。右图是训练中（带 ε 探索）每回合拿到的回报；绿色虚线是最短路线的回报 $-13$。改变 $\varepsilon$ 会从头重新训练。 Red cells are the cliff. The left panel shows the greedy route learned in run 1 (the path taken once exploration stops): purple for SARSA, blue for Q-learning. The right panel shows the return obtained per episode during training (with ε exploration); the green dashes mark the shortest route's return $-13$. Changing $\varepsilon$ retrains from scratch.

在 $\varepsilon=0.1$ 时按"运行"，训练满 500 个回合：Q-learning 学到了贴着悬崖的最短路线（贪心回报 $-13$），SARSA 学到了绕到最上面一排的安全路线（$-17$）；可是训练中的回报反过来，最后 100 回合 SARSA 约 $-27$，Q-learning 约 $-51$。At $\varepsilon=0.1$ press "Run" and train the full 500 episodes: Q-learning learns the shortest route along the cliff edge (greedy return $-13$), SARSA a safe route along the top row ($-17$); yet the online returns are the other way round, about $-27$ for SARSA and $-51$ for Q-learning over the last 100 episodes.
把 $\varepsilon$ 降到 0.01 再训练满 500 回合：探索几乎不再害人掉崖，两条曲线靠拢（约 $-17$ 和 $-16$），SARSA 的路线也挪近了悬崖。Lower $\varepsilon$ to 0.01 and train 500 episodes again: exploration hardly ever throws the robot off the cliff any more, the two curves come together (about $-17$ and $-16$), and SARSA's route moves closer to the cliff.

Q-learning 学到的是"不探索时"的最优值，所以贴边走；但训练时它仍有 10% 的概率随机迈一步，贴边时迈向悬崖就是 $-100$（最后 100 回合平均每回合掉下去约 0.35 次，SARSA 约 0.05 次）。SARSA 把自己的探索也算进了价值：贴边的格子"对一个会抖的机器人"确实危险，所以它绕远。哪个对？取决于部署时会不会继续探索。一个在真实世界边用边学的机器人，训练中摔一次的代价是真实的，SARSA 式的保守更接近你想要的；如果只在仿真里训练、上线后贪心执行，Q-learning 的路线更好。

Q-learning learns the optimal values "without exploration", so it walks the edge; but during training it still takes a random step 10% of the time, and a random step toward the cliff from the edge costs $-100$ (over the last 100 episodes it falls about 0.35 times per episode, SARSA about 0.05). SARSA folds its own exploration into the values: for a robot that jitters, edge cells really are dangerous, so it detours. Which is right? It depends on whether exploration continues at deployment. For a robot that learns while working in the real world, every training fall is a real cost and SARSA-style caution is closer to what you want; if you train in simulation and then execute greedily, Q-learning's route is better.

最大化偏差与 Double Q-learningMaximization bias and double Q-learning

Q-learning 的目标里有一个 $\max$。如果几个动作的真实价值都一样，但估计带噪声，那么"估计里最大的那个"系统性地偏高：最大值挑中的正是碰巧被高估的那个。数学上就是 $\mathbb E[\max_a\hat Q(s,a)]\ \ge\ \max_a\mathbb E[\hat Q(s,a)]$。这个偏高再被自举一步步往回传。

Sutton & Barto 的例子 6.7：从 A 出发，向右立即结束（奖励 0）；向左到 B（奖励 0），B 有 $n$ 个动作，每个都以奖励 $\mathcal N(\mu,1)$ 结束，$\mu=-0.1$。向左的真实价值是 $-0.1$，所以最优是一直向右；在 $\varepsilon=0.1$ 下，最好的行为是只有 $\varepsilon/2=5\%$ 的回合向左。想象成机器人在路口：右边是安全的回充点，左边是一个有 $n$ 种抓取方式的工作台，每种平均略亏、但单次结果噪声很大。Double Q-learning（van Hasselt, 2010）维护两张表，用一张选最大动作、用另一张估它的值，两张表的噪声互相独立，就不会"自己挑自己的高估"。

Q-learning's target contains a $\max$. If several actions have the same true value but noisy estimates, then "the largest estimate" is systematically too high: the max picks exactly the one that happens to be overestimated. In symbols, $\mathbb E[\max_a\hat Q(s,a)]\ \ge\ \max_a\mathbb E[\hat Q(s,a)]$. Bootstrapping then passes this excess back step by step.

Sutton & Barto's Example 6.7: from A, going right ends the episode at once (reward 0); going left leads to B (reward 0), where $n$ actions each end the episode with reward $\mathcal N(\mu,1)$, $\mu=-0.1$. Going left is truly worth $-0.1$, so the optimum is always right; under $\varepsilon=0.1$ the best possible behaviour goes left in only $\varepsilon/2=5\%$ of episodes. Picture a robot at a junction: to the right a safe charger, to the left a workbench with $n$ ways to grasp, each slightly losing on average but very noisy in any single try. Double Q-learning (van Hasselt, 2010) keeps two tables, uses one to select the maximizing action and the other to evaluate it; their noise is independent, so a table never "picks its own overestimate".

FIG 4最大化偏差：Q-learning（蓝）与 Double Q-learning（紫）Maximization bias: Q-learning (blue) and double Q-learning (purple)

左：在 A 选择向左的回合比例（500 次独立运行的平均），$\varepsilon=0.1$，$\alpha=0.1$。绿色虚线是最优行为的比例（$\mu<0$ 时 5%，$\mu>0$ 时 95%）。右：这个小 MDP，B 处的动作个数随 $n$ 改变。 Left: fraction of episodes that go left at A (mean of 500 independent runs), $\varepsilon=0.1$, $\alpha=0.1$. The green dashes mark the optimal behaviour (5% when $\mu<0$, 95% when $\mu>0$). Right: the little MDP; the number of actions at B follows $n$.

把 B 的动作数 $n$ 从 1 拖到 10 或更多：蓝色曲线在最初几十个回合冲到 90% 以上（Q-learning 被"某个动作偶然很好"骗去了左边），紫色曲线基本不受影响。$n=1$ 时没有可"挑"的，两条曲线几乎一样。Drag the number of actions at B, $n$, from 1 to 10 or more: the blue curve shoots above 90% in the first few dozen episodes (Q-learning is lured left by "some action that happened to look great"), while the purple curve is barely affected. At $n=1$ there is nothing to pick from and the two curves almost coincide.

5从表格到网络：致命三元组与 DQNFrom tables to networks: the deadly triad and DQN

表格在 6.12 节讲的维数灾难面前不堪一击：一张相机图像的状态数是天文数字。办法是用带参数 $\theta$ 的函数 $Q_\theta(s,a)$（线性特征或神经网络）代替表格，相似的状态共享参数，学一处也改变了别处。可这正是麻烦的来源：一次更新会牵动其他状态的估计，而 TD 的目标本身又依赖这些估计。

Sutton & Barto 把危险归结为三样东西同时出现，称为致命三元组 (deadly triad)：函数逼近、自举、off-policy 数据。下面是最小的例子：两个状态，特征分别是 1 和 2，线性估计 $\hat v(s_1)=w$，$\hat v(s_2)=2w$；$s_1\to s_2$ 和 $s_2\to$终点，奖励都是 0，所以真值全是 0，$w=0$ 就是完美答案。如果数据里只有 $s_1\to s_2$ 这一种转移（比如 off-policy 的行为从不经过 $s_2$ 之后的那段），TD 更新是

Tables collapse under the curse of dimensionality of Lesson 6.12: a camera image has an astronomical number of states. The remedy is a parametric function $Q_\theta(s,a)$ (linear features or a neural network) in place of the table, so that similar states share parameters and learning in one place changes others too. That is exactly the source of trouble: one update moves the estimates of other states, and the TD target itself depends on those estimates.

Sutton & Barto boil the danger down to three ingredients appearing together, the deadly triad: function approximation, bootstrapping and off-policy data. Here is the smallest example: two states with features 1 and 2 and linear estimates $\hat v(s_1)=w$, $\hat v(s_2)=2w$; $s_1\to s_2$ and $s_2\to$ end both give reward 0, so all true values are 0 and $w=0$ is the perfect answer. If the data contain only the $s_1\to s_2$ transition (say an off-policy behaviour never visits what comes after $s_2$), the TD update is

$$ w\ \leftarrow\ w+\alpha\big[\,0+\gamma\,\hl{boot}{\hat v(s_2)}-\hat v(s_1)\big]\,\hl{fa}{\phi(s_1)} = w+\alpha\,(2\gamma w-w)=\big(1+\alpha(2\gamma-1)\big)\,w,\qquad \hl{off}{\mathcal D=\{s_1\to s_2\}} $$

当 $\gamma>0.5$ 时每次更新都把 $w$ 乘以一个大于 1 的数：为了让 $s_1$ 的值追上目标 $2\gamma w$，增大 $w$，可目标也跟着一起变大，永远追不上。

For $\gamma>0.5$ every update multiplies $w$ by a number larger than 1: to make $s_1$'s value catch up with its target $2\gamma w$ we increase $w$, but the target grows along with it and is never caught.

FIG 5致命三元组：三样同时打开才会发散The deadly triad: divergence needs all three

左：两个估计值的绝对值随更新次数的变化（对数纵轴），蓝色是 $\hat v(s_1)$，紫色是 $\hat v(s_2)$；真值都是 0，所以越往下越好。用的是期望更新，没有采样噪声。右：两个状态的示意图。三个开关分别关掉三元组中的一项："表格"让两个状态各有自己的参数 $w_1,w_2$；"蒙特卡洛目标"用真实回报 0 当目标；"on-policy"让两种转移轮流出现在数据里。 Left: the absolute values of the two estimates against the number of updates (log vertical axis), blue for $\hat v(s_1)$, purple for $\hat v(s_2)$; both true values are 0, so lower is better. These are expected updates with no sampling noise. Right: a sketch of the two states. Each switch removes one leg of the triad: "table" gives each state its own parameter $w_1,w_2$; "Monte Carlo target" uses the actual return 0 as the target; "on-policy" lets both transitions appear in the data in turn.

三样都开着时，把 $\gamma$ 从 0.9 往下拖，找到 $w$ 不再增长的位置：$\gamma\le0.5$，此时每步的放大因子 $1+\alpha(2\gamma-1)\le1$。With all three on, drag $\gamma$ down from 0.9 and find where $w$ stops growing: $\gamma\le0.5$, where the per-update factor $1+\alpha(2\gamma-1)\le1$.
在 $\gamma\ge0.8$ 下，每次只关掉一样，三样都试一遍：无论关掉哪一样，发散都消失了。At $\gamma\ge0.8$, switch off one ingredient at a time and try all three: whichever one you remove, the divergence disappears.

on-policy 为什么能救？因为数据里也有 $s_2\to$终点，那次更新把 $\hat v(s_2)=2w$ 往 0 拉，拉的力度（$\alpha\cdot2w\cdot2$）比前一次的放大大得多。off-policy 的数据分布恰好"看不到"会纠错的那部分。Q-learning 天生就是 off-policy 的（目标里的 $\max$ 对应的贪心策略不是产生数据的 ε-greedy 策略），深度网络是函数逼近，TD 目标是自举：DQN 正好坐在三元组的正中间。它能工作，靠的是两个工程手段把危险压住。

Why does on-policy data help? Because the data also contain $s_2\to$ end, and that update pulls $\hat v(s_2)=2w$ toward 0 with a force ($\alpha\cdot2w\cdot2$) much larger than the previous amplification. The off-policy distribution happens to "miss" exactly the part that would correct the error. Q-learning is off-policy by nature (the greedy policy behind the $\max$ is not the ε-greedy policy that produced the data), a deep network is function approximation, and the TD target bootstraps: DQN sits right in the middle of the triad. It works thanks to two engineering devices that hold the danger down.

DQN：经验回放 + 目标网络DQN: experience replay + a target network

DQN（Mnih 等, Nature 2015）把 Q-learning 写成一个回归问题：网络输入状态，输出每个离散动作的 $Q$ 值，最小化 TD 误差的 Huber 损失（它对误差的梯度就是截断到 $[-1,1]$ 的 TD 误差，即 DQN 论文里的"误差截断"，见 16.2 节）：

DQN (Mnih et al., Nature 2015) writes Q-learning as a regression problem: the network takes the state and outputs one $Q$ value per discrete action, and it minimizes a Huber loss of the TD error (its gradient is the TD error clipped to $[-1,1]$, the "error clipping" of the DQN paper; see Lesson 16.2):

$$ \mathcal L(\theta)=\mathbb E_{\hl{replay}{(s,a,r,s')\sim\mathcal D}}\Big[\,\ell\Big(r+\gamma\,(1-d)\max_{a'}\hl{tgt}{Q_{\theta^-}(s',a')}-Q_\theta(s,a)\Big)\Big],\qquad \theta^-\leftarrow\theta $$

其中 $\ell$ 是 Huber 损失，$d=1$ 表示 $s'$ 是终止状态，目标网络参数 $\theta^-$ 每 $C$ 次更新才从 $\theta$ 复制一次。两个关键部件：

经验回放 $\mathcal D$（Lin, 1992）：把所有转移存进一个大缓冲区，每次更新从中随机抽一小批。连续采到的转移高度相关（机器人一直在同一片区域），直接用它们训练就像只看同一个角落的 SGD（6.4 节的 SGD 假设样本近似独立）；随机抽样打散了相关性，每条数据还能被反复利用。
目标网络 $\theta^-$：目标里的 $Q$ 用一份冻结的参数副本计算，每 $C$ 次更新才同步一次。这样回归目标在一段时间内是固定的，不会出现 FIG 5 里"追着自己跑"的放大循环。

下面的 DQN 控制一个在房间里的点机器人：状态是连续的位置 $(x,y)$，4 个动作各移动 0.08，中间有一堵墙，到达右上方的绿色圆得 $+1$，$\gamma=0.95$，一回合最多 40 步（到时截断，截断不是终止，目标照常自举）。网络是 2–32–32–4 的 ReLU MLP，Adam 学习率 0.002，每个环境步做一次 32 个样本的更新，$C=200$，ε 在前 3000 步从 1 线性降到 0.1。每 1000 步，用贪心策略从墙左边 30 个固定起点各跑一次做评估。

where $\ell$ is the Huber loss, $d=1$ marks a terminal $s'$, and the target parameters $\theta^-$ are copied from $\theta$ only once every $C$ updates. The two key parts:

Experience replay $\mathcal D$ (Lin, 1992): store every transition in a large buffer and draw each mini-batch from it at random. Consecutive transitions are strongly correlated (the robot stays in one area for a while), and training on them directly is like SGD that only ever sees one corner (the SGD of Lesson 6.4 assumes roughly independent samples); random draws break the correlation, and every transition is reused many times.
A target network $\theta^-$: the $Q$ in the target is computed with a frozen copy of the parameters, synchronized only every $C$ updates. The regression target therefore stays fixed for a while, and the "chasing your own tail" amplification of FIG 5 cannot take hold.

The DQN below controls a point robot in a room: the state is the continuous position $(x,y)$, the 4 actions each move 0.08, a wall stands in the middle, reaching the green disc at the top right gives $+1$, $\gamma=0.95$, and an episode lasts at most 40 steps (then it is truncated; truncation is not termination, so the target still bootstraps). The network is a 2–32–32–4 ReLU MLP trained with Adam at learning rate 0.002, one 32-sample update per environment step, $C=200$, and ε falls linearly from 1 to 0.1 over the first 3000 steps. Every 1000 steps the greedy policy is evaluated once from each of 30 fixed starts to the left of the wall.

FIG 6在浏览器里训练 DQNTraining a DQN in the browser

评估曲线（横轴：环境步数，千）evaluation curves (horizontal: environment steps, thousands)

左：房间俯视图，实心矩形是墙，绿圈是目标。底色是网络给出的 $\max_a Q_\theta(s,a)$：蓝色越浓越大；这个任务的真实价值一定在 0 和 1 之间，超出这个范围（不可能的值）的格子画成红色。小箭头是贪心动作，紫色线是从 3 个评估起点出发的贪心路线，琥珀色圆点是正在训练的机器人。右：绿色是评估成功率，琥珀色是评估起点上预测的 $\max_a Q$ 的平均，紫色是这些起点上实际拿到的折扣回报的平均；纵轴超过 1.5 的部分被截掉。改变任何一个开关都会重新开始训练。 Left: the room from above; the solid rectangle is the wall and the green ring the goal. The background shows the network's $\max_a Q_\theta(s,a)$: more saturated blue is larger; in this task the true value always lies between 0 and 1, and cells outside that range (impossible values) are drawn in red. Small arrows are greedy actions, purple lines are greedy routes from 3 of the evaluation starts, and the amber dot is the robot being trained. Right: green is the evaluation success rate, amber the mean predicted $\max_a Q$ at the evaluation starts, purple the mean discounted return actually obtained from them; values above 1.5 are clipped. Changing any switch restarts training.

保持经验回放和目标网络都打开，按"训练"：在 8000 到 11000 个环境步之间（我们试过的 4 个种子；种子 1 在 8000 步时），评估成功率超过 90%，价值图从目标沿着绕墙的路线"长"出来，预测的 $Q$ 与实际回报在 0.6 左右会合。With replay and the target network both on, press "Train": somewhere between 8,000 and 11,000 environment steps (over the 4 seeds we tried; 8,000 for seed 1) the evaluation success rate passes 90%, the value map grows outward from the goal along the route around the wall, and the predicted $Q$ and the actual return meet at about 0.6.
关掉目标网络（目标直接用正在训练的网络），重新训练：头两千步内预测的 $Q$ 就冲到 10 以上（种子 1 达到上万），价值图一片红色。这是 FIG 5 那种发散在神经网络上的样子。Switch the target network off (targets come straight from the network being trained) and train again: within the first two thousand steps the predicted $Q$ shoots above 10 (above ten thousand for seed 1) and the value map turns red. This is the divergence of FIG 5 on a neural network.

还可以试试关掉经验回放（每次只用最近的 32 个转移）：在我们试过的 4 个种子里，第 12000 步时成功率都在 30% 以下（中间可能短暂冲高再跌回去），而完整 DQN 都到了 100%。即使是完整的 DQN，训练初期评估起点上预测的 $Q$ 也有 0.8 到 1.4（随种子不同），远高于当时实际拿到的回报 0，也高于训练好后能达到的约 0.6；超过 1 的值在这个任务里根本不可能出现。这就是 FIG 4 的最大化偏差加上自举。打开 Double DQN（用在线网络选动作、用目标网络估值），4 个种子里早期预测 $Q$ 的峰值都更低，其中 3 个种子的成功率更早超过 90%（第 4 个同时），最后两者都到 100%。

Also try switching replay off (each update uses only the 32 most recent transitions): for the 4 seeds we tried, the success rate at 12,000 steps was below 30% (it can spike briefly and collapse again), while the full DQN reached 100% on all of them. Even the full DQN predicts $Q$ of 0.8 to 1.4 at the evaluation starts early in training (depending on the seed), far above the return actually obtained at the time, 0, and above the roughly 0.6 achievable once trained; values above 1 are outright impossible in this task. This is the maximization bias of FIG 4 compounded by bootstrapping. With Double DQN (the online network selects the action, the target network evaluates it) the early peak of the predicted $Q$ was lower for all 4 seeds, and the success rate passed 90% sooner for 3 of them (at the same time for the fourth); both end at 100%.

另一种看法Another view

带目标网络的 DQN 可以看成一连串监督回归：冻结 $\theta^-$，目标 $y=r+\gamma\max_{a'}Q_{\theta^-}(s',a')$ 就是固定标签，用 SGD 拟合几百步；然后更新标签再拟合。这就是"拟合值迭代"（fitted Q iteration，Riedmiller 2005 的 Neural Fitted Q）。每一轮是 Bellman 算子的一次近似应用：算子本身是压缩的（6.12 节），但"应用算子 + 投影到网络能表示的函数"的组合不一定是，这正是函数逼近会出问题的地方。

DQN with a target network can be read as a sequence of supervised regressions: freeze $\theta^-$, and the target $y=r+\gamma\max_{a'}Q_{\theta^-}(s',a')$ is a fixed label fitted by SGD for a few hundred steps; then refresh the labels and fit again. This is "fitted Q iteration" (Riedmiller's Neural Fitted Q, 2005). Each round is an approximate application of the Bellman operator: the operator itself is a contraction (Lesson 6.12), but "apply the operator, then project onto the functions the network can represent" need not be, and that is exactly where function approximation can go wrong.

6再看数学The math

提示：把鼠标悬停在公式中带底色的符号上，FIG 1–6 中对应的元素会被高亮（例如 $G_t$ 加粗 FIG 1 的紫色 MC 柱与曲线，$\max$ 加粗 FIG 3 的蓝色路线和 FIG 4 的蓝色曲线）。Tip: hover the highlighted symbols in the formulas and the matching elements in FIG 1–6 light up (for example $G_t$ thickens FIG 1's purple MC bars and curve, and the $\max$ thickens FIG 3's blue route and FIG 4's blue curve).

记号与出发点Notation and starting point

沿用 20.1 节：在时刻 $t$ 处于 $s_t$，做 $a_t$，得到奖励 $r_{t+1}$，到达 $s_{t+1}$。回报 $G_t=\sum_{k\ge0}\gamma^k r_{t+k+1}$。6.12 节最小化代价 $c$，这里最大化奖励，二者只差一个符号 $r=-c$，$\min$ 变成 $\max$。最优动作价值满足 Bellman 最优方程：

As in Lesson 20.1: at time $t$ we are in $s_t$, take $a_t$, receive reward $r_{t+1}$ and reach $s_{t+1}$. The return is $G_t=\sum_{k\ge0}\gamma^k r_{t+k+1}$. Lesson 6.12 minimized a cost $c$; here we maximize reward, which differs only by the sign $r=-c$, with $\min$ turning into $\max$. The optimal action value satisfies the Bellman optimality equation:

$$ Q^\star(s,a)=\mathbb E_{s'\sim P(\cdot\mid s,a)}\Big[\,r(s,a,s')+\gamma\max_{a'}Q^\star(s',a')\,\Big],\qquad \pi^\star(s)=\arg\max_a Q^\star(s,a) $$

值迭代用模型精确计算右边的期望。没有模型时，我们只能拿到期望里的样本。

Value iteration computes the expectation on the right exactly from the model. Without a model, all we get are samples of what is inside it.

用样本求期望：随机逼近Expectations from samples: stochastic approximation

要估计随机变量 $X$ 的均值，样本均值可以写成增量形式 $\bar x_n=\bar x_{n-1}+\tfrac1n(x_n-\bar x_{n-1})$。把 $1/n$ 换成一般步长 $\alpha_t$，就是本课所有更新共同的形状"估计 ← 估计 + α(目标 − 估计)"。Robbins–Monro 条件保证它收敛到均值：

To estimate the mean of a random variable $X$, the sample mean can be written incrementally as $\bar x_n=\bar x_{n-1}+\tfrac1n(x_n-\bar x_{n-1})$. Replacing $1/n$ by a general step $\alpha_t$ gives the shape shared by every update in this lesson, "estimate ← estimate + α(target − estimate)". The Robbins–Monro conditions guarantee convergence to the mean:

$$ \sum_t\alpha_t=\infty,\qquad \sum_t\alpha_t^2<\infty $$

第一条保证步长总和足够大，从任何初值都能走到真值；第二条保证步长衰减得足够快，噪声最终被平均掉。$\alpha_t=1/t$ 两条都满足。

The first ensures the steps add up to enough to reach the true value from any start; the second that they shrink fast enough for the noise to be averaged away eventually. $\alpha_t=1/t$ satisfies both.

常数步长不满足第二条：估计不会精确收敛，而是在真值附近持续抖动，抖动幅度随 $\alpha$ 增大（FIG 1 里 $\alpha_{\rm TD}=0.3$ 的误差平台）。好处是它对较新的样本权重更大，适合环境或策略在变化的情形。

A constant step violates the second condition: the estimate does not converge exactly but keeps jittering around the true value, more so for larger $\alpha$ (the error plateau at $\alpha_{\rm TD}=0.3$ in FIG 1). In exchange it weights recent samples more, which suits environments or policies that change.

蒙特卡洛与 TD(0)Monte Carlo and TD(0)

左边是蒙特卡洛，右边是 TD(0)，$\delta_t$ 叫 TD 误差：

Monte Carlo on the left and TD(0) on the right, where $\delta_t$ is the TD error:

$$ V(s_t)\leftarrow V(s_t)+\alpha\big[\hl{mcret}{G_t}-V(s_t)\big]\qquad\qquad V(s_t)\leftarrow V(s_t)+\alpha\,\delta_t,\quad \delta_t=\hl{tdtarget}{r_{t+1}+\gamma V(s_{t+1})}-V(s_t) $$

$G_t$ 是 $V^\pi(s_t)$ 的无偏样本，但它累积了整条轨迹上所有动作和转移的随机性，方差大；TD 目标只含一步的随机性，方差小，但在 $V$ 不准时是有偏的。两者的关系是一个望远镜求和：若 $V$ 在回合内保持不变，

$G_t$ is an unbiased sample of $V^\pi(s_t)$, but it accumulates the randomness of every action and transition along the trajectory, so its variance is large; the TD target contains one step of randomness, so its variance is small, but it is biased while $V$ is wrong. The two are related by a telescoping sum: if $V$ is held fixed during the episode,

$$ G_t-V(s_t)=\sum_{k\ge0}\gamma^k\,\delta_{t+k} $$

MC 误差就是之后所有 TD 误差的折扣和。介于两者之间的 $n$ 步回报和 TD($\lambda$) 在这条谱上连续地取舍偏差与方差；20.4 节的 GAE 用的正是这个思路。

The MC error is the discounted sum of all subsequent TD errors. The $n$-step returns and TD($\lambda$) in between trade bias against variance continuously along this spectrum; the GAE of Lesson 20.4 uses exactly this idea.

SARSA、Q-learning 与收敛SARSA, Q-learning and convergence

SARSA 的目标 $r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$ 是 $Q^\pi$ 的 Bellman 期望方程的样本（$\pi$ 是正在执行的策略）；Q-learning 的目标 $r_{t+1}+\gamma\max_{a'}Q(s_{t+1},a')$ 是 Bellman 最优方程的样本，与 $a_{t+1}$ 怎么选无关，所以是 off-policy。表格 Q-learning 在每个 $(s,a)$ 被无限次访问且步长满足 Robbins–Monro 条件时以概率 1 收敛到 $Q^\star$（Watkins & Dayan, 1992）。ε-greedy 行为策略：

SARSA's target $r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$ is a sample of the Bellman expectation equation for $Q^\pi$ ($\pi$ being the policy being executed); Q-learning's target $r_{t+1}+\gamma\max_{a'}Q(s_{t+1},a')$ is a sample of the Bellman optimality equation, regardless of how $a_{t+1}$ is chosen, hence off-policy. Tabular Q-learning converges to $Q^\star$ with probability 1 when every $(s,a)$ is visited infinitely often and the steps satisfy the Robbins–Monro conditions (Watkins & Dayan, 1992). The ε-greedy behaviour policy is

$$ \pi_\varepsilon(a\mid s)=\begin{cases}1-\varepsilon+\varepsilon/|\mathcal A|, & a=\arg\max_{a'}Q(s,a')\\ \varepsilon/|\mathcal A|, & a\ne\arg\max_{a'}Q(s,a')\end{cases} $$

让 $\varepsilon$ 随时间慢慢趋于 0，同时保证每个动作仍被无限次尝试（GLIE），SARSA 也收敛到 $Q^\star$。FIG 3 里 $\varepsilon$ 固定为 0.1，所以 SARSA 收敛到的是 ε-greedy 策略中最好的那个，而不是 $Q^\star$。

Letting $\varepsilon$ decay slowly to 0 while every action is still tried infinitely often (GLIE) makes SARSA converge to $Q^\star$ as well. In FIG 3 $\varepsilon$ is fixed at 0.1, so SARSA converges to the best ε-greedy policy, not to $Q^\star$.

最大化偏差与双估计器Maximization bias and the double estimator

$\max$ 是凸函数，由 Jensen 不等式 $\mathbb E[\max_a\hat Q_a]\ge\max_a\mathbb E[\hat Q_a]$。例如 10 个真实值都为 0、估计误差独立服从 $\mathcal N(0,1)$ 的动作，估计的最大值期望约为 1.54。Double Q-learning 用两张表 $Q^A,Q^B$，每次随机更新其中一张：

$\max$ is convex, so by Jensen's inequality $\mathbb E[\max_a\hat Q_a]\ge\max_a\mathbb E[\hat Q_a]$. For example, for 10 actions with true value 0 and independent $\mathcal N(0,1)$ estimation errors, the expected maximum of the estimates is about 1.54. Double Q-learning keeps two tables $Q^A,Q^B$ and updates one of them at random each time:

$$ Q^A(s,a)\leftarrow Q^A(s,a)+\alpha\Big[r+\gamma\,\hl{dq}{Q^B\big(s',\arg\max_{a'}Q^A(s',a')\big)}-Q^A(s,a)\Big] $$

选择用 $Q^A$，估值用独立的 $Q^B$：给定所选动作，$Q^B$ 对它的估计是无偏的（整体上可能略微低估）。Double DQN（van Hasselt 等, 2016）直接复用 DQN 现成的两套参数：目标改为 $r+\gamma\,Q_{\theta^-}\big(s',\arg\max_{a'}Q_\theta(s',a')\big)$。

Selection uses $Q^A$ and evaluation the independent $Q^B$: given the selected action, $Q^B$'s estimate of it is unbiased (overall it may slightly underestimate). Double DQN (van Hasselt et al., 2016) reuses DQN's two existing parameter sets: the target becomes $r+\gamma\,Q_{\theta^-}\big(s',\arg\max_{a'}Q_\theta(s',a')\big)$.

函数逼近：半梯度 TDFunction approximation: semi-gradient TD

有参数时，Q-learning 的更新是

With parameters, the Q-learning update is

$$ \theta\leftarrow\theta+\alpha\,\delta_t\,\nabla_\theta Q_\theta(s_t,a_t),\qquad \delta_t=r_{t+1}+\gamma\max_{a'}Q_\theta(s_{t+1},a')-Q_\theta(s_t,a_t) $$

它看起来像在对 $\tfrac12\delta_t^2$ 做梯度下降，其实不是：真正的梯度还应包含目标对 $\theta$ 的导数，这里把目标当常数（"半梯度"）。所以它不是任何固定目标函数的下降法，SGD 的收敛保证（6.4 节）不适用。on-policy 的线性 TD 是收敛的（Tsitsiklis & Van Roy, 1997），因为在 on-policy 分布下更新的期望方向是"稳定"的；off-policy 时这个性质丢失，FIG 5 就是反例（Baird 1995 给出了更著名的七状态反例）。目标网络把 $\max_{a'}Q_{\theta^-}$ 在 $C$ 步内冻结，使每一段都是一个真正的回归问题。

It looks like gradient descent on $\tfrac12\delta_t^2$ but is not: the true gradient would also contain the target's derivative with respect to $\theta$, which is treated here as a constant ("semi-gradient"). It is therefore not descent on any fixed objective, and the convergence guarantees of SGD (Lesson 6.4) do not apply. On-policy linear TD does converge (Tsitsiklis & Van Roy, 1997), because under the on-policy distribution the expected update direction is "stable"; off-policy that property is lost, and FIG 5 is a counterexample (Baird, 1995, gave the better-known seven-state one). The target network freezes $\max_{a'}Q_{\theta^-}$ for $C$ steps, so that each stretch is a genuine regression problem.

一句话总结In one sentence

所有 value-based 方法都是"用样本代替期望的 Bellman 备份"；它们的区别在于用什么当目标（$G_t$、$Q(s',a')$、$\max$、双估计器），以及用表格还是函数来存储估计。

Every value-based method is "a Bellman backup with a sample in place of the expectation"; they differ in what they use as the target ($G_t$, $Q(s',a')$, a $\max$, a double estimator) and in whether the estimates are stored in a table or a function.

7机器人中的它In robotics

DQN 的突破。Mnih 等（Nature 2015）用同一个卷积网络、同一套超参数，直接从屏幕像素学会了 49 个 Atari 2600 游戏，其中许多达到人类水平。它展示了 Q-learning 加上回放和目标网络能从高维感知输入学控制。之后的改进（Double DQN、优先经验回放、Dueling 结构、多步回报、分布式价值等）被 Rainbow（Hessel 等, 2018）合在一起。

离散动作的机器人任务。当动作能自然地离散化时，Q 函数很好用。Zeng 等（IROS 2018）让机器人在杂乱桌面上学"推"和"抓"的配合：两个全卷积网络（推、抓各一个）为俯视图的每个像素和每个末端朝向输出一个 $Q$ 值，机器人执行 $Q$ 最大的那个像素上的动作。"在哪个像素抓"是一个巨大但有图像结构的离散动作空间，网络一次前向就能对它取 $\max$。

连续动作的难处。DQN 的 $\max_{a'}$ 要对所有动作枚举。机械臂的动作是连续的关节速度或末端位移：一个 7 关节手臂每个关节只取 5 档，就有 $5^7=78125$ 个动作，再细一点就无法枚举。几种出路：

在动作上做优化：QT-Opt（Kalashnikov 等, CoRL 2018）用相机图像和候选动作作为 Q 网络输入，用交叉熵方法（6.11 节的 CEM）在连续动作上近似求 $\max_a Q(s,a)$。它主要用在多台真实机器人上收集的大量抓取尝试做 off-policy 训练，报告在没见过的物体上达到 96% 的抓取成功率。
让 $\max$ 有闭式解：NAF（Gu 等, 2016）把优势函数限制为动作的二次型，最大值点直接由网络输出。
学一个策略网络去做 $\max$：DDPG、TD3 和 SAC 训练一个 actor $\mu_\phi(s)\approx\arg\max_aQ(s,a)$，critic 用的正是本课的 TD 目标，这是 20.4 节的内容；或者完全绕开 $Q$，直接对策略求梯度，这是 20.3 节。

为什么 off-policy 对机器人重要。真实机器人每次尝试都花时间、磨损硬件。Value-based 的 off-policy 学习让所有历史数据都能复用，也是从固定数据集学习（20.5 节离线 RL）的起点；不过在完全离线时，$\max$ 会去查询数据里从没出现过的动作，最大化偏差会变成严重的"外推误差"，那是 20.5 节要解决的问题。TD 学习本身也贯穿后面的课：actor-critic 的 critic、24.3 节 TD-MPC 里的价值函数，都用本课的 TD 目标训练。

The DQN breakthrough. Mnih et al. (Nature 2015) used one convolutional network and one set of hyperparameters to learn 49 Atari 2600 games directly from screen pixels, reaching human level on many of them. It showed that Q-learning plus replay and a target network can learn control from high-dimensional perception. Later improvements (double DQN, prioritized replay, the dueling architecture, multi-step returns, distributional values and more) were combined in Rainbow (Hessel et al., 2018).

Robot tasks with discrete actions. When actions discretize naturally, a Q-function works well. Zeng et al. (IROS 2018) had a robot learn the synergy of "push" and "grasp" on a cluttered table: two fully convolutional networks (one for pushing, one for grasping) output one $Q$ value for every pixel of a top-down image and every end-effector orientation, and the robot executes the action at the pixel with the largest $Q$. "Which pixel to grasp at" is a huge but image-structured discrete action space, and a single forward pass takes the $\max$ over it.

The trouble with continuous actions. DQN's $\max_{a'}$ enumerates all actions. An arm's actions are continuous joint velocities or end-effector displacements: a 7-joint arm with only 5 levels per joint already has $5^7=78125$ actions, and any finer and enumeration is hopeless. The ways out:

Optimize over the action: QT-Opt (Kalashnikov et al., CoRL 2018) feeds the camera image and a candidate action into the Q-network and approximates $\max_aQ(s,a)$ over continuous actions with the cross-entropy method (CEM, Lesson 6.11). It was trained off-policy, mostly on a large set of grasp attempts collected on several real robots, and reported 96% grasp success on previously unseen objects.
Give the $\max$ a closed form: NAF (Gu et al., 2016) restricts the advantage to a quadratic in the action, so the maximizer is read straight off the network output.
Learn a policy network to do the $\max$: DDPG, TD3 and SAC train an actor $\mu_\phi(s)\approx\arg\max_aQ(s,a)$ whose critic uses exactly this lesson's TD target, the subject of Lesson 20.4; or skip $Q$ altogether and take gradients of the policy directly, as in Lesson 20.3.

Why off-policy matters for robots. Every real-robot trial costs time and wears hardware. Value-based off-policy learning reuses all past data, and it is the starting point for learning from a fixed dataset (Lesson 20.5, offline RL); fully offline, however, the $\max$ queries actions that never occur in the data, and maximization bias turns into severe "extrapolation error", which is the problem Lesson 20.5 tackles. TD learning itself runs through later lessons: the critic of actor-critic methods and the value function in TD-MPC (Lesson 24.3) are trained with this lesson's TD target.

工程经验Practical notes

用 DQN 类方法时最常检查的几件事：奖励尺度（DQN 在 Atari 上把奖励截断到 $[-1,1]$）；终止与超时截断分开处理；目标网络同步周期或软更新系数 $\tau$（$\theta^-\leftarrow\tau\theta+(1-\tau)\theta^-$）；回放缓冲区够不够大，旧数据会不会太旧；以及定期用贪心策略做独立评估，同时比较预测的 $Q$ 和实际的回报，二者长期对不上说明在高估或发散。

The things most often checked with DQN-style methods: the reward scale (DQN clipped Atari rewards to $[-1,1]$); handling termination and time-limit truncation separately; the target-network sync period or soft-update rate $\tau$ ($\theta^-\leftarrow\tau\theta+(1-\tau)\theta^-$); whether the replay buffer is large enough and its data not too stale; and regular separate evaluation of the greedy policy, comparing predicted $Q$ with the returns actually obtained: a persistent mismatch means overestimation or divergence.

8常见误区Common pitfalls

误区 1：把超时截断当成终止Pitfall 1: treating a time-limit truncation as termination

回合因为到了步数上限而结束时，$s'$ 并不是终止状态，机器人本可以继续走下去，目标仍应是 $r+\gamma\max_{a'}Q(s',a')$。若把它当成终止（$d=1$），就等于告诉网络"在这个位置未来价值为 0"，而这只取决于计时器，不取决于状态，学出来的价值会出现无法解释的凹陷。FIG 6 里只在真正到达目标时置 $d=1$。

When an episode ends because it hit the step limit, $s'$ is not a terminal state: the robot could have kept going, and the target should still be $r+\gamma\max_{a'}Q(s',a')$. Treating it as terminal ($d=1$) tells the network "the future is worth 0 here", which depends on a timer rather than on the state, and the learned values grow unexplained dents. FIG 6 sets $d=1$ only when the goal is actually reached.

误区 2：以为 ε-greedy 就够探索了Pitfall 2: assuming ε-greedy explores enough

ε-greedy 每一步独立地随机，难以完成需要"连续很多步都偏离当前最好"的探索（FIG 2 的小充电点陷阱）。稀疏奖励的机器人任务里尤其明显。乐观初值、基于访问计数或不确定性的探索奖励、示范数据引导，往往比调大 $\varepsilon$ 有效得多。

ε-greedy randomizes each step independently and rarely achieves exploration that needs "many consecutive steps away from the current best" (the small-pad trap of FIG 2). It shows most in sparse-reward robot tasks. Optimistic initialization, exploration bonuses based on visit counts or uncertainty, and guidance from demonstrations usually help far more than a larger $\varepsilon$.

误区 3：用训练中的回报评价 off-policy 学到的策略Pitfall 3: judging an off-policy learner by its training return

FIG 3 里 Q-learning 的训练回报比 SARSA 差得多，可它学到的贪心策略更好（$-13$ 对 $-17$）。训练回报混入了探索的代价，衡量的是行为策略，不是目标策略。评价学到的策略，要关掉探索单独跑评估回合。

In FIG 3 Q-learning's training return is far worse than SARSA's, yet its greedy policy is better ($-13$ against $-17$). The training return includes the cost of exploration and measures the behaviour policy, not the target policy. To judge what was learned, turn exploration off and run separate evaluation episodes.

误区 4：把 $Q$ 值当成可信的回报预测Pitfall 4: taking $Q$ values as trustworthy return predictions

$\max$ 带来的系统性高估（FIG 4）和函数逼近误差叠加在一起，DQN 的 $Q$ 值常常明显高于真实回报（FIG 6 训练初期预测值在 0.8 以上，而实际回报是 0）。若用 $Q$ 做决策之外的事，例如判断"抓取成功概率"或在多个策略间比较，要先用蒙特卡洛回报校准，或用 Double/Clipped 估计器。

The systematic overestimation from the $\max$ (FIG 4) compounds with approximation error, and DQN's $Q$ values often sit well above the true returns (early in FIG 6 the predictions are above 0.8 while the actual return is 0). If you use $Q$ for anything beyond choosing actions, such as estimating "grasp success probability" or comparing policies, first calibrate against Monte Carlo returns or use double or clipped estimators.

误区 5：觉得回放和目标网络只是锦上添花Pitfall 5: thinking replay and the target network are optional extras

去掉目标网络，FIG 6 的预测值在两千步内就冲到几百甚至上万；去掉回放，成功率在 12000 步时仍不到 30%。它们不是调参技巧，而是让"off-policy + 自举 + 函数逼近"能工作的结构性部件。学习率太大、目标同步太频繁，效果和去掉目标网络类似。

Without the target network, FIG 6's predictions shoot to hundreds or even above ten thousand within two thousand steps; without replay, the success rate is still below 30% at 12,000 steps. They are not tuning tricks but structural parts that let "off-policy + bootstrapping + function approximation" work at all. Too large a learning rate or too frequent a target sync behaves much like removing the target network.

9小练习Check yourself

1. TD(0) 更新：当前 $V(s)=0.4$，观察到 $r=0$，$V(s')=0.8$，$\gamma=0.9$，$\alpha=0.5$。更新后的 $V(s)$ 是？1. A TD(0) update: currently $V(s)=0.4$; we observe $r=0$ and $V(s')=0.8$, with $\gamma=0.9$ and $\alpha=0.5$. What is $V(s)$ after the update?

选项 A。目标 $0+0.9\times0.8=0.72$，TD 误差 $0.72-0.4=0.32$，$V(s)\leftarrow0.4+0.5\times0.32=0.56$。0.72 是目标本身（相当于 $\alpha=1$），0.60 是忘了乘 $\gamma$。Option A. The target is $0+0.9\times0.8=0.72$, the TD error $0.72-0.4=0.32$, so $V(s)\leftarrow0.4+0.5\times0.32=0.56$. 0.72 is the target itself (as if $\alpha=1$), and 0.60 forgets the $\gamma$.

2. 在 $\varepsilon=0.1$ 的悬崖行走里，为什么 SARSA 学到的路线比 Q-learning 离悬崖远？2. In cliff walking with $\varepsilon=0.1$, why does SARSA learn a route farther from the cliff than Q-learning?

选项 C。SARSA 是 on-policy 的，估计的是会探索的策略本身的价值，贴边格子对这个策略确实危险。Q-learning 估计的是贪心策略的价值，与探索无关，所以学到最短路线；它收敛得很好，只是训练中因为探索掉崖更多。Option C. SARSA is on-policy: it estimates the value of the exploring policy itself, for which edge cells really are dangerous. Q-learning estimates the greedy policy's value regardless of exploration and so learns the shortest route; it converges fine, it just falls more during training because of exploration.

3. 某状态有 10 个动作，真实价值都是 0，当前估计各自带有独立噪声。下列说法哪个正确？3. A state has 10 actions whose true values are all 0, and the current estimates carry independent noise. Which statement is correct?

选项 B。Jensen 不等式给出 $\mathbb E[\max_a\hat Q_a]\ge\max_a\mathbb E[\hat Q_a]=0$，动作越多、噪声越大偏得越多（FIG 4 里 $n$ 越大蓝色曲线越高）。Double Q-learning 把选择与估值分开，所选动作的估值不再系统性偏高。Option B. Jensen's inequality gives $\mathbb E[\max_a\hat Q_a]\ge\max_a\mathbb E[\hat Q_a]=0$, and more actions or more noise make it worse (larger $n$ lifts the blue curve in FIG 4). Double Q-learning decouples selection from evaluation, so the selected action's value is no longer systematically too high.

4. 下列哪一项不属于 Sutton & Barto 所说的"致命三元组"？4. Which of the following is not part of Sutton & Barto's "deadly triad"?

选项 D。三元组是函数逼近、自举和 off-policy 数据，三者同时出现时 TD 可能发散（FIG 5 去掉任何一项发散都消失）。ε-greedy 只是产生行为数据的一种方式；它让数据变成 off-policy 的，但它本身不是三元组的一项。Option D. The triad is function approximation, bootstrapping and off-policy data; with all three present TD can diverge (in FIG 5 removing any one stops the divergence). ε-greedy is just one way of generating behaviour data; it makes the data off-policy, but it is not itself a leg of the triad.

5. 一个 7 关节机械臂，每个关节的速度指令离散成 5 档。若用 DQN，网络输出层需要多少个 $Q$ 值？5. A 7-joint arm has each joint's velocity command discretized into 5 levels. With DQN, how many $Q$ values must the output layer produce?

选项 B。联合动作是每个关节档位的组合，$5^7=78125$。35 是把各关节当成独立选择（DQN 的 $\max$ 并不是这样定义的），16807 是 $7^5$。动作数随关节数指数增长，这正是连续动作要转向 CEM、actor-critic 或策略梯度（20.3、20.4 节）的原因。Option B. A joint action is a combination of one level per joint, $5^7=78125$. 35 treats the joints as independent choices (not how DQN's $\max$ is defined), and 16807 is $7^5$. The count grows exponentially with the number of joints, which is why continuous actions turn to CEM, actor-critic or policy gradients (Lessons 20.3 and 20.4).

10延伸阅读Further reading

R. S. Sutton & A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Ch. 6 and 11 — TD、SARSA、Q-learning（随机游走、悬崖行走、最大化偏差的例子都出自第 6 章），以及函数逼近与致命三元组（第 11 章）TD, SARSA and Q-learning (the random walk, cliff walking and maximization bias examples are from Ch. 6), and function approximation and the deadly triad (Ch. 11)
R. S. Sutton, Learning to predict by the methods of temporal differences, Machine Learning, 1988 — TD 学习的奠基论文the founding paper of TD learning
C. J. C. H. Watkins & P. Dayan, Q-learning, Machine Learning, 1992 — Q-learning 的收敛性证明（算法本身来自 Watkins 1989 年的博士论文）the convergence proof of Q-learning (the algorithm itself is from Watkins's 1989 PhD thesis)
G. A. Rummery & M. Niranjan, On-line Q-learning using connectionist systems, Cambridge University technical report, 1994 — 后来被称为 SARSA 的算法the algorithm later named SARSA
H. van Hasselt, Double Q-learning, NeurIPS (NIPS) 2010; H. van Hasselt, A. Guez & D. Silver, Deep reinforcement learning with double Q-learning, AAAI 2016 — 最大化偏差与双估计器maximization bias and the double estimator
V. Mnih et al., Human-level control through deep reinforcement learning, Nature, 2015 — DQN：经验回放、目标网络，从像素玩 AtariDQN: experience replay, a target network, Atari from pixels
J. N. Tsitsiklis & B. Van Roy, An analysis of temporal-difference learning with function approximation, IEEE Transactions on Automatic Control, 1997 — 线性 TD 在 on-policy 下收敛，以及 off-policy 时为何会失败linear TD converges on-policy, and why it can fail off-policy
D. Kalashnikov et al., QT-Opt: Scalable deep reinforcement learning for vision-based robotic manipulation, CoRL 2018 — 用 CEM 处理连续动作的 Q-learning，在真实机器人上学抓取Q-learning with CEM over continuous actions, learning to grasp on real robots
M. Hessel et al., Rainbow: Combining improvements in deep reinforcement learning, AAAI 2018 — DQN 各种改进的组合与消融the combination and ablation of DQN's improvements