在线遗憾下界

结论 ​

考虑 $N\ge 2$ 个专家、$T$ 轮完整信息预测。每轮学习器选择分布 $p_t\in {\mathrm{\Delta }}_N$，随后观察损失向量 ${\ell }_t\in [0,1{]}^N$，并承担 $⟨p_t,{\ell }_t⟩$。相对最佳固定专家的遗憾为

$$R_T=\sum _{t=1}^T⟨p_t,{\ell }_t⟩-\underset{i\in [N]}{min}\sum _{t=1}^T{\ell }_{t,i}.$$

存在普适常数 $c>0$，使在例如 $2\le N\le e^{T/8}$ 的常见参数区间内，对任何可能随机化的学习器，都存在一个损失序列满足

$$\mathbb{E}{R}_T\ge c\sqrt{T\log N}.$$

期望只对学习器随机性取值。与 Hedge 的 $O(\sqrt{T\log N})$ 上界对照可知，在不增加损失结构的对抗模型中，$T$ 与 $N$ 的依赖已经无法按阶改善。

若 $N$ 相对 $T$ 极大，遗憾最多为 $T$，正确的全区间尺度写成

$$\mathrm{\Omega }(min\{T,\sqrt{T\log N}\})$$

并需配合具体常数与参数限制。把平方根公式外推到 $\log N\gg T$ 会超过遗憾的平凡上限。

随机坏序列 ​

下界可由概率法构造。先不针对学习器挑确定序列，而令每位专家每轮的损失独立取 Bernoulli$(1/2)$：

$${\ell }_{t,i}\sim \mathrm{Bernoulli}(1/2).$$

当前损失与学习器根据过去选择的 $p_t$ 独立，因此

$$\mathbb{E}⟨p_t,{\ell }_t⟩=\frac{1}{2},\mathbb{E}{L}_A=\frac{T}{2}.$$

学习器无法预见哪位专家会在这一轮幸运。

每位专家的累计损失 $L_i$ 都围绕 $T/2$ 波动，标准差为 $\mathrm{\Theta }(\sqrt{T})$。在 $N$ 个独立副本中取最小值，会得到约

$$\mathbb{E}\underset{i}{min}{L}_i\le \frac{T}{2}-c\sqrt{T\log N}.$$

学习器仍付出 $T/2$，事后最佳专家却因极值效应显得持续优秀，两者之差正是所需遗憾。严格证明可用二项分布反尾界、Sudakov 型估计，或构造带小偏置的隐藏最佳专家并做信息论检验。

从随机分布到确定序列 ​

上面证明在随机损失分布下，任意确定学习器的平均遗憾很大。Yao minimax 原理把它转成：对任意随机化学习器，存在某个确定损失序列使其期望遗憾同样大。即使不显式引用完整 minimax 定理，平均值论证也说明随机分布支持中至少有一个序列不低于平均坏度。

这个转换只给“每个算法存在一个坏序列”，不表示从随机样本抽到的每条序列都坏，也不表示同一条万能序列同时击败所有算法。量词顺序是下界的一部分。

为什么最佳专家不是预测信号 ​

在构造中，获胜专家是事后由累计随机波动选出来的。它并没有每轮更低的条件期望，学习器也没有可利用的先验身份。遗憾比较器允许事后选择，正因如此极值偏差成为不可避免的成本。

若环境预先声明某位专家具有固定正 gap，问题转为随机专家或 bandit 识别，可能得到对数于 $T$ 的 gap-dependent regret。那是额外分布结构带来的改善，不与本下界矛盾。

边界与不同目标 ​

下界针对外部遗憾和最佳固定专家。若比较器允许随时间切换，基准更强，下界不会变小，还会依赖切换次数或变化预算。若损失具有强凸性、可预测性或小方差，可获得数据依赖的更小上界，但最坏序列仍可回到平方根尺度。

高概率下界、期望下界与 almost-sure 陈述不是同一个命题。这里的期望下界已经足以否定统一的 $o(\sqrt{T\log N})$ 期望保证；若要证明固定概率下遗憾大，需要对随机构造的尾部再作控制。

参考资料

• Nicolò Cesa-Bianchi and Gábor Lugosi, Prediction, Learning, and Games, lower-bound chapters.
• Sébastien Bubeck and Nicolò Cesa-Bianchi, “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems,” lower-bound preliminaries.
• Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, minimax and Yao arguments.