Finite-Time Analysis of Kernelised Contextual Bandits

Michal Valko, Nathaniel Korda, Rémi Munos, Ilias N. Flaounas, Nello Cristianini

TL;DR

This paper introduces KernelUCB, a frequentist algorithm for contextual bandits that leverages kernel methods to model non-linear relationships between actions and rewards. The authors provide a rigorous finite-time analysis, proving a cumulative regret bound of $\tilde{O}(\sqrt{T\tilde{d}})$, where $\tilde{d}$ is the "effective dimension" of the data—a result that matches the lower bounds for linear bandits and improves upon previous agnostic analyses of Gaussian Process-based approaches.

What Problem Does This Paper Address?

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

While kernels allow us to model non-linearities by mapping data into a high-dimensional Reproducing Kernel Hilbert Space (RKHS), doing so in a bandit setting is challenging. Previous work (like GP-UCB) often relied on Bayesian assumptions—assuming the reward function is actually sampled from a Gaussian Process. This paper tackles the agnostic case: how do we provide strong theoretical guarantees when we only assume the reward function lives in an RKHS, without assuming a specific prior distribution?

Methods

The authors propose KernelUCB, which is essentially a "kernelized" version of the popular LinUCB algorithm.

  1. The Kernel Trick: Instead of working directly with high-dimensional feature vectors, the algorithm uses a similarity function (kernel) $k(x, x')$. This allows it to operate in potentially infinite-dimensional spaces using only the kernel matrix of observed data.
  2. Dual Representation: They derive dual forms for both the reward predictor and the confidence width. This ensures the algorithm only needs to perform operations on the kernel matrix, avoiding the "curse of dimensionality" in the feature space.
  3. SupKernelUCB: To facilitate a rigorous mathematical proof, the authors introduce a variant called SupKernelUCB. This version uses a "master" algorithm to partition trials into subsets, ensuring that the rewards within each subset are independent enough to apply concentration inequalities (like Azuma-Hoeffding).
  4. Effective Dimension ($\tilde{d}$): They define a data-dependent quantity called the effective dimension. This measures how many "principal directions" the data actually occupies in the RKHS, providing a way to bound regret even when the underlying Hilbert space is infinite-dimensional.

Datasets

Not discussed in the paper. 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.

Key Insights and Ideas

  • Agnostic Superiority: The paper shows that for the "agnostic" case (where the reward function is fixed but unknown), their frequentist analysis yields a tighter bound than the previous state-of-the-art (GP-UCB). Specifically, their 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: The authors show that if you use a linear kernel, KernelUCB becomes identical to LinUCB, and their regret bound perfectly matches the known lower bounds for the linear case. This confirms that their kernelized analysis is "tight."
  • Effective Dimension as a Proxy: The introduction of $\tilde{d}$ is a clever way to handle infinite-dimensional spaces. It suggests that even if our model could be infinitely complex, the actual complexity is limited by the diversity of the contexts we actually observe.
  • Regularization Trade-off: The analysis provides a clear guideline for setting the regularization parameter $\gamma$ based on the (often unknown) RKHS norm of the reward function.

Key Results

  • Regret Bound: The main result is a cumulative regret bound of $R(T) \leq \tilde{O}(\sqrt{T\tilde{d}})$. In plain English, this means the "mistakes" the algorithm makes grow much slower than time $T$, ensuring the algorithm eventually learns the optimal strategy.
  • Information Gain vs. Effective Dimension: They prove 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.
  • Kernel Specifics: For common kernels like the RBF (Gaussian) kernel, they show their bound scales with $O(\ln T)^{d/2}$, an improvement over the $O(\ln T)^d$ found in prior agnostic GP-UCB literature.

Limitations and Future Work

  • Computational Complexity: Like many kernel methods, KernelUCB requires inverting a kernel matrix. While the authors suggest using the Schur complement for online updates (reducing the cost per step), the memory and time complexity still grow with the number of rounds $T$.
  • Hyperparameter Sensitivity: The algorithm requires choosing a kernel and a regularization parameter $\gamma$. The paper notes that if the RKHS norm of the reward function is unknown, setting $\gamma$ becomes a challenge that might require cross-validation.
  • Finite Action Set: The analysis assumes a large but finite set of actions. Extending this to truly continuous action spaces while maintaining the same frequentist guarantees is a potential area for future exploration.

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},
}

Loading related content...

Figure