Source-linked AI summary
A Gang of Bandits
Nicolò Cesa-Bianchi, Claudio Gentile, Giovanni Zappella
TL;DR
The paper addresses contextual bandits for recommendation when users are connected by a social network. It develops a graph-sharing strategy and scalable clustering variants, and reports improved prediction performance over methods that ignore relational information. The approach’s node-level computation can nevertheless scale quadratically with the number of users.
Problem
Contextual recommendation requires balancing exploration and exploitation, while existing bandit methods do not incorporate the social relationships among users.
Method
The paper assigns a linear bandit to each network node, shares information through the graph, and derives clustering-based variants for scalability.
Results
The proposed methods outperform baselines that do not use graphical information on two real-world datasets, while graph structure can reduce the regret-bound determinant term for dense graphs.
Takeaways & Limitations
Exploiting social-network structure can improve recommendation prediction performance while clustering can reduce graph noise and running time.
Takeaways & Limitations
GOB.Lin has quadratic running-time and memory dependence on the number of nodes, limiting practical deployment without graph compression.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses contextual recommendation as an exploration–exploitation problem and incorporates social-network structure into bandit algorithms. It proposes clustering-based variants to improve prediction performance and reduce computation.
- Contextual recommendation must balance serving content matching users’ interests with exploring new content to improve the overall user experience.
- The paper introduces a global networked-bandit strategy that allocates a bandit algorithm to each user and shares contexts and payoffs with neighboring users.
- Two clustering-based variants reduce graph noise while making the strategy more scalable.One deletes edges between clusters; the other treats each cluster as a node in a smaller network.
- Experiments on synthetic data and Delicious and Last.fm show improved prediction performance from exploiting network structure.
2 Related work
Prior work recognizes social relationships as useful for recommendation, but this paper combines contextual bandits with social-graph information.
- Social relationships are established in recommender-system research as useful information for improving recommendation quality.
- LinUCB introduced linear contextual bandits for personalized content recommendation, while other studies examine metric, probabilistic, or payoff-sharing dependencies.
- The paper identifies its approach as the first work combining contextual bandits with social-graph information.
3 Learning model
The learning model presents users as nodes in a known connected social graph and assumes nearby users have similar reward parameters. At each round, the learner selects a context for a presented user, observes a noisy payoff, and seeks to minimize cumulative regret.
- Users are represented by nodes in a known undirected, connected graph, whose edges encode social links.
- At each round, the learner receives a user and candidate context vectors, selects one context, and observes its payoff.
- Each user has an unknown parameter vector, and rewards are noisy versions of linear functions of context vectors.
- The expected reward is linear in context, while bounded noise in [−1, 1] implies variance at most 4.
- The algorithm aims to bound cumulative regret for the observed sequence of users and context sets, with graph smoothness motivating Laplacian regularization.
- Nearby users are assumed to have similar parameter vectors, making rewards observed at one node informative about connected users.
4 Algorithm and regret analysis
The paper develops GOB.Lin by combining per-node linear bandits with graph-based information sharing, then analyzes its regret and scalability. Its regret bound reflects both similarity across adjacent nodes and graph-dependent reductions in the log-determinant term, while matrix inversion creates a quadratic dependence on the number of nodes.
- Algorithm: GOB.Lin runs a linear bandit at each graph node and updates non-observed nodes using reward information from the observed node.Because the assumed node parameters are close, updates are shared to keep prototype vectors similar over time.
- Algorithm: The algorithm represents graph structure with A = I_n + L and A⊗ = A ⊗ I_d, where L is the graph Laplacian.The Kronecker product couples node-specific parameter blocks through the graph.
- Algorithm: The selected context and observed payoff are spread across node blocks, making contextual information available to other nodes while retaining only the observed node’s reward signal.When the coupling matrix is the identity, the method reduces to independent linear bandits; graph coupling enables cross-node updates.
- Scalability: (dn)^2 time and memory per round make the number of nodes the main practical scaling limitation, motivating graph compression through node clustering.The paper reports that projecting contexts onto principal components reduced the practical impact of the dimension dependence, while node dependence remained significant.
- Regret analysis: The regret analysis combines a multitask kernel with a linear-bandit analysis under bounded context norms and graph-structured parameter similarity.The theorem assumes ||x_t,k|| ≤ B and includes the graph smoothness term Σ_(i,j)∈E ||u_i − u_j||^2.
- Regret analysis: In dense graphs, the GOB.Lin log-determinant term can be a factor n smaller than for n independent bandits, although its exact practical advantage depends on the data–graph interaction.The paper contrasts no-edge and complete-graph cases and characterizes the stated bounds through tr(M_T).
5 Experiments
The experiments compare GOB.Lin and clustering variants with graph-independent baselines on synthetic and real-world recommendation datasets. Results show robustness to payoff noise, sensitivity to graph noise, and improved performance from exploiting relational information.
- Datasets: The evaluation uses a synthetic 4Cliques dataset and the real-world Last.fm and Delicious recommendation datasets.Last.fm contains 1,892 users and 17,632 artists; Delicious contains 1,861 users and 69,226 URLs.
- Synthetic results: GOB.Lin is more robust to payoff noise than competitors but degrades as graph noise grows, especially at high graph-noise levels.The highest reported graph-noise condition perturbs 500 of 1,200 original edges, or 41.7%.
- Baselines and variants: GOB.Lin and its variants are compared with LinUCB-IND, which models users independently, and LinUCB-SIN, which shares one model across all users.The clustering variants use macro-level cluster networks or disconnected cluster components.
- Scalability: Clustering reduces computation quadratically with the number of nodes and can regularize the model by limiting graph-noise influence.GOB.Lin.MACRO uses cluster nodes, while GOB.Lin.BLOCK disconnects clusters; multiple cluster sizes were tested and the best-performing choice was reported.
- Real-world results: On both real-world datasets, GOB.Lin and its variants outperform graph-independent baselines; MACRO performs best on Last.fm, while BLOCK performs best on Delicious.The dataset-specific pattern reflects shared popular artists on Last.fm and more user-dependent website preferences on Delicious.
A Appendix
The appendix proves the cumulative-regret theorem by decomposing instantaneous regret and applying concentration and matrix-based bounds. The resulting inequalities hold uniformly over time with probability at least 1 − δ.
- Proof strategy: The appendix provides the proof of Theorem 1.The proof establishes the paper’s cumulative-regret guarantee.
- Proof strategy: Instantaneous regret is decomposed into terms that are bounded using the algorithm’s confidence quantities and contextual assumptions.The derivation introduces fixed-time shorthand before applying the decomposition.
- Probability guarantee: A prior theorem is invoked with λ = 1 to obtain bounds that hold simultaneously for all time steps with probability at least 1 − δ.The uniform event is then used to control cumulative regret.
- Final bound: The cumulative regret bound follows after combining the inequalities and applying (a + b)^2 ≤ 2a^2 + 2b^2.The appendix concludes that the resulting expression gives the desired bound.