logistic bandits with tildeosqrtdt regret without context diversity assumptions¶
会议: NeurIPS 2026
arXiv: 2604.22161
领域: 学习理论
关键词: logistic bandits, contextual bandits, context diversity, sample splitting, one-step estimator
一句话总结¶
本文提出了首个无需上下文多样性假设（如协方差矩阵最小特征值严格正下界）即可达成率最优 \(\widetilde{\mathcal{O}}(\sqrt{dT})\) 累积遗憾的 \(K\) 臂逻辑斯蒂老虎机算法 SupSplitLog，通过创新性样本分流（pilot set 与 estimation set）与牛顿型一步修正机制，消除了随机均匀探索阶段，并将界拓展至数据依赖几何复杂度。
研究背景与动机¶
逻辑斯蒂老虎机（Logistic Bandits）作为在线二元反馈序列决策的标准建模框架，广泛应用于推荐系统、临床试验、网络调度与偏好强化学习。在 \(K\) 臂（有限动作集）背景下，经典线性老虎机理论已知能实现 \(\widetilde{\mathcal{O}}(\sqrt{dT})\) 的率最优遗憾上界。然而，在广义线性与逻辑斯蒂设定下，非线性 sigmoid 链接函数导致观测噪声与参数估计产生的 Hessian 阵耦合，使得无法像线性情况那样直接套用标量鞅浓度不等式来避免维数 \(d\) 的冗余膨胀。
为了在 \(K\) 臂逻辑斯蒂老虎机中证明 \(\widetilde{\mathcal{O}}(\sqrt{dT})\) 遗憾界，现存代表性方法（如 SupCB-GLM、SupLogistic、DDRTS-GLM）均极度依赖强上下文多样性假设（Context Diversity Assumption），即强制要求上下文协方差矩阵的最小特征值存在全局正下界 \(\lambda_{\min}(\mathbb{E}[\frac{1}{K}\sum_{a}\bm{x}_{t,a}\bm{x}_{t,a}^\top]) \ge \sigma_0^2 > 0\)（在 \(d\) 维空间中必然导致 \(\sigma_0^{-2} = \Omega(d)\)）。为了满足该条件，算法必须在前序阶段执行长度依赖于维度 \(d\) 的全空间均匀随机采样预热阶段。这带来了深刻的理论与实践矛盾：现实中特征往往高度集中在某个低维子空间或退化流形上，最小特征值可能任意接近于 0，迫使已有算法彻底失效；同时强制全局均匀探索不仅造成高昂的早期遗憾，还使得遗憾上界保守地随全空间物理维度 \(d\) 剧烈增长。
本文的核心洞察在于：之所以需要上下文多样性与强行抬高 Hessian 最小特征值，完全是因为传统估计器将所有样本混杂在一起计算 MLE，导致中间点 Hessian 与误差噪声高度统计相关；若能打破样本用途的混杂，便无需借助全空间均匀特征来强行正定化 Hessian。本文的核心 idea 是：提出样本解耦分流与牛顿型一步修正架构（SupSplitLog），将层级样本自适应拆分为试点集（用于拟合粗糙初值点）与估计集（用于一步曲率校正），借助空间几何不确定性门限精确平衡两阶段误差，彻底摆脱上下文多样性假设并实现最优 \(\widetilde{\mathcal{O}}(\sqrt{dT})\) 遗憾。
方法详解¶
整体框架¶
SupSplitLog 算法构建在分层排除（Auer elimination）框架之上，维护 \(S = \lfloor 0.5 \log_2 T \rfloor\) 个独立的样本层级桶 \(\Psi^{(s)}\)。在每一轮决策中，对于未被排除的候选臂集 \(A^{(s)}\)，算法计算当前一步校正估计器下的预测奖励与基于估计集特征的不确定性宽度 \(w_{t,a}^{(s)}\)。当存在臂的不确定性超过当前层级分辨率 \(2^{-s}\) 时，触发探索条件 (a)，选择不确定性最大的臂拉动并将该样本纳入当前层级；若所有臂不确定性均低于 \(1/\sqrt{T}\) 则进入利用状态并选择贪心臂（条件 (b)）；否则消除劣臂后进入更细粒度的下一层级 \(s \leftarrow s+1\)（条件 (c)）。
方法的核心创新在于将每个层级的样本流严格解耦为互斥的两部分：试点集 \(P^{(s)}\) 和估计集 \(E^{(s)}\)（即 \(\Psi^{(s)} = P^{(s)} \cup E^{(s)}, P^{(s)} \cap E^{(s)} = \emptyset\)）。进入层级 \(s\) 的样本通过几何正交不确定性阈值 \(\tau^{(s)}\) 进行分流：当沿着所选臂方向在试点集上的预测方差较大时，判定初值点精度尚不足，将样本分流至试点集 \(P^{(s)}\)；反之，若在试点集方向已足够精确，则分配给估计集 \(E^{(s)}\) 以执行一步牛顿校正。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入上下文与候选臂集<br/>观测当前轮 K 个特征向量"] --> B["分层臂过滤与置信评估<br/>计算预测值与不确定性宽度"]
B -->|条件a: 最大不确定性 > 2^-s| C["自适应样本分流机制<br/>对比试点集方差与阈值 tau"]
C -->|方差 > tau 归入 P| D["试点集初值估计<br/>正则化逻辑斯蒂损失拟合"]
C -->|方差 <= tau 归入 E| E["牛顿型一步校正<br/>在估计集上执行单步曲率更新"]
D --> F["更新置信椭球与下一轮决策"]
E --> F
B -->|条件b: 所有不确定性 <= 1/sqrt T| G["贪心臂利用开发"]
B -->|条件c: 宽度 <= 2^-s| H["劣臂淘汰并进入下一层 s+1"]关键设计¶
1. 试点集与估计集样本分流：解耦噪声与曲率矩阵的统计依赖
传统方法在对逻辑斯蒂损失做 Taylor 展开分析误差时，中间点 Hessian 矩阵 \(\check{\mathbf{H}}_t\) 内部的评估点取决于包含当前噪声在内的所有样本，导致交叉项无法作为鞅差序列应用标量浓度不等式。本文将每个层级 \(s\) 的动作序列在算法逻辑上划分入两个互斥集合 \(P^{(s)}\) 与 \(E^{(s)}\)。试点集 \(P^{(s)}\) 上的样本仅用于通过正则化逻辑斯蒂最大似然估计求解初始参数 \(\bar{\bm{\theta}}_t^{(s)}\)： $\(\bar{\bm{\theta}}_t^{(s)} = \arg\min_{\bm{\theta} \in \Theta} \sum_{i \in P^{(s)}(t)} \left[ -r_i \log(\mu(\bm{x}_{i,a_i}^\top \bm{\theta})) - (1-r_i)\log(1-\mu(\bm{x}_{i,a_i}^\top \bm{\theta})) \right] + \frac{\lambda}{2} \|\bm{\theta}\|_2^2\)$ 当且仅当在新观测方向上的试点集特征协方差逆范数满足 \(\|\bm{x}_{t,a_t}\|_{(\mathbf{V}_{P,t-1}^{(s)})^{-1}}^2 > \tau^{(s)}\) 时（条件 (a1)），样本才归入 \(P^{(s)}\)。这一设计的关键有效性在于，构建估计集曲率矩阵 \(\mathbf{H}_t^{(s)}(\bar{\bm{\theta}}_t^{(s)})\) 所依据的参数 \(\bar{\bm{\theta}}_t^{(s)}\) 完全由试点集 \(P^{(s)}\) 确定，对于估计集 \(E^{(s)}\) 中的伯努利噪声 \(\epsilon_i = r_i - \mu(\bm{x}_{i,a_i}^\top \bm{\theta}^*)\) 而言，曲率加权系数 \(p_i = \bm{x}^\top (\mathbf{H}_t^{(s)}(\bar{\bm{\theta}}_t^{(s)}))^{-1}\bm{x}_{i,a_i}\) 在条件 \(\sigma\)-代数下是确定性的，从而直接激活了经典标量 Bernstein 浓度不等式。
2. 牛顿型一步校正估计器：实现免维度依赖的高概率预测界
在传统半参数统计中，一步 M-估计器（One-step M-estimator）常用于从粗糙 \(\sqrt{n}\)-一致初值出发免迭代逼近完全有效估计。本文将其迁移至在线老虎机领域，利用估计集 \(E^{(s)}(t)\) 构造经验梯度 \(\bm{g}_t^{(s)}(\bm{\theta})\) 与经验 Hessian 阵 \(\mathbf{H}_t^{(s)}(\bm{\theta})\)，执行单步修正： $\(\widehat{\bm{\theta}}_t^{(s)} = \bar{\bm{\theta}}_t^{(s)} + \left(\mathbf{H}_t^{(s)}(\bar{\bm{\theta}}_t^{(s)})\right)^{-1} \bm{g}_t^{(s)}(\bar{\bm{\theta}}_t^{(s)})\)$ 该估计器的预测误差可以精确分解为三项：噪声项（标量噪声线性加权）、正则化偏差项以及高阶泰勒余项： $\(|\bm{x}^\top (\widehat{\bm{\theta}}_t^{(s)} - \bm{\theta}^*)| \le \left|\bm{x}^\top (\mathbf{H}_t^{(s)})^{-1} \sum_{i \in E} \epsilon_i \bm{x}_{i,a_i}\right| + \left|\bm{x}^\top (\mathbf{H}_t^{(s)})^{-1} \lambda \bm{\theta}^*\right| + \text{Remainder}\)$ 利用逻辑斯蒂导数的 1-Lipschitz 连续性（即 \(|(\log \dot{\mu}(v))'| \le 1\)），余项可被紧致约束为 \((e^r - 1) \sqrt{|E|} \sqrt{L_\mu \kappa} \|\bm{x}\|_{\mathbf{V}_E^{-1}}\)，其中 \(r = \max_{i \in E} |\bm{x}_{i,a_i}^\top (\bar{\bm{\theta}} - \bm{\theta}^*)|\) 为初值点在估计集方向上的最大局部拟合偏差。通过分流门限控制，余项被压制在主噪声项常数倍以内，最终推导出完全不依赖维度 \(d\) 的预测误差高概率上界 \(|\bm{x}_{t,a}^\top (\widehat{\bm{\theta}}_{t-1}^{(s)} - \bm{\theta}^*)| \le w_{t,a}^{(s)} = \alpha \|\bm{x}_{t,a}\|_{(\mathbf{V}_{E,t-1}^{(s)})^{-1}}\)。
3. 动态几何门限与数据依赖复杂度扩展：收缩低维流形上的探索成本
算法的核心平衡杠杆是阈值 \(\tau^{(s)}\)。若 \(\tau^{(s)}\) 过大，试点集样本过少，初值点精度不足会导致一步校正余项爆炸；若 \(\tau^{(s)}\) 过小，过多样本被截流至试点集，导致用于消除不确定性的估计集有效样本不足且试点集自身产生过多遗憾。论文精确构造了阈值： $\(\tau^{(s)} = \frac{1}{\beta^2} \min\left\{ 1, \frac{2^{-s}}{\sqrt{32 L_\mu \kappa d \log(1+ T/(\kappa\lambda d))}} \right\}\)$ 结合椭球覆盖引理，进入试点集的总步数严格受控于 \(|P^{(s)}(T)| \le 2 d \log(1+T/(\kappa\lambda d)) (\tau^{(s)})^{-1}\)，使得试点集累积遗憾与估计集累积遗憾达到精确的阶数平衡。进一步地，算法将固定的维度参数 \(d\) 替换为动态追踪的 Gram 矩阵对数行列式： $\(\widetilde{d} = \log\left(\frac{\det \mathbf{V}_T}{\det (\kappa\lambda \mathbf{I})}\right) = \log\det\left(\mathbf{I} + \frac{1}{\kappa\lambda} \sum_{t=1}^T \bm{x}_{t,a_t}\bm{x}_{t,a_t}^\top\right)\)$ 自适应更新门限 \(\tau_t^{(s)}\) 与自归一化常数 \(\beta_t^{(s)}\)（即 Algorithm 2）。当上下文集中在秩为 \(r \ll d\) 的低维子空间时，\(\widetilde{d} \approx r \log T\)，使算法自动退化为依赖内蕴有效维数 \(r\) 的遗憾，避免了高维环境下的维数灾难。
实验关键数据¶
主实验¶
实验在合成的高维逻辑斯蒂老虎机环境上进行评估，固定时界 \(T=2000\)、动作数 \(K=5\)、问题难度参数 \(\kappa=20\)、正则化参数 \(\lambda=1\)、参数边界 \(B=1\)。通过控制上下文向量生成的有效子空间秩 \(r\) 与特征范数范围，模拟三种几何分布（低维集中度由强到弱）：
- low 几何体制：有效子空间维度 \(r=2\)，特征范数 \(\|\bm{x}\|_2 \in [0, 0.05]\)（高度退化，对数行列式 \(\log\frac{\det \mathbf{V}_t}{\det \kappa\lambda \mathbf{I}}\) 极小）；
- middle 几何体制：有效子空间维度 \(r=10\)，特征范数 \(\|\bm{x}\|_2 \in [0.3, 0.5]\)；
- high 几何体制：全空间充满 \(r=d\)，特征范数 \(\|\bm{x}\|_2 \in [0.8, 1.0]\)。
对比算法包括当前最顶尖的三大代表方法：SupCB-GLM、SupLogistic（两者均基于传统 Auer 分层与全维度均匀探索预热）以及 DDRTS-GLM（双重双稳健 Thompson 采样）。
| 几何分布体制 (以 \(T=2000\) 统计) | 特征空间维度 \(d\) | 评估指标 (累积遗憾) | SupSplitLog (本文) | DDRTS-GLM | SupLogistic | SupCB-GLM | 相对优势/表现分析 |
|---|---|---|---|---|---|---|---|
low (强退化 \(r=2\)) |
\(d=20\) | 最终累积遗憾 \(R_T\) | 最优 (显著平缓收敛) | 次优 (发散或慢速) | 劣 (受制于预热开销) | 劣 (方差极大) | 无需全向探索，直接自适应内蕴子空间 |
low (强退化 \(r=2\)) |
\(d=100\) | 最终累积遗憾 \(R_T\) | 最优 (近亚线性平稳) | 较高 | 极高 (预热强制耗尽) | 极高 | 彻底免疫高维失效；基准方法因缺乏多样性崩塌 |
middle (部分退化 \(r=10\)) |
\(d=20\) | 最终累积遗憾 \(R_T\) | 最优 | 极具竞争力 | 较高 | 较高 | 适中复杂度下样本分流优势显著 |
middle (部分退化 \(r=10\)) |
\(d=100\) | 最终累积遗憾 \(R_T\) | 最优 | 次优 | 较高 | 较高 | 在大环境维度下表现极为鲁棒 |
high (全向充满 \(r=d\)) |
\(d=3\) | 最终累积遗憾 \(R_T\) | 优异 (与 SOTA 相当) | 微弱领先 | 相当 | 略逊 | 全向探索成立时各基线理论假设均满足 |
high (全向充满 \(r=d\)) |
\(d=20\) | 最终累积遗憾 \(R_T\) | 优异 | 微弱领先 | 次之 | 次之 | DDRTS 依靠后验采样充分利用了强多样性 |
理论性质与遗憾界对比（分析表）¶
不同算法在上下文假设、遗憾依赖阶数与低维自适应性上的理论对比：
| 算法 | 上下文多样性假设要求 | 累积遗憾上界 \(\widetilde{\mathcal{O}}(\cdot)\) | 主项维度依赖 | 非主导项维度依赖 | 数据自适应性 (Data-dependent) |
|---|---|---|---|---|---|
| SupCB-GLM (Li et al., 2017) | 必须 (\(\sigma_0^{-2} = \Omega(d)\)) | \(\kappa \sqrt{dT} + d \sigma_0^{-8} + \kappa^8 d^3 \sigma_0^{-4}\) | \(\sqrt{d}\) | \(\mathcal{O}(d^9)\) 极高次幂 | ✗ (固定环境全维) |
| SupLogistic (Jun et al., 2021) | 必须 (\(\sigma_0^{-2} = \Omega(d)\)) | \(\sqrt{dT} + d \sigma_0^{-8} + \kappa^2 d \sigma_0^{-4}\) | \(\sqrt{d}\) | \(\mathcal{O}(d^9)\) 极高次幂 | ✗ (固定环境全维) |
| DDRTS-GLM (Kim et al., 2023) | 必须 (\(\sigma_0^{-2} = \Omega(d)\)) | \(\sigma_0^{-1}\sqrt{\kappa T} + \kappa^3 \sigma_0^{-6}\) | \(\sqrt{d}\) (由 \(\sigma_0^{-1}\) 隐式引入) | \(\mathcal{O}(d^3)\) | ✗ (依赖固定下界) |
| SupSplitLog (本文) | 完全无需任何多样性假设 | \(\kappa \sqrt{dT} + \kappa^{2.5} d^{2.5}\) | \(\sqrt{d}\) (最优) | \(\mathcal{O}(d^{2.5})\) (严格改进) | ✓ (替换 \(d\) 为 \(\widetilde{d} \ll d\)) |
关键发现¶
- 低维结构自适应性：在
low与middle几何体制中，传统基线由于强制实施长度正比于 \(\sqrt{dT}\) 的全局探索预热，在退化子空间上浪费了大量样本且拉高了前期遗憾；SupSplitLog 的累积遗憾曲线极为平缓，其增量几乎仅与低维有效秩 \(r\) 对应的对数行列式成正比。 - 高维鲁棒性：当维度 \(d\) 从 3 扩展至 100 时，依赖多样性假设的基线方法由于 \(\sigma_0^{-2} = \Omega(d)\) 导致其置信界严重发散，性能急剧劣化；SupSplitLog 不仅在 \(d=100\) 的低维退化场景保持极低遗憾，且无需做任何前置超参数微调。
- 与后验采样基线的权衡：在
high全向各向同性体制下，DDRTS-GLM 展现了 Thompson 采样的实证优势（经验常数略好）；但一旦脱离全向独立假设，DDRTS-GLM 的表现迅速受挫，证明了 SupSplitLog 理论保证的坚实性。
亮点与洞察¶
- 半参数一步修正引入在线决策：创新性地将数理统计中的一步牛顿修正与多臂老虎机分层消除相结合。巧妙之处在于利用算法内部控制的样本分配将参数估计值与残差观测值强行置于不同滤波（filtration）下，完美化解了逻辑斯蒂自回归非线性带来的鞅差失效难题。
- 摆脱虚妄的多样性假设：过去近十年逻辑斯蒂 \(K\) 臂老虎机理论普遍认为要达到 \(\sqrt{dT}\) 必须做全向随机探索以使得信息矩阵各向均匀膨胀；本文彻底打破了这一思想禁锢，证明只需在已有样本方差不足的特定正交补方向精准补充试点集，便能达到全域最优收敛率。
- 向核化与神经老虎机无缝迁移的潜力：因为完全去除了特征协方差最小特征值的先验下界，且遗憾界可完全以 Gram 矩阵对数行列式 \(\log\det(\mathbf{I} + \mathbf{V}_T)\) 刻画，这一机制天然契合再生核希尔伯特空间（RKHS）及神经常见特征维度无穷或极大的设置，为广义非线性老虎机打通了全新理论范式。
局限与展望¶
- 次要项对维度的多项式依赖：论文最终界中的低阶常数项包含 \(\kappa^{2.5} d^{2.5}\)（或数据依赖版本下的 \(\widetilde{d}^{2.5}\)），虽然相较于以往算法的 \(d^9\) 级别多项式已有本质改进，但在超大维度甚至 \(d \approx T\) 的极端场景下，该常数项仍可能主导有限时间步内的开销。
- 对非线性参数 \(\kappa\) 的高阶敏感：界中主项包含 \(\kappa \sqrt{dT}\)，次项含 \(\kappa^{2.5}\)。由于 \(\kappa = \sup \frac{1}{\dot{\mu}}\) 随参数范数 \(B\) 指数级爆炸（\(\kappa \sim e^B\)），在极端奖励稀疏或饱和场景下的极小方差仍会导致上界较为保守。
- 批处理计算开销：在每一轮判断中都需要对候选臂特征计算基于矩阵逆的马氏距离 \(\|\bm{x}\|_{(\mathbf{V}_E)^{-1}}\) 与 \(\|\bm{x}\|_{(\mathbf{V}_P)^{-1}}\)，并动态计算增量行列式，在高维大动作集下的单步延迟有待通过矩阵逆递推更新（Sherman-Morrison）进一步加速优化。
相关工作与启发¶
- vs SupCB-GLM (Li et al., 2017) & SupLogistic (Jun et al., 2021): 两者均基于 Auer 分层排除框架，但都因无法剥离中间点 Hessian 的随机性而不得不退求其次：引入 \(\sigma_0^2\) 正定下界并通过全向随机采样强行让所有方向方差收敛，由此付出了极高阶的 \(d \sigma_0^{-8}\) 遗憾惩罚。本文通过样本拆分一步法直接消除这一结构性缺陷，将上界从超高多项式彻底精简至干净的 \(\widetilde{\mathcal{O}}(\kappa \sqrt{dT} + \kappa^{2.5} d^{2.5})\)。
- vs DDRTS-GLM (Kim et al., 2023): DDRTS-GLM 采用双重双稳健加权与 Thompson 采样跳过了 Auer 框架，得到了实证上更具启发式的表现，但其分析仍然深植于全局正定特征假设中（依赖 \(\sigma_0^{-1} \sqrt{\kappa T}\)）。本文算法是纯粹确定性的置信上界消除法，给出了最严格的免假设保证，且在低维结构中实测显著击败 DDRTS。
- vs Filippi et al. (2010) 经典广义线性老虎机: Filippi 等人在无需多样性假设下只能通过直接自归一化技术获得 \(\widetilde{\mathcal{O}}(d\sqrt{T})\) 界（主项带 \(d\) 而非 \(\sqrt{d}\)）。本文通过 \(K\) 臂独立分层与一步修正首次在无假设下将主项降至率最优的 \(\sqrt{dT}\)。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次打破逻辑斯蒂老虎机长期存在的上下文多样性假设，样本分流与牛顿一步校正结合精妙。
- 实验充分度: ⭐⭐⭐⭐ 理论证明严丝合缝，合成实验精准针对低维退化流形验证了几何自适应机制；缺少真实工业级数据集验证。
- 写作质量: ⭐⭐⭐⭐⭐ 动机阐述深刻，对为什么传统方法需要多样性假设的技术症结解析极为透彻，定理主线清晰。
- 价值: ⭐⭐⭐⭐⭐ 解决了广义线性多臂老虎机长期悬而未决的理论难题，并架起了通往高维/核化逻辑斯蒂老虎机的桥梁。