Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence

By Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric. 2012

339 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

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].”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, methodology): “Despite these challenges, in Section 3 we identify an effective algorithm under natural measures of performance, using ideas inspired by the fixed budget setting of the stochastic best arm problem (Karnin et al., 2013; Audibert & Bubeck, 2010; Gabillon et al., 2012).”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “Gabillon et al. (2012) propose the UGapE algorithm for m best arm identification for m > 1.”
Simple regret for infinitely many armed bandits (2015, background): “The problem of minimizing the simple regret in a multi-armed bandit setting (with finitely many arms) has recently attracted significant attention (Even-Dar et al., 2006; Audibert et al., 2010; Kalyanakrishnan et al., 2012; Kaufmann & Kalyanakrishnan, 2013; Karnin et al., 2013; Gabillon et al., 2012”
Identifying Best Interventions through Online Importance Sampling (2017, background): “There have been many studies on the classical best arm identification in the bandit literature, both in the fixed confidence regime (Kaufmann et al., 2015; Gabillon et al., 2012) and in the fixed budget setting (Audibert & Bubeck, 2010; Chen & Li, 2015; Jamieson et al.”
A new acquisition function for Bayesian optimization based on the moment-generating function (2017, background): “There are some other, less popular acquisition functions: BayesGap [23] and UGap [24], which are gap-based exploration approaches.”
Almost Optimal Exploration in Multi-Armed Bandits (2013, background): “Our work is related to (Gabillon et al., 2012), that also consider both the fixed confidence and fixed budget variants of the problem.”
Simple Bayesian Algorithms for Best Arm Identification (2016, background): “…large body of work in the recent machine learning literature has sought to characterize various notions of the complexity of best-arm identification [Even-Dar et al., 2002, Mannor and Tsitsiklis, 2004, Audibert and Bubeck, 2010, Gabillon et al., 2012, Karnin et al., 2013, Jamieson and Nowak, 2014].”
Bayesian Optimization and Semiparametric Models with Applications to Assistive Technology (2014, background): “We note that a similar approach is touched upon briefly by Ginsbourger and Riche [2010b], but they view it as too intractable to warrant attention.”
Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting (2014, background): “The sample complexity result derived for LUCB 978-1-4799-3001-2/14/$31.00 ©2014 IEEE is the best known result for the LUCB sampling strategy improving the result of ∑ i6=i∗ ∆ −2 i log( ∑ j 6=i∗ ∆ −2 j ) [7] to∑ i6=i∗ ∆ −2 i log ( n log(∆−2i ) ) .”
Optimal Best Arm Identification with Fixed Confidence (2016, background): “…arms (Even-Dar et al. (2006); Kaufmann and Kalyanakrishnan (2013)), another family of strategies exploits the use of upper and lower conﬁdence bounds on the means of the arms (Kalyanakrishnan et al. (2012); Gabillon et al. (2012); Kaufmann and Kalyanakrishnan (2013); Jamieson et al. (2014)).”
Learning to Learn without Gradient Descent by Gradient Descent (2016, methodology): “We are therefore considering the finite horizon setting that is popular in AB tests (Kohavi et al., 2009; Scott, 2010) and is often studied under the umbrella of best arm identification in the bandits literature (Bubeck et al., 2009; Gabillon et al., 2012).”
On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning (2014, methodology): “3The additional Theorem is in supplementary material and is a slight modification of that in [Gabillon et al., 2012].”
Causal Bandits: Learning Good Interventions via Causal Inference (2016, background): “This is sometimes refered to as a “pure exploration” (Bubeck et al., 2009) or “best-arm identiﬁcation” problem (Gabillon et al., 2012) and is most appropriate when, as in drug and policy testing, the learner has a ﬁxed experimental budget after which its policy will be ﬁxed indeﬁnitely.”
Decentralized Exploration in Multi-Armed Bandits (2018, methodology): “…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 ﬁxed conﬁdence setting: the objective is to minimize the number of rounds needed to achieve a ﬁxed conﬁdence to…”