Graph Clustering Bandits for Recommendation

Bandits are becoming an essential tool in modern recommenders systems [9, 12]. Most recommendation setting involve an ever changing dynamic set of items, in many domains such as news and ads recommendation the item set is changing so rapidly that is impossible to use standard collaborative filtering techniques. In these settings bandit algorithms such as contextual bandits have been proven to work well [10] since they provide a principled way to gauge the appeal of the new items. Yet, one drawback of contextual bandits is that they mainly work in a content-dependent regime, the user and item content features determine the preference scores so that any collaborative effects (joint user preferences over groups of items) that arise are being ignored. Incorporating collaborative effects into bandit algorithms can lead to a dramatic increase in the quality of recommendations. In bandit algorithms this has been mainly done by clustering the user. For instance, we may want to serve content to a group of users by taking advantage of an underlying network of preference relationships among them. These preference relationships can either be explicitly encoded in a graph, where adjacent nodes/users are deemed similar to one another, or implicitly contained in the data, and given as the outcome of an inference process that recognizes similarities across users based on their past behavior. To deal with this issue a new type of bandit algorithms has been developed which work under the assumption that users can be grouped (or clustered) based on their selection of items e.g.