2.1　蒙特卡罗方法

蒙特卡罗方法不是指某一种特定的算法，而是单纯指基于随机采样的方法进行计算学习［23］。关于蒙特卡罗方法，有一个很经典的计算圆周率的例子。我们知道半径为r的圆面积是πr2，而其外接正方形的面积是4r2。因此圆和其外接正方形面积的比值是。这样，我们从正方形内随机采样点（p1，p2，···，pn），当n足够大的时候，采样点在圆内的个数t和总采样数n满足：

因此，当我们知道t和n，π的值也就算出来了。

从上面的例子可以看到，可以通过大量的采样，得到一些理论值的近似值。在强化学习中，这就是V值和Q值。

2.1.1　蒙特卡罗方法预测状态V值

在蒙特卡罗方法中，我们从初始状态s0出发，基于一定的策略π随机选取动作，使状态转化为终结状态send，同时获得一个奖励r，以此作为一个回合。当我们不断重复这个过程N次，就可以得到N条从s0出发的轨迹τ，以及其对应的结束状态和奖励。当N非常大的时候，根据大数定律，我们可以认为这个奖励序列（r1，r2，r3，···，rn）的均值ravg就是状态s0在策略π下的V值，即

举个例子，我们下象棋时，看到某个残局的时候，都会在脑海里模拟接下来的棋局，以此判断在这个局面下，是红方还是黑方占据优势。这个模拟的过程，就可以类比为蒙特卡罗方法，而预测的这个局面的优势，就可以理解为状态的V值。

在计算s0的V值的均值时，可以有两种策略，一种是首次访问（first-visit）蒙特卡罗方法，一种是每次访问（every-visit）蒙特卡罗方法。因为在每次生成轨迹τ的时候，是有可能多次经过状态s0的。那么首次访问蒙特卡罗方法只计算第一次经过s0时的回报，而每次访问蒙特卡罗方法则把每次经过s0的回报都用在均值计算中。

2.1.2　蒙特卡罗方法预测Q值

但是，在没有模型的时候，一般我们选择估计Q函数，这里最主要的原因是，考虑了动作，Q函数的估计会比V值的估计更直观一些。因为我们学习的目标是找到一个使回报最大的策略，在知道状态s的V值的情况下，我们的策略是

而在无模型的情况下，p（s′|s，a）是不可知的，甚至r（s，a）也是很难获得的，因此即使我们计算出了每个状态s下的V值，我们还是没有办法选择一个策略。而反过来，如果我们知道了Q（s，a），我们的策略马上就可以定义为

2.1.3　蒙特卡罗策略优化算法

通过蒙特卡罗方法来进行强化学习的具体步骤可以分为两步。首先我们根据一个初始的策略在环境中采样到轨迹，根据采样的轨迹来估计Q（s，a），这一步也被称为策略估计（Policy Evaluation）；在第二步中，我们根据估计到的Q值更新初始的策略，这一步也被称为策略提升（Policy Improvement）。具体的算法如Algorithm 1所示。

但是这里会有一个新的问题，在预测Q值的情况下，需要在状态s下以一定的策略遍历所有可能的动作a，以通过大量的数据求得Q（s，a）的估计值。但是对于一个确定性的策略来说，在状态s下执行动作a是固定的。因此，如果我们固定以某一个策略进行采样，很有可能得到一个有很大偏差的估计，无法采到大量的状态动作对。然而另一方面，纯用随机的方式采样，也存在效率低、和实际有偏差的问题。因此这里其实牵涉到强化学习一个很重要的问题：探索和利用。在后面的章节，我们也会不断讨论这个根本的问题。

Algorithm 1 蒙特卡罗策略优化算法

Require：

Init Q（s，a），Initπ（s），Init R（s，a）=［］

1：Repeat

2：从初始状态s0开始，以初始策略π来生成一个回合（episode）的轨迹

3：for回合里的每一个状态动作对（s，a）do

4：计算（s，a）的回报G

5：把G更新到对应的R（s，a）

6：使用R（s，a）更新Q值：Q（s，a）=avg（R（s，a））

7：end for

8：对于回合里的每个状态s，更新策略π（s）=argmax a Q（s，a）

2.1.4　探索和利用

使用蒙特卡罗方法能够估计值函数的前提条件是能够合理地访问每个可能的状态。因此，我们希望尽可能探索到所有可能的状态，从而估计一个比较准确的Q（s，a）。当状态空间比较小的时候，可以通过随机探索的方法来探索全部的状态空间。但是当状态空间比较大的时候，需要利用现有已经探索到的策略，以便高效访问那些Q值更高的状态动作对。因此要如何设计探索策略，才可以保证很好地访问到所有的状态呢？

一种最常用的方式叫做ϵ贪婪策略（ϵ-greedy algorithm）。这个算法来源于多臂老虎机（bandits）。其思路很简单，在每个状态下，以一定概率ϵ随机选择动作，而以1-ϵ的概率选择当前Q值最大的动作。这样，既兼顾了利用当前的策略，也有一定的概率探索新的更好的策略。在这之上也可以有很多变种，比如在迭代之初，可以用一个更大的ϵ，来增加探索的概率，而当后期已经获得了一些比较好的策略时，可以适当降低探索的概率。可以证明，这样的策略是保证收敛的。

ϵ贪婪的策略在ϵ的时候，还是对动作均匀采样的，但这样其实会有效率的问题。因为在某个状态下不同动作的Q值大小是不一致的，我们可以考虑更多的探索Q值更大的动作，这样可以更快收敛。一个比较好的策略是UCB（Upper Confidence Bound）：

这个式子和常见的UCB的公式稍有不同。其中N（s）是之前采样到状态s的次数，N（s，a）是在状态下选择动作a的次数，Q（s，a）是对应的估计的Q值，C是人工设置的权重参数。基于UCB的值，选择不同的动作：

可以看到，当某个动作的Q值比较大、以及该动作被采样的次数很小时，相应的UCB值都比较大，也即更可能被采样到。我们可以认为体现的是对现有策略的利用，代表的是对未知的探索，C是用来控制探索和利用的比重。

2.1.5　异策略蒙特卡罗方法

可以看到，在之前的ϵ贪婪的策略中，我们用来评估和行动的策略是同一个策略。如果进一步优化，可以把评估和行动的策略拆成两个不同的策略：评估某个状态-动作对的Q值是目标策略（target policy），用来执行动作的策略称为行为策略（behavior policy）。这里涉及强化学习中一个很重要的概念：同策略和异策略，有时也会被称为“在策略”和“离策略”。像ϵ贪婪策略这种评估和行为的策略是同样的策略，称为同策略；行为策略和目标策略是两个单独函数的策略，称为异策略。在同策略的情况下，如要保持探索性则必然会牺牲一定的最优选择机会。异策略下通常可以有更大的自由度，可以在目标策略中求解最优值，但同时也会更难收敛一些。在后面的章节中，同策略和异策略的比较还会在不同的算法中出现。

例如在蒙特卡罗方法中，如果使用两个策略函数：目标策略和行为策略，我们会通过行为策略来生成回合、局，然后基于这些回合、局，在目标策略上进行更新，这样行为策略通常是更偏向于探索的；而目标策略利用行为策略采样的回合、局的时候，可以更倾向于选择最优解，而不用考虑探索的问题。

在异策略上，我们需要用行为策略（πb）采样的回报的期望去估计目标策略（πt）的回报的期望，这就牵涉到用一个简单分布去估计服从另一个分布的随机变量的均值的问题，通常在统计上会用重要性采样（Importance Sampling）的方法来进行处理。同时，行为策略πb和目标策略之间也要满足条件：如果πt（a|s）＞0，则πb（a|s）＞0；或者换个说法，如果πb（a|s）=0，那么πt（a|s）=0。这样保证在πt和πb中，所有状态下的动作空间都是一致的。

具体来说，在离散的情况下，行为策略πb的回报的期望是E（R|πb）=ri×pi，而πt的回报的期望是E（R|πb）=ri×qi。其中pi表示策略πb获得回报ri的概率，qi表示策略πt获得回报ri的概率。如果用蒙特卡罗方法采样，可以通过计算采样N次得到回报的均值来估计回报的期望。

这里K i和M i分别代表两个策略采样得到回报ri的次数。当采样次数N足够大的时候，其实是可以得到K i=N×pi，M i=N×qi的，因此即使我们没有对策略πt进行采样，通过对πb进行采样，也可以得到

这个就称为普通重要性采样（Ordinary Importance Sampling）。但是在实际应用中，因为我们不可能做到无限次采样，因此有可能会碰到某一次采样的值特别大或者特别小，导致整个采样的方差特别大，最后算的均值和真实的期望不一致。这里最重要的原因是，我们对策略πb每次采样的回合、局都在策略πb中赋予了同样的权重，实际上在有限次采样的过程中，某个采样τi在πb中出现K i次，在策略πt中应该出现K i×次。因此通常我们会用这个估计的次数来替换N：

离线的蒙特卡罗方法也采用这种加权的重要性采样（Weighted Importance Sampling）的方法。具体说来，对于采样的一个回合、局：

这个序列在策略π下出现的概率是

对于第i回合τi，我们可以根据重要性采样得到行为策略πb的回报期望，来估计目标策略πt的比值（Importance Sam pling Ratio）：

如果单独考虑这个采样序列中的τi，令，假设每一步得到的奖励是G1，G2，···，GT-1，结合式（2.11），因为K i=1，可以变为

基于蒙特卡罗的马尔可夫性，我们可以把它改成增量的方式

其中CT=CT-1+WT是对应的采样序列τi在策略πt下出现次数的概率。这样我们就可以根据行为策略πb采样的数据来增量地更新目标策略πt了。在实践中，通常可以用一个较早的目标策略加上ϵ来作为一个行为策略进行采样。