本文介绍蒙特卡罗方法，详细介绍蒙特卡罗预测。接着会通过多臂老虎机和UCB来介绍探索-利用困境（exploration-exploitationdilemma），然后会介绍On-Policy和Off-Policy的蒙特卡罗预测，最后会简单的比较一下蒙特卡罗方法与动态规划的区别。每一个算法都会有相应的示例代码，通过一个简单的21点游戏来比较On-Policy和Off-Policy算法。
目录
接下来我们介绍解决MDP问题的另外一种方法——蒙特卡罗方法。前面的动态规划方法，我们需要完全的环境动力学(′,|,)。而蒙特卡罗方法只需要经验(Experience)——通过与真实环境交互或者模拟得到的状态、行为和奖励的序列。如果从模拟学习，那么需要一个模型来建模环境，但是这个模型不需要完整的环境动力学，它只需要能采样即可。有的时候显示的定义一个概率分布是很困难的，但是从中获取样本却比较容易。
蒙特卡罗方法通过平均采样的回报(return)来解决强化学习问题。它要求任务是Episodic的，并且一个Episode进入终止状态后才能开始计算（后面介绍的TemporalDifference不需要任务是Episodic，即使Episodic的任务也不用等到一个Episode介绍才能计算）。
首先我们来使用蒙特卡罗方法解决预测问题——给定策略，计算状态价值函数的问题。回忆一下，状态的价值是从这个状态开始期望的回报——也就是期望的所有未来Reward的打折累加。因此很直观的想法就是从经验中估计——所有经过这个状态的回报的平均。我们的目标是估计，但是我们有的只是一些经验的Episode，这些Episode是采样策略得到的。也就是Episode1,1,2,…,～。而t时刻状态是s的回报是如下定义的：
=++1+...+1
而状态价值函数是采样策略时期望的回报：
()=[|=]
蒙特卡罗方法的思想是使用(采样的)平均回报来估计期望回报，根据大数定律，如果采样的次数趋于无穷，那么估计是无偏的。
比如我们要估计()，我们用很多Episodic的经验，这些经验是使用策略获得的。一个Episode里s的每次出现都叫做s的一次visit。当然在一个Episode里s可能多次出现，一种方法只考虑s的第一次visit，这就叫First-Visit蒙特卡罗方法；而另外一种就是每次visit都算，这就是Every-Visit蒙特卡罗方法。这两者的收敛在理论上有一些细微区别，我们这里不讨论，这里我们使用First-Visit蒙特卡罗方法。算法伪代码如下：
图：First-Visit蒙特卡罗方法伪代码
在介绍蒙特卡罗预测的代码之前，我们来学习一下21点游戏的玩法，并且说明为什么之前的动态规划很难解决这个问题，后面我们会使用蒙特卡罗方法来估计状态的价值函数。
这个游戏有一个庄家和一个玩家(我们这里假设只有一个玩家)，有一副扑克牌，他们的目标是使得手中所有的牌加起来尽可能大，但是不能超过21（可能等于），最终谁的大谁获胜，如果一样大就是平均(Draw)。所有的花牌(Face，也就是J、Q、K)都算作10，Ace可以算1也可以算11。游戏开始时庄家和玩家都会发到两张牌，庄家的一张牌是亮出来的，而玩家的两张牌是不亮的。如果这两张牌是21点(一个Ace和一个花牌或者一个10)，那么就叫一个natural，如果对手不是natural，那就获胜，否则是平局。如果都不是natural，那么玩家可以有两种选择，继续要牌(hit)或者不要(stick)。如果继续要牌之后超过21点，就叫爆了(goesbust)，那么庄家获胜。如果没有爆就停止要牌，那就轮到庄家要牌，庄家如果爆了，那就玩家获胜，否则就比最终的大小来区分胜负或者平局。
从游戏的技巧来看（作者在学习强化学习之前也没玩过，所有总结的不一定正确），玩家需要根据庄家亮的牌以及自己牌的和来决定是否继续要牌。同样庄家可能需要根据自己的点数以及玩家的牌的张数以及玩家要牌的快慢表情等(如果是跟机器玩可能就无表情了？机器能像人那样使用表情骗人吗？——明明分不高故意装得很有信心，从而引导对手爆掉)来决定是否继续要牌。另外就是Ace的使用，如果把Ace算成11也没有超过21点，那么在要牌肯定不会爆掉，但是有可能分变小，比如现在是3+Ace，我们可以认为是4点或者14点，但似乎都有点少，那么我们再要一张。如果是8，那么Ace只能算成1，否则就爆了(22)，这样的结果就是12点。
由于有两个角色——庄家和玩家，玩的好的Agent可能还要对对手建模，甚至还要利用对手的表情这样的信息，包括用表情来骗人。这里为了简单，我们假设看不到表情，而且我们的Agent是玩家，而庄家使用一个固定的策略：如果得分达到或者超过17就stick，否则就一直hit。
我们可以用MDP来对这个游戏进行建模，这是个有限的MDP，而且是Episodic的，游戏肯定会结束。对于结束状态，获胜、失败和平局，Reward分别是+1、-1和0。没有结束的状态的Reward都是0,打折因子是1。玩家的Action只有stick和hit两种。状态是玩家的牌和庄家亮出来的那种牌（这部分信息是玩家可以获得的所有信息）。此外为了简单，我们假设发牌的牌堆是无限的（也就是每种牌都可能无限张，因此记住已经发过的牌是没有什么意义的，但实际的情况是有区别的，如果拿过一张Ace，那么再拿到Ace的概率会变化）
玩家的状态有多少种呢？首先是自己的当前得分，因为如果当前不超过11点，那么必然可以要牌而不爆掉，因此状态是12-21共10种可能。而另外的信息就是庄家亮牌ace-10共十种（花牌和10没区别）。还有一点就是Ace，如果玩家有一个Ace而且可以把它算作11而不爆，那么这个Ace就叫可用(Usable)的Ace。如果Ace算作11就爆了，那么它只能算11，也就是不能再（根据不同情况）变化了，也就不“可用”了。如果Ace可以算11，那么我们一定把它算成11，因为如果算成1，那么分就一定小于等于11（否则就爆了），那么我们一定会继续要牌，这个状态是不需要决策的，直接变成一个新的状态。
关于“可用”的Ace算11可能有些难以理解，我们通过一个例子来说明。假设现在玩家手里的牌是2+3+Ace，这个Ace是“可用”的，我们现在的状态是16点并且有一个“可用”的Ace。如果我们把Ace当成1，那么也可以增加一个状态，2+3+Ace，但是这个状态我们一定会hit。所以我们不需要任务这种状态存在。因此这个MDP一共有10102=200个状态。
为什么这个问题很难用动态规划来解决呢？因为动态规划需要知道(′,|,)，比如现在的牌是3+8+2，如果我们采取hit(要牌)，我们也许还能计算变成3+8+2+4的概率，但是reward是多少呢？此外如果我们stick，那么我们的状态会取决于庄家的行为并且最终进入终止状态，这个是很难计算的（因为我们不知道没有亮的牌是多少）。而使用蒙特卡罗方法就很简单，我们不需要知道这些概率，只需要根据某个策略来采取行为就可以了，而环境动力学我们只需要随机模拟就可以了。
首先我们来简单的阅读一些Blackjack环境代码。代码在envs/blackjack.py里。要点都在注释里了，请读者仔细阅读注释。
玩家的牌存在self.player里，而庄家的牌存在self.dealer里，状态是3元组。3元组的第一个是spaces.Discrete(32)，Discrete(32)的范围是0-31。游戏中没有0的牌，1-31表示玩家的牌的和，注意如果玩家到了21点肯定不会再要牌，因此即使爆了最大和也最多是20+11=31，其实根据我们的分析12以下也没必要有，不过有也没关系。3元组的第二个是spaces.Discrete(10)，1-10表示庄家亮牌的点数。3元组的第三个元素用0和1表示是否有可用的Ace。
代码如下，非常直观，请读者对照前面的伪代码阅读代码和注释。
最后我们测试简单的策略——不到20就要牌，否则就停止的策略，看看它在不同状态下的价值函数：
如果我们运行jupyternotebook的代码，可以得到下图的结果。可以看到经过500k次迭代后价值函数非常平滑，而10k次迭代还是不平滑的，也就是误差比较大。我们发现(验证)这个策略并不好：从图中可以看出，只有一上来我们(agent)的点数大于20点才会赢，事实上如果我们知道庄家的策略，我们一上来到了18点就可以停止要牌了，但是我们很激进的要超过19才停止，这显然很容易爆掉。所以这个策略基本就是输的。
前面介绍的是使用蒙特卡罗方法来求解一个策略的状态价值函数，而行为状态函数也是类似的算法，只不过采样后累加的key是s-a而不是s而已。这里就不赘述了。
和之前的策略迭代类似，我们可以用蒙特卡罗预测替代基于动态规划的策略评估，然后不断提升策略。这里我们计算的是行为价值函数q(s,a)而不是状态v(s)。
0→0→1→1→2→...→→
这里使用的策略提升是贪婪的方法：
为什么这个方法可以提升策略呢？我们仍然可以使用前面的策略提升定理来证明：
这个算法有两个假设：蒙特卡罗迭代的次数是无穷的（才能逼近真实的价值函数）；ExploringStart。前者我们可以忽略，因为迭代足够多次数一般就够了，而且我们之前也讨论过价值迭代，我们不需要精确的估计策略的价值就可以使用价值提升了。这里的关键问题是ExploringStart，初始状态0因为游戏是随机初始化的，因此所有可能的初始状态我们都可能遍历到，而且随着采样趋于无穷，每种可能初始状态的采样都是趋于无穷。与0对应的0可能有很多，但是有可能我们的策略会只选择其中一部分，那么有可能我们搜索的空间是不完整的。一种办法就是ExploringStart，就是强制随机的选择所有可能的(0S和(0))，但这样有问题——我们的策略探索过(0,0)之后发现它不好，正常的话，它碰到0S0后就避免0了，但是我们强迫它随机(平均)的探索(0,0)和(0,1)，其实是浪费的。这个问题我们留到后面来解决，我们首先假设是ExploringStart的，看看蒙特卡罗预测的伪代码。
通过上面的算法，我们就可以得到最优的策略如下图所示。
这里学到的策略大致是：如果有可用的Ace，那么一直要牌直到18点，这显然是有道理的，因为我们知道庄家是要到17点为止。如果没有Ace，如果庄家亮出来的牌很小，那么我们到11或者12点就停止要牌了。为什么这是最优的？作者也不清楚，知道的读者可以留言告诉我。
这一节我们不会实现ExploringStart的算法，原因前面我们讲过了，这个算法并不高效和通用，我们之后的内容会介绍没有ExplroingStart的算法并用它们来解决21点游戏。
当然如果我们知道这个K个手臂的均值，那么我们每次都选择均值最大的那个投币，那么获得的期望回报应该是最大的。
可惜我们并不知道。那么我们可能上来每个都试一下，然后接下来一直选择最大的那个。不过这样可能也有问题，因为奖励是随机的，所以一次回报高不代表真实的均值回报高。当然你可以每个都试两次，估计一下奖励的均值。如果还不放心，你可以每个都试三次，或者更多。根据大数定律，试的次数越多，估计的就越准。最极端的一种做法就是每个手臂都投一样多的次数；另外一种极端就是碰运气，把所有的机会都放到一个手臂上。后一种如果运气好是最优的，但是很可能你抽到的是回报一般的甚至很差的手臂，期望的回报其实就是K个手臂的平均值。前一种呢？回报也是K个手臂的平均值！我们实际的做法可能是先每个手臂都试探几次，然后估计出比较好的手臂（甚至几个手臂），然后后面重点尝试这个(些)手臂，当然偶尔也要试试不那么好的手臂，太差的可能就不怎么去试了。但这个“度”怎么控制就是一个很复杂的问题了。这就是exploit-explore的困境(dilemma)。利用之前的经验，优先“好”的手臂，这就是exploit；尝试目前看不那么“好”的手臂，挖掘“潜力股”，这就是explore。
一种策略(Policy)的Regret(损失)为：
不要被数学公式吓到了，用自然语言描述就是：最理想的情况是n次都是均值最大的那个手臂()，不过我们并不知道，[()]是这个策略下选择第j个手臂的期望。那么R就是期望的损失，如果我们的策略非常理想，这个策略只尝试最好的手臂，其它不试，那么R就是0。
但是这样的理想情况存在吗？很明显不太可能存在（存在的一种情况是k个手臂的均值一样）。那么我们的策略应该尽量减少这个损失。LaiandRobbins证明了这个损失的下界是logn，也就是说不存在更好的策略，它的损失比logn小（这类似于算法的大O表示法）。所以我们的目标是寻找一种算法，它的损失是logn的。UCB就是其中的一种算法：
每次决策之前，它都用上面的公式计算每个手臂的UCB值，然后选中最大的那个手臂。公式右边的第一项是exploit项，是第j个手臂的平均回报的估计。这个值越大我们就越有可能再次选中它。第二项是explore项，是第j个手臂的尝试次数，越小这个值就越大，也就是说尝试次数越少的我们就越应该多尝试。当=0时，第二项为无穷大，所以这个算法会首先尝试完所有的手臂（explore），然后才会选择回报最大的那个(exploit)，试了之后这个手臂的平均值可能变化，而且增加，explore值变小，接着可能还是试最大的那个，也可能是第二大的，这要看具体情况。
另一种极端就是k个手臂都差不多（比如都是一样的回报），那么exploit项大家都差不多，起决定作用的就是explore项，那么就是平均的尝试这些手臂，由于k各手臂回报差不多，所以这个策略也还不错。处于中间的情况就是有一些好的和一些差的，那么根据分析，大部分尝试都是在好的手臂上，偶尔也会试一试差的，所以策略的结果也不会太差。
On-Policy的策略通常是soft的，也就是s∈S,a∈A(s),π(a|s)>0。因此soft的策略在状态s时对于所有的Action都有一定的概率去尝试，但是最终会有某个(些)Action的概率会比较大从而形成比较固定的策略。为什么蒙特卡罗控制要求策略是soft而之前的动态规划不需要呢（还记得之前的策略提升都是用到固定的贪婪的策略吗）？
我们看一下这两种方法的backup图，从图中我们可以看出，在动态规划的时候，我们是“遍历”一个状态所有Action，以及Action的所有新状态。通过这种类似广度优先的方式递归的方式，我们遍历了所有空间。而蒙特卡罗方法我们是通过采样的方法一次访问一条“路径”，如果策略是固定的，那么我们每次都是访问相同的路径。
这一节我们会介绍ε-贪婪算法，它在大部分情况下(1-ε的概率)会使用贪婪的策略选择a使得q(s,a)最大，但是也会有ε的概率随机的选择策略。因此对于“最优”行为的概率是1-ε+ε/|A|（因为随机也可能随机到最优的行为），而其它行为的概率是ε/|A|。算法的伪代码如下：
图：On-Policy蒙特卡洛控制算法
这个证明难点是第二行到第三行的不等式，它利用了这样一个结论：n个数的“线性组合”小于等于最大的那个数。所谓的线性组合就是n个数分别乘以n个系数在加起来，这n个系数是大于等于0小于等于1并且和为1的。我们以两个数为例，假设1≤2：
同样三个数的情况可以用类似的方法证明。我们再回过头来看上面的不等式，假设状态s下有n种行为，那么第三行就是n个数((,)aπ(s,a))的线性组合，因为这n个数的系数都是大于0小于1的，而且其和是1：
如下图所示，蒙特卡罗控制是这样优化的，注意和动态规划不同，蒙特卡罗控制一上来是有Q，然后做ε-贪婪的提升，然后计算新的Q，不过因为蒙特卡罗是采样的近似，所以图中的蒙特卡罗的预测不是精确的预测(,)，而是它的近似，所以图中的线没有接近上端。
图：蒙特卡罗控制的GPI
然后是实现ε-贪婪策略的蒙特卡罗控制函数mc_control_epsilon_greedy：
注意和伪代码比，我们没有“显式”定义新策略′π′，而是把当前策略定义为Q(s,a)的一个函数policy=make_epsilon_greedy_policy(Q,epsilon,env.action_space.n)，因此Q(s,a)发生变化时，对于的函数就会发生变化。
运行后我们把V(s)画出来，如下图所示。
我们可以看出，如果一上来手上的牌就大于18，我们最优的胜率是大于0的(当然也会可能输，因为庄家大于17就停止要牌，仍然有一定概率比我们大)。
前面的ε-贪婪策略可以解决ExploringStart的问题，但是带来一个新的问题，它永远只能学到ε-soft的策略，用于决策的时候还去“探索”其实是不好的。本节我们介绍Off-Policy的蒙特卡罗预测，和前面的On-Policy策略相比，Off-Policy有两个不同策略：目标策略(targetpolicy)和行为策略(behaviorpolicy)。目标策略就是我们解决问题需要学习的策略；而行为策略是用来生成Episode的策略。如果目标策略和行为策略相同，那就是On-Policy策略了。
本节我们解决预测问题，假设目标策略和行为策略都已知的情况下计算其价值函数。假设目标策略是，而行为策略是b，我们的目的是根据b生成的Episode采样来计算()或(,)。为了通过b生成的Episode能够用来估计，我们要求如果(|)>0则(|)>0，这叫做b是的coverage。为什么要有coverage的要求？因为如果我们要估计的策略(|)>0，而(|)=0，那么就不可能有Episode会在状态s是采取行为a，那么就无法估计(|)了。
coverage的另外一种说法就是：如果(|)=0那么一定有(|)=0。因此策略b一定是随机的策略，为什么？因为b如果是确定的策略，对于任何状态，只有一个使得(|)=1，其余的都是0。因为b是的coverage，所以除了j，其余所有的(|)=0，因此只有(|)>0，因此它必须是(|)=1，这样和b就是相同的策略，这显然不是Off-Policy策略。
因此在Off-Policy控制里，行为策略通常是随机的，它会“探索”，而目标策略通常是固定的贪心的策略，它更多的是“利用”。几乎所有的Off-Policy策略都使用重要性采样(ImportanceSampling)方法，这是根据一个概率分布来估计另外一个不同的概率分布的常见方法。我们希望估计的是策略，而实际采样用的是b生成的Episode。因此我们在计算平均的回报时需要对它乘以一个采样重要性比例(importance-samplingratio)来加权。通俗的解释就是：(|)的概率是0.2，而(|)=0.4，那么我们需要乘以2。给定初始状态和策略，再给定任意状态-行为轨迹(trajectory)，我们可以就是其条件概率——在给定策略下出现这个轨迹的概率。
为了估计()，我们可以简单的用重要性比例加权平均回报：
这种平均方法加普通重要性采样(ordinaryimportancesampling)，另外一种叫加权重要性采样(weightedimportancesampling):
普通重要性采样是无偏的估计，而加权重要性采样是有偏的估计；前者的方差很大，而后者较小。Off-Policy预测的伪代码如下：
图：Off-Policy蒙特卡罗预测
有了Off-Policy预测之后，我们很容易得到Off-Policy蒙特卡罗控制。伪代码如下：
注意这个代码和上面代码最后两行的差别。首先因为我们的策略是确定的策略，因此只有一个Action的概率是1，其余的是0。因此如果状态是，那么策略会选择Q最大的那个a，也就是max(,)，如果≠()，则说明(|)=0，因此和上面算法的条件一样，可以退出for循环，否则就更新W，如果执行到最后一行代码，说明(|)=1，所以分子是1。
核心的函数是mc_control_importance_sampling，代码和伪代码几乎一样，请读者参考伪代码阅读：
我们可以看出结果和前面的On-Policy算法差不多，但是运算速度会快很多，读者可以自行比较一下。
动态规划需要模型p(s’,r|s,a)；而蒙特卡罗方法不需要，它只需要能获得采样的Episode就行。因此动态规划也称为基于模型的(modelbased)方法；而蒙特卡罗方法被称为无模型的(modelfree)方法。基于模型的方法需要知道环境的动力系统，有些问题我们很容易知道环境动力系统，但是还有很多问题我们无法直接获得。如果我们还想使用动态规划，我们就必须用一个模型来建模环境，这本身就是一个很复杂的问题。比如前面我们的21点游戏，想完全建模其动力系统是很困难的。
动态规划是有bootstrapping的，()和(,)都需要先有估计(初始值)，然后通过迭代的方法不断改进这个估计。
蒙特卡罗方法是offline的，需要一个Episode结束之后才能计算回报。等介绍过TD(λ)之后，与constant-αMC(一种后面我们会介绍的蒙特卡罗方法)等价的TD(1)可以实现online计算。这样如果不是Episode的任务（比如用于不结束状态的连续的任务），或者有些任务如果策略不对可能永远无法结束，比如后面我们会介绍的WindyGridworld。
如下图所示，动态规划会”遍历”所有的子树，而蒙特卡罗方法只采样一条路径。