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

arXiv: https://arxiv.org/abs/2106.02575 · HTML: https://mlsanity.com/paper/2106.02575/

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Private Reinforcement Learning with PAC and Regret Guarantees](https://mlsanity.com/paper/2009.09052/) (2020)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?](https://mlsanity.com/paper/1905.12298/) (2019)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case](https://mlsanity.com/paper/1802.04085/) (2018)
- [Local Differential Privacy for Bayesian Optimization](https://mlsanity.com/paper/2010.06709/) (2020)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [(Locally) Differentially Private Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.00706/) (2020)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis](https://mlsanity.com/paper/1703.08937/) (2017)
- [Privacy-Preserving Bandits](https://mlsanity.com/paper/1909.04421/) (2019)
- [A Multi-Armed Bandit to Smartly Select a Training Set from Big Medical Data](https://mlsanity.com/paper/1705.08111/) (2017)
- [Thompson Sampling on Symmetric α-Stable Bandits](https://mlsanity.com/paper/1907.03821/) (2019)
- [Privacy-Preserving Multi-Party Contextual Bandits](https://mlsanity.com/paper/1910.05299/) (2019)

## Built on by (most cited first, 25 of 25)

- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022)
- [Byzantine-Robust Federated Linear Bandits](https://mlsanity.com/paper/2204.01155/) (2022)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [On the Statistical Complexity of Estimation and Testing under Privacy Constraints](https://mlsanity.com/paper/2210.02215/) (2022)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [Collaborative AI Teaming in Unknown Environments via Active Goal Deduction](https://mlsanity.com/paper/2403.15341/) (2024)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)
- [Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics](https://mlsanity.com/paper/2501.19239/) (2025)
- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)
- [Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm](https://mlsanity.com/paper/2303.07287/) (2023)
- [DPMAC: Differentially Private Communication for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2308.09902/) (2023)
- [Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2402.04417/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)
- [Local Differential Privacy for Sequential Decision Making in a Changing Environment](https://mlsanity.com/paper/2301.00561/) (2023)
- [The Safety-Privacy Tradeoff in Linear Bandits](https://mlsanity.com/paper/2504.16371/) (2025)
- [Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails](https://mlsanity.com/paper/2604.06492/) (2026)
- [Unlearning Offline Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2605.00638/) (2026)
- [Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy](https://mlsanity.com/paper/2606.23096/) (2026)

## 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.