Batched Kernelized Bandits: Refinements and Extensions

Authors	Chenkai Ma et al.
Year	2026
Field	Statistics / ML
arXiv	2603.12627
PDF	Download
Categories	stat.ML, cs.IT, cs.LG

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.

---

Engineering Breakdown

Plain English

This paper tackles black-box optimization where you get noisy feedback in batches rather than one sample at a time, and the true function lives in a Reproducing Kernel Hilbert Space (RKHS). The authors refine prior work by Li and Scarlett (2022) which showed O(log log T) batches are sufficient for near-optimal regret. They make two concrete improvements: (1) they pin down the exact optimal number of batches including constant factors, and (2) they remove an extra factor of B from the regret bound itself. This matters because it reduces both the number of sequential batch rounds needed and the total cumulative regret incurred during optimization.

Core Technical Contribution

The paper's main novelty is tightening two key bounds in the batched kernelized bandits framework. First, they characterize the optimal batch count more precisely than the log log T upper bound, including the hidden constants that matter in practice. Second, they introduce an improved regret analysis that eliminates a multiplicative factor of B (number of batches) that appeared in prior upper bounds, making the algorithm fundamentally more sample-efficient. The authors also extend lower bounds to cover a wider range of batch sizes, providing better algorithm-independent baselines for what is theoretically achievable. These are refinements of the existing Li-Scarlett framework rather than completely new algorithms, but they represent significant progress in understanding the fundamental limits of batch optimization.

How It Works

The framework operates as follows: at each round, the algorithm selects a batch of points to evaluate in parallel, receives noisy function values, and uses this batch of data to update its belief about the underlying function in the RKHS. The algorithm leverages kernel properties—specifically that functions with bounded RKHS norm can be well-approximated by a small number of basis functions—to guide exploration efficiently. The key technical insight is using optimism under uncertainty (confidence bounds) in the RKHS to balance exploration and exploitation across batches. The regret analysis decomposes into terms capturing (1) approximation error from finite basis, (2) estimation error from noisy observations, and (3) optimization error from discretization of the input space. By carefully tracking how information accumulates across batches and how many batches are needed before the algorithm can reliably narrow down the optimum, they derive both upper bounds (showing an algorithm that achieves certain regret) and lower bounds (proving no algorithm can do better).

Production Impact

In a real system doing sequential batch optimization—like hyperparameter tuning where you evaluate multiple candidates in parallel across a compute cluster—this work directly informs how many parallel rounds you need and how much total regret (suboptimality) to expect. Engineers can use the refined batch count analysis to determine whether it's worth waiting for a full batch to complete before launching the next round, versus proceeding with incomplete information; the tighter constants help make that trade-off concrete. The removed factor of B in regret means the algorithm gracefully handles batching without penalizing you heavily for parallelism, which is critical when batch size is large or forced by hardware constraints. However, the RKHS assumption requires kernel selection—you must choose or learn a kernel that reflects your problem structure, and if the true function doesn't actually have bounded RKHS norm in your chosen kernel, the guarantees break down. Implementation requires solving optimization subproblems (like maximum probability of improvement) in the RKHS, which can be computationally expensive in high dimensions, so this approach works best for low- to moderate-dimensional problems with 10-100 dimensions.

Limitations and When Not to Use This

The paper assumes the unknown function belongs to an RKHS with bounded norm—a strong structural assumption that may not hold for highly nonlinear or discontinuous problems common in real applications. While the batch size range for lower bounds is extended, there remain parameter regimes where the gap between upper and lower bounds is not fully closed, meaning the analysis is not completely tight. The approach scales poorly in dimension: the sample complexity and computational cost grow with the dimension of the input space, making it impractical for high-dimensional problems (>1000 dimensions) without additional structure or dimensionality reduction. The paper does not address settings where the batch size is adaptive or adversarially chosen, nor does it fully explore how to select the kernel in practice when the function class is unknown, leaving practitioners without clear guidance on that critical step.

Research Context

This work builds directly on Li and Scarlett (2022), which established that O(log log T) batches suffice for near-optimal regret in kernelized bandits—a breakthrough showing batching doesn't destroy asymptotic optimality. It extends the classical kernel-based bandit literature (e.g., Srinivas et al. 2009 on GP-UCB) into the practical batched setting where sequential rounds are expensive. The refinements contribute to a broader agenda of understanding fundamental limits and trade-offs in optimization under resource constraints (batch size, query budget, computation). This work opens the door to tighter analyses of other kernel-based learning problems and could inform future research on adaptive batch sizing or kernels that automatically adjust to the problem structure.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →