# Spectral Thompson sampling

arXiv: https://arxiv.org/abs/2604.13739 · HTML: https://mlsanity.com/paper/2604.13739/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 24 references that are in the map.
- First posted on arXiv 15 Apr 2026.

## Builds on (most cited first, 2 of 2)

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)

## Built on by (most cited first, 5 of 5)

- [Spectral bandits for smooth graph functions with applications in recommender systems](https://mlsanity.com/paper/2605.20552/) (2026)
- [Revealing graph bandits for maximizing local influence](https://mlsanity.com/paper/2605.00489/) (2026)
- [Spectral bandits for smooth graph functions](https://mlsanity.com/paper/2604.18420/) (2026)
- [Spectral bandits](https://mlsanity.com/paper/2604.25272/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)

## Abstract (arXiv)

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.