蒙特卡洛（MonteCarlo，MC）方法是第一个真正意义上用于估计价值函数和发现最优策略的学习方法。MC方法不需要掌握环境的动态信息，而是通过与环境交互获得经验进行学习。与动态规划（DP）相比，MC方法尽管也需要一个模型，但该模型只用于生成交互样本，而DP需要完整的转移概率分布。MC方法通过求样本均值去估计状态价值，每当完成一轮交互之后，就会根据交互经验更新状态价值函数和最优策略。总体而言，MC方法是逐轮更新的，而不是逐步更新（在线）。
蒙特卡洛方法通过采样和平均回报去估计动作-状态价值的方法，与第二章多臂bandits问题很相似，多臂bandits问题就是通过不断采样和平均去估计每个动作的期望奖励。但它们之间的本质不同在于，多臂bandits问题是静态的，但MC方法处理的问题可以是动态的。
1.MC预测（policyevaluation）
假设现在要估计给定策略下的状态价值\(v_\pi(s)\)。最直观的方法就是，根据交互经验，对每个遇到的状态\(s\)求回报，并将其所有的回报样本求期望\(E[G|S_o=s]\)。随着观测数据的不断增加，状态\(s\)的回报期望就越接近于真实值。这里需要注意的是，在每一轮交互中，状态\(s\)出现的次数可能会存在多次，如果只计算第一次出现的状态\(s\)的回报，那么这种方法称为首次访问蒙特卡洛方法（first-visitMCmethod，FVMC）；反之，如果对每一次出现的状态\(s\)都计算其回报，那么这类方法称为每次访问蒙特卡洛方法（every-visitMCmethod，EVMC）。两种方式的MC方法都会收敛到真实值。FVMC方法被研究的更早，且更为简单。下图给出了FVMC算法的伪代码。
从FVMC算法的伪代码中可以看出，该方法每轮是独立采样获得的回报\(G\)，因此\(G\)是满足独立同分布的，其分布等同于\(v_\pi(s)\)。但是，方差却不能保证是有界的，原因在于累计奖励\(\sum_tR_t\)并不能保证是有界的，且方差通常较大。这样估计得到的状态价值是无偏的。
同时也可以看出，MC方法所估计的每一个状态价值都是独立的，它不基于其他状态价值的估计。即MC方法的重要特征就是不需要自举（bootstrap）。FVMC方法另一个优势在于，它可以对某一个特定的状态估计其状态价值，即从特定状态出发直至终结。
2.MC对状态-动作价值的估计
由于模型的动态信息是未知，通过估计状态价值函数无法得到最优策略，原因在于无法像动态规划那样，从当前状态出发尝试每一个动作，从而挑选出可以转移到最佳下一状态的动作。因此，模型未知时，估计状态-动作价值函数更为合理。
唯一复杂的是，许多状态-动作对可能永远不会被访问到。例如\(\pi\)是一个确定性策略，则在策略\(\pi\)下每个状态\(s\)只能观察到一个可选动作的回报。这是一个严重的问题，因为学习状态-动作价值的目的是帮助在每个状态的可用动作中选择最佳动作。因此，这是一个持续探索的问题（maintainingexploration），需要探索所有可能的状态-动作价值。其中一个方法就是选定起始状态-动作对采用遍历所有的状态-动作对或者所有的状态-动作对都有概率被选中，这种方法称为起始性探索（exploringstarts）。
起始性探索的假设有时是有用的，但一般来说并不可靠，尤其是需要直接与实际环境互动进行学习。另一个最常见的替代方法是采用随机性策略，使得每一个状态的所有可选动作都有可能被选中。
3.MC控制
现在考虑如何用蒙特卡洛估计方法来进行控制，即近似最优策略。总体思路就是之前提到的GPI，广义策略迭代。
首先，考虑经典策略迭代的蒙特卡洛版本。在这种方法中，需要交替执行策略评估和策略改进的步骤，从任意初始策略\(\pi_0\)开始，最后收敛到最优策略和最优状态-动作价值函数：
在第\(k\)轮交互后，估计得到最优状态-动作价值函数\(q_{\pi_k}(s,a)\)，利用贪婪的方式来更新当前策略可得
\(\pi_{k+1}\)之所以优于\(\pi_k\)，正是基于策略改进理论，即
该理论保证了最优策略与最优价值函数的收敛。从而说明蒙特卡罗方法可以用于在没有获得环境动态信息的情况下，只通过每轮交互的采样找到最优策略。但是，在实际过程中，先进行策略评估得到近似的\(q_\pi\)需要进行大量的采样（多轮交互），再进行策略改进，如此循环往复其收敛速度太慢。其改进方式类似于价值迭代，每完成一轮交互，就更新策略评估，同时进行策略改进，而不用等到策略评估收敛后才改进策略。下图给出了MCES算法的伪代码。
MCES算法需要随机起始点，要求所有的状态-动作对都有可能被选中。这个条件比较苛刻，许多场景都不适用。MCES算法采用的是确定性策略，但由于起始点\((S_0,A_0)\)是随机的，从而保证了持续探索性，即一个状态的所有可选动作都有可能被探索到。最后，MCES算法是逐轮更新的，直至收敛，符合广义策略迭代的理论。
4.随机策略的MC控制
为了避免起始性探索的假设，现在引入两个新的概念：在线策略方法与离线策略方法（on-policy，off-policy）。在线策略方法是指用于交互的策略（用于评估或改进），同时也是用于控制的策略。而离线策略方法中交互策略用于生成样本数据，而训练得到的目标策略用于控制。蒙特卡洛ES方法是一个在线策略方法的例子。
在线控制方法其策略往往是软性的（soft），即随机策略\(\pi(a|s)>0\)对于所有的\(s\in\mathcal{S}\)和\(a\in\mathcal{A}(s)\)，随着交互轮数的增加逐渐向确定性策略靠拢。例如，\(\epsilon\)-greedy方法是在线策略方法中经常采用的动作选择策略。其对于任意非贪婪动作的选择概率为\(\frac{\epsilon}{|\mathcal{A}(s)|}\)，而对于贪婪动作的选择概率为\(1-\epsilon+\frac{\epsilon}{|\mathcal{A}(s)|}\)。基于第一次访问的在线策略MC算法不再要求随机初始点，因为它引入了软性策略已经具备了持续探索性。其算法的伪代码如下。
根据策略改进理论，\(\epsilon\)-greedy策略同样可以逐渐逼近最优策略。其证明如下。
利用状态价值函数的最优解的唯一性，可得\(\epsilon\)-greedy策略最终会收敛到最优解。
5.通过重要性采样（importancesampling）的离线策略预测
所有的策略学习方法都面临一个困境，如何从次优的交互过程中学习到最优策略。在线学习方法采用随机策略，使其逐渐逼近最优策略。离线学习方法则更为直接，定义两个策略，一个用于学习最优策略，称为目标策略（targetpolicy），即确定性策略；另一个用于探索环境生成经验样本，是随机性策略，称为交互策略（behaviourpolicy）。离线学习方法通常有更大的方差和更慢的收敛速度，但是另一方面，它更加强大更加通用。当目标策略和交互策略保持一致，那么离线学习方法等同于在线学习方法。
离线学习方法中的预测问题，相当于根据交互策略\(b\)去估计目标策略\(\pi\)中的价值函数\(v_\pi\)或\(q_\pi\)，其中\(b\neq\pi\)。这里有一个前置条件\(\pi(a|s)>0\)当且仅当\(b(a|s)>0\)，即交互策略要覆盖目标策略的动作-状态空间。几乎所有的离线学习方法使用了重要性采样技术，即根据一种分布下的采样数据估计另一种分布下的期望。给定初始状态与动作，根据随机性策略生成一段交互轨迹\(\{S_t,A_t,S_{t+1},A_{t+1},\ldots,S_T\}\)，可得这段轨迹的概率为
定义目标策略与交互策略下轨迹的相对概率为重要性采样系数，即
可以看出重要性采样系数与状态转移概率无关，仅与动作选择概率有关。简单分析一下\(\rho_{t:T-1}\)的值，当\(\pi\)为确定性策略时，\(\pi(a|s)=1\)，而\(0 我们希望估计目标策略\(\pi\)下的期望回报值，但真实交互采用的是交互策略\(b\)，计算得到回报\(G_t\)，得到的期望为\(E[G_t|S_t=s]=v_b(s)\)。这就是重要性抽样的作用所在。一条轨迹对应一个回报\(G_t\)和其对应概率\(P\{\cdots\}\)，由此可得目标策略的回报\(\rho_{t:T-1}G_t\)，从而得到策略\(\pi\)的回报期望值： 式（5.1）本质就是取所有采集得到的策略目标回报样本求均值。另一个改进方法是加权重要性采样（weightedimportancesampling）： 对于首次访问方法，一般重要性采样方法是无偏的，但是加权采样方法是有偏的，例如仅一次采样，通过加权采样方法得到的期望为\(G_t\)，显然不正确。但在实际应用中，加权采样方法通常有更小的方差，实际效果更好，原因在于 加权后的\(W_iG_{t_i}\)具有更小的方差。当\(\rho_{t:T(t)-1}\)越大，则意味着交互策略产生与目标策略一致的交互轨迹的概率越小，在实际采样过程中，\(\rho_{t:T(t)-1}\)大部分情况下都为0。 最后，对于每次访问方法，两种采样都是有偏的。 6.递增法（incrementalimplementation） 这里主要考虑加权采样方法的递推实现。考虑针对状态\(s\)采样已得到一系列的回报值\(G_1,G_2,\ldots,G_n\)及其对应的权重\(W_i=\rho_{t_i:T(t_i)-1}\)，则得到状态价值估计： 下一次采样，状态价值估计更新为 其中，\(C_{n+1}=C_n+W_{n+1},\C_0=0\)。下面给出离线学习的蒙特卡洛预测方法的伪代码，如下图所示。 书上提供的伪代码是基于每次访问的离线策略算法。伪代码中用了一些技巧，针对一条轨迹从后向前逐个更新状态-动作价值，即使一个状态-动作对出现多次，最终会被首次访问的状态-动作价值所替代，而重要采样率\(W\)也采用累乘的方式进行更新，效率更高。同时，需要注意策略\(\pi\)是确定性策略，所以\(\pi(A_t|S_t)=1\)。当交互策略采用的动作不是确定性策略所采用的动作时，\(W=0\)。 值得注意的是，利用交互策略去估计目标策略下的状态-动作价值，当目标策略的动作轨迹在交互策略中出现的概率越小，那么当采样得到该条轨迹的回报时，就应该更加重视，从而衡量目标策略下的状态-动作价值。也只有当交互策略的动作与目标策略的动作一致时，重要性采样的回报才有可能不是0。 7.离线学习方法的MC控制 离线学习的MC控制算法的核心思想仍然是广义策略迭代，在更新状态-动作价值函数的同时进行策略改进，直至得到最优策略。下图给出离线学习的MC控制算法的伪代码。 通过伪代码可以看出，只要发生策略改进则重新进行采样。其原因在于，目标策略采用的是确定性策略，当交互策略采用的动作\(a\)与目标策略的动作不同时，则\(\pi(a|s)=0\)，导致重要性采样系数为零，就没必要再进行本轮游戏的循环了。当动作空间较大时，该算法的学习速率会比较慢。而解决这一问题的有效方法是采用差分学习，这不是本章所要表达的重点。 8.小结 这一章主要描述了蒙特卡洛方法，它实际上是一种基于逐轮更新的交互学习的方法。相比于动态规划方法，蒙特卡洛方法有四点优势。第一，蒙特卡洛方法不需要知道环境的动态信息，只需要在和环境的交互中学习最优策略。第二，蒙特卡洛方法可以利用采样模型进行学习，对于复杂环境，即使知道其动态信息也很难实现，而获得模拟样本却相对比较容易。第三，蒙特卡洛方法可以只估计状态空间中感兴趣的部分，而不用精确估计所有状态集。第四，蒙特卡洛方法不会受限于马尔可夫性质，因为它并不采用自举的方式，状态价值的估计值是独立同分布的。 蒙特卡洛方法需要注意的一点就是保持充分的探索。由此产生两种方式，一种是在线学习方式，一种是离线学习方式。在线学习方式采用随机策略，随着采样数据的不断增加，使得随机策略不断逼近最优策略。离线学习方法定义两种策略，一种是目标策略用于近似最优策略，一种是交互策略用于产生样本，但从交互策略中估计目标策略下的状态价值需要引入重要性采样技术。 9.例子 21点游戏：21点纸牌游戏的目的是获得其数值之和尽可能大但不超过21的纸牌。所有的花牌（J,Q,K）都计为10，一张王牌（A）可以计为1或11。考虑每个玩家与庄家独立竞争的版本。游戏开始时发两张牌给庄家和玩家。庄家的一张牌面朝上，另一张牌则面朝下。如果玩家立即有21点（一张王牌和一张花牌），这被称为黑杰克，，那么他就赢了，除非庄家也有黑杰克，则比赛是平局。如果玩家没有21点，那么他可以继续要牌，直到他停牌（卡住）或超过21点（爆掉）。如果玩家爆掉就输了；如果玩家没爆掉且停牌，那么就轮到庄家。庄家只能按照固定策略要牌或者停牌：庄家点数必须在17或以上的总和，否则必须要牌。如果庄家爆掉，则玩家获胜；否则，比较谁的最终总和接近21，则谁获胜。 21点游戏可以看作是一个回合制的有限马尔科夫动态过程。在这个游戏过程中，过程奖励\(R\)设置为0，只在游戏结果中给予奖励，如果玩家赢了则奖励为\(+1\)，如果输了则奖励为\(-1\)，平局奖励为\(0\)。玩家的动作就两个，要牌或停牌。游戏状态取决于玩家和庄家的牌面。在仿真过程中，假设牌是可重复抽取的，这样记录牌抽取的过程就没有必要了。当卡牌A被记为11点且没有爆掉，则认为是卡牌A有用，反之则没用。 仿真1 首先考虑蒙特卡洛预测问题。玩家的策略采用当玩家手中点数为20或者21时才停牌，否则将一直要牌。MC预测问题就是衡量固定策略下的状态价值函数。 在程序实现过程中，需要注意几点。当玩家的点数小于12时，任何策略都会选择要牌，因此这些状态价值不值去探索。由于卡牌A的作用会随着要牌的情况而发生改变，可以统计有效卡牌A的数量，当点数大于21且有效卡牌A数量不为0时，总点数-10并卡牌A数量-1。具体代码参照随书代码blackjack.py。蒙特卡洛预测结果如下图所示。 仿真结果与我们的认知相符，蒙特卡洛方法是采用逐轮采样的，卡牌A发挥作用比不发挥作用的情况要少，所以当游戏局数较少时，采集的样本也较少，估计的效果就比较差（比较左侧两图）。当游戏局数足够多之后，状态价值函数的估计就逼近真实值了。 仿真2 下面考虑随机起始点的蒙特卡洛算法（MCES算法）学习21点游戏的最优策略。在程序实现过程中，需要注意MCES算法采用的是首次访问的统计方式。由于游戏过程的奖励为0且假设\(\gamma=1\)，这里在计算每个状态-动作价值的方法中可以采用取巧的方式，从每轮轨迹的初始状态向后计算即可，因为\(G_{t-1}=\gamma\cdotG_t+r_t=r_T\)。当遇到已经出现过的状态-动作对，则跳过。本次仿真总共进行了一百万局，MCES算法的仿真结果如下。 仿真结果也符合我们的认知，当卡牌A发挥作用时，状态价值整体比没有发挥作用时较好。 仿真3 最后考虑蒙特卡洛重要性采样的离线策略预测方法。针对初始状态：卡牌A发挥作用，玩家初始点数为13，庄家显示的牌的点数为2，利用随机策略去估计确定策略（玩家的策略采用当玩家手中点数为20或者21时才停牌，否则将一直要牌。）下的状态价值。仿真过程中分别采用一般重要性采样方法和加权重要性采样方法。仿真结果如下。