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

Understand

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.