Spectral Thompson sampling

arXiv cs.LG / 4/16/2026

💬 OpinionSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

Key Points

The paper introduces Spectral Thompson Sampling (SpectralTS), a variant of Thompson Sampling for graph-structured bandit problems where neighboring nodes have similar expected payoffs.
It argues that traditional TS analysis/tools can scale poorly with the number of choices, and addresses this using an “effective dimension” d that is expected to be small in real-world graphs.
Theoretical results show SpectralTS achieves regret scaling of about d*sqrt(T ln N) with high probability, matching the order of best-known bounds while improving computational efficiency.
The authors report that SpectralTS is competitive on both synthetic experiments and real-world data, suggesting practical value for applications like recommender systems and computational advertising.

Abstract

Thompson Sampling (TS) has attracted a lot of interest due to its good empirical performance, in particular in the computational advertising. Though successful, the tools for its performance analysis appeared only recently. In this paper, we describe and analyze SpectralTS algorithm for a bandit problem, where the payoffs of the choices are smooth given an underlying graph. In this setting, each choice is a node of a graph and the expected payoffs of the neighboring nodes are assumed to be similar. Although the setting has application both in recommender systems and advertising, the traditional algorithms would scale poorly with the number of choices. For that purpose we consider an effective dimension d, which is small in real-world graphs. We deliver the analysis showing that the regret of SpectralTS scales as d*sqrt(T ln N) with high probability, where T is the time horizon and N is the number of choices. Since a d*sqrt(T ln N) regret is comparable to the known results, SpectralTS offers a computationally more efficient alternative. We also show that our algorithm is competitive on both synthetic and real-world data.