2019/02/05 by Lilian Besson, Besson, Lilian, Emilie Kaufmann +3 · 4 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1902.01575
openalex publication_date 2019/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(√(TA ΥTlog(T))) regret in T rounds on some "easy" instances, where A is the number of arms and ΥT the number of change-points, without prior knowledge of ΥT. In contrast with recently proposed algorithms that are agnostic to ΥT, we perform a numerical study showing that GLR-klUCB is also very efficient in practice, beyond easy instances.