强化学习教程（四）：蒙特卡罗改进策略

hdy

01

引言

强化学习是机器学习的一个领域，它引入了一个必须在复杂环境中学习最优策略的智能体概念。该智能体通过根据环境状态采取行动并获得奖励来进行学习。强化学习是一个颇具挑战性的课题，与其他机器学习领域有着显著差异。正因如此，它仅适用于其他方法无法解决的特定问题。

强化学习的惊人之处在于，相同的算法可以使智能体适应完全不同的、未知的且复杂的条件。特别是蒙特卡洛算法，它不需要任何关于环境动态的先验知识。这一特性极具实用价值，因为在现实生活中我们通常无法获取此类信息。

在上一篇文章中我们已经探讨了蒙特卡洛方法的基本原理，本文将重点介绍改进这些方法的特殊技术。

注：为了充分理解本文所述概念，强烈建议先熟悉本系列文章第三部分介绍的蒙特卡洛算法核心概念。

02

  ε-greedy policies

本文是前篇内容的逻辑延续——在前文中我们介绍了运用蒙特卡洛方法估算价值函数的核心思想，同时深入探讨了强化学习中著名的"探索-利用困境"问题：若仅采用贪婪策略，该问题将阻碍智能体的高效学习。本文将重点分析一种改进算法——基于ε-贪婪策略的运用。

• 定义
  
  

若对于所有状态 s ∈ S 和动作 a ∈ A 均有 π(a|s)> 0，则该策略称为soft策略。换言之，在给定状态 s 下选择任何动作的概率均不为零。

当对于所有 s ∈ S 和 a ∈ A 满足 π(a|s) ≥ ε/|A(s)| 时，该策略称为 ε-soft策略。

实际应用中，ε-soft策略通常接近确定性策略（ε为一个极小正数），即存在一个极高概率被选中的主导动作，其余概率则以确保每个动作至少具有 p ≥ ε/|A(s)| 的最小概率方式分配给其他动作。如果一个策略在概率为 1-ε 的情况下选择收益最大的行动，在概率为 ε 的情况下随机选择一个行动，那么这个策略被称为 ε -贪婪策略。



不同的策略类型

根据ε-贪婪策略的定义，所有动作都能以均等概率 p = ε/|A(s)| 被选中。而剩余概率（1-ε）则全部赋予具有最大回报的动作，因此该动作的总选择概率为 p = 1 - ε + ε/|A(s)|。

关于ε-贪婪策略的利好消息是：它们可以被整合进策略改进算法！理论表明，广义策略迭代（GPI）并不要求更新后的策略必须严格遵循价值函数的贪婪选择，只需向贪婪策略方向逼近即可。具体而言，若当前策略是ε-soft软策略，那么任何基于V函数或Q函数更新的ε-贪婪策略，都能保证其性能优于或等于原策略π。

03
  蒙特卡洛控制

在蒙特卡洛方法中寻找最优策略的过程，与我们先前文章中讨论的基于模型的算法过程一致。首先初始化任意策略π，随后策略评估与策略改进两个步骤交替进行。

术语control特指寻找最优策略的运算过程。

• Q函数的计算通过采样大量事件轨迹并对回报值取平均来实现。
• 策略改进则是通过使当前策略相对于价值函数变得贪婪（或ε-贪婪）来完成。
• 
  
  

理论上，我们需要运行无限次事件轨迹才能获得Q函数的精确估计。但实际应用中无需如此，甚至可以在每次策略改进时仅执行单次策略评估迭代。

另一种可行方案是仅使用单条事件轨迹来更新Q函数和策略。在每条轨迹结束后，利用计算得到的回报值评估策略，而策略只针对该轨迹中访问过的状态进行更新。

在所实现的探索性起始算法版本中，尽管数据采集过程中采用了不同策略，系统仍会综合考虑所有（状态，动作）对的回报值。

采用ε-贪婪策略的算法版本与上述版本基本一致，仅存在以下细微差异：

• 策略π初始化为任意ε-soft策略；
• 完整轨迹（包含起始状态动作对(S₀, A₀)）均严格遵循策略π生成；
• 策略更新过程中，π始终保持ε-贪婪特性：
• 
  
  

04

举个栗子

通过理解蒙特卡洛控制的工作原理，我们现在已经为寻找最优策略做好了充分准备。让我们回到前文中的二十一点游戏示例，但这次我们将重点分析最优策略及其对应的Q函数。基于这个案例，我们将得出若干重要结论。

• Q函数
  
  

这幅图展示了最优策略下的Q函数示例，但实际Q函数可能存在显著差异。以玩家持21点（无可用Ace）且庄家持6点时选择要牌的q值-0.88为例：虽然在此情况下玩家必输，但q值为何不是-1？这里主要有两个原因：

• 首先，训练初期算法无法准确判断各状态下的最优动作，因此几乎是随机选择动作。结果可能是，在某些时候，两个行动之间的 q 值差异会变得相当大。因此，在策略改进步骤中，算法总是会贪婪地选择回报最大的行动。因此，其他收益较低的行动将永远不会再被采样，它们的真实 q 值也不会被充分计算。值得注意的是，在庄家持7点的相似状态下，q值确实收敛至理论值-1，因此，我们可以看到，由于算法的随机性，对于相似的状态，算法的收敛结果是不同的。
• 其次，我们将学习率α设定为0.005，这意味着算法需要较长时间才能收敛到正确值。若采用超过500万次迭代或调整α值，估计值可能更接近-1。
  
  

• 最佳策略
  
  

要从构建的Q函数直接推导出最优策略，我们只需比较同一状态下"要牌"和"停牌"两个动作的回报值，选择q值更高的动作即可。

根据构建的 Q 函数推导出最佳策略

实验表明，最终得到的二十一点策略与真实最优策略极为接近，这证明我们为ε和α选择的超参数值设置得当。需要注意的是，不同问题对应的最优超参数值各不相同，必须根据具体情况进行调整。

05

On-Policy VS Off-Policy

考虑一种强化学习算法，它通过生成智能体的轨迹样本来估计在给定策略下的Q函数。由于某些状态出现得非常稀少，算法会显式地多次采样这些状态，以确保它们被充分学习。那么，这种方法是否存在什么问题？

事实上，样本的获取方式会影响价值函数的估计，从而也会影响策略的优化。理想情况下，我们会假设采样得到的数据代表了真实的状态分布，这样得到的最优策略也是正确的。然而，这个假设通常是不成立的：实际数据的分布与采样策略不同。

不考虑数据分布差异、直接使用非常规采样数据求解策略的方法称为On-Policy策略方法。我们之前实现的蒙特卡洛控制就是典型的On-Policy策略方法。

另一类算法则考虑数据分布问题，其典型解决方案是采用双策略框架：

• 行为策略：用于生成采样数据
• 目标策略：通过学习获得，最终形成智能体的最优策略
  
  

这种同时使用行为策略和目标策略的算法称为Off-Policy策略方法。虽然实际应用中这类方法更复杂、更难收敛，但往往能得到更精确的解。

Off-Policy政策使用行为政策对数据进行采样，但需要进行调整，以便适当地学习目标政策

要通过行为策略b估计目标策略π，必须满足覆盖准则：对于所有状态s和动作a，当π(a|s)>0时，必须保证b(a|s)>0。换言之，目标策略可能采取的所有动作，在行为策略中发生概率必须不为零，否则该动作将无法被评估。

接下来的核心问题是：当使用行为策略采样时，如何评估目标策略？这就引出了重要性采样技术——几乎成了所有Off-Policy策略方法的核心解决方案。

06
重要性采样

在机器学习算法中，计算期望值是非常常见的操作。然而，有时这可能会变得非常困难，需采用特殊的方法来实现。

• 动机
  
  

假设我们有一个关于 f(x) 的数据分布（其中 x 是一个多维向量）。我们用 p(x) 来表示其概率密度函数。

我们希望找到它的期望值。根据积分的定义，可以写成：

然而由于某些原因，这个表达式可能难以计算。实际上，精确计算积分值可能非常复杂，特别是当x维度很高时。在某些情况下，甚至无法从p分布中采样。

正如我们已经了解的，蒙特卡洛方法可以通过求平均值来近似期望值：

• 核心思想
  
  

重要性采样的核心在于通过另一个变量（行为策略）的分布来估计目标变量（目标策略）的期望值。设另一个分布为q，通过数学推导可以得到基于q分布计算p分布期望值的公式：

最终我们可以将表达式改写为部分和的形式，用于计算原始期望值：

这一方法的精妙之处在于：现在所有采样点x都来自新分布q，若从q采样比从p采样更高效，将显著提升估计效率。

• 应用
  
  

最终推导出的公式完美契合Off-Policy方法！为了明确理解，让我们解析其每个组成部分：

• Eₚ[f(x)] 表示我们最终要求解的目标策略π在状态s下的期望回报G
• x 对应于我们要估算其返回值的单个状态s；xᵢ 是通过状态s的N条轨迹中的一条
  
  

• f(xᵢ) 是状态s对应的回报G
  
  

• p(xᵢ) 是目标策略π下获得回报G的概率
  
  

• q(xᵢ) 是行为策略b下获得回报G的概率
  
  

由于采样数据仅通过行为策略b获得，在公式表示中我们无法使用x ~ p(x)（只能使用x ~ q(x)），这正是需要采用重要性采样的关键原因。

不过，要将重要性采样应用于蒙特卡洛方法，我们需要对前述公式稍作调整：

• 核心目标：计算策略π下的Q函数
  
• 实际操作：通过策略b估计Q函数
  
• 关键技术：利用重要性采样公式，基于策略b估计策略π的Q函数
  
• 概率计算：我们要计算的是，在当前状态 s 和智能体的下一个行动 a 的情况下，智能体获得奖励 G 的概率。
  
  
  那么期望概率可以表示为智能体从 sₜ 到终端状态的轨迹概率。这个概率可以写成：在策略（π或b）下连续动作选择概率与状态转移概率p的连续乘积
  
  

• 关键简化：虽然转移概率p未知，但由于分子分母中都包含p，相除时会被约去。
  
  
  

     最终得到的比例ρ称为重要性采样比

• 最终应用：将ρ代入原始公式，获得策略π下Q函数的估计值
  
  

若需计算V函数而非Q函数，方法完全类似：

我们之前实现的二十一点算法属于on-policy策略方法，因为其数据采样和策略改进使用的是相同的策略。

07

增量式更新机制

为优化蒙特卡洛方法的实现，可采用增量式更新机制。前述伪代码需要反复重算状态-动作值的平均值，若以数组形式存储(S,A)对的回报值并在新增数据时重新计算均值，这种实现效率较低。

更高效的解决方案是将平均值公式改写为递归形式：

此公式使我们能够基于前次平均值和新回报来增量更新，将每次迭代的计算复杂度从线性O(n)降至常数O(1)，同时无需存储历史数据数组。该技术同样适用于其他需要持续更新平均值的算法场景

• Constant-α MC
  

通过观察上述更新规则，我们可以注意到其中的 1/n 是一个常数项。我们可以通过引入 α 参数来推广这个增量式实现方法，用这个可自定义的参数（取值范围 0 到 1）来替代 1/n。

通过引入α 参数，我们可以调节新观测值对先前估计值的影响程度。这个调整也会影响收敛过程：

如上图所示：

• 较小的 α 值会使算法收敛到真实值的速度变慢，但一旦估计平均值接近真实平均值时，方差就会变小。
• 较大的 α 值会使算法更快地收敛到真实值，但在估计平均值接近真实平均值时，方差会变大。
  
  

08

结论

至此，我们已经理解了on-policy与off-policy方法的本质区别。虽然off-policy策略方法通常更难调参，但其最终能产生更优策略。作为目标策略值调整的示例，重要性采样技术是强化学习中绝大多数off-policy策略方法的核心支柱之一。

打团先救我

yikao33

蒙特卡洛算法

luobin

👍👍👍👍👍

weikamd

凌浩

luobin

👍👍👍👍👍👍👍

蓝色欧文

AMT

yikao33

蒙特卡罗改进策略