针对重尾噪声下的非线性多臂老虎机，提出高效低误差算法。
Nonlinear Bandit
- 基于在线镜面下降与自适应胡贝尔损失，设计一阶更新算法
- 实现近乎最优的 $ ilde{ m O}(T^{1/(1+ε)})$ 误差界
- 无需预知参数，适用于推荐、金融等真实场景
本文研究在重尾噪声下的广义线性多臂老虎机（GLB）问题。这类分布特征广泛存在于个性化推荐、金融市场和医疗治疗等实际应用中。基于在线镜面下降（OMD）方法，提出EHHM算法，结合单次遍历更新（对当前轮次 $t$ 和时间范围 $T$ 的计算复杂度为 $ m O(1)$），同时实现几乎最优的 $ ilde{ m O}(T^{1/(1+ε)})$ 误差上界。此外，利用某些链接函数的特殊性质，消除对常用参数的依赖。进一步研究上下文特征呈分段常数的情况，改进算法得PGLB-EHM，理论分析表明其误差界阶保持不变。针对非线性多臂老虎机（NB）的特例，引入二分法与特殊约束，提出NB-EHM算法。最终通过仿射提升方法，将一般性非线性多臂老虎机问题推广至可应用NB-EHM，并获得次线性误差边界。
原文摘要 · Abstract (English)
In this paper we first study the problem of generalized linear bandit (GLB) under heavy-tailed noise. The characteristics of heavy-tailed distributions are widely observed in real-world applications such as personalized recommendation, financial markets, and medical treatments. Based on the online mirror descent (OMD) method, we propose an algorithm EHM that extends the adaptive Huber loss method (Wang et al., 2025) with one-pass update ($\mathcal{O}(1)$ computational complexity with respect to current round $t$ and the time horizon $T$), which simultaneously achieves an almost optimal regret of $\widetilde{\mathcal{O}}(T^{\frac{1}{1+ε}})$ where $T$ is the time horizon. In addition, by utilizing a special property of some link function (Sawarni et al., 2025), our algorithm eliminates the need to know a commonly used parameter. Next, we study the GLB problem under the case when contextual characteristic becomes piecewise constant, and we slightly revised former algorithm to obtain the PGLB-EHM algorithm. After theoretical analysis, we prove that the regret upper bound order stays the same. Furthermore, we look deeper into a special case of nonlinear bandit (NB) and present the NB-EHM algorithm with bisection method and special restriction. Eventually we utilize the affine lifting approach and show that the general NB problem can be applied with NB-EHM to achieve a sublinear regret bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。