Bandit算法学习与总结（一）

关注我们，一起学习~

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