# Spectral bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 60 references that are in the map.
- First posted on arXiv 28 Apr 2026.

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

- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Cheap Bandits](https://mlsanity.com/paper/1506.04782/) (2015)
- [Spectral Thompson sampling](https://mlsanity.com/paper/2604.13739/) (2026)
- [Efficient learning by implicit exploration in bandit problems with side observations](https://mlsanity.com/paper/2604.24555/) (2026)
- [Online learning with noisy side observations](https://mlsanity.com/paper/2604.13740/) (2026)

## Abstract (arXiv)

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.