mlsanityData to 7 Oct 2026

Achieving Privacy in the Adversarial Multi-Armed Bandit

arXiv 1701.04222 ↗First posted 16 Jan 2017cs.LG cs.AI cs.CRcited by 24

Not on the map. Why?

Abstract (arXiv)

In this paper, we improve the previously best known regret bound to achieve ε-differential privacy in oblivious adversarial bandits from O(T2/3/ε) to O(√T ln T /ε). This is achieved by combining a Laplace Mechanism with EXP3. We show that though EXP3 is already differentially private, it leaks a linear amount of information in T. However, we can improve this privacy by relying on its intrinsic exponential mechanism for selecting actions. This allows us to reach O(√ln T)-DP, with a regret of O(T2/3) that holds against an adaptive adversary, an improvement from the best known of O(T3/4). This is done by using an algorithm that run EXP3 in a mini-batch loop. Finally, we run experiments that clearly demonstrate the validity of our theoretical analysis.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jan 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 8; 2023: 4; 2024: 4; 2025: 3; 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. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  4. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  5. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  6. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  7. 2024Trustworthy Distributed AI Systems: Robustness, Privacy, and Governancecited by 12
  8. 2021Littlestone Classes are Privately Online Learnablecited by 10
  9. 2023Concentrated Differential Privacy for Banditscited by 10
  10. 2022Private and Byzantine-Proof Cooperative Decision-Makingcited by 9
  11. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  12. 2021Adaptive Control of Differentially Private Linear Quadratic Systemscited by 7
12 more
  1. 2022Dynamic Global Sensitivity for Differentially Private Contextual Banditscited by 5
  2. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
  3. 2021Cascading Bandit under Differential Privacycited by 1
  4. 2023DPMAC: Differentially Private Communication for Cooperative Multi-Agent Reinforcement Learningcited by 1
  5. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  6. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
  7. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  8. 2025Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacycited by 1
  9. 2025Faster Rates for Private Adversarial Banditscited by 1
  10. 2026Differential Privacy in the Extensive-Form Bandit Problemcited by 1
  11. 2023Local Differential Privacy for Sequential Decision Making in a Changing Environmentcited by 0
  12. 2025Optimal Regret of Bernoulli Bandits under Global Differential Privacycited by 0