Asymptotically efficient adaptive allocation rules

By Tze Leung Lai, H. Robbins. 1985

How researchers see this paper

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

In Statistics and Probability

Citations in the corpus

Reinforcement Learning with Deep Energy-Based Policies (2017, background): “During the learning process, it is often best to keep trying multiple available options until the agent is confident that one of them is the best (similar to a bandit problem (Lai & Robbins, 1985)).”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “In the bandits setting, Lai and Robbins [92] introduced upper conﬁdence bounds (UCB) as approximate alternatives to Gittins indices in 1985.”
Balanced Linear Contextual Bandits (2018, methodology): “Thompson Sampling (Thompson 1933), (Scott 2010), (Agrawal and Goyal 2012), (Russo et al. 2018) and Upper Conﬁ-dence Bounds (UCB) (Lai and Robbins 1985), (Auer, Cesa-Bianchi, and Fischer 2002) are two different methods which are highly effective in dealing with the exploration vs. exploitation…”
Learning to Learn for Global Optimization of Black Box Functions (2016, background): “…2015], probability of improvement [Kushner, 1964, Jones et al., 1998], expected improvement [Moˇckus et al., 1978, Jones et al., 1998, Jones, 2001, Brochu et al., 2009, Snoek et al., 2012, Wang and de Freitas, 2014], upper conﬁdence bounds [Lai and Robbins, 1985, Srinivas et al., 2010], and so on.”
The Uncertainty Bellman Equation and Exploration (2017, background): “For this reason, most provably-efﬁcient approaches to reinforcement learning rely upon the optimism in the face of uncertainty (OFU) heuristic [14, 13, 7].”
Deep Exploration via Bootstrapped DQN (2016, background): “This approach was first proposed for finite-armed bandits [11], but the principle has been extended successfully across bandits with generalization and tabular RL [9].”
A contextual-bandit approach to personalized news article recommendation (2010, methodology): “In contrast to the unguided exploration strategy adopted by ǫ - greedy , another class of algorithms generally known as upper con-ﬁdence bound algorithms [4, 7, 17] use a smarter way to balance exploration and exploitation.”
Fairness in Learning: Classic and Contextual Bandits (2016, methodology): “First, we study the classic stochastic multi-armed bandit problem [Lai and Robbins, 1985, Katehakis and Robbins, 1995].”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, background): “To oﬀset this, the majority of provably eﬃcient learning algorithms use a principle known as optimism in the face of uncertainty [3] to encourage exploration.”
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…”
On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models (2014, methodology): “In generic one-parameter models, Lai and Robbins (1985) prove that, with a proper notion of consistency adapted to regret minimization, inf where KL( ν i , ν j ) denotes the Kullback-Leibler divergence between distributions ν i and ν j .”
Thompson Sampling for Contextual Bandits with Linear Payoffs (2012, background): “Chapelle & Li (2011) demonstrate that for the basic stochastic MAB problem, empirically TS achieves regret comparable to the lower bound of Lai & Robbins (1985); and in applications like display advertising and news article recommendation modeled by the contextual bandits problem, it is competitive…”
Cognitive Medium Access: Exploration, Exploitation, and Competition (2007, methodology): “The proof is an application of a theorem proved in [13].”
Exploration scavenging (2008, background): “Introduction The k-armed bandit problem (Lai & Robbins, 1985; Berry & Fristedt, 1985; Auer et al., 2002; Even-Dar et al., 2006) has been studied in great detail, primarily because it can be viewed as a minimal formalization of the exploration problem faced by any autonomous agent.”
Further Optimal Regret Bounds for Thompson Sampling (2012, methodology): “…many algorithms available for the stochastic bandit problem, some popular ones include Upper Conﬁdence Bound (UCB) family of algorithms, (e.g., [15, 4], and more recently [3, 8, 16, 13]), which have good theoretical guarantees, and the algorithm by [9], which gives optimal strategy under…”
Counterfactual Data-Fusion for Online Reinforcement Learners (2017, background): “In ofﬂine settings, however, counterfactual quantities are not empirically estimable (namely, when the antecedent of the counterfactual contradicts the observed value), except in some special cases ((12), Chs. 7, 9).”
Contextual Bandits with Similarity Information (2009, background): “By now the MAB problem with a small ﬁnite set of arms is quite well understood (e.g. see [26, 4, 3]).”