# The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits

3 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We propose a new algorithm for the piece-wise i.i.d. non-stationary bandit problem with bounded rewards. Our proposal, GLR-klUCB, combines an efficient bandit algorithm, klUCB, with an efficient, parameter-free, change-point detector, the Bernoulli Generalized Likelihood Ratio Test, for which we provide new theoretical guarantees of independent interest. We analyze two variants of our strategy, based on local restarts and global restarts, and show that their regret is upper-bounded by $O(\Upsilon_T \sqrt{T \log(T)})$ if the number of change-points $Υ_T$ is unknown, and by $O(\sqrt{\Upsilon_T T \log(T)})$ if $\Upsilon_T$ is known. This improves the current state-of-the-art bounds, as our algorithm needs no tuning based on knowledge of the problem complexity other than $Υ_T$. We present numerical experiments showing that GLR-klUCB outperforms passively and actively adaptive algorithms from the literature, and highlight the benefit of using local restarts.
Keywords :
Document type :
Preprints, Working Papers, ...
Domain :

https://hal.inria.fr/hal-02006471
Contributor : Lilian Besson <>
Submitted on : Monday, February 4, 2019 - 4:08:13 PM
Last modification on : Saturday, January 25, 2020 - 1:23:41 AM
Long-term archiving on: Sunday, May 5, 2019 - 4:41:23 PM

### Files

The-Generalized-Likelihood-Rat...
Files produced by the author(s)

### Identifiers

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

### Citation

Lilian Besson, Emilie Kaufmann. The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits. 2019. ⟨hal-02006471⟩

Record views