Spectral bandits for smooth graph functions with applications in recommender systems

1 Introduction

• The paper formalizes bandits in which graph nodes are arms and expected payoffs form a smooth graph function.Such functions return similar values on neighboring nodes and can be expressed using Laplacian eigenvectors with the smallest eigenvalues.Source: §1 · p. 1
• Targeted advertising can be framed as learning a smooth preference function over a social network to find interested people.The passage motivates this framing by noting that friends tend to have similar preferences.Source: §1 · p. 1
• In content-based recommendation, similar items form graph neighbors, and the framework models a user's preference for those items.The goal is to learn which items the user likes most from ratings of recommended items.Source: §1 · p. 1
• The setting assumes the graph is known, then repeatedly selects a node and observes its payoff, with interest in the regime t < N.Examples include observing an ad click or an item's rating.Source: §1 · p. 1
• When the number of eigenvectors k is unknown and may approach N, regularization is needed to avoid regret scaling with N.If k were small and known, ordinary linear bandits could solve the problem trivially.Source: §1 · pp. 1–2
• The proposed algorithms target expected cumulative regret scaling with effective dimension d rather than poorly with node count N.The paper evaluates both algorithms on synthetic and real-world content-based recommendation problems.Source: §1 · p. 2

2 Setting

• The known graph has nodes connected by similarity-weighted edges, and its Laplacian eigenvalues and eigenvectors define the spectral representation.The Laplacian is L = D − W, with eigenvalues ordered from smallest to largest.Source: §2 · p. 2
• A reward is assumed to be a linear combination of Laplacian eigenvectors, with larger coefficients on low-eigenvalue vectors expressing graph smoothness.The paper does not require a hard cutoff to zero coefficients after some small number k; instead it assumes high-index coefficients are small.Source: §2 · p. 2
• At each time step, the recommender selects a node and observes its noisy reward.The reward is modeled as x^T_{π(t)}α* + ε_t, with R-sub-Gaussian noise.Source: §2 · p. 2
• The objective is cumulative pseudo-regret against the strategy that always selects the node with the best expected payoff.The node representation has dimension D and norm at most one.Source: §2 · p. 2
• Because the number of arms, nodes, and basis dimensions can all equal N, regret scaling with N or D is unacceptable for large graphs.The algorithms and analyses also apply to any finite number of arms K.Source: §2 · p. 2

3 Effective dimension

• Effective dimension d is a proxy for the number of relevant dimensions in the problem.The section introduces a formal definition, but the supplied passage does not include its defining condition.Source: §3 · p. 2
• The setting assumes diagonal coefficients 0 < λ_1 ≤ ··· ≤ λ_N and vectors x_i with norm at most 1; for graph functions, the basis vectors have norm 1.Because the first graph-Laplacian eigenvalue is zero, the coefficients are shifted using Λ = Λ_L + λI.Source: §3 · p. 2
• When the coefficients λ_i grow rapidly above T, d is small; if they are all small, d may be of order T and the regret bounds may be useless.The small-d case is described for spaces whose dimension is much larger than T, including large social-network graphs.Source: §3 · p. 2

4 Algorithms

• SpectralUCB uses a spectral penalty in a regularized least-squares estimate and sets reward-prediction confidence widths using effective dimension d.Its cumulative-regret guarantee is stated under ||α*||Λ≤C and predictions in [−1, 1].Source: SpectralUCB · p. 3
• The regularization bound C must cover ||α*||Λ; choosing it too small can put the true coefficients outside the region and cause underperformance.A time-dependent C_t avoids needing an advance upper bound, but the regret guarantee holds only once C_t≥||α*||Λ.Source: SpectralUCB · p. 3
• SpectralTS samples the unknown coefficients from a normal distribution, initializing its confidence matrix with the graph-Laplacian penalty ΛL+λI.This initialization encodes the assumption that large coefficients correspond to eigenvectors with small eigenvalues.Source: SpectralUCB · p. 3
• With D=N, SpectralTS takes N² time per step versus N³ for SpectralUCB because it avoids computing confidence bounds for every arm.The comparison follows from sampling and maximizing a sampled parameter in SpectralTS, versus evaluating a confidence norm for each context in SpectralUCB.Source: SpectralUCB · p. 3
• Under ||α*||Λ≤C and |x_i^Tα*|≤1, SpectralTS has a 1−δ probability cumulative-regret bound that scales with effective dimension d.The section frames this guarantee for recommendation settings with T<N.Source: SpectralUCB · p. 4

• In the T < N synthetic setting, the 250-node Barabási–Albert graph used degree 3, with payoffs based on the first three smoothest Laplacian eigenvectors.Source: §5 · p. 4
• Across 10 simulations, SpectralTS had results comparable to SpectralUCB but much faster computation, since SpectralUCB computes confidence intervals for every arm.Source: Figure 3 · p. 4, §5 · p. 4
• The MovieLens experiment used a 10-nearest-neighbor similarity graph of 2019 movies and averaged results over 10 randomly sampled users.Source: §5 · p. 4, Figure 4 · p. 4
• On MovieLens, SpectralTS and SpectralUCB both outperform LinearTS and LinUCB in cumulative regret, following the same trend as the synthetic data.Source: Figure 4 · p. 4, §5 · p. 4