蒙特卡罗算法蒙特卡罗方法

1.蒙特卡罗方法的基本思想

蒙特卡洛法又称统计模拟法，是利用随机数(或伪随机数)来解决计算问题，是一种重要的数值计算方法。这个方法的名字来源于世界闻名的蒙特卡洛，它是基于概率的。

一个简单的例子就可以说明蒙特卡罗方法。假设我们需要计算一个不规则图形的面积，图形的不规则程度与解析计算(如积分)的复杂度成正比。又是如何用蒙特卡罗方法计算出来的？首先，你把图形放在一个已知面积的盒子里，然后想象你有一些豆子，把豆子均匀地撒到盒子里，散射后数出图形中有多少豆子，然后根据图形内外豆子的比例计算出面积。你的豆子越小，撒得越多，结果就越准确。

2.强化学习中的蒙特卡罗方法

现在我们开始解释强化学习中的蒙特卡罗方法。与上一篇文章中的DP不同，不需要完整的环境知识。蒙特卡洛方法求解最优策略只需要经验，可以在线获得，也可以根据某种仿真机制获得。

需要注意的是，我们只对插曲任务定义蒙特卡洛方法，所谓插曲任务是指无论采用哪种策略π，都会在有限时间内达到结束状态并获得奖励的任务。比如玩桌游，经过有限的几步，总能达到输赢或平局的结果，并获得相应的奖励。

那么什么是体验呢？经验其实就是一个训练样本。比如初始状态s，遵循策略π，最终得到总收益r，这是一个样本。如果我们有很多这样的样本，我们就可以估计在状态S下遵循策略π的预期收益，也就是状态值函数Vπ(s)。蒙特卡罗方法依靠样本的平均回报来解决强化学习问题。

虽然蒙特卡罗方法和动态规划方法有很多不同之处，但蒙特卡罗方法借鉴了动态规划中的许多思想。在动态规划中，我们首先估计策略，计算特定策略π对应的Vπ和Qπ，然后改进策略，最后形成策略迭代。这些思想也适用于蒙特卡罗方法。

3.蒙特卡罗政策评估

首先，考虑用蒙特卡罗方法学习状态值函数Vπ(s)。如上所述，估算Vπ(s)的一个显而易见的方法是对所有达到这种状态的回报进行平均。分为初诊MC法和复诊MC法。这里只考虑第一种MC方法，即在一次疫情中，只记录S的第一次就诊，并取其上的平均回报。

现在我们假设有如下一些样本，取贴现因子γ=1，即直接计算累计收益，有

按照第一种MC方法，对状态为s的epic的累计收益进行平均，vπ(s)∞(2+1–5+4)/4 = 0.5

很容易知道，当我们经历无穷多个epic时，Vπ(s)的估计值会收敛到它的真值。

4.动作值的蒙特卡罗估计

当状态转移概率p(s'|a，s)已知时，我们可以在策略估计后用一个新的价值函数来改进策略，只需要看哪个动作能得到最大的期望累积收益。但是没有准确的状态转移概率是不可行的。所以我们需要估计作用值函数Qπ(s，a)。Qπ(s，a)的估计方法和之前类似，即在状态s下采用动作a时，跟随策略π得到的预期累计收益为Qπ(s，a)，仍然是用平均收益来估计。有了Q值，策略就可以改进了

5.继续探索(保持探索)

我们来讨论一下维护探索的问题。前面说过，我们通过一些样本来估计Q和V，在未来执行估计最大的动作。这里有一个问题，假设a0，a1，a2在某个状态s0下可以执行，如果代理已经估计了两个Q函数值，比如q (s0，A0)，Q(s0，a1)，Q(s0，A0) >: Q(s0，a1)，那么以后只会执行一个确定的动作A0。这样我们就不能更新Q(s0，a1)的估计，得到Q(s0，a2)的估计。因此，我们不能保证Q(s0，a0)是s0下最大的Q函数。

维护探索的思想很简单，就是用软策略代替确定性策略，让所有动作都可以执行。比如其中一种方法是ε-贪婪策略，即在所有状态下，当前最优动作a0以1-ε的概率执行，其他动作A1，a2以ε的概率执行。这样就可以得到所有动作的估计值，然后缓慢地降低ε值，最终使算法收敛，得到最优策略。为简单起见，在下面的MC控制中，我们使用探索开始，即只有在第一步中，所有A都有非零概率被选中。

6.蒙特卡洛控制

我们来看看MC版本的策略迭代过程:

根据前面的说法，价值函数Qπ(s，a)的估计值需要在无穷多集后收敛到它的真值。在这种情况下，策略迭代肯定是低效的。在前面的DP中，我们引入了值迭代算法，即每次只使用值函数的近似值进行迭代，而没有完整的策略估计，这里使用了类似的思路。每个策略的近似值用这个近似值更新得到一个近似策略，最终收敛到最优策略。这种思想叫做广义策略迭代。