On Context-Dependent Clustering of Bandits
This work addresses recommendation tasks by improving collaborative filtering with bandit algorithms, though it appears incremental as it builds on existing cluster-of-bandit methods.
The paper tackles the problem of collaborative recommendation by introducing a cluster-of-bandit algorithm (CAB) that shares feedback among users based on context-dependent neighborhoods, resulting in significantly increased prediction performance on production and real-world datasets.
We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating the neighborhood of users in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference as well as learning processes in a manner that seamlessly interleaving explore-exploit tradeoffs and collaborative steps. We prove regret bounds under various assumptions on the data, which exhibit a crisp dependence on the expected number of clusters over the users, a natural measure of the statistical difficulty of the learning task. Experiments on production and real-world datasets show that CAB offers significantly increased prediction performance against a representative pool of state-of-the-art methods.