mlsanityData to 7 Oct 2026

Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits

arXiv 2106.02575 ↗First posted 4 Jun 2021cs.LGcited by 25

Not on the map. Why?

Abstract (arXiv)

In this paper we investigate the problem of stochastic multi-armed bandits (MAB) in the (local) differential privacy (DP/LDP) model. Unlike previous results that assume bounded/sub-Gaussian reward distributions, we focus on the setting where each arm's reward distribution only has (1+v)-th moment with some v∈ (0, 1]. In the first part, we study the problem in the central ε-DP model. We first provide a near-optimal result by developing a private and robust Upper Confidence Bound (UCB) algorithm. Then, we improve the result via a private and robust version of the Successive Elimination (SE) algorithm. Finally, we establish the lower bound to show that the instance-dependent regret of our improved algorithm is optimal. In the second part, we study the problem in the ε-LDP model. We propose an algorithm that can be seen as locally private and robust version of SE algorithm, which provably achieves (near) optimal rates for both instance-dependent and instance-independent regret. Our results reveal differences between the problem of private MAB with bounded/sub-Gaussian rewards and heavy-tailed rewards. To achieve these (near) optimal rates, we develop several new hard instances and private robust estimators as byproducts, which might be used to other related problems. Finally, experiments also support our theoretical findings and show the effectiveness of our algorithms.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 24 of its 55 references that are in the map. First posted on arXiv 4 Jun 2021.

Builds on

24 of 55 references.

References · 24

  1. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  2. 2020Differentially-Private Federated Linear Banditscited by 83
  3. 2018Differentially Private Contextual Linear Banditscited by 82
  4. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  5. 2021Robust and Differentially Private Mean Estimationcited by 66
  6. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 52
  7. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
  8. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  9. 2015Algorithms for Differentially Private Multi-Armed Banditscited by 44
  10. 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
  11. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  12. 2019Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?cited by 27
12 more
  1. 2021Regret Minimization in Heavy-Tailed Banditscited by 24
  2. 2018Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Casecited by 19
  3. 2020Local Differential Privacy for Bayesian Optimizationcited by 19
  4. 2020Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewardscited by 18
  5. 2020Propose, Test, Release: Differentially private estimation with high probabilitycited by 15
  6. 2020(Locally) Differentially Private Combinatorial Semi-Banditscited by 14
  7. 2020Bandit algorithms: Letting go of logarithmic regret for statistical robustnesscited by 12
  8. 2017A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosiscited by 9
  9. 2019Privacy-Preserving Banditscited by 6
  10. 2017A Multi-Armed Bandit to Smartly Select a Training Set from Big Medical Datacited by 5
  11. 2019Thompson Sampling on Symmetric α-Stable Banditscited by 4
  12. 2019Privacy-Preserving Multi-Party Contextual Banditscited by 3

Built on by

Cited by year (2026 to 7 Oct)

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

25 papers.

Sort:

By area:

  1. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  2. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  3. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  4. 2023Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewardscited by 11
  5. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  6. 2022Byzantine-Robust Federated Linear Banditscited by 7
  7. 2023Quantum Heavy-tailed Banditscited by 7
  8. 2023Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Riskcited by 7
  9. 2022On the Statistical Complexity of Estimation and Testing under Privacy Constraintscited by 6
  10. 2023On Private and Robust Banditscited by 6
  11. 2024Collaborative AI Teaming in Unknown Environments via Active Goal Deductioncited by 6
  12. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
13 more
  1. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  2. 2025Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamicscited by 2
  3. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  4. 2023Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Normcited by 1
  5. 2023DPMAC: Differentially Private Communication for Cooperative Multi-Agent Reinforcement Learningcited by 1
  6. 2024Decentralized Blockchain-based Robust Multi-agent Multi-armed Banditcited by 1
  7. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  8. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  9. 2023Local Differential Privacy for Sequential Decision Making in a Changing Environmentcited by 0
  10. 2025The Safety-Privacy Tradeoff in Linear Banditscited by 0
  11. 2026Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tailscited by 0
  12. 2026Unlearning Offline Stochastic Multi-Armed Banditscited by 0
  13. 2026Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacycited by 0