mlsanityData to 14 Oct 2026

Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?

arXiv 1905.12298 ↗First posted 29 May 2019cs.LG stat.MLcited by 27

Not on the map. Why?

Abstract (arXiv)

Based on differential privacy (DP) framework, we introduce and unify privacy definitions for the multi-armed bandit algorithms. We represent the framework with a unified graphical model and use it to connect privacy definitions. We derive and contrast lower bounds on the regret of bandit algorithms satisfying these definitions. We leverage a unified proving technique to achieve all the lower bounds. We show that for all of them, the learner's regret is increased by a multiplicative factor dependent on the privacy level ε. We observe that the dependency is weaker when we do not require local differential privacy for the rewards.

Key facts. Cited by 27 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

27 papers.

Sort:

By area:

  1. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  2. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  3. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  4. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  5. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  6. 2022Offline Reinforcement Learning with Differential Privacycited by 20
  7. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  8. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  9. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  10. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
  11. 2021Privacy-Preserving Communication-Efficient Federated Multi-Armed Banditscited by 11
  12. 2023Concentrated Differential Privacy for Banditscited by 10
15 more
  1. 2021Adaptive Control of Differentially Private Linear Quadratic Systemscited by 7
  2. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  3. 2022Dynamic Global Sensitivity for Differentially Private Contextual Banditscited by 5
  4. 2024Replicability is Asymptotically Free in Multi-armed Banditscited by 2
  5. 2025DP-NCB: Privacy Preserving Fair Banditscited by 2
  6. 2021Cascading Bandit under Differential Privacycited by 1
  7. 2022Anonymous Bandits for Multi-User Systemscited by 1
  8. 2024Differentially Private Deep Model-Based Reinforcement Learningcited by 1
  9. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  10. 2025Faster Rates for Private Adversarial Banditscited by 1
  11. 2023Robust and differentially private stochastic linear banditscited by 0
  12. 2023Thompson Sampling under Bernoulli Rewards with Local Differential Privacycited by 0
  13. 2025Optimal Regret of Bernoulli Bandits under Global Differential Privacycited by 0
  14. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0
  15. 2026Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacycited by 0