Kullback-Leibler upper confidence bounds for optimal sequential allocation

DOI10.1214/13-AOS1119zbMath1293.62161arXiv1210.1136OpenAlexW3100329718MaRDI QIDQ366995

Rémi Munos, Odalric-Ambrym Maillard, Olivier Cappé, Gilles Stoltz, Aurélien Garivier

Publication date: 25 September 2013

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.1136

zbMATH Keywords

Kullback-Leibler divergencemulti-armed bandit problemssequential testingupper confidence bound

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Sequential statistical analysis (62L10) Sequential estimation (62L12)

Related Items (33)

Bayesian adaptive bandit-based designs using the Gittins index for multi-armed trials with normally distributed endpoints ⋮ Batched bandit problems ⋮ Scalar utility theory and proportional processing: what does it actually imply? ⋮ Probabilistic learning inference of boundary value problem with uncertainties based on Kullback-Leibler divergence under implicit constraints ⋮ Infomax strategies for an optimal balance between exploration and exploitation ⋮ Kullback-Leibler upper confidence bounds for optimal sequential allocation ⋮ Regret bounds for Narendra-Shapiro bandit algorithms ⋮ The multi-armed bandit problem: an efficient nonparametric solution ⋮ Local Dvoretzky-Kiefer-Wolfowitz confidence bands ⋮ Dealing with expert bias in collective decision-making ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Good arm identification via bandit feedback ⋮ ASYMPTOTICALLY OPTIMAL MULTI-ARMED BANDIT POLICIES UNDER A COST CONSTRAINT ⋮ Probabilistic learning constrained by realizations using a weak formulation of Fourier transform of probability measures ⋮ A confirmation of a conjecture on Feldman’s two-armed bandit problem ⋮ Learning the distribution with largest mean: two bandit frameworks ⋮ Finite-Time Analysis for the Knowledge-Gradient Policy ⋮ Unnamed Item ⋮ On Bayesian index policies for sequential resource allocation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Infinite Arms Bandit: Optimality via Confidence Bounds ⋮ Boundary crossing probabilities for general exponential families ⋮ Adaptive policies for perimeter surveillance problems ⋮ Learning to Optimize via Information-Directed Sampling ⋮ Explore First, Exploit Next: The True Shape of Regret in Bandit Problems ⋮ Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models ⋮ Technical Note—A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents ⋮ Learning to Optimize via Posterior Sampling ⋮ Asymptotically optimal algorithms for budgeted multiple play bandits ⋮ Satisficing in Time-Sensitive Bandit Learning

Uses Software

• py/maBandits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• An asymptotically optimal policy for finite support models in the multiarmed bandit problem
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Exploration-exploitation tradeoff using variance estimates in multi-armed bandits
• Asymptotically efficient adaptive allocation rules
• On the Gittins index for multiarmed bandits
• Optimal adaptive policies for sequential allocation problems
• Multi‐Armed Bandit Allocation Indices
• Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis
• Graphical Models, Exponential Families, and Variational Inference
• Optimal stopping and dynamic allocation
• Asymptotic Statistics
• Optimal Adaptive Policies for Markov Decision Processes
• On the Theory of Apportionment
• ASYMPTOTIC BAYES ANALYSIS FOR THE FINITE-HORIZON ONE-ARMED-BANDIT PROBLEM
• Sample mean based index policies by O(log n) regret for the multi-armed bandit problem
• Probability Inequalities for Sums of Bounded Random Variables
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Some aspects of the sequential design of experiments
• Sequential Tests of Statistical Hypotheses
• Finite-time analysis of the multiarmed bandit problem

This page was built for publication: Kullback-Leibler upper confidence bounds for optimal sequential allocation