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.
abstractText: 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.
authors.name: Jay Tenenbaum
authors.name: Haim Kaplan
authors.name: Yishay Mansour
authors.name: Uri Stemmer
references.authors: B. Balle J. Bell A. Gascon K. Nissim
references.title: Differentially private summation with multimessage shuffling
references.venue: arXiv preprint arXiv:1906.09116
references.authors: B. Balle J. Bell A. Gascón K. Nissim
references.title: The privacy blanket of the shuffle model
references.venue: Annual International Cryptology Conference, pages 638–667. Springer
references.authors: B. Balle J. Bell A. Gascón K. Nissim
references.title: Private summation in the multi-message shuffle model
references.venue: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 657–676
references.authors: A. Beimel I. Haitner K. Nissim U. Stemmer
references.title: On the round complexity of the shuffle model
references.venue: Theory of Cryptography Conference, pages 683–712. Springer
references.authors: A. Beimel K. Nissim E. Omri
references.title: Distributed private data analysis: Simultaneously solving how and what
references.venue: Annual International Cryptology Conference, pages 451–468. Springer
references.authors: A. Bittau Ú. Erlingsson P. Maniatis I. Mironov A. Raghunathan D. Lie M. Rudominer U. Kode J. Tinnes B. Seefeld
references.title: Prochlo: Strong privacy for analytics in the crowd
references.venue: Proceedings of the 26th Symposium on Operating Systems Principles, pages 441–459
references.authors: M. Bun J. Nelson U. Stemmer
references.title: Heavy hitters and the structure of local privacy
references.venue: ACM Transactions on Algorithms (TALG), 15(4):1–40
references.authors: T.H. Chan E. Shi D. Song
references.title: Optimal lower bound for differentially private multi-party aggregation
references.venue: European Symposium on Algorithms, pages 277–288. Springer
references.authors: A. Cheu A. Smith J. Ullman D. Zeber M. Zhilyaev
references.title: Distributed differential privacy via shuffling
references.venue: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 375–403. Springer
references.authors: A. Dubey A. Pentland
references.title: Differentially-private federated linear bandits
references.venue: arXiv preprint arXiv:2010.11425
references.authors: C. Dwork F. McSherry K. Nissim A. Smith
references.title: Calibrating noise to sensitivity in private data analysis
references.venue: Theory of cryptography conference, pages 265–284. Springer
references.authors: Ú. Erlingsson V. Feldman I. Mironov A. Raghunathan S. Song K. Talwar A. Thakurta
references.title: Encode
references.venue: shuffle, analyze privacy revisited: Formalizations and empirical evaluation. arXiv preprint arXiv:2001.03618
references.authors: Ú. Erlingsson V. Feldman I. Mironov A. Raghunathan K. Talwar A. Thakurta
references.title: Amplification by shuffling: From local to central differential privacy via anonymity
references.venue: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468–2479. SIAM
references.authors: H. Esfandiari A. Karbasi A. Mehrabian V. Mirrokni
references.title: Regret bounds for batched bandits
references.venue: arXiv preprint arXiv:1910.04959
references.authors: Z. Gao Y. Han Z. Ren Z. Zhou
references.title: Batched multi-armed bandits problem
references.venue: arXiv preprint arXiv:1904.01763
references.authors: B. Ghazi R. Pagh A. Velingker
references.title: Scalable and differentially private distributed aggregation in the shuffled model
references.venue: arXiv preprint arXiv:1906.08320
references.authors: A. Guha Thakurta A. Smith
references.title: nearly) optimal algorithms for private online learning in full-information and bandit settings
references.venue: Advances in Neural Information Processing Systems, 26:2733–2741
references.authors: W. Hoeffding
references.title: Probability inequalities for sums of bounded random variables
references.venue: The Collected Works of Wassily Hoeffding, pages 409–426. Springer
references.authors: P. Jain P. Kothari A. Thakurta
references.title: Differentially private online learning
references.venue: Conference on Learning Theory, pages 24–1. JMLR Workshop and Conference Proceedings
references.authors: E. Kaufmann O. Cappé A. Garivier
references.title: On the complexity of best-arm identification in multi-armed bandit models
references.venue: The Journal of Machine Learning Research, 17(1):1–42
references.authors: N. Mishra A. Thakurta
references.title: nearly) optimal differentially private stochastic multi-arm bandits
references.venue: Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pages 592–601
references.authors: W. Ren X. Zhou J. Liu N.B. Shroff
references.title: Multi-armed bandits with local differential privacy
references.venue: arXiv preprint arXiv:2007.03121
references.authors: H. Robbins
references.title: Some aspects of the sequential design of experiments
references.venue: Bulletin of the American Mathematical Society, 58(5):527–535
references.authors: T. Sajed O. Sheffet
references.title: An optimal private stochastic-mab algorithm based on optimal private stopping rule
references.venue: International Conference on Machine Learning, pages 5579–5588. PMLR
references.authors: R. Shariff O. Sheffet
references.title: Differentially private contextual linear bandits
references.venue: arXiv preprint arXiv:1810.00068
references.authors: C. Shi C. Shen
references.title: Federated multi-armed bandits
references.venue: arXiv preprint arXiv:2101.12204
references.authors: W.R. Thompson
references.title: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
references.venue: Biometrika, 25(3/4):285–294
references.authors: A. Tossou C. Dimitrakakis
references.title: Algorithms for differentially private multi-armed bandits
references.venue: Proceedings of the AAAI Conference on Artificial Intelligence, volume 30
references.authors: K. Zheng T. Cai W. Huang Z. Li
references.title: and L
references.venue: Wang. Locally differentially private 
sections.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.
sections.heading: 1 Introduction
sections.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].
sections.heading: 1.1 Our contributions
sections.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].
sections.heading: 1.2 Related work
sections.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.
sections.heading: 2 Background and preliminaries
sections.heading: 2.1 Shuffle-model privacy
sections.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.
sections.heading: 2.2 Shuffle-model MAB
sections.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.
sections.heading: 2.3 Concentration bounds
sections.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) .
sections.heading: 3 Differentially private MAB in the shuffle model
sections.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
sections.heading: 3.1 SDP-AE: Shuffle Differentially Private Arm Elimination
sections.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.
sections.heading: 3.1.1 Algorithm outline
sections.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
sections.heading: 3.1.2 Analysis
sections.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
  ) .
sections.heading: 3.2 VB-SDP-AE: Variable Batch Shuffle Differentially Private Arm Elimination
sections.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.
sections.heading: 3.2.1 Algorithm outline
sections.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
sections.heading: 3.2.2 Analysis
sections.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
  ε
  ) .
sections.heading: 4 Conclusion and future work
sections.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.
title: Differentially Private Multi-Armed Bandits in the Shuffle Model