On Bayesian Upper Confidence Bounds for Bandit Problems

By Emilie Kaufmann, Olivier Capp'e, Aurélien Garivier. 2012

414 citations recorded by the source corpus.

Subfields: Reinforcement Learning, Probabilistic & Bayesian Methods

How researchers see this paper

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

In Reinforcement Learning

In Probabilistic & Bayesian Methods

Citations in the corpus

Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “The GP-UCB algorithm has since been generalized to other Bayesian models by considering upper quantiles [84] instead of Equation (45) deﬁned below, which is more reminiscent of frequentist concentration bounds.”
Learning to reinforcement learn (2016, methodology): “Model simulations were conducted with the PymaBandits toolbox from (Kaufmann et al., 2012a) and custom Matlab scripts.”
Learning to Learn for Global Optimization of Black Box Functions (2016, background): “This wide variety of possible models highlights how broad and encompassing this approach can be, despite the fact that it is often associated with Gaussian processes, to the point of receiving the name of Gaussian process bandits in the literature [Srinivas et al., 2010, Kaufmann et al., 2012].”
The Uncertainty Bellman Equation and Exploration (2017, methodology): “If we had access to the true posterior distribution over the Q-values then we could take actions that lead to states with higher uncertainty by, for example, using Thompson sampling (Thompson, 1933; Strens, 2000), or constructing Q-values that are high probability upper bounds on the true Q-values a”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “egret lower bound, up to constants, [5]. In the Bayesian case Thompson sampling also achieves close to the regret bound [87, 88], as does Bayes-UCB which aims to combine Bayesian methods and optimism [40]. A stochastic multi-armed bandit problem is dened by the pair fA;R g, where A 2 N is the number”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “In particular this shows that, as far as high probability bounds are concerned, anytime strategies are surprisingly weaker than strategies using the time horizon information (for which exponential concentration of R̂n around lnn are possible, see Audibert et al. [2009]).”
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): “…algorithms include the KL-UCB algo-rithm of Capp´e et al. (2013)—a variant of UCB1 (Auer et al. (2002)) using informational upper bounds, Thompson Sampling (Kaufmann et al. (2012b); Agrawal and Goyal (2013)), the DMED algorithm (Honda and Takemura, 2011) and Bayes-UCB (Kaufmann et al., 2012a).”
Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis (2012, background): “…1− 1 t ln(T ) , πa,t ) . where Q(α, π) denotes the quantile of order α of the distribution π • A special link between these two indices is shown in [9]: qa,t < ua,t. 2In Appendix A of [1] the authors show that adding a second optimal arm can only improve the regret performance of Thompson Sampling.”
Simple Bayesian Algorithms for Best Arm Identification (2016, methodology): “See Kim and Nelson [2006] and Kim and Nelson [2007] for reviews.”
Near-Optimal Regret Bounds for Thompson Sampling (2017, methodology): “Our regret bound in Theorem 1.1 achieves the lower bounds of Lai and Robbins (1985) and matches the upper bounds provided by Kaufmann et al. (2012b) for TS. Theorem 1.2 and 1.3 show that TS with Beta distribution and TS with Gaussian distribution achieve a problem-independent regret bound of O ( √…”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “…which has been analyzed recently in [Agrawal and Goyal, 2012, Kauffmann et al., 2012, Agrawal and Goyal, 2013, Kaufmann et al., 2013], the Gittins indexes, see [Gittins., 1979, Gittins et al., 1989], and optimistic Bayesian algorithms such as in [Srinivas et al., 2010, Kauffman et al., 2012]).”
Bandit Algorithms (2020, background): “The Kiefer–Wolfowitz theorem is due to Kiefer and Wolfowitz [1960]. The algorithm in Note 3 is due to Fedorov [1972].”
Online Learning: A Comprehensive Survey (2018, methodology): “A special case of Markovian bandits is Bayesian bandits (Scott, 2010; Gittins et al., 2011; Kaufmann et al., 2012), which are parametric stochastic bandits where the parameters of the reward distributions are assumed to be drawn from known priors, and the regret is computed by also averaging over…”
Contextual Bandits with Latent Confounders: An NMF Approach (2016, neutral): “Uniform prior on reward that has been used in bandit setting [26] reduces to a special case of this model.”