提出一种高效在线更新的重尾线性老虎机算法。
Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
- 基于在线镜方法设计单次遍历更新机制
- 计算复杂度从O(t log T)降至O(1)，近似最优且自适应方差
- 适合高维、噪声分布不规则的在线决策场景
研究带有重尾噪声的随机线性老虎机问题。现有处理重尾噪声的方法如截断和中位数均值，依赖特定噪声假设或老虎机结构，适用性受限。近期工作[黄等, 2024]通过自适应Huber回归引入软截断，但需存储全部历史数据并在每轮进行全遍历，导致计算开销大。本文提出基于在线镜方法的单次遍历算法，每轮仅用当前数据更新，将每轮计算复杂度从O(t log T)降至O(1)，在维度d、时间范围T下达到近似最优且自适应方差的损失界：~O(d T^{(1−ε)/(2(1+ε))} √∑_{t=1}^T ν_t² + d T^{(1−ε)/(2(1+ε))})，其中ν_t^{1+ε}为第t轮回报的(1+ε)-阶中心矩。
原文摘要 · Abstract (English)
We study the stochastic linear bandits with heavy-tailed noise. Two principled strategies for handling heavy-tailed noise, truncation and median-of-means, have been introduced to heavy-tailed bandits. Nonetheless, these methods rely on specific noise assumptions or bandit structures, limiting their applicability to general settings. The recent work [Huang et al.2024] develops a soft truncation method via the adaptive Huber regression to address these limitations. However, their method suffers undesired computational costs: it requires storing all historical data and performing a full pass over these data at each round. In this paper, we propose a \emph{one-pass} algorithm based on the online mirror descent framework. Our method updates using only current data at each round, reducing the per-round computational cost from $\mathcal{O}(t \log T)$ to $\mathcal{O}(1)$ with respect to current round $t$ and the time horizon $T$, and achieves a near-optimal and variance-aware regret of order $\widetilde{\mathcal{O}}\big(d T^{\frac{1-ε}{2(1+ε)}} \sqrt{\sum_{t=1}^T ν_t^2} + d T^{\frac{1-ε}{2(1+ε)}}\big)$ where $d$ is the dimension and $ν_t^{1+ε}$ is the $(1+ε)$-th central moment of reward at round $t$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。