mlsanityData to 14 Oct 2026

Differentially Private Multi-Armed Bandits in the Shuffle Model

arXiv 2106.02900 ↗First posted 5 Jun 2021cs.LG cs.CRcited by 24

Not on the map. Why?

Abstract (arXiv)

We give an (varepsilon,δ)-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model with a distribution-dependent regret of Oleft(left(suma∈ [k]:Deltaa>0fraclog TDeltaaright)+frack√logfrac1δlog Tvarepsilonright), and a distribution-independent regret of Oleft(√kTlog T+frack√logfrac1δlog Tvarepsilonright), where T is the number of rounds, Deltaa 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.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). Builds on 19 of its 31 references that are in the map. First posted on arXiv 5 Jun 2021.

Builds on

19 of 31 references.

References · 19

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  2. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 164
  3. 2018Distributed Differential Privacy via Shufflingcited by 115
  4. 2019Batched Multi-armed Bandits Problemcited by 98
  5. 2020Differentially-Private Federated Linear Banditscited by 83
  6. 2018Differentially Private Contextual Linear Banditscited by 82
  7. 2019The Privacy Blanket of the Shuffle Modelcited by 74
  8. 2021Federated Multi-Armed Banditscited by 59
  9. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 53
  10. 2019Regret Bounds for Batched Banditscited by 49
  11. 2015Algorithms for Differentially Private Multi-Armed Banditscited by 45
  12. 2020Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluationcited by 39
7 more
  1. 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
  2. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  3. 2020Private Summation in the Multi-Message Shuffle Modelcited by 34
  4. 2017Heavy Hitters and the Structure of Local Privacycited by 20
  5. 2019Scalable and Differentially Private Distributed Aggregation in the Shuffled Modelcited by 20
  6. 2019Differentially Private Summation with Multi-Message Shufflingcited by 9
  7. 2020On the Round Complexity of the Shuffle Modelcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 7; 2024: 3; 2025: 6; 2026: 1.

24 papers.

Sort:

By area:

  1. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  2. 2022Shuffle Private Linear Contextual Banditscited by 27
  3. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  4. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  5. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  6. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  7. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  8. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  9. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  10. 2023On Private and Robust Banditscited by 6
  11. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  12. 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densitiescited by 3
12 more
  1. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
  2. 2025DP-NCB: Privacy Preserving Fair Banditscited by 2
  3. 2023DPMAC: Differentially Private Communication for Cooperative Multi-Agent Reinforcement Learningcited by 1
  4. 2024Privacy Preserving Adaptive Experiment Designcited by 1
  5. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  6. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  7. 2025Faster Rates for Private Adversarial Banditscited by 1
  8. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 1
  9. 2023Robust and differentially private stochastic linear banditscited by 0
  10. 2025Optimal Regret of Bernoulli Bandits under Global Differential Privacycited by 0
  11. 2025Differential Privacy in Kernelized Contextual Bandits via Random Projectionscited by 0
  12. 2025Beyond ATE: Multi-Criteria Design for A/B Testingcited by 0