Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards
Authors: Bo Xue
Yimu Wang
Yuanyu Wan
Jinfeng Yi
Lijun Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: linear bandits
heavy-tailed
truncated
mean of medians
TL;DR: Our truncation-based algorithm supports online learning and mean-of-medians-based algorithm requires only one estimator per epoch, distinguishing it from existing truncation-based approaches.

Abstract: This paper investigates the problem of generalized linear bandits with heavy-tailed rewards, whose $(1+\epsilon)$-th moment is bounded for some $\epsilon\in (0,1]$. Although there exist methods for generalized linear bandits, most of them focus on bounded or sub-Gaussian rewards and are not well-suited for many real-world scenarios, such as financial markets and web-advertising. To address this issue, we propose two novel algorithms based on truncation and mean of medians. These algorithms achieve an almost optimal regret bound of $\widetilde{O}(dT^{\frac{1}{1+\epsilon}})$, where $d$ is the dimension of contextual information and $T$ is the time horizon. Our truncation-based algorithm supports online learning, distinguishing it from existing truncation-based approaches. Additionally, our mean-of-medians-based algorithm requires only $O(\log T)$ rewards and one estimator per epoch, making it more practical. Moreover, our algorithms improve the regret bounds by a logarithmic factor compared to existing algorithms when $\epsilon=1$. Numerical experimental results confirm the merits of our algorithms.

Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards
Bo 11 Yimu Wang', Yuanyu Wan', Jinfeng Yi¹, Lijun Zhang Depaarmeen of Computer Science, City University of Hong Kong, Hong Kong, China "hhe City University of Hong Kong Shenzhen Research Institute, Shenzhen, China Cheritoon School of Computer Science, University of Waterloo, Waterloo, Canada *School of Software Technology. Zhejiang University, Ningbo, China
IJD AI Research, Beijing, China
"National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China PPegg Cheng Laboratory, Shenzhen, China
boxue4-cemy. cityu. edu hk, yimu. wang@uwaterloo ca, wanyyēzju. edu. yi yijinfeng@jd.co com, zhanglj j @1 amda. nju. edu. en
amdaanjju.
Abstract
This paper investigates the problem of generalized linear bandits with heavy-tailed rewards, whose (1 + e)-th moment is bounded for some (0, 1]. Although there exist methods for generalized linear bandits, most them focus on bounded or sub- Gaussian rewards and not well-suited for many real-world scenarios, such financial markets and web-addertisinng. To address this issue, we propose two novel algorithms based truncation and mean of medians. These algorithms achieve almost optimal regret bound of Ö(dT where d the dimension contextual information and 7 is the time horizon. Our truncation- -ased algorithm supports online learning, distinguishing from existing cuncction-basee approaches. Ad- ditionally, our mean-of-ne of-medians-based algorithm requires only Ologg Z') rewards and one estimator per epoch, making more practical. Moreover, our algorithms improve the regret bounds by logarithmic factor compared to existing algorithms when 1. Numerical experimental results confirm the merits our algorithms.
1 Introduction
The multi-armed bandits (MAB) is a powerful framework to model the sequential decision-making process with limited information [Robbins] 1952]. which has been found applications in various areas such as medical trails [Villar et al. 2015 and advertisement placement [Bubeck and Cesa- Bianchi 2012). In the classical K Karmed bandit problem, an agent selects one of the K arms and receives reward drawn independently and identically distributed from an unknown distribution associated with the chosen arm. The goal of the agent maximize the cumulative rewards through the trade-off between exploration and exploitation, i.e., pulling the arms that may potentially give better outcomes while also exploiting the knowledge gained from previous trials select the optimal arm.
One fundamental limitation of MAB is that it ignores contextual information in some scenarios such advertisement placement [Lattimore and Szepesvári 2020], where features of users and products can provide valuable guidance for decision making. In these cases, decisions should not only rely on rewards from previous epochs but also the contextual information from both past and current epochs. Stochastic Linear Bandits (SLB) has emerged as the most popular model in the last decade to address this limitation, assuming linear relationship between the contextual vector and the expected reward
Lijunn Zhang is the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table I: Summary of the existing work for the linear bandits with heavy-tailed rewards. CC is the abbreviation of computational complexity.
Regret
CC_ Truncacation
CC_MoM
Arms
Model
Medina and Yang
2016
O(dT²)
O(dT)
O log O log T) O(d2T)
infinite
SLB
Shao et al.
2018
O(dyT)
O + deT2) (
infinite
SLB
Xue ef al.
2020
((VaT)
finite
SLB
This work
((dyT)
O(dT)
O(dPT/logT)
infinite
GLB
Auer, 2002 Dani er al. 2008; Abbasi-yadkon et al. 2011 Hu et al. 2021 Alieva et al. 2021 Yang et al. [022]] | He et al. | [0022] Bengs et al. [022]. However, in many real-world applications, such social network [Filippi et al. [010]. the assumption of Poisson logistic relation between the expected reward and contextual vector has demonstrated better performance, which motivates the study of generalized linear bandits (GLB), In each round, the agent first observes decision set D, C Rdd composed of contextual vectors. Then, the agent selects an arm æt E 'D and receives a reward y/ satisfying the expectation,
Elye [z,] (0.
where 0. is the inherent vector and u(+)) is the link function, such as the identity function or the logistic function. The performance of the agent is measured by the regret such that
R(T) = Σ (M(T, 0.) u(z,
where a; = argmaa,=ED, (=xx' 0.) represents the optimal arm in the set D,
Extensive research has been conducted on the GLB, with most assuming Gau-Gans rewards Filippi et af.) 2010; Li et al.) 2012 2017; Jun et al.) 2017 Lu et al. 2019 Zhou et al. 2019 Han et al. 2021 Li and Wang 2022 However, it has been observed that in certain sequential decision-making scenarios, such as financial markets [Cont and Bouchaud] 2000]] the occurrence of extreme returns is much more frequent than the standard normal distribution. This phenomenon is known as heavy-tailed behavior [Foss et al. 2013). where the existing algorithms are not suitable. To address this limitation, in this study, focus the GLB with heavy-tailed rewards [Bubeck et al.) 2013]. i.c., the reward obtained at t-th round satifies the condition
Elya [t] S u
for some E (0, 1] and > O. Different from the traditional sub-Gaussian setting, heavy-tailed rewards do not decay exponentially and the estimation of expected rewards is significantly impacted.
According to the distinguishing characteristic of heavy-tailed distributions where extreme values occur with high probability, previous studies have developed three main strategies address the issue in parameter estimation [Audibert and Catoni| [2011] Hsu and Sabato 2014 Zhang and Zhou 2018 Ray Chowdhury and Gopalan 2019 Lugosi and Mendelson [202]] Zhong et al. [021] Huang et al.
2022: Diakonikolas et al.] 2022 Gorbunov et al. [022]] Kamath et al. [022 Li and Liu [202]] Gou
et al. 2023). One such strategy is truncation Audibert and Catoni [2011), which mitigates the impact
of extreme values by truncating them. A recently proposed strategy is the mean of medians approach (Zhong el al. 2021], which involves partitioning the samples drawn from the heavy-tailed distribution into multiple groups, taking the median within each group, and computing the mean of these medians. intuitively reduces the impact of extreme samples, as extreme samples are distributed to both sides, thus the median value is more robust. The third strategy is median of means [Hsu and Sabato 2014). which adjusts the order calculating mean and taking the median in the mean of medians strategy.
Most existing algorithms for heavy-tailed bandit problems are derived from aforementioned three strategies, with primary focus on the SLB model [Medina and Yang) [0166] Shao et al.) 20188) 8 Xue et al. 2020). To provide a comprehensive overview and facilitate comparison, we present summary of our results and previous findings on linear bandits with heavy-tailed rewards Table For the sake of clarity, the presented regret bounds in Table I are under the assumption that the rewards have finite variance. The computational complexity only takes into account multiplication and division operations. Although Shao et al. (2018) and Xue al. (2020) achieve nearly optimal regret for

---

infinite-an armed and finite-armed SLB, respectively, their algorithms are computationally expensive. The latest work utilizing the mean of medians approach demonstrates efficiency but limited to symmetric rewards [Zhong et al. 2021]. Therefore, designing efficient heavy-tailed algorithms for GLB with symmetric and asymmetric rewards is an interesting and non-trivial challenge.
Through the delicate employment of heavy-tailed strategies, our contributions to the generalized linear bandit problem with heavy-tailed rewards can be summeraized follows:
We develop two novel algorithms, CRTM and CRMM, which utilize the truncation strategy and mean of medians strategy, respectively. Both algorithms exhibit a sublinear regret bound of ÖdT ), which is amolst optimal as the lower bound is (ddT+=7 [Shao et al. 2018 8j.
CRTM reduces the computational complexity from ( to ((T) when compared to existing cuncation-based algorithms [Shao al. 2018 Xue al. 2020]. while CRMM
reduces the number of estimator required per round from Olog T to only one, as compared
to existing median-of-meann based algorithms [Shao et al. 2018 Xue al. 2020).
When = 1,, the regret bounds of CRTM and CRMM improves a logarithmic factor of order and
for some (0, 1), respectively, over the recently proposed method of Zhong el al. 2002] Notably, CRTM extends the method of Zhong el al. [001 from symmetric rewards to general case, making CRTM more practical.
We conduct numerical experiments demonstrate that our proposed algorithms not only achieve a lower regret bound but also require fewer computational resources when applied to heavy-tailed bandit problems.
2
Related Work
In this section, we briefly review the related work on linear bandits. Through out the paper, the p-norm of vector æ E Rd is ||œ||p- = ()z1 +... + ( 1/P. Given a positive definite matrix A E IRd the weighted Euclidean norm of the vector is ||~||| Vxe T Ax.
2.1 Generalized Linear Bandits
Filippi et al. 2010) was the first address the generalized linear bandit problem and proposed an algorithm with regret bound of (dvT)). However, their algorithm is not efficient as it requires storing all the action-feedback pairs encountered so far and performing maximum likelihood estima- tion at each step. A notable improvement was presented by Zhang et al. (2016) with the introduction of an efficient algorithm called OL whose space and time complexity each epoch does not grow over time and achieves a ((dVT) regret. However, their algorithm is limited to the logistic link function. Later, Jun et al. 2017)] extended P to generic link functions while still maintaining the (dvTT regret bound. Ding et al. [2021] proposed another efficient generalized linear bandit. algorithm following the line of Thompson sampling scheme.
The main challenge in the bandit problem is the trade-off between exploration and exploitation. method, specifically for the linear bandit model with infinite arms [Dani el al. 2008 Abbasi-yadkori el al. 2011 Zhang al. 2016 Here we take the algorithm OL to give brife introduction this approach (Zhang et al. 2016). With the arrival of a new trial (Ix, y/ in the t-th epoch, OL'M first constructs a surrogate loss (0) satisfying (0) = (-yt Ut + u(x,, 0) 22 Then, OL employs a variant of the online Newton step (ONS) update the estimated parameters, i.e.,
To address this issue, the most commonly used approach is the confidence-region-biie
| 12 (0 ON (O.)
N. 1+1
argmin OER
2
Here, V4+1 + 2 for k >> 0, and the initialized matrix V1 AL for À > 0. Subsequently, OL'M constructs confidence region C++1 centered the estimated parameter @ 1+11 such that
C. 0 e Ed
0N S sa+1}
(1 -1) moment of rewards exists, then the (1 e2)-th moment of rewards is bounded [ue al. 2020 Thus, CRTM and CRMM achieve this regret improvement when 2 1.
F e > 62 > 0, if the
3

---

where M++1 = t) indicating the uncertainty of the estimation and the unknown parameter 0. lies this region with high probability. Finally, OL'M selects the most promising arm 1 according to the principle of "optimization in the face of uncertainty", i.e.,
104+10041 DEC241
argmax
(x: 0).
2.2 Bandit Learning with Heavy-tailed Rewards
Most of the existing work developed heavy-tailed bandit algorithms using truncation and median of means strategies [Bubeck et al., [2013] Medina and Yang) 2016; (Shao et al. 2018 Xue et al.) [020)]
Huang et al. 2022 [Bbbeck et al. [2033] first conducted extensive research on multi-armed bandits
with heavy- tailed rewards and achieved a logarithmic regret bound. Medina and Yang (016) extended
2
to the SLB model and introduced two algorithms that achieve regret bounds of (dT dd'22447)
and
), respectively. Shao et al. [018)) improved upon the results of Medina and Yang 2016 by a more delicate application of heavy-tailed strategies, achieving a regret bound of
Ö(d T 113c
Li.. + dT ITT:)
O(d Xue et al. [2020] investigated the case with finite arms and provided two algorithms that attained regret bounds of T Recently, Zhong el al. [2021] proposed the mean of medians estimator for the super heavy-tailed bandit problem, but the rewards are limited to symmetric distributions. Applying this estimator to the GLB algorithm of et al. (2017) yields heavy-tailed
GLB algorithm that achieves the regret bound of (ddlog T) 2. - for some E (0, To illustrate the basic idea of adopting different heavy-tailed strategies in the bandit model, we briefly describe three representative algorithms.
For the algorithm exploiting truncation strategy, we take the algorithm TOFU as an instance (Sao el al. 2018 With the trials up to round f, TOFU truncates the rewards d times as follows,
yr (0wllshee 3e (u(00ushhh i =
(5)
) is the truncated criterion, and wt (t) denotes the element in the i-th row and T-th column of matrix V V A, A, [2, 22, 27]] E RRxxt is the matrix composed of selected arms and V+1 A + Ls- Using these truncated rewards, TOFU conducts an estimator as 0 V. [u! Vut/" ......, ug Y with ui YY, - (t)y)-I Ish,- TOFU then constructs a confidence region centered on this estimator and selects the promising arm, similar to (3) and (4). Notice that the scalarized parameters {t){
where h, Ot म[नन(]
updated at each epoch, requiring TOFU to store the learning history and truncate all rewards at each epoch. Thus, TOFU is not an online method.
For the algorithm exploiting median of means strategy, it's common to play the chosen arm times and get sequences of rewards {Y,' 1/=1, where Y?' = [Vi.... ... y/l is the j-th reward sequence up to epoch f. MENU executes least square estimation for each reward sequence and get r estimators, i.e.
0 1+1 = Argmin||A]] Y 1/ + 1012. j = ..
(6)
BER4
where r (log T) operated as follows,
Shao al 2018
Then, the median of means strategy adopted by MENU is
m median of {110'.. 0 llv.. : : 1, []
Then, MENU takes the estimator 0::; with A: argmin
{my} the center of confidence
region. Finally, MENU selects the most promising arm similar to
For the mean of medians method proposed by Zhong et al. [2021) at each epoch f, the agent first plays the selected arm times, with value o = O(log T) for some E (0, 1), and then receives rewards {ur = for these plays. Subsequently, the agent randomly divides the rewards into multiple groups, with each group contains [ rewards. The agent then takes the median of each group and uses the mean of these medians to update the estimator. Notice that the expectation of the median has bias to the expected reward other than the symmetric distribution. Thus, mean of medians strategy is limited to symmetric distribution. Another point worth mentioning is that F is too

---

large to try sufficient different arms. For example, the agent can only play [T/r] 100 different arms with T 10th and 0.62, which is obviously unreasonable
3
Algorithms
In this section, we first introduce the generalized linear bandit model and then demonstrate two novel algorithms based on truncation and mean of medians, respectively.
3.1 Learning Model
The formal description of the generalized linear bandit model is as follows. In each round t, an agent plays an arm æ; E D, and obtains stochastic reward Yt, which is generated from generalized linear model represented by the following equation,
Pr(ye(x.)) exp y! 0. m(ar O.) h(ye,))
(8)
g(T)
where 0, is the inherent parameters, 7 > 0 is a known scale parameter, and g(t) and h(;,)) are normalizers [P. McCullaghh 1989]. The expectation of ys is given by
Elys xxe] = m' mx; 0.).
Thus, m'(-) is the link function in T.. such that (x-) = m m'(.). The reward model can be rewritten as 1/2 م u( 0.) W
where T/ random noise satisfying the condition
E[n [G-1]
Here, G:-1 2 {x Ui....... 3t Filippi et al. 2010 Jun al. 2017 Li al. 2017]. we make standard assumptions as follows.
is o o-filtration and Go 0. Following the existing work
Assumption The coefficients 0, and contextual vectors bounded, such that 10. 1l2 S and | & 1 for all x E DD where a known constant.
Assumption The link function p(-) is L-Lipschitz on 1-S,S) S), and continuously differentiable on S). Moreover, there exists some O such that pz) Z and lu(z)] S U for any 2 (-S
3.2 Truncation
Our first algorithm is called Confidence Region with Truncated Mean (CRTM). The complete procedure is provided in Algorithm [ Here, we consider the heavy-tailed setting, i.e., there exists
constant u > 0, the rewards admit
[Ival 1+c 1t-1-1-1] I u.
(10)
As we have mentioned earlier in Section 2.1 to design effective algorithms for GLBB model, construct- ing narrow confidence region for the underlying coefficients 0, necessary. However, heavy-tailed rewards that satisfy (10) produce extreme values with high probability, resulting in confidence region with large radius. Therefore, straightforward approach to settle this problem is to truncate the extreme reward to reduce its impact.
In each round t, CRTM first plays an arm 2, Dr and observes the corresponding reward Then, CRTM truncates the reward ze using a uniform criterion Ō(T such that
J = y ye-|llas (allaslll,,, 1lelsr
a 0.62 nearly optimal for according the experiments of Zhong et al
2021

---

Algorithm Confidence Region with Truncated Mean (CRTM)
Input: ó, e, u, K,K, A max 1, x/2] and ' N+
1: Initialize 0 and V1 AId
2: Define the truncation criterion r = 2 (u/ In(4T/6)) (d'nn (1 +
RT 2Xd /x)² T
3: for = ., T do
4: (at, 0.) ar (z. 0)
5: Play the arm I; and observe the payoff Y
6: Truncate the observed payoff Yt | lly, 10llTT
7: Compute the gradient (0,) (- + u( 0c))
8: Update V++1 V, -
9: Update the estimator
0 0. VV.n + (0 - 0r. (2)
0.11 argmin |00|:5S
2
10: Construct the confidence region
C++1 0 E [
0. $7}
11: end for
where V, = V.-1 52,-10;__ with V1 Ala- Here, 6 is defined in Assumption and
À max m1 </2.. With the processed action-reward pair (æt, Dc); CRTM computes the gradient of the loss function as
Vi( (- u( 0))...
(11)
where (-)- is the negative log- log-likelihood of the generalized linear model (8). After that, CRTM employs a variant of online Newton step (ONS) to update its estimator, given by
000 0 +(0 -0- (o)))
0++1- argmin
| lSS
Equipped with above estimation, CRTM construets the confidence region C++1 where the inherent parameters 0, lies in with high probability, such that
C++1 { T 1.till $7)
where y = Õ(T denotes the width the confidence region, and details are shown in Theorem Given the confidence region C the most promising arm 1z+1 can be obtained through the following maximize operation,
(x1+1, 0(+1)
argmax (xx 0) mED #EC..1
since p(-) is monotonically increasing according to Assumption 2
Although there exists several heavy-tailed linear bandit algorithms based on the truncation strategy, such as TOFU (Shao et al.) 2018] and BTC [Xue et al.) 20200. CRTM differs from them in two aspects. Firstly, both TOFU and BTC have store the historical rewards and truncate them each epoch, resulting in a computational complexity of OT?2). In contrast, CRTM achieves online learning by processing only the reward of current round, whose computational complexity is O(T). Secondly, while TOFU and BTC are designed for SL.B model and calculate the estimator via least-squares estimation, CRTM is designed for the GLB model and updates the estimator using the ONS method, which makes the analytical techniques fundamentally different. Theorem [rovides a tight confidence region, and its proof relies on the induced method because ONS is ierativvly updated method. Due to the page limit, we provide the detailed proof in the Appendix A.2.
Theorem the rewards satisfy and 10 then with probability as least the confidence region in CRTM is
0
0
θ Vin 27

---

Algorithm 2 Confidence Region with Mean of Medians (CRMM)
Input: 0, U, K,K,K, K, max x/2 and T N
1: Initialize 0 0, 1 dI and "1 A.2
2: r= 16 47
8 and To = [T/r]
3: for f 1,2 To do
4: (c,,0.) = argmax D,0CC, (xr 0)
5:
Play the arm æ; times and observe the rewards {ye 22 . .
6:
Take the median of {vl ........ Vi Dt
7: Compute the gradient (0, (- Dr ul 0z))
8:
Update V++1 = V + - Compute the center of confidence region
9:
0 - 0z Iien + +(0- 0c. vē((O.)
0.11 = argmin
|00|
2
10:
Construct the confidence region
{ 00 R= 10 1- -00+1ll S m11
C++1
11: end for
where
4d In
KT
48U2d
KT
= 244u (n(47/6) + 7 T
1
22S2
In
2Ad
K
2Ad
With above confidence region, the regret bound of CRTM is explicitly given follows.
Theorem If the rewards satisfy 9 and 110)
then with probability at least 1 - 6, the regret of
CRTM satisfies
142r R(T) SO [d(logT)
144 T T
Remark:
The above theorem establishes Odd regret bound with the assumption that the (1+c)) c)-th moment the rewards is bounded for some e E (0, 1]. Existing algorithms based on truncation is time-consuming because they need to store the learning history and truncate all historical rewards at each epoch (Shao el al. 2018) Xue et al.) 2020). Unlike the recently proposed mean of medians method which is limited in symmetric rewards [Zhong al. [021]. CRTM expands it
asymmetric and achieves improved regret bound by factor of O(log T" s
for some (0. 1)
if 1. Furthermore, CRTM almost optimal as the lower bound is 2(T ++.
Shao el al. 2018
3.3
Mean of Medians
In this section, present second algorithm, referred Confidence Region with Mean of Medians (CRMM), which shares a similar framework with CRTM but uses a different mean of medians estimator. The complete procedure is outlined in Algorithm 2 CRMM requires that for some e E (0, 1]. the 1 central moment of the rewards is bounded, and the distribution of rewards is symmetric. Precisely, for some (0, 1), there exists constant such that the rewards satisfy
E [nd (+
and p(n)) p(-n)).
(12)
At each epoch t,, CRMM plays the selected arm Ø; r times, generating rewards (log T). To obtain robust estimation using mean of medians strategy, CRMM first takes the median of [y:..... ......,, yi denoted by ft. Subsequently, CRMM computes the gradient with the arm-reward pair (æ,, Wt) through the operation similar to (II) Then, CRMM employs variant of ONS to update the estimator and construct the confidence region C++1 centered on the new estimator. The details about the constructed confidence region is given in Theorem
.......7 ...) .y......g!
with
7

---

Compared to existing bandit algorithms that utilize the median of means strategy. the primary difference lies the item chosen as the "means". As we have introduced 7 MENU of Shao et al. (2018) uses the distance between different estimators as the "means". BMM of Xue el al. [222 calculates multiple estimated rewards for each arm and treats them as the "means". Both MENU and BMM require (log 7) estimators during each round, whereas CRMM only requires one estimator. Moreover, compared to the mean of medians approach [Zhong et al. 2021]. CRMM plays each selected arm fewer times, leading results. Since the chosen arm has to be played multiple times, we assume the arm set for CRMM static, such that Dj- D for > O, which is common assumption [Medina and Yang 2016 Zhang
more model updates, which is critical based on experimental
et al. 2016 Lu et al. 2019]. The following theorem guarantees a tight confidence region.
Theorem If the rewards satisfy 9 and region in CRMM is
12
then with probability as least 26, the confidence
10
0++1
S 7e41,
where
7+11 = (4U2 + Cpt I-e 4d
nt
+ 2p² l-
In
1 +
+ +S2
2Ad
p 2=2CIn(4T// + =C, C (4v) (Av)
With above confidence region, we prove the following regret bound for CRMM.
Theorem If the rewards satisfy 9 and 12). then with probability least 28, the regret of CRMM satisfies
R(T)= S ( (d(log ( T
O
Remark:
3 clarifies that if the rewards have a finite 1 ++ central moment for some e E 10. CRMM achieves a regret bound of (dT This bound reduces to (dvTT) when = 1, indicating that CRMM achieves the same order the bounded rewards assumption regarding both d and T (Zhang et al. 2016 Jun ef al. (017)). Compared to the approach of /fong et al. 2021
Theorem
CRMM enhances the bound by an order of O(log T") 2o -à) for fixed a E (0, 1
4 Experiments
This section demonstrates the improvement of our algorithms by numerical experiments. Firstly, we show the effectiveness of our algorithms in dealing with heavy-tailed problems by comparing their regret to that of existing generalized linear bandit algorithms. Secondly, we evaluate the efficiency of our algorithms by comparing their time consumption to other existing algorithms designed for heavy-tailed bandit problems. All algorithms are implemented using PyCharm 2022 and tested on a laptop with 2.5GHz CPU and 32GB of memory.
4.1 Regret Comparison
To assess the enhancement of our algorithms in handling heavy-tailed problems, we utilize the vanilla GLB algorithms, specifically OL [Zhang al. 2016) and GLOOC [Jun el al. 2017 (. as baselines. Additionally, we incorporate the mean of medians method proposed by Zhong et al. (2021) into OL'M and GLOC, resulting in another two baselines OL'M mom and GLOC_mon m_mm respectively. All algorithms are configured with e = 1, 8 = 0.01, and T = 106.
Let 0, = 1/vd E Rd, where 1 is an all-1 vector and ||0.12 = 1. The number of arms is set to K = 20, and the feature dimension is d 10. Each component of the contextual vector æ; is uniformly sampled from the interval [0, 1]. and then normalized to be unit norm, i.e., ||æ/||a = 1. We tune the width of the confidence region following the common practice in bandit. learning /Zhan et af.) 2016 Jun et al. 2017). Precisely, with e being a tuning parameter searched within [e 11. the width of the confidence region for OL?M and GLOC are set as ? ed edln(t/) X + 1) and 7/ = ( 0.) y 1 respectively. addition, the radius of the confidence region is set od (n(T//))) 2. (n( + 1+ for CRTM, and ed In(t/(d)) 1)t 174 for
8

---

3,0
2.00-
OL'M
OL'M
Cumulative Regret
GLOC
Cumulative Regret
2.50
mam
mom
GLOc_mom
GLoc.mom CRMM(our))
1.25
CRMM[ours)
CRTM(oum)
1.3
CRTM[
0.75
0.50
0.25
03
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
10
Itoration
Iteration
(a) Student's l-noises (symmetric)
(b) Pareto noises (asymmetric)
Figure 1: Regret comparison
CRMM. For OL ML __m per round, and 0.62 is close optimal according to the experiments of Zhong et al. [2021]
mom and GLOC_ mom, the chosen arm played F == (161n(2T/8) times
We run 10 repetitions for each algorithm and display the average regret with time evolution. According to the generalized linear bandit model, the observed reward y/ is given by
Y/+ = μ 0.) + 7
where (ax) Ite-a is the logit model and is the heavy-tailed noises. To evaluate the algorithms performance under both symmetric and asymmetric rewards, Ht fits the following two distributions,
ii Student's 's t-Noise: Tee G3.5(1.5
G(2)
(1 - where G(-) is the Gamma function;
(ii) Pareto Noise: T/
su g++1
2 where s = 3 and Fm 0.01.
Fig. compares our algorithms against two vanilla GLB algorithms (OL and GLOC), as well as these two algorithms exploiting mean of medians estimators (OL'M_mon M_momm and GLOC_mom). Fig. [[) shows that CRTM and CRMM outperform the other four algorithms. CRTM provides the best performance, which is consistent with the theoretical guarantees. OL mom and GLOC mom appear ineffective at handling heavy-tailes problems, because they update estimator only 100 times with the chosen played F times (Zhong al. 2021]. Fig. (b) presents the cumulative regrets under asymmetric noises, with CRTM still having the lowest regret curve, demonstrating its generality and effectiveness in handling heavy-tailed bandit problems. On the other hand, CRMM, GLOC mom, and OL M_moo performs poorly in Fig. bb), as they can not deal with the asymmetric rewards.
4.2 Runtime Comparison
To demonstrate the efficiency improvement of our algorithms, we compare them with existing heavy- tailed bandit algorithms such CRT and MoM [Medina and Yang. 2016), TOFU and MENU (Shao) al. 22088) and SupBTC and SupBMM [Xue al. 2020]. Among them, CRT, TOFU and SupBTC employ truncation strategy, while MoM, MENU and SupBMM utilize the median of means strategy.
The experimental settings are the same as de- scribed Regret Comparison section, except for the time horizon and feature dimension. We use a smaller time horizon T = 10* since TOFU is time-consuming. The feature dimen- sion is increased difference between SupBTC and TOFU. The computational runtimes are shown Table 2
Table 2: Runtime comparsion
Algorithm
Time(s)
Algorithm
Time(s)
CRT
3.1737
MoM
0.0630
100 highlight the
TOFU SupBTC
3931.9963
MENU
24.1990
1187.1863
SupBMM
0.0685
CRTM
2.2909
CRMM
0.0514
For the truncation- based algorithms, CRTM consumes the least time, while TOFU and SupBTC takes over hundred times longer execute than CRTM, representing significant improvement. CRT takes only slightly longer than CRTM as both algorithms update the model online, but the regret bound of CRT is (dT2), which is Ö(T1) worse

---

than the bound of CRTM. For median of means algorithms,, CRMM has the shortest runtime. MENU takes significantly longer than the other algorithms because MENU needs calculate the distance between (logg T' estimators.
5 Conclusion and Future Work
We present two algorithmss CRTM and CRMM, for the generalized linear bandit model with heavy- tailed rewards, which utilize the truncation and mean of medians strategies, respectively, Both algorithms achieve the regret bound of (dd conditioned on a bounded (1 + e)-th moment of rewards, where E (0, 1]. This bound is almost optimal since the lower bound of the stochastic liear bandit problem ((dT [Shao et al. 2018). CRTM is the first truncation- based online algorithm for the heavy-tailed bandit problem that handles both symmetric and asymmetric rewards and approaches the optimal regret bound. CRMM enhances the regret bound of the the most related work by logarithmic factor [Zhong al. 2022]. However, CRMM is limited to symmetric rewards and we will investigate to overcome this restriction in the future.
Acknowledgments and Disclosure of Funding
This work was partially supported by the National Key R&D Program of China (0222D0114801)) the Key Basic Research Foundation of Shenzhen (JCYJ202208) 8100005011), NSFC (62122037, 61921006) and the major key project of PCL (PCI.2021A12).
References
Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, pages 2312-2320, 2011.
Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. Robust pure exploration in linear bandits with limited budget. In Proceedings of the 38th International Conference Machine Learning, pages 187-195, 2021.
Yves Audibert and Olivier Catoni. Robust linear least squares regression. The Annals of Statistics, 39(5):2766 2011.
Peter Auer. Using confidence bounds for exploitation-exploraiion trade-offss Journal of Machine Learning Research, 3(1 ((1)):377442, 2002.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Math. J. (2), 19(3):357-377, 1967.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In Proceedings of the 39th International Conference on Machine Learning, pages 776417866 2022.
Sébastien Bubeck and Nicolò Cesa-Biancha Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
Séhastien Bubeck, Nicolò Cesa Gesa-Bianchh,, and Gáhor Lugosi. Bandits with heavy tail. IEEE Transac- tions on Information Theory, 59(11):7711-7711 2013.
Rama Cont and Jean- Chinlpp Bouchaud. Herd behavior and aggregate fluctuations in financial markets. Macroeconomic Dynamics, 1()):770-196 2000.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. Proceedings of the 21st Anmual Conference on Learning, pages 355-366, 2008
Ilias Diakonikolas, Daniel Kane, Jasper Lee, and Ankit Pensia. Outlier-robust sparse mean estimation for heavy-tailed distributions. In Advances Neural Information Processing Systems 35, pages 5164-5177, 2022.
10

---

Qin Ding, Cho-Jui Hsich, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In Proceedings of The 24th International Conference Artificial Intelligence and Statistics, pages 1585-1593, 2021.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems 23, pages 386-594. 2010.
Sergey Foss, Dmitry Korshunov, and Stan Zachary. An Introduction to Heavy-Tailed and Subexpo- nential Distributions. Springer, 2013.
Eduard Gorbunov, Marina Danilova, David Dobre, Pavel Dvurechenskii, Alexander Gasnikov, and Gauthier Gidel. Clipped stochastic methods for variational inequalities with heavy-tailed noise. In Advances in Neural Information Processing Systems 35, pages 31319-31332, 2022.
Yutian Gou, Jinfeng Yi, and Lijun Zhang. Stochastic graphical bandits with heavy-tailes rewards. In Proceedings of the 39th Conference on Uncertuinty in Artificial Intelligence, pages 734-744, 2023,
Yuxuan Han, Zhipeng Liang, Yang Wang, and Jiheng Zhang. Generalized linear bandits with local differential privacy. In Advances in Neural Information Processing Systems 34, pages 26511- 1-51222 2021.
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. In Advances in Neural Information Processing Systems 35, pages 34614-34625, 2022.
Daniel Hsu and Sivan Sabato. Heavy-tailed regression with a generalized median-of-means. In Proceedings of the 31st International Conference Machine Learning, pages 37-45, 2014.
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In Proceedings of the 38th International Conference on Machine Learning, pages 4349-4358, 2021.
Jiatai Huang, Yan Dai, and Longbo Huang, Adaptive best-of-both-worte algorithm for heavy-tailed multi-armed bandits. In Proceedings of the 39th International Conference on Machine Learning. pages 9173-9200 2022.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems 30, pages 99-109, 2017.
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In Proceedings of the 39th International Conference on Machine Learning, pages 10633-10660, 2022.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Shaojie Li and Yong Liu. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. In Proceedings of the 39th International Conference on Machine Learning, pages 12931-12963, 2022.
Chuanhao Li and Hongning Wang. Communication efficient federated learning for generalized linear bandits. In Advances in Neural Information Processing Systems 35, pages 38411-38422 2022.
Lihong Li, Wei Chu, John Langford, Taesup Moon, and Xuanhui Wang. An unbiased offline evaluation of contextual bandit algorithms with generalized linear models. In Proceedings of the Workshop On-line Trading of Exploration and Exploitation 2, 2012.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference on Machine Learning, pages 2071 2080, 2017.
Shiyin La Guanghui Wang, Yao Hu, and Lijun Zhang. Multi-objective generalized linear bandits. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3080-3086. 2019.
11

---

Gábor Lugosi and Shahar Mendelson. Robust multivariate mean estimation: The optimality of trimmed mean. The Annals of Statistics, 49(1):393 410, 2021.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In Pro- ceedings of the 33rd International Conference on International Conference on Machine Learning, pages 1642-1650, 2016.
William Mendenhall, Robert.J. Beaver, and Barara.M. Beaver. Introduction to Probability and Statistics. Cengage Learning, 2012.
John A. Nelder P. McCullagh. Generalized linear models. 1989.
Sayak Ray Chowdhury and Aditya Gopalan. Bayesian optimization under heavy- payoffs. In Advances in Neural Information Processing Systems 32, pages 13790-13801, 2019.
Herbert Robbins. Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc., 58(5):527-535, 1952.
Yevgeny Seldin, François Laviolette, Nicolò Cesa Desa-Bianchi, John Shawe- and Peter Auer. Pac-bayesian inequalities for martingales. IEEE Transactions on Information Theory, 58(12):7086 7093, 2012.
Han Shao, Xiaotian Yu, Irwin King, and Michael R. Lyu. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. In Advances in Neural Information Processing Systems 31, pages 8430-8439, 2018.
Sofía S. Villar, Jack Bowden, and James Wason. Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges. Statistical Science, (o(en)e,,3(()199))))) 30(2):199-215, 2015.
Bo Xue, Guanghui Wang, Yimu Wang, and Lijun Zhang. Nearly optimal regret for stochastic linear bandits with heavy-tailed payoffs. In Proceedings of the 29th International Joint Conference Artificial Intelligence, pages 2936-2942, 2020.
Shuo Yang, Tongzheng Ren, Sanjay Shakkottai, Eric Price, Inderjit S. Dhillon, and Sujay Sanghavi. Linear bandit algorithms with sublinear time complexity. In Proceedings the 39th International Conference on Machine Learning, pages 25241-252600 2022.
Lijum Zhang and Zui Zhou. 4 reregssssoon with haived distributions. In Advances in Neural Information Processing Systems 31, pages 1084-1094, 2018
Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-Hua Zhou. Online stochastic linear optimization under one-bit feedback. In Proceedings of the 33rd International Conference Machine Learning, pages 392-401, 2016.
Han Zhong, Jiayi Huang, Lin Yang, and Liwei Wang. Breaking the moments condition barrier: No-regret algorithm for bandits with super heavy-tailed payoffs. In Advances in Neural Information Processing Systems 34, pages 15710-15720, 2021.
Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning in generalized linear contextual bandits with stochastic delays. In Advances in Neural Information Processing Systems 32, pages 5197- 5208, 2019.
12


Reviews:
[{"review_id": "TeapgLcw4d", "reviewer": "Reviewer_WjRx", "summary": "This paper proposes two novel algorithms which improve computational complexity and regret bounds over previous algorithms for generalized linear bandits with heavy-tailed rewards by combining the truncation strategy (or means of medians strategy) with the online Newton step.", "questions": "1. Can dependency on $\\kappa$ in the regret bound be relaxed?", "limitations": "Yes. This work is mostly theoretical and potential negative societal impact is unseen.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This work improves the computational complexity and regrets bound of the generalized linear contextual bandits with heavy-tailed rewards which are closely related to the real-world application.", "weaknesses": "1. Among the input values for the algorithm, $S$, $\\epsilon$ and $v$ is not known in practice.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you sincerely for your time and effort in reviewing our work. We have carefully considered your concerns and our responses are provided as follows.\n\n----\n**Weeknesses: Among the input values for the algorithm, $S, \\epsilon$ and $v$ is not known in practice.**\n\nHuang et al. [2022] proposed an algorithm for heavy-tailed MAB models that eliminates the dependence on $\\epsilon$ and $v$ by utilizing the FTRL framework and the doubling trick technique. This provides some insights to remove the dependence on $\\epsilon$ and $v$ in the GLB model. However, GLB algorithm is based on the online Newton step method, which is fundamentally different from FTRL, and we will strive to address this issue in future research. For the parameter $S$, most existing online GLB algorithms requires prior knowledge $S$ [Zhang et al., 2016; Jun et al., 2017; Lu et al., 2019]. We will try to remove this limitation in the future.\n\n-----\n**Questions: Can dependency on $\\kappa$ in the regret bound be relaxed?**\n\n[1] introduced an algorithm for the Logistic model that enhanced the dependency on $\\kappa$ from $O(\\kappa^{-1})$ to $O(\\kappa^{-1/2})$. However, their algorithm is offline, as it relies on the maximum likelihood estimate. Consequently, directly applying [1]'s technique to our algorithms would not yield a similar improvement, since our algorithms are online. In future research, we aim to improve the dependency on $\\kappa$ by employing a variant of [1]'s technique. The revised version of our paper will provide a more comprehensive discussion of this issue.\n\n\nReferences\n\n[1] Improved Optimistic Algorithms for Logistic Bandits. Louis Faury, Marc Abeille, Clément Calauzènes, Olivier Fercoq, 2020."}, {"review_id": "WmFcwzmG5o", "reviewer": "Reviewer_QvG4", "summary": "This paper studies the problem of generalized linear bandits with heavy-tail rewards. Due to the heavy-tailedness, methods and algorithms for linear bandits with sub-gaussian rewards cannot be directly applied. To handle such issues, existing works have developed certain strategies, two of which are the truncation strategy and the mean-of-medians strategy. To this end, this paper proposes two novel algorithms, CRTM and CRMM, which utilize the aforementioned strategies and achieve sublinear regret bounds. CRTM reduces the computational complexity of previously best known truncation-based methods, while CRMM reduces the number of estimators required. Furthermore, CRTM does not require the reward to have symmetric distribution, contrasting existing works. Experimental results demonstrate the low regret and computational complexity of the proposed methods.\n", "questions": "In the theoretical proof, what are the major differences from previous works? For example, is there any non-trivial ideas applied? \nMore details in  the Weakness section.\n", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "\n**1. Clarity**\nThe paper has a clear presentation. The GLB bandit problem and heavy-tailedness are rigorously defined. \n\n**2. Meaningful results for an important problem**\nHeavy-tailedness is an important aspect due to its board application in many real-world scenarios. This paper proposed computationally efficient near-optimal algorithms for such a setting, which is a meaningful result. \n\n**3. Experiments**\nThe experimental study covers the regret bound as well as the computational complexity.\n", "weaknesses": "There is no major technical weakness/flaws in this paper, as far as I can tell.\n\nHowever, I do challenge the technical contribution of this paper: in terms of the theoretical analysis, does this paper improves over existing results or does this paper develop novel analytical techniques to facilitate the analysis? For example, in line 209, this paper mentions that the theoretical analysis is fundamentally different from that of TOFU/BTC. However, it seems to me that this is not elaborated in the later part of the paper, so I have to assume that the technical contribution is incremental compared to existing works.  Therefore, I am concerned about the technical contribution of this paper. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you sincerely for your time and effort in reviewing our work.  We have carefully considered your concerns, and are very happy to respond more questions during the rolling discussion.\n\n----\n\n**Questions: In the theoretical proof, what are the major differences from previous works TOFU/BTC? For example, is there any non-trivial ideas applied?**\n\nWe first highlight the key differences in the analysis between TOFU and CRTM. For TOFU, which employs the least square estimation (LSE), the confidence region for the inherent parameter $\\theta_*$ is given by\n\\begin{equation}\n\\lVert\\hat{\\theta}\\_{t+1}^{LSE}-\\theta\\_\\*\\rVert_{\\widetilde{V}\\_{t+1}} \\leq  \\lVert \\underbrace{\\widetilde{V}\\_{t+1}^{-\\frac{1}{2}} A\\_t\\(Y\\_t-A\\_t^\\top\\theta\\_\\*\\)}\\_{A}  \\rVert\\_2+\\lVert\\theta\\_\\*\\rVert\\_{\\widetilde{V}\\_{t+1}^{-1}}\n\\end{equation}\nwhere $A\\_t=[x\\_1,x\\_2,\\ldots,x\\_t]\\in\\mathbb{R}^{d\\times t}$ is the matrix composed of selected arm vectors, $\\widetilde{V}\\_{t+1}=A\\_tA\\_t^\\top+I_d$ and $Y\\_t=[y\\_1,y\\_2,\\ldots,y\\_t]\\in\\mathbb{R}^{t\\times 1}$ is the historical reward vector. For CRTM, which employs the Online Newton Step (ONS) method, the confidence region for the inherent parameter $\\theta\\_*$ is\n\\begin{equation}\n\\lVert\\hat{\\theta}\\_{t+1}^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_{t+1}}^2\\leq\\underbrace{\\sum\\_{\\tau=1}^t 2x\\_\\tau^\\top\\left\\(\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\right\\) \\left\\(y\\_\\tau-\\mu\\(x\\_\\tau^\\top\\theta\\_\\*\\)\\right\\)}\\_{B}+\\sum\\_{\\tau=1}^t \\lVert x_\\tau\\rVert\\_{V\\_\\tau^{-1}}^2 \\left\\(y\\_\\tau-\\mu\\(x\\_\\tau^\\top\\theta\\_\\*\\)\\right\\)^2+O\\(\\log t\\).\n\\end{equation}\n\nAlthough both above two equations include the linear combination of historical rewards ($A$ and $B$), there exists essential differences between these two terms. Specifically, $A$'s coefficients $\\widetilde{V}_{t+1}^{-\\frac{1}{2}}A_t$ are known and the agent can truncate the scaled rewards to reduce the impact of extreme noises. However, $B$'s coefficient $\\\\{x\\_\\tau^\\top\\(\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_*\\)\\\\}\\_{\\tau=1}\\^t$ are unknown, which makes the existing technique of TOFU invalid. \n\nTo address this issue, our main contribution in analytical technique is the adoption of inductive method. We first relax term $B$ as follows:\n\\begin{equation}\n\\|x\\_\\tau^\\top\\(\\hat{\\theta}^{ONS}\\_\\tau-\\theta\\_\\*\\)y\\_\\tau\\|\\leq\\lVert\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_\\tau}\\cdot\\lVert x\\_\\tau\\rVert\\_{V\\_\\tau^{-1}}\\cdot|y\\_\\tau|.\n\\end{equation}\n\nFor $\\tau=1$, it is evident that $\\lVert\\hat{\\theta}\\_1^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_1}^2\\leq \\gamma$. Then, we assume $\\lVert\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_\\tau}^2\\leq \\gamma$ for $\\tau=1,2,\\ldots, t$, which replaces the unknown parameters $\\lVert\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_\\tau}$ with $\\gamma^{1/2}$. Since $\\lVert x\\_\\tau\\rVert\\_{V\\_\\tau^{-1}}$ is known, CRTM can truncate the term $\\lVert x\\_\\tau\\rVert\\_{V\\_\\tau^{-1}}\\|y\\_\\tau|\\$ to reduce the impact of extreme values. A delicate analysis of this approach for applying the truncated strategy demonstrates that $\\lVert\\hat{\\theta}\\_{t+1}^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_{t+1}}^2\\leq\\gamma$, which concludes the proof of the confidence region. Further details can be found in Lemma 5 of the supplementary material."}, {"review_id": "H7oewHZo4c", "reviewer": "Reviewer_7N78", "summary": "This paper considers Generalized Linear Bandit (GLB) with heavy-tailed rewards, i.e., the rewards $y_t=\\mu(\\langle x_t,\\theta^\\ast\\rangle)+\\eta_t$ only allows a bounded $(1+\\epsilon)$-order moment. By utilizing the truncation and the mean of medians technique (both for handling heavy-tailed r.v.s), the authors establish efficient algorithms for GLBs with infinite arms and heavy-tailed rewards.", "questions": "See Weaknesses. I am willing to increase my score if the authors can address it convincingly.", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Compared to previous works on LB with heavy-tailed rewards, this paper considers Generalized LB instead of standard Stochastic LB, where the function $\\mu$ can be any Lipschitz and uniformly bounded function.\n2. This paper has a lower computational complexity: previous truncation-based works achieving $\\sqrt T$-style regret require performing an iteration over all previous observations every time they update the confidence set, which costs $\\mathcal O(T)$ time. In contrast, by utilizing the ONS step used in the $\\text{OL}^2\\text{M}$ algorithm, this algorithm only needs $\\mathcal O(d^2)$ time for each round.\n3. The presentation is pretty clear, and the algorithms are easy to understand.\n4. The results are supported by various numerical illustrations.", "weaknesses": "I am not sure what is the main technical contribution of this paper. For example, the CRTM algorithm looks pretty like equipping the $\\text{OL}^2\\text{M}$ algorithm by Zhang et al. (2016) with the previous truncation techniques by Shao et al. (2018) or Xue et al. (2020). Without any part in the main text devoted to explaining the technical hardness of showing Theorems 1 & 2, it is hard to evaluate the contribution of this paper. The same also holds for the mean-of-medians method CRMM.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks sincerely for your time and effort in reviewing our work.  We have carefully considered your concerns, and are very happy to respond more questions during the rolling discussion.\n\n----\n\n**Q1:The CRTM algorithm looks pretty like equipping the OL$^2$M algorithm by Zhang et al. (2016) with the previous truncation techniques by Shao et al. (2018) or Xue et al. (2020).  The same also holds for the mean-of-medians method CRMM.**\n\nTo deal with the heavy-tailed GLB problem, it is essential to incorporate the GLB algorithm's fundamental technique (Online Newton Step method) and heavy-tailed strategies (truncation and mean of medians). However, our algorithms not only attain the nearly optimal regret bounds but also offer significant improvements in efficiency compared with existing algorithms (Shao et al., 2018; Xue et al., 2020). Specifically, CRTM reduces the computational complexity from $O(T^2)$ to $O(T)$, and CRMM reduces the number of estimators required per round from $O(\\log T)$ to only $1$. To achieve such improvements, we have developed novel approaches for applying heavy-tailed strategies and conducted new analytical techniques. We give a detailed introduction as follows.\n\n----\n**Q2: Technical contribution of the truncation-based method CRTM.**\n\nCompared with existing truncation-based algorithm TOFU (Shao et al., 2018) and BTC (Xue et al., 2020), CRTM differs from them in two aspects. First, both TOFU and BTC have to store the historical rewards and truncate all these rewards at each epoch, resulting in a computational complexity of $O(T^2)$. In contrast, CRTM achieves online learning by truncating only the reward of current round, whose computational complexity is $O(T)$. Second, TOFU and BTC are designed for SLB model and calculate the estimator via Least Square Estimation (LSE) , CRTM is designed for the GLB model and updates the estimator using the Online Newton Step (ONS) method, which makes the analytical techniques different. \n\nThe main innovation in CRTM's analysis is the adoption of inductive method. We first display the key differences in the analysis between TOFU and CRTM. For TOFU employing LSE, the confidence region for the inherent parameter $\\theta_\\*$ is\n\\begin{equation}\n\\lVert\\hat{\\theta}\\_{t+1}^{LSE}-\\theta\\_\\*\\rVert_{\\widetilde{V}\\_{t+1}} \\leq  \\lVert \\underbrace{\\widetilde{V}\\_{t+1}^{-\\frac{1}{2}} A\\_t\\(Y\\_t-A\\_t^\\top\\theta\\_\\*\\)}\\_{A}  \\rVert\\_2+\\lVert\\theta\\_\\*\\rVert\\_{\\widetilde{V}\\_{t+1}^{-1}}\n\\end{equation}\nwhere $A\\_t=[x\\_1,x\\_2,\\ldots,x\\_t]\\in\\mathbb{R}^{d\\times t}$ is the matrix composed of selected arm vectors, $\\widetilde{V}\\_{t+1}=A\\_tA\\_t^\\top+I_d$ and $Y\\_t=[y\\_1,y\\_2,\\ldots,y\\_t]\\in\\mathbb{R}^{t\\times 1}$ is the historical reward vector. For CRTM employing the ONS method, the confidence region for the inherent parameter $\\theta\\_\\*$ is\n\\begin{equation}\n\\lVert\\hat{\\theta}\\_{t+1}^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_{t+1}}^2\\leq\\underbrace{\\sum\\_{\\tau=1}^t 2x\\_\\tau^\\top\\left\\(\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\right\\) \\left\\(y\\_\\tau-\\mu\\(x\\_\\tau^\\top\\theta\\_\\*\\)\\right\\)}\\_{B}+\\sum\\_{\\tau=1}^t \\lVert x_\\tau\\rVert\\_{V\\_\\tau^{-1}}^2 \\left\\(y\\_\\tau-\\mu\\(x\\_\\tau^\\top\\theta\\_\\*\\)\\right\\)^2+O\\(\\log t\\).\n\\end{equation}\nAlthough both above two equations include the linear combination of historical rewards ($A$ and $B$), there exists essential difference between these two terms. Specifically, $A$'s coefficients $\\widetilde{V}_{t+1}^{-\\frac{1}{2}}A_t$ are known and the agent can truncate the scaled rewards to reduce the impact of extreme noises. However, $B$'s coefficients $\\\\{x\\_\\tau^\\top\\(\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_*\\)\\\\}\\_{\\tau=1}^t$ are unknown, which makes the existing technique of TOFU invalid. \n\nTo address this issue, we adopt the inductive method. The first step is to relax term $B$ as follows:\n\\begin{equation}\n\\|x\\_\\tau^\\top\\(\\hat{\\theta}^{ONS}\\_\\tau-\\theta\\_\\*\\)y\\_\\tau\\|\\leq\\lVert\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_\\tau}\\cdot\\lVert x\\_\\tau\\rVert\\_{V\\_\\tau^{-1}}\\cdot|y\\_\\tau|.\n\\end{equation}\nFor $\\tau=1$, it is evident that $\\lVert\\hat{\\theta}\\_1^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_1}^2\\leq \\gamma$. Then, we assume $\\lVert\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_\\tau}^2\\leq \\gamma$ for $\\tau=1,2,\\ldots, t$, which replaces the unknown parameters $\\lVert\\hat{\\theta}\\_\\tau^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_\\tau}$ with $\\gamma^{1/2}$. Since $\\lVert x\\_\\tau\\rVert\\_{V\\_\\tau^{-1}}$ is known, CRTM can truncate the term $\\lVert x\\_\\tau\\rVert\\_{V\\_\\tau^{-1}}\\|y\\_\\tau|\\$ to reduce the impact of extreme values. A delicate analysis of this approach for applying the truncated strategy demonstrates that $\\lVert\\hat{\\theta}\\_{t+1}^{ONS}-\\theta\\_\\*\\rVert\\_{V\\_{t+1}}^2\\leq\\gamma$, which concludes the proof of the confidence region. Further details can be found in Lemma 5 of the supplementary material.\n\n----\n\n**Q3: Technical contribution of the mean-of-medians method CRMM.**\n\nCompared with existing median of means algorithms MENU (Shao et al., 2018) and BMM (Xue et al., 2020), CRMM differs from them in two aspects. The first one is the estimator as we introduced in Q2. The second one is the order of \"mean\" and  \"medians'' operations. MENU and BMM first calculate $O(\\log T)$ \"means'' using multiple historical reward sequences, and then takes the median of these \"means''. CRMM reverses the order of these two operations to reduce the number of \"means'' to $1$, as the calculation of \"means'' is time-consuming. Specifically, CRMM first takes the median of multiple rewards and then calculates a single \"mean'' using the median reward. \n\nThe analysis has been adapted to prove that such an exchange can achieve a near-optimal regret bound. Two important properties of the median are utilized in our proof. The first property is that scaling a set of variables does not alter the index of the median term, which is employed in the proof of Lemma 10 (Lines 144-153). The second property is the upper bound of the median's $(1+\\epsilon)$-th moment, as established in Lemma 8."}, {"review_id": "8MzeJ49FIg", "reviewer": "Reviewer_jQHU", "summary": "In this paper, the authors study the problem of generalized linear bandits with heavy tailed rewards. They propose two algorithms based on truncation and mean of medians. The algorithms both achieve near optimal regret bound of $\\tilde{O}(dT^{\\frac{1}{1+\\epsilon}})$. These regret bounds improve upon previous results in the sense of regret bound or computational complexity. Finally, the authors run simulations to support their claims.", "questions": "1. For CRMM, since the assumption of symmetric distribution is used to guarantee that the median is 0, I am curious about whether it is possible to replace the condition with the median of the distribution equals 0.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem of generalized linear bandits with heavy-tailed rewards is well-motivated.\n2. Both algorithms achieve near optimal regret bounds, the proof looks correct to me.\n3. The writing is clear, the related work part is really helpful. ", "weaknesses": "1. According to the introduction of previous methods for generalized linear bandits and bandits with heavy-tailed rewards, the algorithms are direct combinations of previous techniques. Therefore the algorithmic novelty is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you sincerely for your time and effort in reviewing our work. We have carefully considered your concerns and our responses are provided as follows.\n\n----\n\n**Weaknesses: According to the introduction of previous methods for generalized linear bandits and bandits with heavy-tailed rewards, the algorithms are direct combinations of previous techniques. Therefore the algorithmic novelty is limited.**\n\nIn fact, all existing heavy-tailed bandit algorithms are combinations of bandit algorithms' fundamental framework and heavy-tailed strategies (truncation and mean of medians) (Bubeck et al., 2013; Medina and Yang, 2016; Shao et al., 2018; Xue et al., 2020). The challenge is to find an appropriate approach to apply the heavy-tailed strategies for the problems at hand, and provide rigorous analysis for the proposed algorithms. \n\nOur proposed algorithms differ from existing algorithms (Shao et al., 2018; Xue et al., 2020) in two main aspects. First, our work integrates heavy-tailed strategies into the Online Newton Step (ONS) method, whereas existing research has applied heavy-tailed strategies to Least Square Estimation (LSE), resulting in fundamentally different analytical techniques. Second, our algorithms not only achieve nearly optimal regret bounds but also offer significant improvements in efficiency compared to existing heavy-tailed algorithms (Shao et al., 2018; Xue et al., 2020). Specifically, CRTM reduces the computational complexity from $O(T^2)$ to $O(T)$ when compared to existing truncation-based algorithms (Shao et al., 2018; Xue et al., 2020). CRMM reduces the number of estimators required per round from $O(\\log T)$ to only $1$ when compared to existing median-of-means-based algorithms (Shao et al., 2018; Xue et al., 2020). To attain such improvements, we have developed novel approaches for applying heavy-tailed strategies and introduced new analytical techniques. We provide a detailed introduction as follows.\n\n**Truncation-based algorithm:** CRTM differs from existing algorithms TOFU (Shao et al., 2018) and BTC (Xue et al., 2020) in the truncated terms. Both TOFU and BTC have to store the historical rewards and truncate all these rewards at each epoch, resulting in a computational complexity of $O(T^2)$. In contrast, CRTM achieves online learning by truncating only the reward of current round, whose computational complexity is $O(T)$. The main innovation in CRTM's analysis is the adoption of inductive method. Please refer to the **response for reviewer QvG4** for more details. \n\n**Mean-of-medians-based algorithm:** CRMM differs from MENU (Shao et al., 2018) and BMM (Xue et al., 2020) in the order of the \"mean\" and \"medians\" operations. MENU and BMM first calculate $O(\\log T)$ \"means\" using multiple historical reward sequences, and then takes the median of these \"means\". CRMM reverses the order of these two operations to reduce the number of \"means\", as the calculation of \"means\" is time-consuming. Specifically, CRMM first takes the median of multiple rewards and then calculates a single \"mean\" using the median rewards, which reduces the number of estimators required per round from $O(\\log T)$ to only $1$. The analysis has been adapted to prove such an exchange can achieve the nearly optimal regret bound. Two important properties of the median are utilized in our proof. The first property is that scaling a set of variables does not alter the index of the median term, which is employed in the proof of Lemma 10 (Lines 144-153). The second property is the upper bound of the median's $(1+\\epsilon)$-th moment, as established in Lemma 8.\n\n----\n\n**Questions: For CRMM, since the assumption of symmetric distribution is used to guarantee that the median is 0, I am curious about whether it is possible to replace the condition with the median of the distribution equals 0.**\n\n\nYes, replacing the condition with the median of the distribution being equal to $0$ is sufficient to conduct the nearly optimal regret bound. The symmetric distribution is utilized in the proof of Lemma 10, and the details can be found in Lines 156-158 of the supplementary material, where we mention that the symmetric distribution is employed to ensure that the median is 0. We will provide a more comprehensive discussion of this assumption in the revised paper."}]

Author rebuttal:

Meta-review: All reviewers have reached a consensus and recommend to accept the paper. The main strengths are:
* clarity of the algorithm and presentation 
* relevant problem addressed. 

The discussion focused on the potential weakness of the technical contribution that the authors eventually addressed in their rebuttal. We recommend that the final version reflects these exchanges and highlight the novel technical contributions precisely.
Decision: Accept (poster)