mlsanityData to 14 Oct 2026

Algorithms for Differentially Private Multi-Armed Bandits

arXiv 1511.08681 ↗First posted 27 Nov 2015stat.ML cs.CR cs.LGcited by 45

Not on the map. Why?

Abstract (arXiv)

We present differentially private algorithms for the stochastic Multi-Armed Bandit (MAB) problem. This is a problem for applications such as adaptive clinical trials, experiment design, and user-targeted advertising where private information is connected to individual rewards. Our major contribution is to show that there exist (ε, δ) differentially private variants of Upper Confidence Bound algorithms which have optimal regret, O(ε-1 + log T). This is a significant improvement over previous results, which only achieve poly-log regret O(ε-2 log2 T), because of our use of a novel interval-based mechanism. We also substantially improve the bounds of previous family of algorithms which use a continual release mechanism. Experiments clearly validate our theoretical bounds.

Key facts. Cited by 45 papers in the map (data through 14 Oct 2026). First posted on arXiv 27 Nov 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 9; 2023: 5; 2024: 10; 2025: 6; 2026: 4.

45 papers.

Sort:

By area:

  1. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  2. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  3. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  4. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  5. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  6. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  7. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  8. 2024Trustworthy Distributed AI Systems: Robustness, Privacy, and Governancecited by 14
  9. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  10. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
  11. 2021Privacy-Preserving Communication-Efficient Federated Multi-Armed Banditscited by 11
  12. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
33 more
  1. 2021Littlestone Classes are Privately Online Learnablecited by 10
  2. 2022Private and Byzantine-Proof Cooperative Decision-Makingcited by 10
  3. 2023Concentrated Differential Privacy for Banditscited by 10
  4. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  5. 2021Adaptive Control of Differentially Private Linear Quadratic Systemscited by 7
  6. 2022Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimizationcited by 7
  7. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  8. 2022Federated X-Armed Banditcited by 5
  9. 2022Dynamic Global Sensitivity for Differentially Private Contextual Banditscited by 5
  10. 2024Thompson Sampling Itself is Differentially Privatecited by 4
  11. 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environmentcited by 2
  12. 2024Fixed-Budget Differentially Private Best Arm Identificationcited by 2
  13. 2025DP-NCB: Privacy Preserving Fair Banditscited by 2
  14. 2021Cascading Bandit under Differential Privacycited by 1
  15. 2022Anonymous Bandits for Multi-User Systemscited by 1
  16. 2024Privacy Preserving Adaptive Experiment Designcited by 1
  17. 2024Fairness and Privacy Guarantees in Federated Contextual Banditscited by 1
  18. 2024Differentially Private Deep Model-Based Reinforcement Learningcited by 1
  19. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  20. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
  21. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  22. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  23. 2025Differentially Private Hyperparameter Tuning using Local Bayesian Optimizationcited by 1
  24. 2025Faster Rates for Private Adversarial Banditscited by 1
  25. 2025Deceptive Exploration in Multi-armed Banditscited by 1
  26. 2021Encrypted Linear Contextual Banditcited by 0
  27. 2023Local Differential Privacy for Sequential Decision Making in a Changing Environmentcited by 0
  28. 2025The Safety-Privacy Tradeoff in Linear Banditscited by 0
  29. 2025Beyond ATE: Multi-Criteria Design for A/B Testingcited by 0
  30. 2026CHRONOS: Temporally-Aware Multi-Agent Coordination for Evolving Data Marketplacescited by 0
  31. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0
  32. 2026Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacycited by 0
  33. 2026Plausible Deniability Guarantees for Whistleblowerscited by 0