3.10 多臂老虎机算法

多臂老虎机算法(multi-arm bandit algorithm)是一种检验方法，尤其适用于 Web 测试。
相比于传统的统计学实验设计方法，它实现了明显的优化，并且能更快地做出决策。

• 主要术语

多臂老虎机
一种假想的老虎机，提供多个拉杆供用户选择，每个拉杆对应不同的收益，用于模拟多处理实验。
臂
表示实验中的一个处理，例如 Web 测试中的标题 A。
获胜
通过实验模拟老虎机上的获胜，例如客户点击了链接。

• 传统 A/B 测试 问题

传统的 A/B 测试需要根据特定的设计在实验中采集数据，去回答某个具体的问题。
例如: “处理 A 和处理 B 哪个更好?”
假定一旦问题得到解答，就结束实验，然后继续操作结果。

你可能已经发现，使用这一方法存在几个问题。

首先，我们得到的答案并不是结论性的，即“效果未证明”。 换句话说，实验结果可能会表明一个效果，但是我们没有足够的样本去证明所表明的效果，
也就无法确定效果是否符合传统的统计标准。这并未回答我们应该做出什么决策的问题。

其次，我们可能希望在实验得出结论前，就开始利用之前获得的结果。

再次，我们希望能根据实验结束后获得的其他数据，去更改我们的决策，或是尝试其他的事情。

传统的实验方法和假设检验方法可以追溯至 20 世纪 20 年代，这些方法是相当僵化的。
随着具有强大计算能力的计算机和软件的出现，我们可以使用一些更强大、更灵活的方法。
此外，数据科学(包括商业)并不十分关注统计显著性，而是更加关注整体工作和结果的优化。

• 什么是多臂老虎机算法

多臂老虎机算法在 Web 测试中广受欢迎，它可以一次测试多个处理，相比于传统的统计设计，它能更快地得出结论。
该算法以赌博中使用的老虎机命名，也称“单臂老虎机”，因为该算法在配置上实现了稳定地从赌徒那里掠取金钱。
让我们想象一台有多个拉杆的老虎机，每个拉杆以不同的速率付款，这就是一个多臂老虎机，即该算法全称的由来。

我们的目标是尽可能赢取更多的钱，具体地说，越早识别并确定可以获胜的拉杆越好。
但是挑战在于，我们并不知道各个老虎机拉杆的回报速率，只知道拉动老虎机拉杆的结果。
我们假设无论拉的是哪个拉杆，每次“获胜”将得到相同数额的回报，不同之处只在于获胜的概率。
进一步假设，我们初始尝试拉动每个拉杆 50 次，得到以下结果。

• 拉杆 A:拉动 50 次，获胜 10 次。
• 拉杆B:拉动50次，获胜2次。
• 拉杆C:拉动50次，获胜4次。

一种极端的做法是：
拉杆 A 看起来像是赢家，因此让我们放弃尝试拉动其他的拉杆，一直拉动拉杆 A。该做法充分利用了初始试验的结果。 如果拉杆 A 的确更优，我们就可以 尽早从中受益。
但另一方面，如果拉杆 B 和拉杆 C 事实上更好，那么我们就会失去发现这一点的偶然性。

另一种极端的做法是:
这看上去完全在随机范围内，让我们继续以均等的可能性拉动各个拉杆。
这一做法将给予拉杆 A 的替代者们一个充分展示的偶然性，但是在此过程中，我们的处理看上去并非最优。

问题在于这一做法将持续多长时间? 老虎机算法采用了一种混合的方法。

一开始，我们更频繁地拉动拉杆 A，充分利用该拉杆初始看上去更优的结果。
但我们并未放弃拉杆 B 和拉杆 C，只是较少地拉动它们。 如果拉杆 A 持续表现优异，我们将继续少拉动拉杆 B 和拉杆 C，而是更频繁地拉动拉杆 A。
而如果拉杆 C 的表现开始变好，拉杆 A 的结果开始变糟，这时我们可以减少拉动拉杆 A 的次数，转而频繁地拉动拉杆 C。
如果其中一个拉杆被证明是优于拉杆 A 的，只是由于随机性导致它未在初始试验中显现出来，那么现在就有偶然性在进一步的检验中得以显现。

• Web 测试

现在，我们考虑将算法应用于 Web 测试，这回测试的不再是多个老虎机拉杆，而是多个要在 Web 网站上测试的报价、标题、颜色等。
用户可以点击(即商家的“获胜”)，也可以不点击。

初始，各个报价的展示是随机且平等的。随着测试的开展，如果一个报价开始优于其他报价，那么可以更频繁地显示该报价(即“拉动拉杆”)。

但问题是，应该如何确定修改拉动速率的算法的参数? 拉动拉杆的速率”应该改成多少? 何时改变速率?

下面给出了一个简单的算法，它被称为 A/B 测试的 ε-贪心算法。 (1) 生成一个介于 0 和 1 之间的随机数。
(2) 如果随机数落在 0 和 ε 之间
其中，ε 是一个介于 0 和 1 之间的数字，通常非常小，则抛一次硬币(硬币是均匀的，即得到正反面的概率均为 50%)。
a. 如果硬币正面向上，显示报价 A。
b. 如果硬币反面向上，显示报价B。
(3) 如果随机数大于或等于 ε，显示迄今为止具有最高响应率的报价。

ε 是控制该算法的唯一参数
如果 ε = 1，最终得到的是一个标准的简单 A/B 测试，每个实 验对象在处理 A 和处理 B 之间随机分配。
如果 ε = 0，最终得到一个纯粹的贪心算法，贪心算法无须做进一步的实验，将实验对象(Web 访问者)分配给表现最好的处理即可。

• 汤普森抽样(Thompson’s sampling)方法

一个更复杂的算法，我们可以在每个阶段 中做一次“抽样”(拉动拉杆)，以最大化选择最佳拉杆的可能性。 当然，我们并不知道哪个拉杆是最佳的，而问题完全在于此!

但是随着每一次连续的抽取，我们都能获得收益，进而获得更多的信息。

汤普森抽样采用了贝叶斯方法，它首先使用 Beta 分布假设回报的先验分布，Beta 分布常用于指定贝叶斯问题中的先验情况。
随着每次抽取信息的累积，通过更新累积信息，我们就可以更好地优化下一次抽取，直至选取最优的拉杆。

老虎机算法可以有效地应对三种以上的处理，并趋向于最佳选择的方向。 对于传统的统计检验过程而言，三种以上处理决策的复杂性，远远超出了传统的 A/B 测试，因此老虎机算法颇具优势。

本节要点

1. 传统的 A/B 测试基于随机抽样过程，会导致过度地使用非最优处理。
2. 相比而言，多臂老虎机算法改进了抽样过程，加入了在实验过程中学到的信息，减少了非最优处理的频数。
3. 多臂老虎机算法还有助于有效地应对两种以上的处理。
4. 多臂老虎机具有多种不同的算法，能够解决如何将抽样概率从非最优处理转移到(假设的)最优处理的问题。