前言

 上期介绍了动态规划，本期将介绍蒙特卡罗算法。我们也会称“蒙特卡洛法”，翻译的不同，我们就不深究了，同样，这期笔者会尽量用通俗易懂的语言来让大家能够真正读懂！！！

前期回顾

强化学习:基础知识篇(包含Gym库的简单实践)——手把手教你入门强化学习（一）
强化学习:Markov决策过程(MDP)——手把手教你入门强化学习(二)
强化学习:实践理解Markov决策过程(MDP)——手把手教你入门强化学习(三)
强化学习:动态规划求解最优状态价值函数——手把手教你入门强化学习(四)

一、基本概念

蒙特卡罗法

蒙特卡罗法，也叫作统计模拟方法，我先讲一下它基于模型的思路。现在我们不知道MDP模型的环境，也就是不知道环境中的状态转移概率，这时候我们采取一种思路，利用（蒙特卡洛模拟）大数定律通过多次统计，算期望，我们将环境的状态转移概率计算出来。有了环境模型，这时候我们就可以用上节课讲的动态规划的值迭代来求解贝尔曼期望方程，得出状态动作价值函数，同样也能得到最优策略。但是这种思路需要大量的统计计算，而且实操性不高。那它用的是什么思路呢，是的，它还有不基于模型的思路。

这里肯定有读者就疑惑了，那它到底是基于模型还是不基于模型的强化学习算法？我们判断一个算法是不是基于模型，我们判断的依据就是，它是否显示的利用已知的或者学习的转移状态概率和奖励函数进行状态价值函数的求解或者预测未来的状态。
那这个方法不基于模型的思路是什么呢？这也是我这期博客的重点。我们最终还是把它当做不基于模型的算法。

蒙特卡罗法是一种基于完整回合采样的强化学习方法，通过统计经验回报的平均值来估计状态或动作的价值函数。其核心特点是不依赖环境模型，仅通过实际交互的样本数据进行学习，适用于回合制任务，特点如下：
1 无模型学习
无需事先知道环境的状态转移概率$P(s'|s,a)$获奖函数R(s,a)直接通过与环境交互的样本数据学习。
2 基于完整回合
必须等待一个完整的回合（从初始状态到终止状态）结束后，才利用该回合内的所有经验进行价值函数更新。
3 回报平均
通过多次采样同一状态（或状态-动作对）的回报（Return），计算其平均值作为价值估计。
为了保证估值计算的有效性，蒙特卡罗法会使用更适合自己的估值方法，对此算法有两种策略：1 首次访问蒙特卡罗 2 每次访问蒙特卡罗

首次访问蒙特卡罗（First-Visit MC）

仅统计回合中首次访问某状态的回报。对任意状态s来说，如果在一个完整的Episode中第一次碰到它，就对计数器N(s)进行加1的操作。当然，在一开始，所有状态的N(s)的值肯定都是0。随着访问次数的增加，每个状态的N(s) 的值将交替增加。在对N(s)做加1操作的同时，需要对另一个用于记录总体奖励值的函数S(s)进行加Gt的操作​。然后，可以得到估值

也就是说，只要在Episode中访问一个状态s，且它在这个Episode中第一次出现，就进行“一揽子”操作：
我们通过这个计算公式计算。

只要这么持续下去，根据大数定律，最终V(s)肯定无限趋近于它的数学期望值

这个过程，和不断地扔一个匀质硬币，最终正面朝上和反面朝上的概率都无限接近$\frac{1}{2}$的过程没有什么区别。智能体每次都是在执行一个Episode后，需要回过头来，从第一个状态开始，逐个进行N(s)、S(s)、V(s)的计算。

每次访问蒙特卡罗（Every-Visit MC）

统计回合中每次访问该状态的所有回报。跟首次很相似，唯一的区别就是每次访问蒙特卡罗就是在一个回合内每次遇到状态s都需要做一次更新，不管这个回合内有几个s，而首次访问蒙特卡罗是只有在这个回合第一次遇到状态s才更新，第二次更新就需要等到下一个回合。

二、蒙特卡罗算法流程

下面讲述一下算法流程：
这里我们用每次访问蒙特卡罗进行状态价值评估
1 蒙特卡罗策略评估（Policy Evaluation）
目标：评估给定策略$\pi$的状态价值函数$v{\pi}(s)$或动作价值函数$q{\pi}(s,a)$步骤： 1）生成回合 使用策略$\pi$与环境交互，生成多个完整的回合序列：

2) 计算收获
对每个状态s,计算其后续累积折扣回报：

3) 更新价值函数：
对每个状态s,执行以下操作：

随着回合次数计算的增加，V(s)最终会无限趋近于真实值。

三、优化方法——增量平均

首次访问蒙特卡罗策略估值和每次访问蒙特卡罗策略估值，都可以通过在程序里设置计数器的方式解决求和及求平均值的问题。而在程序中，为了使得计算方便、表达简洁，通常会把这个更新公式写成它的增量平均形式：

可以动态更新均值，无需存储所有历史回报，其中a是学习率，在遇到每一个状态s的时候，我们计算出当前状态的收获，这个收获跟我们估算的状态价值函数进行相减，我们就能知道这个变化量的大小，我们通过这个差异逐步学习，逼近真实的期望值。

这样我们把计算时间复杂度就降下来了。

总结

蒙特卡罗法的过程，是一个通过不断采样让样本丰富起来，进而比较准确地估算出由策略π驱使的某个状态的估值Vπ(s)的过程。一旦准确地计算出这个估值，我们就可以沿用动态规划的方法进行策略优化了。
缺点：
在开始的几十个甚至上百个Episode中，前几次实验结果的方差一定大得惊人，因为这时候我们的初始数据是随机的。最初产生的状态估值都严重偏离真实的估值，是不可信的。

本期介绍了蒙特卡罗法的两种估值方法以及通过增量平均进行优化的方法。

写在最后

 如果想要更深入强化学习的内容，关注我，下期更精彩，感兴趣的友友也可以关注我的csdn账号。
 https://blog.csdn.net/qq_53769632?spm=1000.2115.3001.5343