Kullback-Leibler upper confidence bounds for optimal sequential allocation
From MaRDI portal
Publication:366995
DOI10.1214/13-AOS1119zbMATH Open1293.62161arXiv1210.1136OpenAlexW3100329718MaRDI QIDQ366995FDOQ366995
Authors: Olivier Cappé, Odalric-Ambrym Maillard, Rémi Munos, Gilles Stoltz, Aurélien Garivier 
Publication date: 25 September 2013
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: We consider optimal sequential allocation in the context of the so-called stochastic multi-armed bandit model. We describe a generic index policy, in the sense of Gittins [J. R. Stat. Soc. Ser. B Stat. Methodol. 41 (1979) 148-177], based on upper confidence bounds of the arm payoffs computed using the Kullback-Leibler divergence. We consider two classes of distributions for which instances of this general idea are analyzed: the kl-UCB algorithm is designed for one-parameter exponential families and the empirical KL-UCB algorithm for bounded and finitely supported distributions. Our main contribution is a unified finite-time analysis of the regret of these algorithms that asymptotically matches the lower bounds of Lai and Robbins [Adv. in Appl. Math. 6 (1985) 4-22] and Burnetas and Katehakis [Adv. in Appl. Math. 17 (1996) 122-142], respectively. We also investigate the behavior of these algorithms when used with general bounded rewards, showing in particular that they provide significant improvements over the state-of-the-art.
Full work available at URL: https://arxiv.org/abs/1210.1136
Recommendations
- A minimax and asymptotically optimal algorithm for stochastic bandits
- Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
- On Bayesian index policies for sequential resource allocation
- Adaptive treatment allocation and the multi-armed bandit problem
- Tuning Bandit Algorithms in Stochastic Environments
Learning and adaptive systems in artificial intelligence (68T05) Sequential statistical analysis (62L10) Sequential estimation (62L12)
Cites Work
- Graphical models, exponential families, and variational inference
- Asymptotic Statistics
- Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
- Title not available (Why is that?)
- Empirical likelihood
- Probability Inequalities for Sums of Bounded Random Variables
- Sequential Tests of Statistical Hypotheses
- Title not available (Why is that?)
- Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
- Asymptotically efficient adaptive allocation rules
- On the Gittins index for multiarmed bandits
- Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some aspects of the sequential design of experiments
- Finite-time analysis of the multiarmed bandit problem
- Regret bounds and minimax policies under partial monitoring
- Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
- Kullback-Leibler upper confidence bounds for optimal sequential allocation
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Thompson sampling: an asymptotically optimal finite-time analysis
- Optimal stopping and dynamic allocation
- An asymptotically optimal policy for finite support models in the multiarmed bandit problem
- Optimal Adaptive Policies for Markov Decision Processes
- Optimal adaptive policies for sequential allocation problems
- ASYMPTOTIC BAYES ANALYSIS FOR THE FINITE-HORIZON ONE-ARMED-BANDIT PROBLEM
- On the Theory of Apportionment
Cited In (40)
- A minimax and asymptotically optimal algorithm for stochastic bandits
- Title not available (Why is that?)
- Learning the distribution with largest mean: two bandit frameworks
- Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models
- Bayesian adaptive bandit-based designs using the Gittins index for multi-armed trials with normally distributed endpoints
- Lower bounds of success probabilities for high-fidelity approach in KLM scheme
- Probabilistic learning constrained by realizations using a weak formulation of Fourier transform of probability measures
- The multi-armed bandit problem: an efficient nonparametric solution
- Learning to optimize via information-directed sampling
- Batched bandit problems
- Kullback-Leibler upper confidence bounds for optimal sequential allocation
- On Bayesian index policies for sequential resource allocation
- Adaptive policies for perimeter surveillance problems
- Satisficing in Time-Sensitive Bandit Learning
- Boundary crossing probabilities for general exponential families
- Scalar utility theory and proportional processing: what does it actually imply?
- Infomax strategies for an optimal balance between exploration and exploitation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Probabilistic learning inference of boundary value problem with uncertainties based on Kullback-Leibler divergence under implicit constraints
- Dealing with expert bias in collective decision-making
- A better resource allocation algorithm with semi-bandit feedback
- Asymptotically optimal multi-armed bandit policies under a cost constraint
- Finite-time analysis for the knowledge-gradient policy
- Boundary crossing for general exponential families
- A confirmation of a conjecture on Feldman’s two-armed bandit problem
- Normal bandits of unknown means and variances
- Explore first, exploit next: the true shape of regret in bandit problems
- Asymptotically optimal algorithms for budgeted multiple play bandits
- Local Dvoretzky-Kiefer-Wolfowitz confidence bands
- Tuning Bandit Algorithms in Stochastic Environments
- Infinite Arms Bandit: Optimality via Confidence Bounds
- Technical note -- A note on the equivalence of upper confidence bounds and Gittins indices for patient agents
- Learning to optimize via posterior sampling
- Title not available (Why is that?)
- Physics-constrained non-Gaussian probabilistic learning on manifolds
- Good arm identification via bandit feedback
- Title not available (Why is that?)
- A review of recent advances in empirical likelihood
- Regret bounds for Narendra-Shapiro bandit algorithms
Uses Software
This page was built for publication: Kullback-Leibler upper confidence bounds for optimal sequential allocation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q366995)
