技术摘要：针对稀疏参数更新的线性上下文多臂老虎机实用且最优算法

1. 问题设定

本文研究了在稀疏参数更新约束下的**随机线性上下文多臂老虎机（stochastic linear contextual bandits）**问题。在此设定下，智能体在随时间变化的 $K$ 个臂的集合中顺序选择动作（臂），每个臂由一个 $d$ 维特征向量表征。奖励由一个未知的线性模型 $\theta^*$ 加上噪声生成。

核心约束在于，学习者只能在极少数的更新时刻 $B$ 将奖励反馈纳入其参数估计（例如，通过岭回归或极大似br 似估计 MLE）。至关重要的是，作者将其与严格批处理（strictly batched）设定进行了区分。虽然奖励在间隔结束时才延迟交付，但作者认为，在实际部署中，上下文是在选择动作之前被观测到的。因此，学习者应当被允许进行间隔内的无奖励适应性更新（例如，基于观测到的上下文更新 Gram 矩阵或消除集合），即使沉重的参数重训练被延迟了。这种区分弥补了全顺序方法与禁止间隔内适应性的严格批处理方法之间的鸿沟。

目标是设计能够实现以下目标的算法：

1. 在小 $K$（$K \le O(ed)$）和高 $K$（$K \ge \Omega(ed)$）两种情形下均达到极小极大最优遗憾（minimax-optimal regret）。
2. 仅进行 $O(\log \log T)$ 次参数更新。
3. 避免计算昂贵的方法子程序，特别是 G-最优设计（G-optimal design），这曾是先前严格批处理最优算法的瓶颈。

2. 方法论

本文提出了两种用于线性上下文老虎机的算法以及一种用于广义线性老虎机的扩展算法。

BLCE-G (结合消除与 G-最优设计的批处理反馈线性上下文老虎机)

该算法将臂消除法与近 G-最优设计策略相结合。

• 结构： 它基于静态的时间间隔网格运行。
• 机制： 在每个间隔内，轮次被分为若干阶段。第一阶段利用近 G-最优设计来采样臂，以确保足够的信息增益。随后的阶段涉及选择相对于当前 Gram 矩阵最具信息量的方向，最后进行基于最新估计的贪婪选择。
• 消除： 利用来自先前间隔的估计值迭代地消除次优臂。
• 复杂度： 它保留了 G-最优设计的理论紧凑性，但将其放宽为可通过 Sherman-Morrison 公式在 $O(Kd^3)$ 内计算的近最优版本。

BLCE (具有消除机制的批处理反馈线性上下文老虎机)

该算法完全移除了 G-最优设计步骤以提高计算效率。

• 结构： 与 BLCE-G 具有类似的静态间隔网格和臂消除框架。
• 机制： BLCE 不依赖 G-最优设计，而是依靠不确定性驱动的探索（选择在逆 Gram 矩阵中范数最大的臂），并结合臂消除。为了补偿缺乏显式设计的缺陷，探索阶段被相应延长。
• 意义： 这是第一个在无需依赖 G-最优设计的情况下，在稀疏更新设定下实现极小极大最优性的线性上下文老虎机算法，将时间复杂度降低至 $O(Kd^2 T \log \log T)$。

BGLE (具有消除机制的批处理反馈广义线性上下文老虎机)

该算法将 BLCE 的原理扩展到广义线性奖励（指数族分布）。

• 机制： 它在间隔边界使用极大似然估计（MLE），并在探索期间使用加权 Gram 矩阵来处理非线性。
• 关键特性： 其遗憾界限独立于最差情况下的曲率参数 $\kappa$，而是依赖于平均逆曲率 $\hat{\kappa}$。

3. 核心贡献

本文做出了以下具体贡献：

1. 稀疏更新下最紧凑的遗憾界限： 作者引入了 BLCE-G，它在小 $K$ 和高 $K$ 情形下均能实现极小极大最优遗憾（忽略多项式对数因子），且仅需 $O(\log \log T)$ 次参数更新。这匹配了已知的极小极大下界 $\Omega(\sqrt{dT} \log K)$ 和 $\Omega(d\sqrt{T})$。
2. 无需 G-最优设计的最优性： BLCE 被证明是第一个在稀疏更新设定下，无需依赖计算昂贵的 G-最优设计步骤即可实现极小极大最优遗憾的算法。它实现了已知最优算法中最低的时间复杂度。
3. 重新定义适应性图景： 本文明确分类并区分了三种操作设定：
   • 全顺序（Fully Sequential）： 每轮进行完全适应。
   • 严格批处理（Strictly Batched）： 无间隔内上下文适应性（动作规则在间隔开始时即固定）。
   • 稀疏参数更新（Rare Parameter Updates）： 限制了依赖奖励的更新，但允许无奖励的间隔内适应性。
     作者认为，“稀疏参数更新”是一个实用的范畴，它既避免了严格批处理的计算瓶颈，又保持了统计效率。
4. 广义线性扩展： 对广义线性老虎机（BGLE）的扩展提供了与最差情况曲率参数 $\kappa$ 无关的近最优遗憾保证，相比之下，先前工作的瞬态项依赖于 $\kappa$，这是一个显著的改进。
5. 实践优越性： 实验结果表明，所提算法在累积遗憾和运行时间方面均一致优于最先进的基准算法（如 RS-OFUL、BatchLinUCB-DG、SoftBatch），特别是在高维或大 $K$ 的设定下，先前的最优方法往往面临指数级或高多项式级的时间复杂度。

4. 结果

• 遗憾界限：
  • BLCE-G: $O(\sqrt{dT}(\sqrt{\log(KT)} \wedge \sqrt{d} + \log T)\sqrt{\log d \log \log T})$。
  • BLCE: $O(\sqrt{dT}(\sqrt{\log(KT)} \wedge \sqrt{d} + \log T)\sqrt{\log T \log \log T})$。
  • BGLE: 主项为 $O(RS\sqrt{d(d+\log T)T \log T \log \log T / \hat{\kappa}})$。
• 参数更新： 所有算法均以 $O(\log \log T)$ 次更新运行。
• 时间复杂度：
  • BLCE-G: $O(Kd^2 T (d + \log \log T))$。
  • BLCE: $O(Kd^2 T \log \log T)$。
  • BGLE: $O(Kd^2 T \log \log T + C_{opt}^{tot})$。
• 实证表现： 在 $T=10,000$ 的实验中，BLCE 和 BLCE-G 在各种 $(K, d)$ 对下均实现了最低的累积遗憾。BLCE 展示了最快的运行速度，通常与次优基准相当，而依赖于 G-最优设计的严格批处理最优方法则表现出“指数级”的运行时间或显著更高的成本。

5. 意义与主张

本文声称其结果统一了线性及广义线性上下文老虎机的理论与实践。其主要意义在于证明了有限的奖励适应性并不一定需要计算昂贵的预设探索计划。通过允许在间隔内进行轻量级的、无奖励的上下文处理，作者展示了实现以下目标的可行性：

• 保留稀疏更新算法的统计最优性。
• 消除阻碍严格批处理最优方法部署的主要计算瓶颈（G-最优设计）。
• 提供既具有理论完备性（极小极大最优）又具有实际高效性（低运行时间）的算法，使其适用于模型重训练成本高昂但上下文观测是连续的真实世界流水线。

作者对理论界限保持谦逊，指出虽然从理论上看 BLCE-G 具有更小的极小极大遗憾界限，但实验结果显示，在良性的随机环境中，BLCE 的表现往往相当甚至更好，这表明即使在稀疏更新的情况下，贪婪利用（greedy exploitation）也可能非常有效。