uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs
Authors: Yu Chen
Jiatai Huang
Yan Dai
Longbo Huang
Venue: ICLR 2025 Spotlight (2025)
Keywords: Heavy Tailed
Multi-Armed Bandits
Parameter-Free
Best-of-Both-Worlds
Primary area: learning theory

Abstract: In this paper, we present a novel algorithm, `uniINF`, for the Heavy-Tailed Multi-Armed Bandits (HTMAB) problem, demonstrating robustness and adaptability in both stochastic and adversarial environments. Unlike the stochastic MAB setting where loss distributions are stationary with time, our study extends to the adversarial setup, where losses are generated from heavy-tailed distributions that depend on both arms and time. Our novel algorithm `uniINF` enjoys the so-called Best-of-Both-Worlds (BoBW) property, performing optimally in both stochastic and adversarial environments *without* knowing the exact environment type. Moreover, our algorithm also possesses a Parameter-Free feature, *i.e.*, it operates *without* the need of knowing the heavy-tail parameters $(\sigma, \alpha)$ a-priori.
To be precise, `uniINF` ensures nearly-optimal regret in both stochastic and adversarial environments, matching the corresponding lower bounds when $(\sigma, \alpha)$ is known (up to logarithmic factors). To our knowledge, `uniINF` is the first parameter-free algorithm to achieve the BoBW property for the heavy-tailed MAB problem. Technically, we develop innovative techniques to achieve BoBW guarantees for Parameter-Free HTMABs, including a refined analysis for the dynamics of log-barrier, an auto-balancing learning rate scheduling scheme, an adaptive skipping-clipping loss tuning technique, and a stopping-time analysis for logarithmic regret.

Published as a conference paper at ICLR 2025
UNIINF: BEST-OF-BOTH-WORIIE ALGORITHM FOR PARAMETER-FREI HEAVY-TAILED MABS
Yu Chen
Jiatai Huang
III, Tsinghua University
Beijing ZhuoShi Capital Co., Ltd., China huang ata @ @zsquant com
chenyu23emai 1s. wtt....tsiigaaat..ee. edu.cn
Yan Dai
Longbo Huang
ORC, Massachusetts Institute of Technology yandai20emit.edi
III,, Tsinghua University
1 Longbohuangetsingguu. edw.aaaaeddd.ooom
ABSTRACT
In this paper, we present a novel algorithm, uni INF, for the Heavy- Saive-Tailed Multi- Armed Bandits (HTMAB) problem, demonstrating robustness and adaptability both stochastic and adversarial environments. Unlike the stochastic MAB setting where loss distributions are stationary with time, our study extends to the adversarial setup, where losses are generated from heavy-tailed distributions that depend on both arms and time. Our novel algorithm uni INF enjoys the so-called Best- of-Both-Wee Woth-Worlds (BoBW) property, performing optimally in both stochastic and adversarial environments without knowing the exact environment type. Moreover, algorithm also possesses Parameter-Free feature, i.e., it operates without the need of knowing the heavy-tail parameters (a, a)) a-priori. To be precise, un TNF ensures nearly-optimal regret in both stochastic and adversarial environments, matching the corresponding lower bounds when (a, a)) is known (up to logarithmic factors). To our knowledge, uni INF is the first parameter-free algorithm achieve the BoBW property for the heavy-tailed MAB problem. Technically, we develop innovative techniques to achieve BoBW guarantees for Parameter-Free HTMABs, including a refined analysis for the dynamics of log-barrier, an auto- balancing learning rate scheduling scheme, an adaptive skipping-clipping loss tuning technique, and stopping- time analysis for logarithmic regret.
INTRODUCTION
Multi-Armed Bandits (MAB) problem serves as a solid theoretical formulation for addressing the exploration-exploiee
trade-off inherent in online learning. Existing research in this area often assumes sub-Gaussian loss (or reward) distributions (Lattimore & Szepesvári, 2020) or even bounded ones (Auer et al., 2002). However, recent empirical evidences revealed that Heavy-Tailed (HT) distributions appear frequently in realistic tasks such as network routing (Liebeherr et al., 2012), algorithm portfolio selection (Gagliolo & Schmidhuber, 2011), and online deep learning (Zhang et al., 2020). Such observations underscore the importance of developing MAB solutions that are robust heavy- distributions.
In this paper, we consider the Heavy- -ailed Multi-Armed Bandits (HTMAB) proposed by Bubeck et al. (2013). In this scenario, the loss distributions associated with each arm do not allow bounded variances but instead have their a-th moment bounded by some constant σ², where a E (1,2) 2) and assume E[[[[|]] σe for every
2 are predetermined constants. Mathematically, Although numerous existing HTMAB algorithms operated under the assumption that the parameters and are known (Bubeck et al., 2013; Yu al., 2018: Wei & Srivastava, 2020), real-world applications often present limited knowledge of the true environmental parameters. Thus we propose to explore the scenario where the algorithm lacks any prior information about the parameters. This setup, variant of classical HTMABs, is referred to as the Farameter-Free HTMAB problem.
i.
"The first three authors contributed equally to this paper. I Part of the work was done when Yan Dai was at IIIS, Tsinghua University.
1 *Corrsponndig author.

---

Published as a conference paper at ICLR 2025
In addition to whether and are known, there is yet another separation that distinguishes our setup from the classical one. In bandit learning literature, there are typically two types of environments, stochastic ones and adversarial ones. In the former type, the loss distributions are always stationary, Le., they depend solely on the arm and not on time. Conversely, in adversarial environments, the losses can change arbitrarily, as-if manipulated by an adversary aiming to fail our algorithm.
When the environments can be potentially adversarial, a desirable property for bandit algorithms is called Best-of-Botke Worhds (BoBW), as proposed by Bubeck & Slivkins (2012). A BoBW algorithm behaves well in both stochastic and adversarial environments without knowing whether stochasticity is satisfied. More specifically, while ensuring near-optimal regret in adversarial environments, the algorithmic performance in a stochastic environment should automatically be boosted, ideally matching the optimal performance of those algorithms specially crafted for stochastic environments.
In practical applications of machine learning and Dacision-making acquiring prior knowledge about the environment is often a considerable challenge (Talaei Khoei & Kaabouch, 2023). This is not only regarding the distribution properties of rewards or losses, which may not conform to idealized assumptions such as sub-Gaussian or bounded behaviors, but also about the stochastic or adversarial settings the agent palying in. Such environments necessitate robust solutions that can adapt without prior distributional knowledge. Therefore, the development of a BoBW algorithm that operates effectively without this prior information termed parameter-free HTMAB algorithm is not just theoretical interest but a practical necessity.
Various previous work has made strides in enhancing the robustness and applicability of HTMAB algorithms. For instance, Huang et al. (2022) pioneered the development of the first BoBW algorithm for the HTMAB problem, albeit requiring prior knowledge of the heavy-tail parameters (a, o) to achieve near-optimal regret guarantees. Genalti et al. (2024) proposed an Upper Confidence Bound (UCB) based parameter-free HTMAB algorithm, specifically designed for stochastic environments. Both algorithms'' regret adheres to the instance-depender and instance-inde independent lower bounds established by Bubeck et al. (2013). Though excited progress has been made, the following important question still stays open, which further eliminates the need of prior know about the environment:
Can we design a BoBW algorithm for the Parameter-Free HTMAB problem?
Addressing parameter-free HTMABs in both adversarial and stochastic environments presents notable difficulties: i) although UCB-type algorithms well estimate the underlying loss distribution and provide both optimal instance-dependent and independent regret guarantees, they are incapable of adversarial environments where loss distributions are time- deeendependntt; ii) heavy-tailed losses can be potentially very negative, which makes many famous algorithmic frameworks, including Follow- the- the-Regularized-I Leader (FTRL), Online Mirror Descent (OMD), or (FTPL.) fall short unless meticulously designed; and iii) while it was shown that FTRL with 3-Tsallis entropy regularizer can enjoy best-of- soaff-btt-wwolde guarantees, attaining optimal regret requires an exact match between |3 and 3/4- - which is impossible without knowing a in advance.
Leader
Our contribution. In this paper, we answer this open question affirmatively by designing a single algorithm uni INF that enjoys both Parameter-Free and BoBW properties- - that is, it i) does not require any prior knowledge of the environment, e.g., O,, and ii) its performance when deployed in an adversarial environment nearly matches the universal cestance-indepedeeee by Bubeck et al. (2013), and it attains the instance-deeendent lower bound in stochastic environments as well. For more details, we summarize the advantages of our algorithm in Table 1. Our research directly contributes to enhancing the robustness and applicability of bandit algorithms in variety of unpredictable and non-ideal conditions. Our main contributions are three-fold:
lower bound given
We develop novel BoBW algorithm uni INF (see Algorithm 1) for the Parameter-Frree HTMAB problem. Without any prior knowledge about the heavy-tail shape-and-scale parameters (a, o). uni INF can achieve nearly optimal regret upper bound automatically under both adversarial and stochastic environments (see Table or Theorem 3 for more details).
We contribute several innovative algorithmic components in designing the algorithm un i INF, including a refined analysis for weroowtthh-Reulaiizeeee Leader (FTRL) with log- barrier regularizers (refined log- bar-berrirr analysis in short; see Section 4.1,, an auto- balancinnn learning rate scheduling scheme (see Section 4.2), and an adaptive skipping-clipping loss tuning technique (see Section 4.3).
To derive the desired BoBW W property, we develop novel analytical techniques as well. These include a refined approach to control the Bregman divergence term via calculating partial derivatives and
2

---

Published as a conference paper at ICLR 2025
Table 1: Overview of Related Works For Heavy-Tailed MABS
Algorithm* #
ax-Free?
o-Free??
Env.
Regret
Opt?
Lower Bound (Bubeck et al,, 2013)
Eier (2) 3- log
11 (ak' Vag
RobustUCB (Bubeck al,, 2013)
Expr (3.) - log
x
x
Only Stoc.
(ook* 1/.7111)
Robust MOSS
Li T log( I a
Only Stoc.
(Wei & Srivastava, 2020)
(ok''VV-T"
/
XPp (Lee ul., 2020b)
(6 + Ein 5. (TA, - log K) 10-18608
X
X
Only Stoc.
Texplo K1
HTINP (Huang et al., 2022)
Stoc.
Σ Eizir( (2,)= T
x
Adv.
(ao 3/7%
OPTETINF (Houng ul., 2022)
Stoc.
Eizir A. a log
X
/
Adv.
x
AdaTINE (Huung ul., 2022)
Only Adv.
o EEer log?"
A-BR (Genalti et al., 2024)
Only Stoc.
uni INFE (Ours)
Stoc.
O [K join log log
(oK1-NoTTH NoTT))
"a-Free? and -Feee? denotes whether the algorithm is parameter-free w.r. and respectively. Env. includes the environments that the algorithm work; if one algorithm work in both stochastic and adversarial environments, then we mark this column by green. Regret describes algorithmic guarantees, usually (if' applicable) restance-depende algorithm matches the destancedeeeedeet lower bound by Bubeck et al. (2013) up to constant factont or the instance-indee indeaeeeindeeendentt lower hound up logarithmic factors.
ones above aataace-independen ones. Opt? means whether the
"Up to log(a") 'Up to log(o") and log(1/ Amin) factors when all A,'s As's are similar to the dominant sub-optimal gap Amin-
(og(1/A)) / factors.
invoking the intermediate value theorem (see Section 5.2) and stopping- -ime analysis for achieving Oloog regret in stochastic environments (see Section 5.4).
RELATED WORK
Due to space limitations, we defer the detailed comparison with the related works into Appendix A and only discuss few most related ones here.
Heavy-Tailes Aulti-Armed Bandits. HTMABs were introduced by Bubeck et al. (2013), who gave both mnstance-dependee and independent lower and upper bounds under stochastic assumptions. Various efforts have been devoted in this area since then. To exemplify, Wei & Srivastava (2020) improve the instance-indedd -nnauneeendeeeeeeentt upper bound; Yu al. (2018) developed pure exploration algorithm for HTMABs; Medina & Yang (2016); Kang & Kim (2023); Xue et al. (2024) considered linear HTMAB problem; and Dorn et al. (2024) investigated the symmetric reward distribution.
Best-of-Bothh -ott-ofBooth--e Both-Wodds Algorithms. Bubeck & Slivkins (2012) pioneered the study of BoBW bandit algorithms, and was followed by various improvements including EXP 3-based approaches (Seldin Slivkins, 2014), FTPL-based approaches (Honda al., 2023), and FTRL-basee approaches (Wei & Luo, 2018; Zimmert & Seldin, 2019). When the loss distribution can be heavy-tailed, Huang et al. (2022) achieves
property under the known-(a, assumption.
Parameter-Fres HTMABs. Another line HTMABs' research aimed at getting rid of the prior knowledge of presented the GSR method to identify the optimal arm in HTMAB without any prior knowledge. In terms of regret minimization, Lee et al. (2020b) and Lee & Lim (2022) considered the when is
which we call Parameter-Fiee Free HTMABs. Along this line, Kagrecha al. (2019)
3

---

Published as a conference paper at ICLR 2025
unknown. Genalti et al. (2024) were the first to achieve the parameter-free free property while maintaining near-optimal regret. However, all these algorithms fail in adversarial environments.
PRELIMINARIES: HEAVY-TAILED MULTI-ARMEI BANDITS
For finite set X, ((X) denotes the set of probability distributions over X, often also referred to as the simplex over X. We also use A [K] ((K]) to denote the simplex over [K]. We use O to hide all constant factors, and use Ô to additionally suppress all logarithmic factors. We usually use bold letters æ to denote vector, while I; denotes an entry of the vector. Unless mentioned explicitly, log(z) denotes the natural logarithm of æ. Throughout the text, we will use {F+} to denote the natural filtration, i.e., Fr represents the o-algebra generated by all random observations made during the first / time-slots.
Notations. For an integer n 2 [n]] denotes the set {1, ..... n).
Multi-Armed Bandits (MAB) an interactive game between player and an environment that lasts for finite number of T > 0 rounds. In each round E [2], the player can choose action from K3 arms, denoted by i, E [K]. Meanwhile, a K -ddimensional loss vector &, E RK is generated by the environment from distribution v,, simultaneously without observing ig. The player then suffers a loss of l,i, and observe this loss (but not the whole loss vector &g). The player's 's objective is to minimize the expected total loss, or equivalently, minimize the following (pseudo-)regret..
Rr max E =E[K]
Σ
le,
where the expectation is taken w.E.t. the randomness when the player decides the action in and the environment generates the loss l, We use '" = argmin,E
Σ 4,. to denote the optimal arm.
In Heavy--aaled MABs (HTMAB), for every t E [T] and i E [K], the loss is independently sampled from some heavy-tailed distribution Vt.; in the sense that E < o", where a E (1. 2] and (BoBW) algorithm
2 are some pre-determined but unknown constants. A Best-of-Both-Wont is one that behaves well in both stochastic and adversarial environments (Bubeck & Slivkins, 2012), where stochastic environments are those with homogeoomgessuu {Me) (i.e., Vt, = V1, for every t E [T] and E [K] and adversarial environments are those where Vt,s 's can depend on both and i. However, we do not allow the loss distributions depend on the player's previous actions. 3
Before concluding this section, we make the following important assumption which is also considered in Huang et al. (2022) and Genalti et al. (2024). Notice that Assumption 1 is strictly weaker than the common "non-negative losses" assumption in the MABs literature (Auer et al., 2002; Lee et al., 2020a; Jin al., 2023), which only needs the truncated non-negativity for the optimal arm. We make a detailed discussion this assumption in Appendix B.
Assumption 1 (Truncated Non-Negative Loss (Huang al., 2022, Assumption 3.6)). There exits an optimal arm i" E [K] such that l,,5 : is truncated non-negative for all E [7]. where random variable X is called truncated non-negative E[ 1[|
M]] 2 0 for any M 2
Additionally, we make the following assumption for stochastic cases. Assumption 2 is common for algorithms utilizing self-bounding analyses, especially those with BoBW properties (Gaillard et al., 2014; Luo & Schapire, 2015; Wei & Luo, 2018; Zimmert & Seldin, 2019; Ito et al., 2022).*
Assumption 2 (Unique Best Arm). In stochastic setups, if we denote the mean of distribution Vi.1 as μ4s == Et [e] for all i E [K), then there exists a unique best arm i E [K] such that
A P4g pi- foror all + i.. That is, the minimum gap Amin min;4 Di is positive.
4 THE BOBW HTMAB ALGORITHM UNIIN INE
In this section, we introduce our novel algorithm uni INF (Algorithm 1) for parameter-free HTMABs achieving BoBW. To tackle the adversarial environment, we adopt the famous Follow-the-Regularize Leader (FTRL) framework instead the statistics-based approach. Moreover, we utilize the log-
CCalled oblivious adversary model (Bubeck & Slivkins, 2012; Wei & Luo, 2018; Zimmert & Seldin, 2019). 'While Assumption 2 is commonly adopted in prior work, it is worth noting that some Tsallis-INF algorithms do not require this assumption analyzed in Ito (2021a) and further extended in Jin et al. (2023).
4

---

Published as a conference paper at ICLR 2025
Algorithm I uni INF: the universal INF-type algorithm for Parameter-Frre HTMAB
Initialize the learning rate S₁ f
2: for = 1,2....,77 do
,,......'
3: Apply Follow-the- Regularized-Leadee (FTRL) to calculate the action at A K with the log-barrier regularizer v, defined in Eq. (2): > Refinned log-barrier analysis; see Section 4.1.
K
(2.00) + (.((a)) (x(x) == S log 25
3t c argmin #EA [K]
4: Sample action bn Ty. Play and observe feedback l,fe.
5: for 1,2..... K do & Adaptive skipping-clippee loss tuning; see Section 4.3, Note that only cotpp and C,th (but not the whole Edlip and eolip vectors) are accessible to the player.
6: Calculate the action-dependent skipping threshold for arm and round
St
Ci.i
(3)
4(1 10--1p =1,5)
and define skipped version and clipped version of the actual loss b,,
(0r
Ee,
if 1e, < Ct, otherwise
kkip Skip(l,,i, Ct,s) =
Ct
if 2 Ct.
Clip(le, Cra) =
-Cri
if S -Cr,
otherwise
7: Calculate the importance sampling estimate of Chip, namely &, where Es,
1
ic), Vi E [K].
8: Update the learning rate S
Auto-balancing learning rates; see Section 4.2.
$ 5 + (Coli))2 (1 xt,i.² - log T)
regularizer to derive the logarithmic regret bound in stochastic setting. In the rest of this section, we introduce the main novel components in un TNF, including the refined log-barrier analysis (see Section 4) the auto-bur tittobblancing learning rate scheduling scheme (see Section 4.2), and the adaptive skipping-clipping loss tuning technique (see Section 4.3).
4.1 REFINED LOG-BARRIER ANALYSIS
We adopt the log-barrier regularizer -S EK log learning rate in round f. While log-barrier regularizers were commonly used in the literature for data-adaptive bounds such as small-loss bounds (Foster et al., 2016), path-length bounds (Wei & Luo, 2018), and second-order bounds (Ito, 2021b), and have also been shown to enable the best-of-both- worlds property in certain settings, this paper introduces novel analysis illustrating that log barrier regularizers also provide wwvironment--ddativvig for both stochastic and adversarial settings.
Eq. (2) where 5, is the
==
Precisely, it is known that log-barrier applied to loss sequence {c:) ensures Σ (x. - y, C.) S E - K log T + DIV.) where DIV, I S5- EK 2,, for non-negative c, 's (Foster et al., 2016, Lemma 16) and DIV, S S- Σ Ct,ac,, for general e, (Dai et al., 2023, Lemma 3.1). In comparison, our Lemmas 4 and 5 focus on the case where S, is adequately large compared |c/ll and give refined version of DIv, S. ΣK 22,(11
)2 er, which means
T Σ x y, c) S E SS41 S. log T +
T
T
K
Σ S.
Σ
2
(5)
1=1
t=1
5

---

Published as a conference paper at ICLR 2025
The extra (1 r2,3)² terms are essential to exclude the optimal arm 1 E [K] nice property that leads to best-of-bott both-worlds guarantees (Zimmert & Seldin, 2019; Dann et al., 2023b). To give more technical details why need this (1 - xx,;)², in Section 5.1, will decompose the regret into skipping error (e,,, - ( [ A i*] and main regret which is roughly Σ (z: - y, (eii)) The skipping errors already include the indicator L[i, * i*], so the exclusion of 1 is automatic. However, for the main regret, must manually introduce some St.a)) to exclude 1" which means the previous bounds mentioned above do not apply, while our novel Eq. (5) is instead helpful.
4.2 AUTO-BALANCING LEARNING RATE SCHEDULING SCHEME
We design the our auto-balancing learning rate S, in Eq. (4). The idea is to balance Bregman divergence term DIV, and a V-shiffiing term SHIFT, that arise in our regret analysis (roughly corre- sponding the terms on the RHS of Eq. (5)). They allow the following upper bounds as we will include as Lemmas 5 and 9:
DIV, S O
Ui t.
(1 xT,;.)
SHIFT, S O ((S++1 St) K log T)
(6)
U-SSiiting
Bregman Divergence
Thus, to make DIV, roughly the same as SHIFF, it suffices to ensure (S1+1- - St) 2 (G, )². -(K (Klog T)-1. Our definition of S, in Eq. (4) follows since (S.+1 - -,)S R S -S.
4.3 ADAPTIVE
LOss TUNING TECHNIQUE
For heavy-tailed losses, a unique challenge is that ElC,,,,, the squared incurred loss appearing in the Bregman divergence term (as shown in Eq. (6)), does not allow straightforward upper bound as we only have 1[[ [0] S σ", A previous workaround is deploying skipping technique that replaces large loss with 0 (Huang et al., 2022). This technique forbids sudden increase in the divergence term and thus eases the balance between DIV, and SHIFT, However, this skipping not a free lunch: if we skipped too much, the increase of S: will be slow, which makes the skipping threshold Ct,; grow slowly as well therefore, we end up skipping even more and incurring tremendous skipping error! This eventually stops us from establishing instance-dependent guarantees in stochastic setups.
To address this limitation, we develop an adaptive Akippingcclipping technique, The idea is to ensure that every loss will influence the learning process - imagine that the green eelip in Eq. (4) is replaced
by økip then S. will not change the current f,,5, is large, which risks the algorithm from doing "t,is" nothing if happening repeatedly. Instead, our clipping technique induces an adequate reaction upon observing a large loss, which both prevents the learning rate S, from having a drastic change and ensures the growth of S, is not too slow. Specifically, from Eq. (4), if we skip the loss l,,se must have S @(1 + (K log T) ).S, This is crucial for our stopping-timg -tim analysis in Section 5.2.
the skipped loss Li (more specifically, its importance- weighted version k,) to decide the action a; in the FTRL update Eq. (2). Utilizing the truncated non-negativity assumption (Assumption I), we can exclude one arm when controlling the skipping error, as already seen in Eq. (5). We shall present more details Section 5.4.
While clipping is used to tune St,
MAIN RESULTS
The main guarantee of our uni INF (Algorithm 1) is presented in Theorem 3 below, which states that un i INF achieves both optimal minimax regret for adversarial cases (up to logarithmic factors) and near-optimal instacceddependee regret for stochastic cases.
Theorem 3 (Main Guarantee). Under the adversarial environments, uni INF (Algorithm 1) achieves
RT δ ((kk((K1zz0) (ok>-Vop//>)
Moreover, for the stochastic environments, INi (Algorithm 1) guarantees
Rr -0=0
0
K
-
log T log a
A Amin
Amin

---

Published as a conference paper at ICLR 2025
The formal proof of this theorem is provided in Appendix F. As shown in Table I, our uni INF automatically achieves nearly optimal instance-dependent and mustance-independerr regret guarantees in stochastic and adversarial environments, respectively. Specifically, under stochastic settings,
uni INF achieves the regret upper bound O (K AAmm))))))))))) //-1 log T log log""/Amm)) Compared to the instance-dependent lower bound ? Eigs- /a.)) log given by Bubeck et al. (2013),
our result matches the lower bound up to logarithmic factors log /Amin which is independent of when all A, s are similar the dominant sub-optimal gap Aiin- For adversarial environments, our algorithm achieves an O (TTT=//))/)) regret, which matches the instance-independent lower bound S2
given in Bubeck et al. (2013) to logarithmic terms. Therefore, the regrel guarantees of uni INF are nearly-optimal in both stochastic and adversarial enviromments.
5.1 REGRET DECOMPOSITION
In Sections 5.1 to 5.4, we sketch the proof of our BoBW result in Theorem 3. To begin with, decompose the regret Rr into few terms and handle each of them separately. Denoting y E RK as the one-hot vector the optimal action 1" [K] ie.. ys 1 = i*}, we know from Eq. (1) that
RT
E Σ ac, y, Ex)
As the log-barrier regularizer V, is prohibitively large when close to the boundary of A (K)), we instead consider the adjusted benchmark ÿ defined as Ti ==
i + i" it
and rewrite Rr as
K-1
i
T
RT
E
V y, kaip)
E
xt y.
eskipy
+
E
Σ (x
y, l, eqtip)
(7)
BENCHMARK CALIBRATION ERROR
11. MAIN REGRET
III. SKIPPING ERROR
We now go over each term one by one.
Term I. Benchmark Calibration Error. As in typical log-barrier analysis (Wei & Luo, 2018; Ito, 2021b), the Benchmark Calibration Error not the dominant term. This is because
- Elle, oK,
K K-
y y. eskip)
Elckii skkp S Σ
T
which is independent from T. Therefore, the key is analyzing the other two terms.
Term Main Regret. By FTRL regret decomposition (see Lemma 29 in the appendix; it is an extension of the classical FTRL bounds (Lattimore & Szepesvári, 2020, Theorem 28.5)), have
MAIN REGRET E
Σ
(x)
V. ehhiig
E
Σ
(
J. T.
T
T-1
Σ E Dv. (Zt, 21)1 +
Σ
( 1+1
v. (v1-(()441) (.(4411))l+
where Di, ()) (v) (x)
V (2) x) is the Bregman divergence induced by the t-th regularizer ,, and 2, denotes the posterior optimal estimation in episode t, namely
E (),))) + M((z))
Zt = argmin
(8)
sCAlR]
For simplicity, we use the abbreviation DIV, := Dv, (x,, 2,) for the Bregman divergence between x;
and 2, under regularizer Ve, and let SHIFT, := [( e+1 (g) V (T)) ( 1+ (x(+)) (x be the V-shifting term. Then, we can reduce the analysis of main regret to bounding the sum of Bregman divergence term E[DIv,) and V-shifting term E[SHIFT,)-
7

---

Published as a conference paper at ICLR 2025
Term III. Skipping Error. To control the skipping error, define SKIPERR, be,i. l, [|Ct,ca Cr as the loss incurred by the skipping operation at episode t. Then we have (x y. le
Σ (a1.5 - y:) (le,e
eskip
t,a
kE[K]
Σ
Tt, (e. ghip
+ (Ie.i - 1))- (4+. G.f
1f1
E [|SIPERRR|] [ie * (*) Ft-1] + (x1,5 - 1) (Ce,"
Notice that the factor (21.5- 1) in the second tern is negative and --e--uerurrlll.. Then we have
E l,.5 pkip Fi-1 [1|1e,,-11 2 C,,-- 4,55 2 0,
where the inequality is due to the truncated non-negative assumption (Assumption 1) of the optimal arm i Therefore, we have [x( - 1) (Le,i- (.Te Fr-1] - and thus
B[ y, R. (ntH)) F(-1) S E|JSKIPERR(] 1 1i 1
(9)
which gives an approach to control the skipping error by the sum of skipping losses SKIPERR,'S 's where we pick a sub-optimal arm i, + v*. Formally, we give the following inequality:
SKIPPING ERROR S E Σ SKIPERR: 1lc +
To summarize, the regret Rx decomposes into the sum of Bregman divergence terms E(DIv,,, V V-shifting terms E[SMIFT]]. and sub-optimal skipping losses [[[SKIPERR:] L[i, + i']], namely
Rr S
E
DIV.
+E
SHIFT,
+ E
Σ |SKIPERR 1/6 i*1 toK. (10)
BREGMAN DIVERGENCE TERMS
V-SHIFTING TERMS
SUB-OPTIMAL SKIPPING LOSSES
In Sections 5.2 5.4, we analyze these three key items and introduce our novel analytical techniques for both adversarial and stochastic cases. Specifically, we bound the Bregman divergence terms in Section 5.2 (all formal proofs Appendix C), the V-shifting terms in Section 5.3 (all formal proofs in Appendix D), and the skipping error terms in Section 5.4 (all formal proofs in Appendix E). Afterwards, to get our Theorem 3, putting Theorems 10, and 13 together gives the adversarial guarantee, while the stochastic guarantee follows from combination of Theorems 8, 11, and 14.
5.2 ANALYZING BREGMAN DIVERGENCE TERMS
From the log-barrier regularizer defined in Eq. (2), we can explicitly write out DIV, as
DIV, De, (2 21) St Σ
log
Ft.s
Nt.i 2t,i
1):
Zt,b
EE []
To simplify notations, we define We,s := Fe.l 1, which gives DIV, = S₁ Em (We, log( We, + 1)). Therefore, one natural idea is to utilize the inequality x - log(x + 1) x2 for x E 1-1 1/2). To do so, we need to ensure -1/2 S Wt.i < 1/2, i.e., is multiplicatively close to 2r. If the losses are bounded, this property is achieved in previously papers (Lee et al., 2020a: Jin & Luo, 2020). However, it is non-trivial for heavy-tailed (thus unbounded) losses. By refined analysis on the calculation of x and z by KKT conditions, we develop novel technical tools to depict 2, and provide the following important lemma in HTMABs. We refer readers the proof of Lemma 15 for more technical details.
Lemma (z, is Multiplicatively Close to x.). 21, S 24,6 S s every t E [T] and i E [K].
Lemma 4 implies W [-1/2, 1/2). Hence DIV, = St E.K, (we,, log(w,,; + 1)) S St ΣK w Conditioning on the natural filtration Ft-1, Wz,i is fully determined by feedback &, in episode 1, which allows to give precise depiction of Wy, via calculating the partial derivative ow,, // and invoking the intermediate value theorem. The detailed procedure is included as Lemma 16 in the appendix, which further results in the following lemma on the Bregman divergence term DIV,-
8

---

Published as a conference paper at ICLR 2025
Lemma 5 (Upper Bound of DIv.). For every & [T), can bound DIV,
DIV. = ( (1-
Σ T=1
DIV, = = (S K log
Compared to previous bounds on DIV,, Lemma 5 contains an (1 vt,i,) that is crucial for our instance-dependent bound and serves as main technical contribution, as we sketched in Section 4.1.
Adversarial Cases. By definition of S, in Eq. (4), we can bound ST+1 as the following lemma. Lemma (Upper Bound for SI+1). The expectation of S1+1 can be bounded by E[Sr+1 S 2- o I
(11)
Combining this upper-bound on [[] with Lemma 5, we can control the expected sum of Bregman divergence terms B DIv.] in adversarial environments, stated in the following theorem.
Theorem 7 (Adversarial Bounds for Bregman Divergence Terms). In adversarial environments, the sum of Bregman divergence terms can be bounded
Ō =6(Kk
E
DIve
Stochastic Cases, For Olog T) bounds, we opt for the first statement of Lemma 5. By definition of øskip "ti we immediately have gskip) S Ct.,, = (1 - Ft,i,) 1)). Further using Bl [*] S a², we - o" xz,5-)) )) (formalized Lemma 20 in the appendix).
have E FF,1]= (
We can now perform a stopping-tin time argument for the sum of Bregman divergence terms in stochastic cases. Briefly, we pick a fixed constant M > The expected sum of DIv, 's on those (t SS 2 M) then within O(M i-o 'T) according to Lemma 5. On the other hand, we claim that the sum of DIv,'s on those {t S; < M) can also be well controlled because E[DIV, Fi-1] = O(E[S] -t.5-) ) Ft-1)). The detailed analysis is presented in Appendix C.6, and we summarize Therefore, the sum of Bregman divergences in stochastic environments is also well-controlled.
follows.
Theorem (Stochastic Bounds for Bregman Divergence Terms). In stochastic settings, the sum of Bregman divergence terms be bounded by
DIV. = -0 (Ko I min
log T R
E
5.3 ANALYZING U-SHIITING TERMS
Since our choice of {Stherr hetry is non-decreasing, the V-shifting term Vz+1 (æ) V.(x) 2 0 trivially holds for any E A [K, We get the following lemma by algebraic manipulations. Lemma (Upper Bound of SHIFT,). For every 2 O, we can bound SHIFT, as
SHIFT: O (s, (
s..i))) ((-
Σ SHIFT, OS+1 log
Similarly, Lemma also contains useful (1 Ft,,, )2 term-inn
- in fact, the bounds in Lemma are extremely similar to those in Lemma and thus allow analogous analyses. This is actually an expected phenomenon, thanks our buto-balancing learning rates introduced in Section 4.2.
Adversarial Cases. Again, we utilize the [[[S++]] bound in Lemma and get the following theorem. Theorem 10 (Adversarial Bounds for UhShfiing Terms). In adversarial environments, the expecta- tion of the sum of W-shifting terms can be bounded by
T
< E[ (K log T)] = = (ox--VVo)))))
E
SHIFT,

---

Published as a conference paper at ICLR 2025
Stochastic Cases. Still similar to Dive's, condition Fi-1 and utilize 19 - Ct, to get [SHIF; | Fi-1] = O(s) 00 - xt, (formalized as Lemma 24 in the appendix). Thus, for stochastic environments, stopping-tima argument similar to that of DIV, yields Theorem 11.
Theorem 11 (Stochastic Bounds for V-shifting Terms). In stochastic environments, the sum of V-shifting terms can be bounded by
SHIFT, =0 -KOKT min
Rr 4
E
T log T
5.4 ANALYZING SUB-OPTIMAL SKIPPING LOSSES
This section controls the sub-optimal skipping losses when we pick a sub-optimal arm it # i", i.e.
Σ SKIPERR, 1[s i*] E1e skip 1.i.
1ls +
> 1a.l 1ile,, 2 C.s. - 1 + it].
For skipping errors, we need a more dedicated stopping-time analysis in both adversarial and stochas- tic cases. Different from previous sections, it is now non-trivial to bound the sum of SKIPERR, on those {4 S2 < M where M the stopping-time threshold. However, a key observation that whenever encounter non-zero SKIPERR,, St+1 will be 12(1)-times larger than S. Thus the number of non-zero SKIPERR, before S, reaching M is small. Equipped with this observation, we derive the following lemma, whose formal proof is included in Appendix F.I.
Lemma 12 (Stopping- Time Argument for Skipping Losses). Given a stopping tome the total skipping loss on those t's with # i' bounded by
time threshold M,
aa E M
T
log M
Σ SKIPERRR| 1/e * 1*]
$ M
Σ
1le
+
14
+
+
log [
log
Equipped with this novel stopping-time analysis, it only remains to pick proper threshold M for Lemma 12. It turns out that for adversarial and stochastic cases, we have to pick different M's. Specifically, we achieve the following two theorems, whose proofs are in Appendices E.2 and E.3. Theorem 13 (Adversarial Bounds for Skipping Losses). By setting adversarial stopping-tine thresh- old Made == (K log 7) -/TT1/, we huve
T
Σ
SKIPERR, 1(4 + i*] = =o(ok--/arVo))
Theorem 14 (Stochastic Bounds for Skipping Losses). By setting stochastic stopping time threshold M 4 T -
have I'r
1 # +i0 =0 =0(Klo8T g= A log
σ Amin
Rx
E
[SKIPERR||
4
CONCLUSION
This paper designs the first algorithm for Parameter-Free HTMABs that enjoys the Best-of-Bothh Worlds property. Specifically, our algorithm, uni INF, simultancously achieves near-optimal instance- independent and eestance-dependens bounds in adversarial and stochastic environments, respectively. uniINE INF incorporates several innovative algorithmic components, such as i) refined log- log-barrier analysis, di) auto-balancing learning rates, and iii) adaptive Shpping--lipping loss tuning. Analytically, we also introduce meticulous techniques including iv) analyzing Bregman divergence via partial derivatives and intermediate value theorem and v\ stopping-tine time analysis for logarithmic regret. We expect many of these techniques to be of independent interest. In terms of limitations, uni INF does suffer from some extra logarithmic factors; it 's dependency on the gaps { (A,1)) ) also improvable when some of the gaps much smaller than the other. We leave these for future investigation.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
This paper is primarily theoretical in nature, with the main contributions being the development of uni INF, the Best-of-Bothh Both--Worlds algorithm for Parameter- Heavy-Tailed Multi-Armed Bandits, and the introduction of several innovative algorithmic components and analytical tools. To ensure reproducibility, we have provided clear and detailed explanations of our methods, assumptions, and the development process of the algorithm throughout the paper. Complete proofs of our claims and results are included the appendices. We have made every effort to present our research in transparent and comprchensive manner enable other researchers to understand and replicate our results.
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their detailed reviews, from which we benefit greatly. This work was supported by the National Natural Science Foundation of China Grants 52450016 and 52494974, and in part by the National Science Foundation of China under Grant 623B1015.
REFERENCES
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256, 2002.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial ban- dits. Conference on Learning Theory, pp. 42-1. JMLR Workshop and Conference Proceedings, 2012.
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transac- tions Information Theory, 59(11):7711-7711, 2013.
Mingyu Chen and Xuezhou Zhang. Improved algorithms for adversarial bandits with unbounded losses. arXiv preprint 23.iv:23 2023.
Mingyu Chen and Xuezhou Zhang. Scale-free adversarial reinforcement learning. arXiv preprint arXiv:2403.00930, 2024.
Duo Cheng, Xingyu Zhou, and Bo Ji. Taming heavy-tailed losses in adversarial bandits and the best- of-both-worlds setting, In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Yan Dai, Haipeng Luo, Chen-Yo Yu Wei, and Julian Zimmert. Refined regret for adversarial mdps with linear function approximation. In International Conference on Machine Learning. pp. 6726-6755 PMLR, 2023.
Chris Dann, Chen-Yu Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In The Thirty Sixth Annual Conference on Learning Theory, pp. 5503-5570. PMLR. 2023a.
Christoph Dann, Chen-Yu Wei, and Julian Zimmert. Best of both worlds policy optimization. In International Conference Machine Learning, pp. 6968-7008. PMLR, 2023b.
Yuntian Deng, Xingyu Zhou, Baekjin Kim, Ambuj Tewari, Abhishek Gupta, and Ness Shroff. Weighted gaussian process bandits for non-stationary environments. In International Conference on Artificial Intelligence and Statistics, pp. 6909-6932. PMLR, 2022.
Yuriy Dorn, Aleksandr Katrutsa, Ilgam Latypov, and Andrey Pudovikov. Fast ucb-type algorithms for stochastic bandits with heavy and super heavy symmetric noise. arXiv preprint arXiv:2402.07062. 2024.
11

---

Published as a conference paper at ICLR 2025
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness fast convergence. Advances in Neural Information Processing Systems, 29, 2016.
Matteo Gagliolo and Jürgen Schmidhuber. Algorithm portfolio selection bandit problem with unbounded losses. Annals of Mathematics and Artificial Intelligence, :1:4-66,, 2011.
Pierre Gaillard, Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses. In Conference on Learning Theory, pp. 176-196. PMLR, 2014.
Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli. (e, ad-apptivve regret minimization in heavy-tailed bandits. In The Thirty Seventh Annual Conference Learning Theory, pp. 1882-1915. PMLR, 2024.
Hédi Hadiji and Gilles Stoltz. Adaptation to the range in k-armed bandits. Journal of Machine Learning Research, 24(13):1-33 2023.
Junya Honda, Shinji Ito, and Taira Tsuchiya. worlds for bandit problems. In International Conference on Algorithmic Learning Theory, pp. 726-754. PMLR. 2023.
achieves best-of-both-
Jiatai Huang, Yan Dai, and Longbo Huang. Adaptive best-of-both both-worlds algorithm for heavy-tailes multi-armed bandits. In International Conference Machine Learning, pp. 9173-9200. PMLR, 2022.
Shinji Ito. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear ban- dits. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 2654-2667. Curran Associates, Inc., 2021a. URL http:::/ .ew.. neurips ctpppper_ccepppr_ieeesseee Pap.aoaeae0bb---aa..pp.pp..
Shinji Ito. Phrameter-free multi-armed bandit algorithms with hybrid data data-dependent regret bounds.
In Conference on Learning Theory, pp. 2552-2583. PMLR, 2021b.
Shinji Ito and Kei Takemura. Bese-offthre--worldss linear bandit algorithm with variance-adaptive regret bounds. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2653-2677. PMLR, 2023.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-botthwwordds algorithms for online learning with feedback graphs. Advances in Neural Information Processing Systems, 35: 28631-28643, 2022.
Tiancheng Jin and Haipeng Luo. Simultancously learning stochastic and adversarial episodic mdps with known transition. Advances in neural information processing systems, 33:16557-16566. 2020.
Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved armed bandits: Firl with general regularizers and multiple optimal arms. Advances in Neural Information Processing Systems, 36:30918 18-188881 809977,, 2023.
guarantees for multi-
Anmol Kagrecha, Jayakrishnan Nair, and Krishna P Jagannathan. Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards. NeurlPS, pp. 11269-11278, 2019.
Minhyun Kang and Gi-Soo Kim. Heavy-tailed linear bandit with huber regression. In Uncertainty in Artificial Intelligence, pp. 1027-1036. PMLR, 2023.
Fang Kong, Canzhe Zhao, and Shuai Li. fest-of-three-worke analysis for linear bandits with follow- the-regularized-leuu algorithm. In The Thirty Sixth Anmual Conference on Learning Theory, pp. 657-673, PMLR, 2023.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chung-We Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference Learning Theory, pp. 2516-2564. PMLR, 2020a.
12

---

Published as a conference paper at ICLR 2025
Jongyeong Lee, Junya Honda, Shinji Ito, and Min-hwan Oh. Follow-the- hetp:wtte--petuued--eeeee with fr' f (e) chet-type tail distributions: Optimality in adversarial bandits and cest-of-both-worlees arXiv preprint (rXXv:24033051533 2024.
Kyungjae Lee and Sungbin Lim. Minimax optimal bandits for heavy tail rewards. IEEE Transactions on Neural Networks and Learning Systems, 35(4):5280-5294, 2022.
Kyungjae Lee, Hongjun Yang, Sungbin Lim, and Songhwai Oh. Optimal algorithms for stochastic multi-armed bandits with heavy tailed rewards. Advances Neural Information Processing Systems, 33:8452-8462. 2020b.
Jörg Liebeherr, Almut Burchard, and Florin Ciucu. Delay bounds in communication networks with heavy-tailed and self-similar traffic. IEEE Transactions on Information Theory, 58(2):1010-1024, 2012.
Haipeng Luo and Robert E Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory, pp. 1286-1304, PMLR, 2015.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning, pp. 1642-1650. PMLR, 2016.
Sudeep Raja Putta and Shipra Agrawal. Scale-free adversarial multi armed bandits. In International Conference on Algorithmic Learning Theory, pp. 910-930. PMLR, 2022.
Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory, 1743-1759, PMLR, 2017.
Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning, pp. 1287-1295. PMLR, 2014.
Aleksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1 2019.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
Tala Talaei Khoei and Naima Kaabouch. Machine learning: Models, challenges, and research directions. Future Internet, 15(10):332, 2023.
William R Thompson, On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
Taira Tsuchiya, Shinji Ito, and Junya Honda. Best-of-both--orldd algorithms for partial monitoring. In International Conference on Algorithmic Learming Theory, pp. 1484-1515. PMLR, 2023.
Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pp. 1263-1291, PMLR, 2018.
Lai Wei and Vaibhav Srivastava. Minimax policy for heavy-tailed bandits. IEEE Control Systems Letters, 5(4): 2020.
Yifan Wu, András György, and Csaba Szepesvári. Online learning with gaussian payoffs and side observations. Advances in Neural Information Processing Systems, 28, 2015.
Bo Xue, Yimu Wang, Yuanyu Wan, Jinfeng Yi, and Lijun Zhang. Efficient algorithms for generalized linear bandits with heavy-tailed rewards. Advances in Neural Information Processing Systems, 36, 2024.
Xiaotian Yu, Han Shao, Michael R Lyu, and Irwin King. Pure exploration of multi-armed bandits with heavy-tailed payoffs. In UAI, pp. 937-946, 2018.
13

---

Published as a conference paper at ICLR 2025
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems,
2020.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 467-475. PMLR, 2019.
14

---

Published as a conference paper at ICLR 2025
Supplementary Materials
Additional Related Works
16
A.I Multi-Armed Bandits
16
A.2 Heavy-Tailed MABs
16
A.3 Best-of-Both- BothWoo-tt Algorithms
16
A.4 Parameter-Free HTMABs
16
Discussions on Assumption 1 (Truncated Non-Negative Loss)
17
Bregman Divergence Terms: Omitted Proofs in Section 5.2
17
C.I Ar,i is Multiplicatively Close to Zr,ç. Proof Lemma 4
18
C.2 Calculating Wa,i via Partial Derivatives
23
C33 Bregman Divergence before Expectation: Proof of Lemma
25
C,4 Bounding the Expectation of Learning Rate S141: Proof of Lemma 6
27
C,5 Adversarial Bounds for Bregman Divergence Terms: Proof of Theorem 7
28
C.6 Stochastic Bounds for Bregman Divergence Terms: Proof of Theorem
28
V-Shifting Terms: Omitted Proofs Section 5.3
29
D.I U-Shifting Terms before Expectation: Proof of Lemma 9
29
D.2 Adversarial Bounds for V/Shifting Terms: Proof of Theorem 10
30
D.3 Stochastic Bounds for Vp-Shifting Terms: Proof of Theorem 11
30
Skipping Loss Terms: Omitted Proofs Section 5.4
E.1
Constant Clipping Threshold Argument: Proof of Lemma 12
31
Adversarial Bounds for Skipping Losses: Proof of Theorem 13
................................
32
E.3
Stochastic Bounds for Skipping Losses: Proof of Theorem 14
33
Main Theorem: Proof of Theorem 3
33
15

---

ALGORITIMMS Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORKS
In this section, we present a detailed version of literature review to include more discussion and related works.
A.1 MULEI-ARMED BANDITS
The Multi-Armed Bandits (MAB) problem (Thompson, 1933; Slivkins et al., 2019; Lattimore & Szepesvári, 2020; Bubeck et al., 2012) is an important theoretical framework for addressing the trade-off inherent in online learning. Various studies discovered different setups for the loss (or reward) signals. For example, most works focus on standard bounded losses where the loss of each arm belongs to bounded range such as [0, 1] (Auer et al., 2002; Wei & Luo, 2018; Lee al., 2020a; Jin al., 2023). Srinivas et al. (2009); Wu et al. (2015); Deng er al. (2022) assumed the losses following Gaussian or sub- Gaussian distribution. Another branch of works called scale-free MABs consider the case when the losses' range is unknown to the agent (Putta & Agrawal, 2022; Chen & Zhang, 2023; 2024; Hadiji & Stoltz, 2023). In this paper, we consider the heavy-taile loss signals where each arm's '' loss do not allow bounded variances but instead have their a-th moment bounded by some constant d", which called the Heavy-Tailes
poploration-exploittatie
Bandits (HTMABs).
A.2 HEAVY-TAILED MABS
HTMABs were introduced by Bubeck et al. (2013). who gave both instance-dependent and instance- independent lower and upper bounds under stochastic assumptions. Various efforts have been devoted in this area since then. To exemplify, Wei & Srivastava (2020) removed a sub-optimal (ogg)) factor in the instance-independent upper bound; et al. (2018) developed a pure exploration algorithm for HTMABs; Medina & Yang (2016), Kang & Kim (2023), and Xue et al. (2024) considered the linear HTMAB problem; and Dorn et al. (2024) specifically investigated the case where the heavy-tailed reward distributions are presumed be symmetric. Nevertheless, all these works focused on stochastic environments and required the prior knowledge of heavy-tail parameters (a, or. In contrast, this paper focuses free HTMABs, which means i) the loss distributions can possibly be non-stationary, and ii) the true heavy-tail parameters (a, or) remain unknown.
sath-ofbboth-woll algorithms in parameter-
A.3 BEST-OF-BOTI-WOOT
Bubeck & Slivkins (2012) pioneered the study of Best-of-Bott-Worldd bandit algorithms, and was followed by various improvements including EXP 3-based approaches (Seldin & Slivkins, 2014; Seldin & Lugosi, 2017), FTPL-based approaches (Honda et al., 2023; Lee et al., 2024), and FTRL- based approaches (Wei & Luo, 2018: Zimmert & Seldin, 2019: Jin et al., 2023). Equipped with data-dependent learning rates, Ito (2021a;b); Tsuchiya et al. (2023); Ito & Takemura (2023); Kong al. (2023) achieve Best-of-Both- Bothh-Woooldds algorithms various online learning problems. When the loss distribution can be heavy-tailed, Huang et al. (2022) gave an algorithm HT INF that achieves Best-of- S-----tthooldd property under the known-(ax, o) assumption. Unfortunately, without access to these true parameters, their alternative algorithm Opt HTINF failed to achieve near-optimal regret guarantees in either adversarial or stochastic environments.
A.4 PARAMETER- FREE HTMABS
Another line of research aimed at getting rid of the prior knowledge of or which we call Parameter-Free HTMABs. Along this line, Kagrecha et al. (2019) presented the GSR method to identify the optimal arm in HTMAB without any prior knowledge. In terms of regret minimization, Lee et al. (2020b) and Lee & Lim (2022) considered the case when a is unknown. Genalti et al. (2024) the first to achieve the parameter-fie property while maintaining near-optimal regret. However, all these algorithms fail in adversarial environments not to mention the best-of botttoo--othh--o Set-botth-wlddd worlds property which requires optimality in both stochastic and adversarial environments.
16

---

Published as a conference paper at ICLR 2025
B DISCUSSIONS ON ASSUMPTION (TRUNCATED NON-NEGATIVE LOSS)
In this section, we detailedly diseuss the existing results on Assumption 1 in HTMABs works. important to note that the truncated non-negativity loss assumption is not unique to study. In fact, it was also used Huang et al. (2022) and Genalti et al. (2024), and is indeed a relaxation of the more common "non-negative losses" assumption found in the MAB literature (Auer et al., 2002; Lee et al., 2020a; Jin et al., 2023). For better comparison, we summarize the exisiting results in HTMABs for the relationship between the prior knowledge of heavy-tailed parameters (a, ai) and Assumption in the following table.
Table 2: Impact of Assumption BoBW Guarantees for HTMABs
Assumptions
Known (a,
Unknown (ø, a)
HIINE achieves BoBW
uniINF achieves BoBW
With Assumption I
(Huang et al., 2022)
(Our Work)
Inferred by Cheng et al. (2024)
Weaker than Assumption 1?
Open Problem
(discussed below)
SAO-HT achieves BoBW
No BoBW possible
Without Any Assumption
(Cheng et al., 2024)
(Genalti et al., 2024, Theorems 2 & 3)
The truncated non-negative loss assumption is first introduced by Huang al. (2022), and their algo- rithm HT INF achieves nearly optimal automatically in both stochasite and adversarial environments with Assumption 1 and prior knowledge of heavy-tailed parameters (o, a.), as shown in Table 2.
Recently, Cheng et al. (2024) justified that when parameters (a, a) are known, BoBW is achievable without any assumptions (that is, Assumption is redundant when parameters are known). Specifi- cally, the algorithm SAO-HT presented by Cheng et al. (2024) achieves nearly optimal in adversarial and stochastic cases up to some extra logarithm factors. This result implies that Assumption is redundant for optiaml HTMABs when parameters are known.
When it comes to parameter-free setups, Theorems and by Genalti et (2024) highlight that achieving optimal worst-case regret guarantees is impossible without any assumptions. Moreover, Genalti et al. (2024) present an efficient algorithm Adar-UCB which achieve nearly minimax optimal on both instance-dependent and instance-independde regret bounds, under the stochastic environments and Assumption 1.
Therefore, adopt Assumption 1 when developing BoBW algorithms for parameter-free free HTMABs. Our algorithm, uni INF (Algorithm 1), achieves nearly optimal automatically in both stochastic and adversarial settings without knowing the parameters (a, o.) a-priori. Our result also demonstrates that Assumption is sufficient for BoBW guarantees in parameter-free HTMAAB.
As summarized by Table 2, while Assumption has been validated sufficient for achieving BoBW guarantees in both known and unknown parameter settings, the exploration for weaker assumptions continues to be intersting topic for future research.
C BREGMAN DIVERGENCE TERMS: OMITTED PROOFS IN SECTION 5.2
In this section, we present the omitted proofs in Section 5.2, the analyses for the Bregman divergence term DIV, Dv. (It. 21) (xx)) (z())) (V 2, zz) where Te, 2, are defined
== argmin L. (x)).
Z1 argmin L,, 2) (((2),
=EA[K]
and L, is defined as the cumulative loss
skip
L
1 = iz.
17

---

Published as a conference paper at ICLR 2025
By KKT conditions, there exist two unique multipliers Ze and Z such that
St
St
Vi E [K].
Zt,
1,-1,
Z
L Zt
We highlight that Ze is fixed conditioning Ft-1, while Ze is fully determined by l.
C.1 Zr, IS MULTIPLICATIVELL CLOSE Ft,a PROOF OF LEMMA 4
Lemma 4 investigates the relationship between Zt,s and 2t, By previous discussion, the key of the proof is carefully studied the multipliers Z, and Z,.
Lemma 15 (Restatement of Lemma 4). For every & E [T]] and i E [K], we have
1
2 Ft. S 2,, S 2Z1,i-
Proof. Positive Loss. Below we first consider le,,, > O, the other case E,,s, < 0 can be verified similarly, and the f,,,, 0 case is trivial. We prove this lemma for left and right sides, respectively. The left side 2,, S 21,0 According the KKT conditions, given S. and L (Le), the goal of computing 24 (2t) can be reduced to find a scalar multiplier Ze (Ze), such that we have
K
2t,5 (Z,)
and
K Σ
21,(Zz =
i=1
where
St
S. Lu,i - 11-1, + l,s
S
(1,(())
(A)
(12)
L
Note that each (A) an increasing function of on (-o0, s) Since Ee,,. > O, easy to see that it (Ze) < Ft.i,. Thus in order to satisfy the sum-to-one constraint, we must have Z, Ze and Z, Zi Le... Moreover, we have 2,,,, It.t and 24,1 > Fτ, for all # it. Therefore, we only need prove that 2t, 2 f. Thanks the monotonicity of ze,a (A), it suffices to find multiplier Z, such that
Ft.t
2t,i, (2t) 2
(13)
2
24,5 (Z.) $
(14)
EE[A]
With the above two conditions hold, we can conclude that 2, Z,, i.e., Zz is lower-bound for the actual multiplier Z, making 4 E A, and thus 24,i = 2,, (2,) 2 2t,i, (Z,) 2 Ze..
For our purpose, we will choose Z, as follows
Zz
if It. <
Z,
21
the unique solution to 2t,i, (A)
St.i 2
if 3t.b. 2 2'
We will verify Eq. (13) and Eq. (14) for both cases. For the condition Eq. (13), when 2t,i, 2 automatically holds by definition of 7, When Ft,i, 2. Therefore,
1 it
2.
1
we have S, = 4Cr, I1,a,) 2 2kii
(,i.
St L Ln-1,d +
S
L Z,
4
2n
18

---

Published as a conference paper at ICLR 2025
St
1-1 + 2
St Zx
(11-1 - Ze) .0 (1+ 2
81
(11- 2,3
1. 132,81
1+ 2
3
2
Ttiie
Thus, have 8,
holds regardless 2,,4, 1/2 not.
Le, -2
Then, we verify the other statement Eq. (14). When 24,4
1/4 we have
Σ
Ze,1 (Z.)
24,5 (Z,) +
Σ 24,5 (Z,)
[E[K]
2t,ie (Z+) +
Σ Iti
1.
if
For the other case Ttii 2 2. It turns out that the definition of Z, i.e. 24,4 (Z;) = Zii 2
solves to
skip
28,
Ze
+
Lt-1,
2,5e
F1,54
S: +
Cri
<
Z1
Di,h
Nt.i
St. + Au (1 I(,be)
S.
< Z1
Z1,b
S,(1 4x²,,, (1 - xt.s5e)
4 Dz,ūee)
12
S2 - 11}2
74 + 4.7 Iet.i))
where the first inequality holds by the definition of ze,te in Eq. (12) and 0
skip 4,00
Cli
]. ) S am (1 ) For all + de we then have
S,
St
S.
La.i
Z,
1 Zt
S
S, (, - 1)2
1 Zi
2ot (1-2).))
S
(1--155 - -Zz) (1 (1- [hi 1.: 1:)11 (1-21.))
S.(2 1)2
(2 - 1)2
= Dtji
1- 1- Fz,b A.17, 2e (1 It....)
Since we have Ft,i S E Eiji,
Lt,i =
Feiies then
S
1 4. b1 + 4x
4.22
2r,(
L
Zz
< Zt,i"
1
4x23
De,i Aurti -
(15)
19

---

Published as a conference paper at ICLR 2025
Therefore, have
(a)
407,1
Σ
28,5
Zt)
S
Rti5 +
4r 1 Σ It,
2
[E[K]
ip/t
42,,11 (1 Ftt.ie) (1
43
(6)
$
11.s + =4x2,i (1 (1 I2,,.)
2
(0) S 1,
where step (a) is obtained by applying Eq. (15) to i i and 21,4, (Zi) /2; step (b) is due to Ft,h 2 1/2; step (c) is due to the fact that + 2/2 + 4x- x) has maximum value less than 1.
Then, we have already verified Eq. (14), which finishes the proof of 21,,, 2 22.5.
The right side 2,,4 I 2x We then show that t,, 2 holds for all i [K]. The main idea is similar to what we have done in the argument for the left-side inequality, will find some Z under which we can verify that
24, (Zi) S 2 Vi 2r,1 (Z,) 2 1.
(16)
(17)
VE[K]
We can then claim that this Z, is indeed an upper-bound of the actual multiplier Ze.
Let j argmax Ft,j, we just take Z, to be the unique solution to zt,j (A) 2rt.j", which solves
S. 2
Z = Ze +
One can verify that
St
21.5 (Zi)
(L--1.3- - Zz. (1
S,
[Te
1.3 Zz) 2.5
-1
I2.j"
Ft,j"
2x
For [K]] f" it is easy to see that
S
2,,
I4-1,1
Zz
S.
25
S
(L--1 - -Zz) (1
(Io-
21)
Fe,b
F1,1
1
2.
Hence Eq. (16) holds. In order to verify Eq. (17), note that
Cr. <
St 4 (1 - x4,d.)
Ee 5
Ft,sc
When Zt,i, 2 1/2, we have
S:
L.s. < 4. 4. 2
111 Ejtti St.j
20

---

Published as a conference paper at ICLR 2025
St
2
Z1 - Zr.
Therefore, we have
S.
S,
28,4 (2i)
2
Lr,se Zz 11-1,h + +Z, Z, Zt
Therefore,
Σ (Z,) 2t,te (Z,) + Σ
2 (Z,)
(18)
KE[K]
ifi
2r,, (Zi) + Σ (2,)
2 21,4 + Σ
Ft,i 1.
On the other hand, when Te,te < 1/2, we have
Lei. - St
St
S: 2051,6
<
4ot,i st.i.)
Art,i
If ø1.1, 2 " we have E,,, < (2/(22))-) = Z, Ze Then we can apply the same analysis as Eq. (18). Hence the only remaining case is 2t,4 < 1/2 and Dt,te < Zej", where we have
F (Zi) It.j Fts. It.is Ftih Zt.ie (Zt).
(19)
Therefore, we have
Σ Zt,((Z,) -1 |2 (Zt) - xt.jj" + ( It... + Σ
(Zx)
It
(E[K]
(ptiee)
Zt,i (Z,) Ft,t
2
hence EiERK] 2,, > 1. In all, we show that Σie(K] (Z,) 2 1, and we are done.
Negative Loss. The proof of case E,, < is very similar. In this case, we have 21,1, (Z,) > Ft which shows that EEE(K] (2.) > 1. Therefore, we have Z, < Zz. which implies 2, < Zt, for i o it and 24,4, > It,s.. Therefore, we only need to verify that 2t,t, S 2x,,i, and 24,4 2 1 i o it. We apply similar proof process above statement.
2 2z,5 for
For the first inequality, we just need to verify that there exists a multiplier Z, such that
2t,5e (Z.) < 2xri
(20)
21,1 (7.) 2
(21)
KE(K]
We set Z, as the unique solution to 26,1, (A) = 2I Then we have
St
Z:
L 1,80 ie + Eeeie
2.r
St
St + L1-
pkip
1,5t
+ 2
Z1,be
St Cr
> Zi + 2 Dt,be
St
St
Zx +
21t.it
4x (1 - Ft...))
21

---

Published as a conference paper at ICLR 2025
S2 1)
Z. 4rr,i. (1 - (1,
If Ft, 1/2, have Zz 2 Z4- Therefore,
Σ VE[K]
2 2 (1) 2 Zt.ie (Z.) + Σ
2e, (2,) 2 + Σ Fee 21
ifft
For the other case, if st,4, 1/2, we have for any i
+ it
St
(2,)
S, (2v,
1 - Ze +
Azc.ie (1-ze.i))
2T -
Nts
1 1+ Tz,i
Awr,i (1 322
+ 2
2 Nt,s
42
A
Tt, G3 -
where the second inequality holds by 20,,,
1 > 0 and Ft,s S It,., Therefore, we have
Act,i 2x
4xr,i (1-3t,,))) 2 1.
Zt,i (Zt) 2 f. +
Σ
Ttii
6Z -1
6 1
iE[K]
For the second inequality, we need to verify that there exists multiplier Z, such that
1
24, 21, (Z))
2 21,s
vi vi
(22)
Σ 20,1 (2.) < 1.
(23)
HE[K]
Let j = argmax Lt.j- Then we set Z, as
S.
7. 7
D1.3"
Hence, we have for any i + is.
S:
21,i (Zr)
(Lc-1,3 -Zz) (1+
S,
(1r-1:: Ze 3
Tt.i
-tti 1
Ft.j
2 Dt,i 2'
where the inequality holds by Ft.j > F1.s. Therefore, we have
1
(Z,) 2 2 FtZt-
Then we verity Eq. (23). Since we have 7, S 2,, then 21, S oe, for any i it. Thus we only
need to prove 2,,i, (Z+)= S Zt,i.. Notice that
S.
S
2t.
L1-15, Zz + le.i. +
St 5 xes"
-:-1, Zz
S.
xe,""
4ma,is (1 P2.
where the inequality is due to leie = phip
/ 2 /t.tt///an and the definition of Cr., in Eq. (3).
we have Tei 2 1/2, then
S.
Sz
S S.
2
Ft.j"
4x - Iz...)
Ft,5"
2(1 Ft.is
22

---

Published as a conference paper at ICLR 2025
Se
Se
"1.5"
2 Lijti
Ft.J
St
F1,5"
23rLj
2 0.
Therefore, we have Zt,i, (7+) S Ti, which implies that EiE(K] (1,((2)) S Eielk] Tt, 1. For
the case when Vei < 1/2,, also have
St
S
S.
St
4w (1 Vr,s.)
V1,5"
231,i
If Zt.z S 2 we still have 2t,r (Ze) S Zt,i,- Otherwise, for zz.j" > 2xiii we can write
St
Zt,i (Zt)
In-1,56 - Zx + 41,, + St
21.5"
8t
T
7x +
S
Ne.."
42 -xe.te)
Ftitk
Dtii
1
Iz,jj"
4(1 xtt,1))
Notice that here Tt.s E 1/2]. which implies that 1 + have
2 1/2. Therefore, we
x1."
101 [1.4)
1
21,5 (Z,) I 21e
2 + 21,66"
2
Since 21,5 (Zi)
1 Fes we have
Σ
(t) S
Σ
Ft.i +
2 2t. +
+ Ftiis = 1. 2 2h.s
In all, we conclude Eq. (23) and prove this lemma.
C.2 CALCULATING W VIA PARTIAL DERIVATIVES
By inspecting the partial derivatives of the multiplier 2, with respect to the feedback vector &g can derive the following lemmas on Wt.i-
Lemma 16. We have
SP..e ΣkETKo SP,
Ft.i
1/1 1/1= it]
11
where
G. := arggiinn( + Xle, x) + (z).).
ZEA
Here X is some constant ranged from (0, 1), implicitly determined by Ee.
Notice that conditioning on the time step before t 1, Zz,i only depends on E,c. Then we denote
Proof.
az,
(0) = de,s i,=0;;
where e; is the unit vector supported the i-th coordinate, and 0 is scalar.
23

---

Published as a conference paper at ICLR 2025
Notice that
Σ
1,
(24)
Lrs Ze
JE(K]
JE[K]
Then partially derivate E,, on both sides of Eq. (24), we get
Σ jEパK]
St
(1[j i]
Z =
2/,
Skip 2,
2 = 0,
(4.5 - 2
S₁
S
jE[K]
which solves to
z
Z1,4 ΣjE(K] zi.J""
Similarly, denote
24 (0) =
Tles d,,
Then according to the chain rule, we have
z St
2/,3
2
Σ KE|K]
1 51
We denote
Dwi.
w/,,5 (0) =
ale =0,
Recall that W1,
Tei (Ce, (Z, Zi)), hence
2
wh.i5
Ftsi
1 j]
Σ
St.
St.
kE(KK]
)
Ft.i
1 = 5] - -2t,)
Σ
27,
S
kE[K]
Thus according the intermediate value theorem, we have
Si. ERE(KO St.kk
Wr,1 = Tes
It.
1li = it]
S
where
4. argmin(L,... =EA[K]
Xle, z) + vr(2)),
and À is some constant ranged from (0, 1), implicitly determined by T. Furthermore, Lemma guarantees that
22,1/2 < Ges S 201, Vi e [K].
(25)
n
24

---

Published as a conference paper at ICLR 2025
C.3 BREGMAN DIVERGENCE BEFORE EXPECTATION: PROOF OF LEMMA 5
Lemma 17 (Formal version of Lemma 5). We have
DIV. S 2048 S (L - x1,t.)².
Therefore, the expectation of the Bregman Divergence term DIV, can be bounded by
E,DI,, Fi-1) S 2048
Σ S S Fe- zz,))²
(E(K]
Moreover, for any T E (T), we can bound the sum of Bregman divergence term by
T
DIV, S 4096 ST+1K log T.
Proof. Recall the definition of Wtii, we have
DIV, Σ
S,(w, - log(1 + wr,;))
KE(R]
By Lemma 4, we have W1,1 = 0t.5/ 21,1 - 1 E [-1 Therefore, since x - log(1 + x) S xx²
we have
DIV, 2 Σ
S. (Ali = is i/w Ali + is]w(.))
(26)
iE|K]
By Lemma 16, we have
Gi.
11s = Eess St
It.i
1/ 11== it]
ExE(K) Si,
and Ge satisfying / < Cei S 201 by Eq. (25). Then, for i + ie, we have
Whes -ship.
Ft.1
Se.
S
ΣxE[K] S2,K"'
Shit
2
wh, (2skip)2
11.
(
F2.
52
St
2.
(ENE(Ky C7.1k
ElEIKT T7.,k)
And for i its
skip lr,in
1
Ejtt, Shis
Wiibe
S₁
EKEIKY G2.x""
(Eigti (2.) )²
(Ejyih shis) 2
skip (le,3)
1
256 (kipp
whit
5
(ENELK) Gi,))
5
(ENe(K) x2,x)
Therefore, have
Σ [E[K]
St . (1)² = &t]wī, + [ + is]w?,))
Σ EEjr, xh.) 2
(27)
27 22.51
< 256
(ckip)) S11
+
[kE[K]] 2i
EKE(K] 27,
Notice that
Σ Ejtt, aids )²
2
Eigt, 27. +
+
EkE[K] x2,
2 x
EkEjKy TF,
ERE(K] 22,x
EkE(K] 27,4
ExejK 2Ī,1
25

---

Published as a conference paper at ICLR 2025
For Zt,4 $ 1/2,, we have
- -x1,,,) 1.
Then we have
2
2
Eitti #2.
11
+
$1+1.1588
8(1 -1... (28)
Σ [E[K]] Li,k)
Σ ΣNE[K] Fiik ΣmE[K] 2
For Ftii 2 1/2, we denote
F7,2
tr == EME[K] Lith
E [K],
2
which satisfies Te,i S 2 S 4x/, for every E [K]. Since Tti 2 1/2, we also have 1/2 S Feti S 3r S 1. Therefore,
Eipse Li.
tt
(1 It.i. 2 + Tr,i Σ It.
+ ΣkE(K) T7
EkE[K] Ti,k)
ΣxE[K] Fi,k
ifte
S (1 It.te )²
4
(29)
2
< It..i ) +
Σ
Itee
iffie
S 55(11 - xz,ū,)
Combine these cases, we get
DIV, < Σ
S. (1li= = is/w,, + 1li # islw?,))
iE[K]
< 256 (L ST (11- Exe(K) 27
2
Σ Σizi Lh. Exe(K] 27. EnE(K] 27,
$ 2048
( S -11 11--0 12,.
where the first inequality is due to Eq. (26), the second inequality is due to Eq. (27), and the last inequality is due to Eq. (28) for Tt, S 1/2 and Eq. (29) for Tr,i, 2 1/2.
Moreover, taking expectation conditioning on Fz-1, we directly imply
E[DIV, FF-1] S 2048
Σ ST E KE[K]
Fi-1l - x2.;)
Consider the sum of DIV, we can write
T
T
Σ DIV. < 2048 Σ ST
(2hipp2 (1 - Ne,5 )
Notice that by definition of S441 in Eq. (4), we have
(K log T) (St+ - S?) =
(elip)) (1,te)
(1 -2.
Moreover, since | is controlled by Cr.s.. we have
S - S + Cr., (1 - xx,,, (K log T) S: (1 + (4Klog () < 28?
(30)
where the first inequlity is due to | S Cr,i, and the definition of Ct,s, in Eq. (3), and the second inequlity holds by T 2 2. Therefore, as t.t.
skip
eelip t,ae
trivially, we have
T
T
DIV, < 2048
Σ S.
(Clip) (1 It... )²
t=1
26

---

Published as a conference paper at ICLR 2025
T
$2 St.
2048 K log
St
1=1
(St-1 + St)(S Si)
2048 K log T
S1
1=1
2048(1 + /2) K log T
S4+1 Se
4096 ST+1K K log
where the first ineuqality is by Lemma 5 and | S | the second inequality is due to the definition of S1+1 in Eq. (4) and | s 1 and the last inequality is due to the S S v2S, by Eq. (30).
C.4 BOUNDING THE EXPECTATION OF LEARNING RATE ST+1: PROOF OF LEMMA 6
Recall the definition of S, in Eq. (31), we have
T
ST+1
4+
plii 2 (1 I1,..) (K (K (og T)
t=1
T
Clip (K T)-1.
4
t=1
Therefore, to control E[ST+1], 11, suffices to control [[S] where S defined as follows:
S: 4
Celyy 2. (KlogT) -1
(31)
The formal proof of Lemma 6 which bounds B[Sr+1 is given below. Lemma (Restatement of Lemma 6). We have
B[Sr+1] $ 2 o(K log T) T
(32)
Proof. By clipping operation, we have
1
celip t,
S Cr.. St 4(1 - -xt,i,)
S.: S ST+1 S.
Therefore, we know
T
T <
4 +
Σ
clip t.se
(K log
Σ
|e,
S2-0 (K log T
4 1=1
where the inequality is given by 22 > 16, /clip
S S and |ettip
S le Hence,
T
S < 3 K log T)
Σ 1ee
1=1
Take expectation on both sides and use the convexity of mapping i + 2a, We get
4
E[S] <
(Klog -// ... .. 1//0
2 log T) 1/a. 1/10
The conclusion follows from the fact that ST41 S.
27

---

Published as a conference paper at ICLR 2025
C.5 ADVERSARIAL BOUNDS FOR BREGMAN DIVERGENCE TERMS: PROOF OF THEOREM 7
Equipped with Lemma 6, we can verify the main result (Theorem 7) for Bregman divergence terms in adversarial case.
Theorem 19 (Formal version of Theorem 7). We have
Σ
DIV, s 8192 1192-oK2-1/aqpl
(log (oogg))"-// 1-1aa
Proof. By Lemma 17 and Lemma have
T
E
DIV, I 4096 E[Sr+1] K log T
8192 /o/ll//or/////// (log
Ignoring the logarithmic terms, will get E
T
DIv.
5O(ok-
C.6 STOCHASTIC BOUNDS FOR BREGMAN DIVERGENCE TERMS: PROOF OF THEOREM 8
We first calculate the expectation of a single Bregman divergence term E D,V,, Fe-1).
Lemma 20, Conditioning on Ft-1, the expectation of Bregman divergence term DIV, can bounded by
D Fi-1l 4096 S1-000 (1-2,(1--)
Proof. From Lemma 17, we have
DIv, Fi-il S 2048 ST ((Cgti)) - xe,sr)? Fi-11
(33)
$ 2048 ST'EE
(Celip
22 x2,,,) )2 Fi-1
(34)
1,te
By definition of Cr.i, in Eq. (3), we have
R(DIV, Fe-1] < 2048
S. S E C22- - Ft,i, 2- Pe 12 (1 19.
S -!-a
s 2048
o [1 - -1(,i,) F(-1]
a
s 2048 S1-a
a
a Σ 11,5 - x1,.) a
iE[k]
Notice that
Σ KE(K]
21,(11 -1,,)
Σ
Tz,i + Dz,5- (1 x(,t-)
(1 x(,i-) + D1,5- (1 x2,5-)
2(1 It,5")
Therefore, we have
E[DIV, Fi-1l < 4096 0 F1,5') ).
Then we bound the sum of Bregman divergence in stochastic case by the stopping time argument. Theorem 21 (Formal version of Theorem 8). In stochastic settings, the sum of Bregman divergence terms can be bounded by
T
1 - RT. < 8192 16384='T K min o log +
E
DIV.
4
28

---

Published as a conference paper at ICLR 2025
Proof. We first consider stopping threshold M1
M1 = inf {s > 0 4096 s s'-0 00 I minn4
(35)
Then, define the stopping time Ti
Ti = inf Mi A
Since we have St+1 S (1 + (4K log 7) - 2S. by Eq. (30), we have ST, S 2M, Then by Lemma 17, we have
DIV,
< 4096 [ST (K log T)] - 8192 M1 logT.
Therefore, by Lemma 20,
T
E
DIV,
= E
DIV, + E
E|DIV,
Fi-1l
Ti
T
S 8192 M1 K logg T + E
4096 EE S a(1 - xz.s") F(
Li=
8192 M1 K log T + E
4096 M - 0 )2,50)
where the last inequality due St 2 M for 2 and a 0. Therefore, by definition of Mi. we have
T
T Σ (1
Klog T + Amiu
E
DIV
< 8192
min
J n-T
E
x2Ss.)
(4-4096)
T1
8192 16384
I
K log T +
Rr.
min
4
where the first inequality due to the definition of Mi Eq. (35) and the second inequality is due to
Rr 2 B[Amin Σt -t,5.] in stochastic case.
D V-SHIFTING TERMS: OMITTED PROOFS IN SECTION 5.3
D.1 V-SHIFTING TERMS BEFORE EXPECTATION: PROOF OF LEMMA
First we give the formal version of Lemma 9.
Lemma 22 (Formal version of Lemma 9). We have for any E [T].
SHIFT, S
Σ
(S.-1 5:)(-log(()) S S. (G..)) ( Iz,5.
<E[K]
Moreover, for any T E [T
1]. we have
SHIFT, S ST41 - K log T
Proof. By definition of V, in Eq. (2), we have
SHIFT, (V.+1 (T) vz(ū)) - (Ve+1(Fe+1) - (x(++11))
< Σ (S St) (loool(gg))
A
S - S
< (K log T')
8 + St
29

---

Published as a conference paper at ICLR 2025
1 5
celip ( (1-I,,,))
2
where the first inequality is by L 4+ (z) (2(2), the second inequality is due to the definition of y. and the third inequality holds by Si+1 S.. Moreover, for any T E [T 1], we also have
SHIFT,
Σ
( (ee1 v.( (1.+) v.()))))
< > (S1+1 - Sii) K KoogT
ST+1 K Klog T.
D.2 ADVERSARIAL. BOUNDS FOR V-SHIFTING TERMS: PROOF OF THEOREM 10
In adversarial case, we have already bounded the expectation of [[[T+1] in Appendix C.5. Therefore, we have the following lemma. Theorem 23 (Formal version of Theorem 10). The expectation of the sum of V/shifting terms be bounded by
E
SHIFT,
2 ///o (
Proof. By Lemma 22, we have
E
SHIFT,
$ E[Sr]
K log T s E[Sr+1] K log T.
Notice that Lemma 6 gives the bound of [E(S+11). Therefore, we have
E
Σ
SMIFT, 2 ak 12oo
D.3 STOCHASTIC BOUNDS FOR V-SHIFTING TERMS: PROOF THEOREM 11
Again, we start with a single-step bound on SHIFT,
Lemma 24. Conditioning on for any E [T - 11. we have
E[SHIFT, FF-1] S -1-00 o 122,5)
Proof. According to Lemma 22, we have
E|SHITT F.-1] -
E
clip
(1
Ie.ie ) [
2
By definition of Cr,ú in Eq. (3), have
1
E[SHIFT, F.-I] _
5,
E [C (1 It.ie 2--a Re (1 ze,i.) [r-1]
2
Sl-a
<
0 B[(1 - It,2,a F(-1]
2 42-a
1
91 " Σ
21,1 -2,,)
2
<E[K]
30

---

Published as a conference paper at ICLR 2025
By similar method used in the proof of Lemma 20, further have
Σ
21,((1 - 22,5) 1 Σ
Ft,s + x1.5- 21,5-) S 2(1 21,5
AE[K]
Therefore, have
E|SHIFT, FF-il S St - - I2t,5))
Theorem 25 (Formal version of Theorem 11). We can bound the sum of & U-shifting terms by the following inequality.
E
SHIFT;
I 2Ko
A n-T log T + - RT
min
t=0
Proof.
Similar to the proof in Theorem 21, we consider stopping threshold M2 defined as follows
M2 = inf > 0 : a a0 I mia/44-
Then similarly define the stopping time T/
Tz = inf (4 2 1 S. 2 M2} AT.
Therefore, we have Sy s - - 2M2. Then by Lemma 22, we have
E
SHIFT,
E E[S K log T < 2M2 K log T
1=U
Therefore, we have
T-1
E
SHIFT,
E
SHIFT,
+ E
E[SHIFT,
Fe-il
L
2M2 Klog T E
Σ
B a(1 x2,5')) Fr-1)
T-1
$ 2M2 K log T + E
M2 E 21,5 F(
where the first inequality holds by Lemma 24 and the second inequality is due to S. 2 M2 for 2 T2 and 0. Notice that Rr 2 E. E Amin Te.3 )] We can combine the definition of M2 and get
1 2 A - go K log T + Rr
E
SHIFT,
min
4
E SKIPPING LOSS TERMS: OMITTED PROOFS IN SECTION 5.4
E. CONSTANT CLIPPING THRESHOLD ARGUMENT: PROOF OF LEMMA 12
Proof of Lemma 12. For given clipping threshold constant M, first perform clipping operation
Clip(Ea,,, M), which gives a universal clipping error
li M l1,6, M
SKIPERR
Univ UniX(MM)
-M l < M
Le,b + M l,, < M
31

---

Published as a conference paper at ICLR 2025
If Ct.,, 2 M, then this clipping is ineffective. Otherwise, get the following action-dependent clipping error
SKIPERR, AcDDep (M) (
SKIPERR; - SKIPERR, Univ {
Cr.i, < M Cr.,, 2 M
Therefore, we directly have [SKIPERR S [ Univ (M) + [SKIPERR, ActDep (M)) Another important observation is that if SKIPERR, (M) O, we have S, S M, (Lthe)) C and [SKIPERR, AcDDe (M)l - M, which implies that
S S + C2 (1 --t,5,? (Klog T) = = (1 + (16K log 7)
Thus the number of occurrences of non-zero SKIPERR, Act (M''s is upper-bounded by [log 1155/11111 1- 1og2)-1/1 M Then we can bound the sum of the sub-optimal skipping loss by
T
E
SKIPERR/| 11e + 4*]]
S II
SKIPERR, Univ (M) 1 # 87]
+ SKIPERR, ActDep (MDI)
<
E
Σ le,tal Illee,.. 2 M] 1lie # i4]
+ M Eloog / /I+16K log M] + M
log M
S SonMI-BB
1/s + i*]]
2M
log(1 + (16K log T)-1) + M.
E.2 ADVERSARIAL BOUNDS FOR SKIPPING LOSSES: PROOF OF THEOREM 13
Theorem 26 (Formal version of Theorem 13). By setting Mady == oK log T) 1/ we have
SKIPERR; 1/6 # (*)
(log7)) +
2 - (log 2)2- + +loog 2 log K log log T
2
S a K AKK-~/o7 VoTm
Proof. Notice that we have 2x 2 log(1 + 1- holding for 2 1. Therefore,
E
SKIPERR,
live + i*]]
So 00d (Maddol-
Σ live + 1*]
2d log adv K log T.
By the expression of Made we have
T
E
SKIPERR;
1[. + 1*]]
S (K K log T) 1//0/%// + 16 o K log T) 1-1////// .lol//loog.. log (o(K log T)) 1/721//
-ao-////%o. (1og + (logT)2-14 2looo log log log T)
32

---

Published as a conference paper at ICLR 2025
E.3 STOCHASTIC BOUNDS FOR SKIPPING LOSSES: PROOF OF THEOREM 14
Theorem 27 (Formal version of Theorem 14). By setting M = 4a-10 min we have
SKIPERR
lit # +1
4- (2 alooo log(l/Amin))
1
K log T
RT. 4
min
a-
Proof. Since we set the constant in stochastic case as M = 4 - log(1 + 1) Vx 2 1, we have
then by 2x: 2
miu
E
SKIPERR;
10e # 1*]]
T 1 E
S 5 (M
life # ii] Σ
+ -M
logg M
K log T
T
-
min E
Σ
The + i*]
K log T क min
(2 4 a log + log(1/ (1/(1m))))
Since we have
Rr 2 E
Σ min 16, #14
which shows that
Σ SKIPERR
1/v + i']]
K log T. -
1
(2 log loooo lololl/////// log(1/Amin)) RT.
F MAIN THEOREM: PROOF OF THEOREM
In this section, we prove the main theorem. Here we present the formal version our main result.
Theorem 28 (Formal version of Theorem 3). For Algorithm 1, under the adversarial settings, we have
Rr < oK 1u-/aa
(8195(1og ( ()og + 22oog log K
2
2 log log T + ok
=ō (oKK-//oT)))
Moreover, for the stochastic settings, we have
-
4
σa Amin
Rr S 4. K
log T
8192 16384 + 2
2 + log
Amiu
0: 1
=0 =0
o-1
K
log T log
Amin
A
A Amin
33

---

Published as a conference paper at ICLR 2025
Proof. We denote y E RR as the one-hot vector the optimal action i E [K], i.e. y4 = 1 i*).
By definition Ry in Eq. (1), we have
T Σ
RT
E
y,
be)
Consider the adjusted benchmark y where
i + i i=
By standard regret decomposition in FTRL-based MAB algorithm analyses, we have
Rr
E
y e
+
EE
c D,
+ E
cz
y he
pthipy
(36)
BENCHMARK CALIBRATION ERROR
MAIN REGRET
SKIPPING ERROR
As in typical log- bag-barier analysis, the Benchmark Calibration Error is not the dominant term. This because we have, by definitions of and ÿ.
T K Σ -L
V y. eskipy
S
Blle So,,
T
which is independent from T. Therefore, the key is analyzing the other two terms.
By the FTRL decomposition in Lemma 29, we have
T
T
MAIN REGRET =
(o
y. ep
=E
Σ
c
T
T-1
E (1r, 21)1 +
Σ ((((++1 - v,(T)) - (v ( - v2(2++1)))
1=1
1=0
where
Dv. (y. x) (.( ( xx)
given the Bregman divergence induced by the t-th regularizer v, and 2, denotes the posterior optimal estimation in episode namely
+ Mo(z) =((=)))+W(())))
= argmin *EAIN]
As mentioned in Section we denote DIV, == Dv. (I,, 2,) for the Bregman divergence between æy (7) ( (1++1(0(41) - (x(++)))) be the U-shifting term, and SKIPERR; := Ee,i, مkip l, [1,,, 1 2 C.a.] be the sub-optimal skipping losses. Then, we can reduce the analysis of main regret to bounding the sum of Bregman divergence term E(Dvv,] and V-shifting term E [HHHIF..). Moreover, for sub-optimal skipping losses, we have
and under regularizer 1 SHIFT, := [ 1-1
(x, y. l, echip)
Σ (at,5 - v:) (Le,i t,5
<E(K]
Σ i
Le,i (e,
skip
+ (It, 1) (4e,- (,4-
skip
E [|SKIPERR||
lie + i*] Fe-1l + (x - 1) (4..0
skip
Notice that the factor (x 1) in the second term is negative and Fe-r-measurable. Then we have
E
cakip Fr-1]
E [1 2 C2,-1 c,,5 221200 0.
34

---

Published as a conference paper at ICLR 2025
where the inequality is due to the truncated non-negative assumption (Assumption 1) of the optimal arm i". Therefore, have (x,, 1) (le,z- (.)))) Fr-1] and thus
) Fi-1l & E|JSKIPERR:] 1 + i-] F(-1): [x y, Rr
which gives an approach to control the skipping error by the sum of skipping losses SKIPERR;" where we pick sub-optimal arm in # i". Formally, we give the following inequality:
SKIPPING ERROR E
Σ [KKPEERR/
1[i # 1*]
To summarize, the regret Rr decomposes into the sum of Bregman divergence terms D[V,, the W-shifting terms E[SHIFTT), and the sub-optimal skipping losses E[[SKIPERR/| 1 1 o 2"]], namely
Ry
E
Σ
DIV,
E
SHIFT,
+
E
SKIPERRR,|
1 # 1*]
taK.
BREGMAN DIVERGENCE TERMS
V-SHIFTNG TERMS
SUR-OPTIMAL SKIPPING LossEs
We discuss the regret upper bound under adversarial and stochastic environments separately.
Adversarial Cases. According to Theorems 19, 23, and 26, have
r
RT
DIV,
E
SHIFT,
+
SKIPERR
116 +1)
tok
< 8192 oK 1//71/0 (log 27) 1-1-1// + 2 .2000 ook 1/- 1/2 (log
+oK 1//-////'/..... (10gT) 1- (log 2-2--//- + 12 22og σ
log K
log log + oo
= =o =oK'-/oT%/. [8195[log]] 7) 1- + (log + 2og
2
2
log K loglog + oK.
2
Stochastic Cases. According to Theorems 21, 25, and 27, we have
T
Rr < E
DIV,
+E
SHIFT,
E
SKIPERRR|
lle + +i]
toK
1=0
< 8192 16384
KA
log
Rr
min
2Ko
log
T
RT
min
4
4a' T
aa
A min
K log
(2log + a log o (001))mmn))
- Rr toK
a
8192 16384 +2 2+ 4-²1 log T
3
< K
a a- 22og 4 + log
Rr.
Amin
Amin
4
which implies that
--
σ
Rr < 4.
K
log T. 8192 16384 + 2
2 2 4 log
A Amin
A
Amin
Therefore, we finish the proof, which shows the BoBW property of Algorithm 1.
The following lemma characterizes the FTRL regret decomposition, which is the extension of the classical FTRL bound (Lattimore & Szepesvári, 2020, Theorem 28.5). Dann et al. (2023a, Lemma 17) also gave similar result, but include full proof here for the sake of completeness.
35

---

Published as a conference paper at ICLR 2025
Lemma 29 (FTRL Regret Decomposition). In amiINE (Algorithm 1), we have (set So ffr simplicity),
T E De (at, 2,)] + (((( V v (V.(xs) v
E
Σ
y.
Ri)
where Dv, is the Bregman divergence induced by v and is given by
Zt == argmin ((,)))) + wo(z))
SEAIN]
Proof. We denote L, = E Eg. Denote f : IR* + as the Frenchel conjugate of function f: RRK R. where
((y)
sup ( x) f(x)} mERK
Moreover, denote J _ + as the restriction of f R² + RRo on A AKKI, i..
[((x), a E A
F(x)
00, x $ A
Therefore, by definition, we have
2, VV (r)),, x2 = (-
Then recall the properties of Bregman divergence, we have
De. (xx, z1) Dv, (VW (-b:)) = (- - Lt-
Therefore, have
T
T Σ
c ú. 21) = ( LT)
(x Le)
t=1
1=1
T
(-Li) - (- - (-L-(-))))) + Eo-1))
1=1
+ (0, -TT) Σ
V -t:) (
T
Dw: (-Le, -1--1) + (ÿ, - -TT)
Σ
V (-L,) -V, (-
t=1
T Dv, (Zi, 21) -L)
T
Σ
[ (-Le) - V. (-Ln-)))
t=1
For the second and third terms, we have
T
U. LT)
(.))),) (7((-1--))
(7, -rr)
1. ( L.) (0: L, L.-1) + vx()
( LT)
sup x
{(x, -Le) vx(x)) (ar:: - LL-1)> + V (2xx)
< (ū, LT)
((0++1) Lt) - -v,((c++) - (10,, 1)- + ve((x))
36

---

Published as a conference paper at ICLR 2025
sup *EAiN]
{ -Ln) - (x(x)) + (xr, 1..-Ly -LT-1) - (2(()))
T
= (ū. - LT) -
Σ
(vr()))) - v/21((0)))
sup mEAin]
{(ar, -Lr) - (a:))
1=1
(.. - -TT) - (D) - sup
LLT) - (2)())) + VT(
(vx( - (2z)
ΦEA[8]
2 Σ (V.()-- - v--1(()) (vr( vx=1(
which finishes the proof.
37


Reviews:
[{"review_id": "s0zXddi1KN", "reviewer": "Reviewer_HjBa", "summary": "The paper studies Heavy-Tailed MultiArmed Bandits (HTMAB) problem. The main contribution of the paper is to design an optimal algorithm that achieves both Best of-Both-Worlds (BoBW) and Parameter-free properties for HTMAB, where BoBW means that the algorithm performs optimally in both stochastic and adversarial environments and Parameter-free means that the algorithm do not need to know the the heavy-tail parameters in advance.", "questions": "When $\\alpha, \\sigma$ known, it is trivial to use regular FTRL based algorithm to achieves (nearly) optimal worst-case regret for adversarial bandit problems with potentially heavy-tailed losses (fix the clipping bound $[-r,r]$ with $r=\\sigma T^{1/\\alpha}K^{-1/\\alpha}$ and use Theorem 4 in [6]). When $\\alpha, \\sigma$ are unknown, intuitively, it suffices to use the adaptive clipping bound according to the empirical estimation of $\\alpha, \\sigma$ (Line 6 of ALG 1). Is the high-level idea of the algorithm in this paper the one I described?\n\n\nReferences: \n[1] Putta, Sudeep Raja, and Shipra Agrawal. \"Scale-free adversarial multi armed bandits.\" International Conference on Algorithmic Learning Theory. PMLR, 2022.\n\n[2] Chen, Mingyu, and Xuezhou Zhang. \"Scale-free Adversarial Reinforcement Learning.\" arXiv preprint arXiv:2403.00930 (2024).\n\n[3] Chen, Mingyu, and Xuezhou Zhang. \"Improved Algorithms for Adversarial Bandits with Unbounded Losses.\" arXiv preprint arXiv:2310.01756 (2023).\n\n[4] Huang, Jiatai, Yan Dai, and Longbo Huang. \"Banker online mirror descent: A universal approach for delayed online bandit learning.\" International Conference on Machine Learning. PMLR, 2023.\n\n[5] Hadiji, Hédi, and Gilles Stoltz. \"Adaptation to the range in k-armed bandits.\" Journal of Machine Learning Research 24.13 (2023): 1-33.\n\n[6] Wei, Chen-Yu, and Haipeng Luo. \"More adaptive algorithms for adversarial bandits.\" Conference On Learning Theory. PMLR, 2018.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written. The theoretical results and proof appear to be correct.\n2. The paper achieves worst-case BoBW optimal regret for HTMAB, which improves previous results proposed in [Huang 2022].", "weaknesses": "1. The paper should include the comparisons with previous scale-free MAB works, e.g. [1-5]. Specifically, the algorithm structure proposed in the paper seems very close to the one proposed in [3], which also uses the clipping/skipping technique and inf regularization. The differences should be further clarified.\n2. Assumption 1 is a bit weird. I can understand why it is unavoidable, but I suggest that the authors can give the best (not worst-case optimal) upper bounds we can get without this assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "NNrsv0Bh61", "reviewer": "Reviewer_jQU5", "summary": "The paper addresses the heavy-tailed MAB problem, a variant of the stochastic bandit problem where rewards are sampled from distributions having potentially infinite variance. The main contribution of this work is to provide an algorithm with tight regret guarantees in both the stochastic and adversarial HTMAB problem. While the performance in the stochastic setting is worse (not in terms of T) than existing algorithms (e.g. AdarUCB), the algorithm simultaneously deals with the two settings and is tight in both the instance-dependent and independent sense.", "questions": "- How do applications justify the adversarial HTMAB? Can you please provide some examples?\n\n- I think it would be interesting to highlight the trade-off between ADAR-UCB and UniInf more. How is the best-of-both-worlds property related to the extra factor in the stochastic setting's regret bound? Does your algorithm require extra round-robin turns (as in Adar-UCB)?\n\n- Do you know what the optimal performance would be without the truncated non-negativity assumption? Are there any known lower bounds for the problem without this assumption?\n\n- It would be interesting to understand if alternative (and possibly weaker) assumptions can lead to the same performances (I would like to point out that Theorems 2 and 3 from Genalti et al. don't necessarily imply that this specific assumption is required, but rather that without any assumptions such performances are unattainable).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is written, and it provides an exhaustive review of the existing literature.\n\nThe contribution is clear, and it is well highlighted which open question the paper addresses.\n\nThe paper also presents some nice technical contributions in the algorithm and in the proofs.", "weaknesses": "Overall, the contribution is limited when it comes to applications since adversarial HTMABs are uncommon in the real world and the literature. Instead, in the purely stochastic setting, the algorithm does slightly worse than AdaRUCB by a factor of  $\\log \\frac{\\sigma^\\alpha}{\\Delta_{min}}$ (Genalti et al.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ENA9gBDIDY", "reviewer": "Reviewer_3K75", "summary": "This work establishes the first parameter-free algorithm for heavy-tailed multi-armed bandits (MABs) with best-of-both-worlds (BOBW) properties. This algorithm does not require prior knowledge of heavy-tail parameters $(\\sigma, \\alpha)$ and simultaneously obtains the (nearly) optimal regret in both the stochastic and adversarial environments.", "questions": "1. If $(\\sigma, \\alpha)$ is known a priori, can we eliminate Assumption 1? What are the main technical difficulties when eliminating Assumption 1 in the case of known $(\\sigma, \\alpha)$?\n2. In the previous work [10], the Tsallis entropy regularizer is used while the log-barrier regularizer is used in this work. Is it because the magnitude of the loss estimates in this work is larger than the magnitude of the loss estimates in [10]?\n\n[10] Huang et al. Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed\nBandits. ICML, 22.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Technical innovations**: The proposed algorithm and its analysis incorporate new ingredients including a new skipping and clipping scheme of the loss estimates and a stopping time argument to bound the stability terms and the skipping errors, which seem to be technically valuable and might be of independent interest.\n2. **Writing**: Generally, this work is well written.", "weaknesses": "1. **More comparisons with existing literature**: Most parts of the presentation in this work are clear. However, I would like to suggest the authors provide more discussions and comparisons with the techniques in existing literature. For instance, the exclusion of the optimal arm $i^\\ast$ in Eq. (5) when using the log-barrier regularizer is also achieved by [1,2]. I am not very sure whether there are additional technical nuances between the exclusion of the optimal arm in Eq. (5) of this work and those in [1,2]. For the data-dependent learning rates, several works have also leveraged them to achieve BOBW results in various online learning problems (say, [2,3,4,5,6,7]). Besides, when bounding the stability term of OMD/FTRL, a key property required is to ensure the multiplicative stability of the update of the prediction. In this work, such a property is guaranteed by Lemma 4. However, it seems not appropriate to call such a lemma “novel” as on Line 423, since it has also appeared in previous works when using the log-barrier regularizer (say, Lemma 9 in [8]; Lemma 12 in [9]).\n\n[1] Ito. Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds. COLT, 21.\n\n[2] Ito. Hybrid Regret Bounds for Combinatorial Semi-Bandits and Adversarial Linear Bandits. NeurIPS, 21.\n\n[3] Ito et al. Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs. NeurIPS, 22.\n\n[4] Tsuchiya et al. Best-of-Both-Worlds Algorithms for Partial Monitoring. ALT, 23.\n\n[5] Ito et al. Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds. COLT, 23.\n\n[6] Kong et al. Best-of-three-worlds analysis for linear bandits with follow-the-regularized-leader algorithm. COLT, 23.\n\n[7] Ito et al. Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds. COLT, 24.\n\n[8] Lee et al. A closer look at small-loss bounds for bandits with graph feedback. COLT, 20.\n\n[9] Jin et al. Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition. NeurIPS, 20.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "k7Y94XrI4O", "reviewer": "Reviewer_uA58", "summary": "This paper studies parameter-free best-of-both-worlds (BOBW) for HT-MABs, where 1) HT means that the loss distributions can be unbounded but have $\\\\alpha$-th moment bounded by $\\\\sigma^{\\\\alpha}$, for some $\\\\sigma>0, \\\\alpha\\in(1,2]$; 2) BOBW means that one single algorithm can enjoy logarithmic gap-dependent regret in the stochastic environment (loss distributions are fixed over time) and worst-case optimal regret in adversarial environment (loss distributions change over time), without knowing in advance whether the environment is sto. or not; 3) parameter-free means that the algorithm doesn’t now the value of $\\\\sigma>0, \\\\alpha\\in(1,2]$, but can ensure the regret guarantee as if they were known.\n\nAn algorithm called uniINF is proposed, which ensures $\\\\tilde{O}(\\\\frac{K}{(\\\\Delta_{\\\\text{min}})^{\\\\frac{1}{\\\\alpha-1}}}) $ (expected pseudo-)regret in sto. env. (which is optimal up to log terms and the gap dependency), and near-optimal regret in adv. env. (which is optimal up to log terms) when the loss distributions of the optimal arm satisfy the truncated non-negative assumption (Assumption 1). This is the first parameter-free BOBW result in HTMAB. Previous results approach that in one single env. only (either sto. or adv.).\n\nTechnically, this is achieved by several components, including 1) iterative and adaptive learning rate scheduling; 2) adaptive clipping/skipping; 3) refined analysis for log-barrier regularizer.", "questions": "1. To my understanding, this paper claims to develop a new analysis for $DIV_t$ (also named stability term) when using log-barrier, and introduces an extra $(1-x_{t,i})^2$ factor in the bound, which is the key to get self-bounding property and BOBW. However, I don't quite understand what it means by “$S_t$ is adequately large compared to $||c_t||_{\\infty}$”. I tried to find a formal lemma or theorem statement for this new bound (with exactly the same form) on $DIV_t$ term but I failed. Could the authors help explain this? Under what conditions does this new bound hold?\n\n2. What’s the difficulty to get the refined gap dependency? From the appendix, I feel that in both DIV term and SHIFT term, we cannot achieve that. Could the authors elaborate more on that (from the analysis perspective)? Is it because the regularizer is log-barrier rather than Tsallis entropy?\n\nPost rebuttal ===============================\n\nI'm increasing the score from 6 to 8.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The parameter-free BOBW bound in HTMAB is a quite strong guarantee, and to achieve this, several technical innovations are proposed.", "weaknesses": "I’m not happy with how Assumption 1 is justified. From Line 193 to 195, it says that \"we make the following **essential** assumption. As shown in (Genalti et al., 2024, Theorems 2 & 3), without Assumption 1, there does not exist HTMAB algorithms that can … without knowing either $\\\\alpha$ or $\\\\sigma$.\" However, this statement could be misleading based on my understanding on (Genalti et al., 2024).\n\nThe negative result shown in (Genalti et al., 2024) is that, it’s impossible for one single algorithm to match the lower bound in (Bubeck et al., 2013) for all unknown $\\\\sigma>0$ or $\\\\alpha\\\\in(1,2]$. However, I don’t think it has been characterized that how weak the needed assumption to be \"parameter-free\" in HTMAB. In fact, in the conclusion part of (Genalti et al., 2024), it even says that \"investigating the role of the truncated non-positivity assumption, especially, whether weaker assumptions can be formulated.\"\n\nTherefore, I would urge the authors to refine the statements related to Assumption 1, as currently it may leave the impression that Assumption 1 is a necessary condition for \"parameter-free\", which as of now it’s still unclear yet.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Spotlight)