16.1 任务与奖励

强化学习 (Reinforcement Learning, RL) 讨论的是智能体 (agent) 如何在复杂、不确定的环境 (environment) 中通过学习来最大化它能获得的累积奖励。

从监督学习到强化学习：一个宏观的理解

在我们深入技术细节之前，先从你熟悉的监督学习出发，建立一个对强化学习的宏观认识。这对于理解其核心思想至关重要。

监督学习和强化学习的异同：

• 相似点：两者都在学习一个“映射”。监督学习学习从“特征”到“标签”的映射，而强化学习学习从“环境状态”到“最优动作”的映射。从这个角度看，强化学习中的策略 (policy) 就好比是监督学习中的分类器或回归器。
• 核心区别：在于反馈机制。
  • 监督学习：拥有明确的、即时的“标签” (ground-truth)。模型做出预测后，可以立即通过损失函数计算与真实标签的差距，然后直接优化。这就像一个学生做练习题，每道题都有标准答案。
  • 强化学习：没有现成的“正确答案”。智能体必须先做出一个动作，然后从环境中获得一个反馈信号（奖赏）。这个奖赏往往是延迟的 (delayed)，甚至是稀疏的 (sparse)。比如下围棋，可能要到几十步甚至最终棋局结束时，才能知道最初的几步是好是坏。这就是所谓的**“延迟标记信息”。智能体必须通过“事后反思”来判断之前的哪一步动作对最终结果贡献最大，这个过程也叫做“信用分配” (Credit Assignment) 问题**。

总而言之，如果说监督学习是“模仿式学习”，那么强化学习就是**“试错式学习” (Trial-and-Error Learning)**。

---

马尔可夫决策过程 (MDP)

强化学习任务通常使用马尔可夫决策过程 (Markov Decision Process, MDP) 作为数学框架来描述。它之所以重要，是因为它提供了一套形式化的语言来描述智能体与环境的交互过程。

图 16.1 讲解:
这张图展示了强化学习的基本交互循环。

1. 在 $t$ 时刻，智能体观测到当前状态 $x_t$。
2. 基于状态 $x_t$，智能体的策略 $\pi$ 决定执行一个动作 $a_t$。
3. 环境接收到动作 $a_t$ 后，会转移到一个新的状态 $x_{t+1}$，并反馈给智能体一个即时奖赏 $r_{t+1}$。
   这个 “状态-动作-奖赏” 的循环不断持续，智能体的目标就是通过调整其策略 $\pi$ 来最大化未来的累积奖赏。

一个 MDP 由一个四元组 $E=(X,A,P,R)$ 定义：

• $X$: 状态空间 (State Space)，包含了智能体可能感知到的所有环境状态的集合。
  • 为什么用 $X$? 这是数学上的惯例。在机器学习和数学中，通常用大写字母如 $X,Y,Z$ 来表示一个集合或空间。这里的 $X$ 代表状态 (State) 的全集。
• $A$: 动作空间 (Action Space)，包含了智能体可以采取的所有动作的集合。
• $P$: 状态转移函数 (State Transition Function)，$P:X\times A\times X\mapsto [0,1]$。它定义了环境的动态。$P(x^{\prime }|x,a)$ 表示在状态 $x$ 下执行动作 $a$ 后，环境随机转移到状态 $x^{\prime }$ 的概率。
  • 为什么用 $\times$ (乘号)？ 这里的 $\times$ 不是乘法，而是数学中表示 “笛卡尔积” (Cartesian Product) 的符号。$X\times A\times X$ 表示这个函数 $P$ 的“输入域” (domain)。它说明 $P$ 接受一个组合作为输入，这个组合是一个元组 (tuple) (状态, 动作, 下一个状态)，例如 $(x,a,x^{\prime })$。然后 $P$ 会为这个特定的组合输出一个概率值。
  • $x^{\prime }$ 是可以计算出来的吗？ 这是一个关键区别。在图 16.2 所示的随机 (stochastic) 环境中，我们不能“计算”出（即 100% 确定地预测）下一个状态 $x^{\prime }$ 将是什么。我们能“计算”的是转移到任何一个特定 $x^{\prime }$ 的概率。
  • 例如：在“健康”状态下执行“不浇水”动作，我们无法计算出 $x^{\prime }$ 就是 “缺水”。我们只能计算出 $x^{\prime }$ 有 $p=0.5$ 的概率是“缺水”，有 $p=0.5$ 的概率是“健康”。
  • 因此，$x^{\prime }$ 本身是环境随机过程的一个结果 (outcome)，而 $P(x^{\prime }|x,a)$（即这个结果发生的概率）才是模型 $P$ 允许我们“计算”或（在“有模型”学习中）“查询”到的东西。
  • 图 16.2 中的概率 § 是怎么来的？ 在这个例子中，这些概率是预先定义好的模型的一部分。我们假设我们对这个“西瓜生长”环境有充分的了解，知道浇水/不浇水后它会以怎样的概率变化。这属于 “有模型” (Model-based) 学习 的范畴，即环境的动态模型 ($P$ 和 $R$) 是已知的。在更多实际情况中，这个模型是未知的（即 “免模型” learning），智能体必须通过与环境的大量交互来估计它。
• $R$: 奖赏函数 (Reward Function)，$R:X\times A\times X\mapsto \mathbb{R}$。它定义了智能体的目标。$R(x,a,x^{\prime })$ 表示在状态 $x$ 执行动作 $a$ 并转移到 $x^{\prime }$ 后，智能体能获得的即时奖赏 (immediate reward)。
  • 为什么映射到 $\mathbb{R}$? $\mathbb{R}$ 代表实数集。奖赏可以是一个正数（奖励）、负数（惩罚）或零。

![图 16.2: 给西瓜浇水的马尔可夫决策过程](配图/图16-2.png)

图 16.2 讲解:
这是一个具体的 MDP 示例，将抽象概念具象化。

• 状态 (s): 共有 4 个状态：{健康, 缺水, 溢水, 凋亡}。
• 动作 (a): 共有 2 个动作：{浇水, 不浇水}。
• 转移概率 §: 定义了环境的不确定性。例如，即使在 “健康” 状态下 “浇水”，也不能 100% 保证继续健康，存在 $p=0.4$ 的概率会变为 “溢水”。
• 奖赏 ®: 提供了即时反馈。保持健康有正奖赏，进入不良状态有负奖赏，最终 “凋亡” 获得一个巨大的负奖赏，这强烈地指导智能体要避免这个结局。
• 终止状态: “凋亡” 是一个终止状态 (terminal state)。

• 这个例子和 MDP 是怎么来的？是人为建模的吗？ 是的。图 16.2 是一个人为建模的、简化的环境模型。我们作为设计者，假设我们完全理解西瓜生长的所有规则（即状态转移概率 $P$）以及每种结果的好坏（即奖赏函数 $R$）。

• MDP 的局限性和环境建模的难度：
  • MDP 最大的局限性在于它假设我们已知完美的环境模型（即 $P$ 和 $R$）。
    • 在现实中，这几乎是不可能的。 比如，在自动驾驶中，我们无法建立一个完美的数学模型来描述“在路口左转，撞上行人的概率是 0.01%”。
    • 环境建模（即找出 $P$ 和 $R$）是极其困难的。 这就是为什么强化学习分为两大流派：
      1. 有模型学习 (Model-based)：先尝试学习环境模型 $P$ 和 $R$（这本身就很难），然后再利用这个模型来计算最优策略。（图 16.2 的例子就是“有模型”的前提）
      2. 免模型学习 (Model-free)：放弃对环境建模。智能体不去管 $P$ 和 $R$ 到底长什么样，它只管在环境中大量“试错”，直接根据获得的经验（即 (状态, 动作, 奖赏, 下一状态) 四元组）来逐步优化自己的策略 $\pi$。
    • 免模型学习（如 Q-Learning, Policy Gradient）是目前应用更广泛的方法，因为它绕过了“环境建模”这个难题。

---

策略 (Policy)

策略 ($\pi$) 是智能体的“大脑”，它决定了智能体在某个状态下应该采取什么动作。策略是强化学习算法最终要学习到的东西。

• 策略 ($\pi$) 是怎么来的？它是不是 RL 训练的对象？
• 1. 策略是训练的核心对象：策略 $\pi$ 就是强化学习要“训练”和“优化”的那个东西。在深度强化学习中，这个策略 $\pi$ 通常就是一个神经网络。
• 2. 它如何开始：在训练刚开始时，这个策略（神经网络）是随机初始化的。它完全不知道在什么状态该做什么动作，所以它的行为就像“瞎蒙”。
• 3. 它如何更新：智能体使用这个随机策略去和环境交互，收集了大量经验（即历史奖赏）。然后，它会“反思”这些经验：
  • “哦，上次我在状态 $x$ 做了动作 $a$，结果导致我后来拿到了很高的累积奖赏，那么我下次再遇到 $x$ 时，选择 $a$ 的概率就应该提高一点。”
  • “反之，如果一个动作导致了很差的后果（比如‘凋亡’），我就要降低这个动作的概率。”
• 4. 最终目标：通过不断的“试错-反馈-更新”，策略 $\pi$ 被逐步优化，最终收敛到一个能使其长期累积奖赏最大化的（近似）最优策略。

1. 确定性策略 (Deterministic Policy): $\pi :X\mapsto A$。对于任意状态 $x$，策略都给出一个确定的动作 $a$。
2. 随机性策略 (Stochastic Policy): $\pi :X\times A\mapsto [0,1]$。$\pi (a|x)$ 表示在状态 $x$ 时，选择动作 $a$ 的概率。

   • 为什么定义里写 $\mapsto \mathbb{R}$ (实数)，但又说是概率？ 从严谨的数学定义上，函数输出的值域是实数集 $\mathbb{R}$，但我们额外增加了一个约束条件：对于同一个状态 $x$ 下的所有动作 $a$，其概率之和必须为 1，即 ${\sum }_{a\in A}\pi (a|x)=1$。同时，每个概率值都在 $[0,1]$ 区间内。满足这些条件的实数就是概率。所以，虽然它输出的是实数，但这些实数必须符合概率的定义。

---

累积奖赏 (Cumulative Reward)

一个好的策略不能只看重眼前的即时奖赏，而应该追求长期的回报。因此，我们用累积奖赏来评估一个策略的好坏。

这个奖赏（Reward）是怎么来的？也是人为设计的吗？

• 是的，奖赏函数 $R$（即时奖赏）是人为设计的，它是整个强化学习问题的 “规则制定者”。
• 1. $R$ 是人为设计的：设计 $R$ 的过程叫做 “奖赏工程” (Reward Engineering)。它告诉智能体“什么是好的，什么是坏的”。比如在西瓜例子中，我们规定“保持健康”奖赏 $r=+1$，“凋亡”奖赏 $r=-100$。
• 2. $R$ 在训练中固定不变：一旦设计好，$R$ 就代表了任务的目标，在整个训练过程中是固定不变的。如果它变了，那任务本身就变了。
• 3. $R$ 是训练策略的核心驱动力：
  • 我们人为设计了（固定的）即时奖赏 $R$。
  • 由此推导出了（固定的）累积奖赏目标（例如 $\gamma$ 折扣累积奖赏）。
  • 策略 $\pi$ 的全部训练目标，就是最大化这个固定的累积奖赏的期望值。
  • 因此，奖赏函数 $R$ 的设计至关重要，如果 $R$ 设计得不好（比如，你只奖励“浇水”这个动作，而不关心西瓜的状态），智能体就会学到一个很荒谬的策略（比如疯狂浇水直到“溢水”）。

1. $T$ 步累积奖赏:
   $$\mathbb{E}\left[\frac{1}{T}\sum _{t=1}^T{r}_t\right]$$

   • $r_t$ 是什么？ $r_t$ 是智能体在第 $t$ 步获得的即时奖赏。
   • 公式解读: 这个公式计算的是在有限的 $T$ 步内，智能体能获得的平均奖赏。${\sum }_{t=1}^T{r}_t$ 是把这 $T$ 步的所有即时奖赏加起来，除以 $T$ 就是求平均。$\mathbb{E}[\cdot ]$ 表示求期望，因为策略和环境状态转移都可能是随机的，所以累积奖赏是一个随机变量，我们关心的是它的期望值。这种评估方式适用于一些有明确固定时长的任务。

2. $\gamma$ 折扣累积奖赏:
   $$\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{r}_{t+1}\right]$$

   • 公式解读: 这个公式用于评估无限时长的任务。它将未来每一步的奖赏 $r_{t+1}$ 乘以一个折扣因子 (discount factor) ${\gamma }^t$。
   • $\gamma \in [0,1)$:
     • 这确保了即使是无限步数的奖赏加和，结果也会收敛为一个有限值。
     • 这也符合经济学直觉：未来的奖励不如眼前的奖励有价值。$\gamma$ 越接近 1，说明智能体越有“远见”，对未来的奖赏越重视；$\gamma$ 越接近 0，则智能体越“短视”，更关心即时回报。

---

16.2 K-臂老虎机

在深入研究完整的多步 (multi-step) 强化学习问题（如 MDP）之前，我们先从一个简化的情况入手：K-臂老虎机 (K-armed bandit)。

![图 16.3：K-臂老虎机图示](配图/图16-3.png)

K-臂老虎机是一个 “单步强化学习任务” (single-step reinforcement learning task)。它被用来研究强化学习中的一个核心挑战：“探索与利用” (Exploration vs. Exploitation) 的窘境。

• K-臂老虎机: 如图 16.3 所示，想象有一台有 $K$ 个摇臂的老虎机（也叫赌博机）。
• 动作 (Action): 在每一步，智能体（赌徒）选择一个摇臂 $k$ 按下。
• 奖赏 (Reward): 智能体立即获得一个奖赏 $v$。
• 不确定性: 每个摇臂 $k$ 的奖赏 $v$ 并不是一个固定值，而是服从一个未知的概率分布。智能体只能通过多次尝试来估计每个摇臂的平均奖赏（期望奖赏）。
• 目标: 在有限的 $T$ 次尝试中，最大化累积奖赏。

K-臂老虎机和完整的 MDP (马尔可夫决策过程) 有什么区别？

1. 步数: K-臂老虎机是单步的。你做出一个动作（选摇臂），立刻得到奖赏，任务结束。MDP 是多步的，动作会引发状态转移，奖赏往往是延迟的 (delayed)。
2. 状态 (State): K-臂老虎机问题没有“状态”的概念（或者说，它只有一个永不改变的单一状态）。无论你之前做了什么，你都面临着同样的 $K$ 个摇臂。而在 MDP 中，你的动作会带你进入新的状态。

简而言之，K-臂老虎机是 MDP 的一个特例，它剥离了所有复杂性（如状态转移、延迟奖赏），只保留了“在不确定性中选择最优动作”这一个核心问题，因此它是研究**“探索-利用窘境”**的最佳模型。

---

16.2.1 探索与利用

为了最大化累积奖赏，我们显然希望“利用”我们已知的最好的摇臂。但问题是，我们如何知道哪个是最好的？我们对每个摇臂 $k$ 期望奖赏的估计 $Q(k)$ 只是一个近似值。

这就引出了著名的 “探索-利用窘境” (Exploration-Exploitation Dilemma)：

• 利用 (Exploitation): 选择当前（根据已有经验）估算出的期望奖赏最高的摇臂。
  • 好处: 立刻获得（当前看来）最好的回报。
  • 风险: 如果当前的估计不准，你可能会永远错过那个真正最好的摇臂，导致最终的累积奖赏并非最大化。
• 探索 (Exploration): 选择一个当前估计并非最优的摇臂。
  • 好处: 获得更多关于这个摇臂的信息，从而更新对它的奖赏估计 $Q(k)$，未来有可能发现它才是“最优摇臂”。
  • 风险: 浪费了一次本可以“利用”已知最优摇臂的机会，导致即时奖赏受损。

两种极端的策略：

1. “仅探索” (Exploration-only) 策略: 将所有的 $T$ 次尝试平均分配给 $K$ 个摇臂。
   • 结果: 这种策略可以很好地估计出每个摇臂的期望奖赏，但它在“探索”上花费了太多精力。它会明知某些摇臂很差，却依然要继续尝试，因此无法最大化累积奖赏。
2. “仅利用” (Exploitation-only) 策略: 尝试每个摇臂一次（或几次），然后“锁定”那个当前看起来最好的摇臂，之后永远只选它。
   • 结果: 如果最初的估计有偏差（几乎必然如此），这个策略很可能会“短视”地锁定在一个非最优的摇臂上，导致无法最大化累积奖赏。

结论：强化学习智能体必须在探索和利用之间达成折中 (trade-off)。

---

16.2.2 $ϵ$-贪心

$ϵ$-贪心法 ($ϵ$-greedy) 是平衡探索与利用的最简单、最常用的策略之一。

核心思想：
设置一个 [0, 1] 之间的小数 $ϵ$（例如 0.1）。

• 以 $1-ϵ$ 的概率进行利用 (Exploitation)：
  • 选择当前估计的平均奖赏 $Q(k)$ 最高的那个摇臂 $k$（即 $k=\arg {\max }_{i}Q(i)$）。
• 以 $ϵ$ 的概率进行探索 (Exploitation)：
  • 在所有 $K$ 个摇臂中随机选择一个。

$ϵ$ 是什么？它如何控制这个平衡？

• $ϵ$ (epsilon) 是 “探索率” (Exploration Rate)。
• 若 $ϵ=0$，则算法变为“仅利用” (Exploitation-only) 策略。
• 若 $ϵ=1$，则算法变为“仅探索” (Exploitation-only) 策略（纯随机选择）。
• 通常 $ϵ$ 是一个接近 0 的小值（如 0.1 或 0.01），确保算法以 “贪心”（即利用）为主，但保留一小部分机会去探索其他可能性。

奖赏的增量计算

为了执行 $ϵ$-贪心法，我们需要一种方法来高效地估计每个摇臂 $k$ 的平均奖赏 $Q(k)$。

如果我们直接使用

$Q(k)=\frac{1}{n}{\sum }_{i=1}^n{v}_i$，（公式 16.1）

就需要记录摇臂 $k$ 获得的所有历史奖赏 $v_1,\dots ,v_n$，这在尝试次数 $n$ 很大时效率低下。

因此，我们使用 增量式 (incremental) 计算：
假设摇臂 $k$ 已被尝试了 $n-1$ 次，平均奖赏为 $Q_{n-1}(k)$。当它第 $n$ 次被尝试，获得了新奖赏 $v_n$ 后，新的平均奖赏 $Q_n(k)$ 可以更新为：

$$\begin{array}{rl}{Q}_n(k)& =\frac{1}{n}\sum _{i=1}^n{v}_i\\ & =\frac{1}{n}\left(v_n+\sum _{i=1}^{n-1}{v}_i\right)\\ & =\frac{1}{n}(v_n+(n-1)\times Q_{n-1}(k))\end{array}$$(16.2)

公式 (16.2) 的讲解:

这个公式非常高效。它告诉我们，不需要存储摇臂 $k$ 过去所有的 $v_1,\dots ,v_n$ 奖赏值。我们只需要记住两个值：

1. 旧的平均值 $Q_{n-1}(k)$
2. 旧的计数值 $n-1$

当新的奖赏 $v_n$ 到来时，我们用 $(n-1)\times Q_{n-1}(k)$ 瞬时恢复出“过去的奖赏总和”，加上 $v_n$ 得到“新的奖赏总和”，再除以“新的计数值” $n$，就得到了新的平均值 $Q_n(k)$。这正是教材 (原西瓜书 图 16.4 $ϵ$-贪心算法，对应下方笔记中 图 16.4 伪代码的第 22 行) 伪代码中第 11 行 Q(k) = (Q(k) * count(k) + v) / (count(k) + 1) 的数学原理（伪代码中的 Q(k) 和 count(k) 是 $n-1$ 时的旧值）。

将公式 (16.2) 稍作变换，我们可以得到一个在强化学习中更具普遍意义的形式：

$$\begin{array}{rl}{Q}_n(k)& =\frac{1}{n}(v_n+(n-1)Q_{n-1}(k))\\ & =\frac{1}{n}(v_n+n{Q}_{n-1}(k)-Q_{n-1}(k))\\ & =Q_{n-1}(k)+\frac{1}{n}(v_n-Q_{n-1}(k))\end{array}$$(16.3)

公式 (16.3) 的直觉理解 (非常重要!):

这个公式是强化学习中许多更新规则（如 Q-Learning）的原型。我们可以把它解读为：

新估计值 = 旧估计值 + 步长 $\times$ ( 目标值 - 旧估计值 )

• 新估计值: $Q_n(k)$
• 旧估计值: $Q_{n-1}(k)$
• 步长 (Step Size): $\alpha =\frac{1}{n}$。它代表我们这次修正的“幅度”。
• 目标值 (Target): $v_n$。这是我们刚刚观测到的“真实”奖赏（尽管它也只是一个样本）。
• ( 目标值 - 旧估计值 ): $v_n-Q_{n-1}(k)$。这被称为 “误差” (Error) 或 TD-Error (时序差分误差 - Temporal Difference Error) 的雏形。它代表了我们的“估计”与“现实”之间的差距。

解读: 我们的算法在旧的估计 $Q_{n-1}(k)$ 的基础上，朝着“误差” $v_n-Q_{n-1}(k)$ 的方向，迈出了一小步（步长为 $\frac{1}{n}$）来进行修正，从而得到了新的、更准确的估计 $Q_n(k)$。

$ϵ$-贪心算法伪代码

结合教材图 16.4 所示，$ϵ$-贪心算法的流程如下：

输入: 摇臂数量 K, 奖励函数 R, 尝试次数 T, 探索率 $ϵ$
输出: 累积奖赏 r

1:  r = 0                       // 初始化累积奖赏
2:  // 初始化 Q 数组 (存储每个摇臂的平均奖赏估计)
3:  // 初始化 count 数组 (存储每个摇臂被尝试的次数)
4:  $\forall i=1,...,K:Q(i)=0,\text{count}(i)=0$
5:  // $\forall$ 读作"对于所有的", 在这里指初始化循环：
    // 遍历所有 K 个摇臂，把它们的 Q 值和 count 值都设为 0
6:
7:  for t = 1 to T do:          // 循环 T 次
8:      if $\text{rand}()<ϵ$ then:
9:         // 探索：从 K 个摇臂中随机选一个
10:         $k=\text{uniform\_random\_select\_from}(1,...,K)$
11:      else:
12:         // 利用：选择当前 Q 值最高的摇臂
13:         $k={\text{argmax}}_i(Q(i))$
14:      end if
15:      // 执行动作 (拉下摇臂 k)，观测即时奖赏 v
16:      $v=R(k)$
17:      // 更新累积奖赏
18:      $r=r+v$ S
19:      // 更新摇臂 k 的计数值和平均奖赏估计 (使用公式 16.2)
20:      $Q(k)=(Q(k)\times \text{count}(k)+v)/(\text{count}(k)+1)$
21:      $\text{count}(k)=\text{count}(k)+1$
22:
23:  end for

伪代码讲解 (图 16.4)：

1. 输入/输出: 算法需要知道有几个摇臂 $K$、总共能试多少次 $T$、探索率 $ϵ$ 以及一个奖励函数 $R$。它的目标是返回最终的累积奖赏 $r$。
   • 关于奖励函数 $R$ 的澄清：$R$ 不是 $ϵ$-贪心算法本身。$R$ 代表的是环境（Environment），或者说问题本身（例如那 $K$ 台老虎机）。
   • $ϵ$-贪心算法是决策者（Agent/Policy），它决定“下一步拉哪根摇臂”。
   • 当算法（在第16行）执行 v = R(k) 时，它是在与环境 $R$ 交互：算法选择动作 $k$（拉第 $k$ 根摇臂），环境 $R$ 根据其内部机制（这个机制对算法是未知的）返回一个即时奖赏 $v$。
   • 因此，$R$ 是算法的输入（算法需要调用它来获取奖赏），而不是算法本身。
2. 初始化 (Lines 1-4): 我们需要“记账本”。r 是总奖赏。Q 数组是我们的“大脑”，记录对每个摇臂的“价值估计”，初始都为0。count 数组记录每个摇臂被拉了多少次，初始也为0。
3. 主循环 (Line 6): 重复 $T$ 次“选择-行动-更新”的循环。
4. 探索/利用决策 (Lines 7-13): 这是 $ϵ$-贪心的核心。
   • if rand() < ε: 产生一个 0 到 1 的随机数。如果它小于 $ϵ$（比如 $ϵ=0.1$ 时，有 10% 的概率发生），则执行“探索”：在 $K$ 个摇臂中随便选一个。
   • else: 在 $1-ϵ$ 的概率下（比如 90% 的概率），执行“利用”：在 Q 数组中找到当前值最大的那个摇臂 $k$。
5. 行动与更新 (Lines 16-23):
   • v = R(k): 拉下选定的摇臂 $k$，环境返回一个奖赏 $v$。
   • r = r + v: 更新总奖赏。
   • Q(k) = ... 和 count(k) = ...: 这是最关键的学习步骤。我们只更新被选中的那个摇臂 $k$ 的记账本。使用公式 (16.2) 的逻辑来更新它的平均奖赏 $Q(k)$，并将其尝试次数 count(k) 加 1。

$ϵ$ 应该如何设置？是固定的吗？

$ϵ$ 是一个超参数，它的设置对算法性能影响很大。

1. 固定 $ϵ$:
   • 如果奖赏的不确定性很大（即概率分布方差很大），则需要较大的 $ϵ$ 来进行更多的探索。
   • 如果奖赏比较确定（方差很小），则较小的 $ϵ$ 就足够了。
2. 衰减 $ϵ$ (Decaying $ϵ$):
   • 一个更优的策略是让 $ϵ$ 随着尝试次数 $t$ 的增加而逐渐减小，例如 ${ϵ}_t=1/\sqrt{t}$。
   • 直觉: 在初期（$t$ 很小），我们对摇臂一无所知，此时 $ϵ$ 较大，算法倾向于探索。随着后期（$t$ 很大）经验的积累，我们的估计 $Q(k)$ 越来越准，此时 $ϵ$ 变小，算法倾向于利用已知的最优摇臂。这完美地平衡了探索和利用。

---

16.2.3 Softmax

$ϵ$-贪心法在“探索”时，是以均等概率从所有 $K$ 个摇臂中随机选择一个。这在某些情况下可能不是最优的，因为它对待一个“估计很差”的摇臂和一个“估计只比当前最优差一点点”的摇臂是完全相同的。

Softmax 算法 提供了另一种更“智能”的思路来平衡探索和利用。它的核心思想是：不再以 $ϵ$ 的概率进行完全随机的探索，而是根据当前对各个摇臂的奖赏估计值 $Q(k)$ 来分配探索的概率。

$Q(k)$ 越高的摇臂，被选中的概率也越高；反之，$Q(k)$ 越低的摇臂，被选中的概率也越低，但仍然有被选中的可能。

这种概率分配是基于 玻尔兹曼分布 (Boltzmann distribution)：

$$P(k)=\frac{e^{\frac{Q(k)}{\tau }}}{{\sum }_{i=1}^K{e}^{\frac{Q(i)}{\tau }}}$$ (16.4)

公式 (16.4) 的直觉理解:

1. $Q(k)$: 摇臂 $k$ 的当前平均奖赏估计。
2. $e^{Q(k)}$ (指数函数): 这是一个关键。指数函数 $e^x$ 能将估计值 $Q(k)$ 映射为正数，并且能放大估计值之间的差异。例如，$Q=2$ 的臂会比 $Q=1$ 的臂获得 $e$ 倍（约 2.718 倍）的“权重”，而不仅仅是 2 倍。
3. ${\sum }_{i=1}^K{e}^{Q(i)/\tau }$ (分母): 这是归一化项。它把所有 $K$ 个摇臂的“权重”全部加起来，用以确保所有摇臂的 $P(k)$ 概率之和为 1。
4. $\tau$ (温度参数): 这是 Softmax 算法的核心超参数，被称为 “温度” (Temperature)，它控制着探索与利用的平衡。

“温度”参数 $\tau$ 是如何控制探索-利用平衡的？

$\tau$ (tau) 是一个大于 0 的正数。

• 当 $\tau \to \infty$ (高温):

  • 数学上: $\tau$ 非常大，导致所有的 $Q(k)/\tau$ 都趋近于 0。
  • 结果: 所有的 $e^{Q(k)/\tau }$ 都趋近于 $e^0=1$。
  • 公式变为: $P(k)\approx \frac{1}{{\sum }_{i=1}^{K}1}=\frac{1}{K}$。
  • 结论: 算法退化为 “仅探索” (Exploration-only) 策略，即在所有摇臂中均匀随机选择（和 $ϵ=1$ 的 $ϵ$-贪心法一样）。

• 当 $\tau \to 0$ (低温 / 冰点):

  • 数学上: $\tau$ 非常小，我们假设 $Q(k^{\ast })$ 是所有 $Q$ 值中最大的那个。此时，$Q(k^{\ast })/\tau$ 会是一个巨大的正数，而其他 $Q(j)/\tau$ (其中 $j\ne k^{\ast }$) 相比之下会是小得多（甚至是巨大的负数）。
  • 结果: $e^{Q(k^{\ast })/\tau }$ 将会远远大于所有其他的 $e^{Q(j)/\tau }$。
  • 公式变为: 分母 $\sum e^{Q(i)/\tau }$ 几乎完全被 $e^{Q(k^{\ast })/\tau }$ 主导。
    • 对于最优臂 $k^{\ast }$: $P(k^{\ast })\approx \frac{e^{Q(k^{\ast })/\tau }}{e^{Q(k^{\ast })/\tau }}\to 1$。
    • 对于其他臂 $j$: $P(j)\approx \frac{e^{Q(j)/\tau }}{e^{Q(k^{\ast })/\tau }}\to 0$。
  • 结论: 算法退化为 “仅利用” (Exploitation-only) 策略，即 100% 确定地选择当前估计值最高的那个摇臂（和 $ϵ=0$ 的 $ϵ$-贪心法一样）。

• 合适的 $\tau$: 当 $\tau$ 取一个中间值时（如 $\tau =0.1$），算法会表现出“Softmax”的特性：$Q$ 值高的臂有很大概率被选中，$Q$ 值低的臂也有小概率被“探索”。

• 衰减 $\tau$: 类似于 $ϵ$ 衰减，$\tau$ 也可以设计为随时间 $t$ 逐渐衰减。初期 $\tau$ 较大（高温），鼓励探索；后期 $\tau$ 变小（降温），鼓励利用。

伪代码讲解 (图 16.5)

Softmax 算法的伪代码（教材图 16.5）在结构上与 $ϵ$-贪心法（图 16.4）几乎完全相同。

输入: 摇臂数量 K, 奖励函数 R, 尝试次数 T, 温度参数 $\tau$
输出: 累积奖赏 r

1:  r = 0
2:  $\forall i=1,...,K:Q(i)=0,\text{count}(i)=0$
3:  for t = 1 to T do:          // 循环 T 次
4:     // 核心区别：
5:     // 1. 根据当前 Q(1)…Q(K) 和 $\tau$, 使用式 (16.4) 计算 K 个概率
6:     //    P(1)…P(K)
7:     // 2. 按照这个概率分布 P, 随机抽样选择一个摇臂 k
8:     k=select_from({1...K}) using Pk = \text{select\_from}(\{1...K\}) \text{ using } Pk=select_from({1...K}) using P
9:
10:    $v=R(k)$                     // 执行动作, 观测奖赏
11:    $r=r+v$                     // 更新累积奖赏
12:    // 后续更新步骤与 $ϵ$-贪心法完全相同
13:    $Q(k)=(Q(k)\times \text{count}(k)+v)/(\text{count}(k)+1)$
14:    $\text{count}(k)=\text{count}(k)+1$
15:  end for

对比 $ϵ$-贪心法：

• 相同点: 初始化 (Lines 1-2)、与环境交互 (v = R(k))、更新累积奖赏 (r = r + v)、更新平均值和计数值 (Lines 13-14) 的逻辑是完全一致的。
• 唯一区别: 仅在于动作选择的策略（Lines 5-8）。
  • $ϵ$-贪心法使用一个 if/else 模块：(1-$ϵ$) 的概率“贪心”选择 $\arg \max Q(k)$，$ϵ$ 的概率“均匀”探索。
  • Softmax 算法则是一个统一的概率框架：它总是在进行“加权探索”，只不过这个“权重”由 $\tau$ 控制，当 $\tau \to 0$ 时，这个“加权探索”就退化为了“贪心利用”。

Softmax 和 $ϵ$-贪心法，哪个更好？

这个问题没有绝对的答案，取决于具体的应用（教材 图 16.6）。

![图 16.6：不同算法在 2-摇臂赌博机上的性能比较](配图/图16-6.png)
教材（图 16.6）中展示了一个 2-臂老虎机实验：

• 臂 1: $P(r=1)=0.4,P(r=0)=0.6$ (期望奖赏 0.4)
• 臂 2: $P(r=1)=0.2,P(r=0)=0.8$ (期望奖赏 0.2)

实验结果 (图 16.6)：

1. “仅探索” (纯随机) 表现最差，平均奖赏收敛到 $(0.4+0.2)/2=0.3$。
2. “仅利用” 表现次差，它很可能在早期因为随机性而锁定了较差的臂 2。
3. $ϵ$-贪心 ($ϵ=0.01$) 因为探索率太低，收敛较慢。
4. $ϵ$-贪心 ($ϵ=0.1$) 和 Softmax ($\tau =0.1$) 在这个特定问题上表现最好，且性能非常接近，都快速收敛到了接近最优臂 1 的期望奖赏（约 0.38-0.39）。

结论：

• $ϵ$-贪心法：实现简单，计算开销极小。
• Softmax 算法：实现略复杂，每一步都需要计算 $K$ 个指数和一次归一化，计算开销稍大。但它的探索策略更“合理”（即更倾向于探索“看起来不错”的臂）。

在很多任务中，两者在调好参数（$ϵ$ 或 $\tau$）后性能相近。

---

16.3 有模型学习

(这部分笔记内容待补充…)
(现在的16.3笔记直接跳过了教材，仅为后续学习 Flow Q-Learning 使用)

在 16.1 中，我们定义了马尔可夫决策过程 (MDP) $E=(X,A,P,R)$。其中 $P$（状态转移函数）和 $R$（奖赏函数）共同构成了环境模型。

有模型学习 (Model-Based Learning) 的核心前提是：我们已知 这个环境模型 $P$ 和 $R$。

这就像我们在玩一个游戏（比如西瓜种植，图 16.2），我们不仅能玩，手上还拿着一本完整的游戏规则说明书（即 $P$ 和 $R$）。这本说明书精确地告诉了我们：

1. 在任何状态 $x$ 下，执行任何动作 $a$，会以什么概率 $P(x^{\prime }|x,a)$ 转移到下一个状态 $x^{\prime }$。
2. 在发生这次转移后，我们会得到多少即时奖赏 $R(x,a,x^{\prime })$。

有模型学习的目标是什么？

既然我们已经知道了全部规则，我们就不再需要“试错” (Trial-and-Error) 了。

我们的任务从“学习” (Learning) 转化为了 “规划” (Planning)。

想象一下，你站在一个迷宫的起点，手上拿着完整的迷宫地图（模型）。你不需要真的去“探索”每一条死路，你可以在起点就利用这张地图，“规划”出一条通往终点的最优路径。

因此，有模型学习的目标是：利用已知的 $P$ 和 $R$，通过计算，直接找出那个能最大化累积奖赏的最优策略 ${\pi }^{\ast }$。

---

16.3.1 核心工具：价值函数与贝尔曼方程

为了“规划”，我们需要一个工具来衡量“一个状态有多好”或“一个动作有多好”。这就是价值函数。

💡 教材定义

在模型已知时, 对任意策略 $\pi$ 能估计出该策略带来的期望累积奖赏。

• 函数 $V^{\pi }(x)$ 表示从状态 $x$ 出发, 使用策略 $\pi$ 所带来的累积奖赏；
• 函数 $Q^{\pi }(x,a)$ 表示从状态 $x$ 出发, 执行动作 $a$ 后再使用策略 $\pi$ 带来的累积奖赏。

这里的 $V(\cdot )$ 称为 “状态价值函数” (state value function), $Q(\cdot )$ 称为 “状态-动作价值函数” (state-action value function), 分别表示指定“状态”上以及指定“状态-动作”上的累积奖赏。

笔记解读：

1. 状态价值函数 (State-Value Function) $V^{\pi }(x)$:

   • 含义：从状态 $x$ 出发，后续一直 采用策略 $\pi$，能获得的 $\gamma$-折扣累积奖赏的期望值。
   • $V^{\pi }(x)$ 衡量的是“状态 $x$ 本身有多好”（在策略 $\pi$ 的指导下）。

2. 状态-动作价值函数 (State-Action-Value Function) $Q^{\pi }(x,a)$:

   • 含义：在状态 $x$ 时，先执行动作 $a$，然后后续再 采用策略 $\pi$，能获得的 $\gamma$-折扣累积奖赏的期望值。
   • $Q^{\pi }(x,a)$ 衡量的是“在状态 $x$ 下执行动作 $a$ 有多好”（在策略 $\pi$ 的指导下）。

Q-Function 就是我们要找的 Q-Learning 里的 Q 吗？

是的！ 这就是 Q-Learning 中“Q”的来源。$Q^{\pi }(x,a)$ 是后续所有免模型学习（包括 FQL）的核心概念。FQL 中的 “Critic” 网络，其目标就是估计这个 $Q$ 函数。

贝尔曼方程 (Bellman Equation)

有了 $P$ 和 $R$，我们就可以推导出价值函数必须满足的一个关键性质，即贝尔曼方程。这个方程是整个强化学习的基石。

它将一个状态的价值 $V^{\pi }(x)$ 与其后续状态的价值 $V^{\pi }(x^{\prime })$ 建立起了递归联系：

$$V^{\pi }(x)=\sum _{a\in A}\pi (a|x)\sum _{x^{\prime }\in X}P(x^{\prime }|x,a)\left(R(x,a,x^{\prime })+\gamma V^{\pi }(x^{\prime })\right)$$ (16.5)

公式 (16.5) 的直觉理解 (非常重要!):

这个公式看起来很吓人，但它只是在做“加权平均”：

“当前状态 $x$ 的价值” = “所有可能的下一步的期望价值”

我们把它拆开看：

1. R(x,a,x') + γV^π(x'): 这是你“单步”的总回报。你先执行 $a$ 转移到 $x^{\prime }$，立即获得奖赏 $R$，然后从 $x^{\prime }$ 开始继续执行策略 $\pi$，获得未来的折扣价值 $\gamma V^{\pi }(x^{\prime })$。
2. ∑_{x' ∈ X} P(x'|x,a) [ ... ]: 这是在求“动作 $a$”的期望价值。因为从 $(x,a)$ 出发，环境是随机的（图 16.2），你可能转移到 $x_1^{\prime }$，也可能转移到 $x_2^{\prime }$。所以你需要用转移概率 $P$ 来加权平均，算出执行动作 $a$ 后所有可能结果的期望回报。这个结果就是 $Q^{\pi }(x,a)$！
3. ∑_{a ∈ A} π(a|x) [ ... ]: 这是在求“状态 $x$”的期望价值。因为在状态 $x$，你的策略 $\pi$ 本身也可能是随机的，你可能选择 $a_1$，也可能选择 $a_2$。所以你必须再用策略概率 $\pi$ 来加权平均，算出在状态 $x$ 下所有可能动作的期望回报。

因此，(16.5) 也可以拆解为两个更简洁的公式：

$$V^{\pi }(x)=\sum _{a\in A}\pi (a|x)Q^{\pi }(x,a)$$ (16.6)
$$Q^{\pi }(x,a)=\sum _{x^{\prime }\in X}P(x^{\prime }|x,a)\left(R(x,a,x^{\prime })+\gamma V^{\pi }(x^{\prime })\right)$$ (16.7)

我们的最终目标是找到最优价值函数 $V^{\ast }(x)$ 和 $Q^{\ast }(x,a)$，它们对应了最优策略 ${\pi }^{\ast }$。最优策略一定是贪心的，它会选择能带来最高 $Q^{\ast }$ 值的动作。因此，贝尔曼方程可以被写成贝尔曼最优方程 (Bellman Optimality Equation)：

$$Q^{\ast }(x,a)=\sum _{x^{\prime }\in X}P(x^{\prime }|x,a)\left(R(x,a,x^{\prime })+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(x^{\prime },a^{\prime })\right)$$ (16.8)

这是 16.4 Q-Learning 算法的理论基石。

---

16.3.2 如何求解？(策略迭代与值迭代)

💡 核心思想：有模型学习 = 动态规划 (无泛化)

“在模型已知时，强化学习任务能归结为基于动态规划的寻优问题。与监督学习不同，这里并未涉及到泛化能力，而是为每一个状态找到最好的动作。”

这句话是理解“有模型学习”的关键，我们来拆解一下：

1. “…归结为基于动态规划 (Dynamic Programming, DP) 的寻优问题”

   • 什么是动态规划？ 动态规划的核心思想是将一个大问题分解为一堆相关的“子问题”，通过求解所有子问题，最终得到大问题的解。

   • 它和强化学习 (RL) 有什么关系？

   • 我们在 16.3.1 中推导出的贝尔曼方程 (Bellman Equation) 就是一个完美的 DP 结构！

   • 大问题：求解状态 $x$ 的最优价值 $V^{\ast }(x)$。

   • 子问题：求解 $x$ 的所有“下一步”状态 $x^{\prime }$ 的最优价值 $V^{\ast }(x^{\prime })$。

   • 贝尔曼方程 $V(x)=\cdots \sum P(\dots (R+\gamma V(x^{\prime })))$ 告诉我们，一个状态的价值可以由其后续状态的价值来递归定义。

   • 因此，我们接下来要讲的 “策略迭代” 和 “值迭代”，它们本质上就是两种经典的动态规划算法，用来迭代求解这个递归的贝尔曼方程。

2. “…与监督学习不同，这里并未涉及到泛化能力…”

   • 这是有模型 DP 算法与神经网络（如 DQN）最根本的区别。

   • 监督学习（例如图像分类）：你用 6 万张手写数字图片（训练集）去训练一个神经网络。你的目标是让这个网络在 1 万张它从未见过的图片（测试集）上也能表现良好。这就是 “泛化” (Generalization)。

   • 有模型 DP 算法（例如值迭代）：想象一个 4x4 的格子世界 (Grid World)，总共有 16 个状态。我们的算法会计算并存储一个 4x4 的表格 (Table)，精确地记录每一个格子的价值（比如 $V(1,1)=0.8,V(1,2)=0.9,\dots$）。

   • 这个算法没有“泛化”可言。它不知道 $V(1,1)$ 和 $V(1,2)$ 在“概念上”是邻居。它只是为 16 个离散的状态，计算出了 16 个精确的数值。如果你把世界改成 5x5，这个 4x4 的表格就完全没用了，必须从头重算。

3. “…而是为每一个状态找到最好的动作。”

   • 这承接了上一点。因为我们为每一个状态 $x$ 都计算出了精确的 $V^{\ast }(x)$ 或 $Q^{\ast }(x,a)$，所以我们的最优策略 ${\pi }^{\ast }$ 也是一个**“查找表” (Lookup Table)**。

   • 例如，在 4x4 格子世界中，最终的策略 ${\pi }^{\ast }$ 会是这样一个表格：

   • 在状态 $(1,1)$，执行 $\to$

   • 在状态 $(1,2)$，执行 $\to$

   • 在状态 $(1,3)$，执行 $\uparrow$

   • …

   • 我们为每一个状态都找到了一个确定的“最优解”。这是一种 “规划” (Planning)，而不是像监督学习那样的“泛化” (Generalization)。

有了模型 $P,R$ 和贝尔曼方程，求解最优策略 ${\pi }^{\ast }$ 就变成了纯粹的计算问题。主要有两种算法：

1. 策略迭代 (Policy Iteration):

   • 思路：像“演员”和“评论家”一样交替工作。
   • 步骤:
     1. 策略评估 (Policy Evaluation)：固定当前策略 ${\pi }_k$。利用已知的 $P,R$ 和公式 (16.5)，解一个N元一次方程组（N是状态总数），计算出当前策略下所有状态的真实价值 $V^{{\pi }_k}(x)$。
     2. 策略改进 (Policy Improvement)：根据 $V^{{\pi }_k}(x)$，更新策略。对于每个状态 $x$，都贪心地选择那个能导向最高未来价值的动作 $a$，形成新策略 ${\pi }_{k+1}$。
     3. 循环: 重复 1 和 2，直到策略 $\pi$ 不再变化，此时的 $\pi$ 就是最优策略 ${\pi }^{\ast }$。

2. 值迭代 (Value Iteration):

   • 思路：更直接，不关心中间的策略，只专注于迭代计算出最优价值 $V^{\ast }(x)$。
   • 步骤:
     1. 初始化一个随意的 $V_0(x)$（比如全为0）。
     2. 迭代更新: 不断地用贝尔曼最优方程 (16.8) 的逻辑作为更新规则，迭代 $k$ 次：
        $$V_{k+1}(x)\leftarrow \underset{a}{\max }\sum _{x^{\prime }\in X}P(x^{\prime }|x,a)\left(R(x,a,x^{\prime })+\gamma V_k(x^{\prime })\right)$$ (16.9)
     3. 循环: 重复步骤 2，直到 $V_k(x)$ 收敛不再变化。此时的 $V_k$ 就是 $V^{\ast }$。
     4. 提取策略: 一旦有了 $V^{\ast }$，最优策略 ${\pi }^{\ast }$ 也就随之确定了：在任何状态 $x$，选择那个能最大化 (16.9) 右侧的动作 $a$ 即可。

小结

• 有模型学习的本质是：利用已知的模型 ($P$ 和 $R$)，通过动态规划（如值迭代），为所有已知的、离散的状态 $x$ 计算出一个精确的最优价值 $V^{\ast }(x)$，并导出一个“查找表”式的最优策略 ${\pi }^{\ast }$。

• 这为我们引出了 16.3.3 的“诅咒”： 如果状态空间 $X$ 不是 4x4 这种小表格，而是像自动驾驶的“图像”那样连续且无限的，这种“为每一个状态计算”的 DP 方法就彻底失效了。这也正是 16.5 值函数近似 (用神经网络来近似 $V(x)$) 必须被提出的原因。

---

16.3.3 “模型的诅咒”：为什么有模型学习不够用？

读到这里，你可能会想：既然有模型学习可以通过“规划”直接算出最优解，为什么我们还要费劲去学“免模型”呢？

这就是 “模型的诅咒” (Curse of the Model)，也是我们必须转向 16.4 的核心原因。有模型学习在现实中几乎不可行，因为它依赖两个致命的假设：

1. 假设一：我们已知 $P$ 和 $R$。

   • 现实是：我们几乎永远不知道完美的环境模型。我们无法写出一个函数 $P$，来精确计算“在自动驾驶时，方向盘左转5度，下一帧图像是 $x^{\prime }$ 的概率”。
   • 对策？：我们可以尝试去“学习”模型 $P$ 和 $R$。但这本身就是一个极其困难的监督学习问题，甚至比直接学习策略更难。

2. 假设二：我们的状态空间 $X$ 是有限且足够小的。

   • 现实是：策略迭代和值迭代都要求我们能遍历 (iterate) 状态空间中的每一个状态 $x$。
   • 诅咒：在现实任务中，状态空间 $X$ 往往是天文数字。
     • 围棋的状态空间 $\approx 10^{170}$。
     • 自动驾驶的状态 $x$ 是一张摄像头图像，状态空间 $X$ 是所有可能的图像，这是一个连续且无限的空间。
   • 当状态空间巨大或连续时，你根本无法执行 $V(x)\leftarrow \dots$ 这样的更新，因为你连存储所有 $V(x)$ 的表格都做不到。

这为我们后续的学习铺平了道路：

1. ## 16.4 免模型学习 (如 Q-Learning) 就是为了解决假设一。它提出了一种天才般的思路：我们能不能不依赖 $P$ 和 $R$，仅仅通过“试错”收集的样本 (x, a, r, x')，就直接估计出最优的 $Q^{\ast }(x,a)$？

2. ## 16.5 值函数近似 就是为了解决假设二。它提出：既然我们存不下 $Q(x,a)$ 这张大表，我们能不能用一个神经网络 $Q_{\theta }(x,a)$ 来近似它？

   • 这正是你 Flow Q-Learning 学习路线.md 中提到的 Critic (评论家) / 价值网络 (Q网络)。
   • 这也正是你的 FQL 论文中，Actor-Critic 框架里的那个 Critic。

现在，我们已经初步准备好进入 16.4，去探究 Q-Learning 是如何巧妙地绕过“模型”这个大山的。

---

16.4 免模型学习

在 16.3.3 中，我们讨论了“模型的诅咒” (Curse of the Model)，指出了“有模型学习” (Model-Based Learning) 的两个致命假设：

1. 我们必须已知完美的环境模型 $P$ (状态转移函数) 和 $R$ (奖赏函数)。
2. 状态空间 $X$ 必须是有限且足够小的，以便我们能用动态规划 (DP) 遍历所有状态。

在绝大多数现实任务中，这两个假设都不成立。我们几乎永远无法获知环境的精确模型 $P$ 和 $R$。

因此，我们必须转向 “免模型学习” (Model-Free Learning)。

💡 免模型学习的核心思想

免模型学习算法不依赖环境模型 $P$ 和 $R$。

它放弃了“规划” (Planning)，回归到“试错式学习” (Trial-and-Error)。智能体必须在未知的环境中亲自执行动作，通过采样和观察实际发生的经验——即 (状态, 动作, 奖赏, 下一状态) 四元组——来直接估计价值函数和优化策略。

这也使得免模型学习比有模型学习要困难得多。

---

16.4.1 蒙特卡洛强化学习

蒙特卡洛 (Monte Carlo, MC) 方法 是我们接触的第一种，也是最直观的免模型学习方法。

💡 什么是蒙特卡洛方法？

蒙特卡洛方法的核心思想是 “采样” (Sampling)。当我们无法计算一个量的精确期望值时（例如因为我们不知道 $P$ 和 $R$），我们可以通过大量随机试验，用试验结果的平均值来近似这个期望值。

这就好像我们在 16.2 K-臂老虎机中所做的那样：我们不知道摇臂 $k$ 的期望奖赏 $Q(k)$，但我们可以通过多次拉动它，用观测到的所有奖赏的平均值来估计它。

在强化学习中，我们要估计的是价值函数（即累积奖赏的期望值）。

MC 方法如何估计价值函数？

很简单：让智能体在环境中完整地运行 $N$ 次（$N$ 很大）。每一次从开始到结束称为一条 “轨迹” (Trajectory) 或 “幕” (Episode)。

$$<x_0,a_0,r_1,x_1,a_1,r_2,\dots ,x_T>$$

对于轨迹中出现的每一个状态 $x$（或状态-动作对 $(x,a)$），我们都计算出它在这条轨迹中获得的 “实际”累积奖赏（即“回报”，Return）。然后，我们将 $N$ 次试验中观测到的所有“回报”进行平均，以此作为价值函数的估计值。

免模型学习的困境：V 还是 Q？

在 16.3 有模型学习中，我们既可以学习状态价值函数 $V(x)$，也可以学习状态-动作价值函数 $Q(x,a)$。

但在免模型设定下，只学习 $V(x)$ 是不够的。

• 为什么？ 回想一下，如果我们只有 $V(x)$，我们要如何改进策略？我们需要“贪心”地选择动作，即：
  $$\pi (x)=\arg \underset{a}{\max }\sum _{x^{\prime }\in X}P(x^{\prime }|x,a)\left(R(x,a,x^{\prime })+\gamma V(x^{\prime })\right)$$
  问题：要执行这个 $\arg \max$，我们必须知道 $P$ 和 $R$。但在免模型学习中， $P$ 和 $R$ 是未知的！我们无法“向前看” (lookahead) 来判断哪个动作 $a$ 会导向最好的 $V(x^{\prime })$。

• 解决方案：我们必须直接估计 $Q(x,a)$。

  • $Q(x,a)$ 函数的定义是“在状态 $x$ 执行动作 $a$，后续遵循策略 $\pi$ 的期望累积奖赏”。
  • 它已经把动作 $a$ 的即时后果（即 $P$ 和 $R$ 的作用）“内化” (internalize) 到了 $Q$ 值本身。
  • 一旦我们有了 $Q(x,a)$ 的估计，改进策略就变得非常简单，不再需要 $P$ 和 $R$：
    $$\pi (x)=\arg \underset{a}{\max }Q(x,a)$$

因此，免模型学习的核心目标就是估计 $Q(x,a)$。MC 方法就是通过平均多条轨迹的实际回报来估计 $Q(x,a)$。

探索-利用窘境 (再访)

这里出现了和 K-臂老虎机完全一样的问题：如果我们总是“利用” (Exploitation) 当前最好的 $Q(x,a)$，我们可能会错过那个真正 最优的动作，因为我们从未“探索” (Explore) 过它。

例如，在状态 $x$，我们尝试了动作 $a_1$ 并发现 $Q(x,a_1)=10$。如果我们从此“仅利用”，我们就永远不会去尝试 $a_2$，也就永远不会发现 $Q(x,a_2)$ 可能是 100。

解决方案：和 16.2.2 K-臂老虎机一样，我们必须在策略中引入探索。最简单的方法就是 $ϵ$-贪心法 ($ϵ$-greedy)。

• 以 $1-ϵ$ 的概率进行利用：选择 $\arg {\max }_{a}Q(x,a)$。
• 以 $ϵ$ 的概率进行探索：从所有动作中随机选择一个。

这引出了我们的第一个完整算法：同策略蒙特卡洛学习。

---

同策略蒙特卡洛学习 (On-Policy MC)

“同策略” (On-Policy) 是一个非常关键的术语。

💡 什么是“同策略” (On-Policy)？

它的含义是：我们用来“生成轨迹数据”的策略，与我们正在“评估和改进”的策略，是同一个策略。

在这个算法 (图 16.10) 中：

1. 我们维护一个 $ϵ$-贪心策略 $\pi$。
2. 我们用这个 $\pi$ 去和环境交互，生成轨迹 (line 5)。
3. 我们用生成的轨迹来更新 $\pi$ 自己的 $Q$ 值 (line 17-18)。
4. 我们用更新后的 $Q$ 值来改进 $\pi$ (line 22)。

从始至终，都只有这一个 $ϵ$-贪心策略 $\pi$ 在自我迭代和更新。

教材 图 16.10 给出了同策略 MC 算法的伪代码，它完美地结合了 K-臂老虎机中的“增量式平均”和 $ϵ$-贪心策略。

1:  $Q(x,a)=0,\text{count}(x,a)=0,\forall x\in X,a\in A$
2:  $\pi (x,a)=1/|A(x)|,\forall x\in X,a\in A$  // 初始化为均匀随机策略
3:  for s = 1, 2, … do:          // 循环每一“幕” (episode)
4:      // 3a. 【生成轨迹】
        // 在环境 E 中, 从 x_0 出发, 执行策略 π，产生1个 episode 的轨迹:
5:      $<x_0,a_0,r_1,x_1,a_1,r_2,...,x_{T-1},a_{T-1},r_T,x_T>$ // $<x_0,a_0,r_1>$ 为1组
6:
7:      // 3b. 【评估策略 (Q值更新)】
8:      $G=0$  // 初始化“未来累积奖赏”(Return)
9:      // 从后向前遍历轨迹 (t = T-1, T-2, …, 0)
10:    for t = T-1 down to 0 do:
11:         // 1. 高效计算累积奖赏
12:         // $G=r_{t+1}+\gamma \times G$
13:         $G=r_{t+1}+\gamma \times G$
14:
15:         // 2. 使用“增量式平均” (公式 16.2) 更新 Q 值
16:         // 将 G 视为 (x_t, a_t) 这对“摇臂”的一次“奖赏”
17:         $Q(x_t,a_t)=\frac{Q(x_t,a_t)\times \text{count}(x_t,a_t)+G}{\text{count}(x_t,a_t)+1}$
18:         $\text{count}(x_t,a_t)=\text{count}(x_t,a_t)+1$
19:     end for
20:
21:     // 3c. 【改进策略 (ε-贪心)】
22:     for x in 所有在轨迹中出现过的状态 x do:
23:         $a^{\ast }=\arg {\max }_{a^{\prime }}Q(x,a^{\prime })$     // 1. 找到“利用”的动作
24:         for a in A(x) do:          // 2. 更新所有动作的概率
25:             if $a==a^{\ast }$ then:
26:                 $\pi (x,a)=1-ϵ+ϵ/|A(x)|$
27:             else:
28:                 $\pi (x,a)=ϵ/|A(x)|$
29:             end if
30:         end for
31:     end for
32: end for

---

伪代码讲解 (图 16.10)：

• Line 1-2 (初始化):

  • Q(x, a) 和 count(x, a) 是什么？
  • 它们不是集合，而是两个巨大的 “查找表” (Lookup Tables)。在实际编程中，你可以把它们想象成两个字典 (Dictionary) 或哈希表 (Hash Map)。
  • Q(x, a)：这个表存储的是“状态-动作对”的价值。它的“键”是 (x, a) 对，“值”是一个数字，代表我们当前对“在状态 $x$ 下执行动作 $a$”的平均累积奖赏的估计。
  • count(x, a)：这是一个并行的“记账本”。它的“键”也是 (x, a) 对，“值”也是一个数字，代表我们总共访问过 (x, a) 这对组合多少次。
  • Line 1 的 $\forall x\in X,a\in A$ 是一个概念上的描述，意思是“这个表格准备好存储所有可能的 (x, a) 组合”。在实际操作中，你不需要（也不可能）
    在一开始就初始化所有 (x, a)。你通常是“惰性” (lazy) 初始化：当你在 Line 17 第一次遇到某个 (x_t, a_t) 组合时，你才在 Q 表和 count 表中创建这个条目，并将其值设为 0。

• x, a, r 和 Q表的关系：

  • 1. x 可以理解为模型每一帧的输入吗？
    • 是的。x 就是智能体在 $t$ 时刻观察到的“环境快照”。
    • 重要限制：在这个“表格型”算法中，x 必须是离散的、可枚举的。比如“格子世界中的 (2, 3) 坐标”或“西瓜的‘健康’状态”。它不能是原始的、高维的图像（比如 [1080, 1920, 3] 的像素矩阵），因为你无法为“每一张可能的图像”都在 Q 表里创建一个条目。
  • 2. a 是每一帧的动作输出吗？
    • 是的。a 就是智能体根据 x 决定执行的动作，比如“向东走”或“浇水”。
  • 3. r 是每一帧的奖励吗？
    • 是的。r_t 是即时奖赏 (immediate reward)。它是你在 $t-1$ 时刻做出动作 $a_{t-1}$ 后，环境在 $t$ 时刻立即反馈给你的“分数”。
  • 4. Q表是不是要记录“每个t对应的x和a，以及其对应的r”？
    • 不，这是最关键的区别！ Q 表不记录 r（即时奖赏）。
    • Q 表记录的是 G（未来累积奖赏）的平均值。
    • Q(x, a) 不是日志 (Log)：它不记录“我在第1幕的第3帧遇到了 (x_1, a_1)，回报是 G=10；在第5幕的第8帧又遇到了 (x_1, a_1)，回报是 G=12”。
    • Q(x, a) 是摘要 (Summary)：它只记录“对于 (x_1, a_1) 这个组合，我总共见过了 count=2 次，它们的回报 G 的平均值现在是 Q=11。”
    • 这就是 Line 17 (Q * count + G) / (count + 1) 的全部意义：它是在更新这个平均值，而不是在“记录”一个新的条目。

• Line 3 (主循环): 算法会不断产生新的轨迹（幕-episode），直到设置的 episode 的上限

• Line 5 (生成轨迹): 这是“同策略”的核心。算法使用它当前的策略 $\pi$（它是一个 $ϵ$-贪心策略）与环境交互，从头（$x_0$）到尾（$x_T$）跑完一整幕，并记录下所有 (x, a, r)。

• Line 8-19 (遍历轨迹与更新Q值): 这是 MC 方法的核心，也是算法实现的关键。

  • for t = T-1 down to 0 和 $G=r_{t+1}+\gamma \times G$ 是如何工作的？
    • 这个 for 循环没有问题，它是一种非常高效的动态规划技巧，用来计算轨迹上每一步的“未来累积奖赏”（也称为 Return）。
    • G 是一个临时累加器，它的值在循环的每一步中都会被覆盖。
    • 我们来一步一步走这个循环 (Line 8-19)，假设 $\gamma =0.9$:
      • Line 8: 循环开始前，G 被初始化为 0。
      • 第 1 轮循环 (t = T-1):
        • t 等于 T-1。
        • Line 13: G = r_{(T-1)+1} + \gamma * G $\to$ G = r_T + 0.9 * 0 $\to$ G = r_T。
        • G 现在的值是 r_T。这个 G 是 (x_{T-1}, a_{T-1}) 这对组合的“回报”。
        • Line 17: 我们更新 Q(x_{T-1}, a_{T-1}) 的值。假设这是我们第一次遇到 (x_{T-1}, a_{T-1})，那么 Q 和 count 都是 0。
          • Q(x_{T-1}, a_{T-1}) = (0 * 0 + G) / (0 + 1) = G (即 r_T)。
        • Line 18: count(x_{T-1}, a_{T-1}) = 0 + 1 = 1。
        • 小结：在 t=T-1 时，我们计算出最后一步的 (x,a) 对的回报是 r_T，并更新了 Q 表：Q(x_{T-1}, a_{T-1}) 的新估计值是 r_T，访问次数是 1。
      • (省略后续循环 t 的推演)
  • 总结：这个反向循环是一个绝妙的技巧。它只用一个变量 G，就在一次遍历中，为轨迹中的每一个 (x_t, a_t) 对都计算出了它对应的正确的未来折扣累积奖赏。

• Line 22-31 (改进策略): 在评估完这一幕轨迹（即用 Line 10-19 更新了 Q 表）之后，我们立刻改进 (Improve) 我们的策略 π。这个过程被称为 “策略改进” (Policy Improvement)。

  • Line 22: for x in 所有在轨迹中出现过的状态 x do:

    • 讲解: 我们只更新那些在本幕 (episode) 中实际访问过的状态 $x$ 所对应的策略。这是一个效率优化，我们不需要去更新那些我们根本没去过的状态的策略。

  • Line 23: a^* = \arg\max_{a'} Q(x, a')

    • 讲解: 这是从“价值函数” (Q 表) 中提取“贪心策略”的核心步骤。我们来拆解这里的所有符号：
    • x 是什么？
      • x 是一个特定的状态，比如在“西瓜”例子中 x = "健康"，或在“格子世界”中 x = (2, 3)。
    • A(x) 是什么？ (Line 24 中会用到)
      • A(x) 是一个集合 (Set)，代表在状态 x 下所有可用的动作 (Action)。
      • 数据结构: {"浇水", "不浇水"} 或者 {"北", "南", "东", "西"}。
      • |A(x)| 是什么？ (Line 26/28 中会用到)
        • |A(x)| 是这个集合的大小 (cardinality)，即一个数字。如果 A(x) = {"北", "南", "东", "西"}，那么 |A(x)| = 4。
    • a' (a-prime) 是什么？
      • a' 是一个迭代变量 (iterator) 或“哑变量”。\arg\max_{a'} 的意思是：“请遍历 A(x) 集合中的每一个动作 a'…”。
    • Q(x, a') 是什么？
      • 这是在查询 (Query) 我们的 Q 表。我们遍历 a'，对每一个 a' \in A(x)，都去 Q 表中查出 (x, a') 这个键 (key) 对应的价值 (value)。
    • a^* (a-star) 是什么？
      • a^* 是 \arg\max 运算的结果。它不是一个数字，而是那个导致 Q(x, a') 值最大的特定动作 (action)。
      • 数据结构: 和 a 一样，是一个动作，比如 "浇水" 或 "东"。
    • 一个具体的例子 (假设 x = (2, 3)):
      1. A(x) 是 {"北", "南", "东", "西"}。
      2. a' 开始遍历。
      3. 查询 Q 表:
         • a' = "北": 查到 Q((2,3), "北") = 10.5
         • a' = "南": 查到 Q((2,3), "南") = -5.1
         • a' = "东": 查到 Q((2,3), "东") = 15.2 (在本幕中刚被更新过)
         • a' = "西": 查到 Q((2,3), "西") = 8.0
      4. \arg\max 比较这些值 (10.5, -5.1, 15.2, 8.0)，发现 15.2 是最大的。
      5. a^* 被赋值为导致 15.2 的那个动作。
      6. 最终结果: a^* = "东"。

  • 一个关键问题: Q(x, a') 和 Q(x_t, a_t) (Line 17) 有何不同？

    • Q(x_t, a_t) (Line 17): 这是一个写操作 (Update)。x_t 和 a_t 是过去时，它们是轨迹中在 t 时刻已经发生的特定状态和动作。我们用 G (回报) 来更新 Q 表中这一个条目。
    • Q(x, a') (Line 23): 这是一个读操作 (Query)。x 是一个给定的状态，a' 是未来时，代表所有可能的动作。我们查询 Q 表中的多个条目，目的是为了决策——找出最好的动作 a^* 是谁。

  • Line 24-31: for a in A(x) do ... end for

    • 讲解: 现在我们已经知道了在状态 x 下最好的动作是 a^* (比如 "东")。接下来的这个循环是去更新策略 π。
    • π(x, a) (pi) 是什么？它和 Q 表是什么关系？
      • π (pi) 就是策略 (Policy)。在“表格型”强化学习中，它也是一个查找表 (Lookup Table)，就像 Q 表一样。
      • Q 表 (价值函数) 存储的是价值（Value）：Q(x, a) 存储一个数字 (比如 15.2)，代表“在 x 做 a 有多好”。
      • π 表 (策略函数) 存储的是概率（Probability）：π(x, a) 存储一个概率 (比如 0.925)，代表“在 x 时，我们有多大概率选择 a”。
      • 关系: π 是根据 Q 计算出来的。Q 表是“事实依据”，π 表是基于这些依据做出的“行动计划”。Line 22-31 的全部工作，就是根据 Q 表的最新事实，来更新 π 表的行动计划。

  • Line 26: $\pi (x,a)=1-ϵ+ϵ/|A(x)|$

  • Line 28: $\pi (x,a)=ϵ/|A(x)|$

    • 讲解: 这两行就是在构建 \epsilon-贪心策略。我们继续用上面的例子：
    • 已知: x = (2, 3), a^* = "东", \epsilon = 0.1, |A(x)| = 4。
    • 计算“探索”概率: \epsilon / |A(x)| = 0.1 / 4 = 0.025。
    • 计算“利用”概率: 1 - \epsilon = 1 - 0.1 = 0.9。
    • for a in A(x) 循环开始:
      • a = "北": a 不等于 a^* ( “北” != “东” )。
        • 执行 Line 28: π((2,3), "北") = 0.025。
      • a = "南": a 不等于 a^* ( “南” != “东” )。
        • 执行 Line 28: π((2,3), "南") = 0.025。
      • a = "东": a 等于 a^* ( “东” == “东” )。
        • 执行 Line 26: π((2,3), "东") = 0.9 + 0.025 = 0.925。
      • a = "西": a 不等于 a^* ( “西” != “东” )。
        • 执行 Line 28: π((2,3), "西") = 0.025。
    • 循环结束。我们更新了 π 表中关于 x = (2, 3) 状态的策略：
      • π((2,3)) 对应的策略现在是：{"北": 0.025, "南": 0.025, "东": 0.925, "西": 0.025}。
      • (检查总和: 0.025 * 3 + 0.925 = 1.0。完美。)
    • 为什么 Line 26 的公式是 1 - \epsilon + \epsilon / |A(x)|？
      • 因为 \epsilon-贪心策略的含义是：
        1. 你有 1 - \epsilon (90%) 的概率去利用（即选择 a^*）。
        2. 你有 \epsilon (10%) 的概率去探索（即在所有 |A(x)| 个动作中均匀随机选择一个）。
      • 这意味着，a^* ( “东” ) 这个动作，它既能从“利用”中分到 1 - \epsilon (90%) 的概率，也能从“探索”中分到 \epsilon / |A(x)| (2.5%) 的概率。所以它的总概率是这两者之和。
      • 而其他所有非最优动作（“北”, “南”, “西”），它们只能从“探索”中分到 \epsilon / |A(x)| (2.5%) 的概率。

• Line 32 (end for): 这一幕 (episode $s$) 结束。我们已经用这一幕的经验，更新了 Q 表（Line 10-19），并基于更新后的 Q 表，更新了 π 表（Line 22-31）。

  • 现在，算法回到 Line 3，开始下一幕 (episode $s+1$) 游戏。

  • 最关键的是，在 Line 5，当它要生成下一条轨迹时，它会使用这个刚刚被微小改进过的新策略 π。这就是“同策略” (On-Policy) 的精髓：策略在“自我迭代”，用自己（$s$ 时刻的 $\pi$）产生的经验，来创造一个更好的自己（$s+1$ 时刻的 $\pi$）。

这个“生成轨迹 $\to$ 评估 $Q$ $\to$ 改进策略 $\pi$”的循环不断重复，最终 Q 表和策略 $\pi$ 将收敛到（近似）最优。

异策略蒙特卡洛学习 (Off-Policy MC)

“同策略” (On-Policy) 算法（如图 16.10）有一个核心限制：它必须在“探索”和“利用”之间进行妥协。它最终学习到的，是一个 $ϵ$-贪心策略，而不是一个最优的（纯贪心）策略。

我们真正想要的，是学习一个确定性的最优策略 $\pi$（即“原始策略”，Original Policy），但为了保证充分探索，我们的“试错”数据（轨迹）又必须来自一个随机性的探索策略 ${\pi }^{\prime }$（如 $ϵ$-贪心策略）。

💡 什么是“异策略” (Off-Policy)？

它的含义是：我们使用一个策略（称为 “行为策略” ${\pi }^{\prime }$，Behavior Policy）来与环境交互、生成轨迹数据；同时，我们利用这些数据来评估和改进另一个策略（称为 “目标策略” $\pi$，Target Policy）。

• 目标策略 $\pi$: 我们真正想学习的策略。在 16.4.1 中，这就是我们想要的那个确定性的、纯贪心的最优策略。
• 行为策略 ${\pi }^{\prime }$: 我们用来探索环境、收集样本的策略。它必须是探索性的（例如 $ϵ$-贪心），以确保能采样到所有可能的 $(x,a)$ 对。

这就带来了一个核心问题：我们如何使用从 ${\pi }^{\prime }$ 获得的“回报” $R$ 来估计 $\pi$ 的 $Q^{\pi }$ 值？这两个策略下，同一个 $(x,a)$ 对的期望回报是不同的。

答案是使用 “重要性采样” (Importance Sampling)。

---

重要性采样 (Importance Sampling)

让我们用一个非常具体的比喻来理解重要性采样。

比喻：估计 A 班的平均分，但你只能抽 B 班的学生

• 你的目标 (Target)：你想知道 A 班（目标策略 $\pi$）学生的平均数学成绩（期望回报 $E_{\pi }[R]$）。
• 你的限制 (Behavior)：你没有 A 班的学生名单。你只能去B 班（行为策略 ${\pi }^{\prime }$）随机抽查学生，问他们的成绩。
• 已知信息：
  • A 班的“学霸”比例是 50%，B 班的“学霸”比例是 10%。
  • A 班的“学渣”比例是 50%，B 班的“学渣”比例是 90%。
  • 学霸的成绩都是 100 分，学渣的成绩都是 50 分。

问题：如果你直接抽 B 班的学生，然后计算他们的平均分，你会得到什么？
你大概率会抽到 9 个学渣和 1 个学霸，平均分 $\approx (9\times 50+1\times 100)/10=55$ 分。
这个 55 分严重低估了 A 班的真实平均分（应该是 $(50\%\times 100+50\%\times 50)=75$ 分）。

重要性采样的作用：
重要性采样提供了一个 “加权” 的方法，来修正这个偏差。
它的核心思想是：“你从 B 班抽到的这个样本，在 A 班有多‘重要’（即多‘稀有’）？”

• 当你从 B 班抽到了一个学渣（50 分）时：

  • 这个学渣在 A 班出现的概率 $p(\text{学渣})=0.5$
  • 这个学渣在 B 班出现的概率 $q(\text{学渣})=0.9$
  • 权重 $\rho =p/q=0.5/0.9\approx 0.56$。
  • 解读：B 班的学渣“太不值钱了”，A 班没那么多学渣。所以我们要给这个 50 分的样本一个更低的权重（小于 1）。

• 当你从 B 班抽到了一个学霸（100 分）时：

  • 这个学霸在 A 班出现的概率 $p(\text{学霸})=0.5$
  • 这个学霸在 B 班出现的概率 $q(\text{学霸})=0.1$
  • 权重 $\rho =p/q=0.5/0.1=5.0$。
  • 解读：B 班的学霸“太稀有了”，在 A 班其实很常见。所以我们要给这个 100 分的样本一个巨大的权重（大于 1）。

现在，我们用这个加权平均来重新计算：
$(1\times \text{学霸的权重}\times 100\text{分}+9\times \text{学渣的权重}\times 50\text{分})/10$
$\approx (1\times 5.0\times 100+9\times 0.56\times 50)/10$
$\approx (500+252)/10=75.2$ 分。
看！这个结果就非常接近 A 班的真实平均分 75 分了。

---

现在，我们来看数学公式：

我们想计算 $E[f(x)]$，其中 $x\sim p$，但我们只能从 $x\sim q$ 采样：

$$\begin{array}{rl}{E}_p[f]& =\int p(x)f(x)dx\\ & =\int q(x)\frac{p(x)}{q(x)}f(x)dx\\ & =E_q\left[\frac{p(x)}{q(x)}f(x)\right]\end{array}$$ (基于 16.23)

公式 (16.23) 拆解：

这个公式是重要性采样的理论核心。它展示了我们如何将一个“无法计算的期望”转变为一个“可以计算的期望”。

• $E_p[f]=\int p(x)f(x)dx$：目标期望值。
  • 这就是我们“想求的平均值”。
  • 积分 $\int$ 在这里是计算连续变量（例如状态是车速、角度）的期望（平均值）的数学定义。
  • 它在概念上等同于 A/B 班比喻中离散情况下的求和 $\sum$。
  • 比喻中：A 班的真实平均分（75 分），即 $E_A[\text{分数}]={\sum }_x{p}_A(x)\times \text{分数}(x)$。
• $f(x)$：你关心的那个“值”。
  • 比喻中：就是学生 $x$ 的分数（100分 或 50分）。
• $p(x)$：$x$ 在“目标分布”中发生的概率密度 (PDF)。
  • 比喻中：学生 $x$（比如“学霸”）在 A 班 出现的概率（$p(\text{学霸})=0.5$）。
• $q(x)$：$x$ 在“行为分布”中发生的概率密度 (PDF)（你实际采样的分布）。
  • 比喻中：学生 $x$（比如“学霸”）在 B 班 出现的概率（$q(\text{学霸})=0.1$）。
• $\frac{p(x)}{q(x)}$：这就是重要性采样系数 $\rho (x)$。
  • 比喻中：我们计算的权重（学霸的权重是 5.0）。
• $E_q\left[\dots \right]$：在“行为分布” $q$ 下求期望。
  • 比喻中：在 B 班 进行抽样。
• $E_q\left[\frac{p(x)}{q(x)}f(x)\right]$：
  • 这就是整个变换的“魔术”：它告诉我们，想求 $f(x)$ 在 A 班的平均分，我们不需要在 A 班抽样；我们只需要在 B 班 抽样，然后计算 $\frac{p(x)}{q(x)}f(x)$ 这个“加权分数”的平均分即可。这两个平均分的期望在数学上是严格相等的。

---

在实际操作中，我们无法计算精确的期望 $E_q$，我们只能通过有限的 $m$ 个样本来近似它：

$${\hat{E}}_p[f]\approx \frac{1}{m}\sum _{i=1}^m\frac{p(x_i)}{q(x_i)}f(x_i)$$ (基于 16.24)

公式 (16.24) 拆解：

这个公式是实践操作。它告诉我们如何用有限的样本去估计公式 (16.23) 那个理论上的期望值。这就是蒙特卡洛方法。

公式 (16.23) 是一个理论上的期望（用 $\int$ 或 $E_q$ 表示），我们无法精确计算它。所以我们通过在 $q$ 分布（B班）中实际采样 $m$ 次，用 $m$ 个样本的平均值来近似它。

• $m$：你采样的总次数。
  • 比喻中：你总共从 B 班抽了 $m=10$ 个学生。
• $x_i$：你抽到的第 $i$ 个样本（$x_i$ 是从 $q$ 分布中抽取的）。
  • 比喻中：你抽到的第 $i$ 个学生（比如，他是个“学霸”）。
• $f(x_i)$：这个样本的值。
  • 比喻中：这个“学霸”学生的分数（$f(x_i)=100$）。
• $\frac{p(x_i)}{q(x_i)}$：这个样本的权重。
  • 比喻中：$\frac{p(\text{学霸})}{q(\text{学霸})}=\frac{0.5}{0.1}=5.0$。
• ${\sum }_{i=1}^m\dots$：把所有 $m$ 个样本的“加权分数”全部加起来。
• $\frac{1}{m}\sum \dots$：除以 $m$，求“加权平均分”。
  • 这就是我们对 $E_p[f]$（A班的真实平均分）的最终估计值。当 $m$ 越大（抽的学生越多），这个估计值就越接近真实的 75 分。

---

将重要性采样应用于 MC

现在，我们把上面的比喻完美地对应到强化学习中：

抽象比喻	强化学习 (RL)
A 班 (想了解的)	目标策略 $\pi$ (Target Policy)，例如那个纯贪心的最优策略。
B 班 (能采样的)	行为策略 ${\pi }^{\prime }$ (Behavior Policy)，例如 $ϵ$-贪心策略。
$p(x)$ (在 A 班的概率)	$P^{\pi }$ (一条轨迹在 $\pi$ 下发生的概率)。
$q(x)$ (在 B 班的概率)	$P^{{\pi }^{\prime }}$ (同一条轨迹在 ${\pi }^{\prime }$ 下发生的概率)。
$x$ (一个学生)	$T$ (一条完整的轨迹) $<x_0,a_0,r_1,\dots ,x_T>$。
$f(x)$ (学生的分数)	$R$ (轨迹的回报)，即 $\sum {\gamma }^t{r}_{t+1}$。

---

现在我们来推导 RL 中的“权重” $\rho$：

我们需要计算 $\rho =\frac{p(x)}{q(x)}=\frac{P^{\pi }}{P^{{\pi }^{\prime }}}$。

一条轨迹发生的概率 $P^{\pi }$ 是什么？它等于一连串事件发生的概率之和：

1. 在 $x_0$ 选择 $a_0$ 的概率（由策略 $\pi$ 决定）
2. 并且 环境从 $x_0$ 转移到 $x_1$ 的概率（由环境 $P_{x\to x^{\prime }}$ 决定）
3. 并且 在 $x_1$ 选择 $a_1$ 的概率（由策略 $\pi$ 决定）
4. 并且 环境从 $x_1$ 转移到 $x_2$ 的概率（由环境 $P_{x\to x^{\prime }}$ 决定）
5. …以此类推

$$P^{\pi }=\prod _{i=0}^{T-1}\pi (x_i,a_i)P_{x_i\to x_{i+1}}^{a_i}$$ (基于 16.27)

公式 (16.27) 拆解：

• $P^{\pi }$：目标策略 $\pi$ 跑出这条轨迹 $T$ 的总概率 (这就是 $p(x)$)。
• ${\prod }_{i=0}^{T-1}$：连乘符号。代表 ${\text{P}}_0\times {\text{P}}_1\times \cdots \times {\text{P}}_{T-1}$。
• $\pi (x_i,a_i)$：目标策略 $\pi$ 在状态 $x_i$ 时，选择动作 $a_i$ 的概率。
• $P_{x_i\to x_{i+1}}^{a_i}$：环境在 $x_i$ 状态和 $a_i$ 动作下，转移到 $x_{i+1}$ 状态的概率。

同理，行为策略 ${\pi }^{\prime }$ 跑出同一条轨迹的概率为：
$$P^{{\pi }^{\prime }}=\prod _{i=0}^{T-1}{\pi }^{\prime }(x_i,a_i)P_{x_i\to x_{i+1}}^{a_i}$$

现在，计算权重 $\rho$ (即 $\frac{P^{\pi }}{P^{{\pi }^{\prime }}}$):
$$\rho =\frac{{\prod }_{i=0}^{T-1}\pi (x_i,a_i)P_{x_i\to x_{i+1}}^{a_i}}{{\prod }_{i=0}^{T-1}{\pi }^{\prime }(x_i,a_i)P_{x_i\to x_{i+1}}^{a_i}}$$

关键的简化来了！
你会发现，分子和分母中，所有与环境相关的项 $P_{x_i\to x_{i+1}}^{a_i}$ 是完全一样的！它们可以全部约掉！

这太棒了！因为我们是“免模型”学习，我们根本不知道环境的 $P_{x\to x^{\prime }}$ 是什么。而这个公式告诉我们，我们根本不需要知道它！

我们只需要知道两个策略本身：
$${\rho }_{0:T-1}=\prod _{t=0}^{T-1}\frac{\pi (x_t,a_t)}{{\pi }^{\prime }(x_t,a_t)}$$ (基于 16.28)

公式 (16.28) 拆解：

• ${\rho }_{0:T-1}$：这条从 0 到 $T-1$ 的完整轨迹的权重。
• $\frac{\pi (x_t,a_t)}{{\pi }^{\prime }(x_t,a_t)}$：在 $t$ 时刻的单步权重。
  • $\pi (x_t,a_t)$：我们的目标策略（例如纯贪心）在 $x_t$ 时 会 选择 $a_t$ 的概率。（如果 $a_t$ 是贪心动作，概率为 1；否则为 0）。
  • ${\pi }^{\prime }(x_t,a_t)$：我们的行为策略（例如 $ϵ$-贪心）在 $x_t$ 时 实际 选择 $a_t$ 的概率。（例如 $1-ϵ+ϵ/|A|$ 或 $ϵ/|A|$）。

---

最终的 Q 值更新：

当我们更新 $Q(x_t,a_t)$ 时，我们只关心从 $t$ 时刻开始的未来回报 $R_t$。
因此，我们也只需要计算从 $t$ 时刻开始的未来权重 ${\rho }_{t:T-1}$。

我们的 $Q$ 值更新（使用“普通重要性采样” OIS）就变成了：

$$Q(x_t,a_t)\leftarrow \text{Average}\left({\rho }_{t:T-1}\times R_t\right)$$ (基于 16.26)

公式 (16.26) 拆解：

• $Q(x_t,a_t)$：我们要更新的目标，即“在状态 $x_t$ 执行 $a_t$”的价值。
• $R_t$：我们在这条轨迹中，从 $t$ 时刻开始，实际观测到的未来累积回报 (这就是 $f(x)$)。
• ${\rho }_{t:T-1}$：从 $t$ 时刻开始的权重 (这就是 $\rho (x)$)。
• ${\rho }_{t:T-1}\times R_t$：“加权回报”。
• $\text{Average}(\dots )$：
• 比喻中：我们用 $({\text{加权分数}}_1+\cdots +{\text{加权分数}}_m)/m$ 来估计平均分。
• RL 中：我们使用增量式平均（例如伪代码中的 Q = (Q * count + R) / (count + 1)）来不断更新 $Q(x_t,a_t)$ 的平均值。这里的 $R$ 就是指这个加权回报 ${\rho }_{t:T-1}\times R_t$。
  $$

---

异策略 MC 算法伪代码

教材 图 16.11 给出了异策略 MC 算法的伪代码。这是一个“普通重要性采样” (OIS) 的实现，它使用增量式平均（类似式 16.2）来更新 Q 值。

1:  $Q(x,a)=0,\text{count}(x,a)=0,\forall x\in X,a\in A$
    $\pi (x)=\arg {\max }_{a^{\prime }}Q(x,a^{\prime })$  // 初始化 $\pi$ 为确定性贪心策略
2:  for s = 1, 2, … do:          // 循环每一“幕” (episode)
3:      // 3a. 【用 ${\pi }^{\prime }$ 生成轨迹】
        // 在 E 中执行 $ϵ$-贪心策略 ${\pi }^{\prime }$ (基于当前 Q) 产生轨迹:
        $<x_0,a_0,r_1,x_1,a_1,r_2,...,x_{T-1},a_{T-1},r_T,x_T>$
4:
5:      // 3b. 【评估策略 $\pi$ (Q值更新)】
        // (注：书中伪代码此处的实现非常独特, 是一种前向计算方式)
        // (为便于理解, 此处解释其“意图”)
6:      for t = 0, 1, …, T-1 do:  // 遍历轨迹中的每一步
7:          // 1. 计算从 t 时刻开始的实际回报 $G_t$
8:          $G_t={\sum }_{i=t+1}^T{\gamma }^{i-t-1}{r}_i$
9:
10:         // 2. 计算此回报的重要性采样系数 $\rho$
              //    (即式 16.28, 从 t 到 T-1 的概率比值)
11:         ${\rho }_{t:T-1}={\prod }_{k=t}^{T-1}\frac{\pi (x_k,a_k)}{{\pi }^{\prime }(x_k,a_k)}$
12:
13:         // 3. 计算加权回报 R
14:         $R={\rho }_{t:T-1}\times G_t$
15:
16:         // 4. 使用“增量式平均” (OIS) 更新 Q 值
17:         $Q(x_t,a_t)=\frac{Q(x_t,a_t)\times \text{count}(x_t,a_t)+R}{\text{count}(x_t,a_t)+1}$
18:         $\text{count}(x_t,a_t)=\text{count}(x_t,a_t)+1$
19:
20:         // 5. 【改进策略 $\pi$】
21:         $\pi (x_t)=\arg {\max }_{a^{\prime }}Q(x_t,a^{\prime })$
22:     end for
23: end for

伪代码讲解 (图 16.11)：

• Line 1 (初始化): 这是与“同策略”的第一个关键区别。我们初始化两个策略：Q 和 count 照常。但目标策略 $\pi$ 被显式地初始化为基于 $Q$ 的纯贪心策略。

• Line 3 (生成轨迹): 这是第二个关键区别。我们用于生成轨迹的，是行为策略 ${\pi }^{\prime }$，它是一个基于当前 $Q$ 的 $ϵ$-贪心策略。$\pi$ 和 ${\pi }^{\prime }$ 不再是同一个策略。

• Line 6-22 (评估与改进): 循环遍历轨迹中的每一个 $(x_t,a_t)$ 对。

  • 计算回报 $G_t$: 和同策略一样，计算从 $(x_t,a_t)$ 出发，实际获得的累积奖赏。
  • 计算 IS 系数 ${\rho }_{t:T-1}$: 这是异策略的核心。我们必须计算这个回报的“权重”。
    • $\pi (x_k,a_k)$: 目标策略 $\pi$ (纯贪心) 选择 $a_k$ 的概率。如果 $a_k$ 是 $\pi (x_k)$ (即贪心动作)，则概率为 1，否则为 0。
    • ${\pi }^{\prime }(x_k,a_k)$: 行为策略 ${\pi }^{\prime }$ ($ϵ$-贪心) 选择 $a_k$ 的概率 (值为 $1-ϵ+ϵ/|A|$ 或 $ϵ/|A|$)。
  • 重要细节：如果轨迹中任何一个 $a_k$ ($k\ge t$) 是 ${\pi }^{\prime }$ 探索（非贪心）时选的，那么 $\pi (x_k,a_k)=0$，导致整个 ${\rho }_{t:T-1}=0$。这意味着，我们只从那些“目标策略 $\pi$ 也有可能走出的”轨迹片段中学习。
  • 计算加权回报 $R$: $R=\rho \times G_t$。
  • Line 17-18 (更新 Q 值): 这两行是“普通重要性采样” (OIS) 的增量式更新。我们把加权回报 $R$ 当作一个新的样本，更新 $Q$ 值的平均值。
  • Line 21 (改进策略 $\pi$): 在更新 $Q(x_t,a_t)$ 之后，我们立刻更新我们的目标策略 $\pi$，使其在 $x_t$ 状态上保持贪心。

• OIS vs. WIS: 这种 OIS 算法（图 16.11）是无偏的，但其方差可能极大（因为 $\rho$ 的连乘积可能变得非常大）。在实际应用中，更常用的是“加权重要性采样” (Weighted Importance Sampling, WIS)，它通过对分母也进行加权来减小方差，尽管这会引入一点偏差。

(注：教材图 16.11 中的 Line 4 和 Line 6 是一种非常规的、前向计算 PDIS (逐决策重要性采样) 的方式，其数学形式复杂。上述伪代码（Line 7-14）是为清晰起见，对图 16.11 算法 意图 的重构，使其与式 16.28 的标准 IS 逻辑保持一致。)