IDEAS home Printed from https://ideas.repec.org/p/hal/journl/inria-00329797.html
   My bibliography  Save this paper

Online Optimization in X-Armed Bandits

Author

Listed:
  • 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 - LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal - Université de Lille, Sciences et Technologies - Ecole Centrale de Lille - CNRS - Centre National de la Recherche Scientifique - Inria Lille - Nord Europe - Inria - Institut National de Recherche en Informatique et en Automatique)

  • 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 - LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal - Université de Lille, Sciences et Technologies - Ecole Centrale de Lille - CNRS - Centre National de la Recherche Scientifique - Inria Lille - Nord Europe - Inria - Institut National de Recherche en Informatique et en Automatique)

  • Gilles Stoltz

    () (DMA - Département de Mathématiques et Applications - ENS Paris - ENS Paris - École normale supérieure - Paris - CNRS - Centre National de la Recherche Scientifique, GREGH - Groupement de Recherche et d'Etudes en Gestion à HEC - HEC Paris - Ecole des Hautes Etudes Commerciales - CNRS - Centre National de la Recherche Scientifique)

  • Csaba Szepesvari

    () (Department of Computing Science [Edmonton] - University of Alberta [Edmonton])

Abstract

We consider a generalization of stochastic bandit problems where the set of arms, X, is allowed to be a generic topological space. We constraint the mean-payoff function with a dissimilarity function over X in a way that is more general than Lipschitz. We construct an arm selection policy whose regret improves upon previous result for a large class of problems. In particular, our results imply that if X 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 Holder with a known exponent, then the expected regret is bounded up to a logarithmic factor by $\sqrt{n}$, i.e., the rate of the growth of the regret is independent of the dimension of the space. Moreover, we prove the minimax optimality of our algorithm for the class of mean-payoff functions we consider.

Suggested Citation

  • Sébastien Bubeck & Rémi Munos & Gilles Stoltz & Csaba Szepesvari, 2008. "Online Optimization in X-Armed Bandits," Post-Print inria-00329797, HAL.
  • Handle: RePEc:hal:journl:inria-00329797
    Note: View the original document on HAL open archive server: https://hal.inria.fr/inria-00329797
    as

    Download full text from publisher

    File URL: https://hal.inria.fr/inria-00329797/document
    Download Restriction: no

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sébastien Bubeck & Rémi Munos & Gilles Stoltz & Csaba Szepesvari, 2011. "X-Armed Bandits," Post-Print hal-00450235, HAL.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:journl:inria-00329797. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (CCSD). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.