Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits

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{{\rm Y}}_T\log (T)})$ regret in $T$ rounds on some "easy" instances, where A is the number of arms and ${{\rm Y}}_T$ the number of change-points, without prior knowledge of ${{\rm Y}}_T$. In contrast with recently proposed algorithms that are agnostic to ${{\rm Y}}_T$, we perform a numerical study showing that GLR-klUCB is also very efficient in practice, beyond easy instances.

References in corpus (6)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Analysis of Thompson Sampling for the multi-armed bandit problem
• The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
• Multi-armed Bandits with Application to 5G Small Cells
• Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection
• KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints

Cited by in corpus (11)

• An empirical evaluation of active inference in multi-armed bandits
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Algorithms for Non-Stationary Generalized Linear Bandits
• Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret
• A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• A survey on multi-player bandits
• Weighted Gaussian Process Bandits for Non-stationary Environments
• Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
• Unifying Clustered and Non-stationary Bandits