Timezone: »
Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
Yulian Wu · Youming Tao · Peng Zhao · Di Wang
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.
Author Information
Yulian Wu (King Abdullah University of Science and Technology)
Youming Tao (Shandong University)
Peng Zhao (Nanjing University)
Di Wang (KAUST)
More from the Same Authors
-
2023 Poster: Fast Rates in Time-Varying Strongly Monotone Games »
Yu-Hu Yan · Peng Zhao · Zhi-Hua Zhou -
2023 Poster: Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization »
SIJIA CHEN · Wei-Wei Tu · Peng Zhao · Lijun Zhang -
2023 Poster: Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards »
Yulian Wu · Xingyu Zhou · Sayak Ray Chowdhury · Di Wang -
2022 : Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits »
Yulian Wu -
2022 Poster: No-Regret Learning in Time-Varying Zero-Sum Games »
Mengxiao Zhang · Peng Zhao · Haipeng Luo · Zhi-Hua Zhou -
2022 Spotlight: No-Regret Learning in Time-Varying Zero-Sum Games »
Mengxiao Zhang · Peng Zhao · Haipeng Luo · Zhi-Hua Zhou -
2022 Poster: Dynamic Regret of Online Markov Decision Processes »
Peng Zhao · Long-Fei Li · Zhi-Hua Zhou -
2022 Spotlight: Dynamic Regret of Online Markov Decision Processes »
Peng Zhao · Long-Fei Li · Zhi-Hua Zhou -
2020 Poster: Learning with Feature and Distribution Evolvable Streams »
Zhen-Yu Zhang · Peng Zhao · Yuan Jiang · Zhi-Hua Zhou