潮科技行业入门指南 | 深度学习理论与实战：提高篇（17）—— 强化学习简介(三)

上一节遇到的一个问题就是 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。

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。因此 soft 的策略在状态 s 时对于所有的 Action 都有一定的概率去尝试，但是最终会有某个(些) Action 的概率会比较大从而形成比较固定的策略。为什么蒙特卡罗控制要求策略是 soft 而之前的动态规划不需要呢（还记得之前的策略提升都是用到固定的贪婪的策略吗）？

图：动态规划的 backup 图

图：蒙特卡罗方法的 backup 图

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

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!