# Spectral bandits for smooth graph functions

Source: [Spectral bandits for smooth graph functions](<https://www.sota2.com/research/paper/69e705287d0172140ec7f321>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-22T05:23:53.567Z

Authors: Michal Valko, R\\'emi Munos, Branislav Kveton, Tom\\'a\\v{s} Koc\\'ak

Published: 2026-04-20T15:39:22.000Z

## Abstract

Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this paper, 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 and its expected rating is similar to 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 two algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on real-world content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of nodes evaluations.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Contextual Bandits on ogbn-arxiv](<https://www.sota2.com/research/sota/contextual-bandits-on-ogbn-arxiv.md>): Contextual Bandits; Ogbn-arxiv; Cumulative Regret: 210.8.

- [Contextual Bandits on MIND small](<https://www.sota2.com/research/sota/contextual-bandits-on-mind-small.md>): Contextual Bandits; MIND small; Cumulative Regret: 341.7.

- [Contextual Bandits on Synthetic SBM](<https://www.sota2.com/research/sota/contextual-bandits-on-synthetic-sbm.md>): Contextual Bandits; Synthetic SBM; Cumulative Regret: 466.2.

- [Contextual Bandits on Amazon](<https://www.sota2.com/research/sota/contextual-bandits-on-amazon.md>): Contextual Bandits; AMAZON; Cumulative Regret R(T): 195.

- [Contextual Bandits on LastFM](<https://www.sota2.com/research/sota/contextual-bandits-on-lastfm.md>): Contextual Bandits; LastFM; Cumulative Regret: 282.7.

- [Contextual Bandits on MovieLens-1M](<https://www.sota2.com/research/sota/contextual-bandits-on-movielens-1m.md>): Contextual Bandits; MovieLens 1M; Cumulative Regret: 245.1.

- [Contextual Bandits on MovieLens 100k](<https://www.sota2.com/research/sota/contextual-bandits-on-movielens-100k.md>): Contextual Bandits; MovieLens 100k; Cumulative Regret: 256.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2604.18420>)

[PDF](<https://arxiv.org/pdf/2604.18420.pdf>)
