Bounded regret in stochastic multi-armed bandits

Sébastien Bubeck; Vianney Perchet; Philippe Rigollet

Bounded regret in stochastic multi-armed bandits

Sébastien Bubeck
, Vianney Perchet
, Philippe Rigollet

Princeton University
Laboratoire de Probabilités et Modèles Aléatoires

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

Résumé

We study the stochastic multi-armed bandit problem when one knows the value μ^(*) of an optimal arm, as a well as a positive lower bound on the smallest positive gap Δ. We propose a new randomized policy that attains a regret uniformly bounded over time in this setting. We also prove several lower bounds, which show in particular that bounded regret is not possible if one only knows Δ, and bounded regret of order 1/Δ is not possible if one only knows μ^(*).

langue originale	Anglais
Pages (de - à)	122-134
Nombre de pages	13
journal	Journal of Machine Learning Research
Volume	30
état	Publié - 1 janv. 2013
Modification externe	Oui
Evénement	26th Conference on Learning Theory, COLT 2013 - Princeton, NJ, États-Unis Durée: 12 juin 2013 → 14 juin 2013

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@article{4200b476db8c49afb8de48eadf0a868d,

title = "Bounded regret in stochastic multi-armed bandits",

abstract = "We study the stochastic multi-armed bandit problem when one knows the value μ(*) of an optimal arm, as a well as a positive lower bound on the smallest positive gap Δ. We propose a new randomized policy that attains a regret uniformly bounded over time in this setting. We also prove several lower bounds, which show in particular that bounded regret is not possible if one only knows Δ, and bounded regret of order 1/Δ is not possible if one only knows μ(*).",

author = "S{\'e}bastien Bubeck and Vianney Perchet and Philippe Rigollet",

year = "2013",

month = jan,

day = "1",

language = "English",

volume = "30",

pages = "122--134",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

note = "26th Conference on Learning Theory, COLT 2013 ; Conference date: 12-06-2013 Through 14-06-2013",

}

TY - JOUR

T1 - Bounded regret in stochastic multi-armed bandits

AU - Bubeck, Sébastien

AU - Perchet, Vianney

AU - Rigollet, Philippe

PY - 2013/1/1

Y1 - 2013/1/1

N2 - We study the stochastic multi-armed bandit problem when one knows the value μ(*) of an optimal arm, as a well as a positive lower bound on the smallest positive gap Δ. We propose a new randomized policy that attains a regret uniformly bounded over time in this setting. We also prove several lower bounds, which show in particular that bounded regret is not possible if one only knows Δ, and bounded regret of order 1/Δ is not possible if one only knows μ(*).

AB - We study the stochastic multi-armed bandit problem when one knows the value μ(*) of an optimal arm, as a well as a positive lower bound on the smallest positive gap Δ. We propose a new randomized policy that attains a regret uniformly bounded over time in this setting. We also prove several lower bounds, which show in particular that bounded regret is not possible if one only knows Δ, and bounded regret of order 1/Δ is not possible if one only knows μ(*).

UR - https://www.scopus.com/pages/publications/84898021400

M3 - Conference article

AN - SCOPUS:84898021400

SN - 1532-4435

VL - 30

SP - 122

EP - 134

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

T2 - 26th Conference on Learning Theory, COLT 2013

Y2 - 12 June 2013 through 14 June 2013

ER -

Bounded regret in stochastic multi-armed bandits

Résumé

Autres fichiers et liens

Empreinte digitale

Contient cette citation