Algorithms for Differentially Private Multi-Armed 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 : 2016

Algorithms for Differentially Private Multi-Armed Bandits

Résumé

We present differentially private algorithms for the stochastic Multi-Armed Bandit (MAB) problem. This is a problem for applications such as adaptive clinical trials, experiment design, and user-targeted advertising where private information is connected to individual rewards. Our major contribution is to show that there exist $(\epsilon, \delta)$ differentially private variants of Upper Confidence Bound algorithms which have optimal regret, $O(\epsilon^{-1} + \log T)$. This is a significant improvement over previous results, which only achieve poly-log regret $O(\epsilon^{-2} \log^{2} T)$, because of our use of a novel interval-based mechanism. We also substantially improve the bounds of previous family of algorithms which use a continual release mechanism. Experiments clearly validate our theoretical bounds.
Fichier principal
Vignette du fichier
single-mab-aaai16-final.pdf (215.46 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01234427 , version 1 (26-11-2015)

Identifiants

Citer

Aristide C. Y. Tossou, Christos Dimitrakakis. Algorithms for Differentially Private Multi-Armed Bandits. AAAI 2016, Feb 2016, Phoenix, Arizona, United States. ⟨hal-01234427⟩
199 Consultations
256 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More