HTTPS SSH

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

This repository contains the LaTeX code of a research article written by Lilian Besson and Emilie Kaufmann, entitled "The Generalized Likelihood Ratio Test meets klUCB: an Improved Algorithm for Piece-Wise Non-Stationary Bandits".

We are working on this article.

Published Maintenance Ask Me Anything !

I (Lilian Besson) have started my PhD in October 2016, and this is a part of my on going research in 2019.


Abstract

In this paper, we propose a new algorithm for the piece-wise i.i.d. non-stationary bandit problem, when the rewards are bounded. Our proposal, GLRklUCB, combines an efficient bandit algorithm, kl-UCB, 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 their regret is upper-bounded by $O(U_T sqrt(T \log(T)))$ if the number of change-points $U_T$ is unknown, and $O(sqrt(U_T T log(T))$ if $U_T$ is known. We present extensive numerical experiments showing that GLRklUCB outperforms all the passive and adaptive algorithms from the literature, and highlight the benefit of local restarts.


📜 License ? GitHub license

MIT Licensed (file LICENSE).

© 2019 Lilian Besson and Emilie Kaufmann.

Maintenance Ask Me Anything ! Analytics ForTheBadge uses-badges ForTheBadge uses-git

forthebadge made-with-overleaf forthebadge made-with-latex ForTheBadge built-with-science