Title :

Algorithms for Differentially Private Multi-Armed Bandits

Author(s) :

Tossou, Aristide [Auteur]
Dimitrakakis, Christos [Auteur]
Université de Lille, Sciences Humaines et Sociales
Sequential Learning [SEQUEL]

Conference title :

AAAI 2016

City :

Phoenix, Arizona

Country :

Etats-Unis d'Amérique

Start date of the conference :

2016-02-11

English keyword(s) :

differential privacy
regret
reinforcement learning
stochastic multi-armed bandits

HAL domain(s) :

Statistiques [stat]/Machine Learning [stat.ML]
Informatique [cs]/Cryptographie et sécurité [cs.CR]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL