Spectral Thompson Sampling

Tomáš Kocák 1 Michal Valko 1 Rémi Munos 2, 1 Shipra Agrawal 3
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : Thompson Sampling (TS) has surged 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.
Type de document :
Communication dans un congrès
AAAI Conference on Artificial Intelligence, Jul 2014, Québec City, Canada
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

Contributeur : Michal Valko <>
Soumis le : dimanche 27 juillet 2014 - 17:22:59
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 11 avril 2017 - 18:22:37


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00981575, version 2


Tomáš Kocák, Michal Valko, Rémi Munos, Shipra Agrawal. Spectral Thompson Sampling. AAAI Conference on Artificial Intelligence, Jul 2014, Québec City, Canada. 〈hal-00981575v2〉



Consultations de la notice


Téléchargements de fichiers