Optimal Regret of Bandits under Differential Privacy
Authors: Achraf Azize
Yulian Wu
Junya Honda
Francesco Orabona
Shinji Ito
Debabrota Basu
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Multi-armed Bandits
Regret Analysis
Lower Bound
Primary area: theory

Abstract: As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utilities emerges as a timely question. In this context, regret minimisation in stochastic bandits under $\epsilon$-global Differential Privacy (DP) has been widely studied. 
The present literature poses a significant gap between the best-known regret lower and upper bound in this setting, though they ``match in order''.
Thus, we revisit the regret lower and upper bounds of $\epsilon$-global DP bandits and improve both. 
First, we prove a tighter regret lower bound involving a novel information-theoretic quantity characterising the hardness of $\epsilon$-global DP in stochastic bandits. This quantity smoothly interpolates between Kullback–Leibler divergence and Total Variation distance, depending on the privacy budget $\epsilon$.
Then, we choose two asymptotically optimal bandit algorithms, i.e., KL-UCB and IMED, and propose their DP versions using a unified blueprint, i.e., (a) running in arm-dependent phases, and (b) adding Laplace noise to achieve privacy. For Bernoulli bandits, we analyse the regrets of these algorithms and show that their regrets asymptotically match our lower bound up to a constant arbitrary close to 1.
At the core of our algorithms lies a new concentration inequality for sums of Bernoulli variables under Laplace mechanism, which is a new DP version of the Chernoff bound.
Finally, our numerical experiments validate that DP-KLUCB and DP-IMED achieve lower regret than the existing $\epsilon$-global DP bandit algorithms.

Optimal Regret of Bandits under Differential Privacy
Achraf Azize* FairPlay Joint Team CREST, ENSAE Paris achraf wzizzeensae..fr
Yulian Wut
King Abdullah University of Science Technology (KAUST)
Thuwal 23955-6900, Kingdom of Saudi Arabia yul ian wu@kaust. edu.sa
Junya Honda Kyoto University RIKEN AIP
Francesco Orabona
King Abdullah University for Science & Technology (KAUST)
Thuwal 23955-6900, Kingdom of Saudi Arabia
honda@i. waw.aaii.kkooouu.ac...
francesco@orabona. com
Shinji Ito
Debabrota Basu
The University of Tokyo
Univ. Lille, Inria, CNRS Centrale Lille, UMR 9189-CRISIAL debabrota. basu@inria.. fr
RIKEN AIP
shinjimmiin uu-toiitsttt.ttttoooooo ac.
Abstract
As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utilities emerges a timely question. In this context, regret minimisation in stochastic bandits under e-global Differential Privacy (DP) has been widely studied. The present literature poses significant gap between the best-known regret lower and upper bound in this setting, though they "match in order". Thus, revisit the regret lower and upper bounds of c-global DP bandits and improve both. First, we prove a tighter regret lower bound involving a novel information-thooretii quantity characterising the hardness of e-global DP in stochastic bandits. This quantity smoothly interpolates between Kullback-Leibler divergence and Total Variation distance, depending the privacy budget Then, we choose two asymptotically optimal bandit algorithms, i.e., KL-UCB and IMED, and propose their DP versions using unified blueprint, i.e., (a) running in arm- dependent phases, and (b) adding Laplace noise to achieve privacy. For Bernoulli bandits, analyse the regrets of these algorithms and show that their regrets asymptotically match our lower bound up a constant arbitrary close to 1. At the core of our algorithms lies new concentration inequality for sums of Bernoulli variables under Laplace mechanism, which is new DP version of the Chernoff bound. Finally, our numerical experiments validate that DP-KL UCB and DP-IMED achieve lower regret than the existing e-global DP bandit algorithms.
Introduction
Multi-armed bandit is classical setup of sequential decision-making under partial information, where the agent collects more information about environment by interacting with it. To understand the setting, let us consider clinical trial, where a doctor has K candidate medicines to choose from and wants to recommend "effective" medicines their patients. At each step of the trial, new patient Pt arrives, the doctor prescribes a, [K] {L....,K} one of the K medicines. and
Part of the work is done during A. Azize's visit to Kyoto University and PhD Scool Team, Inria Lille. Part of the work is done during Wu's internship at RIKEN AIP and visit to Kyoto University.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

observes the reaction of the patient to the medicine. The observations are quantified as rewards, such that r, = 1 if the patient p: is cured and 0 otherwise. To design an algorithm recommending "effective" medicines, the doctor can use a regret-minimising bandit algorithm [Thompson) 1933). Le., a bandit algorithm that aims to maximise the expected number of cured patients during the trial.
Following the trial, the doctor wants to release the trial results to the public, i.e., the sequence of recommended medicines (01,...,, aT), in order to communicate the findings. However, the doctor fears that publishing the results may compromise the privacy of the patients who participated in the trial. Specifically, the rewards (r1.....Pr) rr) constitute the private information that needs to be protected, since rewards in clinical trials may reveal sensitive information about the health condition of the patients. In addition to clinical trials, many applications of bandits, such as recommendation
systems [Silva et al.) [022]] online advertisement [Chen et al.] [014], crowd-sourcingg sourcing (Zhou et al. 2014), user studies Losada et al., 2022], ryper-parameted tuning [1.i et al. 2017], communication networks [Lindstähl et al. 2022]. and pandemic mitigation (Libin et al. 2019 J. involve sensitive user data, and thus invokes the data privacy concerns. Motivated by the privacy concerns in bandits, we
study the privacy-utility trade-off in stochastic multi-armed bandits.
We adhere Differential Privacy (DP) (Dwork and Roth [014] as the privacy framework, and regret
minimisation [Auer et al. 2002] in stochastic bandits as the utility measure. DP has been studied for
multi-armed bandits under different bandit settings: finite- armed stochastic [Mishra and Thakurta
2015
(Sajed and Sheffet 2019 ZZheng et al. [2020a] Hu et al. [2021] [Azize and Basu [2022] Hu and
[202 Azize and Basu 2024] Wang and Zhu [2024], adversarial [Thakurta and Smith 2013
Agarwal and Singh] 7 and Dimitrakakis 2017]. linear [Hanna et al. 2022 Li et al. 2022
Azize and Basu 2024], contextual linear [Shariff and Sheffet |018| Neel and Roth | Zheng
et al.] 20206 Azize and Basu (024)) and kernel bandits [Pavlovic et al. [025]] J, among others. Most
of these works were for regret minimisation, but the problem has also been explored for best-arm
identification, with fixed confidence [Azize et al. 2023 2024] and fixed budget (Chen et al. 2024).
The problem has also been studied under three different DP trust models: (a) global DP where the
users trust the centralised decision maker MMisrra and Thakurta| 2013 Shariff and Sheffei 2018
Sajed and Sheffet 2019 Azzize and Basu 2022 Hu and Hegde 2022]. (b) local DP where each user deploys a local perturbation mechanism send "noisy" version of the rewards to the policy [Basu cct al. Zheng et al.) [020aab] Han et all 202T], and (c) shuffle DP where users still feed their data to local perturbation, but now they trust intermediary apply a uniformly random permutation on all users' data before sending to the central servers (Tenenbaum et al. [2021] Garcelon et al. 2022 Chowdhury and Zhou| 2022] In this paper, we focus on c-pure DP, under global trust model, in stochastic finite-armed bandits, with the aim of regret minimisation.
Related Works. This problem setting has been studied by Mishra and Thakurta (2015), Sajed and
Sheffei 2019). Hu al. [202]] Azize and Basu [2022), Hu and Hegde [2022]. All the regret upper and lower bounds in this setting are summarised in Table 1 DP-UCB [Mishra and Thakurta 2015
was the first DP version of the Upper Confidence Bound (UCB) algorithm [Auer et al. 2002 that
achieved logarithmic regret. DP-UCB uses the tree-based mechanism (Dwork et al. 2010 Chan
al.] [201T] to compute privately the sum of rewards. For each arm, the tree mechanism maintains a binary tree of depth log(T") over the T streaming reward observations. As a result, the noise added
to the sum of rewards has a scale of O (log2*(TT)/ (T) for rewards in [0, 1]. DP-UCB builds a high probability upper bound on the means using the noisy sum of rewards to design a private UCB index
and yields regret bound of O (Ea log(T))
A. + K 1og (T)/c). where A. is the difference between
the mean reward of an optimal arm and arm a. This upper bound has an additional log..5((2 factor compared to the Q K log(T") /e) regret lower bound, first proved by Shariff and Sheffet 20018).
DP-SE [Sajed and Sheffel 2019 was the first DP bandit algorithm to eliminate the additional multiplicative factor log" 1.5 ( in the regret. DP-SE is DP version of the Successive Elimination algorithm [Even-Dar et al. 2002). DP-SE runs in independent episodes. At each episode, the algorithm explores set of active arms uniformly. At the end of an episode, DP-SE eliminates provably sub-optimal arms, but only uses the samples collected at the current episode to decide the arms to eliminate. Due the addition of the Laplace noise to the sum of rewards, each arm is explored longer, resulting in the additional O (K log(T")/e)
e) in the regret.
A careful reading of DP-SE suggests that running the algorithm in independent episodes while forget- log.. (TT) in the regret. These ingredients, i.c., running in
ting the previous samples shreds the extra log"
2

---

Table 1: A summary of regret upper and lower bounds for e-global DP bandits.
Regret Upper Bound
Regret Lower Bound
Mishra and Thakurta 2015
log(r)a
Eaya- + -usta
log(2)
(DP-UCB)
As log(??
Sajed and Sheffet 2019
K lngel?
(DP-SE)
Ω
K (og(T))
Hu and Hegde 2022
0
Zuza"
min( (
A, log(()
(Lazy- (izyy-D-TSS)
Azize Basu
2022
A. (Tg(T)
(AdaP-UCB)
A. log(T)
aaza
min(A] ....
min(ki(Ha ( )ed.
Our results
Au log(T)
(Thm.
Va >
Exgar delpo.p")
Au log(T) (Thm.
independent phases with forgetting and adding Laplace noise, have been further adapted to UCB
ct al. 2022]] Azzie and Basu 2022), Wu et al. [2023] and to Thompson Sampling in Hu and Hegde
ba.el e}). Similarly, Aomilarly,AAue Azize and Basu 2022 use the same three components of doubling, forgetting, and Laplace mechanism to Ci(r) propose AdaP-KLUCB that achieves regret uppe bound of mil(kll ),C,,,,) log(T)) for
[2022] The state-of-the art regret upper bound is thus O (C. (T)(T)) min (A.:
Though the regret of AdaP-KLUCB is order-optimal, we observe that C1(T) (T) and C2 are not universal constants, i.e., may depend the environment.
On the other hand. Azize and Basu 2022] improve the problem-dependent regret lower bound of Shariff and Sheffet [2018] to E. log(T) (etra) Here, da is the Kullback-Leibler (KL.)
indistingussability gap for arm a characterising the hardness of non-private bandits (Lai and Robbins 1985]. and to is "Total Variation" (TV) version of de characterising the hardness of private bandits. For Bernoulli bandits, tn = A. and d, = kl(Ha. (=*). Under the approximation da A the lower bound of Azize and Basu 2002 recovers that of Shariff and Sheffet [0088. and the regret upper bounds of Sajed and Sheffet 2019). Azize and Basu [2022). Hu and Hegde [2022) match approximately the lower bound. However, this approximation
be arbitrarily bad, exposing gap
between the state-of the upper and lower bounds in DP bandits. This motivates us to ask:
Q1. Can we derive matching regret upper and lower bounds up to the same constant for e-global DP bandits?
Additionally, following the triumph of doubling and forgetting as an algorithmic blueprint in DP bandits, Hu et al. [02T] conjectured that forgetting is necessary for designing any e-global DP bandit algorithm with an optimal regret upper bound matching the lower bound. Thus, we wonder:
Q2. Is it possible design optimal e-global DP bandit algorithm without applying forgetting?
Aim and Contributions. To address these questions, we revisit regret minimisation for Bernoulli bandits under c-global DP. Our main goal is to provide matching regret upper and lower bounds up to the same constant. Answering this question leads to the following contributions:
Tighter regret lower bound: In Theorem I we provide new asymptotic regret lower bound for any consistent e-global DP policy. This result is a strict improvement over the lower bound of Azize and Basu 2022) for all e. This lower bound depends on a new ixformation-theorett quantity d, (Eq. (6) interpolating smoothly between KI. and TVV depending on e. This quantity also indicates smooth transition between high and low privacy regimes, where the impact DP does and does not appear, respectively. In addition to the existing techniques, of environment idea to couple the impacts of DP and bandit feedback (Lemma I
proof applies new "double change"
2. Tighter concentration inequality: In Proposition| I we provide DP version of Chernoff-style concentration bound for sum of Bernoullis with added Laplace noise. d, naturally appears in this bound. Also, the bound suggests that as long as the number of summed Laplace noise is negligible compared to the number of summed Bernoullis, the effect of the noise comparable to having one Laplace noise in the dominant term of the bound. This bound is universally interesting for DP literature as the concentrations of random variables and Laplace noises are commonly treated separately unlike the coupled treatment in Proposition
3

---

3. Algorithm design and tighter regret upper bounds: Based on the concentration bound of Proposi-
tion I we modify the generic blueprint used by (Sajed and Sheffet (2019) Azize and Basu [022]. Hu
and Hegde 2022]. We (a) get rid of "reward-forgettnn
and thus sum all rewards at each phase, and
(b) develop new private indexes using de- We also run the algorithms in geometrically increasing arm-dependent batches, with ratio a' > 1. We instantiate these modifications for two algorithms that achieve constant optimal regrets withour privacy, i.e., KL-UCB and IMED, to propose DP-K DP-KLUCB and DP-IMED (Algorithm D. We analyse the regret of both algorithms (Theorem 2 and show that their regret upper bounds match asymptotically the regret lower bound of Theorem T up to the constant a, which can be set arbitrarily close to 1, for all bandit instances and values of
We also validate experimentally that our algorithms DM-IMED and DP-KLUCB achieve the lowest regret among DP bandit algorithms in the literature. Finally, in Appendix B we extend the adaptive continual release model of Jain et al. [2023] to bandits and show that this definition is equivalent to the classic e-global DP notion adopted in the DP bandit literature [Mishra and Thakurta
2015 Azize
and Basu 2022 2024]. This result can be of independent interest.
Background: Regret Minimisation and Differential Privacy in Bandits
In this section, we formalise the essential components of our work, i.e., the stochastic bandit problem, regret minimisation as a utility measure, and Differential Privacy (DP) as the privacy constraint.
Stochastic Bandits. stochastic bandit problem is a sequential game between a policy x and a
stochastic environment [Thomsoon I933 Lai and Robbins 1985 The game is played over T rounds, where T E 21, J is a natural number called the horizon. At each step & E (1..... 7). the policy chooses an action a₂ E [K]. The stochastic environment, which is a collection of distributions v & (Pa E [K]), samples reward ri Pa. and reveals it to the policy The interaction between the policy and environment _ (Pa E [K]) over T steps induces a probability measure on the sequence of outcomes H7 A (a1, (22 72, , (T,TT) rT). Let each WT,
Pa be probability measure on (R. B(RR) with B being the Borel set. For each & E [T], let 0 = =[K]] x R) C B2t and F, = B(L)). First, we formalise the definition of policy.
Definition 1 (Policy). A policy is sequence (mT)T= where Te is probability kernel from Fi) to ( 2.). Since [K] is discrete, we adopt the convention that for E [K), Te(a 01,71,..... 1, 1)) = x<({a}
The interaction probability measure on conditional distribution of action a given @1 T1......... 02-1, T:-1 is π ((a Ht-1), and (b) the condi- tional distribution of reward r, given 01, 71. ................................ It- is Pa.- To construct the probability measure, let À be f-nitte measure on (R, B(R)) ) for which Pa is absolutely continuous with respect to A for all a e [K]. Let Pa dPa/ /PP/dd be the RikondNi derivative of Pa with respect to A. Letting be the counting measure with p(B) = [B), the density Pur 2r - R can now be defined with respect to the product measure (p x \) by
depends on the environment and the policy: (a) the
T
Pur (a1, T1, OT, T
II 1=1
(e(a Ti,........ 14-1,11--1100 (ri)
and PPrr (B) & S Pun (p x X) (dw) for all E Fr. So (QT, Fr, Pvr) ) is a probability space over histories induced by the interaction between and v.
Regret minimisation. We study regret minimisation as the utility measure Lai and Robbins 1985 Informally, the regret of policy is the deficit suffered by the learner relative to the optimal policy which knows the environment and always plays the optimal arm. Let v = (Pa : a E [K]) a bandit instance and define (a( = f x dP((r) the mean of arm a's reward distribution. We assume throughout that (a(v)) exists and is finite for all actions. Let / (v) = max Ha(v) the largest mean among all the arms. The regret of policy π on bandit instance //
T
K
Regy 2 Tu² (v) EvT
Σ
rt
=
A EE [Na(
(2)

---

Li= where (T) & Ei= 1 fa = a and (a(2) _ (²(v) (v)))Ha(z)) The expectation is taken with respect to the probability measure Por on action-reward sequences induced by the interaction of and v. Hereafter, we drop the dependence on y when the context is clear.
For many classes of bandits, it is possible to define notion of instance-dependers optimality that characterises the hardness of regret minimisation. Specifically, for any consistent policy over
class of bandits & - MM x ... MM, i.e., policy Iecos(() verifies limy = Th for all V E E and all p > 0, then the regret of π on any environment v E E is lower bounded by
Reky 0
lim inf (T. T-000
(v(v)
Tog(T)
(M)20 KTint KTint(Pa,,ee (Pa, Ma)
where (P, (M) & PM (KI(P,, P'): :: (p())) > n²), and KL is the Kullback-Leibler divergence, i.e,, for two probability distributions P. on (22, F). the KI. divergence is KT,(P, Q) -
aq (w) dP(w) when < Q, and too otherwise. The lower bound of Equation (3) is tight for many classes of bandits, and the "KL-inf" is fundamental quantity that characterises the complexity of regret minimisation bandits.
flog
Bernoulli bandits. A Bernoulli bandit is stochastic environment where the distribution of each arm follows a Bernoulli distribution. Let μ E [0, 1]K then v (Beroouli((aa) : E [K]) is a
Bernoulli enviromment. For Bernoulli bandits, KLint (Pa. P.. 1r" MMa) ki(Ha. where kl is the
relative entropy between Bernoullis, ie., kl(p. q) _ plog(p/q) + (1 p) log((1 - (1 4)) for p,4 E [0, 1] and singularities are defined by taking limits. Using the "optimism in the face of uncertainty" principle, it is possible to design algorithms tailored for Bernoulli bandits, such as
KL-UCB Cappéé al. 2013 or IMED (Honda and Takemura 2015). that achieve the lower bound of EEquation (3) asymptoticalyy y, up to the same constant.
Differential Privacy (DP). DP [workk and Roth 2014) guarantees that any sequence of algorithm outputs "essentially" equally likely to occur, regardless of the presence or absence of any individual. The probabilities are taken over random choices made by the algorithm, and "essentially" is captured by closeness parameters that we call privacy budgets. Formally, DP is a constraint on the class of mechanisms, where mechanism M is a randomised algorithm that takes input dataset Mp- The probability space is over the coin flips of the
D (#1,..., .TT} E XT and outputs mechanism M. Given some event E in the output space F), note MD (E) & M(E(D) the probability of observing the event E given that the input of the mechanism D.
Definition (e-DP Dwork al. 20061). A mechanism M satisfies e-DP for a given e 2 0, if
YD ~ D', VE VE Mo(E) S (M)
(4)
where D ~ D' if and only if d (D, DD ΣT (D + DJ} s i.e. D and D' differ by at most one record, and are said to be neighbouring datasets.
DP widely adopted as privacy framework since the definition enjoys different interesting prop- erties, and can be achieved by combining simple basic mechanisms. Hereafter, we mainly use two important DP properties: post- post-processing (Proposition 4 and group privacy (Proposition 5 and we use the Laplace mechanism (Theorem 5) to achieve DP.
Bandits under DP. We extend DP to bandits by reducing a policy x = ( #T) to "batch" mechanism M (Azize and Basu 2024]. Different ways of reducing policy to batch mechanism differ on the input representation and the nature of the mechanism.
(a) In Table DP, we represent each user de by the vector xe & (2t,1...., Ft,K) RK of all its K "potential rewards." " This is the vector of potential rewards since the policy only observes T, 2 Dr,a, when it recommends action a, In Table DP, the induced "batch" mechanism M from the policy takes as input table of rewards x è (er E (R:K)² and outputs a sequence of actions
a A (a...... ar) E [K]T with probability M & I My (aela1, .i.a.... at-1 21-1,a._) This is the probability of observing (a1, ... .rr when a interacts with the table of rewards x. M distribution over sequences of actions since EaE M (5((()) (a) 1.
5

---

(b) In View DP, the induced "batch" mechanism from the policy т takes input list of rewards and ouiputs sequence of actions. The difference in the representation the imput dataset. Since in bandits, the policy only observes the reward corresponding to the action chosen, another natural choice for the input is a list of rewards, i.e,, _ {ri..... .r......,)........ E IR.". Now, the induced "batch" mechanism ya from the policy takes as input list of rewards (ri..... (T) E R²" and outputs sequence of actions a - (ai,...,, ".r)))..rr)).. E [K]", with probability V (a) & II Tr (azla), rl..... ac- Jr-1)) This is the probability of observing a when т interacts with r. V is a distribution over sequences of actions, since Eac(KTr 1/7 (a) 1.
Definition (Table DP and View DP [Azize and Basu 2024 ). (a) A policy x satisfies e-Table DP if and only if M is e-DP. (b) policy salisfies e-View DP if and only if V e-D..
Table DP and View DP have been formalised in [Azize and Basu interchangeably in the private bandit literature. For e-pure, Proposition 1 in Azize and Basu [024] shows that these two definitions are equivalent.
2024 and have been used
Thus, we refer to any policy that verifies e- Table DP or e-View DP as e-global DP policy. In Appendix B we also extend the interactive DP definition of of et al. [2023] to bandits and show that c-global DP is equivalent to it. In the following, main goal is to design c-global DP policy that minimises the regret Reg- (T, v/) on any Bernoulli environment v.
3 Regret Lower Bound under c-global DP
In this section, we present new regret lower bound for bandits under e-global DP. We compare this result to the lower bound of Azize and Basu [2022), and provide a proof.
Theorem (Regret lower bound under e-global DP). For every e-global DP consistent policy over the class of Bernoulli bandits, we have
Regr [T, v) log(T)
lim inf T-2
(5)
de (Maa)M))
a: 20
where
dr
inf ze zv(z)g,)V))
{e lz - x1 kl(2,))3 x E.R, [0,
(6)
For any suboptimal arm a, n²* > pa and de(Ma, inf infwelmnn felp - pa) + kl( p ).
Implications of Theorem 1 (a) Theorem improves the lower bound of Azize and Basu 2022
Specifically, Theorem 3 in Azize and Basu [2022] gives a lower bound
(T, v) lTg(T)
Aa 1²) GEDa)
lim inf 7-000
Σ
Theorem Dis is a strict improvement on the lower bound of Azize and Basu 2022 since d, (po: fe*) S min [Ll[[l((/a Ma, ,,), eAw} I min ,()), Ge for any Mo and n²"
(b) Solving the constrained optimisation problem defining de for Bernoulli variables gives
kl k²) if 2 log f2
1 -
+ log
Pha
1 11* 11* (1 je Mo
de(Mas((")
(8)
14 11 + (1
11a
kl
1et Dee 10*
if not
This suggests the existence of two privacy regimes: a low privacy regime when e 2 log ":, + +log t- and a high privacy regime when S log 8" + log I-p- the low privacy regime, de (H μ²) just Me reduces to the non-private kl (Jay ),,, and privacy can be achieved for free. In the high privacy regime, (Ha, 4²) can be written as the sum of two terms, i.e., KL term between Bernoullis with p² means (r+((=a=)e jes and j², and TV distance between Bernoullis with means +1+ )ae and Pa- At the limit, we have that de (pos R²) ~e-+0 X A..

---

(c) Theorem I can be generalised beyond Bernoulli bandits: for a class & of unstructured stochastic
bandits, ie.. E M1 x .... x MMx, the lower bound becomes
liming inf Reg log(T)
A
Σ
(9)
7-000
dart (Par ft, Ma. c)"
a:d.30
where dint (Pas H², Ma: c) a inf {d (dM P`) p(P)) > )²} and
dm (Pa PT) - inf (cTV(Pa. KL P') ): (Pa)) S w(Q) - m(P)))
QEM,
for Pa: P' M, such that ((Pa) S p(P)).
Key Changes in Proof Techniques. by introducing "double" change of environment. (a) The first change environment uses the group privacy property of the policy, and thus the TV transport. (b) The second change uses the classic "Lai-Robbins change of measure and thus the KL transport. By optimising for the "in-between" environment, the double change always has smaller transport than any route led by purely KL or TV transport. The detailed proof is in Appendix C
The proof improves the lower bound of AflAzize and Basu [022
Algorithm Design and Regret Analysis
In this section, we propose two algorithms, DP-KLUCB and DP-IMED, presented in Algorithm ] At the core of our algorithm design lies a new concentration bound for c-DP means of Bernoulli variables (Proposition [). We analyse both the privacy and regret of our proposed algorithms, and show that their regret upper bound matches the lower bound up to a constant arbitrary close to
First, we start with the concentration inequality for the private mean of IID Bernoullis.
Proposition (Concentration Bound of Private Mean). For μa (0, 1) and > 0, let Sn,m ET X; + m Y, where X; Ber(u) and Yj ~ Lap(1/e), be the sum of n independent Bernoulli random variables with mean I and m independent Laplace variables with scale l/c. Let E [0, 1] and (n Jey be sequence such that m nm o(1). Then, for any a >> 0 there exists constant Ag such that for all E N.
8am.
S
S 5m
Pr
S A.ee Pm. for x S us
S -
n (m for H.
nm
nm
We recall that (æ, v) inf sefselang. kl(z, v) + E|zz x/l.
private version of the Chernoff bound (Lemma [T.. where d, replaces the kl in the exponent. (b) As soon as the number of summed I Laplace noises is negligible with respect the number of summed Bernoulli variables n, then the effect of m on the dominant term is similar to when m = 1. (c) This concentration bound is a tighter version
Discussions. (a) This concentration bound can be
Lemma 4 of Azize and Basu 2022 and other works in bandits under DP [Mshhaa and Thakurta 2015 Sajed and Sheftet 2019 Hu et al. 2021 Hu and Hegde 2022] deal with the concentration of the noise and random variables separately- they use an inequality Pr(X + Y 2 a) < Pr(X 2 a) + Pr(Y 2 0). followed by classic non con-private concentration bound for the first term and concentration bound of Laplace noise for the second term.
of Lemma- in Azize and Basu [0222] with
We improve this loose analysis by coupled treatment of noise and variables.
Proposition D corollary of the general Lemma that holds for any n and m. To prove Lemma we express Pr $..m 2 in the form of convolution of the sums of Bernoulli rewards and Laplace noises. Even though we still resort to the Chernoff bound for each of the sums, considering the convolution of sums significantly improves the bound compared with the naïve use of the Chernoff bounds for noise and variables in Sp,m. The complete proof is in Appendix D
Proof Sketch.
Algorithm Design. Based on Proposition [ we propose DP-KLUCB and DP-IMED in Algorithm
Both algorithms run in arm-dependent phases (Line 9 in Algorithm [T. and add Laplace noise to achieve e-global DP (Line 10 Algorithm [Tp. This similar the algorithm design (Sajed and Azize and Basu 2022 Hu and Hegde 20022) with two modifications.
Sheffet 2019
7

---

Algorithm 1: DP-KLUCB and DP-IMED
Input: E: privacy parameter, K: number of arms, T: horizon, {Bm 1 mm=oi batch sizes Pull each arm Bo times and receive rewards { )==
Compute private reward sum S1,0 En= Xi, + Y1,0 for Y2,0 Lap(1/e);
Compute private mean fı,o S Bu:
4 Set arm- arm-dependent epoch my == 0 for each arm i E [K];
5 Set cumulative pull number 74m; == Bo for each arm i E [K]; Set & <- K BBo
7 while & S T do
(DP-KLUCB); compute i(t) E arg max; (t(() maximising the DP-KLUCB index given by
(t) = max { (: de (Iimm.las (2) S
logt
(10)
Tbm;
(DP-IMED): compute i(t) E arg min, 4(t) minimising the DP-IMED index given by
[,()) = nm,de (lūs,m (ā (0])) + log mmp
(11)
where jē" (1) = maxx Pj.m; and [x:]]] = ma min ( 1}} is the clipping of x onto [0, 1]:
mmssee) Bmuge) +1
Pull arm i(1) for Bm times and receive rewards { (Xi(0,m)n=mmm +1
Pomae)) Bmagt
10
Update the noisy sum 5:00 + 5:(0)mao + =m==mau> +1 where ma0 ~ Lap(1/e);
X + Ya(0)
11
Compute private mean (=a00),aa)+11 Suc, u/
12
Update ma(e) +- m4(1) + 1, Amm,(t) < Ama.n + Bumayy & t- t + Bm,(t);
13
end
(a) Our algorithms do not forget rewards from previous phases. In contrast, the algorithms of Sajed and Sheffet [2019), [Azize and Basu [2022] Hu and Hegde [2022] run in adaptive and "non- overlapping" phases. The sums of rewards are computed over non-overlapping sequences. Thus, the rewards collected in the past phases are "thrown away" in the future phases. By running non- overlapping phases, these algorithms avoid the use of sequential composition (Proposition 66, and use instead the "parallel composition" property (Lemma T0) of DP to add less noise. Specifically, if the rewards in [0, 1]. forgetting ensures that adding one Lap (1/e) to each sum of rewards is enough to make the simultancous release of all the partial sums achieving DP. In our algorithms, we do not forget previous private sums (Line 10 in Algorithm []]. The price of not forgetting adding multiple Laplace noises with scale 1/fe to the non non-private sum. To overcome this price, we use the insights from the concentration inequality of Proposition T ie.,, as long as the number of added Laplace noises is negligible with respect to the number of Bernoulli variables, the effect of the added noise on the dominant term is similar to having one Laplace noise. This refined analysis removes forgetting.
(b) Our algorithms use new indexes, i.e. Eq. 10] and Eq. (TT). inspired by Proposition []] and are based the de quantity appearing in the lower bound. In addition, the index of DP-KLUCB is instantiated with an exploration bonus of log(l)/ (g())//mss This contrasts AdaP-KLUCB and Lazy-DP-TS, which need an exploration bonus of roughly 3 log(t)/nn,, needed for their regret analysis.
Now, we present the privacy guarantee of our algorithms.
Proposition 2 (Privacy analysis). DP-KLUCB and DP-IMED are c-global DP for rewards in [0, 1].
Proof Sketch. First, given a sequence of rewards fri....,rrh) .r) E [0 and some time steps 1= 11 < 12 <.. 4 T + 1, releasing the partial sums
{-1 k=1 is eDP, where Y& Lap(1/e). This is the main privacy lemma used design DP bandit algorithms in prior work [Sajed and Sheffet 2019 Azize and Basu 2022 Hu and Hegde 2022] Now, by the post-
( 1ha+11 Ts + Yv
(Eh Ts Σラ= Y k=
processing property of DP, we also have that releasing the sums
is c-DP, by summing the outputs of the previous DP mechanism. Finally, DP-IMED and DP-KLUCE

---

are e-global DP by adaptive post-processing of the sum of rewards. The detailed proof is presented in Appendix
To have a "good" regret bound. Proposition suggests using a batching strategy where the number of batches is sublinear in T. For simplicity, we chose the batch sizes Bm in Algorithm | such that Bm 2 nga" i.e., a geometric sequence with initialisation no E N and ratio a > 1. Thus, we take
Bm
RO
70
(12)
a
where [a] is the smallest integer no less than r. When is an integer, Bm noa" Theorem 2 (Regret upper bound of DP-IMED and DP-KLUCB), Assume μ- < 1. Under the batch
sizes given in Equation 12 with a > 1, and for any Bernoulii bandit v, we have
ad, log de(Hi.
v) - Σ
+ o(log
171
S ad, log T de de(pi, u*)) ollog
Reg (DP-KLUCB,
Comments. (a) The regret upper bounds of DP-IMED and DP-KLUCB match asymptotically the lower bound of Theorem [ up the constant a 1, where a is the ratio of the georemetrically increasing batch sizes Bm- This parameter & > 1 can be set arbitrarily close to 1 to match the dominant term in the asymptotic regret lower bound. In addition, our analysis only requires that the number of batches is sublinear in T", as seen from Proposition [ As result, we can also use polynomially increasing batch size instead of Bm s a." which fully makes the regret asymptotically optimal. We used a geometrically increasing batch size here just for simplicity. (b) Our algorithms strictly improve over the regret upper bounds of [Azize and Basu 2022), Hu and Hegde (202)).
Also, our upper bounds are the first to show a dependence in the tighter quantity d,, compared to
having min { A <A,} } in the regrets for Azize and Basu 2022]. J Hu and Hegde [2022] We provide additional comments that compare our regret upper bound to that of AdaP-KLUCB in Appendix F
Proof Sketch. The proof uses similar steps as those of Honda and Takemura 2015 for the IMED
algorithm and the reduction technique for the KL-UCB algorithm by Honda 2019 with the new concentration inequality involving d, (Proposition I.. The main technical challenge dealing with the adaptive batching strategy in the analysis. We control this by a regret decomposition tailored for batched pulls of arms where the property of IMED/KL-UCB index can still be naturally incorporated. The full proof is presented in Appendix
Beyond Bernoulli Bandits. First, we highlight that some of our results are already valid beyond Bernoulli bandit instances: (a) As explained in the Implications of Theorem T our regret lower bound is already true for any class of distributions.
(b) As expressed in Proposition] 2 our algorithms are already e-DP for any distribution with bounded support on [0, 1]. This could easily be generalised to any bounded rewards on [a, b) by multiplying the noise terms with the range (b (b-a). On the other hand, the parts only valid for Bernoullis are: the concentration inequality (Proposition[] IT and the regret upper bounds (Theorem 2) It is also worth noting that the same regret upper bound of Theorem is also valid for distributions over [0, 1), since we only used the Chernoff bound for Bernoulli distributions, which is also valid for distributions over [0, 1]. Both the concentration inequality and regret upper bound can be extended beyond Bernoullis, to say sub-Gaussian distributions or exponential families. However, what less clear is whether is possible get matching upper and lower bounds up to constants, like we achieve in the Bernoulli case. This represents an interesting open direction to explore. The following takeaways from our analysis can be helpful achieve that goal: (a) d, is the information- -ooommtiion--hooettic quantity that tightly characterises the hardness of bandits with DP, (b) forgetting is not a fundamental design choice, and (c) it is important to have a coupled treatment of the signal and the noise to achieve tight concentration bounds, which are the building block for algorithm design.
5 Experimental Analysis
In this section, we numerically compare the performance of our algorithms, iee., DP-KLUCB and DP-IMED, to e-global DP algorithms from the literature: DP-SE [Sajed and Sheffet 2019 AdaP-

---

10a
101
10a
10a
Regret
Regret
107
10
DP
10a
DP-SE
AdaP-KLUCB
AdaP-KLUCB
10a
Lazy-DPTS
Lazy-DPTTS
DP-KL-UB
10c
DP-KL-UB
DP-MEED
DRIMED
IMED
IMED
10-2
0.4
1.0
0.8
Step t
1e6
Step
1e6
Figure I: Evolution of the regret (mean 22 std) over time for DP-SE, AdaP-KLUCB, Lazy-DP-TS, DP-KLUCB, and DP-IMED for e = 0.25, and Bernoulli bandits μl (left) and μ2 (right).
KLUCB [Azize and Basu 2022 and Lazy-DP-TS (Hu and Hegde 2022 As non-private benchmark, we include the IMED algorithm [Honda and Takemura 2015]. Since both AdaP-KLUCB and Lazy- chose no 1 and
DP-TS explore each once, and arm-dependent doubling,
2 for
DP-KLUCB and DP-IMED. Also, to comply with the regret analysis in [Azize and Basu 2022 Sajed
and Sheffet 2019]. chose 3.1 in
and B 1/T in DP.SE.
Setup. As Sajed and Sheffet 2019 Azize and Basu 2022 and Hegde [022] we consider different 5-arm Bernoulli environments, with specific arm-means choices. We run each algorithm 100
times for T = 10 For 0.25, we plot the mean regret in Figure 1 f [0.75, 0.7, 0.7, 0.7. 0.7]
in the left and μl2 A 70, 0.625, 0.5, 0.375, 0.25] in the right. In Appendix G we present additional
results for some other environments under different budgets.
Results. DP-KLUCB and DP-IMED achieve lower regret for all Bernoulli environments and privacy budgets under study (up 10 times less on an average). This is explained by the fact that DP-KLUCB and DP-IMED do not forget half of the samples, and also thanks to their tighter d based indexes.
Discussions and Future Works
We improve both regret lower bound (Theorem 1 and upper bounds (Theorem 2 for Bernoulli bandits under c-global DP. We introduce a new information-theereti quantity d, (Equation (6) that tightly characterises the hardness of minimising regret under DP,, and smoothly interpolates between the KL and the TV. Our proposed algorithms share ingredients with algorithms from the literature while alleviating the need forget rewards concentration inequality for private means of Bernoullis (Proposition [ Our results solve the open problem of having matching upper and lower bound up the same constant posed by Azize and Basu 2022 and refute that forgetting is necessary for designing optimal DP bandit algorithms.
design technique. This is thanks to a new tighter
An interesting future work would be to generalise concentration inequality, and in turn, the regret upper bounds to general distribution families (e.g. sub-Gaussians, exponential families).
Acknowledgments and Disclosure of Funding
PAD A. Azize thanks the support of the FairPlay Joint Team and THIA ANR program "AI PhD@Lille Lille.. J. Honda was supported by JSPS KAKENHI Grant Number JP25K03184. A. Azize, J. Honda, and Basu acknowledge the Inria-Kyoto University Associate Team "RELIANT" for supporting the project. D. Basu acknowledges the supports of ANR JCJC project REPUBLIC (ANR-22-CE23-0003--)) and PEPR project FOUNDRY (ANR23-PELA-000))
References
Naman Agarwal and Karan Singh. The price of differential privacy online learning. In Interna- tional Conference Machine Learning, pages 32-40. PMLR, 2017.
10

---

Peter Auer, Nicolo problem. Machine learning, 47(2-3):235-2555 2002.
and Paul Fischer. Finite-time analysis of the multiarmed bandit
Achraf Azize and Debabrota Basu. When privacy meets partial information: A refined analysis of differentially private bandits. Advances in Neural Information Processing Systems, 35:32199- 32210, 2022.
Achraf Azize and Debabrota Basu. Concentrated differential privacy for bandits. In 2nd IEEE Conference on Secure and Trustworthy Machine Learning, 2024.
Achraf Azize, Marc Jourdan, Aymen Al Marjani, and Debabrota Basu. On the complexity of differ- entially private best-arm identification with fixed confidence. arXiv preprint urXiv:2309.02202 2023.
Achraf Azize, Mare Jourdan, Aymen AI Marjani, and Debabrota Basu. Differentially private best-arm identification. arXiv preprini arXXiv2246.066400 2024.
Debabrota Basu, Christos Dimitrakakis, and Aristide Tossou. Differential privacy for multi-armed bandits: What is it and what is its cost? arXiv preprint arXiv: 2019.
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208-240. Springer, 2003.
O. Cappé, A. Garivier, O.-A. Maillard, R. Munos, and G. Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 1163):111--1141, 2013.
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur. 14(3), nov 2011. ISSN 1094-9224. doi: 10.1144520436221224436666 URL https://doi: org/10. 10. 1145/204362
2043626
Shouyuan Chen, Tian Lin, Irwin King, Michael Lyu, and Wei Chen. Combinatorial pure exploration of multi-armed bandits. Advances in neural information processing systems, 27, 2014.
Zhirui Chen, P. N. Karthik, Yeow Meng Chee, and Vincent F. Tan. Fixed-budget differentially private best arm identification. arXiv preprint MXXiv:2401.09073 2024.
Sayak Ray Chowdhury and Xingyu Zhou. Shuffle private linear contextual bandits. arXiv preprint arXiv:2202.05567, 2022.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-40) 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Proceedings of the Third Conference on Theory of Cryptography, TCC*06, pages 265-284, Berlin, Heidelberg, 2006. Springer- Verlag..
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In ACM Symposium on Theory of Computing, STOC '0, page 715-724, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781450300506.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC bounds for multi-armed bandit and Markov decision processes. Conference on Computational Learning Theory, COLT '02, page 255-270. Berlin, Heidelberg, 2002. Seringer-Verlage ISBN 354043836X.
Evrard Garcelon, Kamalika Chaudhuri, Vianney Perchet, and Matteo Pirotta. Privacy amplification via shuffling for linear contextual bandits. In International Conference on Algorithmic Learning Theory, pages 381-407 PMLR, 2022.
Yuxuan Han, Zhipeng Liang, Yang Wang, and Jiheng Zhang. Generalized linear bandits with local differential privacy. Advances in Neural Information Processing Systems, 34:26511-266 2021.
Osama Hanna, Antonious M Girgis, Christina Fragouli, and Suhas Diggavi. Differentially private stochastic linear bandits: (almost) for free. arXiv preprint 220.::2200.04445. 2022.
11

---

Junya Honda. A note on KL-UCB+ policy for the stochastic bandit. arXiv preprint arXiv: 2019.
Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Mach. Learn. Res., 16:3721-3756, 2015.
Bingshan Hu and Nidhi Hegde. Near-optimal Thompson sampling- based algorithms for differentially private stochastic bandits. In Uncertainty in Artificial Intelligence, pages 844-852. PMLR, 2022.
Bingshan Hu, Zhiming Huang, and Nishant A. Mehta. Optimal algorithms for private online learning in stochastic environment, 2021. URL htttts:///arittt org/ org/abs// /202. 07929.
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. International Conference on Machine Learning, pages 14654-14678, PMLR, 2023.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1383 1385. PMLR, 2015.
Cyrille Kone, Emilie Kaufmann, and Laura Richert. Adaptive algorithms for relaxed pareto set identification. Advances in Neural Information Processing Systems, 36:35190-35201, 2023.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematies, 6(1):4 22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Fengjiao Li, Xingyu Zhou, and Bo Ji. Differentially private linear bandits with partial distributed feedback. In 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt). pages 41-48. IEEE, 2022.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit- approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1):6765-6811 2017.
Pieter JK Libin, Timothy Verstraeten, Diederik M Roijers, Jelena Grujic, Kristof Theys, Philippe Lemey, and Ann Nowé. Bayesian best-arm identification for selecting influenzz mitigation strategies. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018, 2019.
Simon Lindstähl, Alexandre Proutiere, and Andreas Johnsson. Measurement- admission control in sliced networks: A best arm identification approach. GLOBECOM 2022- 2022-0022 IEEE Global Communications Conference, pages 1484-1490. IEEE, 2022.
David E Losada, David Elsweiler, Morgan Harvey, and Christoph Trattner. A day at the races: using best arm identification algorithms to reduce the cost of information retrieval user studies. Applied Intelligence, 52(5):5617-5632 2022.
Nikita Mishra and Abhradeep Thakurta. (Nearly) optimal differentially private stochastic multi-arm bandits. In Conference on Uncertainty Artificial Intelligence, 2015.
Alasdair PS Munro, Leila Janani, Victoria Corneliu,, Parvinder Aley, Gavin Babbage, David Baxter, Marcin Bula, Katrina Cathie, Krishna Chatterjee, Kate Dodd, et al. Safety and immunogenicity of seven covid-19 vaccines as a third dose (booster) following two doses of chadox ncov-19 or bnt162b2 in the uk (cov-boost): a blinded, multicentre, randomised, controlled, phase 2 trial. The Lancet, 398(10318))2258 2276, 2021.
Seth Neel and Aaron Roth. Mitigating bias in adaptive data gathering via differential privacy. In International Conference Machine Learning, pages 3720-3729, PMLR, 2018
Nikola Pavlovic, Sudeep Salgia, and Qing Zhao. Differentially private kemeliizdd contextual bandits. arXiv preprint arriv:2501.07000 2025.
Touqir Sajed and Sheffet. An optimal private stochastic-MAB algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pages 5579-5588. PMLR, 2019.
12

---

Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. In Advances in Neural Information Processing Systems, pages 4296-4306 2018.
Nícollas Silva, Heitor Werneck, Thiago Silva, Adriano CM Pereira, and Leonardo Rocha. Multi- armed bandits in recommendation systems: A survey of the state-of-the-art and future directions. Expert Systems with Applications, 197:116669, 2022.
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private multi- armed bandits in the shuffle model. Advances in Neural Information Processing Systems, 34: 24956-24967, 2021.
Abhradeep Guha Thakurta and Adam Smith. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances Neural Information Processing Systems, 26, 2013.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-2944 1933.
Aristide CY Tossou and Christos Dimitrakakis. Achieving privacy in the adversarial multi-ane multi-armed bandit. In Thirty-First First AAAI Conference Artificial Intelligence, 2017.
Siwei Wang and Jun Zhu. Optimal learning policies for differential privacy in multi-armed bandits. Journal of Machine Learning Research, 25(314):1-52 2024.
Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. On private and robust bandits. Advances in Neural Information Processing Systems, 36:34778 -37700, 2023.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. In Advances in Neural Information Processing Systems, volume 33, pages 12300-12310, 2020a.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. In Advances in Neural Information Processing Systems, volume 33, pages 12300-12310, 2020b.
Yuan Zhou, Xi Chen, and Jian Li. Optimal PAC multiple arm identification with applications to crowdsourcing. In International Conference Machine Learning, pages 217-225. PMLR, 2014.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claim is proving matching regret upper and lower bound for bandits under Differential Privacy. These claims accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of our work in Appendix H
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: All our theoretical results (Theorem Proposition 1 Proposition 2 and Theorem 3) contain the full set of assumptions needed. The proof sketches and intuitions are described in the main paper, while the detailed proofs are deferred to the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide a detailed pseudo-code of our main algorithm (Algorithm T that contains all the information needed implement the algorithm. Implementation details on our experiments are given in Section and Appendix G Also, the full code to reproduce our figures is provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
15

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide access the code as supplementary material. We also provide full instructions to generate our results. As our experiments are done synthetic data using simulated Bernoulli distributions, there is no dataset per se.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
wttpps.ccpubllc//uuiiece guwde// CodeeSumiia ssi onyolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All the experimental details are explained in Section
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All the figures reported in the paper report the empirical mean +2 stds over 100 runs of each algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix G specify the compute ressources needed for the experiments. As our algorithm straightforward to code, and the datasets consist of simulated Bernoulli instances, all the experiments could be reproduced using commercial laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/neurrpps http://pcccccccccccciiiieeeooeee
Answer: [Yes]
Justification: Yes, our paper conforms with the NeurlPS Code of Ethies
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
17

---

Our paper improves the state-of-the offthhe-n art theory results in Differentially Private Bandit algorithms. Our algorithms are shown to preserve privacy while maintaining great utility, this encouraging the use of such algorithms in real-word sensitive applications of bandits.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeett of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses such risk. Our proposed algorithms satisfy Differential Privacy, and are implemented only on simulated data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We do not use any existing assets. Our algorithms are implemented from scratch and are tested on synthetic Bernoulli data.
Guidelines:
18

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Our contributions, methods and idea do not involve the of LLMs at all.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non standardd components.
Please refer to our LLM policy for what should or should not be described.
20

---

A Outline
The appendices are organised follows:
In Appendix B extend the adaptive continual release model of Jain al. 2023 bandits, and link it to e-global DP.
In Appendix we provide the proof of the three lemmas used to prove the regret lower bound of Theorem and the proof of Theorem
Appendix tion[]
we provide the complete proof of the concentration inequality of Proposi-
In Appendix
we provide the complete proof of the privacy guarantee of Proposition
In Appendix
provide the complete proof of the regret upper bounds of Theorem
In Appendix
we provide additional experimental results.
Appendix we discuss some limitations of our work.
In Appendix recall useful lemmas used throughout the paper.
B Adaptive Continual Release Model for Bandits
In this section, we extend the adaptive continual release model of Jain et al. [2023] to bandits. In this model, the policy interacts with an adversary that chooses adaptively rewards based on previous outputs of the policy.
In the following, formalise the notion of an adaptive adversary from Jain al. 2023 and call it "reward-feeding" adversary.
Definition 4 -weard-Feeding Adversary). A reward-feeding adversary A is sequence of functions (A,)t= such that, for (1...., TT).
A : 11,0...,00 (rt,
A "reward-feeding" adversary .A is sequence of "reward" functions that take as input the action- history and outputs pair of rewards (r(.r.)). The reward-feeding adversary AA has two channels: left "standard" channel L and right channel R. These channels are used to simulate "neighbouring" rewards.
Precisely, to simulate "neighbouring" rewards, the interactive protocol between the policy π and the reward-feeding adversary has two hyper-parameters: (a) specific "challenge" time /* [1, T}, and (b) a binary b E (T., Rt). For steps 1 * 1,' the policy observes a reward coming from the adversary's left "standard" channel, i.c. Ft r Otherwise, when t*, the policy observes reward from the channel corresponding to the secret binary b.
In other words, if b L, the policy always observes reward from the left channel. When b = R. the policy observes the left channel reward for all steps, except at t* where the policy observes a right channel reward. Thus, for any sequence of actions (a1..... ar) chosen by the policy æ, and for any t", the sequence rewards observed by π when
L is neighbouring to the sequence of rewards observed when b R. In addition, these two sequences only differ the reward observed the challenge time 1a, and the rewards have been adaptively chosen by the adversary.
Thus, formalise the adaptive continual release interaction follows:
21

---

Let be E (I, R} and 1 E (I,...,T)
For = I....,T
The policy selects an action at (t(:
a E [K]
2. The adversary A selects an adaptively chosen pair of rewards:
(rt,r?) = A((e1....,
If + A
r1 rt
If =
Te- = r
3. The policy observes the reward T
When this interaction is run with parameters t* and b, represent the interaction by " illustrate it in Figure 2 The view of the adversary A the interaction 2 A is the sequence of actions chosen by the policy æ, i.e.
A, and
View A View A 44" A.=
A) a .o,....,TT).
policy is DP in the adaptive continual release model if the view the adversary is indistinguishable when the interaction run on b and R for any challenge step t*
Definition (DP in the Adaptive Continual Release Model).
A policy a is (D in the adaptive continual release model for given 2 and 8 E [0, 1), if for all reward-feeding adversaries A, all subset of views S C [K]
sup (E.......
Pr[Viee A.=
R.tt" A,5 E 8.
policy n is p-zCDP in the adaptive continual release model for a given p 2 0, for every a > 1, and every reward-feeding adversary A.
Da (Vieew A, |[View A, PEEI,...,TT
sup
S pa.
Remark 1. [Expanding the View of the Reward-feeding Adversary A] For any reward-feeding
adversary A, any policy and any 1 E (I,..., T), and any (0I....,TT) [K] have for the left view:
Pr(View
Ltt" Art = (a1,.... or)] = Tı (11 (T(())))((22)) 01 A (a1)) ..
कт( ai, (a1),
(a1), .... uT, A (al....,
On the other hand, for the right view:
Pr[View-R. R.t" A. (a aT)] क. (a1) an, A(1))
7 ai A (
Al .r)))...))))...
Zr(ar 01 Al (a)) ar- A (a1, ar11))
Let us define
AL. (ai....,ar) ar) 2
(a1, o2), (aa,......
to be the list of rewards that the policy observes when the protocol is run on the left channel. Also,
R.t (a1...., A (A) (u1,..., is the list of rewards that the policy observes when the protocol is run on the right channel and L*_ We observe that, for any (a1....,aT) [K]T.
Ali (a1....,uT))
22

---

r1
a1
A
π
1 x+)
aT
(r )
(a)b=L
r
A
π
(r
oT
(b)b= R
Figure 2: Interactive protocol in the adaptive continual release model between a policy π and reward-feeding adversary A. The protocol in Figure (a) is run with L. while the protocol in Figure (b) is run with b = L. The framed part corresponds to the reward observed by the policy.
(a) Pr[Vicw L,t" (a1, (a1...., or)] V* ((a1...... @T) ALT (a1...., ar)..
R,tt (b) Pr[View A.r. (aI...., ar Vaa ((a1,.... aT) AR. (a1....,aTT)
(c) ALi (ai,..., UT) and AR, (ai,.... .T) are neighbouring lists of rewards, and only differ at the 1 element.
This remark will help connect the adaptive continual release model with View DP later.
Remark 2. [Reward-feeding Adversary Tree Reward Input] A reward-fceding adversary can be represented by tree of rewards. Each node in the tree corresponds to a reward input. The tree has depth of size T. At depth [T] of the tree reside all possible rewards the policy observe step depth t to depth t + depends on the action a1+1- Finally, the policy only observes the reward corresponding its trujectory in the Iree. An example of the tree presented in Figure for T = and K
t. Going from from
A policy π is DP in the adaptive continual release model if and only if is DP when interacting with two neighbouring trees of rewards. Two trees of rewards are neighbouring if they only differ in rewards at one depth t* E [T].
Now, we relate DP in the adaptive continual release model with View DP and Table DP.
23

---

a1 = 1
d1
=
2
t=1 1
ビ= 1
a2 =
1
Q2
2
==2
t 2
r
03
= 1
0:3
2
= 3 r
t =
r
r
(a) List of rewards
(b) Table of rewards
1=1
2
2
1=
2
2
2
t=
P
(c) Tree rewards
Figure 3: Different reward representations for T = 3 and K = 2. The highlighted rewards are the rewards observed by the policy for the trajectory (a), a2 uz) = (1, (1,2,1)
Proposition 3 (Link between the Adaptive Continual Release Model, View DP, and Table DP). For any policy n, we have that
(a) æ DP in the adaptive continual release model = Table DP.
(b) æ is 6-DP in the adaptive continual release model + n is c-Table DP < a is 6- c-View DP.
Proposition shoows that the adaptive continual release model stronger than Table DP. For pure e-DP, the adaptive continual release model, Table DP and View DP all equivalent.
To prove this proposition, we use the following reduction.
Reduction (From table of rewards to "reward-feeding" adversaries). For pair of reward tables x,x' (RK)P, we define A(x,x") be the "reward-feeding adversary defined by
A(x,x"), ai,..., - (It,a, 2(.aa)
In other words, at step I, the adversary A(x,x* x') only uses the last action a, and returns the artth column from It the left channel, and the ac-th column from z' the right channel.
24

---

For neighbouring tables and x' which only differ at some step t", it is possible to show that, for every S RR,, we have
L.t" Pr[View A ES] M
. Pri[View R,t" A(xx²), =8|=MŞ(5)
In other words, the batch mechanism .M combined with neighbouring tables can be "simulated" using a specific type of "reward-feeding" adversaries that only care about the last action from the history.
Proof. (a) Suppose that æ DP the adaptive continual release model.
Let t" E T and ~ x' be two tables of rewards in (R*)7 that only differ at step t². Using Reduction we build A(x,r')
For this construction, we have that M View A(xx'), and M = View Rit" A(xx"),,
Since ग is DP the adaptive continual release model, View h,t" A(x,x"),r and View Lat A(x,'),= are indistin-
guishable. Thus, MI and M. are indistinguishable, i.e., MM is DP and i is Table DP.
(b) To prove this part, it is enough to show that e-View DP implies e-DP in the adaptive continual release model.
Suppose that is c- View DP, ve.v is c-DP. Let A be a "reward-feeding adversary, and (o1.....ar) [K]] a sequence of arms.
Using Remark 1 and the notation defined there, we have
Pr(Vicw A, = (a1..... ...,,ar)]] V ((a1..... ar) Abit (aI,...,ar))
S (Ca), aT) RR. (a), (al.....rr))
= Pr(Vewie
A.T L,t"
where the inequality holds because T is DP, and neighbouring lists of rewards.
Lt (a....., ar) and A (a (o1,..., ar)
Finally, this means that æ is c-DP in the adaptive continual release model, since for pure DP, it is enough to check the atomic events (a.....,a7) .T))
Note that the proof breaks we consider composite events, which are necessary for approximate DP proofs.
Summary of the relationship between definitions. We introduced three increasingly stronger input representations and their corresponding DP definitions: list of rewards with View DP, table rewards with Table DP, and tree of rewards with DP in the adaptive continual release. These representations are summarised in Figure 3 for T and K 2.
In general, DP in the adaptive continual release is stronger than Table DP, which is stronger than View DP. For e-pure DP, these three definitions are equivalent, with the same privacy budget More care is needed for other variants of DP, where going from one definition to another happens with a loss in the privacy budgets (Proposition 1 in Azize and Basu 2022
C Lower Bound Proof
In this section, we present the proof of the three main lemma used to prove Theorem | We adopt the same notation introduced in the proof of Theorem
Lemma (Controlling Pya (2 n L 0 A), aka Double change of environment). We show that
( (Lt.bu(((VV.. O(T*)
Pa (Ωn LO &
(13)
n2
for any >> 0.
25

---

Proof. We have
Pyr (Ω
T Σ -Σ (QNLN4)
II (as (1,........ "1:",...,,0011.. Pt (re,r) dr dr:
Σ/1 1(90L) A) chram((r))
me(ar
(ra, dr. drl
(
Σ
I.I. 1 ((90 II a aa.ry.....,,
T
(re, rf) dr, drl
T
Σ 1 II
me(at 01,
(re, r/) dr dr!
1 A) II (e(a @ TV /
1, r- (r))
and (r
Ei log
(V(P.)
1(22 A)e
ap
(a f,,,',....,,..................,. .............--......... r 1-- (r()
(6) @(
Σ / ((2) II (a an,r at -.-1, 1b,, (r+) dr)
T
(1V (N2(T) m2).
where:
(a) is because π c-DP:
(b) is by definition of L;
(c) is because ( < 1(2 A);
(d) by definition the coupling, and because Q A doesn't depend on (ri)-
(e) by definition of A.
Then, using Markov inequality and the consistency of R,, we get
PV"a (Na(T) S n2)) = Pi'x (T - N2(T) 2 T 122)
PU'T (N1 2 T 112) Exd (T))
(
T n2
T n2
for any a > 0, since arm is sub-optimal in environment v/ and æ is consistent. All in all, we have that, for any a > O,
Pa (ΩU (LTO O(Ta)
T 122
Lemma (Controlling IP (2n Choosing n22 = (2( a function such that (T - 00 when's T - then
Pyt ( or),
asymptotically in T.
Proof. First, have
Pay (QNL044) < Par (204) A4)
26

---

Let us introduce the notation r, _ r where Ta. - minft E N: Na(t) = s). Then,
T
dP (rt)
N2(T)
dP2(((2s)
Na(T)
log
Σ log
Σ W
dP
(1
where W, log (r2.) are iid bounded random variables, with positive mean [yr[Wa]]
kl(12; p?). This is true since under the coupling 7, the marginal of r2, is P2.
Then, get
M
Pyr (A) S Pyr
3m S 122
W. (1 + a0kl(1122 21))m2
S Pyr
maX S:12
- We
(1 + (1+ (()
112
Using Asymptotic maximal Hoeffding inequality (Lemma 12 we have that
max E W.
lim Pym 1-+20
(1 + aakl((u) (1)) = 0.
n
Thus, by choosing n2 = nz2 (T) a function such that (2( + 0o when T - oo, then
P*)( or or()),
asymptotically in T.
Lemma 3 (Controlling py5 (Ii L9)). choosing n22 (2( function such that n2 (T) - 00
when T + oc, then
Pyn (D) = or((),
asymptotically in T.
Proof. First, by the construction of the couplings, only rewards coming from arm 2 are different, iee.
T
dham(r; r') ((x + r1)
Σ
(A
1=1
Let us introduce the notation Ta,e Fra.. where Ta, - minft E N: N.(t) =). Then,
Na(T)
Nz(T)
dham((r,)))
1(2,, 2222)=
Σ Z,
where Ze 1(r2, * r(.,)) are i..d Bernoulli random variables with positive mean E,yn [Z.]
Fy (r2. # r22,,) TV22, Pt).
Pyn (S2 < Pyx
3m < n2
Σ
Z, > (1+ (L+a)
8=1
P
max
2==1
m
(1 + TV Pb)
12
Using Asymptotic maximal Hoeffding inequality (Lemma 12
we have that
lim PyT maxmán En Z. > (1+ Pb) 0.
Thus, by choosing ne n2 (T) function such that r22(T') when T oo, then
Pyn (Ω oT(1),
(14)
asymptotically in T.
27

---

C.1
Complete Proof of Theorem I
Before providing the proof, we introduce maximal couplings.
Definition (Maximal Couplings). Let and Q be two probability distributions that share the same
o-algebra and [I(,,, Q) be the set of all couplings between P and Q We denote by c (IP, Q) the maximal coupling between IP and Q i.e., the coupling that verifies for any measurable A,
P P(x (F.O) [X A] Px~rpx E P), ( E A] = Pr~alY E A),
F(X,Y) (7.0) X # y]= = inf
+ Q)
cell(P.Q)
Finally, we are ready to present now the detailed proof of Theorem |
Proof of Theorem 7 Without loss of generality, suppose that we have 2-armed Bernoulli bandit instance V P2) with means (14,, (2) where 14 2 /22 Let æ be an c-global DP consistent policy. We also introduce two other environments v/ = (Pi, P2) and v" = (P1, P.T) that only differ
at the distribution of the second arm, where μ12 I u12 ju S p2z i.e., arm 1 is still optimal in environment s' but is not optimal environment v".
The main idea is to control the probability of the event S & (N2(T) S n2) in an augmented coupled history space, for some T22 to be fine-tuned later (that may depend on the horizon 2).
Step 1: Building the coupled bandit environment 7. We build a coupled bandit environment y of and o'. The policy æ interacts with the coupled environment y up to given time horizon T to produce an augmented history {(ae: rt, (() The steps of this interaction process are: (a) The probability of time / is dictated only by the policy H, and Ø1; 11, 022 r2,--. 1, i... the policy ignores {ra) [=] (b) The distribution of pair of rewards (rr,*() is Co2 - (Po,, Pa. the maximal coupling of (Pa,, Pa,) and is conditionally independent of the previous observed history {(a,, T's [l The distribution of the augmented history induced by the interaction of (a,,Ti, r1..., ........... OT, rT, rT) A II ve(as |
choosing an action 0₁
t and the coupled environment can be defined as p (a1, Tı,
a1; ..,...; re-1, 1c,, (rt, r/).
Again, we introduce the notation A (a1..... 01 A (ri,...., rr), and r' & (ri,...,,,7)) r4t. Step 2: Probability decomposition. We introduce L a {dhamm(r r') S (1 + am TV (V PJ) d.P., (r() log dPH (r()
and A A
{ET
& (1 + a)) 1²) m2 } for some a > 0, where dham(r, r') -
Et Pragrr Also, here for Bernoullis, we have TV Pb) = p/2 12-
Event L will be used to do change of measure from environment y to v' using the group privacy property of π, then event will be used to do a classic "Lai- Raii-Robbins" change of measure using the KL from environment s' to v"
First, we start with the decomposition
Per (N2 I n2) = p,r (2 n L 4) (9)
(15)
Step 3: Controlling each probability. Using Lemma which formalises the "double" change of environment idea, we get
Pyn (2N < (1
O(T9) T
(16)
for any > 0. Using Lemma and Lemma 3 we control the probabilities P ( n L n A9) or or(1) and P.r (I2 L+) = (1()), for any choice of n22 = (2((T) as a function of T such that
n2 (7) + oo when T + x..
Step 4: Putting everything together and choosing n2. First, we chose n2 <IV( OTT²)
(1-a) log(T)
a and a = 2 to get exp ((1 + a) (P2, Pb) + kl(pb (())) T T-ng = o1()
With this choice of n12, we have now that Pyr (N) < n2) = oT()), and thus, using Markoy
inequality, we get, for any > 0, and all μ2 1/2 S M1 - p
(1 a) log(T))
Epn [N2(T)] 2 N2P (N2(T) > n2) ETV(P, P2) + kl uy) (1 (1-)
o(1)
28

---

Finally, taking - O, and the supremum over all p1 [12, and μ2 + p1. we get the result.
D Concentration Inequality Proof
Lemma 4 (Tail Bound of Cumulative Laplacian Noise). Let 7m =Ete Yi where Yt Lap(1/c) are ii.d. Laplace random variables with parameter 1/e. Then, for 2 > 0, we have
7l 2 =] < exp(-I(z))
where f(2) 62 1 11gmlog(1 + mez).
Proof. For a random variable Y ~ Lap(1 /e), the probability density function is
(v) 2
exp(-el
The moment someent-gnneratngg function (MGF) is given by
My (t) E[exp(tYY)
|t|
<e.
2
f2
The random variable Zm 1= Yi is the sum of m i..d. Laplace random variables. The MGF of Zm is the product of the MGFs of the individual Y::
Mzn. (t) = (M)(
Thus, we have
2
Mzm (t)
<e.
To bound 1m[2m 2 =/. we use the Chernoff bound:
P 2 v inf Elexp(t.Zm. - t2)]
oct<c
inf exp (-tz) Mz.. (t) octirr
6²
inf exp oct<r
-12 - m log
c 2 f2
122
inf exp 0<t<c
-tz log
1-
2
Consider
t2
f((2) tz + m log 1
2
Letting = evI (0,c) for A 1/(mez) we have
f((2) = ezv1 - c m loge
2 t.c + log A 1/(m=z) (by -1-e2 c
= EZ (ez A 1/m) + m log(1 A 1/(mez))
EZ log mez)
2 E2 m log + mez).
Then, we have
f((z) 2 EZ - 1 mlog(1 + mez) f(2),
for z 2 0. Thus, we obtain
PiZm 2 2) exp (-f(z))
29

---

Lemma (Concentration bound of private summation). For E (0, and > 0, let
11
m
Sm.m
X; Ber(p)) Y, Lap(1/e)
be the sum of independent n. Bernoulli random variables (RVs) with mean I and m Laplace RVs with scale 1/c. Then, for np
Pr Sn,m 2) S Ac(n, m, n, M.e 1)) (d/l//n..))
where
A. Am (m,n,x,,1)
{ e(l me(x yn) TM log /
(x - nup)
max vElu.//n]
e(1 me(x n4)) + +1.
Similarly, S 14p4
Pr Sn Snm S x S A.(m, n, p)e add(a///
where
(,,
(np x)
c(1 melyn x² log
+ c(1 mc(np x))" +1
yE|z/a,p1
1 1-H μ
Proof of Lemmna 5 For μ E 10 and > 0, the private summation can be written
m
3 nnm
Xi
Y
X Ber(u), Y; Lap(1/e).
(17)
1=1
j=1
Re-define the non-private summation and the sum of the noise by
Sn
X
Zm Σ Y
(18)
and denote density of Zm by fm (=). Then, we can upper bound the probability by
Pr 5 2 x
Pr [r Zm 2 x] fm (z) Pr(S, 2 2/dz
fm Pr(S, 2 - 2|d2+ + / fm 2 x - 2/d2
(m( 2 2//d2 /-=0 fm(2) Pr[S, 2 - 2-22
Pr(Sn 2 x] [ [m()) 2 -
(19)
2
M
Here, Pr(S,, 2 x =] can be upper bounded by Chernoff bound. Let P(r z) be such upper
bound. Then, from Lemma III we have
P(æ 2) c = for r r-2 np.
(20)
Based on this upper bound, we can bound the second term in 19
(II) = { 20
fm 2 x - 2/dz
30

---

[m(=) 2)dz
J0
PiBn(2))P( - ==)0== + / Pm 2))dz
(integration by parts)
F / Fm(()(-PP(C =2))dz
2 P(x) + / Em(()(-PP(( - =))dzz,
(21)
where (2) _ fm(z)dz= = Pr[Zm 2| is the (complement) cumulative distribution. From
Lemma 4 we have
(m) mm 2 m| v exp (-f(2))
where f(2) ez - m0g + mez). Thus, we can bound the second term in (21
Pm (m(())- (-P P'xx - =))ddz
00
Fmn(2)( (P((-PPpx- 2))dz +
P (Fm(z) is decreasing)
2-nH
f (-P'(x- ( 2))dz
Fmn(2)(-PPs 2))dz + Fmnx -np)
Ja-na
n
(= P'(x =))d= + Fm nnp--n))Ppp P(np)
(-P =))d= -
(22)
We now focus on bounding the first term in RHS of the last inequality. Observe that
P'()) (z/m pie -n
(23)
where k1'(2,2)
(x,y) 3) = (kd(w)))
is the derivative with respect to the first argument. Then, for x 2 2 n44.
dx
we have
n
f(z)( Pp 2))d2
x an-
e(1 + mez) "ml kl'l 2)/n, u)e =e (o-k--((((==)///pp)
s/n
ne(1 + ym) (y, uee cla- va- -n m.ll y (s 2)/n)
fz/n fein
<e inf ialgcluanneeeee-
ne(1 + me(a "n))
Se mdddle//) for ne(1 + me(x - mm (y p)dy
= -ddd//// ne(1 + me(x un)) (m)) kll(l/ll 14)
So -d.(//// no + mc(x - (m))mn p))
= ne(1 + me(1 - (um) m log
(24)
where di (x/n,, 11) is defined in (6). Now, we bound the second term in 22
(( =e(1 + me(x -e ne(x/n=n)
<o(1 + mc(a mp)) m (x/n....)
(25)
31

---

Note that we have for x 2 mp
Pr(Sn 2 x P(x) & -nl((///a))
(by Lemma I1
Se (ddd/////
(26)
Putting 24
25 and
26
together have for x//n 1
Pr pp, 2 x - Am n, n, u.) n (ele//p
where
A. (m, n,,,,, = (I nnp)
max vc vElu.//n]
eel + me(r - ym)) log /
+ e(1 + me(x -pp))" + 1.
Similarly, get for x//n S M
n, Pr Sm,m S x S n,, Nie
where
A A, (,,,,,
(x-np) max wElam/n)
e(l + me(x ynn) log + e(1 me(x n4)) +1.
Corollary 1 (Concentration bound of private mean). Consider Sn,m given in Lemma 5 Let E [0, 1]. Let {n ImeN be a sequence such that m/nn. = o(1). Then, for any there exists constant Aa >> O such that for all m E N
Pr
Smm m
< Age (dn
x 2 p.
1m
Spmm
Pr
< mm
S p.
Um
Proof of Corollary 7 From Lemma have for 4
(m Rms x, (4)
=nmm (x ()) max sE(u,
eel + (m + D)nm - y)) m1 log + e(1 + (m + 1)enm (2 - 1))
(27)
For E [u, x].
A. (m,, 7m F, n)= S A(nm) 7mme(1 + (m + ) log 1 e(1 + (m + ) + 1.
Since existing to make 1 + S be hold, we have the result. The proof for the case of x j is completely analogous.
E Privacy Analysis
First, we provide simple lemma motivate the intuition behind the algorithm design. Then, we provide complete proof of Proposition|
32

---

Lemma 6 (Continual release of noisy rewards). Let rewards fri....,,rh T. Then, the mechanism
rr) E [0,
Ler = =1
12 t be time-step, with
r1
r1 + ... + r2 + Y1
F2
S
71 + Tt- Y1 + Y2
PT + Y1 + 122 + +... Yz-1
is e-DP, where (Y,...., Ye) .id Lap(1/e).
Proof of Lemma 0
First, consider trying to release the following partial sums
F1 + + Pig-
r2
Pt + 7
PT
T4- + TT
Because the rewards are in [0, 1], the sensitivity of each partial sum is Since each partial sum is computed on non-overlapping sequences, combining the Laplace mechanism (Theorem 5) with the parallel composition property of DP (Lemma IO) gives that
11
r1 + rt + Y1
Ita + ....
+ Pt--1 + Y/2
P
FT
The-1
rT. + Ye-1
e-DP, where 1e-1) iid Lap(1/e).
Consider the post-proe post-processing function f (#1,... De xz-1) - (x1, + I2,...... ,.....,,t 31 + D2 + ...... + xz-1 1).
Then, have that that C i. So, by the post-processing property of DP, C c-P.
Proof of Proposition Let be either DP-IMED DP-KLUCB. Let {ri, (f1,--.,P7) .T) and r² (r...... ... be two neighbouring reward lists, that only differ t* {I...., T). Fix 4 (a1 (a1...., 0T) [K]T. We want show that
V (a) S (a).
Step 1: Probability decomposition and time-steps before t*:
V (a)
Te (arla1 F1, 41 11-1) (alaaa a- 1/11)
II
(F
me
[=1
T
melae ri, ... a1 Pt-1)
II Telaelas, .h... a-11
(=1+1
since for t
t", r K. Let denote by Pr(a>t
.))
IT aa(aaa Ti... dz- d.-1. the probability of the policy recommending the sequence (0e+1....., ar), when interacting with r = (rr} and already recommending o1...., ar- in the first steps.
Let us denote by .t. ty the time-steps of the beginning of the phases when i interacts with r, and 1' "i, the time-steps of the beginning of the phases when x interacts with r². Also, let 4. be the beginning of the phase for which L" belongs in list phases. Similarly, let bi be the beginning of the phase for which t* belongs in list r' phases.
Since (a1...., ar) is fixed, and r; = r for < t", then th. = =thy and = KG, Le,, t" falls at the same phase in r and r'.
Step 2: Considering the noisy sum of rewards at phase k*:
33

---

Let St. = -E + Yı, be the noisy partial sum of rewards collected at phase k for where Yu- ~ Lap(1/e). Similarly, let S k. Z
- r' + YE be the noisy partial sum of rewards collected at phase kt for r", where Vgg ~ Lap(1/e). We make two main observations:
(a) If the value of the noisy partial sum at phase k* is exactly the same between the neighbouring r and r', then the policy will recommend the sequence of actions a >t with the same probability under r and r':
Pr(a
Et r. St. s) = Pr(a"" S rr, S s).
(28)
This is due to the structure of the algorithm π, where the reward at step ts only affects the statistic Sg.. and nothing else.
(b) Since rewards are [0, 1), using the Laplace mechanism, we have that
Pr(Sg. a r) S e Pr(S = S St .r)
(29)
Step 3: Combining Eq. 28 and Eq. 29 aka post-processing:
We have
S5 .)) = /
Pr(a >1
Pr(ff. = a²" .r))Pr(a"" Se .r. =8)
SER
$
C'PrSS = ,'')Pr(a>** a .r', Sr s)
JERR
= e Pr(a2"
a St" ,r)).
This concludes the proof:
V7 (F
Pr(a2t" a .)
a E
Pr(a>1'
F
Regret Analysis Proof
Lemma (Explicit solution of de). If,, n¹ (0,1) and μ S n,, have
de(u, A inf (kl(2, 11") c(2 14)
(30)
zE(M,N")
under Bernoulli cases, then solves the optimisation problem. Thus, we have
n1 = max (w - 1e'ees
kl (H,,4))
if p 2 1 + (1 1d)ee
d.(s)p))=
1¹ te ( (1' (1- -mx
/
(1 vl) 11 + (1-
if 5 1 + je'
(31)
For 2 vl,
1l.e ul + (1- 11)) 11)
2" min
and
if p < p'e-
kl (l(
ule + (1 - (1-1e)²
d.())))))
n'e- we' + (1 - - +e (u we + (1 - 111)))
ule
p'e²
if p yl'e + (1 - 110)
(32)
34

---

Proof. The Bellback--eiblee divergence between two Bernoulli random variables with means 2 and μl is given by
1-2
kl(2,)) = = log /¹¹ + (1 - -2) =2)log
1 /
The optimisation problem
2 llo 2 + (1 2) log 1 μ¹ + c(2 1)
de inf =E sElp
μ
To find the optimal 2", take the derivative of the objective function with respect to and let it equal to 0:
2 1
1-2 + c(2 u) = 0. + (1 2)
2 log
Oz
1 - μ¹
By calculation, we have
2(1 -() t 0. n¹ -2
log
Rearrange for 2, to obtain
1t + w()es
The optimal x must lie within the interval [e, n²), hence we have
11
11 (,,
( 1 (1 ul)es
max
We always have -+(1--0ee
p Wer S pl, so remove the min part:
1 2" = max (1 w + (1-1111))) --/)ee )
Thus, we obtain
kl (1.
if 2 + (1 wl)es
de())
1² kl ( + +1 ((l-w)ectte He + ut + (1- -ejeee 11
16
if ps + (1 (1-1/)e 1l)e
Now, we consider μ 2 u',
de de(H)
inf (kl(2, + c((u -2)} =Elu' ml
So, we need to minimise
de = inf 1oo 2 + (1 2- log - + E(μ 2) 1- μ
zEIa' w1]
μ¹
over [w', 14). Differentiating the objective function with respect and setting it equal have
1 -
log n
log
0.
Solving for z, we get
ple-
e'ee + (1 - μ²) 2 n¹.
Projecting the solution to [p', nd) then have that the optimal solution is
μ'e
min
wle + +(1 (1-5
Thus, the explicit solution is
n'e²
kl pH,,
if p wle + (1 - 10)'
ple ) if p μl + (1 - (1') we + (1 (1- = -1 + 2c(p= pe + (1- (
nld²
kl
35

---

Lemma 8. For any p.pl E [0, 1],
dfde (1, du
Sc.
Proof. For μ S yl, from 31 we have the explicit solution. p 2 n'+(1-w') jec
de (H, n³) kl(p, vz) μ log
H
+ (1 pi) log - 1
Its derivative with respect to is
dfde k') de
d
p(1 - p¹) 1² - 11)
kl(H, n²) = log
du
We have the condition
11¹
1 2 u
1l + (1 1e)es
Since μ² 2 μr, we note that
d'd. (1,)1))}
50.
dy
Similarly, since μ 2 11111 [++(1=w)er- Jes we substitute this into the derivative
m11 1²)
(1 vl)
11(1 11)
nl
16'
ec
10' x'+11-pase"
Thus,
p²1 11')
log
11(1 - 14) 50.
n¹ 1 S (0+(1=p)) then
d'de (H, -
du
Therefore, for μ S n
dfde (p, dp
<0.
Now, consider the of p 2 n/. From the explicit solution 32 when μ
k'e
we=+(11p)))
n'e ((d.() and the result holds. Let's consider ça +1e-+
similar the above argument,
dø we have
111 n²) dfde (n, kl(H, log du
[0,.e.
du
1 - p)
Thus, have the result in the lemma.
Lemma 9. For any 0 S n² <1
dfd, (H, 4²)}
1
dul
Proof. Considering the definition of d, in (6) we have for 0 S f S μ²
de(u,))) inf kl(2,)() c(2 nd) sElm,n1
We first show
dfd. (n,
d(kl (1, dpl
(33)
dpl
36

---

From the explicit solution in 31 we have if 2 w'+(I-n'eer then d, (1, n²) = kl (1,, k(). So the Je In this
inequality holds. If 14 1+(1-pae let ((() 1 --(--1)er then (' Tt' )e
case, d, (1,, μ²) = kl (f()),))) + (f(())) - p1) where μ S f(4() S p.. By calculation, we have for this case,
dfd. H') ((()
log f(1e) - log - f(v() 1 1d
f(''
+e)
du'
11'
1d 11)
Note that log fun2) log
1-f(p'1
+ c
and 5 f(1().
And we bound
I-
d(kl (4,, [1)}
1 1
dul
11
1
1
nl
1
Thus, we have the result.
Theorem 3 (Regret upper bound of DP-IMED). Assume μL* < 1. Under the batch sizes given in 12 with > 1, the regret bound of DP-IMED for Bernoulli bandit is
Rogr (DP-IMED, v) S Σ ad, T
inpi de p*) + o(logT)
Proof of Theorem 3 Let T be the set of rounds t such that Lines 12 are run, that is, the rounds
such that the arm selection occurred. For T, we define (t) as ji,n when (t 1) Tim Let j be any optimal arm, that is, j such that A = O. By the batched structure of the algorithm, we have
Regret (T)
(1* (b) (i(t)
87f1" t=1
<
(μ* - mi) +
Σ
(4** pa)
B B
(i(t) = N.(t 1) 7m. t E T]
1=1 m=0
70
Σ
(μr* mi)
T
Σ (nt m:)
Bm 1 [i(l) = i, N. - 1) 7m LE E (ū5(() < p
t= m=0
(A)
T
30
(1t
p4)
Bm 1 [i(t) i, N, 1)
Um t t TET, /² 5).
m=0
(13)
(34)
where 5 is small constant. (A) and (B) correspond to the regret before and after the convergence, respectively. Note that we have
a
m+1
m++ - 1
Thm
100
no
+ a-1
(35)
and
m++1 -
a -
Bm
Pm
7mm-1
ng
70g
+1 2n
(36)
a-1
a
37

---

Pre-convergence Term. First consider (A). Define
max 1 mapyy Spr -
{nm de (Kz.mbbb H²¹ - 6) + log Am }
(37)
where we define Ij -00 if Pjjm
all m E E+. re for
Then,
(i(t) = i, t E T, (t) < p² - implies that
4(t) (t) S (0) S 1(d p" -0) + log N₂(1) 1j. where (*()) max; [t()) is the optimal arm obtained by Line in Algorithm By this fact have
T
(A)
Σ
Bm+1 1 1 [1(t)=i, =1, Ni(1 1) Rm: ET,, T((1) - [,]
(=1
T'
Bm+11 [i(1)= =i N,(1 - 1) = Rym 1 ET, log N₂(L - 1) s T,]
[=1 m=0
T
B Bm+12 1
((t) = i, N,(t 1) nm: t E T, 7m S s
[= mm0
Σ
i(t)= = i, N₂ 1) = nm, te T, nl a -1
a sob
Bm+1
m=0
t=1
log, ((a //gg/1111)
T
Σ
But+
Σ
[[(())= = Ni(t - 1) = Rm: E ET
M=0
Since (i(t)= = i, Ni(l Rem) can occur at most once for each we have
log.((a-11)) ((a-1) 5/oot)))))))
(A) v
Σ m==
Bm+1
n Uloga (a-11) //o+)))+++ nl
1og, ((a-1)oat /mo 1
n10
n10
a-1
a²((a - 1)el: /no + 1) no + 1 (iees/nn=-
$ no
a a-1
= a²o + anp +1
{nm amde 88} am +
= =a²
max mijiy. </
< a Σ 1 [pg. < <p' 6) nm am ((Psiimbb ano +1.
(38)
Now, let consider the expectation of 38 When By.m 11" 5 we have
fur
pu
dfde (Iāg, lb- m)}
de de((ijmmylb 1¹- -6) de ( lb.
du
dp (by Lemma 9
> de (i, l1.1(²) k(*)
1 μ
d. (1 (i mo vx*)
8',
where we set 8' = 5/ p²).
38

---

Let P(x) = Pr|de (
j.m, y lo x²) 2 fi.m < 1 - 8). If PJ.m 1et - 5, then 0 s
de de((ū),.mslb:-u" I di = d0 )="). Hence, we have
E
1 Pijm
< 1= - 5) nm C (lsmmbon
cm -63
1 Jigj.m < s² - 6) nm e (B )=8))
E
dd
um Ume amm (x- (d(-)))))ppp))) d(-P(xx)
dd n cmmllm00))) P(x) dr
= =Imme" (-
di ((v
S e and
" e e P(r) dx.
Let Ca E [0, [r] be such that de (Co, 11*) = 2. Then
{delleg.,,lo n²) 2 z, Ryjm < p² 83 {ig. Cci 1=--8) -8
Therefore,
P(x) Prlūjmm < Cas Mjmm < p² - - m
mmdelennii)) A (39)
for any a > by Corollary | Thus, we have
E Fimm 4² - 8) "
+ /0m d)
S Nme n'nd
n e (omml--8)) A dx
mmm Dm
+ di din Are mm160-0 nm
(40)
By letting a < 8' and combining (38) with (40p, we obtain
2
E
[[(])] 2
Om amd + dnn Age mml(6-aa) + ano +
2
nd"
+ + Aac (26'-n( + amg +
(8' ua)
+ A, e (0'- (e (0-10' a0) + +1)
2
+ ang + 1
(8' -a)2
(1-c c-'6 -0)33
c (8)
(c- +1)
a²
(dd' + A1
+ ano + 1
e (8' 08-33
= 0(1).
(41)
Post-convergence Term
Next consider (B). Since de (u, n) = 0 for any μ E [0, 1J. we have
('(t) S max (t) ((== (1)
max log Nv (T) < log
Vap (1)=)(()) (1)
On the other hand, i(t) = i, N.(t 1) nmm tET, T, (t) n³ 8 8 implies that (1) = (()) 2 ne (li+(()), [7 (1))) de (lix(()) n² - -8),
Tm,
from which we have
(i(t) = Na(t - 1) = nm, E T, (tt(t) 2 2p² -53 C de (17:(t)] μ²¹ - -5) I log T)
So, we have
T
8
(B)
Bm+ 1 [i(l) i, N.(1 - 1) = nm, 1 LET, (2y(1) 2 p² -
1=1 m=0
39

---

T
Bm+1l 1 (i(t) = N:(t - 1) = Tom an (lā,(t)]b: p²¹ - -d) 2 log T
[=] m=0
T
Bm+1 1 [mmde (lit. f1" - 6) - log T
Σ
1 li(t) N,(t 1) = 1mm!
m=0
20
Bm+1 I [ninde (1 11 - -d) 2 log T
(42)
m=0
Bm+1l 1 [ p²) 8¹) log T)
m=0
where recall that 8' = 8/(1 ) and the last inequality follows from Lemma
Let
log T
H
(43)
de (e 11*) 28
and
m = inf E N. nm H}
Then, by Rm H and 35 we have
no a -
a
H Rm
-1
2 ng
a
a
which implies
(a (a-1)H +1)
m²
S
loga
(44)
n2p
Now, the post-convergence term can be bounded as follows:
B[(B] <
Bm+1 Pr (d 1²) 5') s log T]
m==
m -1
Σ
Bmt1 Σ
Bm+1 Pr [m (de (Ji mi:
ld= 1²) -8') < Tog
m==0
m=m=*
Bm+1 Pr H (de 8)) log
0m
n10
a +1 1
+ 1 - no + Σ
Bm+1 Pr H (de 1²*) - 8') s log 7]
710
m=m*
(a-1)1 + -1
< 710
n2 + Σ
Bm+1 Pr dde (ldi v²) S de (pi, k²) 8']
a - 1
(by and
all +1
Bm+1 Pr Jii. 2 p4 + 8e
(by Lemma
m=m*
Sal
Bm+1 Ag Ag mm - (p+++ /e,p')
(by Corollary !
<aH +
m1+1 Age mo 2
m+
a-1 (d.(m:00//e )=44))))
(by 36
(45)
m=
aaH + A
Σ
m+
(46)
m=
40

---

all An Io a dx
aH 2a e-ai'
In(a)A
a aogo
de 11*) 28' + to().
(47)
Here, in 45 took a' < <d(44 + 8' (()) and in (46) we defined
no nd (m, + 8' "/, (1) a') a
We complete the proof by combining 34
and and letting 8' I-p 4
Theorem (Regret upper bound of DP-KLUCB). Assume pd 1. Under the batch sizes given in with or >> 1, the regret bound of DP-KLUCB for Bernoulli bandit v is
ad, log T de(ps, w+)
(DPp(DD-KLUCBB,) v\) <
+ ollog T)
Proof of Theorem 4
By the same argument as the analysis for DP-IMED we have
Regret S no
Σ
(n*
#
00
Σ 8z1
(1r p4)
Bm 1 [i(t) = N₂(1 1) nm, 1 LET, (1) n²
m=0
(A)
T
50
+ Σ
(4t p4)
Σ
B 1 [i(t) = i, N, - 1) = nm t te TET, (+(() 2 μr¹ 8).
m=0
(48)
where (t) = max, [t)...
We transformation of these terms that is similar to Honda 2019 but more suitable for the batched algorithm. First, we have
T
(A)
B 1 li(t) N.(t - 1) Roms te T, (t) < p² 5)
[=1
m==
T
m 1 li(t) i, Nt 1) =
mom te T,,, (,(()) < p¹ -].
Let
1-= max. mpp.. <p- -5 (ligieimmmm n²= -0]
Since
-03 (1,(1) < n² - 0}+ + sup { u de (1(
logt
< 1r -
N₂ 1)
logt
de (e -8)) N₁ 1)' (3)(t) < <x²² -
< (110-1)), (ú5(1) < n¹ -6}.
41

---

we see that
i(1) =i, Ni(1 1)= Rm, LET, <ET,L<e> ( -6), Fijm < <x² -
Bm++1 1
m=0
T
20
Bm+13 1
[(t) = i, N, 1) Am- <<
T
Bm+1l 1 i(t)= = i, Ni(t 1) = nm, Pm < <
(by Ni(t 1) S 1)
m=0
T
Bm++ll 1l mm <oti Σ
1 [i(1) = (N(1-1) nm.
m=
1=1
Bm+tll Il nm < <
m=0
(a + 1)e
(by nm
= =Ei Bm and B S amm)
- (a + l)e?,
where 1, is defined in 37 The evaluation of this expectation is the one same as 38 which results [[(AA]] (1).
Now, we consider the second term. Note that i(t) = implies (t) = (te(t) and we also have
(a,(1) 2 1² -3
sup ju: de de(( 1)) S N₂(1)
logt
2 4¹ - 8
logt
dc(((,((t)bbb -- - -5) N,(() J
Then, have
B
BmIil (i(1) i, N.(1 - 1) 7mm LE EET, (1) 2 n² -
Am
m=0
Σ
Σ
Bm+1I 1 [i(t) N,(t 1) nm 1 E ET [i(()) 2 p² 8]
t=
00
log 7mm
B Bm+1l
i(1) =i, N1(1 1) nmm: ET, de me 1b.11. 11" -8) S
t=1 m=0
log
Bm+11 I
de de -6)
1 [i(1) i, i, N₂(1 - 1) = mm
m m0
[ml
log l
Bm+1l 1
de de 8) s
whose expectation is analysed in
42)
in Azize and Basu [0022] and Basu 2022 shows that for > 3, AdaP-KLUCE yields regret
Comparison to the regret bound of
Theorem in Azize
Ci(r),,
37
)) (49)
Reg, (AdaP-KUUCB v) <
min(kl(Has f³), CzeA log (T) + 7 7-3/
a:A.>0
where (r) and C2 > 0 are defined as
inf max (1+ B)a (1+7) SEB
C1((T)
log(T) A min(kl(pa. (al(k(((a.)))) ,²); C2cA log(T),
((( [c(33) - Ye,T) ),
42

---

such that T is a constant that controls the optimism in AdaP- KLUCB, B _ {5 0: c()) yer
for 3 0, c(B) E [0, 1] defined such that: ki(Ha c(3) 1²)) d(pa.f)) and "e such that kl + +e,T Po) - log(T) for the horizon and & the phase.
1+8
In general, C₁ and C2 may depend on Ha and μ², and thus are not "constants". In contrast, our bound in Theorem 2 matches the asymptotic lower bound of Theorem uup to the exact constant a 1 that controls the geometrically increasing batches and which can be chosen arbitrarily close to 1. In addition, our analysis only requires that the number of batches is sublinear in T, as seen from Proposition[] As a result, we can also use polynomially increasing batch size instead of Bm, R am", which fully makes the regret asymptotically optimal. We used geometrically increasing batch size here just for simplicity.
Comment on KL-UCB and IMED algorithms. We present both DP- -P-KB and DP-IMED to show that, for two different algorithmic design philosophies in bandits (KL-UUB and IMED), privacy framework of geometric batching without forgetring, combined with our new concentration inequality, can design algorithms with optimal regret upper bounds.
(a) KL-UCB and IMED belong to fundamentally different algorithmic bandit families:
KL-UCB is UCB-style algorithm that relies on optimism in the face of uncertainty, and constructs upper confidence bounds based on Chernoff's s inequality.
IMED is an information-theonee method that selects arms based on empirical divergence minimisation, comparing empirical rewards the estimated best arm.
(b) Our proposed privacy framework works for both KL-UCB and IMED: our framework estimates the unknown means privately by running the algorithm in geometrically increasing phases, and accumulating Laplace noises from each phase, i.c. no forgetting. In addition, our tight DP-Chernoff concentration inequality (Proposition M directly provides new de-based indexes for both KL-UCB and IMED style algorithms, tightly balancing exploration and exploitation under noisy DP observations. Combining everything with a generic regret upper bound analysis provides two optimal DP bandit. algorithms.
Improved regret bounds of KL-UCB/IMED v.s. UCB The improvement introduced by us- ing asymptotically optimal algorithms (KL-UCB/IMED) compared to the vanilla UCB algo- rithm Lattimore and Szepesvári 2020 boils down to comparing kl(pa: with the squared gap
A3 (/r pa)
(a) Using Pinsker's inequality, we always have that kl(Has n²)² 2 2
(b) However, for close values of Pa and μ², a Taylor expansion shows that
A + +(A
kl(Ha, 24aa -aa)
which means that
-- kl(Ha. -(+) 2|aa 111--a. pa)
+ o(1 - oc
when Ma tends to either 0 or This means that our algorithms DP-KLUCB and DP-IMED improve over the state-of-the-arr algorithms (AdaP-UCB and Lazy-D--TS) in problem-dependent constant (related to the variance of Bernoullis), which could blow up for some hard instances close to the borders 0 and 1.
G Extended Experiments
In this section, we present additional experiments comparing the algorithms in four bandit environ- ments with Bernoulli distributions, as defined by Sajed and Sheffet (2019). namely
# = (0.75, 0.70, 0.70, 0.70, 0.70), 122 = (0.75, 0.625, 0.5, 0.375, 0.25), #3 = {0.75. 0.53125, 0.375, 0.28125, 0.25), A44 {0.75, 0.71875, 0.625, 0.46875, 0.25).
43

---

and four budgets e E {0.01, 0.1, 0.5, 1}. The results are presented in Figure 4 for μl, Figure 5 for pa- Figure for Ma and Figure 7 for μ4. We implement all the algorithms in Python (version 3.8) and on an 8 core 64-bits Intel i5 @ 1.6 GHz CPU.
For all the environments and privacy budgets tested, DP-IMED and DP-KLUCB achieve the lowest regret.
Comparison to the lower bound. We also plot the regret as function of the privacy budget in
Figure The algorithm chosen is DP-IMED with a = 1.1, T = 10 and for bandit environment μ [0.8. 0.1, 0.1, 0.1, 0.1]. We discretise the [0. interval into 100 values of For each the algorithm 100 times and plot the mean and standard deviation of the regret in [0, 1]. We also plot the asymptotic regret lower bound in Figure 8 for T = 10" and μ function of The performance of our algorithm DP-IMED matches the regret lower bound. We also remark that the change between the high and the low privacy regimes happens smoothly.
run
Effect of a, the geometric batching hyper-paramter. all previous figures, we took a 2, which corresponds to arm-dependent doubling. The reason we chose 2 is to have a "fair" comparison to the other algorithms in the literature, i.e. DP-SE, AdaP-KLUCB and Lazy-DP-TS, which all use an arm-dependent doubling in the original papers, and in theory, could also be implemented using geometrically increasing batches of any ratio a > 1. By taking a = 2. we mainly focus on the effect of our algorithm's 's two main algorithmic novelties: getting rid of forgetting and new d.-based indexes. In Figure 9 we plot the regret of DP-IMED as a function of time steps for different values of a. As gets smaller, the performance of DP-IMED gets better. However, the performance worsens when is very close to 1. At the limit when a + 1, each arm-dependent phase length tends to 1, and thus, one Laplace noise is added to each Bernoulli reward sample. This is equivalent to local DP, where the price of privacy is high.
Real-world dataset. We add an experiment inspired by the COV-BOOST Munro et al. [202] Kone et al. 2023) dataset. COV-BOOST is a Phase 2 clinical trial, conducted on 2,883 participants, to measure the immunogenicity of different COVID-19 19 vaccines as third dose. This resulted in total of 20 vaceination strategies being assessed, each of them defined by the vaceines received as first, second and third doses. In Table 4 of Kone al. [2023], the authors report the average immune responses induced by each candidate strategy in cohorts participants. From this study, we extract and process the Anti-spike IgG average immune response for each strategy, then project them in [0, 1] to simulate Bernoulli bandits with K = 20 arms, and run our algorithms with different values of c. We report the evolution of regret for this specifie Bernoulli instance, under different values of in Figure 10 DP-IMED and DP-KLUCB still achieve the lowest regret for this instance.
H Limitations
In this section, we describe some of the limitations of our results.
Our matching upper and lower bounds are asymptotic in the horizon T. This is also the case in classic multi-armed bandit results without privacy. An interesting direction is to investigate the effect of privacy on the oTlog(T) terms, which are committed in the current analysis.
Our algorithms and regret upper bounds tailored for Bernoulli distributions. This is a fundamental setting in bandits and an important first step for understanding the inter- play between privacy and sequential decision-making. Generalising the analysis to other distributions is an interesting future direction.
An important ingredient in our algorithms is geometrically increasing batching. Our con- centration results allow for any batching strategy where the batch size nr is negligible in T, i.e. nr- o(T). However, it is unclear if it is possible to eliminate this design choice altogether, like we did with forgetting. This is an important direction to explore, especially for adversarial bandits, where arm-dependent batching strategies like those used in the stochastic setting are bound to fail.
44

---

104
10a
Regret
Regret
10a
10a
DP-SE
101
DP.SE
AcaP-KLLCC
AdaP-KLUCS
10a
Lary-DP-TS
10
DP-I-DP-TS
DP-KL-UCB
DP-KL-UCE
DP-IMED
DRJIMED
IMED
10-1
IMED
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Step
le6
1e6
(a) c 0.01
(b) 0.1
104
10
10a
10a
Regret
Regret
10a
DP-SE
10a
DP-SE
AdaP-KLUCS
AdaP KLUCB
10a
Lacy-DPTSS
10a
Lazy-DP-TS
DP-KL-UCB
DP-KL-UCE
DP-IMED
DR/IEED
10-1
10-1
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
1e6
1e6
(c) < 0.5
(d) c ==
Figure 4: Evolution of regret (mean +2 std) over time for for different budgets
I Existing technical results and Definitions
Proposition (Post-processing Dwork and Roth 2014 Let M be mechanism and f be an arbitrary randomised function defined on M's output. M is e-DP, then f M e-DP.
The post-processing property ensures that any quantity constructed only from a private output is still private, with the same privacy budget. This is consequence of the data processing inequality.
Proposition (Group Privacy [Dwork and Roth 2014)). Let D and D' be two datasets in X If M (c, DD, then for any event E E
MD(A) (DDm (A)
(50)
Group privacy translates the closeness of output distributions neighbouring input datasets to closeness output distributions on any datasets D and D' that depend on the Hamming distance dHam (D, D'). This property will be the basis for proving lower bounds in Section
Proposition 6 (Simple Composition). Let M .K be k mechanisms. We define the mechanism
G:D
M
im1
as the k composition of the mechanisms M M
If each M is (es, 6D). then G is Ek Cs, Σ/= 8.)-DP.
each M is PCPCDD, then G is > CDP
45

---

10a
104
10a
10a
Regret
Regret
10a
10a
DP-SE
101
DP.SE
AcaP-KLLCC
AdaP-KLUC3
Lary-DP-TS
DP-T-DP-TT
DP-KL-UCB
10"
DP-KL-UCE
DP-IMED
DRJIMED
IMED
IMED
10-2
10-1
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Step
1e6
1e6
(a) c 0.01
(b) 0.1
10a
10
10a
10a
Regret
10a
Regret
102
10
DP-SE
10a
DP-SE
KLUCK
AdaP KLUCE
Lazy-DPTS
Lazy-DP-TS
10a
DP-KL-UCB
10a
DP-KL-UCE
DP-IMED
DR/IMED
10-1
10-1
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
1e6
1e6
(c) 0.5
(d)
==1
Figure 5: Evolution of regret (mean +2 std) over time for for different budgets
Composition is fundamental property of DP. Composition helps analyse the privacy of sophis- ticated algorithms, by understanding the privacy each building block, and summing directly the privacy budgets. Proposition X can be improved in two directions. (a) It possible show that the result is still true if the mechanisms are chosen adaptively, and that the mechanism at step i takes as auxiliary input the outputs of the last i mechanisms. (b) Advanced composition theorems Kairouz et al. 2015] for (c, 6)-DP improve the dependence on k the number of composed mechanisms. Specifically, if the same mechanism composed l times, Proposition 6 concludes that the composed mechanism is (ke, DP. Advanced composition Kairouz et al. (2015) shows that the k-fold adap- tively composed mechanism is (e', 8' -DD for any 8' where e' /2k log(1/0') kcee" 1). Roughly speaking, advanced composition provides a (vke, 6DP guarantee, improving by /k the (ke, DDP guarantee of simple composition.
In addition the classic composition theorems, provide here additional property of interest: parallel composition.
Lemma 10 (Parallel Composition). Let M' M M be k mechanisms, such that n, where is the size of the imput dataset. Let f1.... tk tx+1 be indexes [1, n| such that = t1 < ... < th <
4--1
Let's 's define the following mechanism
G I
In
M
G is the mechanism that get by applying each M to the i-th partition of the input dataset {x "e....,,,,.. according to the indexes t < tu tx-1-
each M is -)-P) then G is (c, DD
46

---

101
10
104
10a
Regres
102
10a
104
AdaP-KLUC3
104
AdaP-KLUCE
Lazy-OP-TS
Lazy-DPTS
DR-KL-UB
DRILLUCB
10"
DAIMED
DR-MED
IMED
IMED
0.0
0.6
0.8
0.0
0.4
0.6
Step
1e6
Step
1e6
(a)
0.01
(b)
0.1
104
10
10a
Regret
Regret
10a
AdaP-KLUCa
10a
AdaP-KUCE
Lazy-OP-TS
Lazy-DP-TS
10a
DP-KL-UB
109
DA-MED
DP-MED
IMED
IMED
0.8
0.6
0.8
Step
1e6
Step
1e6
(c) 0.5
(d)
c=)
Figure 6: Evolution of regret (mean +2 std) over time for μl for different budgets e.
If each M is Pc-CDD, then G is P-ZCDP
In parallel composition, the mechanisms are applied to different "non- nhon-overlapping" parts of the input dataset. If each mechanism is DP, then the parallel composition of the k mechanisms is DP, with the same privacy budget. This property will be the basis for designing private bandit algorithms
in Section 4
Theorem's (The Laplace Mechanism Dwork and Roth 2014 ). Let X E be a deterministic If(D)
algorithm with & sensitivity s1(f) & max
f(D')
I. Let
D-D
Mi(f.e) ff+ (YI...,,
where Y, are L.dd from Tap (xllf), where the Laplace distribution centred with scale denoted Lap(b), is the distribution with probability density function
Lap(x(b) & 1
exp
26
b
for any IR
The mechanism Mf(f,e) is called the Laplace mechanism and satisfies e-DP.
Lemma 11 (Chernoff Tail Bound via KI. Divergence (Boucheron et al.) (0003). ). Let X1, X2,..., X,, be independent Bernoulli random variables with success probabilities P1-P2..... .p.. Define S, n
En Xi, and let E[S.] Ei= Pt. Then the following bounds hold:
Upper Tail Bound: for any a > p
PSS, 2 a) S exp (-n kl a 11
n m
47

---

104
101
10a
102
Regret
10a
Regret
10a
DP-SE
104
DP.SE
AcaP-KLLCC
AdaP-KLUCS
Lary-DP-TS
10a
DP-I-DP-TS
DF-KL-UCB
DP-KL-UCE
10-1
DP-IMED
10-1
DRJIMED
IMED
IMED
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.8
1.0
Step
1e6
1e6
(a)
0.01
(b) 0.1
10a
10a
10
10a
10a
Regret
Regret
10a
10a
DP-SE
10a
DP:SE
AcLCKKLUC
AdaP KLUCB
Lazy-DPTS
10
Lazy-DP-TS
DP-KL-UCB
DP-KL-UCE
10-4
DP-IMED
10-1
DR-IMED
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
1e6
1e6
(c)
0.5
(d) c ==
Figure 7: Evolution of regret (mean +2 std) over time for for different budgets
where kl(p,g) q) is defined
kl(p, 4) =loo + (1 p) log 9
Lower Tail Bound: for any < 11
P(S, a) exp (-n kl ( nn'
)
Lemma 12 (Asymptotic Maximal Hoeffding Inequality). Assume that X₃ has positive μ and that X; - μA is o-sub- Sah-Gaussiin. Then,
max Eis X, s (1 (1+ =1
Vc > 0, lim P
71000
7
48

---

8000
lower bound
DP-IMED
7000
6000
Regret for T= 10
5000
4000
3000
2000
1000
0
10-2
10-1
100
Privacy budget
Figure 8: Evolution of the regret for T
107 with respect to for DP-IMED 0.1,0.1,,11, 0.1, 0.1], compared to the asymptotic regret lower bound of Theorem
104
Regret
103
a 1.01
a = 1.5
a
102
+ a
0.0
0.2
0.4
0.6
0.8
1.0
Step
1e6
Figure 9: Effect of on the regret of DP-IMED, #2 and 0.25.
49

---

10a
10
10a
10a.
DP-SE
AdaP-KLUC3
AdaP-KLUCE
Lazy-OP-TS
104
Lazy-DP-TS
DP-KLUCB
DP.LLUCB
DA-MED
DP-MED
IMED
IMED
0.0
0.2
0.6
0.0
0.4
0.6
Step
1e6
Step
1e6
(a)
0.01
(b)
0.1
10a
Regret
10a
10a
AdaP-KLUCa
AdaP-KLUCB
Lazy-OP-TS
10A
Lazy-DP-TS
10a
DP-MED
DP-MED
IMED
IMED
Step
1e6
Step
166
(c)
0.5
(d)
c=1
Figure 10: Evolution of regret (mean +2 std) over time for the COV-BOOST dataset, for different budgets
50


Reviews:
[{"review_id": "lXvIQbWIal", "reviewer": "Reviewer_Xdjy", "summary": "This paper studies the classical DP MAB problem, with an objective of closing the instance-dependent upper and lower bound that existed in previous works, namely $\\Delta_a^{-2}$ v.s. $\\text{kl}(\\mu_a,\\mu_\\ast)^{-1}$. The authors proposed a new measure $d_\\epsilon$ such that 1) a new lower bound of $d_\\epsilon^{-1}$ is given, and 2) a new algorithm achieving $d_\\epsilon^{-1}$ is also yielded.", "questions": "Line 95--96: \"However, this approximation can be arbitrarily bad, exposing a gap between the state-of-the-art upper and lower bounds in DP bandits.\" What does \"arbitrarily bad\" exactly mean?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The exact match of two $d_\\epsilon^{-1}$ is exciting. Previously the upper and lower bounds only agree in an asymptotical setting (but now still this case due to $\\alpha$; nevertheless the $\\alpha$ here can be arbitrarily close to $1^+$ in contrast to the previous instance-dependent approximation).\n2. The algorithm design illustrates that it is possible to get rid of \"forgetting\", thus offering more algorithmic tools in the future. However, I have to admit that I'm not super familiar with DP literature, and therefore I am not super certain whether this innovation is significant enough.\n3. Numerical illustraions are provided, which supports the superiority of proposed algorithms.\n\nWeakness:\n1. The match between upper and lower bounds only holds in asymptotic settings where one can reduce $\\alpha\\to 1^+$ as much as they want. \n2. It is unclear how much improvement is really yielded by the new $d_\\epsilon$ measure, given that $\\text{kl}$ and $\\Delta_a^{-2}$ are already approx. equal in asymp. cases.\n\nOverall, I feel the improvements may look kind of \"marginal\" given the previously already-good (but non-perfect) upper and lower bounds. However, given the perfect matching coefficient (if I did not misunderstand), I feel this \"perfect\" result deserves to be presented.", "was_revised": true, "final_justification": "I am satisfied with Authors' responses and decide to keep my original evaluation.", "rebuttal": "We thank Reviewer Xdjy for the time spent reviewing, careful reading, and kind words about the novelty and the significance of the contributions. We agree that highlighting the perfect match between our regret upper and lower bounds may be of interest to the community, as it is rare in online learning with DP constraints. \n\n**W1 - The upper and lower bound match when $\\alpha \\rightarrow 1$.** \n\nIndeed, our regret upper bound and lower bound match up to a constant $\\alpha >1$, where $\\alpha$ is the ratio of the geometrically increasing batch sizes. This parameter $\\alpha$ can be set arbitrarily close to 1 to have 'perfect' matching upper and lower bounds. Still, it is easy to remove the constant $\\alpha>1$ since the only essential requirement in our analysis is that the number of phases is sublinear in $T$ (in other words, the batch size $B_m$ goes to $\\infty$). We choose the batch size of $B_m \\approx \\alpha^m$ just for simplicity, which is practically sufficient. This point is discussed in Appendix F, and we will make it explicit in the revised version.\n\n\n**W2 - The improvement yielded by $d_\\epsilon$.** \n\n(a) In the regret lower bound: the improvement reduces to a comparison between our $d_\\epsilon$ and the $\\min \\lbrace \\mathrm{kl}, 6 \\epsilon \\cdot \\mathrm{tv} \\rbrace$ of Azize and Basu [2022]. In the high privacy regime ($\\epsilon \\rightarrow 0$), $d_\\epsilon$ reduces to $\\epsilon \\cdot \\mathrm{tv}$ and thus improves over a $6$ factor from the lower bound of Azize and Basu [2022]. In the low privacy regime (big $\\epsilon$), both expressions reduce to the $\\mathrm{kl}$, which is the tightest quantity for non-private bandits. Finally, for intermediate values of $\\epsilon$, we always have that $d_\\epsilon < \\min\\lbrace\\mathrm{kl}, 6 \\epsilon \\cdot \\mathrm{tv} \\rbrace$ as explained in point (a) after Theorem 1 (Line 235-236). \n\n(b) In the regret upper bound: the improvement reduces to a comparison between our $d_\\epsilon$ and the $O(\\min\\lbrace \\Delta_a^2, \\epsilon \\Delta_a \\rbrace)$ of Azize and Basu [2022]. Again, in the high privacy regime, we improve over constants. However, in the low privacy regime, the improvement reduces to a comparison between $\\mathrm{kl}$ and $\\Delta_a^2$. This improvement is a problem-dependent quantity that can be arbitrarily good for some instances. Refer to the answer to Q below for a detailed discussion. This is also the case for intermediate values of $\\epsilon$.\n\n\n\n(c) $d_\\epsilon$ is a smooth interpolation between the TV and the KL, that has nice transport properties allowing it to be a good index for DP-KLUCB and DP-IMED. These smoothness properties are also important for the regret upper bound proof.\n\n**Q - Meaning of arbitrarily bad in Line 95-96.** \n\nIn Line 95-96, we are talking about approximating the $\\mathrm{kl}(\\mu_a, \\mu^\\star)$ with the squared gap $\\Delta_a^2 = (\\mu^\\star - \\mu_a)^2$. \n\n(a) Using Pinsker's inequality, we always have that $\\mathrm{kl}(\\mu_a, \\mu^\\star) \\geq 2 \\Delta_a^2$\n\n(b) However, for close values of $\\mu_a$ and $\\mu^\\star$, a Taylor expansion shows that \n$$ \\mathrm{kl}(\\mu_a, \\mu^\\star) = \\frac{\\Delta_a^2}{2 \\mu_a (1 - \\mu_a)} + o(\\Delta_a^2) $$\nwhich means that $$\\frac{\\Delta_a^{-2}}{\\mathrm{kl}(\\mu_a, \\mu^\\star)^{-1}} = \\frac{1}{2\\mu_a(1 - \\mu_a)} + o(1) \\rightarrow \\infty$$\nwhen $\\mu_a$ tends to either $0$ or $1$. This means that our algorithms improve over the state-of-the-art algorithms in a problem-dependent constant (related to the variance of Bernoullis), which could blow up for some hard instances close to the borders $0$ and $1$.\n\nWe will add a discussion about this in the Extended Background section in the Appendix, as suggested by Reviewer aTyM."}, {"review_id": "sW0yTLQa7H", "reviewer": "Reviewer_64S8", "summary": "This paper studies differentially private (DP) multi-armed bandits. It first provides an improved lower bound of the regret of bandits algorithms under the constraint of differential privacy. Then, it proposes two algorithms for DP bandits, and proves that their regret bounds match with the lower bound up to a constant factor. Finally, the synthetic experiments validates the theoretical results.", "questions": "1. Why the authors would like to propose two algorithms? Any specific reasons, for example, their design ideas are fundamentally different?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The theoretical results seem solid and important. Both lower and upper bounds are provided and they are matching up to a constant factor.\n2. The presentation is clear because it lists the key improvements in the proofs.\n\nWeaknesses:\n1. The setting is limited to multi-armed bandits and Bernoulli distribution, while linear or contextual bandits are more general models. In particular, Proposition 1 is limited to Bernoulli distribution. It is unclear that Gaussian or sub-Gaussian distribution can also have similar results so that the algorithm is still optimal.\n2. The experiments could be benefit from some real-world dataset.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I decide to keep my score.", "rebuttal": "We thank Reviewer 64S8 for the time spent reviewing, careful reading and interesting suggestions.\n\n**W1 - The setting is limited to multi-armed bandits and Bernoulli distribution.** \n\nHere are the main elements about this point : (a) the regret lower bound (Equation 9) and privacy analysis (Proposition 2) in the paper are already valid beyond Bernoullis, (b) only the concentration inequality and the regret upper bound are specific to Bernoullis,  (c) it is possible to extend these two results, beyond Bernoullis, to sub-Gaussian or exponential distributions. (d) what is less clear is whether it is possible to obtain matching upper and lower bounds up to the constant for these distributions.  (e) Bernoulli bandits are a fundamental setting found in many applications and the takeaways from our analysis can be helpful beyond Bernoullis or stochastic MABs, (f) all prior work in bandits with DP is for either bounded or Bernoulli rewards, since it is important to control the sensitivity of the empirical mean to use the Laplace mechanism, (g) the improvement we introduce in this setting is non-trivial, and not just a constant factor (see answers to W2 and Q for Reviewer Xdjy). \n\n\nPlease refer to the answers to W3 and Q1 of Reviewer aTyM for a detailed discussion about each point.\n\n\n**W2 - Real-world dataset in experiments.** \n\nWe thank the Reviewer for this suggestion. Indeed, our current experimental analysis is only done on simulated environments. There are two reasons for this: \n\n(a) Starting from the DP-SE paper, most experiments on DP bandit papers (Sajed and\nSheffet [2019], Hu et al. [2021], Azize and Basu [2022], Hu and Hegde [2022]) have been run on the same sets of Bernoulli environments and privacy budgets. This helps in providing a fair comparison of the algorithms, run using the same hyperparameters as the original papers.\n\n(b) Working with simulated environments helps in providing a complete picture by varying multiple parameters that control the hardness of the problem.\n\nWe agree that the paper could benefit from adding a real-world dataset. In the Extended Experiments section, we will add an experiment inspired by the COV-BOOST [1] dataset. COV-BOOST is a phase 2 clinical trial, conducted on 2883 participants to measure the immunogenicity of different Covid-19 vaccines as a third dose. This resulted in a total of 20 vaccination strategies being assessed, each of them defined by the vaccines received as first, second and third doses. In [1], the authors have reported the average immune responses induced by each candidate strategy on cohorts of participants. From this study, we extract and process these average immune responses for each strategy to simulate Bernoulli bandits with $K = 20$ arms, and run our algorithms with different values of $\\epsilon$. Though this is still a 'semi-synthetic' experiment, it would illustrate the performance of the DP algorithms in more practical scenarios. We will report the evolution of regret for this specific Bernoulli instance, under different values of $\\epsilon$ in Appendix G of the updated version. DP-KLUCB and DP-IMED still achieve the lowest regret for this instance.\n\n[1] A.P.S. Munro, L. Janani, V. Cornelius, and et al. Safety and immunogenicity of seven COVID-19 vaccines as a third dose (booster) following two doses of ChAdOx1 nCov-19 or BNT162b2 in the UK (COV-BOOST): a blinded, multicentre, randomised, controlled, phase 2 trial. The Lancet, 398(10318):2258–2276, 2021.\n\n**Q - On proposing two algorithms.** The reason for presenting both DP-KLUCB and DP-IMED is to show that, for two different algorithmic design philosophies in bandits (KL-UCB and IMED), our privacy framework of geometric batching without forgetting, combined with our new concentration inequality, can design algorithms with optimal regret upper bounds. \n\n(a) KL-UCB and IMED belong to fundamentally different algorithmic bandit families:  \n\n- KL-UCB is a UCB-style algorithm that relies on *optimism in the face of uncertainty*, and constructs upper confidence bounds based on Chernoff's inequality\n\n- IMED is an information-theoretic method that selects arms based on *empirical divergence minimisation*, comparing empirical rewards to the estimated best arm.\n\nWe will add an extended discussion about these two families of algorithms in the Extended Background section in the appendix, as suggested by Reviewer aTyM.\n\n\n(b) Our proposed privacy framework works for both KL-UCB and IMED: our framework estimates the unknown means privately by running the algorithm in geometrically increasing phases, and accumulating Laplace noises from each phase, i.e. no forgetting. In addition, our tight DP-Chernoff concentration inequality (Proposition 1) directly provides new $d_\\epsilon$-based indexes for both KL-UCB and IMED style algorithms (Equations 10 and 11), tightly balancing exploration and exploitation under noisy DP observations. Combining everything with a generic regret upper bound analysis provides two optimal DP bandit algorithms.\n\nWe hope that our response addresses the reviewer's questions, and will convince them to raise their score."}, {"review_id": "OV27aoEOhI", "reviewer": "Reviewer_NvHt", "summary": "The paper studies the $K$-armed bandit problem under $\\epsilon$-global differential privacy (DP) and establishes matching lower and upper regret bounds up to a constant $\\alpha$ that can be made arbitrarily close to one. The contributions include: a tighter lower bound (Theorem 1) based on a new divergence that interpolates between KL-divergence and total variation distance; an improved concentration inequality (Proposition 1); and differentially private variants of two asymptotically optimal bandit algorithms (KL-UCB and IMED), which are shown to match the regret lower bound. The paper also includes experimental results comparing the performance of the proposed algorithms to prior methods (DP-SE, AdaP-KLUCB, Lazy-DP-TS); see Figure 1.", "questions": "1. What is the limitation in extending the concentration inequality for Bernoulli plus Laplace noise to more general reward distributions beyond Bernoulli?\n\n2. Shouldn’t the limitation to Bernoulli reward distributions be reflected in the title of the paper?\n\n3. Is it correct to say that the analysis of DP-KLUCB and DP-IMED follows similar lines as the analyses of their non-private variations, with the key difference being the use of the concentration inequality in Proposition 1?\n\n4. In the definition of $d_\\epsilon(x, y)$ (Eq. (6)), the infimum is taken over $z \\in [x \\wedge y, x \\vee y]$. Is this infimum always attained for Bernoulli distributions, and how computationally efficient is it to evaluate this in practice when applying the algorithm?", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is well written.\n\nIt closes a gap in the literature regarding the performance of differentially private bandit algorithms. In particular, Table 1 reports the lower and upper bounds from Azize and Basu [2022], which exhibit a constant gap (assuming the KL divergence is within constant factors of the squared reward gap). This paper improves that gap to an arbitrarily close-to-1 constant by introducing a new information-theoretic quantity that interpolates between KL divergence and total variation distance. See Theorem 1, Corollary 1, and Theorem 2. The lower bound is proven using standard change-of-measure techniques from bandit theory (e.g., Lai & Robbins, 1985). While I did not go through all the proofs in full detail, the results appear sound and consistent with prior techniques. The regret analysis for the proposed algorithms builds on the corresponding non-private analyses, leveraging the new concentration inequality in Proposition 1.\n\nA limitation is that the results apply only to Bernoulli reward distributions, which restricts the generality of the findings. While the technical content is solid and compelling, the paper addresses a rather niche problem (closing the constant gap between lower and upper bounds for differentially private multi-armed bandits) in a narrow setting (Bernoulli rewards). The limited scope of the contribution is my main reservation about the paper.\n\nMinor comment:\nTypo on line 85: “uppe bound” → “upper bound”", "was_revised": true, "final_justification": "As mentioned in my review, the technical content of the paper is solid. However, the work addresses a rather niche problem: closing the constant gap between lower and upper bounds for differentially private multi-armed bandits, in a narrow setting: Bernoulli rewards. Overall, I maintain my evaluation of the submission that is weak accept.", "rebuttal": "We thank Reviewer NvHt for the time spent reviewing, careful reading and precise questions.\n\n**W/Q1/Q2 - Limitation to Bernoulli distributions.** \n\nHere are the main elements about this point : (a) the regret lower bound (Equation 9) and privacy analysis (Proposition 2) in the paper are already valid beyond Bernoullis, (b) only the concentration inequality and the regret upper bound are specific to Bernoullis,  (c) it is possible to extend these two results, beyond Bernoullis, to sub-Gaussian or exponential distributions. (d) what is less clear is whether it is possible to obtain matching upper and lower bounds up to the constant for these distributions.  (e) Bernoulli bandits are a fundamental setting found in many applications and the takeaways from our analysis can be helpful beyond Bernoullis or stochastic MABs, (f) all prior work in bandits with DP is for either bounded or Bernoulli rewards, since it is important to control the sensitivity of the empirical mean to use the Laplace mechanism, (g) the improvement we introduce in this setting is non-trivial, and not just a constant factor (see answers to W2 and Q for Reviewer Xdjy). \n\nPlease refer to the answers to W3 and Q1 of Reviewer aTyM for a detailed discussion about each point.\n\n**Q3 - The analysis of DP-KLUCB/DP-IMED compared to their non-private versions.** \n\nIndeed, the analysis of DP-KLUCB and DP-IMED follows the general structure of the proof of their non-private versions. However, as explained in the Proof Sketch after Theorem 2, there are some technical challenges in the proof: (i) The main one is dealing with the adaptive batching strategy needed for privacy. To deal with this, the proof starts with a new regret decomposition different from the classic ones used in the non-private analysis, (ii) Dealing with the new $d_\\epsilon$-based indexes (Equations 10 and 11), in contrast to the KL-based ones in the non-private analysis. For the analysis to still work, we had to prove some technical properties on the $d_\\epsilon$ divergence (Lemmas 7, 8 and 9).\n\n**Q4 - The infimum in $d_\\epsilon$ and computational efficiency.** \n\n(a) The expression of $d_\\epsilon$: For Bernoulli distributions, we present a closed-form expression of $d_\\epsilon(\\mu_a, \\mu^\\star)$ in Equation 8. This expression shows that the infimum is always attained, and even provides a closed-form expression of the value at which this infimum is attained:\n\n- In the low privacy regime (when $\\epsilon$ is big), $d_\\epsilon$ reduces to the kl, which means that the infimum is attained at the left corner of the interval, i.e., $z^\\star = \\mu_a$.\n\n- In the high privacy regime, the expression of Equation 8 indicates that the values at which the infimum is attained is $z^\\star = \\frac{\\mu^\\star}{\\mu^\\star + (1 - \\mu^\\star) e^\\epsilon}$, which is always inside the interval $[\\mu_a, \\mu^\\star]$ for the values of $\\epsilon$ in this regime. Finally, when $\\epsilon \\rightarrow 0$, the infimum is attained at the right corner of the interval, i.e., $z^\\star = \\mu^\\star$. Please refer to Lemma 7 in the appendix for a proof of Equation 8.\n\n- Beyond Bernoullis, there may be no closed-form solution for $d_\\epsilon$, which depends on whether there are closed-form expressions of the KL and the TV. For example, the TV between two Gaussians with different covariances has no simple formula. On the other hand, the infimum can be shown to always exist, as the expression to be minimised is an interpolation of the kl and tv, so it is continuous and convex on a compact interval.\n\n(b) Computational efficiency: Again, for Bernoullis, we have a closed-form expression in Equation 8, and it is a straightforward computation. This may indeed be a different question for distributions beyond Bernoullis. But again, since the objective is convex and the interval is compact, it is possible to run off-the-shelf convex optimisation solvers to compute $d_\\epsilon$ for distributions beyond Bernoullis.\n\nWe thank the Reviewer for this question, which we will include in an added 'Generalisations Beyond Bernoullis' paragraph.\n\nWe hope that our response addresses the reviewer's questions, and will convince them to raise their score."}, {"review_id": "Dp0HUL97Bh", "reviewer": "Reviewer_aTyM", "summary": "This paper investigates regret minimization in Bernoulli bandits under $\\epsilon$-global Differential Privacy (DP). The authors first define DP in the context of bandit settings, formalizing privacy constraints for sequential decision-making. They then derive a tighter regret lower bound for the general problem. Next, they develop a new concentration inequality for sums of Bernoulli random variables with added Laplace noise, serving as a DP analog of the Chernoff bound. Based on this, they propose two algorithms, DP-KLUCB and DP-IMED, which operate in arm-dependent phases with geometrically increasing batch sizes. Finally, the authors prove the DP properties of these algorithms and establish regret upper bounds that asymptotically match the lower bound up to a constant arbitrarily close to 1, with numerical experiments validating their superior performance.", "questions": "(a) The current results, particularly the regret lower bound and algorithms, are specific to Bernoulli bandits. Could the authors discuss the potential for extending these results to other reward distributions, such as sub-Gaussian or heavy-tailed distributions? What specific challenges do they anticipate in such extensions, and are there any preliminary ideas or approaches to address these challenges? Additionally, can the strategy of using rewards from previous phases be applied to bandits with other distributions?\n\n(b) The design of the algorithms heavily relies on Proposition 1, a new concentration inequality. Could the authors provide intuition behind this proposition, explaining how it facilitates differentially private bandit algorithms? Additionally, how did the concentration inequality from Azize and Basu [2022] inspire the development of this new, tighter inequality?\n\n(c) The introduction highlights adaptive clinical trials as a motivating example. Could the authors provide a detailed description of how the proposed algorithms, such as DP-KLUCB and DP-IMED, could be applied in this context? Specifically, how do these algorithms ensure patient privacy while optimizing treatment allocation?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "(a) Quality:  The technical contributions of this paper include the proposed algorithms and the proofs for both the lower and upper regret bounds. The lower bound proof is particularly compelling, introducing a novel term (\\mathrm{d}_\\epsilon(\\mu_a, \\mu^*)) and employing a double change of environment technique to achieve a tighter bound. However, the algorithms appear as straightforward extensions of existing methods like , DP-KLUCB and DP-IMED,, lacking significant innovation in their formulation. Similarly, the upper bound proof adheres to standard methodologies in differentially private bandit literature, offering no novel technical insights.\n\n\n(b) Clarity: The paper is clearly written and well-organized, with a logical progression from motivation to empirical validation. However, it assumes substantial prior knowledge of differential privacy and bandit algorithms, such as KL-UCB and IMED, which may hinder accessibility for readers less familiar with these areas. To improve clarity, the authors could provide additional background on these concepts, perhaps in the introduction or an appendix, to broaden the paper’s accessibility.\n\n(c) Significance： This paper addresses regret minimization in differentially private bandits, building on prior work such as Azize and Basu [2022], and achieves a tighter lower bound, enhancing theoretical understanding. However, the theorem’s restriction to Bernoulli bandits limits its applicability to other reward distributions, potentially reducing its impact on the broader field. The algorithms’ primary novelty lies in using rewards from previous phases for parameter estimation, but the resulting improvement in regret performance is marginal, further constraining the paper’s practical significance.\n\n\n(d) Originality: The paper contributes a tighter lower bound, deepening the understanding of the current differentially private bandit model, and clearly distinguishes its contributions from prior work with appropriate citations. However, the originality of the algorithms is limited, as their design heavily relies on existing frameworks like DP-KLUCB, with minimal novel components beyond the use of historical rewards.", "was_revised": true, "final_justification": "I have added the score by 1, raising my rating from 3 to 4 in my previous reply. I think the paper can be accepted.", "rebuttal": "We thank Reviewer aTyM for the time spent reviewing, careful reading and detailed comments.\n\n**W1 - Straightforward extensions of existing methods**\n\n(a) *Novelty in algorithm design:* As explained in the Algorithm Design paragraph, there are two main novelties in our design:\n\n- Eliminating reward forgetting: This may appear as a minor change. However, it was previously believed (Hu et al. [2021]) that reward forgetting is fundamental to designing near-optimal DP bandit algorithms. Many works in similar settings (e.g., linear/contextual bandits, best arm identification) adopted forgetting. We show it is not necessary, and that this misconception arose from non-tight concentration bounds. Our result could inform improved bounds in related settings.\n\n- New $d_\\epsilon$ indexes (Eq. 10 & 11): This is the heart of every bandit algorithm design. Our new indexes tightly balance exploration and exploitation in an $\\epsilon$-aware way, targeting the lower bound. To derive them, we develop a new DP-Chernoff inequality (Proposition 1), the first in the DP bandit literature to consider jointly  the noise and the signal for tighter concentration. This result may be of independent interest.\n\n(b) *Technical novelty in the upper bound proof:* Please refer to Q3 of Reviewer NvHt. In short, the new proof handles the adaptive batching strategy and the new properties of $d_\\epsilon$ indexes.\n\n**W2 - Assuming substantial prior knowledge in DP and bandits**\n\nThank you for the suggestion. We will add an Extended Background section in the Appendix. It will include more details on KL-UCB, IMED, the Chernoff bound, and how these improve upon classic UCB in Bernoulli bandits.\n\n**W3 - Limited to Bernoulli with marginal improvement in regret**\n\nSince this is important, we stress the following points:\n\n(a) As explained in Point (c) of the Implications of Theorem 1 (Line 244), our regret lower bound holds for *any* class of distributions.\n\n(b) Proposition 2 shows that our algorithms are already $\\epsilon$-DP for any distribution supported on $[0,1]$. Generalising to bounded rewards in $[a, b]$ just requires scaling the noise terms by $(b - a)$. Removing forgetting relies on adaptive composition, not on any stochastic assumptions on the rewards. The only important element is to be able to control the sensitivity of the empirical mean to guarantee DP using the Laplace mechanism.\n\n(c) The parts of the paper that are only valid for Bernoulli distributions are: the concentration inequality (Proposition 1) and the regret upper bounds (Theorem 2).  It is also worth noting that the same regret upper bounds of Theorem 2 are also valid for distributions over $[0,1]$, since to prove these results, we only used the Chernoff bound for Bernoulli distributions, which is also valid for distributions over $[0,1]$.\n\n(d) We believe both the concentration inequality and regret upper bound could be extended to sub-Gaussian or exponential families. What’s unclear and more technical is whether matching upper and lower bounds (up to the constants) can be achieved beyond the Bernoulli case. See Q1 below for more.\n\n(e) Bernoulli bandits are a fundamental setting found in many applications (clinical trials, ad recommendations through clicks, etc). Studying the exact cost of DP in this setting helps focus on the tradeoffs introduced by the DP constraint, without all the technical overhead introduced by other distributions of rewards. Finally, the takeaways from our analysis can be helpful beyond Bernoullis or stochastic MABs:\n\n1. $d_\\epsilon$ is the information-theoretic quantity that tightly characterises the hardness of DP bandits. We believe that $d_\\epsilon$ will appear in other DP bandit settings (e.g., contextual/linear, RL), other accuracy measures (BAI with fixed confidence/budget) or even beyond bandits (sequential hypothesis testing, sequential mean estimation, etc).\n\n2. Forgetting is *not* a necessary design choice. Prior work (Hu et al. [2021]) conjectured it was essential to design near-optimal DP bandit algorithms. Our results show otherwise, and can improve many later works that built on this design choice.\n\n3. Our tight concentration inequality for the sum of Bernoulli and Laplace variables is of independent interest and can improve DP accuracy in other continual observation settings.\n\n(f) All prior work in stochastic DP bandits also focused on Bernoulli or bounded rewards. For bounded rewards, designing exactly optimal algorithms is already technical (even without DP), making DP analysis harder to follow.\n\n(g) *Marginal improvement:* We would like to stress that our result improves a problem-dependent quantity that can be arbitrarily large, especially for Bernoulli means near 0 or 1. See Reviewer Xdjy's W2 and Q for more.\n\nWe will include a detailed \"Generalisations Beyond Bernoullis\" paragraph in the updated version.\n\n**Q2 - Intuition behind Proposition 1 and differences to prior work**\n\n(a) *Intuition:* Proposition 1 is a DP analogue of Chernoff’s bound (Lemma 11). It controls the concentration of the empirical mean of Bernoulli variables estimated privately by aggregating Laplace noise over phases. The estimator includes $n_m$ Bernoulli variables and $m$ Laplace noises. The key insight is: if $m = o(n_m)$ (which holds under our geometric batching), then the dominant term in concentration is $e^{- n_m d_\\epsilon}$. This is the main ingredient needed to prove a regret bound in $\\log(T)/d_\\epsilon$. Prior work focused on reducing noise additions but sacrificed tightness in concentration.\n\n(b) *Comparison to prior work:* Lemma 4 in Azize and Basu [2022] (and others) gives concentration of noisy means using Laplace noise. However, as noted in Point (c) after Proposition 1 (Line 269), they apply a union bound that *separates* the Bernoulli and Laplace components, then apply Hoeffding to each. Using this naive concentration in our 'no-forgetting' setting would result in regret bounds with extra poly-log$(T)$ factors. To match exactly the lower bound, our proof uses a *coupled treatment* of Laplace noises and Bernoulli variables. Please refer to Appendix D for the details of this coupled treatment.\n\n**Q1 - Extension beyond Bernoulli bandits**\n\nAs stated in W3, the two key components needing generalisation beyond Bernoulli are Proposition 1 and Theorem 2. We believe the “coupled treatment” approach from Proposition 1 could extend to exponential and sub-Gaussian families. What is unclear is whether the $d_\\epsilon$ term would still appear in the exponent. As detailed in Q2 above, this is key to matching the lower bound.\n\nFinally, as the current privacy analysis is only valid for bounded rewards, to have a complete privacy/utility analysis, the class of rewards to be considered should be something like 'bounded sub-Gaussians' or 'bounded exponential families'.  Achieving matching bounds in these distributions is already technically challenging, even without DP.\n\n**Q3 - Application to clinical trials**\n\nIn adaptive clinical trials, treatments are allocated sequentially. At step $t$, patient $p_t$ arrives, the doctor assigns treatment $a_t$, and observes reaction/reward $r_t$ ($=1$ if cured, $0$ otherwise). The goal is to maximise cured patients (minimise regret) while protecting the privacy of the patients.\n\nHere, the private data is $(r_1, \\dots, r_T)$, since the reaction of a patient may reveal sensitive health information. The privacy risk is that publishing actions $(a_1, \\dots, a_T)$ might leak information about the private rewards $(r_1, \\dots, r_T)$.\n\nRunning DP-KLUCB/DP-IMED to recommend adaptively the allocations $(a_1, \\dots, a_T)$ ensures that even if an adversary knows the reactions of all but one patient, the adversary cannot infer that patient’s membership to the trial by looking at $(a_1, \\dots, a_T)$. The $\\epsilon$-DP guarantee controls this inference risk via a trade-off between Type I and II errors of the adversary, depending on $\\epsilon$. Among all algorithms satisfying that same privacy guarantee, DP-KLUCB and DP-IMED achieve the lowest regret.\n\nThe same applies to other DP bandit applications, like ad recommendation through users' clicks or private hyper-parameter tuning of models.\n\nWe hope that our response addresses the reviewer's questions, and will convince them to raise their score."}]

Author rebuttal:

Meta-review: The paper studies the multi-armed bandit problem with global differential privacy, and establishes matching lower and upper regret bounds. The contributions include: a tighter lower bound based on a new divergence that interpolates between KL-divergence and total variation distance, an improved concentration inequality, and differentially private variants of two asymptotically optimal bandit algorithms that are shown to match the regret lower bound. Although this paper addresses a rather niche problem (closing the constant gap between lower and upper bounds for differentially private multi-armed bandits) in a narrow setting (of Bernoulli rewards), which limit its contributions and broader impact, the reviewers all agree that this paper is technically solid. Based on their comments, I recommend Accept. 

The authors are encouraged to incorporate the reviewers’ comments and polish the presentation during preparing the final version.
Decision: Accept (poster)