Pure Exploration for Multi-Armed Bandit Problems

Sébastien Bubeck (), Rémi Munos () and Gilles Stoltz
Additional contact information
Sébastien Bubeck: SEQUEL - Sequential Learning - LIFL - Laboratoire d'Informatique Fondamentale de Lille - Université de Lille, Sciences et Technologies - Inria - Institut National de Recherche en Informatique et en Automatique - Université de Lille, Sciences Humaines et Sociales - CNRS - Centre National de la Recherche Scientifique - Centre Inria de l'Université de Lille - Inria - Institut National de Recherche en Informatique et en Automatique - LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal - Université de Lille, Sciences et Technologies - Centrale Lille - CNRS - Centre National de la Recherche Scientifique
Rémi Munos: SEQUEL - Sequential Learning - LIFL - Laboratoire d'Informatique Fondamentale de Lille - Université de Lille, Sciences et Technologies - Inria - Institut National de Recherche en Informatique et en Automatique - Université de Lille, Sciences Humaines et Sociales - CNRS - Centre National de la Recherche Scientifique - Centre Inria de l'Université de Lille - Inria - Institut National de Recherche en Informatique et en Automatique - LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal - Université de Lille, Sciences et Technologies - Centrale Lille - CNRS - Centre National de la Recherche Scientifique

Working Papers from HAL

Abstract: We consider the framework of stochastic multi-armed bandit problems and study the possibilities and limitations of forecasters that perform an on-line exploration of the arms. These forecasters are assessed in terms of their simple regret, a regret notion that captures the fact that exploration is only constrained by the number of available rounds (not necessarily known in advance), in contrast to the case when the cumulative regret is considered and when exploitation needs to be performed at the same time. We believe that this performance criterion is suited to situations when the cost of pulling an arm is expressed in terms of resources rather than rewards. We discuss the links between the simple and the cumulative regret. One of the main results in the case of a finite number of arms is a general lower bound on the simple regret of a forecaster in terms of its cumulative regret: the smaller the latter, the larger the former. Keeping this result in mind, we then exhibit upper bounds on the simple regret of some forecasters. The paper ends with a study devoted to continuous-armed bandit problems; we show that the simple regret can be minimized with respect to a family of probability distributions if and only if the cumulative regret can be minimized for it. Based on this equivalence, we are able to prove that the separable metric spaces are exactly the metric spaces on which these regrets can be minimized with respect to the family of all probability distributions with continuous mean-payoff functions.

Date: 2010-06-08
Note: View the original document on HAL open archive server: https://hal.science/hal-00257454v6
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://hal.science/hal-00257454v6/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:hal-00257454

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().