最佳臂识别

目标为何不同 ​

累计 regret 要求探索期间也尽量拿到高奖励；最佳臂识别只评价最后交出的臂是否正确以及用了多少样本。A/B 测试是典型场景：试验阶段可以有意多采不确定版本，只要最终选择有明确置信保证。两种目标都使用 bandit 数据，却不能用同一个 regret 指标互相代替。

Fixed-confidence 形式 ​

设唯一最佳臂 $i^{\ast }=\arg \underset{i}{max}{\mu }_i$，算法包含自适应拉臂规则、随机停止时间 $\tau$ 和输出 $\hat{i}$。若对允许的所有实例都有

$$\text{Pr}(\hat{i}=i^{\ast })\ge 1-\delta ,$$

就称算法是 $\delta$-correct；目标是最小化 $\mathbb{E}\tau$ 或给出其高概率界。典型复杂度依赖 gaps ${\mathrm{\Delta }}_i={\mu }^{\ast }-{\mu }_i$，粗略量级为

$$\sum _{i\ne i^{\ast }}{\mathrm{\Delta }}_i^{-2}\log \left(1/\delta \right),$$

但最优常数还取决于跨臂信息分配，不能把该量级当作所有模型的精确答案。

Fixed-budget 形式 ​

给定总预算 $T$，算法必须在 $T$ 次拉臂后输出 $\hat{i}$，评价误判概率 $\text{Pr}(\hat{i}\ne i^{\ast })$ 的衰减。这里不输入 $\delta$，也没有随机停止时间。一个 fixed-confidence 停止规则截到 $T$ 并不自动成为最优 fixed-budget 方法，两类问题的最优分配可能不同。

Successive elimination 图像 ​

算法为每个存活臂维护置信区间。当某臂的上置信界低于另一臂的下置信界时，便永久淘汰它；难分的近均值臂获得更多样本，明显较差的臂很快退出。证明需要置信事件对所有自适应轮次同时有效，不能在随机停止时刻只套一个固定时间 Hoeffding 界。

边界与辨析 ​

UCB1公理库UCB 算法UCB1 · upper confidence bound algorithm在有界随机多臂赌博机中选择经验均值加置信半径最大的手臂。为低累计 regret 设计，可能仍把大量样本用于当期收益，而不是实现最优识别比例。纯探索算法反过来可能反复拉明显次优但尚需排除的臂，承担较大即时 regret。多臂并列最优、容许 $\epsilon$-最佳臂或重尾奖励都需要修改正确性事件。

参考资料

• Eyal Even-Dar, Shie Mannor, Yishay Mansour, Action Elimination and Stopping Conditions for the Multi-Armed Bandit, JMLR, 2006.
• Emilie Kaufmann, Olivier Cappé, Aurélien Garivier, On the Complexity of Best-Arm Identification, JMLR, 2016.