When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits

Achraf Azize
  • Fonction : Auteur
Debabrota Basu

Résumé

We study the problem of multi-armed bandits with $\epsilon$-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and linear bandits that quantify the hardness of bandits with $\epsilon$-global DP. These bounds suggest the existence of two hardness regimes depending on the privacy budget $\epsilon$. In the high-privacy regime (small $\epsilon$), the hardness depends on a coupled effect of privacy and partial information about the reward distributions. In the low-privacy regime (large $\epsilon$), bandits with $\epsilon$-global DP are not harder than the bandits without privacy. For stochastic bandits, we further propose a generic framework to design a near-optimal $\epsilon$ global DP extension of an index-based optimistic bandit algorithm. The framework consists of three ingredients: the Laplace mechanism, arm-dependent adaptive episodes, and usage of only the rewards collected in the last episode for computing private statistics. Specifically, we instantiate $\epsilon$-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB and AdaP-KLUCB. AdaP-KLUCB is the first algorithm that both satisfies $\epsilon$-global DP and yields a regret upper bound that matches the problem-dependent lower bound up to multiplicative constants.
Fichier principal
Vignette du fichier
When_Privacy_Meets_Partial_Information-2.pdf (626.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03781600 , version 1 (20-09-2022)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Achraf Azize, Debabrota Basu. When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits. Advances in Neural Information Processing Systems, Dec 2022, New Orleans, United States. ⟨hal-03781600⟩
28 Consultations
16 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More