# Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits

Zixin Zhong1
<EMAIL_ADDRESS>
Wang Chi Cheung2,3
<EMAIL_ADDRESS>
Vincent Y. F. Tan3,4,5
<EMAIL_ADDRESS>
1 Department of Computing Science, University of Alberta, Canada 2 Department
of Industrial Systems and Management, National University of Singapore,
Singapore 3 Institute of Operations Research and Analytics, National
University of Singapore, Singapore 4 Department of Mathematics, National
University of Singapore, Singapore 5 Department of Electrical and Computer
Engineering, National University of Singapore, Singapore.

###### Abstract

We study the Pareto frontier of two archetypal objectives in multi-armed
bandits, namely, regret minimization (RM) and best arm identification (BAI)
with a fixed horizon. It is folklore that the balance between exploitation and
exploration is crucial for both RM and BAI, but exploration is more critical
in achieving the optimal performance for the latter objective. To this end, we
design and analyze the BoBW-lil’UCB$(\gamma)$ algorithm. Complementarily, by
establishing lower bounds on the regret achievable by any algorithm with a
given BAI failure probability, we show that (i) no algorithm can
simultaneously perform optimally for both the RM and BAI objectives, and (ii)
BoBW-lil’UCB$(\gamma)$ achieves order-wise optimal performance for RM or BAI
under different values of $\gamma$. Our work elucidates the trade-off more
precisely by showing how the constants in previous works depend on certain
hardness parameters. Finally, we show that BoBW-lil’UCB outperforms a close
competitor UCBα (Degenne et al.,, 2019) in terms of the time complexity and
the regret on diverse datasets such as MovieLens and Published Kinase
Inhibitor Set.

##  1 Introduction

Consider a drug company $\mathsf{Dandit}$ (Drug Bandit) that wants to design
an effective vaccine for a certain virus. It has a certain number of feasible
options, say $L=10$. Because $\mathsf{Dandit}$ has a limited budget, it can
only test vaccines for a fixed number of times, say $T=1,000$. Using the
limited number of tests, it wants to find the option that will lead to the
“best” outcome, e.g., the maximum efficacy of the drug. At the same time,
$\mathsf{Dandit}$ aims to protect individuals from potentially adverse side
effects of the vaccines to be tested. How can $\mathsf{Dandit}$ find the
optimal drug design and, at the same time, protect the health of participants?
We design an algorithm BoBW-lil’UCB that allows $\mathsf{Dandit}$ to balance
between these two competing targets. In complement, we also show that it is
impossible for $\mathsf{Dandit}$ to achieve optimal performances for both
targets simultaneously, and $\mathsf{Dandit}$ has to settle for operating on
the Pareto frontier of the two objectives.

To solve $\mathsf{Dandit}$’s problem, we study the Cumulative Regret
Minimization (RM) and Best Arm Identification (BAI) problems for stochastic
bandits with a fixed time horizon or budget. While most existing works only
study one of these two targets (Auer et al., 2002a, ; Audibert and Bubeck,,
2010), Degenne et al., (2019) designed the UCBα algorithm for both RM and BAI
with a fixed confidence. Therefore, these studies are not directly applicable
to $\mathsf{Dandit}$’s problem as $\mathsf{Dandit}$ is interested in obtaining
the optimal item and minimizing the damage across a fixed number of tests.
However, our setting dovetails neatly with company $\mathsf{Dandit}$’s goals.
$\mathsf{Dandit}$ can utilize our algorithm to sequentially and adaptively
select different design options to test the vaccines and to eventually balance
between choosing the optimal vaccine and, in the process, mitigating any
physical damage on the participants. We also show that $\mathsf{Dandit}$
cannot achieve both targets optimally and simultaneously.

Beyond any specific applications, we believe this problem is of fundamental
theoretical importance in the broad context of multi-armed bandits (MAB). In
order to design an efficient bandit algorithm, a well-known challenge is to
balance between exploitation and exploration (Auer et al., 2002a, ; Lattimore
and Szepesvári,, 2020; Kaufmann and Garivier,, 2017). Our work quantifies the
Pareto frontier of RM and BAI, as well as the effects of exploitation and
exploration on these two aims.

Main contributions. In stochastic bandits, there are $L$ items with different
unknown reward distributions. At each time step, a random reward is generated
from each item’s distribution. Based on the previous observations, a learning
agent selects an item and observes its reward. Given the number of time steps
$T\in\mathbb{N}$, the agent aims to maximize the cumulative rewards and to
identify the optimal item with high probability.

Our first main contribution is the BoBW-lil’UCB$(\gamma)$ algorithm. BoBW-
lil’UCB$(\gamma)$ is designed for both RM and BAI over a fixed time horizon,
which achieves Pareto-optimality of RM and BAI in some regimes.

  * (i)

On one hand, we can shrink the confidence radius of each item by increasing
$\gamma$, which encourages BoBW-lil’UCB$(\gamma)$ to pull items with high
empirical mean rewards (exploitation) and generally leads to high rewards
(i.e., small regret).

  * (ii)

On the other hand, we can enlarge the confidence radius by decreasing $\gamma$
to encourage the exploration of items that have not been sufficiently pulled
in previous time steps (exploration); this will result in a high BAI success
probability.

The parameter $\gamma$ in BoBW-lil’UCB$(\gamma)$ can be tuned such that either
its cumulative regret or its failure probability almost matches the
corresponding state-of-the-art lower bound (Lai and Robbins,, 1985; Carpentier
and Locatelli,, 2016). The performance of BoBW-lil’UCB$(\gamma)$ implies that
exploitation is more critical in achieving the optimal performance for RM,
while exploration is more crucial for BAI in stochastic bandits. We also
analyze the Exp3.P algorithm proposed by Auer et al., 2002b  for both RM and
BAI, which indicates the similar trade-off between these two aims in
adversarial bandits.

Moreover, we evaluate the Pareto frontier of RM and BAI theoretically. In
Lattimore and Szepesvári, (2020), Note 33.2 and Exercise 33.5 only explore the
sub-optimality for BAI of an asymptotically-optimal RM algorithm, and provide
asymptotic bounds with constant $\varepsilon$ (See Section 3 for the meaning
of $\varepsilon$). Our work goes beyond the asymptotic regimes in that
observation, by exploring the Pareto frontier of RM and BAI for any algorithm
in Theorems 5.1 and 5.3 in the finite horizon / budget setting. Our non-
asymptotic bounds quantify how the trade-off between regret and BAI
probability depends on the hardness quantity $H_{2}$ and gap parameter
$\Delta_{1,i}$’s of an instance (see definitions in Section 2), instead of
fixed constants such as $\varepsilon$ (Lattimore and Szepesvári,, 2020).
Another relevant work is Bubeck et al., (2009), which explores the trade-off
between cumulative regret and _simple regret_.111When there is no ambiguity,
we abbreviate “cumulative regret” as “regret”. Due to the relation between BAI
and simple regret, our results precisely quantify the values of constants $C$
and $D$ in Bubeck et al., (2009) (see Section 5 for details). While these two
works focus on the stochastic bandits, we also analyze the Pareto frontier
between RM and BAI in adversarial bandits in Appendix B.

Furthermore, BoBW-lil’UCB$(\gamma)$ empirically outperforms a close competitor
UCBα (Degenne et al.,, 2019) in difficult scenarios in which the differences
between the optimal and suboptimal items are small. While both algorithms
identify the optimal item with high probability, UCBα, designed for the fixed-
confidence case, requires a longer horizon to do so and also suffers from
larger regret. This demonstrates the superiority of BoBW-lil’UCB$(\gamma)$
under the fixed-budget setting, which it is specifically designed for.

Novelty. (i) We are the first to design an algorithm for both RM and BAI with
a fixed budget. We can adjust the proposed BoBW-lil’UCB$(\gamma)$ algorithm to
perform (near-)optimally for both RM and BAI with proper choices of $\gamma$.
(ii) The performance of BoBW-lil’UCB$(\gamma)$ implies that exploitation is
more crucial to obtain a small regret, while exploration is more critical to
shrink the BAI failure probability. (iii) We quantify the Pareto frontier of
RM and BAI. We show that it is inevitable for any algorithm to compromise
between RM and BAI in a fixed horizon setting. Beyond the stochastic bandits,
we also provide a preliminary study on the adversarial bandits.

Literature review. Both the RM and BAI problems have been studied extensively
for stochastic multi-armed bandits. Firstly, an RM algorithm aims to maximize
its cumulative rewards, i.e., to minimize its regret (the gap between the
highest cumulative rewards and the obtained rewards). One line of seminal
works on RM involve the class of Upper Confidence Bound (UCB) algorithms (Auer
et al., 2002a, ; Garivier and Cappé,, 2011), while another line of works study
Thompson sampling (TS) algorithms (Agrawal and Goyal,, 2012; Russo and Van
Roy,, 2014; Agrawal and Goyal,, 2017). Lai and Robbins, (1985) derived a lower
bound on the regret of any online algorithm.

Secondly, there are two complementary settings for BAI: (i) given
$T\in\mathbb{N}$, the agent aims to maximize the probability of finding the
optimal item in at most $T$ steps (Audibert and Bubeck,, 2010; Karnin et al.,,
2013; Zhong et al., 2021a, ); (ii) given $\delta>0$, the agent aims to find
the optimal item with the probability of at least $1-\delta$ in the smallest
number of time steps (Bubeck et al.,, 2013; Kaufmann and Kalyanakrishnan,,
2013). These two settings are known as the fixed-budget and fixed-confidence
settings respectively. Moreover, Kaufmann et al., (2016) presented theoretical
findings for both settings, including a lower bound for two-armed bandits and
a lower bound for multi-armed Gaussian bandits under the fixed-budget setting.
Carpentier and Locatelli, (2016) established a lower bound on the failure
probability of any algorithm in a fixed time horizon.

While most existing works focus solely on RM or BAI, Degenne et al., (2019)
explored both goals with a fixed confidence and proposed the UCBα algorithm.
Recently Kim et al., (2023) also focused on the fixed-confidence setting and
studied the trade-off between RM and Pareto Front Identification (PFI) in
linear bandits; PFI is a generalization of BAI since in this setting each arm
has a vector reward instead of a scalar one. Simchi-Levi and Wang, (2023)
provided a novel definition of Pareto Optimality and aimed to solve a
corresponding minimax multi-objective optimization problem, which has a
different focus from this work. To the best of our knowledge, there is no
existing analysis of a single, unified algorithm for both RM and BAI given a
fixed horizon. Our work fills in this gap by proposing the BoBW-
lil’UCB$(\gamma)$ algorithm and proving that it achieves Pareto-optimality in
some regimes. We also study the Pareto frontier of RM and BAI, which depends
on the balance between exploitation and exploration. We show that a single
algorithm cannot perform optimally for both RM and BAI simultaneously.

##  2 Problem Setup

For any $n\in\mathbb{N}$, we denote the set $\\{1,\ldots,n\\}$ as $[n]$. Let
there be $L\in\mathbb{N}$ ground items, contained in $[L]$. A random variable
$X$ (or its distribution) is $\sigma$-sub-Gaussian ($\sigma$-SG) if
$\mathbb{E}[\mathrm{e}^{\lambda(X-\mathbb{E}X)}]\leq\exp({\lambda^{2}\sigma^{2}}/{2}).$
Each item $i\in[L]$ is associated with a $\sigma$-SG reward distribution
$\nu_{i}$, mean $w_{i}$, and variance $\sigma_{i}^{2}$. The distributions
$\\{\nu_{i}\\}_{i\in[L]}$, means $\\{w_{i}\\}_{i\in[L]}$, and variances
$\\{\sigma_{i}^{2}\\}_{i\in[L]}$ are unknown to the agent. We let
$\\{g_{i,t}\\}_{t=1}^{T}$ be the i.i.d. sequence of rewards associated with
item $i$ during the $T$ time steps; each $g_{i,t}$ is an independent sample
from $\nu_{i}$.

We focus on stochastic instances with a unique item having the highest mean
reward, and assume that $w_{1}>w_{2}\geq\ldots\geq w_{L}$, so the unique
optimal item $i^{*}=1$. Note that the items can, in general, be arranged in
any order; the ordering that $w_{i}\geq w_{j}$ for $i<j$ is employed to ease
our discussion. We denote $\Delta_{1,i}:=w_{1}-w_{i}$ as the optimality gap of
item $i$, and assume $\Delta_{1,i}\leq 1$ for all $i\in[L]$; this can be
achieved by rescaling the instance if necessary. We define the minimal
optimality gap

$\displaystyle\Delta:=\min_{i\neq 1}\Delta_{1,i}.$

Clearly, $\Delta>0$. We characterize the hardness of an instance with the
following canonical quantities:

$\displaystyle H_{1}$ $\displaystyle:=\sum_{i\neq
1}\frac{1}{\Delta_{1,i}}\quad\mbox{and}\quad H_{2}:=\sum_{i\neq
1}\frac{1}{\Delta_{1,i}^{2}}.$ (2.1)

The hardness quantity $H_{1}$ is involved in some near-optimal regret bounds
(Auer et al., 2002a, ; Agrawal and Goyal,, 2012). The quantity $H_{2}$ was
first introduced in Audibert and Bubeck, (2010) and appears in many landmark
works on BAI (Jamieson et al.,, 2014; Karnin et al.,, 2013; Carpentier and
Locatelli,, 2016).

The agent uses an online algorithm $\pi$ to decide the item $i_{t}^{\pi}$ to
pull at each time step $t$, and the item $i_{\mathrm{out}}^{\pi,T}$ to output
eventually. More formally, an algorithm consists of a tuple
$\pi\\!:=\\!((\pi_{t})_{t=1}^{T},\psi_{T}^{\pi,T})$, where

  * •

the sampling rule $\pi_{t}$ determines, based on the observation history, the
item $i_{t}^{\pi}$ to pull at time step $t$. That is, the random variable
$i_{t}^{\pi}$ is $\mathcal{F}_{t-1}$-measurable, where
$\mathcal{F}_{t}:=\sigma(i_{1}^{\pi},g_{i_{1}^{\pi},1},\ldots,i_{t}^{\pi},g_{i_{t}^{\pi},t})$;

  * •

the recommendation rule $\psi_{T}^{\pi,T}$ chooses an item
$i_{\mathrm{out}}^{\pi,T}$, that is, by definition,
$\mathcal{F}_{T}$-measurable.

Moreover, we define the pseudo-regret $R_{T}$ of $\pi$ as

$\displaystyle R_{T}(\pi):$ $\displaystyle=\max_{1\leq i\leq
L}\mathbb{E}\Bigg{[}\sum_{t=1}^{T}g_{i,t}\Bigg{]}-\mathbb{E}\Bigg{[}\sum_{t=1}^{T}g_{i_{t}^{\pi},t}\Bigg{]}=T\cdot
w_{1}-\mathbb{E}\Bigg{[}\sum_{t=1}^{T}w_{i_{t}^{\pi}}\bigg{]}.$

The algorithm $\pi$ aims to both minimize the pseudo-regret $R_{T}(\pi)$ and
at the same time, to identify the optimal item with high probability, i.e., to
minimize the failure probability $e_{T}(\pi):=\Pr(i_{\mathrm{out}}^{\pi,T}\neq
1)$. We omit $T$ and / or $\pi$ in the superscript or subscript when there is
no cause of confusion. We write $R_{T}(\pi)$ as $R_{T}(\pi,\mathcal{I})$,
$e_{T}(\pi)$ as $e_{T}(\pi,\mathcal{I})$ when we wish to emphasize their
dependence on both the algorithm $\pi$ and the instance $\mathcal{I}$.

##  3 Discussion on Existing Algorithms

Although there is no existing work that analyzes a single algorithm for both
RM and BAI in a fixed horizon, it is natural to ask if an algorithm which is
originally designed for RM can also perform well for BAI, and vice versa. In
Table 3.1, we present the theoretical results from some existing works. We
focus on algorithms that are with (potential) theoretical guarantees for both
RM and BAI. We define

$\displaystyle H^{\prime}_{p}:=\max_{i\neq
1}\frac{i^{p}}{\Delta_{i}^{2}}\;\;\text{ and
}\;\;C_{p}:=2^{-p}+\sum_{r=2}^{L}r^{-p}$

for $p>0$ as in Shahrampour et al., (2017). We abbreviate Sequential Halving
as SH, Nonlinear Sequential Elimination with parameter $p$ as NSE$(p)$, and
UCB-E with parameter $a$ as UCB-E$(a)$. Also see Appendix A for more
discussions.

Table 3.1:  Comparison among upper bounds for algorithms and lower bounds in
stochastic bandits.

Algorithm/Instance | Pseudo-regret $R_{T}$ | Failure Probability $e_{T}$ | References
---|---|---|---
SH | ${\Theta}(T)$ | $\displaystyle\approx\exp\bigg{(}-\frac{T}{8H_{2}\log_{2}L}\bigg{)}\vphantom{\Bigg{(}}$ | Karnin et al., (2013)
NSE$(p)$ | ${\Theta}(T)$ | $\displaystyle\approx\exp\bigg{(}-\frac{2(T-L)}{H^{\prime}_{p}C_{p}}\bigg{)}\vphantom{\Bigg{(}}$ | Shahrampour et al., (2017)
UCB-E$(\alpha\log T)$ | $6.3\alpha^{2}H_{1}\log T$ | $2LT^{1-2\alpha/25}$ | Corollary A.1, Audibert and Bubeck, (2010)
BoBW-lil’UCB$(\gamma)$ |  $H_{1}\log T$ (Prob-dep) | $\approx L\exp\\!\bigg{(}-\frac{T-L}{144H_{2}}\bigg{)}$ | Theorems 4.1 and 4.2
$\sqrt{TL}\log T$ (Prob-indep)
Stochastic Bandits | $\approx 4H_{1}\log T$ | $\displaystyle\frac{1}{6}\exp\bigg{(}-\frac{400T}{H_{2}\log L}\bigg{)}\vphantom{\Bigg{(}}$ | Lai and Robbins, (1985); Carpentier and Locatelli, (2016)
(Lower Bound)

According to the discussions on RM and BAI in Lattimore and Szepesvári,
(2020), any algorithm with an asymptotically optimal regret would incur a
failure probability lower bounded by $\Omega(T^{-1})$; this is much larger
than the state-of-the-art lower bound $\Omega(\exp(-400T/(H_{2}\log L)))$ by
Carpentier and Locatelli, (2016). Therefore, we only include algorithms that
were designed for BAI in Table 3.1.

Among the various BAI algorithms, SH and NSE$(p)$ perform almost the best.
However, their bounds on the failure probabilities are incomparable in
general. The comparison among more BAI algorithms is provided in Table A.1.
Due to the designs of SH and NSE$(p)$, we surmise their regrets grow linearly
with $T$, which is vacuous for the RM task.

Although UCB-E$(\alpha\log T)$ has upper bounds on both pseudo-regret and
failure probability, its bound on the latter, which decays only polynomially
fast with $T$ when $\alpha$ is an absolute constant, is clearly suboptimal
vis-à-vis the state-of-the-art lower bound by Carpentier and Locatelli,
(2016). In order to achieve an exponentially decaying upper bound on $e_{T}$
(i.e., $\exp(-\Theta(T))$), we need to set $\alpha=O(T/\log T)$, and hence the
regret bound (see Corollary A.1 in the supplementary) will be $O(T^{2}/\log
T)$, which is vacuous.

The discussion above raises a natural question. Is it possible to provide a
non-trivial bound on the regret for an algorithm that performs optimally for
BAI over a fixed horizon? This motivates us to design BoBW-lil’UCB, which can
be tuned to perform near-optimally for both RM and BAI.

##  4 The BoBW-lil’UCB Algorithm

We design and analyze BoBW-lil’UCB$(\gamma)$ (Best of Both Worlds-Law of
Iterated Logs-UCB), an algorithm for both RM and BAI in a fixed horizon. By
choosing parameter $\gamma$ judiciously, the guarantees of BoBW-
lil’UCB$(\gamma)$ match those of the state-of-the-art algorithms for both RM
(up to log factors) and BAI (concerning the exponential term).

Algorithm 1 BoBW-lil’UCB$(\gamma)$

1: Input: time budget $T$, size of ground set of items $L$, scale $\sigma>0$,
$\varepsilon\in(0,1)$, $\beta\geq 0$, and $\gamma\in(0,1)$.

2: Sample $i_{t}=i$ for $t=1,\ldots,L$ and set $t=L$.

3: For all $i\in[L]$, compute $N_{i,L}$, $\hat{g}_{i,L}$, $C_{i,L,\gamma}$,
$U_{i,L,\gamma}$:  $\displaystyle
N_{i,t}=\sum_{u=1}^{t}\mathsf{1}\\{i_{u}=i\\},\
\hat{g}_{i,t}=\frac{\sum_{u=1}^{t}g_{i,t}\cdot\mathsf{1}\\{i_{u}=i\\}}{N_{i,t}},$
$\displaystyle
C_{i,t,\gamma}=5\sigma(1+\sqrt{\varepsilon})\sqrt{\frac{2(1+\varepsilon)}{N_{i,t}}\cdot\log\Big{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t})}{\gamma}\Big{)}},\quad
U_{i,t,\gamma}=\hat{g}_{i,t}+C_{i,t,\gamma}.$

4: for $t=L+1,\ldots,T$ do

5: Pull item
$i_{t}=\operatorname*{arg\,max}_{i\in[L]\vphantom{\big{]}}}U_{i,t-1,\gamma}$.

6: Update $N_{i_{t},t}$, $\hat{g}_{i_{t},t}$, $C_{i_{t},t,\gamma}$, and
$U_{i_{t},t,\gamma}$.

7: end for

8: Output $i_{\mathrm{out}}=\operatorname*{arg\,max}_{i\in[L]}\hat{g}_{i,T}$.

Design of algorithm. We design BoBW-lil’UCB in the spirit of the law of the
iterated logarithm (LIL) (Darling and Robbins,, 1967; Jamieson et al.,, 2014).
We remark that it is a variation of the lil’UCB algorithm proposed by Jamieson
et al., (2014). The three differences are:

  * (i)

to construct the confidence radius $C_{i,t,\gamma}$, we replace $(1+\beta)$
and $\delta$ in lil’UCB by $5$ and $\gamma$ in BoBW-lil’UCB$(\gamma)$
respectively;

  * (ii)

in the design of $C_{i,t,\gamma}$, we also replace
$\log((1+\varepsilon)N_{i,t})$ by $\log(\beta+(1+\varepsilon)N_{i,t})$;

  * (iii)

BoBW-lil’UCB$(\gamma)$, which is designed for both RM and BAI in a fixed
horizon, involves no stopping rule since it proceeds for exactly $T$ time
steps; while lil’UCB is designed for BAI with a fixed confidence.

Although our algorithm depends on the choices of $\varepsilon$, $\beta$, and
$\gamma$, we term it as BoBW-lil’UCB$(\gamma)$ instead of the more verbose
BoBW-lil’UCB$(\varepsilon,\beta,\gamma)$ because we scale the confidence
radius by only varying $\gamma$ which adjusts the performance of the
algorithm. More precisely, inspired by the LIL (see Theorem C.1), we design
item $i$’s confidence radius $C_{i,t,\gamma}$ with $N_{i,t}$ (the number of
time steps when item $i$ is pulled up to and including the $t^{\mathrm{th}}$
time step) and $\hat{g}_{i,t}$ (the empirical mean of item $i$ at time step
$t$), and its upper confidence bound $U_{i,t,\gamma}$ accordingly.

The design of BoBW-lil’UCB$(\gamma)$ allows us to shrink $C_{i,t,\gamma}$, the
confidence radius of each item $i$, by increasing $\gamma$; and vice versa.
Moreover, with a fixed $\gamma$, if item $i$ is rarely pulled in previous time
steps, it has a small $N_{i,t}$ and hence a large $C_{i,t,\gamma}$; and vice
versa.

  * (i)

Therefore, when $\gamma$ increases, the dominant term in
$U_{i,t,\gamma}=\hat{g}_{i,t}+C_{i,t,\gamma}$ becomes the empirical mean
$\hat{g}_{i,t}$. Since BoBW-lil’UCB pulls the item with the largest
$U_{i,t-1,\gamma}$ at time step $t$, the algorithm tends to pull the item with
the largest empirical mean in this case. In other words, a large $\gamma$
encourages exploitation.

  * (ii)

When $\gamma$ decreases, the confidence radius $C_{i,t,\gamma}$ dominates
$U_{i,t,\gamma}$. Consequently, BoBW-lil’UCB is likely to pull items with
large $C_{i,t,\gamma}$, i.e., the rarely pulled items with small $N_{i,t}$.
This indicates that a small $\gamma$ encourages exploration.

Altogether, we can scale $U_{i,t,\gamma}$ by adjusting $\gamma$, which allows
us to balance exploitation and exploration and trade-off between the twin
objectives — RM and BAI.

Analysis for RM. We first derive problem-dependent and problem-independent
bounds on the pseudo-regret of BoBW-lil’UCB$(\gamma)$.

######  Theorem 4.1 (Bounds on the pseudo-regret of BoBW-lil’UCB).

Let $\varepsilon\in(0,1)$, $\beta\geq 0$, and
$\gamma\in(0,\min\\{\log(\beta+1+\varepsilon)/e,1\\})\vphantom{\big{(}}$. For
all $T\geq 1$, the pseudo-regret of BoBW-lil’UCB$(\gamma)$ satisfies

$\displaystyle R_{T}\\!\leq\\!O\bigg{(}\sigma^{2}\cdot\sum_{i\neq
1}\frac{\log({1}/{\gamma})}{\Delta_{1,i}}+2TL\gamma^{1+\varepsilon}\bigg{)},\quad
R_{T}\\!\leq\\!O\bigg{(}\sigma^{2}\sqrt{TL}\log\bigg{(}\frac{\log(T/L\gamma)}{\gamma}\bigg{)}+2TL\gamma^{1+\varepsilon}~{}\bigg{)}.$

Furthermore, we can set $\gamma=(\log T)/{T}$ to obtain

$\displaystyle R_{T}\leq O\bigg{(}\sigma^{2}\cdot\sum_{i\neq 1}\frac{\log
T}{\Delta_{1,i}}\bigg{)},\quad R_{T}\leq O\big{(}\sigma^{2}\sqrt{TL}\log
T~{}\big{)}.$

We observe that the order of the problem-dependent upper bound on the pseudo-
regret of BoBW-lil’UCB($(\log T)/{T}$) almost matches that of the lower bound
(Lai and Robbins,, 1985). Moreover, the worst-case (problem-independent) upper
bound of BoBW-lil’UCB($(\log T)/{T}$) is $\tilde{O}(\sqrt{TL})$, which matches
the lower bound $O(\sqrt{TL})$ (Bubeck et al.,, 2012) up to log factors. This
implies that we can tune the parameter $\gamma$ in the BoBW-lil’UCB$(\gamma)$
algorithm to obtain close-to-optimal performance for RM.

We remark that when the optimal item is not unique, we can also derive
analogous upper bounds on the pseudo-regret of BoBW-lil’UCB$(\gamma)$ using a
similar line of analysis (see Proposition D.1).

Analysis for BAI. Next, we upper bound the failure probability of BoBW-
lil’UCB$(\gamma)$.

######  Theorem 4.2 (Bounds on the failure probability of BoBW-lil’UCB).

Let $\varepsilon\in(0,1)$, $\beta\geq 0$, and
$\gamma\in(0,\min\\{\log(\beta+1+\varepsilon)/e,1\\})\vphantom{\big{(}}$. Let
$\Delta_{i}=\max\\{\Delta,\Delta_{1,i}\\}$ for all $i\in[L]$. For all $T\geq
1$, the failure probability of BoBW-lil’UCB$(\gamma)$ satisfies

(4.1)

In particular, the bound on $e_{T}$ in (4.1) holds when
$\gamma\geq\gamma_{1}(\Delta,H_{2})$, where

$\displaystyle\gamma_{1}(\Delta,H_{2})$
$\displaystyle=\sqrt{2.8\log\bigg{(}\frac{6\sqrt{2.8}\sigma(1+\varepsilon)^{2}}{\Delta}+\beta\bigg{)}}\cdot\exp\Bigg{(}-\frac{T-L}{144\sigma^{2}(1+\varepsilon)^{3}(H_{2}+\Delta^{-2})}\Bigg{)}.$

For all $T\geq 1$, when $\gamma$ assumes its lower bound
$\gamma_{1}(\Delta,H_{2})$, we have

$\displaystyle\\!\\!e_{T}\leq\tilde{O}\bigg{(}\\!L\exp\\!\bigg{(}\\!\\!-\\!\frac{T-L}{144\sigma^{2}(1+\varepsilon)^{2}(H_{2}+\Delta^{-2})}\bigg{)}\bigg{)}.\\!$
(4.2)

When $T\gg L$, the gap between our upper bound in (4.2) and
$\Omega(\exp(-{400T}/{(H_{2}\log L)}))$, the state-of-the-art lower bound
(Carpentier and Locatelli,, 2016), is manifested by the (pre-exponential) term
$L$ as well as the constant in the exponent. This indicates that BoBW-
lil’UCB$(\gamma)$ can be adjusted to perform near-optimally for BAI over a
fixed horizon.

Further observation. As discussed earlier, BoBW-lil’UCB$(\gamma)$ encourages
more exploitation than exploration when $\gamma$ is large (e.g. $\gamma=(\log
T)/{T}$) and it stimulates more exploration when $\gamma$ is small (e.g.
$\gamma=\gamma_{1}(\Delta,H_{2})$). Besides, Theorems 4.1 and 4.2 imply that
the pseudo-regret of BoBW-lil’UCB$(\gamma)$ decreases with $\gamma$ while its
failure probability increases with $\gamma$. Therefore, to minimize the
regret, we should increase $\gamma$ to stimulate exploitation; and we should
decrease $\gamma$ to encourage exploration for obtaining a small failure
probability. This indicates that an optimal RM algorithm encourages more
exploitation compared to an optimal BAI one, and vice versa.

##  5 Pareto Frontier of RM and BAI

Theorems 4.1 and 4.2 together suggest that BoBW-lil’UCB$(\gamma)$ cannot
perform optimally for both RM and BAI simultaneously with a universal (or
single) choice of $\gamma$. In this section, we prove that no algorithm can
perform optimally for these two objectives simultaneously. Given a certain
failure probability of an algorithm, our goal is to establish a non-trivial
lower bound on its pseudo-regret.

We first consider bandit instances in which items have bounded rewards. Let
$\mathcal{B}_{1}(\underline{\Delta},\overline{R})$ denote the set of
stochastic instances where (i) the minimal optimality gap
$\Delta\geq\underline{\Delta}$; and (ii) there exists $R_{0}\in\mathbb{R}$
such that the rewards are bounded in $[R_{0},R_{0}+\overline{R}]$. Let
$\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})$ denote the
set of instances that (i) belong to
$\mathcal{B}_{1}(\underline{\Delta},\overline{R})$, and (ii) have hardness
quantities $H_{2}\leq\overline{H}_{2}$.

######  Theorem 5.1.

Let $\phi_{T},\underline{\Delta},\overline{R},\overline{H}_{2}>0$. Let $\pi$
be any algorithm with $e_{T}(\pi,\mathcal{I})\leq\exp(-\phi_{T})/4$ for all
$\mathcal{I}\in\mathcal{B}_{1}(\underline{\Delta},\overline{R})$. Then

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{1}(\underline{\Delta},\overline{R})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{(L-1)\overline{R}}{8\underline{\Delta}},\qquad\sup_{\mathcal{I}\in\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{\underline{\Delta}\overline{H}_{2}\overline{R}^{3}}{8}.$

In Theorem 5.1, we apply the bounds $R_{0}$ and $R_{0}+\overline{R}$ on items’
rewards to classify instances. In general, $\Delta H_{2}\leq(L-1)/\Delta$
holds for any instance, and equality holds when $\Delta_{1,i}=\Delta$ for all
$i\neq 1$. Therefore,
$\mathcal{B}_{1}(\underline{\Delta},\overline{R})=\mathcal{B}_{2}(\underline{\Delta},\overline{R},(L-1)/(\underline{\Delta}^{2}))$.
When $\overline{R}>1$, the analysis for the set
$\mathcal{B}_{2}(\underline{\Delta},\overline{R},(L-1)/(\underline{\Delta}^{2}))$
provides a better bound (higher lower bound) for the set
$\mathcal{B}_{1}(\underline{\Delta},\overline{R})$.

Our non-asymptotic bounds complete the asymptotic observation on the trade-off
between regret and BAI in Lattimore and Szepesvári, (2020) and quantify how
the trade-off depends on the hardness quantity $H_{2}$ and gap
$\Delta_{1,i}$’s of an instance, instead of fixed constants such as
$\varepsilon$. Another relevant work is Bubeck et al., (2009). On one hand,
Bubeck et al., (2009) explores the trade-off between the cumulative regret
$R_{T}$ and the simple regret $r_{T}$ and shows that any algorithm with
$R_{T}\leq C\psi(T)$ satisfies
$r_{T}\geq{\underline{\Delta}}\exp(-D\psi(T))/{2}$ in some instance. On the
other hand, our work studies the Pareto frontier of $R_{T}$ and the BAI
failure probability $e_{T}$. Since $e_{T}$ and $r_{T}$ satisfy that
$\underline{\Delta}\cdot e_{T}\leq r_{T}\leq e_{T}$, our Theorem 5.1 indicates
that

######  Corollary 5.2.

Let $\phi_{T},\underline{\Delta}>0$. Let $\pi$ be any algorithm satisfying

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{1}(\underline{\Delta},1)}R_{T}(\pi,\mathcal{I})\leq\phi_{T}\cdot\frac{L-1}{8\underline{\Delta}},$

then $e_{T}\geq\exp(-\phi_{T})/4$ and
$r_{T}\geq\underline{\Delta}\exp(-\phi_{T})/4$.

In view of Corollary 5.2, we have precisely quantified that
$C=(L-1)/(8\underline{\Delta})$ and $D=1$ in the work of Bubeck et al.,
(2009).

Furthermore, we establish a similar analysis for instances in which the
variance of each item’s reward distribution is bounded. Let
$\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{V})$ denote the set of
instances where (i) the minimal optimality gap $\Delta\geq\underline{\Delta}$;
(ii) for each item $i$, the variance $\sigma_{i}^{2}\leq\overline{V}$. Let
$\mathcal{B}_{2}^{\prime}(\underline{\Delta},\overline{V},\overline{H}_{2})$
denote the set of instances (i) that belong to
$\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{V})$, and (ii) have
hardness quantities $H_{2}\leq\overline{H}_{2}$. The key difference between
the proofs of these two theorems lies in the design of hard instances. We
elaborate on the details in Appendix E.

######  Theorem 5.3.

Let $\phi_{T},\underline{\Delta},\overline{V},\overline{H}_{2}>0$. Let $\pi$
be any algorithm with $e_{T}(\pi,\mathcal{I})\leq\exp(-\phi_{T})/4$ for all
$\mathcal{I}\in\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{V})$.
Then

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{V})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{(L-1)\overline{V}}{2\underline{\Delta}},\qquad\sup_{\mathcal{I}\in\mathcal{B}_{2}^{\prime}(\underline{\Delta},\overline{V},\overline{H}_{2})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{\underline{\Delta}\overline{H}_{2}\overline{V}}{2}.$

By characterizing stochastic rewards with different statistics, Theorems 5.1
and 5.3 provide different lower bounds on the pseudo-regret. We observe that
when the rewards of items are bounded in $[R_{0},R_{0}+\overline{R}]$ for some
$R_{0}\in\mathbb{R}$, the variances of the rewards are bounded by
$\overline{R}^{2}/4$. Therefore,

$\displaystyle\mathcal{B}_{1}(\underline{\Delta},\overline{R})\subset\mathcal{B}_{1}^{\prime}\bigg{(}\underline{\Delta},\frac{\overline{R}^{2}}{4}\bigg{)},\qquad\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})\subset\mathcal{B}_{2}^{\prime}\bigg{(}\underline{\Delta},\frac{\overline{R}^{2}}{4},\overline{H}_{2}\bigg{)}.$

Besides, it is clear that

$\displaystyle\mathcal{B}_{1}(\underline{\Delta},\overline{R}),\
\mathcal{B}_{2}(\underline{\Delta},\overline{R},h),\
\mathcal{B}_{2}^{\prime}\bigg{(}\underline{\Delta},\frac{\overline{R}^{2}}{4},h\bigg{)}\subset\mathcal{B}_{1}^{\prime}\bigg{(}\underline{\Delta},\frac{\overline{R}^{2}}{4}\bigg{)}.$

Due to the relationship among these four sets of instances, we let $\pi$ be an
algorithm with $e_{T}(\pi,\mathcal{I})\leq\exp(-\phi_{T})/4$ in any instance
of $\mathcal{B}_{1}^{\prime}(\underline{\Delta},{\overline{R}^{2}}/{4})$, and
compare the derived lower bounds on its pseudo-regret $R_{T}(\pi,\mathcal{I})$
in Table 5.1. Table 5.1 indicates that

  * •

when the bound for $\mathcal{B}_{1}(\underline{\Delta},\overline{R})$ (second
column of Table 5.1) holds for
$\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{R}^{2}/4)$, the
quantities $L$ and $\underline{\Delta}$ are of the same order in the bounds
derived for $\mathcal{B}_{1}(\underline{\Delta},\overline{R})$ and
$\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{R}^{2}/4)$
respectively;

  * •

similarly, when the bound for
$\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})$ (third
column) holds for
$\mathcal{B}_{2}^{\prime}(\underline{\Delta},{\overline{R}^{2}}/{4},\overline{H}_{2})$,
the quantities $L$ and $\underline{\Delta}$ are of the same order in the
bounds for $\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})$
and
$\mathcal{B}_{2}^{\prime}(\underline{\Delta},{\overline{R}^{2}}/{4},\overline{H}_{2})$.

Table 5.1: Lower bounds on $R_{T}$ when $e_{T}\leq\mathrm{e}^{-\phi_{T}}/4$.

Instance Set  | $\mathcal{B}_{1}(\underline{\Delta},\overline{R})$ | $\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})$ | $\mathcal{B}_{1}^{\prime}(\underline{\Delta},{\overline{R}^{2}}/{4})$ | $\mathcal{B}_{2}^{\prime}(\underline{\Delta},{\overline{R}^{2}}/{4},\overline{H}_{2})$
---|---|---|---|---
Bound on $R_{T}$ | $\phi_{T}\cdot{(L\\!-\\!1)\overline{R}}{/(8\underline{\Delta})}$ | $\phi_{T}\cdot{\underline{\Delta}\overline{H}_{2}\overline{R}^{3\vphantom{\hat{3}}}}/{8}$ | $\phi_{T}\cdot{(L\\!-\\!1)\overline{R}^{2}}/{(8\underline{\Delta})}$ | $\phi_{T}\cdot{\underline{\Delta}\overline{H}_{2}\overline{R}^{2}}/{8}$

Moreover, when $\overline{R}>1$, we can apply the analysis of
$\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})$ to obtain
a better bound (higher lower bound) for
$\mathcal{B}_{2}^{\prime}(\underline{\Delta},{\overline{R}^{2}}/{4},\overline{H}_{2})$.

In any set of instances studied in Theorems 5.1 or 5.3,

  * •

when $\phi_{T}$ linearly grows with $T$, which is typical in the bounds on
$e_{T}$ (Karnin et al.,, 2013; Carpentier and Locatelli,, 2016), the
corresponding bound on $R_{T}$ grows linearly with $T$ (vacuous);

  * •

when the bound on $R_{T}$ grows with $\log T$ as in Garivier and Cappé, (2011)
and Lai and Robbins, (1985), $\phi_{T}$ grows logarithmically with $T$ (i.e.,
the failure probability only decays polynomially).

Thus, we cannot achieve optimal performances for both RM and BAI using any
algorithm with fixed parameters. Alternatively, we can apply BoBW-
lil’UCB$(\gamma)$ to achieve the best of both objectives with proper choices
of the single parameter $\gamma$.

Tightness of the upper and lower bounds. We compare the upper and lower bounds
on the pseudo-regret of BoBW-lil’UCB($\gamma$) when the horizon $T\to\infty$.

######  Corollary 5.4.

Define the interval
$\mathcal{I}(\nu,T)=[\gamma_{1}(\underline{\Delta},\overline{H}_{2}),\min\\{\log(\beta+1+\varepsilon)/e,(\log
T)/T,1/L\\}]$, which is a function of the instance $\nu$ and the fixed horizon
$T$. When $\mathcal{I}(\nu,T)\neq\emptyset$,let $\pi_{0}$ denote the online
algorithm BoBW-lil’UCB$(\gamma)$ with $\gamma$ satisfying the condition that
$\gamma\in\mathcal{I}(\nu,T)$. Then

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{2}(\underline{\Delta},1,\overline{H}_{2})}R_{T}(\pi_{0},\mathcal{I})\in\Omega\bigg{(}\underline{\Delta}\overline{H}_{2}\log\bigg{(}\frac{1}{\gamma
L}\bigg{)}\bigg{)}\bigcap
O\bigg{(}\frac{L}{\underline{\Delta}}\log\bigg{(}\frac{1}{\gamma}\bigg{)}\bigg{)}.$

We observe from Corollary 5.4,222$\overline{H}_{2}$ has the same units as
$L\cdot\underline{\Delta}^{-2}$; hence, the terms in $\Omega(\cdot)$ and
$O(\cdot)$ also have the same units. which combines Theorems 4.1, 4.2, and
5.1, that the gap between the upper and lower bounds depend on the term
$\underline{\Delta}\overline{H}_{2}$ in the lower bound and
$L/\underline{\Delta}$ in the upper bound. As $H_{2}\leq(L-1)\Delta^{-2}$ for
any instance, when $\Delta=\Delta_{1,i}$ for all $i\neq 1$ (all suboptimal
items have the same suboptimality gap), equality holds, and hence the bounds
match up to a small additive $\log(1/L)$ term. Corollary 5.4 implies that the
parameter $\gamma$ in BOBW-lil-UCB$(\gamma)$ is essential in tuning the
algorithm such that it can perform optimally for either RM or BAI. This
implies that in some regimes, BOBW-lil-UCB$(\gamma)$ achieves Pareto-
optimality up to constant or small additive (e.g., $\log(1/L)$) terms.

Besides, to show that there are cases for which
$\mathcal{I}(\nu,T)\neq\emptyset$, we use several examples here. In the
instance where $L=256$, $w_{1}=0.5$, $w_{i}=0.45$ for $i\neq 1$ and rewards
are drawn from Bernoulli distributions, if we let $\varepsilon=0.01$,
$\beta=e$, $\mathcal{I}(\nu,T)$ is always non-empty when time horizon $T\geq
10^{6}$ as shown in Table 5.2.

Table 5.2: Intervals $\mathcal{I}(\nu,T)$ under different time horizons $T$ Time horizon $T$ | $\mathcal{I}(\nu,T)$ |
---|---|---
$10^{6}\vphantom{\Big{(}}$ | $[1.85\times 10^{-7},$ | $1.38\times 10^{-5}]$
$10^{7}\vphantom{\Big{(}}$ | $[4.33\times 10^{-73},$ | $1.61\times 10^{-6}]$
$10^{8}\vphantom{\Big{(}}$ | $[0,$ | $1.84\times 10^{-7}]$
$10^{9}\vphantom{\Big{(}}$ | $[0,$ | $2.07\times 10^{-8}]$

Furthermore, Corollary 5.4 suggests that the lower bound in Theorem 5.1 is
almost tight, as it is achieved by BoBW-lil’UCB$(\gamma)$. Hence, up to terms
logarithmic in the parameters such as $L$, we have quantified the Pareto
frontier for the trade-off between RM and BAI in stochastic bandits.

##  6 Numerical Experiments

We numerically compare BoBW-lil’UCB$(\gamma)$ and UCBα as they are the only
algorithms that can be tuned to perform (near-)optimally for both RM and BAI.
Since BoBW-lil’UCB$(\gamma)$ is designed for the fixed-budget setting and UCBα
is for the fixed-confidence setting, there cannot be a completely fair
comparison between them. However, we attempt to perform fair comparisons as
much as possible.

We evaluate the algorithms with both synthetic and real data. For BoBW-
lil’UCB$(\gamma)$, we fix $\varepsilon=0.01$, $\beta=e$, and vary $\gamma$.
For UCBα, we vary $\alpha$. We run BoBW-lil’UCB$(\gamma)$ for $T$ (fixed in a
specific instance) time steps, when the horizon (stopping time) of UCBα
depends on its stopping rule and the instance. Due to the difference between
the fixed-horizon and fixed-confidence settings, the regrets of each algorithm
may be accumulated over different time horizons.

For each choice of algorithm and instance, we run $10^{4}$ independent trials.
Since the empirical failure probability of BoBW-lil’UCB$(\gamma)$ is below
$1\%$ in each instance (see Table H.1 in Appendix H.1), we set $\delta=0.01$
for UCBα, which guarantees that the failure probability of UCBα is also below
$1\%$. We also present the experiment results with empirical failure
probabilities below $2\%$ in Appendix H (where we set $\delta=0.02$ for UCBα).
We focus on the comparison on (i) the time horizon each algorithm runs; and
(ii) the regret incurred over its corresponding horizon. We present the
averages and standard deviations of the time horizons and redthe regrets of
each algorithm. More numerical results that reinforce the conclusions herein
are presented in Appendix H.

###  6.1 Experiments using synthetic data

We set $w_{1}=0.5$, and $w_{i}=0.5-\Delta$ for all $i\neq 1$. We let
$\mathrm{Bern}(a)$ denote the Bernoulli distribution with parameter $a$. We
consider Bernoulli bandits, i.e., $\nu_{i}=\mathrm{Bern}(w_{i})$. We display
some numerical results in Figure 6.1 ; more results are postponed to Appendix
H.3.

Figure 6.1: Bernoulli instances with $L\\!=\\!64$, failure probability
$\\!\leq\\!1\%$. Left: $\Delta\\!=\\!0.05$; right: $\Delta\\!=\\!0.1$.

Under each instance presented in Figure 6.1, the regret of BoBW-
lil’UCB$(\gamma)$ is reduced when $\gamma$ grows (see Table H.3 for exact
values), which corroborates with Theorem 4.1. Both the regret and the stopping
time of UCBα grow with $\alpha$, which corroborates with Degenne et al.,
(2019, Theorem 3). Moreover, we observe that the standard deviations of the
regrets are larger for UCBα compared to BoBW-lil’UCB$(\gamma)$, which suggests
that BoBW-lil’UCB$(\gamma)$ is more statistically robust and consistent in
terms of the regret. Note that a larger $\Delta$ means that the difference
between the optimal and suboptimal items is more pronounced, resulting in an
easier instance. Given a fixed horizon $T$, our BoBW-lil’UCB$(\gamma)$
algorithm outperforms the UCBα algorithm with a varying range of parameters
$\gamma$ and $\alpha$ in instances with different values of $\Delta$.

###  6.2 Experiments on real datasets

We use two real-world datasets, the MovieLens 25M (ML-25M) dataset (Harper and
Konstan,, 2015) and the Published Kinase Inhibitor Set 2 (PKIS2) dataset
(Drewry et al.,, 2017), to evaluate the performances of BoBW-lil’UCB$(\gamma)$
and UCBα in two types of practical applications, namely, content
recommendation and drug recovery. Similarly as in Zong et al., (2016); Hong et
al., (2020); Zhong et al., 2021b ; Mason et al., (2020); Mukherjee et al.,
(2021), we generate data based on the real-world datasets.

ML-25M dataset. GroupLens Research provides a collection of datasets
online,333https://grouplens.org/datasets/movielens including the ML-25M
dataset. These datasets describe the rating activities from MovieLens, a movie
recommendation service, and are widely used to evaluate the performances of
bandit algorithms (Zong et al.,, 2016; Hong et al.,, 2020; Zhong et al.,
2021b, ). The ML-25M dataset contains about $25$ million ratings across about
$62$ thousand movies. We choose movies with a high number of ratings in our
simulations. For each selected movie, we compute the empirical mean rating and
generate random ratings according to a standard Gaussian distribution with the
corresponding mean. We aim to obtain cumulatively high ratings (RM) and
identify the movie with the highest rating (BAI); these are standard
objectives in online recommendation systems.

PKIS2 dataset. This repository444Table 4 in
https://www.biorxiv.org/content/10.1101/104711v1.supplementary-material. tests
$641$ small molecule compounds (kinase inhibitor) against $406$ protein
kinases. This experiment aims to find the most effective inihibitor against a
targeted kinase, and is a fundamental study in cancer drug discovery. The
entries in PKIS2 indicate the _percentage control_ of each inhibitor, which
show the effectiveness of inhibitors and follow log-normal distributions
(Christmann-Franck et al.,, 2016). Accordingly, we generate random variables
as in Mason et al., (2020); Mukherjee et al., (2021) (see Appendix H.4 for
details). We aim to find out the most effective inhibitor with the highest
percentage control against one specific kinase MAPKAPK5, and also obtain high
percentage controls cumulatively during the online learning process. Our study
may aid in understanding how best to design experimental studies that aim to
identify the most effective inhibitor in a fixed number of tests (BAI in a
fixed horizon), as well as to provide effective inhibitors throughout the
course of study (RM).

Figure 6.2: Empirical failure probability $\leq 1\%$. Left: ML-25M dataset;
right: PKIS2 dataset.

On the left of Figure 6.2, we report the results of the experiments on the
$22$ movies with at least $50,000$ ratings from the ML-25M dataset. The other
plot in Figure 6.2 considers the effectiveness of $109$ inhibitors test
against the MAPKAPK5 kinase in the PKIS2 dataset. Both figures suggest that
with high probability, BoBW-lil’UCB$(\gamma)$ can identify the most popular
movie with the highest rating or the most effective inhibitor against MAPKAPK5
with the highest percentage control within a fixed horizon. UCBα takes longer
to do so, and also suffers from a larger regret. These results from the real-
life datasets suggest that given a fixed horizon $T$ and a wide range of
parameters, BoBW-lil’UCB$(\gamma)$ outperforms UCBα in these real-life
instances, which demonstrates the potential of BoBW-lil’UCB$(\gamma)$ in
practical settings.

## References

  * Abbasi-Yadkori et al., (2018) Abbasi-Yadkori, Y., Bartlett, P., Gabillon, V., Malek, A., and Valko, M. (2018).  Best of both worlds: Stochastic & adversarial best-arm identification.  In Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 918–949. PMLR.
  * Abramowitz and Stegun, (1964) Abramowitz, M. and Stegun, I. A. (1964).  Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables.  Dover, New York, ninth edition.
  * Agrawal and Goyal, (2012) Agrawal, S. and Goyal, N. (2012).  Analysis of Thompson sampling for the multi-armed bandit problem.  In Proceedings of the 25th Annual Conference on Learning Theory, pages 39.1–39.26.
  * Agrawal and Goyal, (2013) Agrawal, S. and Goyal, N. (2013).  Thompson sampling for contextual bandits with linear payoffs.  In Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 127–135.
  * Agrawal and Goyal, (2017) Agrawal, S. and Goyal, N. (2017).  Near-optimal regret bounds for Thompson sampling.  Journal of the ACM (JACM), 64(5):1–24.
  * Audibert and Bubeck, (2010) Audibert, J.-Y. and Bubeck, S. (2010).  Best arm identification in multi-armed bandits.  In Proceedings of the 23th Conference on Learning Theory, pages 41–53.
  * (7) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002a).  Finite-time analysis of the multiarmed bandit problem.  Machine Learning, 47(2-3):235–256.
  * (8) Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002b).  The nonstochastic multiarmed bandit problem.  SIAM Journal of Computing, 32(1):48–77.
  * Bubeck et al., (2012) Bubeck, S., Cesa-Bianchi, N., et al. (2012).  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends® in Machine Learning, 5(1):1–122.
  * Bubeck et al., (2009) Bubeck, S., Munos, R., and Stoltz, G. (2009).  Pure exploration in multi-armed bandits problems.  In The 20st International conference on Algorithmic learning theory, pages 23–37. Springer.
  * Bubeck et al., (2013) Bubeck, S., Wang, T., and Viswanathan, N. (2013).  Multiple identifications in multi-armed bandits.  In Proceedings of the 30th International Conference on Machine Learning, pages 258–265.
  * Carpentier and Locatelli, (2016) Carpentier, A. and Locatelli, A. (2016).  Tight (lower) bounds for the fixed budget best arm identification bandit problem.  In Feldman, V., Rakhlin, A., and Shamir, O., editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 590–604, Columbia University, New York, New York, USA. PMLR.
  * Christmann-Franck et al., (2016) Christmann-Franck, S., van Westen, G. J., Papadatos, G., Beltran Escudie, F., Roberts, A., Overington, J. P., and Domine, D. (2016).  Unprecedently large-scale kinase inhibitor set enabling the accurate prediction of compound–kinase activities: A way toward selective promiscuity by design?  Journal of chemical information and modeling, 56(9):1654–1675.
  * Chung and Lu, (2006) Chung, F. and Lu, L. (2006).  Concentration inequalities and martingale inequalities: a survey.  Internet Mathematics, 3(1):79–127.
  * Darling and Robbins, (1967) Darling, D. A. and Robbins, H. (1967).  Iterated logarithm inequalities.  Proceedings of the National Academy of Sciences of the United States of America, 57(5):1188.
  * Degenne et al., (2019) Degenne, R., Nedelec, T., Calauzenes, C., and Perchet, V. (2019).  Bridging the gap between regret minimization and best arm identification, with application to A/B tests.  In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 1988–1996.
  * Drewry et al., (2017) Drewry, D. H., Wells, C. I., Andrews, D. M., Angell, R., Al-Ali, H., Axtman, A. D., Capuzzi, S. J., Elkins, J. M., Ettmayer, P., Frederiksen, M., et al. (2017).  Progress towards a public chemogenomic set for protein kinases and a call for contributions.  PloS one, 12(8):e0181585.
  * Dubhashi and Panconesi, (2009) Dubhashi, D. P. and Panconesi, A. (2009).  Concentration of measure for the analysis of randomized algorithms.  Cambridge University Press.
  * Gabillon et al., (2012) Gabillon, V., Ghavamzadeh, M., and Lazaric, A. (2012).  Best arm identification: A unified approach to fixed budget and fixed confidence.  In Proceedings of the 25th International Conference on Neural Information Processing Systems.
  * Garivier and Cappé, (2011) Garivier, A. and Cappé, O. (2011).  The kl-ucb algorithm for bounded stochastic bandits and beyond.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 359–376.
  * Gerchinovitz and Lattimore, (2016) Gerchinovitz, S. and Lattimore, T. (2016).  Refined lower bounds for adversarial bandits.  In Proceedings of the 29th International Conference on Neural Information Processing Systems, pages 1198–1206.
  * Götze et al., (2019) Götze, F., Sambale, H., and Sinulis, A. (2019).  Higher order concentration for functions of weakly dependent random variables.  Electronic Journal of Probability, 24:1 – 19.
  * Harper and Konstan, (2015) Harper, F. M. and Konstan, J. A. (2015).  The movielens datasets: History and context.  Acm transactions on interactive intelligent systems (tiis), 5(4):1–19.
  * Hong et al., (2020) Hong, J., Kveton, B., Zaheer, M., Chow, Y., Ahmed, A., and Boutilier, C. (2020).  Latent bandits revisited.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Proceedings of the 34th Advances in Neural Information Processing Systems, volume 33, pages 13423–13433. Curran Associates, Inc.
  * Jamieson et al., (2014) Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. (2014).  lil’ucb: An optimal exploration algorithm for multi-armed bandits.  In Proceedings of the 27th Conference on Learning Theory, pages 423–439.
  * Karnin et al., (2013) Karnin, Z., Koren, T., and Somekh, O. (2013).  Almost optimal exploration in multi-armed bandits.  In Proceedings of the 13th International Conference on Machine Learning, pages 1238–1246.
  * Kaufmann et al., (2016) Kaufmann, E., Cappé, O., and Garivier, A. (2016).  On the complexity of best-arm identification in multi-armed bandit models.  The Journal of Machine Learning Research, 17(1):1–42.
  * Kaufmann and Garivier, (2017) Kaufmann, E. and Garivier, A. (2017).  Learning the distribution with largest mean: two bandit frameworks.  ESAIM: Proceedings and surveys, 60:114–131.
  * Kaufmann and Kalyanakrishnan, (2013) Kaufmann, E. and Kalyanakrishnan, S. (2013).  Information complexity in bandit subset selection.  In Proceedings of the 26th Annual Conference on Learning Theory, pages 228–251.
  * Kim et al., (2023) Kim, W., Iyengar, G., and Zeevi, A. (2023).  Pareto front identification with regret minimization.
  * Lai and Robbins, (1985) Lai, T. L. and Robbins, H. (1985).  Asymptotically efficient adaptive allocation rules.  Advances in applied mathematics, 6(1):4–22.
  * Lattimore and Szepesvári, (2020) Lattimore, T. and Szepesvári, C. (2020).  Bandit algorithms.  Cambridge University Press.
  * Mason et al., (2020) Mason, B., Jain, L., Tripathy, A., and Nowak, R. (2020).  Finding all $\epsilon$-good arms in stochastic bandits.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Proceedings of the 34th Advances in Neural Information Processing Systems, volume 33, pages 20707–20718. Curran Associates, Inc.
  * Mukherjee et al., (2021) Mukherjee, A., Tajer, A., Chen, P.-Y., and Das, P. (2021).  Mean-based best arm identification in stochastic bandits under reward contamination.  In Proceedings of the 35th Advances in Neural Information Processing Systems.
  * Russo and Van Roy, (2014) Russo, D. and Van Roy, B. (2014).  Learning to optimize via posterior sampling.  Mathematics of Operations Research, 39(4):1221–1243.
  * Shahrampour et al., (2017) Shahrampour, S., Noshad, M., and Tarokh, V. (2017).  On sequential elimination algorithms for best-arm identification in multi-armed bandits.  IEEE Transactions on Signal Processing, 65(16):4281–4292.
  * Simchi-Levi and Wang, (2023) Simchi-Levi, D. and Wang, C. (2023).  Multi-armed bandit experimental design: Online decision-making and adaptive inference.  In Ruiz, F., Dy, J., and van de Meent, J.-W., editors, Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 3086–3097. PMLR.
  * Tsybakov, (2008) Tsybakov, A. B. (2008).  Introduction to Nonparametric Estimation.  Springer Publishing Company, Incorporated, 1st edition.
  * Wei and Luo, (2018) Wei, C.-Y. and Luo, H. (2018).  More adaptive algorithms for adversarial bandits.  In Proceedings of the 31st Conference on Learning Theory, pages 1263–1291. PMLR.
  * (40) Zhong, Z., Cheung, W. C., and Tan, V. (2021a).  Probabilistic sequential shrinking: A best arm identification algorithm for stochastic bandits with corruptions.  In Proceedings of the 38th International Conference on Machine Learning.
  * (41) Zhong, Z., Cheung, W. C., and Tan, V. (2021b).  Thompson sampling for cascading bandits.  Accepted by Journal of Machine Learning Research.
  * Zimmert and Seldin, (2021) Zimmert, J. and Seldin, Y. (2021).  Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits.  Journal of Machine Learning Research, 22:28–1.
  * Zong et al., (2016) Zong, S., Ni, H., Sung, K., Ke, N. R., Wen, Z., and Kveton, B. (2016).  Cascading bandits for large-scale recommendation problems.  In Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, pages 835–844.

Supplementary Material for
“Achieving the Pareto Frontier of Regret Minimization
( and Best Arm Identification in Multi-Armed Bandits”

In Appendix A, we discuss the existing algorithms and relevant theoretical
findings in stochastic bandits. In Appendix B, we (i) study the performance of
UP-ADV (Audibert and Bubeck,, 2010) and Exp3.P (Auer et al., 2002b, ) for both
RM and BAI in adversarial bandits, and (ii) provide a lower bound on the BAI
failure probability and the Pareto frontier of RM and BAI in adversarial
bandits. In Appendix C, we list the useful facts that are used in the
analysis. In Appendices D to G, we present detailed proofs of our theoretical
results. In Appendix H, more numerical results are provided.

##  Appendix A Detailed discussion on existing algorithms

While most existing works only aim to perform either RM or BAI, Degenne et
al., (2019) designed and analyzed an algorithm called UCBα for both RM and BAI
under the fixed-confidence setting. Given any $\delta$, UCBα aims to minimize
the number of time steps $\tau$ so that $e_{\tau}\leq\delta$, and, at the same
time, the incurred regret $R_{\tau}$ can also be upper bounded. Therefore, the
focus of Degenne et al., (2019) differs from that of our work. We aim to study
the pseudo-regret of an algorithm which can identify the best item with high
probability in a fixed horizon $T$ in this work.

To the best of our knowledge, their is no existing work that analyzes a single
algorithm for both RM and BAI under the fixed-budget setting. However, it is
natural to question if an algorithm which is originally designed for RM can
also perform well for BAI, and vice versa. We study some algorithms that are
originally designed to achieve optimal performance for either RM or BAI.

RM. According to the discussions on RM and BAI in Lattimore and Szepesvári,
(2020) (see the second point in Note 33.3), for any algorithm with a regret
that (nearly) matches the state-of-the-art lower bound (Carpentier and
Locatelli,, 2016):

$\displaystyle\liminf_{T\rightarrow\infty}\frac{R_{T}(\pi)}{\log
T}\geq\sum_{i\neq 1}\frac{\Delta_{1,i}}{\mathrm{KL}(\nu_{i}\|\nu_{1})},$

we can construct two instances $\mathcal{I}$ and $\mathcal{I}^{\prime}$ with

$\displaystyle w_{1}^{\mathcal{I}}>w_{2}^{\mathcal{I}}\geq\ldots\geq
w_{L}^{\mathcal{I}},\qquad
w_{i}^{\mathcal{I}^{\prime}}=w_{i}^{\mathcal{I}}+\varepsilon(w_{1}^{\mathcal{I}}-w_{i}^{\mathcal{I}}),\mbox{
for some }\varepsilon>0$

such that

$\displaystyle
e_{T}(\pi,\mathcal{I})+e_{T}(\pi,\mathcal{I}^{\prime})\geq\Omega(T^{(1+o(1))(1+\varepsilon)^{2}}).$
(A.1)

This serves as a basic observation on the limitation for BAI of an algorithm
that performs (near-)optimally for RM.

BAI. Audibert and Bubeck, (2010) were the first to explore the BAI problem
under the fixed-budget setting. Carpentier and Locatelli, (2016) provided a
lower bound on the failure probability of any algorithm.

In the spirit of UCB1 (Auer et al., 2002a, ), Audibert and Bubeck, (2010)
designed UCB-E for BAI. We let UCB-E$(a)$ denote the UCB-E algorithm when it
is run with parameter $a$. When $T$ is sufficiently large, we can upper bound
the pseudo-regret of UCB-E$(\alpha\log T)$ $(\alpha\geq 2)$ with a similar
analysis as that for UCB1 (see Proof of Theorem 1 in Auer et al., 2002a ).
Besides, we can upper bound its failure probability with Theorem 1 in Audibert
and Bubeck, (2010).

######  Corollary A.1.

Let $\alpha>12.5$. Assume that $g_{i,t}\in[0,1]$ for all $i\in[L]$, and
$\alpha\log T\leq 25(T-L)/(36H_{2})$. UCB-E$(\alpha\log T)$ satisfies

$\displaystyle R_{T}$ $\displaystyle\leq 2\alpha^{2}\sum_{i\neq
1}\bigg{(}\frac{\log
T}{\Delta_{1,i}}\bigg{)}+\bigg{(}1+\frac{\pi^{2}}{3}\bigg{)}\cdot\bigg{(}\sum_{i\neq
1}\Delta_{1,i}\bigg{)},$ $\displaystyle\quad e_{T}$ $\displaystyle\leq
2LT^{(1-2\alpha/25)}.$

When the horizon $T$ grows, Corollary A.1 indicates that the BAI failure
probability of UCB-E$(\alpha\log T)$ decays only polynomially fast. In order
to achieve the upper bound on $e_{T}$ as $\exp(-\Theta(T))$, we need to set
$\alpha=O(T/\log T)$, and hence the regret bound as shown in Corollary A.1
will be $O(T^{2}/\log T)$, which is vacuous.

###  A.1 Existing results under the fixed-budget setting of BAI

We abbreviate Sequential Rejects as SR, Sequential Halving as SH, Nonlinear
Sequential Elimination with parameter $p$ as NSE$(p)$. Besides, we simplify
the bounds for algorithms which were initially analyzed for more general
problems than identification of the optimal item $i^{*}$. we define

$\displaystyle H^{\prime}_{p}:=\max_{i\neq
1}\frac{i^{p}}{\Delta_{i}^{2}},\quad C_{p}:=2^{-p}+\sum_{i=2}^{L}i^{-p}$

for $p>0$ as in Shahrampour et al., (2017). We let UGapEb$(a)$ denote the
UGapEb algorithm when it is run with parameter $a$. In Table A.1, We present
existing bounds from some seminal works. The algorithms are listed in
chronological order.

Table A.1: Comparison under the fixed-budget setting of BAI: upper bounds for
algorithms and lower bounds in stochastic bandits.

Algorithm/Instance | Reference | Failure probability $e_{T}$
---|---|---
UCB-E$\displaystyle\bigg{(}\frac{25(T-L)}{36H_{2}}\bigg{)}$ | Audibert and Bubeck, (2010) | $\displaystyle 2TL\exp\bigg{(}-\frac{T-L}{18H_{2}}\bigg{)}\vphantom{\Bigg{(}}$
SR | Audibert and Bubeck, (2010) | $\displaystyle L(L-1)\exp\bigg{(}-\frac{T-L}{(1/2+\sum_{i=2}^{L}1/i)H_{2}}\bigg{)}\vphantom{\Bigg{(}_{a}}$
UGapEb$\displaystyle\bigg{(}\frac{T-L}{16H_{2}}\bigg{)}$ | Gabillon et al., (2012) | $\displaystyle 2TL\exp\bigg{(}-\frac{T-L}{8H_{2}}\bigg{)}\vphantom{\Bigg{(}}$
SAR | Bubeck et al., (2013) | $\displaystyle 2L^{2}\exp\bigg{(}-\frac{T-L}{8(1/2+\sum_{i=2}^{L}1/i)H_{2}}\bigg{)}\vphantom{\Bigg{(}_{a}}$
SH | Karnin et al., (2013) | $\displaystyle 3\log_{2}L\cdot\exp\bigg{(}-\frac{T}{8H_{2}\log_{2}L}\bigg{)}\vphantom{\Bigg{(}}$
NSE$(p)$ | Shahrampour et al., (2017) | $\displaystyle(L-1)\exp\bigg{(}-\frac{2(T-L)}{H^{\prime}_{p}C_{p}}\bigg{)}\vphantom{\Bigg{(}}$
Stochastic Bandits | Carpentier and Locatelli, (2016) |  $\displaystyle\frac{1}{6}\exp\bigg{(}-\frac{400T}{H_{2}\log L}\bigg{)}$ (Lower Bound)

Since SH and NSE pull a number of items “uniformly” in each phase, we surmise
the regret grows like $\Theta(T)$. For instance, there are $\log L$ many
phases in SH and at least two items are uniformly pulled during each phase, so
at least one non-optimal item $j\neq 1$ is pulled for at least $T/(L\log L)$
times, leading to a regret at least $\Delta_{1,j}\cdot T/(L\log L)$.

As discussed in Shahrampour et al., (2017), $H_{p}^{\prime}C_{p}\leq H_{2}\log
L$ in some special cases. Therefore, SH is better than NSE$(p)$ if we
disregard the sub-exponential term, while NSE$(p)$ is better in some cases in
its dependence on the exponential term. However, they are incomparable in
general.

##  Appendix B Conclusion and Further Discussion on Adversarial Bandits

In Sections 5 and 6, we explore the Pareto frontier of RM and BAI over a fixed
horizon in stochastic bandits. The performance of our BoBW-lil’UCB algorithm
sheds light on the different emphases of RM and BAI. Moreover, we prove that
no algorithm can simultaneously perform optimally for both objectives and
BoBW-lil’UCB nearly achieves the Pareto-optimality in some parameter regimes.
However, as described in the discussion after Corollary 5.4, although our
BoBW-lil’UCB algorithm nearly achieves the Pareto frontier, we acknowledge
that there remains a small gap $\log(1/L)$ which may be closed in the future
by developing another more sophisticated algorithm.

In real-life applications, it may be unrealistic to assume i.i.d. stochastic
rewards,meaning that the stochastic bandit model may not be appropriate. This
brings the study of adversarial bandits (Auer et al., 2002b, ; Abbasi-Yadkori
et al.,, 2018) to the fore. Here, the rewards of each item are not necessarily
drawn independently from the same distribution. In adversarial bandits, while
there exists a lower bound on the regret of any algorithm (Gerchinovitz and
Lattimore,, 2016), there is no lower bound on the failure probability for BAI.
We fill this gap by proving a lower bound
$\Omega(\exp(-150T\underline{\Delta}^{2}))$ in Theorem B.3, where
$\underline{\Delta}$ is the minimal gap between the empirically-optimal items
and the other items (see Appendix B.1 for the definitions). This bound is
almost tight as it nearly matches the upper bound of UP-ADV (Abbasi-Yadkori et
al.,, 2018).

Furthermore, there is no existing analysis of a single algorithm that is
applicable to both RM and BAI in adversarial bandits. We fill this gap by
studying the performance of Exp3.P$(\gamma,\eta)$ (Auer et al., 2002b, ) for
both targets. Theorems B.1 and B.2 imply that by adjusting
Exp3.P$(\gamma,\eta)$ with $\gamma$, we can balance between exploitation and
exploration, and trade-off between the twin objectives: RM and BAI. Besides,
Theorem B.4 implies that no algorithm can simultaneously perform optimally for
both objectives in adversarial bandits. However, since the regret bound of
Exp3.P$(\gamma,\eta)$ is problem-independent, we cannot ascertain if
Exp3.P$(\gamma,\eta)$ achieves the Pareto frontier between RM and BAI. The
further study of the Pareto frontier in adversarial bandits, especially the
stochastically constrained adversarial bandits (Zimmert and Seldin,, 2021; Wei
and Luo,, 2018), may serve as an interesting direction for future work.

Outline. In this section, we first formulate the RM and BAI problem in
adversarial bandits in Appendix B.1. Next, we study the performance of UP-ADV
(Audibert and Bubeck,, 2010) and Exp3.P (Auer et al., 2002b, ) for both RM and
BAI in Appendix B.2. Subsequently, we provide a lower bound on the BAI failure
probability and the Pareto frontier of RM and BAI in Appendix B.3. We
summarize some theoretical findings in Table B.1.

###  B.1 Problem setup for adversarial bandits

In an adversarial bandit instance, we let $g_{i,t}\in[0,1]$ be the reward of
item $i$ at time $t$, and let $G_{i,t}:=\sum_{u=1}^{t}g_{i,u}$ for all $1\leq
t\leq T$. We define the $\bar{\Delta}_{i,j,T}$, _empirical gap_ between item
$i$ and $j$ in $[L]$ and the empirically-optimal item $\bar{i}^{*}_{T}$ as
follows:

$\displaystyle\bar{\Delta}_{i,j,T}:=\frac{1}{T}\cdot(G_{i,t}-G_{j,t}),\quad\bar{i}^{*}_{T}:=\operatorname*{arg\,max}_{1\leq
i\leq L}G_{i,T}.$

Moreover, we define the empirically-minimal optimality gap as

$\displaystyle\bar{\Delta}_{T}:=\min_{j\neq\bar{i}_{T}^{*}}\bar{\Delta}_{\bar{i}_{T}^{*},j}.$

We say an instance is obliviously adversarial555When there is no ambiguity, we
say an instance is adversarial to indicate that it is obliviously
adversarial., if $\\{\bm{g}_{i,t}\\}_{i,t}$ is a sequence of rewards
obliviously generated by the instance before online process. We assume the
empirically-optimal item $\bar{i}_{T}^{*}$ is unique, which implies that
$\bar{\Delta}_{\min,T}>0$.

Moreover, we define the empirical-regret $\bar{R}_{T}^{\pi}$ of an online
algorithm $\pi$ (as defined in Section 2) as

$\displaystyle\bar{R}_{T}^{\pi}:=\max_{1\leq i\leq
L}\sum_{t=1}^{T}g_{i,t}-\sum_{t=1}^{T}g_{i_{t}^{\pi},t}=G_{\bar{i}^{*}_{T},T}^{\mathcal{I}}-\sum_{t=1}^{T}g_{i_{t}^{\pi},t}.$

Recall the definition of pseudo-regret $R_{T}(\pi)$ in Section 2: if an
instance is stochastic, $\mathbb{E}\bar{R}_{T}^{\pi}=R_{T}^{\pi}$; if it is
adversarial, $\mathbb{E}\bar{R}_{T}^{\pi}\leq R_{T}^{\pi}$. The aim of the
agent is slightly different in stochastic and adversarial bandits:

  * •

if the instance is stochastic, the algorithm $\pi$ aims to both minimize the
pseudo-regret $R_{T}(\pi)$ and identify the pseudo-optimal item with high
probability, i.e., to minimize $e_{T}(\pi):=\Pr(i_{\mathrm{out}}^{\pi,T}\neq
i^{*}_{T})$;

  * •

if the instance is adversarial, the algorithm $\pi$ aims to both minimize the
empirical-regret $\bar{R}_{T}(\pi)$ and identify the empirically-optimal item
with high probability, i.e., to minimize
$\bar{e}_{T}(\pi):=\Pr(i_{\mathrm{out}}^{\pi,T}\neq\bar{i}^{*}_{T})$.

We omit $T$ and/or $\pi$ in the superscript or subscript when there is no
cause of confusion. We write $\bar{R}_{T}(\pi)$ as
$\bar{R}_{T}(\pi,\mathcal{I})$, $\bar{e}_{T}(\pi)$ as
$\bar{e}_{T}(\pi,\mathcal{I})$ when we wish to emphasize their dependence on
both the algorithm $\pi$ and the instance $\mathcal{I}$.

###  B.2 Adversarial algorithms: UP-ADV and Exp3.P

We discuss the theoretical performances of two basic algorithms in this
section.

Hence, we take the performance of this basic algorithm as a benchmark to
evaluate any algorithm for this target. Besides, it is clearly that the
uniform pull algorithm is the same as Exp3.P algorithm with $\beta=0$,
$\gamma=1$. We see that UP-ADV satisfies that $\mathbb{E}\bar{R}_{T}\leq T$,
which is consistent with Theorem B.2.

The UP-ADV algorithm. First of all, Abbasi-Yadkori et al., (2018) shows that a
simple algorithm, which is termed as UP-ADV and chooses an item based on the
uniform distribution at each time step $t$, satisfies that

$\displaystyle\bar{e}_{T}\leq
L\exp\bigg{(}-\frac{3T\bar{\Delta}_{T}^{2}}{28L}\bigg{)}.$ (B.1)

Abbasi-Yadkori et al., (2018) claimed that UP-ADV performs near-optimally for
BAI in adversarial bandits, which is verified by our Theorem B.3 in the next
section. Besides, it is obvious that UP-ADV satisfies
$\mathbb{E}\bar{R}_{T}\leq T$.

Algorithm 2 Uniform Pull-ADV (UP-ADV) (Abbasi-Yadkori et al.,, 2018)

1: Input: time budget $T$, size of ground set of items $L$.

2: for $t=1,\ldots,T$ do

3: Choose item $i_{t}\in[L]$ with probability $1/L$.

4: Update the estimated cumulative gain
$\tilde{G}_{i,t}=\sum_{u=1}^{t}g_{i,u}\cdot\mathbb{I}\\{i_{u}=i\\}$.

5: end for

6: Output
$i_{\mathrm{out}}=\operatorname*{arg\,max}_{i\in[L]}\tilde{G}_{i,T}$.

The Exp3.P algorithm. After the Exp3 algorithm and its variations were
proposed by Auer et al., 2002b  for RM in adversarial bandits, this class of
algorithms has been widely discussed as in Lattimore and Szepesvári, (2020);
Bubeck et al., (2012). We present Exp3.P$(\gamma,\eta)$ in Algorithm 3.

Algorithm 3 Exp3.P$(\gamma,\eta)$ (Bubeck et al., (2012), Section 3.3, Fig.
3.1)

1: Input: time budget $T$, size of ground set of items $L$, parameters
$\eta>0$ and $\gamma\in[0,1]$.

2: Set $p_{1}$ be the uniform distribution over $[L]$, i.e., $p_{i,1}=1/L\
\forall i\in[L]$.

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

4: Choose item $i_{t}\in[L]$ with probability $p_{i,1}$.

5: Compute the estimated gain for each item
$\displaystyle\tilde{g}_{i,t}=\frac{g_{i,t}\cdot\mathbb{I}\\{i_{t}=i\\}}{p_{i,t}}$
and update the estimated cumulative gain
$\tilde{G}_{i,t}=\sum_{u=1}^{t}\tilde{g}_{i,u}$.

6: Compute the new probability distribution over the items
$p_{t+1}=(p_{1,t+1},\ldots,p_{L,t+1})$ where  $\displaystyle
p_{i,t+1}=(1-\gamma)\cdot\frac{\exp(\eta\tilde{G}_{i,t})}{\sum_{\ell=1}^{L}\exp(\eta\tilde{G}_{\ell,t})}+\frac{\gamma}{L}.$

7: end for

8: Output
$i_{\mathrm{out}}=\operatorname*{arg\,max}_{i\in[L]}\tilde{G}_{i,T}$.

We first provide the upper bound on the regret of Exp3.P$(\gamma,\eta)$. The
proof is similar to that in Bubeck et al., (2012) and is postponed to Appendix
F.1

######  Theorem B.1 (Bounds on the regret of Exp3.P$(\gamma,\eta)$).

Let $\eta>0$, $\gamma\in[0,1/2]$ satisfying that $L\eta\leq\gamma$. Then we
can upper bound the regret of Exp3.P$(\gamma,\eta)$ as follows. (i) Fix any
given $\delta\in(0,1)$, with probability at least $1-\delta$,

$\displaystyle\bar{R}_{T}\leq\gamma T+\eta
LT+\ln\bigg{(}\frac{L^{2}T}{\eta\delta}\bigg{)}+\frac{\ln L}{\eta}.$

(ii) Moreover,

$\displaystyle\mathbb{E}\bar{R}_{T}\leq\gamma T+\eta
LT+\ln\bigg{(}\frac{L^{2}T}{\eta}\bigg{)}+\frac{\ln L}{\eta}+1.$

We observe that Exp3.P$(1,\eta)$ is exactly the same as UP-ADV, and the
corresponding bound provided in Theorem B.2 is with the same order as in (B.1)
derived by Abbasi-Yadkori et al., (2018). Our upper bound is even slightly
smaller regarding the constants since we apply tighter concentration
inequalities. Next, we upper bound its failure probability to identify the
empirically-optimal item $\bar{i}_{T}^{*}$.

######  Theorem B.2 (Bound on the failure probability of Exp3.P).

Assume $G_{1,T}\geq G_{2,T}\geq\ldots\geq G_{L,T}$. We see that the optimal
item $\bar{i}_{T}^{*}=1$. The failure probability of Exp3.P$(\gamma,\eta)$
satisfies

$\displaystyle\bar{e}_{T}\leq\exp\bigg{(}-\frac{\gamma
T\bar{\Delta}_{1,2,T}^{2}}{4L}\bigg{)}+\sum_{i=2}^{L}\exp\bigg{(}-\frac{3\gamma
T(\bar{\Delta}_{1,2,T}/2+\bar{\Delta}_{2,i,T})^{2}}{L(3+\bar{\Delta}_{1,2,T}/2+\bar{\Delta}_{2,i,T})}\bigg{)}\leq
L\exp\bigg{(}-\frac{\gamma T\bar{\Delta}_{T}^{2}}{4L}\bigg{)}.$

The key idea among the analysis of Theorem B.2 is to derive high-probability
one-sided bounds on $\tilde{G}_{i,T}-G_{i,T}$ for all $i\in[L]$ with Theorems
C.2 and C.3. The detailed proof is postponed to Appendix F.2.

Theorems B.1 and B.2 imply that by adjusting Exp3.P$(\gamma,\eta)$ with
$\gamma$, we can balance between exploitation and exploration and trade-off
between the twin objectives — RM and BAI. In detail,

  * •

When $\gamma$ increases, the Exp3.P$(\gamma,\eta)$ algorithm tends to bahave
more similarly to UP-ADV, which leads to a larger regret and a smaller failure
probability. This indicates that a large $\gamma$ encourages exploitation.

  * •

When $\gamma$ decreases, the Exp3.P$(\gamma,\eta)$ algorithm tends to
emphasize more on the observation from previous time steps and pull the items
with high empirically means, which leads to a smaller regret and a larger
failure probability. In other words, a small $\gamma$ encourages exploitation.

###  B.3 Global performances of adversarial algorithms

In this section, we first lower bound the failure probability to identify the
empirically-optimal item in adversarial bandits. Next, given a certain failure
probability of an algorithm, we establish a non-trivial lower bound on its
empirical-regret. The proofs are in Appendix G.

We consider bandit instances in which items have bounded rewards. Let
$\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},\bar{R})$ denote the set of
instances where (i) the empirically-minimal optimality gap
$\bar{\Delta}_{T}\geq\underline{\Delta}_{T}$ in $T$ time steps; and (ii) there
exists $R_{0}\in\mathbb{R}$ such the rewards are bounded in $[R_{0},R_{0}+R]$.
We focus on $\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},1)$ for brevity; the
analysis can be generalized for any
$\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},\bar{R})$.

####  B.3.1 Lower bound on the BAI failure probability in adversarial bandits

######  Theorem B.3.

Let $0<\underline{\Delta}_{T}\leq 1$. Then any algorithm $\pi$ satisfies that

$\displaystyle\sup_{\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},1)}\bar{e}_{T}(\pi,\mathcal{I})\geq\frac{1-\exp(-{3T}/{200})}{4}\cdot\exp\bigg{(}-\frac{150T\underline{\Delta}_{T}^{2}}{L}\bigg{)}.$

Furthermore, when $T\geq 10$,

$\displaystyle\sup_{\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},1)}\bar{e}_{T}(\pi,\mathcal{I})\geq\frac{2}{65}\exp\bigg{(}-\frac{150T\underline{\Delta}_{T}^{2}}{L}\bigg{)}.$

We construct $L$ instances with clipped Gaussian distributions, which are
similar to those designed for the analysis of lower bound on regret in
Gerchinovitz and Lattimore, (2016).

Besides, the gap between our lower bound in Theorem B.3 and the upper bounds
of UP-ADV/Exp3.P$(1,\eta)$ in (B.1) and Theorem B.2 is manifested by the (pre-
exponential) term $L$ as well as the constant in the exponential term. This
indicates that UP-ADV/Exp3.P$(1,\eta)$ perform near-optimally for BAI and our
lower bound in Theorem B.3 is almost tight.

####  B.3.2 Trade-off between RM and BAI in adversarial bandits

######  Theorem B.4.

Let $0<\underline{\Delta}_{T}\leq 1$ and $T\geq 10$. Let $\pi$ be any
algorithm with $\bar{e}_{T}(\pi,\mathcal{I})\leq 2\exp(-\psi_{T})/65$ for all
$\mathcal{I}\in\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},1)$. Then

$\displaystyle\sup_{\mathcal{I}\in\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},1)}\mathbb{E}\bar{R}_{T}(\pi,\mathcal{I})\geq\psi_{T}\cdot\frac{L-1}{103\underline{\Delta}_{T}}.$

Theorem B.4 implies that, as shown for the stochastic bandits (see Theorems
5.1 and 5.3), we cannot achieve optimal performances for both RM and BAI using
any algorithm with fixed parameters in adversarial bandits. Besides, Theorems
B.2 and B.4 indicates that

$\displaystyle\sup_{\mathcal{I}\in\bar{\mathcal{B}}_{1}(\underline{\Delta}_{T},1)}\mathbb{E}\bar{R}_{T}(\textsc{Exp3.P$(\gamma,\eta)$},\mathcal{I})\geq\bigg{(}\log\bigg{(}\frac{2}{65}\bigg{)}+\frac{\gamma
T\underline{\Delta}_{T}^{2}}{4L}\bigg{)}\cdot\frac{L-1}{103\underline{\Delta}_{T}}=\Omega(\gamma
T\bar{\Delta}_{T}).$

However, since the upper bound on the regret of Exp3.P$(\gamma,\eta)$ in
Theorem B.1 is problem-independent, we cannot ascertain if the algorithm
achieves the Pareto optimality, which may serve as an interesting direction
for future work. Lastly, we summarize some theoretical findings of the
adversarial bandits in Table B.1.

Table B.1: Comparison among upper bounds for algorithms and lower bounds in adversarial bandits.  Algorithm/Instance | Expected empirical-regret $\mathbb{E}\bar{R}_{T}$ | Failure Probability $\bar{e}_{T}$
---|---|---
UP-ADV | ${\Theta}(T)$ | $\displaystyle L\exp\bigg{(}-\frac{3T\bar{\Delta}_{T}^{2}}{28L}\bigg{)}\vphantom{\Bigg{(}}$
| (Abbasi-Yadkori et al.,, 2018)
Exp3.P$(\gamma,\eta)$ |  $\displaystyle\gamma T+\eta LT+\ln\bigg{(}\frac{L^{2}T}{\eta}\bigg{)}+\frac{\ln L}{\eta}+1$ aaa | $\displaystyle L\exp\bigg{(}-\frac{\gamma T\bar{\Delta}_{T}^{2}}{4L}\bigg{)}\vphantom{\Bigg{(}}$
(Theorem B.1 ) | (Theorem B.2)
Adversarial Bandits |  | $\displaystyle\frac{2}{65}\exp\bigg{(}-\frac{150T\bar{\Delta}_{T}^{2}}{L}\bigg{)}\vphantom{\Bigg{(}}$
|  | (Lower Bound, Theorem B.3)
Adversarial Bandits | $\displaystyle\psi_{T}\cdot\frac{L-1}{103\underline{\Delta}_{T}}$ | $\displaystyle\frac{2}{65}\exp(-\psi_{T})\vphantom{\Bigg{(}}$
| (Lower Bound, Theorem B.4 ) | (Theorem B.4)

##  Appendix C Useful facts

###  C.1 Concentration

######  Theorem C.1 (Non-asymptotic law of the iterated logarithm; Jamieson et
al., (2014), Lemma 3).

Let $X_{1},X_{2},\ldots$ be $i.i.d.$ zero-mean sub-Gaussian random variables
with scale $\sigma>0;$ i.e. $\mathbb{E}[\mathrm{e}^{\lambda
X_{i}}]\leq\exp({\lambda^{2}\sigma^{2}}/{2}).$ For all $\varepsilon\in(0,1)$
and $\gamma\in(0,\log(1+\varepsilon)/e)$, we have

$\Pr\bigg{(}\forall\tau\geq
1,\frac{1}{\tau}\sum_{s=1}^{\tau}X_{s}\leq\sigma(1+\sqrt{\varepsilon})\sqrt{\frac{2(1+\varepsilon)}{\tau}\cdot\log\bigg{(}\frac{\log((1+\varepsilon)\tau)}{\gamma}\bigg{)}}~{}\bigg{)}\geq
1-\frac{2+\varepsilon}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

######  Theorem C.2 (Chung and Lu, (2006), Theorem 20).

Let $X_{1},\cdots,X_{n}$ be a martingale adapted to filtration
$\mathcal{F}=(\mathcal{F}_{i})_{i}$ satisfying

  1. 1.

$\operatorname{\mathrm{Var}}(X_{i}|\mathcal{F}_{i-1})\leq\sigma_{i}^{2}$, for
$1\leq i\leq n$;

  2. 2.

$X_{i}-X_{i-1}\leq a_{i}+M$, for $1\leq i\leq n$.

Then we have

$\displaystyle\Pr\left(X_{n}-\mathbb{E}X_{n}\geq\lambda\right)\leq\exp\left(-\frac{\lambda^{2}}{2[\sum_{i=1}^{n}(\sigma_{i}^{2}+a_{i}^{2})+M\lambda/3]}\right).$

######  Theorem C.3 (Chung and Lu, (2006), Theorem 22).

Let $X_{1},\cdots,X_{n}$ be a martingale adapted to filtration
$\mathcal{F}=(\mathcal{F}_{i})_{i}$ satisfying

  1. 1.

$\operatorname{\mathrm{Var}}(X_{i}|\mathcal{F}_{i-1})\leq\sigma_{i}^{2}$, for
$1\leq i\leq n$;

  2. 2.

$X_{i-1}-X_{i}\leq a_{i}+M$, for $1\leq i\leq n$.

Then we have

$\displaystyle\Pr\left(X_{n}-\mathbb{E}X_{n}\leq-\lambda\right)\leq\exp\left(-\frac{\lambda^{2}}{2[\sum_{i=1}^{n}(\sigma_{i}^{2}+a_{i}^{2})+M\lambda/3]}\right).$

######  Theorem C.4 (Abramowitz and Stegun, (1964), Formula 7.1.13; Agrawal
and Goyal, (2013), Lemma 6; Agrawal and Goyal, (2017), Fact 4).

Let $Z\sim{\cal N}(\mu,\sigma^{2})$. The following inequalities hold:

$\displaystyle\frac{1}{2\sqrt{\pi}}\exp\bigg{(}-\frac{7z^{2}}{2}\bigg{)}$
$\displaystyle{\leq}\Pr_{Z}(|Z-\mu|>z\sigma){\leq}\exp\bigg{(}-\frac{z^{2}}{2}\bigg{)}$
$\displaystyle\forall z>0,$
$\displaystyle\frac{1}{2\sqrt{\pi}z}\exp\bigg{(}-\frac{z^{2}}{2}\bigg{)}$
$\displaystyle{\leq}\Pr_{Z}(|Z-\mu|>z\sigma){\leq}\frac{\sqrt{2}}{\sqrt{\pi}z}\exp\bigg{(}-\frac{z^{2}}{2}\bigg{)}$
$\displaystyle\forall z\geq 1.$

######  Theorem C.5 (Standard multiplicative variant of the Chernoff-Hoeffding
bound; Dubhashi and Panconesi, (2009), Theorem 1.1).

Suppose that $X_{1},\ldots,X_{T}$ are independent $[0,1]$-valued random
variables, and let $X=\sum^{T}_{t=1}X_{t}$. Then for all
$\varepsilon\in(0,1)$,

$\displaystyle\Pr(X-\mathbb{E}X\geq\varepsilon\mathbb{E}X)\leq\exp\bigg{(}-\frac{\varepsilon^{2}}{3}\mathbb{E}X\bigg{)},\
\Pr(X-\mathbb{E}X\leq-\varepsilon\mathbb{E}X)\leq\exp\bigg{(}-\frac{\varepsilon^{2}}{3}\mathbb{E}X\bigg{)}.$

###  C.2 Change of measure

######  Lemma C.6 (Tsybakov, (2008), Lemma 2.6).

Let $P$ and $Q$ be two probability distributions on the same measurable space.
Then, for every measurable subset $A$ (whose complement we denote by
$\bar{A}$),

$\displaystyle P(A)+Q(\bar{A})\geq\frac{1}{2}\exp(-\mathrm{KL}(P\parallel
Q)).$

######  Lemma C.7 (Gerchinovitz and Lattimore, (2016), Lemma 1).

Consider two instances $1$ and $2$. We let $N_{i,t}$ denote the number of
pulls of item $i$ up to and including time step $t$. Under instance $j$
($j=1,2$),

  * •

we let $(g_{i,t}^{j})_{t=1}^{T}$ be the sequence of rewards of item $i$ and
$i_{t}^{j}$ be the pulled item at time step $t$, and let $P_{j,i}$ denote the
distribution of the gain of item $i$;

  * •

we assume
$\\{\bm{g}_{t}^{j}=(g_{1,t}^{j},g_{2,t}^{j},\ldots,g_{L,t}^{j})\\}_{t=1}^{T}$
is an i.i.d. sequence, i.e., $\bm{g}_{t_{1}}^{j}$ and $\bm{g}_{t_{2}}^{j}$ are
i.i.d. for $t_{1}\neq t_{2}$ but $\\{g_{i,t}^{j}\\}_{i=1}^{L}$ can be
independent.

  * •

we let $i_{t}^{j}$ be the pulled item at time step $t$, and let
$\mathbb{P}_{j}$ denote the probability law of the process
$\\{\\{i_{t}^{j},g_{i_{t}^{j},t}^{j}\\}\\}_{t=1}^{T}$.

Then, we have

$\displaystyle\mathrm{KL}(\mathbb{P}_{1}\parallel\mathbb{P}_{2})=\sum_{i=1}^{L}\mathbb{E}_{\mathbb{P}_{1}}[N_{i,T}]\cdot\mathrm{KL}(P_{1,i}\parallel
P_{2,i}).$

###  C.3 KL divergence

######  Theorem C.8 (Pinsker’s and reverse Pinsker’s inequality; Götze et al.,
(2019), Lemma 4.1).

Let $P$ and $Q$ be two distributions that are defined in the same finite space
$\mathcal{A}$ and have the same support. We have

$\displaystyle\delta(P,Q)^{2}\leq\frac{1}{2}\mathrm{KL}(P,Q)\leq\frac{1}{\alpha_{Q}}\delta(P,Q)^{2}$

where $\delta(P,Q)=\sup\\{\ |P(A)-Q(A)|\
\big{|}A\subset\mathcal{A}\\}=\frac{1}{2}\sum_{x\in\mathcal{A}}|P(x)-Q(x)|$ is
the total variational distance, and $\alpha_{Q}=\min_{x\in X:Q(x)>0}Q(x)$.

######  Lemma C.9 (KL divergence between two Gaussian distributions).

Let $P_{1}=\mathcal{N}(\mu_{1},\sigma_{1}^{2})$,
$P_{2}=\mathcal{N}(\mu_{2},\sigma_{2}^{2})$. Then

$\displaystyle\mathrm{KL}(P_{1}||P_{2})=\log\bigg{(}\frac{\sigma_{2}}{\sigma_{1}}\bigg{)}+\frac{\sigma_{1}^{2}+(\mu_{1}-\mu_{2})^{2}}{2\sigma_{2}^{2}}-\frac{1}{2}.$

######  Lemma C.10 (KL divergence between clipped Gaussian distributions;
Lemma 7, Gerchinovitz and Lattimore, (2016)).

Let $Z$ be normally distributed with mean $1/2$ and variance $\sigma^{2}>0$.
Let $\mathrm{clip}_{[a,b]}x:=\max\\{a,\min\\{b,x\\}\\}$ for $a\leq b$. Define
$X=\mathrm{clip}_{[0,1]}(Z)$ and $Y=\mathrm{clip}_{[0,1]}(Z-\varepsilon)$ for
$\varepsilon\in\mathbb{R}$. Then

$\mathrm{KL}(P_{X}\parallel P_{Y})\leq\frac{\varepsilon^{2}}{2\sigma^{2}}.$

##  Appendix D Analysis of BoBW-lil’UCB$(\gamma)$ in stochastic bandits

######  Proposition D.1 (Bounds on the pseudo-regret of BoBW-
lil’UCB$(\gamma)$).

Assume the distribution $\nu_{i}$ is sub-Gaussian with scale $\sigma>0$ for
all $i\in[L]$, and $w_{1}\geq w_{2}\geq\ldots\geq w_{L}$. Let
$\varepsilon\in(0,1)$, $\beta\geq 0$, and
$\gamma\in(0,\min\\{\log(\beta+1+\varepsilon)/e),1\\})$. The pseudo-regret of
BoBW-lil’UCB$(\gamma)$ satisfies

$\displaystyle R_{T}\leq
O\bigg{(}\sigma^{2}(1+\varepsilon)^{3}\cdot\sum_{i:\Delta_{1,i}>0}\frac{\log({1}/{\gamma})}{\Delta_{1,i}}\bigg{)},\quad
R_{T}\leq
O\bigg{(}\sigma^{2}(1+\varepsilon)^{3}\sqrt{TL}\log\bigg{(}\frac{\log(T/L\gamma)}{\gamma}\bigg{)}~{}\bigg{)}.$

Furthermore, we can set $\gamma=1/\sqrt{T}$ to obtain

$\displaystyle R_{T}\leq
O\bigg{(}\sigma^{2}(1+\varepsilon)^{3}\cdot\sum_{i:\Delta_{1,i}>0}\frac{\log
T}{\Delta_{1,i}}\bigg{)},\quad R_{T}\leq
O\big{(}\sigma^{2}(1+\varepsilon)^{3}\sqrt{TL}\log T~{}\big{)}.$

###  D.1 Proof of Theorem 4.1

See 4.1

###### Proof.

Recall that we assume $w_{1}>w_{2}\geq\ldots\geq w_{L}$. Therefore, item $1$
is optimal and $\Delta_{1,j}>0$ for all $j\neq 1$.

Step 1: Concentration. Let $\mathcal{E}_{i,\gamma}:=\\{\forall t\geq
L,|\hat{g}_{i,t}-w_{i}|\leq C_{i,t,\gamma}\\}$ for all $i\in[L]$. We apply
Theorem C.1 to show that $\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}$ holds with
high probability.

######  Lemma D.2 (Concentration of $\hat{g}_{i,t}$).

Fix any $\varepsilon\in(0,1)$ and $\gamma\in(0,\log(\beta+1+\varepsilon)/e)$.
We have

$\displaystyle\Pr\bigg{(}\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}\bigg{)}\geq
1-\frac{2L(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

Step 2: Bound on $N_{i,T}$ for $i\neq 1$. Next, for all $t>L$, when

$\displaystyle\\{~{}\hat{g}_{1,t-1}>w_{1}-C_{1,t-1,\gamma},\quad\hat{g}_{i,t-1}<w_{i}+C_{i,t-1,\gamma},\quad\Delta_{1,i}>2C_{i,t-1,\gamma},\quad\forall
i\neq 1\\}$

holds, we have

$\displaystyle\\{~{}U_{1,t-1,\gamma}=\hat{g}_{1,t-1}+C_{1,t-1,\gamma}>w_{1}=w_{i}+\Delta_{1,i}>w_{i}+2C_{i,t-1,\gamma}>\hat{g}_{i,t-1}+C_{i,t-1,\gamma}=U_{i,t-1,\gamma}\quad\forall
i\neq 1~{}\\},$

which indicates $i_{t}=1$. In other words, when $i_{t}=i\neq 1$ for $t>L$, one
of the following holds:

$\displaystyle\hat{g}_{1,t-1}\leq
w_{1}-C_{1,t-1,\gamma},\quad\hat{g}_{i,t-1}\geq
w_{i}+C_{i,t-1,\gamma},\quad\Delta_{1,i}\leq 2C_{i,t-1,\gamma},$

We see that

$\displaystyle\Delta_{1,i}\leq
2C_{i,t-1,\gamma}=10\sigma(1+\sqrt{\varepsilon})\sqrt{\frac{2(1+\varepsilon)}{N_{i,t-1}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}}$
$\displaystyle\Leftrightarrow~{}$ $\displaystyle
N_{i,t-1}\leq\frac{200\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{1,i}^{2}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}.$

In order to bound $N_{i,t-1}$, we derive the following lemma:

######  Lemma D.3.

For all $\tau>0$, $1.4ac/\rho+b\geq e$, we have

$\displaystyle\tau\leq
c\log\bigg{(}\frac{\log(a\tau+b)}{\rho}\bigg{)}~{}\Rightarrow~{}\tau\leq
c\log\bigg{(}\frac{1.4}{\rho}\log\bigg{(}\frac{1.4ac}{\rho}+b\bigg{)}\bigg{)}.$

We apply Lemma D.3 with

$\displaystyle
c=\frac{200\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{1,i}^{2}},\quad
a=1+\varepsilon,\text{ and }~{}\rho=\gamma,$

to obtain

$\displaystyle
N_{i,t-1}\leq\frac{200\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{1,i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{200a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{1,i}^{2}\gamma}+\beta\bigg{)}\bigg{)}:=\bar{N}_{i,\gamma}.$

$1.4ac/\rho+b\geq e$ is satisfied when $\gamma\in(0,1)$. Therefore, when
$t>L$, $\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}$ holds and
$N_{i,t-1}>\bar{N}_{i,\gamma}$ for all $i\neq 1$, we always have $i_{t}=1$.

Step 3: Conclusion. Consequently,

$\displaystyle R_{T}$
$\displaystyle=\mathbb{E}\bigg{[}\sum_{t=1}^{T}g_{1,t}-g_{i_{t},t}\bigg{]}=\mathbb{E}\bigg{[}\bigg{(}\sum_{t=1}^{T}g_{1,t}-g_{i_{t},t}\bigg{)}\cdot\mathsf{1}\bigg{(}\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}\bigg{)}\bigg{]}+\mathbb{E}\Bigg{[}\bigg{(}\sum_{t=1}^{T}g_{1,t}-g_{i_{t},t}\bigg{)}\cdot\mathsf{1}\Bigg{(}~{}\overline{\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}}~{}\Bigg{)}\Bigg{]}$
$\displaystyle\leq\mathbb{E}\bigg{[}\bigg{(}\sum_{t=1}^{T}g_{1,t}-g_{i_{t},t}\bigg{)}\cdot\mathsf{1}\bigg{(}\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}\bigg{)}\bigg{]}+T\cdot\Pr\Bigg{(}~{}\overline{\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}}~{}\Bigg{)}$
$\displaystyle\leq\sum_{j\neq
1}\mathbb{E}\bigg{[}\bigg{(}\sum_{t=1}^{T}g_{1,t}-g_{i_{t},t}\bigg{)}\cdot\mathsf{1}\bigg{(}i_{t}=j,\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}\bigg{)}\bigg{]}+T\cdot\Pr\Bigg{(}~{}\overline{\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}}~{}\Bigg{)}$
$\displaystyle\leq\sum_{j\neq
1}\Delta_{1,j}\cdot\mathbb{E}\bigg{[}\sum_{t=1}^{T}\cdot\mathsf{1}(i_{t}=j)~{}\bigg{|}~{}\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}\bigg{]}+T\cdot\Pr\Bigg{(}~{}\overline{\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}}~{}\Bigg{)}$
$\displaystyle=\sum_{j\neq
1}\Delta_{1,j}\cdot\mathbb{E}\bigg{[}N_{j,T}~{}\bigg{|}~{}\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}\bigg{]}+T\cdot\Pr\Bigg{(}~{}\overline{\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}}~{}\Bigg{)}$
$\displaystyle\leq\sum_{j\neq
1}\Delta_{1,j}\cdot(2+\bar{N}_{j,\gamma})+T\cdot\Pr\Bigg{(}~{}\overline{\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}}~{}\Bigg{)}$
$\displaystyle=\sum_{i\neq 1}2\Delta_{1,i}+\sum_{i\neq
1}\frac{200\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{1,i}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{200a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{1,i}^{2}\gamma}+\beta\bigg{)}\bigg{)}$
$\displaystyle\hskip
20.00003pt+\frac{2TL(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}$
$\displaystyle=\sum_{i\neq 1}2\Delta_{1,i}+\sum_{i\neq
1}\frac{200\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{1,i}}\cdot\log\bigg{(}\frac{2a_{1}}{\gamma}\log\bigg{(}\frac{10\sqrt{2a_{1}}\cdot\sigma(1+\sqrt{\varepsilon})(1+\varepsilon)}{\Delta_{1,i}\sqrt{\gamma}}+\beta\bigg{)}\bigg{)}$
$\displaystyle\hskip
20.00003pt+\frac{2TL(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

We see that $a_{1}=1.4\leq 2$. If we divide the ground set into two classes
depending on whether $\Delta_{1,i}\geq\sqrt{L/T}$, we have

$\displaystyle R_{T}$ $\displaystyle\leq
T\cdot\sqrt{\frac{L}{T}}+2L+\frac{200L\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\sqrt{L/T}}\log\bigg{(}\frac{4}{\gamma}\log\bigg{(}\frac{20\sigma(1+\sqrt{\varepsilon})(1+\varepsilon)}{\sqrt{L/T}\sqrt{\gamma}}+\beta\bigg{)}\bigg{)}$
$\displaystyle\hskip
20.00003pt+\frac{2TL(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}$
$\displaystyle=\sqrt{TL}\cdot\bigg{[}1+200\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)\log\bigg{(}\frac{4}{\gamma}\log\bigg{(}\frac{20\sigma(1+\sqrt{\varepsilon})(1+\varepsilon)}{\sqrt{\gamma
L/T}}+\beta\bigg{)}\bigg{)}\bigg{]}$ $\displaystyle\hskip
20.00003pt+2L+\frac{2TL(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

In short, we have

$\displaystyle R_{T}$ $\displaystyle\leq O\bigg{(}\sigma^{2}\cdot\sum_{i\neq
1}\frac{\log({1}/{\gamma})}{\Delta_{1,i}}+2TL\gamma^{1+\varepsilon}\bigg{)},$
$\displaystyle R_{T}$ $\displaystyle\leq
O\bigg{(}\sigma^{2}\sqrt{TL}\log\bigg{(}\frac{\log(T/L\gamma)}{\gamma}\bigg{)}+2TL\gamma^{1+\varepsilon}~{}\bigg{)}.$

Let $\gamma=(\log T)/{T}$, we have

$\displaystyle R_{T}\leq O\bigg{(}\sigma^{2}\cdot\sum_{i\neq 1}\frac{\log
T}{\Delta_{1,i}}\bigg{)},\quad R_{T}\leq O\big{(}\sigma^{2}\sqrt{TL}\log
T~{}\big{)}.$

∎

###  D.2 Proof of Theorem 4.2

See 4.2

###### Proof.

Recall that we assume $w_{1}>w_{2}\geq\ldots\geq w_{L}$. We let
$\Delta_{1}=w_{1}-w_{2}$ and $\Delta_{i}=w_{1}-w_{i}$ for all $i\neq 1$. Then
$\Delta=\Delta_{1}$ and $\Delta_{1,i}=\Delta_{i}$ for $i\neq 1$.

Step 1: Concentration. Let $\mathcal{E}^{\prime}_{i,\gamma}:=\\{\forall t\geq
L,|\hat{g}_{i,t}-w_{i}|\leq C_{i,t,\gamma}/5\\}$ for all $i\in[L]$. Similarly
to Lemma D.2, we can apply Theorem C.1 to show that

$\displaystyle\Pr\bigg{(}\bigcap_{i=1}^{L}\mathcal{E}^{\prime}_{i,\gamma}\bigg{)}\geq
1-\frac{2L(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

In the following, we prove that conditioning on the event
$\big{\\{}\bigcap_{i=1}^{L}\mathcal{E}^{\prime}_{i,\gamma}\big{\\}}$, we have
$i_{\mathrm{out}}=1$, which concludes the proof.

We assume $\bigcap_{i=1}^{L}\mathcal{E}^{\prime}_{i,\gamma}$ holds from now
on. Since $i_{\mathrm{out}}$ is the item with the largest empirical mean, we
have

$\displaystyle\hat{g}_{i_{\mathrm{out}},T}\geq\hat{g}_{i,t}\quad\forall i\neq
i_{\mathrm{out}},\quad\hat{g}_{i_{\mathrm{out}},T}\geq
w_{i_{\mathrm{out}}}-C_{i_{\mathrm{out}},T,\gamma}/5,\quad
w_{i}+C_{i,T,\gamma}/5\geq\hat{g}_{i,t}\quad\forall i\neq i_{\mathrm{out}}.$

Consequently, to show $i_{\mathrm{out}}=1$, it is sufficient to show that

$\displaystyle\frac{C_{i,T,\gamma}}{5}\leq\frac{\Delta_{i}}{2}~{}\Leftrightarrow~{}$
$\displaystyle\Delta_{i}\geq\frac{2C_{i,T,\gamma}}{5}=2\sigma(1+\sqrt{\varepsilon})\sqrt{\frac{2(1+\varepsilon)}{N_{i,T}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,T})}{\gamma}\bigg{)}}$
$\displaystyle\Leftrightarrow~{}$ $\displaystyle
N_{i,T}\geq\frac{8\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,T})}{\gamma}\bigg{)}\quad\forall
i\in[L].$ (D.1)

Step 2: Upper bound $N_{i,T}~{}(i\neq 1)$. To begin with, we let $a_{1}=2$ and
prove prove by induction that

$\displaystyle
N_{i,t}\leq\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{72a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{i}^{2}\gamma}+\beta\bigg{)}~{}\bigg{)}+1\quad\forall
i\neq 1.$ (D.2)

Clearly, this inequality holds for all $i\neq 1$ when $1\leq t\leq L$. Now we
assume that the inequality holds for all $i\neq 1$ at time $t-1(t>L)$. If
$i_{t}\neq i$, we have $N_{i,t}=N_{i,t-1}$ and the inequality still holds for
$i$. Otherwise, we have $i_{t}=i$ and in particular $U_{i,t-1,\gamma}\geq
U_{1,t-1,\gamma}$. Since

$\displaystyle U_{i,t-1,\gamma}=\hat{g}_{i,t-1}+C_{i,t-1,\gamma}\leq
w_{i}+\frac{6C_{i,t-1,\gamma}}{5},\quad
U_{1,t-1,\gamma}=\hat{g}_{1,t-1}+C_{1,t-1,\gamma}\geq
w_{1}+\frac{4C_{1,t-1,\gamma}}{5}\geq w_{1}=w_{i}+\Delta_{i},$

we have

$\displaystyle\frac{6C_{i,t-1,\gamma}}{5}\geq\Delta_{i}$
$\displaystyle~{}\Leftrightarrow~{}N_{i,t-1}\leq\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}$
$\displaystyle~{}\overset{(a)}{\Rightarrow}~{}N_{i,t-1}\leq\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{72a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{i}^{2}\gamma}+\beta\bigg{)}~{}\bigg{)}.$

We obtain (a) using Lemma D.3 with $\gamma\in(0,1)$: See D.3 Subsequently, by
using $N_{i,t}=N_{i,t-1}+1$, we obtain (D.2).

Step 3: Lower bound $N_{i,T}~{}(i\neq 1)$. Next, we again prove by induction
that

$\displaystyle N_{i,t}\geq
200\sigma^{2}(1+\varepsilon)(1+\sqrt{\varepsilon})^{2}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t})}{\gamma}\bigg{)}\cdot\min\bigg{\\{}\frac{1}{25\Delta_{i}^{2}},\quad\frac{1}{36(C_{1,t-1,\gamma})^{2}}\bigg{\\}},\quad\forall
i\neq 1.$ (D.3)

Clearly, this inequality holds for all $i\neq 1$ when $1\leq t\leq L$. Now we
assume that these inequalities hold for all $i\neq 1$ at time $t-1(t>L)$. If
$i_{t}\neq 1$, we have

$N_{i,t}\geq N_{i,t-1}\quad\forall i\neq 1,\quad N_{1,t}=N_{1,t-1},$

which implies that the inequalities still hold for all $i\neq 1$. Otherwise,
$i_{t}=1$ indicates that $U_{1,t-1,\gamma}\geq U_{i,t-1,\gamma}$ for all
$i\neq 1$. Since

$\displaystyle U_{1,t-1,\gamma}=\hat{g}_{1,t-1}+C_{1,t-1,\gamma}\leq
w_{1}+\frac{6C_{1,t-1,\gamma}}{5},\quad
U_{i,t-1,\gamma}=\hat{g}_{i,t-1}+C_{i,t-1,\gamma}\geq
w_{i}+\frac{4C_{i,t-1,\gamma}}{5},$

we have

$\displaystyle\frac{4C_{i,t-1,\gamma}}{5}\leq\Delta_{i}+\frac{6C_{1,t-1,\gamma}}{5}$
$\displaystyle\Leftrightarrow~{}$ $\displaystyle
C_{i,t-1,\gamma}=5\sigma(1+\sqrt{\varepsilon})\sqrt{\frac{2(1+\varepsilon)}{N_{i,t-1}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}}\leq\frac{5\Delta_{i}+6C_{1,t-1,\gamma}}{4}$
$\displaystyle\Leftrightarrow~{}$
$\displaystyle\frac{20\sigma(1+\sqrt{\varepsilon})}{5\Delta_{i}+6C_{1,t-1,\gamma}}\cdot\sqrt{\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}}\leq\sqrt{\frac{N_{i,t-1}}{2(1+\varepsilon)}}$
$\displaystyle\Leftrightarrow~{}$
$\displaystyle\frac{400\sigma^{2}(1+\sqrt{\varepsilon})^{2}}{(5\Delta_{i}+6C_{1,t-1,\gamma})^{2}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}\leq\frac{N_{i,t-1}}{2(1+\varepsilon)}$
$\displaystyle\Leftrightarrow~{}$ $\displaystyle
N_{i,t-1}\geq\frac{800\sigma^{2}(1+\varepsilon)(1+\sqrt{\varepsilon})^{2}}{(5\Delta_{i}+6C_{1,t-1,\gamma})^{2}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}.$

We apply $u+v\leq 2\max\\{u,v\\}$ and $N_{i,t}=N_{i,t-1}$ for all $i\neq 1$ to
obtain (D.3).

Step 4: Lower bound on $N_{1,T}$. Recall that we want to show (D.1). (i) To
show (D.1) holds for all $i\neq 1$, (D.3) indicates that it is sufficiently to
show that

$\displaystyle\frac{200\sigma^{2}(1+\varepsilon)(1+\sqrt{\varepsilon})^{2}}{36(C_{1,T-1,\gamma})^{2}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,T})}{\gamma}\bigg{)}\geq\frac{8\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,T})}{\gamma}\bigg{)}.$

Moreover, since $\Delta_{1}=\min\limits_{i\in[L]}\Delta_{i}$, it is sufficient
to show

$\displaystyle\frac{25}{36(C_{1,T-1,\gamma})^{2}}\geq\frac{1}{\Delta_{1}^{2}}~{}\Leftrightarrow~{}C_{1,T-1,\gamma}\leq\frac{5\Delta_{1}}{6}.$

(ii) In order to show (D.1) holds for all $i\in[L]$, it is sufficient to show
that

$\displaystyle C_{1,T-1,\gamma}\leq\frac{5\Delta_{1}}{6}.$

With $a_{1}=2$, this is implied by

$\displaystyle
N_{1,T-1}\geq\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{72a_{1}\beta\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{i}^{2}\gamma}\bigg{)}~{}\bigg{)}$
$\displaystyle~{}\Leftrightarrow~{}N_{1,T}\geq\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{72a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{i}^{2}\gamma}+\beta\bigg{)}~{}\bigg{)}+1.$

We obtain the inequality in the above display by applying Lemma D.3.
Meanwhile, (D.2) and $t=\sum_{i=1}^{L}N_{i,t}$ implies that

$\displaystyle N_{1,T}=T-\sum_{i\neq 1}N_{i,T}\geq T-(L-1)-\sum_{i\neq
1}\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{72a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{i}^{2}\gamma}+\beta\bigg{)}~{}\bigg{)}.$

Altogether, we complete the proof with

$\displaystyle\sum_{i=1}^{L}\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{72a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{i}^{2}\gamma}+\beta\bigg{)}~{}\bigg{)}\leq
T-L+1.$ (D.4)

Step 5: Conclusion. Since

$\displaystyle\frac{72\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{a_{1}}{\gamma}\log\bigg{(}\frac{72a_{1}\sigma^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)^{2}}{\Delta_{i}^{2}\gamma}+\beta\bigg{)}~{}\bigg{)}$
$\displaystyle\leq\frac{72\sigma^{2}(1+\varepsilon)^{3}}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{2a_{1}}{\gamma^{2}}\log\bigg{(}\frac{6\sqrt{2a_{1}}\cdot\sigma(1+\varepsilon)^{2}}{\Delta_{i}}+\beta\bigg{)}~{}\bigg{)},$

To show (D.4), it is sufficient to have

$\displaystyle\sum_{i=1}^{L}\frac{72\sigma^{2}(1+\varepsilon)^{3}}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{2a_{1}}{\gamma^{2}}\log\bigg{(}\frac{6\sqrt{2a_{1}}\cdot\sigma(1+\varepsilon)^{2}}{\Delta_{i}}+\beta\bigg{)}~{}\bigg{)}\leq
T-L+1$ $\displaystyle\Leftrightarrow~{}$
$\displaystyle\sum_{i=1}^{L}\frac{72\sigma^{2}(1+\varepsilon)^{3}}{\Delta_{i}^{2}}\cdot\log\bigg{(}\frac{2a_{1}}{\gamma^{2}}\bigg{)}\leq
T-L+1-\sum_{i=1}^{L}\frac{72\sigma^{2}(1+\varepsilon)^{3}}{\Delta_{i}^{2}}\cdot\log\bigg{(}\log\bigg{(}\frac{6\sqrt{2a_{1}}\cdot\sigma(1+\varepsilon)^{2}}{\Delta_{i}}+\beta\bigg{)}~{}\bigg{)}$
$\displaystyle\Leftrightarrow~{}$
$\displaystyle\gamma\geq\sqrt{2a_{1}}\cdot\exp\Bigg{(}-\frac{T-L+1-\sum_{i=1}^{L}72\sigma^{2}\Delta_{i}^{-2}\cdot(1+\varepsilon)^{3}\log\big{(}\log\big{(}\frac{6\sqrt{2a_{1}}\cdot\sigma(1+\varepsilon)^{2}}{\Delta_{i}}+\beta\big{)}~{}\big{)}}{\sum_{i=1}^{L}{144\sigma^{2}(1+\varepsilon)^{3}}{\Delta_{i}^{-2}}}\Bigg{)}.$

Recall the definition of $H_{2}$ in (2.1):

$\displaystyle H_{2}=\sum_{i\neq 1}\frac{1}{\Delta_{1,i}^{2}}.$

Furthermore, it suffices to have

$\displaystyle\gamma$
$\displaystyle\geq\sqrt{2a_{1}}\cdot\exp\Bigg{(}-\frac{T-L}{144\sigma^{2}(1+\varepsilon)^{3}(H_{2}+1/\Delta_{1,2}^{2})}+\frac{1}{2}\log\bigg{(}\log\bigg{(}\frac{6\sqrt{2a_{1}}\cdot\sigma(1+\varepsilon)^{2}}{\Delta_{1,2}}+\beta\bigg{)}~{}\bigg{)}~{}\Bigg{)}$
$\displaystyle=\sqrt{2.8\cdot\log\bigg{(}\frac{6\sqrt{2.8}\cdot\sigma(1+\varepsilon)^{2}}{\Delta_{1,2}}+\beta\bigg{)}}\exp\bigg{(}-\frac{T-L}{144\sigma^{2}(1+\varepsilon)^{3}(H_{2}+1/\Delta_{1,2}^{2})}\bigg{)}:=\gamma_{1}(\Delta_{1,2},H_{2}).$

Note that $\Delta=\Delta_{1,2}$. When $\gamma=\gamma_{1}(\Delta,H_{2})$,

$\displaystyle e_{T}$
$\displaystyle\leq\frac{2L(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma_{1}(\Delta,H_{2})}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}$
$\displaystyle=\frac{2L(2+\varepsilon)}{\varepsilon[\log(1+\varepsilon)]^{1+\varepsilon}}\cdot\bigg{[}2.8\log\bigg{(}\frac{6\sqrt{2.8}\cdot\sigma(1+\varepsilon)^{2}}{\Delta}+\beta\bigg{)}\bigg{]}^{(1+\varepsilon)/2}\cdot\exp\bigg{(}-\frac{T-L}{144\sigma^{2}(1+\varepsilon)^{2}(H_{2}+1/\Delta^{2})}\bigg{)}.$

∎

###  D.3 Proof of Lemma D.2

See D.2

###### Proof.

Let

$\displaystyle\mathcal{E}_{i,\gamma}:=\\{\forall t\geq
L,|\hat{g}_{i,t}-w_{i}|\leq C_{i,t,\gamma}\\}.$

Then

$\displaystyle\Pr(\mathcal{E}_{i,\gamma})$ $\displaystyle=\Pr\bigg{(}\forall
t\geq L,\big{|}\hat{g}_{i,t}-w_{i}\big{|}\leq
5\sigma(1+\sqrt{\varepsilon})\sqrt{\frac{2(1+\varepsilon)}{N_{i,t}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t-1})}{\gamma}\bigg{)}}~{}\bigg{)}$
$\displaystyle=\Pr\bigg{(}\forall N_{i,t}\geq 1,$ $\displaystyle\hskip
40.00006pt\bigg{|}\bigg{(}\frac{1}{N_{i,t}}\sum_{u=1}^{t}g_{i,u}\cdot\mathsf{1}\\{i_{u}=i\\}\bigg{)}-w_{i}\bigg{|}\leq
5\sigma(1+\sqrt{\varepsilon})\sqrt{\frac{2(1+\varepsilon)}{N_{i,t}}\cdot\log\bigg{(}\frac{\log(\beta+(1+\varepsilon)N_{i,t})}{\gamma}\bigg{)}}~{}\bigg{)}$

When $\varepsilon\in(0,1)$ and $\gamma\in(0,\log(\beta+1+\varepsilon)/e)$,
Theorem C.1 indicates that

$\Pr(\mathcal{E}_{i,\gamma})\geq
1-\frac{2(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

Furthermore,

$\displaystyle\Pr\bigg{(}\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}\bigg{)}=1-\Pr\Bigg{(}~{}\overline{\bigcap_{i=1}^{L}\mathcal{E}_{i,\gamma}}~{}\Bigg{)}=1-\Pr\bigg{(}\bigcup_{i=1}^{L}\overline{\mathcal{E}_{i,\gamma}}\bigg{)}$
$\displaystyle\quad\geq
1-\sum_{i=1}^{L}\Pr\big{(}~{}\overline{\mathcal{E}_{i,\gamma}}~{}\big{)}\geq
1-\frac{2L(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

∎

###  D.4 Proof of Lemma D.3

See D.3

###### Proof.

Let

$\displaystyle
f(\tau)=c\log\bigg{(}\frac{\log(a\tau+b)}{\rho}\bigg{)},\quad\tau_{a_{1},a_{2}}=c\log\bigg{(}\frac{a_{1}}{\rho}\log\bigg{(}\frac{a_{2}c}{\rho}+b\bigg{)}\bigg{)}.$

Then

$\displaystyle\tau_{a_{1},a_{2}}\geq
f(\tau_{a_{1},a_{2}})~{}\Leftrightarrow~{}$ $\displaystyle
c\log\bigg{(}\frac{a_{1}}{\rho}\log\bigg{(}\frac{a_{2}c}{\rho}+b\bigg{)}\bigg{)}\geq
c\log\bigg{(}\frac{1}{\rho}\log\bigg{[}ac\log\bigg{(}\frac{a_{1}}{\rho}\log\bigg{(}\frac{a_{2}c}{\rho}\bigg{)}\bigg{)}+b\bigg{]}\bigg{)}$
$\displaystyle\Leftrightarrow~{}$ $\displaystyle
a_{1}\log\bigg{(}\frac{a_{2}c}{\rho}+b\bigg{)}\geq\log\bigg{[}ac\log\bigg{(}\frac{a_{1}}{\rho}\log\bigg{(}\frac{a_{2}c}{\rho}\bigg{)}\bigg{)}+b\bigg{]}.$

Let $a_{1}\geq 1.4$, then $x^{a_{1}}\geq x\log x$ for all $x\geq 1$. To obtain
$\tau_{a_{1},a_{2}}\geq f(\tau_{a_{1},a_{2}})$, it suffices to have

$\displaystyle\bigg{(}\frac{a_{2}c}{\rho}+b\bigg{)}\cdot\log\bigg{(}\frac{a_{2}c}{\rho}+b\bigg{)}\geq
ac\log\bigg{(}\frac{a_{1}}{\rho}\log\bigg{(}\frac{a_{2}c}{\rho}\bigg{)}\bigg{)}+b,$

which is implied by

$\displaystyle\frac{a_{2}c}{\rho}+b\geq e~{}\text{ and
}~{}\frac{a_{2}c}{\rho}\cdot\log\bigg{(}\frac{a_{2}c}{\rho}+b\bigg{)}\geq\frac{aca_{1}}{\rho}\log\bigg{(}\frac{a_{2}c}{\rho}\bigg{)}.$

Conditioned on $a_{2}c/\rho+b\geq e$, the last inequality holds when
$a_{2}\geq a\cdot a_{1}$. Since $\tau-f(\tau)$ is monotonically increasing in
$\tau$, and $\tau_{a_{1},a\cdot a_{1}}\geq f(\tau_{a_{1},a\cdot a_{1}})$,
i.e., $\tau_{a_{1},a\cdot a_{1}}-f(\tau_{a_{1},a\cdot a_{1}})\geq 0$, we have

$\displaystyle\tau\geq\tau_{1.4,1.4a}~{}\Rightarrow~{}\tau-f(\tau)\geq 0.$

In other words, when $1.4ac/\rho+b\geq e$,

$\displaystyle\tau\leq
f(\tau)~{}\Rightarrow~{}\tau\leq\tau_{1.4,2.8}=c\log\bigg{(}\frac{1.4}{\rho}\log\bigg{(}\frac{1.4ac}{\rho}\bigg{)}\bigg{)}.$

∎

##  Appendix E Analysis of the Pareto frontier of RM and BAI in stochastic
bandits

###  E.1 Proof of Theorem 5.1

See 5.1

###### Proof.

Step 1: Construct instances. To begin with, we fix $d_{\ell}\in(0,1/4]$ for
all $2\leq\ell\leq L$. We let $\mathrm{Bern}(a)$ denote the Bernoulli
distribution with parameter $a$. We define the following distributions:

$\displaystyle\nu_{1}:=\mathrm{Bern}(1/2),\quad\nu_{\ell}:=\mathrm{Bern}(1/2-d_{\ell})\quad\forall
1<\ell\leq L;$
$\displaystyle\nu_{1}^{\prime}:=\mathrm{Bern}(1/2),\quad\nu_{\ell}^{\prime}:=\mathrm{Bern}(1/2+d_{\ell})\quad\forall
1<\ell\leq L.$

We construct $L$ instances such that under instance $\ell$ ($1\leq\ell\leq
L$), the stochastic reward of item $i$ is drawn from distribution

$\nu_{i}^{\ell}:=b\cdot(\nu_{i}\mathsf{1}\\{i\neq\ell\\}+\nu_{i}^{\prime}\mathsf{1}\\{i=\ell\\}),$

where $b>0$. Under instance $\ell$ ($1\leq\ell\leq L$), we see item $\ell$ is
optimal, and we define several other notations as follows:

  * (i)

We let $g_{i,t}^{\ell}$ be the random reward of item $i$ at time step $t$.
Then $g_{i,t}^{\ell}\in\\{0,b\\}$.

  * (ii)

We let
$\Delta_{i,j}^{\ell}:=\mathbb{E}[\sum_{t=1}^{T}g_{i,t}^{\ell}-g_{k,t}^{\ell}]/T$
denote the gap between item $i$ and $j$. Then

$\displaystyle\Delta_{1,j}^{1}=b\cdot d_{j}\ \quad\forall 2\leq j\leq
L,\quad\Delta_{\ell,1}^{\ell}=b\cdot d_{\ell},\ \Delta_{\ell,j}^{\ell}=b\cdot
d_{\ell}+b\cdot d_{j}\quad\forall 2\leq j,\ell\leq L,j\neq\ell.$

  * (iii)

We denote the difficulty of the instance with

$\displaystyle H_{2}(\ell):=\sum_{j\neq\ell}(\Delta_{\ell,j}^{\ell})^{-2}.$

Then $H_{2}(1)=\max\limits_{1\leq\ell\leq
L}H_{2}(\ell)\leq(L-1)b^{-2}\cdot\max\limits_{2\leq\ell\leq L}d_{\ell}^{-2}$.

  * (iv)

We let $i_{t}^{\ell}$ be the pulled item at time step $t$, and
$O_{\ell}^{t}=\\{i_{u}^{\ell},g_{i_{u}^{\ell},u}\\}^{t}_{u=1}$ be the sequence
of pulled items and observed rewards up to and including time step $t$.

  * (v)

We let $\mathbb{P}_{\ell}^{t}$ be the measure on $O_{\ell}^{t}$, and let
$P_{\ell,i}$ be the measure on the rewards of item $i$.

For simplicity, we abbreviate $\mathbb{P}_{\ell}^{T}$, $O_{\ell}^{T}$ as
$\mathbb{P}_{\ell}$, $O_{\ell}$ respectively. Moreover, we let $N_{i,t}$
denote the number of pulls of item $i$ up to and including time step $t$.

Step 2: Change of measure. First of all, we apply Lemmas C.6 and C.7 to obtain
that for all $1\leq\ell\leq L$,

$\displaystyle\Pr_{O_{1}}(i_{\mathrm{out}}\neq
1)+\Pr_{O_{\ell}}(i_{\mathrm{out}}=1)\geq\frac{1}{2}\exp(-\mathrm{KL}(\mathbb{P}_{1}\parallel\mathbb{P}_{\ell}))=\frac{1}{2}\exp(-\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}]\cdot\mathrm{KL}(P_{1,\ell}\parallel
P_{\ell,\ell})).$

Suppose the pseudo-regret is upper bounded by $\overline{\mathrm{Reg}}$, we
have

$\displaystyle\overline{\mathrm{Reg}}$
$\displaystyle\geq\mathbb{E}_{\mathbb{P}_{1}}\Bigg{[}\sum_{t=1}^{T}\mathsf{1}\\{i_{t}^{1}\neq
1\\}\cdot(g_{1,t}^{1}-g_{i_{t},t}^{1})\Bigg{]}=\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}\neq
1\\}\cdot(g_{1,t}^{1}-g_{i_{t},t}^{1})]$
$\displaystyle=\sum_{\ell=2}^{L}\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}=\ell\\}\cdot(g_{1,t}^{1}-g_{i_{t},t}^{1})]=\sum_{\ell=2}^{L}\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}_{1}^{t}}[(g_{1,t}^{1}-g_{i_{t},t}^{1})|i_{t}^{1}=\ell]\cdot\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}=\ell\\}]$
$\displaystyle=\sum_{\ell=2}^{L}\sum_{t=1}^{T}\Delta_{1,\ell}^{1}\cdot\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}=\ell\\}]=\sum_{\ell=2}^{L}b\cdot
d_{\ell}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}].$

Since $H_{2}(\ell)=\sum_{j\neq\ell}(\Delta_{\ell,j}^{\ell})^{-2}$, we have

$\displaystyle\frac{\overline{\mathrm{Reg}}}{H_{2}(1)}=\frac{\sum_{\ell=2}^{L}b\cdot
d_{\ell}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}]}{\sum_{\ell=2}^{L}(\Delta_{1,j}^{1})^{-2}}=\frac{\sum_{\ell=2}^{L}b\cdot
d_{\ell}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}]}{b^{-3}\cdot\sum_{\ell=2}^{L}d_{j}^{-2}}.$

Thus, by the pigeonhole principle, there exists $2\leq\ell_{1}\leq L$ such
that

$\displaystyle
b^{3}d_{\ell_{1}}^{3}\mathbb{E}_{\mathbb{P}_{1}}\cdot[N_{\ell_{1},T}]=\frac{b\cdot
d_{\ell_{1}}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell_{1},T}]}{b^{-2}\cdot
d_{\ell_{1}}^{-2}}\leq\frac{\overline{\mathrm{Reg}}}{H_{2}(1)}~{}\Leftrightarrow~{}\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell_{1},T}]\leq\frac{\overline{\mathrm{Reg}}}{b^{3}d_{\ell_{1}}^{3}H_{2}(1)}.$

Since $d_{\ell}\in(0,1/4]$ for all $2\leq\ell\leq L$, we apply Theorem C.8 to
obtain

$\displaystyle\Pr_{O_{1}}(i_{\mathrm{out}}\neq
1)+\Pr_{O_{\ell_{1}}}(i_{\mathrm{out}}=1)\geq\frac{1}{2}\exp(-\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell_{1},T}]\cdot\mathrm{KL}(P_{1,\ell_{1}}\parallel
P_{\ell_{1},\ell_{1}}))\geq\frac{1}{2}\exp\bigg{(}-\frac{\overline{\mathrm{Reg}}}{b^{3}d_{\ell_{1}}^{3}H_{2}(1)}\cdot\frac{(2d_{\ell_{1}})^{2}}{1/4}\bigg{)}.$

Since
$\Pr_{O_{\ell_{j}}}(i_{\mathrm{out}}\neq\ell_{1})\geq\Pr_{O_{\ell_{1}}}(i_{\mathrm{out}}=1)$,
we have

$\displaystyle\max_{1\leq\ell\leq
L}\Pr_{O_{\ell}}(i_{\mathrm{out}}\neq\ell)\geq\frac{1}{4}\exp\bigg{(}-\frac{8\overline{\mathrm{Reg}}}{H_{2}(1)b^{3}\cdot\min\limits_{2\leq\ell\leq
L}d_{\ell}}~{}\bigg{)}.$

Step 3: Conclusion. We define

$\ell_{2}:=\operatorname*{arg\,max}_{1\leq\ell\leq
L}\Pr_{O_{\ell}}(i_{\mathrm{out}}\neq\ell).$

Suppose algorithm $\pi$ satisfies that

$\displaystyle\Pr_{O_{\ell_{2}}}(i_{\mathrm{out}}\neq\ell_{2})\leq\frac{1}{4}\exp(-\phi_{T}),$

then we have

$\displaystyle\overline{\mathrm{Reg}}\geq\phi_{T}\cdot\frac{H_{2}(1)b^{3}\cdot\min\limits_{2\leq\ell\leq
L}d_{\ell}}{8}.$

When $d=d_{\ell}>0$ for all $2\leq\ell\leq L$, we have
$H_{2}(1)=(L-1)/(b^{2}d^{2})$.

Step 4: Classification of instances. Suppose algorithm $\pi$ satisfies that
$e_{T}(\pi)\leq\exp(-\phi_{T})/4$. Let
$\mathcal{B}_{1}(\underline{\Delta},\overline{R})$ denote the set of
stochastic instances where (i) the minimal optimality gap
$\Delta\geq\underline{\Delta}$; and (ii) there exists $R_{0}\in\mathbb{R}$
such the rewards are bounded in $[R_{0},R_{0}+\overline{R}]$. Then

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{1}(\underline{\Delta},\overline{R})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{(L-1)\overline{R}}{8\underline{\Delta}}\quad\forall\underline{\Delta},\overline{R}>0.$

Let $\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})$ denote
the set of stochastic instances that (i) belong to
$\mathcal{B}_{1}(\underline{\Delta},\overline{R})$, and (ii) are with hardness
parameter $H_{2}\leq\overline{H}_{2}$. Then, we have

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{2}(\underline{\Delta},\overline{R},\overline{H}_{2})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{\underline{\Delta}\overline{H}_{2}\overline{R}^{3}}{8}\quad\forall\underline{\Delta},\overline{R},\overline{H}_{2}>0.$

∎

###  E.2 Proof of Theorem 5.3

See 5.3

###### Proof.

Step 1: Construct instances. To begin with, we fix any $\sigma>0$,
$d_{\ell}>0$ for all $2\leq\ell\leq L$. We define the following distributions:

$\displaystyle\nu_{1}:=\mathcal{N}(1/2,\sigma^{2}),\quad\nu_{\ell}:=\mathcal{N}(1/2-d_{\ell},\sigma^{2})\quad\forall
1<\ell\leq L;$
$\displaystyle\nu_{1}^{\prime}:=\mathcal{N}(1/2,\sigma^{2}),\quad\nu_{\ell}^{\prime}:=\mathcal{N}(1/2+d_{\ell},\sigma^{2})\quad\forall
1<\ell\leq L.$

We construct $L$ instances such that under instance $\ell$ ($1\leq\ell\leq
L$), the stochastic reward of item $i$ is drawn from distribution

$\nu_{i}^{\ell}:=\nu_{i}\mathsf{1}\\{i\neq\ell\\}+\nu_{i}^{\prime}\mathsf{1}\\{i=\ell\\}.$

Under instance $\ell$ ($1\leq\ell\leq L$), we see item $\ell$ is optimal, and
we define several other notations as follows:

  * (i)

We let $g_{i,t}^{\ell}$ be the random reward of item $i$ at time step $t$.

  * (ii)

We let
$\Delta_{i,j}^{\ell}:=\mathbb{E}[\sum_{t=1}^{T}g_{i,t}^{\ell}-g_{k,t}^{\ell}]/T$
denote the gap between item $i$ and $j$. Then

$\displaystyle\Delta_{1,j}^{1}=d_{j}\ \quad\forall 2\leq j\leq
L,\quad\Delta_{\ell,1}^{\ell}=d_{\ell},\
\Delta_{\ell,j}^{\ell}=d_{\ell}+d_{j}\quad\forall 2\leq j,\ell\leq
L,j\neq\ell.$

  * (iii)

We denote the difficulty of the instance with

$\displaystyle H_{2}(\ell):=\sum_{j\neq\ell}(\Delta_{\ell,j}^{\ell})^{-2}.$

Then $H_{2}(1)=\max\limits_{1\leq\ell\leq
L}H_{2}(\ell)\leq(L-1)\cdot\max\limits_{2\leq\ell\leq L}d_{\ell}^{-2}$.

  * (iv)

We let $i_{t}^{\ell}$ be the pulled item at time step $t$, and
$O_{\ell}^{t}=\\{i_{u}^{\ell},g_{i_{u}^{\ell},u}\\}^{t}_{u=1}$ be the sequence
of pulled items and observed rewards up to and including time step $t$.

  * (v)

We let $\mathbb{P}_{\ell}^{t}$ be the measure on $O_{\ell}^{t}$, and let
$P_{\ell,i}$ be the measure on the rewards of item $i$.

For simplicity, we abbreviate $\mathbb{P}_{\ell}^{T}$, $O_{\ell}^{T}$ as
$\mathbb{P}_{\ell}$, $O_{\ell}$ respectively. Moreover, we let $N_{i,t}$
denote the number of pulls of item $i$ up to and including time step $t$.

Step 2: Change of measure. First of all, we apply Lemmas C.6 and C.7 to obtain
that for all $1\leq\ell\leq L$,

$\displaystyle\Pr_{O_{1}}(i_{\mathrm{out}}\neq
1)+\Pr_{O_{\ell}}(i_{\mathrm{out}}=1)\geq\frac{1}{2}\exp(-\mathrm{KL}(\mathbb{P}_{1}\parallel\mathbb{P}_{\ell}))=\frac{1}{2}\exp(-\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}]\cdot\mathrm{KL}(P_{1,\ell}\parallel
P_{\ell,\ell})).$

Suppose the pseudo-regret is upper bounded by $\overline{\mathrm{Reg}}$, we
have

$\displaystyle\overline{\mathrm{Reg}}$
$\displaystyle\geq\mathbb{E}_{\mathbb{P}_{1}}\Bigg{[}\sum_{t=1}^{T}\mathsf{1}\\{i_{t}^{1}\neq
1\\}\cdot(g_{1,t}^{1}-g_{i_{t},t}^{1})\Bigg{]}=\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}\neq
1\\}\cdot(g_{1,t}^{1}-g_{i_{t},t}^{1})]$
$\displaystyle=\sum_{\ell=2}^{L}\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}=\ell\\}\cdot(g_{1,t}^{1}-g_{i_{t},t}^{1})]=\sum_{\ell=2}^{L}\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}_{1}^{t}}[(g_{1,t}^{1}-g_{i_{t},t}^{1})|i_{t}^{1}=\ell]\cdot\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}=\ell\\}]$
$\displaystyle=\sum_{\ell=2}^{L}\sum_{t=1}^{T}d_{\ell}\cdot\mathbb{E}_{\mathbb{P}_{1}^{t}}[\mathsf{1}\\{i_{t}^{1}=\ell\\}]=\sum_{\ell=2}^{L}d_{\ell}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}].$

Since $H_{2}(\ell)=\sum_{j\neq\ell}(\Delta_{\ell,j}^{\ell})^{-2}$, we have

$\displaystyle\frac{\overline{\mathrm{Reg}}}{H_{2}(1)}=\frac{\sum_{\ell=2}^{L}d_{\ell}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}]}{\sum_{\ell=2}^{L}(\Delta_{1,j}^{1})^{-2}}=\frac{\sum_{\ell=2}^{L}d_{\ell}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell,T}]}{\sum_{\ell=2}^{L}d_{j}^{-2}}.$

Thus, by the pigeonhole principle, there exists $2\leq\ell_{1}\leq L$ such
that

$\displaystyle
d_{\ell_{1}}^{3}\mathbb{E}_{\mathbb{P}_{1}}\cdot[N_{\ell_{1},T}]=\frac{d_{\ell_{1}}\cdot\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell_{1},T}]}{d_{\ell_{1}}^{-2}}\leq\frac{\overline{\mathrm{Reg}}}{H_{2}(1)}~{}\Leftrightarrow~{}\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell_{1},T}]\leq\frac{\overline{\mathrm{Reg}}}{d_{\ell_{1}}^{3}H_{2}(1)}.$

Further, we apply Lemma C.9 to obtain

$\displaystyle\Pr_{O_{1}}(i_{\mathrm{out}}\neq
1)+\Pr_{O_{\ell_{1}}}(i_{\mathrm{out}}=1)\geq\frac{1}{2}\exp(-\mathbb{E}_{\mathbb{P}_{1}}[N_{\ell_{1},T}]\cdot\mathrm{KL}(P_{1,\ell_{1}}\parallel
P_{\ell_{1},\ell_{1}}))\geq\frac{1}{2}\exp\bigg{(}-\frac{\overline{\mathrm{Reg}}}{d_{\ell_{1}}^{3}H_{2}(1)}\cdot\frac{(2d_{\ell_{1}})^{2}}{2\sigma^{2}}\bigg{)}.$

Since
$\Pr_{O_{\ell_{j}}}(i_{\mathrm{out}}\neq\ell_{1})\geq\Pr_{O_{\ell_{1}}}(i_{\mathrm{out}}=1)$,
we have

$\displaystyle\max_{1\leq\ell\leq
L}\Pr_{O_{\ell}}(i_{\mathrm{out}}\neq\ell)\geq\frac{1}{4}\exp\bigg{(}-\frac{2\overline{\mathrm{Reg}}}{H_{2}(1)\sigma^{2}\cdot\min\limits_{2\leq\ell\leq
L}d_{\ell}}~{}\bigg{)}.$

Step 3: Conclusion. We define

$\ell_{2}:=\operatorname*{arg\,max}_{1\leq\ell\leq
L}\Pr_{O_{\ell}}(i_{\mathrm{out}}\neq\ell).$

Suppose algorithm $\pi$ satisfies that

$\displaystyle\Pr_{O_{\ell_{2}}}(i_{\mathrm{out}}\neq\ell_{2})\leq\frac{1}{4}\exp(-\phi_{T}),$

then we have

$\displaystyle\overline{\mathrm{Reg}}\geq\phi_{T}\cdot\frac{H_{2}(1)\sigma^{2}\cdot\min\limits_{2\leq\ell\leq
L}d_{\ell}}{2}.$

When $d=d_{\ell}>0$ for all $2\leq\ell\leq L$, we have $H_{2}(1)=(L-1)/d^{2}$.

Step 4: Classification of instances. Suppose algorithm $\pi$ satisfies that
$e_{T}(\pi)\leq\exp(-\phi_{T})/4$. Let
$\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{V})$ denote the set of
stochastic instances where (i) the minimal optimality gap
$\Delta\geq\underline{\Delta}$; (ii) for each item $i$, the variance
$\sigma_{i}^{2}\leq\overline{V}$. Then

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{V})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{(L-1)\overline{V}}{2\underline{\Delta}}\quad\forall\underline{\Delta},\overline{V}>0.$

Let
$\mathcal{B}_{2}^{\prime}(\underline{\Delta},\overline{V},\overline{H}_{2})$
denote the set of stochastic instances (i) that belong to
$\mathcal{B}_{1}^{\prime}(\underline{\Delta},\overline{V})$, and (ii) are with
the hardness $H_{2}\leq\overline{H}_{2}$. We have

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{2}^{\prime}(\underline{\Delta},\overline{V},\overline{H}_{2})}R_{T}(\pi,\mathcal{I})\geq\phi_{T}\cdot\frac{\underline{\Delta}\overline{H}_{2}\overline{V}}{2}\quad\forall\underline{\Delta},\overline{V},\overline{H}_{2}>0.$

∎

###  E.3 Proof of Corollary 5.4

See 5.4

###### Proof.

We consider the stochastic instances in
$\mathcal{B}_{2}(\underline{\Delta},1,\overline{H}_{2})$. By the
classification of instances in Theorem 5.1, these instances satisfy the
conditions

$\displaystyle g_{i,t}\in[0,1]\quad\forall i,t,\quad\text{ and }\quad
H_{2}\leq\overline{H}_{2}.$

Therefore, the distribution $\nu_{i}$ is sub-Gaussian with scale $\sigma=1/2$
for all $i\in[L]$. We assume $T$ is sufficiently large such that

$\displaystyle\frac{\log T}{T}$
$\displaystyle\geq\gamma_{1}=\sqrt{2.8\log\bigg{(}\frac{6\sqrt{2.8}\sigma(1+\varepsilon)^{2}}{\underline{\Delta}}+\beta\bigg{)}}\cdot\exp\Bigg{(}-\frac{T-L}{144\sigma^{2}(1+\varepsilon)^{3}(\overline{H}_{2}+1/\underline{\Delta}^{2})}\Bigg{)}$
$\displaystyle=\sqrt{2.8\log\bigg{(}\frac{3\sqrt{2.8}(1+\varepsilon)^{2}}{\underline{\Delta}}+\beta\bigg{)}}\cdot\exp\Bigg{(}-\frac{T-L}{36(1+\varepsilon)^{3}(\overline{H}_{2}+\underline{\Delta}^{-2})}\Bigg{)}.$

As a result, for all instance in
$\mathcal{B}_{2}(\underline{\Delta},1,\overline{H}_{2})$, since
$\Delta\geq\underline{\Delta}$ and $H_{2}\leq\overline{H}_{2}$, we have

$\displaystyle\frac{\log T}{T}$
$\displaystyle\geq\sqrt{2.8\log\bigg{(}\frac{3\sqrt{2.8}(1+\varepsilon)^{2}}{\Delta}+\beta\bigg{)}}\cdot\exp\Bigg{(}-\frac{T-L}{36(1+\varepsilon)^{3}(H_{2}+\Delta^{-2})}\Bigg{)}.$

Fix any $\gamma\in[\gamma_{1},(\log T)/L]$. On one hand, for any instance in
$\mathcal{B}_{2}(\underline{\Delta},1,\overline{H}_{2})$, Theorem 4.1 implies
that BoBW-lil’UCB$(\gamma)$ satisfies that

$\displaystyle R_{T}\leq O\bigg{(}\log\bigg{(}\frac{1}{\gamma}\bigg{)}\cdot
H_{1}\bigg{)}.$

On the other hand, Theorem 4.2 implies that

$\displaystyle e_{T}$
$\displaystyle\leq\frac{2L(2+\varepsilon)}{\varepsilon}\bigg{(}\frac{\gamma}{\log(1+\varepsilon)}\bigg{)}^{1+\varepsilon}.$

Moreover, we can apply Theorem 5.1 to obtain that

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{2}(\underline{\Delta},1,\overline{H}_{2})}R_{T}(\textsc{BoBW-
lil'UCB$(\gamma)$},\mathcal{I})$
$\displaystyle\in\Omega\bigg{(}\underline{\Delta}\overline{H}_{2}\log\bigg{(}\frac{1}{\gamma
L}\bigg{)}\bigg{)}.$

Altogether, we have

$\displaystyle\sup_{\mathcal{I}\in\mathcal{B}_{2}(\underline{\Delta},1,\overline{H}_{2})}R_{T}(\textsc{BoBW-
lil'UCB$(\gamma)$},\mathcal{I})$
$\displaystyle\in\Omega\bigg{(}\underline{\Delta}\overline{H}_{2}\log\bigg{(}\frac{1}{\gamma
L}\bigg{)}\bigg{)}\bigcap
O\bigg{(}\frac{(L-1)}{\underline{\Delta}}\log\bigg{(}\frac{1}{\gamma}\bigg{)}\bigg{)}.$

∎

##  Appendix F Analysis of Exp3.P in adversarial bandits

###  F.1 Proof of Theorem B.1

See B.1

###### Proof.

The analysis is similar to that of Theorem 3.2 in Bubeck et al., (2012) with
$\beta=0$, while the following lemma signifies the key difference.

######  Lemma F.1 (Implied by Bubeck et al., (2012), Lemma 3.1).

For any item $i$, with probability at least $1-\delta$,

$\displaystyle\sum_{t=1}^{T}g_{i,t}\leq\sum_{t=1}^{T}\tilde{g}_{i,t}+\ln\bigg{(}\frac{LT}{\eta\delta}\bigg{)}.$

Replacing Lemma 3.1 in Bubeck et al., (2012) by Lemma F.1, we can adopt the
analysis of Theorem 3.2 in Bubeck et al., (2012) and show that with
probability $1-\delta$,

$\displaystyle\bar{R}_{T}\leq\gamma T+\eta
LT+\ln\bigg{(}\frac{L^{2}T}{\eta\delta}\bigg{)}+\frac{\ln L}{\eta}.$

Moreover, we derive that

$\displaystyle W^{\prime}=\bar{R}_{T}-\bigg{[}\gamma T+\eta
LT+\ln\bigg{(}\frac{L^{2}T}{\eta}\bigg{)}+\frac{\ln L}{\eta}\bigg{]},$
$\displaystyle\mathbb{P}(W^{\prime}>\ln\frac{1}{\delta})=\Pr\bigg{(}\bar{R}_{T}-\bigg{[}\gamma
T+\eta LT+\ln\bigg{(}\frac{L^{2}T}{\eta\delta}\bigg{)}+\frac{\ln
L}{\eta}\bigg{]}>0\bigg{)}\leq\delta,$
$\displaystyle\mathbb{E}\bar{R}_{T}-\bigg{[}\gamma T+\eta
LT+\ln\bigg{(}\frac{L^{2}T}{\eta}\bigg{)}+\frac{\ln L}{\eta}\bigg{]}\leq 1,$
$\displaystyle\mathbb{E}\bar{R}_{T}\leq\gamma T+\eta
LT+\ln\bigg{(}\frac{L^{2}T}{\eta}\bigg{)}+\frac{\ln L}{\eta}+1.$

∎

###  F.2 Proof of Theorem B.2

See B.2

###### Proof.

For brevity, we assume $G_{1,T}\geq G_{2,T}\geq\ldots\geq G_{L,T}$ and
abbreviate $\bar{\Delta}_{i,j,T}$ as $\Delta_{i,j}$ for any $i,j\in[L]$.
Consequently, the optimal item $\bar{i}^{*}=1$.

Step 1: Construction of martingale. Let

$\displaystyle y_{i,t}=\tilde{g}_{i,t}-g_{i,t},\quad
X_{i,t}=\tilde{G}_{i,t}-G_{i,t}=\sum_{u=1}^{t}(\tilde{g}_{i,u}-g_{i,u})=\sum_{u=1}^{t}y_{i,u}.$

Now we fix arbitrary $i\in[L]$ and abbreviate $y_{i,t}$ as $y_{t}$, $X_{i,t}$
as $X_{t}$ for brevity when there is no ambiguity. Then we have

$\displaystyle
X_{t}-X_{t-1}=y_{t}=\tilde{g}_{i,t}-g_{i,t}=g_{i,t}\cdot\bigg{(}\frac{\mathbb{I}\\{i_{t}=i\\}}{p_{i,t}}-1\bigg{)}=g_{i,t}\cdot\bigg{(}\frac{\mathbb{I}\\{i_{t}=i\\}}{p_{i,t}}-1\bigg{)},$
$\displaystyle-1\leq y_{t}\leq\frac{1}{p_{i,t}}-1\quad\text{ since
}g_{i,t}\leq 1,$
$\displaystyle\mathbb{E}[y_{t}|\mathcal{F}_{t-1}]=\mathbb{E}\bigg{[}g_{i,t}\cdot\bigg{(}\frac{\mathbb{E}[\mathbb{I}\\{i_{t}=i\\}|\mathcal{F}_{t-1}]}{p_{i,t}}-1\bigg{)}\bigg{|}\mathcal{F}_{t-1}\bigg{]}=0,\quad\mathbb{E}y_{t}=\mathbb{E}[\mathbb{E}[y_{t}|\mathcal{F}_{t-1}]]=0.$

Since $y_{t}$ is a martingale, we can apply Theorem C.2 and C.3 for the
analysis.

Meanwhile, note that $g_{i,t},p_{i,t}\in\mathcal{F}_{t-1}$ and again
$g_{i,t}\leq 1$. Since $\mathbb{P}(i_{t}=i|\mathcal{F}_{t-1})=p_{i,t}$, the
variance conditioned on $\mathcal{F}_{t-1}$ is the variance of the Bernoulli
random variable with parameter $p_{i,t}$, scaled to the range
$[0,g_{i,t}/p_{i,t}]$. Hence, we have

$\displaystyle\operatorname{\mathrm{Var}}(X_{t}|\mathcal{F}_{t-1})$
$\displaystyle=\operatorname{\mathrm{Var}}(y_{t}|\mathcal{F}_{t-1})=\operatorname{\mathrm{Var}}\bigg{(}\frac{g_{i,t}\cdot(\mathbb{I}\\{i_{t}=i\\}-1)}{p_{i,t}}~{}\bigg{|}~{}\mathcal{F}_{t-1}\bigg{)}=\operatorname{\mathrm{Var}}\bigg{(}\frac{g_{i,t}\cdot\mathbb{I}\\{i_{t}=i\\}}{p_{i,t}}~{}\bigg{|}~{}\mathcal{F}_{t-1}\bigg{)}$
$\displaystyle=\operatorname{\mathrm{Var}}\bigg{(}\frac{g_{i,t}\cdot\mathbb{I}\\{i_{t}=i\\}}{p_{i,t}}~{}\bigg{|}~{}\mathcal{F}_{t-1}\bigg{)}=\frac{g^{2}_{i,t}}{p^{2}_{i,t}}\cdot\operatorname{\mathrm{Var}}(\mathbb{I}\\{i_{t}=i\\}|\mathcal{F}_{t-1})=\frac{p_{i,t}(1-p_{i,t})g^{2}_{i,t}}{p^{2}_{i,t}}=\frac{(1-p_{i,t})g^{2}_{i,t}}{p_{i,t}}$
$\displaystyle=g_{i,t}^{2}\cdot\bigg{(}\frac{1}{p_{i,t}}-1\bigg{)}\leq\frac{1}{p_{i,t}}-1:=\sigma_{t}^{2}\qquad\text{
since }g_{i,t}\leq 1.$

On one hand, in order to apply Theorem C.2 to upper bound
$\tilde{G}_{i,T}-G_{i,T}$, we need to upper bound
$\operatorname{\mathrm{Var}}(X_{t}|\mathcal{F}_{t-1})$, $y_{t}$, and lower
bound $p_{i,t}$. These bounds will depend on the lower bound on $p_{i,t}$. On
the other hand, to lower bound $\tilde{G}_{i,T}-G_{i,T}$ with Theorem C.3, we
need to upper bound $\operatorname{\mathrm{Var}}(X_{t}|\mathcal{F}_{t-1})$,
$p_{i,t}$, and lower bound $y_{t}$. This motivates to derive bounds on
$p_{i,t}$. Since
$1-\gamma+\frac{\gamma}{L}-\frac{1}{L}=(1-\frac{1}{L})(1-\gamma)>0$, there are
global bounds on $\\{p_{i,t}\\}_{i,t}$:

$\displaystyle\frac{\gamma}{L}\leq p_{i,t}\leq 1-\gamma+\frac{\gamma}{L}.$

Step 2: Bound $\tilde{G}_{i,T}-G_{i,T}$ with high probability.

Upper bound on $\tilde{G}_{i,T}-G_{i,T}$. We first derive upper bounds on
$\sum_{t=1}^{T}\sigma^{2}$, $y_{t}$ with lower bounds on $p_{i,t}$:

(i)
$\displaystyle\sum_{t=1}^{T}\sigma_{t}^{2}=\sum_{t=1}^{T}\bigg{(}\frac{1}{p_{i,t}}-1\bigg{)}\leq
T\cdot\bigg{(}\frac{L}{\gamma}-1\bigg{)}$ (ii) $\displaystyle
y_{t}\leq\frac{1-\beta}{p_{i,t}}-1\leq\frac{L}{\gamma}-1:=M.$

Let $a_{t}=0$. We apply Theorem C.2. For all $\lambda\in(0,1)$,

$\displaystyle\Pr(X_{T}-\mathbb{E}X_{T}\geq\lambda)\leq\exp\Bigg{(}-\frac{\lambda^{2}}{\sum_{t=1}^{T}\sigma_{t}^{2}+{M\lambda}/{3}}\Bigg{)},\qquad\mathbb{E}X_{T}=\sum_{t=1}^{T}\mathbb{E}y_{t}=0.$

Therefore, for all $i\in[L]$, $\lambda_{i}\in(0,1)$,

$\displaystyle\mathbb{P}(\tilde{G}_{i,T}-G_{i,T}\geq\lambda_{i})\leq\exp\Bigg{(}-\frac{\lambda_{i}^{2}}{\sum_{t=1}^{T}\sigma_{t}^{2}+{M\lambda_{i}}/{3}}\Bigg{)}.$
(F.1)

Lower bound on $\tilde{G}_{i,T}-G_{i,T}$. Similarly, we have
$X_{t-1}-X_{t}=-y_{t}\leq 1:=M^{\prime}$. We apply Theorem C.3. Therefore, for
all $i\in[L]$, $\lambda_{i}\in(0,1)$, we have

$\displaystyle\Pr(\tilde{G}_{i,T}-G_{i,T}\leq-\lambda_{i})\leq\exp\Bigg{(}-\frac{\lambda_{i}^{2}}{\sum_{t=1}^{T}\sigma_{t}^{2}+M^{\prime}\lambda_{i}/3}\Bigg{)}.$
(F.2)

Step 3: Last step. We decompose the failure probability as follows:

######  Lemma F.2.

For any fixed time budget $T$, we have

$\displaystyle\Pr(i_{\mathrm{out}}\neq
1)\leq\Pr\bigg{(}\tilde{G}_{1,T}-G_{1,T}\leq-\frac{T\Delta_{1,2}}{2}\bigg{)}+\sum_{i=2}^{L}\Pr\bigg{(}\tilde{G}_{i,T}-G_{i,T}\geq\frac{T\Delta_{1,2}}{2}+T\cdot\Delta_{2,i}\bigg{)}.$

Combining (F.1), (F.2) and Lemma F.2 , we see that

$\displaystyle\lambda_{1}\leq\frac{T\Delta_{1,2}}{2},\quad\lambda_{i}\leq\frac{T\Delta_{1,2}}{2}+T\cdot\Delta_{2,i}\quad\forall
i\neq 1,$ $\displaystyle\Rightarrow~{}$ $\displaystyle\Pr(i_{\mathrm{out}}\neq
1)\leq\exp\Bigg{(}-\frac{\lambda_{1}^{2}}{\sum_{t=1}^{T}\sigma_{t}^{2}+{M^{\prime}\lambda_{1}}/{3}}\Bigg{)}+\sum_{i=2}^{L}\exp\Bigg{(}-\frac{\lambda_{i}^{2}}{\sum_{t=1}^{T}\sigma_{t}^{2}+{M\lambda_{i}}/{3}}\Bigg{)}.$

Let

$\displaystyle\lambda_{1}:=\frac{T\Delta_{1,2}}{2}\qquad\lambda_{i}:=\frac{T\Delta_{1,2}}{2}+T\cdot\Delta_{2,i}\quad\forall
i\neq 1.$

We now complete the proof:

$\displaystyle\Pr(i_{\mathrm{out}}\neq 1)$
$\displaystyle\leq\exp\Bigg{(}-\frac{T\Delta_{1,2}^{2}/4}{L/\gamma}\Bigg{)}+\sum_{i=2}^{L}\exp\Bigg{(}-\frac{T(\Delta_{1,2}/2+\Delta_{2,i})^{2}}{{L(3+\Delta_{1,2}/2+\Delta_{2,i})}/{(3\gamma)}}\Bigg{)}$
$\displaystyle=\exp\Bigg{(}-\frac{\gamma
T\Delta_{1,2}^{2}}{4L}\Bigg{)}+\sum_{i=2}^{L}\exp\Bigg{(}-\frac{3\gamma
T(\Delta_{1,2}/2+\Delta_{2,i})^{2}}{L(3+\Delta_{1,2}/2+\Delta_{2,i})}\Bigg{)}.$

∎

###  F.3 Proof of Lemma F.2

See F.2

###### Proof.

We observe that

$\displaystyle\Pr(i_{\mathrm{out}}\neq 1)=\Pr(\exists i\neq
1:\tilde{G}_{i,T}\geq\tilde{G}_{1,T})$ $\displaystyle\leq\Pr\bigg{(}\exists
i\neq
1:\tilde{G}_{i,T}-G_{i,T}\geq\frac{T\Delta_{1,2}}{2}+T\cdot\Delta_{2,i},\text{
or }\tilde{G}_{1,T}-G_{1,T}\leq-\frac{T\Delta_{1,2}}{2}\bigg{)}$ (F.3)
$\displaystyle\leq\Pr\bigg{(}\tilde{G}_{1,T}-G_{1,T}\leq-\frac{T\Delta_{1,2}}{2}\bigg{)}+\sum_{i=2}^{L}\Pr\bigg{(}\tilde{G}_{i,T}-G_{i,T}\geq\frac{T\Delta_{1,2}}{2}+T\cdot\Delta_{2,i}\bigg{)}.$
(F.4)

It is trivial to obtain (F.4) with (F.3). Now we complete the proof with the
derivation of (F.3). We denote

$\displaystyle\mathcal{E}_{1,T}:=\bigg{\\{}\tilde{G}_{1,T}-G_{1,T}\leq-\frac{T\Delta_{1,2}}{2}\bigg{\\}},\qquad\mathcal{E}_{i,T}:=\bigg{\\{}\tilde{G}_{i,T}-G_{i,T}\geq\frac{T\Delta_{1,2}}{2}+T\cdot\Delta_{2,i}\bigg{\\}}\quad\forall
i\neq 1.$

We can rewrite (F.3) as $\mathbb{P}(\exists i\neq
1:\tilde{G}_{i,T}\geq\tilde{G}_{1,T})\leq\mathbb{P}(\bigcup_{i=1}^{L}\mathcal{E}_{i,T})$.
Hence, it is sufficient to show