Best Arm Identification (BAI) problems are progressively used for data-sensitive applications, such as designing adaptive clinical trials, tuning hyper-parameters, and conducting user studies to name a few. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence under $\epsilon$-global Differential Privacy (DP).
First, to quantify the cost of privacy, we derive a lower bound on the sample complexity of any $\delta$-correct BAI algorithm satisfying $\epsilon$-global DP. Our lower bound suggests the existence of two privacy regimes depending on the privacy budget $\epsilon$. In the high-privacy regime (small $\epsilon$), the hardness depends on a coupled effect of privacy and a novel information-theoretic quantity, called the Total Variation Characteristic Time. In the low-privacy regime (large $\epsilon$), the sample complexity lower bound reduces to the classical non-private lower bound.
Second, we propose , an $\epsilon$-global DP variant of the Top Two algorithm.  runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. We derive an asymptotic upper bound on the sample complexity  of  that matches with the lower bound up to multiplicative constants in the high-privacy regime.
Finally, we provide an experimental analysis of  that validates our theoretical results.

§ INTRODUCTION

We study the stochastic multi-armed bandit problem [34], which allows us to reflect on fundamental information-utility trade-offs involved in interactive sequential learning. Specifically, in a bandit problem, a learning agent is exposed to interact with $K$ unknown probability distributions $\lbrace \nu_1, \ldots, \nu_K \rbrace$ with bounded expectations, referred as the reward distributions (or arms). $\boldsymbol{\nu} \triangleq \lbrace \nu_1, \ldots, \nu_K \rbrace$ is called a bandit instance. At every step $t>0$, the agent chooses to interact with one of the reward distributions $\nu_{A_t}$ for an $A_t \in [K]$, and obtains a sample (or reward) $r_t$ from it. The goal of the agent can be of two types: (a) maximise the reward accumulated over time, or equivalently to minimise the regret, and (b) to find the reward distribution (or arm) with highest expected reward. The first problem is called the regret-minimisation problem [3], while the second one is called the Best Arm Identification (BAI) problem [31]. In this paper, we focus on the BAI problem, i.e. to compute

\begin{align}\label{eq:BAI}
a^\star \triangleq \argmax_{{\color{red}a} \in [K]} \underset{r\sim \nu_{\color{red}a}}{\mathbb{E}}[r] \triangleq \argmax_{{\color{red}a} \in [K]} \mu_{\color{red}a} .\tag{BAI}
\end{align}

With its advent in 1950s [7, 8] and resurgence in last two decades [39, 20, 23, 31, 13], BAI has been extensively studied with different structural assumptions (Fixed-confidence: [24]; Fixed-budget: [10]; Non-stochastic: [25]; Best-of-both-worlds: [1]; Linear: [49]). In this paper, we specifically investigate the Fixed Confidence BAI problem, in brief FC-BAI, that yields a $\delta$-correct recommendation $\hat{a} \in [K]$ satisfying $\Pr(\hat{a} \neq a^\star) \leq \delta$.
FC-BAI is increasingly deployed for different applications, such as clinical trials [4], hyper-parameter tuning [35], communication networks [37], online advertisement [11], crowd-sourcing [52], user studies [38], and pandemic mitigation [36] to name a few. All of these applications often involve the sensitive and personal data of users, which raises serious data privacy concerns [51], as illustrated in Example <ref>.

[Adaptive dose finding trial]
In a dose-finding trial, one physician decides $K$ possible dose levels of a medicine based on preliminary studies $($Typically, $K \in \{3, \ldots, 10\}$ in practice [4]$)$.
At each step $t$, a patient is chosen from a local pool of volunteers and a dose level $a_t \in [K]$ is applied to the patient. Following that, the effectiveness of the dose on the patient, i.e. $r_t \in \R$ is observed.
The goal of the physician is to recommend after the trial, which dose level is most effective on average, i.e. the dose level $a^*$ that maximises the expected reward.
Here, every application of a dose level and the patient's reaction to it exposes information regarding the medical conditions of the patient.
Additionally, at each step $t$ of an adaptive sequential trial, the physician can use an FC-BAI algorithm that observes the previous history of dose levels $\{a_s\}_{s< t}$ and their effectiveness $\{r_s\}_{s< t}$ to decide on the next dose level $a_{t}$ to test.
When releasing the experimental findings of the trial to health authorities, the physician should thoroughly detail the experimental protocol. This includes the dose allocated to each patient $\{a_s\}_{s\leq t}$ and the final recommended dose level $a^\star$.
Thus, even if the sequence of reactions to doses $\{r_s\}_{s\leq t}$ is kept secret, publishing the sequence of chosen dose levels $\{a_s\}_{s\leq t}$ and the final recommended dose level $a^\star$ computed using the history can leak information regarding patients involved in the trial.

This example demonstrates the need for privacy in best-arm identification. In this paper, we investigate privacy-utility trade-offs for a privacy-preserving algorithm in FC-BAI.
Specifically, we use the celebrated Differential Privacy (DP) [18] as the framework to preserve data privacy. DP ensures that an algorithm's output is unaffected by changes in input by a single data point. By limiting the amount of sensitive information that an adversary can deduce from the output, DP renders an individual corresponding to a data point `indistinguishable'.
A popular way to achieve DP is to inject a calibrated amount of noise, from a Laplace [18] or Gaussian distribution [14], into the algorithm.
The scale of the noise is set to be proportional to the algorithm’s sensitivity and inversely proportional to the privacy budget $\epsilon$.

Specifically, we study $\epsilon$-global DP, where users trust the centralised decision-maker with access to the raw sensitive rewards. For example, in an adaptive dose-finding trial, the patients trust the physician conducting the trial. Thus, at any time $t$, she has access to all the true history $\{a_s, r_s\}_{s < t}$, and it is her duty to design an algorithm such that publishing $\{a_s\}_{s \leq t}$ and the recommended optimal dose $a^\star$ obeys $\epsilon$-DP given the sensitive input, i.e. the effectiveness of the dose levels on the patients $\{r_s\}_{s \leq t}$. We define the notion of $\epsilon$-global DP for BAI rigorously in Section <ref>.

For different settings of bandits, the cost of $\epsilon$-global DP and optimal algorithm design techniques are widely studied in the regret-minimization problem [41, 50, 46, 48, 42, 6, 5]. Recently, a problem-dependent lower bound on regret of stochastic multi-armed bandits with $\epsilon$-global DP and an algorithm matching the regret lower bound is proposed by [5].
In contrast, DP is meagerly studied in the FC-BAI problem of bandits [46, 29].
Though efficient algorithm design in FC-BAI literature is traditionally propelled by deriving tight lower bounds, we do not have any explicit sample complexity lower bound for FC-BAI satisfying $\epsilon$-global DP.
Here, by an `efficient' algorithm, we refer to the FC-BAI algorithms that aim to minimise the expected number of samples required (alternatively called, expected stopping time) to find a $\delta$-correct recommendation.
Presently, we know neither the minimal cost in terms of sample complexity for ensuring DP in FC-BAI, nor the feasibility of efficient algorithm design to achieve the minimal cost.

Motivated by this gap in the literature, we aim to address two questions:

* What is the fundamental hardness of ensuring Differential Privacy in the Best-Arm Identification with fixed confidence problem ($\epsilon$-DP-FC-BAI) in terms of a lower bound on the sample complexity?

* How to design an efficient $\epsilon$-DP-FC-BAI algorithm that achieves the lower bound order-optimally?

Our contributions. These questions have led to the following contributions:

1. Hardness as lower bounds: We commence our study by deriving the lower bound on sample complexity (or expected stopping time) of any FC-BAI algorithm ensuring $\epsilon$-global DP, in brief $\epsilon$-DP-FC-BAI (Section <ref>). In Theorem <ref>, we prove that the sample complexity of $\epsilon$-DP-FC-BAI depends on the minimum of two information-theoretic quantities one that depends on privacy, and the other that originates from the classical sample complexity of non-private FC-BAI [31]. The term dependent on privacy depends on the privacy budget $\epsilon$, and a novel information-theoretic quantity, referred to as the Total Variation Characteristic Time $T^*_{\mathrm{TV}}$. $T^*_{\mathrm{TV}}$ depends on the Total Variation (TV) distance between the reward distributions in the bandit problem and corresponding most confusing instance. The lower bound also indicates that, in a similar spirit as the regret minimisation with $\epsilon$-global DP [5], there are two regimes of hardness for $\epsilon$-DP-FC-BAI. For lower level of privacy (i.e. higher $\epsilon$), the sample complexity of $\epsilon$-DP-FC-BAI is identical to that of the non-private FC-BAI. But for higher level of privacy (i.e. lower $\epsilon$), the sample complexity depends on $\epsilon$ and $T^*_{\mathrm{TV}}$.

2. Algorithm design: Following the lower bounds, we aim to design an efficient $\epsilon$-DP-FC-BAI algorithm that simultaneously achieves the lower bound order-optimally and is computationally efficient (Section <ref>). Due to the superior empirical performance and computational efficiency of Top Two algorithms, we design an $\epsilon$-DP variant of Top Two algorithms, named . Specifically, we show two simple design techniques, i.e. adaptive episodes for each arm and Laplacian mechanism, if properly used, lead to  from the non-private TTUCB [26]. We further derive an asymptotic (as $\delta \rightarrow 0$) upper bound on the sample complexity of  (Theorem <ref>). In the high-privacy regime, the sample complexity upper bound of  coincides with the lower bound up to multiplicative constants. Thus, it is an order-optimal $\epsilon$-DP-FC-BAI algorithm in this regime, whereas the looseness in the low-privacy regime is as same as the looseness of the non-private Top Two algorithm. In Section <ref>, we experimentally show that  is more sample efficient than the existing $\epsilon$-DP-FC-BAI algorithm, i.e. DP-SE [46]. We also show that its sample complexity is independent of the privacy budget in the low-privacy regime, as already indicated by the lower bound.

3. Technical tools: (a) To derive the lower bound, we provide an $\epsilon$-global DP version of the transportation lemma [32] (Lemma <ref>), which we prove using a sequential coupling argument. We also define and study the TV characteristic time ($T^{\star}_{\text{TV}}$) quantifying the hardness of FC-BAI in high privacy regimes (Proposition <ref>). (b) To design the algorithm, we propose a generic wrapper, which adapts the existing FC-BAI algorithm to tackle DP-FC-BAI. It builds on two components: (i) Adaptive episodes with per-arm doubling and forgetting, (ii) A private GLR stopping rule obtained by plugging in private empirical means in the non-private GLR stopping rule used of FC-BAI with Gaussian distributions. To use this proposed wrapper, one can choose among the numerous existing sampling rules to tackle FC-BAI. In this work, we consider the Top Two algorithms since they have good theoretical guarantees and empirical performance. To provide the sample complexity upper bound, we study step-by-step the effects of doubling, forgetting, and adding noise on the performance of the algorithm. Building on [27], we provide a generic analysis of the class of Top Two algorithms when combined with our wrapper.

§.§ Related works

Lower bound. Efficient algorithm design in BAI literature is propelled by the derivation of lower bounds on sample complexity. [31] derive the first lower bounds for classical fixed-confidence BAI setting without privacy, which is further improved in [21] by introducing KL characteristic time $T^{\star}_{\text{KL}}$ (Corollary <ref>). Motivated by this, we prove the first-known lower bound on sample complexity for FC-BAI with $\epsilon$-global DP (Theorem <ref>). The proof employs a similar sequential coupling argument as in the regret lower bound for bandits with $\epsilon$-global DP [48, 5]. This similarity is also reflected in the existence of two privacy regimes depending on the privacy budget $\epsilon$. And for both lower bounds,
the Total Variation (TV) appears to be the information-theoretic measure that captures the hardness in the high privacy regime. Specifically, the TV characteristic time ($T^{\star}_{\text{TV}}$, Corollary <ref>) serves as the BAI counterpart to the TV-distinguishability gap ($t_{\inf}$) in the problem-dependent regret lower bound for bandits with $\epsilon$-global DP as in <cit.>.

Algorithms for BAI with fixed confidence (FC-BAI).
The optimal sample complexity for the non-private FC-BAI problem (i.e., $T^{\star}_{\text{KL}}$) is well-understood [21], and algorithms are proposed with the aim to achieve this lower bound.
Early approaches involved Successive Elimination (SE) based algorithms [19] with uniform sampling to find the optimal arm.
Inspired by the success of Upper Confidence Bound (UCB) algorithms in the regret setting, the Lower Upper Confidence Bound (LUCB) algorithm was proposed [20].
However, neither SE nor LUCB algorithms achieve asymptotic optimality.
The Track-and-Stop (TnS) algorithm introduced in [21] was the first to asymptotically achieve the exact optimal sample complexity $T^{\star}_{\text{KL}}$.
TnS attains asymptotic optimality by solving a plug-in estimate of the lower bound optimization problem at each step.
The game-based approach presented in [13] relaxes this requirement by casting the optimization problem as an unknown game and proposing sampling rules based on iterative strategies to estimate and converge to its saddle point.
Finally, the Top Two algorithms arose as an identification strategy based on the praised Thompson Sampling algorithm for regret minimization [45].
In recent years, numerous variants have been analyzed and shown to be asymptotically near optimal [27].
At every step, a Top Two sampling rule selects the next arm to sample from among two candidate arms, a leader and a challenger.
In addition to their great empirical performance, and easy implementation compared to TnS and Game-based algorithms, the Top Two algorithms achieve near asymptotic optimality.
In Sec. <ref>, we derive an $\epsilon$-global DP version of a Top Two algorithm: .

$\epsilon$-DP BAI algorithms. DP-SE [46] is an $\epsilon$-global DP version of the Successive Elimination algorithm. Although the algorithm was proposed and analysed for the regret minimisation setting in [46], it is possible to derive a sample complexity from the analysis in [46]. We compare in-depth DP-SE and , both theoretically (Section <ref>) and experimentally (Section <ref>). In both aspects, our proposed algorithm  outperforms DP-SE. Another adaptation of DP-SE, namely DP-SEQ, is proposed in [29] for the problem of privately finding the arm with the highest quantile at a fixed level. But this is a different setting of interest than the present paper.
[44] also studies privacy for BAI under fixed confidence but with multiple agents.
They propose and analyse the sample complexity of DP-MASE, a multi-agent version of DP-SE.
They show that multi-agent collaboration leads to better sample complexity than independent agents, even under privacy constraints.
While the multi-agent setting with federated learning allows tackling large-scale clinical trials taking place at several locations simultaneously, we study the single-agent setting, which is relevant for many small-scale clinical trials (see Example <ref>).

§ DIFFERENTIAL PRIVACY AND BEST ARM IDENTIFICATION

Background: Differential Privacy (DP). DP ensures protection of an individual's sensitive information when her data is used for analysis. A randomised algorithm satisfies DP if the output of the algorithm stays almost the same, regardless of whether any single individual's data is included in or excluded from the input. This is achieved by adding controlled noise to the algorithm's output.

A randomised algorithm $\alg$ satisfies $(\epsilon, \delta)$-Differential Privacy (DP) if for any two neighbouring datasets $\mathcal D$ and $\mathcal D'$ that differ only in one entry, i.e. $\dham(\mathcal D, \mathcal D') = 1$, and for all sets of output $\mathcal{O} \subseteq \mathrm{Range}(\alg)$,

\begin{equation}\label{eq:dp}
\operatorname{Pr}[\alg(\mathcal D) \in \mathcal{O}] \leq e^{\epsilon} \operatorname{Pr}\left[\alg\left(\mathcal D'\right) \in \mathcal{O}\right] + \delta,
\end{equation}

where the probability space is over the coin flips of the mechanism $\alg$, and for some $(\epsilon, \delta)\in \real^{\geq0} \times \real^{\geq0}$. If $\delta = 0$, we say that $\alg$ satisfies $\epsilon$-DP. A lower privacy budget $\epsilon$ implies higher privacy.

The Laplace mechanism [16, 18] ensures $\epsilon$-DP by injecting controlled random noise into the output of the algorithm, which is sampled from a calibrated Laplace distribution (as specified in Theorem <ref>). We use $Lap(b)$ to denote the Laplace distribution with mean 0 and variance $2b^2$.

Let us consider an algorithm $f: \mathcal{X} \rightarrow \real^d$ with sensitivity $s(f) \defn \underset{\substack{\mathcal{D}, \mathcal{D'} \text{ s.t }|\mathcal{D} - \mathcal{D'}|_{\mathrm{Hamming}} = 1}}{\max} | f(\mathcal{D}) - f(\mathcal{D'})|{1}$. Here, $\onenorm{\cdot}$ is the $L_1$ norm on $\real^d$. If $d$ noise samples $\setof{N_i}_{i=1}^d$ are generated independently from $Lap\left(\frac{s(f)}{\epsilon}\right)$, then the output injected with the noise, i.e. $f(\mathcal{D}) + [N_1, \ldots, N_d]$, satisfies $\epsilon$-DP.

Background: BAI with fixed confidence.
Now, we describe the canonical best-arm identification problem with fixed confidence (FC-BAI). BAI is a variant of pure exploration, where the goal is to identify the optimal arm. In FC-BAI, the learner is provided with a confidence level $1-\delta \in (0,1)$ [We remind not to confuse risk level $\delta$ with the $\delta$ of $(\epsilon, \delta)$-DP. Hereafter, we consider $\epsilon$-global DP as the privacy definition, and $\delta$ always represents the risk (or probability of mistake) of the BAI strategy.]. Learner aims to recommend an arm that is optimal with probability at least $1 - \delta$, while using as few samples as possible. To achieve this, the learner defines a FC-BAI strategy to interact with the bandit instance $ \boldsymbol{\nu} = \{\nu_a: a \in [\arms] \} $. We denote the action played at step $t$ by $a_t$, and the corresponding observed reward by $r_t \sim \nu_{a_t}$. $\mathcal{H}_t=\left(a_1, r_1, \ldots, a_t, r_t\right)$ is the history of actions played and rewards collected until time $t$. We augment the action set by a stopping action $\top$, and write $a_t=\top$ to denote that the algorithm has stopped before step $t$. A FC-BAI strategy $\pi$ is composed of

i. A pair of sampling and stopping rules $\left(\mathrm{S}_t: \mathcal{H}_{t-1} \rightarrow \mathcal{P}([|1, K|] \cup\{\top\})\right)_{t \geq 1}$. For an action $a \in$ $[K],$ $ \mathrm{S}_t\left(a \mid \mathcal{H}_{t-1}\right)$ denotes the probability of playing action $a$ given history $\mathcal{H}_{t-1}$. On the other hand, $\mathrm{S}_t\left(\top \mid \mathcal{H}_{t-1}\right)$ is the probability of the algorithm halting given $\mathcal{H}_{t-1}$. For any history $\mathcal{H}_{t-1}$, a consistent sampling and stopping rule $\mathrm{S}_t$ satisfies $\mathrm{S}_t\left(\top \mid \mathcal{H}_{t-1}\right)=1$ if $\top$ has been played before $t$.

ii. A recommendation rule $\left(\operatorname{Rec}_t: \mathcal{H}_{t-1} \rightarrow \mathcal{P}([|1, K|])\right)_{t>1}$. A recommendation rule dictates $\operatorname{Rec}_t\left(a \mid \mathcal{H}_{t-1}\right)$, i.e. the probability of returning action $a$ as a guess for the best action given $\mathcal{H}_{t-1}$.

We denote by $\tau$ the stopping time of the algorithm, i.e. the first step $t$ demonstrating $a_t = \top$.
A BAI strategy $\pi$ is called $\delta$-correct for a class of bandit instances $\mathcal{M}$, if for every instance $\boldsymbol{\nu} \in \mathcal{M}$, $\pi$ recommends the optimal action $a^\star (\boldsymbol{\nu}) = \argmax_{a \in [\arms]} \mu_a$ with probability at least $1-\delta$, i.e. $\mathbb{P}_{\boldsymbol{\nu}, \pi} ( \tau < \infty, \widehat{a} = a^\star(\boldsymbol{\nu}) ) \geq 1 - \delta$.

FC-BAI with $\epsilon$-global DP ($\epsilon$-DP-FC-BAI). Now, we formally define $\epsilon$-global DP for FC-BAI, where the BAI strategy (a.k.a. the centralised decision maker) is trusted with all the intermediate rewards. We represent each user $u_t$ by the vector $\textbf{x}_t \defn (x_{t, 1}, \dots, x_{t, \arms}) \in \real^\arms$, where $x_{t, a}$ represents the potential reward observed, if action $a$ was recommended to user $u_t$. Due to the bandit feedback, only $r_t = x_{t, a_t} \sim \nu_{a_t}$ is observed at step $t$. We use an underline to denote any sequence. Thus, we denote the sequence of sampled actions until $\horizon$ as $\underline{a}^\horizon = (a_1, \dots, a_\horizon)$. We further represent a set of users $\lbrace u_t\rbrace_{t=1}^{\horizon}$ until $\horizon$ by the table of potential rewards $ \underline{\textbf{d}}^\textbf{\horizon} \defn \lbrace \textbf{x}_1, \dots, \textbf{x}_\horizon\rbrace \in (\real^\arms)^\horizon$.
First, we observe that $\underline{\textbf{d}}^\horizon$ is the sensitive input generated through interaction with the users, and $(\underline{a}^\horizon, \widehat{a}, \horizon)$ is the output of the BAI strategy. Hence, we define the probability that the BAI strategy $\pi$ samples the action sequence $\underline{a}^\horizon$, recommends the action $\widehat{a}$, and halts at time $\horizon$, as

\begin{equation}\label{eq:prob_event}
\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}}^\horizon) \defn \operatorname{Rec}_{T+1}\left(\widehat{a} \mid \mathcal{H}_{\horizon}\right) \mathrm{S}_{T+1}\left(\top \mid \mathcal{H}_{\horizon} \right) \prod_{t=1}^T \mathrm{~S}_t\left(a_t \mid \mathcal{H}_{t - 1}\right)
\end{equation}

where $\horizon$ users under interaction are represented by the table of potential rewards $\underline{\textbf{d}}^\horizon$

Thus, a BAI strategy satisfies $\epsilon$-global DP if the probability defined in Eq. (<ref>) is similar when the BAI strategy interacts with two neighbouring tables of rewards differing by a user (i.e. a row in $\underline{\textbf{d}}^\horizon$).

Sequential interaction between a BAI strategy and users

[1]
Input: A BAI strategy $\pi = (S_t, \operatorname{Rec}_t)_{t \geq 1}$ and Users $\{u_t\}_{t \geq 1}$ represented by the table $\underline{\textbf{d}}$
Output: A stopping time $\tau$, a sequence of samples actions $\underline{a}^\tau = (a_1, \dots, a_\tau)$ and a recommendation $\hat{a}$ satisfying $\epsilon$-global DP
$t = 1, \dots$
$\pi$ recommends action $a_t \sim S_t(. \mid a_1, r_1, \dots, a_{t - 1}, r_{t - 1})$
$a_t = \top$
Halt. Return $\tau = t$ and $ \hat{a} \sim \operatorname{Rec}_t(. \mid a_1, r_1, \dots, a_{t - 1}, r_{t - 1})$
$u_t$ sends the sensitive reward $r_t \defn \underline{\textbf{d}}_{t, a_t}$ to $\pi$

A BAI strategy satisfies $\epsilon$-global DP, if for all $\horizon \geq 1$, all neighbouring table of rewards $\underline{\textbf{d}}^\horizon$ and $\underline{\textbf{d}'}^\horizon$, i.e. $\dham(\underline{\textbf{d}}^\horizon, \underline{\textbf{d}'}^\horizon) = 1$, all sequences of sampled actions $\underline{a}^\horizon \in [\arms]^\horizon$ and recommended actions $\widehat{a} \in [\arms]$ we have that

\begin{equation*}
\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}}^\horizon)  \leq e^\epsilon \pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}'}^\horizon).
\end{equation*}

Definition <ref> can be seen as a BAI counterpart of the $\epsilon$-global DP definition proposed in [5] for regret minimization. We demonstrate the BAI strategy-Users interaction in Algorithm <ref>.

It is possible to consider that the output of a BAI strategy is only the final recommended action $\hat{a}$, i.e. not publishing the intermediate actions $\underline{a}^\horizon$. This gives a weaker definition of privacy compared to Definition <ref>, since the latter defends against adversaries that may look inside the execution of the BAI strategy, i.e. pan-privacy [17]. In addition, Definition <ref> is needed in practice. For example, in the case of dose-finding (Example <ref>), the experimental protocol, i.e. the intermediate actions, needs to be published too.

The goal in $\epsilon$-DP-FC-BAI is to design a $\delta$-correct $\epsilon$-global DP algorithm, with $\tau$ as small as possible.

§ LOWER BOUND ON SAMPLE COMPLEXITY FOR FC-BAI WITH $\EPSILON$-GLOBAL DP

The central question that we address in this section is

How many additional samples a BAI strategy must select for ensuring $\epsilon$-global DP?

In response, we prove a lower bound on the sample complexity of any $\delta$-correct $\epsilon$-DP BAI strategy.
Our lower bound features problem-dependent characteristic times reminiscent of the FC-BAI setting.

Let $\boldsymbol{\nu} \triangleq \{\nu_a : a \in [\arms]\}$ be a bandit instance, consisting of $\arms$ arms with finite means $\{\mu_a\}_{a \in [\arms]}$. Now, we define the set of alternative instances as $\operatorname{Alt}(\boldsymbol{\nu})\triangleq \left\{\boldsymbol{\lambda}: a^{\star}(\boldsymbol{\lambda}) \neq a^{\star}(\boldsymbol{\nu})\right\}$, i.e. the bandit instances with a different optimal arm than $\boldsymbol{\nu}$. For two probability distributions $\mathbb{P}, \mathbb{Q}$ on the same measurable space $(\Omega, \mathcal{F})$, the Total Variation (TV) distance is defined as $ \TV{\mathbb{P}}{\mathbb{Q}} \triangleq \sup_{A \in \mathcal{F}} \{\mathbb{P}(A) - \mathbb{Q}(A)\}\textbf{}$, while the KL divergence (or relative entropy) is $\KL{\mathbb{P}}{\mathbb{Q}} \triangleq \int \log\left(\frac{\dd\mathbb{P}}{\dd\mathbb{Q}} (\omega) \right) \dd \mathbb{P} (\omega)$, when $\mathbb{P} \ll \mathbb{Q}$, and $\infty$ otherwise. We denote the probability simplex by $\Sigma_K \triangleq \{ \omega \in [0,1]^\arms: \sum_{a=1}^\arms \omega_a = 1 \} $.

First, we derive an $\epsilon$-global DP variant of the ‘transportation’ lemma, i.e. Lemma 1 in [31].

Let $\delta \in (0,1) $ and $\epsilon>0$. Let $\boldsymbol{\nu}$ be a bandit instance and $\lambda \in \operatorname{Alt}(\boldsymbol{\nu})$. For any $\delta$-correct $\epsilon$-global DP BAI strategy, we have that

\begin{equation*}
6 \epsilon  \sum_{a = 1}^\arms \expect_{\boldsymbol{\nu}, \pi} \left [N_a(\tau) \right] \TV{\nu_{a}}{\lambda_{a}}  \geq \mathrm{kl}(1-\delta, \delta),
\end{equation*}

where $\mathrm{kl}(1-\delta, \delta) \defn x \log\frac{x}{y} + (1 - x) \log \frac{1 - x}{1 - y} \;$ for $x,y \in (0,1)$.

Proof sketch. We use Sequential Karwa-Vadhan Lemma <cit.> with a data-processing inequality in the BAI canonical model. Extra care is needed to deal with the stopping times in the coupling, compared to a fixed horizon $T$ in regret minimization. The proof is deferred to Appendix <ref>.

Leveraging Lemma <ref>, we derive a sample complexity lower bound for any $\epsilon$-DP-FC-BAI strategy.

Let $\delta \in (0,1) $ and $\epsilon>0$. For any $\delta$-correct $\epsilon$-global DP BAI strategy, we have that

\begin{align}\label{eq:lower_bound}
\mathbb{E}_{\boldsymbol{\nu}}[\tau] &\geq T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \log (1 / 3 \delta),%\\
%\text{where}~\left (T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \right ) ^{-1 } &\defn \sup _{\omega \in \Sigma_K} \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})} \min  \left(\sum_{a=1}^K \omega_a \KL{\nu_a}{\lambda_a}, 6 \epsilon \sum_{a=1}^K \omega_a  \TV{\nu_a}{\lambda_a} \right).\notag
\end{align}

where $\left (T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \right )^{-1 } \defn \sup\limits_{\omega \in \Sigma_K} \inf\limits_{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})} \min  \left(\sum_{a=1}^K \omega_a \KL{\nu_a}{\lambda_a}, 6 \epsilon \sum_{a=1}^K \omega_a  \TV{\nu_a}{\lambda_a} \right)$.

Comments on the lower bound. Similar to the lower bound for the non-private BAI [21], the lower bound of Theorem 2 is the value of a two-player zero-sum game between a MIN player and MAX player. MIN plays an alternative instance $\lambda$ close to $\nu$ in order to confuse MAX. The latter plays an allocation $\omega \in \Sigma_K$ to explore the different arms, with the purpose of maximising the divergence between $\nu$ and the confusing instance $\lambda$ that MIN played. On top of the KL divergence present in the non-private lower bound, our bound features the TV distance that appears naturally when incorporating the $\epsilon$-global DP constraint. The proof is deferred to Appendix <ref>. In order to compare the lower bound of an $\epsilon$-global BAI strategy with the non-private lower bound of [21], we relax Theorem <ref> to further derive a simpler bound, as in Corollary <ref>.

For any $\delta$-correct $\epsilon$-global DP BAI strategy, we have that

\begin{gathered}
\mathbb{E}_{\boldsymbol{\nu}}[\tau] \geq \max\left( T^{\star}_{\mathrm{KL}}(\boldsymbol{\nu}) , \frac{1}{6 \epsilon}  T^{\star}_{\mathrm{TV}}(\boldsymbol{\nu})\right) \log (1 / 3 \delta),% \quad \text { where } \\
%\left(T^{\star}_{\textbf{d}}(\boldsymbol{\nu}) \right)^{-1} \defn \sup _{\omega \in \Sigma_K} \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})}  \sum_{a=1}^K \omega_a \textbf{d}(\nu_a, \lambda_a)
\end{gathered}

where $\left(T^{\star}_{\textbf{d}}(\boldsymbol{\nu}) \right)^{-1} \defn \sup _{\omega \in \Sigma_K} \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})}  \sum_{a=1}^K \omega_a \textbf{d}(\nu_a, \lambda_a)$, and $\textbf{d}$ is either $\mathrm{KL}$ or $\mathrm{TV}$.

The proof is direct by observing that $T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \geq T^{\star}_{\text{KL}}(\boldsymbol{\nu})$ and $ T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \geq \frac{1}{6 \epsilon} T^{\star}_{\mathrm{TV}}(\boldsymbol{\nu})$.

Comparison with the non-private lower bound.
$T^{\star}_{\text{KL}}$ is the characteristic time in the non-private lower bound [21], and we refer to Section 2.2 of [21] for a detailed discussion on its properties.
The sample complexity lower bound suggests the existence of two hardness regimes depending on $\epsilon$, $T^{\star}_{\text{KL}}$ and $T^{\star}_{\mathrm{TV}}$. (1) Low-privacy regime: When $\epsilon > T^{\star}_{\mathrm{TV}(\boldsymbol{\nu})}/(6 T^{\star}_{\text{KL}}(\boldsymbol{\nu}))$, the lower bound retrieves the non-private lower bound, i.e. $T^{\star}_{\text{KL}}(\boldsymbol{\nu})$, and thus, privacy can be achieved for free.
(2) High-privacy regime: When $\epsilon < T^{\star}_{\mathrm{TV}}(\boldsymbol{\nu})/(6 T^{\star}_{\text{KL}}(\boldsymbol{\nu}))$, the lower bound becomes $ T^{\star}_{\mathrm{TV}} / (6 \epsilon)$ and $\epsilon$-global DP $\delta$-BAI requires more samples than non-private ones.

In the following proposition, we characterise $T^{\star}_{\mathrm{TV}}$ for Bernoulli instances.

Let $\nu$ be a bandit instance, i.e. such that $\nu_a = \text{Bernoulli}(\mu_a)$ and $\mu_1 > \mu_2 \geq \dots \geq \mu_\arms$. Let $\Delta_a \defn \mu_1 - \mu_a$ and $\Delta_\text{min} \defn \min_{a \neq 1} \Delta_a $. We have that

\begin{align*}
T^{\star}_{\mathrm{TV}}(\boldsymbol{\nu}) = \frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a}, &&\text{and}  &&\frac{1}{\Delta_{\text{min}}} \leq T^{\star}_{\mathrm{TV}}(\boldsymbol{\nu}) \leq  \frac{\arms}{\Delta_{\text{min}}}.
\end{align*}

Proof sketch.
The proof is direct by solving the optimisation problem defining $T^{\star}_{\mathrm{TV}}$ and using that $\TV{\text{Bernoulli}(p)}{\text{Bernoulli}(q)} = | p - q|$. We refer to Appendix <ref> for details.

Comment. The aforementioned bound on TV characteristic time for Bernoulli instances is $\epsilon$-global DP parallel of the KL-characteristic time bound $T^\star_{\text{KL}}(\boldsymbol{\nu}) \leq \sum_{a=1}^\arms \Delta_a^{-2} $  [21].
Using Pinsker's inequality, one can connect the TV and KL characteristic times by $T^\star_{\text{TV}}(\boldsymbol{\nu}) \ge \sqrt{2T^\star_{\text{KL}}(\boldsymbol{\nu})}$.

§ ALGORITHM DESIGN: PRIVATE TOP TWO WITH ADAPTIVE EPISODES ()

In this section, we propose , an $\epsilon$-global DP version of the TTUCB algorithm [26]. We show that  satisfies $\epsilon$-global DP, is $\delta$-correct, and has an asymptotic sample complexity that matches the high privacy lower bounds up to multiplicative constants.

TTUCB belongs to the family of Top Two algorithms [45, 47, 27], which selects at each time two arms called leader and challenger, and sample among them.
After initialisation, TTUCB uses a UCB-based leader and a Transportation Cost (TC) challenger, expressed by

\[
B_{n} = \argmax_{a \in [K]} \{\hat \mu_{n,a} + \sqrt{6 \log (n) /N_{n,a}}  \}, \quad \text{and} \quad C_{n} =  \argmin_{a \ne B_{n}} \frac{\hat \mu_{n,B_{n}} - \hat \mu_{n,a}}{\sqrt{1/N_{n, B_n}+ 1/N_{n,a}}} \: .
\]

Here, $(\hat \mu_{n},N_{n})$ are the empirical means and counts on the whole history.
The theoretical motivation behind the TC challenger comes from the theoretical lower bound in FC-BAI, which involves the KL-characteristic time $T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu}) = \min_{\beta \in (0,1)} T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})$.
For Gaussian distributions, we have

\begin{align*}\label{eq:kl_beta}
2T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})^{-1} = \max_{\omega \in \Sigma_K, \omega_{a^\star} = \beta} \frac{(\mu_{a^\star} - \mu_{a})^2}{1/\beta + 1/\omega_{a}} \quad \text{and} \quad T^{\star}_{\mathrm{KL},1/2}(\boldsymbol{\mu}) \le 2 T^{\star}_{\mathrm{KL}}(\boldsymbol{\mu}) \: ,
\end{align*}

The maximiser of the above equation is denoted by $\omega^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})$, and is further referred to as the $\beta$-optimal allocation as it is unique.
Let $N_{n,b}^{a}$ denote the number of times arm $b$ was pulled when $a$ was the leader, and $L_{n,a}$ denotes the number of times arm $a$ was the leader.
In order to select the next arm to sample $I_n$, TTUCB relies on $K$ tracking procedures, i.e. set $I_n = B_n$ if $N_{n,B_n}^{B_n} \le  \beta L_{n+1,B_n}$, else $I_n = C_n$.
This ensures that $\max_{a \in [K], n>K}|N_{n,a}^{a} - \beta L_{n,a}| \le 1$.
Standing on this premise, we now describe how we design an $\epsilon$-global DP extension of TTUCB.

Private algorithm design.
As illustrated in Algorithm <ref>,  relies on three ingredients: adaptive episodes with doubling, forgetting, and adding calibrated Laplacian noise.
(1)  maintains $K$ episodes, i.e. one per arm.
The private empirical estimate of the mean of an arm is only updated at the end of an episode, that means when the number of times that a particular arm was played doubles (Line 5).
(2) For each arm $a$,  forgets rewards from previous phases of arm $a$, i.e. the private empirical estimate of arm $a$ is only computed using the rewards collected in the last phase of arm $a$ (Line 8).
This assures that the means of each arm are estimated using a non-overlapping sequence of rewards.
(3) Thanks to this doubling and forgetting,  is $\epsilon$-global DP as soon as each empirical mean (Line 9) is made $\epsilon$-DP, and thus, avoiding any use of privacy composition.
This is achieved by adding Laplace noise.
We formalise this intuition in Lemma <ref> of Appendix <ref>.

The aforementioned generic wrapper can be used to construct a near-optimal differentially private version of any existing FC-BAI algorithm that deploys a sampling rule with the empirical means of rewards. In this work, we consider and rigorously analyse the Top Two algorithms since they demonstrate both good theoretical guarantees and empirical performance.

For rewards in $[0,1]$,  satisfies $\epsilon$-global DP.

Proof sketch.
A change in one user only affects the empirical mean calculated at one episode of an arm, which is made private using the Laplace Mechanism and Lemma <ref>.
Since the sampled actions, recommended action, and stopping time are computed only using the private empirical means,  satisfies $\epsilon$-global DP thanks to post-processing lemma.
We refer to Appendix <ref> for details.

Private GLR stopping rule.
We consider the private GLR stopping rule based on the private means and on the pulling counts from the last phase (Line 12), and recommend the arm with the highest private mean (Line 11).
Lemma <ref> yields a threshold function ensuring that any sampling rule is $\delta$-correct, when using the private GLR stopping rule.

Let $\delta \in (0,1)$, $\epsilon > 0$.
Let $s > 1$ and $\zeta$ be the Riemann $\zeta$ function.
Let $ c_{k}(n, m,\delta) = 2 \cC_{G} ( \log((K-1)\zeta (s)k^s/\delta )/2) + 2 \log(4 + \log n ) + 2 \log(4 + \log m)$ be the threshold without privacy.
Given any sampling rule, the following threshold

\begin{equation} \label{eq:private_threshold}
c_{\epsilon, k_{1}, k_{2}}(n, m,\delta) = 2 c_{k_{1}k_{2}}(n, m,\delta/2) + \frac{1}{n \epsilon^2} \log \left(\frac{2 K k_{1}^{s} \zeta(s)}{\delta} \right)^2 + \frac{1}{m \epsilon^2} \log \left(\frac{2 K k_{2}^{s} \zeta(s)}{\delta} \right)^2
\end{equation}

with the GLR stopping rule yields a $\delta$-correct algorithm for sub-Gaussian distributions.
The function $\cC_{G}$ is defined in (<ref>).
It satisfies $\cC_{G}(x) \approx x + \ln(x)$.

Remark. We observe that approximately $c_{\epsilon, k_{1}, k_{2}}(n, m,\delta) \approx 2\log (1/\delta) + ( 1/n + 1/m ) \log (1/\delta)^2/\epsilon^2$.

Proof sketch. Proving $\delta$-correctness of a GLR stopping rule is done by leveraging concentration results. Specifically, we start by decomposing the failure probability $\bP_{\mu}\left( \tau_{\delta} < + \infty, \hat a \neq  a^\star \right)$ into a non-private and a private part using the basic property of $\bP(X + Y  \ge a+b) \le \bP(X \ge a) + \bP(Y \ge b)$.
The two-factor in front of $c_{k_{1}k_{2}}$ originates from the looseness of this decomposition.
To remove it, we would need a tighter stopping threshold that jointly controls both the non-private and the private parts.
We conclude using concentration results from sub-Gaussian random variables for the non-private part, and Laplace random variables for the private part.

. Private statistics are in red. Changes due to privacy are in blue.

[1]
Input: $\beta \in (0,1)$, risk $\delta \in (0,1)$, privacy budget $\textcolor{blue}{\epsilon}$, thresholds $\textcolor{blue}{c_{\epsilon,k_1, k_2}}  : \N^2 \times (0,1) \to \R^+$
Output: Recommendation $\hat{a}$ and Stopping time $\tau$ satisfying $\epsilon$-global DP
Initialization: $\forall a \in [K]$, pull arm $a$, set $k_{a}=1$, $T_{1}(a) = \arms+1$, $L_{n,a} = 0$, $N_{n, a} = 1$, $n = K+1$.
$n > K$
there exists $a \in [K]$ such that $N_{n,a} \ge 2 N_{T_{k_{a}}(a),a}$ Per-arm doubling
Change phase $k_{a} \gets k_{a} + 1$ for this arm $a$
Set $T_{k_{a}}(a) = n$ and $\tilde N_{k_{a}, a} =  N_{T_{k_{a}}(a), a} - N_{T_{k_{a} - 1}(a), a}$ Pulls of $a$ in its last phase
Set $\hat \mu_{k_{a},a} = \tilde N_{k_{a},a}^{-1} \sum_{s = T_{k_{a}-1}(a)}^{T_{k_{a}}(a) - 1} X_{s} \ind{I_s = a}$ Empirical mean of $a$ in its last phase
Set $\privmean{k_{a}}{a} =  \hat \mu_{k_{a},a} +  \textcolor{blue}{Y_{k_{a},a}}$ where $Y_{k_{a},a} \sim \text{Lap}((\epsilon\tilde N_{k_{a},a} )^{-1} )$ Make it private
Set $\hat a_{n} = \argmax_{b \in [K]} \privmean{k_{b}}{b}$ Arm with highest private mean
$\frac{(\privmean{k_{\hat a_{n}}}{\hat a_{n}}  - \privmean{k_{b}}{b})^2}{1/\tilde N_{k_{\hat a_{n}},\hat a_{n}}+ 1/\tilde N_{k_{b},b}} \ge 2\textcolor{blue}{c_{\epsilon, k_{\hat a_{n}},k_{b}}}(\tilde N_{k_{\hat a_{n}}, \hat a_{n}}, \tilde N_{k_{b},b},\delta)$ for all $b \ne \hat a_{n}$
return ($\hat a_{n}$, $n$) If GLR stopping condition is met, recommend the empirical best arm
Set $B_n = \argmax_{a \in [K]} \{\privmean{k_{a}}{a} + \sqrt{k_{a}/\tilde N_{k_{a},a}} + k_{a}/(\epsilon \tilde N_{k_{a},a}) \}$ Private UCB leader
Set $C_n = \argmin_{a \ne B_n} \frac{\privmean{k_{B_n}}{B_n} - \privmean{k_{a}}{a} }{\sqrt{1/N_{n, B_n}+ 1/N_{n,a}}}$ Private TC challenger

Set $I_n = B_n$ if $N_{n,B_n}^{B_n} \le  \beta L_{n+1,B_n}$, else $I_n = C_n$ Tracking
Pull $I_n$ and observe $X_{n} \sim \nu_{I_n}$
Set $N_{n+1, I_n} \gets N_{n, I_n} + 1$, $N^{B_n}_{n+1, I_n} \gets N^{B_n}_{n, I_n} + 1$ and $L_{n+1, B_n} \gets L_{n, B_n} + 1$. Set $n \gets n + 1 $

Let $(\delta, \beta) \in (0,1)^2$ and $\epsilon > 0$.
Combined with the private GLR stopping rule using threshold as in (<ref>),  is $\delta$-correct and satisfies that, for all $\mu \in \R^{K}$ such that $\min_{a \ne b}|\mu_{a} - \mu_{b}| > 0$,

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

Proof sketch.
We adapt the asymptotic proof of the TTUCB algorithm, which is based on the unified analysis of Top Two algorithms from [27].
Below, we present high-level ideas of the proof and specify the effect of different elements of  on the expected sample complexity.

Consequences of Theorem 5. (1) The non-private TTUCB algorithm [26] achieves a sample complexity of $T_{\mathrm{KL},\beta}^\star(\boldsymbol{\mu})$ for sub-Gaussian random variables.
The proof relies on showing that the empirical pulling counts are converging towards the $\beta$-optimal allocation $\omega^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})$.
(2) The effect of doubling and forgetting is a multiplicative four-factor, i.e. $4 T_{\mathrm{KL},\beta}^\star(\boldsymbol{\mu})$.
The first two-factor is due to forgetting since we throw away half of the samples.
The second two-factor is due to doubling since we have to wait for the end of an episode to evaluate the stopping condition.
(3) The Laplace noise only affects the empirical estimate of the mean.
Since the Laplace noise has no bias and a sub-exponential tail, the private means will still converge towards their true values.
Therefore, the empirical counts of  will also converge to $\omega^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})$ asymptotically.
(4) While the Laplace noise has little effect on the sampling rule itself, it changes drastically the dependency in $\log(1/\delta)$ of the threshold used in the GLR stopping rule.
The private threshold $c_{\epsilon, k_1, k_2}$ has an extra factor $\bigO(\log^2( 1/\delta ))$ compared to the non-private one $c_{k}$.
Using the convergence towards $\omega^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})$, the stopping condition is met as soon as $\frac{n}{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})} \lesssim 2\log ( 1/\delta ) + \frac{{\Delta}^2_{\max}}{2\epsilon^2} \frac{T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})}{n} \log^2( 1/\delta )$.
Solving the inequality for $n$ concludes the proof while adding a multiplicative four-factor.

For $\beta = 1/2$, it is well known that $T^\star_{\mathrm{KL},1/2}(\boldsymbol{\mu} ) \leq 2 T^\star_{\mathrm{KL}}(\boldsymbol{\mu}) \leq 8\sum_{a \ne a^\star} \Delta_a^{-2}$.
We consider Bernoulli instances ($0 < \Delta_{\min} \le \Delta_{\max} < 1$), where the gaps have the same order of magnitude, i.e. Condition 1: there exists a constant $C \ge 1$ such that $\Delta_{\max}/\Delta_{\min} \leq C$. For such instances, there exists a universal constant $c$, such that

\[
\limsup_{\delta \to 0} \frac{\bE_{\boldsymbol{\mu}}[\tau_{\delta}]}{\log(1/\delta)} \le~ c~ \max  \Big\lbrace T^\star_{\mathrm{KL},1/2}(\boldsymbol{\mu} ), C \epsilon^{-1}  \sum\nolimits_{a \neq a^\star } \Delta_{a}^{-1}   \Big\rbrace \: .
\]

Without privacy, i.e. $\epsilon \to + \infty$,  yields a multiplicative eight-factor.
On top of the four-factor due to doubling and forgetting, another multiplicative two comes from $2c_{k_{1}k_{2}}$ in Equation (<ref>).

Comparison to the lower bound.
For Bernoulli bandits verifying Condition 1, the upper bound of Theorem <ref> matches the $T^\star_{\text{TV}}(\boldsymbol{\mu})/\epsilon$ lower bound of Corollary <ref> up to constants in the high-privacy regime, i.e. when $\epsilon \preceq T^\star_{\text{TV}}(\boldsymbol{\mu})/T^\star_{\text{KL}}(\boldsymbol{\mu})$.
In the low-privacy regime, the upper bound reduces to $T^\star_{\mathrm{KL},1/2}(\boldsymbol{\mu})$.

In Appendix <ref>, we discuss in-depth why this difference is necessary for private BAI algorithms based on the GLR stopping rule, which poses an interesting open problem.

Comparison to DP-SE. DP-SE is a private version of the successive-elimination algorithm studied in [46] for the regret minimisation setting.
The algorithm samples active arms uniformly during phases of geometrically increasing length.
Based on the private confidence bounds, DP-SE eliminates provably sub-optimal arms at the end of each phase.
Due to its phased-elimination structure, DP-SE can be easily converted into an $\epsilon$-DP-FC-BAI algorithm, where we stop once there is only one active arm left.
In particular, the proof of Theorem 4.3 of [46] shows that with high probability any sub-optimal arm $a\neq a^\star$ is sampled no more than $\bigO (\Delta_a^{2} + (\epsilon\Delta_a)^{-1})$.
From this result, it is straightforward to extract a sample complexity upper bound for DP-SE, i.e. $\bigO ( \sum_{a\ne a^\star} \Delta_a^{-2}  +  \sum_{a\ne a^\star} (\epsilon\Delta_a)^{-1}).$ This shows that DP-SE too achieves (ignoring constants) the high-privacy lower bound $T^\star_{\textrm{TV}}(\boldsymbol{\mu})/\epsilon$ for Bernoulli instances.
However, due to its uniform sampling within the phases, DP-SE is less adaptive than .
Inside a phase, DP-SE continues to sample arms that might already be known to be bad, while  adapts its sampling rule based on the transportation costs that reflect the amount of evidence collected in favour of the hypothesis that the leader is the best arm.
Finally,  has the advantage of being anytime, i.e. its sampling strategy does not depend on the risk $\delta$.

§ EXPERIMENTAL ANALYSIS

We perform experiments to show that: (i)  has better empirical performance compared to , and (ii) the transition between high and low-privacy regimes is reflected empirically.

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 Bernoulli instance $\mu_{1}$ (left) and $\mu_{2}$ (right). The shaded vertical line separates the two privacy regimes.  outperforms DP-SE.

Experimental setup. We compare the performances of  and DP-SE for FC-BAI in different Bernoulli instances as in [46].
The first instance has means $\mu_{1} = (0.95, 0.9, 0.9, 0.9, 0.5)$ and the second instance has means $\mu_{2} = (0.75, 0.7, 0.7, 0.7, 0.7)$.
As a benchmark, we also compare to the non-private TTUCB. We set the risk $\delta=10^{-2}$. We implement all the algorithms in Python (version $3.8$) and on an 8-core 64-bits Intel<EMAIL_ADDRESS>GHz CPU.
We run each algorithm $100$ times, and plot corresponding average and standard deviations of stopping times in Figure <ref>.
We also test the algorithms on other Bernoulli instances and report the results in Appendix <ref>.

Result analysis.
a. Efficiency in performance.  requires less samples than DP-SE to provide a $\delta$-correct answer. In the high privacy regime, i.e. small $\epsilon$,  outperforms DP-SE in all the instances tested. In the low privacy regimes, i.e. large $\epsilon$, both algorithms have similar performance that in the worst case is four times the samples required of TTUCB, as shown theoretically.

b. Impact of privacy regimes. As indicated by the theoretical sample complexity lower bounds and upper bounds, the experimental performance of  demonstrates two regimes: a high-privacy regime (for $\epsilon < 0.2$), where the stopping time of  depends on the privacy budget $\epsilon$, and a low privacy regime (for $\epsilon > 0.2$), where the performance of  does not depend on $\epsilon$.

§ CONCLUSION AND FUTURE WORKS

We study FC-BAI with $\epsilon$-global DP. We derive a sample complexity lower bound that quantifies the additional samples needed by a $\delta$-correct BAI strategy in order to ensure $\epsilon$-global DP. The lower bound further suggests the existence of two privacy regimes. In the low-privacy regime, no additional samples are needed, and privacy can be achieved for free. For the high-privacy regime, the lower bound reduces to $\Omega({\epsilon}^{-1} T^\star_{\text{TV}})$, and more samples are required. We also propose , an $\epsilon$-global DP variant of the Top Two algorithms, that runs in adaptive phases and adds Laplace noise.  achieves the high privacy regime lower bound up to multiplicative constants.

The upper bound matches the lower bound by a multiplicative constant in the high privacy regime, and is also loose in some instances in the low privacy regime, due to the mismatch between the KL divergence of Bernoulli distributions and that of Gaussian. It would be an interesting technical challenge to merge this gap. One possible direction to solve this issue is to use transportation costs tailored to Bernoulli for both the Top Two Sampling and the stopping. Another interesting direction would be to extend the proposed technique to other variants of pure DP, namely $(\epsilon, \delta)$-DP and Rényi-DP [40], or other trust models, namely local DP [15] and shuffle DP [12, 22].

This work has been partially supported by the THIA ANR program “AI_PhD@Lille". A. Al-Marjani acknowledges the support of the Chaire SeqALO (ANR-20-CHIA-0020). D. Basu acknowledges the Inria-Kyoto University Associate Team “RELIANT” for supporting the project, and the ANR JCJC for the REPUBLIC project (ANR-22-CE23-0003-01). We thank Emilie Kaufmann and Aurélien Garivier for the interesting conversations. We also thank Philippe Preux for his support.

[1]
Abbasi-Yadkori, Y., Bartlett, P., Gabillon, V., Malek, A., and Valko, M.
Best of both worlds: Stochastic & adversarial best-arm
In Conference on Learning Theory, pages 918–949. PMLR.

[2]
Acharya, J., Sun, Z., and Zhang, H. (2021).
Differentially private assouad, fano, and le cam.
In Algorithmic Learning Theory, pages 48–78. PMLR.

[3]
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).
Finite-time analysis of the multiarmed bandit problem.
Machine learning, 47(2-3):235–256.

[4]
Aziz, M., Kaufmann, E., and Riviere, M.-K. (2021).
On multi-armed bandit designs for dose-finding clinical trials.
The Journal of Machine Learning Research, 22(1):686–723.

[5]
Azize, A. and Basu, D. (2022).
When privacy meets partial information: A refined analysis of
differentially private bandits.
Advances in Neural Information Processing Systems,

[6]
Basu, D., Dimitrakakis, C., and Tossou, A. (2019).
Differential privacy for multi-armed bandits: What is it and what is
its cost?
arXiv preprint arXiv:1905.12298.

[7]
Bechhofer, R. E. (1954).
A single-sample multiple decision procedure for ranking means of
normal populations with known variances.
The Annals of Mathematical Statistics, pages 16–39.

[8]
Bechhofer, R. E. (1958).
A sequential multiple-decision procedure for selecting the best one
of several normal populations with a common unknown variance, and its use
with various experimental designs.
Biometrics, 14(3):408–429.

[9]
Cai, T. T., Wang, Y., and Zhang, L. (2021).
The cost of privacy: Optimal rates of convergence for parameter
estimation with differential privacy.
The Annals of Statistics, 49(5):2825–2850.

[10]
Carpentier, A. and Locatelli, A. (2016).
Tight (lower) bounds for the fixed budget best arm identification
bandit problem.
In Conference on Learning Theory, pages 590–604. PMLR.

[11]
Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. (2014).
Combinatorial pure exploration of multi-armed bandits.
Advances in neural information processing systems, 27.

[12]
Cheu, A. (2021).
Differential privacy in the shuffle model: A survey of separations.
arXiv preprint arXiv:2107.11839.

[13]
Degenne, R., Koolen, W. M., and Ménard, P. (2019).
Non-asymptotic pure exploration by solving games.
Advances in Neural Information Processing Systems, 32.

[14]
Dong, J., Roth, A., and Su, W. J. (2022).
Gaussian differential privacy.
Journal of the Royal Statistical Society Series B: Statistical
Methodology, 84(1):3–37.

[15]
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2013).
Local privacy and statistical minimax rates.
In 2013 IEEE 54th Annual Symposium on Foundations of Computer
Science, pages 429–438. IEEE.

[16]
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010a).
Differential privacy under continual observation.
In Proceedings of the forty-second ACM symposium on Theory of
computing, pages 715–724. ACM.

[17]
Dwork, C., Naor, M., Pitassi, T., Rothblum, G. N., and Yekhanin, S. (2010b).
Pan-private streaming algorithms.
In ICS, pages 66–80.

[18]
Dwork, C. and Roth, A. (2014).
The algorithmic foundations of differential privacy.
Foundations and Trends® in Theoretical Computer
Science, 9(3–4):211–407.

[19]
Even-Dar, E., Mannor, S., Mansour, Y., and Mahadevan, S. (2006).
Action elimination and stopping conditions for the multi-armed bandit
and reinforcement learning problems.
Journal of machine learning research, 7(6).

[20]
Gabillon, V., Ghavamzadeh, M., and Lazaric, A. (2012).
Best arm identification: A unified approach to fixed budget and fixed
Advances in Neural Information Processing Systems, 25.

[21]
Garivier, A. and Kaufmann, E. (2016).
Optimal best arm identification with fixed confidence.
In Conference on Learning Theory, pages 998–1027. PMLR.

[22]
Girgis, A. M., Data, D., Diggavi, S., Suresh, A. T., and Kairouz, P. (2021).
On the renyi differential privacy of the shuffle model.
In Proceedings of the 2021 ACM SIGSAC Conference on Computer and
Communications Security, pages 2321–2341.

[23]
Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S. (2014).
lil’ucb: An optimal exploration algorithm for multi-armed bandits.
In Conference on Learning Theory, pages 423–439. PMLR.

[24]
Jamieson, K. and Nowak, R. (2014).
Best-arm identification algorithms for multi-armed bandits in the
fixed confidence setting.
In 2014 48th Annual Conference on Information Sciences and
Systems (CISS), pages 1–6. IEEE.

[25]
Jamieson, K. and Talwalkar, A. (2016).
Non-stochastic best arm identification and hyperparameter
In Artificial intelligence and statistics, pages 240–248.

[26]
Jourdan, M. and Degenne, R. (2022).
Non-asymptotic analysis of a ucb-based top two algorithm.
arXiv preprint arXiv:2210.05431.

[27]
Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, E. (2022).
Top two algorithms revisited.
Advances in Neural Information Processing Systems,

[28]
Jourdan, M., Degenne, R., and Kaufmann, E. (2023).
Dealing with unknown variances in best-arm identification.
International Conference on Algorithmic Learning Theory.

[29]
Kalogerias, D. S., Nikolakakis, K. E., Sarwate, A. D., and Sheffet, O. (2021).
Quantile multi-armed bandits: Optimal best-arm identification and a
differentially private scheme.
IEEE Journal on Selected Areas in Information Theory,

[30]
Karwa, V. and Vadhan, S. (2017).
Finite sample differentially private confidence intervals.

[31]
Kaufmann, E., Cappé, O., and Garivier, A. (2016).
On the complexity of best arm identification in multi-armed bandit
Journal of Machine Learning Research, 17:1–42.

[32]
Kaufmann, E. and Kalyanakrishnan, S. (2013).
Information complexity in bandit subset selection.
In Conference on Learning Theory, pages 228–251. PMLR.

[33]
Kaufmann, E. and Koolen, W. M. (2021).
Mixture martingales revisited with applications to sequential tests
and confidence intervals.
Journal of Machine Learning Research, 22(246):1–44.

[34]
Lattimore, T. and Szepesvári, C. (2020).
Bandit algorithms.
Cambridge University Press.

[35]
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and Talwalkar, A. (2017).
Hyperband: A novel bandit-based approach to hyperparameter
The Journal of Machine Learning Research, 18(1):6765–6816.

[36]
Libin, P. J., Verstraeten, T., Roijers, D. M., Grujic, J., Theys, K., Lemey,
P., and Nowé, A. (2019).
Bayesian best-arm identification for selecting influenza mitigation
In Machine Learning and Knowledge Discovery in Databases:
European Conference, ECML PKDD 2018.

[37]
Lindståhl, S., Proutiere, A., and Johnsson, A. (2022).
Measurement-based admission control in sliced networks: A best arm
identification approach.
In GLOBECOM 2022-2022 IEEE Global Communications Conference,
pages 1484–1490. IEEE.

[38]
Losada, D. E., Elsweiler, D., Harvey, M., and Trattner, C. (2022).
A day at the races: using best arm identification algorithms to
reduce the cost of information retrieval user studies.
Applied Intelligence, 52(5):5617–5632.

[39]
Mannor, S. and Tsitsiklis, J. N. (2004).
The sample complexity of exploration in the multi-armed bandit
Journal of Machine Learning Research, 5(Jun):623–648.

[40]
Mironov, I. (2017).
Rényi differential privacy.
In 2017 IEEE 30th computer security foundations symposium
(CSF), pages 263–275. IEEE.

[41]
Mishra, N. and Thakurta, A. (2015).
(Nearly) optimal differentially private stochastic multi-arm
In UAI.

[42]
Neel, S. and Roth, A. (2018).
Mitigating bias in adaptive data gathering via differential privacy.
In International Conference on Machine Learning, pages
3720–3729. PMLR.

[43]
Nikolakakis, K. E., Kalogerias, D. S., and Sarwate, A. D. (2019).
Optimal rates for learning hidden tree structures.
arXiv preprint arXiv:1909.09596.

[44]
Rio, A., Barlier, M., Colin, I., and Soare, M. (2023).
Multi-agent best arm identification with private communications.
In Proceedings of the 40th International Conference on Machine

[45]
Russo, D. (2016).
Simple bayesian algorithms for best arm identification.
In Conference on Learning Theory, pages 1417–1418. PMLR.

[46]
Sajed, T. and Sheffet, O. (2019).
An optimal private stochastic-mab algorithm based on optimal private
stopping rule.
In International Conference on Machine Learning, pages
5579–5588. PMLR.

[47]
Shang, X., Heide, R., Menard, P., Kaufmann, E., and Valko, M. (2020).
Fixed-confidence guarantees for bayesian best-arm identification.
In International Conference on Artificial Intelligence and
Statistics, pages 1823–1832. PMLR.

[48]
Shariff, R. and Sheffet, O. (2018).
Differentially private contextual linear bandits.
In Advances in Neural Information Processing Systems, pages

[49]
Soare, M., Lazaric, A., and Munos, R. (2014).
Best-arm identification in linear bandits.
Advances in Neural Information Processing Systems, 27.

[50]
Tossou, A. C. and Dimitrakakis, C. (2016).
Algorithms for differentially private multi-armed bandits.
In Thirtieth AAAI Conference on Artificial Intelligence.

[51]
Tucker, K., Branson, J., Dilleen, M., Hollis, S., Loughlin, P., Nixon, M. J.,
and Williams, Z. (2016).
Protecting patient privacy when sharing patient-level data from
clinical trials.
BMC medical research methodology, 16(1):5–14.

[52]
Zhou, Y., Chen, X., and Li, J. (2014).
Optimal pac multiple arm identification with applications to
In International Conference on Machine Learning, pages
217–225. PMLR.

§ OUTLINE

The appendices are organized as follows:

* The proof of our lower bound is detailed in Appendix <ref> (Theorem <ref>).

* The proof of the privacy of  is done in Appendix <ref> (Theorem <ref>).

* The  algorithm is presented in more details in Appendix <ref>, and we show the $\delta$-correctness of the non-private GLR stopping rule (Theorem <ref>).

* The asymptotic upper bound on the expected sample complexity of  is proven in Appendix <ref> (Theorem <ref>).

* Extended experiments are presented in Appendix <ref>.

§ LOWER BOUNDS ON SAMPLE COMPLEXITY

In this section, we provide the proofs for the sample complexity lower bounds. First, we present the canonical model for BAI to introduce the relevant quantities. Then, we prove an $\epsilon$-global version of the transportation lemma, i.e. Lemma <ref>. Using this lemma, we prove Theorem <ref>. Finally, we prove the formula expressing the TV characteristic time for Bernoulli instances.

§.§ Canonical model for BAI

Let $\boldsymbol{\nu} \triangleq \{\nu_a : a \in [\arms]\}$ be a bandit instance, consisting of $\arms$ arms with finite means $\{\mu_a\}_{a \in [\arms]}$. Now, we recall the interaction between a BAI strategy $\pi$ and the bandit instance $\nu$ in the Protocol <ref>. The BAI strategy $\pi$ halts at $\tau$, samples a sequence of actions $\underline{A}^\tau$, and recommends the action $\hat{A}$. Let $\mathbb{P}_{\boldsymbol{\nu}, \pi}$ be the probability distribution over the triplets $(\tau, \underline{A}^\tau, \hat{A})$, when the BAI strategy $\pi$ interacts with the bandit instance $\nu$.

For a fixed $\horizon > 1$, a sequence of actions $\underline{a}^\horizon = (a_1, \dots, a_\horizon) \in [\arms]^\horizon$ and a recommendation $\hat{a} \in [\arms]$, we define the event $E = \{\tau = \horizon, \underline{A}^\tau = \underline{a}^\horizon,  \hat{A} = \hat{a} \}$. We have that

\begin{align*}
\mathbb{P}_{\boldsymbol{\nu}, \pi}(E) = \int_{\underline{r}^\horizon = (r_1, \dots, r_\horizon) \in \real^\horizon} \pol(\underline{a}^\horizon, \hat{a}, \horizon \mid  \underline{r}^\horizon ) \prod_{t = 1}^\horizon \dd \nu_{a_t}(r_t) dr_t
\end{align*}

\begin{align*}
\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{r}^\horizon) \defn \operatorname{Rec}_{T+1}\left(\widehat{a} \mid \mathcal{H}_{\horizon}\right) \mathrm{S}_{T+1}\left(\top \mid \mathcal{H}_{\horizon} \right) \prod_{t=1}^T \mathrm{~S}_t\left(a_t \mid \mathcal{H}_{t - 1}\right)
\end{align*}

and $\mathcal{H}_t = (a_1, r_1, \dots, a_t, r_t)$.

Remark on the bandit feedback. Let $\pi$ be an $\epsilon$-DP BAI strategy. Let $\horizon \geq 1$, $\underline{a}^\horizon \in [\arms]^\horizon$ a sequence sampled actions and $\widehat{a} \in [\arms]$ a recommended actions. This time, let $\underline{r}^\horizon = \{r_1, \dots, r_\horizon \} \in \real^\horizon$ and $\underline{r'}^\horizon \in \real^\horizon$ two neighbouring sequence of rewards, i.e. $\dham(\underline{r}^\horizon, \underline{r'}^\horizon) \defn \sum_{t = 1}^\horizon \ind{r_t \neq r'_t} = 1$ . Consider the table of rewards $\underline{d}^\horizon$ consisting of concatenating $\underline{r}^\horizon$ colon-wise $ \arms$ times, i.e. $\underline{d}^\horizon_{t, i} = \underline{r}^\horizon_t$ for all $i \in [\arms]$ and all $t \in [\horizon]$ . Define $\underline{d'}^\horizon$ similarly with respect to $\underline{r'}^\horizon$.

In this case, by definition of $\pi$, $\underline{d}^\horizon$ and $\underline{d'}^\horizon$, it is direct that

\begin{equation*}
\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{r}^\horizon) = \pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{d}^\horizon)
\end{equation*}

and $\dham(\underline{d}^\horizon, \underline{d'}^\horizon) = 1$.

Which means that

\begin{equation*}
\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{r}^\horizon)  \leq e^\epsilon \pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{r'}^\horizon).
\end{equation*}

In other words, if $\pi$ is $\epsilon$-pure DP for neighbouring table of rewards $\underline{d}^\horizon$, then $\pi$ is also $\epsilon$-pure DP for neighbouring sequence of observed rewards $\underline{r}^\horizon$.

§.§ Transportation lemma under $\epsilon$-global DP: Proof of Lemma <ref>

lem:chg_env_dp[Transportation lemma under $\epsilon$-global DP]
Let $\delta \in (0,1) $ and $\epsilon>0$. Let $\boldsymbol{\nu}$ be a bandit instance and $\lambda \in \operatorname{Alt}(\boldsymbol{\nu})$. For any $\delta$-correct $\epsilon$-global DP BAI strategy, we have that

\begin{equation*}
6 \epsilon  \sum_{a = 1}^\arms \expect_{\boldsymbol{\nu}, \pi} \left [N_a(\tau) \right] \TV{\nu_{a}}{\lambda_{a}}  \geq \mathrm{kl}(1-\delta, \delta),
\end{equation*}

where $\mathrm{kl}(x, y) \defn x \log\frac{x}{y} + (1 - x) \log \frac{1 - x}{1 - y} \;$ for $x,y \in (0,1)$.

Step 1: Distinguishability due to $\delta$-correctness. Let $\pi$ be a $\delta$-correct $\epsilon$-global DP BAI strategy. Let $\boldsymbol{\nu}$ be a bandit instance and $\lambda \in \operatorname{Alt}(\boldsymbol{\nu})$.

Let $\mathbb{P}_{\boldsymbol{\nu}, \pi}$ denote the probability distribution of $(\underline{A}, \widehat{A}, \tau)$ when the BAI strategy $\pi$ interacts with $\nu$. For any alternative instance $\lambda \in \operatorname{Alt}(\boldsymbol{\nu})$, the data-processing inequality gives that

\begin{align}\label{ineq:data}
\KL{\mathbb{P}_{\boldsymbol{\nu}, \pi}}{\mathbb{P}_{\boldsymbol{\lambda}, \pi}} & \geq \mathrm{kl}\left(\mathbb{P}_{\boldsymbol{\nu}, \pi}\left(\widehat{A}=a^{\star}(\boldsymbol{\nu})\right), \mathbb{P}_{\boldsymbol{\lambda}, \pi}\left(\widehat{A}=a^{\star}(\boldsymbol{\nu})\right)\right) \notag\\
& \geq \mathrm{kl}(1-\delta, \delta) .
\end{align}

where the second inequality is because $\pi$ is $\delta$-correct i.e. $\mathbb{P}_{\boldsymbol{\nu}, \pi}\left(\widehat{A}=a^{\star}(\boldsymbol{\nu})\right) \geq 1 - \delta$ and $\mathbb{P}_{\boldsymbol{\lambda}, \pi}\left(\widehat{A}=a^{\star}(\boldsymbol{\nu})\right) \leq \delta$, and the monotonicity of the $\mathrm{kl}$.

Step 2: Connecting KL and TV under $\epsilon$-global DP. On the other hand, by the definition of the KL, we have that

\begin{align*}
\KL{\mathbb{P}_{\boldsymbol{\nu}, \pi}}{\mathbb{P}_{\boldsymbol{\lambda}, \pi}} = \expect_{\tau, \underline{A}^\tau, \hat{A} \sim \mathbb{P}_{\boldsymbol{\nu}, \pi} } \left[ \log \left ( \frac{\mathbb{P}_{\boldsymbol{\nu}, \pi}(\tau, \underline{A}^\tau, \hat{A})}{ \mathbb{P}_{\boldsymbol{\lambda}, \pi}(\tau, \underline{A}^\tau, \hat{A}) } \right) \right]
\end{align*}

\begin{equation*}
\mathbb{P}_{\boldsymbol{\nu}, \pi}(\tau = \horizon, \underline{A}^\tau = \underline{a}^\horizon,  \hat{A} = \hat{a}) = \int_{\underline{r} \in \real ^ \horizon} \pi(\underline{a}^\horizon,  \widehat{a}, T \mid \underline{r}) \prod_{t = 1}^\horizon  \dd \nu_{a_t}(r_t).
\end{equation*}

Since $\pi$ is $\epsilon$-global DP, using the sequential Karwa-Vadhan lemma <cit.>, we get that

\begin{align*}
\log \left ( \frac{ \mathbb{P}_{\boldsymbol{\nu}, \pi}(\tau = \horizon, \underline{A}^\tau = \underline{a}^\horizon,  \hat{A} = \hat{a})}{  \mathbb{P}_{\boldsymbol{\lambda
}, \pi}(\tau = \horizon, \underline{A}^\tau = \underline{a}^\horizon,  \hat{A} = \hat{a}) } \right) &\leq  6 \epsilon \sum_{t = 1}^\horizon \TV{\nu_{a_t}}{\lambda_{a_t}}\\
&= 6 \epsilon \sum_{a = 1}^\arms N_a(\horizon) \TV{\nu_{a}}{\lambda_{a}}
\end{align*}

Which gives that

\begin{align}\label{ineq:karwa}
\KL{\mathbb{P}_{\boldsymbol{\nu}, \pi}}{\mathbb{P}_{\boldsymbol{\lambda}, \pi}} \leq 6 \epsilon \expect_{\boldsymbol{\nu}, \pi} \left [ \sum_{a = 1}^\arms N_a(\tau) \TV{\nu_{a}}{\lambda_{a}} \right].
\end{align}

Combining Inequalities <ref> and <ref> concludes the proof.

§.§ Lower bound on sample complexity: Proof of Theorem <ref>

thm:lower_bound[Sample complexity lower bound for $\epsilon$-DP-FC-BAI]
Let $\delta \in (0,1) $ and $\epsilon>0$. For any $\delta$-correct $\epsilon$-global DP BAI strategy, we have that

\begin{align*}
\mathbb{E}_{\boldsymbol{\nu}}[\tau] &\geq T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \log (1 / 3 \delta),%\\
%\text{where}~\left (T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \right ) ^{-1 } &\defn \sup _{\omega \in \Sigma_K} \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})} \min  \left(\sum_{a=1}^K \omega_a \KL{\nu_a}{\lambda_a}, 6 \epsilon \sum_{a=1}^K \omega_a  \TV{\nu_a}{\lambda_a} \right).\notag
\end{align*}

where $\left (T^{\star}\left(\boldsymbol{\nu} ; \epsilon\right) \right )^{-1 } \defn \sup\limits_{\omega \in \Sigma_K} \inf\limits_{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})} \min  \left(\sum_{a=1}^K \omega_a \KL{\nu_a}{\lambda_a}, 6 \epsilon \sum_{a=1}^K \omega_a  \TV{\nu_a}{\lambda_a} \right)$.

Let $\pi$ be a $\delta$-correct $\epsilon$-global DP BAI strategy. Let $\boldsymbol{\nu}$ be a bandit instance and $\lambda \in \operatorname{Alt}(\boldsymbol{\nu})$.

Let $\expect$ denote the expectation under $\mathbb{P}_{\boldsymbol{\nu}, \pi}$, ie $\expect \defn \expect_{\boldsymbol{\nu}, \pi}$.

By Lemma <ref>, we have that
$6 \epsilon  \sum_{a = 1}^\arms \expect \left [N_a(\tau) \right] \TV{\nu_{a}}{\lambda_{a}}  \geq \mathrm{kl}(1-\delta, \delta).$

Lemma 1 from [31] gives that $\sum_{a = 1}^\arms \expect \left [N_a(\tau) \right] \KL{\nu_{a}}{\lambda_{a}} \geq \mathrm{kl}(1-\delta, \delta).$

Since these two inequalities hold for all $\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})$, we get

\begin{align*}
\mathrm{kl}(1- &\delta, \delta)  \leq \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})} \min \left(6 \epsilon  \sum_{a = 1}^\arms \expect \left [N_a(\tau) \right] \TV{\nu_{a}}{\lambda_{a}} ,\sum_{a = 1}^\arms \expect \left [N_a(\tau) \right] \KL{\nu_{a}}{\lambda_{a}}\right) \\
& \stackrel{(a)}{=} \expect[\tau] \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})} \min \left(6 \epsilon \sum_{a=1}^K \frac{\expect\left[N_a(\tau)\right]}{\expect[\tau]} \TV{\nu_{a}}{\lambda_{a}}, \sum_{a=1}^K \frac{\expect\left[N_a(\tau)\right]}{\expect[\tau]} \KL{\nu_{a}}{\lambda_{a}}\right) \\
& \stackrel{(b)}{\leq} \expect[\tau]\left(\sup _{\omega \in \Sigma_K} \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})} \min \left( 6 \epsilon \sum_{a=1}^K \omega_a  \TV{\nu_a}{\lambda_a}, \sum_{a=1}^K \omega_a \KL{\nu_a}{\lambda_a} \right) \right) \: .
\end{align*}

(a) is due to the fact that $\expect[\tau]$ does not depend on $\boldsymbol{\lambda}$. (b) is obtained by noting that the vector $\left(\omega_a\right)_{a \in[K]} \triangleq \left(\frac{\mathbb{E}_{\nu, \pi}\left[N_a(\tau)\right]}{\mathbb{E}_{\nu, \pi}[\tau]}\right)_{a \in[K]}$ belongs to the simplex $\Sigma_\arms$.

The theorem follows by noting that for $\delta \in(0,1), \mathrm{kl}(1-\delta, \delta) \geq \log (1 / 3 \delta)$.

§.§ TV characteristic time for Bernoulli instances: Proof of Proposition <ref>

prop:tv[TV characteristic time for Bernoulli instances] Let $\nu$ be a bandit instance, i.e. such that $\nu_a = \text{Bernoulli}(\mu_a)$ and $\mu_1 > \mu_2 \geq \dots \geq \mu_\arms$. Let $\Delta_a \defn \mu_1 - \mu_a$ and $\Delta_\text{min} \defn \min_{a \neq 1} \Delta_a $. We have that

\begin{align*}
T^{\star}_{\mathrm{TV}}(\boldsymbol{\nu}) = \frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a}, &&\text{and}  &&\frac{1}{\Delta_{\text{min}}} \leq T^{\star}_{\mathrm{TV}}(\boldsymbol{\nu}) \leq  \frac{\arms}{\Delta_{\text{min}}}.
\end{align*}

Step 1:    Let $\nu$ be a bandit instance, i.e. such that $\nu_a \defn \text{Bernoulli}(\mu_a)$ and $\mu_1 > \mu_2 \geq \dots \geq \mu_\arms$.

For the alternative bandit instance $\boldsymbol{\lambda}$, we refer to the mean of arm $a$ as $\rho_a$, i.e. $\lambda_a \defn \text{Bernoulli}(\rho_a)$.

By the definition of $T^{\star}_{\textbf{TV}} $, we have that

\begin{align*}
\left(T^{\star}_{\textbf{TV}}(\boldsymbol{\nu}) \right)^{-1} &= \sup _{\omega \in \Sigma_K} \inf _{\boldsymbol{\lambda} \in \operatorname{Alt}(\boldsymbol{\nu})}  \sum_{a=1}^K \omega_a \TV{\nu_a}{ \lambda_a}\\
&\stackrel{(a)}{=} \sup _{\omega \in \Sigma_K} \min_{a \neq 1} \inf _{\boldsymbol{\lambda} : \rho_a > \rho_1} \omega_1 \left | \mu_1 - \rho_1 \right | + \omega_a \left | \mu_a - \rho_a  \right | \\
&\stackrel{(b)}{=} \sup _{\omega \in \Sigma_K} \min_{a \neq 1} \min(\omega_1, \omega_a) \Delta_a \\
&\stackrel{(c)}{=} \sup _{\omega \in \Sigma_K} \omega_1 \min_{a \neq 1} \min(1, \frac{\omega_a}{\omega_1}) \Delta_a \\
&\stackrel{(d)}{=} \sup_{ (x_2, \dots, x_\arms) \in (\real ^+)^{\arms - 1} } \frac{\min_{a \neq 1} g_a(x_a)}{1 + x_2 + \dots + x_\arms} \: ,
\end{align*}

where $g_a(x_a) \defn \min(1, x_a) \Delta_a$.

Equality (a) is obtained due to the fact that $\operatorname{Alt}(\boldsymbol{\nu}) = \bigcup_{a \neq 1} \{ \boldsymbol{\lambda}: \rho_a > \rho_1 \}$, and for Bernoullis, $\TV{\nu_a}{\lambda_a} = | \mu_a - \rho_a |$.

Equality (b) is true, since $\inf _{\boldsymbol{\lambda} : \rho_a > \rho_1} \omega_1 \left | \mu_1 - \rho_1 \right | + \omega_a \left | \mu_a - \rho_a  \right | = \min(\omega_1, \omega_a) \Delta_a $.

Equality (c) holds true, since $\omega_1 \neq 1$ (if $\omega_1 = 0$, the value of the objective is 0).

Equality (d) is obtained by the change of variable $x_a \defn \frac{\omega_a}{\omega_1}$

Step 2: Let $(x_2, \dots, x_\arms) \in (\real ^+)^{\arms - 1}$. By the definition of $g_a$, we have that

\[g_a(x_a) \leq x_a \Delta_a \quad \text{and} \quad g_a(x_a) \leq \Delta_a.\]

This leads to the inequalities

\[\min_{a \neq 1} g_a(x_a) \leq g_a(x_a) \leq x_a \Delta_a\quad \text{and} \quad \min_{a \neq 1} g_a(x_a) \leq \Delta_\text{min}.\]

\begin{align*}
\left (\min_{a \neq 1} g_a(x_a) \right)\left ( \frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a} \right) &= \frac{\min_{a \neq 1} g_a(x_a)}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{\min_{a \neq 1} g_a(x_a)}{\Delta_a}\\
&\leq 1 + \sum_{a=2}^\arms x_a \: .
\end{align*}

This means that for every $(x_2, \dots, x_\arms) \in (\real ^+)^{\arms - 1}$,

\begin{equation*}
\frac{\min_{a \neq 1} g_a(x_a)}{1 + x_2 + \dots + x_\arms} \leq \frac{1}{\frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a}}.
\end{equation*}

Here, the upper bound is achievable for $x^\star_a = \frac{\Delta_\text{min}}{\Delta_a}$, since $g_a(x^\star_a) = \Delta_\text{min} $ for all $a \neq 1$.

This concludes that

\begin{align*}
\left(T^{\star}_{\textbf{TV}}(\boldsymbol{\nu}) \right)^{-1} = \frac{1}{\frac{1}{\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a}} &&\implies \left(T^{\star}_{\textbf{TV}}(\boldsymbol{\nu}) \right) = {\Delta_\text{min}} + \sum_{a=2}^\arms \frac{1}{\Delta_a} \: .
\end{align*}

Step 3: The lower and upper bounds on $\left(T^{\star}_{\textbf{TV}}(\boldsymbol{\nu}) \right)$ follow from the fact that $\frac{1}{\Delta_a} \geq 0$  for all $a$, and $\frac{1}{\Delta_a} \leq \frac{1}{\Delta_{\min}}$ for all $a \neq 1$.

Hence, we conclude the proof.

§.§ On the total variation distance and the hardness of privacy

Our lower bound suggests that the hardness of the DP-FC-BAI problem is characterized by $T^\star_{TV}$, which is a total variation counterpart of the classic KL-based characteristic time $T^\star_{KL}$ in FC-BAI [21]. The total variation distance appears to be the natural measure to quantify the hardness of privacy in other settings such as regret minimization [5], Karwa-Vadhan lemma [30] and Differentially Private Assouad, Fano, and Le Cam [2]. The high-level intuition is that: Pure DP can be seen as a multiplicative stability constraint of $e^\epsilon$ when one data point changes. With group privacy, if two datasets differ in $d_{ham}$ points, then one incurs a factor $e^ {d_{ham}~\epsilon}$. Now, by sampling $n$ i.i.d points from a distribution $P$ and $n$ i.i.d points from a distribution $Q$, the Karwa-Vadhan lemma states that the incurred factor is $e^{(nTV(P,Q)) ~ \epsilon}$. This is proved by building a maximal coupling, which is the coupling that minimizes the Hamming distance in expectation. In brief, the total variation naturally appears in lower bounds since it is the quantity that characterises the hardness of the optimal transport problem minimizing the hamming distance, i.e $TV(P, Q) = \inf_{(X,Y)\sim (P,Q)} E(1_{X \neq Y})$. However, it is possible that the problem can be characterized by other f-divergences.  Finally, one can always go from TV to KL using Pinsker's inequality, though that would always be less tight than the TV-based lower bound.

On the relation between $T^\star_{TV}$ and $T^\star_{KL}$ A direct application of Pinsker's inequality gives that $T^\star_{TV}(\nu) \geq \sqrt{2 T^\star_{KL}(\nu)}$. For completeness, we present here the exact calculations:

For every alternative mean parameter $\lambda$ and every arm $a$, using Pinkser's inequality, we have that $d_{TV} ( \mu_a, \lambda_a) \leq \sqrt{\frac{1}{2} d_{KL} ( \mu_a, \lambda_a)}$.
Therefore, for every allocation over arms $\omega$, we have

\[
\sum_a \omega_a d_{TV} ( \mu_a, \lambda_a) \leq \sum_a \omega_a \sqrt{\frac{1}{2} d_{KL} ( \mu_a, \lambda_a)} \leq \sqrt{\frac{1}{2}\sum_a \omega_a d_{KL} ( \mu_a, \lambda_a)} \: .
\]

Taking the supremum over the simplex and the infimum over the set of alternative mean parameters yields $(T^\star_{TV}(\nu))^{-1} \leq \sqrt{\frac{1}{2} (T^\star_{KL}(\nu))^{-1} }$.
This concludes the proof.

§ PRIVACY ANALYSIS

In this section, we prove that  satisfies $\epsilon$-DP. We first provide the privacy lemma that justifies using doubling and forgetting in . Using the privacy lemma and the post-processing property of DP, we conclude the privacy analysis of .

§.§ Privacy lemma for non-overlapping sequences

Let $\mathcal M$ be a mechanism that takes a set as input and outputs the private empirical mean, i.e.

\begin{align}\label{eq:priv_mean}
\mathcal{M}(\{ r_i, \dots, r_j \}) \defn \frac{1}{j -i} \sum_{t=i}^{j} r_t + Lap\left ( \frac{1}{(j-i) \epsilon} \right ).
\end{align}

Let $\ell < \horizon$ and $t_1, \ldots t_{\ell}, t_{\ell + 1}$ be in $[1, \horizon]$ such that $1 = t_1  < \cdots < t_\ell < t_{\ell+1}  - 1 = T$.

Let's define the following mechanism

\begin{align}\label{eq:priv_mean_non_over}
\mathcal G : \{ r_1, \dots, r_\horizon \} \rightarrow \bigotimes_{i=1}^\ell \mathcal{M}_{ \{r_{t_i}, \ldots, r_{t_{i + 1} - 1} \}}
\end{align}

In other words, $\mathcal{G}$ is the mechanism we get by applying $\mathcal{M}$ to the non-overlapping partition of the sequence $\{r_1, \dots, r_\horizon\}$ according to $t_1  < \cdots < t_\ell < t_{\ell+1}$, i.e.

\begin{align*}
\begin{pmatrix}
\vdots \\
\end{pmatrix} \overset{\mathcal{G}}{\rightarrow}  \begin{pmatrix}
\mu_1\\
\vdots \\
\mu_\ell
\end{pmatrix}
\end{align*}

where $\mu_i \sim \mathcal{M}_{ \{r_{t_i}, \ldots, r_{t_{i + 1} - 1} \}}$.

For $r_t \in [0,1]$, the mechanism $\mathcal{G}$ is $\epsilon$-DP.

Let $r^\horizon \defn (r_1, \dots, r_\horizon)$ and $r'^\horizon \defn (r_1', \dots, r_\horizon')$ be two neighbouring reward sequences in [0,1]. This implies that $\exists j \in [1, \horizon]$ such that $r_j \neq r_j'$ and $\forall t \neq j$, $r_t = r_t'$.

Let $\episode'$ be such that $t_{\episode'} \leq j \leq t_{\episode'+1}-1$, and follows the convention that $t_0 = 1$ and $t_{\episode + 1} = T + 1$.

Let $\mu \defn (\mu_1, \dots, \mu_\episode)$ a fixed sequence of outcomes. Then,

\begin{align*}
\frac{\mathbb P ( \mathcal{G} (r^\horizon) = \mu  )}{\mathbb P ( \mathcal{G} (r'^\horizon) = \mu  )} = \frac{\mathbb P \left( \mathcal{M}(\{ r_{{t_{\ell'}}}, \dots, r_{t_{\ell'+1} - 1} \}) = \mu_{\ell'}  \right)}{\mathbb P \left( \mathcal{M}(\{ r_{{t_{\ell'}}}, \dots, r_{t_{\ell'+1} - 1} \}) = \mu_{\ell'}  \right)} \leq e^\epsilon,
\end{align*}

where the last inequality holds true because $\mathcal{M}$ satisfies $\epsilon$-DP following Theorem <ref>.

§.§ Privacy analysis of : Proof of Theorem <ref>

thm:privacy[Privacy analysis]
For rewards in $[0,1]$,  satisfies $\epsilon$-global DP.

Let $\horizon \geq 1$. Let $\underline{\textbf{d}}^\horizon = \{\textbf{x}_1, \dots, \textbf{x}_\horizon\}$ and $\underline{\textbf{d}'}^\horizon = \{\textbf{d}'_1, \dots, \textbf{d}'_\horizon\}$ two neighbouring reward tables in $(\real^\arms)^\horizon$. Let $j \in [1, \horizon]$ such that, for all $t \neq j$, $d_t = d'_t$.

We also fix a sequence of sampled actions $\underline{a}^T = \{a_1, \dots, a_T\} \in [\arms]^\horizon$ and a recommended action $\hat{a}\in \arms$.

We refer to  BAI strategy by $\pi$.

We want to show that:
$\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}}^\horizon)  \leq e^\epsilon \pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}'}^\horizon)$.

The main idea is that the change of reward in the $j$-th reward only affects the empirical mean computed in one episode, which is made private using the Laplace Mechanism and Lemma <ref>.

Step 1. Sequential decomposition of the output probability

We observe that due to the sequential nature of the interaction, the output probability can be decomposed to a part that depends on $\underline{\textbf{d}}^{j - 1} \defn \{\textbf{x}_1, \dots, \textbf{x}_{j - 1}\}$, which is identical for both $\underline{\textbf{d}}^\horizon$ and $\underline{\textbf{d}'}^\horizon$ and a second conditional part on the history.

Specifically, we have that

\begin{align*}
\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}}^\horizon) &\defn \operatorname{Rec}_{T+1}\left(\widehat{a} \mid \mathcal{H}_{\horizon}\right) \mathrm{S}_{T+1}\left(\top \mid \mathcal{H}_{\horizon} \right) \prod_{t=1}^T \mathrm{~S}_t\left(a_t \mid \mathcal{H}_{t - 1}\right)\\
&\defn \mathcal{P}^{\pol}_{ \underline{\textbf{d}}^{j - 1} } (\underline{a}^j) \mathcal{P}^{\pol}_{\underline{\textbf{d}} }(a_{> j}, \hat{a}, T \mid \underline{a}^j)
\end{align*}

* $ a_{> j} \defn (a_{j + 1}, \dots, a_\horizon)$

* $\mathcal{P}^{\pol}_{ \underline{\textbf{d}}^{j - 1} } (\underline{a}^j) \defn \prod_{t = 1}^j \mathrm{~S}_t\left(a_t \mid \mathcal{H}_{t - 1}\right) $

* $\mathcal{P}^{\pol}_{\underline{\textbf{d}} }(a_{> j}, \hat{a}, T \mid \underline{a}^j)  \defn \operatorname{Rec}_{T+1}\left(\widehat{a} \mid \mathcal{H}_{\horizon}\right) \mathrm{S}_{T+1}\left(\top \mid \mathcal{H}_{\horizon} \right) \prod_{t = j+1}^\horizon \mathrm{~S}_t\left(a_t \mid \mathcal{H}_{t - 1}\right) $

\begin{equation*}
\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}'}^\horizon) \defn \mathcal{P}^{\pol}_{ \underline{\textbf{d}}^{j - 1} } (\underline{a}^j) \mathcal{P}^{\pol}_{\underline{\textbf{d}'} }(a_{> j}, \hat{a}, T \mid \underline{a}^j)
\end{equation*}

since $\underline{\textbf{d}'}^{j - 1} = \underline{\textbf{d}}^{j - 1}$.

Which means that

\begin{equation}\label{eq:deco_frac}
\frac{\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}}^\horizon)}{\pi(\underline{a}^\horizon, \widehat{a}, \horizon \mid \underline{\textbf{d}'}^\horizon)} = \frac{\mathcal{P}^{\pol}_{\underline{\textbf{d}} }(a_{> j}, \hat{a}, T \mid \underline{a}^j)}{\mathcal{P}^{\pol}_{\underline{\textbf{d}'} }(a_{> j}, \hat{a}, T \mid \underline{a}^j)}
\end{equation}

Step 2. The adaptive episodes are the same, before step $j$

Let $\ell$ such that $t_\ell \leq j < t_{\ell + 1}$ when $\pi$ interacts with $\underline{\textbf{d}}^\horizon$. Let us call it $\psi^\pol_{\underline{\textbf{d}}^\horizon}(j) \defn \ell$.
Similarly, let $\ell'$ such that $t_{\ell'} \leq j < t_{\ell' + 1}$ when $\pi$ interacts with $\underline{\textbf{d}'}^\horizon$. Let us call it $\psi^\pol_{\underline{\textbf{d}'}^\horizon}(j) \defn \ell'$.

Since $\psi^\pol_{\underline{\textbf{d}}^\horizon}(j)$ only depends on $\underline{\textbf{d}}^{j - 1}$, which is identical for $\underline{\textbf{d}}^\horizon$ and $\underline{\textbf{d}'}^\horizon$, we have that $\psi^\pol_{\underline{\textbf{d}}^\horizon}(j) = \psi^\pol_{\underline{\textbf{d}'}^\horizon}(j)$ with probability $1$.

We call $\xi_j$ the last time-step of the episode $\psi^\pol_{\underline{\textbf{d}}^\horizon}(j)$, i.e $\xi_j \defn t_{\psi^\pol_{\underline{\textbf{d}}^\horizon}(j) + 1} -1$.

Step 3. Private sufficient statistics

Let $r_t \defn \underline{\textbf{d}}^\horizon_{t, a_t}$, be the reward corresponding to the action $a_t$ in the table $\underline{\textbf{d}}^\horizon$. Similarly, $r'_t \defn \underline{\textbf{d}'}^\horizon_{t, a_t}$ for $\underline{\textbf{d}'}^\horizon$.

Let us define $L_j \defn \mathcal{G}_{\{r_1, \dots, r_{\xi_j} \} }$ and $L'_j \defn \mathcal{G}_{\{r'_1, \dots, r'_{\xi_j} \} }$, where $\mathcal{G}$ is defined as in Eq. <ref>, using the same episodes for $d$ and $d'$. In other words, $L_j$ is the list of private empirical means computed on a non-overlapping sequence of rewards before step $\xi_j$.

Using the forgetting structure of , there exists a randomised mapping $f_{\underline{\textbf{d}}_{> \xi_j}}$ such that $\mathcal{P}^{\pol}_{\underline{\textbf{d}} }(. \mid \underline{a}^j) = f_{\underline{\textbf{d}}_{> \xi_j}} \circ   L_j $ and $\mathcal{P}^{\pol}_{\underline{\textbf{d}'} }(. \mid \underline{a}^j) = f_{\underline{\textbf{d}}_{> \xi_j}} \circ   L_j' $.

In other words, the interaction of $\pi$ with $\underline{\textbf{d}}$ and $\underline{\textbf{d}'}$ from step $\xi_j + 1$ until $\horizon$ only depends on the sufficient statistics $L_j$, which summarises what happened before $\xi_j$, and the new inputs $\underline{\textbf{d}}_{> \xi_j}$, which are the same for $\underline{\textbf{d}}$ and $\underline{\textbf{d}'}$.

Step 4. Concluding with Lemma <ref> and the post-processing lemma

Since rewards are in $[0,1]$, using Lemma <ref>, we have that $\mathcal{G}$ is $\epsilon$-DP.

Since $\mathcal{P}^{\pol}_{\underline{\textbf{d}} }(. \mid \underline{a}^j)$ is just a post-processing of the output of $\mathcal{G}$, we have that

\begin{equation*}
\frac{\mathcal{P}^{\pol}_{\underline{\textbf{d}} }(a_{> j}, \hat{a}, T \mid \underline{a}^j)}{\mathcal{P}^{\pol}_{\underline{\textbf{d}'} }(a_{> j}, \hat{a}, T \mid \underline{a}^j)} \leq e^\epsilon \: ,
\end{equation*}

and Eq. (<ref>) concludes the proof.

§ : A PRIVATE TOP TWO ALGORITHM WITH ADAPTIVE EPISODES

We propose a generic wrapper to adapt existing BAI algorithms to tackle private BAI (Appendix <ref>).
Then, we show how to instantiate our wrapper with an instance of Top Two algorithm (Appendix <ref>), namely TTUCB [26].

§.§ Generic wrapper on existing BAI algorithms

We propose a generic wrapper to adapt existing BAI algorithms to tackle the $\epsilon$-DP-FC-BAI problem.

* It uses adaptive episodes with doubling and forgetting (Appendix <ref>).
This builds on the idea used to make the UCB algorithm private for regret minimisation [5].

* It relies on a private GLR (generalised likelihood ratio) stopping rule (Appendix <ref>).
The GLR stopping rule [21] is widely used in the BAI literature, since it ensures $\delta$-correctness of the stopping rule regardless of the sampling rule.

For each arm $a \in [K]$, we maintain a phase at time $n$ whose index will be denoted by $k_{n, a} \in \N$.
We switch phase as soon as the number of times that the arm was played is doubled.
We only evaluate the stopping condition when we switch phase for an arm.

§.§.§ Adaptive episodes with doubling and forgetting

As initialisation, we start by pulling each arm once, and set $k_{n,a}=1$, $T_{1}(a) = \arms+1$ and $N_{n, a} = 1$ for all $a \in [K]$.
In the following, we will consider $n > K$ and we denote the global pulling count of arm $a$ before time $n$ by $N_{n,a} \defn \sum_{t \in [n-1]} \indi{I_t = a}$.
For each arm $a \in [K]$, the random stopping time denoting the end of $k_{a}-1$ and the beginning of phase $k_{a} > 1$ is denoted by

\begin{equation} \label{eq:phase_switch_times}
T_{k_{a}}(a) \defn \inf \left\{ n \in \N \mid N_{n,a} \ge 2 N_{T_{k_{a}-1}(a), n} \right\} \: .
\end{equation}

At the beginning of phase $k_{a}$ for an arm $a \in [K]$, we update the empirical mean based on the observations on arm $a \in [K]$ collected during this last phase, i.e.

\begin{equation} \label{eq:non_private_estimator_mean}
\hat \mu_{k_{a},a} \defn \frac{1}{\tilde N_{k_{a},a}} \sum_{s = T_{k_{a}-1}(a)}^{T_{k_{a}}(a) - 1} X_{s} \ind{I_s = a} \: ,
\end{equation}

where the local pulling count pf arm $a$ is denoted by $\tilde N_{k_{a},a} \defn N_{T_{k_{a}}(a),a} -  N_{T_{k_{a}-1}(a),a}$, meaning it is the number of collected samples during the phase $k_{a} - 1$.
To ensure privacy, we add a Laplace noise to define the private empirical mean, i.e.

\begin{equation} \label{eq:private_estimator_mean}
\tilde \mu_{k_{a},a} \defn \hat \mu_{k_{a},a} + Y_{k_{a},a} \quad \text{where} \quad Y_{k_{a},a} \sim \text{Lap}\left(\frac{1}{\epsilon\tilde N_{k_{a},a}} \right) \: .
\end{equation}

We emphasise that only the private version the estimator $\hat \mu_{k_{a},a}$, i.e. $\tilde \mu_{k_{a},a}$, is used by the algorithm until the end of phase $k_{a}$ for arm $a$.
Since $(k_{n,a})_{a \in [K]}$ denotes the current phases at time $n$, our algorithm relies on $(\hat \mu_{k_{n,a},a}, \tilde \mu_{k_{a},a}, \tilde N_{k_{n,a}, a}, N_{n,a})_{a \in [K]}$.

Due to the doubling, the growth of the global and local pulling counts is exponential (Lemma <ref>).

For all $a \in [K]$ and all $k \in \N$ such that $\bE_{\bnu}[T_{k}(a)] < +\infty$, we have

\[
N_{T_{k}(a), a} = 2^{k-1} \quad \text{and} \quad \tilde N_{k,a} = 2^{k-2} \: .
\]

Let $a \in [K]$.
After initialisation, we have $k = 1$, $T_{1}(a) = \arms+1$ and $N_{T_{1}(a),a} =1$.
Using the definition of the adaptive phase switch (Equation (<ref>)), it is direct to see that $N_{T_{2}(a), a} = 2$ and $\tilde N_{2,a} = 1$ when $\bE_{\bnu}[T_{2}(a)] < +\infty$.

Now, we proceed by recurrence.
Suppose that $N_{T_{k}(a), a} = 2^{k-1}$ and $\tilde N_{k,a} = 2^{k-2}$ when $\bE_{\bnu}[T_{k}(a)] < +\infty$.
If $\bE_{\bnu}[T_{k+1}(a)] < +\infty$, then it means that the phase $k$ ends for arm $a$ almost surely.
Since we sample only one arm at each round, at the beginning of phase $k+1$ for arm $a$, we have $N_{T_{k+1}(a), a} = 2 N_{T_{k}(a), a} = 2^{k}$ by using the definition of the adaptive phase switch (<ref>).
Then, we have directly that	$\tilde N_{k+1,a} = N_{T_{k+1}(a),a} -  N_{T_{k}(a),a} = 2^{k} - 2^{k-1} = 2^{k-1}$.

§.§.§ GLR stopping rule

Non-private GLR stopping rule with phases. Given a set of non-private threshold functions $(c_{k})_{k \in \N}$, such that $c_{k} : \N \times \N \times (0,1) \to \R_{+}$ for all $k \in \N$, the non-private GLR stopping rule can be evaluated at the beginning of each phase for each arm, namely

\begin{align} \label{eq:non_private_GLR_stopping_rule}
\tau^{\text{NP}}_{\delta} &= \inf \left\{ n \in \N \mid  \forall b \neq \hat a_{n}^{\text{NP}}, \: \frac{(\hat \mu_{k_{n,\hat a_{n}^{\text{NP}}},\hat a_{n}^{\text{NP}}}  - \hat \mu_{k_{n,b}, b})^2}{1/\tilde N_{k_{n,\hat a_{n}^{\text{NP}}},\hat a_{n}^{\text{NP}}}+ 1/\tilde N_{k_{n,b},b}} \ge 2c_{k_{n,\hat a_{n}^{\text{NP}}}k_{n,b}}(\tilde N_{k_{n,\hat a_{n}^{\text{NP}}},\hat a_{n}^{\text{NP}}}, \tilde N_{k_{n,b},b},\delta) \right\} \: ,
\end{align}

where $\hat a_{n}^{\text{NP}} = \argmax_{a \in [K]} \hat \mu_{k_{n,a},a}$ is the non-private candidate answer until we switch phase again (for any arm).
We emphasise that this stopping condition is only evaluated at the beginning of each phase for each arm since it involves quantities that are fixed until we switch phase again.

Lemma <ref> gives non-private threshold functions ensuring that the non-private GLR stopping rule is $\delta$-correct for all $\delta \in (0,1)$, independently of the sampling rule.

Let $\delta \in (0,1)$.
Let $s > 1$ and $\zeta$ be the Riemann $\zeta$ function.
Given any sampling rule, the non-private GLR stopping rule (Equation (<ref>)) with non-private threshold functions

\begin{equation} \label{eq:non_private_stopping_threshold}
c_{k}(n, m,\delta) = 2 \cC_{G} \left( \frac{1}{2}\log\left(\frac{(K-1)\zeta (s)^2k^s}{\delta} \right)\right) + 2 \log(4 + \log n ) + 2 \log(4 + \log m)
\end{equation}

ensures $\delta$-correctness for $1$-sub-Gaussian distributions. The function $\cC_{G}$ is defined in Equation (<ref>). It satisfies $\cC_{G} \approx x + \log x$.

The non-private GLR stopping rule matches the one used for Gaussian bandits.
Proving $\delta$-correctness of a GLR stopping rule is done by leveraging concentration results.
In particular, we build upon Theorem 9 of [33], which is restated below.

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

\begin{align*}
\bP_{\bnu} \left[ \exists n \in \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| \cC_{G}\left(\frac{x}{|S|}\right) \right] \leq e^{-x} \: ,
\end{align*}

where $\cC_{G}$ is defined in [33] as

\begin{align} \label{eq:def_C_gaussian_KK18Mixtures}
\cC_{G}(x) \defn \min_{\lambda \in ]1/2,1]} \frac{g_G(\lambda) + x}{\lambda} &&\text{and} &&g_G (\lambda) \defn 2\lambda - 2\lambda \log (4 \lambda) + \log \zeta(2\lambda) - \frac{1}{2} \log(1-\lambda) \: .
\end{align}

Here, $\zeta$ is the Riemann $\zeta$ function and $\cC_{G}(x) \approx x + \log(x)$.

Let $\hat a = \hat a_{n}^{\text{NP}} = \argmax_{b \in [K]} \hat \mu_{k_{n,a},a}$.
Standard manipulations yield that for all $b \neq \hat a$

\begin{align*}
\frac{(\hat \mu_{k_{n,\hat a},\hat a}  - \hat \mu_{k_{n,b},b})^2}{1/\tilde N_{k_{n,\hat a},\hat a}+ 1/\tilde N_{k_{n,b},b}}
=  \inf_{y \ge x} \left\{\tilde N_{k_{n,\hat a}, \hat a}( \hat \mu_{k_{n,\hat a}, \hat a} - x)^2 + \tilde N_{k_{n,b}, b} ( \hat \mu_{k_{n,b}, b} - y)^2\right\} \: .
\end{align*}

Using the non-private GLR stopping rule (<ref>) with non-private threshold functions $(c_{k})_{k \in \N}$ and the above manipulations, we obtain

\begin{align*}
&\bP_{\bnu}\left( \tau_{\delta}^{\text{NP}} < + \infty, \hat a \neq  a^\star \right)\\
&\le \bP_{\bnu}\left( \exists n \in \N, \: \exists a \neq a^\star, \: a = \argmax_{b \in [K]} \hat \mu_{k_{n,b},b}, \: \forall b \ne a, \right. \\
&\qquad\quad \left. \inf_{y \ge x} \left\{\tilde N_{k_{n,a},  a}( \hat \mu_{k_{n, a}, a} - x)^2 + \tilde N_{k_{n,b}, b} ( \hat \mu_{k_{n,b}, b} - y)^2\right\} \ge 2c_{k_{n,a} k_{n,b}}(\tilde N_{k_{n,a}, a}, \tilde N_{k_{n,b}, b}, \delta) \right) \\
&\underset{(a)}{\le} \bP_{\bnu}\left( \exists n \in \N, \: \exists a \neq a^\star, \: a = \argmax_{b \in [K]} \hat \mu_{k_{n,a},a},  \right. \\
&\qquad\quad \left. \tilde N_{k_{n,a},  a}( \hat \mu_{k_{n,a}, a} - \mu_{a})^2 + \tilde N_{k_{n,a^\star}, a^\star} ( \hat \mu_{k_{n,a^\star}, a^\star} - \mu_{a^\star})^2 \ge 2c_{k_{n,a} k_{n,a^\star}}(\tilde N_{k_{n,a}, a}, \tilde N_{k_{n,a^\star}, a^\star}, \delta) \right) \\
&\underset{(b)}{\le} \bP_{\bnu}\left( \exists a \neq a^\star, \exists (k_{a}, k_{a^\star}) \in \N^2, \right. \\
&\qquad\quad \left.  \tilde N_{k_{a},  a}( \hat \mu_{k_{ a}, a} - \mu_{a})^2 + \tilde N_{k_{a^\star}, a^\star} ( \hat \mu_{k_{a^\star}, a^\star} - \mu_{a^\star})^2 \ge 2c_{k_{a} k_{a^\star}}(\tilde N_{k_{a}, a}, \tilde N_{k_{a^\star}, a^\star}, \delta) \right) \\
&\underset{(c)}{\le} \sum_{a \ne a^\star} \sum_{(k_{a}, k_{a^\star}) \in \N^2}  \bP_{\bnu}\left(\tilde N_{k_{a},  a}( \hat \mu_{k_{ a}, a} - \mu_{a})^2 + \tilde N_{k_{a^\star}, a^\star} ( \hat \mu_{k_{a^\star}, a^\star} - \mu_{a^\star})^2 \right. \\
&\qquad \qquad \qquad \qquad\qquad \qquad\qquad \qquad\qquad \qquad
\left. \ge 2c_{k_{a} k_{a^\star}}(\tilde N_{k_{a}, a}, \tilde N_{k_{a^\star}, a^\star}, \delta) \right) \: ,
\end{align*}

The inequality (a) is obtained with $(b,x,y) = (a^\star, \mu_{a}, \mu_{a^\star})$.
The inequality (b) drops the condition $a = \argmax_{b \in [K]} \hat \mu_{k_{b},b}$, hence we can restrict to $(k_{a}, k_{a^\star}) \in \N^2$ since it doesn't depend on other phase indices.
The inequality (c) relies on a direct union bound.
For all $a \ne a^\star$ and all $(k_{a}, k_{a^\star}) \in \N^2$, the estimators $\hat \mu_{k_{a},a}$ (resp. $\hat \mu_{k_{a^\star},a^\star}$) are based solely on the observations collected for arm $a$ (resp. arm $a^\star$) between times $n \in \{ T_{k_{a}-1}(a), \cdots, T_{k_{a}}(a) -1 \}$ (resp. $n \in \{ T_{k_{a^\star}-1}(a^\star), \cdots, T_{k_{a^\star}}(a^\star)-1\}$) with local counts $\tilde N_{k_{a},a}$ (resp. $\tilde N_{k_{a^\star},a^\star}$), i.e. dropping past observations.
Using Lemma <ref> for all $a \ne a^\star$ and all $(k_{a}, k_{a^\star}) \in \N^2$, we obtain

\begin{align*}
\bP_{\bnu}\left( \tau_{\delta} < + \infty, \hat \imath = i^\star \right) &\le \frac{\delta}{K-1} \frac{1}{\zeta (s)^2 }  \sum_{a \ne a^\star} \sum_{(k_{a}, k_{a^\star}) \in \N^2} \frac{1}{(k_{a} k_{a^\star})^s} =  \delta \: .
\end{align*}

Private GLR stopping rule with phases. Since we want to ensure privacy, the non-private GLR stopping rule cannot be used since it relies on the empirical means $\hat \mu_{k_{n,a},a}$, which are not private.
To alleviate this problem, we propose the private GLR stopping rule, which is based on the private empirical means $\tilde \mu_{k_{n,a},a}$.

Given a set of private threshold functions $(c_{\epsilon,k_1,k_2})_{(\epsilon,k_1,k_2) \in \R^\star_{+} \times \N^2}$, such that $c_{\epsilon,k_1,k_2} : \N \times \N \times (0,1) \to \R_{+}$ for all $(\epsilon,k_1,k_2) \in \R^\star_{+} \times \N^2$, the non-private GLR stopping rule is evaluated at the beginning of each phase for each arm, namely

\begin{align} \label{eq:private_GLR_stopping_rule}
\tau_{\delta} &= \inf \left\{ n \in \N \mid  \forall b \neq \hat a_{n}, \: \frac{(\tilde \mu_{k_{n,\hat a_{n}},\hat a_{n}}  - \tilde \mu_{k_{n,b}, b})^2}{1/\tilde N_{k_{n,\hat a_{n}},\hat a_{n}}+ 1/\tilde N_{k_{n,b},b}} \ge 2c_{\epsilon,k_{n,\hat a_{n}},k_{n,b}}(\tilde N_{k_{n,\hat a_{n}},\hat a_{n}}, \tilde N_{k_{n,b},b},\delta) \right\} \: ,
\end{align}

where $\hat a_{n} = \argmax_{a \in [K]} \tilde \mu_{k_{n,a},a}$ is the private candidate answer until we switch phase again (for any arm).
We emphasise that this stopping condition is only evaluated at the beginning of each phase for each arm since it involves quantities that are fixed until we switch phase again.

Theorem <ref> gives private threshold functions ensuring that the private GLR stopping rule is $\delta$-correct for all $\delta \in (0,1)$ and all $\epsilon \in \R^\star_{+}$, independently of the sampling rule.
thm:delta_correct_private_threshold[$\delta$-correctness of the private GLR stopping rule]
Let $\delta \in (0,1)$ and $\epsilon \in \R^\star_{+}$.
Let $s > 1$ and $\zeta$ be the Riemann $\zeta$ function and non-private threshold function $(c_{k})_{k \in \N}$ as in (<ref>).
Given any sampling rule, the private GLR stopping rule (Equation (<ref>)) with private threshold functions

\begin{equation} \label{eq:stopping_private_threshold}
c_{\epsilon,k_{1},k_{2}}(n, m,\delta) = 2 c_{k_{1}k_{2}}(n, m,\delta/2) + \frac{1}{n \epsilon^2} \log \left(\frac{2 K k_{1}^{s} \zeta(s)}{\delta} \right)^2 + \frac{1}{m \epsilon^2} \log \left(\frac{2 K k_{2}^{s} \zeta(s)}{\delta} \right)^2
\end{equation}

ensures $\delta$-correctness for $1$-sub-Gaussian distributions.

Let $\epsilon \in \R^{\star}_{+}$.
Since $Y_{k_{n,a},a} \sim \text{Lap}\left((\epsilon\tilde N_{k_{n,a},a})^{-1} \right)$, we have that $\tilde N_{k_{n,a}, a} |Y_{k_{n,a},a}| \sim \cE(\epsilon)$ for all $a \in [K]$ and all $n \in \N$, where $\cE(\cdot)$ denotes the exponential distribution.
Using concentration results for exponential distribution, a direct union bound yields that

\begin{equation} \label{eq:concentration_time_uniform_privacy}
\bP\left( \exists n \in \N, \: \exists a \in [K], \: \tilde N_{k_{n,a}, a} |Y_{k_{n,a},a}| \ge \frac{1}{\epsilon}\log \left(\frac{ K k_{n,a}^{s} \zeta(s)}{\delta} \right)\right) \le \delta \: .
\end{equation}

Let us denote $\tilde c_{\epsilon,k_{1},k_{2}}(n, m,\delta)$ the threshold associated to the Laplace noise, i.e.

\[
\tilde  c_{\epsilon,k_{1},k_{2}}(n, m,\delta) =\frac{1}{n \epsilon^2} \log \left(\frac{ K k_{1}^{s} \zeta(s)}{\delta} \right)^2 + \frac{1}{m \epsilon^2} \log \left(\frac{ K k_{2}^{s} \zeta(s)}{\delta} \right)^2 \: .
\]

Using the private GLR stopping rule (Equation (<ref>)) with private threshold functions $(c_{\epsilon,k_1,k_2})_{(\epsilon,k_1,k_2) \in \R^{\star}_{+} \times \N^2}$, similar manipulations as above yields

\begin{align*}
&\bP_{\bnu}\left( \tau_{\delta} < + \infty, \hat a \neq  a^\star \right)\\
&\le \bP_{\bnu}\left( \exists n \in \N, \: \exists a \neq a^\star,  \tilde N_{k_{n,a},  a}( \hat \mu_{k_{n,a}, a} - \mu_{a} + Y_{k_{n,a},a})^2 + \tilde N_{k_{n,a^\star}, a^\star} ( \hat \mu_{k_{n,a^\star}, a^\star} - \mu_{a^\star} + Y_{k_{n,a^\star}, a^\star})^2 \right. \\
&\qquad \quad \left. \ge 4c_{k_{n,a} k_{n,a^\star}}(\tilde N_{k_{n,a}, a}, \tilde N_{k_{n,a^\star}, a^\star}, \delta/2) + 2\tilde  c_{\epsilon,k_{n,a},k_{n,a^\star}}(\tilde N_{k_{n,a}, a}, \tilde N_{k_{n,a^\star}, a^\star},\delta/2)\right) \\
&\underset{(a)}{\le} \bP_{\bnu}\left( \exists a \neq a^\star, \exists (k_{a}, k_{a^\star}) \in \N^2, \right. \\
&\qquad \qquad \left.  \tilde N_{k_{a},  a}( \hat \mu_{k_{ a}, a} - \mu_{a})^2 + \tilde N_{k_{a^\star}, a^\star} ( \hat \mu_{k_{a^\star}, a^\star} - \mu_{a^\star})^2 \ge 2c_{k_{a} k_{a^\star}}(\tilde N_{k_{a}, a}, \tilde N_{k_{a^\star}, a^\star}, \delta/2) \right) \\
&\quad +  \bP_{\bnu}\left(\exists n \in \N, \: \exists a \neq a^\star,  \:  \tilde N_{k_{n,a}, a} Y_{k_{n,a},a}^2 + \tilde N_{k_{n,a^\star}, a^\star} Y_{k_{n,a^\star},a^\star}^2 \right. \\
&\qquad \qquad \left.   \ge \tilde  c_{\epsilon,k_{n,a},k_{n,a^\star}}(\tilde N_{k_{n,a}, a}, \tilde N_{k_{n,a^\star}, a^\star},\delta/2) \right)\\
&\underset{(b)}{\le} \delta/2 + \bP\left( \exists n \in \N, \: \exists a \in [K], \: \tilde N_{k_{n,a}, a} |Y_{k_{n,a},a}| \ge \frac{1}{\epsilon}\log \left(\frac{2 K k_{n,a}^{s} \zeta(s)}{\delta} \right)\right)\\
&\underset{(c)}{\le} \delta/2 + \delta/2 = \delta \:.
\end{align*}

The inequality (a) uses that $\bP(X + Y  \ge a+b) \le \bP(X \ge a) + \bP(Y \ge b) $ and $(x - y)^2 \le 2x^2 + 2y^2$.
The inequality (c) leverages Lemma <ref> and a direct inclusion of event.
The inequality (c) deploys Equation (<ref>) to conclude.

§.§ : Instantiating our wrapper with a Top Two sampling rule

A blueprint of Top Two algorithm design. At time $n > K$, a Top Two sampling rule defines a leader $B_n$ and a challenger $C_n$.
Then, it selects among them the next arm to sample $I_n$.
Given a proportion $\beta \in (0,1)$ fixed beforehand, the choice of $I_n \in \{B_n, C_n\}$ should ensure that the leader is sampled close to $\beta$ of the times where it was chosen as leader.
In early works on Top Two algorithms, this choice is randomised.
Following [26], we use $K$ independent tracking procedures.

We denote by $N^{a}_{n,b} \defn \sum_{t \in [n-1]} \indi{B_t = a, \: I_t = C_t  = b}$ the number of times the arm $b$ was pulled while the arm $a$ was the leader, and by $L_{n,a} \defn \sum_{t \in [n-1]} \indi{B_t = a}$ the number of times arm $a$ was the leader.
At time $n > K$, the next arm to be pulled $I_n$ is defined as

\begin{equation} \label{eq:tracking_selection}
I_{n} = B_{n} \quad \text{if } N_{n,B_n}^{B_n} \le \beta L_{n+1,B_n} \text{ , otherwise} \quad I_{n} = C_{n} \: .
\end{equation}

In other words, we sample the leader if we have not yet sampled it a fraction $\beta$ of the times it was leader.
Those $K$ independent tracking procedure satisfy the desired property (Lemma <ref>).

For all $n > K$ and all $a \in [K]$, we have

\[
-1/2 \le N_{n,a}^{a} - \beta L_{n,a}  \le 1 \: .
\]

To finish specifying a Top Two algorithm, we simply need to specify the choice of the leader/challenger pair.
Intuitively, a good choice of the leader/challenger pair should ensure (1) sufficient exploration, (2) convergence of the leader towards the best arm $a^\star$, and (3) convergence of the global pulling proportions to the $\beta$-optimal allocation $\omega_{\mathrm{KL},\beta}(\mu)$, which is defined for Gaussian distributions as

\[
\omega^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) \defn \argmax_{\omega \in \Sigma_K, \omega_{a^\star} = \beta} \min_{a \ne a^\star} \frac{\Delta_{a}^2}{1/\beta + 1/\omega_{a}}  \: .
\]

While we consider TTUCB algorithm [26] in , we emphasise that other Top Two algorithms could be used with the same type of guarantees.
TTUCB is a Top Two algorithm which combines a UCB-based leader and a Transportation Cost (TC) challenger.
Its key novelty lies in the use of $K$ tracking procedures.
Since it is deterministic, the analysis is less cumbersome.

Non-private leader/challenger pair.
The non-private leader/challenger pair is inspired by the TTUCB algorithm [26].
At time $n > K$, the non-private UCB leader is defined as

\begin{equation} \label{eq:non_private_UCB_leader}
B^{\text{NP}}_{n} \defn \argmax_{a \in [K]} \left\{\hat \mu_{k_{n,a}, a} + \sqrt{\frac{k_{n,a}}{\tilde N_{k_{n,a},a}}} \right\} \: ,
\end{equation}

where $\sqrt{k_{n,a}/\tilde N_{k_{n,a},a}}$ is a bonus to cope for the uncertainty which depends on the current phase $k_{n,a}$.
Later, we show that $\log(n)/k_{n,a} = \Theta(1)$ for all $a \in [K]$. Hence, it has the same scaling as the bonus used in standard UCB.
Since it depends solely on the local counts $(\tilde N_{k_{n,a},a})_{a \in [K]}$ and the empirical means $(\hat \mu_{k_{n,a}, a})_{a \in [K]}$, the non-private UCB leader is fixed until we switch phase again.

At time $n > K$, the non-private TC challenger is defined as

\begin{equation} \label{eq:non_private_TC_challenger}
C^{\text{NP}}_{n} \defn \argmin_{a \ne B^{\text{NP}}_n} \frac{\hat \mu_{k_{n,B^{\text{NP}}_n}, B^{\text{NP}}_n} -\hat \mu_{k_{n,a}, a} }{\sqrt{1/N_{n, B^{\text{NP}}_n}+ 1/N_{n,a}}} \: .
\end{equation}

While it depends on the empirical means $(\hat \mu_{k_{n,a}, a})_{a \in [K]}$ that are fixed till we switch phase again, it also depends on the global counts $(N_{n,a})_{a \in [K]}$.
Therefore, the non-private TC challenger is chosen in an adaptive manner.
This is the key to obtain guarantees on the expected sample complexity of the non-private algorithm.

We derive upper bounds on the expected sample complexity of the non-private  algorithm in the asymptotic regime of $\delta \to 0$ (Theorem <ref>).
In particular, it shows that the cost of doubling and forgetting is multiplicative four-factor compared to the TTUCB algorithm, which achieves $T_{\mathrm{KL},\beta}^\star(\mu )$ (see Theorem 2.3 in [26]).
We defer its proof to Appendix <ref>.

Let $(\delta, \beta) \in (0,1)^2$.
Combined with the non-private GLR stopping rule (Equation (<ref>)) using non-private threshold functions as in Equation (<ref>), the non-private  algorithm is $\delta$-correct and satisfies that, for all $1$-sub-Gaussian distributions $\model$ with means $\boldsymbol{\mu} \in \R^{K}$ such that $\min_{a \ne b}|\mu_{a} - \mu_{b}| > 0$,

\[
\limsup_{\delta \to 0} \frac{\bE_{\bnu}[\tau^{\text{NP}}_{\delta}]}{\log(1/\delta)} \le 4 T_{\mathrm{KL},\beta}^\star(\mu )  \: ,
\]

where $T_{\mathrm{KL},\beta}^\star(\mu )$ is the $\beta$-characteristic time for Gaussian distributions, such that

\[
2T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})^{-1} \defn \max_{\omega \in \Sigma_K, \omega_{a^\star} = \beta} \frac{(\mu_{a^\star} - \mu_{a})^2}{1/\beta + 1/\omega_{a}}\: .
\]

Private leader/challenger pair.
Since we want to ensure privacy, the non-private leader/challenger pair cannot be used since it relies on the empirical means $\hat \mu_{k_{n,a},a}$, which are not private.
To alleviate this problem, we propose a private leader/challenger pair which is based on the private empirical means $\tilde \mu_{k_{n,a},a}$.

At time $n > K$, the private UCB leader is defined as

\begin{equation} \label{eq:private_UCB_leader}
B_{n} \defn \argmax_{a \in [K]} \left\{\tilde \mu_{k_{n,a}, a} + \sqrt{\frac{k_{n,a}}{\tilde N_{k_{n,a},a}}} + \frac{k_{n,a}}{\epsilon \tilde N_{k_{n,a},a}}\right\} \: ,
\end{equation}

where $k_{n,a}/(\epsilon\tilde N_{k_{n,a},a})$ is a bonus to cope for the uncertainty due to the Laplace noise.
It also depends on the current phase $k_{n,a}$ and has the same scaling as the private UCB indices.
Likewise, the private UCB leader is fixed until we switch phase again.

At time $n > K$, the private Transportation Cost (TC) challenger is defined as

\begin{equation} \label{eq:private_TC_challenger}
C_{n} \defn \argmin_{a \ne B_n} \frac{\tilde \mu_{k_{n,B_n}, B_n} - \tilde \mu_{k_{n,a}, a} }{\sqrt{1/N_{n, B_n}+ 1/N_{n,a}}} \: .
\end{equation}

Likewise, the private TC challenger is chosen in an adaptive manner, which is key to obtain guarantees on the expected sample complexity of the private algorithm.

We derive upper bounds on the expected sample complexity of the private  algorithm in the asymptotic regime of $\delta \to 0$ (Theorem <ref>).
We defer its proof to Appendix <ref>.
thm:sample_complexity[Asymptotic upper bound on expected sample complexity of ]
Let $(\delta, \beta) \in (0,1)^2$.
Combined with the non-private GLR stopping rule (Equation (<ref>)) using non-private threshold functions as in Equation (<ref>), the non-private  algorithm is $\delta$-correct and satisfies that, for all bandit instances $\bnu$ with $1$-sub-Gaussian distributions and means $\boldsymbol{\mu} \in \R^{K}$ such that $\min_{a \ne b}|\mu_{a} - \mu_{b}| > 0$,

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

where $T_{\mathrm{KL},\beta}^\star(\mu )$ is the $\beta$-characteristic time for Gaussian distributions.

§ ANALYSIS OF : PROOF OF THEOREM <REF>

Let $\beta \in (0,1)$, $\epsilon \in \R^{\star}_{+},$ and $\bnu$ be a bandit instance consisting of $K$, $1$-sub-Gaussian distributions with distinct means $\boldsymbol{\mu} \in \R^{K}$, i.e. $\min_{a \ne b}|\mu_{a} - \mu_{b}| > 0$.
For conciseness, we denote $\Delta_{a} \defn \mu_{a^\star} - \mu_{a}$, $\Delta_{\min} \defn \min_{a \ne a^\star} \Delta_{a}$,
and $\Delta_{\max} \defn \max_{a \ne a^\star} \Delta_{a}$.

For Gaussian distributions, the unique $\beta$-optimal allocation $\omega^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) = \{\omega^{\star}_{\beta, a}\}$ is defined as

\begin{equation} \label{eq:beta_optimal_allocation}
\omega^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu}) \defn \argmax_{\omega \in \Sigma_K, \omega_{a^\star} = \beta}  \min_{a \ne a^\star} \frac{\Delta_{a}^2}{1/\beta + 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}
\forall a \ne a^\star, \quad \frac{\Delta_{a}^2}{1/\beta + 1/\omega^{\star}_{\beta,a}} = 2 T^{\star}_{\mathrm{KL},\beta}(\boldsymbol{\mu})^{-1} \: .
\end{equation}

Our proof follows the unified sample complexity analysis of Top Two algorithms from [27].

Let $\gamma> 0$.
We denote by $T_{\boldsymbol{\mu}, \gamma}$ the convergence time towards $\omega^{\star}_{\beta}$, which is a random variable quantifies the number of samples required for the global empirical allocations $N_n/(n-1)$ to be $\gamma$-close to $\omega^{\star}_{\beta}$ for any subsequent time, namely

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

The rest of Appendix <ref> is organised as follows.
First, we prove that  ensures sufficient exploration (Appendix <ref>)
Second, we prove that there is convergence towards the $\beta$-optimal allocation (Appendix <ref>) in finite time.
Finally, we conclude the proof of Theorem <ref> (Appendix <ref>).
In Appendix <ref>, we compare our asymptotic upper bound with our asymptotic lower bound on the expected sample complexity (Theorem <ref>).
In Appendix <ref>, we discuss the limitation of our result and pose an open problem.
Appendix <ref> will detail the slight modification that needs to be made in order to obtain Theorem <ref>.

§.§ Technical results

Before delving into the proofs, we first recall some useful technical results extracted from the literature.

Concentration results.
In order to control the randomness of $(\tilde \mu_{k_{a},a})_{a \in [K]}$, we use a standard concentration result on the empirical mean of sub-Gaussian random variables and on sub-exponential observations (Lemma <ref>).
Since Bernoulli distributions are $1/2$-sub-Gaussian and the absolute value of a Laplace is an exponential distribution, Lemma <ref> applies to our setting.

There exists a sub-Gaussian random variable $W_\mu$ such that, almost surely,

\begin{align*}
\forall a \in [K], \: \forall k_{a} \in \N, \quad |\hat \mu_{k_{a},a} - \mu_a| \le W_\mu \sqrt{\frac{\log (e + \tilde N_{k_{a},a})}{\tilde N_{k_{a},a}}} \: .
\end{align*}

There exists a sub-exponential random variable $W_{\epsilon}$ such that, almost surely,

\begin{align*}
\forall a \in [K], \: \forall k_{a} \in \N, \quad |Y_{k_{a},a}| \le W_{\epsilon} \frac{\log (e + k_{a})}{\tilde N_{k_{a}, a}} \: .
\end{align*}

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

The first part is a known result, e.g. Appendix E.2 in [27].
Let us define

\[
W_{\epsilon} \defn \sup_{a \in [K]}\sup_{k_{a} \in \N} \frac{\tilde N_{k_{a},a}|Y_{k_{a},a}|}{\log(e + k_{a})} \: .
\]

By definition, we have that, almost surely,

\begin{align*}
\forall a \in [K], \: \forall k_{a} \in \N, \quad |Y_{k_{a},a}| \le W_{\epsilon} \frac{\log (e + k_{a})}{\tilde N_{k_{a}, a}} \: .
\end{align*}

Since $\tilde N_{k,i}|Y_{k,i}| \sim \cE(\epsilon )$, Lemma 72 in [27] yields that $W_{\epsilon}$ is a sub-exponential random variable.
Since $W_\mu$ is sub-Gaussian and $W_{\epsilon}$ is a sub-exponential, any random variable which is polynomial in $(W_{\epsilon},W_{\mu})$ has a finite expectation.

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

Let $\overline{W}_{-1}(x) \defn - W_{-1}(-e^{-x})$ for all $x \ge 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}'(x) = \left(1-\frac{1}{\overline{W}_{-1}(x)} \right)^{-1}$ for all $x > 1$.
Then, for all $y \ge 1$ and $x \ge 1$,

\[
\overline{W}_{-1}(y) \le x \quad \iff \quad y \le x - \log(x) \: .
\]

Moreover, for all $x > 1$,

\[
x + \log(x) \le \overline{W}_{-1}(x) \le x + \log(x) + \min \left\{ \frac{1}{2}, \frac{1}{\sqrt{x}} \right\} \: .
\]

Lemma <ref> is an inversion result to upper bound a time, which is implicitly defined.
It is a direct consequence of Lemma <ref>.

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

\begin{align*}
&C(A, B) = \sup \left\{ x \mid \: x < A \log x + B \right\} \: .
\end{align*}

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

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

\[
C(A, B) = \sup \left\{ x \mid \: x < A \log (x) + B \right\} = \sup \left\{ x \ge A \mid \: x < A \log (x) + B \right\} \: .
\]

Using Lemma <ref> yields that

\begin{align*}
x \ge A \log x + B  \: \iff \: \frac{x}{A} - \log \left( \frac{x}{A} \right) \ge \frac{B}{A} + \log A \: \iff \: x \ge A \overline{W}_{-1} \left( \frac{B}{A} + \log A \right) \: .
\end{align*}

§.§ Sufficient exploration

The first step of in the generic analysis of Top Two algorithms [27] is to show that  ensures sufficient exploration.
The main idea is to show that, if there are still undersampled arms, either the leader or the challenger will be among them.
Therefore, after a long enough time, no arm can still be undersampled.
We emphasise that there are multiple ways to select the leader/challenger pair in order to ensure sufficient exploration.
Therefore, while we conduct the proof for , other choices of leader/challenger pair would yield similar results.

Given an arbitrary phase $p \in \N$, we define the sampled enough set, i.e. the arms having reached phase $p$, and the arm with highest mean in this set (when not empty) as

\begin{equation} \label{eq:def_sampled_enough_sets}
S_{n}^{p} = \{a \in [K] \mid N_{n,a} \ge 2^{p-1} \} \quad \text{and} \quad a_n^\star = \argmax_{a \in S_{n}^{p}} \mu_{a} \: .
\end{equation}

Since $\min_{a \neq b}|\mu_a - \mu_b| > 0$, $a_n^\star$ is unique.

Let $p \in \N$ such that $(p-1)/4 \in \N$.
We define the highly and the mildly under-sampled sets as

\begin{equation} \label{eq:def_undersampled_sets}
U_n^p \defn \{a \in [K]\mid N_{n,a} < 2^{(p-1)/2} \} \quad \text{and} \quad V_n^p \defn \{a \in [K] \mid N_{n,a} < 2^{3(p-1)/4}\} \: .
\end{equation}

They correspond to the arms having not reached phase $(p-1)/2$ and phase $3(p-1)/4$, respectively.

Lemma <ref> shows that, when the leader is sampled enough, it is the arm with highest true mean among the sampled enough arms.

Let $S_{n}^{p}$ and $a_n^\star$ as in (<ref>).
There exists $p_0$ with $\bE_{\bnu}[\exp(\alpha p_0)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_0$, for all $n$ such that $S_{n}^{p} \neq \emptyset$, $B_{n} \in S_{n}^{p}$ implies that $B_{n} = a_n^\star = \argmax_{a \in S_{n}^{p}} \tilde \mu_{k_{n,a},a} $.

Let $p_{0}$ to be specified later.
Let $p \ge p_0$.
Let $n \in \N$ such that $S_{n}^{p} \ne \emptyset$, where $S_{n}^{p}$ and $a_n^\star$ as in Equation (<ref>).
Let $(k_{n,a})_{a \in [K]}$ be the phases indices for all arms.
Since $N_{n,a} \ge 2^{p-1}$ for all $a \in S_{n}^{p}$, we have $k_{n,a} \ge p$ and $\tilde N_{k_{n,a},a} \ge 2^{p-2}$ by using Lemma <ref>. Using	Lemma <ref>, we obtain that

\begin{align*}
\tilde \mu_{k_{n,a_n^\star}, a_n^\star} &\ge \mu_{a_n^\star} - W_{\mu} \sqrt{\frac{\log(e+2^{p-2})}{2^{p-2}}} - W_{\epsilon}  \frac{\log(e+p)}{2^{p-2}} \: , \\
\tilde \mu_{k_{n,a},a}  &\le  \mu_{a} + W_{\mu} \sqrt{\frac{\log(e+2^{p-2})}{2^{p-2}}} + W_{\epsilon}  \frac{\log(e+p)}{2^{p-2}} \: ,\quad \forall a \in S_{n}^{p} \setminus \{ a_n^\star \}.
\end{align*}

Here, we use that $x \to \log(e + x)/x$ is decreasing.

Let $\overline \Delta_{\min} = \min_{a \ne b} |\mu_{a} - \mu_{b}|$. By assumption on the considered instances, we know that $\overline \Delta_{\min} > 0$.
Let $p_{1} = \lceil \log_2 (X_{1}-e) \rceil + 2$ and $ p_2 = \lceil \log_2 ( (X_{2} - e  -2)\log 2  +  1) \rceil + 2$ with

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

where we used Lemma <ref>, and $h_{1}$ defined therein.
Then, for all $p \in \N $ such that $p \ge \max\{p_1, p_{2}\} + 1$ and all $n \in \N$ such that $S_{n}^{p} \ne \emptyset$, we have $\tilde \mu_{k_{n,a_n^\star}, a_n^\star} \ge \mu_{a_n^\star} - \overline\Delta_{\min}/4$ and $\tilde \mu_{k_{n,a},a}  \le  \mu_{a} + \overline\Delta_{\min}/4$ for all $a \in S_{n}^{p} \setminus \{ a_n^\star \}$, hence $a_n^\star = \argmax_{a \in [K]} \tilde \mu_{k_{n,a},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_{+}$.

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

\begin{align*}
& I_{k_{n,a_n^\star},a_n^\star} \ge \mu_{a_n^\star} - W_{\mu} \sqrt{\frac{\log(e+2^{p-2})}{2^{p-2}}} - W_{\epsilon}  \frac{\log(e+p)}{2^{p-2}}  \: , \\
\forall a \in S_{n}^{p} \setminus \{ a_n^\star \}, \quad  & I_{k_{n,a},a}  \le  \mu_{a} + W_{\mu} \sqrt{\frac{\log(e+2^{p-2})}{2^{p-2}}} + W_{\epsilon}  \frac{\log(e+p)}{2^{p-2}} + \sqrt{\frac{p}{2^{p-2}}} + \frac{p}{\epsilon 2^{p-2}} \: ,
\end{align*}

where we used Lemma <ref> and the fact that $x \to \log(e + x)/x$ and $x \to x 2^{2-x}$ are decreasing function for $x \ge 2$.
Let $p_{3} = \lceil \log_2 X_{3} \rceil + 2$ and $ p_{4} = \lceil \log_2 X_{4} \rceil + 2$ with

\begin{align*}
X_{3} &= \sup \left\{ x > 1 \mid \: x \le 64 \overline\Delta_{\min}^{-2} ( \log_{2} x + 2) \right\} \le h_{1} ( 64 \overline\Delta_{\min}^{-2}/\log 2 ,\: 128 \overline\Delta_{\min}^{-2}) \: , \\
X_{4} &= \sup \left\{ x > 1 \mid \: x \le 8 \epsilon^{-1}\overline\Delta_{\min}^{-1}   ( \log_{2} x + 2) \right\} \le h_{1} ( 8 \epsilon^{-1}\overline\Delta_{\min}^{-1} / \log 2,\:  16 \overline\Delta_{\min}^{-1} \epsilon^{-1}) \: ,
\end{align*}

where we used Lemma <ref>, and $h_{1}$ defined therein.
We highlight that $(p_{3}, p_{4})$ are deterministic values, hence their expectation is finite.
Then, for all $p \in \N $ such that $p \ge p_{0} = \max\{p_{1}, p_{2}, p_{3}, p_{4}\} + 1$ and all $n \in \N$ such that $S_{n}^{p} \ne \emptyset$, we have $I_{k_{n,a_n^\star},a_n^\star} \ge \mu_{a_n^\star} - \overline\Delta_{\min}/4$ and $I_{k_{n,a},a}   \le  \mu_{a} + \overline\Delta_{\min}/2$ for all $a \in S_{n}^{p} \setminus \{ a_n^\star \}$, hence $a_n^\star = B_n$ since we have $B_n = \argmax_{a \in [K]} I_{k_{n,a},a} $.

Since we have $\bE_{\bnu}[\exp(\alpha p_{0})] < + \infty$ for all $\alpha \in \R_{+}$, this concludes the proof.

Lemma <ref> shows that the transportation costs between the sampled enough arms with largest true means and the other sampled enough arms are increasing fast enough.

Let $S_{n}^{p}$ and $a_n^\star$ are as in Equation (<ref>).
There exists $p_1$ with $\bE_{\bnu}[\exp(\alpha p_1)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_1$, for all $n$ such that $S_{n}^{p} \neq \emptyset$, for all $b \in  S_{n}^{p} \setminus \{a_n^\star\} $, we have

\[
\frac{\tilde \mu_{k_{n,a_n^\star},a_n^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,a_n^\star}, a_n^\star}+ 1/\tilde N_{k_{n,b},b}}} \geq  2^{p/2} C_{\mu} \: ,
\]

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

Let $p_{1}$ to be specified later.
Let $p \ge p_1$.
Let $n \in \N$ such that $S_{n}^{p} \ne \emptyset$, where $S_{n}^{p}$ and $a_n^\star$ as in Equation (<ref>).
Let $(k_{n,a})_{a \in [K]}$ be the phases indices for all arms.
Since $N_{n,a} \ge 2^{p-1}$ for all $a \in S_{n}^{p}$, we have $k_{n,a} \ge p$ and $\tilde N_{k_{n,a},a} \ge 2^{p-2}$ by using Lemma <ref>.
Let $\overline \Delta_{\min} = \min_{a \ne b} |\mu_{a} - \mu_{b}|$, which satisfies $\overline \Delta_{\min} > 0$ by assumption on the instance considered.

Using	Lemma <ref>, for all $b \in S_{n}^{p} \setminus \{ a_n^\star \}$, we obtain

\begin{align*}
&\tilde \mu_{k_{n,a_n^\star}, a_n^\star} - \tilde \mu_{k_{n,b},b} \ge \overline \Delta_{\min} - W_{\mu} \sqrt{\frac{\log(e+2^{p-2})}{2^{p-4}}} - W_{\epsilon}  \frac{\log(e+p)}{2^{p-3}} \: .
\end{align*}

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

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

where we used Lemma <ref>, and $h_{1}$ defined therein.
Then, for all $p \in \N $ such that $p \ge p_{1} = \max\{p_{3}, p_{2}\} + 1$ and all $n \in \N$ such that $S_{n}^{p} \ne \emptyset$, we have, for all $b \in S_{n}^{p} \setminus \{ a_n^\star \}$,

\begin{align*}
&\tilde \mu_{k_{n,a_n^\star}, a_n^\star} - \tilde \mu_{k_{n,b},b} \ge  \overline \Delta_{\min} /2\: .
\end{align*}

As in the proof of Lemma <ref>, we obtain that $\bE_{\bnu}[\exp(\alpha p_{1})] < + \infty$ for all $\alpha \in \R_{+}$.

Then, for all $b \in S_{n}^{p} \setminus \{ a_n^\star \}$, we have

\[
\frac{\tilde \mu_{k_{n,a_n^\star},a_n^\star} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,a_n^\star}, a_n^\star}+ 1/\tilde N_{k_{n,b},b}}} \ge 2^{p/2} \frac{\overline\Delta_{\min}}{2^{5/2}}   \: ,
\]

where we used that $\min\{\tilde N_{k_{n,a_n^\star}, \tilde N_{k_{n,b},b}}\} \ge 2^{p-2}$.
Setting $C_{\mu} = \overline \Delta_{\min} /2^{5/2}$ yields the result.

Lemma <ref> shows that the transportation costs between sampled enough arms and undersampled arms are not increasing too fast.

Let $S_{n}^{p}$ be as in Equation (<ref>).
For all $p \ge 1$ and all $n$ such that $S_{n}^{p} \neq \emptyset$

\[
\forall a \in S_{n}^{p} , \: \forall b \notin  S_{n}^{p} , \quad \frac{\tilde \mu_{k_{n,a},a} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,a}, a}+ 1/\tilde N_{k_{n,b},b}}} \leq  2^{p/2} D_{\mu} +  2W_{\mu}\sqrt{\log(e + 2^{p-2})} + 2W_{\epsilon} \log(e+p) \: ,
\]

where $D_{\mu} > 0$ is a problem dependent constant and $(W_\mu, W_{\epsilon})$ are the random variables defined in Lemma <ref>.

Let $p \ge 1$.
Let $n \in \N$ such that $S_{n}^{p} \ne \emptyset$, where $S_{n}^{p}$ as in Equation (<ref>).
Let $(k_{n,a})_{a \in [K]}$ be the phases indices for all arms.
Since $N_{n,a} \ge 2^{p-1}$ for all $a \in S_{n}^{p}$, we have $k_{n,a} \ge p$ and $\tilde N_{k_{n,a},a} \ge 2^{p-2}$ by using Lemma <ref>.
Likewise, $N_{n,a} < 2^{p-1}$ for all $a \notin S_{n}^{p}$, we have $k_{n,a} < p$ and $\tilde N_{k_{n,a},a} < 2^{p-2}$.
Let $\overline \Delta_{\max} = \min_{a \ne b} |\mu_{a} - \mu_{b}|$, which satisfies $\overline \Delta_{\max} > 0$ by assumption on the instance considered.
Using	Lemma <ref>, for all $a \in S_{n}^{p}$ and $b \notin S_{n}^{p}$, we obtain

\begin{align*}
\frac{\tilde \mu_{k_{n,a},a} - \tilde \mu_{k_{n,b},b}}{\sqrt{1/\tilde N_{k_{n,a}, a}+ 1/\tilde N_{k_{n,b},b}}} &\le \sqrt{\tilde N_{k_{n,b},b}}(\tilde \mu_{k_{n,a},a} - \tilde \mu_{k_{n,b},b}) \\
&\le \sqrt{\tilde N_{k_{n,b},b}}(\mu_{a} - \mu_{b}) + 2W_{\mu}\sqrt{\log(e + \tilde N_{k_{n,b},b})} + 2W_{\epsilon} \frac{\log(e+k_{n,b})}{\sqrt{\tilde N_{k_{n,b},b}}} \\
&\le 2^{(p-2)/2} \overline \Delta_{\max} +  2W_{\mu}\sqrt{\log(e + 2^{p-2})} + 2W_{\epsilon} \log(e+p)
\end{align*}

where we used that $\tilde N_{k_{n,b},b} \ge 1$, $k_{n,b} < p$, $\tilde N_{k_{n,b},b} < 2^{p-2} \le \tilde N_{k_{n,a},a}$ and $x \to \log(e + x)/x$ is decreasing.
Taking $D_{\mu} = \overline \Delta_{\max}/2$ yields the result.

Lemma <ref> shows that the challenger is mildly undersampled if the leader is not mildly undersampled.

Let $V_{n}^{p}$ be as in Equation (<ref>).
There exists $p_2$ with $\bE_{\bnu}[\exp(\alpha p_2)] < +\infty$ for all $\alpha > 0$ such that if $p \ge p_2$, for all $n$ such that $U_n^p \neq \emptyset$, $B_{n} \notin V_{n}^{p}$ implies $C_{n} \in V_{n}^{p}$.

Let $p_{2}$ to be specified later.
Let $p \ge p_{2}$.
Let $n \in \N$ such that $U_n^p \neq \emptyset$ and $V_{n}^{p} \ne [K]$, where $U_{n}^{p} \subseteq V_{n}^{p}$ are defined in Equation (<ref>).
In the following, we suppose that $B_{n} \notin V_{n}^{p}$.

Let $(k_{n,a})_{a \in [K]}$ be the phases indices for all arms.
Let $p_{0}$ as in Lemma <ref>.
Let $b_n^\star = \argmax_{ b \notin V_{n}^{p}} \mu_{b}$.
Then, for all $p \ge 4p_{0}/3 -1/3$ and all $n$ such that $B_{n} \notin V_{n}^{p}$, Lemma <ref> yields that $B_{n} =  b_n^\star = \argmax_{a \notin V_{n}^{p} } \tilde \mu_{k_{n,a},a} $.

Let $p_{1}$ and $C_{\mu}$ as in Lemma <ref>, and $D_{\mu}$ as in Lemma <ref>.
Then, for all $p \ge 4\max\{p_{0}, p_{1}\}/3 -1/3$ and all $n$ such that $B_{n} \notin V_{n}^{p}$, we have $B_{n} =  b_n^\star $ and

\begin{align*}