最佳臂识别

形式陈述 ​

本页在多臂赌博机公理库多臂赌博机模型Multi-armed bandit · MAB每轮选择一个臂，并且只观察该臂结果的部分反馈序贯决策模型。反馈下，把样本量与置信度公理库样本复杂度、精度与置信度Sample complexity · Accuracy and confidence用 m(ε,δ) 描述达到风险精度与失败概率所需的数据量。而非累计奖励作为主要资源—精度接口。

累计随机遗憾公理库随机赌博机与伪遗憾Stochastic bandit · Pseudo-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 方法，两类问题的最优分配可能不同。

直觉

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

例子与边界

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

fixed-confidence 与 fixed-budget 的输入和输出量词不同：前者先给失败概率并让停止时间随机，后者先给轮数并最小化错误概率。截断或重复可以给出转换，却不保证保留最优分配常数。

推论与应用

successive elimination 用同时有效的置信区间快速淘汰大 gap 臂；更精细的方法学习最优采样比例，并与 change-of-measure 下界匹配。gap 决定哪些臂必须被反复区分，而不是只决定即时遗憾。

A/B 测试、候选模型筛选和实验设计可直接使用 fixed-confidence 目标。若部署期间奖励本身也重要，应改用带 regret 约束的识别协议，不能把纯探索成本隐藏掉。

参考资料

• 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.