Delayed feedback in kernel bandits
File(s)
Accepted version
Author(s)
Vakili, Sattar
Ahmed, Danyal
Bernacchia, Alberto
Pike-Burke, Ciara
Type
Conference Paper
Abstract
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 O~(Γk(T)T−−−−−−√+E[τ]) regret, where T is the number of time steps, Γk(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 O~(Γk(T)T−−√+E[τ]Γk(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.
Date Issued
2023-07-23
Date Acceptance
2023-04-24
Citation
Proceedings of Machine Learning Research, 2023, 202, pp.34779-34792
ISSN
2640-3498
Publisher
ML Research Press
Start Page
34779
End Page
34792
Journal / Book Title
Proceedings of Machine Learning Research
Volume
202
Copyright Statement
Copyright © The authors and PMLR 2023. MLResearchPress.
Source
40th International Conference on Machine Learning
Publication Status
Published
Start Date
2023-07-23
Finish Date
2023-07-29
Coverage Spatial
Hawaii, USA