Finite-Time Analysis of Kernelised Contextual Bandits

Michal Valko 1 Nathan Korda 1 Rémi Munos 1 Ilias Flaounas 2 Nello Cristianini 2
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 : We tackle the problem of online reward maximisation over a large finite set of actions described by their contexts. We focus on the case when the number of actions is too big to sample all of them even once. However we assume that we have access to the similarities between actions' contexts and that the expected reward is an arbitrary linear function of the contexts' images in the related reproducing kernel Hilbert space (RKHS). We propose KernelUCB, a kernelised UCB algorithm, and give a cumulative regret bound through a frequentist analysis. For contextual bandits, the related algorithm GP-UCB turns out to be a special case of our algorithm, and our finite-time analysis improves the regret bound of GP-UCB for the agnostic case, both in the terms of the kernel-dependent quantity and the RKHS norm of the reward function. Moreover, for the linear kernel, our regret bound matches the lower bound for contextual linear bandits.
Type de document :
Communication dans un congrès
Uncertainty in Artificial Intelligence, Jul 2013, Bellevue, United States
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00826946
Contributeur : Michal Valko <>
Soumis le : mardi 28 mai 2013 - 15:52:18
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 3 septembre 2013 - 09:52:58

Fichier

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

Identifiants

  • HAL Id : hal-00826946, version 1

Citation

Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, Nello Cristianini. Finite-Time Analysis of Kernelised Contextual Bandits. Uncertainty in Artificial Intelligence, Jul 2013, Bellevue, United States. 〈hal-00826946〉

Partager

Métriques

Consultations de la notice

604

Téléchargements de fichiers

390