Source-linked AI summary
Spectral bandits
Tomáš Kocák, Rémi Munos, Branislav Kveton, Shipra Agrawal, Michal Valko
TL;DR
The paper asks how to learn high-payoff arms when rewards are smooth over a large graph and interaction budgets are much smaller than the number of nodes. It models rewards spectrally and introduces three algorithms whose regret depends on an effective dimension; experiments show that smoothness can support preference estimation for many items from few node evaluations.
Problem
The problem is to recommend high-payoff graph nodes when the number of nodes is large, the interaction budget is limited, and standard linear-bandit regret scales with ambient dimension D.
Method
The paper represents graph-smooth rewards in the graph-Laplacian eigenbasis and proposes SpectralUCB, SpectralTS, and SpectralEliminator.
Results
The three spectral algorithms have regret bounds that scale with the effective dimension d, typically much smaller than D for real-world graphs, and outperform linear counterparts when rewards are graph-smooth.
Takeaways & Limitations
Spectral structure can be leveraged for graph-based online learning, including recommendation, without regret scaling directly with the full number of nodes or features.
Takeaways & Limitations
Standard linear-bandit approaches remain unsuitable when the ambient dimension D is very large because their regret can scale linearly or as a square root of D.
Abstract
from arXiv · showhide
Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this work, we study a bandit problem where the payoffs of arms are smooth on a graph. This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation. In this problem, each item we can recommend is a node of an undirected graph and its expected rating is similar to the one of its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret with respect to the optimal policy would not scale poorly with the number of nodes. In particular, we introduce the notion of an effective dimension, which is small in real-world graphs, and propose three algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of node evaluations.
1. Introduction
The paper studies bandits whose expected payoffs are smooth over a known graph, motivated by applications such as targeted advertising and content recommendation. It addresses settings with far fewer interaction rounds than graph nodes and seeks regret that depends on an effective dimension rather than the full problem size.
- Motivation: Smooth graph functions assign similar values to neighboring nodes and can be represented using graph-Laplacian eigenvectors with small eigenvalues.The paper casts learning such functions as regression on Laplacian eigenvectors and brings the concept to bandits.
- Motivation: Graph structure supports applications such as targeted advertising, where neighboring users tend to have similar preferences.The learner seeks a smooth preference function over a social network.
- Motivation: Content-based recommendation models items as graph nodes whose similarity suggests that users prefer similar items similarly.Nearest-neighbor graphs can encode item similarity for recommendation.
- Problem: When T ≪ N, the learner cannot afford to sample every node once before making useful recommendations.Each round selects a node, observes its payoff, and updates the model.
- Problem: Unknown or large spectral dimension k requires regularization so regret does not scale with the number of nodes N.The paper seeks regret independent of N when the number of relevant features may approach N.
- Contributions: The work improves the effective-dimension definition, provides a matching lower bound, improves two regret bounds, and evaluates the methods on artificial, MovieLens, and Flixster data.These contributions extend earlier conference versions of the work.
2. Setting
The spectral bandit setting represents node rewards in the graph-Laplacian eigenbasis and assumes smoothness through smaller coefficients on higher-index eigenvectors. Its algorithms target regret governed by graph-dependent effective dimension rather than the ambient dimension.
- Graph representation: The graph Laplacian is formed as L = D − W from the symmetric similarity matrix W and diagonal degree matrix D.Its eigenvalues and eigenvectors are ordered through an eigendecomposition of L.
- Reward model: The reward function is represented as a linear combination of the graph-Laplacian eigenvectors.The feature vector for each node is a row of the eigenvector matrix Q.
- Smoothness assumption: Large coefficients on low-eigenvalue eigenvectors produce smooth graph functions, while higher-index coefficients are assumed to be small.The model avoids requiring an exactly sparse expansion in a known number k of eigenvectors.
- Interaction model: At each round, the recommender chooses a node and receives a noisy reward under conditionally independent zero-mean R-sub-Gaussian noise.Node feature vectors satisfy ||x_v||_2 ≤ 1, and the goal is minimizing cumulative regret against the best node.
- Scaling objective: The setting has K = N arms and D = N-dimensional eigenvector features, so regret scaling with N or D is unacceptable for large graphs.The algorithms and analyses also apply to any finite number of arms K.
3. Related work
Related work connects spectral bandits to linear, similarity-based, graph-structured, side-observation, and alternative-objective bandits. The paper distinguishes its setting through known graph similarity, smooth rewards, and regret goals tied to spectral structure.
- Linear and contextual bandits: Standard linear bandits provide relevant baselines, but their regret can scale with the ambient dimension D, which may be very large.The cited line of work includes SupLinRel, SupLinUCB, OFUL, and LinUCB.
- Open direction: Adversarial linear-bandit extensions leave open whether regret can scale better than D in the spectral setting.The cited work considers time-dependent reward functions.
- Similarity-based bandits: Similarity-based bandits assume Lipschitz or broader context relations, but their regret bounds scale worse with the relevant dimensions than the spectral setting described here.Gaussian-process and RKHS-norm approaches are also more general than this setting.
- Graph bandits: Gang-of-bandits methods smooth node-specific weight vectors, whereas the present setting models a shared graph-smooth reward structure.This distinction concerns what quantity is assumed smooth on the graph.
- Graph bandits: CLUB constructs a graph iteratively and benefits from a small number of clusters, while spectral algorithms can exploit similarity structure even when clusters nearly match the number of actions.The comparison also highlights that the present setting assumes the similarity graph is known.
- Other graph bandits: Unimodal and networked bandits impose specialized graph reward or neighborhood-observation structures that differ from spectral smoothness.Networked bandits add rewards from the selected node and its neighborhood.
- Side observations: Bandits with side observations reveal rewards from neighboring actions in addition to the selected action, unlike the feedback setting described for spectral bandits.The cited literature covers both stochastic and adversarial variants.
- Alternative objectives: Follow-up spectral-bandit work also studies sensing costs, cheap averages of node rewards, and graph classification with bandit feedback.Some related analyses require knowing the number of relevant eigenvectors d.
4. Spectral bandits
Spectral bandits exploit graph smoothness by regularizing rewards in the graph-Laplacian eigenbasis and measuring complexity with an effective dimension d. The paper shows that d can be substantially smaller than the ambient dimension and supports matching lower-bound analysis.
- Graph smoothness: Graph smoothness lets the reward vector be represented in the Laplacian eigenbasis, with small components associated with large eigenvalues.The algorithms enforce this structure through regularization of the corresponding coefficients.
- Effective dimension: The effective dimension d is a proxy for the number of relevant dimensions and satisfies d < d_old ≪ D in the paper’s intended regime.Here D is the ambient feature dimension, while d_old denotes the earlier effective-dimension definition.
- Empirical implications: d is upper bounded by D, but experiments show both quantities can be much smaller than D, including when T > N.This supports using spectral bandits beyond the regime where the time horizon is shorter than the number of nodes.
- Effective dimension: The new effective dimension is always bounded by 2d_old and is often much smaller, tightening bounds that depend on the effective dimension.The paper presents this improvement as a reason for replacing the earlier definition.
- Effective dimension: d is especially small when Laplacian coefficients grow rapidly above T, whereas sparse graphs with uniformly small eigenvalues can make d approach T.In the latter case, the resulting regret bounds may become ineffective.
- Lower bound: The paper establishes a lower bound for every effective dimension d and horizon T, showing spectral bandits are at least as difficult as a d-arm bandit.The lower bound transfers the difficulty of the K-arm bandit problem with K = d to this setting.
5. Algorithms
The paper proposes SpectralUCB, SpectralTS, and SpectralEliminator to exploit graph spectral structure in bandit learning. Their regret analyses depend on effective dimension, while implementation techniques address confidence computation, matrix updates, and eigenbasis construction.
- Algorithms: The paper introduces three algorithms: SpectralUCB, SpectralTS, and SpectralEliminator.The first two use confidence-based exploration or Thompson sampling, while SpectralEliminator removes unpromising arms in phases.
- SpectralUCB: SpectralUCB uses a spectral penalty in regularized least squares and sets confidence widths using the effective dimension d.This avoids computing a determinant when defining the confidence parameter.
- SpectralTS: SpectralTS samples coefficients from a normal distribution centered at the current estimate, then chooses the arm maximizing the sampled reward.Its regret bound is stated in terms of the effective dimension.
- SpectralEliminator: SpectralEliminator works in phases by eliminating arms that are not promising, and its regret upper bound improves on SpectralUCB and SpectralTS in d dependence.The related LinearEliminator result achieves optimal √(DT) regret for finite-arm linear bandits.
- Computational scalability: Lazy updates can make SpectralUCB’s running time comparable to SpectralTS despite the general cost of computing N UCBs each round.The implementation maintains a sorted queue while exploiting the fact that each arm’s UCB can only decrease.
- Computational scalability: Sherman–Morrison updates avoid recomputing an N × N matrix inverse from scratch after each rank-one update.The proposed algorithms also use fast SDD solvers to approximate low-frequency Laplacian eigenvectors in O(Lm log m) time.
6. Analysis
The analysis establishes high-probability regret guarantees for SpectralUCB, SpectralTS, and related algorithms using confidence bounds and effective-dimension geometry. Determinant control is the key step that replaces dependence on ambient dimension with dependence on the effective dimension.
- Overview: The paper proves regret upper bounds for SpectralUCB, SpectralTS, and SpectralEliminator after deriving confidence-ellipsoid and effective-dimension lemmas.The proof development proceeds from general concentration results to algorithm-specific regret bounds.
- Effective-dimension analysis: The determinant |V_t| is maximized when the observed feature vectors are aligned with the eigenbasis axes.This geometric property underlies the effective-dimension control of the analysis.
- SpectralUCB: SpectralUCB combines an OFUL-style confidence ellipsoid with determinant geometry to make its regret scale with effective dimension d rather than ambient dimension D.The determinant argument also avoids computing determinants in the algorithm.
- SpectralUCB: With probability at least 1 −δ, SpectralUCB satisfies its theorem-level regret guarantee through confidence widths defined using effective dimension d.The confidence parameter is selected from the effective-dimension analysis rather than from determinant computation.
- Comparison: Setting Λ = I recovers LinUCB and yields the known e O(D√T) regret upper bound as a corollary, while the spectral regularization targets lower-dimensional structure.The related SupLinUCB comparison concerns a different algorithm that is not efficient.
- SpectralTS: SpectralTS separates saturated from unsaturated arms and uses a super-martingale argument to establish its high-probability regret bound.The optimal arm belongs to the unsaturated group, and an alternative Cauchy-Schwarz-based argument supports the analysis.
- SpectralEliminator: Replacing Λ with I in Algorithm 3 gives LinearEliminator, which has an e O(D√T) upper bound and uses self-normalized, data-adaptive confidence bounds.The paper describes its analysis as simpler than those of SupLinRel and SupLinUCB.
7. Experiments
The experiments evaluate empirical regret and computational complexity on artificial and real recommendation datasets, while examining parameter sensitivity and implementation speedups. SpectralEliminator is excluded because its phase-based confidence updates make it impractical for small horizons.
- Experimental design: The experiments compare SpectralTS, SpectralUCB, LinearTS, and LinUCB on artificial graphs plus MovieLens and Flixster datasets.They measure both empirical regret and computational complexity.
- Experimental design: SpectralEliminator is omitted because updating its confidence ellipsoid only at the end of each phase is impractical for small time horizons.This is an explicit experimental scope limitation.
- Experimental design: The study examines sensitivity to parameters and the effects of reduced bases, Sherman-Morrison matrix inversion, and lazy UCB updates.These speedups are evaluated for their impact on computational complexity, performance, or running time.
7.1 Artificial datasets
On artificial lattice, Erdős-Rényi, and Barabási-Albert graphs, spectral algorithms generally achieve lower or sublinear empirical regret than linear baselines. The comparison also shows sensitivity to graph structure and parameter choices.
- Erdős-Rényi graphs: SpectralTS and SpectralUCB can leverage reward smoothness and outperform LinearTS and LinUCB under empirically selected parameters.Figure 4 reports the dependence of cumulative regret on confidence and regularization parameters.
- Erdős-Rényi graphs: Spectral algorithms show sublinear-looking regret while linear algorithms appear linear for small T, with substantially smaller empirical regret for the spectral methods.This comparison is reported for the selected parameters in Figure 5a.
- Lattice graphs: On lattice graphs, spectral algorithms perform well relative to linear algorithms.The lattice experiment uses 500 nodes and empirically selected parameters.
- Barabási-Albert graphs: On Barabási-Albert graphs, spectral algorithms outperform linear algorithms after only a few rounds.The paper cautions that empirically optimal parameters can be too aggressive, as illustrated by SpectralUCB’s apparently linear curve in one horizon.
7.2 The effect of smoothness on the regret
The smoothness experiment varies the number of graph-Laplacian eigenvectors used to construct the reward function and compares SpectralTS with SpectralUCB. It studies how reward smoothness affects cumulative regret on a 500-node Barabási-Albert graph.
- Setup: The experiment uses a Barabási-Albert graph with 500 nodes, time horizon T = 100, and effective dimension close to 8.Algorithm parameters are taken from the earlier Barabási-Albert experiment.
- Setup: Reward smoothness is controlled by making 5, 25, 100, or 500 eigenvector coefficients nonzero.This varies the spectral complexity of the constructed reward function.
- Computational effects: The computational-time experiment distinguishes UCB configurations with or without Sherman-Morrison and lazy updates, and TS configurations with or without Sherman-Morrison.The measured quantity is computational time in seconds.
7.3 Computational complexity improvements
The paper reduces spectral-bandit computation by using fewer Laplacian eigenvectors and implementation optimizations, while evaluating regret and runtime on MovieLens.
- Implementation: Lazy UCB updates made SpectralUCB runtime comparable to, and sometimes better than, SpectralTS.
- Reduced basis: Using 10% of the eigenvectors achieved similar performance to the full basis with a fraction of the running time.The experiment varied L across 20, 200, and 2000 eigenvectors for N = 2019.
- Reduced basis: Extracting only the first L eigenvectors makes graph decomposition O(Lm log m) and reduces each least-squares problem to L dimensions.
- MovieLens evaluation: MovieLens contains 6k users and one million movie ratings, while the experiment used 400 users and 618 movies with at least 500 ratings.
- MovieLens evaluation: On MovieLens, spectral algorithms consistently outperformed linear algorithms across 20 sampled users at T = 500.The experiment also compared running times and used lazy updates for UCB methods.
7.5 Flixster experiments
The Flixster experiment evaluates spectral-bandit methods using a social network of users and movie preferences represented through completed ratings.
- Dataset: The Flixster dataset produced 972 movies and 1070 users after selecting movies with at least 500 ratings.
- Dataset: User preferences were completed using low-rank matrix factorization, following the MovieLens experimental setup.
7.6 Additional observations for improving the empirical performance
The paper identifies graph construction and algorithm-parameter choices as practical levers for improving empirical performance, with trade-offs involving smoothness, effective dimension, and theoretical guarantees.
- Graph structure: Reducing the number of graph neighbors increases effective dimension but decreases function smoothness, creating a trade-off that can improve performance.
- Confidence parameters: Scaling the confidence ellipsoid can improve empirical performance, but some regret bounds may no longer hold.The experiments selected values that gave good empirical performance despite worst-case bounds being loose.
- Regularization: Choosing the regularization parameter λ requires balancing graph dependence against making regularized eigenvalues similar.
- Graph weights: Scaling graph weights changes both eigenvalue gaps and reward-function smoothness, thereby changing the effective dimension and graph usefulness.
8. Conclusion
The paper formulates spectral bandits as repeatedly maximizing an unknown graph-smooth function and addresses the high ambient dimension of standard linear-bandit methods. It introduces algorithms whose regret depends on a smaller effective dimension and reports side results for linear bandits.
- Problem: Spectral bandits repeatedly maximize an unknown function that is assumed smooth on a given similarity graph.
- Problem: Standard linear-bandit regret scales with ambient dimension D, which can be very large.
- Spectral algorithms: Three algorithms—SpectralUCB, SpectralTS, and SpectralEliminator—have regret bounds scaling with effective dimension d rather than D.The paper states that d is typically much smaller than D for real-world graphs.
- Empirical conclusion: The experiments showed that spectral algorithms leverage graph structure better than linear counterparts when rewards are graph-smooth.
- Linear-bandit side results: The paper provides regret analysis for LinUCB with an e O(D√T) upper bound and proves a minimax-optimal bound for LinearEliminator.
- Linear-bandit side results: LinearEliminator uses adaptive confidence bounds and is described as state of the art among algorithms with e O(√DT) regret.