多臂老虎机 (multi-armed bandit, MAB) 是赌场里的一种游戏。首先展示单臂老虎机。
当你玩老虎机的时候,扭动右边的手臂,有两种结果发生,1. 得到奖励,2. 啥也没有。如下图所示。
如果你要面临从多个老虎机中选择最好的几个来玩,通常这种问题成为多臂老虎机问题。
每个老虎机都有可能出奖励或什么也不出,比如你每台机子玩一次,第 1, 2, 5 出来奖励,而第 3 和 4 台什么也没出。
每台老虎机都有各自的胜率,即出奖励的概率。下图左边的胜率为 0.1,右边的胜率为 0.7。
当你玩左边老虎机 10 次,你期望只有 1 次出奖励。当你玩右边老虎机 10 次,你期望有 7 次出奖励。
问题来了,每台老虎机的胜率在玩之前是未知的。
为了找到胜率最高的老虎机并继续玩下去来最大化收益,你需要一个策略。
最简单的策略就是探索 (explore) 每台老虎机多次,统计胜率。比如每台机子玩 15 次,根据出奖励个数估计这五台胜率分别为 2/15, 9/15, 12/15, 3/15 和 6/15。
显然,第三台机子胜率最高,可以一直玩它;第二台也 OK,可以时不时玩它;其他三台不用考虑了。
问题来了,这个探索策略听起来不错,但需要大量实验来证实,比如第一台机子胜率很低,但这是在你玩很多次的情况才能得到的结论。
我们能做得更好一点么?即用少量实验来提前区分好和坏老虎机?
可以的!
利用 (exploit) 策略就是用少量的实验来验证结论,如下图所示,每台机子只玩两次。
根据统计结果我们得出第二台老虎机胜率最高。
问题来了,我们知道 (假装事先知道) 其实第三台才是最好的,但是只玩两次根本识别不出来它。
我们能做得更好一点么?即用少量实验来提前区分“真正”好和坏老虎机?
可以的!
最优策略是同时探索和利用,有两大要义:
如下图所示,利用第 2 和 3 台老虎机,但是时不时也会探索一下第 5 台老虎机。
用这样的策略玩若干次,最终可以锁定最好的老虎机 - 第三台。
探索利用策略 (explore-exploit strategy) 是可行的,下面来看看实操是如何进行的。
实操技巧是汤姆森采样 (Thompson sampling),在介绍该技巧之前先复习贝塔分布。
假设对老虎机实验三次,得到结果是胜率都为 0.7,但哪种情况我们最有信心来声称该老虎机的胜率是 0.7?
老虎机真实的胜率是未知但确定的,我们通过实验得到结果都是采样而来的,这个采样结果本身是已知但随机的。比如你再做一次实验,得到的结果可能会不同。
因此我们需要一个概率分布来对老虎机胜率建模,而这个分布就是贝塔分布。
放在老虎机具体中,贝塔分布描述的是给定实验成功 (得到奖励) 和失败 (没得到奖励) 的次数而老虎机胜率的分布。关于贝塔分布的内容,请参考该系列上一贴。
三幅图相同的是,函数最大值都发生在 p = 2/3 时。三幅图不同的是,从左到右来看,峰越来越尖,展开越来越窄,即越来越有信心声称老虎机胜率为 2/3。
解释如下。在第一个老虎机对应的“肥胖”概率分布下,随机点可以非常自由的“跑动”,因此在很多情况下会偏离 2/3,而在第三个老虎机对应的“清瘦”概率分布下,随机点可以不能自由的“跑动”,因此在很多情况下不会偏离 2/3。
对于热爱数学公式的同学,下图满足你们的好奇心。
唯一需要注意的是贝塔函数写法的惯例是 B(a+1, b+1) 而不是 B(a, b),即在成功次数 a 和失败次数 b 都加上 1,记住就行了。
现在开始做一个简单采样,主要是观察采样结果和对应的贝塔概率分布函数图的关系。
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 负
前戏有感觉了么?有的话让我们来的硬核内容 -- 汤姆森采样。
假设在每台机子上经过了若干轮采样得到了如下情景。
下一步该选哪一台机子玩呢?步骤有二。
1. 在每台机对应的贝塔概率分布函数中随机选一个点。
2. 收集 4 个点对应的 4 个横坐标,找到最大值 (对应的是胜率最高的) 对应的老虎机玩下去。
更新选中老虎机的贝塔分布函数,重复其采样过程,不断玩下去。
什么?讲完了?汤姆森采样就这么简单!
同学们肯定有疑问,这么简单的采样技巧有用么?WHY?
看我给你娓娓道来。假设下图是马上要采样前的三台老虎机的现状。掐指一看觉得第一台好 (这么多奖励,答应我玩下去),第二台不确定 (才玩两次,可能是好机,想继续探索),第三台垃圾 (没有奖励,有多远滚多远)。
下面来看用汤姆森采样技巧得到的结果是否和你的直觉结果一致。
先看第一台机:
再看第二台机:
最后看第三台机:
汤姆森采样技巧得到结果和你的直觉结果高度一致。欧耶!
朋友们,你们弄懂了多臂老虎机和汤姆森采样了吗?