“Sutton RL V2”

第一章：强化学习问题（The Reinforcement Learning Problem）详细讲解

1. 引言：从交互中学习

强化学习的核心思想源于我们日常生活中的一种学习方式：通过与环境的交互，根据结果调整行为，从而达成某种目标。
例如，一个婴儿通过挥动手臂、观察周围，逐渐学会抓握物体；我们学开车时，通过不断尝试和调整，最终能够平稳驾驶。这种“从交互中学习”的模式，正是强化学习研究的起点。

定义：强化学习（Reinforcement Learning, RL）是机器学习的一个分支，研究智能体（agent）如何在与环境（environment）的交互中，通过试错（trial and error）来学习最优行为策略，以最大化累积的奖励信号（reward signal）。

2. 强化学习的基本特征

与常见的监督学习和无监督学习相比，强化学习有三个关键特点：

  1. 闭环性（closed-loop）：智能体的动作会影响它后续接收到的输入（状态），形成一个动态的交互循环。
  2. 没有直接的指导信号：智能体不会被明确告知“该怎么做”，而是通过尝试不同动作，观察获得的奖励来推断哪些行为更好。
  3. 延迟奖励（delayed reward）：当前的动作不仅影响立即奖励，还可能影响未来很长一段时间内的奖励。例如，下棋时某一步看似无关紧要，但可能最终决定胜负。

这些特点共同构成了强化学习问题的独特挑战，其中**探索与利用的权衡（exploration-exploitation trade-off）**尤为关键：

  • 利用（exploitation）：选择当前已知能带来高奖励的动作。
  • 探索（exploration）：尝试未知的动作，以获取更多信息，可能发现更优的策略。
    两者必须平衡，否则要么固守次优方案，要么因过度探索而损失累积奖励。

3. 强化学习的核心要素

一个典型的强化学习系统包含以下四个基本要素：

3.1 策略（Policy）

  • 定义：策略是智能体在给定状态下选择动作的规则。它可以是简单的查找表（如每个状态对应一个动作），也可以是复杂的函数（如神经网络）。
  • 数学表示：通常用 $\pi$ 表示，$\pi(a|s)$ 表示在状态 $s$ 下选择动作 $a$ 的概率（确定性策略则概率为1）。
  • 作用：策略决定了智能体的行为，是强化学习最终要学习的目标。

3.2 奖励信号（Reward Signal）

  • 定义：在每个时间步，环境向智能体发送一个标量数值，称为奖励 $R_t$。智能体的目标是最大化长期累积奖励。
  • 作用：奖励定义了问题的目标，即什么是对智能体“好”的事件。它提供了立即反馈，是策略改进的依据。
  • 注意：奖励是来自环境的信号，智能体不能主动改变它，只能通过改变行为间接影响它。

3.3 价值函数（Value Function）

  • 定义：价值函数 $v(s)$ 或 $q(s,a)$ 表示从某个状态（或状态-动作对）出发，按照某一策略行动，所能获得的期望累积奖励（即长期“好坏”的度量）。
  • 与奖励的区别：奖励是即时的、局部的，而价值是长期的、累积的预测。智能体做决策时，更应依据价值而非立即奖励。例如，一个状态可能立即奖励很低，但它能导向高奖励的未来状态，因此该状态的价值高。
  • 重要性：几乎所有的强化学习算法都围绕如何准确估计价值函数展开，它是算法设计中最核心的部分。

3.4 环境模型（Model of the Environment）（可选）

  • 定义：模型是对环境动态特性的模拟，能够预测给定状态和动作后，下一步的状态和奖励。
  • 分类：
    • 基于模型的方法（model-based）：利用模型进行规划（planning），即在决策前模拟未来可能的情况。
    • 无模型方法（model-free）：不显式建模环境，直接通过试错学习价值函数或策略。
  • 作用：模型可以加速学习，但构建准确的模型通常很困难。

4. 强化学习问题的数学框架（初步）

虽然完整的马尔可夫决策过程（MDP）在第3章才正式引入，但本章给出了基本概念：

  • 智能体（agent）：学习并决策的实体。
  • 环境（environment）：智能体之外的一切，与智能体交互，根据智能体的动作更新状态并给出奖励。
  • 时间步（time step）：离散时间 $t=0,1,2,\dots$，每个时间步发生一次交互：智能体接收状态 $S_t$，选择动作 $A_t$，环境返回下一状态 $S_{t+1}$ 和立即奖励 $R_{t+1}$。
  • 回报（Return）$G_t$：从时间 $t$ 开始的累积奖励。常用定义有两种：
    • 总回报（episodic tasks）：$G_t = R_{t+1} + R_{t+2} + \cdots + R_T$，其中 $T$ 是终止时刻（适用于有明确结束点的任务，如游戏对局）。
    • 折扣回报（continuing tasks）：$G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$，其中 $\gamma \in [0,1]$ 是折扣因子，表示未来奖励的现值（$\gamma$ 越接近1，智能体越有远见）。

5. 通过一个例子理解：井字棋（Tic-Tac-Toe）

本章用一个经典小游戏详细展示了强化学习的工作流程，有助于理解抽象概念。

5.1 问题设定

  • 智能体执“X”，对手（假设不完美）执“O”。
  • 游戏结束：智能体赢（+1）、输（-1）、平（0）。
  • 目标是学会最大化获胜概率。

5.2 状态、动作、价值

  • 状态：棋盘上所有可能棋子布局（约 $3^9$ 种，但实际少很多）。
  • 动作：在当前空白格下“X”。
  • 价值函数：每个状态的价值 $V(s)$ 表示从该状态出发，按当前策略能获胜的概率估计。
  • 初始值：所有未定状态设为0.5，获胜状态为1，失败为0。

5.3 学习过程（时序差分思想）

  1. 策略：通常采用 $\varepsilon$-greedy 策略（多数选当前最优动作，偶尔随机探索）。
  2. 经验生成：与对手对弈，得到状态序列。
  3. 更新价值：每走一步（除探索步外），用更新规则： $$ V(s) \leftarrow V(s) + \alpha \big[ V(s') - V(s) \big] $$ 这里 $s$ 是当前状态，$s'$ 是下一状态，$\alpha$ 是步长参数。这种利用后续状态估计来更新当前状态的方法，就是**时序差分学习（Temporal-Difference Learning）**的雏形。
  4. 效果：多次对弈后，价值函数逐渐逼近真实获胜概率，策略也趋于最优。

5.4 此例揭示的要点

  • 无模型学习：未显式建模对手行为，直接通过交互学习。
  • 自举（bootstrapping）：用后继状态的估计值更新当前状态，这是TD方法的特点。
  • 探索的重要性：随机探索保证了所有状态都能被访问到。

6. 概念关系图

以下用 Mermaid 语法描述强化学习问题中各要素的关系：

graph TD A[智能体 Agent] -->|选择动作 Action| B[环境 Environment] B -->|下一状态 Next State| A B -->|奖励 Reward| A C[策略 Policy π] -->|决定动作选择| A D[价值函数 Value] -->|评价状态/动作的长期优劣| A E[模型 Model] -->|模拟环境动态| A F[回报 Return] -->|累积奖励目标| A G["探索与利用 Exploration/Exploitation"] -->|平衡短期与长期收益| A

7. 本章在全书中的位置

  • 第1章 是全书的总览，定义了问题、核心术语和总体框架。
  • 第2章 从最简单的多臂老虎机（bandit）问题入手，讲解评估性反馈和探索策略，是后续章节的基础。
  • 第3章 正式引入马尔可夫决策过程（MDP），给出状态、动作、转移概率、回报的数学形式，是强化学习理论的核心。
  • 第4-8章 聚焦于表格型方法（状态空间有限），包括动态规划、蒙特卡洛、时序差分、资格迹等。
  • 第9章以后 引入函数近似，处理大规模或连续状态空间。
  • 第12-15章 探讨强化学习与心理学、神经科学的联系以及实际应用案例。

因此，第1章为后续所有内容奠定概念基础，理解本章对掌握全书至关重要。

8. 本章核心要点总结

  • 强化学习的本质：智能体通过与环境交互，学习能最大化累积奖励的行为策略。
  • 三大特征：闭环性、无直接指导、延迟奖励。
  • 探索与利用：必须平衡，否则无法找到最优解。
  • 基本要素：策略、奖励、价值函数、模型（可选）。
  • 价值函数是核心：几乎所有算法都围绕估计价值函数展开。
  • 时序差分思想：用后续估计更新当前估计，是蒙特卡洛和动态规划的结合。
  • 回报定义：分总回报和折扣回报，对应episodic和continuing两类任务。
  • 模型的有无：基于模型的方法可利用规划，无模型方法更简单通用。

9. 常见难点与学习建议

难点1：价值函数 vs. 奖励

  • 初学者容易混淆。记住：奖励是环境给的即时信号，价值是智能体估计的长期期望。
  • 例子：下棋时，吃掉对方一个车可能立即获得“好”的奖励，但若因此输掉比赛，该状态的价值其实很低。价值函数能正确评估这种长期后果。

难点2：探索与利用的权衡

  • 直观上容易理解，但实际设计中如何选择探索策略（如$\varepsilon$-greedy、UCB、softmax）需要经验。
  • 建议通过简单实验（如多臂老虎机）观察不同策略的效果。

难点3：自举（bootstrapping）的理解

  • TD方法用估计值更新估计值，这可能导致累积误差，但通常收敛。
  • 对比蒙特卡洛方法（等待真实回报）和动态规划（依赖模型），有助于理解自举的优缺点。

学习建议

  1. 动手实现井字棋例子：用表格存储状态价值，实现$\varepsilon$-greedy策略和上述更新规则，观察学习过程。
  2. 阅读后续章节前：确保能用自己的语言解释策略、价值、奖励、模型等术语。
  3. 关注历史背景：第1.7节的历史回顾有助于理解学科发展脉络，增强对核心思想的领悟。

通过以上讲解，你应该对强化学习的基本问题有了清晰的认识。下一章将进入具体的算法学习，从最简单的多臂老虎机开始。

第二章：多臂老虎机（Multi-arm Bandits）详细讲解

1. 本章定位与核心问题

前一章定义了强化学习的一般框架：智能体与环境交互，最大化累积奖励。但在最一般的情况下，状态、动作、延迟奖励、策略学习等因素交织，非常复杂。
第2章则从一个简化的设定入手——只有一个状态（即非关联性任务，nonassociative task），只存在动作选择及其立即奖励。这就是经典的 n-臂老虎机问题（n-armed bandit problem）。

通过研究这个简化版本，我们能清晰地区分评估性反馈（evaluative feedback）与指导性反馈（instructive feedback），并深入理解强化学习的核心挑战——探索与利用的平衡。本章介绍的许多方法（如ε-贪心、UCB、梯度方法）将作为基础，在后继章节中扩展至完整强化学习问题。

2. n-臂老虎机问题定义

2.1 问题描述

  • 智能体面临 $n$ 个动作（levers），每个动作对应一个未知的期望奖励（即动作价值 $q_*(a)$）。
  • 在每个时间步 $t$，智能体选择一个动作 $A_t$，环境根据该动作的真实价值 $q_*(A_t)$ 加上随机噪声给出立即奖励 $R_t$。
  • 目标是最大化累积奖励（或期望总奖励），通常假设在固定步数内（如1000步）或无限时间下。

2.2 重要术语

  • 动作价值（action value）：$q_*(a) = \mathbb{E}[R_t | A_t = a]$，即采取动作 $a$ 所获奖励的期望。
  • 估计价值（estimated value）：$Q_t(a)$ 表示在第 $t$ 步对动作 $a$ 价值的估计。
  • 贪心动作（greedy action）：当前估计价值最大的动作。
  • 探索（exploration）：选择非贪心动作，以获取更准确的价值估计。
  • 利用（exploitation）：选择贪心动作，最大化即时奖励。

3. 动作价值方法（Action-Value Methods）

3.1 样本平均法（Sample-Average Method）

最直接的估计方法：用实际观测到的奖励的平均值作为动作价值估计。

$$ Q_t(a) = \frac{\text{执行动作 } a \text{ 得到的奖励之和}}{\text{执行动作 } a \text{ 的次数}} = \frac{R_1 + R_2 + \cdots + R_{N_t(a)}}{N_t(a)}. $$

若 $N_t(a) = 0$，则设 $Q_t(a) = 0$（或其他初始值）。
优点：当 $N_t(a) \to \infty$ 时，$Q_t(a) \to q_*(a)$（大数定律）。

3.2 动作选择规则

(1) 贪心方法（Greedy）

$$ A_t = \arg\max_a Q_t(a). $$
  • 只利用，不探索。可能陷入次优。

(2) $\varepsilon$-贪心方法（$\varepsilon$-greedy）

  • 以概率 $1-\varepsilon$ 选择贪心动作，以概率 $\varepsilon$ 随机选择所有动作（包括贪心动作）。
  • 性质：保证所有动作被无限次尝试，估计值收敛到真值，最优动作被选中的概率趋于 $1-\varepsilon$。

3.3 示例：10-armed testbed

  • 构建2000个随机10臂老虎机任务，每个动作的真实价值 $q_*(a) \sim \mathcal{N}(0,1)$，奖励 $R_t \sim \mathcal{N}(q_*(A_t),1)$。
  • 比较贪心、$\varepsilon=0.01$、$\varepsilon=0.1$ 的性能（图2.1）：
    • 贪心方法初期上升快，但长期停滞（约1/3概率找到最优）。
    • $\varepsilon=0.1$ 探索更多，找到最优更快，但最终最优动作选中率不超过91%。
    • $\varepsilon=0.01$ 学习慢，但最终性能更好。

4. 增量实现（Incremental Implementation）

4.1 递推公式

为高效计算样本平均，可用增量更新：

$$ Q_{k+1} = Q_k + \frac{1}{k}\big[ R_k - Q_k \big], $$

其中 $Q_k$ 是前 $k-1$ 次奖励的平均，$R_k$ 是第 $k$ 次奖励。
通用形式：

$$ \text{新估计} = \text{旧估计} + \text{步长} \times (\text{目标} - \text{旧估计}). $$

4.2 步长参数 $\alpha$

  • 常数步长：$Q_{k+1} = Q_k + \alpha [R_k - Q_k]$，形成指数加权移动平均： $$ Q_{k+1} = (1-\alpha)^k Q_1 + \sum_{i=1}^k \alpha (1-\alpha)^{k-i} R_i. $$
  • 适用于非平稳环境，但对过去奖励的权重指数衰减。

4.3 收敛条件（随机近似理论）

若步长序列 $\alpha_k(a)$ 满足：

$$ \sum_{k=1}^{\infty} \alpha_k(a) = \infty, \quad \sum_{k=1}^{\infty} \alpha_k^2(a) < \infty, $$

则 $Q_t(a) \to q_*(a)$ 以概率1。样本平均（$\alpha_k = 1/k$）满足；常数步长不满足，因此不会完全收敛，但能跟踪变化。

5. 处理非平稳问题（Nonstationary Problems）

在实际强化学习中，环境常随时间变化，即 $q_*(a)$ 可能漂移。此时，应更重视近期奖励。

  • 常数步长 $\alpha$ 恰好实现“最近奖励权重更大”，适合非平稳。
  • 但样本平均对所有历史奖励等权，不适合非平稳。

6. 乐观初始值（Optimistic Initial Values）

  • 将初始估计值 $Q_1(a)$ 设为一个乐观值（如+5，远高于可能真实值）。
  • 效果：初期智能体因失望而频繁探索，从而更快发现最优动作。
  • 优点：简单有效，尤其对平稳问题。
  • 缺点：探索是暂时的，无法处理环境变化后的再次探索需求。

示例：图2.2显示，贪婪+乐观初始值比$\varepsilon=0.1$初期表现差，但后期更好。

7. 上置信界动作选择（Upper-Confidence-Bound, UCB）

UCB在选择动作时，不仅考虑当前估计价值，还考虑估计的不确定性：

$$ A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]. $$
  • 第二项是不确定性度量：$N_t(a)$ 越小，不确定性越大；$t$ 越大，所有动作的不确定性都被放大。
  • 参数 $c$ 控制探索程度。
  • 优点：比$\varepsilon$-greedy更高效，能根据确定性调整探索。
  • 缺点：难以推广到大规模状态空间或非平稳问题。

图2.3显示UCB性能通常优于$\varepsilon$-greedy，尤其在早期。

8. 梯度老虎机算法（Gradient Bandits）

不直接估计动作价值，而是学习一个动作偏好 $H_t(a)$，通过 softmax 转换为选择概率：

$$ \pi_t(a) = \frac{e^{H_t(a)}}{\sum_{b=1}^n e^{H_t(b)}}. $$

更新规则（基于随机梯度上升）：

$$ H_{t+1}(A_t) = H_t(A_t) + \alpha (R_t - \bar{R}_t)(1 - \pi_t(A_t)), $$

$$ H_{t+1}(a) = H_t(a) - \alpha (R_t - \bar{R}_t)\pi_t(a),\quad \forall a \neq A_t. $$

其中 $\bar{R}_t$ 是到时刻 $t$ 的平均奖励，作为基线（baseline），降低方差但不影响期望梯度。

图2.4显示有基线比无基线收敛更快。数学上可证明这是随机梯度上升。

9. 关联搜索（Associative Search / Contextual Bandits）

  • 前述问题都假设只有一个状态（非关联）。但真实强化学习需要在不同状态下采取不同动作，即学习策略 $\pi(a|s)$。
  • 关联搜索是介于多臂老虎机和完整MDP之间的中间问题：
    • 每步遇到一个状态（上下文），状态与奖励分布有关；
    • 动作只影响立即奖励，不改变后续状态。
  • 本章将多臂老虎机方法扩展到多状态情形，为后续MDP铺垫。

示例：多个老虎机任务，每个任务有不同颜色标识，智能体需根据颜色选择最佳动作。

10. 算法比较与总结

10.1 参数研究（图2.5）

  • 所有算法在合适参数下呈倒U形曲线。
  • UCB在10-armed testbed上表现最佳。
  • 算法对参数值较鲁棒（在一个数量级内变化性能尚可）。

10.2 核心要点

  • 探索与利用的平衡是强化学习的基本挑战，本章给出多种简单有效的策略。
  • 评估性反馈与指导性反馈的本质区别：前者只告诉动作好坏，后者告诉正确动作。
  • 增量更新和常数步长适合在线学习。
  • 乐观初始值、UCB、梯度方法提供了不同探索机制。
  • 关联搜索为完整强化学习问题铺路。

10.3 难点与建议

  • 难点1：理解探索与利用的权衡在不同场景下的表现（如平稳 vs 非平稳）。
    • 可通过模拟10-armed testbed观察不同算法的学习曲线。
  • 难点2：UCB的置信区间解释，以及对 $\ln t$ 的理解。
    • 多动手计算示例。
  • 难点3：梯度方法中的基线 $\bar{R}_t$ 作用。
    • 尝试无基线版本对比。
  • 建议：编程实现本章所有算法，在10-armed testbed上复现图2.5，加深理解。

11. 概念关系图

graph TD A[n-armed bandit problem] --> B[动作价值估计] A --> C[探索与利用平衡] B --> D[样本平均法] B --> E[增量更新] C --> F[ε-greedy] C --> G[UCB] C --> H[梯度方法] C --> I[乐观初始值] A --> J[非平稳问题] J --> K[常数步长] A --> L[关联搜索 contextual bandits] L --> M[多个状态]

12. 与前后的联系

  • 第1章 提出强化学习问题，本章是其简化版本，只关注评估性反馈和立即奖励。
  • 第3章 正式引入马尔可夫决策过程（MDP），状态和动作的序列关系，将本章方法扩展至完整强化学习。
  • 第5章以后 蒙特卡洛、时序差分等方法均需处理多状态和延迟奖励，但探索机制常借鉴本章思想（如ε-greedy、UCB在表格型方法中的应用）。

因此，掌握本章内容是后续学习的基础，尤其理解探索与利用的平衡对任何强化学习算法都至关重要。

13. 核心要点总结

  1. 问题定义：n-armed bandit 是只有一个状态的强化学习问题，核心是估计动作价值并平衡探索与利用。
  2. 动作价值估计：样本平均法，增量更新。
  3. 探索策略：
    • ε-greedy：简单有效。
    • UCB：基于不确定性。
    • 梯度方法：基于偏好随机选择。
    • 乐观初始值：初始高估诱导探索。
  4. 非平稳处理：常数步长跟踪变化。
  5. 关联搜索：引入状态信息，连接至完整MDP。
  6. 实用建议：无绝对最优方法，需根据问题特性（平稳性、步数、计算资源）选择并调参。

希望这份讲解能帮你深入理解多臂老虎机问题，并为后续章节打下坚实基础。动手实践是最好的学习方式，建议亲自编码验证每种算法的效果！

第三章：有限马尔可夫决策过程（Finite Markov Decision Processes）详细讲解

1. 引言：从交互问题到数学框架

第1章和第2章介绍了强化学习的直观概念和简化版本（多臂老虎机）。现在，我们需要一个能够描述多状态、序列决策、延迟奖励的通用数学框架。这就是马尔可夫决策过程（Markov Decision Process, MDP）。

本章将正式定义强化学习问题的数学形式，包括智能体与环境的交互方式、回报的定义、马尔可夫性质、价值函数、贝尔曼方程以及最优策略的概念。本章是全书的理论基石，所有后续算法都在此框架下讨论。

2. 智能体-环境接口（Agent-Environment Interface）

2.1 定义

强化学习问题由两个实体构成：

  • 智能体（Agent）：学习和决策的主动方。
  • 环境（Environment）：智能体之外的一切，与智能体交互。

在离散时间步 $t = 0,1,2,\dots$ 上，交互过程如下：

  • 智能体接收环境状态的表示 $S_t \in \mathcal{S}$（$\mathcal{S}$ 是状态集合）。
  • 基于 $S_t$，智能体选择一个动作 $A_t \in \mathcal{A}(S_t)$（$\mathcal{A}(S_t)$ 是在状态 $S_t$ 下可用的动作集合）。
  • 执行动作后，环境在下一个时间步 $t+1$ 返回：
    • 一个数值奖励 $R_{t+1} \in \mathcal{R} \subset \mathbb{R}$
    • 新的状态 $S_{t+1}$

这种交互形成了闭环：智能体的动作影响环境，环境反馈又影响智能体的后续选择。

2.2 示例

例3.1 生物反应器
状态：温度、搅拌速率等传感器读数；动作：目标温度和搅拌速率；奖励：有用化学品的瞬时产出率。

例3.2 拾放机器人
状态：关节角度和速度；动作：施加在电机上的电压；奖励：+1 成功拾取物体，同时每步给予小的负奖励以鼓励平滑运动。

例3.3 回收机器人
状态：电池电量（高/低）；动作：搜索、等待、回充；奖励：收集易拉罐得+1，电池耗尽得-3。

3. 目标和奖励（Goals and Rewards）

3.1 奖励假设（Reward Hypothesis）

任何目标和目的都可以归结为最大化智能体接收到的标量信号（奖励）的累积和的期望值。

  • 奖励信号是智能体学习的目标定义。
  • 关键：奖励应该指示“我们想要实现什么”，而不是“如何实现它”。例如，下棋时只应在最终获胜时给予正奖励，而不是对吃子给予奖励，否则可能学到为吃子而输棋的策略。

3.2 例子

  • 机器人行走：每前进一步给正奖励。
  • 逃出迷宫：每步给-1，鼓励尽快逃出。
  • 回收机器人：收集易拉罐+1，电池耗尽-3。

4. 回报（Return）

智能体的目标是最大化长期累积奖励，即回报 $G_t$。定义方式取决于任务类型。

4.1 回合制任务（Episodic Tasks）

  • 交互自然划分为独立的回合（episodes），每个回合终止于一个终止状态，然后重置。
  • 回报是后续奖励之和： $$ G_t = R_{t+1} + R_{t+2} + \cdots + R_T, $$ 其中 $T$ 是回合结束的时刻。

4.2 持续性任务（Continuing Tasks）

  • 交互无限持续，没有终止状态。
  • 必须使用**折扣（discounting）**使无限和收敛： $$ G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}, \quad 0 \leq \gamma \leq 1. $$
    • $\gamma$ 称为折扣率，表示未来奖励的现值。
    • $\gamma = 0$：只关心立即奖励（短视）。
    • $\gamma \to 1$：强烈考虑未来奖励（有远见）。

例3.4 倒立摆

  • 回合制视角：每步+1直到失败，回报 = 失败前的步数。
  • 持续性视角：每步0，失败时-1，折扣回报与失败时间相关。

5. 回合制与持续性任务的统一符号

为统一处理两种任务，可以引入吸收状态（absorbing state）：

  • 进入吸收状态后，所有后续奖励为0，且状态不再改变。
  • 于是持续性任务的公式 $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$ 同样适用于回合制任务（若 $\gamma=1$ 且回合有限，则和仍有限）。
  • 常用简化符号： $$ G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}, $$ 其中 $T$ 可以是 $\infty$（持续性任务），但 $\gamma=1$ 时不能同时 $T=\infty$。

6. 马尔可夫性质（The Markov Property）

6.1 定义

状态信号应包含历史中所有相关信息，使得未来只依赖于当前状态（即历史可压缩）。数学上：

  • 环境在 $t+1$ 的响应（新状态和奖励）的概率只依赖于 $t$ 的状态和动作，与之前的历史无关： $$ p(s', r \mid s, a) \doteq \Pr\{S_{t+1}=s', R_{t+1}=r \mid S_t=s, A_t=a\}. $$
  • 如果这个条件对所有历史成立，则状态具有马尔可夫性质。

6.2 重要性

  • 马尔可夫性使得我们可以基于当前状态做出最优决策，无需回顾历史。
  • 实际中状态信号往往只是对真实世界状态的不完全描述，但我们可以近似地将其视为马尔可夫。

例3.5 倒立摆的状态
理想情况下，需要知道位置、速度、角度、角速度才满足马尔可夫性，但粗略量化后仍可求解。

例3.6 抽牌扑克
无法知道对手的手牌，但根据下注、换牌数等信息，可以构建近似马尔可夫状态。

7. 马尔可夫决策过程（Markov Decision Processes, MDP）

7.1 定义

如果一个强化学习任务具有马尔可夫性质，则称为马尔可夫决策过程。若状态和动作空间有限，称为有限MDP。

一个有限MDP由以下要素完全描述：

  • 状态集合 $\mathcal{S}$
  • 动作集合 $\mathcal{A}(s)$（对每个状态）
  • 动态特性： $$ p(s', r \mid s, a) = \Pr\{S_{t+1}=s', R_{t+1}=r \mid S_t=s, A_t=a\}. $$ 这些概率完全决定了环境的行为。

7.2 派生量

  • 状态-动作对的期望奖励： $$ r(s,a) = \mathbb{E}[R_{t+1} \mid S_t=s, A_t=a] = \sum_{r \in \mathcal{R}} r \sum_{s' \in \mathcal{S}} p(s',r \mid s,a). $$
  • 状态转移概率： $$ p(s' \mid s,a) = \Pr\{S_{t+1}=s' \mid S_t=s, A_t=a\} = \sum_{r \in \mathcal{R}} p(s',r \mid s,a). $$
  • 给定下一个状态的期望奖励： $$ r(s,a,s') = \mathbb{E}[R_{t+1} \mid S_t=s, A_t=a, S_{t+1}=s'] = \frac{\sum_{r} r \, p(s',r \mid s,a)}{p(s' \mid s,a)}. $$

例3.7 回收机器人MDP

  • 状态：高电量、低电量。
  • 动作：在高电量时可搜索或等待；在低电量时可搜索、等待或回充。
  • 转移概率和期望奖励如书中表3.1所示。可通过状态转移图（图3.3）直观表示。

8. 价值函数（Value Functions）

8.1 策略（Policy）

策略 $\pi$ 是从状态到动作选择概率的映射：$\pi(a \mid s) = \Pr\{A_t = a \mid S_t = s\}$。

8.2 状态价值函数 $v_\pi(s)$

从状态 $s$ 出发，按照策略 $\pi$ 行动所获得的期望回报：

$$ v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s] = \mathbb{E}_\pi\left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t = s \right]. $$

8.3 动作价值函数 $q_\pi(s,a)$

从状态 $s$ 采取动作 $a$，然后按照策略 $\pi$ 行动所获得的期望回报：

$$ q_\pi(s,a) = \mathbb{E}_\pi[G_t \mid S_t = s, A_t = a]. $$

8.4 贝尔曼方程（Bellman Equation）——价值函数的递归关系

对于 $v_\pi$，可以分解为立即奖励和未来价值的期望：

$$ \begin{aligned} v_\pi(s) &= \mathbb{E}_\pi[G_t \mid S_t = s] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ &= \sum_a \pi(a \mid s) \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma \mathbb{E}_\pi[G_{t+1} \mid S_{t+1}=s'] \right] \\ &= \sum_a \pi(a \mid s) \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma v_\pi(s') \right]. \end{aligned} $$

这就是 $v_\pi$ 的贝尔曼方程。它表明当前状态的价值等于立即奖励的期望加上下一状态价值的折扣期望。

例3.8 网格世界（图3.5）
一个4×4网格，每个状态（格子）有四个动作，但撞墙会导致留在原地并得到-1。随机策略（所有动作等概率）下，通过求解贝尔曼方程得到每个状态的价值。

例3.9 高尔夫（图3.6）
用价值函数表示从不同位置到洞口的期望杆数。展示了“价值”如何反映长期结果。

9. 最优价值函数与最优策略（Optimal Value Functions and Optimal Policies）

9.1 定义

  • 最优状态价值函数 $v_*(s)$： $$ v_*(s) = \max_\pi v_\pi(s) \quad \forall s. $$
  • 最优动作价值函数 $q_*(s,a)$： $$ q_*(s,a) = \max_\pi q_\pi(s,a) \quad \forall s,a. $$ 它们描述了在所有策略中能获得的最大期望回报。

9.2 贝尔曼最优方程（Bellman Optimality Equation）

对于 $v_*$，有：

$$ v_*(s) = \max_a \mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t=s, A_t=a] = \max_a \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma v_*(s') \right]. $$

对于 $q_*$，有：

$$ q_*(s,a) = \mathbb{E}\left[ R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \mid S_t=s, A_t=a \right] = \sum_{s',r} p(s',r \mid s,a) \left[ r + \gamma \max_{a'} q_*(s',a') \right]. $$

9.3 最优策略

  • 任何贪心策略（greedy policy）关于 $v_*$ 或 $q_*$ 都是最优的。
  • 具体地，若已知 $v_*$，则最优动作可通过单步前瞻得到：$\pi_*(s) = \arg\max_a \sum_{s',r} p(s',r \mid s,a) [r + \gamma v_*(s')]$。
  • 若已知 $q_*$，则无需模型，直接选择使 $q_*(s,a)$ 最大的动作。

例3.10 高尔夫的最优价值（图3.6下半部分）展示了 $q_*(s, \text{driver})$ 的轮廓，从发球台用一号木，之后使用最优动作，期望杆数为-3。

例3.11 回收机器人的贝尔曼最优方程 给定了两个状态的非线性方程组。

例3.12 网格世界的最优解（图3.8）展示了最优价值函数和最优策略。

10. 最优性与近似（Optimality and Approximation）

  • 在理论上，我们可以通过求解贝尔曼最优方程得到最优策略，但这需要：
    1. 精确的环境动态 $p(s',r \mid s,a)$（通常未知）；
    2. 巨大的计算资源（状态数爆炸时不可行）；
    3. 马尔可夫性质严格成立。
  • 实际中，我们只能寻求近似最优解。强化学习方法通过交互采样来逼近最优策略，尤其关注那些在智能体访问频繁的状态上提高精度。

11. 概念关系图

graph TD A[强化学习问题] --> B[马尔可夫决策过程 MDP] B --> C[状态集 S, 动作集 A, 奖励 R] B --> D["动态函数 p(s',r|s,a)"] B --> E[策略 π] E --> F["状态价值 vπ(s)"] E --> G["动作价值 qπ(s,a)"] F --> H[贝尔曼方程] G --> H H --> I["价值迭代/策略迭代"] I --> J["最优价值函数 v* / q*"] J --> K["最优策略 π*"] K --> L[贝尔曼最优方程]

12. 与前后的联系

  • 第1章 直观介绍了强化学习问题，本章提供了严格的数学形式。
  • 第2章 的多臂老虎机是MDP的一个极端特例（单状态）。
  • 第4章及以后 将基于MDP框架介绍各种求解算法（动态规划、蒙特卡洛、时序差分等），并逐步放松对模型的依赖，最终扩展到大规模问题的函数近似方法。

13. 核心要点总结

  1. MDP 是强化学习的标准框架：由状态、动作、奖励、转移概率组成。
  2. 马尔可夫性质 保证决策仅依赖当前状态，是理论推导的基础。
  3. 价值函数 量化长期好坏，分为 $v_\pi$ 和 $q_\pi$。
  4. 贝尔曼方程 揭示价值函数的递归结构，是几乎所有算法的出发点。
  5. 最优价值函数 定义理论极限，贝尔曼最优方程 提供求解目标。
  6. 策略 决定行为，最优策略可通过贪心于最优价值函数获得。
  7. 实际求解 通常只能近似，强调在访问频繁的状态上提高精度。

14. 常见难点与学习建议

难点1：理解价值函数与立即奖励的区别

  • 立即奖励是局部、当前的，而价值是长期累积的。价值高的状态可能立即奖励很低（例如通往胜利的中间局面）。

难点2：贝尔曼方程的推导

  • 初学者易混淆期望符号。关键在于将回报分解为立即奖励 + 后续回报的折扣，并利用全期望公式。

难点3：策略与价值函数的相互依赖

  • 价值函数依赖于策略，策略改进又依赖于价值函数，这种循环是广义策略迭代（GPI）的基础。

学习建议

  1. 手动推导贝尔曼方程 对简单MDP（如回收机器人）写出显式方程。
  2. 实现网格世界 编程计算给定策略下的价值函数（第4章会学迭代法）。
  3. 理解最优策略的贪心性：即使模型未知，只要拥有 $q_*$，就能直接选出最优动作，这是Q学习的核心思想。
  4. 反复阅读例3.8、3.9、3.12，它们直观展示了价值函数的几何意义。

掌握本章内容后，你就拥有了理解所有后续算法的理论工具。从下一章开始，我们将学习如何实际求解MDP。

第四章：动态规划（Dynamic Programming）详细讲解

1. 引言：从理论到算法

在第三章中，我们学习了马尔可夫决策过程（MDP）的数学框架，定义了价值函数、贝尔曼方程和最优策略。但有了这些理论，如何实际求解最优策略呢？
动态规划（Dynamic Programming, DP） 提供了一组算法，可以在已知环境模型（即 $p(s',r|s,a)$）的情况下，计算最优价值函数和最优策略。尽管DP在实际应用中常因“维度灾难”而受限，但它是理解后续所有强化学习算法的基础。

本章的核心思想：利用贝尔曼方程，通过自举（bootstrapping）——即用后继状态的估计值来更新当前状态——迭代改进价值函数，最终收敛到最优。

2. 环境假设

本章假设环境是有限MDP，即：

  • 状态集 $\mathcal{S}$ 和动作集 $\mathcal{A}(s)$ 有限。
  • 已知动态 $p(s', r \mid s, a)$ 对任意 $s, a, r, s'$。
  • 目标是求解最优价值函数 $v_*$ 或 $q_*$，进而得到最优策略。

3. 策略评估（Policy Evaluation）

3.1 问题定义

给定一个策略 $\pi$，计算其状态价值函数 $v_\pi$。这称为策略评估或预测问题。

3.2 迭代策略评估

利用贝尔曼方程（4.4）作为更新规则：

$$ v_{k+1}(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r + \gamma v_k(s') \right], \quad \forall s \in \mathcal{S}. $$
  • $v_k$ 表示第 $k$ 次迭代的估计值函数。
  • 该更新是对所有状态同时进行的（或用“就地”方式逐个更新），称为一次扫描（sweep）。
  • 当 $k \to \infty$ 时，$v_k \to v_\pi$（在保证收敛的条件下，如 $\gamma < 1$ 或回合终止）。

3.3 实现细节

  • 两种数组 vs 就地更新：使用两个数组（旧值和新值）可以保持更新同步，就地更新收敛更快但依赖更新顺序。
  • 终止条件：通常当 $\max_s |v_{k+1}(s) - v_k(s)| < \theta$ 时停止（$\theta$ 是小阈值）。

例4.1 网格世界（图4.1）
4×4网格，每个非终止状态有四个动作（上下左右），撞墙留在原地并得-1，随机策略（所有动作等概率）。通过迭代策略评估得到价值函数收敛到每个状态到终止状态的负期望步数。

4. 策略改进（Policy Improvement）

4.1 动机

有了当前策略的价值函数 $v_\pi$，我们想知道是否存在更好的策略。考虑在状态 $s$ 下选择动作 $a \neq \pi(s)$，然后继续遵循 $\pi$，其价值为：

$$ q_\pi(s,a) = \sum_{s',r} p(s',r|s,a) \left[ r + \gamma v_\pi(s') \right]. $$

若 $q_\pi(s,a) > v_\pi(s)$，则选择 $a$ 比始终遵循 $\pi$ 好。

4.2 策略改进定理

对于任意一对确定性策略 $\pi$ 和 $\pi'$，如果对所有 $s$ 有 $q_\pi(s, \pi'(s)) \ge v_\pi(s)$，则 $v_{\pi'}(s) \ge v_\pi(s)$（对任意 $s$）。
严格不等式至少在一个状态成立时，则至少一个状态的价值严格提高。

4.3 贪心策略

根据当前价值函数 $v_\pi$，定义贪心策略 $\pi'$：

$$ \pi'(s) = \arg\max_a q_\pi(s,a) = \arg\max_a \sum_{s',r} p(s',r|s,a) \left[ r + \gamma v_\pi(s') \right]. $$

由策略改进定理，$\pi'$ 至少和 $\pi$ 一样好。若与 $\pi$ 相等，则 $\pi$ 已是最优。

例4.1 续：对随机策略的 $v_\pi$ 做贪心改进，得到的新策略如图4.2右下所示，比随机策略好得多（实际上就是最优策略）。

5. 策略迭代（Policy Iteration）

5.1 算法流程

结合策略评估和策略改进，交替进行：

  1. 初始化：任选策略 $\pi_0$。
  2. 评估：计算当前策略的价值函数 $v_{\pi_k}$。
  3. 改进：根据 $v_{\pi_k}$ 构造贪心策略 $\pi_{k+1}$。
  4. 重复2-3直至策略稳定（不再变化）。

由于有限MDP的策略数有限，策略迭代一定在有限步内收敛到最优策略和最优价值函数。

5.2 伪代码

图4.3给出了完整的策略迭代算法（使用迭代策略评估）。

例4.2 杰克租车问题
杰克有两个租车点，每日租车和还车数量服从泊松分布，他可以在夜间移车（成本2元/辆）。状态是两处车辆数，动作是移车数量。图4.4展示了策略迭代找到的策略序列，最终达到最优。

6. 价值迭代（Value Iteration）

6.1 动机

策略迭代的每次评估都需要多次扫描，可能很慢。价值迭代则只进行一次评估扫描就立即改进，即：

$$ v_{k+1}(s) = \max_a \sum_{s',r} p(s',r|s,a) \left[ r + \gamma v_k(s') \right], \quad \forall s. $$

这相当于将贝尔曼最优方程作为更新规则。可以看作截断的策略迭代。

6.2 收敛性

在相同条件下（$\gamma < 1$ 或回合终止），序列 $\{v_k\}$ 收敛到 $v_*$。

6.3 终止条件

通常检查 $\max_s |v_{k+1}(s) - v_k(s)| < \theta$ 时停止，并输出贪心策略作为近似最优策略。

例4.3 赌徒问题
赌徒有资本 $s \in \{1,...,99\}$，每轮押注 $a$，以概率 $p_h$ 赢回双倍，否则输掉。目标是积累到100。价值迭代求解最优策略（图4.6）。有趣的是最优策略不是简单的“全押”，而是取决于当前资本。

7. 异步动态规划（Asynchronous Dynamic Programming）

7.1 问题

传统DP需要对所有状态进行扫描，当状态空间极大时（如西洋双陆棋 $10^{20}$ 状态），单次扫描都不可行。

7.2 异步DP的思想

  • 不必按顺序扫描所有状态，可以任意顺序更新状态的值。
  • 只要每个状态在无穷多次更新中被访问，算法仍可收敛。
  • 允许在更新中混合价值迭代和策略评估，甚至可以在与环境交互时实时更新。

7.3 优势

  • 可将计算聚焦在相关状态上（如当前智能体访问频繁的状态）。
  • 易于与实时交互结合。

8. 广义策略迭代（Generalized Policy Iteration, GPI）

8.1 核心思想

策略迭代、价值迭代、异步DP都可以统一到广义策略迭代的框架中：

  • 两个交替过程：策略评估（使价值函数与当前策略一致）和策略改进（使策略对当前价值函数贪心）。
  • 它们相互竞争又相互协作，最终收敛到最优。

8.2 图示（图4.7）

  • 价值函数和策略分别表示为两条线。
  • 策略评估将价值函数拉向“与策略一致”的线。
  • 策略改进将策略拉向“对价值函数贪心”的线。
  • 反复作用最终到达交点（最优）。

几乎所有强化学习方法都可视为GPI的一种实例。

9. DP的效率

  • DP可以在多项式时间内找到最优策略（状态数 $n$，动作数 $m$），而直接搜索策略空间需要 $m^n$ 步。
  • 维度灾难：状态数随状态变量数指数增长，这是问题的固有难度，并非DP独有。
  • 实践中DP可处理百万级状态；异步DP可进一步扩展到更大问题。

10. 概念关系图

graph TD A[MDP模型] --> B[策略评估] A --> C[策略改进] B --> D[价值函数 vπ] C --> E[改进的策略 π'] D --> F[策略迭代] E --> F F --> G["最优策略 v* / π*"] A --> H[贝尔曼最优方程] H --> I[价值迭代] I --> G F --> J[广义策略迭代 GPI] I --> J J --> K[所有强化学习方法]

11. 与前后的联系

  • 第3章 给出了MDP的理论基础，本章则给出了基于模型的精确求解方法。
  • 第5章 开始转向无模型方法（蒙特卡洛），不需要环境模型。
  • 第6章 的时序差分（TD）结合了DP的自举和蒙特卡洛的采样，是本章思想的延伸。
  • 第7章 资格迹进一步统一了TD和蒙特卡洛。
  • 第8章 将规划（使用模型）和学习（无模型）通过GPI统一。

12. 核心要点总结

  1. 策略评估：迭代贝尔曼方程计算给定策略的价值。
  2. 策略改进：基于当前价值函数贪心构造更好策略，策略改进定理保证提升。
  3. 策略迭代：交替评估和改进，收敛到最优。
  4. 价值迭代：将贝尔曼最优方程作为更新，省去完整评估。
  5. 异步DP：打破扫描限制，灵活更新状态。
  6. 广义策略迭代（GPI）：评估和改进交互作用的核心框架。
  7. 自举：用后继状态的估计更新当前状态，是DP和TD的共同特点。
  8. DP的局限性：需要模型，且面临维度灾难，但仍是理论基石。

13. 常见难点与学习建议

难点1：区分策略评估和价值迭代

  • 策略评估：对所有动作求和（依据给定策略）。
  • 价值迭代：对所有动作取最大（隐含策略改进）。
    对比式(4.5)和式(4.10)可清晰看出差异。

难点2：理解GPI的收敛性

  • 即使两个过程互相干扰，最终总能收敛，因为策略改进总是在价值函数正确时停止，而价值函数又随策略改进而变化。图4.7直观解释。

难点3：异步DP的收敛条件

  • 关键：所有状态必须被无限次更新，但顺序任意。这比同步扫描更灵活，但理论证明仍成立。

学习建议

  1. 手动计算：对小网格世界手算几轮策略评估和价值迭代，感受数值变化。
  2. 编程实现：
    • 实现策略迭代求解例4.2（杰克租车）并观察策略改进过程。
    • 实现价值迭代求解例4.3（赌徒问题），探索不同 $p_h$ 下的策略。
  3. 对比算法：比较策略迭代和价值迭代的收敛速度（可尝试在简单MDP上记录迭代次数）。
  4. 深入GPI：思考在后续无模型方法（如Q-learning）中，GPI如何体现。

掌握本章后，你就理解了基于模型的精确求解方法。下一章将进入无模型的蒙特卡洛方法，学习如何直接从经验中学习价值函数。

第五章：蒙特卡洛方法（Monte Carlo Methods）详细讲解

1. 引言：从模型已知到模型未知

前几章我们学习了动态规划（DP）方法，它们依赖于完全已知的环境模型（即状态转移概率和期望奖励）。然而在大多数实际问题中，我们无法获得精确的模型，只能通过与环境的交互获取经验——即状态、动作、奖励的序列样本。
蒙特卡洛（Monte Carlo, MC）方法正是从这样的经验中直接学习的算法。它不需要环境模型，而是通过对完整回合（episode）的回报进行平均来估计价值函数，并进而改进策略。

2. 蒙特卡洛方法的基本特点

  • 适用范围：仅适用于回合制任务（episodic tasks），即交互能够自然划分为有限长度的回合，每个回合最终进入终止状态。
  • 学习方式：在每个回合结束后，利用该回合中获得的实际回报来更新价值估计。因此，MC方法是回合级增量（episode-by-episode），而非步进级在线学习。
  • 核心思想：根据大数定律，通过大量样本的平均值逼近期望值。

3. 蒙特卡洛预测（Monte Carlo Prediction）

预测问题：给定一个策略 $\pi$，估计其状态价值函数 $v_\pi$（或动作价值函数 $q_\pi$）。

3.1 状态价值估计

  • 首次访问MC（first-visit MC）：对于每个回合中第一次访问到的状态 $s$，记录该回合从 $s$ 之后获得的回报 $G_t$，然后对所有回合中首次访问 $s$ 的回报取平均，作为 $V(s)$ 的估计。
  • 每次访问MC（every-visit MC）：对于回合中每次访问到的状态 $s$，都记录其回报并取平均。

收敛性：当访问次数趋于无穷时，两种方法都收敛到 $v_\pi(s)$（首次访问MC更直观，每次访问MC也成立）。

3.2 动作价值估计

类似地，可以估计 $q_\pi(s,a)$。但由于策略可能是确定性的，许多动作可能从未被访问过，导致无法学习。因此需要保持探索，确保所有状态-动作对都能被无限次访问。

例5.1 二十一点（Blackjack）

  • 状态：玩家当前点数（12-21）、庄家明牌（A-10）、是否有可用的A。
  • 动作：要牌（hit）或停牌（stick）。
  • 策略：点数≥20时停牌，否则要牌。
  • 通过模拟大量对局，对每个状态计算平均回报，得到价值函数（图5.2）。这个例子中状态不会重复出现，因此首次访问和每次访问等价。

3.3 蒙特卡洛备份图

MC的备份图（图5.3）与DP不同：它显示了一条完整的状态轨迹（从当前状态直到回合结束），而不是一步转移的所有可能分支。

4. 蒙特卡洛控制（Monte Carlo Control）

4.1 广义策略迭代（GPI）框架

与DP一样，MC控制也遵循GPI：交替进行策略评估和策略改进，但评估基于采样回报而非模型。

4.2 探索问题

为了保证所有状态-动作对都能被充分采样，必须解决探索问题。本章介绍三种方法：

  1. 探索性开端（Exploring Starts）：假设每个回合以随机的状态-动作对开始，保证所有对都被访问。
  2. 同策略方法（on-policy）：评估和改进的是同一个策略，且该策略必须保持探索性（如ε-soft）。
  3. 异策略方法（off-policy）：用行为策略（探索性）生成数据，学习目标策略（通常为贪心策略）。

5. 探索性开端（Exploring Starts）

假设我们能够控制回合的起始状态和动作，使每个状态-动作对都有非零概率作为开端。这样，即使使用贪心策略也能保证所有对都被无限次访问。

算法：MC ES（蒙特卡洛探索性开端）（图5.4）

  • 对每个回合，随机选择起始状态和动作。
  • 执行当前策略（通常是贪心）直至结束。
  • 对回合中出现的每个状态-动作对，用其回报更新估计值。
  • 策略改进：将策略改为对当前估计值贪心。

例5.3 二十一点求解最优策略
应用MC ES，初始策略为之前评估的“点数≥20停牌”，最终学到的策略（图5.5）与Thorp的“基本策略”几乎一致，仅有一处细微差异（可能是由于版本不同）。

理论开放问题：MC ES的收敛性尚未被严格证明，但实验表明它收敛到最优。

6. 同策略蒙特卡洛控制（On-policy MC Control）

6.1 动机

探索性开端在实际中难以保证（如真实机器人无法随意重置状态）。因此，我们需要一种不依赖此假设的方法。

6.2 ε-soft策略

定义：策略 $\pi$ 是 ε-soft，如果对每个状态和所有动作有 $\pi(a|s) \ge \frac{\epsilon}{|\mathcal{A}(s)|}$（$\epsilon > 0$）。
ε-贪心策略 是ε-soft的一种特殊形式：以 $1-\epsilon+\frac{\epsilon}{|\mathcal{A}(s)|}$ 的概率选择贪心动作，其余动作等概率 $\frac{\epsilon}{|\mathcal{A}(s)|}$。

6.3 策略改进定理在ε-soft中的推广

设 $\pi$ 为任意ε-soft策略，$\pi'$ 为关于 $q_\pi$ 的ε-贪心策略。可以证明 $v_{\pi'}(s) \ge v_\pi(s)$（对所有 $s$），且等号成立当且仅当 $\pi$ 已是所有ε-soft策略中的最优。

证明思路：利用策略改进定理，将ε-soft策略视为在“扩展环境”中允许任意策略，该环境以 $1-\epsilon$ 的概率按原环境转移，以 $\epsilon$ 的概率随机选择动作。这样，ε-贪心策略就是该扩展环境中的普通贪心策略，因此改进成立。

6.4 算法

同策略MC控制算法（图5.6）：

  • 使用ε-贪心策略生成回合。
  • 对回合中每个状态-动作对，用其回报更新估计值。
  • 策略自动保持为ε-贪心（无需显式改进，因为动作选择策略就是ε-贪心）。

7. 异策略蒙特卡洛预测（Off-policy MC Prediction）

7.1 动机

我们希望学习最优策略（目标策略 $\pi$），但行为策略 $\mu$ 可以任意（通常是探索性的）。这称为异策略学习。

7.2 重要性采样（Importance Sampling）

重要性采样是一种用来自某分布的样本来估计另一分布下期望值的技术。在MC中，我们需要根据 $\mu$ 生成的轨迹，估计 $\pi$ 下的期望回报。

设一个轨迹 $S_t, A_t, S_{t+1}, A_{t+1}, \dots, S_T$ 在策略 $\pi$ 下的概率为：

$$ \prod_{k=t}^{T-1} \pi(A_k|S_k) p(S_{k+1}|S_k,A_k). $$

在策略 $\mu$ 下的概率为类似乘积。两者的比值即为重要性采样比率：

$$ \rho_{t:T-1} = \frac{\prod_{k=t}^{T-1} \pi(A_k|S_k)}{\prod_{k=t}^{T-1} \mu(A_k|S_k)}. $$

注意转移概率 $p$ 抵消，因此比率只依赖于策略和所选动作，与模型无关。

7.3 普通重要性采样（Ordinary Importance Sampling）

$$ V(s) = \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{|\mathcal{T}(s)|}. $$
  • 估计量无偏，但方差可能极大（甚至无穷大）。
  • 因为 $\rho$ 可能很大，导致估计值剧烈波动。

7.4 加权重要性采样（Weighted Importance Sampling）

$$ V(s) = \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1}}. $$
  • 分母是权重和，若分母为0则估计为0。
  • 有偏（但偏差随样本增加趋于0），方差通常远小于普通重要性采样，且有限。

例5.4 二十一点状态值估计
用随机策略生成数据，估计目标策略（点数≥20停牌）下某个状态的值。图5.7显示加权重要性采样误差远小于普通重要性采样。

例5.5 无限方差示例
一个简单的MDP（图5.8）展示了普通重要性采样估计的方差无穷大，估计值不收敛，而加权重要性采样立即得到正确值。

8. 增量实现（Incremental Implementation）

8.1 普通重要性采样的增量更新

可直接使用第2章的增量平均公式，将 $R$ 替换为 $\rho G$。

8.2 加权重要性采样的增量更新

对于加权平均，需要维护累积权重 $C_n$ 和当前估计 $V_n$，新样本到来时：

$$ V_{n+1} = V_n + \frac{W_n}{C_n} \left( G_n - V_n \right), \quad C_{n+1} = C_n + W_{n+1}. $$

其中 $W_n$ 是重要性采样比率。

图5.9给出了完整的增量异策略MC预测算法。

9. 异策略蒙特卡洛控制（Off-policy MC Control）

9.1 基本思想

  • 行为策略 $\mu$ 为任意软策略（如ε-soft），保证探索。
  • 目标策略 $\pi$ 为关于当前 $Q$ 的贪心策略。
  • 用重要性采样从 $\mu$ 生成的数据中学习 $q_\pi$。

9.2 算法

图5.10给出了异策略MC控制算法。注意更新只针对那些动作与目标策略一致的轨迹（即 $\pi(A_t|S_t) > 0$）。

  • 每步计算重要性采样比率 $\rho$。
  • 更新时只对当前状态-动作对进行，且只使用 $\rho$ 缩放更新量。
  • 策略改进隐式地通过将 $\pi$ 设为对 $Q$ 贪心完成。

9.3 缺点

  • 学习效率低：只有完整执行了目标策略的轨迹尾部才能用于学习，如果探索动作频繁，学习会非常缓慢。
  • 解决方向：结合时序差分（TD）方法（下一章）可以缓解此问题。

10. 截断回报的重要性采样（高级主题）

对于折扣因子 $\gamma < 1$，可以通过将回报分解为多个“平坦部分回报”（flat partial returns）来降低方差。每个部分回报只到某个未来时刻 $h$，然后乘以相应的重要性采样比率，加权求和。这种方法称为截断重要性采样（truncated importance sampling），公式见(5.8)和(5.9)。它能在不引入偏差的前提下减小方差。

11. 概念关系图

graph TD A[Monte Carlo方法] --> B[预测] A --> C[控制] B --> D[首次访问MC] B --> E[每次访问MC] B --> F[动作价值估计] C --> G[探索问题] G --> H[Exploring Starts] G --> I["On-policy (ε-soft)"] G --> J[Off-policy] J --> K[重要性采样] K --> L[普通重要性采样] K --> M[加权重要性采样] J --> N[Off-policy MC控制] I --> O[On-policy MC控制] H --> P[MC ES] P --> Q[最优策略] O --> Q N --> Q

12. 与前后的联系

  • 第2章 的多臂老虎机是单状态情况下的评估性反馈问题，本章将其扩展为多状态、序列决策的MC方法。
  • 第3-4章 的DP需要模型，本章则完全无模型，直接从经验学习。
  • 第6章 的时序差分（TD）结合了MC的采样和DP的自举，是更高效的在线学习方法。
  • 第7章 的资格迹（eligibility traces）统一了MC和TD，形成TD(λ)算法。
  • 第8章 的Dyna架构将学习与规划结合，其中规划部分可以用MC方法从模拟经验中学习。

13. 核心要点总结

  1. MC方法的特点：无模型、仅适用于回合制任务、基于完整回报的平均。
  2. 预测：
    • 首次访问MC和每次访问MC都收敛。
    • 动作价值估计需要处理未访问动作，引出探索问题。
  3. 控制：
    • 探索性开端：理论简单，但不实用。
    • 同策略：使用ε-soft策略保证探索，策略改进定理在ε-soft中仍然成立。
    • 异策略：重要性采样将来自行为策略的数据转化为目标策略的估计，但方差大、学习慢。
  4. 重要性采样：
    • 普通重要性采样无偏但方差大。
    • 加权重要性采样有偏但方差小，实际中更常用。
  5. 增量实现：加权重要性采样需维护累积权重。
  6. 异策略控制：理论上可行，但效率问题促使我们转向TD方法。

14. 常见难点与学习建议

难点1：重要性采样比率的推导

  • 注意比率中转移概率抵消，只依赖策略。建议亲手推导一两个轨迹的比率，理解其含义。

难点2：加权重要性采样的偏差

  • 虽然初始估计有偏，但随着样本增加，分母趋于无穷，偏差消失。理解“有偏但一致”的概念。

难点3：异策略控制的学习效率

  • 为什么只从轨迹尾部学习？因为只有那些动作符合目标策略的步骤才能用于更新。可以尝试在小型MDP中实现并观察学习速度。

学习建议

  1. 编程实践：
    • 实现首次访问MC预测解决二十一点问题（图5.2）。
    • 实现MC ES（图5.4）求解最优策略（图5.5）。
    • 比较普通和加权重要性采样在例5.5上的表现。
  2. 深入思考：为何MC ES没有严格证明却有效？这反映了强化学习理论仍有许多开放问题。
  3. 联系后续：思考如何将重要性采样与TD结合（第7章将涉及）。

掌握本章后，你已学会如何从经验中直接学习，但MC方法需要等待回合结束才能更新。下一章的时序差分（TD）方法将允许你每步学习，更加高效和灵活。

第六章：时序差分学习（Temporal-Difference Learning）详细讲解

1. 引言：从蒙特卡洛到自举

在前几章中，我们学习了两种求解强化学习问题的基本方法：

  • 动态规划（DP）：利用模型进行自举（bootstrapping）——用后继状态的估计值更新当前状态，但需要完整的环境模型。
  • 蒙特卡洛（MC）：无需模型，通过采样完整回合的回报来更新价值，但必须等到回合结束才能学习。

时序差分（Temporal-Difference, TD）学习巧妙地结合了二者的优点：

  • 像MC一样，直接从经验中学习，无需模型。
  • 像DP一样，使用后继状态的估计值（自举）进行更新，因此可以在每一步之后立即学习，无需等待回合结束。

TD学习被认为是强化学习中最核心、最创新的思想之一。

2. TD预测（TD Prediction）

2.1 TD(0)更新规则

考虑策略评估问题：估计给定策略 $\pi$ 的状态价值函数 $v_\pi$。最简单的TD方法称为 TD(0)，其更新公式为：

$$ V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]. $$
  • 目标（target）：$R_{t+1} + \gamma V(S_{t+1})$，称为TD目标。
  • 误差：$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$，称为TD误差。
  • 步长参数 $\alpha$ 控制更新幅度。

对比MC的更新（$\alpha[G_t - V(S_t)]$），TD使用当前估计的 $V(S_{t+1})$ 替代未来的真实回报 $G_t$，因此实现了自举。

2.2 备份图

图6.2展示了TD(0)的备份图：仅考虑从当前状态到下一状态的一条样本路径，与MC的完整轨迹（图5.3）和DP的全部分支（图3.4）形成对比。

2.3 例子：开车回家（Driving Home）

例6.1：每天下班开车回家，你需要估计剩余时间。离开办公室时估计30分钟，5分钟后发现下雨，重新估计总时间40分钟，等等。TD学习会在每一步根据当前预测更新前一状态的估计，而MC必须等到实际到家才知道真实时间。这个例子直观地说明了TD在线学习的优势。

3. TD与MC、DP的比较

3.1 目标来源

  • MC：目标 = 实际回报 $G_t$（无偏，但高方差）。
  • DP：目标 = 期望回报 $R_{t+1} + \gamma v_\pi(S_{t+1})$（需模型）。
  • TD：目标 = 采样 + 自举：$R_{t+1} + \gamma V(S_{t+1})$（有偏，但低方差）。

3.2 优势

  • TD无需模型，直接从经验学习。
  • TD可在线学习，每步更新，适用于长期或持续性任务。
  • TD通常比MC收敛更快，尤其在方差大的随机环境中。

3.3 随机游走例子（例6.2）

一个5状态的马尔可夫链（图6.5），左右两端为终止状态，奖励仅在右端为+1。通过比较TD(0)和MC（常数$\alpha$）的学习曲线（图6.7），发现TD在大多数$\alpha$下收敛更快，误差更低。

4. TD预测的收敛性与最优性

4.1 收敛性

对于表格型情况，TD(0)在满足随机近似条件（如$\sum\alpha=\infty,\sum\alpha^2<\infty$）下收敛到 $v_\pi$。对于线性函数近似，在on-policy分布下，TD(λ)也有收敛保证。

4.2 批处理形式与确定性等价估计

如果我们将所有经验数据作为一个批处理（batch），反复应用TD(0)直到收敛，最终得到的是确定性等价估计（certainty-equivalence estimate）：即根据数据构建的最大似然模型，然后精确求解该模型下的价值函数。而批处理MC则得到最小化训练集均方误差的估计。

例6.3：随机游走批处理实验（图6.8）显示，批处理TD优于批处理MC。

例6.4：一个更直观的例子：

  • 观察到A→B（奖励0）然后B终止（奖励0）一次，以及B直接终止（奖励1）七次。
  • MC：$V(B)=6/8=0.75$，$V(A)=0$（仅一次A→B的回报为0）。
  • TD(0)批处理：先学习模型（A到B概率1，B终止奖励1概率6/8），然后解方程得 $V(A)=V(B)=0.75$。 显然TD的解更合理，因为它利用了马尔可夫结构。

5. 同策略TD控制：Sarsa

5.1 从状态价值到动作价值

控制问题需要学习动作价值 $q_\pi(s,a)$。Sarsa算法直接将TD(0)应用于动作价值对：

$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t) \right]. $$

更新使用五元组 $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$，故得名 Sarsa。

5.2 算法流程（图6.9）

  • 初始化 $Q(s,a)$。
  • 对每个回合：
    • 初始化 $S$，用ε-贪心策略选 $A$。
    • 对每一步：
      • 执行 $A$，得 $R,S'$。
      • 用ε-贪心策略从 $S'$ 选 $A'$。
      • 更新 $Q(S,A)$。
      • $S \leftarrow S', A \leftarrow A'$。

5.3 收敛性

在合理条件下（所有状态-动作对被无限次访问，策略逐渐变为贪心），Sarsa收敛到最优策略。

5.4 例子：风车世界（Windy Gridworld）

例6.5：一个网格世界，中间区域有向上吹的风（图6.10）。动作有上下左右，但风会使实际位置偏移。用Sarsa学习，结果（图6.11）显示经过8000步后策略已接近最优（ε=0.1导致平均步数比最优多2步）。注意MC在此无法使用，因为可能产生永不终止的循环。

6. 异策略TD控制：Q-learning

6.1 Q-learning更新

Q-learning是异策略TD控制的最重要算法，其更新公式：

$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a} Q(S_{t+1},a) - Q(S_t,A_t) \right]. $$

关键点：目标中使用了 $\max_a Q(S_{t+1},a)$，这直接逼近最优动作价值 $q_*$，而与当前行为策略无关。

6.2 特点

  • 异策略：行为策略可以是任意探索性策略（如ε-贪心），而目标策略是贪心策略。
  • 收敛性：在满足一定条件下（所有状态-动作对无限次更新，步长适当），Q-learning以概率1收敛到 $q_*$。
  • 备份图：图6.14展示了Q-learning的备份，从状态-动作节点出发，对下一状态的所有动作取最大值。

6.3 例子：悬崖行走（Cliff Walking）

图6.13：一个网格世界，左下为起点，右下为终点，中间是悬崖（掉入得-100并回到起点）。用Q-learning和Sarsa比较。Sarsa由于ε-贪心探索，会尽量远离悬崖（保守），而Q-learning学习到最优策略但可能因探索而偶尔掉下悬崖。结果（图6.13）显示Sarsa在训练中获得更高累积奖励，而Q-learning最终策略更优但训练中风险大。

7. 特殊情况：后状态（Afterstates）

7.1 动机

在某些问题中，动作的结果是确定性的、已知的，但后续状态未知（如游戏中的走子）。此时，学习后状态价值函数比学习状态-动作对更高效。

7.2 定义

后状态（afterstate）是指执行动作后立即进入的中间状态，而该状态之后的演化仍未知。例如井字棋中，下完一步后棋盘格局（后状态）是确定的，但对手的应对未知。后状态价值函数 $f(\text{afterstate})$ 评估该后状态的长期价值。

7.3 优势

多个不同的状态-动作对可能映射到相同的后状态，从而共享学习经验，加速学习。

井字棋例子：两个不同的棋步可能导致相同的棋盘格局，因此它们的价值应相同。用后状态函数可直接共享。

8. 概念关系图

graph TD A[TD学习] --> B[预测] A --> C[控制] B --> D["TD(0)更新"] D --> E["目标: R+γV(S')"] D --> F["误差: δ"] C --> G["同策略: Sarsa"] C --> H["异策略: Q-learning"] G --> I["更新用 Q(S',A')"] H --> J["更新用 max Q(S',a)"] C --> K[后状态价值] B --> L["与MC/DP对比"] L --> M["MC: 无偏高方差"] L --> N["DP: 需模型"] L --> O["TD: 有偏低方差"]

9. 与前后的联系

  • 第2章 的多臂老虎机提供了评估性反馈的基础，TD方法将其扩展到多状态序列。
  • 第3-4章 的MDP和DP为TD提供了理论框架和自举思想。
  • 第5章 的MC提供了无需模型的学习范式，TD则将其在线化。
  • 第7章 的资格迹（eligibility traces）将TD(0)推广到TD(λ)，统一了TD和MC。
  • 第9章以后 将TD与函数近似结合，解决大规模问题。

10. 核心要点总结

  1. TD学习的核心：结合MC的采样和DP的自举，每步更新，无需模型。
  2. TD(0)预测：更新规则简单，收敛性有保证，实践中通常比MC快。
  3. 批处理最优性：批处理TD收敛到确定性等价估计，利用马尔可夫结构。
  4. Sarsa：同策略TD控制，学习动作价值，用ε-贪心保证探索。
  5. Q-learning：异策略TD控制，直接学习最优动作价值，行为策略可任意。
  6. 后状态价值：适用于确定性子步的领域，提高学习效率。
  7. 探索与利用：Sarsa和Q-learning以不同方式处理，各有适用场景。

11. 常见难点与学习建议

难点1：理解自举带来的偏差

  • 自举使TD目标有偏（除非λ=1），但方差降低。在批处理中，TD利用结构反而得到更好的估计（如例6.4）。

难点2：Sarsa与Q-learning的区别

  • Sarsa学习的是当前ε-贪心策略的价值，更新中用到下一步的实际动作 $A'$，因此策略影响更新。
  • Q-learning学习的是最优策略的价值，更新中用最大值，与 $A'$ 无关，因此是异策略。

难点3：探索与利用的权衡在控制中的体现

  • Sarsa在训练中更安全（如悬崖行走），因为探索时也会更新保守的值。
  • Q-learning更激进，可能学到最优但训练中风险高。

学习建议

  1. 编程实践：
    • 实现TD(0)预测在随机游走（例6.2）上，比较不同α的效果。
    • 实现Sarsa和Q-learning在风车世界和悬崖行走，观察学习曲线差异。
  2. 理论推导：亲手推导Q-learning更新中的最大值项如何保证异策略性。
  3. 思考后状态：尝试将井字棋问题用后状态价值函数建模，并与状态-动作对方法对比效率。

TD学习是强化学习的核心，本章奠定了几乎所有现代算法的基础。下一章将引入资格迹，将TD推广到多步回溯，进一步统一TD和MC。

第七章：n步自举（n-step Bootstrapping）详细讲解

1. 引言：统一时序差分与蒙特卡洛方法

在第六章中，我们学习了 时序差分（TD）方法（如 TD(0) 和 Sarsa），它们每步更新，自举地使用后继状态估计。我们也学习了蒙特卡洛（MC）方法，它们需要等到回合结束才更新，但使用无偏的完整回报。这两种方法处于一个谱系的两端，中间存在着许多中间方法——**n步自举（n-step bootstrapping）方法。本章将系统介绍这个谱系，并引出更强大的资格迹（eligibility traces）**技术，最终形成 TD(λ) 算法，将 TD 和 MC 统一在一个框架中。

本章核心思想：通过调整自举的深度（n步），可以在偏差（bias）和方差（variance）之间取得平衡，同时获得计算效率和学习速度的优化。

2. n步TD预测（n-step TD Prediction）

2.1 从一步到n步

回忆TD(0)的目标是 $R_{t+1} + \gamma V(S_{t+1})$，而MC的目标是完整回报 $G_t$。n步TD则介于两者之间：使用前 $n$ 步的实际奖励，然后用估计值替代剩余部分：

$$ G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V_{t+n-1}(S_{t+n}), $$

其中 $V_{t+n-1}$ 是在时刻 $t+n-1$ 时的价值估计（即第 $n$ 步时的最新估计）。当 $n=1$ 时即为TD(0)，当 $n=\infty$（或直到回合结束）时即为MC。

2.2 n步回报的性质

  • 误差缩减性质：对于任何近似价值函数 $v$，期望的 n步回报的误差不超过 $\gamma^n$ 倍的原误差： $$ \max_s \left| \mathbb{E}_\pi[G_{t:t+n} | S_t=s] - v_\pi(s) \right| \le \gamma^n \max_s |v(s)-v_\pi(s)|. $$ 这保证了n步方法的收敛性。

2.3 例子：随机游走（例7.1）

在19状态随机游走任务中，比较不同 $n$ 和步长 $\alpha$ 的性能（图7.2）。结果表明，中间值 $n$（如4-8）表现最好，说明适当自举能比纯TD(0)或纯MC更有效。

2.4 实现方式

n步方法需要等待 $n$ 步才能获得更新所需的数据，因此不能完全在线（需缓存最近 $n$ 个状态和奖励）。实际中常通过资格迹机制来近似实现。

3. 前向视图：λ-回报（λ-return）

3.1 混合多个n步回报

我们可以不局限于某个固定的 $n$，而是将多个不同 $n$ 的回报加权平均。例如，一半 2步回报加一半 4步回报。TD(λ) 采用一种特殊的加权方式：对所有 $n \ge 1$，权重为 $(1-\lambda)\lambda^{n-1}$，总和为1。这样得到的复合回报称为 λ-回报（λ-return）：

$$ G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}. $$

当 $\lambda=0$ 时，$G_t^\lambda = G_{t:t+1}$（即TD(0)）；当 $\lambda=1$ 时，$G_t^\lambda = G_t$（即MC）。如图7.3和图7.4所示，λ控制了对未来步骤的衰减速度。

3.2 λ-回报算法

λ-回报算法（forward view）在每个状态 $S_t$ 被访问后，将其价值更新为：

$$ V(S_t) \leftarrow V(S_t) + \alpha [G_t^\lambda - V(S_t)]. $$

这是理论上的理想更新，但需要知道整个未来轨迹，因此不能在线实现。图7.6（上左）显示了该算法在随机游走任务上的表现，与n步方法类似，中间λ效果最佳。

4. 后向视图：资格迹（Eligibility Traces）

4.1 机制与直觉

**后向视图（backward view）**是λ-回报的因果、在线实现方法。它引入一个额外的记忆变量——资格迹（eligibility trace） $E_t(s)$，记录每个状态被“访问”的近期程度。当TD误差 $\delta_t$ 发生时，它按比例更新所有资格迹非零的状态：

$$ \Delta V(s) = \alpha \delta_t E_t(s). $$

这样，当前TD误差会被分配给之前访问过的状态，越久远的状态获得的更新越小。

4.2 累积迹（Accumulating Trace）

标准累积迹的更新规则：

  • 所有状态的迹乘以衰减因子 $\gamma\lambda$： $$ E_t(s) = \gamma\lambda E_{t-1}(s), \quad \forall s \neq S_t. $$
  • 被访问的状态迹增加1： $$ E_t(S_t) = \gamma\lambda E_{t-1}(S_t) + 1. $$ 当 $\lambda=0$ 时，只有当前状态的迹非零，退化为TD(0)。当 $\lambda=1$ 且 $\gamma=1$ 时，迹永不衰减，相当于MC。

4.3 替换迹（Replacing Trace）与荷兰迹（Dutch Trace）

  • 替换迹：每次访问状态时，将其迹设为1而非增加1。这能防止迹过大，在部分问题中性能更好。
  • 荷兰迹：一种介于累积和替换之间的形式，定义为： $$ E_t(S_t) = (1-\alpha)\gamma\lambda E_{t-1}(S_t) + 1. $$ 当 $\alpha$ 小近似累积，$\alpha$ 大近似替换。

图7.9展示了三种迹的行为差异。

4.4 TD(λ)算法

结合上述更新，得到完整的 TD(λ) 算法（图7.7）：

  • 初始化 $V$ 和 $E=0$。
  • 对每个回合的每一步：
    • 采取动作，得奖励 $R$ 和下一状态 $S'$。
    • 计算TD误差 $\delta = R + \gamma V(S') - V(S)$。
    • 更新迹 $E$（按累积/替换/荷兰规则）。
    • 对每个状态 $s$：$V(s) \leftarrow V(s) + \alpha \delta E(s)$。

图7.6（中右、下右）显示了不同迹类型在随机游走上的表现，荷兰迹最为稳健。

5. 前向与后向视图的等价性

在离线批处理（off-line）情况下，累积迹的TD(λ) 与 λ-回报算法完全等价。在线情况下，若步长足够小，二者也近似等价。真正的在线TD(λ)（true online TD(λ)）（图7.10）使用荷兰迹和额外的修正项，实现了在线时与λ-回报的精确等价，其性能如图7.6（下左）所示。

6. 控制中的资格迹

6.1 Sarsa(λ)

将资格迹思想扩展到动作价值，得到 Sarsa(λ)（图7.12）。此时迹对应每个状态-动作对 $E(s,a)$，更新规则类似：

  • 迹更新（选择一种类型）。
  • TD误差 $\delta = R + \gamma Q(S',A') - Q(S,A)$。
  • $Q(s,a) \leftarrow Q(s,a) + \alpha \delta E(s,a)$。

优点：能一次性将奖励沿状态-动作路径传播，加速学习。例如图7.13中，一个回合获得高奖励后，Sarsa(λ) 会更新整条路径上的所有动作价值，而Sarsa(0) 只更新最后一步。

6.2 Watkins的Q(λ)

Watkins的 Q(λ) 是针对异策略Q-learning的扩展。由于Q-learning的目标是贪心策略，但行为策略可能探索，因此资格迹必须在探索性动作处截断——一旦采取非贪心动作，所有后续的迹被清零。图7.14和图7.15展示了算法细节。但这种方法效率低，因为频繁探索时迹常被截断。

6.3 离线策略资格迹

更通用的离线策略方法使用重要性采样来修正迹，避免截断。但这部分内容较为前沿，本书未深入。

7. 实现问题与计算效率

  • 在表格型情况下，理论上每个时间步需更新所有状态的迹，但实际中迹很小的状态可以忽略，只更新迹大于阈值的少数状态。
  • 使用函数近似（如线性方法）时，迹只对应参数向量，计算量通常只增加一倍左右。
  • 荷兰迹在计算上与累积迹相当，但性能更优。

8. 可变λ（Variable λ，高级话题）

λ可以随时间变化，例如根据状态的可信度调整。如果某个状态的价值估计非常准确，可以将该状态的λ设得很小，从而截断回溯。这提供了更精细的控制，但目前应用较少。

9. 概念关系图

graph TD A[自举深度] --> B[n步TD] A --> C["λ-回报（前向）"] C --> D[资格迹（后向）] D --> E[累积迹] D --> F[替换迹] D --> G[荷兰迹] E --> H["TD(λ)"] F --> H G --> H H --> I[控制方法] I --> J["Sarsa(λ)"] I --> K["Watkins Q(λ)"] J --> L[加速学习] K --> M[离线策略截断]

10. 与前后的联系

  • 第6章 介绍了一步TD方法（TD(0)、Sarsa、Q-learning），本章将其推广到多步和λ。
  • 第5章 的MC方法是 $\lambda=1$ 的特例。
  • 第4章 的DP是使用完整模型的全备份，而本章的方法是从样本中学习。
  • 第9章以后 将资格迹与函数近似结合，形成梯度TD(λ)等方法。
  • 第8章 的规划方法（如Dyna）可与本章方法结合，用资格迹从模拟经验中学习。

11. 核心要点总结

  1. n步自举：在TD和MC之间提供了平滑过渡，通过调整 $n$ 平衡偏差与方差。
  2. λ-回报：将多个n步回报加权平均，形成理论上的理想更新目标。
  3. 资格迹：实现λ-回报的因果在线机制，通过迹向量将当前TD误差分配给过去状态。
  4. 迹类型：累积迹、替换迹、荷兰迹，各有适用场景，荷兰迹通常最稳健。
  5. 等价性：离线情况下，累积迹TD(λ) 等价于 λ-回报算法；在线情况下，true online TD(λ) 实现精确等价。
  6. 控制扩展：Sarsa(λ) 可大幅加速学习；Watkins Q(λ) 引入截断以处理离线策略。
  7. 实践建议：当奖励延迟较长或非马尔可夫时，使用资格迹（λ>0）通常比单步方法效果好。但若数据可无限生成，单步方法可能计算更高效。

12. 常见难点与学习建议

难点1：前向视图与后向视图的区别

  • 前向视图：站在当前状态，向前看，计算理想目标（λ-回报）。不能在线实现。
  • 后向视图：站在当前时刻，向后看，用资格迹分配当前误差。可在线实现。 建议：先理解前向视图的直观意义，再接受后向视图作为其等价实现。

难点2：迹的衰减参数 $\gamma\lambda$

  • $\gamma$ 是折扣因子，影响未来奖励的重要性。
  • $\lambda$ 是迹衰减参数，控制自举程度。两者在迹更新中以乘积形式出现，共同决定“近期”的定义。

难点3：为什么荷兰迹更好？

  • 荷兰迹解决了累积迹可能变得过大（当状态频繁访问）的问题，同时保留了累积迹的某些优点。它在随机游走实验（图7.6）中表现最稳定。

学习建议

  1. 编程实践：
    • 实现n步TD预测在随机游走任务上，复现图7.2。
    • 实现TD(λ)（累积迹和替换迹）在相同任务上，观察图7.6。
  2. 理论推导：尝试推导离线情况下累积迹TD(λ)与λ-回报的等价性（可参考书中习题）。
  3. 思考应用：考虑一个延迟奖励的任务（如迷宫），比较Sarsa(0)和Sarsa(0.9)的学习速度差异。

资格迹是强化学习中既优雅又实用的技术，它将TD和MC统一在一个框架内，使我们可以灵活地在偏差与方差之间做选择。掌握本章后，你将能够理解许多现代强化学习算法的底层机制。下一章将进入规划与学习，探讨如何将模型与学习方法结合。

第八章：表格型方法的规划与学习（Planning and Learning with Tabular Methods）详细讲解

1. 引言：规划与学习的统一视角

在前几章中，我们学习了两种截然不同的求解强化学习问题的途径：

  • 基于模型的方法（model-based），如动态规划（DP），利用已知的环境模型（状态转移概率和期望奖励）进行规划（planning），通过模拟推演来改进策略。
  • 无模型方法（model-free），如蒙特卡洛（MC）和时序差分（TD），直接从与环境的交互经验中学习价值函数和策略，无需模型。

传统上，这两类方法被视为对立。然而，本章将揭示它们在本质上具有深刻的相似性：它们都通过备份（backup）操作来更新价值函数。区别仅在于备份所基于的经验来源——规划使用模拟经验（由模型生成），而学习使用真实经验（由环境生成）。

基于这一洞察，我们可以设计一种统一的架构，将规划、学习、行动和模型学习无缝整合在一起，使它们相互促进。这正是本章的核心内容。

2. 模型与规划的基本概念

2.1 模型（Model）

在强化学习中，模型是指智能体用来预测环境如何响应其动作的任何事物。给定一个状态和动作，模型预测下一状态和奖励。模型分为两类：

  • 分布模型（distribution model）：给出所有可能下一状态及其概率的完整描述，如DP中的 $p(s',r|s,a)$。
  • 样本模型（sample model）：根据概率分布生成一个样本的下一状态和奖励，如模拟器。

模型可以用于**模拟（simulate）**经验，即生成与真实环境类似的状态-动作-奖励序列。

2.2 规划（Planning）

规划是指任何以模型为输入、以策略为输出的计算过程。在**状态空间规划（state-space planning）**中（本书采用的方式），规划是在状态空间中搜索最优策略，价值函数是中间产物。典型代表是DP、启发式搜索等。

所有状态空间规划方法都有一个共同结构：

模型 → 模拟经验 → 备份操作 → 更新价值函数 → 改进策略

这与无模型学习方法的结构几乎相同，只是经验来源不同。

3. Dyna架构：整合规划、行动、学习

3.1 动机

在实际问题中，智能体需要同时处理三项任务：

  • 直接强化学习：从真实经验中学习价值函数和策略。
  • 模型学习：从真实经验中构建（或更新）环境模型。
  • 规划：利用模型生成模拟经验，进一步改进价值函数和策略。

这三者应协同工作：真实经验同时用于直接学习和模型学习；模型又用于规划，规划的结果影响行动；行动产生新的真实经验，如此循环。这就是 Dyna架构 的核心思想（图8.3）。

3.2 Dyna-Q算法

Dyna-Q是Dyna架构在Q-learning上的具体实现（图8.4）。算法包含以下步骤：

  1. 直接RL：用真实经验执行一步Q-learning更新。
  2. 模型学习：将刚经历的状态-动作对 $(S,A)$ 的下一个状态和奖励存入模型（假设确定性环境）。
  3. 规划：重复 $n$ 次（每次时间步内），从已见过的状态-动作对中随机采样一个，用模型给出模拟的下一状态和奖励，执行一步Q-learning更新。

参数 $n$ 控制每步真实交互后执行的规划步数。

3.3 例子：Dyna迷宫（例8.1）

一个简单的网格迷宫（图8.5），从起点S到终点G，每步奖励0（到G为+1），$\gamma=0.95$。比较不同规划步数 $n$ 的学习曲线：

  • $n=0$（无规划，纯Q-learning）：学习极慢，约25个回合达到最优。
  • $n=5$：5个回合就接近最优。
  • $n=50$：3个回合即达到最优。

图8.6展示了规划如何快速将知识从目标状态反向传播，使智能体在第二回合就学会大部分路径。

4. 模型错误时的挑战与应对

4.1 模型错误

模型可能因为环境变化或采样不足而错误。此时，基于错误模型的规划会误导智能体。问题分为两类：

  • 乐观错误（optimistic error）：模型预测比实际好。智能体尝试这些高估动作时会发现真相，从而修正模型。
  • 悲观错误（pessimistic error）：模型预测比实际差。智能体可能永远不会尝试那些被低估的动作，导致无法发现更好的策略。

4.2 例子：阻塞迷宫（例8.2）与捷径迷宫（例8.3）

  • 阻塞迷宫（图8.7）：原路径被阻塞，新路径出现。Dyna-Q能较快适应，因为模型预测变差后，探索会找到新路径。
  • 捷径迷宫（图8.8）：新捷径出现，但原路径仍可用。由于模型没有捷径，规划强化了原路径，智能体几乎不会尝试捷径方向，导致永远学不到捷径。

4.3 Dyna-Q+：鼓励探索性规划的改进

Dyna-Q+ 在Dyna-Q的基础上添加探索奖励（exploration bonus）：

  • 对每个状态-动作对，记录自上次真实尝试以来的时间步 $\tau$。
  • 在规划备份中，将奖励替换为 $R + \kappa \sqrt{\tau}$（$\kappa$ 是小常数）。这激励智能体去测试长期未试的动作，从而发现环境变化。

图8.8显示Dyna-Q+成功找到了捷径。

5. 优先级扫描（Prioritized Sweeping）

5.1 问题

Dyna的规划随机均匀地采样状态-动作对，但许多备份是无效的（例如，值还未变化的区域）。为了更高效，我们希望将计算资源集中在价值可能发生较大变化的状态-动作对及其前驱上。

5.2 算法思想

优先级扫描（prioritized sweeping）维护一个优先级队列，其中存放那些备份后价值变化较大的状态-动作对。每次从队列中取出优先级最高的进行备份，然后检查其所有可能的前驱，若前驱的价值变化超过阈值，也将其加入队列。这样，价值变化的信息从后继反向传播到前驱，传播效率极高。

5.3 算法流程（图8.9，确定性环境）

  • 执行真实一步，更新模型，计算当前 $(S,A)$ 的TD误差的绝对值 $P$。若 $P > \theta$，则将 $(S,A)$ 按优先级 $P$ 加入队列。
  • 在规划阶段，重复 $n$ 次：
    • 取出队列中优先级最高的 $(S,A)$。
    • 用模型生成 $R,S'$，执行Q-learning更新。
    • 对每个可能的前驱 $(\bar{S},\bar{A})$（即模型中从 $\bar{S},\bar{A}$ 到达 $S$ 的状态-动作对），计算其TD误差绝对值，若大于 $\theta$ 则加入队列。

5.4 例子

  • 迷宫任务（例8.4，图8.10）：优先级扫描比Dyna-Q快5-10倍，且随状态空间增大优势更明显。
  • 杆操纵任务（例8.5，图8.11）：一个具有14400个状态（部分不可达）的连续问题，优先级扫描成功找到最优路径，而Dyna-Q无法做到。

5.5 扩展到随机环境

对于随机环境，模型需维护转移计数，备份使用全备份（考虑所有可能下一状态）而非样本备份。此时，优先级仍由变化的幅度决定。

6. 全备份与样本备份的比较

6.1 定义

  • 全备份（full backup）：使用模型计算所有可能下一状态的期望值，如式(8.1)的Q-learning全备份。
  • 样本备份（sample backup）：仅使用一个样本的下一状态和奖励，如式(8.2)的Q-learning更新。

6.2 权衡

  • 全备份：无采样误差，但计算代价与分支因子 $b$ 成正比。
  • 样本备份：有采样误差，但计算代价小（$O(1)$）。多次样本备份可逐渐减小误差。

6.3 效率分析（图8.13）

假设所有 $b$ 个后继等概率，初始误差为1，后继值准确。那么：

  • 一次全备份将误差降为0。
  • $t$ 次样本备份的误差约为 $\sqrt{\frac{b-1}{b t}}$。

对于较大 $b$，少量样本备份即可将误差降到很低，而一次全备份需要 $b$ 倍的计算量。因此，在有限计算资源下，样本备份通常更优。

7. 轨迹采样（Trajectory Sampling）

7.1 问题

DP使用穷举扫描（sweeping）——依次备份所有状态。这对于大状态空间不现实，且许多状态可能从未被访问，浪费资源。我们需要更智能的备份分布。

7.2 按策略分布

一个自然的想法是：按当前策略下的访问频率分布来分配备份，即轨迹采样（trajectory sampling）——模拟遵循当前策略的轨迹，并备份轨迹中出现的状态或状态-动作对。这恰好是我们从模型中模拟经验时的自然方式。

7.3 效果比较

图8.14展示了在一个随机生成的MDP（1000或10000状态）上，按策略分布的轨迹采样与均匀扫描的比较：

  • 在短期，轨迹采样更快找到好的策略，因为它专注于与起始状态相关的区域。
  • 在长期，均匀扫描最终可能略优，因为轨迹采样会反复备份已熟练的区域。但对于大状态空间，短期优势更为显著。

8.1 基本思想

启发式搜索（如A*、Minimax）是传统AI中的规划方法。它针对当前状态，构建一棵搜索树，使用启发式价值函数评估叶节点，然后反向传播更新根节点的动作选择。这与DP中的备份本质上相同，但搜索是深度优先且高度聚焦于当前状态。

8.2 与强化学习的结合

在强化学习中，我们可以将启发式搜索视为一种规划，它利用当前的价值函数（可能是近似的）来改进当前决策。搜索树中的每一步备份都是对价值函数的临时改进，但通常不保存（除非与学习结合）。Tesauro的TD-Gammon就使用了这样的方法：在每一步，用搜索树评估当前动作，并用于选择动作，但学习仍使用TD(λ)从实际对局中更新网络。

8.3 深层备份与浅层备份

启发式搜索中的深层备份可以分解为一系列单步备份（图8.15）。因此，搜索的效果来自于将计算资源集中在当前状态的后继上，而不是使用更复杂的多步备份。这提示我们，有效利用计算资源比备份深度更重要。

本章简要提及蒙特卡洛树搜索（MCTS），它是现代游戏AI（如AlphaGo）的核心技术。MCTS结合了树搜索和蒙特卡洛采样：在搜索树中，通过重复模拟（rollout）来估计节点价值，并逐步扩展树。它本质上是轨迹采样的一种形式，且与资格迹有深层联系。但本书只作简介，未展开。

10. 概念关系图

graph TD A[规划与学习] --> B[模型] A --> C[真实经验] B --> D[模拟经验] C --> E[直接RL] C --> F[模型学习] D --> G[规划备份] G --> H["改进价值/策略"] E --> H H --> I[行动] I --> C style A fill:#f9f,stroke:#333 style H fill:#ff9,stroke:#333 subgraph Dyna架构 B C D E F G end G --> J[全备份 vs 样本备份] G --> K[优先级扫描] G --> L[轨迹采样] G --> M[启发式搜索] K --> N[反向传播] L --> O[按策略分布] M --> P[聚焦当前状态]

11. 与前后的联系

  • 第4章 的DP是规划的基础，本章将其扩展为使用样本模型和轨迹采样的形式。
  • 第5-6章 的MC和TD是直接RL的例子，本章将它们与模型结合在Dyna中。
  • 第7章 的资格迹可用于加速规划中的备份传播（如优先级扫描中利用迹的思想）。
  • 第9章以后 将函数近似与本章方法结合，实现大规模问题的规划与学习。

12. 核心要点总结

  1. 规划与学习的统一：两者都基于备份操作，区别仅在于经验来源。
  2. Dyna架构：将直接RL、模型学习、规划三者整合，用真实经验同时改善价值函数和模型，用模拟经验加速学习。
  3. 模型错误：乐观错误容易纠正，悲观错误可能导致无法发现改进，需用探索奖励（如Dyna-Q+）激励探索。
  4. 优先级扫描：通过反向传播价值变化，极大提高规划效率，尤其适合大规模问题。
  5. 全备份 vs 样本备份：样本备份在计算资源有限时通常更优，尤其当分支因子大时。
  6. 轨迹采样：按策略分布分配备份，聚焦于相关状态，比均匀扫描更高效。
  7. 启发式搜索：可视为聚焦于当前状态的深度备份，能与学习结合提升决策质量。
  8. 实践意义：当环境可模拟时，应充分利用规划；当模型可能错误时，需谨慎处理；优先级扫描和轨迹采样是提升效率的关键技术。

13. 常见难点与学习建议

难点1：理解Dyna中“规划”的本质

  • 规划不是独立的过程，而是与学习共享同一套价值函数和策略。模拟经验产生的备份与真实经验的备份完全一样，只是来源不同。这有助于理解为什么规划可以加速学习。

难点2：优先级扫描的“前驱”概念

  • 在表格型环境中，前驱是指那些经过一步动作后能到达当前状态的状态-动作对。维护这些前驱需要额外数据结构（反向列表），这在复杂环境中可能昂贵，但通常可行。

难点3：样本备份 vs 全备份的效率比较

  • 图8.13的分析基于后继值准确、初始误差为1的假设。在实际中，后继值也在变化，因此样本备份的优势可能更大。建议通过实验感受差异。

学习建议

  1. 实现Dyna-Q：在网格世界（如图8.5）上编程实现Dyna-Q，观察不同 $n$ 的效果。可进一步实现Dyna-Q+，观察其对环境变化的适应。
  2. 实现优先级扫描：在相同迷宫上实现优先级扫描（确定性），比较与Dyna-Q的收敛速度。
  3. 思考：在一个随机环境中，如何扩展优先级扫描？考虑使用全备份并维护转移概率。
  4. 阅读MCTS：了解MCTS在AlphaGo中的应用，思考它与本章轨迹采样的联系。

本章为后续大规模问题的规划与学习奠定了方法论基础。下一章将进入函数近似，将表格方法扩展到连续状态空间，开启强化学习在现代应用中的新篇章。

第九章：基于近似的同策略预测（On-policy Prediction with Approximation）详细讲解

1. 引言：从表格到函数近似

在前八章中，我们学习了各种强化学习方法，但所有方法都假设状态（或状态-动作对）空间足够小，可以用表格存储价值估计。然而，实际问题往往具有庞大的甚至连续的状态空间，不可能逐一记录每个状态的值。例如，一个机器人的传感器读数可以构成连续高维空间，棋类游戏的状态数远超存储能力。

解决这一问题的关键是泛化（generalization）：从有限的经验中学习，并能准确估计从未见过的状态的价值。这正是**函数近似（function approximation）**的目标——用一个参数化函数 $\hat{v}(s, \mathbf{w})$ 来逼近真实价值函数 $v_\pi(s)$，其中 $\mathbf{w}$ 是参数向量。

本章将同策略预测问题（估计当前策略 $\pi$ 的价值函数）与函数近似相结合，重点讨论梯度下降法及其在线性模型下的特例。我们将看到，之前学习的表格法其实是线性函数近似的一种特例。

2. 价值预测与函数近似

2.1 问题形式化

给定一个策略 $\pi$，我们希望通过经验学习来逼近 $v_\pi$。用一个参数化函数 $\hat{v}(s, \mathbf{w})$ 作为近似，其中 $\mathbf{w} \in \mathbb{R}^n$。我们的目标是找到 $\mathbf{w}$，使 $\hat{v}$ 尽可能接近真实值。

在监督学习中，通常提供一系列输入-输出对 $(s, v_\pi(s))$ 作为训练数据。在强化学习中，我们并没有直接的真实值，而是通过备份（backup）得到的目标值（如 MC 回报 $G_t$、TD 目标 $R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})$ 等）作为近似监督信号。因此，我们可以将每个备份视为一个训练样本：输入是状态 $S_t$，输出是某个目标 $U_t$（可能是随机变量）。然后利用函数近似方法更新 $\mathbf{w}$ 来最小化预测误差。

2.2 性能度量

为了衡量近似的质量，我们需要一个误差函数。常用的选择是均方根误差（RMSE），但需指定状态分布 $\mu(s)$：

$$ \overline{\text{VE}}(\mathbf{w}) = \sum_{s \in \mathcal{S}} \mu(s) \left[ v_\pi(s) - \hat{v}(s, \mathbf{w}) \right]^2. $$

分布 $\mu(s)$ 通常取为同策略分布（on-policy distribution），即按照策略 $\pi$ 与环境交互时各状态被访问的频率。这是最自然的，因为训练样本正好来自这个分布。

理想目标是找到全局最优 $\mathbf{w}^*$ 使 $\overline{\text{VE}}$ 最小，但对于非线性函数近似通常只能收敛到局部最优。

3. 梯度下降方法（Gradient-Descent Methods）

3.1 随机梯度下降（SGD）

假设在每个时间步 $t$，我们得到一个样本 $S_t$ 及其真实价值 $v_\pi(S_t)$（虽然未知，但用目标 $U_t$ 近似）。我们采用随机梯度下降更新参数：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t - \frac{1}{2} \alpha \nabla \left[ v_\pi(S_t) - \hat{v}(S_t, \mathbf{w}_t) \right]^2 = \mathbf{w}_t + \alpha \left[ v_\pi(S_t) - \hat{v}(S_t, \mathbf{w}_t) \right] \nabla \hat{v}(S_t, \mathbf{w}_t). $$

其中 $\nabla \hat{v}(S_t, \mathbf{w}_t)$ 是函数关于 $\mathbf{w}$ 的梯度。

在实际中，$v_\pi(S_t)$ 未知，我们用某个目标 $U_t$ 替代，得到：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[ U_t - \hat{v}(S_t, \mathbf{w}_t) \right] \nabla \hat{v}(S_t, \mathbf{w}_t). $$

如果 $U_t$ 是 $v_\pi(S_t)$ 的无偏估计（如 MC 回报 $G_t$），则在适当条件下（步长衰减）收敛到局部最优。

3.2 TD(λ) 的梯度下降形式

对于 TD(λ)，目标 $U_t$ 是 λ-回报 $G_t^\lambda$。但 $G_t^\lambda$ 是有偏的（因为使用了当前估计 $\hat{v}$），因此上述更新并不严格是梯度下降。然而，我们可以将其视为“半梯度”方法，在实践中仍有效。

前向视角的梯度下降 TD(λ) 更新：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[ G_t^\lambda - \hat{v}(S_t, \mathbf{w}_t) \right] \nabla \hat{v}(S_t, \mathbf{w}_t). $$

后向视角则通过资格迹实现：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \delta_t \mathbf{e}_t, $$

其中

$$ \delta_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t) - \hat{v}(S_t, \mathbf{w}_t), $$

$$ \mathbf{e}_t = \gamma \lambda \mathbf{e}_{t-1} + \nabla \hat{v}(S_t, \mathbf{w}_t). $$

完整的在线算法见图 9.1。

4. 线性方法（Linear Methods）

4.1 线性函数近似

线性函数近似是最简单、最常用的形式。每个状态 $s$ 用特征向量 $\mathbf{x}(s) = (x_1(s), x_2(s), \dots, x_n(s))^\top$ 表示，近似价值为：

$$ \hat{v}(s, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s) = \sum_{i=1}^n w_i x_i(s). $$

梯度 $\nabla \hat{v}(s, \mathbf{w}) = \mathbf{x}(s)$，因此更新简化为：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[ U_t - \hat{v}(S_t, \mathbf{w}_t) \right] \mathbf{x}(S_t). $$

线性方法有许多优点：

  • 只有一个全局最优（如果特征线性无关）。
  • 有收敛性保证（如 TD(λ) 在同策略分布下收敛到最小误差附近，误差上界为 $\frac{1-\gamma\lambda}{1-\gamma}$ 倍最小可能误差）。
  • 计算简单，易于实现。

4.2 特征构造

线性方法的关键在于选择合适的特征。特征应当捕捉状态中与长期价值相关的信息。以下是几种常用的特征构造方法。

4.2.1 粗编码（Coarse Coding）

  • 每个特征对应状态空间中的一个区域（如圆形区域），当状态落入该区域时特征值为1，否则为0。
  • 区域的形状和大小决定了泛化的方式：大的区域产生宽泛的泛化，小的区域产生精细的局部泛化（图9.2,9.3）。
  • 最终的分辨率（精细度）由特征的数量决定，而初始泛化宽度由区域大小决定（图9.4）。

4.2.2 瓦片编码（Tile Coding）

  • 一种特殊的粗编码，将状态空间划分为多个互不相交的瓦片（tiles），每个划分称为一个铺层（tiling）。多个铺层互相重叠，每个铺层中只有一个瓦片被激活。
  • 优点：计算高效，只需找出当前状态落在每个铺层的哪个瓦片，然后对这些瓦片对应的参数求和。
  • 步长 $\alpha$ 的设置很直观：若用 $m$ 个铺层，取 $\alpha = 1/m$ 可实现单次学习到目标值（但通常用更小的值，如 $\alpha = 0.1/m$）。
  • 可以通过哈希（hashing） 将大规模瓦片映射到较小的内存空间，有效利用存储（图9.5,9.6）。

4.2.3 径向基函数（Radial Basis Functions, RBF）

  • 特征值为连续值，通常为高斯函数：$x_i(s) = \exp\left( -\frac{\|s - \mathbf{c}_i\|^2}{2\sigma_i^2} \right)$。
  • 提供平滑的近似，但计算更复杂。也可调整中心 $\mathbf{c}_i$ 和宽度 $\sigma_i$（非线性学习）。

4.2.4 Kanerva编码

  • 用于高维二值状态空间，特征对应随机选择的原型状态（prototypes）。特征值为1如果当前状态与原型足够接近（按汉明距离）。
  • 优点：特征数量可独立于状态维度，仅受限于计算资源，适用于极高维问题（图9.7）。

5. 控制中的函数近似

虽然本章主题是预测，但为完整性也介绍了如何将函数近似扩展到控制。

5.1 动作价值近似

类似地，用参数化函数 $\hat{q}(s,a,\mathbf{w})$ 逼近 $q_\pi(s,a)$。更新规则为：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[ U_t - \hat{q}(S_t, A_t, \mathbf{w}_t) \right] \nabla \hat{q}(S_t, A_t, \mathbf{w}_t). $$

其中 $U_t$ 可以是 MC 回报 $G_t$、Sarsa 目标 $R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, \mathbf{w}_t)$ 等。对应的 Sarsa(λ) 算法（图9.8）和 Watkins 的 Q(λ)（图9.9）都有相应的梯度下降形式。

5.2 资格迹的处理

在函数近似中，资格迹也需针对参数向量定义。迹的更新为：

$$ \mathbf{e}_t = \gamma \lambda \mathbf{e}_{t-1} + \nabla \hat{q}(S_t, A_t, \mathbf{w}_t). $$

对于线性近似，梯度就是特征向量。

5.3 示例：山地车（Mountain-Car）

例9.2：山地车任务（图9.10）是一个经典的连续控制问题，智能体需控制一辆动力不足的车爬上山坡。用瓦片编码和 Sarsa(λ) 成功学习到最优策略。实验表明，中间 λ 值（如0.9）性能最好（图9.11），且替换迹优于累积迹。优化初始值（乐观初始）保证了探索（ε=0 时仍能探索）。

6. 自举（Bootstrapping）的争议

本章最后讨论了自举在函数近似中的角色。非自举方法（如 MC）在理论上更可靠（无偏、收敛性好），但在实践中，自举方法（TD 类）往往学得更快，且能获得更好的策略（即使价值估计的 RMSE 可能更大）。图9.12总结了一系列实验，表明中间 λ 值（部分自举）通常表现最佳。这提示我们：自举引入的偏差可能是值得的，因为它加速了学习，并可能引导参数朝向更有用的方向。

7. 概念关系图

graph TD A[函数近似必要性] --> B[价值预测 as 监督学习] B --> C[梯度下降方法] C --> D[线性方法] C --> E[非线性方法（如神经网络）] D --> F[特征表示] F --> G[粗编码] F --> H[瓦片编码] F --> I[RBF] F --> J[Kanerva编码] D --> K[收敛性保证] E --> L[局部最优] B --> M[控制扩展] M --> N[动作价值近似] N --> O["Sarsa(λ)"] N --> P["Q(λ)"] K --> Q[自举 vs 非自举] Q --> R[实践性能]

8. 与前后的联系

  • 第2章 的梯度老虎机算法可视为单状态下的梯度下降。
  • 第6-7章 的表格型 TD(λ) 是本章线性方法的特例（每个状态一个特征）。
  • 第10章 将深入讨论离线策略下的函数近似，面临更大的挑战（如发散风险）。
  • 第11章 的策略梯度方法将参数化策略本身，可与价值函数结合。

9. 核心要点总结

  1. 函数近似的必要性：解决大规模、连续状态空间的泛化问题。
  2. 梯度下降框架：将每个备份视为监督样本，更新参数以减小预测误差。
  3. 线性方法：最简单且理论最完善，关键在于特征工程。
  4. 特征构造方法：粗编码、瓦片编码、RBF、Kanerva编码，各有适用场景。
  5. 同策略收敛性：线性 TD(λ) 在同策略分布下收敛到最小误差附近。
  6. 控制扩展：Sarsa(λ) 等算法可自然推广到函数近似。
  7. 自举的价值：尽管有偏，但实践中常优于非自举方法。

10. 常见难点与学习建议

难点1：理解“半梯度”与真正梯度的区别

  • 当目标 $U_t$ 依赖于当前参数时，更新不是真正的梯度下降（如 TD 目标）。但实践中仍有效，且有理论保证（如线性情况下收敛到有界解）。

难点2：特征工程的重要性

  • 线性方法的性能完全取决于特征的选择。理解各种特征构造方法如何影响泛化和分辨率是应用的关键。

难点3：资格迹在函数近似中的形式

  • 迹是参数向量的迹，而非状态的迹。更新时每个参数都有自己的迹，这在线性近似中就是特征向量。

学习建议

  1. 编程实践：
    • 实现线性 TD(0) 在随机游走任务上，使用随机特征（如多项式）或瓦片编码。
    • 在山地车任务上实现 Sarsa(λ) 与瓦片编码，复现图9.11的效果。
  2. 理论推导：尝试推导线性 TD(0) 的收敛性（可参考相关文献）。
  3. 思考：为什么 λ=1（MC）在短期学习中不如 λ=0.9？这反映了偏差-方差权衡的复杂现实。

本章为处理大规模问题打开了大门。下一章将进入更复杂的离线策略情况，其中函数近似可能导致发散，需要更精巧的算法。

第十章：基于近似的同策略控制（On-policy Control with Approximation）详细讲解

1. 引言：从预测到控制

在第九章中，我们学习了如何用函数近似来预测给定策略的价值函数。现在，我们自然地将这一技术扩展到控制问题——即寻找最优策略。本章将专注于同策略（on-policy）方法，其中用于生成数据的策略也是我们正在学习和改进的策略。典型代表是Sarsa算法，将其与函数近似结合，就得到了**半梯度Sarsa（semi-gradient Sarsa）**及其带资格迹的版本 Sarsa(λ)。

本章将讨论如何将第九章的预测方法适配到控制，如何处理连续动作空间，以及在平均奖励设置下的扩展。

2. 半梯度Sarsa（Semi-gradient Sarsa）

2.1 从表格到近似

在表格型Sarsa中，我们维护一个二维表 $Q(s,a)$，更新规则为：

$$ Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t) \right]. $$

当使用函数近似时，我们用参数化函数 $\hat{q}(s,a,\mathbf{w})$ 逼近 $q_*(s,a)$，并通过梯度下降更新参数：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[ R_{t+1} + \gamma \hat{q}(S_{t+1},A_{t+1},\mathbf{w}_t) - \hat{q}(S_t,A_t,\mathbf{w}_t) \right] \nabla \hat{q}(S_t,A_t,\mathbf{w}_t). $$

由于目标 $R_{t+1} + \gamma \hat{q}(S_{t+1},A_{t+1},\mathbf{w}_t)$ 依赖于当前参数，这并非真正的梯度下降（而是“半梯度”），但在线性近似下仍能收敛到有界解。

2.2 动作选择与探索

在同策略方法中，动作选择策略通常为 $\varepsilon$-贪心。因此，我们需要根据当前 $\hat{q}$ 的值选出贪心动作，但为了探索，实际执行的动作可能是随机的。注意，更新中使用的 $A_{t+1}$ 就是实际执行的下一个动作（由 $\varepsilon$-贪心产生）。

2.3 收敛性

对于线性函数近似，在半梯度Sarsa中，只要状态-动作特征满足一定条件，且步长适当衰减，算法可以收敛到一个有界区域。但不像表格情况那样保证收敛到最优，而是收敛到某个近似最优解附近。

3. 资格迹与Sarsa(λ)

3.1 迹的定义

与预测类似，我们可以为每个参数引入资格迹，从而得到 Sarsa(λ)。更新规则为：

$$ \delta_t = R_{t+1} + \gamma \hat{q}(S_{t+1},A_{t+1},\mathbf{w}_t) - \hat{q}(S_t,A_t,\mathbf{w}_t), $$

$$ \mathbf{e}_t = \gamma \lambda \mathbf{e}_{t-1} + \nabla \hat{q}(S_t,A_t,\mathbf{w}_t), $$

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \delta_t \mathbf{e}_t. $$

对于线性近似，梯度就是特征向量 $\mathbf{x}(s,a)$，因此迹是特征向量的指数衰减和。

3.2 迹的类型

在函数近似中，我们同样可以使用累积迹、替换迹或荷兰迹。替换迹在每次访问状态-动作对时将其迹重置为1，而非累积加1。荷兰迹则介于两者之间。实验表明，替换迹和荷兰迹在控制问题中通常更稳定。

3.3 示例：山地车（Mountain Car）

第九章中已经展示了Sarsa(λ)在山地车任务上的应用。图9.10和图9.11显示了不同λ值对学习速度的影响，中间λ值（如0.9）表现最佳，而λ=1（纯MC）则较慢。这再次说明自举（λ<1）在函数近似中的优势。

4. 连续动作的处理

在许多实际任务中，动作空间是连续的（例如，施加的力、角度等）。表格型方法无法直接处理，但函数近似可以。一种简单方法是离散化连续动作，然后用标准方法。但更优雅的方法是将动作也作为函数近似的输入，输出为动作价值。但此时选择贪心动作需要求解优化问题：

$$ a^* = \arg\max_{a \in \mathcal{A}} \hat{q}(s,a,\mathbf{w}). $$

这通常很难解析求解，可以采用以下策略：

  • 采样：随机采样几个动作，取最大值。
  • 梯度上升：用梯度上升在动作空间中搜索（需$\hat{q}$关于$a$可微）。
  • 策略参数化：直接学习一个策略（见第11章）。

本章可能介绍一种简单方法：使用归一化高斯网络（Normalized Gaussian Networks）或核方法，但通常只作简介。

5. 平均奖励设置（Average Reward Setting）

5.1 问题背景

对于持续进行的任务（continuing tasks），折扣因子$\gamma$有时不自然（如长期平均性能）。平均奖励设置中，目标是最大化平均每步奖励：

$$ \bar{r}(\pi) = \lim_{h \to \infty} \frac{1}{h} \sum_{t=1}^{h} \mathbb{E}[R_t | \pi]. $$

此时，价值函数定义为相对价值（differential value），满足贝尔曼方程：

$$ v_\pi(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \left[ r - \bar{r}(\pi) + v_\pi(s') \right]. $$

动作价值类似：

$$ q_\pi(s,a) = \sum_{s',r} p(s',r|s,a) \left[ r - \bar{r}(\pi) + \sum_{a'} \pi(a'|s') q_\pi(s',a') \right]. $$

5.2 半梯度Sarsa的平均奖励形式

在平均奖励设置下，TD误差变为：

$$ \delta_t = R_{t+1} - \bar{R}_t + \hat{q}(S_{t+1},A_{t+1},\mathbf{w}_t) - \hat{q}(S_t,A_t,\mathbf{w}_t), $$

其中$\bar{R}_t$是当前对平均奖励的估计。然后更新参数和平均奖励：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \delta_t \nabla \hat{q}(S_t,A_t,\mathbf{w}_t), $$

$$ \bar{R}_{t+1} = \bar{R}_t + \beta \delta_t, $$

其中$\beta$是另一个步长。

这种算法称为差分Sarsa（Differential Sarsa），它不需要折扣，适用于持续任务。

6. 收敛性讨论

  • 线性函数近似：在同策略控制中，半梯度Sarsa可以收敛到某个有界解，但并不保证收敛到最优策略，甚至可能发散（但在实践中很少见）。
  • 资格迹：引入资格迹通常加速收敛，但可能增加发散风险，需谨慎选择迹类型。
  • 非线性近似：理论上更复杂，但实践中常用神经网络（如DQN）并取得巨大成功，但那是第11章内容（或第16章）。

7. 概念关系图

graph TD A[同策略控制] --> B[半梯度Sarsa] B --> C["动作选择: ε-贪心"] B --> D["更新: w += α δ ∇q"] B --> E[资格迹扩展] E --> F["Sarsa(λ)"] F --> G["迹更新 e = γλ e + ∇q"] A --> H[连续动作] H --> I["离散化/优化"] A --> J[平均奖励设置] J --> K[差分Sarsa] K --> L["TD误差: δ = R - R̄ + q' - q"] L --> M[更新平均奖励]

8. 与前后的联系

  • 第9章 奠定了函数近似预测的基础，本章将其扩展到控制。
  • 第6章 的表格Sarsa是本章的特例（每个状态-动作对用一个特征）。
  • 第11章 的策略梯度方法直接学习策略，可与价值函数结合（Actor-Critic）。
  • 第16章（第二版）将讨论深度强化学习，即使用深度神经网络作为函数近似，本章为其提供了理论铺垫。

9. 核心要点总结

  1. 半梯度Sarsa：将表格Sarsa的更新转化为参数更新，使用梯度下降，但目标依赖于当前参数，因此是半梯度。
  2. 资格迹：通过迹向量将TD误差传播到历史参数，加速学习。
  3. 连续动作：需要额外技术处理，如动作离散化或优化方法。
  4. 平均奖励：适用于持续任务，用差分价值代替折扣价值，需同时估计平均奖励。
  5. 收敛性：线性近似下可收敛到有界解，但不保证最优；非线性近似更复杂。
  6. 实践建议：通常选择λ=0.9附近，用替换迹，步长α需小心调整；连续任务用差分方法。

10. 常见难点与学习建议

难点1：半梯度的含义

  • 真正的梯度下降要求目标独立于参数。但Sarsa目标使用了当前参数，因此更新不是任何函数的梯度。但实践中仍有效，且有理论支持（如投影操作）。

难点2：资格迹的实现细节

  • 在线性近似中，迹就是特征向量的衰减和。需要存储每个参数的迹，但通常只需存储非零特征对应的迹。

难点3：平均奖励的收敛

  • 平均奖励估计$\bar{R}$需与价值学习同步，两个步长需适当选取。理论上要求$\alpha$和$\beta$都趋近于0且$\beta$衰减更慢。

学习建议

  1. 编程实践：
    • 实现线性半梯度Sarsa在山地车任务上，并与表格方法比较。
    • 实现Sarsa(λ)（累积迹和替换迹）并观察λ的影响。
    • 在连续动作任务（如Pendulum）中尝试离散化方法。
  2. 理论推导：尝试推导线性半梯度Sarsa的收敛性（可参考Bertsekas & Tsitsiklis）。
  3. 思考：为什么在函数近似中，同策略比异策略更容易收敛？这为第11章做铺垫。

本章是同策略控制与函数近似的关键章节，为后续深度强化学习算法奠定了基础。下一章将介绍策略梯度方法，直接从策略参数化学习。

第十一章：基于近似的异策略方法（Off-policy Methods with Approximation）详细讲解

1. 引言：异策略学习的挑战

在前几章中，我们学习了**同策略（on-policy）方法，即用于生成数据的策略与正在学习和改进的策略相同。而在许多情况下，我们希望能够从另一个不同的行为策略（behavior policy）收集的数据中学习目标策略，这就是异策略（off-policy）**学习。异策略学习有重要应用，例如：

  • 从旧数据（经验回放）中学习。
  • 从人类演示或其他智能体的轨迹中学习。
  • 在学习最优策略的同时保持探索性行为策略。

当结合函数近似时，异策略学习面临巨大的挑战。简单地将同策略的半梯度方法（如Sarsa）与重要性采样结合往往导致发散。本章将深入探讨这些挑战，并介绍几种能够保证稳定性的算法，如梯度TD方法、TDC和强调性TD（Emphatic TD）。

2. 异策略学习的基础概念

2.1 行为策略与目标策略

  • 行为策略（behavior policy） $\mu(a|s)$：实际与环境交互并生成数据的策略。
  • 目标策略（target policy） $\pi(a|s)$：我们想要评估或优化的策略。

异策略学习的目标是利用从 $\mu$ 收集的样本，估计或优化 $\pi$ 的价值函数。

2.2 重要性采样回顾

在第5章中，我们已经见过重要性采样在蒙特卡洛方法中的应用。对于时序差分学习，我们需要每步重要性采样比率：

$$ \rho_t = \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}. $$

这个比率用于校正每一步的采样偏差。

2.3 异策略TD更新

将重要性采样直接应用到TD(0)中，得到异策略TD(0)预测：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \rho_t \delta_t \nabla \hat{v}(S_t, \mathbf{w}_t), $$

其中 $\delta_t = R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w}_t) - \hat{v}(S_t, \mathbf{w}_t)$。

问题：当使用函数近似时，这个简单的更新可能发散，即使在线性近似下也是如此。这是因为目标中包含了当前参数 $\mathbf{w}_t$，导致更新不再是任何函数的梯度，且方差可能很大。

3. 发散风险：致命三要素（The Deadly Triad）

Sutton和Barto指出，导致异策略学习发散需要三个要素同时出现：

  1. 函数近似：价值函数用参数化模型近似，而非表格。
  2. 自举（bootstrapping）：更新中使用了后继状态的估计值（如TD目标）。
  3. 异策略训练：数据分布与目标策略的分布不一致。

当这三者同时存在时，半梯度方法可能不稳定。经典的例子是Baird的反例（Baird’s counterexample）。

3.1 Baird的反例（例11.1）

Baird设计了一个简单的七状态MDP，使用线性函数近似和异策略训练（行为策略是均匀随机，目标策略是确定性的）。半梯度DP和TD(0)更新都导致参数发散到无穷大。这个例子有力地说明了异策略+自举+近似的危险性。

4. 梯度TD方法（Gradient-TD Methods）

为了克服发散问题，研究者提出了梯度TD方法，它们通过将更新构造为某个目标函数的真实梯度来保证收敛性。

4.1 目标函数：均方投影贝尔曼误差（MSPBE）

梯度TD方法旨在最小化均方投影贝尔曼误差（Mean Squared Projected Bellman Error, MSPBE）。对于线性近似 $\hat{v}(s, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$，MSPBE定义为：

$$ \text{MSPBE}(\mathbf{w}) = \| \hat{v} - \Pi T_\pi \hat{v} \|_D^2, $$

其中 $T_\pi$ 是贝尔曼算子，$\Pi$ 是到近似空间的投影，$\|\cdot\|_D$ 是状态分布 $D$（由行为策略 $\mu$ 产生的稳态分布）下的加权范数。

4.2 GTD（Gradient-TD）算法

GTD算法通过引入辅助变量来估计梯度，避免了直接使用半梯度。以预测为例，GTD的更新规则为：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left[ \rho_t \delta_t \mathbf{x}_t - \gamma \rho_t \mathbf{x}_{t+1} (\mathbf{v}_t^\top \mathbf{x}_t) \right], $$

$$ \mathbf{v}_{t+1} = \mathbf{v}_t + \beta \left[ \delta_t \mathbf{x}_t - \mathbf{v}_t \right], $$

其中 $\mathbf{v}_t$ 是辅助变量，$\beta$ 是另一个步长。这个更新是收敛的（在线性近似下），因为它实际上是随机梯度下降在MSPBE上的实现。

4.3 TDC（TD with Gradient Correction）

TDC是GTD的一个简化版本，它只使用一个辅助变量，更新更为简洁。对于线性近似：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \rho_t \delta_t \mathbf{x}_t - \alpha \gamma \rho_t \mathbf{x}_{t+1} (\mathbf{v}_t^\top \mathbf{x}_t), $$

$$ \mathbf{v}_{t+1} = \mathbf{v}_t + \beta (\delta_t \mathbf{x}_t - \mathbf{v}_t). $$

TDC在理论和实践中都表现良好，且已证明在异策略线性近似下收敛到MSPBE的最优解。

5. 强调性TD（Emphatic TD）

另一种解决发散问题的方法是强调性TD（Emphatic TD），它通过引入**强调因子（emphasis）**来调整更新的权重，使得更新方向与目标策略的分布更一致。

5.1 强调因子

强调因子 $M_t$ 是一个正标量，它衡量当前状态在目标策略下的重要性。递归定义：

$$ M_t = \gamma \rho_{t-1} M_{t-1} + 1, $$

其中 $\rho_t$ 是重要性采样比率。然后更新为：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha M_t \rho_t \delta_t \nabla \hat{v}(S_t, \mathbf{w}_t). $$

这个简单的修改可以显著提高稳定性。强调性TD已被证明在线性近似下收敛到正确的解，且在某些情况下比梯度TD更简单。

6. 异策略控制方法

将上述预测方法扩展到控制（学习最优动作价值）是自然的。例如：

  • 异策略Sarsa：使用重要性采样和梯度TD更新动作价值。
  • GQ(λ)：梯度TD版本的Q-learning。
  • 强调性Q-learning：结合强调因子。

然而，控制问题中目标策略通常为贪心策略，这导致重要性采样比率 $\rho_t$ 可能为零，从而截断迹。这带来了额外的复杂性，目前仍是活跃研究领域。

7. 概念关系图

graph TD A[异策略学习] --> B[挑战：发散] B --> C[致命三要素] C --> D[函数近似] C --> E[自举] C --> F[异策略分布] B --> G[解决方案] G --> H[梯度TD方法] G --> I[强调性TD] H --> J[GTD] H --> K[TDC] H --> L[目标函数：MSPBE] I --> M[强调因子] G --> N[扩展到控制] N --> O["GQ/异策略Sarsa"]

8. 与前后的联系

  • 第5章 引入了重要性采样用于蒙特卡洛异策略学习，本章将其扩展到TD。
  • 第6章 的Q-learning是异策略表格方法，本章讨论其在函数近似下的不稳定问题及解决方案。
  • 第9章 介绍了同策略预测的函数近似，本章研究异策略下的类似问题。
  • 第10章 的同策略控制（Sarsa）相对稳定，而异策略控制更困难。
  • 第12-13章 将讨论这些算法在神经科学和心理学中的可能对应，如多巴胺系统与TD误差的关系。

9. 核心要点总结

  1. 异策略学习+函数近似+自举 是导致发散的致命三要素。
  2. Baird的反例 直观展示了线性近似下异策略TD可能发散。
  3. 梯度TD方法 通过最小化MSPBE获得稳定更新，如GTD和TDC。
  4. 强调性TD 通过强调因子调整权重，也是一种有效解决方案。
  5. 重要性采样 在异策略学习中必不可少，但可能增加方差，需谨慎使用。
  6. 理论保证：梯度TD和强调性TD在线性近似下可证明收敛。
  7. 控制扩展：仍存在挑战，如截断迹和收敛性。

10. 常见难点与学习建议

难点1：理解MSPBE

  • MSPBE是投影贝尔曼误差的加权范数，它衡量了近似价值函数与贝尔曼方程投影之间的差距。理解它需要扎实的线性代数基础，建议先复习投影算子和范数。

难点2：梯度TD的推导

  • GTD的更新看似复杂，其实是将梯度下降应用于MSPBE。推导过程涉及目标函数对参数的梯度，并引入辅助变量估计期望值。建议阅读原始论文（如Sutton et al., 2009）并手动推导简单情况。

难点3：强调因子的直观理解

  • 强调因子可以看作对状态在目标策略下的重要性的度量。它通过递归方式累积，使得更新更关注那些在目标策略下频繁出现的状态。

学习建议

  1. 动手实现：在Baird的反例上实现半梯度TD、GTD和强调性TD，观察发散与收敛。
  2. 理论推导：尝试推导线性情况下GTD的更新如何最小化MSPBE。
  3. 阅读文献：深入阅读Sutton等人的原始论文《Fast Gradient-Descent Methods for Temporal-Difference Learning》和《Emphatic Temporal-Difference Learning》。
  4. 联系实际：思考深度强化学习中的经验回放（如DQN）如何规避发散问题——它们通常使用目标网络（减少自举）和同策略采样（实际是行为策略近于目标策略），但仍面临挑战。

异策略学习与函数近似的结合是强化学习理论中最深刻的主题之一。掌握本章内容，你将理解为何许多深度强化学习算法需要复杂的技巧（如目标网络、经验回放优先级）来保持稳定，并为更高级的研究打下基础。

第十二章：资格迹（Eligibility Traces）详细讲解

1. 引言：统一时序差分与蒙特卡洛

在前面的章节中，我们学习了时序差分（TD）方法（如TD(0)）和蒙特卡洛（MC）方法。TD(0)每步更新，自举地使用后继状态估计；MC则需等待回合结束，用完整回报更新。两者各有优缺点：TD(0)方差小但有偏，MC无偏但方差大。在 n步自举（n-step bootstrapping） 方法（第7章）中，我们看到了一个平滑的谱系，其中n步回报提供了介于两者之间的折中。然而，n步方法需要等待n步才能更新，且对于每个n需要不同的算法。

资格迹（Eligibility Traces） 是一种优雅的机制，它可以实现在线、增量式地混合多步回报，从而将TD和MC统一在一个框架中。通过一个参数 $\lambda$，资格迹可以让我们在任何时刻用当前TD误差更新所有过去相关的状态，且其效果等价于混合了不同n步回报的 $\lambda$-回报。因此，资格迹是强化学习中实现高效学习的关键技术之一。

本章将深入探讨资格迹的理论基础、前向视图（λ-return）和后向视图（资格迹）的等价性，以及如何在函数近似和控制中使用资格迹，包括处理离线策略的高级主题。

2. λ-回报：前向视图（The λ-return）

2.1 从n步回报到λ-回报

n步回报定义为：

$$ G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n \hat{v}(S_{t+n}, \mathbf{w}_{t+n-1}), $$

其中 $\hat{v}$ 是当前价值估计。当 $n=1$ 时即为TD(0)目标，当 $n \to \infty$（直至回合结束）时即为MC回报。

λ-回报 是将所有n步回报加权平均得到的复合回报：

$$ G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}, $$

其中 $0 \le \lambda \le 1$。当 $\lambda=0$ 时，只有 $n=1$ 项有效，退化为TD(0)；当 $\lambda=1$ 时，权重全部集中到 $n=\infty$，即MC回报。因此，λ控制着自举的程度。

2.2 前向视图算法

λ-回报算法（off-line版本）在每个回合结束后，对每个状态 $S_t$ 执行更新：

$$ \mathbf{w} \leftarrow \mathbf{w} + \alpha \left[ G_t^\lambda - \hat{v}(S_t, \mathbf{w}) \right] \nabla \hat{v}(S_t, \mathbf{w}). $$

这个更新需要知道整个未来的轨迹，因此不能在线实现，但它是理论上的理想目标。

2.3 误差缩减性质

与n步回报类似，λ-回报也具有误差缩减性质：使用近似价值函数 $v$ 计算的λ-回报的期望误差不超过原误差的某个倍数。这保证了基于λ-回报的迭代算法最终收敛到真实价值函数。

3. 资格迹：后向视图（Eligibility Traces）

3.1 核心思想

后向视图 提供了一种在线的、因果的机制来近似λ-回报。它引入一个额外的记忆变量——资格迹（eligibility trace） $e_t(s)$（对于表格型）或 $\mathbf{e}_t$（对于函数近似），记录每个参数（或状态）最近被“访问”的程度。当TD误差 $\delta_t$ 发生时，它被按比例分配给所有之前访问过的状态，分配比例由迹决定。

3.2 表格型资格迹

对于表格型状态价值函数，资格迹定义为：

  • 所有状态的迹每步衰减 $\gamma\lambda$： $$ e_t(s) = \gamma\lambda e_{t-1}(s), \quad \forall s \neq S_t. $$
  • 被访问的状态的迹增加1（或重置为1，取决于迹的类型）： $$ e_t(S_t) = \gamma\lambda e_{t-1}(S_t) + 1 \quad \text{(累积迹)}. $$ 然后，价值更新为： $$ V(s) \leftarrow V(s) + \alpha \delta_t e_t(s), \quad \forall s. $$ 其中 $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$。

3.3 三种常见的迹类型

  • 累积迹（accumulating trace）：如上所述，每次访问增加1。它可能导致迹过大，尤其在频繁访问时。
  • 替换迹（replacing trace）：访问状态时，将其迹设为1（而非增加）。这避免了迹无限增长，通常表现更好。
  • 荷兰迹（dutch trace）：一种介于累积和替换之间的形式，定义为： $$ e_t(S_t) = (1-\alpha)\gamma\lambda e_{t-1}(S_t) + 1, $$ 其中 $\alpha$ 是步长。当 $\alpha$ 小时近似累积，$\alpha$ 大时近似替换。荷兰迹在理论分析中具有优势。

图12.1（假设书中图）展示了三种迹在多次访问同一状态时的不同行为。

3.4 函数近似下的资格迹

对于线性函数近似 $\hat{v}(s,\mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$，资格迹是参数向量 $\mathbf{e}_t$，更新为：

$$ \mathbf{e}_t = \gamma\lambda \mathbf{e}_{t-1} + \nabla \hat{v}(S_t, \mathbf{w}_t) = \gamma\lambda \mathbf{e}_{t-1} + \mathbf{x}(S_t). $$

然后参数更新为：

$$ \mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \delta_t \mathbf{e}_t. $$

这正是 TD(λ) 算法（图12.2）。

4. 前向与后向视图的等价性

在离线批处理情况下，累积迹的TD(λ)与λ-回报算法完全等价。这意味着后向视图确实是在线实现λ-回报的一种方式。在线情况下，若步长足够小，两者也近似等价。然而，为了达到精确等价，需要更精心的设计。

真正的在线TD(λ)（True Online TD(λ)） 使用荷兰迹和一个修正项，实现在线情况下与λ-回报的精确等价（图12.3）。这消除了近似误差，使算法在每一步都准确对应λ-回报更新。

5. 控制中的资格迹：Sarsa(λ)

将资格迹用于控制，自然得到 Sarsa(λ) 算法（图12.4）。对于动作价值函数 $\hat{q}(s,a,\mathbf{w})$，迹更新为：

$$ \mathbf{e}_t = \gamma\lambda \mathbf{e}_{t-1} + \nabla \hat{q}(S_t,A_t,\mathbf{w}_t), $$

TD误差为：

$$ \delta_t = R_{t+1} + \gamma \hat{q}(S_{t+1},A_{t+1},\mathbf{w}_t) - \hat{q}(S_t,A_t,\mathbf{w}_t). $$

然后 $\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \delta_t \mathbf{e}_t$。

Sarsa(λ) 可以显著加速学习，因为它能将一次获得的奖励快速传播到一系列先前动作上（图12.5）。

6. 离线策略资格迹（Off-policy Traces）

当行为策略与目标策略不同时，需要引入重要性采样来修正迹。一个简单的方法是将重要性采样比率 $\rho_t = \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}$ 乘入迹更新：

$$ \mathbf{e}_t = \gamma\lambda \rho_t \mathbf{e}_{t-1} + \nabla \hat{q}(S_t,A_t,\mathbf{w}_t). $$

但这种做法可能导致方差极大。更高级的方法使用**控制变量（control variates）**来减小方差，如 Tree-Backup(λ) 和 Q(λ) 的变种。

Watkins的Q(λ) 是一种早期的离线策略迹方法：它只在当前动作是贪心动作时继续迹，一旦出现探索动作，迹就被截断（置零）。这虽然保证了目标策略的正确性，但频繁探索时学习效率低。

Tree-Backup(λ) 使用期望值而非最大值，且不需要重要性采样，适用于任意目标策略。

7. 稳定的离线策略方法

结合梯度TD方法（第11章）与资格迹，可以得到稳定的离线策略算法，如 GQ(λ)。这些算法旨在最小化某种误差（如MSPBE），并通过迹来加速收敛。虽然数学复杂，但为离线策略学习提供了理论保障。

8. 实现问题

  • 在表格型方法中，理论上每个时间步需要更新所有状态的迹，但实际中迹很小的状态可以忽略，只需维护一个非零迹的列表。
  • 在函数近似中，迹的存储和计算通常只比无迹方法多一倍。
  • 荷兰迹在计算上与累积迹相当，但性能更优，推荐使用。

9. 概念关系图

graph TD A[资格迹] --> B["前向视图: λ-return"] A --> C["后向视图: 迹更新"] B --> D[混合n步回报] C --> E["累积迹/替换迹/荷兰迹"] C --> F[函数近似下的迹] F --> G["TD(λ)"] G --> H["控制扩展: Sarsa(λ)"] H --> I[加速学习] A --> J[离线策略] J --> K[重要性采样修正] J --> L["Watkins Q(λ)"] J --> M["Tree-Backup(λ)"] J --> N["GQ(λ)"]

10. 与前后的联系

  • 第7章（n步自举） 为资格迹提供了基础，λ-回报正是n步回报的加权平均。
  • 第6章（TD学习） 是λ=0的特例，第5章（MC）是λ=1的特例。
  • 第9-10章（函数近似控制） 将资格迹扩展到连续状态和控制问题。
  • 第11章（离线策略方法） 与资格迹结合，产生更高级的稳定算法。
  • 第13章（策略梯度） 也可以与资格迹结合，形成带迹的策略梯度方法。

11. 核心要点总结

  1. 资格迹的作用：在TD和MC之间连续插值，提供偏差-方差权衡，加速学习。
  2. 前向视图（λ-return）：理论上的理想更新，但不可在线实现。
  3. 后向视图（资格迹）：在线实现λ-回报的机制，通过迹将当前TD误差分配给过去状态。
  4. 迹类型：累积迹、替换迹、荷兰迹，其中荷兰迹在理论和实践中表现优异。
  5. True Online TD(λ)：在线精确等价于λ-回报的算法。
  6. Sarsa(λ)：将资格迹用于同策略控制，显著提升学习速度。
  7. 离线策略迹：面临更大挑战，需结合重要性采样或Tree-Backup等技术。
  8. 实现技巧：利用稀疏迹优化计算。

12. 常见难点与学习建议

难点1：理解前向视图与后向视图的等价性

  • 建议：先接受λ-回报作为理想目标，然后通过推导（或阅读书中附录）理解为何累积迹的更新累积起来等效于λ-回报。动手在小规模随机游走任务上比较两种算法，观察它们的等价性。

难点2：迹类型的选择

  • 实验表明，荷兰迹通常最稳健。替换迹在某些问题中优于累积迹。建议在实现中先尝试荷兰迹，因为它与True Online TD(λ)结合最好。

难点3：离线策略迹的复杂性

  • 这是前沿研究领域，不必过于纠结细节。重点理解Watkins Q(λ)的截断思想和Tree-Backup如何避免重要性采样。

学习建议

  1. 编程实践：
    • 实现表格型TD(λ)在随机游走任务上，观察不同λ和迹类型的影响。
    • 实现Sarsa(λ)在山地车或风车世界任务，比较与Sarsa(0)的速度差异。
  2. 理论推导：尝试推导True Online TD(λ)的更新公式（可参考van Seijen & Sutton, 2014）。
  3. 阅读文献：深入了解Tree-Backup(λ)和GQ(λ)的工作原理。
  4. 思考应用：在深度强化学习中，资格迹常被忽略（因为计算量大），但近年有研究将其与神经网络结合，思考可能的挑战和解决方案。

资格迹是强化学习中优雅而强大的工具，它将各种方法统一在一个框架内，并为高效学习提供了理论依据。掌握本章内容，你将能更深入地理解现有算法的设计，并为设计新算法打下基础。

第十三章：策略梯度方法（Policy Gradient Methods）详细讲解

1. 引言：为什么需要策略梯度？

在前面的章节中，我们主要学习了基于值函数的方法，即通过估计动作价值函数 $q(s,a)$ 或状态价值函数 $v(s)$ 来间接得到策略（如 $\varepsilon$-贪心）。这类方法在离散动作空间和小规模问题上表现优异，但也存在一些局限性：

  • 不能处理连续动作空间：值函数方法需要为每个动作计算最大值，这在连续动作空间中不可行。
  • 策略可能是随机的：最优策略在某些情况下是随机的（例如，在部分可观测环境或博弈中），而值函数方法通常只能得到确定性策略（贪心策略）。
  • 策略参数的微小变化可能导致动作选择的剧变：在值函数方法中，如果动作价值的估计稍有变化，贪心策略可能突然跳转到完全不同的动作，导致学习不稳定。

策略梯度方法 直接对策略进行参数化 $\pi(a|s,\boldsymbol{\theta})$，并通过梯度上升来优化策略的性能。这种方法可以自然地处理连续动作空间，学习随机策略，并且具有良好的收敛性保证。

本章将介绍策略梯度方法的基本原理、核心定理、经典算法以及如何与值函数结合形成 Actor-Critic 方法。

2. 策略参数化

2.1 离散动作空间

对于离散动作，常用的参数化是 softmax（或称 Gibbs 分布）：

$$ \pi(a|s,\boldsymbol{\theta}) = \frac{e^{h(s,a,\boldsymbol{\theta})}}{\sum_b e^{h(s,b,\boldsymbol{\theta})}}, $$

其中 $h(s,a,\boldsymbol{\theta})$ 是动作偏好函数，通常为线性函数 $h(s,a,\boldsymbol{\theta}) = \boldsymbol{\theta}^\top \mathbf{x}(s,a)$ 或神经网络输出。Softmax 保证所有动作概率为正且和为1。

2.2 连续动作空间

对于连续动作，常用高斯分布：

$$ \pi(a|s,\boldsymbol{\theta}) = \frac{1}{\sigma(s,\boldsymbol{\theta})\sqrt{2\pi}} \exp\left( -\frac{(a - \mu(s,\boldsymbol{\theta}))^2}{2\sigma(s,\boldsymbol{\theta})^2} \right), $$

其中均值 $\mu(s,\boldsymbol{\theta})$ 和标准差 $\sigma(s,\boldsymbol{\theta})$ 由参数 $\boldsymbol{\theta}$ 决定。这样，策略输出的是一个连续动作的概率密度。

3. 策略梯度定理（Policy Gradient Theorem）

策略梯度方法的核心是策略梯度定理，它给出了性能函数 $J(\boldsymbol{\theta})$ 对参数 $\boldsymbol{\theta}$ 的梯度表达式。性能函数可以是起始状态的价值、平均每步奖励等。对于回合制任务，通常取：

$$ J(\boldsymbol{\theta}) = v_{\pi_\boldsymbol{\theta}}(s_0), $$

其中 $s_0$ 是起始状态。

策略梯度定理（以 $J(\boldsymbol{\theta}) = v_{\pi_\boldsymbol{\theta}}(s_0)$ 为例）：

$$ \nabla J(\boldsymbol{\theta}) \propto \sum_s \mu(s) \sum_a \nabla \pi(a|s,\boldsymbol{\theta}) q_\pi(s,a), $$

其中 $\mu(s)$ 是策略 $\pi_\boldsymbol{\theta}$ 下的稳态分布。另一种常见形式（用于梯度上升）为：

$$ \nabla J(\boldsymbol{\theta}) = \mathbb{E}_{\pi_\boldsymbol{\theta}} \left[ \sum_{a} q_\pi(S_t,a) \nabla \pi(a|S_t,\boldsymbol{\theta}) \right], $$

或者利用对数导数技巧（$\nabla \pi = \pi \nabla \ln \pi$）：

$$ \nabla J(\boldsymbol{\theta}) = \mathbb{E}_{\pi_\boldsymbol{\theta}} \left[ q_\pi(S_t,A_t) \nabla \ln \pi(A_t|S_t,\boldsymbol{\theta}) \right]. $$

这个形式将梯度表达为期望形式，便于用蒙特卡洛采样估计。

4. REINFORCE 算法

REINFORCE（Williams, 1992）是最简单的蒙特卡洛策略梯度算法。它直接使用策略梯度定理的期望形式，用采样回报 $G_t$ 代替 $q_\pi(S_t,A_t)$：

对于每个回合中的每一步 $t$：

$$ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha \gamma^t G_t \nabla \ln \pi(A_t|S_t,\boldsymbol{\theta}), $$

其中 $\gamma^t$ 是折扣因子（可选，取决于性能定义）。REINFORCE 是一种同策略方法，需要完整回合才能更新。

优点：无偏估计，收敛性有保证。 缺点：方差很大，学习缓慢。

例13.1：短走廊问题
书中用一个简单的网格世界（短走廊）说明 REINFORCE 的学习过程。在这个问题中，最优策略是随机的，REINFORCE 能够学到正确的随机策略，而值函数方法只能学到确定性策略（次优）。

5. 带基线的 REINFORCE

为了减小方差，可以在梯度估计中引入基线（baseline） $b(s)$：

$$ \nabla J(\boldsymbol{\theta}) = \mathbb{E}_{\pi_\boldsymbol{\theta}} \left[ (q_\pi(S_t,A_t) - b(S_t)) \nabla \ln \pi(A_t|S_t,\boldsymbol{\theta}) \right]. $$

基线可以是任意函数，只要不依赖于动作 $A_t$，期望不变。常用基线是状态价值估计 $\hat{v}(S_t,\mathbf{w})$，因为它与动作无关且接近 $q_\pi$，能有效降低方差。

带基线的 REINFORCE 更新为：

$$ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha \gamma^t (G_t - \hat{v}(S_t,\mathbf{w})) \nabla \ln \pi(A_t|S_t,\boldsymbol{\theta}), $$

同时用 TD 或蒙特卡洛方法更新价值估计 $\mathbf{w}$。

6. Actor-Critic 方法

Actor-Critic 将策略梯度与值函数估计相结合：

  • Actor：策略 $\pi(a|s,\boldsymbol{\theta})$，负责选择动作。
  • Critic：价值函数 $\hat{v}(s,\mathbf{w})$（或 $\hat{q}(s,a,\mathbf{w})$），负责评价 actor 的表现。

Critic 提供TD误差作为评价信号，实现自举，从而降低方差并允许在线学习。

6.1 单步 Actor-Critic

在每个时间步：

  1. 从策略 $\pi(\cdot|S_t,\boldsymbol{\theta})$ 采样动作 $A_t$，执行得 $R_{t+1}, S_{t+1}$。
  2. 计算 TD 误差：$\delta_t = R_{t+1} + \gamma \hat{v}(S_{t+1},\mathbf{w}) - \hat{v}(S_t,\mathbf{w})$。
  3. 更新 Critic：$\mathbf{w} \leftarrow \mathbf{w} + \alpha_\mathbf{w} \delta_t \nabla \hat{v}(S_t,\mathbf{w})$。
  4. 更新 Actor：$\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha_\boldsymbol{\theta} \delta_t \nabla \ln \pi(A_t|S_t,\boldsymbol{\theta})$。

这里 $\delta_t$ 作为优势函数 $A_t = q_\pi(S_t,A_t) - v_\pi(S_t)$ 的近似。

6.2 带资格迹的 Actor-Critic

将资格迹引入 Actor-Critic 可进一步提高学习效率。对于 Actor，迹更新为：

$$ \mathbf{e}_t^\theta = \gamma \lambda^\theta \mathbf{e}_{t-1}^\theta + \nabla \ln \pi(A_t|S_t,\boldsymbol{\theta}), $$

更新 Actor：$\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \alpha_\boldsymbol{\theta} \delta_t \mathbf{e}_t^\theta$。 Critic 可使用 TD(λ) 更新。

7. 连续动作的处理

策略梯度方法天然适合连续动作空间。只需将策略参数化为高斯分布，梯度 $\nabla \ln \pi(a|s,\boldsymbol{\theta})$ 可解析计算。例如，对于均值为 $\mu(s,\boldsymbol{\theta})$、方差固定的高斯策略：

$$ \ln \pi(a|s,\boldsymbol{\theta}) = -\frac{(a - \mu(s,\boldsymbol{\theta}))^2}{2\sigma^2} - \ln(\sigma\sqrt{2\pi}), $$

则

$$ \nabla_\mu \ln \pi = \frac{a - \mu(s,\boldsymbol{\theta})}{\sigma^2}. $$

这样，更新可以直接应用。

例13.2：山地车（Mountain Car）的连续动作版本
如果将离散动作（油门+1、-1、0）改为连续油门值，策略梯度方法能够学习到平滑的控制策略。

8. 优势函数

在 Actor-Critic 中，使用 TD 误差 $\delta_t$ 作为优势函数的近似。更一般地，优势函数定义为：

$$ A^\pi(s,a) = q_\pi(s,a) - v_\pi(s). $$

使用优势函数可以进一步减小方差，因为它反映了相对于平均水平的优势。在实际算法中，常用 GAE（Generalized Advantage Estimation） 来平衡偏差与方差：

$$ \hat{A}_t = \sum_{l=0}^{\infty} (\gamma\lambda)^l \delta_{t+l}, $$

其中 $\delta_t$ 是 TD 误差，$\lambda$ 控制自举程度。

9. 概念关系图

graph TD A[策略梯度方法] --> B[策略参数化] A --> C[策略梯度定理] C --> D[REINFORCE] C --> E[带基线的REINFORCE] E --> F[Actor-Critic] F --> G[单步Actor-Critic] F --> H[带资格迹的Actor-Critic] F --> I[优势函数与GAE] A --> J[连续动作处理] A --> K[与值函数方法的联系] K --> L[基于值的方法（如Q-learning）]

10. 与前后的联系

  • 第2章（多臂老虎机） 的梯度老虎机算法是单步、无状态的策略梯度雏形。
  • 第5-6章（MC和TD） 提供了价值估计的基础，Actor-Critic 中的 Critic 正是基于这些方法。
  • 第7章（资格迹） 可与 Actor-Critic 结合形成更高效的算法。
  • 第11章（异策略方法） 中的一些思想（如重要性采样）可用于异策略策略梯度（如 Off-policy Actor-Critic）。
  • 第13章以后（深度强化学习） 将策略梯度与深度神经网络结合，形成 DDPG、PPO、A3C 等现代算法。

11. 核心要点总结

  1. 策略参数化：将策略表示为可微函数（如 softmax 或高斯分布）。
  2. 策略梯度定理：给出了性能函数梯度的期望形式，为算法设计提供理论基础。
  3. REINFORCE：最简单的蒙特卡洛策略梯度，无偏但方差大。
  4. 基线：引入基线（如价值估计）可显著减小方差。
  5. Actor-Critic：结合策略梯度和值函数估计，实现自举和在线学习。
  6. 优势函数：使用优势函数代替原始回报，进一步优化梯度估计。
  7. 连续动作：策略梯度自然处理连续动作，只需适当参数化。
  8. 与值函数方法的比较：策略梯度适用于随机策略和连续动作，收敛性更稳定。

12. 常见难点与学习建议

难点1：策略梯度定理的理解

  • 建议：仔细阅读书中定理的推导过程，理解对数导数技巧（$\nabla \pi = \pi \nabla \ln \pi$）和期望的转换。可尝试在简单 MDP 上手动计算梯度，验证定理。

难点2：方差问题

  • REINFORCE 方差大的原因：回报 $G_t$ 波动大，且乘以概率的梯度。理解基线为何不改变期望但降低方差，可通过简单的统计例子（如估计均值时减去常数）来类比。

难点3：Actor 和 Critic 的学习率

  • 实践中需小心调整 Actor 和 Critic 的学习率，通常 Critic 应比 Actor 学习更快（或使用不同的步长）。可参考 PPO 等算法中的处理。

学习建议

  1. 编程实践：
    • 实现 REINFORCE 和带基线的 REINFORCE 在短走廊或 CartPole 任务上，比较学习曲线。
    • 实现单步 Actor-Critic 在山地车连续动作版本。
  2. 理论推导：推导高斯策略下的 $\nabla \ln \pi$ 表达式，并实现之。
  3. 阅读文献：了解现代策略梯度算法（如 PPO、A3C、SAC）如何继承和发展本章思想。
  4. 思考应用：策略梯度在机器人控制、游戏 AI 中的成功应用，体会其优势。

策略梯度方法构成了现代深度强化学习的基石。掌握本章内容后，你将能理解许多前沿算法的核心思想，并为后续研究打下坚实基础。

第十四章：心理学（Psychology）详细讲解

1. 引言：为什么强化学习要关注心理学？

强化学习（RL）的核心思想——智能体通过与环境交互、根据奖励信号调整行为——并非计算机科学家的凭空发明，而是深深植根于心理学对动物和人类学习的长期研究。实际上，RL 的许多概念和算法都可以在心理学的学习理论中找到对应物。本章将探讨 RL 与心理学之间的双向关系：

  • 心理学为 RL 提供了灵感和实验证据；
  • RL 的数学模型为心理学理论提供了精确的计算框架，能够解释和预测复杂的动物学习现象。

通过本章，我们将看到 RL 不仅是一门工程学科，更是理解智能本质的重要工具。

2. 心理学学习理论的基石

2.1 效果律（Law of Effect）

由 Edward Thorndike 于 1911 年提出，是 RL 最直接的心理学术源。效果律指出：

在相同情境下，导致满意后果的反应将与该情境建立更强的联结，未来更可能再次发生；导致不适后果的反应则联结减弱。

这正是 RL 中“奖励增加动作概率、惩罚减少动作概率”的原型。Thorndike 的“迷笼实验”（猫通过尝试打开笼门获得食物）展示了试错学习的过程，与 RL 中的探索与利用如出一辙。

2.2 操作性条件反射（Operant Conditioning）

B.F. Skinner 将效果律发展为操作性条件反射理论。核心概念包括：

  • 强化（reinforcement）：任何能增加反应概率的刺激（如食物）。
  • 惩罚（punishment）：任何能减少反应概率的刺激（如电击）。
  • 正强化/负强化：正强化是给予奖励，负强化是移除厌恶刺激。
  • 强化程序（schedules of reinforcement）：如固定比率、可变比率等，对行为模式有深刻影响，这与 RL 中的奖励分布和探索策略相关。

Skinner 箱实验是操作性条件反射的典型例子：动物按压杠杆获得食物，从而学会按压杠杆。

2.3 巴甫洛夫条件反射（Pavlovian Conditioning）

Ivan Pavlov 的经典条件反射研究揭示了动物如何将中性刺激（如铃声）与重要事件（如食物）关联。当铃声反复与食物同时出现后，单独铃声也能引起唾液分泌。这对应于 RL 中的预测学习：铃声成为食物即将到来的预测信号，其预测价值可以用值函数表示。

在 RL 术语中，条件刺激（CS）相当于状态，非条件刺激（US）相当于奖励，条件反应（CR）相当于对奖励的预期行为。

3. 强化学习对心理学现象的计算解释

3.1 时序差分学习与多巴胺神经元

RL 中的 TD 误差 $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 在动物学习中有惊人的对应物。神经生理学研究发现，中脑多巴胺神经元的放电模式与 TD 误差高度一致：

  • 当奖励未预测到时，多巴胺神经元在奖励时刻强烈放电（正误差）。
  • 当奖励完全被预测时，多巴胺神经元在奖励时刻无反应（零误差）。
  • 当预测奖励未出现时，多巴胺神经元在奖励应出现时刻放电抑制（负误差）。

这种对应表明，多巴胺系统可能是在编码“奖励预测误差”，从而指导学习。这是 RL 对神经科学最著名的贡献之一。

3.2 阻塞效应（Blocking）

Kamin（1969）发现，如果动物已经学会刺激 A 预测奖励，那么后续将 A 与 B 同时呈现时，动物不会学会 B 也预测奖励。这称为阻塞效应。RL 中的 TD 学习可以完美解释：因为 A 已经能完美预测奖励，B 的出现不产生新的预测误差，因此 B 的价值不会更新。这个现象为 TD 学习提供了关键实验支持。

3.3 二阶条件反射（Second-Order Conditioning）

如果刺激 A 预测奖励，那么将新刺激 B 与 A 配对（不直接与奖励配对），动物也会对 B 产生条件反应。在 RL 中，这对应于值函数的传播：A 获得高价值后，与 A 配对的 B 也会获得价值，因为 TD 误差会从 A 传递给 B。

3.4 条件性强化（Conditioned Reinforcement）

在操作性条件反射中，原本中性的刺激（如点击声）如果与食物配对，它本身也能作为强化物维持行为。这对应于 RL 中的二次强化：点击声获得了正的价值，因此可以作为奖励信号。

3.5 探索与利用的心理学解释

动物行为中也存在探索与利用的权衡。例如，在“多臂老虎机”任务中，动物必须在已知高回报选项和未知选项之间选择。研究表明，动物会表现出接近最优的探索策略，与 $\varepsilon$-贪心或 UCB 等算法一致。

4. 心理学实验与强化学习模型的对应

以下表格总结了典型心理学实验与 RL 概念/算法的对应关系：

心理学现象/实验RL 概念/算法解释
Thorndike 迷笼试错学习、效果律猫尝试不同动作，最终成功动作概率增加
Skinner 箱操作性条件反射、Q-learning动物学习动作-奖励映射
巴甫洛夫条件反射TD 学习、值函数中性刺激获得预测价值
阻塞效应TD 误差已有预测阻止新学习
二阶条件反射值函数传播价值从初级刺激传递到次级刺激
多巴胺神经元放电TD 误差神经元编码预测误差
延迟满足折扣因子 γ未来奖励的折现
习得性无助无奖励、负价值长期负奖励导致放弃尝试

5. 心理学给强化学习研究的启示

  • 奖励设计：心理学强调奖励的时效性和一致性，RL 中奖励函数的设计需考虑动物的生物特性。
  • 探索机制：动物探索不是完全随机的，而是有内在动机（好奇心），这启发了 RL 中的内在奖励（如 curiosity-driven exploration）。
  • 分层学习：动物能学会将复杂行为分解为子目标，对应 RL 中的层次强化学习。
  • 情绪与强化：情绪（如恐惧、愉悦）可作为内部奖励信号，引导行为。

6. 概念关系图

graph TD A[心理学学习理论] --> B[效果律] A --> C[操作性条件反射] A --> D[巴甫洛夫条件反射] B --> E[强化与惩罚] C --> E D --> F[预测学习] E --> G[强化学习核心：奖励最大化] F --> H[TD误差与多巴胺] G --> I[算法：Q-learning,策略梯度] H --> I I --> J[解释心理现象] J --> K[阻塞效应] J --> L[二阶条件反射] J --> M[探索-利用]

7. 与前后的联系

  • 前几章（1-13章） 介绍了 RL 的数学框架和算法，本章为这些算法提供了心理学基础，说明它们不是凭空产生，而是反映了生物学习的原理。
  • 第15章（神经科学） 将进一步探讨 RL 的神经生物学基础，特别是多巴胺系统的详细模型。
  • 第16-17章（应用与前沿） 将展示如何利用 RL 设计更智能的机器，并探索与心理学结合的未来方向。

8. 核心要点总结

  1. RL 源于心理学：效果律、操作性条件反射是 RL 的雏形。
  2. TD 误差与多巴胺：RL 的预测误差机制在神经科学中找到对应，是双向启发的典范。
  3. 阻塞效应验证 TD 学习：心理学实验支持 TD 学习的合理性。
  4. 二阶条件反射与价值传播：解释了为什么中性刺激能获得强化能力。
  5. 探索-利用：动物行为中也存在类似权衡，启发更自然的探索策略。
  6. 心理学启发 RL 设计：内在动机、层次学习、情绪等心理学概念为 RL 提供新思路。

9. 常见难点与学习建议

难点1：区分巴甫洛夫条件反射与操作性条件反射

  • 巴甫洛夫条件反射是“刺激-刺激”学习，动物学会预测重要事件；操作性条件反射是“动作-结果”学习，动物学会通过动作获取奖励。两者在 RL 中分别对应预测问题和控制问题。

难点2：理解阻塞效应的计算意义

  • 阻塞效应说明学习需要“惊讶”，即预测误差。没有误差就没有学习。这是 TD 学习的核心。

难点3：多巴胺编码的是奖励还是预测误差？

  • 早期认为多巴胺编码奖励，但后来发现它编码的是预测误差。理解这一转变需要 TD 误差的概念。

学习建议

  1. 阅读经典实验：了解 Thorndike、Skinner、Pavlov、Kamin 等人的原始实验设计，加深对心理学现象的理解。
  2. 模拟实验：用编程实现简单的 TD 学习，模拟阻塞效应，观察预测误差如何导致学习停止。
  3. 跨学科思考：阅读神经科学文献（如 Schultz, Dayan, Montague 1997）了解多巴胺与 TD 误差的关联。
  4. 反思 RL 设计：思考如何将心理学原理（如好奇心、内在动机）融入 RL 算法，提升学习效率。

心理学与强化学习的交汇不仅揭示了智能的共性原理，也为设计更类人的智能系统提供了蓝图。掌握本章内容，你将能更深刻地理解 RL 算法为何如此设计，以及它们如何反映生物学习的本质。

第十五章：神经科学（Neuroscience）详细讲解

1. 引言：强化学习与神经科学的双向关系

强化学习不仅是一门工程学科，它还与神经科学有着深刻的相互启发关系。一方面，神经科学的研究揭示了动物大脑中存在与强化学习算法惊人相似的机制，为RL的生物学合理性提供了证据；另一方面，RL的计算模型为理解大脑的学习和决策过程提供了理论框架，帮助解释实验现象并预测新的发现。

本章将探讨RL与神经科学的交叉领域，重点关注多巴胺系统、基底节、前额叶皮层等脑区如何实现奖励预测、动作选择和时序差分学习。

2. 多巴胺神经元与奖励预测误差

2.1 经典实验：Schultz等人的研究

Wolfram Schultz及其同事在20世纪90年代进行了一系列著名的神经生理学实验，记录了猴子在执行任务时中脑多巴胺神经元的放电活动。他们发现：

  • 当猴子获得意料之外的奖励（如果汁）时，多巴胺神经元短暂放电（正相位响应）。
  • 当奖励完全可预测时（如条件刺激后总是有奖励），神经元在奖励时刻没有反应，而是在条件刺激时刻放电。
  • 当预期奖励被省略时，神经元在奖励应出现时刻放电受到抑制（负相位响应）。

2.2 TD误差的神经对应

Montague、Dayan和Sejnowski（1996）指出，多巴胺神经元的放电模式与时序差分（TD）误差 $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 高度一致：

  • 未预测的奖励 → 正TD误差（奖励时刻放电）
  • 完全预测的奖励 → TD误差为零（无放电）
  • 奖励被省略 → 负TD误差（放电抑制）

这种惊人的对应表明，多巴胺系统可能是在编码奖励预测误差，并利用这个信号来指导学习。这为TD学习提供了神经层面的证据，也成为计算神经科学最著名的成果之一。

2.3 多巴胺的功能

多巴胺不仅参与奖励处理，还涉及动机、运动控制等多种功能。在RL框架中，多巴胺的相位信号用于更新值函数的估计，而多巴胺的基线水平可能反映预期的平均奖励（即$\bar{R}$）。

3. 基底节与动作选择

3.1 基底节的结构

基底节是一组皮层下核团，包括纹状体（尾状核和壳核）、苍白球、黑质和丘脑底核。它在动作选择、程序性学习和习惯形成中起关键作用。

3.2 直接通路与间接通路

基底节内存在两条主要通路：

  • 直接通路：促进运动，通过抑制苍白球内侧部（GPi）和黑质网状部（SNr）来解除丘脑的抑制，从而允许皮层发起动作。
  • 间接通路：抑制运动，通过一系列中间核团增强GPi/SNr的抑制输出，阻止不想要的动作。

这两条通路的平衡决定了最终的动作选择，类似于强化学习中“动作选择”机制。

3.3 多巴胺对通路的影响

多巴胺对直接通路和间接通路有相反的作用：

  • 在直接通路中，多巴胺通过D1受体增强兴奋性，促进动作。
  • 在间接通路中，多巴胺通过D2受体抑制活动，从而减少对动作的抑制。

因此，多巴胺的释放（如正TD误差）会偏向于选择那些获得正预测误差的动作，这正好对应强化学习中的“更新”和“偏好”。

4. 前额叶皮层与认知控制

4.1 工作记忆与计划

前额叶皮层（PFC）参与工作记忆、计划和抽象推理。在RL中，这些功能对应于维护状态信息、进行前瞻性规划和策略搜索。PFC可能编码“状态”的抽象表示，并与基底节互动以选择合适动作。

4.2 层级强化学习

研究表明，前额叶皮层可能支持层级决策，即将复杂任务分解为子目标。这与RL中的**选项（options）**框架（Sutton, Precup, Singh 1999）相呼应，其中高层策略选择子策略，子策略执行一系列基本动作。

5. 其他脑区的角色

  • 杏仁核：参与情绪学习和条件性恐惧，对应RL中与负奖励（惩罚）相关的学习。
  • 海马体：参与情景记忆和空间导航，可能与基于模型的RL中的世界模型构建有关。
  • 小脑：参与精细运动控制和时序协调，可能涉及低层控制器的学习。

6. 神经调质系统与探索

除了多巴胺，其他神经调质也参与学习：

  • 去甲肾上腺素：与注意力、警觉性相关，可能调节探索-利用平衡。
  • 乙酰胆碱：参与注意力、记忆编码，可能影响学习率。
  • 血清素：与情绪、冲动控制相关，可能参与惩罚处理和延迟满足。

这些调质系统可能对应RL算法中的各种参数（如探索率、学习率、折扣因子）的动态调节。

7. 计算神经科学模型

基于RL的计算模型被广泛用于模拟神经活动和行为。例如：

  • Actor-Critic 模型：Critic对应纹状体中的价值预测神经元（可能通过多巴胺信号），Actor对应直接通路中的动作选择神经元。
  • Q-learning 的神经实现：有模型提出，纹状体中的棘状神经元（MSNs）通过突触可塑性实现Q值的更新，多巴胺信号作为奖赏预测误差指导可塑性。

这些模型不仅拟合实验数据，还能预测新的神经现象，如多巴胺对突触可塑性的影响。

8. 概念关系图

graph TD A[神经科学] --> B[多巴胺系统] A --> C[基底节] A --> D[前额叶皮层] A --> E[其他脑区] B --> F[TD误差编码] B --> G[奖励预测] C --> H["直接通路/间接通路"] C --> I[动作选择] D --> J["工作记忆/规划"] D --> K[层级决策] F --> L[RL算法验证] I --> L L --> M[计算神经科学模型] M --> N[Actor-Critic] M --> O[Q-learning神经实现]

9. 与前后的联系

  • 第14章（心理学） 提供了RL与行为实验的联系，本章则将RL与神经机制联系起来。
  • 前几章（1-13章） 介绍了RL的算法和理论，本章为这些算法提供了神经生物学基础。
  • 第16章（应用与案例） 展示了RL在工程中的应用，而神经科学启示可能催生更高效的算法（如神经调节启发式学习率调整）。

10. 核心要点总结

  1. 多巴胺编码TD误差：中脑多巴胺神经元的放电模式与RL中的奖励预测误差高度一致，这是RL与神经科学最著名的交汇点。
  2. 基底节实现动作选择：直接通路和间接通路的平衡，由多巴胺调节，实现了基于价值的动作选择，类似于Actor-Critic架构。
  3. 前额叶皮层支持认知控制：PFC参与状态表征、规划和层级决策，与RL中的模型和选项框架对应。
  4. 其他脑区各司其职：杏仁核、海马体、小脑等参与情绪、记忆和运动学习，丰富了对RL不同模块的神经理解。
  5. 计算神经科学模型：RL模型被用于模拟神经活动，并预测新的实验现象，形成理论与实验的闭环。
  6. 神经调质系统：多巴胺、去甲肾上腺素、乙酰胆碱等调节学习参数，可能实现自适应探索和利用。

11. 常见难点与学习建议

难点1：区分多巴胺的相位与紧张性放电

  • 相位放电对应短暂的TD误差，用于学习；紧张性放电反映平均奖励水平。理解两者的不同有助于解释多巴胺的多重功能。

难点2：基底节通路的动态平衡

  • 直接通路和间接通路不是独立运作的，而是动态平衡。多巴胺通过D1和D2受体调节这种平衡，从而实现动作偏好的更新。建议查阅基底节的解剖图和功能示意图。

难点3：从神经现象到RL算法的映射

  • 不同脑区的功能映射到RL的哪个部分（状态、动作、价值、策略）有时是模糊的。建议从Actor-Critic模型入手，逐步扩展到更复杂的框架。

学习建议

  1. 阅读原始文献：Schultz, Dayan & Montague (1997) 的综述是经典入门；进一步可阅读Doya (2002) 关于神经调质与RL的论文。
  2. 模拟实验：用Python实现一个简单的TD学习模型，并模拟多巴胺神经元的放电模式，加深理解。
  3. 跨学科思考：结合心理学和神经科学，思考RL算法如何改进（例如，基于多巴胺的探索机制）。
  4. 观看视频：神经科学公开课（如MIT 9.13）中有关于基底节和多巴胺的讲解，有助于建立直观认识。

神经科学与强化学习的交叉领域正在蓬勃发展，它不仅验证了RL的生物学合理性，也为设计更智能的算法提供了灵感。掌握本章内容，你将能更深刻地理解RL算法与大脑的关联，并为未来的跨学科研究奠定基础。

第十六章：应用与案例研究（Applications and Case Studies）详细讲解

1. 引言：从理论到实践

在前面的章节中，我们系统学习了强化学习的理论基础和各类算法——从动态规划、蒙特卡洛、时序差分到策略梯度，从表格方法到函数近似，从同策略到异策略。然而，理论的最终价值在于应用。本章通过一系列经典的案例研究，展示了强化学习方法如何在现实世界或复杂模拟任务中取得成功。这些案例不仅验证了算法的有效性，也揭示了在实际应用中遇到的挑战（如状态表示、探索、计算效率等）以及如何巧妙地将领域知识融入学习系统。

本章将介绍以下几个案例：

  • TD-Gammon：一个通过学习达到人类顶尖水平的西洋双陆棋程序。
  • Samuel’s Checkers Player：历史上最早的强化学习成功案例之一。
  • Acrobot：一个连续控制任务的基准问题。
  • Elevator Dispatching：优化电梯群控的工业应用。
  • Dynamic Channel Allocation：蜂窝电话系统中的信道分配问题。
  • Job-Shop Scheduling：复杂调度问题的强化学习解决方案。

通过这些案例，我们将看到强化学习方法如何在不同领域被灵活应用，并总结出成功的共同要素。

2. TD-Gammon：西洋双陆棋大师

2.1 背景与问题

西洋双陆棋（Backgammon）是一种二人零和博弈，具有巨大的状态空间（约 $10^{20}$ 个状态），且有随机性（掷骰子）。传统的启发式搜索方法由于巨大的分支因子（约400）而难以奏效。

2.2 方法

TD-Gammon 由 Gerald Tesauro 开发，使用时序差分学习（TD(λ)）与人工神经网络相结合：

  • 状态表示：将棋盘位置编码为198个输入特征（包括每个点的棋子数、是否被占用等）。
  • 网络结构：单隐层神经网络（40-80个隐单元），输出为对当前玩家获胜概率的估计。
  • 学习过程：程序通过自我对弈生成经验，每走一步后，用 TD(λ) 更新网络权重，目标是最小化预测误差。训练中使用了 ε-贪心 探索，但随着训练逐步降低探索率。
  • 搜索增强：后续版本（如 TD-Gammon 2.0）在决策时结合了浅层搜索（2-3层），进一步提高棋力。

2.3 结果与意义

  • 经过约150万局自我对弈，TD-Gammon 达到了人类顶尖大师的水平。
  • 程序发现了一些人类从未采用的新走法，并被职业选手采纳，改变了西洋双陆棋的玩法。
  • 意义：证明了仅通过自我对弈和 TD 学习，无需人类专家知识，即可在复杂博弈中超越人类水平。

2.4 关键点

  • 自举（bootstrapping）：TD(λ) 利用后继状态的估计进行更新，加速学习。
  • 函数近似：神经网络实现了从大量状态到价值的泛化。
  • 自我对弈：无需外部监督，自动生成训练数据。

3. Samuel’s Checkers Player：历史先驱

3.1 背景

Arthur Samuel 在1950-60年代开发的跳棋程序是机器学习历史上的里程碑，也是强化学习的早期范例。

3.2 方法

  • 价值函数：使用线性函数近似，特征包括棋子优势、中心控制等。
  • 学习机制：程序通过自我对弈，利用时序差分思想（但当时未称为TD）更新权重。具体地，它比较当前棋盘位置的评估值与通过搜索得到的更准确评估值之间的差异，并调整权重使两者更接近。
  • 搜索：结合了启发式搜索（如α-β剪枝）来改进决策质量。

3.3 结果

Samuel 的程序经过训练后达到了相当不错的业余水平，虽然未超过人类大师，但它证明了计算机可以通过学习自我改进。

3.4 关键点

  • 特征工程：手工设计的特征对成功至关重要。
  • 自举与搜索结合：搜索提供更精确的目标，学习泛化到未见状态。
  • 历史地位：为后来的 TD-Gammon 等系统奠定了基础。

4. Acrobot：连续控制基准

4.1 问题描述

Acrobot 是一个两连杆欠驱动机械臂（类似体操运动员在单杠上摆动），目标是将末端（脚）摆过指定高度。动作空间：在关节处施加三种离散力矩（正向、反向、零）。状态空间为连续的四维（两关节角度和角速度）。

4.2 方法

Sutton（1996）采用 Sarsa(λ) 结合瓦片编码（tile coding） 解决此任务：

  • 函数近似：使用瓦片编码将连续状态离散化为二进制特征，每动作一组特征。
  • 算法：同策略 Sarsa(λ) 在线学习，使用 ε-贪心 策略（ε=0，但通过乐观初始化保证探索）。
  • 参数：λ=0.9，α=0.2/48（48个铺层）。

4.3 结果

经过数百回合学习，程序学会了通过来回摆动积蓄能量，最终将末端甩到目标高度（图14.7）。学习曲线（图14.6）显示，Sarsa(λ) 显著快于无资格迹的版本。

4.4 关键点

  • 连续状态处理：瓦片编码有效泛化。
  • 资格迹加速：λ>0 将奖励快速传播到前期动作。
  • 乐观初始化：鼓励探索，无需显式 ε-贪心。

5. Elevator Dispatching：电梯群控优化

5.1 问题背景

现代高层建筑中，如何调度多部电梯以最小化乘客等待时间是重要的经济问题。状态空间极大（估计 $10^{22}$），无法用传统方法求解。

5.2 方法

Crites 和 Barto（1996）应用 Q-learning 于四部电梯、十层楼的仿真环境：

  • 半马尔可夫决策过程（SMDP）：电梯决策发生在离散事件时刻（如乘客到达、电梯停靠），奖励为各乘客等待时间的平方和的负值。
  • 状态表示：精心设计47个输入特征，包括各层呼叫等待时间、电梯位置和方向等。
  • 函数近似：神经网络（20隐单元）近似动作价值函数。
  • 训练：多部电梯共享奖励，但各自独立决策，通过模拟运行数万小时（计算时间约4天）训练。

5.3 结果

训练出的调度策略在平均等待时间、超过60秒等待比例等指标上显著优于传统方法（如扇区调度），接近甚至超过当时最先进的研究算法（图14.9）。

5.4 关键点

  • SMDP 建模：将连续时间问题转化为离散事件，折扣因子由事件间隔决定。
  • 特征工程：领域知识融入状态表示。
  • 多智能体：虽独立学习，但共享奖励，体现合作。

6. Dynamic Channel Allocation：动态信道分配

6.1 问题背景

蜂窝电话系统中，需要将有限的信道分配给通话用户，同时避免干扰（同一信道不能用于相邻小区）。目标是最大化接入率，最小化阻塞概率。

6.2 方法

Singh 和 Bertsekas（1997）提出一种 SMDP-Q-learning 方法：

  • 状态：当前信道分配配置 + 事件类型（呼叫到达、离开、切换）。
  • 动作：为到达呼叫分配信道（或阻塞），或为离开呼叫重新配置信道。
  • 后状态：由于动作结果是确定性的（配置变化），学习后状态价值函数，大大简化问题。
  • 特征：每个小区可用信道数、信道使用密度等线性特征。
  • 算法：线性 TD(0) 更新。

6.3 结果

在49个小区、70信道的仿真中，RL方法在不同负载下均优于固定分配和动态借用算法（BDCL），阻塞率降低（图14.10）。

6.4 关键点

  • 后状态价值：利用确定性转移简化学习。
  • 线性函数近似：特征设计至关重要。
  • 在线学习：算法可实时适应流量变化。

7. Job-Shop Scheduling：车间调度

7.1 问题背景

车间调度涉及多任务、多资源的时序和资源约束，目标是找到满足约束的最短时间安排。NASA 航天飞机载荷处理问题（SSPP）是典型实例。

7.2 方法

Zhang 和 Dietterich（1995, 1996）将调度视为搜索过程，用 TD(λ) 学习如何高效搜索：

  • 状态：当前部分调度方案。
  • 动作：选择修复操作（如移动任务、重新分配资源池）。
  • 奖励：每一步的小负惩罚，最终奖励为方案长度的负值（用资源扩张因子 RDF 度量）。
  • 函数近似：两种网络结构——手工特征神经网络和时延神经网络（TDNN）。
  • 训练：在100个人工生成的问题上训练，用 ε-贪心选择动作，结合经验回放和随机采样搜索。

7.3 结果

学习到的调度策略能以更少的修复步骤找到高质量调度，计算时间也少于传统迭代修复方法（图14.11,14.12）。

7.4 关键点

  • 问题转化：将调度视为序列决策问题。
  • 状态表示：从手工特征到自动特征提取（TDNN）。
  • 泛化：学到的策略适用于新问题实例。

8. 案例总结与共性

案例领域RL方法关键技巧成果
TD-Gammon棋类博弈TD(λ) + 神经网络自我对弈、搜索增强人类大师水平
Samuel’s Checkers棋类博弈线性近似+自举特征工程、搜索业余水平
Acrobot控制Sarsa(λ) + 瓦片编码资格迹、乐观初始化成功学习摆动策略
Elevator Dispatching运筹Q-learning + 神经网络SMDP、特征设计优于传统调度
Dynamic Channel Allocation通信SMDP-Q + 线性近似后状态价值、特征降低阻塞率
Job-Shop Scheduling调度TD(λ) + 神经网络问题转化、经验回放加速高质量调度

共同要素：

  • 函数近似：所有案例都使用某种形式的函数近似（线性、瓦片、神经网络）来泛化。
  • 算法选择：根据问题特性选择合适方法（如TD(λ)用于棋类，Sarsa用于控制，Q-learning用于SMDP）。
  • 领域知识：状态表示和特征设计对成功至关重要。
  • 探索机制：ε-贪心、乐观初始化、内在奖励等确保充分探索。
  • 计算资源：模拟或自我对弈生成大量数据，离线训练。

9. 概念关系图

graph TD A[应用案例] --> B[TD-Gammon] A --> C[Samuel's Checkers] A --> D[Acrobot] A --> E[Elevator Dispatching] A --> F[Dynamic Channel Allocation] A --> G[Job-Shop Scheduling] B --> H["TD(λ)+神经网络"] C --> I["线性近似+搜索"] D --> J["Sarsa(λ)+瓦片编码"] E --> K["Q-learning+SMDP"] F --> L["Q-learning+后状态"] G --> M["TD(λ)+特征学习"] H --> N[自我对弈] I --> O[特征工程] J --> P[连续状态离散化] K --> Q[事件驱动] L --> R[确定性转移] M --> S[调度即决策] N --> T[成功共性] O --> T P --> T Q --> T R --> T S --> T T --> U[函数近似] T --> V[领域知识] T --> W[探索机制]

10. 与前后的联系

  • 前几章（1-15章） 提供了理论和方法基础，本章展示了这些方法如何在实际问题中落地。
  • 第9-11章 的函数近似和异策略方法在多个案例中应用（如 TD-Gammon 的神经网络、Elevator 的 Q-learning）。
  • 第7章 的资格迹在 Acrobot 和 TD-Gammon 中发挥关键作用。
  • 第13章 的策略梯度虽未在这些案例中直接使用，但后续深度强化学习（如 DQN、AlphaGo）继承了本章案例的思想。

11. 核心要点总结

  1. 问题转化是关键：将实际问题建模为 MDP 或 SMDP，定义状态、动作、奖励。
  2. 函数近似必不可少：面对大状态空间，必须用泛化方法（特征、神经网络）。
  3. 探索与利用的平衡：需根据问题设计合适的探索策略。
  4. 领域知识融入：特征设计、状态表示、动作约束等融入可大幅提升学习效率。
  5. 算法选择有讲究：同策略 vs 异策略、资格迹、搜索深度等需匹配问题特性。
  6. 验证与评估：需在真实或高保真仿真中测试，与现有方法对比。
  7. 计算资源不可忽视：许多成功案例依赖于大量模拟数据或长时间训练。

12. 学习建议与难点

常见难点

  • 问题建模：如何将实际问题抽象为 RL 框架？建议从简单版本开始，逐步增加复杂性。
  • 特征设计：领域知识如何转化为特征？需与领域专家合作，尝试多种表示。
  • 算法参数调整：每个案例都有大量参数（α、λ、网络结构等），需系统实验。
  • 计算成本：许多案例需大量计算，可能无法在个人机器上复现，但可通过简化版模拟理解核心思想。

学习建议

  1. 阅读原始论文：每个案例都有详细论文，可深入了解细节。
  2. 动手复现简化版：例如，实现一个小型西洋双陆棋环境，用 TD(0) 学习；或在 OpenAI Gym 的 Acrobot 上实现 Sarsa(λ)。
  3. 思考替代方案：如果不用 RL，传统方法如何？RL 的优势在哪里？
  4. 关注现代发展：TD-Gammon 启发了 AlphaGo，了解后续发展有助于把握趋势。

13. 总结

本章通过六个经典案例，生动展示了强化学习在博弈、控制、运筹、通信、调度等领域的强大应用。这些案例不仅验证了理论的有效性，也为后续研究者提供了宝贵的实践经验和启示。正如 Sutton 和 Barto 所言，强化学习的最终目标是将理论与实际紧密结合，创造出能够解决现实世界问题的智能系统。

第十七章：前沿（Frontiers）详细讲解

1. 引言：探索强化学习的未来

在前面的章节中，我们系统学习了强化学习的基础理论、经典算法和成功应用。然而，RL 领域仍在迅速发展，许多重要的挑战和开放问题等待着我们去探索。本章将带领读者了解 RL 的前沿研究方向，这些方向正在拓展 RL 的能力边界，使其能够应对更复杂、更现实的问题。

本章将讨论以下几个前沿主题：

  • 部分可观测性与状态估计（Partially Observable MDPs）
  • 分层强化学习与时间抽象（Hierarchical RL and Temporal Abstraction）
  • 内在动机与探索（Intrinsic Motivation and Exploration）
  • 迁移学习与多任务学习（Transfer Learning and Multi-task Learning）
  • 多智能体强化学习（Multi-Agent RL）
  • 基于模型的强化学习与规划（Model-based RL and Planning）
  • 安全强化学习与鲁棒性（Safe RL and Robustness）
  • 与神经科学和心理学的深度结合（Integration with Neuroscience and Psychology）
  • 深度强化学习的挑战（Challenges in Deep RL）

这些方向并非孤立，而是相互交织，共同推动 RL 向更通用、更智能的方向发展。

2. 部分可观测性与状态估计

2.1 POMDP 框架

在许多现实问题中，智能体无法直接观测到环境的完整状态，只能通过传感器获得部分观测。这类问题被建模为部分可观测马尔可夫决策过程（POMDP）。POMDP 由以下要素构成：

  • 状态集 $\mathcal{S}$（隐藏的真实状态）
  • 动作集 $\mathcal{A}$
  • 观测集 $\mathcal{O}$
  • 转移概率 $p(s'|s,a)$
  • 观测概率 $p(o|s',a)$
  • 奖励函数 $r(s,a)$

智能体的目标是在不完全观测下最大化累积奖励。

2.2 信念状态（Belief State）

解决 POMDP 的一种经典方法是引入信念状态 $b(s)$，即智能体对当前处于真实状态 $s$ 的后验概率分布。信念状态是充分统计量，满足马尔可夫性质。因此，POMDP 可以转化为信念状态空间上的 MDP（但信念空间是连续的）。

2.3 近似方法

精确求解 POMDP 通常是难解的，因此需要近似方法：

  • 基于值函数的方法：如点基值迭代（PBVI）、启发式搜索。
  • 基于策略梯度的方法：直接优化带记忆的策略（如 RNN 策略）。
  • 状态表示学习：通过深度学习从观测序列中自动提取隐藏状态表示。

例：在自动驾驶中，车辆只能通过摄像头看到部分环境，需要推断被遮挡物体的可能位置。

3. 分层强化学习与时间抽象

3.1 动机

经典 RL 在每一步都选择原子动作，这在长时间任务中学习效率低下。分层强化学习（HRL）通过引入时间抽象（temporal abstraction），允许智能体在不同时间尺度上决策，从而加速学习并实现复杂行为。

3.2 选项（Options）框架

Sutton、Precup 和 Singh（1999）提出的选项是 HRL 的核心概念。一个选项由三部分组成：

  • 策略 $\pi : \mathcal{S} \times \mathcal{A} \to [0,1]$
  • 终止条件 $\beta : \mathcal{S} \to [0,1]$
  • 初始集 $I \subseteq \mathcal{S}$

选项可以像原子动作一样被高层策略选择，执行直到终止。选项内部可以包含更底层的选项，形成层级结构。

3.3 分层价值函数

在 HRL 中，可以定义分层价值函数，如：

  • $V^\mu(s)$：遵循高层策略 $\mu$ 的价值。
  • $Q^\mu(s, o)$：在状态 $s$ 选择选项 $o$ 的价值。

学习可以在多个层级同时进行。

3.4 其他 HRL 方法

  • 分层抽象机（HAM）：将策略表示为有限自动机。
  • MAXQ 分解：将任务分解为子任务，每个子任务有独立的价值函数。
  • Feudal Networks：基于“封建”结构，高层给中层指定子目标，中层给低层指令。

例：在迷宫导航中，高层策略选择“去房间”、“探索走廊”等选项，每个选项由底层原子动作实现。

4. 内在动机与探索

4.1 问题

在奖励稀疏的环境中，智能体可能长期得不到外部奖励，导致学习停滞。内在动机通过引入内部奖励信号，鼓励智能体探索新奇或有信息量的状态。

4.2 好奇心驱动探索

  • 基于预测误差：智能体对环境的动态进行建模，将预测误差作为内在奖励。如果某个状态-动作的结果难以预测，则给予正奖励，鼓励探索。
  • 基于信息增益：奖励智能体获取能减少环境不确定性的经验（如贝叶斯方法中的信息增益）。

4.3 计数探索与伪计数

  • 计数探索：为每个状态-动作对维护访问次数，将访问次数的倒数作为探索奖励。
  • 伪计数：在连续状态空间中，用密度模型估计状态的“新奇程度”。

4.4 内在动机的神经基础

心理学研究表明，动物具有内在动机（如好奇、玩耍）。多巴胺系统可能同时编码外部奖励和内部奖励。

例：在 Montezuma’s Revenge 这类游戏中，外部奖励极少，好奇心驱动的方法（如 ICM）能显著提升探索效率。

5. 迁移学习与多任务学习

5.1 目标

迁移学习旨在将在一个任务（源任务）中学到的知识迁移到另一个相关任务（目标任务）中，以减少学习时间和数据需求。

5.2 迁移方法

  • 值函数迁移：将源任务的值函数作为目标任务的初始值，或作为特征。
  • 策略迁移：将源任务的策略作为初始化，或通过微调适应新任务。
  • 特征迁移：学习可迁移的状态表示（如通过自编码器）。
  • 模型迁移：将环境动态模型迁移到新任务。

5.3 多任务学习

同时学习多个任务，通过共享表示来提高样本效率和泛化能力。常见方法包括多任务深度神经网络，其中低层特征共享，高层任务特定。

5.4 元强化学习（Meta-RL）

元强化学习旨在学习一个“学习算法”，使得智能体能够在新任务上快速适应（如通过少量梯度步）。典型方法包括RNN 元学习（将历史轨迹编码为状态，输出动作）。

例：机器人学会抓取不同形状的物体，先学习通用抓取策略，再快速适应新物体。

6. 多智能体强化学习（MARL）

6.1 问题框架

多智能体系统涉及多个同时学习并相互作用的智能体。根据目标一致性，可分为：

  • 完全合作：所有智能体共享同一个奖励（如团队协作）。
  • 完全竞争：零和博弈（如棋类游戏）。
  • 混合型：一般和博弈（如经济市场）。

6.2 挑战

  • 非平稳性：每个智能体的策略变化导致环境对其他智能体而言是非平稳的。
  • 信用分配：如何将团队奖励分配给每个智能体的动作？
  • 通信：智能体间是否允许通信？如何学习有效通信？
  • 扩展性：随着智能体数量增加，联合动作空间指数增长。

6.3 方法

  • 独立学习：每个智能体忽略其他智能体，将环境视为平稳（但实际不成立，需技巧）。
  • 集中训练与分散执行（CTDE）：训练时使用全局信息，执行时仅用局部观测。代表算法：MADDPG、QMIX。
  • 对手建模：显式建模其他智能体的策略，以预测其行为。
  • 通信学习：学习何时发送什么信息给其他智能体。

例：多机器人协同搬运物体，每个机器人只能局部观测，需合作完成任务。

7. 基于模型的强化学习与规划

7.1 模型的作用

基于模型的 RL（MBRL）通过学习环境模型，利用模型进行规划或生成模拟数据，以提高样本效率。

7.2 模型学习

  • 确定性模型：预测下一个状态和奖励（如神经网络）。
  • 概率模型：输出分布，捕捉不确定性（如高斯过程、贝叶斯网络）。

7.3 规划与学习结合

  • Dyna 架构：用真实经验更新模型，用模型生成模拟经验更新价值/策略。
  • 模型预测控制（MPC）：在每个时间步，用模型规划短时域最优动作，执行第一个动作，然后重新规划。
  • 想象增强学习：如 I2A（Imagination-Augmented Agents），用模型生成想象轨迹，辅助策略学习。

7.4 挑战

  • 模型偏差：学习到的模型可能不准确，导致规划失误。
  • 计算开销：规划可能很耗时，需权衡实时性。

例：在围棋中，AlphaZero 使用学习到的模型（即策略-价值网络）进行蒙特卡洛树搜索，结合了模型和无模型方法。

8. 安全强化学习与鲁棒性

8.1 问题

在现实世界中，RL 智能体的不安全行为可能导致灾难性后果（如自动驾驶事故）。安全 RL 旨在确保学习过程中和最终策略的安全性。

8.2 约束强化学习

  • 约束 MDP（CMDP）：在 MDP 基础上引入约束条件，如累计成本不超过阈值。
  • 拉格朗日方法：将约束作为惩罚项加入目标，用对偶梯度下降优化。

8.3 鲁棒强化学习

  • 对抗性扰动：假设环境参数或对手行为存在不确定性，学习在最坏情况下仍能表现良好的策略。
  • 分布鲁棒优化：在可能的动态分布上优化最坏情况性能。

8.4 离线强化学习

从静态数据集学习，不与环境交互，避免探索中的危险。挑战在于分布偏移和外推误差。常用方法包括保守 Q-learning（CQL）、行为克隆正则化等。

例：医疗治疗策略学习，必须在历史数据上离线学习，不能在线探索。

9. 与神经科学和心理学的深度结合

9.1 双向启发

  • RL 为神经科学提供计算模型，解释多巴胺、基底节等功能。
  • 神经科学启发 RL 算法，如基于多巴胺的探索机制、基于海马体的记忆模型。

9.2 认知架构

结合心理学中的工作记忆、注意力、情绪等概念，设计更类人的 RL 智能体。

例：DeepMind 的“Psychlab”平台用于研究 RL 智能体的认知能力，模拟心理学实验。

10. 深度强化学习的挑战

10.1 样本效率

深度 RL 通常需要海量数据，限制了在真实世界的应用。改进方向包括：模型基方法、数据增强、元学习等。

10.2 泛化能力

训练环境和测试环境可能存在差异（分布外泛化）。需要学习更鲁棒、更抽象的特征。

10.3 可解释性

深度 RL 的策略往往是黑箱，难以理解其决策过程。研究可解释的 RL 模型有助于安全部署。

10.4 计算资源

训练大规模深度 RL 模型需要大量算力，推动分布式训练和硬件优化。

11. 概念关系图

graph TD A[RL前沿] --> B[部分可观测] A --> C[分层RL] A --> D[内在动机] A --> E["迁移/多任务"] A --> F[多智能体] A --> G[基于模型] A --> H["安全/鲁棒"] A --> I[与神经科学结合] A --> J[深度RL挑战] B --> B1[POMDP] B --> B2[信念状态] B --> B3[近似方法] C --> C1[选项] C --> C2[分层价值函数] D --> D1[好奇心] D --> D2["计数/伪计数"] E --> E1[迁移学习] E --> E2[元学习] F --> F1["合作/竞争"] F --> F2[CTDE] G --> G1[Dyna] G --> G2[MPC] H --> H1[约束MDP] H --> H2[离线RL] I --> I1[多巴胺模型] I --> I2[认知架构] J --> J1[样本效率] J --> J2[泛化] J --> J3[可解释性]

12. 与前后的联系

  • 前几章 提供了 RL 的基础（MDP、DP、MC、TD、函数近似、策略梯度等），本章在这些基础上展望未来发展方向。
  • 第14-15章 讨论了心理学和神经科学的联系，本章则将其融入前沿主题，体现跨学科融合。
  • 第16章 的应用案例展示了 RL 的现有能力，而本章则探讨如何突破这些能力的局限。

13. 核心要点总结

  1. POMDP：处理现实中的部分可观测问题，信念状态和近似方法是关键。
  2. 分层 RL：通过时间抽象加速学习，选项框架是重要基础。
  3. 内在动机：在稀疏奖励中引导探索，好奇心、信息增益是常见方法。
  4. 迁移/多任务学习：利用已有知识加速新任务学习，元学习是高级形式。
  5. 多智能体 RL：处理多个交互的智能体，CTDE 是主流框架。
  6. 基于模型的 RL：通过学习环境模型提高样本效率，需处理模型偏差。
  7. 安全与鲁棒性：约束优化和离线学习是确保安全的重要手段。
  8. 与神经科学结合：双向启发推动更类人的智能。
  9. 深度 RL 挑战：样本效率、泛化、可解释性是当前热点。

14. 常见难点与学习建议

难点1：理解 POMDP 的信念状态

  • 信念状态是概率分布，其更新依赖于贝叶斯滤波。建议先复习隐马尔可夫模型（HMM），再扩展到 POMDP。

难点2：选项的层级学习

  • 如何同时学习高层策略和底层选项？需理解分层价值函数的分解和更新。可阅读 Sutton 等人的原始论文。

难点3：多智能体的非平稳性

  • 每个智能体的策略变化使环境对其他智能体非平稳，这破坏了马尔可夫性质。CTDE 通过集中训练缓解，但仍有挑战。

学习建议

  1. 阅读原始文献：每个方向都有奠基性论文，选择感兴趣的主题深入研读。
  2. 动手实现：尝试用现有库（如 OpenAI Gym、PyMARL）实现简单版本的前沿算法（如选项学习、MADDPG）。
  3. 关注最新进展：顶级会议（NeurIPS、ICML、ICLR）每年都有大量前沿工作，保持关注。
  4. 跨学科思考：将 RL 与其他领域（认知科学、机器人、经济学）结合，寻找创新点。

本章描绘了强化学习研究的广阔图景，展示了从理论到应用再到未来的无限可能。掌握这些前沿方向，将为你在学术或工业界开展 RL 研究打下坚实基础。