最佳臂识别 | Codeboy's Blog

形式陈述

本页使用随机赌博机的固定均值环境与逐次选臂反馈，评价识别错误和所需样本数。先固定允许的奖励模型族 $\mathcal M$ ；每个实例有有限整数 $K\ge2$ 个臂，各臂奖励来自固定的可积概率律，最佳均值唯一。分布的有界性或尾部条件是 $\mathcal M$ 的一部分。

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

Fixed-confidence 形式

设唯一最佳臂 $i^*=\arg\max_i\mu_i$ ，输入 $0<\delta<1$ 。算法包含自适应拉臂规则、相对于可观测历史过滤的停止时间 $\tau$ 和由停止历史决定的输出 $\widehat i$ 。若对 $\mathcal M$ 中每个实例都几乎必然有限停止，且

\Pr(\widehat i=i^*)\ge1-\delta,

就称算法是 $\delta$ -correct；目标是最小化 $\mathbb E\tau$ 或给出其高概率界。典型复杂度依赖 gaps $\Delta_i=\mu^*-\mu_i$ 。在有界或共同次高斯尺度的常见模型中，其主要 gap 与置信度依赖常写成

\sum_{i\ne i^*}\Delta_i^{-2}\log(1/\delta),

还可能有额外对数项；最优常数取决于跨臂信息分配。仅假设奖励可积时，不能直接使用这个平方 gap 量级。

Fixed-budget 形式

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

直觉

算法为每个存活臂维护置信区间。当某臂的上置信界低于另一臂的下置信界时，便永久淘汰它；难分的近均值臂获得更多样本，明显较差的臂很快退出。证明需要置信事件对所有自适应轮次同时有效，不能在随机停止时刻只套一个固定时间 Hoeffding 界。置信序列提供逐臂的全时间覆盖；再用并集界，给各臂分配总和不超过 $\delta$ 的错误预算，才能保证所有区间在停止时仍共同有效。

例子与边界

UCB1为低累计 regret 设计，可能仍把大量样本用于当期收益，而不是实现最优识别比例。纯探索算法反过来可能反复拉明显次优但尚需排除的臂，承担较大即时 regret。多臂并列最优、容许 $\varepsilon$ -最佳臂或重尾奖励都需要修改正确性事件。

例如当前三个臂的区间为 $A:[0.62,0.70]$ 、 $B:[0.41,0.55]$ 、 $C:[0.59,0.67]$ 。因为 $B$ 的上界 $0.55$ 低于 $A$ 的下界 $0.62$ ，可以淘汰 $B$ ； $A$ 与 $C$ 的区间仍重叠，尚不能停止。继续采样后若得到 $A:[0.64,0.67]$ 、 $C:[0.59,0.62]$ ，则 $A$ 的下界严格超过 $C$ 的上界，才可停止并选择 $A$ 。这两次判断依赖同一个对所有臂、所有时间同时覆盖的事件；分别在两个选定时刻构造固定时间区间，不能自动提供这项自适应保证。

推论与应用

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é, and Aurélien Garivier, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models, JMLR 17(1), 2016, pp. 1–42；Lemma 1 与 Appendix A.1：停止历史的 change-of-measure 不等式及其证明。

形式陈述 ​

Fixed-confidence 形式 ​

Fixed-budget 形式 ​

反向链接

形式陈述

Fixed-confidence 形式

Fixed-budget 形式