$B^{\text{EB}}_{t}=k$. Then, for all $i\neq k$, we have

$\displaystyle\mu_{i}-\sqrt{\frac{2f_{1}(n,\delta)}{\min\\{N_{t,k},N_{t,i}\\}}}\leq\mu_{i}-\sqrt{\frac{2f_{1}(n,\delta)}{N_{t,i}}}\leq\mu_{t,i}\leq\mu_{t,k}$
$\displaystyle\leq\mu_{k}+\sqrt{\frac{2f_{1}(n,\delta)}{N_{t,k}}}$
$\displaystyle\leq\mu_{k}+\sqrt{\frac{2f_{1}(n,\delta)}{\min\\{N_{t,k},N_{t,i}\\}}}\>.$

Re-ordering the above equations for $i$ such that $\mu_{i}>\mu_{k}$ yields the
result. ∎

######  Lemma 32.

Let $\varepsilon\geq 0$,
$\Delta_{\mu}(\varepsilon)=\min_{k\notin\mathcal{I}_{\varepsilon}(\mu)}\Delta_{k}$
and
$C_{\mu,\varepsilon_{0}}(\varepsilon)=\max\\{2\Delta_{\mu}(\varepsilon)^{-1}-\varepsilon_{0}^{-1},\varepsilon_{0}^{-1}\\}^{2}$.
Let $A_{\varepsilon_{0},\varepsilon,i}=2/\Delta_{\mu}(\varepsilon)^{2}$ for
all $i\in i^{\star}(\mu)$,
$A_{\varepsilon_{0},\varepsilon,i}=C_{\mu,\varepsilon_{0}}(\varepsilon)$ for
all $i\in\mathcal{I}_{\varepsilon}(\mu)\setminus i^{\star}(\mu)$, otherwise
$A_{\varepsilon_{0},\varepsilon,i}=\max\\{C_{\mu,\varepsilon_{0}}(\varepsilon),2/\Delta_{i}^{2}\\}$.
For all $n>K$, under event $\mathcal{E}_{n,\delta}$, for all
$t\in[n]\setminus[K]$ such that
$B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)$, there exists
$i_{t}\in[K]$ such that

$T_{t}(i_{t})\leq\frac{4f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}A_{\varepsilon_{0},\varepsilon,i_{t}}+3(K-1)/2\quad\text{and}\quad
T_{t+1}(i_{t})=T_{t}(i_{t})+1\>.$

###### Proof.

Let $\Delta_{i}=\mu_{\star}-\mu_{i}$ and
$\Delta_{\max}=\max_{i\in[K]}\Delta_{i}$. When $\varepsilon\geq\Delta_{\max}$,
we have $\mathcal{I}_{\varepsilon}(\mu)^{\complement}=\emptyset$, hence the
above result holds trivially since the event
$B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)$ cannot happen. Let
$\varepsilon\in[0,\Delta_{\max})$, i.e.
$\mathcal{I}_{\varepsilon}(\mu)^{\complement}\neq\emptyset$. We will consider
in two distinct cases since

$\left\\{B_{t}\notin\mathcal{I}_{\varepsilon}(\mu)\right\\}=\\{B_{t}\notin\mathcal{I}_{\varepsilon}(\mu),C_{t}\in
i^{\star}(\mu)\\}\cup\\{B_{t}\notin\mathcal{I}_{\varepsilon}(\mu),C_{t}\notin
i^{\star}(\mu)\\}\>.$

Case 1. Let $t\in[n]\setminus[K]$ such that
$(B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t})=(i,j)$ with
$i\notin\mathcal{I}_{\varepsilon}(\mu)$ and $j\in i^{\star}(\mu)$. Using
Lemmas 46 and 31, we obtain

$\min\\{\beta,1-\beta\\}\left(\min\\{T_{t}(i),T_{t}(j)\\}-3(K-1)/2\right)\leq\min\\{N_{t,i},N_{t,j}\\}\leq\frac{8f_{1}(n,\delta)}{\Delta_{i}^{2}}\leq\frac{8f_{2}(n,\delta)}{\Delta_{i}^{2}}\>,$

which can be rewritten as

$\min\\{T_{t}(i),T_{t}(j)\\}\leq\frac{8f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}\Delta_{i}^{2}}+3(K-1)/2\>.$

Let us define
$\Delta_{\mu}(\varepsilon)=\min_{k\notin\mathcal{I}_{\varepsilon}(\mu)}\Delta_{k}$,
and

$\forall i\notin\mathcal{I}_{\varepsilon}(\mu),\quad
D_{\varepsilon,i}=2/\Delta_{i}^{2}\quad\text{and}\quad\forall i\in
i^{\star}(\mu),\quad D_{\varepsilon,i}=2/\Delta_{\mu}(\varepsilon)^{2}\>.$

The above shows that there exists
$k_{t}\in\mathcal{I}_{\varepsilon}(\mu)^{\complement}\cup i^{\star}(\mu)$ such
that

$T_{t}(k_{t})\leq\frac{4f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}D_{\varepsilon,k_{t}}+3(K-1)/2\quad\text{and}\quad
T_{t+1}(k_{t})=T_{t}(k_{t})+1\>.$

Case 2. Let $t\in[n]\setminus[K]$ such that
$(B^{\text{EB}}_{t},C^{\text{TC}\varepsilon_{0}}_{t})=(i,j)$ with
$i\notin\mathcal{I}_{\varepsilon}(\mu)$ and $j\notin i^{\star}(\mu)$. Let
$i_{0}\in i^{\star}(\mu)$. Using the TC challenger, we obtain

$\displaystyle\frac{\varepsilon_{0}-\Delta_{i}}{\sqrt{1/N_{t,i}+1/N_{t,i_{0}}}}+\sqrt{2f_{2}(n,\delta)}\geq\frac{\mu_{t,i}-\mu_{t,i_{0}}+\varepsilon_{0}}{\sqrt{1/N_{t,i}+1/N_{t,i_{0}}}}$
$\displaystyle\geq\frac{\mu_{t,i}-\mu_{t,j}+\varepsilon_{0}}{\sqrt{1/N_{t,i}+1/N_{t,j}}}$
$\displaystyle\geq\varepsilon_{0}\sqrt{\min\\{N_{t,i},N_{t,j}\\}/2}\>.$

Using Lemma 31, we obtain

$\frac{1}{1/N_{t,i}+1/N_{t,i_{0}}}\leq\min\\{N_{t,i},N_{t,i_{0}}\\}\leq\frac{8f_{1}(n,\delta)}{\Delta_{i}^{2}}\leq\frac{8f_{2}(n,\delta)}{\Delta_{i}^{2}}\>.$

By distinguishing between $\varepsilon_{0}>\Delta_{i}$ and
$\varepsilon_{0}\leq\Delta_{i}$ and using that $\Delta_{i}>0$, we have

$\displaystyle\frac{\varepsilon_{0}-\Delta_{i}}{\sqrt{1/N_{t,i}+1/N_{t,i_{0}}}}+\sqrt{2f_{2}(n,\delta)}\leq\max\\{2\varepsilon_{0}/\Delta_{i}-1,1\\}\sqrt{2f_{2}(n,\delta)}\>.$

Using Lemma 46 to lower bound $\min\\{N_{t,i},N_{t,j}\\}$ and reordering, we
have shown that

$\min\\{T_{t}(i),T_{t}(j)\\}\leq\max\left\\{\left(\frac{2}{\Delta_{i}}-\frac{1}{\varepsilon_{0}}\right)^{2},\frac{1}{\varepsilon_{0}^{2}}\right\\}\frac{4f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}+3(K-1)/2\>.$

Let us define
$C_{\mu,\varepsilon_{0}}(\varepsilon)=\max\\{2\Delta_{\mu}(\varepsilon)^{-1}-\varepsilon_{0}^{-1},\varepsilon_{0}^{-1}\\}^{2}$.
The above shows that, there exists $k_{t}\notin i^{\star}(\mu)$ such that

$T_{t}(k_{t})\leq\frac{4f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}C_{\mu,\varepsilon_{0}}(\varepsilon)+3(K-1)/2\quad\text{and}\quad
T_{t+1}(k_{t})=T_{t}(k_{t})+1\>.$

Summary. Let us define $(A_{\varepsilon_{0},\varepsilon,i})_{i\in[K]}$ as in
the statement of Lemma 32. Under $\mathcal{E}_{n,\delta}$, we have show that,
when $B_{t}\notin\mathcal{I}_{\varepsilon}(\mu)$, there exists $i_{t}\in[K]$
such that

$T_{t}(k_{t})\leq\frac{4f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}A_{\varepsilon,\varepsilon_{0},i_{t}}+3(K-1)/2\quad\text{and}\quad
T_{t+1}(k_{t})=T_{t}(k_{t})+1\\}\>.$

∎

For all $n>K$, under event $\mathcal{E}_{n,\delta}$, combining Lemma 4 and 32
for
$A_{t}(n,\delta)=\\{B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)\\}$
and
$D_{i}(n,\delta)=\frac{4f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}A_{\varepsilon_{0},\varepsilon,i}+3(K-1)/2$
yields that

$\sum_{t=K+1}^{n}\mathds{1}\left(B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)\right)\leq\frac{4f_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}H_{\mu,\varepsilon_{0}}(\varepsilon)+3K(K-1)/2\>.$

where we used that
$\sum_{i\in[K]}A_{\varepsilon_{0},\varepsilon,i}=H_{\mu,\varepsilon_{0}}(\varepsilon)$
where $H_{\mu,\varepsilon_{0}}(\varepsilon)$ is defined in (5). To conclude
the proof of Lemma 5, we use that

$\sum_{t=K+1}^{n}\mathds{1}\left(B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)\right)=n-1-\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}\sum_{j}T_{n}(i,j)\>.$

Let $\tilde{f}_{1}(n,\delta)$ and $\tilde{f}_{2}(n,\delta)$ defined as in (26)
and (28). Using Lemma 50, we have
$\tilde{f}_{1}(n,\delta)\leq\tilde{f}_{2}(n,\delta)$. Therefore, it is direct
to see that Lemma 33 can be proven with the same proof as for Lemma 5 based on
the concentration event
$\tilde{\mathcal{E}}_{n,\delta}=\tilde{\mathcal{E}}^{1}_{n,\delta}\cap\tilde{\mathcal{E}}^{2}_{n,\delta}$
with $(\tilde{\mathcal{E}}^{1}_{n,\delta})_{n>K}$ and
$(\tilde{\mathcal{E}}^{2}_{n,\delta})_{n>K}$ as in (27) and (29).

######  Lemma 33.

Let $\delta\in(0,1]$, $\varepsilon\geq 0$ and
$H_{\mu,\varepsilon_{0}}(\varepsilon)$ as in (5). For all $n>K$, under the
event $\tilde{\mathcal{E}}_{n,\delta}$,

$\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}\sum_{j}T_{n}(i,j)\geq
n-1-\left(\frac{4H_{\mu,\varepsilon_{0}}(\varepsilon)}{\min\\{\beta,1-\beta\\}}\tilde{f}_{2}(n,\delta)+3K(K-1)/2\right)\>.$

###  E.2 Proof of Theorem 2

Let $s>1$. For all $n>K$, let
$\mathcal{E}_{n}=\mathcal{E}^{1}_{n,1}\cap\mathcal{E}^{2}_{n,1}$ with
$(\mathcal{E}^{1}_{n,\delta})_{n>K}$ and $(\mathcal{E}^{2}_{n,\delta})_{n>K}$
as in (24) and (25). Using Lemma 45, we know that
$\sum_{n>K}\mathbb{P}_{\nu}(\mathcal{E}_{n}^{\complement})\leq\frac{K(K+1)}{2}\zeta(s)$.

Let $\varepsilon_{0}>0$, $\varepsilon_{1}\geq\varepsilon_{0}$ and
$\delta\in(0,1)$. Since $\varepsilon_{1}\geq\varepsilon_{0}$, and using the
definition of the stopping rule (3), it is direct to see that
$\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]\leq\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]$.

Suppose that we have constructed a time $T(\delta)>K$ be such that for $n\geq
T(\delta)$, $\mathcal{E}_{n}\subset\\{\tau_{\varepsilon_{0},\delta}\leq n\\}$
Then, Lemma 47 yields

$\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]\leq
T(\delta)+\frac{K(K+1)}{2}\zeta(s)\>.$

We will construct an infinite number of times
$\\{T(\delta,u)\\}_{u\in\mathcal{U}}$ such that the above property holds,
hence taking the infimum yields

$\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]\leq\inf_{u\in\mathcal{U}}T(\delta,u)+\frac{K(K+1)}{2}\zeta(s)\>.$

This proof strategy is the one used to prove Theorem 5. Theorem 2 is a
corollary of Theorem 5. Note that the notation of both theorems differ
slightly since we provide a shorter statement in the main content. The key
difference lies in the refined analysis used to clip $\min_{j\neq
i}w_{\varepsilon_{0},1/2}(\mu,i)_{j}$ by a fixed value $x\in[0,(K-1)^{-1}]$
for all $i\in\mathcal{I}_{\varepsilon}(\mu)$.

######  Theorem 5.

Let $\varepsilon_{0}>0$, $\varepsilon_{1}\geq\varepsilon_{0}$ and
$\delta\in(0,1)$. Using the threshold (4) in the stopping rule (3) with error
$\varepsilon_{1}$, the EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed
proportions $\beta=1/2$ is $(\varepsilon_{1},\delta)$-PAC and satisfies that,
for all $\nu\in\mathcal{D}^{K}$,
$\mathbb{E}_{\nu}[\tau_{\varepsilon_{1},\delta}]\leq\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]$
and

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

where

$\displaystyle T_{\mu,\varepsilon_{0}}(\delta,\varepsilon,x)=\sup\left\\{n\mid
n-1\leq\frac{2(1+\gamma)^{2}\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)}{(1-x)^{d_{\mu,\varepsilon_{0}}(\varepsilon,x)}}\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\left.\left(\sqrt{c(n-1,\delta)}+\sqrt{(2+s)\log
n}\right)^{2}\right\\}\>,$ $\displaystyle
S_{\mu,\varepsilon_{0}}(\varepsilon,x)=h_{1}\left(\frac{4(2+s)(1+\gamma^{-1})}{a_{\mu,\varepsilon_{0}}(\varepsilon,x)v_{\mu,\varepsilon_{0}}(\varepsilon)}H_{\mu,\varepsilon_{0}}(\varepsilon),\>\frac{(1+\gamma^{-1})(3K^{2}/4+1)}{a_{\mu,\varepsilon_{0}}(\varepsilon,x)v_{\mu,\varepsilon_{0}}(\varepsilon)}+1\right)\>,$
$\displaystyle
v_{\mu,\varepsilon_{0}}(\varepsilon)=\frac{\min_{i\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)}{\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)}$
$\displaystyle
a_{\mu,\varepsilon_{0}}(\varepsilon,x)=\min_{i\in\mathcal{I}_{\varepsilon}(\mu)}(1-x)^{d_{\mu,\varepsilon_{0}}(x,i)}\max\\{\min_{j\neq
i}w_{\varepsilon_{0},1/2}(\mu,i)_{j},x/2\\}\>,$ $\displaystyle
d_{\mu,\varepsilon_{0}}(\varepsilon,x)=\max_{i\in\mathcal{I}_{\varepsilon}(\mu)}d_{\mu,\varepsilon_{0}}(x,i)\quad\text{with}\quad
d_{\mu,\varepsilon_{0}}(x,i)=|\\{j\neq
i\mid\>w_{\varepsilon_{0},1/2}(\mu,i)_{j}<x/2\\}|\>,$

where $\gamma\in(0,1/2]$ and $s>1$ are analysis parameters.
$T_{\varepsilon_{0},1/2}(\mu,i)$ and $w_{\varepsilon_{0},1/2}(\mu,i)$ are
defined in (1), $H_{\mu,\varepsilon_{0}}(\varepsilon)$ in (5), $\zeta$ is the
Riemann $\zeta$ function and
$h_{1}(z,y)=z\overline{W}_{-1}\left(\log(z)+y/z\right)$ is defined in Lemma 51
and satisfies that $h_{1}(z,y)\approx x\log(z)+y+\log(\log(z)+y/z)$.

###### Proof.

Let $\varepsilon\in[0,\varepsilon_{0}]$ be an analysis parameter, and
$I_{\varepsilon}=|\mathcal{I}_{\varepsilon}(\mu)|$. Let
$v\in\mathring{\triangle}_{I_{\varepsilon}}$ defined as

$\forall i\in\mathcal{I}_{\varepsilon}(\mu),\quad
v_{i}=\frac{T_{\varepsilon_{0},1/2}(\mu,i)}{\sum_{j\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon_{0},1/2}(\mu,j)}\>,\quad\text{hence}\quad\min_{i\in\mathcal{I}_{\varepsilon}(\mu)}v_{i}=v_{\mu,\varepsilon_{0}}(\varepsilon)\>.$

The main technical result on which our proof relies on is Lemma 34, which we
will prove afterwards.

######  Lemma 34.

There exist $D_{0}>0$ and $T_{\mu}>0$ such that for all $n\geq T_{\mu}$ such
that $\mathcal{E}_{n}\cap\\{n<\tau_{\varepsilon_{1},\delta}\\}$ holds true,
there exists $i_{0}\in\mathcal{I}_{\varepsilon}(\mu)$ and $t\leq n$ with
$B^{\text{EB}}_{t}=i_{0}$, which satisfies

$1/N_{t,i_{0}}^{i_{0}}+1/N_{t,C^{\text{TC}\varepsilon_{0}}_{t}}^{i_{0}}\leq\frac{D_{0}}{v_{i_{0}}(n-1)}\left(1/\beta+1/w^{\star}_{\beta}(i_{0})_{C^{\text{TC}\varepsilon_{0}}_{t}}\right)\>.$
(15)

Before proving Lemma 34, we show how it can be used to conclude. Based on
Lemma 34, let $D_{0}>0$, $T_{\mu}>0$, $n>T_{\mu}$ such that
$\mathcal{E}_{n}\cap\\{n<\tau_{\varepsilon_{1},\delta}\\}$ holds true, $i_{0}$
and $t\leq n$ such that as $B^{\text{EB}}_{t}=i_{0}$ and

$1/N_{t,i_{0}}^{i_{0}}+1/N_{t,C^{\text{TC}\varepsilon_{0}}_{t}}^{i_{0}}\leq\frac{D_{0}}{v_{i_{0}}(n-1)}\left(1/\beta+1/w^{\star}_{\beta}(i_{0})_{C^{\text{TC}\varepsilon_{0}}_{t}}\right)\>.$

Using the stopping rule (3) with error $\varepsilon_{0}$, $t\leq
n<\tau_{\varepsilon_{1},\delta}$, $B^{\text{EB}}_{t}=\hat{\imath}_{t}=i_{0}$
and the definition of the TC${}_{\varepsilon_{0}}$challenger in (2) with slack
$\varepsilon_{0}$, we obtain

$\displaystyle\sqrt{2c(n-1,\delta)}$ $\displaystyle\geq\min_{i\neq
i_{0}}\frac{\mu_{t,i_{0}}-\mu_{t,i}+\varepsilon_{0}}{\sqrt{1/N_{t,i_{0}}+1/N_{t,i}}}$
$\displaystyle\geq\frac{\mu_{i_{0}}-\mu_{C^{\text{TC}\varepsilon_{0}}_{t}}+\varepsilon_{0}}{\sqrt{1/N_{t,i_{0}}+1/N_{t,C^{\text{TC}\varepsilon_{0}}_{t}}}}-\sqrt{2(2+s)\log
n}$
$\displaystyle\geq\sqrt{\frac{1/\beta+w^{\star}_{\beta}(i_{0})_{C^{\text{TC}\varepsilon_{0}}_{t}}^{-1}}{1/N_{t,i_{0}}^{i_{0}}+1/N_{t,C^{\text{TC}\varepsilon_{0}}_{t}}^{i_{0}}}}\sqrt{2T_{\varepsilon_{0},\beta}(\mu,i_{0})^{-1}}-\sqrt{2(2+s)\log
n}$
$\displaystyle\geq\sqrt{\frac{2(n-1)}{D_{0}\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon_{0},\beta}(\mu,i)}}-\sqrt{2(2+s)\log
n}\>.$

The third inequality is obtained since $\mathcal{E}_{n}$ holds. The fourth
inequality is obtained since $N_{t,i}^{i_{0}}\geq N_{t,i}^{i_{0}}$ for all
$i\in[K]$ and by using Lemmas 8 and 9. The last inequality is obtained by
Lemma 34 and using the definition of $v_{i_{0}}$.

Let’s define $T(\delta,D_{0}):=\sup\\{n>K\mid
n-1<D_{0}\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon_{0},\beta}(\mu,i)(\sqrt{c(n-1,\delta)}+\sqrt{(2+s)\log
n})^{2}\\}$. Therefore, we have
$\mathcal{E}_{n}\cap\\{n<\tau_{\varepsilon_{0},\delta}\\}=\emptyset$ (i.e.
$\mathcal{E}_{n}\subset\\{\tau_{\varepsilon_{0},\delta}\leq n\\}$) for all
$n\geq\max\\{T(\delta,D_{0}),T_{\mu}+1\\}$. This concludes the construction.

To conclude the proof, we will show that Lemma 34 for many choices of $D_{0}$
and $T_{\mu}$.

Vanilla Proof of Lemma 34.  Let
$g_{\varepsilon}(n)=\frac{4H_{\mu,\varepsilon_{0}}(\varepsilon)}{\min\\{\beta,1-\beta\\}}(2+s)\log
n+3K(K-1)/2$. Using Lemma 5, under the event $\mathcal{E}_{n}$,

$\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}\sum_{j}T_{n}(i,j)\geq
n-1-g_{\varepsilon}(n)\>.$

Therefore, the pigeonhole principle yields that there exists
$i_{0}\in\mathcal{I}_{\varepsilon}(\mu)$ such that

$\sum_{j}T_{n}(i_{0},j)\geq v_{i_{0}}(n-1-g_{\varepsilon}(n))\>.$

The crux of the problem is to relate $N_{t,C_{t}}^{i_{0}}/(t-1)$ and
$w^{\star}_{\beta}(i_{0})_{C_{t}^{\text{TC}\varepsilon_{0}}}$. To do so, we
use the approach of [20] that builds on the idea behind the proof for APT from
[30]: 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_{0}$
such that

$N_{n,k_{1}}^{i_{0}}\geq\frac{w^{\star}_{\beta}(i_{0})_{k_{1}}}{1-\beta}\sum_{j\neq
i_{0}}N_{n,j}^{i_{0}}\>,$ (16)

and we take such $k_{1}$. Let
$t_{1}:=\sup\left\\{t<n\mid(B_{t},C_{t})=(i_{0},k_{1})\right\\}$ be the last
time at which $i_{0}$ was the leader and $k_{1}$ was the challenger. If
$I_{t_{1}}=B_{t_{1}}$ then $N_{t_{1},k_{1}}^{i_{0}}=N_{n,k_{1}}^{i_{0}}$,
otherwise $N_{t_{1},k_{1}}^{i_{0}}=N_{n,k_{1}}^{i_{0}}-1$. In both cases, we
have $N_{t_{1},k_{1}}^{i_{0}}\geq N_{n,k_{1}}^{i_{0}}-1$. Combined with the
above and using that $w^{\star}_{\beta}(i_{0})_{k_{1}}\leq 1-\beta$ and
$v_{i_{0}}\leq 1$, we obtain

$\displaystyle N_{t_{1},k_{1}}^{i_{0}}\geq N_{n,k_{1}}^{i_{0}}-1$
$\displaystyle\geq\frac{w^{\star}_{\beta}(i_{0})_{k_{1}}}{1-\beta}\sum_{j\neq
i_{0}}N_{n,j}^{i_{0}}-1$ $\displaystyle\geq
w^{\star}_{\beta}(i_{0})_{k_{1}}\left(\sum_{j\neq
i_{0}}T_{n}(i_{0},j)-\frac{K-1}{2(1-\beta)}\right)-1$ $\displaystyle\geq
w^{\star}_{\beta}(i_{0})_{k_{1}}v_{i_{0}}(n-1)-(1-\beta)v_{i_{0}}g_{\varepsilon}(n)-\frac{K+1}{2}$
$\displaystyle\geq
w^{\star}_{\beta}(i_{0})_{k_{1}}v_{i_{0}}(n-1)-h_{\varepsilon}(n)\>,$
$\displaystyle\text{with}\quad h_{\varepsilon}(n)$
$\displaystyle=\frac{4(1-\beta)H_{\mu,\varepsilon_{0}}(\varepsilon)}{\min\\{\beta,1-\beta\\}}f_{2}(n)+(1-\beta)3K(K-1)/2+\frac{K+1}{2}\>.$

Let $w_{i_{0},-}>0$ be a lower bound on $w^{\star}_{\beta}(i_{0})_{k_{1}}$,
e.g. $w_{i_{0},-}=\min_{i\neq i_{0}}w^{\star}_{\beta}(i_{0})_{i}$. For
instances $\mu$ such that $w^{\star}_{\beta}(i_{0})_{k_{1}}$ is small, the
equation (16) can be satisfied at the very beginning, hence $t_{1}$ might be
sublinear in $n$. Due to the missing link between $t_{1}$ and $n$, we use the
following inequality

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

which is a suboptimal step which artificially introduces $1/\beta$.

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

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

for all $n>C_{1}(w_{i_{0},-},v_{\mu,\varepsilon_{0}}(\varepsilon))$. The last
inequality is obtained by definition of

$C_{1}(w,v):=\sup\left\\{n\geq 1\mid
n-1<\frac{h_{\varepsilon}(n)}{wv}\left(1+\gamma^{-1}\right)\right\\}\>,$ (17)

which ensures that, for all
$n>C_{1}(w_{i_{0},-},v_{\mu,\varepsilon_{0}}(\varepsilon))$, the last
condition of the equivalence

$\displaystyle
w^{\star}_{\beta}(i_{0})_{k_{1}}-\frac{h_{\varepsilon}(n)}{v_{i_{0}}(n-1)}\geq(1+\gamma)^{-1}w^{\star}_{\beta}(i_{0})_{k_{1}}\quad\iff\quad
n-1\geq\frac{h_{\varepsilon}(n)}{v_{i_{0}}w^{\star}_{\beta}(i_{0})_{k_{1}}}\left(1+\gamma^{-1}\right)$

is satisfied since $w^{\star}_{\beta}(i_{0})_{k_{1}}\geq w_{i_{0},-}$,
$v_{i_{0}}\geq v_{\mu,\varepsilon_{0}}(\varepsilon)$ and
$n>C_{1}(w_{i_{0},-},v_{\mu,\varepsilon_{0}}(\varepsilon))$.

Second, using Lemma 46, we can show that

$\displaystyle N_{t_{1},i_{0}}^{i_{0}}\geq
T_{t_{1}}(i_{0},k_{1})-N^{i_{0}}_{t_{1},k_{1}}\geq\beta
T_{t_{1}}(i_{0},k_{1})-1$
$\displaystyle\geq\frac{\beta}{1-\beta}N_{t_{1},k_{1}}^{i_{0}}-\frac{1}{1-\beta}\>.$

Then, re-ordering the above and using that $N_{t_{1},k_{1}}^{i_{0}}\geq
w^{\star}_{\beta}(i_{0})_{k_{1}}v_{i_{0}}(n-1)-h_{\varepsilon}(n)$, we obtain

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

for all $n>C_{2}(w_{i_{0},-},v_{\mu,\varepsilon_{0}}(\varepsilon))$. The last
inequality is obtained by definition of

$C_{2}(w,v):=\sup\left\\{n\in\mathbb{N}^{\star}\mid
n-1<\frac{1}{wv}\left(h_{\varepsilon}(n)+\frac{\gamma+1-\beta}{\beta\gamma}\right)\right\\}\>,$
(18)

which ensures that, for all
$n>C_{2}(w_{i_{0},-},v_{\mu,\varepsilon_{0}}(\varepsilon))$, the last
condition of the equivalence

$\displaystyle\left(\frac{\beta}{1-\beta}-\frac{1}{(1-\beta)\left(w^{\star}_{\beta}(i_{0})_{k_{1}}v_{i_{0}}(n-1)-h_{\varepsilon}(n)\right)}\right)^{-1}+1\leq(1+\gamma)/\beta$
$\displaystyle\iff\quad\frac{1}{w^{\star}_{\beta}(i_{0})_{k_{1}}v_{i_{0}}(n-1)-h_{\varepsilon}(n)}\leq\frac{\beta\gamma}{\gamma+1-\beta}$
$\displaystyle\iff\quad
n-1\geq\frac{1}{w^{\star}_{\beta}(i_{0})_{k_{1}}v_{i_{0}}}\left(h_{\varepsilon}(n)+\frac{\gamma+1-\beta}{\beta\gamma}\right)$

is satisfied since $w^{\star}_{\beta}(i_{0})_{k_{1}}\geq w_{i_{0},-}$,
$v_{i_{0}}\geq v_{\mu,\varepsilon_{0}}(\varepsilon)$ and
$n>C_{2}(w_{i_{0},-},v_{\mu,\varepsilon_{0}}(\varepsilon))$.

Let
$T_{\mu}\geq\max_{k\in[2]}C_{k}(\min_{i\in\mathcal{I}_{\varepsilon}(\mu)}w_{i,-},v_{\mu,\varepsilon_{0}}(\varepsilon))$
and $D_{0}=(1+\gamma)^{2}/\beta$. In summary, we have shown that for all
$n>T_{\mu}$, there exists $i_{0}\in\mathcal{I}_{\varepsilon}(\mu)$ and
$t_{1}\leq n$ with $B_{t_{1}}=i_{0}$ and such that (15) holds.

For $\beta=1/2$, using that $K\geq 2$, $1<1+\gamma^{-1}$ and
$5/2+\gamma^{-1}\leq 3(1+\gamma^{-1})/2$ (since $\gamma\in(0,1/2]$), we obtain
that

$\displaystyle\max_{i\in[2]}C_{i}(w,v)$ $\displaystyle\leq\sup\left\\{n\geq
1\mid
n-1<\frac{1+\gamma^{-1}}{wv}\left(4(2+s)H_{\mu,\varepsilon_{0}}(\varepsilon)\log
n+3K^{2}/4+1\right)\right\\}$
$\displaystyle<h_{1}\left(\frac{4(2+s)(1+\gamma^{-1})}{wv}H_{\mu,\varepsilon_{0}}(\varepsilon),\>\frac{(1+\gamma^{-1})(3K^{2}/4+1)}{wv}+1\right)\>,$

where the last inequality uses Lemma 51 and $h_{1}(x,y)$ defined therein.

Using $w_{i_{0},-}=\min_{i\neq i_{0}}w^{\star}_{\beta}(i_{0})_{i}$ and
$\beta=1/2$, the first part of Theorem 5 (i.e. $x=0$) is obtained by taking
the infimum over $(\varepsilon,x)\in[0,\varepsilon_{0}]\times\\{0\\}$.

Refined Proof of Lemma 34.  When considering large $K$ or instances with
unbalanced $\beta$-optimal allocation,
$\min_{i_{0}\in\mathcal{I}_{\varepsilon}(\mu)}\min_{i\neq
i_{0}}w^{\star}_{\beta}(i_{0})_{i}$ can become arbitrarily small, hence a
dependence in its inverse is undesired. Thanks to the refined analysis from
[20], we can clip it with a value of our choosing which is away from zero.

Let $x\in(0,1/(K-1)]$ be an allocation threshold and
$d_{\mu}(x,i):=|\\{j\in[K]\setminus\\{i\\}\mid\>w^{\star}_{\beta}(i)_{j}<(1-\beta)x\\}|$
for all $i\in\mathcal{I}_{\varepsilon}(\mu)$. The equation (16) is only
informative when (1) $w^{\star}_{\beta}(i_{0})_{k_{1}}\geq(1-\beta)x$ or (2)
$w^{\star}_{\beta}(i_{0})_{k_{1}}<(1-\beta)x$ and $N_{n,k_{1}}^{i_{0}}\geq
x\sum_{j\neq i_{0}}N_{n,j}^{i_{0}}$. The problematic case occurs when (3)
$w^{\star}_{\beta}(i_{0})_{k_{1}}<(1-\beta)x$ and
$N_{n,k_{1}}^{i_{0}}<x\sum_{j\neq i_{0}}N_{n,j}^{i_{0}}$.

When $w^{\star}_{\beta}(i_{0})_{k_{1}}\geq(1-\beta)x$, we can use the above
computations by considering $w_{i_{0},-}=\max\\{(1-\beta)x,\>\min_{i\neq
i_{0}}w^{\star}_{\beta}(i_{0})_{i}\\}$.

When $w^{\star}_{\beta}(i_{0})_{k_{1}}<(1-\beta)x$ and
$N_{n,k_{1}}^{i_{0}}\geq x\sum_{j\neq i_{0}}N_{n,j}^{i_{0}}$, the above proof
can be conducted by using $(1-\beta)x$ instead of
$w^{\star}_{\beta}(i_{0})_{k_{1}}$ since we will obtain that

$\displaystyle
N_{t_{1},k_{1}}^{i_{0}}\geq(1-\beta)xv_{i_{0}}(n-1)-h_{\varepsilon}(n)\quad\text{and}\quad
1/\beta+\frac{1}{(1-\beta)x}\leq
1/\beta+1/w^{\star}_{\beta}(i_{0})_{k_{1}}\>.$

Then, we can likewise consider $w_{i_{0},-}=\max\\{(1-\beta)x,\>\min_{i\neq
i_{0}}w^{\star}_{\beta}(i_{0})_{i}\\}$ to conclude.

When $w^{\star}_{\beta}(i_{0})_{k_{1}}<(1-\beta)x$ and
$N_{n,k_{1}}^{i_{0}}<x\sum_{j\neq i_{0}}N_{n,j}^{i_{0}}$, as in (16), the
pigeonhole principle yields that there exists
$k_{2}\in[K]\setminus\\{i_{0},k_{1}\\}$ such that

$N_{n,k_{2}}^{i_{0}}\geq\frac{w^{\star}_{\beta}(i_{0})_{k_{2}}}{1-\beta-w^{\star}_{\beta}(i_{0})_{k_{1}}}\sum_{j\notin\\{i_{0},k_{1}\\}}N_{n,j}^{i_{0}}\geq\frac{(1-x)w^{\star}_{\beta}(i_{0})_{k_{2}}}{1-\beta}\sum_{j\neq
i_{0}}N_{n,j}^{i_{0}}\>.$

Based on $k_{2}$ the same dichotomy as for $k_{1}$ 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}(i_{0})_{k_{2}}<(1-\beta)x$ and
$N_{n,k_{2}}^{i_{0}}<x\sum_{j\notin\\{i_{0},k_{1}\\}}N_{n,j}^{i_{0}}$, we
should also ignore it since it is non informative and construct a third arm
$k_{3}$.

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 (1)
$w^{\star}_{\beta}(i_{0})_{k_{d}}\geq(1-\beta)x$ or (2)
$w^{\star}_{\beta}(i_{0})_{k_{d}}<(1-\beta)x$ and $N_{n,k_{d}}^{i_{0}}\geq
x\sum_{j\notin\\{i_{0}\\}\cup\\{k_{a}\\}_{a\in[d-1]}}N_{n,j}^{i_{0}}$ holds.
This means that for all $a\in[d-1]$, we have
$w^{\star}_{\beta}(i_{0})_{k_{a}}<(1-\beta)x$ and

$N_{n,k_{a}}^{i_{0}}<x\sum_{j\notin\\{i_{0}\\}\cup\\{k_{b}\\}_{b\in[a-1]}}N_{n,j}^{i_{0}}\>.$

Using the pigeonhole principle for
$i\in[K]\setminus\left(\\{i_{0}\\}\cup\\{k_{a}\\}_{a\in[d-1]}\right)$ yields
that $k_{d}$ satisfies

$\displaystyle
N_{n,k_{d}}^{i_{0}}\geq\frac{w^{\star}_{\beta}(i_{0})_{k_{d}}}{1-\beta-\sum_{a\in[d-1]}w^{\star}_{\beta}(i_{0})_{k_{a}}}\sum_{j\notin\\{i_{0}\\}\cup\\{k_{b}\\}_{b\in[a-1]}}N_{n,j}^{i_{0}}\>,$

Using a simple recurrence on the arms $\\{k_{a}\\}_{a\in[d-1]}$, we obtain
that

$\sum_{j\notin\\{i_{0}\\}\cup\\{k_{b}\\}_{b\in[a-1]}}N_{n,j}^{i_{0}}\geq(1-x)^{d-1}\sum_{j\neq
i_{0}}N_{n,j}^{i_{0}}\>.$

Let $t_{d}:=\sup\left\\{t<n\mid(B_{t},C_{t})=(i_{0},k_{d})\right\\}$. Since
the arm $k_{d}$ satisfies case 1 or case 2, we can conclude similarly as above
with an extra multiplicative factor $(1-x)^{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_{0}\\}\mid\>w^{\star}_{\beta}(i_{0})_{i}<(1-\beta)x\\}$,
i.e. $d-1\leq d_{\mu}(x,i_{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. Let
$d_{\mu,\varepsilon}(x)=\max_{i\in\mathcal{I}_{\varepsilon}(\mu)}d_{\mu}(x,i)$.
Using that

$\displaystyle(1-x)^{d-1}\geq(1-x)^{d_{\mu}(x,i_{0})}\geq(1-x)^{d_{\mu,\varepsilon}(x)}\>,$
$\displaystyle
w_{i_{0},-}=(1-x)^{d_{\mu}(x,i_{0})}\max\\{(1-\beta)x,\>\min_{i\neq
i_{0}}w^{\star}_{\beta}(i_{0})_{i}\\}\>,$

we can conclude the proof by taking
$T_{\mu}\geq\max_{k\in[2]}C_{k}(\min_{i\in\mathcal{I}_{\varepsilon}(\mu)}w_{i,-},v_{\mu,\varepsilon_{0}}(\varepsilon))$
and $D_{0}=\frac{(1+\gamma)^{2}}{\beta(1-x)^{d_{\mu,\varepsilon}(x)}}$. In
other words, we have shown that $n>T_{\mu}$, there exists
$i_{0}\in\mathcal{I}_{\varepsilon}(\mu)$ and $t_{d}\leq n$ with
$B_{t_{d}}=i_{0}$ and such that (15) holds. Using $\beta=1/2$, the second part
of Theorem 5 is obtained by taking the infimum over
$(\varepsilon,x)\in[0,\varepsilon_{0}]\times(0,1/(K-1)]$. ∎

####  E.2.1 Consequence of tighter concentration

It is direct to see that the proof of Theorem 5 will also work when using the
concentration event
$\tilde{\mathcal{E}}_{n}=\tilde{\mathcal{E}}^{1}_{n,1}\cap\tilde{\mathcal{E}}^{2}_{n,1}$
with $(\tilde{\mathcal{E}}^{1}_{n,\delta})_{n>K}$ and
$(\tilde{\mathcal{E}}^{2}_{n,\delta})_{n>K}$ as in (27) and (29). Let us
define

$\displaystyle\tilde{f}_{1}(n)$
$\displaystyle=\frac{1}{2}\overline{W}_{-1}(2s\log n+2\log(2+\log n)+2)\>,$
$\displaystyle\tilde{f}_{2}(n)$ $\displaystyle=\overline{W}_{-1}\left(s\log
n+2\log\left(2+\log n\right)+2\right)\>.$

Using Lemma 50, we know that $\tilde{f}_{1}(n)\leq\tilde{f}_{2}(n)$. Then, we
will be able to show

$\mathbb{E}_{\nu}[\tau_{\delta}]\leq\inf_{(\varepsilon,x)\in[0,\varepsilon_{0}]\times[0,1/(K-1)]}\max\left\\{\tilde{T}_{\mu,\varepsilon_{0}}(\delta,\varepsilon,x)+1,\>\tilde{S}_{\mu,\varepsilon_{0}}(\varepsilon,x)\right\\}+\zeta(s)K(K+1)/2\>,$

where

$\displaystyle\tilde{T}_{\mu,\varepsilon_{0}}(\delta,\varepsilon,x)=\sup\left\\{n\mid
n-1\leq\frac{2(1+\gamma)^{2}\sum_{i\in\mathcal{I}_{\varepsilon}(\mu)}T_{\varepsilon_{0},1/2}(\mu,i)}{(1-x)^{d_{\mu,\varepsilon_{0}}(\varepsilon,x)}}\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\left.\left(\sqrt{c(n-1,\delta)}+\sqrt{\tilde{f}_{2}(n)}\right)^{2}\right\\}\>,$
$\displaystyle\tilde{S}_{\mu,\varepsilon_{0}}(\varepsilon,x)=\tilde{h}_{1}\left(\frac{4(1+\gamma^{-1})}{a_{\mu,\varepsilon_{0}}(\varepsilon,x)v_{\mu,\varepsilon_{0}}(\varepsilon)}H_{\mu,\varepsilon_{0}}(\varepsilon),\>\frac{(1+\gamma^{-1})(3K^{2}/4+1)}{a_{\mu,\varepsilon_{0}}(\varepsilon,x)v_{\mu,\varepsilon_{0}}(\varepsilon)}+1\right)\>,$

with $\tilde{h}_{1}(z,y)>\sup\left\\{n\geq 1\mid
n<z\tilde{f}_{2}(n)+y\right\\}$. Using Lemma 49, we obtain that

$\displaystyle n\geq
z\tilde{f}_{2}(n)+y\quad\iff\quad\frac{n-y}{z}-\log(n-y)\geq s\log
n+2\log\left(2+\log n\right)+2-\log z$
$\displaystyle\impliedby\>\frac{n}{z(1+s)}-\log\frac{n}{z(1+s)}\geq\log(1+s)+\frac{s}{s+1}\log
z+\frac{1}{1+s}(2\log\left(2+\log n\right)+2+\frac{y}{z})\>.$

Therefore, we can consider $\tilde{h}_{1}(z,y)\geq z(1+s)h_{2}(z,y)$ with

$h_{2}(z,y)=\sup\left\\{x\mid x-\log x-\frac{2}{1+s}\log(\log
x+2+\log(z(1+s)))<C(z,y)\right\\}$

where $C(z,y)=\frac{y}{(1+s)z}+\frac{s}{s+1}\log z+\log(1+s)+\frac{2}{1+s}$.
Therefore, we will obtain a mulitplicative factor $(1+s)$ instead of $(2+s)$
in front of $H_{\mu,\varepsilon_{0}}(\varepsilon)$. This improvement is rather
mild, hence we don’t elaborate on it further.

##  Appendix F Probability of error and simple regret

Let $\varepsilon_{0}>0$ and $\beta\in(0,1)$. In Appendix F, we provide an
analysis on the probability of error and the simple regret of EB-
TC${}_{\varepsilon_{0}}$ with fixed proportions $\beta$ and slack
$\varepsilon_{0}>0$ (Theorem 6 proved in Appendix F.1). In Appendix F.2, we
provide an upper bound on the unverifiable expected sample complexity of EB-
TC${}_{\varepsilon_{0}}$ (Theorem 7). Then, by using Theorem 6, we prove that
the policy pulling arm $\hat{\imath}_{n}$ at time $n$ has a constant induced
regret (Corollary 2 proved in Appendix F.3). In practice, we will mostly be
interested in the case $\beta=1/2$.

Theorem 3 and Corollary 1 is a corollary of Theorem 6 up to some additional
computations on the complexities
$(H_{i}(\mu,\varepsilon_{0}))_{i\in[C_{\mu}-1]}$, which we will detail below.
Theorem 6 provides upper bound on
$\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu)\right)$
holding for any time $n$ and any error $\varepsilon\geq 0$, and upper bound on
$\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]$ holding for any time
$n$.

######  Theorem 6.

Let $\varepsilon_{0}>0$. For all $\varepsilon\geq 0$, let
$i_{\mu}(\varepsilon)=i$ if $\varepsilon\in[\Delta_{i},\Delta_{i+1})$ and
$i\in[C_{\mu}-1]$, otherwise $i_{\mu}(\varepsilon)=C_{\mu}$. For all
$i\in[C_{\mu}-1]$, let
$C_{i}(\varepsilon_{0})=2\Delta_{i}^{-1}-\varepsilon_{0}^{-1}$ and
$C_{i,j}(\varepsilon_{0})=2\frac{\Delta_{j}/\varepsilon_{0}+1}{\Delta_{i}-\Delta_{j}}+3\varepsilon_{0}^{-1}$.
For all $i\in[C_{\mu}-1]$, let
$H_{i}(\mu,\varepsilon_{0}):=\min_{j\in[i]}\max\\{\bar{H}_{i,j}(\mu,\varepsilon_{0}),\>\tilde{H}_{i,j}(\mu,\varepsilon_{0})\\}$
where

$\displaystyle\bar{H}_{i,j}(\mu,\varepsilon_{0})$
$\displaystyle:=|i^{\star}(\mu)|\max\left\\{\sqrt{2}\Delta^{-1}_{j+1},\>C_{i+1,j}(\varepsilon_{0})\right\\}^{2}$
$\displaystyle\quad+\max\left\\{C_{j+1}(\varepsilon_{0}),\>C_{i+1,j}(\varepsilon_{0})\right\\}^{2}\left(\sum_{k=2}^{j}|\mathcal{C}_{\mu}(k)|+\sum_{k=i+1}^{C_{\mu}}|\mathcal{C}_{\mu}(k)|\right)$
$\displaystyle\quad+\sum_{k=j+1}^{i}|\mathcal{C}_{\mu}(k)|\max\left\\{C_{j+1}(\varepsilon_{0}),\>C_{i+1,j}(\varepsilon_{0}),\sqrt{2}\Delta_{k}^{-1}\right\\}^{2}\>,$
$\displaystyle\tilde{H}_{i,j}(\mu,\varepsilon_{0})$
$\displaystyle:=\frac{2|i^{\star}(\mu)|}{\Delta^{2}_{j+1}}+\max\left\\{C_{j+1}(\varepsilon_{0}),\varepsilon_{0}^{-1}\right\\}^{2}\sum_{k=2}^{j}|\mathcal{C}_{\mu}(k)|+\frac{2\sum_{k=1}^{j}|\mathcal{C}_{\mu}(k)|}{(\Delta_{i+1}-\Delta_{j})^{2}}$
$\displaystyle\quad+\sum_{k=j+1}^{C_{\mu}}|\mathcal{C}_{\mu}(k)|\max\left\\{C_{j+1}(\varepsilon_{0}),\varepsilon_{0}^{-1},\sqrt{2}\Delta_{k}^{-1}\right\\}^{2}\>.$

The EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed proportions $\beta=1/2$
satisfies that, for all $\nu\in\mathcal{D}^{K}$ and all $n\geq D_{\mu}$, if
the algorithm has not stopped yet, then

$\displaystyle\forall\varepsilon\geq 0,\quad$
$\displaystyle\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu)\right)\leq\mathds{1}\left(\varepsilon<\Delta_{\max}\right)\frac{K(K+1)}{2}e^{2}(2+\log
n)^{2}p\left(\frac{n-5K^{2}/2}{8H_{i_{\mu}(\varepsilon)}(\mu,\varepsilon_{0})}\right)\>,$
$\displaystyle\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]\leq\frac{K(K+1)}{2}e^{2}(2+\log
n)^{2}\sum_{i\in[C_{\mu}-1]}(\Delta_{i+1}-\Delta_{i})p\left(\frac{n-5K^{2}/2}{8H_{i}(\mu,\varepsilon_{0})}\right)\>.$

where $p(x)=x\exp(-x)$ and
$D_{\mu}=8H_{1}(\mu,\varepsilon_{0})h_{2}\left(8H_{1}(\mu,\varepsilon_{0}),5K^{2}/2,2+\log\left(K(K+1)/2\right)\right)+5K^{2}/2$
with $h_{2}$ defined in Lemma 51.

##### Hardness of BAI

We have $C_{2}(\varepsilon_{0})=2\Delta_{\min}^{-1}-\varepsilon_{0}^{-1}$ and
$C_{2,1}(\varepsilon_{0})=2\Delta_{\min}^{-1}+3\varepsilon_{0}^{-1}$. Then, we
obtain
$H_{1}(\mu,\varepsilon_{0})=\bar{H}_{1,1}(\mu,\varepsilon_{0})=K(2\Delta_{\min}^{-1}+3\varepsilon_{0}^{-1})^{2}$
since

$\tilde{H}_{1,1}(\mu,\varepsilon_{0})=4|i^{\star}(\mu)|\Delta_{\min}^{-2}+\sum_{k=2}^{C_{\mu}}|\mathcal{C}_{\mu}(k)|\max\left\\{C_{2}(\varepsilon_{0}),\varepsilon_{0}^{-1},\sqrt{2}\Delta_{k}^{-1}\right\\}^{2}\>.$

This corresponds to the complexity of the two-groups instances which are
defined as
$\mathcal{D}_{\Delta}:=\left\\{\nu\in\mathcal{D}^{K}\mid\>C_{\mu}=2,\Delta_{2}=\Delta\right\\}$
where $\Delta>0$. More importantly, it corresponds to the complexity of
identifying one of the best arms, i.e. taking $\varepsilon=0$ yields

$\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin
i^{\star}(\mu)\right)\leq\frac{K(K+1)}{2}e^{2}(2+\log
n)^{2}p\left(\frac{n-5K^{2}/2}{8K(2\Delta_{\min}^{-1}+3\varepsilon_{0}^{-1})^{2}}\right)\>.$

##### Hardness of $\varepsilon$-BAI

Let $i>1$ and $j\in[i]$. We have
$C_{i+1,j}(\varepsilon_{0})=2\frac{\Delta_{j}/\varepsilon_{0}+1}{\Delta_{i+1}-\Delta_{j}}+3\varepsilon_{0}^{-1}$,
$C_{j+1}(\varepsilon_{0})=2\Delta_{j+1}^{-1}-\varepsilon_{0}^{-1}\leq
2\Delta_{j+1}^{-1}$ and $\sqrt{2}\Delta_{k}^{-1}\leq 2\Delta_{j+1}^{-1}$ for
all $k\geq j+1$. Direct manipulations show that, for all $i>1$ and all
$j\in[i]$, we have

$\max\\{\bar{H}_{i,j}(\mu,\varepsilon_{0}),\tilde{H}_{i,j}(\mu,\varepsilon_{0})\\}\leq
K\max\left\\{2\Delta_{j+1}^{-1},\>2\frac{\Delta_{j}/\varepsilon_{0}+1}{\Delta_{i+1}-\Delta_{j}}+3\varepsilon_{0}^{-1}\right\\}^{2}\>.$

Therefore, we have

$H_{i}(\mu,\varepsilon_{0})\leq
K\min_{j\in[i]}\max\left\\{2\Delta_{j+1}^{-1},\>2\frac{\Delta_{j}/\varepsilon_{0}+1}{\Delta_{i+1}-\Delta_{j}}+3\varepsilon_{0}^{-1}\right\\}^{2}\>.$

Taking $j=1$ and then $j=2$, we see that, for all $i>1$,

$\displaystyle H_{i}(\mu,\varepsilon_{0})$ $\displaystyle\leq
K\max\left\\{2\Delta_{\min}^{-1},\>3\varepsilon_{0}^{-1}+2\Delta_{i+1}^{-1}\right\\}^{2}<H_{1}(\mu,\varepsilon_{0})\>,$
$\displaystyle H_{i}(\mu,\varepsilon_{0})$ $\displaystyle\leq
K\max\left\\{2\Delta_{3}^{-1},\>2\frac{\Delta_{\min}/\varepsilon_{0}+1}{\Delta_{i+1}-\Delta_{\min}}+3\varepsilon_{0}^{-1}\right\\}^{2}\leq
K\max\left\\{2\frac{\Delta_{\min}/\varepsilon_{0}+1}{\Delta_{3}-\Delta_{\min}}+3\varepsilon_{0}^{-1}\right\\}^{2}\>,$

where the last inequality uses that $\Delta_{3}\leq\Delta_{i+1}$ for all
$i>1$.

Similarly, we can derive a lower bound on $H_{i}(\mu,\varepsilon_{0})$ by
noting that
$H_{i}(\mu,\varepsilon_{0})\geq\min_{j\in[i]}\bar{H}_{i,j}(\mu,\varepsilon_{0})$.
For all $j\in[i]$, we have that
$\sqrt{2}\Delta_{j+1}^{-1}\geq\sqrt{2}\Delta_{i+1}^{-1}$,
$C_{j+1}(\varepsilon_{0})\geq 2\Delta_{i+1}^{-1}-\varepsilon_{0}^{-1}$ and
$C_{i+1,j}(\varepsilon_{0})\geq 2\Delta_{i+1}^{-1}+3\varepsilon_{0}^{-1}$,
hence we obtain

$H_{i}(\mu,\varepsilon_{0})\geq\min_{j\in[i]}\bar{H}_{i,j}(\mu,\varepsilon_{0})\geq
2K\Delta_{i+1}^{-2}\>.$

##### Three-groups instances

The three-groups instances are defined as
$\mathcal{D}_{\Delta,\Lambda}:=\left\\{\nu\in\mathcal{D}^{K}\mid\>C_{\mu}=3,\Delta_{2}=\Delta,\Delta_{3}=\Lambda\right\\}$
where $\Delta>0$ and $\Lambda>\Delta$. Above results yield

$H_{2}(\mu,\varepsilon_{0})\leq
K\left(2\frac{\Delta/\varepsilon_{0}+1}{\Lambda-\Delta}+3\varepsilon_{0}^{-1}\right)^{2}=\mathcal{O}\left(\frac{K}{\min\\{\Lambda-\Delta,\varepsilon_{0}\\}^{2}}\right)\>.$

###  F.1 Proof of Theorem 6

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

Let $\Delta_{\max}=\max_{i\in[K]}\mu_{\star}-\mu_{i}$. Let $\varepsilon_{1}$
be an analysis parameter (i.e. not the error parameter from the stopping rule
(3)). When $\varepsilon_{1}\geq\Delta_{\max}$, we have
$\mathcal{I}_{\varepsilon_{1}}(\mu)^{\complement}=\emptyset$, hence
$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu))=0$.
In the following, we consider $\varepsilon_{1}\in[0,\Delta_{\max})$.

For all $n>K$ and $\delta\in(0,1)$, let
$\tilde{\mathcal{E}}_{n,\delta}=\tilde{\mathcal{E}}^{1}_{n,\delta}\cap\tilde{\mathcal{E}}^{2}_{n,\delta}$
with $(\tilde{\mathcal{E}}^{1}_{n,\delta})_{n>K}$ and
$(\tilde{\mathcal{E}}^{2}_{n,\delta})_{n>K}$ as in (27) and (29) for $s=0$,
i.e.

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

where

$\displaystyle\tilde{f}_{1}(n,\delta)$
$\displaystyle=\frac{1}{2}\overline{W}_{-1}(2\log(1/\delta)+2\log(2+\log
n)+2)\>,$ $\displaystyle\tilde{f}_{2}(n,\delta)$
$\displaystyle=\overline{W}_{-1}\left(\log\left(1/\delta\right)+2\log\left(2+\log
n\right)+2\right)\>.$

Using Lemma 50, we know that
$\tilde{f}_{1}(n,\delta)\leq\tilde{f}_{2}(n,\delta)$. Using Lemmas 42 and 44,
we obtain that
$\mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n,\delta}^{\complement})\leq\frac{K(K+1)}{2}\delta$.

Suppose that we have constructed a time $T_{\varepsilon_{1}}(\delta)>K$ such
that
$\tilde{\mathcal{E}}_{n,\delta}\subseteq\\{\hat{\imath}_{n}\in\mathcal{I}_{\varepsilon_{1}}(\mu)\\}$
for $n>T_{\varepsilon_{1}}(\delta)$. Then, using Lemma 48, we obtain

$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu))\leq\frac{K(K+1)}{2}\inf\\{\delta\mid\>n>T_{\varepsilon_{1}}(\delta)\\}\>.$

We will construct an infinite number of times
$\\{T_{\varepsilon_{1}}(\delta,\varepsilon)\\}_{\varepsilon\in[0,\varepsilon_{1}]}$
such that the above property holds, hence taking the infimum yields

$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu))\leq\frac{K(K+1)}{2}\inf\\{\delta\mid\>n>\inf_{\varepsilon\in[0,\varepsilon_{1}]}T_{\varepsilon_{1}}(\delta,\varepsilon)\\}\>.$

This proof strategy is the one used to prove Theorem 6.

Let $\varepsilon\in[0,\varepsilon_{1}]$. Since
$\hat{\imath}_{n}=B^{\text{EB}}_{n}$, our goal is to construct a time
$T_{\varepsilon_{1}}(\delta,\varepsilon)$ such that

$\forall
n>T_{\varepsilon_{1}}(\delta,\varepsilon),\quad\tilde{\mathcal{E}}_{n,\delta}\cap\\{B^{\text{EB}}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\\}=\emptyset\>.$

##### Error due to undersampled arms

Let us denote by $U_{\varepsilon,\varepsilon_{1},t}(n,\delta)$ the set of
undersampled arms which are not $\varepsilon_{1}$-good, i.e.

$U_{\varepsilon,\varepsilon_{1},t}(n,\delta):=\mathcal{I}_{\varepsilon_{1}}(\mu)^{\complement}\cap\left\\{i\mid\>N_{t,i}\leq
4C_{\varepsilon,i}\tilde{f}_{2}(n,\delta)\right\\}\quad\text{with}\quad
C_{\varepsilon,i}:=\frac{2}{\min_{k\in\mathcal{I}_{\varepsilon}(\mu)}(\Delta_{i}-\Delta_{k})^{2}}\>.$

Lemma 35 shows that, for $n$ large enough, a necessary condition for an error
to occur is to have an undersampled leader.

######  Lemma 35.

Let $\varepsilon_{1}>0$ and $\varepsilon\in[0,\varepsilon_{1}]$. Let
$H_{\mu,\varepsilon_{0}}(\varepsilon)$ as in Lemma 5 and define

$\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0}):=H_{\mu,\varepsilon_{0}}(\varepsilon)+\frac{2|\mathcal{I}_{\varepsilon}(\mu)|}{\min_{(i,j)\in\mathcal{I}_{\varepsilon}(\mu)\times\mathcal{I}_{\varepsilon_{1}}(\mu)^{\complement}}(\Delta_{j}-\Delta_{i})^{2}}\>.$
(19)

Let us define

$S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)=\sup\left\\{n\mid
n\leq\frac{4\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})}{\min\\{\beta,1-\beta\\}}\tilde{f}_{2}(n,\delta)+(3/2+1/\beta)K^{2}\right\\}\>.$

For all $n>S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$, under
the event $\tilde{\mathcal{E}}_{n,\delta}$, we have
$B^{\text{EB}}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$ implies that
$B^{\text{EB}}_{n}\in U_{\varepsilon,\varepsilon_{1},n}(n,\delta)$.

###### Proof.

Let $|\mathcal{I}_{\varepsilon}(\mu)|=I_{\varepsilon}$ and
$g_{\varepsilon,\varepsilon_{0}}(n,\delta)=\frac{4H_{\mu,\varepsilon_{0}}(\varepsilon)}{\min\\{\beta,1-\beta\\}}\tilde{f}_{2}(n,\delta)+3K(K-1)/2$.
Using Lemma 5 and the pigeonhole principle, there exists
$i_{0}\in\mathcal{I}_{\varepsilon}(\mu)$ such that

$\displaystyle\sum_{j}T_{n}(i_{0},j)\geq\left(n-1-g_{\varepsilon,\varepsilon_{0}}(n,\delta)\right)/I_{\varepsilon}\>.$

Therefore, we have

$N_{n,i_{0}}\geq\beta\sum_{j}T_{n}(i_{0},j)-(K-1)\geq\beta\left(n-1-g_{\varepsilon,\varepsilon_{0}}(n,\delta)\right)/I_{\varepsilon}-(K-1)\>.$

Let $S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$ defined as
in the statement of Lemma 35. Direct manipulations shows that

$S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)\geq\sup\left\\{n\mid
n-1\leq
g_{\varepsilon,\varepsilon_{0}}(n,\delta)+\frac{I_{\varepsilon}}{\beta}\left(4\tilde{f}_{2}(n,\delta)\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}C_{\varepsilon,i}+K-1\right)\right\\}\>.$

Therefore, we have
$N_{n,i_{0}}>4\tilde{f}_{2}(n,\delta)\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}C_{\varepsilon,i}$
for all $n>S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$.

Let $n>S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$. Suppose
that $B^{\text{EB}}_{n}=i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$. Using
Lemma 31, under the event $\tilde{\mathcal{E}}_{n,\delta}$, we obtain that

$\min\\{N_{n,i},N_{n,i_{0}}\\}\leq\frac{8\tilde{f}_{1}(n,\delta)}{(\mu_{i_{0}}-\mu_{i})^{2}}\leq
4C_{\varepsilon,i}\tilde{f}_{2}(n,\delta)\>.$

Suppose towards contradiction that
$\min\\{N_{n,i},N_{n,i_{0}}\\}=N_{n,i_{0}}$, then we have $N_{n,i_{0}}\leq
4C_{\varepsilon,i}\tilde{f}_{2}(n,\delta)$. This is a direct contradiction
with
$N_{n,i_{0}}>4\tilde{f}_{2}(n,\delta)\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}C_{\varepsilon,i}$
since $n>S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$.
Therefore, we have shown that $\min\\{N_{n,i},N_{n,i_{0}}\\}=N_{n,i}$, hence
$i\in U_{\varepsilon,\varepsilon_{1},n}(n,\delta)$. This concludes the proof.
∎

##### No remaining undersampled arms

Lemma 36 shows that, if there are still undersampled arms which are not
$\varepsilon_{1}$-good, then either the leader or the challenger was not often
selected as leader or challenger.

######  Lemma 36.

Let $\varepsilon_{1}\geq 0$ and $\varepsilon\in[0,\varepsilon_{1}]$. Let
$\Delta_{\mu}(\varepsilon)=\min_{k\notin\mathcal{I}_{\varepsilon}(\mu)}\Delta_{k}$,
$C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})=2\max_{j\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}\frac{\Delta_{j}/\varepsilon_{0}+1}{\min_{k\in\mathcal{I}_{\varepsilon}(\mu)}(\Delta_{j}-\Delta_{k})}+\varepsilon_{0}^{-1}$
and
$C_{\mu,\varepsilon_{0}}(\varepsilon)=2/\Delta_{\mu}(\varepsilon)-\varepsilon_{0}^{-1}$.
Let
$A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i}=\max\\{2/\Delta_{\mu}(\varepsilon)^{2},C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})^{2}\\}$
for all $i\in i^{\star}(\mu)$,
$A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i}=\max\\{C_{\mu,\varepsilon_{0}}(\varepsilon)^{2},C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})^{2}\\}$
for all $i\in(\mathcal{I}_{\varepsilon}(\mu)\setminus
i^{\star}(\mu))\cup([K]\setminus\mathcal{I}_{\varepsilon_{1}}(\mu))$, and
otherwise
$A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i}=\max\\{C_{\mu,\varepsilon_{0}}(\varepsilon)^{2},C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})^{2},2/\Delta_{i}^{2}\\}$
for all
$i\in\mathcal{I}_{\varepsilon_{1}}(\mu)\setminus\mathcal{I}_{\varepsilon}(\mu)$.
For all $n>K$, under event $\tilde{\mathcal{E}}_{n,\delta}$, for all
$t\in[n]\setminus[K]$ such that
$U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset$, there exists
$i_{t}\in[K]$ such that

$T_{t}(i_{t})\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i_{t}}+3(K-1)/2\quad\text{and}\quad
T_{t+1}(i_{t})=T_{t}(i_{t})+1\>.$

###### Proof.

We will be interested in three distinct cases since

$\displaystyle\left\\{U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset\right\\}=\left\\{U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\cap\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}\neq\emptyset\right\\}$
$\displaystyle\quad\cup\left\\{U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset,\>U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\cap\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}=\emptyset,\>B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)\right\\}$
$\displaystyle\quad\cup\left\\{U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset,\>U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\cap\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}=\emptyset,\>B^{\text{EB}}_{t}\in\mathcal{I}_{\varepsilon}(\mu)\right\\}\>,$

Case 1. Let $t\in[n]\setminus[K]$ such that
$\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}\cap
U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset$. Let
$k_{t}\in\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}\cap
U_{\varepsilon,\varepsilon_{1},t}(n,\delta)$. For this
$k_{t}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$, we have
$T_{t+1}(k_{t})=T_{t}(k_{t})+1$ and, by combining Lemma 31 and
$N_{t,k_{t}}\leq 4C_{\varepsilon,k_{t}}\tilde{f}_{2}(n,\delta)$, we obtain
that

$\displaystyle
T_{t}(k_{t})\leq\frac{N_{t,k_{t}}}{\min\\{\beta,1-\beta\\}}+\frac{3(K-1)}{2}\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}C_{\varepsilon,k_{t}}+3(K-1)/2\>.$

Case 2. Let $t\in[n]\setminus[K]$ such that
$U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset$,
$U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\cap\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}=\emptyset$
and $B^{\text{EB}}_{t}\notin\mathcal{I}_{\varepsilon}(\mu)$. Let
$\Delta_{\mu}(\varepsilon)$ and $C_{\mu,\varepsilon_{0}}(\varepsilon)$ defined
as in the statement of Lemma 36. Let
$D_{\varepsilon_{0},\varepsilon,i}=2/\Delta_{\mu}(\varepsilon)^{2}$ for all
$i\in i^{\star}(\mu)$,
$D_{\varepsilon_{0},\varepsilon,i}=C_{\mu,\varepsilon_{0}}(\varepsilon)$ for
all $i\in\mathcal{I}_{\varepsilon}(\mu)\setminus i^{\star}(\mu)$, otherwise
$D_{\varepsilon_{0},\varepsilon,i}=\max\\{C_{\mu,\varepsilon_{0}}(\varepsilon),2/\Delta_{i}^{2}\\}$.
Using Lemma 32, there exists $k_{t}\in[K]$ such that

$T_{t}(k_{t})\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}D_{\varepsilon,\varepsilon_{0},k_{t}}+3(K-1)/2\quad\text{and}\quad
T_{t+1}(k_{t})=T_{t}(k_{t})+1\>.$

Case 3. Let $t\in[n]\setminus[K]$ such that
$U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset$,
$U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\cap\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}=\emptyset$
and $B^{\text{EB}}_{t}\in\mathcal{I}_{\varepsilon}(\mu)$. Let $j_{0}\in
U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\setminus\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}$,
which is possible since
$U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\cap\\{B^{\text{EB}}_{t},C^{\text{TC}}_{t}\\}=\emptyset$
and $U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset$. Let us denote
by $(B^{\text{EB}}_{t},C^{\text{TC}}_{t})=(i,j)$ with
$i\in\mathcal{I}_{\varepsilon}(\mu)$ and $j\neq j_{0}$. Using the TC
challenger, under the event $\mathcal{E}_{n,\delta}$, we obtain

$\displaystyle\frac{\mu_{i}-\mu_{j_{0}}+\varepsilon_{0}}{\sqrt{1/N_{t,i}+1/N_{t,j_{0}}}}+\sqrt{2\tilde{f}_{2}(n,\delta)}\geq\frac{\mu_{t,i}-\mu_{t,j_{0}}+\varepsilon_{0}}{\sqrt{1/N_{t,i}+1/N_{t,j_{0}}}}$
$\displaystyle\geq\frac{\mu_{t,i}-\mu_{t,j}+\varepsilon_{0}}{\sqrt{1/N_{t,i}+1/N_{t,j}}}$
$\displaystyle\geq\varepsilon_{0}\sqrt{\min\\{N_{t,i},N_{t,j}\\}/2}\>.$

Since $\mu_{i}-\mu_{j_{0}}+\varepsilon_{0}\geq\varepsilon_{0}>0$, we have

$\displaystyle\frac{\mu_{i}-\mu_{j_{0}}+\varepsilon_{0}}{\sqrt{1/N_{t,i}+1/N_{t,j_{0}}}}$
$\displaystyle\leq\sqrt{N_{t,j_{0}}}(\mu_{i}-\mu_{j_{0}}+\varepsilon_{0})+\sqrt{2\tilde{f}_{2}(n,\delta)}$
$\displaystyle\leq\left(2\frac{\mu_{i}-\mu_{j_{0}}+\varepsilon_{0}}{\min_{k\in\mathcal{I}_{\varepsilon}(\mu)}(\mu_{k}-\mu_{j_{0}})}+1\right)\sqrt{2\tilde{f}_{2}(n,\delta)}\>.$

Using Lemma 31 to lower bound $\min\\{N_{t,i},N_{t,j}\\}$ and
$\mu_{i}-\mu_{j_{0}}\leq\Delta_{j_{0}}$ for all
$i\in\mathcal{I}_{\varepsilon}(\mu)$, direct manipulation yields that

$\displaystyle\min\\{T_{t}(i),T_{t}(j)\\}\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})^{2}+3(K-1)/2\>.$

where $C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})$ is defined as in
the statement of Lemma 36. It is direct to see that
$C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})^{2}\geq\max\\{1/\varepsilon_{0}^{2},\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}C_{\varepsilon,i}\\}$
and $C_{\varepsilon,i}\geq 2/\Delta_{i}^{2}$ for all
$i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$. The above shows that there exists
$k_{t}\in[K]$ such that

$T_{t}(k_{t})\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})^{2}+3(K-1)/2\quad\text{and}\quad
T_{t+1}(k_{t})=T_{t}(k_{t})+1\>.$

Summary. Let us define
$(A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i})_{i\in[K]}$ as in the
statement of Lemma 36. Under $\tilde{\mathcal{E}}_{n,\delta}$, we have show
that, when $U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset$, there
exists $i_{t}\in[K]$ such that

$T_{t}(i_{t})\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i_{t}}+3(K-1)/2\quad\text{and}\quad
T_{t+1}(i_{t})=T_{t}(i_{t})+1\>.$

∎

Lemma 37 shows that, for $n$ large enough, there is no undersampled arms which
are not $\varepsilon_{1}$-good.

######  Lemma 37.

Let $\varepsilon_{1}\geq 0$ and $\varepsilon\in[0,\varepsilon_{1}]$. Let
$\Delta_{\mu}(\varepsilon)$,
$C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})$ and
$C_{\mu,\varepsilon_{0}}(\varepsilon)$ as in Lemma 36 and

$\displaystyle\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})$
$\displaystyle:=|i^{\star}(\mu)|\max\\{\sqrt{2}\Delta_{\mu}(\varepsilon)^{-1},C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})\\}^{2}\>$
$\displaystyle\quad+|(\mathcal{I}_{\varepsilon}(\mu)\setminus
i^{\star}(\mu))\cup([K]\setminus\mathcal{I}_{\varepsilon_{1}}(\mu))|\max\\{C_{\mu,\varepsilon_{0}}(\varepsilon),C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1})\\}^{2}\>$
$\displaystyle\quad+\sum_{i\in\mathcal{I}_{\varepsilon_{1}}(\mu)\setminus\mathcal{I}_{\varepsilon}(\mu)}\max\\{C_{\mu,\varepsilon_{0}}(\varepsilon),C_{\mu,\varepsilon_{0}}(\varepsilon,\varepsilon_{1}),\sqrt{2}\Delta_{i}^{-1}\\}^{2}\>\>.$
(20)

Let us define

$T_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)=\sup\left\\{n\mid
n\leq\frac{4\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})}{\min\\{\beta,1-\beta\\}}\tilde{f}_{2}(n,\delta)+3K^{2}/2\right\\}\>.$

For all $n>T_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$, under
the event $\tilde{\mathcal{E}}_{n,\delta}$, we have
$U_{\varepsilon,\varepsilon_{1},n}(n,\delta)=\emptyset$.

###### Proof.

For all $n>K$, under event $\tilde{\mathcal{E}}_{n,\delta}$, combining Lemma 4
and 36 for
$A_{t}(n,\delta)=\\{U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset\\}$
and
$D_{i}(n,\delta)=\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i}+3(K-1)/2$
yields that

$\sum_{t=K+1}^{n}\mathds{1}\left(U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset\right)\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})+3K(K-1)/2\>.$

where we used that
$\sum_{i\in[K]}A_{\varepsilon,\varepsilon_{1},\varepsilon_{0},i}=\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})$
where $\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})$ is defined
in (37).

For all $i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$, let us define

$\displaystyle t_{i}(n,\delta)=\max\left\\{t\in[n]\setminus[K]\mid\>i\in
U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\right\\}\>.$

By definition, for all $i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$, we have
$i\in U_{\varepsilon,\varepsilon_{1},t}(n,\delta)$ for all
$t\in(K,t_{i}(n,\delta)]$ and $i\notin
U_{\varepsilon,\varepsilon_{1},t}(n,\delta)$ for all
$t\in(t_{i}(n,\delta),n]$. Therefore, for all
$t\in(K,\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}t_{i}(n,\delta)]$, we
have $U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset$ and
$U_{\varepsilon,\varepsilon_{1},t}(n,\delta)=\emptyset$ for all
$t>\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}t_{i}(n,\delta)$, hence

$\displaystyle\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}(t_{i}(n,\delta)-K)$
$\displaystyle=\sum_{t=K+1}^{n}\mathds{1}\left(U_{\varepsilon,\varepsilon_{1},t}(n,\delta)\neq\emptyset\right)$
$\displaystyle\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})+3K(K-1)/2\>.$

Let $T_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$ defined as
in the statement of Lemma 37. Direct manipulations show that

$\displaystyle
T_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)\geq\sup\left\\{n\mid
n-K\leq\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})+3K(K-1)/2\right\\}\>.$

Let $n>T_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$. Then, we
have

$n-K>\frac{4\tilde{f}_{2}(n,\delta)}{\min\\{\beta,1-\beta\\}}\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})+3K(K-1)/2\geq\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}(t_{i}(n,\delta)-K)\>,$

hence $n>\max_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}t_{i}(n,\delta)$.
This conclude the proof that
$U_{\varepsilon,\varepsilon_{1},n}(n,\delta)=\emptyset$. ∎

##### Upper bound probability of error

Let $S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$ and
$T_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$ as in Lemmas 35
and 37. For $\beta=1/2$, direct manipulations show that
$\max\\{S_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta),T_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)\\}\leq
E_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$ with

$\displaystyle
E_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta):=\sup\left\\{n\mid
n\leq
8\max\\{\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0}),\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})\\}\tilde{f}_{2}(n,\delta)+5K^{2}/2\right\\}$

Combining Lemmas 35 and 37, for all
$n>E_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$, we proved
that

$\tilde{\mathcal{E}}_{n,\delta}\cap\\{\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\\}=\tilde{\mathcal{E}}_{n,\delta}\cap\\{B^{\text{EB}}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\\}\subseteq\tilde{\mathcal{E}}_{n,\delta}\cap\\{U_{\varepsilon,\varepsilon_{1},n}(n,\delta)\neq\emptyset\\}=\emptyset\>,$

hence
$\\{\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\\}\subseteq\tilde{\mathcal{E}}_{n,\delta}^{\complement}$.

Using Lemma 48,
$\mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n,\delta}^{\complement})\leq
K(K+1)\delta/2$ and taking the infimum over
$\varepsilon\in[0,\varepsilon_{1}]$, yields

$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu))\leq\frac{K(K+1)}{2}\inf\\{\delta\mid\>n>E_{\varepsilon_{1},\varepsilon_{0},\mu}(\delta)\\}\>.$

where we used Lemma 52 and
$\inf_{\varepsilon\in[0,\varepsilon_{1}]}E_{\varepsilon,\varepsilon_{1},\varepsilon_{0},\mu}(\delta)=E_{\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$
with

$E_{\varepsilon_{1},\varepsilon_{0},\mu}(\delta):=\sup\left\\{n\mid n\leq
8\inf_{\varepsilon\in[0,\varepsilon_{1}]}\max\\{\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0}),\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})\\}\tilde{f}_{2}(n,\delta)+5K^{2}/2\right\\}\>.$

Using Lemma 52, we obtain that

$\displaystyle\mathbb{P}_{\nu}\left(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\right)$
$\displaystyle\leq\mathds{1}\left(\varepsilon_{1}<\Delta_{C_{\mu}}\right)\frac{K(K+1)}{2}e^{2}(2+\log
n)^{2}$ $\displaystyle\quad
p\left(\frac{n-5K^{2}/2}{8\inf_{\varepsilon\in[0,\varepsilon_{1}]}\max\\{\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0}),\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})\\}}\right)\>,$

where $p(x)=x\exp(-x)$.

##### More explicit complexity

In order to obtain a more interpretable result, we notice that the dependence
in $(\varepsilon,\varepsilon_{1})$ of
$\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})$ and
$\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})$ is only with
respect to its position in the ordered means. In the following, we will
replace the dependency in $(\varepsilon,\varepsilon_{1})$ by a dependency in
such indices.

Let $\mu\in\mathbb{R}^{K}$. Let us denote by $C_{\mu}:=|\\{\mu_{i}\mid
i\in[K]\\}|$ the number of different arm means in $\mu$. For all
$i\in[C_{\mu}]$, we denote the set of arms having mean gap $\Delta_{i}$ by
$\mathcal{C}_{\mu}(i):=\\{k\in[K]\mid\mu_{\star}-\mu_{k}=\Delta_{i}\\}$ where
the gaps are sorted by increasing order

$0=\Delta_{1}<\Delta_{2}<\cdots<\Delta_{C_{\mu}}\>.$

In particular, we have $\mathcal{C}_{\mu}(1)=i^{\star}(\mu)$ and
$\Delta_{C_{\mu}}=\Delta_{\max}$. Let us denote by

$\forall\varepsilon>0,\quad i_{\mu}(\varepsilon):=\begin{cases}i&\text{if
}\varepsilon\in[\Delta_{i},\Delta_{i+1})\quad\text{with}\quad
i\in[1,C_{\mu}-1]\\\ C_{\mu}&\text{if
}\varepsilon\geq\Delta_{C_{\mu}}\end{cases}\>.$ (21)

It is direct to see that
$i_{\mu}(\varepsilon)=\max\\{i\in[C_{\mu}],\mathcal{C}_{\mu}(i)\subset\mathcal{I}_{\varepsilon}(\mu)\\}$
for all $\varepsilon>0$. For all $i\in[C_{\mu}-1]$, let us define
$H_{i}(\mu,\varepsilon_{0})=\min_{j\in[i]}\max\\{\bar{H}_{i,j}(\mu,\varepsilon_{0}),\>\tilde{H}_{i,j}(\mu,\varepsilon_{0})\\}$
with $\bar{H}_{i,j}(\mu,\varepsilon_{0})$ and
$\tilde{H}_{i,j}(\mu,\varepsilon_{0})$ as in Theorem 6. Let
$\varepsilon_{1}\geq 0$ and $\varepsilon\in[0,\varepsilon_{1}]$. Then, we have
by direct manipulations that

$\inf_{\varepsilon\in[0,\varepsilon_{1}]}\max\\{\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0}),\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})\\}=H_{i_{\mu}(\varepsilon_{1})}(\mu,\varepsilon_{0})\>,$

since
$\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})=\bar{H}_{i_{\mu}(\varepsilon_{1}),i_{\mu}(\varepsilon)}(\mu,\varepsilon_{0})$
and
$\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})=\tilde{H}_{i_{\mu}(\varepsilon_{1}),i_{\mu}(\varepsilon)}(\mu,\varepsilon_{0})$.
This concludes the first part of Theorem 6, i.e.

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

##### Simple regret

Since $\mu_{\star}-\mu_{\hat{\imath}_{n}}$ is a positive random variable, we
obtain that

$\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]=\int_{\varepsilon_{1}=0}^{+\infty}\mathbb{P}_{\nu}(\mu_{\star}-\mu_{\hat{\imath}_{n}}>\varepsilon_{1})\mathrm{d}\,\varepsilon_{1}=\int_{\varepsilon_{1}=0}^{+\infty}\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu))\mathrm{d}\,\varepsilon_{1}\>.$

As a function of $\varepsilon$, our upper bound on
$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu))$
is piecewise constant on $[\Delta_{i},\Delta_{i+1})$ for all $i\in[C_{\mu}-1]$
and has null value for $\varepsilon_{1}\geq\Delta_{\max}$. Our upper is
informative, i.e. smaller than $1$, for all $n\geq D_{\mu}$ where

$\displaystyle D_{\mu}$
$\displaystyle=8H_{1}(\mu,\varepsilon_{0})h_{2}\left(8H_{1}(\mu,\varepsilon_{0}),5K^{2}/2,2+\log\left(K(K+1)/2\right)\right)+5K^{2}/2$
$\displaystyle>\sup\left\\{x\mid\>x<8H_{1}(\mu,\varepsilon_{0})\overline{W}_{-1}\left(2\log\left(2+\log
x\right)+2+\log\left(K(K+1)/2\right)\right)+5K^{2}/2\right\\}\>,$

where the inequality is obtained by using Lemma 51, and $h_{2}$ is defined
therein. Therefore, we obtain that, for all $n\geq D_{\mu}$,

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

which concludes the second part of Theorem 6.

###  F.2 Unverifiable sample complexity

The $(\varepsilon,\delta)$-_unverifiable sample complexity_ is defined as the
expectation of the smallest stopping time $\tilde{\tau}$ satisfying
$\mathbb{P}(\forall
t\geq\tilde{\tau},\hat{\imath}_{n}\in\mathcal{I}_{\varepsilon}(\mu))\geq
1-\delta$. Theorem 7 gives an upper bound on the unverifiable expected sample
complexity of the EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed proportions
$\beta=1/2$.

######  Theorem 7.

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

$\mathbb{P}_{\nu}\left(\forall
n>U_{i_{\mu}(\varepsilon),\delta}(\mu,\varepsilon_{0}),\>\hat{\imath}_{n}\in\mathcal{I}_{\varepsilon}(\mu)\right)\geq
1-\delta\>.$

The times $U_{i_{\mu}(\varepsilon),\delta}(\mu,\varepsilon_{0})$ are the
$(\varepsilon,\delta)$-unverifiable sample complexity of EB-
TC${}_{\varepsilon_{0}}$ defined as

$\forall i\in[C_{\mu}-1],\quad
U_{i,\delta}(\mu,\varepsilon_{0})=h_{2}\left(\log(1/\delta),8H_{i}(\mu,\varepsilon_{0}),8H_{i}(\mu,\varepsilon_{0})\log\left(K(K+1)/2\right)+5K^{2}/2\right)\>,$
(22)

with $(H_{i}(\mu,\varepsilon_{0}))_{i\in[C_{\mu}-1]}$ defined in Theorem 6.
The function
$h_{2}(\log(1/\delta),A,B)=2A\overline{W}_{-1}(\frac{1}{2}\log(1/\delta)+\frac{B}{2A}+\log(2A))$
satisfies that $h_{2}(\log(1/\delta),A,B)=_{\delta\to
0}A\log(1/\delta)+\mathcal{O}(\log\log(1/\delta))$.

###### Proof.

In Appendix F.1, we consider the concentration event
$\tilde{\mathcal{E}}_{n,\delta}$ that involved tighter concentration results
with thresholds $\tilde{f}_{1}(n,\delta)$ and $\tilde{f}_{2}(n,\delta)$. Let
$n>K$ and $\delta\in(0,1)$. It is direct to see that the same argument holds
for the concentration events
$\mathcal{E}_{n,\delta}=\mathcal{E}^{1}_{n,\delta}\cap\mathcal{E}^{2}_{n,\delta}$
with $(\mathcal{E}^{1}_{n,\delta})_{n>K}$ and
$(\mathcal{E}^{2}_{n,\delta})_{n>K}$ as in (24) and (25) for $s=0$, i.e.

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

where $f_{1}(n,\delta)=\log(1/\delta)+\log n+\log\left(K(K+1)/2\right)$ and
$f_{2}(n,\delta)=\log(1/\delta)+2\log n+\log\left(K(K+1)/2\right)$, which
satisfy $f_{1}(n,\delta)\leq f_{2}(n,\delta)$. Using Lemmas 40 and 41, we
obtain that
$\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\complement})\leq\delta$.

In the following, we use the notation on the gaps introduced in Appendix F.1,
the complexities $(H_{i}(\mu,\varepsilon_{0}))_{i\in[C_{\mu}-1]}$ defined in
Theorem 6 and the function $i_{\mu}(\varepsilon)$ defined in (21). To prove
Theorem 6, we obtain as an intermediary step that: for all
$n>E_{\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$,
$\\{\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\\}\subseteq\mathcal{E}_{n,\delta}^{\complement}$,
where

$\displaystyle E_{\varepsilon_{1},\varepsilon_{0},\mu}(\delta)$
$\displaystyle:=\sup\left\\{n\mid n\leq
8\inf_{\varepsilon\in[0,\varepsilon_{1}]}\max\\{\bar{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0}),\tilde{H}_{\varepsilon,\varepsilon_{1}}(\mu,\varepsilon_{0})\\}f_{2}(n,\delta)+5K^{2}/2\right\\}$
$\displaystyle=\sup\left\\{n\mid n\leq
8H_{i_{\mu}(\varepsilon_{1})}f_{2}(n,\delta)+5K^{2}/2\right\\}\>,$

where the equality holds by using the rewriting of the complexities done in
the end of Appendix F.1.

Let $A=8H_{i_{\mu}(\varepsilon_{1})}$ and
$B=8H_{i_{\mu}(\varepsilon_{1})}\log\left(K(K+1)/2\right)+5K^{2}/2$. Using a
proof similar to Lemma 51, applying Lemma 49 yields that

$\displaystyle n>E_{\varepsilon_{1},\varepsilon_{0},\mu}(\delta)\>$
$\displaystyle\iff\>n>2A\log n+A\log(1/\delta)+B$
$\displaystyle\iff\>\frac{n}{2A}-\log\left(\frac{n}{2A}\right)>\frac{1}{2}\log(1/\delta)+\frac{B}{2A}+\log(2A)$
$\displaystyle\iff\>n>2A\overline{W}_{-1}\left(\frac{1}{2}\log(1/\delta)+\frac{B}{2A}+\log(2A)\right)\>,$

Let us define
$h_{2}(\log(1/\delta),A,B)=2A\overline{W}_{-1}\left(\frac{1}{2}\log(1/\delta)+\frac{B}{2A}+\log(2A)\right)$
and, for all $i\in[C_{\mu}-1]$, we define

$U_{i,\delta}(\mu,\varepsilon_{0})=h_{2}\left(\log(1/\delta),8H_{i}(\mu,\varepsilon_{0}),8H_{i}(\mu,\varepsilon_{0})\log\left(K(K+1)/2\right)+5K^{2}/2\right)\>.$

Therefore, we have shown that, for all $\varepsilon_{1}\geq 0$,

$\\{\exists
n>U_{i_{\mu}(\varepsilon_{1}),\delta}(\mu,\varepsilon_{0}),\>\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\\}\subseteq\mathcal{E}_{n,\delta}^{\complement}$

Using that $\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\complement})\leq\delta$,
we can conclude that, for all $\varepsilon_{1}\geq 0$,

$\mathbb{P}_{\nu}\left(\forall
n>U_{i_{\mu}(\varepsilon_{1}),\delta}(\mu,\varepsilon_{0}),\>\hat{\imath}_{n}\in\mathcal{I}_{\varepsilon_{1}}(\mu)\right)\geq
1-\delta\>.$

∎

###  F.3 Cumulative regret of induced policy

Given a stream of recommendations $(\hat{\imath}_{n})_{n>K}$, an external
agent aiming at minimizing its cumulative regret can simply pull the arm
$\hat{\imath}_{n}$ at time $n$. Since the EB-TCa algorithm has anytime
guarantees on the simple regret of this recommendation, the regret of the
induced policy is constant (Corollary 2).

######  Corollary 2.

Let $\varepsilon_{0}>0$. Let $(\hat{\imath}_{n})_{n>K}$ be the recommendations
of the EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed proportions
$\beta=1/2$. An agent pulling $\hat{\imath}_{n}$ at time $n$ has constant
induced regret, i.e.

$\forall\nu\in\mathcal{D}^{K},\>\forall
T>K,\quad\sum_{n=K+1}^{T}\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]=\mathcal{O}\left(\frac{K^{3}\Delta_{\max}}{\min\\{\Delta_{\min},\varepsilon_{0}\\}^{2}}\left(\log\frac{K}{\min\\{\Delta_{\min},\varepsilon_{0}\\}^{2}}\right)^{2}\right)\>.$

###### Proof.

Using that
$H_{1}(\mu,\varepsilon_{0})=\max_{i\in[C_{\mu}-1]}H_{i}(\mu,\varepsilon_{0})$,
a direct upper bound based on Corollary 1 yields that, for all $n\geq
D_{\mu}$,

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

Let $c>0$. Let $f(c,x)=(c+\log(x))^{2}x\exp(-x)$ for all $x\geq 1$. Let $A>0$,
$B>0$. By integration, for all $C\geq A+B$, we obtain

$\displaystyle\sum_{n=C}^{T}f(c,(n-B)/A)$ $\displaystyle\leq
A\int_{1}^{+\infty}f(c,x)\mathrm{d}\,x=A\left(c^{2}+2cC_{1}+C_{2}\right)\>.$

where
$C_{\alpha}=\int_{1}^{+\infty}\log(x)^{\alpha}\exp(-x)\mathrm{d}\,x<+\infty$
for all $\alpha\geq 0$. For $n\geq 5K^{2}$, we have $n\leq 2(n-5K^{2}/2)$.
Recall that
$D_{\mu}=8H_{1}(\mu,\varepsilon_{0})h_{2}\left(8H_{1}(\mu,\varepsilon_{0}),5K^{2}/2,2+\log\left(K(K+1)/2\right)\right)+5K^{2}/2$
with $h_{2}$ defined in Lemma 51. For all $n<5K^{2}/2+D_{\mu}$, we have
trivially that
$\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]\leq\Delta_{\max}$.
Therefore, we obtain

$\displaystyle\sum_{n=K+1}^{T}\mathbb{E}_{\nu}[\mu_{\star}-\mu_{\hat{\imath}_{n}}]\leq(5K^{2}/2+D_{\mu})\Delta_{\max}+\frac{K(K+1)}{2}e^{2}\Delta_{\max}$
$\displaystyle\quad\sum_{n=5K^{2}+8H_{1}(\mu,\varepsilon_{0})}^{T}f\left(2+\log\left(16H_{1}(\mu,\varepsilon_{0})\right),\>\frac{n-5K^{2}/2}{8H_{1}(\mu,\varepsilon_{0})}\right)$
$\displaystyle\leq(5K^{2}/2+D_{\mu})\Delta_{\max}+\frac{K(K+1)}{2}e^{2}\Delta_{\max}$
$\displaystyle\quad
8H_{1}(\mu,\varepsilon_{0})\left(\left(2+\log\left(16H_{1}(\mu,\varepsilon_{0})\right)\right)^{2}+2C_{1}\left(2+\log\left(16H_{1}(\mu,\varepsilon_{0})\right)\right)+C_{2}\right)\>.$

Studying the function $h_{2}(x,y,z)$, it is direct to see that
$h_{2}(x,y,z)=_{x\to+\infty}o(\log(x)^{\alpha})$ for all $\alpha>0$, hence
$\Delta_{\max}D_{\mu}$ is dominated by the other term. Therefore, by studying
the dominating term when $\min\\{\Delta_{\min},\varepsilon_{0}\\}\to 0$, our
upper bound scales as

$\mathcal{O}\left(K^{2}\Delta_{\max}H_{1}(\mu,\varepsilon_{0})(\log
H_{1}(\mu,\varepsilon_{0}))^{2}\right)=\mathcal{O}\left(\frac{K^{3}\Delta_{\max}}{\min\\{\Delta_{\min},\varepsilon_{0}\\}^{2}}\left(\log\frac{K}{\min\\{\Delta_{\min},\varepsilon_{0}\\}^{2}}\right)^{2}\right)\>,$

where we used that
$H_{1}(\mu,\varepsilon_{0})=K(2\Delta_{\min}^{-1}+3\varepsilon_{0}^{-1})^{2}=\mathcal{O}\left(\frac{K}{\min\\{\Delta_{\min},\varepsilon_{0}\\}^{2}}\right)$.
∎

The idea of decoupling exploration and exploitation when minimizing the regret
in the multi-armed bandits literature was introduced by [2]. At each round,
the agent is allowed to choose one arm to explore and one arm to exploit at
every round. While the agent suffers the loss from the exploited arm, it
observes the one of the explored arm without cost. In the stochastic regime
for instances having a unique best arm, the Decoupled-Tsallis-INF algorithm
[33] achieves a constant regret $\mathcal{O}(K/\Delta_{\min})$. Therefore, in
this setting, our constant regret in Corollary 2 does have the best achievable
scaling in $K$ and $\Delta_{\min}$.

##### Beyond synchronized policy

When the external agent plays $\hat{\imath}_{n}$ at time $n$, it is said to be
synchronized with the recommendation rule. In all generality, one could pull
arm $\hat{\imath}_{\mathcal{L}(n)}$ at time $n$, where
$\mathcal{L}:\mathbb{N}\to\mathbb{N}$ is a non-decreasing function, and obtain
similar guarantees as Corollary 2. The agent can be slower than the
recommendation rule (e.g. offline hyper-parameter optimization) hence
$\mathcal{L}$ can be rapidly increasing, e.g. $\mathcal{L}(n)=Bn+K$ where
$B>1$. The recommendation rule can be slower than the agent (e.g. pulling the
same arm multiple times) hence $\mathcal{L}$ can be piecewise constant with
small steps, e.g. $\mathcal{L}(n)=\lceil n/B\rceil+K$. The communication
between the agent and the recommendation rule can happen infrequently (e.g.
paying to access the recommendation) hence $\mathcal{L}$ can be piecewise
constant with large steps, e.g. $\mathcal{L}(n)=(\lceil n/B\rceil)^{\alpha}+K$
where $\alpha>1$.

##  Appendix G Concentration results

The proof of Lemma 3 is given in Appendix G.1. Appendix G.2 gathers
concentration results to control the empirical means and gaps.

###  G.1 Proof of Lemma 3

Proving that a GLR stopping rule ensures the algorithm to be
$(\varepsilon_{1},\delta)$-PAC is done by leveraging concentration results. In
particular, we build upon Theorem 9 of [27] which is restated below. While
Theorem 9 was only stated for Gaussian distributions, it is direct to notice
that the result also holds for sub-Gaussian distributions with variance proxy
$\sigma^{2}=1$ (as the authors mentioned).

######  Lemma 38 (Theorem 9 of [27]).

Consider a sub-Gaussian bandit $\nu$ with means $\mu\in\mathbb{R}^{K}$. Let
$S\subseteq[K]$ and $x>0$.

$\displaystyle\mathbb{P}_{\nu}\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 [27] by
$\mathcal{C}_{G}(x)=\min_{\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)\>,$
(23)

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 $i\neq\hat{\imath}_{n}$

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

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

$\displaystyle\mathbb{P}_{\nu}\left(\tau_{\varepsilon_{1},\delta}<+\infty,\hat{\imath}_{\tau_{\varepsilon_{1},\delta}}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\right)$
$\displaystyle\leq\mathbb{P}_{\nu}\left(\exists n\in\mathbb{N},\>\exists
i\notin\mathcal{I}_{\varepsilon_{1}}(\mu),\>i=i^{\star}(\mu_{n}),\>\right.$
$\displaystyle\qquad\left.\min_{k\neq i}\inf_{y\geq
x+\varepsilon_{1}}\left(N_{n,\hat{\imath}_{n}}(\mu_{n,\hat{\imath}_{n}}-x)^{2}+N_{n,i}(\mu_{n,i}-y)^{2}\right)\geq
2c(n-1,\delta)\right)$ $\displaystyle\leq\mathbb{P}_{\nu}\left(\exists
n\in\mathbb{N},\>\exists
i\notin\mathcal{I}_{\varepsilon_{1}}(\mu),\>i=i^{\star}(\mu_{n}),\>\right.$
$\displaystyle\qquad\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)$
$\displaystyle\leq\sum_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}\mathbb{P}_{\nu}\left(\exists
n\in\mathbb{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)\>,$

where the second inequality is obtained with
$(k,x,y)=(i^{\star},\mu_{i},\mu_{i^{\star}})$ since
$i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$, 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\notin\mathcal{I}_{\varepsilon_{1}}(\mu),\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 38 for all
$i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)$ and using that
$|\mathcal{I}_{\varepsilon_{1}}(\mu)|\leq K-1$, we obtain

$\mathbb{P}_{\nu}\left(\tau_{\delta}<+\infty,\hat{\imath}_{\tau_{\delta}}\notin\mathcal{I}_{\varepsilon_{1}}(\mu)\right)\leq\sum_{i\notin\mathcal{I}_{\varepsilon_{1}}(\mu)}\frac{\delta}{K-1}\leq\delta\>.$

###  G.2 Sequence of concentration events

Lemma 39 is a standard concentration result for sub-Gaussian distribution,
hence we omit the proof.

######  Lemma 39.

Let $X$ be an observation from a sub-Gaussian distribution with mean $0$ and
variance proxy $\sigma^{2}$. Then, for all $\delta\in(0,1]$,

$\mathbb{P}_{X}\left(\left|X\right|\geq\sigma\sqrt{2\log(1/\delta)}\right)\leq\delta\>.$

Lemma 40 gives a sequence of concentration events under which the empirical
means are close to their true values.

######  Lemma 40.

Let $\delta\in(0,1]$ and $s\geq 0$. For all $n>K$, let
$f_{1}(x,\delta)=\log(1/\delta)+(1+s)\log x$ and

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

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

###### Proof.

Let $(X_{s})_{s\in[n]}$ be i.i.d. observations from one sub-Gaussian
distribution with mean $0$ and variance proxy $\sigma^{2}=1$. Then,
$\frac{1}{m}\sum_{i=1}^{m}X_{i}$ is sub-Gaussian with mean $0$ and variance
proxy $\sigma^{2}=1/m$. By union bound over $[K]$ and over $m\in[n]$, we
obtain

$\displaystyle\mathbb{P}_{\nu}\left(\exists k\in[K],\exists t\leq
n,\>|\mu_{t,k}-\mu_{k}|\geq\sqrt{\frac{2f_{1}(n,\delta)}{N_{t,k}}}\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{2f_{1}(n,\delta)}{m}}\right)$
$\displaystyle\leq\delta\sum_{k\in[K]}\sum_{m\in[n]}n^{-(1+s)}=K\delta
n^{-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 sub-Gaussian observations (Lemma 39). ∎

Lemma 41 gives a sequence of concentration events under which the empirical
gaps are close to their true values.

######  Lemma 41.

Let $\delta\in(0,1]$ and $s\geq 0$. For all $n>K$, let
$f_{2}(x,\delta)=\log(1/\delta)+(2+s)\log(x)$ and

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

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

###### Proof.

Let $(X_{s})_{s\in[n]}$ and $(Y_{s})_{s\in[n]}$ be two streams of i.i.d.
observations from two sub-Gaussian distributions with mean $0$ and variance
proxy $\sigma^{2}=1$. Then,
$\frac{1}{m_{1}}\sum_{i=1}^{m_{1}}X_{i}-\frac{1}{m_{2}}\sum_{i=1}^{m_{2}}Y_{i}$
is sub-Gaussian with mean $0$ and variance proxy
$\sigma^{2}=\frac{1}{m_{1}}+\frac{1}{m_{2}}$. By union bound , we obtain

$\displaystyle\mathbb{P}_{\nu}\left(\exists(i,k)\in[K]^{2}\>\text{s.t.}\>i\neq
k,\>\exists t\leq
n,\>\left|\frac{(\mu_{t,i}-\mu_{t,k})-(\mu_{i}-\mu_{k})}{\sqrt{1/N_{t,i}+1/N_{t,k}}}\right|\leq\sqrt{2f_{2}(n,\delta)}\right)$
$\displaystyle\leq\sum_{(i,k)\in[K]^{2},i\neq
k}\sum_{(m_{1},m_{2})\in[n]^{2}}\mathbb{P}\left(\left|\frac{1}{m_{1}}\sum_{i=1}^{m_{1}}X_{i}-\frac{1}{m_{2}}\sum_{i=1}^{m_{2}}Y_{i}\right|\leq-\sqrt{2f_{2}(n,\delta)\left(1/m_{1}+1/m_{2}\right)}\right)$
$\displaystyle\leq\delta\sum_{(i,k)\in[K]^{2},i\neq
k}\sum_{(m_{1},m_{2})\in[n]^{2}}n^{-(2+s)}=\frac{K(K-1)}{2}\delta 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 sub-Gaussian observations (Lemma 39). ∎

##### Tighter concentration

Lemma 42 provides concentration results on the empirical means, which are
tighter than the one obtained in Lemma 40.

######  Lemma 42.

Let $\delta\in(0,1]$ and $s\geq 0$. Let $\overline{W}_{-1}$ defined in Lemma
49. For all $n>K$, let

$\tilde{f}_{1}(n,\delta)=\frac{1}{2}\overline{W}_{-1}(2\log(1/\delta)+2s\log
n+2\log(2+\log n)+2)\>,$ (26)

and

$\tilde{\mathcal{E}}^{1}_{n,\delta}=\left\\{\forall k\in[K],\forall t\leq
n,\>|\mu_{t,k}-\mu_{k}|<\sqrt{\frac{2\tilde{f}_{1}(n,\delta)}{N_{t,k}}}\right\\}\>.$
(27)

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

###### Proof.

Let $(X_{s})_{s\in[n]}$ be i.i.d. observations from one sub-Gaussian
distribution with mean $0$ and variance proxy $\sigma^{2}=1$. Let
$S_{t}=\sum_{s\in[t]}X_{s}$. To derived concentration result, we use peeling.

Let $\eta>0$, $\gamma>0$ and $D=\lceil\frac{\log(n)}{\log(1+\eta)}\rceil$. For
all $i\in[D]$, let $N_{i}=(1+\eta)^{i-1}$. For all $i\in[D]$, we define the
family of priors $f_{N_{i},\gamma}(x)=\sqrt{\frac{\gamma
N_{i}}{2\pi}}\exp\left(-\frac{x^{2}\gamma 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}(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
supermartingale since sub-Gaussian distributions with mean $0$ and variance
proxy $\sigma^{2}=1$ satisfy

$\forall\lambda\in\mathbb{R},\quad\mathbb{E}_{X}[\exp(sX)]\leq\exp(\lambda^{2}/2)\>.$

By Tonelli’s theorem, then $\overline{M}(t)$ is also a non-negative
supermartingale 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}(x)\geq\frac{1}{\sqrt{1+\eta}}f_{t,\gamma}(x)$

Direct computations shows that

$\displaystyle\int
f_{t,\gamma}(x)\exp\left(xS_{t}-\frac{1}{2}x^{2}t\right)\,dx=\frac{1}{\sqrt{1+\gamma^{-1}}}\exp\left(\frac{S_{t}^{2}}{2(1+\gamma)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^{-1})(1+\eta)}}\exp\left(\frac{S_{t}^{2}}{2(1+\gamma)t}\right)\>,$

Using Ville’s maximal inequality for non-negative supermartingale, 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)\left(2\log\left(1/\delta\right)+2\log
D+\log(1+\gamma^{-1})+\log(1+\eta)\right)\>.$

Since this upper bound is independent of $t$, we can optimize it and choose
$\gamma$ as in Lemma 43.

######  Lemma 43 (Lemma A.3 in [9]).

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)$

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 m\leq
n,\left|\frac{1}{m}\sum_{s=1}^{m}X_{s}\right|\geq\sqrt{\frac{1}{m}\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}$ yields

$\displaystyle\mathbb{P}_{\nu}\left(\exists t\leq
n,\sqrt{N_{t,k}}\left|\mu_{t,k}-\mu_{k}\right|\geq\sqrt{2\tilde{f}_{1}(n,\delta)}\right)\leq\delta
n^{-s}\>.$

Doing a union bound over arms yields the result. ∎

Lemma 44 provides concentration results on the empirical gaps, which are
tighter than the ones obtained in Lemma 41.

######  Lemma 44.

Let $\delta\in(0,1]$ and $s\geq 0$. Let $\overline{W}_{-1}$ defined in Lemma
49. For all $n>K$, let

$\tilde{f}_{2}(n,\delta)=\overline{W}_{-1}\left(\log\left(1/\delta\right)+s\log
n+2\log\left(2+\log n\right)+2\right)\>,$ (28)

and

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

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

###### Proof.

Without loss of generality, we show the result for arms $(i,k)=(1,2)$. Let
$(X_{s})_{s\in[n]}$ and $(Y_{s})_{s\in[n]}$ be i.i.d. observations from two
sub-Gaussian distribution with mean $0$ and variance proxy $\sigma^{2}=1$. Let
$S_{t,k}=\sum_{s\in[t]}\mathds{1}\left(I_{s}=k\right)X_{s}$ for all
$k\in\\{1,2\\}$. To derived concentration result, we use peeling as in Lemma
42.

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

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

which satisfies $\overline{M}_{k}(0)=1$ for all $k\in\\{1,2\\}$. As in the
proof of Lemma 42, we obtain that $\overline{M}_{1}(t)$ and
$\overline{M}_{2}(t)$ are non-negative supermartingale such that

$\displaystyle\forall
k\in\\{1,2\\},\quad\overline{M}_{k}(t)\geq\frac{1}{D}\frac{1}{\sqrt{(1+\gamma^{-1})(1+\eta)}}\exp\left(\frac{S_{t,k}^{2}}{2(1+\gamma)N_{t,k}}\right)\>.$

where we used $(i_{1},i_{2})\in[D]^{2}$ and consider
$N_{t,k}\in[N_{i_{k}},N_{i_{k}+1})$ for all $k\in\\{1,2\\}$. Let us define
$\overline{M}(t)=\overline{M}_{1}(t_{1})\overline{M}_{2}(t_{2})$. Then, we
have that $\overline{M}(t)$ is a non-negative supermartingale such that

$\overline{M}(t)\geq\frac{1}{D^{2}}\frac{1}{(1+\gamma^{-1})(1+\eta)}\exp\left(\frac{1}{2(1+\gamma)}\sum_{k\in\\{1,2\\}}\frac{S_{t,k}^{2}}{N_{t,k}}\right)$

Using Ville’s maximal inequality for non-negative supermartingale, 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_{1},i_{2})\in[D]^{2}$ and
$N_{t,k}\in[N_{i_{k}},N_{i_{k}+1})$ for all $k\in\\{1,2\\}$,

$\displaystyle\sum_{k\in\\{1,2\\}}\frac{S_{t,k}^{2}}{N_{t,k}}$
$\displaystyle\leq 2(1+\gamma)\left(\log\left(1/\delta\right)+2\log
D+\log(1+\gamma^{-1})+\log(1+\eta)\right)\>.$

Since this upper bound is independent of $t$, we can optimize it and choose
$\gamma$ as in Lemma 43.

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

$\displaystyle\sum_{k\in\\{1,2\\}}\frac{S_{t,k}^{2}}{N_{t,k}}$
$\displaystyle\leq 2\overline{W}_{-1}\left(\log\left(1/\delta\right)+2\log
D+\log(1+\eta)+1\right)$ $\displaystyle\leq
2\overline{W}_{-1}\left(\log\left(1/\delta\right)+2\log\left(2+\log
n\right)+2\right)$

The second inequality is obtained as in Lemma 42 by using that $D\leq
1+\frac{\log n}{\log(1+\eta)}$, $\overline{W}_{-1}$ increasing, taking
$\eta^{\star}=e^{2}-1$ and using $3-2\log 2\leq 2$.

Since $[n]\subseteq\bigcup_{i\in[D]}[N_{i},N_{i+1})$, $N_{t,k}\leq n$ and
$N_{t,k}(\mu_{t,k}-\mu_{k})=S_{t,k}$ (unit-variance), this yields

$\displaystyle\mathbb{P}\left(\exists t\leq
n,\sum_{k\in\\{1,2\\}}\frac{N_{t,k}}{2}(\mu_{t,k}-\mu_{k})^{2}\geq\overline{W}_{-1}\left(\log\left(1/\delta\right)+2\log\left(2+\log
n\right)+2\right)\right)\leq\delta\>.$

Let
$C(n,\delta):=\overline{W}_{-1}\left(\log\left(1/\delta\right)+2\log\left(2+\log
n\right)+2\right)$. In the following, we consider that we are under the event,

$\mathcal{E}_{n,\delta}(1,2):=\left\\{\forall t\leq
n,\>\sum_{k\in\\{1,2\\}}\frac{N_{t,k}}{2}(\mu_{t,k}-\mu_{k})^{2}<C(n,\delta)\right\\}\>,$

which has probability at least $1-\delta$. Since it satisfies the above
constraint, the quantity $\mu_{t,1}-\mu_{1}-(\mu_{t,2}-\mu_{2})$ is upper
bounded by

$\max_{x\in\mathbb{R}^{2}}\left\\{\mu_{t,1}-\mu_{t,2}-x_{1}+x_{2}\right\\}\quad\text{subject
to}\quad\sum_{k\in\\{1,2\\}}\frac{N_{t,1}}{2}(\mu_{t,k}-x_{k})^{2}\leq
C(n,\delta)\>.$

Introducing a Lagrange multiplier $\alpha$, the above optimization problem is
equivalent to

$\min_{\alpha\geq
0}\max_{x\in\mathbb{R}^{2}}\left\\{\mu_{t,1}-\mu_{t,2}-x_{1}+x_{2}+\alpha\left(C(n,\delta)-\sum_{k\in\\{1,2\\}}\frac{N_{t,k}}{2}(\mu_{t,k}-x_{k})^{2}\right)\right\\}\>.$

Solving for $x$ by cancelling the derivative yields that
$x_{1}=\mu_{t,1}-\frac{1}{\alpha N_{t,1}}$ and
$x_{2}=\mu_{t,2}+\frac{1}{\alpha N_{t,2}}$. Therefore, we obtain as solution

$\displaystyle\min_{\alpha\geq 0}\left\\{\alpha
C(n,\delta)+\frac{1}{2\alpha}\sum_{k\in\\{1,2\\}}\frac{1}{N_{t,k}}\right\\}=\sqrt{2C(n,\delta)\sum_{k\in\\{1,2\\}}\frac{1}{N_{t,k}}}\>,$

where the last equality is obtained by solving the optimization since the
derivative is null at
$\alpha^{\star}=\sqrt{\sum_{k\in\\{1,2\\}}\frac{1}{2C(n,\delta)N_{t,k}}}$. By
symmetry, we obtain the same result to upper bound
$\mu_{t,2}-\mu_{2}-(\mu_{t,1}-\mu_{1})$. Therefore, under
$\mathcal{E}_{n,\delta}(1,2)$, we have shown that

$\frac{|\mu_{t,1}-\mu_{1}-(\mu_{t,2}-\mu_{2})|}{1/N_{t,1}+1/N_{t,2}}\leq\sqrt{2\overline{W}_{-1}\left(\log\left(1/\delta\right)+2\log\left(2+\log
n\right)+2\right)}\>.$

The same argument as above can be applied for all $(i,k)\in[K]^{2}$ such that
$i\neq k$. A direct union bound yields

$\displaystyle\mathbb{P}_{\nu}((\tilde{\mathcal{E}}^{2}_{n,\delta})^{\complement})\leq\sum_{(i,k)\in[K]^{2},i\neq
k}\mathbb{P}_{\nu}\left(\mathcal{E}_{n,\delta
n^{-s}}(i,k)^{\complement}\right)\leq\frac{K(K-1)}{2}\frac{\delta}{n^{s}}\>,$

where we used the inclusion proven above for $(n,\delta/n^{s})$. This
concludes the proof. ∎

##### Global events

Lemma 45 combines the above sequences of concentration events.

######  Lemma 45.

Let $s>1$. Let $(\mathcal{E}^{1}_{n,\delta})_{n>K}$ and
$(\mathcal{E}^{2}_{n,\delta})_{n>K}$ as in (24) and (25). Let
$(\tilde{\mathcal{E}}^{1}_{n,\delta})_{n>K}$ and
$(\tilde{\mathcal{E}}^{2}_{n,\delta})_{n>K}$ as in (27) and (29). Let us
define
$\mathcal{E}_{n,\delta}:=\mathcal{E}^{1}_{n,\delta}\cap\mathcal{E}^{2}_{n,\delta}$
and
$\tilde{\mathcal{E}}_{n,\delta}:=\tilde{\mathcal{E}}^{1}_{n,\delta}\cap\tilde{\mathcal{E}}^{2}_{n,\delta}$
for all $n>K$. Then,

$\sum_{n>K}\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\complement})\leq\frac{K(K+1)}{2}\zeta(s)\delta\quad\text{and}\quad\sum_{n>K}\mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n,\delta}^{\complement})\leq\frac{K(K+1)}{2}\zeta(s)\delta\>.$

###### Proof.

It is direct to see that

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

The same proof can be applied to upper bound
$\sum_{n>K}\mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n,\delta}^{\complement})$. ∎

##  Appendix H Technicalities

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

##### Key technical result

Lemma 4 is the key technical ingredient on which our proofs rely on. It builds
on a sequence of “bad” events such that, under each “bad” event, either the
leader or the challenger was not often selected as leader or challenger, and
shows that the number of times those “bad” events occur is small.

######  Lemma (Lemma 4).

Let $\delta\in(0,1]$ and $n>K$. Let $(A_{t,\delta}(n,\delta))_{n\geq t>K}$ be
a sequence of events and $(D_{i}(n,\delta))_{i\in[K]}$ be positive thresholds
satisfying that, for all $t\in[n]\setminus[K]$, under the event
$A_{t,\delta}(n,\delta)$,

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

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

###### Proof.

Using the inclusion of events given by the assumption on
$(A_{t,\delta}(n,\delta))_{n\geq t>K}$, we obtain

$\displaystyle\sum_{t=K+1}^{n}\mathds{1}\left(A_{t,\delta}(n,\delta)\right)$
$\displaystyle\leq\sum_{t=K+1}^{n}\mathds{1}\left(\exists
k_{t}\in[K],\>T_{t}(k_{t})\leq
D_{k_{t}}(n,\delta),\>T_{t+1}(k_{t})=T_{t}(k_{t})+1\right)$
$\displaystyle\leq\sum_{i\in[K]}\sum_{t=K+1}^{n}\mathds{1}\left(T_{t}(i)\leq
D_{i}(n,\delta),\>T_{t+1}(i)=T_{t}(i)+1\right)\leq\sum_{i\in[K]}D_{i}(n,\delta)\>.$

The second inequality is obtained by union bound. The third inequality is
direct since the number of times one can increase by one a quantity that is
positive and bounded by $D_{i}(n,\delta)$ is at most $D_{i}(n,\delta)$. ∎

##### Tracking

Lemma 46 provide general results for the $K(K-1)$ tracking procedures both for
IDS and fixed proportions, which includes the ones of Lemma 2. The main
theoretical argument behind those results is based on applying Theorem 6 in
[12].

######  Lemma 46.

For all $n>K$, $i\in[K]$, $j\neq i$, we have

$-1/2\leq N_{n,j}^{i}-(1-\bar{\beta}_{n}(i,j))T_{n}(i,j)\leq
1\quad\text{i.e.}\quad-1\leq(T_{n}(i,j)-N^{i}_{n,j})-\bar{\beta}_{n}(i,j)T_{n}(i,j)\leq
1/2$

and

$\displaystyle\frac{N^{i}_{n,i}-(K-1)/2}{\max_{j\neq
i}\bar{\beta}_{n}(i,j)}\leq\sum_{j\neq
i}T_{n}(i,j)\leq\frac{N^{i}_{n,i}+K-1}{\min_{j\neq i}\bar{\beta}_{n}(i,j)}\>.$

Let $\beta\in(0,1)$. For fixed proportions $\beta$, we have

$\displaystyle
N_{n,i}\geq\min\\{\beta,1-\beta\\}\left(T_{n}(i)-\frac{3(K-1)}{2}\right)\>.$

###### Proof.

We have $K(K-1)$ independent two-arms C-Tracking between the challenger and
the leader. Theorem 6 in [12] yields the result. The second inequality is a
simple re-ordering.

To obtain the second part, direct manipulations yield that

$\displaystyle\sum_{j\neq i}T_{n}(i,j)\leq\sum_{j\neq
i}\frac{T_{n}(i,j)-N^{i}_{n,j}+1}{\bar{\beta}_{n}(i,j)}\leq\frac{\sum_{j\neq
i}(T_{n}(i,j)-N^{i}_{n,j})+K-1}{\min_{j\neq i}\bar{\beta}_{n}(i,j)}\>,$

which allows to conclude since $N^{i}_{n,i}=\sum_{j\neq
i}(T_{n}(i,j)-N^{i}_{n,j})$. The lower bound is obtained similarly.

The third is a direct consequence of the first part since

$\displaystyle N_{n,i}=\sum_{j\neq i}(T_{n}(i,j)-N^{i}_{n,j})+\sum_{j\neq
i}N^{j}_{n,i}$ $\displaystyle\leq\beta\sum_{j\neq
i}T_{n}(i,j)+(1-\beta)\sum_{j\neq i}T_{n}(j,i)+3(K-1)/2$
$\displaystyle\geq\beta\sum_{j\neq i}T_{n}(i,j)+(1-\beta)\sum_{j\neq
i}T_{n}(j,i)-3(K-1)/2\>.$

Having shown

$\max_{i\in[K]}\left|N_{n,i}-\left(\beta\sum_{j\neq
i}T_{n}(i,j)+(1-\beta)\sum_{j\neq i}T_{n}(j,i)\right)\right|\leq 3(K-1)/2\>,$

it is direct to conclude. ∎

##### Methodology

Lemma 47 is a standard result to upper bound the expected sample complexity of
an algorithm, e.g. see Lemma 1 in [11]. This is a key method extensively used
in the literature.

######  Lemma 47.

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}\subseteq\\{\tau_{\delta}\leq
n\\}$. Then, $\mathbb{E}_{\nu}[\tau_{\delta}]\leq
T(\delta)+\sum_{n>K}\mathbb{P}_{\nu}(\mathcal{E}_{n}^{\complement})$.

###### Proof.

Since the random variable $\tau_{\delta}$ is positive and
$\\{\tau_{\delta}>n\\}\subseteq\mathcal{E}_{n}^{\complement}$ for all $n\geq
T(\delta)$, we have

$\mathbb{E}_{\nu}[\tau_{\delta}]=\sum_{n\geq
0}\mathbb{P}_{\nu}(\tau_{\delta}>n)\leq T(\delta)+\sum_{n\geq
T(\delta)}\mathbb{P}_{\nu}(\mathcal{E}_{n}^{\complement})\>,$

which concludes the proof by adding positive terms. ∎

Lemma 48 is a key method to upper bound the probability of error of an
algorithm.

######  Lemma 48.

Let $\varepsilon\geq 0$ and $(\mathcal{E}_{n,\delta})_{n>K,\delta\in(0,1)}$ be
a sequence of events such that
$\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\complement})\leq C\delta$ with
$C>0$. Suppose that $T_{\varepsilon}(\delta)>K$ is such that for
$n>T_{\varepsilon}(\delta)$,
$\mathcal{E}_{n,\delta}\subseteq\\{\hat{\imath}_{n}\in\mathcal{I}_{\varepsilon}(\mu)\\}$.
Then,

$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu))\leq
C\inf\\{\delta\mid\>n>T_{\varepsilon}(\delta)\\}\>.$

###### Proof.

Using the assumption, we have
$\mathbb{P}_{\nu}(\hat{\imath}_{n}\notin\mathcal{I}_{\varepsilon}(\mu))\leq\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\complement})\leq
C\delta$ for all $n>T_{\varepsilon}(\delta)$. Taking the infimum yields the
result. ∎

##### Inversion results

Lemma 49 gathers properties on the function $\overline{W}_{-1}$, which is used
in the literature to obtain concentration results.

######  Lemma 49 ([22]).

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 50 provides an ordering on the thresholds for tighter concentration
results. It leverages properties of $\overline{W}_{-1}$.

######  Lemma 50.

Let $s\geq 0$. Let $\overline{W}_{-1}$ defined in Lemma 49. For all
$\delta\in(0,1]$ and $n\geq 1$, let us denote by

$\displaystyle\tilde{f}_{1}(n,\delta)$
$\displaystyle=\frac{1}{2}\overline{W}_{-1}(2\log(1/\delta)+2s\log
n+2\log(2+\log n)+2)\>,$ $\displaystyle\tilde{f}_{2}(n,\delta)$
$\displaystyle=\overline{W}_{-1}\left(\log\left(1/\delta\right)+s\log
n+2\log\left(2+\log n\right)+2\right)\>.$

Then, we have $\tilde{f}_{1}(n,\delta)\leq\tilde{f}_{2}(n,\delta)$.

###### Proof.

Let $a>0$ and $b\geq 1$. Let us define
$f(x)=\frac{1}{x}\overline{W}_{-1}(ax+b)$. Using Lemma 49, we have

$f^{\prime}(x)=-\frac{1}{x^{2}}\left(\overline{W}_{-1}(ax+b)-\frac{ax}{1-\overline{W}_{-1}(ax+b)^{-1}}\right)\>.$

Therefore, we obtain $f^{\prime}(x)\leq 0$ if and only if
$\overline{W}_{-1}(ax+b)\geq ax+1$. Since $\overline{W}_{-1}(ax+b)\geq ax+b$
and $b\geq 1$, the function $f(x)$ is decreasing for all $x\geq 1$. Therefore,
$\frac{1}{2}\overline{W}_{-1}(2x+b)\leq\overline{W}_{-1}(a+b)$. Applying this
result with $a=\log\left(1/\delta\right)+s\log n$ and $b=2\log(2+\log n)+2\geq
1$ for all $n\geq 1$, we obtain
$\tilde{f}_{1}(n,\delta)\leq\tilde{f}_{2}(n,\delta)$. ∎

Lemma 51 is an inversion result to upper bound a time which is implicitly
defined. It is a direct consequence of Lemma 49.

######  Lemma 51.

Let $\overline{W}_{-1}$ defined in Lemma 49. Let $A>0$, $B>0$ such that
$B/A+\log A>1$ and

$\displaystyle C(A,B)=\sup\left\\{x\mid\>x<A\log x+B\right\\}\>,$
$\displaystyle
C(A,B,D)=\sup\left\\{x\mid\>x<A\overline{W}_{-1}\left(2\log\left(2+\log
x\right)+D\right)+B\right\\}\>.$

Then, $C(A,B)<h_{1}(A,B)$ with $h_{1}(z,y)=z\overline{W}_{-1}\left(y/z+\log
z\right)$ and $C(A,B)<Ah_{2}(A,B,D)+B$ where

$\displaystyle h_{2}(x,y,z)=\inf\left\\{u\mid\>u-\log
u-2\log\left(2+\log(xu+y)\right)\geq z\right\\}\>.$

###### Proof.

Since $B/A+\log A>1$, we have $C(A,B)\geq A$, hence

$C(A,B)=\sup\left\\{x\mid\>x<A\log(x)+B\right\\}=\sup\left\\{x\geq
A\mid\>x<A\log(x)+B\right\\}\>.$

Using Lemma 49 yields that

$\displaystyle x\geq A\log
x+B\>\iff\>\frac{x}{A}-\log\left(\frac{x}{A}\right)\geq\frac{B}{A}+\log
A\>\iff\>x\geq A\overline{W}_{-1}\left(\frac{B}{A}+\log A\right)\>.$

By changing the variable, we obtain

$C(A,B,D)=B+A\sup\left\\{y\mid\>y<\overline{W}_{-1}\left(2\log\left(2+\log(Ay+B)\right)+D\right)\right\\}$

Likewise, Lemma 49 yields that

$\displaystyle
y\geq\overline{W}_{-1}\left(2\log\left(2+\log(Ay+B)\right)+D\right)\>$
$\displaystyle\iff\>y-\log y-2\log\left(2+\log(Ay+B)\right)\geq D\>.$

∎

Lemma 52 is an inversion result to upper bound a probability which is
implicitly defined based on times that are implicitly defined.

######  Lemma 52.

Let $\overline{W}_{-1}$ defined in Lemma 49. Let $A>0$, $B>0$, $C>0$, $E>0$,
$\alpha>0$, $\beta>0$ and

$\displaystyle D_{A,B,C}(\delta)=\sup\left\\{x\mid\>x\leq
A(\log(1/\delta)+C\log x)+B\right\\}\>,$ $\displaystyle
D_{A,B,C,E,\alpha,\beta}(\delta)=\sup\left\\{x\mid\>x\leq\frac{A}{\alpha}\overline{W}_{-1}\left(\alpha\left(\log(1/\delta)+C\log(\beta+\log
x)+E\right)\right)+B\right\\}\>.$

Then,

$\displaystyle\inf\\{\delta\mid x>D_{A,B,C}(\delta)\\}\leq
x^{C}\exp\left(-\frac{x-B}{A}\right)\>,$ $\displaystyle\inf\\{\delta\mid
x>D_{A,B,C,E,\alpha,\beta}(\delta)\\}\leq
e^{E}\left(\alpha\frac{x-B}{A}\right)^{1/\alpha}(\beta+\log
x)^{C}\exp\left(-\frac{x-B}{A}\right)\>.$

###### Proof.

Direct manipulations yield that

$\displaystyle x>D_{A,B,C}(\delta)\>$
$\displaystyle\iff\>x>A(\log(1/\delta)+C\log
x)+B\>\iff\>\delta<x^{C}\exp\left(-\frac{x-B}{A}\right)\>.$

Likewise, using Lemma 49, we obtain

$\displaystyle x>D_{A,B,C,E,\alpha,\beta}(\delta)\>$
$\displaystyle\iff\>\alpha\frac{x-B}{A}>\overline{W}_{-1}\left(\alpha\left(\log(1/\delta)+C\log(\beta+\log
x)+E\right)\right)$
$\displaystyle\iff\>\frac{x-B}{A}-\frac{1}{\alpha}\log\left(\alpha\frac{x-B}{A}\right)>\log(1/\delta)+C\log(\beta+\log
x)+E$
$\displaystyle\iff\>\delta<e^{E}\left(\alpha\frac{x-B}{A}\right)^{1/\alpha}(\beta+\log
x)^{C}\exp\left(-\frac{x-B}{A}\right)\>.$

∎

##  Appendix I Multiplicative setting

Let $\nu\in\mathcal{D}^{K}$ with mean parameters
$\mu\in(\mathbb{R}^{\star}_{+})^{K}$. Compared to the additive setting, we
only consider strictly positive mean parameters. In many applications, this
assumption is natural. In other applications, there is a known lower bound on
the value of the true mean parameters, hence we can simply translate the
problem by adding this lower bound. We also note that the problem of
identifying which arms are above the threshold $0$ is the thresholding bandit
problem, which has been extensively studied in the literature. Overall, while
this assumption might seem restrictive, we think it is rather mild. Since the
means are strictly positive, the multiplicative error $\varepsilon$ has also
to be positive and strictly smaller than $1$. Given a multiplicative error
$\varepsilon\in[0,1)$, the set of multiplicative $\varepsilon$-good arms are
denoted by
$\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu):=\\{i\in[K]\mid\Delta_{i}\leq\mu_{\star}\varepsilon\\}$.
We will refer to this problem as multiplicative $\varepsilon$-BAI.

First, we discuss the characteristic times involved in the fixed-confidence
multiplicative $\varepsilon$-BAI (Appendix I.1). Second, for
$\varepsilon_{0}\in(0,1)$, we present the EB-
TC${}_{\varepsilon_{0}}^{\text{m}}$ with IDS or fixed $\beta$ proportions
(Appendix I.2). Finally, we prove that EB-TC${}_{\varepsilon_{0}}^{\text{m}}$
is asymptotically (resp. $\beta$-)optimal when using IDS (resp. fixed $\beta$)
when combined with the appropriate GLR stopping rule (Appendix I.3).

###  I.1 Characteristic times

Let $\nu\in\mathcal{D}^{K}$ with mean parameters
$\mu\in(\mathbb{R}^{\star}_{+})^{K}$. We assume in the following that there
exists a unique best arm, i.e. $i^{\star}(\mu)=\\{i^{\star}\\}$. Let
$\varepsilon\in[0,1)$. The ($\beta$-)characteristic times for the fixed
confidence multiplicative $\varepsilon$-BAI setting with Gaussian bandits
$\mathcal{N}(\mu,1)$ are defined as
$T^{\operatorname*{mul}}_{\varepsilon}(\mu)=\min_{i\in\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu),\beta\in(0,1)}T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu,i)$
and
$T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu)=\min_{i\in\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu)}T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu,i)$
where

$2T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu)^{-1}(\mu,i)=\max_{w\in\triangle_{K},w_{i}=\beta}\min_{j\neq
i}\frac{(\mu_{i}-(1-\varepsilon)\mu_{j})^{2}}{1/\beta+(1-\varepsilon)^{2}/w_{j}}\>,$
(30)

We denote by $w^{\operatorname*{mul}}_{\varepsilon}(\mu,i)$ and
$w^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu,i)$ their maximizer, which we
refer to as the ($\beta$-)optimal allocation for multiplicative
$\varepsilon$-BAI.

Even though the multiplicative $\varepsilon$-BAI is less studied, it is direct
to see that it has similar properties as $T_{0}(\mu)$. Due to the factor
$(1-\varepsilon)^{2}$ in the denominator, it is not possible to simply use a
reduction to a BAI problem as we did for the additive $\varepsilon$-BAI
problem (see Lemma 9). Since the properties listed in Appendix C are obtained
by studying the optimization problem defining $T_{0}(\mu)$, we will have the
same properties for $T^{\operatorname*{mul}}_{\varepsilon}(\mu)$ by accounting
for the extra multiplicative factor $(1-\varepsilon)^{2}$. We list here the
properties on which our proof relies:

  * •

$T^{\operatorname*{mul}}_{\varepsilon}(\mu)=\min_{\beta\in(0,1)}T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu,i^{\star})$
and
$T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu)=T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu,i^{\star})$,
meaning the unique best arm corresponds to the arm which is the easiest to
verify multiplicative $\varepsilon$-BAI.

  * •

$w^{\operatorname*{mul}}_{\varepsilon}(\mu)=\\{w^{\operatorname*{mul}}_{\varepsilon}\\}$
and
$w^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu)=\\{w^{\operatorname*{mul}}_{\varepsilon,\beta}\\}$,
meaning there is a unique ($\beta$-)optimal allocation which satisfies
$\min_{i\in[K]}(w^{\operatorname*{mul}}_{\varepsilon})_{i}>0$ and
$\min_{i\in[K]}(w^{\operatorname*{mul}}_{\varepsilon,\beta})_{i}>0$.

  * •

There is equality at the equilibrium of the transportation costs, meaning for
all $i\neq i^{\star}$

$\displaystyle\frac{(\mu_{i^{\star}}-(1-\varepsilon)\mu_{i})^{2}}{(w^{\operatorname*{mul}}_{\varepsilon})^{-1}_{i^{\star}}+(1-\varepsilon)^{2}(w^{\operatorname*{mul}}_{\varepsilon})^{-1}_{i}}$
$\displaystyle=2T^{\operatorname*{mul}}_{\varepsilon}(\mu)^{-1}\>\text{and}\>\frac{(\mu_{i^{\star}}-(1-\varepsilon)\mu_{i})^{2}}{\beta^{-1}+(1-\varepsilon)^{2}(w^{\operatorname*{mul}}_{\varepsilon,\beta})_{i}^{-1}}$
$\displaystyle=2T^{\operatorname*{mul}}_{\varepsilon,\beta}(\mu)^{-1}\>,$ (31)

and the multiplicative overall balance equation is satisfied

$\sum_{i\neq
i^{\star}}\left(\frac{(w^{\operatorname*{mul}}_{\varepsilon})_{i}}{(w^{\operatorname*{mul}}_{\varepsilon})_{i^{\star}}}\right)^{2}=(1-\varepsilon_{0})^{2}\>.$
(32)

For the sake of space, we omit the proofs and defer the reader to Appendix C
for ideas on how to prove them.

###  I.2 Anytime Top Two algorithm

Let $\varepsilon_{0}\in(0,1)$. The EB-TC${}_{\varepsilon_{0}}^{\text{m}}$
algorithm, detailed in Figure 3, has the same structure as EB-
TC${}_{\varepsilon_{0}}$. There are two differences. First, the IDS
proportions are
$\beta_{n}(i,j)=N_{n,j}/((1-\varepsilon_{0})^{2}N_{n,i}+N_{n,j})$ when
considering multiplicative $\varepsilon$-BAI. Second, the challenger will be
based on transportation costs for multiplicative $\varepsilon$-BAI, namely

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

Figure 3: EB-TC${}_{\varepsilon_{0}}^{\text{m}}$ algorithm with fixed or IDS
proportions.

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

2:Set $\hat{\imath}_{n}\in\operatorname*{arg\,max}_{i\in[K]}\mu_{n,i}$,
$B^{\text{EB}}_{n}=\hat{\imath}_{n}$ and
$C^{\text{TC}^{\text{m}}_{\varepsilon_{0}}}_{n}\in\operatorname*{arg\,min}_{i\neq
B^{\text{EB}}_{n}}\frac{\mu_{n,B^{\text{EB}}_{n}}-(1-\varepsilon_{0})\mu_{n,i}}{\sqrt{1/N_{n,B^{\text{EB}}_{n}}+(1-\varepsilon_{0})^{2}/N_{n,i}}}$.

3:Set [fixed] $\bar{\beta}_{n+1}(i,j)=\beta$ or [IDS]
$\beta_{n}(i,j)=N_{n,j}/((1-\varepsilon_{0})^{2}N_{n,i}+N_{n,j})$ and update
$\bar{\beta}_{n+1}(i,j)$.

4:Set $I_{n}=C^{\text{TC}^{\text{m}}_{\varepsilon_{0}}}_{n}$ if
$N_{n,C^{\text{TC}^{\text{m}}_{\varepsilon_{0}}}_{n}}^{B^{\text{EB}}_{n}}\leq(1-\bar{\beta}_{n+1}(B^{\text{EB}}_{n},C^{\text{TC}^{\text{m}}_{\varepsilon_{0}}}_{n}))T_{n+1}(B^{\text{EB}}_{n},C^{\text{TC}^{\text{m}}_{\varepsilon_{0}}}_{n})$,
otherwise set $I_{n}=B^{\text{EB}}_{n}$.

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

##### Stopping rule for fixed-confidence multiplicative $\varepsilon$-BAI

Similarly, the fixed-confidence setting requires a stopping rule, which will
be different since we tackle multiplicative $\varepsilon$-BAI. Given an
error/confidence pair $(\varepsilon,\delta)\in[0,1)\times(0,1)$, the
GLR${}_{\varepsilon}^{\text{m}}$ stopping rule [15] prescribes to stop at the
time

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

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

######  Lemma 53.

Let $\varepsilon\in[0,1)$ and $\delta\in(0,1)$. Given any sampling rule, using
the threshold (4) with the stopping rule (34) with error/confidence pair
$(\varepsilon,\delta)$ yields a $(\varepsilon,\delta)$-PAC algorithm for sub-
Gaussian distributions.

###### Proof.

The proof of Lemma 53 is actually almost identical to the one of Lemma 3. The
only change is at the beginning of the proof. Since
$\hat{\imath}_{n}=i^{\star}(\mu_{n})$, standard manipulations yield that for
all $i\neq\hat{\imath}_{n}$

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

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

$\displaystyle\mathbb{P}_{\nu}\left(\tau_{\varepsilon,\delta}^{\operatorname*{mul}}<+\infty,\hat{\imath}_{\tau_{\varepsilon,\delta}^{\operatorname*{mul}}}\notin\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu)\right)$
$\displaystyle\leq\mathbb{P}_{\nu}\left(\exists n\in\mathbb{N},\>\exists
i\notin\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu),\>i=i^{\star}(\mu_{n}),\>\right.$
$\displaystyle\qquad\left.\min_{k\neq i}\inf_{y\geq
x/(1-\varepsilon)}\left(N_{n,\hat{\imath}_{n}}(\mu_{n,\hat{\imath}_{n}}-x)^{2}+N_{n,i}(\mu_{n,i}-y)^{2}\right)\geq
2c(n-1,\delta)\right)$ $\displaystyle\leq\mathbb{P}_{\nu}\left(\exists
n\in\mathbb{N},\>\exists
i\notin\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu),\>i=i^{\star}(\mu_{n}),\>\right.$
$\displaystyle\qquad\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)$
$\displaystyle\leq\sum_{i\notin\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu)}\mathbb{P}_{\nu}\left(\exists
n\in\mathbb{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)\>,$

where the second inequality is obtained with
$(k,x,y)=(i^{\star},\mu_{i},\mu_{i^{\star}})$ since
$i\notin\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu)$, and the third
by union bound. Then, we can conclude as in Appendix G.1 that

$\mathbb{P}_{\nu}\left(\tau_{\varepsilon,\delta}^{\operatorname*{mul}}<+\infty,\hat{\imath}_{\tau_{\varepsilon,\delta}^{\operatorname*{mul}}}\notin\mathcal{I}^{\operatorname*{mul}}_{\varepsilon}(\mu)\right)\leq\delta\>.$

∎

##### Asymptotic expected sample complexity

While Theorem 8 holds for all sub-Gaussian distributions, it is particularly
interesting for Gaussian ones, in light of Lemma 1. It shows that, for
multiplicative $\varepsilon$-BAI, EB-TC${}_{\varepsilon_{0}}^{\text{m}}$ is
asymptotically optimal for Gaussian bandits when using IDS proportions and
asymptotically $\beta$-optimal when using fixed proportions $\beta$.

######  Theorem 8.

Let $\varepsilon_{0}\in(0,1)$, $\beta\in(0,1)$ and $\delta\in(0,1)$. Using the
threshold (4) in the stopping rule (34) with error/confidence
$(\varepsilon_{0},\delta)$, the EB-TC${}_{\varepsilon_{0}}^{\text{m}}$
algorithm is $(\varepsilon_{0},\delta)$-PAC and it satisfies that, for all
$\nu\in\mathcal{D}^{K}$ such that $|i^{\star}(\mu)|=1$,

$\text{{\bf[IDS]}}\quad\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]}{\log(1/\delta)}\leq
T^{\operatorname*{mul}}_{\varepsilon_{0}}(\mu)\quad\text{and}\quad\text{{\bf[fixed
$\beta$]}}\quad\limsup_{\delta\to
0}\>\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]}{\log(1/\delta)}\leq
T^{\operatorname*{mul}}_{\varepsilon_{0},\beta}(\mu)\>.$

###  I.3 Proof of Theorem 8

The proof is very similar to the one of Theorem 1, hence we will only
highlight key differences. We defer the reader to Appendix D for a detailed
discussion on the proof method and intuition on the different steps of the
proof, see also [36, 21, 40].

In the following, we consider a slack $\varepsilon_{0}$ for EB-
TC${}_{\varepsilon_{0}}^{\text{m}}$ which matches the error $\varepsilon$
considered by the GLR${}_{\varepsilon}^{\text{m}}$ stopping rule (34), i.e.
$\varepsilon_{0}=\varepsilon$. For conciseness, we denote
$w^{\star}=w^{\operatorname*{mul}}_{\varepsilon}$ and
$w^{\star}_{\beta}=w^{\operatorname*{mul}}_{\varepsilon,\beta}$.

Let $\gamma>0$. Let us define the _convergence times_
$T_{\varepsilon_{0},\gamma}$ and $T_{\varepsilon_{0},\beta,\gamma}$ as in (10)
and (14), i.e.

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

Lemma 54 gives a sufficient condition for asymptotic optimality and asymptotic
$\beta$-optimality. The proof is the same as for Lemmas 13 and 25, hence we
omit it.

######  Lemma 54.

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

$\limsup_{\delta\to
0}\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]}{\log\left(1/\delta\right)}\leq
T^{\operatorname*{mul}}_{\varepsilon_{0}}(\mu)\>.$

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

$\limsup_{\delta\to
0}\frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_{0},\delta}]}{\log\left(1/\delta\right)}\leq
T^{\operatorname*{mul}}_{\varepsilon_{0},\beta}(\mu)\>.$

####  I.3.1 Sufficient exploration

Lemma 55 shows that the transportation cost is strictly positive and increases
linearly, it bares similarity with Lemma 14.

######  Lemma 55.

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

$\frac{\mu_{n,i}-(1-\varepsilon_{0})\mu_{n,j}}{\sqrt{1/N_{n,i}+(1-\varepsilon_{0})^{2}/N_{n,j}}}\geq\sqrt{L}D_{\mu}\>,$

where $D_{\mu}>0$ is a problem dependent constant.

###### Proof.

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

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

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

$\displaystyle
L_{1}=\sup\left\\{x\mid\>x<\frac{4(2-\varepsilon_{0})^{2}W_{\mu}^{2}}{\varepsilon_{0}^{2}\min_{i\in[K]}\mu_{i}^{2}}\log(x)+e\right\\}<h_{1}\left(\frac{4(2-\varepsilon_{0})^{2}W_{\mu}^{2}}{\varepsilon_{0}^{2}\min_{i\in[K]}\mu_{i}^{2}},e\right)\>,$

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

$\displaystyle\frac{\mu_{n,i}-(1-\varepsilon_{0})\mu_{n,j}}{\sqrt{1/N_{n,i}+(1-\varepsilon_{0})^{2}/N_{n,j}}}\geq\frac{\varepsilon_{0}\min_{i\in[K]}\mu_{i}/2}{\sqrt{1/N_{n,i}+(1-\varepsilon_{0})^{2}/N_{n,j}}}\geq\sqrt{L}\frac{\varepsilon_{0}\min_{i\in[K]}\mu_{i}}{2\sqrt{1+(1-\varepsilon_{0})^{2}}}\>.$

Setting
$D_{\mu}=\frac{\varepsilon_{0}\min_{i\in[K]}\mu_{i}}{2\sqrt{1+(1-\varepsilon_{0})^{2}}}$
yields the result. ∎

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

######  Lemma 56.

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

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

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

###### Proof.

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

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

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

Lemma 57 show that the desired property for the TC challenger, we omit the
proof since it is the same as for Lemma 17.

######  Lemma 57.

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

Combining Lemma 16 and Lemma 57 yields Lemma 58. Importantly, Lemma 58 holds
for the EB-TC${}_{\varepsilon_{0}}$ algorithm with fixed proportions
$\beta\in(0,1)$ and IDS proportions. Since the proof is the same as for Lemmas
18 and 26, we omit it.

######  Lemma 58.

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

####  I.3.2 Empirical overall balance

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

######  Lemma 59.

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

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

###### Proof.

Let $N_{1}$ as in Lemma 58. We proceed as in Lemma 19. Let us define

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

Direct manipulations yield that

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

Using that
$\beta_{n}(i^{\star},C_{n})N_{n,i^{\star}}=(1-\beta_{n}(i^{\star},C_{n}))N_{n,C_{n}}/(1-\varepsilon_{0})^{2}$
since
$\beta_{n}(i^{\star},C_{n})=N_{n,C_{n}}/((1-\varepsilon_{0})^{2}N_{n,i^{\star}}+N_{n,C_{n}})$
and the inequalities proven in Lemma 19, we can exhibit deterministic
constants $A,B>0$ (depending on $K$ and $\varepsilon_{0}$) such that

$\displaystyle|G_{n+1}-G_{n}|\leq
AN_{1}+B\quad\text{hence}\quad|G_{n}|\leq(n-1-N_{1})(AN_{1}+B)+(1-\varepsilon_{0})^{2}\>.$

where the second inequality is obtained by telescopic sum (as in Lemma 19) and
using that
$G_{N_{1}+1}=\beta_{N_{1}}(i^{\star},C_{N_{1}})^{2}-(1-\beta_{N_{1}}(i^{\star},C_{N_{1}}))^{2}/(1-\varepsilon_{0})^{2}$.

As in Lemma 19, it is possible to exhibit deterministic constants $C,D>0$
(depending on $K$ and $\varepsilon_{0}$) such that

$\displaystyle\left|\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\sum_{i\neq
i^{\star}}\left(\frac{1}{1-\varepsilon_{0}}\frac{N_{n,i}}{n-1}\right)^{2}-\frac{G_{n}}{(n-1)^{2}}\right|\leq\frac{CN_{1}+D}{n-1}\>.$

Combining both results, we can show

$\displaystyle\left|\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\sum_{i\neq
i^{\star}}\left(\frac{1}{1-\varepsilon_{0}}\frac{N_{n,i}}{n-1}\right)^{2}\right|\leq\frac{(A+C)N_{1}+B+D}{n-1}+\frac{(1-\varepsilon_{0})^{2}}{(n-1)^{2}}\>.$

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

$N_{2}=\inf\left\\{n>2\mid\>\frac{(A+C)N_{1}+B+D}{n-1}+\frac{(1-\varepsilon_{0})^{2}}{(n-1)^{2}}\leq\gamma\right\\}\>,$

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

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

######  Lemma 60.

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

$c_{L}\leq\frac{N_{n,i^{\star}}}{n-1}\leq c_{U}\quad\text{where}\quad
c_{U}=\sqrt{\frac{(1-\varepsilon_{0})^{2}/2+1}{(1-\varepsilon_{0})^{2}+1}}\quad\text{and}\quad
c_{L}=\frac{1-c_{U}}{(1-\varepsilon_{0})\sqrt{2(K-1)}}\>.$

###### Proof.

Let $N_{2}$ as in Lemma 59 for $\frac{\gamma}{(1-\varepsilon_{0})^{4}}$. Using
Lemma 59, we obtain for all $n\geq N_{2}$

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

where we used that $\frac{N_{n,i^{\star}}}{n-1}\leq 1$. Taking
$\gamma=(1-\varepsilon_{0})^{2}/2$ yields the upper bound.

Let $\tilde{N}_{2}$ as in Lemma 59 for
$\frac{\gamma}{(K-1)(1-\varepsilon_{0})^{2}}$. Using Lemma 59, we obtain for
all $n\geq\max\\{N_{2},\tilde{N}_{2}\\}$

$\displaystyle-\gamma$
$\displaystyle\leq(K-1)(1-\varepsilon_{0})^{2}\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-(K-1)\sum_{i\neq
i^{\star}}\left(\frac{N_{n,i}}{n-1}\right)^{2}$
$\displaystyle\leq(K-1)(1-\varepsilon_{0})^{2}\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\left(1-\frac{N_{n,i^{\star}}}{n-1}\right)^{2}$
$\displaystyle\leq(K-1)(1-\varepsilon_{0})^{2}\left(\frac{N_{n,i^{\star}}}{n-1}\right)^{2}-\left(1-c_{U}\right)^{2}$

Taking $\gamma=\left(1-c_{U}\right)^{2}/2$ yields the lower bound. Note that

$\displaystyle c_{L}\leq c_{U}\quad$ $\displaystyle\iff\quad
1\leq\frac{(1-\varepsilon_{0})^{2}/2+1}{(1-\varepsilon_{0})^{2}+1}\left(2(K-1)(1-\varepsilon_{0})^{2}+2\sqrt{2(K-1)}(1-\varepsilon_{0})+1\right)\>,$

where the last condition is trivially true. Taking
$N_{3}=\max\\{N_{2},\tilde{N}_{2}\\}$ yields the result. ∎

Lemma 61 is a rescaled version of the empirical overall balance equation which
is proven by simply combining Lemma 59 and Lemma 60.

######  Lemma 61.

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

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

###### Proof.

Let $N_{3}$ and $c_{L}$ as in Lemma 60. Let $N_{2}$ as in Lemma 59 for $\gamma
c_{L}^{2}/(1-\varepsilon_{0})^{2}$. Direct manipulation shows that, for all
$n\geq N_{4}=\max\\{N_{2},N_{3}\\}$,

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

This concludes the result. ∎

####  I.3.3 Convergence towards optimal allocation

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

######  Lemma 62.

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

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

###### Proof.

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

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

Let $N_{4}$ as in Lemma 61. As in Lemma 22, we can show for all $n\geq N_{4}$

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

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

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

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

$\displaystyle\frac{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,i}}{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,j}}\sqrt{\frac{1+(1-\varepsilon_{0})^{2}N_{n,i^{\star}}/N_{n,j}}{1+(1-\varepsilon_{0})^{2}N_{n,i^{\star}}/N_{n,i}}}$