提出仅需极少数更新的高效线性上下文老虎机算法，兼顾最优性能与实际计算效率。
Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
- 设计两种仅需O(log log T)次参数更新的算法，实现理论最优后悔率。
- 新算法在静态调度下同时适用于小和大更新次数场景，且运行时间最低。
- 适合关注低频更新与高计算效率的在线决策研究者使用。
我们研究在稀疏参数更新下的线性上下文老虎机问题：学习者只能在少量更新时刻利用奖励反馈更新参数，但仍需在线观察上下文并顺序选择动作。这一设定澄清了文献中常被混淆的实际区别——许多‘严格批处理’方法还额外限制区间内的上下文自适应性，即区间内动作策略不能依赖于该区间内历史上下文/动作序列（仅限当前轮次上下文）。针对线性上下文老虎机，我们提出两种实用算法，仅需 O(log log T) 次参数更新。首个算法 BLCE-G 在静态调度下，于小更新次数与大更新次数场景均达到最小最大后悔率（至多多项式对数因子）。第二个算法 BLCE 去除了先前严格批处理方法中的近 G-最优设计步骤——这是主要计算瓶颈——但仍保持最小最大后悔率，并实现了已知最优算法中的最低运行时复杂度。我们将这些稀疏更新与计算原则扩展至广义线性上下文老虎机。总体而言，我们的结果在仅 O(log log T) 次更新下，为线性上下文老虎机提供了最小最大最优算法，并为广义线性情形提供了近最优扩展，同时保持实际计算高效。
原文摘要 · Abstract (English)
We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many "strictly batched" methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only $O(\log\log T)$ parameter updates. Our first algorithm BLCE-G attains minimax-optimal regret (up to polylogarithmic factors in $T$) simultaneously in both the small-$K$ and large-$K$ regimes under a static schedule. Our second algorithm BLCE removes the near G-optimal design step -- a dominant computational bottleneck in prior strictly batched static-grid methods -- yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield minimax-optimal algorithms for linear contextual bandits and a near-optimal generalized-linear extension under $O(\log\log T)$ parameter updates, while remaining computationally efficient in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。