Differentially Private Multi-Armed Bandits in the Shuffle Model
Year: 2021

Abstract:
We give an (ε, δ)-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model with a distribution-dependent regret of O ((∑ a∈[k]:∆a>0 log T ∆a ) + k √ log 1 δ log T ε ) , and a distribution-independent regret of O (√ kT log T + k √ log 1 δ log T ε ) , where T is the number of rounds, ∆a is the suboptimality gap of the arm a, and k is the total number of arms. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.

text: O ((∑ a∈[k]:∆a>0 log T ∆a ) + k √ log 1δ log T ε ) , and a distribution-independent regret
of O (√ kT log T + k √ log 1δ log T
ε
) , where T is the number of rounds, ∆a is the
suboptimality gap of the arm a, and k is the total number of arms. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.

heading: 1 Introduction
text: The multi-armed bandit (MAB) problem is a classical sequential decision-making problem in which an agent tries to maximize a cumulative stochastic reward [27, 23] under uncertainty. This problem, which is applicable to various areas such as recommender systems, online advertising and clinical trials, embodies the well known exploration-exploitation trade-off between learning the environment and acting optimally based on our current knowledge about the environment.
More formally, in the MAB problem at each time t = 1, . . . , T an agent chooses an arm i from the set [k] = {1, . . . , k} of k arms, and obtains an iid reward rt drawn from the unknown distribution Ri over {0, 1} with expectation µi = E [Ri]. Let a∗ = arg maxa µa be an arm with the largest expected reward, and denote this reward by µ∗ = µa∗ . Let the (suboptimality) gap of an arm a to be the gap between its expected reward and that of a∗, i.e., ∆a = µ∗ − µa. The agent’s goal is to maximize the total expected reward, or rather to minimize the expected regret R(T ) = T · µ∗ − E [∑T i=1 r t ] defined to be the expected gap between the algorithm and the optimal algorithm that knows the distributions Ri.
In this work we address the privacy in such a setting. As a motivating example, consider an advertisement system in which the server presents to each user an advertisement a ∈ [k]. The user then decides whether to click on the advertisement or not. This click decision depends on different private characteristic of the user. The user then reports to the server whether it clicked on the advertisement (in which case its reward is r = 1) or not (r = 0). From this example, it is clear that r is private information of the user, and using traditional algorithms for the MAB problem incautiously might leak user-private data.
In order to mathematically alleviate privacy concerns, Dwork et al. [11] defined the notion of differential privacy (DP), which requires that the output of the computation has a limited dependency ∗Google Research. jayten@google.com. †Blavatnik School of Computer Science, Tel Aviv University and Google Research. haimk@tau.ac.il. ‡Blavatnik School of Computer Science, Tel Aviv University and Google Research. mansour.yishay@gmail.com. §Blavatnik School of Computer Science, Tel Aviv University and Google Research. u@uri.co.il.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
on any single user’s data. Formally, a mechanism (ε, δ)-DP if for any pair of neighboring inputs (differing by a single user’s data), the probability that the mechanism outputs a value in any set B is not different by more than a multiplicative factor of eε and an additive factor of δ. Differential privacy has been extensively studied under many different sub-models of privacy. On one end of the spectrum lies the centralized model of differential privacy, where the users trust the server with their data, and the liability to protect user privacy lies on the server, who must make sure that any data published externally (e.g., aggregated statistics) respects the privacy constraints. On the other end of the spectrum lies the (strictly stronger) local model of differentialy privacy (LDP), where the user privatizes its own data prior to sending it to the server.5
Differentially private versions of the MAB problem have been considered in various previous works, where the private information are users’ rewards (two neighboring inputs differ by the reward value of a single user), and the algorithm’s output is the subsequent arm(s) it selects. Table 1 summarizes the best known distribution-dependent regret bounds for the various privacy models, together with our new result in the shuffle model which we soon define formally.
With real-world algorithms gradually moving away from the centralized model of privacy, the immediate question is “can we design a private algorithm for MAB with privacy guarantees which are similar to local DP, but with similar regret to centralized DP (without a multiplicative 1/ε2 factor)?”.
To address the inevitable gap between the local and centralized models, which is in fact common in the literature of differential privacy, the alternative shuffle model [6, 9, 13] explores the space in between the local and centralized models by introducing a trusted shuffler that receives user messages and permutes them (i.e., disassociates a message from its sender) before they are delivered to the server. For privacy analysis, we assume that the shuffle is perfectly secure, i.e., its output contains no information about which user generated each of the messages. This is traditionally achieved by the shuffler stripping implicit metadata from the messages (e.g., timestamps, routing information), and frequently forwarding this data to remove time and order information. The shuffle model ensures that sufficiently many reports are collected in each round so that any one report can hide in a shuffled batch. In order to apply the shuffle model to the MAB problem in the context of advertisements, we divide the algorithm into batches, where before each batch we decide on the fly its size m, and then present the m next users the same advertisement a, and finally apply a private shuffle model mechanism to their rewards to communicate reward aggregate information to the server.8
A constantly growing body of work presents new and improved mechanisms in the shuffle model for basic statistical tasks [16, 13, 12, 2], such as private binary summation, in which the server must privately approximate the sum of a collection of values x1, ..., xm ∈ {0, 1} held by the m users in
5Formally, in the non-interactive setting, a mechanism is (ε, δ)-LDP if for any two user inputs, the probability that the privatizer sends the server a value in any set B is not different by more than a multiplicative factor of eε and an additive factor of δ. 6The corresponding distribution-independent regret bounds usually simply replace the ∑ a∈[k]:∆a>0 log T ∆a
term with √ kT log T .
7This lower bound can be extended from (ε, 0)-LDP to (ε, δ)-LDP using arguments from Bun et al. [7] and Cheu et al. [9] since we focus on single-round (non-interactive) mechanisms in which the user can only send information to another party once.
8We remark that a given user does not know in advance the size of the batch in which it participates, since this size depends on the algorithm’s run.
the shuffle. For private binary summation, the optimal achievable errors in the central, local and shuffle model are Θ̃(1/ε) [11], Θ̃( √ m/ε) [5, 8] and Θ̃(1/ε) [9] respectively, where the Θ̃(·) hides poly-logarithmic terms. Similar errors hold for the private summation problem which approximates the sum of real values in [0, 1].

heading: 1.1 Our contributions
text: To the best of our knowledge, our work is the first to consider the MAB problem under the shuffle model of differential privacy. In order to support the online nature of the MAB problem, we consider a variant of the shuffle model. As opposed to the classical shuffle model, in which the shuffle size is unbounded and the mechanism runs only once, we continuously run shuffle mechanisms for many disjoint batches of users who can only afford a single round of communication.9
We consider the paradigm where the server controls the different users who are cooperative and communicate only with the server. We give a rigorous definition of shuffle differential privacy (SDP) for the multi-armed bandit problem (assuming binary rewards), and give and prove the first two such algorithms. Our algorithms Shuffle Differentially Private Arm Elimination (SDP-AE) and Variable Batch Shuffle Differentially Private Arm Elimination (VB-SDP-AE) are both based on the well-known arm elimination (AE) algorithm, using consecutive batches of users and together with an SDP private binary summation mechanism.
We show that the simpler but weaker SDP-AE achieves a distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a
) +
k log 1δ ε2
) , and a distribution-independent regret of
O (√
kT log T + k log 1δ ε2
) .10
We then describe VB-SDP-AE, a generalization of SDP-AE to exponentially growing batch sizes, and prove it has a distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a
) + k √ log 1δ log T
ε
) , and
a distribution-independent regret of O (√ kT log T + k √ log 1δ log T
ε
) .
Note that, compared to the local model (Ren et al [22]), the regret of both SDP-AE and VB-SDP-AE is improved, by having the dependency on 1/ε be additive rather than multiplicative. In addition, VB-SDP-AE almost matches the regret of the best known algorithms for the centralized model,
that is the distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a ) + kε ) of Tossou and Dimi-
trakakis [28].

heading: 1.2 Related work
text: The differentially private MAB problem has been considered in many previous works [19, 17, 21]. Shi and Shen [26] and Dubey and Pentland [10] studied MAB and linear bandits respectively in the federated setting. Zheng et al. [29] studied contextual bandits with LDP. Batched MAB with a predetermined number of batches was studied in [14, 15].
For the private summation problem, Cheu et al. [9] gave unbiased (ε, δ)-SDP mechanisms over binary inputs and real inputs in [0, 1], with error roughly √ log(1/δ)/ε and log(1/δ)/ε, respectively. In several works of Balle et al. [2, 3, 1], they gave a biased (ε, δ)-SDP mechanism for real inputs in [0, 1] with similar error and a constant number of messages, and a single-message (ε, δ)-SDP mechanism with optimal error.
9Beimel et al. [4] showed that every centralized-DP mechanism can be emulated in the shuffle model in two (communication-intensive) rounds of communication, however these results are not applicable to our setting since we assume that each online user participates only in one shuffle and then disappears.
10In this paper, we assume that T is known apriori. Otherwise, we can apply standard doubling arguments to get roughly the same results.

heading: 2 Background and preliminaries

heading: 2.1 Shuffle-model privacy
text: In the well-studied setting of shuffle model privacy, there are m users, each with data xi ∈ X . Each user applies some encoder E : X → Y ∗ to their data and sends the messages (yi,1, ..., yi,p) = E(xi) to a shuffler S : Y ∗ → Y ∗. The shuffler then shuffles all the messages yi,j from all the users, and outputs them in a uniformly random order to an analyzer A : Y ∗ → Z to estimate some function f(x1, ..., xm). Thus, the mechanism M consists of the tuple (E,S,A). We say that such a mechanism M is (ε, δ)-shuffle differentially private (or (ε, δ)-SDP for short) if the output of S is (ε, δ)-differentially private, or more formally: A mechanism M = (E,S,A) is (ε, δ)-SDP if for any pair of inputs {xi}mi=1 and {x′i}mi=1 which differ in at most one value, we have for all B ⊆ Y ∗:
P (S(∪mi=1E(xi)) ∈ B) ≤ eε · P (S(∪mi=1E(x′i)) ∈ B) + δ.
In the mechanism used in this paper, E outputs the user’s reward bit together with a set of random bits, and A sums all these bits and debiases the result to get an unbiased estimate of the sum of the users’ rewards.

heading: 2.2 Shuffle-model MAB
text: Algorithms which are private in the shuffle model typically apply the mechanism M once over a set of m users. Here we study the MAB problem which is an online problem, often deployed in real-world applications and with users which are end-devices such as cellphones with a possibly limited or unreliable internet connection. Hence, to adapt the MAB problem to the shuffle model, we batch sequences of consecutive users, and assume that each user can afford a single round of communication, and is never selected more than once.
Model and objective The shuffle-model MAB setting involves repeating the following process until the T ’th player pulls its arm:
1. The server selects a batch size m, a batch of m random fresh new users, and an m-user single-round SDP mechanism M .11 It then picks an arm a ∈ [k] that all m users of the batch pull. (For concreteness think that the server picks an ad a ∈ [k] and sends it to the a random batch of m users.)
2. Each user i determines binary reward from pulling the arm a.12 (For concreteness think that each user decides whether to click on the ad or not. This defines the reward related to user i, which is ri = 1 if it clicks the ad and ri = 0 otherwise.) Since our m users are random, these rewards are a sample of m independent rewards from the distribution Ra associated with arm a.
3. The server computes M({ri}i∈batch) using the rewards ri.
The objective is to minimize the (pseudo) regret, which is the expected difference between the sum of the rewards accumulated (over all the users) by the algorithm and the sum of the rewards of the optimal algorithm that apriori knows an arm with the largest expected reward a∗. Let µa = E [Ra] be the expected reward (or simply mean) of the arm a, let µ∗ denote the expected reward of a∗, let ∆a = µ
∗ − µa be the (suboptimality) gap of the arm a which quantifies the gap between its expected reward and that of a∗, and let Na be the random variable which counts the total number of times the arm a was pulled during the run of the algorithm.
Formally, the (pseudo) regret of the algorithm for T ∈ N users is defined to be
R(T ) = T · µ∗ − E  T∑ i=1 ri  = E ∑ a∈[k] Na∆a  . 11Note that always selecting m = 1 reduces this setting to the Local model MAB. 12For simplicity, we assume that the rewards are binary. However, our algorithms and proofs naturally extend to the real [0, 1] reward setting, by replacing our private binary summation mechanism (defined later, see Appendix C) with a private summation mechanism for real numbers in [0, 1] with similar guarantees.
Privacy Since the private data of each user is its reward, the appropriate adaptation of shuffle model privacy for the multi-armed bandit problem is as follows. An algorithm for the multi-armed bandits problem is (ε, δ)-shuffle differentially private (SDP) if for any batch of users, the shuffle mechanism that we apply over them in step 3 is (ε, δ)-SDP with respect to the rewards of the users (as we recall, the reward of a user – whether it clicked on an ad or not – depends on its private features). Formally, for every batch we run a shuffle mechanism where the m users are the users of the current batch, and the data xi of each user is its reward ri, and we require that each such mechanism is (ε, δ)-SDP.

heading: 2.3 Concentration bounds
text: We use the following standard definitions of Sub-Gaussian random variables and Hoeffding’s inequality. Definition 1 (Sub-Gaussian random variable). A random variable X with mean µ is called subGaussian with variance σ2, i.e., X ∼ SG(σ2) if:
∀λ ∈ R, E [ exp(λ(X − µ)) ] ≤ eλ 2σ2/2.
An equivalent definition shows that if ∀t > 0,max ( P (X − µ ≥ t), P (X − µ ≤ −t) ) ≤
exp ( −t2 2σ2 ) , then X is sub-Gaussian with variance σ2 (up to constant factor). It is well known that if
Xi ∼ SG(σ2i ) are independent random variables for i = 1, . . . , n, then ∑n i=1Xn ∼ SG( ∑n i=1 σ 2 i ) and for any a, b > 0, a · X1 + b ∼ SG(a2 · σ21). A bounded random variable X ∈ [a, b] is SG((b− a)2/4). Sub-Gaussian random variables satisfy the following concentration bound, Lemma 2.1 (Hoeffding’s inequality [18]). Let {Xi}ni=1 be independent SG(σ2) random variables,
then P (∣∣∣∑ni=1Xi − E [∑ni=1Xi]∣∣∣ ≥ t) ≤ 2 exp( −t22nσ2) .

heading: 3 Differentially private MAB in the shuffle model
text: In this paper, we use the shuffle model to give a private solution to the multi-armed bandit problem, attaining similar privacy guarantees to that of the local privacy model (LDP), without sacrificing the regret. That is, our algorithm almost matches the best known regret in the centralized model of differential privacy. Our algorithms rely on the fact that algorithms for the multi-armed bandit problem take decisions based on sums of rewards received from the users. Hence, we rely on a particularly efficient and accurate mechanism for private binary summation in the shuffle model as a building block in our algorithms. Specifically, for any ε, δ ∈ (0, 1), let Msum be a private binary summation mechanism, which for any number of users (batch size) m ∈ N, is (ε, δ)-SDP, unbiased, and has an error distribution which is independent of the input, and is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) .13 Note that our notation of Msum does not include ε and δ which will always be clear from context or inherited from the algorithm which runs Msum. The challenge is to combine Msum with the well studied arm elimination (AE) MAB algorithm to get an SDP algorithm for the MAB problem with almost optimal regret.14

heading: 3.1 SDP-AE: Shuffle Differentially Private Arm Elimination
text: We base our algorithm on the (non-private) arm elimination (AE) algorithm for the MAB problem, which informally maintains a set of viable arms (initially set to be [k]), and each phase pulls the set of viable arms sequentially. Once a phase ends, we search for arms which are noticeably suboptimal in comparison to some other arm, and we eliminate them from the set of viable arms.
To adapt AE to the shuffle model, in each phase t each arm is pulled not once, but rather by a whole batch of users. Once all the users in the batch pull the arm and receive their reward, we apply
13Note that our methods and algorithms should work similarly if they were built over other common algorithms for the MAB problem in which batching makes sense, such as the UCB algorithm.
14For completeness, in Appendix C we give a complete description and a proof of such a mechanism Msum.
the private binary summation mechanism Msum to the batch’s rewards, which gives the server an unbiased but noisy estimate of the sum of rewards in the batch. This estimate has two sources of error, which we account for when we compute the upper confidence bound – the empirical error due to sampling the reward function of the arm, and the error due to the private binary summation mechanism Msum.

heading: 3.1.1 Algorithm outline
text: In the algorithm below which we call Shuffle Differentially Private Arm Elimination (SDP-AE), we update the estimate of the mean reward of each arm a after every batch of users who sample a. The algorithm works in phases, and maintains a set of viable arms initially set to be [k]. In each phase, for every viable arm we have a single batch of users sampling it. At the end of phase t, we denote by Ŝta the noisy estimate of the cumulative sum of the rewards from all previous samples of a in the phases 1, . . . , t, and denote by N ta the total number of previous samples of arm a in the phases 1, . . . , t. The natural estimate for the mean reward of the arm a (denoted by µ̂ta) is therefore µ̂ t a = Ŝ t a/N t a. We then calculate the upper and lower confidence bounds UCBta and LCB t a respectively of each viable arm a after each phase t using a specific bound which takes into account both sources of error. We finally eliminate any remaining arm with an upper confidence bound which is strictly smaller than the lower confidence bound of some other arm. Algorithm 1 consolidates the algorithm presentation above.
Algorithm 1: SDP-AE (Shuffle Differentially Private Arm Elimination) 1 Input: privacy parameters ε and δ, batch size m and horizon T . 2 Initialize: Ŝ0a = 0, N0a = 0 and µ̂0a = 0 for every a ∈ [k]; 3 Let σ2ε,δ = O ( log 1δ ε2 ) be the sub-Gaussian variance of the error distribution of Msum;
4 Let V = [k] denote the set of viable arms; 5 for phase t← 1, 2, . . . do 6 for arm a ∈ V do 7 for each new user i← 1 to m do 8 User i pulls the arm a and observes reward rta,i; 9 If total arm samples in current algorithm run is T , exit;
10 end 11 Communication: Perform private binary summation Zta ←Msum ( {rta,i}mi=1 ) ;
12 Server update: Update Ŝta ← Ŝt−1a + Zta, N ta ← N t−1a +m, and finally µ̂ta ← Ŝta/N ta; 13 end
14 Confidence bounds: For each arm a, calculate Ita ← ( 2 √ tσε,δ Nta + 1√ Nta ) · √ 2 log T , and the upper and lower confidence bounds UCBta ← µ̂ta + Ita and LCBta ← µ̂ta − Ita; 15 Elimination: remove all arms a from V such that UCBta < maxa′∈S LCBta′ ; 16 end

heading: 3.1.2 Analysis
text: The privacy is trivial, since each batch we use the (ε, δ)-SDP mechanism Msum. We now focus on regret.
Theorem 3.1 gives a bound on the regret of SDP-AE as a function of the batch size m. We follow a somewhat standard regret bound analysis for arm elimination, comprising two parts. The first part uses Hoeffding’s inequality to derive a high probability bound on ∣∣µ̂ta − µa∣∣, the error between the empirical average reward and the true mean reward of the arm a at a given phase t. The second part uses this bound to bound the expected number of times we sample each suboptimal arm a, and summing over all suboptimal arms we get a bound on the regret.
Theorem 3.1. The algorithm SDP-AE is (ε, δ)-SDP, and has a distribution-dependent re-
gret of O (∑ a∈[k]:∆a>0 ( log T ∆a + σ2ε,δ log T m∆a +m∆a )) , and a distribution-independent regret of
O √(1 + σ2ε,δm ) kT log T +mk .
Proof sketch. Fix a phase t. For any arm a, we have µ̂ta = ∑t s=1Msum({r s a,i} m i=1)
Nta , where N ta = m · t.
We apply Hoeffding’s inequality (Lemma 2.1) once on the sequence of actual rewards of the users, and once on the sequence of errors that Msum introduces into the approximated sum of rewards. We conclude that with high probability, ∀a ∈ [k],∀t ∈ [T ], we have ∣∣µ̂ta − µa∣∣ ≤ ( 2√tσε,δNta + 1√Nta ) · √ 2 log T .
Assuming this high probability event, each arm a is necessarily eliminated after the phase t0 where ∣∣µ̂t0a − µa∣∣ becomes at most roughly ∆a/4. We show that this occurs after at most O ( log T ∆2a + σ2ε,δ·log T m∆2a ) pulls of the arm a, and since we must complete the batch of size m, the
total regret of the arm a is at most Ra = O (
log T ∆a + σ2ε,δ·log T m∆a +m∆a
) . To get the distribution-
dependent regret we sum the regret above over all arms. For the distribution-independent regret, we split this sum based on if the arm a has ∆a < β where β = Θ (√ (1+σ2ε,δ/m)k log T
T
) or not, and
bound each sum separately. Namely, bound the contribution of arms with ∆a < β by βT .
Recall that the private binary summation mechanism Msum’s error distribution is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) . We fix a concrete batch size m in SDP-AE, and apply Theorem 3.1 to get the following corollary.
Corollary 3.2. SDP-AE with a batch size of m = ⌈ σε,δ ⌉ = Θ ( log 1δ ε2 ) is (ε, δ)-SDP and has a distribution-dependent regret of
O  ∑ a∈[k]:∆a>0 ( log T ∆a + ∆a log 1 δ ε2 ) = O   ∑ a∈[k]:∆a>0 log T ∆a + k log 1δ ε2  , and a distribution-independent regret of O (√ kT log T +
k log 1δ ε2
) .

heading: 3.2 VB-SDP-AE: Variable Batch Shuffle Differentially Private Arm Elimination
text: In this section we modify SDP-AE to give an (ε, δ)-SDP algorithm for the MAB problem with improved additional regret. Recall that SDP-AE has a distribution-dependent regret of
O ((∑ a∈[k]:∆a>0 log T ∆a ) + k log 1δ ε2 ) , whereas the best known regret for (ε, δ) centralized-DP is
due to Tossou and Dimitrakakis [28], and is O ((∑
a∈[k]:∆a>0 log T ∆a ) + kε ) . Since any SDP algo-
rithm can be emulated by a centralized-DP mechanism, we can only wish to match the regret of Tossou and Dimitrakakis [28]. Hence, the natural question is: “Can we reduce the dependence in ε of the additive (second) regret term from 1ε2 to 1 ε?” 15
15Note that a Naive attempt to convert the algorithm of Tossou and Dimitrakakis [28] from the centralized model to the shuffle model fails. This is since in the centralized model they can decrease the relative noise as the number of iteration increases by keeping the raw data from the users and reusing it in later iterations. However, in our setting, the noise per shuffle batch has to remain constant for privacy, and we do not have access to the raw data of the users.
Before presenting our solution, we first indicate two intuitive approaches that fail. The first is to continue using batches of constant size m = Ω(1/ε2). This idea fails since intuitively in the worst case we can expect a first batch regret of m = Ω(1/ε2) which already surpasses O(1/ε). The second is to try to directly adapt the algorithm of Tossou and Dimitrakakis [28], which can be interpreted as AE with batches of size ⌈ 1/ε ⌉ . Unfortunately, this adaptation fails since it requires that the added noise to the empirical mean of each arm decreases with time, whereas in the shuffle model, we must ensure privacy with respect to each batch equally and independently, so the total noise cannot decrease with time.
Now for our improved algorithm, observe that using a large batch size increases the regret a lot for arms which are very suboptimal. This is since rather than pulling these arms only a few times until we detect that they are suboptimal, we commit ourselves to pulling them throughout a large batch. On the other hand, fixing the batch size to be small increases the overall estimation error, since every application of the SDP summation algorithm Msum introduces an error of the same magnitude (specifically, the error is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) ) independently of the batch size. Hence, more executions of Msum translates to more noise due to privacy. We therefore extend SDP-AE to support variable size batches, which start small and gradually increase. Intuitively, the smaller batches initially, allow us to quickly eliminate very suboptimal arms with only a small number of pulls. We gradually increase the batch size to reduce the per-user error introduced by the private binary summation mechanism. Specifically, we double the batch size after each phase.

heading: 3.2.1 Algorithm outline
text: We consolidate the idea above into Algorithm 2 below, which we call Variable Batch Shuffle Differentially Private Arm Elimination (VB-SDP-AE), which uses a different batch size mt = 2t for each phase t:
Algorithm 2: VB-SDP-AE (Variable Batch Shuffle Differentially Private Arm Elimination) 1 Input: privacy parameters ε and δ and horizon T . 2 Initialize: Ŝ0a = 0, N0a = 0 and µ̂0a = 0 for every a ∈ [k]; 3 Let σ2ε,δ = O ( log 1δ ε2 ) be the sub-Gaussian variance of the error distribution of Msum;
4 Let V = [k] denote the set of viable arms; 5 for phase t← 1, 2, . . . do 6 Let mt ← 2t; 7 for arm a ∈ V do 8 for each new user i← 1 to mt do 9 User i pulls the arm a and observes reward rta,i;
10 If total number of arm samples is T , exit; 11 end 12 Communication: Perform private binary summation Zta ←Msum ( {rta,i}m t i=1 ) ;
13 Server update: Update Ŝta ← Ŝt−1a +Zta, N ta ← N t−1a +mt, and finally µ̂ta ← Ŝta/N ta; 14 end
15 Confidence bounds: For each arm a, calculate Ita ← ( 2 √ tσε,δ Nta + 1√ Nta ) · √ 2 log T , and the upper and lower confidence bounds UCBta ← µ̂ta + Ita and LCBta ← µ̂ta − Ita; 16 Elimination: remove all arms a from V such that UCBta < maxa′∈S LCBta′ ; 17 end

heading: 3.2.2 Analysis
text: The privacy is trivial, since in each batch we use the (ε, δ)-SDP mechanism Msum. We now focus on regret.
To give a regret bound on VB-SDP-AE, we follow a similar proof to that of Theorem 3.1.
Theorem 3.3. The algorithm VB-SDP-AE is (ε, δ)-SDP, and has a distribution-dependent regret of O ((∑
a∈[k]:∆a>0 log T ∆a
) + kσε,δ log T ) , and a distribution-independent regret of
O (√ kT log T + kσε,δ log T ) .
Proof sketch. A slight modification of the proof of Theorem 3.1 lets us recover that with high probability, ∀a ∈ [k],∀t ∈ [T ], we have that ∣∣µ̂ta − µa∣∣ ≤ ( 2√tσε,δNta + 1√Nta ) · √ 2 log T . Assuming this high probability event, adapting the proof of Theorem 3.1 to our exponentially growing batch sizes gives that each arm a is necessarily eliminated after we have already performedO ( log T ∆2a + σε,δ·log T ∆a ) pulls of the arm a. Unlike the proof of Theorem 3.1, since the batch sizes grow as 2t, the additional pulls of the arm a required to complete the last batch before elimination, adds only a factor of 2 to the total number of pulls to the arm. Hence, the regret of the arm a is at most Ra = O ( log T ∆a + σε,δ · log T ) .
To get the distribution-dependent regret we sum the regret above over all arms. For the distributionindependent regret, we split this sum based on if the arm a has ∆a < β where β = Θ (√ k log T T ) or
not, and bound each sum separately. Namely, bound the regret over arms with ∆a < β by βT .
We recall that the private binary summation mechanism Msum’s error distribution is sub-Gaussian with variance σ2ε,δ = O ( log 1δ ε2 ) , i.e., σε,δ = O (√ log 1δ ε ) , and apply Theorem 3.3 to get the
following corollary. Corollary 3.4. VB-SDP-AE is (ε, δ)-SDP and has a distribution-dependent regret of
O ((∑ a∈[k]:∆a>0 log T ∆a ) + k √ log 1δ log T ε ) , and a distribution-independent regret of
O (√ kT log T + k √ log 1δ log T
ε
) .

heading: 4 Conclusion and future work
text: In this paper, we gave and analyzed differentially private algorithms for the MAB problem, closing the inevitable multiplicative Ω(1/ε2) regret gap between the local model and the centralized model, by considering the (intermediate) shuffle model. Our algorithms are batched variants of AE, which use a private binary summation mechanism for the shuffle model as a building block. Compared to the non-private AE algorithm’s regret, our first algorithm SDP-AE has an additive factor of k log 1δ ε2 using constant size batches, and our second algorithm VB-SDP-AE improves the additive
factor to k √ log 1δ log T
ε by using exponentially growing batches, which enable the early detection and elimination of very suboptimal arms.
A natural future work is to extend our results (i.e., the usage of a private binary summation mechanism for the shuffle model) to more general RL settings such as linear/contextual bandits or Markov decision processes. It would also be interesting to study whether our log T term in the additional additive regret factor can be shaved through a more sophisticated algorithm, or an alternative analysis. Finally, it is interesting to study whether there are more refined distribution-dependent regret bounds that depend on the KL-divergence as in Kaufmann et al. [20].
Disclosure of Funding
This work is partially supported by Israel Science Foundation (grants 993/17,1595/19,1871/19), German-Israeli Foundation (grant 1367/2017), Len Blavatnik and the Blavatnik Family Foundation, the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement 882396), the Yandex Initiative for Machine Learning at Tel Aviv University.

Review summaries:
This paper studies the problem of multi-armed bandits under the shuffled model of DP. The authors provide two algorithms, one of which almost matches the regret of the best known algorithms for the centralized model. To do so, they give a variant of the arm elimination algorithm that leverages the private summation algorithm by Cheu et al. [9] and uses exponentially growing batches. 

The paper proposes a shuffle model of DP for multi-armed bandits. The paper proposes two algorithms, SDP-AE and VB-SDP-AE, for bandits with shuffle DP and Bernoulli rewards. Distribution-dependent and independent regret bounds are derived for both the algorithms. VB-SDP-AE achieves additive regret due to privacy which has same order of dependence on $\epsilon$ but logarithmically worse dependence on $T$ than centralised DP.

This paper studies the multi-armed bandit problem under the constraint of approximate differential privacy. Previously, multi-armed bandits have been studied in other models of privacy such as the centralized pure DP model, the centralized approximate DP model, and the local pure DP model. However, this is the first work to consider the multi-armed bandit problem under the shuffle model of privacy.  To be clear, the model that the authors consider is as follows. At each round $t$, a batch of $m$ random users are selected. An action (e.g. an ad) is then selected for each user. The reward for each user is then presented to a shuffle DP mechanism.  In terms of results, the authors prove a regret bound which is slightly weaker than the result one can obtain in the central DP model but significantly stronger than the result one can obtain the local DP model. In particular, it removes a multiplicative $1/\epsilon^2$ dependence that appears in the regret bound for the local DP model.  In terms of techniques, the authors combine some ideas from the bandit literature and the differential privacy literature. In particular, their algorithms are based on the non-private arm elimination algorithm and they show how one can use private binary summation from the shuffle DP literature to obtain a shuffle DP algorithm for MAB. The authors also give two differential algorithms. The first algorithm uses static batch sizes in each round. The second algorithm uses dynamic batch sizes and they show that this improves the regret.

This paper adapts the shuffle model of differential privacy to the multi-armed bandit setting, and aims to design a bandit algorithm which has privacy guarantees similar to that in the local model, while simultaneously having regret guarantees similar to the central DP model. The authors propose two arm-elimination style algorithms, which uses a private binary summation mechanism with optimal error guarantees as a subroutine, in order to obtain improved regret guarantees over the local model. In particular, they show how a simple, constant batch size policy already gets rid of the multiplicative dependence on $1/\epsilon^2$. Then, they show how to adapt this policy to exponentially increasing batch sizes, improving the additive dependence from $\approx k/\epsilon^2$ to $\approx k/\epsilon$. 

The paper studies the classic multi-armed bandit problem in the shuffled model of differential privacy. Paper's first contribution is the definition of shuffled differential privacy (SDP) in the multi-armed bandit setting.  The paper's main contribution is an SDP algorithm with the same regret guarantees as the best-known multi-armed bandit algorithm in the central privacy model.