Optimal and Practical Batched Linear Bandit Algorithm¶

会议: ICML 2025
arXiv: 2507.08438
代码: 待确认
领域: 强化学习 / Bandit
关键词: 批量线性 Bandit, 臂消除, 正则化 G-最优设计, 极小极大最优, 有限自适应性

一句话总结¶

BLAE 通过将臂消除策略与正则化 G-最优设计深度融合，首次在批量线性 Bandit 问题中同时实现了 large-\(K\) 和 small-\(K\) 两种体制下的极小极大最优遗憾（仅差 \(\log T\) 因子），同时保持 \(\mathcal{O}(\log\log T)\) 的最低批次复杂度和卓越的实际性能。

研究背景与动机¶

问题定义¶

随机线性 Bandit 是序列决策的经典框架：智能体从 \(K\) 个嵌入在 \(d\) 维特征空间的臂中反复选择，每轮获得含噪线性奖励 \(r_t = \langle x_t, \theta^* \rangle + \eta_t\)，目标是最小化累积遗憾 \(\mathcal{R}(T) = \mathbb{E}\left[\sum_{t=1}^T \left(\langle x^*, \theta^* \rangle - \langle x_t, \theta^* \rangle\right)\right]\)。

在批量（batched）设定下，\(T\) 轮被划分为 \(B\) 个不相交批次，策略更新只在批次边界发生——这直接建模了推荐系统、临床试验等场景中不宜频繁更新策略的实际约束。

现有方法的困境¶

尽管理论上已有若干算法可达到近最优遗憾，但它们在实践中各有痛点：

计算不可行：Ruan et al. (2021)、Hanna et al. (2023)、Zhang et al. (2025) 的算法源自 contextual（时变特征）设定，含有为时变场景定制的子程序；在固定特征的 plain linear bandit 上无法利用静态结构，中等规模问题即无法运行

批次过多：Abbasi-Yadkori et al. (2011) 的 rare-switching OFUL 需要 \(\mathcal{O}(d\log T)\) 批次，Esfandiari et al. (2021) 需要 \(\mathcal{O}(\log T)\) 批次——仍显过多

臂过早消除：Ren et al. (2024) 的方法常在早期就错误地消除最优臂，且对超参数 \(\gamma\) 极为敏感，选择不当会使第三批膨胀至 \(\mathcal{O}((\log T)^{1+\gamma})\)，耗尽整个时间窗口

体制盲区：此前无算法能同时在 large-\(K\)（\(K \geq \Omega(e^d)\)）和 small-\(K\)（\(K \leq \mathcal{O}(e^d)\)）两种体制下匹配各自的遗憾下界

核心问题：能否设计一个理论上极小极大最优、实践中也表现优越的批量线性 Bandit 算法？

方法详解¶

整体框架：BLAE 算法¶

BLAE（Batched Linear bandit Algorithm with Elimination）的核心思路是将逐批臂消除与正则化 G-最优试验设计有机结合。算法在 \(\mathcal{O}(\log\log T)\) 个批次中运行，每个批次执行以下步骤：

构建置信集合：基于当前数据估计 \(\hat{\theta}\)，并构建参数的置信椭球
臂消除：利用置信上下界剔除"必然次优"的臂——若某个臂的期望奖励上界低于当前最佳臂的下界，则永久消除
正则化 G-最优设计：在存活臂集合上求解一个正则化的 G-最优设计问题，得到各臂的最优分配比例
按比例采样：在该批次中按设计比例分配各臂的拉取次数，收集观测数据
参数更新：利用新数据更新 \(\hat{\theta}\) 和信息矩阵 \(V\)

批次大小呈双指数增长（\(T_m \propto T^{2^{-m}}\) 的递推结构），使得总批次数为 \(\mathcal{O}(\log\log T)\)。

关键设计¶

正则化 G-最优设计¶

标准 G-最优设计旨在最小化所有臂上的最大预测方差：

\[\min_{\pi \in \Delta_K} \max_{k \in [K]} \| x^{(k)} \|^2_{H(\pi)^{-1}}, \quad H(\pi) = \sum_k \pi_k x^{(k)} x^{(k)\top}\]

但在批量设定下，存活臂集合逐批缩小，信息矩阵可能变得病态。BLAE 引入正则化：

\[H_\lambda(\pi) = \sum_k \pi_k x^{(k)} x^{(k)\top} + \lambda I\]

正则化参数 \(\lambda\) 确保信息矩阵始终良定义，并允许分析从一个批次到下一个批次的平滑过渡，避免 warm-start 问题。

批次间最优设计的递推分析¶

传统分析将每个批次视为独立的最优设计问题。BLAE 的关键技术创新在于跨批次的最优设计分析（Lemma 3）：利用上一批次积累的信息矩阵作为下一批次的正则项，建立了批次间信息积累的精细递推关系，从而获得比逐批独立分析更紧的界。

精细集中不等式¶

为同时处理批处理和正则化带来的依赖结构，作者发展了两个新的集中不等式（Lemma 1, 2），分别刻画：

正则化最小二乘估计 \(\hat{\theta}\) 到真参数 \(\theta^*\) 的偏差上界
在 G-最优设计分配下，信息矩阵方差项的精细控制

这些技术工具同时适用于批量与非批量 Bandit 研究。

高效单位球覆盖¶

为处理 large-\(K\) 体制（\(K \geq \Omega(e^d)\)），算法需要一个高效的单位球 \(\epsilon\)-覆盖来约束搜索空间。Lemma 8 提供了覆盖大小的改进上界，既保证理论保证也改善实际性能。

理论分析¶

Theorem 1（主定理）：BLAE 在使用 \(\mathcal{O}(\log\log T)\) 个批次的情况下，其最坏情况累积遗憾满足：

\[\mathcal{R}(T) = \mathcal{O}\left(\sqrt{dT}\left(\sqrt{\log(KT)} \wedge \sqrt{d + \log T}\right) \log\log T\right)\]

这一界的关键特性：

small-\(K\) 体制（\(K \leq \mathcal{O}(e^d)\)）：遗憾为 \(\mathcal{O}(\sqrt{dT\log K} \cdot \log\log T)\)，匹配下界 \(\Omega(\sqrt{dT\log K})\)（Zhou, 2019）
large-\(K\) 体制（\(K \geq \Omega(e^d)\)）：遗憾为 \(\mathcal{O}(d\sqrt{T} \cdot \log\log T)\)，匹配下界 \(\Omega(d\sqrt{T})\)（Dani et al., 2008）
两体制统一：通过取 \(\min\) 操作 \(\wedge\) 自动适应两种体制，无需预知 \(K\) 与 \(d\) 的关系

实验关键数据¶

遗憾界与批次复杂度对比¶

方法	最坏遗憾	批次复杂度	实际可行性
Abbasi-Yadkori et al. (2011)	\(\mathcal{O}(d\sqrt{T}\log T)\)	\(\mathcal{O}(d\log T)\)	批次过多
Esfandiari et al. (2021)	\(\mathcal{O}(\sqrt{dT\log(KT)})\)	\(\mathcal{O}(\log T)\)	批次偏多
Ruan et al. (2021)	\(\mathcal{O}(\sqrt{dT\log(dKT)\log d}\log\log T)\)	\(\mathcal{O}(\log\log T)\)	计算量大
Hanna et al. (2023)	\(\mathcal{O}(d\sqrt{T\log T}\log\log T)\)	\(\mathcal{O}(\log\log T)\)	计算量大
Ren et al. (2024)	\(\mathcal{O}(\sqrt{dT\log(KT)}\log\log T)\)	\(\mathcal{O}(\log\log T)\)	易过早消除最优臂
Zhang et al. (2025)	\(\mathcal{O}(\sqrt{dT\log(dKT)\log T}\log(dT)\log\log T)\)	\(\mathcal{O}(\log\log T)\)	计算量大
BLAE（本文）	\(\mathcal{O}(\sqrt{dT}(\sqrt{\log(KT)} \wedge \sqrt{d+\log T})\log\log T)\)	\(\mathcal{O}(\log\log T)\)	低计算开销
下界 (Dani et al., 2008)	\(\Omega(d\sqrt{T})\)	—	large-\(K\)
下界 (Zhou, 2019)	\(\Omega(\sqrt{dT\log K})\)	—	small-\(K\)

数值实验性能对比¶

论文在多种设定（不同 \(d\)、\(K\)、\(T\) 组合）下进行了广泛的数值实验。BLAE 在所有测试场景中一致且大幅优于现有方法：

实验维度	BLAE 表现	对比方法表现	优势说明
固定 \(d=5, K=20\)	最低累积遗憾	Ren et al. 遗憾显著偏高	Ren 过早消除最优臂
增大 \(K\) (large-\(K\))	遗憾稳定增长	多数方法遗憾急剧增长	G-最优设计有效控制方差
增大 \(d\)	遗憾平缓增长	Ruan/Hanna/Zhang 计算超时	低计算开销优势凸显
不同 \(T\) 值	与理论 \(\sqrt{T}\) 趋势吻合	部分方法偏离理论预期	理论与实践一致
实际批次数	极少（\(\sim\log\log T\)）	Esfandiari 需数十倍批次	真正的低自适应性
运行时间	秒级	Ruan/Zhang 可达小时级	中等规模问题即体现差距

亮点与洞察¶

理论-实践统一：BLAE 是首个同时做到极小极大最优遗憾（两个体制）与实际性能卓越的批量线性 Bandit 算法，打破了"理论最优 ≠ 实际好用"的常见困境
体制自适应：通过 \(\wedge\)（取 \(\min\)）操作自然适应 large-\(K\) / small-\(K\) 两种体制，无需先验知识或体制检测
计算可行性：避免了为 contextual 设定定制的重型子程序（如分阶段估计-策略更新），在固定特征设定下充分利用静态结构，实现了低计算开销
正则化的关键作用：正则化不仅是技术手段（保证矩阵可逆），更是实现跨批次信息积累分析的核心杠杆——这一洞见可推广到其他在线学习问题
消除策略的稳健性：相比 Ren et al. 的激进消除，BLAE 的消除更保守——结合 G-最优设计的方差控制，有效避免了过早剔除最优臂的致命错误

局限与展望¶

固定特征假设：BLAE 针对固定特征（plain linear bandit）设计和优化，未直接处理 contextual 设定中的时变特征；推广到时变特征需要额外机制
\(\log\log T\) 因子：虽然批次复杂度已达 \(\mathcal{O}(\log\log T)\) 的最低水平，但遗憾界中仍含 \(\log\log T\) 因子，能否完全消除仍是开放问题
有限臂集合：算法假设有限臂集合 \(K < \infty\)，对于连续臂空间的线性 Bandit（如 \(\mathcal{A} = \{x : \|x\| \leq 1\}\)）需要通过覆盖网离散化，可能引入额外损耗
G-最优设计的求解：需要求解凸优化问题，虽然计算量远低于对手方法，但在超大 \(K\) 场景下仍可能成为瓶颈
噪声模型：假设 \(\sigma\)-sub-Gaussian 噪声，对重尾噪声或异方差场景的适用性有待验证

评分¶

维度	分数 (1-10)	说明
新颖性	8	正则化 G-最优 + 臂消除的融合设计原创，两体制统一最优为首次
技术深度	9	跨批次最优设计分析、新集中不等式等技术工具扎实
实验充分度	8	多维度全面对比，计算效率对比尤为有说服力
实用价值	8	低计算开销+强实际表现，可直接部署于推荐/临床试验等场景
写作质量	8	问题动机清晰，理论-实验对应关系好，Table 1 一目了然
综合	8.2	理论与实践的完美统一，首次在批量线性 Bandit 中兼顾两体制最优性和实用性