Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Finite-Time Analysis of Kernelised Contextual Bandits
Michal Valko, Nathaniel Korda, Remi Munos, Ilias Flaounas, Nelo Cristianini
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.
Keywords:
Pages: 654-663
PS Link:
PDF Link: /papers/13/p654-valko.pdf
BibTex:
@INPROCEEDINGS{Valko13,
AUTHOR = "Michal Valko and Nathaniel Korda and Remi Munos and Ilias Flaounas and Nelo Cristianini",
TITLE = "Finite-Time Analysis of Kernelised Contextual Bandits",
BOOKTITLE = "Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "654--663"
}


hosted by DSL   •   site info   •   help