引言与背景

蒙特卡洛方法是强化学习中的重要算法类别，它标志着从基于模型到无模型算法的转变。这类算法不依赖环境模型，而是通过与环境的直接交互获取经验数据来学习最优策略。

蒙特卡洛方法在强化学习算法谱系中处于"无模型"方法的起始位置，是从基于模型的方法（如值迭代和策略迭代）向无模型方法过渡的第一步。

无模型强化学习的核心理念可以简述为：如果没有模型，我们必须有数据；如果没有数据，我们必须有模型；如果两者都没有，我们就无法找到最优策略。在强化学习中，"数据"通常指智能体与环境交互的经验。

均值估计问题

在介绍蒙特卡洛强化学习算法之前，我们首先需要理解均值估计问题，这是理解从数据而非模型中学习的基础。

考虑一个可以取有限实数集合 $X$ 中值的随机变量 $X$，我们的任务是计算 $X$ 的均值或期望值：$E[X]$

有两种方法可以计算 $E[X]$：

基于模型的方法：当已知随机变量的概率分布时，可以直接根据期望值的定义计算：
无模型的方法：当概率分布未知时，假设我们有随机变量 $X$ 的样本 $\{x_1, x_2, \ldots, x_n\}$，则可以近似计算：

大数定律

在强化学习中，状态值和动作值都定义为回报的期望值。因此，估计状态值或动作值本质上是一个均值估计问题。

基础蒙特卡洛算法（MC Basic）

从策略迭代到无模型算法

策略迭代算法包含两个步骤：策略评估和策略改进。蒙特卡洛算法的核心思想是将策略迭代中基于模型的策略评估步骤替换为无模型的蒙特卡洛估计步骤。

计算动作值有两种方法：

基于模型的方法：先计算状态值 $v_{\pi_k}$，然后计算动作值：
无模型的方法：利用动作值的定义：

MC Basic

从初始策略 $\pi_0$ 开始，算法在第 $k$ 次迭代中有两个步骤：

策略评估：估计所有 $(s, a)$ 的 $q_{\pi_k}(s, a)$。具体地，对每个 $(s, a)$，收集足够多的episode并使用回报的平均值 $q_k(s, a)$ 来近似 $q_{\pi_k}(s, a)$。
策略改进：解决 $\pi_{k+1}(s) = \arg\max_{\pi} \sum_a \pi(a|s)q_k(s, a)$ 对所有 $s \in S$。贪婪最优策略为 $\pi_{k+1}(a^*_k|s) = 1$，其中 $a^*_k = \arg\max_a q_k(s, a)$。
算法伪代码如下：

对比策略迭代算法可以看出它与策略迭代算法非常相似。唯一的区别是，它直接从经验样本中计算action value，而策略迭代首先计算state value，然后根据系统模型计算action value。

另外， MC basic 是从有限个样本估计action value，因此，action value的近似值可能并不准确。尽管如此，算法通常仍能运行。这与截断策略迭代算法类似，在这种算法中，行动值的计算既不准确，也不精确。

由于策略迭代是收敛的，MC Basic 在给定足够样本的情况下也是收敛的。

算法示例

以一个简单的网格世界为例，智能体从状态 $s_1$ 开始，有五种可能的动作。对于每个动作，我们需要收集足够长的回合来有效近似动作值。$r_{boundary} = r_{forbidden} = −1, r_{target} = 1.$ $ γ = 0.9$.

按照策略 $\pi_0$，我们可以从 $(s_1, a_1), (s_1, a_2), \ldots, (s_1, a_5)$ 分别开始获得以下episode：

从 $(s_1, a_1)$ 开始的episode：$s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} s_1 \xrightarrow{a_1} \ldots$
动作值等于回合的折扣回报：$q_{\pi_0}(s_1, a_1) = -1 + \gamma(-1) + \gamma^2(-1) + \cdots = \frac{-1}{1-\gamma}$
从 $(s_1, a_2)$ 开始的回合：$s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_3} \ldots$
动作值：$q_{\pi_0}(s_1, a_2) = 0 + \gamma \cdot 0 + \gamma^2 \cdot 0 + \gamma^3(1) + \gamma^4(1) + \cdots = \frac{\gamma^3}{1-\gamma}$
$q_{\pi_0}(s_1, a_3) = \frac{\gamma^3}{1-\gamma}$， $q_{\pi_0}(s_1, a_4) = \frac{-1}{1-\gamma}$， $q_{\pi_0}(s_1, a_5) = \frac{-\gamma}{1-\gamma}$
通过比较五个动作值，我们可以确定最大值 $q_{\pi_0}(s_1, a_2)=q_{\pi_0}(s_1, a_3) = \frac{\gamma^3}{1-\gamma}>0$, 并据此更新策略:

\[ \pi_1(a_2|s_1)=1\ or\ \pi_1(a_3|s_1)=1 \]

上面的例子比较简单，在更复杂的场景中， episode长度对最终最优策略有重大影响。当每个episode太短时，策略和价值估计都不是最优的。

在极端情况下，当episode长度为1时，只有与目标相邻的状态具有非零值，所有其他状态的值为零，因为每个回合太短而无法达到目标或获得正奖励。

随着episode长度增加，一个有趣的空间模式出现：离目标更近的状态比离目标更远的状态更早拥有非零值。这是因为从一个状态开始，智能体必须至少走一定步数才能到达目标状态并获得正奖励。

这与稀疏奖励问题相关，即只有在达到目标时才能获得正奖励的情况。稀疏奖励设置需要能够达到目标的长episode，当状态空间很大时，这一要求很难满足，从而降低了学习效率。

探索起始的蒙特卡洛算法（MC Exploring Starts）

MC Exploring Starts 算法通过更有效地利用样本来扩展 MC Basic 算法。假设我们有一个按策略 $\pi$ 获得的episode：

\[ s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_4} s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \ldots \]

每当一个状态-动作对在回合中出现时，它被称为该状态-动作对的一次访问（visit）。有不同的策略可以利用这些访问：

\[ \begin{equation}\begin{aligned}{s}_{1}\overset{{a}_{2}}{ \rightarrow }{s}_{2}\overset{{a}_{4}}{ \rightarrow }{s}_{1}\overset{{a}_{2}}{ \rightarrow }{s}_{2}\overset{{a}_{3}}{ \rightarrow }&{s}_{5}\overset{{a}_{1}}{ \rightarrow }\ldots\ [\text{original}\ \text{episode}] \\ {s}_{2}\overset{{a}_{4}}{ \rightarrow }{s}_{1}\overset{{a}_{2}}{ \rightarrow }{s}_{2}\overset{{a}_{3}}{ \rightarrow }&{s}_{5}\overset{{a}_{1}}{ \rightarrow }\ldots\ [subepisode \ starting\ from \left( {{s}_{2},a_4})\right.] \\ {s}_{1}\overset{{a}_{2}}{ \rightarrow }{s}_{2}\overset{{a}_{3}}{ \rightarrow }&{s}_{5}\overset{{a}_{1}}{ \rightarrow }\ldots\ [subepisode\ starting\ from\left. \left( {{s}_{1},{a}_{2}}\right) \right\rbrack \\ {s}_{2}\overset{{a}_{3}}{ \rightarrow }&{s}_{5}\overset{{a}_{1}}{ \rightarrow }\ldots\ [subepisode \ starting\ from \left. \left( {{s}_{2},{a}_{3}}\right) \right\rbrack \\ &{s}_{5}\overset{{a}_{1}}{ \rightarrow }\ldots\ [subepisode \ starting\ from \left. \left( {{s}_{5},{a}_{1}}\right) \right\rbrack \end{aligned}\end{equation} \]

初始访问策略（initial visit）：回合仅用于估计它开始的初始状态-动作对的动作值。MC Basic 算法使用这种策略, 如3式所示，这种策略并不高效（sample-efficient），这个episode 还访问了很多其他 state-action对。
首次访问策略（first visit）：对于在一个episode中出现了很多次的state-action对，只计算其在回合中的第一次访问。
每次访问策略（every visit）：计算state-action对的每次访问。
在样本使用效率方面，每次访问策略是最好的。如果一个episode足够长，可以多次访问所有状态-动作对，那么使用每次访问策略，这单个episode可能足以估计所有动作值。

更高效地更新策略

更新策略有两种策略：

在策略评估步骤中，收集从同一状态-动作对开始的所有episode，然后使用这些episode的平均回报近似动作值。MC Basic 算法采用这种策略。
使用单个episode的回报来近似相应的动作值，这样我们可以在收到回合后立即获得粗略估计，然后以episode为单位更新策略。
MC Exploring Starts 算法的伪代码如下所示：

该算法使用每次访问策略，从回合结束状态开始并向后计算折扣回报，这种技术使算法更高效，但也使其更复杂。

探索起始条件要求从每个状态-动作对开始生成足够多的回合。只有当每个状态-动作对都被充分探索时，我们才能准确估计它们的动作值（根据大数定律），从而成功找到最优策略。

如果一个动作没有被充分探索，其动作值可能被不准确地估计，即使它实际上是最佳动作，该动作也可能不会被策略选择。

MC Basic 和 MC Exploring Starts 都需要满足这一条件。然而，这一条件在许多应用中很难满足，特别是那些涉及与环境的物理交互的应用。这个问题可以通过使用软策略来解决，如下一节中介绍的 MC ε-Greedy 算法。

ε-贪婪蒙特卡洛算法（MC ε-Greedy）

软策略与ε-贪婪策略

软策略是指在任何状态下都有正概率选择任何动作的策略。考虑一个极端情况，如果我们只有一个episode，使用软策略，一个足够长的回合可以多次访问每个状态-动作对。这样，我们就不需要从不同的状态-动作对开始生成大量回合，从而可以去除探索起始要求。

ε-贪婪策略是一种常见的软策略，它有更高的概率选择贪婪动作（具有最大动作值的动作），同时对任何其他动作保持相同的非零概率。

具体来说，假设 $\varepsilon \in [0,1]$，相应的 ε-贪婪策略形式如下：

\[ \pi(a|s) = \begin{cases} 1-\varepsilon + \frac{\varepsilon}{|A(s)|}, & \text{for the greedy action} \\ \frac{\varepsilon}{|A(s)|}, & \text{for the other}|A(s)|-1 \ \text{actions} \end{cases} \]

其中 $|A(s)|$ 表示与状态 $s$ 关联的动作数量。

当 $\varepsilon = 0$ 时，ε-贪婪变成贪婪策略。当 $\varepsilon = 1$ 时，选择任何动作的概率等于 $\frac{1}{|A(s)|}$。

选择贪婪动作的概率总是大于选择任何其他动作的概率，因为对于任何 $\varepsilon \in [0,1]$，有：

\[ 1-\varepsilon+\frac{\varepsilon}{|A(s)|} \geq \frac{\varepsilon}{|A(s)|} \]

算法描述

要将ε-贪婪策略集成到蒙特卡洛学习中，我们只需将策略改进步骤从贪婪改为ε-贪婪。

具体来说，MC Basic 或 MC Exploring Starts 中的策略改进步骤旨在解决：

\[ \pi_{k+1}(s) = \arg\max_{\pi \in \Pi} \sum_a \pi(a|s)q_{\pi_k}(s, a) \]

其中 $\Pi$ 表示所有可能策略的集合，解决方案是贪婪策略。

现在，策略改进步骤变为解决：

\[ \pi_{k+1}(s) = \arg\max_{\pi \in \Pi_\varepsilon} \sum_a \pi(a|s)q_{\pi_k}(s, a) \]

其中 $\Pi_\varepsilon$ 表示所有ε-贪婪策略的集合（给定 $\varepsilon$ 值）。这样，我们强制策略为ε-贪婪。解决方案是：

\[ \pi_{k+1}(a|s) = \begin{cases} 1-\frac{|A(s)|-1}{|A(s)|}\varepsilon, & \text{if } a = a^*_k \\ \frac{1}{|A(s)|}\varepsilon, & \text{if } a \neq a^*_k \end{cases} \]

其中 $a^*_k = \arg\max_a q_{\pi_k}(s, a)$。

MC ε-Greedy 算法伪代码：

如果在策略改进步骤中用ε-贪婪策略替代贪婪策略，我们仍然能保证获得最优策略吗？答案是既是又否。肯定的是，在给定足够样本的情况下，算法可以收敛到在集合 $\Pi_\varepsilon$ 中最优的ε-贪婪策略。否定的是，该策略仅在 $\Pi_\varepsilon$ 中最优，但可能不是在 $\Pi$ 中最优。然而，如果 $\varepsilon$ 足够小，$\Pi_\varepsilon$ 中的最优策略接近 $\Pi$ 中的最优策略。

ε-贪婪策略的探索与利用（Exploration and Exploitation）

探索与利用的权衡

探索与利用构成了强化学习中的基本权衡：

探索：策略可能尝试尽可能多的动作，这样所有动作都能被访问和评估。
利用：改进后的策略应该选择具有最大动作值的贪婪动作。
然而，由于当前时刻获得的动作值可能因为探索不足而不准确，我们应该在进行利用的同时继续探索，以避免错过最优动作。

ε-贪婪策略提供了平衡探索和利用的一种方式：

一方面，ε-贪婪策略有更高的概率选择贪婪动作，从而利用估计值。
另一方面，ε-贪婪策略也有机会选择其他动作，从而继续探索。

ε-贪婪策略的最优性

随着 $\varepsilon$ 增加，ε-贪婪策略的最优性变差：

当 $\varepsilon = 0$ 时，策略是贪婪的，在所有策略中是最优的。
当 $\varepsilon$ 很小（如0.1）时，最优ε-贪婪策略与最优贪婪策略一致。
当 $\varepsilon$ 增加（如0.2）时，获得的ε-贪婪策略与最优贪婪策略不一致。
为什么当 $\varepsilon$ 较大时，ε-贪婪策略与最优贪婪策略不一致？以目标状态为例：在贪婪情况下，目标状态的最优策略是保持不动以获得正奖励。然而，当 $\varepsilon$ 较大时，有很高的概率进入禁区并获得负奖励。因此，在这种情况下，目标状态的最优策略是逃离而不是保持不动。

ε-贪婪策略的探索能力

当 $\varepsilon$ 较大时，ε-贪婪策略的探索能力较强：