When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits
Authors: Achraf Azize
Debabrota Basu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
Multi-armed Bandits
Regret Analysis
Stochastic Linear Bandits

Abstract: We study the problem of multi-armed bandits with ε-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits that quantify the hardness of bandits with ε-global DP. These bounds suggest the existence of two hardness regimes depending on the privacy budget ε. In the high-privacy regime (small ε), the hardness depends on a coupled effect of privacy and partial information about the reward distributions. In the low-privacy regime (large ε), bandits with ε-global DP are not harder than the bandits without privacy. For stochastic bandits, we further propose a generic framework to design a near-optimal ε global DP extension of an index-based optimistic bandit algorithm. The framework consists of three ingredients: the Laplace mechanism, arm-dependent adaptive episodes, and usage of only the rewards collected in the last episode for computing private statistics. Specifically, we instantiate ε-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB and AdaP-KLUCB. AdaP-KLUCB is the first algorithm that both satisfies ε-global DP and yields a regret upper bound that matches the problem-dependent lower bound up to multiplicative constants.

When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits
Achraf Azize and Debabrota Basu
Équipe Scool, Univ. Lille, Inria, CNRS. Centrale Lille, UMR 9189- CRIStAL
F-59000 Lille, France
{achraf azize, azize, debabrota. basu] @inria.
Abstract
We study the problem of multi- bandits with e-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits that quantify the hardness of bandits with e-global DP. These bounds suggest the existence of two hardness regimes depending on the privacy budget In the high-privacy regime (small c), the hardness depends on a coupled effect of privacy and partial information about the reward distributions. In the low-privacy regime (large e), bandits with e-global DP are not harder than the bandits without privacy. For stochastic bandits, we further propose a generic framework design near-optimal c-global DP extension of mnde--based optimistic bandit algorithm. The framework consists of three ingredients: the Laplace mechanism, uem-deeendent adaptive episodes, and usage of only the rewards collected in the last episode for computing private statistics. Specifically, instantiate e-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB and AdaP-KLUCB. AdaP-KLUCB is the first algorithm that both satisfies e-global DP and yields regret upper bound that matches the problem- dependent lower bound up to multiplicative constants.
Introduction
Multi-armed bandit problems, in short bandits, are model for sequential decision-maie making with partial information (Lattimore and Szepesvári] 2018). In bandits, learner sequentially interacts with an environment, which is of unknown distributions (or arms actions), over T N steps. T' is referred to as the horizon. At each step t E {1..... T), the learner chooses an arm A from {1..... K} and the environment reveals a reward r, from the distribution VA.- The learner's objective to maximise its cumulative reward Σ rs. An equivalent performance metric for bandit algorithm is regret. Regret is the difference between the expected cumulative reward collected by pulling the optimal arm a for T times and the expected cumulative reward obtained by using म. Regret is the price paid by the bandit algorithm due to partial information about the reward distributions. The goal of a bandit algorithm is to minimise its regret. Bandits, introduced widely studied and deployed in real-life applications,
in [Thompson) 1933) for medical trials, such as online advertising (Schwartz et al.) 2017). recommendation systems (Silva et al.) (022)) and investment portfolio design (Silva et al. 2022). Sensitive data of individuals, such as health conditions, personal preferences, financial status etc., are utilised in these applications, which raises the concern about privacy.
In bandit-based recommendation systems, the learning algorithm selects item for each user. The user decides whether or not to click the recommendation. Based on the click clickfeed feedback, the bandit algorithm improves its subsequent recommendations. Here, an action corresponds to an
Example 1.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

item and reward corresponds to whether a user clicks on the item (1) or not (0). A change in user's preference prompts changes the algorithm's 's output. As a result. even if the click feedback is kept private, the user's private information, i.e. their preference over items, is revealed. Privacy protection aims to prevent the algorithm's output from revealing the preferences of any specific user.
This example demonstrates the need for privacy in bandits. In this paper, we use Differential Privacy (DP) (Dwork and Roth 2014) as the framework for privacy, DP ensures that an algorithm's 's output is unaffected by changes in input at a single data point. By limiting the amount of sensitive information that an adversary can deduce from the output, DP renders an individual corresponding to a data point 'indistinguishable.. A calibrated amount of noise is injected into an algorithm to ensure DP. The noise scale is set to be proportional to the algorithm's ' sensitivity and inversely proportional to the privacy budget e.
To address the privacy issues in bandit applications, the problem of Differentially Private Bandits is coined and studied under different settings, such as stochastic bandits (Mishra and Thakurta 2015
Tossou and Dimitrakakis 2016 Sajed and Sheffet, 2019 Hu et al., (021), ). adversarial bandits (Tossou and Dimitrakakis 2017) and linear contextual bandits (Shariff and Sheffet 20118] 8 Neel and Roth
2018). Also, muluple adaptations of DP, namely local and global, are proposed for bandits (Basu et al. 2019). Local DP aims to preserve the privacy of the sequence of rewards obtained by sending noisy rewards to the algorithm (Duchi et al. 2013). Global DP allows the algorithm to access rewards without noise and aims to keep the sequence of rewards private while only the sequence of actions taken by the algorithm is produced to the public (Basu et al.) 2019). Though local DP provides stronger privacy as the data curator has no access to the original reward stream, it injects too much noise that leads to higher regret. Also, the fundamental hardness of local DP in bandits in terms of regret lower bound and also corresponding optimal algorithms are well-understood (Zheng et al. 2020). Thus, in this paper, we focus on the bandit problems with e-global DP. We aim to address two questions:
1. What is the fundamental hardness of differentially private bandits with global DP expressed in terms of the regret lower bound?
How to design an algorithmic framework that converts an optimistic and near-optimal bandit algorithm into near-optimal bandit algorithm satisfying global DP?
Our Contributions. These questions have led to the following contributions:
1. Hardness as Lower Bounds: We derive both the minimax (worst-case) and problem-dependent lower bounds on the regret of bandits with e-global DP for stochastic bandits (Thm. and B] Sec. Both the bounds show that the hardness depends on a trade-off between the privacy budget e and the distinguishability gap of a bandit environment. If the is bigger than the distinguishability gap, a bandit with global DP is not harder than a non-private bandit problem. Additionally, our problem-dependent regret lower bound (Thm. (3) provides novel observation that the difficulty of a bandit problem with global DP depends on the TV-indistinguishabiii gap (finf, Thm. (3). This was not known in the regret lower bound in (Shariff and Sheffet 20018), where the privacy dependent term in regret, i.e. K Tog(T) is independent of the hardness of the bandit instance. Our lower bounds explicates this missing link between the interaction of privacy and partial information. We also extend our techniques to derive the lower bounds for linear bandits with a finite number of arms (Thm. annd (5.. These lower bounds also reflect the same transition of hardness depending on and distinguishabilin gaps.
2. Algorithm Design:
Optimistic bandit algorithms used the empirical mean and variance of observed rewards to compute indexes and use them select an action. We propose three fundamental strategies to design private bandit algorithm from an optimistic algorithm (Sec. 4 a) add Laplacian noise to the empirical mean of each arm calibrated by the corresponding sensitivity, b) use adaptive episodes to compute the private empirical mean less number of times, and c) use only the observed rewards of the arm's 's last active episode] and forget everything before to keep the sensitivity of the empirical mean low. We deploy these techniques with UCB (Auer et al.) 2002) and KL-UCB (Garivier and Cappé, 2011) algorithms for non-private bandits to propose two near-optimal and e-global DP bandit algorithms, AdaP-UCB and AdaP- AdaP-KLUGE KLUCB (Sec. 4.. Both of these algorithms achieve near-optimal problem-dependent regret and also reflect a transition in hardness from a low to a high privacy regime
'The last active episode of an arm is the last episode in which that arm was played.

---

(Thm. 7 and 88. Both theoretical (Table and experimental (Sec.) results demonstrate optimality of AdaP-KLUCG than existing algorithms.
3. Technical Tools: (a) To derive the lower bound, we extend the Karwa- Vadhan lemma (Lemma
6.1, (Karwa and Vadhan 2017)) to the sequential setting (Lemma (b) We present novel sequential information processing lemma under e-global DP (Thm. [T) that controls the difference between the outcome streams of differentially private policy when interacting with two different bandit instances. (c) This leads to a generic proof structure, utilised to generate refined regret lower bounds under e-global DP for different settings. (d) To derive the regret upper bound, we develop a novel and general analysis of optimistic algorithms with adaptive episodes.
Our regret lower and upper bounds close the open question posed in (Tenenbaum et al. 2021I i.e. the problem-dependent regret bounds of differentially private bandits should depend on the KI-ddivergence between the reward distributions.
Related Works: Lower Bound. (Shariff and Sheffet 2018) first proposed a problem-dependeer lower bound on regret, M[max To
(ogg(T) for stochastic bandits with e-global DP. But this bound is restricted to Berooulii distributions of reward. In this paper, we provide the first meeblem-dependent regret lower bound that is valid for any reward distribution. This lower bound shows that the effect of privacy does not only depend on but also on the total variation distance corresponding to the environment. Thus, it explicates the coupled effect of privacy and partial information in a high-privacy regime, which was not observed before. To derive this tighter lower bound, we extend the Karwa-Vadhan lemma (Lemma 6.1, (Karwa and Vadhan, (017g) to a sequential and minimax lower bounds for stochastic and linear bandits. To our knowledge, these are the first regret lower bounds for linear bandits with e-global DP. Basu et al. (2019) also proposed minimax regret lower bound for stochastic bandits with e-global DP, However, our minimax lower bound (Thm. 2 tighter and does not need to assume that the reward distributions are Lipschitz continuous.
A.
c
setting and also propose a generic proof structure leading to problem-dependen
Related Works: Bandit Algorithms with e-global DP. DP-UCB (Mishra and Thakurta 2015] Tossou and Dimitrakakis 2016) was the first global DP version of UCB. DP-UCB uses the tree- based mechanism (Dwork et al. 2010a Chan al. 201T) to compute the sum of rewards. The tree mechanism maintains a binary free of depth log T') over the T streaming observations, where each node in this tree holds an i..d sample from a Laplace distribution with zero mean and scale (Iog(T)/<) At each step t, the mechanism yields the sum of the first t observations and the log(T) nodes on the root-to-the-laat path in the binary tree as the private empirical mean. As a result, the noise added to the UCB index per time-step is O (Iog(T)2 /c), which is responsible for the extra multiplicative factor log(T))1. in regret compared to the lower bound. DP-SE (Sajed and Sheffet 2019) was the first e-global DP algorithm to eliminate the additional multiplicative factor log( DP-SE is an e-global DP version of the Successive Elimination algorithm (Even-Dar ct al. 2002). However, the drawbacks were that the algorithm was not anytime, and was optimal only asymptotically, i.e. the horizon should be big enough. On the other hand, careful analysis of the algorithm suggests that what made the algorithm optimal was the fact that the algorithm was run in doubling episodes, where the private means computed at the end of the episode to decide which arms to eliminate, were only computed using the samples collected from that episode. We detect these ingredients and generalise them to propose general framework make any optimist index-based policy optimal fo followed by upper bounds matching the lower bounds ( (Table ( Similar techniques have been deployed to design a global DP extension of UCB in (Hu et al., 2021) but they have an additive factor log(T) extra in regret than AdaP-UCB and do not match our proposed regret lower bound. Also, DP-TS (Hu and Hegde, 2022) aims to achieve e-global DP with Thompson sampling based approach. The "lazy" version of DP-TS achieves a similar regret as AdaP-UCB. but does not achieve the refined lower bound of Thm. with the indistinguishability gaps. Even in non- non-private bandits, Thompson Sampling (Agrawal and Goyal 2013) is not known to achieve the Kullback-Leine (KL) indistinguihaabiiiy gap while KL-UUCB (Garivier and Cappé. 201T) is known to achieve it. Our work leads to the first near-optimal bandit algorithm with c-global DP, namely AdaP- -LUCB.
Here, a² is the optimal arm with mean reward μ² and A. - vr" Mo is the suboptimality gap of arm 'The number of private empirical mean reward statistics computed by the algorithm.
"Not using the full history of rewards compute the private empirical mean reward statistics.
3

---

Table 1: A comparison of e-global DP algorithms for bandits.
Algorithm
Regret
Private Means
Anytime
Forgetfulness
DP-UCB Mishra and Thakurta 2015:
Iun(T))
KT
Yes
No
Tossou and Dimitrakakis
2016
DP-SE
logtt3 + Eephar
loz(r)) D.
((log(T))
No
Yes
Sajed and Sheffet 2019
AdaP-UCB
o E Emppan
Au WoelT) muii 22g (ca5a] log
(llgg(T))
Yes
Yes
AdaP-KLUCB
(aaght" min(dd ()
((log(T))
Yes
Yes
2 Background: Differential Privacy and Bandits
Differential Privacy (DP). DP renders an individual corresponding to datum indistinguishable by constraining the output of an algorithm to almost the same under a change in one input datum.
Definition ((e, 5)-DP (Dwork and Roth 2014)). A randomised algorithm A satisfies (c, 6)- Differential Privacy (DP) if for any two neighbouring datasets 5 DD and D'' and for all sets of ouput O C Rango(A)
Pr(A(D) E Ol e <r E 5
where the probability space is over the coin flips of the mechanism A and some (e, 0) E R20 XR
5 = 0, we say that A satisfies e-differential privacy.
The Laplace mechanism (Dwork et al. (2010b; Dwork and Roth 2014) ensures cDD by injecting a random noise to the output of the algorithm that is sampled from calibrated Laplace distribution (as specified in Theorem 1. We use Lap(b) to denote the Laplace distribution with mean 0 and variance 212.
Theorem (E-DP of Laplace Mechanism (Theorem 3.6. Dwork and Roth 2014 )). Let us consider an algorithm f X + Ra with sensitivity s(f) A
max
[F(D) (D2)) Here,
D,D' x1 D HaHaming =1
Il-l1, is the Lı norm on Rd If noise samples [N:
i=1 generated independently from Lap( (())
the output injected with the noise, i.e. f(D) + [N1...., Na) satisfies c-DP.
The Laplace mechanism is originally proposed ensure DP when the input database is static. In sequential setting like bandits, a mechanism must update the published statistics as new data items arrive, and thus DP definitions are extended accordingly (Basu et al., (219))
Stochastic Bandits with Global DP. Now, we descrihe the general canonical bandit model (Section 4.6, (Lattimore and Śzepesvári, 2018)) and define global Differential Privacy (global DP) in this setting. A bandit algorithm (or policy) interacts with an environment v consisting of K arms with reward distributions 1/ for given horizon T and produces history Hr & {AA, RT) At each step t, the choice of the arm depends on the previous history H4-1. The reward R. sampled from the reward distribution VA, and is conditionally independent of the previous history H.-1. A bandit algorithm (or policy) ı can be represented by sequence (me)²= where n, : :4411 - [K] is probability kernel. Thus, we denote the probability of occurrence of sequence of actions TTa= |rT) -
K
aT [an, ........000 arl given sequence of rewards TT & [[1....,,ru]
I (((a)) an, F1, -.... rt-)- Iewe consider a" as the output of a bandit algorithm and T.T as the input, laa (T) defines the corresponding probability distribution on the output space required for defining DP (Eq. (T). In order define DP in the sequential setup of bandits, the event-level privacy under continuous observations (Dwork et al., 2010b) framework is adopted. In this framework, if two data sequences differ on single entry at single time-step and are identical on all other time-steps, they are called neighbouring data sequences. A sequential algorithm is differentially private if its output sequence is not distinguishable from two neighbouring input sequences. This framework leads to the global DP definition for bandits (Mishra and Thakurta 2015 Basu et al. 2019).
Definition 2 (Global DP for Bandits). A bandit algorithm E II satisfies e-global DP, if TT) S TO.T T | "T) for every action sequence a" E [K]T and every two neighbouring reward sequences nT, T E IRT, which means that 2j E T] such that r, $ r'ss and V t $ j = r'. The set of all bandit algorithms satisfying e-global DP, i.e. II called the e-global DP policy class.
Neighbouring datasets differ only in entry, ie | D' Hamming 1.

---

Table 2: Regret lower bounds for bandits with e-global DP
Minimax
Problem Dependent
Stochastic Multi-armed bandit
DVVTK 1),
A, log Emd.so min(c, Scta)
inf ox) EnEd a log s.t. |all S An min ( (Ep))((A)
Stoachastic Linear bandit
expl dVT. exp(-6)
Now, we formally define the regret a bandit algorithm with e-global DP, namely n;, as
Regr( (F", (v) Expr
Σ
Rs
Σ ENE [Na(T)].
(T) A E [ is the number of times the arm is played till T. A. 2 (z) pa is suboptimality gap the arm a. The expectation is taken with respect to the probability measure action-rewee sequences induced by the interaction of x and The objective of the bandit algorithm σ' to satisfy e-global DP while minimising the regret over horizon T. regret lower bound of any e-global DP bandit algorithm in II quantifies the fundamental hardness of this problem.
Regret Lower Bounds for Bandits with e-global DP
The first question is how much additional regret we have to endure in bandits with c-global DP than the bandits without privacy. The lower bound on regret provides insight into the intrinsic hardness of the problem and serves target for the optimal algorithm design. this section, we prove minimax and problem-dependee lower bounds for stochastic and linear bandits under e-global DP. The We defer the proof details to supplementary.
proposed lower bounds are summarised Table 2
Stochastic Bandits. First, consider the stochastic bandit problem with K-arms (as in Section 2
Minimax Regret. We derive the minimax regret lower bound this bandit setting with c-global DP. Minimax regret is the lowest achievable regret by any bandit algorithm under the worst environment among a family of environments & with arms under consideration.
RegT
minimax
inf sup Regr(T", (TT, ,v) ET KEEK
Theorem 2 (Minimax lower bound). For any K and T K and the minimax regret of stochastic bandits with e-global DP satisfies
K
RegT.e
minimux
max
ST(KK-
(3)
27
131
without global DP
with c-global DP
Consequences of Theorem [ Equation (3) shows two regimes of hardness: high-privacy, correspond- ing to lower values of e, and low low-privacy, corresponding to higher values of In the high-privacy
regime, specifically for < 27
(K-1) the hardness depends only on the number of the arms
K and the privacy budget and is higher than the lower bound for bandits without privacy. In the
fow-privacy regime, i.e. for 2 without privacy. This indicates the phenomenon that for higher values of c, signifying lower privacy, bandits with global DP are not harder than the bandits without privacy. Especially, for significantly large T', the threshold between low and high privacy regimes is smaller than most of the practically used privacy budget values. For example, if T 108 and = 100, the bandits with and without global DP are equivalently hard for any privacy budget 0.05. This shows that for stochastic bandits, we can deploy very low privacy budgets (c) without losing anything in performance.
181
/
[K-1] the lower bound coincides with that of the bandits
27
Problem-dependen/ Regret: Similar to the lower bounds specific to the Bernoulli reward distribu- tions (Shariff and Sheffet 2018), the minimax bound indicates a separation between hardness due to global DP and partial information. To understand whether this observation is artefact of the
5

---

Bernoulli distribution and the worst-case environment considered in minimax bounds, we derive a lower bound on the groblem-dependers regret (Equation 2 for general reward distributions.
Before deriving the lower bound, we define two Cooommtiion-thorettii terms that quantify the dis- tinguishability of the specifie bandit environment v where the algorithm is operating from all other bandit environments with K arms and finite means. If M is set of distributions with finite means, and (u(P) is the mean of the reward distribution P M,, we define the KL-distinguishcailit gap as diat (P. μ², .M) - inf P.EM {DKL (P P') p > n²) and the TV-iistinguishaabiity gap as These two quantities indicate the min-
Vint (P.j² MM) A PEEM (TV (P ('): > p*). imum dissimilarity, in terms of KL--divergence and Total Variation (TV) distance, of the reward distribution of the optimal arm a" with any other distribution with a finite mean higher than j². For bandits without DP, the inverse of the KL-dditinguishabbiity gap quantifies the hardness to identify the optimal arm of the environment v under partial information (Lai and Robbins 1985).
Theorem 3 Problem-dependee
Regret Lower Bound). Let the environment & be set of K reward distributionn with finite means and a policy ne E Teoos (E) n IT be a consistent policy To over & satisfying e-global DP. Then, for all (P)) E E, it holds that
lim inf Regr (T',
Da
T-200
log(T)
a:A.>0 min dint (Pa, v²" Mo), 6 titine (Pas 1t Ma)
without global
e-global
Consequences of Theorem 3 Now, we summarise the interesting observations led by the lower bound.
Universality: The lower bound of Theorem 3 holds for any environment with K arms and reward distributions with finite means. This is the first general lower bound for bandits with e-global DP.
MM) A.. i.c. the 2. For Bernoulli distributions of reward: TV-distinguishabiiity gap tinl (Pas "", suboptimality gap of arm o, and the Kl--disinguishahility gap dinf (Pa, MM.) 2 24 Thus, our For Bernoulli rewards, our lower bound is able to retrieve the lower bound of (Shariff and Sheffer 2018) with explicit constants.
problem-dependent lower bound reduces to 22 min A
log
High- and Low-privacy Regimes: Like the minimax regret bound, the problem-depedded regret also indicates two clear regimes in regret due to high and low privacy (resp. small and large privacy duat' Pa..u"
budgets e). In the low- low-privacy regime, i.e. for Thus, there is loss in performance due to privacy diac(Pe..u"".
6f (PP.M" "M.]' the regret achievable by bandits
with global DP and without global DP are same.
in this regime. In the high-p gigh-privcy regime, i.e. for E < Gfurr(Pe.
the regret depends on a coupled effect of privacy and partial information. This effect is quantified by the inverse of the privacy budget times the inverse of the TV-distinguishabiiiyy gap. This interaction between privacy and partial information was not explicated by any of the existing lower bounds. In Section 4 we propose the AdaP-KLUCE algorithm that demonstrates the same interactive effect in its regret upper bound.
Stochastic Linear Bandits. In order to illustrate the generality of our results, and also to investigate how partial information and privacy in structured bandits, we derive minimax and problem-dependent regret lower bounds for stochastic linear bandits (Lattimore and Szepesvari (017). To perform the
regret analysis, we consider a simple linear model with parameter 0 E R and Gaussian noise. It implies that for an action A, E A C Rdd the reward is R2 (A,, 0) nh where T), N/ 1) is
sequence of independent Gaussian noises. The regret of policy is Reg, 0) & Eg ET,,A,
where suboptimality gap A. - max,'EA (a' - a, 0), and [- is the expectation with respect to the measure o outcomes induced by the interaction of the policy and the linear bandit determined by 0. Given this structure, we state the minimax and problem- -ebeededeeennentt regret lower bounds for stochastic linear bandits.
A policy æ is called consistent over class of bandits E if for all E E and p 0, holds that lim Rr(s.ll 0. We denote the class of consistent policies over set of environments E as Hoves (E).

---

Theorem 4 (Minimax regret lower bound), Let A= 1-1,11,11" and è = IR.. Then, for any e-global DP policy, we have that
exp(-2) 8
exp( (66 d
RogT minimax (A, 2 max
dvT.
(5)
4
without globat
e-global DP
Theorem 5 (Problem-dependens regret lower bound), Let A C Rd be finite set spanning I& and E IR be such that there a unique optimal action. Then, any consistent and e-global DP bandit algorithm satisfies
Regr (A.0)
lim liminf
log(T) 2 (c,,),
(6)
7-000
where the structural distinguishability gap is the solution of constraint optimisation
(A. inf aE(0,00) aEA
Σ
a(aa)aa such that ||all S min
0.54 2
(A)A
without global DP
with e-global DP
for all a E A with Du > O. Ha = EnEA a(a)aa,, and a structure-dependen constant Pa (AA)
Remarks. Theorems and 5 are the first minimax and problem-dependdnt regret lower bounds for linear bandits. The minimax regret bound also shows clear distinction between high- and low-privacy regimes for < 2exp(-4) bound, the difference between high- and low-privacy regimes is more subtle. The first constraint on ||a| --- is reminiscent of the Graves-Lai bound for structural bandits without privacy. The second constraint, i.e. 3cpa (A) captures the interaction between privacy and partial information under linear structure and in the
and 2 eexp(-4)/vZ For the problem-dependent
regime.
Proof Technique. In order to prove the lower bounds, we adopt the general canonical bandit model. The high-level idea of proving bandit lower bounds selecting two hard environments, which are hard to be statistically distinguished but are conflicting, i.e. actions that may be optimal in one is suboptimal other. This is quantified by upper bounding the per-step Kl.-divergence between action distributions for such hard environments, and then plugging in this upper bound in the Bretagnolle- Huber inequality to obtain a regret lower bound. Though this proof technique works to quantify the hardness due to partial information, we need to upper bound the "confusion" created due to global DP. Existing proofs use the information-processie To prove a general bound, we derive a sequential version of this lemma. The sequential version leads to an upper bound of the KL-divergence dependent on both the total-variation distinguishability gap and the privacy budget, and enables us show the coupled effect of privacy and cartial-ifformation in the high-privacy regimes. For details of the technical results, we refer to the Supplementary Material.
lemma of Karwa-Vadhan (Karwa and Vadhan 2017).
Stochastic Bandit Algorithms with e-global DP: AdaP-UCB & AdaP-KLUCB
In this section, we present a framework (Algorithm 7 to convert index-based optimistic algorithms into algorithms satisfying e-global DP. We instantiate this framework by proposing AdaP-UCB and ALUCC, and derive corresponding regret upper bounds.
Algorithm 1 A framework for e-global DP extension of an index-based bandit algorithm
1: Input: Privacy budget an environment v with K arms, parameter a > 3
2: Output: A sequence of T'aactions satisfying e-global DP
3: Initialisation: Choose each arm once and assign t = K
4: for = 1, do
Adaptive episodes of reward subsequences
5: Let = t+1
6: Compute A, = argmax, (4, - 1, Arm selection with private indexes (Eqn. 7
7: Choose arm A, until round t such that NA, = 2N > Douuling of episodes
8: end for
Index- -aaed Algorithms and Private Empirical Mean. We focus on index- bandit algorithms that compute the empirical mean of rewards of each arm at each step. Using the empirical means, they
7

---

compute an optimistic index for each arm that serves as a high-probabbility upper confidence bound on the true mean of the corresponding arm. Examples of such algorithms with empirical mean- based indexes include UCB (Auer et al., 2002), MOSS (Audibert and Bubeck 2010), KL.-UCB (Garivier and Cappé 2011) IMED (Honda and Takemura 2015) etc. Here, the empirical mean is the main statistics of reward sequences used by the algorithms. Thus, by post-processing lemma, designing an e-global DP bandit algorithm reduces to computing the empirical means privately.
By Theorem | we know that adding a Laplacian noise with scale s(ft)/e to each empirical mean turns it c-DP, where s(βe) is the sensitivity of empirical mean far at step f. For K arms and horizon T. an index-based bandit algorithm computes the empirical mean KT times. Using the naive composition of e-DP, a first baseline is to make each computed empirical mean -DP. This needs us to add at each step noise scaled linearly to T. This might lead the corresponding bandit algorithm to yield a linear regret. Thus, we need to add noise less number of times and with lower sensitivity.
Empirical Mean using Reward Sub-sequence. The improvement is invoked by the observation that a bandit algorithm does not need to calculate the empirical mean at each time-step using all the rewards observed till that step. Thus, motivated by the DP-SE (Sajed and Sheffet 2019). we calculate the empirical mean less number of times by exploiting an episodic structure that we will explicit later. Specifically, we use only the rewards of the last episode. We formally express this trick in Lemmal D|
Lemma 1. Let us define the private empirical mean of the rewards between steps i and j (i < f) as
(r r
j- Σ r Lap
(G-1ye)
If < 11 < ... < te < T and Tt E [0, the mechanism o mapping the sequence of re- wards (21, TT) to (e + 1)-riivtte empirical means (T (121h, ...,, (reerr... FT satisfies e-DP.
Lemmal limplies that, if we calculate the empirical mean of cach arm é+ 1+11 (< T') times non- overlapping sequencessses of the reward stream, we only need to ensure that each empirical mean is e-DP with respect to the corresponding reward sub-sequence. These (e + 1) private empirical means together ensure that the sequence of (e + 1) computed indexes and the resultant action sequence of length T satisfy e-global DP by the post-processing lemma (Dwork and Roth 2014). Thus, we divide the horizon into (e + 1) epiisodes. This allows us to take T actions only by computing È + 1 private empirical means with the rewards observed in the last active episode of the arm. Specifically, for each& 1 E [4, 4i+1 - 1]. we play the same arm that was decided at the beginning of the episode, i.e. at 4,, with the private empirical mean computed from the last active episode of that arm.
daptive Episodes with Doubling. In order to set the episode lengths, we focus on the specific structure of the bandit process. Specifically, we know that sub-optimal arm should be sampled at times before discarding. Since the empirical means are computed using only
least n. = O (T) rewards of one episode, to yield a near-optimal regret, the length of the episode should be greater at any given time than Na. To satisfy this criterion, we deploy adaptive episodes with doubling.
AZ
Example 2 (Illustration of Algortihm [.. To clarify the schematic, we illustrate few steps of executing Algorithm 7 in Figure [ After playing each arm once, the first episode begins at I1. To observe different ingredients, we focus on step t1- = 7. The index of Arm 1 at t1 uses the private empirical mean i + Lap( 2e) to build high probability upper bound of the real mean μ1 with confidence t The index of Arm 2 uses To + Lap( If we assume that the index of Arm I is higher at ts. Arm I is played for a full episode from ta until ts - 1. The last time, when Arm I was played, the length of the episode was 2. Thus, following ta, the length of the episode is doubled to 4.
Theorem 6 (e-global DP). If Is is computed using only the private empirical mean of the rewards collected in the last active episode of arm a, Algorithm [ satisfies e-global DP.
Proof. The main idea is that change in reward will only affect the empirical mean calculated in one episode, which is made private using the Laplace Mechanism and Lemma []] Since the actions are only calculated using the private empirical means, the algorithm is e-global DP following the post-processing lemma. We refer to Appendix D for a complete proof.
Now, to concretise an algorithm, we only need to explicit how the indexes are calculated. In other words, we need build high-probability upper confidence bound on the true mean of an arm only using a private empirical mean. We instantiate the design details for AdaP-UCB and AdaP-KLUCB.
8

---

Arm 2
12
76
F22
Arm
ri
r3
F4
77 78 rg
710
Step
f1
13 4
ts
Figure An illustration adaptive episodes with per-arm doubling.
AdaP-UCB and AdaP-KLUCB. Let fig be the empirical mean reward of arm a computed using the samples collected between t. (t) and (8)+-1 1. For episode E, v)a (c) la is the last active episode of arm a. In Example 1 (4) = 2 and 1/2 1/2(4) = 3. Thus, due to the doubling of episode length, the empirical mean corresponds to NNatte
samples of arm a. Since the rewards are in
[0, 1]. the private empirical mean as fa.. = i/a Lap (N-( satisfies c-DP (Theorem) Now, we want to ensure that (tz - I, a), computed using only H is high-probabblity upper bound on the true mean. Here, introduce specific indexes that satisfy this criterion.
a log((t))
alog(tt)
For AdaP-UCB:
(te 1, =
V 2 1 (N, 11 ex Noo -1
(7)
q E [0, (Kl.,) v alog(te) 2 Na -
For AdaP-KLUCB:
(1e 1, max
where i6,52 = Clipo.1 (Ph.e + 7 (fN,(te-1)
log((te)
mmax 10,
alog(tz)) ex Nx.tN((t-1)
}.1} is the private
empirical mean clipped between zero and one.
Theorem 7. For rewards in [), AdaP-UCB satisfies e-global DP, and for a > 3. it yields regret
Reg. v) S Σ min log(T) + a-3
16a
30
a:d,>00
Theorem 8. When the rewards are sampled from Bernoulli distributions, AdaP-KLUCE satisfies e-global DP, and for a > and constants Ci(a), C2 O, it yields regret
E (mint Ci(a)
3a
Regy (Agy(Adda
log(T)
+ a -
o:A.30 minnfdint(Mea )(), C2cAa]
Both the upper bounds show that for low-privacy regime, the regrets of AdaP-UCB and AdaP-KLUCE are independent of e, and in high-privacy regime, they depend on the coupled effect. In Ap- pendix E.4 we also derive moobeem-ndepennee
or minimax regret upper bounds for AdaP-UCB and AdaP-Ke ALLUC, which are /TTTTIBB log(T) + K Klog(T)).
Remark 1. controls the width of the optimistic confidence bound. Specifically, it dictates that the real mean is smaller than the optimistic index with high probability, i.e. with probability 1 1- + at step t. The requirement that >> 3 is due to analysis of the algorithm. To be specific, the requirement that a > is needed to use a sum--interal inequality in the proof of Theorem 71, Since the dominant terms in the regret upper bounds of both AdaP-UCB and AdaP-KLUCE are multiplicative in making a smaller will tighten the bound. We leave it for future work. We refer to Section G.3 for a detailed discussion choosing
Summary of Algorithm Design. We propose three ingredients design e-global DP version of a bandit algorithm (Algo. [. Firstly, add Laplace noise to make the empirical means private (Lemma T). Secondly, compute the index of collected from the last active episode of that arm and forget all the samples obtained before that. Thirdly, use adaptive episodes with doubling. At the beginning of episode choose the arm with the highest index and play it double number of times than the length of the last active episode of the arm.
using the private empirical mean of rewards
Experimental Analysis
In this section, we perform empirical evaluations to test two hypotheses: (i) AdaP-KLUCB is the most optimal algorithm among the existing bandit algorithms with e-global DP, and (ii) the

---

no priacy
global DP
10a
KLUCB
Rogret
Regret I
10
Hlggh Privccy
Low Privacy
DF-UCB(1 0.1)
109
Add--UCB(r S.1)
10s-
AddP KLUCB(o 3.1)
10
0.0
0.2
0.1
0.6
0.8
1.0
10"
Step L
x10"
Privacy budget
Evolution of regret over time for DP-UCB, DP-SE, AdaP-UCB, and AdaP-KLUCB with = 1. Each algorithm is run 20 times with T 10", and Bernoulli distribu- tions with means (0.75, 0.625, 0.5, 0.375, 0.25). AdaP-KLUCB achieves the lowest regret.
Figure 2:
Figure 3: Dependence of lower bounds and re- gret of AdaP-KLUCB with respect to the privacy budget e. We run AdaP-KLUCB for 20 runs with T 10". Echoing the theoretical analysis, re- gret of AdaP-KLUCB transits between privacy regimes and is independent of for low-privacy.
transition between high and low-loive www-privacy regimes is reflected in the empirical performance. Additional experimental results are deferred to Appendix G
Efficiency in Performance. First, we compare performances of AdaP-UCB and AdaP-KLUCB with those of DP-SE and DP-UCB. We set = 3.1 to comply with the regret upper bounds of AdaP-UCB and AdaP-KLUCB. We assign 7 0.1 for DP-UCB and / 1/l for DP-SE. We implement all the algorithms in Python (version 3.8) and
8 core 64-bits Intel i5 @ 1.6 GHz CPU. We test the algorithms for Bernoulli bandits with 5-arms and means {0.75, 0.625, 0.5, 0.375, 0.25) (as in Sajed and Sheffet (2019). We run each algorithm 20 times for a horizon T 10", and plot corresponding average and standard deviations of regrets Figure 2 AdaP-KLUCB achieves the lowest regret followed by AdaP-UCB. Both of them achieve 10 times lower regret than the competing algorithms.
Impact of Privacy Regimes. In Figure we plot regret of AdaP-KLUCB at T 107 for a Bernoulli bandit with mean rewards {0.8, 0. 0.1, 0.1, 0.1). We plot the average regret over 20 runs function of the privacy budget [0.05, 10]. As indicated by the theoretical regret lower bounds and upper bounds, the experimental performance of AdaP-KLUCH demonstrates two regimes: high-privacy regime (for e < 0.3), where the regret of AdaP-KLUCB depends on the privacy budget and low privacy regime (for > 0.3), where the regret of AdaP-KLUCB does not depend on
In brief, our experimental results validate that AdaP-KLUCB is the most optimal algorithm for stochastic bandits that satisfies e-global DP, and performance of AdaP -LUCCB transits from high- to cnw-privacy regimes, where performance turns independent of the privacy budget c.
Conclusion and Future Works
We revisit bandits with e-global DP. We prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits indicating two regimes of hardness. We propose framework to design an e-global DP version of an index-based optimistic bandit algorithm in a near-optimal fashion by utilising three ingredients: adding noise with Laplace Mechanism, using the empirical mean of rewards collected in the last active episode an arm, and adapting episodes with doubling.
One limitation of our analysis that the lower and upper bounds defer by multiplicative constants. would be technical challenge to merge this gap. Another future direction is derive regret lower bounds for other variants of DP, namely (c, 8DP and Rényi-DP (Mironov) (017), especially the structured bandits compatible with Gaussian noise injection and also to extend the proposed proof techniques in these settings. For the algorithm design, it would be interesting to see how the proposed ingredients generalise to linear and contextual bandits (Shariff and Sheffet 2018). and Markov Decision Processes (Vietri et al. 2020
Acknowledgments and Disclosure of Funding
This work is supported by the Al_PhD@@ PhD@Lille grant. D. Basu acknowledges Inria-Kyoto University Associate Team "RELIANT" for supporting the project. We also thank Philippe Preux for his support.
10

---

References
Agrawal, S. and Goyal, N. (2013). Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pages 127-135. PMLR.
Audibert, J.-Y. and Bubeck, S. (2010). Regret bounds and minimax policies under partial monitoring. The Journal of Machine Learning Research, 11:275-22836.
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-255
Basu, D., Dimitrakakis, C., and Tossou, A. (2019), Differential privacy for multi-armed bandits: What is it and what its cost? arXiv preprint 1rXiv:1905.12233
Chan, T.-H. H., Shi, E., and Song, D. (2011). Private and continual release of statistics. ACM Trans. Inf. Syst. Secur, 14(3).
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2013). Local privacy, data processing inequalities, and statistical minimax rates. arXiv preprint UrXiv:1302.322
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010a). Differential privacy under continual observation. In Proceedings of the Forty-Second ACM Symposium Theory of Computing, STOC 10, page 715-724, New York, NY, USA. Association for Computing Machinery.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010b). Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715-724, ACM.
Dwork, C. and Roth, A. (2014). The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, ((3-4):211-44)
Even-Dar, E., Mannor, S., and Mansour, Y. (2002). PAC bounds for multi-armed bandit and Markov decision processes. Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT '02, page 255-2700 270, Berlin, Heidelberg. Springer-Verlag.
Garivier, A. and Cappé, O. (2011). The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference on learning theory, pages 359-376. JMLR Workshop and Conference Proceedings.
Honda, J. and Takemura, A. (2015). Non-asymptotic analysis of new bandit algorithm for semi- bounded rewards. Mach. Learn. Res., 16:3721-3756.
Hu, B. and Hegde, N. (2022). Near-optimal thompson sampling-based algorithms for differentially private stochastic bandits. In Uncertainty in Artificial Intelligence, pages 844-852. PMLR.
Hu, B., Huang, Z., and Mehta, N. A. (2021). Optimal algorithms for private online learning in stochastic environment.
Karwa, V. and Vadhan, S. (2017). Finite sample differentially private confidence intervals.
Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22.
Lattimore, Т. and Szepesvari, C. (2017). The end of optimism? An asymptotic analysis of finite-armed linear bandits. Artificial Intelligence and Statistics, pages 728-737. PMLR.
Lattimore, T. and Szepesvári, C. (2018). Bandit algorithms. preprint.
Mironov, I. (2017). Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE.
Mishra, N. and Thakurta, A. (2015). (Nearly) optimal differentially private stochastic multi-arm bandits. In UAI.
Neel, and Roth, (2018). Mitigating bias adaptive data gathering via differential privacy. In International Conference Machine Learning, pages 3720-3729. PMLR

---

Sajed, T. and Sheffet, O. (2019). An optimal private Stochastic-MAB algorithm based on an optimal private stopping rule.
Schwartz, E. M., Bradlow, E. T., and Fader, P. S. (2017), Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522.
Shariff, R. and Sheffet, O. (2018). Differentially private contextual linear bandits. In Advances in Neural Information Processing Systems, pages 4306.
Silva, N., Werneck, H., Silva, T., Pereira, A. C., and Rocha, L.. (2022). Multi-armed bandits in recommendation systems: A survey of the state-of-the-art and future directions. Expert Systems with Applications, 166:6.
Tenenbaum, J., Kaplan, H., Mansour, Y., and Stemmer, U. (2021). Differentially private multi- bandits the shuffle model. Advances in Neural Information Processing Systems, 34:24956- 24967.
Thompson. W. R. (1933). On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-299)
Tossou, A. C. and Dimitrakakis, C. (2016). Algorithms for differentially private multi-armed bandits. In Thirtieth AAAI Conference on Artificial Intelligence.
Tossou, C. and Dimitrakakis, C. (2017). Achieving privacy in the adversarial multi-armed bandit. In Thirty-First AAAI Conference on Artificial Intelligence.
Vietri, G., Balle, B., Krishnamurthy, A., and Wu, S. (2020). Private reinforcement learning with PAC and regret guarantees. In International Conference on Machine Learning, pages 9754-9764. PMLR.
Zheng. K., Cai, T., Huang, W., Li, Z., and Wang, L. (2020). Locally differentially private (contextual) bandits learning.
12


Reviews:
[{"review_id": "fikrpuDE2u6", "reviewer": "Reviewer_B8Us", "summary": "This paper considers DP bandits under the central model. The authors present both minimax and problem-dependent lower bounds for both MAB and linear bandits. Then, they also establish a general method for designing private bandit algorithms based on non-private ones. Extensive numerical simulations are conducted to validate the theoretical results. ", "questions": "- My first concern is about the proof of the privacy guarantee in Section 4. The tricky part is that the adaptive batch schedule also depends on private data (rewards). Thus, an adversary can observe the batch schedule to infer the private data. More specifically, changing one reward in the sequence will also change the follow-up batch schedule. The standard proof cannot be directly applied here. I believe this can be handled by a careful but non-trivial argument, but I will first leave it to the authors in the rebuttal period. \n\n- My second concern is more general. This relates to the commonly-used notion of DP in bandits. In particular, the neighboring relation is about two neighboring reward sequences, i.e., differ in the reward value at only one particular time slot. This is inspired by the standard continual model of DP. However, this is not the right notion for DP in MAB. To see it, this notion requires that if one changes a reward at time $t$, the reward obtained at $t+1, t+2,...$ are still the same by the requirement of the neighboring definition. This is obviously not the case in MAB, since the policy would be different at   $t+1, t+2,...$ due to the change of reward at time $t$, and hence the agent will pull different arms and hence different rewards will be observed. Note that this is in sharp contrast to the classic continual observation DP model where the typical task is simply to count the current counts in the online stream data, where there is no correlation between the data across time slots, and hence the standard neighboring relation makes sense in terms of privacy protection. I think one can also propose a more meaningful notion of DP in bandits (with only a minor change of the current proof), but again I will leave it to the authors in the rebuttal period.\n\n- In fact, the intuition for the above two questions are quite related.", "limitations": "Yes,  limitations and potential negative societal impacts have been addressed. ", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**strengths**\n- A comprehensive study of lower bounds under the central model\n\n**Weaknesses**\n- The proof for the privacy guarantees in the upper bound part seems to need more care", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_jD7zvtP1Nq", "reviewer": "Reviewer_75rR", "summary": "This paper proves the minimax regret lower bound and problem-dependent regret lower bound for stochastic and linear bandits that quantify the hardness of bandits with $\\epsilon$-global DP. The results reveal interesting phase transition phenomenon in that in the high-privacy regime, the hardness depends on a coupled effect of privacy and partial information about the reward distributions; while in the low-privacy regime, the regret of bandits with $\\epsilon$-global DP reduces to that of bandits without privacy. In the algorithm, the authors then propose AdaP-UCB and AdaP-KLUCB methods which are $\\epsilon$-global DP extensions of UCB and KL-UCB algorithms, respectively. AdaP-KLUCB is shown to be the first algorithm that both satisfies $\\epsilon$-global DP and yields a regret upper bound that matches the problem-dependent lower bound. \n", "questions": "See above weakness part.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\n1. In spite of a very theoretical paper, this paper is very well written and is easy to follow. \n\n2. DP in bandit algorithms has received recent attentions. The hardness of local DP in bandits in terms of regret lower bound has been well studied in the literature. However, fundamental hardness of differentially private bandits with global DP is less studied, except for Shariff and Sheffet (2018). \n\n3. The proposed algorithm is able to achieve a regret upper bound that matches the problem-dependent lower bound.  \n\n\nWeaknesses\n\n1. Technical novelty beyond Shariff and Sheffet (2018). Shariff and Sheffet (2018) studied the problem-dependent lower bound on regret for stochastic bandits of Bernoulli reward with $\\epsilon$-globally DP. This paper extends the results to general reward case. It is important to explicitly highlight the technical contributions beyond Shariff and Sheffet (2018) . \n\n2. In the experiments, the proposed algorithms were compared to the benchmark methods DP-SE and DP-UCB. However, there are some recent developments, e.g., DP-TS by Hu and Hegde (2022), on differentially private stochastic bandits. DP-TS and its lazy version are shown to be superior over DP-SE. It is important to compare with the state-of-the-art methods. \n\nHu and Hegde (2022), Near-Optimal Thompson Sampling-based Algorithms for Differentially Private Stochastic Bandits, UAI.\n\n3. Can authors provide some discussion on the requirement $\\alpha > 3$ in algorithms and theorems? I noticed that $\\alpha =1$ actually works the best as shown in the additional simulation results in the supplementary materials.\n\n4. The authors claim that Figure 3 show that in the low privacy regime ($\\epsilon > 0.3$), the regret of AdaP-KLUCB does not depend on $\\epsilon$. However, what I observe is that when $\\epsilon > 0.3$, the regret first decreases when $\\epsilon$ increases and then stabilizes. This step-shape decreasing pattern is consistent even when $\\epsilon < 0.3$. Therefore, more convincing numerical evidence would be helpful to justify this claim. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "IYQwvWwpjt", "reviewer": "Reviewer_8hyR", "summary": "This paper studies the regret minimization problem for stochastic (Bernoulli and linear) bandits under the notion of global differentially privacy. This is a thorough study of the problem where the authors propose lower bounds quantifying fundamental problem hardness, an algorithmic framework and upper bound on the regret for the proposed algorithms under this framework. These results are supported by sound numerical findings. Some highlights: \n\n-- Two sets of lower bound results are provided: problem-dependent and minimax. The key lemma driving these results is a non-trivial extension of Karwa-Vadhan lemma which bounds the differential privacy when the data is generated from non-identical distributions. \n\n-- The algorithmic developments are novel from a bandit perspective more-so than from a privacy perspective, particularly, the idea of adaptive phases which is the key driver in ensuring the privacy of the algorithm. \n", "questions": "-- A natural idea would be to use a tree-based aggregation technique for adaptively keeping track of the means. It is not completely clear to me how adaptively using doubling horizon ensures the same privacy level. Further, the privacy proofs do not require composition which is surprising. I would like to be convinced if this is due to the definition of Global DP or a consequence of the algorithmic template. \n", "limitations": "A contextual bandit extension would be nice esp. since the authors get rid of tree-based aggregation. But there the adaptive-doubling idea might not work since the minimum eigenvalue of the covariance matrix would need to be updated regularly in order to have consistent parameter estimate. ", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n-- Non-trivial novel theoretical contributions for both lower bound and upper regret bound. Some of the key results (for eg., Theorem 10) could be of independent interest and have wider application. The key implication of the lower bound is the phase transition behavior of bandits depending on the privacy budget. This has implications particularly because in the low-privacy regime, the problem is equivalent to the non-private setting.\n\n-- The general purpose framework proposed for algorithmic design unifies existing bandit algorithms. This is a much deeper contribution than proposing and analyzing a single algorithm. I believe this makes the contribution very fundamental.\n\n-- Numerical results are also done for a variety of privacy budget though it would interesting if they could demonstrate the lower bounds as well as study the dependence on $\\alpha$. A\n\nWeakness: \n\n-- More discussion regarding the parameter $alpha$ and how to tune it. A small discussion regarding this possibly in the main body of the paper. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "29fdSce3mVr", "reviewer": "Reviewer_9pTm", "summary": "This work investigates $\\epsilon$-global differential privacy for multi-armed bandits. For both stochastic and linear bandits, it derives refined instance-dependent and global lower bounds on the regret for differentially private learning, in that they quantify the burden of privacy in two distinct regimes. Crucially, in the low-privacy regime, the privacy constraint doesn't make the bandits problem any harder. Next, the work formulates a general $\\epsilon$-global strategy for stochastic bandits and shows that two algorithms based on it have regret upper bounds with privacy regime patterns like those in the lower bounds. This is confirmed empirically, where the two privacy regimes are evident.", "questions": "1. It would be useful to clarify either in the abstract or in \"Our Contributions\" that the regret lower bounds effectively generalize the claims of [1] in generalizing it beyond Bernoulli to general distributions. My point is that there was prior work hinting at distinct regimes of privacy and I think it's a good idea to acknowledge that at the outset.\n2. It would be useful to discuss the gap between the lower bounds and the upper bounds for AdaP-UCB and AdaP-KLUCB. If feasible, instance-independent upper bounds would also be useful to have.\n3. In Algorithm 1 (line 253), please clarify where $I_a^\\epsilon$ comes from. You mention index-based algorithm but never actually define $I_a^\\epsilon$.\n4. Please fix some minor typos (e.g. \"Algortihm\") through the manuscript.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper touches contributes to a very important theme in the context of differential privacy for bandits - the cost of obtaining this privacy - and identifies two distinct regimes of privacy preservation. Empirical results confirm the theory.\n- It materializes a simple $\\epsilon$-global DP strategy applicable to existing index-based bandit algorithms. This strategy clearly incorporates features that are known/desirable in the context of DP algorithms (e.g. Laplacian noise, private empirical means using little data).\n\nWeaknesses: Please see questions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept