Improved Learning Complexity in Combinatorial Pure Exploration Bandits

Gabillon, Victor; Lazaric, Alessandro; Ghavamzadeh, Mohammad; Ortner, Ronald; Bartlett, Peter

Type de document :

Communication dans un congrès avec actes

Titre :

Improved Learning Complexity in Combinatorial Pure Exploration Bandits

Auteur(s) :

Gabillon, Victor [Auteur]
Queensland University of Technology [Brisbane] [QUT]
Lazaric, Alessandro [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Sequential Learning [SEQUEL]
Ghavamzadeh, Mohammad [Auteur]
Sequential Learning [SEQUEL]
Adobe Systems Inc. [Adobe Advanced Technology Labs]
Ortner, Ronald [Auteur]
Montanuniversität Leoben [MUL]
Bartlett, Peter [Auteur]
Queensland University of Technology [Brisbane] [QUT]

Titre de la manifestation scientifique :

Proceedings of the 19th International Conference on Artificial Intelligence (AISTATS)

Ville :

Cadiz

Pays :

Espagne

Date de début de la manifestation scientifique :

2016-05

Date de publication :

2016

Discipline(s) HAL :

Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Extraction et transfert de connaissances dans l'apprentissage par renforcement

Collections :