Fixed-Budget Differentially Private Best Arm Identification
Authors: Zhirui Chen
P. N. Karthik
Yeow Meng Chee
Vincent Tan
Venue: ICLR 2024 poster (2024)
Keywords: Best Arm Identification
Differential Privacy
Primary area: reinforcement learning

Abstract: We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints, when the arm rewards are supported on the unit interval. 
Given a finite budget $T$ and a privacy parameter  $\varepsilon>0$, the goal is to minimise the error probability in finding the arm with the largest mean after $T$ sampling rounds, subject to the constraint that the policy of the decision maker satisfies a certain {\em $\varepsilon$-differential privacy} ($\varepsilon$-DP) constraint. We construct a policy satisfying the $\varepsilon$-DP constraint (called {\sc DP-BAI}), based on the principle of {\em maximum absolute determinants}, and derive an upper bound on its error probability. Furthermore, we derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$, with exponents in the two bounds matching order-wise in (a) the sub-optimality gaps of the arms, (b) $\varepsilon$, and (c) the problem complexity that is expressible as the sum of two terms, one characterising the complexity of standard fixed-budget BAI (without privacy constraints), and the other accounting for the $\varepsilon$-DP constraint. Additionally, we present some auxiliary results that contribute to the derivation of the lower bound on the error probability. These results, we posit, may be of independent interest and could prove instrumental in proving lower bounds on error probabilities in several other bandit problems.
Whereas prior works provide results for BAI in the fixed-budget regime without privacy constraints or in the fixed-confidence regime with privacy constraints, our work fills the gap in the literature by providing the results for BAI in the fixed-budget regime under the $\varepsilon$-DP constraint.

Published as a conference paper at ICLR 2024
FIXED-BUDGET DIFFERENTIALLY PRIVATE BEST ARM IDENTIFICATION
Zhirui Chen', P. Karthik Yeow Meng Chee', and Vincent Y. Tan National University of Singapore Indian Institute of Technology, Hyderabad
zhiruicher.eu www.euuuuuueeeee.eee nus.edu pnkarthikeai. with. ac. in {ymchee, vtan @nus edu, sg
ABSTRACT
We study best arm identification (BAI) in linear bandits in the fixed- exed-budget regime under differential privacy constraints, when the arm rewards are supported on the unit interval. Given finite budget T and a privacy parameter to minimise the error probability in finding the arm with the largest mean after T sampling rounds, subject to the constraint that the policy of the decision maker satisfies a certain s-differential privacy (s-DP) constraint. We construct a policy satisfying the e-DP constraint (called DP-BAI) by proposing the principle of maximum absolute determinants, and derive an upper bound on its error probability. Furthermore, we derive minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in T,, with exponents in the two bounds matching order-wise in (a) the sub-optimality gaps of the arms, (b) E, and (c) the problem complexity that is expressible as the sum of two terms, one characterising the complexity of standard fixed-budget BAI (without privacy constraints), and the other accounting for the s-DP constraint. Additionally, we present some auxiliary results that contribute to the derivation of the lower bound on the error probability. These results, posit, may be of independent interest and could prove instrumental in proving lower bounds on error probabilities in several other bandit problems. Whereas prior works provide results for BAI in the fixed- fixed-budget regime without privacy constraints or in the regime with privacy constraints, our work fills the gap in the literature by providing the results for BAI in the fixed-budget regime under the e-DP constraint.
0, the goal is
INTRODUCTION
Multi-armed bandit problems (Thompson) 1933) form a class sequential decision-makinn problems with applications in fields diverse clinical trials, internet advertising, and recommendation systems. The common thread in all these applications is the need to balance exploration (learning about the environment) and exploitation (making the best decision given current knowledge). The isplorationeexploiaatiio trade-off has been studied extensively in the context of regret minimisation, where the goal is to minimise the cumulative difference between the rewards of the actions taken and the best possible action in hindsight; see Lattimore and Szepesvári (2020) and the references therein for an exhaustive list of works on regret minimisation. On the other hand, the pure exploration framework, which is the focus of this paper, involves identifying the best arm (action) based on a certain criterion such as the highest mean reward. The pure exploration paradigm has been a subject of rigorous study in the literature, predominantly falling within two overarching regimes: the fixed-con cond--oniieeccee regime and the fixed -uddeet regime. In the fixed-contidence regime, the objective is to curtail the anticipated number of trials needed to pinpoint the optimal arm, all while adhering to predefined maximum allowable error probability. Conversely, in the fixed-budget budget regime, the aim is suppress the likelihood of erroneous identification of the best arm under a predetermined budget.
The task of identifying the best arm in a multi-armed bandit setting is non-trivial due to the inherent uncertainty associated with each arm's true reward distribution. This problem is amplified when privacy constraints are considered, such as the need to protect individual-level data in a medical trial user data in an online advertising setting (Chan et al.) (011). In the context of such data-intensive applications, the notion of differential privacy (Dwork) (0066) has become the gold-standars for the modelling and analytical study of privacy. While there has been growing
Motivation:
"This work was carried out when P. N. Karthik was a Research Fellow the National University of Singapore.

---

Published as a conference paper at ICLR 2024
bandits interest in the design of perrrerriipeeeiigggg... algorithms for regret minimisation in
(Basu et al.] 22019; Jain et al., 2012) Chan et al. |011]] Guha Thakurta and Smith 2013 Mishra and Thakurta 2013 Tossou and Dimitrakakis (016), comparable level of attention has not been directed towards the domain of pure exploration. Addressing this lacuna in the literature, our research aims investigate differentially private best arm identification within the fixed-budget regime.
Problem Setup: Briefly, our problem setup is as follows. We consider a multi-armed bandit in which each arm yields independent rewards supported on the unit interval [0, 1J. Each arm is associated with a known, d-dimensional feature vector, where d is potentially much smaller than the number of arms. The mean reward of each arm a linear function of the associated feature vector, and is given by the dot product of the feature vector with an unknown d- d-dimensional vector O" which fully specifies the underlying problem instance. Given a designated budget T and a parameter E > O, the objective is to minimise the probability of error in identifying the arm with the largest mean reward (best arm), while concurrently fulfilling a certain E-differential privacy (e-DP) constraint delineated in Basu et al. (2019). We explain the specifies of our model and define the e-DP constraint formally in Section 2 beloo.
Overview of Prior Works: Differential privacy (DP) (Dwork 2006) and best-arm identification (BAI) (Lattimore and Szepesvári (020) have both been extensively investigated in the literature, encompassing wide array of works. In this section, we discuss selection of more recent con- tributions at the intersection of these two topics. Sharrff and Sheffer (2018) prove that any c-DP (viz. (e, -)P with 5 0) algorithm must incur additional regret of least 5 ((K log T)))), where KJ is the number of arms. Building on this result, [Sajed and Sheffel (2019) propose an elimination-based algorithm that satisfies the e-DP constraint and achieves order-wise optimality in the additional regret term. Zheng et al. (020)) study regret minimisation with the (e. - differential privacy constraint, stronger requirement than (e. 8)- for contextual and generalised linear bandits. Azzie and Basu (2022) study the E-global differential privacy constraint for regret minimisation, and provide both minimax and depeenddn regret bounds for general stochastic bandits and linear bandits. Chowdhury and Zhou (2023) and (Slanki et al. (2023) explore differential privacy in a distributed (federated) setting. Chowdhury and Zhou (2023) explore regret minimization with the (s, dDDP constraint in a distributed setting, considering
untrustworthy server. They derive an upper bound on the regret which matches order-wise with the one obtainable under a centralized setting with trustworthy server; for similar work that studies regret minimisation in the distributed and centralised settings, see Hanna et al.] (2022). (Sllani et al. (2023) study federated learning for combinatorial bandits, considering a slightly different notion of privacy than the one introduced in Dwork (2006). We observe that the existing literature on bandits mainly focused on regret minimisation with DP constraint and the pure exploration counterpart has not been studied extensively.
In the pure exploration domain, Carpentier and Locatelli Ii (2016) study the fixed-budget BAI problem and obtains a minimax lower bound on the error probability: the authors show that their bound is order-wise tight in the exponent of the error probability. |Yang and Tan (2022) investigate fixed-budget BAI for linear bandits and propose an algorithm based on the G-optimal design. They prove minimax lower bound on the error probability and obtain an upper bound on the error probability of their algorithm OD- OD-LINBAL. Despite the significant contributions of Carpentier and Locatelli (016)). Yang and Tan (022)), Komiyama ct al. (2022), and Kato et al. (2023), these works do not take into account DP constraints. Nikolakakis et al. (20IT) Rio et al. (023) study BAI in the fixed-confidence setting with e eDD constraint and propose successive eliminttion-type algorithms, but these works do not derive a lower bound that is a function of the privacy parameter c. Our work is thus the first to study differentially private best arm identification in fixed-budget regime and provide a lower bound explicitly related the privacy parameter 8.
We present a novel algorithm for fixed-budget BAI under the e-DP constraint. Our proposed algorithm, called DP-BAI, is based on the principle of maximizing absolute determi- nants (or MAX-DET in short). A key aspect of our algorithm is the privatisation of the empirical mean of each arm via the addition of Laplacian noise. The amount of noise added an arm is inversely proportional to the product of the privacy parameter & and the number of times the arm is pulled. Recognising the trade-off between the number of arm pulls and the level of noise injected for privatisation, the MAX-DET principle minimises the maximum Laplacian noise injected across all arms, thereby ensuring a small probability of error in identifying the best arm. We believe our work can open for future exploration in precise control over Laplacian noise (crucial to meet the
Our Contributions:
2

---

Published as a conference paper at ICLR 2024
e-DP guarantee) and using other popular techniques in fixed-budget BAI, such as G-optimal designs Kiefer and Wolfowitz, [1660] Yang and Tan 2022) and XYy-adaptive allocations (Soare et al. 2014), with DP-constraint. We find it analytically convenient to leverage the properties of the MLA--DET collection (cf. Definition 3.1) to satisfy the s-DP constraint. See Remark for a brief justification on why extending other popular techniques for fixed- BAI such G-optimal design (Yang and Tan 2022) to the differential privacy setting of our work is not readily feasible.
Additionally, we establish the first-known lower bound on the error probability under the e-DP constraint for a class of "hard" problem instances. We demonstrate that both the upper and lower bounds decay exponentially relative to the budget T. The exponents in these bounds capture the problem complexity through certain hardness parameter. which we show can be expressed as the sum of two terms: one measuring the complexity of the standard fxxedbbuget BAT without privacy constraints, and the other accounting for the c-DP constraint. We also present some auxiliary findings. such as the properties of the so-called early stopping version of a BAI policy (see Lemmas 4.3 and 4.5) that contribute to the derivation of the lower bound, which may be of independent interest and could prove instrumental in deriving lower bounds on error probabilities in several other bandit problems. Our work stands out the first in the field to provide precise and tight bounds the error probability for fixed- budget BAI under the E-DP constraint, achieving order-wise optimal exponents in both the lower and the upper bounds.
NOTATIONS AND PRELIMINARIES
Consider multi-armed bandit with K > 2 arms, in which each yields independent and identically distributed (i.i.d)) rewards, and the rewards are statistically independent across arms. Let
[K] : {1, (1,..., K} denote the set of arms. For i E [K] let v4 denote the rewards distribution of arm i. As in several prior works (Chowdhury and Zhou 2022, Shariff and Sheffet 2018 Zhou and Chowdhury 2023], we assume throughout the paper that v4 supported in [0, 1] for all i E [K]. We impose a linear structure on the mean rewards of the arms. That is, for each i E [K], we assume that arm is associated with a feature vector a, E Rdd where d is the dimension of the feature vector, and the mean reward of arm i is given by n4: a. 0" for some fixed and unknown 0" E Rd. We assume that the feature vectors of the arms (a. K == are known beforehand to decision maker, whose goal it identify the best arm = [ Me we assume that the best arm is unique and defined unambiguously.
The Fixed-Budgel Regime: The decision maker is allowed to pull the arms sequentially, one at each time t E {1, ... Let A, E [K] denote the arm pulled by the decision maker at time t, and let Ni. - 2==1 1 (A,=i) denote the number of times arm i is pulled up to time t. Upon pulling arm A,, the decision maker obtains the instantaneous reward XA..NA, E [0. 1]; here, Xi,. ~ denotes the reward obtained on the nihh pull of arm Notice that E[X = fu; a, 0" for all E [K] and n 2 1. For all t, the decision to pull arm A, is based on the history of arm pulls and rewards seen up to time i.e., A, is a (random) function of H, == (A1, X XA, Given a fixed budger T < co, the objective of the decision maker enror in finding the best arm after T rounds of arm pulls, while also satisfying a certain differential privacy constraint outlined below. We let İT denote the best arm output by the decision maker.
A
1.
minimise the probability of
The e-Differential Privacy Constraint: Let == {x = ( C [0, 1| denote the collection of all possible rewards outcomes from the arms. Any sequential arm selection policy of the decision maker may be viewed as taking inputs from X' and producing (AI...., Ar [r) E [K]T+I as outputs in the following manner: for an input x = (xx,)) E X.
Output time 1 A Ar.
Output at time t = 2 A₂ As NAINA)))
Output at time t 3 A3 As(AI, AQ, AA,
Output at time t = T A = Ar (A,, ZA,
Ar-1. T-1),
Terminal output
Îr = iT Lt AA, AN, T),
(1)
3

---

Published as a conference paper at ICLR 2024
We say that (2: and x' (xf.)) are neighbouring if they differ in exactly one location, i..., there exists (i. [K] x [T] such that Tı,t # z and I₁ =z/,- for all (j.s) * (i, With the viewpoint in ① we now introduce the notion of e-differential privacy for a sequential policy of the decision maker, following the lines of Nikolakakis et al. (202T] Section 5).
Definition 2.1. Given any E > O, a randomised policy M : X - [K]T+] satisfies e-disferential privacy if, for any pair of neighbouring x,x' E X.
(MM() E S ef (MM(M(()) E AA c [K]T+]
Remark 1. A generalization of the notion of e-differential privacy is that of (c, -)dffferrnnt privacy (Dwork et al., 2014, Chapter 2). For the sake of simplicity in exposition, in the main text, provide details for the former. An extension of our algorithm, called DP- OP-BAI-GAUUS be shown to be applicable to the latter (generalized) notion of differential privacy. The details and accompanying analyses of the performance of DP-BAI-GAUSS can be found in Appendix D
will
While the actual sequence of rewards observed under M is random, it is important to note that a pair of reward sequences, say (x, x'), is fixed when specifying the c-DP constraint. In (2). PM denotes the probability measure induced by the randomness arising from only the arm outputs under M. In the sequel, we refer to the tuple e = ((a)): jie|))]))))) (V)) 0" E) as a problem instance, and let P denote to be the set of all problem instances that admit unique best arm. Given P and a policy т, we write P to denote the probability measure induced under π and under the instance v. When the dependence on v is clear from the context, we simply write Ip
3 OUR METHODOLOGY
To meet the e-DP guarantee, our approach is to add Laplacian noise to the empirical mean reward of each arm, with the magnitude of the noise inversely proportional the product of ε and the number of times the arm is pulled. Intuitively, to minimize the maximum Laplacian noise that is added (so as to minimize the failure probability of identifying the best arm), we aim to balance the number of pulls for each arm in the current active set. To this end, we employ the MAX-DET explained below.
The MAX-DET Collection: Fix d' E N. For any set S C Rdd' with |S| = d' vectors, each of length d', let DET(S) to denote the absolute value of the determinant of the d' x d' matrix formed by stacking the vectors in S as the columns of the matrix.
Definition 3.1. Fix d' N. Given any finite set A C Rd with |A| 2 d', we say B C A with [B] = d' is a MAX-DES collection of A if
DET(B) 2 DET(B") for all B' C with |B d'.
(3)
Thus, a MAX-DEB collection B C A has the maximum absolute determinant among all subsets of A with the same cardinality as B. If (pan(A) = d', the vectors in B are linearly independent, and any E AA may be expressed as a linear combination of the vectors in B. Call the coefficients appearing in this linear combination expression for b as its coordinates (Meyer) 2000) Chapter 4). The set of coordinates of each b E A is unique, and b may be expressed alternatively as a d'-length vector of its coordinates. In this new system of coordinates, the vectors in B constitute the standard basis vectors.
3.1 THE DIFFERENTIALLY PRIVATE BEST ARM IDENTIFICATION (DP-BAI) POLICY
We now construct a policy based on the idea of successive elimination (SE) of arms, Our policy for Differentially Private Best Arm Identification, called DAI, operates over a total of M phases, where M is designed to have order Ollog d). In each phase E [M], the policy maintains an active set Ap of arms which are potential contenders for emerging as the best arm. The policy ensures that with high probability, the true best arm lies within the active set in each phase.
Policy-Specific Notations: We now introduce some policy-specifie notations. Let
= inf 2 2 glog(d) > K - [dP /274
(4)
Let (9 and (20 be defined as follows:
9o min K, [a? /4]},
9: 1/
1,
(5)
ho max (K- - [d]] /41,0),
h; [11-11 11/A|
Vi
(6)
4

---

Published as a conference paper at ICLR 2024
Let Su 9u + hu, and for each p [M], let Sp beginning of phase p, defined via
Apl denote the number of active arms at the
90 + hp-1 IspsMr
Sp
(7)
M1 M1 M
For > O, let Lap (#) denote the Laplacian distribution with density fa(2) = 2- @ R.
Initialisation: We initialise our policy with the following parameters:
M1 =min(i~ E N: h4 = =0,
M = M1 + min EN:::: 1} 1,
T' T Mid - (M -1MdMM) /d]4/4 do d, To= 0,
a = a, ViE
A1 [K].
(8)
Policy Description: We now describe the DP- OP-BAI policy. The policy takes as inputs the differential privacy parameter e, budget T, the number of arms K, and the feature vectors of the arms (a. : E
[K]). With the initialisation in (8), the policy operates in phases. In each phase p [M], the first
step is dimensionality reduction YYngg and Tan 2022), whereby the dimension of the set of vectors {a (a(--)) i E Ap} } is reduced using a linear transformation here, a ((?-1) R 1 for all i E Ap. More specifically, suppose that dp == ddim(span {a (p-1) : E Ap)). The policy chooses an arbitrary orthogonal basis Up = (u (p)
(p) for span a E Ap}, and obtains a new set of vectors (1-11))
= [a " I,,, for all i A
where [vl,, denotes the coordinates of v with respect to Up. Subsequently, the policy checks if d < / Spp where s, = Apl defined in 7 If this true, then the policy constructs a MAX-DEB collection Bp Ap consisting of BBp = dp arms, and pulls each arm i B3 for [ T" Mdd many times, and sets Tp = T p- + de 2 1. On the other hand, if de 2 /Sp. then the policy pulls each arm in Ap for T" Msp many times, and sets Tp = Tp-1 + 8p Msp
T
1. After pulling the arms according to the
preceding rule, the policy computes
N.T. X
(10)
N.T, NoTT,-1
e=Ni,Tp-1t1
for each arm i E Ap that was pulled at least once in phase p, and subsequently computes its private empirical mean 21; via
T(r)
(11)
where ( Lap (N.,T; - -
is independent of the arm pulls and arm rewards. For i E Ap that not pulled in phase p. the policy computes its corresponding private empirical mean via
O4 14
(12)
JEG
where (as,))EE,, is the unique set of coefficients such that a. (p) phase p. the policy retains only the top 8pt1 arms with the largest private empirical means and eliminates the remaining arms; intuitively, these arms are most likely to produce the highest rewards in the subsequent phases. At the end of the Mth phase, the policy returns the only arm left in AM+1 as the best arm. For pseudo-code of the DP-BAI policy, see Algorithm
(p) -EEE, Ois a At the end of
Remark 2. It is natural to wonder why we do not devise differentially private version of OD- LinBAI (Yang and Tan 2022), the state-of-the-ane art linear fixed-budget BAI algorithm, which uses G-optimal designs. A proposal to do so, called DP-OD, is provided in Appendix E However, the error probability in identifying the best arm under DP-OD depends not only on the suboptimality gaps of the arms, but is also a function of the arm vectors. For example, in a 2-armed bandit instance, let a [x. 0) a2 [0. y) with x, y 0, and 0r [ 2/, 0.5/ y\ Then, μl 0.5 + A. I22 = 0.5, and the suboptimality gap A = μ11 P2. For this instance, the upper bound on the error
probability of DP-OD exp (-2 A 24 axu (-))-)) We observe that aVy can be made arbitrarily aAy
T large. Thus, this bound is inferior to the upper bound of DP-BAI (equal to exp( - ( -0
and independent of the arm vectors). See Appendix E for further details.
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 Fixed-Budget Differentially Private Best Arm Identification (DP-BAI)
Input:
8: differential privacy parameter; budget; {a. E [K]]: d-dimensional feature vectors.
Output: IT: best arm.
1: Initialise To 0, A = [K]. a;
(0) for all i E [K]. Set M and T as in (8)
2: for E 21, 2,. M do
3: Set dp dim(span// (a i Ap)).
4: Obtain the new vector set (a.
(p) : E Ap) from the set (a. 1a( : Ap} via (9)
5: Compute Sp using (7)
6: if d, < 85p then Construct MAX-DET collection B, C Ap. Pull each arm in B, for [ Md, many times. Update Tр +- Tp-1 + dpl T
7:
8:
Md,
9:
Obtain the empirical means (f4(p) :ie Bp} via 10))
10:
Generate {(P) Lap
for E Bp.
F cl
Map
Set 14 - a! + ((p) for all Bp.
11:
For arm i Ap Bp. compute f0; via 12
13:
else
Pull each arm in A, for
many times. Update T, < Tp- + spl T
Mep
Map
15:
Obtain the empirical means (p(
: Apt via (10)
16:
Generate ((P) Lap
for E Ap.
Map
Set p + a + z(p) for all Ay.
17:
18: end if
19: Compute Sp+1 using
20: Ap-1 <- the set of 8p41 arms with largest private empirical means among (74 :1 E A,).
21:
end for
22: IT < the only arm remaining in AM+1
return Best arm IT-
THEORETICAL RESULTS
We now present theoretical results for the DP- BAI policy. followed by a minimax lower bound on the етоо probability. We write IID--BI to denote the DP-BAI policy symbolically. The first result below, proved Appendix F asserts that DP Bai meets the e-DP constraint for any 0.
Proposition 4.1. The DP-BAI policy with privacy and budget parameters (e, T) satisfies the s-DP constraint, i.e,, for any pair of neighbouring x, x' E X. pmaa-na (UDP-BAI(x) E < e [pTlo--MM ([DD)BAT(X')) E AS c [K]T+
(13)
In 133,, the probabilities appearing either sides of (13) with respect to the randomness in the arms output by UDР-BAI for fixed neighbouring reward sequences x, x' E X' (see Section 2). The of Laplacian noise for the privatisation of the empirical means of the arms (see Lines 10-11 and plays a crucial role in showing [13
16-17 in Algorithm]] !
4.1 THE HARDNESS PARAMETER
Recall that problem instance v may be expressed as the tuple ((ar)se[k) (x))) 0" e).
In this section, we capture the hardness of such an instance in terms of the instance -pstafce-specific arm sub-optimality gaps and the privacy parameter e. Recall that the arm means under the above instance are given by 14, = a. 0" for all i E [K]. Let A; = As=(m)) #4 denote the -utimmatyl gap of arm i [K]. Further, let (l,,... Ix) be a permutation of [K] such that A,, - A .... < Alg.
and let Ag) Ad, for all E [K]. The hardness of instance is defined as
H(v)= (V) (p)(
(14)

---

Published as a conference paper at ICLR 2024
where
HBAI(U) = max (SIS((AK)
A and (pri(o) =
max (SIS(PAA))
(15)
A (6)
Going forward, we omit the dependence of H, HBAL. and H pri on for notational brevity. It is worthwhile to mention here the quantity in (14) specialises to the hardness term "H2" " in Audibert al. (2010). which is identical to HBAL. when K S de and holds, for instance, for a standard K'armed bandit with K = d. 0* E IR as the vector of arm means, and (a,) ) the standard basis vectors in Rd Intuitively, while HBAI quantifies the difficulty of fixed-budget BAI without privacy constraints, ppi accounts for the c-DP constraint and captures the additional difficulty of BAI under this constraint.
+oo. The former condition K s de
4.2 UPPER BOUND ON THE ERROR PROBABILITY OF DP-BAI
In this section, we provide an upper bound on the error probability of DP-BAI.
Theorem 4.2. Fix P. Let (v) denote the unique best arm of instance v. For all sufficiently large T, the error probability of TTP BAI with budget T and privacy parameter satisfies
T
Palleam (ir + (1)) exp
(16)
65 M
where M and T are defined in 8 In 16 PplloP denotes the probability measure induced by DP BAI under the instance v.
This is proved in Appendix Since M = O(log d) and T' = (TT) (as T + co), 16) implies that
aol (fr +()) cxp ( T
H log (H)
(17)
4.3 LOWER BOUND THE ERROR PROBABILITY
In this section, we derive the first-of-its -ind lower bound on the error probability of fixed-budget BAI under the s-DP constraint. Towards this, we first describe an auxiliary version of generic policy that takes input three arguments-a generic policy म. π E N. and E [K]-and pulls auxiliary arm (arm 0) whenever arm i is pulled n or more times under æ. We believe that such auxiliary policies are potentially instrumental in deriving lower bounds error probabilities in other bandit problems.
The Early Stopping Policy: Suppose that the set of arms [K] is augmented with an auxiliary arm (arm 0) which yields reward 0 each time it is pulled; recall that the arm rewards are supported in [0, 1]. Given a generic policy æ, n E and E [K] let ES(T n, t) denote the early stopping version of π with the following sampling and recommendation rules.
Sampling rule: given a realization Hi-1 (a1, (a1, ,.,, Ut-1, D(=1 [(0 < n, then (BS(A.))) (Ae A H₂-1) 1ptt (A+ E A H4-1) [K]
(18)
and if E.= 1 (a,=.) 2 n, then (E)( (A, = 0 H4-1) 1. That is, as long as arm pulled for total fewer than times, the sampling rule of ES(TT, n, c) is identical that of Else, ES(T, n,,) pulls arm e with certainty.
Recommendation rule: Given history Ht (a1, 31 21, .... aT, IT), if Exe 1a,=00) then
P ES((..))) (Ir E A Hr) T. (ir E A Hr) YAS [K)
(19)
and if Σ
1a,=00 O, then m.)( (îg 0 Ht) 1. That is, if the auxiliary arm 0 is pulled under π, the recommendation of E.S( n. 1) is consistent with that of n. Else, ES(m,, recommends arm O as the best arm.
The next result below provides "bridge" between policy and its early stopped version. Lemma 4.3. Fix problem instance E P. policy n, n E N, and E [K]. For any A C [K] and E = fIr E A} O (N.r < n),
p (FE) (.....) (F)-
(20)
7

---

Published as a conference paper at ICLR 2024
In addition, let ((n.))) = (( (E LE(T (LE
X T X... R" where
n, = T for all i * and n, = n. Notice that Definition 2.1 readily extends to any randomised policy that maps (m...)) to {O..... K] T+1 We then have the following corollary to Lemma 4.3
Corollary 4.4, If π X + [K] meets the e-DP constraint, then ES(T, n..) : X( + {O..... K]'+1 also meets the E-DP constraint.
Given the early stopping version of policy и, the following lemma provides "bridge" between two problem instances v, d' E P.
Lemma 4.5. Fix policy n, n E N, L E [K], and > O, and suppose that M = ES(TT, n, 1) satisfies the E- E-DP constraint with respect to X(n.)) For any pair of instances v = ((a)) ()), (VS)eE[K) 0²,=) and v' = -(ax)iE[K)) (V)) 0"" .e). with 0- + 0", V, + v/, and V; = v/, for all i + we have
P.M (M((X..))e(()))ett)))) E ES) S S (M((
E ES) AS S {0. KJT41
(21)
Gen (w,, v.), with (V v.)) being the total variation distance between the distributions v, and v', and (ii) n, T for all i + and n. n.
where in (2T). (i)
The proof of Lemma 4.5 follows exactly along the lines of the proof Karwa and Vadhan (2018
Lemma 6. and is omitted. Leveraging Lemma in conjunction with Lemma prrovidde us with change-of-mmassue technique, facilitating the transition from P Pe under any given policy This change-oft -feaasure technique serves as the foundation that enables us to derive the subsequent minimax lower bound on the error probability.
provides
Definition 4.6. A policy for fixed-budger BAI is said to be consistent if
lim P. (Ir # (b)) = =0, VeEP.
(22)
T T-++0
Theorem 4.7 (Lower Bound), Fix any 31, B2, B3 [0.1] with 81 + 32 + B3 3, consistent policy π, and constant >> O. For all sufficiently large T, there exists an instance v E P such that
[-cllog (Ir # (")) exp (- (- ( a
T
(23)
(HBAI()))))) Hpa(o)8s)
Consequently,
Ind (ir # (x)) exp (-
c(log (Hnrr(v))) + Hpri )
inf lim inf sup consistent T-+000 VEP
21,
(24)
for any > 0 and B1, B2, B3 E [0, 1] with 81 B/ 33 < 3.
Theorem 4.7, proved in Appendix H implies that for any chosen B E [0, 1) (arbitrarily close to 1), there does not exist a consistent policy æ with an upper bound on its error probability assuming any of the following forms for all instances
P: exp
(log d) (Hax(()++
exp exp (-22 [log (F) #pp((()) or exp (-9( (Ing (i ())) In this sense, the dependencies of the upper bound in 16) on log d, HBAI()) (v), and H (p)(v)) are "tight". Also, in this precise sense, none of these terms can be improved upon general.
Remark 3. It is pertinent to highlight that the upper bound in (16) applies to any problem instance, whereas the lower bound in (23) is minimax result that is applicable one or more hard instances. An ongoing quest in fixed-budget BAI is to construct policy with provably matching error probability upper and lower bounds for all problem instances.
NUMERICAL STUDY
This section presents a numerical evaluation our proposed DP-BAI policy on synthetic data, and
compares it with BASELINE, algorithm which follows DP-BAI but for Lines 6 to 13 in Algorithm [ ie., BASELINE does not construct MAX- collections. We note that BASELINE is e e-DP for any
> 0, and bears similarities with SEQUENTIAL. HALVING (Karnin al. 2013) when + (i.e.,
8

---

Published as a conference paper at ICLR 2024
0.1
T 300
1.0
0.8
0.8
Success Rate
0.6
0.6
0.4
OD-LINBAL
0.4
OD-LIB
DP-BAI 0.1)
BA
0.2
DP-OD (.1)
0.2
DP-OD
BASELINE (5 0.1)
BASELINE
50
100
150
200
250
300
350
400
450 500
0.1
0.7 0.9 i1 13 15 17
T
in DP-BAI, BASELINE and DP-OD
Figure I:
Comparison of DP-BAI to BASELINE, OD-LINBAI and DP-OD for different values e. Note that is not applicable OD-LINBAL.
non-private algorithm). However, because it does not exploit the linear structure the means, we will see that it performs poorly vis-à-vis DP-BAI. In addition, we compare DP-B IP-BAI AI with the state-of-the-ar OD-LINBAI Yang and Tan 2022) algorithm for fixed-budget best arm identification, which is non-private algorithm and serves an upper bound in performance (in terms of the error probability) of our algorithm. Also, we consider an D-DP version of OD-LINBAI which we call DP-OD. A more comprehensive description of the DP-OD algorithm is presented in Appendix E.
Our synthetic instance is constructed follows. We set K 30, d 2, and l" [0.045 0.5] a _]"_ a2 [0 0.9] a3 [10 O)T, and wi randomly generated from a uniform distribution on the interval [0, 0.8]. Clearly, μ1 = 0.5, 22 μ3 0.45, and μ4 = w:/2 + 0.045 for all E {4, ......... 30), thereby implying that arm 1 the best arm. The sub-optimality gaps are given by AΑ = As 0.05 and A > 0.05 for all i E (4...., 30); thus, arms 2 and 3 exhibit the smallest gaps. In addition,
[1 w;] for all E {4...., 30), where
set v4, the reward distribution of arm i, to be the uniform distribution supported on [0, 2/4e] for all E [K].
We experiments with several choices for the budget T and the privacy parameter e, conducting 1000 independent trials for each pair (T, E) and reporting the fraction of trials which the best arm is successfully identified.
The experimental results are shown in Figure for varying T and e values respectively. As the results demonstrate, the DP-BAI policy significantly outperforms BASELINE and DP-OD, demonstrating that the utility of the MAX-DET collection in exploiting the linear structure of the arm means. We also observe that as > +o0 (i.e.. privacy requirement vanishes), the performances DP-BAI and the non- non-private statc-of-the the- OD-LINBAI algorithm are similar.
CONCLUSIONS AND FUTURE WORK
This work has taken a first step towards understanding the effect of imposing a differential privacy constraint on the task of exdgeb BAI bandits with linearly structured mean rewards. Our contributions include the development and comprehensive analysis of a policy, namely DP-BAI, which exhibits exponential decay in error probability with respect to the budget and demonstrates a dependency on the dimensionality of the arm vectors d and a composite hardness parameter, which encapsulates contributions from both the standard fixed- fixed-budget BAI task and the imposed differential privacy stipulation. A distinguishing aspect in the design of this policy is the critical utilization of the MAX-DET collection, instead of existing tools like G-optimal designs (Yang and Tan (022) and addattti allocations (Soare al. 2014). Notably, we establish minimax lower bound that underlines the inevitability of certain terms in the exponent of the error probability of DP-BAI.
Some interesting directions for future research include extending work to incorporate generalized linear bandits (Azizi et al. 2022) and neural contextual bandits (Zhou et al. 2020). Additionally, we aim tackle the unresolved question brought forth post Theorem 4.7] does there exist efficient fixed-budget BAI policy respecting the e-DP requirement, whose error probability upper bound approximately matches a problem-dependee lower bound?

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This research/project is supported by the National Research Foundation Singapore under the Al Singapore Programme (AISG Award No: ASS22TCC-023-012-22 by the Singapore Ministry of Education Academic Research Fund (AcRF) Tier 2 under grant number 4-8000423-00--0, and the Singapore Ministry of Education AcRF Tier under grant number --8000189-01-00)
This work is also supported
REFERENCES
Audibert, J.-Y., Bubeck, S., and Munos, R. (2010). Best arm identification in multi-armed bandits. In COLT, pages 41-53.
Azize, A. and Basu, D. (2022). When privacy meets partial information: refined analysis of differentially private bandits. Oh, H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances in Neural Information Processing Systems.
Azize, A. and Basu, D. (2023). Interactive and concentrated differential privacy for bandits. In Sixteenth European Workshop Reinforcement Learning.
Azizi, M., Kveton, B., and Ghavamzadeh, M. (2022). Fixed-budget best-arm identification in structured bandits. In Proceedings of the Thirty-First International Joint Conference Artificial Intelligence, IJCAI-22, pages 2798-2804.
Basu, D., Dimitrakakis, C., and Tossou, A. (2019). Privacy in multi-armed bandits: Fundamental definitions and lower bounds. arXiv preprint arXiv:1905. 12298.
Carpentier, A. and Locatelli, A. (2016). Tight (lower) bounds for the fixed budget best arm identifica- tion bandit problem. Conference on Learning Theory, pages 590-604. PMLR.
Chan, T.-H. H., Shi, E., and Song, D. (2011). Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24.
Chowdhury, S. R. and Zhou, X. (2022). Shuffle private linear contextual bandits. In International Conference Machine Learning, pages 3984 4009. PMLR.
Chowdhury, S. R. and Zhou, X. (2023). Distributed differential privacy in multi-armed bandits. In The Eleventh International Conference on Learning Representations.
Dwork, C. (2006). Differential privacy. In Automata, Languages and Programming: 33rd Interna- tional Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings. Part II 33, pages 1-12. Springer.
Dwork, C.,, Roth, A., et al. (2014). The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 9(3-4):211-407.
Guha Thakurta, A. and Smith, A. (2013). (nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances Neurul Information Processing Systems, 26:2733-2741.
Hanna, O. Girgis. M.. Fragouli, C., and Diggavi, (2022). Differentially private stochastic linear bandits: (almost) for free. arXiv preprint arXiv:2207.03445
Jain, P., Kothari, P., and Thakurta, A. (2012). Differentially private online learning. In Conference on Learning Theory, pages 24-1. JMLR Workshop and Conference Proceedings.
Karnin, Z., Koren, T., and Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246. PMLR.
Karwa, V. and Vadhan, S. (2018). Finite sample differentially private confidence intervals. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstubl-Leibniz Zentrum fuer Informatik.
10

---

Published as a conference paper at ICLR 2024
Kato, M., Imaizumi, M., Ishihara, T., and Kitagawa, T. (2023). Asymptotically minimax optimal fixed-budget best arm identification for expected simple regret minimization. arXiv preprint arXiv:2302.02988.
Kiefer, J. and Wolfowitz, (1960). The equivalence of extremum problems. Canadian Journal of Mathematics, 12:363-366.
Komiyama, J., Tsuchiya, T., and Honda, J. (2022). Minimax optimal algorithms for fixed- fixed-budget best arm identification. Advances in Neural Information Processing Systems, 35:10393-
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Meyer, C. D. (2000). Matrix analysis and applied linear algebra, volume 71. SIAM.
Mishra, N. and Thakurta, A. (2015). (nearly) optimal differentially private stochastic multi-arm bandits. Proceedings of the Thirty-Fi First Conference on Uncertainty in Artificial Intelligence. pages 592-692-999 992-601.
Nikolakakis, K. E., Kalogerias, S., Sheffet, O., and Sarwate, A. D. (2021). Quantile multi-armed bandits: Optimal best-arm identification and a differentially private scheme. IEEE Journal on Selected Areas in Information Theory, 2(2):534-544
Rio, A., Barlier, M., Colin, I., and Soare, M. (2023). Multi-agent best arm identification with private communications. International Conference on Machine Learning.
Sajed, T. and Sheffet, O. (2019). An optimal private stochastic-man algorithm based on optimal private stopping rule. International Conference on Machine Learning, pages 5579-5588. PMLR.
Shariff, R. and Sheffet, O. (2018). Differentially private contextual linear bandits. Advances in Neural Information Processing Systems, volume 31, page 4301-4311.
Sheffet, O. (2015). Private approximations of the 2nd-momen matrix using existing techniques in linear regression. arXiv preprini (rXXiv:557.000555
Soare, M., Lazaric, A., and Munos, R. (2014). Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27:828 836.
Solanki, S., Kanaparthy, S., Damle, S., and Gujar, (2023). Differentially private federated combi- natorial bandits with constraints. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2022, Grenoble, France, September 19-23, 2022, Proceed- ings, Part IV, pages 620-632- 637. Springer.
Thompson, W. R. (1933). On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294.
Tossou, A. and Dimitrakakis, C. (2016). Algorithms for differennially private multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, page 2087-2093.
Weisberg, S. (2005). Applied linear regression, volume 528. John Wiley & Sons.
Yang, J. and Tan, V. (2022). Minimax optimal fixed-budget best arm identification linear bandits. Advances in Neural Information Processing Systems, 35: 1661122222266.6
Zheng. K., Cai, T., Huang, W., Li, Z., and Wang, L. (2020). Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems,
Zhou, D., Li, I.., and Gu, Q. (2020). Neural contextual bandits with UCB-based exploration. In Proceedings of the International Conference on Machine Learning, ICMI,220, pages 11492-11502
Zhou, X. and Chowdhury, S. R. (2023). On differentially private federated linear contextual bandits. arXiv preprint arXiv:2302.13945
11

---

Published as a conference paper at ICLR 2024
Supplementary Material for "Fixed-Budget Differentially Private Best Arm Identification"
A USEFUL FACTS
In this section, we collate some useful facts that will be used in the subsequent proofs.
Lemma A.1 (Hoeffding's inequality). Let .i....; Xn be independent random variables such that a, S X; S b, almost surely for all i for some fixed constants a, S by, E [n]. Let
Sn = + Kn.
Then, for all O.
2ca
P (S - B[s)] 2 e) S exp
(25)
(bs 0z)
2c
P ([S,, E [Sa]] 2 c) S 2exp
(26)
Σ -==1 (b. a,)
Definition A.2 (Sub-exponential random variable). Let T E and b > 0. random variable X said be sub-exponential with parameters (T2,b) if
AR72 AA:
E [exp(AX)) S exp
(27)
Lemma A.3 (Linear combination of sub-exponential random variables). Let XI...., Xn be in- dependent, zero-mean sub-exponentiaa random variables, where X; is -ubb--xponentiill Then, for any 01...., On E IR, the random variable E 0;X; is (72 -j-suub-epponntial where 7² 7== >>>n aē and b = max; by (as).
Lemma A.4 (Tail bounds sub-exponential random variables). Suppose that X is sub-exponential with parameters (f².b) Then,
2²
72
exp
0
0S
272
P(X- B[ 2
(28)
72
E
exp
2h
b
B AN EXAMPLE OF THE POLICY-SPECIFE NOTATIONS IN SEC. 3.1
Consider d 16, K 10, 000. Then, have Pu 64, ho = 9936, Mj 4, M 10 and 2 27.65. In the following table, we display the values of sp for p = 1,..., Mi.
p
8p
(sp-1
9o //)/(5g 9o)
1000
N.A.
2
423
Rs 27.65
77
As 27.68
(= Mi)
64
Rs 27.62
For p M1 + 1....... M, we simply have sp = 10-pp i.e., 85 32, 86
16,...,117 1.
Notice that the values in the third column of the above table (apart from the first row which is not applicable) are nearly equal to the value of A. Based on the above table, we may bifurcate the operations of our algorithm into two distinct stages. Roughly speaking, in the first stage (i.e., phases 1 to Mi), the algorithm aims to reduce the number of arms to a predetermined quantity (i.e., 9n) quickly possible. Following this, in the second stage (i.e., phase M1 + 1 to M), the algorithm iteratively halves the number of arms. This process designed to gradually concentrate arm pulls those arms with small sub-optimality gaps (including the best arm) much possible, thereby improving the accuracy of estimating the mean of the best arm and encouraging effective identification of the best arm.
12

---

Published as a conference paper at ICLR 2024
C EQUIVALENCE OF OUR NOTION OF DP WITH THE NOTION OF TABLE-DP OF AZIZE AND BASU 2023)
In this section, we discuss the notion of table-DP introduced in the recent work by Azize and Basu 2023 Section 2), and we will show that our definition of differential privacy in Definition 2.1 is equivalent to the notion of table-DP. Firstly, maintain notational consistency with AAzie and Basu (2023), we introduce a dual decision maker who obtains the reward X XA., rather than the reward A...NA,. upon pulling arm A, time step t; see Section 2 for other relevant notations. Then, for any policy т, we write (T)) denote its dual policy obtained by substituting its decision maker with the dual decision maker. Clearly, in the non-private setting, any policy is equivalent to its dual policy. We demonstrate below that the same conclusion holds under DP considerations too. To begin, we formally define DP for the dual policy.
Definition C.I Collumn-neighbouu differ in exactly one column, i.e., there exists l. E (T) such that x., # x, and x., x for all f L, where , = (x,,a) ) and x = 1=
We say that x, x' E X are column-neighhouring if they
Definition C.2 (Table-DP), Given any E > O and a randomised policy M X - [K]++1 we say that the dual policy ((M) satisfies e-table-DP if, for any pair of (lllum-neighbouring x' X,
PDlM) (D(M) (x) S) s e PPMM) (D(M)(x) ES)
For any = (+ E [K]T+], we denote [z]] == (2)) E [K]-tt]] Then, we have the following alternative characterization of table-DP.
Corollary C.3. Given any >> 0 and a randomised policy M X - [K]T+], the dual policy D(M) satisfies E-table-DP if and only if for any E [T] and any pair of oolumn-neighhouringg x, x' X with x. # x
PP(M) (ID(M) (x)T+ E S) S PD(M) (DIMM)N) E ES) VS c [K]
In the following, we demonstrate that the notions of DP in Definition equivalent after some slight modifications in notations.
C.2 and Definition 2.1 are
Proposition C.4. Fix any policy If πt satisfies E-DP, then D(x) satisfies --tall--D..
Proof. Fix any z = (z) E [K]T+1, and any pair of columo-neighbouring xD, x!D E X. For i E [K] and / E [T], we let
T
74,1 = Σ
(==i))
(29)
(=1
Notice that n,, is equal to Nr. A, = 2, for all T S L. Then, we construct x, x' E by defining for all tellee E [T]
X == =x_ and
x X X
(30)
and for all (i,g) E [K] X [T] \ ( mz..) | [T]}
xij and =
Hence, the fact that x" 'D X' are column-neighbourin implies that either x and x' neighbouring or x = x'. That is, by the assumption that π satisfies e-DP, we have
pd ('(((x)) 2) < P (x(x') = z).
(31)
In addition, by 29 and 30 we obtain that
pd (x) = 2) = - (D(T)(()) = 2) and
P (T(x') 2) = -PD())(D(T)(())
2).
(32)
Finally, combining 31 and 32 we have
P(r) (D(m)(xP)= = 2) pPP(T)) <)P((()))) =))
which completes the desired proof.
13

---

Published as a conference paper at ICLR 2024
Proposition C.5. Fix any policy If (T)) satisfies e-table-DP, then satisfies E-DP.
Proof. Fix any (z)) [K] and any pair of neighbouring x, x' X. Again, for i [K] and E [T] we let
T
ni, Σ
(=
(33)
t=1
Then, construct x ,,,' x X' by defining for all E [T]
x = Xar and
X x X
(34)
and for all (i,5) E [K]
[ [( t) te [T]]
x = and 2-==0
Hence, the fact that x' X' are neighbouring, implies that either xa and x'D are column- neighbouring or x" x That is, by the assumption that ((T) satisfies E-table-DP, we have
p(r) (D(T) = 2) s pPD(T) (D(x)xx))=
(35)
In addition, by
33 and 34
we obtain
(D(T)(x²) 1 (T(x') =z) =DD(=)(D(T)((>
P" (xx) = z) = =pD(T) =PD(=)D((T(('" = 2) and
z).
(36)
Finally, combining (35 and 36 we have
Pa (x(x)= 2) S EP (T(x) 2),
which completes the proof.
Combining Propositions C.4
and
C.5
obtain the following corollary.
Corollary C.6. A policy ग satisfies e-DP if and only if D(T)) satisfies s-table-DP.
This proves the equivalence betweeen our notion of DP in Definition 2.1 and the notion of table-DP appearing in the work of Azize and Basu (203)).
D EXTENSION OF OUR RESULTS TO (E, DIFFEREEEL PRIVACY
Below, first define the (e, diifferrenii privacy constraint formally.
Definition D.1 ((E, dddiifferet privacy). Given any > 0 and 5 > 0, a randomised policy
M [K]++) +1 satisfies (s, d)ddifferential privacy if, for any pair of neighbouring x, x'x' E e.
I.M (M(x) E S) < ef (PM((((x) E S) + [SC[K]T+
The above definition particularises to that of e-differential privacy when 5 = 0. Therefore, it is clear that any policy that satisfies the s-DP constraint automatically satisfies (c, DDP constraint for all > In particular, our proposed DP-BAI policy satisfies the (e, dD- constraint for all
However, DP-BAI has been specifically designed for (e, 0)-D, and does not adjust the agent's s strategy for varying values of Therefore, exclusively for the (e, 8) -iffferentia privacy constraint with 8 0, provide variant of proposed algorithm called DP-BAI-GAUS: that utilises the Gaussian mechanism (Dwork et al. 2014) and operates with additive Gaussian noise (in contrast to Laplacian noise under BA.).. The pseudo-code of OP-BAI-GAUSS is shown in Algorithm 2 where the differences from DP-BAI are highlighted red.
Proposition D.2. The OP-BAI-GAUSS policy with privacy and budget parameters (c, 5, T) satisfies the (e, DD constraint, i.e for any pair of neighbouring x, E X and VS [K]
Bal (TDP. GAUSS (x) E S)
D.l--BAA--Goss (TTp BAI-GAUSS E)) ES)+ (37)
14

---

Published as a conference paper at ICLR 2024
Algorithm 2 DP-BAI-GAUSS,
Input:
e, 6: differential privacy parameters; T: budget; {a: E [K]]: d-dimensional feature vectors.
Output: Iy: best arm.
1: Initialise To 0, Ai [K] a
(0) for all i E [K]. Set M and T as in (8)
2: for p E 2,,
M) do
3: Set dp dim(spant (9-1) i Ap)).
4: Obtain the new vector set (a. (p)
: Ap} from the set {a!-1 :i E Ap} via 9
5: Compute Sp using (7).
6: if dp < Sp then Construct MAX-DET collection B, C Ap.
7:
8:
T Pull each arm in B, for Md, many times. Update TN +- Tp-1 + dpl Md,
T
9:
Obtain the empirical means (f4(p) :ie Bp} via 10)
10:
Generate (P) Gaussian
0, 2l1((1,5)/0)
T7 [el Map M 1)²
for By.
((P) < 14,") + Ee for all i E Bp. Set 14
11:
For arm i Ap B,, compute ( via 12
13:
else
Pull each arm in Ap for
many times. Update Tp - Tp-1 + spl Map
Mep
Obtain the empirical means (n(2) i E Ap} via 100
15:
16:
Generate ZTP)
Gaussian
0, 20g((125)/0) [el T 1)a
for i E Ap.
(p)) 17: Set fi + A + <i²) for all i Ay.
18: end if
19: Compute 8p+1 using 77)
20: Ap-1 <- the set of 8p41 arms with largest private empirical means among (74 :1 E Ap).
21:
end for
22: IT 4 the only arm remaining in AM+1
return Best arm İr.
The proof of Proposition D.2 is deferred until Section Below, present upper bound on the error probability of DP-BAI-GAUSS, Proposition D.3. For any problem instance P.
T
T
plluu--At-cous (ir * (()) S exp -St
HBAL log d
Vlog( 122b Hpri log d
where HBAI and Hpu are as defined in (15).
The proof of Proposition D.3 follows along the lines of the proof of Theorem 4.2 by using sub- Gaussian concentration bounds place of sub-exponential concentration bounds. The proof deferred until Section J
Remark 4. It is pertinent to highlight that the contribution of algorithms do not lie in the introduction of a novel privacy mechanism such as Laplace and Gaussian mechanisms. Instead, propose new sampling strategy based the MAX-DET principle for fixed budget BAI. This strategy can be seamlessly integrated into any differential privacy mechanism, including the Laplace and the Gaussian mechanisms.
Table shows comparison of the upper bounds for DP-BAI- and DP-BAI (from Theo- rem Because DP-BAI is (e, d)dffferreet private for 5 > as alluded to earlier, the preceding comparison is valid.
We observe that DP-B BAI-GAUSS outperforms DP-BAI for large values and T. In the small regime, however, DP-BAI performs better than DP-BAI-GAUSS. In particular, when 8 0. the
15

---

Chapter 2) is to Published as a conference paper at ICLR 2024
Condition 7 and
DI-BSA--GAUSS
DP-BAA
logt To pri log
HhAt log
T
exp
-
Hoal logd
exp
-2
H log
T
T Hf logs
S
/logt d6 pri log
T
PBat log
T
exp
-
Vlog( ds pap logd
T
v
exp
-
Fr Iog
T
logt T3 pri log
T H log
exp
1Ω
Vlog( fi Hops logd
T
exp
(-22
H log
T
8 = 0, T
0
exp(-52(1)) (vacuous)
Ω?
T 17 loga
Table Comparison between the upper bounds of DP-BAI and DP-BAI-GAUSS, The ticks indicate the tighter of the two bounds under the given condition.
additive noise in the Gaussian mechanism is infinite and thus vacuous. That is, DP-BAI-GAUSE is not applicable when 5 = O. The above trends are not surprising. given that DP-BAI designed for 5 0 and is hence expected work well for small values of ó. Finally, in order keep the analysis simple and bring out the main ideas clearly, we hence only discuss e-DP criterion our main text, and the discussion regarding of (e,6) presented in this section of the appendix.
E A DIFFERENTIALLY PRIVATE VERSION OF OD-LINBAI 2022) AND ITS ANALYSIS
YANG AND TAN,
E. DETAILS OF IMPLEMENTING DP-OD
To achieve e-DP for DP-OD, variant of OD-LINBAI (Yang and Tan 2022). one of the natural solutions is to use the idea of Shariff and Sheffet 2018), which is to add random noise in the ordinary subroutine,
least square (OLS) estimator; note that OD LINBAl uses the OLS estimator similar to the algorithm of Shariff and Sheffet 2018). Specifically, given a dataset {(T,, yi) ) one of the steps the computation of the standard OLS estimator (Weisberg. 2005 evaluate the coefficient vector 33 via
GB = U,
where G' is the Gram matrix in the OLS estimator and U = Et_ aays is the moment matrix. While Shariff and Sheffet (2018) add random noise to both and U, we do not add noise to G the feature vectors are determined and known to the decision maker in setting. Instead, add independent Laplacian noise with parameter & to each element U of the OLS estimator, with L = m [K] |, ||;
Laplacian noise instead of Gaussian Wishart noise, noting from Shariff and Sheffet (2018 Section 4.2) (Sefffft (2015) Theorem 4.1) that the latter versions of noise can potentially be infinite and hence not particularly suitable for satisfying the e-DP constraint. Using Sharriff and Sheffet (2018) Claim 7), we may then prove that the above method satisfies the
e-DP constraint.
E.2 A BRIEF ANALYSIS OF DP-OD
The error probability of identifying the best arm under DP-OD depends not only on suboptimality gaps of the arms, but also inherently function of the arm vectors, as demonstrated below.
Proposition E.1. Let K 2, [2c, O , a2 [0, v] with x. > O, and 0" |00.5 - A)/2, 0.5/u) for some fixed > 0. The upper bound on the error probability of DP-OD for the above bandit instance is
T
exp -
TV
(AA)
Proof. Note that there is only one round in DP-OD for the two-armed bandit instance. Let T1 and T2 be the number of arm pulls for arm and arm respectively. By the sampling strategy of DP-OD, have T; (TT) and T2 ((T) (as T oo). From the description in Section E. note that
16

---

Published as a conference paper at ICLR 2024
the moment matrix is given by U matrix with Laplacian noise, i.e.,
Ti a X1, + E/= 22 We denote U to be the moment
Ü= + 1
(38)
where & and & are independent Laplacian noises with parameters & and L = x V respectively.
The estimates of the expected reward of arm 1 and arm 2 are
e1 = ÜG
(39)
and
P1 (G Ü a2).
(40)
where the Gram matrix G = Tj + T2ayaa Then, the event (īz > [22} implies that the decision maker successfully identifies the best arm. In other words,
P(ir + S P( S P2).
(41)
By and
39
40
we have
Ti
T2
E1
E2
T4i
112
X1,i
2
+
T 1=1
T2 i=1
TTi
yT2
Hence,
T
X1,
A
T3
X2,i
A
P( To2 < 0) P
<1
+ PP
Σ
>
112
+
4
4
T2
i=1
A 4
E
A
+
P
+ P
>
(42)
xTΙ
yT2
4
By Lemma
A.1
we have
T
X1,5
A
T1
P
<
11
I
exp
(43)
Ti
4
8A2
and
T2
X2,1
A
T2
P
+
S
exp
(44)
T2
4
8A2
i=1
For sufficiently large T' and T2, by Lemma A.4
we have
E
A
Ti
TP
<
exp
(45)
rTi
4
8(x 8)/x
and
22
TzAe
S exp
(46)
yT²
8(x V u)/u
Recall that Ti = O(T) and T, ( and (46). we have
(as T
oc). and by combining
42
43
45
2VE (cA)-1 )) zny
T
P( < (22) S cxp -Ω
2
can be arbitrarily large, the above bound is inferior to the upper bound of DP- Noting that zVy
zAy
BAI (equal to exp(-92 (-(--T(aa)-- )) for the above bandit instance). Figure 2/sows the empirical performances of DP-BAI and DP-OD by fixing and varying in this problem instance, where 0.05, æ = is fixed, and y > is allowed to vary, and the reward distribution uniform distribution in [o. 2/r]] for arm i 1,2. The success rates are obtained by averaging across 1000 aVy
independent trials. We observe that when the ratio wny increases, the performance of DP-OD becomes worse. However, the performance of DP-BAI is essentially independent of this ratio as the theory suggests. The numerical results presented in Section 5 of our paper as well as this additional numerical study, showing the empirical performances of DP-BAI and DP-OD, reaffirm the inferiority of DP-OD.
17

---

Published as a conference paper at ICLR 2024
7 500, 0.2
T' 500, 0.4
1.0
1.0
0.8
0.8
Success Rate
Sucocss Rate
0.6
0.6
0.4
0.4
DP-BAI DP-OD
DP-BAT
DP-OD
10
13
16
19
22
25
28
7
10
13
16
19
22
25
28
275
(a)
(h)
T = 250,
0.2
T = 250, c 0.4
1.0
Success Rate
Success Rata
0.6
0.4
0.4-
0.2
DP-BAI
0.2
DP-BAI
DP-OD
DP-OD
0.0
0.0
10
13
22
13 16
25
(c)
(d)
Figure 2: Comparison of DP-BAI to DP-OD for different values of aVy in the two-armed bandit
instance introduced in Appendix E.2
PROOF OF PROPOSITION 4.
Let N(() Nr.,, Under the (random) process of DP-BAI, we introduce an auxiliary random mechanism से whose imput is x E X, and whose output is (N/²) " [e[ where define
<()) if i Ap. By Dwork et al. (2014 Proposition 2) to prove Proposition 4.1 suffices to show that e-differentially private, i.e., for neighbouring x, X.
(#(x) S) S (#*(') E S) VS C Ω
(47)
where Ô is the of all possible outputs of न. In the following, we write IP denote the probability measure induced under 7 with input x E X.
Fix neighbouring z, E X arbitrarily. There exists unique pair (i,t) with z # z In addition.
fix any n4 (p) and Borel set
X C [0, for E [K] and p [M] such that
0 < n (1) < n (2) ... S (M) T We(K
Let
<a if n (M)
M 1,
(48)
min(p [M] : (p) 2 n).
otherwise.
For any j E [M], we define the event
D, = (V(pp) E [K] b]: NOD)) = ni)) pp(mm) E x; (0))
and
D' DJ- (N(P) = (p)}
18

---

Published as a conference paper at ICLR 2024
For j' E {1 + ,...,... M}
Djy'= (V(i.)) :e [K] x {j +i+,...... .+......"" N = = .i. Exi {
In particular, Do and D M are events with probability 1, i.e.
P (Do n DM,M) =1 V X.
Then, if n (M) < n2, by the definition of i we can have
F (DM) P (DM).
(49)
(M) and we will show
In the following, we assume ni
P (DM) < exp(s) (Dm)
(50)
which then implies that म is e-differentially private. For x {z, J'J, we denote
1xx
X
(p)
1)
Y1
j=
(p)
That is, fx is the value of Pj the condition of D' under probability measure P
Then, by the chain rule we have for both E 2z,zz}
P (Da) = = (D)) P 11
Exi (p)
D2) Px (Dgasr as D2)
= P (Db) /
Stap(e - -xx (De.M D2 n (2)
ni = =x}) dx (51)
where (-)p(-) is the probability density function of Laplace distribution with parameter Note that by definition it holds
1
<(n -n! (2
p D2) P D'
p Dp.M/ D2 n ( =x]) xx})=pp) = (DaMM D (og D2n = =3)
Vx Ex x²
(52)
ip)
fLap(1 - (12) I exp(e) (x - 1xx) Vx E Ex
Hence, combining 51) and 52 we have
p (Dm) S exp(s)) (Dm)
which implies स is e-differentially private.
G PROOF OF THEOREM 4.2
Lemma G.I. Fix d' E and finite A C Rdd such that span(A) Bdd Let B (bi...., ba be a MAX-DET collection of A. Fix an arbitrary z E A, and let 3I,..., Bar E lK be the unique set of coefficients such that
3,b;-
Then, 18al < 1 for all i [d'].
19

---

Published as a conference paper at ICLR 2024
Proof. Fix A.Let B [b] b2 bal be the d' d' matrix consisting of vectors in B. Let 3=
[81 $2 Be]
to be a vector consisting of the members 31,..., 3x
Then, by the definition of B, for i [d"], we have
=
In addition, let (()) be the matrix that is identical to B except the i-th column is replaced by z, i.e., ( (b] bi-1 2
bi+1
ba] for i [d"]. Note that by the definition of MAX-DE DET
collection, we have
det [() S (det(B)))
(53)
By Cramer's Rule Meyer 2000
Chapter 6), have
del(B())
3 dct(B)
(54)
Finally, combining 133 and
54
we have for all E [d"]
|3. < 1
Lemma G.2. Fix an instance E P and E [M]. Let (v) denote the unique best arm under v. For any set Q C [K] with [Q] Sp and i" (t) E Q, ler de dim(span 2}). We have
pllaaaal
(T((P) 2 (w)
Ap = 2
A
))
=A1
T
< 2 exp
+ 2exp
(55)
16
M M(d A sp)
16
M M A sp)
for all T' sufficiently large and j @ (v)).
Proof. Fix E @ (u)). Notice that the sampling strategy of DA- depends on the relation between |Q] and dg. We consider two cases.
Case 1: de > V
In this case, note that each arm in Q is pulled
T M Q
many times. Let
E = (p)
(p) (r))))
+ A, 2 2,/2}.
(56)
Let X,,o -Xis- u4 for all e [K] and [T]. Notice that X 1-1, 1] for all (i. Then,
pToor (Ei
Ap ②)
No +
Noro))
MEaT Σ
A
T
iplleea BM
Σ
X
Xr(r) 2
Ap Ap =
2
M Q
s= No
(a)
2
2
M
exp
2
M
T
exp
A3
(57)
Q
where (a) follows Lemma A.I
Furthermore. let
Eg (5550) - (/% 2 A2
(58)
20

---

Published as a conference paper at ICLR 2024
clr) We note that both e and (vr(w) are (72,6) sub-exponential, where = then yields that )
Lemma A.3
(p) (v)
is sub-exponential with parameters
2v2 xर|
Subse-
quently, Lemma
A.4 yields that for all sufficiently large T",
pollornas (E2
Ap
2) exp
T'
6
T
E
M
Q
= exp
(59)
8
We therefore have
pllloaaa
(n)))
(p) 2 (1)
Ap = -)
pllln-nn (Ei U E2
Ap Q)
(a)
1
T"
(-5 1 T"
exp
43)
+ exp
E
4
M|
M 2
T"
T'
exp
A3 + exp
EA/)
(60)
M (dg A sp)
8
M ( A sp)
where (a) follows from the union bound.
Case 2: de S V
In this case, each arm in B, c Q is pulled for
T Mdo
times. Recall that we have (p)
Eier, a (p) Using @ this implies a, = EieB, aj a which in turn implies that (ay,
Eies, ays (a,, 0*) Using we then have
E
HoP. BAI (p!))
Ap = =Q) = Mg.
(61)
If j & Bp. we denote
1(00 Σ az
(62)
eB
and
(
Σ
Z(p)
(63)
LEB,
Note that
62 and (63) still hold in the case of j E Bp.
We define the event
G = G1=11f (()
A
μ1 2
Then, we have
al (G1
Ap = Q)
pa sai
T
(A(00) -11)) N
T' A
Ap =
Mdq
Mdq
4
N.. +
Mdl
T"
sMI
Σ
ax, n.)
T' 4
1 -
Mde
== N.
N
(a)
2(
Mda
T"
1//422
exp
do
T"
Mde
21

---

Published as a conference paper at ICLR 2024
T
S exp
8
M
T"
exp
4
(64)
Mi
Sp)
where (a) follows Lemma G.1
and Lemma A.1
In addition, we define the event
((P) 2 A
G2 =
By Lemma A.3 and Lemma G.1 we have ((P) ΣiEB, aj,esc
7(p) max (aj,al
is a sub-exponential random
variable with parameters (EEEs 0g mag
2
Then, by Lemma A.4
ktaq
holds that for 7" sufficiently large
palpoenn (G2 Ap =Q) S exp
4 max.ce O1
TV Xfa
T
EA,
MdQ
S exp
16
T'
EAj
M
Asp.
S exp
(65)
16
Define the events
G3 = p (o) - (o) 1
(p)
Aj
and
2(p) G. =
.
4
(p(())
4
Similar to (64) and 65
we have
1
T"
ppllo--n (Gss Ap = s exp
- A3
(66)
8
M Mi sp)
and for sufficiently large T'
T"
EΑi
M(dgAApp Aep)
Plloe-ns (Ga Ag Q) I exp
(67)
16
Hence, in Case 2, for sufficiently large T we have
(x!")
A, = 2) >
< |pllorann
(GI UG3 U Ap
(-1
T
1
T
< 2exp
1 43 + 2exp
EA,
(68)
(db A sp)
16
M M ^ Ap)
Finally, combining both Cases and 2, for sufficiently large T', we have
2
11 (w)
Ap = 2)
T
< 2exp
17
+ 2exp
8
Mid A 8p)
16
M(d ^ 8pp)
T
T
< 2exp
A3
+ 2exp
E4/)
16
M ^ sp)
16
M M ^ As
22

---

Published as a conference paper at ICLR 2024
Lemma G.3. Fix instance P and p [M1]. Recall the definitions of X in 4 and go in 8 For any set Q C [K] with [2] = Sp and i" (v) E Q, it holds when is sufficiently large
pul (v) $ Apt1 Ap
2)
$ 21
exp
1
T
A Alww) + exp (- 16
T"
A(0o)))
(69)
16
M M(6 A sp)
M ( sp)
[M]] and Q C [ with [Q] 8p and (*() E Q. Let Quub be the set of Sp 90 + 1 arms in with largest suboptimal gap. In addition, let
Proof. Fix v E P.
N
Σ
JEQubb
be the number of arms in Quuh with private empirical mean larger than the best arm. Then, we have
E gllor-Ba (Naub
Ap
Q)
Σ
1 (1777'2z(e)
Ap = -
juQu
Σ
(p) (p)) 2 (o)
Ap = 2)
<
Quub
(a)
Σ
exp
16
1
M(d3 A 8p)
T
A3
+ exp
(16
16
M(d 8p)
T
JEQuub
(6)
T"
1
T"
Ed(00) ))
2 1
A2 (g6)
exp
exp
Mi A 8p)
16
M(d a 8p)
T
2(pp
9o + 1)
exp
A (g0)
16
M Md sp)
1
T"
+ exp
EA (go)
(70)
16
M (dB
sp)
where (a) follows Lemma
G.2 and (b) follows from the fact that minjeguab A, 2 (g)))
Then,
plloonsi
(i"(v) & Apt1 Ap =
pllpr.A (Nsubb > 8p+1 - + 1 A, Q)
E Tor-AA
/Noub
Ap Q)
8p-1 90
+1
(6)
2(sp 90 1)
1
T
1
T"
8pt1
9o
+
exp
16
M (db sp)
2 (g0)
exp
16
M (dB A sp)
E
(4) 2(hp +
1
T
T
exp
A (po)
+
exp
1p+11 +1
16
(dd A 8p)
16
Md 8p)
(e)
T
1
T"
2A
exp
A (90)
exp
MdB A sp)
16
M(2 A sp)
where (a) follows from the fact that Nsub 2 Sp+1 9u + 1 a necessary condition for i" (v) & Ap+1
when A, = Q. (b) follows Markov's inequality, (c) is obtained from 770 In addition, (d) is obtained
from the definition in 77. and (e) is obtained from the definition in
23

---

Published as a conference paper at ICLR 2024
Lemma G.4. Fix instance E P and p {M1 +1....,M M.. For any set Q [K] with [Q]
Sp
and i (0) E Q, it holds that when T" is sufficiently large
plloras (i) & Ap
Ap
Q)
s 6 exp
T
A (ppottt + exp
(-11 (-16
T
e (Alonatt))
16
M sp)
M(dg sp)
(71)
where we define 8M42 1.
Proof. Fix v E P. P E [Mi] and Q C [K] with Q - &p and (v) E Q. Similarly, let Q be the set of Sp 8942 arms in Q with the largest suboptimality gaps. Again, let
Naub
Σ jEQ Qoub
1 2x()))))))))
Then, we have
Ellla-BA
[Naub]
Ap = =Q)
E
1 (1190'2
1App = 2
jEQuab
Σ jeQuab
po BAI
(1(21=
[4 2 (i((())
Ap = 2)
1
T
1
T"
exp
16
M(d A 8p)
A + exp
{16
16
M(d A 8p)
jEQmb
(6)
1
T
(-1
1
T
3 2 Q
exp
16
(dl A 8p)
A (xp-2+1)
+ eex
16
M (dg 8p)
E
T
2(8p
8pt2)
exp
A (lontatt)
Mid A Sp) 16
1
T'
+ exp
e (e01a+1)
(72)
16
Mdg A sp)
where (a) follows from Lemma G.2 and (b) follows from the fact that min Aj 2 A As
Similarly,
have
pllorsal (i) & Apt1 Ap = Q)
TDPAA (Nsuh 2 8p-1 - 8pt2 + 1 Ap
Q)
BlllBA (Nsub Ap Q)
8pt1 - 8p42 +
(c)
2(8p 8pt2)
T'
A2 Alon12t1)
exp
8pt1 - Spt2 +
16
M M(Ba & sp)
1
T
exp
(sp12t1)
16
(db A sp)
(d)
T"
1
T
6
exp
A (
+ exp
e (
16
MdB A 8p)
16
M(d ^ 8p)
where (a) follows from the fact that Nsub 2 Spt1 8p42 + is the necessary condition (v) & Ap+1 when A, Q, (b) follows from Markov's inequality, (c) follows 772). and (d) is obtained from the definition in
24

---

Published as a conference paper at ICLR 2024
With the above ingredients in place, are ready to prove Theorem 4.2
Proof of Theorem 4.2 Fix instance o E P. Recall that in DP-BAI, the decision maker eliminates
in successive phases, and the decision maker can successfully identify the best arm if and only if it is not eliminated in any of the phases. That is,
M
DDP.BAA 1
(I))(())
S
Σ PN (f"(v) & Apt1 ('(v) E Ap).
(73)
p=1
Then, we divide the rightmost sum of the probabilities into two parts, Let
P
all aAt (i"(v) & Ap+1 (0) E Ap)
and
M Σ
P2
P.
pllor-aa (i*(v) Apt1 (0( E Ap)
p= p=M++1
In the case of K < [d/44 by definition we have Mi = 0, which implies that Pi = 0. In the case of
K [d2/44 /4] by Lemma G.3
obtain
Pi 2Mr
exp
16
1
Md
T
A
((12//AD)
exp T'
16
M
T
e e
(((1//1)))
T"
2M
exp
64M HBAL
+
64M pri
T
4Mixexp
(74)
64MH
In addition, by Lemma G.4
P2
Σ
6
cxp
T
A2 (oo11at1)
+ +exp
(-
1
T
e (d(o
16
Msp
16
Msp
p= Mi+1
Σ
6
cxp
T
A Alo ) + +oxp
T" 16
16Msp
M1+1
7"
T
6
exp
D ((opta+1)
+ exp
16M 16M 4) E (omiatt)
16M +4)
M=M++1
T"
64M A()) )(
T"
Σ
exp
+ exp 64Mi A11)
(E(s (M
T
T" (- 64MH
I <6M M1) -M)
exp
+ +exp
64MHBAI
T
< 12(M Mi) exp Finally, combining
(75)
64MH
74 and
75 for sufficiently large T" we have
pllpo-n
[ ('())()) S Pi + Pa
T"
(12M + AM exp
64MH
T
< exp
(76)
65MH
25

---

Published as a conference paper at ICLR 2024
H PROOF OF THEOREM 4.7
Let P be the set of problem instances that meet the following properties: (a) the best arm is unique;
(b) the feature vectors {a; K Rd mutually orthogonal; (c) K d > 3 and (d) 1. Hence,
we have P - P. and it suffices to consider the instances in P to prove Theorem 4.7
Note that log(d) 1, HAAT and Hpri when P'. That is, for any u P', T 0,0 0,
and B, [0, 1] with B, 2 3. for E 213, we have
exp (-
T
I exp (- c(logd)3
T
((HBAA)** (=((logd))
c(log d) ((HBAI) + (H)p))
+ (Hri)
Hence, besides we consider the instances in ,, still suffices to show that 23 holds the cases of (i) 31 [0, 1), 822 = 83 1. (ii) B2 E [0. 1), B1 33 and (iii) 33 [0, 1). 31 = 32 1. In the following, we will show that cases (i) and (ii) can be satisfied by following the argument of Carpentiirr and Locatelli (216)) while case (iii) is satisfied by the formula of change-of-measure introduced in Subsection 4.3
First, we present the proof of Lemma 4.3 in the following.
Proof of Lemin 4.3 Fix problem instance E P, policy n E N. and e E [K]. and event E = (Ir A) (NN, n) for arbitrary A S [K].
By the definition of early stopping policy, we have
((N.T < nn) = (essm <n]
(77)
and
= PSfff E A} (Ner < m)) = P (.. ((I1 A} (N.r <n)).
(78)
By the chain rule, we have
= P. =
((N.T <n)))p A (Ni, < n))
(79)
and
p.S( = PP ((N.r n) TP (ftr E A) (Nor n)).
(80)
That is,
(E) m (E).
(81)
Lemma H.1 (Adapted from Carpentier and Locatelli 2016)). Fix K > 0, H > O, and a non-private consistent policy x. For all sufficiently large T, there exists an instance v E P with K 2 K, HBAL > H such that,
P.y (Ir (iT (i)) exp (- ( log(()
401T
(82)
Note that 82 still holds even with DP constraint, and the privacy parameter & will not affect HBAL- Hence, we can have the following corollary.
Corollary H.2. Fix K O, A 0, é O and consistent policy For all sufficiently large T, there exists instance V P' with K K, HEAL H and ε = Ě such that,
401T
p. (fr # (w))
> exp (
'oog (K( (Tog
(K)HBAL())
(83)
With the above Corollary, we are now ready to discuss Case (i) in Lemma Lemma H.3. Fix any [0, 1), a consistent policy n, and a constant P such that,
O. For all sufficiently
large T, there exists instance
p. (I + (1)) > exp exp
(ap(--a
(- "(log K) K) (HBA((() + Hpei(H))
(84)
26

---

Published as a conference paper at ICLR 2024
Proof. Fix >> 0, B E (0. Let ü(K, E.),T) to be the instance in Corollary H.1 that meets
83
Then, when K exp (401 --. (2c) - we have
log( K
2c(log(K))).
(85)
401
In addition, by the definition pri we have
lim H,, =0 80+000
(86)
which implies that there exists e' (K, (H,T) such that when ē E> e'(K, H.,
Hpri(((K, ET) < (iBAI( E,,,),, since HAI would not be affected by the privacy parameter.
(87)
Finally, combining
83
and we have for sufficiently large T
P.. (Ir # (w)) > exp (- c(log K ()*(HBII(())))) + H (u))
(88)
where v = o(K, 11, E,,,,, e'( H.H), T), and K exp (401 (2c))
Similarly, we discuss Case (ii) Lemma H.4
Lemma H.4. Fix any 3 E [0, 1), a consistent policy n, and a constant > O. For all sufficiently large T, there exists an instance p' such that,
P (Ir + +())) > exp (- c(log aollo (HBAl(U) + Hpa(o)))
(89)
Proof. Again, fix > 0, 3 (0, Recall that ū(K, H,,,T) the instance in Corollary
that
meets (83. Similarly, when H > (802c) =-, we have
11
2
(90)
401
In addition, we have
lim ( H T)) =0 8-+00
(91)
which implies that there exists e' e((K, H, 2, () such that when E > el (K, H T,3),
Hpri ()), HBAI(ū(K T))
(92)
Finally, combining 83
90 and
we have for all sufficiently large T
P.
(Ir + (v))
> exp (- c(log (HBAri(()) + Hpa(v))
(93)
where = ö( H. E, e' (K, H. 3), and H (802c)
Furthermore, before we discuss (iii), introduce the following lemma.
Lemma H.5. Fix H > 0, 3 E [0, 1). a consistent policy n, and K > 3. For all sufficiently large T, there exists instance P' with K K, Hpri H. and Hpr 2 (HBAI) 8. such that,
P. (i + 80 (v)) > exp (- "oo(( K) (pH(K))))))
97T
(94)
27

---

Published as a conference paper at ICLR 2024
Proof. Fix H O, consistent policy x, and K > 3. Fix E (0, ( ) and let ys 7/-KK
for i ...... K. We construct K + problem instances e(0), v(1), ((R) P with K = K arms follows. For instance 0,.... K, the reward distribution of arm i [K] is
v Ber( 1 76 if } Ber( + 76)
(95)
==
where Ber is denoted to be Bernoulli distribution. In addition, the privacy parameters of these K + 1 instances are set to be the same, and is denoted by é. By the fact that H (vl()) - +o0 as é + 0 for all j o....: K. Then, choose be any value such that for all j 0, ...,,, K
Hpa(v!)) 2 H and Hpri (v)) 2 (H))I(vl)))
(96)
By the fact that is consistent policy, when T is sufficiently large. we have 1o (iz 1)
(97)
Furthermore, we denote n, =
4E coo) (Nv,,) to be the expected number of pulls for arm i E [K] in
instance with time budget T. Then, we define event E, {Nir n&) n {fr = 1}. It then holds that
Pi (E,)
= 1 Pio0 (-Ei)
(a]
2 1 pr (Nurr 2 4n;) - Pr (fr +
1
P go (Ni, 2 4n,) 2
(c) 1
4 2
(98)
4'
where (a) follows from the union bound, (b) follows 97 and (c) obtained from Markov's 's inequality.
Then, by Lemma 4.3 we have
(B((.....)) (F,))..))FFFFFF)))))))FF) P. FE)) > 4'
(99)
In addition, by Lemma 4.5 we have for 1,..., K
p ES m.
(E.) 2 exp ( Gen:TV (1) (0) p (Ei)
v:0)
(4) 1
cxp ( -en, (1) (1))))
4
(b)
exp(- exp(-12en:1/)
(100)
where (a) follows (9). and (b) is obtained by the definition in 95) In other words, we have
Pot (Ir # (i(((())
2 p (E.)
ES( m. (Ei)
(b)
1op(-12nn4h),
(101)
4
where (a) follows Lemma 4.3 and (b) follows (100).
Observe that for any (x:
s= C RR and (yi ( C R it holds that min D1
K --1
Σ EielR 11 2c
Dielk 2/
Then, by letting xy = n4+1 and ys ex F/ (ot+40)
we conclude that there exists (,..... K}
such that
k 1 /
nyee Hpail
<
Σ
n:
(p(H))(()))
Sye Cya
i=2
2=2
28

---

Published as a conference paper at ICLR 2024
(4)
4T/
En H (eelli)()))))
K
4T/
im2
4T
log (K) log(2)
14)
8T
(102)
log(K)
where (a) follows from the fact that Σ
i= (0)) (Ni,r) $ T, and (b) is obtained from Hpr( S (c) follows from the fact that log (o) log(2) -2 a the assumption that K > 3.
K
1 dx Σ t. and (d) is obtained by
57
Combining (IOT) and [O2]. we have
p siey (Ix (v(()))
exp(- (122mne
Hprilu())) eny Si millilpa(l(
12
exp
(- (Tog(tk) log(K) ((((K)((r((()))
96T
2 oxp
(103)
That is, when T' is sufficiently large, we have
97T (- (Tlog(R H)) (px(())))(
pat oiry
(tr + 1" ('((())))
exp
With Lemma H.. we are now ready to show that Theorem 4.7 holds Case (iii) in the following lemma.
Lemma H.6. Fix any 3 1), a consistent policy and a constant large T, there exists an instance E p' such that,
0. For all sufficiently
p. (fr # (u)) > exp (- (-c(log c(loog K (HBAI(() + (u))
(104)
Proof. Fix > 0 1). 1). Similarly, let ö(K, H. 3,T)) be the instance specified in Lemma H.5
that meets 94 Then, when A (194c) we have
2c H0).
(105)
97
Finally, combining 94). (66 and (105), we have for all sufficiently large T
P. (ir # (w)) > exp cclog () + (vr))
(106)
c(log
where ö(K, H. and H (
Proof of Theorem 4.7 Finally, by combining Lemmas H.3 holds.
and
H.6
we see that Theorem
29

---

Published as a conference paper at ICLR 2024
1 PROOF OF PROPOSITION D.2
The proof of Proposition D.2 shares some similarities as the proof of Proposition 4.1 and the difference is using the property of Gaussian mechanism instead of Laplacian mechanism.
Let NOP) = N, Under the (random) process of DP-BAI-GAUSS, we introduce an auxiliary
random mechanism ह whose input is x E X, and whose output is (Nv!") Pi )EE(K) where define /!!)) 0 if & Ap. By Dwork et al. (2014 Proposition 2.1), to prove Proposition D.2 suffices to show that मे is (e, di-fffereent private, i.e., for all neighhouring x, x' EX
p (+(x) E S) S e (f((') E E) + VS V
(107)
where 52 is the set of all possible outputs of æ. In the following, we write P to denote the probability measure induced under it with input x E X.
Fix neighbouring z, z E X arbitrarily. There exists a unique pair (i, with Zin * z addition,
fix any (P) and Borel set
Xs S [0, 1] for i E [K] and p [M] such that
0 S (1) sm (2) S... m (M) < T Vi E [K].
Let
M 1
(M) < if n
P
(108)
min{p E [M] : 2 n)
otherwise.
For any j E [M], we define the event
D3 (i.pp) N(O) n. ,,((a) {
and
D Dj (
(i) ND:1 = =n ((1) E Ex,')
For j' E (i + 1..1..... ................................ M}
DjS {(.pp) ())
N(0) nn p1(0) E }
In particular, Do and D,, MM are events with probability 1, i.e.
p
(Do n DM.M) =1 VX X.
(M) < n, by the definition of म., we have Then, if m
F (Dm) P (DM).
(109)
(M) 2 n and we will show
In the following, we assume ni
p (Dm) < exp(s) (Dm)
(110)
which then implies that म is a-iifferentially private. For x E {z, 2'), we denote
(
fx
X
(p)
(p
Ttg
11
41
That is, fx is the value of p in the condition of D', under probability measure P
2
Then, by the chain rule we have for both x E {z,zz
P (Dm)
u. (D))
E (p)
D2) pp (Dg.M D2)
= = (D') /
(p) fGauss(I
1x) (Dp. D2 n (7 =x})
dr (111)
30

---

Published as a conference paper at ICLR 2024
where fGauss (.) is the probability density function of Gaussian distribution with mean and (1gg(122//8) (=(m) 1 -n })²
variance
Note that by definition it holds
pa
D2) = 1 (D) D fp = =x}/ = =P (Dg.M D n (14 = x3) 1
Vr E X (p) (112)
(2)
p D g.M
By property of Gaussian mechanism (Dwork et al. 2014 Appendix A), there exists sets (p)
S
X with y ny= = and y+ U - ( such that
JgEN fGause (x - Px) dx S V {2,z²} (Zeyy fGauss (r (12) dr I exp(E) Joeyt fGauss (kx)) dx
(113)
Hence, combining (IT), 112 and 113 we have
P (Dm) & exp(e) (DM) +
which implies that # is (c, didifferrent private.
J PROOF PROPOSITION D.3
The proof of Proposition D.3 shares some similarities as the proof of Theorem 4.2 and the difference using the concentration bound of Gaussian random variables instead of Sub Sub--Expnential random
variables.
Lemma J.1. Fix an instance v E P and p E [M]. For any set Q C [K] with |Q] = 8p and i" (u) E Q.
let dg (span ()). We have
pllor-AAcaass
Ap = =)
[1j
A
T
1)
s²aA3 T
2
22exp
+ +2xxp
(114)
16
M (db sp)
32 log (1.25/8)
M(g A sp)
for all j (v))
Proof. Fix j E (r)). Notice that the sampling strategy of DT IDDP-BAI-AAM BAI-GAUSS depends on the relation between IQ and dg- We consider two cases.
Case 1: do > Vl2.
In this case, note that each arm in Q is pulled
times. Let
M g
= f
(1(()) + + 2 2,/
(115)
Let N1,, Ni,s
14 for all i [K] and E (T). Notice that Xi,s [-1,1] for all (i, Then,
pplloe.BAt-Gaa BAL-GASS (Ei Ap Q)
Ng.2y
No
T'' Mाअा Σ
A
T"
X
X
2
Ap
M Q
s=N, NyTrp
N
2
A
M Q
exp
T M
1
=xxp
A3
(116)
4
M Q
31

---

Published as a conference paper at ICLR 2024
where (a) follows from Lemma A.1 Furthermore, let
Eg = 15)
c(p) (sr(w) 2 A//2}.
(117)
We note that both 5) and S (v) under DP-BAI-GAUSS are Gaussian random variables with zero mean and variance and variance
((P)
L Hence, </²)
e(p) (v) is Gaussian random variable with zero mean
(=f go 1>a
4 (1g((125//))
(el शग 1)a
Subsequently,
T' (Ajel Mर 1)² lo (1 2.25/5)
PUlGE-BA--GASS (E2 Ap = 0)== S exp
We therefore have
p BAL-GUNS
(1g 2 ( [pp) (i)
Ap -)
pp BAL-GGS
[Ej U Eg
Ap = Q)
T
(Ajεl T
O 1)²
exp
s3 + exp
(118)
M(d A sp)
32 log (1.25/6)
where (a) follows from the union bound.
Case 2: do S VI2.
Similarly, in this case, each arm in Bp C Q pulled for
T' Mdo
times. Recall that we have
(60)) EieB, Ojsi a (p) Using @ this implies aj = Eies, aga as, which in turn implies that
(aj, 0*) = LiEB, ag (a,, 0-) Using 12 we then have
E Upe BALss
Ap = Q) Mg.
(119)
If $ Bp, we denote
(p) = Σ
(120)
AEB
and
() Σ
(121)
IEB
Note that
120 and 121) still hold in the case of Bp. We define the event
{ (1)0)
A
G
11 2
4
Then, have
Ip pn BpI----BA--GAa BAI-GAUSS (G1
Ap 2)
I GAiss
T
(1/1))
T'
A;
Ap 2)
Mdq
Mdq 4
N.
T' 4
I plp.o--A-GGa
Σ
Σ
arj,(Xe, -n,)
Ap
=
Mde
4
EEB
S=N,,TT-1111
(4)
2(
Mdo
T
Aj/4)2
exp
do
T
Mdq
32

---

Published as a conference paper at ICLR 2024
T
S exp
13
T"
exp
8
M A Sp)
A3
(122)
where (a) follows Lemma G. and Lemma A.
In addition, we define the event
A
22 =
By the fact that ( Gaussian random variable with zero mean and variance
(1.25//)/
[e] xrag 1)a
we have () ELEB, 2! a Gaussian random variable with zero mean and variance 2108(122//8) Note that EiEB, az I dq. then we can have EiEB, ag (el maa
(Aje T" 1)2
P BAL (G2 Ap = =Q S exp
Mdg 32dq log(1.25/0))
(Ayel T" 112 Mdo
I exp
(123)
32 log (o.((.25//6)
Define the events
(p) G3 Pi-()) (o) s
Aj
(()
-
A
4
and
G4 =
(p((0)
S
4
Similar to 122 and 123). we have
T
P PllD (Gs Ap 2) S exp
1
13
(dQ A sp)
and
(Aj&l E
T
1)2
Mdd
A 2 s exp
32 log(1 1.25/0)
Hence, Case 2, 2.we have
P Pll--nA--Dae
(16
(p)
Ap -
(1((1)
GGUGGUG, UG4 A)
I
T
1
(Ajel T'
Mdg
1)2
< 2 2xxp
A3
2exp
Mid Ap))
32 log (1.25/0)
Finally, combining both Cases 1 and 2, for sufficiently large T', we have
(p)
Ap 2)
(()
(Ajεl
T
T
Mid A.y
2exp
A?
+ 2 exp
Mid A 8p)
32 loglll.25 (1.25//))
(Ayol
T"
1)2
< 2exp
A2
+ 2exp
16
M(d ^ sp)
32 log (1.25/0
33

---

Published as a conference paper at ICLR 2024
Lemma J.2. Fix instance P and [M Recall the definitions of A in and go in 8 For any set Q C [K] with [2] = sp and i" (z) E Q. it holds
(v) $ Ap+1 1 Ap Q)
(-1
T'
A (80)
1
T
Ar(d5 Asp)
$ 21
exp
A(00)
+ +exp
16
M sp)
32 log (1.25/0)
Proof. Fix U P.p [Mi] and Q [K] with [Q] Sp and (0) Q. Let Quub be the set of Ap 90 + arms in with largest suboptimal gap. In addition, let
Naub
Σ @EQubb
be the number of arms in Quub with private empirical mean larger than the best arm. Then, we have
E
(Nsub
Q)
Σ
1 (1mf"227/P0)) A = 2
jE jEQuab
Σ
po Bpllo--At--cass
(p!T)) 2 pi(()) An 2)
jeQuu
(A,E
Midd map) 1)2
T
2
exp
16
M (dl A sp)
A3 exp
32 log( (1.25/0)
JEQuub
(9
Midd 7)22
1
T
2
exp
A2 (90)
+ exp
16
M(d A 8p)
32 log(11222 (1.25/8)
T
2(8p
90
+ 1)
exp
A (g0)
16
Md3 A 8p)
(A (10)
1)2
Md
+ exp
(124)
32 loglo1112 (1.2(11)//8))
n where (a) follows Lemma J.1 and (b) follows from the fact that min Quat A, 2 A
Then,
ooe BAI GAUSS
(i*(u) & Ap+1 Ap =Q=
(Nsub 2 8p+1 - 90
A, = Q)
E DA (Naub
Ap = Q)
8pt1 9o +
(A
Midgy n 1)2
T'
(c)
2(Sp 90 + 1)
1
T
stoo) + exp
8p+1 - 9o +
exp
16
M A 8p)
32 log (1 ..25
(A
MidgAapp 1)2
7"d
(d)
2(hp 1)
T"'
exp
+ exxp
hp+ +
16
M(Ba ^ sp)
32 log( (1. 1.25/8)
(A (A)))
T"
1)2²
1
T
M(d
21
exp
exp
16
M
(d2 sp)
32 logg1.25//5)
34

---

Published as a conference paper at ICLR 2024
where (a) follows from the fact that N 2 8p+1 1 90 9o 1 necessary condition for (v) & Ap+1
when A, = Q, (b) follows from Markov's 's inequality, and (c) follows from (124). In addition, (d) is
obtained from the definition in (7) and (e) is obtained from the definition in (6)
Lemma J.3. Fix instance E and p E {M1 + ................... M) For any set Q C [K] with [Q] Sp and i" (e) E Q, it holds
p spl---- (i*(u) & Ap+1 Ap = Q)
T' 1)2 (A(omatt1) M(dg
T"
A Slomattt) exp
< exp
16
M [d A Sp)
32 log(1.25/
(125)
where we define SM+2 1.
Proof. Fix v E P.y [Mi] and Q C [K] with Q - sp and i" (v) E Q. Similarly, let Qsub be the set of 8p Sp+2 arms Q with the largest suboptimality gaps. Again, let
Noub
Σ
jEQuub
Then, we have
By
(Naub)
Ap Q
Σ
E B.lS
1 (1859) 22(0)
Ap = 0)
jE Qrub
Σ
pllor-BARGAES
(F!T)) 2 (P
(p)
Ap 2)
jE Quub
( (AfEl
de(dB (op) 1)2
T"
T
2
cxp
A3 exp
16
M (dB sp)
32 log (8.2
jEQubb
(A (A(
Midg (op) 1)2
T
2 Quub
exp
A Alomeatt)
+ exp
16
Mig A sp)
32 (9.2g1/5//0)
1
T
2(5 Sp+2)
exp
16
(dB sp)
A D (oppat))
(A 1)
M(B Asp) 1)2
+ exp
(126)
32 log(1 (1.25/8)
where (a) follows from Lemmal J.1
and (b) follows from the fact that minjegmth A, 2 A As
By similar calculation,
polo--St--AASS (i*(w) $ Ap-1 Ap =Q)
IΛG WV
(Arsh) 2 8pt1 8pt2 + A, 2)
E TTp BAL-GASS
(Nsubb
Ap = Q)
8pt1 8p42 +
2(sp - 8pt2)
7
A 2
exp
8pt1 8p42 +1
16
Mída ^ 8p)
(A (A(ope2t1je)
T
1)2
(ap)
+ exp
32 2ollo11.25
35

---

Published as a conference paper at ICLR 2024
(A(opeat))
T Mr (.p)
1)2
(d)
1
T"
A 2 (spszt1)) + exp
exp
16
Míd A 8p)
32 (lo(1.25)) (1.25//)
where (a) follows from the fact that Asub 2 Sp+1 Sp+2 is the necessary condition i* (v)) & Ap+1 when A, = 2, (b) follows from Markov's incquality, (c) follows from (26). and (d) is obtained from the definition (7)
With the above ingredients in place, we are now ready to prove Proposition D.3
Proof of Proposition D.3 Fix instance v E P. Recall that in DP-BAI-GAUSS, the decision maker eliminates arms in successive phases, and the decision maker successfully identify the best arm if and only it is not eliminated in any of the phases. That is,
po BAI GAUSA
(Ir (1++i()) i0)
Σ
pUl (i) Ap+1 (0()) e Ap).
Then, split the rightmost sum of the probabilities into two parts. Let
Mi
Pi
Ue BAL-GAMS
(i(v) $ Ap+1 (0(v) E Ap)
p=1
and
M
P2
Σ
To BAI GAUSS (i"(v) & Apt1 (v) E Ap)
p=M++1
When K < d / by definition, we have Mi = O, which implies that Pi = 0. When K > 14/4
by Lemma J.2 we obtain
T
(-1 (A(rP/// Ma 1)2
T
Pi < 2M
exp
A Altar/on)
+ exp
16
Md²
32 (1.2//)5/
T
T
$
2M,
exp
64MHBAI
+ cxx
64MH log(1 (1.55/))
(127)
In addition, by Lemma J.3
Pg <
Σ
M
6
exp
T
A (optatt))
+ eexp
(A 1)
Meo
T' 1)2
16
Msp
32 logll11122 (1.55/0)
p=M++1
M
(A (A(sp- M(48p42
T'
12
Σ
6
exp
2 (ontatl)
+ exp
16M (48 + 4)
32 log( (1.5//))/0)
p=M++1
+1
T
T'
Σ
6
exp
A1))
+exp
64Mi
64Miv/ogg(1. /og((125/// 11.55/)
T
T
< 6(M -M)
exp
64MHBAI
+ cxp
64MH pet / log (1.25/8)
(128)
Finally, combining 117 and (12
for sufficiently large T' we have
ppllo--AL-GW
i (v))
< P + P2
T
(Vress( (VDert
T
S exp
-Ω
HBAi logd"
(log(L)))) Hpri log d
This completes the proof.
36


Reviews:
[{"review_id": "uRgJnNY3X4", "reviewer": "Reviewer_9gBt", "summary": "This paper is the first to study best arm identification (BAI) in linear bandits under a fixed DP budget budget. With extensive research focusing on DP MAB, this paper tries to answer this problem through a different lens of \"pure exploration\". This work serves as a valuable complement to the current body of literature.", "questions": "Please refer to weakness", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To this end, the paper proposes a policy satisfying $\\epsilon$-DP, thus providing an upper bound of the decaying speed of the error probability. The paper also provides an almost-matching lower bound. Empirical evaluation is also provided to show the effectiveness of the algorithm.", "weaknesses": "Although this is a nice work, I still suggest the paper provide more discussion on the connections between this problem to 1) BAI in the fixed-confidence regime, 2) and generally, MAB under DP. I understand superficially speaking they are different problems, but it is not very clear (to me) whether or not there exist some connections  deeper. For example, there might be a simple adaptation of previous algorithms to suit this setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jOFXSBoV8M", "reviewer": "Reviewer_pqgE", "summary": "This paper investigates the best arm identification (BAI) problem in multi-armed bandits with differential privacy (DP) guarantees. It focuses on the fixed-budget BAI setting, aiming to minimize the error probability of selecting a suboptimal arm within a set number of arm pulls (budget). Notably, the paper introduces DP-BAI, the first algorithm to achieve DP guarantees in the fixed-budget BAI context. This algorithm outperforms a naive approach that directly incorporates a DP mechanism into the existing state-of-the-art non-private BAI algorithm.", "questions": "- see Weakness 1: How does DP-BAI compare to OD-LinBAI, especially when $\\epsilon\\to\\infty$? \n\n- Page 4, Definition 3.1: Why is a Max-Det collection of $\\mathcal{A}$ always linearly independent raises questions. Does this implicitly assume that $\\mathcal{A}$ spans $\\mathbb{R}^{d'}$? \n\n- Regarding Algorithm 1:\n  - Lines 8, 14: The phrasing in these lines is confusing and seems inconsistent with earlier descriptions. The term \"pull each arm XX times\" is ambiguous. From the description, it appears that, in line 8, every arm in $B_p$ is pulled $T'/Md_p$ times, totaling $T'/M$ arm pulls. Meanwhile, in line 14, it seems there are a total of $T'/Ms_p$ arm pulls, with each pull randomly choosing an arm from $A_p$. \n  - Can the authors provide some high-level intuition behind the choice of $g_i$ and $h_i$ as described in equations (5) and (6)?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper introduces the first algorithm to solve the BAI problem within a fixed-budget constraint and under DP guarantees. The paper also offers an extensive theoretical analysis, establishing an upper bound on the error probability for the new algorithm, which is adaptive to the complexity of the problem measured by $H_{BAI}, H_{pri}$. Furthermore, it provides a matching lower bound, demonstrating that the algorithm attains optimal performance in this specific setting.", "weaknesses": "The paper lacks a detailed comparison with existing non-private fixed-budget BAI works. For example, a natural question is: Does the error probability of DP-BAI converge to that of the state-of-the-art non-private counterpart when $\\epsilon \\to \\infty$? Such an analysis would be valuable in understanding the trade-offs between privacy and performance.\n\nMoreover, I personally believe that the writing of this paper, especially in the algorithm description section, could be improved. Currently the presentation has a lot of notations, many without adequate explanations. A more detailed explanation of each notation and some high-level insights would significantly improve the paper's readability and effectively convey the core ideas.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CpqleDPKDo", "reviewer": "Reviewer_Nv4R", "summary": "The authors propose and analyze an algorithm for the fixed-budget best-arm identification problem with differential privacy constraints. The algorithm is based on differentially private version of MAX-DET rather than adapting established fixed-budget BAI algorithms. In the appendix the authors provide a general analysis of natural possible extension of one such algorithm and clearly benchmark their algorithm with this extension. The lower bounds also depend on new notions of complexity which incorporate differential privacy as a constraint in policy design.", "questions": "--\nI am skeptical about their definition of DP since it is defined over length $T$ sequences. I would expect that in the online setting this definition would only be defined over a sample of sequence starting from the time when the reward sequences differ as done in joint differential privacy. \n\n--\nI would like an intuitive explanation of why their algorithm works on a small example somewhere in the paper (maybe, in an appendix).\n\n-- \nFinally, the central idea of the paper is to use D-optimal design rather than G-optimal design. These ideas are theoretically equivalent (see Proposition~3 in Soare et al. NeurIPs 2014) but  this paper demonstrates a dramatic performance improvement in their numerical experiments. What is the intuitive explanation for this?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I think the authors provide fundamental analysis of the problem in terms of the upper and lower bound. The main strength of the contribution is demonstrated by proving that the algorithm matches instance optimal bounds. Further, the algorithm idea is new itself and clearly outperforms existing benchmarks (and straightforward adaptations thereof).", "weaknesses": "I think the paper can be written more intuitively given that it has a lot of parameters. For example, while the algorithm is stated clearly, I am unsure why it works intuitively. What makes the apparent dimension go down for the first few rounds? How does decreasing the span basis vectors of the arm space lead to convergence to the optimal arm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XLCaO1XPHA", "reviewer": "Reviewer_mZMs", "summary": "This work studied the way to adopt differential privacy on the Best Arm Identification policy. The main trick is to append each arm's empirical mean with proper Laplace distribution.", "questions": "1. Motivation to consider DP-BAI algorithm. For my understanding, DP is for preventing potential privacy risk when sharing statistics of a dataset. I would be great for the author to provide motivation to consider DP in bandit problem, especially on the best arm identification task. \n\n2. Intuition on scheme (7). I had difficulty to make sense on  the scheme (7) and would be thankful is author can provide explanations.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The work provide comprehensive details on establishing its theoretical claims.", "weaknesses": "The empirical evaluation is limited on a particular synthetic data instance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4gsItay2e5", "reviewer": "Reviewer_fyMv", "summary": "This paper studies the problem of identifying the best arm in a differentially private manner. This paper focuses on the pure DP setting. Here, the privacy model is as follows. At each time step T, there are K arms. Each arm has a potential reward x_{t, k}. The algorithm is DP if, changing only one of the x_{t, k} causes the trajectory of arms that are selected to satisfy the usual eps-DP property.\n\nThe authors prove tight upper and lower bounds for this problem. In particular, they determine a parameter, similar to the parameter in the non-private setting, which essentially governs the error rate of the algorithm.", "questions": "See weaknesses above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies an interesting problem and will be of interest to researchers working on DP and bandits. The authors also prove tight results so I believe this is a significant contribution to the literature. The writing quality and clarity is good. The lower bound is a nice technical contribution.", "weaknesses": "Unless I misunderstood, two datasets are neighboring if the set of possible rewards differ in only one location. I'm curious what the motivation for this is. For example, if we use clinical trials as the motivating example then each arm may correspond to a different treatment. In this case, I would view two datasets as neighboring if the set of observations differ at one step which could mean that all K arms at a single time step have different rewards. I am curious how this impacts the results of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)