Batched Kernelized Bandits: Refinements and Extensions
Not on the map. Why?
Abstract (arXiv)
In this paper, we consider the problem of black-box optimization with noisy feedback revealed in batches, where the unknown function to optimize has a bounded norm in some Reproducing Kernel Hilbert Space (RKHS). We refer to this as the Batched Kernelized Bandits problem, and refine and extend existing results on regret bounds. For algorithmic upper bounds, (Li and Scarlett, 2022) shows that B=O(loglog T) batches suffice to attain near-optimal regret, where T is the time horizon and B is the number of batches. We further refine this by (i) finding the optimal number of batches including constant factors (to within 1+o(1)), and (ii) removing a factor of B in the regret bound. For algorithm-independent lower bounds, noticing that existing results only apply when the batch sizes are fixed in advance, we present novel lower bounds when the batch sizes are chosen adaptively, and show that adaptive batches have essentially same minimax regret scaling as fixed batches. Furthermore, we consider a robust setting where the goal is to choose points for which the function value remains high even after an adversarial perturbation. We present the robust-BPE algorithm, and show that a suitably-defined cumulative regret notion incurs the same bound as the non-robust setting, and derive a simple regret bound significantly below that of previous work.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 22 of its 42 references that are in the map. First posted on arXiv 13 Mar 2026.
Builds on
22 of 42 references.
References · 22
- 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
- 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
- 2019Batched Multi-armed Bandits Problemcited by 98
- 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
- 2018Adversarially Robust Optimization with Gaussian Processescited by 62
- 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
- 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
- 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
- 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
- 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
- 2019Regret Bounds for Batched Banditscited by 49
- 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
10 more
- 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
- 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
- 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 31
- 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
- 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 17
- 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
- 2020Distributionally Robust Bayesian Quadrature Optimizationcited by 15
- 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
- 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
- 2020Mixed Strategies for Robust Optimization of Unknown Objectivescited by 8
Built on by
Citing papers per year: 2026: 3.
3 papers.