Chapter 7 - Temporal-Difference Methods#

1.1 问题设定#

给定固定策略 $\pi$，智能体按该策略产生经验序列：

目标是用样本估计所有状态的真实价值 $v_\pi(s)$，但不知道环境的转移概率和奖励模型。

1.2 TD(0) 更新#

在时刻 $t$ 观察到转移 $(s_t,r_{t+1},s_{t+1})$ 后，只更新刚访问的状态：

对所有未访问状态：

式 (7.2) 在算法描述中经常省略，但它在数学上不可缺少：一次迭代只改变价值向量的一个分量。

把更新写成更熟悉的插值形式：

因此，当 $0<\alpha_t(s_t)<1$ 时，新估计位于旧估计和本次 TD 目标之间。

1.3 从回报定义到 Bellman 方程#

状态价值定义为：

由于

可得：

在 Markov 性与固定策略下，

于是得到 Bellman 期望方程：

1.4 Box 7.1 - 用 Robbins-Monro 推导 TD#

把 Bellman 方程移到一边，定义求根函数：

真实根满足 $g(v_\pi(s_t))=0$。但期望未知，只能用单个转移构造带噪观测：

Robbins-Monro 更新为：

这里仍含未知真值 $v_\pi(s_{t+1})$。把它替换为当前估计 $v_t(s_{t+1})$，就得到式 (7.1)。

[!important] 自举发生在哪里 TD 目标用一个估计 $v_t(s_{t+1})$ 去更新另一个估计 $v_t(s_t)$，这就是 bootstrapping。随机逼近推导先给出理想的无偏观测，再用当前估计代替未知真值；Theorem 7.1 说明这种耦合替换仍可收敛。

1.5 TD 目标与 TD 误差#

定义一步 TD 目标：

教材采用的 TD 误差符号是：

因此更新写成：

[!warning] 符号约定 很多强化学习资料把 TD 误差定义为“目标减当前值”，此时更新使用加号。本教材定义为“当前值减目标”，所以更新使用减号。两种写法数值完全等价，但推导时不能混用。

若 $0<\alpha_t(s_t)<1$，则：

从而：

这说明每次更新都把当前估计拉近本次目标，但不表示它在每一步都更接近真值，因为 TD 目标本身是随机且随估计变化的。

当 $v_t=v_\pi$ 时：

因此 TD 误差也可理解为 innovation，即新样本相对于当前预测带来的新信息。

1.6 TD 与 Monte Carlo 的比较#

Table 7.1：TD learning 与 MC learning

若一条长度为 $L$ 的回合中每个状态有 $\lvert\mathcal A\rvert$ 个可选动作，软策略可能产生数量级为 $\lvert\mathcal A\rvert^L$ 的动作序列。MC 目标吸收整条序列的随机性，而单步 TD 只使用局部转移，因此常有更低方差。

[!note] 补充理解 TD 与 MC 的核心权衡是偏差和方差。TD 用当前估计截断未来回报，通常降低方差但引入自举偏差；MC 使用完整真实回报，没有自举偏差，却对整条轨迹的随机性更敏感。

1.7 Theorem 7.1 - TD 的收敛性#

给定固定策略 $\pi$，若对每个状态 $s$ 都有：

其中访问 $s$ 时 $\alpha_t(s)>0$，未访问时 $\alpha_t(s)=0$，则：

第一项要求每个状态获得无限或足够多的有效更新，因此必须保证充分探索，例如使用 exploring starts 或探索性策略。第二项要求步长平方和有限，使噪声的累计方差受控。

常数步长不满足第二个条件，所以一般不能保证几乎必然收敛到一个固定点；不过在平稳问题中，它可以在真值附近波动，并具有跟踪非平稳目标的能力。

1.8 Box 7.2 - 收敛证明的结构#

定义误差：

对已访问状态，式 (7.1) 可写为：

对未访问状态：

令

用于已访问状态，并对未访问状态令 $\eta_t(s)=0$。两种情况可统一为：

证明随后核对 Chapter 6 的多变量随机逼近定理。

若 $s\ne s_t$，则：

若 $s=s_t$，利用 Bellman 方程：

因为 $0\le\gamma<1$，条件期望映射具有压缩性；奖励有界又保证条件方差有界。再结合 Robbins-Monro 步长条件，便得到 $\Delta_t\to0$。

2.1 固定策略下的 Sarsa#

给定策略 $\pi$，经验序列写为：

Sarsa 更新为：

而对所有 $(s,a)\ne(s_t,a_t)$：

名称 Sarsa 来自一次更新所需的五元组：

其 TD 目标和教材符号下的 TD 误差分别为：

2.2 动作价值 Bellman 方程#

Sarsa 是对以下方程的随机逼近：

2.3 Box 7.3 - 为什么式 (7.13) 是 Bellman 方程#

按模型展开：

其中：

这正是：

2.4 Theorem 7.2 - Sarsa 的收敛性#

给定固定策略 $\pi$，若对所有状态动作对 $(s,a)$：

则：

这里 $\alpha_t(s,a)$ 仅在 $(s,a)=(s_t,a_t)$ 时为正。因此第一项也意味着每个状态动作对必须被无限或足够多次访问。

2.5 用 Sarsa 学习最优策略#

固定策略 Sarsa 只做策略评估。要学习最优策略，需要在每次动作价值更新后立刻改进策略，这就是广义策略迭代：

对状态 $s_t$ 采用 $\epsilon$-greedy 改进。设：

教材给出的概率写法为：

这等价于：以 $1-\epsilon$ 选择贪婪动作，另以 $\epsilon$ 在所有动作上均匀探索。

2.6 Algorithm 7.1 - Sarsa 控制#

初始化

• 对所有 $(s,a)$ 初始化 $q_0(s,a)$；
• 选择学习率 $\alpha_t(s,a)>0$；
• 从 $q_0$ 导出初始 $\epsilon$-greedy 策略 $\pi_0$。

每个回合

1. 从初始状态 $s_0$ 开始，按 $\pi_0(\cdot\mid s_0)$ 选择 $a_0$。
2. 当 $s_t$ 不是目标状态时：
   • 执行 $a_t$，观察 $r_{t+1},s_{t+1}$；
   • 按当前策略 $\pi_t(\cdot\mid s_{t+1})$ 选择 $a_{t+1}$；
   • 用式 (7.12) 更新 $q(s_t,a_t)$；
   • 把 $s_t$ 的策略更新为关于新 $q$ 的 $\epsilon$-greedy 策略；
   • 令 $s_t\leftarrow s_{t+1}$，$a_t\leftarrow a_{t+1}$。

这里没有先把一个策略完全评估好再改进，而是把评估和改进交织执行。

2.7 Sarsa 实验#

实验设置：

• 所有回合从左上角开始，到蓝色目标格终止；
• $r_{\text{target}}=0$；
• $r_{\text{forbidden}}=r_{\text{boundary}}=-10$；
• $r_{\text{other}}=-1$；
• $\alpha=0.1$，$\epsilon=0.1$；
• $q_0(s,a)=0$，初始策略对 5 个动作均匀分布。

结果解读：

• 左图显示最终策略能把智能体从指定起点带到目标；
• 总奖励随训练整体上升；
• 回合长度随训练整体下降；
• 偶发的长度尖峰和奖励骤降来自 $\epsilon$-greedy 的随机探索；
• 未充分访问的状态不保证得到全局最优动作，因此“找到一条好路径”不等于“学到所有状态的最优策略”。

2.8 Box 7.4 - Expected Sarsa#

Expected Sarsa 不再对下一动作 $A$ 取一次样本，而是在当前策略下对它求期望：

其中：

Expected Sarsa 对应的方程是：

它与 Sarsa 的区别只在 TD 目标：

求期望略增计算量，但消除了下一动作采样造成的随机性，通常能降低估计方差。

3.1 从折扣回报的不同分解出发#

动作价值定义：

同一个回报可以按不同深度自举：

一般地：

若一直展开到回合结束：

这些上标只表示分解方式不同；在使用真实 $q_\pi$ 时，它们对同一 $G_t$ 的期望是一致的。

3.2 n 步更新#

用样本目标：

n 步 Sarsa 更新为：

实际在时刻 $t$ 尚未获得 $r_{t+n},s_{t+n},a_{t+n}$，所以必须等到 $t+n$ 才更新 $(s_t,a_t)$。更准确的在线索引写成：

3.3 两个极端#

当 $n=1$：

算法退化为单步 Sarsa。

当 $n=\infty$ 且 $\alpha_t=1$：

算法退化为 Monte Carlo 回报学习。

3.4 偏差、方差与延迟#

本节给出的 n 步 Sarsa 仍是策略评估算法。若要学习最优策略，仍须像 Algorithm 7.1 那样加入策略改进。

4.1 Q-learning 更新#

Q-learning 直接估计最优动作价值。其更新为：

其余状态动作对保持不变。

Q-learning 的 TD 目标是：

与 Sarsa 相比，Q-learning 不需要实际采样 $a_{t+1}$ 来构造目标，只需 $(s_t,a_t,r_{t+1},s_{t+1})$。

4.2 Q-learning 求解的方程#

Q-learning 是对下式的随机逼近：

这是动作价值形式的 Bellman 最优方程，其唯一解是 $q_*(s,a)$。

4.3 Box 7.5 - 从动作价值到 Bellman 最优方程#

按期望定义展开式 (7.19)：

两边对当前动作取最大，并定义：

得到：

这正是状态价值形式的 Bellman 最优方程。因此式 (7.19) 的固定点对应最优动作价值和最优策略。

4.4 同策略与异策略#

强化学习中要区分两类策略：

• 行为策略 $\pi_b$：真正与环境交互、生成经验样本的策略；
• 目标策略 $\pi_T$：算法试图评估或不断改进的策略。

若 $\pi_b=\pi_T$，称为同策略学习（on-policy learning）；若二者可以不同，称为异策略学习（off-policy learning）。

4.5 同策略/异策略与在线/离线不能混淆#

这两组概念回答不同问题：

• 在线学习：交互过程中边收集数据边更新；
• 离线学习：用预先收集的数据更新，不再与环境交互；
• 同策略算法可自然在线实现，但不能直接把其他策略产生的数据当作本策略数据；
• 异策略算法既可在线，也可离线实现。

[!note] 补充理解 “异策略”不自动等于“离线”。在线 Q-learning 可以一边用探索性行为策略交互，一边学习贪婪目标策略；离线 Q-learning 则先固定数据集，再从中学习。

4.6 Algorithm 7.2 - Q-learning 的同策略实现#

尽管 Q-learning 本质上支持异策略，它也可以让行为策略和目标策略相同，从而按同策略方式实现。

初始化

• 初始化 $q_0(s,a)$；
• 设学习率 $\alpha_t(s,a)>0$；
• 从 $q_0$ 导出初始 $\epsilon$-greedy 策略 $\pi_0$。

每个回合

1. 在 $s_t$ 按当前 $\epsilon$-greedy 策略生成 $a_t$。
2. 执行动作并得到 $r_{t+1},s_{t+1}$。
3. 用式 (7.18) 更新 $q(s_t,a_t)$。
4. 把 $s_t$ 的策略更新为关于新 $q$ 的 $\epsilon$-greedy 策略。
5. 转到 $s_{t+1}$，重复直到终止。

这里“同策略实现”只描述行为策略与维护的控制策略相同；Q-learning 的更新目标仍然是 Bellman 最优目标，而不是 Sarsa 的采样动作目标。

4.7 Algorithm 7.3 - Q-learning 的异策略实现#

初始化

• 初始化 $q_0(s,a)$；
• 指定行为策略 $\pi_b(a\mid s)$；
• 设学习率 $\alpha_t(s,a)>0$；
• 目标策略将由 $q_t$ 的贪婪动作给出。

对行为策略产生的经验进行更新

1. 使用 $\pi_b$ 生成回合 $$\{s_0,a_0,r_1,s_1,a_1,r_2,\ldots\}.$$
2. 对回合内每个转移 $(s_t,a_t,r_{t+1},s_{t+1})$：
   • 用式 (7.18) 更新 $q(s_t,a_t)$；
   • 选择一个 $$a_t^*\in\arg\max_{a'}q_{t+1}(s_t,a').$$
   • 把 $s_t$ 处的目标策略更新为： $$\pi_{T,t+1}(a\mid s_t) = \begin{cases} 1, &a=a_t^*,\\ 0, &\text{otherwise}. \end{cases}$$

目标策略不负责采样，因此不必为探索保留概率，可以直接贪婪。行为策略则应保证相关状态动作对得到充分覆盖。

4.8 Q-learning 的收敛条件#

教材指出其证明与 Theorem 7.1 类似并省略。表格型 Q-learning 的基本要求仍包括：

以及所有需要学习的 $(s,a)$ 被充分访问、奖励有界、折扣率满足 $0\le\gamma<1$ 等。在这些条件下，Bellman 最优算子的压缩性把随机更新推向 $q_*$。

4.9 Q-learning 实验一：指定起点到目标#

实验设置与 Sarsa 示例相同：

且 $\alpha=0.1,\epsilon=0.1$。结果同样显示：

• 学到的策略可从指定起点抵达目标；
• 总奖励整体提高；
• 回合长度整体缩短；
• 由于探索仍在进行，单个回合会有随机波动。

比较 Figure 7.2 和 Figure 7.3 时，不应只凭单次曲线断言哪个算法绝对更好；二者使用的 TD 目标不同，对行为策略风险的反应也不同。

4.10 Q-learning 实验二：异策略学习所有状态#

实验设置：

子图含义：

• (a) 和 (b)：由基于模型的策略迭代求得的最优策略与最优状态价值，作为 ground truth；
• (c)：行为策略在每个状态对 5 个动作均匀采样，即每个动作概率为 $0.2$；
• (d)：该行为策略产生一条长为 $100000$ 步的持续轨迹，覆盖大量状态动作对；
• (e)：Q-learning 从这条异策略数据中学到的贪婪目标策略；
• (f)：$q_0(s,a)=0$ 时，状态价值均方根误差逐步趋近 0；
• (g)：$q_0(s,a)=10$ 时，初值较接近真值，约在 $10000$ 步内收敛；
• (h)：$q_0(s,a)=100$ 时，初值很差，仍能收敛但需要更多更新。

学到的最优策略不必与基准图中的箭头完全相同，因为一个 MDP 可能存在多个具有相同最优价值的最优策略。

4.11 Q-learning 实验三：探索能力决定数据质量#

Figure 7.5 的三行分别考察不同的行为策略。左列是行为策略，中列是它产生的 $100000$ 步轨迹，右列是状态价值均方根误差。

• 均匀策略可视为 $\epsilon=1$，覆盖最充分，Figure 7.4 中误差快速归零；
• 当 $\epsilon=0.5$ 时，覆盖变弱，误差只缓慢下降；
• 当 $\epsilon=0.1$ 时，某些区域很少访问，误差几乎不下降；
• 第三行虽也标为 $\epsilon=0.1$，但初始贪婪偏好不同，产生了另一种覆盖模式，仍不足以学好全局价值。

[!important] 异策略不等于不需要探索 Q-learning 允许目标策略和行为策略不同，却仍要求数据覆盖。行为策略若不访问某些状态动作对，算法就没有信息更新它们；“可从任意策略学习”必须理解为“可从任意具有充分覆盖的数据生成策略学习”。

5.1 统一更新骨架#

动作价值 TD 算法都可以写成：

其中 $\overline q_t$ 是具体算法的 TD 目标。统一误差为：

5.2 Table 7.2 - TD 目标#

MC 也能嵌入式 (7.20)：令 $\alpha_t(s_t,a_t)=1$，则新估计直接等于完整回报目标。

5.3 Table 7.2 - 所求方程#

除 Q-learning 外，本章这些算法都在评估给定策略的 Bellman 方程；Q-learning 直接求 Bellman 最优方程。

5.4 四个算法的关系#

[!note] 补充理解 从算子角度看，Sarsa 和 Expected Sarsa 采样或计算 $T_\pi q$，Q-learning 采样 $T_*q$。从数据角度看，n 步方法改变的是目标向未来展开的深度。两条轴彼此独立：一条决定求哪个固定点，另一条决定用多长的回报近似它。

Q1. TD 中的 “TD” 是什么意思？#

每个 TD 算法都有一个 TD 误差，用于表示新样本目标与当前估计之间的差异。因为这个差异联系相邻或不同时间步的估计，所以叫 temporal difference，即时序差分。

Q2. TD learning 中的 “learning” 是什么意思？#

从数学角度看，learning 就是 estimation：从样本估计状态价值或动作价值，再根据估计值获得或改进策略。

Q3. Sarsa 只能评估给定策略，怎样学习最优策略？#

把价值估计与策略改进交织起来。每更新一个状态动作价值，就把对应状态的策略更新成关于当前 $q$ 的 $\epsilon$-greedy 策略；新策略继续生成样本，再进行下一次估计。这就是广义策略迭代。

Q4. 为什么 Sarsa 要把策略更新为 $\epsilon$-greedy？#

因为同一个策略既是被改进的目标策略，也是负责生成评估样本的行为策略。若完全贪婪，许多动作可能永远不被访问，无法保证充分探索。

Q5. 定理要求学习率衰减，为什么实践中常用小常数？#

固定策略评估是平稳问题，衰减步长适合得到严格收敛。但控制过程中策略每轮都在改变，目标是非平稳的；若步长衰减得太小，估计无法及时跟踪新策略。小常数步长能持续适应变化，代价是在最终值附近保留小幅波动。

Q6. 应学习所有状态的最优策略，还是只学习一部分？#

取决于任务。若只需从固定起点到固定目标，可以重点探索路径附近状态，数据要求较低；但没有覆盖所有状态动作对，就不能保证路径是全局最优。若目标是得到完整最优策略，则需要全局充分探索。

Q7. 为什么 Q-learning 是异策略，而本章其他 TD 算法是同策略？#

Q-learning 求解 Bellman 最优方程，其目标通过 $\max_a q(s',a)$ 隐含贪婪目标策略，不需要下一动作来自行为策略。Sarsa 等算法求解给定策略的 Bellman 方程，目标中的动作必须服从被评估策略，因此行为策略和目标策略相同。

Q8. 为什么异策略 Q-learning 的目标策略用 greedy 而不是 $\epsilon$-greedy？#

目标策略不负责生成经验，所以不承担探索任务。探索由行为策略负责，目标策略可以直接取关于当前动作价值的贪婪策略。

8.1 四个核心目标#

8.2 统一更新#

教材符号下：

8.3 收敛条件#

对每个需要学习的状态或状态动作对：

并保证充分访问、奖励有界和 $0\le\gamma<1$。

8.4 算法定位#

8.5 n 步连续谱#

9.1 状态价值 TD#

9.2 Sarsa#

9.3 Expected Sarsa#

9.4 n 步 Sarsa#

9.5 Q-learning#

9.6 Bellman 与 Bellman 最优方程#