Spectral Bandits for Smooth Graph Functions

Michal Valko 1 Rémi Munos 2, 1 Branislav Kveton 3 Tomáš Kocák 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
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.
Type de document :
Communication dans un congrès
International Conference on Machine Learning, May 2014, Beijing, China
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00986818
Contributeur : Michal Valko <>
Soumis le : mardi 20 mai 2014 - 00:24:34
Dernière modification le : jeudi 11 janvier 2018 - 01:49:34
Document(s) archivé(s) le : mercredi 20 août 2014 - 10:55:14

Fichier

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

Identifiants

  • HAL Id : hal-00986818, version 3

Citation

Michal Valko, Rémi Munos, Branislav Kveton, Tomáš Kocák. Spectral Bandits for Smooth Graph Functions. International Conference on Machine Learning, May 2014, Beijing, China. 〈hal-00986818v3〉

Partager

Métriques

Consultations de la notice

826

Téléchargements de fichiers

223