mlsanityData to 7 Oct 2026

Multi-Armed Bandits with Local Differential Privacy

arXiv 2007.03121 ↗First posted 6 Jul 2020cs.LG cs.CR stat.MLcited by 37

Not on the map. Why?

Abstract (arXiv)

This paper investigates the problem of regret minimization for multi-armed bandit (MAB) problems with local differential privacy (LDP) guarantee. In stochastic bandit systems, the rewards may refer to the users' activities, which may involve private information and the users may not want the agent to know. However, in many cases, the agent needs to know these activities to provide better services such as recommendations and news feeds. To handle this dilemma, we adopt differential privacy and study the regret upper and lower bounds for MAB algorithms with a given LDP guarantee. In this paper, we prove a lower bound and propose algorithms whose regret upper bounds match the lower bound up to constant factors. Numerical experiments also confirm our conclusions.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

37 papers.

Sort:

By area:

  1. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  2. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  3. 2022Shuffle Private Linear Contextual Banditscited by 27
  4. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  5. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  6. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  7. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  8. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  9. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  10. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  11. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  12. 2021Differential Privacy in Personalized Pricing with Nonparametric Demand Modelscited by 13
25 more
  1. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  2. 2021Privacy-Preserving Communication-Efficient Federated Multi-Armed Banditscited by 11
  3. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  4. 2023On Private and Robust Banditscited by 6
  5. 2022Dynamic Global Sensitivity for Differentially Private Contextual Banditscited by 5
  6. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  7. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  8. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  9. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  10. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
  11. 2025DP-NCB: Privacy Preserving Fair Banditscited by 2
  12. 2021Cascading Bandit under Differential Privacycited by 1
  13. 2024Privacy Preserving Adaptive Experiment Designcited by 1
  14. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
  15. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  16. 2024QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Banditscited by 1
  17. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  18. 2025Faster Rates for Private Adversarial Banditscited by 1
  19. 2023Thompson Sampling under Bernoulli Rewards with Local Differential Privacycited by 0
  20. 2023Beyond Random Noise: Insights on Anonymization Strategies from a Latent Bandit Studycited by 0
  21. 2024Differentially Private High Dimensional Banditscited by 0
  22. 2025Locally Differentially Private Thresholding Banditscited by 0
  23. 2025Beyond ATE: Multi-Criteria Design for A/B Testingcited by 0
  24. 2026Unlearning Offline Stochastic Multi-Armed Banditscited by 0
  25. 2026Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacycited by 0