%0 Conference Paper %1 bubeck2008 %A Bubeck, S. %A Munos, R. %A Stoltz, G. %A Szepesvári, Cs. %B NIPS %D 2008 %E Koller, D. %E Schuurmans, D. %E Bengio, Y. %E Bottou, L. %I MIT Press %K action bandits, bounds large minimax multi-armed space, stochastic theory, %P 201--208 %T Online Optimization in X-armed Bandits %X We consider a generalization of stochastic bandit problems where the set of arms, X, is allowed to be a generic topological 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 whose regret improves upon previous results 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 Hölder 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. We also prove the minimax optimality of our algorithm for the class of problems considered.

@inproceedings{bubeck2008, abstract = {We consider a generalization of stochastic bandit problems where the set of arms, X, is allowed to be a generic topological 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 whose regret improves upon previous results 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 H{\"o}lder 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. We also prove the minimax optimality of our algorithm for the class of problems considered.}, added-at = {2020-03-17T03:03:01.000+0100}, author = {Bubeck, S. and Munos, R. and Stoltz, G. and Szepesv{\'a}ri, {Cs}.}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/23674e15d9493d9734a0fec24471f46a0/csaba}, booktitle = {NIPS}, crossref = {NIPS21}, date-added = {2010-08-28 17:38:14 -0600}, date-modified = {2012-01-21 16:46:10 -0700}, editor = {Koller, D. and Schuurmans, D. and Bengio, Y. and Bottou, L.}, ee = {http://books.nips.cc/papers/files/nips21/NIPS2008_0553.pdf}, interhash = {8c728c86efd1f60669195efc035b6b94}, intrahash = {3674e15d9493d9734a0fec24471f46a0}, keywords = {action bandits, bounds large minimax multi-armed space, stochastic theory,}, pages = {201--208}, pdf = {papers/HOO-NIPS08.pdf}, publisher = {MIT Press}, timestamp = {2020-03-17T03:03:01.000+0100}, title = {Online Optimization in {X}-armed Bandits}, year = 2008 }