Spectral Bandits for Smooth Graph Functions with Applications in Recommender Systems

Tomáš Kocák 1 Michal Valko 1 Rémi Munos 2, 1 Branislav Kveton 3 Shipra Agrawal 4
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
2 Microsoft - Microsoft Research [Cambridge]
3 Technicolor Research [Palo Alto]
4 Microsoft Research [Redmond]
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 recommended item 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 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 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 nodes evaluations.
Type de document :
Communication dans un congrès
AAAI Workshop on Sequential Decision-Making with Big Data, Jul 2014, Québec City, Canada
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01045036
Contributeur : Michal Valko <>
Soumis le : jeudi 24 juillet 2014 - 14:58:25
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 25 novembre 2014 - 16:46:25

Fichier

Spectral_Bandits.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01045036, version 1

Collections

INRIA | UNIV-LILLE3 | LAGIS | CRISTAL | CRISTAL-SEQUEL

Citation

Tomáš Kocák, Michal Valko, Rémi Munos, Branislav Kveton, Shipra Agrawal. Spectral Bandits for Smooth Graph Functions with Applications in Recommender Systems. AAAI Workshop on Sequential Decision-Making with Big Data, Jul 2014, Québec City, Canada. 〈hal-01045036〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

439

Téléchargements de fichiers

213

Contact


archive-ouverte@inria.fr