A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences

Odalric-Ambrym Maillard · Rémi Munos · Gilles Stoltz

121 citations0/0 files storedarXiv (Cornell University)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Bandit Algorithms Research Reinforcement Learning in Robotics Optimization and Search Problems

Abstract

We consider a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit problem in the case of distributions with finite supports (not necessarily known beforehand), whose asymptotic regret matches the lower bound of \cite{Burnetas96}. Our contribution is to provide a finite-time analysis of this algorithm; we get bounds whose main terms are smaller than the ones of previously known algorithms with finite-time analyses (like UCB-type algorithms).

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 121 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem 1952Some aspects of the sequential design of experiments 2009Exploration–exploitation tradeoff using variance estimates in multi-armed bandits 2010UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem 1996Optimal Adaptive Policies for Sequential Allocation Problems 2010Regret Bounds and Minimax Policies under Partial Monitoring 2010An Asymptotically Optimal Bandit Algorithm for Bounded Support Models.

Cited by

2017Near-Optimal Regret Bounds for Thompson Sampling 2013Information Complexity in Bandit Subset Selection 2014Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits 2020Multi-Armed Bandits with Fairness Constraints for Distributing Resources to Human Teammates 2013Robust Risk-Averse Stochastic Multi-armed Bandits

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.