小孩都看得懂的多臂老虎机和汤姆森采样

0 老虎机

多臂老虎机 (multi-armed bandit, MAB) 是赌场里的一种游戏。首先展示单臂老虎机。

当你玩老虎机的时候，扭动右边的手臂，有两种结果发生，1. 得到奖励，2. 啥也没有。如下图所示。

如果你要面临从多个老虎机中选择最好的几个来玩，通常这种问题成为多臂老虎机问题。

每个老虎机都有可能出奖励或什么也不出，比如你每台机子玩一次，第 1, 2, 5 出来奖励，而第 3 和 4 台什么也没出。

1 老虎机胜率

每台老虎机都有各自的胜率，即出奖励的概率。下图左边的胜率为 0.1，右边的胜率为 0.7。

当你玩左边老虎机 10 次，你期望只有 1 次出奖励。当你玩右边老虎机 10 次，你期望有 7 次出奖励。

问题来了，每台老虎机的胜率在玩之前是未知的。

为了找到胜率最高的老虎机并继续玩下去来最大化收益，你需要一个策略。

2 探索策略

最简单的策略就是探索 (explore) 每台老虎机多次，统计胜率。比如每台机子玩 15 次，根据出奖励个数估计这五台胜率分别为 2/15, 9/15, 12/15, 3/15 和 6/15。

显然，第三台机子胜率最高，可以一直玩它；第二台也 OK，可以时不时玩它；其他三台不用考虑了。

问题来了，这个探索策略听起来不错，但需要大量实验来证实，比如第一台机子胜率很低，但这是在你玩很多次的情况才能得到的结论。

我们能做得更好一点么？即用少量实验来提前区分好和坏老虎机？

可以的！

3 利用策略

利用 (exploit) 策略就是用少量的实验来验证结论，如下图所示，每台机子只玩两次。

根据统计结果我们得出第二台老虎机胜率最高。

问题来了，我们知道 (假装事先知道) 其实第三台才是最好的，但是只玩两次根本识别不出来它。

我们能做得更好一点么？即用少量实验来提前区分“真正”好和坏老虎机？

可以的！

4 探索-利用策略

最优策略是同时探索和利用，有两大要义：

1. 一直利用好的
2. 随机探索差的

如下图所示，利用第 2 和 3 台老虎机，但是时不时也会探索一下第 5 台老虎机。

用这样的策略玩若干次，最终可以锁定最好的老虎机 - 第三台。

探索利用策略 (explore-exploit strategy) 是可行的，下面来看看实操是如何进行的。

实操技巧是汤姆森采样 (Thompson sampling)，在介绍该技巧之前先复习贝塔分布。

5 贝塔分布

假设对老虎机实验三次，得到结果是胜率都为 0.7，但哪种情况我们最有信心来声称该老虎机的胜率是 0.7？

老虎机真实的胜率是未知但确定的，我们通过实验得到结果都是采样而来的，这个采样结果本身是已知但随机的。比如你再做一次实验，得到的结果可能会不同。

因此我们需要一个概率分布来对老虎机胜率建模，而这个分布就是贝塔分布。

放在老虎机具体中，贝塔分布描述的是给定实验成功 (得到奖励) 和失败 (没得到奖励) 的次数而老虎机胜率的分布。关于贝塔分布的内容，请参考该系列上一贴。

三幅图相同的是，函数最大值都发生在 p = 2/3 时。三幅图不同的是，从左到右来看，峰越来越尖，展开越来越窄，即越来越有信心声称老虎机胜率为 2/3。

解释如下。在第一个老虎机对应的“肥胖”概率分布下，随机点可以非常自由的“跑动”，因此在很多情况下会偏离 2/3，而在第三个老虎机对应的“清瘦”概率分布下，随机点可以不能自由的“跑动”，因此在很多情况下不会偏离 2/3。

对于热爱数学公式的同学，下图满足你们的好奇心。

唯一需要注意的是贝塔函数写法的惯例是 B(a+1, b+1) 而不是 B(a, b)，即在成功次数 a 和失败次数 b 都加上 1，记住就行了。

6 采样前戏

现在开始做一个简单采样，主要是观察采样结果和对应的贝塔概率分布函数图的关系。

1. 还没开始采样，所有函数都是 B(1, 1)，0 胜 0 负

2. 第一台机子出来奖励，目前胜率为 1，函数更新为 B(2, 1)，1 胜 0 负

3. 第二台机子没出来奖励，目前胜率为 0，函数更新为 B(1, 2)，0 胜 1 负

4. 第二台机子第二次出来了奖励，目前胜率为 0.5，函数更新为 B(2, 2)，1 胜 1 负

前戏有感觉了么？有的话让我们来的硬核内容 -- 汤姆森采样。

7 汤姆森采样

假设在每台机子上经过了若干轮采样得到了如下情景。

下一步该选哪一台机子玩呢？步骤有二。

1. 在每台机对应的贝塔概率分布函数中随机选一个点。

2. 收集 4 个点对应的 4 个横坐标，找到最大值 (对应的是胜率最高的) 对应的老虎机玩下去。

更新选中老虎机的贝塔分布函数，重复其采样过程，不断玩下去。

8 WHY 汤姆森采样

什么？讲完了？汤姆森采样就这么简单！

同学们肯定有疑问，这么简单的采样技巧有用么？WHY？

看我给你娓娓道来。假设下图是马上要采样前的三台老虎机的现状。掐指一看觉得第一台好 (这么多奖励，答应我玩下去)，第二台不确定 (才玩两次，可能是好机，想继续探索)，第三台垃圾 (没有奖励，有多远滚多远)。

下面来看用汤姆森采样技巧得到的结果是否和你的直觉结果一致。

先看第一台机：

• 你的直觉：好机，这么多奖励，答应我玩下去
• 汤姆森采样：分布函数偏右 (skew to right)，随机出来的值大概率是大值，而大值可在采样过程中胜出 (在这种情况下不断利用第一台机)

再看第二台机：

• 你的直觉：不确定，才玩两次，可能是好机，想继续探索
• 汤姆森采样：分布函数很宽包含了很多胜率值，随机出来的值有概率是大值，还是可以在采样过程中胜出 (在这种情况下探索第二台机成功了)

最后看第三台机：

• 你的直觉：坏 (垃) 机 (圾)，没有奖励，有多远滚多远
• 汤姆森采样：分布函数偏左 (skew to left)，随机出来的值大概率是小值，而小值在采样过程中很难胜出 (在这种情况下不会利用第三台机)

汤姆森采样技巧得到结果和你的直觉结果高度一致。欧耶！

朋友们，你们弄懂了多臂老虎机和汤姆森采样了吗？