# Differentially Private Multi-Armed Bandits in the Shuffle Model

arXiv: https://arxiv.org/abs/2106.02900 · HTML: https://mlsanity.com/paper/2106.02900/

## 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 (most cited first, 19 of 19)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Heavy Hitters and the Structure of Local Privacy](https://mlsanity.com/paper/1711.04740/) (2017)
- [Scalable and Differentially Private Distributed Aggregation in the Shuffled Model](https://mlsanity.com/paper/1906.08320/) (2019)
- [Differentially Private Summation with Multi-Message Shuffling](https://mlsanity.com/paper/1906.09116/) (2019)
- [On the Round Complexity of the Shuffle Model](https://mlsanity.com/paper/2009.13510/) (2020)

## Built on by (most cited first, 24 of 24)

- [When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits](https://mlsanity.com/paper/2209.02570/) (2022)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Differentially Private Stochastic Linear Bandits: (Almost) for Free](https://mlsanity.com/paper/2207.03445/) (2022)
- [Shuffle Private Stochastic Convex Optimization](https://mlsanity.com/paper/2106.09805/) (2021)
- [Privacy Amplification via Shuffling for Linear Contextual Bandits](https://mlsanity.com/paper/2112.06008/) (2021)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Differentially Private Linear Bandits with Partial Distributed Feedback](https://mlsanity.com/paper/2207.05827/) (2022)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [(Private) Kernelized Bandits with Distributed Biased Feedback](https://mlsanity.com/paper/2301.12061/) (2023)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [Concurrent Shuffle Differential Privacy Under Continual Observation](https://mlsanity.com/paper/2301.12535/) (2023)
- [DP-NCB: Privacy Preserving Fair Bandits](https://mlsanity.com/paper/2508.03836/) (2025)
- [DPMAC: Differentially Private Communication for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2308.09902/) (2023)
- [Privacy Preserving Adaptive Experiment Design](https://mlsanity.com/paper/2401.08224/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)
- [Faster Rates for Private Adversarial Bandits](https://mlsanity.com/paper/2505.21790/) (2025)
- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)
- [Robust and differentially private stochastic linear bandits](https://mlsanity.com/paper/2304.11741/) (2023)
- [Optimal Regret of Bernoulli Bandits under Global Differential Privacy](https://mlsanity.com/paper/2505.05613/) (2025)
- [Differential Privacy in Kernelized Contextual Bandits via Random Projections](https://mlsanity.com/paper/2507.13639/) (2025)
- [Beyond ATE: Multi-Criteria Design for A/B Testing](https://mlsanity.com/paper/2509.05864/) (2025)

## 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.