论文连接 https://arxiv.org/abs/1811.04383
本篇论文使用二分类算法，为在线场景(contextual bandits)探索了多臂赌博机(multi-armed bandits)的变种形式，主要涉及重复采样(bootstrapping)和随机算法。其中，自适应贪心算法(Adaptive-Greedy algorithm)是作者认为最好的一种方式。
对multi-armed bandits不了解的同学可以参考https://zhuanlan.zhihu.com/p/80261581，里面有很详细的解释。
一、问题描述
对于K个赌博机（每个赌博机的收益均服从Bernoulli分布），在每轮开始的时候，系统都会将一组协变量(covariates)xt作为先验知识告诉张三。经过N+1轮后，张三需要根据先验知识[前N轮每轮的协变量、每轮的选项、每轮的收益]从赌博机中选择一个收益最大的一个。
二、相关研究
对于多臂赌博机解决方案主要是upper confidence bounds 和 Thompson sampling。前者通过每个赌博机回报的最好预期进行选择，后者则通过Beta分布对每个赌博机的收益进行模拟。此外还有类似以概率P选择实际表现最优的赌博机，以概率1-P随机选择的Epsilon-Greedy。在时间有限的情况下，还存在最初随机进行选择，在最后选择实际表现最好的Explore-Then-Exploit算法。LINUCB算法对于每个赌博机使用一个线性函数估计其期望收益的上限（详见知乎专栏）
三、UCB算法
UCB算法的不足在于需要访问整个数据集。在线数据中，每次数据都是以流(stream)或者batch的形式存在。针对这个问题，一种在实际中表现较好的方式，是先对每个样本分配一个Gamma(1,1)的权重，再传入分类器。另外，也可以采用决策树或随机森林对数据进行拟合，则终端节点可认为是数据的期望上界。
四、冷启动问题
在线场景中另一个问题在于相较于协方差（比如用户点击的次数）的大小，赌博机的回报率（比如用户点入推荐商品）几乎为零。通常，我们使用合并先验（incorporating a prior）或平滑的方式解决问题。Rsmooth=(nR + a)/(n + b)。其中R是估计的回报率，a和b是平滑的常数。但如果赌博机数量提升的话,上述方案会使得每个赌博机直到都被采集相当次数之前，都处于较低的回报率。另外一种方式使通过使用Beta先验并忽略协变量，直到对于每个标签取得一定的观测数量后再重新使用协变量。
还有一种方式是通过在冷启动时，选取赌博机的一个子集，从中进行随机采样。随时间，逐步增加子集中赌博机的数量。但这种方法很难确定最优的子集数量。
五、基线比较算法
一些常用的Bandit算法可参考上文提及的知乎专栏。较新颖的方法是采用SoftmaxExplorer。通过各赌博机所占的概率比例进行选择。fi(x)的输出为0-1的概率值，因此先使用反Sigmoid转化为实数值，通过softmax重新转化为概率，从而避免输出概率过小的问题。为了让该算法长期收敛于最佳策略，每轮都会成以当前论述值，从而放大赌博机收益之间的差距。
Epsilon-Greedy算法以一定概率1-p选择当前收益最大的赌博机，以概率p从任意赌博机中随机选择一个。随着round的增加，随机选择的概率越来越低。
Epsilon-Greedy算法可以很容易改成启发式的学习方法。例如在ActiveExplorer算法中使用神经网络替换uniform采样。[上述算法可参考https://github.com/david-cortes/contextualbandits]
其中表现最好的算法是ContextualAdaptiveGreedy，这类算法运行速度也较快。但需注意再结合启发式算法的增强手段无法对此类算法有明显提升。
