随机赌博机与伪遗憾

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

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

三臂数值账本 ​

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

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

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

最优臂某次实现奖励较低，不会让其均值身份改变；realized regret 甚至可能短期为负。均值漂移、依赖历史或由对手挑选奖励时，固定 ${\mu }_i$ 与 gap 分解失效，应切换模型，而不是继续套随机 bandit 的结论。

算法选择对应不同的统计接口。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在模型族最坏参数上评价算法风险，再在所有允许算法中寻找最优值。分析改为给所有实例统一的最坏保证。两种尺度回答的问题不同：前者解释给定实例为何容易，后者校准没有额外间隔信息时能承诺到什么程度。