心得&复述知识体系：《强化学习》中的蒙特卡洛方法 Monte Carlo Methods in RL

前言： 刚刚读完 Sutton 的《强化学习（第二版）》第5章：蒙特卡洛方法。为了巩固本章收获，笔者将在本文中用尽量简单直白的语言复述本章的思想，各个知识点之间的关系。同时，这方便笔者日后进行复习，也与他人分享了心得。

本文目录：

• 各小节间结构关系
• 补充知识点与心得
  • 重要度采样比心得
  • 增量式实现更新公式简单推导
  • 单状态MDP中，策略下的期望
• 实例代码

笔者阅读的是中文书籍，提到的具体公式笔者将给出其所在的英文版本的页码，英文书籍原文见 Sutton 本人官网：http://incompleteideas.net/book/the-book.html。

本章目录：5.1 蒙特卡洛预测 5.2 动作价值的蒙特卡洛估计 5.3 蒙特卡洛控制 5.4 没有试探性出发假设的蒙特卡洛控制 5.5 基于重要度采样的离轨策略 5.6 增量式实现 5.7 离轨策略蒙特卡洛控制 5.8 折扣敏感的重要度采样 5.9 每次决策型重要度采样 5.10 本章小结

各小节间结构关系

首先，本章介绍中指出蒙特卡洛的优点与特殊性，即：

• 无需拥有完备的关于环境的信息，蒙特卡洛方法从真实或模拟的环境中交互采样即可；
• 蒙特卡洛是基于每一幕进行改进的，而非每一步（而非每一次动作）进行改进（be incremental in an episode-by-episode sense, but not in a step-by-step (online) sense）；
• 蒙特卡洛方法在马尔科夫性不成立时性能损失较小，因为不需要用后继状态的估计值来更新当前的估值。

基于上述特点，在已知环境中的很多幕的序列的情况下，“5.1 蒙特卡洛预测”提出了两种蒙特卡洛预测方法：

• 首次访问型MC预测算法（first-visit MC method）；
• 每次访问型MC预测算法（every-visit MC method）。

“5.2 动作价值的蒙特卡洛估计”则告诉读者：在实际环境中，很难保证所有“状态-动作”都出现过一遍，因此可能有采样不足的问题。因此，我们可以通过设置每个“状态-动作”的第一次采样的概率都不为0，来进行 试探性出发 。或者使用别的思想。接下来的讨论中， 我们先保留试探性出发的假设 。

基于广义策略迭代（GPI）的思想，“5.3 蒙特卡洛控制”讨论了使用贪心更新策略下，蒙特卡洛算法的向最优策略的收敛性（数学上可以证明，见P97-98），并且，给出了 基于试探性出发的蒙特卡洛（蒙特卡洛 ES） 算法框架。

值得注意的是，为了保证蒙特卡洛算法收敛，我们做了两个假设：

1. 试探性出发；
2. 在进行策略评估时有无限多幕的样本序列进行试探。

为了在应用中消除两个假设的影响，我们需要设计算法。基于试探性出发的蒙特卡洛（蒙特卡洛 ES）采用了GPI的思想，即不再要求在策略改进前就完成策略评估，这可以有效消除假设2的影响。

“5.4 没有试探性出发假设的蒙特卡洛控制”以后的内容则是讨论如何消除假设1的影响。

为了消除假设1（“试探性出发”）的影响，我们采用：

• 同轨策略（on-policy）；
• 离轨策略（off-policy）。

在通过策略中，我们观测到的“状态、动作、回报”序列是遵从我们的策略的，在我看来，可以理解为：我们一边观测我们的系统，一边改进它；但是并非在线改进，而是以幕为单位进行改进，即遵循：“由策略生成序列-由序列更新动作期望-由期望更新最优动作-进而更新策略” 。其算法框图见书P101：

但是，注意到“由策略生成序列”这个步骤。在很多情况下，我们得到的序列并非是我们完全可控的，即 我们无法由我们自己的策略生产序列 。这就需要一种 能够使用与自己策略无关的序列，来更新自己策略的方法了，即离轨策略。

离轨策略相对复杂，书上分为几个小节对其进行分步讲解：

• “5.5 基于重要度采样的离轨策略”本节中主要讨论了评估离轨序列价值所要用到的概念：重要度采样比，并且提出了“普通重要度采样”与“加权重要度采样”，告诉读者“加权重要度采样”的估计方差为1，而非“普通重要度采样”的无穷，但是“加权重要度采样”是有偏的，偏差会收敛到0。其中，我还对重要度采样比有一点心得，见[1] ；
• “5.6 增量式实现”则对价值更新公式做了一个很简单的推导[2]；
• 现在有了 能够估计离轨策略价值 的前提，可以开始讨论如何对策略进行更新了，“5.7 离轨策略蒙特卡洛控制”给出了 离轨策略MC控制算法 ，并附有算法框图。
• “5.8 折扣敏感的重要度采样”讨论了：如果考虑（回报中的）折扣，那么在离轨策略中，如何考虑回报、更新价值。这减小了方差，更利于收敛，即 折扣敏感的重要度采样 ；
• “5.9 每次决策型重要度采样”讨论了：不考虑折扣，也可减小方差。使用 每次决策型重要度采样 来进行无偏估计即可。

书上给出了2个例子（有代码进行实现）：

1. 二十一点游戏，用于说明蒙特卡洛的基本思想；
2. 单状态MDP，用于说明普通重要度采样的方差不收敛性。我对于证明策略下的期望有一点心得，见[3]。

补充知识点与心得

[1] 重要度采样比心得

重要度采样比定义为：在目标策略和行动策略轨迹下的相对概率。经过推导，即

为什么这么定义这个参数，或者说，长成这样的公式有什么用？

我们来看其使用场景，普通重要度采样：

加权重要度采样：

其中，二者的期望分别接近与，而这个 重要度采样比 在其中的作用为：当观测值贴近策略时，此时取得的G更加重要，影响更大，因此其系数 重要度采样比 增大。

[2] 增量式实现更新公式简单推导

把下式转换为增量式：

书上没有给出，因为太简单了，我在这里证明一下。

即答案：

其中，

[3] 单状态MDP中，策略下的期望

期望 E 为：

解得 E = 1 。

实例代码

源代码来自：github.com/ShangtongZhang/reinforcement-learning-an-introduction/chapter05

实例代码与解析见：https://github.com/PiperLiu/Reinforcement-Learning-practice-zh/blob/master/practice/04-Monte-Carlo-Methods.ipynb

微信编辑器：https://www.mdnice.com/