编者按：本文节选自《深度学习理论与实战：提高篇 》一书，原文链接http://fancyerii.github.io/2019/03/14/dl-book/ 。作者李理，环信人工智能研发中心vp，有十多年自然语言处理和人工智能研发经验，主持研发过多款智能硬件的问答和对话系统，负责环信中文语义分析开放平台和环信智能机器人的设计与研发。
以下为正文。
本文介绍蒙特卡罗方法，详细介绍蒙特卡罗预测。接着会通过多臂老虎机和UCB来介绍探索-利用困境（exploration-exploitation dilemma），然后会介绍On-Policy和Off-Policy的蒙特卡罗预测，最后会简单的比较一下蒙特卡罗方法与动态规划的区别。每一个算法都会有相应的示例代码，通过一个简单的21点游戏来比较On-Policy和Off-Policy算法。
目录
蒙特卡罗预测 (Monte Carlo Prediction)
21 点游戏 (Blackjack)
蒙特卡罗预测代码示例
Blackjack 环境
蒙特卡罗预测代码
蒙特卡罗控制
多臂老虎机和 UCB
On-Policy 蒙特卡洛控制
On-Policy 蒙特卡罗控制代码示例
Off-Policy 蒙特卡罗预测
Off-Policy 蒙特卡罗控制
Off-Policy 蒙特卡罗控制代码示例
动态规划和蒙特卡罗方法的比较
接下来我们介绍解决 MDP 问题的另外一种方法——蒙特卡罗方法。前面的动态规划方法，我们需要完全的环境动力学 𝑝(𝑠′,𝑟|𝑠,𝑎) 。而蒙特卡罗方法只需要经验 (Experience)——通过与真实环境交互或者模拟得到的状态、行为和奖励的序列。如果从模拟学习，那么需要一个模型来建模环境，但是这个模型不需要完整的环境动力学，它只需要能采样即可。有的时候显示的定义一个概率分布是很困难的，但是从中获取样本却比较容易。
蒙特卡罗方法通过平均采样的回报(return)来解决强化学习问题。它要求任务是 Episodic 的，并且一个 Episode 进入终止状态后才能开始计算（后面介绍的 Temporal Difference 不需要任务是 Episodic，即使 Episodic 的任务也不用等到一个 Episode 介绍才能计算）。
首先我们来使用蒙特卡罗方法解决预测问题——给定策略，计算状态价值函数的问题。回忆一下，状态的价值是从这个状态开始期望的回报——也就是期望的所有未来 Reward 的打折累加。因此很直观的想法就是从经验中估计——所有经过这个状态的回报的平均。我们的目标是估计 𝑣𝜋 ，但是我们有的只是一些经验的 Episode，这些 Episode 是采样策略 𝜋 得到的。也就是Episode𝑆1,𝐴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点，就叫爆了(goes bust)，那么庄家获胜。如果没有爆就停止要牌，那就轮到庄家要牌，庄家如果爆了，那就玩家获胜，否则就比最终的大小来区分胜负或者平局。
读者可以在继续阅读之前上网“搜索21点在线”来试玩一下，这样对这个游戏更加熟悉。进入网站点击”Try it free”可以免费单人试玩，请不要赌博！！
从游戏的技巧来看（作者在学习强化学习之前也没玩过，所有总结的不一定正确），玩家需要根据庄家亮的牌以及自己牌的和来决定是否继续要牌。同样庄家可能需要根据自己的点数以及玩家的牌的张数以及玩家要牌的快慢表情等(如果是跟机器玩可能就无表情了？机器能像人那样使用表情骗人吗？——明明分不高故意装得很有信心，从而引导对手爆掉)来决定是否继续要牌。另外就是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 就要牌，否则就停止的策略，看看它在不同状态下的价值函数：
如果我们运行 jupyter notebook 的代码，可以得到下图的结果。可以看到经过 500k 次迭代后价值函数非常平滑，而10k次迭代还是不平滑的，也就是误差比较大。我们发现(验证)这个策略并不好：从图中可以看出，只有一上来我们 (agent) 的点数大于 20 点才会赢，事实上如果我们知道庄家的策略，我们一上来到了 18 点就可以停止要牌了，但是我们很激进的要超过 19 才停止，这显然很容易爆掉。所以这个策略基本就是输的。
前面介绍的是使用蒙特卡罗方法来求解一个策略的状态价值函数，而行为状态函数也是类似的算法，只不过采样后累加的 key 是 s-a 而不是 s 而已。这里就不赘述了。
和之前的策略迭代类似，我们可以用蒙特卡罗预测替代基于动态规划的策略评估，然后不断提升策略。这里我们计算的是行为价值函数q(s,a)而不是状态v(s)。
𝜋0→𝑞𝜋0→𝜋1→𝑞𝜋1→𝜋2→...→𝜋∗→𝑞∗
这里使用的策略提升是贪婪的方法：
为什么这个方法可以提升策略呢？我们仍然可以使用前面的策略提升定理来证明：
这个算法有两个假设：蒙特卡罗迭代的次数是无穷的（才能逼近真实的价值函数）；Exploring Start。前者我们可以忽略，因为迭代足够多次数一般就够了，而且我们之前也讨论过价值迭代，我们不需要精确的估计策略的价值就可以使用价值提升了。这里的关键问题是 Exploring Start，初始状态 𝑆0 因为游戏是随机初始化的，因此所有可能的初始状态我们都可能遍历到，而且随着采样趋于无穷，每种可能初始状态的采样都是趋于无穷。与 𝑆0 对应的 𝐴0 可能有很多，但是有可能我们的策略会只选择其中一部分，那么有可能我们搜索的空间是不完整的。一种办法就是Exploring Start，就是强制随机的选择所有可能的(𝑆0S 和𝐴(𝑆0) )，但这样有问题——我们的策略探索过 (𝑆0,𝐴0) 之后发现它不好，正常的话，它碰到𝑆0S0后就避免 𝐴0 了，但是我们强迫它随机(平均)的探索 (𝑆0,𝐴0) 和 (𝑆0,𝐴1) ，其实是浪费的。这个问题我们留到后面来解决，我们首先假设是 Exploring Start 的，看看蒙特卡罗预测的伪代码。
通过上面的算法，我们就可以得到最优的策略如下图所示。
这里学到的策略大致是：如果有可用的 Ace，那么一直要牌直到 18 点，这显然是有道理的，因为我们知道庄家是要到 17 点为止。如果没有 Ace，如果庄家亮出来的牌很小，那么我们到 11 或者 12 点就停止要牌了。为什么这是最优的？作者也不清楚，知道的读者可以留言告诉我。
这一节我们不会实现 Exploring Start 的算法，原因前面我们讲过了，这个算法并不高效和通用，我们之后的内容会介绍没有 Explroing Start 的算法并用它们来解决 21 点游戏。
上一节遇到的一个问题就是 Exploring Start 的问题，如果我们不“探索”所有可能的 (𝑆0,𝐴0) ，那么就可能“错过”好的策略。但是如果不“利用”以往的知识而把过多的时间浪费在明显不好的状态也似乎不明智，这就需要权衡“探索”(Explore)和“利用”(Exploit)。我们下面通过一个多臂老虎机的例子来介绍一下探索和利用的矛盾。
这是很简单的一个问题，但在很多地方都有应用，比如互联网广告，游戏厅有一个 K 臂的老虎机，你可以选择其中的一个投币，每个手臂都是一个产生一个随机的奖励，它们的均值是固定的（也有 Nonstationary 的多臂老虎机，我这里只考虑 Stationary 的）。你有 N 次投币的机会，需要想办法获得最大的回报 (reward)。
当然如果我们知道这个 K 个手臂的均值，那么我们每次都选择均值最大的那个投币，那么获得的期望回报应该是最大的。
可惜我们并不知道。那么我们可能上来每个都试一下，然后接下来一直选择最大的那个。不过这样可能也有问题，因为奖励是随机的，所以一次回报高不代表真实的均值回报高。当然你可以每个都试两次，估计一下奖励的均值。如果还不放心，你可以每个都试三次，或者更多。根据大数定律，试的次数越多，估计的就越准。最极端的一种做法就是每个手臂都投一样多的次数；另外一种极端就是碰运气，把所有的机会都放到一个手臂上。后一种如果运气好是最优的，但是很可能你抽到的是回报一般的甚至很差的手臂，期望的回报其实就是K个手臂的平均值。前一种呢？回报也是K个手臂的平均值！我们实际的做法可能是先每个手臂都试探几次，然后估计出比较好的手臂（甚至几个手臂），然后后面重点尝试这个(些)手臂，当然偶尔也要试试不那么好的手臂，太差的可能就不怎么去试了。但这个“度”怎么控制就是一个很复杂的问题了。这就是 exploit-explore 的困境 (dilemma)。利用之前的经验，优先“好”的手臂，这就是 exploit；尝试目前看不那么“好”的手臂，挖掘“潜力股”，这就是 explore。
一种策略 (Policy) 的 Regret (损失)为：
不要被数学公式吓到了，用自然语言描述就是：最理想的情况是 n 次都是均值最大的那个手臂 ( 𝜇∗ )，不过我们并不知道，𝜇𝑗𝔼[𝑇𝑗(𝑛)] 是这个策略下选择第 j 个手臂的期望。那么 R 就是期望的损失，如果我们的策略非常理想，这个策略只尝试最好的手臂，其它不试，那么 R 就是 0。
但是这样的理想情况存在吗？很明显不太可能存在（存在的一种情况是 k 个手臂的均值一样）。那么我们的策略应该尽量减少这个损失。Lai and Robbins 证明了这个损失的下界是 logn，也就是说不存在更好的策略，它的损失比 logn 小（这类似于算法的大 O 表示法）。所以我们的目标是寻找一种算法，它的损失是 logn 的。UCB 就是其中的一种算法：
每次决策之前，它都用上面的公式计算每个手臂的 UCB 值，然后选中最大的那个手臂。公式右边的第一项是 exploit 项，是第j个手臂的平均回报的估计。这个值越大我们就越有可能再次选中它。第二项是 explore 项，𝑛𝑗 是第 j 个手臂的尝试次数，𝑛𝑗 越小这个值就越大，也就是说尝试次数越少的我们就越应该多尝试。当 𝑛𝑗=0 时，第二项为无穷大，所以这个算法会首先尝试完所有的手臂（explore），然后才会选择回报最大的那个(exploit)，试了之后这个手臂的平均值可能变化，而且 𝑛𝑗 增加，explore 值变小，接着可能还是试最大的那个，也可能是第二大的，这要看具体情况。
我们来分析一些极端的情况，一种情况是最好的（假设下标是 k)比第二好的要好很多，那么第一项占主导，那么稳定了之后大部分尝试都是最好的这个，当然随着 𝑛𝑘 的增加 explore 项在减少(其它手表不变)，所以偶尔也试试其它手臂，但其它手臂的回报很少，所以很快又会回到第 k 个手臂。但是不管怎么样，即使 n 趋于无穷大，偶尔也会尝试一下其它的手臂的。不过因为大部分时间都在第 k 个手臂上，所以这个策略还是可以的。
另一种极端就是k个手臂都差不多（比如都是一样的回报），那么 exploit 项大家都差不多，起决定作用的就是 explore 项，那么就是平均的尝试这些手臂，由于 k 各手臂回报差不多，所以这个策略也还不错。处于中间的情况就是有一些好的和一些差的，那么根据分析，大部分尝试都是在好的手臂上，偶尔也会试一试差的，所以策略的结果也不会太差。
当然这个只是简单的直觉的分析，事实上可以证明这个算法的 regret 是 logn 的，具体证明细节请参看论文Finite-time Analysis of the Multiarmed Bandit Problem。
我们再回到前面蒙特卡洛控制的问题，需要 Exploring Start，有什么办法可以避免吗？从理论上讲，如果蒙特卡洛实验的次数趋于无穷，那么所有的 Action 我们也需要尝试无穷次才能保证无偏的估计。我们这里先介绍 On-Policy 的方法，它的基本思想和 UCB 类似，把大多数时间花在当前策略认为好的 Action 上，但是也要花一些时间探索所有其它的 Action。为什么叫 On-Policy 呢？这是和 Off-Policy 相对的，On-Policy 指的是生成 Episode 的策略和最后使用来决策的策略是同一个策略；而 Off-Policy 有两个策略：一个策略用于生成 Episode，而另一个策略是最终用了决策的策略。
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
代码在这里。首先我们定义函数 make_epsilon_greedy_policy，它的输入是一个 Q 函数和epsilon，输出一个实现 ε- 贪婪的策略的函数。
然后是实现ε-贪婪策略的蒙特卡罗控制函数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 就停止要牌，仍然有一定概率比我们大)。
前面的 ε- 贪婪策略可以解决 Exploring Start的问题，但是带来一个新的问题，它永远只能学到 ε-soft 的策略，用于决策的时候还去“探索”其实是不好的。本节我们介绍 Off-Policy 的蒙特卡罗预测，和前面的 On-Policy 策略相比，Off-Policy 有两个不同策略：目标策略 (target policy)和行为策略 (behavior policy)。目标策略就是我们解决问题需要学习的策略；而行为策略是用来生成 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 策略都使用重要性采样 (Importance Sampling) 方法，这是根据一个概率分布来估计另外一个不同的概率分布的常见方法。我们希望估计的是策略 𝜋 ，而实际采样用的是 b 生成的 Episode。因此我们在计算平均的回报时需要对它乘以一个采样重要性比例 (importance-sampling ratio) 来加权。通俗的解释就是：𝑏(𝑎|𝑠) 的概率是0.2，而𝜋(𝑎|𝑠)=0.4 ，那么我们需要乘以 2。给定初始状态 𝑆𝑡 和策略 𝜋 ，再给定任意状态-行为轨迹 (trajectory)，我们可以就是其条件概率——在给定策略下出现这个轨迹的概率。
虽然轨迹的概率是和 MDP 的转移概率 𝑝(𝑠′|𝑠,𝑎) 有关，但是两个策略的重要性比例是和它无关的，它只跟两个策略相关。
为了介绍后面的算法，我们先介绍一个数学记号，请读者在继续阅读之前熟悉这些记号。首先我们把很多的 Episode 使用统一的时刻来标志，也就是把所有的 Episode 顺序的串起来。比如有两个Episode，𝑒1 是 105 个时间单位，𝑒2 是 50 个。那么我们用 1 到 155 来标识这过两个Episode。𝑒2 的第一个时刻是 106，𝑒2 的最后一个时刻是 155。我们介绍一个记号 τ(s)，如果是 every-visit 的方法，它代表状态 s 在同样时间里的下标集合；如果是 first-visit 的方法，那么每个 Episode 只算第一次的出现。举例来说：比如两个 Episode 是 {𝑠1,𝑠1,𝑠2,𝑠3} 和{𝑠2,𝑠3,𝑠2,𝑠1} 。如果是 every-visit 的方法，则 𝜏(𝑠1)={1,2,8} ；如果是 first-visit 方法，则𝜏(𝑠1)={1,8} 。然后是记号T(t)，它表示 t 时刻之后的第一个结束时刻。对于上面的例子 T(2)=4, T(5)=8，表示第 2 个时刻之后的第一个结束时刻是 4，第 5 个时刻之后的第一个结束时刻是 8。其实就是这个时刻所在 Episode 的结束时刻。再就是记号 G(t)，它表示从 t 时刻到 T(t) 时刻的回报 (Return)，也就是 t 时刻的回报。因此记号 {𝐺(𝑡)}𝑡∈𝜏(𝑠) 表示所有这些 Episode 里状态 s 的回报的集合。{𝜌𝑡:𝑇(𝑡)−1}𝑡∈𝜏(𝑠) 表示与之对应的采样重要性比例。
为了估计 𝑣𝜋(𝑠) ，我们可以简单的用重要性比例加权平均回报：
这种平均方法加普通重要性采样 (ordinary importance sampling)，另外一种叫加权重要性采样 (weighted importance sampling):
普通重要性采样是无偏的估计，而加权重要性采样是有偏的估计；前者的方差很大，而后者较小。Off-Policy预测的伪代码如下：
图：Off-Policy蒙特卡罗预测
有了 Off-Policy 预测之后，我们很容易得到 Off-Policy 蒙特卡罗控制。伪代码如下：
注意这个代码和上面代码最后两行的差别。首先因为我们的策略 𝜋 是确定的策略，因此只有一个Action 的概率是 1，其余的是 0。因此如果状态是 𝑆𝑡 ，那么策略 𝜋 会选择 Q 最大的那个 a，也就是 𝑎𝑟𝑔max𝑎𝑄(𝑆𝑡,𝑎) ，如果 𝐴𝑡≠𝜋(𝑆𝑡) ，则说明 𝑝(𝐴𝑡|𝑆𝑡)=0 ，因此和上面算法的条件一样，可以退出 for 循环，否则就更新 W，如果执行到最后一行代码，说明 𝑝(𝐴𝑡|𝑆𝑡)=1 ，所以分子是 1。
完整代码在这里。
核心的函数是 mc_control_importance_sampling，代码和伪代码几乎一样，请读者参考伪代码阅读：
运行后我们把V(s)画出来，如下图所示。
我们可以看出结果和前面的 On-Policy 算法差不多，但是运算速度会快很多，读者可以自行比较一下。
是否有模型
动态规划需要模型 p(s’,r|s,a)；而蒙特卡罗方法不需要，它只需要能获得采样的 Episode 就行。因此动态规划也称为基于模型的 (model based) 方法；而蒙特卡罗方法被称为无模型的 (model free) 方法。基于模型的方法需要知道环境的动力系统，有些问题我们很容易知道环境动力系统，但是还有很多问题我们无法直接获得。如果我们还想使用动态规划，我们就必须用一个模型来建模环境，这本身就是一个很复杂的问题。比如前面我们的21点游戏，想完全建模其动力系统是很困难的。
bootstrapping
动态规划是有 bootstrapping 的，𝑣(𝑠) 和 𝑞(𝑠,𝑎) 都需要先有估计(初始值)，然后通过迭代的方法不断改进这个估计。
online/offline
蒙特卡罗方法是 offline 的，需要一个 Episode 结束之后才能计算回报。等介绍过 TD(λ) 之后，与 constant-α MC (一种后面我们会介绍的蒙特卡罗方法)等价的 TD(1) 可以实现 online 计算。这样如果不是 Episode 的任务（比如用于不结束状态的连续的任务），或者有些任务如果策略不对可能永远无法结束，比如后面我们会介绍的 Windy Gridworld。
注意动态规划并没有 online/offline 只说，因为它不是采样的方法。这是蒙特卡罗方法的一个缺点，后面的时间差分学习能解决这个问题。
full/sampling backup
如下图所示，动态规划会”遍历”所有的子树，而蒙特卡罗方法只采样一条路径。
图：蒙特卡罗算法只采样一条路径
图：动态规划会递归的遍历所有子树
本文经授权发布，不代表36氪立场。如若转载请联系原作者。
联系客服
