16 | 简单却有效的Bandit算法
刑无刀
该思维导图由 AI 生成，仅供参考
我在之前的文章中表达过，推荐系统的使命就是在建立用户和物品之间的连接。建立连接可以理解成：为用户匹配到最佳的物品；但也有另一个理解就是，在某个时间某个位置为用户选择最好的物品。
推荐就是选择
生活中，你我都会遇到很多要做选择的场景。上哪个大学，学什么专业，去哪家公司，中午吃什么等等。这些事情，都让选择困难症的我们头很大。头大在哪呢？主要是不知道每个选择会带来什么后果。
你仔细想一下，生活中为什么会害怕选择，究其原因是把每个选项看成独一无二的个体，一旦错过就不再来。推荐系统中一个一个单独的物品也如此，一旦选择呈现给用户，如果不能得到用户的青睐，就失去了一个展示机会。如果跳出来看这个问题，选择时不再聚焦到具体每个选项，而是去选择类别，这样压力是不是就小了很多？
比如说，把推荐选择具体物品，上升到选择策略。如果后台算法中有三种策略：按照内容相似推荐，按照相似好友推荐，按照热门推荐。每次选择一种策略，确定了策略后，再选择策略中的物品，这样两个步骤。
那么，是不是有办法来解决这个问题呢？当然有！那就是 Bandit 算法。
MAB 问题
Bandit 算法来源于人民群众喜闻乐见的赌博学，它要解决的问题是这样的。
一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么想最大化收益该怎么整？
这就是多臂赌博机问题 (Multi-armed bandit problem, K-armed bandit problem, MAB)，简称 MAB 问题。有很多相似问题都属于 MAB 问题。
假设一个用户对不同类别的内容感兴趣程度不同，当推荐系统初次见到这个用户时，怎么快速地知道他对每类内容的感兴趣程度？这也是推荐系统常常面对的冷启动问题。
假设系统中有若干广告库存物料，该给每个用户展示哪个广告，才能获得最大的点击收益，是不是每次都挑收益最好那个呢？
算法工程师又设计出了新的策略或者模型，如何既能知道它和旧模型相比谁更靠谱又对风险可控呢？
这些问题全都是关于选择的问题。只要是关于选择的问题，都可以简化成一个 MAB 问题。
我在前面的专栏中提过，推荐系统里面有两个顽疾，一个是冷启动，一个是探索利用问题，后者又称为 EE 问题：Exploit－Explore 问题。针对这两个顽疾，Bandit 算法可以入药。
冷启动问题好说，探索利用问题什么意思？
利用意思就是：比较确定的兴趣，当然要用啊。好比说我们已经挣到的钱，当然要花啊。
探索的意思就是：不断探索用户新的兴趣才行，不然很快就会出现一模一样的反复推荐。就好比我们虽然有一点钱可以花了，但是还得继续搬砖挣钱啊，要不然，花完了就要喝西北风了。
Bandit 算法
Bandit 算法并不是指一个算法，而是一类算法。现在就来介绍一下 Bandit 算法家族怎么解决这类选择问题的。
首先，来定义一下，如何衡量选择的好坏？Bandit 算法的思想是：看看选择会带来多少遗憾，遗憾越少越好。在 MAB 问题里，用来量化选择好坏的指标就是累计遗憾，计算公式如图所示。
简单描述一下这个公式。公式有两部分构成：一个是遗憾，一个是累积。求和符号内部就表示每次选择的遗憾多少。
Wopt 就表示，每次都运气好，选择了最好的选择，该得到多少收益，WBi 就表示每一次实际选择得到的收益，两者之差就是“遗憾”的量化，在 T 次选择后，就有了累积遗憾。
在这个公式中：为了简化 MAB 问题，每个臂的收益不是 0，就是 1，也就是伯努利收益。
这个公式可以用来对比不同 Bandit 算法的效果：对同样的多臂问题，用不同的 Bandit 算法模拟试验相同次数，比比看哪个 Bandit 算法的累积遗憾增长得慢，那就是效果较好的算法。
Bandit 算法的套路就是：小心翼翼地试，越确定某个选择好，就多选择它，越确定某个选择差，就越来越少选择它。
如果某个选择实验次数较少，导致不确定好坏，那么就多给一些被选择机会，直到确定了它是金子还是石头。简单说就是，把选择的机会给“确定好的”和“还不确定的”。
Bandit 算法中有几个关键元素：臂，回报，环境。
臂：是每次选择的候选项，好比就是老虎机，有几个选项就有几个臂；
回报：就是选择一个臂之后得到的奖励，好比选择一个老虎机之后吐出来的金币；
环境：就是决定每个臂不同的那些因素，统称为环境。
将这个几个关键元素对应到推荐系统中来。
臂：每次推荐要选择候选池，可能是具体物品，也可能是推荐策略，也可能是物品类别；
回报：用户是否对推荐结果喜欢，喜欢了就是正面的回报，没有买账就是负面回报或者零回报；
环境：推荐系统面临的这个用户就是不可捉摸的环境。
下面直接开始陈列出最常用的几个 Bandit 算法。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
Bandit算法是一种解决选择问题的算法，源自赌博学，用于解决多臂赌博机问题(MAB问题)。在推荐系统中，Bandit算法可以应用于解决冷启动和探索利用问题。文章介绍了几种常用的Bandit算法，包括汤普森采样、UCB算法和Epsilon贪婪算法，并通过模拟试验对它们的效果进行了对比。汤普森采样以其简单实现和显著效果备受青睐。此外，文章还探讨了Bandit算法在解决推荐系统冷启动问题中的应用思路。总的来说，Bandit算法将用户视为多变的环境，将待推荐的物品视为赌场里的老虎机摇臂，通过不断试错来实现推荐。文章以简洁明了的语言介绍了Bandit算法的核心思想和关键元素，并为读者留下了一个问题，引发读者的思考和讨论。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《推荐系统三十六式》，新⼈⾸单¥59
《推荐系统三十六式》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(14)
- 最新
- 精选
🐱您的好友William🐱bandit是 reinforcement learning 的只有一个state和多个action的情况，我觉得thompson sampling的问题好像是它应该是有一个assumption，它假设了每个action背后会不会有反馈是一个Bernoulli Distribution，但是人的兴趣会不断地变化，所以assumption可能不hold，所以需要不断地online learning估计才行。在我来看，UCB最能直接反应问题的本质，我比较喜欢UCB。作者回复: 你说得很对，同时我佩服你这中英文输入法切换自如的功力。
2018-10-0329
那年岁月Thompson采样，既然是冷启动用户，都初始化为1，下次这个用户可能就不是冷启动了，这个矩阵就没用了啊。只存储m个物品的矩阵就行吧作者回复: 你不要这么机械理解冷启动，数据不足都算是冷启动，
2018-04-101
王千发请问对于新item的冷启动，应该怎么做呢？大致思路是怎样的？作者回复: 内容相似是个常用办法。
2019-02-26
大猫星球目前我们冷启动采用标签与topic探索推荐作者回复: 值得尝试。
2018-04-13
林彦1. Epsilon贪婪算法的不足: (1) Epsilon贪婪算法中的概率值(Epsilon值)定多少是合理的，能由候选集的条件判断比较合理的范围吗？这个值需要做试验和根据算法结果调整吗？ (2) 如果p值是固定的，总有一部分用户是肯定要看到不好的结果的，随着算法搜集到更多的反馈不会改善这个效果。 (3) 如果有大量的劣质资源，即使平均收益最大的臂可能都比整个候选集中最好的臂的收益差很多。Exploration的过程中会导致用户对整个系统丧失耐心，好的坏的都不愿意反馈。这样Exploit到好的候选的几率就更低，时间更长，需要更多的用户来做试验。 (4) 如何在实际环境中衡量Epsilon贪婪算法对整体的贡献，怎么知道多少次点击或多少用户之后的临界值来判断这个算法是对整体起足够多的正面作用的？ 2. UCB算法的不足: 候选多时，很多候选都没有显示过，平均收益和其标准差会相同。这时候如何排序？如果纯粹随机，就可能需要较长时间得到候选集中更好的结果。UCB算法本质上是“确定性”（Deterministic）算法，随机探索的能力受到一定限制。 3. 汤普森采样的不足: 汤普森采样相对已经比较好了，我自己想不出更好的解决办法。当有相当数量的候选点击率和点击次数都很接近时，系统Explore到好的候选需要一些资源 (时间，用户等)。回到上面Epsilon贪婪算法的不足中的(3)。如果开始时有大量的劣质资源，没有人工干预发现好的候选比较耗时，整个系统可能还未来得及给用户推荐好的候选已经进入负循环。 Epsilon贪婪算法的不足的(3)和(4)适用于所有的Bandit算法。2018-04-09128
曾阿牛讲得很直白，赞。回到正题： 1）Bandit算法是试验型算法，基于大数定理，收敛应该不快 2）汤普森算法保留的参数量有点大，适用场景有点受限2018-04-105
yya这个属于强化学习的方法吗2018-04-091- Geek_015fd0exp3算法是不是比它们更好一些？2021-05-18
指尖旋律Bandit算法是反映了用户的一个长期兴趣吗，一般会考虑长期使用bandit算法建立的标签体系吗？如果使用了如何考虑时间因素呢2019-09-11
mi2mn个参数会不会太稀疏了啊？会不会导致a和b参考意义不大呢？2019-04-01
收起评论
