22070 articles – 15901 references  [version française]

hal-00450235, version 1

## X--Armed Bandits

Sébastien Bubeck () 1, Rémi Munos () 2, Gilles Stoltz () 34, Csaba Szepesvari () 5

(2010-01-20)

Abstract: We consider a generalization of stochastic bandits where the set of arms, $\cX$, is allowed to be a generic measurable space and the mean-payoff function is locally Lipschitz'' with respect to a dissimilarity function that is known to the decision maker. Under this condition we construct an arm selection policy, called HOO hierarchical optimistic optimization), with improved regret bounds compared to previous results for a large class of problems. In particular, our results imply that if $\cX$ is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally Hölder continuous with a known exponent, then the expected of HOO regret is bounded up to a logarithmic factor by $\sqrt{n}$, i.e., the rate of growth of the regret is independent of the dimension of the space. We also prove the minimax optimality of our algorithm when the dissimilarity is a metric.

• 1:  SEQUEL (INRIA Futurs)
• INRIA – CNRS : UMR8146 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – Ecole Centrale de Lille
• 2:  SEQUEL (INRIA Lille - Nord Europe)
• INRIA – CNRS : UMR8146 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – Ecole Centrale de Lille
• 3:  Département de Mathématiques et Applications (DMA)
• CNRS : UMR8553 – Ecole normale supérieure de Paris - ENS Paris
• 4:  Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH)
• GROUPE HEC – CNRS : UMR2959
• 5:  Department of Computing Science
• Department of Computing Science, University of Alberta
• Domain : Computer Science/Learning
Mathematics/Statistics
Statistics/Statistics Theory
Mathematics/Optimization and Control
Humanities and Social Sciences/Economies and finances
• Available versions :  v1 (2010-01-25) v2 (2011-04-13)

• hal-00450235, version 1
• oai:hal.archives-ouvertes.fr:hal-00450235
• From:
• Submitted on: Monday, 25 January 2010 17:26:34
• Updated on: Monday, 25 January 2010 17:30:29