A Gang of Bandits

Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella

Abstract

Multi-armed bandit problems are receiving a great deal of attention because they adequately formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such as online advertisement and 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. In this paper, we introduce novel algorithmic approaches to the solution of such networked bandit problems. More specifically, we design and analyze a global strategy which allocates a bandit algorithm to each network node (user) and allows it to "share" signals (contexts and payoffs) with the neighboring nodes. We then derive two more scalable variants of this strategy based on different ways of clustering the graph nodes. Our experiments, carried out on synthetic and real-world datasets, show a marked increase in prediction performance obtained by exploiting the network structure.

Introduction

In modern recommendation systems, the multi-armed bandit (MAB) framework serves as the primary mechanism for balancing exploration (testing new content to learn user preferences) and exploitation (recommending content with known high utility). While effective, traditional contextual bandit algorithms—such as LinUCB—typically treat users as independent entities. This approach ignores the "social" reality of modern web platforms: users are often connected via social networks, and these connections frequently imply shared interests.

This paper addresses the networked bandit problem, where the goal is to utilize an underlying social graph to share feedback and contexts between neighboring nodes. By assuming that "friends" have similar tastes, we can significantly accelerate the learning process for new or less active users, effectively reducing the cumulative regret of the system.

The GOB.Lin Framework

The authors introduce GOB.Lin (Gang of Bandits, Linear version), an algorithm that maintains a linear contextual bandit instance at every node in a graph. The core innovation lies in how these instances interact through two primary mechanisms:

  1. Laplacian Regularization: The algorithm assumes that the preference vectors of neighboring users in the graph are close to each other in Euclidean space. By using the Laplacian matrix of the graph as a regularizer, the learning process is constrained by the network structure, ensuring that updates to one user's model inform the models of their neighbors.
  2. Information Sharing: When a user interacts with an item and generates a payoff (e.g., a click), that signal is "spread" to neighboring nodes via a kernel defined by the graph structure. This allows the algorithm to update multiple user models simultaneously from a single interaction.

Addressing Scalability

Running a full network of bandits is computationally intensive, with a complexity of $O((dn)^2)$ per round, where $d$ is the feature dimension and $n$ is the number of nodes. To make this approach viable for larger networks, the authors propose two variants:

  • GOB.Lin.MACRO: This variant groups users into clusters, treating each cluster as a single "macro-node" within a simplified graph. This reduces the effective $n$ while preserving the broad social structure.
  • GOB.Lin.BLOCK: This approach deletes edges between clusters to create independent, smaller sub-graphs. This reduces noise and computational overhead by localizing the information sharing.

Experimental Evaluation

The researchers evaluated GOB.Lin against two standard baselines: LinUCB-IND (one independent model per user) and LinUCB-SIN (one single model shared by all users). Testing was conducted on three distinct datasets:

  • 4Cliques (Synthetic): A controlled environment with 100 nodes divided into four cliques, used to measure sensitivity to graph noise.
  • Last.fm: A dataset of 1,892 users and over 12,000 social edges, where payoffs were defined by music listening history.
  • Delicious: A social bookmarking dataset with 1,861 nodes, where payoffs were based on URL bookmarking.

Key Findings

  • Superior Performance: GOB.Lin and its variants consistently outperformed both the independent and pooled baselines in terms of cumulative reward. It successfully found the "middle ground" between ignoring individual differences and failing to share information.
  • Clustering as a Denoising Tool: Interestingly, the MACRO and BLOCK variants often performed better than the full GOB.Lin model. By grouping users, the algorithms became more robust to "noisy" social links—edges in the graph that do not actually represent shared interests.
  • Domain Sensitivity: The optimal strategy depended on the dataset. On Last.fm, where certain artists have broad appeal, the MACRO version excelled. On Delicious, where interests are highly niche, the BLOCK version’s localized personalization proved more effective.

Conclusion and Future Work

The GOB.Lin framework demonstrates that social network data is a powerful regularizer for contextual bandits. By moving beyond the assumption of user independence, recommendation engines can achieve higher accuracy with fewer interactions.

However, challenges remain regarding computational complexity on massive scales (millions of users) and the assumption of a static graph. Future research directions include the integration of feature hashing to improve scalability and the development of models that can adapt to evolving social structures over time.

Summary updated

Abstract

Multi-armed bandit problems are receiving a great deal of attention because they adequately 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, we may want to serve content 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 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 marked increase in prediction performance obtained by exploiting the network structure.
BibTeX
@inproceedings{cesabianchi2013gang,
  author = {Nicolò Cesa-Bianchi and Claudio Gentile and Giovanni Zappella},
  title = {{A Gang of Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=HJbP7ubdWB},
}
Figure