环信出品《深度学习理论与实战：提高篇》：强化学习简介(22)

编者按：环信开源国内首本免费深度学习理论和实战专著《深度学习理论与实战：提高篇 》，内容涵盖听觉，视觉，语言和强化学习，七百多页详尽的理论和代码分析。本文节选自《深度学习理论与实战：提高篇 》一书，原文链接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问题的另外一种方法——蒙特卡罗方法。前面的动态规划方法，我们需要完全的环境动力学p(s′,r|s,a)$p(s^{\prime },r|s,a)$。而蒙特卡罗方法只需要经验(Experience)——通过与真实环境交互或者模拟得到的状态、行为和奖励的序列。如果从模拟学习，那么需要一个模型来建模环境，但是这个模型不需要完整的环境动力学，它只需要能采样即可。有的时候显示的定义一个概率分布是很困难的，但是从中获取样本却比较容易。

蒙特卡罗方法通过平均采样的回报(return)来解决强化学习问题。它要求任务是Episodic的，并且一个Episode进入终止状态后才能开始计算（后面介绍的Temporal Difference不需要任务是Episodic，即使Episodic的任务也不用等到一个Episode介绍才能计算）。

蒙特卡罗预测(Monte Carlo Prediction)

首先我们来使用蒙特卡罗方法解决预测问题——给定策略，计算状态价值函数的问题。回忆一下，状态的价值是从这个状态开始期望的回报——也就是期望的所有未来Reward的打折累加。因此很直观的想法就是从经验中估计——所有经过这个状态的回报的平均。我们的目标是估计vπ$v_{\pi }$，但是我们有的只是一些经验的Episode，这些Episode是采样策略π$\pi$得到的。也就是Episode S1,A1,R2,…,Sk∼π$S_1,A_1,R_2,\dots ,S_k\sim \pi$。而t时刻状态是s的回报是如下定义的：

Gt=Rt+γRt+1+...+γT−1RT$$G_t=R_t+\gamma R_{t+1}+...+{\gamma }^{T-1}{R}_T$$

而状态价值函数是采样策略π$\pi$时期望的回报：

vπ(s)=Eπ[Gt|St=s]$$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

蒙特卡罗方法的思想是使用(采样的)平均回报来估计期望回报，根据大数定律，如果采样的次数趋于无穷，那么估计是无偏的。

比如我们要估计vπ(s)$v_{\pi }(s)$，我们用很多Episodic的经验，这些经验是使用策略π$\pi$获得的。一个Episode里s的每次出现都叫做s的一次visit。当然在一个Episode里s可能多次出现，一种方法只考虑s的第一次visit，这就叫First-Visit蒙特卡罗方法；而另外一种就是每次visit都算，这就是Every-Visit蒙特卡罗方法。这两者的收敛在理论上有一些细微区别，我们这里不讨论，这里我们使用First-Visit蒙特卡罗方法。算法伪代码如下：

图：First-Visit蒙特卡罗方法伪代码

21 点游戏 (Blackjack)

在介绍蒙特卡罗预测的代码之前，我们来学习一下 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个状态。

为什么这个问题很难用动态规划来解决呢？因为动态规划需要知道p(s′,r|s,a)$p(s^{\prime },r|s,a)$，比如现在的牌是3+8+2，如果我们采取hit(要牌)，我们也许还能计算变成3+8+2+4的概率，但是reward是多少呢？此外如果我们stick，那么我们的状态会取决于庄家的行为并且最终进入终止状态，这个是很难计算的（因为我们不知道没有亮的牌是多少）。而使用蒙特卡罗方法就很简单，我们不需要知道这些概率，只需要根据某个策略来采取行为就可以了，而环境动力学我们只需要随机模拟就可以了。

蒙特卡罗预测代码示例

完整代码在这里。

Blackjack环境

首先我们来简单的阅读一些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 才停止，这显然很容易爆掉。所以这个策略基本就是输的。

图：10k 迭代没有 Ace

图：10k 迭代有 Ace

图：500k 迭代没有 Ace

图：500k 迭代有 Ace

前面介绍的是使用蒙特卡罗方法来求解一个策略的状态价值函数，而行为状态函数也是类似的算法，只不过采样后累加的 key 是 s-a 而不是 s 而已。这里就不赘述了。

蒙特卡罗控制

和之前的策略迭代类似，我们可以用蒙特卡罗预测替代基于动态规划的策略评估，然后不断提升策略。这里我们计算的是行为价值函数q(s,a)而不是状态v(s)。

π0→qπ0→π1→qπ1 →π2→...→π∗→q∗$${\pi }_0\to q_{{\pi }_0}\to {\pi }_1\to q_{{\pi }_1}\to {\pi }_2\to ...\to {\pi }_{\ast }\to q_{\ast }$$

这里使用的策略提升是贪婪的方法：

为什么这个方法可以提升策略呢？我们仍然可以使用前面的策略提升定理来证明：

上面的证明第一行到第二行的等号稍微有点绕，但并不复杂：argmaxaqπk(s,a)$arg\underset{a}{max}{q}_{{\pi }_k}(s,a)$是遍历所有的a，找到使得qπk(s,a)$q_{{\pi }_k}(s,a)$最大的那个a，假设是a∗$a_{\ast }$，那么qπk(s,a∗)$q_{{\pi }_k}(s,a_{\ast })$，自然就是使得maxaqπk(s,a)$\underset{a}{max}{q}_{{\pi }_k}(s,a)$。第二行到第三行的不等式很容易，最大的那个a对应的q自然比任何其它(πk(s)${\pi }_k(s)$)的q要大。

这个算法有两个假设：蒙特卡罗迭代的次数是无穷的（才能逼近真实的价值函数）；Exploring Start。前者我们可以忽略，因为迭代足够多次数一般就够了，而且我们之前也讨论过价值迭代，我们不需要精确的估计策略的价值就可以使用价值提升了。这里的关键问题是Exploring Start，初始状态S0$S_0$因为游戏是随机初始化的，因此所有可能的初始状态我们都可能遍历到，而且随着采样趋于无穷，每种可能初始状态的采样都是趋于无穷。与S0$S_0$对应的A0$A_0$可能有很多，但是有可能我们的策略会只选择其中一部分，那么有可能我们搜索的空间是不完整的。一种办法就是Exploring Start，就是强制随机的选择所有可能的(S0$S_0$和A(S0)$A(S_0)$)，但这样有问题——我们的策略探索过(S0,A0)$(S_0,A_0)$之后发现它不好，正常的话，它碰到S0$S_0$后就避免A0$A_0$了，但是我们强迫它随机(平均)的探索(S0,A0)$(S_0,A_0)$和(S0,A1)$(S_0,A_1)$，其实是浪费的。这个问题我们留到后面来解决，我们首先假设是Exploring Start的，看看蒙特卡罗预测的伪代码。

图：蒙特卡罗控制算法伪代码

通过上面的算法，我们就可以得到最优的策略如下图所示。

图：使用 Exploring Start 的蒙特卡罗控制求解结果

这里学到的策略大致是：如果有可用的 Ace，那么一直要牌直到 18 点，这显然是有道理的，因为我们知道庄家是要到 17 点为止。如果没有 Ace，如果庄家亮出来的牌很小，那么我们到 11 或者 12 点就停止要牌了。为什么这是最优的？作者也不清楚，知道的读者可以留言告诉我。

这一节我们不会实现 Exploring Start 的算法，原因前面我们讲过了，这个算法并不高效和通用，我们之后的内容会介绍没有 Explroing Start 的算法并用它们来解决 21 点游戏。

多臂老虎机和 UCB

上一节遇到的一个问题就是Exploring Start的问题，如果我们不“探索”所有可能的(S0,A0)$(S_0,A_0)$，那么就可能“错过”好的策略。但是如果不“利用”以往的知识而把过多的时间浪费在明显不好的状态也似乎不明智，这就需要权衡“探索”(Explore)和“利用”(Exploit)。我们下面通过一个多臂老虎机的例子来介绍一下探索和利用的矛盾。

这是很简单的一个问题，但在很多地方都有应用，比如互联网广告，游戏厅有一个K臂的老虎机，你可以选择其中的一个投币，每个手臂都是一个产生一个随机的奖励，它们的均值是固定的（也有Nonstationary的多臂老虎机，我这里只考虑Stationary的）。你有N次投币的机会，需要想办法获得最大的回报(reward)。

当然如果我们知道这个K个手臂的均值，那么我们每次都选择均值最大的那个投币，那么获得的期望回报应该是最大的。

可惜我们并不知道。那么我们可能上来每个都试一下，然后接下来一直选择最大的那个。不过这样可能也有问题，因为奖励是随机的，所以一次回报高不代表真实的均值回报高。当然你可以每个都试两次，估计一下奖励的均值。如果还不放心，你可以每个都试三次，或者更多。根据大数定律，试的次数越多，估计的就越准。最极端的一种做法就是每个手臂都投一样多的次数；另外一种极端就是碰运气，把所有的机会都放到一个手臂上。后一种如果运气好是最优的，但是很可能你抽到的是回报一般的甚至很差的手臂，期望的回报其实就是K个手臂的平均值。前一种呢？回报也是K个手臂的平均值！我们实际的做法可能是先每个手臂都试探几次，然后估计出比较好的手臂（甚至几个手臂），然后后面重点尝试这个(些)手臂，当然偶尔也要试试不那么好的手臂，太差的可能就不怎么去试了。但这个“度”怎么控制就是一个很复杂的问题了。这就是exploit-explore的困境(dilemma)。利用之前的经验，优先“好”的手臂，这就是exploit；尝试目前看不那么“好”的手臂，挖掘“潜力股”，这就是explore。

一种策略(Policy)的Regret(损失)为：

不要被数学公式吓到了，用自然语言描述就是：最理想的情况是n次都是均值最大的那个手臂(μ∗${\mu }^{\ast }$)，不过我们并不知道，μjE[Tj(n)]${\mu }_j\mathbb{E}[T_j(n)]$是这个策略下选择第j个手臂的期望。那么R就是期望的损失，如果我们的策略非常理想，这个策略只尝试最好的手臂，其它不试，那么R就是0。

但是这样的理想情况存在吗？很明显不太可能存在（存在的一种情况是k个手臂的均值一样）。那么我们的策略应该尽量减少这个损失。Lai and Robbins证明了这个损失的下界是logn，也就是说不存在更好的策略，它的损失比logn小（这类似于算法的大O表示法）。所以我们的目标是寻找一种算法，它的损失是logn的。UCB就是其中的一种算法：

每次决策之前，它都用上面的公式计算每个手臂的UCB值，然后选中最大的那个手臂。公式右边的第一项是exploit项，是第j个手臂的平均回报的估计。这个值越大我们就越有可能再次选中它。第二项是explore项，nj$n_j$是第j个手臂的尝试次数，nj$n_j$越小这个值就越大，也就是说尝试次数越少的我们就越应该多尝试。当nj=0$n_j=0$时，第二项为无穷大，所以这个算法会首先尝试完所有的手臂（explore），然后才会选择回报最大的那个(exploit)，试了之后这个手臂的平均值可能变化，而且nj$n_j$增加，explore值变小，接着可能还是试最大的那个，也可能是第二大的，这要看具体情况。

我们来分析一些极端的情况，一种情况是最好的（假设下标是k)比第二好的要好很多，那么第一项占主导，那么稳定了之后大部分尝试都是最好的这个，当然随着nk$n_k$的增加explore项在减少(其它手表不变)，所以偶尔也试试其它手臂，但其它手臂的回报很少，所以很快又会回到第k个手臂。但是不管怎么样，即使n趋于无穷大，偶尔也会尝试一下其它的手臂的。不过因为大部分时间都在第k个手臂上，所以这个策略还是可以的。

另一种极端就是k个手臂都差不多（比如都是一样的回报），那么exploit项大家都差不多，起决定作用的就是explore项，那么就是平均的尝试这些手臂，由于k各手臂回报差不多，所以这个策略也还不错。处于中间的情况就是有一些好的和一些差的，那么根据分析，大部分尝试都是在好的手臂上，偶尔也会试一试差的，所以策略的结果也不会太差。

当然这个只是简单的直觉的分析，事实上可以证明这个算法的regret是logn的，具体证明细节请参看论文Finite-time Analysis of the Multiarmed Bandit Problem。