lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits

By Kevin G. Jamieson, Matthew Malloy, Robert D. Nowak, Sébastien Bubeck. 2013

451 citations recorded by the source corpus.

The paper proposes a novel upper confidence bound (UCB) procedure for identifying the arm with the largest mean in a multi-armed bandit game in the fixed confidence setting using a small number of total samples. The procedure cannot be improved in the sense that the number of samples required to identify the best arm is within a constant factor of a lower bound based on the law of the iterated logarithm (LIL). Inspired by the LIL, we construct our confidence bounds to explicitly account for the infinite time horizon of the algorithm. In addition, by using a novel stopping time for the algorithm we avoid a union bound over the arms that has been observed in other UCB-type algorithms. We prove that the algorithm is optimal up to constants and also show through simulations that it provides superior performance with respect to the state-of-the-art.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

Citations in the corpus

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, background): “When q = 1 /K this implies that the best arm is identiﬁed with about log(1 /δ ) log( K ) =2 ∆ − 2 i which matches known upperbounds Karnin et al. (2013); Jamieson et al. (2014) and lower bounds Kaufmann et al. (2015) up to log factors.”
Non-stochastic Best Arm Identification and Hyperparameter Optimization (2015, methodology): “These algorithms rely on probability theory to determine how many times each arm must be pulled in order to decide if the arm is suboptimal and should no longer be pulled, either by explicitly discarding it, e.g., Successive Elimination (Even-Dar et al., 2006) and Exponential Gap Elimination (Karnin”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, background): “Such bounds have sparked recent interest in sequential decision making [18, 19, 20, 21, 22] but to the best of our knowledge we are the first to leverage them for RL.”
Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling (2018, background): “It generalizes results obtained by [18, 23] in the Gaussian case and by [3] without the uniformity in time, and also handles subsets of arms.”
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 [19, 13] and in the fixed budget setting [3, 10, 17, 8].”
Causal Bandits: Learning Good Interventions via Causal Inference (2016, methodology): “As alluded to above, causal bandit problems can be treated as classical multi-armed bandit problems by simply ignoring the causal model and extra observations and applying an existing best-arm identiﬁcation algorithm with well understood simple regret guarantees (Jamieson et al., 2014).”
Accurate Inference for Adaptive Linear Models (2017, background): “A variety of confidence bounds and corresponding rules have been proposed [Auer, 2002, Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010, Abbasi-Yadkori et al., 2011, Jamieson et al., 2014] based largely on tools in martingale theory of concentration and law of iterated logarithm.”
Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, methodology): “…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 inequalities.”
Conservative Bandits (2016, methodology): “The manager even thinks that perhaps a best-arm identification strategy from the bandit literature, such as the recent lil’UCB method of Jamieson et al. (2014), could be more suitable.”
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons (2020, methodology): “In the proof, we invoke the results shown by Jamieson et al. (2014); Chen et al. (2017).”
Optimal Best Arm Identification with Fixed Confidence (2016, unknown): “…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)).”
Simple regret for infinitely many armed bandits (2015, methodology): “Second, we compare SiRI to lil’UCB (Jamieson et al., 2014) designed for the best-arm identiﬁcation in the ﬁxed conﬁdence setting.”
Uniform, nonparametric, non-asymptotic confidence sequences (2018, methodology): “Both Jamieson et al. (2014) and Zhao et al. (2016) construct a constant boundary rather than a linear increasing boundary over each epoch.”
Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits (2022, background): “For the classical multiarmed bandits setting, there is extensive literature on PAC-arm identification problem (Even-Dar et al., 2006; Audibert and Bubeck, 2010; Kalyanakrishnan et al., 2012; Karnin et al., 2013; Jamieson et al., 2014), where the learner gets to see a noisy draw of absolute reward fe”
Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting (2014, methodology): “• lil’UCB (+LS) [10] : This is a UCB procedure and is run with β = 1, a = (2 + β)2/β2 = 9, and δ = ( νε 5(2+ε) )1/(1+ε) for input confidence ν.”