多臂老虎机是一个在探索(exploration)和开发(exploitation)过程中寻找最高收益的问题。此类“实验”能力几乎已经成为了优秀实验平台的标配。
本篇是阅读《A modern Bayesian look at the multi-armed bandit》后结合个人理解的学习总结。它总结了基于贝叶斯的随机概率匹配法和其它相关方法。
定义 代表t时为止的奖励序列， 代表t时选择的臂，t时刻奖励 ， 是一个未知向量。
情况下两种例子：
定义 是 的期望值，最佳策略应该一直选择 最大的臂。
在伯努利分布下， 。
定义 是 的先验概率密度，此时以 产生 ， 产生y，则0时刻选择a正确概率：
定义 为指示函数， 时 ：
如果没有关于 的先验，则先验视为各个 是一样的， 是均匀分布。
观测到奖励情况后，通过贝叶斯方法进行更新， 。t时刻：
随机概率匹配用 来分配a的t+1时观测值，通过一种自然平衡探索与开发的方式。
如果 是来自 的独立抽样，则基于大数定理：
如果 是指数族，而且 是它的共轭分布，则可以独立的抽样 ，否则可以用马可夫相关的方法进行抽样模拟。
的后验抽样足够对概率匹配进行支持 。
（5）可以不用显式计算，从 模拟 ，并选择
随机概率匹配自然的包含了不确定性，下图为两臂情况下的情况：
在(a)中，错误选中概率为18%；在(b)中，错误选中概率为0.8%。
这个例子说明，随着学习的进行，探索的占比会减少。
此方法假设单臂未来的奖励会与一个几何分布有关： ，其中
基廷斯提供了一种计算各个臂价值的算法，得到的结果称为 基廷斯指数 。它在前提可保证时是最优方案。
这部分的数学相关很复杂先跳过，简单了解可参考《算法之美》第二章相关部分。
对基廷斯指数的三个问题：
计算每个手臂奖励均值及置信区间上限，然后选上限最高的手臂。
值得注意的是，此上限并不是常见的置信区间算法，而且比较难计算。
概率匹配结合了2.3中的多种好处。
定义 ，先验为 ，它们之间相互独立。
分别代表t时刻a的累计成功次数和观测次数。
则 的后验为：
其中 是贝塔分布。此时最佳概率为：
验证主要关注regret，最佳选择 ，手臂a在t时刻的观测次数为 ，则t时刻的regret为：
则T时段累计regret为 。以下是一些模拟对比结果。
从测试数据看RPM会比后者好得多。
可发现在批量更新场景，两种贪心策略效果都是比RPM差的。
平均效果来看，RPM效果最差，但是它的标准差最小，最优解命中率最高；参数为0.999的Gittins index平均效果最好，标准差较大，且最优解的命中率低于RPM。
RPM可以用来解决多臂老虎机问题，它基于后验抽样，易于实现、健壮性好，且在批量更新场景表现更佳。
此外这是一篇学习记录，个人理解可能不够到位，任何问题欢迎留言。