# Non-Asymptotic Analysis of a UCB-based Top Two Algorithm

Marc Jourdan  Rémy Degenne

###### Abstract

A Top Two sampling rule for bandit identification is a method which selects
the next arm to sample from among two candidate arms, a leader and a
challenger. Due to their simplicity and good empirical performance, they have
received increased attention in recent years. However, for fixed-confidence
best arm identification, theoretical guarantees for Top Two methods have only
been obtained in the asymptotic regime, when the error level vanishes. In this
paper, we derive the first non-asymptotic upper bound on the expected sample
complexity of a Top Two algorithm, which holds for any error level. Our
analysis highlights sufficient properties for a regret minimization algorithm
to be used as leader. These properties are satisfied by the UCB algorithm, and
our proposed UCB-based Top Two algorithm simultaneously enjoys non-asymptotic
guarantees and competitive empirical performance.

Multi-armed bandits, Best-arm identification, Gaussian bandits, Top Two
algorithm, Fixed confidence, Non-asymptotic

##  1 Introduction

Faced with a collection of items (“arms”) with unknown probability
distributions, a question that arises in many applications is to find the
distribution with the largest mean, which is referred to as the best arm.
Different approaches have been considered depending on the data collection
process. Sequential hypothesis testing (Chernoff, 1959; Robbins, 1952)
encompasses situations where there is no control on the collected samples.
Experimental design (Chaloner & Verdinelli, 1995; Pukelsheim, 2006) aims at
choosing the data collection scheme a priori. In the multi-armed bandit
(Audibert et al., 2010; Jamieson & Nowak, 2014) and the ranking and selection
(Hong et al., 2021) literature, an algorithm chooses sequentially the
distribution from which it will collect an additional sample based on past
data.

In order to have theoretical guarantees for this identification problem, one
should adopt a statistical model on the underlying distributions. While
parametric models are reasonable for applications such as A/B testing
(Kaufmann et al., 2014), they are unrealistic in other fields such as
agriculture (Jourdan et al., 2022). Despite the restricted scope of its
applications, studying the identification task for Gaussian distributions is a
natural first step. Hopefully the insights gained will then be generalized to
wider classes of distributions.

In the fixed confidence identification problem, an algorithm aims at
identifying the best arm with an error of at most $\delta\in(0,1)$ while using
as few samples as possible. Since each sample has a cost, those algorithms
should provide an upper bound on the expected number of samples used by the
algorithm before stopping. For those guarantees to be useful in practice, they
should hold for any $\delta$, which is referred to as the non-asymptotic (or
moderate) regime. In contrast, the asymptotic regime considers vanishing error
level, i.e. $\delta\to 0$. For Gaussian distributions, Top Two algorithms (Qin
et al., 2017; Shang et al., 2020) have only been studied in the asymptotic
regime. We show the first non-asymptotic guaranty for a Top Two algorithm
holding for any instance with a unique best arm.

###  1.1 Setting and Related Work

A Gaussian bandit problem is described by $K$ arms whose probability
distributions belongs to the set $\mathcal{D}$ of Gaussian distributions with
known variance $\sigma^{2}$. By rescaling, we assume $\sigma_{i}^{2}=1$ for
all $i\in[K]$. Since an element of $\mathcal{D}$ is uniquely characterized by
its mean, the vector $\mu\in\mathbb{R}^{K}$ refers to a $K$-arms Gaussian
bandit. Let $\triangle_{K}\subseteq\mathbb{R}^{K}$ be the $(K-1)$-dimensional
simplex.

A best arm identification (BAI) algorithm aims at identifying an arm with
highest mean parameter, i.e. an arm belonging to the set
$i^{\star}(\mu)=\operatorname*{arg\,max}_{i\in[K]}\mu_{i}$. At each time
$n\in\mathbb{N}$, the algorithm (1) chooses an arm $I_{n}$ based on previous
observations, (2) observes a sample
$X_{n,I_{n}}\sim\mathcal{N}(\mu_{I_{n}},1)$, and (3) decides whether it should
stop and return an arm $\hat{\imath}_{n}$ or continue sampling. We consider
the _fixed confidence_ identification setting, in which the probability of
error of an algorithm is required to be less than a given $\delta\in(0,1)$ on
all instances $\mu$. The _sample complexity_ of an algorithm corresponds to
its stopping time $\tau_{\delta}$, which counts the number of rounds before
termination. An algorithm is said to be $\delta$-correct on $\mathcal{D}^{K}$
if
$\mathbb{P}_{\mu}\left(\tau_{\delta}<+\infty,\>\hat{\imath}_{\tau_{\delta}}\notin
i^{\star}(\mu)\right)\leq\delta$ for all $\mu\in\mathcal{D}^{K}$ (Even-Dar et
al., 2002). We aim at designing $\delta$-correct algorithms minimizing
$\mathbb{E}[\tau_{\delta}]$.

As done in all the literature on fixed-confidence BAI, we assume that there is
a unique best arm and we denote it by $i^{\star}(\mu)$ or $i^{\star}$ when
$\mu$ is clear from the context. To ensure $\delta$-correctness on
$\mathcal{D}^{K}$, an algorithm has to be able to distinguish the unknown
$\mu$ from any instance having a different best arm, hence it needs to
estimates the gaps between arms. Lemma 1.1 gives a lower bound on the expected
sample complexity which is known to be tight in the asymptotic regime, i.e.
when $\delta$ goes to zero.

######  Lemma 1.1 (Garivier & Kaufmann (2016)).

An algorithm which is $\delta$-correct on all problems in $\mathcal{D}^{K}$
satisfies that for all $\mu\in\mathbb{R}^{K}$,
$\mathbb{E}_{\mu}[\tau_{\delta}]\geq T^{\star}(\mu)\log(1/(2.4\delta))$ where
$T^{\star}(\mu)=\min_{\beta\in(0,1)}T^{\star}_{\beta}(\mu)$ and, for all
$\beta\in(0,1)$,

$T^{\star}_{\beta}(\mu)^{-1}:=\max_{w\in\triangle_{K}:w_{i^{\star}(\mu)}=\beta}\min_{i\neq
i^{\star}(\mu)}\frac{(\mu_{i^{\star}(\mu)}-\mu_{i})^{2}}{2\left(1/\beta+1/w_{i}\right)}\>.$

When considering the sub-class of algorithms allocating a fraction $\beta$ of
their sample to the best arm, we obtain a lower bound as in Lemma 1.1 with
$T^{\star}_{\beta}(\mu)$ instead of $T^{\star}(\mu)$. An algorithm is said to
be asymptotically optimal (resp. $\beta$-optimal) if its sample complexity
matches that lower bound asymptotically, that is if $\limsup_{\delta\to
0}\mathbb{E}_{\mu}[\tau_{\delta}]/\log(1/\delta)\leq T^{\star}(\mu)$ (resp.
$T^{\star}_{\beta}(\mu)$). Russo (2016) showed the worst-case inequality
$T_{1/2}^{\star}(\mu)\leq 2T^{\star}(\mu)$ for any single-parameter
exponential families (Lemma C.1). Therefore, the expected sample complexity of
an asymptotically $\beta$-optimal algorithm with $\beta=1/2$ is at worst twice
higher than that of any asymptotically optimal algorithm. Leveraging the
symmetry of Gaussian distributions, a tighter worst-case inequality can be
derived (Lemma C.6). The allocations $w^{\star}(\mu)$ and
$w^{\star}_{\beta}(\mu)$ realizing $T^{\star}(\mu)$ and
$T^{\star}_{\beta}(\mu)$ are known to be unique, and satisfy
$\min_{i\in[K]}\min\\{w^{\star}(\mu)_{i},w^{\star}_{\beta}(\mu)_{i}\\}>0$
(Lemma C.2). Barrier et al. (2022) showed that $2\leq
w^{\star}(\mu)_{i^{\star}}^{-1}\leq\sqrt{K-1}+1$ for Gaussian distributions
(Lemma C.4).

##### Related Work

The first BAI algorithms were introduced and studied under the assumption that
the observation have bounded support, with a known upper bound (Even-Dar et
al., 2006; Kalyanakrishnan et al., 2012; Gabillon et al., 2012; Jamieson et
al., 2014). The sample complexity bounds proved for these algorithms scale as
the sum of squared inverse gap, i.e. $H(\mu):=\sum_{i\neq
i^{\star}(\mu)}2(\mu_{i^{\star}(\mu)}-\mu_{i})^{-2}$, which satisfies
$H(\mu)\leq T^{\star}(\mu)\leq 2H(\mu)$ (Garivier & Kaufmann, 2016). Following
their work, a rich literature designed asymptotically optimal algorithms in
the fixed-confidence setting for parametric distributions, such as single-
parameter exponential families, and non-parametric distributions such as
bounded ones. Those algorithms build on two main ideas. The Tracking approach
computes at each round the optimal allocation for the empirical estimator, and
then tracks it (Garivier & Kaufmann, 2016). To achieve lower computational
cost, Game-based algorithms (Degenne et al., 2019) view $T^{\star}(\mu)^{-1}$
as a min-max game between the learner and the nature, and design saddle-point
algorithms to solve it sequentially.

Top Two algorithms arose as an identification strategy based on the praised
Thompson Sampling algorithm for regret minimization (Thompson, 1933): Russo
(2016) introduced Top Two Probability Sampling (TTPS) and Top Two Thompson
Sampling (TTTS). Adopting a Bayesian viewpoint, Russo studied the convergence
rate of the posterior probability that $i^{\star}$ is not the best arm, under
some conditions on the prior. For Gaussian bandits, other Bayesian Top Two
algorithms with frequentist components have been shown to be asymptotically
$\beta$-optimal: Top Two Expected Improvement (TTEI, (Qin et al., 2017)) and
Top Two Transportation Cost (T3C, Shang et al. (2020)). Jourdan et al. (2022)
introduces fully frequentist Top Two algorithms. Their analysis proves
asymptotic $\beta$-optimality for several Top Two algorithms and distribution
classes, beyond Gaussian. Mukherjee & Tajer (2022) provides guarantees for
single-parameter exponential families, at the price of adding forced
exploration. Wang et al. (2022) proposes a heuristic to tackle the top-$k$
identification problem and choose $\beta$ in an adaptive manner. In addition
to their success in the fixed-confidence setting, Top Two algorithms have also
been studied for fixed-budget problems (Ariu et al., 2021), in which
guarantees on the error probability should be given after $T$ samples. While
existing Top Two sampling rules differ by how they choose the leader and the
challenger, they all sample the leader with probability $\beta$. By design,
Top Two algorithms with a fixed $\beta$ can reach $\beta$-optimality at best,
and cannot be optimal on all instances $\mu$.

##### Shortcomings of the Asymptotic Regime

While the literature provides a detailed understanding of the asymptotic
regime, many interesting questions are unanswered in the non-asymptotic
regime. Recent works (Chen et al., 2017b; Simchowitz et al., 2017; Mason et
al., 2020; Marjani et al., 2022) have shown that the sample complexity is
affected by strong moderate confidence terms (independent of $\delta$).
Strikingly, the analysis of Jourdan et al. (2022) applies to the $\beta$-EB-TC
algorithm whose empirical stopping times can be several order of magnitude
larger than other Top Two algorithms for $\delta=0.01$. Since the proof of
asymptotic $\beta$-optimality hides design flaws, non-asymptotic guarantees
should be derived to understand which Top Two algorithms will perform well in
practice for any reasonable choice of $\delta$.

###  1.2 Contributions

Our main contribution is to propose the first non-asymptotic analysis of Top
Two algorithms. In particular, we identify sufficient properties of the leader
(seen as a regret-minimization algorithm) for it to hold. This solves two open
problems: obtaining an upper bound which (1) is non-asymptotic (Theorem 2.4
holds for any $\delta$) and (2) holds for all instances having a unique best
arm (i.e. sub-optimal arms can have the same mean, which was not allowed in
the analyzes of previous work on Top Two algorithms). As a consequence, we
propose the TTUCB (Top Two UCB) algorithm which builds on the UCB algorithm.

By using tracking instead of sampling to choose between the leader and the
challenger, TTUCB is the first Top Two algorithm which is asymptotically
$\beta$-optimal (Theorem 2.3) and has non-asymptotic guarantees (Theorem 2.4).
Our experiments reveal that TTUCB performs on par with existing Top Two
algorithms, which are only proven to be asymptotically $\beta$-optimal, even
for large sets of arms. Numerically, we show that considering adaptive
proportions compared to a fixed $\beta=1/2$ yields a significant speed-up on
hard instances, and to a moderate improvement on random instances.

##  2 UCB-Based Top Two Algorithm

We propose a fully deterministic Top Two algorithm based on UCB (Auer et al.,
2002), named TTUCB and detailed in Algorithm 1. We prove a non-asymptotic
upper bound on the expected sample complexity holding for any instance having
a unique best arm.

##### Stopping and Recommendation Rules

The $\sigma$-algebra
$\mathcal{F}_{n}:=\sigma(\\{I_{t},X_{t,I_{t}}\\}_{t\in[n-1]})$, called
history, encompasses all the information available to the agent before time
$n$. Let us denote by
$N_{n,i}:=\sum_{t\in[n-1]}\mathds{1}\left(I_{t}=i\right)$ the number of pulls
of arm $i$ before time $n$, and its empirical mean by
$\mu_{n,i}:=\frac{1}{N_{n,i}}\sum_{t\in[n-1]}X_{t,I_{t}}\mathds{1}\left(I_{t}=i\right)$.

The algorithm stops as soon as the generalized likelihood ratio exceeds a
stopping threshold $c(n-1,\delta)$, i.e.

$\min_{i\neq\hat{\imath}_{n}}\frac{\mu_{n,\hat{\imath}_{n}}-\mu_{n,i}}{\sqrt{1/N_{n,\hat{\imath}_{n}}+1/N_{n,i}}}\geq\sqrt{2c(n-1,\delta)}\>,$
(1)

where we recommend
$\hat{\imath}_{n}=\operatorname*{arg\,max}_{i\in[K]}\mu_{n,i}$ at time $n$.
Lemma 2.1 provides an explicit threshold ensuring $\delta$-correctness, which
relies on concentration inequalities derived in Kaufmann & Koolen (2021).

######  Lemma 2.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))$ (2)

with the stopping rule (1) ensures $\delta$-correct for Gaussian
distributions. Defined in (17), we have $\mathcal{C}_{G}(x)\approx x+\log(x)$.

Algorithm 1 TTUCB

Input: $(\beta,\delta)\in(0,1)^{2}$, threshold
$c:\mathbb{N}\times(0,1)\to\mathbb{R}^{+}$ and function
$g:\mathbb{N}\to\mathbb{R}^{+}$.

Pull once each arm $i\in[K]$;

for $n>K$ do

Set $\hat{\imath}_{n}=\operatorname*{arg\,max}_{i\in[K]}\mu_{n,i}$;

if
$\min_{i\neq\hat{\imath}_{n}}\frac{\mu_{n,\hat{\imath}_{n}}-\mu_{n,i}}{\sqrt{1/N_{n,\hat{\imath}_{n}}+1/N_{n,i}}}\geq\sqrt{2c(n-1,\delta)}$
then

return $\hat{\imath}_{n}$;

end if

Set
$B^{\text{UCB}}_{n}=\operatorname*{arg\,max}_{i\in[K]}\left\\{\mu_{n,i}+\sqrt{g(n)/N_{n,i}}\right\\}$;

Set $C^{\text{TC}}_{n}=\operatorname*{arg\,min}_{i\neq
B^{\text{UCB}}_{n}}\frac{(\mu_{n,B^{\text{UCB}}_{n}}-\mu_{n,i})_{+}}{\sqrt{1/N_{n,B^{\text{UCB}}_{n}}+1/N_{n,i}}}$;

Pull $I_{n}=\begin{cases}B^{\text{UCB}}_{n}&\text{if
}N_{n,B^{\text{UCB}}_{n}}^{B^{\text{UCB}}_{n}}\leq\beta
L_{n+1,B^{\text{UCB}}_{n}}\\\ C^{\text{TC}}_{n}&\text{else.}\end{cases}$;

Observe $X_{n,I_{n}}$ and update the counters and $\mu_{n}$;

end for

##### Sampling Rule

We initialize by sampling each arms 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}$, and
chooses $I_{n}=B_{n}$ or $I_{n}=C_{n}$ based on a fixed allocation $\beta$. In
prior work this choice was done at random, which means that the leader was
sampled with probability $\beta$. We replace randomization by tracking, and
show similar theoretical and numerical results (see Figure 6 in Appendix G.2).
Using tracking simplifies the non-asymptotic analysis. We use $\beta=1/2$
since $w^{\star}(\mu)_{i^{\star}}\leq 1/2$ (Lemma C.4) and
$T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$ is small (Lemma C.6 and Figure 4).

Let $L_{n,i}:=\sum_{t\in[n-1]}\mathds{1}\left(B_{t}=i\right)$ be the number of
time arm $i$ was the leader, and
$N^{i}_{n,j}:=\sum_{t\in[n-1]}\mathds{1}\left((B_{t},I_{t})=(i,j)\right)$ be
the number of pulls of arm $j$ at rounds in which $i$ was the leader. We use
$K$ independent tracking procedures. A tracking procedure is a deterministic
method to convert a sequence of allocations over arms into a sequence of arms,
which ensures that the empirical proportions are close to the averaged
allocation over arms. For each leader, we track the allocation
$(\beta,1-\beta)$ between the leader and the challenger. Formally, we set
$I_{n}=B_{n}$ if $N_{n,B_{n}}^{B_{n}}\leq\beta L_{n+1,B_{n}}$, else
$I_{n}=C_{n}$. Using Theorem 6 in (Degenne et al., 2020) for each tracking
procedure between two arms yields Lemma 2.2.

######  Lemma 2.2.

$\forall n>K$, $\forall i\in[K]$, $-\frac{1}{2}\leq N_{n,i}^{i}-\beta
L_{n,i}\leq 1$.

At time $n$, the UCB leader is defined as

$B^{\text{UCB}}_{n}=\operatorname*{arg\,max}_{i\in[K]}\left\\{\mu_{n,i}+\sqrt{g(n)/N_{n,i}}\right\\}\>,$
(3)

where $\sqrt{g(n)/N_{n,i}}$ is a bonus coping for uncertainty. To ensure we
have an upper confidence bound on $\mu_{i}$ holding with high probability, the
bonus is calibrated by concentration. Let $\alpha>1$ and $s>1$ be two
concentration parameters. For Gaussian observations, a function $g$ which is
sufficient for the purpose of our proof can be obtained by a union bound over
time, giving $g_{u}(n)=2\alpha(1+s)\log n$. We can improve on $g_{u}$ with
mixtures of martingales, yielding

$g_{m}(n)=\overline{W}_{-1}\left(2s\alpha\log(n)+2\log(2+\alpha\log
n)+2\right)\>,$

with $\overline{W}_{-1}(x)=-W_{-1}(-e^{-x})$ for all $x\geq 1$, where $W_{-1}$
is the negative branch of the Lambert $W$ function, and
$\overline{W}_{-1}(x)\approx x+\log(x)$. A UCB leader with $g_{0}(n)=0$
recovers the Empirical Best (EB) leader (Jourdan et al., 2022). Choosing $g$
is central for empirical performance and non-asymptotic guarantees, but not
for asymptotic ones. In our experiments, we will consider $g_{m}$ with
$\alpha=s=1.2$.

Given a leader $B_{n}$, the TC challenger is defined as

$C^{\text{TC}}_{n}=\operatorname*{arg\,min}_{i\neq
B_{n}}\frac{(\mu_{n,B_{n}}-\mu_{n,i})_{+}}{\sqrt{1/N_{n,B_{n}}+1/N_{n,i}}}\>,$
(4)

where $x_{+}=\max\\{x,0\\}$. Shang et al. (2020) introduced the TC challenger
as a computationally efficient approximation of the challenger in TTTS (Russo,
2016), which uses re-sampling till an unlikely event occurs. Both T3C and TTTS
use the TS leader which takes the best arm of a vector of realization drawn
from a sampler, e.g. $\theta_{i}\sim\mathcal{N}(\mu_{n,i},1/N_{n,i})$ for
Gaussian distributions with unit variance.

##### Computational Cost

Computing the stopping rule (1) and the UCB leader (3) can be done in
$\mathcal{O}(K)$. At time $n$ where $B_{n}$ coincides with $\hat{\imath}_{n}$,
computing the TC challenger (4) is done as a by-product of the computation of
the stopping rule, without additional cost. When $B_{n}\neq\hat{\imath}_{n}$,
we draw at random an arm in $\\{i\neq B_{n}\mid\mu_{n,i}\geq\mu_{n,B_{n}}\\}$,
which often only contains $\hat{\imath}_{n}$. Therefore, the per-round
computational and memory cost of TTUCB is in $\mathcal{O}(K)$.

###  2.1 Sample Complexity Upper Bound

Leveraging the unified analysis of Top Two algorithms proposed by Jourdan et
al. (2022), we obtain the asymptotic $\beta$-optimality of TTUCB (Theorem
2.3). After showing the required properties for the UCB leader, we proved that
tracking Top Two algorithms can be analyzed in the same way as their sampling-
based counterparts.

######  Theorem 2.3.

Let $(\delta,\beta)\in(0,1)^{2}$, $s>1$ and $\alpha>1$. Using the threshold
(2) in (1) and $g_{u}$ (or $g_{m}$) in (3), the TTUCB algorithm is
$\delta$-correct and asymptotically $\beta$-optimal for all
$\mu\in\mathbb{R}^{K}$ such that $\min_{i\neq j}|\mu_{i}-\mu_{j}|>0$, i.e. it
satisfies

$\limsup_{\delta\to 0}\>\mathbb{E}_{\mu}[\tau_{\delta}]/\log(1/\delta)\leq
T_{\beta}^{\star}(\mu)\>.$

Theorem 2.3 and guarantees for other Top Two algorithms hold only for arms
having distinct means. Moreover, an asymptotic result provides no guarantees
on the performance in moderate regime of $\delta$. We address those two
limitations.

##### Non-Asymptotic Upper Bound

Theorem 2.4 gives an upper bound on the expected sample complexity holding for
any $\delta$ and any instance having a unique best arm. It is a direct
corollary of a more general result holding for any $\beta\in(0,1)$, $s>1$ and
$\alpha>1$ (Theorem D.4).

######  Theorem 2.4.

Let $\delta\in(0,1)$. Using the threshold (2) in (1) and $g_{u}$ in (3) with
$s=\alpha=1.2$, the TTUCB algorithm with $\beta=1/2$ satisfies that, for all
$\mu\in\mathbb{R}^{K}$ such that $|i^{\star}(\mu)|=1$,

$\mathbb{E}_{\mu}[\tau_{\delta}]\leq\max\left\\{T_{0}(\delta),C_{\mu}^{1.2},C_{0}^{6},(2/\varepsilon)^{1.2}\right\\}+12K\>,$

where $C_{\mu}=h_{1}\left(26H(\mu)\right)$, $C_{0}=2/(\varepsilon
a_{\mu}(w_{0}))+1$,

$\displaystyle T_{0}(\delta)$ $\displaystyle=\sup\\{n>K\mid
n-1\leq\frac{2T_{1/2}^{\star}(\mu)(1+\varepsilon)^{2}}{(1-w_{0})^{d_{\mu}(w_{0})}}$
$\displaystyle\qquad(\sqrt{c(n-1,\delta)}+\sqrt{4\log n})^{2}\\}\>,$
$\displaystyle a_{\mu}(w_{0})$
$\displaystyle=(1-w_{0})^{d_{\mu}(w_{0})}\max\\{\min_{i\neq
i^{\star}(\mu)}w_{1/2}^{\star}(\mu)_{i},w_{0}/2\\}\>,$ $\displaystyle
d_{\mu}(w_{0})$
$\displaystyle=|\\{i\in[K]\setminus\\{i^{\star}(\mu)\\}\mid\>w_{1/2}^{\star}(\mu)_{i}<w_{0}/2\\}|\>,$

with $\varepsilon\in(0,1]$ and $w_{0}\in[0,(K-1)^{-1}]$. The function
$h_{1}(x):=x\overline{W}_{-1}\left(\log(x)+\frac{2+2K}{x}\right)$ is positive,
increasing for $x\geq 2+2K$, and satisfies $h_{1}(x)\approx x(\log x+\log\log
x)$.

The TTUCB sampling rule using $g_{m}$ in (3) (instead of $g_{u}$) satisfies a
similar non-asymptotic upper bound (see Corollary D.5 in Appendix D.3).

The upper bound on $\mathbb{E}_{\mu}[\tau_{\delta}]$ involves several terms.
The $\delta$-dependent term is $T_{0}(\delta)$. In the asymptotic regime, we
can show that $\limsup_{\delta\to 0}T_{0}(\delta)/\log(1/\delta)\leq
2T_{1/2}^{\star}(\mu)$ by taking $w_{0}=0$ and letting $\varepsilon$ go to
zero. While there is (sub-optimal) factor $2$ in $T_{0}(\delta)$, Theorem 2.3
shows that TTUCB is asymptotically $1/2$-optimal. This factor is a price we
paid to obtain more explicit non-asymptotic terms, and removing it would
require more sophisticated arguments in order to control the convergence of
the empirical proportions $N_{n}/(n-1)$ towards $w_{1/2}^{\star}(\mu)$.

In the regime where $H(\mu)\to+\infty$, the upper bound is dominated by the
$\delta$-independent term $C_{\mu}^{1.2}$ (when $\alpha=1.2$) with satisfies
$C_{\mu}=\mathcal{O}(H(\mu)\log H(\mu))$. Compared to the best known upper and
lower bounds in this regime (see discussion below), our non-asymptotic term
has a sub-optimal scaling in $\mathcal{O}((H(\mu)\log H(\mu))^{\alpha})$ with
$\alpha>1$. While taking $\alpha\approx 1$ would mitigate this sub-optimality,
it would yield a larger dependency in $C_{0}^{\alpha/(\alpha-1)}$.

Since Theorem 2.4 holds for any instance having a unique best arm, our result
corroborates the intuition that assuming $\min_{i\neq j}|\mu_{i}-\mu_{j}|>0$
is an artifact of the existing proof to obtain asymptotic $\beta$-optimality
(Theorem 2.3).

For instances such that $\min_{i\neq i^{\star}}w_{1/2}^{\star}(\mu)_{i}$ is
arbitrarily small, taking $w_{0}=0$ yields an arbitrarily large $C_{0}$. By
clipping with $w_{0}/2$, we circumvent this pitfall and ensure that
$C_{0}=\mathcal{O}(K/\varepsilon)$. Since it yields a larger $T_{0}(\delta)$,
we are trading-off asymptotic terms for improved non-asymptotic ones. We
illustrate this with two archetypal instances. For the “$1$-sparse” instance,
in which $\mu_{1}>0$ and $\mu_{i}=0$ for all $i\neq 1$, we have by symmetry
that $2w_{1/2}^{\star}(\mu)_{i}=1/(K-1)$ for all $i\neq 1$. Therefore, we have
$C_{0}=\mathcal{O}(K/\varepsilon)$ since $d_{\mu}(w_{0})=0$ for all
$w_{0}\in[0,1/(K-1)]$. The “almost dense” instance is such that $\mu_{1}=1$,
$\mu_{K}=0$ and $\mu_{i}=1-\gamma$ for all $i\notin\\{1,K\\}$. By symmetry,
there exists a function $h:[0,1)\to[0,(K-1)^{-1})$ with $\lim_{\gamma\to
0}h(\gamma)=0$, such that $2w_{1/2}^{\star}(\mu)_{K}=h(\gamma)$ and
$2w_{1/2}^{\star}(\mu)_{i}=(1-h(\gamma))/(K-2)$ for all $i\notin\\{1,K\\}$.
While $\lim_{\gamma\to 0}C_{0}=+\infty$ for $w_{0}=0$, we obtain
$\lim_{\gamma\to 0}C_{0}=\mathcal{O}(K/\varepsilon)$ by taking
$w_{0}=(1-h(\gamma))/(K-2)$ since $d_{\mu}(w_{0})=1$.

Table 1: Upper bound on the sample complexity $\tau_{\delta}$ in probability ($\mathsection$) or in expectation ($\dagger$). The notation $\mathcal{O}$ displays the dominating term when $\delta\to 0$ for the asymptotic regime, and when $H(\mu)\to+\infty$ (or $\Delta_{i}\to 0$) for the non-asymptotic one. The notation $\tilde{\mathcal{O}}$ hides polylogarithmic factors. (*) Upper bound on $\mathbb{E}_{\mu}[\tau_{\delta}\mathds{1}\left(\mathcal{E}\right)]$ where $\mathbb{P}[\mathcal{E}^{\complement}]\leq\gamma$. (**) The asymptotic upper bound holds for instances having all distinct means (Theorem 2.3), while the non-asymptotic one doesn’t require this assumption (Theorem 2.4). Algorithm | Asymptotic behavior | Non-asymptotic behavior
---|---|---
LUCB1$\dagger$ (Kalyanakrishnan et al., 2012) | $\mathcal{O}\left(H(\mu)\log(1/\delta)\right)$ | $\mathcal{O}\left(H(\mu)\log H(\mu)\right)$
Exp-Gap$\mathsection$ (Karnin et al., 2013) | $\mathcal{O}\left(H(\mu)\log(1/\delta)\right)$ | $\mathcal{O}(\sum_{i\neq i^{\star}}\Delta_{i}^{-2}\log\log\Delta_{i}^{-1})$
lil’ UCB$\mathsection$ (Jamieson et al., 2014) | $\mathcal{O}\left(H(\mu)\log(1/\delta)\right)$ | $\mathcal{O}(\sum_{i\neq i^{\star}}\Delta_{i}^{-2}\log\log\Delta_{i}^{-1})$
DKM$\dagger$ (Degenne et al., 2019) | $T^{\star}(\mu)\log(1/\delta)+\tilde{\mathcal{O}}(\sqrt{\log(1/\delta)})$ | $\tilde{\mathcal{O}}\left(KT^{\star}(\mu)^{2}\right)$
Peace$\mathsection$ (Katz-Samuels et al., 2020) | $\mathcal{O}\left(T^{\star}(\mu)\log(1/\delta)\right)$ | $\mathcal{O}\left(H(\mu)\log(K/\Delta_{\min})\right)$
FWS$\dagger$ (Wang et al., 2021) | $T^{\star}(\mu)\log(1/\delta)+\mathcal{O}(\log\log(1/\delta))$ | $\mathcal{O}\left(e^{K}H(\mu)^{19/2}\right)$
EBS$\dagger$ (Barrier et al., 2022)* | $T^{\star}(\mu)\log(1/\delta)+o(1)$ | $\mathcal{O}\left(KH(\mu)^{4}/w_{\min}^{2}\right)$
TTUCB$\dagger$ (this work)** | $T^{\star}_{\beta}(\mu)\log(1/\delta)+\mathcal{O}(\log\log(1/\delta))$ |  $\mathcal{O}\left(\left(H(\mu)\log H(\mu)\right)^{\alpha}\right)$ with $\alpha>1$

##### Comparison with Existing Upper Bounds

Table 1 summarizes the asymptotic and non-asymptotic scalings of the upper
bound on the sample complexity of existing BAI algorithms. Among the class of
asymptotically ($\beta$-)optimal algorithms, very few of them also enjoy non-
asymptotic guarantees, e.g. the existing analyses for Track-and-Stop and Top
Two algorithms are purely asymptotic. The gamification approach of Degenne et
al. (2019) is the first attempt to provide both. While their non-asymptotic
upper bound on $\mathbb{E}_{\mu}[\tau_{\delta}]$ also involves an implicit
time $T_{1}(\delta)$, it scales with $KT^{\star}(\mu)^{2}$ and is only valid
for $\log(1/\delta)\gtrsim KT^{\star}(\mu)$ (see their Lemma 2, with constants
given by Appendix D.7). Let
$T^{\star}_{\delta}:=T^{\star}(\mu)\log(1/\delta)$. As a first order
approximation, they obtain $T_{1}(\delta)\approx
T^{\star}_{\delta}+\Theta\left(\sqrt{T^{\star}_{\delta}\log
T^{\star}_{\delta}}\right)$, and we obtain
$T_{0}(\delta)\approx\Theta\left(T^{\star}_{\delta}+\log
T^{\star}_{\delta}\right)$ (Lemma D.13). Wang et al. (2021) were the first to
obtain an upper bound on $\mathbb{E}_{\mu}[\tau_{\delta}]$ of the form
$\Theta(T^{\star}_{\delta}+\log\log(1/\delta))$. While they improved the
second-order $\delta$-dependent term, the $\delta$-independent term scales
with $e^{K}H(\mu)^{19/2}$ (see their Theorem 2 for $\varepsilon^{-1}\gtrsim
T^{\star}(\mu)$, with constants given by Appendix N). Let
$\Delta_{\min}:=\min_{i\neq i^{\star}}(\mu_{i^{\star}}-\mu_{i})$. The
algorithm proposed by Barrier et al. (2022) has a non-asymptotic upper bound
on $\mathbb{E}_{\mu}[\tau_{\delta}\mathds{1}\left(\mathcal{E}\right)]$ of the
form $(1+\varepsilon)T^{\star}_{\delta}+f(\mu,\delta)$ which is valid for
$\log(1/\delta)\gtrsim w_{\min}^{-2}K/\Delta_{\min}$, where $\mathcal{E}$ is
such that $\mathbb{P}_{\mu}(\mathcal{E}^{\complement})\leq\gamma$. Since
$f(\mu,\delta)=_{\delta\to 0}o(1)$, they obtain a better $\delta$-dependency.
However, $f(\mu,\delta)$ is arbitrarily large when
$w_{\min}:=\min_{i\in[K]}w^{\star}(\mu)_{i}$ is arbitrarily small since it
scales with $KH(\mu)^{4}/w_{\min}^{2}$. Therefore, they suffer from the
pitfall which we avoided by clipping. In light of Table 1, TTUCB enjoys the
best scaling when $H(\mu)\to+\infty$ in the class of asymptotically
($\beta$-)optimal BAI algorithms.

The LUCB1 algorithm (Kalyanakrishnan et al., 2012) has a structure similar to
a Top Two algorithm, with the difference that LUCB samples both the leader and
the challenger instead of choosing one. As LUCB1 satisfies
$\mathbb{E}_{\mu}[\tau_{\delta}]\leq 292H(\mu)\log(H(\mu)/\delta)+16$, it
enjoys better scaling when $H(\mu)\to+\infty$ than TTUCB. Since the empirical
allocation of LUCB1 is not converging towards $w^{\star}_{1/2}(\mu)$, it is
not asymptotically $1/2$-optimal. The Peace algorithm (Katz-Samuels et al.,
2020) has a non-asymptotic upper bound on $\tau_{\delta}$ of the form
$\mathcal{O}((T^{\star}_{\delta}+\gamma^{\star}(\mu))\log(K/\Delta_{\min}))$,
which holds with probability at least $1-\delta$. The term
$\gamma^{\star}(\mu)$ is a Gaussian-width which originates from concentration
on the suprema of Gaussian processes and satisfies
$\gamma^{\star}(\mu)=\Omega(H(\mu))$.

Another class of BAI algorithms focus on the dependency in the gaps
$\Delta_{i}:=\mu_{i^{\star}}-\mu_{i}$, and derive non-asymptotic upper bound
on $\tau_{\delta}$ holding with high probability. Karnin et al. (2013);
Jamieson et al. (2014); Chen et al. (2017a, b) gives $\delta$-PAC algorithms
with an upper bound of the form $\mathcal{O}(H(\mu)\log(1/\delta)+\sum_{i\neq
i^{\star}}\Delta_{i}^{-2}\log\log\Delta_{i}^{-1})$, and Jamieson et al. (2014)
shows that for two arms the dependency $\Delta^{-2}\log\log\Delta^{-1}$ is
optimal when $\Delta\to 0$. While those algorithms obtain the best scaling
when $H(\mu)\to+\infty$, they are not asymptotically ($\beta$-)optimal.

##  3 Non-Asymptotic Analysis

###  3.1 Proof Sketch of Theorem 2.4

Since the existing analyses of Top Two algorithms are asymptotic in nature, we
adopt a different approach which ressembles the non-asymptotic analysis of
Degenne et al. (2019). We first define concentration events to control the
deviations of the random variables used in the UCB leader and the TC
challenger. For all $n>K$, let
$\mathcal{E}_{n}:=\bigcap_{i\in[K]}\bigcap_{t\in[n^{5/6},n]}(\mathcal{E}^{1}_{t,i}\cap\mathcal{E}^{2}_{t,i})$
where

$\displaystyle\mathcal{E}^{1}_{t,i}$
$\displaystyle:=\\{\sqrt{N_{t,i}}|\mu_{t,i}-\mu_{i}|<\sqrt{6\log t}\\}\>,$
$\displaystyle\mathcal{E}^{2}_{t,i}$
$\displaystyle:=\\{\frac{(\mu_{t,i^{\star}}-\mu_{t,i})-(\mu_{i^{\star}}-\mu_{i})}{\sqrt{1/N_{t,i^{\star}}+1/N_{t,i}}}>-\sqrt{8\log
t}\\}\>.$

Using Lemmas D.8 and E.6, the proof boils down to constructing a time
$T(\delta)$ after which $\mathcal{E}_{n}\subset\\{\tau_{\delta}\leq n\\}$ for
$n>T(\delta)$ since it would yield that $\mathbb{E}_{\mu}[\tau_{\delta}]\leq
T(\delta)+12K$.

Let $n>K$ such that $\mathcal{E}_{n}\cap\\{n<\tau_{\delta}\\}$ holds true, and
$t\in[n^{5/6},n]$ such that $B^{\text{UCB}}_{t}=i^{\star}$. Using that $t\leq
n<\tau_{\delta}$, under $\bigcap_{i\neq i^{\star}}\mathcal{E}^{2}_{t,i}$, the
stopping condition yields that

$\sqrt{2c(n-1,\delta)}\geq(\frac{\mu_{i^{\star}}-\mu_{C^{\text{TC}}_{t}}}{\sqrt{1/N^{i^{\star}}_{t,i^{\star}}+1/N^{i^{\star}}_{t,C^{\text{TC}}_{t}}}}-\sqrt{8\log
n})_{+}\>.$

Let $w^{\star}_{1/2}$ be the unique element of $w^{\star}_{1/2}(\mu)$. Lemma
3.1 links the empirical proportions $N^{i^{\star}}_{t,i}/(t-1)$ to the
$1/2$-optimal allocations $w^{\star}_{1/2,i}$ for
$i\in\\{i^{\star},C^{\text{TC}}_{t}\\}$. It is the key technical challenge of
our non-asymptotic proof strategy.

######  Lemma 3.1.

There exist $D_{0}\geq 1$ and $T_{\mu}>0$ such that for all $n>T_{\mu}$ such
that $\mathcal{E}_{n}\cap\\{n<\tau_{\delta}\\}$ holds true, there exists
$t\in[n^{5/6},n]$ with $B^{\text{UCB}}_{t}=i^{\star}$, which satisfies

$(n-1)(1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,C^{\text{TC}}_{t}}^{i^{\star}})\leq
D_{0}(2+1/w^{\star}_{1/2,C^{\text{TC}}_{t}})\>.$

Before proving Lemma 3.1, we conclude the proof of Theorem 2.4. Let
$D_{0},T_{\mu}$ and $t$ as in Lemma 3.1 and
$T(\delta):=\sup\\{n>K\mid\>n-1\leq
T^{\star}_{1/2}(\mu)D_{0}(\sqrt{c(n-1,\delta)}+\sqrt{4\log n})^{2}\\}$. For
all $n>\max\\{T_{\mu},T(1)\\}$, we have

$\sqrt{c(n-1,\delta)}+\sqrt{4\log
n}\geq\sqrt{(n-1)T^{\star}_{1/2}(\mu)^{-1}D_{0}^{-1}}\>.$

Therefore, we have proved that
$\mathcal{E}_{n}\cap\\{n<\tau_{\delta}\\}=\emptyset$ for all
$n>\max\\{T_{\mu},T(\delta)\\}$. This concludes the proof.

Provided that $B_{t}=i^{\star}$, the above only used the stopping condition
and the TC challenger, and no other properties of the leader. Lemma 3.2 shows
that $B^{\text{UCB}}_{t}=i^{\star}$, except for a sublinear number of times.
Section 3.3 exhibits sufficient conditions on a regret minimization algorithm
to obtain a non-asymptotic upper bound.

######  Lemma 3.2.

Under the event
$\bigcap_{k\in[K]}\bigcap_{t\in[n^{5/6},n]}\mathcal{E}^{1}_{t,k}$,

$L_{n,i^{\star}}\geq n-1-24H(\mu)\log n-2K\>.$

##### Proof Sketch of Lemma 3.1

The key technical challenge is to link
$N_{t,C^{\text{TC}}_{t}}^{i^{\star}}/(n-1)$ with
$w^{\star}_{1/2,C^{\text{TC}}_{t}}$. We adopt the approach used to analyze of
APT (Locatelli et al., 2016): consider an arm being over-sampled and study the
last time this arm was pulled. By the pigeonhole principle, at time $n$,

$\exists k_{1}\neq i^{\star},\>\text{s.t.}\quad N_{n,k_{1}}^{i^{\star}}\geq
2(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})w^{\star}_{1/2,k_{1}}\>.$ (5)

Let $t_{1}$ be the last time at which $B^{\text{UCB}}_{t}=i^{\star}$ and
$C^{\text{TC}}_{t}=k_{1}$, hence $N_{t_{1},k_{1}}^{i^{\star}}\geq
N_{n,k_{1}}^{i^{\star}}-1$. Using Lemmas 2.2 and 3.2, we show that
$N_{t_{1},k_{1}}^{i^{\star}}\gtrapprox w^{\star}_{1/2,k_{1}}(n-1)$ and then
that $t_{1}\geq n^{5/6}$ for $n$ large enough (see Appendix D.2).

Then, we need to link $N_{t_{1},i^{\star}}^{i^{\star}}$ to $(n-1)/2$. When
$w^{\star}_{1/2,k_{1}}$ is small, (5) can be true at $t_{1}=n^{5/6}$, hence
there is no hope to show that $t_{1}=n-o(n)$. To circumvent this problem, we
link $N_{t_{1},i^{\star}}^{i^{\star}}$ to $N_{t_{1},k_{1}}^{i^{\star}}$ thanks
to Lemma 2.2, and use that

$\displaystyle\frac{n-1}{N_{t_{1},i^{\star}}^{i^{\star}}}+\frac{n-1}{N_{t_{1},k_{1}}^{i^{\star}}}$
$\displaystyle\leq\left(2+\frac{n-1}{N_{t_{1},k_{1}}^{i^{\star}}}\right)\left(\frac{N_{t_{1},k_{1}}^{i^{\star}}}{N_{t_{1},i^{\star}}^{i^{\star}}}+1\right)$
(6) $\displaystyle\leq 2(1+\varepsilon)^{2}(2+1/w^{\star}_{1/2,k_{1}})\>,$

for $n>T_{\mu}(w_{-})$ with
$T_{\mu}(w_{-})\leq\max\\{C_{\mu}^{1.2},(2/(\varepsilon
w_{-})+1)^{6},(2/\varepsilon)^{1.2}\\}$ (Lemmas D.10 and D.11), where
$w_{-}=\min_{i\neq i^{\star}}w^{\star}_{1/2,i}>0$ lower bounds
$w^{\star}_{1/2,k_{1}}$. This concludes the proof for $w_{0}=0$. The (sub-
optimal) multiplicative factor $2$ in $T_{0}(\delta)$ comes from the
inequality (6). To remove it, we need to control the deviation between the
empirical proportion of arm $i$ and $w^{\star}_{1/2,i}$ for all $i\in[K]$.
Nevertheless, TTUCB is asymptotically $1/2$-optimal (Theorem 2.3).

##### Refined Analysis

For $w_{0}\in(0,(K-1)^{-1}]$, we develop a refined method to clip $\min_{i\neq
i^{\star}}w_{1/2,i}^{\star}$ by $w_{0}/2$ (see Appendix D). Our method can be
used to analyze other algorithms, and it improves existing results on APT.

###  3.2 Beyond Gaussian Distributions

Theorems 2.3 and 2.4 naturally hold for sub-Gaussian r.v. thanks to simple
adaptations of concentration results (see, e.g., Lemmas 2.1, E.2 and E.5). The
situation is akin to the regret bound of UCB: it holds for any sub-Gaussian,
but it is close to optimality in a distribution-dependent sense only for
Gaussians. However, if the focus is on asymptotically $\beta$-optimal
algorithms, then it is challenging to express the characteristic time
$T^{\star}(\mu)$ for the non-parametric class of sub-Gaussian distributions
with known sub-Gaussian bound.

The TTUCB algorithm can also be defined for more general distributions such as
single-parameter exponential families or bounded distributions. It is only a
matter of adapting the definition of the UCB leader and the TC challenger. For
bounded distributions, the UCB leader was studied in Agrawal et al. (2021) and
the TC challenger was analyzed in Jourdan et al. (2022). Leveraging their
unified analysis of Top Two algorithms with our tracking-based results, we can
show asymptotic $\beta$-optimality of TTUCB for bounded distributions and
single-parameter exponential families with sub-exponential tails. We believe
that non-asymptotic guaranties could be obtained for more general
distributions, but it will come at the price of more technical arguments and
less explicit non-asymptotic terms.

###  3.3 Generic Regret Minimizing Leader

Our non-asymptotic analysis highlights that any regret minimization algorithm
that selects the arm $i^{\star}$ except for a sublinear number of times
(Property 1) can be used as leader with the TC challenger.

######  Property 1.

There exists $(\tilde{\mathcal{E}}_{n})_{n}$ with
$\sum_{n}\mathbb{P}_{\mu}(\tilde{\mathcal{E}}_{n}^{\complement})<+\infty$ and
a function $h$ with $h(n)=\mathcal{O}(n^{\gamma})$ for some $\gamma\in(0,1)$
such that under event $\tilde{\mathcal{E}}_{n}$, $L_{n,i^{\star}}\geq
n-1-h(n)$.

For asymptotic guarantees, the sufficient properties on the leader from
Jourdan et al. (2022) are weaker since they are even satisfied by the greedy
choice $B_{n}=\hat{\imath}_{n}$. While Top Two algorithms were introduced by
Russo (2016) to adapt Thompson Sampling to BAI, we have shown that other
regret minimization algorithms can be used: the Top Two method is a generic
wrapper to convert any regret minimization algorithm into a best arm
identification strategy.

The regret of an algorithm at time $n$, $\bar{R}_{n}=\sum_{i\neq
i^{\star}}\Delta_{i}N_{n,i}$, is almost always studied through its expectation
$\mathbb{E}[\bar{R}_{n}]$. This is however not sufficient for our application.
We need to prove that with high probability, $N_{n,i}$ is small for all arm
$i\neq i^{\star}$. Such guarantees are known for UCB (Audibert et al., 2009)
and ETC (Lattimore & Szepesvari, 2019), but are yet unknown for Thompson
Sampling. We cannot in general obtain a good enough bound on $N_{n,i}$ from a
bound on $\mathbb{E}[\bar{R}_{n}]$. However, we can if we have high
probability bounds on $\bar{R}_{n}$. Suppose that a regret minimization
algorithm $\text{Alg}_{1}$ satisfies Property 2 and is independent of the
horizon $n$.

######  Property 2.

There exists $s>1$, $\gamma\in(0,1)$, $(\mathcal{E}_{n,\delta})_{(n,\delta)}$
with $\sum_{n}\mathbb{P}_{\mu}[\mathcal{E}_{n,n^{-s}}^{\complement}]<+\infty$
and a function $h$ with $h(n,n^{-s})=\mathcal{O}(n^{\gamma})$ such that under
event $\mathcal{E}_{n,\delta}$, $\bar{R}_{n}\leq h(n,\delta)$.

Let $\text{Alg}_{2}$ be the algorithm $\text{Alg}_{1}$ used in a Top Two
procedure, but which uses only the observations obtained at times $n$ such
that $I_{n}=B_{n}$ and discards the rest. Let
$\tilde{\mathcal{E}}_{n}=\mathcal{E}_{n,n^{-s}}$ and
$\Delta_{\min}=\min_{i\neq i^{\star}}\Delta_{i}$. Then, under
$\tilde{\mathcal{E}}_{n}$, $\text{Alg}_{2}$ satisfies $\sum_{i\neq
i^{\star}}N^{i}_{n,i}\leq h(n,n^{-s})/\Delta_{\min}$ and Lemma 2.2 yields

$N^{i^{\star}}_{n,i^{\star}}\geq\beta(n-1)-h(n,n^{-s})/\Delta_{\min}-K/2\>.$

Therefore, Property 1 holds for $\tilde{\mathcal{E}}_{n}$ and
$h(n)=(h(n,n^{-s})/\Delta_{\min}+K/2+1)/\beta$. Given a specific algorithm, a
finer analysis could avoid discarding information by using $\text{Alg}_{1}$
with every observations.

###  3.4 Adaptive Proportions

Given a fixed allocation $\beta$, any Top Two algorithm can at best be
asymptotically $\beta$-optimal. Since the optimal allocation
$\beta^{\star}\in\operatorname*{arg\,min}_{\beta\in(0,1)}T^{\star}_{\beta}(\mu)$
is unknown, it should be learned from the observations by a Top Two algorithm
using an adaptive proportion $\beta_{n}$ at time $n$. While showing asymptotic
optimality for an adaptive Top Two algorithm is still an open problem, Wang et
al. (2022) propose a heuristic update mechanism for $\beta$ based on the
optimality conditions for the problem underlying $T^{\star}(\mu)$. For BAI
with Gaussian observations, their update mechanism rewrites as
$\beta_{n}=N_{n,C_{n}}/(N_{n,B_{n}}+N_{n,C_{n}})$ (see Appendix G.1).

Let
$\bar{\beta}^{i}_{n}:=\frac{1}{L_{n,i}}\sum_{t\in[n-1]}\beta_{t}\mathds{1}\left(B_{t}=i\right)$
be the average proportion when arm $i$ was the leader before time $n$. When
using tracking with adaptive proportions, one should use
$\bar{\beta}^{B_{n}}_{n+1}$ instead of $\beta$. Up to technicalities, our non-
asymptotic arguments can be adapted to use $\bar{\beta}^{B_{n}}_{n+1}$.
Showing optimality requires important steps whose proof still eludes us. The
main challenges are to prove the convergence of $\bar{\beta}^{B_{n}}_{n}$
towards the optimal choice $\beta^{\star}$, to control its convergence rate
and ensure that it is bounded away from $\\{0,1\\}$.

##  4 Experiments

In the moderate regime ($\delta=0.1$), we assess the empirical performance of
TTUCB with bonus $g_{m}$ and concentration parameters $s=\alpha=1.2$. As
benchmarks, we compare our algorithm with three sampling-based Top Two
algorithms: TTTS, T3C and $\beta$-EB-TCI. In addition, we consider Track-and-
Stop (TaS) (Garivier & Kaufmann, 2016), FWS (Wang et al., 2021), DKM (Degenne
et al., 2019), LUCB (Kalyanakrishnan et al., 2012) and uniform sampling. At
time $n$, the LUCB algorithm computes a leader and a challenger, then sample
them both (see Appendix G.1). To provide a clear comparison with Top Two
algorithms, we define a new $\beta$-LUCB algorithm which sample the leader
with probability $\beta$, else sample the challenger. At the exception of LUCB
and $\beta$-LUCB which have their own stopping rule, all algorithms uses the
stopping rule (1) with the heuristic threshold $c(n,\delta)=\log((1+\log
n)/\delta)$. Even though this choice is not sufficient to prove
$\delta$-correctness, it yields an empirical error which is several orders of
magnitude lower than $\delta$. Top Two algorithms and $\beta$-LUCB use
$\beta=1/2$. To allow for a fair numerical comparison, LUCB and $\beta$-LUCB
use $\sqrt{2c(n-1,\delta)/N_{n,i}}$ as bonus, which is too tight to yield
valid confidence intervals. Supplementary experiments are available in
Appendix G.

Figure 1: Empirical stopping time on random instances ($K=10$).

##### Random Instances

We assess the performance on $5000$ random Gaussian instances with $K=10$ such
that $\mu_{1}=0.6$ and $\mu_{i}\sim\mathcal{U}([0.2,0.5])$ for all $i\neq 1$.
Numerically, we observe $w^{\star}(\mu)_{i^{\star}}\approx 1/3\pm 0.02$ (mean
$\pm$ std). In Figure 1, we see that TTUCB performs on par with existing Top
Two algorithms, and slightly outperforms TaS and FWS. Our algorithm achieves
significantly better result than DKM, LUCB, $1/2$-LUCB and uniform sampling.
The CPU running time is reported in Table 4, and the observed empirical errors
before stopping is displayed in Figure 5 (Appendix G.2).

Figure 2: Influence of $K$ on $\mathbb{E}_{\mu}[\tau_{\delta}]$ ($\pm$ Std)
for “$1$-Sparse”.

##### Larger Sets of Arms

Next, we evaluate the impact of larger number of arms (up to $K=1000$). The
“$1$-sparse” scenario of Jamieson & Nowak (2014) sets $\mu_{1}=1/4$ and
$\mu_{i}=0$ for all $i\neq 1$, i.e. $H(\mu)=32(K-1)$ (see Appendix G.2 for
other instances). We consider algorithms with low computational cost. In
Figure 2, all algorithms have the same linear scaling in $K$ (i.e. in
$H(\mu)$). Faced with an increase in the number of arms, the TS leader used in
T3C appears to be more robust than the UCB leader in TTUCB. This is a common
feature of UCB algorithms since the bonus of each sub-optimal arm has to be
overcome.

Figure 3: Empirical stopping time on “equal means” instances
$(K,\mu_{i^{\star}},\Delta)=(35,0,0.5)$: constant $\beta=1/2$ and adaptive
(A-). The Lower bound (“lbd”) is $T^{\star}(\mu)\log(1/\delta)$.

##### Adaptive Proportions

The ratio $T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$ seems to reach its highest
value $r_{K}=2K/(1+\sqrt{K-1})^{2}$ for “equal means” instances (Lemma C.6),
i.e. $\mu_{i}=\mu_{i^{\star}}-\Delta$ for all $i\neq i^{\star}$ with
$\Delta>0$. To best observe differences between Top Two algorithms with
$\beta=1/2$ and their adaptive version, we consider such instances with $K=35$
($r_{K}\approx 3/2$). Figure 3 reveals that adaptive proportions yield better
empirical performance, with an empirical speed-up close to $r_{K}\approx 3/2$.
On random instances (Figure 8 in Appendix G.2), the improvement from adaptive
proportions is milder. This is expected as
$T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$ is close to one when sub-optimal arms
have significantly distinct means (see Figure 4).

##  5 Conclusion

In this paper, we have shown the first non-asymptotic upper bound on the
expected sample complexity of a Top Two algorithm, which holds for any error
level and for any instance having a unique best arm. Furthermore, we have
demonstrated that the TTUCB algorithm achieves competitive empirical
performance compared to other algorithms, including Top Two methods.

As in previous work on Top Two methods, we obtained theoretical guarantees for
a fixed allocation $\beta$ of the proportion of samples allocated to the
leader. While heuristics have been proposed by Wang et al. (2022) to define an
adaptive proportion $\beta_{n}$ at time $n$, no guaranty have been obtained
for them. Deriving guarantees for adaptive proportions is a challenging open
problem, whose solution would improve our understanding of Top Two algorithms.
Additionally, while we showed that the empirical speed-up is mild for random
Gaussian instances and significant for hard instances, we believe the
improvement can be larger for other distributions.

Finally, the Top Two sampling rule is a promising method to tackle complex
settings such as structured bandits. While heuristics exist for some
structured bandits such as Top-$k$, it is not clear whether it is possible to
efficiently adapt Top Two methods to cope for more sophisticated structure
such as (transductive) combinatorial or linear bandits.

## Acknowledgements

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 FATE
(ANR22-CE23-0016-01).

## References

  * Agrawal et al. (2021) Agrawal, S., Juneja, S. K., and Koolen, W. M.  Regret minimization in heavy-tailed bandits.  In _Conference on Learning Theory_ , 2021.
  * Ariu et al. (2021) Ariu, K., Kato, M., Komiyama, J., McAlinn, K., and Qin, C.  Policy choice and best arm identification: Asymptotic analysis of exploration sampling under posterior weighted policy regret.  _arXiv preprint arXiv:2109.08229_ , 2021.
  * Audibert et al. (2009) Audibert, J.-Y., Munos, R., and Szepesvári, C.  Exploration-exploitation trade-off using variance estimates in multi-armed bandits.  _Theoretical Computer Science_ , 410(19), 2009.
  * Audibert et al. (2010) Audibert, J.-Y., Bubeck, S., and Munos, R.  Best Arm Identification in Multi-armed Bandits.  In _Conference on Learning Theory_ , 2010.
  * Auer et al. (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P.  Finite-time analysis of the multiarmed bandit problem.  _Machine Learning_ , 47(2):235–256, 2002.
  * Barrier et al. (2022) Barrier, A., Garivier, A., and Kocák, T.  A non-asymptotic approach to best-arm identification for gaussian bandits.  In _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , 2022.
  * Chaloner & Verdinelli (1995) Chaloner, K. and Verdinelli, I.  Bayesian experimental design: A review.  _Statistical Science_ , 1995.
  * Chen et al. (2017a) Chen, L., Li, J., and Qiao, M.  Towards instance optimal bounds for best arm identification.  _Conference on Learning Theory_ , 2017a.
  * Chen et al. (2017b) Chen, L., Li, J., and Qiao, M.  Nearly instance optimal sample complexity bounds for top-k arm selection.  In _Artificial Intelligence and Statistics_ , 2017b.
  * Chernoff (1959) Chernoff, H.  Sequential design of Experiments.  _The Annals of Mathematical Statistics_ , 30(3):755–770, 1959.
  * Degenne (2019) Degenne, R.  _Impact of structure on the design and analysis of bandit algorithms_.  PhD thesis, Université de Paris, 2019.
  * Degenne et al. (2019) Degenne, R., Koolen, W. M., and Ménard, P.  Non-asymptotic pure exploration by solving games.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Degenne et al. (2020) Degenne, R., Shao, H., and Koolen, W. M.  Structure adaptive algorithms for stochastic bandits.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Even-Dar et al. (2002) Even-Dar, E., Mannor, S., and Mansour, Y.  Pac bounds for multi-armed bandit and markov decision processes.  In _International Conference on Computational Learning Theory_ , 2002\.
  * Even-Dar et al. (2006) Even-Dar, E., Mannor, S., and Mansour, Y.  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) Gabillon, V., Ghavamzadeh, M., and Lazaric, A.  Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence.  In _Advances in Neural Information Processing Systems_ , 2012.
  * Garivier & Kaufmann (2016) Garivier, A. and Kaufmann, E.  Optimal best arm identification with fixed confidence.  In _Proceedings of the 29th Conference On Learning Theory_ , 2016\.
  * Hong et al. (2021) Hong, L., Fan, W., and Luo, J.  Review on ranking and selection: A new perspective.  _Frontiers of Engineering Management_ , 8:321–343, 2021\.
  * Jamieson et al. (2014) Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S.  lil’UCB: an Optimal Exploration Algorithm for Multi-Armed Bandits.  In _Proceedings of the 27th Conference on Learning Theory_ , 2014\.
  * Jamieson & Nowak (2014) Jamieson, K. G. and Nowak, R. D.  Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting.  In _Conference on Information Sciences and Systems (CISS)_ , 2014\.
  * Jourdan et al. (2022) Jourdan, M., Degenne, R., Baudry, D., De Heide, R., and Kaufmann, E.  Top two algorithms revisited.  _Advances in Neural Information Processing Systems_ , 2022.
  * Jourdan et al. (2023) Jourdan, M., Degenne, R., and Kaufmann, E.  Dealing with unknown variances in best-arm identification.  _International Conference on Algorithmic Learning Theory_ , 2023.
  * Jun & Nowak (2016) Jun, K.-W. and Nowak, R.  Anytime exploration for multi-armed bandits using confidence information.  In _International Conference on Machine Learning (ICML)_ , 2016.
  * Kalyanakrishnan et al. (2012) Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P.  PAC subset selection in stochastic multi-armed bandits.  In _International Conference on Machine Learning (ICML)_ , 2012\.
  * Karnin et al. (2013) Karnin, Z., Koren, T., and Somekh, O.  Almost optimal Exploration in multi-armed bandits.  In _International Conference on Machine Learning (ICML)_ , 2013\.
  * Katz-Samuels et al. (2020) Katz-Samuels, J., Jain, L., Jamieson, K. G., et al.  An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits.  _Advances in Neural Information Processing Systems_ , 2020.
  * Kaufmann & Koolen (2021) Kaufmann, E. and Koolen, W. M.  Mixture martingales revisited with applications to sequential tests and confidence intervals.  _Journal of Machine Learning Research_ , 22(246):1–44, 2021.
  * Kaufmann et al. (2014) Kaufmann, E., Cappé, O., and Garivier, A.  On the Complexity of A/B Testing.  In _Proceedings of the 27th Conference On Learning Theory_ , 2014\.
  * Lattimore & Szepesvari (2019) Lattimore, T. and Szepesvari, C.  _Bandit Algorithms_.  Cambridge University Press, 2019.
  * Locatelli et al. (2016) Locatelli, A., Gutzeit, M., and Carpentier, A.  An optimal algorithm for the thresholding bandit problem.  In _International Conference on Machine Learning (ICML)_ , 2016.
  * Marjani et al. (2022) Marjani, A. A., Kocák, T., and Garivier, A.  On the complexity of all $\varepsilon$-best arms identification.  _arXiv preprint arXiv:2202.06280_ , 2022.
  * Mason et al. (2020) Mason, B., Jain, L., Tripathy, A., and Nowak, R.  Finding all $\varepsilon$-good arms in stochastic bandits.  _Advances in Neural Information Processing Systems_ , 2020.
  * Mukherjee & Tajer (2022) Mukherjee, A. and Tajer, A.  Sprt-based efficient best arm identification in stochastic bandits.  _arXiv preprint arXiv:2207.11158_ , 2022.
  * Pukelsheim (2006) Pukelsheim, F.  _Optimal design of experiments_.  SIAM, 2006.
  * Qin et al. (2017) Qin, C., Klabjan, D., and Russo, D.  Improving the expected improvement algorithm.  In _Advances in Neural Information Processing Systems 30 (NIPS)_ , 2017.
  * Robbins (1952) Robbins, H.  Some aspects of the sequential design of experiments.  _Bulletin of the American Mathematical Society_ , 58(5):527–535, 1952.
  * Russo (2016) Russo, D.  Simple Bayesian algorithms for best arm identification.  In _Proceedings of the 29th Conference on Learning Theory (COLT)_ , 2016.
  * Shang et al. (2020) Shang, X., de Heide, R., Kaufmann, E., Ménard, P., and Valko, M.  Fixed-confidence guarantees for bayesian best-arm identification.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2020.
  * Simchowitz et al. (2017) Simchowitz, M., Jamieson, K., and Recht, B.  The simulator: Understanding adaptive sampling in the moderate-confidence regime.  In _Conference on Learning Theory_ , 2017.
  * Thompson (1933) Thompson, W.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25:285–294, 1933.
  * Wang et al. (2021) Wang, P.-A., Tzeng, R.-C., and Proutiere, A.  Fast pure exploration via frank-wolfe.  _Advances in Neural Information Processing Systems_ , 2021.
  * Wang et al. (2022) Wang, Z., Yang, S., and You, W.  Optimality conditions and algorithms for top-k arm identification.  _arXiv preprint arXiv:2205.12086_ , 2022.
  * Wilson (1927) Wilson, E. B.  Probable inference, the law of succession, and statistical inference.  _Journal of the American Statistical Association_ , 22(158):209–212, 1927.

##  Appendix A Outline

The appendices are organized as follows:

  * •

Appendix B gathers notation used in this work.

  * •

In Appendix C, we study the link between $T^{\star}(\mu)$ and
$T^{\star}_{\beta}(\mu)$ for Gaussian distributions.

  * •

The detailed analysis of our non-asymptotic upper bound (Theorem 2.4),
sketched in Section 3, is detailed in Appendix D. We also give a non-
asymptotic upper bound on the TTUCB using $g_{m}$ in (3) (Corollary D.5), and
on uniform sampling (Theorem D.6).

  * •

We show the asymptotic optimality of our algorithm (Theorem 2.3) in Appendix
F.

  * •

Appendix E gathers concentration results used by the stopping rule (Lemma 2.1)
and the sampling rule.

  * •

Implementation details and supplementary experiments are detailed in Appendix
G.

Table 2: Notation for the setting. Notation | Type | Description
---|---|---
$K$ | $\mathbb{N}$ | Number of arms
$\mu_{i}$ | $\mathbb{R}$ | Mean of arm $i\in[K]$
$\mu$ | $\mathbb{R}^{K}$ | Vector of means, $\mu:=(\mu_{i})_{i\in[K]}$
$i^{\star}$ | $\mathbb{R}^{K}\to[K]$ | Best arm operator, $i^{\star}(\mu)=\operatorname*{arg\,max}_{i\in[K]}\mu_{i}$
$T^{\star}(\mu),T^{\star}_{\beta}(\mu)$ | $\mathbb{R}^{\star}_{+}$ | Asymptotic ($\beta$-)characteristic time
$w^{\star}(\mu),w^{\star}_{\beta}(\mu)=\\{(w^{\star}_{\beta,i})_{i\in[K]}\\}$ | $\triangle_{K}$ | Asymptotic ($\beta$-)optimal allocation

##  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$, 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\\}$. While Table 2 gathers problem-specific
notation, Table 3 groups notation for the algorithms. We emphasize that
$N^{i}_{n,i}$ is the number of times where we pulled arm $i$ as a leader
before time $n$.

Table 3: Notation for algorithms. Notation | Type | Description
---|---|---
$B_{n}$ | $[K]$ | Leader at time $n$
$C_{n}$ | $[K]$ | Challenger at time $n$
$I_{n}$ | $[K]$ | Arm sampled at time $n$
$\beta$ | $(0,1)$ | Proportion parameter
$X_{n,I_{n}}$ | $\mathbb{R}$ | Sample observed at the end of time $n$, i.e. $X_{n,I_{n}}\sim\mathcal{N}(\mu_{I_{n}},1)$
$\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$, i.e. $\hat{\imath}_{n}\in\operatorname*{arg\,max}_{i\in[K]}\mu_{n,i}$
$\tau_{\delta}$ | $\mathbb{N}$ | Sample complexity (stopping time of the algorithm)
$\hat{\imath}$ | $[K]$ | Arm recommended by the algorithm
$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$, $N_{n,i}:=\sum_{t\in[n-1]}\mathds{1}\left(I_{t}=i\right)$
$\mu_{n,i}$ | $\mathcal{I}$ | Empirical mean of arm $i$ before time $n$, $\mu_{n,i}:=\frac{1}{N_{n,i}}\sum_{t\in[n-1]}X_{t,I_{t}}\mathds{1}\left(I_{t}=i\right)$
$L_{n,i}$ | $\mathbb{N}$ | Counts of $B_{t}=i$ before time $n$, $L_{n,i}:=\sum_{t\in[n-1]}\mathds{1}\left(B_{t}=i\right)$
$N^{i}_{n,j}$ | $\mathbb{N}$ | Counts of $(B_{t},I_{t})=(i,j)$ before time $n$, $N^{i}_{n,j}:=\sum_{t\in[n-1]}\mathds{1}\left((B_{t},I_{t})=(i,j)\right)$

##  Appendix C Characteristic Times

Let $\mu\in\mathcal{D}^{K}$ such that $i^{\star}(\mu)=\\{i^{\star}\\}$. Let
$\beta\in(0,1)$ and $w^{\star}_{\beta}$ be the unique allocation
$\beta$-optimal allocation satisfying $w^{\star}_{\beta,i}>0$ for all
$i\in[K]$ (Lemma C.2), i.e. $w_{\beta}^{\star}(\mu)=\\{w^{\star}_{\beta}\\}$
where

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

We restate without proof two fundamental results on the characteristic time
and the associated allocation, which were first shown in (Russo, 2016). Lemma
C.1 gives an upper bound on $T^{\star}_{\beta}(\mu)/T^{\star}(\mu)$ and Lemma
C.2 shows that the ($\beta$-)optimal allocation is unique with strictly
positive values. (Russo, 2016) shows that these two results hold for any
single-parameter exponential families. Jourdan et al. (2022) extended their
proof for the non-parametric family of bounded distributions. Moreover, they
argue that these results should hold for more general distributions provided
some regularity assumptions are satisfied.

######  Lemma C.1 (Russo (2016)).

$T^{\star}_{1/2}(\mu)\leq 2T^{\star}(\mu)$ and with
$\beta^{\star}=w^{\star}_{i^{\star}}(\mu)$,

$\displaystyle\frac{T^{\star}_{\beta}(\mu)}{T^{\star}(\mu)}\leq\max\left\\{\frac{\beta^{\star}}{\beta},\frac{1-\beta^{\star}}{1-\beta}\right\\}\>.$

######  Lemma C.2 (Russo (2016)).

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]$.

##### Gaussian Distributions

Since Lemma C.1 is a worst-case inequality holding for general distributions,
we expect that tighter inequality can be achieved for Gaussian distributions
by leveraging their symmetry. This intuition is fueled by recent results of
Barrier et al. (2022). Using a rewriting of the optimization problem
underlying $T^{\star}(\mu)$ (Lemma C.3), they provide a better understanding
of characteristic times and their optimal allocations (Lemma C.4). In
particular, for Gaussian distributions, Lemma C.4 shows that the optimal
allocation of arm $i^{\star}$ is never above $1/2$ and is larger than
$1/(\sqrt{K-1}+1)\geq 1/K$.

######  Lemma C.3 (Proposition $8$ in Barrier et al. (2022)).

Let $\mu\in\mathbb{R}^{K}$ be a $K$-arms Gaussian bandits and $r(\mu)$ be the
solution of $\psi_{\mu}(r)=0$, where

$\forall r\in(1/\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2},+\infty),\quad\psi_{\mu}(r)=\sum_{i\neq
i^{\star}}\frac{1}{\left(r(\mu_{i^{\star}}-\mu_{i})^{2}-1\right)^{2}}-1\>,$

and $\psi_{\mu}$ is convex and decreasing. Then,

$T^{\star}(\mu)=\frac{2r(\mu)}{1+\sum_{i\neq
i^{\star}}\frac{1}{r(\mu)(\mu_{i^{\star}}-\mu_{i})^{2}-1}}\>.$

######  Lemma C.4 (Proposition $10$ in Barrier et al. (2022)).

Let $\mu\in\mathbb{R}^{K}$ be a $K$-arms Gaussian bandits. For $K=2$,

$w^{\star}(\mu)=(0.5,0.5)\quad\text{and}\quad
T^{\star}(\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\>,$

and

$\max\left\\{\frac{8}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}},4\frac{1+\sqrt{K-1}}{\overline{\Delta^{2}}}\right\\}\leq
T^{\star}(\mu)\leq 2\frac{(1+\sqrt{K-1})^{2}}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}\>,$

where $\overline{\Delta^{2}}=\frac{1}{K-1}\sum_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}$. In particular, the equalities
$w^{\star}(\mu)_{i^{\star}}=1/(\sqrt{K-1}+1)$ and
$T^{\star}(\mu)=\frac{2(1+\sqrt{K-1})^{2}}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}$ are reached if and only if
$\mu_{i}=\max_{i\neq i^{\star}}\mu_{i}$ for all $i\neq i^{\star}$.

By inspecting the proof of Proposition 8 in Barrier et al. (2022), we obtain
directly the following rewriting of $T^{\star}_{\beta}(\mu)$.

######  Lemma C.5.

Let $\mu\in\mathbb{R}^{K}$ be a $K$-arms Gaussian bandits and $r_{\beta}(\mu)$
be the solution of $\varphi_{\mu,\beta}(r)=0$, where

$\forall r\in(1/\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2},+\infty),\quad\varphi_{\mu,\beta}(r)=\sum_{i\neq
i^{\star}}\frac{1}{r(\mu_{i^{\star}}-\mu_{i})^{2}-1}-\frac{1-\beta}{\beta}\>,$

and $\varphi_{\mu,\beta}$ is convex and decreasing. Then,

$T^{\star}_{\beta}(\mu)=\frac{2r_{\beta}(\mu)}{\beta}\>.$

###### Proof.

Using the proof of Proposition 8 in Barrier et al. (2022), we obtain directly
that

$\displaystyle 2T^{\star}_{\beta}(\mu)^{-1}=C_{\beta}(\mu)$

where $C_{\beta}(\mu)$ is the solution of $\Phi_{\mu}(C)=0$ where

$\Phi_{\mu}(C)=\sum_{i\neq
i^{\star}}\frac{\beta}{\beta(\mu_{i^{\star}}-\mu_{i})^{2}/C-1}-(1-\beta)\>.$

The idea behind the above result is that at the equilibrium, i.e. at
$w^{\star}$, all the transportation costs are equal to $C$. Then, the implicit
equation defining $C$ is obtained by using the constraints that $\sum_{i\neq
i^{\star}}w^{\star}_{i}=1-\beta$. To conclude, we simply use $r=\beta/C$.

Since it is the sum of $K-1$ convex and decreasing functions,
$\varphi_{\mu,\beta}$ is also convex and decreasing. ∎

Figure 4: Ratio of characteristic times
$\Omega(x)=T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$ for $K=3$ (left) and $K=4$
(right). The dashed blue line is $r_{2}=6/(1+\sqrt{2})^{2}$ (left), and the
blue point is $r_{3}=8/(1+\sqrt{3})^{2}$ (right).

Lemma C.6 aims at improving the worst-case inequality between
$T^{\star}_{1/2}(\mu)$ and $T^{\star}(\mu)$ in the Gaussian setting. For
$K=2$, those two quantities are equal. For $K\geq 3$, we showed that
$\max_{\mu:|i^{\star}(\mu)|=1}T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$ is at least
$r_{K}$, which is achieved when all sub-optimal arms have the same mean. As
the gradient of the ratio is the null vector for those instances, we
conjecture this is the maximum, i.e. $T^{\star}_{1/2}(\mu)\leq
r_{K}T^{\star}(\mu)$. Our conjecture is supported by numerical simulations for
$K\geq 3$. In Figure 4, we plot the ratio of characteristic times
$\Omega(x)=T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$ for $K\in\\{3,4\\}$. We
observed that our conjecture is validated empirically, and that
$T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$ is often close to $1$.

######  Lemma C.6.

For $K=2$, we have $T^{\star}_{1/2}(\mu)=T^{\star}(\mu)$. For $K\geq 3$, let
$r_{K}=2K/(1+\sqrt{K-1})^{2}$. Then, for all $\mu$ such that $i^{\star}(\mu)$
is unique, we have $\frac{T^{\star}_{1/2}(\mu)}{T^{\star}(\mu)}=\Omega(x)$
where
$x_{j}=\frac{\mu_{i^{\star}}-\mu_{j}}{\mu_{i^{\star}}-\mu_{j^{\star}}}\geq 1$
for all $j\notin\\{i^{\star},j^{\star}\\}$ with
$j^{\star}\in\operatorname*{arg\,min}_{j\neq
i^{\star}}\mu_{i^{\star}}-\mu_{j}$. In other words,
$\frac{T^{\star}_{1/2}(\mu)}{T^{\star}(\mu)}$ is independent from
$\mu_{i^{\star}}$ and $\min_{j\neq i^{\star}}\mu_{i^{\star}}-\mu_{j}$.
Moreover, we have

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

###### Proof.

Using Lemma C.4, we have $T^{\star}_{1/2}(\mu)=T^{\star}(\mu)$ directly for
$K=2$.

For $K\geq 3$, we want to upper bound $T^{\star}_{1/2}(\mu)/T^{\star}(\mu)$.
If we denote by $\Delta_{\min}(\mu)=\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}$, it is easy to see that
$T^{\star}_{1/2}(\mu)/T^{\star}(\mu)=T^{\star}_{1/2}(\tilde{\mu})/T^{\star}(\tilde{\mu})$
when $\Delta_{\min}(\mu)=\Delta_{\min}(\tilde{\mu})$. Likewise, this ratio is
invariant by translation of all means by a same quantity. Therefore, we
consider without restriction an instance $\mu$ such that
$\Delta_{\min}(\mu)=1$ and with

$\mu_{1}=0>\mu_{2}=-x_{2}\geq\cdots\geq\mu_{K}=-x_{K}\>,$

where $x_{2}=1$ and $x_{i}\geq 1$ for all $i\geq 3$.

First, we can rewrite

$\displaystyle T^{\star}_{1/2}(x)^{-1}$
$\displaystyle=\frac{1}{4}\max_{q\in\triangle_{K-1}}\min_{i\geq
2}\frac{x_{i}^{2}}{1+1/q_{i}}\geq\frac{1}{4}\max_{q\in\triangle_{K-1}}\min_{i\geq
2}\frac{1}{1+1/q_{i}}=\frac{1}{4K}\>,$

where the inequality is an equality if and only $x_{i}=1$ for all $i\geq 2$.
Using Lemma C.4, we know that

$T^{\star}(x)=2(1+\sqrt{K-1})^{2}$

if and only $x_{i}=1$ for all $i\geq 2$. Therefore, we have exhibited an
instance such that

$\frac{T^{\star}_{1/2}(\mu)}{T^{\star}(\mu)}=\frac{2K}{(1+\sqrt{K-1})^{2}}\>.$

Applying Lemma C.5 for $\beta=1/2$, we obtain $T^{\star}_{1/2}(x)=4C(x)$ where
$C(x)$ is the implicit solution of the equation

$\displaystyle\varphi(x,C(x))=0\quad\text{where}\quad\varphi(x,C)=\frac{1}{C-1}+\sum_{i\geq
3}\frac{1}{Cx_{i}^{2}-1}-1\>.$

Using Lemma C.3, we know that

$T^{\star}(x)=\frac{2r(x)}{1+\frac{1}{r(x)-1}+\sum_{i\geq
3}\frac{1}{r(x)x_{i}^{2}-1}}$

where $r(x)$ is the implicit solution of the equation

$\displaystyle\psi(x,r(x))=0\quad\text{where}\quad\psi(x,r)=\frac{1}{(r-1)^{2}}+\sum_{i\geq
3}\frac{1}{(rx_{i}^{2}-1)^{2}}-1\>.$

Therefore, we obtain that

$\displaystyle\Omega(x)=\frac{1}{2}\frac{T^{\star}_{1/2}(x)}{T^{\star}(x)}=\frac{C(x)}{r(x)-1}+\sum_{i\geq
3}\frac{C(x)}{r(x)(r(x)x_{i}^{2}-1)}\>,$

and our goal is to show that the above quantity is maximum if and only
$x_{i}=1$ for all $i\geq 2$. One way of doing this is by computing the
gradient and showing it is negative, which would imply that the function is
decreasing. Let $j\geq 3$. Using the implicit differentiation theorem, we
obtain

$\displaystyle\frac{\partial C}{\partial
x_{j}}(x)=-\frac{\frac{\partial\varphi}{\partial
x_{j}}(x,C(x))}{\frac{\partial\varphi}{\partial
C}(x,C(x))}=-\frac{\frac{2C(x)x_{j}}{(C(x)x_{j}^{2}-1)^{2}}}{\frac{1}{(C(x)-1)^{2}}+\sum_{i\geq
3}\frac{x_{i}^{2}}{(C(x)x_{i}^{2}-1)^{2}}}\quad\text{and}\quad\frac{\partial
C}{\partial x_{j}}(1_{K-2})=-\frac{2C(1_{K-2})}{K-1}\>,$

and

$\displaystyle\frac{\partial r}{\partial
x_{j}}(x)=-\frac{\frac{\partial\psi}{\partial
x_{j}}(x,r(x))}{\frac{\partial\psi}{\partial
r}(x,r(x))}=-\frac{\frac{2r(x)x_{j}}{(r(x)x_{j}^{2}-1)^{3}}}{\frac{1}{(r(x)-1)^{3}}+\sum_{i\geq
3}\frac{x_{i}^{2}}{(r(x)x_{i}^{2}-1)^{3}}}\quad\text{and}\quad\frac{\partial
r}{\partial x_{j}}(1_{K-2})=-\frac{2r(1_{K-2})}{K-1}\>.$

Direct computations yield that

$\displaystyle\frac{\partial}{\partial
x_{j}}\left(\frac{C(x)}{r(x)-1}\right)=\frac{\frac{\partial C}{\partial
x_{j}}(x)(r(x)-1)-C(x)\frac{\partial r}{\partial
x_{j}}(x)}{(r(x)-1)^{2}}\quad\text{and}\quad\frac{\partial}{\partial
x_{j}}\left(\frac{C(x)}{r(x)-1}\right)_{x=1_{K-2}}=\frac{1}{K-1}\frac{2C(1_{K-2})}{(r(1_{K-2})-1)^{2}}\>,$

and

$\displaystyle\frac{\partial}{\partial
x_{j}}\left(\frac{C(x)}{r(x)(r(x)x_{j}^{2}-1)}\right)=\frac{\frac{\partial
C}{\partial x_{j}}(x)r(x)(r(x)x_{j}^{2}-1)-C(x)\frac{\partial r}{\partial
x_{j}}(x)\left(2r(x)x_{j}^{2}-1\right)-2C(x)r(x)^{2}x_{j}}{\left(r(x)(r(x)x_{j}^{2}-1)\right)^{2}}$
$\displaystyle\frac{\partial}{\partial
x_{j}}\left(\frac{C(x)}{r(x)(r(x)x_{j}^{2}-1)}\right)_{x=1_{K-2}}=\left(\frac{1}{K-1}-1\right)\frac{2C(1_{K-2})}{(r(1_{K-2})-1)^{2}}\>,$

and, for $i\geq 3$ s.t. $i\neq j$,

$\displaystyle\frac{\partial}{\partial
x_{j}}\left(\frac{C(x)}{r(x)(r(x)x_{i}^{2}-1)}\right)=\frac{\frac{\partial
C}{\partial x_{j}}(x)r(x)(r(x)x_{i}^{2}-1)-C(x)\frac{\partial r}{\partial
x_{j}}(x)\left(2r(x)x_{i}^{2}-1\right)}{\left(r(x)(r(x)x_{i}^{2}-1)\right)^{2}}$
$\displaystyle\frac{\partial}{\partial
x_{j}}\left(\frac{C(x)}{r(x)(r(x)x_{i}^{2}-1)}\right)_{x=1_{K-2}}=\frac{1}{K-1}\frac{2C(1_{K-2})}{(r(1_{K-2})-1)^{2}}\>.$

Then, plugging everything together, we obtained that

$\displaystyle\frac{\partial\Omega}{\partial
x_{j}}(1_{K-2})=\frac{2C(1_{K-2})}{(r(1_{K-2})-1)^{2}}\left(\frac{1}{K-1}+\frac{1}{K-1}-1+\sum_{i\geq
3,i\neq j}\frac{1}{K-1}\right)=0\>.$

Therefore, we have shown that $\nabla\Omega(1_{K-2})=0_{K-2}$. ∎

##  Appendix D Non-Asymptotic Analysis

In Appendix D.1, we state and prove one key result for each one of the three
main components of the TTUCB sampling rule: the UCB leader (Lemma D.1), the TC
challenger (Lemma D.2) and the tracking (Lemma D.3). The proof of Theorem 2.4
is detailed in Appendix D.2, which uses the stopping rule (1) and a proof
method from (Locatelli et al., 2016). It is a direct consequence of a more
general result (Theorem D.4). In Appendix D.3, we prove a non-asymptotic upper
bound for the TTUCB when using $g_{m}$ instead of $g_{u}$ (Corollary D.5). We
compare our results with uniform sampling in Appendix D.4 (Theorem D.6). Other
technicalities are gathered in Appendix D.5.

###  D.1 Key Properties

Before delving in the proof of Theorem D.4 itself, we present the key
properties of each component of the TTUCB sampling rule under a some
concentration event.

Let $\alpha>1$ and $s>1$. Let $(\mathcal{E}_{n})_{n>K}$ be the sequence of
concentration events defined as
$\mathcal{E}_{n}:=\mathcal{E}_{1,n}\cap\mathcal{E}_{2,n}$ for all $n>K$ where
$\mathcal{E}_{1,n}$ and $\mathcal{E}_{2,n}$ are defined in (18) and (20) as

$\displaystyle\mathcal{E}_{1,n}$ $\displaystyle:=\left\\{\forall
k\in[K],\forall
t\in[n^{1/\alpha},n],\>|\mu_{t,k}-\mu_{k}|<\sqrt{\frac{g_{u}(t)}{N_{t,k}}}\right\\}\>,$
$\displaystyle\mathcal{E}_{2,n}$ $\displaystyle:=\left\\{\forall k\neq
i^{\star},\forall
t\in[n^{1/\alpha},n],\>(\mu_{t,i^{\star}}-\mu_{t,k})-(\mu_{i^{\star}}-\mu_{k})>-\sqrt{2\alpha(2+s)\log(t)\left(\frac{1}{N_{t,i^{\star}}}+\frac{1}{N_{t,k}}\right)}\right\\}\>,$

with $g_{u}(n)=2\alpha(1+s)\log n$. In Lemma E.6, it is shown that
$\sum_{n>K}\mathbb{P}(\mathcal{E}_{n}^{\complement})\leq(2K-1)\zeta(s)$.

##### UCB Leader

Lemma D.1 shows that the UCB leader is different from $i^{\star}$ for only a
sublinear number of times under a certain concentration event. It is slightly
more general than Lemma 3.2 presented in Section 2.

######  Lemma D.1.

Let $(\mathcal{E}_{1,n})_{n}$ and $g_{u}$ as in Lemma E.2. Let
$H(\mu)=\sum_{i\neq
i^{\star}(\mu)}\frac{2}{(\mu_{i^{\star}(\mu)}-\mu_{i})^{2}}$. For all $n>K$,
under the event $\mathcal{E}_{1,n}$,

$\forall t\in[n^{1/\alpha},n],\quad L_{t,i^{\star}}\geq
t-1-2H(\mu)g_{u}(t)/\beta-K/\beta\>,$ (7)

Let $(\mathcal{E}_{3,n})_{n}$ and $g_{m}$ as in Lemma E.3. Under the event
$\mathcal{E}_{3,n}$, (7) holds by using $g_{m}$ instead of $g_{u}$.

###### Proof.

Suppose that at time $t\in[n^{1/\alpha},n]$, the UCB leader is different from
$i^{\star}$, i.e. $B_{t}=k\neq i^{\star}$. Using the event $\mathcal{E}_{1,n}$
and the definition of $B_{t}$ yields

$\displaystyle\mu_{i^{\star}}\leq\mu_{t,i^{\star}}+\sqrt{\frac{g_{u}(t)}{N_{t,i^{\star}}}}\leq\mu_{t,k}+\sqrt{\frac{g_{u}(t)}{N_{t,k}}}\leq\mu_{k}+\sqrt{\frac{4g_{u}(t)}{N_{t,k}}}\>.$

We get that if $t\geq n^{1/\alpha}$, then
$N_{t,k}\leq\frac{4g_{u}(t)}{(\mu_{i^{\star}}-\mu_{k})^{2}}$. Therefore, we
obtain the following upper bound on the number of times the leader is
different from $i^{\star}$ up to time $t$

$t-1-L_{t,i^{\star}}=\sum_{k\neq
i^{\star}}L_{t,k}\leq\frac{1}{\beta}\sum_{k\neq
i^{\star}}N_{t,k}^{k}+\frac{K-1}{2\beta}\leq\frac{1}{\beta}\sum_{k\neq
i^{\star}}N_{t,k}+\frac{K-1}{2\beta}\leq\sum_{k\neq
i^{\star}}\frac{4g_{u}(t)}{(\mu_{i^{\star}}-\mu_{k})^{2}\beta}+\frac{K-1}{2\beta}\>,$

where we used Lemma D.3 for the second inequality and $N^{k}_{t,k}\leq
N_{t,k}$ for the third. This concludes the proof for $g_{u}$. The same
reasoning can be applied for $g_{m}$. ∎

##### TC Challenger

Lemma D.2 shows a lower bound on the “transportation” costs used by the TC
challenger provided a certain concentration holds. This lower bound depends
only on the empirical counts when the best arm is the leader.

######  Lemma D.2.

For all $n>K$, under the event $\mathcal{E}_{2,n}$, for all
$t\in[n^{1/\alpha},n]$ such that $B_{t}=i^{\star}$,

$\forall k\neq
i^{\star},\quad\frac{\mu_{t,B_{t}}-\mu_{t,k}}{\sqrt{1/N_{t,B_{t}}+1/N_{t,k}}}\geq\frac{\mu_{i^{\star}}-\mu_{k}}{\sqrt{1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,k}^{i^{\star}}}}-\sqrt{2\alpha(2+s)\log
n}\>.$

###### Proof.

Under $\mathcal{E}_{2,n}$, using $B_{t}=i^{\star}$ yields

$\displaystyle\frac{\mu_{t,B_{t}}-\mu_{t,k}}{\sqrt{1/N_{t,B_{t}}+1/N_{t,k}}}\geq\frac{\mu_{i^{\star}}-\mu_{k}}{\sqrt{1/N_{t,i^{\star}}+1/N_{t,k}}}-\sqrt{2\alpha(2+s)\log
t}\geq\frac{\mu_{i^{\star}}-\mu_{k}}{\sqrt{1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,k}^{i^{\star}}}}-\sqrt{2\alpha(2+s)\log
n}\>,$

where the second inequality uses that $N_{t,k}\geq N^{i^{\star}}_{t,k}$ for
all $k\neq i^{\star}$. ∎

##### Tracking

Lemma D.3 shows the key property satisfied by the $K$ independent tracking
procedures used by the TTUCB sampling rule. It is slightly more general than
Lemma 2.2 presented in Section 2. It is a simple corollary of Theorem 6 in
(Degenne et al., 2020).

######  Lemma D.3.

For all $n>K$ and $i\in[K]$, we have $-1/2\leq N_{n,i}^{i}-\beta L_{n,i}\leq
1$ and for all $k\neq i$,

$N_{n,i}^{i}\geq\frac{\beta}{1-\beta}N_{n,k}^{i}-\frac{1}{2}\frac{1}{1-\beta}\>.$

###### Proof.

We can rewrite the tracking condition $N_{n,B_{n}}^{B_{n}}\leq\beta
L_{n+1,B_{n}}$ as

$N_{n,B_{n}}^{B_{n}}-\beta
L_{n+1,B_{n}}\leq(L_{n+1,B_{n}}-N_{n,B_{n}}^{B_{n}})-(1-\beta)L_{n+1,B_{n}}\>.$

For all $k\in[K]$, this corresponds to a two-arms C-Tracking between the
leader $k$ and the challengers with $w_{n}=(\beta,1-\beta)$ for all $n$ such
that $B_{n}=k$. The leader’s pulling count is $N_{n,B_{n}}^{B_{n}}$ and the
challengers’ pulling count is $L_{n+1,B_{n}}-N_{n,B_{n}}^{B_{n}}$. We recall
that C-Tracking was defined as
$I_{n}=\operatorname*{arg\,min}_{k\in[K]}N_{n,k}-\sum_{t\in[n]}w_{t,k}$.

Theorem 6 in (Degenne et al., 2020) yields for all $n>K$, $-\frac{1}{2}\leq
N_{n,B_{n}}^{B_{n}}-\beta L_{n,B_{n}}\leq 1$. The $K$ parallel tracking
procedures are independent since they are considering counts partitioned on
the considered leader. Therefore, the above results holds for all $i\in[K]$.
This concludes the first part of the proof.

Direct manipulations yield the second part of the result, namely

$\displaystyle N_{n,k}^{i}\leq
L_{n,i}-N_{n,i}^{i}\leq(1-\beta)L_{n,i}+\frac{1}{2}\quad\text{and}\quad
N_{n,i}^{i}\geq-\frac{1}{2}+L_{n,i}\beta\geq\frac{\beta}{1-\beta}(N_{n,k}^{i}-\frac{1}{2})-\frac{1}{2}\>.$

∎

The choice of $K$ independent tracking procedures was made for two reasons.
First, independent procedures are simpler to analyze for theoretical purpose.
Second, independent procedures yields better empirical performance since it
avoids over-sampling a sub-optimal arm when it is mistakenly chosen as leader.
To understand the second argument, let’s look at another design with one
tracking procedure. Namely we set $I_{n}=B_{n}$ if $N_{n,B_{n}}\leq\beta n$,
else $I_{n}=C_{n}$. When $B_{n}\neq i^{\star}$, then it will (almost always)
take $I_{n}=B_{n}$ since $N_{n,B_{n}}$ is lower than $\beta n$. On the other
hand, when $B_{n}\neq i^{\star}$ with $K$ independent tracking procedures,
both $N_{n,B_{n}}^{B_{n}}$ and $L_{n,B_{n}}$ are small, hence it is less
systematic.

###  D.2 Proof of Theorem 2.4

Theorem 2.4 is a direct corollary of Theorem D.4, which holds for any
$\beta\in(0,1)$, $s>1$ and $\alpha>1$.

######  Theorem D.4.

Let $(\delta,\beta)\in(0,1)^{2}$, $s>1$ and $\alpha>1$. Using the threshold
(2) in (1) and $g_{u}$ in (3), the TTUCB algorithm satisfies that, for all
$\mu\in\mathbb{R}^{K}$ such that $|i^{\star}(\mu)|=1$,

$\mathbb{E}_{\mu}[\tau_{\delta}]\leq\max\left\\{T_{0}(\delta),C_{\mu}^{\alpha},C_{0}^{\frac{\alpha}{\alpha-1}},C_{1}^{\alpha}\right\\}+C_{2}\>,$

where

$\displaystyle T_{0}(\delta)=\sup\left\\{n>K\mid n-1\leq
T_{\beta}^{\star}(\mu)\frac{(1+\varepsilon)^{2}}{\beta(1-w_{0})^{d_{\mu}(w_{0})}}(\sqrt{c(n-1,\delta)}+\sqrt{\alpha(2+s)\log
n})^{2}\right\\}\>,$ $\displaystyle
C_{\mu}=h_{1}\left(4\alpha^{2}(1+s)H(\mu)/\beta\right)\>,\quad
C_{0}=\frac{2}{\varepsilon a_{\mu}(w_{0})}+1\>,\quad
C_{1}=1/(\beta\varepsilon)\>,\quad C_{2}=(2K-1)\zeta(s)+1\>,$ $\displaystyle
a_{\mu}(w_{0})=(1-w_{0})^{d_{\mu}(w_{0})}\max\\{\min_{i\neq
i^{\star}(\mu)}w_{\beta}^{\star}(\mu)_{i},(1-\beta)w_{0}\\}\>,\quad
d_{\mu}(w_{0})=|\\{i\in[K]\setminus\\{i^{\star}(\mu)\\}\mid\>w_{\beta}^{\star}(\mu)_{i}<(1-\beta)w_{0}\\}|\>,$

with $\varepsilon\in(0,1]$, $w_{0}\in[0,1/(K-1)]$ and $\zeta$ is the Riemann
$\zeta$ function. For all $x>0$, the function
$h_{1}(x):=x\overline{W}_{-1}\left(\log(x)+\frac{2+K/\beta}{x}\right)$ is
positive, increasing for $x\geq 2+K/\beta$, and satisfies $h_{1}(x)\approx
x(\log x+\log\log x)$.

Let $n>K$ such that $\mathcal{E}_{n}$ holds true and the algorithm has not
stop yet, i.e. $\mathcal{E}_{n}\cap\\{n<\tau_{\delta}\\}$. Let
$t\in[n^{1/\alpha},n]$ such that $B_{t}=i^{\star}$. Let $c(n,\delta)$ as in
(2), which satisfies that $n\mapsto c(n,\delta)$ is increasing. Using the
stopping rule (1) and $t\leq n<\tau_{\delta}$, we obtain

$\displaystyle\sqrt{2c(n-1,\delta)}\geq\sqrt{2c(t-1,\delta)}\geq\min_{i\neq\hat{\imath}_{t}}\frac{\mu_{t,\hat{\imath}_{t}}-\mu_{t,i}}{\sqrt{1/N_{t,\hat{\imath}_{t}}+1/N_{t,i}}}\geq\min_{i\neq
B_{t}}\frac{(\mu_{t,B_{t}}-\mu_{t,i})_{+}}{\sqrt{1/N_{t,B_{t}}+1/N_{t,i}}}=\frac{(\mu_{t,B_{t}}-\mu_{t,C_{t}})_{+}}{\sqrt{1/N_{t,B_{t}}+1/N_{t,C_{t}}}}\>,$

The last inequality is an equality when $B_{t}=\hat{\imath}_{t}$, and
trivially true when $B_{t}\neq\hat{\imath}_{t}$ since a positive term is
higher than zero (already null when taking $i=\imath_{t}$). Using Lemma D.2,
we obtain

$\displaystyle\frac{\mu_{t,B_{t}}-\mu_{t,C_{t}}}{\sqrt{1/N_{t,B_{t}}+1/N_{t,C_{t}}}}$
$\displaystyle\geq\frac{\mu_{i^{\star}}-\mu_{C_{t}}}{\sqrt{1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,C_{t}}^{i^{\star}}}}-\sqrt{2\alpha(2+s)\log
n}$
$\displaystyle\geq\sqrt{\frac{1/\beta+1/w^{\star}_{\beta,C_{t}}}{1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,C_{t}}^{i^{\star}}}}\min_{i\neq
i^{\star}}\frac{\mu_{i^{\star}}-\mu_{i}}{\sqrt{1/\beta+1/w^{\star}_{\beta,i}}}-\sqrt{2\alpha(2+s)\log
n}$
$\displaystyle\geq\sqrt{\frac{1/\beta+1/w^{\star}_{\beta,C_{t}}}{1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,C_{t}}^{i^{\star}}}}\sqrt{2T^{\star}_{\beta}(\mu)^{-1}}-\sqrt{2\alpha(2+s)\log
n}\>,$

where the second inequality is obtained by artificially making appear
$1/\beta+1/w^{\star}_{\beta,C_{t}}$ and taking the minimum of $i\neq
i^{\star}$. The last inequality simply uses the definition of
$w^{i^{\star}}_{\beta}$.

While combining Lemma D.1 and Lemma D.3 links
$N_{t,i^{\star}}^{i^{\star}}/(t-1)$ with $\beta$, we need another argument to
compare the empirical allocation $N_{t,C_{t}}^{i^{\star}}/(t-1)$ of the sub-
optimal arm $C_{t}$ with its $\beta$-optimal allocation
$w^{\star}_{\beta,C_{t}}$. Before delving into this key argument, we conclude
the proof under an assumption that will be shown to hold later: there exists
$D_{0}>0$ and $T_{\mu}>0$ such that for all $n>T_{\mu}$, there exists a well
chosen $t\in[n^{1/\alpha},n]$ with $B_{t}=i^{\star}$, which satisfies

$1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,C_{t}}^{i^{\star}}\leq\frac{D_{0}}{n-1}\left(1/\beta+1/w^{\star}_{\beta,C_{t}}\right)\>.$
(8)

Let’s define

$T(\delta,D_{0}):=\sup\left\\{n>K\mid n-1\leq
T_{\beta}^{\star}(\mu)D_{0}\left(\sqrt{c(n-1,\delta)}+\sqrt{\alpha(2+s)\log
n}\right)^{2}\right\\}\>.$

For all $n>\max\\{T_{\mu},T(1,D_{0})\\}$, the lower bound on
$\frac{\mu_{t,B_{t}}-\mu_{t,C_{t}}}{\sqrt{1/N_{t,B_{t}}+1/N_{t,C_{t}}}}$ is
positive, hence we can use that it is upper bounded by
$\sqrt{2c(n-1,\delta)}$. Putting everything together, we have shown that

$\forall n>\max\\{T_{\mu},T(1,D_{0})\\},\quad n-1\leq
T^{\star}_{\beta}(\mu)D_{0}\left(\sqrt{c(n-1,\delta)}+\sqrt{\alpha(2+s)\log
n}\right)^{2}\>.$

Therefore, we have $\mathcal{E}_{n}\cap\\{n<\tau_{\delta}\\}=\emptyset$ (i.e.
$\mathcal{E}_{n}\subset\\{\tau_{\delta}\leq n\\}$) for all
$n\geq\max\\{T(\delta,D_{0}),T(1,D_{0}),T_{\mu}\\}+1$. Using that $\delta\to
T(\delta,D_{0})$ is an decreasing function (since $\mathcal{C}_{G}$ is
increasing), we obtain that
$T(\delta,D_{0})=\max\\{T(\delta,D_{0}),T(1,D_{0})\\}$.

Combining Lemmas D.8 and E.6 yields

$\displaystyle\mathbb{E}_{\mu}[\tau_{\delta}]\leq\max\\{T(\delta,D_{0}),T_{\mu}\\}+1+\sum_{n\geq
1}\mathbb{P}_{\mu}(\mathcal{E}_{n}^{\complement})\leq\max\\{T(\delta,D_{0}),T_{\mu}\\}+1+(2K-1)\zeta(s)\>.$

At this stage, the proof of Theorem D.4 boils down to exhibiting $D_{0}>0$ and
$T_{\mu}>0$ such that: for all $n>T_{\mu}$, there exists a well chosen
$t\in[n^{1/\alpha},n]$ with $B_{t}=i^{\star}$ and such that (8) holds. As
mentioned above, the crux of the problem is to relate
$N_{t,C_{t}}^{i^{\star}}/(t-1)$ and $w^{\star}_{\beta,C_{t}}$. To do so, we
will build on the idea behind the proof for APT from Locatelli et al. (2016):
consider an arm being over-sampled and study the last time this arm was
pulled.

By the pigeonhole principle, at time $n$, there is an index $k_{1}\neq
i^{\star}$ such that (5) holds, i.e.

$N_{n,k_{1}}^{i^{\star}}\geq\frac{w^{\star}_{\beta,k_{1}}}{1-\beta}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})\>,$

and we take such $k_{1}$. Let
$t_{1}:=\sup\left\\{t<n\mid(B_{t},C_{t})=(i^{\star},k_{1})\right\\}$ be the
last time at which $i^{\star}$ was the leader and $k_{1}$ was the challenger.
If $I_{t_{1}}=B_{t_{1}}$ then
$N_{t_{1},k_{1}}^{i^{\star}}=N_{n,k_{1}}^{i^{\star}}$, else
$N_{t_{1},k_{1}}^{i^{\star}}=N_{n,k_{1}}^{i^{\star}}-1$. In both cases, we
have $N_{t_{1},k_{1}}^{i^{\star}}\geq N_{n,k_{1}}^{i^{\star}}-1$. Let $f_{1}$
as in (15). Combined the above with Lemma D.9, we obtain

$N_{t_{1},k_{1}}^{i^{\star}}\geq
N_{n,k_{1}}^{i^{\star}}-1\geq\frac{w^{\star}_{\beta,k_{1}}}{1-\beta}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})-1\geq
w^{\star}_{\beta,k_{1}}(n-1)-f_{1}(n)\>.$

Let $w_{-}>0$ be a lower bound on $w^{\star}_{\beta,k_{1}}$, for example
consider $w_{-}=\min_{i\neq i^{\star}}w^{\star}_{\beta,i}$. Let

$C_{0}(w_{-})=\sup\left\\{n\geq 1\mid
n-1<\frac{1}{w_{-}}\left(n^{1/\alpha}+f_{1}(n)\right)\right\\}\>.$ (9)

Since $t_{1}-1\geq N^{i^{\star}}_{t_{1},k_{1}}\geq
w^{\star}_{\beta,k_{1}}(n-1)-f_{1}(n)$, we obtain that $t_{1}\geq
n^{1/\alpha}$ for all $n>N_{0}(w_{-})$. For instances $\mu$ such that
$w^{\star}_{\beta,k_{1}}$ is small, the equation (5) can be satisfied at the
very beginning, hence $t_{1}$ might be sublinear in $n$. Therefore, while
combining Lemma D.1 and Lemma D.3 yields
$N_{t_{1},i^{\star}}^{i^{\star}}\gtrapprox\beta(t_{1}-1)$, it is not possible
to obtain $N_{t_{1},i^{\star}}^{i^{\star}}\gtrapprox\beta(n-1)$. Due to the
missing link between $t_{1}$ and $n$, we use the following inequality

$\displaystyle
1/N_{t_{1},i^{\star}}^{i^{\star}}+1/N_{t_{1},k_{1}}^{i^{\star}}\leq\frac{1}{n-1}\left(1/\beta+\frac{n-1}{N_{t_{1},k_{1}}^{i^{\star}}}\right)\left(\frac{N_{t_{1},k_{1}}^{i^{\star}}}{N_{t_{1},i^{\star}}^{i^{\star}}}+1\right)\>,$

which is a suboptimal step which artificially introduces $1/\beta$, and is
responsible for the multiplicative factor $1/\beta$ in Theorem D.4. Improving
on this suboptimal step is an interesting question, whose answer still eludes
us. One idea would be to leverage the information of the sampled arm at time
$t$ since we have $N_{t,i^{\star}}^{i^{\star}}\leq\beta L_{t+1,i^{\star}}$
when $i^{\star}=B_{t}=I_{t}$, else $N_{t,i^{\star}}^{i^{\star}}\geq\beta
L_{t+1,i^{\star}}$.

Let $\varepsilon\in(0,1]$. It remains to control both terms. First, we obtain

$\displaystyle 1/\beta+\frac{n-1}{N_{t_{1},k_{1}}^{i^{\star}}}\leq
1/\beta+\frac{1}{w^{\star}_{\beta,k_{1}}-f_{1}(n)/(n-1)}\leq(1+\varepsilon)\left(1/\beta+1/w^{\star}_{\beta,k_{1}}\right)\>,$

for all $n>C_{1}(w_{-})$. The last inequality is obtained by definition of

$C_{1}(w_{-})=\sup\left\\{n\geq 1\mid
n-1<\frac{f_{1}(n)}{w_{-}}\left(1+\frac{1}{\varepsilon}\right)\right\\}\>,$
(10)

which ensures that, for all $n>C_{1}(w_{-})$, the last condition of the
equivalence

$\displaystyle
w^{\star}_{\beta,k_{1}}-f_{1}(n)/(n-1)\geq(1+\varepsilon)^{-1}w^{\star}_{\beta,k_{1}}\quad\iff\quad
n-1\geq\frac{f_{1}(n)}{w^{\star}_{\beta,k_{1}}}\left(1+\frac{1}{\varepsilon}\right)$

is satisfied since $w^{\star}_{\beta,k_{1}}\geq w_{-}$ and $n>C_{1}(w_{-})$.
Second, using Lemma D.3 with $N_{t_{1},k_{1}}^{i^{\star}}\geq
w^{\star}_{\beta,k_{1}}(n-1)-f_{1}(n)$, we obtain

$\displaystyle\frac{N_{t_{1},k_{1}}^{i^{\star}}}{N_{t_{1},i^{\star}}^{i^{\star}}}+1\leq\left(\frac{\beta}{1-\beta}-\frac{1}{2(1-\beta)\left(w^{\star}_{\beta,k_{1}}(n-1)-f_{1}(n)\right)}\right)^{-1}+1\leq(1+\varepsilon)/\beta\>,$

for all $n>C_{2}(w_{-})$. The last inequality is obtained by definition of

$C_{2}(w_{-}):=\sup\left\\{n\in\mathbb{N}^{\star}\mid
n-1<\frac{1}{w_{-}}\left(f_{1}(n)+\frac{1-\beta+\varepsilon}{2\beta\varepsilon}\right)\right\\}\>,$
(11)

which ensures that, for all $n>C_{2}(w_{-})$, the last condition of the
equivalence

$\displaystyle\left(\frac{\beta}{1-\beta}-\frac{1}{2(1-\beta)\left(w^{\star}_{\beta,k_{1}}(n-1)-f_{1}(n)\right)}\right)^{-1}+1\leq(1+\varepsilon)/\beta$
$\displaystyle\iff\>\frac{1}{w^{\star}_{\beta,k_{1}}(n-1)-f_{1}(n)}\leq\frac{2\beta\varepsilon}{1-\beta+\varepsilon}\iff\>n-1\geq\frac{1}{w^{\star}_{\beta,k_{1}}}\left(f_{1}(n)+\frac{1-\beta+\varepsilon}{2\beta\varepsilon}\right)$

is satisfied since $w^{\star}_{\beta,k_{1}}\geq w_{-}$ and $n>C_{2}(w_{-})$.
By comparison between (9) and (11), we notice that

$\max\left\\{C_{0}(w_{-}),C_{2}(w_{-})\right\\}\leq\max\left\\{C_{0}(w_{-}),\left(\frac{1-\beta+\varepsilon}{2\beta\varepsilon}\right)^{\alpha}\right\\}$

Putting everything together, we have shown that taking
$D_{0}=(1+\varepsilon)^{2}/\beta$, we have for all
$n>\max\\{K,C_{0}(w_{-}),C_{1}(w_{-}),C_{2}(w_{-})\\}$, there exists
$t_{1}\in[n^{1/\alpha},n]$ with $B_{t_{1}}=i^{\star}$ and such that (8) holds.
Let $h_{1}$ defined in (16). Since $\varepsilon\leq 1$, using Lemmas D.10 and
D.11 with the above yields

$\max\\{C_{0}(w_{-}),C_{1}(w_{-}),C_{2}(w_{-})\\}\leq\max\left\\{h_{1}\left(4\alpha^{2}(1+s)H(\mu)\right),\left(\frac{2}{\varepsilon
w_{-}}+1\right)^{1/(\alpha-1)},\frac{1}{\beta\varepsilon}\right\\}^{\alpha}\>.$

Using $w_{-}=\min_{i\neq i^{\star}}w^{\star}_{\beta,i}$ yields the first part
of Theorem D.4, i.e. the special case of $w_{0}=0$.

##### Refined Non-Asymptotic Upper Bound

When considering large $K$ or instances with unbalanced $\beta$-optimal
allocation, $\min_{i\neq i^{\star}}w^{\star}_{\beta,i}$ can become arbitrarily
small. Therefore, the dependency in the inverse of $\min_{i\neq
i^{\star}}w^{\star}_{\beta,i}$ is undesired, and we would like to clip it with
a value of our choosing which is away from zero.

Let $w_{0}\in(0,1/(K-1)]$ be an allocation threshold and
$d_{\mu}(w_{0}):=|\\{i\in[K]\setminus\\{i^{\star}\\}\mid\>w^{\star}_{\beta,i}<(1-\beta)w_{0}\\}|$
be the number of arms having a $\beta$-optimal allocation strictly smaller
than $(1-\beta)w_{0}$. As discussed above, for instances $\mu$ such that
$w^{\star}_{\beta,k_{1}}$ (defined above) is small, the equation (5) can be
satisfied at the very beginning for a small empirical allocation
$N_{n,k_{1}}^{i^{\star}}$. To provide a more meaningful result, one needs to
have a sub-optimal arm $k_{1}$ such that either:

  * •

Case 1: $w^{\star}_{\beta,k_{1}}$ is not too small, i.e.
$w^{\star}_{\beta,k_{1}}\geq(1-\beta)w_{0}$.

  * •

Case 2: $w^{\star}_{\beta,k_{1}}$ is too small but $N_{n,k_{1}}^{i^{\star}}$
is large enough, i.e. $w^{\star}_{\beta,k_{1}}<(1-\beta)w_{0}$ and
$N_{n,k_{1}}^{i^{\star}}\geq
w_{0}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})$.

In case 1, we can conduct the same manipulations as above simply by using
$w_{-}=\max\\{(1-\beta)w_{0},\min_{i\neq i^{\star}}w^{\star}_{\beta,i}\\}$
instead of $w_{-}=\min_{i\neq i^{\star}}w^{\star}_{\beta,i}$, since it is a
lower bound for $w^{\star}_{\beta,k_{1}}$.

In case 2, the above proof can also be applied by conducting the same
algebraic manipulations with $(1-\beta)w_{0}$ instead of
$w^{\star}_{\beta,k_{1}}$, and using
$w_{-}=(1-\beta)w_{0}=\max\\{(1-\beta)w_{0},\min_{i\neq
i^{\star}}w^{\star}_{\beta,i}\\}$. To slightly detail the argument, we can
show similarly that
$N_{t_{1},k_{1}}^{i^{\star}}\geq(1-\beta)w_{0}(n-1)-f_{1}(n)$, where $f_{1}$
as in (15) since we have $(1-\beta)w_{0}<1-\beta$. Then, for all
$n>C_{1}((1-\beta)w_{0})$,

$\displaystyle
1/\beta+\frac{n-1}{N_{t_{1},k_{1}}^{i^{\star}}}\leq(1+\varepsilon)\left(1/\beta+\frac{1}{(1-\beta)w_{0}}\right)\leq(1+\varepsilon)\left(1/\beta+1/w^{\star}_{\beta,k_{1}}\right)\>.$

The problematic situation happens when we are neither in case 1 nor in case 2:

  * •

Case 3: both $w^{\star}_{\beta,k_{1}}$ and $N_{n,k_{1}}^{i^{\star}}$ are too
small, i.e. $w^{\star}_{\beta,k_{1}}<(1-\beta)w_{0}$ and
$N_{n,k_{1}}^{i^{\star}}<w_{0}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})$.

In case 3 it is not possible to conclude the proof with the arm $k_{1}$
without paying the price of an inverse of $\min_{i\neq
i^{\star}}w^{\star}_{\beta,i}$. To overcome this price, we need to find
another arm $k$ such that either case 1 or case 2 happens. Since
$N_{n,k_{1}}^{i^{\star}}$ and $w^{\star}_{\beta,k_{1}}$ are small, we will
ignore arm $k_{1}$ and use the pigeonhole principle on all arm
$i\in[K]\setminus\\{i^{\star},k_{1}\\}$. As in (5), we obtain that there
exists $k_{2}$ such that

$\displaystyle
N_{n,k_{2}}^{i^{\star}}\geq\frac{w^{\star}_{\beta,k_{2}}}{1-\beta-w^{\star}_{\beta,k_{1}}}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}-N_{n,k_{1}}^{i^{\star}})\geq\frac{(1-w_{0})w^{\star}_{\beta,k_{2}}}{1-\beta}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})\>,$

where the last inequality is obtained by using $w^{\star}_{\beta,k_{1}}>0$ and
$N_{n,k_{1}}^{i^{\star}}<w_{0}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})$.
Based on $k_{2}$ the same dichotomy happens: either we can conclude the proof
when we are in case 1 or 2 or we cannot since we are in case 3. If case 3
occurs also for $k_{2}$, i.e. $w^{\star}_{\beta,k_{2}}<(1-\beta)w_{0}$ and
$N_{n,k_{2}}^{i^{\star}}<w_{0}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}-N_{n,k_{1}}^{i^{\star}})$,
we should also ignore it since it is non informative.

The main idea is then to peel off arms that are not informative, till we find
an informative one. By induction, we construct a sequence $(k_{a})_{a\in[d]}$
of such arms, where $k_{d}$ is the first arm for which either case 1 or case 2
holds. This means that for all $a\in[d-1]$, we have
$w^{\star}_{\beta,k_{a}}<(1-\beta)w_{0}$ and

$N_{n,k_{a}}^{i^{\star}}<w_{0}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}-\sum_{b\in[a-1]}N_{n,k_{b}}^{i^{\star}})\>.$

The construction, which rely on the pigeonhole principle for
$i\in[K]\setminus\left(\\{i^{\star}\\}\cup\\{k_{a}\\}_{a\in[d-1]}\right)$,
yields that $k_{d}$ satisfies

$\displaystyle
N_{n,k_{d}}^{i^{\star}}\geq\frac{w^{\star}_{\beta,k_{d}}}{1-\beta-\sum_{a\in[d-1]}w^{\star}_{\beta,k_{a}}}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}-\sum_{a\in[d-1]}N_{n,k_{a}}^{i^{\star}})\geq\frac{(1-w_{0})^{d-1}w^{\star}_{\beta,k_{d}}}{1-\beta}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}})\>,$

where the last inequality is obtained since
$\sum_{a\in[d-1]}w^{\star}_{\beta,k_{a}}>0$ and by a simple recurrence on the
arms $\\{k_{a}\\}_{a\in[d-1]}$. Since the arm $k_{d}$ satisfies case 1 or case
2, we can conclude similarly as above. Let
$t_{d}:=\sup\left\\{t<n\mid(B_{t},C_{t})=(i^{\star},k_{d})\right\\}$.

When $w^{\star}_{\beta,k_{d}}\geq(1-\beta)w_{0}$, the above proof can also be
applied by conducting the same algebraic manipulations with
$(1-w_{0})^{d-1}w^{\star}_{\beta,k_{d}}$, and using
$w_{-}=(1-w_{0})^{d-1}\max\\{(1-\beta)w_{0},\min_{i\neq
i^{\star}}w^{\star}_{\beta,i}\\}$. In more details, we can show that
$N_{t_{d},k_{d}}^{i^{\star}}\geq(1-w_{0})^{d-1}w^{\star}_{\beta,k_{d}}(n-1)-f_{1}(n)$,
where $f_{1}$ as in (15) since we have
$(1-w_{0})^{d-1}w^{\star}_{\beta,k_{d}}<1-\beta$. Then, for all
$n>C_{1}(w_{-})$,

$\displaystyle
1/\beta+\frac{n-1}{N_{t_{d},k_{d}}^{i^{\star}}}\leq(1+\varepsilon)\left(1/\beta+\frac{1}{(1-w_{0})^{d-1}w^{\star}_{\beta,k_{d}}}\right)\leq\frac{1+\varepsilon}{(1-w_{0})^{d-1}}\left(1/\beta+1/w^{\star}_{\beta,k_{d}}\right)\>.$

This allow to conclude the result with
$D_{0}=\frac{(1+\varepsilon)^{2}}{\beta(1-w_{0})^{d-1}}$, hence paying a
multiplicative factor of $1/(1-w_{0})^{d-1}$.

When $w^{\star}_{\beta,k_{d}}<(1-\beta)w_{0}$ and $N_{n,k_{a}}^{i^{\star}}\geq
w_{0}(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}-\sum_{a\in[d-1]}N_{n,k_{a}}^{i^{\star}})$,
we conclude similarly by manipulating $(1-w_{0})^{d-1}(1-\beta)w_{0}$, and
using
$w_{-}=(1-w_{0})^{d-1}(1-\beta)w_{0}=(1-w_{0})^{d-1}\max\\{(1-\beta)w_{0},\min_{i\neq
i^{\star}}w^{\star}_{\beta,i}\\}$. First, we have
$N_{t_{d},k_{d}}^{i^{\star}}\geq(1-w_{0})^{d-1}w_{0}(n-1)-f_{1}(n)$, where
$f_{1}$ as in (15) since we have $(1-\beta)(1-w_{0})^{d-1}w_{0}<1-\beta$.
Then, for all $n>C_{1}(w_{-})$,

$\displaystyle
1/\beta+\frac{n-1}{N_{t_{d},k_{d}}^{i^{\star}}}\leq(1+\varepsilon)\left(1/\beta+\frac{1}{(1-w_{0})^{d-1}(1-\beta)w_{0}}\right)\leq\frac{1+\varepsilon}{(1-w_{0})^{d-1}}\left(1/\beta+1/w^{\star}_{\beta,k_{d}}\right)\>.$

This allow to conclude the result with
$D_{0}=\frac{(1+\varepsilon)^{2}}{\beta(1-w_{0})^{d-1}}$.

To remove the dependency in the random variable $d$, we consider the worst
case scenario where
$\\{k_{a}\\}_{a\in[d-1]}=\\{i\in[K]\setminus\\{i^{\star}\\}\mid\>w^{\star}_{\beta,i}<(1-\beta)w_{0}\\}$,
i.e. $d-1\leq d_{\mu}(w_{0})$. In words, it means that we had to enumerate
over all arms with small allocation, such that case 2 didn’t hold, before
finding an arm with large allocation, i.e. satisfying case 1.

In all the cases considered above, the parameters always satisfied
$w_{-}\geq(1-w_{0})^{d_{\mu}(w_{0})}\max\\{(1-\beta)w_{0},\min_{i\neq
i^{\star}}w^{\star}_{\beta,i}\\}$ and
$D_{0}\leq\frac{(1+\varepsilon)^{2}}{\beta(1-w_{0})^{d_{\mu}(w_{0})}}$. This
yields the second part of Theorem D.4, i.e. for $w_{0}\in(0,1/(K-1)]$.

###  D.3 Tighter UCB Leader

While Theorem 2.3 holds for the TTUCB sampling rule using $g_{m}$ and $g_{u}$,
Theorem D.4 is formulated solely for $g_{u}$. Experiments highlight that using
$g_{u}$ leads to worse performances than when using $g_{m}$. This is not
surprising since $g_{m}$ is smaller than $g_{u}$.

It is direct to see that the proof of Theorem D.4 also holds for $g_{m}$ up to
additional technicalities which we detail below. As the obtained non-
asymptotic upper bound is less explicit, we chose not to include it in Theorem
2.3.

Let $\alpha>1$ and $s>1$. Let $(\tilde{\mathcal{E}}_{n})_{n}$ be the sequence
of concentration events defined as
$\tilde{\mathcal{E}}_{n}:=\mathcal{E}_{3,n}\cap\mathcal{E}_{2,n}$ for all
$n>K$ where $\mathcal{E}_{3,n}$ is defined in (19) as

$\displaystyle\mathcal{E}_{3,n}$ $\displaystyle:=\left\\{\forall
k\in[K],\forall
t\in[n^{1/\alpha},n],\>|\mu_{t,k}-\mu_{k}|<\sqrt{\frac{g_{m}(t)}{N_{t,k}}}\right\\}\>,$
$\displaystyle g_{m}(n)$
$\displaystyle:=\overline{W}_{-1}\left(2s\alpha\log(n)+2\log(2+\alpha\log
n)+2\right)\>,$

where $\overline{W}_{-1}(x)=-W_{-1}(-e^{-x})$ for all $x\geq 1$, with $W_{-1}$
is the negative branch of the Lambert $W$ function.

Let $n>K$ such that $\tilde{\mathcal{E}}_{n}$ holds true and the algorithm has
not stop yet, i.e. $\tilde{\mathcal{E}}_{n}\cap\\{n<\tau_{\delta}\\}$. Using
the second part of Lemma D.1, the vast majority of the proof is unchanged.
Modifying the definition of $f_{1}$ in (15) of Lemma D.9 to account for
$g_{m}$, we define $f_{2}(n):=2H(\mu)g_{m}(n)/\beta+K/\beta+2$ for all $n>K$.

In light of the proofs of the technical Lemmas D.10 and D.11, we can define

$\tilde{C}_{\mu}=\sup\left\\{x\in\mathbb{N}^{\star}\mid
x<f_{2}(x^{\alpha})\right\\}\>,$

and obtain directly Corollary D.5 with the same proof as in Appendix D.2.

######  Corollary D.5.

Let $(\delta,\beta)\in(0,1)^{2}$, $\varepsilon\in(0,1]$, $s>1$, $\alpha>1$,
$w_{0}\in[0,1/(K-1)]$. Combining the stopping rule (1) with threshold (2) and
the TTUCB sampling rule using $g_{u}$ in (3) yields a $\delta$-correct
algorithm such that, for all $\mu\in\mathbb{R}^{K}$ with $|i^{\star}(\mu)|=1$,

$\mathbb{E}_{\mu}[\tau_{\delta}]\leq\max\left\\{T_{0}(\delta),\tilde{C}_{\mu}^{\alpha},C_{0}^{\frac{\alpha}{\alpha-1}},C_{1}^{\alpha}\right\\}+C_{2}\>,$

where $T_{0}(\delta)$, $C_{0}$, $C_{1}$ and $C_{2}$ are defined in Theorem
2.3, and

$\tilde{C}_{\mu}:=\sup\left\\{x\in\mathbb{N}^{\star}\mid
x<2H(\mu)g_{m}(x^{\alpha})/\beta+K/\beta+2\right\\}\>.$ (12)

##### Explicit Upper Bound

Since $g_{m}$ is itself a non-standard function (like logarithm), it is not
straightforward to obtain an explicit upper bound on (12). For $g_{u}$, it was
done in Lemma D.10 by using Lemma D.7.

Using Lemma D.7, we obtain that

$\displaystyle x\geq 2H(\mu)g_{m}(x^{\alpha})/\beta+K/\beta+2$
$\displaystyle\iff\>$
$\displaystyle\frac{x-c_{0}}{c_{\mu}}-\log\left(\frac{x-c_{0}}{c_{\mu}}\right)\geq
2s\alpha^{2}\log(x)+2\log(2+\alpha^{2}\log x)+2$ $\displaystyle\impliedby\>$
$\displaystyle
y-\log(y)\geq\frac{1}{s\alpha^{2}+1/2}\left(\log(2+\alpha^{2}\log
x)+\frac{c_{0}}{2c_{\mu}}\right)+\frac{s\alpha^{2}}{s\alpha^{2}+1/2}\log
c_{\mu}+c_{1}$ $\displaystyle\iff\>$ $\displaystyle x\geq h_{2}(c_{\mu},x)\>,$

where we used $y=\frac{x}{c_{\mu}(2s\alpha^{2}+1)}$,
$c_{1}=\log(2s\alpha^{2}+1)+\frac{1}{s\alpha^{2}+1/2}$, $c_{\mu}=2H(\mu)$,
$c_{0}=K/\beta+2$ and define

$h_{2}(z,x):=z(2s\alpha^{2}+1)\overline{W}_{-1}\left(\frac{1}{s\alpha^{2}+1/2}\left(s\alpha^{2}\log
z+\frac{c_{0}}{2z}+\log(2+\alpha^{2}\log x)\right)+c_{1}\right)\>.$ (13)

For both equivalences above, we used that we are interested in larger values
of $x$, hence we used that $\frac{x-c_{0}}{c_{\mu}}\geq 1$,
$\frac{x}{c_{\mu}(2s\alpha^{2}+1)}\geq 1$,
$2s\alpha^{2}\log(x)+2\log(2+\alpha^{2}\log x)+2\geq 1$ and
$\frac{1}{s\alpha^{2}+1/2}\left(s\alpha^{2}\log
c_{\mu}+\frac{c_{0}}{2c_{\mu}}+\log(2+\alpha^{2}\log x)\right)+c_{1}\geq 1$.
Since those conditions are implied by $x\geq h_{2}(c_{\mu},x)$, those
conditions are neither restrictive nor informative.

Therefore, we have shown that $\tilde{C}_{\mu}$ defined in (12) satisfies

$\tilde{C}_{\mu}\leq\sup\left\\{x\in\mathbb{N}^{\star}\mid
x<h_{2}\left(2H(\mu),x\right)\right\\}\>,$

where $h_{2}(z,x)$ is defined in (13) is such that
$h_{2}(z,x)\approx_{x}2z\log(2+\alpha^{2}\log x)$ and
$h_{2}(z,x)\approx_{z}2s\alpha^{2}z\log z$.

###  D.4 Uniform Sampling

While the shortcomings of uniform sampling are well known for general bandit
instances, it is also clear that uniform sampling perform well for highly
symmetric instances $\mu$ such that $w^{\star}(\mu)\approx\mathrm{1}_{K}/K$.
Therefore, we derive a non-asymptotic upper bound for uniform sampling
(Theorem D.6), which allow a clear comparison with Theorem D.4 (and Corollary
D.5).

######  Theorem D.6.

Let $\delta\in(0,1)$. Combining the stopping rule (1) with threshold (2) and
the uniform sampling rule yields a $\delta$-correct algorithm such that, for
all $\mu\in\mathbb{R}^{K}$ with $|i^{\star}(\mu)|=1$,

$\mathbb{E}_{\mu}[\tau_{\delta}]\leq\max\left\\{T_{1}(\delta),h_{3}\left(\frac{8\alpha
K(1+s)}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}\right)\right\\}+1+(2K-1)\zeta(s)\>,$
(14)

where $h_{3}(x)=x\overline{W}_{-1}(\log(x))$ for all $x\geq e$ and
$h_{3}(x)=x$ for all $x\in(0,e)$ and

$\displaystyle T_{1}(\delta)$ $\displaystyle=\sup\left\\{n>K\mid
n-1\leq\frac{4K}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}\left(\sqrt{c(n-1,\delta)}+\sqrt{\alpha(2+s)\log
n}\right)^{2}\right\\}\>.$

###### Proof.

Let $n>K$ such that $\mathcal{E}_{n}$ holds true and the algorithm has not
stop yet, i.e. $\mathcal{E}_{n}\cap\\{n<\tau_{\delta}\\}$. Let
$t:=\sup\left\\{t\in[n^{1/\alpha},n]\mid\>(t-1)/K\in\mathbb{N},\>\hat{\imath}_{t}=i^{\star}\right\\}$.
Using the stopping rule (1) and $t\leq n<\tau_{\delta}$, we obtain

$\displaystyle\sqrt{2c(n-1,\delta)}\geq\sqrt{2c(t-1,\delta)}\geq\min_{i\neq\hat{\imath}_{t}}\frac{\mu_{t,\hat{\imath}_{t}}-\mu_{t,i}}{\sqrt{1/N_{t,\hat{\imath}_{t}}+1/N_{t,i}}}=\frac{\mu_{t,\hat{\imath}_{t}}-\mu_{t,k_{t}}}{\sqrt{1/N_{t,\hat{\imath}_{t}}+1/N_{t,k_{t}}}}\>,$

where
$k_{t}=\operatorname*{arg\,min}_{i\neq\hat{\imath}_{t}}\frac{\mu_{t,\hat{\imath}_{t}}-\mu_{t,i}}{\sqrt{1/N_{t,\hat{\imath}_{t}}+1/N_{t,i}}}$.
Since we sample uniformly, for all time $t$ such that $(t-1)/K\in\mathbb{N}$,
we have $N_{t,i}=(t-1)/K$ for all $i\in[K]$. Combining the above with Lemma
D.2, we obtain

$\displaystyle\sqrt{2c(n-1,\delta)}+\sqrt{2\alpha(2+s)\log
n}\geq\frac{\mu_{i^{\star}}-\mu_{k_{t}}}{\sqrt{1/N_{t,i^{\star}}^{i^{\star}}+1/N_{t,k_{t}}^{i^{\star}}}}\geq\sqrt{\frac{t-1}{2K}}\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})\>,$

where the last inequality is obtained by taking the minimum over $i\in[K]$. To
conclude the proof, we simply have to link $t$ with $n$. More precisely, we
will show that $n-t\leq K-1$ and $\hat{\imath}_{t}=i^{\star}$ for $n$ large
enough. By concentration, we have

$\displaystyle\mu_{i}-\sqrt{\frac{Kg_{u}(t)}{t-1}}=\mu_{i}-\sqrt{\frac{g_{u}(t)}{N_{t,i}}}\leq\mu_{t,i}\leq\mu_{i}+\sqrt{\frac{g_{u}(t)}{N_{t,i}}}=\mu_{i}+\sqrt{\frac{Kg_{u}(t)}{t-1}}\>.$

Therefore, we have $\mu_{t,i^{\star}}>\max_{i\neq i^{\star}}\mu_{t,i}$, i.e.
$\hat{\imath}_{t}=i^{\star}$, for all $t>N_{3}$ where

$N_{3}:=\sup\left\\{n\in\mathbb{N}\mid n-1\leq\frac{4Kg_{u}(n)}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}\right\\}\>,$

which means that we have at worse $n-t\leq K-1$. For $n\geq N_{3}+K$, we
obtain $t\geq n-(K-1)>N_{3}$.

Let $c_{\mu}=\frac{8\alpha K(1+s)}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}$ and $x=n/c_{\mu}$. Assume that
$c_{\mu}\geq e$. Using the definition of $g_{u}$ and Lemma D.7, direct
manipulations yields

$\displaystyle n>\frac{4Kg_{u}(n)}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}\>\iff\>x-\log(x)>\log(c_{\mu})\>\iff\>x>\overline{W}_{-1}(\log(c_{\mu}))\>,$

where the last inequality uses that $\log(c_{\mu})\geq 1$ and $x\geq 1$, which
is not restrictive (or informative) since it is implied by
$x>\overline{W}_{-1}(\log(c_{\mu}))$. When $c_{\mu}<e$, which means that the
problem is easy, we have directly that $x-\log(x)>1>\log(c_{\mu})$ for $x>1$.
Therefore, the condition becomes $x>1$, i.e. $n\geq c_{\mu}$. Defining
$h_{3}(x)=x\overline{W}_{-1}(\log(x))$ for all $x\geq e$ and $h_{3}(x)=x$ for
all $x\in(0,e)$, we have

$N_{3}\leq h_{3}\left(\frac{8\alpha K(1+s)}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}\right)\>.$

Using a similar argument as the one in Appendix D.2 which rely on D.8 and the
definition of $T_{1}(\delta)$, we can conclude the proof. ∎

The structure of the non-asymptotic upper bound of uniform sampling in (14) is
similar to the one for the TTUCB sampling rule in Theorem D.4. Therefore, we
can compare the dominating terms for both the asymptotic and the non-
asymptotic regime.

First, we look at the asymptotic dominant term, namely we compare
$T_{0}(\delta)$ and $T_{1}(\delta)$. Taking $w=\mathrm{1}_{K}/K$ instead of
$w^{\star}(\mu)$ in the definition of $T^{\star}(\mu)$, it is direct to see
that $T^{\star}(\mu)\leq\frac{4K}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}$. Using Lemma C.1, we have
$T^{\star}_{\beta}(\mu)\leq
T^{\star}(\mu)\max\left\\{\frac{\beta^{\star}}{\beta},\frac{1-\beta^{\star}}{1-\beta}\right\\}$
where $\beta^{\star}=w^{\star}_{i^{\star}}(\mu)$. Therefore, while we can’t
say that
$T_{\beta}^{\star}(\mu)\frac{(1+\varepsilon)^{2}}{\beta(1-w_{0})^{d_{\mu}(w_{0})}}\leq\frac{4K}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}$ for all instances $\mu$, empirical
evidences suggest that the gap is significant for reasonable instances. It is
even possible to design instances where the gap between both notion of
complexity explodes.

Second, we examine the dominating $\delta$-independent term. Using Lemma D.7,
we obtain by concavity that for all $x>e$

$0<h_{1}(x)-h_{3}(x)\leq
2\overline{W}_{-1}^{\prime}(\log(x))=2\left(1-\frac{1}{\overline{W}_{-1}(\log(x))}\right)^{-1}\>,$

which yields that $\lim_{x\to+\infty}h_{1}(x)-h_{3}(x)\leq 2$. While those two
functions diverges when $x\to+\infty$, their difference remains bounded by a
finite quantity. Therefore, $h_{1}$ and $h_{3}$ are qualitatively similar. It
is direct to see that $\frac{2}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}<H(\mu)\leq\frac{2K}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}$ Therefore, while we can’t say that
$\alpha H(\mu)\leq\frac{2K}{\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}$ for all instances $\mu$, the gap can
become significant for some instances.

###  D.5 Technicalities

Lemma D.7 gathers properties on the function $\overline{W}_{-1}$ which we used
in this work.

######  Lemma D.7 (Jourdan et al. (2023)).

Let $\overline{W}_{-1}(x)=-W_{-1}(-e^{-x})$ for all $x\geq 1$, where $W_{-1}$
is the negative branch of the Lambert $W$ function. The function
$\overline{W}_{-1}$ is increasing on $(1,+\infty)$ and strictly concave on
$(1,+\infty)$. In particular,
$\overline{W}_{-1}^{\prime}(x)=\left(1-\frac{1}{\overline{W}_{-1}(x)}\right)^{-1}$
for all $x>1$. Then, for all $y\geq 1$ and $x\geq 1$,

$\overline{W}_{-1}(y)\leq x\quad\iff\quad y\leq x-\log(x)\>.$

Moreover, for all $x>1$,

$x+\log(x)\leq\overline{W}_{-1}(x)\leq
x+\log(x)+\min\left\\{\frac{1}{2},\frac{1}{\sqrt{x}}\right\\}\>.$

Lemma D.8 is a standard result to upper bound the expected sample complexity
of an algorithm.

######  Lemma D.8.

Let $(\mathcal{E}_{n})_{n>K}$ be a sequence of events and $T(\delta)>K$ be
such that for $n\geq T(\delta)$, $\mathcal{E}_{n}\subset\\{\tau_{\delta}\leq
n\\}$. Then, $\mathbb{E}_{\mu}[\tau_{\delta}]\leq
T(\delta)+\sum_{n>K}\mathbb{P}_{\mu}(\mathcal{E}_{n}^{\complement})$.

###### Proof.

$\displaystyle\mathbb{E}_{\mu}[\tau_{\delta}]=\sum_{n}\mathbb{P}_{\mu}(\tau_{\delta}>n)\leq\sum_{n<T(\delta)}\mathbb{P}_{\mu}(\tau_{\delta}>n)+\sum_{n\geq
T(\delta)}\mathbb{P}_{\mu}(\mathcal{E}_{n}^{\complement})\leq
T(\delta)+\sum_{n>K}\mathbb{P}_{\mu}(\mathcal{E}_{n}^{\complement})\>.$

∎

##### Technical Results

Lemma D.9 shows that a linear lower bound on the number of samples allocated
to the challenger, i.e.
$L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}\gtrapprox(1-\beta)(n-1)$.

######  Lemma D.9.

Let $w\in(0,1-\beta)$ and $(\mathcal{E}_{1,n})_{n}$ as in (18). For all
$n\in\mathbb{N}^{\star}$, under $\mathcal{E}_{1,n}$,

$\frac{w}{1-\beta}\left(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}\right)-1\geq(n-1)w-f_{1}(n)\>,$

where

$f_{1}(n)=2H(\mu)g_{u}(n)/\beta+K/\beta+2\>.$ (15)

###### Proof.

Using Lemma D.3, we obtain that, under $\mathcal{E}_{1,n}$,

$\displaystyle\frac{w}{1-\beta}\left(L_{n,i^{\star}}-N_{n,i^{\star}}^{i^{\star}}\right)-1=wL_{n,i^{\star}}-\frac{w}{1-\beta}-1$
$\displaystyle\geq w(n-1)-2H(\mu)g_{u}(n)/\beta-K/\beta-2\>.$

where the last inequality uses Lemma D.1 for $t=n$ and $w\in(0,1-\beta)$. ∎

Lemma D.10 gives an explicit upper bound on the constant $C_{0}(w_{-})$
defined implicitly in Appendix D.2.

######  Lemma D.10.

Let $w_{-}>0$ and $C_{0}(w_{-})$ as in (9). Then, we have

$\displaystyle
C_{0}(w_{-})\leq\max\left\\{h_{1}\left(4\alpha^{2}(1+s)H(\mu)/\beta\right),\left(\frac{2}{w_{-}}+1\right)^{1/(\alpha-1)}\right\\}^{\alpha}\>.$

where $h_{1}:\mathbb{R}_{+}^{\star}\to\mathbb{R}_{+}^{\star}$ is an increasing
function for $x\geq 2+K/\beta$ defined as

$h_{1}(x):=x\overline{W}_{-1}\left(\log(x)+\frac{2+K/\beta}{x}\right)\>.$ (16)

###### Proof.

Using the definition of $g_{u}$ and Lemma D.7, direct manipulations yields

$\displaystyle n^{1/\alpha}\geq f_{1}(n)\>\iff\>n^{1/\alpha}\geq
c_{\mu}\log(n^{1/\alpha})+2+K/\beta\>\iff\>x-\log(x)\geq
d_{\mu}\>\iff\>x\geq\overline{W}_{-1}\left(d_{\mu}\right)\>,$

where $x=n^{1/\alpha}/c_{\mu}$, $d_{\mu}=\log(c_{\mu})+(2+K/\beta)/c_{\mu}$
and $c_{\mu}=4\alpha^{2}(1+s)H(\mu)/\beta$. For the last equivalence we used
that we are only interested in $x\geq 1$ (small values are not relevant for
upper bounds). Since $\overline{W}_{-1}\left(d_{\mu}\right)\geq 1$, this
condition is neither restrictive nor informative as we obtain the final
condition $x\geq\overline{W}_{-1}\left(d_{\mu}\right)$. Moreover, we can show

$\displaystyle d_{\mu}\geq
1\>\iff\>c_{\mu}(\log(c_{\mu})-1)\geq-(2+K/\beta)\>\impliedby\>c_{\mu}(\log(c_{\mu})-1)\geq-1\>,$

where the last part is true since $2+K/\beta\geq 1$ and
$\min_{x\in\mathbb{R}}x(\log(x)-1)=-1$ by direct computations. Therefore, for
all $n\geq h_{1}(c_{\mu})^{\alpha}$, we have

$\displaystyle
n-1\geq\frac{1}{w_{-}}\left(n^{1/\alpha}+f_{1}(n)\right)\>\impliedby\>n-1\geq\frac{2}{w_{-}}n^{1/\alpha}\>\impliedby\>n\geq\left(\frac{2}{w_{-}}+1\right)^{\alpha/(\alpha-1)}\>.$

Given the definition of $C_{0}(w_{-})$ as in (9), this concludes the proof.

Since $x\to\overline{W}_{-1}(x)$ is a positive and increasing function, i.e.
$\overline{W}_{-1}(x)>0$ and $\overline{W}_{-1}^{\prime}(x)>0$, a sufficient
condition for $h_{1}$ to be increasing is to have
$f:x\to\log(x)+\frac{2+K/\beta}{x}$ increasing since

$h_{1}^{\prime}(x)=\overline{W}_{-1}(f(x))+xf^{\prime}(x)\overline{W}_{-1}^{\prime}(f(x))>0\>\impliedby\>\overline{W}_{-1}(f(x))>0\>\text{and}\>f^{\prime}(x)\overline{W}_{-1}^{\prime}(f(x))\geq
0\>.$

Since $f^{\prime}(x)=\frac{1}{x}-\frac{2+K/\beta}{x^{2}}$, we have that
$h_{1}$ is increasing for $x\geq 2+K/\beta$. ∎

Lemma D.11 gives an explicit upper bound on the constant $C_{1}(w_{-})$
defined implicitly in Appendix D.2.

######  Lemma D.11.

Let $w_{-}>0$ and $C_{1}(w_{-})$ as in (10). Then, we have

$\displaystyle
C_{1}(w_{-})\leq\max\left\\{h_{1}\left(4\alpha^{2}(1+s)H(\mu)/\beta\right),\left(\frac{1+1/\varepsilon}{w_{-}}+1\right)^{1/(\alpha-1)}\right\\}^{\alpha}\>.$

###### Proof.

Using manipulations conducted in Lemma D.10, we obtain that, for all $n\geq
h_{1}\left(4\alpha^{2}(1+s)H(\mu)/\beta\right)^{\alpha}$,

$\displaystyle
n-1\geq\frac{f_{1}(n)}{w_{-}}\left(1+\frac{1}{\varepsilon}\right)\>\impliedby\>n-1\geq\frac{1+1/\varepsilon}{w_{-}}n^{1/\alpha}\>\impliedby\>n\geq\left(\frac{1+1/\varepsilon}{w_{-}}+1\right)^{\alpha/(\alpha-1)}\>.$

Given the definition of $C_{1}(w_{-})$ as in (10), this concludes the proof. ∎

Lemma D.12 gives an asymptotic upper bound for times that are defined
implicitly. For example, it can be used with $T_{0}(\delta)$ and
$T_{1}(\delta)$ defined in Theorem D.4 and Theorem D.6.

######  Lemma D.12.

Let $C>0$, $D>0$, $c(n,\delta)$ as in (2) and

$T(\delta):=\sup\left\\{n\in\mathbb{N}^{\star}\mid n-1\leq
C\left(\sqrt{c(n-1,\delta)}+\sqrt{D\log n}\right)^{2}\right\\}\>.$

Then, we have $\limsup_{\delta\to 0}\frac{T(\delta,C)}{\log(1/\delta)}\leq C$.

###### Proof.

Let $\gamma>0$. Direct manipulations yield that

$\displaystyle n-1\leq C\left(\sqrt{c(n-1,\delta)}+\sqrt{D\log n}\right)^{2}$
$\displaystyle\iff\>$ $\displaystyle\left(\sqrt{n-1}-\sqrt{CD\log
n}\right)^{2}-4\log\left(4+\log\frac{n}{2}\right)\leq
2C\mathcal{C}_{G}\left(\frac{1}{2}\log\left(\frac{K-1}{\delta}\right)\right)$
$\displaystyle\impliedby\>$ $\displaystyle
n\leq\frac{2C}{1+\gamma}\mathcal{C}_{G}\left(\frac{1}{2}\log\left(\frac{K-1}{\delta}\right)\right)$
$\displaystyle\text{for }n>N_{\gamma}$

where
$N_{\gamma}=\sup\left\\{n\in\mathbb{N}^{\star}\mid\left(\sqrt{n-1}-\sqrt{CD\log
n}\right)^{2}-4\log\left(4+\log\frac{n}{2}\right)>(1+\gamma)n\right\\}$.
Therefore, we have

$T(\delta,C)\leq
N_{\gamma}+1+\frac{2C}{1+\gamma}\mathcal{C}_{G}\left(\frac{1}{2}\log\left(\frac{K-1}{\delta}\right)\right)\>.$

Using that $\mathcal{C}_{G}(x)\approx x+\log(x)$ (Lemma E.1), we obtain
directly that, for all $\gamma>0$,

$\limsup_{\delta\to
0}\frac{T(\delta,C)}{\log(1/\delta)}\leq\frac{C}{1+\gamma}\>,$

which yields the result by letting $\gamma$ go to zero. ∎

Lemma D.13 gives a non-asymptotic upper bound for times that are defined
implicitly. For example, when considering the idealized choice
$c(n,\delta)=\log(1/\delta)$, it can be used as a first order approximation of
$T_{0}(\delta)$ and $T_{1}(\delta)$ defined in Theorem D.4 and Theorem D.6.

######  Lemma D.13.

Let $C>0$, $D>0$ and $T(\delta):=\sup\left\\{n\in\mathbb{N}^{\star}\mid
n-1\leq C\log(1/\delta)+D\log n\right\\}$. Then, we have

$T(\delta)<D\overline{W}_{-1}\left(\frac{C}{D}\log(1/\delta)+1/D+\log
D\right)$

for $\log(1/\delta)\geq\frac{D-D\log(D)-1}{C}$, else $T(\delta)<D$.

###### Proof.

Direct manipulations yield that

$\displaystyle n-1\geq C\log(1/\delta)+D\log n\iff\>y-\log
y\geq\frac{C}{D}\log(1/\delta)+c_{D}\iff\>n\geq
D\overline{W}_{-1}\left(\frac{C}{D}\log(1/\delta)+c_{D}\right)$

where $y=n/D$ and $c_{D}=1/D+\log D$. For the last equivalence, we used that
$\frac{C}{D}\log(1/\delta)+c_{D}\geq 1$ if and only if
$\log(1/\delta)\geq\frac{D}{C}(1-c_{D})=\frac{D-D\log(D)-1}{C}$. When
$\frac{C}{D}\log(1/\delta)+c_{D}<1$, which means that the $\delta$ parameter
is large, we have directly that $y-\log y\geq
1>\frac{C}{D}\log(1/\delta)+c_{D}$ for $y\geq 1$. Therefore, the condition
becomes $n\geq D$. ∎

##  Appendix E Concentration

The proof of Lemma 2.1 is given in Appendix E.1. In Appendix E.2, we show
concentration results for the UCB leader (both with $g_{u}$ and $g_{m}$) and
the TC challenger.

###  E.1 Proof of Lemma 2.1

Proving $\delta$-correctness of a GLR stopping rule is done by leveraging
concentration results. In particular, we build upon Corollary 10 of Kaufmann &
Koolen (2021), which is restated below.

######  Lemma E.1.

Consider Gaussian bandits with means $\mu\in\mathbb{R}^{K}$ and unit variance.
Let $S\subseteq[K]$ and $x>0$.

$\displaystyle\mathbb{P}_{\mu}\left[\exists n\in\mathbb{N},\>\sum_{k\in
S}\frac{N_{n,k}}{2}(\mu_{n,k}-\mu_{k})^{2}>\sum_{k\in
S}2\log\left(4+\log\left(N_{n,k}\right)\right)+|S|\mathcal{C}_{G}\left(\frac{x}{|S|}\right)\right]\leq
e^{-x}$

where $\mathcal{C}_{G}$ is defined in Kaufmann & Koolen (2021) by
$\mathcal{C}_{G}(x)=\max_{\lambda\in]1/2,1]}\frac{g_{G}(\lambda)+x}{\lambda}$
and

$g_{G}(\lambda)=2\lambda-2\lambda\log(4\lambda)+\log\zeta(2\lambda)-\frac{1}{2}\log(1-\lambda)\>,$
(17)

where $\zeta$ is the Riemann $\zeta$ function and $\mathcal{C}_{G}(x)\approx
x+\log(x)$.

Since $\hat{\imath}_{n}=i^{\star}(\mu_{n})$, standard manipulations yield that
for all $k\neq\hat{\imath}_{n}$

$\displaystyle\frac{(\mu_{n,\hat{\imath}_{n}}-\mu_{n,k})^{2}}{\frac{1}{N_{n,\hat{\imath}_{n}}}+\frac{1}{N_{n,k}}}$
$\displaystyle=\inf_{u\in\mathbb{R}}\left(N_{n,\hat{\imath}_{n}}(\mu_{n,\hat{\imath}_{n}}-u)^{2}+N_{n,k}(\mu_{n,k}-u)^{2}\right)=\inf_{y\geq
x}\left(N_{n,\hat{\imath}_{n}}(\mu_{n,\hat{\imath}_{n}}-x)^{2}+N_{n,k}(\mu_{n,k}-y)^{2}\right)\>.$

Let $i^{\star}=i^{\star}(\mu)$. Using the stopping rule (1) and the above
manipulations, we obtain

$\displaystyle\mathbb{P}_{\mu}\left(\tau_{\delta}<+\infty,\hat{\imath}_{\tau_{\delta}}\neq
i^{\star}\right)$ $\displaystyle\leq\mathbb{P}_{\mu}\left(\exists i\neq
i^{\star},\>i=i^{\star}(\mu_{n}),\>\min_{k\neq i}\inf_{y\geq
x}\left(N_{n,i}(\mu_{n,i}-x)^{2}+N_{n,k}(\mu_{n,k}-y)^{2}\right)\geq
2c(n-1,\delta)\right)$ $\displaystyle\leq\mathbb{P}_{\mu}\left(\exists i\neq
i^{\star},\>i=i^{\star}(\mu_{n}),\>\frac{N_{n,i}}{2}(\mu_{n,i}-\mu_{i})^{2}+\frac{N_{n,i^{\star}}}{2}(\mu_{n,i^{\star}}-\mu_{i^{\star}})^{2}\geq
c(n-1,\delta)\right)$ $\displaystyle\leq\sum_{i\neq
i^{\star}}\mathbb{P}_{\mu}\left(\frac{N_{n,i}}{2}(\mu_{n,i}-\mu_{i})^{2}+\frac{N_{n,i^{\star}}}{2}(\mu_{n,i^{\star}}-\mu_{i^{\star}})^{2}\geq
c(n-1,\delta)\right)$

where the second inequality is obtained with
$(k,x,y)=(i^{\star},\mu_{i},\mu_{i^{\star}})$, and the third by union bound.
By concavity of $x\mapsto\log(4+\log(x))$ and
$N_{n,i^{\star}}+N_{n,i}\leq\sum_{k\in[K]}N_{n,k}=n-1$, we obtain

$\forall i\neq i^{\star},\quad\log(4+\log N_{n,i^{\star}})+\log(4+\log
N_{n,i})\leq 2\log(4+\log((n-1)/2))$

Combining the above with Lemma E.1 for all $i\neq i^{\star}$, we obtain
$\mathbb{P}_{\mu}\left(\tau_{\delta}<+\infty,\hat{\imath}=i^{\star}\right)\leq\sum_{i\neq
i^{\star}}\frac{\delta}{K-1}=\delta$.

###  E.2 Sampling Rule

In Lemmas E.2 and E.3, we prove that the UCB leader using $g_{u}$ and $g_{m}$
is truly an upper confidence bounds for the unknown mean parameters, when a
certain concentration event occurs. Then, when another concentration event
occurs, we show a lower bound on the “transportation” costs used by the TC
challenger in Lemma E.5. Lemma E.6 upper bounds the probability of not being
in the intersection of the two above sequence of concentration events.

##### UCB Leader

Lemma E.2 proves that the bonus $g_{u}$ is sufficient to have upper confidence
bounds on the unknown mean $\mu$ for Gaussian observations. The proof uses a
simple union bound argument over the time.

######  Lemma E.2.

Let $\alpha>1$ and $s>1$. For all $n>K$, let $g_{u}(n)=2\alpha(1+s)\log(n)$
and

$\mathcal{E}_{1,n}:=\left\\{\forall k\in[K],\forall
t\in[n^{1/\alpha},n],\>|\mu_{t,k}-\mu_{k}|<\sqrt{\frac{g_{u}(t)}{N_{t,k}}}\right\\}\>.$
(18)

Then, for all $n>K$, $\mathbb{P}(\mathcal{E}_{1,n}^{\complement})\leq
Kn^{-s}$.

###### Proof.

Let $(X_{s})_{s\in[n]}$ be Gaussian observations from one distribution with
unit variance. By union bound over $[K]$ and using that $n\leq t^{\alpha}$, we
obtain

$\displaystyle\mathbb{P}\left(\exists k\in[K],\exists
t\in[n^{1/\alpha},n],\>|\mu_{t,k}-\mu_{k}|\geq\sqrt{\frac{2\alpha(1+s)\log(t)}{N_{t,k}}}\right)$
$\displaystyle\leq\sum_{k\in[K]}\mathbb{P}\left(\exists
t\in[n^{1/\alpha},n],\>|\mu_{t,k}-\mu_{k}|\geq\sqrt{\frac{2(1+s)\log(n)}{N_{t,k}}}\right)$
$\displaystyle\leq\sum_{k\in[K]}\mathbb{P}\left(\exists
m\in[n],\>\left|\frac{1}{m}\sum_{s\in[m]}X_{s}\right|\geq\sqrt{\frac{2(1+s)\log(n)}{m}}\right)$
$\displaystyle\leq\sum_{k\in[K]}\sum_{m\in[n]}\mathbb{P}\left(\left|\frac{1}{m}\sum_{s\in[m]}X_{s}\right|\geq\sqrt{\frac{2(1+s)\log(n)}{m}}\right)$
$\displaystyle\leq\sum_{k\in[K]}\sum_{m\in[n]}n^{-(1+s)}=Kn^{-s}\>,$

where we used that
$\mu_{t,k}-\mu_{k}=\frac{1}{N_{t,k}}\sum_{s=1}^{t}\mathds{1}\left(I_{s}=k\right)X_{s,k}$
and concentration results for Gaussian observations. ∎

Lemma E.3 proves that the bonus $g_{m}$ is sufficient to have upper confidence
bounds on the unknown mean $\mu$ for Gaussian observations. The proof uses a
more sophisticated argument based on mixture of martingales.

######  Lemma E.3.

Let $\alpha>1$ and $s>1$. For all $x\geq 1$, let
$\overline{W}_{-1}(x)=-W_{-1}(-e^{-x})$ where $W_{-1}$ is the negative branch
of the Lambert $W$ function. For all $n>K$, let
$g_{m}(n)=\overline{W}_{-1}\left(2s\alpha\log(n)+2\log(2+\alpha\log
n)+2\right)$ and

$\mathcal{E}_{3,n}:=\left\\{\forall k\in[K],\forall
t\in[n^{1/\alpha},n],\>|\mu_{t,k}-\mu_{k}|<\sqrt{\frac{g_{m}(t)}{N_{t,k}}}\right\\}\>.$
(19)

Then, for all $n>K$, $\mathbb{P}(\mathcal{E}_{3,n}^{\complement})\leq
Kn^{-s}$.

###### Proof.

Let $(X_{s})_{s\in[t]}$ the observations from a standard normal distributions
and denote $S_{t}=\sum_{s\in[t]}X_{s}$. To derived concentration result, we
use peeling.

Let $\eta>0$ and $D=\lceil\frac{\log(n)}{\log(1+\eta)}\rceil$. For all
$i\in[D]$, let $\gamma_{i}>0$ and $N_{i}=(1+\eta)^{i-1}$. For all $i\in[D]$,
we define the family of priors
$f_{N_{i},\gamma_{i}}(x)=\sqrt{\frac{\gamma_{i}N_{i}}{2\pi}}\exp\left(-\frac{x^{2}\gamma_{i}N_{i}}{2}\right)$
with weights $w_{i}=\frac{1}{D}$ and process

$\displaystyle\overline{M}(t)=\sum_{i\in[D]}w_{i}\int
f_{N_{i},\gamma_{i}}(x)\exp\left(xS_{t}-\frac{1}{2}x^{2}t\right)\,dx\>,$

which satisfies $\overline{M}(0)=1$. It is direct to see that
$M(t)=\exp\left(xS_{t}-\frac{1}{2}x^{2}t\right)$ is a non-negative martingale.
By Tonelli’s theorem, then $\overline{M}(t)$ is also a non-negative martingale
of unit initial value.

Let $i\in[D]$ and consider $t\in[N_{i},N_{i+1})$. For all $x$,

$f_{N_{i},\gamma}(x)\geq\sqrt{\frac{N_{i}}{t}}f_{t,\gamma_{i}}(x)\geq\frac{1}{\sqrt{1+\eta}}f_{t,\gamma_{i}}(x)$

Direct computations shows that

$\displaystyle\int
f_{t,\gamma_{i}}(x)\exp\left(xS_{t}-\frac{1}{2}x^{2}t\right)\,dx=\frac{1}{\sqrt{1+\gamma_{i}^{-1}}}\exp\left(\frac{S_{t}^{2}}{2(1+\gamma_{i})t}\right)\>.$

Minoring $\overline{M}(t)$ by one of the positive term of its sum, we obtain

$\displaystyle\overline{M}(t)\geq\frac{1}{D}\frac{1}{\sqrt{(1+\gamma_{i}^{-1})(1+\eta)}}\exp\left(\frac{S_{t}^{2}}{2(1+\gamma_{i})t}\right)\>,$

Using Ville’s maximal inequality, we have that with probability greater than
$1-\delta$, $\log\overline{M}(t)\leq\log\left(1/\delta\right)$. Therefore,
with probability greater than $1-\delta$, for all $i\in[D]$ and
$t\in[N_{i},N_{i+1})$,

$\displaystyle\frac{S_{t}^{2}}{t}$
$\displaystyle\leq(1+\gamma_{i})\left(2\log\left(1/\delta\right)+2\log
D+\log(1+\gamma_{i}^{-1})+\log(1+\eta)\right)\>.$

Since this upper bound is independent of $t$, we can optimize it and choose
$\gamma_{i}$ as in Lemma E.4 for all $i\in[D]$.

######  Lemma E.4 (Lemma A.3 in Degenne (2019)).

For $a,b\geq 1$, the minimal value of
$f(\eta)=(1+\eta)(a+\log(b+\frac{1}{\eta}))$ is attained at $\eta^{\star}$
such that $f(\eta^{\star})\leq 1-b+\overline{W}_{-1}(a+b)$. If $b=1$, then
there is equality.

Therefore, with probability greater than $1-\delta$, for all $i\in[D]$ and
$t\in[N_{i},N_{i+1})$,

$\displaystyle\frac{S_{t}^{2}}{t}$
$\displaystyle\leq\overline{W}_{-1}\left(1+2\log\left(1/\delta\right)+2\log
D+\log(1+\eta)\right)$
$\displaystyle\leq\overline{W}_{-1}\left(1+2\log\left(1/\delta\right)+2\log\left(\log(1+\eta)+\log
n\right)-2\log\log(1+\eta)+\log(1+\eta)\right)$
$\displaystyle=\overline{W}_{-1}\left(2\log\left(1/\delta\right)+2\log\left(2+\log
n\right)+3-2\log 2\right)$

where $g(s)=\log(\zeta(s))+s(1-\log(2s))$. The second inequality is obtained
since $D\leq 1+\frac{\log n}{\log(1+\eta)}$. The last equality is obtained for
the choice $\eta^{\star}=e^{2}-1$, which minimizes
$\eta\mapsto\log(1+\eta)-2\log(\log(1+\eta))$. Since
$[n]\subseteq\bigcup_{i\in[D]}[N_{i},N_{i+1})$ and
$N_{t,k}(\mu_{t,k}-\mu_{k})=\sum_{s\in[N_{t,k}]}X_{s,k}$ (unit-variance), this
yields

$\displaystyle\mathbb{P}\left(\exists t\leq
n,\left|\frac{1}{t}\sum_{s=1}^{t}X_{s}\right|\geq\sqrt{\frac{1}{t}\overline{W}_{-1}\left(2\log(1/\delta)+2\log(2+\log(n))+3-2\log
2\right)}\right)\leq\delta\>.$

Since $3-2\log 2\leq 2$ and $\overline{W}_{-1}$ is increasing, taking
$\delta=n^{-s}$ and restricting to $m\in[n^{1/\alpha},n]$ yields

$\displaystyle\mathbb{P}\left(\exists
m\in[n^{1/\alpha},n],\sqrt{N_{m,k}}\left|\mu_{m,k}-\mu_{k}\right|\geq\sqrt{\overline{W}_{-1}\left(2s\log(n)+2\log(2+\log(n))+2\right)}\right)\leq
n^{-s}\>.$

Using $n\leq m^{\alpha}$ and doing a union bound over arms yield the result. ∎

##### TC Challenger

Lemma E.5 lower bounds the difference between the empirical gap and the
unknown gap.

######  Lemma E.5.

Let $\alpha>1$ and $s>1$. For all $n>K$, let

$\mathcal{E}_{2,n}:=\left\\{\forall k\neq i^{\star},\forall
t\in[n^{1/\alpha},n],\>(\mu_{t,i^{\star}}-\mu_{t,k})-(\mu_{i^{\star}}-\mu_{k})>-\sqrt{2\alpha(2+s)\log(t)\left(\frac{1}{N_{t,i^{\star}}}+\frac{1}{N_{t,k}}\right)}\right\\}\>.$
(20)

Then, for all $n>K$,
$\mathbb{P}(\mathcal{E}_{2,n}^{\complement})\leq(K-1)n^{-s}$.

###### Proof.

Let $(X_{s})_{s\in[n]}$ and $(Y_{s})_{s\in[n]}$ be Gaussian observations from
two distributions with unit variance. Then
$\frac{1}{m_{1}}\sum_{i=1}^{m_{1}}X_{i}-\frac{1}{m_{2}}\sum_{i=1}^{m_{2}}Y_{i}$
is Gaussian with variance $\frac{1}{m_{1}}+\frac{1}{m_{2}}$. By union bound
and using that $n\leq t^{\alpha}$, we obtain

$\displaystyle\mathbb{P}\left(\exists k\neq i^{\star},\exists
t\in[n^{1/\alpha},n],\>\frac{(\mu_{t,i^{\star}}-\mu_{t,k})-(\mu_{i^{\star}}-\mu_{k})}{\sqrt{1/N_{t,i^{\star}}+1/N_{t,k}}}\leq-\sqrt{2\alpha(2+s)\log(t)}\right)$
$\displaystyle\leq\sum_{k\neq i^{\star}}\mathbb{P}\left(\exists
t\in[n^{1/\alpha},n],\>\frac{(\mu_{t,i^{\star}}-\mu_{t,k})-(\mu_{i^{\star}}-\mu_{k})}{\sqrt{1/N_{t,i^{\star}}+1/N_{t,k}}}\leq-\sqrt{2(2+s)\log(n)}\right)$
$\displaystyle\leq\sum_{k\neq
i^{\star}}\mathbb{P}\left(\exists(m_{1},m_{2})\in[n]^{2},\>\frac{\frac{1}{m_{1}}\sum_{i=1}^{m_{1}}X_{i}-\frac{1}{m_{2}}\sum_{i=1}^{m_{2}}Y_{i}}{\sqrt{1/m_{1}+1/m_{2}}}\leq-\sqrt{2(2+s)\log(n)}\right)$
$\displaystyle\leq\sum_{k\neq
i^{\star}}\sum_{(m_{1},m_{2})\in[n]^{2}}\mathbb{P}\left(\frac{1}{m_{1}}\sum_{i=1}^{m_{1}}X_{i}-\frac{1}{m_{2}}\sum_{i=1}^{m_{2}}Y_{i}\leq-\sqrt{2(2+s)\log(n)\left(1/m_{1}+1/m_{2}\right)}\right)$
$\displaystyle\leq\sum_{k\neq
i^{\star}}\sum_{(m_{1},m_{2})\in[n]^{2}}n^{-(2+s)}=(K-1)n^{-s}\>,$

where we used that
$(\mu_{t,i^{\star}}-\mu_{i^{\star}})-(\mu_{t,k}-\mu_{k})=\frac{1}{N_{t,i^{\star}}}\sum_{s=1}^{t}\mathds{1}\left(I_{s}=i^{\star}\right)X_{s,i^{\star}}-\frac{1}{N_{t,k}}\sum_{s=1}^{t}\mathds{1}\left(I_{s}=k\right)X_{s,k}$
and concentration results for Gaussian observations. ∎

Using a mixture of martingale arguments, we could improve on Lemma E.5
similarly as $g_{u}$ improved on $g_{m}$. This will impact second order terms
of our non-asymptotic theoretical guarantees, at the price of less explicit
non-asymptotic terms.

##### Concentration Event

Lemma E.6 upper bounds the summed probabilities of the complementary events.

######  Lemma E.6.

Let $\zeta$ be the Riemann $\zeta$ function. Let $(\mathcal{E}_{1,n})_{n>K}$,
$(\mathcal{E}_{2,n})_{n>K}$ and $(\mathcal{E}_{3,n})_{n>K}$ as in (18), (20)
and (19). For all $n>K$, let
$\mathcal{E}_{n}=\mathcal{E}_{1,n}\cap\mathcal{E}_{2,n}$ and
$\tilde{\mathcal{E}}_{n}=\mathcal{E}_{3,n}\cap\mathcal{E}_{2,n}$. Then,

$\max\left\\{\sum_{n>K}\mathbb{P}(\mathcal{E}_{n}^{\complement}),\sum_{n>K}\mathbb{P}(\tilde{\mathcal{E}}_{n}^{\complement})\right\\}\leq(2K-1)\zeta(s)\>.$

###### Proof.

Using Lemmas E.2 and E.5, direct union bound yields

$\displaystyle\sum_{n\in\mathbb{N}^{\star}}\mathbb{P}(\mathcal{E}_{n}^{\complement})\leq\sum_{n\in\mathbb{N}^{\star}}\mathbb{P}(\mathcal{E}_{1,n}^{\complement})+\mathbb{P}(\mathcal{E}_{2,n}^{\complement})\leq\sum_{n\in\mathbb{N}^{\star}}(2K-1)n^{-s}=(2K-1)\zeta(s)\>.$

The same proof trivially holds for $\tilde{\mathcal{E}}_{n}$ by using Lemmas
E.3 and E.5. ∎

##  Appendix F Asymptotic Analysis

Based solely on Theorem D.4, it is not possible to obtain asymptotic