Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits

Lilian Besson 1 Emilie Kaufmann 2 Odalric-Ambrym Maillard 2 Julien Seznec 2, 3
1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE, Inria Rennes – Bretagne Atlantique
2 Scool - Scool
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.inria.fr/hal-02006471
Contributor : Emilie Kaufmann Connect in order to contact the contributor
Submitted on : Tuesday, December 8, 2020 - 9:26:26 AM
Last modification on : Friday, January 21, 2022 - 3:09:33 AM

Files

BKMS20.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - ShareAlike 4.0 International License

Identifiers

  • HAL Id : hal-02006471, version 2
  • ARXIV : 1902.01575

Citation

Lilian Besson, Emilie Kaufmann, Odalric-Ambrym Maillard, Julien Seznec. Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits. 2020. ⟨hal-02006471v2⟩

Share

Metrics

Les métriques sont temporairement indisponibles