# An $\varepsilon$-Best-Arm Identification Algorithm
for Fixed-Confidence and Beyond

Marc Jourdan
<EMAIL_ADDRESS>
&Rémy Degenne
<EMAIL_ADDRESS>
&Emilie Kaufmann
<EMAIL_ADDRESS>

Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille,
France

###### Abstract

We propose EB-TCε, a novel sampling rule for $\varepsilon$-best arm
identification in stochastic bandits. It is the first instance of Top Two
algorithm analyzed for approximate best arm identification. EB-TCε is an
_anytime_ sampling rule that can therefore be employed without modification
for fixed confidence or fixed budget identification (without prior knowledge
of the budget). We provide three types of theoretical guarantees for EB-TCε.
First, we prove bounds on its expected sample complexity in the fixed
confidence setting, notably showing its asymptotic optimality in combination
with an adaptive tuning of its exploration parameter. We complement these
findings with upper bounds on its probability of error at any time and for any
error parameter, which further yield upper bounds on its simple regret at any
time. Finally, we show through numerical simulations that EB-TCε performs
favorably compared to existing algorithms, in different settings.

##  1 Introduction

In pure exploration problems, the goal is to answer a question about a set of
unknown distributions (modelling for example the efficacy of a treatment) from
which we can collect samples (measure its effect), and to provide guarantees
on the candidate answer. Practitioners might have different pre-defined
constraints, e.g. the maximal budget might be fixed in advance or the error
made should be smaller than a fixed admissible error. However, in many cases,
fixing such constraints in advance can be challenging since a “good” choice
typically depends on unknown quantities. Moreover, while the budget is limited
in clinical trials, it is often not fixed beforehand. The physicians can
decide to stop earlier or might obtain additional fundings for their
experiments. In light of those real-world constraints, regardless of its
primal objective any strategy for choosing the next treatment should ideally
come with guarantees on its current candidate answer that hold at any time.

We formalize our investigations in the well-studied stochastic bandit model
[4, 29], in which a learner interacts sequentially with an environment
composed of $K\in\mathbb{N}$ arms, which are unknown distributions
$(\nu_{i})_{i\in[K]}$ with finite means $(\mu_{i})_{i\in[K]}$. At each stage
$n\in\mathbb{N}$, the learner chooses an arm $I_{n}\in[K]$ based on the
samples previously observed and receives a sample $X_{n,I_{n}}$, random
variable with conditional distribution $\nu_{I_{n}}$ given $I_{n}$. It then
proceeds to the next stage. An algorithm for the learner in this interaction
is specified by a _sampling rule_ , a procedure that determines $I_{n}$ based
on previously observed samples. Formally, the sampling rule defines for all
$n\in\mathbb{N}$ a function from $([K]\times\mathbb{R})^{n-1}$ to the
probability distribution on $[K]$, which is measurable with respect to the
$\sigma$-algebra
$\mathcal{F}_{n}:=\sigma(\\{I_{t},X_{t,I_{t}}\\}_{t\in[n-1]})$. We call that
$\sigma$-algebra _history_ before $n$.

##### Identification tasks

We focus on best arm identification (BAI). In that task, the goal of the
algorithm is to find which of the arms has the largest mean, and to do so with
a small probability of error, as quickly as possible. If several arms have
means very close to the maximum, finding the one with the highest mean might
be difficult. However in practice we are often satisfied by any good enough
arm, in the sense that its mean is greater than $\mu_{\star}-\varepsilon$,
where $\mu_{\star}=\max_{i\in[K]}\mu_{i}$. This is the $\varepsilon$-BAI task.
Our results can also be adapted to the multiplicative $\varepsilon$-BAI task,
in which all means are non-negative and we want to find an arm with mean
$\mu_{i}\geq(1-\varepsilon)\mu_{\star}$ [19] (see Appendix I for details).

Now that we have a (for now informal) goal, we need to complement the sampling
rule with a recommendation rule that specifies which arm is the candidate
returned by the algorithm for the best arm. We follow [5] and define that rule
for all stages: for all $n\in\mathbb{N}$, we denote by $\hat{\imath}_{n}$ this
$\mathcal{F}_{n}$-measurable function from $([K]\times\mathbb{R})^{n-1}$ to
$[K]$. We call _algorithm_ the combination of a sampling and a recommendation
rule.

##### Performance criteria

There are several ways to evaluate the performance of an algorithm for
$\varepsilon$-BAI. Let
$\mathcal{I}_{\varepsilon}(\mu)=\\{i\in[K]\mid\mu_{i}\geq\mu_{\star}-\varepsilon\\}$
be the set of $\varepsilon$-good arms. The _probability of
$\varepsilon$-error_ or the recommendation at $n$ is defined as
$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu))$.
Introduced in [1], the expected _simple regret_ is defined as
$\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]$, and is independent of
any parameter $\varepsilon$. Based on those notions, several setting are
studied in the bandit identification literature.

  * •

Fixed confidence: we augment the algorithm with a _stopping rule_ , a stopping
time $\tau_{\varepsilon,\delta}$ with respect to the history of samples and we
impose that the algorithm should be $(\varepsilon,\delta)$-PAC. That is, its
probability of $\varepsilon$-error at $\tau_{\varepsilon,\delta}$ must satisfy
$\mathbb{P}_{\nu}(\tau_{\varepsilon,\delta}<+\infty,\hat{\imath}_{\tau_{\varepsilon,\delta}}\notin\mathcal{I}_{\varepsilon}(\mu))\leq\delta$.
The parameter $\delta$ is known to the algorithm. An algorithm is judged based
on its expected sample complexity $\mathbb{E}[\tau_{\varepsilon,\delta}]$, the
expected number of samples it needs to collect before it can stop and return a
good arm with the required confidence.

  * •

Fixed budget: we run the algorithm until a predefined time $T$ and we evaluate
it based on the probability of error at $T$. This setting has been mostly
studied for $\varepsilon=0$ [1, 25], but [41] present the first bounds for
$\varepsilon>0$ for an algorithm that is actually agnostic to this value.

  * •

Simple regret minimization: we evaluate the expected simple regret at $T$ [5,
41].

Simple regret is typically studied in an anytime setting: [5] contains upper
bounds on the simple regret at time $n$ for any $n\in\mathbb{N}^{*}$.
Similarly, [23] propose the _anytime exploration_ setting, in which they
control the error probability $\mathbb{P}\left(\hat{\imath}_{n}\neq
i_{\star}\right)$ for exact best arm identification. Interestingly, the
authors build on an algorithm for the fixed-confidence setting, LUCB [24],
whose sampling rule depends on the risk parameter $\delta$, which they replace
by a sequence $\delta_{n}$. The algorithm that we study in this paper,
motivated by the fixed-confidence $\varepsilon$-BAI problem, will already be
_anytime_ , which means that it does not depend on a given final time $T$ or a
confidence level $\delta$. We shall analyze its sample complexity in the fixed
confidence setting but thanks to the anytime property we will also be able to
prove guarantees on its probability of $\varepsilon$-error for every
$\varepsilon\geq 0$ and its simple regret at any time.

##### Additional notation and assumption

We denote by $\mathcal{D}$ a set to which the distributions of the arms are
known to belong. We suppose that all distributions in $\mathcal{D}$ are 1-sub-
Gaussian. A distribution $\nu_{0}$ is 1-sub-Gaussian if it satisfies
$\mathbb{E}_{X\sim\nu_{0}}[e^{\lambda(X-\mathbb{E}_{X\sim\nu_{0}}[X])}]\leq
e^{\lambda^{2}/2}$ for all $\lambda\in\mathbb{R}$. For example, all
distributions bounded in $[-1,1]$ are 1-sub-Gaussian. Let us denote by
$i^{\star}(\mu):=\operatorname*{arg\,max}_{i\in[K]}\mu_{i}$ the set of arms
with largest mean (i.e. $i^{\star}(\mu)=\mathcal{I}_{0}(\mu)$). Let
$\Delta_{i}:=\mu_{\star}-\mu_{i}$ denote the sub-optimality gap of arm $i$. We
denote by $\triangle_{K}\subset\mathbb{R}^{K}$ the simplex of dimension $K-1$.

##### Fixed-confidence $\varepsilon$-best-arm identification

Let $\varepsilon\geq 0$ and $\delta\in(0,1)$ be fixed error and confidence
parameters. In the _fixed-confidence_ $\varepsilon$-BAI setting [31, 13, 35,
16], the probability of error of an algorithm is required to be less than
$\delta$ for all instances $\nu\in\mathcal{D}^{K}$. That requirement leads to
an asymptotic lower bound on the expected sample complexity on any instance.

######  Lemma 1 ([10]).

For all $(\varepsilon,\delta)$-PAC algorithms and all instances
$\nu_{i}=\mathcal{N}(\mu_{i},1)$ with $\mu\in\mathbb{R}^{K}$,
$\liminf_{\delta\to
0}\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon,\delta}]}{\log(1/\delta)}\geq
T_{\varepsilon}(\mu)$ where
$T_{\varepsilon}(\mu)=\min_{i\in\mathcal{I}_{\varepsilon}(\mu)}\min_{\beta\in(0,1)}T_{\varepsilon,\beta}(\mu,i)$
with

$T_{\varepsilon,\beta}(\mu,i)^{-1}=\max_{w\in\triangle_{K},w_{i}=\beta}\min_{j\neq
i}\frac{1}{2}\frac{(\mu_{i}-\mu_{j}+\varepsilon)^{2}}{1/\beta+1/w_{j}}\>.$ (1)

We say that an algorithm is asymptotically (resp. $\beta$-)optimal if its
sample complexity matches that lower bound, that is if $\limsup_{\delta\to
0}\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon,\delta}]}{\log(1/\delta)}\leq
T_{\varepsilon}(\mu)$ (resp.
$T_{\varepsilon,\beta}(\mu)=\min_{i\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon,\beta}(\mu,i)$).
Note that the expected sample complexity of an asymptotically $1/2$-optimal
algorithm is at worst twice higher than that of any asymptotically optimal
algorithm since $T_{\varepsilon,1/2}(\mu)\leq 2T_{\varepsilon}(\mu)$ [34].

The asymptotic characteristic time $T_{\varepsilon}(\mu)$ is of order
$\sum_{i=1}^{K}\min\\{\varepsilon^{-2},\Delta_{i}^{-2}\\}$. It is computed as
a minimum over all $\varepsilon$-good arms
$i\in\mathcal{I}_{\varepsilon}(\mu)$ of an arm-specific characteristic time,
which can be interpreted as the time required to verify that $i$ is
$\varepsilon$-good. Each of the times
$\min_{\beta\in(0,1)}T_{\varepsilon,\beta}(\mu,i)$ correspond to the
complexity of a BAI instance (i.e. $\varepsilon$-BAI with $\varepsilon=0$) in
which the mean of arm $i$ is increased by $\varepsilon$ (Lemma 9). Let
$w_{\varepsilon,\beta}(\mu,i)$ be the maximizer of (1). In [16], they show
that
$T_{\varepsilon}(\mu)=T_{\varepsilon,\beta^{\star}(i^{\star})}(\mu,i^{\star})$
and $T_{\varepsilon,\beta}(\mu)=T_{\varepsilon,\beta}(\mu,i^{\star})$, where
$i^{\star}\in i^{\star}(\mu)$ and
$\beta^{\star}(i^{\star})=\operatorname*{arg\,min}_{\beta\in(0,1)}T_{\varepsilon,\beta}(\mu,i^{\star})$.
For $\varepsilon=0$, a similar lower bound to Lemma 1 holds for all $\delta$
[15]. Lower bounds of order
$\sum_{i=1}^{K}\Delta_{i}^{-2}\log\log\Delta_{i}^{-2}$ (independent of
$\delta$, but with a stronger dependence in the gaps) were also shown [17, 6,
38, 7]. Note that the characteristic time for $\sigma$-sub-Gaussian
distributions (which does not have a form as “explicit” as (1)) is always
smaller than the ones for Gaussian having the same means and variance
$\sigma^{2}$.

A good algorithm should have an expected sample complexity as close as
possible to these lower bounds. Several algorithms for ($\varepsilon$-)BAI are
based on modifications of the UCB algorithm [24, 17, 14]. Others compute
approximate solutions to the lower bound maximization problem and sample arms
in order to approach the solution [15, 11, 39]. Our method belongs to the
family of Top Two algorithms [34, 36, 21], which select at each time two arms
called leader and challenger, and sample among them. It is the first Top Two
algorithm for the $\varepsilon$-BAI problem (for $\varepsilon>0$).

##### Any time and uniform $\varepsilon$-error bound

In addition to the fixed-confidence guarantees, we will prove a bound on the
probability of error for any time $n$ and any error $\varepsilon$, similarly
to the results of [41]. That is, we bound
$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu))$ for
all $n$ and all $\varepsilon$. This gives a bound on the probability of error
in $\varepsilon$-BAI, and a bound on the simple regret of the sampling rule by
integrating:
$\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]=\int\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu))\mathrm{d}\,\varepsilon$.

The literature mostly focuses on the fixed budget setting, where the time $T$
at which we evaluate the error probability is known and can be used as a
parameter of the algorithm. Notable algorithms are successive rejects (SR,
[1]) and sequential halving (SH, [25]). These algorithms can be extended to
not depend on $T$ by using a doubling trick [23, 41]. That trick considers a
sequence of algorithms that are run with budgets $(T_{k})_{k}$, with
$T_{k+1}=2T_{k}$ and $T_{1}=2K\lceil\log_{2}K\rceil$. Past observations are
dropped when reaching $T_{k}$, and the obtained recommendation is used until
the budget $T_{k+1}$ is reached.

###  1.1 Contributions

We propose the EB-TC${}_{\varepsilon_{0}}$ algorithm for identification in
bandits, with a slack parameter $\varepsilon_{0}>0$, originally motivated by
$\varepsilon_{0}$-BAI. We study its combination with a stopping rule for fixed
confidence $\varepsilon$-BAI (possibly with $\varepsilon_{0}\neq\varepsilon$)
and also its probability of error and simple regret at any time.

  * •

EB-TC${}_{\varepsilon_{0}}$ performs well empirically compared to existing
methods, both for the expected sample complexity criterion in fixed confidence
$\varepsilon$-BAI and for the anytime simple regret criterion. It is in
addition easy to implement and computationally inexpensive in our regime.

  * •

We prove upper bounds on the sample complexity of EB-TC${}_{\varepsilon_{0}}$
in fixed confidence $\varepsilon$-BAI with sub-Gaussian distributions, both
asymptotically (Theorem 1) as $\delta\to 0$ and for any $\delta$ (Theorem 2).
In particular, EB-TCε with $\varepsilon>0$ is asymptotically optimal for
$\varepsilon$-BAI with Gaussian distributions.

  * •

We prove a uniform $\varepsilon$-error bound valid for any time for EB-
TC${}_{\varepsilon_{0}}$. This gives in particular a fixed budget error bound
and a control of the expected simple regret of the algorithm (Theorem 3 and
Corollary 1).

##  2 Anytime Top Two sampling rule

We propose an anytime Top Two algorithm, named EB-TC${}_{\varepsilon_{0}}$ and
summarized in Figure 1.

##### Recommendation rule

Let $N_{n,i}:=\sum_{t\in[n-1]}\mathds{1}\left(I_{t}=i\right)$ be the number of
pulls of arm $i$ before time $n$, and
$\mu_{n,i}:=\frac{1}{N_{n,i}}\sum_{t\in[n-1]}X_{t,I_{t}}\mathds{1}\left(I_{t}=i\right)$
be its empirical mean. At time $n>K$, we recommend the Empirical Best (EB) arm
$\hat{\imath}_{n}\in\operatorname*{arg\,max}_{i\in[K]}\mu_{n,i}$ (where ties
are broken arbitrarily).

###  2.1 Anytime Top Two sampling rule

We start by sampling each arm once. At time $n>K$, a Top Two sampling rule
defines a leader $B_{n}\in[K]$ and a challenger $C_{n}\neq B_{n}$. It then
chooses the arm to pull among them. For the leader/challenger pair, we
consider the Empirical Best (EB) leader $B^{\text{EB}}_{n}=\hat{\imath}_{n}$
and, given a slack $\varepsilon_{0}>0$, the Transportation Cost
(TC${}_{\varepsilon_{0}}$) challenger

$C^{\text{TC}\varepsilon_{0}}_{n}\in\operatorname*{arg\,min}_{i\neq
B^{\text{EB}}_{n}}\frac{\mu_{n,B^{\text{EB}}_{n}}-\mu_{n,i}+\varepsilon_{0}}{\sqrt{1/N_{n,B^{\text{EB}}_{n}}+1/N_{n,i}}}\>.$
(2)

The algorithm then needs to choose between $B_{n}$ and $C_{n}$. In order to do
so, we use a so-called _tracking_ procedure [15]. We define one tracking
procedure per pair of leader/challenger $(i,j)\in[K]^{2}$ such that $i\neq j$,
hence we have $K(K-1)$ independent tracking procedures. For each pair $(i,j)$
of leader and challenger, the associated tracking procedure will ensure that
the proportion of times the algorithm pulled the leader $i$ remains close to a
target average proportion $\bar{\beta}_{n}(i,j)\in(0,1)$. At each round $n$,
only one tracking rule is considered, i.e. the one of the pair
$(i,j)=(B_{n},C_{n})$.

We define two variants of the algorithm that differ in the way they set the
proportions $\bar{\beta}_{n}(i,j)$. Fixed proportions set
$\bar{\beta}_{n}(i,j)=\beta$ for all $(n,i,j)\in\mathbb{N}\times[K]^{2}$,
where $\beta\in(0,1)$ is fixed beforehand. Information-Directed Selection
(IDS) [40] defines $\beta_{n}(i,j)=N_{n,j}/(N_{n,i}+N_{n,j})$ and sets
$\bar{\beta}_{n}(i,j):=T_{n}(i,j)^{-1}\sum_{t\in[n-1]}\mathds{1}\left((B_{t},C_{t})=(i,j)\right)\beta_{t}(i,j)$
where $T_{n}(i,j):=\sum_{t\in[n-1]}\mathds{1}\left((B_{t},C_{t})=(i,j)\right)$
is the selection count of arms $(i,j)$ as leader/challenger.

1:Input: slack $\varepsilon_{0}>0$, proportion $\beta\in(0,1)$ (only for fixed
proportions).

2:Set $\hat{\imath}_{n}\in\operatorname*{arg\,max}_{i\in[K]}\mu_{n,i}$,
$B_{n}=\hat{\imath}_{n}$ and $C_{n}\in\operatorname*{arg\,min}_{i\neq
B_{n}}\frac{\mu_{n,B_{n}}-\mu_{n,i}+\varepsilon_{0}}{\sqrt{1/N_{n,B_{n}}+1/N_{n,i}}}$.

3:Set
$\bar{\beta}_{n+1}(B_{n},C_{n})=(T_{n}(B_{n},C_{n})\bar{\beta}_{n}(B_{n},C_{n})+\beta_{n}(B_{n},C_{n}))/T_{n+1}(B_{n},C_{n})$
with [fixed] $\beta_{n}(i,j)=\beta$ or [IDS]
$\beta_{n}(i,j)=N_{n,j}/(N_{n,i}+N_{n,j})$ and
$T_{n+1}(B_{n},C_{n})=T_{n}(B_{n},C_{n})+1$.

4:Set $I_{n}=C_{n}$ if
$N_{n,C_{n}}^{B_{n}}\leq(1-\bar{\beta}_{n+1}(B_{n},C_{n}))T_{n+1}(B_{n},C_{n})$,
otherwise set $I_{n}=B_{n}$.

5:Output: next arm to sample $I_{n}$ and next recommendation
$\hat{\imath}_{n}$.

Figure 1: EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed or IDS proportions.

Let
$N^{i}_{n,j}:=\sum_{t\in[n-1]}\mathds{1}\left((B_{t},C_{t})=(i,j),\>I_{t}=j\right)$
be the number of pulls of arm $j$ at rounds in which $i$ was the leader. We
set $I_{n}=C_{n}$ if
$N_{n,C_{n}}^{B_{n}}\leq(1-\bar{\beta}_{n+1}(B_{n},C_{n}))T_{n+1}(B_{n},C_{n})$
and $I_{n}=B_{n}$ otherwise. Using Theorem 6 in [12] for each tracking
procedure (i.e. each pair $(i,j)$) yields Lemma 2 (proved in Appendix H).

######  Lemma 2.

For all $n>K$, $i\in[K]$, $j\neq i$, we have $-1/2\leq
N_{n,j}^{i}-(1-\bar{\beta}_{n}(i,j))T_{n}(i,j)\leq 1$.

The TC${}_{\varepsilon_{0}}$ challenger seeks to minimize an empirical version
of a quantity that appears in the lower bound for $\varepsilon_{0}$-BAI (Lemma
1). As such, it is a natural extension of the TC challenger used in the T3C
algorithm [36] for $\varepsilon_{0}=0$. In earlier works on Top Two methods
[34, 32, 36], the choice between leader and challenger is randomized: given a
fixed proportion $\beta\in(0,1)$, set $I_{n}=B_{n}$ with probability $\beta$,
otherwise $I_{n}=C_{n}$. [20] replaced randomization by tracking, and [40]
proposed IDS to define adaptive proportions $\beta_{n}(B_{n},C_{n})\in(0,1)$.
In this work we study both fixed proportions with $\beta=1/2$ and adaptive
proportions with IDS. Empirically, we observe slightly better performances
when using IDS (e.g. Figure 7 in Appendix J.2.1). While [20] tracked the
leader with $K$ procedures, we consider $K(K-1)$ independent tracking
procedures depending on the current leader/challenger pair.

##### Choosing $\bm{\varepsilon_{0}}$

[21] shows that EB-TC (i.e. EB-TC${}_{\varepsilon_{0}}$ with slack
$\varepsilon_{0}=0$) suffers from poor empirical performance for moderate
$\delta$ in BAI (see Appendix D.3 in [21] for a detailed discussion).
Therefore, the choice of the slack $\varepsilon_{0}>0$ is critical since it
acts as a regularizer which naturally induces sufficient exploration. By
setting $\varepsilon_{0}$ too small, the EB-TC${}_{\varepsilon_{0}}$ algorithm
will become as greedy as EB-TC and perform poorly. Having $\varepsilon_{0}$
too large will flatten differences between sub-optimal arms, hence it will
behave more uniformly. We observe from the theoretical guarantees and from our
experiments that it is best to take $\varepsilon_{0}=\varepsilon$ for
$\varepsilon$-BAI, but the empirical performance is only degrading slowly for
$\varepsilon_{0}>\varepsilon$. Taking $\varepsilon_{0}<\varepsilon$ leads to
very poor performance. We discuss this trade-off in more details in our
experiments (e.g. Figures 5, 6 and 7 in Appendix J.2.1). When tackling BAI,
the limitation of EB-TC can be solved by adding an implicit exploration
mechanism in the choice of the leader/challenger pair. For the choice of
leader, we can use randomization (TS leader [34, 32, 36]) or optimism (UCB
leader [20]). For the choice of the challenger, we can use randomization (RS
challenger [34]) or penalization (TCI challenger [21], KKT challenger [40] or
EI challenger [32]).

##### Anytime sampling rule

EB-TC${}_{\varepsilon_{0}}$ is independent of a budget of samples $T$ or a
confidence parameter $\delta$. This anytime sampling rule can be regarded as a
stream of empirical means/counts $(\mu_{n},N_{n})_{n>K}$ (which could trigger
stopping) and a stream of recommendations
$\hat{\imath}_{n}=i^{\star}(\mu_{n})$. These streams can be used by agents
with different kinds of objectives. The fixed-confidence setting couples it
with a stopping rule to be $(\varepsilon,\delta)$-PAC. It can also be used to
get an $\varepsilon$-good recommendation with large probability at any given
time $n$.

###  2.2 Stopping rule for fixed-confidence $\varepsilon$-best-arm
identification

In addition to the sampling and recommendation rules, the fixed-confidence
setting requires a stopping rule. Given an error/confidence pair, the GLRε
stopping rule [15] prescribes to stop at the time

$\tau_{\varepsilon,\delta}=\inf\left\\{n>K\mid\>\min_{i\neq\hat{\imath}_{n}}\frac{\mu_{n,\hat{\imath}_{n}}-\mu_{n,i}+\varepsilon}{\sqrt{1/N_{n,\hat{\imath}_{n}}+1/N_{n,i}}}\geq\sqrt{2c(n-1,\delta)}\right\\}\quad\text{with}\quad\hat{\imath}_{n}=i^{\star}(\mu_{n})\>,$
(3)

where $c:\mathbb{N}\times(0,1)\to\mathbb{R}_{+}$ is a threshold function.
Lemma 3 gives a threshold ensuring that the GLRε stopping rule is
$(\varepsilon,\delta)$-PAC for all $\varepsilon\geq 0$ and $\delta\in(0,1)$,
independently of the sampling rule.

######  Lemma 3 ([27]).

Let $\varepsilon\geq 0$ and $\delta\in(0,1)$. Given any sampling rule, using
the threshold

$c(n,\delta)=2\mathcal{C}_{G}(\log((K-1)/\delta)/2)+4\log(4+\log(n/2))$ (4)

with the stopping rule (3) with error/confidence pair $(\varepsilon,\delta)$
yields a $(\varepsilon,\delta)$-PAC algorithm for sub-Gaussian distributions.
The function $\mathcal{C}_{G}$ is defined in (23). It satisfies
$\mathcal{C}_{G}(x)\approx x+\log(x)$.

##  3 Fixed-confidence theoretical guarantees

To study $\varepsilon$-BAI in the fixed-confidence setting, we couple EB-
TC${}_{\varepsilon_{0}}$ with the GLRε stopping rule (3) using error
$\varepsilon\geq 0$, confidence $\delta\in(0,1)$ and threshold (4). The
resulting algorithm is $(\varepsilon,\delta)$-PAC by Lemma 3. We derive upper
bounds on the expected sample complexity
$\mathbb{E}_{\nu}[\tau_{\varepsilon,\delta}]$ both in the asymptotic regime of
$\delta\to 0$ (Theorem 1) and for finite confidence when
$\varepsilon=\varepsilon_{0}$ (Theorem 2).

######  Theorem 1.

Let $\varepsilon\geq 0$, $\varepsilon_{0}>0$ and $(\beta,\delta)\in(0,1)^{2}$.
Combined with GLRε stopping (3), the EB-TC${}_{\varepsilon_{0}}$ algorithm is
$(\varepsilon,\delta)$-PAC and it satisfies that, for all
$\nu\in\mathcal{D}^{K}$ with mean $\mu$ such that $|i^{\star}(\mu)|=1$,

$\text{{\bf[IDS]}}\>\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon,\delta}]}{\log(1/\delta)}\leq
T_{\varepsilon_{0}}(\mu)D_{\varepsilon,\varepsilon_{0}}(\mu)\quad\text{and}\quad\text{{\bf[fixed
$\beta$]}}\>\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon,\delta}]}{\log(1/\delta)}\leq
T_{\varepsilon_{0},\beta}(\mu)D_{\varepsilon,\varepsilon_{0}}(\mu)\>,$

where $D_{\varepsilon,\varepsilon_{0}}(\mu)=(1+\max_{i\neq
i^{\star}}(\varepsilon_{0}-\varepsilon)/(\mu_{\star}-\mu_{i}+\varepsilon))^{2}$.

While Theorem 1 holds for all sub-Gaussian distributions, it is particularly
interesting for Gaussian ones, in light of Lemma 1. When choosing
$\varepsilon=\varepsilon_{0}$ (i.e.
$D_{\varepsilon_{0},\varepsilon_{0}}(\mu)=1$), Theorem 1 shows that EB-
TC${}_{\varepsilon_{0}}$ is asymptotically optimal for Gaussian bandits when
using IDS proportions and asymptotically $\beta$-optimal when using fixed
proportions $\beta$. We also note that Theorem 1 is not conflicting with the
lower bound of Lemma 1, as shown in Lemma 11 in Appendix C. Empirically we
observe that the empirical stopping time can be drastically worse when taking
$\varepsilon_{0}<\varepsilon$, and close to the optimal one when
$\varepsilon_{0}>\varepsilon$ (Figures 5, 6 and 7 in Appendix J.2.1).

Until recently [40], proving asymptotic optimality of Top Two algorithms with
adaptive choice $\beta$ was an open problem in BAI. In this work, we prove
that their choice of IDS proportions also yield asymptotically optimal
algorithms for $\varepsilon$-BAI. While the proof of Theorem 1 assumes the
existence of a unique best arm, it holds for instances having sub-optimal arms
with the same mean. This is an improvement compared to existing asymptotic
guarantees on Top Two algorithms which rely on the assumption that the means
of all arms are different [32, 36, 21]. The improvement is possible thanks to
the regularization induced by the slack $\varepsilon_{0}>0$.

While asymptotic optimality in the $\varepsilon$-BAI setting was already
achieved for various algorithms (e.g. $\varepsilon$-Track-and-Stop (TaS) [16],
Sticky TaS [10] or L$\varepsilon$BAI [19]), none of them obtained non-
asymptotic guarantees. Despite their theoretical interest, asymptotic results
provide no guarantee on the performance for moderate $\delta$. Furthermore,
asymptotic results on Top Two algorithms require a unique best arm regardless
of the considered error $\varepsilon$: reaching asymptotic
($\beta$-)optimality implicitly means that the algorithm eventually allocates
samples in an optimal way that depends on the identity of the unique best arm,
and that requires the unique best arm to be identified. As our focus is
$\varepsilon$-BAI, our guarantees should only require that one of the
$\varepsilon$-good arms is identified and should hold for instances having
multiple best arms. The upper bound should scale with $\varepsilon_{0}^{-2}$
instead of $\Delta_{\min}^{-2}$ when $\Delta_{\min}$ is small. Theorem 2
satisfies these requirements.

######  Theorem 2.

Let $\delta\in(0,1)$ and $\varepsilon_{0}>0$. Combined with
GLR${}_{\varepsilon_{0}}$ stopping (3), the EB-TC${}_{\varepsilon_{0}}$
algorithm with fixed $\beta=1/2$ is $(\varepsilon_{0},\delta)$-PAC and
satisfies that, for all $\nu\in\mathcal{D}^{K}$ with mean $\mu$,

$\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]\leq\inf_{\tilde{\varepsilon}\in[0,\varepsilon_{0}]}\max\left\\{T_{\mu,\varepsilon_{0}}(\delta,\tilde{\varepsilon})+1,\>S_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})\right\\}+2K^{2}\>,$

where $T_{\mu,\varepsilon_{0}}(\delta,\tilde{\varepsilon})$ and
$S_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})$ are defined by

$\displaystyle
T_{\mu,\varepsilon_{0}}(\delta,\tilde{\varepsilon})=\sup\\{n\mid n-1\leq
2(1+\gamma)^{2}\sum_{i\in\mathcal{I}_{\tilde{\varepsilon}}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)(\sqrt{c(n-1,\delta)}+\sqrt{4\log
n})^{2}\\}\>,$ $\displaystyle
S_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})=h_{1}\left(\frac{16(1+\gamma^{-1})}{a_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})}H_{\mu,\varepsilon_{0}}(\tilde{\varepsilon}),\>\frac{(1+\gamma^{-1})K^{2}}{a_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})}+1\right)\>,$
$\displaystyle
a_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})=\frac{\min_{i\in\mathcal{I}_{\tilde{\varepsilon}}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)}{\sum_{i\in\mathcal{I}_{\tilde{\varepsilon}}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)}\min\limits_{i\in\mathcal{I}_{\tilde{\varepsilon}}(\mu),j\neq
i}w_{\varepsilon_{0},1/2}(\mu,i)_{j}\>,$

where $\gamma\in(0,1/2]$ is an analysis parameter and $h_{1}(y,z)\approx
z+y\log(z+y\log(y))$ as in Lemma 51. $T_{\varepsilon_{0},1/2}(\mu,i)$ and
$w_{\varepsilon_{0},1/2}(\mu,i)$ are defined in (1) and

$\displaystyle
H_{\mu,\varepsilon_{0}}(\tilde{\varepsilon}):=\frac{2|i^{\star}(\mu)|}{\Delta_{\mu}(\tilde{\varepsilon})^{2}}+(|\mathcal{I}_{\tilde{\varepsilon}}(\mu)\setminus
i^{\star}(\mu)|)C_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})^{2}+\sum_{i\notin\mathcal{I}_{\tilde{\varepsilon}}(\mu)}\max\\{C_{\mu,\varepsilon_{0}}(\tilde{\varepsilon}),\sqrt{2}\Delta_{i}^{-1}\\}^{2}\>,$
(5)

with
$\Delta_{\mu}(\tilde{\varepsilon})=\min_{k\notin\mathcal{I}_{\tilde{\varepsilon}}(\mu)}\Delta_{k}$
and
$C_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})=\max\\{2\Delta_{\mu}(\tilde{\varepsilon})^{-1}-\varepsilon_{0}^{-1},\varepsilon_{0}^{-1}\\}$.

The upper bound on $\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]$ involves
a $\delta$-dependent term
$T_{\mu,\varepsilon_{0}}(\delta,\tilde{\varepsilon})$ and a
$\delta$-independent term $S_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})$. The
choice of $\tilde{\varepsilon}$ influences the compromise between those, and
the infimum over $\tilde{\varepsilon}$ means that our algorithm benefits from
the best possible trade-off. In the asymptotic regime, we take
$\tilde{\varepsilon}=0$ and $\gamma\to 0$ and we obtain $\lim_{\delta\to
0}\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]/\log(1/\delta)\leq
2|i^{\star}(\mu)|T_{\varepsilon_{0},1/2}(\mu)$. When $|i^{\star}(\mu)|=1$, we
recover the asymptotic result of Theorem 1 up to a multiplicative factor $2$.
For multiple best arms, the asymptotic sample complexity is at most a factor
$2|i^{\star}(\mu)|$ from the $\beta$-optimal one.

Given a finite confidence, the dominant term will be
$S_{\mu,\varepsilon_{0}}(\tilde{\varepsilon})$. For $\tilde{\varepsilon}=0$,
we show that
$H_{\mu,\varepsilon_{0}}(0)=\mathcal{O}(K\min\\{\Delta_{\min},\varepsilon_{0}\\}^{-2})$,
hence we should consider $\tilde{\varepsilon}>0$ to avoid the dependency in
$\Delta_{\min}$. For $\tilde{\varepsilon}=\varepsilon_{0}$, there exists
instances such that
$\max_{i\in\mathcal{I}_{\varepsilon_{0}}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)$
is arbitrarily large, hence $S_{\mu,\varepsilon_{0}}(\varepsilon_{0})$ will be
very large as well. The best trade-off is attained in the interior of the
interval $(0,\varepsilon_{0})$. For $\tilde{\varepsilon}=\varepsilon_{0}/2$,
Lemma 10 shows that
$T_{\varepsilon_{0},1/2}(\mu,i)=\mathcal{O}(K/\varepsilon_{0}^{2})$ for all
$i\in\mathcal{I}_{\varepsilon_{0}/2}(\mu)$ and
$H_{\mu,\varepsilon_{0}}(\varepsilon_{0}/2)=\mathcal{O}(K/\varepsilon_{0}^{2})$.
Therefore, we obtain an upper bound
$\mathcal{O}(|\mathcal{I}_{\varepsilon_{0}/2}(\mu)|K\varepsilon_{0}^{-2}\log\varepsilon_{0}^{-1})$.

Likewise, Lemma 10 shows that $\min_{j\neq
i}w_{\varepsilon_{0},1/2}(\mu,i)_{j}\geq(16(K-2)+2)^{-1}$ for all
$i\in\mathcal{I}_{\varepsilon_{0}/2}(\mu)$. While the dependency in
$a_{\mu,\varepsilon_{0}}(\varepsilon_{0}/2)$ is milder in $\varepsilon$-BAI
than in BAI (as it is bounded away from $0$), we can improve it by using a
refined analysis (see Appendix E). Introduced in [20], this method allows to
clip $\min_{j\neq i}w_{\varepsilon_{0},1/2}(\mu,i)_{j}$ by a fixed value
$x\in[0,(K-1)^{-1}]$ for all $i\in\mathcal{I}_{\tilde{\varepsilon}}(\mu)$.

##### Comparison with existing upper bounds

The LUCB algorithm [24] has a structure similar to a Top Two algorithm, with
the differences that LUCB samples both the leader and the challenger and that
it stops when the gap between the UCB and LCB indices is smaller than
$\varepsilon_{0}$. As LUCB satisfies
$\mathbb{E}_{\mu}[\tau_{\varepsilon_{0},\delta}]\leq
292H_{\varepsilon_{0}}(\mu)\log(H_{\varepsilon_{0}}(\mu)/\delta)+16$ where
$H_{\varepsilon_{0}}(\mu)=\sum_{i}(\max\\{\Delta_{i},\varepsilon_{0}/2\\})^{-2}$,
it enjoys better scaling than EB-TC${}_{\varepsilon_{0}}$ for finite
confidence. However, since the empirical allocation of LUCB is not converging
towards $w_{\varepsilon_{0},1/2}(\mu)$, it is not asymptotically
$1/2$-optimal. While LUCB has better moderate confidence guarantees, there is
no hope to prove anytime performance bounds since LUCB indices depends on
$\delta$. In contrast, EB-TC${}_{\varepsilon_{0}}$ enjoys such guarantees (see
Section 4).

##### Key technical tool for the non-asymptotic analysis

We want to ensure that EB-TC${}_{\varepsilon_{0}}$ eventually selects only
$\varepsilon$-good arms as leader, for any error $\varepsilon\geq 0$. Our
proof strategy is to show that if the leader is not an $\varepsilon$-good arm
and empirical means do not deviate too much from the true means, then either
the current leader or the current challenger was selected as leader or
challenger less than a given quantity. We obtain a bound on the total number
of times that can happen.

######  Lemma 4.

Let $\delta\in(0,1]$ and $n>K$. Let $T_{n}(i):=\sum_{j\neq
i}(T_{n}(i,j)+T_{n}(j,i))$ be the number of times arm $i$ was selected in the
leader/challenger pair. Assume there exists a sequence of events
$(A_{t}(n,\delta))_{n\geq t>K}$ and positive reals
$(D_{i}(n,\delta))_{i\in[K]}$ such that, for all $t\in\\{K+1,\ldots,n\\}$,
under the event $A_{t}(n,\delta)$,

$\exists i_{t}\in[K],\quad T_{t}(i_{t})\leq
D_{i_{t}}(n,\delta)\quad\text{and}\quad T_{t+1}(i_{t})=T_{t}(i_{t})+1\>.$ (6)

Then, we have
$\sum_{t=K+1}^{n}\mathds{1}\left(A_{t}(n,\delta)\right)\leq\sum_{i\in[K]}D_{i}(n,\delta)$.

To control the deviation of the empirical means and empirical gaps to their
true value, we use a sequence of concentration events
$(\mathcal{E}_{n,\delta})_{n>T}$ defined in Lemma 45 (Appendix G.2) such that
$\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\complement})\leq K^{2}\delta
n^{-s}$ where $s\geq 0$ and $\delta\in(0,1]$. For the EB-
TC${}_{\varepsilon_{0}}$ algorithm with fixed $\beta=1/2$, we prove that,
under $\mathcal{E}_{n,\delta}$,
$\\{B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)\\}$ is a “bad” event
satisfying the assumption of Lemma 4. This yields Lemma 5, which essentially
says that the leader is an $\varepsilon$-good arm except for a logarithmic
number of rounds.

######  Lemma 5.

Let $\delta\in(0,1]$, $n>K$ and $\varepsilon\geq 0$. Under the event
$\mathcal{E}_{n,\delta}$, we have

$\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}\sum_{j}T_{n}(i,j)\geq
n-1-8H_{\mu,\varepsilon_{0}}(\varepsilon)f_{2}(n,\delta)-3K^{2}\>,$

where $f_{2}(n,\delta)=\log(1/\delta)+(2+s)\log n$ and
$H_{\mu,\varepsilon_{0}}(\varepsilon)$ is defined in (5).

Noticeably, Lemma 5 holds for any $\varepsilon\geq 0$ even when there are
multiple best arms. As expected the number of times the leader is not among
the $\varepsilon_{0}$-good arms depends on
$H_{\mu,\varepsilon_{0}}(\varepsilon_{0})=\mathcal{O}(K/\varepsilon_{0}^{2})$.
The number of times the leader is not among the best arms depends on
$H_{\mu,\varepsilon_{0}}(0)=\mathcal{O}(K(\min\\{\Delta_{\min},\varepsilon_{0}\\})^{-2})$.

##### Time-varying slack

Theorem 1 shows the asymptotic optimality of the EB-TC${}_{\varepsilon_{0}}$
algorithm with IDS for $\varepsilon_{0}$-BAI (where $\varepsilon_{0}>0$). To
obtain optimality for BAI, we consider time-varying slacks
$(\varepsilon_{n})_{n}$, where $(\varepsilon_{n})_{n}$ is decreasing,
$\varepsilon_{n}>0$ and $\varepsilon_{n}\to_{+\infty}0$. A direct adaptation
of our asymptotic analysis on $\mathbb{E}_{\nu}[\tau_{0,\delta}]$ (see
Appendix D), regardless of the choice of $(\varepsilon_{n})_{n}$, one can show
that using GLR0 stopping, the EB-TC${}_{(\varepsilon_{n})_{n}}$ algorithm with
IDS is $(0,\delta)$-PAC and is asymptotically optimal in BAI. Its empirical
performance is however very sensitive to the choice of $(\varepsilon_{n})_{n}$
(Appendix J.2.3).

##  4 Beyond fixed-confidence guarantees

Could an algorithm analyzed in the fixed-confidence setting be used for the
fixed-budget or even anytime setting? This question is especially natural for
EB-TC${}_{\varepsilon_{0}}$, which does not depend on the confidence parameter
$\delta$. Yet its answer is not obvious, as it is known that algorithms that
have _optimal_ asymptotic guarantees in the fixed-confidence setting can be
sub-optimal in terms of error probability. Indeed [28] prove in their Appendix
C that for any asymptotically optimal (exact) BAI algorithm, there exists
instances in which the error probability cannot decay exponentially with the
horizon, which makes them worse than the (minimax optimal) uniform sampling
strategy [5].

Their argument also applies to $\beta$-optimal algorithms, hence to EB-TC0
with $\beta=1/2$. However, whenever $\varepsilon_{0}$ is positive, Theorem 3
reveals that the error probability of EB-TC${\varepsilon_{0}}$ always decays
exponentially, which redeems the use of optimal fixed-confidence algorithms
for a relaxed BAI problem in the anytime setting. Going further, this result
provides an anytime bound on the probability to recommend an arm that is not
$\varepsilon$-optimal, for any error $\varepsilon\geq 0$. This bound involves
instance-dependent complexities depending solely on the gaps in $\mu$. To
state it, we define $C_{\mu}:=|\\{\mu_{i}\mid i\in[K]\\}|$ as the number of
distinct arm means in $\mu$ and let
$\mathcal{C}_{\mu}(i):=\\{k\in[K]\mid\mu_{\star}-\mu_{k}=\Delta_{i}\\}$ be the
set of arms having mean gap $\Delta_{i}$ where the gaps are sorted by
increasing order $0=\Delta_{1}<\Delta_{2}<\cdots<\Delta_{C_{\mu}}$. For all
$\varepsilon\geq 0$, let $i_{\mu}(\varepsilon)=i$ if
$\varepsilon\in[\Delta_{i},\Delta_{i+1})$ (with the convention
$\Delta_{C_{\mu}+1}=+\infty$). Theorem 3 shows that the exponential decrease
of
$\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu)\right)$
is linear.

######  Theorem 3.

(see Theorem 6 in Appendix F) Let $\varepsilon_{0}>0$. The EB-
TC${}_{\varepsilon_{0}}$ algorithm with fixed proportions $\beta=1/2$
satisfies that, for all $\nu\in\mathcal{D}^{K}$ with mean $\mu$, for all
$\varepsilon\geq 0$, for all $n>5K^{2}/2$,

$\displaystyle\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu)\right)\leq
K^{2}e^{2}(2+\log
n)^{2}\exp\left(-p\left(\frac{n-5K^{2}/2}{8H_{i_{\mu}(\varepsilon)}(\mu,\varepsilon_{0})}\right)\right)\>.$

where $p(x)=x-\log x$ and $(H_{i}(\mu,\varepsilon_{0}))_{i\in[C_{\mu}-1]}$ are
such that
$H_{1}(\mu,\varepsilon_{0})=K(2\Delta_{\min}^{-1}+3\varepsilon_{0}^{-1})^{2}$
and $K/\Delta_{i+1}^{-2}\leq H_{i}(\mu,\varepsilon_{0})\leq
K\min_{j\in[i]}\max\\{2\Delta_{j+1}^{-1},\>2\frac{\Delta_{j}/\varepsilon_{0}+1}{\Delta_{i+1}-\Delta_{j}}+3\varepsilon_{0}^{-1}\\}^{2}$
for all $i>1$.

This bound can be compared with the following uniform $\varepsilon$-error
bound of the strategy using uniform sampling and recommending the empirical
best arm:

$\mathbb{P}\left(\hat{\imath}_{n}^{\text{U}}\notin\mathcal{I}_{\varepsilon}(\mu)\right)\leq\sum_{i\notin\mathcal{I}_{\varepsilon}(\mu)}\exp\left(-\frac{\Delta_{i}^{2}\lfloor
n/K\rfloor}{4}\right)\leq
K\exp\left(-\frac{n-K}{4K\Delta_{i_{\mu}(\varepsilon)+1}^{-2}}\right)$

Recalling that the quantity $H_{i}(\mu,\varepsilon_{0})$ in Theorem 3 is
always bounded from below by $2K\Delta_{i+1}^{-1}$, we get that our upper
bound is larger than the probability of error of the uniform strategy, but the
two should be quite close. For example for $\varepsilon=0$, we have

$\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin
i^{\star}(\mu)\right)\\!\leq\exp\left(-\Theta\\!\left(\frac{n}{K(\Delta_{\min}^{-1}+\varepsilon_{0}^{-1})^{2}}\right)\right)\>,\>\
\mathbb{P}_{\nu}\left(\hat{\imath}_{n}^{\text{U}}\notin
i^{\star}(\mu)\right)\\!\leq\exp\left(-\Theta\\!\left(\frac{n}{K\Delta_{\min}^{-2}}\right)\right).$

Even if they provide a nice sanity-check for the use of a sampling rule with
optimal fixed-confidence guarantees for $\varepsilon_{0}$-BAI in the anytime
regime, we acknowledge that these guarantees are far from optimal. Indeed, the
work of [41] provides tighter anytime uniform $\varepsilon$-error probability
bounds for two algorithms: an anytime version of Sequential Halving [25] using
a doubling trick (called DSH), and an algorithm called Bracketting Sequential
Halving, that is designed to tackle a very large number of arms. Their upper
bounds are of the form
$\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu)\right)\leq\exp\left(-\Theta\left(n/H(\varepsilon)\right)\right)$
with $H(\varepsilon)=\frac{1}{g(\varepsilon/2)}\max_{i\geq
g(\varepsilon)+1}\frac{i}{\Delta_{i}^{2}}$ where
$g(\varepsilon)=|\\{i\in[K]\mid\mu_{i}\geq\mu^{\star}-\varepsilon\\}|$.
Therefore, they can be much smaller than
$K\Delta_{i_{\mu}(\varepsilon)+1}^{-2}$.

The BUCB algorithm of [26] is also analyzed for any level of error
$\varepsilon$, but in a different fashion. The authors provide bounds on its
$(\varepsilon,\delta)$-_unverifiable sample complexity_ , defined as the
expectation of the smallest stopping time $\tilde{\tau}$ satisfying
$\mathbb{P}(\forall
t\geq\tilde{\tau},\hat{\imath}_{n}\in\mathcal{I}_{\varepsilon}(\mu))\geq
1-\delta$. This notion is different from the sample complexity we use in this
paper, which is sometimes called _verifiable_ since it is the time at which
the algorithm can guarantee that its error probability is less than $\delta$.
Interestingly, to prove Theorem 3 we first prove a bound on the unverifiable
sample complexity of EB-TC${}_{\varepsilon_{0}}$ which is valid for all
$(\varepsilon,\delta)$, neither of which are parameters of the algorithm. More
precisely, we prove that $\mathbb{P}_{\nu}\left(\forall
n>U_{i_{\mu}(\varepsilon),\delta}(\mu,\varepsilon_{0}),\>\hat{\imath}_{n}\in\mathcal{I}_{\varepsilon}(\mu)\right)\geq
1-\delta$ for $U_{i,\delta}(\mu,\varepsilon_{0})=_{\delta\to
0}8H_{i}(\mu,\varepsilon_{0})\log(1/\delta)+\mathcal{O}(\log\log(1/\delta))$.
As this statement is valid for all $\delta\in(0,1)$, applying it for each $n$
to $\delta_{n}$ such that
$U_{i_{\mu}(\varepsilon),\delta_{n}}(\mu,\varepsilon_{0})=n$, we obtain
Theorem 3. We remark that such a trick cannot be applied to BUCB to get
uniform $\varepsilon$-error bounds for any time, as the algorithm does depend
on $\delta$.

##### Simple regret

As already noted by [41], uniform $\varepsilon$-error bounds easily yield
simple regret bounds. We state in Corollary 1 the one obtained for EB-
TC${}_{\varepsilon_{0}}$. As a motivation to derive simple regret bounds, we
observe that they readily translate to bounds on the cumulative regret for an
agent observing the stream of recommendations $(\hat{\imath}_{n})$ and playing
arm $\hat{\imath}_{n}$. An exponentially decaying simple regret leads to a
constant cumulative regret in this decoupled exploration/exploitation setting
[2, 33].

######  Corollary 1.

Let $\varepsilon_{0}>0$. Let $p(x)$ and
$(H_{i}(\mu,\varepsilon_{0}))_{i\in[C_{\mu}-1]}$ be defined as in Theorem 3.
The EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed $\beta=1/2$ satisfies
that, for all $\nu\in\mathcal{D}^{K}$ with mean $\mu$, for all $n>5K^{2}/2$,

$\displaystyle\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]\leq
K^{2}e^{2}(2+\log
n)^{2}\sum_{i\in[C_{\mu}-1]}(\Delta_{i+1}-\Delta_{i})\exp\left(-p\left(\frac{n-5K^{2}/2}{8H_{i}(\mu,\varepsilon_{0})}\right)\right)\>.$

Following the discussion above, this bound is not expected to be state-of-the-
art, it rather justifies that EB-TC${}_{\varepsilon_{0}}$ with
$\varepsilon_{0}>0$ is not too much worse than the uniform sampling strategy.
Yet, as we shall see in our experiments, the practical story is different. In
Section 5, we compare the simple regret of EB-TC${}_{\varepsilon_{0}}$ to that
of DSH in synthetic experiments with a moderate number of arms, revealing the
superior performance of EB-TC${}_{\varepsilon_{0}}$.

##  5 Experiments

We assess the performance of the EB-TC${}_{\varepsilon_{0}}$ algorithm on
Gaussian instances both in terms of its empirical stopping time and its
empirical simple regret, and we show that it perform favorably compared to
existing algorithms in both settings. For the sake of space, we only show the
results for large sets of arms and for a specific instance with
$|i^{\star}(\mu)|=2$.

Figure 2: (a) Empirical stopping time on “$\alpha=0.3$” instances for varying
$K$ and stopping rule (3) using $(\varepsilon,\delta)=(0.1,0.01)$. The BAI
algorithms T3C, EB-TCI and TTUCB are modified to be $\varepsilon$-BAI ones.
(b) Empirical simple regret on instance $\mu=(0.6,0.6,0.55,0.45,0.3,0.2)$, in
which EB-TC${}_{\varepsilon_{0}}$ with slack $\varepsilon_{0}=0.1$ and fixed
$\beta=1/2$ is used.

##### Empirical stopping time

We study the impact of large sets of arms (up to $K=1000$) in
$\varepsilon$-BAI for $(\varepsilon,\delta)=(0.1,0.01)$ on the “$\alpha=0.3$”
scenario of [18] which sets $\mu_{i}=1-((i-1)/(K-1))^{\alpha}$ for all
$i\in[K]$. EB-TC${}_{\varepsilon_{0}}$ with IDS and slack
$\varepsilon_{0}=\varepsilon$ is compared to existing $\varepsilon$-BAI
algorithms having low computational cost. This precludes algorithms such as
$\varepsilon$-Track-and-Stop (TaS) [16], Sticky TaS [10] or $\varepsilon$-BAI
adaptation of FWS [39] and DKM [11]. In Appendix J.2.2, we compare EB-TCε to
those algorithms on benchmarks with smaller number of arms. We show that EB-
TCε performs on par with $\varepsilon$-TaS and $\varepsilon$-FWS, but
outperforms $\varepsilon$-DKM. As Top Two benchmarks with fixed $\beta=1/2$,
we consider T3C [36], EB-TCI [21] and TTUCB [20]. To provide a fair
comparison, we adapt them to tackle $\varepsilon$-BAI by using the stopping
rule (3) and by adapting their sampling rule to use the TC$\varepsilon$
challenger from (2) (with a penalization $\log N_{n,i}$ for EB-TCI). We use
the heuristic threshold $c(n,\delta)=\log((1+\log n)/\delta)$. While it is too
small to ensure the $(\varepsilon,\delta)$-PAC property, it still yields an
empirical error which is several orders of magnitude lower than $\delta$.
Finally, we compare with LUCB [24] and uniform sampling. For a fair
comparison, LUCB uses $\sqrt{2c(n-1,\delta)/N_{n,i}}$ as bonus, which is also
too small to yield valid confidence intervals. Our results are averaged over
$100$ runs, and the standard deviations are displayed. In Figure 2(a), we see
that EB-TCε performs on par with the $\varepsilon$-T3C heuristic, and
significantly outperforms the other algorithms. While the scaling in $K$ of
$\varepsilon$-EB-TCI and LUCB appears to be close to the one of EB-TCε,
$\varepsilon$-TTUCB and uniform sampling obtain a worse one. Figure 2(a) also
reveals that the regularization ensured by the TC$\varepsilon$ challenger is
sufficient to ensure enough exploration, hence other exploration mechanisms
are superfluous (TS/UCB leader or TCI challenger).

##### Anytime empirical simple regret

The EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed $\beta=1/2$ and
$\varepsilon_{0}=0.1$ is compared to existing algorithms on the instance
$\mu=(0.6,0.6,0.55,0.45,0.3,0.2)$ from [16], which has two best arms. As
benchmark, we consider Doubling Successive Reject (DSR) and Doubling
Sequential Halving (DSH), which are adaptations of the elimination based
algorithms SR [1] and SH [25]. SR eliminates one arm with the worst empirical
mean at the end of each phase, and SH eliminated half of them but drops past
observations between each phase. These doubling-based algorithms have
empirical error decreasing by steps: they change their recommendation only
before they restart. In Figure 2(b), we plot the average of the simple regret
over $10000$ runs and the standard deviation of that average (which is too
small to see clearly). We observe that EB-TC${}_{\varepsilon_{0}}$ outperforms
uniform sampling, as well as DSR and DSH, which both perform worse due to the
dropped observations. The favorable performance of EB-TC${}_{\varepsilon_{0}}$
is confirmed on other instances from [16], and for “two-groups” instances with
varying $|i^{\star}(\mu)|$ (see Figures 10 and 12).

##### Supplementary experiments

Extensive experiments and implementation details are available in Appendix J.
In Appendix J.2.1, we compare the performance of EB-TC${}_{\varepsilon_{0}}$
with different slacks $\varepsilon_{0}$ for IDS and fixed $\beta=1/2$. In
Appendix J.2.2, we demonstrate the good empirical performance of EB-
TC${}_{\varepsilon_{0}}$ compared to state-of-the art methods in the fixed-
confidence $\varepsilon$-BAI setting, compared to DSR and DSH for the
empirical simple regret, and compared to SR and SH for the probability of
$0$-error in the fixed-budget setting (Figure 13). We consider a wide range of
instances: random ones, benchmarks from the literature [18, 16] and “two-
groups” instances with varying $|i^{\star}(\mu)|$.

##  6 Perspectives

We have proposed the EB-TC${}_{\varepsilon_{0}}$ algorithm, which is easy to
understand and implement. EB-TC${}_{\varepsilon_{0}}$ is the first algorithm
to be simultaneously asymptotically optimal in the fixed-confidence
$\varepsilon_{0}$-BAI setting (Theorem 1), have finite-confidence guarantees
(Theorem 2), and have also anytime guarantees on the probability of error at
any level $\varepsilon$ (Theorem 3), hence on the simple regret (Corollary 1).
Furthermore, we have demonstrated that the EB-TC${}_{\varepsilon_{0}}$
algorithm achieves superior performance compared to other algorithms, in
benchmarks where the number of arms is moderate to large. In future work, we
will investigate its possible adaptation to the data-poor regime of [41] in
which the number of arms is so large that any algorithm sampling each arm once
is doomed to failure.

While our results hold for general sub-Gaussian distributions, the EB-
TC${}_{\varepsilon_{0}}$ algorithm with IDS and slack $\varepsilon_{0}>0$ only
achieves asymptotic optimality for $\varepsilon_{0}$-BAI with Gaussian
bandits. Even though IDS has been introduced by [40] for general single-
parameter exponential families, it is still an open problem to show asymptotic
optimality for distributions other than Gaussians. While our non-asymptotic
guarantees on $\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]$ and
$\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]$ were obtained for the
EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed $\beta=1/2$, we observed
empirically better performance when using IDS. Deriving similar (or better)
non-asymptotic guarantees for IDS is an interesting avenue for future work.

Finally, the EB-TC${}_{\varepsilon_{0}}$ algorithm is a promising method to
tackle structured bandits. Despite the existence of heuristics for settings
such as Top-k identification [40], it is still an open problem to efficiently
adapt Top Two approaches to cope for other structures such as
$\varepsilon$-BAI in linear bandits.

## Acknowledgments and Disclosure of Funding

Experiments presented in this paper were carried out using the Grid’5000
testbed, supported by a scientific interest group hosted by Inria and
including CNRS, RENATER and several Universities as well as other
organizations (see https://www.grid5000.fr). This work has been partially
supported by the THIA ANR program “AI_PhD@Lille”. The authors acknowledge the
funding of the French National Research Agency under the project BOLD
(ANR-19-CE23-0026-04) and the project FATE (ANR22-CE23-0016-01).

## References

  * Audibert et al. [2010] J.-Y. Audibert, S. Bubeck, and R. Munos.  Best Arm Identification in Multi-armed Bandits.  In _Conference on Learning Theory_ , 2010.
  * Avner et al. [2012] O. Avner, S. Mannor, and O. Shamir.  Decoupling exploration and exploitation in multi-armed bandits.  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , pages 1107–1114, 2012.
  * Barrier et al. [2022] A. Barrier, A. Garivier, and T. Kocák.  A non-asymptotic approach to best-arm identification for gaussian bandits.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , 2022.
  * Bubeck and Cesa-Bianchi [2012] S. Bubeck and N. Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Fondations and Trends in Machine Learning_ , 5(1):1–122, 2012.
  * Bubeck et al. [2011] S. Bubeck, R. Munos, and G. Stoltz.  Pure Exploration in Finitely Armed and Continuous Armed Bandits.  _Theoretical Computer Science 412, 1832-1852_ , 412:1832–1852, 2011.
  * Chen et al. [2017a] L. Chen, J. Li, and M. Qiao.  Towards instance optimal bounds for best arm identification.  _Conference on Learning Theory_ , 2017a.
  * Chen et al. [2017b] L. Chen, J. Li, and M. Qiao.  Nearly instance optimal sample complexity bounds for top-k arm selection.  In _Artificial Intelligence and Statistics_ , 2017b.
  * Chen and Ryzhov [2023] Y. Chen and I. O. Ryzhov.  Balancing optimal large deviations in sequential selection.  _Management Science_ , 69(6):3457–3473, 2023\.
  * Degenne [2019] R. Degenne.  _Impact of structure on the design and analysis of bandit algorithms_.  PhD thesis, Université de Paris, 2019.
  * Degenne and Koolen [2019] R. Degenne and W. M. Koolen.  Pure exploration with multiple correct answers.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Degenne et al. [2019] R. Degenne, W. M. Koolen, and P. Ménard.  Non-asymptotic pure exploration by solving games.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Degenne et al. [2020] R. Degenne, H. Shao, and W. M. Koolen.  Structure adaptive algorithms for stochastic bandits.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Even-Dar et al. [2006] E. Even-Dar, S. Mannor, and Y. Mansour.  Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems.  _Journal of Machine Learning Research_ , 7:1079–1105, 2006\.
  * Gabillon et al. [2012] V. Gabillon, M. Ghavamzadeh, and A. Lazaric.  Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence.  In _Advances in Neural Information Processing Systems_ , 2012.
  * Garivier and Kaufmann [2016] A. Garivier and E. Kaufmann.  Optimal best arm identification with fixed confidence.  In _Proceedings of the 29th Conference On Learning Theory_ , 2016\.
  * Garivier and Kaufmann [2021] A. Garivier and E. Kaufmann.  Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models.  _Sequential Analysis_ , 40(1):61–96, 2021.
  * Jamieson et al. [2014] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck.  lil’UCB: an Optimal Exploration Algorithm for Multi-Armed Bandits.  In _Proceedings of the 27th Conference on Learning Theory_ , 2014\.
  * Jamieson and Nowak [2014] K. G. Jamieson and R. D. Nowak.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In _Conference on Information Sciences and Systems (CISS)_ , 2014\.
  * Jourdan and Degenne [2022a] M. Jourdan and R. Degenne.  Choosing answers in $\varepsilon$-best-answer identification for linear bandits.  In _International Conference on Machine Learning (ICML)_ , 2022a.
  * Jourdan and Degenne [2022b] M. Jourdan and R. Degenne.  Non-asymptotic analysis of a ucb-based top two algorithm.  _arXiv preprint arXiv:2210.05431_ , 2022b.
  * Jourdan et al. [2022] M. Jourdan, R. Degenne, D. Baudry, R. De Heide, and E. Kaufmann.  Top two algorithms revisited.  _Advances in Neural Information Processing Systems_ , 2022.
  * Jourdan et al. [2023] M. Jourdan, R. Degenne, and E. Kaufmann.  Dealing with unknown variances in best-arm identification.  _International Conference on Algorithmic Learning Theory_ , 2023.
  * Jun and Nowak [2016] K.-W. Jun and R. Nowak.  Anytime exploration for multi-armed bandits using confidence information.  In _International Conference on Machine Learning (ICML)_ , 2016.
  * Kalyanakrishnan et al. [2012] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone.  PAC subset selection in stochastic multi-armed bandits.  In _International Conference on Machine Learning (ICML)_ , 2012\.
  * Karnin et al. [2013] Z. Karnin, T. Koren, and O. Somekh.  Almost optimal Exploration in multi-armed bandits.  In _International Conference on Machine Learning (ICML)_ , 2013\.
  * Katz-Samuels and Jamieson [2020] J. Katz-Samuels and K. Jamieson.  The true sample complexity of identifying good arms.  In _International Conference on Artificial Intelligence and Statistics_ , 2020.
  * Kaufmann and Koolen [2021] E. Kaufmann and W. M. Koolen.  Mixture martingales revisited with applications to sequential tests and confidence intervals.  _Journal of Machine Learning Research_ , 22(246):1–44, 2021.
  * Komiyama et al. [2022] J. Komiyama, T. Tsuchiya, and J. Honda.  Minimax optimal algorithms for fixed-budget best arm identification.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Lattimore and Szepesvari [2019] T. Lattimore and C. Szepesvari.  _Bandit Algorithms_.  Cambridge University Press, 2019.
  * Locatelli et al. [2016] A. Locatelli, M. Gutzeit, and A. Carpentier.  An optimal algorithm for the thresholding bandit problem.  In _International Conference on Machine Learning (ICML)_ , 2016.
  * Mannor and Tsitsiklis [2004] S. Mannor and J. Tsitsiklis.  The Sample Complexity of Exploration in the Multi-Armed Bandit Problem.  _Journal of Machine Learning Research_ , pages 623–648, 2004.
  * Qin et al. [2017] C. Qin, D. Klabjan, and D. Russo.  Improving the expected improvement algorithm.  In _Advances in Neural Information Processing Systems 30 (NIPS)_ , 2017.
  * Rouyer and Seldin [2020] C. Rouyer and Y. Seldin.  Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits.  In _Conference on Learning Theory_ , pages 3227–3249. PMLR, 2020\.
  * Russo [2016] D. Russo.  Simple Bayesian algorithms for best arm identification.  In _Proceedings of the 29th Conference on Learning Theory (COLT)_ , 2016.
  * Sabato [2019] S. Sabato.  Epsilon-best-arm identification in pay-per-reward multi-armed bandits.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Shang et al. [2020] X. Shang, R. de Heide, E. Kaufmann, P. Ménard, and M. Valko.  Fixed-confidence guarantees for bayesian best-arm identification.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2020.
  * Shin et al. [2018] D. Shin, M. Broadie, and A. Zeevi.  Tractable sampling strategies for ordinal optimization.  _Operations Research_ , 66(6):1693–1712, 2018\.
  * Simchowitz et al. [2017] M. Simchowitz, K. Jamieson, and B. Recht.  The simulator: Understanding adaptive sampling in the moderate-confidence regime.  In _Conference on Learning Theory_ , 2017.
  * Wang et al. [2021] P.-A. Wang, R.-C. Tzeng, and A. Proutiere.  Fast pure exploration via frank-wolfe.  _Advances in Neural Information Processing Systems_ , 2021.
  * You et al. [2023] W. You, C. Qin, Z. Wang, and S. Yang.  Information-directed selection for top-two algorithms.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pages 2850–2851. PMLR, 2023.
  * Zhao et al. [2023] Y. Zhao, C. J. Stephens, C. Szepesvári, and K.-S. Jun.  Revisiting simple regret: Fast rates for returning a good arm.  In _40th International Conference on Machine Learning (ICML)_ , 2023\.

##  Appendix A Outline

The appendices are organized as follows:

  * •

Notation are summarized in Appendix B.

  * •

In Appendix C, we show how the characteristic times and optimal allocations
for $\varepsilon$-BAI can be reduced to the ones of a BAI problem with
modified instances (Lemma 9).

  * •

The asymptotic upper bound on the expected sample complexity of the EB-
TC${}_{\varepsilon_{0}}$ algorithm when combined with the stopping rule (4) is
proven in Appendix D (Theorem 1).

  * •

The non-asymptotic upper bound on the expected sample complexity of the EB-
TC${}_{\varepsilon_{0}}$ algorithm when combined with the stopping rule (4) is
proven in Appendix E (Theorem 5).

  * •

The upper bound on the probability of error and on the simple regret of the
EB-TC${}_{\varepsilon_{0}}$ algorithm is proven in Appendix F (Theorem 6), as
well as the upper bound on its unverifiable expected sample complexity
(Theorem 7).

  * •

Appendix G gathers concentration results used for the calibration of the
stopping rule (Lemma 3) and to control the empirical means and gaps.

  * •

Appendix H gathers existing and new technical results which are used for our
proofs.

  * •

In Appendix I, we discuss the multiplicative notion of $\varepsilon$-goodness,
propose the EB-TC${}_{\varepsilon_{0}}^{\text{m}}$ algorithm and show
asymptotic guarantees on the expected sample complexity when combined with the
appropriate GLR stopping rule (Theorem 8).

  * •

Implementation details and additional experiments are presented in Appendix J.

Table 1: Notation for the setting. Notation | Type | Description
---|---|---
$K$ | $\mathbb{N}$ | Number of arms
$\nu_{i}$ | $\mathcal{D}$ | Sub-Gaussian distribution of arm $i\in[K]$
$\nu$ | $\mathcal{D}^{K}$ | Vector of sub-Gaussian distributions, $\nu:=(\nu_{i})_{i\in[K]}$
$\mu_{i}$ | $\mathbb{R}$ | Mean of arm $i\in[K]$
$\mu$ | $\mathbb{R}^{K}$ | Vector of means, $\mu:=(\mu_{i})_{i\in[K]}$
$\mu_{\star}$ | $\mathbb{R}$ | Largest mean, $\mu_{\star}:=\max_{i\in[K]}\mu_{i}$
$\Delta_{i}$ | $\mathbb{R}_{+}$ | Gap of arm $i$, $\Delta_{i}:=\mu_{\star}-\mu_{i}$
$i^{\star}(\mu)$ | $[K]$ | Best arms, $i^{\star}(\mu):=\operatorname*{arg\,max}_{i\in[K]}\mu_{i}$
$\varepsilon$ | $\mathbb{R}_{+}$ | Additive error of $\varepsilon$-good arms
$\mathcal{I}_{\varepsilon}(\mu)$ | $[K]$ |  $\varepsilon$-Good arms, $\mathcal{I}_{\varepsilon}(\mu):=\\{i\in[K]\mid\Delta_{i}\leq\varepsilon\\}$
$T_{\varepsilon}(\mu),T_{\varepsilon,\beta}(\mu),T_{\varepsilon,\beta}(\mu,i)$ | $\mathbb{R}^{\star}_{+}$ | Asymptotic ($\beta$-)characteristic time for $\varepsilon$-BAI
$w_{\varepsilon}(\mu),w_{\varepsilon,\beta}(\mu),w_{\varepsilon,\beta}(\mu,i)$ | $\triangle_{K}$ | Asymptotic ($\beta$-)optimal allocation for $\varepsilon$-BAI
$C_{\mu}$ | $[K]$ | Number of equivalence classes, $C_{\mu}:=|\\{\mu_{i}\mid i\in[K]\\}|$
$\mathcal{C}_{\mu}(i)$ | $[K]$ | Equivalence class, $\mathcal{C}_{\mu}(i):=\\{k\in[K]\mid\mu_{\star}-\mu_{k}=\Delta_{i}\\}$

##  Appendix B Notation

We recall some commonly used notation: the set of integers
$[n]:=\\{1,\cdots,n\\}$, the complement $X^{\complement}$ and interior
$\mathring{X}$ of a set $X$, the indicator function $\mathds{1}\left(X\right)$
of an event, the probability $\mathbb{P}_{\nu}$ and the expectation
$\mathbb{E}_{\nu}$ under distribution $\nu$, Landau’s notation $o$,
$\mathcal{O}$, $\Omega$ and $\Theta$, the $(K-1)$-dimensional probability
simplex $\triangle_{K}:=\left\\{w\in\mathbb{R}_{+}^{K}\mid w\geq
0,\>\sum_{i\in[K]}w_{i}=1\right\\}$. The functions $\mathcal{C}_{G}$ and
$g_{G}$ are defined in (23), $\overline{W}_{-1}$ in Lemma 49, $h_{1}$ in Lemma
51, $\zeta$ is the Riemann $\zeta$ function. While Table 1 gathers problem-
specific notation, Table 2 groups notation for the algorithms.

Table 2: Notation for algorithms. Notation | Type | Description
---|---|---
$B_{n},B^{\text{EB}}_{n}$ | $[K]$ | (EB) Leader at time $n$
$C_{n},C^{\text{TC}\varepsilon_{0}}_{n}$ | $[K]$ | (TC${}_{\varepsilon_{0}}$) Challenger at time $n$
$I_{n}$ | $[K]$ | Arm sampled at time $n$
$X_{n,I_{n}}$ | $\mathbb{R}$ | Sample observed at the end of time $n$, i.e. $X_{n,I_{n}}\sim\nu_{I_{n}}$
$\mathcal{F}_{n}$ |  | History before time $n$, i.e. $\mathcal{F}_{n}:=\sigma(I_{1},X_{1,I_{1}},\cdots,I_{n},X_{n,I_{n}})$
$\hat{\imath}_{n}$ | $[K]$ | Arm recommended before time $n$
$\tau_{\varepsilon,\delta}$ | $\mathbb{N}$ | Sample complexity (stopping time)
$c(n,\delta)$ | $\mathbb{N}\times(0,1)\to\mathbb{R}^{\star}_{+}$ | Stopping threshold function
$N_{n,i}$ | $\mathbb{N}$ | Number of pulls of arm $i$ before time $n$
$\mu_{n,i}$ | $\mathcal{I}$ | Empirical mean of arm $i$ before time $n$
$T_{n}(i,j)$ | $\mathbb{N}$ | Counts of $(B_{t},C_{t})=(i,j)$ before time $n$
$T_{n}(i)$ | $\mathbb{N}$ | Counts of $i\in\\{B_{t},C_{t}\\}$ before time $n$
$N^{i}_{n,j}$ | $\mathbb{N}$ | Counts of $(B_{t},C_{t},I_{t})=(i,j,j)$ before time $n$
$\beta$ | $(0,1)$ | Fixed proportion
$\beta_{n}(i,j)$ | $(0,1)$ | IDS proportions
$\bar{\beta}_{n}(i,j)$ | $(0,1)$ | Averaged IDS proportions

##  Appendix C Characteristic Times

In Appendix C, we first recall properties satisfied by the
($\beta$-)characteristic times and ($\beta$-)optimal allocation for the BAI
setting with Gaussian bandits. Then, we show how a $\varepsilon$-BAI problem
can be reduced to a BAI one on a modified (and easier) instance.

##### BAI setting

Let $\nu\in\mathcal{D}^{K}$ with mean $\mu\in\mathbb{R}^{K}$. The
($\beta$-)characteristic times for the fixed-confidence BAI setting with
Gaussian bandits $\mathcal{N}(\mu,1)$ are defined as

$T^{\star}(\mu)=\min_{\beta\in(0,1)}T^{\star}_{\beta}(\mu)\quad\text{with}\quad
2T^{\star}_{\beta}(\mu)^{-1}=\max_{w\in\triangle_{K},w_{i^{\star}}=\beta}\min_{i^{\star}\neq
i}\frac{(\mu_{i^{\star}}-\mu_{i})^{2}}{1/\beta+1/w_{i}}\>,$ (7)

see [15, 34] for example. Let us denote by $w^{\star}_{\beta}(\mu)$ and
$w^{\star}(\mu)$ their maximizer, which we will refer to as ($\beta$-)optimal
allocations. Note that
$(T^{\star}(\mu),T^{\star}_{\beta}(\mu))=(T_{0}(\mu),T_{0,\beta}(\mu))$ and
$(w^{\star}(\mu),w^{\star}_{\beta}(\mu))=(w_{0}(\mu),w_{0,\beta}(\mu))$.

We recall in the following some fundamental results on those quantities
($\beta$-)characteristic times and ($\beta$-)optimal allocations. Lemma 6
proves that the ($\beta$-)optimal allocations are unique, have strictly
positive elements, and shows a worst-case inequality $T^{\star}_{1/2}(\mu)\leq
2T^{\star}(\mu)$. Lemma 6 also holds for any single-parameter exponential
family of distributions and for the non-parametric family of bounded
distributions [21].

######  Lemma 6 ([15, 34, 21]).

If $i^{\star}(\mu)$ is a singleton and $\beta\in(0,1)$, then $w^{\star}(\mu)$
and $w_{\beta}^{\star}(\mu)$ are singletons, i.e. the optimal allocations are
unique, and $w^{\star}(\mu)_{i}>0$ and $w_{\beta}^{\star}(\mu)_{i}>0$ for all
$i\in[K]$. Moreover, we have $T^{\star}_{1/2}(\mu)\leq 2T^{\star}(\mu)$ and
with $\beta^{\star}=w^{\star}_{i^{\star}}(\mu)$. Additionally, we have
$H(\mu)\leq T^{\star}(\mu)\leq 2H(\mu)$ where
$H(\mu)=2\sum_{i\in[K]}\Delta_{i}^{-2}$ where
$\Delta_{i^{\star}}=\Delta_{\min}$.

For Gaussian bandits, Lemma 7 shows that the ($\beta$-)characteristic times
and ($\beta$-)optimal allocations can be obtained by solving a simpler
optimization problem, which is amenable to faster implementation (e.g.
Newton’s iterates). It also provides upper and lower bound on the optimal
allocation of the best arm, and gives hints that a tighter worst-case
inequality $T^{\star}_{1/2}(\mu)\leq r_{K}T^{\star}(\mu)$ might hold.

######  Lemma 7 ([3, 20]).

Assume that $i^{\star}(\mu)=\\{i^{\star}\\}$. Let $r(\mu)$ and
$r_{\beta}(\mu)$ be the solution of $\psi_{\mu}(r)=0$ and
$\varphi_{\mu,\beta}(r)=0$ with, for all $r\in(1/\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2},+\infty)$,

$\psi_{\mu}(r)=\sum_{i\neq
i^{\star}}\frac{1}{\left(r(\mu_{i^{\star}}-\mu_{i})^{2}-1\right)^{2}}-1\quad\text{and}\quad\varphi_{\mu,\beta}(r)=\sum_{i\neq
i^{\star}}\frac{1}{r(\mu_{i^{\star}}-\mu_{i})^{2}-1}-\frac{1-\beta}{\beta}\>,$

Then, $\psi_{\mu}$ and $\varphi_{\mu,\beta}$ are convex and decreasing.
Moreover,

$T^{\star}(\mu)=\frac{2r(\mu)}{1+\sum_{i\neq
i^{\star}}\frac{1}{r(\mu)(\mu_{i^{\star}}-\mu_{i})^{2}-1}}\quad\text{and}\quad
T^{\star}_{\beta}(\mu)=\frac{2r_{\beta}(\mu)}{\beta}\>.$

Additionally, for all $i\neq i^{\star}$, we have $\beta
w^{\star}_{\beta}(\mu)_{i}^{-1}=\beta
T^{\star}_{\beta}(\mu)(\mu_{i^{\star}}-\mu_{i})^{2}/2-1$. For $K=2$,
$w^{\star}(\mu)=(0.5,0.5)$ and
$T^{\star}(\mu)=T^{\star}_{1/2}(\mu)=8(\mu_{1}-\mu_{2})^{2}$. For $K\geq 3$,
we have

$1/(\sqrt{K-1}+1)\leq w^{\star}(\mu)_{i^{\star}}\leq 1/2\>.$

Let $r_{K}=2K/(1+\sqrt{K-1})^{2}$,
$j^{\star}\in\operatorname*{arg\,min}_{j\neq
i^{\star}}\mu_{i^{\star}}-\mu_{j}$ and $x\in\mathbb{R}^{K-2}$ such that
$x_{j}=\frac{\mu_{i^{\star}}-\mu_{j}}{\mu_{i^{\star}}-\mu_{j^{\star}}}$. Then,
we have $T^{\star}_{1/2}(\mu)/T^{\star}(\mu)=\Omega(x)$ (i.e. independent of
$\mu_{i^{\star}}$ and $\mu_{i^{\star}}-\mu_{j^{\star}}$) and

$\displaystyle\Omega(1_{K-2})=r_{K}\quad\text{and}\quad\nabla_{x}\Omega(1_{K-2})=0_{K-2}\>.$

Lemma 8 gathers necessary conditions on the ($\beta$-)optimal allocations at
the equilibrium such as equality of the transportation costs, and a link
between the squared allocation which was refered to as overall balance in
[40].

######  Lemma 8 ([3, 40]).

Assume that $i^{\star}(\mu)=\\{i^{\star}\\}$ and $\beta\in(0,1)$. Then, for
all $i\neq i^{\star}$,

$\displaystyle
2T^{\star}(\mu)^{-1}=\frac{(\mu_{i^{\star}}-\mu_{i})^{2}}{1/w^{\star}(\mu)_{i^{\star}}+1/w^{\star}(\mu)_{i}}\quad\text{and}\quad
2T^{\star}_{\beta}(\mu)^{-1}=\frac{(\mu_{i^{\star}}-\mu_{i})^{2}}{1/\beta+1/w^{\star}_{\beta}(\mu)_{i}}\>.$

Moreover, we have

$w^{\star}(\mu)_{i^{\star}}^{2}=\sum_{i\neq
i^{\star}}w^{\star}(\mu)_{i}^{2}\>.$

##### Reduction of an $\varepsilon$-BAI problem to a BAI problem

Lemma 9 gives a reduction of a $\varepsilon$-BAI problem to a BAI one on a
modified instance, which is easier. Thanks to Lemma 9, it is possible to
leverage existing results on $T^{\star}(\mu)$, $T^{\star}_{\beta}(\mu)$,
$w^{\star}(\mu)$, $w^{\star}_{\beta}(\mu)$ (such as Lemmas 6, 7 and 8) in
order to study $T_{\varepsilon}(\mu)$, $T_{\varepsilon,\beta}(\mu)$,
$T_{\varepsilon,\beta}(\mu,i)$, $w_{\varepsilon}(\mu)$,
$w_{\varepsilon,\beta}(\mu)$ and $w_{\varepsilon,\beta}(\mu,i)$.

######  Lemma 9.

Let $\mu\in\mathbb{R}^{K}$, $\varepsilon\geq 0$ and
$\tilde{\varepsilon}\in[0,\varepsilon]$ and $\beta\in(0,1)$. For all
$i\in\mathcal{I}_{\tilde{\varepsilon}}(\mu)$, we define $\mu_{\varepsilon}(i)$
as $\mu_{\varepsilon}(i)_{j}=\mu_{j}-\varepsilon$ for all $j\neq i$ and
$\mu_{\varepsilon}(i)_{i}=\mu_{i}$. Then, for all
$i\in\mathcal{I}_{\tilde{\varepsilon}}(\mu)$,
$T_{\varepsilon,\beta}(\mu,i)=T^{\star}_{\beta}(\mu_{\varepsilon}(i))$ and
$w_{\varepsilon,\beta}(\mu,i)=w^{\star}_{\beta}(\mu_{\varepsilon}(i))$.
Moreover, for all $i^{\star}\in i^{\star}(\mu)$,

$T_{\varepsilon}(\mu)=T^{\star}(\mu_{\varepsilon}(i^{\star}))\quad\text{and}\quad
T_{\varepsilon,\beta}(\mu)=T^{\star}_{\beta}(\mu_{\varepsilon}(i^{\star}))\>.$

Moreover, we have $w_{\varepsilon}(\mu)=\bigcup_{i^{\star}\in
i^{\star}(\mu)}w^{\star}(\mu_{\varepsilon}(i^{\star}))$ and
$w_{\varepsilon,\beta}(\mu)=\bigcup_{i^{\star}\in
i^{\star}(\mu)}w^{\star}_{\beta}(\mu_{\varepsilon}(i^{\star}))$.

###### Proof.

For $\varepsilon=0$, the result is direct by definition. Let $\varepsilon>0$
and $\tilde{\varepsilon}\in[0,\varepsilon]$. The first part is obtained by
definition of $T^{\star}_{\varepsilon,\beta}(\mu,i)$,
$w^{\star}_{\varepsilon,\beta}(\mu,i)$. Let $i^{\star}\in i^{\star}(\mu)$ and
$\mu_{\varepsilon}(i^{\star})$ defined as above, hence
$i^{\star}(\mu_{\varepsilon}(i^{\star}))=\\{i^{\star}\\}$. For all
$i\in\mathcal{I}_{\varepsilon}(\mu)\setminus i^{\star}(\mu)$, let us denote by
$\lambda^{(i^{\star},i)}_{\varepsilon}$ the instance such that
$\lambda^{(i^{\star},i)}_{\varepsilon,i}=\mu_{i}$ and
$\lambda^{(i^{\star},i)}_{\varepsilon,j}=\mu_{j}-\varepsilon$ for all $j\neq
i$. If $\mu_{i^{\star}}-\mu_{i}=\varepsilon$ then
$i^{\star}(\lambda^{(i^{\star},i)}_{\varepsilon})=\\{i\\}\cup
i^{\star}(\mu)\setminus\\{i^{\star}\\}$, otherwise
$i^{\star}(\lambda^{(i^{\star},i)}_{\varepsilon})=\\{i\\}$. We consider the
permutation $\sigma$ that swaps arm $i$ with arm $i^{\star}$. By symmetry, we
have
$T^{\star}(\lambda^{(i^{\star},i)}_{\varepsilon})=T^{\star}(\sigma(\lambda^{(i^{\star},i)}_{\varepsilon}))$.
Moreover, we have that the gaps of
$\sigma(\lambda^{(i^{\star},i)}_{\varepsilon})$ are all strictly smaller than
the gaps of $\mu_{\varepsilon}$ since $\varepsilon\geq\Delta_{i}>0$.
Therefore, Lemma 11 of Barrier et al (2022) yields that
$T^{\star}(\sigma(\lambda^{(i^{\star},i)}_{\varepsilon}))>T^{\star}(\mu_{\varepsilon})$.
We have proved that

$\forall i^{\star}\in i^{\star}(\mu),\quad
T^{\star}(\mu_{\varepsilon}(i^{\star}))<\min_{i\in\mathcal{I}_{\varepsilon}(\mu)\setminus
i^{\star}(\mu)}T^{\star}(\lambda^{(i^{\star},i)}_{\varepsilon})\>.$

By symmetry $T^{\star}(\mu_{\varepsilon}(i^{\star}))$ is constant for all
$i^{\star}\in i^{\star}(\mu)$, hence we have shown that

$\forall i^{\star}\in i^{\star}(\mu),\quad
T_{\varepsilon}(\mu)=T^{\star}(\mu_{\varepsilon}(i^{\star}))\>.$

It also shows that $w_{\varepsilon}(\mu)=\bigcup_{i^{\star}\in
i^{\star}(\mu)}w^{\star}(\mu_{\varepsilon}(i^{\star}))$. The same reasoning
yields the result for $T_{\varepsilon,\beta}(\mu)$ and
$w_{\varepsilon,\beta}(\mu)$. ∎

#####  $\varepsilon$-BAI problems cannot be arbitrarily difficult

Lemma 10 shows that, for all $i\in\mathcal{I}_{\varepsilon/2}(\mu)$,
$T_{\varepsilon,1/2}(\mu,i)$ cannot be arbitrarily large and $\min_{j\neq
i}w_{\varepsilon_{0},1/2}(\mu,i)_{j}$ cannot be arbitrarily small. The proof
relies on Lemma 9 and existing results for BAI.

######  Lemma 10.

Let $\varepsilon>0$ and $\mu\in\mathbb{R}^{K}$. Then, for all
$i\in\mathcal{I}_{\varepsilon/2}(\mu)$, we have
$T_{\varepsilon,1/2}(\mu,i)\leq 32K/\varepsilon^{2}$ and $\min_{j\neq
i}w_{\varepsilon,1/2}(\mu,i)_{j}\geq(16(K-2)+2)^{-1}$.

###### Proof.

Let $i\in\mathcal{I}_{\varepsilon/2}(\mu)$, hence
$\mu_{i}\geq\mu_{\star}-\varepsilon/2$. Let $\mu_{\varepsilon}(i)$ as in Lemma
9 which satisfies that $i^{\star}(\mu_{\varepsilon}(i))=\\{i\\}$. Let
$\Delta_{i,j}=\mu_{i}-\mu_{j}$ and $\Delta_{i,i}=\mu_{i}-\max_{j\neq
i}\mu_{j}$. Then, we have

$\displaystyle
T_{\varepsilon,1/2}(\mu,i)=T^{\star}_{1/2}(\mu_{\varepsilon}(i))\leq
2T^{\star}(\mu_{\varepsilon}(i))\leq
8\sum_{j\in[K]}(\Delta_{i,j}+\varepsilon)^{-2}\leq
8\sum_{j\in[K]}(\Delta_{j}+\varepsilon/2)^{-2}\>,$

where we used Lemma 6 for the two first inequality and
$i\in\mathcal{I}_{\varepsilon/2}(\mu)$ for the last one. Since $\Delta_{j}\geq
0$, we conclude that $T_{\varepsilon,\beta}(\mu,i)\leq 32K/\varepsilon^{2}$.
Moreover, using Lemma 6, we have

$\displaystyle
T_{\varepsilon,1/2}(\mu,i)=T^{\star}_{1/2}(\mu_{\varepsilon}(i))\geq
T^{\star}(\mu_{\varepsilon}(i))\geq
2\sum_{j\in[K]}(\Delta_{i,j}+\varepsilon)^{-2}\>.$

Likewise, using Lemma 9 and Lemma 7, we obtain that, for all $j\neq i$,

$\displaystyle
w_{\varepsilon,1/2}(\mu)_{j}^{-1}/2=w^{\star}_{1/2}(\mu_{\varepsilon}(i))_{j}^{-1}/2$
$\displaystyle=T^{\star}_{1/2}(\mu_{\varepsilon}(i))(\mu_{i}-\mu_{j}+\varepsilon)^{2}/4-1$
$\displaystyle\leq
2\sum_{k\notin\\{i,j\\}}\left(\frac{\mu_{i}-\mu_{j}+\varepsilon}{\mu_{i}-\mu_{k}+\varepsilon}\right)^{2}+1$

where the last inequality uses what we proved above. When
$\mu_{k}\leq\mu_{j}$, the ratio is smaller than one. When $\mu_{k}>\mu_{j}$,
we have $\mu_{\star}\geq\mu_{k}>\mu_{j}\geq\mu_{\star}-\varepsilon/2$, hence
$\mu_{k}-\mu_{j}\leq\varepsilon/2$ and

$\frac{\mu_{i}-\mu_{j}+\varepsilon}{\mu_{i}-\mu_{k}+\varepsilon}\leq
1+\frac{\varepsilon/2}{\mu_{\star}-\mu_{k}+\varepsilon/2}\leq 2\>.$

Therefore, we obtain $w_{\varepsilon,1/2}(\mu)_{j}^{-1}/2\leq 8(K-2)+1$, which
concludes the result. ∎

Lemma 11 links the characteristic times for $\varepsilon$-BAI where
$\varepsilon\in\\{\varepsilon_{0},\varepsilon_{1}\\}$.

######  Lemma 11.

Let $\mu\in\mathbb{R}^{K}$ such that $|i^{\star}(\mu)|=1$. Let
$\varepsilon_{0}>\varepsilon_{1}$. Then, for all $\beta\in(0,1)$, we have

$T_{\varepsilon_{0}}(\mu)(\Delta_{\min}+\varepsilon_{0})^{2}\geq
T_{\varepsilon_{1}}(\mu)(\Delta_{\min}+\varepsilon_{1})^{2}\quad\text{and}\quad
T_{\varepsilon_{0},\beta}(\mu)(\Delta_{\min}+\varepsilon_{0})^{2}\geq
T_{\varepsilon_{1},\beta}(\mu)(\Delta_{\min}+\varepsilon_{1})^{2}\>.$

Let $\varepsilon_{0}<\varepsilon_{1}$. Then,

$T_{\varepsilon_{0}}(\mu)(\Delta_{\max}+\varepsilon_{0})^{2}\geq
T_{\varepsilon_{1}}(\mu)(\Delta_{\max}+\varepsilon_{1})^{2}\quad\text{and}\quad
T_{\varepsilon_{0},\beta}(\mu)(\Delta_{\max}+\varepsilon_{0})^{2}\geq
T_{\varepsilon_{1},\beta}(\mu)(\Delta_{\max}+\varepsilon_{1})^{2}\>.$

###### Proof.

Let $i^{\star}(\mu)=\\{i^{\star}\\}$. Let $\varepsilon_{0}>\varepsilon_{1}$.
Using Lemma 9, we have

$\displaystyle
2T_{\varepsilon}(\mu)^{-1}(\Delta_{\min}+\varepsilon)^{-2}=\max_{w\in\triangle_{K}}\min_{j\neq
i^{\star}}\frac{\tilde{\Delta}_{j}(\varepsilon)^{2}}{1/w_{i^{\star}}+1/w_{j}}\quad\text{with}\quad\tilde{\Delta}_{j}(\varepsilon)=\frac{\mu_{\star}-\mu_{j}+\varepsilon}{\Delta_{\min}+\varepsilon}\>.$

To conclude the first part of the first result, a sufficient condition is to
show that
$\tilde{\Delta}_{j}(\varepsilon_{1})\geq\tilde{\Delta}_{j}(\varepsilon_{0})$
for all $j\neq i^{\star}$. Direct manipulations show that, for all $j\neq
i^{\star}$,

$\displaystyle\tilde{\Delta}_{j}(\varepsilon_{1})\geq\tilde{\Delta}_{j}(\varepsilon_{0})\>$
$\displaystyle\iff\>1-\frac{\varepsilon_{0}-\varepsilon_{1}}{\mu_{\star}-\mu_{j}+\varepsilon_{0}}\geq
1-\frac{\varepsilon_{0}-\varepsilon_{1}}{\Delta_{\min}+\varepsilon_{0}}\>\iff\>\mu_{\star}-\mu_{j}\geq\Delta_{\min}\>,$

hence the result holds. The same proof can be used to obtain the second part
of the first result.

Let $\varepsilon_{0}<\varepsilon_{1}$. Using Lemma 9, we have

$\displaystyle
2T_{\varepsilon}(\mu)^{-1}(\Delta_{\max}+\varepsilon)^{-2}=\max_{w\in\triangle_{K}}\min_{j\neq
i^{\star}}\frac{\bar{\Delta}_{j}(\varepsilon)^{2}}{1/w_{i^{\star}}+1/w_{j}}\quad\text{with}\quad\bar{\Delta}_{j}(\varepsilon)=\frac{\mu_{\star}-\mu_{j}+\varepsilon}{\Delta_{\max}+\varepsilon}\>.$

To conclude the first part of the second result, a sufficient condition is to
show that
$\bar{\Delta}_{j}(\varepsilon_{1})\geq\bar{\Delta}_{j}(\varepsilon_{0})$ for
all $j\neq i^{\star}$. Direct manipulations show that, for all $j\neq
i^{\star}$,

$\displaystyle\bar{\Delta}_{j}(\varepsilon_{1})\geq\bar{\Delta}_{j}(\varepsilon_{0})\>$
$\displaystyle\iff\>1+\frac{\varepsilon_{1}-\varepsilon_{0}}{\mu_{\star}-\mu_{j}+\varepsilon_{0}}\geq
1+\frac{\varepsilon_{1}-\varepsilon_{0}}{\Delta_{\max}+\varepsilon_{0}}\>\iff\>\mu_{\star}-\mu_{j}\leq\Delta_{\max}\>,$

hence the result holds. The same proof can be used to obtain the second part
of the second result. ∎

##  Appendix D Asymptotic analysis

Let $\varepsilon_{0}>0$, $\beta\in(0,1)$ and $\delta\in(0,1)$. In this
section, we provide an asymptotic analysis of EB-TC${}_{\varepsilon_{0}}$
slack $\varepsilon_{0}>0$ combined with the stopping rule (3) with parameters
$(\varepsilon_{0},\delta)$. First, we detail IDS proportions in Appendix D.1.
Then, we sketch the proof for fixed proportions $\beta$ in Appendix D.2.

In the following, we consider a sub-Gaussian bandit with distribution
$\nu\in\mathcal{D}^{K}$ having mean parameter $\mu\in\mathbb{R}^{K}$ with a
unique best arm, i.e. $i^{\star}(\mu)=\\{i^{\star}\\}$. We restate Theorem 1
below.

######  Theorem 4 (Theorem 1).

Let $\varepsilon_{0}>0$, $\varepsilon_{1}\geq 0$ and $\delta\in(0,1)$. Using
the threshold (4) in the stopping rule (3) with slack $\varepsilon_{1}$, the
EB-TC${}_{\varepsilon_{0}}$ algorithm is $(\varepsilon_{1},\delta)$-PAC. For
IDS proportions, it satisfies that, for all $\nu\in\mathcal{D}^{K}$ such that
$|i^{\star}(\mu)|=1$,

$\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]}{\log(1/\delta)}\leq
T_{\varepsilon_{0}}(\mu)\left(1+\max_{i\neq
i^{\star}}\frac{\varepsilon_{0}-\varepsilon_{1}}{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1}}\right)^{2}\>.$

Let $\beta\in(0,1)$. For fixed proportions $\beta$, it satisfies that, for all
$\nu\in\mathcal{D}^{K}$ such that $|i^{\star}(\mu)|=1$,

$\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]}{\log(1/\delta)}\leq
T_{\varepsilon_{0},\beta}(\mu)\left(1+\max_{i\neq
i^{\star}}\frac{\varepsilon_{0}-\varepsilon_{1}}{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1}}\right)^{2}\>.$

Theorem 1 provides asymptotic upper bound on the expected sample complexity of
the EB-TC${}_{\varepsilon_{0}}$ algorithm when combined with the stopping rule
(3). When $\varepsilon_{1}=\varepsilon_{0}$ and for Gaussian distributions,
combining Lemma 1 and Theorem 1 shows that the EB-TC${}_{\varepsilon_{0}}$
algorithm is asymptotically optimal for $\varepsilon_{0}$-BAI when using IDS
proportions and asymptotically $\beta$-optimal for $\varepsilon_{0}$-BAI when
using fixed proportions $\beta$. Until recently [40], proving asymptotic
optimality of Top Two algorithms with adaptive choice $\beta$ was an open
problem in the BAI literature. Our work extends their analysis to tackle the
$\varepsilon$-BAI setting. Compared to previous work, we removed the
assumption that sub-optimal arms should have distinct means.

Considering $\varepsilon_{1}\neq\varepsilon_{0}$ can be interesting when the
practitioner decides to tackle $\varepsilon$-BAI with an error $\varepsilon$
which is different from the slack $\varepsilon_{0}$ used by the EB-
TC${}_{\varepsilon_{0}}$ algorithm. Those situations occur when the
practitioner is observing the data collected by the EB-
TC${}_{\varepsilon_{0}}$ algorithm without having control over it. Theorem 1
show that the resulting sequential hypothesis testing has still asymptotic
guarantees on the expected sample complexity. Quite naturally, those
guarantees are not asymptotically optimal even for Gaussian distributions. The
sub-optimality multiplicative gap of IDS proportions (that is, the ratio of
the upper bound in Theorem 1 and the characteristic time for
$\varepsilon_{1}$-BAI, $T_{\varepsilon_{1}}(\mu)$) is

$\frac{T_{\varepsilon_{0}}(\mu)}{T_{\varepsilon_{1}}(\mu)}\frac{(\Delta_{\min}+\varepsilon_{0})^{2}}{(\Delta_{\min}+\varepsilon_{1})^{2}}\geq
1\quad\text{when }\varepsilon_{0}>\varepsilon_{1}\text{ ,
otherwise}\quad\frac{T_{\varepsilon_{0}}(\mu)}{T_{\varepsilon_{1}}(\mu)}\frac{(\Delta_{\max}+\varepsilon_{0})^{2}}{(\Delta_{\max}+\varepsilon_{1})^{2}}\geq
1\>,$

where the inequalities comes from Lemma 11 and justify that there is no
contradiction with the asymptotic lower bound on the expected sample
complexity (Lemma 1). The same reasoning applies to fixed proportions $\beta$
by replacing $T_{\varepsilon}(\mu)$ by $T_{\varepsilon,\beta}(\mu)$.

##### Concentration result

For both proofs, we use the following concentration result of the empirical
mean for sub-Gaussian observations (Lemma 12). This is a standard tool for the
asymptotic analysis of Top Two algorithms (e.g. Lemma 3 in [32], Lemma 5 in
[36] or Lemma 14 in [21]), hence we omit the proof.

######  Lemma 12.

There exists a sub-Gaussian random variable $W_{\mu}$ such that almost surely,
for all $i\in[K]$ and all $n$ such that $N_{n,i}\geq 1$,

$\displaystyle|\mu_{n,i}-\mu_{i}|\leq
W_{\mu}\sqrt{\frac{\log(e+N_{n,i})}{N_{n,i}}}\>.$

In particular, any random variable which is polynomial in $W_{\mu}$ has a
finite expectation.

###  D.1 IDS proportions

Using Lemma 9, the optimal allocation for $\varepsilon_{0}$-BAI are defined as

$w_{\varepsilon_{0}}(\mu):=\operatorname*{arg\,max}_{w\in\triangle_{K}}\min_{i\neq
i^{\star}}\frac{(\mu_{i^{\star}}-\mu_{i}+\varepsilon_{0})^{2}}{1/w_{i^{\star}}+1/w_{i}}\>.$

Since $|i^{\star}(\mu)|=1$, let
$\mu_{\varepsilon_{0}}=\mu_{\varepsilon_{0}}(i^{\star})$ where
$\mu_{\varepsilon}(i^{\star})$ as in Lemma 9. Since we have
$T_{\varepsilon_{0}}(\mu)=T^{\star}(\mu_{\varepsilon_{0}})$ and
$w_{\varepsilon_{0}}(\mu)=w^{\star}(\mu_{\varepsilon_{0}})$, Lemma 6 and 8
yield that $w_{\varepsilon_{0}}(\mu)=\\{w^{\star}\\}$ is a singleton with
unique element denotes by $w^{\star}$ which satisfies that
$\min_{i\in[K]}w^{\star}_{i}>0$,

$\sum_{i\neq
i^{\star}}\left(\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right)^{2}=1\>,$
(8)

and

$\forall
i\in[K]\setminus\\{i^{\star}\\},\quad\frac{(\mu_{i^{\star}}-\mu_{i}+\varepsilon_{0})^{2}}{1/w^{\star}_{i^{\star}}+1/w^{\star}_{i}}=2T_{\varepsilon_{0}}(\mu)^{-1}\>.$
(9)

[40] refers to (8) as the overall balance equation. The key novelty of their
analysis is to show that asymptotically the empirical proportions satisfy the
same equation, referred to as the empirical overall balance, when using IDS
proportions with sampling to choose among the leader and the challenger. The
key novelty in our work lies in proving that the empirical overall balance
equation is also satisfied when using IDS proportions with $K(K-1)$ tracking
procedures to select between the leader and the challenger (see Appendix
D.1.2).

##### Convergence time

We follow an asymptotic analysis similar to the ones used in [32, 36, 21] with
the improvement from [40]. Let $\gamma>0$. Let us define the _convergence
time_ $T_{\varepsilon_{0},\gamma}$, which is a random variable quantifies the
number of samples required for the empirical allocations
$\left(N_{n,i}/N_{n,i^{\star}}\right)_{i\neq i^{\star}}$ to be $\gamma$-close
to $\left(w^{\star}_{i}/w^{\star}_{i^{\star}}\right)_{i\neq i^{\star}}$:

$T_{\varepsilon_{0},\gamma}:=\inf\left\\{T\geq 1\mid\forall n\geq
T,\>\max_{i\neq
i^{\star}}\left|\frac{N_{n,i}}{N_{n,i^{\star}}}-\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right|\leq\gamma\right\\}\>.$
(10)

Lemma 13 gives a sufficient condition to prove Theorem 1 for IDS proportions.
The case $\varepsilon_{0}=\varepsilon_{1}$ is a direct consequence of
combining Theorem 13 and Proposition 14 in [40]. The proof is inspired by
existing methods, e.g. Theorem 2 in [21] or Theorem 3 in [32].

######  Lemma 13.

Let $\varepsilon_{0}>0$, $\varepsilon_{1}\geq 0$ and $\delta\in(0,1)$. Assume
that there exists $\gamma_{1}(\mu)>0$ such that for all
$\gamma\in(0,\gamma_{1}(\mu)]$,
$\mathbb{E}_{\nu}[T_{\varepsilon_{0},\gamma}]<+\infty$. Using the threshold
(4) in the stopping rule (3) with slack $\varepsilon_{1}$ yields an algorithm
such that, for all $\nu\in\mathcal{D}^{K}$ such that $|i^{\star}(\mu)|=1$,

$\limsup_{\delta\to
0}\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]}{\log\left(1/\delta\right)}\leq
T_{\varepsilon_{0}}(\mu)\left(1+\max_{i\neq
i^{\star}}\frac{\varepsilon_{0}-\varepsilon_{1}}{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1}}\right)^{2}\>.$

###### Proof.

Let $\gamma>0$. Let us define by

$\tilde{T}_{\gamma,\varepsilon_{0}}:=\inf\left\\{T\geq 1\mid\forall n\geq
T,\>\left\|\frac{N_{n}}{n-1}-w^{\star}\right\|_{\infty}\leq\gamma\right\\}\>.$

Using that

$\sum_{i\neq
i^{\star}}\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}=\frac{1}{w^{\star}_{i^{\star}}}-1\quad\text{and}\quad\sum_{i\neq
i^{\star}}\frac{N_{n,i}}{N_{n,i^{\star}}}=\frac{n-1}{N_{n,i^{\star}}}-1\>,$

it is direct to see that for all $n\geq T_{\gamma}$

$\displaystyle\left|\frac{N_{n,i^{\star}}}{n-1}-w^{\star}_{i^{\star}}\right|$
$\displaystyle=\left|\frac{n-1}{N_{n,i^{\star}}}-\frac{1}{w^{\star}_{i^{\star}}}\right|\frac{N_{n,i^{\star}}}{n-1}w^{\star}_{i^{\star}}\leq\left|\frac{n-1}{N_{n,i^{\star}}}-\frac{1}{w^{\star}_{i^{\star}}}\right|\leq\gamma(K-1)\>,$
$\displaystyle\left|\frac{N_{n,i}}{n-1}-w^{\star}_{i}\right|$
$\displaystyle=w^{\star}_{i^{\star}}\left|\frac{N_{n,i}}{n-1}\left(\frac{1}{w^{\star}_{i^{\star}}}-\frac{n-1}{N_{n,i^{\star}}}\right)+\frac{N_{n,i}}{N_{n,i^{\star}}}-\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right|$
$\displaystyle\leq\left|\frac{1}{w^{\star}_{i^{\star}}}-\frac{n-1}{N_{n,i^{\star}}}\right|+\left|\frac{N_{n,i}}{N_{n,i^{\star}}}-\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right|\leq\gamma
K\>.$

Therefore, for all $\gamma\in(0,\gamma_{1}(\mu)/K]$,
$\mathbb{E}_{\nu}[\tilde{T}_{\gamma,\varepsilon_{0}}]<+\infty$.

Let $\mu_{\varepsilon_{0}}$ as in Lemma 9. Since we have
$T_{\varepsilon_{0}}(\mu)=T^{\star}(\mu_{\varepsilon_{0}})$ and
$w_{\varepsilon_{0}}(\mu)=w^{\star}(\mu_{\varepsilon_{0}})$, we can leverage
existing results from the BAI literature, e.g. Theorem 2 in [21] or Theorem 3
in [32]. The sole criterion on the stopping threshold is to be asymptotically
tight (Definition 1).

######  Definition 1.

A threshold $c:\mathbb{N}\times(0,1]\to\mathbb{R}_{+}$ is said to be
asymptotically tight if there exists $\alpha\in[0,1)$, $\delta_{0}\in(0,1]$,
functions $f,\bar{T}:(0,1]\to\mathbb{R}_{+}$ and $C$ independent of $\delta$
satisfying: (1) for all $\delta\in(0,\delta_{0}]$ and $n\geq\bar{T}(\delta)$,
then $c(n,\delta)\leq f(\delta)+Cn^{\alpha}$, (2) $\limsup_{\delta\to
0}f(\delta)/\log(1/\delta)\leq 1$ and (3) $\limsup_{\delta\to
0}\bar{T}(\delta)/\log(1/\delta)=0$.

Since $\mathcal{C}_{G}$ defined in (23) satisfies $\mathcal{C}_{G}\approx
x+\log(x)$, it is direct to see that

$c(n,\delta)=2\mathcal{C}_{G}\left(\frac{1}{2}\log\left(\frac{K-1}{\delta}\right)\right)+4\log\left(4+\log\frac{n}{2}\right)$

is asymptotically tight, e.g. by taking $(\alpha,\delta_{0},C)=(1/2,1,4)$,
$f(\delta)=2\mathcal{C}_{G}\left(\frac{1}{2}\log\left(\frac{K-1}{\delta}\right)\right)$
and $\bar{T}(\delta)=1$.

Based on continuity arguments and using that
$\mathbb{E}_{\nu}[T_{\varepsilon_{0},\gamma}]<+\infty$, the proof of Theorem 2
in [21] yields that

$\limsup_{\delta\to
0}\frac{\mathbb{E}_{\nu}[\tau_{\delta}]}{\log\left(1/\delta\right)}\leq\left(\min_{i\neq
i^{\star}}\frac{(\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1})^{2}}{2\left(1/w^{\star}_{i^{\star}}+1/w^{\star}_{i}\right)}\right)^{-1}=T_{\varepsilon_{0}}(\mu)\max_{i\neq
i^{\star}}\left(\frac{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{0}}{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1}}\right)^{2}\>,$

where the equality uses the condition at the equilibrium (9). This concludes
the proof. ∎

Using Lemma 13, the proof of Theorem 1 for IDS proportions boils down to
showing that $\mathbb{E}_{\nu}[T_{\varepsilon_{0},\gamma}]<+\infty$. As in
[32, 36, 21, 40], the proof is divided in several steps. First, we show that
all the arms are sufficient explored for $n$ large enough (Appendix D.1.1).
Second, we prove that the empirical overall balance equation approximately
holds for $n$ large enough (Appendix D.1.2). Finally, we show convergence of
the empirical ratio of proportions towards the ratio of optimal allocation,
i.e. $\mathbb{E}_{\nu}[T_{\varepsilon_{0},\gamma}]<+\infty$ (Appendix D.1.3).

####  D.1.1 Sufficient exploration

To upper bound the expected convergence time, as prior work we first establish
sufficient exploration. Given an arbitrary threshold $L\in\mathbb{R}_{+}^{*}$,
we define the sampled enough set and its arms with highest mean (when not
empty) as

$S_{n}^{L}:=\\{i\in[K]\mid N_{n,i}\geq
L\\}\quad\text{and}\quad\mathcal{I}_{n}^{\star}:=\operatorname*{arg\,max}_{i\in
S_{n}^{L}}\mu_{i}\>.$ (11)

In all generality $\mathcal{I}_{n}^{\star}$ is a set, yet we obtain
$\mathcal{I}_{n}^{\star}=\\{i^{\star}\\}$ as soon as $i^{\star}\in S_{n}^{L}$.
We define the highly and the mildly under-sampled sets

$U_{n}^{L}:=\\{i\in[K]\mid N_{n,i}<\sqrt{L}\\}\quad\text{and}\quad
V_{n}^{L}:=\\{i\in[K]\mid N_{n,i}<L^{3/4}\\}\>.$ (12)

[21] identifies the properties that the leader and the challenger should
satisfy to ensure sufficient exploration. We improve on their analysis by
removing the need for the distinct means assumption, and supporting IDS
instead of a fixed allocation $\beta$.

Lemma 14 shows that the transportation cost is strictly positive and increases
linearly. Compared to previous results, the key improvement lies in the fact
that the lower bound holds for $(i,j)\in\mathcal{I}_{n}^{\star}\times
S_{n}^{L}$ instead of
$(i,j)\in\mathcal{I}_{n}^{\star}\times\left(S_{n}^{L}\setminus\mathcal{I}_{n}^{\star}\right)$.
This is due to the $\varepsilon_{0}$ regularization, which removes the need to
assume that the means are distinct.

######  Lemma 14.

Let $S_{n}^{L}$ and $\mathcal{I}_{n}^{\star}$ as in (11). There exists $L_{0}$
with $\mathbb{E}_{\mu}[(L_{0})^{\alpha}]<+\infty$ for all $\alpha>0$ such that
if $L\geq L_{0}$, for all $n$ such that $S_{n}^{L}\neq\emptyset$, for all
$(i,j)\in\mathcal{I}_{n}^{\star}\times S_{n}^{L}$ such that $i\neq j$, we have

$\frac{\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,j}}}\geq\sqrt{L}\frac{\varepsilon_{0}}{2\sqrt{2}}\>.$

###### Proof.

Using Lemma 12 and $\min\\{N_{n,i},N_{n,j}\\}\geq L$, we obtain

$\displaystyle\mu_{n,i}-\mu_{n,j}$
$\displaystyle\geq\mu_{i}-\mu_{j}-W_{\mu}\left(\sqrt{\frac{\log(e+N_{n,i})}{N_{n,i}}}+\sqrt{\frac{\log(e+N_{n,j})}{N_{n,j}}}\right)$
$\displaystyle\geq-2W_{\mu}\sqrt{\frac{\log(e+L)}{L}}\geq-\frac{\varepsilon_{0}}{2}\>,$

where the last inequality is obtained for $L\geq L_{0}=L_{1}-e$ which is
defined as

$\displaystyle
L_{1}=\sup\left\\{x\mid\>x<16W_{\mu}^{2}\log(x)/\varepsilon_{0}^{2}+e\right\\}\leq
h_{1}\left(16W_{\mu}/\varepsilon_{0}^{2},e\right)\>.$

The last inequality is obtained by using Lemma 51, and we recall that $h_{1}$
is defined in Lemma 51. Since $h_{1}\left(x,e\right)\sim_{x\to+\infty}x\log
x$, we have $\mathbb{E}_{\mu}[(L_{0})^{\alpha}]<+\infty$ for all $\alpha>0$ by
using Lemma 12 (polynomial in $W_{\mu}$). Then, we have

$\displaystyle\frac{\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,j}}}\geq\frac{\varepsilon_{0}/2}{\sqrt{1/N_{n,i}+1/N_{n,j}}}\geq\sqrt{L}\frac{\varepsilon_{0}}{2\sqrt{2}}\>.$

∎

Lemma 15 gives an upper bound on the transportation costs between a sampled
enough arm and an under-sampled one.

######  Lemma 15.

Let $S_{n}^{L}$ as in (11). There exists $L_{1}$ with
$\mathbb{E}_{\mu}[(L_{1})^{\alpha}]<+\infty$ for all $\alpha>0$ such that for
all $L\geq L_{1}$ and all $n\in\mathbb{N}$,

$\forall(i,j)\in
S_{n}^{L}\times\overline{S_{n}^{L}},\quad\frac{\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,j}}}\leq\sqrt{L}(D_{1}+4W_{\mu})\>,$

where $D_{1}>0$ is a problem dependent constant and $W_{\mu}$ is the random
variables defined in Lemma 12.

###### Proof.

Using Lemma 12 and $N_{n,i}\geq L\geq N_{n,j}\geq 1$, we obtain

$\displaystyle\frac{\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,j}}}$
$\displaystyle\leq\sqrt{N_{n,j}}|\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}|$
$\displaystyle\leq\sqrt{L}\left(|\mu_{i}-\mu_{j}+\varepsilon_{0}|+W_{\mu}\left(\sqrt{\frac{\log(e+N_{n,i})}{N_{n,i}}}+\sqrt{\frac{\log(e+N_{n,j})}{N_{n,j}}}\right)\right)$
$\displaystyle\leq\sqrt{L}\left(|\mu_{i}-\mu_{j}+\varepsilon_{0}|+2W_{\mu}\sqrt{\log(e+1)}\right)$
$\displaystyle\leq\sqrt{L}(D_{1}+4W_{\mu})\>,$

for $D_{1}=\max_{i\neq j}|\mu_{i}-\mu_{j}+\varepsilon_{0}|$. ∎

Lemma 16 shows the desired property for the EB leader. Since it corresponds to
Lemma 17 in [21], we omit the proof.

######  Lemma 16 (Lemma 17 in [21]).

There exists $L_{2}$ with $\mathbb{E}_{\nu}[(L_{2})^{\alpha}]<+\infty$ for all
$\alpha>0$ such that if $L\geq L_{2}$, for all $n$ (at most polynomial in $L$)
such that $S_{n}^{L}\neq\emptyset$, $B_{n}^{\text{EB}}\in S_{n}^{L}$ implies
$B_{n}^{\text{EB}}\in\mathcal{I}_{n}^{\star}$.

Lemma 17 show that the desired property for the TC challenger. Compared to
existing result, we improve by remove the assumption that all arms have
distinct means thanks to the regularization $\varepsilon_{0}>0$.

######  Lemma 17.

There exists $L_{3}$ with $\mathbb{E}_{\nu}[L_{3}]<+\infty$ such that if
$L\geq L_{3}$, for all $n$ (at most polynomial in $L$) such that
$U_{n}^{L}\neq\emptyset$, $B_{n}^{\text{EB}}\notin V_{n}^{L}$ implies
$C_{n}^{\text{TC}\varepsilon_{0}}\in V_{n}^{L}$.

###### Proof.

In the following, we consider $U_{n}^{L}\neq\emptyset$ (hence
$V_{n}^{L}\neq\emptyset$) and $B_{n}^{\text{EB}}\notin V_{n}^{L}$. Let
$\mathcal{J}_{n}^{\star}=\operatorname*{arg\,max}_{i\in\overline{V_{n}^{L}}}\mu_{i}$
and $L_{2}$ as in Lemma 16. Then, for $L\geq L_{2}^{4/3}$, we have
$B_{n}^{\text{EB}}\in\mathcal{J}_{n}^{\star}$.

Let $L_{0}$ and $(L_{1},D_{1})$ as in Lemmas 14 and 15. Then, for all
$L\geq\max\\{L_{0}^{4/3},L_{2}^{4/3},L_{1}^{2}\\}$,

$\displaystyle B_{n}^{\text{EB}}\in\mathcal{J}_{n}^{\star}\>,$
$\displaystyle\forall(i,j)\in\mathcal{J}_{n}^{\star}\times\overline{V_{n}^{L}},\>\text{s.t.
}i\neq j,\quad$
$\displaystyle\frac{\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,j}}}\geq
L^{3/8}\frac{\varepsilon_{0}}{2\sqrt{2}}\>,$
$\displaystyle\forall(i,j)\in\overline{U_{n}^{L}}\times U_{n}^{L},\quad$
$\displaystyle\frac{\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,j}}}\leq
L^{1/4}(D_{1}+4W_{\mu})\>.$

Since
$\mathcal{J}_{n}^{\star}\subseteq\overline{V_{n}^{L}}\subseteq\overline{U_{n}^{L}}$,
for all $L\geq
L_{3}:=\max\\{L_{0}^{4/3},L_{2}^{4/3},L_{1}^{2},\left(\frac{2\sqrt{2}}{\varepsilon_{0}}(D_{1}+4W_{\mu})\right)^{8}+1\\}$
we have

$\forall(i,k,j)\in\mathcal{J}_{n}^{\star}\times
U_{n}^{L}\times\overline{V_{n}^{L}},\>\text{s.t. }i\neq
j,\quad\frac{\mu_{n,i}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,j}}}>\frac{\mu_{n,i}-\mu_{n,k}+\varepsilon_{0}}{\sqrt{1/N_{n,i}+1/N_{n,k}}}\>.$

As $B_{n}^{\text{EB}}\in\mathcal{J}_{n}^{\star}$, the definition
$C_{n}^{\text{TC}\varepsilon_{0}}$ yields that
$C_{n}^{\text{TC}\varepsilon_{0}}\in V_{n}^{L}$. Otherwise the above strict
inequality would wield a contradiction. Using Lemma 12, we show

$\mathbb{E}_{\bm{F}}[L_{3}]\leq\mathbb{E}_{\bm{F}}\left[\left(\frac{2\sqrt{2}}{\varepsilon_{0}}(D_{1}+4W_{\mu})\right)^{8}+1\right]+\mathbb{E}_{\bm{F}}[(L_{0})^{4/3}]+\mathbb{E}_{\bm{F}}[(L_{2})^{4/3}]+\mathbb{E}_{\bm{F}}[(L_{1})^{2}]<+\infty\>,$

hence this concludes the proof. ∎

Lemma 18 shows that all arms are sufficiently explored and that the leader is
the unique best arm for $n$ large enough.

######  Lemma 18.

There exist $N_{1}$ with $\mathbb{E}_{\nu}[N_{1}]<+\infty$ such that for all
$n\geq N_{1}$ and all $i\in[K]$, $N_{n,i}\geq\sqrt{n/K}$ and
$B_{n}^{\text{EB}}=i^{\star}$.

###### Proof.

Let $L_{2}$ and $L_{3}$ as in Lemmas 16 and 17. Therefore, for $L\geq
L_{4}:=\max\\{L_{3},L_{2}^{4/3}\\}$, for all $n$ such that
$U_{n}^{L}\neq\emptyset$, $B_{n}^{\text{EB}}\in V_{n}^{L}$ or
$C_{n}^{\text{TC}\varepsilon_{0}}\in V_{n}^{L}$. We have
$\mathbb{E}_{\nu}[L_{4}]<+\infty$. There exists a deterministic $L_{5}$ such
that for all $L\geq L_{5}$, $\lfloor L\rfloor\geq KL^{3/4}$. Let
$L\geq\max\\{L_{5},L_{4}\\}$.

Suppose towards contradiction that $U_{\lfloor KL\rfloor}^{L}$ is not empty.
Then, for any $1\leq t\leq\lfloor KL\rfloor$, $U_{t}^{L}$ and $V_{t}^{L}$ are
non empty as well. Using the pigeonhole principle, there exists some $i\in[K]$
such that $N_{\lfloor L\rfloor,i}\geq L^{3/4}$. Thus, we have
$\left|V_{\lfloor L\rfloor}^{L}\right|\leq K-1$. Our goal is to show that
$\left|V_{\lfloor 2L\rfloor}^{L}\right|\leq K-2$. A sufficient condition is
that one arm in $V_{\lfloor L\rfloor}^{L}$ is pulled at least $L^{3/4}$ times
between $\lfloor L\rfloor$ and $\lfloor 2L\rfloor-1$.

If we have

$\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(\\{B_{t}^{\text{EB}},C_{t}^{\text{TC}\varepsilon_{0}}\\}\subseteq
V_{t}^{L}\right)\geq KL^{3/4}\>,$

then, using that $V_{t}^{L}\subseteq V_{\lfloor L\rfloor}^{L}$, we obtain

$\sum_{t=\lfloor L\rfloor}^{\lfloor 2L\rfloor-1}\mathds{1}\left(I_{t}\in
V_{\lfloor L\rfloor}^{L}\right)\geq\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(I_{t}\in V_{t}^{L}\right)\geq\sum_{t=\lfloor
L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(\\{B_{t}^{\text{EB}},C_{t}^{\text{TC}\varepsilon_{0}}\\}\subseteq
V_{t}^{L}\right)\geq KL^{3/4}\>,$

Therefore, there exists $i\in V_{\lfloor L\rfloor}^{L}$ which is sampled
$L^{3/4}$ times between $\lfloor L\rfloor$ and $\lfloor 2L\rfloor-1$.

In the following, we assume that

$\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(\\{B_{t}^{\text{EB}},C_{t}^{\text{TC}\varepsilon_{0}}\\}\subseteq
V_{t}^{L}\right)<KL^{3/4}\>,$

Since $B_{t}^{\text{EB}}\in V_{t}^{L}$ or $C_{t}^{\text{TC}\varepsilon_{0}}\in
V_{t}^{L}$, we have

$\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\left(\mathds{1}\left(B_{t}^{\text{EB}}\in
V_{t}^{L},C_{t}^{\text{TC}\varepsilon_{0}}\notin
V_{t}^{L}\right)+\mathds{1}\left(B_{t}^{\text{EB}}\notin
V_{t}^{L},C_{t}^{\text{TC}\varepsilon_{0}}\in V_{t}^{L}\right)\right)>\lfloor
2L\rfloor-\lfloor L\rfloor-KL^{3/4}\>.$

Therefore, we have

$\displaystyle\text{\bf Case 1:}\quad\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(B_{t}^{\text{EB}}\in
V_{t}^{L},C_{t}^{\text{TC}\varepsilon_{0}}\notin
V_{t}^{L}\right)>\left(\lfloor 2L\rfloor-\lfloor L\rfloor-
KL^{3/4}\right)/2\>,$ or $\displaystyle\text{\bf Case 2:}\quad\sum_{t=\lfloor
L\rfloor}^{\lfloor 2L\rfloor-1}\mathds{1}\left(B_{t}^{\text{EB}}\notin
V_{t}^{L},C_{t}^{\text{TC}\varepsilon_{0}}\in V_{t}^{L}\right)>\left(\lfloor
2L\rfloor-\lfloor L\rfloor-KL^{3/4}\right)/2\>.$

Since $\beta_{t}(i,j)=N_{t,j}/(N_{t,j}+N_{t,i})$, we obtain

$\displaystyle
1/2\leq\begin{cases}\beta_{t}(B_{t}^{\text{EB}},C_{t}^{\text{TC}\varepsilon_{0}})&\text{if}\quad
B_{t}^{\text{EB}}\in V_{t}^{L},C_{t}^{\text{TC}\varepsilon_{0}}\notin
V_{t}^{L}\\\
1-\beta_{t}(B_{t}^{\text{EB}},C_{t}^{\text{TC}\varepsilon_{0}})&\text{if}\quad
B_{t}^{\text{EB}}\notin V_{t}^{L},C_{t}^{\text{TC}\varepsilon_{0}}\in
V_{t}^{L}\end{cases}\>.$

This lower bound will be crucial to argue that the challenger is sampled
enough in case 2 and the leader is sampled enough in case 1.

Case 1. Using Lemma 46 and the above, we obtain

$\displaystyle\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(I_{t}\in V_{\lfloor L\rfloor}^{L}\right)$
$\displaystyle\geq\sum_{i\in V_{\lfloor L\rfloor}^{L}}\sum_{j\neq
i}\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(I_{t}=i,\>(B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t})=(i,j)\right)$
$\displaystyle\geq\sum_{i\in V_{\lfloor L\rfloor}^{L}}\sum_{j\neq
i}\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\beta_{t}(i,j)\mathds{1}\left((B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t})=(i,j)\right)-K^{2}$
$\displaystyle\geq\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\beta_{t}(B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t})\mathds{1}\left(B^{\text{EB}}_{t}\in
V_{t}^{L},\>C^{\text{TC}\varepsilon_{0}}_{t}\notin V_{t}^{L}\right)-K^{2}$
$\displaystyle\geq\left(\lfloor 2L\rfloor-\lfloor L\rfloor-
KL^{3/4}\right)/4-K^{2}\geq KL^{3/4}\>,$

where the last inequality is obtained for $L\geq L_{6}+1$ with

$L_{6}=\sup\left\\{L\in\mathbb{N}\mid\left(\lfloor 2L\rfloor-\lfloor L\rfloor-
KL^{3/4}\right)/4-K^{2}<KL^{3/4}\right\\}\>.$

Therefore, there exists $i\in V_{\lfloor L\rfloor}^{L}$ which is sampled
$L^{3/4}$ times between $\lfloor L\rfloor$ and $\lfloor 2L\rfloor-1$.

Case 2. Using Lemma 46 and the above, we obtain

$\displaystyle\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(I_{t}\in V_{\lfloor L\rfloor}^{L}\right)$
$\displaystyle\geq\sum_{j\in V_{\lfloor L\rfloor}^{L}}\sum_{i\neq
j}\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}\mathds{1}\left(I_{t}=j,\>(B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t})=(i,j)\right)$
$\displaystyle\geq\sum_{j\in V_{\lfloor L\rfloor}^{L}}\sum_{i\neq
j}\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}(1-\beta_{t}(i,j))\mathds{1}\left((B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t})=(i,j)\right)-K^{2}$
$\displaystyle\geq\sum_{t=\lfloor L\rfloor}^{\lfloor
2L\rfloor-1}(1-\beta_{t}(B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t}))\mathds{1}\left(B^{\text{EB}}_{t}\notin
V_{t}^{L},\>C^{\text{TC}\varepsilon_{0}}_{t}\in V_{t}^{L}\right)-K^{2}$
$\displaystyle\geq\left(\lfloor 2L\rfloor-\lfloor L\rfloor-
KL^{3/4}\right)/4-K^{2}\geq KL^{3/4}\>,$

where the last inequality is obtained for $L\geq L_{6}+1$. Therefore, there
exists $i\in V_{\lfloor L\rfloor}^{L}$ which is sampled $L^{3/4}$ times
between $\lfloor L\rfloor$ and $\lfloor 2L\rfloor-1$.

Summary. We have shown $\left|V_{\lfloor 2L\rfloor}^{L}\right|\leq K-2$. By
induction, for any $1\leq k\leq K$, we have $\left|V_{\lfloor
kL\rfloor}^{L}\right|\leq K-k$, and finally $U_{\lfloor
KL\rfloor}^{L}=\emptyset$ for all $L\geq
L_{7}:=\max\\{L_{5},L_{4},L_{6}+1\\}$. Defining $N_{0}=KL_{7}$, we have
$\mathbb{E}_{\nu}[N_{0}]<+\infty$. For all $n\geq N_{0}$, we let $L=n/K$,
hence we have $U_{n}^{n/K}=U_{\lfloor KL\rfloor}^{L}=\emptyset$. This
concludes the proof of sufficient exploration.

Leader is best arm. Using Lemma 12, we obtain that for all $n\geq N_{0}$,

$\displaystyle\forall i\neq i^{\star},\quad$
$\displaystyle\mu_{n,i}\leq\mu_{i}+W_{\mu}\sqrt{\frac{\log(e+N_{n,i})}{N_{n,i}}}\leq\mu_{i}+W_{\mu}\sqrt{\frac{\log(e+\sqrt{n/K})}{\sqrt{n/K}}}\>,$
$\displaystyle\mu_{n,i^{\star}}\leq\mu_{i^{\star}}-W_{\mu}\sqrt{\frac{\log(e+N_{n,i^{\star}})}{N_{n,i^{\star}}}}\leq\mu_{i^{\star}}-W_{\mu}\sqrt{\frac{\log(e+\sqrt{n/K})}{\sqrt{n/K}}}\>.$

Therefore, we have $B_{n}^{\text{EB}}=i^{\star}$ for all $n\geq
N_{1}:=\max\\{N_{0},K(X_{0}-e)^{2}+1\\}$ where

$X_{0}=\sup\left\\{x>1\mid x<\frac{16W_{\mu}^{2}}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}\log(x)+e\right\\}\leq
h_{1}\left(\frac{16W_{\mu}^{2}}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}},e\right)\>,$

where the last inequality is obtained by using Lemma 51 with $h_{1}$ defined
therein. Since $h_{1}(x,e)\sim_{x\to+\infty}x\log x$, we have

$\mathbb{E}_{\nu}[N_{1}]<\mathbb{E}_{\nu}[N_{0}]+\mathbb{E}_{\nu}[K(X_{0}-e)^{2}+1]<+\infty\>.$

This concludes the proof. ∎

####  D.1.2 Empirical overall balance

As in [40], the key to obtain asymptotic optimality is to show that the
empirical proportion satisfy the empirical overall balance equation. Compared
to them, the novelty of Lemma 19 is that we use IDS proportions with $K(K-1)$
tracking procedures to select between the leader and the challenger instead of
sampling.

######  Lemma 19.

Let $\gamma>0$. There exists $N_{2}$ with $\mathbb{E}_{\nu}[N_{2}]<+\infty$
such that for all $n\geq N_{2}$

$\left|\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{n-1}\right)^{2}\right|\leq\gamma\>.$

###### Proof.

Let $N_{1}$ as in Lemma 18. Then, we have for all $n>N_{1}$

$\displaystyle\frac{N_{n,i^{\star}}}{n-1}=\frac{N^{i^{\star}}_{n,i^{\star}}}{n-1}+\frac{\sum_{i\neq
i^{\star}}N^{i}_{N_{1},i^{\star}}}{n-1}\quad\text{,}\quad\frac{N_{n,i}}{n-1}=\frac{N^{i^{\star}}_{n,i}}{n-1}+\frac{\sum_{j\neq
i^{\star}}N^{j}_{N_{1},i}}{n-1}\>,$
$\displaystyle(1-\bar{\beta}_{n}(i^{\star},j))\frac{T_{n}(i^{\star},j)}{n-1}=\frac{1}{n-1}\sum_{t=N_{1}}^{n-1}\mathds{1}\left(C_{t}=j\right)(1-\beta_{t}(i^{\star},j))+(1-\bar{\beta}_{N_{1}}(i^{\star},j))\frac{T_{N_{1}}(i^{\star},j)}{n-1}\>,$
$\displaystyle\sum_{j\neq
i^{\star}}\bar{\beta}_{n}(i^{\star},j)\frac{T_{n}(i^{\star},j)}{n-1}=\frac{1}{n-1}\sum_{t=N_{1}}^{n-1}\beta_{t}(i^{\star},C_{t})+\sum_{j\neq
i^{\star}}\bar{\beta}_{N_{1}}(i^{\star},j)\frac{T_{N_{1}}(i^{\star},j)}{n-1}$

Chaining the inequalities with Lemma 46, we obtain that

$\displaystyle-\frac{K}{n-1}\leq\frac{N_{n,i^{\star}}}{n-1}-\frac{1}{n-1}\sum_{t=N_{1}}^{n-1}\beta_{t}(i^{\star},C_{t})\leq\frac{2N_{1}+K}{n-1}\>,$
$\displaystyle-\frac{1}{n-1}\leq\frac{N_{n,i}}{n-1}-\frac{1}{n-1}\sum_{t=N_{1}}^{n-1}\mathds{1}\left(C_{t}=j\right)(1-\beta_{t}(i^{\star},j))\leq\frac{2N_{1}+1}{n-1}\>.$

Using that $a^{2}-b^{2}=(a-b)(a+b)\leq 2(a-b)$ for $(a,b)\in(0,1)^{2}$, we
obtain

$\displaystyle-2\frac{K}{n-1}\leq\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\left(\frac{1}{n-1}\sum_{t=N_{1}}^{n-1}\beta_{t}(i^{\star},C_{t})\right)^{2}\leq
2\frac{2N_{1}+K}{n-1}\>,$
$\displaystyle-2\frac{1}{n-1}\leq\left(\frac{N_{n,i}}{n-1}\right)^{2}-\left(\frac{1}{n-1}\sum_{t=N_{1}}^{n-1}\mathds{1}\left(C_{t}=j\right)(1-\beta_{t}(i^{\star},j))\right)^{2}\leq
2\frac{2N_{1}+1}{n-1}\>.$

For all $n>N_{1}$, let us denote by

$G_{n}=\left(\sum_{t=N_{1}}^{n-1}\beta_{t}(i^{\star},C_{t})\right)^{2}-\sum_{j\neq
i^{\star}}\left(\sum_{t=N_{1}}^{n-1}\mathds{1}\left(C_{t}=j\right)(1-\beta_{t}(i^{\star},j))\right)^{2}\>.$

Therefore, we have

$\displaystyle-4K\frac{N_{1}+1}{n-1}\leq\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{n-1}\right)^{2}-\frac{G_{n}}{(n-1)^{2}}\leq
4\frac{N_{1}+K}{n-1}\>.$

Direct manipulations yield that

$\displaystyle\frac{1}{2}(G_{n+1}-G_{n})$
$\displaystyle=\beta_{n}(i^{\star},C_{n})\sum_{t=N_{1}}^{n-1}\beta_{t}(i^{\star},C_{t})-(1-\beta_{n}(i^{\star},C_{n}))\sum_{t=N_{1}}^{n-1}\mathds{1}\left(C_{t}=C_{n}\right)(1-\beta_{t}(i^{\star},C_{n}))$
$\displaystyle+\beta_{n}(i^{\star},C_{n})-1/2\>.$

Therefore, we obtain by using the above inequalities that

$\displaystyle\frac{1}{2}(G_{n+1}-G_{n})$
$\displaystyle\leq\beta_{n}(i^{\star},C_{n})N_{n,i^{\star}}-(1-\beta_{n}(i^{\star},C_{n}))N_{n,C_{n}}+2N_{1}+K+3/2$
$\displaystyle=2N_{1}+K+3/2\>,$ $\displaystyle\frac{1}{2}(G_{n+1}-G_{n})$
$\displaystyle\geq\beta_{n}(i^{\star},C_{n})N_{n,i^{\star}}-(1-\beta_{n}(i^{\star},C_{n}))N_{n,C_{n}}-2N_{1}-K-3/2$
$\displaystyle=-2N_{1}-K-3/2\>,$

where we used that
$\beta_{n}(i^{\star},C_{n})N_{n,i^{\star}}=(1-\beta_{n}(i^{\star},C_{n}))N_{n,C_{n}}$
since
$\beta_{n}(i^{\star},C_{n})=\frac{N_{n,C_{n}}}{N_{n,i^{\star}}+N_{n,C_{n}}}$.
Summing those inequalities, we obtain

$\displaystyle G_{n}=\sum_{t=N_{1}+1}^{n-1}(G_{t+1}-G_{t})+G_{N_{1}+1}$
$\displaystyle\leq(4N_{1}+2K+3)(n-1-N_{1})+1$
$\displaystyle\geq-(4N_{1}+2K+3)(n-1-N_{1})-1\>,$

where we used that
$G_{N_{1}+1}=2\beta_{N_{1}}(i^{\star},C_{N_{1}})-1\in[-1,1]$. Combining
everything together, we have shown that

$\displaystyle\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{n-1}\right)^{2}$ $\displaystyle\leq
4\frac{N_{1}+K}{n-1}+\frac{(4N_{1}+2K+3)(n-1-N_{1})+1}{(n-1)^{2}}$
$\displaystyle\geq-4K\frac{N_{1}+1}{n-1}-\frac{(4N_{1}+2K+3)(n-1-N_{1})+1}{(n-1)^{2}}\>.$

Therefore, we have shown the desired results for $n\geq N_{2}$ defined as

$N_{2}=\inf\left\\{n>2\mid\>4K\frac{N_{1}+1}{n-1}+\frac{(4N_{1}+2K+3)(n-1-N_{1})+1}{(n-1)^{2}}\leq\gamma\right\\}\>,$

which satisfies $\mathbb{E}_{\nu}[N_{2}]<+\infty$ since it is a linear
function of $N_{1}$. ∎

As in [40], using Lemma 19 allows to bound the empirical proportion allocated
to the unique best arm $N_{n,i^{\star}}/(n-1)$ away from $0$ (Lemma 20).

######  Lemma 20.

There exists $N_{3}$ with $\mathbb{E}_{\nu}[N_{3}]<+\infty$ such that for all
$n\geq N_{3}$

$\frac{1}{4\sqrt{2(K-1)}}\leq\frac{N_{n,i^{\star}}}{n-1}\leq\frac{3}{4}\>.$

###### Proof.

Let $N_{2}$ as in Lemma 19 for $\gamma=1/2$. Using Lemma 19, we obtain
$\frac{N_{n,i^{\star}}}{n-1}\leq\frac{3}{4}$ since

$\displaystyle 1/2\geq\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{n-1}\right)^{2}\geq\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\left(1-\frac{N_{n,i^{\star}}}{n-1}\right)^{2}=2\frac{N_{n,i^{\star}}}{n-1}-1\>.$

Let $\tilde{N}_{2}$ as in Lemma 19 for $\gamma=\frac{1}{32(K-1)}$. Similarly
by using Lemma 19, we obtain
$\frac{N_{n,i^{\star}}}{n-1}\geq\frac{1}{4\sqrt{2(K-1)}}$ since

$\displaystyle\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}\geq-\frac{1}{32(K-1)}+\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{n-1}\right)^{2}$
$\displaystyle\geq-\frac{1}{32(K-1)}+\frac{1}{K-1}\left(1-\frac{N_{n,i^{\star}}}{n-1}\right)^{2}$
$\displaystyle\geq\frac{1}{32(K-1)}\>.$

Taking $N_{3}=\max\\{N_{2},\tilde{N}_{2}\\}$ yields the result. ∎

Lemma 21 is a rescaled version of the empirical overall balance equation which
is proven by simply combining Lemma 19 and Lemma 20.

######  Lemma 21.

Let $\gamma>0$. There exists $N_{4}$ with $\mathbb{E}_{\nu}[N_{4}]<+\infty$
such that for all $n\geq N_{4}$

$\left|1-\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{N_{n,i^{\star}}}\right)^{2}\right|\leq\gamma\>.$

###### Proof.

Let $N_{2}$ as in Lemma 19 for $\frac{\gamma}{32(K-1)}$. Let $N_{3}$ as in
Lemma 20. Direct manipulation shows that, for all $n\geq
N_{4}=\max\\{N_{2},N_{3}\\}$,

$\displaystyle\left|1-\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{N_{n,i^{\star}}}\right)^{2}\right|=\left(\frac{n-1}{N_{n,i^{\star}}}\right)^{2}\left|\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{n-1}\right)^{2}\right|\leq
32(K-1)\frac{\gamma}{32(K-1)}=\gamma\>.$

This concludes the result. ∎

####  D.1.3 Convergence towards optimal ratio of allocation

As in [40], we show that a challenger will not be sampled next when the ratio
of its empirical proportion compared to the one of $i^{\star}$ overshoots the
ratio of the optimal allocations (Lemma 22).

######  Lemma 22.

Let $\gamma>0$. There exists $N_{5}$ with $\mathbb{E}_{\nu}[N_{5}]<+\infty$
such that for all $n\geq N_{5}$ and all $i\neq i^{\star}$,

$\frac{N_{n,i}}{N_{n,i^{\star}}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\quad\implies\quad
C_{n}^{\text{TC}\varepsilon_{0}}\neq i\>.$

###### Proof.

Let $\gamma>0$. Let $i\neq i^{\star}$ such that

$\frac{N_{n,i}}{N_{n,i^{\star}}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\>.$

Suppose towards contradiction that

$\forall j\neq
i^{\star},\quad\frac{N_{n,j}}{N_{n,i^{\star}}}>\frac{w^{\star}_{j}}{w^{\star}_{i^{\star}}}\>.$

Let $\tilde{\gamma}>0$. Let $N_{4}$ as in Lemma 21 for $\tilde{\gamma}$. then
using Lemma 21 and 8 yields that, for all $n\geq N_{4}$,

$\displaystyle\tilde{\gamma}\geq\sum_{j\neq
i^{\star}}\left(\frac{N_{n,j}}{N_{n,i^{\star}}}\right)^{2}-1\geq\left(\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\right)^{2}-\left(\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right)^{2}=\gamma\left(\gamma+2\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right)\>.$

Therefore, we have a contradiction if we take $\tilde{\gamma}$ small enough
(e.g. $\tilde{\gamma}<\gamma^{2}$), hence we have shown that, for all $n\geq
N_{4}$,

$\frac{N_{n,i}}{N_{n,i^{\star}}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\quad\implies\quad\exists
j\notin\\{i^{\star},i\\},\quad\frac{N_{n,j}}{N_{n,i^{\star}}}\leq\frac{w^{\star}_{j}}{w^{\star}_{i^{\star}}}\>.$

Let $N_{1}$ as in Lemma 18. Using that $B_{n}^{\text{EB}}=i^{\star}$ for all
$n\geq N_{1}$ and the definition of $C_{n}^{\text{TC}\varepsilon_{0}}$, we
known that

$\displaystyle\frac{\mu_{n,i^{\star}}-\mu_{n,i}+\varepsilon_{0}}{\sqrt{1/N_{n,i^{\star}}+1/N_{n,i}}}>\frac{\mu_{n,i^{\star}}-\mu_{n,j}+\varepsilon_{0}}{\sqrt{1/N_{n,i^{\star}}+1/N_{n,j}}}\quad\implies\quad
C_{n}^{\text{TC}\varepsilon_{0}}\neq i\>.$

To conclude the proof, it is sufficient to show that the ratio of the two
quantities is strictly larger than one. For all $n\geq\max\\{N_{1},N_{4}\\}$,
we obtain

$\displaystyle\frac{\mu_{n,i^{\star}}-\mu_{n,i}+\varepsilon_{0}}{\mu_{n,i^{\star}}-\mu_{n,j}+\varepsilon_{0}}\sqrt{\frac{1+N_{n,i^{\star}}/N_{n,j}}{1+N_{n,i^{\star}}/N_{n,i}}}\geq\frac{\mu_{n,i^{\star}}-\mu_{n,i}+\varepsilon_{0}}{\mu_{n,i^{\star}}-\mu_{n,j}+\varepsilon_{0}}\sqrt{\frac{1+w^{\star}_{i^{\star}}/w^{\star}_{j}}{1+\left(w^{\star}_{i}/w^{\star}_{i^{\star}}+\gamma\right)^{-1}}}\>.$

Let $\tilde{\gamma}>0$. Using Lemmas 12 and 18, we have, for all $n\geq N_{1}$
and all $k\neq i^{\star}$,

$\displaystyle\left|\frac{\mu_{n,i^{\star}}-\mu_{n,k}+\varepsilon_{0}}{\mu_{i^{\star}}-\mu_{k}+\varepsilon_{0}}-1\right|$
$\displaystyle\leq\frac{W_{\mu}}{\mu_{i^{\star}}-\mu_{k}+\varepsilon_{0}}\left(\sqrt{\frac{\log(e+N_{n,k})}{N_{n,k}}}+\sqrt{\frac{\log(e+N_{n,i^{\star}})}{N_{n,i^{\star}}}}\right)$
$\displaystyle\leq\frac{2W_{\mu}}{\min_{k\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{k}+\varepsilon_{0})}\sqrt{\frac{\log(e+\sqrt{n/K})}{\sqrt{n/K}}}\leq\tilde{\gamma}$

for all $n\geq N_{6}=K(X_{0}-e)^{2}+1$ which is defined as

$\displaystyle X_{0}$ $\displaystyle=\sup\left\\{x\geq
1\mid\>x<\frac{4W_{\mu}^{2}}{\tilde{\gamma}^{2}\min_{k\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{k}+\varepsilon_{0})^{2}}\log x+e\right\\}$
$\displaystyle\leq
h_{1}\left(\frac{4W_{\mu}^{2}}{\tilde{\gamma}^{2}\min_{k\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{k}+\varepsilon_{0})^{2}},e\right)\>.$

where the last inequality is obtained by using Lemma 51 with $h_{1}$ defined
therein. Since $h_{1}(x,y)\sim_{x\to+\infty}x\log x$, we have
$\mathbb{E}_{\nu}[N_{6}]<+\infty$ since it polynomial in $W_{\mu}$ (by using
Lemma 12). Let $\kappa>0$. We have shown that, for all
$n\geq\max\\{N_{1},N_{4},N_{6}\\}$,

$\displaystyle\frac{\mu_{n,i^{\star}}-\mu_{n,i}+\varepsilon_{0}}{\mu_{n,i^{\star}}-\mu_{n,j}+\varepsilon_{0}}\sqrt{\frac{1+N_{n,i^{\star}}/N_{n,j}}{1+N_{n,i^{\star}}/N_{n,i}}}$
$\displaystyle\geq\frac{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{0}}{\mu_{i^{\star}}-\mu_{j}+\varepsilon_{0}}\sqrt{\frac{1+w^{\star}_{i^{\star}}/w^{\star}_{j}}{1+\left(w^{\star}_{i}/w^{\star}_{i^{\star}}+\gamma\right)^{-1}}}\frac{1-\tilde{\gamma}}{1+\tilde{\gamma}}$
$\displaystyle=\sqrt{\frac{1+w^{\star}_{i^{\star}}/w^{\star}_{i}}{1+\left(w^{\star}_{i}/w^{\star}_{i^{\star}}+\gamma\right)^{-1}}}\frac{1-\tilde{\gamma}}{1+\tilde{\gamma}}\>.$

where the equality uses that the transportation costs are equal at the
equilibrium, i.e. (9). Taking $\tilde{\gamma}$ small enough, we have that
shown that, for all $n\geq\max\\{N_{1},N_{4},N_{6}\\}$,

$\frac{N_{n,i}}{N_{n,i^{\star}}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\quad\implies\quad\frac{\mu_{n,i^{\star}}-\mu_{n,i}+\varepsilon_{0}}{\mu_{n,i^{\star}}-\mu_{n,j}+\varepsilon_{0}}\sqrt{\frac{1+N_{n,i^{\star}}/N_{n,j}}{1+N_{n,i^{\star}}/N_{n,i}}}>1\quad\implies\quad
C_{n}^{\text{TC}\varepsilon_{0}}\neq i\>.$

This concludes the proof. ∎

Lemma 23 shows no sub-optimal arm is overshooting the ratio of its optimal
allocation for $n$ large enough.

######  Lemma 23.

Let $\gamma>0$. There exists $N_{6}$ with $\mathbb{E}_{\nu}[N_{6}]<+\infty$
such that for all $n\geq N_{6}$ and all $i\neq i^{\star}$,

$\frac{N_{n,i}}{N_{n,i^{\star}}}\leq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\>.$

###### Proof.

Let $\gamma>0$. Let $N_{1}$ as in Lemma 18. Let $N_{3}$ and $N_{5}$ as in
Lemmas 20 and 22. Let $M\geq\max\\{N_{3},N_{5},N_{1}\\}$ and $n>M$. Let
$t_{n,i}(\gamma)=\max\left\\{M,\max\left\\{t\in\\{M,\cdots,n-1\\}\mid\>\frac{N_{t,i}}{N_{t,i^{\star}}}<\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma/2\right\\}\right\\}$
for all $i\neq i^{\star}$. In particular, using Lemma 22, for all $n>M$

$\forall
t>t_{n,i}(\gamma),\quad\frac{N_{t,i}}{N_{t,i^{\star}}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma/2\quad\text{hence}\quad
i\neq C^{\text{TC}\varepsilon_{0}}_{t}\>,$

and

$N_{t_{n,i}(\gamma),i}\leq\max\left\\{M,\left(\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma/2\right)N_{t_{n,i}(\gamma),i^{\star}}\right\\}$

Then, we have for all $n\geq M$,

$\displaystyle N_{n,i}$
$\displaystyle=N_{t_{n,i}(\gamma),i}+\mathds{1}\left(i=I_{t_{n,i}(\gamma)}\right)+\sum_{t=t_{n,i}(\gamma)+1}^{n-1}\mathds{1}\left(i=I_{t}=C^{\text{TC}\varepsilon_{0}}_{t}\right)$
$\displaystyle\leq\max\left\\{M,\left(\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma/2\right)N_{t_{n,i}(\gamma),i^{\star}}\right\\}+1\>.$

Using that $N_{t_{n,i}(\gamma),i^{\star}}\leq N_{n,i^{\star}}$,
$N_{n,i^{\star}}\geq\frac{n-1}{4\sqrt{2(K-1)}}$ (Lemma 20) and
$\max\\{a,b\\}\leq a+b$, we obtain that

$\displaystyle\frac{N_{n,i}}{N_{n,i^{\star}}}$
$\displaystyle\leq\frac{4(M+1)\sqrt{2(K-1)}}{n-1}+\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma/2\leq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\>,$

where the last inequality holds for $n\geq
N_{7}=8(M+1)\sqrt{2(K-1)}/\gamma+1$. Taking
$N_{6}=\max\\{N_{3},N_{5},N_{1},N_{7}\\}$ yields the result since
$\mathbb{E}_{\nu}[N_{6}]<+\infty$. ∎

Finally, Lemma 24 shows that the sufficient condition (see Lemma 13) to obtain
the asymptotic upper bound on the expected sample complexity is satisfied.

######  Lemma 24.

Let $\varepsilon_{0}>0$, $\gamma>0$ and $T_{\varepsilon_{0},\gamma}$ as in
(10). Under the EB-TC${}_{\varepsilon_{0}}$ sampling rule with IDS
proportions, we have $\mathbb{E}_{\nu}[T_{\varepsilon_{0},\gamma}]<+\infty$.

###### Proof.

Let $\gamma>0$ and $\tilde{\gamma}$. Let $N_{4}$ and $N_{6}$ as in Lemmas 21
and 23 for $\tilde{\gamma}$. Then, using Lemmas 21 and 23, we have for all
$n\geq\max\\{N_{4},N_{6}\\}$,

$\displaystyle\left(\frac{N_{n,i}}{N_{n,i^{\star}}}\right)^{2}$
$\displaystyle\geq
1-\sum_{j\notin\\{i,i^{\star}\\}}\left(\frac{N_{n,j}}{N_{n,i^{\star}}}\right)^{2}-\tilde{\gamma}$
$\displaystyle\geq
1-\sum_{j\notin\\{i,i^{\star}\\}}\left(\frac{w^{\star}_{j}}{w^{\star}_{i^{\star}}}+\tilde{\gamma}\right)^{2}-\tilde{\gamma}$
$\displaystyle=\left(\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right)^{2}-\left((K-2)\tilde{\gamma}+2\sum_{j\notin\\{i,i^{\star}\\}}\frac{w^{\star}_{j}}{w^{\star}_{i^{\star}}}+1\right)\tilde{\gamma}$

where the equality uses (9). Therefore, we have shown that for all
$n\geq\max\\{N_{4},N_{6}\\}$,

$\displaystyle\frac{N_{n,i}}{N_{n,i^{\star}}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\sqrt{1-\left(\frac{w^{\star}_{i^{\star}}}{w^{\star}_{i}}\right)^{2}\left((K-2)\tilde{\gamma}+2\sum_{j\notin\\{i,i^{\star}\\}}\frac{w^{\star}_{j}}{w^{\star}_{i^{\star}}}+1\right)\tilde{\gamma}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}-\gamma\>,$

where the last inequality holds for $\tilde{\gamma}$ small enough as a
function of $\gamma$ and $w^{\star}$. Therefore, we obtained

$\max_{i\neq
i^{\star}}\left|\frac{N_{n,i}}{N_{n,i^{\star}}}-\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}\right|\leq\gamma\>,$

which concludes the proof, i.e. $\mathbb{E}_{\nu}[T_{\gamma}]<+\infty$. ∎

Combining Lemmas 13 and 24 concludes the first part of Theorem 1, i.e.

$\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]}{\log(1/\delta)}\leq
T_{\varepsilon_{0}}(\mu)\left(1+\max_{i\neq
i^{\star}}\frac{\varepsilon_{0}-\varepsilon_{1}}{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1}}\right)^{2}\>.$

###  D.2 Fixed proportions

Using Lemma 9, the $\beta$-optimal allocation for $\varepsilon_{0}$-BAI are
defined as

$w_{\varepsilon_{0},\beta}(\mu):=\operatorname*{arg\,max}_{w\in\triangle_{K},w_{i^{\star}}=\beta}\min_{i\neq
i^{\star}}\frac{(\mu_{i^{\star}}-\mu_{i}+\varepsilon_{0})^{2}}{1/\beta+1/w_{i}}\>.$

Since $|i^{\star}(\mu)|=1$, let
$\mu_{\varepsilon_{0}}=\mu_{\varepsilon_{0}}(i^{\star})$ where
$\mu_{\varepsilon}(i^{\star})$ as in Lemma 9. Since we have
$T_{\varepsilon_{0},\beta}(\mu)=T^{\star}_{\beta}(\mu_{\varepsilon_{0}})$ and
$w_{\varepsilon_{0},\beta}(\mu)=w^{\star}_{\beta}(\mu_{\varepsilon_{0}})$,
Lemma 6 and 8 yield that
$w_{\varepsilon_{0},\beta}(\mu)=\\{w^{\star}_{\beta}\\}$ is a singleton with
unique element denotes by $w^{\star}_{\beta}$ which satisfies that
$\min_{i\in[K]}w^{\star}_{\beta,i}>0$ and

$\forall
i\in[K]\setminus\\{i^{\star}\\},\quad\frac{(\mu_{i^{\star}}-\mu_{i}+\varepsilon_{0})^{2}}{1/\beta+1/w^{\star}_{\beta,i}}=2T_{\varepsilon_{0},\beta}(\mu)^{-1}\>.$
(13)

When considering fixed proportions $\beta$, the proof strategy is the same as
in Appendix D.1. The sole difference lies in the fact that the empirical
allocation of the unique best arm is converging towards a fixed $\beta$.

##### Convergence time

Let $\gamma>0$. Let us define the _convergence time_
$T_{\varepsilon_{0},\beta,\gamma}$, which is a random variable quantifies the
number of samples required for the empirical allocations $N_{n}$ to be
$\gamma$-close to $w^{\star}_{\beta}$:

$T_{\varepsilon_{0},\beta,\gamma}:=\inf\left\\{T\geq 1\mid\forall n\geq
T,\>\left\|\frac{N_{n}}{n-1}-w^{\star}_{\beta}\right\|_{\infty}\leq\gamma\right\\}\>.$
(14)

Lemma 25 gives a sufficient condition for asymptotic $\beta$-optimality. The
case $\varepsilon_{0}=\varepsilon_{1}$ is a direct consequence of existing
methods, e.g. Theorem 2 in [21] or Theorem 3 in [32].

######  Lemma 25.

Let $\varepsilon_{0}>0$, $\varepsilon_{1}\geq 0$ and $\delta\in(0,1)$. Assume
that there exists $\gamma_{1}(\mu)>0$ such that for all
$\gamma\in(0,\gamma_{1}(\mu)]$,
$\mathbb{E}_{\nu}[T_{\varepsilon_{0},\beta,\gamma}]<+\infty$. Using the
threshold (4) in the stopping rule (3) with slack $\varepsilon_{1}$ yields an
algorithm such that, for all $\nu\in\mathcal{D}^{K}$ such that
$|i^{\star}(\mu)|=1$,

$\limsup_{\delta\to
0}\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]}{\log\left(1/\delta\right)}\leq
T_{\varepsilon_{0},\beta}(\mu)\left(1+\max_{i\neq
i^{\star}}\frac{\varepsilon_{0}-\varepsilon_{1}}{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1}}\right)^{2}\>.$

###### Proof.

The proof is the same of the ones of Lemma 13. The sole difference is that we
have $w^{\star}_{\beta,i^{\star}}=\beta$ by definition. ∎

##### Sufficient exploration

Lemma 26 shows that all arms are sufficiently explored and that the leader is
the unique best arm for $n$ large enough.

######  Lemma 26.

There exist $N_{1}$ with $\mathbb{E}_{\nu}[N_{1}]<+\infty$ such that for all
$n\geq N_{1}$ and all $i\in[K]$, $N_{n,i}\geq\sqrt{n/K}$ and
$B_{n}^{\text{EB}}=i^{\star}$.

###### Proof.

Since Lemmas 16 and 17 holds, we can use the intermediate results of Lemma 18.
It is direct to see that the proof can be conducted similarly by noting that,
for all $i\neq j$,

$\min\\{\beta_{t}(i,j),1-\beta_{t}(i,j)\\}=\min\\{\beta,1-\beta\\}>0\>.$

∎

##### Convergence towards optimal allocation

Combining Lemma 26 with the proof of Lemma F.8 in [20] yields Lemma 27.

######  Lemma 27.

Let $\gamma>0$. There exists $N_{2}$ with $\mathbb{E}_{\mu}[N_{2}]<+\infty$
such that for all $n\geq N_{2}$,

$\left|\frac{N_{n,i^{\star}}}{n-1}-\beta\right|\leq\gamma\>.$

Combining Lemmas 26 and 27 with the proof of Lemma F.9 in [20] yields Lemma
28.

######  Lemma 28.

Let $\gamma>0$. There exists $N_{5}$ with $\mathbb{E}_{\nu}[N_{5}]<+\infty$
such that for all $n\geq N_{5}$ and all $i\neq i^{\star}$,

$\frac{N_{n,i}}{n-1}\geq w^{\star}_{\beta,i}+\gamma\quad\implies\quad
C_{n}^{\text{TC}\varepsilon_{0}}\neq i\>.$

Combining Lemmas 27 and 28 with the proof of Lemma F.10 in [20] yields Lemma
29.

######  Lemma 29.

Let $\gamma>0$. There exists $N_{6}$ with $\mathbb{E}_{\nu}[N_{6}]<+\infty$
such that for all $n\geq N_{6}$,

$\left\|\frac{N_{n}}{n-1}-w^{\star}_{\beta}\right\|_{\infty}\leq\gamma\>.$

Lemma 30 is a direct corollary of Lemma 29.

######  Lemma 30.

Let $\varepsilon_{0}>0$, $\beta\in(0,1)$, $\gamma>0$ and
$T_{\varepsilon_{0},\beta,\gamma}$ as in (14). Under the EB-
TC${}_{\varepsilon_{0}}$ sampling rule with fixed proportions $\beta$, we have
$\mathbb{E}_{\nu}[T_{\varepsilon_{0},\beta,\gamma}]<+\infty$.

Combining Lemmas 25 and 30 concludes the second part of Theorem 1, i.e.

$\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]}{\log(1/\delta)}\leq
T_{\varepsilon_{0},\beta}(\mu)\left(1+\max_{i\neq
i^{\star}}\frac{\varepsilon_{0}-\varepsilon_{1}}{\mu_{i^{\star}}-\mu_{i}+\varepsilon_{1}}\right)^{2}\>.$

##  Appendix E Non-asymptotic analysis

Let $\varepsilon_{0}>0$, $\beta\in(0,1)$ and $\delta\in(0,1)$. In this
section, we provide a non-asymptotic analysis of EB-TC${}_{\varepsilon_{0}}$
with fixed proportions $\beta$ and slack $\varepsilon_{0}>0$ when combined
with the stopping rule (3) with parameters $(\varepsilon_{0},\delta)$. In
practice, we will mostly be interested in the case $\beta=1/2$. First, we
prove Lemma 5 in Appendix E.1. Then, we detail the proof of Theorem 2 in
Appendix E.2.

In the following, we consider a sub-Gaussian bandit with distribution
$\nu\in\mathcal{D}^{K}$ having mean parameter $\mu\in\mathbb{R}^{K}$. In
particular, our analysis holds when several arms have the largest mean
$\mu_{\star}$.

###  E.1 Proof of Lemma 5

Let $s\geq 0$. For all $n>K$ and $\delta\in(0,1]$, let
$\mathcal{E}_{n,\delta}=\mathcal{E}^{1}_{n,\delta}\cap\mathcal{E}^{2}_{n,\delta}$
with $(\mathcal{E}^{1}_{n,\delta})_{n>K}$ and
$(\mathcal{E}^{2}_{n,\delta})_{n>K}$ as in (24) and (25), i.e.

$\displaystyle\mathcal{E}^{1}_{n,\delta}$ $\displaystyle=\left\\{\forall
k\in[K],\forall t\leq
n,\>|\mu_{t,k}-\mu_{k}|<\sqrt{\frac{2f_{1}(n,\delta)}{N_{t,k}}}\right\\}\>,$
$\displaystyle\mathcal{E}^{2}_{n,\delta}$
$\displaystyle=\left\\{\forall(i,k)\in[K]^{2}\>\text{s.t.}\>i\neq k,\>\forall
t\leq
n,\>\frac{\left|(\mu_{t,i}-\mu_{t,k})-(\mu_{i}-\mu_{k})\right|}{\sqrt{1/N_{t,i}+1/N_{t,k}}}<\sqrt{2f_{2}(n,\delta)}\right\\}\>,$

where $f_{2}(x,\delta)=\log(1/\delta)+(1+s)\log(x)$ and
$f_{2}(x,\delta)=\log(1/\delta)+(2+s)\log(x)$.

Lemma 31 shows that when there are arms with strictly higher true mean than
the one of the leader, then at least one of those arms is undersampled.

######  Lemma 31.

Under $\mathcal{E}^{1}_{n,\delta}$, for all $t\in[n]\setminus[K]$ let
$B^{\text{EB}}_{t}=k$. Then,

$\forall i\neq
k,\quad\mathds{1}\left(\mu_{i}>\mu_{k}\right)\min\\{N_{t,k},N_{t,i}\\}\leq\frac{8f_{1}(n,\delta)}{(\mu_{i}-\mu_{k})^{2}}\>.$

###### Proof.

Under $\mathcal{E}^{1}_{n,\delta}$, for all $t\in[n]\setminus[K]$, let