mlsanityData to 7 Oct 2026

An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule

arXiv 1905.09383 ↗First posted 22 May 2019stat.ML cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

We present a provably optimal differentially private algorithm for the stochastic multi-arm bandit problem, as opposed to the private analogue of the UCB-algorithm [Mishra and Thakurta, 2015; Tossou and Dimitrakakis, 2016] which doesn't meet the recently discovered lower-bound of Omega left(fracKlog(T)ε right) [Shariff and Sheffet, 2018]. Our construction is based on a different algorithm, Successive Elimination [Even-Dar et al. 2002], that repeatedly pulls all remaining arms until an arm is found to be suboptimal and is then eliminated. In order to devise a private analogue of Successive Elimination we visit the problem of private stopping rule, that takes as input a stream of i.i.d samples from an unknown distribution and returns a multiplicative (1 ± α)-approximation of the distribution's mean, and prove the optimality of our private stopping rule. We then present the private Successive Elimination algorithm which meets both the non-private lower bound [Lai and Robbins, 1985] and the above-mentioned private lower bound. We also compare empirically the performance of our algorithm with the private UCB algorithm.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 5; 2023: 9; 2024: 7; 2025: 10; 2026: 1.

37 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. 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. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  8. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  9. 2023On Differentially Private Federated Linear Contextual Banditscited by 14
  10. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  11. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
  12. 2023Concentrated Differential Privacy for Banditscited by 10
25 more
  1. 2023On Private and Robust Banditscited by 6
  2. 2023Unbounded Differentially Private Quantile and Maximum Estimationcited by 6
  3. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  4. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  5. 2024Thompson Sampling Itself is Differentially Privatecited by 4
  6. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  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. 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environmentcited by 2
  11. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
  12. 2024Fixed-Budget Differentially Private Best Arm Identificationcited by 2
  13. 2024Privacy Preserving Adaptive Experiment Designcited by 1
  14. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  15. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
  16. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  17. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  18. 2025Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacycited by 1
  19. 2025Faster Rates for Private Adversarial Banditscited by 1
  20. 2025DP-SPRT: Differentially Private Sequential Probability Ratio Testscited by 1
  21. 2025Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regretcited by 0
  22. 2025Optimal Regret of Bernoulli Bandits under Global Differential Privacycited by 0
  23. 2025Secure Best Arm Identification in the Presence of a Copycatcited by 0
  24. 2025Beyond ATE: Multi-Criteria Design for A/B Testingcited by 0
  25. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0