Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions¶

会议: NeurIPS 2026
arXiv: 2604.22161
领域: 学习理论
关键词: 逻辑多臂老虎机、上下文老虎机、样本分割、单步牛顿校正、无分集假设

一句话总结¶

提出 SupSplitLog 算法，通过将样本正交分割为用于粗估计的引导集与用于牛顿修正的估计集，首次在无需任何上下文协方差特征值下界（分集假设）的前提下实现了 $\tilde{O}(\sqrt{dT})$ 的极小极大最优累积遗憾，并支持数据依赖的几何自适应上界。

研究背景与动机¶

逻辑多臂老虎机（Logistic Bandits）是建模二值奖励反馈下序贯决策问题的经典数学框架，在在线广告召回、推荐系统点击率预估及大语言模型偏好强化学习等领域具有坚实的理论支撑。在线性上下文赌博机中，通过 Auer 框架构建独立样本桶已能达到 $\tilde{O}(\sqrt{dT})$ 阶的维度次线性遗憾；然而，在非线性逻辑链接函数 $\mu(z)=(1+e^{-z})^{-1}$ 下，最大似然估计的泰勒展开余项包含依赖参数未知中值点的海森矩阵，导致噪声项与数据自适应选择产生复杂的统计纠缠。为了压制海森矩阵偏差，先前达到 $\tilde{O}(\sqrt{dT})$ 遗憾的最优算法（如 SupCB-GLM、SupLogistic、DDRTS-GLM）无一例外地强加了严格的上下文多样性（Context Diversity）假设，要求特征协方差矩阵的最小特征值全局有正下界 $\lambda_{\min}(\mathbb{E}[\frac{1}{K}\sum_{a}\bm{x}_{t,a}\bm{x}_{t,a}^{\top}]) \ge \sigma_0^2 > 0$。

这种分集假设在理论和实际应用中带来了严重的局限性。一方面，由于单位球内向量协方差特征值天然满足 $\sigma_0^{-2} = \Omega(d)$，使得先前界中的高阶项或前导项实际劣于 $\sqrt{dT}$，在特征维度升高时产生维数灾难；另一方面，分集假设彻底排除了上下文向量集中在低维流形或低维子空间的常见退化场景。现有无分集假设的算法（如基于自协调分析的广义线性老虎机）其遗憾界普遍退化为 $\tilde{O}(d\sqrt{T})$，存在显著的 $\sqrt{d}$ 间隙。导致这一理论鸿沟的核心矛盾在于：如何在消除对特征全空间均匀探索强行依赖的同时，解耦估计器诱导海森矩阵中的历史噪声相关性，从而将标量型集中不等式严谨应用于非线性项。

本文的切入角度是打破传统最大似然估计“全样本直接重优化”的范式，从半参数统计学中的单步牛顿估计器（One-step Estimator）汲取灵感。通过构建基于不确定性自适应触发的样本正交分割机制，算法将每个置信层级的探索样本严格解耦为引导集（Pilot Set）与估计集（Estimation Set）。核心 idea：将收集的反馈样本正交分割为用于构建粗糙初始估计量的引导集与用于执行单步牛顿曲率校正的估计集，彻底切断校正海森矩阵对当前估计集噪声的统计依赖，在完全无需上下文多样性假设的前提下首次达成 $\tilde{O}(\kappa\sqrt{dT} + \kappa^{2.5}d^{2.5})$ 的速率最优遗憾界。

方法详解¶

整体框架¶

SupSplitLog 算法建立在分层逐级消除（Auer-style elimination）的总体架构之上，将时间跨度离散化为 $S = \lfloor 0.5 \log_2 T \rfloor$ 个指数衰减的不确定性层级 $s \in [S]$。在每个层级 $s$ 内，维护一个独立采样桶 $\Psi^{(s)}$。与传统算法无差别汇聚样本不同，SupSplitLog 创新地将 $\Psi^{(s)}$ 实时解耦为两个互斥的样本子集：引导集 $P^{(s)}$ 与估计集 $E^{(s)}$（满足 $\Psi^{(s)} = P^{(s)} \cup E^{(s)}$ 且 $P^{(s)} \cap E^{(s)} = \emptyset$）。引导集 $P^{(s)}$ 用于求解带正则化的逻辑回归损失，产出初始点估计量 $\bar{\bm{\theta}}_t^{(s)}$；估计集 $E^{(s)}$ 则专门用来计算局部梯度与经验海森曲率，执行单步牛顿步校正以输出最终决策估计量 $\widehat{\bm{\theta}}_t^{(s)}$。

在每一轮 $t$，算法自底向上遍历层级 $s$：若动作集合 $A^{(s)}$ 中存在某一动作在估计集特征矩阵 $\mathbf{V}_{E,t-1}^{(s)}$ 下的不确定性宽度 $w_{t,a}^{(s)}$ 超过当前层级阈值 $2^{-s}$，算法触发探索并选择不确定性最大的动作 $a_t$；接着通过局部特征方向在引导集特征矩阵 $\mathbf{V}_{P,t-1}^{(s)}$ 下的投影范数判定是将该步样本分流至引导集 $P^{(s)}$ 还是估计集 $E^{(s)}$。若所有动作不确定性均低于 $1/\sqrt{T}$ 则进入贪心开发；若介于两者之间，则剔除劣质动作并递进至下一精细层级 $s+1$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["当前轮上下文动作集 X_t = {x_t,a}"] --> Lvl["分层筛选：初始化候选集 A^(1) = [K], 层级 s = 1"]
    Lvl --> Est["双集解耦估计：P^(s) 产出初始粗估计 θ_bar<br/>E^(s) 执行单步牛顿校正得 θ_hat"]
    Est --> Eval{"动作不确定性检测<br/>w_t,a > 2^(-s) ?"}
    Eval -->|条件 a: 存在高不确定性| PickExpl["探索动作：选择最大不确定性 a_t<br/>观察环境反馈二值奖励 r_t"]
    PickExpl --> SplitCond{"引导不确定性阈值判定<br/>||x_t,at||^2 > τ^(s) ?"}
    SplitCond -->|条件 a1: 超出阈值| AddP["分配至引导集 P^(s)<br/>提升初始点估计精度"]
    SplitCond -->|条件 a2: 未超阈值| AddE["分配至估计集 E^(s)<br/>累计单步牛顿校正曲率"]
    Eval -->|条件 b: 所有动作 w_t,a <= 1/sqrt(T)| Exploitation["纯开发决策：贪心选择 m_t,a 最大动作"]
    Eval -->|条件 c: 不确定性介于两者之间| Elim["动作空间剪枝：淘汰次优动作<br/>层级递增 s <- s + 1 进入下一阶段"]
    AddP --> NextRound["结束本轮，进入 t+1 轮"]
    AddE --> NextRound
    Exploitation --> NextRound
    Elim --> Lvl

关键设计¶

1. 双集解耦的单步牛顿估计：隔绝曲率依赖与噪声相关 传统广义线性模型估计器直接在全样本上优化正则化负对数似然，使得海森矩阵 $\mathbf{H}_t(\check{\bm{\theta}})$ 包含由中值定理引入的参数未知值 $\check{\bm{\theta}}$，进而将历史奖励噪声隐式注入逆协方差加权中，彻底破坏了标量集中不等式的独立性前提。SupSplitLog 的核心机制在于严格分离样本角色： $$ \bar{\bm{\theta}}t^{(s)} = \argmin} \in \Theta} \left{ \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}|_2^2 \right} $$ 利用引导集 }^\top \bm{\theta})) \right] + \frac{\lambda}{2}|\bm{\theta$P^{(s)}(t)$ 获得该粗糙初始点后，在估计集 $E^{(s)}(t)$ 上仅计算一阶梯度 $\bm{g}_t^{(s)}(\bar{\bm{\theta}}_t^{(s)})$ 与经验海森矩阵 $\mathbf{H}_t^{(s)}(\bar{\bm{\theta}}_t^{(s)}) = \lambda \mathbf{I} + \sum_{i \in E^{(s)}(t)} \dot{\mu}(\bm{x}_{i,a_i}^\top \bar{\bm{\theta}}_t^{(s)})\bm{x}_{i,a_i}\bm{x}_{i,a_i}^\top$，进而通过单步牛顿步生成校正估计： $$ \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}^*) = (\text{noise}) + (\text{bias}) + (\text{remainder})$ 中，由于海森矩阵逆算子完全由外生引导集样本与估计集上下文确定，条件化于适当的代数流 $\mathcal{H}_{s,t}$ 后，估计集内的噪声项 $\epsilon_i = r_i - \mu(\bm{x}_{i,a_i}^\top \bm{\theta}^*)$ 严格保持零均值与条件独立，允许直接套用标量 Bernstein 不等式，完全抹去了对特征维度 $d$ 的显式依赖。

2. 几何投影门控自适应分流：平衡初始点精度与校正稳健性 单步牛顿校正的成功实施高度依赖初始点 $\bar{\bm{\theta}}_t^{(s)}$ 在关键上下文方向上的精度。为控制高阶泰勒余项 $(\text{remainder})$，必须确保局部内积偏差 $r_t^{(s)} = \max_{i \in E^{(s)}(t)} |\bm{x}_{i,a_i}^\top (\bar{\bm{\theta}}_t^{(s)} - \bm{\theta}^*)|$ 恒小于 1。SupSplitLog 设计了基于马氏距离的自适应门控准则： $$ |\bm{x}{t,a_t}|{P,t-1}^{(s)})^{-1}}^2 > \tau^{(s)} \coloneqq \frac{1}{\beta^2} \min\left{ 1, \frac{2^{-s}}{\sqrt{32 L\mu \kappa d \log(1 + T/(\kappa\lambda d))}} \right} $$ 若新样本方向在引导集所张成的椭球空间中仍具有较高不确定性（大于阈值 $\tau^{(s)}$），系统将其归入引导集 $P^{(s)}$，强力压制自标准化椭球范数下的参数估计误差；反之，一旦特征方向已被引导集充分学习，样本便源源不断输入估计集 $E^{(s)}$ 用于强化曲率校正。通过椭圆势能引理（Elliptical Potential Lemma），引导集样本总数 $|P^{(s)}(T)| \le 2d \log(1 + T/(\kappa\lambda d)) (\tau^{(s)})^{-1}$ 被严格约束，使得引导集带来的次优探索遗憾与估计集校正残差达到精准渐近平衡。

3. 数据依赖的自适应上界扩展：低维流形自适应无损加速 针对现实场景中上下文向量并非充满全维欧氏空间、而是紧密分布于未知低维子空间或非均匀流形上的退化形态，算法给出了动态数据依赖版本。算法摒弃固定的全局常数 $\beta$ 与 $\tau^{(s)}$，代之以依据在线累积 Gram 矩阵实时计算的自适应参数 $\beta_{t-1}^{(s)}$ 与 $\tau_{t-1}^{(s)}$。该机制使得理论分析中的维度项 $d$ 完全被数据内生复杂度测度 $\tilde{d} \coloneqq \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)$ 所置换。当特征集中于有效维度为 $r \ll d$ 的子空间时，$\tilde{d} = O(r \log T)$，算法无需先验知晓内在有效维度，即可在执行期间自动获得收敛加速。

损失函数 / 训练策略¶

引导集参数优化采用带 $L_2$ 正则化的负对数似然损失： $$ \mathcal{L}t^{(s)}(\bm{\theta}) = \sum}(t)} \left[ -r_i \log(\mu(\bm{x{i,a_i}^\top \bm{\theta})) - (1-r_i)\log(1 - \mu(\bm{x}|_2^2 $$ 在实际运行中，设置超参数 }^\top \bm{\theta})) \right] + \frac{\lambda}{2}|\bm{\theta$\lambda = 1$，常数上界 $B=1$，曲率下界常数 $\kappa=20$。对引导集的凸优化求解采用投影梯度下降法（Projected Gradient Descent），迭代轮数固定为 20 步，学习率设定为 0.3。在得到 $\bar{\bm{\theta}}_t^{(s)}$ 后，单步牛顿校正直接通过解析矩阵运算完成逆海森矩阵与梯度的线性变换，无需对估计集进行多轮迭代拟合，极大降低了在线决策的计算耗时。

实验关键数据¶

主实验¶

实验在合成逻辑赌博机环境中评估算法累积遗憾，环境固定总步数 $T=2000$，候选动作数 $K=5$，特征范数满足 $\|\bm{x}_{t,a}\|_2 \le 1$，未知参数范数 $\|\bm{\theta}^*\|_2 \le B = 1$，导数下界约束 $\dot{\mu}(\bm{x}_{t,a}^\top \bm{\theta}^*) \ge 1/\kappa = 1/20$。对比基线包括：SupCB-GLM (Li et al., 2017)、SupLogistic (Jun et al., 2021) 以及 DDRTS-GLM (Kim et al., 2023)。评估在三种不同环境几何结构（High、Middle、Low，表征内在有效子空间维度及特征范数差异）与不同环境维度（$d \in \{3, 20, 100\}$）下进行，重复 10 次独立随机实验并统计均值与标准差。

下表总结了在维度 $d=20$ 及高维 $d=100$ 下各算法在三类几何空间结构中的最终累积遗憾对比：

实验场景配置	结构复杂度 ($\log\frac{\det\mathbf{V}_T}{\det\kappa\lambda\mathbf{I}}$)	SupSplitLog (本文)	SupCB-GLM	SupLogistic	DDRTS-GLM	相对最佳基线提升
$d=20$, Low 几何 ($r=2$)	极低（约 0.5 - 2）	$5.4 \pm 1.2$	$28.6 \pm 4.5$	$24.1 \pm 3.8$	$18.2 \pm 3.1$	70.3% 降低
$d=20$, Middle 几何 ($r=10$)	中等（约 15 - 25）	$16.8 \pm 2.9$	$54.2 \pm 6.1$	$46.7 \pm 5.4$	$23.5 \pm 3.7$	28.5% 降低
$d=20$, High 几何 ($r=20$)	满秩扩展（约 45 - 60）	$42.1 \pm 5.2$	$88.4 \pm 9.2$	$79.3 \pm 8.6$	$39.7 \pm 4.8$	性能相当 (相差~6%)
$d=100$, Low 几何 ($r=2$)	极端低维（约 0.5 - 3）	$6.1 \pm 1.4$	$142.5 \pm 16.8$	$118.2 \pm 14.1$	$32.4 \pm 5.1$	81.2% 降低
$d=100$, Middle 几何 ($r=10$)	稀疏退化（约 18 - 30）	$21.4 \pm 3.5$	$230.1 \pm 21.4$	$195.4 \pm 18.9$	$48.6 \pm 6.3$	55.9% 降低
$d=100$, High 几何 ($r=100$)	高维均匀（约 160 - 200）	$96.5 \pm 8.7$	$380.6 \pm 34.2$	$315.2 \pm 28.7$	$88.2 \pm 7.9$	处于同一竞争力区间

消融实验¶

消融实验着重考察不同的数据几何分布机制（即特征范数区间与有效子空间维度 $r$ 的组合）对算法内部引导集 $P^{(s)}$、估计集 $E^{(s)}$ 样本分配比率及后悔增长速率的影响。

| 几何结构模式 | 有效秩 $r$ 与特征范数 $\|\bm{x}\|_2$ | 引导集占比 $|P|/T$ | 估计集占比 $|E|/T$ | 累积遗憾 ($T=2000, d=100$) | 说明 | |-------------|---------------------------------------|-------------------|-------------------|---------------------------|------| | Low 流形配置 | $r=2, \|\bm{x}\|_2 \in [0, 0.05]$ | $3.2\%$ | $18.4\%$ (其余为开发) | $6.1 \pm 1.4$ | 极低秩下引导集极快饱和，绝大多数样本用于开发 | | Middle 流形配置 | $r=10, \|\bm{x}\|_2 \in [0.3, 0.5]$ | $8.7\%$ | $34.1\%$ | $21.4 \pm 3.5$ | 引导集稳定约束主子空间方向误差，单步校正高效收敛 | | High 流形配置 | $r=100, \|\bm{x}\|_2 \in [0.8, 1.0]$ | $24.6\%$ | $49.5\%$ | $96.5 \pm 8.7$ | 满秩下需要更多引导样本探索各维度，遗憾受制于高阶项 | | 固定阈值基准 (无自适应 $\tau_t^{(s)}$) | 固定 $\tau^{(s)}$ (Algorithm 1) | $21.5\%$ | $38.2\%$ | $44.8 \pm 5.9$ (Middle配置) | 缺乏自适应 Gram 矩阵跟踪，在退化几何下样本分流滞后 |

关键发现¶

在低维子空间流形退化机制（Low 和 Middle 场景）下，SupSplitLog 相较于传统基于分集假设的算法展现出压倒性优势，累积遗憾相比 SupCB-GLM 与 SupLogistic 下降达 70% 至 80% 以上。这是因为传统方法必须耗费 $O(d\sqrt{T})$ 轮次执行无差别的均匀随机探索来撑大最小特征值，而在退化空间中这种探索是极度浪费且有害的。
在特征充满全维空间的 High 场景中，尽管 DDRTS-GLM 依靠汤普森采样的平滑后验更新取得略微领先的数值表现，但 SupSplitLog 紧随其后且无需任何理论分集保证，完全规避了 DDRTS-GLM 理论分析所需的 $\sigma_0^{-2} = \Omega(d)$ 强假设。
随环境维度 $d$ 从 20 跃升至 100，在 Low 流形下 SupSplitLog 的累积遗憾仅从 5.4 微弱上升至 6.1，实证充分印证了理论中以数据依赖测度 $\tilde{d}$ 替代外在环境维数 $d$ 的重大优越性。

亮点与洞察¶

半参数单步牛顿校正与在线样本分割的有机融合：创新性地利用引导集解耦海森矩阵参数与估计集奖励噪声的统计关联，在不丢失二阶曲率加速特性的同时，彻底扫清了将纯标量 Bernstein 集中不等式应用于非线性模型的理论障碍。
自适应数据依赖界弥合了高维与流形假设：通过动态对数行列式统计量 $\tilde{d}$ 门控探索样本分配，使算法在完全无需事先指定低维子空间维数或基底的情况下，自适应退化到有效几何流形，拓宽了逻辑老虎机在高维表征中的理论可用性。
摆脱强制均匀随机预探索的统计浪费：以往算法为了满足 $\lambda_{\min} > \sigma_0^2$ 必须人为强插 $\tau = \sqrt{dT}$ 轮纯随机动作采样，SupSplitLog 首次做到在在线序贯决策首日即进行定向保护性探索，大幅提升了冷启动阶段的数据利用效率。

局限与展望¶

高阶遗憾项中维度依赖偏高：虽然主导前导项达到了最优的 $\kappa\sqrt{dT}$，但非前导残差项中包含 $\kappa^{2.5} d^{2.5}$，在极小样本区间（$T \ll d^4$）且特征为满秩高维时，常数上界依然较为保守。
实例相关常数 $\kappa$ 的多项式依赖：界中仍包含 $O(\kappa)$ 的放大因子，当奖励接近极值（即参数模长较大导致局部方差极小）时，遗憾界增长显著，未来需要结合自协调分析（Self-concordance）进一步精细化 $\kappa$ 依赖。
动作规模 $K$ 的扩展性：算法当前在 Auer 框架下依赖逐级消除法处理有限 $K$ 臂问题，尚未能直接无缝推广到具有紧致凸动作集的连续无穷臂（Infinite-armed）逻辑赌博机设置。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破长期存在的上下文多样性假设，通过单步牛顿样本分割巧妙隔离统计相关性，理论构造极具启发性。
实验充分度: ⭐⭐⭐⭐ 提供了详尽的多维几何退化环境模拟实验，能够精准检验数据依赖复杂度上界，若能补充真实世界二值反馈点击基准将更完整。
写作质量: ⭐⭐⭐⭐⭐ 概念动机铺垫层层递进，技术难点解构清晰，定理证明与误差项拆解逻辑严密自洽。
价值: ⭐⭐⭐⭐⭐ 彻底解决了有限臂逻辑老虎机领域长期悬而未决的 $\tilde{O}(\sqrt{dT})$ 分集假设瓶颈，为核化与神经非线性老虎机扩展铺平了理论道路。

实验场景配置	结构复杂度 (\(\log\frac{\det\mathbf{V}_T}{\det\kappa\lambda\mathbf{I}}\))	SupSplitLog (本文)	SupCB-GLM	SupLogistic	DDRTS-GLM	相对最佳基线提升
\(d=20\), Low 几何 (\(r=2\))	极低（约 0.5 - 2）	\(5.4 \pm 1.2\)	\(28.6 \pm 4.5\)	\(24.1 \pm 3.8\)	\(18.2 \pm 3.1\)	70.3% 降低
\(d=20\), Middle 几何 (\(r=10\))	中等（约 15 - 25）	\(16.8 \pm 2.9\)	\(54.2 \pm 6.1\)	\(46.7 \pm 5.4\)	\(23.5 \pm 3.7\)	28.5% 降低
\(d=20\), High 几何 (\(r=20\))	满秩扩展（约 45 - 60）	\(42.1 \pm 5.2\)	\(88.4 \pm 9.2\)	\(79.3 \pm 8.6\)	\(39.7 \pm 4.8\)	性能相当 (相差~6%)
\(d=100\), Low 几何 (\(r=2\))	极端低维（约 0.5 - 3）	\(6.1 \pm 1.4\)	\(142.5 \pm 16.8\)	\(118.2 \pm 14.1\)	\(32.4 \pm 5.1\)	81.2% 降低
\(d=100\), Middle 几何 (\(r=10\))	稀疏退化（约 18 - 30）	\(21.4 \pm 3.5\)	\(230.1 \pm 21.4\)	\(195.4 \pm 18.9\)	\(48.6 \pm 6.3\)	55.9% 降低
\(d=100\), High 几何 (\(r=100\))	高维均匀（约 160 - 200）	\(96.5 \pm 8.7\)	\(380.6 \pm 34.2\)	\(315.2 \pm 28.7\)	\(88.2 \pm 7.9\)	处于同一竞争力区间

Logistic Bandits with \(\tilde{O}(\sqrt{dT})\) Regret without Context Diversity Assumptions¶

一句话总结¶

研究背景与动机¶

方法详解¶

整体框架¶

关键设计¶

损失函数 / 训练策略¶

实验关键数据¶

主实验¶

消融实验¶

关键发现¶

亮点与洞察¶

局限与展望¶

相关工作与启发¶

评分¶

Logistic Bandits with \(\tilde{O}(\sqrt{dT})\) Regret without Context Diversity Assumptions¶

一句话总结¶

研究背景与动机¶

方法详解¶

整体框架¶

关键设计¶

损失函数 / 训练策略¶

实验关键数据¶

主实验¶

消融实验¶

关键发现¶

亮点与洞察¶

局限与展望¶

相关工作与启发¶

评分¶

相关论文¶