Improved Learning Complexity in Combinatorial Pure Exploration Bandits

Abstract : We study the problem of combinatorial pure exploration in the stochastic multi-armed bandit problem. We first construct a new measure of complexity that provably characterizes the learning performance of the algorithms we propose for the fixed confidence and the fixed budget setting. We show that this complexity is never higher than the one in existing work and illustrate a number of configurations in which it can be significantly smaller. While in general this improvement comes at the cost of increased computational complexity, we provide a series of examples , including a planning problem, where this extra cost is not significant.
Type de document :
Communication dans un congrès
Proceedings of the 19th International Conference on Artificial Intelligence (AISTATS), May 2016, Cadiz, Spain. 2016
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01322198
Contributeur : Alessandro Lazaric <>
Soumis le : jeudi 26 mai 2016 - 17:25:55
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32
Document(s) archivé(s) le : samedi 27 août 2016 - 11:01:03

Fichier

AISTATS_full_CR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01322198, version 1

Collections

Citation

Victor Gabillon, Alessandro Lazaric, Mohammad Ghavamzadeh, Ronald Ortner, Peter Bartlett. Improved Learning Complexity in Combinatorial Pure Exploration Bandits. Proceedings of the 19th International Conference on Artificial Intelligence (AISTATS), May 2016, Cadiz, Spain. 2016. 〈hal-01322198〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

34