Parameter-Free Heavy-Tailed Bandits Gianmarco Genalti [email protected] Politecnico di Milano
Alberto Maria Metelli [email protected] Politecnico di Milano July 2026
arXiv:2607.29460v1 [cs.LG] 31 Jul 2026
Abstract Heavy-tailed distributions arise naturally in sequential decision-making problems such as financial investment, online advertising, and network management, where rare but extreme outcomes can dominate performance. Heavy-tailed bandits model online decision-making in these settings by assuming only that rewards X satisfy E[|X|1+ϵ ] ≤ u, for some tail exponent ϵ ∈ (0, 1] and moment bound u < +∞. However, most existing regret minimization algorithms require these parameters to be known. This assumption is particularly restrictive in practice: ϵ and u govern the frequency and magnitude of rare events and are therefore precisely the quantities that are hardest to infer reliably from limited observations. Motivated by an open problem posed by Genalti and Metelli at COLT 2025, we resolve the assumptionfree adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters. We first study adaptation to the moment bound u for a fixed tail exponent ϵ. We prove that every algorithm unaware of u, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees. We then introduce a scheduledexploration algorithm that requires no knowledge of u and matches the resulting adaptation frontier up to logarithmic factors. Finally, we show that the same algorithm can be instanced without knowing ϵ by calibrating its exploration schedule to the endpoint ϵ = 1. It achieves sublinear regret for every fixed ϵ > 0, while no algorithm can guarantee sublinear regret uniformly over all ϵ ∈ (0, 1]. Altogether, our results resolve the COLT open problem without additional distributional assumptions and provide a sharp characterization of the statistical cost of adapting to unknown heavy tails.
1
Introduction
Heavy-tailed rewards arise naturally in sequential decision-making problems such as financial investment (Gagliolo and Schmidhuber, 2011; Genalti et al., 2026), online advertising (Anderson, 2007), and network management (Liebeherr, Burchard, and Ciucu, 2012), where rare but extreme observations may dominate performance. The heavy-tailed stochastic multi-armed bandit model captures these settings by assuming only that the rewards X of every arm satisfy E[|X|1+ϵ ] ≤ u for some ϵ ∈ (0, 1] and u < +∞. The parameter ϵ, named tail exponent, controls the heaviness of the tails, while u, named moment bound, controls their scale. When both parameters are known, robust estimators can be calibrated to attain the distribution-free regret of 1 ϵ 1 e u 1+ϵ O K 1+ϵ T 1+ϵ , (1) where K is the number of arms and T is the horizon (Bubeck, Cesa-Bianchi, and Lugosi, 2013). The knowledge of (ϵ, u) is particularly restrictive in the real-world. Both parameters describe the behavior of rare observations and are therefore difficult to infer reliably from limited data. Moreover, misspecifying ϵ changes the polynomial concentration rate of the estimators (Lugosi and Mendelson, 2019), rather than merely its constants. Prior work showed that the known-parameter guarantees cannot generally be recovered without either paying an additional regret or imposing further distributional assumptions (Genalti et al., 2024). This motivated the open problem of Genalti and Metelli (2025) asking what are the best assumptionfree regret guarantees when the heavy-tail parameters are unknown and which algorithms can attain them.
1
Contributions. In this paper, we first fix the tail exponent ϵ and study adaptation to the unknown moment bound u. Rather than considering only the best distribution-free rate, we characterize how robustness to arbitrary scales u trades off with performance on favorable instances. Let Φf ree (K, T ) denote a moment-free distribution-free regret rate and let Φdep (K, T ) denote the gap-sum-normalized distribution-dependent regret rate.1 We prove that every strategy unaware of u must satisfy (Theorem 4) 1+ϵ 1+ϵ (2) Φdep (K, T )Φf ree (K, T ) ϵ = Ω T ϵ . Thus, improving the distribution-free guarantee necessarily deteriorates the distribution-dependent one. This establishes a frontier that reveals how adaptation trades off distribution-dependent and distribution-free guarantees. We complement this lower bound by proposing an adaptive regret minimization algorithm, Adaptive Robust ETC (AdaR-ETC), which leverages Median-of-Means (Lugosi and Mendelson, 2019) Explore-Then-Commit (Lattimore and Szepesvári, 2020) strategy that does not make use of the knowledge of u. To achieve adaptivity, AdaR-ETC is parametrized by α ∈ [(1 + ϵ)/(1 + 2ϵ), 1), q ∈ [0, ϵ/(1 + 2ϵ)], and βα = (1 − α)(1 + ϵ)/ϵ, and obtains a distribution-free regret bound (Theorem 5), ϵ (1−q) α e K 1+ϵ T (3) Φf ree (K, T ) = O and a distribution-dependent regret bound (Theorem 6), e K q−1 T βα . Φdep (K, T ) = O
(4)
The combination of these guarantees is tight on the joint lower bound frontier of Equation (2). Balancing the horizon dependence and the one on the number of arms gives 1+ϵ 1 ϵ e u 1+ϵ O K 1+2ϵ T 1+2ϵ . (5) This also represents the best possible distribution-free guarantee that can be obtained by any algorithm unaware of u. As visible from the exponent of T , this regret bound is worse compared to the one of Equation (1), establishing the price of adaptivity. Specializing this bound in the finite variance case (ϵ = 1), we obtain √ 2 e e 3 a O(T ) rate, strictly greater than the O( T ) rate attainable in bandits with bounded or subgaussian rewards (Lattimore and Szepesvári, 2020). We then remove the knowledge of ϵ. The Median-of-Means estimator uses neither ϵ nor u; only the exploration schedule makes use of ϵ. Calibrating it to the known endpoint ϵ = 1 yields a single strategy, independent of both parameters, satisfying a distribution-free regret bound 3+ϵ 2ϵ 1 e u 1+ϵ O K 3(1+ϵ) T 3(1+ϵ) (6) for every fixed true ϵ > 0 (Theorem 7). Thus matches the bound of Eq. (5) for ϵ = 1, but deteriorates for all ϵ ∈ (0, 1). Furthermore, we prove a pairwise lower bound (Theorem 8) across moment orders showing that this profile is optimal, up to logarithmic factors, among strategies retaining the balanced finite-variance guarantee at ϵ = 1. Hence, no single policy is optimal at every moment order; adaptation is described by a frontier rather than by one oracle curve. Finally, our pointwise guarantee cannot be made uniform. Although the regret is sublinear for every fixed ϵ > 0, no strategy can guarantee sublinear regret (normalized by u) uniformly over ϵ ∈ (0, 1] (Corollary 9). Indeed, as ϵ approaches zero, the finite-moment assumption becomes arbitrarily weak and the exponent of T approaches one. Altogether, our results characterize the assumption-free cost of u-adaptivity, provide an algorithm attaining the resulting distribution-dependent frontier, and identify the limits of simultaneous (ϵ, u)-adaptation.
2
Heavy-Tailed Bandits
We recall some fundamental notions on heavy-tailed bandits (Bubeck, Cesa-Bianchi, and Lugosi, 2013) and the required notations for regret rates defined in (Hadiji and Stoltz, 2020). 1 These quantities will be formally defined later in the paper.
2
Interaction Protocol. In the stochastic multi-armed bandit problem (Lattimore and Szepesvári, 2020), a learner interacts with K ∈ N≥2 arms for a horizon of T ∈ N rounds. A bandit instance is an ordered tuple ν = (ν1 , . . . , νK ) of probability distributions on R. For every arm i ∈ [K],2 successive pulls produce an i.i.d. i.i.d.
sequence Xi,1 , Xi,2 , . . . ∼ νi , and the reward sequences are independent across arms. At every round t ∈ [T ], the learner selects an arm It ∈ [K] according to a possibly randomized rule π measurable w.r.t. the history up to t − 1. The learner then observes the reward generated by the selected Pt arm XIt ,t . Let Ni (t) = s=1 1{Is = i} be the number of pulls of arm i up to t. Heavy-Tailed Bandits. In this paper, we consider heavy-tailed reward distributions. For ϵ ∈ (0, 1] and u > 0, we denote the set of heavy-tailed bandit instances as: Hϵ,u = (ν1 , . . . , νK ) : EX∼νi |X|1+ϵ ≤ u, ∀i ∈ [K] . The dependence of Hϵ,u on K is kept implicit in the notation. Let µi := EX∼νi [X] be the expected reward of arm i, µ∗ := maxi∈[K] µi be the optimal expected reward, and ∆i := µ∗ − µi be the suboptimality gap of arm i. The expected cumulative regret of a strategy π is given by # " T K X X ∗ π ∆i Eν,π [Ni (T )], (µ − µIt ) = RT (ν) = Eν,π t=1
i=1
where the expectation is taken over both the randomness rewards and the internal randomness of the strategy. When the strategy is clear from the context, we write RT (ν). (ϵ, u)-adaptivity in Heavy-Tailed Bandits. Most of the existing algorithms require, as an input, both u and ϵ (see, e.g., Bubeck, Cesa-Bianchi, and Lugosi (2013); Agrawal, Juneja, and Glynn (2020); Lee and Lim (2022)). These parameters govern the behavior of the tails of the reward distributions and cannot be estimated reliably (Bahadur and Savage, 1956). Since heavy-tailed bandits model complex real-world scenarios beyond the canonical yet limiting distributional assumptions, requiring such knowledge severely limits their scope. A recent research stream (Ashutosh et al., 2021; Genalti et al., 2024; Tamás, Szentpéteri, and Csáji, 2024; Chen et al., 2024) focused on devising (ϵ, u)-adaptive algorithms, i.e., unaware of the values of u and/or ϵ, and on characterizing the statistical limits of learnability without this knowledge. Genalti et al. (2024) show that adaptivity comes at a cost: either that knowledge is substituted by another structural assumption, or the same regret bounds as if u and/or ϵ are known (oracle rates) cannot be achieved. Genalti and Metelli (2025) propose a COLT open problem addressing the following questions: 1. What are the best possible regret rates that can be achieved under adaptivity requirements? 2. What algorithms match such rates? 3. Is there a best assumption that allows for oracle rates? In this paper, we provide a collection of results that, altogether, answer the first two questions.
3
Regret Rates in Heavy-Tailed Bandits
In the stochastic bandit literature, there are two main ways to express regret guarantees: distribution-free bounds and distribution-dependent bounds.3 In this paper, the latter term refers specifically to the gap-sumnormalized coefficient introduced in Definition 3. In distribution-dependent bounds, the guarantee depends on the specific instance through the suboptimality gaps ∆i , whereas distribution-free bounds remove this dependence by considering the worst case over the entire class. We recall the known lower bound which characterizes the minimax regret in heavy-tailed bandits when both u and ϵ are known to the learner. Theorem 1 (Distribution-free regret lower bound, Bubeck, Cesa-Bianchi, and Lugosi (2013)). Fix ϵ ∈ (0, 1]. There exists a constant cϵ > 0, depending only on ϵ, such that, for every u > 0, every K ≥ 2, every horizon 2 Given k ∈ N, we define [k] := {1, 2, . . . , k}.
3 With little approximation, these guarantees are also known in the literature as worst-case and instance-dependent.
3
T ≥ K, and every exploration strategy π, 1
ϵ
1
sup RTπ (ν) ≥ cϵ u 1+ϵ K 1+ϵ T 1+ϵ .
(7)
ν∈Hϵ,u
In this paper, we tackle (ϵ, u)-adaptivity through a two-step approach. First, we characterize the u-adaptive setting, in which ϵ is known. We then remove the knowledge of ϵ and quantify the additional difficulty of simultaneously adapting to both parameters. It is worth noting that the he u-adaptive setting is of interest on its own. Indeed, in non-heavy-tailed MABs, adaptation to an unknown bound on the support of the rewards has been characterized in Hadiji and Stoltz (2020). However, in heavy-tailed bandits the limits of adaptation to an unknown moment bound remain open. Inspired by the definitions of Hadiji and Stoltz (2020) for bounded-support bandits, we now define the two types of regret rates considered in our analysis. Definition 2 (Moment-free distribution-free regret rate). A strategy π for stochastic heavy-tailed bandits admits a moment-free distribution-free regret bound Φf ree if, without knowing u, it guarantees 1
RTπ (ν) ≤ u 1+ϵ Φf ree (K, T ),
(8)
for all K ≥ 2, T ≥ 1, u > 0, and ν ∈ Hϵ,u . Theorem 1 implies that every attainable moment-free distribution-free rate, whenever T ≥ K, satisfies ϵ
1
Φf ree (K, T ) ≥ cstd,ϵ K 1+ϵ T 1+ϵ ,
(9)
for some constant cstd,ϵ > 0 possibly depending on ϵ. Definition 3 (Distribution-dependent regret rate). A strategy π for stochastic heavy-tailed bandits admits a distribution-dependent rate Φdep if, without knowing u, it guarantees X RTπ (ν) lim sup ≤ ∆i , (10) T →+∞ Φdep (K, T ) i:∆i >0
for all K ≥ 2, u > 0, ν ∈ Hϵ,u . The normalization in Definition 3 entails no loss of generality. Indeed, any multiplicative constant in a distribution-dependent upper bound can be absorbed into the definition of Φdep (K, T ). This is necessary to compare rates and to state the adaptation frontier with a constant that depends only on ϵ. The term distribution-dependent rate has a specific meaning in this paper: Φdep (K, T ) is the coefficient multiplying the sum of the suboptimality gaps. It should not be confused with the classical distribution-dependent bounds, which may exhibit a different dependence on the gaps. The functions Φf ree (K, T ) and Φdep (K, T ) explicitly depend on both the horizon T and the number of arms K. Their dependence on ϵ is suppressed because ϵ is fixed throughout the u-adaptive analysis, whereas neither rate is allowed to depend on the unknown value of u. In the following sections, we characterize the trade-off between these two rates and study their optimal dependence on K, T , and ϵ.
4
u-adaptivity: You can’t have it both ways
In this section, we characterize the limits of learnability when the moment bound u is unknown. Our main result establishes a fundamental trade-off between the distribution-free and the distribution-dependent guarantees. These two guarantees cannot be optimized independently: improving one necessarily deteriorates the other. Moreover, the trade-off concerns both the dependence on the horizon T and the dependence on the number of arms K. The following result shows that the two quantities must lie on a frontier. Theorem 4 (Existence of a trade-off). Fix ϵ ∈ (0, 1]. Consider a strategy that does not know u and admits a moment-free distribution-free rate Φf ree (K, T ) = o(T ), for every fixed K ≥ 2. Then, any distribution-
4
Distribution-dependent exponent c
1 5/6 3/4 2/3
ε=1 ε = 0.5 ε = 0.25 0 0
2 3
3 4
5 6
1
Distribution-free exponent d Figure 1: Trade-off between the distribution-dependent and the distribution-free rates in T . dependent rate Φdep (K, T ) satisfying Definition 3 fulfills 1+ϵ
lim inf
Φdep (K, T )Φf ree (K, T ) ϵ 1+ϵ
T →+∞
T ϵ
≥ cϵ ,
∀K ≥ 2,
(11)
where cϵ > 0 depends only on ϵ. The proof follows the change-of-measure procedure developed in (Hadiji and Stoltz, 2020), together with the instance construction of Genalti et al. (2024). Theorem 4 establishes a frontier rather than two independent lower bounds. Intuitively, a learner that aggressively pursues a small distribution-dependent regret explores apparently suboptimal arms only a limited number of times. In the heavy-tailed setting, however, an arm that mostly returns low-reward observations may still hide a rare but extremely large reward. Protecting against these alternatives requires additional exploration. This improves the distribution-free guarantee, but it is unnecessary on favorable instances and deteriorates the distribution-dependent performance. The tension first appears in the dependence on T and, among strategies lying on the optimal horizon frontier, also in the dependence on K. To isolate the exponents, suppose that the two rates admit monomial envelopes of the form Φdep (K, T ) = K a T c and Φf ree (K, T ) = K b T d , up to multiplicative factors that are bounded above and below by constants independent of K and T . Substituting these expressions into Theorem 4 gives 1+ϵ
1+ϵ
1+ϵ
lim inf K a+ ϵ b T c+ ϵ d− ϵ ≥ cϵ .
T →+∞
Consequently, the exponents of T must satisfy c + d(1 + ϵ)/ϵ ≥ (1 + ϵ)/ϵ. This inequality describes the fundamental trade-off in the horizon T . Decreasing the distribution-free exponent d forces the distributiondependent exponent c to increase, and vice versa. In Figure 1, we provide a graphical representation of this trade-off. The dependence on K requires additional care because Theorem 4 takes T to infinity for each fixed K. If the inequality holds strictly, polynomial growth in T may compensate for any fixed dependence on K. Consider instead strategies attaining the horizon boundary c + d(1 + ϵ)/ϵ = (1 + ϵ)/ϵ. For these strategies, the dependence on T cancels in the lower bound. Since cϵ is independent of K, the exponent of K must then satisfy a + b(1 + ϵ)/ϵ ≥ 0. Thus, among strategies lying on the optimal horizon frontier, improving the distribution-free dependence on K necessarily deteriorates the distribution-dependent dependence. Equal-gap interpretation. Consider an equal-gap instance consisting of one optimal arm and K − 1 P suboptimal arms, each with gap ∆ > 0. On this family, i:∆i >0 ∆i = (K − 1)∆. Therefore, if Φdep (K, T ) = K a T c , then RT (ν) ≤ K a T c (K − 1)∆ ≤ K a+1 T c ∆. Thus, the exponent governing the dependence of the actual regret on K is a + 1, rather than a. Rewriting the inequality in terms of the distribution-dependent exponent gives (a + 1) + b(1 + ϵ)/ϵ ≥ 1. This formulation
5
Table 1: Representative points on the K-frontier for ϵ = 1. Operating point
(b, a)
Φf ree (K, T ) Equal-gap RT
Instance-oriented (1/2, −1) K-balanced (1/3, −2/3)
K 1/2 T d K 1/3 T d
O(T c ∆) O(K 1/3 T c ∆)
clarifies that both the distribution-free regret and the actual distribution-dependent regret may deteriorate as K increases. The tension is not that one quantity must decrease while the other increases. Rather, their exponents in K cannot both be made arbitrarily small. On the boundary of the K-frontier, we have a = −b(1 + ϵ)/ϵ, and hence the distribution-dependent exponent is a + 1 = 1 − b(1 + ϵ)/ϵ. Therefore, reducing the distribution-free exponent b necessarily increases the distribution-dependent one a + 1. Representative points for ϵ = 1. At the finite-variance endpoint, the K-frontier becomes a + 2b ≥ 0. Table 1 reports two representative points on its boundary. The first choice yields a distribution-dependent regret that is essentially independent of K on the equal-gap family, but pays a K 1/2 distribution-free factor. Moving to the second point improves the distribution-free dependence from K 1/2 to K 1/3 , while the equal-gap distribution-dependent regret deteriorates from a constant dependence on K to K 1/3 . Balancing both K and T . A natural operating point is obtained by requiring the two guarantees to have the same polynomial dependence on both the horizon and the number of arms. For the horizon, imposing c = d gives c = d ≥ (1+ϵ)/(1+2ϵ). Thus, when the two guarantees are required to have the same dependence on T , neither exponent can be smaller than (1 + ϵ)/(1 + 2ϵ). For the number of arms, the distribution-free exponent is b, whereas the distribution-dependent exponent on the equal-gap family is a + 1. Balancing them amounts ϵ to imposing b = a + 1. Combining this identity with the boundary condition a + b(1 + ϵ)/ϵ = 0 gives b = 1+2ϵ ϵ
1+ϵ
1+ϵ and a = − 1+2ϵ . At the point balancing both K and T , the two rates have form Φf ree (K, T ) = K 1+2ϵ T 1+2ϵ 1+ϵ 1+ϵ 1+ϵ ϵ and Φdep (K, T ) = K − 1+2ϵ T 1+2ϵ . On the equal-gap family, this corresponds to RT (ν) = O K 1+2ϵ T 1+2ϵ ∆ , which has the same dependence on K and T as the distribution-free rate.
For ϵ = 1, the balanced frontier point is Φf ree (K, T ) = K 1/3 T 2/3 and√Φdep (K, T ) = K −2/3 T 2/3 . In particular, the balanced horizon dependence is T 2/3 , which is worse than the T dependence arising in adaptation to an unknown bounded reward range (Hadiji and Stoltz, 2020). This deterioration reflects the additional difficulty of ruling out rare and arbitrarily large rewards, typical of heavy-tailed distributions, when only a finite, unknown moment bound is available.
5
Explore-Then-Commit suffices for u-adaptivity
In this section, we propose an algorithm, fully unaware of u, that achieves regret guarantees that are tight on the frontier defined by Theorem 4. The algorithm allows us to select a point on both the T -frontier and the K-frontier. The dependence on T is controlled by the parameter α, whereas the one on K is controlled by an additional exploration parameter q. Surprisingly, the algorithm is very simple and natural. In fact, an Explore-Then-Commit (ETC) strategy with robust estimation and a tuned amount of exploration LT is enough to get there. We call our algorithm Adaptive Robust ETC (AdaR-ETC, for short), and we report its pseudocode in Algorithm 1. In the next paragraphs, we describe the main components of AdaR-ETC. Robust Estimator. Since the distributions are heavy-tailed, the empirical mean is not a suitable estimator (Bubeck, Cesa-Bianchi, and Lugosi, 2013). We then resort to the well-known Median of Means estimator (MoM, for short). Let Fi = {Xi,1 , . . . , Xi,ni } be the set of ni exploration samples collected from arm i. We divide these samples into BT blocks of equal size si = ⌊ni /BT ⌋. For every b ∈ [BT ], we define the b-th block as Gi,b = Xi,(b−1)si +1 , . . . , Xi,bsi . Thus, each block contains exactly si samples. If ni is not divisible by BT , the remaining ni − BT si samples are discarded.
6
Algorithm 1: Adaptive Robust ETC (AdaR-ETC) Require: Number of arms K, horizon T , exploration parameters α ∈ [(1 + ϵ)/(1 + 2ϵ), 1) and q ∈ [0, ϵ/(1 + 2ϵ)]. (1−α)(1+ϵ) e T ← KBT + K q T βα , LT ← min{T, L e T }, Fi ← ∅ for all i ∈ [K]. 1: Set βα ← , BT ← 8 log(KT 3 ) , L ϵ 2: for t = 1, . . . , LT do 3: Select arm It ← 1 + ((t − 1) mod K). 4: Observe the reward and append it to FIt . 5: end for 6: if LT < T then 7: for i ∈ [K] do oM 8: Compute µ bM (Fi ). i 9: end for oM 10: Select Ib∗ ∈ arg maxi∈[K] µ bM (Fi ). i 11: for t = LT + 1, . . . , T do 12: Select arm It ← Ib∗ . 13: end for 14: end if
Pbsi Xi,ℓ for b ∈ [BT ]. For each block Gi,b , we define the corresponding block average as X i,b = s1i ℓ=(b−1)s i +1 Let X i,(1) ≤ X i,(2) ≤ · · · ≤ X i,(BT ) denote the ordered block averages. The MoM estimator is defined as oM µ bM (Fi ) = X i,(⌈BT /2⌉) . i
Intuitively, although a single block average may be corrupted by an extreme observation, under the finite (1 + ϵ)-moment assumption, a constant fraction of the block averages remains close to the true mean with high probability. Taking their median prevents a small number of atypical blocks from significantly affecting the estimate. 1
ϵ
ϵ
More precisely, if E[|X|1+ϵ ] ≤ u, the estimation error is, with high probability, of order u 1+ϵ BT 1+ϵ ni − 1+ϵ . Thus, we choose BT logarithmic in K and T . Most importantly, while u and ϵ determine the rate appearing in the concentration analysis, the computation of the MoM estimator itself does not require knowledge of u nor ϵ. This estimator enjoys optimal, up to constants, concentration properties around the true mean (Bubeck, Cesa-Bianchi, and Lugosi, 2013). Exploration Budget. The exploration budget of AdaR-ETC is controlled by two parameters. The parameter α determines how the exploration budget scales with the horizon, through βα = (1 − α)(1 + ϵ)/ϵ. A larger α corresponds to a smaller βα and thus to less exploration as T grows. This improves the distributiondependent rate on T , at the cost of a worse distribution-free rate. The parameter q plays the analogous role for the dependence on the number of arms. The polynomial part of the total exploration budget is K q T βα . Since exploration is performed in a round-robin fashion, each arm gets approximately K q−1 T βα samples. Increasing q assigns more exploration samples to each arm as K grows. This improves the distribution-free rate on K, but increases the regret paid on favorable instances. The restrictions on α and q are chosen so that the exploration contribution does not dominate the estimation one. Indeed, α ≥ βα is equivalent to α ≥ (1 + ϵ)/(1 + 2ϵ), whereas q ≤ ϵ/(1 + 2ϵ) is equivalent to q ≤ (1 − q)ϵ/(1 + ϵ). Regret Guarantees. The following results formalize the resulting trade-off and certify the tightness of AdaR-ETC with respect to the frontier of Theorem 4. Theorem 5 (Distribution-free regret of AdaR-ETC). Let ϵ ∈ (0, 1] be fixed and known. Let α ∈ [(1 + ϵ)/(1 + 2ϵ), 1) and q ∈ [0, ϵ/(1 + 2ϵ)]. For every u > 0 and every instance ν ∈ Hϵ,u , AdaR-ETC satisfies 1 ϵ e u 1+ϵ K 1+ϵ (1−q) T α , RTAdaR-ETC (ν) ≤ O e hides polylogarithmic terms in T and constants depending only on ϵ, α, and q. where O 1
The two main contributions to the regret are, up to logarithmic factors, u 1+ϵ K q T βα due to exploration, 1 ϵ and u 1+ϵ K 1+ϵ (1−q) T α due to committing according to the MoM estimates. The restrictions imposed on 7
α and q ensure that ϵthe latter term dominates. Thus, AdaR-ETC is u-adaptive with distribution-free rate e K 1+ϵ (1−q) T α . Φf ree (K, T ) = O On the other hand, we have the following distribution-dependent guarantee. Theorem 6 (Distribution-dependent regret of AdaR-ETC). Let ϵ ∈ (0, 1] be fixed and known. Let α ∈ [(1 + ϵ)/(1 + 2ϵ), 1) and q ∈ [0, ϵ/(1 + 2ϵ)]. For every fixed instance ν ∈ Hϵ,u , AdaR-ETC satisfies X RAdaR-ETC (ν) ∆i . lim sup T q−1 βα ≤ T T →+∞ K i:∆i >0
e K q−1 T βα . Thus, AdaR-ETC is u-adaptive with distribution-dependent rate Φdep (K, T ) = O The two parameters α and q control two distinct, but parallel, trade-offs. The parameter α determines the trade-off in the horizon T : Φf ree (K, T ) ∝ T α and Φdep (K, T ) ∝ T βα . Since α + βα ϵ/(1 + ϵ) = 1, the two exponents lie exactly on theϵ T -frontier. Similarly, the parameter q determines the trade-off in the number of arms K: Φf ree (K, T ) ∝ K 1+ϵ (1−q) and Φdep (K, T ) ∝ K q−1 . These exponents satisfy (1 − q)ϵ/(1 + ϵ) + (q − 1)ϵ/(1 + ϵ) = 0. Thus, at the level of exponents, the choice of q realizes the equality case of the K-trade-off associated with the optimal T -frontier. Hence, for every admissible choice of α and q, AdaR-ETC matches the T -frontier of Theorem 4 up to logarithmic factors. Its explicit dependence on K realizes the corresponding polynomial K-trade-off on the horizonoptimal boundary.
6
Characterizing (ϵ, u)-adaptivity
We now remove the knowledge of ϵ and consider a single strategy that uses neither u nor ϵ. This setting involves two distinct adaptation constraints. The first is the frontier associated with the unknown scale u, characterized in Theorem 4. The second is a new frontier across different moment orders ϵ: improving the regret guarantee on a lighter-tailed class necessarily worsens the guarantee on heavier-tailed classes. (ϵ, u)-adaptive AdaR-ETC. We first construct an order-free version of AdaR-ETC by calibrating both its T dependence and its K-dependence to the finite-variance endpoint ϵ = 1. We then show that, for every fixed ϵ > 0, the resulting distribution-free and distribution-dependent guarantees lie on the unknown-u frontier. Finally, we prove that its distribution-free guarantee is also tight, up to logarithmic factors, among strategies retaining the optimal endpoint guarantee at ϵ = 1. At the finite-variance endpoint ϵ = 1, the choice balancing the dependence on the horizon T is α = 2/3 and βα = 2/3, whereas the choice balancing the distributionfree and the distribution-dependent dependence on the number of arms K is q = 1/3. Thus, we define the e T = KBT + K 1/3 T 2/3 . As order-free version of AdaR-ETC by setting directly BT = 8 log(KT 3 ) and L e T } and the arms are explored in in the previous section, the effective exploration budget is LT = min{T, L round-robin order. The resulting strategy is fully unaware of both u and ϵ. The following theorem characterizes its regret. Theorem 7 (Regret of AdaR-ETC calibrated with ϵ = 1). Let ϵ ∈ (0, 1] and u > 0 be fixed. For every T ≥ K ≥ 2 and every instance ν ∈ Hϵ,u , the order-free version of AdaR-ETC calibrated with ϵ = 1 satisfies 1 3+ϵ 2ϵ e u 1+ϵ RTAdaR-ETC (ν) ≤ O K 3(1+ϵ) T 3(1+ϵ) . (12) e hides factors at most polylogarithmic in K and T and constants depending on ϵ. Moreover, for every where O fixed instance ν ∈ Hϵ,u , X RAdaR-ETC (ν) lim sup T−2/3 2/3 ≤ ∆i . (13) T T →+∞ K i:∆ >0 i
The distribution-free guarantee follows from the same exploration–estimation decomposition of Theorem 5. For every fixed K, the regret is sublinear on every fixed heavy-tailed moment class, even though the algorithm
8
T exponent
1 1 ((ε, u) known) 1+ε 1+ε (u unknown, ε known) 1+2ε
2/3
3+ε ((ε, u) unknown) 3(1+ε)
1/2 0
0.5 ε
1
Figure 2: T exponent as a function of ϵ. does not know the value of ϵ. The distribution-dependent guarantee follows because, on every fixed instance, the probability of committing to a suboptimal arm vanishes sufficiently fast. Asymptotically, the regret is therefore entirely due to round-robin exploration. For every fixed ϵ, Theorem 7 therefore gives the rates ϵ 2 ϵ e K 23 1+ϵ e K −2/3 T 2/3 . Consequently, T 1− 3 1+ϵ and Φdep,ϵ (K, T ) = O Φf ree,ϵ (K, T ) = O ϵ
Φf ree,ϵ (K, T )Φdep,ϵ (K, T ) 1+ϵ ϵ ϵ 2 ϵ 2 ϵ − 32 1+ϵ e K 32 1+ϵ e ). =O T 1− 3 1+ϵ + 3 1+ϵ = O(T
Thus, for every fixed ϵ > 0, the order-free version of AdaR-ETC matches the unknown-u frontier in its polynomial dependence on T . The exponents of K satisfy the corresponding trade-off on the horizon-optimal boundary. Limits of (ϵ, u)-adaptivity. If ϵ were known, the point balancing both the T -dependence and the Kdependence on the u-adaptivity frontier would be obtained by choosing α⋆ (ϵ) = (1 + ϵ)/(1 + 2ϵ) and q ⋆ (ϵ) = ϵ/(1 + 2ϵ). For fixed K, the price of not knowing ϵ is therefore the difference 3+ϵ 1+ϵ ϵ(1 − ϵ) − = ≥ 0. 3(1 + ϵ) 1 + 2ϵ 3(1 + ϵ)(1 + 2ϵ)
(14)
The two exponents coincide at ϵ = 1, whereas the lack of knowledge of ϵ causes a strictly positive loss in the dependence on T for every ϵ ∈ (0, 1) (Figure 1). When the dependence on K is also retained, the two rates are not overall comparable. Indeed, ϵ ϵ(1 − ϵ) 2ϵ − =− . 3(1 + ϵ) 1 + 2ϵ 3(1 + ϵ)(1 + 2ϵ) ≤ 0 Thus, the endpoint-calibrated strategy has a worse dependence on T , but a smaller distribution-free exponent in K. This behavior is a consequence of the K-trade-off characterized in the previous sections. For every ϵ < 1, we have q ⋆ (ϵ) = ϵ/(1 + 2ϵ) < 1/3. The order-free strategy therefore explores more aggressively in K than the strategy designed with knowledge of ϵ. This additional exploration improves the distribution-free dependence on K, but worsens the dependence on K on favorable instances. We now show that this redistribution is unavoidable. Fix an exploration strategy π that uses neither u nor ϵ. For an instance ν, define its intrinsic moment scale at order ϵ as 1 (15) Uϵ (ν) := max EX∼νi |X|1+ϵ 1+ϵ . i∈[K]
The normalized regret profile of π is Φπϵ (K, T ) :=
RTπ (ν) . ν:0<Uϵ (ν)<+∞ Uϵ (ν) sup
(16)
The normalized profile is equivalent to a scale-uniform raw-moment guarantee. More precisely, for every
9
1
B ≥ 0, Φπϵ (K, T ) ≤ B if and only if the same strategy π satisfies supν∈Hϵ,u RTπ (ν) ≤ u 1+ϵ B simultaneously for every u > 0. Indeed, every ν ∈ Hϵ,u satisfies Uϵ (ν) ≤ u1/(1+ϵ) , while the reverse implication follows by setting u = Uϵ (ν)1+ϵ . To simplify the notation, once the strategy π is fixed, we write Φϵ (K, T ) in place of Φπϵ (K, T ). Theorem 8 (Pairwise lower bound for adaptation to an unknown ϵ). There exists a numerical constant c1 > 0 such that, for every fixed strategy whose action rule uses neither the realized moment order nor the moment bound, T ≥ K ≥ 2, and 0 < ϵ ≤ ϵ′ ≤ 1, if Φϵ′ (K, T ) ≤ T /4, then ϵ
ϵ
Φϵ (K, T )Φϵ′ (K, T ) 1+ϵ ≥ c1 T K 1+ϵ .
(17)
Specializing Theorem 8 to ϵ′ = 1 gives a conditional tightness result. More precisely, among strategies retain e K 1/3 T 2/3 , the pairwise frontier forces the dependence on both ing the endpoint guarantee Φ1 (K, T ) ≤ O K and T displayed in Theorem 7. This does not define an unconditional minimax curve over all values of ϵ: a different strategy may deliberately accept a worse guarantee at ϵ = 1 to improve its performance at another e K 1/3 T 2/3 . moment order. Suppose that a strategy satisfies, in the non-saturated regime, Φ1 (K, T ) ≤ O Theorem 8 then gives 2 ϵ 2 ϵ ϵ e 2− 1+ϵ K 3 1+ϵ T 1− 3 1+ϵ , (18) Φϵ (K, T ) ≥ Ω matching the distribution-free upper bound of Theorem 7 in both K and T , up to logarithmic factors. e K 1/3 T 2/3 at ϵ = 1, the distribution-free Therefore, among strategies retaining the endpoint guarantee O rate of the order-free version of AdaR-ETC is frontier-optimal, up to logarithmic factors, in its joint dependence on K and T . The choice q = 1/3 can also be recovered directly from this matching requirement. Suppose that the endpoint 1−q schedule used a generic exponent q. Its endpoint distribution-free rate would have order K 2 T 2/3 . The 1+q ϵ pairwise lower bound would then imply, at moment order ϵ, a K-dependence ofϵ at least K 2 1+ϵ . On the other hand, the corresponding Median of Means upper bound would scale as K 1+ϵ (1−q) . The two exponents coincide if and only if (1−q)ϵ/(1+ϵ) = (1+q)ϵ/(2+2ϵ), which gives q = 1/3. Thus, the K 1/3 T 2/3 exploration schedule is not merely a convenient endpoint choice: it is the unique polynomial schedule in this family that matches the unknown-order frontier in K and T . Finally, pointwise sublinearity cannot be strengthened to a uniform guarantee over all moment orders. Corollary 9 (Impossibility of uniform sublinear adaptation). There exists a numerical constant c2 > 0 such that, for every strategy that uses neither u nor ϵ and every T ≥ K ≥ 2, sup Φϵ (K, T ) ≥ c2 T.
(19)
ϵ∈(0,1]
Hence, no strategy can guarantee sublinear normalized regret uniformly over ϵ ∈ (0, 1] without further assumptions. There is no contradiction between this impossibility result and Theorem 7. The theorem fixes ϵ > 0 and K before letting T grow, whereas the supremum in Corollary 9 may select a different value of ϵ for every horizon. Consistently, limϵ→0 (3 + ϵ)/(3(1 + ϵ)) = 1. Thus, sublinear regret is achievable for every fixed ϵ > 0 and fixed K, but not uniformly over the entire range ϵ ∈ (0, 1]. Why Calibrating to ϵ = 1? The choice of calibrating AdaR-ETC to the finite-variance endpoint ϵ = 1 may appear arbitrary, especially because the same construction can be calibrated to any design order ϵ̄ ∈ (0, 1]. The parameter ϵ̄ should not be interpreted as an estimate of the unknown true order ϵ. Rather, it selects an operating point on the adaptation frontier. Calibrating to ϵ̄ = 1 is a natural choice because it requires no additional information and preserves the optimal guarantee on the finite-variance class. Since every admissible true order satisfies ϵ ≤ 1, this choice always corresponds to an optimistic calibration: unless ϵ = 1, the algorithm overestimates the moment order and explores less than a strategy calibrated to the true class. The resulting deterioration is the price required to retain the finite-variance guarantee. More generally, fix a calibration order ϵ̄ ∈ (0, 1] and define q̄ = ϵ̄/(1 + 2ϵ̄) and β̄ = (1 + ϵ̄)/(1 + 2ϵ̄). The
10
l m e T (ϵ̄) = KBT + K q̄ T β̄ . It depends on ϵ̄, but calibrated version of AdaR-ETC uses the exploration budget L not on ϵ or on u. Theorem 10 (Regret of AdaR-ETC calibrated with ϵ = ϵ). Fix a calibration order ϵ̄ ∈ (0, 1]. Let ϵ ∈ (0, 1] and u > 0 be fixed and unknown. For every T ≥ K ≥ 2 and every instance ν ∈ Hϵ,u , the ϵ̄-calibrated version of AdaR-ETC calibrated with ϵ satisfies ϵ(1+ϵ̄) 1+2ϵ̄+ϵϵ̄ (1+ϵ)(1+2ϵ̄) T (1+ϵ)(1+2ϵ̄) , K ϵ ≤ ϵ̄, 1 e RT (ν) ≤ O u 1+ϵ . 1+ϵ̄ ϵ̄ K 1+2ϵ̄ T 1+2ϵ̄ , ϵ ≥ ϵ̄. Moreover, for every fixed instance ν ∈ Hϵ,u , lim sup T →+∞ K
RT (ν) 1+ϵ̄ − 1+2ϵ̄
T
1+ϵ̄ 1+2ϵ̄
X
≤
∆i .
(20)
i:∆i >0
1+ϵ̄ 1 ϵ̄ e u 1+ϵ̄ At the calibration order ϵ = ϵ̄, the two branches coincide and give O K 1+2ϵ̄ T 1+2ϵ̄ , namely the balanced unknown-u rate associated with ϵ̄.
The two sides of the calibration order have different interpretations. If ϵ̄ < ϵ, the learner underestimates the moment order and therefore explores more than necessary. This choice is conservative: the exploration term dominates, and the regret remains at the rate associated with ϵ̄. If ϵ̄ > ϵ, the learner overestimates the moment order and explores too little for the true heavy-tailed class. The estimation term then dominates, and the regret deteriorates as the true ϵ decreases. The pairwise lower bound in Theorem 8 shows that these two branches cannot be improved, up to logarithmic factors, while preserving the balanced guarantee at ϵ̄. For ϵ < ϵ̄, this follows by applying the lower bound to the pair (ϵ, ϵ̄); for ϵ > ϵ̄, it follows by applying it to (ϵ̄, ϵ). Thus, each calibration selects a frontier-optimal profile across moment classes. In particular, calibrating to ϵ̄ = 1 does not make the strategy simultaneously minimaxoptimal at every ϵ, which is impossible. Instead, it selects the frontier-optimal profile among strategies retaining the balanced finite-variance guarantee.
7
Conclusions and Future Directions
We resolved the assumption-free rate and algorithmic components of the open problem of Genalti and Metelli (2025). We characterized the regret frontier induced by adaptation to the unknown moment bound u, provided an algorithm, Adaptive Robust ETC, matching it up to logarithmic factors, and extended the analysis to the case in which both u and ϵ are unknown. Two natural directions remain open. First, it would be interesting to design an anytime version of our algorithm; a doubling-trick construction should preserve the polynomial rates, at the cost of additional logarithmic factors. Second, completing the third part of the open problem requires identifying the weakest additional assumption under which the oracle rates can be recovered.
11
References Agrawal, S.; Juneja, S.; and Glynn, P. 2020. Optimal δ-Correct Best-Arm Selection for Heavy-Tailed Distributions. In Algorithmic Learning Theory, 61–110. PMLR. Anderson, C. 2007. The long tail: How endless choice is creating unlimited demand. Random House. Ashutosh, K.; Nair, J.; Kagrecha, A.; and Jagannathan, K. 2021. Bandit algorithms: Letting go of logarithmic regret for statistical robustness. In International Conference on Artificial Intelligence and Statistics, 622– 630. PMLR. Bahadur, R. R.; and Savage, L. J. 1956. The nonexistence of certain statistical procedures in nonparametric problems. The Annals of Mathematical Statistics, 27(4): 1115–1122. Bubeck, S.; Cesa-Bianchi, N.; and Lugosi, G. 2013. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11): 7711–7717. Chen, Y.; Huang, J.; Dai, Y.; and Huang, L. 2024. uniINF: Best-of-both-worlds algorithm for parameter-free heavy-tailed MABs. arXiv preprint arXiv:2410.03284. Gagliolo, M.; and Schmidhuber, J. 2011. Algorithm portfolio selection as a bandit problem with unbounded losses. Annals of Mathematics and Artificial Intelligence, 61: 49–86. Genalti, G.; Bhatt, S.; Gatti, N.; and Metelli, A. M. 2026. Catoni-Style Change Point Detection for Regret Minimization in Piecewise-Stationary Heavy-Tailed Bandits. In The 29th International Conference on Artificial Intelligence and Statistics. Genalti, G.; Marsigli, L.; Gatti, N.; and Metelli, A. M. 2024. (ε, u)-Adaptive Regret Minimization in HeavyTailed Bandits. In The Thirty Seventh Annual Conference on Learning Theory, 1882–1915. PMLR. Genalti, G.; and Metelli, A. M. 2025. Open Problem: Regret Minimization in Heavy-Tailed Bandits with Unknown Distributional Parameters. In The Thirty Eighth Annual Conference on Learning Theory, 1–5. PMLR. Hadiji, H.; and Stoltz, G. 2020. arXiv:2006.03378.
Adaptation to the Range in K-Armed Bandits.
arXiv preprint
Lattimore, T.; and Szepesvári, C. 2020. Bandit algorithms. Cambridge University Press. Lee, K.; and Lim, S. 2022. Minimax optimal bandits for heavy tail rewards. IEEE Transactions on Neural Networks and Learning Systems, 35(4): 5280–5294. Liebeherr, J.; Burchard, A.; and Ciucu, F. 2012. Delay bounds in communication networks with heavy-tailed and self-similar traffic. IEEE Transactions on Information Theory, 58(2): 1010–1024. Lugosi, G.; and Mendelson, S. 2019. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5): 1145–1190. Tamás, A.; Szentpéteri, S.; and Csáji, B. C. 2024. Data-driven upper confidence bounds with near-optimal regret for heavy-tailed bandits. arXiv preprint arXiv:2406.05710.
12
A
Proof of the Lower Bound for u-adaptive Heavy-Tailed Bandits
Theorem 4 (Existence of a trade-off). Fix ϵ ∈ (0, 1]. Consider a strategy that does not know u and admits a moment-free distribution-free rate Φf ree (K, T ) = o(T ), for every fixed K ≥ 2. Then, any distributiondependent rate Φdep (K, T ) satisfying Definition 3 fulfills 1+ϵ
lim inf
Φdep (K, T )Φf ree (K, T ) ϵ
≥ cϵ ,
1+ϵ
T →+∞
T ϵ
∀K ≥ 2,
(11)
where cϵ > 0 depends only on ϵ. Proof. Let ϵ , 1+ϵ
ρ :=
p :=
1 1+ϵ = , ρ ϵ
and let Φ := Φf ree (K, T ). Fix K ≥ 2 and ∆ > 0, and consider the deterministic instance ν (0) defined by (0)
ν1
(0)
= δ∆ ,
νi
i ∈ {2, . . . , K}.
= δ0 ,
Arm 1 is the unique optimal arm, while every arm i ≥ 2 has gap ∆i = ∆. Consequently, RT (ν (0) ) = ∆
K X
Eν (0) [Ni (T )],
i=2
where Ni (T ) :=
T X
1{It = i}.
t=1
Since Φf ree (K, T ) = o(T ) for every fixed K, for all sufficiently large T it holds that 2−ρ T. 16
Φ≤ For such values of T , define β :=
16Φ T
p .
The preceding inequality ensures that β ≤ 1/2. For every suboptimal arm i ∈ {2, . . . , K}, consider an alternative instance ν (i) that differs from ν (0) only in the distribution of arm i, which is replaced by (i)
νi
= (1 − β)δ0 + βδ 2∆ . β
The mean of the modified arm is 2∆ = 2∆. β Therefore, arm i is the unique optimal arm under ν (i) . Arm 1 has gap ∆, while every arm j ∈ / {1, i} has gap 2∆. (i)
µi = β
The (1 + ϵ)-moment of the modified arm is EX∼ν (i) |X|1+ϵ = β i
2∆ β
1+ϵ
= (2∆)1+ϵ β −ϵ . Hence, ν (i) belongs to Hϵ,ui with ui := (2∆)1+ϵ β −ϵ ,
13
and 1
ui1+ϵ = 2∆β −ρ . By the moment-free distribution-free guarantee, RT (ν (i) ) ≤ 2∆β −ρ Φ T = 2∆ Φ 16Φ ∆T = , 8 where we used βρ =
16Φ . T
Every pull of an arm different from i incurs regret at least ∆ under ν (i) . It follows that T Eν (i) [T − Ni (T )] ≤ . 8 For ease of notation, let xi := Eν (0) [Ni (T )] and yi := Eν (i) [T − Ni (T )] . Thus, yi ≤
T . 8
Let P0 and Pi denote the distributions of the complete interaction history under ν (0) and ν (i) , respectively. Since the two instances differ only on arm i, the adaptive KL decomposition gives KL(P0 , Pi ) = xi KL δ0 , (1 − β)δ0 + βδ 2∆ β 1 = xi log . 1−β Since β ≤ 1/2, log
1 1−β
≤ 2β,
and therefore KL(P0 , Pi ) ≤ 2βxi . Consider the event Ai :=
Ni (T ) >
T 2
By the definitions of xi and yi , xi ≥
T P0 (Ai ) 2
yi ≥
T Pi (Aci ). 2
and
14
.
The Bretagnolle–Huber inequality then gives T (P0 (Ai ) + Pi (Aci )) 2 T ≥ exp (−KL(P0 , Pi )) 4 T ≥ exp(−2βxi ). 4
xi + y i ≥
Since yi ≤ T /8, we have xi +
T T ≥ exp(−2βxi ). 8 4
We claim that xi ≥
1 1 min T, . 32 β
xi <
1 1 min T, . 32 β
Indeed, suppose by contradiction that
Then xi <
T 32
and
βxi <
1 . 32
Consequently, xi +
T 5T < , 8 32
whereas T 1 T exp(−2βxi ) > exp − 4 4 16 3T 6T > = . 16 32 This is a contradiction. Therefore, p 1 T xi ≥ min T, . 32 16Φ Summing over the K − 1 suboptimal arms yields RT (ν
(0)
p T K −1 ∆ min T, . )≥ 32 16Φ
It remains to remove the minimum. Let cstd,ϵ > 0 be the constant appearing in Theorem 1. Since every valid moment-free distribution-free rate must satisfy the standard minimax lower bound, for all sufficiently large T, 1
Φ ≥ cstd,ϵ K ρ T 1+ϵ . It follows that
T 16Φ
p ≤
T
(16cstd,ϵ )p K T ≤ , 2(16cstd,ϵ )p
where the last inequality uses K ≥ 2. Define κϵ := min {1, 2(16cstd,ϵ )p } .
15
The preceding upper bound implies
min T,
T 16Φ
p
≥ κϵ
T 16Φ
p .
Therefore, RT (ν
(0)
p T ) ≥ cϵ (K − 1)∆ , Φ
where o n 1+ϵ min 1, 2(16cstd,ϵ ) ϵ κϵ = . cϵ := 1+ϵ 32 16p 32 16 ϵ Thus, all constants are now explicitly specified in terms of the constant cstd,ϵ from the standard minimax lower bound. On the baseline instance, X
∆i = (K − 1)∆.
i:∆i >0
By Definition 3, for every η > 0 and all sufficiently large T , RT (ν (0) ) ≤ (1 + η)Φdep (K, T )(K − 1)∆. Combining the upper and lower bounds and cancelling (K − 1)∆ gives cϵ Φdep (K, T )Φf ree (K, T )p ≥ p T 1+η for all sufficiently large T . Taking the inferior limit and then letting η → 0 yields 1+ϵ
lim inf
Φdep (K, T )Φf ree (K, T ) ϵ 1+ϵ
T →+∞
T ϵ
This concludes the proof.
B
≥ cϵ . ■
Proofs of the Regret Upper Bounds of AdaR-ETC in u-adaptive Heavy-Tailed Bandits
We first derive the Median of Means concentration inequality used in both proofs. The argument is standard and follows from the finite-moment analysis underlying robust heavy-tailed estimation (Bubeck, CesaBianchi, and Lugosi, 2013). Lemma 11 (Concentration of the Median of Means estimator). Fix ϵ ∈ (0, 1], and let X1 , . . . , Xn be independent samples with common mean µ satisfying max E[|Xi |1+ϵ ] ≤ u. i∈[n]
Let 1 ≤ B ≤ n, divide the samples into B blocks of size s = ⌊n/B⌋, and let µ bM oM be the Median of Means estimator defined from these blocks. Then, ϵ ! 1+ϵ 1 B B M oM M oM 1+ϵ P µ b − µ > Cϵ u ≤ exp − , n 8 where 3+ϵ
CϵM oM := 21+ 1+ϵ . Proof. Let p = 1 + ϵ. By Jensen’s inequality, |µ|p ≤ E[|X1 |p ] ≤ u.
16
Therefore, E[|X1 − µ|p ] ≤ 2p−1 (E[|X1 |p ] + |µ|p ) ≤ 2p u. Let X b be the average of one block of size s = ⌊n/B⌋. The von Bahr–Esseen inequality gives E |X b − µ|p ≤ 2p+1 u s1−p . By Markov’s inequality, 1 p−1 3 1 P |X b − µ| > 21+ p u p s− p ≤ . 4 Since s ≥ n/(2B), 2
3 1+ p − p−1 p
s
2 2+ p
≤2
p−1 p
B n
= CϵM oM
B n
ϵ 1+ϵ
.
If the Median of Means estimator deviates from µ by more than the displayed radius, at least half of the block averages must be bad. The blocks are independent, and each is bad with probability at most 1/4. Hoeffding’s inequality therefore yields ϵ ! 1+ϵ 1 B B M oM 1+ϵ M oM u b − µ > Cϵ ≤ exp − P µ . n 8 ■ Theorem 5 (Distribution-free regret of AdaR-ETC). Let ϵ ∈ (0, 1] be fixed and known. Let α ∈ [(1 + ϵ)/(1 + 2ϵ), 1) and q ∈ [0, ϵ/(1 + 2ϵ)]. For every u > 0 and every instance ν ∈ Hϵ,u , AdaR-ETC satisfies 1 ϵ e u 1+ϵ RTAdaR-ETC (ν) ≤ O K 1+ϵ (1−q) T α , e hides polylogarithmic terms in T and constants depending only on ϵ, α, and q. where O Proof. Let ρϵ :=
ϵ , 1+ϵ
rq := ρϵ (1 − q),
and recall that βα =
1−α . ρϵ
For ease of notation, define 1
V := u 1+ϵ ,
MT := K q T βα ,
HT := K rq T α .
By Jensen’s inequality, |µi | ≤ V for every arm. Therefore, every suboptimality gap is bounded by ∆i ≤ 2V. The restrictions on q and α imply q ≤ ρϵ (1 − q) = rq and βα ≤ α. Consequently, MT ≤ HT . Moreover, q ≤ ϵ/(1 + 2ϵ) implies rq ≥ ϵ/(1 + 2ϵ), while α ≥ (1 + ϵ)/(1 + 2ϵ). Hence, α ≥ 1 − rq . We now bound the exploration length. If K ≤ T , then K = K rq K 1−rq ≤ K rq T 1−rq ≤ HT ,
17
and therefore LT ≤ KBT + MT + 1 ≤ (BT + 2)HT . e If K > T , then LT ≥ KBT > T , so that LT = T . Since rq + α ≥ 1, we also have LT = T ≤ K rq T α = HT . Thus, in all cases, LT ≤ (BT + 2)HT . If LT = T , the algorithm only explores, and the regret satisfies RT (ν) ≤ 2V LT ≤ 2V (BT + 2)HT . e T , and every arm receives at least We may therefore assume that LT < T . In this case, LT = L LT ni ≥ ≥ BT K samples. Moreover, writing MT = K q T βα and using BT ≥ 1, KBT + ⌈MT ⌉ ni ≥ K ⌈MT ⌉ = BT + K MT ≥ BT + − 1 ≥ K q−1 T βα . K Let ET be the event on which, simultaneously for every i ∈ [K], ρ BT ϵ oM M oM µ bM − µ ≤ C V . i i ϵ ni By Lemma 11 and a union bound, P(ETc ) ≤ K exp
BT − 8
.
Since BT ≥ 8 log(KT 3 ), P(ETc ) ≤
1 . T3
On ET , every estimate has error at most rT := CϵM oM V BTρϵ K rq T −ρϵ βα . Since Ib∗ maximizes the estimated mean, its suboptimality gap satisfies ∆Ib∗ ≤ 2rT . The expected regret can therefore be bounded as RT (ν) ≤ 2V LT + 2rT T + 2V T P(ETc ). Using 1 − ρϵ βα = α, we obtain 2rT T = 2CϵM oM V BTρϵ HT . Combining the previous bounds gives RT (ν) ≤ 2V (BT + 2)HT + 2CϵM oM V BTρϵ HT +
18
2V . T2
Since BT ≥ 1, ρϵ ≤ 1, and HT ≥ 1, it follows that RT (ν) ≤ 2CϵM oM + 8 BT V HT . Recalling the definitions of V and HT , we conclude that 3+ϵ 1 ϵ RT (ν) ≤ 22+ 1+ϵ + 8 BT u 1+ϵ K 1+ϵ (1−q) T α . e guarantee follows. Since BT = ⌈8 log(KT 3 )⌉, the stated O
■
Theorem 6 (Distribution-dependent regret of AdaR-ETC). Let ϵ ∈ (0, 1] be fixed and known. Let α ∈ [(1 + ϵ)/(1 + 2ϵ), 1) and q ∈ [0, ϵ/(1 + 2ϵ)]. For every fixed instance ν ∈ Hϵ,u , AdaR-ETC satisfies X RAdaR-ETC (ν) ∆i . lim sup T q−1 βα ≤ T T →+∞ K i:∆i >0
Proof. Let 1 ϵ , V := u 1+ϵ . 1+ϵ If every arm is optimal, the regret is identically zero and the claim is immediate. We may therefore assume that the instance contains at least one suboptimal arm, and define
ρϵ :=
∆min := min ∆i . i:∆i >0
Since α < 1, we have βα > 0. Moreover, βα ≤
1+ϵ < 1. 1 + 2ϵ
For every fixed K, it follows that KBT + K q T βα = o(T ). eT < T . Thus, for all sufficiently large T , we have LT = L As in the proof of Theorem 5, every arm receives at least ni ≥ K q−1 T βα exploration samples. Define ρ BT K 1−q ϵ . T βα Since K and the instance are fixed, BT is logarithmic in T and βα > 0, so that
rT := CϵM oM V
lim rT = 0.
T →+∞
Consequently, for all sufficiently large T , 2rT < ∆min . Let ET be the event on which all the MoM estimates differ from their respective means by at most rT . Lemma 11 and the choice BT ≥ 8 log(KT 3 ) give 1 P(ETc ) ≤ 3 . T On ET , no suboptimal arm can maximize the estimated mean. Therefore, the arm selected during the commitment phase is optimal. During the round-robin exploration phase, every arm is selected at most LT ≤ BT + K q−1 T βα + 2 K
19
times. Hence, the exploration regret is bounded by BT + K q−1 T βα + 2
X
∆i .
i:∆i >0
The commitment phase incurs no regret on ET . On ETc , its regret is at most 2V T . We thus obtain, for every sufficiently large T , X 2V ∆i + 2 . RT (ν) ≤ BT + K q−1 T βα + 2 T i:∆i >0
Dividing by K
q−1
T
βα
gives RT (ν) ≤ K q−1 T βα
1+
BT + 2 K q−1 T βα
X
∆i +
i:∆i >0
2V . K q−1 T βα +2
For every fixed K, BT + 2
lim
T →+∞ K q−1 T βα
=0
and 2V
lim
T →+∞ K q−1 T βα +2
= 0.
Taking the superior limit proves X RT (ν) ≤ ∆i . q−1 β α T T →+∞ K
lim sup
i:∆i >0
■
C
Proofs for (ϵ, u)-adaptivity
Let the constant from Lemma 11 be 3+ϵ
CϵM oM := 21+ 1+ϵ Theorem 7 (Regret of AdaR-ETC calibrated with ϵ = 1). Let ϵ ∈ (0, 1] and u > 0 be fixed. For every T ≥ K ≥ 2 and every instance ν ∈ Hϵ,u , the order-free version of AdaR-ETC calibrated with ϵ = 1 satisfies 1 3+ϵ 2ϵ e u 1+ϵ RTAdaR-ETC (ν) ≤ O K 3(1+ϵ) T 3(1+ϵ) . (12) e hides factors at most polylogarithmic in K and T and constants depending on ϵ. Moreover, for every where O fixed instance ν ∈ Hϵ,u , X RAdaR-ETC (ν) lim sup T−2/3 2/3 ≤ ∆i . (13) T T →+∞ K i:∆ >0 i
Proof. Let ρϵ :=
ϵ , 1+ϵ
1
V := u 1+ϵ ,
and define 2ρϵ
MT := K 1/3 T 2/3 ,
2ρϵ
HT := K 3 T 1− 3 .
By Jensen’s inequality, |µi | ≤ V for every arm, and hence every suboptimality gap satisfies ∆i ≤ 2V . Since ρϵ ≤ 1/2 and T ≥ K, we have MT = HT
K T
ϵ 1−2ρ 3
20
≤1
and K = HT
K T
1− 2ρ3ϵ ≤ 1.
It follows that LT ≤ KBT + MT + 1 ≤ (BT + 2)HT . If LT = T , the algorithm performs only round-robin exploration, and therefore RT (ν) ≤ 2V LT ≤ 2V (BT + 2)HT . e T , MT = K 1/3 T 2/3 , and the number ni of samples We may thus assume that LT < T . In this case, LT = L collected from each arm satisfies KBT + ⌈MT ⌉ ni ≥ K ⌈MT ⌉ = BT + K MT − 1 ≥ K −2/3 T 2/3 . ≥ BT + K In particular, ni ≥ BT , so that the Median of Means estimator is well defined. Let ET be the event on which, simultaneously for every i ∈ [K], ρ BT ϵ M oM M oM µ bi − µi ≤ Cϵ V . ni By Lemma 11 and a union bound, P(ETc ) ≤ K exp
1 BT ≤ 3. − 8 T
On ET , the estimation error of every arm is at most 2ρϵ
2ρϵ
rT := CϵM oM V BTρϵ K 3 T − 3 . Since Ib∗ maximizes the estimated mean, its gap satisfies ∆Ib∗ ≤ 2rT . The expected regret is therefore bounded by RT (ν) ≤ 2V LT + 2rT T + 2V T P(ETc ). Using the preceding bounds, we obtain 2V RT (ν) ≤ 2V (BT + 2)HT + 2CϵM oM V BTρϵ HT + 2 T ≤ 8 + 2CϵM oM BT V HT , where we used BT ≥ 1, ρϵ ≤ 1, and HT ≥ 1. Recalling the definitions of V and HT , we conclude that 3+ϵ 2ϵ 3+ϵ 1 RT (ν) ≤ 8 + 22+ 1+ϵ BT u 1+ϵ K 3(1+ϵ) T 3(1+ϵ) . This proves the distribution-free guarantee. We now prove the distribution-dependent claim. If every arm is optimal, then the regret is identically zero. Otherwise, define ∆min := min ∆i . i:∆i >0
For every fixed K, KBT + K 1/3 T 2/3 = o(T ),
21
e T < T for all sufficiently large T . and hence LT = L On the event ET , every estimate has error at most rT . Since the instance and K are fixed, lim rT = 0.
T →+∞
Consequently, for all sufficiently large T , 2rT < ∆min , and the arm selected during the commitment phase is optimal. During round-robin exploration, every arm is pulled at most LT ≤ BT + K −2/3 T 2/3 + 2 K times. The exploration regret is thus at most X BT + K −2/3 T 2/3 + 2 ∆i . i:∆i >0
The commitment phase incurs no regret on ET and at most 2V T regret on ETc . Therefore, for all sufficiently large T , X 2V ∆i + 2 . RT (ν) ≤ BT + K −2/3 T 2/3 + 2 T i:∆i >0
Dividing by K −2/3 T 2/3 and taking the superior limit gives X RT (ν) ≤ ∆i , −2/3 T 2/3 T →+∞ K i:∆ >0
lim sup
i
because BT = O(log T ) for every fixed K.
■
Theorem 8 (Pairwise lower bound for adaptation to an unknown ϵ). There exists a numerical constant c1 > 0 such that, for every fixed strategy whose action rule uses neither the realized moment order nor the moment bound, T ≥ K ≥ 2, and 0 < ϵ ≤ ϵ′ ≤ 1, if Φϵ′ (K, T ) ≤ T /4, then ϵ
ϵ
Φϵ (K, T )Φϵ′ (K, T ) 1+ϵ ≥ c1 T K 1+ϵ .
(17)
Proof. Let a :=
ϵ , 1+ϵ
Φ′ := Φϵ′ (K, T ).
We first prove that K −1 . 2 Fix ∆ > 0 and consider the all-zero reference process, in which every arm deterministically returns zero. For a fixed realization of the strategy’s internal randomness, let Φ′ ≥
τj = inf{t ∈ [T ] : It = j}, with τj = +∞ if arm j is never selected, and set σj = (τj − 1) ∧ T. Let m be the number of arms selected at least once, and denote their ordered first-visit times by r1 < r2 < · · · < rm . Since at least ℓ distinct arms must have been visited by round rℓ , we have rℓ ≥ ℓ. Moreover, every unvisited
22
arm contributes T to the sum of the σj . Since T ≥ K, K X
σj ≥
j=1
m X (rℓ − 1) + (K − m)T ℓ=1
m(m − 1) + (K − m)K 2 K(K − 1) ≥ . 2 Taking expectation with respect to the internal randomness of the strategy, there exists an arm j ∈ [K] such that K −1 . E0 [σj ] ≥ 2 ≥
Now consider the deterministic instance in which arm j always returns ∆ and every other arm always returns zero. Until arm j is first selected, the observed history coincides with the all-zero reference process. Therefore, the regret on this instance is at least ∆E0 [σj ]. ′
Its intrinsic moment scale at order ϵ equals ∆, and hence Φ′ ≥
K −1 ∆E0 [σj ] ≥ . ∆ 2
Fix ∆ > 0 and consider the baseline instance ν (0) defined by (0)
ν1
(0)
= δ∆ ,
νi
i ∈ {2, . . . , K}.
= δ0 ,
′
Its intrinsic scale at order ϵ is ∆. Hence, RT (ν (0) ) = ∆
K X
E0 [Ni (T )] ≤ ∆Φ′ .
i=2
It follows that E0 [N1 (T )] ≥ T − Φ′ ≥
3T . 4
Moreover, there exists an arm j ∈ {2, . . . , K} such that E0 [Nj (T )] ≤
Φ′ . K −1
Define K −1 . 128Φ′ The preliminary lower bound on Φ′ ensures that β ≤ 1/64. Construct an alternative instance ν (j) by replacing only arm j with β :=
(j)
νj
= (1 − β)δ0 + βδ 2∆ . β
The mean of the modified arm is 2∆, so arm j is optimal and arm 1 has gap ∆. The intrinsic scale of the alternative instance at order ϵ is 1 1+ϵ ! 1+ϵ 2∆ (j) Uϵ (ν ) = β β ϵ
= 2∆β − 1+ϵ . Consequently, ϵ
RT (ν (j) ) ≤ 2∆β − 1+ϵ Φϵ (K, T ).
23
Let P0 and Pj denote the laws of the complete interaction history under the baseline and alternative instances. By the adaptive KL decomposition, 1 KL(P0 , Pj ) = E0 [Nj (T )] log 1−β ′ Φ 1 ≤ 2β = . K −1 64 Since N1 (T )/T ∈ [0, 1], Pinsker’s inequality gives E0 [N1 (T )] Ej [N1 (T )] ≤ − T T
r
KL(P0 , Pj ) 2 1 1 ≤ √ ≤ . 8 8 2
It follows that 5T . 8 Every pull of arm 1 incurs regret ∆ under the alternative instance, and hence 5∆T . RT (ν (j) ) ≥ 8 Combining the upper and lower bounds on the alternative regret yields 5 Φϵ (K, T ) ≥ T βa. 16 Therefore, a 5 K −1 a Φϵ (K, T )Φϵ′ (K, T ) ≥ T 16 128 5 T (K − 1)a ≥ √ 16 128 5 T Ka ≥ √ 16 256 Ej [N1 (T )] ≥
where the last two inequalities use a ≤ 1/2. The claim follows with 5 5 √ . c1 := √ = 16 256 256 2 ■ Corollary 9 (Impossibility of uniform sublinear adaptation). There exists a numerical constant c2 > 0 such that, for every strategy that uses neither u nor ϵ and every T ≥ K ≥ 2, sup Φϵ (K, T ) ≥ c2 T. ϵ∈(0,1]
Proof. Let c2 :=
5 √ . 16 128
If Φ1 (K, T ) >
T , 4
then sup Φϵ (K, T ) ≥ Φ1 (K, T ) > ϵ∈(0,1]
24
T ≥ c2 T. 4
(19)
Suppose instead that Φ1 (K, T ) ≤ T /4. For every ϵ ∈ (0, 1], Theorem 8 with ϵ′ = 1 gives ϵ
ϵ
Φϵ (K, T ) ≥ c2 T (K − 1) 1+ϵ Φ1 (K, T )− 1+ϵ ϵ 4(K − 1) 1+ϵ ≥ c2 T . T Letting ϵ decrease to zero, the last multiplicative factor converges to one. Therefore, sup Φϵ (K, T ) ≥ c2 T. ϵ∈(0,1]
This proves the claim.
■
Theorem 10 (Regret of AdaR-ETC calibrated with ϵ = ϵ). Fix a calibration order ϵ̄ ∈ (0, 1]. Let ϵ ∈ (0, 1] and u > 0 be fixed and unknown. For every T ≥ K ≥ 2 and every instance ν ∈ Hϵ,u , the ϵ̄-calibrated version of AdaR-ETC calibrated with ϵ satisfies ϵ(1+ϵ̄) 1+2ϵ̄+ϵϵ̄ (1+ϵ)(1+2ϵ̄) T (1+ϵ)(1+2ϵ̄) , K ϵ ≤ ϵ̄, 1 e RT (ν) ≤ O . u 1+ϵ 1+ϵ̄ ϵ̄ K 1+2ϵ̄ T 1+2ϵ̄ , ϵ ≥ ϵ̄. Moreover, for every fixed instance ν ∈ Hϵ,u , lim sup T →+∞ K
RT (ν) 1+ϵ̄ − 1+2ϵ̄
T
1+ϵ̄ 1+2ϵ̄
≤
X
∆i .
(20)
i:∆i >0
Proof. Let 1 ϵ ϵ̄ , ρ̄ := , V := u 1+ϵ . 1+ϵ 1 + ϵ̄ The calibration parameters can equivalently be written as ρ̄ 1 q̄ = , β̄ = . 1 + ρ̄ 1 + ρ̄
ρ :=
In particular, 1 − q̄ = β̄ and q̄ + β̄ = 1. Define MT := K q̄ T β̄ ,
HT := K ρβ̄ T 1−ρβ̄ ,
GT := max{MT , HT }.
Since T ≥ K and q̄ + β̄ = 1, we have MT ≥ K. Therefore, LT ≤ KBT + MT + 1 ≤ (BT + 2)GT . If LT = T , Jensen’s inequality gives |µi | ≤ V and hence ∆i ≤ 2V for every arm. Thus, RT (ν) ≤ 2V LT ≤ 2V (BT + 2)GT . e T (ϵ̄), and every arm receives at least Suppose now that LT < T . In this case, LT = L KBT + ⌈MT ⌉ ni ≥ K MT MT ≥ BT + −1≥ K K exploration samples. Let ET be the event on which all the Median of Means estimates satisfy the concentration bound of Lemma 11. Since BT = ⌈8 log(KT 3 )⌉, a union bound gives 1 BT P(ETc ) ≤ K exp − ≤ 3. 8 T
25
On ET , every estimate has error at most rT := CϵM oM V
BT ni
ρ
≤ CϵM oM V BTρ K ρ(1−q̄) T −ρβ̄ = CϵM oM V BTρ K ρβ̄ T −ρβ̄ . Since the committed arm maximizes the estimated mean, its gap is at most 2rT . Consequently, RT (ν) ≤ 2V LT + 2rT T + 2V T P(ETc ) ≤ 2V (BT + 2)GT + 2CϵM oM V BTρ HT +
2V . T2
Using BT ≥ 1, ρ ≤ 1, and GT ≥ 1, we obtain the explicit bound RT (ν) ≤ 8 + 2CϵM oM BT V GT .
(21)
It remains to identify which term defines GT . We have ρ̄−ρ MT K 1+ρ̄ . = HT T Since T ≥ K, if ϵ ≤ ϵ̄, then ρ ≤ ρ̄ and MT ≤ HT . Equation (21) therefore gives ϵ(1+ϵ̄) ϵ(1+ϵ̄) RT (ν) ≤ 8 + 2CϵM oM BT V K (1+ϵ)(1+2ϵ̄) T 1− (1+ϵ)(1+2ϵ̄) . If instead ϵ ≥ ϵ̄, then ρ ≥ ρ̄ and MT ≥ HT , yielding 1+ϵ̄ ϵ̄ RT (ν) ≤ 8 + 2CϵM oM BT V K 1+2ϵ̄ T 1+2ϵ̄ . This proves the distribution-free guarantee. We finally prove the distribution-dependent guarantee. If every arm is optimal, the claim is immediate. Otherwise, define ∆min := min ∆i . i:∆i >0
For every fixed K and fixed ϵ̄ > 0, KBT + K q̄ T β̄ = o(T ), so LT < T for all sufficiently large T . Moreover, the radius rT converges to zero for every fixed true ϵ > 0. Hence, for all sufficiently large T , 2rT < ∆min and the committed arm is optimal on ET . During round-robin exploration, every arm is selected at most BT + K q̄−1 T β̄ + 2 times. Therefore, X 2V RT (ν) ≤ BT + K q̄−1 T β̄ + 2 ∆i + 2 . T i:∆i >0
Dividing by K
q̄−1
T
β̄
and taking the superior limit gives X RT (ν) ≤ ∆i . q̄−1 β̄ T T →+∞ K i:∆ >0
lim sup
i
Since q̄ − 1 = −(1 + ϵ̄)/(1 + 2ϵ̄), this is exactly Equation (20).
26
■