Pure Exploration in Multi-armed Bandits Problems

By Sébastien Bubeck, R´emi Munos, Gilles Stoltz. 2009

579 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, background): “One may interpret this result as an extension of the distribution-dependent pure-exploration results of Bubeck et al. (2009); but in our case, our bounds hold when the number of pulls is potentially much smaller than the number of arms K.”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “arm identification problem, which is more suitable for the model selection task [7], [30], [50], [51], [72], [104].”
Learning to Learn for Global Optimization of Black Box Functions (2016, methodology): “We are therefore considering the ﬁnite horizon setting that is popular in AB tests Kohavi et al. [2009], Scott [2010] and is often studied under the umbrella of best arm identiﬁcation in the bandits literature [Bubeck et al., 2009, Gabillon et al., 2011, 2012, Hoffman et al., 2014].”
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, methodology): “and simple regret. We approximate the latter as the mean cumulative regret in the last 500 time-steps, a proxy for the quality of the ﬁnal policy (see further discussion on pure exploration settings, Bubeck et al. (2009)). Cumulative regret is computed based on the best expected reward, as is standa”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, methodology): “We note that the non-stochastic best arm setting is quite generally applicable, encompassing many problems including the stochastic best arm identification problem [1], less-well-behaved stochastic sources like max-bandits [10], exhaustive subset selection for feature extraction, and many optimizati”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, positive): “However it was shown in [Kleinberg et al., 2008] and [Bubeck et al., 2009b] that under a generalized version of equation (6.4) it is possible to circumvent the curse of dimensionality and obtain a regret of Õ( √ n).”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, background): “In fact, the average regret, RT /T , is a natural upper bound on the suboptimality of the best stimulus considered so far, i.e., RT /T ≥ mint [f(x∗)− f(xt)] (often called the simple regret, Bubeck et al. (2009)).”
Almost Optimal Exploration in Multi-Armed Bandits (2013, methodology): “Bubeck et al. (2013) considered the problem of multiple best-arm identification and presented a variant of the Successive Rejects algorithm that with high probability outputs a set of m-best arms given a fixed budget of pulls. They also presented extensions to their setting that deal with arms havin”
Regret Bounds for Gaussian Process Bandit Problems (2010, unknown): “The covariance of the posterior process is given by x, y (cid:105) := (cid:104) x, y (cid:105) Z := k ( x, y ) − k ( x, Z ) (cid:48) k ( Z, Z ) − 1 k ( Z, y ) .”
Convergence Rates of Efficient Global Optimization Algorithms (2011, methodology): “, 2010, and references therein), with noiseless data, and loss measured by the simple regret (Bubeck et al., 2009).”
Regret based Robust Solutions for Uncertain Markov Decision Processes (2013, background): “Extending the definitions of simple and cumulative regret in stochastic multi-armed bandit problems [2], we now define a new variant of regret called Cumulative Expected Regret (CER).”
Exploration from Demonstration for Interactive Reinforcement Learning (2016, methodology): “There are several value-based like UCB [6] and others [24, 7, 11] and model-based methods [35, 29, 18, 19], studied in the context of multi-arm bandits, that perform eﬀective exploration by maintaining statistics about changes in the value function and the number of times state-action pairs have…”
Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, methodology): “The best-arm identification or pure exploration problem has received a great deal of attention since then; we mention the influential work of Bubeck et al. (2009) and the proposals of Jamieson et al. (2014), Kaufmann et al. (2016), and Zhao et al. (2016), whose methods included iterated-logarithm…”
Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search (2012, background): “However, there is no actual benefit to accruing reward during planning, and so it is in theory more appropriate to use pure exploration bandits [4].”
Learning to Learn without Gradient Descent by Gradient Descent (2016, methodology): “efore considering the ﬁnite horizon setting that is popular in AB tests Kohavi et al. [2009], Scott [2010] and is often studied under the umbrella of best arm identiﬁcation in the bandits literature [Bubeck et al., 2009, Gabillon et al., 2011, 2012, Hoffman et al., 2014]. Our experiments will show t”
Decentralized Exploration in Multi-Armed Bandits (2018, background): “…duration of the exploration phase is fixed and is known by the forecaster, and the objective is to maximize the probability of returning the best arm (Bubeck et al, 2009; Audibert et al, 2010; Gabillon et al, 2013); • the fixed confidence setting: the objective is to minimize the number of rounds…”