Faster Rates for Private Adversarial Bandits
Authors: Hilal Asi
Vinod Raman
Kunal Talwar
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Bandits
Primary area: social_aspects->privacy
TL;DR: We design new differentially private algorithms with improved privacy and utility tradeoffs for adversarial bandits and bandits with expert advice.

Abstract: We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of $O\left(\frac{\sqrt{KT}}{\sqrt{\epsilon}}\right)$, improving upon the existing upper bound $O\left(\frac{\sqrt{KT \log(KT)}}{\epsilon}\right)$ for all $\epsilon \leq 1$. In particular, our algorithms allow for sublinear expected regret even when $\epsilon \leq \frac{1}{\sqrt{T}}$, establishing the first known separation between central and local differential privacy for this problem. For bandits with expert advice, we give the first differentially private algorithms, with expected regret $O\left(\frac{\sqrt{NT}}{\sqrt{\epsilon}}\right), O\left(\frac{\sqrt{KT\log(N)}\log(KT)}{\epsilon}\right)$, and $\tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{\epsilon ^{1/3}} + \frac{N^{1/2}\log(NT)}{\epsilon}\right)$, where $K$ and $N$ are the number of actions and experts respectively. These rates allow us to get sublinear regret for different combinations of small and large $K, N$ and $\epsilon.$

Faster Rates for Private Adversarial Bandits
Hilal Asi
Vinod Raman 2 Kunal Talwar"
Abstract
the loss of selected actions, such that its expected regret
We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, give a simple and efficient conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of O [KT
T
E
Σ (e(I))
arg min
Σ (()
xE[K]
is minimized, where the expectation is taken with respect to the randomness of the learner.
Bandit algorithms, and in particular adversarial bandit algo- rithms (Auer et al., 2002), have been of significant interest for over two decades (Bubeck et al., 2012) due to their applications to online advertising, medical trials, and recom- mendation systems. In many of these settings, one would like to publish the actions selected by bandit algorithms without leaking sensitive user information. For example, when predicting treatment options for patients with the goal of maximizing the number of cured patients, one may want to publish results about the best treatment without leaking sensitive patient medical history (Lu et al., 2021). In online advertising, goal is to publish the recommended ads with- out leaking user preferences. In light of such privacy con- cerns, study adversarial bandits under the constraint of differential privacy (Dwork, 2006). Surprisingly, unlike the stochastic setting (Azize & Basu, 2022), the price of privacy in adversarial bandits is not well understood. Existing work by Agarwal & Singh (2017) and Tossou & Dimitrakakis (2017) give E-differentially private bandit algorithms with expected regret at most O /KTlog(K)
VE
improving upon the existing upper bound O (TTloR(KT) for all E $ 1. In particular,
our algorithms allow for sublinear expected regret even when first known separation between central and local differential privacy for this problem. For bandits with expert advice, give the first differentially private algorithms, with expected /KTlog(V]log(kK)
VT. establishing the
VNT V8
regret
( where K' and N are the number of actions and experts respectively. These rates allow us get sublinear regret for different combinations of small and large K, N and
and Ô Ny11 2/11/x/1/222//3 (og(NT)
N2 14/21ng(NT) (og(NT)
gl/s
However, their
1. Introduction
algorithms satisfy the stronger notion local differential privacy and become vacuous for tasks with high privacy requirements, where one might take 5 VT In fact, was not known how large E needs to be in order to obtain sublinear expected worst-case regret.
In the adversarial bandit problem, learner plays se- quential game against nature over T E N rounds. In each round t E {I....,T), T"
nature picks a loss function 4: [K] > [0, 1]. hidden to the learner. The learner, using the history of the game up to time point L 1, selects a po- tentially random action 1 {l...., ..} and nature reveals only the loss (o:)) of the selected action. For any sequence of loss functions L1, .1.....6. lr, the goal of the learner is to se- lect sequence of actions T,...., TT. while only observing
Main Contributions. Motivated by this gap, we provide new, differentially private algorithms for adversarial ban- dits and bandits with expert advice with better trade-offs between privacy and regret. In the adversarial bandits set- ting, we provide simple and efficient conversion of any non-private bandit algorithm into private bandit algorithm. By instantiating this conversion with existing (non-privat
'Equal contribution 'Apple Departmennt of Statistics, Univer- sity of Michigan, Ann Arbor. Work done while interning at Apple. Correspondence to: Vinod Raman <vkraman uumich.edu>.
In( TTosoou & Dimitrakakis (2017) also claim to give algorithm
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
with regret Ö f2/3 /Kln(K)
however, we are unable to verify
2173
its correctness. See Appendix G.I.

---

Faster Rates for Private Adversarial Bandits
bandit algorithms, we get e-differentially private bandit algo- rithms with expected regret at most O upon the best known upper bounds for all E I 1. In particu-
The first works for bandits with expert advice also date back at least to that of Auer et al. (2002), who propose EXP4 and bound its expected regret by O ( (o)))) where N is the number of experts. When 2 K, Seldin & Lugosi (2016) prove a lower bound of 2 the expected regret, showing that EXP4 is already near opti- mal. As a result, EXP4 has become an important building block for related problems, like online multiclass classifica- tion (Daniely & Helbertal, 2013; Raman et al., 2024) and sleeping bandits (Kleinberg et al., 2010), among others.
KTT VE
improving
lar, this result shows that sublinear regret is possible for any E E w (+). As corollaries. we establish separations in the achievable regret bounds between:
K
on
(1) Oblivious and Adaptive adversaries. In particular, while we show that sublinear regret is possible for all choices of E w(+) under an oblivious adversary, this is not the case for an adaptive adversary, where one cannot achieve sublinear regret if & E of (T) (Asi et al., 2023).
Private Online Learning, Dwork et al. (2010a) initiated the study of differentially private online learning. Jain et al. (2012) extend these results to broad setting of online convex programming by using gradient- based algorithms to achieve differential privacy. Following this work, Guha Thakurta & Smith (2013) privatize the Follow-the-Appoot Shhh--pproximate--aae Leader template to obtain sharper guarantees for online convex optimization. In the special case of learning with expert ad- vice, Dwork et al. (2014) and Jain & Thakurta (2014) give private online learning algorithms with regret bounds of O (Tlog(N)
(2) Central and Local differential privacy. While our re- sults show that sublinear regret is possible i E ol /T) under central differential privacy, it is well known that this is not the case for local differential privacy.
For bandits with expert advice (Auer al., 2002), we give the first differentially private algorithms. In particular, we give three different (s, diffferrrry private bandit algorithms, obtaining expected re- and
More recently, Agarwal & Singh (2017)
e
gret
O O (NTT
O (NT VE
design private algorithms for online linear optimization with regret bounds that scale like O(vT) + O In particular, for the setting of learning with expert advice, they show that it is possible to obtain a regret bound that scales like O (Volog(NN + N log(N) log T improv- ing upon the work by Dwork et al. (2014) and (Jain & Thakurta, 2014). For large N, this upper bound was further improved to O (ogg) + T1/2 log(N) and
6 N1/2 log NT)
Ô /N10 (Vg( 6173
respectively. These regret guarantees cover regimes with high-privacy requirements and regimes with a large number of experts N. In both settings, our techniques involve combining the
5
Laplace mechanism with batched losses.
1.1. Related Works
o ( (VTloogN) + (og(N) by Asi at (2023) and Asi 2273
Adversarial Bandits and Bandits with Expert Advice. We refer the reader to the excellent book by Bubeck et al. (2012) for a history of stochastic and adversarial bandits. The study of the adversarial bandit problem dates back at least the seminal work of Auer et al. (2002), who show that a modification to the Multiplicative Weights Algo- rithm, known as EXP3, achieves worst-case expected regret o TT log( K)
et al. (2024) respectively in the oblivious setting.
Private Bandits. The majority of existing work on differen- tially private bandits focus on the stochastic setting (Mishra & Thakurta, 2015; Tossou & Dimitrakakis, 2016; Sajed & Sheffet, 2019; Hu et al., 2021: Azize & Basu, 2022), linear contextual bandits (Shariff & Sheffet, 2018; Neel & Roth, 2018), or adjacent notions of differential privacy (Zheng et al., 2020; Tenenbaum et al., 2021; Ren et al., 2020). To our knowledge, there are only three existing works that study differentially private adversarial bandits. The first is by Guha Thakurta & Smith (2013) who give an 6)- differentially private bandit algorithm with expected regret KT3/4 Finally, and in parallel, Agarwal & Singh (2017) and Tossou & Dimitrakakis (2017) improve the up-
Following this work, there has heen an explosion of interest in designing better adversarial bandit algorithms, including, amongst others, the work by Audibert & Bubeck (2009), who establish that the minimax regret for adversarial bandits is θ (VTK) More recently, there has been interest in unifying existing adversarial bandit algo- rithms through the lens of Follow-the-Resn Regullarize Leader (FTRL) and Follow-the- Dollow-the-Peeturte Settuuree-LLLdded (FTPL) (Aber- nethy et al., 2015). Surprisingly, while it was known since the work of Audibert & Bubeck (2009) that an FTRL-based approach can lead to minimax optimal regret bounds, it was only recently shown that this is also the case for FTPL-based bandit algorithms (Honda et al., 2023).
per bound O < (KT)gg(K) We note that the private
algorithms given by Agarwal & Singh (2017) and Tossou & Dimitrakakis (2017) satisfy the even stronger notion of
2

---

Faster Rates for Private Adversarial Bandits
Table 1. Summary of upper bounds with constant factors and dependencies on log & suppressed. The three rows for Bandits with Experts represent different algorithms with incomparable guarantees.
Existing Work
Our Work
Adversarial Bandits
(KT
K
VE
Bandits with Experts
NA
NT
KT (Ng( (og(
Bandits with Experts
NA
N1 p1/ NT)
N172 NT)
Bandits with Experts
NA
+
1//
local differential privacy (Duchi et al., 2013).
tion that A outputs when run on (4, (4,)) In addition. we will sometimes use Hi == (7,, (T.))) to denote the history of selected actions and observed losses induced by running A up to, but not including, timepoint E N. Note that Hi is a random variable and we may write the action selected by algorithm A on round E N as A(Ha)- It will also be helpful to think about H. as the View of A as a result of its interaction with the adversary up to, but not including, timepoint I.
2. Preliminaries
2.1. Notation
Let K E N denote the number of actions and é [K] + [0, 1] denote an arbitrary loss function that maps an action to bounded loss. For abstract sequence 21..... 2n. we abbreviate it as 21:n and (zx)==1 interchangeably. For a measurable space (X, (x)))))) we let II(2)) denote the set of all probability measures on X. We let Lap(A) denote the Laplace distribution with mean zero and scale such that its probability density function is fx(x) 2 exp (=) Finally, we let [N] = {1, [L....,A) N} for N N.
Given a bandit online learner A, we define its worst-case expected regret as
T Σ
C(AAHA))
RT K) = sup f1.2
E
- inf Σ 401
<E(K]
where the expectation is taken only with respect to the ran- domness of the learner Our goal to design a bandit algorithm A such that RA(T, K) o(T)- Note that our definition of regret means that we are assuming an oblivi- ous adversary. one that selects the entire sequence of losses f,...., by before the game begins. This assumption is in contrast to that of an adaptive adversary which, for every E N. may select the loss & based on He. We leave quanti- fying the rates for private adversarial bandits under adaptive adversaries for future work. That said, we do note that the lower bounds for adaptive adversaries established in full- information setting by Asi et al. (2023) also carry over to the bandit feedback setting. Accordingly, Corollary 3.2 and Theorems and 5 in Asi et al. (2023) show that the strong separation the possible rates for oblivious and adaptive adversaries also holds under bandit feedback.
2.2. The Adversarial Bandit Problem
In the adversarial bandit problem, learner plays a sequen- tial game against nature over T E NN rounds. In each round t E [T]. the learner selects (potentially randomly) an action 4 E [K] and observes only its loss (4))). The goal of the learner is to adaptively select actions
E [K] such that its cumulative loss close to the best possible cumulative loss of the best fixed action E [K] in hind- sight. Crucially, we place no assumptions on the sequence of losses f ly, and thus they may be chosen adversar- ially.
Before we quantify the performance metric of interest, we provide a formal definition of a bandit online learning algo- rithm. This definition will be useful for precisely formaliz- ing the notion of privacy (Section 2.4) and describing our generic transformation of non-private bandit algorithms to private ones (Section 3).
2.3. The Bandits with Expert Advice Problem
In adversarial bandits with expert advice (Auer et al., 2002). we distinguish between a set of experts [N] and the set of available actions [K]. In each round E [2]] each expert [N] predicts distribution paر [[[K]). The learner uses these predictions to compute its own distribution jue E [[[[)), after which it samples 4 ~ fa and observes the loss (T,).. The goal of the learner is to compete against the best fixed expert in hindsight while observing bandit feedback. We need a new definition of a bandit with expert
Definition 2.1 (Bandit Algorithm). A bandit algorithm is deterministic map A ([K) x RR' + I((K)) which, for every t E N. maps history of actions and observed losses (I,, Ea (Z.) E ([K) x R)(-1 to a distribution H4 E I[(K)). The learner then samples an action 1; ~ fr-
We will slightly abuse notation by using A((I, (1 to denote the random action J, drawn from Pt, the distribu-
3

---

Faster Rates for Private Adversarial Bandits
advice algorithm to account for the fact that the learner has access to expert advice.
We use an analogous definition of differential privacy for bandits with expert advice.
Definition 2.2 (Bandits with Expert Advice Algorithm). A bandit with expert advice algorithm is a deterministic map A: ([K] R)* (II([K))*)* + [[((K) which, for every t E N. maps the history of actions and observed losses (14)) E ([K) x R)--1 as well the sequence of expert advice #I: E (() to a distribution fi E [((]). The learner then samples an action action I, ~ fi--
Definition 2.4 ((s, -iiffferrent Privacy in Bandits with Expert Advice (Dwork et al., 2014)), A bandit with expert advice algorithm A is (e, diifferrrrtl private if for every T E N. any two sequences of loss functions f1TT and f/rr differing at exactly one time point t' we have that IP (((((H)) A(H2), A(HH))....A((H))) E S e [(A(())))) A(H() A(H.. E E E where we let H4 = (T,, lo (T.)) and H. = (T., e. (..)
[T], and any E
[K]T
One can now take analogous definition of worst-case expected regret to be
Note that Definition 2.4 implicitly assumes that only the sequence of losses is sensitive information and that expert predictions are public.
T
RA(T,K,N, = sup sup ELST
E
Σ
& (A(He,
(1 ))
Our main focus in this work will be on designing bandit algorithms that satisfy pure differential privacy (i.e. when 8 = 0). In Appendix A, we review several fundamental properties of privacy and
T
K
inf JEIN
m4)) 1=
(((1)
mechanisms that serve as important building blocks.
where the expectation is taken only with respect to the ran- domness of the learner. As for adversarial bandits, our definition of minimax regret for bandits with experts advice implicitly assumes an oblivious adversary.
3. Faster Rates for Private Adversarial Bandits
In this section, we establish a connection between non- private bandit algorithms that can handle negative losses and e-differentially private bandit algorithms. Let B be any bandit algorithm and define
2.4. Differential Privacy
In this work, we are interested in designing bandit algo- rithms that have low expected regret while satisfying the constraint of differential privacy. Roughly speaking, differ- ential privacy quantifies the following algorithmic property: an algorithm A is private bandit algorithm if, for any two sequences of losses that differ in exactly one position, the distributions over actions induced by running A on the two loss sequences are close. Definition 2.3 formalizes this notion of privacy in adversarial bandits.
RT K,A) = sup Exe
E
Σ ((B((H))
inf EE[K]
E
Σ Σ
T > (,(
sup fur
E
((((L))
inf <E[K]
where (0))= = (e( + Zo(i) with (1) ~ Lap(A), H. (Is, E ([=))==1+ and the expectation is taken with respect to both the randomness of B and the losses (T.-- Theorem 3. states that one can always convert B into an e-differentially private bandit algorithm A whose regret guarantees can be written in terms of (T, K,
Definition 2.3 ((e, Diffferrrnt Privacy in Adversarial Bandits (Dwork et al., 2014)). A bandit algorithm A is (E, 6) diffferrrentllllyy private if for every T E N, any two sequences of loss functions f1.r and frrr differing at ex- actly one time point t' E [T'] and any E C [K]". we have that P ((A(H))) ), A(HH))...... A(Hr))
Theorem 3.1 (Generic Conversion). Let B be any bandit algorithm. Then, for every T 2 1 and E S 1, there exists an e-differentially private bandit algorithm A, such that
<
e ((A(H)) A(H,) A(H))) E E]+
+8 8, where we let H4 (I,, (T.)) and Hi (T,, (-.
RA, (T, S TR.B
( + (
(-
T
ET
We note that the our notion of differential privacy in Defini- tion 2.3 is inherently for an oblivious adversary. A different definition of privacy is required if the adversary is allowed to be adaptive i.e., having the ability to pick the loss e, using the realized actions /,, .,,..., T--1 played by the learner (see Definition 2.1 in Asi et al. (2023) for more details). While the utility guarantees of our bandit algorithms hold only for oblivious adversaries, their privacy guarantees hold against adaptive adversaries.
In particular, picking T = [2] means that there exists
e-differentially private bandit algorithm A such that
2 [T RB (=T, (TT,K1)) 1,1)+ 2
As a corollary of Theorem 3.1, we establish new upper bounds on the expected regret under the constraint of g- differential privacy that improves on existing work in all
4

---

Faster Rates for Private Adversarial Bandits
regimes of e > O. In particular, Corollary 3.2 follows by letting B be the HTINF algorithm from Huang al. (2022), which modifies Gollow-the-Regllarize----aee (FTRL) for heavy-tailed losses.
Algorithm Non-Private to Private Conversion
1: Input: Non-private bandit algorithm B, batch size T, privacy parameter E E (0, 1]
Initialize: j =
Corollary 3.2 (FTRL Conversion). For every e E [ 1}, if B is HTINF with a and o v6, then Algorithm when run with B and = 1 is e-diffrrenially private and suffers worse-case expected regret at most
3: for t ,...., do
4: if - (j ( + 1 then
5: Receive action 1, from B.
6: end
7: Play action 4, ;- 1 Observe loss (I)).
VTK VE
O
if f jr then
10: Define e5(i) := - - (i(i)
11:
Pass (,(4,) + 2, to B. where Z3 ~ #
In Appendix E, we instantiate Theorem 3.1 with EXP3 and FTPL to obtain two other upper bounds. In every case, our upper bounds establish the first known separation in rates between central differential privacy and local differential privacy (see Appendix A for definition) for this problem. Namely, while the lower bounds from Basu et al. (2019) show that any local e-differentially private bandit algorithm must suffer linear (TT) expected regret when E < VT* Corollary 3.2 gives an algorithm satisfying e-central differ- ential privacy (i.e. Definition 2.3) whose expected regret is sublinear (T') even when E < 1. The remainder of this vT section is dedicated to proving Theorem 3.1. Corollary 3.2 is proven in Appendix D.
12: Update j+
13: end if
14: end for
(non-local) differential privacy.
Algorithm provides the pseudo code for converting non- private bandit algorithm to private bandit algorithm.
Lemma 3.3 (Privacy guarantee). For every bandit algo- rithm B, batch size T 2 1, and S 1, Algorithm I is E-differentially private.
Proof. (sketch of Lemma 3.3) Observe that Algorithm 1 applies the bandit algorithm B on the losses l,,-.., . in a black box fashion. Accordingly, the privacy guaran- tee of Algorithm 1 follows from the privacy guarantee of & (I1),.... 2 (4(=) and post-processing. The privacy of each (1,), follows from the Laplace mechanism.
3.1. Proof of Theorem 3.1
The conversion behind Theorem 3.1 is remarkably simple. At a high-level, it requires simulating the non-private ban- dit algorithm on noisy batched losses. That is, instead of passing every loss to the non non-private bandit algorithm, we play the same arm for batch size т, average the loss across this batch, add independent Laplace noise the batched loss, and then pass this noisy batched loss to the non-prine non-private bandit algorithm. By adding Laplace noise to batched losses as opposed to the original losses (as is done by Tossou & Dimitrakakis (2017) and Agarwal & Singh (2017)), the mag- nitude of the required noise reduced by multiplicative factor of the batch size.
A rigorous proof of Lemma 3.3 is in Appendix C.
Lemma 3.4 (Utility guarantee). For every bandit algorithm B, batch size T 2 1, and ε S 1, the worst-case expected regret of Algorithm is at most ( K, +
The proof of Lemma 3.4 follows from the following result by Arora et al. (2012).
However, a key issue that needs to be handled when adding noise (whether to batched or un- un- batched losses) is the fact that the losses fed to the non-private bandit algorithm can now be negative and unbounded. Accordingly. in order to get any meaningful utility guarantees, Theorem 3.1 effec- tively requires our non-private bandit algorithm to handle unbounded, negative (but still unbiased) losses. Fortunately, there are several existing adversarial bandit algorithms that can achieve low expected regret while observing negative losses. Three of these are presented in Corollary 3.2, 1. and E.3. To the best of our knowledge, this is the first work to establish a connection between handling negative losses (for example in works that handle heavy-tailed losses) and
Theorem 3.5 (Theorem 2 in (Arora et al., 2012)). Let B be any bandit algorithm. Let 2 1 be batch size and let A,, be the batched version of B. That is, the bandit algorithm Ar groups the rounds 1,..., T into consecutive and disjoint batches of size T such that the j ''th batch begins on round (j -1)T + 1 and ends on round jr. At the start of each batch j the algorithm A, calls B3 and receives action I drawn from B's internal distribution. Then, Ay plays this action for T rounds. At the end of the batch, Ar feeds B with the average loss value 1 533 -==(s-1)r4 1)r4 (T(T)). For such an algorithm A,, its worst-case expected regret is at most Rg (T, K) +
5

---

Faster Rates for Private Adversarial Bandits
Note that Algorithm 1 is precisely the batched version of its input B. Accordingly, Theorem 3.5 immediately implies that any sequence CL.T. the expected regret of Algorithm _-_ I is at most rRg(? 7 K, ) + T. We provide complete proof of Lemma 3.4 in Appendix C.
algorithm whose worst-case expected regret most
VTN VE E
1 +
4. Upper bounds for Bandits with Expert Advice
The upper bound in Corollary 4.3 is non vacuous for con- stant or small N (i.e. N & K). However, this bound is vac- uous when N grows with T. To address this, we consider EXP4 which enjoys expected regret O (VKT (og()) in the non- private setting, exhibiting only a poly-logarithmic dependence on N (Auer et al., 2002). The following the- orem shows that by adding independent Laplace noise to each observed loss, a similar improvement over Corollary 4.3 can be established for large N, at the cost of a worse dependence e.
Theorem 3.1 also allows us to give guarantees for bandits with expert advice. To do so, we need Theorem 4.1, due to Auer et al. (2002), which shows that any bandit algorithm can be converted into a bandit with expert advice algorithm in black-box fashion. For completeness, we provide this conversion and the proof of Theorem 4.1 in Appendix F.
Theorem 4.1 (Bandit to Bandit with Expert Advice). Lel B be any bandit algorithu and (g(T, K) denote its worst- case expected regret. Then, the worst-case expected regret of Algorithm 5 when initialized with B is at most Rg (T,,NN)
Theorem 4.4 (Locally Private EXP4). For every S 1.
Algorithm 6 when run with n
log(N)
3TK 10
By treating each expert as meta-action, Theorem 3.1 and Theorem 4.1 can be used to convert a non-private bandit algorithm B into a private bandit with expert advice algo- rithm A in the following way: given non non-private bandit algorithm B, use Theorem 3.1 to convert it into private bandit algorithm B' Then, use Theorem 4.1 to convert B' into a private bandit with expert advice algorithm A. By post-processing. the corresponding actions played by A are also private. In fact, this conversion also satisfies a stronger notion of privacy where the expert advice is also taken be sensitive information. Theorem 4.2 formalizes this conversion.
and = 1nK (Tg(KT) is E-differentially private and suffers worst-case expected regret at most
/TK (N) log (KT)
O
Due to space constraints, we defer Algorithm 6, which just adds independent Laplace noise to each observed loss, to Appendix F. Note that when N < K, the upper bound in Corollary 4.3 is still superior to that of Theorem 4.4 for all ranges of < The proof of Theorem 4.4 is also deferred to Appendix F.
Theorem 4.2 (Generic Conversion). Let B be any bandit algoritimm. Then, for every T 2 1 and S. 1, there exists an E-differentially private bandit with expert advice algorithm A, such that
Algorithm 6 provides stronger privacy guarantee than what is actually necessary. Indeed, by adding independent Laplace noise to each observed loss, Algorithm 6 actually satisfies e-local differential privacy (see Appendix A for definition). Accordingly, in contrast to Corollary 3.2, the upper bound in Theorem 4.4 vacuous for S VT The following algorithm uses the batching technique from Sec- tion to improve the dependence from Theorem 4.4 while also improving the dependence on N from Corollary 4.3.
(T
(T,,K RRg
+
In particular, by setting [1], there exists an 6- differentially private bandit with expert advice algorithm A such that
Ra(T,K,N) S 2 RB (eT, 1,) 2
Theorem 4.5 (Private, Batched EXP4). For every E, (0, 1]. Algorithm 2, when run with
The proof of Theorem 4.2 is deferred to Appendix F since it closely follows that of Theorem 3.1. Using HTINF for B in Theorem 4.2 gives the following corollary.
(N (NVlg(()) log 1/3 log!/ (33 log 1/3 1/3(NN
n
T1/3
Corollary 4.3 (FTRL Conversion). For every e E [ 11. if is HTINF with a = 2 and a = V6, then Theorem 4.2 guarantees the existence of an E-differentially private
(N Nlog( 1/3 log 2/3 (NT))118
log2/3
T
2// log 1/3 (N))
6

---

Faster Rates for Private Adversarial Bandits
Algorithm 2 Private, Batched EXP4
and N > T. We leave deriving non-vacuous upper bounds for this regime as interesting direction for future work.
1: Input: Action space [ Number of experts N, batch size T, privacy parameters e, 6 > 0, learning rate ', mixing parameter 7 >
5. Barriers to Even Faster Rates for Private Adversarial Bandits
2: Initialize: r 1, w (j) 1 for all j E [N]
3: for t ....., T do
4: Receive expert advice "4......."
v E [([K])
In this work, we provided new algorithms for the private adversarial bandit problem and its expert advice counterpart. In the adversarial bandits setting, we provided a generic conversion of a non-private bandit algorithm into a private bandit algorithm. Instantiating our conversion with exist- ing bandit algorithms resulted in private bandit algorithms whose worst-case expected regret improve upon all exist- ing work in all privacy regimes. In the bandits with expert advice setting, we provide, to the best of our knowledge, the first private adversarial bandit algorithms by modifying EXP4.
5: itt= (r- 1)T + then
6: Set P,( EjENN w-
()(
7:
end if
8:
Set (i) + (1- D1 E.
9:
Draw 4 Qt
10:
Observe loss (() and construct unbiased estimator
((( ((())((11))
(+(1)
11:
if rT then
12:
Define (x() = 1 Ex-(--1)++1 lo. pel and
(.()) = (+(i) + 2Z where
An important direction of future work is answering whether it is possible to achieve an additive separation in and T. We note that this is possible in the stochastic bandit setting (Azize & Basu, 2022) well as the the full-information adversarial online setting (Agarwal & Singh, 2017). To this end, we conclude our paper by discussing some road blocks when attempting to derive such guarantees for the adversarial bandit setting.
3K v N (log(!)
24 Lap
YTE
13: Update 1r+1(j) x- -wr(s) exp(-11,,()
14: Update r t r 1.
15: end if
16: end for
5.1. On the Hardness of Privatizing EXP3
and
First, we comment on the difficulty of privatizing EXP3, In the full-information setting, a standard privacy analysis for exponential weights shows that for every E [T], the per-round privacy loss at time step is at most 21, and for
1/33/ 1/3 2/33 log. 2/ (NTT)
y max
2/3
r - advanced composition yields (e, -)dfifferetti pri- vT
12nK
N Nlog( ( (og(NN)
vacy with expected regret O(v (lo((K))))) /s) (Dwork et al., 2014).
ET
Unfortunately, it is not easy to bound the per-round privacy loss of EXP3 uniformly across time. This is because EXP3 uses
satisfies (e, 8)diifferentially privacy and suffers worst-case expected regret at most
estimators (Robins et al., 1994) (see Algorithm 3). Thus the algorithm needs to know not just the arm Ie but also the probability P. with which it was selected. It is, however, the privacy cost of releasing Pt and indeed we can construct examples where the per-round privacy loss grows with the time horizon T. We provide more formal analysis of this issue in Appendix G.I.
1og2/3( 1/3 (N) N1/6 2 log 1/6 (6(()) log //gg/(((7)) log"
e//3
clear how to account for
/1/2 log( 1/2 log IoT(NT)
The proof of Theorem 4.5 modifies the standard proof of EXP4 to handle the noisy, batched losses. See Appendix for the full proof. Compared to Theorem 4.3 and 4.4, Theorem 4.5 shows that Algorithm 2 enjoys sublinear regret even when N 1 and ε J. Table 2 summarizes the three regimes and the corresponding algorithm that obtains the best regret bound in that regime. Our upper bounds for bandits with expert advice become vacuous when S 1
5.2. Limits of Class of Adversarial Bandit Algorithms
In Section 3, we established upper bounds of O //KT) the expected regret for the private adversarial bandit prob- lem. Unfortunately, by exploiting the ability to pick arbitrary sequences of loss functions, we can show that for large class of bandit algorithms, including EXP3 and its batched
v on
VT
7

---

Faster Rates for Private Adversarial Bandits
Table Summary of the three regimes for bandits with expert advice and the corresponding algorithm that obtains the hest regret hound in that regime.
Regime
Best Alg.
Guarantee
Low-dimension, High Privacy (N S K)
Cor. 4.3
0 VNNT
High-dimension, Low Privacy (N K, )
Thm. 4.4
0 O(VK log N RT)
High-dimension, High Privacy (N 2 K, )
Thm. 4.5
O N NN log(NT) N log(NT)
.3/3
variants, one cannot significantly improve upon this upper bound. Informally, our result holds for any (adaptively) pri- vate bandit algorithm that "quickly" reduces the probability of playing a sub-optimal arm. We provide the formal details below, starting with some intuition.
f1. The first condition simply lower bounds the proba- bility that A plays action 2 by 7 when A is run on fir-- The second condition states that A drops, and subsequently maintains, the probabílity of playing action to y in roughly t rounds. Accordingly, when is small, condition (2) states that A drops the probability of playing action 2 down to 7 relatively quickly. One should really think of y as be- ing O (Ba(f)r)) where (f(Tr) denotes the expected regret of A when run on f1.r. Then, condition (1) triv- ially satisfied, while condition (2) states that A roughly drops and keeps the probability of playing action 2 around O (a(fi.)) by round T, and keeps it there. In other words, after round T, plays action 2 on average p times in 2 ((RAT))) rounds. The latter property is reasonable -
Consider an instance on two arms where arm has loss at each step, while arm 2 has loss at each step. Any algorithm that has regret R must play arm 2 at most O(R) times on this instance. Informally, our lower bound applies to bandit algorithms that drops the probability of playing Rt arm 2 to be about T within about o(T/R) R) steps. We note that EXP3 drops this probability to O x) in (log T) steps. For algorithms of this kind, our lower bound shows that any e-differentially private algorithm (for E < 1) must incur regret O( (TEE) Intuitively, the lower bound follows from the fact that if the loss of arm 2 falls to 0 at step ~ T/R (while arm 1 is unchanged at )) then an E e-differentially private algorithm must pull arm 2 at least times to "notice" this change. Accounting for the accumulated regret in the time takes to pull arm 2 sufficiently many times, and setting parameters appropriately yields the lower bound.
for bandit algorithms given that (2 (x( = for all E [T'] and thus any low-regret bandit al algorithm should not be playing action 2 often. Lemma 5. provides a lower bound on the expected regret of private bandit algorithms that satisfy these two conditions.
Lemma 5.1. Let ε S 1 and A be any s-differentially pri- vate algorithm. If A satisfies conditions (1) and (2) with parameters E [0, 11. < I and 2yr S p S >(T - T), then the worst-case expected regret of A is at least
More formally, fix K 2 and T E N. For 7 [0, E (I....,T} and E [T], define the sets
T
Ey = i1: Σ
14:= = 2] 2T}
TT
1
T
max
4
(
2
c
47
2
>
and
r+ Σ 8=++1
pT
2
1
JeP)
T
EP
Tii 21
16
2
In particular, if A satisfies conditions (1) and (2) with pa-
Consider the sequence of loss functions ,2....,(y fr, such that (2. 1 and (1.T(1) = 1. Our assumptions on the bandit algorithms are with respect to their behavior ......,..... A for which there exists y E [0, 1), т 2 (T - -) such that:
rameters y [0, }... T TE o (VF). and p O(2). then the worst-case expected regret of A is St (VT).
......, ly. In particular, we will consider bandit algorithms T and yT S S
Lemma 5.1 shows that if one wants to design an differentially private algorithm (for = < 1) whose upper bound enjoys an additive separation between T and e, then there cannot exist a E [0. such that satisfies condi- tions (1) and (2) with E o Unfortunately, an implication of Lemma 5.1 is that such an additive separation is not possible for EXP3 and its batched variants. Indeed, batched EXP3 on the loss sequence Ci:r.
(1) P(I IT E Ex)= 2 2 and
(v I (v)) and p S 7T -)). r).
(2) P(T,,...,TT JT E 7 2 2
where IiT are the random variables denoting the actions played by A when run on the sequence of loss functions
8

---

Faster Rates for Private Adversarial Bandits
where (1) 1/2 and (2) 1, has regret least YT + K/Tj, where is the batch size. Assume, towards contradiction that for some setting of parameters, this was o( /T/)). This implies that is (ET), and that k/n s/nis is o( /Te). EXP3 drops the probability of a bad arm to O(r) in log(1/7)//n steps, and the batched version will do so in
Audibert, J.-Y. and Bubeck, S. Minimax policies for ad- versarial and stochastic bandits. In COLT, pp. 217-226, 2009.
Auer, P., Ceee--eeanneeeee BissnBianch,, N., Freund, Y., and Schapire, R. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(11::8 417-77 2002.
<:lo((1 (1//////n/ steps. Thus condition (2) is satisfied with т
being o( (TTT)) and & (ignoring logarithmic factors). This then yields lower bound of w (TT/)) using Lemma 5.1, which contradicts the assumption. Thus the expected regret has to be S2( (T/E) up to logarithmic factors. We
Azize, A. and Basu, D. When privacy meets partial informa- tion: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35: 52199-32210, 2022.
provide the proof of Lemma 5.1 in Appendix G.
Basu, D., Dimitrakakis, C., and Tossou, Differential privacy for multi-armed bandits: What is it and what is its cost? arXiv preprint 1rXiv:1905.12200 2019.
6. Future work
There are several important directions of future work. First, it is important understand whether additive separation between e and 7' is possible under bandit feedback. Note that this is the case in the full-information setting under an oblivious adversary (Asi et al., 2023). Another important direction is improving our upper bounds for private bandits with expert advice. particular, would be interesting to see whether sublinear regret is possible for all N and w( (+).
Bubeck, S., Cesa-Bianchi N., et al. Regret analysis of
stochastic and nonstochastic multi-armed bandit prob- lems. Foundations and Trends in Machine Learning, 5 (1):1-122, 2012.
Cesa-Bil Desa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Cheng, D., Zhou, X., and Ji, B. Follow-the follow-the-perturbeee perturbed-leader for adversarial bandits: Heavy tails, robustness, and pri- vacy.
Impact Statement
Daniely, A. and Helbertal, T. The price of bandit informa- tion in multiclass online classification. In Conference on Learning Theory, pp. 93-104. PMLR, 2013.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Local pri- vacy, data processing inequalities, and statistical minimax rates. arXiv preprint /302.33.00 2013.
References
Dwork, C.
Differential privacy. In International colloquium on automata, languages, and programming, pp- 1-12. Springer, 2006.
Abernethy, J. D., Lee, C., and Tewari, A. Fighting bandits with new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Dif- ferential privacy under continual observation. In Proceed- ings of the forty-second ACM symposium on Theory of computing, pp. 715-724, 2010a.
Agarwal, N. and Singh, K. The price of differential pri- vacy for online learning. In International Conference on Machine Learning, pp. 30-40. PMLR, 2017.
Arora, R., Dekel, O., and Tewari, A. Online bandit learning against an adaptive adversary: from regret to policy regret. arXiv preprint arXiv: 64000 2012.
Dwork, C., Rothblum, G. N., and Vadhan, S. Boosting and differential privacy. In 2010 IEEE 51st Annual Sympo- sium on Foundations of Computer Science, pp. 51-60. IEEE, 2010b.
Asi, H., Feldman, V., Koren, T., and Talwar, K. Private online prediction from experts: Separations and faster rates. In The Thirty Sixth Annual Conference on Learning Theory, pp. 674-699. PMLR, 2023.
Dwork, C., Roth, At, al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3-4):211-407, 2014.
Guha Thakurta, A. and Smith, A. (nearly) optimal algo- rithms for private online learning in full-information and bandit settings. Advances in Neural Information Process- ing Systems, 26, 2013.
Asi, H., Koren, T., Liu, D., and Talwar, K. Private online learning via lazy algorithms. arXiv preprint arXiv:2406.088 036200 2024.

---

Faster Rates for Private Adversarial Bandits
Honda, J., Ito, S., and Tsuchiya, T. Follow-the-perturbedd leader achieves best-of-both-worled for bandit problems. In International Conference on Algorithmic Learning Theory, pp. 726-754. PMLR, 2023.
Ren, W., Zhou, X., Liu, J., and Shroff, N. B. Multi-armed bandits with local differential privacy. arXiv preprint wwXiv:2007.33221 2020.
Robins, J. M., Rotnitzky, A., and Zhao, L. Estimation of regression coefficients when some regressors not always observed. Journal of the American statistical Association, 89(427)8846866 1994.
Hu, B., Huang, Z., and Mehta, N. A. Optimal algorithms for private online learning in a stochastic environment. arXiv preprint arXiv:2102.07929, 2021.
Huang. J., Dai, Y., and Huang. Adaptive best-of-boot oo-both- worlds algorithm for heavy-tailed multi-armed bandits. In international conference machine learning, pp. 9173- 9200. PMLR, 2022.
Sajed, and Sheffet, O. mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pp. 5579-5588. PMLR, 2019.
An optimal private stochastic-
Seldin, Y. and Lugosi, G. lower bound for multi-armed bandits with expert advice. In 13th European Workshop on Reinforcement Learning (EWRL), volume 2, pp. 2016.
Jain, P. and Thakurta, A. G. (near) dimension independent risk bounds for differentially private learning. In Inter- national Conference on Machine Learning, pp. 476-484. PMLR, 2014.
Shariff, R. and Sheffet, O. Differentially private contextual linear bandits. Advances in Neural Information Process- ing Systems, 31, 2018.
Jain, P., Kothari, P., and Thakurta, A. Differentially pri- vate online learning. In Conference Learning Theory, pp. 24-1. JMLR Workshop and Conference Proceedings, 2012.
Tenenbaum, J., Kaplan, H., Mansour, Y., and Stemmer, U. Differentially private multi-armed bandits the shuf- fle model. Advances in Neural Information Processing Systems, 14:24956-24967, 2021.
Kairouz, P., Oh, S., and Viswanath, P. The composition the- orem for differential privacy. In International conference on machine learning, pp. 1376-1385, PMLR, 2015.
Tossou, A. and Dimitrakakis, C. Algorithms for differen- tially private multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Kleinberg, R., Niculescu A., and Sharma, Y. Re- gret bounds for sleeping experts and bandits. Machine learning, 80(2):245-217 272, 2010.
Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and computation, 108(2):212- 261, 1994.
Tossou, A. and Dimitrakakis, C. Achieving privacy in the adversarial multi-armed bandit. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Lu, Y., Xu, Z., and Tewari, A. Bandit algorithms for preci- sion medicine. arXiv preprint arXiv:2 108.0488,,, 2021.
Zheng, K., Cai, T.,, Huang, W., Li, Z., and Wang, L. Lo- cally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33: 12300-12310, 2020.
Mishra, N. and Thakurta, A. (nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pp. 592-5922-99 601, 2015.
Neel, S. and Roth, A. Mitigating bias in adaptive data gath- ering via differential privacy. In International Conference on Machine Learning, pp. 3720-3729. PMLR, 2018
Neu, G. and Bartók, G. Importance weighting without im- portance weights: An efficient algorithm for combinato- rial semi-bandits, Journal of Machine Learning Research, 17(154):1-11, 2016.
Raman, A., Raman, V., Subedi, U., Mehalel, I., and Tewari, A. Multiclass online learnability under bandit feedback. In International Conference on Algorithmic Learning Theory, pp. 997-1012. PMLR, 2024.
10

---

Faster Rates for Private Adversarial Bandits
A. Privacy properties and privacy-preserving mechanisms
Definition A.1 (e-indistinguishaalltt). Let X and Y random variables with support X. Let
In e(Xx))) SEX P(Y E {s))
E
(x = max
be the max divergence. Then X and Y are s-indistinguuishabee if and only if
E.
Definition A.2 ((s, -nninniiissinguihhabiltyy... Let X and Y be random variables with support X. Let
PPX E -))))))))
Do (XII))
max SCX,F(EE)22
In
P(Y E S)
be the 6-approximate max divergence. Then X and Y are (E, -indiiiiiiinuueeaalll if and only if
max (XI 2 (YIIx)) s.
The follow lemma relates the two notions of indistinguishabiltty to differential privacy.
Lemma A.3 (Differential privacy = Indistinguishabiiity (Remark 3.2 in (Dwork et al., 2014))). Let X and y be arbitrary sets. Let be a randomized algorithm such that A X + y. Then, A is e-differentially private if and only if for every pair of neighboring datasets 2ı:n and s' we have that the random variables A(x1a)) and A(z'..) are e-indistinguishable Likewise, A is (e, -idffferrentilll private if and only for every pair of neighboring datasets Fian and d'uno we have that the random variables A(æ1m) and A(21mn) are (E, didissinditinnuushaable
Next, we cover composition.
Lemma A.4 (Basic Composition (Corollary 3.15 in (Dwork et al., 2014))). Let X, V1, .2......y be arbitrary sets and N. Let A1,A2, ....... Ar be a sequence of randomized algorithms where A1 2m - Y1 and A. ........ V)-1, x + Ve for all 2., If for every t E [I] and every V1:1-1 E V1 x 3/2
Vt-11 we have that As A is E--differentially private, then the overall algorithm A X + V1 x Do x ... x Vr, defined as
A(m
T1a), ) (1:m)) ... ,1.))....,.. a.si)):
(31
satisfies ET eT-differential privacy.
Lemma A.5 (Basic Composition (Corollary 3.15 in (Dwork et al., 2014))). Let X, V2......... Dv be arbitrary sets and N. Let AI, ..., Ar be a sequence of randomized algorithms where Ai X" - Y1 and A. VI.... .... Vr-1, X + Ye for all t 2.3..... ...... T. If for every t [T] and every V1a-1 E 31 x Vi2
V--1. we have that As (111:0111.) is E--differeniiall private, then the overall algorithm A A: X + V1 x 322 ... x Yrr, defined as
A(xrn) (AI(EII))
(A (x A2(A1 (2)m),
xlmn)
satisfies ET -ddifferential privacy.
Lemma A.6 (Advanced Composition (Dwork et al., 2010b; Kairouz et al., 2015)), Let 2,J1,.22.... Vr be arbi- trary sets and N. Let A Ar be a sequence of randomized algorithms where Ai x Y1 and ..,,.., A "1,,...;Y--1,8 + for all 2.3,...,TT T. for every t E [T] and every V1--1 E 31 }/2 XV-1. we have
that A(( is e:ddifferemiillly private, then for every ö' > 0, the overall algorithm A nm + V1 x 3/2 ... x Vr. defined as
(r A(rI.)) - (2 (
F1n)) ... 21.1))
satisfies (e', 82 8'f-differential privacy, where
3
T
1
<
c +
log
2
8'
1=1

---

Faster Rates for Private Adversarial Bandits
Post-processing and group privacy will also be useful.
Lemma A.7 (Post Processing (Proposition 2.1 in (Dwork al., 2014))). Let X,Y, Z be arbitrary sets and n E N. Let :: 2 + ) and B: y + Z be randomized algorithms. If A is (s, d)-diffrrettiall private then the composed algorithm A.A: X - 2 is also (e, (..-)yfferenntill) private.
For our lower bounds in Section 5, the notion of group privacy will be useful.
Lemma A.8 (Group Privacy (Theorem 2.2 in (Dwork et al., 2014))), Let X and y be arbitrary sets and let n. E N. Suppose A: x + y is an e-differentially private algorithm. Then, for every pair of datasets Tims zi.n that differ in 1 S k S
positions and every event E S V, we have that
[A(T)))) E FJ S AT (A(()m) E F..
For designing algorithms, the following primitive will be useful.
Definition A.9 (Laplace Mechanism (Definition 3.3 in (Dwork al., 2014))). Let A' be arbitrary set and n E N. Suppose f n + R is query with sensitivity A (i.e for all pairs of datasets Fi:n, Fi.n x that differ in exactly one index, we have that ( (=(.n)) S A). Then, for every e, the mechanism M x -> TR defined as ((1 = f( + Z, where (ap(?) is s-differentially private.
Lastly, make comparisons to local differential privacy, we define it below for the sake of completeness. Definition A.10 (Local differential privacy (Duchi et al., 2013)). Let X' and y be arbitrary sets. A randomized mechanism :: + y is (e, 6)-LDP, if for every x + E X' and any measurable subset Y C V/ we have that
(M) E YJ S (TTP(M(r)) EV]
When 8 0, we say that M e local differentially private.
B. Helper Lemmas
Lemma B.1 (Hazard Rate of Laplace distribution). Let 'D denote the Laplace distribution Lap(0, A), f and F denote its probability and cumulative density functions respectively. Define
f(z)
hD(2) 1- F())
to be the hazard rate function of Lap(O, X). Then
supho(2) S
sER
Moreover, hz(2) is non-decreasing in
Proof. Recall that for À >> 0, have
x exp( x
f(z) = 21
and
1/2 )
if i if 0
F(2) =
1 exp(
Fix RR. If 0, then
f(x)
1 exp +
2x
v
1- F(x)
- exp }
Otherwise, note that when æ 2 0, we have
f(x)
exp } 1 exp
1- F(x)
X
This shows that suprer hp(x)= < 3. To see that hp is non londderreasing, note that when S 0, we have that hn(z)) 2 ex) is increasing in and when 2 0, (x)) is constant.
1- [x)
12

---

Faster Rates for Private Adversarial Bandits
Lemma B.2 (Truncated Non-negativity of Noisy Losses). Let Z Lap(A) and & |0, 11. Then, for any M 0, we have
that
B + +011++1 2H20
Proof. Let M 2 0 and & [0, 1]. Then, we can write
E [[Z + E) 2 + > MH = EE + + EE] MH]
Since f 2 0, it suffices to show that F. /1 Z + 8 M) 0. To that end, note that
E 2 2 + > MH E [ > M - {}] + B|Z < -
Suppose that M - 2 0. Then, since Z is symmetric random variable (around the origin), [ < -M -0}
E [Z M E. Since M - f < M
have that
IE 121 + > = E M - M + 0.
Finally, suppose that M - < Then,
E 2211 M
2>
0}}
Using again the fact that Z is symmetric. we have that
E ZI(0
Z> - -
Finally, since L - -MM- S M + L, we have that
ZT > My E [Z]
03]
M M +0) 0, [ZT < 7< - -
completing the proof.
Lemma B.3 (Norms of Laplace Vectors (Fact C. in (Agarwal & Singh, 2017))). 71..... ZT (Tap(A)) then
P(3 e [T] 11 Z 10x3 log)) < T
C. Proof of Lemmas 3.3 and 3.4
C.1. Proof of Lemma 3.3
Note that the sequence of actions played by Algorithm are completely determined by /i...., , [ in a dataseet-independent way. Thus, by post-processing suffices to show that the actions JI.... [[ output in a e-differentially private manner. Note that the distribution over the action 41 is independent of the dataset fI...., ly. Thus, it suffices to only prove privacy with respect to the actions 12. I2...., [ Consider the sequence of mechanisms M2,..., M where
M2 : [K] luTT + IR x [K] is defined as
M2(61, (ITT) (fr(1) + 71, (11)) Z)))
for 71 ~ -ap( and Mj ([K) x Ry x [K] l1T + R x [K] is defined as
i- Mj((in,ra) (1) (iT) = (, (1, 1) + 2 ((i., (.). (iz (is-1,,--1((5)) Z 2z-1)))
13

---

Faster Rates for Private Adversarial Bandits
for 2 Lap(22 --), Observe that Algorithm I is precisely the mechanism M : f1:r - ([K) R)" that adaptively
composes M2. ..... M We will now show that M is e-differentially private by showing that M (f1:;) and ((ea.) are e-indistinguishable for arbitrary neighboring datasets f1rT and fi.--
Consider (wo datasets f1.T and fir that differ in exactly one position. Let t' E [2]] be the index where the two datasets differ. je E (1..... [ be the batch in where the lies. That is, jet E fi...... [ such that t' E (()- J'T}.
Fix outcomes (f,; r2) r=) -2 E ([K) R.) L and
[ E
( [k].
For all S J'. we have that the random variables indistinguishable. We now show that the random variables ((i,, ) dys (IT) and My+i((is, r.) ) iy (.)) are e-indisinguishaale.
T' 2--
(1r) and Mj ro) 1,1, (TT)) are 0-
Recall that
(1)ni((innr))a By, LIT) = (L) (cr())) Zz,, B((,, (1r,
Note that the query l (ip) has sensitivity at most 7. Indeed, we have that
fT
= 1 -,1))))))))(((((66(0-( (.iy)
( =
Σ
Thus, by Definition A.9 and post- post-processing, we have that ((), - (1T) and My+1 4 ((dg ry ) 1 (1T)
are s-indisinguuisablee for all inputs.
To complete the proof, we now show that for all j > j' + 1. M2 T, 1 -y)
(rr and (( 1.)a 1 ( are
o-indistinguishable Fix some j >> j' + 1. Recall, that
1o) (IT) = (eg-1(i)- + Zz-1, B((ss, ( + Z Zy-1)))
Since for every s E { - 1)r + .j} we have that la = l. we get that ( + Zi-1 and (1g-1) + Z are same in distribution. The same can be said about B((i,, and ((i,,r,)) o (iz-1, (iz-1, (()))))) + Zy-1)). Accordingly, M, ((is, r.) are O-indistinguishable for all inputs. Since M is the composition of M2,..., M [= by basic composition, we have that M (11T) and M(' (f):T) are e-mdistinguishable, and therefore M is e-differentially private. This completes the proof.
(1 ((s., 1. 1, (IT) and ((.. i (
ro B((i,,
+ Z)-1))
C.2. Proof of Lemma 3.4
Let Ei...., by be any sequence of loss functions. Note that the bandit algorithm B is evaluated on the loss sequence & + ZI..... & [ + Z | where (i) = " Σズ (i) and Z, ~ Lap( Let 4I,..., be the random
variables denoting the predictions of B as indicated in Line 4 in Algorithm 1. By definition of Rg ((T) K, 1) T
we get that
+ Σ
(77)
T
1
E
(L,)
inf KE[K]
4,(0)
RS
K, TE
j=1
By definition of é,, we have that
E
inf
Σ
e.(i) < TRB (7) K,
1
K
TE
j=1
1)
j=1
s=
+)1+1
Next, note that by construction, we have that for every j E {l..... T T5. Thus, we can write
[1) and s e {0i - 1)7 + 1.... 1. we have that
14

---

Faster Rates for Private Adversarial Bandits
$
T rRB
{
E
Σ
inf kE(K]
Σ
Σ
(,(1)
(-1))+1
a= (j-1)r+1
which further gives
+
+
E
(c(
inf KE[K]
Σ
( S
RRg
.K K. -
TE
Finally, the expected regret for rounds
[ ....., T can be bounded above by т. Thus, overall, have that
E
inf KE
Σ 4(1 TBB
(1=
K,
1 7E +
TRg
T
1 _112 TE
+
Noting that f,,..., fr was arbitrary completes the proof.
D. Proof of Corollary 3.2
The following Theorem from (Huang al., 2022) will be useful.
Theorem D.1 (Theorem 4.1 (Huang et al., 2022)). Let fi,...,eT ET any sequence of random loss functions that satisfy the following two properties: (1) for every E [K] and E [T',, the random variable Le(i) truncated non-negative and (2) for every E [K] and t [T), the random variable Ea(i) is heavy-tailed with parameters
(1, and 0. Then, the expected regret of HTINE (Algorithm (Huang et al., 2022)) when run on .,....,.y Er at most 30g K1 à (T + 1)a.
We now make precise the definition of truncated non-negativity and heavy-tails.
Definition D.2 (Truncated Non-negativity). random variable X is truncated non-negative for every M Z 0, we have that E [X- [[[X M}] 2 0.
In Appendix B, we prove that random losses of the form ((1) = E(t) + Zj are truncated non-negative when E(i) E [o, 1] and 7, Tap(A)-
Definition D.3 ((a; or- Heavy- loss). A random loss ?(1) is (a, σ heavv tailed if E [(()]]]] 00
In addition, if {(1) ((i) + Ze. where {(i) [0, 1] and Z Lap(A), then E(i) is (2, /2 4X2) --havy tailed. We now ready to prove Corollary 3.2.
Proof. (of Corollary 3.2) In order
Theorem 3.1, need upper bound RHTINI (T, X). Let l1, (,.... ey be any sequence of loss functions such that l, [K] [0, 1] and let fi..... Er be such that (i) (i( + Z.(i) where (1) ~ Lap(A). Then, since for every t E [T] and E [K], we have that ()) is truncated non-negative and (2, /2 + 4X heavy tailed, Theorem D.1 implies that
RUTINE CATTIN(T,K,, (T,KA)) S 30 30 (X (2))
Finally, to get Corollary 3.2, just upper bound
2 RHTINE (ET, 1,K,1)
2 - 208 + --,
VTK 2
Ve
E
for 2 +.
15

---

Faster Rates for Private Adversarial Bandits
Algorithm 3 EXP3 with Mixing
1: Input: Action space [K], learning rate mixing parameter >>
2: Initialize: W1 (i) = for all E [
3: for ....., T do
4: Set (i( = (1 - 7)
() LIERN (i(() + K
5: Draw It
6: Observe loss (T) and construct unbiased estimator (1))) (.
P(())
Update (1) & we(i) exp(-nfc(t) for all i e [K]
8:
end for
E. Additional Upper Bounds for Private Adversarial Bandits
In this section, we instantiate Theorem 3.1 with other (non-prion noon-private) bandit algorithms to obtain two other regret upper bounds.
E.1. EXP3 Conversion
Corollary E.1 follows by letting B in Theorem 3.1 be the classical EXP3 algorithm (Auer et al., 2002). See Appendix D for pseudocode EXP3.
Corollary E.1 (EXP3 Conversion). For every < 1, if is EXP3 run with learning rate
log(K)
=
KT (ogg(TT)
and mixing parameter 4nK log(eKTT). then Algorithm when run with B and [ is e-differentially private and suffers worst-case expected regret at most
+ 36 TK log K)
log KT)
4
VE
Algorithm 3 provides the pseudocode for the version of EXP3 that consider.
The following lemma about EXP3 will be useful when proving Corollary E.1.
Lemma F.2 ((Auer al., 2002; Bubeck al., 2012)). For any sequence of loss functions fI...., Er, where l, [K] R. if n 0 is such that y max (t) S 1 for all [T], then EXP3 when run on fI...., ey outputs distributions
Pir I([K))² such that
T Σ Σ P(OG)))
log(K) K
T
inf
Le(1)
2/T
4())
1
where &g is the unbiased estimate of the true loss & that EXP3 computes in Line 6 of Algorithm 3 and the expectation is taken only with respect to the randomness of EXP3.
Proof. (of Corollary 1) In order to use Theorem 3.1, we first need to bound REXPS (exxrs(,,5 K, A). Let .1,...,ly be any
sequence of loss functions such that & [K] + [o. 1] and let f,...., &y be such that (i) (() + Zz where
(1) ~ (A). Let be the event that there exists a E [T] such that max [2) > 10X² log KT. Then, Lemma
B.3 shows that IP [ < 7. Moreover, note that E (E) = 0 for all E [K] and t E [T]. Let A be the random variable denoting the internal randomness of EXP3. We need to bound
REXPa (T,,sTT,, (T, K,
E
Σ e (EXP3((A))
inf Σ (iii) iE[R] t=1
A.Z
16

---

Faster Rates for Private Adversarial Bandits
We write REXP3 (T, K,X) A)
E 1-2
Σ
inf (EEP3((A)))
Σ (ii E
P(E)
E
Σ ((EPP((L))
- inf
Σ
((i)
E P(E))
KE[K]
1,2
KE[K]
Since 1. ((EPP((AA) - inf Eis (e(i)
P.
S T, we have that
REXPS (T, K2
l (EXP3(H)))
inf EE[K]
Σ
((( Fe
+1
A,ZI:
We now want to use Lemma E.2 to bound A. E 4(EXP((H.) inf E 4(11 E Recall, that EXP3 is actually running on the noisy losses f,,.... LT. So, in order to Lemma E.2, we need to pick 7, 0 such that max (1) S 1, where we use l, to denote the unbiased estimate that EXP3 constructs of the true (noisy) loss &, In particular, recall that EXP3 constructs (i) {())= where we used (i denote the measure that EXP3 uses select its action 4e on round E [2]. Moreover, given a mixing parameter y > 0, we have that P((i) 2 k- Thus, we need to pick y and 7) such that
Pc(
K
max <E(K]
(1( 5
max [z((1] S 1.
iE [K]
Conditioned on event ES, we have that [a Then, conditioned on the event E and the random variables Zi,..., Zr, we can use Lemma E.2 get that
[z) Σ 4A logo(( KT). Thus, it suffices to pick y = 4nAK log (TT).
T
K
T Σ
log K)
T
K
E
P((0),(())
E ZIT
Σ inf KE[K]
2111 + 2
+1
Taking an outer expectation, then gives that
T
K
T (.11 E"
log(K)
T
K
E
ΣΣ
P(00(
E
<
inf K
E
+ 2TT +
+ 17
E ZI.T
&(1)
E
A.Z..
ZLTT
7
Since (i),, conditioned on ES, is zero-mean and Zz(1) conditioned on the history H. is independent of Pr()), we have that
log(As (K)
K
ΣΣ
P.(1)( E
< inf KE[K]
Σ
(()
2
n
E Zier
2(1) E
A,ZIe
"
which further gives
log(K)
T
K
2xT +
+ 17
ΣΣ
Σ
E
+1.
Zier
It just remains to bound Ezyr ΣrTER
ΣK
(((1)2 Fs]
Note that we can write
17

---

Faster Rates for Private Adversarial Bandits
K
E 7I.T
(1)
E
S nR
E
max (i) E
ZI.T
ie KE[K]
i=1
S k
E
(() + Zx(1))² E
Z1.r
S 2 K
E
(1 + max (x)))) F K
ZuTT
T
< 2 Σ
(1 + 10X log KT)
2m1
2n (1 + 10X log" KT).
Plugging this bound back in gives that
log( K)
REXPS (T)),A) S 2TT
+ 2n/KK 10X log" KT)) 1.
n
Recall that we picked y = 4mjAK log(KT), Substituting this selection gives
(T, K,A) & SnAKTlog(KT) + log(K)
+ 21yTK(1 + 10A log2 KT) + 1.
We then write
(og(K)
REXPS (T, K,
+ 22,TK(1 (X2 log² KT) + 1.
n
Picking 77
log K)
log" KT) get overall that
max () 11
REXPs (T, s 2 log) 10 max log² KT) 1.
Finally, Corollary E.1 follows by the fact that
VTK log K) log (og((T) REXPS (,,,1) + < 36
+
VE
This completes the proof.
E.2. FTPL Conversion
Corollary E.3 follows by using www.-tthe-eetuuue----eee (FTPL) with Geometric Resampling (Neu & Bartók, 2016). The pseudocode for FTPL with Geometric Resampling is provided in Algorithm 4.
Corollary E.3 (FTPL Conversion). For every [ 1}, if B FTPL with perturbation distribution Lap ( and
Geometric Resampling threshold M (see Algorithm 4), where M = VeKT and
log(K)
min
(<KT + KT log (EKT)) M(1 llg(sTT)
18

---

Faster Rates for Private Adversarial Bandits
Algorithm 4 Bandit FTPL with Geometric Resampling (Neu & Bartók, 2016)
1: Input: M, 7)
2: Initialize: (u( for all e [K]
3: 1,..., do
4: Sample Zı.... Zk ii.d. from Lap(O, 1
5: Select action 1, E arg min (Ln-1(1) 2.)
6: Observe loss (Ta)
7: Let M, = 0.
8: f = 1,
M do
9:
Sample ...... x i.i.d. from Lap(O. #))
E arg ( + Z then
11: Set M, i.
12:
break
13:
end if
14:
end for
15: Define -()) ii.
16:
+ (().. Update L, - La-++
17:
end for
Algorithm when run with B and T [ is e-differentially private and suffers worse-case expected regret most
KT log K) log(KT) 2 E
Ve
We now prove Corollary E.3. Lemma E.4 first bounds R8(T, K, when B is Algorithm 4.
Lemma E.4. Let B denote Algorithm 4. Then, if M = VT and
log(K)
7) min (V
(KT' + 10KTX2 (og((K()) M(1 + 41log(())
we have that
(T X) & LLV/KTlog(K' log( + 10
Proof. Let , be any sequence of loss functions such that & [K] + [0. 1] and let E,,..., & be such that
(.(1)= = 4() + Gi) where Ge(i) ~ Lap(A). Let E be the event that there exists t E [T] such that max (G)2 > 10X² log" KT. Then, Lemma B.3 shows that P [E] < $. Moreover, note that E. (i) E 0 for all E [K] and E [T].
We need to bound
T
RT K, =
E B.G
(((((H)) - inf Σ
4(i)
(E[K]
t=1
We can write Rg K, A) as
T
Σ
(B(H))
inf iE[K]
Σ (1) E P(E) +
Σ ((((H)
inf
Σ
(i
E" P(E))
B.GHT
B.GHT
*E(K]
Since Es.Gur
((((((((
infze]K] Σ (aii)
E
S. we have that
19

---

Faster Rates for Private Adversarial Bandits
T Σ
Rs(T,K,A) E 8
Σ
((B(H)) inf xE(R] t=1
(e(i)
E
+1
x 8,G
((B(HL)
E
inf KE(K] t=1
Σ
(0)++ +1
Let i be the arm that minimizes Σ 4(t). Moreover, let & denote the unbiased estimate that Algorithm 4 constructs of the true (noisy) loss & when run on the noisy losses f1,...,fy Ey. We start with the following regret decomposition for FTPL from Lemma 3/honda202ffollow.
E B,G
(L1 E
E B.GHT
Σ
200 E
2
max [E[K]
+
E B,G
K ΣΣ
(()(P.))) Pi+1(1) E
2 z~Lap(
where we define P.(i) IP 11 = ile
The first term on the right can be bounded
6log(K) K))
2
E
max Zi|
Z~Lap(
[E[K]]
77
As for the second term, Lemma from (Cheng et al.) gives that
exp(-nllddli)+
Pet1(i) exp(mllddli))
P((
Accordingly, we have that
(((1) (xp(lll)(((()))l 5 P(() P(1(1) P((1(1 expl-n|l(:la)).
Thus, we can bound
For >> such that 7/l 2ll I 1, we have that
exp(n1121111 s 2n114t1 + 1.
Since ||ē|11 [M((((4)+ M(1 lo)lo)()), it suffices to pick v S M(++slog(21) For this choice of rj. we have that
(()(P(()) P(+1(1) 22P(0((0))))) < 2P(()((()))))))))
Plugging this in gives
T
K
T
K
E
ΣΣ
(())(P)))))))))))))))))))))))))) - Po+1(0))
E
< 2n E B.GLT
ΣΣ P((())) E
B.GLT
and therefore
20

---

Faster Rates for Private Adversarial Bandits
E B
Σ
-
6log(K)
2n
E B,G
ΣΣ
K
POLO!)
E
7
To bound the second term on the right hand side, we have that
T K De
T K
E
ΣΣ
RO(())
E B.G
ΣΣ
P01G0))
-10M)) E
B,G
t=1
2 2 E 8,G
Σ Σ
P1000(1)) = (P)()))
E"
T
K
= 2 E 8,0
Σ E (E(0))
E
(i(
i=1
K
= E G1T
E (4(1) +G(1))²
i=1
2 E GIT
+ G.(1))) E
[==
2KT + 20KTX log (KT),
where the first inequality follows from Lemma 12 in (Cheng et al.). Thus,
Σ
E 5 6log(K) + 4nKT + 40nKTX> 1og2 (KT).
B.G
Next, note that
Σ ((TT. (((t))
E
E B.G
Σ
(T)) - ((+) E
Σ (T.)) - -a(T.)
E
B.GH
B,GHT
T
Σ ((())) Ee((tt F.c
B.GLT
Thus, suffices to upper bound the latter two terms. Starting with the third term, we have that
21

---

Faster Rates for Private Adversarial Bandits
T
T (L)) -e(ttt Ee
E
Σ
-1(1))
E
=
E
B,G
B,G
(((0)) - -1(()))))))))) -
Be((t) L"
E
B,G
(1)1() PA(1T) (P(())) E
E
8,G
E
(G(()++ + -1.0))((1--P0000 E
8.G
E
-1 P(( (M())) E
B,G
< 0,
where the second equality follows by Lemma 4 from (Neu & Bartók, 2016). Now, for the second term, by Lemma 5 from (Neu & Bartók, 2016) we have that
KT
Σ
((Li)) - (o(le)
E"
S
B.G
cM
t=1
Combining all our bounds gives
Glog(K)
KT
E
((TT
- (((")
E
<
+ +
+ 10KTX (KT)) +
B.GHT
n
cM
For M VKT and min
(KT+10KTX (KT)) 4og(1+))))g()) J we get that
log(K]
E
- -(((it) E
< 10AV KT Kooog(gooo log((K)))) 10.
B.GHT
Since T Etn ((T)) - -(()))(((()))))) FP0
ΣL l le(it) FO. have that
EES.GUT
10 Rs K, < 10Xv K) log (KT 10v KT +1,
which completes the proof.
Equipped with Lemma E.4, we are now ready to prove Corollary E.3.
Proof. (of Corollary E.3) Let B be Algorithm 4 with the hyperparameters selected according to Lemma E.4. Then, we know
that
RT K,A) & 11A HIXVKTlogh log)(T)T)) + 10 KT.
By Theorem 3.1, we can convert into e-differentially private algorithm AA such that
22

---

Faster Rates for Private Adversarial Bandits
Algorithm 5 Bandit Bandit with Expert Advice
1: Input: Bandit algorithm B, Number of experts N, Action space [K]
2: Initialize: with action space [M
3: for 1,rt=,..... T do
4: Receive expert predictions u P p E =I([K])
5: Sample 1 /M for all j E [N]
6: Define ke()) ( for all E [N]
7: Receive expert Jr E [M] from B
8: Play action I E [K] and observe loss e (T,'²)
9: Pass (J)) to
end for
(A - - RB(ET, K, +
22
<
v KET (K) log(KT) 1111100KKTT
KT
8
32v
KT log( K) log( KT)
2
Ve
E
completing the proof.
F. Proofs for Bandits with Expert Advice
The following guarantee about Multiplicative Weights (MW) will be useful when proving utility guarantees. Lemma F.1
& Lugosi, 2006; Littlestone & Warmuth, 1994)). For any sequence of loss functions L1, Lr, where & [N] - R. if > 0 is such that maxje[N] (e( S for all t E [T], then MW when run on f,,..., ey outputs distribations Pv. E I([N])² such that
I ΣΣ P(O))) inf
T Σ JE(N]
((() + log(NN
T N
ΣV P.ODA
=
t=
F.1. Proof of Theorem 4.1
Proof. (of Theorem 4.1) Consider loss sequence l,,..., lT and sequence of expert predictions w4A Let j e arg mi Et= Σ (4) (1) denote an optimal expert in hindsight. By definition of the bandit algorithm B. pointwise for every 11:N we have that
T
T <
E
Σ
(((Ji)
Σ5
(07) + Rs),,N).
1=1
By definition of é, we then have that
E
(
<
Σ (( + (T.
Taking outer expectation with respect to the randomness of 7 11:N 1:2' we have,
E
=
(1) (4)
23

---

RA. RA, S rRg( T 1 .N, + Faster Rates for Private Adversarial Bandits
Algorithm 6 Local-DP EXP4
1: Input: Action space [ Number of experts N, privacy parameters E > 0, 17, > 0
2: Initialize: wi (j) = 1 for all j j [N]
3: for tort11... 1,...... T do
4: Receive expert advice p M M
5: Set Pr(j) = ΣSE[N] (e(
(e(1)
6: Set Q+(2)= -1 E Ex P()0((0 k.
7: Predict ~ Qt
8:
Observe loss (Le) and define ((()) (e(t) + Zi where 2; Lap(O, !)
Construct unbiased estimator (((i)= (1111==11)
9:
Qx(1)
10: Define E(() = uo. E, for all [N]
11: Update wx+1(5) (5) < wi(s) exp( (n)
12:
end for
which completes the proof.
F22. Proof of Theorem 4.2
Let B be any bandit algorithm. Then, for every 7 2 1. We need to show that there exists a e-differentiall private bandit with expert advice algorithm A, such that
T ET
Proof. (of Utility in Theorem 4.2). Fix S and
1. By Theorem 3.1, can convert B into e-differentially private
bandit algorithm B, such that
Rg, (T, S TRo( {T K, 1 +
ET
Then, using Theorem 4.1, we can convert B, into bandit with expert advice algorithm A, such that
T RA, (T,K,N) Rs, (T₁N) S riol r N, ) ET
+T,
completing the proof.
Proof. (of Privacy in Theorem 4.2) Consider the same algorithm as in the proof of the utility guarantee. That is, let Ar be the result of using Theorem convert B to B, and Theorem 4.1 convert B, A,. By Theorem 3.1, know that B, e-differentially private. suffices show that Algorithm 5, when given end, let fi.T and Grrr be two sequences that differ at exactly timepoint. Let 1:N be any sequence of expert advice and fix I; ~ μ1 for all & E [T] and i E [N]. Observe that Algorithm 5 instantiates B, on the action space [N] and simulates B, on the sequence of losses ((i) = (T)).. Let l.. and l denote the two sequences of losses that Algorithm 5 simulates B, on when run on L.T and f. respectively. Note that f1.T and éi.r differ at exactly one timepoint. Thus, B, outputs actions J1..... Jr in an e-differentially private manner. Finally, by post-processing it follows that the sequence of actions T. output by Algorithm 5 is also e-differentially private.
input is also e-differentially private. To that
E.3. Proof of Theorem 4.4
Proof. (of Utility in Theorem 4.4) Fix e 5 1. L Let E,, be any sequence of loss functions and ui:: be
any sequence of advice vectors. Let E' be the event that there exists E [T] such that max |2i12 > 10X log 2 (KT).. Then, Lemma B.3 shows that P [E] < 1. Moreover, note that E [Zj] E*] = 0 for all i E [K] and t E [T]. Let .A be the random variable denoting the internal randomness of Algorithm when sampling actions J, We need to bound
24

---

Faster Rates for Private Adversarial Bandits
T
R(T, K,N)= =
E A.ZI:T
Σ
(TT)))
inf JE[M] tml
Σ
bx
We can write R(T, N) as
T
T Σ
E
Σ
inf
1 Ee
E
P(E)
+
E
Σ 4(I)
inf
Σ
m
&
E
P(E
A.71.
JE[N]
A.ZI.T
JEIM
==1
Since Z.
Et (c(t) inf Ets uut le E
I T, have that
T
T kd Ee be
R(T,K,N) A,Zı.T
Σ
(((.))
inf JE[N]
Σ
+1.
Accordingly, for the remainder of the proof, we will assume that event E has occurred, which further implies that max{e(T] [aX Ziil S 4ATo
Algorithm runs Multiplicative Weights using the noisy losses ",,...,
2y. For = 41 A log( KT), we have that
(L) (L,(T) Z
Q1(11) < n
7) max max ()) = 7) max max -M² & = 1J max max [E[T] JE[N]
(4Alog(KT)) s
EE JE[N
(E[T] JE[N]
Accordingly, for this choice of 7, Lemma F.1 implies that
log(N)
N
ΣΣ
POOO)s inf
Σ
400+
+
n Σ Σ POO00)
JEIN]
7
-I
Taking expectation of both sides, we have that
T N
T E
log(N)
T N
POOA
E
inf JE
E
Σ
+
+ E A.ZI.T
ΣΣ
P.G))
E
A,Z
2
We now analyze each of the three terms with expectations separately. First,
T N
T
N
K P((j)
E
ΣΣ
P.O)
E" = E
2004
E
A.ZI.T
A.ZI.
1=
1=1
T
N Σ ())))
E
ΣΣ
2,0)) E
A.Z..
T
K
Qc(i) - x
E A.ZI
(,(1)) E
1 1-7
T
ΣΣ Σ (0(1) E
Y
2 E
(1-7) A.ZI.T
K 7) A.21.T
1=1
25

---

Faster Rates for Private Adversarial Bandits
Next,
POOEEE
E
P.OM -
A.Z1.
A.Z1.T
(=1/=1
$ E
ΣΣ P(O Σ
(Z) E
A.Z1-
E
ΣΣ
Σ
P.
200 E
A.Z.I
i=1
Q1(1) R
ΣΣ
2,11) E²
E
A.Z1-
1-7
2 (1 A,Z
20(1)(111))
E
Finally,
inf JE(N] ZE.T
Σ
L0 E
inf E
Σ E M E
JEIN] ZETT
inf E
Σ E/ m
E
JE Z1.7
T
inf
le
JE[N]
where the second equality follows by the unbiasedness of & and the last by the fact that Zi is zero-mean (conditioned on ES). Putting all the bounds together, we get that
1
E A,7
ΣΣ
E
(1
7
i=
is at most
inf JEIN
Σ
T
4
m
+
(Ng
7
E
(i) E
+ (1 7) A.ZIT
20000 E
"
K(1 7)
Z11r
Multiplying both sides by (1 - 7), we have that EA,Zi.
Eie (1) F.c is most
(1 7) inf JE[N]
ls mi + (1 7) log(N)
7
20(0) E
+ 1
ΣΣ 2.00((0))) E
K
21.7
A.ZI.
which implies that
K ΣΣ 2000( E
log(N)
T K
< inf [E
4 p
+ TTT +1
Σ Σ Q,())
E
A.Z.T
A.ZL.
Using the fact that & is an unbiased estimator of é gives that
26

---

Faster Rates for Private Adversarial Bandits
[og(N)
T K
ΣΣ
2000 E
inf JE[M]
Σ
pl +
7T + 17
E Z1:7
ΣΣ
211
E
A,Z
Since 7 is zero-mean (conditioned on F39 and independent of Qc)),, we get that,
K
log(N) + +
E
Q(0)((0)
E
inf JE
E
Σ
E
A.ZI.T
Z1:7
It suffices to bound the expectation on the right-hand side. To that end, observe that
K
Σ
(1)
E
E 7A.TT
Σ
(e(()) + Z;)² E
ZET
2 2 E Z1.
Σ Σ (4(1)2 ( +2))) E
T
K
2 2 E
M
(1 (Z))²) F
Z1.T
1=1
S 2K + 10X2 log KT)
Thus, overall we have that
K
T
log(N)
E
E
< inf JE(N]
Σ
la
m
+ 7T + 2n/T((1 10X2log² KT).
A.Z.:T
Plugging in our choice of y = 4n (lgg(o)))
T
log(N)
E
ΣΣ Q.000()))))
E
s inf jEIM]
le
md +
4ogTTlog((T)) (1 + 10X2 KT).
A,Zı.
17
t=1
which for 2 gives
T K
T
log(N) + +3kKT( + 10X² log² KT).
E
ΣΣ
2000( E
< inf
Σ
le
m +
A.Z..
JE[M
"
Picking 7)
(N) we have
3TK(1+10A> log KT)
B
ΣΣ 2000).)))
E
< inf
Σ
4
md + 16 (N)
A.Z.
JE[N]
t=1
For our choice A =
we get
K ΣΣ
T
T
16 TK / log( N) log (T))
E
E
<
inf JENN tm1
Σ
l m1 +
A.Zi.T
27

---

Faster Rates for Private Adversarial Bandits
Finally, noting that
T ΣΣ Q.(G)( 1=
T Σ
R(T, KJT,K,N) <
F
inf JE(N t=1
1 4++1
A,Z
completes the proof.
The proof of privacy in Theorem 4.4 is identical to the proof of Lemma 3.3 after taking batch size 7 = 1, so we omit the details here.
F.4. Proof of Theorem 4.5
Proof. (of Utility in Theorem 4.5) Fix e, E (0, 1] and batch size Let À = 3K / log( Let 21....,,7 er be any sequence
of loss functions and L:N be any sequence of advice vectors. Let be the event that there exists a E (1...., [ such that maXje[N] 1/122 2 10A (N 1 Then, Lemma B.3 shows that IP [b]] S f. Moreover, note that E | b9 = O for all [N] and []. Let A be the random variable denoting the internal randomness of Algorithm when sampling actions J. We need to bound
R(T, K)N)
E (aI
inf GE(M]
Σ
m bx
We write R(T, K, N)
T
T Σ JE[N]
E
Σ
((T))
H le E
P(E) +
E
Σ (TT)
inf
Σ
m
4
E
P(E))
A.Z1.
A.Zr.
JEIM
1=1
Since EA,Z.T
Ete Ce(te) inf Ete u4 le
< T, we have that
R(T,K,N)
E A.ZLIT
Σ 4(T)) inf
Σ p lg
E
(1)
JEIN
Accordingly, for the remainder of the proof, will assume that event E has occurred, which further implies that max,el[?] [ max]e[N] |2z| < 4X [F]).
Algorithm 2 runs Multiplicative Weights using the noisy, batched losses C,...., For y 2 12nK N log( log(NT) have that
we
12K N Nlog (+) log(NT)
max max ((,()) < max max ((((())) + 22) < max nax re[ [
2 S
S
rell T JE[N
rel JE[M
ETY
12n /N log( (NT)
Accordingly, for any choice
Lemma F.1 implies that
or
F ΣΣ PAO),)))) inf
F tn ME P.OE0))
log(N)
Σ
JE[N]
17
Taking expectation of both sides, we have that
28

---

Faster Rates for Private Adversarial Bandits
F. LERONEE
(N) 17
E
inf J JE[M] Z
()
E
+
+
IE
P.OCO E
1.Z
A.ZII
r=
Using the fact that Z zero-mean and conditionally independent of P, given the history of the game up to and including time point (r - 1)r, we have that
log(N)
ΣΣ P.OEEEE E
S
inf E M 21r
E
+
+
E A.ZI:T
ΣΣ P.OOOUE
A,Z
7
We now analyze each of the three terms with expectations separately. First,
N
:
N
K
E
Σ Σ
P.O0
E
E
Σ
Σ
Σ
P)) Σ (0)(())) E
A.Zu.
T A.Z
==
r=
(r- 1]r-111-11
1
E
Σ
Σ P.(O)
(o(i) E
T A,Z
+
1
Qi(1) - 1-7
(4(1) E
T A.ZIT
+ K Σ (1)
T (1 (1-7)
Σ
E
7(1 7) A.ZITT
T
Next,
E N
N
E
E
= E
Σ
(0)0)+)2) E
A.71.
A.Zu.
r=1 1
N Σ
(000(,0)((2Z)))))) E
A.Zr.
T
Σ P.O)
10x 1og
E
A.Zı.
I
T
T
Σ
E POOO))
E
+ 10
X2
log
(N
A.Zr.
T
To bound the first of the two terms above, note that:
29

---

Faster Rates for Private Adversarial Bandits
H
F
E
ΣΣ
P.00
E
S
E A.Z..
Σ P.(
Σ
E
E.
A.Z1.T
==
==(r-1)++1
1
S
E
P.O) 72
ls 11a
F.
A.ZI:T
s=(r-1)++1
S E A.Z.:T
Σ
N
P0O)=
Σ
(es m2.
2
F.
Ø=1
1=(r-1)++1
+ ΣΣ P.O)
1 E $
N
W Σ
Fr
7 AA.7..
m=
(r-+)r++1
L
1 E
Σ
Σ
77
N Σ
P.U)
Σ 2020
K
E
T A.71T
(r 11r+1==1
L
K
1 E
ΣE (r-1)))++1 i=1
Σ
Σ
Σ P.(O)((()))
( E
T A,Z1.
+ ΣΣ i=1
1 E A.Zu.
(Q((1-
K
(1) E
1-7 7
K Σ (o(1)
1 7(1 7) A.ZI.T
E
Σ
E
t=1 i=1
Finally,
inf E JE[N] ZUT
Σ 4.0) r=1
E
= = inf E JEIN 2
Σ
Σ
F.c
r=1 == (r- 1r++1
+ Σ
inf E JEIN Z
E
E
inf JELN
E 1
t=1
where the last equality follows by the unbiasedness of é, Putting all the bounds together, we get that
30

---

Faster Rates for Private Adversarial Bandits
E 7(1 7) A.21.7
Σ
Σ (0())((())
E
S
inf JE M
l un + log(N)
+
γ
T
11
(1 - 7)
K
11
2001)(()))
E
r(1 - 7)
A.Z1.
10n
T
T x log²(N (NV
[
)
Multiplying both sides by 7(1 - -)), gives
+ K
7(1 7) log(N)
T
Σ 20000
E
S
(1--) inf
Σ
2 p
+ Ty
A,ZI.
JE[M]
+ 77
E A.ZL.T
(1)
E
t=1 i=1
T 10m 7)5
x² log
which implies that
K
Tlog(N)
E
Σ
Σ
(1))((
F
inf jE[N]
Σ t=1
l m +
+ 7TT
A.ZIeT
11
+ K Σ
IF + "
Σ
(0(1)(2))
E
A.Zu.r
A=1 ==
T + 10yIIA2 (NV
-T )
+
Using the fact that & is an unbiased estimator of & gives that
+
K
+
(lg((N)
T
Σ
Q0(1)
E
inf JE[N]
le
+ +I
Σ
Σ
(i)
E
+
+1 2 (N
A.ZuT
71
A.ZII
By the boundedness of the loss, we have
T logg(N)
T
T
E A.ZI.
Σ
Σ
Q((1)(()))
D
<
inf JEIN]
l
m
+ 7T nKT
+ 10n X logg
"
t=1 =
1=1
31

---

Faster Rates for Private Adversarial Bandits
Bounding the regret in the last 7 rounds by 7, gives
T
K
T le mg +
T Tlog(N)
E
ΣΣ (1(1)(()))
Fe
& inf JE[N]
+ +TT + TTTK + 100TT>² 10rTT>1og log)(NT) +
A.ZI.T
7
t=1
T
T [log(N)
90gTNK2 log( (3) log log (NT)
S inf jE[N]
le mn]
+
7T + 1TKK
+7
62n272
7
Using Equation 1, then gives that
(o))(N)
90nTNK² log( ()) log (NT)
R(T,K,N)
+ +TT+ + + +nTK +
+ 2T
E2,272
Since 7) < 1, we trivially have that
R(T,K,N) 3rlog(N)
90 log( ()) log (NT) E2y272
log((NT)
+ TT + nTK +
Now, choosing 7 = max ///N1/8 K2/ 1// (NT)
12 y log( + NNT) NT)
2/3,2/3
gives
R(T,K,N) (og((N)
17 (2 (NT) n v (lg((H)) log(NT) log(NT)) 2//3
+ 90 max
T+TTK
(N log( 1))) log (NT) log (N))
(N logt (ogg())) () 2/g2/"( (NTTy
Choosing
T1/3/1/2g1/5
and r
c2/8 log (3N
gives
95(N (og()) 1/2
log 1/3 1og (NT) log 1/3 log (NNT2/
R(T,K,N) <
e\/3
(95N (95Nlog(())) 2)) K2/2 log 2/3 (NT) 2/3 (N)71/3
2/3
/2222/ log N
/6 ( log /3 (NT) log 1/3 /3 (NN
1//
log( 12/2 1/2 log(NN)) log(N)
e
which completes the proof.
Proof. (of Privacy in Theorem 4.5) Fix 5 E (0, 1]. Note that the sequence of actions played by Algorithm 2 are completely determined by the noisy loss vectors 8 ........ Lzz. Thus, by post-processig it suffices to show that these vectors output in a e-diffcrentially private manner. From this perspective, Algorithm 2 can be viewed as the adaptive composition M of the sequence of mechanisms M MI...., M f where Mj ((K) x I{(AT))² E - T defined as
M1 1sT l.T)) = ((())
32

---

Faster Rates for Private Adversarial Bandits
for L2 ()) defined as in Line 10 of Algorithm 2. Likewise, for (2..... ..... [1). define M2 (R-V)-+ x (TT(K]) [K])*
lurr R.N such that
I:N M. (L M(s-) 1isr ((s +1 -o- (1T) = (C.,(()....,,,,...)) (N))
We will prove that M( and ((1r)) are (c, dndistiiitig To do so, fix two neighboring data sets f1r and fi Let L' be the index where the two datasets differ. Let E {1,.... [ } be the batch in where 1' lies. Fix sequence of
outcomes 1 E (R*) $ Pi:T [I((K) NT, and IrT E [K]*.
For all and
1:N r', we have that the random variables M, (r- (rr-1)+++rr trry / ((r-))++srs lier)
now show that -1 (1- 1)r+1:r' 11r (11-1))+++' (1T)) and Mp P 1)r+rr' 1 1 1)-+'' :err) are (c, I:N
M, (21r-11 1 (r- 1)r+ I ((-- (r-1))+tr::: ( are O-indistinguishable.
I:N
We
indistinguishale. On input ø1. - -1-))))++= and () the mechanism M, (ir)) computes (
1:N
(,,()== {x)(5) + Zp,, where Zh, Lap
3k / N log(?))
and
yTE
K pe (i) = Qm(i)
(x(())= = T
Σ m= (r' 1y141
for every j E [N]. Note that #ir'-1 complete determines Qm. Moreover, the global sensitivity of (f), with respect to neighboring datasets, is at most K since (+) 2 7. for E [T]. Accordingly, by the Laplace Mechanism and advanced composition, we have that the outputs of Mpr(. (c, (1TT and Mp (-, (1:)) are (s. 6) -iiniiiinguuihablee..
yr
To complete the proof, it suffices to show that for indistinguishable. However, this follows from the fact that for every r 2 r' + 1, we have that ( 1)r++1r7=11111 1-1-1)r +)r+1 and that mechanism M, does access the true data ())r but only the privatized, published outputs of the previous mechanisms M1 MI.....22 M, Thus, by advanced composition, have that the entire mechanism M is (=, -iifferrenilll private.
r' r'+1, 1, we have that the outputs of, M, (1:)) and Mr(s, (1:)) are
G. Barriers to Private Adversarial Bandits
G.1. Privacy leakage in EXP3
To better understand its per-round privacy loss, is helpful to view EXP3 as the adaptive composition of T mechanisms M2,..., My where M. : [K]*_1 x 1.7 + [K]. For every & (2...., T), , the mechanism Mr, given input the previously selected actions J,.... I and the dataset fi.r, computes the distribution
wi(1)
7
(((() = (1 - 7)
+
Σx == we(
K
where w)( exp(-n Etp (.)) and (.() ((HL)) Then, Mr samples action ~ Pt. The mechanism M, P.G)
Er-differentially private if for any pair of neighboring data sets liTT and fr.r, we have that
PIM, (4
(1T)) St (1a-1.
sup I.
sup KJ SEIKT
Now, consider two neighboring datasets f1.T and lrr that differ at the first time point the sequence of probabilities output by the mechanisms when Since & * f, we have that & & 8g. Accordingly, P2 # P The key insight now that because P2 * P/, we have that &g # &g and so P3 + P/- Continuing this process gives that P, + P/ and é, + & for all t 2 2. Unfortunately. this difference in probabilities can cause the privacy loss to grow with t. To get some intuition, fix some 2 2 and sequence J,,..., I-1 E [K] Consider the ratio
Let Pi...., Pr denote fırr and let P',..., Pj denote the same for f.r-
33

---

Faster Rates for Private Adversarial Bandits
1.0
P P_t(2)
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0
1e6
Figure 1. Probabilities on action 2 assigned by EXP3 when run with 0.0001, and T = 100
on datasets & and Cyr-
sup (i) ΣK w/(i) (E[K]
Pi(i)
wr(i)
sup kE[K] P!(
sup
(((() Σ 1コ=1 wili)
kE|K] w((i)
Observe that
we(
(
Σ (.( - {c(1)
1-1
sup <E[K] (1(
sup exp iE[K]
11 sm1
(1) (())T(() =1 =
1 + E E = (0) P!(i) P.
sup exp(") KE[K]
P1(1)
Since (i(1) # Pi( for every 5 t 1, we can pick two neighboring sequences of losses and a sequence of actions J1,...,
, JT such that suP{e(K] (( grows very quickly with s. For example, the following choices for neighhoring datasets
(1)
and sequences of actions will do. Let K = 2 and pick ę1.r such that (1) = 1, f (2) = O, and fx(1) = (, = 1 for all t (2. T). Pick neighboring dataset fT.T such that (1) = (2) = 1, for all E [T]. Finally, consider the sequence of actions I1 ... Ir such that I, if is odd and I, if is even. That is, the sequence of actions I,..., Ir alternates between 2 and 1, starting with action 2.
We claim that for this choice of neighboring datasets and sequences of actions, (2( and P2( diverge rapidly with (2(2) approaching for the loss sequence fI.T, have that W1+2(1) (1+1(1) w. exp -0 and wx+2(2) (x(() exp (-)
and (2( approaching z. To see why. fix t 2 2 and suppose that I, = 1. Then, by definition,
Since L = 1, we know that (1) P1) and therefore W2+2(2) w. (2) exp 1-7:(1] Now, if P1( < 3.2 then (1e=2(1/uu4all
< wrr (r)/w/ (2) (2) < 1. Accordingly, P1)2(1) < 1/2, and repeating the analysis would eventually 3. A symmetric argument shows that if P.(1) 1/2. then 3.- Since the two loss sequences f1rr and Grr identical after time point 2, an identical argument holds for C To complete the proof sketch, note that for loss sequence C1TT, /4 1 and (1(1) < 1. thus (2)
show that w. (1) (w((2) + O, implying that (2(2)
(x(2))ux (0,)//1,1000 (1)(()))))))))))))) O, and therefore (2)
7. On the other hand, for loss sequence fr 12 1 and PA(1) > z. giving that P!( + 3
We also verify this claim empirically in Figure 1, which gives a better sense of the rate of divergence between (2(2) and P((2). The code generating the figure above is provided below.
34

---

Faster Rates for Private Adversarial Bandits
import пumpy np import hatplotlib.pyple as plt
eta 0.0001
100 int (1/eta)
gamma eta
Exccute EXP3 on loss sequence I_, (dots, L
w_1 =1
M_2
P_2
P_2_hist - [1
for in range (T)
2 (w 2/ (w + w ))) funmixed prob.
2 = (1-ganna) * Q gamma/2 #mixed prob.
22_hiist.appeddee
if == 0:
R_2 w_2 pp. (0 (P_2))
elif t 2 0:
x_2 = w_2 np. (l1leta/aaappee (P_2)) #pull action 2 in even rounds
else:
1_
ep.exp (-1+eta/ ((1-P_2)) spull action 1 in odd rounds
plt.p plot (P_2 2 hist, label= (2)
Execute EXP3 loss sequence 1 1'_,, Adots, 1'r
w_1
w_2 =1
2_2 =
P_2 hist = []
for range (T):
Q_2 (w_2/ (w_2 + w_1))
P_2 = (1-gamma) 0_2 gamma/2
ap__ist.apppedd (P_2)
if $ 0:
2 2
pp.exp (-1-eta/ (P_2)) #pull action in even rounds
else:
I 1 ex.exp (-1xeta/ ((1-__)) &pull action 1 in odd rounds
alt.plot P_2_hist, label= "p' "p'_t(() ())
plt.xlabe xlabel ("t")
plt. legend ()
We note that the authors of (Tossou & Dimitrakakis,, 2017) acknowledge that this issue was overlooked when stating Theorem 3.3 (Tossou Dimitrakakis, 2017). Therefore, we are unable verify the Theorem 3.3. Unfortunately, (Tossou Dimitrakakis, 2017) use Theorem 3.3 in the proof of Corollary 3.3, which claims to give private adversarial bandit
ignoring log factors in z. Thus, we are unable to verify whether algorithm with expected regret Ö T2/3 (K)((K) Corollary 3.3 correct.
2173
G.2. Proof of Lemma 5.1
Proof. (of Lemma 5.1) Let A be any e-differentially private algorithm (for & S 1) that satisfies condition (1) and (2) with parameters 7 E [0, 11, T and 2yr S S 7(T 7). Consider the alternate sequence of loss functions ,,..., Ey such that f f1r but l such that (2()) and (1( for all E {T + 1,..., T).
2
35

---

Faster Rates for Private Adversarial Bandits
suffices to show that
P E2,) P( 1x,,)) S _e
(2)
where I.T and 1 are the random variables denoting the selected actions of A when run on 1.T and '/.r respectively, Indeed, when .j,..., 1/ E E we have that the regret of when run on É/.r at least by 2 2- On the other hand, if I E E,,, we have that the regret of A on ferr is at least T.T. So with probability the regret of A on f1r is T and with probability at least 1 - e the regret of A on frr is at least 27 - _ 2 2 g. 2 where the inequality follows from the fact that y S 2.
1. Therefore, the worst-case expected regret least
TT (1 2
1 )
P - 5 47
T 1-2er)
(1 c
YT 4
max
max
1
5
2
2
47
To prove Equation 2, recall that may write any randomized algorithm A deterministic function of an input and an infinite sequence of bits b1, b2.... generated uniformly at random. From this perspective, we can think of randomized bandit algorithm A as deterministic mapping from sequence of losses frr and an infinite sequence of bits b E {0, 1) to a sequence of 7 actions. That is,
A: : {0. 13 (10, - [K]_.
Using this perspective, Equation 2 is equivalent to showing that:
P 6-101,1 (A(b, & ET,,) e po (00 (A(b, $ E..,).
Consider the following sequence of losses parameterized by c (T +1, 7}. sp:
1/2,
if =
(5())
0, if and S
1,
i 2 and & S
Let L = (G. S (1+,,... .,,,, S pp } be the collection of all such sequences of loss functions. Note that every
y E L differs from lir only at time points E S. Thus, by group privacy (see Lemma A.8), we have that
sup P EC b- (A(b, & E²,+) S PP bu (A(b, & E2,,).
Now, fix the sequence of random bits b E 10 Let LT = A(b, A(b. Define S' = (t 2 + 1: : i = 2} and
5 S'Sp be the first p such time points. Let 1.7 Alb, (es)) Let t' max(t 2 +1 Ei H1, 2} < p} and
S = = 2 t + Ei I(1-'0 = 2} S p}. Because bandit algorithms only observe the losses of the selected
action, have that L' 18 In addition, we have that ih E EP,r if and only if l' 2 T n/2 and likewise for 11.7 Therefore,
&
Thr FR 16i F.
and therefore
Ii & Ex = 1fi & E
Taking expectation on both sides with respect to b ~~ (0, 13 gives that
36

---

Faster Rates for Private Adversarial Bandits
(o.(0. (1r)) $ 1),,)) = (o (i5) & ET
I sup P EL mnco.ij (A(b, ((:T) & E2,r))
S PP waaaaa (A(b, & b,,r),
completing the proof.
37


Reviews:
[{"review_id": "tPzOM9s8F0", "reviewer": "Reviewer_124Y", "summary": "This paper studies adversarial bandit problems and bandit problems with expert advice, and introduces a differentially private algorithm that achieves better regret bounds than previous approaches.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address their concerns below and hope they will reevaluate their score accordingly.\n\n> in line 43-44, \"Motivated by this gap\", which gap?\n\nBy this phrase, we are referring to our comment in the previous sentence on lines 38-40: \"it was not known how large $\\epsilon$ needs to be to obtain sublinear expected worst-case regret.\" We will clarify this in the final version. \n\n> \"it is well known that this is not the case for local differential privacy.\" then what is your contribution?\n\nIn this paper, we study the weaker notion of *central differential privacy*. Our results (Corollary 3.2) shows that under central differential privacy constraints, sub-linear regret is possible even when $\\epsilon \\leq \\frac{1}{\\sqrt{T}}.$ This is not the case under the strict notion of *local differential privacy*, where sublinear regret is **not** possible if $\\epsilon \\leq \\frac{1}{\\sqrt{T}}.$ Hence, our results establish a separation between central and local differential privacy in terms of when sublinear regret can be achieved. \n\n> No experiments\n\nWe acknowledge the reviewer's concern. However, our work is intentionally theoretical, aimed at understanding fundamental rates and limits of private adversarial bandits.\n\n>  (Q1) The regret of $O(\\sqrt{KT \\log K}/\\epsilon)$ is for the local differential privacy model...\n\nSince local differential privacy is stronger than central differentially privacy, any $\\epsilon$-locally differentially private algorithm is also an $\\epsilon$-centrally differentially private algorithm. Accordingly, comparing our regret bounds against $O(\\sqrt{KT \\log K}/\\epsilon)$ *is still meaningful since this is the only known regret bound for adversarial bandits under central differential privacy*. That is, we don't intend to compare our CDP results with LDP; it just happens to be the case that the previous best known regret bound for adversarial bandits under CDP is $O(\\sqrt{KT \\log K}/\\epsilon)$.\n\n> (Q2) What are the same points and differences among the three algorithms?\n\nFor bandits *with expert advice*, we give three different algorithms/regret bounds to cover different combinations of small and large $K, N$ and $\\epsilon.$ In particular, amongst the three algorithms we give, none of their regret bounds strictly dominate the other -- there are certain choices of $K, N$ and $\\epsilon$, where the regret bound of one algorithm is better than the other. Below, we highlight three regimes and the corresponding algorithm that obtains the best regret bound in that regime. We will include this detailed comparison in the final version. \n\n**Low-dimension and High Privacy ($N \\leq K$):** Our upper bound $O(\\frac{\\sqrt{NT}}{\\sqrt{\\epsilon}})$ is superior. \n\n**High-dimension and Low Privacy ($N \\geq K$ and $\\epsilon \\geq \\frac{K}{N}$):** Our second upper bound $O(\\frac{\\sqrt{KT \\log N} \\log(KT)}{\\epsilon})$ is superior.\n\n**High-dimension and High Privacy ($N \\geq K$ and $\\epsilon \\leq \\frac{1}{\\sqrt{T}}$):** Our third upper bound $O(\\frac{N^{1/6}K^{1/2}T^{2/3}\\log(NT)}{\\epsilon^{1/3}} + \\frac{N^{1/2}\\log(NT)}{\\epsilon})$ is superior. \n\nThese regimes are all interesting in practice, so it's important to get the best rates for each one.  With regards to the algorithms, two out of the three algorithms, namely those obtaining the guarantees in Corollary 4.3 and Theorem 4.5, use the batching plus noise technique. The last algorithm, the one obtaining the guarantee in Theorem 4.4, does not batch and adds noise to each loss vector. \n\n> (Q3) What is the exact information you want to protect?\n\n We are taking *only* the sequence of loss functions as the sensitive information. This is made explicit in our definition of differential privacy in Definition 2.4 and is standard in the private bandit literature.\n\n> (Q4) Why did you choose pure differential privacy?\n\nPure differential privacy is a stronger privacy guarantee and often easier to derive minimax rates for. Surprisingly, and unlike under full-information online learning, we found that even under pure differential privacy, the minimax rates for adversarial bandits were not known. This motivated our study of pure differential privacy. \n\n> (Q5) Compare your results with related work.\n\nWe will make sure to include a comparison in the final version. For HTINF, the non-private version achieves a regret bound of $O(\\sqrt{TK})$ whereas our private version achieves a regret bound of $O(\\frac{\\sqrt{TK}}{\\sqrt{\\epsilon}} + \\frac{1}{\\epsilon}).$ So, the blow is by a factor of $O(\\frac{1}{\\sqrt{\\epsilon}}).$ \n\n> (Q6) There is a gap of the factor of $\\sqrt{K}$ between your upper bound and lower bound.\n\nThis gap comes from the fact that in our lower bound we only consider a setting with two arms. It should be possible to upgrade of lower bound with a factor of $K$ using the standard strategy for proving lower bounds for adversarial bandits, but we leave this for future work.", "claims_and_evidence": "The writing is not clear enough. See the weakness part for details.", "methods_and_evaluation_criteria": "They make sense.", "theoretical_claims": "I didn't check the details of the proofs. Most of them seem true.", "experimental_designs_or_analyses": "There is no experiment.", "relation_to_broader_scientific_literature": "Their results improve upon previous regret bounds.", "essential_references_not_discussed": "The paper investigated most of the related work.", "other_strengths_and_weaknesses": "Strengths:\nThe problem in the paper is interesting. And it is good to give the lower bound.\n\nWeaknesses:\n1. The writing is not clear enough. For example, in lines 43-44, \"Motivated by this gap\", which gap? In lines 71- 73, \"it is well known that\nthis is not the case for local differential privacy.\" Then what is your contribution? What is the logic of the sentence?\n2. There are no experimental results.\n3. See the Questions part for more details.", "other_comments_or_suggestions": "See the Questions part for more details.", "questions_for_authors": "1.  The regret of $O(\\sqrt{KT\\log K}/\\epsilon)$ is for local differential privacy model. You consider classical DP in your paper, i.e., central differential privacy. How can you compare your CDP results with LDP since they are different DP models?\n2. You give 3 different DP private bandit algorithms and get 3 regret bounds. What are the same points and differences among the three algorithms? What is your motivation to design them?\n3. You define Definition 2.3 on history $\\{\\mathcal{H}_t\\}$. What is the exact information you want to protect? Loss function or action? Which part is sensitive information?\n4. Why did you choose pure differential privacy, not approximation DP for your work?\n5. Compare your results with related work. For example, compare the result of Corollary 3.2 with non-private  HTINF and explain the effect of privacy.\n6. There is a gap of the factor of $\\sqrt{K}$ between your upper bound and lower bound. Could you please explain it?", "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": "mWKMcbEPJq", "reviewer": "Reviewer_w61y", "summary": "This paper presents novel differentially private (DP) adversarial bandit algorithms with improved dependency on the DP parameter $\\epsilon$. It improves the regret bound from $O(\\sqrt{KT\\log KT}/\\epsilon)$ to $O(\\sqrt{KT}/\\epsilon)$, ensuring no-regret even when $\\epsilon \\sim 1/\\sqrt{T}$. Moreover, the paper's construction is general in that it provides a framework for constructing DP adversarial bandit algorithms from a baseline adversarial bandit algorithm with unbounded and negative losses.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and noting that our work advances the frontier of privacy-preserving algorithms and could have a broader impact. We address the reviewer's main concern below and hope they reevaluate their score accordingly.\n\n> Does Lemma 5.1 rule it out?\n\nThe reviewer is correct in that Lemma 5.1 does not rule out the possibility that the algorithm from Tossou \\& Dimitrakakis (2017) obtains a regret of $O(\\frac{T^{2/3} \\sqrt{K \\log K}}{\\epsilon^{1/3}})$ as this upper bound is larger than our lower bound $O(\\sqrt{T/\\epsilon})$ in Lemma 5.1. Nevertheless, even if one considers the upper bound $O(\\frac{T^{2/3} \\sqrt{K \\log K}}{\\epsilon^{1/3}})$, our upper bound  of $O(\\sqrt{KT/\\epsilon})$ in Corollary 3.2 is strictly better for all $\\epsilon \\leq 1$. \n\n> In Line 1850, Shouldn't...”?\n\nYes, this is a typo and the reviewer is correct. We will make sure to fix this in the camera-ready version.", "claims_and_evidence": "This paper is mainly theoretical and its claims are supported by proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I could not find any specific issues with their theorems, particularly their main results, Theorem 3.1 and Theorem 4.2, which provide a general conversion from a class of bandit algorithms to differentially private ones.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper extends the line of research on DP online learning, particularly DP adversarial bandit algorithms. Their results demonstrate that no-regret learning is achievable for any privacy parameter $\\epsilon \\in \\omega(1/T)$ in the oblivious adversary setting under the central DP model. This setting is optimal in the sense that it is known that no-regret learning is impossible for $\\epsilon \\in o(1/\\sqrt{T})$ in either the adaptive adversary setting or the local DP setting. Their improved dependence on $\\epsilon$ implies a better trade-off between privacy and utility, advancing the frontier of privacy-preserving algorithms.", "essential_references_not_discussed": "All essential references are discussed to the best of my knowledge.", "other_strengths_and_weaknesses": "**Strengths**  \n\n- This paper provides a simple conversion technique from adversarial bandit algorithms with unbounded losses over the reals to a DP adversarial bandit algorithm with improved rates. This could have a broader impact due to its simplicity and its independence from the details of the baseline (host) algorithm.  \n- They provide a lower bound of $\\Omega(\\sqrt{T/\\epsilon})$ for a class of algorithms, including EXP3 and its batched variants.  \n\n**Weakness**  \n\n- While they have shown, through experiments and quantitative arguments, that Theorem 3.3 of Tossou & Dimitrakakis (2017) is problematic, it is unclear whether Lemma 5.1 in this paper definitively rules out one of Tossou & Dimitrakakis (2017)'s algorithms claiming a regret of $\\widetilde{O}\\left(\\frac{T^{2/3}\\sqrt{K\\log K}}{\\epsilon^{1/3}}\\right)$ (This is also my question: Does Lemma 5.1 rule it out?).", "other_comments_or_suggestions": "In **Line 1850**,  Shouldn't \"...$M_t:[K]^{i-1}$...” be “...$M_t:[K]^{t-1}$...”?", "questions_for_authors": "Please refer to the strengths & weaknesses section above.", "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": "Nma6rbv0gI", "reviewer": "Reviewer_NE5W", "summary": "The paper presents novel differentially private algorithms for adversarial bandits and bandits with expert advice. The primary contribution is an efficient conversion method that transforms any non-private bandit algorithm into a differentially private one, leading to improved regret bounds. The proposed algorithms achieve regret upper bounds of O(\\sqrt{KT/ϵ}) (the sota had an additional log term) for adversarial bandits, which improves on existing results. Additionally, for bandits with expert advice, the paper introduces the first differentially private algorithms with various regret bounds that cater to different settings of actions, experts, and privacy parameters.\n\n## update after rebuttal\"\nI have read the discussions and I keep my assessment unchanged", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their comments. We address their concerns below and hope they will reevaluate their score accordingly.\n\n> No experiments.\n\nWe acknowledge the concern regarding the lack of experiments. However, our work is intentionally theoretical, aimed at understanding fundamental rates and limits of private adversarial bandits. Theoretical contributions often provide key insights that guide future empirical research. While experimental validation is certainly valuable, we believe that our results are meaningful in their own right and align with the norms of theoretical research in this area.\n\n> (Q1) How do the proposed algorithm compare experimentally to the SOTA?\n\nOur paper is mainly theoretical in nature. That said, we agree with the reviewer that this is an important direction of future work.\n\n> Could alternative privacy mechanisms improve regret rates?\n\nThis is a great question. We believe that one way to improve our regret bounds is through the use of the Binary Tree Mechanism, which has been used to obtain private regret guarantees in the full-information setting. However, our current attempts at doing have been unsuccessful. In particular, some subtleties arise in the bandit setting as one needs to deal with unbiased estimates of the true loss, whose sensitivity can be massive. We will make sure to discuss this in the camera-ready version. \n\n> How does the proposed approach generalize to contextual bandits?\n\nThe bandits with expert advice setting can be viewed as the contextual version of the traditional adversarial bandit setting [1]. Accordingly, our results in Section 4 show that our techniques do extend to the contextual setting. Table 1 summarizes the exact regret bounds we achieve for the bandits with expert advice setting. \n\n[1] Auer, Peter, et al. \"The nonstochastic multiarmed bandit problem.\" SIAM journal on computing 32.1 (2002): 48-77.", "claims_and_evidence": "The paper claims an improvement over the previous best regret bound. This improvement is significant because it ensures sublinear regret even when ϵ≤\\sqrt{T}​, which was not previously achieved. The claim is supported by mathematical proofs demonstrating regret upper bounds under different adversarial conditions.\nThe study establishes a fundamental separation between central and local differential privacy in adversarial bandits, proving that sublinear regret is possible for ϵ∈o(1/\\sqrt{T}) under central differential privacy, whereas this is not achievable under local differential privacy.\nThree different private algorithms are introduced, achieving different regret bounds with various techniques.", "methods_and_evaluation_criteria": "The paper primarily employs theoretical analysis to evaluate the effectiveness of the proposed algorithms. No numerical experiments are reported.", "theoretical_claims": "Generic Conversion Framework:\n    The paper establishes a (very simple) framework to convert any non-private bandit algorithm into a private one while maintaining sublinear regret.\n    The core technique involves batching rounds and adding Laplace noise to the observed losses.\n\nLower Bounds and Limits:\n    The authors prove that it is difficult to achieve an additive separation between ϵϵ and TT in the adversarial bandit setting, unlike in full-information settings.\n    They also show that standard EXP3-based approaches are challenging to privatize effectively due to compounding privacy loss over multiple rounds.", "experimental_designs_or_analyses": "nothing here", "relation_to_broader_scientific_literature": "The paper builds upon and extends several foundational works in adversarial bandits and differential privacy, with no remarkably original mechanism or proof scheme.", "essential_references_not_discussed": "The interest of the contribution is justified by the application of bandits to \"online advertising, medical trials, and recommendation systems\" but the relevance of adversarial bandits in these settings would deserve references.", "other_strengths_and_weaknesses": "+ The proposed framework (Alg 1) applies to any non-private bandit algorithm, it is very simple and natural.\n+ The introduction of batching and noise addition significantly improves private bandit performance.\n- No experimental results are presented to support theoretical findings.\n- The paper focuses purely on theoretical settings without discussing real-world implementations.", "other_comments_or_suggestions": "It would be useful to contrast the results with private stochastic bandits to understand trade-offs.", "questions_for_authors": "How do the proposed algorithm compare experimentally to the SOTA?\nCould alternative privacy mechanisms improve regret rates?\nHow does the proposed approach generalize to contextual bandits?", "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": "PEzq0ff4bq", "reviewer": "Reviewer_faFK", "summary": "This work studies the adversarial bandit problem where the reward function can vary across stages and considers a differential privacy guarantee. The author proposes a novel algorithm within a batched learning framework, adding Laplace noise to the average reward in each batch to ensure differential privacy. Compared with previous work, this approach achieves a better dependency on the differential privacy parameter $\\epsilon$ while still maintaining a $\\sqrt{T}$ regret.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address the reviewer's main concern below and hope that they will reevaluate their score accordingly.\n\n> Therefore, it is not entirely fair to directly compare the results with prior work, as the improvement may stem from this assumption.\n\nWhile adaptive adversaries are well-studied in non-private bandit literature, oblivious adversaries have been the main focus in the private bandit literature. In particular, there are only two previous works that study private adversarial bandits, namely Tossou \\& Dimitrakakis (2017) and  Agarwal \\& Singh (2017). In the last two paragraphs of Section 2.1,  Tossou \\& Dimitrakakis (2017) make explicit that they first consider an oblivious adversary. They then note that their guarantees can be apply to an $m$-bounded adaptive adversary. As for Agarwal \\& Singh (2017), Theorem 4.1 makes it clear that they only consider an oblivious adversary as the sequence of loss vectors is fixed before the game begins. Nevertheless, if one considers an adaptive adversary, then the lower bound from Asi et al. (2023) shows that sublinear regret is not possible under pure differential privacy even for a constant $\\epsilon$. Moreover, for approximate differential privacy, the lower bounds from Asi et al. (2023) show that sub linear regret is not possible if $\\epsilon \\leq \\frac{1}{\\sqrt{T}}.$ Thus, the adaptive adversary case is not as interesting because existing algorithms are already optimal (up to log factors).\n\n> The definition of differential privacy should be refined...\n\nOur definitions of differential privacy (see Definitions 2.3 and 2.4) do include $\\delta$, and this is the standard $\\delta$ which people use to capture failure probability.  \n\n> Additionally, in lines 236-237, there is a contradiction between the stated upper bound and the previously established lower bound.\n\nOur algorithm obtaining the upper bound in Corollary 3.2  satisfies the notion of central differential privacy. Therefore, the lower bound from Basu et al. (2019) does **not** apply here as it hold for the more strict notion of local differential privacy. We will clarify this in the paper. We will also make sure to include an explicit definition of local differential privacy in the camera-ready version. \n\n> (Q1) While the Generic Conversion method is well-motivated, it is unclear which of the three different results for Bandits with Experts is the best, and what specific advantages the other algorithms provide.\n\nNone of the regret guarantees of our three algorithms strictly dominate the other. Below, we highlight three regimes and the corresponding algorithm that obtains the best regret bound in that regime. We will make sure to include this detailed comparison in the final version. \n\n**Low-dimension and High Privacy ($N \\leq K$):** In this regime, our upper bound $O(\\frac{\\sqrt{NT}}{\\sqrt{\\epsilon}})$ is superior. \n\n**High-dimension and Low Privacy ($N \\geq K$ and $\\epsilon \\geq \\frac{K}{N}$):** In this regime, our second upper bound $O(\\frac{\\sqrt{KT \\log N} \\log(KT)}{\\epsilon})$ is superior.\n\n**High-dimension and High Privacy ($N \\geq K$ and $\\epsilon \\leq \\frac{1}{\\sqrt{T}}$):** In this regime, our third upper bound $O(\\frac{N^{1/6}K^{1/2}T^{2/3}\\log(NT)}{\\epsilon^{1/3}} + \\frac{N^{1/2}\\log(NT)}{\\epsilon})$ is superior. \n\nThese are all regimes that are interesting in practice, so its important to get the best rates for each one of these regimes. \n\n> (Q2) However, it is unclear why this method fails to achieve a $1/\\sqrt{\\epsilon}$ dependency in the second and third regret guarantees.\n\nThe second guarantee (Theorem 4.4) actually does not use the batching method. Instead, it simply adds Laplace noise to each loss vector. Thus, one should not expect to get a $\\frac{1}{\\sqrt{\\epsilon}}$ here, as this approach actually gives a stronger, local DP guarantee. We will make this more explicit in the camera ready version. As for the third guarantee, this is more subtle and occurs because more noise needs to be added to privatize the batched expert losses. We will include a more complete discussion in the camera-ready version.\n\n> (Q3) However, it remains unclear whether the batch learning framework with a batch size of  can effectively remove the logarithmic dependency on  compared to previous work...\n\nOur technique allows us to improve upon existing regret bounds in terms of both $\\epsilon$ and $T$. As the reviewer noted, our batching with noise technique allows to improve the dependence on $\\epsilon$ from $1/\\epsilon$ to $1/\\sqrt{\\epsilon}.$ However, our technique also allows us to *expand* the set of bandit algorithms that we can privatize beyond EXP3. In particular, we are now able to privatize *heavy-tailed* bandit algorithms which do not have $\\log{T}$ terms in their regret bounds, one of which is the HTINF algorithm from Huang et al. (2022). Because our reduction carries over the regret bound from the base bandit algorithm, we are able to remove a log factor in $T.$", "claims_and_evidence": "The author provides a clear claim of the result in the theorems and includes a proof sketch to outline the key steps of the theoretical analysis.", "methods_and_evaluation_criteria": "The main contribution of this work focuses on the theoretical analysis of regret, with the simulation serving as an auxiliary tool to support its efficiency, which is reasonable and sufficient.", "theoretical_claims": "The author provides a clear proof sketch outlining the key steps of the theoretical analysis. The critical step involves transitioning from the Non-Private to the Private setting. With the batched learning framework, it becomes reasonable to reduce the magnitude of the Laplace noise added to the average reward function, saving a factor of $\\epsilon$. On the other hand, the batched updating in an adversarial environment introduces an additional dependency of $\\sqrt{\\epsilon}$. Therefore, the improvement in the dependency on $\\epsilon$ appears reasonable.\n\nHowever, a concern regarding correctness arises with the logarithmic dependency on the number of rounds $T$. Based on the proof sketch, the only stated improvement concerns $\\epsilon$, and it remains unclear whether the batch learning framework with a batch size of $1/\\epsilon$ can effectively remove the logarithmic dependency on $T$ compared to previous work.", "experimental_designs_or_analyses": "The main contribution of this work focuses on the theoretical analysis of regret, with the simulation serving as an auxiliary tool to support its efficiency, which is reasonable and sufficient. Therefore, there is no need to evaluate the soundness or validity of the experimental designs or analyses.", "relation_to_broader_scientific_literature": "This work mainly focuses on providing a differential privacy guarantee for the adversarial bandit problem, which may be related to other works on bandit analysis.", "essential_references_not_discussed": "This paper provides a comprehensive discussion of related work in adversarial bandits and private bandits.", "other_strengths_and_weaknesses": "Compared with previous works in the adversarial bandit problem, this work relies on a stronger assumption of an oblivious adversary, where all reward functions are chosen at the beginning and cannot adapt based on the agent's previous actions. Therefore, it is not entirely fair to directly compare the results with prior work, as the improvement may stem from this assumption. It would be beneficial to explicitly highlight this difference in the introduction and include it in the comparison table.", "other_comments_or_suggestions": "The definition of differential privacy should be refined. For instance, in Theorem 4.5, the algorithm provides a $(\\epsilon, \\delta)$ privacy guarantee, but the earlier definition only involves $\\epsilon$, making it unclear what $\\delta$ represents. Additionally, in lines 236-237, there is a contradiction between the stated upper bound and the previously established lower bound. This discrepancy appears to stem from different definitions of privacy (local vs. non-local differential privacy). However, the paper does not clearly define local differential privacy or explain what specifically accounts for the gap in the regret bound. Clarifying these aspects would strengthen the theoretical consistency of the work.", "questions_for_authors": "The results for Bandits with Experts are somewhat confusing, and several questions arise:\n\n1. While the Generic Conversion method is well-motivated, it is unclear which of the three different results for Bandits with Experts is the best, and what specific advantages the other algorithms provide. A clearer comparison of these results would be helpful.\n\n2. Based on the proof sketch, the proposed method appears to be a general framework applicable to any algorithm. However, it is unclear why this method fails to achieve a $1/\\sqrt{\\epsilon}$ dependency in the second and third regret guarantees. A more detailed explanation of this limitation would be beneficial.\n\n3. Regarding the Adversarial Bandit result and the first result for Bandits with Experts, the proof sketch suggests that the only stated improvement concerns $\\epsilon$. However, it remains unclear whether the batch learning framework with a batch size of $1/\\epsilon$ can effectively remove the logarithmic dependency on $T$ compared to previous work. Clarifying this aspect would improve the theoretical discussion.", "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:

Meta-review: This paper presents a **central differentially private (CDP)** framework for the adversarial bandit problem. Its main contribution is a generic conversion method that transforms any non-private adversarial bandit algorithm into one satisfying CDP, achieving a regret bound of $O\left(\frac{\sqrt{K T}}{\sqrt{\varepsilon}}\right)$. Additionally, the work extends this approach to bandits with expert advice, proposing the first DP algorithms for this setting with regret bounds that adapt to the number of actions, experts, and privacy parameters. A key insight of the results is that, unlike **local differential privacy (LDP)**, where sublinear regret is impossible when $\varepsilon \leq \frac{1}{\sqrt{T}}$, the proposed CDP framework maintains sublinear regret even in this regime. This demonstrates a fundamental separation between CDP and LDP in adversarial bandits. 

This paper was escalated to the SAC, who also reviewed the paper in detail. Overall, we believe the paper offers a versatile and theoretically sound approach to differentially private adversarial bandit learning, providing a better understanding of privacy-regret trade-offs in such problems.

However, one reviewer pointed out that LDP differs significantly from CDP. Therefore, while the dependence of regret on $\varepsilon$ in this work is tighter than that in previous studies on bandits with LDP, it may not be entirely accurate to claim that the regret in this work directly improves upon the existing upper bound of $O\left(\frac{\sqrt{K T \log (K T)}}{\varepsilon}\right)$, as stated, for example, in lines 19-21 of the abstract in the current version. Thus, the authors are strongly advised to carefully check and clarify all such comparisons for better accuracy and clarity in the camera-ready version of this work.
Decision: Accept (poster)