NIPS 2011 的一篇论文（“Thompson Sampling 的实证评估”）在实验中表明，Thompson Sampling 击败了 UCB。UCB 基于在乐观假设下选择承诺最高回报的杠杆（即，您对预期回报的估计方差很大，因此您拉动了您不太了解的杠杆）。相反，Thompson Sampling 是完全贝叶斯的：它从后验分布生成一个老虎机配置（即预期奖励的向量），然后就好像这是真实的配置一样行事（即它拉动了具有最高预期奖励的杠杆）。

贝叶斯控制规则（“ A Minimum Relative Entropy Principle for Learning and Acting ”，JAIR）是 Thompson Sampling 的推广，从信息论原则和因果关系中推导出 Thompson Sampling。特别是，当您希望最小化策略和（未知）最优策略之间的 KL 并且考虑因果约束时，贝叶斯控制规则是最优策略。这很重要的原因是因为这可以被视为贝叶斯推理对动作的扩展：当您的性能标准是估计器和（未知）真实分布之间的 KL 时，贝叶斯推理可以被证明是最佳预测策略。

UCB 在随机情况下确实接近最优（对于 T 轮游戏高达 log T 因子），并且在更依赖问题的意义上达到 Pinsker 不等式的差距。Audibert 和 Bubeck最近的论文在最坏的情况下消除了这种对数依赖性，但在有利的情况下，当不同的手臂具有良好分离的奖励时，它的界限更差。

一般来说，UCB 是一个更大的算法家族中的一个候选者。在游戏中的任何时候，您都可以查看所有没有“失格”的手臂，即其置信上限不小于某个手臂的置信下限。基于此类合格武器的任何分布的选择构成了一种有效的策略，并且会在常数范围内获得类似的遗憾。

根据经验，我不认为对许多不同的策略进行了重要的评估，但我认为 UCB 通常非常好。

大多数最近的研究都集中在将老虎机问题扩展到具有随机奖励的简单 K 臂设置之外，扩展到非常大（或无限）的动作空间，有或没有辅助信息，以及在随机或对抗性反馈下。在性能标准不同的情况下也有工作（例如仅识别最佳手臂）。

当前的技术状态可以这样总结：

• 随机：UCB 和变体（遗憾）$R_T = O(\frac{K \log T}{\Delta})$
• 对抗性：EXP3 和变体（遗憾）$\tilde{R}_T = O(\sqrt{T K \log K})$
• 上下文：这很复杂

其中是轮数，是臂数，是最佳臂和次佳臂（间隙）之间的真实差异。$T$$K$$\Delta$