Unifying Clustered and Non-stationary Bandits

Abstract

Non-stationary bandits and online clustering of bandits lift the restrictive assumptions in contextual bandits and provide solutions to many important real-world scenarios. Though the essence in solving these two problems overlaps considerably, they have been studied independently. In this paper, we connect these two strands of bandit research under the notion of test of homogeneity, which seamlessly addresses change detection for non-stationary bandit and cluster identification for online clustering of bandit in a unified solution framework. Rigorous regret analysis and extensive empirical evaluations demonstrate the value of our proposed solution, especially its flexibility in handling various environment assumptions.

arXiv comment26 pages, 3 figures

References in corpus (6)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Online Clustering of Bandits
• Learning Contextual Bandits in a Non-stationary Environment
• Weighted Linear Bandits for Non-Stationary Environments
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits