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

Understand

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.