Spectral Thompson sampling

Tomas Kocak; Michal Valko; Remi Munos; Shipra Agrawal

cs.LGApr 15, 2026

Spectral Thompson sampling

Authors: Tomas Kocak, Michal Valko, Remi Munos, Shipra Agrawal

Organizations: SequeL team, INRIA Lille - Nord Europe, France · SequeL team, INRIA Lille, France · Microsoft Research NE, USA · ML and Optimization Group, Microsoft Research, Bangalore, India

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 dsqrt(T ln N) with high probability, where T is the time horizon and N is the number of choices. Since a dsqrt(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.

Figures & tables

	Linear	Spectral
Optimistic Approach $D^{2}N$ per step update	LinUCB $D\sqrt{T\ln{T}}$	SpectralUCB $d\sqrt{T\ln{T}}$
Thompson Sampling $D^{2}+DN$ per step update	LinearTS $D\sqrt{T\ln N}$	SpectralTS $d\sqrt{T\ln N}$

Table 1: Linear vs. Spectral Bandits

Figure 1: Barabási-Albert random graph results

Figure 2: MovieLens data results

Thompson Sampling

Thompson sampling selects actions by drawing from posterior beliefs about rewards, balancing exploration and exploitation in sequential decisions.

See all 53 papers

Spectral bandits
Apr 28, 2026Tomáš Kocák, Rémi Munos, Branislav Kveton +2Multi-Armed Bandits Graph Bandits
ENS de Lyon, 15 Parvis Ren´e Descartes, 69342 Lyon, France · Inria Lille – Nord Europe, SequeL team · DeepMind Paris, 14 Rue de Londres, 75009 Paris, France +2
Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
May 10, 2026Zhiming Huang, Bingshan Hu, Jianping PanThompson Sampling Multi-Armed Bandits
Paul G. Allen School of Computer Science & Engineering, University of Washington, WA, USA · Department of Computer Science, University of British Columbia, BC, Canada · Department of Computer Science, University of Victoria, BC, Canada
Spectral bandits for smooth graph functions
Apr 20, 2026Michal Valko, Rémi Munos, Branislav Kveton +1Graph Signal Processing Multi-Armed Bandits
INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France · INRIA Lille - Nord Europe, SequeL team, France · Microsoft Research New England, Cambridge, MA, USA +1

Apr 28, 2026J/K move · Enter open · S save

Spectral bandits

Tomáš Kocák, Rémi Munos, Branislav Kveton, Shipra Agrawal+1

ENS de Lyon, 15 Parvis Ren´e Descartes, 69342 Lyon, France · Inria Lille – Nord Europe, SequeL team · DeepMind Paris, 14 Rue de Londres, 75009 Paris, France+2

Multi-Armed Bandits Graph Bandits Recommender Systems

Open paper AskPDF 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.

Abstract

Thompson Sampling

Explore similar work

Spectral bandits

Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

Spectral bandits for smooth graph functions