Finite-Time Analysis of Kernelised Contextual Bandits

Michal Valko, Nathaniel Korda, Rémi Munos, Ilias N. Flaounas, Nello 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.

Introduction

In many real-world scenarios, such as online advertising or news recommendation, an agent must select actions from a massive set based on "contexts" (e.g., user profiles or article keywords). While standard linear contextual bandits assume the reward is a linear function of these contexts, real-world relationships are rarely perfectly linear.

Kernel methods allow us to model non-linearities by mapping data into a high-dimensional Reproducing Kernel Hilbert Space (RKHS). However, providing theoretical guarantees in a bandit setting is challenging. Previous work, such as GP-UCB, often relied on Bayesian assumptions, assuming the reward function is sampled from a Gaussian Process. This paper addresses the agnostic case: providing strong theoretical guarantees when the reward function lives in an RKHS without assuming a specific prior distribution.

The KernelUCB Algorithm

The authors propose KernelUCB, a frequentist algorithm that leverages kernel methods to model non-linear relationships between actions and rewards. It can be viewed as a "kernelized" version of the LinUCB algorithm, filling a gap in the literature for frequentist bandit analysis using kernels.

Comparison of regression and bandit algorithms in Bayesian and Frequentist frameworks.

The algorithm relies on several key technical components:

  1. The Kernel Trick: Instead of working directly with high-dimensional feature vectors, the algorithm uses a similarity function (kernel) $k(x, x')$, allowing it to operate in potentially infinite-dimensional spaces using only the kernel matrix of observed data.
  2. Dual Representation: By deriving dual forms for both the reward predictor and the confidence width, the algorithm ensures operations are performed on the kernel matrix, avoiding the "curse of dimensionality."
  3. SupKernelUCB: To facilitate rigorous mathematical proof, the authors introduce a variant called SupKernelUCB. This version partitions trials into subsets to ensure rewards within each subset are sufficiently independent for concentration inequalities (like Azuma-Hoeffding).
  4. Effective Dimension ($\tilde{d}$): This data-dependent quantity measures the "principal directions" the data occupies in the RKHS, bounding regret even in infinite-dimensional spaces.

Theoretical Analysis and Key Results

The paper provides a rigorous finite-time analysis, proving a cumulative regret bound of $\tilde{O}(\sqrt{T\tilde{d}})$. This result matches the lower bounds for linear bandits and improves upon previous agnostic analyses of Gaussian Process-based approaches.

Agnostic Superiority

For the "agnostic" case where the reward function is fixed but unknown, the frequentist analysis yields a tighter bound than the previous state-of-the-art (GP-UCB). Specifically, the regret scales with the square root of the effective dimension ($\sqrt{\tilde{d}}$), whereas previous agnostic bounds scaled linearly with information gain.

The Bridge to Linear Bandits

When using a linear kernel, KernelUCB becomes identical to LinUCB. The authors show their regret bound perfectly matches the known lower bounds for the linear case, confirming the tightness of their kernelized analysis.

Information Gain vs. Effective Dimension

The authors demonstrate that the information gain $I(y_T; \theta^*)$ used in previous GP-UCB analyses is at least as large as their effective dimension $\tilde{d}$. By showing their bound depends on the smaller quantity, they demonstrate a theoretical improvement. For common kernels like the RBF (Gaussian) kernel, the bound scales with $O(\ln T)^{d/2}$, an improvement over the $O(\ln T)^d$ found in prior agnostic GP-UCB literature.

Discussion and Limitations

While KernelUCB provides strong theoretical guarantees, it faces practical challenges. Like many kernel methods, it requires inverting a kernel matrix. Although the authors suggest using the Schur complement for online updates, the memory and time complexity still grow with the number of rounds $T$.

Additionally, the algorithm requires choosing a kernel and a regularization parameter $\gamma$. If the RKHS norm of the reward function is unknown, setting $\gamma$ becomes a challenge. Finally, the analysis assumes a large but finite set of actions; extending this to truly continuous action spaces while maintaining frequentist guarantees remains an area for future exploration.

Note: This is a purely theoretical paper focused on providing mathematical proofs and regret bounds. No empirical experiments on specific datasets were conducted in this work.

Summary updated

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.
BibTeX
@inproceedings{valko2013finite,
  author = {Michal Valko and Nathaniel Korda and Rémi Munos and Ilias N. Flaounas and Nello Cristianini},
  title = {{Finite-Time Analysis of Kernelised Contextual Bandits}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=OQtgoaReT9r},
}
Figure