# Delayed Feedback in Kernel Bandits

arXiv: https://arxiv.org/abs/2302.00392 · HTML: https://mlsanity.com/paper/2302.00392/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 29 references that are in the map.
- First posted on arXiv 1 Feb 2023.

## Builds on (most cited first, 18 of 18)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [On Batch Bayesian Optimization](https://mlsanity.com/paper/1911.01032/) (2019)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)

## Built on by (most cited first, 10 of 10)

- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [Active Learning for Level Set Estimation Using Randomized Straddle Algorithms](https://mlsanity.com/paper/2408.03144/) (2024)
- [Biased Dueling Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2408.14603/) (2024)
- [A Contextual Combinatorial Bandit Approach to Negotiation](https://mlsanity.com/paper/2407.00567/) (2024)
- [Leveraging semantic similarity for experimentation with AI-generated treatments](https://mlsanity.com/paper/2510.21119/) (2025)
- [Lipschitz Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/2510.00309/) (2025)
- [Batched Stochastic Linear Bandits with 1-Bit Communication Constraints](https://mlsanity.com/paper/2605.30976/) (2026)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Kernel ε-Greedy for Multi-Armed Bandits with Covariates](https://mlsanity.com/paper/2306.17329/) (2023)

## Abstract (arXiv)

Black box optimisation of an unknown function from expensive and noisy evaluations is a ubiquitous problem in machine learning, academic research and industrial production. An abstraction of the problem can be formulated as a kernel based bandit problem (also known as Bayesian optimisation), where a learner aims at optimising a kernelized function through sequential noisy observations. The existing work predominantly assumes feedback is immediately available; an assumption which fails in many real world situations, including recommendation systems, clinical trials and hyperparameter tuning. We consider a kernel bandit problem under stochastically delayed feedback, and propose an algorithm with tildeO(√Gammak(T)T+mathbbE[τ]) regret, where T is the number of time steps, Gammak(T) is the maximum information gain of the kernel with T observations, and τ is the delay random variable. This represents a significant improvement over the state of the art regret bound of tildeO(Gammak(T)√T+mathbbE[τ]Gammak(T)) reported in Verma et al. (2022). In particular, for very non-smooth kernels, the information gain grows almost linearly in time, trivializing the existing results. We also validate our theoretical results with simulations.