Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?

Abstract

Based on differential privacy (DP) framework, we introduce and unify privacy definitions for the multi-armed bandit algorithms. We represent the framework with a unified graphical model and use it to connect privacy definitions. We derive and contrast lower bounds on the regret of bandit algorithms satisfying these definitions. We leverage a unified proving technique to achieve all the lower bounds. We show that for all of them, the learner's regret is increased by a multiplicative factor dependent on the privacy level $\epsilon$. We observe that the dependency is weaker when we do not require local differential privacy for the rewards.

27 pages, 1 figure, 2 tables, 14 theorems

References in corpus (3)

• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• Differentially Private Contextual Linear Bandits
• Pan-private Algorithms: When Memory Does Not Help

Cited by in corpus (11)

• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Multi-Armed Bandits with Local Differential Privacy
• Locally Differentially Private (Contextual) Bandits Learning
• Generalized Linear Bandits with Local Differential Privacy
• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• Local Differential Privacy for Bayesian Optimization
• Optimal Order Simple Regret for Gaussian Process Bandits
• (Locally) Differentially Private Combinatorial Semi-Bandits
• Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients
• No-Regret Algorithms for Private Gaussian Process Bandit Optimization
• Privacy-Preserving Bandits