Finite-Time Analysis of Kernelised Contextual Bandits

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.

Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)

References in corpus (2)

• Efficient Optimal Learning for Contextual Bandits
• An introduction to the Europe Media Monitor family of applications

Cited by in corpus (50)

• Spectral bandits for smooth graph functions
• Differentially-Private Federated Linear Bandits
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Multi-objective Contextual Multi-armed Bandit with a Dominant Objective
• Neural Thompson Sampling
• Distributionally Robust Bayesian Optimization
• Streaming kernel regression with provably adaptive mean, variance, and regularization
• Improved Optimistic Algorithms for Logistic Bandits
• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• Statistical Inference for Online Decision Making via Stochastic Gradient Descent
• Stochastic Bandits with Context Distributions
• Federated Linear Contextual Bandits
• Simple Regret Minimization for Contextual Bandits
• Graph Neural Bandits
• EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Multi-objective Contextual Bandit Problem with Similarity Information
• Corruption-Tolerant Gaussian Process Bandit Optimization
• Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• High-Dimensional Experimental Design and Kernel Bandits
• Optimal Order Simple Regret for Gaussian Process Bandits
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• Neural Bandit with Arm Group Graph
• Online Learning in Kernelized Markov Decision Processes
• Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
• Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning
• Neural Combinatorial Clustered Bandits for Recommendation Systems
• Stochastic Linear Contextual Bandits with Diverse Contexts
• Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification
• Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity
• Gaussian Process Bandit Optimization with Few Batches
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Active Online Learning with Hidden Shifting Domains
• Approximation Theory Based Methods for RKHS Bandits
• Pure Exploration in Kernel and Neural Bandits
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Self-Supervised Contextual Bandits in Computer Vision
• Collaborative Pure Exploration in Kernel Bandit
• Neural Contextual Bandits without Regret
• Uniform Generalization Bounds for Overparameterized Neural Networks
• Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures
• Kernel-based Multi-Task Contextual Bandits in Cellular Network Configuration
• Robust Bandit Learning with Imperfect Context