Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits

Emilie Kaufmann
Odalric-Ambrym Maillard
Julien Seznec
  • Fonction : Auteur
  • PersonId : 1084851

Résumé

We introduce GLR-klUCB, a novel algorithm for the piecewise iid non-stationary bandit problem with bounded rewards. This algorithm combines an efficient bandit algorithm, kl-UCB, with an efficient, parameter-free, changepoint detector, the Bernoulli Generalized Likelihood Ratio Test, for which we provide new theoretical guarantees of independent interest. Unlike previous non-stationary bandit algorithms using a change-point detector, GLR-klUCB does not need to be calibrated based on prior knowledge on the arms' means. We prove that this algorithm can attain a $O(\sqrt{TA \Upsilon_T\log(T)})$ regret in $T$ rounds on some ``easy'' instances, where A is the number of arms and $\Upsilon_T$ the number of change-points, without prior knowledge of $\Upsilon_T$. In contrast with recently proposed algorithms that are agnostic to $\Upsilon_T$, we perform a numerical study showing that GLR-klUCB is also very efficient in practice, beyond easy instances.

Domaines

Autres [stat.ML]
Fichier principal
Vignette du fichier
BKMS20.pdf (282.84 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02006471 , version 1 (04-02-2019)
hal-02006471 , version 2 (08-12-2020)
hal-02006471 , version 3 (01-08-2022)

Licence

Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales

Identifiants

Citer

Lilian Besson, Emilie Kaufmann, Odalric-Ambrym Maillard, Julien Seznec. Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits. 2020. ⟨hal-02006471v2⟩
603 Consultations
876 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More