mlsanityData to 7 Oct 2026

Finite-Time Analysis of Kernelised Contextual Bandits

arXiv 1309.6869 ↗First posted 26 Sep 2013cs.LG stat.MLcited by 177

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 177 papers in the map (data through 7 Oct 2026). First posted on arXiv 26 Sep 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 32; 2022: 31; 2023: 27; 2024: 26; 2025: 33; 2026: 28.

177 papers.

Sort:

By area:

  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  2. 2021Adapting to Misspecification in Contextual Banditscited by 81
  3. 2021Federated Linear Contextual Banditscited by 61
  4. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  5. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  6. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  7. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  8. 2024Feedback Efficient Online Fine-Tuning of Diffusion Modelscited by 52
  9. 2021EE-Net: Exploitation-Exploration Neural Networks in Contextual Banditscited by 43
  10. 2021Neural Contextual Bandits without Regretcited by 40
  11. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  12. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
38 more
  1. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  2. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  3. 2023On the Sublinear Regret of GP-UCBcited by 25
  4. 2024Bridging Model-Based Optimization and Generative Modeling via Conservative Fine-Tuning of Diffusion Modelscited by 24
  5. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  6. 2021Batched Neural Banditscited by 22
  7. 2021Neural Active Learning with Performance Guaranteescited by 22
  8. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  9. 2021Multi-facet Contextual Bandits: A Neural Network Perspectivecited by 20
  10. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  11. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  12. 2023Graph Neural Banditscited by 20
  13. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  14. 2021Nearly Optimal Algorithms for Level Set Estimationcited by 17
  15. 2022Learning Neural Contextual Bandits Through Perturbed Rewardscited by 17
  16. 2022Federated Neural Banditscited by 17
  17. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  18. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  19. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  20. 2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
  21. 2021Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learningcited by 14
  22. 2022Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimizationcited by 14
  23. 2022Latent Variable Representation for Reinforcement Learningcited by 14
  24. 2024PageRank Bandits for Link Predictioncited by 14
  25. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  26. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  27. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  28. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  29. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  30. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  31. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  32. 2023Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixturescited by 12
  33. 2023Quantum Bayesian Optimizationcited by 12
  34. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  35. 2022Improved Algorithms for Neural Active Learningcited by 11
  36. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
  37. 2024PAK-UCB Contextual Bandit: An Online Learning Approach to Prompt-Aware Selection of Generative Models and LLMscited by 11
  38. 2025Abacus: A Cost-Based Optimizer for Semantic Operator Systemscited by 11

50 most cited of 177 All 177 (JSON)