Batched Kernelized Bandits: Refinements and Extensions

Chenkai Ma; Keqin Chen; Jonathan Scarlett

stat.MLMar 13, 2026

Batched Kernelized Bandits: Refinements and Extensions

Authors: Chenkai Ma, Keqin Chen, Jonathan Scarlett

Organizations: National University of Singapore

Abstract

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(\log\log 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.

Figures & tables

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: Illustration of a class of hard-to-distinguish functions

\mathcal{F}

, where any

x\in\mathcal{X}

can be

\epsilon

-optimal for at most one bump function. This is an “idealized” illustration, with the actual functions used having infinite support but steady decay to zero.

Panel of Figure 2 — Figure 2: Synthetic functions sampled using different kernels.

Algorithm	$T=200$	$T=400$	$T=600$	$T=800$	$T=1000$
BPE (Orig, $B=4$ )	114.69	140.67	164.22	181.67	197.91
BPE ( $a=0.52$ , $B=4$ )	137.54	160.83	182.23	196.4	210.57
BPE ( $a=0.6$ , $B=5$ )	118.99	132.6	141.08	148.74	154.76
BPE ( $a=0.65$ , $B=6$ )	111.08	127.25	139.05	148.69	158.05

Appendix

Table 1: Cumulative regret of BPE using different batch sizes and the SE kernel.

Algorithm	$T=200$	$T=400$	$T=600$	$T=800$	$T=1000$
BPE (Orig, $B=4$ )	255.09	344.66	428.34	471.35	505.8
BPE ( $a=0.31$ , $B=3$ )	367.95	471.04	574.1	630.37	677.65
BPE ( $a=0.4$ , $B=3$ )	254.45	344.24	384.13	424.07	464.1
BPE ( $a=0.5$ , $B=4$ )	254.31	334.58	409.87	443.63	469.56

Appendix

Table 2: Cumulative regret of BPE using different batch sizes and the Matérn kernel (

\nu=1.5

Algorithm	$T=200$	$T=400$	$T=600$	$T=800$	$T=1000$
BPE (Orig, $B=4$ )	210.2	260.35	305.59	317.21	321.77
BPE ( $a=0.36$ , $B=3$ )	226.77	246.05	256.91	260.48	264.06
BPE ( $a=0.4$ , $B=3$ )	192.91	218.55	220.44	222.34	224.23
BPE ( $a=0.5$ , $B=3$ )	222.34	261.57	294.47	304.41	310.01

Appendix

Table 3: Cumulative regret of BPE using different batch sizes and the Matérn kernel (

\nu=2.5

Explore similar work

May 11, 2026

Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves

\tilde{O}(\sqrt{T γ_T})

adversarial regret, where

T

and

γ_T

denote the number of total rounds and the maximum information gain, respectively. For squared exponential (SE) and

ν

-Matérn kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nyström approximation while maintaining nearly optimal regret guarantees.

Shogo Iwazaki

LY Corporation Tokyo, Japan

Multi-Armed Bandits Adversarial Bandits

Ask PDF

May 26, 2026

Near-Optimal Regret in Adversarial Kernel Bandits

We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose an exponential-weights algorithm built on a regularized importance-weighted loss estimator, together with an explicit correction term that cancels the bias introduced by the regularization. Our main result bounds the regret by

\widetilde{O}\big(\sqrt{T\, d_*(λ)\,\log|{X}|}\big)

, where

d_*(λ)

is a widely-adopted notion of effective dimension that captures the complexity of the kernel. Up to logarithmic factors, this matches the known rate achieved in the related stochastic kernel bandit problem. A notable application is the Matérn

(ν,d)

kernel with smoothness parameter

ν

\mathbb{R}^d

, for which our bound specializes to

\widetilde{O}\big(T^{(ν+d)/(2ν+d)}\big)

, improving over the best-known prior rate of Chatterji et al. [2019] while simultaneously removing the rank-one adversary assumption required by their analysis. Moreover, this rate is the same as the known optimal rate for stochastic kernel bandits, and also matches a lower bound from concurrent work up to a

\log T

factor.

Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett +1

National University of Singapore

Kernel Methods Adversarial Bandits

Ask PDF

Oct 8, 2026

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain

γ_T

. In particular, the best existing upper bounds scale as

\sqrt{Tγ_T}

up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general

Ω(\sqrt{Tγ_T/\log T})

minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly

Θ(\sqrt{Tγ_T})

(i.e., within constant factors) for the Matérn-

ν

kernel with

ν\in (0,2)

γ

-exponential kernel with

γ\in (0,2)

, and certain piecewise-polynomial kernels.

Chenkai Ma, Jonathan Scarlett

National University of Singapore

Minimax Regret Multi-Armed Bandits Information-Theoretic Lower Bounds

Ask PDF

Abstract

Explore similar work

Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

Near-Optimal Regret in Adversarial Kernel Bandits

A General Ω~(TγT)\widetildeΩ(\sqrt{T γ_T})Ω(TγT​​) Lower Bound for Kernel Bandits

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits