Exploration-exploitation tradeoff using variance estimates in multi-armed bandits

Jean-Yves Audibert 1, 2 Remi Munos 3 Csaba Szepesvari
1 IMAGINE [Marne-la-Vallée]
CSTB - Centre Scientifique et Technique du Bâtiment, LIGM - Laboratoire d'Informatique Gaspard-Monge, ENPC - École des Ponts ParisTech
2 WILLOW - Models of visual object recognition and scene understanding
CNRS - Centre National de la Recherche Scientifique : UMR8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
3 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : Algorithms based on upper confidence bounds for balancing exploration and exploitation are gaining popularity since they are easy to implement, efficient and effective. This paper considers a variant of the basic algorithm for the stochastic, multi-armed bandit problem that takes into account the empirical variance of the different arms. In earlier experimental works, Such algorithms were found to outperform the competing algorithms. We provide the first analysis of the expected regret for such algorithms. As expected, our results show that the algorithm that uses the variance estimates has a major advantage over its alternatives that do not use Such estimates provided that the variances of the payoffs of the suboptimal arms are low. We also prove that the regret concentrates only at a polynomial rate. This holds for all the upper confidence bound based algorithms and for all bandit problems except those special ones where with probability one the payoff obtained by pulling the optimal arm is larger than the expected payoff for the second best arm. Hence, although upper confidence bound bandit algorithms achieve logarithmic expected regret rates, they might not be Suitable for a risk-averse decision maker. We illustrate some of the results by Computer simulations. (C) 2009 Elsevier B.V. All rights reserved.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-enpc.archives-ouvertes.fr/hal-00711069
Contributeur : Ist Enpc <>
Soumis le : vendredi 22 juin 2012 - 12:04:20
Dernière modification le : vendredi 12 avril 2019 - 10:18:03

Lien texte intégral

Identifiants

Citation

Jean-Yves Audibert, Remi Munos, Csaba Szepesvari. Exploration-exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, Elsevier, 2009, 410 (19), pp.1876--1902. ⟨10.1016/j.tcs.2009.01.016⟩. ⟨hal-00711069⟩

Partager

Métriques

Consultations de la notice

718