随机赌博机下界

Lai–Robbins 型陈述 ​

考虑 $K$ 臂随机赌博机。第 $i$ 臂奖励独立来自分布 ${\nu }_i$，均值 ${\mu }_i$；唯一最优均值为 ${\mu }^{\ast }=\underset{i}{max}{\mu }_i$，次优差距 ${\mathrm{\Delta }}_i={\mu }^{\ast }-{\mu }_i>0$。记 $N_i(T)$ 为前 $T$ 轮拉取臂 $i$ 的次数。

称策略在一个模型族上 uniformly good，若对族中每个环境与任意 $a>0$，其期望遗憾都是 $o(T^a)$。在可识别且 KL 正则的单参数或一般分布族中，对每个次优臂 $i$，

$$\underset{T\to \mathrm{\infty }}{lim inf}\frac{{\mathbb{E}}_{\nu }{N}_i(T)}{\log T}\ge \frac{1}{K_{inf}({\nu }_i,{\mu }^{\ast })},$$

其中

$$K_{inf}({\nu }_i,{\mu }^{\ast })=inf\{\mathrm{KL}({\nu }_i\Vert {\nu }^{\prime }):{\mathbb{E}}_{{\nu }^{\prime }}X>{\mu }^{\ast }\}.$$

因此伪遗憾满足

$$\underset{T\to \mathrm{\infty }}{lim inf}\frac{{\mathbb{E}}_{\nu }{\mathrm{Regret}}_T}{\log T}\ge \sum _{i:{\mathrm{\Delta }}_i>0}\frac{{\mathrm{\Delta }}_i}{K_{inf}({\nu }_i,{\mu }^{\ast })}.$$

这是渐近、分布依赖下界。$lim inf$ 不能改写成“每个 $T$ 都精确大于右侧乘 $\log T$”。

为什么次优臂必须被反复拉取 ​

固定次优臂 $i$，构造替代环境 ${\nu }^{\prime }$：只把第 $i$ 臂换成均值超过原 ${\mu }^{\ast }$ 的分布 ${\nu }_i^{\prime }$，其他臂不变。策略与观测共同生成的前 $T$ 轮历史分布记为 ${\mathbb{P}}_{\nu }^T$ 与 ${\mathbb{P}}_{{\nu }^{\prime }}^T$。链式法则和自适应动作的条件可测性给出换测度恒等式

$$\mathrm{KL}({\mathbb{P}}_{\nu }^T\Vert {\mathbb{P}}_{{\nu }^{\prime }}^T)={\mathbb{E}}_{\nu }{N}_i(T)\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime }).$$

动作选择本身不额外贡献 KL，因为给定相同历史，策略使用相同的随机核；只有真的观察臂 $i$ 时，两环境才泄露区别。

取事件 $A_T$ 表示“臂 $i$ 没有被拉接近线性次数”。在原环境里它是次优臂，uniform goodness 迫使 $A_T$ 高概率发生；在替代环境里它变成最优臂，同一性质迫使 $A_T$ 的概率按多项式速度趋零。由 数据处理不等式公理库数据处理不等式Data processing inequality对 Markov 链 X→Y→Z，有 I(X;Z)≤I(X;Y)。，把整段历史压成 ${\mathbf{1}}_{A_T}$ 后

$${\mathbb{E}}_{\nu }{N}_i(T)\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime })\ge \mathrm{kl}({\mathbb{P}}_{\nu }(A_T)\Vert {\mathbb{P}}_{{\nu }^{\prime }}(A_T))\gtrsim \log T.$$

再对所有能让臂 $i$ 变成最优的 ${\nu }_i^{\prime }$ 取 KL 下确界，得到定理。下界表达的是一次信息预算：若不在次优臂上累计约 $\log T$ 份对数似然证据，策略就无法排除“它其实最好”的近邻世界。

Bernoulli 两臂实例 ​

设两臂分别为 $\mathrm{Ber}(0.6)$ 与 $\mathrm{Ber}(0.5)$。对第二臂，最接近且均值超过 $0.6$ 的 Bernoulli 替代分布在边界趋近 $q\downarrow 0.6$，故

$$K_{inf}=\mathrm{kl}(0.5\Vert 0.6)=\frac{1}{2}\log \frac{0.5}{0.6}+\frac{1}{2}\log \frac{0.5}{0.4}\approx 0.0204.$$

任何 uniformly good 策略渐近至少拉取第二臂约 $49\log T$ 次，相应遗憾系数至少约 $4.9\log T$。均值差只有 $0.1$ 并不足以决定精确常数；奖励分布的 KL 可区分度才是下界中的正确信息量。

边界与相邻下界 ​

uniform goodness 排除了“永远只拉第一臂”这类在当前环境遗憾为零、换一个环境却线性失败的策略。没有跨环境的一致性要求，就不能强迫策略探索。

当 gap 随 $T$ 变小，分布依赖的对数式可能不再描述最坏情形；有限时 minimax 下界通常是 $\mathrm{\Omega }(\sqrt{KT})$。Packing–Fano公理库Packing–Fano 学习下界Packing-Fano method · Fano method for minimax lower bounds将参数空间离散成大量两两分离却统计上难以区分的候选，再由 Fano 不等式导出维数敏感的极小极大下界。同时排列许多难环境以提取维数，本页则用单臂替代环境和序贯换测度刻画每个 gap 的渐近代价。

参考资料

• Tze Leung Lai and Herbert Robbins, “Asymptotically Efficient Adaptive Allocation Rules,” 1985.
• Apostolos Burnetas and Michael Katehakis, work on optimal adaptive policies.
• Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.