RL 学习笔记 #4 蒙特卡洛学习算法

本文最后更新于：2024年12月24日晚上

在上一节中，我们介绍了策略迭代，它依赖于明确的环境模型（model-based）来进行策略评估和改进。然而，在许多现实问题中，环境模型不可用，或者我们无法轻易获得完整的转移概率 $T$ 和奖励函数 $R$。这时，蒙特卡洛学习算法（Monte Carlo Learning）作为一种无模型（model-free）方法，提供了一种通过样本进行策略优化的途径。

蒙特卡洛方法的核心思想是：通过对环境的采样，基于多次模拟的经验回报，估计状态值函数或状态-动作值函数（Monte Carlo Estimation）。其依据就是经典的大数定律。

蒙特卡洛学习主要依赖以下几个关键特性：

基于样本：直接使用采样的经验（例如状态序列、奖励序列）进行学习。
延迟更新：直到采样结束后，才对策略或值函数进行更新。
无需环境模型：完全基于与环境的交互，适用于复杂环境。

MC 基本算法 | MC Basic

与策略迭代类似，蒙特卡洛方法需要基于一个固定策略 $\pi$。我们知道策略迭代包含两个主要步骤：

策略评估（PE）：$v_{\pi^{(k)}}=r_{\pi^{(k)}}+\gamma P_{\pi^{(k)}} v_{\pi^{(k)}}$
策略改进（PI）：$\pi^{(k+1)} = \arg\max _\pi\left(r_\pi+\gamma P_\pi v_{\pi^{(k)}}\right)$

这里面最核心的地方就是状态值 $v_{\pi^{(k)}}$ 的求解，此时有两种办法：

基于模型 $T$ 和 $R$，使用迭代法求解： \[ v_{\pi^{(k)}}(s) = \sum_a \pi^{(k)}(a \mid s) \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_{\pi^{(k)}}(s') \right] \]
免模型求解，回归状态值的原始定义： \[ v_\pi(s) = \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \]

换句话说，我们可以从任意状态 $s$ 出发，随机采样若干轨迹 $\{\tau\}$，使用这些轨迹的累计回报 $\{g_t\}$ 的平均值来估计 $s$ 的期望累计回报： \[ v_\pi(s) = \mathbb{E}_\pi\left[G_t \mid S_t = s\right] \approx \frac{1}{N} \sum_{i=1}^N g^{(i)}(s) \] 同理，也可以估计动作 $a$ 的期望累计回报： \[ q_\pi(s,a) = \mathbb{E}_\pi\left[G_t \mid S_t = s, A_t = a\right] \approx \frac{1}{N} \sum_{i=1}^N g^{(i)}(s, a) \] 总之就是一句话：没有模型时，就得有数据！这里采样到的轨迹在统计学或概率学上会称为样本（Sample），而在强化学习中则称为经验（Experience）。

算法框架

以下的步骤包含在策略迭代过程中的策略估计（PE）步骤中。这里我们使用蒙特卡洛方法估计动作价值 $q_\pi(s,a)$，因为如果先估计状态值 $v_\pi(s)$，在之后的策略改进（PI）步骤中还是需要计算 $q_\pi(s,a)$，此时又得需要模型！

具体步骤如下：

采样：从待求解状态 $s_t$ 和动作 $a_t$ 出发，基于策略 $\pi$ 生成多条完整的轨迹，每条轨迹由状态、动作、奖励序列组成，例如： \[ \tau = \{s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1}, r_{t+2}, \dots, s_T\} \] 其中 $T$ 是终止时刻。
回报计算：对于每个轨迹，计算累计回报（Return）： \[ g_t = \sum_{k=t}^T \gamma^{k-t} r_{k+1} \]
更新：通过多次采样得到的回报 $\{g_t\}$，对动作价值函数进行更新： \[ q_\pi(s_t,a_t) \leftarrow \frac{\text{累计回报和}}{\text{访问次数}} \]

之后在策略改进（PI）步骤中，依旧是贪心选择最大动作价值来更新策略。

有趣的现象——回合（Episode）的长度：
为了 $G_t$ 估计的准确性，我们希望每次采样到的 $g_t$ 都尽量精确，因此 Episode 也是越长越好。
如果 Episode 长度很短，例如 $1$，即模型只会探索一个步骤，最终只有目标周围一步的状态值会得到准确估计，其他地方均为 $0$，因为无法得到最终奖励。
推广开来，只有当 Episode 长度超过一个状态距离目标状态的最短路径时，该状态值才能得到更新；并且超过得越多，这个估计状态值就离真实值越接近。

MC 探索性启动 | MC Exploring Starts

为了估计的准确性，蒙特卡洛算法往往需要采样大量样本（每个状态、每个动作都要采样，如果环境是随机的，则还需要采样 $N$ 次求平均），导致 Basic 算法的效率过低。

在实际使用中，我们会用更高效的改进算法。蒙特卡洛方法的一个基础假设是每个状态和动作都可以被访问（Visit）到。而 MC Basic 实际上是 Initial-visit 方法，即对于一个 Episode 只考虑起点的 $(s_t,a_t)$。但这样其实是对后续轨迹的浪费！

一个完整的轨迹上的所有 $(s,a)$ 的访问实际上都可以被利用，这就是探索性启动（Exploring Starts, ES）。当然细化下去还可以分为两种：

First-visit：对于轨迹上的 $(s_t,a_t)$，只考虑首次访问时的 $g_t$。
Every-visit：对于轨迹上的 $(s_t,a_t)$，每次访问时的 $g_t$ 都被计算。

Exploring Starts 也有一定的局限性：
需要对环境有完全的访问权限，才能随机选择任意状态和动作。
在复杂环境中，不易实现随机探索。
这也是 Exploring Starts 名字的由来——因为有的状态访问不到，所有需要指定起点（Starts）进行探索（Exploring）。

另一个优化的思路是增量式更新。在上一节中我们曾介绍过截断策略迭代，这是一种利用不精确估计去减少计算量的方法。同样，在 MC 算法中也可以借鉴这种思想。

即使有了探索性启动，我们也需要采样多个轨迹取平均才能精确估计 $G_t$。但是在这里，我们可以每得到一个 $g_t$ 就立即改进策略（PI）。虽然不能准确得到结果，但是也能将 $\pi$ 向着优化方向前进一小步，此时下一次采样轨迹就会更加接近最优解，加快收敛速度。

这一类采用不精确中间结果来加快收敛速度的思想，也被统称为 Generalized Policy Iteration (GPI)。

MC $\varepsilon$-贪婪策略 | MC $\varepsilon$-Greedy

在实际问题中，探索性启动往往也需要消耗额外的资源，因为某些策略 $\pi$ 可能永远不会访问某些状态或执行某些动作。之前我们提到的贪心策略（确定性策略）正是如此，对于一种状态只考虑一个最优的动作，就导致许多动作无法被访问到。

为此，我们引入软策略（Soft Policy）的概念：在每个状态有概率选取不同动作的随机性策略。由于随机性的存在，只要采样的 Episode 足够长，所有的 $(s,a)$ 都会被访问到。这样我们就能去掉 Exploring Starts 的条件。

最常见的软策略是 $\varepsilon$-贪婪策略（$\varepsilon$-Greedy Policy）： \[ \pi(a \mid s)= \begin{cases}1-\frac{\varepsilon}{|A(s)|}(|A(s)|-1), & \text { for the greedy action, } \\ \frac{\varepsilon}{|A(s)|}, & \text { for the other }|A(s)|-1 \text { actions. }\end{cases} \] 其中，参数 $$，$|A(s)| $ 表示状态 $s$ 的动作数。

可以看到，最优动作所赋予的概率 $1-\frac{\varepsilon}{|A(s)|}(|A(s)|-1)=1-\varepsilon + \frac{\varepsilon}{|A(s)|} \ge \frac{\varepsilon}{|A(s)|}$，也就是说我们还是会将最大的概率留给最优动作，只不过略微增加了其他动作被探索到的概率。

$\varepsilon$-贪婪策略反应的是探索（exploration）和利用（exploitation）的平衡：$\varepsilon$ 越小就越侧重利用（更贪心），$\varepsilon$ 越大就越侧重探索（更均衡）。

对蒙特卡洛学习的改进

之前我们在做策略更新（PU）或者策略优化（PI）的时候，都默认进行贪心选择 $a = \arg\max_a q(s, a)$，即：

\[ \pi^{(k+1)}(a \mid s) = \begin{cases} 1, & \;\; a = a^*_k, \\ 0, & \;\; a \ne a^*_k. \end{cases} \] 现在我们将 $\varepsilon$-贪婪策略嵌入到更新规则中： \[ \pi^{(k+1)}(a \mid s) = \begin{cases} 1 - \epsilon + \frac{\varepsilon}{|A(s)|}, & \;\; a = a^*_k, \\ \frac{\varepsilon}{|A(s)|}, & \;\; a \ne a^*_k. \end{cases} \] 可以证明，随着 $\varepsilon \to 0$ 时，算法逐渐收敛于最优策略。一个常用的方法是随着策略更新，逐渐减小 $\varepsilon$，直到当前策略与 $\varepsilon=0$ 的贪心策略一致（Consistent）。