强化学习 · Bandit（四）高级探索

大家好，欢迎来到强化学习算法的第四讲《高级探索》。 

上一讲中，我们解决了非静态问题，教大家如何处理价值分布随着时间变化而变化的多臂老虎机。 今天，我们将延续皇家赌场的主题，讨论一些比 ε贪心算法（ε-Greedy）更复杂、更高效的探索策略。

不方便看视频的朋友们，请下拉阅读图文。

---

在强化学习算法第二期《Bandit：探索与开拓》中，我们指出了Exploration (探索) 和Exploitation (开拓)的辩证统一：两者缺一不可，但因计算和时间资源有限而不得不作出取舍。

在第二讲里，我们只提及了一种探索方法，即非常简单的 ε贪心算法（ε-Greedy）：

以 ε 的概率，完全随机地选择action。 ε 一般是比较小的数，比如5%。

以1 - ε 的概率（剩下的大部分情况） 选择目前拥有最高价值估计的老虎机。

虽然ε贪心算法思路极其简单，但却异常地难以超越。这方面出现过很多论文和研究项目，但很少有在大部分情况下都优于ε-Greedy的算法。在此，为大家介绍两个针对多臂老虎机问题的高级探索策略。

1

第一种算法是Optimistic Exploration（乐观探索法），也叫Optimistic Initial Value（乐观初始值）。

回到我们熟悉的皇家赌场💰设置。假设一开始时，你刻意地高估↑每个老虎机的价值。那么，直到它们让你“失望”之前，你都在探索新的老虎机。此法可类比为“人之初，性本善” —— 直到足够证据显示这人是恶人为止。

我们用具体数字来举例。假设你面前有三台老虎机（即三个action），且已知每台老虎机奖励你的金币数目最少是1枚，最多是3枚。

我们之前的做法是把每台老虎机的初始价值估计设为0。现在你故意把每台的初始价值估计设为5枚金币。因为每次奖励最多只有3枚金币，所以这个初始值很明显是高估的。我们称之为“乐观估计”。

之后仍然遵循纯贪心算法，即我们每次选择目前拥有最大价值估计的老虎机 —— argmax Q(a)。如果出现两台老虎机的Q值并列冠军的情况，那么就在它们之间随机选择。因为无论哪台老虎机都不会给出超过3枚金币，所以刚开始的一段时间里无论作何选择都只会降低Q值↓。

我们在 Ⓐ Ⓑ Ⓒ 三台老虎机上模拟一下这个新的探索方法：

Step 1：Ⓐ Ⓑ Ⓒ 刚开始都是并列最大（都是Q = 5)。我们随机选择Ⓑ机器，获得2枚金币，与初始Q值做平均，得最新Q值 为 (5+2)/2 = 3.5。

Step 2：现在Ⓐ = Ⓒ = 5，继续采用贪心算法，在并列最大的Ⓐ Ⓒ老虎机中随机选择。假设我们的选择是 Ⓐ，得金币1枚，那Ⓐ的新估计就变为 (5+1)/2 = 3.0。

Step 3：现在只有Ⓒ机拥有最大Q值，根据贪心算法，只可能选择Ⓒ机作为这一步的action。

从这个实例可以看出，即使用绝对贪心算法，也可以实现轮流选择不同action，而非固定exploit某一个选项。乐观探索法通过在初始值上做手脚，机智地平衡了exploration与exploitation。

上图是乐观探索法的实验结果。横轴代表了你在赌场的一千次尝试；纵轴是你正确选择了最佳老虎机的概率，这个概率越高，意味着算法判断越准确。

• 灰色曲线是之前提及的ε贪心算法，ε = 10%随机选择；

• 黑色曲线是乐观探索法，从初始Q值 = 5 出发，之后均为ε = 0，即纯贪心算法。

比较两曲线，开始时，乐观探索法因为做了大量exploration，比ε贪心获得的奖励低；但趋于稳定后，乐观探索能达到比ε贪心更好的效果。

2

第二个算法是 Upper-Confidence Bound（简称UCB，上限置信区间算法）。该算法相对比较复杂， 且只适用于Multi-arm Bandit问题，对别的强化学习问题并没有显著帮助。但因为它特别有趣，所以在此略作介绍。

我们采用【薄荷大法】的顺序分析一下：

M → Motivation：为什么要发明这个算法？

ε贪心算法以ε概率随机选择一个非最佳的action来进行探索。问题在于，很可能一台老虎机你已经试了1000次，但另一台你只试了50次。从统计上说，试验次数越多，得到价值估计就越准确；反之，试验次数越少，价值估计的不确定性就越大。但ε贪心算法完全没有考虑这一点，它只会不顾任何情况地随机试验。

IN → Intuition：解决这个问题的直观思路是什么？

Upper-Confidence Bound的中心思想，就是把上文提到的不确定性纳入探索过程，根据一个数学公式调整Q值的相对大小对最终决策的影响。校正过Q值之后，下一步的action就由纯贪心（简单的取最大值）来决定。

T → Technicality：我们来分析一下UCB公式：

• Q_t(a) 是原本未校正的Q值估计。

• t 是目前总共试验次数。

• N_t(a) 是尝试某一个老虎机 a 的次数。

• c 是可手动设置的超参数（hyper-parameter）。这个常数项控制了探索与开拓的平衡，其中的平方根可以直观地认为是某action的标准差。

其中，第二项分母N_t(a)，即某个action的实验次数越大，表达式的值就越小，意味着argmax越不容易选择这个action。换言之，当尝试某个action次数越多，那么Confidence（置信度）就越高，自然不需要更多的探索。

第二项分子中 t 越大，表达式的值也越大，argmax更可能探索这个action。直观的说，两个赌场里，假设③号老虎机的试验次数都是1000次（即N_t(③) = 1000）。如果第一个赌场的总次数是100万次，第二个赌场的总次数是2000次，则对③号老虎机的相对置信度是第一个赌场更低。

最后我们来分析一下超参数 c：

• 当 c 越大，第二项的值也越大，意味着我们越多地做探索。

• 当 c = 0，此式等价于未校正过的Q_t(a)，UCB算法退化为简单的纯贪心算法，相当于没有任何探索成分。

上图是Upper-Confidence Bound算法的实际运行效果。横轴是在赌场尝试的一千次试验，纵轴是平均获得的奖励。可见UCB（蓝线）自始至终比ε贪心（灰线）获得的奖励高。

在这一讲里，我们介绍了乐观探索和上限置信区间这两种更先进的探索策略。在下一期推送中，我们将以一种完全不同的思路来解决Multi-arm Bandit问题。