# When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution

arXiv: https://arxiv.org/abs/2104.07150 · HTML: https://mlsanity.com/paper/2104.07150/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 14 Apr 2021.

## Builds on (most cited first, 15 of 15)

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Empirical Analysis of Predictive Algorithms for Collaborative Filtering](https://mlsanity.com/paper/1301.7363/) (2013)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [Learning Contextual Bandits in a Non-stationary Environment](https://mlsanity.com/paper/1805.09365/) (2018)
- [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](https://mlsanity.com/paper/1907.05632/) (2019)
- [Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection](https://mlsanity.com/paper/1302.3721/) (2013)
- [Graph Clustering Bandits for Recommendation](https://mlsanity.com/paper/1605.00596/) (2016)

## Abstract (arXiv)

Collaborative bandit learning, i.e., bandit algorithms that utilize collaborative filtering techniques to improve sample efficiency in online interactive recommendation, has attracted much research attention as it enjoys the best of both worlds. However, all existing collaborative bandit learning solutions impose a stationary assumption about the environment, i.e., both user preferences and the dependency among users are assumed static over time. Unfortunately, this assumption hardly holds in practice due to users' ever-changing interests and dependence relations, which inevitably costs a recommender system sub-optimal performance in practice. In this work, we develop a collaborative dynamic bandit solution to handle a changing environment for recommendation. We explicitly model the underlying changes in both user preferences and their dependency relation as a stochastic process. Individual user's preference is modeled by a mixture of globally shared contextual bandit models with a Dirichlet Process prior. Collaboration among users is thus achieved via Bayesian inference over the global bandit models. Model selection and arm selection for each user are done via Thompson sampling to balance exploitation and exploration. Our solution is proved to maintain a standard tilde O(√T) sublinear regret even in such a challenging environment. And extensive empirical evaluations on both synthetic and real-world datasets further confirmed the necessity of modeling a changing environment and our algorithm's practical advantages against several state-of-the-art online learning solutions.