新算法让带噪声和干扰的线性上下文老虎机更稳健且更快。
Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise
- 用在线镜面下降设计高效算法，每轮计算仅需常数时间。
- 在存在对抗性干扰和重尾噪声时，实现次线性累积损失增长。
- 无需提前知道噪声强度或干扰总量，适合实际部署场景。
研究在对抗性污染和具有有限(1+ε)阶矩（ε∈(0,1]）的重尾噪声下的线性上下文老虎机问题。现有方法依赖有限方差假设且计算效率低。本文提出一种基于在线镜面下降的高效算法，每轮计算复杂度仅为O(1)，远优于现有O(t log T)的代价。我们建立了包含噪声(1+ε)阶矩项和总污染量项的加法型累积遗憾界。当ε=1时，恢复有限方差情形下的已有结果；无污染时，达到重尾噪声下最优已知率。算法无需预先知晓噪声矩或污染总量，仍能保证次线性遗憾。
原文摘要 · Abstract (English)
We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite $(1+ε)$-th moments for some $ε\in (0,1]$. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance (i.e., finite second-moment) assumption and suffers from computational inefficiency. We propose a computationally efficient algorithm based on online mirror descent that achieves robustness to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs $\mathcal{O}(t\log T)$ computational cost, our algorithm reduces this to $\mathcal{O}(1)$ per round. We establish an additive regret bound consisting of a term depending on the $(1+ε)$-moment bound of the noise and a term depending on the total amount of corruption. In particular, when $ε= 1$, our result recovers existing guarantees under finite-variance assumptions. When no corruption is present, it matches the best-known rates for linear contextual bandits with heavy-tailed noise. Moreover, the algorithm requires no prior knowledge of the noise moment bound or the total amount of corruption and still guarantees sublinear regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。