Source-linked AI summary
Finite-Time Analysis of Kernelised Contextual Bandits
Michal Valko, Nathaniel Korda, Remi Munos, Ilias Flaounas, Nelo Cristianini
TL;DR
The paper addresses online reward maximization over very large finite action sets when contexts or their similarities are available but exhaustive exploration is infeasible. It introduces KernelUCB through RKHS-based kernelization and derives a frequentist finite-time regret analysis, recovering the linear-bandit lower bound and improving agnostic GP-UCB bounds.
Problem
Contextual bandits need to maximize rewards over large action sets that cannot all be explored, while exploiting context similarities and potentially nonlinear reward relationships.
Method
KernelUCB kernelizes contextual LinUCB, using RKHS regularized regression and similarities between data points to compute action-specific upper confidence bounds.
Results
For the linear kernel, the regret bound matches the lower bound for contextual linear bandits, while the agnostic analysis improves GP-UCB's bound in kernel-dependent quantity and RKHS reward-function norm.
Takeaways & Limitations
KernelUCB provides a similarity-based, non-linear extension of LinUCB whose analysis covers GP-UCB as a special case and recovers the linear benchmark.
Takeaways & Limitations
The paper omits a detailed derivation because of space constraints, and the linear contextual model assumes one fixed unknown parameter shared across actions.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops KernelUCB for contextual bandits with large action sets and similarity information, using RKHS structure to model potentially nonlinear reward relationships. Its frequentist analysis yields data-dependent regret guarantees that connect effective dimension to prior linear and GP-UCB results.
- Motivation: Large contextual-bandit action sets motivate learning expected rewards from contexts when exhaustive exploration is infeasible.Examples include online advertising and recommending relevant news feeds from cheaply retrieved features.
- Approach: KernelUCB uses similarities between contexts and RKHS regression to form upper confidence bounds for potentially nonlinear reward relationships.It is a kernel-based extension of LinUCB and selects the action with the highest upper confidence bound.
- Analysis: The analysis provides a data-dependent cumulative-regret bound governed by the effective dimension ˜d, which measures the data's occupied directions in the RKHS.The effective dimension roughly captures how many RKHS directions contain most of the data.
- Results: For the dot-product kernel, KernelUCB recovers LinUCB's contextual linear-bandit regret bounds, matching the linear-case lower bound.This establishes the linear setting as a special case of the kernelized analysis.
- Results: GP-UCB is a special case of KernelUCB, while the agnostic analysis improves its regret bound through the kernel-dependent quantity and reward-function norm.The comparison concerns the case where the reward function is not necessarily sampled from a Gaussian-process prior.
- Analysis: The analysis also describes the tradeoff between the regularization parameter and the RKHS norm of the reward function.It provides guidance for setting the regularization parameter.
2 Background
Contextual bandits choose among changing action sets using action contexts and seek to maximize cumulative reward under limited exploration. The background develops UCB-based estimation, reviews linear contextual methods, and positions the setting relative to kernel, Gaussian-process, metric, linear-bandit, and hypothesis-class approaches.
- 2.1 Basic Model: At each time, actions have context vectors, and choosing one yields a context-dependent reward observed by the algorithm.The algorithm uses previously observed contexts, actions, and rewards together with the current context to choose an action.
- 2.1 Basic Model: The contextual regret compares each chosen action with the action having the highest expected reward for the current context.Unlike classical bandits, the optimal action can change over time when contexts change.
- 2.2 UCBs: UCB algorithms select actions by adding an uncertainty width to the estimated mean reward, balancing exploitation and exploration.The widths are designed to be larger for insufficiently explored actions and smaller after repeated observations.
- 2.3 UCBs for Linear Contextual Bandits: Regression constructs contextual reward estimates and uncertainty widths; linear contextual methods use regularised least-squares regression and an exploration parameter η(t).LinUCB uses a constant exploration parameter, while SupLinUCB provides a related theoretical analysis.
- 2.4 Related Work: Prior work includes LinUCB, SupLinUCB, SupLinRel, GP-UCB, metric-similarity methods, Confidence-Ball algorithms, and EXP4-based approaches for related bandit settings.These approaches differ in assumptions, action spaces, regret definitions, and the structural information used.
3 Kernelised UCB
KernelUCB is obtained by directly kernelising LinUCB, replacing finite-dimensional context representations with RKHS representations and computing predictions and confidence widths through kernel matrices. The resulting algorithm selects the action with the largest upper confidence bound and includes GP-UCB as a special case under a particular regularisation choice.
- 3 Kernelised UCB: KernelUCB is derived by directly kernelising LinUCB using the kernel trick and a kernelised Mahalanobis distance.The derivation is presented to establish the notation used for the analysis.
- 3.1 Kernelised Model: Kernel methods map contexts from R^d into a possibly infinite-dimensional RKHS H where a linear reward relationship is modeled.The associated kernel represents inner products between mapped contexts.
- 3.1 Kernelised Model: KernelUCB assumes an RKHS-linear expected reward and defines the optimal action by maximizing the inner product between the mapped context and unknown reward parameter.With the identity mapping, this recovers the linear bandit case.
- 3.2 Kernelised Estimators: Prediction estimators are obtained from ridge regression in the RKHS and rewritten in dual form using only entries of the kernel matrix.This avoids direct computation in a potentially infinite-dimensional feature space.
- 3.2 Kernelised Estimators: Confidence widths use the RKHS analogue of the Mahalanobis distance and can be represented through regularised kernel-matrix operations.For standard normal noise, the width equals the variance of the prediction estimator.
- 3.3 KernelUCB Algorithm: KernelUCB maintains kernel-matrix quantities online and chooses the action with the largest upper confidence bound using an exploration parameter η.The algorithm supports online inverse updates and common linear, RBF, and polynomial kernels.
- 3.3 KernelUCB Algorithm: GP-UCB is a special case of KernelUCB when the regularisation constant is set to the model noise.The kernel choice is problem dependent, and the linear kernel yields the dual representation of LinUCB.
4 Analysis
The analysis controls KernelUCB’s finite-time regret in potentially infinite-dimensional RKHSs using effective dimension, concentration, and regularisation. It recovers linear-bandit guarantees and improves agnostic GP-UCB dependence on kernel complexity and RKHS norm.
- Proof strategy: SupKernelUCB partitions trials into mutually exclusive subsets so conditional reward errors are independent and Azuma-Hoeffding concentration applies.The construction enables high-probability control of predictors despite their dependent random-variable structure.
- Effective dimension: KernelUCB’s analysis replaces potentially infinite RKHS dimension with the data-dependent effective dimension ˜d.˜d reflects how the data are distributed across principal RKHS directions.
- Effective dimension: ˜d ≤ 1 + (C/(γ ln T))^1/α when covariance eigenvalues decrease polynomially as λ_i ≤ Ci^-α, with α > 1.This gives a concrete effective-dimension bound under polynomial spectral decay.
- Special cases: For the linear kernel, the analysis recovers the LinUCB result matching the contextual linear-bandit lower bound.When Φ ≡ I_d, the effective dimension is bounded by d and the known linear result is recovered exactly.
- Comparison with GP-UCB: For agnostic GP-UCB, the RBF-kernel bound scales as O((ln T)^d/2) rather than O((ln T)^d), and unknown RKHS norm enters linearly rather than quadratically.GP-UCB is recovered as a special case when the regulariser equals the model noise.
5 Conclusion
KernelUCB runs using only a similarity function and admits a finite-time regret analysis governed by effective dimension. Its analysis recovers the linear contextual-bandit lower-bound rate and improves agnostic GP-UCB guarantees.
- 5 Conclusion: KernelUCB can operate with only a similarity function instead of explicit context features.The algorithm uses kernelised regularised regression in the RKHS to form action-wise upper confidence bounds.
- 5 Conclusion: The cumulative regret scales as ˜O(√(T ˜d)), where ˜d is the effective dimension of the data in feature space.The effective dimension replaces the potentially infinite RKHS dimension in the analysis.
- 5 Conclusion: The analysis recovers LinUCB’s lower-bound-matching guarantee and improves agnostic GP-UCB dependence on kernel complexity and RKHS norm.For unknown RKHS norm, the dependence is linear rather than quadratic.