mlsanityData to 7 Oct 2026

Nonlinear Bandit

arXiv 2607.07304 ↗First posted 8 Jul 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 (O(1) computational complexity with respect to current round t and the time horizon T), which simultaneously achieves an almost optimal regret of widetildeO(T^frac11+ε) 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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 16 of its 42 references that are in the map. First posted on arXiv 8 Jul 2026.

Builds on

16 of 42 references.

References · 16

  1. 2018Neural Ordinary Differential Equationscited by 3,733
  2. 2019Introduction to Online Convex Optimizationcited by 793
  3. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  4. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 109
  5. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 63
  6. 2018Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffscited by 31
  7. 2021Regret Minimization in Heavy-Tailed Banditscited by 24
  8. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  9. 2024Bandit Convex Optimisationcited by 18
  10. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  11. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  12. 2017A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosiscited by 9
4 more
  1. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  2. 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
  3. 2024Stochastic Bandits with ReLU Neural Networkscited by 2
  4. 2021Empirical analysis of representation learning and exploration in neural kernel banditscited by 1

Built on by

Not cited yet.