X-Armed Bandits

By Sébastien Bubeck, R´emi Munos, Gilles Stoltz, Csaba Szepesvari. 2010

439 citations recorded by the source corpus.

We consider a generalization of stochastic bandits where the set of arms, X, 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 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 continuous with a known smoothness degree, then the expected regret of HOO is bounded up to a logarithmic factor by √n, that is, 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. Our basic strategy has quadratic computational complexity as a function of the number of time steps and does not rely on the doubling trick. We also introduce a modified strategy, which relies on the doubling trick but runs in linearithmic time. Both results are improvements with respect to previous approaches.

Subfields: Finance, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Finance

In Management Science and Operations Research

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, background): “Two related lines of work that both make use of an underlying metric space are Gaussian process optimization (Srinivas et al., 2009) and X -armed bandits (Bubeck et al., 2011), or bandits deﬁned over a metric space.”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “Recent proposed optimistic optimization methods provide an alternative to Bayesian optimization [31], [87], [116].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “We refer the reader to [52] for the details of this result (which is much more general than what we briefly outlined, in particular it applies for metric spaces, or even more general action sets), as well as a more precise historical account.”
Learning to Optimize via Posterior Sampling (2013, background): “e case where actions are described by a nite number of features and the reward function is linear in these features. Other authors have studied cases where the reward function is Lipschitz continuous [13,23,36], sampled from a Gaussian process [35], or takes the form of a generalized [18] or sparse ”
A Tutorial on Thompson Sampling (2017, background): “UCB algorithms have been proposed for a variety of problems, including bandit problems with independent arms [36, 53, 54, 55], bandit problems with linearly parameterized arms [30, 56], bandits with continuous action spaces and smooth reward functions [57, 58, 59], and exploration in reinforcement l”
Minimax Regret Bounds for Reinforcement Learning (2017, background): “ 1−δ: Eaz F∆e,k,h,H,log(1/δ) , (16) Eaz F′ ∆e,k,h ,1/ √ L,log(1/δ) , (17) Eaz Fb′,k,h,H 2,log(1/δ) . (18) Also Eq. 14 combined with a union bound argument over all N′ k,h(x) ∈ [T] (see, e.g., Bubeck et al., 2011, for the full description of the application of union bound argument in the case mar”
Lipschitz Continuity in Model-based Reinforcement Learning (2018, neutral): “…´ ari, 1996; M ¨ uller, 1996; Ferns et al., 2004; Hinderer, 2005; Rachelson & Lagoudakis, 2010; Szepesv´ari, 2010; Pazis & Parr, 2013; Pirotta et al., 2015; Pires & Szepesv ´ ari, 2016; Berkenkamp et al., 2017; Bellemare et al., 2017) and bandits (Kleinberg et al., 2008; Bubeck et al., 2011).”
Stochastic Convex Optimization with Bandit Feedback (2011, background): “[7] show √ T regret for a subset of Lipschitz functions with certain metric properties.”
Time-Sensitive Bandit Learning and Satisficing Thompson Sampling (2017, background): “Many papers [5, 12, 13] have studied bandit problems with continuous action spaces, where it is also necessary to learn only approximately optimal actions.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, background): “Analysis of HOO The bound reported in [34] is in terms of the”
Optimal Best Arm Identification with Fixed Confidence (2016, background): “…efﬁcient strategies in much more elaborate settings, for example including side information ( Abbasi-Yadkori et al., 2011; Agrawal and Goyal, 2013), inﬁnitely many arms (Srinivas et al., 2010; Bubeck et al., 2011), or for the search of optimal strategies in games (Munos, 2014), to name just a few.”
Bayesian Multi-Scale Optimistic Optimization (2014, methodology): “Remarkably, a variant of these methods, Simultaneous Optimistic Optimization (SOO) by Munos (2011), is able to optimize an objective function globally without knowledge of the function’s smoothness.”
Online Learning with Switching Costs and Other Adaptive Adversaries (2013, background): “…bandit feedback is strictly harder than learning with full-information, even on a small ﬁnite action set and even in terms of the dependence on T (previous gaps we are aware of were either in terms of the number of actions [4], or required large or continuous action spaces —see, e.g., [6, 21]).”
Copeland Dueling Bandits (2015, positive): “Given that both our algorithms utilize confidence bounds to make their choices, we anticipate that continuous-armed UCB-style algorithms like those proposed in [24, 25, 26, 27, 28, 29, 30] can be combined with our ideas to produce a solution to the continuous-armed Copeland bandit problem that does ”
Learning to Optimize via Information-Directed Sampling (2014, background): “Specific UCB algorithms and Thompson sampling are known to be asymptotically efficient for multi–armed bandit problems with independent arms [5, 16, 33, 38, 39] and satisfy strong regret bounds for some problems with dependent arms [15, 20, 21, 27, 44, 46, 51].”