mlsanityData to 14 Oct 2026

Distributed Differential Privacy in Multi-Armed Bandits

arXiv 2206.05772 ↗First posted 12 Jun 2022cs.LG cs.CRcited by 14

Not on the map. Why?

Abstract (arXiv)

We consider the standard K-armed bandit problem under a distributed trust model of differential privacy (DP), which enables to guarantee privacy without a trustworthy server. Under this trust model, previous work largely focus on achieving privacy using a shuffle protocol, where a batch of users data are randomly permuted before sending to a central server. This protocol achieves (ε,δ) or approximate-DP guarantee by sacrificing an additional additive O!left(!fracKlog T√log(1/δ)ε!right)! cost in T-step cumulative regret. In contrast, the optimal privacy cost for achieving a stronger (ε,0) or pure-DP guarantee under the widely used central trust model is only Theta!left(!fracKlog Tε!right)!, where, however, a trusted server is required. In this work, we aim to obtain a pure-DP guarantee under distributed trust model while sacrificing no more regret than that under central trust model. We achieve this by designing a generic bandit algorithm based on successive arm elimination, where privacy is guaranteed by corrupting rewards with an equivalent discrete Laplace noise ensured by a secure computation protocol. We also show that our algorithm, when instantiated with Skellam noise and the secure protocol, ensures emphR'enyi differential privacy -- a stronger notion than approximate DP -- under distributed trust model with a privacy cost of O!left(!fracK√log Tε!right)!.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 43 of its 65 references that are in the map. First posted on arXiv 12 Jun 2022.

Builds on

43 of 65 references.

References · 43

  1. 2019Advances and Open Problems in Federated Learningcited by 3,046
  2. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  3. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 164
  4. 2020The Discrete Gaussian for Differential Privacycited by 135
  5. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 128
  6. 2013Introducing LETOR 4.0 Datasetscited by 121
  7. 2018Distributed Differential Privacy via Shufflingcited by 115
  8. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  9. 2018Differentially Private Contextual Linear Banditscited by 82
  10. 2019The Privacy Blanket of the Shuffle Modelcited by 74
  11. 2021The Skellam Mechanism for Differentially Private Federated Learningcited by 68
  12. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 53
31 more
  1. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
  2. 2015Algorithms for Differentially Private Multi-Armed Banditscited by 45
  3. 2017The Price of Differential Privacy For Online Learningcited by 45
  4. 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learningcited by 39
  5. 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
  6. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  7. 2020Private Summation in the Multi-Message Shuffle Modelcited by 34
  8. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  9. 2019How You Act Tells a Lot: Privacy-Leakage Attack on Deep Reinforcement Learningcited by 29
  10. 2022Shuffle Private Linear Contextual Banditscited by 27
  11. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  12. 2017Achieving Privacy in the Adversarial Multi-Armed Banditcited by 24
  13. 2020Concentration Inequalities for Statistical Inferencecited by 24
  14. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  15. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  16. 2020Local Differential Privacy for Regret Minimization in Reinforcement Learningcited by 22
  17. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  18. 2019Old Dog Learns New Tricks: Randomized UCB for Bandit Problemscited by 21
  19. 2020A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergencescited by 21
  20. 2020Local Differential Privacy for Bayesian Optimizationcited by 19
  21. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  22. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  23. 2019Private Aggregation from Fewer Anonymous Messagescited by 15
  24. 2020Pure Differentially Private Summation from Anonymous Messagescited by 15
  25. 2020(Locally) Differentially Private Combinatorial Semi-Banditscited by 14
  26. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  27. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
  28. 2021Adaptive Control of Differentially Private Linear Quadratic Systemscited by 7
  29. 2013Maximum entropy distributions on graphscited by 4
  30. 2021Pure Differential Privacy from Secure Intermediariescited by 4
  31. 2021Cascading Bandit under Differential Privacycited by 1

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 5; 2024: 5; 2025: 3.

14 papers.

Sort:

By area:

  1. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  2. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  3. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  4. 2023On Private and Robust Banditscited by 6
  5. 2025Improved Bounds for Private and Robust Alignmentcited by 5
  6. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  7. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  8. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  9. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  10. 2024Fixed-Budget Differentially Private Best Arm Identificationcited by 2
  11. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  12. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
2 more
  1. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  2. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1