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

编者按：环信开源国内首本免费深度学习理论和实战专著《深度学习理论与实战：提高篇 》，内容涵盖听觉，视觉，语言和强化学习，七百多页详尽的理论和代码分析。本文节选自《深度学习理论与实战：提高篇 》一书，原文链接http://fancyerii.github.io/2019/03/14/dl-book/ 。作者李理，环信人工智能研发中心vp，有十多年自然语言处理和人工智能研发经验，主持研发过多款智能硬件的问答和对话系统，负责环信中文语义分析开放平台和环信智能机器人的设计与研发。

On-Policy蒙特卡洛控制

我们再回到前面蒙特卡洛控制的问题，需要 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$\mathrm{\forall }s\in \mathcal{S},a\in \mathcal{A}(s),\pi (a|s)>0$。因此soft的策略在状态s时对于所有的Action都有一定的概率去尝试，但是最终会有某个(些)Action的概率会比较大从而形成比较固定的策略。为什么蒙特卡罗控制要求策略是soft而之前的动态规划不需要呢（还记得之前的策略提升都是用到固定的贪婪的策略吗）？

图：动态规划的 backup 图

图：蒙特卡罗方法的 backup 图

我们看一下这两种方法的 backup 图，从图中我们可以看出，在动态规划的时候，我们是“遍历”一个状态所有 Action，以及 Action 的所有新状态。通过这种类似广度优先的方式递归的方式，我们遍历了所有空间。而蒙特卡罗方法我们是通过采样的方法一次访问一条“路径”，如果策略是固定的，那么我们每次都是访问相同的路径。

这一节我们会介绍ε-贪婪算法，它在大部分情况下(1-ε的概率)会使用贪婪的策略选择a使得q(s,a)最大，但是也会有ε的概率随机的选择策略。因此对于“最优”行为的概率是1-ε+ε/|A|（因为随机也可能随机到最优的行为），而其它行为的概率是ε/|A|。算法的伪代码如下：

图：On-Policy蒙特卡洛控制算法

假设策略π$\pi$是一个ε-soft的策略，它的行为价值函数是qπ(s,a)$q_{\pi }(s,a)$，而π′${\pi }^{\prime }$是对qπ$q_{\pi }$进行ε-贪婪之后得到的新策略（当然它也是一个ε-soft的策略），那么这个新策略π′${\pi }^{\prime }$相对于π$\pi$是有提升的（新的策略比老的好）。下面我们来证明一下， ∀s∈S$\mathrm{\forall }s\in \mathcal{S}$，我们有：

这个证明难点是第二行到第三行的不等式，它利用了这样一个结论：n个数的“线性组合”小于等于最大的那个数。所谓的线性组合就是n个数分别乘以n个系数在加起来，这n个系数是大于等于0小于等于1并且和为1的。我们以两个数为例，假设x1≤x2$x_1\le x_2$：

同样三个数的情况可以用类似的方法证明。我们再回过头来看上面的不等式，假设状态s下有n种行为，那么第三行就是n个数(aπ(s,a)$a_{\pi }(s,a)$)的线性组合，因为这n个数的系数都是大于0小于1的，而且其和是1：

我们在蒙特卡罗方法（包括后面的TD）使用的不是状态价值函数V(s)而是行为价值函数Q(s,a)，为什么呢？我们首先回顾一下GPI，参考下图。假设使用V(s)，我们首先有个初始的策略π$\pi$，我们用蒙特卡罗预测来估计vπ(s)$v_{\pi }(s)$，然后我们使用ε-贪婪获得一个更好的策略，然后再估计这个新的策略的价值函数，不断的迭代。这里我们需要根据V(s)来计算这个ε-贪婪的策略如下：

如下图所示，蒙特卡罗控制是这样优化的，注意和动态规划不同，蒙特卡罗控制一上来 是有Q，然后做ε-贪婪的提升，然后计算新的Q，不过因为蒙特卡罗是采样的近似，所以图中的蒙特卡罗的预测不是精确的预测Qπ(s,a)$Q_{\pi }(s,a)$，而是它的近似，所以图中的线没有接近上端。

图：蒙特卡罗控制的 GPI

On-Policy 蒙特卡罗控制代码示例

代码在这里。首先我们定义函数make_epsilon_greedy_policy，它的输入是一个Q函数和epsilon，输出一个实现ε-贪婪的策略的函数。

然后是实现ε-贪婪策略的蒙特卡罗控制函数mc_control_epsilon_greedy：

注意和伪代码比，我们没有“显式”定义新策略π′${\pi }^{\prime }$，而是把当前策略定义为Q(s,a)的一个函数policy = make_epsilon_greedy_policy(Q, epsilon, env.action_space.n)，因此Q(s,a)发生变化时，对于的函数就会发生变化。

运行后我们把V(s)画出来，如下图所示。

图：无Ace时最佳值函数

图：有Ace时最佳值函数

我们可以看出，如果一上来手上的牌就大于 18，我们最优的胜率是大于 0 的(当然也会可能输，因为庄家大于 17 就停止要牌，仍然有一定概率比我们大)。

Off-Policy蒙特卡罗预测

前面的ε-贪婪策略可以解决Exploring Start的问题，但是带来一个新的问题，它永远只能学到ε-soft的策略，用于决策的时候还去“探索”其实是不好的。本节我们介绍Off-Policy的蒙特卡罗预测，和前面的On-Policy策略相比，Off-Policy有两个不同策略：目标策略(target policy)和行为策略(behavior policy)。目标策略就是我们解决问题需要学习的策略；而行为策略是用来生成Episode的策略。如果目标策略和行为策略相同，那就是On-Policy策略了。

本节我们解决预测问题，假设目标策略和行为策略都已知的情况下计算其价值函数。假设目标策略是π$\pi$，而行为策略是b，我们的目的是根据b生成的Episode采样来计算vπ(s)或qπ(s,a)$v_{\pi }(s)或q_{\pi }(s,a)$。为了通过b生成的Episode能够用来估计π$\pi$，我们要求如果π(a|s)>0$\pi (a|s)>0$则b(s|a)>0$b(s|a)>0$，这叫做b是π$\pi$的coverage。为什么要有coverage的要求？因为如果我们要估计的策略π(a|s)>0$\pi (a|s)>0$，而b(a|s)=0$b(a|s)=0$，那么就不可能有Episode会在状态s是采取行为a，那么就无法估计π(a|s)$\pi (a|s)$了。

coverage的另外一种说法就是：如果b(a|s)=0$b(a|s)=0$那么一定有π(a|s)=0$\pi (a|s)=0$。因此策略b一定是随机的策略，为什么？因为b如果是确定的策略，对于任何状态si$s_i$，只有一个aj$a_j$使得b(aj|si)=1$b(a_j|s_i)=1$，其余的都是0。因为b是π$\pi$的coverage，所以除了j，其余所有的π(ak|si)=0$\pi (a_k|s_i)=0$，因此只有π(aj|si)>0$\pi (a_j|s_i)>0$，因此它必须是π(aj|si)=1$\pi (a_j|s_i)=1$，这样π$\pi$和b就是相同的策略，这显然不是Off-Policy策略。

因此在Off-Policy控制里，行为策略通常是随机的，它会“探索”，而目标策略通常是固定的贪心的策略，它更多的是“利用”。几乎所有的Off-Policy策略都使用重要性采样(Importance Sampling)方法，这是根据一个概率分布来估计另外一个不同的概率分布的常见方法。我们希望估计的是策略π$\pi$，而实际采样用的是b生成的Episode。因此我们在计算平均的回报时需要对它乘以一个采样重要性比例(importance-sampling ratio)来加权。通俗的解释就是：b(a|s)$b(a|s)$的概率是0.2，而π(a|s)=0.4$\pi (a|s)=0.4$，那么我们需要乘以2。给定初始状态St$S_t$和策略π$\pi$，再给定任意状态-行为轨迹(trajectory)，我们可以就是其条件概率——在给定策略下出现这个轨迹的概率。

虽然轨迹的概率是和MDP的转移概率p(s′|s,a)$p(s^{\prime }|s,a)$有关，但是两个策略的重要性比例是和它无关的，它只跟两个策略相关。

为了介绍后面的算法，我们先介绍一个数学记号，请读者在继续阅读之前熟悉这些记号。首先我们把很多的Episode使用统一的时刻来标志，也就是把所有的Episode顺序的串起来。比如有两个Episode，e1$e_1$是105个时间单位，e2$e_2$是50个。那么我们用1到155来标识这过两个Episode。e2$e_2$的第一个时刻是106，e2$e_2$的最后一个时刻是155。我们介绍一个记号τ(s)$\tau (s)$，如果是every-visit的方法，它代表状态s在同样时间里的下标集合；如果是first-visit的方法，那么每个Episode只算第一次的出现。举例来说：比如两个Episode是{s1,s1,s2,s3}$\{s_1,s_1,s_2,s_3\}$和{s2,s3,s2,s1}$\{s_2,s_3,s_2,s_1\}$。如果是every-visit的方法，则τ(s1)={1,2,8}$\tau (s_1)=\{1,2,8\}$；如果是first-visit方法，则τ(s1)={1,8}$\tau (s_1)=\{1,8\}$。然后是记号T(t)，它表示t时刻之后的第一个结束时刻。对于上面的例子T(2)=4,T(5)=8，表示第2个时刻之后的第一个结束时刻是4，第5个时刻之后的第一个结束时刻是8。其实就是这个时刻所在Episode的结束时刻。再就是记号G(t)，它表示从t时刻到T(t)时刻的回报(Return)，也就是t时刻的回报。因此记号{G(t)}t∈τ(s)$\{G(t){\}}_{t\in \tau (s)}$表示所有这些Episode里状态s的回报的集合。{ρt:T(t)−1}t∈τ(s)$\{{\rho }_{t:T(t)-1}{\}}_{t\in \tau (s)}$表示与之对应的采样重要性比例。

为了估计vπ(s)$v_{\pi }(s)$，我们可以简单的用重要性比例加权平均回报：

这种平均方法加普通重要性采样 (ordinary importance sampling)，另外一种叫加权重要性采样 (weighted importance sampling):

普通重要性采样是无偏的估计，而加权重要性采样是有偏的估计；前者的方差很大，而后者较小。Off-Policy预测的伪代码如下：

图：Off-Policy蒙特卡罗预测

Off-Policy 蒙特卡罗控制

有了 Off-Policy 预测之后，我们很容易得到 Off-Policy 蒙特卡罗控制。伪代码如下：

图：Off-Policy 蒙特卡罗控制

注意这个代码和上面代码最后两行的差别。首先因为我们的策略π$\pi$是确定的策略，因此只有一个Action的概率是1，其余的是0。因此如果状态是St$S_t$，那么策略π$\pi$会选择Q最大的那个a，也就是argmaxaQ(St,a)$arg\underset{a}{max}Q(S_t,a)$，如果At≠π(St)$A_t\ne \pi (S_t)$，则说明p(At|St)=0$p(A_t|S_t)=0$，因此和上面算法的条件一样，可以退出for循环，否则就更新W，如果执行到最后一行代码，说明p(At|St)=1$p(A_t|S_t)=1$，所以分子是1。

Off-Policy蒙特卡罗控制代码示例

完整代码在这里。

核心的函数是 mc_control_importance_sampling，代码和伪代码几乎一样，请读者参考伪代码阅读：

运行后我们把V(s)画出来，如下图所示。

图：Off-Policy算法无Ace时最佳值函数

图：Off-Policy算法有Ace时最佳值函数

我们可以看出结果和前面的 On-Policy 算法差不多，但是运算速度会快很多，读者可以自行比较一下。

动态规划和蒙特卡罗方法的比较

• 是否有模型

动态规划需要模型p(s’,r|s,a)；而蒙特卡罗方法不需要，它只需要能获得采样的Episode就行。因此动态规划也称为基于模型的(model based)方法；而蒙特卡罗方法被称为无模型的(model free)方法。基于模型的方法需要知道环境的动力系统，有些问题我们很容易知道环境动力系统，但是还有很多问题我们无法直接获得。如果我们还想使用动态规划，我们就必须用一个模型来建模环境，这本身就是一个很复杂的问题。比如前面我们的21点游戏，想完全建模其动力系统是很困难的。

• bootstrapping

动态规划是有bootstrapping的，v(s)$v(s)$和q(s,a)$q(s,a)$都需要先有估计(初始值)，然后通过迭代的方法不断改进这个估计。

• online/offline

蒙特卡罗方法是offline的，需要一个Episode结束之后才能计算回报。等介绍过TD(λ)之后，与constant-α MC(一种后面我们会介绍的蒙特卡罗方法)等价的TD(1)可以实现online计算。这样如果不是Episode的任务（比如用于不结束状态的连续的任务），或者有些任务如果策略不对可能永远无法结束，比如后面我们会介绍的Windy Gridworld。

注意动态规划并没有online/offline只说，因为它不是采样的方法。这是蒙特卡罗方法的一个缺点，后面的时间差分学习能解决这个问题。

• full/sampling backup

如下图所示，动态规划会”遍历”所有的子树，而蒙特卡罗方法只采样一条路径。

图：蒙特卡罗算法只采样一条路径

图：动态规划会递归的遍历所有子树