Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
Authors: Jing Wang
Yu-Jie Zhang
Peng Zhao
Zhi-Hua Zhou
Venue: ICML 2025 poster (2025)
Keywords: heavy-tailed linear bandit
huber loss
Primary area: theory->online_learning_and_bandits

Abstract: 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] develop a soft truncation method via the adaptive Huber regression to address these limitations. However, their method suffers undesired computational cost: 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-\varepsilon}{2(1+\varepsilon)}} \sqrt{\sum_{t=1}^T \nu_t^2} + d T^{\frac{1-\varepsilon}{2(1+\varepsilon)}}\big)$ where $d$ is the dimension and $\nu_t^{1+\varepsilon}$ is the $(1+\varepsilon)$-th central moment of reward at round $t$.

Linear Bandits: Huber Regression with One-Pass Update
Jing Wang" Yu-Jie Zhang?
Peng Zhao 12 Zhi-Hua Zhou"
Abstract
However, in many real-world scenarios, the noise in data may follow a heavy-tailed distribution, such as in financial markets (Hull, 2012) and online advertising (Jebarajakirthy et al., 2021). This motivates the study of heavy-tailed linear bandits (HvtLB) (Medina & Yang. 2016; Shao et al., 201 8; Xue et al., 2020; Huang et al., 2023), where the noise π) in (1) satisfies that for some E (0, 1], v > 0,
We study the stochastic linear bandits with heavy- tailed noise. Two principled strategies for han- dling heavy-tailed noise, truncation and median- of of-means, have been introduced to heavy-tailed bandits. Nonetheless, these methods rely on spe- cific noise assumptions or bandit structures, lim- iting their applicability to general settings. The recent work (Huang et al., 2023) develops a soft truncation method via the adaptive Huber regres- sion 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 one-pass algorithm based on the online mirror descent framework. Our method updates using only current data each round, reducing the per-round computational cost from (1 log T) to ((1) with respect to current round t and the time horizon T', and achieves a near- optr-mltimal and variance-aware regret order ( Etn ot dl (ा where d is the dimension and ut is the (1 + s)-th central moment of reward at round t.
Eind = O, Bllmd |+] S l+c
(2)
To address heavy-tailed noise, statistical methods in estima- tion and regression often rely on two key principles: trunca- tion and median-of-means (MOM) (Lugosi Mendelson, 2019). Truncation methods handle outliers by directly re- moving extreme data points. Soft version truncation, such as Catoni's ' M-estimator (Catoni, 2012), reduces the impact of outliers by assigning them lower weights. This ensures ro- bust estimates while maintaining potentially valuable infor- mation from extreme data points. methods take a different approach by dividing the dataset into several groups, calculating the mean within each group, and then using the median of these group means as the final estimate. This method limits the influence of outliers to only few groups, preventing impact on the overall dataset.
(MOM)
For HvtLB, Shao et al. (2018) developed algorithms us- ing truncation and MOM- based least squares approach for parameter estimation, and achieved an (dT regret bound which is proven to be optimal. However, these ap- proaches have some notable issues: truncation methods require the assumption of bounded absolute moments for rewards, which cannot vanish in deterministic case, mak- ing them suboptimal in noiseless scenarios; MOM methods rely repeated arm pulling and assumption of fixed arm set, which makes them difficult to extend to more general settings. These limitations reveal that methods based on truncation and MOM heavily depend on specific assump- tions or the bandit structure. For broad decision-makin scenarios, such as online MDPs and adaptive control, where the state or context may vary dynamically, these assump- tions no longer hold. A more detailed discussion of these challenges is provided in Section 6.
1. Introduction
Stochastic Linear Bandits (SLB) models sequential decision- making process with linear structured reward distributions, which has been extensively studied in the literature (Dani et al., 2008; Abbasi- Yadkori et al., 201 1; Li et al., 2021b). Abbasi-Yadkori
Specifically, in SLB the observed reward at time is the inner product of the arm's 's feature vector X, and an unknown parameter 0., corrupted by sub- Gaussian noise Th, namely,
Ft = X, 0, + 7)-
(1)
National Key Laboratory for Novel Software Technol- ogy, Nanjing University, China "School of Artificial Intelli- gence, Nanjing University, China *Center for Advanced Intel- ligence Project, RIKEN, Japan. Correspondence Peng Zhao <zhaop@ conda.nju.cdu.cr
Recently, Sun et al. (2020) made remarkable progress in the study of heavy-tailed statistics by proposing adaptive Huber regression, which leverages the Huber loss (Hu- ber, 1964) to achieve non-asymptotic guarantees. Li
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
Table I: Comparisons of our regret bounds and computational complexity to previous best-knowwn results for heavy- tailed linear bandits. For the regret, the logarithmic dependence over T' is hidden by O()-nootaion;; d is the dimension and in is the moment bound. For the computational cost, we only keep the dependence on the time step and overall time step T.
Method
Algorithm
Regret
Comp. cost
Remark
MENU (Shao et al., 2018)
δ (aT Tt
Olog T)
fixed arm set and repeated pulling
MOM
CRMM (Xue al., 2023)
O(1)
Truncation
TOFU (Shao et al., 2018)
ö (d'' T+.)
O(t)
absolute moment
CRTM (Xue et al., 2023)
((1)
E[re|t* [r-1] S u
Huher
HEAVY-OFUL (Huang et al., 2023)
δ (daaiite
v EE 18 dradie
(t
instance-dependent bound
Huber
Hvt-UCB (Corollary 1)
δ (dT ाスं)
O(1)
E| qu '+ Fi S wite
Huber
Hvt-UCB (Theorem 1)
Ö ( Ets 12 + dl मोकं
((1)
instance-dependent bound
Sun (2024) further applied this technique to SLB, achiev- ing an optimal and variance-aware regret bound under bounded variance conditions (a 1). Subsequently, Huang al. (2023) extended the adaptive Huber regres- sion to handle heavy-tailed scenarios (e E (0, I)), achiev- ing an optimal and restance-depedenn regret bound of (dT /Ei= v² + dd for HvtLB. Notably, the adaptive Huber regression does not rely additional noise assumptions or the repeated pulling of bandit settings. This generality allows the approach to be further adapted to other decision-making scenarios, such as reinforcement learning with function approximation.
that while one-pass algorithms based on the truncation and MOM approach have been proposed by Xue et al. (2023), but as noted earlier, these methods heavily rely on specific assumptions the bandit structure. Given the attractive properties of Huber loss-based method (Huang et al., 2023), natural question arises: Is it possible to design one-pass Huber-loss-bant -aasd algorithm that achieves optimal regret?
Our Results. In this work, we propose a Huber loss- based one-pass algorithm Hvt-UCB utilizing the Online Mirror Descent (OMD) framework, which achieves the optimal regret bound of Ö(T while eliminating the need store historical data. Additionally, our algorithm can further achieve the instance-dependent regret bound of Ö (dT (1++)-th central moment of reward at round f. Our approach preserves both optimal and mnstance-dependett regret guar- antees achieved by Huang et al. (2023) while significantly reducing the per-round computational cost from O(t log T') to ((1) with respect to the current round t and the time horizon T. Moreover, our algorithm does not rely on ad- ditional assumptions. making it more broadly applicable. A comprehensive comparison of our results and previous works on heavy-tailed linear bandits is presented in Table 1.
In each round t, the adaptive Huber regression has to solve
the following optimization problem:
Et= +2++dT" +dT ). where w/ is the
0 arg min A 10112 + Σ (0),
BEG
where θ is the feasible set of the parameter, À is the reg- ularization parameter, and f, (0) represents the Huber loss at round 8. Unlike the OFUL algorithm (Abbasi- Yadkkri et al., 2011) for SLB with sub-Gaussian noise, which uses least squares (LSS for estimation and can update recursively based on the closed-form solution, the Huber loss is par- tially quadratic and partially linear. Solving (3) requires storing all historical data and performing a full pass over all historical data at each round to update the parameter esti- mation. This results in per-round storage cost of (() and computational cost of O( log T) with respect to the current round: and the time horizon T. making computationally infeasible for large-scale real-time applications. Thus, we require one-pass algorithm for HvtLB that updates the estimation at each round t using only the current data, with- out storing historical data. Indeed, our goal is to design an algorithm for htave-tailed linear bandits that is (basically) as efficient as OFUL in SLB with aub-Gaussian noise. Note
Key Challenges and Techniques. Designing one-pass algorithm for heavy- tailed linear bandits presents two major challenges. On the one hand, unlike the full-batch estima- tor (3) (Huang et al., 2023), which leverages the entire histor- ical data to control the estimation error, a one-pass estimator updates relies only on the current data point. Achieving comparable estimation error bound for one-pass estimator is much more challenging, especially in the presence of heavy-tailed noise. On the other hand, OMD is originally developed for regret minimization. Adapting it to parameter estimation requires linking the parameter gap (estimation
2

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
error) with the loss value gap (regret). To address these chal- lenges, our algorithm design and analysis incorporate two key components: (i) Handling heavy-tailed noise: Zhang et al. (2016) have adopted variant of Online Newton Step (ONS) to Logistic Bandits settings, but their method cannot be applied to HvtLB since their method relies on the global strong convexity of the logistic loss, whereas the Huber loss partially linear. We generalize their approach to the OMD framework and introduce a recursive normalization factor that ensures normal data stays in the quadratic region of the Huber loss with high probability, maintaining robustness in estimation. This normalization f'cctor also introduces a negative term in the estimation error, which is crucial for controlling stability. (ii) Supporting one-pass updates: The OMD framework introduces a stability term in estimation error, which represents the impact of online updates. The adaptive normalization factor adds a multiplicative bias to this term, resulting in a positive term of order (VVT) that weakens the bound. This requires a careful design of the normalization factor and learning rate of OMD to cancel it out using the negative term that arises from our OMD- based analysis, which is similar to a crucial technique in the regret analysis of recent iidiient-variatoon online learning methods (Zhao et al., 2020b; 2024).
Huber-Bandit algorithm based on Huber regression, achiev- ing an Ö( Ö(VāTT=) regret bound, On the other hand, Li & Sun (2024) were the first to apply adaptive Huber re- gression technique (Sun al., 2020) to SLB, focusing on noise with finite variance (namely, HvtLB with & 1). They proposed the AdaOFUL algorithm, achieving an op-
timal variance-awan regret of Ö(dy Σx= vf),, where is is the upper bound of the variance. This result is subse- quently improved by Huang et al. (2023), which is also the most related work to ours. Huang et al. (2023) con- sidered general heavy-tailed scenarios with E E (0, 1] and proposed HEAVY-OFUL with an restance-dependee gret of Ö 1_ VET 12 + HT ((+)))) where v/!+ is the (1 + s)-th central moment of reward at round Sub- sequent works have applied Huber regression various bandit settings, such as matrix-valued contextual bandits with low-rank structure (Kang et al., 2024). We emphasize that all the above Huber regression-basee algorithms for heavy- stavy-tailed bandits are not updated in a one-pass manner. Beyond Huber-based approaches, other techniques have been explored for handling heavy-tailed noise and outliers. These include general robust loss functions like Tilted Em- pirical Risk Minimization (TERM) (Li et al., 2021a), and reweighting- based methods proposed in the offline contex- tual bandit (Sakhi et al., 2024; Behnamnia et al., 2024). A potential future direction could be to develop one-pass algorithms based on these techniques.
re-
2. Related Work
Heavy-Tailed Bandits. The multi-armed bandits (MAB) problem with heavy-tailed rewards, characterized by finite (1+ m-momen,, was first studied by Bubeck et al. (2013). They introduced two widely used robust estimation and regression methods from statistics into the heavy-tailed ban- dits setting: truncation and median-of-means (MOM). Med- ina & Yang (2016) extended these methods to heavy-tailed linear bandits (HvtLB) and proposed two algorithms: the truncation- based CRT algorithm and the MOM- MoM 2tc algorithm, achieving x0T') and Ö 1+2r, i+3:) regret bounds, respectively. Later, Shao et al. (2018) established an (((7 lower bound for HvtLB and introduced the truncation-based TOFU algorithm and the MOM-based MENU algorithm, both achieving an ÖdTTTt) ) regret bound. For HvtLB with finite arm set, Xue al. (2020) es- tablished an (dt"= lower bound, and proposed the truncation-based BTC algorithm and MOM-based BMM algorithm, both of which achieve an Ö(V regret bound, reducing the dependence on the dimension d under the finite arm set setting. To the best of our knowledge, the two works (Kang& & Kim, 2023; Li & Sun, 2024) first introduce Huber loss to linear bandits. Specifically, Kang & Kim (2023) studied the heavy-tailed linear contextual bandits (HvtLCB) with fixed and finite arm set, where the context X, at each round is independently and identically distributed from a fixed distribution. They proposed the
One-Pass Bandit Learning. In SLB, Abbasi- Yadkori et al. (2011) proposed the OFUL algorithm, achieving an Odd'T) regret bound. It uses Least Squares (LS) for pa- rameter estimation, naturally supporting one-pass updates with a closed-form solution. As an important extension of SLB, Generalized Linear Bandits (GLB) is first intro- duced by Filippi et al. (2010). Their proposed GLM-UCB algorithm achieves an (RdVT) regret bound, where measures the non-linearity of the generalized linear model. This algorithm relies on Maximum Likelihood Estimation (MLE) which does not have a closed-fore form solution like LS in SLB and requires storing all historical data, resulting in a per-round computational cost of Ot). To this end, Zhang et al. (2016) proposed OL2M, the first one-pass algorithm for Logistic Bandits (a specific class of GLBB, achieving an (KdVT) regret bound with per-round computational cost of (1)). Later, Jun et al. (2017) explored one-pass algo- rithms for GLB by introducing the conversion. Using this conversion, they developed GLOC, a one-pass algorithm that achieves the same theoretical guar- antees and per-round cost as OL2M but is applicable to all GLB, Xue et al. (2023) considered heavy-tailed GLB and proposed two one-pass algorithms: truncation-baad based CRTM and -eeanans- based CRMM, both achiev- ing an Ö(dTT' T+: regret bound. Subsequent works have
3

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
tackled more challenging topies, such as reducing the depen- dence on with one-pass algorithms designing such algo- rithms for more complex models like Multinomial Logistic Bandits and Multinomial Logit MDPs (Zhang & Sugiyama, 2023; Li et al., 2024; Lee & Oh, 2024; Li et al., 2025).
The Huber loss is a robust modification of the squared loss that preserves convexity. It behaves quadratic function when |a|| is less than the threshold т, ensuring strong con- vexity in this range. When |x| exceeds т, the loss transitions to a linear function to reduce the influence of outliers.
At round t, building on the Huber loss, adaptive Huber regression estimates the unknown parameter 8, of linear model (4) by using all past data up as
3. One-Pass Heavy-tailed Linear Bandits
In this section, we present our one-pass method for han- dling linear bandits with heavy-tailed noise. Section 3.1 introduces the problem setup. Section 3.2 reviews the latest work of Huang et al. (2023) and identifies the inefficiency of the previous method. Section 3.3 introduces the OMD-type estimator based on Huber loss, along with the arm selection strategy and the regret guarantee.
ST. - xx ox );:0].. (6)
0. arg min dEB
11012
where À is the regularization parameter, fr. (-) represents the Huber loss with dynamic robustification parameter т., and J, denotes the normalization factor. Based on the adaptive Huber regression, their proposed Heavy-OFUL, algorithm achieves the optimal and restacce-depeneen regret bound.
3.1. Problem Setup
We investigate heavy-tailed linear bandits. At round i, the learner chooses an arm X, from the feasible set X; C Red, and then the environment reveals a reward r. IR such that
Remark 1. Note that (Kang & Kim, 2023) and (Kang et al., 2024) also use Huber regression as the estimator in dif- ferent bandit problems. Adaptive Huber regression differs from their methods in two key aspects: first, it uses time- varying robustification parameter T3. second, it introduces normalization factor 0, to further control the loss. This normalization factor not only enables instance-dependent regret bounds but also ensures that the denoised data re- mains within the quadratic region of the Huber loss, such that the Hessian of the loss function is guaranteed to have lower bound, which is essential for theoretical analysis. The two prior works based on Huber regression avoid such normalization but introduce other algorithmic components and assumptions to achieve similar effect: (i) Kang & Kim (2023) incorporates a forced exploration mechanism along with a lower-bounded Hessian assumption; (ii) Kang et al. (2024) employs a local adaptive
ri = X7 0, + ne.
(4)
where 02 E Rd is the unknown parameter and me e IR is the random noise. We define the filtration (Fi)e21 as Fe - a ((X1,71,.... Pt-
The noise q E IR Fe-measurable and satisfies for some e E (0, 1),
Elm | [[-1]] = O and E[|m| 1++ |F--ll = witt with is being
The goal of the learner is to mini- mize the following (pseudo) regret.
T REGT = Σ max x O, - Ex,O.
T
XEX.
We work under the following assumption as prior works (Xue et al., 2023; Huang et al., 2023).
minimization tech- nique together with a lower bounded covariance matrix as- sumption to guarantee a lower bounded Hessian.
Assumption 1 (Boundedness). The feasible set and un- known parameter are assumed to be bounded: Vx E Xe ||x||| < L, 0, E θ holds where θ A {0 |01| S S).
3.2. Reviewing Previous Efforts
Efficiency Concern. When the robustification parameter T = +o0, Huber regression (6) reduces to least square, al- lowing one-pass updates with a closed-form solution. How- ever, for finite T., which is essential for handling heavy- tailed noise, (6) requires solving a strongly convex and smooth optimization problem, which needs to store all past data resulting in storage complexity of O(t). Using Gra- dient Descent (GD) achieve e-accurate solution re- quires Oloog( (1))) iterations, with per-iteration computa- tional cost of ((t) to compute the gradient over all past data. To ensure an optimal regret, is typically set to 1/VT, leading to a total computational cost of O(t log T) at round t. This would be infeasible for large-scale time horizon T.
In this part, we review the best-known algorithm of Huang et al. (2023). They leveraged the adaptive Huber regression method (Sun et al., 2020) to tackle the challenges of heavy- tailed noise. Specifically, adaptive Huber regression is based on the following Huber loss (Huber, 1964).
Definition (Huber loss). Huber loss is defined as
2
if ST.
fxxx)
2
(5)
||||
+
if
>T,
>T,
where T > 0 the robustification parameter.
4

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
3.3. Hyt-UCB: Huber loss-based One-Pass Algorithm
where the main computational cost lies in calculating the inverse matrix V,-1, which can be efficiently updated using the Sherman-Morrison Sattrisoon-Wodbbryy formula with time com- plexity of (dd)). The projection step adds an additional time complexity of (dd)). Focusing on one-pass updates and considering only the dependence on t and T, our es- timator achieves a per-round computational complexity of (1), representing a significant improvement over previ- ous methods with a complexity of O(t T). Moreover, it eliminates the need to store all historical data, requiring only (11) storage cost throughout the learning process.
The adaptive Huber regression method proposed by Huang et al. (2023) incurs significant computational burden in each round and requires storing all past data, which is less fa- vorable in practice. Thus, we aim to design a one-pass algorithm for HvtLB based on the Huber loss (5).
For simplicity, let (0) A x--TT we introduce the loss function (0) based on (5) as follows,
de
if (0)l S To.
(0)
x,
if 2 (0) > Tr.
Statistical Efficiency. As mentioned earlier, OMD is a gen- eral framework that has demonstrated its effectiveness in ad- versarial online learning for regret minimization. Nonethe- less, in stochastic bandits, more critical requirement is the accuracy of parameter estimation. In the following, we demonstrate that OMD also performs exceptionally well in this regard. The key lemma below presents the estimation error of estimator (8) based on OMD-typed update.
where d₂ is the normalization factor, and 72 is the robustifi- cation parameter, both for controlling heavy-tailed noise.
To enable a one-pass update, instead of solving Huber regres- sion (6) using all historical data, adopt the Online Mirror Descent (OMD) framework (Orabona, 2019). As a general and versatile framework for online optimization, OMD has been widely applied to various challenging adversarial on- line learning problems, such as online games (Rakhlin & Sridharan, 2013; Syrgkanis et al., 2015), adversarial ban- dits (Abernethy et al., 2008; Wei & Luo, 2018), and dy- namic regret minimization (Zhao et al., 2024; Jacobsen & Cutkosky, 2022), among others. In contrast, we leverage its potential to address stochastic bandit problems, drawing inspiration from recent advancements in the study of logis- tic bandits (Zhang & Sugiyama, 2023). Specifically, we propose the following OMD-based update for estimation,
Lemma 1 (Estimation error). If fta, To To are set as
28
0, max { Fmin
[ )
1- Tovata++)
V + w Ti TO
V2x(llgg 37) 2(x4))
t
TO
Wi
(log 242) itc
where amin a small poxitive constant which will be speci- fied later and we then with probability at least 1 45, VI 2 1, we have | 8. 8.112.
[/ 0e v=: Let the step size 4, |1
xx
v
0+t1 = arg min (0,, ve,(0.)) ((.,
=arg #50
(0,
(8)
S Be with
where ② is the fcasible set defined in Assumption and Des (:.-) ) is the Bregman divergence associated to the regu- larizer v/, Rd + R. The choice of the regularizer is crucial because, in stochastic bandits, parameter estimation is sub- sequently used for confidence set construction. Therefore, we define the regularizer using the local information as
27
3e 2 107
8 not + AA(++459) (10)
where e dlog (I
1²T 4a mii Xd
We provide an analysis sketch in Section 4, where we ex- plain how to analyze the estimation error using the OMD framework, and decompose the effects of heavy-tailed noise and one-pass updates. The full proof of Lemma is pro- vided in Appendix B.5.
X.XT
|00|2, with V AI (0) = 2
(9)
where Vo A Xla The choice of this local-norm regularizer compatible with the self- nerf-noomalized concentration used to construct the Upper Confidence Bound (UCB) of estimation error. Here, the coefficient in Vú essentially represents the step size of OMD, which will be specified later.
Notably, both our method and the HeavyOFUL algorithm of Huang et al. (2023) require the input of oe Te- In fact, our parameter setting for de is simpler. HeavyOFUL. re- quires maintaining two complex lower bounds for oN to satisfy: AO E O, (X, 8 - X, 6.) /ai| < T ensuring that the loss remains quadratic for noiseless data. In contrast, our analysis focuses on a refined condition to guarantee the quadratic loss property involving only the current estimate 0₁: |(X, 0, X, 0T////l S Tt- This refinement enables us
Computational Efficiency. Clearly, the estimator (8) can be solved with a single projected gradient step, which can be equivalently reformulated as:
0.11 = -,, (v) 0+11= = arg min 100 0+
5

---

Heavy-Tailed Lincar Bandits: Huber Regression with One-Pass Update
Algorithm 1 Hvt-UCB
Corollary 1. Follow the parameter setting in Theorem 1, and replace the is with in the at setting, the regret of Hv-UCB is bounded with probability at least 1 1 1/T, by
Input: time horizon T, confidence 6, regularizer X, minu bounded parameters S, I., parameter for estimation co.
C1. TO. a,
Set K dlog (1 - )ard Vo APds 01 and
REGT Sō <Ō(T (dT
compute 8n by (10)
2: for fort= 1,2, ..... do
The proof of Corollary can be found in Appendix C.2. This bound matches the lower bound ((dT (Shao et al., 2018) up to logarithmic factors. Moreover, when 1, i.., the bounded variance setting, our approach recovers the regret bound (dvTT), which nearly matches the lower bound ((dvT) (Dani et al., 2008).
3: Select X = arg x (x, 0r) + 11
4: Receive the reward rt, and 1/
5: S max 1/2, minu
23.
|| v
Tovat 2010)1
6: Set 7 = To V+ p20+e]
with W2 = va
1/2
Xe
vzl
7: Update V Vi-1+ o, X,,X7
4. Analysis Sketch
8: Compute lct1 by (8) and 3, by (10)
9:
end for
In this section, we provide a proof sketch for Lemma where adapt the analysis framework of Online Mirror Descent (OMD) to the SLB setting. To simplify the pre- sentation, we first illustrate this framework using simpler case where the noise follows a sub-Gaussian distribution in Section 4.1. We then discuss the challenges of extending this framework to handle heavy-tailed noise and present our refined analysis in Section 4.2.
design a recursive parameter setting that directly incor- porates the upper confidence bound B from the previous round into the configuration of o, for the current round. Furthermore, this parameter setting can be directly applied to the adaptive Huber regression. Similar to Huang et al. (2023), our method requires the knowledge the moment i of each round f. If vn not available but general bound is known, such that E[|,: [++e Fe-1] z yI+e, we can still trivially achieve the same estimation error bound by replacing with v in the setting of o,.
4.1. Case study of sub-Gaussian noise
We first consider that the noise 7)e in model (4) follows a R-sub-Gaussian distribution. Then the robustification pa- rameter should be set as +000 and the Huber loss recovers the squared loss by (0) = = O)/o))
UCB Construction. Based on the one-pass estimator (8) and Lemma 1, we can specify the arm selection criterion as
Estimation error decomposition. We begin by decompos- ing the estimation error into the following three components:
X, arg max { (xx, 0t) + B /aaal////v | xEX,
(11)
Lemma 2. Let (,))) = {X, (0. 0) be the de- noised Huber loss function, then the estimation error of estimator (8) with 2 can be decomposed as follows.
Algorithm summarizes the overall algorithm, and enjoys following iistance-dependen regret.
Theorem 1. By setting ot. Tu, To, as in Lemma 1, and let X = d, mmin V 8 = ST, with probability at least 1 1/T, the regret of Hvt-UCB bounded by
|0 0. 0.112
<2 V(,
generclization gap
T
REGT S <ō
I-e 20+0
Σ v
dT 1-c
20-))
ve, (0) 02)
0. - 0,
+4XS²
-=1
2
of
stability
negative
The proof of Theorem can be found Appendix C.I. Compared Huang et al. (2023), our approach achieves the same order of instance-dependent regret bounds, while sig- nificantly reducing the per-round computational complexity from (t log T) to (1).
Proof Sketch. First based on the standard analysis of OMD (Orabona, 2019, Lemma 6.16), we have
(e)( -
When the moment V4 of each round is unknown, but a general bound v is known, such that Elin| I+ Fe-1] E
s 0 0. 2 1 0
2 + 1 [
0_
+l+ we can achieve the following regret bound.
V.
2
6

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
Based on the quadratic property of the denoised loss func- tion E.(), we have the following equality,
Now (0) is partially quadratic and partially linear, to further utilize the OMID-based estimation error decompo- sition, we need make sure Or and 8, both lie in the quadratic region of the loss function (x()). Assuming the event A. = {vv E [1,] 0sllv.., S B holds, we set of 2 (2 || v 3t-1)/( 2:140] ), we can ensure [(x, 0- - x 0.)/o,l - 3. This guarantees that (0,) is always in the quadratic region, allowing us to continue using the previous decomposition. The negative term from the de- composition will then be used for subsequent cancellation.
(.)))) - (.().) = 1000((vv Vi,(0))) 0.) 0. 0.
x ??
Since 0, is the minimizer of (-), (0)) - (0.)
0,
which implies that _110, - 0- 0 X.TT /03 2 (O.,
0.), then substituting this into the OMD update rule and we can achieve the iteration inequality for the estimation error, further with a telescoping sum, and we finish the proof. D
Stability term analysis. The first step is to extract stochas- tic term and deterministic term at each step as follows,
Stability term analysis. Similar to the sub- nab-Gaussian case, we can decompose the stability term into two stochastic and deterministic terms as follows,
VC, (0,) V.- =
X__ (0. 0,)
7
2
X
+
03
V.
Vll Ve.(O.) (0.) v-
1| <2>
min
Te 0s
X O,
Setting o₁ 1, we have X, (0,- (0.-0.) 0.)l S 2LS. Then based on the sub-Gaussian property. we have In21 bounded by OVylog 7') with high probability, and Σ || lic- can be bounded by Olog 7) with Lemma 7 (potential lemma), which means Ei= [C. (0.)),,, S O(log² T).
stochastic term
X_ 0.
X 0 0x
X2
+ 2
deterministic term
Generalization gap term analysis. By taking the gradient of the loss function, we have
Note that the stochastic term is no longer inherently bounded. To address this, we utilize a concentration tech- nique (Lemma 6) to bound it by Ō(ttTe). For the de- terministic term, x_ & is bounded by 2LS/omin. where mmin is the minimum of or, which can be as small as L/VT. If we continue using the analysis based on po- tential lemma, this term will grow to Ö(VT), which is undesirable. Based on the settings of ot, we ensure that Xx 2 v. S 1 Therefore, this term can be bounded by a.
(Z.(0.) - -2. - 0.) Σ 1s (x, 02 0.)
then we can directly apply the 1-dimension seff-normalized concentration (Theorem 2), further based on AM-GM in- equality, we can bound the general gap term by a Olog T)
term and E 00_ 0. p..1 x which can be further canceled by the negative term.
3/ E'm 00. - 0. x02 which can be further canceled out by the negative term.
By integrating the stability term and generalization gap term into Lemma 2, we can achieve the upper bound for the estimation error as ||0++1 0a l|, S O(logT)
Generalization gap term analysis. The non-linear gra- dient of the Huber loss in the heavy-tailed setting makes it impossible to directly obtain one-dimensional self- normalized term. We first decompose it into two distinct components as follows,
4.2. Analysis for haavy- noise
In this section, we extend our analysis to the heavy-tailed case. The presence of heavy-tailed noise and the partially linear structure of the Huber loss introduces new challenges in the three key analyses mentioned above. We will address these challenges one by one in the following discussion.
-V.())))...).......ll -o,
Huber-loss term
Estimation error decomposition. With the presence of heavy-tailed noise, the denoised Huber loss function with noise-free data E (0) X - is defined as
+ 2 s=1
- -V,, -0.)
self normalized term
x
if (0) S T
where Huber-loss term represents the influence of the Huber loss structure on the estimation error. Specifically, when all three gradient terms are within the quadratic region of
(0) A
x_ (0. -0) 0)
if (0)) > Tr-
Tt
0t
7

---

Haive-Tailed Linear Bandits: Huber Regression with One-Pass Update
the Huber loss, i.e., when |z,(0.) < 2. this term becomes zero. Consequently, this term reduces sum involving the indicator function 2.m1 1 (1z (0.) | > / which can be bounded by ( 3.) using Eq. (C.12) of Huang al. (2023). Then the self-normalized term corresponds to the 1-dimensional version of the rolf-normalized concentration can be bounded by an Ö(tirá) term and 2 Ei= |00
802
CRIM TALCO
1350
0114
Chast
manyorol
0. I1 /o² will be canceled by the negative term.
Figure 1: Student t: regret and time cost.
By combining the analysis for stability term and generaliza- tion gap term and substituting back to the estimation error decomposition, we obtain:
DELL CRMU FRINdFFL
0++1 - ealc, S 5120+)) 1-8
Be + पे..
To ensure the event A, holds, 3r must satisfy:
CATH
22000 B tite.
Figure 2: Gaussian: regret and time cost.
Finally, solving for Bi we get Bg (1 Thus we finish the proof of Lemma 1.
and computational time under Student's t noise, while Fig- ure 2 presents the same metrics under Gaussian noise, with shaded regions indicating the variance across trials. Under both noise settings, our algorithm demonstrates compara- ble regret performance to Heavy-OFUL while achieving remarkable computational efficiency, with a speedup ex- ceeding 800x. This efficiency advantage becomes more important the number of rounds T increases. OFUL, CTRM, and CRMM are faster than our Hvt-UCB algorithm because they use closed-form least squares solutions, while Hvt-UCB requires a projection step in each round. How- ever, Hvt-UCB's s runtime remains competitive and is on the same order of magnitude as these least squares- based algo- rithms. Notably, among the one-pass algorithms, CRMM exhibits the fastest runtime because it updates its estimates periodically (every O(log 7) rounds) rather than in every round. In the heavy-tailed noise scenario (Figure 1), the performance of OFUL drops significantly, demonstrating its sensitivity to heavy-tailed distributions. In the Gaussian noise setting (Figure 2), our algorithm maintains competi- tive performance alongside OFUL. However, the truncation- based CRTM algorithm shows suboptimal performance due to excessive reward truncation in light-tailed noise scenarios, which leads to the loss of valuable data. These experimental results validate that our Hvt-UCB algorithm achieves ro- bust performance across heavy-tailes and light-tailed noise environments while maintaining low computational cost.
5. Experiments
In this section, we evaluate the empirical performance and time efficiency of our proposed Hvt-UCB algorithm. We present two experiments under heavy-tailed noise (Student's and light-tailed noise (Gaussian). Furthermore, we pro- vide additional experiments in Appendix E, including vari- ous heavy-tailed noises (Pareto, Lomax, Fisk), time-varying 14, and changing arm sets X, to further validate the effec- tiveness and robustness of our algorithm.
Settings. We consider the linear model r, X,T 8. + ?t- where the dimension d 2, the number of rounds T 18000, and the number of arms n = 50. Each dimension of the feature vectors for the arms is uniformly sampled from [-1, 1] and subsequently rescaled to satisfy L = 1. Simi- larly, 0_ is sampled in the same way and rescaled to satisfy S 5=1. 1. We conduct two synthetic experiments with different distributions for noise qp: (a) Student's (-distribution with degree of freedom df 2.1 to represent heavy-tailed noise: and (b) Gaussian noise sampled from (000 1) to represent light-tailed noise. For the heavy-tailed experiment, we set 8 = 0.99 and = 1,31, while for the light-tailed experi- ment, we set E = 1. We compare the performance of our proposed Hvt-UCB algorithm with the following baselines: (a) the OFUI. algorithm (Abbasi-Yadkorii et al., 201 1): (b) the one-pass truncation-basee based algorithm CRTM (Xue al., 2023); (c) the one-pass MOM-based algorithm CRMM (Xue et al., 2023); and (d) the Huber regression-bastt based algorithm HEAVY-OFUL (Huang et al., 2023).
6. Discussion
In this section, we discuss the potential applications of our approach and highlight its advantages compared to previous methods in broader scenarios involving heavy-tailes noise. Specifically, we focus on two settings: heavy- linear MDPs and adaptive control under heavy-tailed noise.
Results. We conducted 10 independent trials and aver- aged the results. Figure! 1 shows the cumulative regret
8

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
6.1. Online Linear MDPs
where O_ = [A: B]. 2, [My;; uy] and the noise wi in each dimension is assumed to be sub-Gaussian. Then, they used least squares estimator and leveraged the self-normalized concentration technique from linear bandit analysis (Abbasi- Yadkori et al., 2011) to estimate + and provide finite- sample estimation error guarantees.
In the setting of heavy-tailed linear MDPs (Li & Sun, 2024; Huang et al., 2023), the realizable reward for taking action in state at the h-th episode is given by:
[s, a) (Ø(s. 0%) + (s)
where 6(s a) E IR is known feature map. 0% E R is the unknown parameter, and ex (x a) the heavy-tailed noise with Eslen(ss a) = 0 and [|e [* a) S 'R
As noted by Tsiamis et al. (2023), finte--ample guaran- tees for system identification under heavy-tailed noise re- main open challenge. In light of Abbasi- Yadkori & Szepesvári (2011)² application of linear bandit techniques to sub- Sabb-aussian cases, we believe our method for HvtLB can be also benefit adaptive control in heavy-tailed settings. However, MOM methods are infeasible as the feature & which includes the evolving state It. cannot be repeatedly sampled, and cruncation-based methods rely on assumptions of bounded absolute moments for states, which may not hold, While adaptive Huber regression (L.i & Sun, 2024; Huang et al., 2023) offers promising theoretical guarantees for heavy-tailed linear system identification, its computa- tional inefficiency makes it unsuitable for adaptive control. In contrast, our proposed Hvt-UCB algorithm provides one- pass updates and has the potential deliver finite-sample guarantees for adaptive control under heavy-tailed noise.
Linear MDPs often adopt techniques from linear bandits, including estimating unknown parameters in linear model and constructing an upper confidence bound (UCB) based on estimation error analysis. For heavy-tailed linear MDPs, (Huang et al., 2023) employs adaptive Huber regression to estimate the unknown parameter 0% in the reward function. This introduces a challenge similar to that in HvtLB: adap- tive Huber regression is an offline algorithm, while an online setting requires nue-pass estimator. Existing one- one-pass esti- mators for HvtLB, such as the truncation- based and MOM- based algorithms proposed by Xue et al. (2023), are not applicable to heavy-tailed linear MDPs. Truncation-basee algorithms rely on assumptions about absolute moments, which are not suitable in this case. MOM- methods require repeated reward observations for a fixed d(s, a), which is infcasible in linear MDPs since state transitions occur probabilistically.
7. Conclusion
In this paper, we investigate the problem of heavy-tailed lin- ear bandits (HvtLB). We highlight the advantages of Huber loss-based methods over truncation and median-of-meat strategies, while also identifying the inefficiencies in pre- vious Huber loss-based methods for HvtLB. To address these issues, we propose Huber loss-based one-pass algo- rithm Hvt-UCB, based on Online Mirror Descent (OMD). a well-known regret minimization framework in online learn- ing, which we adapt here for use as a statistical estimator. Hvt-UCB achieves the optimal and instance-dependent re-
In contrast, our proposed Hvt-UCB method does not suffer the aforeementioned issue and has the potential to be applied to this scenario without requiring additional assumptions. Its estimation error bound analysis naturally extends to linear MDPs, enabling the construction of UCBs for the value func- tion. By leveraging the UCB-tto-regret analysis in (Huang et al., 2023), Hvt-UCB has the potential to achieve the same theoretical guarantees as adaptive Huber regression, while significantly reducing computational costs.
ET 17 + d'' x))))))))) while only requiring O(1) per-round computational cost. Furthermore, our proposed method enjoys the potential to be extended to more broad online decision-making problems, including online linear MDPs and online adaptive control, thereby broadening its applicability. The key contribution is our adaptation of the OMD framework to stochastic linear ban- dits, effectively addressing the challenges introduced by heavy-tailed noise and the structure of the Huber loss.
gret bound O(dI''t
6.2. Online Adaptive Control
The online adaptive control of Linear Quadratic Sys- tems (Abbasi-Yadkoori following state transition system,
Yadkori & Szepesvári, 2011) considers the
Tz+1= = Ar, + Bu, + Wi+h,
where I2 E E" represents the state at time t, un RRd is the control input at time t, A E Rax= and B E Ruxd are unknown system matrices, and W(+1 is the noise. The online adaptive control requires estimating the unknown parameters A and B (also known as system identification), and constructing finite-samin sample guarantees for estimation error. To this end, Abbasi Yadkori transformed the system into the following linear model:
Both our work and Huang et al. (2023) rely on prior knowl- edge of the moment bound to achieve mnstance-dependee guarantees. Recent progress in heavy-tailed multi-armed bandits has removed this requirement in different settings: adversarial (Huang et al., 2022), stochastic (Genalti et al., 2024), and titt-of-ooth-wortte (Chen et al., 2025). Whether similar techniques can be applied to heavy-tailed linear ban- dits to relax this assumption remains open question.
Abbasi-Yadkori & Szepesvári (2011)
1+1 = O._ 2t + We41,
9

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
Acknowledgements
Chen, Y., Huang, J., Dai, Y., and Huang, L. unilNF: Best- of-both-worlds algorithm for parameter- free heavy-tailed mabs. In Proceedings of the 13th International Confer- ence on Learning Representations (ICLR). 2025.
This research was supported by National Science and Technology Major Project (2022ZD01 14800). NSFC (U23A20382), Postgraduate Research & Practice Innova- tion Program of Jiangsu Province (KYCX25 _027)) The authors also thank Bo Xue for helpful discussions.
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In Proceedings of the 2 Annual Conference on Computational Learning Theory (COLT), pp. 355-366, 2008
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Filippi, S., Cappé, O., Garivier, A., and Szepesvári, C. Para- metric bandits: The generalized linear case. In Advances in Neural Information Processing Systems 23 (NIPS), pp. 586-500 504,594475 2010.
Genalti, G., Marsigli, L., Gatti, N., and Metelli, A. M. (e, u)- adaptive regret minimization heavy-tailed bandits. In Proceedings of the 37th Conference Learning Theory (COLT), pp. 1882-1915, 2024.
References
Abbasi- Yadkor,, Y. and Szepesvári, C. Regret bounds for the adaptive control of linear quadratic systems. In Proceed- ings of the 24th Annual Conference on Computational Learning Theory (COLT), pp- 1-26, 2011.
Huang, J., Dai, Y., and Huang, L. Adaptive best-of-bothe worlds algorithm for heavy-tailed multi-armed bandits. Proceedings of the 39th International Conference on Machine Learning (ICML). pp. 9173-91799999 92000 2022.
Abbasi-Yadkorts Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24 (NIPS), pp. 2312-2320, 2011.
Huang, J., Zhong, H., Wang. L., and Yang, L. Tack- ling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance- dependent regret bounds. In Advances in Neural Informa- tion Processing Systems 36 (NeurIPS), pp. 56576-56588, 2023.
Abbasi-Yadkori, Y., Pál. D., and Szepesvári, C. Online- to-confidence-set conversions and application to sparse stochastic bandits. In Proceedings of the 15th Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1-9, 2012.
Huber, P. J. Robust estimation of a location parameter, In The Annals of Mathematicul Statistics, pp. 73-101, 1964.
Abernethy, J., Hazan, E.,, and Rakhlin, A. Competing in the dark: An efficient algorithm for bandit linear optimiza- tion. In Proceedings of the 21 Annual Conference Learning Theory (COLT), pp. 263 2743-274222 2008.
Hull, J. Risk management and financial institutions, volume 733. John Wiley & Sons, 2012.
Behnamnia, A., Aminian, G., Aghaei, A., Shi, C., Tan, V. Y. F., and Rabiee. H. R. Batch learning via log-sum- exponential estimator from logged bandit feedback. In Proceedings of the ICML 2024 Workshop on Aligning Reinforcement Learning Experimentalists and Theorists, 2024.
Jacobsen, A. and Cutkosky, A. Parameter-free mirror de- scent. Proceedings of the 35th Conference on Learning Theory (COLT), pp. 4160 4211,, 2022.
Jebarajakirthy, C., Maseeh, H. I., Morshed, Z.,, Shankar, A., Arli, D., and Pentecost, R. Mobile advertising: A systematic literature review and future research agenda. International Journal of Consumer Studies, 45(6): 1588- 1291, 2021.
Bubeck, S., Cesa-Bianchi, N., and Lugosi, G. Bandits with heavy tail. IEEE Transactions on Information Theory, 59 (11):7711-7717. 2013.
Jun, K., Bhargava, A., Nowak, R. D., and Willett, R. Scal- able generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems 30 (NIPS), pp. 99-109, 2017.
Catoni, O. Challenging the empirical mean and empirical variance: a deviation study. Annales de I'IHP Probabilités et statistiques, 48(4): -185, 2012.
Chen, G. and Teboulle, M. Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-544 1993.
Kang, M. and Kim, G.-S. Hcavy-tailed linear bandit with Huber regression. In Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1027- 1036, 2023.
10

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
Kang, Y., Hsieh, C.-J., and Lee, T. C. M. Low-rank matrix bandits with heavy-tailed rewards. In Proceedings of the 40th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1863-1889, 2024.
Shao, H., Yu, X., King, I., and Lyu, M. R. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoff's. In Advances in Neural Information Processing Systems 31 (NeurlPS), pp. 8430-8439, 2018
Lee, J. and Oh, M. Nearly minimax optimal regret for multi- nomial logistic bandit. In Advances in Neural Information Processing Systems 37 (NeurIPS), pp. 109003-109065, 2024.
Sun, Q. Zhou, W.-.,, and Fan, J. Adaptive Huber regres- sion. Journal of the American Statistical Association, 115 (529):254-265, 2020.
Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems 28 (NIPS), pp. 2989-29999999 2999, 2015.
Li, L.-F., Zhang, Y.J.., Zhao, P., and Zhou, Z.-H. Provably efficient reinforcement learning with multinomial logit function approximation. In Advances in Neural Informa- tion Processing Systems 37 (NeurIPS), pp. 58539-58573, 2024.
Tsiamis, A., Ziemann, I., Matni, N., and Pappas, J. Sta- tistical learning theory for control: A finite-sample per- spective. IEEE Control Systems Magazine, 43(6):67-97, 2023.
Li, L.-F., Qian, Y.-Y., Zhao, P., and Zhou, Z.-H. Provably efficient online RLHF with one-pass reward modeling. ArXiv preprint, 2502.07193, 2025.
Wei, C.-Y. and Luo, H. More adaptive algorithms for adver- sarial bandits. In Proceedings of the 31st Conference on Learning Theory (COLT), pp. 1263-1291, 2018.
Li, T., Beirami, A., Sanjabi, M., and Smith, Tilted empir- ical risk minimization. In Proceedings the 9th Interna- tional Conference Learning Representations (ICLR), 2021a.
Xue, B., Wang, G., Wang, Y., and Zhang. L.. Nearly opti- mal regret for stochastic linear bandits with heavy-tailed payoffs. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2936- 2942, 2020.
Li, X. and Sun, Q. Variance-aware robust reinforcement learning with linear function approximation under heavy- tailed rewards. Transactions on Machine Learning Re- search, 2024.
Xue, B., Wang. Y., Wan, Y., Yi, and Zhang. L. Efficient al- gorithms for generalized linear bandits with heavy- -taile rewards. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 70880-70891, 2023.
Li, Y., Wang, Y., Chen, X., and Zhou, Y. Tight regret bounds for infinite-arii armed linear contextual bandits. In The 24th International Conference on Artificial Intelligence and Statistics (AISTATS). pp. 370-378, 2021
Zhang, L., Yang, T., Jin, R., Xiao, Y., and Zhou, Z.-H. On-
Lugosi, G. and Mendelson, S. Mean estimation and regres- sion under heavy-tailed distributions: A survey. Founda- fions of Computational Mathematics, 1955):1145-110 2019.
line stochastic linear optimization under one-bit feedback. In Proceedings of the 33rd International Conference on Machine Learning (ICML., pp. 392-401, 2016.
Zhang, Y. and Sugiyama, M. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 29741-29782, 2023.
Medina, A. M. and Yang. S. No-regret algorithms for heavy- tailed linear bandits. In Proceedings of the 33rd Inter- national Conference on Machine Learning (ICML), pp. 1642-1650, 2016.
Zhao, P., Zhang, L., Jiang, Y., and Zhou, Z.-H. A simple ap- proach for non-stationary linear bandits. In Proceedings of the 23rd International Conference on Artificial Intelli- gence and Statistics (AISTATS), pp. 746-755, 2020a.
Orabona, F. A modern introduction to online learning. ArXiv preprint, arXiv:1912. 2019.
Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems 26 (NIPS), pp. 3066- 3074, 2013.
Zhao, P., Zhang, Y.J.,, Zhang, L.,, and Zhou, Z.H. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 125 12510-12520, 2020b.
Sakhi, O., Aouali, I., Alquier, P., and Chopin, N. Loga- rithmic smoothing for pessimistic off-policy evaluation, selection and learning. In Advances in Neural Informa- tion Processing Systems 38 (NeurIPS), pp. 12345-12351 2024.
Zhao, P., Zhang, Y.J.., Zhang, I.., and Zhou, Z.-H. Adap- tivity and non-stationarity: Problem- -deeended dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.

---

Haive-Tailed Lincar Bandits: Huber Regression with One-Pass Update
A. Properties of Huber Loss
Property 1 (Property of Huang et al. (2023)), Let fa( be the Huber loss defined in Definition then the followings are true:
1. (x)( ml,
2. (x) = (*))
3. log (1 + 1x| - f1(x)= z log (1+ + x + [x|+te) for any e E (0, 1].
4. (*(x) = || T}.
Furthermore, the gradient of the loss function (7) is,
(0) X
if [2)) S Th if (0) > Ti,
Ve2(0)
Ti X1
(12)
Xx
if 20) -tt-
T1 0z
Based on Property 1, we have
X,X,
(e)( min (1)( m
V2C,(0) = ()x(0) ST
(13)
of
B. Estimation Error Analysis
For the analysis of estimation error, we begin by defining the following denoised loss function based noise-free data
(0) 0. 0
x. (0.-9) 10.-89 0)
if (0)) 7t
0e
(0)
x (0,
if (0) > T5-
The gradient and Hessian of the denoised loss function (0) can be writen
if) S Tr Vē,(0) = Te X1 (0) > Toe
(0) X+
X.X,
v2ū,(0) = 1 TT
(14)
of
(0) < Tt.
We further the robustification parameter 7, following.
V2k(log 37) 20क TO
1
X
T0
where
(15)
We
(log 272) itf
and we denote event A, sA' E [t].
10, -0.-0.10 llv.., S B.-1). Based on the parameter setting and the event A,, we derive
three useful lemmas for the analysis of estimation error in the following section.
B.1. Useful Lemmas
In this section, we provide some useful lemmas for the estimation error analysis. We provide the estimation error decomposition Lemma 3, the stability term analysis Lemma 4, and the generalization gap term analysis in Lemma 5. Lemma (Estimation error decomposition). When event A, holds, by setting as (15), and as
x 3--1
0/ >
(16)
Va 211
12

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
then the estimation error can be decomposed as following three terms,
10++1- - 0. l
S 4A5² + Σ5/
+ Σ (f.) - 0., -..)
(a
(1-1)
Σ
0, 0.
|
x
5
Lemma 4. By setting Ti (15) and 0, max Vt, mins m Xxll, }. with probability at least 1 8, we have Vt 2 1,
t-e v. & 6a ( V2k(log 37) 37)
log
2T
Ifz
2
+
1
t
0.
- 0.
8
4
X,XI
#=1
8=1
where at is the learning rate need to be tuned and k 2 dlog 1 +
I.2T min Aad
Lemma 5. By setting Tt as (15) and ot as following,
2 x1 vi=1 3r-1
ot max Vt, min; 2/21|Xxllvzz
(17)
Vargl 2[TT2
with probability at least 1 38, we have Vt 2 1,
21
Σ v.. Vl.(0.). 1::00-04. -0.) 1A, S 23/a a
log
Tot पाम
max Ba-1 <E(t+t1
8
4 da + Σ
X,
2 ) 0. 0, 0..
+
L- 8t
81+(+)) v 2ko(log 3T) 30+0)
log
27
8
s=1
B.2. Proof of Lemma 3
Proof. Since A,- {v's E [t].110. - 0. 9.llv.., S 5B holds, T, and 0, satisfies (15) and (16), we have
x 0, X, O.
X
0e l V
Tot 26+0)
1 v
+ w
Tt
0.
3
(
(18)
Ot
at
[=
2w,,3-1
2
We.
2
where W/
Xx Then, based definition of 2.).,, we have (0.) 0 Tr. and (18) shows that (0.) <
va
dc
S Tr, which means both points 0. and O, lie on the quadratic side of the denoised loss function 4(). This allows us to apply Taylor's Formula with lagrange remainder to obtain
Vi. - 0.) + 1 1 0. 1
(19)
v').(E.)
where E, =70c+ + (1 00, for some y E (0, 1). which means & also lie on the quadratic side of the denoised loss function:
x, E, X,O. xi (70, + (1 7)0.) x,
x, x, 0, - x, 0.
(E.)
7
S
S7g
Tt 2
<
Tm
a+
at
where the first inequality comes from (18). Then we have
- S ne)
XxXI
of
=
X.X. of
At the same time,
since 0, = arg mingers (0), we have 0 < (.:).) (..).) Substituting these into (19), we have
0 s (,00. - -,(0)) = (vū 0, 0.)
2
1
0, - 0
x
(20)
13

---

Haave-Tailed Lincar Bandits: Huber Regression with One-Pass Update
which means 1
|0. 0. N,x s (V 0: -..) then we have
2
0.
0. 01|1xa0
XXXX I (v(,())), -000)-1100))))) -..) ( (VE(()))) + ( -V(())))V(( -0.),
Ve,
(21)
where the first term be bounded by the Bregman proximal inequality (Lemmaa 9), we have
(Ve,().)) 0+11 - 0.) S Dv. (0.,0c) -Dy, (0,, 0c+1) -Do (0++1, 0c)
0. 0. 11 0 -0112.
0 0, 2
substituting the above inequality into (21), we have
0g l|:
1 0o-1 0. 0.110 - 0++1 - 01
1 1
2 0
0g
XxXX -
0,
2
2
of
(22)
(v.) O. - -O+1) + (vē,(.)) - Ve,(O)), -0.)
Rearranging the above inequality and using AM-GM inequality, we have
| 0z ea122 $ |00. 8.11 + +|[
? 1. +2 (Vi(()) V2,(00) - -.)- -.. [00-811p220 x,x_
s |0. 0. 0.112 v + +| +2 +2 - VV, 0.)+ {1 a
- 1) |:0. 0.
1||
Xxx]
of
where the last equality comes from that V2 V2-1 + 1 X.XX and we have
Taking the summation of the above inequality over rounds
o;
0
0,
-
1/2
<
00
0x
2
+
(O.)
2
V/-1 +2
- 0.)+
1
Σ
0
0
Vo
a
I 4AS² +
Ve,
(0.)
||
+2 Σ (.,) Ve, 0.) (--1)
Σ
0,
0
x.x
a
where the last incquality comes from Vo = Ala and Assumption 1, thus we complete the proof.
B.3. Proof of Lemma 4
Proof. We first analyze the upper bound of single term [[ based on the definition of loss function (13), we have
2
2 V.-
Pt
X,To A
X,
min
.Tt
T
V--1
17t
X, 0,
X2 0g
X2
min
Tt
Fr
0
V/-1
1h
X, 0,
XXT 0,
1
2
X₂
2
min
.e
Øt
Tt
V
X 0.
X, 0,
1)
X₂
min
+ min
.Th
Øt
a
V/-
14

---

Heavy-Tailed Lincar Bandits: Huber Regression with One-Pass Update
Tt 5e
X
2
0,
-X,
X2
S
min
Tt
+2
(23)
02
V,=
0:
Oe
We define V. a AaT + E
X,X_ of
aV,, then we have Wi
1
Xe
X2
Based on Sherman-Morrioo
Ja
0t
[1-1
4-1
Woodbury formula of V
we have
X2
x,
Xx
V wt)
w +
X,
X, = w²
0z
of
of
of
wp
+ m
thus
|| + liv
then taking the summation over inequality (23) over / rounds and we have a lt,?
Ve, (0.)
20
Te
Ta
2
w
2a
X 0, -x
2
w
V.
+
w
0x
+ w
TERM (A.1)
TERM (A.2)
V /+ 2 and
For TERM (A.1). By appling Lemma C.5 of (Huang et al., 2023), restated in Lemma 6, with To b = maxte(T]]
2 < 1, we have with probability at least 1 - 6, Vl 2 1,
de
Σ
min
To
2
2
S
( (1g
(log3TT) 1-
+ To 2 2
27
2
0s
+
8
by choosing 70- 2ee(log 37)
have To
(V2x(( 1+
1+E (log 3T) 1= 7o
27 log
o which means
(log 22
min
13s
Ts [50]
2
w
S 6
22n(log 3
log
27 8
i+ 2
(24)
+ w
For TERM (A.2). Since oe 2 2/22 | bly, 1. which means aw?
Xt
< 1/8, then we have
V
X_ 0. x 0g
2
W
x 00 - X,
2
20:
0.
0.
(25)
0s
+ W
0x
X.xX
Combining (24) and (25), we have with probability at least 1
1
(l. v 6a
I-e (
2nogg 37)
I-c 2[+00
log
27
i
2
1
Σ
0,
0.
2
8
4
x.x
Thus we complete the proof.
B.4. Proof of Lemma
Proof. We first analyze the upper bound of single term.
Vi,(0,) - v2, O. - 0.) IA.
Vi,(0)) - (&(0.)) + (e,(0,) - -V.( -8.) 1
= (Vi(0)) + V&(O.)- Ve. 0. - 0.) LA, + (V.) ( O. - -0.) -0.) il
(B.1)
TERM (8.2)
15

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
For TERM (B.1). We define (z) as the gradient of Huber loss function (5), then we have
2
if [ S T
()(2))
TB if z Ttp
(26)
Tb
if 2 < Tt--
Based on (12) and (14), Vl,(0) (z))) X, ai
and (e, = (=((((() (1())) X; which means
((((0)) + V4(0.) ve,00), 0 0. ) 1A
0x,00-00 Ae
(v:) (z)()) ()(2 (0.) (0.))
Ot.
we first analyze term (z.())) (0.)) (0.) (0.)) When event A, holds, similar to (18), we have
=x((0.) - 2.(0.)
x, 0:
X,
0.
Tt 2
S
Ot
then based on (26), we have (0,))(0,) - (0.)) = (0)) (0.). Next, we analyze the different situation of (0.).
When (z=) < T we have
1=(0i)= - -22((,)) -2) + =x((0)) s
||((0))) (2)(0)) - (1(0 + (2,(1 =
Tt Tt 7 +
= Te.
(27)
2 2
based on (26) we have
(2.() (2..))
(z.) -vv(())))
22 = =0) - (x.) 2.) + (0.) = O.
For another situation such that [z,().)| 7. based on (26) have
v.(zz - (=(2)(()) - v2l2 - -x - [ + (z. + (0.)) - (0.)) $ 3t.
(28)
Combine this two situations (27) and (28), we have for TERM (B.
v - - - 0.) 1
Xx, - 0.)
(wa(z((0)) (0.)) - (..) =x(0)))
1l
0t
S ((())((0)) (=.)))) (0. (0.))
X
0, 00
ll a
< 1 12 (0.))
1 0 1 {12((0))1>
Tt
2
3T.
X,
0, 0,
vi
1
V,
V1 + wi
S 1 ((.))
>
" {
2 }
3ro
(2(1
/ow,31-1
Wt
1 [=x(0_))
1- 3roy a + aw?t
B
2
S 11 [2(()))
>
o f
3
a g
Tut
((+))
B
2
16

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
where the third inequality comes from the definition of event A, and the last third inequality comes from o, 2 2v2 [xclvzz)
such that oxwi" =
Xx
V S 1/88. Then sum up for l round, and we have
Vi.(0.) + VV.(0))
- -. 1,, 1,. s 33/ a+ +
Σ
B--1 1 (2,(1 >
8
8
2
gm1
S 3 a+
Tot |TiTC
max 3g [E[+++]
1
}
8
-=1
where the last inequality comes from that maX 8e-1 S m P--1 Same as Eq. (C.12) of Huang et al. (2023), by setting To as (17), with probability at least 1 - 6, for all f. 2 1, we have
Σ
(20000())) >
Ts
23
27
log
2
3
5
then we have for TERM (B.1), with probability at least 1 1- for all 1llt
VE, 0.) 2.)1AA 11, S 23
a
1
log
27
Tatzitee
max oE((+1]
36-1)
(29)
8
For TERM (B.2). We first have
- -e,(()))...0.)) - (0.) 1A = Σ (2o(()
Xg _ 0, - 02 IA
(30)
Xg
0, 0. >
(2. (64))
03
where the last inequality comes from that 1 S 1. Then, Lemma C.2 of Huang et al. (2023) (Self- normalized concentration)
shows that by setting To as (17) and b = max 21 < 1, we have with probability at least 1 26, Vt 2 1,
Σ the (z. (0.))
X₂
27
+
< 8t 21 v 2ngg 3T) ((का
log
(31)
5
where V/ = >a + E'=
X and k = dlog (1+
1.2T Amd
Now we need to convert it into a 1-dimensional version, if
Zg is scalar, we have:
(E (o)) _
Z
ve (2.
da + Σt=1
z
7-
o7
Based on inequality (31), we have
EEtm (0.))
x
8t v 2n(log 37) कلाоo
1-
log
27 0
I+f
Aa + s=
Σt_
Σ th (0.))
7,
(x Aa Σ
88 8880
I- 22x(log 37)
I-c 2045)
loog
2T2
))
2
o?
0x
==1
Then based on AM-GM, we have
Σ (=((z( 2.
{
1 Xa
Σ
1- (| V2x(log 37)
llgg
27
1f.
+
x
8
s=1 1
17

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
where we use v Vab= I a + b. Let Z. = (x., 0. 0.). then put it back to (30), for TERM (2), we have with probability at
least 1 - -2,, 14 2 1,
Σ - 0l. - -0,) S / Aa Σ
1
Xe 0g - 0. )
0.)
0s
s=1
(32)
272 1tr) 2
88 (2og 37) 2(122]
log
Combine (29) and (32) together, with union bound we have with probability at least 1 - 36 .V 2 1
27
ve, - 8.) DA. S 23 a+ 1 log
Tot got
max sE([+11
Ba-1
8
+
1 1
da +
Σ
_
Xx 0. - 0. 0.))
81 ف 2n 37) शोकल
log
21 T 8
0x
am1
B.5. Proof of Lemma
Combining the results of Lemma 4 and Lemma 5, with applying the union bound, we obtain that, with probablity at least 1- 46, the following holds for all 2
Proof.
4A5² + Σ (l. 2
+ +
(V.(0.)-
- -0.) 1A. +
1 a
-
Σ
0.
0,
x. ?
s=1
2
2T
S 4X52 + Ga
| v 2nologg 37) 201t
log
8
+
0, 02
X.XT
8=1
+ 46
a +++
log
2T
te Tut Tu
max 8o-1 sE|t+1]
+
Aa
+
X,
0 0
2
8
8
2
1=1
2
27 log 8
+2
8/ 220(lo 3 श.ा.
+
Σ
0g 0
a
< 94 log
2T
Tot
max +EL++
8--1) + A(2 + 452)
+ 152
log
2T
Tot
1-c
8
where the least incquality comes from that a = 4, and
27 log
27 8
1fc
8 Tot [0+0]
t t0 22n(log 3 2[+)]
log
Then we choose Vt 2
27
= 107 log
प (2
5
and we can varify that with probablity least 1 46, the following holds for all 2
B7 2 4182 +
Σ Ve. 0e)
1-- +
VZ. - ve. - 0z) 1
I=1
(33)
( Σ
0_
0.
2
x
of
18

---

Haave-Tailed Linear Bandits: Huber Regression with One-Pass Update
Let B denote the event that the conditions in (33) hold 17 2 1, then P(B) 2
46. We now introduce new event C that
define
C 1i 2 1,
0. 0.l, S Sh
x n Ar.
In the following we will show that if B is true, must be true, which means P(C) 2 P(B) 2 48 by mathematical
induction. When 1, A₁ true by definition such that [0 0z 8011v, S v S VA(2 + 452) Su. Suppose that
iteration 1, for all 8 E [4], A, is true, then we are going to show that A4+1 is also true.
0o.1 0, -
V2
< 4ASS2 + Σ
Vea (0.)
+
Σ
(O.) V(, - -0.) + -2-11) Σ
0. 0. X
V.-1
s=1
4XS + Σ
(e. |
+2 ((.) VL, - 8.) 1 (--1)
Σ
0 0
K
S 3
where the first inequality comes from Lemma 3, the second equality comes from that Vs [t] A, holds, and the last inequality comes from condition (33). As a result, we can conclude that all (A,)22 is true and thus we have (P(C) 2 1 45. And further we can find that
x Br-1
107 log 272 5 Tot 2(40) + 42(2+450 48²)
[ 2 V107 2 2V2 2/2l|Xellv7]
Varat ाानल
thus by setting
||x |xell2== 3e-1
w
22k (lo 37) 20
0, max
Vt, minu:
Tot (040)
To To
W1
(,(+9)
To
(log 24-2) +
we obtain for any (0, 1), with probablity least 46, the following holds for all 2 1,
|0+t1 - 0.112 s 1007 log
2T
l-
(0+0) + +
5
C. Regret Analysis
C.1. Proof of Theorem
Proof. Let X; = arg maxxex, x T O.. Due to Lemma and the fact that X; X₁ E Ne, each of the following holds with probability at least 1 - 48
Vt [T].
X; 0. < x; 0. + B ||
WL E (7),
XTO. 2 x, 0, 3 X Xellvz
By the union bound, the following holds with probability at least - -85
14 [T], X; 0. x, 0. S x; 0, X, B (1xillvzz + [xellvz) 2 (2lll) 1| ||x
19

---

Haavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
where the last inequality comes from the arm selection criteria (11) such that
X 0. + 9 || S Xx 0. + BB-1 [|
Hence the following regret bound holds with probability at least - 86,
T Σx1
T
T
T
REGT x;
8,
x, 0. - 2 Σ
| | = 48T Σ
0,00
t=1
1=1
27 where B7 = 1077 2(+)) To log 5 + (2 452).
Next bound the of bonus Σ W separately by the value of ot. Recall the definition of o in Algorithm decompose [T] as the union of three disjoint sets J2,J2.
|| 3
I1 = (t E minn) T2 =
[T at =
(34)
1- Tol 2(140)
For the summation over J1, since miin
VT*
T
T
T
Σ or = Σ
max {vr, mmin wi Σ
Σ
(v² + o
Σ 1=1
wF S /2K
Σ 1=1
1 +1,
min
where the last inequality comes from Lemma
For the summation over J2, we first have
B 1071 2124 To log
27 + (2
(2 + 4
27
W/
107 log
Tgl X1कक
Tol .ा
To
8
we denote c vA(2+455)
107 log à
27
and have
Σ oww
Σ
1xoll
cL
Σ w <
cLR
(35)
TEJ2 wi
2v)
TEJ
tEJa
where the last inequality comes from Lemma 7. Combining these two cases together, by choosing d = 87 A d, we have
(1
)
cLK
(Vamaatoo
REGT
4,T
V2R
Σ
VX
1=1
T
I-t dT
2 + dT l-m
Thus we complete the proof.
C.2. Proof of Corollary
Proof. Proof Corollary is similar to Theorem 1, only need to change the condition J. (34) to T {t E [T] or {v, ]min) and for the summation over Jn since Jmin
VT
Σ o.wi Σ
max (v, Jmin w/ S (v2 + oi
Σ wa s V
(36)
IET
BET.
20

---

Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update
where the last inequality comes from Lemma 7. Then combine condition (36) with condition (35), by choosing 6 d, we have
T S 45T Σ 1=1
REGT
Jww S 543r
+ (V2KVV++++
CLR
s 20
( 1-c
(Vdent+va)
δ (dv(
Thus we complete the proof.
D. Technical Lemmas
This section contains some technical lemmas that used in the proofs.
D.1. Concentrations
Theorem 2 (Self-normalied concentration for scalar (Abbasi- Yadkori al., 2012, Lemma 7)), Let {Fi]== be a filtration. Let {n ) be real-valued stochastic process such that qe is F--measurable and sequence of real-valued variables such that Ze is F1-1---at fi---measurable. Assume that V >> 0 be deterministic. For any > 0, with probability at
Let [7+ ) be
least 1 - 5:
VV++ E.m Z2 8VV
V 2
11 Z
S
R
V +
7 In
Lemma (Lemma C.5 of Huang al. (2023)). By setting Tt
TO
assume Stt
Fi-1 f
and
Wi
oz
1+s
m
Fi-1 bl+e, Then with probability at least 1 5, we have Vt 2
a
min
1l
(Lgg)) /0// log 8
212
1 w²
D.2. Potential Lemma
Lemma 7 (Elliptical Potential Lemma). Suppose Up = Xl, U2 = U2-1 + X,X,, and ||eella S L, denote Vt 2
2
U,
X,
S
Cmax, then
2
Σ
T
U 1 X
||
2 < maxf1, Cmax Id (1+ (1+ L'T
(37)
Ad
Proof. First, we have the following decomposition,
= U-= + = - -
Taking the determinant on both sides, we get
det(Ui) det(U U (
which in conjunction with Lemma yields
(U.) = det(UU,))(1 + 10 det(UU-))) (1+
10 10 Xx
max Cmnax
Cmax
21

---

Heavy-Tailed Lincar Bandits: Huber Regression with One-Pass Update
2 det(Ur-1) maxx11, Gmax) 10 xx
Note that in the last inequality, we use the fact that 10,-1X, I Caax and + x 2 exp(x/2) holds for any æ E [0, By taking advantage of the telescope structure, we have
Σ DI 2max (1, Cunxx log det(UT) det(Uu)
S 2 max Cmax Idlo (1+ L'T
Ad
where the last inequality follows from the fact that Tr(UT) & Tr(Ub) + L = Ad + L2T, and thus det(Un) (X + I/T/d)4
Lemma (Lemma of Zhao al. (2020a)). For any RR we have
det(I + vv = 1 l|v12
D.3. Useful Lemma for OMD
Lemma (Bregman proximal inequality (Chen Teboulle, 1993, Lemma 3.2)). Let be convex set in a Banach space. Let X' + R. be closed proper convex function X. Given convex regularizer X R, we denote its induced Bregman divergence by :.)..)) Then, any update of the form
X5: = arg min {f(x) + De (xx)
xEX
satisfies the following inequality for any u E X,
f fxx)) f(u) s Do (x,x Di (u, De (Xk, x6-1)
E. Additional Experimental Results
In this section, we provide additional experimental results to validate the effectiveness of our algorithm. Appendix E. shows the experiment of different noise distributions, Appendix E.2 presents the experiment of varying Vt, and Appendix E.3 provides the experiment of varying arm set.
E.1. Experiment of Different Noise Distribution
OFUL
CRTH
CRTN
CAMM
PaaayOOUL
HeRNyGFUL
X0X
Reagru
X00
100B
2000
2000
-003
305
(a) Pareto distribution
(b) Lomax distribution
(c) Fisk distribution
Figure 3: Experiment of Different Noise Distribution
We consider three classic heavy-tailed distributions: (a) Pareto distribution, (b) Lomax distribution, and (c) Fisk distribution. We implement all three distributions using Python's scipy.stats. For the Pareto distribution, we set b 1.5; for the Lomax and Fisk distributions, we set 1.5. We set g 1.49, ensuring that the (1 + m)-moment exists. In the experiments,
Configurations.
time-varying noise scale, consistent with the setup in Figure 4.
Results. We conduct 5 independent trials and averaged the results. Figure 3(a), 3(b) and 3(c) show cumulative regret under different noise distributions. In both settings, our algorithm performs similarly to Hcavy-OFUL, demonstrating competitive performance. Note that the CRMM algorithm performs poorly across all three distributions, as can only handle symmetric noise, while these distributions are symmerrtt.i... In summary, this experiment validates the effectiveness of our algorithm handling various noise distributions.
22

---

Haave-Tailed Lincar Bandits: Huber Regression with One-Pass Update
E.2. Experiment of Varying %
600
6030
30X
OFUL
OFUL CRTN CRMM
CRTN
CRTN
168
CAMI
CAMM
HeavyOrUL WeUCB
MeasyDFUL
HeaxyCFUL
1000
HWtCCB
HAAUC
Reogeet
3008
2003
2000
3000
130
3036
$000
1300
2006
3000
4000
5006
500
1800
200
3003
-003
3000
606
(a) scale of Ve
(b) scale
(c) scale of V 2.5
Figure 4: Experiment of Varying Pt.
Configurations. In this experiment, we consider a Student's t-distribution with time-varying noise scale. Specifically, we fix the degrees of freedom as df = 1.7 and set E = df - 0.01. At each round, noise is first sampled from Student t(df) and then scaled by a factor a, where log 1o ( ~ Unif(0, scale), so that the central moments & vary across rounds. this setting, existing algorithms can only rely on an upper bound of the noise variance, whereas our proposed HvtLB algorithm leverages the actual per-round variance for more accurate and adaptive scheduling. This setting follows the experimental setup proposed by Huang al. (2023).
Results. We test different scales of with scales of 1.5, 2 and 2.5 in Figure 4(a), 4(b) and 4(c). In all environments, HvtLB and HeavyOFUL, which have variance-aware capabilities, outperform other algorithms significantly. In contrast, OFUL performs the worst because it lacks both variance-awareness and the ability to handle heavy-tailed noise.
E.3. Experiment of Varying Arm Set
OFUL HENIyOFUL
HEIXYOFUL
HERXYOFUL
Foughe
2008
2002
20X
100
1030
10
(a) fixed arm set
(b) varying arm set 40/50
(c) varying arm set 30/50
Figure Experiment Varying Arm Set Case.
Configurations. In this experiment, we create total arm set with 50 arms, which are pre-sampled before the experiment begins. make the arm set varying, in each round, we randomly select a subset from X' as the current arm set X,, from which the algorithm can choose arms. this case, the regret based on the best arm in each round, rather than the global optimal arm. We consider three scenarios: (i) the arm set X₁ X' with 50 arms, (ii) randomly selecting 40 arms in each round, and (iii) randomly selecting 30 arms in each round.
Results. We conduct 5 independent trials and averaged the results. Figure 5(a), 5(b) and 5(c) show cumulative regret under different levels of arm set changes. all settings, our algorithm performs the best, while HeavyOFUL and CRTM also achieve competitive results. However, when the arm set varies, the MOM-based algorithm fails. This is because MOM-based algorithms assume a fixed arm set and rely on resampling. When the arm set changes, resampling the same arms possible, so the algorithm selects the closest available arms instead. In summary, this experiment validates the effectiveness of algorithm in scenarios where the arm set time-varying.
23


Reviews:
[{"review_id": "6bNYZpnjkV", "reviewer": "Reviewer_McYB", "summary": "This paper proposes a novel, computationally efficient algorithm for heavy-tailed linear bandits that achieves the best-known regret bound in the literature.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful review! In the following, we will address your main concerns and report additional experiments.\n\n---\n\n**Q1.** \"How will the empirical performance of the algorithm vary with changing $\\nu_t$? I suggest the authors provide results for varying $\\nu_t$ to support the claim that the algorithm is adaptive to $\\nu_t$.\"\n\n**A1.** Thanks for the suggestion. We have conducted additional experiments of time-varying $\\nu_t$ to further support the variance-aware property of our method. We summarize all the details and results in the following anonymous URL: https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf\n\nPlease refer to Figure 2 of this anonymous URL for details. We will add these results in the revised version.\n\n---\n\n**Q2.** \" The novelty seems limited, as the challenges of combining online mirror descent with heavy-tailed bandits are not discussed clearly. Could the authors provide specific challenges in deriving the results of applying online mirror descent to heavy-tailed bandits?\" \n\n**A2.** Thank you for the comments. We believe there may have been a misunderstanding due to our insufficient emphasis on the challenges of applying OMD to heavy-tailed bandits. We will revise the paper to ensure this aspect is presented more clearly. Here, we'd like to take this opportunity to clarify these challenges.\n\n- **Challenge 1: Using one-pass OMD to approximate full-batch MLE.** The offline MLE estimator leverages the entire history of data, enabling its estimation error to be well-controlled. In contrast, OMD updates the one-pass estimator using only current data, making it inherently challenging to ensure the final regret remains unaffected. While OMD is known for its effectiveness in minimizing regret, adapting this capability into a good statistical estimator is far from straightforward. In fact, as shown in Section 4.1, even under Sub-Gaussian noise (a significantly easier scenario), deploying OMD requires: (i) carefully designing the local norm to collaborate with self-normalized concentration, and (ii) properly using the negative term in the regret analysis to control the generalization gap.\n- **Challenge 2: Handing Huber loss and heavy-tailed noise.** In the heavy-tailed setting, deploying OMD as a one-pass estimator is even more challenging. The primary difficulty arises from the curvature of the Huber loss, which is partially linear (undesired region) and partially quadratic (desired region), necessitating careful control of the threshold. Furthermore, in the estimation error analysis, the bias introduced by the one-pass OMD update manifests as an additional stability term that can grow as $\\mathcal{O}(\\sqrt{T})$. It is critical to carefully design both the adaptive normalization factor of the Huber loss and the learning rate in OMD, together to effectively manage the estimation error.\n\nWe will revise the paper to ensure these challenges are clearly elaborated.\n\n---\n\n**Q3.** \"In Lemma $1$, $\\sigma_{\\min }$ is used without being defined beforehand.\"\n\n**A3.** Thank you for the detailed review! We will correct this in the revised version, specifically, $\\sigma_{\\min }$ is a small positive constant to avoid singularity, and we provide the setting of $\\sigma_{\\min}$ in Theorem 1.\n\n---\n\n**Q4.** \"Is there a way to remove the requirement for knowledge of the horizon time $T$?\"\n\n**A4.** Thanks for the question. The requirement of a known time horizon $T$ can be removed using the doubling trick. Specifically, we let the algorithm restart at time steps $2^1, 2^2, 2^3, 2^4, \\ldots, 2^M$. If the time horizon is $T$, then the total number of intervals is $M \\approx \\log T$. When the time horizon is known, the regret bound is $\\widetilde{\\mathcal{O}}(T^{\\frac{1}{1+\\epsilon}})$. Since the length of each interval $2^m$ is known in advance, we can apply the same bound within each interval. Then the overall regret can be calculated by:\n\n$$\\widetilde{\\mathcal{O}}\\left(\\sum_{m=1}^M\\left(2^m\\right)^{\\frac{1}{1+\\epsilon}}\\right)=\\widetilde{\\mathcal{O}}\\left(\\sum_{m=1}^M 2^{\\frac{m}{1+\\epsilon}}\\right)=\\widetilde{\\mathcal{O}}\\left(2^{\\frac{1}{1+\\epsilon}} \\frac{2^{\\frac{M}{1+\\epsilon}}-1}{2^{\\frac{1}{1+\\epsilon}}-1}\\right)=\\widetilde{\\mathcal{O}}\\left(\\frac{2^{\\frac{1}{1+\\epsilon}}}{2^{\\frac{1}{1+\\epsilon}}-1}\\left(T^{\\frac{1}{1+\\epsilon}}-1\\right)\\right) = \\widetilde{\\mathcal{O}}(T^{\\frac{1}{1+\\epsilon}}).$$\n\nIn this way, we are able to remove the requirement of known $T$ in advance, while still achieving a regret bound of $\\widetilde{\\mathcal{O}}(T^{\\frac{1}{1+\\epsilon}})$, up to a constant factor overhead.\n\n---\n\nThanks again for your insightful comments. We will add more experiments and improve the presentation in the revised version.", "claims_and_evidence": "The claims are clear and supported by convincing evidence from the literature.", "methods_and_evaluation_criteria": "The methods and evaluation criteria follow standards in the literature.", "theoretical_claims": "The proofs are based on standard techniques for heavy-tailed distributions and online mirror descent", "experimental_designs_or_analyses": "While the experimental design is standard, I suggest the authors provide results for varying $\\nu_t$ to support the claim that the algorithm is adaptive to $\\nu_t$", "relation_to_broader_scientific_literature": "As the authors mentioned in the discussion section, their results are applicable to linear Markov decision processes and online adaptive control. Because online estimation for heavy-tailed distributions is not well established in bandits or reinforcement learning, I believe this work will have a wide impact on those literatures", "essential_references_not_discussed": "All the essential related references are discussed in the paper.", "other_strengths_and_weaknesses": "Strengths: The paper is well-organized, with a thorough discussion that is easy to follow as well as with clear motivation.\n\nWeaknesses: The novelty seems limited, as the challenges of combining online mirror descent with heavy-tailed bandits are not discussed clearly.", "other_comments_or_suggestions": "In Lemma 1, $\\sigma_{\\min}$ is used without being defined beforehand.\n\n\n\n============== After Rebuttal ================\n\nI appreciate the authors detailed responses.\nI acknowledge that this work has novel contribution on heavy-tailed bandits.\nPlease highlight the responses in the revision for clarity, especially on the novelty.", "questions_for_authors": "Q1: How will the empirical performance of the algorithm vary with changing $v_t$?\n\nQ2: Is there a way to remove the requirement for knowledge of the horizon time $T$?\n\nQ3: Could the authors provide specific challenges in deriving the results of applying online mirror descent to heavy-tailed bandits?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iYca0oUe9V", "reviewer": "Reviewer_C6wo", "summary": "The paper proposes a method for linear bandits with heavy-tailed noise variable, that efficiently estimates the bandit parameter with a single pass through the data and doesn't require processing the complete historical data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your suggestions on experiments and literatures. We will revise the paper accordingly. However, there is an important misunderstanding regarding our technical contributions that we need to clarify.\n\n---\n\n**Q1.** \"contribution is not significant...only contribution is the replacement of the batch GD with OMD...\"\n\n**A1:** We respectfully disagree with the comments. The SOTA method (HEAVY-OFUL) [Huang et al., 2024] adopts an offline MLE estimator and achieves optimal regret for heavy-tailed linear bandits. However, ensuring the one-pass\" property is crucial for online algorithms to ***update efficiently without storing the entire historical data***. Our work builds on HEAVY-OFUL and develops an OMD-based one-pass algorithm, while also ensuring that the final regret remains unaffected. **This is technically highly non-trivial.** We believe it is unfair to describe as merely \"replacing the batch GD with the OMD algorithm for online per-sample updates\". Below, we outline the technical challenges in more detail.\n\n- **Challenge 1: Using one-pass OMD to approximate full-batch MLE.** The offline MLE estimator leverages the entire history of data, enabling its estimation error to be well-controlled. In contrast, it is intuitively non-trivial to develop a one-pass estimator (which uses only the current data) while still ensuring that the estimation error remains as good as the offline MLE estimator. In fact, as shown in Section 4.1, even under Sub-Gaussian noise (a significantly easier scenario), deploying OMD requires: (i) carefully designing the local norm to collaborate with self-normalized concentration, and (ii) properly using the negative term in the regret analysis to control the generalization gap.\n- **Challenge 2: Handing Huber loss and heavy-tailed noise.** In the heavy-tailed setting, deploying OMD as a one-pass estimator is even more challenging. The primary difficulty arises from the curvature of the Huber loss, which is partially linear (undesired region) and partially quadratic (desired region), necessitating careful control of the threshold. Furthermore, in the estimation error analysis, the bias introduced by the one-pass OMD update manifests as an additional stability term that can grow as $\\mathcal{O}(\\sqrt{T})$. It is critical to carefully design both the adaptive normalization factor of the Huber loss and the learning rate in OMD, together to effectively manage the estimation error.\n\nOverall, we believe these technical contributions are not only interesting to the bandits community but also have a broad impact on the audiences of online MDPs and online adaptive control. We will improve the paper's writing to emphasize these points more clearly. Thanks!\n\n---\n\n**Q2.** \"offline bandit learning could be explored more\"\n\n**A2.** Thanks for pointing out the literature on offline bandit learning, which relates to managing extreme values caused by importance weighting. We are happy to incorporate a discussion in the revision.\n\n---\n\n**Q3.** \"Experiment setup is very limited and insufficient to prove the claims\"\n\n**A3.** We'd like to emphasize that our paper primarily focuses on the theoretical side, which we have elaborated the technical contributions  in detail (please refer to **A1**).  Experiments are intended to support our theoretical findings. \n\nWe are happy to conduct additional tests to better address your concerns, and new results and plots are summarized in the following anonymous URL: https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf\n\nConcretely, we add experiments of various heavy-tailed noise (including Pareto, Lomax, Fisk); time-varying $\\nu_t$; varying arm set case; more comparation about empirical advantage of our methods. We will include these additional tests in the revised version. Hope these will address your concerns.\n\n---\n\n**Q4.** \"It is claimed that the method can be adapted to more generalized decision-making ... but no theoretical or experimental evidence is provided\"\n\n**A4.** Without a doubt, the linear bandit model is fundamental in online learning. Our work makes an important step for linear bandits with heavy-tailed noise. As mentioned, our technical contributions are already substantial enough to gain interest from the community.\n\nGiven the importance of linear bandits, the discussion in Section 5 is intended to highlight the potential of our Hvt-LB algorithm to broader decision-making scenarios. However, we prefer not to spend more spaces for those extensions to avoid diverting readers from the main focus, i.e., linear bandits. We believe our techniques will be of interest to audiences working on online linear MDPs and adaptive control.\n\n---\n\nWe appreciate your suggestions and will add additional experiments and related works accordingly. We will also emphasize technical contributions more clearly. If our clarifications have adequately addressed your concerns, please consider updating your score. Thanks!", "claims_and_evidence": "It is claimed that the method can be adapted to more generalized decision-making scenarios, such as reinforcement learning, but no theoretical or experimental evidence is provided, even though a discussion is provided.", "methods_and_evaluation_criteria": "The evaluation criteria are standard, as regret bound and time complexity are the common metrics in the literature.", "theoretical_claims": "The theoretical claims are built towards a single, important theorem: the regret bound. The proof sketch provided in section 4 make the proof process easier to follow. The major part of the theoretical stuff focuses on the estimation error of the bandit parameter, which is essential for a regret analysis.", "experimental_designs_or_analyses": "The. experiment setup is very limited and insufficient to prove the claims of the authors.\n1. One of the claims of the paper was that previous studies assumed a fixed action set, while the proposed method doesn't require such an assumption. But in the experiments, the action set is a fixed set of 50 arms.\n2. The same statement can be mentioned. for the case of Reinforcement Learning or other decision-making scenarios.\n3. There is a vast range of heavy-tailed distributions, but only student-t distribution is tested in the experiments, which is specifically very similar to normal distribution, hence the good performance on only the t distribution is not enough.", "relation_to_broader_scientific_literature": "The contribution of the paper is not significant and essential. Compared to the Heavy-OFUL, whichi is a strong SOTA in the literature, the only contribution is the replacement of the batch GD with OMD algorithm which allows an online per-sample update. The idea of Huber loss and its application on heavy-tailed linear bandits have been thoroughly discussed in Heavy-OFUL and the OMD algorithm is a well-known optimization algorithm. Yet, the theoretical analysis of the combination of OMD with huber objective can be views as the only contribution of the paper.", "essential_references_not_discussed": "The literature of the offline bandit learning could be explored more. Especially off-policy evaluation, where MOM and truncation methods are provided to tackle heavy-tailed noise and outlier effect. For example, the following papers could be studied and reviewed.\n \nSakhi, Otmane, et al. \"Logarithmic smoothing for pessimistic off-policy evaluation, selection and learning.\" arXiv preprint arXiv:2405.14335 (2024).\n\nBehnamnia, Armin, et al. \"Batch Learning via Log-Sum-Exponential Estimator from Logged Bandit Feedback.\" ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists.", "other_strengths_and_weaknesses": "The contributions of the paper are weak. Altogether it provides a theoretical analysis of huber-based linear bandit parameter estimation with OMD optimization, with insufficient experimental evidence.", "other_comments_or_suggestions": "I don't have any particular suggestion.", "questions_for_authors": "The paper's structure is clear. I don't have any question.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1f6nYSgEGg", "reviewer": "Reviewer_kVUc", "summary": "This paper studies the heavy-tailed linear bandits problem. Doing OMD on the Huber loss, the authors yielded an algorithm with near-optimal $\\tilde{\\mathcal O}(d T^{1/(1+\\epsilon)})$ regret which only needs $\\mathcal O(1)$ computation per round (instead of doing a huge Huber regression as previous ones in the literature). Furthermore, the algorithm also attains a \"variance-aware\" property that automatically scales with the $(1+\\epsilon)$-th moments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable feedback and appreciation of our work! We will revise the paper accordingly. Below, we answer your questions.\n\n---\n\n**Q1.** More discussions about algorithms without knowledge of $\\epsilon$ and $\\nu_{t}$ in advance.\n\n**A1.** Thanks for the suggestion. Relaxing this assumption is indeed an important direction for future research of heavy-tailed bandits. The literature and techniques you mentioned for removing the need for known $\\nu_t$ could potentially be adapted to the heavy-tailed setting. We will include a more detailed discussion of these works in the revised version.\n\n---\n\n**Q2.** \" Is there any similar self-bounding concentrations in the world of heavy-tailed distributions? If yes, could you briefly explain what's the main issue when doing it for the learning setup?\"\n\n**A2.** Thanks for the question. As far as we know, Existing results based on empirical variance typically require either a bounded norm or sub-Gaussian assumption which is not applicable to heavy-tailed distributions, since in the heavy-tailed setting (e.g., when only the $(1+\\epsilon)$-moment is bounded), the empirical variance itself can be unbounded.\n\nBesides, after our submission, we noticed a recent paper published on arXiv that studies the heavy-tailed bandit setting (with $\\epsilon = 1$) and claims to eliminate the need for knowing the variance using a peeling-based algorithm, under certain assumptions [1]. Although we have not studied the paper in detail yet, we believe its result is noteworthy.\n\n[1] Ye et al., Catoni Contextual Bandits are Robust to Heavy-tailed Rewards. \n\n---\n\nWe are grateful for your careful review! We will provide more discussion about the literature you suggested in the revised version.", "claims_and_evidence": "The theorems are complemented with easy-to-follow sketches.", "methods_and_evaluation_criteria": "The setup and notation is standard and consistent with previous works in the literature.", "theoretical_claims": "I didn't check the details of the proof, but the sketches are convincing enough.", "experimental_designs_or_analyses": "The numerical illustration is valid.", "relation_to_broader_scientific_literature": "Can be interesting to other problems with heavy-tailed distributions; but mostly talored towards the heavy-tailed linear bandits", "essential_references_not_discussed": "Looks good. See questions for some not-so-related ones.", "other_strengths_and_weaknesses": "Strength:\n\n1. The writing is pretty clear, introducing previous ideas on heavy-tailed linear bandits and highlighting the technical difference / innovation.\n2. The analysis sketch is well-written, making it easy to follow.\n\nWeakness:\n\n1. The algorithm requires knowledge of $\\epsilon$ and $\\nu_t$. I feel it's acceptable as it's the common challenge for heavy-tailed linear bandits (see Q1 & Q2).", "other_comments_or_suggestions": "No", "questions_for_authors": "1. Looks like all previous heavy-tail linear bandit algorithms require the exact knowledge of $\\epsilon$ and $\\nu_t$. Recently this has been relaxed in the heavy-tail multi-armed bandit literature: [1] for the adversarial case, [2] for the stochastic case, and [3] for both (\"best-of-both-worlds\"). I know the techniques here and there are substancially different, but it'd be great to still give some discussions.\n2. Also, regarding the knowledge of $\\nu_t$, there has been Empirical Bernstein inequalities which removes this for standard linear bandits [4, 5]. Is there any similar self-bounding concentrations in the world of heavy-tailed distributions? If yes, could you briefly explain what's the main issue when doing it for the learning setup?\n\n[1] Jiatai Huang, Yan Dai, and Longbo Huang. \"Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits.\" ICML 2022.\n\n[2] Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. \"(ε,𝑢)-Adaptive Regret Minimization in Heavy-Tailed Bandits.\" COLT 2024.\n\n[3] Yu Chen, Jiatai Huang, Yan Dai, and Longbo Huang. \"uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs.\" ICLR 2025.\n\n[4] Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. \"Improved variance-aware confidence sets for linear bandits and linear mixture mdp.\" NeurIPS 2021.\n\n[5] Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun. \"Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps.\" NeurIPS 2022.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9z7wSoTh1Y", "reviewer": "Reviewer_ZqBj", "summary": "This work introduces a new algorithm, inspired by [1], where solve the computation issues with the algorithms in [1].", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful suggestions. Below we will address your main concerns regarding the technical contributions and report additional experiments.\n\n---\n\n**Q1.** about the contributions (\"Compared to [1], the contribution of this work is incremental\", \"elaborate on the main theoretical contributions in relation to [1]\")\n\n**A1.** Thank you for the comments. We believe there may have been a misunderstanding due to our insufficient emphasis on the technical contributions, particularly the challenges of applying OMD to heavy-tailed bandits. We will revise the paper to ensure this aspect is presented more clearly. Here, we'd like to take this opportunity to clarify these challenges and further emphasize our contributions.\n\n- **Challenge 1: Using one-pass OMD to approximate full-batch MLE.** The offline MLE estimator leverages the entire history of data, enabling its estimation error to be well-controlled. In contrast, OMD updates the one-pass estimator using only current data, making it inherently challenging to ensure the final regret remains unaffected. While OMD is known for its effectiveness in minimizing regret, adapting this capability into a good statistical estimator is far from straightforward. In fact, as shown in Section 4.1, even under Sub-Gaussian noise (a significantly easier scenario), deploying OMD requires: (i) carefully designing the local norm to collaborate with self-normalized concentration, and (ii) properly using the negative term in the regret analysis to control the generalization gap.\n- **Challenge 2: Handing Huber loss and heavy-tailed noise.** In the heavy-tailed setting, deploying OMD as a one-pass estimator is even more challenging. The primary difficulty arises from the curvature of the Huber loss, which is partially linear (undesired region) and partially quadratic (desired region), necessitating careful control of the threshold. Furthermore, in the estimation error analysis, the bias introduced by the one-pass OMD update manifests as an additional stability term that can grow as $\\mathcal{O}(\\sqrt{T})$. It is critical to carefully design both the adaptive normalization factor of the Huber loss and the learning rate in OMD, together to effectively manage the estimation error.\n\nWe will revise the paper to ensure these challenges and our technical contributions are clearly elaborated.\n\n---\n\n**Q2.** About experiment  \"explore the case where the degree of freedom satisfies $1<df\\leq 2$\"\n\n**A2.** Thank you for the suggestions. We have conducted additional experiments to address your concerns. We summarize all the details and results in the following anonymous URL: https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf \n\nPlease refer to Figure 2 in this anonymous URL for details, where we use $df = 1.7$ for the Student’s t-distributions. Additionally, we also tested other heavy-tailed noise distributions and ensured they satisfy the condition that there exists an $\\epsilon \\in (0, 1)$ such that the $(1+\\epsilon)$-th moment is bounded, which can be found in Figure 1. We will add these results in the revised version.\n\n---\n\n**Q3.** About experiment \"insufficient, as they are conducted solely on synthetic datasets\"\n\n**A3.** Thanks for your comments. We'd like to emphasize that our paper primarily focuses on the theoretical side, which we have elaborated the technical contributions in detail (please refer to **A1**). The synthetic data are well-suited for setting different configurations to support our theoretical findings. On the practical side, it might be more interesting to explore online MDPs and adaptive control, given the fundamental connection between linear bandits and decision-making problems. We believe that our proposed algorithm (with suitable modifications) could be highly useful. We leave these extensions for future investigation and prefer not to spend more spaces for them in this paper to avoid diverting readers from the main focus.\n\n---\n\n**Q4.** \"In Eq.(7), replace the notation with $z_t(\\theta)$\"\n\n**A4.** Thank you for pointing out the confusion, we will make the presentation clearer in the revised version.\n\n---\n\n**Q5.** \"heavy-tailed distributions does not encompass the sub-Gaussian case...I suggest discussing only the heavy-tailed case in Section 4 to avoid potential confusion\"\n\n**A5.** Thank you for this important suggestion. We intended to use the sub-Gaussian case as a simplified example to demonstrate how to deploy the OMD estimator in linear bandits. However, your suggestion is very reasonable, and we will revise the paper to avoid this confusion.\n\n---\n\nThanks for your helpful suggestions. We will add more experiments and improve the paper writing to more clearly emphasize the technical contributions. If our responses have properly addressed your concerns, please consider updating your score. Thanks!", "claims_and_evidence": "see Other Strengths And Weaknesses", "methods_and_evaluation_criteria": "see Other Strengths And Weaknesses", "theoretical_claims": "see Other Strengths And Weaknesses", "experimental_designs_or_analyses": "see Other Strengths And Weaknesses", "relation_to_broader_scientific_literature": "see Other Strengths And Weaknesses", "essential_references_not_discussed": "see Other Strengths And Weaknesses", "other_strengths_and_weaknesses": "Weaknesses:\n\n1- In Eq. (7), replace the notation with $ z_t(\\theta) $.  \n\n2- Compared to [1], the contribution of this work is incremental.  \n\n3- It would be beneficial to elaborate on the main theoretical contributions in relation to [1].  \n\n4- In the experiments, for a Student’s t-distribution with a degree of freedom greater than 2, the second moment is bounded. It would be valuable to explore the case where the degree of freedom satisfies $ 1 < df \\leq 2 $.  \n\n5- The current experiments are insufficient, as they are conducted solely on synthetic datasets.  \n\n6- The present definition of heavy-tailed distributions does not encompass the sub-Gaussian case. Therefore, I suggest discussing only the heavy-tailed case in Section 4 to avoid potential confusion.\n\n----\n\nReferences:\n\n[1]: Huang, J., Zhong, H., Wang, L., and Yang, L. Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds. NIPS, 2024.", "other_comments_or_suggestions": "see Other Strengths And Weaknesses", "questions_for_authors": "see Other Strengths And Weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "coy6UaU4c9", "reviewer": "Reviewer_P7Rp", "summary": "This paper proposes a one-pass algorithm for stochastic linear bandits with heavy-tailed noise, reducing per-round computational cost from $\\mathcal{O}(t \\log T)$ to $\\mathcal{O}(1)$ using an online mirror descent framework. Unlike existing methods that require storing and processing all past data, the proposed approach updates using only current round data while achieving a near-optimal, variance-aware regret bound. The authors also deduced the regret bound for the proposed algorithm, which is nearly optimal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful comments. Below, we address your main questions regarding the technical contributions, extensions to GLB, experiments, and related works. For other minor issues (e.g., typos), due to limited space, we will directly revise the paper according to your suggestions.\n\n---\n\n**Q1.** \"cannot handle the case when $\\nu_t$ is unknown, which weakens the theoretical contributions\"\n\n**A1.** Thanks for the comment. We'd like to remind that knowing the moment $\\nu_t$ is shared by our work and previous works for heavy-tailed linear bandits, and this issue is orthogonal to our main contributions.\n\n- **Relying on moment $\\nu_t$**: Note that existing works including the current SOTA [Huang et al., 2024] require the moment information $\\nu_t$, even if they can use an offline MLE estimator. Similarly, our work also faces this issue; however, in contrast, we can ensure one-pass efficiency. Handling unknown $\\nu_t$ is indeed important and challenging for the community, which is left as future work to explore.\n- **Theoretical contribution**: Even with known $\\nu_t$, designing a one-pass algorithm remains highly non-trivial due to several challenges, including using one-pass OMD to approximate full-batch MLE, and handling Huber loss and heavy-tailed noise. We kindly request the reviewer to refer to **A2 for Reviewer McYB** for more details. Thanks!\n\n---\n\n**Q2.** \"...generalize to the generalized linear bandit (GLB)...\"\n\n**A2.** In fact, there is prior work that applies OMD to logistic bandits (an important class of GLB) with sub-Gaussian noise, while our paper uses OMD for linear bandits with heavy-tailed noise. This suggests a potential combination. Nonetheless, an evident challenge is how to design a suitable Huber-type regression loss tailored to nonlinear link functions of GLB for the offline MLE estimator. We leave this as an exciting direction for future work. Thanks!\n\n---\n\n**Q3.** Experiments on several aspects (\"time-varying $\\nu_t$\"; \"the empirical advantage of HvtLB\"; \"parameter sensitivity\"; \"linear regret curves\", etc)\n\n**A3.** Thanks for those careful comments! To address your concerns, we have conducted additional experiments and comparisons in the anonymous URL https://default-anno-bucket.s3.us-west-1.amazonaws.com/HvtLB_revised_exp.pdf\n\nIncluding, varying $\\nu_t$ in Figure 2, empirical advantage in Figure 4, and linear regret issue in Figure 5. For parameter sensitivity,  key parameters in the algorithm, such as Huber threshold, are not chosen by tuning but are derived from theoretical analysis. As a result, they indeed can be relatively sensitive. We will add these results in the revised version.\n\n---\n\n**Q4.** More details on [Sun et al. 2020], and differences between [Kang & Kim] \n\n**A4.** Thanks for the helpful suggestion. In the revised version, we will include more details on [Sun et al. 2020]. As for [Kang & Kim], the similarity in titles may cause confusion. However, there are key differences in both setting and methods. \n\n- **Setting**: We focuses on linear bandits with **infinite arm set**, where context $X_t$ chosen depends on previous $\\\\{X_s\\\\}_{s<t}$. Our goal is to design a one-pass algorithm with optimal regret. In contrast, [Kang & Kim] studies linear contextual bandits with **finite arm set**, where $X_t$ is **i.i.d. sampled**. Their method is based on offline MLE and is *not* online.\n\n- **Algorithm**: Even with a similar Huber regression, the designs differ fundamentally. We use OMD with a carefully designed recursive normalization factor, while [Kang & Kim] uses offline MLE with a forced exploration mechanism. Please refer to **A5** for more details.\n\n---\n\n**Q5.** \"In [Kang & Kim] and [Kang et al.], ... if the upper bound $\\nu$ is known, then your Huber loss can be free of the normalization factor as well?\"\n\n**A5.** Thanks for the question. Our Huber loss still requires this factor, even if $\\nu$ is known. The normalization factor $\\sigma_s$ not only ensures variance-awareness but also guarantees that the denoised data lies within the quadratic region of the Huber loss. This ensures that the Hessian has a lower bound, which is crucial for the analysis. We achieve this by designing a recursive factor, where $\\sigma_t$ depends on the last round confidence bound $\\beta_{t-1}$ (see line 5 in Algorithm 1). \n\nWhile these two works avoid this factor, they introduce additional algorithmic mechanisms and assumptions to achieve a similar goal: (i) [Kang & Kim] introduces a forced exploration strategy and Assumption 4 to ensure that the Hessian has a lower-bounded minimum eigenvalue; (ii) [Kang et al.] adopts the local adaptive majorize-minimization method and Assumption 3.1 to establish the Local Restricted Strong Convexity condition (Definition A.3), which guarantees a lower bound on the Hessian.\n\n---\n\nWe are grateful for your careful review! If our clarifications have adequately addressed your concerns, please consider updating your score. Thanks!", "claims_and_evidence": "I read the technical sketch in the main paper but didn't look closely at the details in the appendix. I think the claims and theorems make sense to me.", "methods_and_evaluation_criteria": "The experimental setting and evaluation criteria are aligned with the state-of-the-art evaluation framework in bandit.", "theoretical_claims": "I think the theoretical claims are correct. I will look into other reviewers' opinions for further reference. However, the current method can not handle the case when $\\nu_t$ is unknown, which weakens the theoretical contributions of this work.", "experimental_designs_or_analyses": "1. It seems that the experiments only consider the case when the noise has fixed $\\nu_t$, which may be too weak. It would be better if the authors could show your algorithm can yield robust performance under varying $\\nu_t$ across time $t$.\n2. It seems that several existing methods such as CRTM, CRMM and HeavyOFUL can yield competitive or even better empirical performance with less computational cost. This raises doubts about the advantage of the proposed approach.", "relation_to_broader_scientific_literature": "This paper integrates adaptive robust estimation (Huber regression), computationally efficient online learning (OMD), and variance-aware regret analysis into a single unified framework. As the authors point out in Section 5, the proposed methodology of this work has potential in other problems such as linear MDP problem and online adaptive control problem.", "essential_references_not_discussed": "I think most of the notable references have been sufficiently discussed in this work. One minor suggestion:\n\nSince I am not familiar with Huber regression and its applications, I need to read some literature to read this work. I suggest the authors could add a little bit more details on the deduction of Huber loss and its current applications on bandits and reinforcement learning problems. For example, it would be better if the authors could explain some details of [Sun et al. 2020]. I notice the work [Kang & Kim 2023] also used the same loss Huber regression for heavy-tailed bandit, so the authors should highlight the similarity and differences between Kang & Kim 2023 and yours, which is missing now. I also find [1] and [2] about Huber regression in bandits/RL, and the authors should also discuss these two works in the revision: [1] studies the matrix linear contextual bandit with Huber regression for heavy-tailed rewards, which is an extension to SLB and obtains similar regret bound. [2] considers Huber regression in distributed reinforcement learning, which also considers a similar framework in RL parameter adaptation.\n\n\n[1] Kang et al. Low-rank Matrix Bandits with Heavy-tailed Rewards\n\n[2] Malekzadeh et al. A Robust Quantile Huber Loss With Interpretable Parameter Adjustment In Distributional Reinforcement Learning", "other_strengths_and_weaknesses": "Some typos: 1. line 39 right part: \"cannot not\". 2. line 231 left part: \"both of\" should be changed to \"both\". 3. line 443: \"none of\" instead of \"none\". 4. The estimator in line 193 left part: there are $\\hat\\theta_{t+1}$ in both two equations, which is a little bit confusing. Although I can finally get it, but it is better to change $\\hat\\theta_{t+1}$ to something else in the first equations. 5. There are some non-English words in the submitted codes in the supplementary files, which are not very professional and may lead to the violation of ICML regulations.", "other_comments_or_suggestions": "I think this paper has its own merit. I will reconsider my rating on this work during the rebuttal phase, and potentially raise or decrease my rating based on the discussion with the authors and other reviewers.", "questions_for_authors": "1. Can the approach generalize to the generalized linear bandit setting, or is it strictly limited to the linear case?\n2. How sensitive is the proposed method to hyperparameter tuning (e.g., Huber threshold selection)? I do not see an ablation study on parameters or the hyperparameter setting in the manuscript.\n3. I feel the regret curves for most algorithms in your experiments are linear instead of sublinear, which looks contradicts with the theoretical results. Can you explain that?\n4. In [Kang & Kim et al.] and [Kang et al. Low-rank Matrix Bandits with Heavy-tailed Rewards] (mentioned above), the Huber loss function does not contain the variance normalization factor $\\sigma_s$. Is that because they assume the variance is fixed? Therefore, if the upper bound $\\nu$ is known, then your Huber loss can be free of the normalization factor as well?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel algorithm, Hvt-UCB, for linear bandit problems with heavy-tailed noise. The algorithm achieves state-of-the-art regret upper bounds while significantly reducing the per-round computation time from O(tlog⁡T) to O(1), and eliminating the need to store historical data. This efficiency is achieved by leveraging the Online Mirror Descent (OMD) framework for online updates of the regression parameters.

The reviewers are generally in agreement about the theoretical challenges involved in reducing computation time for bandit algorithms under heavy-tailed rewards, and they acknowledge the contribution of the work to addressing this gap in the literature.
Decision: Accept (poster)