ICLR 2026 学习理论在线学习上下文老虎机方差相关遗憾遗憾下界剥离技术高概率下界

Variance-Dependent Regret Lower Bounds for Contextual Bandits¶

会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=zM23kMEt5q
代码: 无（纯理论）
领域: 学习理论 / 在线学习
关键词: 上下文老虎机, 方差相关遗憾, 遗憾下界, 剥离技术, 高概率下界

一句话总结¶

本文为线性上下文老虎机的「方差相关遗憾」首次证明了与上界匹配（差对数因子）的下界 $\Omega\!\big(d\sqrt{\sum_k \sigma_k^2}\big)$，覆盖任意预先给定的方差序列与自适应弱对手序列，并通过一个反例指出：一旦对手能在看到决策集之后再选方差，这类下界就不可能成立。

研究背景与动机¶

领域现状：线性上下文老虎机里，经典的极小极大遗憾是 $\tilde O(d\sqrt K)$（$d$ 是特征维度、$K$ 是轮数）。近几年大量工作转向「异方差」设定——每轮噪声方差 $\sigma_k^2$ 不同——并把遗憾改进到与方差挂钩的 $\tilde O\!\big(d\sqrt{\sum_{k=1}^K \sigma_k^2}\big)$。其中 Zhao et al. (2023) 的 SAVE 算法不需要事先知道方差，就能达到这个近最优上界（Theorem 1.1），是当前最强的上界结果。

现有痛点：方差相关的研究几乎全是「上界」，「下界」严重缺位。唯一的下界来自 Jia et al. (2024)，他们针对有限 eluder 维度的一般函数类，证明了 $\Omega(\sqrt{d_{\mathrm{elu}}\Lambda})$。但这个结果有两处硬伤：一是退化到线性情形（$d\ge\sqrt A$）后只有 $\sqrt{d\Lambda}$，比上界差了整整一个 $\sqrt d$ 因子，所以没人知道 SAVE 的 $d$ 是不是真的必要；二是它只对「固定总方差预算 $\sum_k\sigma_k^2\le\Lambda$」成立，构造方式是前若干轮用常数方差、后面全填 0，无法刻画任意的方差序列 $\{\sigma_1^2,\dots,\sigma_K^2\}$。

核心矛盾：要证下界，构造的难例必须让方差「按序列分布」而不是「攒成一个预算」，并且要让对维度 $d$ 的依赖也撑满。Jia 的固定预算构造刚好回避了这两点，因此既漏了 $\sqrt d$，又只能处理特殊序列。

本文目标：在「线性」上下文老虎机里，针对一般方差序列证出 $\tilde\Omega\!\big(d\sqrt{\sum_k\sigma_k^2}\big)$ 的下界，把 SAVE 上界钉死为最优；并厘清「方差是预先给定还是自适应生成、对手强弱」这些设定边界。

切入角度：作者注意到上下文老虎机相比随机线性老虎机的关键自由度——每轮的决策集 $D_k$ 可以变。这给了构造难例的空间：可以按方差大小把轮次分组，给不同组分配相互正交的决策集，让各组互不泄露信息，从而把整体遗憾拆成各组遗憾之和，分别打满下界再相加。

核心 idea：用「按方差量级剥离分组 + 正交子实例」把一个复杂的方差序列拆成若干个固定方差的简单子问题，每个子问题套一个 $d\sqrt{K\sigma^2}$ 的基础难例，再求和重组出 $d\sqrt{\sum_k\sigma_k^2}$。

方法详解¶

整体框架¶

本文不提算法，而是一套「构造难例 + 证下界」的技术。整体证明分三层推进。第一层是固定方差阈值 $\sigma$ 下的基础硬度引理（Lemma 4.3）：用超立方体动作集和缩放伯努利奖励造出一族难学实例，证明任何算法在 $K$ 轮内的期望遗憾至少是 $d\sqrt{K\sigma^2}/(8\sqrt6)$。第二层针对「预先给定」的一般方差序列：把 $K$ 轮按方差量级剥离成 $L=\lceil\log_2 K\rceil+1$ 组，每组内方差近似相等，给各组分配正交子空间的决策集，套用基础引理后把各组下界相加（Theorem 4.1）。第三层针对「自适应」序列：当对手逐轮生成方差、各组大小事先未知时，用「多实例 + 循环分配」补上未知组大小这一缺口，并把期望下界提升为高概率下界（Theorem 5.2）。最后给出一个反例（Theorem 5.4），说明若对手能在看到决策集后再定方差，则上述构造全部失效，下界根本不存在——以此精确地刻画出下界成立的边界条件。

下面的设计点按这条「基础硬度 → 预定序列剥离 → 自适应多实例 → 高概率提升 → 强对手反例」的脉络展开。

关键设计¶

1. 按方差量级剥离分组 + 正交子实例：把方差序列拆成可叠加的固定方差子问题

这是整套证明的地基，针对的痛点是：一般序列 $\{\sigma_k^2\}$ 里各轮方差参差不齐，没法直接套一个统一的难例。作者先固定一个方差阈值 $\sigma$，把动作集取成超立方体 $\mathcal A=\{-1,1\}^d$，奖励服从缩放伯努利 $\sigma\cdot B\!\big(1/3+\langle\mu,a\rangle\big)$，未知权重 $\mu\in\{-\Delta,\Delta\}^d$、$\Delta=1/\sqrt{96K}$。这族实例每个动作的方差被 $\sigma^2$ 控住，可等价写成特征 $(\sigma,\sigma\cdot a)$、权重 $\mu'=(1/3,\mu)$ 的线性老虎机。在此之上得到固定方差的基础下界（Lemma 4.3）：

\[\mathbb E_\mu[\mathrm{Regret}(K)] \ge \frac{d\sqrt{K\sigma^2}}{8\sqrt6},\qquad K\ge 1.5\,d^2.\]

对一般序列，把轮次按方差大小切成几何递增的组：$\mathcal K_0=\{k:\sigma_k\le 1/K\}$，$\mathcal K_i=\{k: 2^{i-1}/K<\sigma_k\le 2^i/K\}$（$i=1,\dots,L-1$）。每组 $\mathcal K_i$ 配一个维度 $d_i=d/L$、方差阈值 $\sigma(i)=2^{i-1}/K$、轮数 $|\mathcal K_i|$ 的子实例 $M_i$；把它们嵌进互相正交的子空间——某轮属于 $\mathcal K_i$ 时，决策集形如 $(0,\dots,x,\dots,0)$，只有第 $i$ 块非零。正交是关键：不同组的动作彼此提供不了任何关于其他组权重 $\mu_j$ 的信息，于是总遗憾恰好分解为各组遗憾之和，每组按 Lemma 4.3 打满，求和后得到 Theorem 4.1：

\[\mathbb E[\mathrm{Regret}(K)] \ge \Omega\!\Big(d\sqrt{\textstyle\sum_{k=1}^K \sigma_k^2 \big/ \log K}\Big),\]

与 SAVE 上界仅差一个 $\sqrt{\log K}$，并且比 Jia et al. 多出一个 $\sqrt d$。值得一提的是，正交决策集这一招恰恰用满了「上下文老虎机决策集可变」的自由度，所以在决策集固定的随机线性老虎机里失效——后者只要前 $d$ 轮挑标准基（若那些轮方差为 0）就能零遗憾学全，因此根本拿不到方差相关下界（Remark 4.5）。

2. 多实例循环分配：在自适应序列里补上「组大小未知」的缺口

剥离分组依赖一个隐含前提——每组轮数 $|\mathcal K_i|$ 事先可算。对预定序列这没问题，但在自适应设定里对手逐轮生成方差，$|\mathcal K_i|$ 是个事先未知、甚至随机的量，导致 $M_i$ 没法按 $|\mathcal K_i|$ 去构造。作者的解法是：不再为每组造单一实例，而是为每组造 $L=\lceil\log_2 K\rceil+1$ 个实例 $M_{i,j}$，第 $j$ 个专门服务于轮数落在 $2^{j-1}\le|\mathcal K_i|<2^j$ 的情形。

每当某轮落进组 $\mathcal K_i$，就循环地把它派给 $\{M_{i,1},\dots,M_{i,L}\}$ 中的一个。循环分配保证每个 $M_{i,j}$ 被访问约 $|\mathcal K_i|/L$ 次，于是与真实区间匹配的那个 $j$（满足 $2^{j-1}\le|\mathcal K_i|<2^j$）恰好积累到 $\tilde\Omega\!\big(d_i\sqrt{\sigma^2(i)\,2^j}\big)=\tilde\Omega\!\big(d_i\sqrt{\sigma^2(i)\,|\mathcal K_i|}\big)$ 的遗憾。无论对手把 $|\mathcal K_i|$ 调到多大，总有一个匹配实例顶上来，下界因此与「组大小是否已知」无关。

3. 从期望到高概率：先压成常数概率，再用独立实例放大

第三个设计解决的是自适应序列下「累计方差 $\sum_k\sigma_k^2$ 本身依赖随机过程」带来的麻烦——这让期望型下界难以直接陈述，而标准 $d\sqrt K$ 型下界没有这个困扰。作者分两步把期望下界升级成高概率下界：先通过精细的方差控制和辅助算法，把期望遗憾界转成「以常数概率成立」的界；再创建多个相互独立的实例，借助 union bound 把常数概率放大到 $1-1/K$ 的高概率，得到 Theorem 5.2：

\[\Pr\!\Big[\mathrm{Regret}(K)\ge\Omega\big(d\sqrt{\textstyle\sum_k\sigma_k^2}\big/\log^6(dK)\big)\Big]\ge 1-\tfrac1K,\quad \text{当 }\textstyle\sum_k\sigma_k^2\ge\Omega(d^2).\]

这是据作者所知线性上下文老虎机的第一个高概率下界。代价是对数因子从 Theorem 4.1 的 $\log K$ 松到 $\log^6(dK)$，因为自适应性带来了更多需要 union 的随机性。这套「期望→高概率」的转换被作者认为可独立用于更广一类问题。

4. 强对手反例：用一个 $O(d)$ 遗憾的算法划出下界成立的精确边界

前三个设计都假设「弱对手」——对手必须在看到决策集 $D_k$ 之前定方差 $\sigma_k$。本设计反向论证：这个时序限制不是技术偷懒，而是本质必需。作者构造了一个「强对手」（可在看到 $D_k$ 之后再选 $\sigma_k$）配合一个特制学习算法，证明 Theorem 5.4：存在这样一对对手—算法，使得即便总方差 $\sum_k\sigma_k^2\ge K/2$，遗憾仍被 $O(d)$ 顶住。

直觉是：强对手能与学习者「合谋」，专门在那些已经被探明、不会再吃亏的方向上堆高方差，于是「方差很大」与「遗憾很大」之间的绑定被打破——既然有算法能在大方差下只付 $O(d)$ 遗憾，任何形如 $d\sqrt{\sum_k\sigma_k^2}$ 的下界都不可能成立。这个负面结果还顺势推广到随机线性老虎机（决策集固定，相当于对手预先知道 $D$），得到 Corollary 5.7：同样存在序列让某算法的遗憾 $\le d$ 而 $\sum_k\sigma_k^2\ge K/2$。换言之，方差相关下界只在弱对手 / 上下文（决策集可变）设定下才成立，本文的构造精确卡在这条边界上。

损失函数 / 训练策略¶

不适用（本文为下界证明，无可训练模型）。

实验关键数据¶

本文是纯理论工作，无数值实验。以下两表汇总其核心理论结论与定位。

主结果：下界 vs. 已有上下界¶

设定	本文下界	对照上界（SAVE, Zhao 2023）	与 Jia et al. (2024) 比
预定方差序列	$\Omega\!\big(d\sqrt{\sum_k\sigma_k^2/\log K}\big)$ (Thm 4.1)	$\tilde O\!\big(d\sqrt{\sum_k\sigma_k^2}+d\big)$	多出 $\sqrt d$；适用任意序列而非固定预算
自适应·弱对手	$\Omega\!\big(d\sqrt{\sum_k\sigma_k^2}/\log^6(dK)\big)$，高概率 (Thm 5.2)	同上	首个高概率下界
自适应·强对手	不存在（反例 $\mathrm{Regret}\le d$ 而 $\sum_k\sigma_k^2\ge K/2$）(Thm 5.4)	—	厘清下界成立的边界

结论：在弱对手 / 上下文设定下，下界与上界仅差对数因子，证明了 SAVE 上界中 $d\sqrt{\sum_k\sigma_k^2}$ 的最优性。

关键技术与适用范围¶

技术	解决的问题	适用范围 / 限制
剥离分组 + 正交子实例 (Lemma 4.3, Thm 4.1)	把一般方差序列拆成固定方差子问题	依赖决策集可变；随机线性老虎机失效
多实例循环分配 (Thm 5.2)	自适应下组大小 $	\mathcal K_i
期望→高概率提升 (Thm 5.2)	$\sum_k\sigma_k^2$ 随机、期望界难陈述	可迁移到更广问题
强对手反例 (Thm 5.4, Cor 5.7)	划定下界成立的边界	强对手 / 随机线性老虎机下界不存在

关键发现¶

$\sqrt d$ 缺口被补上：之前 Jia et al. 的 $\sqrt{d\Lambda}$ 与上界差 $\sqrt d$，本文通过正交分块把维度依赖撑满到 $d$，把 SAVE 上界钉成最优。
总方差需 $\ge\Omega(d^2)$：Theorem 4.1 要求 $\sum_k\sigma_k^2\gtrsim d^2$（全 $\sigma_k=1$ 时即 $K\gtrsim d^2$）。这与标准线性老虎机里 $d\sqrt K$ 下界只在 $K\ge\Omega(d^2)$ 时成立同源；总方差太小时，再多零方差轮也不增加问题本质难度。
下界存在与否对「时序」极度敏感：方差是在「看到决策集前」还是「之后」生成，直接决定下界存在还是消失——这是本文最反直觉之处。

亮点与洞察¶

正交分块把"求和"变成可证：按方差量级剥离 + 正交决策集，让各组互不泄露信息，从而把总遗憾干净地分解为各子问题遗憾之和——这是能从固定方差引理拼出一般序列下界的关键，思路可迁移到其他「异质难度叠加」的下界证明。
循环多实例对付未知组大小：用 $\log K$ 个针对不同轮数区间的实例 + 循环分配，绕开了「自适应序列下组大小事先不可知」这一构造障碍，是处理在线/自适应下界时很通用的一招。
首个高概率下界 + 通用转换：把期望下界经「常数概率→union bound 放大」升成高概率，填补了线性上下文老虎机长期只有期望下界的空白，且该转换框架本身可复用。
用反例精确定界：不满足于证出下界，还用一个 $O(d)$ 遗憾的强对手反例标出下界失效的确切条件，让"弱对手"这个假设从"技术需要"升级为"本质必需"。

局限与展望¶

仅限线性：所有结果都绑在线性奖励上；Jia et al. (2024) 在一般函数类（有限 eluder 维度、固定预算）上已有下界，但本文「一般方差序列」的分析能否推广到一般函数逼近仍是开放问题，作者明确留作未来工作。
对数因子不紧：自适应设定的下界带 $\log^6(dK)$，与上界的差距比预定序列的 $\log K$ 大不少，是否能收紧未知。
同方差假设的限制：弱对手下界要求同一轮所有动作 $x\in D_k$ 共享方差 $\sigma_k$，比 SAVE 允许动作相关方差更受限；作者指出把下界推到动作相关方差与其自适应构造从根本上不兼容。
随机线性老虎机无方差相关下界：决策集固定时（Cor 5.7）这类下界根本不存在，意味着方差相关的"可学习性收益"是上下文设定独有的。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 补上长期缺失的方差相关下界，并贡献首个线性上下文老虎机高概率下界与可复用的剥离 / 转换技术
实验充分度: ⭐⭐⭐⭐⭐ 纯理论工作，定理覆盖预定 / 弱对手 / 强对手三种设定且与上界配对，逻辑闭环（无需也不应有数值实验）
写作质量: ⭐⭐⭐⭐ 设定区分与证明脉络清晰，但下界的对数因子与多实例构造较技术性，门槛偏高
价值: ⭐⭐⭐⭐⭐ 钉死 SAVE 上界的最优性，并精确划出方差相关下界成立的边界条件，对在线学习理论有指导意义

设定	本文下界	对照上界（SAVE, Zhao 2023）	与 Jia et al. (2024) 比
预定方差序列	\(\Omega\!\big(d\sqrt{\sum_k\sigma_k^2/\log K}\big)\) (Thm 4.1)	\(\tilde O\!\big(d\sqrt{\sum_k\sigma_k^2}+d\big)\)	多出 \(\sqrt d\)；适用任意序列而非固定预算
自适应·弱对手	\(\Omega\!\big(d\sqrt{\sum_k\sigma_k^2}/\log^6(dK)\big)\)，高概率 (Thm 5.2)	同上	首个高概率下界
自适应·强对手	不存在（反例 \(\mathrm{Regret}\le d\) 而 \(\sum_k\sigma_k^2\ge K/2\)）(Thm 5.4)	—	厘清下界成立的边界