随机赌博机与伪遗憾

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

伪遗憾先对奖励和策略随机性取期望理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。，不等同于某次路径上“最优臂实际总奖励减算法奖励”的 realized regret。 与最佳臂识别理路最佳臂识别best-arm identification以可靠选出最高均值臂为目标，研究纯探索的停止规则与样本复杂度。相比，本页评价整个交互过程的累计机会损失，而后者主要评价最终推荐与样本复杂度；两者共享反馈模型，却优化不同目标。奖励的条件均值若漂移或随历史改变，固定 ${\mu }_i$ 的 gap 分解便不再适用，应切换到对抗 bandit 模型理路对抗赌博机模型Adversarial bandit损失向量可任意变化、学习器只观察所选坐标的在线决策模型。或其他明确模型，而非继续套 UCB 分析。

三臂数值账本 ​

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

从奖励账本也可交叉核对：$T=1000$，算法的期望总奖励为 $0.6\cdot 700+0.5\cdot 250+0.2\cdot 50=555$，始终选均值最优臂的期望奖励为 $600$，差仍为 $45$。这里的次数是期望次数，三者可以不是整数；一次实验恰好得到这些整数次数，也不意味着那次实际奖励必定为 $555$。同样一次探索放在第三臂比第二臂贵四倍，这也是 gap-dependent 分析关心每个次优臂被拉多少次的原因。

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

最优臂某次实现奖励较低，不会让其均值身份改变；realized regret 甚至可能短期为负。如果条件均值随历史或时间改变，就不能再使用固定 ${\mu }_i$ 的同一分解；只有分布的其他部分依赖历史、条件均值仍固定时，分解本身却可能继续成立。不能把恒等式所需的条件与集中界所需的条件混为一谈。

算法选择对应不同的统计接口。KL-UCB理路KL-UCBKL-UCB algorithm · KL 上置信界在 Bernoulli 赌博机中用二元 KL 置信集合的上端点选择臂，并获得匹配分布变化下界的渐近遗憾常数。用分布族的 KL 置信上界，在 Bernoulli 等一参数模型中获得精细的实例依赖常数；Thompson Sampling理路Thompson SamplingPosterior sampling · 汤普森采样 · 后验采样每轮从未知奖励参数的后验分布抽取一个世界并选择该世界中的最优臂，以概率匹配方式平衡探索与利用。从后验抽样行动，需要明确先验、似然和后验更新；Explore-then-Commit理路Explore-then-CommitExplore then commit · 先探索后利用 · ETC先以固定预算均匀估计各臂均值，再永久选择经验最优臂的随机赌博机基线及其 gap-dependent 遗憾。先固定或调谐探索期，再长期选择经验最佳臂，结构简单但对 horizon 与 gap 设定敏感。三者实现同一伪遗憾目标，不共享同一先验需求、调参方式或有限时间证明。

Gap-dependent 分析能描述易区分实例上的对数选择次数：UCB 算法理路UCB 算法UCB1 · upper confidence bound algorithm在有界随机多臂赌博机中选择经验均值加置信半径最大的手臂。对次优臂 $i$ 的典型结论是 $\mathbb{E}{N}_i(T)=O(\log T/{\mathrm{\Delta }}_i^2)$，乘上单次代价 ${\mathrm{\Delta }}_i$ 后贡献 $O(\log T/{\mathrm{\Delta }}_i)$ 遗憾。Gap 越小越难统计区分，但每次选错也越便宜。

当 gaps 很小或未知时，这类界会变得松散，gap-free 或极小极大理路极小极大风险Minimax risk在模型族最坏参数上评价算法风险，再在所有允许算法中寻找最优值。分析改为给所有实例统一的最坏保证。两种尺度回答的问题不同：前者解释给定实例为何容易，后者校准没有额外间隔信息时能承诺到什么程度。