Timezone: »

Online Optimization in X-Armed Bandits
Sebastien Bubeck · Remi Munos · Gilles Stoltz · Csaba Szepesvari

Wed Dec 10 07:30 PM -- 12:00 AM (PST) @
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 Hölder with a known exponent, then the expected regret is bounded up to a logarithmic factor by $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.

Author Information

Sebastien Bubeck (MSR)
Remi Munos (Google DeepMind)
Gilles Stoltz (HEC Paris)
Csaba Szepesvari (University of Alberta)

More from the Same Authors