固定置信最佳臂下界

固定置信目标 ​

固定 $0<\delta <1/2$。考虑 $K$ 臂随机赌博机实例 $\nu =({\nu }_1,\dots ,{\nu }_K)$，各臂均值为 ${\mu }_i$，并假设最佳臂

$$a^{\ast }(\nu )=\arg \underset{i}{max}{\mu }_i$$

唯一。算法自适应拉臂，在停时 $\tau$ 停止并输出 $\hat{a}$。若对模型类中每个唯一最佳臂实例都满足

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

则称为 $\delta$-correct。

目标是最小化 ${\mathbb{E}}_{\nu }\tau$，而非探索期间的累计遗憾。一个识别算法可以大量拉取明显次优但信息关键的臂，只要它更快达到可靠结论；这在累计奖励目标下可能并不合理。

change-of-measure 基本不等式 ​

取另一个实例 ${\nu }^{\prime }=({\nu }_1^{\prime },\dots ,{\nu }_K^{\prime })$，要求其最佳臂与 $\nu$ 不同。记 $N_i(\tau )$ 为停止前拉取臂 $i$ 的次数。在适当绝对连续和可积条件下，任意由停止历史决定的事件 $E$ 满足

$$\sum _{i=1}^K{\mathbb{E}}_{\nu }[N_i(\tau )]\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime })\ge \mathrm{kl}({\text{Pr}}_{\nu }(E)\Vert {\text{Pr}}_{{\nu }^{\prime }}(E)).$$

左侧是算法在真实例下积累的期望对数似然证据；右侧是若要让事件概率在两个世界中显著不同，至少需要的 Bernoulli 检验信息。

令 $E=\{\hat{a}=a^{\ast }(\nu )\}$。$\delta$-correct 性给出

$${\text{Pr}}_{\nu }(E)\ge 1-\delta ,{\text{Pr}}_{{\nu }^{\prime }}(E)\le \delta ,$$

故

$$\sum _i{\mathbb{E}}_{\nu }[N_i(\tau )]\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime })\ge \mathrm{kl}(1-\delta \Vert \delta )\asymp \log \left(1/\delta \right).$$

这对每个会改变最佳臂的替代实例 ${\nu }^{\prime }$ 都必须成立。

特征复杂度 ​

把期望抽样比例写成

$$w_i=\frac{{\mathbb{E}}_{\nu }{N}_i(\tau )}{{\mathbb{E}}_{\nu }\tau },w\in {\mathrm{\Delta }}_K.$$

定义替代集合

$$\mathrm{Alt}(\nu )=\{{\nu }^{\prime }:a^{\ast }({\nu }^{\prime })\ne a^{\ast }(\nu )\}.$$

理想信息率为

$$T^{\ast }(\nu {)}^{-1}=\underset{w\in {\mathrm{\Delta }}_K}{sup}\underset{{\nu }^{\prime }\in \mathrm{Alt}(\nu )}{inf}\sum _{i=1}^K{w}_i\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime }).$$

于是任何 $\delta$-correct 算法满足形如

$${\mathbb{E}}_{\nu }\tau \ge T^{\ast }(\nu )\mathrm{kl}(1-\delta \Vert \delta )$$

的下界。$T^{\ast }(\nu )$ 不是简单的 $\sum _i{\mathrm{\Delta }}_i^{-2}$；它是学习器的抽样分配与最难替代实例之间的极小极大问题，描述应该把证据投向哪些臂。

两臂 Bernoulli 图像 ​

若 ${\mu }_1>{\mu }_2$，替代世界可以稍微降低臂 1、提高臂 2，直到两者顺序翻转。只拉臂 1 无法排除“臂 2 实际略高”的世界，只拉臂 2 也无法排除“臂 1 比观察值更低”的世界；最优比例平衡两个方向的 KL 证据。

当 gap $\mathrm{\Delta }={\mu }_1-{\mu }_2$ 很小时，Bernoulli KL 的局部二次近似使 $T^{\ast }(\nu )$ 按 ${\mathrm{\Delta }}^{-2}$ 增长。于是把错误概率从常数降到 $\delta$ 还要乘 $\log \left(1/\delta \right)$。小 gap 昂贵并非 Hoeffding 上界的偶然产物，而是任何正确算法都面对的检验困难。

证明中的量词 ​

下界要求算法在整个实例类上 $\delta$-correct。若算法只需在一个已知固定实例上正确，它可以直接硬编码最佳臂而无需采样。替代实例正是通过 uniform correctness 排除这种捷径。

KL 方向为 $\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime })$，因为期望抽样次数在真实例 $\nu$ 下计算。交换方向会改变信息率。若两个分布不绝对连续，KL 可为无穷，表示某次观察可能立即排除替代世界；此时必须按扩展实数正确解释，而非把无穷裁成大常数。

与累计遗憾下界的边界 ​

Lai–Robbins 累计遗憾下界也用 change-of-measure，却要求长期高奖励策略对每个次优臂积累足够证据，得到约 $(\log T)/\mathrm{KL}({\nu }_i\Vert {\nu }_{\ast })$ 的拉取数。固定置信识别下界围绕错误概率 $\delta$ 与停止时间，并允许全局优化抽样比例。两者的替代集合和目标函数不同，不能把 $T$ 换成 $1/\delta$ 就互相推出。

参考资料

• Shie Mannor and John Tsitsiklis, “The Sample Complexity of Exploration in the Multi-Armed Bandit Problem,” JMLR, 2004.
• Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier, “On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models,” JMLR, 2016.
• Aurélien Garivier and Emilie Kaufmann, “Optimal Best Arm Identification with Fixed Confidence,” COLT, 2016.