形式陈述
Lai–Robbins 型陈述
考虑以累计随机赌博机遗憾 公理库 随机赌博机与伪遗憾 Stochastic bandit · Pseudo-regret 每个臂从固定分布独立取样时，以均值差和选择次数表达期望损失。 K i ν i μ i μ ∗ = max i μ i Δ i = μ ∗ − μ i > 0 N i ( T ) T i
称策略在一个模型族上 uniformly good ，若对族中每个环境与任意 a > 0 o ( T a ) KL 散度 公理库 KL 散度 Kullback–Leibler divergence · Relative entropy 同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。 i
lim inf T → ∞ E ν N i ( T ) log T ≥ 1 K inf ( ν i , μ ∗ ) , 其中
K inf ( ν i , μ ∗ ) = inf { KL ( ν i ‖ ν ′ ) : E ν ′ X > μ ∗ } . 因此伪遗憾满足
lim inf T → ∞ E ν Regret T log T ≥ ∑ i : Δ i > 0 Δ i K inf ( ν i , μ ∗ ) . 这是渐近、分布依赖下界。lim inf T log T
换测度证明链
固定次优臂 i ν ′ i μ ∗ ν i ′ T P ν T P ν ′ T
KL ( P ν T ‖ P ν ′ T ) = E ν N i ( T ) KL ( ν i ‖ ν i ′ ) . 动作选择本身不额外贡献 KL，因为给定相同历史，策略使用相同的随机核；只有真的观察臂 i
取事件 A T i A T A T 数据处理不等式 公理库 数据处理不等式 Data processing inequality 对 Markov 链 X→Y→Z，有 I(X;Z)≤I(X;Y)。 1 A T
E ν N i ( T ) KL ( ν i ‖ ν i ′ ) ≥ kl ( P ν ( A T ) ‖ P ν ′ ( A T ) ) ≳ log T . 再对所有能让臂 i ν i ′
直觉 次优臂在当前环境里看似不值得拉，却可能在一个只改变该臂的邻近环境中成为最优。策略若几乎不观察它，两种环境产生的历史就过于相似；同一行动规则无法在当前世界少拉它、又在替代世界多拉它。
每拉一次臂 i KL ( ν i ‖ ν i ′ ) log T log T
例子与边界 Bernoulli 两臂实例
设两臂分别为 Ber ( 0.6 ) Ber ( 0.5 ) 0.6 q ↓ 0.6
K inf = kl ( 0.5 ‖ 0.6 ) = 1 2 log 0.5 0.6 + 1 2 log 0.5 0.4 ≈ 0.0204 . 任何 uniformly good 策略渐近至少拉取第二臂约 49 log T 4.9 log T 0.1
边界与相邻下界
uniform goodness 排除了“永远只拉第一臂”这类在当前环境遗憾为零、换一个环境却线性失败的策略。没有跨环境的一致性要求，就不能强迫策略探索。
当 gap 随 T Ω ( K T ) Packing–Fano 公理库 Packing–Fano 学习下界 Packing-Fano method · Fano method for minimax lower bounds 将参数空间离散成大量两两分离却统计上难以区分的候选，再由 Fano 不等式导出维数敏感的极小极大下界。
推论与应用 把每个次优臂的拉取下界乘以 gap 并求和，就得到 Lai–Robbins 的实例依赖遗憾常数。KL-UCB、Thompson Sampling 等渐近有效算法的目标，正是让各臂探索次数逼近这份辨识预算，而不是只达到粗略的 O ( ( log T ) / Δ i 2 )
Uniform goodness 是强制探索的关键量词：它要求策略在整个模型族上都次多项式遗憾。若只评价一个固定环境，永远拉当前最优臂的神谕策略当然无需探索；下界通过相邻环境排除了这种预知答案的策略。
参考资料
Tze Leung Lai and Herbert Robbins, “Asymptotically Efficient Adaptive Allocation Rules,” Advances in Applied Mathematics 6(1), 1985, pp. 4–22.
Apostolos N. Burnetas and Michael N. Katehakis, “Optimal Adaptive Policies for Sequential Allocation Problems,” Advances in Applied Mathematics 17(2), 1996, pp. 122–142.
Sébastien Bubeck and Nicolò Cesa-Bianchi, “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems,” Foundations and Trends in Machine Learning 5(1), 2012, pp. 1–122.
