随机赌博机下界

形式陈述 ​

Lai–Robbins 型陈述 ​

固定允许的单臂奖励分布族 $\mathcal{P}$，其中各分布可积。考虑以累计随机赌博机遗憾理路随机赌博机与伪遗憾Stochastic bandit · Pseudo-regret每个臂从固定分布独立取样时，以均值差和选择次数表达期望损失。为目标的 $K\ge 2$ 臂乘积模型 ${\mathcal{P}}^K$：各臂有独立 IID 奖励流。当前实例 $\nu =({\nu }_1,\dots ,{\nu }_K)$ 有唯一最佳臂，均值为 ${\mu }^{\ast }=\underset{i}{max}{\mu }_i$，次优差距 ${\mathrm{\Delta }}_i={\mu }^{\ast }-{\mu }_i>0$。记 $N_i(T)$ 为前 $T$ 轮拉取臂 $i$ 的次数；本页 KL 与所有对数使用自然对数。

称策略在该族上 uniformly good，若对族中每个唯一最佳臂环境与任意 $a>0$，其累计伪遗憾 ${\overline{\mathrm{Reg}}}_T(\nu )$ 都是 $o(T^a)$。定义

这里的KL 散度理路KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。只在允许的族内取下确界。在 $0<K_{inf}({\nu }_i,{\mu }^{\ast })<\mathrm{\infty }$ 时，

若没有替代分布，约定下确界为 $+\mathrm{\infty }$，该臂不提供正的对数下界。不能悄悄扩大到任意奖励律：若允许以极小概率混入任意大的奖励，均值可提高而 KL 趋于零。若所有次优臂的信息率均在上述正有限范围内，则

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

换测度证明链 ​

固定次优臂 $i$，选取 ${\nu }_i^{\prime }\in \mathcal{P}$，其均值超过原 ${\mu }^{\ast }$ 且 $0<\mathrm{KL}({\nu }_i\Vert {\nu }_i^{\prime })<\mathrm{\infty }$；只改变这一臂得到允许的替代环境 ${\nu }^{\prime }$。策略与观测共同生成的前 $T$ 轮历史分布记为 ${\mathbb{P}}_{\nu }^T$ 与 ${\mathbb{P}}_{{\nu }^{\prime }}^T$。链式法则给出

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

取 $A_T=\{N_i(T)\le T/2\}$，并固定任意 $0<a<1$。在原环境中，uniform goodness 与该臂的正 gap 给出 ${\mathbb{E}}_{\nu }{N}_i(T)=o(T^a)$，故 ${\mathbb{P}}_{\nu }(A_T^c)=o(T^{a-1})$。在替代环境中，臂 $i$ 唯一最优，其余臂均有正 gap；同理 ${\mathbb{E}}_{{\nu }^{\prime }}[T-N_i(T)]=o(T^a)$，故 ${\mathbb{P}}_{{\nu }^{\prime }}(A_T)=o(T^{a-1})$。记两环境下 $A_T$ 的概率为 $p_T,q_T$。由数据处理不等式理路数据处理不等式Data processing inequality对 Markov 链 X→Y→Z，有 I(X;Z)≤I(X;Y)。，把历史压成 ${\mathbf{1}}_{A_T}$ 后

因为 $p_T\to 1$，右侧除以 $\log T$ 的下极限至少为 $1-a$。令 $a\downarrow 0$，再对所有允许且 KL 有限的替代分布取下确界，便得到系数为 $1$ 的结论。