Algorithms for Differentially Private Multi-Armed Bandits

Aristide Tossou 1 Christos Dimitrakakis 2, 1, 3
2 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Type de document :
Communication dans un congrès
AAAI 2016, Feb 2016, Phoenix, Arizona, United States
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01234427
Contributeur : Christos Dimitrakakis <>
Soumis le : jeudi 26 novembre 2015 - 21:52:39
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32
Document(s) archivé(s) le : samedi 27 février 2016 - 13:50:35

Fichiers

single-mab-aaai16-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01234427, version 1
  • ARXIV : 1511.08681

Citation

Aristide Tossou, Christos Dimitrakakis. Algorithms for Differentially Private Multi-Armed Bandits. AAAI 2016, Feb 2016, Phoenix, Arizona, United States. 〈hal-01234427〉

Partager

Métriques

Consultations de la notice

218

Téléchargements de fichiers

156