# Fast UCB-type algorithms for stochastic bandits with heavy and super heavy
symmetric noise

Yuriy Dorn
Institute for Artificial Intelligence
Lomonosov Moscow State University, Moscow, Russia
Moscow Institute of Physics and Technology, Moscow, Russia
<EMAIL_ADDRESS>&Aleksandr Katrutsa
Skoltech, Moscow, Russia
AIRI, Moscow, Russia
<EMAIL_ADDRESS>Ilgam Latypov
Institute for Artificial Intelligence
Lomonosov Moscow State University, Moscow, Russia
Moscow Institute of Physics and Technology, Moscow, Russia
<EMAIL_ADDRESS>&Andrey Pudovikov
Institute for Artificial Intelligence
Lomonosov Moscow State University, Moscow, Russia
<EMAIL_ADDRESS>Corresponding author

###### Abstract

In this study, we propose a new method for constructing UCB-type algorithms
for stochastic multi-armed bandits based on general convex optimization
methods with an inexact oracle. We derive the regret bounds corresponding to
the convergence rates of the optimization methods. We propose a new algorithm
Clipped-SGD-UCB and show, both theoretically and empirically, that in the case
of symmetric noise in the reward, we can achieve an $O(\log T\sqrt{KT\log T})$
regret bound instead of
$O\left(T^{\frac{1}{1+\alpha}}K^{\frac{\alpha}{1+\alpha}}\right)$ for the case
when the reward distribution satisfies
$\mathbb{E}_{X\in\mathcal{D}}[|X|^{1+\alpha}]\leqslant\sigma^{1+\alpha}$
($\alpha\in(0,1])$, i.e. perform better than it is assumed by the general
lower bound for bandits with heavy-tails. Moreover, the same bound holds even
when the reward distribution does not have the expectation, that is, when
$\alpha<0$.

##  1 Introduction

In this work, we consider the stochastic multi-armed bandit problem (MAB) with
a heavy-tailed reward distribution introduced by [1]. This problem is a
special case of the classical MAB problem introduced by [2] with a lower bound
$\Omega\left(T^{\frac{1}{1+\alpha}}K^{\frac{\alpha}{1+\alpha}}\right)$. The
problem is formulated as follows: an agent sequentially chooses one of the $K$
actions (arms) in every round with a total number of rounds equal to $T$. For
each arm $i=1,\dots,K$ there is a corresponding unknown probability
distribution $\mathcal{D}_{i}$ with a finite mean $\mu_{i}$ and finite
$(1+\alpha)$-moment with $\alpha\in(0,1]$. That is, for each arm $i$, there
exists fixed $\sigma_{i}>0$ such that
$\mathbb{E}_{X\in\mathcal{D}_{i}}[|X|^{1+\alpha}]\leqslant\sigma_{i}^{1+\alpha}$.
In each round $t$ when the agent picks an arm $A_{t}$ the reward is drawn
independently from $\mathcal{D}_{A_{t}}$.

An agent aims to minimize the regret, accumulated throughout $T$ rounds

$R_{T}=T\max_{1\leqslant i\leqslant
K}\mu_{i}-\sum_{t=1}^{T}\mathbb{E}[\mu_{A_{t}}].$

The Robust UCB proposed in [1] is a general template for constructing UCB-type
algorithms if one has an accessible and robust mean estimation procedure. In
short, it can be described as follows:

  * •

Find mean estimation procedure with high probability deviation bound, i.e. for
each arm $i$ find mean estimator $\hat{\mu}_{i}^{k_{i}}$ based on $k_{i}$
samples of reward, such that $|\hat{\mu}_{i}^{k_{i}}-\mu_{i}|\leqslant
r(k_{i},\delta)$ holds with probability at least $1-\delta$ and the confidence
radius $r(k_{i},\delta)$ degenerates over $k_{i}$ as fast as possible,

  * •

For each arm $i$ construct upper confidence bound (UCB)

$UCB_{i}(k,\delta)=\hat{\mu}_{i}^{k}+r(k,\delta),$

which is used as a high probability upper bound on mean reward.

  * •

Play arm $A_{t}$ with the highest current UCB $A_{t}=\arg\max_{1\leqslant
i\leqslant K}UCB_{i}(k_{i},\delta)$, receive feedback and update UCB
estimation for the played arm.

In the vanilla UCB introduced by [3], this procedure uses the empirical mean
$\hat{\mu}^{k_{i}}_{i}=\frac{1}{k_{i}}\sum_{t=1}^{T}X_{t}\mathbbm{1}_{\\{A_{t}=i\\}}$
and confidence interval $r(k_{i},\delta)=\sqrt{\frac{2v\log
1/\delta}{k_{i}}}$. In Robust UCB, the empirical mean is replaced by a
truncated empirical mean, median of means, or Catoni’s M-estimator to
construct $\hat{\mu}_{i}^{k_{i}}$ and confidence radius
$r(k_{i},\delta)=v^{1/\alpha}\left(\frac{c\log
1/\delta}{k_{i}}\right)^{\frac{\alpha}{1+\alpha}}$ with an appropriate choice
of parameters $v$ and $c$.

Index-based algorithms, such as UCB-type algorithms, are computationally
intensive procedures. This reduces the practical usefulness of Robust UCB
based on the truncated mean as well as recently proposed algorithms in [4, 5].
From the practical point of view “optimality” is the trade-off between
iteration complexity and oracle complexity with convergence measured in
seconds (not number of iterations) as a final judge.

###  1.1 Related works

The Robust UCB algorithm from [1] is probably the first relevant UCB-type
algorithm for bandits with heavy tails. Study [4] proposed optimal in the
first-factor algorithm with faster concentration compared to well-known
truncated or trimmed empirical mean estimators for the mean of heavy-tailed
distributions. The downside is that the proposed index is computationally
demanding. The authors of [6, 7] propose an optimal algorithm for the case
when it is known that reward distribution has $p$-th moment, but the bounding
constant is unknown. Adaptive Robust UCB algorithm [5] matches the lower bound
and does not require any additional knowledge of the reward’s distribution
parameters.

Study [8] considers Lipschitz bandits with heavy-tailed rewards and
establishes corresponding lower bounds. The authors of [9] consider linear
bandits with heavy-tailed rewards. Optimal algorithms for this setting (up to
a logarithmic factor) were introduced in [10].

In recent years, another idea, usually referred to as ”best-of-two-worlds,”
was proposed. The name implies that the proposed algorithms achieve lower
bounds in both stochastic and adversarial MAB settings. This idea assumes the
application of solution techniques for adversarial bandits from [11] to
stochastic MAB problems with a heavy-tailed distribution of rewards, see [12,
6, 13, 14, 15]. Powered by recent advances in online convex optimization (OCO)
(see [16]), this approach leads to optimal algorithms in both adversarial and
stochastic settings with instance-independent regret bound
$O\left(T^{\frac{1}{1+\alpha}}K^{\frac{\alpha}{1+\alpha}}\right)$.

Despite optimality, there exist cases in which the ”best-of-the-two-worlds”
framework is not the best choice. Because of the nature of the adversarial
bandit problem, any reasonable solution includes additional randomization, and
at each step, the algorithm proposes a probability distribution over arms to
sample and adjusts it based on feedback. In the best case, as the rounds
continue, the probability of picking the best arm converges to 1. In risk-
sensitive applications, additional randomization can be problematic. Another
point is that the probability distribution adjustment is done by online mirror
descent and can sometimes be computationally intensive, for example, when it
is difficult to compute the projections involved. Thus, these features of the
”best-of-the-two-worlds” framework restrict their usefulness for real-time
risk-sensitive and highly loaded systems.

###  1.2 Contributions

In this work, we follow the same UCB template but make it even more general.
Most estimators can be considered as a solution to the corresponding
optimization problem, as MLE is a maximizer of likelihood. Therefore, an
estimator of the mean can be a solution to some stochastic optimization
problem (with the expectation being a solution in the absence of noise). Most
optimization methods are iterative and produce a sequence of estimators
$\\{x^{k}\\}_{k=1}^{\infty}$ that converge to the optimal solution
$\lim_{k\to\infty}x^{k}=x^{*}$. Good methods also provide convergence
guarantees, sometimes with deviation bounds. Therefore, the natural idea is to
construct $K$ auxiliary optimization problems for reward estimation, one for
each arm, and use the appropriate (w.r.t. to accessible inexact oracle)
optimization method and the corresponding convergence rate to construct the
UCB-type index.

To proceed with this idea, we consider a stochastic bandit problem with a
reward distribution that satisfies the following assumption, which is more
convenient than
$\mathbb{E}_{X\in\mathcal{D}}[|X|^{1+\alpha}]\leqslant\sigma^{1+\alpha}$
($\alpha\in(0,1])$, particularly when the expected reward is not properly
defined.

######  Assumption 1.

For any arm $i$ ($i=1,\dots,K$) and any round $t$ ($t=1,\dots,T$), random
reward $X_{i}^{t}=\mu_{i}+\xi_{i}^{t}$ and the probability density function
$\rho_{i}^{t}$ of the noise $\xi_{i}^{t}$ satisfy the following condition:

  * •

$\rho_{i}^{t}(u)=\rho_{i}(u)$ for any $u\in\mathbb{R}$ (i.i.d.),

  * •

$\rho(u)=\rho(-u)$ for any $u\in\mathbb{R}$ (symmetric noise),

  * •

there are $\sigma>0$ and $\alpha>0$, such that
$\mathbb{E}[|\xi_{i}^{t}|^{\alpha}]\leqslant\sigma^{\alpha}$ (heavy tail).

To make a smooth transition from general optimization methods to UCB-type
algorithms, we introduce the concept of $g(k,\delta)$-bounded algorithms in
Subsection 2.1. In Subsection 2.2 we propose a few appropriate auxiliary
optimization problems for arm expected reward estimation, followed by the
introduction of FO-UCB and ZO-UCB algorithms based on general
$g(k,\delta)$-bounded first-order and zero-order algorithms for convex
optimization with inexact oracles.

In Section 2.3 we prove regret bound for FO-UCB

$\displaystyle
R_{T}\leqslant\sum_{i:\Delta_{i}>0}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}^{2}}{8},\frac{1}{T^{2}}\right)+2\right)$
(1)

and in Section 2.4 we prove the similar bound for the ZO-UCB

$R_{T}=\sum_{i=1}^{K}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}}{2},\frac{1}{T^{2}}\right)+2\right).$

In Section 2.5, based on convergence results for Clipped-SGD from [17], we
prove that Clipped-SGD is $g(k,\delta)$-bounded algorithm. Based on this
result, we propose the FO-UCB-type algorithm Clipped-SGD-UCB with regret
$O(\log T\sqrt{KT\log T})$ for noise that satisfies Assumption 1. In Section 3
we show experimentally that our algorithm outperforms other UCB-type
algorithms with heavy-tail and super-heavy-tail (no expectation) settings and
performs nearly optimally in the case of sub-Gaussian noise.

In this work, we consider the case of symmetric noise, for which we obtain the
regret bound $O(\log T\sqrt{TK\log T})$ even in a setting where the noise has
no expectation. Because the Robust UCB with a median of means estimator is
very close to that of our algorithm, it shows results close to ours. The only
drawback is that Robust UCB is much more computationally demanding than our
algorithm.

##  2 UCB via stochastic optimization algorithms

First, we introduce the concept of $g(k,\delta)$-bounded algorithms to clarify
our analysis.

###  2.1 Optimization methods with inexact oracle

For our work, we consider an unconstrained smooth convex optimization problem

$\min_{x\in\mathbb{R}}f(x),$

where the function $f:\mathbb{R}\to\mathbb{R}$ is accessible through the
stochastic first-order oracle $\mathcal{G}:\mathbb{R}\to\mathbb{R}$ or via a
stochastic zero-order oracle $\mathcal{H}:\mathbb{R}\to\mathbb{R}$. Denote
$x^{*}=\arg\min_{x\in\mathbb{R}}f(x)$

An algorithm

$x_{k+1}=\mathcal{A}\left(x_{0},\mathcal{G}(x_{0}),\dots,x_{k},\mathcal{G}(x_{k})\right)$

is called $g(k,\delta)$-bounding first-order algorithm if for any
$k\in\mathbb{N}$ and $\delta>0$ inequality

$f(x_{k})-f(x^{*})\leqslant g(k,\delta)$

holds with a probability of at least $1-\delta$.

An algorithm

$x_{k+1}=\mathcal{A}\left(x_{0},\mathcal{H}(x_{0}),\dots,x_{k},\mathcal{H}(x_{k})\right)$

is called $g(k,\delta)$-bounding zero-order algorithm if for any
$k\in\mathbb{N}$ and $\delta>0$ inequality

$f(x_{k})-f(x^{*})\leqslant g(k,\delta)$

holds with probability at least $1-\delta$.

###  2.2 FO-UCB and ZO-UCB algorithms

We now demonstrate how to construct UCB-type algorithms by incorporating
$g(k,\delta)$-bounding optimization algorithms in the UCB framework.

  1. 1.

For each arm $i$ ($i=1,\dots,K$) construct supplementary convex optimization
problem

$\min_{x\in\mathbb{R}}f_{i}(x),$

such that $\mu_{i}=\arg\min_{x\in\mathbb{R}}f_{i}(x)$, with an accessible
stochastic zero/first-order oracle and the corresponding
$g(k,\delta)$-bounding algorithm $\mathcal{A}$.

  2. 2.

Use $\\{x^{k}_{i}\\}_{k=1}^{T}$ generated by the algorithm $\mathcal{A}$ and
corresponding bound $g(k,\delta)$ to construct UCB-type estimation on the mean
$\mu_{i}$.

  3. 3.

At each round play arm with the biggest UCB.

Setup examples:

  * FO-UCB

Let $f_{i}(x)=\frac{1}{2}(x-\mu_{i})^{2}$ with admissible stochastic first
order oracle $\mathcal{G}(x)=\nabla f_{i}(x,\xi)=x-\xi$. Suppose that we have
$g(k,\delta)$-bounded first-order algorithm $\mathcal{A}$ for this problem,
and the sequence $\\{x_{k}\\}_{k=1}^{\infty}$ is generated by $\mathcal{A}$.
Then we propose the following index

$UCB(i,n_{i}(t),\delta)=x_{i}^{n_{i}(t)}+\sqrt{2g(n_{i}(t),\delta)},$

where $n_{i}(t)=\sum_{s=1}^{t}\mathbbm{1}_{\\{A_{s}=i\\}}$ is the number of
times the $i$th arm is chosen in the first $t$ rounds.

  * ZO-UCB

Let $f_{i}(x)=|x-\mu_{i}|$ with admissible zero-order oracle
$\mathcal{H}(x)=f_{i}(x,\xi)=|x-\xi|$. Suppose that we have
$g(k,\delta)$-bounded zero-order algorithm $\mathcal{A}$ for this problem, and
the sequence $\\{x_{k}\\}_{k=1}^{\infty}$ is generated by $\mathcal{A}$. Then
we propose the following index

$UCB(i,n_{i}(t),\delta)=x_{i}^{n_{i}(t)}+g(n_{i}(t),\delta).$

###  2.3 Convergence of FO-UCB

######  Theorem 2 (Convergence of FO-UCB).

The regret of the FO-UCB with $g(k,\delta)$-bounded first-order algorithm for
the MAB problem with $K$ arms, auxiliary functions
$f_{i}(x)=\frac{1}{2}(x-\mu_{i})^{2}$, period $T$, $\delta=\frac{1}{T^{2}}$
satisfies

$\displaystyle
R_{T}\leqslant\sum_{i:\Delta_{i}>0}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}^{2}}{8},\frac{1}{T^{2}}\right)+2\right)$
(2)

The proof of this theorem is given in Appendix A.

###  2.4 Convergence of ZO-UCB

######  Theorem 3 (Convergence of ZO-UCB).

The regret of the ZO-UCB with $g(k,\delta)$-bounded first-order algorithm for
the MAB problem with $K$ arms, auxiliary functions $f_{i}(x)=|x-\mu_{i}|$,
period $T$, $\delta=\frac{1}{T^{2}}$ satisfies

$R_{T}=\sum_{i=1}^{K}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}}{2},\frac{1}{T^{2}}\right)+2\right)$

The proof of this theorem is given in Appendix B.

######  Remark 4.

Note that these results do not mean that ZO-UCB achieves better regret
compared to FO-UCB because bounding functions $g(k,\delta)$ for first-order
and zero-order algorithms are different.

Thus, we have obtained the general results for arbitrary $g(k,\delta)$-bounded
algorithms. The next step is to proceed with a particular choice of the ZO-UCB
or FO-UCB algorithm and show that these frameworks allow us to obtain very
good variants of the UCB algorithms.

###  2.5 Clipped-SGD-UCB

As we can see from Theorem 2, to make a good UCB-type algorithm we need a good
(in the sense of bounding function $g(k,\delta)$, i.e. convergence) first-
order algorithm. We proceed with clipped-SGD algorithm.

####  2.5.1 Clipped-SGD

Next, we use results obtained in [17] for clipped-SGD with a smooth median of
means as a gradient estimator. In particular, we show that clipped-SGD
algorithm is $g(k,\delta)$-bounded first order algorithm and presents a
particular form of the function $g$. First, we proceed with the definition of
smooth median of means.

######  Definition 5.

Let $\zeta$ be a random element in $\mathbb{R}^{d}$ and let $\theta>0$ be an
arbitrary number. For any positive integers $m$ and $n$, the smoothed median
of means $\mathtt{SMoM}_{m,n}(\zeta,\theta)$ is defined as follows:

$\mathtt{SMoM}_{m,n}(\zeta,\theta)=\mathtt{Med}\left(\upsilon_{1},\dots,\upsilon_{2m+1}\right),$
(3)

where, for each $j\in\\{0,\dots,2m\\}$,

$\upsilon_{j}=\mathtt{Mean}(\zeta_{jn+1},\dots,\zeta_{(j+1)n})+\theta\,\eta_{j+1},$

$\zeta_{1},\dots,\zeta_{(2m+1)n}$ are i.i.d. copies of $\zeta$, and
$\eta_{1},\dots,\eta_{2m+1}\sim{\cal N}(0,{\bf I}_{d})$ are independent
standard Gaussian random vectors.

######  Assumption 6.

There exists $N\in\mathbb{N}$, aggregation rule $\mathcal{R}$ and (possibly
dependent on $T$) constants $b\geqslant 0$, $\sigma\geqslant 0$ such that for
an $x\in\mathbb{R}$ i.i.d. samples $\nabla f_{\xi_{1}}(x),\ldots,\nabla
f_{\xi_{N}}(x)$ from the oracle ${\cal G}(x)$ satisfy the following relations:

$\left|\mathbb{E}[\nabla f_{\Xi}(x)]-\nabla f(x)\right|\leqslant
b\quad\mathbb{E}\left[\left\|\nabla f_{\Xi}(x)-\mathbb{E}[\nabla
f_{\Xi}(x)]\right\|^{2}\right]\leqslant\sigma^{2},$

where $\nabla f_{\Xi}(x)=\mathcal{R}(\nabla f_{\xi_{1}}(x),\ldots,\nabla
f_{\xi_{N}}(x))$ and expectations are taken w.r.t. $\nabla
f_{\xi_{1}}(x),\ldots,\nabla f_{\xi_{N}}(x)$.

Then clipped-SGD algorithm can be defined as

$x^{k+1}=x^{k}-\gamma_{k}\texttt{clip}(\nabla
f_{\Xi^{k}}(x^{k}),\lambda_{k}),$ (4)

where $\nabla f_{\Xi^{k}}(x^{k})$ is an estimator satisfying Assumption 6
sampled independently from previous iterations. We also need the following
assumptions for technical reasons.

######  Assumption 7.

There exists a set $Q\subseteq\mathbb{R}^{d}$ and constant $L>0$ such that for
all $x,y\in Q$

$\|\nabla f(x)-\nabla f(y)\|\leqslant L\|x-y\|,\quad\|\nabla
f(x)\|^{2}\leqslant 2L\left(f(x)-f_{*}\right),$

where $f_{*}=\inf_{x\in Q}f(x)>-\infty$.

Now we are ready to present the particular case of a theorem from [17] to show
that clipped-SGD can be considered as an example of $g(k,\delta)$-bounding
algorithm.

######  Theorem 8.

Consider the problem, where $f(x)=\frac{1}{2}(x-\mu)^{2}$ that is 1-strongly
convex, satisfies Assumption 7, and the oracle gives an unbiased gradient
estimate. Also, we assume that the noise in the gradient estimate satisfies
Assumption 6. Then, there exists $C>0$ such that the clipped-SGD with learning
rate
$\gamma=\min\left(\frac{1}{400L\ln\frac{4(K+1)}{\delta}},\frac{\ln((K+1)R^{2})}{K+1}\right)$
and clipping hyperparameter
$\lambda_{k}=\frac{\exp(-\gamma(1+k/2))R}{120\gamma\ln\frac{4(K+1)}{\delta}}$
provides the iterates such that after $k=1,\ldots,K$ iterations the following
bound holds with probability at least $1-\delta$

$f(x_{k})-f^{*}\leqslant
C\frac{\ln\frac{4(K+1)}{\delta}\ln^{2}((K+1)R^{2})}{k+1}$

where $K$ is sufficiently large and $R\geqslant\|x_{0}-x^{*}\|$.

The proof of this theorem is presented in Appendix C.

######  Corollary 9.

Let Assumptions 6 and 7 hold on $Q=B_{2R}(x^{*})$, where
$R\geqslant\|x^{0}-x^{*}\|$. Suppose that $\nabla f_{\Xi^{k}}(x^{k})$
satisfies Assumption 6, and
$\gamma=\min\left(\frac{1}{400L\ln\frac{4(K+1)}{\delta}},\frac{\ln((K+1)R^{2})}{K+1}\right)$
$\lambda_{k}\equiv\frac{\exp(-\gamma(1+k/2))R}{120\gamma\ln\frac{4(K+1)}{\delta}}.$
Then clipped-SGD is
$C\frac{\ln\frac{4(K+1)}{\delta}\ln^{2}((K+1)R^{2})}{k+1}$-bounding first-
order algorithm.

####  2.5.2 Clipped-SGD-UCB

We are ready to present Clipped-SGD-UCB algorithm. For each arm $i$
($i=1,\dots,K$) choose

$f_{i}(x)=\frac{1}{2}(x-\mu_{i})^{2},$

with stochastic first-order oracle $\nabla f_{i}(x,\xi)=x-\xi$, where $\xi$ is
a random variable sampled from $\mathcal{D}_{i}$.

Then if Assumption 1 holds, the noise on gradient $\nabla f_{i}(x)-\nabla
f_{i}(x,\xi)=\xi-\mu_{i}$ is symmetric.

Algorithm 1 Clipped-SGD-UCB

0: Number of arms $K$, period $T$, batch-size $b=(2m+1)n$, initial estimates
$x_{1}^{0}=\dots=x_{K}^{0}=x^{0}$, clipping regime
$\\{\lambda_{t}\\}_{t=1}^{\infty}$, learning rate schedule
$\\{\gamma_{t}\\}_{t=1}^{\infty}$, parameter $\delta$.

1: Run Clipped-SGD-UCB for each arm $i$ ($i=1,\dots,K$) independently for $b$
iterations and compute $\nabla_{\Xi_{i}^{0}}f_{i}(x_{i}^{0})$ and
$x_{i}^{1}=x_{i}^{0}-\gamma_{0}\texttt{clip}(\nabla
f_{\Xi^{1}_{i}}(x_{i}^{0}),\lambda_{0})$.

2: For each arm $i$ ($i=1,\dots,K$) set $n_{i}(K)=1$ and compute
$UCB(i,n_{i}(K),\delta)=x_{i}^{1}+\sqrt{g(1,\delta)}$.

3: for $t=1,\dots,T$ do

4: Choose arm $i_{t}=\arg\max_{1\leqslant i\leqslant K}UCB(i,n_{i},\delta)$.

5: Play $i_{t}$ arm $b$ times, observe rewards and compute
$\nabla_{\Xi_{i_{t}}^{n_{i_{t}}}}f_{i_{t}}(x_{i_{t}}^{n_{i_{t}}})$.

6: Compute
$x_{i_{t}}^{n_{i_{t}}+1}=x_{i_{t}}^{n_{i_{t}}}-\gamma_{n_{i_{t}}}\texttt{clip}(\nabla_{\Xi_{i_{t}}^{n_{i_{t}}}}f_{i}(x_{i_{t}}^{n_{i_{t}}}),\lambda_{n_{i_{t}}})$.

7: Set $n_{i_{t}}(t+1)=n_{i_{t}}(t)+1$ (increase counter by one).

8: Set  $UCB(i,n_{i}(t+1),\delta)=\begin{cases}&UCB(i,n_{i}(t),\delta),\quad
i\neq i_{t},\\\
&x_{i_{t}}^{n_{i_{t}}}+\sqrt{2g(n_{i_{t}}(t+1),\delta)},\quad\text{otherwise}.\end{cases}$

9: end for

######  Theorem 10 (Convergence of Clipped-SGD-UCB).

The regret of the Clipped-SGD-UCB for multi-armed bandit problem with $K$
arms, period $T$,
$\gamma=\min\left(\frac{1}{400L\ln\frac{4(K+1)}{\delta}},\frac{\ln((K+1)R^{2})}{K+1}\right)$,
$\lambda_{k}=\frac{\exp(-\gamma(1+k/2))R}{120\gamma\ln\frac{4(K+1)}{\delta}}$
and symmetric distribution of rewards satisfies:

$R_{T}\leqslant
4\log((T+1)TR^{2})\sqrt{C\log(4T(T+1)^{2})TK}+\sum_{i}\Delta_{i}$
$R_{T}\leqslant\sum_{i:\Delta_{i}>0}\left[\Delta_{i}+\frac{8C\log(4T(T+1^{2}))\log^{2}((T+1)TR^{2})}{\Delta_{i}}\right]$

The proof of this theorem is presented in Appendix D.

######  Remark 11.

If the algorithm uses a batch of samples to perform a single step with the
batch size $b$, the regret will increase in $b$ times, but the number of
iterations will be $\frac{T}{b}$. Thus adaptive part of the bound will not
change, and only the fixed part will increase, i.e. each arm will require at
least $2b$ samples instead of $2$.

##  3 Numerical Experiments

In this section, we demonstrate the superior performance of the proposed
algorithm in the following environments. The main feature of the test
environment is the structure of the noise that models the uncertainty of the
observed rewards. In the simulations of the multi-armed bandit, one can obtain
a reward estimate $r_{i}=\mu_{i}+\xi$ corresponding to the $i$-th arm, where
$\mu_{i}$ is the ground-truth reward and $\xi$ is the aforementioned noise,
whose distribution is the key feature of the testing environments. In
particular, we focus on super-heavy and heavy tail noise distributions. Also,
we test Gaussian noise to show the performance of our algorithm in a simple
environment. The additional feature of the environment is the number of arms
and the distribution of the corresponding ground-truth rewards. The closer
these rewards are, the more challenging the MAB problem is. For a better
illustration of the algorithms’ performance, we adjust the particular
instances of such environments for the considered noise structure and provide
details in the corresponding sections.

We compare the UCB algorithm [3], the Robust UCB algorithm [1] that uses
median of means to estimate rewards (we further refer to this algorithm as
RUCB-Median), SGD-UCB, SGD-UCB-Median and SGD-UCB-SMoM algorithms. The latter
three algorithms are the particular instances of the proposed framework
summarized in Algorithm 1. In particular, SGD-UCB corresponds to the values
$m=0,n=1$, uses the single sample to estimate gradient similar to vanilla SGD.
SGD-UCB-Median corresponds to the values $m=1,n=1$, takes three samples and
uses their median to estimate gradient. SGD-UCB-SMoM corresponds to the values
$m=1,n=2$ and uses SMoM (3) as a gradient estimate. The parameters $m$ and $n$
are used in Algorithm 1 to generate batch size $b$ and construct gradient
estimate according to Definition 5. We do not consider the Truncated Robust
UCB algorithm [1] since it shows worse performance compared to the RUCB-Median
algorithm. The source code for reproducing the presented results can be found
in the GitHub repository https://github.com/tmpuser1233/Clipped-SGD-UCB.

##### Initialization of reward estimates.

To initialize the reward estimate for every arm we use the following
procedure. Every arm is pulled $p$ times ($p$ is an odd number) and the median
of the obtained rewards are used as initialization $x_{i}^{1}$ in the notation
of Algorithm 1. In this setup we skip the line 1 in pseudocode presented in
Algorithm 1. From our experience we recommend using $p=1$ for Gaussian rewards
noise and $p=3$ for heavy and super-heavy tailed rewards nose.

###  3.1 Super-heavy tail MAB

In this section, we consider the super-heavy tail distributions of the noise
used in the rewards uncertainty simulation. A distribution has a super-heavy
tail if the expectation of the corresponding random variable does not exist.
In particular, we test Cauchy distributions with the CDF
$p_{C}(x)=\frac{1}{\pi\gamma[1+(\frac{x}{\gamma})^{2}]}$, where $\gamma=1$,
Fréchet distribution with the CDF $p_{F}(x)=e^{-x^{-\alpha}}$, where
$\alpha=1$, the mixture of Cauchy ($\gamma=1$) and exponential distributions
with the CDF $p_{CE}(x)=0.7\cdot p_{C}(x)+0.3\cdot
e^{-(x+1)}\mathbb{I}\\{x\geqslant-1\\}$ and the mixture of Cauchy ($\gamma=1$)
and Pareto distributions with the CDF $p_{CP}=0.7\cdot
p_{C}(x)+0.3\cdot\frac{3}{(x+1.5)^{4}}\mathbb{I}\\{x\geqslant-1.5\\}$. Note
that the latter two mixtures of distributions represent the asymmetric
distributions. Although we do not consider asymmetric noise in our proof, we
demonstrate the performance of the proposed framework for such noise
distributions empirically.

To simulate multi-armed bandit, we use the following three environments: 10
arms and the ground-truth reward of the $i$-th arm $\mu_{i}=i,i=0,\ldots,9$,
10 arms and the ground-truth reward of the $i$-th arm
$\mu_{i}=i/10,i=0,\ldots,9$, and 100 arms and the ground-truth reward of the
$i$-th arm $\mu_{i}=i/50,i=0,\ldots,99$. Further, we refer to these
environments as Env1, Env2 and Env3, respectively.

##### Convergence comparison.

To compare the convergence of the considered algorithms we test three
environments mentioned above. Due to the space limitation, we provide here
only plots corresponding to the Cauchy distribution ($\gamma=1$) of the reward
noise $\xi$. The similar plots corresponding to the super-heavy tail
distributions are presented in Appendix E. We use the hyperparameters of the
algorithms which give the best convergence. Figure 1 shows that the proposed
algorithms outperform RUCB-Median and UCB algorithms in Env1 and Env2. At the
same time, Env3 appears more challenging, and RUCB-Median shows slightly
faster convergence in terms of the number of steps. Despite this, we show in
the next paragraph (see Table 1) that our algorithms are significantly faster
in terms of runtime since the single iteration costs are significantly
smaller.

(a) Env1

(b) Env2

(c) Env3

(d) Env1

(e) Env2

(f) Env3

Figure 1: The convergence of the regret metric (the first row) and the mean
regret metric (the second row) for the considered algorithms with Cauchy
distribution ($\gamma=1$) of a reward noise. We report the averaged values
over 120 trials and the corresponding standard deviation area via shaded
regions. Our algorithms show faster convergence in Env1 and Env2 compared to
competitors and slightly slower convergence than RUCB-Median in Env3.

##### Runtime comparison.

In addition to the convergence comparison presented in Figure 1, we also
provide the runtime comparison of the considered algorithms. Such comparison
is important for highlighting the difference in the costs for a single step in
the discussed algorithms. The design of this experiment is the following. We
assign to every algorithm the budget for total pulls of arms equal to
$10^{4}$. In simulations, we track the mean regret $R_{T}/T$ and measure the
runtime to achieve the target values of this metric. We test the target
metrics $R_{T}/T=0.1$ and $R_{T}/T=0.05$. If an algorithm does not achieve the
target value of the mean regret within the assigned budget, we consider such a
run as a fail. We run 100 trials for every algorithm and show in Table 1 the
90% percentile of their running time.

Table 1: Runtime comparison of the considered algorithms to achieve the listed
values of $R_{T}/T$ for the environment Env1 with Cauchy distribution
($\gamma=1$) as a reward noise. Our algorithms more often reach the target
mean regret within the assigned budget, i.e. the number of failed trials is
smaller. Also, we show that our algorithms are significantly faster than RUCB-
Median. We highlight the best values for runtime and # fails with bold.

Algorithms | Runtime for $R_{T}/T=0.1$, s. | # fails | Runtime for $R_{T}/T=0.05$, s | # fails
---|---|---|---|---
SGD-UCB | 2.8 | 7 | 3.7 | 17
SGD-UCB-Median | 2.4 | 17 | 2.6 | 18
SGD-UCB-SMoM | 1.3 | 12 | 1.4 | 30
RUCB-Median | 32.9 | 37 | 33.3 | 37

Note that although the numbers presented in Table 1 depend on environments,
the complexity of the single step of every algorithm preserves over the
different environments. Therefore, we can expect that the ordering of the
algorithms in terms of the runtime will be the same for other noise and
environments.

###  3.2 Heavy-tail MAB

To test the proposed framework in the heavy-tail MAB problem setup, we use the
similar environments as in the previous section and Fréchet distribution with
the CDF $p_{F}(x)=e^{-x^{-\alpha}}$, where $\alpha=1.25$ to model the noise in
the reward estimates.

Figure 2 shows that our algorithms (SGD-UCB and SGD-UCB-Median) provide
smaller mean regret for the considered number of steps in Env2 than RUCB-
Median and UCB algorithms. At the same time, in Env3 we observe only the
asymptotically faster convergence of SGD-UCB and SGD-UCB-Median compared to
the RUCB-Median algorithm. In the observed number of steps, the RUCB-Median
algorithm provides smaller values of mean regret. In addition, Env1 is
especially challenging for the proposed algorithms. The RUCB-Median algorithm
outperforms them and provides the smaller regret values in the considered
number of steps. However, the difference between the regret given by the RUCB-
Median algorithm and the SGD-UCB algorithm is not large and the corresponding
mean regret values are already almost the same.

(a) Env1

(b) Env2

(c) Env3

(d) Env1

(e) Env2

(f) Env3

Figure 2: The convergence of the regret metric (the first row) and the mean
regret metric (the second row) for the considered algorithms with Fréchet
distribution ($\alpha=1.25$) of a reward noise. We report the averaged values
over 120 trials and the corresponding standard deviation area via shaded
regions. Our algorithms show faster convergence in Env2, asymptotically faster
convergence in Env3, and slower convergence than RUCB-Median in Env1.

###  3.3 Gaussian MAB

In this section, we consider three simple environments to test multi-armed
bandits, where reward noise is generated from the standard normal distribution
$\mathcal{N}(0,1)$. The first one corresponds to a bandit with 10 arms and the
reward for the $i$-th arm is computed as follows $\mu_{i}=i/10$, where
$i=0,\ldots,9$. The second one corresponds to a bandit with 10 arms and the
reward for the $i$-th arm is computed as follows $\mu_{i}=i/50$, where
$i=0,\ldots,9$. The third one corresponds to a bandit with 100 arms and the
reward for the $i$-th arm is computed as follows $\mu_{i}=i/50$, where
$i=0,\ldots,99$. We run 150 trial simulations for 3000 steps and average the
final regret. The results of the comparison are presented in Figure 3. These
plots show that in the case of the Gaussian reward noise, the smallest regret
is given by the vanilla UCB algorithm uniformly for the considered
environments. However, the proposed algorithms still converge almost to the
same mean regret values, where UCB converges. This experiment demonstrates
that the proposed algorithms show similar performance to the optimal algorithm
in the Gaussian reward noise setup.

Figure 3: Convergence of the considered algorithms in test environments: a) 10
arms and $\mu_{i}=i/10$, where $i=0,\ldots,9$ (the first column); b) 10 arms
and $\mu_{i}=i/50$, where $i=0,\ldots,9$ (the second column); c) 100 arms and
$\mu_{i}=i/50$, where $i=0,\ldots,99$ (the third column). In such test
environments, UCB provides the best regret and the mean regret compared to
alternatives while our algorithms converge to the same limit values of the
mean regret.

###  3.4 MAB problem with hardly distinguished arms

In addition, to evaluate the robustness of the considered algorithms to the
closed ground-truth rewards, we consider the bandit with hardly
distinguishable rewards. For Gaussian MAB we consider two arms such that the
corresponding rewards are $\\{0,\Delta\\}$. The values of $\Delta$ vary from 0
to 1 with a step size of 0.04. For heavy tail MAB we consider Cauchy
distribution ($\gamma=1$) with 5 arms such that the corresponding rewards are
$\\{0,0,0,0,\Delta\\}$. The values of $\Delta$ vary from 0 to 10 with a step
size of 0.4. For each environment setup, we run 300 trial simulations for 2000
steps and average the final regret on trials. The result of the robustness
analysis is presented in Figure 4. It shows that UCB is optimal for Gaussian
MAB, and our algorithms are close to the RUCB-Median algorithm in terms of the
expected regret for close arms rewards. In the heavy tail environment, we do
not plot UCB, since its expected regret grows crucially and suffers
readability. Our algorithms show smaller expected regrets as arms become more
distinguishable.

(a) Gaussian MAB

(b) Heavy tail MAB

Figure 4: (a) Comparison of the mean regret for the considered algorithms in
Gaussian MAB with two arms with rewards $\\{0,\Delta\\}$. Our algorithms can
distinguish arms with close rewards similar to the competitors. (b) Comparison
of the mean regret for the considered algorithms in heavy tail MAB with five
arms with rewards $\\{0,0,0,0,\Delta\\}.$ Our algorithms can distinguish arms
with close rewards even if the noise is generated from the Cauchy distribution
($\gamma=1$).

##  4 Conclusion and future work

We suggested a new template to construct UCB-type algorithms for stochastic
multi-armed bandits with heavy tails. The main ingredient is to use
$g(k,\delta)$-bounded algorithms for optimization problems with inexact
oracle. As the main illustration example, we propose Clipped-SGD-UCB
algorithm. The proposed algorithm shows convergence even in the case of noise,
which has no expectation. Future work includes the construction of more
appropriate algorithms fine-tuned for the proposed template. It is also
interesting to find good and nontrivial zero-order algorithms appropriate to
the proposed template.

## References

  * [1] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi.  Bandits with heavy tail.  IEEE Transactions on Information Theory, 59(11):7711–7717, 2013.
  * [2] Herbert Robbins.  Some aspects of the sequential design of experiments.  1952\.
  * [3] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47:235–256, 2002.
  * [4] Shubhada Agrawal, Sandeep K Juneja, and Wouter M Koolen.  Regret minimization in heavy-tailed bandits.  In Conference on Learning Theory, pages 26–62. PMLR, 2021.
  * [5] Gianmarco Genalti, Lupo Marsigli, Nicola Gatti, and Alberto Maria Metelli.  Towards fully adaptive regret minimization in heavy-tailed bandits.  arXiv preprint arXiv:2310.02975, 2023.
  * [6] Kyungjae Lee, Hongjun Yang, Sungbin Lim, and Songhwai Oh.  Optimal algorithms for stochastic multi-armed bandits with heavy tailed rewards.  Advances in Neural Information Processing Systems, 33:8452–8462, 2020.
  * [7] Kyungjae Lee and Sungbin Lim.  Minimax optimal bandits for heavy tail rewards.  IEEE Transactions on Neural Networks and Learning Systems, 2022.
  * [8] Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang.  Optimal algorithms for lipschitz bandits with heavy-tailed rewards.  In International Conference on Machine Learning, pages 4154–4163. PMLR, 2019.
  * [9] Andres Munoz Medina and Scott Yang.  No-regret algorithms for heavy-tailed linear bandits.  In International Conference on Machine Learning, pages 1642–1650. PMLR, 2016.
  * [10] Han Shao, Xiaotian Yu, Irwin King, and Michael R Lyu.  Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs.  Advances in Neural Information Processing Systems, 31, 2018.
  * [11] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.  The nonstochastic multiarmed bandit problem.  SIAM journal on computing, 32(1):48–77, 2002.
  * [12] Julian Zimmert and Yevgeny Seldin.  An optimal algorithm for stochastic and adversarial bandits.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 467–475. PMLR, 2019.
  * [13] 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.
  * [14] Jiujia Zhang and Ashok Cutkosky.  Parameter-free regret in high probability with heavy tails.  Advances in Neural Information Processing Systems, 35:8000–8012, 2022.
  * [15] Yuriy Dorn, Nikita Kornilov, Nikolay Kutuzov, Alexander Nazin, Eduard Gorbunov, and Alexander Gasnikov.  Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits.  Computational Management Science, 21(1):19, 2024.
  * [16] Francesco Orabona.  A modern introduction to online learning.  arXiv preprint arXiv:1912.13213, 2019.
  * [17] Nikita Puchkin, Eduard Gorbunov, Nikolay Kutuzov, and Alexander Gasnikov.  Breaking the heavy-tailed noise barrier in stochastic optimization problems.  arXiv preprint arXiv:2311.04161, 2023.
  * [18] Tor Lattimore and Csaba Szepesvári.  Bandit algorithms.  Cambridge University Press, 2020.

##  Appendix A Proof of Theorem 2

Here we provide the detailed proof of Theorem 2 and its formulation for the
reader’s convenience.

######  Theorem 2 (Convergence of FO-UCB).

The regret of the FO-UCB with $g(k,\delta)$-bounded first-order algorithm for
the MAB problem with $K$ arms, auxiliary functions
$f_{i}(x)=\frac{1}{2}(x-\mu_{i})^{2}$, period $T$, $\delta=\frac{1}{T(T+1)}$
satisfies

$\displaystyle
R_{T}\leqslant\sum_{i:\Delta_{i}>0}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}^{2}}{8},\frac{1}{T^{2}}\right)+1\right)$
(5)

###### Proof.

For proof, we follow the standard approach (see [18]). Denote by
$\Delta_{i}=\mu_{i^{*}}-\mu_{i}$, where $i^{*}=\arg\max_{1\leqslant i\leqslant
K}\mu_{i}$. Then regret can be computed as

$R_{T}=\sum_{i=1}^{K}\Delta_{i}\mathbb{E}[n_{i}(T)]$

where $n_{i}(t)$ is the number of rounds before round $t$ when arm $i$ was
chosen.

Let $G_{i}$ be a ”good” event defined by

$G_{i}=\left\\{\mu_{i^{*}}<\min_{1\leqslant t\leqslant
T}UCB(i^{*},n_{i^{*}}(t),\delta)\right\\}\cap\left\\{UCB(i,u_{i},\delta)<\mu_{i^{*}}\right\\},$

where the constant $u_{i}$ will be chosen later.

We show that if $G_{i}$ holds, then $n_{i}(T)\leqslant u_{i}$. We assume that
this is not true and $n_{i}(T)>u_{i}$. Then, there exists a round $t\leqslant
T$ such that $n_{i}(t-1)=u_{i}$ and $A_{t}=i$. Then

$\displaystyle
UCB(i,n_{i}(t-1),\delta)=x_{i}^{u_{i}}+\sqrt{2g(u_{i},\delta)}<\mu_{i^{*}}<UCB(i^{*},n_{i^{*}}(t-1),\delta).$

Hence, $A_{t}=\arg\max_{1\leqslant j\leqslant K}UCB(j,n_{j}(t-1),\delta)\neq
i$ and we obtain a contradiction.

Next, we bound the probability of the complement event

$\hat{G}_{i}=\left\\{\mu_{i^{*}}>\min_{1\leqslant t\leqslant
T}UCB(i^{*},n_{i^{*}}(t),\delta)\right\\}\cup\left\\{x_{i}^{u_{i}}+\sqrt{2g(u_{i},\delta)}>\mu_{i^{*}}\right\\}.$

We can then determine the probability of the first term using a union bound:

$\displaystyle\mathbb{P}\left[\mu_{i^{*}}>\min_{1\leqslant t\leqslant
T}UCB(i^{*},n_{i^{*}}(t),\delta)\right]$
$\displaystyle=\mathbb{P}\left[\cup_{s\leqslant
T}\left\\{\mu_{i^{*}}>UCB(i^{*},n_{i^{*}}(s),\delta)\right\\}\right]$
$\displaystyle\leqslant\sum_{s\leqslant
T}\mathbb{P}\left[\mu_{i^{*}}>UCB(i^{*},n_{i^{*}}(s),\delta)\right]\leqslant\delta
T$

To bound the probability of the second term, we use the following scheme:

$\displaystyle\mathbb{P}\left[x_{i}^{u_{i}}+\sqrt{2g(u_{i},\delta)}>\mu_{i^{*}}\right]$
$\displaystyle=\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}+\sqrt{2g(u_{i},\delta)}>\mu_{i^{*}}-\mu_{i}\right]$
$\displaystyle=\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}>\Delta_{i}-\sqrt{2g(u_{i},\delta)}\right]$
$\displaystyle=\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}>\Delta_{i}-\sqrt{2g(u_{i},\delta)}|\quad|x_{i}^{u_{i}}-\mu_{i}|>\sqrt{2g(u_{i},\delta)}\right]\cdot\mathbb{P}\left[|x_{i}^{u_{i}}-\mu_{i}|>\sqrt{2g(u_{i},\delta)}\right]$
$\displaystyle+\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}>\Delta_{i}-\sqrt{2g(u_{i},\delta)}|\quad|x_{i}^{u_{i}}-\mu_{i}|\leqslant\sqrt{2g(u_{i},\delta)}\right]\cdot\mathbb{P}\left[|x_{i}^{u_{i}}-\mu_{i}|\leqslant\sqrt{2g(u_{i},\delta)}\right]$
$\displaystyle(\text{choose $u_{i}$:
$\sqrt{2g(u_{i},\delta)}=\Delta_{i}-\sqrt{2g(u_{i},\delta)}$})$
$\displaystyle\leqslant\mathbbm{1}\cdot\delta+0\cdot(1+\delta)=\delta$

Hence

$\mathbb{E}[n_{i}(T)]=\mathbb{E}[n_{i}(T)\mathbbm{1}_{G_{i}}]+\mathbb{E}[n_{i}(T)\mathbbm{1}_{\hat{G}_{i}}]\leqslant
u_{i}+\delta T(T+1)$

Assuming $\delta=\frac{1}{T(T+1)}$ and taking
$u_{i}=g^{-1}\left(\frac{\Delta_{i}^{2}}{8},\delta\right)$, where $g^{-1}$ is
such that $g\left(g^{-1}(x,\delta),\delta\right)=x$, we get

$\mathbb{E}[n_{i}(T)]\leqslant
g^{-1}\left(\frac{\Delta_{i}^{2}}{8},\frac{1}{T(T+1)}\right)+1$

Now, we can proceed with the regret estimation.

$\displaystyle
R_{T}=\sum_{i:\Delta_{i}>0}\Delta_{i}\mathbb{E}[n_{i}(T)]\leqslant\sum_{i:\Delta_{i}>0}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}^{2}}{8},\frac{1}{T(T+1)}\right)+1\right)$

$\square$

##  Appendix B Proof of Theorem 3

Here we provide the detailed proof of Theorem 3 and its formulation for the
reader’s convenience.

######  Theorem 3 (Convergence of ZO-UCB).

The regret of the ZO-UCB with $g(k,\delta)$-bounded first-order algorithm for
the MAB problem with $K$ arms, auxiliary functions $f_{i}(x)=|x-\mu_{i}|$,
period $T$, $\delta=\frac{1}{T(T+1)}$ satisfies

$R_{T}=\sum_{i=1}^{K}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}}{2},\frac{1}{T(T+1)}\right)+1\right)$

###### Proof.

The general scheme for the proof is the same as that of Theorem 2. The main
differences are highlighted.

First, the complement event is

$\hat{G}_{i}=\left\\{\mu_{i^{*}}>\min_{1\leqslant t\leqslant
T}UCB(i^{*},n_{i^{*}}(t),\delta,t)\right\\}\cup\left\\{x_{i}^{u_{i}}+g(u_{i},\delta)>\mu_{i^{*}}\right\\}.$

with bound on the probability of the second part

$\displaystyle\mathbb{P}\left[x_{i}^{u_{i}}+g(u_{i},\delta)>\mu_{i^{*}}\right]$
$\displaystyle=\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}+g(u_{i},\delta)>\mu_{i^{*}}-\mu_{i}\right]$
$\displaystyle=\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}>\Delta_{i}-g(u_{i},\delta)\right]$
$\displaystyle=\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}>\Delta_{i}-g(u_{i},\delta)|\quad|x_{i}^{u_{i}}-\mu_{i}|>g(u_{i},\delta)\right]\cdot\mathbb{P}\left[|x_{i}^{u_{i}}-\mu_{i}|>g(u_{i},\delta)\right]$
$\displaystyle+\mathbb{P}\left[x_{i}^{u_{i}}-\mu_{i}>\Delta_{i}-g(u_{i},\delta)|\quad|x_{i}^{u_{i}}-\mu_{i}|\leqslant
g(u_{i},\delta)\right]\cdot\mathbb{P}\left[|x_{i}^{u_{i}}-\mu_{i}|\leqslant
g(u_{i},\delta)\right]$ $\displaystyle(\text{choose $u_{i}$:
$g(u_{i},\delta)=\Delta_{i}-g(u_{i},\delta)$})$
$\displaystyle\leqslant\mathbbm{1}\cdot\delta+0\cdot(1+\delta)=\delta.$

where we get the same estimation of probability as in the proof of the Theorem
2, but with $u_{i}=g^{-1}\left(\frac{\Delta_{i}}{2},\delta\right)$, which
results in

$\mathbb{E}[n_{i}(T)]\leqslant
g^{-1}\left(\frac{\Delta_{i}}{2},\frac{1}{T(T+1)}\right)+1$

and corresponding regret

$R_{T}=\sum_{i=1}^{K}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}}{2},\frac{1}{T(T+1)}\right)+1\right),$

$\square$

##  Appendix C Proof of Theorem 8

In this section, we present the proof of Theorem 8 and provide its formulation
for the reader’s convenience.

######  Theorem 8.

Consider the problem, where $f(x)=\frac{1}{2}(x-\mu)^{2}$ that is 1-strongly
convex, satisfies Assumption 7, and the oracle gives an unbiased gradient
estimate. Also, we assume that the noise in the gradient estimate satisfies
Assumption 6. Then, there exists $C>0$ such that the clipped-SGD with learning
rate
$\gamma=\min\left(\frac{1}{400L\ln\frac{4(K+1)}{\delta}},\frac{\ln((K+1)R^{2})}{K+1}\right)$
and clipping hyperparameter
$\lambda_{k}=\frac{\exp(-\gamma(1+k/2))R}{120\gamma\ln\frac{4(K+1)}{\delta}}$
provides the iterates such that after $k=1,\ldots,K$ iterations the following
bound holds with probability at least $1-\delta$

$f(x_{k})-f^{*}\leqslant
C\frac{\ln\frac{4(K+1)}{\delta}\ln^{2}((K+1)R^{2})}{k+1}$

where $K$ is sufficiently large and $R\geqslant\|x_{0}-x^{*}\|$.

###### Proof.

The proof is based on the following theorem from [17].

######  Theorem 9.

Let Assumptions 7 and strongly convexity property with $\mu>0$ hold on
$Q=B_{2R}(x^{*})$, where $R\geqslant\|x^{0}-x^{*}\|$. Assume that $\nabla
f_{\Xi^{k}}(x^{k})$ satisfies Assumption 6 with parameters $b_{k},\sigma_{k}$
for $k=0,1,\ldots,K$, $K>0$ and

$\displaystyle 0<\gamma$ $\displaystyle\leqslant$
$\displaystyle\min\left\\{\frac{1}{400L\ln\tfrac{4(K+1)}{\delta}},\frac{\ln(B_{K})}{\mu(K+1)},\frac{\ln(C_{K})}{\mu(1+\nicefrac{{K}}{{2}})},\frac{2\ln(D)}{\mu(K+1)}\right\\},$
(6) $\displaystyle B_{K}$ $\displaystyle=$
$\displaystyle\max\left\\{2,\frac{(K+1)\mu^{2}R^{2}}{5400\sigma^{2}\ln\left(\frac{4(K+1)}{\delta}\right)\ln^{2}(B_{K})}\right\\}={\cal
O}\\!\left(\\!\max\\!\left\\{2,\frac{K\mu^{2}R^{2}}{\sigma^{2}\ln\left(\\!\frac{K}{\delta}\\!\right)\ln^{2}\left(\\!\max\\!\left\\{2,\frac{K\mu^{2}R^{2}}{\sigma^{2}\ln\left(\\!\frac{K}{\delta}\\!\right)}\right\\}\right)}\right\\}\\!\right),$
(7) $\displaystyle C_{K}$ $\displaystyle=$
$\displaystyle\max\left\\{2,\frac{(\frac{K}{2}+1)\mu
R}{480b\ln\left(\frac{4(K+1)}{\delta}\right)\ln(C_{K})}\right\\}={\cal
O}\left(\max\left\\{2,\frac{K\mu
R}{b\ln\left(\frac{K}{\delta}\right)\ln\left(\max\left\\{2,\frac{K\mu
R}{b\ln\left(\frac{K}{\delta}\right)}\right\\}\right)}\right\\}\right),$ (8)
$\displaystyle D$ $\displaystyle=$ $\displaystyle\max\left\\{2,\frac{\mu
R}{80b\ln(D)}\right\\}={\cal O}\left(\max\left\\{2,\frac{\mu
R}{b\ln\left(\max\left\\{2,\frac{\mu R}{b}\right\\}\right)}\right\\}\right),$
(9) $\displaystyle\lambda_{k}$ $\displaystyle=$
$\displaystyle\frac{\exp(-\gamma\mu(1+\nicefrac{{k}}{{2}}))R}{120\gamma\ln\tfrac{4(K+1)}{\delta}},$
(10)

for some $\delta\in(0,1]$ and $b=\max_{k=0,1,\ldots,K}b_{k}$,
$\sigma=\max_{k=0,1,\ldots,K}\sigma_{k}$. Then, after $K$ iterations the
iterates produced by clipped-SGD with probability at least $1-\delta$ satisfy

$\|x^{K+1}-x^{*}\|^{2}\leqslant 2\exp(-\gamma\mu(K+1))R^{2}.$ (11)

In particular, when $\gamma$ equals the minimum from (6), then the iterates
produced by clipped-SGD after $K$ iterations with probability at least
$1-\delta$ satisfy

$\|x^{K}-x^{*}\|^{2}={\cal O}\left(\max\left\\{R^{2}\exp\left(-\frac{\mu
K}{L\ln\tfrac{K}{\delta}}\right),\frac{\sigma^{2}\ln\left(\frac{K}{\delta}\right)\ln^{2}\left(B_{K}\right)}{K\mu^{2}},\frac{bR\ln\left(\frac{K}{\delta}\right)\ln\left(C_{K}\right)}{K\mu},\frac{bR\ln(D)}{\mu}\right\\}\right).$
(12)

In this theorem we take the symmetric noise, therefore we ignore terms $C_{K}$
and $D$. Also, we consider the sufficiently large number of iterations that
$\exp\left({-\frac{K+1}{400L\ln\frac{4(K+1)}{\delta}}}\right)<\frac{C\ln\frac{4(K+1)}{\delta}\ln^{2}B_{K}}{(K+1)}$
holds, where $C=5400\sigma^{2}$. To get the proper bounds for $B_{K}$ related
terms we use the following expression
$\ln^{2}B_{k}\leqslant\ln^{2}\frac{(K+1)R^{2}}{C\ln^{2}\frac{4(K+1)}{\delta}}\leqslant\ln^{2}((K+1)R^{2})$
obtained from the simple estimate $(x-y)^{2}\leqslant\max(x^{2},y^{2})$.

$\square$

##  Appendix D Proof of Theorem 10

Here we provide the detailed proof of Theorem 10 and its formulation for the
reader’s convenience.

######  Theorem 10 (Convergence of Clipped-SGD-UCB).

The regret of the Clipped-SGD-UCB for multi-armed bandit problem with $K$
arms, period $T$, $\gamma_{t}=$, $\lambda_{k}=$ and symmetric distribution of
rewards satisfies:

$R_{T}\leqslant
4\log((T+1)TR^{2})\sqrt{C\log(4T(T+1)^{2})TK}+\sum_{i}\Delta_{i}$
$R_{T}\leqslant\sum_{i:\Delta_{i}>0}\left[\Delta_{i}+\frac{8C\log(4T(T+1^{2}))\log^{2}((T+1)TR^{2})}{\Delta_{i}}\right]$

###### Proof.

From Theorem 2 we get

$\displaystyle
R_{T}\leqslant\sum_{i:\Delta_{i}>0}\Delta_{i}\left(g^{-1}\left(\frac{\Delta_{i}^{2}}{8},\frac{1}{T(T+1)}\right)+1\right)$

In case $g(k,\delta)=\frac{C\log(4(T+1)/\delta)\log^{2}((T+1)R^{2})}{k}$ we
get $g^{-1}(x,\delta)=\frac{C\log(4(T+1)/\delta)\log^{2}(T+1)R^{2}}{x}$, and

$R_{T}\leqslant\sum_{i:\Delta_{i}>0}\left[\Delta_{i}+\frac{8C\log(4T(T+1^{2}))\log^{2}((T+1)TR^{2})}{\Delta_{i}}\right]$

We get instance-dependent bound. Now let $\Delta>0$ be some fixed value. Then
we can bound regret in the following way:

$\displaystyle
R_{T}=\sum_{i:\Delta_{i}>0}\Delta_{i}\mathbb{E}[n_{i}(T)]=\sum_{i:\Delta_{i}<\Delta}\Delta_{i}\mathbb{E}[n_{i}(T)]+\sum_{i:\Delta_{i}\geqslant\Delta}\Delta_{i}\mathbb{E}[n_{i}(T)]$
$\displaystyle\leqslant
T\Delta+\frac{8C\log(4T(T+1)^{2})\log^{2}((T+1)TR^{2})K\log
T}{\Delta}+\sum_{i}\Delta_{i}$ $\displaystyle\left(\text{choose
$\Delta=\frac{\log((T+1)TR^{2})\sqrt{8C\log(4T(T+1)^{2})K}}{\sqrt{T}}$}\right)$
$\displaystyle\leqslant
4\log((T+1)TR^{2})\sqrt{C\log(4T(T+1)^{2})TK}+\sum_{i}\Delta_{i}$

$\square$

##  Appendix E Additional experiments for super heavy tail MAB

(a) Env1

(b) Env2

(c) Env3

(d) Env1

(e) Env2

(f) Env3

Figure 5: Regret and mean regret comparison for reward noise generated from
Fréchet ($\alpha=1$) distribution.

(a) Env1

(b) Env2

(c) Env3

(d) Env1

(e) Env2

(f) Env3

Figure 6: Regret and mean regret comparison for reward noise generated from
the mixture Cauchy $(\gamma=1)$ and exponential distributions with weights
$0.7$ and $0.3$, respectively.

(a) Env1

(b) Env2

(c) Env3

(d) Env1

(e) Env2

(f) Env3

Figure 7: Regret and mean regret comparison for reward noise generated from
the mixture Cauchy $(\gamma=1)$ and Pareto distributions with weights $0.7$
and $0.3$, respectively.