Source-linked AI summary
Online Clustering of Bandits
Claudio Gentile, Shuai Li, Giovanni Zappella
TL;DR
Personalized recommendation must balance exploiting known user preferences with exploring changing content, while user similarities may be unknown and clustered. The paper introduces adaptive clustering for bandit strategies, analyzes its regret and scalability, and reports improved prediction performance across synthetic and real-world datasets. It also identifies limitations associated with an alternative graph-initialization strategy and an additional regret-bound factor.
Problem
Recommendation systems face an exploration-exploitation dilemma, while user behavior may form unknown clusters that must be inferred online.
Method
CLUB maintains individual user estimates and a graph whose connected components adaptively represent current user clusters for sharing feedback.
Results
The paper provides a regret analysis in a standard stochastic setting, efficient implementation using random-graph data structures, and often significant prediction gains over state-of-the-art bandit methods.
Takeaways & Limitations
Adaptive clustering can interpolate between one shared bandit and fully personalized bandits while leveraging cluster geometry and sizes.
Takeaways & Limitations
An alternative empty-graph variant requires prior knowledge of the separation parameter γ, while an extra regret-bound factor can be removed only at the cost of losing geometric dependence.
Abstract
from arXiv · showhide
We introduce a novel algorithmic approach to content recommendation based on adaptive clustering of exploration-exploitation ("bandit") strategies. We provide a sharp regret analysis of this algorithm in a standard stochastic noise setting, demonstrate its scalability properties, and prove its effectiveness on a number of artificial and real-world datasets. Our experiments show a significant increase in prediction performance over state-of-the-art methods for bandit problems.
1. Introduction
Online recommendation services must continually adapt to changing content and user preferences while balancing exploitation of appealing content against exploration of new options. Existing explicit- and implicit-network approaches face practical limitations involving unreliable or unavailable social information and scalability.
- Personalized recommendation repeatedly learns mappings between users and content from user and content context features.
- The need to recommend interesting content while exploring new content creates the exploration-exploitation dilemma formalized by multi-armed bandits.
- Social-network adoption creates recommendation opportunities because users with strong ties are more likely to exhibit similar behavior.
- Explicit-network methods can rely on misleading or unavailable social information, and feedback sharing can create severe scaling issues for many users.
- The proposed approach provides regret analysis, scalability through random-graph data structures, and improved prediction performance on synthetic and real-world datasets.
2. Learning Model
The learning model assumes users form unknown behaviorally similar clusters, with contexts and payoffs arriving sequentially under stochastic linear assumptions. The analysis compares adaptive clustering with cluster-aware and signal-sharing alternatives while accounting for cluster sizes and geometry.
- Users are partitioned into m << n unknown clusters whose members share behavior, while different clusters have different behavior.
- At each round, a uniformly sampled user receives an adaptively generated context set, the learner recommends one context, and observes its payoff.
- Expected payoff is linear in the selected context, with conditionally zero-mean bounded-variance noise; bounded noise in [−1, 1] implies σ2 ≤1.
- The reference analysis treats the m known clusters as independent contextual bandits and exploits the random user process to refine cluster-dependent regret terms.
- Regret depends on cluster sizes, with balanced clusters giving a worst case and one large cluster with many singleton clusters representing an easier case.
- The geometric parameter SD(uj) sums distances from a cluster vector to all cluster vectors and can motivate signal sharing when these distances are small.
- The intended analysis combines cluster geometry and relative cluster sizes without prior knowledge of m or γ and without excessive computational burden.
3. The Algorithm
CLUB adaptively estimates user clusters while sharing contextual-bandit feedback within current connected components. It combines per-user estimates, cluster-level aggregate estimates, confidence-based edge pruning, and scalable graph maintenance under a high-probability regret analysis.
- Algorithm structure: CLUB maintains per-user least-squares estimates and an undirected graph whose connected components represent the current user clusters.The graph starts connected, and edges are progressively erased as user-vector estimates evolve.
- Algorithm structure: At each round, CLUB selects an item using an aggregate least-squares estimator formed by collapsing users in the served node’s current cluster.The aggregate estimator is computed from prior contexts and is updated after the observed payoff.
- Adaptive clustering: Edges are deleted when estimated user-vector distances exceed the corresponding confidence thresholds, allowing current clusters to separate as evidence accumulates.The resulting graph and its connected components define the next round’s cluster structure.
- Scalability: The implementation stores individual and aggregate estimators alongside a decremental dynamic-connectivity structure, targeting large n, small d, and very small m.For sufficiently large T relative to n and d, the stated average running time per round is O(d^2 + d · poly(log n)), with memory O(n d^2 + |E1|).
- Regret analysis: The theoretical analysis uses high-probability linear-bandit confidence bounds and establishes regret for a complete initial graph under separated cluster vectors and specified context-generation conditions.The analysis also states that the theorem extends to sufficiently large clusters initialized with a sparser random graph, reducing computational burden.
- Regret analysis: The regret bound reflects cluster geometry and sizes, while comparison with the known-cluster reference incurs an extra √m factor; a related edge-adding variant instead requires prior γ and may depend on √n.The clustering term is smaller when a few large clusters contain most users and their vectors are close, while its inverse γ^2 dependence may be an analysis artifact.
4. Experiments
The experiments evaluate CLUB on synthetic, LastFM, Delicious, and Yahoo datasets against standard bandit baselines using regret ratios or clickthrough rate. CLUB generally performs well when the best degree of sharing is unclear, but its advantage varies across datasets.
- Experimental setup: CLUB is evaluated against LinUCB-ONE and LinUCB-IND on synthetic and real-world recommendation datasets.The study also includes RAN on regret-ratio plots and informed competitors on synthetic data.
- Datasets: Synthetic experiments vary the number of clusters, payoff noise, and cluster-size balancedness.Cluster sizes are generated with z = 0 for equal sizes and increasing z for greater imbalance.
- Datasets: Yahoo uses 8,362,905 records from 713,862 users and 323 news items, with binary click or no-click payoffs.The evaluation uses extracted “5k users” and “18k users” datasets after filtering and record-retention preprocessing.
- Evaluation metrics: Regret-ratio plots use cumulative regret relative to RAN, while Yahoo plots use clickthrough rate over retained records.Lower regret ratios are better, whereas CTR is the fraction of payoff-one outcomes among retained records.
- Results: CLUB outperforms both main competitors on synthetic and LastFM experiments, is outperformed by LinUCB-IND on Delicious, and tends to outperform competitors on Yahoo.The reported pattern suggests CLUB benefits when adaptive interpolation between shared and independent models is useful.
A. Appendix
The appendix supplies omitted proofs, technical details, related-work discussion, and additional experimental results.
- Appendix contents: The supplementary material contains proofs and technical details omitted from the main text.It also includes ancillary comments and discussion about related work.
- Appendix contents: The appendix provides extra experimental results beyond those reported in the main text.
A.1. Proof of Theorem 1
The proof establishes concentration and confidence properties for user and cluster estimates under stochastic context assumptions, then uses them to justify adaptive cluster separation and aggregate estimation. It combines martingale concentration, linear-bandit confidence bounds, and graph-based cluster arguments to support the regret theorem.
- Confidence bounds: The algorithm’s confidence bounds decrease with the number of observations accumulated by a user or cluster.The proof separately tracks node-level and aggregate cluster-level quantities.
- Assumptions: The proof assumes i.i.d. conditional contexts with unit norm, full-rank covariance, and sub-Gaussian projected squared contexts.The covariance minimum eigenvalue is required to be positive, and an alternative variance condition can replace sub-Gaussianity.
- Concentration bounds: Martingale and matrix concentration arguments establish high-probability bounds uniformly over users, rounds, and unit context directions.The proof invokes Freedman-like matrix martingale inequalities and conditional probability bounds.
- Cluster identification: When confidence radii are sufficiently small, edges between well-separated users are likely to be deleted, while deleted edges are likely to join users from different true clusters.This yields that the maintained graph contains the true edge structure with high probability and that current clusters are unions of true clusters.
- Aggregate estimation: Aggregate cluster estimates are analyzed by extending linear-bandit confidence arguments over possible unions of true clusters.The proof bounds the number of such unions by 2^m and applies a martingale result to the aggregated observations.
- Conclusion: The proof concludes by combining the preceding lemmas into the proof of Theorem 1.Some intermediate properties are stated without full derivations, with one proof explicitly omitted as routine calculation.
A.2. Implementation
The implementation stores per-user and per-cluster estimators alongside dynamic connectivity structures, achieving near-linear scalability when the initial graph is sparse. Synthetic plots compare regret ratios across noise levels and cluster counts for balanced and unbalanced clusters.
- Implementation: CLUB stores least-squares estimators for users and current clusters, plus decremental dynamic connectivity to maintain adaptive clusters.The implementation also maintains cluster indices and updates aggregate estimators when clusters split.
- Implementation: O(d^2 + d · poly(log n)) average running time per round applies when T is large compared with n and d.This follows from the stated n · poly(log n) total-time behavior when |E1| has the same scaling.
- Implementation: O(n d^2 + |E1|) memory is required when the number of current clusters never exceeds m.The stored structures include two d × d matrices and one d-dimensional vector per node, with analogous aggregate structures per cluster.
- Synthetic results: Figure 6 varies payoff noise from 0.1 to 0.3 and the number of clusters from 2 to 10 under balanced cluster sizes.Each plot reports an algorithm’s current cumulative regret divided by RAN’s current cumulative regret.
- Synthetic results: Figure 7 repeats the Figure 6 comparison for unbalanced cluster sizes with z = 2.The caption states that the remaining experimental layout is unchanged from Figure 6.
A.3. Further Plots
This section provides additional comparative plots for the synthetic datasets described in the main text, specifically Figures 6 and 7.
- Further plots: The supplementary section contains a more thorough set of comparative plots on the synthetic datasets.It directs the reader to Figures 6 and 7.
- Further plots: Figures 6 and 7 are the referenced visualizations for the additional synthetic-dataset comparisons.
- Further plots: The section adds plots rather than introducing a separate experimental dataset or analysis.
A.4. Derivation of the Reference Bounds
The reference-bound derivation begins from a single-user LINUCB bound and extends it to an oracle algorithm that knows the true clusters. Uniform user sampling supplies the expected cluster participation used in the extension.
- Reference bounds: The derivation starts from the single-user LINUCB bound for either the ONE or IND variant.The user profile vector is denoted u_j ∈ R^d.
- Reference bounds: The clairvoyant algorithm’s bound is obtained by summing regret contributed by each true cluster over the rounds assigned to that cluster.It runs one LINUCB instance per known cluster and uses T_j,T to denote the corresponding rounds.
- Reference bounds: E[T_j,T] = T |V_j| / n because the selected user is uniform over V.The resulting high-probability expression is identified as Equation (1) in the main text.
A.5. Further Comments
The further comments describe a data-dependent CLUB variant for fixed or adaptively generated contexts under a clusterability restriction. Its regret bound is similar to the reference bound but has worse dependence on user-model geometry.
- Further comments: A data-dependent CLUB variant can use clusterability assumptions tied to the set of context vectors.These assumptions support analysis in a fixed-design setting for the context sequence.
- Further comments: The adversary must keep distinct users’ context projections either zero or bounded away from zero by γ.The restriction applies to unit-norm context vectors generated possibly adaptively.
- Further comments: The modified algorithm achieves a cumulative regret bound similar to the reference bound, with worse dependence on the geometry of the user vectors.The analysis follows the same lines as Theorem 1.
A.6. Related Work
Related work studies transfer learning, clustering of Markov Decision Processes, clustered bandits, and low-rank user representations, while using different settings or algorithmic solutions from this paper.
- Transfer learning places a prior distribution over possible models in a stochastic multiarmed bandit setting.
- Brunskill and Li cluster Markov Decision Processes according to model-parameter similarity.
- Maillard and Mannor study noncontextual stochastic bandits with unknown clusters of model parameters, but use algorithmic solutions completely different from this paper.
- Djolonga et al. learn a low-rank subspace from context-defined users under a low-rank variation assumption across users.
A.7. Ongoing Research
The work identifies extensions involving softer or overlapping clusters, alternative graph-clustering methods, additional side information, cold-start users, and weaker statistical assumptions.
- Softer clustering may require prior knowledge of a distance threshold or the number of underlying clusters, both unknown here.
- Partially overlapping clusters and off-the-shelf graph-clustering techniques are proposed extensions, but CLUB is not analyzed with alternative clustering methods.
- Additional must-link and cannot-link constraints are identified as practically important side information.
- A node-duplication strategy could address cold-start users, but no experimental evidence has yet been collected on its effectiveness.
- The authors are investigating whether the i.i.d. and other statistical assumptions in Theorem 1 can be removed.