遗憾与比较器类

遗憾把整段序列压成一场赛后对账：算法必须在信息逐轮到达时行动，比较器却可以看完整段序列后从预先声明的集合中挑最好者。这个“事后挑、但只能在固定集合里挑”的不对称既让基准有解释力，又避免它强到每轮都预知答案。

遗憾是加性差，不是近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。或竞争比；“$O(\sqrt{T})$”也只有在动作集、反馈模型、损失范围与比较器明确时才完整。错误数可视为 0–1 损失累计值，但 mistake bound 在可实现序列上与零错误比较器比较，是更强的专门模型。

No-regret 的含义是平均差距消失，而不是累计损失趋零，也不是最后一次动作收敛。算法完全可能和一个很差的最好比较器一起承受巨大绝对损失；它保证的是没有长期落后于这个参照类，而不是保证环境本身容易预测。

固定专家与动态 oracle ​

设两位专家在十轮中的累计损失分别为 3 和 7，算法累计损失为 4，则相对最好固定专家的遗憾为 $4-3=1$，不是错误数 4，也不是相对每轮事后最好建议的差。若每轮轮流有一位专家零损失，动态 oracle 可累计为零，而任何固定专家约损失五次；换比较器会彻底改变问题难度。

bandit 中的两层期望 ​

随机 bandit 中还有两层期望。伪遗憾用臂的均值比较，期望 realized regret 则把同一奖励表上事后最好臂作为随机基准；有限时域下二者可不同。写“expected regret”时应明确期望对算法、奖励和可能的随机对手分别取在哪里。

负遗憾与更强比较器 ​

遗憾还可能为负：算法能随历史切换，某条序列上可能胜过事后最好固定动作。No-regret 要求的是上界而非非负性。若想保证对每个区间或每个切换次数受限的比较器都好，需要 strongly adaptive 或 shifting regret，并为比较器的额外自由支付复杂度。

从总遗憾到平均表现只需除以 $T$：$O(\sqrt{T})/T=O(1/\sqrt{T})\to 0$。但这不意味着最后一轮动作收敛，也不保证单轮损失下降；在线到批转换通常要平均迭代点或随机抽取一轮，并另外使用凸性或随机顺序假设。

当 $\mathcal{U}$ 是有限专家集合时，定义直接导向专家建议预测公理库专家建议预测Prediction with expert advice在全信息反馈下组合多个专家，并与事后最好的固定专家比较。：指数权重用 $O(\sqrt{T\log |\mathcal{U}|})$ 的代价同时追踪所有固定专家。若 $\mathcal{U}$ 是凸集，在线凸优化公理库在线凸优化Online convex optimization · OCO每轮先在凸域选点、再承受未知凸损失，并与最好固定点比较。把同一比较式与梯度几何结合；若允许有限次切换，则需把切换位置与次数的复杂度加入界中。

遗憾界还可通过在线到批转换产生随机样本下的风险保证。转换不是字面上把 $T$ 改成样本量：必须说明数据次序、损失凸性以及输出采用平均迭代点还是随机一轮，才能把因果序列上的平均比较转成总体期望风险。