提出一种高效更新的广义线性博弈算法，近似最优地平衡计算与统计效率。
Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update
- 基于在线镜像下降的紧置信集设计，实现单次遍历更新
- 每轮时间空间复杂度均为常数，达到近乎最优后悔界
- 适合追求实时性与高精度的在线学习应用
我们研究广义线性博弈（GLB）问题，这是一种扩展经典线性模型的上下文多臂赌博机框架，通过引入非线性链接函数，可建模伯努利、泊松等广泛奖励分布。尽管GLB在现实场景中应用广泛，其非线性特性带来了计算与统计效率的双重挑战。现有方法通常在每轮高开销以获得最优后悔界，或牺牲统计性能换取常数时间更新。本文提出一种联合高效的算法，实现几乎最优的后悔界，且每轮时间与空间复杂度均为$/mathcal{O}(1)$。核心是通过在线预测中的混合损失概念，对在线镜像下降（OMD）估计器构建紧置信集。分析表明，即使采用单次遍历更新，该估计器的统计效率仍可媲美最大似然估计，从而导出一种联合高效的乐观方法。
原文摘要 · Abstract (English)
We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function, thereby modeling a broad class of reward distributions such as Bernoulli and Poisson. While GLBs are widely applicable to real-world scenarios, their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency. Existing methods typically trade off between two objectives, either incurring high per-round costs for optimal regret guarantees or compromising statistical efficiency to enable constant-time updates. In this paper, we propose a jointly efficient algorithm that attains a nearly optimal regret bound with $\mathcal{O}(1)$ time and space complexities per round. The core of our method is a tight confidence set for the online mirror descent (OMD) estimator, which is derived through a novel analysis that leverages the notion of mix loss from online prediction. The analysis shows that our OMD estimator, even with its one-pass updates, achieves statistical efficiency comparable to maximum likelihood estimation, thereby leading to a jointly efficient optimistic method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。