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

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

inria-00574987, version 2

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

Odalric-Ambrym Maillard () ¹, Rémi Munos ¹, Gilles Stoltz ^2, 3, 4

24th Annual Conference on Learning Theory : COLT'11 (2011) 18

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).

1: SEQUEL (INRIA Lille - Nord Europe)
INRIA – CNRS : UMR8146 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – Ecole Centrale de Lille
2: Département de Mathématiques et Applications (DMA)
CNRS : UMR8553 – Ecole normale supérieure de Paris - ENS Paris
3: Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH)
GROUPE HEC – CNRS : UMR2959
4: CLASSIC (INRIA Paris - Rocquencourt)
Ecole normale supérieure de Paris - ENS Paris – INRIA

inria-00574987, version 2
http://hal.inria.fr/inria-00574987
oai:hal.inria.fr:inria-00574987
From: Gilles Stoltz <>
Submitted on: Friday, 27 May 2011 22:44:43
Updated on: Tuesday, 14 June 2011 11:34:34

See detailed view

Associated documents

PDF :

PS :

arXiv: 1105.5820

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00574987"><analytic>
<author><persName><forename>Odalric-Ambrym</forename><surname>Maillard</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</orgName>
<orgName type="team">SEQUEL</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8146</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
<orgName type="institution">Ecole Centrale de Lille</orgName>
</affiliation>
</author>
<author><persName><forename>Rémi</forename><surname>Munos</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</orgName>
<orgName type="team">SEQUEL</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8146</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
<orgName type="institution">Ecole Centrale de Lille</orgName>
</affiliation>
</author>
<author><persName><forename>Gilles</forename><surname>Stoltz</surname></persName>
<affiliation>
<orgName type="laboratory">DMA</orgName>
<orgName type="team">Département de Mathématiques et Applications</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8553</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">GREGH</orgName>
<orgName type="team">Groupement de Recherche et d'Etudes en Gestion à HEC</orgName>
<country>FR</country>
<orgName type="institution">GROUPE HEC</orgName>
<orgName type="institution">CNRS : UMR2959</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Paris - Rocquencourt</orgName>
<orgName type="team">CLASSIC</orgName>
<country>FR</country>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<title type="main" level="a">A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences</title></analytic><monogr><meeting>24th Annual Conference on Learning Theory : COLT'11</meeting><imprint><pubPlace><settlement>Budapest</settlement><country>Hungary</country></pubPlace><biblScope type="publicationDate">2011-05-27</biblScope><biblScope type="pp">18</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00574987</idno><idno type="HALFile">http://hal.inria.fr/inria-00574987/PDF/66-Maillard-Munos-Stoltz.pdf</idno></biblStruct>
</listBibl>
</listBibl>

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

Associated documents

See also

Export