# Towards Fully Adaptive Regret Minimization in Heavy-Tailed Bandits

Gianmarco Genalti
Politecnico di Milano
<EMAIL_ADDRESS>
&Lupo Marsigli
Politecnico di Milano
<EMAIL_ADDRESS>
&Nicola Gatti
Politecnico di Milano
<EMAIL_ADDRESS>
&Alberto Maria Metelli
Politecnico di Milano
<EMAIL_ADDRESS>

###### Abstract

Heavy-tailed distributions naturally arise in many settings, from finance to
telecommunications. While regret minimization under sub-Gaussian or bounded
support rewards has been widely studied, learning on heavy-tailed
distributions only gained popularity over the last decade. In the stochastic
heavy-tailed bandit problem, an agent learns under the assumption that the
distributions have finite moments of maximum order $1+\epsilon$ which are
uniformly bounded by a constant $u$, for some $\epsilon\in(0,1]$. To the best
of our knowledge, literature only provides algorithms requiring these two
quantities as an input. In this paper we study the stochastic adaptive heavy-
tailed bandit, a variation of the standard setting where both $\epsilon$ and
$u$ are unknown to the agent. We show that adaptivity comes at cost,
introducing two lower bounds on the regret of any adaptive algorithm implying
an higher regret w.r.t. the standard setting. Finally, we introduce a specific
distributional assumption and provide Adaptive Robust UCB, a regret
minimization strategy matching the known lower bound for the heavy-tailed MAB
problem.

##  1 Introduction

In this paper, we investigate the stochastic _multi-armed bandit problem_
(MAB, Auer et al., 2002; Lattimore and Szepesvári, 2020) under the assumption
of _heavy-tailed_ (HT) reward distributions. In the classic stochastic multi-
armed bandit setting Robbins (1952), an agent has access to a set of $K$
possible actions (_i.e._ ,  _arms_). Each arm
$i\in[K]\coloneqq\\{1,\dots,K\\}$ is associated with a reward probability
distribution $\nu_{i}$, having finite mean $\mu_{i}$. At every round
$t\in[T]$, being $T$ a learning horizon, after an action $I_{t}$ is selected,
a reward $X_{t}$ is sampled from $\nu_{I_{t}}$ and revealed to the agent. The
goal of the agent is to minimize its expected regret after $T$ rounds, defined
as

$R_{T}=T\max_{i\in[K]}\mu_{i}-\mathbb{E}\left[\sum_{t=1}^{T}\mu_{I_{t}}\right]=\mathbb{E}\left[\sum_{t=1}^{T}\Delta_{I_{t}}\right],$
(1)

where $\Delta_{i}\coloneqq\max_{j\in[K]}\mu_{j}-\mu_{i}$ is the sub-optimality
gap for all $i\in[K]$ and the expectation is taken w.r.t. the randomness of
the reward and the possible randomness of the algorithm.

Most of the existing works assume that the reward probability distributions
$\nu_{i}$ are sub-Gaussian. Under this assumption, the tails of the
distribution present a strong decay (at least as fast as that of the Gaussian
distribution). An important implication is that every moment of finite order
is finite. While this assumption enables the application of powerful
theoretical tools and, consequently, strong regret guarantees, it is often
limiting in many practical scenarios such as, for example, financial
environments (Gagliolo and Schmidhuber, 2011) or network routing problems
(Liebeherr et al., 2012). In settings, where uncertainty has a significant
impact, heavy-tailed distributions naturally arise. In these cases, the tails
decay slower than a Gaussian, and the moment-generating function is no longer
assumed to be finite. As a consequence, the moments of any finite order might
not exist.

In this work, we investigate the regret minimization problem for MAB with
heavy tails, according to the setting introduced in the seminal work (Bubeck
et al., 2013a). We assume moments of order up to $1+\epsilon$, with
$\epsilon\in(0,1]$ to be finite and uniformly bounded by a constant $u$,
namely

$\mathbb{E}_{X\sim\nu_{i}}[|X|^{1+\epsilon}]\leq u<+\infty,\qquad\forall
i\in[K].$ (2)

In (Bubeck et al., 2013a), the authors show that even if the variance is
finite (_i.e._ , $\epsilon=1$) but the higher order moments are not, the same
guarantees of order $\sum_{i\in[K]:\Delta_{i}>0}\frac{\log T}{\Delta_{i}}$
attained in the classic sub-Gaussian stochastic bandit setting (Auer et al.,
2002) can be achieved in the heavy-tailed bandit problem. However, if
$\epsilon<1$, then the dependency on the suboptimality gaps $\Delta_{i}$
deteriorates and the following upper bound on regret is of order
$\sum_{i\in[K]:\Delta_{i}>0}\frac{\log T}{\Delta_{i}^{1/\epsilon}}$. Finally,
the authors show that the dependency on $\Delta_{i}^{1/\epsilon}$ is
unavoidable, by deriving the corresponding lower bound. From a worst-case
perspective, this translates into a regret bound of order (apart from
logarithmic terms) $K^{\frac{\epsilon}{1+\epsilon}}T^{\frac{1}{1+\epsilon}}$,
which degenerates to linear when $\epsilon\rightarrow 0$.

In the heavy-tailed MAB problem, it is canonical to assume the knowledge of
both $\epsilon$ and $u$ and, to the best of the authors’ knowledge, every
regret minimization strategy in the literature requires them as an algorithm’s
input.111Even if $\epsilon$ and $u$ are not requested for some estimators
(_e.g._ , median of means ), they are necessary for the construction of the
upper confidence bound. The goal of this work is to answer the following
question:

> _Is it possible to provide a novel regret minimization strategy in the
> heavy-tailed bandit problem that does not require any prior knowledge on
> $\epsilon$ nor $u$, but still achieves comparable performances to other
> approaches knowing them?_

In this work, we will show that in general it is not possible to achieve the
same order of performance while being adaptive to the aforementioned unknown
quantities. Fortunately, we will show that under a specific distributional
assumption, the answer is, instead, affirmative. In particular, we will
discuss the role of the truncated non-positivity assumption (Huang et al.,
2022), and show that when this assumption is violated it is not possible
anymore to guarantee the existence of an adaptive algorithm w.r.t. $\epsilon$
nor $u$ achieving state-of-the-art performances. We introduce Adaptive Robust
UCB, an algorithm based on the optimism in the face of uncertainty principle
that is capable of being fully adaptive w.r.t. the two parameters $\epsilon$
and $u$ that characterize the reward distributions. In particular, we propose
a modification of the well-known Robust UCB algorithm from (Bubeck et al.,
2013a), showing that under our assumption we are able to attain the same
theoretical guarantees.

##  2 Setting

We now introduce the stochastic heavy-tailed multi-armed bandit problem.
Formally speaking, there are $K\geq 2$ available actions and a sequence of $T$
rounds. To each arm $i_{t}\in[K]$, we associate a probability distribution
$\nu_{i}$ satisfying (2). At each round $t\in[T]$, the agent can choose an
index $i$ and subsequently collects a reward of $X_{t}$, which is an
independent sample from $\nu_{i}$. The agent is allowed to make a decision at
round $t$ by considering all history up to time $t-1$. We remark that
distributions $\\{\nu_{i}\\}_{i\in[K]}$ only admit finite moments up to order
$1+\epsilon$, with $\epsilon\in(0,1]$, thus distributions with infinite
variance are allowed in this problem formulation. The goal of the agent is to
minimize the regret as defined in (1). In the heavy-tailed bandits literature,
is customary to assume the knowledge on both $\epsilon$ and the upper bound on
the $(1+\epsilon)$-th order moment $u$, which is assumed to be common for all
$\\{\nu_{i}\\}_{i\in[K]}$ without loss of generality. The main contribution of
this paper is twofold: first, we show that in general it is not possible to
achieve the same order of performance of the state-of-the-art approaches while
being unaware of these two quantities; then we propose an algorithm, called
Adaptive Robust UCB, that under a specific distributional assumption called
truncated non-positivty is able to match the order of the regret lower bound
for the classic scenario even when both $\epsilon$ and $u$ are unknown. Thus,
in our setting, we will consider both quantities to be unknown to the agent.
From now on, we will refer to any algorithm operating without this knowledge
as adaptive w.r.t. $\epsilon$ or $u$, depending on which one is unknown
(possibly both).

##  3 Lower Bound on the Regret for Adaptive Heavy-Tailed Bandits

In this section, we state a lower bound on the expected regret that any
adaptive algorithm (w.r.t. to either $u$ or $\epsilon$) can achieve in the
heavy-tailed bandit problem. We start by stating the lower bound on the regret
when $\epsilon$ and $u$ are known.

######  Theorem 1 (Lower Bound on Regret for Stochastic Heavy-Tailed Bandit,
adapted from Bubeck et al. (2013a)).

For any fixed $T$, there exists a set of $K$ distributions satisfying (2) and
such that for any algorithm, one has

$R_{T}\geq
0.01K^{\frac{\epsilon}{1+\epsilon}}u^{\frac{1}{1+\epsilon}}T^{\frac{1}{1+\epsilon}}.$
(3)

This result is independent of the problem instance and show how the dependency
on $T$ deteriorates as $\epsilon\rightarrow 0$. In the particular scenario in
which variance is finite, _i.e._ $\epsilon=1$, the lower bound achieves the
same order as the one for classic stochastic multi-armed bandit problems
(Lattimore and Szepesvári, 2020). The following results show that any
algorithm unaware of $\epsilon$ or $u$, respectively, cannot achieve the same
regret order as the one stated in 1. We start by stating the regret lower
bound for any algorithm adaptive w.r.t. $u$.

######  Theorem 2 (Lower Bound on Regret for Stochastic Adaptive Heavy-Tailed
Bandit, unknown $u$).

For any fixed $T$, there exist two sets of distributions satisfying (2) with
$u$ and $u^{\prime}$ (assume $u^{\prime}>u$ without loss of generality),
respectively, and such that for any algorithm adaptive w.r.t. to the
$1+\epsilon$-th order moment, one has

$\max\left\\{\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{(u^{\prime}T)^{\frac{1}{1+\epsilon}}}\right\\}\geq
C_{1}\left(\frac{u^{\prime}}{u}\right)^{\frac{\epsilon}{(1+\epsilon)^{2}}},$
(4)

where $R(T)$ and $R^{\prime}(T)$ are the regrets achieved by this algorithm in
the two instances, respectively, and $C_{1}$ is a constant independent of $u$
or $u^{\prime}$.

Some remarks are in order. This result states that there exist two particular
heavy-tailed bandit problem instances s.t. no algorithm can match the lower
bound on regret presented in (3) on both, and instead some regret is accrued
in a way that is proportional to the ratio of the two $1+\epsilon$-th order
moments of those instances. In our construction (more details can be found in
Appendix A.1), the gap between $u$ and $u^{\prime}$ can be taken arbitrarily
large, and thus the regret gap with the non-adaptive lower bound presented in
(4) can be arbitrarily large. In particular, this result shows that is not
possible to be adaptive in $u$ without the risk of incurring in an arbitrarily
large regret bound.
Next, we present a similar result concerning adaptivity w.r.t. to the maximum
finite order moment $\epsilon$.

######  Theorem 3 (Lower Bound on Regret for Stochastic Adaptive Heavy-Tailed
Bandit, unknown $\epsilon$).

For any fixed $T$, there exist two sets of distributions satisfying (2) with
$\epsilon$ and $\epsilon^{\prime}$ (assume $\epsilon^{\prime}<\epsilon$
without loss of generality), respectively, and such that for any algorithm
adaptive w.r.t. to the order $\epsilon$ of the maximum order finite moment
$u=1$, one has

$\max\left\\{\frac{R(T)}{T^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{T^{\frac{1}{1+\epsilon^{\prime}}}}\right\\}\geq
C_{2}T^{\frac{\epsilon^{\prime}(\epsilon-\epsilon^{\prime})}{(1+\epsilon)(1+\epsilon^{\prime})^{2}}},$
(5)

where $R(T)$ and $R^{\prime}(T)$ are the regrets achieved by this algorithm in
the two instances, respectively, and $C_{2}$ is a constant independent of
$\epsilon$ or $\epsilon^{\prime}$.

Differently from Theorem 2, where $u$ and $u^{\prime}$ could take arbitrarily
high values on the positive semi-axis of real numbers, the values of
$\epsilon$ and $\epsilon^{\prime}$ are known to belong to the set $(0,1]$ and
thus, for any fixed $T$, the term on the right-hand side of (5) cannot grow
arbitrarily. Modern statistical literature present methods to adapt to any
unknown quantity for which lower and upper bounds are known while controlling
finite-time convergence (Lepskii, 1992), thus, to be adaptive w.r.t. unknown
$\epsilon$ is an easier task than adapting to an unknown $u$. We can observe
that by searching for the maximum value of the right-hand side of (5), we get
that for $\epsilon=1$ and $\epsilon^{\prime}=\frac{1}{3}$ the gap’s order is
$\approx T^{\frac{1}{16}}$.

Any algorithm adaptive w.r.t. either $u$ or $\epsilon$ has a higher regret
lower bound than the one of the non-adaptive problem. We remark that the two
bounds introduced in this section refers to adaptivity w.r.t. only one of the
unknown quantities. It’s unknown if simultaneous adaptivity on both implies an
even higher lower bound, so we leave this as an open question for future
investigations.

##  4 A Fully Adaptive Approach for Heavy-Tailed Bandits

In this section, we finally give an answer to our original research question,
_i.e._ whether there’s an algorithm adaptive w.r.t. both $\epsilon$ and $u$
matching the standard setting’s lower bound stated in (3). We already shown
how adaptivity has a cost, and thus the lower bound presented in (3) is not
achievable by any algorithm unaware of at least one of these quantities.
Luckily, it is possible to restrict the set of adaptive heavy-tailed bandit
problem instances under analysis to a special set, that will be defined in a
short, on which our algorithm, namely Adaptive Robust UCB (shortly AdaR-UCB),
is able to achieve a regret order matching the lower bound for the standard
heavy-tailed bandit problem.

###  4.1 The Truncated Non-Positivity Assumption

We start by stating a key assumption, namely the truncated non-positivity
assumption.

######  Assumption 1 (Truncated Non-Positivity).

Given a set of $K$ distributions satisfying (2), let $\nu_{1}$ be the
distribution of the optimal arm, namely $\mu_{1}\geq\mu_{i}~{}~{}\forall i\geq
1$, then

$\mathbb{E}_{\nu_{1}}[X\mathbbm{1}_{\\{|X|>M\\}}]\leq 0~{}~{}~{}\forall M\geq
0.$ (6)

Some remarks are in order. This assumption requires the optimal arm of a
heavy-tailed bandit instance to have more mass on the negative semi-axis, but
still allows the distribution to have an arbitrary support covering,
potentially, all $\mathbb{R}$. A similar version of this assumption, called
truncated non-negativity, appeared in Huang et al. (2022) in the context of
heavy-tailed bandits: the authors discuss the weak nature of this assumption
comparing it to more stronger assumptions that are common in the literature.
The two lower bounds (4) and (5) have been obtained by introducing two
instances that violate this assumption (see Appendix [A.1,A.2]), and thus the
lower bound on regret for the adaptive heavy-tailed bandit problem under the
truncated non-positivity assumption can be smaller than the ones presented in
the previous section. However, in Appendix A.3, we show that forcing the
truncated non-positivity assumption doesn’t result in an improvement of the
lower bound (3). In the next section, we show that under this assumption it is
possible to be adaptive w.r.t. both $\epsilon$ and $u$ while attaining the
best regret order achievable in the heavy-tailed bandit problem.

###  4.2 A Fully Adaptive Algorithm: Adaptive Robust UCB

We are now ready to introduce Algorithm 1, namely Adaptive Robust UCB
(shortly, AdaR-UCB), an algorithm able to operate in the heavy-tailed bandit
problem without any prior knowledge on $\epsilon$ nor $u$.

1

2Initialize $~{}~{}s_{i}\leftarrow 0$,
$~{}~{}\mathbf{X}_{i}\leftarrow\emptyset$,
$~{}~{}\mathbf{X}_{i}^{\prime}\leftarrow\emptyset$,
$~{}~{}\hat{\mu}_{i,0,1}\leftarrow+\infty~{}~{}~{}\forall i\in[K]$.

3 for  _$t\in[\lfloor\frac{T}{2}\rfloor]$_ do

4 for  _$i\in[K]$_ do

5 Compute threshold $\widehat{M}_{i,s_{i},t}$ solving
$\frac{1}{s_{i}}\sum_{j\in[s]}\frac{\min\\{(X_{i,j}^{\prime})^{2},\widehat{M}_{i,s_{i},t}^{2}\\}}{\widehat{M}_{i,s_{i},t}^{2}}-\frac{25\log(t^{4})}{s_{i}}=0$

6 Compute trimmed observations
$\mathbf{Y_{i}}\leftarrow\\{X_{i,1}\mathbbm{1}_{\\{|X_{i,1}|\leq\widehat{M}_{i,s_{i},t}\\}},\ldots,X_{i,s_{i}}\mathbbm{1}_{\\{|X_{i,s_{i}}|\leq\widehat{M}_{i,s_{i},t}\\}}\\}$

7 Compute trimmed mean estimator
$\widehat{\mu}_{i,s_{i},t}(\mathbf{X}_{i})\leftarrow\frac{1}{s_{i}}\sum_{j\in[s_{i}]}Y_{i,j}$

8

9 end for

10 Select an action
${i}_{t}\in\operatorname*{arg\,max}_{i\in[K]}\widehat{\mu}_{i,s_{i},t}+2\sqrt{\frac{V_{s_{i}}(\mathbf{Y_{i}})\log(t^{4})}{s_{i}}}+19\frac{\widehat{M}_{i,s_{i},t}\log(t^{4})}{s_{i}}$

11 Play action $i_{t}$ and receive an observation $X_{t}$

12 Update samples
$\mathbf{X}_{i_{t}}\leftarrow\mathbf{X}_{i_{t}}\cup\\{X_{t}\\}$

13 Play action $i_{t}$ and receive an observation $X_{t}^{\prime}$

14 Update samples
$\mathbf{X}_{i_{t}}^{\prime}\leftarrow\mathbf{X}_{i_{t}}^{\prime}\cup\\{X_{t}^{\prime}\\}$

15 Update number of pulls $s_{i_{t}}\leftarrow s_{i_{t}}+1$

16

17 end for

Algorithm 1 Adaptive Robust UCB (AdaR-UCB)

AdaR-UCB is an optimism in the face of uncertainty based algorithm, built upon
the Robust UCB strategy from Bubeck et al. (2013a) using a modified version of
the trimmed mean estimator. Trimmed mean is a common estimator in the heavy-
tailed statistics literature, where observations are averaged while cutting-
off values outside of a limited and bounded set of the form $[-M,M]$, thus
being more robust w.r.t. empirical mean to extreme values. More formally, we
define the trimmed mean estimator for the mean of a set of observations
$\mathbf{X}=\\{X_{1},\ldots X_{s}\\}$ as

$\hat{\mu}_{s}(\mathbf{X})=\frac{1}{s}\sum_{j\in[s]}X_{j}\mathbbm{1}_{\\{|X_{j}|\leq
M\\}},$ (7)

where $M>0$ is a given threshold. In the Robust UCB algorithm, the trimmed
mean estimator replaces sample average in a standard optimism in the face of
uncertainty strategy, by selecting at each round $t$ the action $i$ maximising
the sum of the estimator with a proper upper confidence bound. AdaR-UCB
operates in the same way, but while in Robust UCB the threshold choice is
driven by the values of $\epsilon$ and $u$, AdaR-UCB computes a proxy
threshold $\widehat{M}$ for $M$ without resorting to either $\epsilon$ or $u$
(or any estimation of them).

AdaR-UCB operates over $T$ rounds, however in Algorithm 1 we presented an
interaction with the environment lasting only $\lfloor\frac{T}{2}\rfloor$
rounds. Indeed, for each round $t$, AdaR-UCB choose a single arm, but collects
two rewards from it instead of one, that’s the reason two different sets of
collected rewards have been introduced: $\mathbf{X}_{i}$ and
$\mathbf{X}_{i}^{\prime}$ for each arm $i\in[K]$. The reason behind this
choice lies in the fact that threshold $\widehat{M}_{i,s_{i},t}$ and trimmed
mean estimator $\widehat{\mu}_{i,s_{i},t}$ need to be computed from
independent samples of data. This design choice will ensure that the
concentration inequalities built on both $\widehat{M}_{i,s_{i},t}$ and
$\widehat{\mu}_{i,s_{i},t}$ to hold properly (see Appendix A.4 and A.5 for
more details) at the cost of a $2$ factor in the final regret of the
algorithm.

We start by stating the main theoretical result about AdaR-UCB, _i.e._ its
upper bound on regret.

######  Theorem 4 (Upper Bound on Regret for AdaR-UCB).

Given a heavy-tailed bandit problem instance satisfying Assumption 1, the
regret of AdaR-UCB then satisfies:

$R_{T}\leq\sum_{i:\Delta_{i}>0}\left(216\left(\frac{36u}{\Delta_{i}}\right)^{\frac{1}{\varepsilon}}\log{T}+10\Delta_{i}\right).$
(8)

First, we point out that this result provides a positive answer to our initial
research question. The proof of Theorem 4 follows similar steps to the result
provided by Bubeck et al. (2013a) concerning the upper bound on regret for
Robust UCB. To be adaptive w.r.t. both $\epsilon$ and $u$ brings additional
difficulties in constructing the algorithm and proving its theoretical
guarantees (see Appendix A.2 and A.1 for more details). In particular, in the
next paragraphs, we introduce a new form for the concentration inequality of
the trimmed mean estimator, which is explicitly dependent on the threshold
choice but not on $\epsilon$ nor $u$. For this result, we discuss the role of
Assumption 1, and finally provide an adaptive way to compute $\widehat{M}$.

Finally, as customary in the bandit literature, we also provide an instance-
independent version of the upper bound on regret of AdaR-UCB.

######  Theorem 5 (Instance-Independent Upper Bound on Regret for AdaR-UCB).

For any heavy-tailed bandit problem instance satisfying Assumption 1, the
regret of AdaR-UCB then satisfies:

$R_{T}\leq 2T^{\frac{1}{1+\epsilon}}(216K\log
T)^{\frac{\epsilon}{1+\epsilon}}(36u)^{\frac{1}{1+\epsilon}}.$ (9)

###  4.3 Concentration Inequality for Trimmed Mean Estimator

In this section we state a concentration inequality for the trimmed mean
estimator (7), which is explicitly dependent on the threshold value $M$. This
concentration result is a key ingredient to prove the theoretical performances
of our approach.

######  Theorem 6 (Concentration Inequality for Trimmed-Mean Estimator).

Given a set of i.i.d. observations $\mathbf{X}=\\{X_{1},\ldots,X_{s}\\}$, and
given a threshold $M>0$, under Assumption 1 we get that for any given
$\delta>0$:

$\mathbb{P}\left(\mu-\widehat{\mu}_{s}(\mathbf{X})\leq
2\sqrt{\frac{V_{s}(\mathbf{Y})\log(\delta^{-1})}{s}}+19\frac{M\log(\delta^{-1})}{s}\right)\geq
1-\delta,$ (10)

where $\mathbf{Y}=\\{X_{1}\mathbbm{1}_{\\{|X|\leq
M\\}},\ldots,X_{s}\mathbbm{1}_{\\{|X|\leq M\\}}\\}$ is the trimmed version of
$\mathbf{X}$ and $V_{s}(\mathbf{Y})$ is its sample variance.

For the algorithm’s execution we will set $\delta^{-1}=t^{3}$. The result
above can be obtained by decomposing the gap between the true mean and the
estimator in a bias-variance fashion by the means of the trimmed variable
$\mathbf{Y}$ then, noting that under Assumption 1 bias can be neglected, by
bounding the variance of $\mathbf{Y}$ (which is bounded by construction) using
the well-known Empirical Bernstein bound (Maurer and Pontil, 2009). More
details can be found in Appendix A.4. Theorem 6 show that trimmed mean
estimator achieves a sub-Gaussian type concentration rate in function of $M$.
This bound is used at line 10 of Algorithm 1 to compute the upper confidence
bounds over the trimmed mean estimators, this allows AdaR-UCB to choose an
action following the optimism in the face of uncertainty paradigm. Our goal is
now to seek for a proper value of $\widehat{M}$ s.t. this concentration result
is powerful enough for AdaR-UCB to achieve an upper bound on regret matching
the lower bound (3), without requiring the knowledge of $u$ nor $\epsilon$ for
the threshold’s construction.

###  4.4 Computing the Threshold

We now discuss the choice of the threshold $M$, showing that the chosen
threshold $M_{s,t}$ depends on both the number of observations and the round
$t$ and thus being dynamic in time. In particular, following a procedure which
is similar to the one presented in Wang et al. (2021), for each round
$t\in[T]$ we compute the value of $\widehat{M}_{s,t}$ as the solution (in $M$)
of

$f_{s,t}(\mathbf{X};M)=\frac{1}{s}\sum_{j\in[s]}\frac{\min\\{X_{j}^{2},M^{2}\\}}{M^{2}}-\frac{9\log(t^{3})}{s}=0.$
(11)

In line 5 of Algorithm 1 we make use of this procedure to choose the
thresholds for all available actions. Exploiting the fact that the first
addendum is monotonically decreasing after some point, and under the
assumption that
$\sum_{i=1}^{s}\mathbbm{1}_{\left|X_{i}\right|>0}>9\log\left(t^{3}\right)$,
(11) admits a unique positive solution. A reader might notice that we are
solving the sample version of this equation instead of the population version
$\mathbb{E}_{X}[f_{s,t}(\mathbf{X};M)]=0$ (as in Wang et al. (2021)). The
solution $\widetilde{M}_{s,t}$ to the population version of (11) satisfies the
following inequality:

$\widetilde{M}_{s,t}\leq\mathbb{E}_{X}[\min\\{X^{2},\widetilde{M}_{s,t}^{2}\\}]\frac{s}{9\log(t^{3})}\leq\mathbb{E}_{X}[|X|^{1+\epsilon}]\widetilde{M}_{s,t}^{1-\epsilon}\frac{s}{9\log(t^{3})}=u\widetilde{M}_{s,t}^{1-\epsilon}\frac{s}{9\log(t^{3})},$
(12)

and thus, by making explicit $\widetilde{M}_{s,t}$, we obtain the following
bound:

$\widetilde{M}_{s,t}\leq\left(\frac{us}{9\log(t^{3})}\right)^{\frac{1}{1+\epsilon}}.$
(13)

We point out that the upper bound presented above is the value that authors
choose as threshold for the trimmed mean Robust UCB algorithm in Bubeck et al.
(2013a), however this choice of $\widehat{M}_{s,t}$ requires the knowledge of
both $u$ and $\epsilon$, making their estimator unfeasible in the adaptive
heavy-tailed bandit problem. It can be shown (see Appendix A.5) that the
solution of the sample version can be bounded (in high probability) the same
way as in (13), and thus allowing us to perform a proper analysis while
dealing with this source of uncertainty.

##  5 Conclusions

In this paper we studied the adaptive heavy-tailed bandit problem, a variation
on the classical heavy-tailed bandit problem where the no information is
provided to the agent regarding the moments of the distribution, not even
which of them are finite. The first results concern the intrinsic difficulty
of the setting, for which two novel lower bounds have been provided. In
particular, we proved that without any additional assumption no algorithm can
match the performances of the non-adaptive setting. Finally, we provided a
novel algorithm, namely Adaptive Robust UCB, that under a specific
distributional assumption over the optimal arm is able to achieve the state-
of-the-art performances of the standard heavy-tailed bandit problem. Future
directions of investigation regard the role of the truncated non-positivity
assumption: in particular, we wonder if is it possible to find a weaker
assumption ensuring this kind of performances for an algorithm.

## References

  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47:235–256, 2002.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Robbins [1952] Herbert Robbins.  Some aspects of the sequential design of experiments.  1952\.
  * Gagliolo and Schmidhuber [2011] Matteo Gagliolo and Jürgen Schmidhuber.  Algorithm portfolio selection as a bandit problem with unbounded losses.  _Annals of Mathematics and Artificial Intelligence_ , 61:49–86, 2011.
  * Liebeherr et al. [2012] 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.
  * Bubeck et al. [2013a] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi.  Bandits with heavy tail.  _IEEE Transactions on Information Theory_ , 59(11):7711–7717, 2013a.
  * Huang et al. [2022] Jiatai Huang, Yan Dai, and Longbo Huang.  Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits.  In _International Conference on Machine Learning_ , pages 9173–9200. PMLR, 2022.
  * Lepskii [1992] OV Lepskii.  Asymptotically minimax adaptive estimation. i: Upper bounds. optimally adaptive estimates.  _Theory of Probability & Its Applications_, 36(4):682–697, 1992.
  * Maurer and Pontil [2009] Andreas Maurer and Massimiliano Pontil.  Empirical bernstein bounds and sample variance penalization.  _arXiv preprint arXiv:0907.3740_ , 2009.
  * Wang et al. [2021] Lili Wang, Chao Zheng, Wen Zhou, and Wen-Xin Zhou.  A new principle for tuning-free huber regression.  _Statistica Sinica_ , 31(4):2153–2177, 2021.
  * Bubeck et al. [2013b] Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet.  Bounded regret in stochastic multi-armed bandits.  In _Conference on Learning Theory_ , pages 122–134. PMLR, 2013b.
  * Maurer [2006] Andreas Maurer.  Concentration inequalities for functions of independent variables.  _Random Structures & Algorithms_, 29(2):121–138, 2006.

##  Appendix A Proofs of Theoretical Results

In this section, we prove the main theoretical results outlined in the paper.

We start by proving the two novel lower bounds provided for the adaptive
heavy-tailed bandit problem, namely Theorem 2 and Theorem 3.

###  A.1 Proof of Theorem 2

We start by constructing two heavy-tailed bandit instances with a common (and
known to the algorithm) maximum order of moment $\epsilon$, but where
$u^{\prime}>u$.

#### Base Instance

$\begin{cases}&\nu_{1}=\delta_{0},\\\
&\nu_{2}=\Delta^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}\delta_{0}+\left(1-\Delta^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}\right)\delta_{u^{\frac{1}{\epsilon}}\Delta^{-\frac{1}{\epsilon}}},\end{cases}$
(14)

where $\Delta\in(0,u^{\frac{1}{1+\epsilon}})$. Thus, we have $\mu_{1}=0$ and
$\mu_{2}=\Delta$. Furthermore, $\mathbb{E}_{\nu_{1}}[|X|^{1+\epsilon}]=0$ and
$\mathbb{E}_{\nu_{2}}[|X|^{1+\epsilon}]=u$. Therefore, optimal arm is arm $2$.

#### Alternative instance

$\begin{cases}&\nu_{1}^{\prime}=\left(1-(2\Delta)^{1+\frac{1}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}}\right)\delta_{0}+(2\Delta)^{1+\frac{1}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}}\delta_{(u^{\prime})^{\frac{1}{\epsilon}}(2\Delta)^{-\frac{1}{\epsilon}}},\\\
&\nu_{2}^{\prime}=\nu_{2},\end{cases}$ (15)

where $\Delta\in(0,\frac{1}{2}(u^{\prime})^{\frac{1}{1+\epsilon}})$. Thus we
have $\mu_{1}^{\prime}=2\Delta$ and $\mu_{2}^{\prime}=\Delta$. Furthermore,
$\mathbb{E}_{\nu_{1}^{\prime}}[|X|^{1+\epsilon}]=u^{\prime}$ and
$\mathbb{E}_{\nu_{2}^{\prime}}[|X|^{1+\epsilon}]=u$. Therefore, optimal arm is
arm $1$.

Suppose that a matching, adaptive algorithms in $u$ and $u^{\prime}$ exist. In
such a case (see (3)), we will have that the expected regret of the base
instance $R(T)$ is of order $(uT)^{\frac{1}{1+\epsilon}}$, while the regret of
the alternative instance $R^{\prime}(T)$ is of order
$(u^{\prime}T)^{\frac{1}{1+\epsilon}}$. Thus, the following is satisfied for a
constant $c$ that does not depend on $T$:

$\displaystyle\max\left\\{\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{(u^{\prime}T)^{\frac{1}{1+\epsilon}}}\right\\}\leq
c,$

We will prove that this is not the case and, specifically, that for any
algorithm:

$\displaystyle\max\left\\{\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{(u^{\prime}T)^{\frac{1}{1+\epsilon}}}\right\\}\geq
f(T,\epsilon,u,u^{\prime}),$

being $f$ a function increasing in $T$. This suffices to show the inexistence
of an algorithm adaptive in $u$ matching the minimax lower bound (3).

The proof is quite technical and merges the approach of [Bubeck et al., 2013b,
Theorem 5] with that of [Lattimore and Szepesvári, 2020, Chapters 14.2, 14.3].

First, we observe that:

$\displaystyle\max\left\\{\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{(u^{\prime}T)^{\frac{1}{1+\epsilon}}}\right\\}\geq\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}}=\frac{\Delta\mathbb{E}[N_{1}(T)]}{(uT)^{\frac{1}{1+\epsilon}}},$
(16)

where $\mathbb{E}[N_{1}(T)]$ is the expected number of times arm $1$ is pulled
over the horizon $T$.

Second, recalling which are the optimal arms in the two instances and that
$u^{\prime}>u$, we have:

$\displaystyle\max\left\\{\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{(u^{\prime}T)^{\frac{1}{1+\epsilon}}}\right\\}\geq$
(17) $\displaystyle\hskip
56.9055pt\geq(u^{\prime}T)^{-\frac{1}{\epsilon+1}}\max\left\\{\frac{\Delta
T}{2}\mathbb{P}\left(N_{1}(T)\geq T/2\right),\frac{\Delta
T}{2}\mathbb{P}^{\prime}\left(N_{1}(T)<T/2\right)\right\\}$
$\displaystyle\hskip
56.9055pt\geq\frac{\Delta}{4}(u^{\prime})^{-\frac{1}{\epsilon+1}}T^{\frac{\epsilon}{\epsilon+1}}\left(\mathbb{P}\left(N_{1}(T)\geq
T/2\right)+\mathbb{P}^{\prime}\left(N_{1}(T)<T/2\right)\right)$
$\displaystyle\hskip
56.9055pt\geq\frac{\Delta}{8}(u^{\prime})^{-\frac{1}{\epsilon+1}}T^{\frac{\epsilon}{\epsilon+1}}\exp\left(-\mathbb{E}[N_{1}(T)]D_{KL}(\nu_{1}\|\nu_{1}^{\prime})\right).$

where we used Bretagnolle-Huber inequality and divergence decomposition,
together with $\max\\{a,b\\}\geq\frac{1}{2}(a+b)$ for $a,b\geq 0$. Let us now
compute the KL-divergence, noting that $\nu_{1}\ll\nu_{1}^{\prime}$:

$\displaystyle D_{KL}(\nu_{1}\|\nu_{1}^{\prime})$
$\displaystyle=\nu_{1}(0)\log\frac{\nu_{1}(0)}{\nu_{1}^{\prime}(0)}$ (18)
$\displaystyle=\log\frac{1}{1-(2\Delta)^{1+\frac{1}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}}}\leq
c(2\Delta)^{1+\frac{1}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}},$

for
$\Delta\in(0,\left(\frac{1}{2}\right)^{\frac{2\epsilon+1}{1+\epsilon}}(u^{\prime})^{\frac{1}{1+\epsilon}})$
and some $c$ to be calculated (we can take $c=2$).

Putting together Equations (16), (LABEL:eq:proof_lb_u_2) and (18), we have:

$\displaystyle\max\left\\{\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{(u^{\prime}T)^{\frac{1}{1+\epsilon}}}\right\\}\geq$
$\displaystyle\hskip
42.67912pt\geq\max\left\\{\frac{\Delta\mathbb{E}[N_{1}(T)]}{(uT)^{\frac{1}{1+\epsilon}}},\frac{\Delta}{8}(u^{\prime})^{-\frac{1}{\epsilon+1}}T^{\frac{\epsilon}{\epsilon+1}}\exp\left(-c\mathbb{E}[N_{1}(T)](2\Delta)^{1+\frac{1}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}}\right)\right\\}$
$\displaystyle\hskip
42.67912pt\geq\frac{\Delta}{2}\left(\frac{\mathbb{E}[N_{1}(T)]}{(uT)^{\frac{1}{1+\epsilon}}}+\frac{1}{8}(u^{\prime})^{-\frac{1}{\epsilon+1}}T^{\frac{\epsilon}{\epsilon+1}}\exp\left(-c\mathbb{E}[N_{1}(T)](2\Delta)^{\frac{1+\epsilon}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}}\right)\right)$
$\displaystyle\hskip
42.67912pt\geq\frac{\Delta}{2}\min_{x\in[0,T]}\left\\{\frac{x}{(uT)^{\frac{1}{1+\epsilon}}}+\frac{1}{8}(u^{\prime})^{-\frac{1}{\epsilon+1}}T^{\frac{\epsilon}{\epsilon+1}}\exp\left(-cx(2\Delta)^{\frac{1+\epsilon}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}}\right)\right\\}\eqqcolon
g(x)$

The latter is a convex function of $x$ and the minimization can be carried out
in closed form vanishing the derivative choosing $x^{*}$ s.t.

$\frac{1}{(uT)^{\frac{1}{1+\epsilon}}}-\frac{c}{8}(u^{\prime})^{-\left(\frac{1}{\epsilon+1}+\frac{1}{\epsilon}\right)}T^{\frac{\epsilon}{\epsilon+1}}(2\Delta)^{\frac{1+\epsilon}{\epsilon}}\exp\left(-cx^{*}(2\Delta)^{\frac{1+\epsilon}{\epsilon}}(u^{\prime})^{-\frac{1}{\epsilon}}\right)=0,$

with simple calculations, we obtain

$x^{*}=c^{-1}(2\Delta)^{-\frac{1+\epsilon}{\epsilon}}(u^{\prime})^{\frac{1}{\epsilon}}\log\left(\frac{Tu^{\frac{1}{\epsilon+1}}}{8(u^{\prime})^{\frac{1}{\epsilon}+\frac{1}{\epsilon+1}}}c(2\Delta)^{\frac{1+\epsilon}{\epsilon}}\right),$

which leads to:

$\displaystyle g(x^{*})$
$\displaystyle=\frac{\Delta}{2}(uT)^{-\frac{1}{\epsilon+1}}c^{-1}(2\Delta)^{-\frac{1+\epsilon}{\epsilon}}(u^{\prime})^{\frac{1}{\epsilon}}\log\left(\frac{Tu^{\frac{1}{\epsilon+1}}}{8(u^{\prime})^{\frac{1}{\epsilon}+\frac{1}{\epsilon+1}}}c(2\Delta)^{\frac{1+\epsilon}{\epsilon}}\right)+$
$\displaystyle\quad+\frac{\Delta}{2}\frac{1}{8}(u^{\prime})^{-\frac{1}{\epsilon+1}}T^{\frac{\epsilon}{\epsilon+1}}\frac{8(u^{\prime})^{\frac{1}{\epsilon}+\frac{1}{\epsilon+1}}}{Tu^{\frac{1}{\epsilon+1}}}c^{-1}(2\Delta)^{-\frac{1+\epsilon}{\epsilon}}$
$\displaystyle=\frac{\Delta}{2}(uT)^{-\frac{1}{\epsilon+1}}c^{-1}(2\Delta)^{-\frac{1+\epsilon}{\epsilon}}(u^{\prime})^{\frac{1}{\epsilon}}\left[\log\left(\frac{Tu^{\frac{1}{\epsilon+1}}}{8(u^{\prime})^{\frac{1}{\epsilon}+\frac{1}{\epsilon+1}}}c(2\Delta)^{\frac{1+\epsilon}{\epsilon}}\right)+1\right]$
$\displaystyle=\frac{\Delta}{2}(uT)^{-\frac{1}{\epsilon+1}}c^{-1}(2\Delta)^{-\frac{1+\epsilon}{\epsilon}}(u^{\prime})^{\frac{1}{\epsilon}}\log\left(\frac{Tu^{\frac{1}{\epsilon+1}}}{8(u^{\prime})^{\frac{1}{\epsilon}+\frac{1}{\epsilon+1}}}ec(2\Delta)^{\frac{1+\epsilon}{\epsilon}}\right).$

We take $\Delta$ (which is
$<\left(\frac{1}{2}\right)^{\frac{2\epsilon+1}{1+\epsilon}}(u^{\prime})^{\frac{1}{1+\epsilon}}$
for sufficiently large $T$) as:

$\displaystyle\frac{Tu^{\frac{1}{\epsilon+1}}}{8(u^{\prime})^{\frac{1}{\epsilon}+\frac{1}{\epsilon+1}}}c(2\Delta)^{\frac{1+\epsilon}{\epsilon}}=e^{\epsilon},$

resulting in:

$\displaystyle\Delta=2^{\frac{2\epsilon-1}{1+\epsilon}}e^{\frac{\epsilon^{2}}{1+\epsilon}}(cT)^{-\frac{\epsilon}{\epsilon+1}}u^{-\frac{\epsilon}{(\epsilon+1)^{2}}}(u^{\prime})^{\frac{1+2\epsilon}{(\epsilon+1)^{2}}}.$

This imply, after some calculations, that:

$\displaystyle g(x^{*})$
$\displaystyle=c^{-\frac{\epsilon}{\epsilon+1}}2^{-\frac{2\epsilon+5}{\epsilon+1}}(1+\epsilon)e^{-\frac{\epsilon}{\epsilon+1}}u^{-\frac{\epsilon}{(\epsilon+1)^{2}}}(u^{\prime})^{\frac{\epsilon}{(\epsilon+1)^{2}}}\geq
C_{1}\cdot\left(\frac{u^{\prime}}{u}\right)^{\frac{\epsilon}{(\epsilon+1)^{2}}},$

where $C_{1}$ is a value independent of $T$ and both $u$ and $u^{\prime}$.
Finally, we have that

$\displaystyle\max\left\\{\frac{R(T)}{(uT)^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{(u^{\prime}T)^{\frac{1}{1+\epsilon}}}\right\\}\geq
C_{1}\cdot\left(\frac{u^{\prime}}{u}\right)^{\frac{\epsilon}{(\epsilon+1)^{2}}}.$

Since $u^{\prime}>u$ can be taken arbitrarily large, we have that the right-
hand side of this inequality can be arbitrarily large. We conclude the proof
by noting that, when $\epsilon=0$, the gap vanishes: however, this is
irrelevant since for this scenario no sublinear regret can be achieved by any
bandit algorithm.

∎

###  A.2 Proof of Theorem 3

We now prove the lower bound for adaptivity w.r.t. $\epsilon$.

We start by constructing two heavy-tailed bandit instances with different
maximum orders of moment $\epsilon$ and $\epsilon^{\prime}$, where
$0<\epsilon^{\prime}<\epsilon<1$. For the sake of simplicity, but without loss
of generality, we will assume a common (and known to the algorithm) maximum
moment of $u=1$.

#### Base Instance

$\begin{cases}&\nu_{1}=\delta_{0},\\\
&\nu_{2}=(1+\Delta\gamma-\gamma^{1+\epsilon})\delta_{0}+(\gamma^{1+\epsilon}-\Delta\gamma)\delta_{1/\gamma},\end{cases}$
(19)

where $\Delta\in[0,\frac{1}{2}]$ and $\gamma=(2\Delta)^{\frac{1}{\epsilon}}$.
Thus, we have $\mu_{1}=0$ and $\mu_{2}=\Delta$. Furthermore,
$\mathbb{E}_{\nu_{1}}[|x|^{\alpha}]=0$ and
$\mathbb{E}_{\nu_{2}}[|x|^{\alpha}]=2^{\frac{1-\alpha}{\epsilon}}\Delta^{\frac{1+\epsilon-\alpha}{\epsilon}}$,
which are guaranteed to be bounded by constant only if $\alpha\leq\epsilon+1$.
Thus, this instance admits moments finite only up to order $\epsilon+1$.
Therefore, optimal arm is arm $2$.

#### Alternative instance

$\begin{cases}&\nu_{1}^{\prime}=(1-(\gamma^{\prime})^{1+\epsilon^{\prime}})\delta_{0}+(\gamma^{\prime})^{1+\epsilon^{\prime}}\delta_{1/\gamma^{\prime}},\\\
&\nu_{2}^{\prime}=\nu_{2},\end{cases}$ (20)

where $\Delta\in[0,\frac{1}{2}]$ and
$\gamma=(2\Delta)^{\frac{1}{\epsilon^{\prime}}}$. Thus, we have
$\mu_{1}=2\Delta$ and $\mu_{2}=\Delta$. Furthermore,
$\mathbb{E}_{\nu_{1}}[|x|^{\alpha}]=(2\Delta)^{\frac{1+\epsilon^{\prime}-\alpha}{\epsilon^{\prime}}}$
and
$\mathbb{E}_{\nu_{2}}[|x|^{\alpha}]=2^{\frac{1-\alpha}{\epsilon}}\Delta^{\frac{1+\epsilon-\alpha}{\epsilon}}$,
which are guaranteed to be bounded by constant only if
$\alpha\leq\epsilon^{\prime}+1$. Thus, this instance admits moments finite
only up to order $\epsilon^{\prime}+1$. Therefore, optimal arm is arm $1$.

Suppose that a matching, adaptive algorithms in $\epsilon$ and
$\epsilon^{\prime}$ exist. In such a case (see (3)), we will have that the
expected regret of the base instance $R(T)$ is of order
$T^{\frac{1}{1+\epsilon}}$, while the regret of the alternative instance
$R^{\prime}(T)$ is of order $T^{\frac{1}{1+\epsilon^{\prime}}}$. Thus, the
following is satisfied for a constant $c$ that does not depend on $T$:

$\displaystyle\max\left\\{\frac{R(T)}{T^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{T^{\frac{1}{1+\epsilon^{\prime}}}}\right\\}\leq
c,$

We will prove that this is not the case and, specifically, that for any
algorithm:

$\displaystyle\max\left\\{\frac{R(T)}{T^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{T^{\frac{1}{1+\epsilon^{\prime}}}}\right\\}\geq
f(T,\epsilon,\epsilon^{\prime}),$

being $f$ a function increasing in $T$. This suffices to show the non-
existence of an algorithm adaptive in $\epsilon$ matching the minimax lower
bound (3).

The proof is quite technical and emulates the analyses and steps performed to
prove Theorem 2.

First, we observe that:

$\displaystyle\max\left\\{\frac{R(T)}{T^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{T^{\frac{1}{1+\epsilon^{\prime}}}}\right\\}\geq\frac{R(T)}{T^{\frac{1}{1+\epsilon}}}=\frac{\Delta\mathbb{E}[N_{1}(T)]}{T^{\frac{1}{1+\epsilon}}},$
(21)

where $\mathbb{E}[N_{1}(T)]$ is the expected number of times arm $1$ is pulled
over the horizon $T$.

Second, recalling which are the optimal arms in the two instances and that
$\epsilon^{\prime}<\epsilon$, we have:

$\displaystyle\max\left\\{\frac{R(T)}{T^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{T^{\frac{1}{1+\epsilon^{\prime}}}}\right\\}\geq$
(22) $\displaystyle\hskip 42.67912pt\geq
T^{-\frac{1}{\epsilon^{\prime}+1}}\max\left\\{\frac{\Delta
T}{2}\mathbb{P}\left(N_{1}(T)\geq\dfrac{T}{2}\right),\frac{\Delta
T}{2}\mathbb{P}^{\prime}\left(N_{1}(T)<\dfrac{T}{2}\right)\right\\}$
$\displaystyle\hskip
42.67912pt\geq\frac{\Delta}{4}T^{\frac{\epsilon^{\prime}}{\epsilon^{\prime}+1}}\left(\mathbb{P}\left(N_{1}(T)\geq\dfrac{T}{2}\right)+\mathbb{P}^{\prime}\left(N_{1}(T)<\dfrac{T}{2}\right)\right)$
$\displaystyle\hskip
42.67912pt\geq\frac{\Delta}{8}T^{\frac{\epsilon^{\prime}}{\epsilon^{\prime}+1}}\exp\left(-\mathbb{E}[N_{1}(T)]D_{KL}(\nu_{1}\|\nu_{1}^{\prime})\right).$

where we used Bretagnolle-Huber inequality and divergence decomposition,
together with $\max\\{a,b\\}\geq\frac{1}{2}(a+b)$ for $a,b\geq 0$. Let us now
compute the KL-divergence, noting that $\nu_{1}\ll\nu_{1}^{\prime}$:

$\displaystyle D_{KL}(\nu_{1}\|\nu_{1}^{\prime})$
$\displaystyle=\nu_{1}(0)\log\frac{\nu_{1}(0)}{\nu_{1}^{\prime}(0)}$ (23)
$\displaystyle=\log\frac{1}{1-(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}}\leq
c(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}},$

for $\Delta\in[0,1/4]$ and some $c$ to be calculated (we can take $c=2$).

Putting together Equations (21), (LABEL:eq:proof_lb_eps_2) and (23), we have:

$\displaystyle\max\left\\{\frac{R(T)}{T^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{T^{\frac{1}{1+\epsilon^{\prime}}}}\right\\}$
$\displaystyle\geq\max\left\\{\frac{\Delta\mathbb{E}[N_{1}(T)]}{T^{\frac{1}{1+\epsilon}}},\frac{\Delta}{8}T^{\frac{\epsilon^{\prime}}{\epsilon^{\prime}+1}}\exp\left(-c\mathbb{E}[N_{1}(T)](2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right)\right\\}$
$\displaystyle\geq\frac{\Delta}{2}\left(\frac{\mathbb{E}[N_{1}(T)]}{T^{\frac{1}{1+\epsilon}}}+\frac{1}{8}T^{\frac{\epsilon^{\prime}}{\epsilon^{\prime}+1}}\exp\left(-c\mathbb{E}[N_{1}(T)](2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right)\right)$
$\displaystyle\geq\frac{\Delta}{2}\min_{x\in[0,T]}\left\\{\frac{x}{T^{\frac{1}{1+\epsilon}}}+\frac{1}{8}T^{\frac{\epsilon^{\prime}}{\epsilon^{\prime}+1}}\exp\left(-cx(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right)\right\\}\eqqcolon
g(x).$

The latter is a convex function of $x$ and the minimization can be carried out
in closed form vanishing the derivative choosing $x^{*}$ s.t.

$\frac{1}{T^{\frac{1}{1+\epsilon}}}-\frac{c}{8}T^{\frac{\epsilon^{\prime}}{\epsilon^{\prime}+1}}(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\exp\left(-cx^{*}(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right)=0,$

with simple calculations, we obtain

$x^{*}=c^{-1}(2\Delta)^{-\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\log\left(\frac{T^{\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}}{8}c(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right),$

which leads to:

$\displaystyle g(x^{*})$
$\displaystyle=\frac{\Delta}{2}T^{-\frac{1}{\epsilon+1}}c^{-1}(2\Delta)^{-\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\log\left(\frac{T^{\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}}{8}c(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right)+$
$\displaystyle\quad+\frac{\Delta}{2}\frac{1}{8}T^{\frac{\epsilon^{\prime}}{\epsilon^{\prime}+1}}\left[\frac{T^{\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}}{8}c(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right]^{-1}$
$\displaystyle=\frac{\Delta}{2}T^{-\frac{1}{\epsilon+1}}c^{-1}(2\Delta)^{-\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\left[\log\left(\frac{T^{\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}}{8}c(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right)+1\right]$
$\displaystyle=\frac{\Delta}{2}T^{-\frac{1}{\epsilon+1}}c^{-1}(2\Delta)^{-\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\log\left(\frac{T^{\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}}{8}ec(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}\right)$

We take $\Delta$ (which is $<1/4$ for sufficiently large $T$) as

$\displaystyle\frac{T^{\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}}{8}c(2\Delta)^{\frac{1+\epsilon^{\prime}}{\epsilon^{\prime}}}=1,$

resulting in:

$\displaystyle\Delta=2^{\frac{2\epsilon^{\prime}-1}{1+\epsilon^{\prime}}}c^{-\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}T^{-\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}\left(\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}\right)}.$

This imply, after some calculations, that:

$\displaystyle g(x^{*})$
$\displaystyle=2^{\left(\frac{2\epsilon^{\prime}-1}{1+\epsilon^{\prime}}-1-3\right)}c^{\left(-\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}-1+1\right)}T^{\left[-\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}\left(\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}\right)+\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}-\frac{1}{\epsilon+1}\right]}$
$\displaystyle=2^{\frac{-2\epsilon^{\prime}-5}{1+\epsilon^{\prime}}}c^{-\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}T^{-\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}\left(\frac{1}{\epsilon+1}+\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}-1\right)}$
$\displaystyle=2^{\frac{-2\epsilon^{\prime}-5}{1+\epsilon^{\prime}}}c^{-\frac{\epsilon^{\prime}}{1+\epsilon^{\prime}}}T^{\frac{\epsilon^{\prime}(\epsilon-\epsilon^{\prime})}{(1+\epsilon^{\prime})^{2}(1+\epsilon)}}\geq
C_{2}\cdot
T^{\frac{\epsilon^{\prime}(\epsilon-\epsilon^{\prime})}{(1+\epsilon^{\prime})^{2}(1+\epsilon)}}.$

where $C_{2}$ is a value independent on $T$. Finally, we have that:

$\displaystyle\max\left\\{\frac{R(T)}{T^{\frac{1}{1+\epsilon}}},\frac{R^{\prime}(T)}{T^{\frac{1}{1+\epsilon^{\prime}}}}\right\\}\geq
C_{2}\cdot
T^{\frac{\epsilon^{\prime}(\epsilon-\epsilon^{\prime})}{(1+\epsilon^{\prime})^{2}(1+\epsilon)}}.$

We conclude the proof by noting that the dependence on $T$ vanishes when
$\epsilon^{\prime}=0$. This is correct, since even when knowing that
$\epsilon^{\prime}=0$ the regret lower bound is necessarily linear. Thus, we
can just focus on $\epsilon$.

∎

###  A.3 Regret Lower Bound under Assumption 1

One may wonder whether enforcing the truncated non-positive assumption
(Assumption 1) leads to a strictly smaller lower bound on the regret in the
heavy-tailed bandit problem. In this section, we show that this is not the
case.

We employ the same construction as in Lattimore and Szepesvári [2020], but
replace the Gaussian distributions with mixtures of Dirac deltas. We define:

$\displaystyle\nu_{\Delta}=\Delta^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}\delta_{0}+\left(1-\Delta^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}\right)\delta_{-u^{\frac{1}{\epsilon}}\Delta^{-\frac{1}{\epsilon}}},$
(24)

The two instances are constructed by the means of (24).

#### Base Instance $\mu$

$\displaystyle\begin{cases}&\nu_{1}=\nu_{2\Delta},\\\
&\nu_{j}=\nu_{3\Delta},\qquad j\neq 1.\end{cases}$

#### Alternative Instance $\mu^{\prime}$

$\displaystyle\begin{cases}&\nu_{1}^{\prime}=\nu_{2\Delta},\\\
&\nu_{i}^{\prime}=\nu_{\Delta},\\\ &\nu_{j}^{\prime}=\nu_{3\Delta},\qquad
j\neq 1,i,\end{cases}$

where $i\in\text{argmin}_{j\neq 1}\mathbb{E}_{\mu}[N_{j}(T)]$.

Both instances satisfy Assumption 1.

We have:

$\displaystyle R(T)+R^{\prime}(T)\geq\frac{\Delta
T}{2}\left(\mathbb{P}_{\mu}\left(N_{1}\leq\frac{T}{2}\right)+\mathbb{P}_{\mu^{\prime}}\left(N_{1}>\frac{T}{2}\right)\right)$

Using the Bretagnolle-Huber inequality, we get

$\displaystyle R(T)+R^{\prime}(T)\geq\frac{\Delta
T}{2}\text{exp}\left(-\frac{1}{2}D_{KL}(\mu||\mu^{\prime})\right).$

We develop the Kullback-Leibler divergence between the two instances:

$\displaystyle D_{KL}(\mu||\mu^{\prime})$
$\displaystyle=\sum_{j=1}^{k}\mathbb{E}[N_{j}(T)]D_{KL}(\nu_{j}||\nu_{j}^{\prime})$
$\displaystyle=\mathbb{E}[N_{i}(T)]D_{KL}(\nu_{i}||\nu_{i}^{\prime})$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\frac{T}{k-1}D_{KL}(\nu_{i}||\nu_{i}^{\prime})$
$\displaystyle=\frac{T}{k-1}\Bigg{(}(3\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}\log\left(\frac{(3\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}}{(\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}}\right)+$
$\displaystyle\quad\quad+(1-(3\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}})\log\left(\frac{1-(3\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}}{1-(\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}}\right)\Bigg{)}$
$\displaystyle\leq\frac{T}{k-1}(3\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}\log(3^{1+\frac{1}{\epsilon}}),$

where the step marked by (*) follows from the fact that $i$ is the least
pulled arm in instance $\mu$.

Plugging this result, we finally get:

$\displaystyle R(T)+R^{\prime}(T)$ $\displaystyle\geq\frac{\Delta
T}{2}\text{exp}\left(-\frac{1}{2}D_{KL}(\mu||\mu^{\prime})\right)$
$\displaystyle\geq\frac{\Delta
T}{2}\text{exp}\left(-\frac{1}{2}\frac{T}{k-1}(3\Delta)^{1+\frac{1}{\epsilon}}u^{-\frac{1}{\epsilon}}\log(3^{1+\frac{1}{\epsilon}})\right).$

We conclude the proof by noting that $\max\\{x,y\\}>\frac{1}{2}(x+y)$ and
setting
$\Delta=\frac{1}{2}\left(\frac{k-1}{T}u^{\frac{1}{\epsilon}}\frac{1}{\log(3^{1+\frac{1}{\epsilon}})}\right)^{\frac{\epsilon}{1+\epsilon}}$.

Finally, we have:

$\displaystyle\max\\{R(T),R^{\prime}(T)\\}\geq
cu^{\frac{1}{\epsilon}}T^{\frac{1}{1+\epsilon}}$

for some constant $c$ independent of $T$.

This proves that even under Assumption 1 is not possible to further improve
the regret lower bound from Bubeck et al. [2013a].

###  A.4 Proof of Theorem 6

With probability at least $1-\delta$:

$\displaystyle\mu-\widehat{\mu}_{s}(\mathbf{X})$
$\displaystyle=\mathbb{E}[X_{1}]-\frac{1}{s}\sum_{t=1}^{s}X_{t}\mathbbm{1}_{|X_{t}|\leq
M_{s,t}}$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{n}\left(\mathbb{E}[X_{1}]-\mathbb{E}\left[X_{t}\mathbbm{1}_{|X_{t}|\leq
M_{s,t}}\right]\right)+\frac{1}{n}\sum_{t=1}^{n}\left(\mathbb{E}\left[X_{t}\mathbbm{1}_{|X_{t}|\leq
M_{s,t}}\right]-X_{t}\mathbbm{1}_{|X_{t}|\leq M_{s,t}}\right)$
$\displaystyle=\frac{1}{n}\sum_{t=1}^{n}\mathbb{E}[X_{t}\mathbbm{1}_{\left|X_{t}\right|>M_{s,t}}]+\frac{1}{s}\sum_{t=1}^{s}\left(\mathbb{E}\left[X_{t}\mathbbm{1}_{|X_{t}|\leq
M_{s,t}}\right]-X_{t}\mathbbm{1}_{|X_{t}|\leq M_{s,t}}\right)$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\frac{1}{s}\sum_{t=1}^{s}\left(\mathbb{E}\left[X_{t}\mathbbm{1}_{|X_{t}|\leq
M_{s,t}}\right]-X_{t}\mathbbm{1}_{|X_{t}|\leq M_{s,t}}\right)$
$\displaystyle\stackrel{{\scriptstyle(**)}}{{\leq}}\sqrt{\frac{2V_{s}(\mathbf{Y})\log(2\delta^{-1})}{s}}+\frac{14M_{s,t}\log(2\delta^{-1})}{3(s-1)}$
$\displaystyle\leq\sqrt{\frac{4V_{s}(\mathbf{Y})\log(\delta^{-1})}{s}}+\frac{56M_{s,t}\log(\delta^{-1})}{3s}$

Note that in step (*) we used Assumption 1 to make the first term vanish. In
step (**), instead, we used Empirical Bernstein Inequality [Maurer and Pontil,
2009]. We also use the facts that $\log(2\delta^{-1})\leq 2\log(\delta^{-1})$
for $\delta\leq\frac{1}{2}$ and $\frac{1}{s-1}\leq\frac{2}{s}$ in the last
step.

∎

###  A.5 Properties of Empirical Adaptive Threshold $\widehat{M}_{s,t}$

In Wang et al. [2021], the authors provide an upper bound on the solution
$\widetilde{M}_{s,t}$ to the population version of (11)333In (11) we set
$\delta^{-1}=t^{3}$, from now on we will refer to it considering the version
with a generic $\delta^{-1}>2$.:

$\displaystyle\frac{\mathbb{E}[\min\\{X_{1}^{2},M^{2}\\}]}{M^{2}}-\frac{\log(\delta^{-1})}{s}=0.$
(25)

The result is reported in (13): unfortunately this bound is unknown in the
adaptive heavy-tailed bandit problem, since it includes both $\epsilon$ and
$u$. However, neither computing the solution of (25) in feasible, since it
would require the knowledge of an expected value, which is a theoretical
quantity. Furthermore, approximating the expected value with a sample mean
would not have a straightforward effect on the equation’s solution. The goal
of this section is to study the behavior of the solution to the sample version
of (25), namely (11).

In particular, we will provide an high-probability upper bound on its value.
This result is particularly important to prove Theorem 4, since it lets us
provide another concentration inequality (which is dependent on both
$\epsilon$ and $u$, but independent on $\widehat{M}_{s,t}$) on the trimmed
mean estimator.

We start by recalling an important result from Wang et al. [2021].

######  Proposition 7 (Uniqueness of Solution for (11)).

Let $\mathbf{X}=(X_{1},\ldots,X_{s})$ be independent and identically
distributed random variables, and $\delta>0$, if

$0<9\log\left(\delta^{-1}\right)<\sum_{i=1}^{s}\mathbbm{1}_{\left|X_{i}\right|>0},$
(26)

then Equation (11) admits a unique positive solution.

This result is crucial to establish a well-posed computation of the empirical
threshold $\widehat{M}_{s,t}$, since it excludes ambiguities.

However, the most important goal, is to bound $\widehat{M}_{s,t}$ the most
similarly to $\widetilde{M}_{s,t}$. Luckily, the following result states that,
in fact, the solution to (11) can be bounded the same way as the solution to
(25).

######  Theorem 8 (Bounds for $\widehat{M}_{s,t}$).

Let $\mathbf{X}=(X_{1},\ldots,X_{s})$ be independent and identically
distributed random variables satisfying (2), and let $\widehat{M}_{s,t}$ be
the (random) solution of (11), then we have that, with probability at least
$1-\delta$:

$\displaystyle\widehat{M}_{s,t}\leq\left(\dfrac{us}{\log(\delta^{-1})}\right)^{\frac{1}{1+\epsilon}}.$
(27)

and:

$\displaystyle\mathbb{P}\left(|X_{1}|>\widehat{M}_{s,t}\right)\leq\frac{49\log(\delta^{-1})}{s}.$
(28)

###### Proof.

This proof makes use of the concentration inequality for self-normalizing
random variable [Maurer, 2006, Maurer and Pontil, 2009].

Let $\mathbf{X}=(X_{1},\ldots,X_{s})$ be independent and identically
distributed random variables satisfying (2), and $M>0$, we then introduce

$\displaystyle
U_{i,M}\coloneqq\min\left\\{\left(\frac{X_{i}}{M}\right)^{2},1\right\\}$

random variable in $[0,1]$. Furthermore, let

$\displaystyle Z_{M}(\mathbf{X})=\sum_{i=1}^{s}U_{i,M},$

random variable in $[0,s]$ and such that
$U_{i,M}=\frac{1}{s}Z_{M}(\mathbf{X})$ for all $i\in[s]$.

We start by showing that $Z_{M}(\mathbf{X})$ satisfies the assumptions of
Theorem 13 from Maurer [2006], in particular, let $a\geq 1$:

$\displaystyle
Z_{M}(\mathbf{X})-\inf_{y\in\mathbb{R}}Z_{M}(\mathbf{X}_{y,k})\leq
1\quad\forall k\in[s],$ (29)
$\displaystyle\sum_{k=1}^{s}\left(Z_{M}(\mathbf{X})-\inf_{y\in\mathbb{R}}Z_{M}(\mathbf{X}_{y,k})\right)^{2}\leq
aZ_{M}(\mathbf{X}),$ (30)

where $\mathbf{X}_{y,k}$ is obtained by substituting $y$ to the $k$-th element
of $\mathbf{X}$.

Equation (29) follows from

$\displaystyle Z_{M}(\mathbf{X})-\inf_{y\in\mathbb{R}}Z_{M}(\mathbf{X}_{y,k})$
$\displaystyle=U_{k,M}-\inf_{y\in\mathbb{R}}\min\left\\{\left(\frac{y}{M}\right)^{2},1\right\\}=U_{k,M}\leq
1\quad\forall k\in[s].$

Similarly, we set $a=1$ and obtain (30) as follows:

$\displaystyle\sum_{k=1}^{s}\left(Z_{M}(\mathbf{X})-\inf_{y\in\mathbb{R}}Z_{M}(\mathbf{X}_{y,k})\right)^{2}$
$\displaystyle=\sum_{k=1}^{s}\left(U_{k,M}-\inf_{y\in\mathbb{R}}\min\left\\{\left(\frac{y}{M}\right)^{2},1\right\\}\right)^{2}$
$\displaystyle\leq\sum_{k=1}^{s}U_{k,M}^{2}$
$\displaystyle\leq\sum_{k=1}^{s}U_{k,M}$ $\displaystyle=Z_{M}(\mathbf{X}).$

Using Theorem 13 from Maurer [2006] with $a=1$, for the right tail of the
distribution, the following holds:

$\displaystyle\mathbb{P}\left(\mathbb{E}[Z_{M}(\mathbf{X})]-Z_{M}(\mathbf{X})>s\epsilon\right)\leq\exp\left(\dfrac{-\epsilon^{2}s^{2}}{2\mathbb{E}[Z_{M}(\mathbf{X})]}\right)$

which implies

$\displaystyle\mathbb{P}\left(\mathbb{E}[U_{i,M}]-U_{i,M}>\epsilon\right)\leq\exp\left(\dfrac{-\epsilon^{2}s^{2}}{2s\mathbb{E}[U_{i,M}]}\right)=\exp\left(\dfrac{-\epsilon^{2}s}{2\mathbb{E}[U_{i,M}]}\right)\quad\forall
i\in[s].$

By letting $\epsilon\coloneqq
2\sqrt{\dfrac{2\mathbb{E}[U_{i,M}]\log(2\delta^{-1})}{s}}$ for all $i\in[s]$,
we get that

$\displaystyle\mathbb{P}\left(\mathbb{E}[U_{i,M}]-U_{i,M}>\sqrt{\dfrac{2\mathbb{E}[U_{i,M}]\log(2\delta^{-1})}{s}}\right)\leq\frac{\delta}{2}\quad\forall
i\in[s],$

which implies

$\displaystyle\mathbb{P}\left(\sqrt{\mathbb{E}[U_{i,M}]}-\sqrt{U_{i,M}}>2\sqrt{\frac{\log(2\delta^{-1})}{s}}\right)\leq\frac{\delta}{2}\quad\forall
i\in[s].$

A similar inequality holds for the left tail:

$\displaystyle\mathbb{P}\left(Z_{M}(\mathbf{X})-\mathbb{E}[Z_{M}(\mathbf{X})]>s\epsilon\right)\leq\exp\left(\dfrac{-\epsilon^{2}s^{2}}{2\mathbb{E}[Z_{M}(\mathbf{X})]+\epsilon
s}\right),$

with similar steps, we get

$\displaystyle\mathbb{P}\left(\sqrt{U_{i,M}}-\sqrt{\mathbb{E}[U_{i,M}]}>2\sqrt{\frac{\log(\delta^{-1})}{s}}\right)\leq\frac{\delta}{2}\quad\forall
i\in[s].$

Using a union bound over the two inequalities on the left and the right tail,
we finally get

$\displaystyle\mathbb{P}\left(\left|\sqrt{\mathbb{E}[U_{i,M}]}-\sqrt{U_{i,M}}\right|>2\sqrt{\frac{\log(\delta^{-1})}{s}}\right)\leq\delta\quad\forall
i\in[s].$ (31)

Let us now define $\widehat{M}$ random variable such that

$\displaystyle U_{i,\widehat{M}}=\frac{c\log(\delta^{-1})}{s}\quad\forall
i\in[s],$

where $c>0$.

We now plug $U_{i,\widehat{M}}$ in (31) and get that, with probability at
least $1-\delta$, and for all $i\in[K]$,

$\displaystyle\sqrt{\frac{c\log(\delta^{-1})}{s}}$
$\displaystyle=\sqrt{U_{i,\widehat{M}}}$
$\displaystyle\geq\sqrt{\mathbb{E}\left[U_{i,\widehat{M}}\right]}-4\sqrt{\frac{\log(\delta^{-1})}{s}}$
$\displaystyle\geq\sqrt{\mathbb{P}\left(|X_{i}|>\widehat{M}\right)}-4\sqrt{\frac{\log(\delta^{-1})}{s}},$

which implies that, with probability at least $1-\delta$:

$\displaystyle\sqrt{\mathbb{P}\left(|X_{i}|>\widehat{M}\right)}\leq(\sqrt{c}+4)^{2}\sqrt{\frac{\log(\delta^{-1})}{s}}\quad\forall
i\in[s].$

On the other side, plugging $U_{i,\widehat{M}}$ in (31) also yields that for
every $i\in[K]$:

$\displaystyle\sqrt{\frac{c\log(\delta^{-1})}{s}}$
$\displaystyle=\sqrt{U_{i,\widehat{M}}}$
$\displaystyle\leq\sqrt{\mathbb{E}\left[U_{i,\widehat{M}}\right]}+4\sqrt{\frac{\log(\delta^{-1})}{s}}$
$\displaystyle\leq\sqrt{\frac{u}{\widehat{M}^{1+\epsilon}}}+4\sqrt{\frac{\log(\delta^{-1})}{s}},$

which implies

$\displaystyle\widehat{M}\leq\left(\frac{us}{(\sqrt{c}-4)^{2}\log(\delta^{-1})}\right)^{\frac{1}{1+\epsilon}}.$

Choosing $c=9$ concludes the proof. ∎

###  A.6 Threshold-Independent Concentration Inequality for Trimmed Mean
Estimator

In this section we provide another concentration inequality for the trimmed
mean estimator defined in (7). Differently from the concentration inequality
(10), this result is independent on the chosen threshold, but instead have an
explicit dependency on both $\epsilon$ and $u$. This result will play a key
role in the regret analysis of Adaptive Robust UCB.

######  Theorem 9 (Threshold-Independent Concentration Inequality for Trimmed-
Mean Estimator).

Given a set of i.i.d. observations $\mathbf{X}=\\{X_{1},\ldots,X_{s}\\}$
satisfying (2), the following holds:

$\mathbb{P}\left(\widehat{\mu}_{s}(\mathbf{X})-\mu\leq
18u^{\frac{1}{1+\epsilon}}\left[\frac{\log(\delta^{-1})}{s}\right]^{\frac{\epsilon}{1+\epsilon}}\right)\geq
1-\delta.$ (32)

###### Proof.

With probability at least $1-\frac{\delta}{2}$:

$\displaystyle\widehat{\mu}_{s}(\mathbf{X})-\mu$
$\displaystyle=\frac{1}{s}\sum_{i=1}^{s}X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}-\mathbb{E}[X_{1}]$
$\displaystyle=\frac{1}{s}\sum_{i=1}^{s}\left(X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}-\mathbb{E}\left[X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}\right]\right)-\frac{1}{s}\sum_{i=1}^{s}\left(\mathbb{E}[X_{1}]-\mathbb{E}\left[X_{t}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}\right]\right)$
$\displaystyle=\frac{1}{s}\sum_{i=1}^{s}\left(X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}-\mathbb{E}\left[X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}\right]\right)-\frac{1}{s}\sum_{i=1}^{s}\mathbb{E}[X_{i}\mathbbm{1}_{\left|X_{i}\right|>M_{s,t}}]$
$\displaystyle\leq\frac{1}{s}\sum_{i=1}^{s}\left(X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}-\mathbb{E}\left[X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}\right]\right)+\frac{1}{s}\sum_{i=1}^{s}\mathbb{E}[|X_{i}|\mathbbm{1}_{\left|X_{i}\right|>M_{s,t}}]$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\frac{1}{s}\sum_{i=1}^{s}\left(X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}-\mathbb{E}\left[X_{i}\mathbbm{1}_{|X_{i}|\leq
M_{s,t}}\right]\right)+$
$\displaystyle\quad\quad+\frac{1}{s}\sum_{i=1}^{s}\left(\mathbb{E}\left[|X_{i}|^{1+\epsilon}\right]^{\frac{1}{1+\epsilon}}\right)\left(\mathbb{E}\left[(\mathbbm{1}_{|X_{i}|>M_{s,t}})^{\frac{1+\epsilon}{\epsilon}}\right]^{\frac{\epsilon}{1+\epsilon}}\right)$
$\displaystyle\stackrel{{\scriptstyle(**)}}{{\leq}}\sqrt{\frac{2M_{s,t}^{1-\epsilon}u\log\left(2\delta^{-1}\right)}{s}}+\frac{M_{s,t}\log\left(2\delta^{-1}\right)}{3s}+\frac{1}{s}\sum_{i=1}^{s}\left(u^{\frac{1}{1+\varepsilon}}\right)\left(\mathbb{E}\left[\mathbbm{1}_{\left|X_{i}\right|>M_{s,t}}\right]^{\frac{\epsilon}{1+\varepsilon}}\right)$
$\displaystyle\leq\sqrt{\frac{2M_{s,t}^{1-\epsilon}u\log\left(2\delta^{-1}\right)}{s}}+\frac{M_{s,t}\log\left(2\delta^{-1}\right)}{3s}+u^{\frac{1}{1+\varepsilon}}\left(\frac{1}{s}\sum_{i=1}^{s}\mathbb{P}\left(|X_{i}|>M_{s,t}\right)^{\frac{\epsilon}{1+\varepsilon}}\right).$

Step (*) follows from Hölder inequality, while step (**) is a consequence of
Bernstein Inequality for bounded random variables.

To proceed further, we make use of Theorem 8 with a confidence level of
$\frac{\delta}{2}$.

In particular, with probability at least $1-\delta$ (by union bound):

$\displaystyle\widehat{\mu}_{s}(\mathbf{X})-\mu$
$\displaystyle\leq\sqrt{\frac{2M_{s}^{1-\epsilon}u\log\left(2\delta^{-1}\right)}{s}}+\frac{M_{s,t}\log\left(2\delta^{-1}\right)}{3s}+$
$\displaystyle\hskip
105.84428pt+u^{\frac{1}{1+\varepsilon}}\left(\frac{1}{s}\sum_{i=1}^{s}\mathbb{P}\left(|X_{i}|>M_{s,t}\right)^{\frac{\epsilon}{1+\varepsilon}}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:ineqM_1}}}{{\leq}}\sqrt{{\frac{2\left(\frac{us}{\log(2\delta^{-1})}\right)^{\frac{1-\epsilon}{1+\epsilon}}u\log\left(2\delta^{-1}\right)}{s}}}+\frac{\left(\frac{us}{\log(2\delta^{-1})}\right)^{\frac{1}{1+\epsilon}}\log\left(2\delta^{-1}\right)}{3s}+$
$\displaystyle\hskip
152.22241pt+u^{\frac{1}{1+\varepsilon}}\left(\frac{1}{s}\sum_{i=1}^{s}\mathbb{P}\left(|X_{i}|>M_{s,t}\right)^{\frac{\epsilon}{1+\varepsilon}}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:ineqM_2}}}{{\leq}}\sqrt{{\frac{2\left(\frac{us}{\log(2\delta^{-1})}\right)^{\frac{1-\epsilon}{1+\epsilon}}u\log\left(2\delta^{-1}\right)}{s}}}+\frac{\left(\frac{us}{\log(2\delta^{-1})}\right)^{\frac{1}{1+\epsilon}}\log\left(2\delta^{-1}\right)}{3s}+$
$\displaystyle\hskip
152.22241pt+\dfrac{u^{\frac{1}{1+\varepsilon}}}{s}\sum_{i=1}^{s}\left(\frac{49\log\left(2\delta^{-1}\right)}{s}\right)^{\frac{\epsilon}{1+\varepsilon}}$
$\displaystyle\leq\left(2+\frac{\sqrt{2}}{3}+7\sqrt{2}\right)u^{\frac{1}{1+\epsilon}}\left[\frac{\log(\delta^{-1})}{n}\right]^{\frac{\epsilon}{1+\epsilon}}$
$\displaystyle\leq
15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(\delta^{-1})}{n}\right]^{\frac{\epsilon}{1+\epsilon}}.$

∎

###  A.7 Proof of Theorem 4

We now prove the upper bound on regret for AdaR-UCB under Assumption 1.

We define for every arm $i\in[K]$ and every $t\in[T]$, the upper confidence
bound as

$B_{i,N_{i}(t-1),t}=\widehat{\mu}_{i,N_{i}(t-1),t}+2\sqrt{\frac{V_{N_{i}(t-1)}(\mathbf{Y}_{i})\log(t^{3})}{N_{i}(t-1)}}+19\frac{\widehat{M}_{i,N_{i}(t-1),t}\log(t^{3})}{N_{i}(t-1)},$

where $N_{i}(t-1)$ is the number of times arm $i$ has been pulled up to time
$t-1$. Note that $N_{i}(t-1)$ is a random variable for every $i$ and every
$t$, where the randomness is inherited from the stochastic nature of the
environment.

Each time an arm $i$ is chosen, AdaR-UCB pulls it two times in a row in order
to collect independent samples for estimator and threshold. Since the two
collections of samples are independent and never used jointly, we consider
$N_{i}(t-1)$ as the number of times arm $i$ has been chosen, and not the
number of times it has been effectively pulled (which would be the double).

We now show that if $i_{t}=i$, for any $i$ such that $\Delta_{i}>0$, then one
of the following four inequalities is true:

$\displaystyle\text{either}\ B_{i^{*},N_{i^{*}}(t-1),t}\leq\mu^{*},$ (33)
$\displaystyle\quad\text{or}\quad\widehat{\mu}_{i,N_{i}(t-1),t}(\mathbf{X}_{i})>\mu_{i}+15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}},$
(34) $\displaystyle\quad\text{or}\
N_{i}(t-1)<36\left(\dfrac{36u}{(\Delta_{i})^{1+\epsilon}}\right)^{\frac{1}{\epsilon}}\log{(t^{3})},$
(35) $\displaystyle\quad\text{or}\
\sqrt{V_{N_{i}(t-1)}(\mathbf{Y}_{i})}>\sqrt{\mathbb{E}[V_{N_{i}(t-1)}(\mathbf{Y}_{i})]}+2\widehat{M}_{i,N_{i}(t-1),t}\sqrt{\frac{2\log(t^{3})}{N_{i}(t-1)}}.$
(36)

Indeed, assume that all four inequalities are false. Then we have

$\displaystyle B_{i^{*},N_{i^{*}}(t-1),t}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:robust1})}}{{>}}\mu^{*}=\mu_{i}+\Delta_{i}$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:robust2})}}{{\geq}}\widehat{\mu}_{i,N_{i}(t-1),t}(\mathbf{X}_{i})-15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}+\Delta_{i}$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\geq}}\
\widehat{\mu}_{i,N_{i}(t-1),t}(\mathbf{X}_{i})+2\sqrt{\frac{V_{N_{i}(t-1)}(\mathbf{Y}_{i})\log(t^{3})}{N_{i}(t-1)}}+19\frac{\widehat{M}_{i,N_{i}(t-1),t}\log(t^{3})}{N_{i}(t-1)}$
$\displaystyle=B_{i,N_{i}(t-1),t}.$

The step marked with (*) is a consequence of the fact that both (35) and (36)
are false. In particular, we need to show that

$\displaystyle\Delta_{i}\geq
15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}+2\sqrt{\frac{V_{N_{i}(t-1)}(\mathbf{Y})\log(t^{3})}{N_{i}(t-1)}}+19\frac{\widehat{M}_{N_{i}(t-1)}\log(t^{3})}{N_{i}(t-1)}.$
(*)

To do so, we make use of Theorem 8 and the following fact:

$\displaystyle\mathbb{E}[V_{N_{i}(t-1)}(\mathbf{Y}_{i})]$
$\displaystyle=\mathbb{E}\left[\textbf{Y}_{i}^{2}\right]-\mathbb{E}\left[\textbf{Y}_{i}\right]^{2}\leq\mathbb{E}\left(X_{t}^{2}\mathbbm{1}_{|X_{t}|\leq\widehat{M}_{t}}\right)$
$\displaystyle=\mathbb{E}\left(|X_{t}|^{1+\epsilon}|X_{t}|^{1-\epsilon}\mathbbm{1}_{|X_{t}|\leq\widehat{M}_{t}}\right)$
$\displaystyle\leq\mathbb{E}\left(|X_{t}|^{1+\epsilon}\widehat{M}_{t}^{1-\varepsilon}\right)$
$\displaystyle\mathbb{E}[V_{N_{i}(t-1)}(\mathbf{Y}_{i})]$ $\displaystyle\leq
u\widehat{M}_{t}^{1-\epsilon}.$ (37)

Now, we make use of the fact that (35) and (36) are false together with
inequalities (27) and (A.7):

$\displaystyle\Delta_{i}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:robust3}}}{{\geq}}36^{\frac{\epsilon}{1+\epsilon}}(36u)^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}$
$\displaystyle=36u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}$
$\displaystyle=(15+2+19)u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}$
$\displaystyle=15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}+2\sqrt{\dfrac{\log(t^{3})u\left(\frac{uN_{i}(t-1)}{\log(t^{3})}\right)^{\frac{1-\epsilon}{1+\epsilon}}}{N_{i}(t-1)}}+19\dfrac{\left(\frac{uN_{i}(t-1)}{\log(t^{3})}\right)^{\frac{1}{1+\epsilon}}\log(t^{3})}{N_{i}(t-1)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:ineqM_1}}}{{\geq}}15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}+2\sqrt{\dfrac{\log(t^{3})u\widehat{M}_{i,N_{i}(t-1),t}^{1-\epsilon}}{N_{i}(t-1)}}+19\dfrac{\widehat{M}_{i,N_{i}(t-1),t}\log(t^{3})}{N_{i}(t-1)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:sigma_bound}}}{{\geq}}15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}+2\sqrt{\frac{\mathbb{E}[V_{N_{i}(t-1)}(\mathbf{Y_{i}})]\log(t^{3})}{N_{i}(t-1)}}+19\frac{\widehat{M}_{i,N_{i}(t-1),t}\log(t^{3})}{N_{i}(t-1)}$
$\displaystyle=15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}+2\sqrt{\frac{\log(t^{3})}{T_{i}(t-1)}}\left[\sqrt{\mathbb{E}[V_{N_{i}(t-1)}(\mathbf{Y})}]+2\widehat{M}_{N_{i}(t-1)}\sqrt{\frac{2\log(t^{3})}{N_{i}(t-1)}}\right]$
$\displaystyle\hskip
106.69783pt+19\frac{\widehat{M}_{N_{i}(t-1)}\log(t^{3})}{N_{i}(t-1)}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:robust4}}}{{\geq}}15u^{\frac{1}{1+\epsilon}}\left[\frac{\log(t^{3})}{N_{i}(t-1)}\right]^{\frac{\epsilon}{1+\epsilon}}+2\sqrt{\frac{V_{N_{i}(t-1)}(\mathbf{Y}_{i})\log(t^{3})}{N_{i}(t-1)}}+19\frac{\widehat{M}_{i,N_{i}(t-1),t}\log(t^{3})}{N_{i}(t-1)}.$
(*)

Finally, as a consequence of (*), we have

$\displaystyle
B_{i^{*},N_{i^{*}}(t-1),t}\stackrel{{\scriptstyle(*)}}{{>}}B_{i,N_{i}(t-1),t}$

but this is a contradiction to the fact that $i_{t}=i$. Thus, statements (33)
to (36) cannot be false simultaneously.

We make use of a union over all the possible values of $N_{i}(t-1)$ and of the
previously introduced concentration inequalities to bound with
$\frac{1}{t^{3}}$ the probabilities of events (33), (34) and (36) to be true:

$\displaystyle\mathbb{P}\left(\\{\eqref{eq:robust1}\text{ is true}\\}\text{ or
}\\{\eqref{eq:robust2}\text{ is true}\\}\text{ or }\\{\eqref{eq:robust4}\text{
is true}\\}~{}~{}\forall N_{i}(t-1)\in[t]~{}\right)\leq
3\sum_{s=1}^{t}\frac{1}{t^{3}}=\frac{3}{t^{2}}.$

To proceed, we introduce the quantity

$\displaystyle v\coloneqq\left\lceil
108\dfrac{\left(36u\right)^{\frac{1}{\varepsilon}}}{\Delta_{i}^{\frac{1+\varepsilon}{\epsilon}}}\log{T}\right\rceil.$

It’s now time to bound the expected number of times each arm is pulled:

$\displaystyle\mathbb{E}[N_{i}(T)]=\mathbb{E}\left[\sum_{t=1}^{T}\mathbbm{1}_{i_{t}=i}\right]$
$\displaystyle\leq
v+\mathbb{E}\left[\sum_{t=v+1}^{T}\mathbbm{1}_{i_{t}=i\text{ and
}\\{\eqref{eq:robust3}\text{ is false }\\}}\right]$ (38) $\displaystyle\leq
v+\mathbb{E}\left[\sum_{t=v+1}^{T}\left(\mathbbm{1}_{i_{t}=i\text{ and
}\\{\eqref{eq:robust1}\text{ or }\eqref{eq:robust2}\text{ or
}\eqref{eq:robust4}\text{ is true}\\}}\right)\right]$ $\displaystyle\leq
v+\sum_{t=v+1}^{T}\frac{3}{t^{2}}$ $\displaystyle\leq v+5$

We can now conclude the proof using the regret decomposition (and considering
that the effective number of pulls is doubled):

$\displaystyle
R_{T}\leq\sum_{i:\Delta_{i}>0}\left(216\left(\frac{36u}{\Delta_{i}^{1+\epsilon}}\right)^{\frac{1}{\epsilon}}\log
T+10\Delta_{i}\right).$

∎

###  A.8 Proof of Theorem 5

The result can be proven by assuming $\log
T\geq\max_{i\in[K]}\frac{10}{216}\left(\frac{\Delta_{i}^{1+\epsilon}}{36u}\right)^{\frac{1}{\epsilon}}$.

We have:

$\displaystyle R_{T}$
$\displaystyle=\sum_{i:\Delta_{i}>0}2\Delta_{i}\mathbb{E}[N_{i}(T)]^{\frac{\varepsilon}{1+\varepsilon}}\mathbb{E}[N_{i}(T)]^{\frac{1}{1+\varepsilon}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:n_pulls_bound}}}{{\leq}}\sum_{i:\Delta_{i}>0}2\Delta_{i}\mathbb{E}[N_{i}(T)]^{\frac{1}{1+\varepsilon}}\left(108\left(\frac{36u}{\Delta_{i}^{1+\epsilon}}\right)^{\frac{1}{\epsilon}}\log
T+5\right)^{\frac{\varepsilon}{1+\varepsilon}}$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\sum_{i:\Delta_{i}>0}2\Delta_{i}\mathbb{E}[N_{i}(T)]^{\frac{1}{1+\varepsilon}}\left(216\left(\frac{36u}{\Delta_{i}^{1+\epsilon}}\right)^{\frac{1}{\epsilon}}\log
T\right)^{\frac{\varepsilon}{1+\varepsilon}}$
$\displaystyle=\left(216(36u)^{\frac{1}{\epsilon}}\log
T\right)^{\frac{\varepsilon}{1+\varepsilon}}\sum_{i:\Delta_{i}>0}2\mathbb{E}[N_{i}(T)]^{\frac{1}{1+\varepsilon}}$
$\displaystyle\stackrel{{\scriptstyle(**)}}{{\leq}}216^{\frac{1}{1+\epsilon}}(36u)^{\frac{1}{1+\epsilon}}(\log
T)^{\frac{\varepsilon}{1+\varepsilon}}K^{\frac{\varepsilon}{1+\varepsilon}}2\left(\sum_{i:\Delta_{i}>0}\mathbb{E}[N_{i}(T)]\right)^{\frac{1}{1+\varepsilon}}$
$\displaystyle\leq 2T^{\frac{1}{1+\varepsilon}}(216K\log
T)^{\frac{\varepsilon}{1+\varepsilon}}(36u)^{\frac{1}{1+\epsilon}}.$

The step marked with (*) follows from the starting assumption on $\log T$. The
step marked with (**) follows from Hölder inequality.

∎