A Gang of Bandits

By Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella. 2013

174 citations recorded by the source corpus.

Multi-armed bandit problems formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such as online advertisement and, more generally, recommendation systems. In many cases, however, these applications have a strong social component, whose integration in the bandit algorithm could lead to a dramatic performance increase. For instance, content may be served to a group of users by taking advantage of an underlying network of social relationships among them. In this paper, we introduce novel algorithmic approaches to the solution of such networked bandit problems. More specifically, we design and analyze a global recommendation strategy which allocates a bandit algorithm to each network node (user) and allows it to "share" signals (contexts and payoffs) with the neghboring nodes. We then derive two more scalable variants of this strategy based on different ways of clustering the graph nodes. We experimentally compare the algorithm and its variants to state-of-the-art methods for contextual bandits that do not use the relational information. Our experiments, carried out on synthetic and real-world datasets, show a consistent increase in prediction performance obtained by exploiting the network structure.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

DRN: A Deep Reinforcement Learning Framework for News Recommendation (2018, background): “Recently, some people try to combine bandit with clustering based collaborative filtering [14], and matrix factorization [6, 21, 32, 42, 43, 51], in order to model more complex user and item relationship, and utilize the social network relationship in determining the reward function.”
Factorization Bandits for Interactive Recommendation (2017, methodology): “Typical item-level contextual features include topic categories for news recommendation (Li et al. 2010; Agarwal and Chen 2009) and genre for music recommendation (Cesa-Bianchi, Gentile, and Zappella 2013).”
Reinforcement Learning in Rich-Observation MDPs using Spectral Methods (2016, methodology): “[7] and the state aggregation analysis of Ortner [21] and perform an additional step of Reward and Transition Clustering .”
Online Clustering of Bandits (2014, methodology): “Both competitors are members of the LinUCB family of algorithms (Auer, 2002; Chu et al., 2011; Li et al., 2010; Abbasi-Yadkori et al., 2011; Cesa-Bianchi et al., 2013).”
Learning Hidden Features for Contextual Bandits (2016, methodology): “In the second type [3, 7, 15, 10], which we are interested in this work, the learner is given a model that predicts the arms’ payoffs based on the given context vectors of arms.”
Multi-Task Learning for Contextual Bandits (2017, background): “Gang of bandits [5] uses a graph structure (e.”
Transferable Contextual Bandit for Cross-Domain Recommendation (2018, background): “FactorUCB (Cesa-Bianchi, Gentile, and Zappella 2013; Wang, Wu, and Wang 2017) assumes the reward function as the dot product between user latent factors and item latent factors.”