首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >小孩都看得懂的多臂老虎机和汤姆森采样

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

作者头像
用户5753894
发布2021-07-29 10:16:10
3.4K0
发布2021-07-29 10:16:10
举报
文章被收录于专栏:王的机器王的机器

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),随机出来的值大概率是小值,而小值在采样过程中很难胜出 (在这种情况下不会利用第三台机)

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

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

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-07-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 王的机器 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 0 老虎机
  • 1 老虎机胜率
  • 2 探索策略
  • 3 利用策略
  • 4 探索-利用策略
  • 5 贝塔分布
  • 6 采样前戏
  • 7 汤姆森采样
  • 8 WHY 汤姆森采样
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档