随机赌博机与伪遗憾

固定均值环境 ​

臂 $i$ 每次拉取都独立产生 ${\nu }_i$ 的奖励，均值 ${\mu }_i$ 固定。令 ${\mu }^{\ast }=\underset{i}{max}{\mu }_i$、${\mathrm{\Delta }}_i={\mu }^{\ast }-{\mu }_i$，$N_i(T)$ 为臂 $i$ 被选次数。伪遗憾为

$${\overline{R}}_T=T{\mu }^{\ast }-\mathbb{E}\sum _{t=1}^T{X}_{t,I_t}=\sum _i{\mathrm{\Delta }}_i\mathbb{E}[N_i(T)].$$

第二个等号由条件期望与 $\sum _i{N}_i(T)=T$ 得到，清楚地说明遗憾来自抽取次优臂。

Bernoulli 臂是具体实例：一次点击为 1，否则为 0，但定义允许一般有界或次高斯奖励。若多个臂并列最优，它们的 gap 为零，抽取它们不产生伪遗憾。

伪遗憾先对奖励和策略随机性取期望，不等同于某次路径上“最优臂实际总奖励减算法奖励”的 realized regret。奖励均值漂移、依赖历史或由对手挑选时，固定 ${\mu }_i$ 与 gap 分解失效，应换模型而非继续套 UCB 分析。

设 Bernoulli 臂均值为 $(0.6,0.5,0.2)$，则 gaps 为 $(0,0.1,0.4)$。若到 $T$ 时三个臂期望选择次数为 $(700,250,50)$，伪遗憾就是

$$0\cdot 700+0.1\cdot 250+0.4\cdot 50=45.$$

同样一次探索放在第三臂比第二臂贵四倍，这也是 gap-dependent 分析关心每个次优臂被拉多少次的原因。

最优臂某次实现奖励较低，不会让其均值身份改变；realized regret 甚至可能短期为负。Gap-free 界在 gaps 很小或未知时给统一最坏保证，gap-dependent 界则能描述易区分实例上的对数选择次数，两者回答不同问题。

UCB 类分析对次优臂 $i$ 的典型结论是 $\mathbb{E}{N}_i(T)=O(\log T/{\mathrm{\Delta }}_i^2)$，乘上单次代价 ${\mathrm{\Delta }}_i$ 后贡献 $O(\log T/{\mathrm{\Delta }}_i)$ 遗憾。Gap 越小越难统计区分，但每次选错也越便宜；最终公式正是两种效应的平衡。

随机模型仍需指定尾部。只有均值存在的重尾奖励不自动拥有 Hoeffding 置信半径；有界、次高斯或已知方差条件会导向不同算法。各臂内部 IID 也不表示不同臂的潜在奖励必须在同一轮独立，因为策略从未同时观察它们；真正需要的是对被抽取序列的条件分布假设。

参考资料

• Lai, Robbins, “Asymptotically Efficient Adaptive Allocation Rules,” 1985.
• Auer, Cesa-Bianchi, Fischer, “Finite-time Analysis of the Multiarmed Bandit Problem,” 2002.