遗憾与比较器类

外部遗憾 ​

对动作 $a_t$ 和固定比较器集合 $\mathcal{U}$，外部遗憾为

$${\mathrm{Reg}}_T=\sum _{t=1}^T{\ell }_t(a_t)-\underset{u\in \mathcal{U}}{inf}\sum _{t=1}^T{\ell }_t(u).$$

比较器是回看完整序列后挑出的最好固定动作，但算法必须逐轮因果行动。No-regret 指 ${\mathrm{Reg}}_T=o(T)$，即平均每轮差距趋零；累计损失本身不必趋零。

若算法随机，可讨论实现值、期望遗憾或高概率遗憾。随机 bandit 的伪遗憾先对奖励取期望再与均值最优臂比较，与单条样本路径遗憾并非恒等。动态遗憾允许比较器随时间变化，若不限制变化总量，逐轮 oracle 可使任何算法显得线性差。

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

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

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

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

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

参考资料

• Cesa-Bianchi, Lugosi, Prediction, Learning, and Games, 2006.
• Bubeck, Cesa-Bianchi, “Regret Analysis of Stochastic and Nonstochastic Bandits,” 2012.