On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence
Authors: Achraf Azize
Marc Jourdan
Aymen Al Marjani
Debabrota Basu
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy
Multi-armed Bandits
Best Arm Identification
Fixed Confidence
TL;DR: We derive sample complexity lower bound and design an algorithm with matching upper bound for differential privacy-preserving best arm identification with fixed confidence.

Abstract: 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 AdaP-TT, an $\epsilon$-global DP variant of the Top Two algorithm. AdaP-TT 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 AdaP-TT that matches with the lower bound up to multiplicative constants in the high-privacy regime. Finally, we provide an experimental analysis of AdaP-TT that validates our theoretical results.

On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence
Achraf Azize
Mare Jourdan
Équipe Scool, Univ. Lille, Inria,
Equipe Scool, Univ. Lille, Inria.
CNRS, Centrale Lille, UMR 9189- CRISIAL
CNRS, Centrale Lille, UMR 9189- CRISIAL
F-59000 Lille, France achraf azize@inria.fr
F-59000 Lille, France
marc m www.jjrddniniii......
Aymen Al Marjani UMPA, ENS Lyon Lyon, France
Debabrota Basu
Équipe Scool, Univ. Lille, Inria,
CNRS, Centrale Lille, UMR 9189- CRIStAL
aymen al aal_marjjai@emn -1yon.
F-59000 Lille, France debabrota. basu@inria.fr
Abstract
Best Arm Identification (BAI) problems are progressively used for data-sensitive applications, such designing adaptive clinical trials, tuning hyper-parameters, and conducting user studies to name few. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence under e-global Differential Privacy (DP). First, to quantify the cost of privacy, we derive lower bound on the sample complexity of any ò-correct BAI algorithm satisfying c-global DP. Our lower bound suggests the existence of two privacy regimes depending on the privacy budget c. In the high-privacy regime (small c), the hardness depends on coupled effect of privacy and a novel information- theoretic quantity, called the Total Variation Characteristic Time. the low-privacy regime (large e), the sample complexity lower bound reduces to the classical non- private lower bound. Second, we propose AdaP-TT, an e-global DP variant of the Top Two algorithm. AdaP-TT runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utilig trade-off. We derive an asymptotic upper bound on the sample complexity of AdaP-TT that matches with the lower bound up to multiplicative constants in the high-privacy regime. Finally, we provide experimental analysis of AdaP-TT that validates theoretical results.
Introduction
We study the stochastic multi-armed bandit problem [LS20], which allows us to reflect on fundamental information-utillis trade-offs involved interactive sequential learning. Specifically, in a bandit prob- lem, learning agent is exposed to interact with K unknown probability distributions {u)...., with bounded expectations, referred the reward distributions (or arms). A (VI...., Mx is called a bandit instance. distributions VA, for an A, [K], and obtains a sample (or reward) 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 called the regret-mining sggretmmiiiiistion problem [ACBF02], while the second one is called the Best Arm
every step > O, the agent chooses to interact with one of the reward
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Identification (BAI) problem [KCG16]. In this paper, we focus on the BAI problem, i.e. to compute
a² - arg max E rovMa
[r] é arg max pla- nE[R]
(BAI)
[E[K]
With its advent in 1950s [Bec54, Bec58] and resurgence in last two decades [MT04, GGL12, JMNB14, KCG16, DKM19), BAT has been extensively studied with different structural assump- tions (Fixed-confiddecce: [JN14]; Fixed-budget: [CL16]; Non-stochastic: [JT16]; Best-of-both- worlds: [AYBG* 18]; Linear: [SLM14]). In this paper, we specifically investigate the Fixed Con- fidence BAI problem, in brief FC-BAI, that yields a 6-correct recommendation á E [K] satisfying Pr(a j a²) S 5. FC-BAI is increasingly deployed for different applications. such as clinical trials [AKR21], hyper-parameter tuning [LJD+17], communication networks [LPJ22], online ad- vertisement [CLK* 14), crowd- crowd-sourcing [ZCL14], user studies [LEHT22], and pandemic mitiga- tion [LVR + 19] to name few. All of these applications often involve the sensitive and personal data of users, which raises serious data privacy concerns ITBD 16], as illustrated in Example 1.
Example (Adaptive dose finding trial). In a dose-finding trial, one physician decides K possi- ble dose levels of a medicine based on preliminary studies (Typically, K E (3...., 10.} in prac- tice [AKR2I]). At each step t. a patient is chosen from a local pool of volunteers and a dose level a, E [ is applied to the patient. Following that, the effectiveness of the dose on the patient, i.e. Te E R 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 's reaction to it exposes information regarding the medical conditions of the patient. Additionally, at each step I of an adaptive sequential trial, the physician can use an FC-BAI algorithm that observes the previous history of dose levels ) and their effectiveness {ra}act to decide the next dose level at 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 {as}act and the final recommended dose level a". Thus, even if the sequence of reactions to doses {r' {r=}ase e is kept secret, publishing the sequence of chosen dose levels ) and the final recommended dose level a* 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 algorithum in FC-BAI. Specifically, we use the celebrated Differential Privacy (DP) [DR 14] as the framework to preserve data privacy. DP ensures that an algorithm's 's output is unaffected by changes in input by 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 calibrated amount of noise, from a Laplace [DR14] or Gaussian distribution [DRS22], into the algorithm. The scale of the noise set to be proportional to the algorithm's sensitivity and inversely proportional to the privacy budget e. Specifically, we study e-global DP, where users trust the centralised decision-maker with access to the raw sensitive rewards. For example, in an adaptive dose- fesse-finiig trial, the patients trust the physician conducting the trial. Thus, at any time t, she has access to all the true history (a.:Ta Fa]sct, and it is her duty to design an algorithm such that publishing {ag} best and the recommended optimal dose a" obeys c-PP given the sensitive input, i.e. the effectiveness of the dose levels on the patients (ralesi. We define the notion of e-global DP for BAI rigorously in Section 2.
For different settings of bandits, the cost of e-global DP and optimal algorithm design techniques are widely studied in the regret-minimization problem [MT15, 5, TD16, SS19, SS18, NR18, BDT19, AB22J. Recently, a problem-dependent lower bound on regret of stochastic multi-armed bandits with e-global DP and an algorithm matching the regret lower bound is proposed by [AB22]. In contrast, DP is meagerly studied in the FC-BAI problem of bandits [SS19, KNSS21J. 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-B BAI satisfying e-global DP. Here, by an 'efficient' algorithm, refer to the FC-BAI algorithms that aim to minimise the expected number of samples required (alternatively called, expected stopping time) to find 5-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, aim to address two questions:

---

1. What is the fundamental hardness of ensuring Differential Privacy in the Best-Arm Identification with fixed confidence problem -F-DP--C--BA) in terms of a lower bound on the sample complexity?
2. How to design an efficient C-DP-FC-BAL algorithm that achieves the lower bound order-optimally?
Our contributions. These questions have led to the following contributions:
Hardness as lower bounds: We commence our study by deriving the lower bound on sample complexity (or expected stopping time) of any FC-BAl algorithm ensuring e-global DP, in brief c-DP-FC-BAI (Section 3). In Theorem 2, we prove that the sample complexity of c-DP-FC-BAI depends on the minimum of two information-theoreee other that originates from the elassical sample complexity of non-private FC-BAI [KCG16]. The term quantity,
quantities one that depends on privacy, and the
dependent on privacy depends on the privacy budget e, and a novel referred to as the Total Variation Characteristic Time Tiv. Tiv 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 similar spirit as the regret minimisation with e-global DP [AB22], there are two regimes of hardness for --DP-CC-BAL For lower level of privacy (i.e. higher e), the sample complexity of e-DP-FC-BAI is identical to that of the non-private FC-BAI. But for higher level of privacy (i.e. lower e), the sample complexity depends on and Tyy-
intommation-thorreee
2. Algorithmm design: Following the lower bounds, we aim to design an efficient B--P-FC-BAI algorithm that simultancously achieves the lower bound order-optimally and is computationally efficient (Section 4). Due to the superior empirical performance and computational efficiency of Top Two algorithms, we design an c-DP variant of Top Two algorithms, named AdaP-TT. Specifically, we show two simple design techniques, i.e. adaptive episodes for each arm and Laplacian mechanism, if properly used, lead to AdaP-TT from the non-private TTUCB [JD22]. We further derive an asymptotic (as - 0) upper bound on the sample complexity of AdaP-TT (Theorem 5). In the high-privacy regime, the sample complexity upper bound of AdaP-TT coincides with the lower bound up to multiplicative constants. Thus, it is an order-optimal e- E-DP-FC-BAI algorithm in this regime, whereas the looseness in the low- cow-privacy regime is same the looseness of the non- non-private Top Two algorithm. In Section 5, we experimentally show that AdaP-TT is more sample efficient than the existing e- DD-FCC-BLL algorithm, i.c. DP-SE [SS19]. 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 e-global DP version of the transportation lemma [KK13] (Lemma 1), which we prove using a sequential coupling argument. We also define and study the TV characteristic time (TTy) quantifying the hardness of FC-BAI in high privacy regimes (Proposition 1). (b) To design the algorithm, we propose a generic wrapper, which adapts the existing FC-BAl 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 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-BAL 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 the performance of the algorithm. Building on [JDB D22,, we provide a generic analysis of the class of Top Two algorithms when combined with our wrapper.
1.1 Related works
Lower bound. Efficient algorithm design in BAI literature is propelled by the derivation of lower bounds on sample complexity. [KCG16] derive the first lower bounds for classical fixed-confidence BAI setting without privacy, which is further improved in [GK16] by introducing KL characteristic time TŽ (Corollary 1). Motivated by this, we prove the first-known lower bound on sample complexity for FC-BAI with c-global DP (Theorem 2). The proof employs similar sequential coupling argument as in the regret lower bound for bandits with c-global DP [SS18, AB22]. This similarity is also reflected in the existence of two privacy regimes depending on the privacy budget c. And for both measure that captures
lower bounds, the Total Variation (TV) appears to be the the hardness in the high privacy regime. Specifically, the TV characteristic time (Ttv. Corollary 1) serves as the BAT counterpart to the -i-distinguishabiiity gap (4inf) in the problem-dependen regret lower bound for bandits with e-global DP as in [AB22, Thcorem 3].
3

---

Algorithms for BAI with fixed confidence (FC-BAI). The optimal sample complexity for the non-private FC-BAI problem (i.e., T ) is well-understood [GK16], and algorithms are proposed with the aim to achieve this lower bound. Farly approaches involved Successive Elimination (SE) based algorithms [EDMMM06] 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 [GGLI2]. However, neither SE nor LUCB algorithms achieve asymptotic optimality. The Track-and-Soe (TnS) algorithm introduced in [GKI6] was the first to asymptotically achieve the exact optimal sample complexity TKL. TnS attains asymptotic optimality by solving plug-in in estimate of the lower bound optimization problem at each step. The game- based approach presented in [DKM19] 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 [Rus16]. In recent years, numerous variants have been analyzed and shown to be asymptotically near optimal [JDB+22]. At every step, a Top Two sampling rule selects the next to sample from among two candidate arms, leader and a challenger. In addition to their great empirical performance, and easy implementation compared to TnS and Base-based algorithms, the Top Two algorithms achieve near asymptotic optimality. In Sec. 4, we derive an e-global DP version of a Top Two algorithm: AdaP-TT.
c-DP BAI algorithms. DP-SE [SS19] is an e-global DP version of the Successive Elimination algorithm. Although the algorithm was proposed and analysed for the regret minimisation setting in [SS19], it is possible to derive sample complexity from the analysis in [SS19]. We compare in-depth DP-SE and AdaP-TT, both theoretically (Section 4) and experimentally (Section 5). In both aspects, our proposed algorithm AdaP-TT outperforms DP-SE. Another adaptation of DP-SE, namely DP-SEQ, is proposed in [KNSS21] for the problem of privately finding the arm with the highest quantile at a fixed level. But this different setting of interest than the present paper. [RBCS23] also studies privacy for BAI under fixed confidence but with multiple agents. They propose and analyse the sample complexity of DP-MASE, 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 simultancously, we study the single-agent setting, which is relevant for many small-scale clinical trials (see Example 1).
2 Differential privacy and best arm identification
Background: Differential Privacy (DP). DP ensures protection of an individual's 's sensitive infor- mation 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 's data is included in or excluded from the input. This is achieved by adding controlled noise to the algorithm's 's output.
Definition ((e, DD [DR14J). A randomised algoritimm A satisfies (e, 8)-ffferrenti Privacy (DP) if for any two neighbouring datasets 'D and 'D' that differ only in one entry, iee. ditm (D, D') = 1, and for all sets of output O C RRano([A),
Pr(A(D) E 0l =E E O
(1)
where the probability space is over the coin flips of the mechanism A, and for some (e, 8) e R20 R20 If 5 O. we say that A satisfies cDDP. A lower privacy budget implies higher privacy.
The Laplace mechanism [DNPR10, DR14] ensures cDP by injecting controlled random noise into the output of the algorithm, which is sampled from calibrated Laplace distribution (as specified in Theorem 1). We use Lap(b) to denote the Laplace distribution with mean 0 and variance 262.
Theorem 1 (E-DP of Laplace mechanism (Theorem 3.6, [DR14)). Let us consider an algorithm (PD) - ((D))1 Here, I1-111 is the L
f + Rdd with sensitivity s(J)= 2
max D,D' aa (D-D' Hamming==
d norm on Rd. If d noise samples {Nv.) are generated independently from Lap (s()) then the output injected with the noise, i.e. ((D) + [Ni....,NNa Na), satisfies c-P)..
Background: BAI with fixed confidence. Now, we describe the canonical best-arm identification problem with fixed confidence (FC-BAI). BAI is variant of pure exploration, where the goal is to

---

Algorithm Sequential interaction between a BAI strategy and users
1: Input: A BAI strategy (S,, Rec))121 and Users {ur h21 represented by the table d
2: Output: A stopping time т, sequence of samples actions a² (a),..., (r) and a recommen-
dation à satisfying e-global DP
3: for = 1.... do
4: recommends action a, Sc(. (L
5: if' a, = then
6: Halt. Return i and à ~ Rocy "aa.f,...,,.111111
7: else
8: 14 sends the sensitive reward ry d di, to
9: end
10:
end for
identify the optimal arm. FC-BAI, the learner is provided with a confidence level 8 E (0, 1) Learner aims to recommend an arm that is optimal with probability at least 1 - 5, while using as few samples as possible. To achieve this, the learner defines FC-BAI strategy to interact with the bandit instance V (va E [K]]. We denote the action played at step / by ar, and the corresponding observed reward by Tt nu Pay H, (a1, rl,, at, Fr) is the history of actions played and rewards collected until time t. We augment the action set by stopping action T, and write a; T to denote that the algorithm has stopped before step t. A FC-BAI strategy π is composed of
i. A pair of sampling and stopping rules (S, H + P[]I,, U (2)) For an action e [K], S, (a 11 denotes the probability of playing action given history Hz-1- On the other hand, S. (T (1,-)) the probability of the algorithm halting given He- For any history H:- I. consistent sampling and stopping rule S, satisfies S, (T H4-1) = 1 if has been played before t.
ii A recommendation rule (Rec, H4-1 + P([I1, Ki))ss A recommendation rule dictates Rec, (a H4-1), i.e. the probability of returning action
guess for the best action given H
We denote by T the stopping time of the algorithm, i.c. the first step f demonstrating d; = =, A BAI strategy π is called d-correct for class of bandit instances M, if for every instance V E M, и recommends the optimal action a" (w) = arg ma Po with probability at least
i.e.
P2, < 6 a" (v)) 2
FC-BAI with c-global DP (-DP-FC-BAD) Now, we formally define c-global DP for FC-BAI, where the BAI strategy ka. the centralised decision maker) is trusted with all the intermediate rewards. We represent each user u, by the vector x, A (It,1...., FT,K) E R where dr, represents potential reward observed, if action a was recommended to user u, Due to the bandit feedback, only r, = Tt.a, ~ Va, observed at step l. We use an underline to denote any sequence. Thus, we denote the sequence of sampled actions until T as a (a1.-. (d...... ar). We further represent a set of users {ue)== until by the table potential rewards d= A (xI....., X1 E (R*)T, First, we observe that d" the sensitive input generated through interaction with the users, and (a" a 7) is the output of the BAI strategy. Hence, we define the probability that the BAI strategy samples the action sequence a", recommends the action ā and halts at time T, as
T
(aa ".", Reer+1 (@) Hr) Sr+1 (T Hr) II
St (a, H4-1)
(2)
where T users under interaction are represented by the table of potential rewards d"
Thus, BAI strategy satisfies e-global DP if the probability defined in Eq. (2) is similar when the BAI strategy interacts with two neighbouring tables of rewards differing by a user (i.c. row in d Definition 2 (e-global DP for BAI). BAI strategy satisfies e-global DP, for all 2 1, all neighbouring lable of rewards d' and d' i.e. d a 1, all sequences of sampled actions a" E [K and recommended uctions ā E [K] we have that
Taa a.T d²) S a,T
'We remind not to confuse risk level ó with the é of (c,8)-DP Hereafter, we consider e-global DP as the privacy definition, and 5 always represents the risk (or probability of mistake) of the BAI strategy.
5

---

Definition 2 can be seen as a BAI counterpart of the e-global DP definition proposed in [AB22] for regret minimization. We demonstrate the BAI strategy- Sustesy-UUsess interaction Algorithm 1.
Remark 1. It is possible to consider that the output of a BAI strategy is only the final recommended action i.e. not publishing the intermediate actions a² This gives a weaker definition of privacy compured to Defimition 2, since the latter defends against adversaries that may look inside the execution of the BAI strategy, i.e. pan-pra pan-privacy [DNP* 10]. In addition, Definition needed in practice. For example, in the case of dose-finding (Example 1), the experimental protocol, i.e. the intermediate actions, needs to be published too.
The goal in c-DP-FC-BAl is to design a d-correct e-global DP algorithm, with 7 as small as possible.
3 Lower bound on sample complexity for FC-BAI with e-global DP
The central question that we address in this section is
How many additional samples a BAI strategy must select for ensuring e-global DP?
In response, we prove lower bound on the sample complexity of any ó-correct c-DP BAI strategy. Our lower bound features problem- dependent characteristic times reminiscent of the FC-BAI setting.
Let - (va a E [K] be a bandit instance, consisting of K arms with finite means (Ma [E[]]- Now, we define the set of alternative instances as Alt(z) & {A : a" (A) # a" (v)}. i.. the bandit instances with different optimal arm than v. For two probability distributions P, Q on the same measurable space (S2 F), the Total Variation (TV) distance is defined as TV (IP) || Q) _ SuPAEF(P(A)) Q(A))
while the KL divergence (or relative entropy) is KL (IP
f log dP (W)) dP(w), when IP < Q
and oc otherwise. We denote the probability simplex by Σx - {w E [0, 1] Ex = 13.
First, we derive an e-global DP variant of the 'transportation' lemma, i.e. Lemma 1 in [KCG16]. Lemma 1 (Transportation lemma under e-global DP). Let 8 E (0, 1) and > O. Let be bandit instance and À E Alt(v). For any 8-correct e-global DP BAI strategy, we have that
K
6E
En, [V (Vo Aa) 2 kl(1-
where kl(1 5) - log (1- (1-x))ogg 1 foro,y x, (0.
Proof sketch. We use Sequential Karwa- Vadhan Lemma [AB22, Lemma 2] with data- prote-procsssigg inequality in the BAI canonical model. Extra care is needed to deal with the stopping times in the coupling, compared a fixed horizon T regret minimization. The proof is deferred to Appendix B.
Karwa-Vadhan
Leveraging Lemma 1, we derive a sample complexity lower bound for any e-DP-FC-BAI strategy.
Theorem 2 (Sample complexity lower bound for e-DP-FC-BAI. Let 8 E (0, 1) and e > 0. For any 8-correct c-global DP BAI strategy, we have that
Ex 2 T (v:6) log(1 (135),
(3)
where (T* (v: &
sup inf min [E=]wake WaKL (va 1l Xa). 66 E W. TV (va Ao)). WEEx XEAl((v)
Comments on the lower bound. Similar to the lower bound for the non-private BAI [GK16], 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 À close to v in order to confuse MAX. The latter plays an allocation divergence between v and the confusing instance À 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 e-global DP constraint. The proof is deferred to Appendix B. In order to compare the lower bound of e-global BAI strategy with the non- non-private lower bound of [GK16]] we relax Theorem 2 to further derive a simpler bound, as in Corollary 1. Corollary 1. For any d-correct e-global DP BAI strategy, we have that
Σx to explore the different arms, with the purpose of maximising the
Er[T] Z max (k),(V) 1
(Tvv(e)) log(1/33) 6e
where (V)) suPweEk in infxEAlu()) EK worluar da), and d is either KL or TV.

---

Proof. The proof is direct by observing that T (w:c) 2 (V) and T (w;E) 2 1 Tiv().. 6e
Comparison with the non-private lower bound. TKL. is the characteristic time the non- non-private lower bound [6K and refer to Section 2.2 of [GK16] for a detailed discussion its properties. The sample complexity lower bound suggests the existence of two hardness regimes depending on TkL and Tiv- (1) Low-privacy regime: When
/TTvw>((6T) (V)). the lower bound retrieves the non-private lower bound, i.e. T (v), and thus, privacy can be achieved for free. (2) High-privacy regime: When < Tiv(1)) ( (2)), the lower bound becomes Tiv/ (6c) and c-global DP 5-BAI requires more samples than non-private ones.
In the following proposition, we characterise Tiv for Bernoulli instances. Proposition 1 (TV characteristic time for Bernoulli instances). Let be a bandit instance, i.e. such that Va Bernoulli(ua) and jni > μ22 2 PK. Let Da - jui pa and Amia minage An-
We have that
K
K
Tiv(w)= = Amin
and
S (Tv(())
Aa
Amic
Amin
a=2
Proof sketch. The proof is direct by solving the optimisation problem defining Tiv and using that TV (Bernoull(p) (Bennouli(g)) = p gl- We refer to Appendix B for details.
Comment. The aforementioned bound on TV characteristic time for Bernoulli instances is e-global DP parallel of the KL-characteristic time bound (v) Σx AT² [GK16]. Using Pinsker's inequality, one can connect the TV and KI. characteristic times by (iv(v) 2 (2T
4 Algorithm design: Private Top Two with adaptive episodes (AdaP-TT)
In this section, we propose AdaP-TT, an e-global DP version of the TTUCB algorithm [JD22]. We show that AdaP-TT satisfies e-global DP, is 8-correct, and has asymptotic sample complexity that matches the high privacy lower bounds up to multiplicatiie constants.
TTUCB belongs to the family of Top Two algorithms [Rus16, SHM 20, JDB 22], which selects each time two arms called leader and challenger, and sample among them. After initialisation, TTUCB uses a ICBB-asee leader and a Transportation Cost (TC) challenger, expressed by
Pn.B. An.a
B, = arg max + (log(n)/Nn.) and C = arg min aE(K)
az VI/Nn, 1/Nn,a
Here, (Bn; N,,) are the empirical means and counts 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 (u) min3e(0.11) T T (p.). For Gaussian distributions, have
(Na. -Ma WEEK ... =D 1/3 1/wa
2T ( (1) max
and T 1 S (T)
The maximiser of the above equation is denoted by W (H)). and is further referred to as the (-optimal allocation as it is unique. Let No., . denote the number of times arm was pulled when was the leader, and Ln,a denotes the number of times arm a was the leader. order to select the next arm to sample n. TTUCB relies on K tracking procedures, i.c. set In = B, if N N S $8Lm+1,B.. else J, Cn This ensures that [ NN n. 3Ln.al < 1. Standing on this premise, we now describe how we design an e-global DP extension of TTUCB.
Private algorithm design. As illustrated Algorithm 2, AdaP-TT relies on three ingredients: adaptive episodes with houblingg.orgeetting and adding calibrated Laplacian noise. (I) AdaP-TT maintains K episodes, i.c. one per arm. The private empirical estimate of the mean of an arm is only updated the end of an episode, that means when the number of times that particular arm was played doubles (Line 5). (2) For each arm AdaP-TT forgets rewards from previous phases of arm a, i.e. the private empirical estimate of arm a only computed using the rewards collected in the last phase of arm (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, AdaP-TT e-global DP as soon as each empirical mean (Line 9) is made e-DP, and thus, avoiding any use of privacy composition. This is achieved by adding Laplace noise. We formalise this intuition in Lemma 2 of Appendix C.
7

---

The aforementioned generic wrapper can be used to construct a near-optimal differ- entially 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 algorithums since they demonstrate both good theoretical guarantees and empirical performance.
Remark 2.
Theorem (Privacy analysis). For rewards in [0, 1), AdaP-TT satisfies e-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 2. Since the sampled actions, recommended action, and stopping time are computed only using the private empirical means, AdaP-TT satisfies e-global DP thanks to post-processing lemma. We refer to Appendix 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 4 yields threshold function ensuring that any sampling rule is ô-correct, when using the private GLR stopping rule.
Theorem 4 (d-correctness). Let å E (0, 1), E> O. Let > 1 and be the Riemann & function. Let Ot (n, m, 6) = 2Ca -1))((()) (0)((s))=//))))))))) /5)/2) 1lo(4++log n) + log(4 114++log log be the threshold without privacy. Given any sampling rule, the following threshold
(2kgf((s)
2
2Khg((s) 2
Kk (n, m, 8) = 2Ck (n, m. m/.)
log
log
(4)
ne²
8
me?
with the GLR stopping rule yields a 8-correct algorithm for nub-Gaussian distributions. The The function Cg is defined in (15). It satisfies Ca(x)= = x + Inx).
Remark. We observe that approximately Ce,ki (n, m,
m, 5) = 2 (o/1///)/////+/////////////////
Proof sketch. Proving d-correctness of a GLR stopping rule is done by leveraging concentration results. Specifically, we start by decomposing the failure probability P,, (Tx +00, o a²) into non-private and private part using the basic property of PPPPPXXX 2 a+bb < P(X aPY 2 b). The two-factor in front of Ck. k2 originates from the looseness of this decomposition. To remove it, we would need 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 non-private part, and Laplace random variables for the private part.
Theorem 5 (Asymptotic upper bound on expected sample complexity). Let (5, (8) E (0, and O. Combined with the private GLR stopping rule using threshold in (4), AdaP-TT is d-correct and satisfies that, for all E RRK such that minazb 1ike
14bl > 0,
(1 (1+ 1
[E([T]]
2
lim sum 6-+ log(1/8)
S (()
max
2
Proof sketch. We adapt the asymptotic proof of the TTUCB algorithm, which is based the unified analysis of Top Two algorithms from [JDB+22]. Below, we present high-level ideas of the proof and specify the effect of different elements of AdaP-TT on the expected sample complexity.
Consequences of Theorem 5. (1) The non-private TTUCB algorithm [JD22] achieves a sample complexity of T for sub-Gaussian random variables. The proof relies on showing that the
empirical pulling counts are converging towards the 3-optimal allocation WkL, (11). (2) The effect of doubling and forgetting is a multiplicative four-factor, i.c. 1 (H). The first two-factor is due to forgetting since throw away half of the samples. The second wooffctor 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 sub-exponential tail, the private means will still converge towards their true values. Therefore, the empirical counts of AdaP-TT will also converge WkL. (1.) asymptotically. (4) While the Laplace noise has little effect on the sampling rule itself, it changes drastically the dependency in log log(1/0) of the threshold used in the GLR stopping rule. The private threshold ce,ki k2 has an extra factor Olog2 (5)) compared to the non-private one Cz- Using the convergence towards wkL,, (14), the stopping condition is met as soon as [n) S 2log(1/0) + Alyg ( log (1/6). Solving the inequality for concludes the proof while adding a multiplicative faut-factor.
"
8

---

Algorithm 2 AdaP-TT. Private statistics are in red. Changes due to privacy are in blue.
1: Input: 3 (0, 1). risk 8 (0, 1), privacy budget e, thresholds Ck, N22 x (0,1) R
2: Output: Recommendation and Stopping time r satisfying e-global DP
3: Initialization: Va [K], pull arm a, set ka 1, (i(a) K 1, Innaa
0, Nn,
n. = K +.
4: for K do
5: if there exists E [K] such that No, 2 2N (a).a then
b Per-arm doubling
6: Change phase kig & kin + for this arm a
7:
Set Tk. (a) and Nk.. NT, (a),a NT,,,
Pulls of a in its last phase
Set Paa.a -Nv.ia 2== X,1 s7g = o} Empirical mean of a in its last phase Tha (a)-1
8:
9:
Set Nia.aa Pkaaa + Ykana where Yka Lap((eNVko.a)
Make it private
10:
end if
Set a₂ = arg maX Pika.b (MLg, on -MA, -D,,,
Arm with highest private mean I/NN,,, an. +1/NN,.b 2Ge, ks (N Kan dn. Ner,b 8) for all b o 0 then
12:
if
13:
return (ān, n) GLR stopping condition is met, recommend the empirical best arm end if
14:
15:
Set B, = arg max max (ikko + V W/aa/Naa + ka/ (c:Nka.a)
> Private UCB leader
BEgn .nn -oka.
Set Cn = arg min Br. B./Nn,B.t//NN.
Private TC challenger
17:
Set I = Bn if N. S 3lnn+1, else In Cn.
b Tracking
Pull Ln, and observe Xn VI,
N=B.. Set Nnt1.1 t Nn..n ni1,1. f- N.l.. 1 and Lnt1,B. + Ln.B. +1. Set < n+1
20:
end for
Discussion For 3 1/2, it is well known that T ( S (M) S 8 & A= We consider Bernoulli instances (0 < Amin S Amax < 1), where the gaps have the same order of magnitude, i.e. Condition 1: there exists constant C > 1 such that Amax/ Amin S C. For such instances, there exists a universal constant such that
[
S max { (Tk,,)2(H)) (C CE CE Eoga A
lim sup 8-0 log(1/8)
Without privacy, i.e. e e- +00 AdaP-TT yields multiplicative eight-factor. On top of the four-factor due to doubling and forgetting, another multiplicative two comes from 2c,, k2 in Equation (4).
Comparison to the lower bound. For Bernoulli bandits verifying Condition 1, the upper bound of
Theorem 5 matches the (p)(f) lower bound of Corollary up to constants in the high-privacy regime, i.e. when < (ty( (t)). In the low-privacy regime, the upper bound reduces to TK TT.. (1). In Appendix E.7, we discuss in-depth why this difference necessary for private BAI algorithms based on the GLR stopping rule, which poses an interesting open problem.
Comparison to DP-SE. DP-SE is private version of the in [SS19] for the regret minimisation setting. The algorithm samples active arms uniformly during phases of geometrically increasing length. Based 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 c-DP-FC-BAI algorithm, where stop once there is only active arm left. In particular, the proof of Theorem 4.3 of [SS19] shows that with high probability any sub- optimal arm a jf a* is sampled no more than O ((A..) -1). From this result, it is straightforward to extract a sample complexity upper bound for DP-SE, i.e. OlEnfa- A + Enza- -1)
algorithm studied
This shows that DP-SE too achieves (ignoring constants) the high-privacy lower bound (1t) for Bernoulli instances. However, due to its uniform sampling within the phases, DP-SE less adaptive than AdaP-TT. Inside phase, DP-SE continues to sample arms that might already be known to be bad, while AdaP-TT 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, AdaP-TT has the advantage being anytime, i.e. its sampling strategy does not depend on the risk 8.

---

107
High Privacy Regime
TTUCB
TTUCB AdaPTT
High Privacy Regime
AdaPTT
DP-SE
Stapping Time
Stapping popping Time
10f
Low Privacy Regime
Privacy Regime
10a
10
10
10
10"
Privacy B
Privacy B
Figure 1: Evolution of the stopping time т (mean + std. over 100 runs) of AdaP-TT, DP-SE, and TTUCB with respect to the privacy budget for 10-2 on Bernoulli instance μu (left) and μ/2 (right). The shaded vertical line separates the two privacy regimes. AdaP-TT outperforms DP-SE.
5
Experimental analysis
We perform experiments show that: (i) AdaP-TT has better empirical performance compared to DP-SE, and (ii) the transition between high and low-privacy regimes is reflected empirically.
Experimental setup. We compare the performances of AdaP-UCB and DP-SE for FC-BAI in different Bernoulli instances as in [SS19]. The first instance has means μ* = (0.95, 0.9, 0.9, 0.9, 0.5) and the second instance has means μ2 (0.75, 0.7, 0.7, 0.7, 0.7). As a benchmark, we also compare to the non-pni non-private TTUCB. We set the risk 5 = 10 10-2 We implement all the algorithms in Python (version 3.8) and on an 8-core 64-bits Intel @ 1.6 GHz CPU. We run each algorithm 100 times, and plot corresponding average and standard deviations of stopping times in Figure 1. We also test the algorithms on other Bernoulli instances and report the results in Appendix F.
Result analysis. a. Efficiency in performance. AdaP-TT requires less samples than DP-SE to provide 8-correct answer. In the high privacy regime, i.e. small e, AdaP-TT outperforms DP-SE in all the instances tested. In the low privacy regimes, i.e. large e, both algorithms have similar performance that in the worst case four times the samples required of TTUCB, shown theoretically.
b. Impact of privacy regimes. As indicated by the theoretical sample complexity lower bounds and upper bounds, the experimental performance of AdaP-TT demonstrates two regimes: a regime (for < 0.2), where the stopping time of AdaP-TT depends on the privacy budget and low privacy regime (for >> 0.2), where the performance of AdaP-TT does not depend on c.
6 Conclusion and future works
We study FC-BAI with e-global DP. We derive a sample complexity lower bound that quantifies the additional samples needed by 8-correct BAI strategy in order to ensure e-global DP. The lower bound further suggests the existence two privacy regimes. In the low-privucy regime, no additional samples are needed, and privacy can be achieved for free. For the high-privacy regime, the lower bound reduces to Q(E "TTy), and more samples are required. We also propose AdaP-TT, an e-global DP variant of the Top Two algorithms, that runs in adaptive phases and adds Laplace noise. AdaP-TT achieves the high privacy regime lower bound up to multiplicative constants.
The upper bound matches the lower bound by multiplicative constant in the high privacy regime, and is also loose in some instances the low privacy regime, due 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 to extend the proposed technique to other variants of pure DP, namely (c, 8)-DP and Rényi- DP [Mir17], other trust models, namely local DP [DJW13] and shuffle DP [Che21, GDD+211,
10

---

Acknowledgments and Disclosure of Funding
This work has been partially supported by the THIA ANR program "AL PhD@Lille A. Al-Marjani acknowledges the support of the Chaire SeqALO AANR20-CCIAA-0DE paria-Kyoto University Associate Team "RELIANT" for supporting the project, and the ANR JCIC for the REPUBLIC project (ANR-22-CE23-00033 Garivier for the interesting conversations. We also thank Philippe Preux for his support.
D. Basu acknowledges the
We thank Emilie Kaufmann and Aurélien
References
[AB22] Achraf Azize and Debabrota Basu. When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 11122199-22210 2022.
[ACBF02] Peter Auer, Nicolo Cesa-Bianchi Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-22 256, 2002.
[AKR21] Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On multi-armed bandit designs for dose-finding clinical trials. The Journal of Machine Learning Research, 22(1):686-77) 723, 2021.
[ASZ21] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Algorithmic Learning Theory, pages 48 18-78. PMLR, 2021.
[AYBG+18 18] Yasin Abbasi-Yadkort Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Conference on Learning Theory, pages 918-949. PMLR, 2018.
[BDT19] Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou. Differential privacy for multi-armed bandits: What is it and what is its cost? arXiv preprint arXiv: 12298, 2019.
[Bec54] Robert E Bechhofer. single-sample multiple decision procedure for ranking means of normal populations with known variances. The Annals of Mathematical Statistics, pages 16-39, 1954.
[Bec58] Robert E Bechhofer. A sequential multiple-decision procedure for selecting the best of several normal populations with common unknown variance, and its use with various experimental designs. Biometrics, (4(3):408442) 1958.
[Che21] Albert Cheu. Differential privacy in the shuffle model: A survey of separations. arXiv preprint arXiv:2107. 1839, 2021.
[CL16] Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference Learning Theory, pages 590-604. PMLR, 2016.
[CLK* 14] Shouyuan Chen, Tian Lin, Irwin King, Michael R Lyu, and Wei Chen. Combinatorial pure exploration multi-armed bandits. Advances in neural information processing systems, 27, 2014.
[CWZ21] T Tony Cai, Yichen Wang, and Linjun Zhang. The cost privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-295 2850, 2021.
[DW133] John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pages 438. IERE, 2013.
[DKM19] Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptotic pure explo- ration by solving games. Advances Neural Information Processing Systems, 32, 2019.

---

[DNP* 10] Cynthia Dwork, Moni Naor. Toniann Pitassi, Guy N Rothblum, and Sergey Yekhanin. Pan-private streaming algorithms. In ICS, pages 66-80, 2010.
[DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential pri- vacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715-724. ACM, 2010.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4)221 1,0,)
[DRS22] Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 2022.
[EDMMM06] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6). 2006.
[GDD+21] Antonious M Girgis, Deepesh Data, Suhas Diggavi, Ananda Theertha Suresh, and Peter Kairouz. On the renyi differential privacy of the shuffle model. Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pages 2321-2341, 2021.
[GGL12] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. Advances in Neural Information Processing Systems, 25, 2012.
[GK16] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 1028-027.-000 PMLR, 2016.
[JD22] Mare Jourdan and Rémy Degenne. Non-asymptotic analysis of a ucb-based top two algorithm. arXiv preprint arXiv:2210.054:3 2022.
JDB+ 22] Mare Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilie Kauf- mann. Top algorithms revisited. Advances in Neural Information Processing Systems, 35:26791-268033 2022.
[JD223] Mare Jourdan, Rémy Degenne, and Emilie Kaufmann. Dealing with unknown vari- ances in best-arm identification. International Conference on Algorithmic Learning Theory, 2023.
[JNB14]] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil'ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423 439, PMLR, 2014.
[JN14] Kevin Jamieson and Robert Nowak. 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 1-6. IEEE, 2014.
[JT16] Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. Artificial intelligence and statistics, pages 240-248. PMLR, 2016.
[KCG16] Emilie Kaufrannn, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
[KK13] Emilie Kaufmann and Shivaram Kalyanakrishnan. Information complexity in bandit subset selection. In Conference on Learning Theory, pages 228-251. PMLR, 2013.
[KK21] Emilie Kaufmann and Wouter M Koolen. Mixture martingales revisited with appli- cations to sequential tests and confidence intervals. Journal of Machine Learning Research, 22((46): 2021.
12

---

[KNSS2I] Dionysios Kalogerias, Kontantinos E Nikolakakis, Anand D Sarwate, and Or Sheffet. Quantile multi-armed bandits: Optimal best-arm identification and a differentially private scheme. IEFE Journal on Selected Areas in Information Theory, 2(2):534-548 2021.
[KV17] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals, 2017.
[LEHT22] David E. Losada, David Elsweiler, Morgan Harvey, and Christoph Trattner. 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 2022.
LJD*17 17] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadch, and Ameet Tal- walkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):6665-886,, 2017.
[LPJ22] Simon Lindståhl, Alexandre Proutiere, and Andreas Johnsson. Mcasurement-basee admission control in sliced networks: A best arm identification approach. GLOBE- COM 2022-2022 IEEE Global Communications Conference, pages 1484 1490. IEEE, 2022.
[LS20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[LVR + 19] Pieter JK Libin, Timothy Verstraeten, Diederik M Roijers, Jelena Grujic, Kristof Theys, Philippe Lemey, and Ann Nowé. Bayesian best-arm identification for selecting influenza mitigation strategies. In Machine Learning and Knowledge Discovery in Databases:
European Conference, ECML PKDD 2018, 2019.
[Mir17] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE, 2017.
[MT04] Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-648, 2004.
[MT15] Nikita Mishra and Abhradeep Thakurta. (Nearly) optimal differentially private stochastic multi-am arm bandits. In UAI, 2015.
[NKS19] Konstantinos E Nikolakakis, Dionysios Kalogerias, and Anand D Sarwate. Optimal rates for learning hidden tree structures. arXiv preprint arXiv:1909.09500 2019.
[NR18] Seth Neel and Aaron Roth. Mitigating bias in adaptive data gathering via differential privacy. International Conference on Machine Learning. pages 3720-3729. PMLR, 2018.
[RBCS23] Alexandre Rio, Merwan Barlier, Igor Colin, and Marta Soare. Multi-agent best arm identification with private communications. In Proceedings of the 40th International Conference on Machine Learning, 2023.
[Rus16] Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pages 1417-1418. PMLR, 2016.
[SHM+20] 20] Xuedong Shang, Rianne Heide, Pierre Menard, Emilie Kaufmann, and Michal Valko. Fixed-confidence guarantees for bayesian best-arm identification. In International Conference on Artificial Intelligence and Statistics, pages 1823-1832. PMLR, 2020.
[SLM14] Marta Soare, Alessandro Lazaric and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
[SS18] Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. In Advances in Neural Information Processing Systems, pages 4296-4306, 2018.
13

---

[SS19] Touqir Sajed and Or Sheffet. An optimal private stochastic-me mab algorithm based on optimal private stopping rule. International Conference on Machine Learning. pages 5579-5588. PMLR, 2019.
[TBD+ 16] Katherine Tucker, Janice Branson, Maria Dilleen, Sally Hollis, Paul Loughlin, Mark J Nixon, and Zoë Williams. Protecting patient privacy when sharing patient-level data from clinical trials. BMC medical research methodology, 16(1):5-14, 2016.
[TD16] Aristide CY Tossou and Christos Dimitrakakis. Algorithms for differentially private multi-armed bandits. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[ZCL14] Yuan Zhou, Xi Chen, and Jian Li. Optimal pac multiple arm identification with applications crowdsourcing. In International Conference on Machine Learning. pages 217-225. PMLR, 2014.
14

---

Appendix
Table of Contents
A Outline
16
B Lower bounds on sample complexity
16
B.1
Canonical model for BAI
16
Transportation lemma under e-global DP: Proof Lemma
B.3 Lower bound sample complexity: Proof of Theorem 2
17
B.4 TV characteristic time for Bernoulli instances: Proof of Proposition
18
B.5 On the total variation distance and the hardness of privacy
19
C Privacy analysis
20
C.I Privacy lemma for non-overlapping sequences
20
C.2 Privacy analysis of AdaP-TT: Proof Theorem
21
D AdaP-TT: A private Top Two algorithm with adaptive episodes
22
D.1 Generic wrapper existing BAI algorithms
22
D.2 AdaP-TT:
Instantiating our wrapper with Top Two sampling rule
25
E Analysis of AdaP-TT: Proof of Theorem 5
27
E.1 Technical results ...
28
Sufficient exploration
29
Convergence towards 8-optimal allocation
33
E.4 Cost of doubling and forgetting
36
E.5
Asymptotic expected sample complexity
37
E,6
Connection to the lower bound
40
E.7 Limitation and open problem
42
E.8 Analysis of non-private AdaP-TT: Proof of Theorem 6
................................
43
F Extended experimental analysis
15

---

A Outline
The appendices are organized follows:
The proof of our lower bound is detailed in Appendix B (Theorem 2).
The proof of the privacy AdaP-TT is done Appendix C (Theorem 3).
The AdaP-TT algorithm is presented in details in Appendix D, and show the ô-correctness of the non-private GLR stopping rule (Theorem 4),
The asymptotic upper bound on the expected sample complexity AdaP-TT proven in Appendix E (Theorem 5).
Extended experiments are presented in Appendix F.
B 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 e-global version of the transportation lemma, i.e. Lemma 1. Using this lemma, we prove Theorem 2. Finally, we prove the formula expressing the TV characteristic time for Bernoulli instances.
B.1 Canonical model for BAI
[K] be bandit instance, consisting of K arms with finite means {Ma he [K]- Now, we recall the interaction between a BAI strategy π and the bandit instance v in the Protocol The BAI strategy æ halts at r, samples a sequence of actions A and recommends the action Let
Let & {Ma
Fu.F be the probability distribution over the triplets (r, AT A), when the BAI strategy π interacts with the bandit instance v.
For a fixed T > 1, a sequence of actions aT = ((1.....,ay ar) E [K]T and a recommendation E [K],
we define the event E = {r = T, A = aT, A = à}. We have that
P Pu.n( (F) Jez (m <aa² a
II du (r,)dr,
where
T II [=1
Taa ",,,,,77 a. 2T) A Reer+1 (ā Hr) STt1 (T (Hr)
S. (at He-1)
and Hi = (a1, Fl,..... at, rz).
Remark on the bandit feedback. Let be an e-D BAI strategy. Let T > 1, a" E [K] a sequence sampled actions and [K] recommended actions. This time, let rd {ri, fri,..., rT) R² and
TT E I two neighbouring sequence of rewards, i.c. dHam (rT (T) & DT {r: & r/ = 1.
Consider the table of rewards d" consisting of concatenating r colon-wise K times, i.e. d' 1
E [K] and E [T]. Define d' similarly with respect r"
In this case, by definition of n. d" and d' is direct that
m Ta T. (TTT -,
and dHam dd'dd")-
Which means that
T Tla a,T ( a.
In other words, i is e-pure DP for neighbouring table of rewards d then a also e-pure DP for neighbouring sequence of observed rewards r!
16

---

B.2
Transportation lemma under e-global DP: Proof of Lemma 1
Lemma 1 (Transportation lemma under e-global DP). Let e (0, 1) and > Let u be bandit instance and À E Alt(v). For any 8-correct e-global DP BAI strategy, we have that
K
GE
Eu [Va (v, Aa) 2 kl(1 - 6,,),
where kl(x, y) A x log (1 2)) log 1-1 1-y for x, (0,
Proof. Step 1: Distinguishability due to d-correctness. Let i be ò-correct e-global DP BAI strategy. Let be bandit instance and À Alt(v).
Let Pv,x denote the probability distribution of (A, Ā, when the BAI strategy interacts with For any alternative instance Alt(z), the data proicessocsssnggg incquality gives that
KL (PP,T || PA,-)) 2 kl (Pu.. (Ā= a" (v)) Px,.= (Ā a" (v)))
2 kl(1 6, 8).
(5)
where the second inequality is because π is 8-correct i.c. Pu, (A= 2 and
FA. (A=a(()) S 6, and the monotonicity of the kl.
Step 2: Connecting KL and TV under e-global DP. On the other hand, by the definition of the KL, we have that
(T .A) (x,n(T, AA) ]
KL (Pu,o PA.x)= = B AnDun
log
where
/ raa a. z) II dva, (re).
T
P. (T =a a) = JEERT
Since 7 is e-global DP, using the sequential Karwa-Vadhan lemma [AB22, Lemma 2}, we get that
(T= = === PT = T,A" =aT,A a)
T
log
< 6e
TV (Va, Aoe)
t=1
6c
N. (Na 2a)
Which gives that
K
KL (Pu.r || PA,x) S 6c E
Σ
(v (1
(6)
Combining Inequalities and 6 concludes the proof.
B.3 Lower bound on sample complexity: Proof of Theorem 2
Theorem 2 (Sample complexity lower bound for -DD-FFC-BAI, Let 8 E (0, and e > 0. For any 8-correct e-global DP BAI strategy, we have that
Ep 2 T (v: log(1/3)),
where (I* (v:e)) A sup inf min IK WL (Na || da) 6E KK w. TV (va Na)). wEEK AEAlt(M)
17

---

Proof. Let ı be d-correct e-global DP BAI strategy. Let v be a bandit instance and À E Alt(v).
Let denote the expectation under IP p, ie E
By Lemma 1, we have that 6e Σx= E (T) TV (Ma || Aa) 2 kl(1 8, 6,6). Lemma I from [KCG16] gives that Ex= E (T) (Va || Aa) 2 kl(1 6,6). Since these two inequalities hold for all X Alt(z). we get
K
K
kd(1-5,0) -
inf
min
(T)
TV (v% An)
Σ
E [N (T)
KL (va Aa)
xc (l)
am
(a)
E (..(TT (T)
K
E [Na(T)
E
inf
min
6c
TV (Va Aa).
KL (Va 11 Aa)
xEAlt(w)
E[r]
E[r]
(b)
E(r]
sup WEEx (EAlt(rr
inf
min
6c
Wa TV (Va Xa);
Wa KL (Va Xia)
(a) is due to the fact that B[T] does not depend on A. (b) obtained by noting that the vector belongs the simplex Eg.
(Wo)aE[K] A
Evaa [N,(7)
Fv.m [T]
aE[K]
The theorem follows by noting that for 8 E (0, kl 6,6) 2 log(1/35).
B.4 TV characteristic time for Bernoulli instances: Proof of Proposition
Proposition 1 (TV characteristic time for Bernoulli instances). Let be bandit instance, i.e. such PK. Let A. & in Ha and Amin - minaş1 Ag.
that Va = Bernoulli(Ha)) and μr > P2 2 We have that
1
K Amin
Tiv(v)
and
S (Tv( S
Amin
A
min
a=2
Proof. Step 1: Let v/ be bandit instance, i.c. such that v. Bernoull and μn U2 2 2
For the alternative bandit instance X, we refer to the mean of arm a as Pa. ie. Ag - Bernoull(ppa).
By the definition of Tiy. we have that
K
(Ti( sup inf WEEk (EAl(()) a=1
Σ
wa TV (Va || Aa)
sup min inf
wi 1am pil + wa 1ifa Pal
weEx a#l Asp.Spp
bb)
sup min min Wa) weEx aøl
sup Wi min min (1,
We W1
)
weEK afl
(d)
minay1 Do (Xa)
sup ( JE
1 22 + ... + JK
where Iu (2.) 2 miin(1
Equality (a) is obtained due to the fact that Alt(p) = U Pa > pr.. and for Bernoullis,
TV (va >a) = |Pa Pal-
Equality (b) is true, since inf xupx Sp1 W1 Iu PIl + Wa IMta Pal min (o)1, Aa.
18

---

Equality (c) holds true, since w1 * 1 (if W1 = 0, the value of the objective is 0). Equality (d) is obtained by the change of variable Tia
We
Step 2: Let (22..... FK) E (IR ) By the definition of ga. we have that
(x(a S Aa and
Iu ga(xa) Da.
This leads the inequalities
min Da (xa) S Ia (x(aa) S da a#1
and
min Iu (Fa) S Amin- a#1
Thus,
K
K
min Ba(ta)
1
min Da (Ta)
min Ia (xa)
a#1
Amin
A
Anin
Aa
a=2
a=
K
+
To
0=
This means that for every (12....,,2) E (R+)K-1
minaæ1 (x(
+ x22
IK
+ Ex= 1
Aui
An
Here, the upper bound is achievable for x This concludes that
Ami A.
since (xx)) Amin for all a a 1.
K
(T)(
(TTv()) = Amin +
Σ
A
Amn
2a=2 An
a=2
Step 3: The lower and upper bounds on (Tiv(D)) follow from the fact that
A. 2 for all a, and
1 S Amm for all + 1.
Hence, we conclude the proof.
B.5 On the total variation distance and the hardness of privacy
Our lower bound suggests that the hardness of the PP-FC-BAI problem is characterized by T which is a total variation counterpart of the classic KL-based characteristic time T in FC- BAI (GK16), The total variation distance appears to be the natural measure to quantify the hardness of privacy other settings such as regret minimization [AB22], Karwa- Vadhan lemma (K [17) and Differentially Private Assouad, Fano, and Le Cam [AS721]. The high-level intuition is that: Pure DP can be seen as a multiplicative stability constraint of e when one data point changes. With group privacy, if two datasets differ in dham points, then one incurs factor edham c, Now, by sampling i..d points from a distribution P and i.i.d points from distribution Q, the Karwa-Vadae states that the incurred factor is (P.TV) This proved by building a maximal coupling, which is the coupling that minimizes the Hamming distance in expectation. In brief, the total variation natu- rally appears in lower bounds since the quantity that characterises the hardness of the optimal transport problem minimizing the hamming distance, i.e TV Q) (n.xx)))((P0) F(1 x 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.
lemma
On the relation between T and Tir. A direct application of Pinsker's inequality gives that (v) 2 22I For completeness, we present here the exact calculations:
19

---

For every alternative mean parameter and every arm a, using Pinkser's inequality, we have that 2 dd (Ma: Aa). Therefore, for every allocation over arms we have
drv drv(Ha: Aa) - /
Σ (Ha I Ewar way V
EdxelHo:dal Aa) S E WodkL (Pa: da).
Taking the supremum over the simplex and the infimum over the set of alternative mean parameters yields (Tiv V ( This concludes the proof.
C
Privacy analysis
In this section, prove that AdaP-TT satisfies e-DP. We first provide the privacy lemma that justifies using doubling and forgetting in AdaP-TT. Using the privacy lemma and the post-processing property of DP, we conclude the privacy analysis of AdaP-TT.
C.1 Privacy lemma for non-overlapping sequences
Lemma 2 (Privacy of non-overlapping sequence of empirical means). Let M be mechanism that takes set as input and outputs the private empirical mean, i.e.
1 M(tr.....,. r3)) -
Σ rs Lap (j- ) -
(7)
Let & < T and f1,...te; .e.tee tet1 be in [1, such that = t < ... < be < te+1 - =I
Let's define the following mechanism
G fri............................. rT]
(8)
In other words, G is the mechanism get by applying M to the non-overlapping partition of the sequence (ri.-..,Pr) according 1 < 24 te-11 1. ie.
μi
Y2
g
where #4 Mr
For E [0, 1}, the mechanism G is e-DP.
Proof. Let T A (r1...., PT) and TT (ri:-..,ry) ..) be neighbouring reward sequences in [0,1]. This implies that 3j E [1,7) such that ry # r and Vt + j. rt = =
Let be such that Le S.j S 4 1, and follows the convention that l0 = and l7+1 T + 1.
Let A (pI....,pe) .ee) fixed sequence of outcomes. Then,
P(G(r") =) P (Mi(f ..... Fhe -11) = pei
S SE,
PP =1) (M((fr ((p2,-1)) = He
where the last inequality holds true because M satisfies e-DP following Theorem 1.
20

---

C.2 Privacy analysis of AdaP-TT: Proof of Theorem 3
Theorem (Privacy analysis). For rewards in [0, 1]. AdaP-TT satisfies e-global DP.
Proof. Let 7 1. Let d (x1, (x,,..,, x and d [dd ---... d/} two neighbouring reward tables in (T. Let [1, T] such that, for all L + j. dg = dz-
We also fix sequence of sampled actions a² {ai...., ar) [K] and recommended action E K.
We refer to AdaP-TT BAI strategy by π.
We want to show that: Tta", a. T' d") E a, d
The main idea is that the change of reward the j-th reward only affects the empirical mean computed in one episode, which is made private using the Laplace Mechanism and Lemma 2.
Step 1. Sequential decomposition of the output probability
We observe that due to sequential nature of the interaction, the output probability can be decom-
posed to part that depends on q A (xI..... Xy-1). which is identical for both d" and d and second conditional part on the history.
Specifically, we have that
Taa a, T d & Recr+1 (ā HT) Sr+1 (T) Hr) II
S. (a. H4-1)
==1
- P (a )P (ayj 0,T x²)
where
azj - (0)tl....,01)
P (a)) II S. (at Hc-1)
Pazas à, T (²) A ReeT+1 (ā HH) ST+1 (T Hr) I Se (a+ HH-1)
Similarly
x(a" T. |d" PT (a- à, a²)
since d= d
Which means that
T(a" "a",a,T d=) (a ā, a²)
(9)
<aa", T d"
P (a à, T a5)
Step The adaptive episodes are the same, before step
Let é such that L J < le-1 when interacts with d Let us call it vag (j) & l. Similarly, let ll such that te j te41 when æ interacts with dd Let us call ( & ll.
Since ts (j) only depends on d di-1 which is identical for d" and d' we have that va5 (j)
ui T ()) with probability 1.
We call E the last time-step of the episode d (i), A
1.
Step 3. Private sufficient statistics
Let A dfa,, be the reward corresponding to the action in the table d" Similarly, rf d' for
'T'
21

---

(p) where G is defined as in Eq. 8, using the same episodes for and d'. In other words, Lj is the list of private empirical means computed on non-overlapping sequence rewards before step Ey.
Let us define Lj - (e) and L' -
Using the forgetting structure of AdaP-TT, there exists a randomised mapping faye; such that
(a(-1 Saxe, o Tag and Pa (²) = Ja,e, T4.
In other words, the interaction of with and d' from step E + until T only depends on the sufficient statistics Lj. which summarises what happened before E,, and the new inputs d d=e;" which are the same for and d'.
Step 4. Concluding with Lemma and the post- post-processing lemma
Since rewards are in [0, 1]. using Lemma 2, we have that G is c-DP. Since PT (. a²) is just post prosessocessing of the output of G, we have that
Pj (0>)) 0, @²)
se,
Ps ( a²)
and Eq. (9) concludes the proof.
D AdaP-TT: A private Top Two algorithm with adaptive episodes
We propose generic wrapper adapt existing BAI algorithms tackle private BAI (Appendix D.1). Then, we show how to instantiate our wrapper with an instance of Top Two algorithm (Appendix D.2), namely TTUCB [JD22].
D.1 Generic wrapper existing BAT algorithms
We propose a generic wrapper to adapt existing BAI algorithms to tackle the c-DP-FC-BAI problem.
1. It uses adaptive episodes with doubling and forgetting (Appendix D.1.1). This builds the idea used to make the UCB algorithm private for regret minimisation [AB22].
2. It relics on a private GLR (generalised likelihood ratio) stopping rule (Appendix D.1.2). The GLR stopping rule [GK 16] widely used in the BAI literature, since ensures correctness of the stopping rule regardless of the sampling rule.
For each arm a E [K] we maintain phase at time whose index will be denoted by kn,e E N. We switch phase soon the number of times that the arm was played is doubled. We only evaluate the stopping condition when we switch phase for an arm.
D.1.1 Adaptive episodes with doubling and forgetting
As initialisation, we start by pulling each arm once, and set kina = 1, (a) K and N.
for a [K]. the following, we will consider n > K and we denote the global pulling count of arm a before time n by Nn.o _ Eiejn-ij (I, = a). For each arm a E [K], the random stopping time denoting the end of ka - and the beginning phase Ka > 1 is denoted by
Th. (a) A inf (n E N Nn,a 2 2N 2NN,.-(())..)
(10)
At the beginning of phase K2 for an arm a E [K]. we update the empirical mean based on the observations on arm a E [K] collected during this last phase, i.e.
The (a)-1 -1
Σ
X,1 (I, o)
(11)
Nk. (T
where the local pulling count pf arm is denoted by Nk. A NT,, (a).a NT,, (a)), meaning
is the number of collected samples during the phase ko 1. To ensure privacy, we add Laplace
22

---

noise to define the private empirical mean, i.e.
Piaia + Yiaaa where
Lap
(12)
We emphasise that only the private version the estimator ik a i.e. Pake is used by the algorithm until the end of phase Ki for arm a. Since (kn,a)ae(K) denotes the current phases at time n, our algorithm relies on aa Mbg as NN... Nu(Kk
Due to the doubling, the growth of the global and local pulling counts is exponential (Lemma 3). Lemma 3. For all E [K] and all k E N such that Ev [T) +oc, have
Nra(a), = 2 and Nua = 2
Proof. Let a E [ After initialisation, we have k (a) K and (T) 1. Using the definition of the adaptive phase switch (Equation (10)), it is direct to see that N (T)),, = 2 and N2.a when E, [T]( +00.
Now, we proceed by recurrence. Suppose that (T), = 2 and Nx.a 2²- when E, [T]( < +oo. If [T (a)] < +oo, then it means that the phase i ends for arm almost surely. Since we sample only one arm at each round, at the beginning of phase k + for arm we have NT (a). 2N)g(a), 2* by using the definition of the adaptive phase switch (10). Then, have directly that N = NTEn(()) -Na(a)a = 2 2k-1 -
D.1.2 GLR stopping rule
Non-private GLR stopping rule with phases. Given set of non- non-private threshold functions (ck) such that C₁ N x (0, 1) + R, for all & N, the non- non-private GLR stopping rule can be evaluated the beginning of each phase for each arm, namely
(PK..aN and ab)
7 NP inf n n E
V4 4 NNP.
2 20% ox (N... axp, N Nen
1/NK a are + 1/ 1/Nkn,o.b
(13)
where a = arg max ( a is the non-private candidate answer until we switch phase again (for any arm). We emphasise that this stopping condition is only evaluated the beginning of each phase for each arm since it involves quantities that are fixed until we switch phase again.
Lemma 4 gives non-private threshold functions ensuring that the non-private GLR stopping rule is 5-correct for all E (0, 1), independently of the sampling rule.
Lemma 4. Let E (0,1), 1). Let and be the Riemann Ç function. Given any sampling rule, the non-private GLR stopping rule (Equation (13)) with non-private threshold functions
ca(n, m. 2CG (} 1210g
(K ((-- 1)((8)
))
2ogg(4 + logn) log(4 log m)
(14)
5
ensures 5-correctness for 1-sub-Gaussian distributions. The function CG is defined in Equation (15). It satisfies CG 2e log
Proof. The non-private GLR stopping rule matches the used for Gaussian bandits. Proving 5-correctness of a GLR stopping rule is done by leveraging concentration results. In particular, we build upon Theorem of [KK21], which is restated below.
Lemma 5. Consider
bandits with means μ E RRKKK Let C [K] and x > O.
Na.k (pn,k - 12 2² > Σ
P 3n E N. Σ
2lo (4 + log (Nn,k) ))+ + |S|Co
(S)] $ ==
2
KES
keS
23

---

where CG is defined in [KK21]cr as
(x(A) and 9G(A) _ 2X 21log(4A) + log ((2
1
Ca(x) min xe]1/2.1
2 log(1 - 2).
(15)
Here, Ç is the Riemann ffnction and Cx(x) + log(x).
Let an"h arg [[ ARn,a. Standard manipulations yield that for all o à
inf v2
(N a xx)² +
y)²
1/Nkm,a.a + 1/NKm,p.b
Using the non-private GLR stopping rule (13) with non-private threshold functions (CE)REN and the above manipulations. obtain
Pr (T8
< +00, à #aa)
< Pu
En E N, 3a # a', a arg max i. 4b + a, kc(k]
x)² + N N w)²} 2 20hn (Nkm Nemi 5)
inf
92
< Pv (0)
E N, 3a # a" a arg max akn,a..s bE[K]
a (itinaaa Haa² + N Nen.ar at (Pkmau - Na. 2 (Nkm, N sar
< Pv (3a + a, 3,Keaa ) E E?2
(b)
Ñ Nku (Prisia - Ha)2 + Nearir (Aiar - pao) 2 200u (Nuavar (ar,,
Σ Σ
Pv (Nua.alPisaa - Ma)² + Nk (fitoa Ho! )2
agtin (Naskis JEN2
2 20 (Nu No. aarra.
The inequality (a) obtained with (b, x. y)
The inequality (b) drops the condition arg be[K] b. hence we can restrict to (Ria, kas) N² since it doesn't depend on other phase indices. The inequality (c) relies on direct union bound. For all a* and all (kas ka N2, the estimators i (resp. .a*) are based solely on the observations collected for arm a (resp. arm
Ma. Ma ,aa,
a') between times E (
Tke (a) 1} (resp. E (Tk.- -1(",, Tke (a*) 1})
with local counts Na (resp. Ni....o i.c. dropping past observations. Using Lemma for all
* a" and all (ka. ka-) N2, we obtain
(T < +00, it) <
8
Σ
Σ
(kakaa 8.
K ((8)
ast" (kurlia JENZ
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 fik...... which are not private. To alleviate this problem, we propose the private GLR stopping rule, which is based on the private empirical means j.......
Given a set of private threshold functions (Ce,A) Ak (e,ks A2)ER; xNP, such that Cr,ky N N x (0, + R4 for all (e, ki, k2) E R x N2, the non-private GLR stopping rule is evaluated at the beginning of each phase for each arm, namely
= inf n E ENNNN Vb o ān: (PKn.A,, On b.b)
> 2ce Cn.en Ron, No. (Neaen on N No.
1/Nkn. den + +1/N L/NNo.DD
(16)
24

---

K kkgg(s)) 2 where â, = arg m 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.
[K] Pr....a is the private candidate answer until we switch phase again (for
Theorem gives private threshold functions ensuring that the private GLR stopping rule is 6-correct for all 6 E (0,1) and all E RL, independently of the sampling rule.
Theorem (é-correctness of the private GLR stopping rule). Let ò E (0, and E R Let s > 1 and ( be the Riemann function and non-private threshold function (Cu)KEN as in (14). Given any sampling rule, the private GLR stopping rule (Equation (16)) with private threshold functions
(2K
2
1 me²
(2kkg(()) (266)
Ce,ki, (n, m, 5) 20k, k2 m, 6,
log
log
(17)
ne²
8
8
ensures d-correctness for I-sub-Gaussian distributions.
Proof. Let Ri. Since Yan,e.a ~ Lap ((EN we have that a ao ~ (()) for all [K] and all N. where E.) denotes the exponential distribution. Using concentration results for exponential distribution, a direct union bound yields that
(Kkn,a((s) 88.
P 3n E N, Ea E [K], NK....a a Y Yon...
log
(18)
Let us denote ke kz (n, m. 8) the threshold associated to the Laplace noise, i.e.
1 ne²
Kkfc(s)
C, (n, (,,
log
log
m
5
Using the private GLR stopping rule (Equation (16)) with private threshold functions (eekk. As)ER; xN2, similar manipulations as above yields
Py (Ts < +00, "00, x(a)
Pv En E N, 3a + a² N N - No + Yk....a) a + Nanar ar (ikmar Ma Vknat sa
a 0/2) + kn aN (Nkm.aras N ,r, 8/2)) 2 Ackn. kn. (NNa. Nem.r ar,
< Pv (3a & a² 3(kia ka.) E N??,
(a)
(akko Ha) + Nu a (pkar,a" pa )2 2ckak.r (Nka No, Ne,,, 8/2))
P. In E N, Ea + a: Nkn V2 aa + Nkn.rr .a V-2 Vinaaaac
2 ZCe.bonashuuu (Nua N NAnarra at, 8/2))
2K a ((8)
< 8/22+ PP P (8)
In InEN, 3a E [K], Nem. Min. 2 log
8
< 6/2+5/2-1 (c)
The inequality (a) uses that PX 2 bb P(X +PY b) and (x- < 2x 0 2y
The inequality (c) leverages Lemma 4 and a direct inclusion of event. The incquality (c) deploys Equation (18) to conclude.
D.2 AdaP-TT: Instantiating our wrapper with a Top Two sampling rule
A blueprint of Top Two algorithm design. At time n K, Top Two sampling rule defines leader B,, and a challenger C,, Then, it selects among them the next arm to sample T,,. Given a proportion 3 (0. 1) fixed beforehand, the choice of 7, E [B,,, C, should ensure that the leader is sampled close to 3 of the times where was chosen as leader. In early works on Top Two algorithms, this choice is randomised. Following [JD22], we use K independent tracking procedures.
25

---

1, = b) the number of times the arm b was pulled while the arm a was the leader, and by Ln.a - Eie(n- the leader. At time n > K, the next arm to be pulled I, is defined as
We denote by No, n,b - 1)
(B, = a) the number times arm a was
, = Bn if N S S8 otherwise
Cn
(19)
In other words, sample the leader if have not yet sampled it fraction / of the times it was leader. Those K' independent tracking procedure satisfy the desired property (Lemma 6). Lemma 6 (Lemma 2.2 in [JD22]). For all > K and all [K], we have
-1/2 & N -LL S 1.
To finish specifying a Top Two algorithm, we simply need to specify the choice of the leader/challenger pair. Intuitively, good choice of the leader/challenger pair should ensure (1) sufficient exploration, (2) convergence of the leader towards the best arm a", and (3) convergence of the global pulling proportions to the B-optimal allocation WKL,a( which is defined for Gaussian distributions as
A
WKI, A arg max min
We =B asta 1/3 + 1/wL
While consider TTUCB algorithm [JD22] in AdaP-TT, algorithms could be used with the same type of guarantees. TTUCB a Top Two algorithm which combines (CCB-based leader and Transportation Cost (TC) challenger. Its key novelty lies in the use of K tracking procedures. Since it is deterministic, the analysis is less cumbersome.
emphasise that other Top Two
Non-private leader/challenger pair. The non non-private leader/challenger pair is inspired by the TTUCB algorithm [JD22]. At time n > K, the non-private UCB leader defined as
kn.a
BNP arg max aE(K]
Pkn
(20)
N Nem.asa
where / Knna/Nk..... Nk.... bonus to cope for the uncertainty which depends on the current phase kn.a- Later, we show that log(n)/kn,a = (()) for all E [K]. Hence, it has the same scaling as the bonus used in standard UCB. Since it depends solely the local counts (eNe....)ueej and the empirical means
( the non-private UCB leader is fixed until we switch phase again.
At time K, the non non-private TC challenger is defined
P* BB""" BNN"
C A arg min az BNP
(21)
V /1/Nn, + I/N
While it depends on the empirical means (Nx.....)aEEIK that are fixed till we switch phase again, also depends on the global counts (NN,a)aE(K) Therefore, the non-private TC challenger 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 AdaP-TT algorithm in the asymptotic regime of 5 0 (Theorem 6). In particular, shows that the cost of doubling and forgetting is multiplicative four-factor compared to the TTUCB algorithm, which achieves T (see Theorem 2.3 in [JD22]). We defer its proof to Appendix E.8.
Theorem 6 (Asymptotic upper bound expected sample complexity of non-private AdaP-TT), Let (6, B) E 1)2. Combined with the non-private GLR stopping rule (Equation (13)) using non non-private threshold functions functioon that, for all 1-sub- Gaub-Gaussian distributions v with means şa E RK such that min [H4 Hbbl O,
in Equation (14), the non-private AdaP-TT algorithm is 8-correct and satisfies
limsup 8-+0 log(1/8)
S <4T
where TKL.9 is the B-characteristic time for Gaussian distributions, such that
(Ma. )2a
(
max WEEK
=9 1/3 + 1 1/w
26

---

Private leader/challenger pair. pair cannot be used since it relies on the empirical means a..... which are not private. To alleviate this problem, we propose private leader/challenger pair which is based on the private empirical means a........
Since we want to ensure privacy, the non non-private leaderfchallenger
At time nu > K, the private UCB leader is defined as
Bn A arg max M.t..a + kn.a
Knna
+
(22)
[E[K]
akn.
eNNoa.a
where /n,a/ (aa/eeeee.. kn... .a) is a bonus to cope for the uncertainty due to the Laplace noise. It also depends on the current phase kn.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
Pk n., .r. Pkkn.a.a
On arg min az
(23)
VI/Nn,B. + 1/Nn,a
Likewise, the private TC challenger is chosen in adaptive manner, which is key obtain guarantees on the expected sample complexity of the private algorithm.
We derive upper bounds the expected sample complexity of the private AdaP-TT algorithm in the asymptotic regime + 0 (Theorem 5). We defer its proof to Appendix E.
Theorem (Asymptotic upper bound expected sample complexity AdaP-TT). Let (6, (0, 1)2. Combined with the non-private GLR stopping rule (Equation (13)) using non-private threshold functions as in Equation (14), the non-private AdaP-TT algorithm d-correct and satisfies that, for all bandit instances v with Hol O,
distributions and means E IR such that ming lP
[T(Ta]
(4T (1+ (1+V1+
A max
lim sup 8-0
(1/81
2e
where T TiI., (p) is the B-characteristic time for Gaussian distributions.
E Analysis of AdaP-TT: Proof of Theorem 5
Let B E (0, 1), E RJ, and v be a bandit instance consisting of K, 1-sub- Gaub-aann distributions with distinct means E RRK i.e. minazth |Ma /4l > 0. For conciseness, we denote A.
A Maa Pa.
A Amin minazt A.. and Amax & maXasaa* A..
For Gaussian distributions, the unique 3-optimal allocation ( (wr defined as
A
k (1)) A
arg max min WEEK =f agfa"
(24)
1/B + 1/wa
At equilibrium, we have equality of the transportation costs (see [JD22] for example), namely
A
Va x a",
1/B+1/w/ = 2T (1)
(25)
Our proof follows the unified sample complexity analysis Top Two algorithms from [JDB 222].
Let y O.
We denote by TH.y the convergence time towards w3. which is a random variable quantifies the number of samples required for the global empirical allocations Na/(n. - 1) to be y-close to w for any subsequent time, namely
N₂
T P.
A inf T
Vn > T
w/
(26)
The rest of Appendix organised as follows. First, we prove that AdaP-TT ensures sufficient exploration (Appendix E.2) Second, we prove that there is convergence towards the 3-optimal
27

---

allocation (Appendix E.3) in finite time. Finally, we conclude the proof of Theorem 5 (Appendix E.5). In Appendix E.6, we compare our asymptotic upper bound with our asymptotic lower bound on the expected sample complexity (Theorem 2). In Appendix F.7, we discuss the limitation of our result and pose an open problem. Appendix E.8 will detail the slight modification that needs be made in order to obtain Theorem 6.
E.1 Technical results
Before delving into the proofs, first recall some useful technical results extracted from the literature.
Concentration results. In order to control the randomness of (JE concentration result on the empirical mean of sub-Gaussian random variables and on sub-exponential observations (Lemma 7). Since Bernoulli distributions are //2-sub-Gaussian and the absolute value of a Laplace is an exponential distribution, Lemma applies to our setting.
standard
Lemma 7, There exists a sub-Gaussian random variable W y such that, almost surely,
log(e + NR...)
Va [K], Vkg N, [i Mpa Way
Nua
There exists sub-exponential random variable We such that, almost surely,
Va [K], Vkia E N, (Yk,,el S W. log(e ka) Nk.a
In particular, any random variable which polynomial in (We, Wy)) has a finite expectation.
Proof. The first part is a known result, e.g. Appendix E.2 in [JDB 22]. Let us define
W. A sup sup Nka (Ya.al aE(K] KNEN log(e + kia)
By definition, we have that, almost surely,
Ya E [K], Vki, E N, |Y S W. log(e + ka)
Nk
Since YY.il ~ E(c), Lemma 72 in [JDB 22] yields that W. is sub-ex sub-exxonential random variable. Since Wp is sub-Gaussian and We is a sub-exponential, any random variable which is polynomial in (W,, Wj) has finite expectation.
Inversion results. Lemma 8 gathers properties the function W -1, which is used in the literature to obtain concentration results.
Lemma 8 ([JK233). Let W-1(x) & -W-1(-e-")) for all x where W-1 is the negative branch of the Lambert W function. The function W-1 is increasing on (1, +o0) and strictly concave
on (1, +oo). In particular, W W_1(x=) = (1 ((x))
-1
for all x > 1. Then, for all y 2 1 and
W W-1(y) S
y V - (e0=log(z))
Moreover, for all x 1,
{
I + log(z) & W (-1(x)) S x + log(z) min
2 Vx
Lemma is an inversion result to upper bound a time, which is implicitly defined. is a direct consequence of Lemma 8.
Lemma 9. Let W-1 defined in Lemma 8. Let A > 0, B > 0 such that B/A + log A > 1 and C(A. sup fa A log + B}
Then, C(A, < (A, with h, = =W - (0/z / log z).
28

---

Proof. Since B/A + log A > 1, we have C(A, 2 A, hence
C(A, sup {= x < Alo
B} sup fx 2 Al x < Alog(z) B}.
Using Lemma yields that x 2 A Aog x
log
B
log
=
AW-1 (4 A
B
+ log A
A
E,2 Sufficient exploration
The first step of in the generic analysis of Top Two algorithms JJDB+22 is to show that AdaP-TT ensures sufficient exploration. The main idea is to show that, there are still undersampled arms, either the leader the challenger will be among them. Therefore, after 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 AdaP-TT, other choices of leader/challenger pair would yield similar results.
Given an arbitrary phase p E 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
5 = {a E [K] Nn.a 2 2p-1}
and a = arg max
(27)
oESH
Since minays |M Mul O, a is unique.
Let p E N such that (p- - 1)/4 N. We define the highly and the mildly under-sampled sets as _
U 2 {a [K] Nn,a 2((0-1//2 and V 2 {a E [K] Nn,a 23(m-11/4)
(28)
They correspond to the arms having not reached phase (p - 1)/2 and phase 3(p - 1)/4, respectively. Lemma 10 shows that, when the leader is sampled enough, it is the arm with highest true mean among the sampled enough arms.
Lemma 10. Let Sg and of as in (27). There exists po with E, [exp(opo)] +00 for all a >> 0 such that if 2 po, for all n such that St, # 0, B, E S implies that Bn 0 = arg m jkn..a
Proof. Let Po to be specified later. Let 2 Po- Let n E N such that St, + 0. where Sp. and 0 as in Equation (27). Let (Kn,a) be the phases indices for all arms. Since Nn. 2 2n-1 for all SP we have kn.a 2 p and Nkn.aia 2 2p-2 by using Lemma 3. Using Lemma 7, we obtain that
log(e + 2F-2)
W. log(e +
Pkn.ag an 2 Maz WaV
22-2
2x-2
log(e + 20-2)
+ W. log(e +D) Wa E Sh (ah)-
Dkna & pa + WT
2p-2
2p-2
Here, we use that - log(e + r)/r is decreasing.
Let Amin min à |m,- /1/. By assumption on the considered instances, we know that Amin 0. Let Pi = [log, Xi é) + 2 and P2 [lgg (052((22 ((X2 - -2)
2) log 2 + 1)] + 2 with
X1 = sup {
64A min W log e) < h1 (64A w e)
r
x S
8 - W. logæ +e 2 1/ log s h (8A W. log 4)
X₂ = sup
r
x <
log
where used Lemma 9, and f defined therein. Then, for all p N such that max(p1, p2) + and all n E N such that Sy * 6, we have jkk,.e a2 2 Mag Amin/ and Pbn.., Ma + Amin for all a E Sg \ (at), hence at = arg max Pkn,a.a- We have, for all R.,,
exp(ap1) S 30 23"(Xi e) hence E, [exp(app)) < t00,
29

---

where we used Lemma 7 and h1 (a, e) ~00 2 log x to obtain that exp(ap1) is at most polynomial in Wr,. Likewise, we obtain that E, (exp(ap2) < too for all R,.
Let us define the UCB indices by Inmee.a = Minmee + V /Km.a/ Namana + kn,a/ / (ENin...)). Using the above, we have
log(E + 2)
W. log(e +
Inmot 12 Mo, W
20-2
20-2
log(e + 2P-2) + W.
log(e +p) +
Va E Sh \ fa71, Ianaa Ha WMy
20-2
20-2
2
c2p
where we used Lemma 3 and the fact that log(e + x//xx and x x22- are decreasing function for x 2 2. Let p3- = [logg X31 + 2 and p4 = [log2 Xa] + with
X3 sup
644 min (log2 2) } h1 (644 min/ log 2, 1284
X4 sup
x
Sc - (log2 } S (8E // log 16 16Ammaa=")
where used Lemma 9, and h1 defined therein. We highlight that (p3, PA) are deterministic values, hence their expectation is finite. Then, for all E N such that 2 Po = max(p1. P2: P3, P1} + 1 and all n E N such that SE. * 9, we have Lem,ng . 2 Mag - Amin/ and Ikn...a S Ma + Aminn 2 for all E Sg \ { hence a = B, since we have B, arg ma) kn,
Since we have [exp((pp)) < +oo for all a E Rt, this concludes the proof.
Lemma 11 shows that the transportation costs between the sampled enough arms with largest true means and the other sampled enough arms are increasing fast enough.
Lemma 11. Let Sg and at, are in Equation (27). There exists p1 with Ey (e(e((pp))) < +00 for all a > O such that p 2 pv. all n such that SN + for all b 5% {at), we have
ahn oh i.kn,u.b
2 2n/2
// oz + +1NNkn.6.b
where C₂ > 0 is a problem dependent constant.
Proof. Let to be specified later. Let 2 Pl. Let E N such that St. + 0. where Sp and of as in Equation (27). Let (Kn,a)eE[K] be phases indices for all arms. Since Nn,a 2 2 for all E Sg,
we have k 2 p and Nu....a 2 2p-2 by using Lemma 3. Let Amin min |Ha Hol. which satisfies Amin by assumption the instance considered.
Using Lemma 7, for all b E SP. \ { we obtain
log(e + 20-2)
W. log(e + p) 2p-3
Mk ai M,n b Amin W
2--4
Let P3- [loge (X,
e)/4)] + 4 and P2 [lgg (X2 cc33loog + 1)7 + 3 with
X3 sup
> 1 x v 64A min W2 log e) < h1 (644 _² W c),
X₂ sup x. 1 x < 4A min W. log + + 3 1/ log 2 S hn (4A (45 m We, 5)
where we used Lemma 9, and h defined therein. Then, for all p E N such that p 2 Pl = max(ps,P2) + 1 and all n E N such that Sp & 0. we have, for all b Sp \ {
Dikning oz Pu..... 2 Amin/2.
As in the proof of Lemma 10, we obtain that [exp(ppp)) < too for all a R..
Then, for all & ST { we have
Mln as P.Nn...b
2 20/2 Amin
//NN Knnggaa at + 1/N NNn.ob
25/2
where we used that min N
Kniag No Ni 2 20-2, Setting C,2 Amin /2 yields the result.
30

---

Lemma 12 shows that the transportation costs between sampled enough arms and undersampled arms are not increasing too fast.
Lemma 12. Let Sh be as in Equation (27). For all p 2 1 and all n such that S + 0
Pkn.a.a P.
Va E S% vb $ 5%
S 2p/ P log(e + 20 2
V/NN + 1/NKo
where D > O is a problem dependent constant and (W jss We) are the random variables defined in Lemma 7.
Proof. Let p 2 1. Let E N such that S * 0. where Sh as in Equation (27). Let (kn,a) ((n,a)aE(K) be the phases indices for all arms. Since Nn,a 2 20 for all E Sh. we have kn,a 2 and Na....a 2P-2 by using Lemma 3. Likewise, Nu.a 2P-1 for all $ Sh, we have kn.a < p and Nkn...a <2P-2, Let Max = mingze IMa= Mol which satisfies mmax > by assumption on the instance considered. Using Lemma 7, for all E SR and b & Sh, we obtain
S V Nun.
(.k,,..6)
1/ I/Nu.an:a + +1/Nkn.ud
log(e + kn.b)
v Nknnoblla - mb) 2W, log(e + Nem. 2W.
V /Nuuab
2(r-2)/22 max 2W Vlog(e + 20-2) WW.log(e
where we used that Nk....h 2 1, kinb < p. No....b < 20-2 < Nam.. and x + log(e + +))//aaaa is decreasing, Taking D Amax/2 yields the result.
Lemma 13 shows that the challenger is mildly undersampled if the leader is not mildly under- sampled.
Lemma 13. Let VP be as in Equation (28). There exists p2 with E [x(exp((p22) < +o0 for all a > 0 such that p 2 p2, for all n such that Ug # 0, Br & Vp implies Cn V..
Proof. Let p2 to be specified later. Let 2 p2. Let n E N such that UE + 0 and V * [K], where UE S VI are defined in Equation (28). In the following, we suppose that B,, V..
be the phases indices for all arms. Let po as in Lemma 10. Let 6 = arg max ub. Then, for all p 2 4pa/3 1/3 and all n such that B, & VR. Lemma 10 yields that Bn = by arg max ".n.a...
Let
Let P1 and Cp as in Lemma 11, and D as in Lemma 12. Then, for all 2 maxx pr 1/3 1/3 and all n such that B, & VR. we have B,, by and
P.n.ig ba Pknn.
vb & Vp,
2 2(3p+1)/8
1/ Ne.. by 1/Nkm.n.
vb E UP
I 2(0+1)/4 Dr. + 2W,, log(e + 2(++2)/2-2)
V ///N N/N Ma 1/ 1/Ne..D.b
+ 2W, log(e + (p+ 1)/2),
where we used Lemmas 11 and 12. Let P3 = 16 logg (2D,, /C,) + then we have 1)/16) >
Dn
C
for all p 2 P3. Let p1 = 9
16
[log, X1 + 25 and ps
32
llog, Xs1 + where
9
W2
X1 = sup
x
x <
log(e + x 8/9
C
2W.
X5 sup
1 <>>
x S
log (e + 4 32 320
C
31

---

As in the proof of Lemma 10, using Lemma 7 yields that Ep (exp(ap=)) < +oo and Ey [x(e((paps)] < too for all a E R Let P2 max(p3, P4. Ps, max Pi 3/3 1/33 + that for all 2 p2, for all n such that B, $ VP, we have Bn bn and
Then, we have shown
Pkkm, on
min 1
max NEUR
1/NNm,a Ay 1/Nkm.o.h
V 11/Nanie Kan ty 1/ /NN..bb
Pen 2g Penbbe
Therefore, by definition of the TC challenger C,, = arg ming
we obtain
/ m.g og +1/N
that C, E V.. Otherwise, there would be contradiction given that assumed that UØ + 0. Given all the condition exhibited above, it is direct to see that E2 (cxp(ap2)] < +00 for all a > 0. This concludes the proof.
Lemma 14 shows that all the arms are sufficient explored for large enough n.
Lemma 14. There exists No with Ey [No] +os such that for all No and all E [K],
log(n/H) K)
Nn. 2 Vn/K K and kina 2 2 2
+1
Proof. Let po and p2 as in Lemmas 10 and 13. Combining Lemmas 10 and 13 yields that, for all
p 2 P3 = max [12, 4po/3 - 1/333 and all n such that Ug * 0, we have B, E Vi or Cn E VP.
We have [2
+00. We have 20-1 2 K23(p-1)/4 for all p 2 P4 = 4 K 1. Let
p 2 max P.
Suppose towards contradiction that Up k2 is not empty. Then, for any 15 K2 UP and Vi" non empty as well. Using the pigeonhole principle, there exists some [K] such that
Nge-1.a 2 23(p-1)/4 Thus, have V 2--1 S K 1. Our goal is show that V S K 2.
sufficient condition is that one arm in V is pulled at least 23/-11)/4 times between 2 and 2D 1.
Case 1. Suppose there exists a E Vi- such that Lar,a Lz 1,a 2
22(2-1)/4 1)/4
+ +3((23). Using
8
Lemma 6, we obtain
2 Nu 1,a 2 B(L20,0 L20-2,a) - > 23(p-1)/4
hence is sampled 28(2-1) 1)/4 times between 2p-1 and 2 1
Case 2. Suppose that for all a E Vp we have Izzra 1120-1,0 < <33(0-1))1) (0/p-11////88 3/(33)). Then,
Σ
(I2z,a Tozp-1,a 2 20-1 K (2310-1)/4 33/(2))
VE
Using Lemma 6, we obtain
Σ (N
No 1,)) - B Σ
(Ler,a - L20-1,a) S3(K - 1)/2.
agVP 2P-1
ag 12
20-1
Combining all the above, we obtain
Σ
(Lera 1,g
(N No
ag 12
OEVE
(1 3)
(Izr, L2g-1,a) -3(K- 1)/2
agV
GEVR
2P-1
2 (1 - 3) 1 K (23(0-11/11 + +3/(28)) 3((K - 11/22 K23(0-1)/11
where the last inequality is obtained for p 2 Ps with
ps = sup ppe / -3) (20-1 K ( 36 (23 1)/4 / 1B+ 3/(23)))
-3(K 1)/2 < <K236-1)/44
32

---

The LHS summation is exactly the number of times where an arm $ V was leader but wasn't t sampled, hence 2F
Σ
I (Be V I, = C+) ( K23(p-1)/4
2
For any 2 St 20 1, UP is non-emply, hence we have Br & V2 (hence Bg & VP) implies
C E VP" S V 2--1. Therefore, we have shown that
2 [1.EV
V 2--1)
Σ
(
20-1, It -.) K23(e-1/44
2=
2=
Therefore, there is least one in V 20-1 that is sampled 23(1-1)/1 times between 2 and 2"
In summary, we have shown 1V I K - 2 for all 2 Ps = max [P3. P4. Pt). ). By induction, for
any 1 < k & K, we have Vip
k2 I K - k, and finally U K2 = 0 for all 2 P6- Defining No K'2P--1, we have E, No) < too by using Lemmas and 13 for ps = max (p2, 4po 10003-1////
and 24 and Ps are deterministic. For all n 2 No. we let 2 K Then, by applying the above, we
have UP k Un (llo_((/K)-L is empty, which shows that Nn,a Z vn/K for all [K]. Using log(n/K)
Lemma 3, we obtain that k 2 2og
1 for all a E [K]. This concludes the proof.
D
E.3 Convergence towards 3-optimal allocation
The second step of in the generic analysis of Top Two algorithms [JDB+22] is to show that AdaP-TT ensures convergence of its empirical proportions towards the 3-optimal allocation. First, we show that the leader coincides with the best arm. Hence, the tracking procedure will ensure that the empirical proportion of time we sample it is exactly 3. Second, we show that a sub-optimal arm whose empirical proportion overshoots its 3-optimal allocation will not be sampled next as challenger. Therefore, this "overshoots implies not sampled" mechanism will ensure the convergence towards the 3-optimal allocation. We emphasise that there are multiple ways to select the leader/challenger pair order to ensure convergence towards the 8-optimal allocation. Therefore, while we conduct the proof for AdaP-TT, other choices of leader/challenger pair would yield similar results. Note that our results heavily rely on having obtained sufficient exploration first.
Convergence for the best arm. Lemma 15 exhibits a random phase which ensures that the leader and the candidate answer are equal to the best arm for large enough n.
Lemma 15. Let No be as in Lemma 14. There exists N1 2 No with E, [Ni] < +oo such that, for all 2 N1, we have àn Bn a*.
Proof. Let k 2 1 and (TA (Ta( in Equation (10). Suppose that E, [maxxe Ti((a) < +oo. Then, Lemma 3 yields that Nra(aj,a 2k-1 and Nr.e 2k-2, Using Lemma 7, we obtain that
log(e + 2k-2)
W. log(e + k) 2k-2
ak 2 Pa Wi
2h-2
log(e + +**-22
log(e + k) 26-2
Va + a" uka S Ho + W
+ W.
2k-2
Let pı = (X, e) 2 and p2 [log, (X2
1)1 2 with
X1 = sup fo > 1
x < 64A 2 2 log r + e} < hy (64A W H² e),
min
min
X₂ sup (x 1
8A W. log x + 1} h (8A We, + 1),
X₂ 2 sup {a > 1 x S 8A-1 min W. log(e + + logz))
where we used Lemma 9, and h1 defined therein. Then, for all & E NK such that min (K) ha > Po = max (p1,P2) such that E, [maxxee(]] TR, (a)] < +00, we have ji 2 Par Amin/ and ikka < Ma + Amin/4 /4 for all o a", hence a" = arg maxae[K] ik.a- We have, for all a E R.,
exp(ap1) S E²d0 ee2(Xx (Xi g//lgg
hence [x(ex((app)] < t00,
33

---

where we used Lemma 7 and hi (ax e) ~o-++00 z llog x: to obtain that exp(ap1) is at most polynomial in W Likewise, we obtain that By [exe(((a22) too for all a E R.. Therefore, we have Ey [exp(opo)] < +o0 for all a E R,.
Let us define the UCB indices by Is,a ju + y k//NRaa + k/(eNs,)). Using the above, we have
log(c + 2)
W. log(e + k)
k
Ik. 2 Pa- WN4
+
2k-2
2k-
e2k-2
log(e + 2)-2)
+ W. log(E + k)
k
Ya + a", IN S Ma + W
+
2
2
22k
Therefore, we have a' = arg [[{] Iia for all & E N such that min ha > max(pi, P2] such that Ey [m/ Tx, (a)] < to0.
Let No in Lemma 14. Using Lemma 14, we obtain that, for all n No and all a [K]
kn,a 2 log2 (n))(2/ + 1. Therefore, we obtain [i]] kn > max pp) is implied by
2 N1 max K (4mma((1.pp) No Using the above, conclude that E, [Ni] < +00 and
ā, = B, = a" for all n NN.
O
Lemma 16 shows that that the pulling proportion of the best arm converges towards B, provided the phase defined in Lemma is reached in finite time for all arms.
Lemma 16. Let 7 > O, and N₃ be as in Lemma 15. There exists a deterministic constant Co 2 such that, for all CoN1.
Nn.a.
n n- - B Sv.
Proof. y > Let Ni in Lemma 15. Let M Ni. Using Lemma 15, we obtain B,, a* for all 2 M. Therefore, we obtain Ln.a- 2 n M and Eazar Na S M for all 2 M. Using Lemma 6 yields that
N Nn.a
[N -BL,aal
In,a
+
Na
n,a
n
n
11
aza
2(M -
< 2(n 1)
+
<T,
n-1
where the last inequality is obtained by taking n 2 max (1/2 23(M - 1))//++10 1}.
Convergence for the sub-optimal arms Lemma 17 exhibits random phase which ensures that if a sub-optimal arm overshoots its 8-optimal allocation then it cannot be selected as challenger for large enough n.
Lemma 17. Let O. Let N₂ and Co be as in Lemma 15 and 16. There exists N₂ 2 CoN1 with E, [Na] < +o0 such that, for all n 2 N2,
Nn,a n
3a # a",
2 Wiaa +
C₁ + a.
Proof. Let > 0 and & > O. Let N, as in Lemma 15 and C as in Lemma 16 for ÿ. Let 2 CoNN. Nn.b n-1 > wHo for all
Let # a" such that & {a*, a). Then, for n 2 Co, we have
N..a > w + Suppose towards contradiction that n-1
Nn. n
Na,
1 - B +
7
Σ w3p = 11111
byfa
byaa
which yields a contradiction for 7 S 7. Therefore, for all n 2 CoN1. we have
Nn. 2 W3.a +
Nn.
3a + a",
3b fa a),
< W7.6
n
34

---

Then, we have
+ Nn. /Nn.b
+ (3 3//
+ Nu /N
+ (3+ + (w/
In the following, we use Lemma 7 and similar manipulations as the proof of Lemma 15. Therefore, obtain that, for all # a",
log(e + 24maa-2)
log(e + 2kn
a Minmere
Aol S W
2hnia--2
ckn.c-2
llogle + kn.a)) 2 -2
log(c + knn))
+ W.
2hn.c
Let Ps [log2 [X1 e)] + 2 and P2 [log2 (22
1)1 + with
X3 sup f 1
x - 1667- log r + }) s 11 (167 2 W
M e), x - 41j W. log c 1 - h1 - Wes e 1)
X₂ = sup x > 1
X2 2 sup { > 1
x - 4n logee + log
where we used Lemma 9, and 1 defined therein. We have, for all a E R+,
exp(aps) S 20n (Xs e) hence Ey(ex((ops]] < to0
where we used Lemma 7 and hı (z.e) to x log to obtain that exp(aps) is at most polynomial W,, Likewise, we obtain that Ev [exp(ap2)] < +oo for all a RQ..
Using Lemma 14 (with Co 2 Ni 2 No). we obtain that, for all n 2 Co, and all a E [K], kn,a 2 1ogg (n/K)/)(/)) K)/2 + 1. Therefore, we obtain min kn max P3} is implied by n 2 N2 = max [K max (pa,x))) No. Using the above, we conclude that E, [N2] < +oo and maxeşa" 1itk,... Mkk -Ael 17 for all 2 N2.
Then, for all n 2 N2. we have Bn a* and
Mi a" Ma
1+ No, /Nu.
A
1 + (B -5)/w/ 1,
1 Nn, /Nn,a
DS +1
1 (3 + 5)/(w3,, + 7)
where the last inequality is obtained by taking y) and sufficiently small and by using Equation (25), ie.
4
+ B/WB.0
A
+
3/W
Therefore, we have shown that Bn a
and
Wk aa VI/Na," 1/Na,a
hence
Cn + a.
V1/Nna" + 1/Na,b
This concludes the proof.
Lemma 18 shows that that the pulling proportion of the best arm converges towards 3 for large enough п. Lemma 18. Let 7 > O and Tun be as in Equation (26). Then, we have Ey [Tps]] < +00.
Proof. Let 0 and O. Let N2 as in Lemma 17 for 7. Let M 2 N2. Using Lemmas 15, 16 and 17 for all n 2 M, we obtain that B, = a²
N.,a* n-1
< 7 and
Nna 2 w +
3a # aa a", -
Cn $ a.
For all a # a², let us define ln,a (7) = max {1 M MSLSn n, Ne./(n - 1) < w3.a + +5]. Since
Nia/ (n - 1) < Ni.a((t (t - 1) for t & n, we have
Nn.a M + n
Σ
1 - -1
n n
L=M
35

---

M 1
N₁,a
11
<3 + It = Ct
L=M
M 1 Non,e (7),a
M -
+ 3 +
n
π 1
The second inequality uses Lemma 17, and the two last inequalities use the definition of tn (7). Using that EaE(K]
n-1 Nu.
EeE[K] WR,a obtain
N
Nn,a
M --1 =Wga - (K - 11 (
M
Σ
W3,6 + 7
π
n2
12
n
bga
Taking 7 //21(((K -))
and n max M, 2(K
1)( 1)/7 + 13 yields that
N₂
w/ 87.
n-1
Let Tn M.y in 26. Then, we showed that Tu.y max Ma,x 1-(M))))MMM/))) 11/7 Therefore, have
Eu[Tual S [max 2(K - () - 1)/7 7+ <
which concludes the proof.
E,4
Cost of doubling and forgetting
Compared to the generic analysis of Top Two algorithms [JDB+22] 22], for AdaP-TT, we need to control the sample complexity cost of doubling and forgetting. Due to this reason, we have to pay multiplicative four-factor: one two-factor due to doubling, and another two-factor due forgetting. is possible to show that this cost exists when adapting any "reasonable" BAI algorithm, meaning for any BAI algorithm in which the empirical proportions such that min, Wa > O. Those BAI algorithms are "reasonable" because the asymptotic lower bound stipulates that all arms have to be sampled linearly in order be near optimal.
converging towards an allocation
Let E Σg be any allocation over arms such that min, Wa > Let > 0. We denote by Tua (w) the convergence time towards w, which is random variable quantifying the number of samples required for the global empirical allocations Nn/(n ( - 1) to be 7-close to w for any subsequent time, namely
(w) & inf {
{ 1
Nn
Vn 27, T,
5
(29)
Lemma shows that the phase switches of the arms happen in a round-rohin fashion, which means that an arm switches phase for second time after all other arms first switch their phases.
Lemma 19, Let w E Σg such that min, Wa > O. Assume that there exists 7 > 0 such that for Ep (T (w)] < too for all y E (0, Yu), where (w)((w) is defined in Equation (29). Let 0. There exists Ta E (0,7)) such that, for all y E (0, Jn), there exists N3 2 Tun((w) with [Na] < t00
which satisfies
max K] TR.. (a) 1
Vn 2 No.
min Tkn, (a) - 5 22+
Proof. Let 1 > O. Let 7/ E (0, 7/) such that 2 max,e [n]x + 7)/(ws -7) < 2 + n, which is possible since min, Wa 0. Let y E (0, Rp)) By assumption, we have E, [w)] < +00. Then, for all n 2 (w),
N₂ n-1
w S7.
w
Let M 2 TT, Te, (w). Let use denote by hMs (kM,a)eEjK) the current phases for all arms [K] time M. Then, for all > M and all [K], we have No.o (n 1)(wa 7). Therefore, taking
36

---

2 [ 2b (wa -7--1 + 1, we obtain that Nn.a 2 2 for all a E [K], hence we have [aX +1sx S n. Since minae x) Th Tim,o+1(a)) 2 M, we have
max KE(K]
Wa S7.
7-
Likewise, taking n 2 [ 2 (wa - -7)=1 1 + 1, we obtain that Nn,a 2 2 for all E [K], hence we have ma Th Tkm +2(() I n. Let a1 = arg min [X] T +2 By
definition and using Lemma 3, we have
2
+2(1),, I a +2((1) - 1) + +)),
Ya + 01, 2k < NTMM (2(01).a S (Tku,t +2( 1)(wa + +7)-
Let 02 arg a Th +2(). By definition and using Lemma we have 2kM +1 NT NeM. slas)iaz 2 (TkM, +2(02) 1) 7)
Therefore, combining the above yields
(TRM,g +2( S (TKM. +2(a1) 1)2 Waz + S (TRM.ng +2( ) 1)(2 + 11),
Wag -7
where the last inequality uses that 7 (0, 7x) and 71 (0, 7/u) is such that max (We 7)/(w, - 7) < 12277 17. We take 2 N3 = ma] +2(), hence we have kn,a 2 kM + for all a E [K]. Since E, [T p. (w)] < too (i.e. arms are sampled linearly), it is direct to see that Ep [max +2()) < +o0. This concludes the proof.
Note that TH, defined in 26 is such that Tn.7 TH.y (L where (H, in Equation (29). Lemma 18 showed that E2, [Tun] < +o0 for all y 0. Therefore, the condition of Lemma 19 fulfilled by AdaP-TT.
E.5 Asymptotic expected sample complexity
The final step of the generic analysis of Top Two algorithms [JDB+22] is to invert the private GLR stopping rule by leveraging the convergence of the empirical proportions towards the 3-optimal allocation. Compared to the non-private GLR stopping rule, the private threshold in the private GLR stopping rule involves an additive term in (log(1/6)") This difference is the largest price that we pay to obtain private BAI algorithm. We defer the reader to Appendix E.7 for more detailed discussion on it.
Asymptotically 8-optimal c-DP-FC-BAL algorithm. The inversion of the GLR stopping rule by leveraging the convergence of the empirical proportions towards the (3-)optimal allocation is a generic method used in the BAI literature. Provided this convergence is shown, it only depends on the threshold that ensures 5-correctness. More precisely, only depends on its asymptotic dependence in (og(1/8). In addition to the multiplicative four-factor, the price of privacy for asymptotically 3-optimal BAI algorithms when combined with the non-private GLR stopping rule is problem dependent multiplicative factor + /1 / (2e2) (Lemma 20).
Lemma 20. Let (ô, B) E 1)2, Assume that there exists "Ip > 0 such that for (Ta < +oo for all Y (0. 72), where Tuu is defined Equation (26). Combining the private GLR stopping rule (Equation (16)) with private threshold (Equation (4)) yields a 8-correct algorithm which satisfies that, for all with mean a such that la" 11)]=1,
log(1/8) S (1)))((H)) ( 1+ V1
E2 [T8)
A max
lim sup 8-+
2
Proof. Theorem 4 yields the d-correctness.
37

---

Let a" be the unique best arm, i.c. a²(()) {a*}. Let Ç > 0. Using Equation (25) and the continuity of
(1a)(1)) - Haa2
(H,, w) H
min
afa" (14) 2(1/ (L/ + 11/wa)
yields that there exists 7c such that implies that
N. n-I w// S 7c and maxae[K] Mknn++ - Mal S 7c
(ikn,ut-L,a"
- ikkn +1,a)
2)1-5)
Va aa'
(n /N + (n 1)/Nn,
n
n n-
1
42
(1 1.++)22 +S)
Nn.a
Nn,a
2
We choose such a ".. Let 7/4 > 0 be such that for Ev [u] < +o0 for all Y E (0, Ya), where T Tun
defined in Equation (26). Let > 0. Let 7/2 (0, 7n)) as Lemma 19 for this 1). In the following.
let us consider E (0, min 8/. A min/ 3mmn/44) /4]).
Let N3 2 Ju,y with Ep [Na] +0 as Lemma 19 for those (7, Then, we have Ey [Tyyy to0 and
m Ten (a) -1
Vn 2 N3.
[ik Thn Kmn, (a) 21
Since arms are sampled linearly, it is direct to construct N4 2 N3 with [N < +oo such that, for all n 2 N4. we have maXae[K] max (an [ūR. - Mol S 7, Therefore, we have å, a²
Let (0, 1). Let n 2 Na/1 i and (Kn,))E[K] be the current phases at time n. Combining the above, we have 0N = a* and
N₂ - w/)
S and maX Tkn, (a) 1 - n minag [K] Tkn. (a) (a) -
max | Pknatla Mal sy aE[K]
n
Let 01 arg min Tkma (a) and a2 = arg a Thn. (a). Therefore, we obtain, for all + a",
(ihnaar "innn (1.m)t1aa)) +1,a) 1/NTe,, (a))ar + 1/N Thn. (a), (Dimmat +h,a Pukn t
1/ 1/Nkn.ant +laen 1/Nkmot1e
1 //NTo. (a1)ae* A/NTmmie (01))a
2 ( min Te (a) - 1) 2(1 - ()
aE(K]
T KL. (14)
Similarly, we can show that, for all a + a*
Ninath.0
NT (a*)
N NTnne (a),
Nrenee (as),a*
NTw. (a1).a
2
(1 + C)T
minae[K] Tkn. (a) -
2
A
max
(1 + ()I
millae]]] Tk (a) 2
Let (CK)kEN as Equation (14). Using Lemma obtain, for all a a a"
20 +1)(km +1) (N 1,at, Nowa +1, 8/2) S log(4 + (max kin.b 1) log he(k]
+ 4Co log(1/6)/2 + log( max knn 1) + 1og -1)(()))//2
bE(K]
38

---

Likewise, we obtain, for all E [K],
1
2K(knn + 1)))()))
2K [2K(nn. + {())
log
log
"kma++1aate
6
+1
A max
(1 (()
2ea minbe[K] (b) -1 (log(1/8) + s slog(max max kn.d + 1) + (log(K((())) bE[K]
Let us denote by T k,+1 = [a Tk (1)), Th.t2 = ma Tk (2)), Th =
minbe[k] 1 (b), TE., = mimbe[k] Thn. (b). Let T be a time such that T 2 T k, 2 KT.
Using Lemmas and 19, we have
(kn,b - 1) log 2 = log (6).b I log TogTT.. (b) S log To, S log + log(( (2 + 11)
Using the private GLR stopping rule (Equation (16)), we have
min (rs, T) xT S
Σ
(T Th 1 (T8 T k(,+t)
T2T2, 2NT
(Ti kn+2 +2 - Tht +1 Fa (Uimart1,0" - (Mma+1.00)
Σ
1/Nk + 1/N Namatlla
T2T,, kn 2nd
Kn + +l,nn, +1 +1 (Nknan N NNknotta:8)
(T+ khtt2 - -ht -1ll (Th, -1) (Th--
1-5 < 88log(4 + log TT, + +log(2 + n))
TKL.
T2T 2NT
+ 4Ca (log(1/5)/2+ + log(2 + logo Te, + +log2 (2 + 11)) +
A 2 max
(1+ (1t))RRL, (log(1/0) + log(( + log TT, + 1ogg + 7)) (og(2
26a
T
Let (6) defined as the largest deterministic time such that the above condition is satisfied when replacing Th by (1-x)T. Let kg be the largest random vector of phases such that that T S TT(()) almost surely, hence T T (o)
almost surely. Then, using the above yields that S T k2+2
almost surely, hence
[T(
E E S (2+m)² lim 8-30
ET & (2+n)² lim sup log(1/0)
(e
lim limsup sup 8-30 log(1/8) S limsup sup 8-00
log(1/8)
log log(1/8)
8-:0
where the second inequality uses Lemma 19 twice, i.e. Thi+e I (2 + T) S (2+ T T k1+1' and the last one used the definition of ki and that (ō) is deterministic.
Since we are only interested in upper bounding lim sups-0 log[1/8] we can safely drop the sec- ond orders terms in T and log(1/5) This allows us to remove the terms in O(log logT) and in Olog log(1/))). Using that Ca(x)) = x + O(log x)), tedious manipulations yields that
Tz(o)
lup (5) 8-0
< T
1 De(H,)),
log (1g(1/))
where
De(m,e) = sup { 22
2
1 1 5 A2 max
1 ( 1+ V 11 (1-(2) s $
A Amxx
<
x +
1 (
1- 2e
2c
The last inequality uses that x² 2hx have shown that
for all x E [0,b(1 v (1+cl) c/b))) Therefore,
Ep [8]
(1))
22 1+ 11+110 1+ (1 (2)
lim sup 8-40
log(1/8) < x2+
(1 - (1-))(100) (1
2
39

---

Letting K, 17 and ç goes to zero yields that
lim sup 6-+0
En [aa]
S e(
1+ 1++1+
A
max 2e
log(1/0) (/0)
Concluding the proof of Theorem 5. Combining Lemmas 14, 18, 19 and 20 concludes the proof of Theorem 5. We restrict the result to instances such that minayt 114, - /uol > 0 in order for Lemma 14 to hold. Note that this is an artifact of the asymptotic proof which could be alleviated with more careful considerations.
Asymptotically optimal c-DP-FC-BAL algorithm. While Lemma 20 is derived for BAI algorithms converging towards the 3-optimal allocation ( , it is direct to see that a similar inversion results can be obtained for BAI algorithms that converge towards the unique optimal allocation WkL (4) = {w*) defined as
A arg max min A3 weEx aptan
WKL(H)
(30)
1/w6- + 1/wa
At equilibrium, we have equality of the transportation costs (see [JD22] for example), namely
A
Ya aa,
2TRR. (n)
(31)
1/W + 1/w
In addition to the multiplicative foutor the price of privacy for asymptotically optimal BAI algo- rithms when combined with the non-private GLR stopping rule is problem dependent multiplicative factor 1 + /1 + / (262) (Lemma 21). We omit the proof since it is the same the one of Lemma 20.
Lemma 21. Let ő E (0, 1) Assume that there exists P/p > O such that for Ey [T (
(w*))
< +00
for all (0, %,), where T u. (w) is defined in Equation (29) and w is defined in Equation (30). Combining the private GLR stopping rule (Equation (16)) with private threshold (Equation (4)) yields 8-correct algorithm which satisfies that, for all v with mean μ such that la" (1)) = 1,
Ev [Ta]
A 2
lim sup sup 6-20 log(1/8) S (H)
1 [1+1+
2
E.6 Connection to the lower bound
In this section, we compare the sample complexity lower bound of Corollary with the sample complexity upper bound of Theorem 5.
Simplification of the upper bound. (Theorem 5) is upper bounded by
The asymptotic expected sample complexity of AdaP-TT
Ep [Ta] 8-+0 log(1/0)
A 2
lim sup
S 4T
1 1+
v 1+
2e
Amax
4T 4
2
22c 2c
where T (14) is the f--charccteristic time for Gaussian bandits, and (a) is due the sub-additivity of the square root.
For 1/2, [Rus16] showed that T (H)) S (p).
On the other hand, [GK16] showed that H()) < TRi (1) < <HH(u), where H(μ) Eng(K] 2A
with A.t Amin-
40

---

Plugging these two inequalities in the upper bound of Theorem 5 with | = 1/2 gives that
E2 TA log
Amax
lim sup
(1/0) S ( 16H (1))
6-2
22
Since we consider Bernoulli distributions, we know that 0 < ourselves to instances such that all the gaps have the same order of magnitude (Condition 1); there exists constant C 2 1 such that Amax S C'Amii
Amin I Amax < 1. If we restrict
For such instances, we obtain
Ey [T8]
CAmin
lim sup sup 6-2
8L.1122(11) (1H
1og(1/5)
V2E
s kL + 16
Σ
Amin
Au
where the last inequality is due to (p) S 2 + Lam Da
Amn
Finally using that b S 2 max(a, (a, b), we get that
E2 [68]
I <emax TTLA)2(M)) C
-
1
K
lim sup
log (1/6
A
Du
6-+0
for the universal constant 45.26.
The lower bound for Bernoulli instances. For Bernoulli instances, Corollary gives that the lower bound of the expected sample complexity of any 5-correct e-global DP BAI strategy is
E2 [Ta] (1/6)
K
lim sup 5-00
2 max TKL((), 6e Amin
Σ
a=2
where we use Proposition to replace Tiv(v) and Tiu (v) is the characteristic time for Bernoulli bandits.
Upper-lower bound discussion for the two privacy regimes. In the low privacy regime, our upper bound retrieves T / for Gaussian distributions. Since the rewards in the analysis are supposed Bernouli,, the mismatch from exact optimality is coming from the mismatch between the KL divergence of Bernoulli distributions and that of Gaussian, which is generally controllable in most instances where the means are far from the borders, i.e. 0, and 1. This is in essence, similar to the mismatch between UCB and KL-UCB in the regret-minimization literature (Chapter 10 in (LS20]). To overcome this mismatch, is necessary adapt the transportation costs to the family of distributions considered. In our setting, this can be done by using the Bernoulli KL rather than Gaussian KL in lines 12 and 16 of the algorithm. While the Top Two algorithms for Bernoulli distributions have been studied in [JDB + 22), the analysis is more involved. Therefore, it would obfuscate where and how privacy is impacting the expected sample complexity.
In the high privacy regime, and for instances verifying Condition 1, our upper bound matches the lower bound e (T)) up constant. Having matching upper and lower bounds only for high privacy regimes is an interesting phenomenon that appears in different settings of differential privacy literature, such regret minimization [AB22], parameter estimation [CW721] and hidden probabilistic graphical models [NKS19]. We speculate two facets of this phenomenon:
1. Explicit bounds in high and low privacy regimes: We have matching bounds only in the high or low privacy regimes because the lower bounds are generally harder to explicit and understand in transitional phases. Thus, it is harder to claim optimality in those phases.
2. Information- cooommttion-thooeticc theoretic roots: There might be more profound information -eooraation--hooettic reason in relation to [NKS19]. Indeed, there seems to be a link between the privacy budget and the information thresholds introduced in [NKS19]. Specifically, the randomized mapping in [3] satisfies DP, then the noisy information threshold and noiseless information threshold can be similarly written as a function of e and the total variation. Finding a rigorous link between these two quantities an interesting question to explore.
41

---

E.7 Limitation and open problem
In the previous section (Appendix E.6), we argue that the upper and lower bounds match up to multiplicative constants in both privacy regimes, provided we restrict ourselves to instances satisfying Condition 1 (i.e. there exists C' such that mmax I CAmin).
While this holds for numerous instances, it does not account for instances in which the gaps have different orders of magnitude. One example would be the regime where Amin 0 while Amax is fixed, hence yielding (p) +00.
In Appendix E.5 (see Lemma 20 and 21), we show that combining the private GLR stopping rule (Equation (16)) with any BAI algorithms whose empirical proportions converge towards the 3-optimal allocation W (p) for Gaussian bandits will incur problem dependent multiplicative cost
2
max
(32)
2r
in addition to the multiplicative four-factor due to doubling and forgetting.
In order to have matching upper and lower bounds, we would need to have Amin instead of Amax in Equation (32). Unfortunately, our results show that it not possible when using the private GLR stopping rule (Equation (16) and a sampling rule that is tailored to asymptotic ( (B--)optmmllity for Gaussian bandits. Therefore, this impossibility result holds for large class of BAI sampling rules when adapting them to tackle private BAI by using the private GLR stopping rule (Equation (16)).
Origin of this limitation. The term Amax appears due the private stopping threshold that ensures d-correctness of the private GLR stopping rule (Equation (16)).
For asymptotically (8-)optimal algorithms, the additive term due to privacy in the threshold is of the order
1
1 11++
1
log(1/6)2 +000 T (1) 4
+
2 log log(1/0)².
Nn.a
Nn..
Therefore, the private GLR stopping rule (Equation (16)) will stop when, for all aa"
n
2 2log(1/0)
(k)(H) A
log lgg(1/))
2
KT.
which yields the problem-dependent multiplicative cost +
A2 2c
Open problem. This impossibility result specific the way we derive an c-DP version of the GLR stopping rule. Therefore, a natural question is whether it is possible to derive a better private GLR stopping rule match the lower bound for all Bernoulli instances.
A two-phase algorithm. AdaP-TT tracks the non-private lower bound (i.e. Tk as non-private algorithm would do, and the additional cost tracking that privately is shown to be Ti /e (up to constants for bandits verifying Condition 1), where the additional cost comes from the added Laplace noise. Another approach would be first perform test to determine in which privacy regime the policy resides, and then track (privately) the corresponding characteristic time. Such an algorithm would empirically estimate both Tjy and T L in the first phase. If the privacy budget is bigger than the empirical estimate of Tiy/Tk then this means that we are in the low privacy regime and the algorithm tracks (privately) the KI characteristic time in the second phase (as AdaP-TT does). However, if the privacy budget is smaller than the empirical estimate of Tiy/Tkk L then is the high privacy regime and the algorithm tracks (privately) the TV characteristic time in the second phase. For such a two-phase algorithm to achieve optimality, properly tuning the amount of time spent in its first phase is a crucial step. Whether it is possible to analyze such an algorithm and quantify the proper tuning (if it even exists) is an interesting direction for future work.
Non-asymptotic sample complexity of AdaP-TT. In the non-private FC-BAI literature (i.e. e +o)), there is light lower bound in the non-asymptotic regime (i.e. for any value of 8). This is the main open problem in FC-BAI, and hence in DP-FC-BAI too. the class of asymptotically (3- Optimal algorithms, TTUCB [JD22] is one of the few to have aon-asympt guarantees. Adapting
42

---

the non non-asy asymptotic analysis of [JD22] to the private AdaP-TT's is an interesting direction for research. We conjecture that such an adaptation is possible (up technicalities) by adding concentration terms linked to Laplace distribution and losing at least multiplicative four-factor compared to TTUCB due to doubling and forgetting.
E.8 Analysis of non-private AdaP-TT: Proof of Theorem 6
The proof's detailed in Appendices E.2 and E.3 can easily by adapted to provide guarantees on the non-private AdaP-TT, which relies on the non-private leader/challenger defined Equation (20) and Equation (21).
The key difference between the non-private T and the private AdaP-TT lies in the definition of the stopping threshold. While the private GLR stopping rule (Equation (16) has an additive terms in (log(1 ((l))(1/8))//0 /e) to cope for the uncertainty due the Laplace noise, the non-private GLR stopping rule (Equation (13)) scales simply as log(1/5) This has drastic consequences in terms of asymptotic upper bound on the expected sample complexity.
It is direct to see that most manipulations from Appendix E.5 still holds for the non-private AdaP-TT. Therefore, we use the notations and conditions defined therein. We show that the non-private GLR stopping rule (Equation (13)) yields
min { (Ts: T KT
Σ
(Tut2 Tht +1+ (Ta Th, Th,+t2)
T2T!, 2xT
kxt2 - T kn+1) 1 3a + a" (At +ha t1at Pi +l,)
Σ
(T+
1/Nemarrla" + 1/ L/Nk.... NN +he
T2T 2xT
< (k a + +1)(kt,.+1))N (Nr. th, No. +1,a, 6)
kat2 - thttt) I (Tz, - 1) 1 1-c < 4log(4 + log Tr. + log(2 + n))
< Σ
(T
T (
T2T 2NT
+ 2C (log(1/8)/2+ + slog(2 + loga Tw, + 12 1)) + loo((ooK 1A/K--1660 1){())))22)
Let (ō) defined as the largest deterministic time such that the above condition is satisfied when replacing T by (1-x)T. Let kig be the largest random vector of phases such that that T k S (6) almost surely, hence T > (ō) almost surely. Then, using the above yields that T3 S T k2+2 almost surely, hence
Ep [78]
E, ET 22 log(1/8) 8-40
Ey ET R & (2+n)² lim sup 8-4
Te(6) log( (o(()
lim simsup 8-40 log(1/8)
S lim sup
S (2+n)² sim 80
log(1/0)
T only interested in upper bounding lim sups-o [og[1/5] we can safely drop the second orders terms in and log(1/8). This allows us to remove the terms in Olog log and in Ollog log(1/8)). Using that Ca( = O(logr), tedious manipulations yields that
First-order terms.
Since
Te(
(k)
lim sup 8 log(1/8)
<
(1 (1-x)
Letting k. 1) and ç goes to zero yields that
E, [TA] log(1/8)
limsup 8-10
< (H).
43

---

Extended experimental analysis
In this section, we perform additional experiments to compare AdaP-TT and DP-SE for FC-BAI. We test the two algorithms in six bandit environments with Bernoulli distributions, as defined by [SS19]. namely
J41 (0.95, 0.9, 0.9, 0.9,
J22 (0.75, 0.7,0,077777
J4 (0, 0.25, 0.5, 0.75, 1),
μ4 = (0.75, 0.625, 0.5, 0.375,,,,,0222
μ45 (0.75, 0.53125, 0.375, 0.28125, 0.25),
μ48 (0.75, 0.71875,, L..62,,0446777 0.25))
For each Bernoulli instance, we implement the algorithms with
6 E {0.001, 0.005, 0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0,9,
and a risk level 5 = 0.01. We verify empirically that the algorithms are 8-correct by running each algorithm 100 times. In Figure 2, we plot the evolution of the average stopping time and standard deviation with respect to the privacy budget e. All the algorithms are implemented in Python (version 3.8) and are tested with an 8-core 64-bits Intel i5 1.6 GHz CPU.
All the experiments validate the same conclusions as the ones reached Section 5, i.e.
1. AdaP-TT requires fewer samples to provide d-correct answer,
2. there exists two privacy regimes, and in the low-privacy regime, the sample complexity is independent of the privacy budget.
44

---

10
High Privacy Regime
TTUCB
TTUCB
High Privacy Regime
AdaP-TT
AdaP-TT
DP-SE
Stopping Time
10a
Stopping
Low Privacy Regime
10
Low Privacy Regime
10a
10a
10
10
10-1
10a
10
10
10-1
10a
10a
Privacy Budget
Privacy Budget
(a) fA1
(b) 112
High Privacy Regime
TTUCB AdaP-TT
High Privacy Regime
TTUCB
AdaP-TT
10a
Stopping Time t
Stopping Time
Low Privccy Regime
10a
Low Privacy Ragime
10a
10*
10a
10
10
10
10
10
10
10
10a
101
Privacy Budget
Privacy Budget
(c) pAa
(d) p4
High Privacy Regime!
TTUCB
High Regimo
TTUCB
AdaP-TT
AdaP-TT
10a
Stopping Time
Stopping
Low Privacy Regime
10a
Low Privacy Regime
10a.
10a
10
10
10
10a
101
10
10
100
101
Privacy Budget
Privacy Budget
(c) μAB
(1) 146
Figure 2: Evolution of the stopping time 7 (mean + std. over 100 runs) of AdaP-TT, DP-SE, and TTUCB with respect to the privacy budget for 8 = 10 on different Bernoulli instances. The shaded vertical line separates the two privacy regimes. AdaP-TT outperforms DP-SE.
45


Reviews:
[{"review_id": "8Bkij9mQje", "reviewer": "Reviewer_NTgq", "summary": "This paper studies the problem of best arm identification with fixed confidence under ϵ-global Differential Privacy. First, they provide a lower bound of the BAI-DP problem showing that two different regimes depend on the privacy budget of $\\epsilon$. They propose an ϵ-global DP variant of the Top Two algorithm, called AdaP-TT, and provide its asymptotic sample complexity. They also conduct experiments that confirm the theoretical validity.", "questions": "Could you provide comparison with [Rio et al 2023]?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "(originality) \n\n-They first derive the hardness result giving a lower bound for the problem of best arm identification with fixed confidence under ϵ-global Differential Privacy.\nFor the high-private regime, the lower bound depends on the Total Variation Characteristic Time, which shares a similar spirit with the regret minimization with ϵ-global DP [AB22]. For low-private regimes, the lower bound reduces to the classical no-private lower bound.\n\n-As an algorithmic contribution, they devise variants of Top Two algorithms, called AdaP-TT, based on non-private TTUCB[JD22]. They propose a sample complexity in an asymptotic regime, which is the order-optimal up to some constants.\n\n\n(quality) The paper is well-structured and easy to follow.", "weaknesses": "-As discussed in the paper, in BAI setting the only Information is leaked when publishing all the sequence of actions $\\{a_s\\}_{s<t}$ and the final recommendation a^*, which might not be frequently common situations, since BAI setting, the decision of final output is more interested. The presented problem is more of an artificial problem, although theoretical results are valid and new insights. \n\n-Related above, the privacy issues should be more important for the case where multiple players may exist rather than only a single player is involved, as in federated learning. With regard to multi-agent bandit problems, recently the following paper studied the best arm identification with DP setting and propose the DP successive elimination based on [SS19].\n\n\n [Rio et al 2023] Multi-Agent Best Arm Identification with Private Communications.\nAlexandre Rio, Merwan Barlier, Igor Colin, Marta Soare. Proceedings of the 40th International Conference on Machine Learning, PMLR 202:29082-29102, 2023.\n\n\nI believe that a comparison with this paper should be required before the publication, even though [Rio et al 2023] might have been public after the NeurIPS submission date (So lacking this comparison in the current is not the reason for rejection). \n [Rio et al 2023]  consider a lower bound but only for the extreme non-private setting, where agents share all their raw reward samples with the central coordinator. Therefore, the submitted paper’s analysis for lower bound might be still novel. However, DP successive elimination proposed in [Rio et al 2023] could cover the single agent BAI-DP. Therefore the authors could do a comparison with this paper.\n======After rebuttal======\nMy concerns are fully addressed. Hence I changed my score from 5 to 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the constructive feedback and the interesting questions.\n\n**Real application motivating privacy at the level of intermediate actions and the single-agent setting.** We respectfully disagree with the assessment of the reviewer regarding the practical grounding of the setting studied in this work. Considering privacy at the level of intermediate actions for a single agent is **not** an artificial problem. It is based on a real-world application of adaptive dose-finding trials (see Example 1 in lines 39--50). \n\nFirst, in many small-scale clinical trials, only one physician decides on which dose to give to a patient taken from a local pool of volunteers. Therefore, it is truly a single-agent setting. While the multi-agent setting and federated learning can tackle large-scale clinical trials taking place at several locations simultaneously, we also need to provide tools for small-scale ones. \n\nSecond, both small-scale and large-scale clinical trials have to publish their experimental findings in order to obtain the right to sell their medicine. This can be done publicly through a medical journal, or confidentially by providing the necessary information to local/international health authorities. The experimental findings of a clinical trial are not reduced solely to the final recommendation $\\hat a_{\\tau_{\\delta}}$, and the scientists need to detail the experimental protocol. This includes the dose allocated to each patient, which are the intermediate actions $(a_t)$ for ${1 \\leq t < \\tau_\\delta}$. Since every application of a dose level and the patient's reaction to it exposes information regarding the medical conditions of the patient, privacy has to be enforced at the level of the intermediate actions too. Indeed, one may propose another definition where the policy only publishes the final recommendation and the intermediate actions are supposed to be \"hidden\". This boils down to defining different trust barriers. \n\nIn our definition, the adversary may look inside the execution of the policy and see the intermediate actions as well. This can be seen as a version of pan privacy [1] and thus would protect against intrusions too. Thus, it is clear that our definition provides better privacy protection and is well-motivated. On the other hand, we agree that an interesting future question may be to see what could be gained in sample complexity if only the final recommendation is published. We would mention it as a possible future work.\n\n\n**Comparison to [Rio et al 2023].** We thank the reviewer for pointing us to [Rio et al 2023]. At the time of the submission, we could not be aware of this concurrent work which was published in ICML this year, i.e. two months after the submission for NeurIPS. On the other hand, [Rio et al 2023] studies a different setup, with multiple agents, while our work is on a single agent. The proposed algorithm in [Rio et al 2023] is a generalisation of DP-SE from single to multi-agent. Since we provide a full theoretical and experimental comparison of our algorithm AdaP-TT compared to DP-SE, we already present the comparison with the single-agent version of the algorithm of [Rio et al 2023]. Here, we provide a statement that we would like to add in the Related Work section while referring to [Rio et al 2023]:\n\n\"\n[Rio et al 2023] also studies privacy for best arm identification under fixed confidence but for 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.\n\"\n\nHope we have addressed your concerns. Let us know if you have any further comments.\n\n[1] Dwork, Cynthia, et al. \"Differential privacy under continual observation.\" Proceedings of the forty-second ACM symposium on Theory of computing. 2010."}, {"review_id": "v1TqjBL1DL", "reviewer": "Reviewer_Z6yo", "summary": "This paper studies the problem of BAI with fixed confidence under ϵ-global Differential Privacy (DP). The authors derive a lower bound on the sample complexity of any δ-correct BAI algorithm satisfying ϵ-global DP. In addition, the authors also design an ϵ-global DP variant of the Top Two algorithm, named AdaP-TT. AdaP-TT runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. The authors provide an asymptotic upper bound on the sample complexity of AdaP-TT, which matches the lower bound up to multiplicative constants in the high-privacy regime. Finally, the authors also conduct experiments to validate their theoretical results.", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1.\tThe studied problem, differential privacy in best arm identification, is interesting and finds applications such as clinical trials and hyper-parameter tuning.\n2.\tThe provided lower bound result is very interesting. The authors give a deep discussion on the problem hardness in two regimes. In the high-privacy regime, the hardness depends on a coupled effect of privacy and a novel information-theoretic quantity, i.e., total variation characteristic time. In the low-privacy regime, the sample complexity lower bound is the same as that in classic (non-private) best arm identification.\n", "weaknesses": "1.\tThe writing of this paper should be improved. This paper is very dense and difficult to follow.\n2.\tThe authors only provide asymptotic sample complexity for their algorithm AdaP-TT. Can the authors provide a non-asymptotic sample complexity, or give some ideas?\n3.\tCan the authors discuss the technical novelty compared to existing works on DP with regret minimization? What is the unique challenge brought by the best arm identification setting?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and kind words concerning the importance of the derived lower bound.\n\n**1. Dense paper and difficult to follow.** The paper investigates private BAI and draws on very recent developments in both fields (like AKR21, AB22, JDB+22, JD22 etc.). As a result, we understand that the non-experts in either of the fields may find the paper difficult to grasp. Thus, even under the space constraint of the submission, we tried to provide proof sketches, connect the relevant results, and discuss the consequences of every theoretical result.  Using the extra page in the final version, we will focus on the paper's presentation by providing additional context for the non-experts in both domains, namely differential privacy and best arm identification, as well as offering more intuition behind the various results and proofs.\n\n**2. Non-asymptotic sample complexity of AdapTT.** Please refer to the general comment for a detailed response.\n\n**3. Technical novelty.** Please refer to the general comment for the technical contribution.\n\nWe hope that our response addresses the reviewer’s questions. We look forward to responding to further queries."}, {"review_id": "TSrnwhSaah", "reviewer": "Reviewer_Qtw8", "summary": "This work provides novel theoretical guarantees to quantify the cost of privacy in DP-FC-BAI (and $\\epsilon$ global DP). Specifically, the authors show that the complexity depends on an information theoretic total variation metric. Although, this holds in the high privacy regime, this is reasonable and possibly connected with results on strong data processing inequalities in prior works. Through their lower bound ,the authors show consistency and recover the non-private regime as well. Additionally, the authors propose a variant of existing algorithms with asymptotically matching upper bound.", "questions": "Which parts of the proofs technique are novel? Could you please include proof sketches that emphasize on the proof technique?\n\nDoes the total variation uniquely characterize the hardness of the problem? Can the lower bounds be expressed in terms of the KL divergence instead?", "limitations": "The authors adequately addressed the limitations.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The originality of the paper is clear. The presentation is clear and the contributions are significant. The total variation characteristic time is a novel quantity that it is introduced in this work. The proposed algorithm (AdaP-TT) is also novel and achieves matching guarantees with the proposed lower bound. The authors manage to characterize a phase transition effect: in the low privacy regime the privacy can be achieved for free. This is correct and has been observed in prior works as well (but for Thomson sampling). The results of the work are the first lower bounds for DP BAI, and they successfully characterize the hardness of the problem.", "weaknesses": "The proof techniques appear to be mostly applications of known proof techniques. Sketches of proofs for the lower and upper bounds can potentially improve further the quality of the paper. The sketches should provide details on the novelty of the proof technique and several steps of the proof (similarly to proof of Lemma 1 in the Appendix).   \n\n\nA few references are missing, for instance \"On the Renyi differential privacy of the shuffle model\" by Girgis et al., \"Secure best arm identification in multi-armed bandits\"  by Ciucanu at al.\n\nFinally, the format of some references in the bibliography can be improved, some references point to older version of prior works on arxiv, while the papers have been published, for instance see [KNSS20].\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the time spent reviewing, careful reading, and kind words about the contributions' novelty and significance. It is really encouraging for us.\n\n**Missing references.** We thank the reviewer for pointing us to these references. We will add them to the Related Works section in the revised version, and update the reference to [KNSS20].\n\n**Technical novelty; \"proof sketches that emphasize on the proof technique\".** Please refer to the general comment for the technical novelty. We also thank the reviewer for the advice, indeed we will add more intuition in the proof sketches and emphasize more the technical contributions pointed out in the general comment.\n\n**Does the total variation uniquely characterize the hardness of the problem? Can the lower bounds be expressed in terms of the KL divergence instead?** We thank the reviewer for this excellent question.\n\nOur 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 [GK16]. The total variation distance appears to be the natural measure to quantify the hardness of privacy in many other settings (regret minimization [1], Karwa-Vadhan lemma [2], Differentially Private Assouad, Fano, and Le Cam [3]). The high-level intuition is that: Pure DP can be seen as a multiplicative stability constraint of $e^\\epsilon$ when one data point changes. Group privacy tells that if two datasets differ in $d_{ham}$ points, then one incurs a factor $e^ {d_{ham}~\\epsilon}$. Now, if I have $n$ iid points from a distribution $P$ and $n$ iid points from a distribution $Q$, the Karwa-Vadhan lemma states that we incur a factor $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 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})$. \nHowever, it is possible that the problem can be characterized by other f-divergences/measures.  \n\nFinally, 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. Please refer to the answer to the reviewer rwuX for the inequality between $T^\\star_{TV}$ and $T^\\star_{KL}$, i.e. $T^\\star_{TV}(\\nu) \\geq \\sqrt{2 T^\\star_{KL}(\\nu)}$.\n\nHope that our response addresses the reviewer's questions. Let us know if you have any other queries.\n\n[1] Azize, A., & Basu, D. (2022). When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35, 32199-32210.\n\n[2] Karwa, V., & Vadhan, S. (2017). Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03908.\n\n[3] Acharya, J., Sun, Z., & Zhang, H. (2021, March). Differentially private assouad, fano, and le cam. In Algorithmic Learning Theory (pp. 48-78). PMLR."}, {"review_id": "YgXYf1CW8V", "reviewer": "Reviewer_RUVA", "summary": "This paper studies the problem of Best Arm Identification (BAI) for bandit problems under the constraints of differential privacy. There are some $K$ distributions and the solver interacts with the arms over a sequence of rounds. In each round they choose a distribution and receive a reward according to that distribution. The goal is to identify the arm with the highest expected reward with certainty $1-\\delta$ where $\\delta$ is a Fixed Confidence (FC) parameter given to the solver. \n\nMotivated by real-world problems like clinical trials for testing doses/efficacy of drugs, the authors suggest studying this problem under the constraint of differential privacy - this is relevant when the rewards received might be private information, such as the medical data of a patient's response to the drug/dose they were administered.\n\nThe contributions of this paper are as follows:\n1. The authors derive a lower bound on the sample complexity for DP-FC-BAI problem - their results suggest that the problem can be characterized in the low-privacy and high privacy regimes. In the former it seems that the sample complexity of the problem is unaffected by the DP constraint.\n2. They present an algorithm, AdaP-TT, which is a differentially private version of the Top Two Upper Confidence Bound (TTUCB) algorithm from prior work. The sample complexity of this algorithm matches the lower bound asymptotically in the high-privacy regime.\n3. The conduct some experiments showing that their algorithm has lower sample complexity compared to another differentially private approach (DP Successive-Elimination).", "questions": "1. You define a low and high privacy regime based on $\\varepsilon$, $T_{KL}^*$ and $T_{TV}^*$, but the expressions for these depend upon $\\mu_i$ which the solver does not have access to. Operationally, is there any way for the solver to know whether they are in the low privacy or high privacy regime?\n2. The claim that there is no additional cost of privacy in terms of sample complexity for the low-privacy regime seems to need some more justification - there is a matching upper bound in the high-privacy regime but since there is no matching upper bound for the low-privacy regime, couldn't there just be a stronger lower bound which holds that we are not yet aware of?", "limitations": "Potential negative societal impacts do not need to be discussed here as this is primarily a theoretical paper.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. The problem being studied is very well-motivated - in particular the example of dose finding and the necessity of privacy preserving BAI is compelling.\n2. The authors provide a lower bound and characterize the hardness of the problem.\n3. The algorithm they provide (privatizing the optimal sample complexity achieving method in the non-private setting) seems to work well in practice based on their experiments. At a cursory look the performance of the algorithms seem to corroborate the constant factors in the sample complexity terms that the authors derived.", "weaknesses": "1. I found this paper very hard to read - the questions being considered by the authors make sense but the expressions derived are not easy to make sense of. The presentation is hard to follow - some terms are introduced without much context (such as ``Top Two algorithms\" on the second page) and this paper seems hard for non-experts to follow.\n2. On page 2 the authors say \"A calibrated amount of noise, from a Laplace [DR14] or Gaussian distribution [DRS22], is injected into an algorithm to ensure DP. The noise scale is set to be proportional to the algorithm’s sensitivity and inversely proportional to the privacy budget $\\varepsilon$.\" I think this statement is somewhat misleading - DP can be achieved in many ways and obfuscating noise is routinely drawn from many distributions (including the Gumbel distribuion, Poisson distributions, or other ad-hoc methods depending on the setting). Indeed, as the authors themselves find in their lower bound, sometimes privacy can be achieved for free. Similarly, the way the scale of the noise is chosen can be very involved - it is not always possible to derive a uniform bound on the sensitivity of an algorithm or such a method could give a very sub-optimal result. It is also important to note that not all problems admit DP solutions - there is no meaningful DP way to compute the XOR of $n$ private bits, for instance.\n3. The expressions in the lower bound are hard to interpret - ideally one might want to characterize them only in terms of the problem parameters i.e. the number of arms $K$, the confidence parameter $\\delta$ and the privacy parameter $\\varepsilon$ - the given bound seems to be more general which is great (as it describes the hardness in terms of the expected rewards), but is it possible to instead substitute a hard instance for the $\\mu_i$ and $\\Delta_a$ values and derive a more readable corollary?\n4. The approach does not seem to be very novel as it reduces to essentially just applying the Laplace mechanism at one point of the TTUCB algorithm from prior work. The sensitivity admits a straightforward bound as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your time, thorough feedback, and precise remarks.\n\nWe first answer the points raised in the \"weaknesses\" section.\n\n**1. The paper is hard to read for non-experts.** The paper studies private BAI and builds upon recent advances in both domains. As such, for non-experts in both domains, it is harder to grasp the key novel insights. With the additional page available for the final version, we will improve the presentation by providing more context for non-experts in both domains, i.e. differential privacy and best arm identification, and providing more intuition behind the different results. \n\n**2. DP can be achieved in many ways.** We thank the reviewer for this precise remark. As correctly pointed out, DP can be achieved in many different ways. The goal of the sentence was to introduce the Laplace and Gaussian mechanisms. A more nuanced and correct way is to say \"A popular way to achieve DP is to inject a calibrated amount of noise, from a Laplace [DR14] or Gaussian distribution [DRS22], 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$.\" We will modify the sentence in the revised version.\n\n**3. The expression of the lower bound is hard to interpret.** The sample complexity lower bound derived in this paper is problem dependent, i.e. depends on the hardness of the environment the policy is interacting with, which is characterized by the expected rewards $(\\mu_i)_{i = 1}^K$. *The FC-BAI literature is mainly interested in problem-dependent bounds*. As pointed out by the reviewer, this is a more general result and more interesting when trying to characterise the hardness of a problem. It is always possible to derive a worst-case lower bound from the problem-dependent one, by optimizing for the worst environment (i.e. the environment with the highest characteristic time in the environment class). This may be even less interpretable than the problem-dependent lower bound. The lower bound of Theorem 2 is expressed to draw a direct parallel with the one known for FC-BAI (see e.g. [GK16]). We provide a simpler version in Corollary 1 and a full characterisation in Proposition 1.\n\n**4. The novelty of the approach.** Please refer to the general comment for the novelty and technical contributions. Applying the Laplace mechanism to the Top Two algorithm to have a sample complexity that matches the lower bound is not as straightforward as it seems. For example, using the tree-based mechanism [DNPR10], which is also based on the Laplace mechanism, to estimate the means privately does not achieve the lower bound. Also, the doubling and forgetting parts are important in order to have less sensitivity and add just the required amount of noise to achieve the lower bound.\n\nWe now answer your other questions.\n\n**1. $T^\\star_{KL}$ and $T^\\star_{TV}$ depend on $(\\mu_i)$? Is there a way for the policy to know in which privacy regime it resides?**\n- First, we would like to mention that $T^\\star_{KL}$ is not our contribution. It is a classic and well-studied quantity in the BAI literature and constitutes a crucial part of the design of every optimal algorithm in this field (see e.g. [GK16]). If $T^\\star_{KL}$ completely characterises the complexity of the non-private problem, $T^\\star_{TV}$ dictates the sample complexity at the high privacy regime and can be seen as a private counterpart of $T^\\star_{KL}$.\n\n- Both $T^\\star_{KL}$ and $T^\\star_{TV}$ depend on $(\\mu_i)$, as they are *problem-dependent lower bounds*. Indeed, $(\\mu_i)$ is unknown to the policy. This means that, for the policy to know in which privacy regime it resides, tracking $T^\\star_{KL}$ and $T^\\star_{TV}$ using the empirical means estimate $(\\hat\\mu_i)$ is a natural way. If $\\epsilon$ is less than the estimated $T^\\star_{TV}$ divided by the estimated $T^\\star_{KL}$, it is the high privacy regime, otherwise, it is the low privacy regime. AdaP-TT is not doing that. It only tracks the non-private lower bound (i.e. $T^\\star_{KL}$) as a non-private algorithm would do, and the additional cost tracking that privately is shown to be $T^\\star_{TV}/\\epsilon$, which comes from the added Laplace noise. Another approach would be to first perform a test to determine in which regime the policy resides, and then track (privately) the corresponding characteristic time. Such a two-phase algorithm requires properly choosing the amount of time spent in its first phase. Without proper tuning, it has no chance to reach asymptotic optimality. Whether it is possible to analyze such an algorithm and quantify the proper tuning is an interesting direction for future work.\n\n**2. No additional cost of privacy in terms of sample complexity for the low-privacy regime.** The sample complexity of AdaP-TT is shown to achieve $T^\\star_{KL}$ of Gaussian distributions in the low-privacy regime. Since the rewards in the analysis are supposed Bernoulli, the mismatch from **exact** optimality is coming from the mismatch between the KL divergence of Bernoulli distributions and that of Gaussian, which is generally controllable in most instances where the means are far from the borders, i.e. $0$, and $1$. This is in essence, similar to the mismatch between UCB and KL-UCB in the regret-minimization literature (Chapter 10 in [LS18]). To overcome this mismatch, it is necessary to adapt the transportation costs to the family of distributions considered. In our setting, this can be done by using the Bernoulli KL rather than Gaussian KL in lines 12 and 16 of the algorithm. While the Top Two algorithms for Bernoulli distributions have been studied in [JDB+22], the analysis is more involved. Therefore, it would obfuscate where and how privacy is impacting the expected sample complexity.\n\nHope that our response addresses the reviewer's questions. Let us know if you have any other queries. If our response convinces you, it would be helpful to raise the score."}, {"review_id": "5YyHMITWEA", "reviewer": "Reviewer_jHc4", "summary": "This work provides some insight into using the Laplace mechanism on the algorithms concerning the best arm identification problem bandits with a constraint of fixed confidence. The analysis carried out in this work enumerates general properties of differentially private FC-BAI and then proposes an algorithm based on those bounds.", "questions": "-", "limitations": "No additional limitations can be seen in this work. All the limitations, to the reviewer's knowledge, have been addressed properly in the paper.", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Analysis carried out in this work is general to all algorithms that are designed to solve the BAI problem where there are some guarantees presented on the sample complexity of such class of algorithms.", "weaknesses": "No weaknesses found in this paper, as per the knowledge of the reviewer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent reviewing and the positive view of this work. We hope that the rebuttals done for the other reviewers will answer your future questions. Also, let us know if you have any other concerns."}, {"review_id": "mgufBBd5JK", "reviewer": "Reviewer_rwuX", "summary": "The paper considers the best arm identification (BAI) problem under differential privacy (DP) constraints, where the goal is to privately identify the arm with the highest expected reward with probability at least $1 - \\delta$. The paper proposes a DP variant of the top two algorithm, which achieves near-optimal performance in the high privacy regime. The paper also proves an information-theoretic instance-dependent lower bound for the DP-BAI problem. The paper also conducts experiments on synthetic data to demonstrate the efficiency of the proposed algorithm.", "questions": "See comments above.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed upper and lower bounds match each other in the high-privacy regime when the true means are away from 0 or 1. This provides an up-to-constant characterization of the asymptotic sample complexity for DP-BAI.\n\nThe proposed algorithm empirically outperforms a natural DP variant of the successive elimination algorithm. \n\nThe paper is also nicely written and easy to read.\n", "weaknesses": "While DP-BAI is an interesting problem to study, the techniques used in the paper are primarily natural variants of previous work. In particular, nonprivate-BAI and the closely related DP regret minimization in the bandit setting have been studied. Hence the technical novelty of the paper is restricted. \n\nIt would be nice if the authors could comment on the non-asymptotic optimality of the proposed algorithm.\n\nMinor comments:\n1. Not sure if colored texts are supported for NeurIPS submissions.\n2. Definition 1: The letter d is a bit overloaded. Maybe it is better to use $D$ or $\\mathcal{D}$ to refer to datasets, which is used later in the paper.\n3. Line 207: Might be good to have parentheses after sup.\n4. Can you comment on how $T^*_{TV}(\\nu)$ and  $T^*_{KL}(\\nu)$ relate to each other? \n5. Algorithm 2: $L_n$'s are not initialized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading and astute observations to improve the manuscript.\n\n**Technical novelty.** Please refer to the general comment.\n\n**Non-asymptotic sample complexity of AdapTT.** Please refer to the general comment.\n\n**Minor Typos.** Thanks for detecting the typos. We will modify them in the final version of the paper. Specifically, we will change $d$ to $D$ in Definition 1, add parentheses after the sup in Line 207, and initialize $L_n$ to zero at the start of Algorithm 1. While colours are allowed in the figures, official guidelines do not specify anything for text. Since it is recommended to have a paper which is legible when printed in black/white, we will avoid the use of colour in the revised version.\n\n**Relation between $T^\\star_{TV}$ and $T^\\star_{KL}$.** One can use Pinsker's inequality to connect the TV characteristic time and the KL characteristic time: $T^\\star_{TV}(\\nu) \\geq \\sqrt{2 T^\\star_{KL}(\\nu) }.$ \n\nWe will add this comment in the final version of the paper.\n\nHere, we present the exact calculations for completeness. 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)}$.\nTherefore, for every allocation over arms $\\omega$, we have\n$\n\\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)}.\n$\nTaking 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} }$.\nThis concludes the proof.\n\nHope our response answers your concerns. Looking forward to addressing any further comments."}]

Author rebuttal:
We would like to thank the reviewers for acknowledging the strengths and soundness of the contribution as well as for their thoughtful comments and efforts towards improving the manuscript. In the following, we address the general concerns of reviewers that were common. 

As pointed out in the reviews, our main goal is to propose a thorough examination of Best Arm Identification under Fixed Confidence with Differential Privacy, i.e. DP-FC-BAI. 

(a) We provide a lower bound on the sample complexity of any $\delta$-correct BAI algorithm satisfying $\epsilon$-global DP. This lower-bound quantifies the additional cost of privacy through a novel information theoretical quantity, i.e. the Total Variation Characteristic Time ($T^\star_{TV}$). As also pointed out in the reviews, *this is the first lower bound in the literature on DP-FC-BAI*. 

(b) We also propose an $\epsilon$-global DP variant of the Top Two algorithm, called AdaP-TT. We provide its asymptotic sample complexity and show that AdaP-TT enjoys both theoretical near-optimality and good experimental performance.

Now, we would like to address two recurring comments.

**Novelty of the results and technical contributions.** We resolve three layers of technical challenges through our contributions.

**1. Lower bound.** 
(a) To derive the lower bound, we first provide an $\epsilon$-global DP version of the transportation lemma (Lemma 1). To prove this lemma, we construct a sequential coupling between the probability distribution of the triplet $(\tau, \underline{A}, \hat{A})$ when the BAI strategy interacts with two different environments. Here, $\tau$ is the stopping time, $\underline{A}$ is the sequence of action recommended and $\hat{A}$ is the recommended final action. Extra care is needed *to deal with the (random) stopping times in the coupling, compared to a fixed horizon $T$ in regret minimization*. This is a result that could be of general use beyond our work. We combine this lemma with a data-processing inequality to prove the final lower bound. 
(b) We also provide a full characterisation of the lower bound by studying the TV characteristic time (Proposition 1), which requires solving exactly the optimization problem defining $T^\star_{TV}$. This provides a closed form expression of $T^\star_{TV}$ with respect to the mean rewards of arms $(\mu_a)_{a = 1}^K$.

**2. Algorithm design.** We propose a *generic wrapper which adapts the existing FC-BAI algorithm to tackle DP-FC-BAI*. It builds on two components. 
(a) Adaptive episodes with per-arm doubling and forgetting, which yields the $\epsilon$-global DP property of the algorithm (Theorem 3). 
(b) 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 prove the $\delta$-correctness of this choice (Theorem 4), we need to combine concentration results for Bernoulli distributions and Laplace distributions, and account for per-arm phase indices which are random variables. As a result, *the dependency in $(n,\delta)$ of the obtained stopping threshold is fundamentally different than the ones obtained in FC-BAI* (see lines 309--314). This has a profound impact on the asymptotic upper bound on the expected sample complexity.

To use this proposed wrapper, one can choose among the numerous existing sampling rules to tackle FC-BAI. In this work, we considered the Top Two algorithms since they have good theoretical guarantees and empirical performance.

**3. Upper bound.** 
(a) We highlight exactly the cost of each algorithmic design choice (doubling, forgetting, the private cost in the GLR stopping) and how they affect the final asymptotic sample complexity. Those remarks will hold for most asymptotically ($\beta$-)optimal algorithms when combined with our wrapper. 

(b) Building on [JDB+22], we provide a generic analysis of the class of Top Two algorithms when combined with our wrapper.

Compared to [JDB+22], the **key challenge** lies in controlling the per-arm phases. As a consequence, the proof of sufficient exploration had to be adapted. More importantly, in order to obtain convergence towards the optimal allocation, *we had to prove that the phase switches of the arms happen in a round-robin fashion after a large enough time*. This means that an arm switches phase for a second time after all other arms first switch their own phases.
    
**Non-asymptotic sample complexity of AdaP-TT.** 
In the *non-private FC-BAI literature* (i.e. $\epsilon = + \infty$), *there is no tight lower bound in the non-asymptotic regime (i.e. for any value of $\delta$)*. This is the main open problem in FC-BAI. Therefore, it is also an open problem in DP-FC-BAI. In the class of asymptotically ($\beta$-)optimal algorithms, few have non-asymptotic guarantees.
[JD22] proposed TTUCB and showed the first non-asymptotic upper bound on the expected sample complexity of a Top Two algorithm.
Adapting the non-asymptotic analysis of [JD22] to the private AdaP-TT is an interesting direction for research.
Based on our understanding of their proof, we conjecture that such an adaptation is possible (up to technicalities).
Intuitively, in Theorem 2.4 in [JD22], the $\delta$-dependent term will be modified by adding a concentration term linked to Laplace distribution to the $\log(n)$ term stemming from sub-Gaussian concentrations. 
Similar to our asymptotic analysis, this will have consequences on the dependency in the upper bound.
For the $\delta$-independent terms in Theorem 2.4 in [JD22], they will also be impacted since Lemma 3.2 in [JD22] should be modified to account for Laplace noise.
In the low-privacy regime, we expect also to lose at least a multiplicative four-factor compared to TTUCB due to doubling and forgetting.

Hope this commentary addresses the concerns regarding technical novelty and challenges. Below, we address the comments specific to each reviewer by responding to them directly.

Meta-review: Although some reviewers found that the paper is dense and hard to parse, others (experts in the area) mentioned that the paper contains sufficient contributions to be published. In particular, the authors derive a hardness result giving a lower bound for the problem of BAI with fixed confidence under $\varepsilon$-global Differential Privacy. For the high-privacy regime, the lower bound depends on the Total Variation Characteristic Time, which shares a similar spirit with the regret minimization with $\varepsilon$-global DP [AB22]. For low-private regimes, the lower bound reduces to the classical no-private lower bound. This is a neat observation. The algorithmic contributions based on top-two algorithms are also novel. 

For the final version of the paper, it would be ideal if the authors can make the presentation more reader-friendly, especially to non-experts.
Decision: Accept (poster)