Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update¶

会议: NeurIPS 2025 arXiv: 2507.11847 代码: 无领域: 强化学习 关键词: 广义线性赌博机, 在线学习, 置信集, 在线镜像下降, 混合损失

一句话总结¶

提出GLB-OMD算法，首次在广义线性赌博机（GLB）问题中同时实现近似最优遗憾界 $\mathcal{O}(\log T\sqrt{T/\kappa_*})$ 和每轮 $\mathcal{O}(1)$ 的时间/空间复杂度，核心技术是基于混合损失（mix loss）为在线镜像下降（OMD）估计量构建紧致置信集。

研究背景与动机¶

广义线性赌博机（GLB）是上下文多臂赌博机框架的重要扩展，通过引入非线性链接函数 $\mu$ 建模更丰富的奖励分布（如Bernoulli、Poisson）。在实际应用中，GLB广泛适用于推荐系统、个性化医疗、动态定价等场景。

GLB的核心挑战在于计算效率和统计效率的权衡： - 统计效率：经典GLM-UCB算法的遗憾界包含 $\kappa = 1/\inf \mu'$ 这一潜在指数大的常数，例如在logistic bandit中 $\kappa = \mathcal{O}(e^S)$ - 计算效率：基于最大似然估计（MLE）的方法需要 $\mathcal{O}(t)$ 的每轮时间和空间复杂度

现有方法要么计算高效但统计不优（GLOC），要么统计最优但计算昂贵（OFUGLB、RS-GLinCB）。本文的目标是设计联合高效的算法——同时实现最优遗憾和常数计算代价。

方法详解¶

整体框架¶

GLB-OMD算法基于"面对不确定性的乐观主义"（OFU）原则。每轮 $t$： 1. 基于OMD估计量 $\theta_t$ 构建椭球置信集 $\mathcal{C}_t(\delta)$ 2. 选择使UCB最大的臂 $X_t = \arg\max_{\mathbf{x}} \{\mathbf{x}^\top \theta_t + \beta_t(\delta) \|\mathbf{x}\|_{H_t^{-1}}\}$ 3. 观察奖励后用OMD更新估计量

关键创新在于用OMD替代MLE作为参数估计器，并为其构建与MLE同等紧致的置信集。

关键设计¶

在线镜像下降（OMD）估计量¶

每轮更新规则： $$\theta_{t+1} = \arg\min_{\theta \in \Theta} \tilde{\ell}_t(\theta) + \frac{1}{2\eta}\|\theta - \theta_t\|^2_{H_t}$$

其中 $\tilde{\ell}_t(\theta)$ 是原始损失的二阶近似（保留曲率信息但可高效求解），$H_t = \lambda I_d + \sum_{s=1}^{t-1} \nabla^2 \ell_s(\theta_{s+1})$ 是累积曲率矩阵。

计算优势：优化问题是欧氏球上的二次优化，复杂度 $\mathcal{O}(d^3)$，与时间 $t$ 无关。$H_t$ 可增量更新（$H_{t+1} = H_t + \nabla^2 \ell_t(\theta_{t+1})$），无需存储历史数据。

基于混合损失（Mix Loss）的置信集¶

关键的技术贡献是分析OMD估计量的逆遗憾（inverse regret）。逆遗憾定义为 $\sum \ell_s(\theta_*) - \sum \ell_s(\theta_{s+1})$，其上界直接决定置信集半径。

传统方法引入中间Online Learning算法 $\tilde{\theta}_s$ 进行分解，但这在GLB设置中难以统一。本文使用混合损失作为中间项： $$m_s(P_s) = -\ln\left(\mathbb{E}_{\theta \sim P_s}[e^{-\ell_s(\theta)}]\right)$$

两步分析： 1. Lemma 2（Ville不等式）：$\sum \ell_s(\theta_*) - \sum m_s(P_s) \leq \log(1/\delta)$，以高概率成立 2. Lemma 3：选择 $P_s = \mathcal{N}(\theta_s, \frac{3}{2}\eta H_s^{-1})$ 为以OMD估计量为中心的高斯分布，可控制 $\sum m_s(P_s) - \sum \ell_s(\theta_{s+1})$

最终置信集（Theorem 1）：$\mathcal{C}_t^{\text{OL}}(\delta) = \{\theta \mid \|\theta - \theta_t\|_{H_t} \leq \beta_t(\delta)\}$，半径 $\beta_t(\delta) = \mathcal{O}(SR\sqrt{d(S^2R + \ln(t/\delta))})$，不依赖 $\kappa$。

损失函数 / 训练策略¶

损失函数：GLM的负对数似然 $\ell_t(\theta) = (m(X_t^\top \theta) - r_t \cdot X_t^\top \theta)/g(\tau)$，其中 $m$ 是对数配分函数。

自协调性假设（Assumption 3）：$|\mu''(z)| \leq R \cdot \mu'(z)$，适用于Bernoulli ($R=1$)、Poisson ($R=1$)、Gaussian ($R=0$) 等常见分布。这是利用链接函数局部曲率改善 $\kappa$ 依赖的关键条件。

遗憾界（Theorem 2）： $$\text{Reg}_T \lesssim dSR\sqrt{S^2R + \log T} \cdot \sqrt{\frac{T\log T}{\kappa_*}} + \kappa d^2 S^2 R^3 \log T (S^2R + \log T)$$

主导项为 $\tilde{\mathcal{O}}(d\sqrt{T/\kappa_*})$，非主导项仍依赖 $\kappa$ 但为低阶项。

实验关键数据¶

主实验（Logistic Bandit）¶

方法	$S=3$（$\kappa=21$）遗憾	$S=5$（$\kappa=137$）遗憾	每轮时间
GLOC	高	很高	最快
GLM-UCB	中高	高	$\mathcal{O}(t)$
OFUGLB	最低	最低	最慢（$\mathcal{O}(t)$）
RS-GLinCB	低	低	随 $\kappa$ 增长
ECOLog	低	低	$\mathcal{O}(\log t)$
GLB-OMD	低（接近OFUGLB）	低	$\mathcal{O}(1)$

Poisson Bandit（无界奖励）：

方法	$S=3$ 运行时间相对OFUGLB	遗憾增幅
GLB-OMD	~1/1000	仅modest增加
OFUGLB	1x（基准）	基准

消融实验¶

$\kappa$ 依赖：当 $S$ 从3增大到7时（$\kappa$ 从21增到963），GLB-OMD保持常数每轮代价，而RS-GLinCB的更新频率随 $\kappa$ 增长
与logistic bandit专用方法对比（Table 2）：GLB-OMD同时改善了ECOLog的 $\mathcal{O}(\log t)$ 时间复杂度和OFUL-MLogB的 $\mathcal{O}(\sqrt{\log T})$ 遗憾额外因子

关键发现¶

GLB-OMD在计算效率和统计效率之间取得最优平衡
OMD估计量即使是one-pass更新，也能匹配MLE的统计效率
非线性链接函数不必然导致更高计算代价——GLB-OMD的每轮代价与LinUCB相同
Covertype真实数据集上的表现与合成数据一致

亮点与洞察¶

混合损失（Mix Loss）的巧妙运用：引入在线预测中的mix loss概念到bandit置信集构建，提供了比直接分解更灵活的分析框架
时变高斯桥接：选择以OMD估计量为中心的时变高斯分布作为mix loss的参考分布，巧妙适配了OMD的在线特性
统一框架：之前logistic bandit的方法依赖特定的logistic结构，本文通用于所有满足自协调性的GLM
实用价值：常数空间复杂度意味着算法可直接部署在资源受限的在线场景

局限性 / 可改进方向¶

主导项中仍有 $S^2$ 依赖，MLE方法已可完全消除（Lee et al., 2024）
非主导项仍线性依赖 $\kappa$，可能通过warm-up策略改善至 $\kappa_\mathcal{X}$
是否能获得类似logistic bandit的geometry-aware界仍是开放问题
可探索放松自协调性假设或改善有限臂设置中的 $d$ 依赖
结合OMD与rare-update技术可能进一步加速

评分¶

创新性: ★★★★★ — 首次在GLB中实现计算+统计联合最优
实验充分性: ★★★★☆ — 覆盖logistic、Poisson和真实数据
实用价值: ★★★★★ — $\mathcal{O}(1)$ 代价对在线系统极有价值
写作质量: ★★★★★ — 理论严谨，脉络清晰