关注我们，一起学习~
1. 导读
学习bandit算法过程中的一些笔记与总结，一起来学bandit算法吧。
MAB问题又称多臂老虎机问题，一个老虎机上有多个老虎臂，每次摇动不同的臂会得到不同的收益，那么如何才能让多次尝试后整体收益最大？这就是多臂老虎机问题。
MAB问题可以采用Bandit算法来解决，Bandit算法的 思想 是希望在多次摇臂后的累积遗憾最小，遗憾即为最好收益与实际收益的差值。这类方法通常包含三个方面， 环境、臂和回报 。在推荐系统中， 不同的策略或者不同的物料池就是不同的臂，而回报就是指用户的反馈 。
在推荐系统中Bandit算法通常可用于冷启动和EE问题， 冷启动问题 即当新用户或新商品出现时，在系统中缺乏他们的交互数据，从而对兴趣推荐造成困扰；推荐系统中的 EE问题 为Exploration（探索）和Exploitation（利用）问题。
- Exploitation ：利用用户的历史行为发掘用户的兴趣，利用当前可能的最优方案，即在推荐系统中就是采用模型预测到的商品进行推荐。
- Exploration ：如果一直只是根据用户的历史行为进行推荐，可能会一直给用户推送相似的产品，而忽略了用户其他的兴趣，因此需要采用其他方案对用户潜在的兴趣进行探索。
因此，探索和利用是两个相互对立，需要相互权衡的点，一方面要关注用户的既有兴趣，另一方面需要探索用户更多其他兴趣。因此如何权衡两者，通常可以采用以下方法。
2. Epsilon-Greedy算法
epsilon-greedy算法是最简单粗暴的方案，该算法是一种贪心策略，因此它每次以1-epsilon的概率选取当前最优的“臂”，以epsilon的概率进行探索，即随机选择其他“臂”。这里最优的臂可以对应于推荐模型计算得到的商品，而其他臂则为剩余的商品。
3. 汤普森采样
汤普森采样（Thompson sampling）基本原理：每个臂是否产生收益符合其背后的一个概率分布，即有一定的概率p能产生收益，1-p不能产生收益；每次做选择时，每个臂对应的概率分布会产生一个随机数，选择最大随机数对应的臂。
这里的分布采用beta分布，beta分布涉及到两个参数，α和β，其 特性如下 ：
- 当α+β的值越大，则分布曲线越窄，产生的随机数容易接近中心；
- α/(α+β)的值越大，分布的中心越靠近1，从而使得产生的随机数也会偏向0或1。
- 想了解beta分布的小伙伴可以参考该链接：https://www.zhihu.com/question/30269898
从而可以得到三类情况，
-
曲线窄且靠近1
-
曲线窄且靠近0
-
曲线宽
例子 ：在为某用户推荐商品时，若把参数α看做推荐该商品后，该用户点击该商品的次数，β看做未点击的次数，则 流程如下 ：
-
取出每个商品对应的α和β；
-
利用beta分布计算得到一个随机数；
-
选出最大随机数对应的商品进行推荐；
-
若该用户点击则α+1，反之β+1
上述为网上的例子，该例子是将候选商品作为了臂。
有效的原因 ：
-
若某个商品被选中多次且点击多次，即用户对该商品很感兴趣，说明该商品收益好，值得被推荐。此时，α+β会较大，而整体曲线会比较窄，并且α/(α+β)也会比较大，这样窄且接近1使得得到的随机数会很多时候都是较大的，从而该商品被推荐的概率会较高。
-
若探索次数不够，无法确定该商品对该用户是否有用，即α+β的值较小，则整个曲线会较宽，需要经过充分太多才能将分布逐渐稳定。
4. UCB算法
置信区间上界（Upper Confidence Bound，UCB）算法，该方法和汤普森采样过程类似，也是从每个臂中得到分数，然后选取分数最高的臂进行推荐，得到反馈后进行更新，其公式为下式，其中表示t次UCB后到目前为止的第j条臂的平均收益，t是目前为止的总次数，T表示第j条臂在t次中被选中的次数。加号右边反映了一种不确定性，再结合平均收益来反映这次可以得到的收益上界。可以发现， 被选中的次数越多，说明越稳定，因此就用平均收益可以较好反映这条臂；而如果被选中的少，则说明不确定性大，有更大的置信区间的范围 。
问题 ：当然像UCB，汤普森采样这样的方法需要遍历所有臂，以此来选取值最大的臂从而进行推荐，这使得对整个遍历空间提出了限制，通常会将其商品集合进行缩小，从而加快运算速度。对于整个商品空间进行遍历的方案，具可以参考之前的分享WSDM'22「微软+美团」探索与利用EE：HCB在整个商品空间探索。
参考
https://blog.csdn.net/qq\_20417499/article/details/105984076
https://blog.csdn.net/lyx\_yuxiong/article/details/81237416
https://www.zhihu.com/question/30269898
精彩推荐
交流群：联系作者-备注“研究方向-公司或学校”
长按关注
更多精彩
秋枫学习笔记
文章好看点这里