Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits

Alexandra Carpentier 1 Alessandro Lazaric 1 Mohammad Ghavamzadeh 1 Rémi Munos 1 Peter Auer 2
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : In this paper, we study the problem of estimating the mean values of all the arms uniformly well in the multi-armed bandit setting. If the variances of the arms were known, one could design an optimal sampling strategy by pulling the arms proportionally to their variances. However, since the distributions are not known in advance, we need to design adaptive sampling strategies to select an arm at each round based on the previous observed samples. We describe two strategies based on pulling the arms proportionally to an upper-bound on their variances and derive regret bounds for these strategies. %on the excess estimation error compared to the optimal allocation. We show that the performance of these allocation strategies depends not only on the variances of the arms but also on the full shape of their distributions.
Type de document :
Communication dans un congrès
ALT - the 22nd conference on Algorithmic Learning Theory, Oct 2011, Espoo, Finland. 2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00659696
Contributeur : Alexandra Carpentier <>
Soumis le : vendredi 13 janvier 2012 - 14:46:53
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : lundi 19 novembre 2012 - 13:35:39

Fichier

adapt_alloc_tech-report.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00659696, version 1

Collections

Citation

Alexandra Carpentier, Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos, Peter Auer. Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits. ALT - the 22nd conference on Algorithmic Learning Theory, Oct 2011, Espoo, Finland. 2011. 〈hal-00659696〉

Partager

Métriques

Consultations de la notice

750

Téléchargements de fichiers

1317