背景
多臂老虎机是一个在探索(exploration)和开发(exploitation)过程中寻找最高收益的问题。此类“实验”能力几乎已经成为了优秀实验平台的标配。
本篇是阅读《A modern Bayesian look at the multi-armed bandit》后结合个人理解的学习总结。它总结了基于贝叶斯的随机概率匹配法和其它相关方法。
1. 随机概率匹配（RPM）
定义)
代表t时为止的奖励序列，
代表t时选择的臂，t时刻奖励)
，
是一个未知向量。
)
情况下两种例子：
- 伯努利老虎机，
)
，)
参数为
- fractional factorial bandit（本文不关注）
定义%20%3D%20E(y_t%20%7C%20%5Ctheta%2C%20a_t%20%3D%20a))
是)
的期望值，最佳策略应该一直选择)
最大的臂。
在伯努利分布下，)
。
定义)
是的先验概率密度，此时以产生，产生y，则0时刻选择a正确概率：
)
（1)
定义)
为指示函数，
时%3D1)
：
)%20%3D%20%5Cint%20I_a(%5Ctheta)%20p(%5Ctheta)%20d%5Ctheta)
（2）
如果没有关于的先验，则先验视为各个
是一样的，
是均匀分布。
观测到奖励情况后，通过贝叶斯方法进行更新，%20%3D%20%5Cfrac%7Bp(Y_t%7C%5Ctheta)p(%5Ctheta)%7D%7Bp(Y_t)%7D)
。t时刻：
%20%5Cpropto%20p(%5Ctheta)%5Cprod%20_%7B%5Ctau%20%3D%201%7D%5Et%20f_%7Ba_%5Ctau%7D(y%7C%5Ctheta))
(3)
则此时%20%3D%20E(I_a(%5Ctheta)%20%7C%20Y_t%20))
（4）
随机概率匹配用
来分配a的t+1时观测值，通过一种自然平衡探索与开发的方式。
1.1 概率分配计算
如果%7D%2C...%2C%5Ctheta%5E%7B(G)%7D)
是来自)
的独立抽样，则基于大数定理：
.)
（5）
如果
是指数族，而且是它的共轭分布，则可以独立的抽样，否则可以用马可夫相关的方法进行抽样模拟。
的后验抽样足够对概率匹配进行支持。
1.2 隐式分配
（5）可以不用显式计算，从模拟 
，并选择)
1.3 探索(exploration)、开发(exploitation)和不确定性
随机概率匹配自然的包含了不确定性，下图为两臂情况下的情况：
Figure 1. One thousand draws from the joint distribution of two independent beta distributions.
In both cases, the horizontal axis represents a beta (20,30) distribution. The vertical axis is
(a) beta(2,1) and (b) beta(20,10).
在(a)中，错误选中概率为18%；在(b)中，错误选中概率为0.8%。
这个例子说明，随着学习的进行，探索的占比会减少。
2. 其它方法
2.1 The Gittins index(基廷斯指数)
此方法假设单臂未来的奖励会与一个几何分布有关：
，其中
基廷斯提供了一种计算各个臂价值的算法，得到的结果称为基廷斯指数。它在前提可保证时是最优方案。
Brezzi and Lai’s approximation to the Gittins index for the binomial bandit
problem with (a) �γ=0.8 and (b) �γ=0.999.
这部分的数学相关很复杂先跳过，简单了解可参考《算法之美》第二章相关部分。
对基廷斯指数的三个问题：
- 不完全学习，可能最终收敛到次优解；
- 各臂的参数需要是固定的；
- 奖励减少结构必须是几何分布。
2.2 UCB算法(Upper Confidence Bounds)
计算每个手臂奖励均值及置信区间上限，然后选上限最高的手臂。
值得注意的是，此上限并不是常见的置信区间算法，而且比较难计算。
2.3 启发式策略
-
2.3.1 平均分配
次策略均匀的探索每个臂，直到其中一个臂奖励超过某个阈值，然后一直选择此臂。这种方法对探索效果很好，但是前期成本高，导致整体奖励效果较差。类似于先进行一轮随机实验评估效果，然后选择效果最好的方案。
-
2.3.2 连胜就继续，输了就换其它
至少好于随机选择……当最优秀的策略效果也没有特别好时，此方案会过度探索，导致效果很差。
-
2.3.3 贪心策略
简单的贪心策略效果很差，比较好的是deterministic probability matching做法。但是在批量更新场景，一个更新周期只能探索一种方案，所以前期会表现特别差。
-
2.3.4 混合策略
混合策略是贪心之外，强制进行一定比例的探索，比如Epsilon-greedy或Epsilon-decreasing。不过上两种方法的敏感度不够高，因此还可以参考Softmax learning方法。
2.4 与概率匹配的对比
概率匹配结合了2.3中的多种好处。
3. 伯努利老虎机上使用不同策略的对比
定义，先验为)
，它们之间相互独立。
分别代表t时刻a的累计成功次数和观测次数。
则的后验为：
%20%3D%5Cprod%20%5Ek_%7Ba%3D1%7DBe(%5Ctheta_a%7CY_%7Bat%7D%2B1%2CN_%7Bat%7D%20-%20Y_%7Bat%7D%20%2B%201))
(10)
其中)
是贝塔分布。此时最佳概率为：
%5Cprod_%7Bj%5Cneq%20a%7DPr(%5Ctheta_j%20%3C%20%5Ctheta_a%20%7C%20Y_%7Bjt%7D%20%2B%201%20-%20N_%7Bjt%7D%20-%20Y_%7Bjt%7D%20%2B%201)d%5Ctheta_a)
(11)
验证主要关注regret，最佳选择%20%3D%20max_a%5C%7B%5Cmu_a(%5Ctheta)%20%5C%7D)
，手臂a在t时刻的观测次数为
，则t时刻的regret为：
%20-%20%5Cmu_a(%5Ctheta)))
(12)
则T时段累计regret为
。以下是一些模拟对比结果。
3.1 批量更新场景
3.1.1 RPM对比平均分配
Cumulative regret in each of 100 simulation experiments under (a) randomized probability
matching and (b) equal allocation. Note that the scales differ by an order of magnitude. For comparison
purposes, both panels include a rug-plot showing the regret distribution under probability matching.
Expected regret per time period under (a) randomized probability matching and (b) equal
allocation. Boxplots show variation across 100 simulated experiments.
Evolution of the posterior distribution (means and upper and lower 95% credibility bounds)
of under (a) randomized probability matching and (b) equal allocation. Each panel corresponds to an
arm. Arms are sorted according to optimality probability when the experiment ends.
从测试数据看RPM会比后者好得多。
3.1.2 RPM对比贪心
Regret from deterministic probability matching. The first ten periods
were spent learning the parameters of each arm.
(a) Stacked stripchart showing cumulative regret after excluding the first 10 test periods. Panel
(b) shows means and standard deviations of the expected losses plotted in panel (a). Greedy methods
have a higher chance of zero regret. Randomized probability matching has a lower variance.
可发现在批量更新场景，两种贪心策略效果都是比RPM差的。
3.2 实时更新场景
(a) Expected regret under real-time sampling across 100 experiments, each simulated for 10 000
time steps and (b) mean and standard deviation of the expected losses plotted in panel (a), along with the
percentage of experiments for which the optimal arm was selected at time 10 000.
平均效果来看，RPM效果最差，但是它的标准差最小，最优解命中率最高；参数为0.999的Gittins index平均效果最好，标准差较大，且最优解的命中率低于RPM。
后记
RPM可以用来解决多臂老虎机问题，它基于后验抽样，易于实现、健壮性好，且在批量更新场景表现更佳。
此外这是一篇学习记录，个人理解可能不够到位，任何问题欢迎留言。
