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

Abstract

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\in (0,1]$. In the first part, we study the problem in the central $\epsilon$-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 $\epsilon$-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.

Accepted for oral presentation at AISTATS 2022. A preliminary version of this paper was presented at the CCS 2021 workshop Privacy Preserving Machine Learning (PPML'21). In this version, we fixed some typos

References in corpus (13)

• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• Differentially-Private Federated Linear Bandits
• Multi-Armed Bandits with Local Differential Privacy
• Corrupt Bandits for Preserving Local Privacy
• Locally Differentially Private (Contextual) Bandits Learning
• Propose, Test, Release: Differentially private estimation with high probability
• Robust and Differentially Private Mean Estimation
• An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule
• On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data
• Privacy-Preserving Multi-Party Contextual Bandits
• A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis
• Local Differential Privacy for Bayesian Optimization
• Regret Minimization in Heavy-Tailed Bandits

Cited by in corpus (1)

• Regret Minimization in Isotonic, Heavy-Tailed Contextual Bandits via Adaptive Confidence Bands