固定置信最佳臂下界

形式陈述 ​

固定置信目标 ​

固定 $0<\delta <1/2$ 和允许的奖励模型族 $\mathcal{M}$；本页所有 KL 与对数均用自然对数。在最佳臂识别理路最佳臂识别best-arm identification以可靠选出最高均值臂为目标，研究纯探索的停止规则与样本复杂度。的 fixed-confidence 目标下，考虑 $K$ 臂随机赌博机实例 $\nu =({\nu }_1,\dots ,{\nu }_K)$，各臂均值为 ${\mu }_i$，并假设最佳臂

唯一。算法自适应拉臂，在相对于可观测历史的停时 $\tau$ 停止并输出由停止历史决定的 $\hat{a}$。若在 $\mathcal{M}$ 中每个唯一最佳臂实例上都几乎必然有限停止，并满足

则称为 $\delta$-correct。

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

change-of-measure 基本不等式 ​

取另一个允许的实例 ${\nu }^{\prime }\in \mathcal{M}$，要求其唯一最佳臂与 $\nu$ 不同。记 $N_i(\tau )$ 为停止前拉取臂 $i$ 的次数。先设各臂 $\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime })<\mathrm{\infty }$ 且 ${\mathbb{E}}_{\nu }\tau <\mathrm{\infty }$；这保证所需的逐步对数似然增量及停止时的累计对数似然可积。任意由停止历史决定的事件 $E$ 满足

证明先对截断停止历史使用似然比链式法则，再用数据处理不等式理路数据处理不等式Data processing inequality对 Markov 链 X→Y→Z，有 I(X;Z)≤I(X;Y)。压成事件指示变量，并对事件 $E\cap \{\tau \le m\}$ 令 $m\to \mathrm{\infty }$。两环境都几乎必然有限停止，所以事件概率收敛；一般无穷 KL 情形按扩展值使用同一截断不等式。左侧用KL 散度理路KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。度量算法在真实例下积累的期望对数似然证据；右侧是若要让事件概率在两个世界中显著不同，至少需要的 Bernoulli 检验信息。

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

故

这对每个允许且会改变最佳臂的替代实例 ${\nu }^{\prime }$ 都必须成立。且 $\mathrm{kl}(1-\delta \Vert \delta )\sim \log \left(1/\delta \right)$ 当 $\delta \downarrow 0$；这不是整个 $(0,1/2)$ 上具有统一正下常数的比较。

特征复杂度 ​

先考虑 $0<{\mathbb{E}}_{\nu }\tau <\mathrm{\infty }$，把期望抽样比例写成

定义替代集合

理想信息率为

在 $0<T^{\ast }(\nu {)}^{-1}<\mathrm{\infty }$ 时，对算法给出的 $w$ 先取替代实例下确界，其信息率再不超过上式对所有 $w$ 的上确界，故任何 $\delta$-correct 算法满足

。若 ${\mathbb{E}}_{\nu }\tau =\mathrm{\infty }$，此下界自动成立；零样本则无法在存在有限信息替代实例时满足 $\delta <1/2$ 的共同正确性。$T^{\ast }(\nu )$ 不是简单的 $\sum _i{\mathrm{\Delta }}_i^{-2}$；它是学习器的抽样分配与最难替代实例之间的极小极大问题，描述应该把证据投向哪些臂。