Finite-Time Analysis of Kernelised Contextual Bandits

Remi Munos, Michal Valko, Nathaniel Korda, Ilias Flaounas, Nelo Cristianini
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:559-568, 2013.

Abstract

We tackle the problem of online reward max- imisation over a large finite set of actions de- scribed 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 similari- ties between actions’ contexts and that the expected reward is an arbitrary linear func- tion of the contexts’ images in the related re- producing kernel Hilbert space (RKHS). We propose KernelUCB, a kernelised UCB algo- rithm, and give a cumulative regret bound through a frequentist analysis. For contex- tual bandits, the related algorithm GP-UCB turns out to be a special case of our algo- rithm, and our finite-time analysis improves the regret bound of GP-UCB for the agnos- tic 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-munos13a, title = {Finite-Time Analysis of Kernelised Contextual Bandits}, author = {Munos, Remi and Valko, Michal and Korda, Nathaniel and Flaounas, Ilias and Cristianini, Nelo}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {559--568}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/munos13a/munos13a.pdf}, url = {https://proceedings.mlr.press/r11/munos13a.html}, abstract = {We tackle the problem of online reward max- imisation over a large finite set of actions de- scribed 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 similari- ties between actions’ contexts and that the expected reward is an arbitrary linear func- tion of the contexts’ images in the related re- producing kernel Hilbert space (RKHS). We propose KernelUCB, a kernelised UCB algo- rithm, and give a cumulative regret bound through a frequentist analysis. For contex- tual bandits, the related algorithm GP-UCB turns out to be a special case of our algo- rithm, and our finite-time analysis improves the regret bound of GP-UCB for the agnos- tic 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Finite-Time Analysis of Kernelised Contextual Bandits %A Remi Munos %A Michal Valko %A Nathaniel Korda %A Ilias Flaounas %A Nelo Cristianini %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-munos13a %I PMLR %P 559--568 %U https://proceedings.mlr.press/r11/munos13a.html %V R11 %X We tackle the problem of online reward max- imisation over a large finite set of actions de- scribed 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 similari- ties between actions’ contexts and that the expected reward is an arbitrary linear func- tion of the contexts’ images in the related re- producing kernel Hilbert space (RKHS). We propose KernelUCB, a kernelised UCB algo- rithm, and give a cumulative regret bound through a frequentist analysis. For contex- tual bandits, the related algorithm GP-UCB turns out to be a special case of our algo- rithm, and our finite-time analysis improves the regret bound of GP-UCB for the agnos- tic 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. %Z Reissued by PMLR on 04 October 2026.
APA
Munos, R., Valko, M., Korda, N., Flaounas, I. & Cristianini, N.. (2013). Finite-Time Analysis of Kernelised Contextual Bandits. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:559-568 Available from https://proceedings.mlr.press/r11/munos13a.html. Reissued by PMLR on 04 October 2026.

Related Material