# Zero-Inflated Bandits

Haoyu Wei  Runzhe Wan  Lei Shi  Rui Song

###### Abstract

Many real applications of bandits have sparse non-zero rewards, leading to
slow learning rates. A careful distribution modeling that utilizes problem-
specific structures is known as critical to estimation efficiency in the
statistics literature, yet is under-explored in bandits. To fill the gap, we
initiate the study of zero-inflated bandits, where the reward is modeled as a
classic semi-parametric distribution called zero-inflated distribution. We
carefully design Upper Confidence Bound (UCB) and Thompson Sampling (TS)
algorithms for this specific structure. Our algorithms are suitable for a very
general class of reward distributions, operating under tail assumptions that
are considerably less stringent than the typical sub-Gaussian requirements.
Theoretically, we derive the regret bounds for both the UCB and TS algorithms
for multi-armed bandit, showing that they can achieve rate-optimal regret when
the reward distribution is sub-Gaussian. The superior empirical performance of
the proposed methods is shown via extensive numerical studies.

Machine Learning, ICML

##  1 Introduction

The bandit problem has received increasing attention and has been widely
applied to areas such as clinical trials [19], finance [38], recommendation
systems [58], among others. Accurate uncertainty quantification is the key to
address the exploration-exploitation trade-off and typically requires certain
assumptions regarding the reward distribution, which can be roughly divided
into two groups:

  * •

Parametric: the reward distribution is assumed to belong to a parameterized
family, such as Gaussian or Bernoulli distributions [6, 28, 3]. The strong
assumption ensures that the design and theoretical analysis can be expressed
in closed form. However, in real-world scenarios, there is no definitive
evidence to confirm a specific distribution of rewards, as indicated by
empirical studies [13]. The misspecification may lead to over- or under-
exploration.

  * •

Non-parametric: the reward distributions need only to satisfy certain
characteristics, such as being sub-Gaussian [16, 23, 59] or bounded [32, 31,
25]. In some instances, an appropriate non-parametric approach can achieve a
regret rate comparable to that of parametric methods [42, 25, 23]. However,
These weaker assumptions are more general, yet sacrificing certain statistical
efficiency from ignoring prior structure information. For example, even if the
rates are the same, empirical performance may still exhibit a significant gap
compared to the parametric approach when rewards are correctly specified in
both methodologies [34].

As usual, a careful distribution modeling that utilizes problem-specific
features can improve the learning efficiency, and in bandits, lead to lower
regrets. However, compared to the rich statistical literature on univariate
distribution, this direction is underexplored in bandits.

Towards bridging this gap, this paper initiates the study of this direction by
focusing on the sparse reward problem. Specifically, this work is motivated by
the observation that in many real-world applications, rewards tend to be
sparse, meaning they are zero (or a constant) in most instances. For instance,
in online advertising, the majority of customers do not click on
advertisements, resulting in a zero reward in most cases; however, for those
instances where there is a click, the reward follows a specific distribution.
Similar patterns are observed in a wide range of applications, including
mobile health [35] and freemium games [54]. While some standard bandit
algorithms can still be applied, they fail to utilize the distribution
property and hence can be less efficient.

To develop efficient bandit algorithms tailored for these applications, this
paper introduces the Zero-Inflated Bandits (ZIB) problem. Here, the reward
distribution is modeled as a mixture of two distributions: one being a delta
distribution at zero, and the other requiring only minimal assumptions. This
makes our model semi-parametric, known for its flexibility and capability to
integrate valuable structural information. We provide an extensive analysis of
the ZIB problem across various setups. In the realm of multi-armed bandits, we
propose both Upper-Confidence Bound (UCB)-type and Thompson Sampling (TS)-type
algorithms, designed for rewards with diverse tail behaviors. Similarly, for
contextual bandits, we also develop both UCB-type and TS-type algorithms,
which are readily adaptable under different generalizable model assumptions.

Main Contributions. The contributions of this paper are three-fold. First, we
propose a general design framework for UCB-type and TS-type algorithms
specifically for ZIB. This framework is adaptable to a wide range of reward
distributions and bandit settings. Our algorithms are suitable for a very
general class of reward distributions; we require only that there exists
$\theta>0$ such that the reward raised to the $\theta$ power has a moment
generating function on a small interval around zero (sub-Weibull
distributions) or even possesses moments of order $1+\epsilon$ with some
$\epsilon>0$ (heavy-tail distributions). Secondly, we theoretically derive
regret bounds for ZIB in the context of multi-armed bandits for both UCB-type
and TS-type algorithms under these weak assumptions. Importantly, while our
analysis accommodates a broad range of reward distributions, it is noteworthy
that in the sub-Gaussian case, our algorithms have been shown to achieve
optimal rates: they precisely match both problem-dependent and problem-
independent regret bounds specifically for sub-Gaussian rewards. Furthermore,
in cases where rewards follow a sub-Weibull distribution, our algorithms can
attain exactly the same problem-independent regret bound as those under the
sub-Gaussian assumption. We also develop concentration inequalities that are
novel in the literature and valuable for analyzing the behavior of product
distributions. Lastly, we show the value of the proposed methods through
extensive numerical experiments.

###  1.1 Related work

Besides the literature on bandits with parametric or non-parametric reward
distribution assumptions discussed above, our paper is also related to the
following areas.

There is a line of research on semiparametric bandits [29, 27, 36, 15].
However, these works focus on the misspecification of the regression function
in contextual bandits, with the aim of reducing the assumption of functional
relationship. Therefore, these works are orthogonal to this paper.

The zero-inflated distribution can also be regarded as a specific form of
hierarchical distribution. In recent years, there is a growing interest in
leveraging hierarchical models in bandits [22, 46, 47]. However, all of them
study the hierarchical structure among bandit instances instead of in the
reward distribution.

In addition to using nonparametric distribution families, one may also
consider using bootstrap-based methods [48, 32] that are agnostic to the
distribution assumption. However, on one hand, these works still require
distribution assumptions to have regret guarantee in bandits; on the other
hand, they fail to utilize the problem-specific structure which may sacrifice
efficiency.

##  2 Zero-Inflated Multi-Armed Bandits

###  2.1 Setup

For any positive integer $M$, we denote the set $\\{1,\dots,M\\}$ by $[M]$. We
start our discussion with the Multi-Armed Bandits (MAB) problem: on each round
$t\in[T]$, the agent can choose an action $A_{t}\in\mathcal{A}$ where
$\mathcal{A}=[K]$ is the action space, and then receive a random reward
$R_{t}=r_{A_{t}}+\varepsilon_{t}$, where $r_{k}=\mathbb{E}[R_{t}\mid A_{t}=k]$
is the mean reward of the $k$-th arm and $\varepsilon_{t}$ is the random
error. The performance of a bandit algorithm is measured by the cumulative
regret

$\displaystyle\mathcal{R}(T)=\sum_{t=1}^{T}{\mathbb{E}}\big{[}\max_{a\in\mathcal{A}_{t}}r_{a}-r_{A_{t}}\big{]}.$

We focus on applications where the reward is zero for a significant proportion
of time, and propose to characterize the reward distribution by the following
Zero-Inflated (ZI) model:

$\begin{split}X_{t}&=\mu_{A_{t}}+\varepsilon_{t},\\\
Y_{t}&\,\sim\,\operatorname{ber}(p_{A_{t}}),\\\
R_{t}&=0\times(1-Y_{t})+X_{t}\times Y_{t}.\end{split}$ (1)

Here, for each arm $k\in[K]$, we introduce two unknown parameters, the non-
zero probability $p_{k}\in[0,1]$ and the mean of the non-zero part $\mu_{k}$.
Here $\varepsilon_{t}$ is a mean-zero random error term. We note this
assumption can always be satisfied: given a reward variable $R_{t}$, one can
always define $Y_{t}=\mathds{1}(R_{t}\neq 0)$ and $X_{t}=\mathds{1}(R_{t}\neq
0)\times R_{t}$. Moreover, as such, it is natural to regard $Y_{t}$ as
observable as well. In contrast, the value of $X_{t}$ is only observable when
$Y_{t}\neq 0$ (equivalently, $R_{t}\neq 0$), and in this case it is equal to
$R_{t}$. Finally, the conditional distribution of $R_{t}$ is a mixture of two
distributions, one of which is a delta distribution on zero and the other is
only required to satisfy minimal assumptions; while the assignment $Y_{t}$ is
Bernoulli. For simplicity, we will occasionally omit the subscript $t$ when
there is no ambiguity.

###  2.2 Light-tailed problem

In this section, we focus on scenarios where $\varepsilon$ exhibits a
relatively light tail. Specifically, we consider the case where rewards have
the sub-Weibull tail property, i.e., there exists $\theta>0$ for which the
moment generating function (MGF) of $|\varepsilon|^{\theta}$ is defined at
least within a small interval around zero. This sub-Weibull distribution
family is very general [55, 56]: for example, when $\theta=1$ and $\theta=2$,
sub-Weibull random variables reduce to sub-exponential or subGaussian random
variables, respectively. Mathematically, we denote
$\varepsilon\sim\operatorname{subW}(\theta;C)$ if zero-mean random variable
$\varepsilon$ satisfies
$\mathbb{E}\exp\big{(}|\varepsilon|^{\theta}/C^{\theta}\big{)}\leq 2$, with
$\theta>0$ and $C>0$ representing the tail and size parameters [37, 45].

The sub-Weibull tail behavior of $\varepsilon$ (or $X-\mu$) implies that the
true reward $R-\mu p$ also follows a sub-Weibull distribution with the same
tail parameter $\theta$ (Lemma 3 in Appendix A). This leads to the idea of
directly constructing an upper confidence bound for $R-\mu p$, given that
various available concentration inequalities for sub-Weibull variables (e.g.
[55, 56]).

Once a valid non-asymptotic upper confidence bound for the true mean $\mu p$
is established, a corresponding UCB algorithm can be developed [7]. However,
creating an effective upper confidence bound for a sub-Weibull variable
requires knowledge of both the tail and size parameters, which is a non-
trivial task. As outlined in Lemma 4 in Appendix A, the size parameter for
$R-\mu p$ could be much larger than that for $X-\mu$, as well as the variance
of $R$. This parameter is also highly sensitive to changes in the unknown
parameters $\mu$ and $p$. This crucial observation leads to three key
insights:

  1. 1.

Employing existing knowledge about the non-zero component $X$ to construct an
upper confidence bound for $R-\mu p$ is unreasonable. This is due to the
potential for the size parameter of $R-\mu p$ to be greatly larger than that
of $X-\mu$ (Lemma 4 (i));

  2. 2.

Relying on the variance of the reward $R$ as the size parameter is also
unwarranted, since the size parameter of $R-\mu p$ may greatly exceed the
variance of $R$ (Lemma 4 (ii));

  3. 3.

Estimating the size parameter using estimated $\mu$ and $p$ or other methods
is highly risky and non-robust, given its extreme sensitivity to $\mu$, $p$,
and the size parameter of $X-\mu$ (Lemma 4 (iii)).

Therefore, a new method is necessary to address this problem. To illustrate
our method, let’s assume $X$ is sub-Gaussian with a variance proxy
$\sigma^{2}$, i.e., $\theta=2$, denoted as
$X-\mu\sim\operatorname{subG}(\sigma^{2})$. Recognizing the product structure,
we introduce the ’product method’: by employing various concentration
inequalities, we can establish valid upper bounds for the unknown parameters
$\mu$ and $p$ using the samples $\\{X_{i}\\}_{i=1}^{n}$ and
$\\{Y_{i}\\}_{i=1}^{n}$ as follows:

$\mathbb{P}(\mu>\overline{X}+U_{X})\leq\Delta\alpha,\qquad\mathbb{P}(p>\overline{Y}+U_{Y})\leq(1-\Delta)\alpha.$

with some pre-specific $\Delta\in(0,1)$ and known functions $U_{X}$ and
$U_{Y}$, where $\overline{X}$ and $\overline{Y}$ are the sample average for
$\\{X_{i}\\}_{i=1}^{n}$ and $\\{Y_{i}\\}_{i=1}^{n}$, respectively. For
instance, one may choose
$U_{X}=\sqrt{\frac{2\sigma^{2}}{n}\log\left[\frac{1}{\Delta\alpha}\right]}$,
$U_{Y}=\sqrt{\frac{1}{2n}\log\left[\frac{1}{(1-\Delta)\alpha}\right]}.$ Then

$\displaystyle\mathbb{P}\Big{(}\mu
p>(\overline{X}+U_{X})(\overline{Y}+U_{Y})\Big{)}$ (2)
$\displaystyle\leq\mathbb{P}(\mu-\overline{X}>U_{X})+\mathbb{P}(p-\overline{Y}>U_{Y})=\alpha,$

which suggests that $(\overline{X}+U_{X})(\overline{Y}+U_{Y})$ serves as a
valid upper bound for the true mean of the reward $r=\mu p$. However,
$\overline{X}$ is not directly observable in this context: we only observe the
sample $X_{i}=R_{i}$ when $Y_{i}=1$. Instead, we define the average value of
the observed $X$ as:

$\overline{X}^{*}:=\frac{1}{\\#\\{\text{$X_{j}$ is
observed}\\}}\sum_{\text{$X_{j}$ is observed}}X_{j}.$

Denote $B:=\sum_{i=1}^{n}Y_{i}$. Given the zero-inflated structure, $B$
represents the exact count of observed $X_{j}$. While $B$ is a random
variable, for any fixed $B\in\mathbb{N}$, the sub-Gaussian inequality remains
applicable. Consequently:

$\displaystyle\mathbb{P}\left(\mu-\overline{X}^{*}>\sqrt{\frac{2\sigma^{2}}{B}\log\left[\frac{1}{\Delta\alpha}\right]}\right)$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{P}\left(\mu-\overline{X}^{*}>\sqrt{\frac{2\sigma^{2}}{B}\log\left[\frac{1}{\Delta\alpha}\right]}\mid
B\right)\right]\leq\Delta p.$

This approach, however, leads to a complex concentration with a ‘random’
convergence rate. Ideally, if we were to observe all $X_{i}$, the expected
rate would be $\sqrt{n}$, as indicated by the probability
$\mathbb{P}\left(\sqrt{n}\left(\mu-\overline{X}^{*}\right)>\sqrt{2\sigma^{2}\log\left(\frac{1}{\Delta\alpha}\right)}\right)$.
In contrast, our current method results in a variable rate of $\sqrt{B}$, as
demonstrated by
$\mathbb{P}\left(\sqrt{B}\left(\mu-\overline{X}^{*}\right)>\sqrt{2\sigma^{2}\log\left(\frac{1}{\Delta\alpha}\right)}\right)$.
This variability not only obscures the upper bound for $\mu$ but also
significantly complicates the theoretical analysis.

To resolve this issue, we introduce Lemma 1, which provides a more precise
concentration for the observed average $\overline{X}^{*}$. This concentration
achieves an exact convergence rate of $\sqrt{n}$ instead of a random number
$B$. Utilizing this lemma, we can establish an upper bound
$U^{\mu}=\overline{X}^{*}+U_{X^{*}}$ for $\mu$ within this concentration
framework. Additionally, we use the upper bound $U^{p}=\overline{Y}+U_{Y}$ for
the Bernoulli parameter $p$, as delineated in (2), to formulate the
concentration for the true mean of rewards from each arm. With the derived
valid upper confidence bounds $U^{\mu}k(t)\times U_{k}^{p}(t)$ for the mean of
the $k$-th arm at round $t$, the UCB algorithm [7] selects the arm based on
its UCB index, defined as
$\operatorname*{arg\\!max}_{k\in[K]}U^{\mu}_{k}(t)\times U_{k}^{p}(t)$, for
the $(t+1)$-th round. The details and procedure of our UCB-type algorithm,
product UCB algorithm, are comprehensively outlined in Algorithm 1.

Data: Horizon $T$, sub-Weibull tail parameter $\theta$ and size parameter $C$.

Set $U_{k}^{\mu}=1$ and $U_{k}^{p}=1,\forall k\in[K]$

Set the counters $c_{k}=0$, and set the mean estimator $\widehat{\mu}_{k}=0$
and $\widehat{p}_{k}=0,\forall k\in[K]$.

for  _$t=1,\dots,T$_ do

2 Take action $A_{t}=\operatorname*{arg\\!max}_{k\in[K]}U_{k}^{\mu}\times
U_{k}^{p}$ (break tie randomly); Observe $R_{t}$ and $Z_{t}$; Update
$c_{A_{t}}=c_{A_{t}}+1$,
$\widehat{p}_{A_{t}}=\widehat{p}_{A_{t}}+\frac{Z_{t}-\widehat{p}_{A_{t}}}{c_{A_{t}}}$,
and
$U_{A_{t}}^{p}=\widehat{p}_{A_{t}}+\sqrt{\frac{\log(2/\delta)}{2c_{A_{t}}}}$
if  _$R_{t}\neq 0$_ then

3 Update  $\widehat{\mu}_{A_{t}}=\frac{1}{\\#\\{R_{A_{t}}\neq
0\\}}\sum_{\text{up to current round }t}R_{A_{t}}$ and  $\displaystyle
U_{A_{t}}^{\mu}=\widehat{\mu}_{A_{t}}$
$\displaystyle+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{n\widehat{p}_{A_{t}}/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{n\widehat{p}_{A_{t}}/2}\right)$ where $D(\theta)$ and
$E(\theta)$ are defined in Lemma 1.

4

5 end for

Algorithm 1 UCB for zero-inflated MAB with light tails

We make three remarks on this algorithm design. First, as the only
computational requirement in Algorithm 1 is the updating of observed means and
upper confidence bounds, the computational cost remains at $\mathcal{O}(KT)$,
identical to that of the basic UCB algorithm. Secondly, in addition to the
data, the algorithm requires the tail parameter $\theta$ and the size
parameter $C$ for the non-zero parts. Typically, $\theta$ can be easily
estimated from historical data. As for $C$, it can be set as the maximum
historical value (after outlier removal) minus the average of the observed
non-zero parts, which can ensure
$\mathbb{E}\exp\\{|X-\mu|^{\theta}/C^{\theta}\\}\leq 2$. However, it is
important to note that this technique is not applicable for determining the
size parameter for the observed rewards $R-\mu p$, as Lemma 4 (i) indicates
that it could potentially be infinite. Finally, in the case that each arm
exhibits distinct tail behaviors, it is straightforward to assign separate
tail parameters $\theta_{k}$ and size parameters $C_{k}$ for the $k$-th arm.
Both the theoretical results and the simulated performance remain valid, as
there are no fundamental changes to the underlying principles of the
algorithm.

###  2.3 Heavy-tailed problem

In some applications with zero-inflated outcomes, the non-zero part can be
heavy-tailed. This is indicated by the non-existence of MGF for
$|\varepsilon|^{\theta}$ within any interval for any $\theta>0$. To address
these scenarios, we expand upon our Algorithm 1 and introduce a heavy-tailed
UCB algorithm, incorporating strategies from [12]. Our approach is predicated
on a modest assumption concerning the non-zero part: specifically, that the
distributions of the noise possesses finite moments of order $1+\epsilon$ for
some $\epsilon\in(0,1]$, that is, we only assume the existence of constants
$\epsilon\in(0,1]$ and $M>0$ such that
$\mathbb{E}|\varepsilon|^{1+\epsilon}\leq M$.

Given that sub-Weibull concentrations are not applicable to some of these
distributions, it becomes necessary to replace the sample mean estimator of
$\mu$ for the non-zero part with a more robust alternative and to accordingly
refine the confidence bound. The trimmed mean, as discussed in [12], provides
a solution to this challenge. Specifically, given the finite moment
characteristic of $X$, a winsorized empirical mean with truncation that
increases with sample size will demonstrate a sub-Weibull tail, as supported
by [9], [12], and [18]. Therefore, we can similarly construct a trimmed mean
for the observable non-zero part, achieving a concentration as outlined in
Lemma 2. Subsequently, we establish an upper bound for $\mu_{k}$ as
$U_{k}^{\mu}$. The validity of employing $U_{k}^{\mu}\times U_{k}^{p}$ as an
upper confidence bound for $r_{k}$ is also derived from Lemma 2. The detailed
procedure is elaborated further in Algorithm 2.

Data: Horizon $T$, parameters $\epsilon$ and $M$.

Set $U_{k}^{\mu}=1$ and $U_{k}^{p}=1,\forall k\in[K]$.

Set the counters $c_{k}=0$, and set the mean estimator $\widehat{p}_{k}=0$ and
$\widehat{\mu}_{k}=0,\forall k\in[K]$.

for  _$t=1,\ldots,T$_ do

7 Take action $A_{t}=\operatorname*{arg\\!max}_{k\in[K]}U_{k}^{\mu}\times
U_{k}^{p}$ (break tie randomly); Observe $R_{t}$ and $Z_{t}$; Update
$c_{A_{t}}=c_{A_{t}}+1$,
$\widehat{p}_{A_{t}}=\widehat{p}_{A_{t}}+\frac{Z_{t}-\widehat{p}_{A_{t}}}{c_{A_{t}}}$,
and $U_{k}^{p}=\widehat{p}_{A_{t}}+\sqrt{\frac{2\log t^{2}}{c_{A_{t}}}}$; if
_$R_{t}\neq 0$_ then

8 Update  $\displaystyle\widehat{\mu}_{A_{t}}=\frac{1}{\\#\\{R_{A_{t}}\neq
0\\}}$ $\displaystyle\sum_{\text{up to current round
}t}R_{t}\mathds{1}\left\\{|R_{t}|\leq
g(\widehat{p}_{A_{t}},\epsilon)M^{\frac{1}{1+\epsilon}}\left(\frac{\log
t^{2}}{c_{A_{t}}}\right)^{\frac{\epsilon}{1+\epsilon}}\right\\}$ where the
function $g(\cdot,\epsilon)$ is defined in Lemma 2. and
$U_{k}^{\mu}=\widehat{\mu}_{A_{t}}+M^{1/(1+\epsilon)}\big{(}32\log
t/c_{k}(t)\big{)}^{\epsilon/(1+\epsilon)};$

9

10 end for

Algorithm 2 UCB for zero-inflated bandits with heavy tails

###  2.4 Thompson sampling approach

In addition to UCB-type algorithms, Thompson Sampling (TS) algorithms,
originally proposed by [41], represent another widely adopted approach in
bandit problems. Unlike UCB algorithms that select actions based on the upper
confidence bounds of each arm, TS-type algorithms initiate with prior
distributions for each arm. These algorithms maintain and iteratively update a
distribution for the rewards from each arm, adjusting based on the observed
outcomes in that arm. In some cases, specially when we know the exact
distributions of rewards, TS-type algorithms tend to alleviate the influence
of delayed feedback by randomizing over actions, thus will have a relatively
better performance than other types of algorithm [13, 49]. Therefore, we also
consider TS-type algorithms in our study.

Similarly to our approach with the UCB-type algorithms above, we consider the
non-zero part $X$ and the zero-one variable $Y$ separately within the TS
framework. For illustration purposes, we initially consider the sub-Gaussian
case for $X-\mu$. This can be easily extended to sub-Weibull cases by
introducing an additional sampling step, known as ’Chambers-Mallows-Stuck
(CMS) Generation,’ to rescale the non-zero part to a sub-Gaussian tail.
Further details on this can be found in [50, 17, 39]. Diverging from the
standard TS algorithm for Gaussian rewards, we use a clipped Gaussian
distribution
$\operatorname{cl}\mathcal{N}(\mu,\sigma^{2};\vartheta):=\max{\mathcal{N}(\mu,\sigma^{2}),\vartheta}$
as the posterior for the non-zero sub-Gaussian part $X$. This clipping is
critical when $X$ is not exactly Gaussian, with the truncation $\vartheta$
serving to limit the probability of overestimating suboptimal arms [23, 26].
For the zero-one variable $Y$, even though it is exactly Bernoulli
distributed, we opt to sample it from a clipped Beta distribution,
$\operatorname{cl}\operatorname{Beta}(\alpha,\beta;\vartheta)$, to maintain
consistency with the non-zero part. ). Our TS-type algorithm for the zero-
inflated multi-armed bandit problem is detailed in Algorithm 3.

Data: Prior parameters $\\{\alpha_{k},\beta_{k},v_{k}\\}_{k=1}^{K}$ and
$\rho,\gamma$.

Set the counter $c_{k}=0,\forall k\in[K]$

for  _$t=1,\ldots,T$_ do

12 Sample
$\widetilde{p}_{k}\sim\operatorname{cl}\text{Beta}(\alpha_{k},\beta_{k};\vartheta_{k}(p))$
and
$\widetilde{\mu}_{k}\sim\operatorname{cl}\mathcal{N}\left(v_{k},\frac{2{\sigma^{2}}}{\rho
c_{k}{\widehat{p}_{k}}};\vartheta_{k}(\mu)\right)$ Take action
$A_{t}=\operatorname*{arg\\!max}_{k\in\mathcal{A}}\widetilde{p}_{k}\times\widetilde{\mu}_{k}$;
Observe reward $R_{t}$ and $Z_{t}$; Update
$\alpha_{A_{t}}=\alpha_{A_{t}}+Z_{t}$ and
$\beta_{A_{t}}=\beta_{A_{t}}+1{-Z_{t}}$; Update
$\widehat{p}_{A_{t}}=\widehat{p}_{A_{t}}+\frac{Z_{t}-\widehat{p}_{A_{t}}}{c_{A_{t}}}$
and $c_{A_{t}}=c_{A_{t}}+1$; Update
$\vartheta_{A_{t}}(p)=\widehat{p}_{A_{t}}+\sqrt{\frac{\gamma}{4c_{A_{t}}}\log^{+}\left(\frac{T}{4c_{A_{t}}K}\right)}.$
if  _$R_{t}\neq 0$_ then

13 Calculate:  $\widehat{\mu}_{A_{t}}=\frac{1}{\\#\\{R_{A_{t}}\neq
0\\}}\sum_{\text{up to current round }t}R_{t};$ Update
$v_{A_{t}}=\widehat{\mu}_{A_{t}}$ and
$\displaystyle\vartheta_{A_{t}}(\mu)=\widehat{\mu}_{A_{t}}+\sqrt{\frac{4\gamma\left[1+\log^{-1}(1+1/\sqrt{c_{A_{t}}T})\right]\sigma^{2}}{\widehat{p}_{A_{t}}^{2}c_{A_{t}}}}$
$\displaystyle\sqrt{\log^{+}\left(\frac{4\left[1+\log^{-1}(1+1/\sqrt{c_{A_{t}}T})\right]\sigma^{2}T}{\widehat{p}_{A_{t}}^{2}c_{A_{t}}K}\right)}$

14

15 end for

Algorithm 3 TS for zero-inflated MAB with light tails

##  3 Zero-Inflated Contextual Bandits

In this section, we extend our discussion to the Contextual Bandits (CB)
problem. For concreteness, we consider the following setup of CB, although
other setups can be similarly formulated and addressed: on each round $t$, the
agent observes a context vector $\mathbf{x}_{t}$ and a set of feasible actions
$\mathcal{A}_{t}$, choose an action $A_{t}\in\mathcal{A}_{t}$, and receive a
random reward $R_{t}=r(\mathbf{x}_{t},A_{t})+\varepsilon_{t}$, where $r$ is
the mean-reward function and $\varepsilon_{t}$ is the random error. The
cumulative regret in this setup is defined as

$\displaystyle\mathcal{R}(T)=\sum_{t=1}^{T}{\mathbb{E}}\big{[}\max_{a\in\mathcal{A}_{t}}r(\mathbf{x}_{t},a)-r(\mathbf{x}_{t},A_{t})\big{]}.$

To utilize the ZI structure, we propose to consider the following model:

$\begin{split}Y_{t}&\sim\operatorname{ber}\big{(}h(\mathbf{x}_{t},A_{t};\bm{\theta})\big{)},\\\
X_{t}&=g\big{(}\mathbf{x}_{t},A_{t};\bm{\beta}\big{)}+\varepsilon_{t},\\\
R_{t}&=0\times(1-Y_{t})+X_{t}\times Y_{t},\end{split}$ (3)

where $\varepsilon_{t}$ is a mean-zero error term, $h$ is a function with
codomain $[0,1]$ and parameterized by $\bm{\theta}$, and $g$ is a function
parameterized by $\bm{\beta}$. We remark the relationship that
$r(\mathbf{x},a)=h(\mathbf{x},a;\bm{\theta})\times
g(\mathbf{x},a;\bm{\beta})$.

We first design a TS-type algorithm for zero-inflated CB. Here, we present a
general template of our algorithm in Algorithm 4, so that it can be quickly
adapted according to different demands in different applications.
Specifically, to sample $\bm{\beta}$, we can regard it as a separate
contextual bandit problem with sub-Gaussian outcomes and with data
$\mathcal{H}_{t,\,\text{non-zero}}=\\{(\mathbf{x}_{l},A_{l},R_{l})\\}_{l\leq
t-1:R_{l}\neq 0}$. We can plug in the sampling rule of various TS-type
algorithms, e.g., when $h$ is chosen as linear, kernalized, neural network,
etc. Similarly, to sample $\bm{\theta}$, we can regard it as a separate
contextual bandit problem with binary outcomes and with data
$\mathcal{H}_{t,\,\text{all}}=\\{(\mathbf{x}_{l},A_{l},Z_{l})\\}_{l=1}^{t-1}$.
We can either plug in the sampling rule of TS for generalized linear model or
other TS algorithm for sub-Gaussian rewards, as for $\bm{\theta}$. The
computational cost is hence bounded by the sum of both and typically
acceptable.

Data: Priors $Q(\bm{\beta})$ and $G(\bm{\theta})$, and other algorithm-
specific parameters.

Set $\mathcal{H}_{\text{all}}=\\{\\}$ and $\mathcal{H}_{\text{non-
zero}}=\\{\\}$.

for  _$t=1,\ldots,T$_ do

17 Sample $\widetilde{\bm{\theta}}$ with an appropriate bandit algorithm for
binary outcomes, using $\mathcal{H}_{\text{all}}$; Sample
$\widetilde{\bm{\beta}}$ with an appropriate bandit algorithm for sub-Gaussian
outcomes, using $\mathcal{H}_{\text{non-zero}}$; Take action
$A_{t}=\operatorname*{arg\\!max}_{a\in\mathcal{A}_{t}}h(\mathbf{x}_{t},a;\widetilde{\bm{\theta}})\times
g(\mathbf{x}_{t},a;\widetilde{\bm{\beta}});$ Observe reward $R_{t}$ and
$Y_{t}$; Update the dataset as
$\mathcal{H}_{\text{all}}\leftarrow\mathcal{H}_{\text{all}}\cup\\{(\mathbf{x}_{t},A_{t},Y_{t})\\}$.
if  _$R_{t}\neq 0$_ then

18 Update the dataset as $\mathcal{H}_{\text{non-
zero}}\leftarrow\mathcal{H}_{\text{non-
zero}}\cup\\{(\mathbf{x}_{t},A_{t},R_{t})\\}$.

19

20 end for

Algorithm 4 General template of TS for zero-inflated contextual bandits

Data: Link functions $\psi_{X}(\cdot)$, $\psi_{Y}(\cdot)$, and $h(\cdot)$.
Ellipsoidal ratio sequence $\\{\rho_{X,t},\rho_{Y,t}\\}_{t\geq 0}$. Rridge
parameters $\lambda_{U}$ and $\lambda_{V}$.

Set $\mathcal{H}_{\text{all}}=\\{\\}$ and $\mathcal{H}_{\text{non-
zero}}=\\{\\}$. Set $U=\lambda_{U}I_{d}$ and $V=\lambda_{V}I_{d}$. Set
$B_{U}=B_{V}=0_{d}$.

for  _$t=1,\dots,T$_ do

22 for  _$a\in\mathcal{A}_{t}$_ do

23 Set
$\displaystyle\operatorname{UCB}_{t}(a)=\Big{[}\psi_{X}(\mathbf{x}_{t},a)^{\top}\widehat{\bm{\beta}}+\sqrt{\rho_{X,t}}\|\psi_{X}(\mathbf{x}_{t},a)\|_{V^{-1}}\Big{]}$
$\displaystyle~{}~{}~{}~{}\times\Big{[}h\big{(}\psi_{Y}(\mathbf{x}_{t},a)^{\top}\widehat{\bm{\theta}}\big{)}+\sqrt{\rho_{Y,t}}\|\psi_{Y}(\mathbf{x}_{t},a)\|_{U^{-1}}\Big{]}.$

24 end for

25 Take action
$A_{t}=\operatorname*{arg\\!max}_{a\in\mathcal{A}_{t}}\operatorname{UCB}_{t}(a)$.
Observe reward $R_{t}$ and $Y_{t}$. Update the dataset as
$\mathcal{H}_{\text{all}}\leftarrow\mathcal{H}_{\text{all}}\cup\\{(\mathbf{x}_{t},A_{t},Y_{t})\\}$
and $U=U+\psi_{Y}(\mathbf{x}_{t},A_{t})\psi_{Y}(\mathbf{x}_{t},A_{t})^{\top}$.
Solve
$\widehat{\bm{\theta}}=\arg\min_{\theta\in\Theta}\bigg{\|}\sum_{s=1}^{t}\Big{[}Y_{s}-h\big{(}\psi_{Y}(\mathbf{x}_{s},A_{s})^{\top}{\bm{\theta}}\big{)}\Big{]}\bigg{\|}_{U^{-1}};$
if  _$R_{t}\neq 0$_ then

26 Update the dataset as $\mathcal{H}_{\text{non-
zero}}\leftarrow\mathcal{H}_{\text{non-
zero}}\cup\\{(\mathbf{x}_{t},A_{t},R_{t})\\}$; Update
$V=V+\psi_{X}(\mathbf{x}_{t},A_{t})\psi_{X}(\mathbf{x}_{t},A_{t})^{\top}$ and
$B_{V}=B_{V}+R_{t}\psi_{X}(\mathbf{x}_{t},A_{t})$. Set
$\widehat{\bm{\beta}}=V^{-1}B_{V}$.

27

28 end for

Algorithm 5 General template of UCB for zero-inflated generalized linear
bandits

As a concrete example, we consider the widely-used generalized linear
contextual bandits, where both functions $h$ and $g$ are structured as
generalized linear functions. This setup is characterized by known functions
$\psi_{X}(\cdot)$, $\psi_{Y}(\cdot)$, and $h(\cdot)$, such that
$g(\mathbf{x}_{t},A_{t};\bm{\beta})=\psi_{X}(\mathbf{x}_{t},A_{t})^{\top}\bm{\beta}$
and
$h(\mathbf{x}_{t},A_{t};\bm{\beta})=h\big{(}\psi_{Y}(\mathbf{x}_{t},A_{t})^{\top}\bm{\theta}\big{)}$.
When the $\varepsilon_{t}$ is sub-Gaussian, the corresponding algorithm can be
designed as follows: For the non-zero reward part, we adapt the approach from
sub-Gaussian generalized-linear Thompson Sampling (GLM-TS) [33, 53]. This
involves sampling
$\widetilde{\bm{\theta}}\sim\mathcal{N}(\widehat{\bm{\theta}},c_{t}^{2}V^{-1})$,
where $V=\lambda
I_{d}+\sum_{(\mathbf{x}_{l},A_{l},R_{l})\in\mathcal{H}_{\text{non-
zero}}}\psi_{X}(\mathbf{x}_{l},A_{l})\psi_{X}(\mathbf{x}_{l},A_{l})^{\top}$
represents the covariance matrix. Here,
$\widehat{\bm{\theta}}=V^{-1}\sum_{(\mathbf{x}_{l},A_{l},R_{l})\in\mathcal{H}_{\text{non-
zero}}}R_{l}\psi_{X}(\mathbf{x}_{l},A_{l})$ is the regularized least square
estimator of $\bm{\theta}$. The sequence $\\{c_{t}\\}_{t\geq 0}$, often
referred to as inverse temperature parameters, is crucial in cases where the
unbounded $\varepsilon_{t}$ is not precisely Gaussian-distributed [53]. For
the Bernoulli part, we still adopt GLM-TS by sampling
$\widetilde{\bm{\beta}}\sim\mathcal{N}(\widehat{\bm{\beta}},a^{2}V)$, where
$\widehat{\bm{\beta}}$ is the minimizer of the cross-entropy loss function
$L(\mathcal{H};\bm{\beta})$ and
$\widehat{\bm{\beta}}=\operatorname*{arg\\!min}_{\bm{\beta}}L(\mathcal{H};\bm{\beta})$.
The matrix $V$ is defined as
$V=\sum_{(\mathbf{x}_{l},A_{l},Y_{l})\in\mathcal{H}_{\text{all}}}\dot{h}(\psi_{Y}(\mathbf{x}_{l},A_{l})\widehat{\bm{\beta}})\psi_{Y}(\mathbf{x}_{l},A_{l})\psi_{Y}(\mathbf{x}_{l},A_{l})^{\top}$.
The tuning parameter $a>0$ can be considered as fixed, which suitable here
since $Y_{t}$ is bounded [33]. Similarly, one can also devise the UCB-type
algorithm, as detailed in Algorithm 5.

##  4 Theory

In this section, we undertake a theoretical analysis of the zero-inflated
algorithm and establish their regret bounds. We will start with some key
lemmas that provide insights and motivations for considering our algorithms.
Following this, we will address the technical challenges encountered in
analyzing these algorithms, and introduce some new sharper concentration
results that are particularly relevant to the zero-inflated structure in
Section 4.1. Then we will rigorously prove the regret bounds for both UCB-type
and TS-type algorithms in Section 4.2.

###  4.1 Technical challenges and key lemmas for the product algorithms

Although both components $X$ and $Y$ have been extensively studied in various
literature [see e.g., 44, 30, 55, for sub-Weibull $X$], adapting these
analyses to our context presents non-trivial challenges. This complexity
arises because the reward, and consequently the action selection, is jointly
determined by both $X$ and $Y$. Moreover, in the case of the non-zero reward
part, the observability of the outcome does not solely depend on whether the
corresponding arm is pulled, as in standard bandits, but also depends on the
value of $Y_{t}$. Consequently, the number of times $X_{t}$ can be observed
becomes a random variable in itself. These intricacies create complex
interdependencies between the two parts, making the analysis far from
straightforward.

Again, a straightforward approach involves treating $R_{t}=X_{t}Y_{t}$ as a
composite variable. This consideration is reasonable, given that $R_{t}$
follows a sub-Weibull distribution as for $X_{t}$. However, the specific sub-
Weibull size parameters for $R_{t}$ demonstrate intricate and sensitive
behavior. This complexity suggests that it may be impractical, if not
impossible, to estimate a reasonable upper bound for these size parameters. We
elaborate the relative lemmas in Appendix A.

We now present an alternative concentration for the observed average value of
$\\{X_{i}:X_{i}\text{ is observed under }n\text{ observations}\\}$ in Lemma 1.
It verifies that the observed average of a i.i.d. sub-Weibull sequence behaves
like a combination of a Gaussian tail and a Weibull tail.

######  Lemma 1.

Suppose $X_{i}-\mu\overset{\text{i.i.d.}}{\sim}\operatorname{subW}(\theta;C)$
and $Y_{i}\overset{\text{i.i.d.}}{\sim}\operatorname{ber}(p)$. Let

$\overline{X}^{*}:=\frac{1}{\\#\\{\text{$X_{j}$ is
observed}\\}}\sum_{\text{$X_{j}$ is observed}}X_{j}$

is the observed mean, then

$\displaystyle\mathbb{P}\Bigg{\\{}$
$\displaystyle\big{|}\mu-\overline{X}^{*}\big{|}\geq 2\mathrm{e}D(\theta)C$
$\displaystyle\left(\sqrt{\frac{2p^{-1}\log(4/\delta)}{n}}+E(\theta){\frac{2p^{-1}\log^{(1/\theta)\vee
1}(4/\delta)}{n}}\right)\Bigg{\\}}\leq\delta$

for any $\delta>0$ and $n\geq 4\log(2/\delta)/p^{2}$. The constants
$D(\theta)$ and $E(\theta)$ are defined in Lemma 6.

Another way to state Lemma 1 is using Bernstein-Orlicz norm [44].But it does
not fit our case here, we introduce the concept of the Revised-Generalized
Bernstein-Orlicz (RGBO) norm in Appendix B. As delineated in Lemma 5, the
above lemma can be reformulated as:

$\big{\|}\mu-\overline{X}^{*}\big{\|}_{\Psi_{\theta,\frac{pE(\theta)}{2\sqrt{n}}}}\leq\frac{4\mathrm{e}D(\theta)C}{p\sqrt{n}}$

with probability $1-\delta/2$ for any $n\geq 4\log(2/\delta)/p^{2}$.
Similarly, in the case of the non-zero part exhibiting heavy-tailed behavior,
the trimmed observed average also demonstrates a sub-Weibull tail, as seen in
the following lemma.

######  Lemma 2.

Suppose $Y_{i}\overset{\text{i.i.d.}}{\sim}\operatorname{ber}(p)$ and
$X_{i}-\mu$ satisfies $\mathbb{E}|X_{i}-\mu|^{1+\epsilon}\leq M$ with positive
$M>0$. Let

$\displaystyle\overline{X}^{**}:=\frac{1}{\\#\\{\text{$X_{j}$ is
observed}\\}}$ $\displaystyle\sum_{\text{$X_{j}$ is observed, $j$ rearrage to
$1,2,\ldots$}}X_{j}\mathds{1}\left(|X_{j}|\leq\left(\frac{jM}{\log(2/\delta)}\right)^{\frac{1}{1+\epsilon}}\right)$

is the truncated observed mean, then

$\mathbb{P}\left(\mu-\overline{X}^{**}\geq
g(p,\epsilon)M^{\frac{1}{1+\epsilon}}\left(\frac{\log(2/\delta)}{n}\right)^{\frac{\epsilon}{1+\epsilon}}\right)\leq\delta$

for any $\delta>0$ and $n\geq 4\log(2/\delta)/p^{2}$, where
$g(p,\epsilon):=\frac{(1+\epsilon)2^{\frac{\epsilon}{1+\epsilon}}}{p^{\frac{\epsilon}{1+\epsilon}}}+\frac{4}{3p}+\frac{2}{\sqrt{p}}.$

A direct corollary from Lemma 2 is that we have

$\mathbb{P}\big{(}\mu-\overline{X}^{*}\geq t\big{)}\leq
2\exp\left(-\frac{nt^{\frac{1+\epsilon}{\epsilon}}}{M^{\frac{1}{\epsilon}}g^{\frac{1+\epsilon}{\epsilon}}(p,\epsilon)}\right)$

for any $0\leq
t\leq(p/2)^{\frac{2\epsilon}{1+\epsilon}}g(p,\epsilon)M^{\frac{1}{1+\epsilon}}$.
Intuitively, these lemmas confirm the validity of confidence upper bounds in
UCB-type algorithms, i.e. Algorithm 1 and 2. The proofs for these UCB-type
algorithms heavily depend on these lemmas. Additionally, Lemma 1 is also
applicable to the TS-type algorithm, Algorithm 3, since the posterior
estimation is derived from a clipped Gaussian distribution, with
$\overline{X}^{*}$ being as its mean.

###  4.2 Regret bounds

Without loss of generality, we assume $r_{k}\in(0,1)$, and
$r_{1}=\max_{k\in[K]}r_{k}$, i.e., the first arm is the optimal arm. This
assumption imposes no restrictions on $\mu_{k}$ and $p_{k}$ other than
requiring them to be greater than zero. We first give the UCB algorithm for
zero-inflate with light tails.

####  4.2.1 Regret bounds for UCB-type algorithms

######  Theorem 1.

Suppose $K$-armed zero-inflated bandit with noises following sub-Weibull
distribution $\operatorname{subW}(\theta;C)$. Then Algorithm 1 with
$\delta=4/T^{2}$ will give the upper bound for the cumulated regret as

$\displaystyle\mathcal{R}(T)$ $\displaystyle\leq
4\Big{(}9+512\mathrm{e}D^{2}(\theta)C^{2}\Big{)}\sum_{k=2}^{K}\frac{1}{p_{k}^{2}}\frac{\log
T}{\Delta_{k}}$ $\displaystyle~{}~{}~{}~{}~{}~{}~{}+2^{6+(1/\theta)\vee
1}\mathrm{e}D(\theta)CE(\theta)\sum_{k=2}^{K}\frac{\log^{(1/\theta)\vee
1}T}{p_{k}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}+2\left(T^{-2}+8T^{-1}+3+4p_{1}^{-2}\log
T\right)\sum_{k=2}^{K}\Delta_{k},$

where $\Delta_{k}=r_{1}-r_{k}$ with $k=2,\ldots,K$ are the sub-optimal gaps.

We can write the regret bound in Theorem 1 as

$\mathcal{R}(T)\lesssim\sum_{k=2}^{K}\frac{1}{p_{k}^{2}}\frac{\log
T}{\Delta_{k}}+\sum_{k=2}^{K}\frac{\log^{(1/\theta)\vee 1}T}{p_{k}}+\frac{\log
T}{p_{1}^{2}}\sum_{k=2}^{K}\Delta_{k}$

for problem-dependent case. By applying Cauchy’s inequality, one can
immediately obtain the problem-independent regret is bounded by

$\mathcal{R}(T)\lesssim\frac{K\log
T}{p_{1}^{2}}+\sum_{k=2}^{K}\frac{\sqrt{T\log T}}{p_{k}}.$ (4)

Here we consider $p_{k}$ as the inherent attribute of each arm. The term
$p_{k}$ within the regret bound is intrinsically connected to the model’s
product structure. It serves as an auxiliary parameter placed before the sub-
optimal gaps $\Delta_{k}$, assists in evaluating the problem’s complexity in a
worst-case scenario. If we trade $p_{k}$ are fixed, note that $\Delta_{k}\leq
1$, then the problem-dependent regret bound becomes

$\mathcal{R}(T)\lesssim\sum_{k=2}^{K}\frac{\log
T}{\Delta_{k}}+K\log^{(1/\theta)\vee 1}T,$

and then, the problem-independent regret bound will be

$\mathcal{R}(T)\lesssim\sqrt{KT\log T}+K,$

which has exactly the same rates as the optimal bound stated in Theorem 3.2 in
[20] for sub-Weibull upper confidence upper algorithms up to a log factor [7,
8].

Similarly, we can prove the regret bound for UCB algorithm for heavy-tailed
non-zero part by utilizing the concentration in Lemma 2. The regret bound of
Algorithm 2 is shown in the following theorem.

######  Theorem 2.

Suppose $K$-armed zero-inflated bandit with noises $\varepsilon_{k}$
satisfying $\max_{k\in[K]}\mathbb{E}|\varepsilon_{k}|^{1+\epsilon}<\infty$ for
some $\epsilon\in(0,1]$. Then Algorithm 2 will give the upper bound for the
cumulated regret as

$\displaystyle\mathcal{R}(T)\leq$ $\displaystyle
2\sum_{k=2}^{K}\left(3\Delta_{k}+\frac{4\Delta_{k}}{p_{1}^{2}}+\frac{9}{p_{k}^{2}\Delta_{k}}\right)$
$\displaystyle+\sum_{k=2}^{K}\big{(}2p_{k}g(p_{k},\epsilon)\big{)}^{\frac{1+\epsilon}{\epsilon}}\frac{M^{{1}/{\epsilon}}}{\Delta_{k}^{{1}/{\epsilon}}}\log
T.$

By plugging the explicit formula for $g(\cdot,\cdot)$, the above regret bound
can be rewritten as

$\mathcal{R}(T)\lesssim\frac{1}{p_{1}^{2}}\sum_{k=2}^{K}\Delta_{k}+\sum_{k=2}^{K}\frac{1}{p_{k}^{2}\Delta_{k}}+\sum_{k=2}^{K}\big{(}p_{k}^{\frac{1}{1+\epsilon}}+p_{k}^{1/2}\big{)}\frac{M^{1/\epsilon}}{\Delta_{k}^{1/\epsilon}}\log
T$

Similarly, one can prove the problem-independent regret for Algorithm 2 is

$\mathcal{R}(T)\lesssim\frac{K}{p_{1}^{2}}+\sum_{k=2}^{K}\frac{\sqrt{T}}{p_{k}}+(MT)^{\frac{1}{1+\epsilon}}\left(K\log
T\right)^{\frac{\epsilon}{1+\epsilon}}.$ (5)

Compared to the results in the literature for heavy-tailed bandits without a
zero-inflated structure [12, 18, 14], our regret bound only introduces an
additional term, $\frac{K}{p_{1}^{2}}+\sum_{k=2}^{K}\frac{\sqrt{T}}{p_{k}}$.
If the number of arms is finite and $p_{k}$ are fixed, this additional term is
significantly smaller than
$K^{\frac{\epsilon}{1+\epsilon}}T^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}T$
as $\epsilon\in(0,1]$. Therefore, to the best of our knowledge, our Algorithm
2 for heavy-tailed distributions also achieves the optimal regret rate as in
the current literature.

####  4.2.2 Regret bounds for TS-type algorithms

Here, we also provide the worst-case regret analysis for our TS-type
algorithm, Algorithm 3, when the non-zero part follows a sub-Gaussian
distribution. In contrast to the proofs of UCB-type algorithms in Section
4.2.1, we require the anti-concentration properties of the distributions to
control the probability of underestimating the optimal arm [4, 23, 24].
Fortunately, the clipped Gaussian and clipped Beta distributions designed in
Algorithm 3 as the posteriors for $X_{t}$ and $Y_{t}$ respectively, and both
of them, as well as their product, exhibit anti-concentration with ideal decay
rates (Lemma 7 and Lemma 8).

######  Theorem 3.

Suppose $K$-armed zero-inflated bandit with noises following sub-Gaussian
distribution. Let $\gamma\geq 4$ and $\rho\in(1/2,1)$, and prior
$\alpha_{k},\beta_{k},v_{k}\in[0,1]$. Then Algorithm 3 will give the upper
bounder for the cumulated regret as

$\mathcal{R}(T)\lesssim\sqrt{KT}+\sum_{k=2}^{K}\left(\frac{\Delta_{k}}{p_{k}}+\frac{1}{p_{1}}\sqrt{\frac{T}{p_{k}K}}\right).$

It is worth noting that if we use the bound $\Delta_{k}\leq 1$, the problem-
independent regret becomes
$\mathcal{R}(T)\lesssim\sqrt{KT}+\sum_{k=2}^{K}\left(\frac{1}{p_{k}}+\frac{1}{p_{1}}\sqrt{\frac{T}{p_{k}K}}\right).$
Thus, if considering the values of $p_{k}$ for each arm as fixed, we can
derive that $\mathcal{R}(T)\lesssim\sqrt{KT}+K$. Compared to the problem-
independent regret of the UCB-type algorithm, Algorithm 1, Algorithm 3
actually improves by a factor of $\sqrt{\log T}$. As a result, according to
Theorem 5.1 in [8], our Algorithm 3 achieves the minimax optimal regret of
$\Omega(\sqrt{KT})$ in MAB problems with sub-Gaussian rewards. However, for
sub-Weibull rewards with tails heavier than sub-Gaussian distributions, i.e.,
$\theta<2$, the additional steps involved in sampling auxiliary variables in
GMS generation will introduce an additional sub-linear term of $T^{1/\theta}$.
Similar discussions can be found in Section 3.4 of [17]

##  5 Experiment

In this section, we only conduct simulation experiments to compare the
performance of several MAB algorithms. We leave the study of CB to further
study, as existing CB algorithms are based on different functional form
assumption with (3), and hence it is impossible to have a fair comparison
which focuses on the zero-inflated structure alone with an assumed data
generation model.

For MAB problems, we compare both our UCB-type and TS-type algorithms across
three unbounded reward distributions: Gaussian, Mixed Gaussian, and
Exponential distributions. To ensure a fair comparison with existing UCB-type
and TS-type algorithms, we have designed the following baseline methods.

UCB baselines:

We consider following UCB-type algorithms for comparison. At round $t$, the
agent takes action $A_{t}=\max_{k\in[K]}U_{k}(t)$ with the $k$-th arm’s upper
bounds
$U_{k}(t)=\overline{R}_{k}(t)+\sqrt{\frac{2\tau^{2}\log(2/\delta)}{c_{k}(t)}}$
for sub-Gaussian rewards
$U_{k}(t)=\overline{R}_{k}(t)+\alpha^{2}\sqrt{\frac{2\log(2/\delta)}{c_{k}(t)}}+\alpha\frac{\log(2/\delta)}{c_{k}(t)}$
for sub-Exponential rewards. Here, the size parameters $\tau^{2}$ and $\alpha$
for the true rewards are determined using the following methods:

  * •

Using the original size parameters for the non-zero part $X_{k}$, assuming
they are known, as the size parameter for constructing $U_{k}(t)$;

  * •

Using the estimated variance of the rewards as the size parameter for
constructing $U_{k}(t)$;

  * •

Using the estimated size parameter as follows:

    * –

For sub-Gaussian $X-\mu\sim\operatorname{subG}(\sigma^{2})$, the sub-Gaussian
variance proxy for $R-\mu p$ is solved by

$\tau^{2}=\max_{s\in\mathbb{R}}\frac{2}{s^{2}}\left[-s\mu
p+\log(1-p+p\mathrm{e}^{s\mu+s^{2}\sigma^{2}/2})\right],$

where $p$ is taken as the average of observations $Y$;

    * –

For sub-Exponential $X-\mu\sim\operatorname{subE}(\lambda)$, the sub-
Exponential parameter $\alpha$ for $R-\mu p$ is solved by

$\alpha^{2}=\lambda^{2}\vee\max_{s\in\mathbb{R}}\frac{2}{s^{2}}\left[-s\mu
p+\log(1-p+p\mathrm{e}^{s\mu+s^{2}\lambda^{2}/2})\right],$

where $\mu$ and $p$ are taken as the averages of observations $X$ and $Y$,
respectively.

  * •

(Strong baseline) Using the true size parameter for $R-\mu p$.

TS baselines:

Here we exclusively consider the TS-type algorithm suitable for general sub-
Gaussian distributions, namely the MOTS algorithm [23]. For Gaussian and
mixed-Gaussian rewards, we can directly apply both Algorithm 3 and the MOTS
algorithm. But, when applying with Exponential rewards, we adopt Algorithm 1
from [39]. In doing so, we integrate their step 5 with our algorithm and the
MOTS algorithm. This ensures that both our method and the one proposed in [23]
are correctly adapted for use with sub-Gaussian distributions after the GMS
generation.

Simulation results:

In UCB-type algorithms, the confidence level $\delta$ is set to $4/T^{2}$,
maintaining consistency. The prior parameters and tuning parameters for both
TS-type algorithms are configured in accordance with the recommendations
provided in [23, 39] for the MOTS algorithm and GMS generation. The simulation
results with different size of $p=\max_{k\in[K]}p_{k}$ are shown in Figure 1,
Figure 2, and Figure 3.

Figure 1: Simulation for zero-inflated bandits with $K=10$ and $T=50000$ with
$N=50$ replications. Small $p$ case.

Figure 2: Simulation for zero-inflated bandits with $K=10$ and $T=50000$ with
$N=50$ replications. Moderate $p$ case.

Figure 3: Simulation for zero-inflated bandits with $K=10$ and $T=50000$ with
$N=50$ replications. Large $p$ case.

As we can see, our algorithms, Algorithm 1 and 3, indeed achieve logarithmic
regret across various types of distributions. In stark contrast, with the
exception of the strong baseline (UCB algorithm with the true size parameter
for $R-\mu p$), all other methods have the potential to result in linear
regret. For instance, methods based on the non-zero part of UCB, variance-
based UCB, and estimated proxy-based UCB all exhibit a linear regret in
Gaussian bandits with $p\sim U[0.05,0.10]$, while MOTS algorithm also fails in
Exponential bandits with $p\sim U[0.15,0.20]\,\cup\,U[0.25,0.30]$.

More surprisingly, our UCB algorithm, Algorithm 1, can even exhibit a
significant advantage over the strong baseline in both Gaussian and Mixed-
Gaussian bandits. This remarkable performance can be attributed to the
presence of a zero-inflated structure within our model, resulting in
(calculated) true size parameters that tend to be quite large. Consequently,
this leads to a more relaxed upper bound when applying Chernoff’s inequality.
These findings collectively highlight the advantages of incorporating the
zero-inflated structure into our approach.

##  6 Discussion

First, although we only give the theoretical regret for MAB algorithms, but it
is not hard to extend to the general linear bandit algorithms in Section 3,
specially when the link functions are strictly increasing. There will be no
essential technical difficulties when applying our novel concentrations in
Section 4.1.

Second, the ZI bandits studied in this paper can be regarded as a special case
of the general problem where the reward distribution has certain hierarchical
structure. Such a model could be practical when the reward distribution is
multimodal, or from the data generation perspective, when the reward
generation mechanism has certain hierarchical structure. For example, when a
customer sees a product/ads, his first impression can be super
interested/interested/not interested, and afterwards, his behavior will follow
certain distribution conditional on this first impression. Compared with the
standard bandit literature (e.g., assuming the reward follows Gaussian or sub-
Gaussian), our approach can utilize the problem-specific structure of the
reward distribution and hence improve the learning rates. As an example, we
can consider the CB problem, and assume the reward distribution is a mixture
distribution of $M$ components as follows:

$\displaystyle\mathbf{Y}_{t}\,\sim\,\operatorname{Multinomial}(1,h(\mathbf{x}_{t};\bm{\theta})),$
$\displaystyle X_{t,i}=g_{i}(\mathbf{x}_{t};\bm{\beta})+\epsilon_{i,t},\forall
i\in[M],$ $\displaystyle R_{t}=\sum_{i\in[K]}X_{i,t}Y_{i,t}.$

In this context, $h$ represents a function that takes values in the
$(M-1)$-dimensional simplex, and $g_{i}(\cdot;\cdot)$ denotes the reward
function for each component. Similar UCB-type and TS-type algorithms can be
considered for these scenarios. We reserve these considerations for further
study.

## References

  * Abramowitz, Stegun, and Romer [1988] Abramowitz, M.; Stegun, I. A.; and Romer, R. H. 1988.  Handbook of mathematical functions with formulas, graphs, and mathematical tables.
  * Adamczak et al. [2011] Adamczak, R.; Litvak, A. E.; Pajor, A.; and Tomczak-Jaegermann, N. 2011.  Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling.  _Constructive Approximation_ 34: 61–88.
  * Agrawal and Goyal [2012] Agrawal, S.; and Goyal, N. 2012.  Analysis of thompson sampling for the multi-armed bandit problem.  In _Conference on learning theory_ , 39–1. JMLR Workshop and Conference Proceedings.
  * Agrawal and Goyal [2013] Agrawal, S.; and Goyal, N. 2013.  Thompson sampling for contextual bandits with linear payoffs.  In _International Conference on Machine Learning_ , 127–135. PMLR.
  * Ahle [2017] Ahle, T. D. 2017.  Asymptotic Tail Bound and Applications .
  * Audibert, Bubeck, and Munos [2010] Audibert, J.-Y.; Bubeck, S.; and Munos, R. 2010.  Best arm identification in multi-armed bandits.  In _COLT_ , 41–53.
  * Auer, Cesa-Bianchi, and Fischer [2002] Auer, P.; Cesa-Bianchi, N.; and Fischer, P. 2002.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ 47: 235–256.
  * Auer et al. [2002] Auer, P.; Cesa-Bianchi, N.; Freund, Y.; and Schapire, R. E. 2002.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ 32(1): 48–77.
  * Bickel [1965] Bickel, P. J. 1965.  On some robust estimates of location.  _The Annals of Mathematical Statistics_ 847–858.
  * Bogucki [2015] Bogucki, R. 2015.  Suprema of canonical weibull processes.  _Statistics & Probability Letters_ 107: 253–263.
  * Boucheron, Lugosi, and Massart [2013] Boucheron, S.; Lugosi, G.; and Massart, P. 2013.  Concentration Inequalities: A Nonasymptotic Theory of Independence. Univ. Press.
  * Bubeck, Cesa-Bianchi, and Lugosi [2013] Bubeck, S.; Cesa-Bianchi, N.; and Lugosi, G. 2013.  Bandits with heavy tail.  _IEEE Transactions on Information Theory_ 59(11): 7711–7717.
  * Chapelle and Li [2011] Chapelle, O.; and Li, L. 2011.  An empirical evaluation of thompson sampling.  _Advances in neural information processing systems_ 24\.
  * Chatterjee and Sen [2021] Chatterjee, S.; and Sen, S. 2021.  Regret minimization in isotonic, heavy-tailed contextual bandits via adaptive confidence bands.  _arXiv preprint arXiv:2110.10245_ .
  * Choi et al. [2023] Choi, Y.-G.; Kim, G.-S.; Paik, S.; and Paik, M. C. 2023.  Semi-parametric contextual bandits with graph-Laplacian regularization.  _Information Sciences_ 645: 119367.
  * Chowdhury and Gopalan [2017] Chowdhury, S. R.; and Gopalan, A. 2017.  On kernelized multi-armed bandits.  In _International Conference on Machine Learning_ , 844–853. PMLR.
  * Dubey and Pentland [2019] Dubey, A.; and Pentland, A. S. 2019.  Thompson Sampling on Symmetric Alpha-Stable Bandits.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , 5715–5721. International Joint Conferences on Artificial Intelligence Organization.  doi:10.24963/ijcai.2019/792.  URL https://doi.org/10.24963/ijcai.2019/792.
  * Dubey et al. [2020] Dubey, A.; et al. 2020.  Cooperative multi-agent bandits with heavy tails.  In _International conference on machine learning_ , 2730–2739. PMLR.
  * Durand et al. [2018] Durand, A.; Achilleos, C.; Iacovides, D.; Strati, K.; Mitsis, G. D.; and Pineau, J. 2018.  Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis.  In _Machine learning for healthcare conference_ , 67–82. PMLR.
  * Hao et al. [2019] Hao, B.; Abbasi Yadkori, Y.; Wen, Z.; and Cheng, G. 2019.  Bootstrapping upper confidence bound.  _Advances in neural information processing systems_ 32\.
  * Henzi and DÃ¼mbgen [2023] Henzi, A.; and DÃ¼mbgen, L. 2023.  Some new inequalities for beta distributions.  _Statistics & Probability Letters_ 195: 109783.  ISSN 0167-7152.  doi:https://doi.org/10.1016/j.spl.2023.109783.  URL https://www.sciencedirect.com/science/article/pii/S016771522300007X.
  * Hong et al. [2022] Hong, J.; Kveton, B.; Zaheer, M.; and Ghavamzadeh, M. 2022.  Hierarchical bayesian bandits.  In _International Conference on Artificial Intelligence and Statistics_ , 7724–7741. PMLR.
  * Jin et al. [2021] Jin, T.; Xu, P.; Shi, J.; Xiao, X.; and Gu, Q. 2021.  Mots: Minimax optimal thompson sampling.  In _International Conference on Machine Learning_ , 5074–5083. PMLR.
  * Jin et al. [2022] Jin, T.; Xu, P.; Xiao, X.; and Anandkumar, A. 2022.  Finite-time regret of thompson sampling algorithms for exponential family multi-armed bandits.  _Advances in Neural Information Processing Systems_ 35: 38475–38487.
  * Kalvit and Zeevi [2021] Kalvit, A.; and Zeevi, A. 2021.  A closer look at the worst-case behavior of multi-armed bandit algorithms.  _Advances in Neural Information Processing Systems_ 34: 8807–8819.
  * Karbasi, Mirrokni, and Shadravan [2021] Karbasi, A.; Mirrokni, V.; and Shadravan, M. 2021.  Parallelizing thompson sampling.  _Advances in Neural Information Processing Systems_ 34: 10535–10548.
  * Kim and Paik [2019] Kim, G.-S.; and Paik, M. C. 2019.  Contextual multi-armed bandit algorithm for semiparametric reward model.  In _International Conference on Machine Learning_ , 3389–3397. PMLR.
  * Krause and Ong [2011] Krause, A.; and Ong, C. 2011.  Contextual gaussian process bandit optimization.  _Advances in neural information processing systems_ 24\.
  * Krishnamurthy, Wu, and Syrgkanis [2018] Krishnamurthy, A.; Wu, Z. S.; and Syrgkanis, V. 2018.  Semiparametric contextual bandits.  In _International Conference on Machine Learning_ , 2776–2785. PMLR.
  * Kuchibhotla and Chakrabortty [2022] Kuchibhotla, A. K.; and Chakrabortty, A. 2022.  Moving beyond sub-Gaussianity in high-dimensional statistics: Applications in covariance estimation and linear regression.  _Information and Inference: A Journal of the IMA_ 11(4): 1389–1456.
  * Kveton et al. [2020a] Kveton, B.; Szepesvári, C.; Ghavamzadeh, M.; and Boutilier, C. 2020a.  Perturbed-History Exploration in Stochastic Linear Bandits.  In _Uncertainty in Artificial Intelligence_ , 530–540. PMLR.
  * Kveton et al. [2019] Kveton, B.; Szepesvari, C.; Vaswani, S.; Wen, Z.; Lattimore, T.; and Ghavamzadeh, M. 2019.  Garbage in, reward out: Bootstrapping exploration in multi-armed bandits.  In _International Conference on Machine Learning_ , 3601–3610. PMLR.
  * Kveton et al. [2020b] Kveton, B.; Zaheer, M.; Szepesvari, C.; Li, L.; Ghavamzadeh, M.; and Boutilier, C. 2020b.  Randomized exploration in generalized linear bandits.  In _International Conference on Artificial Intelligence and Statistics_ , 2066–2076. PMLR.
  * Lattimore and Szepesvári [2020] Lattimore, T.; and Szepesvári, C. 2020.  _Bandit algorithms_.  Cambridge University Press.
  * Ling [2019] Ling, W. 2019.  _Quantile regression for zero-inflated outcomes_.  Ph.D. thesis, Columbia University.
  * Ou et al. [2019] Ou, M.; Li, N.; Yang, C.; Zhu, S.; and Jin, R. 2019.  Semi-parametric sampling for stochastic bandits with many arms.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 7933–7940.
  * Rinne [2008] Rinne, H. 2008.  _The Weibull distribution: a handbook_.  CRC press.
  * Shen et al. [2015] Shen, W.; Wang, J.; Jiang, Y.-G.; and Zha, H. 2015.  Portfolio choices with orthogonal bandit learning.  In _Twenty-fourth international joint conference on artificial intelligence_.
  * Shi, Kuruoglu, and Wei [2022] Shi, Z.; Kuruoglu, E. E.; and Wei, X. 2022.  Thompson Sampling on Asymmetric $\alpha$-Stable Bandits.  _arXiv preprint arXiv:2203.10214_ .
  * Skorski [2023] Skorski, M. 2023.  Bernstein-type bounds for beta distribution.  _Modern Stochastics: Theory and Applications_ 10(2): 211–228.
  * Thompson [1933] Thompson, W. R. 1933.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ 25(3-4): 285–294.
  * Urteaga and Wiggins [2018] Urteaga, I.; and Wiggins, C. H. 2018.  Nonparametric gaussian mixture models for the multi-armed contextual bandit.  _stat_ 1050: 8.
  * Vaart and Wellner [2023] Vaart, A. v. d.; and Wellner, J. A. 2023.  Empirical processes.  In _Weak Convergence and Empirical Processes: With Applications to Statistics_ , 127–384. Springer.
  * van de Geer and Lederer [2013] van de Geer, S.; and Lederer, J. 2013.  The Bernstein–Orlicz norm and deviation inequalities.  _Probability theory and related fields_ 157(1-2): 225–250.
  * Vladimirova et al. [2020] Vladimirova, M.; Girard, S.; Nguyen, H.; and Arbel, J. 2020.  Sub-Weibull distributions: Generalizing sub-Gaussian and sub-Exponential properties to heavier tailed distributions.  _Stat_ 9(1): e318.
  * Wan, Ge, and Song [2021] Wan, R.; Ge, L.; and Song, R. 2021.  Metadata-based multi-task bandits with bayesian hierarchical models.  _Advances in Neural Information Processing Systems_ 34: 29655–29668.
  * Wan, Ge, and Song [2023] Wan, R.; Ge, L.; and Song, R. 2023.  Towards scalable and robust structured bandits: A meta-learning framework.  In _International Conference on Artificial Intelligence and Statistics_ , 1144–1173. PMLR.
  * Wan et al. [2023] Wan, R.; Wei, H.; Kveton, B.; and Song, R. 2023.  Multiplier Bootstrap-based Exploration.  _arXiv preprint arXiv:2302.01543_ .
  * Wang and Chen [2018] Wang, S.; and Chen, W. 2018.  Thompson sampling for combinatorial semi-bandits.  In _International Conference on Machine Learning_ , 5114–5122. PMLR.
  * Weron [1996] Weron, R. 1996.  On the Chambers-Mallows-Stuck method for simulating skewed stable random variables.  _Statistics & probability letters_ 28(2): 165–171.
  * Wu et al. [2022] Wu, S.; Wang, C.-H.; Li, Y.; and Cheng, G. 2022.  Residual bootstrap exploration for stochastic linear bandit.  In _Uncertainty in Artificial Intelligence_ , 2117–2127. PMLR.
  * Wu et al. [2016] Wu, Y.; Shariff, R.; Lattimore, T.; and Szepesvári, C. 2016.  Conservative bandits.  In _International Conference on Machine Learning_ , 1254–1262. PMLR.
  * Xu et al. [2022] Xu, P.; Zheng, H.; Mazumdar, E. V.; Azizzadenesheli, K.; and Anandkumar, A. 2022\.  Langevin monte carlo for contextual bandits.  In _International Conference on Machine Learning_ , 24830–24850. PMLR.
  * Yu et al. [2021] Yu, M.; et al. 2021.  Online Testing and Semiparametric Estimation of Complex Treatment Effects. .
  * Zhang and Chen [2020] Zhang, H.; and Chen, S. X. 2020.  Concentration inequalities for statistical inference.  _arXiv preprint arXiv:2011.02258_ .
  * Zhang and Wei [2022] Zhang, H.; and Wei, H. 2022.  Sharper sub-weibull concentrations.  _Mathematics_ 10(13): 2252.
  * Zhang, Wei, and Cheng [2023] Zhang, H.; Wei, H.; and Cheng, G. 2023.  Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm.  _arXiv preprint arXiv:2303.07287_ .
  * Zhou et al. [2017] Zhou, Q.; Zhang, X.; Xu, J.; and Liang, B. 2017.  Large-scale bandit approaches for recommender systems.  In _International Conference on Neural Information Processing_ , 811–821. Springer.
  * Zhu and Tan [2020] Zhu, Q.; and Tan, V. 2020.  Thompson sampling algorithms for mean-variance bandits.  In _International Conference on Machine Learning_ , 11599–11608. PMLR.

##  Appendix A A Supporting Lemmas for Motivations

We delve into a detailed discussion of the support facts for the motivation
stated in Section 4.1. As previously discussed, the key is finding
concentrations that characterize the structure of zero-inflate. Our initial
observation is that the zero-inflated structure preserves the tail behavior
type of the non-zero component $X-\mu$. This finding is presented in the
following lemma.

######  Lemma 3.

Suppose $X-\mu\,\sim\,\operatorname{subW}(\theta;C_{X})$ and
$Y\,\sim\,\operatorname{ber}(p)$ independent with $Y$. Let $R=XY$. There
exists $C_{R}>0$ such that $R-\mu p\,\sim\,\operatorname{subW}(\theta;C_{R})$.

However, the product structure does not guarantee a simple relationship
between the size parameter of the overall distribution and that of the
original non-zero component. This complexity persists even in the simplest
sub-Gaussian or sub-Exponential cases. The size parameter of the product
$R=XY$ can be exceedingly difficult to approximate, as highlighted in the
following lemma.

######  Lemma 4.

Suppose $X-\mu\,\sim\,\operatorname{subG}(\sigma^{2})$ and
$Y\,\sim\,\operatorname{ber}(p)$ independent with $Y$. Let $R=XY$. Then $R-\mu
p$ is sub-Gaussian. Furthermore, denoted the sub-Gaussian variance proxy for
$R-\mu p$ as $\tau^{2}$, then we have:

  * (i)

If $p=1/2$, for any $\sigma^{2}>0$ and arbitrarily large $M>0$, there exists
$\mu_{*}>0$ such that $\tau^{2}>M\sigma^{2}$ for any $\mu>\mu_{*}$;

  * (ii)

Given arbitrarily large $M>0$, there exists $\sigma_{*}^{2},p_{*},\mu_{*}$
such that $\tau^{2}>M\operatorname{var}(R)$ for any $\mu>\mu_{*}$,
$\sigma^{2}<\sigma^{2}_{*}$ and $p\in[p_{*},1)$;

  * (iii)

    * (a)

For any $\sigma^{2}>0$ and arbitrarily large $M>0$, there exists $\mu_{*}>0$
and $p_{*}\in(0,1)$ such that

$\left.\frac{\partial\tau^{2}}{\partial
p}\right|_{\mu=\mu^{\prime},p=p^{\prime}}>M$

for any $\mu^{\prime}\in(0,\mu_{*}]$ and $p^{\prime}\in[p_{*},1)$;

    * (b)

For any $\mu>0$ and arbitrarily large $M>0$, there exists $\sigma_{*}^{2}>0$
and $p_{*}\in(0,1)$ such that

$\left.\frac{\partial\tau^{2}}{\partial p}\right|_{\sigma^{2}=\sigma^{\prime
2},p=p^{\prime}}>M$

for any $\sigma^{\prime 2}\in(0,\sigma^{2}_{*}]$ and $p^{\prime}\in[p_{*},1)$;

    * (c)

For any $\mu\in\mathbb{R}$ and arbitrarily large $M>0$, there exists
$\sigma_{*}^{2}>0$ and $p_{*}\in(0,1)$ such that

$\left.\frac{\partial\tau^{2}}{\partial\mu}\right|_{\sigma^{2}=\sigma^{\prime
2},p=p^{\prime}}>M$

for any $\sigma^{\prime 2}\in(0,\sigma^{2}_{*}]$ and $p^{\prime}\in[p_{*},1)$.

Besides, the exactly same results are hold for
$X-\mu\sim\operatorname{subE}(\lambda)$ by replacing $\sigma^{2}$ with
$\lambda^{2}$ and $\tau^{2}$ with the $R-\mu p$’s sub-Exponential parameter
$\alpha^{2}$ above.

Lemma 4 indicates three key drawbacks in treating $R-\mu p$ as a singular sub-
Gaussian (or sub-Exponential) distribution. First, as detailed in Lemma 4 (i),
the sub-Gaussian variance proxy for $R-\mu p$ may significantly exceed
$\sigma^{2}$. Although $\sigma^{2}$ is commonly treated as a known parameter
or assigned a universal upper bound across each arm [52, 51], this approach is
not feasible for the sub-Gaussian variance proxy $\tau_{k}^{2}$ of
$R_{k}-\mu_{k}p_{k}$ from the $k$-th arm. This is due to its dependence on
$\mu_{k}$, potentially leading to much larger values for some $\mu_{k}$.
Secondly, using the (estimated) variance as the variance proxy, which usually
is regarded as a common practice [16, 59], shows inappropriate for the zero-
inflated structure, as Lemma 4 (ii) indicates. Lastly, Lemma 4 (iii) suggests
that attempts to estimate the sub-Gaussian variance proxy are also tending to
be imprecise due to its complex relationship with $\mu$, $p$, and
$\sigma^{2}$. For visual clarification, see Figure 4 and 5, which illustrate
Lemma 4 in the context of the sub-Gaussian case.

Figure 4: Plot of $\tau^{2}$ with respect to $\mu$ and $p$ or $\sigma^{2}$ and
$p$.

Figure 5: Plot of the ratio ${\tau^{2}}/{\operatorname{var}(R)}$ with respect
to $\mu$ and $p$ or $\sigma^{2}$ and $p$.

##  Appendix B B Proof of Lemmas

In this section, we will provide the proofs for the concentration results
presented in Section 4.1. We will also include relevant theoretical background
and discussions.

We first define the Revised-Generalized Bernstein-Orlicz (RGBO) transformation
function $\Psi_{\theta,L}(\cdot)$ based on the inverse function

$\Psi_{\theta,L}^{-1}(t):=\sqrt{\log(1+t)}+L(\log(1+t))^{(1/\theta)\vee 1}$

for any $t\geq 0$. It is worthy to note that we replace
$(\log(1+t))^{1/\theta}$ with $(\log(1+t))^{(1/\theta)\vee 1}$ in the
Generalized Bernstein-Orlicz function defined in [44, 30]. It is easy to
verify that is monotone increasing and $\Psi_{\theta,L}(0)=0$, and we can
define the RGBO norm of a variable random $X$ such that
$\|X\|_{\Psi_{\theta,L}}=\inf\\{\eta>0:\mathbb{E}\Psi_{\theta,L}(|X|/\eta)\leq
1\\}$. In contrast to the existent literature only care about heavy tail case
$\theta<1$, Lemma 6 provides the uniform optimal concentration in sense of
rate for any $\theta>0$ with explicit constants. Before stating this lemma, we
first give the equivalence of RGBO norm and concentration inequality stated as
follows.

######  Lemma 5.

For any zero-mean variable $X$ and $L>0$, we have

$\|X\|_{\Psi_{\theta,3^{1/\theta-1/2}L}}\leq\sqrt{3}\tau\,\Longleftrightarrow\,\mathbb{P}\left\\{|X|>\tau\big{(}\sqrt{t}+Lt^{(1/\theta)\vee
1}\big{)}\right\\}\leq 2\mathrm{e}^{-t},\text{ for any }\quad t\geq 0.$

###### Proof.

The proof is exactly the same as the proof of Lemma 1 and Lemma 2 in [44]. It
is worthy to note that the probability here can be rewritten as

$\mathbb{P}\left\\{|X|>\|X\|_{\Psi_{\theta,3^{1/\theta-1/2}L}}\Psi_{\theta,L}^{-1}(\mathrm{e}^{t}-1)/\sqrt{3}\right\\}\leq
2\mathrm{e}^{-t}$

for any $t\geq 0$ and hence

$\mathbb{P}\left\\{|X|\geq
s\|X\|_{\theta,K}\right\\}\leq\frac{2}{1+\Psi_{\theta,3^{1/2-1/\theta}K}(\sqrt{3}s)}$
(6)

for any $s\geq 0$. ∎

######  Lemma 6 (Sharper Sub-Weibull Concentrations).

Suppose $X_{i}-\mu\overset{\text{i.i.d.}}{\sim}\operatorname{subW}(\theta;C)$,
then for any $t\geq 0$,

$\big{\|}\mu-\overline{X}\big{\|}_{\Psi_{\theta,n^{-1/2}E(\theta)}}\leq
2n^{-1/2}\mathrm{e}^{-1}D(\theta)C,$

and

$\mathbb{P}\left\\{\big{|}\mu-\overline{X}\big{|}>2\mathrm{e}D(\theta)C\left(\sqrt{\frac{t}{n}}+E(\theta){\frac{t^{(1/\theta)\vee
1}}{n}}\right)\right\\}\leq 2\mathrm{e}^{-t},$

where $D(\theta)$ and $E(\theta)$ are defined as

$D(\theta)=\begin{cases}(\sqrt{2}\vee
2^{1/\theta})\sqrt{8}\mathrm{e}^{3}(2\pi)^{1/4}\mathrm{e}^{1/24}\left(\mathrm{e}^{2/\mathrm{e}}/\theta\right)^{1/\theta},&\text{
if }\theta<1,\\\ \sqrt{3/(2\mathrm{e}^{2})}\big{(}C^{-1}\vee
C^{\theta-1}\big{)},&\text{ if }1\leq\theta<2,\\\
\sqrt{17/(6\mathrm{e}^{2})}\big{(}C^{-1}\vee C^{\theta/2-1}\big{)},&\text{ if
}\theta\geq 2,\end{cases}$

and

$E(\theta)=\begin{cases}2^{2/\theta-1/2},&\text{ if }\theta<1,\\\
1/\sqrt{6},&\text{ if }1\leq\theta<2,\\\ 0,&\text{ if }\theta\geq 2.\\\
\end{cases}$

###### Proof.

We consider the case $\theta<1$, $1\leq\theta<2$, and $\theta\geq 2$
separately.

$\bullet$ If $\theta\geq 2$. From
$\mathbb{E}\exp\left\\{|X-\mu|^{\theta}/C^{\theta}\right\\}\leq 2$, we know
that

$\mathbb{E}\sum_{j=1}^{\infty}\frac{\left(|X-\mu|^{\theta}/C^{\theta}\right)^{j}}{j!}=\sum_{j=1}^{\infty}\frac{\mathbb{E}|X-\mu|^{j\theta}}{j!C^{j\theta}}\leq
1.$ (7)

This implies for any $k\in\mathbb{N}$, by $\theta\geq 2$,

$\displaystyle\mathbb{E}|X-\mu|^{2k}$ $\displaystyle\leq
1+\mathbb{E}|X-\mu|^{k\theta}$ $\displaystyle\overset{\text{by
\eqref{lem_sharper_sub_W_con_ineq_1}}}{\leq}1+k!C^{k\theta}$
$\displaystyle=1+k!(1\vee C^{\theta/2})^{2k}$ $\displaystyle\overset{\text{by
}k^{k}\times k!\leq(2k)!}{\leq}1+(1\vee
C^{\theta/2})^{2k}\times(2k-1)!!\frac{(2k)!!}{k^{k}}$
$\displaystyle\overset{\text{by Bohr–Mollerup theorem}}{\leq}1+(1\vee
C^{\theta/2})^{2k}\times(2k-1)!!\times\frac{2^{k}k!}{k^{k}}$
$\displaystyle\leq
1+(2k-1)!!\times\big{(}\sqrt{2}\vee\sqrt{2}C^{\theta/2}\big{)}^{2k}$
$\displaystyle\leq(2k-1)!!\times\big{(}2\vee 2C^{\theta/2}\big{)}^{2k}.$

Therefore, the sub-Gaussian intrinsic moment norm for $X-\mu$ satisfies
$\|X-\mu\|_{G}\leq 2\vee 2C^{\theta/2}$, and thus

$\mathbb{P}\left(\big{|}\mu-\overline{X}\big{|}>\big{(}2\vee
2C^{\theta/2}\big{)}\sqrt{\frac{17t}{6n}}\right)\leq\mathbb{P}\left(\big{|}\mu-\overline{X}\big{|}>\|X-\mu\|_{G}\sqrt{\frac{17t}{6n}}\right)\leq
2\mathrm{e}^{-t}$

for any $t\geq 0$ by Theorem 2(b) in [57].

$\bullet$ If $1\leq\theta<2$, (7) still holds for $\theta\in[1,2)$. We claim
there exist positive $\nu$ and $\kappa$ such that

$\mathbb{E}|X-\mu|^{k}\leq\frac{1}{2}\nu^{2}\kappa^{k-2}k!,\qquad
k=2,3,\ldots.$ (8)

Indeed, (7) together with $\theta\geq 1$ implies

$\mathbb{E}|X-\mu|^{k}\leq 1+\mathbb{E}|X-\mu|^{k\theta}\leq 1+k!C^{k\theta}$

Hence, a sufficient condition for (8) is
$1+k!C^{k\theta}\leq\frac{1}{2}\nu^{2}\kappa^{k-2}k!$ for any $k=2,3,\ldots$.
We rewrite this as

$\frac{\nu^{2}}{\kappa^{2}}\kappa^{k}\geq\frac{2}{k!}+2C^{k\theta},\qquad
k=2,3,\ldots.$

Therefore, we can take $\kappa=1\vee C^{\theta}$ and $\nu=\sqrt{3}\kappa$, and
then
$X_{i}-\mu\,\overset{\text{i.i.d.}}{\sim}\,\operatorname{sub\Gamma}(\nu,\kappa)$
by Lemma 2.2.11 in [43]. We can then apply concentration for sub-Gamma
distributions in Corollary 5.2 of [55, 11] and obtain that

$\mathbb{P}\left(\big{|}\mu-\overline{X}\big{|}>\sqrt{6}\big{(}1\vee
C^{\theta}\big{)}\sqrt{\frac{t}{n}}+\big{(}1\vee
C^{\theta}\big{)}\frac{t}{n}\right)=\mathbb{P}\left(\big{|}\mu-\overline{X}\big{|}>\sqrt{2}\nu\sqrt{\frac{t}{n}}+\kappa\frac{t}{n}\right)\leq
2\mathrm{e}^{-t}.$

$\bullet$ If $\theta<1$. Denote $\beta$ is the conjugate of $\theta$, i.e.,
$\beta=\infty$. Then from Theorem 1 in [56], we know that

$\mathbb{P}\left(\bigg{|}\sum_{i=1}^{n}a_{i}(\mu-X_{i})\bigg{|}\geq
2\mathrm{e}D(\theta)\|b\|_{2}\sqrt{t}+2\mathrm{e}L_{n}^{*}(\theta)t^{1/\theta}\|b\|_{\beta}\right)\leq
2\mathrm{e}^{-t}$

where $b=n^{-1}C1_{n}\in\mathbb{R}^{n}$ with $\|b\|_{2}=Cn^{-1/2}$,
$\|b\|_{\beta}=Cn^{-1}$, and $D(\theta)=(\sqrt{2}\vee
2^{1/\theta})\sqrt{8}\mathrm{e}^{3}(2\pi)^{1/4}\mathrm{e}^{1/24}\left(\mathrm{e}^{2/\mathrm{e}}/\theta\right)^{1/\theta}$,
and $L_{n}^{*}(\theta)=L_{n}(\theta)D(\theta)\|b\|_{2}/\|b\|_{\beta}$ with
$L_{n}(\theta):=\frac{4^{1/\theta}\|b\|_{\beta}}{\sqrt{2}\|b\|_{2}}$. Then we
have

$\displaystyle
2\mathrm{e}D(\theta)\|b\|_{2}\sqrt{t}+2\mathrm{e}L_{n}^{*}(\theta)t^{1/\theta}\|b\|_{\beta}=2\mathrm{e}D(\theta)C\left(\sqrt{\frac{t}{n}}+E(\theta)\frac{t^{1/\theta}}{n}\right)$

where $E(\theta)=\frac{4^{1/\theta}}{\sqrt{2}}=2^{\frac{4-\theta}{2\theta}}$.
Combining these results, we obtain the concentration inequality in the lemma.
For the result of the RGBO norm, we just use the lemma 5. ∎

Lemma 6 establishes a uniform result for the sample mean of i.i.d. sub-Weibull
random variables. It is important to note that our result here is sharper than
those in [30] and [56], especially for the case when $\theta\geq 1$, as they
focus on general weighted summations. Another notable difference is in
comparison to the sub-Weibull concentration results for sample means in [2],
[10], and [20], which require symmetry, while our approach does not.
Consequently, we present a novel concentration result for the sample mean of
i.i.d. sub-Weibull random variables.

Next, we will show some anti-concentrations for the posterior distributions in
Algorithm 3, which are essential for the proof of TS-type algorithms.

######  Lemma 7.

For any $0\leq x\leq\frac{\beta}{\alpha+\beta}$, we have

$\mathbb{P}\left(\operatorname{Beta}(\alpha,\beta)>\frac{\alpha}{\alpha+\beta}+x\right)\geq\frac{\Gamma(\beta+\alpha)}{\beta\Gamma(\beta)\Gamma(\alpha)}\left(\frac{\beta}{\alpha+\beta}-x\right)^{\beta}\left(\frac{\alpha}{\alpha+\beta}+x\right)^{\alpha}\left(\frac{\beta+2}{\beta+1}-\frac{\alpha+\beta}{\beta+1}x\right).$

###### Proof.

First, we note that
$\operatorname{Beta}(\alpha,\beta)=1-\operatorname{Beta}(\beta,\alpha)$. Then
we can rewrite the probability as

$\displaystyle\mathbb{P}\left(\operatorname{Beta}(\alpha,\beta)>\frac{\alpha}{\alpha+\beta}+x\right)$
$\displaystyle=$
$\displaystyle\mathbb{P}\left(1-\operatorname{Beta}(\beta,\alpha)>\frac{\alpha}{\alpha+\beta}+x\right)$
$\displaystyle=$
$\displaystyle\mathbb{P}\left(\operatorname{Beta}(\beta,\alpha)\leq
1-\frac{\alpha}{\alpha+\beta}-x\right)$ $\displaystyle\overset{\text{by
Theorem 1 in
\cite[citep]{[\@@bibref{Number}{HENZI2023109783}{}{}]}}}{\geq}\frac{\Gamma(\beta+\alpha)}{\beta\Gamma(\beta)\Gamma(\alpha)}\left(1-\frac{\alpha}{\alpha+\beta}-x\right)^{\beta}\left(\frac{\alpha}{\alpha+\beta}+x\right)^{\alpha}\left[1+\frac{\beta+\alpha}{\beta+1}\left(1-\frac{\alpha}{\alpha+\beta}-x\right)\right]$
$\displaystyle=$
$\displaystyle\frac{\Gamma(\beta+\alpha)}{\beta\Gamma(\beta)\Gamma(\alpha)}\left(\frac{\beta}{\alpha+\beta}-x\right)^{\beta}\left(\frac{\alpha}{\alpha+\beta}+x\right)^{\alpha}\left(\frac{\beta+2}{\beta+1}-\frac{\alpha+\beta}{\beta+1}x\right).$

∎

######  Lemma 8.

Suppose $\xi\sim\mathcal{N}(\mu,\sigma^{2})$ and
$\zeta\sim\operatorname{Beta}(\alpha,\beta)$, then

$\displaystyle\mathbb{P}\left(\xi\times\zeta\geq\frac{\alpha\mu}{\alpha+\beta}+x\right)$
$\displaystyle\geq$
$\displaystyle\left\\{\begin{array}[]{ll}\frac{1}{2}c(\alpha,\beta),&\text{if
}x\leq\frac{\mu\beta}{2(\alpha+\beta)},\\\
\frac{(2\alpha+\beta)\sigma}{\sqrt{2\pi}}\frac{2(\alpha+\beta)x-\mu\beta}{\left[2(\alpha+\beta)x-\mu\beta\right]^{2}+(2\alpha+\beta)^{2}\sigma^{2}}\exp\left\\{-\frac{1}{2}\left(\frac{2(\alpha+\beta)x-\mu\beta}{(2\alpha+\beta)\sigma}\right)^{2}\right\\},&\text{if
}x>\frac{\mu\beta}{2(\alpha+\beta)},\end{array}\right.$

where

$c(\alpha,\beta)=\frac{\Gamma(\beta+\alpha)}{\beta\Gamma(\beta)\Gamma(\alpha)}\left[\frac{\beta}{2(\alpha+\beta)}\right]^{\beta}\left[\frac{2\alpha+\beta}{2(\alpha+\beta)}\right]^{\alpha}\left[\frac{\beta+4}{2(\beta+1)}\right].$

###### Proof.

First, we note that

$\displaystyle\mathbb{P}\left(\xi\times\zeta\geq\frac{\alpha\mu}{\alpha+\beta}+x\right)$
$\displaystyle=\mathbb{P}\left(\xi\times\zeta\geq\left(\mu+y\right)\left(\frac{\alpha}{\alpha+\beta}+z\right)\right)$
$\displaystyle\geq\mathbb{P}\left(\xi\geq\mu+y\right)\times\mathbb{P}\left(\zeta\geq\frac{\alpha}{\alpha+\beta}+z\right)$

with $y,z$ defined as

$y=\frac{2(\alpha+\beta)x-\mu\beta}{2\alpha+\beta},\qquad
z=\frac{\beta}{2(\alpha+\beta)}.$

From Lemma 7, we obtain

$\displaystyle\mathbb{P}\left(\zeta\geq\frac{\alpha}{\alpha+\beta}+z\right)$
$\displaystyle\geq\frac{\Gamma(\beta+\alpha)}{\beta\Gamma(\beta)\Gamma(\alpha)}\left(\frac{\beta}{\alpha+\beta}-z\right)^{\beta}\left(\frac{\alpha}{\alpha+\beta}+z\right)^{\alpha}\left(\frac{\beta+2}{\beta+1}-\frac{\alpha+\beta}{\beta+1}z\right)$
$\displaystyle=\frac{\Gamma(\beta+\alpha)}{\beta\Gamma(\beta)\Gamma(\alpha)}\left[\frac{\beta}{2(\alpha+\beta)}\right]^{\beta}\left[\frac{2\alpha+\beta}{2(\alpha+\beta)}\right]^{\alpha}\left[\frac{\beta+4}{2(\beta+1)}\right]=c(\alpha,\beta)$

with $c(\alpha,\beta)$ is a constant only depending on $\alpha$ and $\beta$.
If $y\leq 0$, i.e., $x\leq\frac{\mu\beta}{2(\alpha+\beta)}$, then
$\mathbb{P}\left(\xi\geq\mu+y\right)\geq\frac{1}{2}$, and thus

$\displaystyle\mathbb{P}\left(\xi\times\zeta\geq\frac{\alpha\mu}{\alpha+\beta}+x\right)\geq\frac{c(\alpha,\beta)}{2}.$

If $y>0$, i.e., $x>\frac{\mu\beta}{2(\alpha+\beta)}$, then by [1],

$\displaystyle\mathbb{P}\left(\xi\geq\mu+y\right)$
$\displaystyle=\mathbb{P}\left(\xi\geq\mu+\sigma\frac{2(\alpha+\beta)x-\mu\beta}{(2\alpha+\beta)\sigma}\right)$
$\displaystyle\geq\frac{1}{\sqrt{2\pi}}\frac{\frac{2(\alpha+\beta)x-\mu\beta}{(2\alpha+\beta)\sigma}}{\left(\frac{2(\alpha+\beta)x-\mu\beta}{(2\alpha+\beta)\sigma}\right)^{2}+1}\exp\left\\{-\frac{1}{2}\left(\frac{2(\alpha+\beta)x-\mu\beta}{(2\alpha+\beta)\sigma}\right)^{2}\right\\}$
$\displaystyle=\frac{(2\alpha+\beta)\sigma}{\sqrt{2\pi}}\frac{2(\alpha+\beta)x-\mu\beta}{\left[2(\alpha+\beta)x-\mu\beta\right]^{2}+(2\alpha+\beta)^{2}\sigma^{2}}\exp\left\\{-\frac{1}{2}\left(\frac{2(\alpha+\beta)x-\mu\beta}{(2\alpha+\beta)\sigma}\right)^{2}\right\\},$

which leads to the final result. ∎

The remaining part of this section will consist of the proofs of the lemmas
presented in the main content.

Proof of Lemma 3:

###### Proof.

From the definition of sub-Weibull distribution, we know that
$\mathbb{E}\exp\\{|X-\mu|^{\theta}/C_{X}^{\theta}\\}\leq 2$. Note that for any
$a,b\geq 0$: if $0\leq\theta\leq 1$, $(a+b)^{\theta}\leq
a^{\theta}+b^{\theta}$; if $\theta>1$, $(a+b)^{\theta}\leq
2^{\theta-1}(a^{\theta}+b^{\theta})$. Hence,

$(a+b)^{\theta}\leq\big{(}2^{\theta-1}\,\vee\,1\big{)}(a^{\theta}+b^{\theta}).$

Thus, for any $C>0$, we have

$\displaystyle\mathbb{E}\exp\\{|R-\mu p|^{\theta}/C^{\theta}\\}$
$\displaystyle=\mathbb{E}\exp\big{\\{}\big{|}(X-\mu)Y+\mu(Y-p)\big{|}^{\theta}/C^{\theta}\big{\\}}$
$\displaystyle\leq\mathbb{E}\exp\big{\\{}\big{(}|X-\mu|Y+\mu|Y-p|\big{)}^{\theta}/C^{\theta}\big{\\}}$
$\displaystyle\leq\mathbb{E}\exp\big{\\{}\big{(}2^{\theta-1}\,\vee\,1\big{)}\big{(}|X-\mu|^{\theta}Y^{\theta}+\mu^{\theta}|Y-p|^{\theta}\big{)}/C^{\theta}\big{\\}}$
$\displaystyle\leq\mathbb{E}\exp\big{\\{}\big{(}2^{\theta-1}\,\vee\,1\big{)}\big{(}|X-\mu|^{\theta}+\mu^{\theta}(p^{\theta}+(1-p)^{\theta})\big{)}/C^{\theta}\big{\\}}$
$\displaystyle=\exp\big{\\{}\big{(}2^{\theta-1}\,\vee\,1\big{)}\mu^{\theta}(p^{\theta}+(1-p)^{\theta})\big{)}/C^{\theta}\big{\\}}\mathbb{E}\exp\big{\\{}\big{(}2^{\theta-1}\,\vee\,1\big{)}|X-\mu|^{\theta}/C^{\theta}\big{\\}}.$

Since $\mathbb{E}\exp\\{|X-\mu|^{\theta}/C_{X}^{\theta}\\}\leq 2$, we have

$\displaystyle 0$
$\displaystyle\leq\lim_{C\,\uparrow\,+\infty}\mathbb{E}\exp\\{|R-\mu
p|^{\theta}/C^{\theta}\\}$
$\displaystyle\leq\lim_{C\,\uparrow\,+\infty}\exp\big{\\{}\big{(}2^{\theta-1}\,\vee\,1\big{)}\mu^{\theta}(p^{\theta}+(1-p)^{\theta})\big{)}/C^{\theta}\big{\\}}\lim_{C_{X}\leq
C\,\uparrow\,+\infty}\mathbb{E}\exp\big{\\{}\big{(}2^{\theta-1}\,\vee\,1\big{)}|X-\mu|^{\theta}/C^{\theta}\big{\\}}$
$\displaystyle=0.$

This implies there exists $C_{R}\geq C_{X}$ such that $\mathbb{E}\exp\\{|R-\mu
p|^{\theta}/C_{R}^{\theta}\\}\leq 2$. ∎

Proof of Lemma 4:

###### Proof.

The result that $R-\mu p$ is sub-Gaussian or sub-Exponential in the lemma
directly comes from Lemma 3 by setting $\theta=2$ and $\theta=1$. For the
second result, we first prove the results for sub-Gaussian case. Denote that
$\tau^{2}$ as the minimal value which satisfies

$\mathbb{E}\exp\\{s(R-\mu p)\\}\leq\exp\\{s^{2}\tau^{2}/2\\}$

for any $s\in\mathbb{R}$. By the definition, we have

$\displaystyle\mathbb{E}\exp\\{s(R-\mu p)\\}$
$\displaystyle=\mathbb{E}\exp\\{s(XY-\mu p)\\}$
$\displaystyle=\mathbb{E}\exp\\{s(0-\mu
p)\\}\mathbb{P}(Y=0)+\mathbb{E}\exp\\{s(X-\mu p)\\}\mathbb{P}(Y=1)$
$\displaystyle=\mathrm{e}^{-s\mu p}(1-p+p\mathbb{E}\mathrm{e}^{sX}).$

Since $\sigma^{2}$ is the minimal value such that
$\mathbb{E}\exp\\{s(X-\mu)\\}\leq\exp\\{s^{2}\sigma^{2}/2\\}$ for all
$s\in\mathbb{R}$, it also is the minimal value such that
$\mathbb{E}\mathrm{e}^{sX}\leq\mathrm{e}^{s\mu+s^{2}\sigma^{2}/2}$. This
indicates $\tau^{2}$ satisfies

$\mathrm{e}^{-s\mu
p}(1-p+p\mathrm{e}^{s\mu+s^{2}\sigma^{2}/2})\leq\exp\\{s^{2}\tau^{2}/2\\},$

i.e.,

$\displaystyle\tau^{2}$
$\displaystyle=\max_{s\in\mathbb{R}}\frac{2}{s^{2}}\left[-s\mu
p+\log(1-p+p\mathrm{e}^{s\mu+s^{2}\sigma^{2}/2})\right].$

Denote

$f(s,\mu,p,\sigma^{2}):=\frac{2}{s^{2}}\left[-s\mu
p+\log(1-p+p\mathrm{e}^{s\mu+s^{2}\sigma^{2}/2})\right]$

with
$\tau^{2}=\max_{s\in\mathbb{R}}f(s,\mu,p,\sigma^{2})=f(s_{*},\mu,p,\sigma^{2})$.
We will first show that

$\forall\,\mu>0,\quad\lim_{p\,\downarrow\,0}s_{*}=+\infty\quad\text{ and
}\quad\quad\lim_{|\mu|\vee\sigma^{2}\,\downarrow\,0}\lim_{p\,\uparrow\,1}s_{*}=0+.$

Indeed, $s_{*}$ satisfies $\frac{\partial}{\partial
s}f(s,\mu,p,\sigma^{2})=0$, i.e.,

$\frac{2\mu
p}{s_{*}^{2}}-\frac{4}{s_{*}^{3}}\log(1-p+p\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2})+\frac{2}{s_{*}^{2}}\frac{p(\mu+\sigma^{2}s_{*})}{p+(1-p)\mathrm{e}^{-s_{*}\mu-
s_{*}^{2}\sigma^{2}/2}}=0,$

or say,

$\frac{2}{p}\log(1-p+p\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2})=s_{*}\left[\frac{(\mu+\sigma^{2}s_{*})}{p+(1-p)\mathrm{e}^{-s_{*}\mu-
s_{*}^{2}\sigma^{2}/2}}+\mu\right].$

As we can see whenever $s_{*}$ is finite, we have
$\lim_{p\,\downarrow\,0}\frac{2}{p}\log(1-p+p\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2})=+\infty$,
then there must be $\lim_{p\,\downarrow\,0}s_{*}=+\infty$ since $\mu>0$. On
the other hand, by letting $p=1$, the above equation becomes

$\log(1+\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2})=s_{*}\mu+s_{*}^{2}\sigma^{2}/2.$

Since $\lim_{x\rightarrow-\infty}\log(1+\mathrm{e}^{x})-x=+\infty$,
$\lim_{x\rightarrow 0}\log(1+\mathrm{e}^{x})-x=\log 2$, we must have
$\lim_{|\mu|\vee\sigma^{2}\,\downarrow\,0}\lim_{p\,\uparrow\,1}s_{*}=0+$. Now,
consider

$\displaystyle\frac{\tau^{2}}{\sigma^{2}}$
$\displaystyle=\frac{2}{s_{*}^{2}\sigma^{2}}\left[-s_{*}\mu
p+\log(1-p+p\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2})\right]$
$\displaystyle=\frac{p}{p+(1-p)\mathrm{e}^{-s_{*}\mu-
s_{*}^{2}\sigma^{2}/2}}+\frac{\mu(1-p)p}{s\sigma^{2}}\frac{\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2}+1}{p\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2}+1-p}$

Then consider $\mu>0$, by taking $p=1/2$, and denote
$\overline{s}=s_{*}(p=1/2,\mu,\sigma^{2})$ we get that

$\displaystyle\left.\frac{\tau^{2}}{\sigma^{2}}\right|_{p=1/2}$
$\displaystyle=\frac{1}{1+\mathrm{e}^{-\overline{s}\mu-\overline{s}^{2}\sigma^{2}/2}}+\frac{\mu}{2\overline{s}\sigma^{2}}\geq\frac{\mu}{2\overline{s}\sigma^{2}}.$

By the inequality $x-\log 2\leq\log\left(\frac{1+\mathrm{e}^{x}}{2}\right)\leq
x$, then $\overline{s}\in(0,\infty)$ satisfies

$\displaystyle\overline{s}\left[\frac{2(\mu+\sigma^{2}\overline{s})}{1+\mathrm{e}^{-\overline{s}\mu-\overline{s}^{2}\sigma^{2}/2}}+\mu\right]$
$\displaystyle=$ $\displaystyle
4\log\left[\frac{1}{2}(1+\mathrm{e}^{\overline{s}\mu+\overline{s}^{2}\sigma^{2}/2})\right]\in\left[4\overline{s}\mu+2\overline{s}^{2}\sigma^{2}-\log
2,\,4\overline{s}\mu+2\overline{s}^{2}\sigma^{2}\right].$

The left hand of the above equation with respect to $\mu>0$ is at most
$3\mu\overline{s}$, while the right hand is at least $4\mu\overline{s}$. This
implies $\lim_{\mu\rightarrow+\infty}\overline{s}=0$, and thus

$\lim_{\mu\rightarrow+\infty}\left.\frac{\tau^{2}}{\sigma^{2}}\right|_{p=1/2}\geq\lim_{\mu\rightarrow+\infty}\frac{\mu}{2\overline{s}\sigma^{2}}=+\infty.$

which concludes the results in (i). Then we will prove the results in (iii).
By envelope theorem,

$\displaystyle\frac{\partial\tau^{2}}{\partial p}$
$\displaystyle=\left.\frac{\partial}{\partial
p}f(s,\mu,p,\sigma^{2})\right|_{s=s^{*}}=\frac{2}{s_{*}^{2}}\left[-s_{*}\mu+\frac{\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2}-1}{1+p\left(\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2}-1\right)}\right].$

The fact that $\frac{\mathrm{e}^{x}}{1+\mathrm{e}^{x}}$ is bounded on
$x\in[0,\infty)$ and the fact
$\lim_{|\mu|\vee\sigma^{2}\,\downarrow\,0}\lim_{p\,\uparrow\,1}s_{*}=0+$
ensure that

$\lim_{|\mu|\vee\sigma^{2}\,\downarrow\,0}\lim_{p\,\uparrow\,1}\frac{\partial\tau^{2}}{\partial
p}=\lim_{|\mu|\vee\sigma^{2}\,\downarrow\,0}\lim_{p\,\uparrow\,1}\frac{2}{s_{*}^{2}}\left[-s_{*}\mu+1\right]=+\infty.$

By the continuity of $f(s^{*},\cdot,\cdot,\cdot)$ on $\mu,p$, and
$\sigma^{2}$, we get the first two results in (iii). Similarly, we can show
that

$\displaystyle\frac{\partial\tau^{2}}{\partial\mu}$
$\displaystyle=\frac{2}{s_{*}}\left[-p+\frac{p\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2}}{1+p\left(\mathrm{e}^{s_{*}\mu+s_{*}^{2}\sigma^{2}/2}-1\right)}\right],$

which ensures
$\lim_{\sigma^{2}\,\downarrow\,0}\lim_{p\,\uparrow\,1}\frac{\partial\tau^{2}}{\partial\mu}=+\infty$
the last result in (iii). Finally, for the result in (ii), we note that

$\operatorname{var}(R)=\mathbb{E}\big{[}(XY-\mu
p)^{2}\big{]}=p\operatorname{var}(X)+p(1-p)\mu^{2}.$

Then by $\sigma^{2}\geq\operatorname{var}(X)$, we have

$\frac{\tau^{2}}{\operatorname{var}(R)}=\frac{\tau^{2}}{p\operatorname{var}(X)+p(1-p)\mu^{2}}\geq\frac{\tau^{2}}{p\sigma^{2}+p(1-p)\mu^{2}}.$

Take $\mu=c\mu_{*}$ with arbitrary $c>1$, by letting
$\sigma^{2}\,\downarrow\,0$ and $p\,\uparrow\,1$, we have

$\displaystyle\left.\frac{\tau^{2}}{\operatorname{var}(R)}\right|_{\mu=c\mu_{*}}$
$\displaystyle\geq\left.\frac{\tau^{2}}{p\sigma^{2}+p(1-p)\mu^{2}}\right|_{\mu=c\mu_{*}}$
$\displaystyle\overset{\tau^{2}|_{\mu=\mu^{*}}>0}{\geq}\frac{\min_{\mu^{\prime}\in[\mu_{*},c\mu_{*}]}\left.\frac{\partial\tau^{2}}{\partial\mu}\right|_{\mu=\mu^{\prime}}(c\mu_{*}-\mu_{*})}{p\sigma^{2}+p(1-p)c^{2}\mu_{*}^{2}}$
$\displaystyle\overset{\text{by the result in (iii)
(c)}}{\geq}\frac{(c-1)M\mu_{*}}{p\sigma^{2}+p(1-p)c^{2}\mu_{*}^{2}}\,\uparrow\,+\infty$

which gives the result in (ii). For the case that
$X-\mu\sim\operatorname{subE}(\lambda)$, one only need to note that the sub-
Exponential parameter $\alpha$ for $R-\mu p$ satisfies

$\mathrm{e}^{-s\mu
p}(1-p+p\mathrm{e}^{s\mu+s^{2}\lambda^{2}/2})\leq\exp\\{s^{2}\alpha^{2}/2\\}$

for any $s\leq\frac{1}{\lambda}$, which implies

$\alpha^{2}=\lambda^{2}\vee\max_{s\in\mathbb{R}}\frac{2}{s^{2}}\left[-s\mu
p+\log(1-p+p\mathrm{e}^{s\mu+s^{2}\lambda^{2}/2})\right].$

Since $\lambda^{2}\vee g(\lambda,\mu,p)$ with differential
$g(\cdot,\cdot,\cdot)$ is also differential on its domain except the points
that $\lambda^{2}=g(\lambda,\mu,p)$, the above results regarding large values
will still hold. Thus, we finish the proof. ∎

Proof of Lemma 1:

###### Proof.

Denote $B\sim\operatorname{binomial}(n;p)$ independent with
$\\{X_{i}\\}_{i=1}^{n}$, we consider the positive $p/2>0$, by concentration
for Bernoulli, we have

$\displaystyle\mathbb{P}(B\geq pn/2)$
$\displaystyle=1-\mathbb{P}(p-\overline{B}\geq p/2)$ $\displaystyle\geq
1-\exp\big{[}-np^{2}/4\big{]}.$

Given any $\delta$, the above inequality ensures

$B\geq pn/2$

with probability at least $1-\delta/2$ for any
$n\geq\frac{4}{p^{2}}\log(2/\delta)$. Now, denote $X_{k}$ as the observed
$X_{i}$. Consider $t>0$ which will be determined later,

$\displaystyle\mathbb{P}\left\\{\big{|}\mu-\overline{X}^{*}\big{|}>2\mathrm{e}D(\theta)C_{X}\left(\sqrt{\frac{t}{np/2}}+E(\theta)\frac{t^{(1/\theta)\vee
1}}{np/2}\right)\right\\}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{B}\left[\mathbb{P}_{X}\left\\{\bigg{|}\mu-\frac{1}{B}\sum_{k=1}^{B}X_{k}\bigg{|}>2\mathrm{e}D(\theta)C_{X}\left(\sqrt{\frac{t}{np/2}}+E(\theta)\frac{t^{(1/\theta)\vee
1}}{np/2}\right)\right\\}\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\left[\mathbb{P}_{X}\left\\{\bigg{|}\mu-\frac{1}{B}\sum_{k=1}^{B}X_{k}\bigg{|}>2\mathrm{e}D(\theta)C_{X}\left(\sqrt{\frac{t}{np/2}}+E(\theta)\frac{t^{(1/\theta)\vee
1}}{np/2}\right),B\geq np/2\right\\}\right]+\frac{\delta}{2}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\left[\mathbb{P}_{X}\left\\{\bigg{|}\mu-\frac{1}{B}\sum_{k=1}^{B}X_{k}\bigg{|}>2\mathrm{e}D(\theta)C_{X}\left(\sqrt{\frac{t}{B}}+E(\theta)\frac{t^{(1/\theta)\vee
1}}{B}\right)\right\\}\right]+\frac{\delta}{2}$ $\displaystyle\leq$
$\displaystyle 2\mathrm{e}^{-t}+\frac{\delta}{2},$

where the last step is by Lemma 6. Finally, by letting
$2\mathrm{e}^{-t}=\delta/2$, we conclude the inequality in the lemma. ∎

Proof of Lemma 2:

###### Proof.

Denote

$M_{k}=\left(\frac{kM}{\log z}\right)^{\frac{1}{1+\epsilon}}$

with $z$ will be determined later. The proof idea comes from Lemma 1 in [12].
Denote $X_{k}$ as the observed $X_{i}$. Consider

$\displaystyle\mathbb{P}\big{(}\mu-\overline{X}^{**}>t\big{)}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{B}\left[\mathbb{P}_{X}\left(\mu-\frac{1}{B}\sum_{k=1}^{B}X_{k}\mathds{1}(|X_{k}|\leq
M_{k})>t\right)\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\Bigg{[}\mathbb{P}_{X}\bigg{(}\frac{1}{B}\sum_{k=1}^{B}\mathbb{E}X\mathds{1}(|X|>M_{k})+\frac{1}{B}\sum_{k=1}^{B}\Big{[}\mathbb{E}X\mathds{1}(|X|\leq
M_{k})-X_{k}\mathds{1}(|X_{k}|\leq M_{k})\Big{]}>t\bigg{)}\Bigg{]}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\Bigg{[}\mathbb{P}_{X}\bigg{(}\frac{1}{B}\sum_{k=1}^{B}\frac{M}{M_{k}^{\epsilon}}+\frac{1}{B}\sum_{k=1}^{B}\Big{[}\mathbb{E}X\mathds{1}(|X|\leq
M_{k})-X_{k}\mathds{1}(|X_{k}|\leq M_{k})\Big{]}>t\bigg{)}\Bigg{]}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\Bigg{[}\mathbb{P}_{X}\bigg{(}\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{B^{\frac{\epsilon}{1+\epsilon}}}+\frac{1}{B}\sum_{k=1}^{B}\Big{[}\mathbb{E}X\mathds{1}(|X|\leq
M_{k})-X_{k}\mathds{1}(|X_{k}|\leq M_{k})\Big{]}>t\bigg{)}\Bigg{]}$

where $B=\sum_{i=1}^{n}Y_{i}\sim\operatorname{binomial}(n;p)$ is independent
with $\\{X_{i}\\}_{i=1}^{n}$. The last inequality is using

$\displaystyle\frac{1}{B}\sum_{k=1}^{B}\frac{M}{M_{k}^{\epsilon}}$
$\displaystyle=M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z\frac{1}{B}\sum_{k=1}^{B}t^{-\frac{\epsilon}{1+\epsilon}}$
$\displaystyle\leq
M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z\frac{1}{B}\int_{0}^{B}t^{-\frac{\epsilon}{1+\epsilon}}\,\mathrm{t}$
$\displaystyle=(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z\times
B^{-\frac{\epsilon}{1+\epsilon}}.$

Next, we consider the positive $p/2>0$, by concentration for Bernoulli, we
have

$\displaystyle\mathbb{P}(B\geq pn/2)$
$\displaystyle=1-\mathbb{P}(p-\overline{B}\geq p/2)$ $\displaystyle\geq
1-\exp\big{[}-np^{2}/4\big{]}.$

Given any $\delta$, the above inequality ensures

$B\geq pn/2$

with probability at least $1-\delta/2$ for any
$n\geq\frac{4}{p^{2}}\log(2/\delta)$. Then by Bernstein’s inequality

$\displaystyle\mathbb{P}\big{(}\mu-\overline{X}^{**}>t\big{)}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\Bigg{[}\mathbb{P}_{X}\bigg{(}\frac{1}{B}\sum_{k=1}^{B}\Big{[}\mathbb{E}X\mathds{1}(|X|\leq
M_{k})-X_{k}\mathds{1}(|X_{k}|\leq
M_{k})\Big{]}>t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{B^{\frac{\epsilon}{1+\epsilon}}}\bigg{)}\Bigg{]}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\Bigg{[}\mathbb{P}_{X}\bigg{(}\frac{1}{B}\sum_{k=1}^{B}\Big{[}\mathbb{E}X\mathds{1}(|X|\leq
M_{k})-X_{k}\mathds{1}(|X_{k}|\leq
M_{k})\Big{]}>t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{B^{\frac{\epsilon}{1+\epsilon}}},B\geq
pn/2\bigg{)}\Bigg{]}+\frac{\delta}{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\Bigg{[}\mathbb{P}_{X}\bigg{(}\frac{1}{B}\sum_{k=1}^{B}\Big{[}\mathbb{E}X\mathds{1}(|X|\leq
M_{k})-X_{k}\mathds{1}(|X_{k}|\leq
M_{k})\Big{]}>t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{(pn/2)^{\frac{\epsilon}{1+\epsilon}}},B\geq
pn/2\bigg{)}\Bigg{]}+\frac{\delta}{2}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{B}\Bigg{[}\exp\left(-\frac{B\left(t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{(pn/2)^{\frac{\epsilon}{1+\epsilon}}}\right)^{2}/2}{MM_{k}^{1-\epsilon}+M_{k}\left(t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{(pn/2)^{\frac{\epsilon}{1+\epsilon}}}\right)/3}\right)\mathds{1}(B\geq
pn/2)\Bigg{]}+\frac{\delta}{2}$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{pn\left(t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{(pn/2)^{\frac{\epsilon}{1+\epsilon}}}\right)^{2}/4}{MM_{n}^{1-\epsilon}+M_{n}\left(t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{(pn/2)^{\frac{\epsilon}{1+\epsilon}}}\right)/3}\right)+\frac{\delta}{2}$

By letting

$t-\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}z}{(pn/2)^{\frac{\epsilon}{1+\epsilon}}}=\frac{4\log(2/\delta)}{3pn}M_{n}+\sqrt{\frac{4MM_{n}^{1-\epsilon}\log(2/\delta)}{pn}},$

by
$\frac{t^{2}/2}{\sigma^{2}+Mt/3}=\frac{A}{n}\,\Longleftrightarrow\,t=\frac{AM}{3n}\pm\sqrt{\frac{A^{2}M^{2}}{9n^{2}}+\frac{2A\sigma^{2}}{n}}\leq\frac{2AM}{3n}+\sqrt{\frac{2A\sigma^{2}}{n}}$.
Let $z=\log(2/\delta)$, we have

$\displaystyle t$
$\displaystyle=\frac{(1+\epsilon)M^{\frac{1}{1+\epsilon}}\log^{\frac{\epsilon}{1+\epsilon}}(2/\delta)}{(pn/2)^{\frac{\epsilon}{1+\epsilon}}}+\frac{4\log(2/\delta)}{3pn}M_{n}+\sqrt{\frac{4MM_{n}^{1-\epsilon}\log(2/\delta)}{pn}}$
$\displaystyle=\frac{(1+\epsilon)2^{\frac{\epsilon}{1+\epsilon}}M^{\frac{1}{1+\epsilon}}}{p^{\frac{\epsilon}{1+\epsilon}}}\left(\frac{\log(2/\delta)}{n}\right)^{\frac{\epsilon}{1+\epsilon}}+\frac{4M^{\frac{1}{1+\epsilon}}}{3p}\left(\frac{\log(2/\delta)}{n}\right)^{\frac{\epsilon}{1+\epsilon}}+\frac{2M^{\frac{1}{1+\epsilon}}}{\sqrt{p}}\left(\frac{\log(2/\delta)}{n}\right)^{\frac{\epsilon}{1+\epsilon}}$
$\displaystyle=\left[\frac{(1+\epsilon)2^{\frac{\epsilon}{1+\epsilon}}}{p^{\frac{\epsilon}{1+\epsilon}}}+\frac{4}{3p}+\frac{2}{\sqrt{p}}\right]M^{\frac{1}{1+\epsilon}}\left(\frac{\log(2/\delta)}{n}\right)^{\frac{\epsilon}{1+\epsilon}},$

which leads to the result. ∎

##  Appendix C C Proof of the regrets for UCB-type algorithms

The proofs for our UCB-type algorithms also follow the standard approach used
in UCB algorithms, which involves controlling two probabilities. The first
probability relates to the underestimation of the optimal arm, characterized
by $\mathbb{P}(U_{1}^{\mu}(t)\times U_{1}^{p}(t)<r_{1})$, and this can be
easily managed using the concentration results presented in Section 4.1. The
second probability concerns the overestimation of suboptimal arms,
characterized by $\mathbb{P}(U_{k}^{\mu}(t)\times
U_{k}^{p}(t)>r_{1})=\mathbb{P}(U_{k}^{\mu}(t)\times
U_{k}^{p}(t)>r_{k}+\Delta_{k})$. Since $\Delta_{k}>0$, the sharp properties of
our concentration results in Section 4.1 also controls this probability,
ensuring an exponential decay rate over rounds.

###  C.1 Proof of Theorem 1

###### Proof.

For any $\delta>0$, denote the upper confidence bound for $p_{k}$ until round
$t$ as
$U_{k}^{p}(t,\delta):=\widehat{p}_{k}(t)+\sqrt{\frac{\log(2/\delta)}{2c_{k}(t)}}$,
with $\widehat{p}_{k}(t)$ be the point estimate at round $t$. Based on the
estimated $\widehat{p}_{k}(t)$ , define the upper confidence bound for
$\mu_{k}$ as

$U_{k}^{\mu}(t,\delta):=\widehat{\mu}_{k}(t)+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{c_{k}(t)\widehat{p}_{k}(t)/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{c_{k}(t)\widehat{p}_{k}(t)/2}\right)$

with $\widehat{\mu}_{k}(t)$ be the point estimate again. For simplicity, we
also denote $\widehat{p}_{k}(t)$ as $\widehat{p}_{k,m}$ when $c_{k}(t)=m$, and
similarly define $\widehat{\mu}_{k,m}$. Similarly, we denote
$U_{k}^{p}(t,\delta)$ as $U^{p}_{k,m}(\delta)$ when $c_{k}(t)=m$, and
similarly define $U_{k,m}^{\mu}(\delta)$.

Now we can define good events as follows

$\mathcal{G}^{0}:=\\{r_{1}<\min_{t\in\\{m_{1},m_{1}+1\ldots,T\\}}U_{1,m_{1}}^{\mu}(\delta)\times
U_{1,m_{1}}^{p}(\delta)\\}$

and

$\mathcal{G}_{k}^{r}=\\{U_{k,m_{k}}^{\mu}(\delta)\times
U_{k,m_{k}}^{p}(\delta)<r_{1}\\}.$

Furthermore, define
$\mathcal{G}_{k}^{p}=\\{\widehat{p}_{k,m_{k}}>p_{k}-\epsilon_{k}\\}$ for
$k\in[K]$ and
$\mathcal{G}_{k}=\mathcal{G}^{0}\,\cap\,\mathcal{G}_{k}^{r}\,\cap\,\mathcal{G}_{1}^{p}\,\cap\,\mathcal{G}_{k}^{p}$
for $k\neq 1$, where $\epsilon_{k}$ will be determined later.

Step 1: For bounding $\mathbb{P}(\mathcal{G}_{k}^{c})$, we use the inequality
that

$\mathbb{P}(A\,\cup\,B)=\mathbb{P}(A)+\mathbb{P}(B)-\mathbb{P}(A\,\cap\,B)=\mathbb{P}(A\,\cap
B^{c})+\mathbb{P}(B).$

Then we can decompose

$\displaystyle\mathbb{P}(\mathcal{G}_{k}^{c})$
$\displaystyle\leq\mathbb{P}(\mathcal{G}^{0c}\,\cup\,\mathcal{G}_{1}^{pc})+\mathbb{P}(\mathcal{G}_{k}^{rc}\,\cup\,\mathcal{G}_{k}^{pc})$
$\displaystyle=\mathbb{P}\big{(}(\mathcal{G}^{0})^{c}\,\cap\,\mathcal{G}_{1}^{p}\big{)}+\mathbb{P}\big{(}(\mathcal{G}_{1}^{p})^{c}\big{)}+\mathbb{P}\big{(}\big{(}\mathcal{G}_{k}^{r})^{c}\,\cap\,\mathcal{G}_{k}^{p}\big{)}+\mathbb{P}\big{(}(\mathcal{G}_{k}^{p})^{c}\big{)}.$

with $\mathbb{P}\big{(}(\mathcal{G}_{1}^{p})^{c}\big{)}$ and
$\mathbb{P}\big{(}(\mathcal{G}_{k}^{p})^{c}\big{)}$ bounding easily. Indeed,
denote $d(p_{1},p_{2})$ as the KL-divergence between two Bernoulli
distributions of probability $p_{1}$ and $p_{2}$, then

$\mathbb{P}\big{(}(\mathcal{G}_{1}^{p})^{c}\big{)}=\mathbb{P}(\widehat{p}_{1,m_{1}}\leq
p_{1}-\epsilon_{1})\leq\exp\left(-m_{1}d(p_{1},p_{1}-\epsilon_{1})\right)$

and similarly
$\mathbb{P}\big{(}(\mathcal{G}_{k}^{p})^{c}\big{)}\leq\exp\left(-m_{k}d(p_{k},p_{k}-\epsilon_{k})\right)$.
For another two terms, we first consider to decompose the sample space as

$\Omega=\\{\widehat{p}_{1,m_{1}}\geq
p_{1}+\epsilon_{1}^{\prime}\\}\,\cup\,\\{\widehat{p}_{1,m_{1}}<p_{1}+\epsilon_{1}^{\prime}\\}$

with $\epsilon_{1}^{\prime}>0$ will be determined later. Then

$\displaystyle\mathbb{P}\big{(}(\mathcal{G}^{0})^{c}\,\cap\,\mathcal{G}_{1}^{p}\big{)}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\big{(}\Omega\,\cap\,(\mathcal{G}^{0})^{c}\,\cap\,\mathcal{G}_{1}^{p}\big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}(\widehat{p}_{1,m_{1}}\geq
p_{1}+\epsilon_{1}^{\prime})+\mathbb{P}\big{(}\widehat{p}_{1,m_{1}}\leq
p_{1}+\epsilon_{1}^{\prime},r_{1}\geq U_{1,m_{1}}^{\mu}(\delta)\times
U_{1,m_{1}}^{p}(\delta),\widehat{p}_{1,m_{1}}>p_{1}-\epsilon_{1}\big{)}$
$\displaystyle\leq$
$\displaystyle\exp(-m_{1}d(p_{1}+\epsilon_{1}^{\prime},p_{1}))+\mathbb{P}\big{(}r_{1}\geq
U_{1,m_{1}}^{\mu}(\delta)\times
U_{1,m_{1}}^{p}(\delta),p_{1}-\epsilon_{1}<\widehat{p}_{1,m_{1}}\leq
p_{1}+\epsilon_{1}^{\prime}\big{)}.$

Note that for any real numbers $a,b$ and any random variable $X,Y$ with
$b,Y\geq 0$,

$\mathbb{P}(ab\geq XY)\leq\mathbb{P}\big{(}\\{a\geq X\\}\text{ or }\\{b\geq
Y\\}\big{)}\leq\mathbb{P}(a\geq X)+\mathbb{P}(b\geq Y).$

By the above inequality, we can next bound the second term in the above bound,

$\displaystyle\mathbb{P}\big{(}r_{1}\geq U_{1,m_{1}}^{\mu}(\delta)\times
U_{1,m_{1}}^{p}(\delta),p_{1}-\epsilon_{1}<\widehat{p}_{1,m_{1}}\leq
p_{1}+\epsilon_{1}^{\prime}\big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{1}p_{1}\geq\left[\widehat{\mu}_{1,m_{1}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{1}\widehat{p}_{1,m_{1}}/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{1}\widehat{p}_{1,m_{1}}/2}\right)\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\left[\widehat{p}_{1,m_{1}}+\sqrt{\frac{\log(2/\delta)}{2m_{1}}}\right],\,p_{1}-\epsilon_{1}<\widehat{p}_{1,m_{1}}\leq
p_{1}+\epsilon_{1}^{\prime}\Bigg{\\}}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{1}p_{1}\geq\left[\widehat{\mu}_{1,m_{1}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}\right)\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\left[\widehat{p}_{1,m_{1}}+\sqrt{\frac{\log(2/\delta)}{2m_{1}}}\right],\,p_{1}-\epsilon_{1}<\widehat{p}_{1,m_{1}}\leq
p_{1}+\epsilon_{1}^{\prime}\Bigg{\\}}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{1}p_{1}\geq\left[\widehat{\mu}_{1,m_{1}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}\right)\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\left[\widehat{p}_{1,m_{1}}+\sqrt{\frac{\log(2/\delta)}{2m_{1}}}\right]\Bigg{\\}}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left\\{\mu_{1}\geq\widehat{\mu}_{1,m_{1}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}\right)\right\\}$
$\displaystyle+\mathbb{P}\left\\{p_{1}\geq\widehat{p}_{1,m_{1}}+\sqrt{\frac{\log(2/\delta)}{2m_{1}}}\right\\}.$

Since we have

$\mathbb{P}\left\\{p_{1}\geq\widehat{p}_{1,m_{1}}+\sqrt{\frac{\log(2/\delta)}{2m_{1}}}\right\\}\leq\frac{\delta}{2}$

and

$\displaystyle\mathbb{P}\left\\{\mu_{1}\geq\widehat{\mu}_{1,m_{1}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{1}({p}_{1}+\epsilon_{1}^{\prime})/2}\right)\right\\}$
$\displaystyle=$
$\displaystyle\mathbb{P}\left\\{\mu_{1}\geq\widehat{\mu}_{1,m_{1}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log\left(\frac{4}{4(\delta/4)^{\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}}}\right)}{m_{1}p_{1}/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}\left(\frac{4}{4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}}\right)}{m_{1}p_{1}/2}\right)\right\\}$ $\displaystyle\overset{\text{by
}\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\leq\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}{\leq}\mathbb{P}\left\\{\mu_{1}\geq\widehat{\mu}_{1,m_{1}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log\left(\frac{4}{4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}}\right)}{m_{1}p_{1}/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}\left(\frac{4}{4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}}\right)}{m_{1}p_{1}/2}\right)\right\\}$ $\displaystyle\overset{\text{by
Lemma
\ref{lem_light_tail_product}}}{\leq}4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}},$

whenever

$m_{1}\geq\frac{4}{p_{1}^{2}}\log\left(\frac{2}{4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}}\right)=\frac{4}{p_{1}^{2}}\log\left(\frac{1}{2}\left(\frac{4}{\delta}\right)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}\right),$ (9)

we can obtain

$\mathbb{P}\big{(}r_{1}\geq U_{1,m_{1}}^{\mu}(\delta)\times
U_{1,m_{1}}^{p}(\delta),p_{1}-\epsilon_{1}<\widehat{p}_{1,m_{1}}\leq
p_{1}+\epsilon_{1}^{\prime}\big{)}\leq
4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}+\delta/2.$

which concludes that

$\mathbb{P}\big{(}(\mathcal{G}^{0})^{c}\,\cap\,\mathcal{G}_{1}^{p}\big{)}\leq\exp\big{(}-m_{1}d(p_{1}+\epsilon_{1}^{\prime},p_{1})\big{)}+4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}+\delta/2.$

It remains to bound
$\mathbb{P}\big{(}\big{(}\mathcal{G}_{k}^{r})^{c}\,\cap\,\mathcal{G}_{k}^{p}\big{)}$.
We first decompose $\Omega=\\{\widehat{p}_{k,m_{k}}\geq
p_{k}+\epsilon_{k}^{\prime}\\}\,\cup\,\\{\widehat{p}_{k,m_{k}}<p_{k}+\epsilon_{k}^{\prime}\\}$
and similarly obtain that

$\displaystyle\mathbb{P}\big{(}\big{(}\mathcal{G}_{k}^{r})^{c}\,\cap\,\mathcal{G}_{k}^{p}\big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}(\widehat{p}_{k,m_{k}}\geq
p_{k}+\epsilon_{k}^{\prime})+\mathbb{P}\big{(}\widehat{p}_{k,m_{k}}\leq
p_{k}+\epsilon_{k}^{\prime},r_{1}\leq U_{k,m_{k}}^{\mu}(\delta)\times
U_{k,m_{k}}^{p}(\delta),\widehat{p}_{k,m_{k}}>p_{k}-\epsilon_{k}\big{)}$
$\displaystyle\leq$
$\displaystyle\exp\big{(}-m_{k}d(p_{k}+\epsilon_{k}^{\prime},p_{k})\big{)}+\mathbb{P}\big{(}r_{1}\leq
U_{k,m_{k}}^{\mu}(\delta)\times
U_{k,m_{k}}^{p}(\delta),\,p_{k}-\epsilon_{k}<\widehat{p}_{k,m_{k}}\leq
p_{k}+\epsilon_{k}^{\prime}\big{)}.$

The second term in above can be furthermore bounded by

$\displaystyle\mathbb{P}\big{(}r_{1}\leq U_{k,m_{k}}^{\mu}(\delta)\times
U_{k,m_{k}}^{p}(\delta),\,p_{k}-\epsilon_{k}<\widehat{p}_{k,m_{k}}\leq
p_{k}+\epsilon_{k}^{\prime}\big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{1}p_{1}\leq\left[\widehat{\mu}_{k,m_{k}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}\widehat{p}_{k,m_{k}}/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}\widehat{p}_{k,m_{k}}/2}\right)\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\left[\widehat{p}_{k,m_{k}}+\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\right],\,p_{k}-\epsilon_{k}<\widehat{p}_{k,m_{k}}\leq
p_{k}+\epsilon_{k}^{\prime}\Bigg{\\}}$ $\displaystyle=$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{k}p_{k}+\Delta_{k}\leq\left[\widehat{\mu}_{k,m_{k}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}\widehat{p}_{k,m_{k}}/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}\widehat{p}_{k,m_{k}}/2}\right)\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\left[\widehat{p}_{k,m_{k}}+\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\right]-\Delta_{k},\,p_{k}<\widehat{p}_{k,m_{k}}\leq
p_{k}+\epsilon_{k}^{\prime}\Bigg{\\}}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{k}p_{k}+\Delta_{k}\leq\left[\widehat{\mu}_{k,m_{k}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\left[\widehat{p}_{k,m_{k}}+\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\right],\,p_{k}-\epsilon_{k}<\widehat{p}_{k,m_{k}}\leq
p_{k}+\epsilon_{k}^{\prime}\Bigg{\\}}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{k}p_{k}+\Delta_{k}\leq$
$\displaystyle\left[\widehat{\mu}_{k,m_{k}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\right]\left[\widehat{p}_{k,m_{k}}+\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\right]\Bigg{\\}}$
$\displaystyle=\mathbb{P}\Bigg{\\{}\left(\mu_{k}+\frac{\Delta_{k}}{2p_{k}}\right)\left(p_{k}+\frac{p_{k}\Delta_{k}}{2r_{k}+\Delta_{k}}\right)\leq$
$\displaystyle\left[\widehat{\mu}_{k,m_{k}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\right]\left[\widehat{p}_{k,m_{k}}+\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\right]\Bigg{\\}}$
$\displaystyle\leq$ $\displaystyle P_{k,\mu}+P_{k,p},$

where the last step is by the fact that for any real numbers $a,b$ and any
random variable $X,Y$ with $b,Y\geq 0$,

$\mathbb{P}(ab\leq XY)\leq\mathbb{P}\big{(}\\{a\leq X\\}\text{ or }\\{b\leq
Y\\}\big{)}\leq\mathbb{P}(a\leq X)+\mathbb{P}(b\leq Y).$

Now, the two parts in the upper bound of $\mathbb{P}\big{(}r_{1}\leq
U_{k,m_{k}}^{\mu}(\delta)\times
U_{k,m_{k}}^{p}(\delta),\,p_{k}-\epsilon_{k}<\widehat{p}_{k,m_{k}}\leq
p_{k}+\epsilon_{k}^{\prime}\big{)}$ can be furthermore bounded. Indeed,
$P_{k,p}$ can be bounded as

$\displaystyle P_{k,p}$
$\displaystyle=\mathbb{P}\left\\{p_{k}+\frac{p_{k}\Delta_{k}}{2r_{k}+\Delta_{k}}\leq\widehat{p}_{k,m_{k}}+\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\right\\}$
$\displaystyle=\mathbb{P}\left\\{\frac{p_{k}\Delta_{k}}{2r_{k}+\Delta_{k}}-\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\leq\widehat{p}_{k,m_{k}}-p_{k}\right\\}$
$\displaystyle\leq\exp\left\\{-2m_{k}\left(\frac{p_{k}\Delta_{k}}{2r_{k}+\Delta_{k}}-\sqrt{\frac{\log(2/\delta)}{2m_{k}}}\right)^{2}\right\\}$
$\displaystyle=\frac{\delta}{2}\exp\left\\{-\frac{2m_{k}p_{k}\Delta_{k}}{2r_{k}+\Delta_{k}}\left(\frac{p_{k}\Delta_{k}}{2r_{k}+\Delta_{k}}-\sqrt{\frac{2\log(2/\delta)}{m_{k}}}\right)\right\\}$
$\displaystyle\leq\delta/2$

as long as

$m_{k}\geq\frac{2(2r_{k}+\Delta_{k})^{2}}{p_{k}^{2}\Delta_{k}^{2}}\log\left(\frac{2}{\delta}\right).$
(10)

Similarly,

$\displaystyle P_{k,\mu}$ $\displaystyle=$
$\displaystyle\mathbb{P}\Bigg{\\{}\mu_{k}+\frac{\Delta_{k}}{2p_{k}}\leq\widehat{\mu}_{k,m_{k}}+2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\Bigg{\\}}$ $\displaystyle=$
$\displaystyle\mathbb{P}\Bigg{\\{}\frac{\Delta_{k}}{2p_{k}}-2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\leq\widehat{\mu}_{k,m_{k}}-\mu_{k}\Bigg{\\}}$
$\displaystyle\overset{\text{by Lemma
\ref{lem_light_tail_product}}}{\leq}\mathbb{P}\Bigg{\\{}\frac{\Delta_{k}}{2p_{k}}-2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\leq\widehat{\mu}_{k,m_{k}}-\mu_{k},$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\big{\|}\mu_{k}-\widehat{\mu}_{k,m_{k}}\big{\|}_{\Psi_{\theta,\frac{p_{k}E(\theta)}{2\sqrt{m_{k}}}}}\leq\frac{4\mathrm{e}D(\theta)C}{p_{k}\sqrt{m_{k}}}\Bigg{\\}}+{\delta}/{2}$
$\displaystyle\overset{\text{by
\eqref{lem_RGBO_equv}}}{\leq}\frac{2}{1+\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}(\sqrt{3}s)}+\delta/2$

where

$s=\big{\|}\mu_{k}-\widehat{\mu}_{k,m_{k}}\big{\|}_{\Psi_{\theta,\frac{p_{k}E(\theta)}{2\sqrt{m_{k}}}}}^{-1}\left[\frac{\Delta_{k}}{2p_{k}}-2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\right].$

By the increasing property of $\Psi_{\theta,L}(\cdot)$, we obtain that

$\displaystyle\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}(\sqrt{3}s)$
$\displaystyle\geq$
$\displaystyle\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}\left(\frac{p_{k}\sqrt{3m_{k}}}{4\mathrm{e}D(\theta)C}\left[\frac{\Delta_{k}}{2p_{k}}-2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\right]\right)$
$\displaystyle\overset{\text{by
\eqref{light_tail_mid_condition}}}{\geq}\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}\left(\frac{\sqrt{3p_{k}m_{k}}}{4\mathrm{e}D(\theta)C}\left[2\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\right]\right)$
$\displaystyle=$
$\displaystyle\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}\left(\sqrt{\frac{3p_{k}\log(4/\delta)}{2(p_{k}-\epsilon_{k})}}+\frac{\sqrt{3p_{k}}E(\theta)\log^{(1/\theta)\vee
1}(4/\delta)}{\sqrt{m_{k}}(p_{k}-\epsilon_{k})}\right)$ $\displaystyle=$
$\displaystyle\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}\left(\sqrt{\log\left(\frac{4}{\delta}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}}+\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}\log^{(1/\theta)\vee
1}\left(\frac{4}{\delta}\right)^{\frac{2^{\theta\wedge 1}}{3^{(1/\theta)\wedge
1}p_{k}^{(\theta\wedge 1)/2}(p_{k}-\epsilon_{k})^{\theta\wedge 1}}}\right)$
$\displaystyle\overset{\text{by
}{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}\leq\frac{2^{\theta\wedge
1}}{3^{(1/\theta)\wedge 1}p_{k}^{(\theta\wedge
1)/2}(p_{k}-\epsilon_{k})^{\theta\wedge
1}}}{\geq}\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}\left(\sqrt{\log\left(\frac{4}{\delta}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}}+\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}\log^{(1/\theta)\vee
1}\left(\frac{4}{\delta}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}\right)$
$\displaystyle=$
$\displaystyle\left(\frac{4}{\delta}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}-1$

whenever

$2\left(1+\frac{1}{\sqrt{p_{k}}}\right)\mathrm{e}D(\theta)C\left(\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}+E(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\right)\leq\frac{\Delta_{k}}{2p_{k}},$
(11)

and a sufficient condition for this is

$2\left(1+\frac{1}{\sqrt{p_{k}}}\right)\mathrm{e}D(\theta)C\sqrt{\frac{\log(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}}\leq\frac{\Delta_{k}}{4p_{k}}$

and

$2\left(1+\frac{1}{\sqrt{p_{k}}}\right)\mathrm{e}D(\theta)CE(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{m_{k}(p_{k}-\epsilon_{k})/2}\leq\frac{\Delta_{k}}{4p_{k}}.$

Thus, we can take

$m_{k}\geq\frac{128\mathrm{e}^{2}D^{2}(\theta)C^{2}p_{k}(1+\sqrt{p_{k}})^{2}}{(p_{k}-\epsilon_{k})\Delta_{k}^{2}}\log\left(\frac{4}{\delta}\right)+\frac{16\mathrm{e}D(\theta)CE(\theta)\sqrt{p_{k}}(1+\sqrt{p_{k}})}{(p_{k}-\epsilon_{k})\Delta_{k}}\log^{(1/\theta)\vee
1}\left(\frac{4}{\delta}\right).$ (12)

Therefore, we can furthermore upper-bound $P_{k,\mu}$ as

$\displaystyle P_{k,\mu}$
$\displaystyle\leq\frac{2}{1+\Psi_{\theta,\frac{3^{1/2-1/\theta}p_{k}E(\theta)}{2\sqrt{m_{k}}}}(\sqrt{3}s)}+\delta/2$
$\displaystyle\leq\frac{2}{1+\left(\frac{4}{\delta}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}-1}+\delta/2$
$\displaystyle=2\left(\frac{\delta}{4}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}+\frac{\delta}{2}.$

Thus, we obtain that

$\displaystyle\mathbb{P}\big{(}\big{(}\mathcal{G}_{k}^{r})^{c}\,\cap\,\mathcal{G}_{k}^{p}\big{)}\leq\exp\big{(}-m_{k}d(p_{k}+\epsilon_{k}^{\prime},p_{k})\big{)}+2\left(\frac{\delta}{4}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}+\delta.$

under condition (10) and (12). To summarize these results, we have

$\displaystyle\mathbb{P}(\mathcal{G}_{k}^{c})$
$\displaystyle\leq\mathbb{P}\big{(}(\mathcal{G}^{0})^{c}\,\cap\,\mathcal{G}_{1}^{p}\big{)}+\mathbb{P}\big{(}(\mathcal{G}_{1}^{p})^{c}\big{)}+\mathbb{P}\big{(}\big{(}\mathcal{G}_{k}^{r})^{c}\,\cap\,\mathcal{G}_{k}^{p}\big{)}+\mathbb{P}\big{(}(\mathcal{G}_{k}^{p})^{c}\big{)}$
$\displaystyle\leq\exp\big{(}-m_{1}d(p_{1}+\epsilon_{1}^{\prime},p_{1})\big{)}+4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}+\delta/2+\exp\big{(}-m_{1}d(p_{1},p_{1}-\epsilon_{1})\big{)}$
$\displaystyle~{}~{}~{}~{}~{}+\exp\big{(}-m_{k}d(p_{k}+\epsilon_{k}^{\prime},p_{k})\big{)}+2\left({\delta}/{4}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}+\delta+\exp\big{(}-m_{k}d(p_{k},p_{k}-\epsilon_{k})\big{)},$

whenever $m_{1}$ satisfies (9) and $m_{k}$ satisfies (10) and (12).

Step 2: Now, we deal with
$\mathbb{E}[c_{k}(T)\cap\mathds{1}(\mathcal{G}_{k})]$. If
$c_{k}(T)>\max\\{m_{1},m_{k}\\}$, then arm $k$ was pulled more than $m_{k}$
times over the first $T$ rounds, and so there must exist a round
$t\in[m_{1},\ldots,T]$ such that $A_{t}=k$. However, on the good event
$\mathcal{G}_{k}$, we have

$\displaystyle U_{k}^{\mu}(t,\delta)U_{k}^{p}(t,\delta)$
$\displaystyle=U_{k,m_{k}}^{\mu}(\delta)U_{k,m_{k}}^{p}(\delta)$
$\displaystyle\overset{\text{on the event }\mathcal{G}_{k}^{r}}{<}r_{1}$
$\displaystyle\overset{\text{on the event
}\mathcal{G}^{0}}{<}\min_{t\in[m_{1},\ldots,T]}U_{1}^{\mu}(t,\delta)U_{1}^{p}(t,\delta)\leq
U_{1}^{\mu}(t,\delta)U_{1}^{p}(t,\delta).$

This means the agent will choose arm 1 instead of arm $k$ at time point $t$,
which leads to a contradiction. Thus, we must have

$c_{k}(T)\leq\max\\{m_{1},m_{k}\\}.$

Step 3: Combining the inequality in Step 1 and Step 2, we obtain

$\displaystyle\mathbb{E}c_{k}(T)$
$\displaystyle\leq\mathbb{E}[c_{k}(T)\cap\mathds{1}(\mathcal{E}_{k})]+\mathbb{E}[c_{k}(T)\cap\mathds{1}\\{(\mathcal{E}_{k})^{c}\\}]$
$\displaystyle\leq\mathbb{E}[c_{k}(T)\cap\mathds{1}(\mathcal{E}_{k})]+T\mathbb{P}(\mathcal{E}_{k}^{c})$
$\displaystyle\leq\max\\{m_{1},m_{k}\\}$
$\displaystyle~{}~{}~{}~{}+T\Big{[}\exp\big{(}-m_{1}d(p_{1}+\epsilon_{1}^{\prime},p_{1})\big{)}+\exp\big{(}-m_{1}d(p_{1},p_{1}-\epsilon_{1})\big{)}+4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}+2\left({\delta}/{4}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+3\delta/2+\exp\big{(}-m_{k}d(p_{k},p_{k}-\epsilon_{k})\big{)}+\exp\big{(}-m_{k}d(p_{k}+\epsilon_{k}^{\prime},p_{k})\big{)}\Big{]}$
$\displaystyle\leq\max\\{m_{1},m_{k}\\}+T\Big{[}\exp\\{-2m_{1}\epsilon_{1}^{\prime
2}\\}+\exp\\{-2m_{1}\epsilon_{1}^{2}\\}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\exp\\{-2m_{k}\epsilon_{k}^{\prime
2}\\}+\exp\\{-2m_{k}\epsilon_{k}^{2}\\}+4(\delta/4)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}+2\left({\delta}/{4}\right)^{\frac{3p_{k}}{2(p_{k}-\epsilon_{k})}}+2\delta\Big{]}$

whenever $m_{1}$ satisfies (9) and $m_{k}$ satisfies (10) and (12). Now,
taking

$m_{1}=\frac{4}{p_{1}^{2}}\log\left(\frac{1}{2}\left(\frac{4}{\delta}\right)^{\left(\frac{p_{1}}{p_{1}+\epsilon_{1}^{\prime}}\right)^{\theta\wedge
1}}\right)$

and

$\displaystyle m_{k}$ $\displaystyle=$
$\displaystyle\left(\frac{2(2r_{k}+\Delta_{k})^{2}}{p_{k}^{2}}+\frac{128\mathrm{e}^{2}D^{2}(\theta)C^{2}p_{k}(1+\sqrt{p_{k}})^{2}}{(p_{k}-\epsilon_{k})}\right)\frac{\log(4/\delta)}{\Delta_{k}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{16\mathrm{e}D(\theta)CE(\theta)\sqrt{p_{k}}(1+\sqrt{p_{k}})}{(p_{k}-\epsilon_{k})}\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{\Delta_{k}}$ $\displaystyle\geq$
$\displaystyle\frac{2(2r_{k}+\Delta_{k})^{2}}{p_{k}^{2}\Delta_{k}^{2}}\log\left(\frac{2}{\delta}\right)$
$\displaystyle~{}~{}~{}~{}+\frac{128\mathrm{e}^{2}D^{2}(\theta)C^{2}p_{k}(1+\sqrt{p_{k}})^{2}}{(p_{k}-\epsilon_{k})\Delta_{k}^{2}}\log\left(\frac{4}{\delta}\right)+\frac{16\mathrm{e}D(\theta)CE(\theta)\sqrt{p_{k}}(1+\sqrt{p_{k}})}{(p_{k}-\epsilon_{k})\Delta_{k}}\log^{(1/\theta)\vee
1}\left(\frac{4}{\delta}\right).$

with $\epsilon_{k}=\epsilon_{k}^{\prime}=p_{k}/2$ for $k\in[K]$ satisfies (9),
(10), and (12) by $r_{k}\in(0,1]$. Under these choice, we obtain

$\displaystyle\exp\\{-2m_{1}\epsilon_{1}^{\prime
2}\\}=\exp\\{-2m_{1}\epsilon_{1}^{2}\\}$ $\displaystyle=$
$\displaystyle\exp\left\\{-2\log\left(\frac{1}{2}\left(\frac{4}{\delta}\right)^{\left(1/2\right)^{\theta\wedge
1}}\right)\right\\}$ $\displaystyle=$
$\displaystyle\left(\frac{1}{2}\right)^{-2}\left[\left(\frac{4}{\delta}\right)^{\left(1/2\right)^{\theta\wedge
1}}\right]^{-2}=4\left(\delta^{2}/16\right)^{(1/2)^{\theta\wedge 1}},$

and

$\displaystyle\exp\\{-2m_{k}\epsilon_{k}^{\prime
2}\\}=\exp\\{-2m_{k}\epsilon_{k}^{2}\\}$ $\displaystyle=$
$\displaystyle\exp\Bigg{\\{}-\frac{p_{k}^{2}}{2}\bigg{[}\left(\frac{2(2r_{k}+\Delta_{k})^{2}}{p_{k}^{2}}+\frac{128\mathrm{e}^{2}D^{2}(\theta)C^{2}p_{k}(1+\sqrt{p_{k}})^{2}}{p_{k}/2}\right)\frac{\log(4/\delta)}{\Delta_{k}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{16\mathrm{e}D(\theta)CE(\theta)\sqrt{p_{k}}(1+\sqrt{p_{k}})}{p_{k}/2}\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{\Delta_{k}}\bigg{]}\Bigg{\\}}$ $\displaystyle=$
$\displaystyle\exp\Bigg{\\{}-\Big{[}(2r_{k}+\Delta_{k})^{2}+128p_{k}^{2}\mathrm{e}^{2}D^{2}(\theta)C^{2}(1+\sqrt{p_{k}})\Big{]}\frac{\log(4/\delta)}{\Delta_{k}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-16\mathrm{e}D(\theta)CE(\theta)p_{k}^{3/2}(1+\sqrt{p_{k}})\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{\Delta_{k}}\Bigg{\\}}$ $\displaystyle\leq$
$\displaystyle\exp\left\\{-(2r_{k}+\Delta_{k})^{2}\frac{\log(4/\delta)}{\Delta_{k}^{2}}\right\\}$
$\displaystyle\leq$
$\displaystyle\exp\left\\{-\Delta_{k}^{2}\frac{\log(4/\delta)}{\Delta_{k}^{2}}\right\\}=\delta/4.$

Aggregating these results, $\mathbb{E}c_{k}(T)$ can be furthermore upper
bounded by

$\displaystyle\mathbb{E}c_{k}(T)$
$\displaystyle\leq\max\\{m_{1},m_{k}\\}+T\left[8\left(\delta^{2}/16\right)^{(1/2)^{\theta\wedge
1}}+2\delta/4+4(\delta/4)^{(1/2)^{\theta\wedge
1}}+2(\delta/4)^{3}+2\delta\right]$ $\displaystyle\leq
m_{1}+m_{k}+T\left[8\left(\delta^{2}/16\right)^{1/2}+\delta/2+4(\delta/4)^{1/2}+2(\delta/4)^{3}+2\delta\right]$
$\displaystyle=m_{1}+m_{k}+T\left(2\sqrt{\delta}+3\delta+\delta^{3}/32\right)$
$\displaystyle=\frac{4}{p_{1}^{2}}\log\left(\left({4}/{\delta}\right)^{(1/2)^{\theta\wedge
1}}/2\right)+\left(\frac{2(2r_{k}+\Delta_{k})^{2}}{p_{k}^{2}}+\frac{128\mathrm{e}^{2}D^{2}(\theta)C^{2}p_{k}(1+\sqrt{p_{k}})^{2}}{p_{k}/2}\right)\frac{\log(4/\delta)}{\Delta_{k}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}+\frac{16\mathrm{e}D(\theta)CE(\theta)\sqrt{p_{k}}(1+\sqrt{p_{k}})}{p_{k}/2}\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{\Delta_{k}}+T\left(3\sqrt{\delta}+4\delta+\delta^{3}/32\right)$
$\displaystyle\leq\frac{4}{p_{1}^{2}}\left(\frac{1}{2}\right)^{\theta\wedge
1}\log\left({4}/{\delta}\right)+\Big{[}(2r_{k}+\Delta_{k})^{2}+128\mathrm{e}D^{2}(\theta)C^{2}p_{k}^{2}(1+\sqrt{p_{k}})^{2}\Big{]}\frac{2\log(4/\delta)}{p_{k}^{2}\Delta_{k}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+32\mathrm{e}D(\theta)CE(\theta)\sqrt{p_{k}}(1+\sqrt{p_{k}})\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{p_{k}\Delta_{k}}+T\left(3\sqrt{\delta}+4\delta+\delta^{3}/32\right)$
$\displaystyle\overset{\text{by $r_{k}\leq 1$ and $p_{k}\leq
1$}}{\leq}\frac{4}{p_{1}^{2}}\log\left({4}/{\delta}\right)+2\Big{(}9+512\mathrm{e}D^{2}(\theta)C^{2}\Big{)}\frac{\log(4/\delta)}{p_{k}^{2}\Delta_{k}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+64\mathrm{e}D(\theta)CE(\theta)\frac{\log^{(1/\theta)\vee
1}(4/\delta)}{p_{k}\Delta_{k}}+T\left(3\sqrt{\delta}+4\delta+\delta^{3}/32\right).$

Now, choose $\delta=4/T^{2}$,

$\displaystyle\mathbb{E}c_{k}(T)$ $\displaystyle\leq\frac{8\log
T}{p_{1}^{2}}+4\Big{(}9+512\mathrm{e}D^{2}(\theta)C^{2}\Big{)}\frac{\log
T}{p_{k}^{2}\Delta_{k}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+2^{6+(1/\theta)\vee
1}\mathrm{e}D(\theta)CE(\theta)\frac{\log^{(1/\theta)\vee
1}T}{p_{k}\Delta_{k}}+T\left(\frac{6}{T}+\frac{16}{T^{2}}+\frac{2}{T^{6}}\right).$

Finally, we obtain the cumulative regret is bounded by

$\displaystyle\mathcal{R}(T)$ $\displaystyle=$
$\displaystyle\sum_{k=2}^{K}\Delta_{k}\mathbb{E}c_{k}(T)$ $\displaystyle\leq$
$\displaystyle\frac{8}{p_{1}^{2}}\log
T\sum_{k=2}^{K}\Delta_{k}+4\Big{(}9+512\mathrm{e}D^{2}(\theta)C^{2}\Big{)}\sum_{k=2}^{K}\frac{\log
T}{p_{k}^{2}\Delta_{k}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+2^{6+(1/\theta)\vee
1}\mathrm{e}D(\theta)CE(\theta)\sum_{k=2}^{K}\frac{\log^{(1/\theta)\vee
1}T}{p_{k}}+\left(6+\frac{16}{T}+\frac{2}{T^{2}}\right)\sum_{k=2}^{K}\Delta_{k}.$

which gives the regret in the theorem. ∎

Proof of problem-independent regret (4):

###### Proof.

For any fixed $\Delta>0$, from the proof of Theorem 1, we know that

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\sum_{k=2}^{K}\Delta_{k}\mathbb{E}c_{k}(T)$
$\displaystyle=\sum_{k:\Delta_{k}<\Delta}\Delta_{k}\mathbb{E}c_{k}(T)+\sum_{k:\Delta_{k}\geq\Delta}\Delta_{k}\mathbb{E}c_{k}(T)$
$\displaystyle\lesssim
T\Delta+\sum_{k:\Delta_{k}\geq\Delta}\Bigg{[}\frac{1}{p_{k}^{2}}\frac{\log
T}{\Delta_{k}}+\frac{\log^{(1/\theta)\vee 1}T}{p_{k}}+\frac{\log
T}{p_{1}^{2}}\Delta_{k}+\Delta_{k}\Bigg{]}$
$\displaystyle\lesssim\sum_{k=2}^{K}\frac{\log^{(1/\theta)\vee
1}T}{p_{k}}+\sum_{k=2}^{K}\Delta_{k}\left(\frac{\log
T}{p_{1}^{2}}+1\right)+\frac{1}{\Delta}\sum_{k=2}^{K}\frac{\log
T}{p_{k}^{2}}+T\Delta$ $\displaystyle\overset{\text{by Cauchy inequality with
}\Delta=\sqrt{\frac{1}{T}\sum_{k=2}^{K}\frac{\log
T}{p_{k}^{2}}}}{\lesssim}\sum_{k=2}^{K}\frac{\log^{(1/\theta)\vee
1}T}{p_{k}}+\left(\frac{\log
T}{p_{1}^{2}}+1\right)\sum_{k=2}^{K}\Delta_{k}+\sqrt{\sum_{k=2}^{K}\frac{T\log
T}{p_{k}^{2}}}$ $\displaystyle\lesssim\frac{K\log
T}{p_{1}^{2}}+\sum_{k=2}^{K}\frac{\sqrt{T\log T}}{p_{k}}.$

∎

###  C.2 Proof of Theorem 2

Before proving the heavy tailed bandit results. We first state some basic
properties of $g(p,\epsilon)$ in the concentration of Lemma 2. Define
$h(p,\epsilon):=pg(p,\epsilon)=(1+\epsilon)2^{\frac{\epsilon}{1+\epsilon}}p^{\frac{1}{1+\epsilon}}+2\sqrt{p}+\frac{4}{3}$,
then $g$ is monotonically decreasing and $h$ is monotonically increasing with
respect to $p$. Specially, they satisfy

$h(p,\epsilon)\leq(1+\epsilon)\times 2\times 1+2\times
1+\frac{4}{3}=\frac{2}{3}(8+2\epsilon)$

for any $p\in(0,1)$, and

$g(p_{1},\epsilon)=\frac{(1+\epsilon)2^{\frac{\epsilon}{1+\epsilon}}}{p_{1}^{\frac{\epsilon}{1+\epsilon}}}+\frac{4}{3p_{1}}+\frac{2}{\sqrt{p_{1}}}\geq(1+\epsilon)2^{\frac{\epsilon}{1+\epsilon}}p_{2}^{\frac{1}{1+\epsilon}}+\frac{4}{3}+2\sqrt{p_{2}}=h(p_{2},\epsilon)$

for any $p_{1},p_{2}\in(0,1)$.

###### Proof.

The proof is similar to the proof of Theorem 1. The essential change is we use
the concentration of trimming observable sample mean in Lemma 2 instead of
sub-Weibull concentrations. We will borrow some techniques in [12]. For fixed
$\epsilon$, we will write $g(p)=g(p,\epsilon)$ and $h(p)=h(p,\epsilon)$.

Step 1:

Similar as the technique in [12], suppose $A_{t}=k$, we define the following
bad events

$\mathcal{B}^{0}(t):=\\{r_{1}\geq U_{1,c_{1}(t),t}^{\mu}\times
U_{1,c_{1}(t)}^{p}\\},\qquad\mathcal{B}_{k}^{\mu}(t):=\left\\{\widehat{\mu}_{k,c_{k}(t),t}\geq\mu_{k}+g({\widehat{p}_{k,t}})M^{\frac{1}{1+\epsilon}}\left(\frac{\log
t^{2}}{c_{k}(t)}\right)^{\frac{\epsilon}{1+\epsilon}}\right\\}$

and

$\displaystyle\mathcal{B}_{k}^{\text{count}}(t)$
$\displaystyle:=\left\\{c_{k}(t)\leq\big{[}2(p_{k}+\varepsilon_{k})g(p_{k}+\varepsilon_{k})\big{]}^{\frac{1+\epsilon}{\epsilon}}\frac{M^{\frac{1}{\epsilon}}}{(\Delta_{k}-\varepsilon_{k}\mu_{k})^{\frac{1+\epsilon}{\epsilon}}}\log
T\right\\}$
$\displaystyle=\left\\{c_{k}(t)\leq\big{[}2h(p_{k}+\varepsilon_{k})\big{]}^{\frac{1+\epsilon}{\epsilon}}\frac{M^{\frac{1}{\epsilon}}}{(\Delta_{k}-\varepsilon_{k}\mu_{k})^{\frac{1+\epsilon}{\epsilon}}}\log
T\right\\}$

with $\varepsilon_{k}\in(0,\Delta_{k}/\mu_{k})$ determined later. Similarly,
define

$\mathcal{B}_{k}^{p}(t)=\\{\widehat{p}_{k,t}>p_{k}+\varepsilon_{k}\\}$

On the event $\mathcal{B}^{0c}\,\cap\,\mathcal{B}_{k}^{\mu
c}\,\cap\,\mathcal{B}_{k}^{\text{count},\,c}\,\cap\,\mathcal{B}_{k}^{pc}$, we
have

$\displaystyle U_{1,c_{1}(t),t}^{\mu}\times U_{1,c_{1}(t),t}^{p}$
$\displaystyle>r_{1}$ $\displaystyle=r_{k}+\Delta_{k}$
$\displaystyle=\mu_{k}p_{k}+\Delta_{k}$
$\displaystyle\geq\mu_{k}p_{k}+2h(p_{k}+\varepsilon_{k})\left(\frac{\log
t^{2}}{c_{k}(t)}\right)^{\epsilon/(1+\epsilon)}+\mu_{k}\varepsilon_{k}$
$\displaystyle\overset{h\text{ is
increasing}}{\geq}\mu_{k}p_{k}+2h(\widehat{p}_{k,t})M^{1/(1+\epsilon)}\left(\frac{\log
t^{2}}{c_{k}(t)}\right)^{\epsilon/(1+\epsilon)}+\mu_{k}\varepsilon_{k}$
$\displaystyle\geq\mu_{k}(\widehat{p}_{k,t}-\varepsilon_{k})+2h(\widehat{p}_{k,t})M^{1/(1+\epsilon)}\left(\frac{\log
t^{2}}{c_{k}(t)}\right)^{\epsilon/(1+\epsilon)}+\mu_{k}\varepsilon_{k}$
$\displaystyle=\mu_{k}\widehat{p}_{k,t}+2h(\widehat{p}_{k,t})M^{1/(1+\epsilon)}\left(\frac{\log