第 5 章蒙特卡洛方法

第 5 章蒙特卡洛方法#

蒙特卡洛方法（Monte Carlo Methods）是一种仅基于经验（即对样本回报取平均）来解决强化学习问题的方法。为确保回报定义明确，本章仅将蒙特卡洛方法应用于回合制任务（episodic tasks）。

只有在一个回合完整结束后，才会更新价值估计和策略。因此，蒙特卡洛方法可以在每个回合的基础上进行，但不能按**每一步（在线/online）**进行。

我们采用广义策略迭代（Generalized Policy Iteration，GPI）的思想，在马尔可夫决策过程（Markov Decision Process，MDP）中通过样本回报 (Return) 学习价值函数。价值函数和相应的策略仍以基本相同的方式相互作用，以实现最优解。

最后说明一点：在本章中，我们假设每个回合总是从时间步 $0$ 开始，到时间步 $T$ 结束，即 $S_T$ 是终止状态。

5.1 蒙特卡洛预测（Monte Carlo Prediction / Evaluation）#

蒙特卡洛方法（Monte Carlo，MC）基础：

定义对状态 $s$ 的访问（visit）：在一个回合中状态 $s$ 的一次出现。显然，$s$ 在同一个回合中可能被访问多次。
评估方法：
- 首次访问蒙特卡洛方法（first-visit MC method）：通过对状态 $s$ 首次访问后获得的回报取平均，来估计 $v_\pi(s)$。
- 每次访问蒙特卡洛方法（every-visit MC method）：对所有访问状态 $s$ 后的回报取平均。

5.1.1 状态值函数的蒙特卡洛预测（Monte Carlo Prediction for State Value Function）#

首次访问蒙特卡洛预测，用于估计 $V \approx v_\pi$
- 算法：
- 直观理解：每个状态的回报 $G_t$ 是从 $S_{T-1}$ 倒推至 $S_0$ 计算而得。根据大数定律（law of large numbers），对某一状态的 $G_t$ 求平均即为该状态的价值：$v(S_t) = E_{\pi}[G_t|S_t]$。
- 回报计算示意图（$T=5$，箭头上的整数为奖励）：

Note

关于蒙特卡洛方法的一个重要事实是：对每个状态的估计是相互独立的。与动态规划（DP）不同，一个状态的估计不会依赖于其他状态的估计。换句话说，蒙特卡洛方法不使用自举（bootstrap），这是我们在上一章定义过的。
对于蒙特卡洛方法，估计某个单一状态的价值所需的计算开销与状态总数无关。因此，在只关心某一个或一部分状态价值时，蒙特卡洛方法尤其具有吸引力。

5.1.2 蒙特卡洛方法预测动作价值函数（Monte Carlo Prediction for Action Value Function）#

动机：状态值函数 $v_\pi$ 仅在已知环境模型的情况下可用。由于蒙特卡洛方法假设无环境模型（model-free），我们在这种情况下的主要目标之一就是估计最优动作价值函数 $q_\star$。
首次访问蒙特卡洛预测，用于估计 $Q \approx q_\pi$
算法：
- 输入：待评估的策略 $\pi$
- 初始化：
  - 对所有 $s \in S, a \in A(s)$，任意初始化 $Q(s, a) \in \mathbb{R}$
  - 对所有 $s \in S, a \in A(s)$，令 $Return(s, a) \leftarrow$ 空列表
- 不断重复（对每一回合）：
  - 生成一个回合：$\pi: S_0, A_0, R_1, S_1, A_1, ..., S_{T-1}, A_{T-1}, R_T, S_T$
  - $G_T \leftarrow 0$
  - $ \text{for } t \text{ in } \{T-1, T-2, ..., 0\}$:
    - $G_{t} \leftarrow \gamma G_{t+1} + R_{t+1}$
    - 将 $G_{t}$ 添加到 $Returns(S_t, A_t)$ 中
    - $q(S_t, A_t) \leftarrow average(Returns(S_t, A_t))$
直观理解：与第 5.1.1 节相同，记住 $q(s,a) = E_\pi[G_t | S_t, A_t]$

Note

蒙特卡洛回报 $G_t$ 提供了对期望回报的无偏样本，但由于环境动态和策略的随机性，每个奖励 $R_t$ 都是随机变量，其累加可能导致期望回报的估计具有高方差。

许多现代强化学习方法（或至少是回报估计方法）正是为缓解这一问题而提出，其中一些将在第 11 章中介绍。

5.2 蒙特卡洛控制（Monte Carlo Control）#

第 5.1 节中我们依赖的一般问题与两个基本假设：

持续探索问题：在估计 $q_\pi$ 时，许多状态-动作对可能永远不会被访问。例如，当使用确定性策略（deterministic policy）时，一个状态下的多个动作可能永远不会被选择。
假设 (1)：探索性开始（exploring starts）：每一回合从某个状态-动作对开始，且所有状态-动作对都有非零概率作为起点。（这保证在无限回合中，每个状态-动作对都将被访问无穷次。）
估计 $\hat{q}_\pi(S_t, A_t)$ 的问题：我们默认使用大数定律并依赖于如下假设：
假设 (2)：无限回合：策略评估是在无限次回合下进行的（完整策略评估）。

显然，这两个假设在实际中很难成立，因此我们将逐步介绍移除它们的方法。

5.2.1 蒙特卡洛控制：去除假设 (2)（Monte Carlo Control: Removing Assumption 2）#

如何去除假设 (2)：
- 为避免执行名义上需要的无限回合下的策略评估，我们可以放弃完整评估后再改进的做法。值迭代（value iteration）就是这种思想的极端例子。
- 对于蒙特卡洛策略迭代，自然的做法是每回合交替执行评估和改进。每个回合结束后，使用观测到的回报进行策略评估，然后对回合中访问过的所有状态进行策略改进。
蒙特卡洛探索性开始（Monte Carlo ES）算法，用于估计 $\pi \approx \pi_\star$

Note

上述算法的核心技巧在于：每次更新 $Q(S_t,A_t)$ 后立即进行策略改进（贪婪化），从而移除了对”无限回合”的依赖（假设 2）。

5.2.2 蒙特卡洛控制移除两个假设（Monte Carlo Control: Removing Both Assumptions）#

同策略（On-policy）与异策略（Off-policy）方法：
- 同策略方法（On-policy Methods）：评估或改进当前用于决策的策略（如蒙特卡洛探索性开始、动态规划等）。
- 异策略方法（Off-policy Methods）：评估或改进的策略不同于数据生成的策略。
$\epsilon$-软策略（$\epsilon$-soft policies）：
- $\epsilon$-贪婪策略（$\epsilon$-greedy policy）：如第 2 章 2.2 节介绍，非贪婪动作以均匀分布的方式被赋予 $\frac{\epsilon}{|A(s)|}$ 的最小选择概率，贪婪动作的概率为 $1 - \epsilon + \frac{\epsilon}{|A(s)|}$。
  - $\epsilon$-贪婪策略属于 $\epsilon$-软策略的一种。在所有 $\epsilon$-软策略中，$\epsilon$-贪婪策略是最贪婪的。
  - $\epsilon$-软策略：对任意状态 $s$，所有动作 $a$ 的选择概率 $\pi(a|s)>\frac{\epsilon}{|A(s)|}$，即每个动作都有非零概率被选中，但不一定均匀。
基于 $\epsilon$-软策略的同策略首次访问蒙特卡洛控制，用于估计 $\pi \approx \pi_\star$
- 算法：
  
  - 直观理解：如果去除了探索性开始假设，就不能简单地使策略对当前价值函数贪婪化，否则非贪婪动作将无法再被探索。因此在[5.2.1 节](#521-monte-carlo-control-removing-assumption-2)基础上，本算法通过以下方式移除了探索性开始的假设：
  - 初始策略设为 $\epsilon$-软策略；
  - 在策略改进时，将旧策略更新为 $\epsilon$-贪婪策略。

Note

- 本算法也移除了第二个假设（无限回合），因为每次更新 $Q(S_t, A_t)$ 后立即执行 $\epsilon$-贪婪化。

- 策略改进定理保证：对 $q_\pi$ 的 $\epsilon$-贪婪策略总优于任意 $\epsilon$-软策略。

- 需要注意的是，该方法最终只能得到 $\epsilon$-软策略中的最优策略，即一个仍保留探索行为的近似最优策略，而非真正的最优策略。

5.3 异策略蒙特卡洛方法（Off-policy Monte Carlo Methods）#

所有学习型控制方法都面临一个两难问题：它们既要学习基于后续最优行为的动作价值，又必须采取非最优行为来探索所有动作（以找到最优动作）。如何在遵循探索性策略的同时学习最优策略呢？一种更直接的方法是使用两种策略。

让我们回顾同策略/异策略学习：

同策略学习（On-policy Learning）：学习智能体当前所遵循的目标策略（target policy） $\pi$ 的价值函数或策略函数。这意味着智能体使用正在改进的策略与环境进行交互。同策略方法通常更简单，优先被考虑。
异策略学习（Off-policy Learning）：学习来源于行为策略（behavior policy） $b$ 的数据，但目标是估计与 $b$ 不同的目标策略（target policy） $\pi$ 的价值或策略函数。异策略方法需要额外的概念和符号。由于数据来源与目标不同，异策略方法通常具有更高的方差且收敛速度较慢。 **另一方面，异策略方法更强大且更通用。**当目标策略与行为策略相同时，异策略方法包含了同策略方法作为特例。
- 为了使用 $b$ 生成的回合来估计 $\pi$ 的价值，我们基于一个覆盖假设（Coverage Assumption）：只要 $\pi(a|s) \ge 0$，就必须有 $b(a|s) \ge 0$。这意味着，在目标策略 $\pi$ 不为零概率的状态中，行为策略 $b$ 必须能够以非零概率选择相同的动作。

5.3.1 基于重要性采样的异策略蒙特卡洛预测（Off-policy Monte Carlo Prediction via Importance Sampling）#

重要性采样（Importance Sampling）的实现：如果你觉得文本推导难以理解，这里有一个讲解视频可供参考。
- 给定来自 $X \sim b$ 的现有样本，我们希望估计$E_{\pi}[X]$（来自不同分布）
- 推导：
```
$$
\begin{align*}
E_{\pi}[X] &= \sum_{x \in X} x \pi(x) \\
&= \sum_{x \in X} x \pi(x) \frac{b(x)}{b(x)} \\
&= \sum_{x \in X} x b(x) \frac{\pi(x)}{b(x)} \\
&= \sum_{x \in X} x b(x) \rho(x)  \quad (\rho(x) \text{ denotes } \frac{\pi(x)}{b(x)}) \\
&= E_{b}[X \rho(X)] \\
&\approx \frac{1}{n} \sum_{i=1}^n x_i \rho(x_i)
\end{align*}
$$
```
- 比值 $\rho(x)=\frac{\pi(x)}{b(x)}$ 被称为重要性采样比率（importance sampling ratio）。
理论上用于评估目标策略 $\pi$ 的重要性采样：
1. 对于一个给定状态-动作轨迹，计算重要性采样比率：
  - 给定一个轨迹 $S_{t+1}, A_{t+1}, S_{t+2}..., A_{T-1}, S_T$ ，从 $S_t, A_t$ 开始，该轨迹的概率为：
    
    \[\begin{split} \begin{align*} Pr (&S_{t+1}, A_{t+1} ,..., S_{T-1}, A_{T-1}, S_T | S_t, A_t) \\ &= p(S_{t+1}|A_t, S_t)\pi(A_{t+1}|S_{t+1}) ... p(S_{T-1}|A_{T-2}, S_{T-2})\pi(A_{T-1}|S_{T-1})p(S_T|A_{T-1},S_{T-1}) \\ &= \Pi_{k=t+1}^{k={T-1}} p(S_k|A_{k-1}, S_{k-1})\pi(A_k|S_k) \times p(S_T|A_{T-1},S_{T-1}) \end{align*} \end{split}\]
    
    因此，重要性采样比率为：
    
    \[\begin{split} \begin{align*} \rho_{t+1: T-1} &= \frac{\Pi_{k=t+1}^{k={T-1}} p(S_k|A_{k-1}, S_{k-1})\pi(A_k|S_k) \times p(S_T|A_{T-1},S_{T-1})}{\Pi_{k=t+1}^{k={T-1}} p(S_k|A_{k-1}, S_{k-1})b(A_k|S_k) \times p(S_T|A_{T-1},S_{T-1})} \\ &= \frac{\Pi_{k={t+1}}^{k={T-1}} \pi(A_k|S_k)}{\Pi_{k={t+1}}^{k={T-1}} b(A_k|S_k)} \end{align*} \end{split}\]
  Note
  - $\rho_{t: T-1}$ 的下标对应于轨迹中的动作序列，即 {$A_{t+1}, ..., A_{T-1}$}，然后轨迹在终止状态 $S_T$ 结束。
  - $\rho_{t+1: T-1}$ 只依赖于两个策略，不依赖于环境动态，因此重要性采样可用于无模型强化学习问题。
2. 给定 $q_b(s,a) = E_b[G_t|S_t = s, A_t = a]$，估计 $q_\pi(s,a)$ 为：
  
  \[ q_\pi(s,a)= E_b[\rho_{t+1:T-1} \times G_t|S_t = s, A_t=a] \]
  - 直观理解：注意动作价值函数 $q$ 的定义 $E[G_t|S_t = s, A_t=a]$ 是对所有轨迹的期望，而每个 $G_t$ 是一个具体实现，它可视为重要性采样方程推导中的变量 $x$。重要性采样比率 $\rho_{t+1:T-1}$ 是按轨迹计算，用于与该轨迹的 $G_t$ 一一对应，并直接与 $G_t$ 相乘。
实践中用于评估目标策略 $\pi$ 的重要性采样
- 说明：
  - 关于时间步：时间步的编号会跨回合递增。例如，如果第一回合在 $t=100$ 结束，那么下一回合从 $t = 101$ 开始。
  - 关于记号：
    - $J(s,a)$：访问状态-动作对 $(s,a)$ 的时间步集合（对于 every-visit 方法；若为 first-visit 方法，则只包括首次访问的时间步）
    - $T(t)$：从时间步 $t$ 开始的第一个终止状态的时间步
    - $\{G_t\}_{t \in J(s,a)}$：所有回合中与 $(s,a)$ 相关的回报集合
    - $\{\rho_{t+1:T(t)-1}\}_{t \in J(s,a)}$：对应轨迹的重要性采样比率
  - 方法：
    - 用于评估目标策略的普通重要性采样（Ordinary importance sampling）：
      
      \[ Q(s,a) \dot= \frac{\sum_{t \in J(s)} \ \rho_{t+1:T(t)-1} \times G_t}{|J(s,a)|} \]
    - 用于评估目标策略的加权重要性采样（Weighted importance sampling）：
      
      \[ Q(s,a) \dot= \frac{\sum_{t \in J(s)} \ \rho_{t+1:T(t)-1} \times G_t}{\sum_{t \in J(s)} \ \rho_{t+1:T(t)-1}} \]

Note

对于首次访问方法：

考虑在观察到 $(s,a)$ 的某个回报 $G_t$ 后估计它们的首次访问方法，在加权平均估计中，该估计等于观察到的回报 $G_t$，不受比率影响，此时其估计为 $q_b(s,a)$ 而非 $q_\pi(s,a)$。而普通方法的估计始终是 $q_\pi(s,a)$，但其波动可能很大，取决于 $\rho_{t+1:T(t)-1}$ 的值。

总而言之，普通重要性采样（ordinary importance sampling）是无偏的，而加权重要性采样（weighted importance sampling）则有偏（尽管其偏差在渐近上会收敛为零）。另一方面，普通重要性采样的方差通常是无界的，因为比值的方差可能无界；而在加权估计器中，任何单个回报所占的最大权重为 1。事实上，在假设回报有界的情况下，即使这些比值本身的方差无穷大，加权重要性采样估计器的方差也会收敛到 0。

在实际应用中，加权估计器通常具有显著更低的方差，因此被强烈推荐使用。 然而，我们不会完全放弃普通重要性采样，因为在后面讨论使用函数逼近的近似方法时，它更容易推广。
对于每次访问方法：

普通和加权重要性采样的每次访问方法（every‑visit methods）都是有偏的，不过其偏差同样会随着样本数量的增加而渐近趋于零。在实际应用中，每次访问方法往往更受青睐，因为它们无需记录每个状态是否已访问，而且更容易扩展到近似方法。

用于更新 $Q(s,a)$ 的增量实现：
- 对于同策略方法：
  
  $Q(s,a)$ 是通过简单平均回报估计的，增量实现与第 2 章 2.4.1 节一致：
  
  \[ 新估计值 \leftarrow 旧估计值 + 步长*[目标值 - 旧估计值] \]
- 对于异策略方法：
  - 普通重要性采样：同样是通过 $J(s,a)$ 中回报的平均值估计，增量公式与上面所示的同策略方法相同。
  - 加权重要性采样：这里，我们必须使用一种略有不同的增量算法，对收益进行加权平均。
    - 假设 $\{G_t\}_{t \in J(s,a)}$ 已包含 $n-1$ 个值，记为 $G_1, G_2, ..., G_{n-1}$，其中 $G_i$ 对应权重为 $W_i = \rho_{i+1:T(i)-1}$ 且 $W_i \in \{\rho_{t+1:T(t)-1}\}_{t \in J(s,a)}$
    - 第 $n$ 次对 $Q(s,a)$ 的加权估计为：
      
      \[\begin{split} \begin{align*} Q_n(s,a) &\dot= \frac{\sum_{k=1}^{k=n-1}W_k G_k}{\sum_{k=1}^{k=n-1}W_k} \\ &\dot= Q_{n-1}(s,a) + \alpha \times [G_n - Q_{n-1}(s,a)] \end{align*} \end{split}\]
      
      其中 $\alpha = \frac{W_n}{C_n}$，$C_n \dot= C_{n-1} + W_n = \sum_{i=1}^{i=n} W_i$，$C_0 \dot= 0$
用于估计 $Q \approx q_\pi$ 的异策略蒙特卡洛预测（策略评估）算法

Note

$W_{t+1} = \rho_{t+1:T(i)-1}$

5.3.2 异策略蒙特卡洛控制（Off-policy Monte Carlo Control）#

经验法则：在控制问题中，目标策略通常是根据当前估计的动作价值函数所得到的确定性贪婪策略。随着行为策略保持随机且更具探索性（例如 $\epsilon$-贪婪策略），该策略会逐渐收敛为确定性的最优策略。
异策略蒙特卡洛控制算法，用于估计 $\pi \approx \pi_\star$
Note
- 即便动作是按另一软策略 $b$ 选取的（可能在不同或同一回合内变化），策略 $\pi$ 在所有遇到的状态上仍会收敛到最优。
- 该方法的一个潜在问题是它只从回合尾部学习，此时余下的动作全是贪婪的。若非贪婪动作较多，学习将变慢，尤其是对于出现在长回合早期的状态；这可能极大拖慢学习速度。

5.4 总结#

目前，蒙特卡洛方法在预测和控制方面仍然存在一些未解的问题，是一个持续进行研究的领域。

思维导图：我们现在的位置
关键要点
- 蒙特卡洛方法相对于动态规划方法的优点：
  1. 蒙特卡洛方法不需要环境模型。
  2. 蒙特卡洛方法可以与仿真或从概率分布中抽样结合使用。对于许多应用，即使构建转换概率的明确模型较为困难，仍然可以轻松地模拟样本回合。
  3. 蒙特卡洛方法可以轻松高效地专注于一小部分状态。特定区域可以被精确评估，而无需为评估其余状态集付出代价。
  4. 蒙特卡洛方法可能更不容易受到马尔可夫性假设违背的影响。因为它们不会基于后继状态的价值估计来更新自己的价值估计，即它们不会进行自举（bootstrap）。
- 保持足够的探索性：
  - 对于同策略方法：使用探索性开始假设（假设1）或将 $\pi$ 初始化为 $\epsilon$ -软策略。
  - 对于异策略方法：我们从由不同的行为策略生成的数据中学习目标策略的价值函数，这满足覆盖假设。同时，我们需要使用重要性采样将行为策略的期望回报转换为目标策略的期望回报。
额外的课程视频（可选）: Emma Brunskill: 批量强化学习

第 5 章 蒙特卡洛方法

Contents

第 5 章 蒙特卡洛方法#

5.1 蒙特卡洛预测（Monte Carlo Prediction / Evaluation）#

5.1.1 状态值函数的蒙特卡洛预测（Monte Carlo Prediction for State Value Function）#

5.1.2 蒙特卡洛方法预测动作价值函数（Monte Carlo Prediction for Action Value Function）#

5.2 蒙特卡洛控制（Monte Carlo Control）#

5.2.1 蒙特卡洛控制：去除假设 (2)（Monte Carlo Control: Removing Assumption 2）#

5.2.2 蒙特卡洛控制移除两个假设（Monte Carlo Control: Removing Both Assumptions）#

5.3 异策略蒙特卡洛方法（Off-policy Monte Carlo Methods）#

5.3.1 基于重要性采样的异策略蒙特卡洛预测（Off-policy Monte Carlo Prediction via Importance Sampling）#

5.3.2 异策略蒙特卡洛控制（Off-policy Monte Carlo Control）#

5.4 总结#

第 5 章蒙特卡洛方法

第 5 章蒙特卡洛方法#