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

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

本文目录：

笔者阅读的是中文书籍，提到的具体公式笔者将给出其所在的英文版本的页码，英文书籍原文见 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 蒙特卡洛预测”提出了两种蒙特卡洛预测方法：

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

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

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

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

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

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

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

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

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

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

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