Unifying Clustered and Non-stationary Bandits
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Change DetectionClusteringMulti-Armed BanditsOnline ClusteringSimilar Papers 제목 키워드 기반
A Definition of Non-Stationary Bandits
Despite the subject of non-stationary bandit learning having attracted much recent attention, we have yet to identify a formal definition of non-stationarity that can consistently distinguish non-stationary bandits from …
A unifying framework for generalised Bayesian online learning in non-stationary environments
We propose a unifying framework for methods that perform probabilistic online learning in non-stationary environments. We call the framework BONE, which stands for generalised (B)ayesian (O)nline learning in (N)on-statio…
Continual LearningMulti-Armed BanditsThompson Sampling for Bandits with Clustered Arms
We propose algorithms based on a multi-level Thompson sampling scheme, for the stochastic multi-armed bandit and its contextual variant with linear expected rewards, in the setting where arms are clustered. We show, both…
ClusteringThompson SamplingActive Search for High Recall: a Non-Stationary Extension of Thompson Sampling
We consider the problem of Active Search, where a maximum of relevant objects - ideally all relevant objects - should be retrieved with the minimum effort or minimum time. Typically, there are two main challenges to face…
Multi-Armed BanditsThompson SamplingCascading Non-Stationary Bandits: Online Learning to Rank in the Non-Stationary Cascade Model
Non-stationarity appears in many online applications such as web search and advertising. In this paper, we study the online learning to rank problem in a non-stationary environment where user preferences change abruptly …
Learning-To-Rank