文章是对Context-free Bandit算法进行总结，以及对每个策略的一些思考。主要会从以下4个方面说明Context-free Bandit，如有问题，欢迎指正讨论~

1、Bandit来源

2、应用场景

3、算法原理

4、算法缺点

来源

多臂老虎机:

刚进赌场，每个臂代表着一个老虎机，怎么选择最优的赢钱策略

应用场景

1、推荐系统中的EE问题

2、推荐系统的冷启动问题

原理（有策略地快速试一试）

1、整体框架(Bandit如何同推荐场景结合)

主要通过前期实验，来刻画每一个新用户对每个Topic的感兴趣概率

1、每一个臂：代表不同的Topic

2、在推荐场景中，针对每一个用户，用Bandit策略为每一个Topic采样/计算一个得分。

3、得到得分后，进行排序，输出TopN的推荐

4、获取用户的反馈，更新到Bandit策略中

5、用户反馈评估方法：累积遗憾
$$R_T=\sum _{i=1}^T(w_{\ast }-W_{B(i)})$$

w* 每次实验所有臂中最佳那个

wB(i)是第i次试验时被选中臂的期望收益

2、不同的Bandit算法

2-1、Thompson sampling算法

假设

• 假设每个臂是否产生收益，其背后有一个概率分布，产生收益的概率为p
• 假设概率p的概率分布符合beta(wins, lose)分布，它有两个参数: wins, lose

beta分布

（简单总结)
横轴：值（范围在0-1）   纵轴：值对应的概率密度
beta(1,1): 直线，每个值的概率相同
beta(100, 1): 高值的概率高
beta(1, 100): 低值的概率高

方法

• 每个臂都维护一个beta分布的参数。每次试验后，选中一个臂，摇一下，有收益则该臂的wins增加1，否则该臂的lose增加1。
• 每次选臂：用每个臂现有的beta分布产生一个随机数，选择所有臂产生的随机数中最大的那个臂去摇

2-2、UCB算法

总结

以arm收益均值的置信区间上限代表对该arm未来收益的预估值

方法

• 初始化：先对每一个臂都试一遍
• 按照如下公式计算每个臂的分数，然后选择分数最大的臂作为选择$$x_j(t)+\sqrt{(\frac{2lnt}{T_{j,t}}})$$

xj(t) 为臂的目前的收益均值
t为目前总实验次数，$T_{j,t}$为当前臂的实验次数

• 针对于Upper Confidence的理解：

当 $T_{j,t}$ 当前arm尝试次数越多时，arm收益均值与置信上限的差值越小，越有置信度

理解：

• 这个方法能让没有机会尝试的arm得到更多尝试的机会
• 对于未知或较少尝试的arm，尽管其均值可能很低，但是由于其不确定性会导致置信区间的上界较大，从而有较大的概率触发exploration
• 对于已经很熟悉的arm(尝试过较多次)，更多的是触发exploitation机制：如果其均值很高，会获得更多的利用机会；反之，则会减少对其尝试的机会

2-3、Epsilon-Greedy算法

• 选一个（0,1）之间较小的数作为epsilon；
• 每次以概率epsilon做一件事：所有臂中随机选一个；
• 每次以概率1-epsilon 选择截止到当前，平均收益最大的那个臂。

理解：

epsilon的值可以控制对Exploit和Explore的偏好程度。越接近0，越保守

2-4、Epsilon-decay算法

• 同epsilon-Greedy基本相同，对epsilon增加衰减系数，前期偏向于Explore，后期epsilon逐渐减小，偏向于Exploit
• 表现在代码中为：

epsilon=max(epsilon*decay_rate,min_temp)

2-5、Greedy

• 先随机试若干次，计算每个臂的平均收益，一直选均值最大那个臂

2-6、random

随机选择一个臂

3、实验结果

整体缺点

算法层

• 忽略特征：将每个Topic看成独立的个体，缺少每个Topic信息的构造，导致预测结果可能存在偏差。

应用层

• 需要较长的时间测试，在前期可能得到一些错误的结论，尤其对于数据较小的推荐场景。

• AB测试不能以天为单位，需要一个整体周期进行AB测试。

• AB测试后，如果全量覆盖，对照组用户需要一定时间的学习。针对对照组用户，在这段时间内用户体验跟之前不一致。

参考资料

https://www.zhihu.com/question/30269898

https://zhuanlan.zhihu.com/p/21388070

http://rob.schapire.net/papers/www10.pdf

https://www.quora.com/What-are-the-practical-drawbacks-of-multi-armed-bandit-testing-as-applied-to-conversion-optimization

最后

以上就是魁梧可乐为你收集整理的Context-free Bandit算法来源应用场景原理（有策略地快速试一试）整体缺点参考资料的全部内容，希望文章能够帮你解决Context-free Bandit算法来源应用场景原理（有策略地快速试一试）整体缺点参考资料所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。