蒙特卡洛方法学习笔记！西湖大学赵世钰老师《强化学习的数学原理》

本文为学习笔记，内容要点整理自西湖大学赵世钰老师《强化学习的数学原理》。

这门课程从零开始、从数学角度、结合大量例子、循序渐进地揭示强化学习的本质原理。书：https://github.com/MathFoundationRL/Book-Mathematical-Foundation-of-Reinforcement-Learning视频：https://www.bilibili.com/video/BV1gM41167Lz

值迭代和策略迭代都属于有模型的算法，同属于动态规划方法。

如果无模型（model-free），应该如何进行学习？无模型时，就需要依赖数据，数据在统计学习中称为Sample（采样），在强化学习中称为Experience经验。

蒙特卡洛方法的核心思想是使用数据计算来代替策略迭代算法中的模型计算部分。

一、蒙特卡洛均值估计与大数定律

先来看抛硬币的例子。

定义一个随机变量X。

如果正面向上，则X=1。如果背面向上，则X=-1。

目标：计算E(X)，也就是X的平均值。

方法：做很多次实验，得到很多的采样，求这些采样的平均数。公式为：

当样本容量n较小时，这种逼近可能不够精确。然而，随着n的增加，逼近的精度逐渐提高。当n趋向无穷大时，样本均值x̄趋近于随机变量X的期望值E[X]。如下图所示：

数学上，大数定理证明了这一现象。

也就是，对于一个随机变量 X，假设有一组独立同分布样本。上面这两个等式表示 x̄ 是 E[X] 的无偏估计，而且它的方差随著 n 的增大而减小。

注："独立同分布"（Independent and Identically Distributed，简称IID）是一种统计学中的重要概念，指的是多个随机变量之间相互独立，且具有相同的概率分布。换句话说，每一个随机变量都不受其他随机变量的影响。

直观的解释是：当我们对同一个随机事件进行大量重复试验时，事件的平均结果将会趋近于该事件的期望值。

二、蒙特卡洛Basic算法

理解蒙特卡洛Basic算法的关键是将策略迭代算法转变无模型。这就需要理解策略迭代算法和蒙特卡洛均值估计。

策略迭代算法在每个迭代包含两部分，策略估计和策略改进。

也就是给定策略πk，计算状态值vπk。然后根据vπk，计算πk+1。策略改进的公式可以进一步表示为：

那么，如何计算红色部分qπk？

从s出发，选择动作a，分很多个episode，每个episode得到Return Gt，然后求Gt的平均值。（action value原始的定义）

我们可以使用上面的表达式，并基于数据（采样或经验）计算出qπk(s,a)。这便是实现Model-free无模型强化学习的思想。

蒙特卡洛Basic算法描述如下所示：

蒙特卡洛Basic算法和策略迭代算法基本一样，区别在于：

策略迭代算法中的策略估计求解state value，再得到action value。而蒙特卡洛Basic算法直接通数据采样的方式得到action value。

三、蒙特卡洛Exploring Starts算法

MC Basic算法的优点是能够清晰揭示核心思想，其缺点是过于简单，难以实际应用。

然而，MC Basic可以扩展以变得更加高效（集中在数据利用和更新策略两个方向）。

数据利用如何变得更加高效？

考虑一个网格世界的例子，按照策略π执行，我们可以在一集中得到一系列状态-动作对，比如：

每次出现一个状态-动作对，就称为对该状态-动作对的一次Visit（访问）。

MC Basic算法使用了Initial-visit method方法。

也就是说，一个回合仅用于估计初始状态-动作对的动作值(s1,a2)。但是，这种策略不是采样高效的，因为回合也访问了许多其他的状态-动作对，如(s2,a4),(s2,a3)和(s5,a1)。这些访问也可以用于估计相应的动作值。具体如下：

很明显地，这样做没有充分利用数据，subepisode被浪费掉了。

此外，一个状态-动作对可能在一个回合中被访问多次，如(s1,a2)被访问两次。如果我们只计算第一次访问，则称为First-Visit Method（首次访问法）。如果我们计算每一个状态-动作对的访问，则称这样的策略为Every-Visit Method（每次访问法）。

更新策略如何更加高效？

第一种方法是MC Basic算法中使用。在策略评估步骤中，收集所有的从状态-动作对开始的Episode，然后平均回报来估计动作值（action value）。

存在的问题是要等所有的Episode都要收集完，造成时间较长。

第二种方法是使用单个Episode来估计动作值。也就是，得到一个Episode就改进策略，以达到效率提升的目的。

蒙特卡洛Exploring Starts算法

Exploring是指每个状态-动作对都需要至少有一个Episode。也就是算法必须尝试从每个可能的状态-动作对开始，以便能够收集足够的数据来估计每个动作的价值。如果没有足够的探索，算法可能会错过最佳的动作，从而导致较差的结果。

Starts是指从状态-动作对（s,a）开始一个Episode。还有一种方法是指从其他状态-动作对开始，也能经过这个（s,a），但目前无法确保必然经过这个（s,a），所以使用“从状态-动作对（s,a）开始一个Episode”的方法。

其算法过程如下所示：

计算过程是从后向前计算的。其形式为：

事实上，Exploring Starts算法是非常困难的。对于许多应用程序来说，很难收集从每个状态-动作对开始的回合。那么，能否去掉Exploring Starts的要求呢？

四、蒙特卡洛ε-Greedy算法

引入soft policy（采用随机策略），也就是每个动作都有可能被选择。因为如果从一个状态-动作对（s,a），这个Episode足够长，就能够确保任一状态-动作对（s,a）都能被访问到。

这样就可以去掉Exploring Starts。

soft policy具体是指什么？可以是ε-Greedy policy。

蒙特卡洛ε-Greedy算法与Exploring Starts算法，不同点在于采用了ε-Greedy策略。

参考资料