Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting

By Kevin G. Jamieson, Robert D. Nowak. 2014

224 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, 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 Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Bandit Algorithms (2020, background): “A more philosophical book that takes a foundational look at probability theory from a Bayesian perspective is by Jaynes [2003]. The careful definition of the posterior can be found in several places, but the recent book by Ghosal and van der Vaart [2017] does an impeccable job.”
The Power of Adaptivity in Identifying Statistical Alternatives (2016, unknown): “In the best-arm identification problem, the player has access to K distributions (arms) such that if arm i 2 [K] is sampled (pulled), an iid random variable with mean μ i is observed; the objective is to identify the arm associated with the highest mean with probability at least 1 using as few pulls”
Hyperband: Bandit-Based Configuration Evaluation for Hyperparameter Optimization (2016, background): “Since subsets of the validation set provide unbiased estimates of its expected performance, this is an instance of the stochastic best-arm identiﬁcation problem for multi-armed bandits (see Jamieson & Nowak (2014) for a brief survey).”
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].”
Time-uniform, nonparametric, nonasymptotic confidence sequences (2018, methodology): “Confidence sequences are a key ingredient in best-arm selection algorithms (Jamieson and Nowak, 2014) and related methods for sequential testing with multiple comparisons (Yang et al.”
Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, methodology): “For ∈ (0, 1− π), we say arm k is -optimal if Qk(π + ) ≥ Qj(π) for all j 6= k. Kalyanakrishnan et al. (2012) introduced the LUCB algorithm for highest mean identification, for which Jamieson and Nowak (2014) gave a simplified analysis in the = 0 case.”
Uniform, nonparametric, non-asymptotic confidence sequences (2018, unknown): “• Jamieson and Nowak (2014), Lemma 1: for i.i.d. sub-Gaussian observations with variance parameter σ2, P ( ∃t ≥ 1 : St ≥ (1 + √ ) √ 2σ2(1 + )t log ( log((1 + )t) δ )) ≤ 1− 2 + ( δ log(1 + ) )1+ .”