TL;DR
SpectralTS brings the power of Thompson Sampling to graph-structured bandit problems, offering a massive computational speedup over optimistic approaches like SpectralUCB. By leveraging the graph's spectral properties, it achieves a competitive regret bound that scales with a small "effective dimension" rather than the total number of items, making it ideal for large-scale recommender systems.
What Problem Does This Paper Address?
Multi-armed bandits are a classic framework for sequential decision-making under uncertainty, widely used in movie recommendations and computational advertising. However, standard bandit algorithms struggle when the number of choices ($N$) is massive.
To handle large item pools, recent approaches use spectral bandits, which assume items are nodes on a graph where neighboring items yield similar rewards (smoothness). While an existing algorithm, SpectralUCB, successfully uses this graph structure to minimize regret, it suffers from a major bottleneck: it must calculate upper confidence bounds for every single item at every single time step. When $N$ is in the thousands or millions, this $\mathcal{O}(N^3)$ per-step complexity becomes computationally prohibitive.
Methods
The authors introduce Spectral Thompson Sampling (SpectralTS) to solve this computational bottleneck. Instead of deterministically calculating upper confidence bounds for all arms, SpectralTS takes a Bayesian approach:
- Graph Spectral Basis: It uses the graph Laplacian ($L = D - W$) and its eigendecomposition to project items into a smooth spectral basis, focusing on eigenvectors associated with small eigenvalues.
- Effective Dimension ($d$): The authors utilize an "effective dimension" $d$, which captures the true underlying structural complexity of the graph. In real-world graphs, $d$ is typically much smaller than $N$.
- Posterior Sampling: At each time step, the algorithm samples a candidate preference vector $\tilde{\mu}(t)$ from a Gaussian posterior distribution $\mathcal{N}(\hat{\mu}(t), v^2 B_t^{-1})$.
- Greedy Selection: It greedily selects the arm that maximizes the expected reward given that specific sample, updating the posterior efficiently via rank-one updates.
This sampling strategy drops the per-step computational complexity from $\mathcal{O}(N^3)$ to $\mathcal{O}(N^2)$.
Datasets
The algorithm was evaluated on two primary setups:
- Synthetic Data: Random graphs generated using the Barabási-Albert (BA) model ($N = 250$ nodes, degree parameter 3) to simulate real-world scale-free network properties.
- MovieLens Dataset: A real-world benchmark consisting of 2,019 movies. Edges represent movie similarities, and the target graph function represents actual user ratings.
Key Insights and Ideas
- The Sampling Advantage: Thompson Sampling completely bypasses the need to compute expensive matrix-vector norms for every arm. Generating a single sample from the posterior and performing a dot product across arms is vastly cheaper than calculating UCBs for all arms.
- Frequentist Guarantees for a Bayesian Heuristic: Despite Thompson Sampling being a Bayesian heuristic, the authors successfully prove a strong frequentist (worst-case) regret bound using advanced martingale analysis techniques.
- The Power of $T < N$: The algorithm is specifically optimized for the practical regime where the time horizon $T$ is smaller than the total number of items $N$ (e.g., a user will never watch all movies on Netflix). In this setting, the effective dimension $d$ remains small, keeping the regret bound tight.
Key Results
- Theoretical Bound: The cumulative regret of
SpectralTSscales as $\mathcal{O}(d \sqrt{T \ln N})$, matching the scaling of state-of-the-art spectral methods while being computationally superior. - Empirical Performance: In both synthetic and real-world tests,
SpectralTSachieved cumulative regret comparable to or slightly better thanSpectralUCBwhile executing significantly faster.
As seen in the Barabási-Albert simulation results, SpectralTS dramatically reduces runtime while maintaining low regret:
Barabási-Albert random graph results showing comparable regret but massive computational time savings for SpectralTS.
Similarly, on the real-world MovieLens dataset, SpectralTS cut down the total computational time from roughly 2,000 seconds to around 500 seconds:
MovieLens data results demonstrating that SpectralTS matches SpectralUCB's accuracy while running significantly faster.
Limitations and Future Work
- Diminishing Returns for Long Horizons: The benefits of
SpectralTSare most pronounced when $T < N$. If the time horizon $T$ grows much larger than $N$, the effective dimension $d$ approaches $N$, and the spectral advantage over standard linear bandits fades. - Static Graph Assumption: The algorithm assumes that the underlying similarity graph is perfectly known and static. Extending this framework to handle noisy, evolving, or dynamically learned graphs remains an open challenge for future research.
Summary updated