在线遗憾下界

形式陈述 ​

全参数范围的结论 ​

考虑全信息专家协议理路专家建议预测Prediction with expert advice在全信息反馈下组合多个专家，并与事后最好的固定专家比较。，$N\ge 2$、$T\ge 1$ 为整数，每轮损失向量 ${\ell }_t\in [0,1{]}^N$。学习器先选分布 $p_t$，再见本轮损失，承担 $⟨p_t,{\ell }_t⟩$。相对最佳固定专家的遗憾为

对每个可能随机化的因果学习器，都存在一个预先固定的损失序列，使

其中 $c>0$ 为普适常数，例如可取 $c=1/8$，期望只对学习器的随机性取得。$\ln N$ 与 $T$ 同阶或更大时，下界饱和在线性尺度，不能把平方根式外推到超过平凡上限 $T$。

用专家编码各块的事后选择 ​

令

于是 $d,h\ge 1$，且 $h\ge T/(2d)$。先取 $2^d$ 位专家，以符号向量 $a\in \{-1,+1{\}}^d$ 编号；若还不足 $N$ 位，就复制已有专家。把前 $dh$ 轮分成 $d$ 块，每块 $h$ 轮。

每轮独立抽取公平符号 $r_t\in \{-1,+1\}$。在第 $j$ 块，专家 $a$ 的损失设为

剩下的 $T-dh$ 轮，所有专家损失都为 $1/2$。这是一份可以在学习开始前抽好的 oblivious 损失表；同一块内专家的损失相关，但各轮的新符号独立于过去与学习器随机种子。

条件于学习器种子和全部过去，本轮每位专家的期望损失都是 $1/2$，所以任何学习器都有 $\mathbb{E}{L}_A=T/2$。另一方面，令 $S_j$ 为第 $j$ 块的符号和。事后最优专家可对每个坐标选择 $a_j$ 与 $S_j$ 同号，得到

因此

其中 $S_h$ 是 $h$ 个独立公平符号的和。

用二阶与四阶矩给出数值界 ​

展开并利用独立性与零均值，得到

对 $|S_h{|}^2=|S_h{|}^{2/3}|S_h{|}^{4/3}$ 使用指数 $3/2$ 与 $3$ 的Hölder 不等式理路Hölder 不等式Hölder's inequality共轭指数下函数乘积的 L¹ 范数由各自的 Lᵖ 范数乘积控制。：

整理即得 $\mathbb{E}|S_h|\ge \sqrt{h/3}$，从而

由于 $d\ge \frac{1}{2}min\{T,\ln N\}$，这至少为 $min\{T,\sqrt{T\ln N}\}/\sqrt{48}$，因而形式陈述中的 $c=1/8$ 可用。

从随机构造得到固定坏序列 ​

上面的期望同时平均损失表与学习器种子。先对种子取期望，再对有限种符号表取平均，便由概率方法理路概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。得到：至少有一份固定表，使该学习器的期望遗憾达到同一下界。这一直接平均论证已经涵盖随机化学习器，不需要另外调用 minimax 定理。

量词是“对每个算法存在一份坏表”；不表示同一份表同时击败全部算法，也不表示每次随机抽表都达到该下界。