Thompson sampling for one-dimensional exponential family bandits

Korda, Nathaniel; Kaufmann, Emilie; Munos, Rémi

Document type :

Communication dans un congrès avec actes

Title :

Thompson sampling for one-dimensional exponential family bandits

Author(s) :

Korda, Nathaniel [Auteur]
Sequential Learning [SEQUEL]
Kaufmann, Emilie [Auteur]

Laboratoire Traitement et Communication de l'Information [LTCI]
Munos, Rémi [Auteur]
Sequential Learning [SEQUEL]

Conference title :

Advances in Neural Information Processing Systems

Country :

Etats-Unis d'Amérique

Start date of the conference :

2013

Book title :

Advances in Neural Information Processing Systems

Publication date :

2013

HAL domain(s) :

Informatique [cs]/Apprentissage [cs.LG]

English abstract : [en]

Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by ...
Show more >Thompson Sampling has been demonstrated in many complex bandit models, however the theoretical guarantees available for the parametric multi-armed bandit are still limited to the Bernoulli case. Here we extend them by proving asymptotic optimality of the algorithm using the Jeffreys prior for 1-dimensional exponential family bandits. Our proof builds on previous work, but also makes extensive use of closed forms for Kullback-Leibler divergence and Fisher information (and thus Jeffreys prior) available in an exponential family. This allow us to give a finite time exponential concentration inequality for posterior distributions on exponential families that may be of interest in its own right. Moreover our analysis covers some distributions for which no optimistic algorithm has yet been proposed, including heavy-tailed exponential families.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

Files

https://hal.archives-ouvertes.fr/hal-00923683/document
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-00923683/document
Open access
Access the document

document
Open access
Access the document

nips13-TS.pdf
Open access
Access the document

document
Open access
Access the document

nips13-TS.pdf
Open access
Access the document

Thompson sampling for one-dimensional ... BibTeX CSV Excel RIS

Files

Thompson sampling for one-dimensional ...

BibTeX

CSV

Excel

RIS