\forall b \notin V_{n}^{p}, \quad \frac{\tilde \mu_{k_{n,b_n^\star},b_n^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,b_n^\star}, b_n^\star}+ 1/\tilde N_{k_{n,b},b}}} &\ge  2^{(3p+1)/8} C_{\mu} \: , \\
\forall b \in U_{n}^{p}, \quad \frac{\tilde \mu_{k_{n,b_n^\star},b_n^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,b_n^\star}, b_n^\star}+ 1/\tilde N_{k_{n,b},b}}} &\le 2^{(p+1)/4} D_{\mu}  +2W_{\mu}\sqrt{\log(e + 2^{(p+1)/2-2})}   \\
&\quad + 2W_{\epsilon} \log(e+(p+1)/2) \: ,
\end{align*}

where we used Lemmas <ref> and <ref>.
Let $p_{3} = 16 \lceil \log_{2} (2D_{\mu}/C_{\mu}) \rceil + 1$, then we have $2^{(p-1)/16} > \frac{D_{\mu}}{C_{\mu}}  $ for all $p \ge p_{3}$.
Let $p_{4} = \frac{16}{9} \lceil \log_{2} X_{4} \rceil + 25$ and $p_{5} = \frac{32}{9} \lceil \log_{2} X_{5} \rceil + 7$ where

\begin{align*}
X_{4} &= \sup \left\{ x > 1 \mid x \le  \frac{W_{\mu}^2}{C_{\mu}^2} \log(e + x^{8/9} 2^{25/18-3/4}) \right\}\: ,\\
X_{5} &= \sup \left\{ x > 1 \mid x \le   \frac{2W_{\epsilon}}{C_{\mu}} \log(e+ 4 + 32\log_{2} (x)/18) \right\}\: .
\end{align*}

As in the proof of Lemma <ref>, using Lemma <ref> yields that $\bE_{\bnu}[\exp(\alpha p_{4})] < + \infty$ and $\bE_{\bnu}[\exp(\alpha p_{5})] < + \infty$ for all $\alpha \in \R_{+}$.
Let $p_{2} = \max\{p_3, p_4, p_5, 4\max\{p_{0}, p_{1}\}/3 -1/3\} + 1$.
Then, we have shown that for all $p \ge p_{2}$, for all $n$ such that $B_{n} \notin V_{n}^{p}$, we have $B_{n} =  b_n^\star $ and

\[
\min_{b \notin V_{n}^{p}}\frac{\tilde \mu_{k_{n,b_n^\star},b_n^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,b_n^\star}, b_n^\star}+ 1/\tilde N_{k_{n,b},b}}} > \max_{b \in U_{n}^{p}}  \frac{\tilde \mu_{k_{n,b_n^\star},b_n^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,b_n^\star}, b_n^\star}+ 1/\tilde N_{k_{n,b},b}}}  \: ,
\]

Therefore, by definition of the TC challenger $C_{n} = \argmin_{b \ne b_n^\star}\frac{\tilde \mu_{k_{n,b_n^\star},b_n^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,b_n^\star}, b_n^\star}+ 1/\tilde N_{k_{n,b},b}}} $, we obtain that $C_{n} \in V_{n}^{p}$.
Otherwise, there would be a contradiction given that we assumed that $U_{n}^{p} \ne \emptyset$.
Given all the condition exhibited above, it is direct to see that $\bE_{\bnu}[\exp(\alpha p_2)] < +\infty$ for all $\alpha > 0$. This concludes the proof.

Lemma <ref> shows that all the arms are sufficient explored for large enough $n$.

There exists $N_0$ with $\bE_{\bnu}[N_0] < + \infty$ such that for all $ n \geq N_0$ and all $a \in [K]$,

\[
N_{n,a} \geq \sqrt{n/K} \quad \text{and} \quad k_{n,a} \ge  \frac{\log (n/K)}{2 \log 2} + 1 \: .
\]

Let $p_0$ and $p_2$ as in Lemmas <ref> and <ref>.
Combining Lemmas <ref> and <ref> yields that, for all $p \ge p_{3} = \max\{p_2, 4p_{0}/3 -1/3\}$ and all $n$ such that $U_{n}^{p} \ne \emptyset$, we have $B_n \in V_{n}^{p}$ or $C_n \in V_{n}^{p}$.
We have $\bE_{\bnu}[2^{p_2}] < + \infty$.
We have $2^{p-1} \ge K 2^{3(p-1)/4}$ for all $p \ge p_{4} = 4 \lceil \log_2 K \rceil + 1$.
Let $p \ge \max \{p_3 , p_4\}$.

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

Case 1. Suppose there exists $a \in V_{ 2^{p-1} }^{p}$ such that $L_{ 2^{p},a} - L_{ 2^{p-1},a} \ge \frac{2^{3(p-1)/4}}{\beta} + 3/(2\beta)$.
Using Lemma <ref>, we obtain

\[
N^{a}_{ 2^{p}, a} - N^{a}_{ 2^{p-1} , a}  \ge \beta(L_{ 2^{p},a} - L_{ 2^{p-1},a}) - 3/2 \ge 2^{3(p-1)/4} \: ,
\]

hence $a$ is sampled $2^{3(p-1)/4}$ times between $ 2^{p-1}$ and $ 2^{p}-1$.

Case 2. Suppose that for all $a \in V_{ 2^{p-1} }^{p}$, we have $L_{ 2^{p},a} - L_{ 2^{p-1},a} < 2^{3(p-1)/4}/\beta + 3/(2\beta)$.

\[
\sum_{a \notin V_{ 2^{p-1} }^{p} }(L_{ 2^{p},a} - L_{ 2^{p-1},a}) \ge 2^{p-1} - K \left( 2^{3(p-1)/4}/\beta + 3/(2\beta) \right)
\]

Using Lemma <ref>, we obtain

\begin{align*}
\left|\sum_{a \notin V_{ 2^{p-1}}^{p} }(N^{a}_{ 2^{p},a} - N^{a}_{ 2^{p-1},a}) - \beta \sum_{a \notin V_{ 2^{p-1}}^{p} }(L_{ 2^{p},a} - L_{ 2^{p-1},a}) \right| \le  3(K-1)/2  \: .
\end{align*}

Combining all the above, we obtain

\begin{align*}
&\sum_{a \notin V_{ 2^{p-1} }^{p} }(L_{ 2^{p},a} - L_{ 2^{p-1},a}) - \sum_{a \notin V_{ 2^{p-1}}^{p} }(N^{a}_{ 2^{p},a} - N^{a}_{ 2^{p-1},a}) \\
&\ge (1-\beta) \sum_{a \notin V_{ 2^{p-1} }^{p} }(L_{ 2^{p},a} - L_{ 2^{p-1},a}) - 3(K-1)/2 \\
&\ge (1-\beta) \left(  2^{p-1} - K \left( 2^{3(p-1)/4}/\beta + 3/(2\beta) \right) \right) - 3(K-1)/2 \ge K 2^{3(p-1)/4} \: ,
\end{align*}

where the last inequality is obtained for $p \ge p_{5}$ with

\[
p_{5} = \sup\left\{ p \in \N \mid (1-\beta) \left(  2^{p-1} - K \left( 2^{3(p-1)/4}/\beta + 3/(2\beta) \right) \right) - 3(K-1)/2 < K 2^{3(p-1)/4} \right\}\: .
\]

The LHS summation is exactly the number of times where an arm $a \notin V_{ 2^{p-1}}^{p}$ was leader but wasn't sampled, hence

\[
\sum_{t = 2^{p-1}}^{2^{p} - 1} \indi{B_{t} \notin V_{2^{p-1}}^{p}, \: I_t = C_{t}} \ge K 2^{3(p-1)/4}
\]

For any $2^{p-1} \leq t \leq 2^{p} - 1$, $U_{t}^{p}$ is non-empty, hence we have $B_{t} \notin V_{2^{p-1}}^{p}$ (hence $B_{t} \notin V_{t}^{p} $) implies $C_{t}  \in V_{t}^{p} \subseteq V_{2^{p-1}}^{p} $.
Therefore, we have shown that

\[
\sum_{t = 2^{p-1}}^{2^{p} - 1} \indi{ I_t \in V_{2^{p-1}}^{p}} \ge \sum_{t = 2^{p-1}}^{2^{p} - 1} \indi{B_{t} \notin V_{2^{p-1}}^{p}, \: I_t = C_{t}} \ge K 2^{3(p-1)/4} \: .
\]

Therefore, there is at least one arm in $V_{ 2^{p-1}}^{p}$ that is sampled $2^{3(p-1)/4}$ times between $ 2^{p-1}$ and $ 2^{p}-1$.

In summary, we have shown $\left|V_{ 2^{p} }^{p}\right| \leq K-2$ for all $p \ge p_{6} = \max \{p_3 , p_4, p_{5}\}$.
By induction, for any $1 \leq k \leq K$, we have $\left|V_{ k 2^{p-1}}^{p}\right| \leq K-k$, and finally $U_{ K 2^{p-1}}^{p} = \emptyset$ for all $p \ge p_{6}$.
Defining $N_{0} = K 2^{p_{6} - 1}$, we have $\bE_{\bnu}[N_{0}] < +\infty$ by using Lemmas <ref> and <ref> for $p_{3} = \max\{p_2, 4p_{0}/3 -1/3\}$ and $p_{4}$ and $p_{5}$ are deterministic.
For all $n \ge N_{0}$, we let $2^{p-1} = \frac{n}{K}$.
Then, by applying the above, we have $U_{ K 2^{p-1}}^{p} = U^{\log_{2}(n/K) + 1}_{n}$ is empty, which shows that $N_{n,a} \geq \sqrt{n/K}$ for all $a \in [K]$.
Using Lemma <ref>, we obtain that $k_{n,a} \ge \frac{\log (n/K)}{2 \log 2} + 1$ for all $a \in [K]$.
This concludes the proof.

§.§ Convergence towards $\beta$-optimal allocation

The second step of in the generic analysis of Top Two algorithms [27] is to show that  ensures convergence of its empirical proportions towards the $\beta$-optimal allocation.
First, we show that the leader coincides with the best arm. Hence, the tracking procedure will ensure that the empirical proportion of time we sample it is exactly $\beta$.
Second, we show that a sub-optimal arm whose empirical proportion overshoots its $\beta$-optimal allocation will not be sampled next as challenger.
Therefore, this “overshoots implies not sampled” mechanism will ensure the convergence towards the $\beta$-optimal allocation.
We emphasise that there are multiple ways to select the leader/challenger pair in order to ensure convergence towards the $\beta$-optimal allocation.
Therefore, while we conduct the proof for , other choices of leader/challenger pair would yield similar results.
Note that our results heavily rely on having obtained sufficient exploration first.

Convergence for the best arm.
Lemma <ref> exhibits a random phase which ensures that the leader and the candidate answer are equal to the best arm  for large enough $n$.

Let $N_{0}$ be as in Lemma <ref>.
There exists $N_1 \ge N_{0}$ with $\bE_{\bnu}[N_1] < + \infty$ such that, for all $ n \geq N_1$, we have $\hat a_{n} = B_{n} = a^\star$.

Let $k \ge 1$ and $(T_{k}(a))_{a \in [K]}$ as in Equation (<ref>).
Suppose that $\bE_{\bnu}[\max_{a \in [K]} T_{k}(a)] < +\infty$.
Then,	Lemma <ref> yields that $N_{T_{k}(a), a} = 2^{k-1}$ and $\tilde N_{k,a} = 2^{k-2}$.
Using	Lemma <ref>, we obtain that

\begin{align*}
&\tilde \mu_{k, a^\star} \ge \mu_{a^\star} - W_{\mu} \sqrt{\frac{\log(e+2^{k-2})}{2^{k-2}}} - W_{\epsilon}  \frac{\log(e+k)}{2^{k-2}} \: , \\
\forall a \ne a^\star, \quad &\tilde \mu_{k,a}  \le  \mu_{a} + W_{\mu} \sqrt{\frac{\log(e+2^{k-2})}{2^{k-2}}} + W_{\epsilon}  \frac{\log(e+k)}{2^{k-2}} \: .
\end{align*}

Let $p_{1} = \lceil \log_2 (X_{1}-e) \rceil + 2$ and $ p_2 = \lceil \log_2 ( X_{2} - e - 1) \rceil + 2$ with

\begin{align*}
X_{1} &= \sup \left\{ x > 1 \mid \: x \le 64 \Delta_{\min}^{-2} W_{\mu}^2 \log x + e \right\} \le h_{1} ( 64 \Delta_{\min}^{-2} W_{\mu}^2 ,\: e) \: , \\
X_{2} &= \sup \left\{ x > 1 \mid \: x \le 8 \Delta_{\min}^{-1} W_{\epsilon} \log x + e + 1 \right\} \le h_{1} ( 8 \Delta_{\min}^{-1} W_{\epsilon}  ,\: e+1) \: , \\
X_{2} &\ge \sup \left\{ x > 1 \mid \: x \le 8 \Delta_{\min}^{-1} W_{\epsilon} \log (e + 2 + \log x )  \right\} \: ,
\end{align*}

where we used Lemma <ref>, and $h_{1}$ defined therein.
Then, for all $k\in \N^{K}$ such that $\min_{a \in [K]} k_{a} > p_{0} = \max\{p_1, p_{2}\}$ such that $\bE_{\bnu}[\max_{a \in [K]} T_{k_{a}}(a)] < +\infty$, we have $\tilde \mu_{k, a^\star} \ge \mu_{a^\star} - \Delta_{\min}/4$ and $\tilde \mu_{k,a}  \le  \mu_{a} + \Delta_{\min}/4$ for all $a \ne a^\star$, hence $a^\star = \argmax_{a \in [K]} \tilde \mu_{k,a}$.
We have, for all $\alpha \in \R_{+}$,

\[
\exp(\alpha p_{1}) \le e^{3\alpha} (X_{1}-e)^{\alpha/\log 2} \quad \text{hence} \quad \bE_{\bnu}[\exp(\alpha p_{1})] < + \infty \: ,
\]

where we used Lemma <ref> and $h_{1}(x,e) \sim_{x \to +\infty} x \log x$ to obtain that $\exp(\alpha p_{1}) $ is at most polynomial in $W_{\mu}$.
Likewise, we obtain that $\bE_{\bnu}[\exp(\alpha p_{2})] < + \infty$ for all $\alpha \in \R_{+}$.
Therefore, we have $\bE_{\bnu}[\exp(\alpha p_0)] < + \infty$ for all $\alpha \in \R_{+}$.

Let us define the UCB indices by $I_{k,a} = \tilde \mu_{k, a} + \sqrt{k/\tilde N_{k,a}} + k/(\epsilon \tilde N_{k,a})$.
Using the above, we have

\begin{align*}
& I_{k,a^\star} \ge \mu_{a^\star} - W_{\mu} \sqrt{\frac{\log(e+2^{k-2})}{2^{k-2}}} - W_{\epsilon}  \frac{\log(e+k)}{2^{k-2}} + \frac{k}{\epsilon 2^{k-2}} \: , \\
\forall a \ne a^\star, \quad & I_{k,a}  \le  \mu_{a} + W_{\mu} \sqrt{\frac{\log(e+2^{k-2})}{2^{k-2}}} + W_{\epsilon}  \frac{\log(e+k)}{2^{k-2}} + \frac{k}{\epsilon 2^{k-2}}\: .
\end{align*}

Therefore, we have $a^\star = \argmax_{a \in [K]} I_{k,a}$ for all $k\in \N^{K}$ such that $\min_{a \in [K]} k_{a} > \max\{p_1, p_{2}\}$ such that $\bE_{\bnu}[\max_{a \in [K]} T_{k_{a}}(a)] < +\infty$.

Let $N_{0}$ as in Lemma <ref>.
Using Lemma <ref>, we obtain that, for all $n \ge N_{0}$ and all $a \in [K]$, $k_{n,a} \ge \log_{2}(n/K)/2 + 1$.
Therefore, we obtain $\min_{a \in [K]} k_{n,a} > \max\{ p_{1}, p_{2}\}$ is implied by $n \ge N_{1} = \max\{ K 4^{\max\{ p_{1}, p_{2}\}}, N_{0}\}$.
Using the above, we conclude that $\bE_{\bnu}[N_{1}] < + \infty$ and $\hat a_{n} = B_{n} = a^\star$ for all $n \ge N_{1}$.

Lemma <ref> shows that that the pulling proportion of the best arm converges towards $\beta$, provided the phase defined in Lemma <ref> is reached in finite time for all arms.

Let $\gamma > 0$, and $N_1$ be as in Lemma <ref>.
There exists a deterministic constant $C_{0} \ge 1$ such that, for all $n \ge C_0 N_{1}$,

\[
\left| \frac{N_{n,a^\star}}{n-1} - \beta\right| \le \gamma \: .
\]

Let $\gamma > 0$.
Let $N_1$ as in Lemma <ref>.
Let $M \ge N_1$.
Using Lemma <ref>, we obtain $B_{n} = a^\star$ for all $n \ge M$.
Therefore, we obtain $L_{n,a^\star} \ge n - M$ and $\sum_{a \neq a^\star} N^{a}_{n,a^\star} \le M $ for all $n \ge M $.
Using Lemma <ref> yields that

\begin{align*}
\left| \frac{N_{n, a^\star}}{n-1} - \beta \right| &\le \frac{|N^{a^\star}_{n, a^\star} - \beta L_{n,a^\star}|}{n-1} + \beta \left|\frac{L_{n,a^\star}}{n-1} - 1 \right| + \frac{1}{n-1} \sum_{a \neq a^\star} N^{a}_{n,a^\star} \\
&\le \frac{1}{2(n-1)} + \beta \frac{2(M-1)}{n-1} \le \gamma \: ,
\end{align*}

where the last inequality is obtained by taking $n \ge \max\{M,(1/2+2\beta (M-1))/\gamma + 1\}$.

Convergence for the sub-optimal arms
Lemma <ref> exhibits a random phase which ensures that if a sub-optimal arm overshoots its $\beta$-optimal allocation then it cannot be selected as challenger for large enough $n$.

Let $\gamma > 0$. Let $N_{1}$ and $C_{0}$ be as in Lemma <ref> and <ref>.
There exists $N_{2} \ge C_{0}N_{1}$ with $\bE_{\bnu}[N_{2}] < + \infty$ such that, for all $n \ge N_{2}$,

\[
\exists a \ne a^\star, \quad \frac{N_{n,a}}{n-1} \ge  \omega^{\star}_{\beta,a} + \gamma \quad \implies \quad C_{n} \ne a \: .
\]

Let $\gamma > 0$ and $\tilde \gamma > 0$.
Let $N_1$ as in Lemma <ref> and $C_{0}$ as in Lemma <ref> for $\tilde \gamma$.
Let $n \ge C_0 N_{1}$.

Let $a \neq a^\star$ such that $\frac{N_{n,a}}{n-1} \ge  \omega^{\star}_{\beta,a} + \gamma$.
Suppose towards contradiction that $\frac{N_{n,b}}{n-1} > \omega^{\star}_{\beta,a}$ for all $b \notin \{ a^\star, a\}$.
Then, for all $n \ge C_0 N_{1}$, we have

\begin{align*}
1 - \beta + \tilde \gamma \ge 1 - \frac{N_{n,a^\star}}{n-1} = \sum_{b \ne a^\star} \frac{N_{n,b}}{n-1} > \gamma + \sum_{b \ne a^\star} \omega^{\star}_{\beta,b} = 1-\beta + \gamma\: ,
\end{align*}

which yields a contradiction for $\tilde \gamma \le \gamma$.
Therefore, for all $n \ge C_{0} N_{1}$, we have

\[
\exists a \ne a^\star, \quad \frac{N_{n,a}}{n-1} \ge  \omega^{\star}_{\beta,a} + \gamma	 \quad \implies \quad  \exists b \notin \{ a^\star, a\}, \quad \frac{N_{n,b}}{n-1} \le \omega^{\star}_{\beta,b} \: .
\]

Then, we have

\[
\sqrt{ \frac{1 + N_{n,a^\star}/N_{n,b}}{1+N_{n,a^\star}/N_{n,a}}}  \ge \sqrt{ \frac{1 + (\beta - \tilde \gamma)/\omega^{\star}_{\beta,b}}{1+(\beta + \tilde \gamma)/(\omega^{\star}_{\beta,a} +  \gamma)}} \: .
\]

In the following, we use Lemma <ref> and similar manipulations as in the proof of Lemma <ref>.
Therefore, we obtain that, for all $c \ne a^\star$,

\begin{align*}
\left|\tilde \mu_{k_{n,a^\star},a^\star} - \tilde \mu_{k_{n,c},c} - \Delta_{c} \right| &\le W_\mu \left( \sqrt{\frac{\log (e + 2^{k_{n,a^\star}-2})}{2^{k_{n,a^\star}-2}}} +  \sqrt{\frac{\log (e + 2^{k_{n,c}-2})}{2^{k_{n,c}-2}}} \right) \\
& \quad +  W_{\epsilon} \left( \frac{\log(e+k_{n,a^\star})}{2^{k_{n,a^\star}-2}} + \frac{\log(e+k_{n,c})}{2^{k_{n,c}-2}} \right) \: .
\end{align*}

Let $p_{3} = \lceil \log_2 (X_{1}-e) \rceil + 2$ and $ p_2 = \lceil \log_2 ( X_{2} - e - 1) \rceil + 2$ with

\begin{align*}
X_{3} &= \sup \left\{ x > 1 \mid \: x \le 16 \eta^{-2} W_{\mu}^2 \log x + e \right\} \le h_{1} ( 16 \eta^{-2} W_{\mu}^2 ,\: e) \: , \\
X_{2} &= \sup \left\{ x > 1 \mid \: x \le 4 \eta^{-1} W_{\epsilon} \log x + e + 1 \right\} \le h_{1} ( 4 \eta^{-1} W_{\epsilon}  ,\: e+1) \: , \\
X_{2} &\ge \sup \left\{ x > 1 \mid \: x \le 4 \eta^{-1} W_{\epsilon} \log (e + 2 + \log x )  \right\} \: ,
\end{align*}

where we used Lemma <ref>, and $h_{1}$ defined therein.
We have, for all $\alpha \in \R_{+}$,

\[
\exp(\alpha p_{3}) \le e^{3\alpha} (X_{3}-e)^{\alpha/\log 2} \quad \text{hence} \quad \bE_{\bnu}[\exp(\alpha p_{3})] < + \infty \: ,
\]

where we used Lemma <ref> and $h_{1}(x,e) \sim_{x \to +\infty} x \log x$ to obtain that $\exp(\alpha p_{3}) $ is at most polynomial in $W_{\mu}$.
Likewise, we obtain that $\bE_{\bnu}[\exp(\alpha p_{2})] < + \infty$ for all $\alpha \in \R_{+}$.

Using Lemma <ref> (with $C_{0}N_{1}\ge N_{1} \ge N_{0}$), we obtain that, for all $n \ge C_{0}N_{1}$ and all $a \in [K]$, $k_{n,a} \ge \log_{2}(n/K)/2 + 1$.
Therefore, we obtain $\min_{a \in [K]} k_{n,a} > \max\{ p_{2}, p_{3}\}$ is implied by $n \ge N_{2} = \max\{ K 4^{\max\{ p_{3}, p_{2}\}}, C_{0}N_{1}\}$.
Using the above, we conclude that $\bE_{\bnu}[N_{2}] < + \infty$ and $\max_{c \ne a^\star} |\tilde \mu_{k_{n,a^\star},a^\star} - \tilde \mu_{k_{n,c},c} - \Delta_{c} | \le \eta$ for all $n \ge N_{2}$.

Then, for all $n \ge N_{2}$, we have $B_n =a^\star$ and

\begin{align*}
\frac{\tilde \mu_{k_{n,a^\star},a^\star} - \tilde \mu_{k_{n,a},a} }{\tilde \mu_{k_{n,a^\star},a^\star} - \tilde \mu_{k_{n,b},b}}  \sqrt{ \frac{1 + N_{n,a^\star}/N_{n,b}}{1+N_{n,a^\star}/N_{n,a}}}  \ge \frac{ \Delta_{a} - \eta}{ \Delta_{b} + \eta } \sqrt{ \frac{1 + (\beta - \tilde \gamma)/\omega^{\star}_{\beta,b}}{1+(\beta + \tilde \gamma)/(\omega^{\star}_{\beta,a} +  \gamma)}} > 1 \: ,
\end{align*}

where the last inequality is obtained by taking $\eta$ and $\tilde \gamma$ sufficiently small and by using Equation (<ref>), i.e.

\[
\frac{ \Delta_{a}}{ \Delta_{b} } \sqrt{ \frac{1 + \beta /\omega^{\star}_{\beta,b}}{1+\beta /\omega^{\star}_{\beta,a} }} = 1 \: .
\]

Therefore, we have shown that $B_n =a^\star$ and

\[
\frac{\tilde \mu_{k_{n,a^\star},a^\star} - \tilde \mu_{k_{n,a},a} }{\sqrt{1/N_{n,a^\star} + 1/N_{n,a}} }   > \frac{\tilde \mu_{k_{n,a^\star},a^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/N_{n,a^\star} + 1/N_{n,b}}}\quad \text{hence} \quad C_{n} \neq a \: .
\]

This concludes the proof.

Lemma <ref> shows that that the pulling proportion of the best arm converges towards $\beta$ for large enough $n$.

Let $\gamma > 0$ and $T_{\boldsymbol{\mu}, \gamma}$ be as in Equation (<ref>).
Then, we have $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}]  < + \infty$.

Let $\gamma > 0$ and $\tilde \gamma > 0$.
Let $N_2$ as in Lemma <ref> for $\tilde \gamma$.
Let $M \ge N_{2}$.
Using Lemmas <ref>, <ref> and <ref> for all $n \ge M$, we obtain that $B_{n} = a^\star$, $\left| \frac{N_{n,a^\star}}{n-1} - \beta\right| \le \tilde \gamma$ and

\[
\exists a \ne a^\star, \quad \frac{N_{n,a}}{n-1} \ge  \omega^{\star}_{\beta,a} + \tilde \gamma \quad \implies \quad C_{n} \ne a \: .
\]

For all $a \ne a^\star$, let us define $t_{n,a}(\tilde \gamma)=\max \left\{t \mid M \le t \le n, \: N_{t, a}/(n-1) < \omega^{\star}_{\beta,a}+ \tilde \gamma \right\}$.
Since $N_{t, a}/(n-1) \le N_{t, a}/(t-1)$ for $t\leq n$, we have

\begin{align*}
\frac{N_{n,a}}{n-1} &\le \frac{M-1}{n-1} + \frac{1}{n-1} \sum_{t=M}^{n} \indi{I_t = C_{t} = a} \\
&\le \frac{M-1}{n-1} + \frac{1}{n-1} \sum_{t=M}^{n} \indi{\frac{N_{t, a}}{n-1} < \omega^{\star}_{\beta,a}+ \tilde \gamma, \: I_t = C_{t} = a} \\
&\le \frac{M-1}{n-1} + \frac{N_{t_{n,a}(\tilde \gamma),a}}{n-1} < \frac{M-1}{n-1} + \omega^{\star}_{\beta,a} + \tilde \gamma \: .
\end{align*}

The second inequality uses Lemma <ref>, and the two last inequalities use the definition of $t_{n,a}(\tilde \gamma)$.
Using that $\sum_{a \in [K]}\frac{N_{n,a}}{n-1} = \sum_{a \in [K]} \omega^{\star}_{\beta,a} = 1$, we obtain

\begin{align*}
\frac{N_{n,a}}{ n - 1} &= 1 - \sum_{b \neq a} \frac{N_{n,a}}{ n -1}
\geq 1 - \sum_{b \neq a} \left(  \omega^{\star}_{\beta,b} + \tilde \gamma + \frac{M-1}{n-1}\right)
=  \omega^{\star}_{\beta,a} - (K-1) \left( \tilde \gamma  + \frac{M-1}{n-1} \right) \: .
\end{align*}

Taking $\tilde \gamma \le  \gamma/(2(K-1))$ and $n \ge \max\{M, 2(K-1)(M-1)/\gamma + 1\}$ yields that

\[
\left\| \frac{N_{n}}{n-1} - \omega^{\star}_{\beta}\right\|_{\infty} \le \gamma \: .
\]

Let $T_{\boldsymbol{\mu}, \gamma}$ as in <ref>. Then, we showed that $T_{\boldsymbol{\mu}, \gamma} \le \max\{M, 2(K-1)(M-1)/\gamma + 1\}$.
Therefore, we have

\[
\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}] \le  \bE_{\bnu} [\max\{M, 2(K-1)(M-1)/\gamma + 1\}] < + \infty \: ,
\]

which concludes the proof.

§.§ Cost of doubling and forgetting

Compared to the generic analysis of Top Two algorithms [27], for , we need to control the sample complexity cost of doubling and forgetting.
Due to this reason, we have to pay a multiplicative four-factor: one two-factor due to doubling, and another two-factor due to forgetting.
It is possible to show that this cost exists when adapting any “reasonable” BAI algorithm, meaning for any BAI algorithm in which the empirical proportions are converging towards an allocation $\omega$ such that $\min_{a} \omega_{a} > 0$.
Those BAI algorithms are “reasonable” because the asymptotic lower bound stipulates that all arms have to be sampled linearly in order to be near optimal.

Let $\omega \in \Sigma_K$ be any allocation over arms such that $\min_{a} \omega_{a} > 0$.
Let $\gamma> 0$.
We denote by $T_{\boldsymbol{\mu}, \gamma}(\omega)$ the convergence time towards $\omega$, which is a random variable quantifying the number of samples required for the global empirical allocations $N_n/(n-1)$ to be $\gamma$-close to $\omega$ for any subsequent time, namely

\begin{equation} \label{eq:rv_T_eps_alloc}
T_{\boldsymbol{\mu}, \gamma}(\omega) \defn \inf \left\{ T \ge 1 \mid \forall n \geq T, \: \left\| \frac{N_{n}}{n-1} - \omega \right\|_{\infty} \leq \gamma \right\}  \: .
\end{equation}

Lemma <ref> shows that the phase switches of the arms happen in a round-robin fashion, which means that an arm switches phase for a second time after all other arms first switch their own phases.

Let $\omega \in \Sigma_K$ such that $\min_{a} \omega_{a} > 0$.
Assume that there exists $\gamma_{\boldsymbol{\mu}} > 0$ such that for $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}(\omega)]  < + \infty$ for all $\gamma \in (0, \gamma_{\boldsymbol{\mu}})$, where $T_{\boldsymbol{\mu}, \gamma}(\omega)$ is defined in Equation (<ref>).
Let $\eta > 0$.
There exists $\tilde \gamma_{\boldsymbol{\mu}} \in (0, \gamma_{\boldsymbol{\mu}})$ such that, for all $\gamma \in (0, \tilde \gamma_{\boldsymbol{\mu}})$, there exists $N_{3} \ge T_{\boldsymbol{\mu}, \gamma}(\omega)$ with $\bE_{\bnu} [N_{3}]  < + \infty$ which satisfies

\[
\forall n \ge N_{3}, \quad \frac{\max_{a \in [K]}T_{k_{n,a}}(a) - 1}{\min_{a \in [K]}T_{k_{n,a}}(a) - 1} \le 2+\eta \: .
\]

Let $\eta > 0$.
Let $\tilde \gamma_{\boldsymbol{\mu}} \in (0, \gamma_{\boldsymbol{\mu}})$ such that $2\max_{a \in [K]}(\omega_{a} + \gamma)/(\omega_{a} - \gamma) \le 2+\eta$, which is possible since $\min_{a} \omega_{a} > 0$.
Let $\gamma \in (0, \tilde \gamma_{\boldsymbol{\mu}})$.
By assumption, we have $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}(\omega)]  < + \infty$.
Then, for all $n \ge T_{\boldsymbol{\mu}, \gamma}(\omega)$,

\[
\left\| \frac{N_{n}}{n-1} - \omega\right\|_{\infty} \le \gamma \: .
\]

Let $M \ge T_{\boldsymbol{\mu}, \gamma}(\omega)$.
Let use denote by $k_{M} = (k_{M,a})_{a \in [K]}$ the current phases for all arms $a \in [K]$ at time $M$.
Then, for all $n \ge M$ and all $a \in [K]$, we have $N_{n,a} \ge (n-1)(\omega_{a} - \gamma)$.
Therefore, taking $n \ge \max_{a \in [K]} 2^{k_{M,a}} (\omega_{a} - \gamma)^{-1} + 1$, we obtain that $N_{n,a} \ge 2^{k_{M,a}}$ for all $a \in [K]$, hence we have $\max_{a \in [K]} T_{k_{M,a} + 1}(a) \le n$.
Since $\min_{a \in [K]} T_{k_{M,a} + 1}(a) \ge M$, we have

\[
\max_{a \in [K]}\left| \frac{N_{T_{k_{M,a} + 1}(a), a}}{n-1} - \omega_{a}\right| \le \gamma \: .
\]

Likewise, taking $n \ge \max_{a \in [K]} 2^{k_{M,a}+1} (\omega_{a} - \gamma)^{-1} + 1$, we obtain that $N_{n,a} \ge 2^{k_{M,a}+1}$ for all $a \in [K]$, hence we have $\max_{a \in [K]} T_{k_{M,a} + 2}(a) \le n$.
Let $a_{1} = \argmin_{a \in [K]} T_{k_{M,a} + 2}(a)$.
By definition and using Lemma <ref>, we have

\begin{align*}
& 2^{k_{M,a_{1}}+1} = N_{T_{k_{M,a_{1}} + 2}(a_{1}), a_{1}}  \le (T_{k_{M,a_{1}} + 2}(a_{1}) - 1)( \omega_{a_{1}} + \gamma) \: , \\
\forall a \ne a_{1}, \quad & 2^{k_{M,a}} \le N_{T_{k_{M,a_{1}} + 2}(a_{1}), a}  \le (T_{k_{M,a_{1}} + 2}(a_{1}) - 1)( \omega_{a} + \gamma) \: .
\end{align*}

Let $a_{2} = \argmax_{a \in [K]} T_{k_{M,a} + 2}(a)$.
By definition and using Lemma <ref>, we have

\begin{align*}
& 2^{k_{M,a_{2}}+1} = N_{T_{k_{M,a_{2}} + 2}(a_{2}), a_{2}}  \ge (T_{k_{M,a_{2}} + 2}(a_{2}) - 1)( \omega_{a_{2}} - \gamma) \: ,
\end{align*}

Therefore, combining the above yields

\begin{align*}
(T_{k_{M,a_{2}} + 2}(a_{2}) - 1) \le (T_{k_{M,a_{1}} + 2}(a_{1}) - 1 ) 2\frac{\omega_{a_{2}} + \gamma}{\omega_{a_{2}} - \gamma} \le (T_{k_{M,a_{2}} + 2}(a_{2}) - 1 )(2+\eta) \: ,
\end{align*}

where the last inequality uses that $\gamma \in (0, \tilde \gamma_{\boldsymbol{\mu}})$ and $\tilde \gamma_{\boldsymbol{\mu}} \in (0, \gamma_{\boldsymbol{\mu}})$ is such that $2\max_{a \in [K]}(\omega_{a} + \gamma)/(\omega_{a} - \gamma) \le 2+\eta$.
We take $n \ge N_{3} = \max_{a \in [K]} T_{k_{M,a} + 2}(a)$, hence we have $k_{n,a} \ge k_{M,a} + 2$ for all $a \in [K]$.
Since $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}(\omega)]  < + \infty$ (i.e. arms are sampled linearly), it is direct to see that $\bE_{\bnu}[\max_{a \in [K]} T_{k_{M,a} + 2}(a)] < +\infty$.
This concludes the proof.

Note that $T_{\boldsymbol{\mu}, \gamma}$ defined in <ref> is such that $T_{\boldsymbol{\mu}, \gamma} = T_{\boldsymbol{\mu}, \gamma}(\omega^\star_{\mathrm{KL},\beta})$ where $T_{\boldsymbol{\mu}, \gamma}(\omega)$ as in Equation (<ref>).
Lemma <ref> showed that $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}]  < + \infty$ for all $\gamma > 0$.
Therefore, the condition of Lemma <ref> are fulfilled by .

§.§ Asymptotic expected sample complexity

The final step of the generic analysis of Top Two algorithms [27] is to invert the private GLR stopping rule by leveraging the convergence of the empirical proportions towards the $\beta$-optimal allocation.
Compared to the non-private GLR stopping rule, the private threshold in the private GLR stopping rule involves an additive term in $\cO(\log(1/\delta)^2)$.
This difference is the largest price that we pay to obtain a private BAI algorithm.
We defer the reader to Appendix <ref> for a more detailed discussion on it.

Asymptotically $\beta$-optimal $\epsilon$-DP-FC-BAI algorithm. The inversion of the GLR stopping rule by leveraging the convergence of the empirical proportions towards the ($\beta$-)optimal allocation is a generic method used in the BAI literature.
Provided this convergence is shown, it only depends on the threshold that ensures $\delta$-correctness.
More precisely, it only depends on its asymptotic dependence in $\log(1/\delta)$.
In addition to the multiplicative four-factor, the price of privacy for asymptotically $\beta$-optimal BAI algorithms when combined with the non-private GLR stopping rule is a problem dependent multiplicative factor $1 + \sqrt{1 +\Delta_{\max}^2/(2\epsilon^2)}$ (Lemma <ref>).

Let $(\delta, \beta) \in (0,1)^2$.
Assume that there exists $\gamma_{\boldsymbol{\mu}} > 0$ such that for $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}]  < + \infty$ for all $\gamma \in (0, \gamma_{\boldsymbol{\mu}})$, where $T_{\boldsymbol{\mu}, \gamma}$ is defined in Equation (<ref>).
Combining the private GLR stopping rule (Equation (<ref>)) with private threshold (Equation (<ref>)) yields a $\delta$-correct algorithm which satisfies that, for all $\bnu$ with mean $\boldsymbol{\mu}$ such that $|a^\star(\boldsymbol{\mu})| = 1$,

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
\le 4T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) \left( 1 + \sqrt{1 +\frac{\Delta_{\max}^2}{2\epsilon^2}}  \right) \: .
\]

Theorem <ref> yields the $\delta$-correctness.

Let $a^\star$ be the unique best arm, i.e. $a^\star(\boldsymbol{\mu}) = \{a^\star\}$.
Let $\zeta > 0$.
Using Equation (<ref>) and the continuity of

\[
(\boldsymbol{\mu}, w) \mapsto \min_{a \ne a^\star(\boldsymbol{\mu})} \frac{(\mu_{a^\star(\boldsymbol{\mu})} - \mu_{a})^2}{2(1/w_{a^\star(\boldsymbol{\mu})} + 1/w_{a})}
\]

yields that there exists $\gamma_\zeta > 0$ such that $\left\| \frac{N_{n}}{n-1} - \omega^{\star}_{\beta} \right\|_{\infty} \le \gamma_\zeta$ and $\max_{a \in [K]}| \tilde \mu_{k_{n,a}+1, a} - \mu_{a} | \le \gamma_\zeta$ implies that

\begin{align*}
\forall a \ne a^\star , \quad &\frac{(\tilde \mu_{k_{n,a^\star}+1, a^\star} - \tilde \mu_{k_{n,a}+1, a})^2 }{(n-1)/ N_{n, a^\star}+ (n-1)/ N_{n,a}} \ge \frac{2(1-\zeta)}{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})} \\
&\frac{n-1}{N_{n, a^\star}}+ \frac{n-1}{N_{n,a}} \le \frac{\Delta_{a}^2}{2} (1+\zeta) T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) \: .
\end{align*}

We choose such a $\gamma_\zeta $.
Let $\gamma_{\boldsymbol{\mu}} > 0$ be such that for $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}]  < + \infty$ for all $\gamma \in (0, \gamma_{\boldsymbol{\mu}})$, where $T_{\boldsymbol{\mu}, \gamma}$ is defined in Equation (<ref>).
Let $\eta > 0$.
Let $\tilde \gamma_{\boldsymbol{\mu}} \in (0, \gamma_{\boldsymbol{\mu}})$ as in Lemma <ref> for this $\eta$.
In the following, let us consider $\gamma \in (0, \min\{\tilde \gamma_{\boldsymbol{\mu}}, \gamma_\zeta, \beta/4, \Delta_{\min}/4\} )$.

Let $N_{3} \ge T_{\boldsymbol{\mu}, \gamma}$ with $\bE_{\bnu} [N_{3}]  < + \infty$ as Lemma <ref> for those $(\gamma, \eta)$.
Then, we have $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}]  < + \infty$ and

\[
\forall n \ge N_{3}, \quad \frac{\max_{a \in [K]}T_{k_{n,a}}(a) - 1}{\min_{a \in [K]}T_{k_{n,a}}(a) - 1} \le 2+\eta \: .
\]

Since arms are sampled linearly, it is direct to construct $N_{4} \ge N_{3}$ with $\bE_{\bnu}[N_{4}] < + \infty$ such that, for all $n \ge N_{4}$, we have $\max_{a \in [K]} \max_{k \in \{k_{n,a}, k_{n,a}+1\}}| \tilde \mu_{k, a} - \mu_{a} | \le \gamma$,
Therefore, we have $\hat a_n = a^\star$.

Let $\kappa \in (0,1)$.
Let $n \ge N_{4}/\kappa$ and $(k_{n,a})_{a \in [K]}$ be the current phases at time $n$.
Combining the above, we have $\hat a_n = a^\star$ and

\begin{align*}
&\max_{a \in [K]}| \tilde \mu_{k_{n,a}+1, a} - \mu_{a} | \le \gamma  \quad ,  \quad \left\| \frac{N_{n}}{n-1} - \omega^{\star}_{\beta}\right\|_{\infty} \le \gamma   \quad \text{and} \quad \frac{\max_{a \in [K]}T_{k_{n,a}}(a) - 1}{\min_{a \in [K]}T_{k_{n,a}}(a) - 1} \le 2+\eta \: .
\end{align*}

Let $a_{1} = \argmin_{a \in [K]}T_{k_{n,a}}(a)$ and $a_{2} = \argmax_{a \in [K]}T_{k_{n,a}}(a)$.
Therefore, we obtain, for all $a \ne a^\star$,

\begin{align*}
\frac{(\tilde \mu_{k_{n,\hat a_{n}}+1,\hat a_{n}}  - \tilde \mu_{k_{n,a}+1, a})^2}{1/\tilde N_{k_{n,\hat a_{n}}+1, \hat a_{n}}+ 1/\tilde N_{k_{n,a}+1,a}} &= \frac{(\tilde \mu_{k_{n,a^\star}+1,a^\star}  - \tilde \mu_{k_{n,a}+1, a})^2}{1/N_{T_{k_{n,a^\star}}(a^\star), a^\star}+ 1/N_{T_{k_{n,a}}(a),a}} \\
&\ge \frac{(\tilde \mu_{k_{n,a^\star}+1,a^\star}  - \tilde \mu_{k_{n,a}+1, a})^2}{1/N_{T_{k_{n,a_{1}}}(a_{1}), a^\star}+ 1/N_{T_{k_{n,a_{1}}}(a_{1}),a}} \\
&\ge (\min_{a \in [K]} T_{k_{n,a}}(a) -1)\frac{2(1-\zeta)}{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}  \: .
\end{align*}

Similarly, we can show that, for all $a \ne a^\star$,

\begin{align*}
\frac{1}{\tilde N_{k_{n,a^\star}+1,a^\star} } + \frac{1}{\tilde N_{k_{n,a}+1,a}} &= \frac{1}{N_{T_{k_{n,a^\star}}(a^\star),a^\star} } + \frac{1}{ N_{T_{k_{n,a}}(a),a}} \\
&\le \frac{1}{N_{T_{k_{n,a_{1}}}(a_{1}),a^\star} } + \frac{1}{ N_{T_{k_{n,a_{1}}}(a_{1}),a}} \\
&\le \frac{1}{\min_{a \in [K]} T_{k_{n,a}}(a) - 1} \frac{\Delta_{a}^2}{2} (1+\zeta) T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) \\
&\le \frac{1}{\min_{a \in [K]} T_{k_{n,a}}(a) - 1} \frac{\Delta_{\max}^2}{2} (1+\zeta) T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})  \: .
\end{align*}

Let $(c_{k})_{k \in \N}$ as in Equation (<ref>).
Using Lemma <ref>, we obtain, for all $a \ne a^\star$,

\begin{align*}
&2 c_{(k_{n,a^\star}+1) (k_{n,a}+1)}(\tilde N_{k_{n,a^\star}+1,a^\star}, \tilde N_{k_{n,a}+1,a}, \delta/2) \le 8 \log(4 + (\max_{b \in [K]}k_{n,b}-1) \log 2 )  \\
&\quad + 4 \cC_{G} \left(\log(1/\delta)/2 +  s\log(\max_{b \in [K]}k_{n,b}-1) +  \log(2(K-1)\zeta (s)^2)/2\right)
\end{align*}

Likewise, we obtain, for all $a \in [K]$,

\begin{align*}
&\frac{1}{\tilde N_{k_{n,a^\star}+1,a^\star} \epsilon^2} \log \left(\frac{2 K (k_{n,a^\star}+1)^{s} \zeta(s)}{\delta} \right)^2 + \frac{1}{\tilde N_{k_{n,a}+1,a} \epsilon^2} \log \left(\frac{2 K (k_{n,a}+1)^{s} \zeta(s)}{\delta} \right)^2 \\
&\le \frac{\Delta_{\max}^2}{2\epsilon^2} \frac{(1+\zeta) T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}{\min_{b \in [K]} T_{k_{n,b}}(b) - 1}  \left( \log(1/\delta) + s \log (\max_{b \in [K]} k_{n,b}+1) + \log (2 K \zeta(s) ) \right)^2
\end{align*}

Let us denote by $T^{+}_{k_n+1} = \max_{b \in [K]} T_{k_{n,b}+1}(b)$, $T^{+}_{k_n+2} = \max_{b \in [K]} T_{k_{n,b}+2}(b)$, $T^{-}_{k_n+1} = \min_{b \in [K]} T_{k_{n,b}+1}(b)$, $T^{-}_{k_n} = \min_{b \in [K]} T_{k_{n,b}}(b)$.
Let $T$ be a time such that $T \ge T^{+}_{k_n+1} \ge \kappa T$.
Using Lemmas <ref> and <ref>, we have

\begin{align*}
(k_{n,b} - 1) \log 2 = \log N_{ T_{k_{n,b}}(b), b} \le \log T_{k_{n,b}}(b) \le \log T^{+}_{k_n} \le \log T^{-}_{k_n} + \log (2+\eta)\: .
\end{align*}

Using the private GLR stopping rule (Equation (<ref>)), we have

\begin{align*}
&\min \left\{\tau_{\delta}, T\right\} -\kappa T \leq   \sum_{T \ge T^{+}_{k_n} \ge \kappa T} (T^{+}_{k_n+2} - T^{+}_{k_n+1}) \indi{\tau_{\delta} > T^{+}_{k_n+1}} \\
&\leq  \sum_{T \ge T^{+}_{k_n} \ge \kappa T} (T^{+}_{k_n+2} - T^{+}_{k_n+1})  \mathds{1}\left( \exists a \ne a^\star, \: \frac{(\tilde \mu_{k_{n,a^\star}+1,a^\star}  - \tilde \mu_{k_{n,a}+1, a})^2}{1/\tilde N_{k_{n,a^\star}+1, a^\star}+ 1/\tilde N_{k_{n,a}+1,a}} \right.\\
&\qquad \qquad \left. < 2c_{\epsilon,k_{n,a^\star}+1,k_{n,a}+1}(\tilde N_{k_{n,a^\star}+1,a^\star}, \tilde N_{k_{n,a}+1,a},\delta) \right)\\
&\leq \sum_{T \ge T^{+}_{k_n} \ge \kappa T} (T^{+}_{k_n+2} - T^{+}_{k_n+1}) \mathds{1}\left( (T^{-}_{k_{n}} -1)\frac{1-\zeta}{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}  < 8 \log( 4 + \log T^{-}_{k_{n}}+ \log(2+\eta)  ) \right.\\
&\quad + 4 \cC_{G} \left(\log(1/\delta)/2 +  s\log(2 + \log_{2} T^{-}_{k_{n}} + \log_{2} (2+\eta)) + \log(2(K-1)\zeta (s)^2)/2\right)   \\
&\quad \left. +  \frac{\Delta_{\max}^2}{2\epsilon^2} \frac{(1+\zeta) T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}{T^{-}_{k_{n}} - 1}  \left( \log(1/\delta) + s \log ( 2 + \log_{2} T^{-}_{k_{n}} + \log_{2} (2+\eta) ) + \log (2 K \zeta(s) ) \right)^2 \right) \: ,
\end{align*}

Let $T_{\zeta}(\delta)$ defined as the largest deterministic time such that the above condition is satisfied when replacing $T^{-}_{k_n}$ by $(1-\kappa)T$.
Let $k_{\delta}$ be the largest random vector of phases such that that $T^{+}_{k_{\delta}+1} \le T_{\zeta}(\delta)$ almost surely, hence $T^{+}_{k_{\delta}+2} > T_{\zeta}(\delta)$ almost surely.
Then, using the above yields that $\tau_{\delta} \le T^{+}_{k_{\delta}+2} $ almost surely, hence

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}[\tau_{\delta}]}{\log(1/\delta)} \le \limsup_{\delta \to 0} \frac{\bE_{\bnu}[T^{+}_{k_{\delta}+2}]}{\log(1/\delta)} \le (2+\eta)^2\limsup_{\delta \to 0} \frac{\bE_{\bnu}[T^{+}_{k_{\delta}+1}]}{\log(1/\delta)} \le (2+\eta)^2\limsup_{\delta \to 0} \frac{ T_{\zeta}(\delta)}{\log(1/\delta)} \: ,
\]

where the second inequality uses Lemma <ref> twice, i.e. $T^{+}_{k_{\delta}+2} \le (2+\eta) T^{-}_{k_{\delta}+2} \le (2+\eta)^2 T^{+}_{k_{\delta}+1}$, and the last one used the definition of $k_{\delta}$ and that $T_{\zeta}(\delta)$ is deterministic.

Since we are only interested in upper bounding $\limsup_{\delta \to 0} \frac{ T_{\zeta}(\delta)}{\log(1/\delta)}$, we can safely drop the second orders terms in $T$ and $\log(1/\delta)$.
This allows us to remove the terms in $\cO(\log \log T)$ and in $\cO(\log \log (1/\delta))$.
Using that $ \cC_{G}(x) = x + \cO(\log x)$, tedious manipulations yields that

\[
\limsup_{\delta \to 0} \frac{ T_{\zeta}(\delta)}{\log(1/\delta)} \le \frac{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}{1-\kappa} D_{\zeta}(\mu, \epsilon) \: ,
\]

\begin{align*}
D_{\zeta}(\mu, \epsilon) = \sup \left\{ x \mid  x^2 < \frac{2}{1-\zeta} x + \frac{1+\zeta}{1-\zeta}\frac{\Delta_{\max}^2}{2\epsilon^2} \right\} \le \frac{1}{1-\zeta} \left( 1 + \sqrt{1 + (1-\zeta^2)\frac{\Delta_{\max}^2}{2\epsilon^2}}  \right) \: .
\end{align*}

The last inequality uses that $x^2 - 2bx - c < 0$ for all $x \in [0, b(1 + \sqrt{1 + c/b^2}))$.
Therefore, we have shown that

\begin{align*}
\limsup_{\delta \to 0} \frac{\bE_{\bnu}[\tau_{\delta}]}{\log(1/\delta)} \le (2+\eta)^2 \frac{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}{(1-\kappa)(1-\zeta)} \left( 1 + \sqrt{1 + (1-\zeta^2)\frac{\Delta_{\max}^2}{2\epsilon^2}}  \right) \: .
\end{align*}

Letting $\kappa$, $\eta$ and $\zeta$ goes to zero yields that

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
\le 4T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) \left( 1 + \sqrt{1 +\frac{\Delta_{\max}^2}{2\epsilon^2}}  \right) \: .
\]

Concluding the proof of Theorem <ref>. Combining Lemmas <ref>, <ref>, <ref> and <ref> concludes the proof of Theorem <ref>.
We restrict the result to instances such that $\min_{a \ne b}|\mu_{a} - \mu_{b}| > 0$ in order for Lemma <ref> to hold.
Note that this is an artifact of the asymptotic proof which could be alleviated with more careful considerations.

Asymptotically optimal $\epsilon$-DP-FC-BAI algorithm.
While Lemma <ref> is derived for BAI algorithms converging towards the $\beta$-optimal allocation $\omega_{\mathrm{KL}, \beta}^\star(\boldsymbol{\mu})$, it is direct to see that a similar inversion results can be obtained for BAI algorithms that converge towards the unique optimal allocation $\omega_{\mathrm{KL}}^\star(\boldsymbol{\mu}) = \{w^\star\}$ defined as

\begin{equation} \label{eq:optimal_allocation}
\omega^{\star}_{\mathrm{KL}}(\boldsymbol{\mu}) \defn \argmax_{\omega \in \Sigma_K} \min_{a \ne a^\star} \frac{\Delta_{a}^2}{1/\omega_{a^\star} + 1/\omega_{a}}  \: .
\end{equation}

At equilibrium, we have equality of the transportation costs (see [26] for example), namely

\begin{equation} \label{eq:equality_equilibrium_bis}
\forall a \ne a^\star, \quad \frac{\Delta_{a}^2}{1/\omega^{\star}_{a^\star} + 1/\omega^{\star}_{a}} = 2 T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu})^{-1} \: .
\end{equation}

In addition to the multiplicative four-factor, the price of privacy for asymptotically optimal BAI algorithms when combined with the non-private GLR stopping rule is a problem dependent multiplicative factor $1 + \sqrt{1 +\Delta_{\max}^2/(2\epsilon^2)}$ (Lemma <ref>).
We omit the proof since it is the same as the one of Lemma <ref>.

Let $\delta \in (0,1)$
Assume that there exists $\gamma_{\boldsymbol{\mu}} > 0$ such that for $\bE_{\bnu} [T_{\boldsymbol{\mu}, \gamma}(\omega^\star)]  < + \infty$ for all $\gamma \in (0, \gamma_{\boldsymbol{\mu}})$, where $T_{\boldsymbol{\mu}, \gamma}(w)$ is defined in Equation (<ref>) and $\omega^\star$ is defined in Equation (<ref>).
Combining the private GLR stopping rule (Equation (<ref>)) with private threshold (Equation (<ref>)) yields a $\delta$-correct algorithm which satisfies that, for all $\bnu$ with mean $\mu$ such that $|a^\star(\boldsymbol{\mu})| = 1$,

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
\le 4T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu}) \left( 1 + \sqrt{1 +\frac{\Delta_{\max}^2}{2\epsilon^2}}  \right) \: .
\]

§.§ Connection to the lower bound

In this section, we compare the sample complexity lower bound of Corollary <ref> with the sample complexity upper bound of Theorem <ref>.

Simplification of the upper bound. The asymptotic expected sample complexity of  (Theorem <ref>) is upper bounded by

\begin{align*}
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
&\leq 4T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) \left( 1 + \sqrt{1 +\frac{\Delta_{\max}^2}{2\epsilon^2}}  \right)\\
&\underset{(a)}{\leq} 4T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})  \left( 2 + \frac{\Delta_{\max}}{\sqrt{2} \epsilon}  \right)
\end{align*}

where $T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})$ is the $\beta$-characteristic time for Gaussian bandits, and (a) is due to the sub-additivity of the square root.

For $\beta = 1/2$, [45] showed that $T^{\star}_{\mathrm{KL},1/2}(\boldsymbol{\mu}) \le 2 T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu})$.

On the other hand, [21] showed that $H(\boldsymbol{\mu}) \le T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu}) \le 2 H(\boldsymbol{\mu})$, where $H(\boldsymbol{\mu}) \defn \sum_{a \in [K]} 2 \Delta_{a}^{-2}$ with $\Delta_{a^\star} = \Delta_{\min}$.

Plugging these two inequalities in the upper bound of Theorem <ref> with $\beta = 1/2$ gives that

\begin{align*}
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
&\leq 8T^{\star}_{\mathrm{KL},1/2}(\boldsymbol{\mu}) + 16 H(\boldsymbol{\mu}) \frac{\Delta_{\max}}{\sqrt{2} \epsilon}
\end{align*}

Since we consider Bernoulli distributions, we know that $0 < \Delta_{\min} \le \Delta_{\max} < 1$.
If we restrict ourselves to instances such that all the gaps have the same order of magnitude (Condition 1): there exists a constant $C \ge 1$ such that $\Delta_{\max} \le C \Delta_{\min}$.

For such instances, we obtain

\begin{align*}
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
&\leq 8T^{\star}_{\mathrm{KL},1/2}(\boldsymbol{\mu}) + 16 H(\boldsymbol{\mu}) \frac{C \Delta_{\min}}{\sqrt{2} \epsilon}\\
&\leq 8T^{\star}_{\mathrm{KL},1/2}(\boldsymbol{\mu}) + 16 \sqrt{2} \frac{C}{ \epsilon} \left(\frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a} \right)
\end{align*}

where the last inequality is due to $H(\boldsymbol{\mu}) \Delta_{\min} \leq \frac{2}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{2}{\Delta_a}  $.

Finally using that $a + b \leq 2 \max(a, b)$, we get that

\begin{align*}
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
&\leq c \max\left\{T^{\star}_{\mathrm{KL},1/2}(\boldsymbol{\mu}), \frac{C}{\epsilon} \left(\frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a} \right) \right\}
\end{align*}

for the universal constant $c = 45.26$.

The lower bound for Bernoulli instances.
For Bernoulli instances, Corollary <ref> gives that the lower bound of the expected sample complexity of any $\delta$-correct $\epsilon$-global DP BAI strategy is

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)} \ge \max\left\{ T^{\star}_{\mathrm{KL}}(\bnu) , \: \frac{1}{6 \epsilon}  \left(\frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a} \right)\right\} \: .
\]

where we use Proposition <ref> to replace $T^{\star}_{\mathrm{TV}}(\bnu)$ and  $T^{\star}_{\mathrm{KL}}(\bnu)$ is the characteristic time for Bernoulli bandits.

Upper-lower bound discussion for the two privacy regimes.
In the low privacy regime, our upper bound retrieves $T^{\star}_{\mathrm{KL},1/2}(\boldsymbol{\mu})$ for Gaussian distributions. Since the rewards in the analysis are supposed Bernoulli, the mismatch from exact optimality is coming from the mismatch between the KL divergence of Bernoulli distributions and that of Gaussian, which is generally controllable in most instances where the means are far from the borders, i.e. $0$, and  $1$. This is in essence, similar to the mismatch between UCB and KL-UCB in the regret-minimization literature (Chapter 10 in [34]). To overcome this mismatch, it is necessary to adapt the transportation costs to the family of distributions considered. In our setting, this can be done by using the Bernoulli KL rather than Gaussian KL in lines 12 and 16 of the algorithm. While the Top Two algorithms for Bernoulli distributions have been studied in [27], the analysis is more involved. Therefore, it would obfuscate where and how privacy is impacting the expected sample complexity.

In the high privacy regime, and for instances verifying Condition 1, our upper bound matches the lower bound $ \epsilon^{-1} T^{\star}_{\mathrm{TV}}(\bnu)$ up to a constant. Having matching upper and lower bounds only for high privacy regimes is an interesting phenomenon that appears in different settings of differential privacy literature, such as regret minimization [5], parameter estimation [9] and hidden probabilistic graphical models [43].
We speculate two facets of this phenomenon:

1. Explicit bounds in high and low privacy regimes: We have matching bounds only in the high or low privacy regimes because the lower bounds are generally harder to explicit and understand in transitional phases. Thus, it is harder to claim optimality in those phases.

2. Information-theoretic roots: There might be a more profound information-theoretic reason in relation to [43]. Indeed, there seems to be a link between the privacy budget $\epsilon$ and the information thresholds introduced in [43]. Specifically, if the randomized mapping $\mathcal{F}$ in [3] satisfies DP, then the noisy information threshold and noiseless information threshold can be similarly written as a function of $\epsilon$ and the total variation. Finding a rigorous link between these two quantities is an interesting question to explore.

§.§ Limitation and open problem

In the previous section (Appendix <ref>), we argue that the upper and lower bounds match up to multiplicative constants in both privacy regimes, provided we restrict ourselves to instances satisfying Condition 1 (i.e. there exists $C \ge 1$ such that $\Delta_{\max} \le C \Delta_{\min}$).

While this holds for numerous instances, it does not account for instances in which the gaps have different orders of magnitude.
One example would be the regime where $\Delta_{\min} \to 0$ while $\Delta_{\max}$ is fixed, hence yielding $T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu}) \to + \infty$.

In Appendix <ref> (see Lemma <ref> and <ref>), we show that combining the private GLR stopping rule (Equation (<ref>)) with any BAI algorithms whose empirical proportions converge towards the $\beta$-optimal allocation $\omega^{\star}_{\mathrm{KL}, \beta}(\boldsymbol{\mu})$ for Gaussian bandits will incur a problem dependent multiplicative cost

\begin{equation}\label{eq:the_curse}
1 + \sqrt{1 +\frac{\Delta_{\max}^2}{2\epsilon^2}}
\end{equation}

in addition to the multiplicative four-factor due to doubling and forgetting.

In order to have matching upper and lower bounds, we would need to have $\Delta_{\min}$ instead of $\Delta_{\max}$ in Equation (<ref>).
Unfortunately, our results show that it is not possible when using the private GLR stopping rule (Equation (<ref>)) and a sampling rule that is tailored to asymptotic ($\beta$-)optimality for Gaussian bandits.
Therefore, this impossibility result holds for a large class of BAI sampling rules when adapting them to tackle private BAI by using the private GLR stopping rule (Equation (<ref>)).

Origin of this limitation.
The term $\Delta_{\max}$ appears due to the private stopping threshold that ensures $\delta$-correctness of the private GLR stopping rule (Equation (<ref>)).

For asymptotically ($\beta$-)optimal algorithms, the additive term due to privacy in the threshold is of the order

\[
\frac{1}{\epsilon^2} \left(\frac{1}{N_{n,a}} + \frac{1}{N_{n,a^\star}} \right)\log(1/\delta)^2 \approx_{n \to + \infty} \frac{T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu})}{n}\frac{\Delta_{a}^2}{2\epsilon^2} \log(1/\delta)^2 \: .
\]

Therefore, the private GLR stopping rule (Equation (<ref>)) will stop when, for all $a \ne a^\star$,

\[
\frac{n}{T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu})} \ge 2 \log(1/\delta) + \frac{T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu})}{n}\frac{\Delta_{a}^2}{2\epsilon^2} \log(1/\delta)^2 \: ,
\]

which yields the problem-dependent multiplicative cost $1 + \sqrt{1 +\frac{\Delta_{\max}^2}{2\epsilon^2}}$.

Open problem.
This impossibility result is specific to the way we derive an $\epsilon$-DP version of the GLR stopping rule.
Therefore, a natural question is whether it is possible to derive a better private GLR stopping rule to match the lower bound for all Bernoulli instances.

A two-phase algorithm.  tracks the non-private lower bound (i.e. $T^\star_{KL}$) as a non-private algorithm would do, and the additional cost tracking that privately is shown to be $T^\star_{TV}/\epsilon$ (up to constants for bandits verifying Condition 1), where the additional cost comes from the added Laplace noise. Another approach would be to first perform a test to determine in which privacy regime the policy resides, and then track (privately) the corresponding characteristic time. Such an algorithm would empirically estimate both $T^{\star}_{TV}$ and $T^{\star}_{KL}$ in the first phase. If the privacy budget $\epsilon$ is bigger than the empirical estimate of $T^{\star}_{TV}/T^{\star}_{KL}$, then this means that we are in the low privacy regime and the algorithm tracks (privately) the KL characteristic time in the second phase (as  does). However, if the privacy budget $\epsilon$ is smaller than the empirical estimate of $T^{\star}_{TV}/T^{\star}_{KL}$, then it is the high privacy regime and the algorithm tracks (privately) the TV characteristic time in the second phase. For such a two-phase algorithm to achieve optimality, properly tuning the amount of time spent in its first phase is a crucial step. Whether it is possible to analyze such an algorithm and quantify the proper tuning (if it even exists) is an interesting direction for future work.

Non-asymptotic sample complexity of .
In the non-private FC-BAI literature (i.e. $\epsilon = + \infty$), there is no tight lower bound in the non-asymptotic regime (i.e. for any value of $\delta$). This is the main open problem in FC-BAI, and hence in DP-FC-BAI too.
In the class of asymptotically ($\beta$-)optimal algorithms, TTUCB [26] is one of the few to have non-asymptotic guarantees.
Adapting the non-asymptotic analysis of [26] to the private AdaP-TT is an interesting direction for research.
We conjecture that such an adaptation is possible (up to technicalities) by adding concentration terms linked to Laplace distribution and losing at least a multiplicative four-factor compared to TTUCB due to doubling and forgetting.

§.§ Analysis of non-private : Proof of Theorem <ref>

The proofs detailed in Appendices <ref> and <ref> can easily by adapted to provide guarantees on the non-private , which relies on the non-private leader/challenger defined in Equation (<ref>) and Equation (<ref>).

The key difference between the non-private  and the private  lies in the definition of the stopping threshold.
While the private GLR stopping rule (Equation (<ref>)) has an additive terms in $\cO(\log(1/\delta)^2/\epsilon)$ to cope for the uncertainty due to the Laplace noise, the non-private GLR stopping rule (Equation (<ref>)) scales simply as $\log(1/\delta)$.
This has drastic consequences in terms of asymptotic upper bound on the expected sample complexity.

It is direct to see that most manipulations from Appendix <ref> still holds for the non-private .
Therefore, we use the notations and conditions defined therein.
We show that the non-private GLR stopping rule (Equation (<ref>)) yields

\begin{align*}
&\min \left\{\tau_{\delta}, T\right\} -\kappa T\\
&\leq   \sum_{T \ge T^{+}_{k_n} \ge \kappa T} (T^{+}_{k_n+2} - T^{+}_{k_n+1}) \indi{\tau_{\delta} > T^{+}_{k_n+1}} \\
&\leq  \sum_{T \ge T^{+}_{k_n} \ge \kappa T} (T^{+}_{k_n+2} - T^{+}_{k_n+1})~~\mathds{1}\Bigg( \exists a \ne a^\star, \: \frac{(\hat \mu_{k_{n,a^\star}+1,a^\star}  - \hat \mu_{k_{n,a}+1, a})^2}{1/\tilde N_{k_{n,a^\star}+1, a^\star}+ 1/\tilde N_{k_{n,a}+1,a}} \\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad  < 2c_{(k_{n,a^\star}+1)(k_{n,a}+1)}(\tilde N_{k_{n,a^\star}+1,a^\star}, \tilde N_{k_{n,a}+1,a},\delta) \Bigg) \\
&\leq \sum_{T \ge T^{+}_{k_n} \ge \kappa T} (T^{+}_{k_n+2} - T^{+}_{k_n+1})~~\mathds{1}\Bigg( (T^{-}_{k_{n}} -1)\frac{1-\zeta}{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}  < 4 \log( 4 + \log T^{-}_{k_{n}}+ \log(2+\eta)  ) \\
&\qquad + 2 \cC_{G} \left(\log(1/\delta)/2 +  s\log(2 + \log_{2} T^{-}_{k_{n}} + \log_{2} (2+\eta)) + \log((K-1)\zeta (s)^2)/2\right) \Bigg) \: ,
\end{align*}

Let $T_{\zeta}(\delta)$ defined as the largest deterministic time such that the above condition is satisfied when replacing $T^{-}_{k_n}$ by $(1-\kappa)T$.
Let $k_{\delta}$ be the largest random vector of phases such that that $T^{+}_{k_{\delta}+1} \le T_{\zeta}(\delta)$ almost surely, hence $T^{+}_{k_{\delta}+2} > T_{\zeta}(\delta)$ almost surely.
Then, using the above yields that $\tau_{\delta} \le T^{+}_{k_{\delta}+2} $ almost surely, hence

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}[\tau_{\delta}]}{\log(1/\delta)} \le \limsup_{\delta \to 0} \frac{\bE_{\bnu}[T^{+}_{k_{\delta}+2}]}{\log(1/\delta)} \le (2+\eta)^2\limsup_{\delta \to 0} \frac{\bE_{\bnu}[T^{+}_{k_{\delta}+1}]}{\log(1/\delta)} \le (2+\eta)^2\limsup_{\delta \to 0} \frac{ T_{\zeta}(\delta)}{\log(1/\delta)} \: ,
\]

First-order terms.
Since we are only interested in upper bounding $\limsup_{\delta \to 0} \frac{ T_{\zeta}(\delta)}{\log(1/\delta)}$, we can safely drop the second orders terms in $T$ and $\log(1/\delta)$.
This allows us to remove the terms in $\cO(\log \log T)$ and in $\cO(\log \log (1/\delta))$.
Using that $ \cC_{G}(x) = x + \cO(\log x)$, tedious manipulations yields that

\[
\limsup_{\delta \to 0} \frac{ T_{\zeta}(\delta)}{\log(1/\delta)} \le \frac{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}{(1-\kappa)(1 - \zeta)} \: .
\]

Letting $\kappa$, $\eta$ and $\zeta$ goes to zero yields that

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}\left[\tau_{\delta}\right]}{\log (1 / \delta)}
\le 4T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})  \: .
\]

§ EXTENDED EXPERIMENTAL ANALYSIS

In this section, we perform additional experiments to compare  and DP-SE for FC-BAI. We test the two algorithms in six bandit environments with Bernoulli distributions, as defined by [46], namely

\begin{align*}
&\mu_1 = (0.95, 0.9, 0.9, 0.9, 0.5),~~~&&\mu_2 = (0.75, 0.7, 0.7, 0.7, 0.7),\\
&\mu_3 = (0, 0.25, 0.5, 0.75, 1),~~~&&\mu_4 = (0.75, 0.625, 0.5, 0.375, 0.25)  \},\\
&\mu_5 = (0.75, 0.53125, 0.375, 0.28125, 0.25),~~~&&\mu_6 = (0.75, 0.71875, 0.625, 0.46875, 0.25)  \}.
\end{align*}

For each Bernoulli instance, we implement the algorithms with
\[\epsilon \in \{0.001, 0.005, 0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1, 10 \}, \]

and a risk level $\delta = 0.01$. We verify empirically that the algorithms are $\delta$-correct by running each algorithm $100$ times. In Figure <ref>, we plot the evolution of the average stopping time and standard deviation with respect to the privacy budget $\epsilon$. All the algorithms are implemented in Python (version $3.8$) and are tested with an 8-core 64-bits Intel<EMAIL_ADDRESS>GHz CPU.

All the experiments validate the same conclusions as the ones reached in Section <ref>, i.e.

*  requires fewer samples to provide a $\delta$-correct answer,

* there exists two privacy regimes, and
in the low-privacy regime, the sample complexity is independent of the privacy budget.

Evolution of the stopping time $\tau$ (mean $\pm$ std. over 100 runs) of , DP-SE, and TTUCB with respect to the privacy budget $\epsilon$ for $\delta = 10^{-2}$ on different Bernoulli instances. The shaded vertical line separates the two privacy regimes.  outperforms DP-SE.