Finite-Time Analysis of Kernelised Contextual Bandits

By Michal Valko, N. Korda, R´emi Munos, Ilias N. Flaounas, Nello Cristianini. Conference on Uncertainty in Artificial Intelligence, 2013

322 citations recorded by the source corpus.

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.

View Paper: https://www.semanticscholar.org/paper/524916b08079b1bdbcad5f5b36e71b7ad8f5f09a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Bandit Algorithms (2020, methodology): “Exponential weighting has been a standard tool in online learning since the papers by Vovk [1990] and Littlestone and Warmuth [1994].”
On Kernelized Multi-armed Bandits (2017, methodology): “Srinivas et al. (2009) have proposed the GP-UCB algorithm, and Valko et al. (2013) the KernelUCB algorithm, for sequentially optimizing reward functions lying in the RKHS H k ( D ) .”
Neural Contextual Bandits with UCB-based Exploration (2019, methodology): “• Unlike the static feature mapping used in kernel bandit algorithms (Valko et al., 2013), NeuralUCB uses a neural network f ( x ; θ t ) and its gradient g ( x ; θ t ) as a dynamic feature mapping depending on θ t .”
Multi-Task Learning for Contextual Bandits (2017, methodology): “We define the effective rank of K̃T+1 in the same way as [18] defines the effective dimension of the kernel feature space.”
Improved Optimistic Algorithms for Logistic Bandits (2020, methodology): “Following (Valko et al., 2013), the linearity of the reward structure has been relaxed to hold only in a reproducing kernel Hilbert space.”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “Part of our results are inspired by the kernelization for the linear bandit problems, e.g. (Valko et al., 2013; Chowdhury & Gopalan, 2017), who studied the regret bound when the features of each arm lies in some reproducing kernel Hilbert space.”