Batched Kernelized Bandits: Refinements and Extensions

1. Problem Statement

The paper addresses the Batched Kernelized Bandits problem, a variation of black-box optimization where:

• Objective: Maximize an unknown function $f: \mathcal{X} \to \mathbb{R}$ over a domain $\mathcal{X} \subseteq [0,1]^d$.
• Assumptions: The function $f$ belongs to a Reproducing Kernel Hilbert Space (RKHS) with a bounded norm $\|f\|_k \le \Psi$. The observations are noisy: $y_t = f(x_t) + z_t$, where $z_t \sim \mathcal{N}(0, \sigma^2)$.
• Batch Constraint: Observations are not revealed immediately after querying a point. Instead, the algorithm selects a batch of points, queries them, and receives all noisy responses only at the end of the batch.
• Settings:
  • Fixed Batches: Batch sizes and boundaries are predetermined before the process starts.
  • Adaptive Batches: The size of the next batch is determined based on observations from previous batches.
  • Robust Setting: The goal is to find a point $x$ that maximizes the function value even under an adversarial perturbation $\delta$ (i.e., maximize $\min_{\delta} f(x+\delta)$).

The primary metric is cumulative regret $R_T = \sum_{t=1}^T (f(x^*) - f(x_t))$, where $x^*$ is the global maximizer. The paper focuses on minimizing the number of batches $B$ required to achieve near-optimal regret scaling of $O^*(\sqrt{T \gamma_T})$, where $\gamma_T$ is the maximum information gain.

2. Methodology

A. Refined Upper Bounds (Standard Setting)

The authors refine the Batched Pure Exploration (BPE) algorithm introduced by Li and Scarlett (2022).

• Algorithm: BPE maintains a set of candidate maximizers. In each batch, it samples points with the highest posterior variance (maximum uncertainty) and eliminates suboptimal points at the end of the batch using tight confidence bounds derived from Vakili et al. (2021a).
• Batch Size Generalization: Instead of the specific batch size rule $N_i = \min(\lceil \sqrt{T N_{i-1}} \rceil, \dots)$ used previously, the authors propose a generalized rule:
  $$N_i = \min \left( \lceil T^{1-ai} \rceil, T - \sum_{j=1}^{i-1} N_j \right)$$
  where $a \in (0, 1)$ is a tunable parameter.
  • $a=1/2$ recovers the original Li & Scarlett setting.
  • $a \to 1$ approaches fully sequential learning.
  • $a \to 0$ approaches a single-batch setting.
• Analysis: By optimizing $a$, the authors derive the exact number of batches required to achieve near-optimal regret, removing a multiplicative factor of $B$ present in previous bounds.

B. Algorithm-Independent Lower Bounds

The paper establishes novel lower bounds for adaptive batches, a gap in previous literature which only covered fixed batches.

• Technique: The authors employ a "change of measure" argument. They construct $B$ families of "hard" functions, where each family is designed to be difficult for a specific batch index $i$ if that batch is "bad" (i.e., starts too early or ends too late).
• Key Insight: They prove that even with adaptive batch sizes, the minimax regret scaling is essentially the same as for fixed batches. The lower bounds show that adaptive batches do not offer a significant advantage in the minimax sense, provided $B = O(\log \log T)$.

C. Robust Setting Extension

The authors extend the framework to adversarially robust optimization.

• Algorithm: They propose Robust-BPE, which modifies the exploration set to include all possible perturbations of the current candidates ($X_{\xi, i} = \cup_{x \in X_i} \{x + \delta : \delta \in \Delta_\xi(x)\}$).
• Regret Definition: They define a cumulative $\xi$-regret that measures the loss relative to the worst-case perturbation of the optimal point.
• Result: They show that Robust-BPE achieves the same cumulative regret bounds as the standard setting and significantly improves the simple regret bound compared to prior work (Bogunovic et al., 2018).

3. Key Contributions

1. Optimal Batch Count Refinement:

   • The paper identifies the optimal number of batches (up to $1+o(1)$) to achieve near-optimal regret.
   • They show that for the Matérn kernel, the optimal number of batches depends on the smoothness parameter $\nu$ and dimension $d$ (specifically $B \approx \log_{1/\eta} \log_2 T$ where $\eta = \nu/(2\nu+d)$), whereas previous work suggested a fixed $O(\log \log T)$ regardless of kernel properties.
   • Removal of Factor $B$: The new regret bound removes the unnecessary multiplicative factor of $B$ found in Li and Scarlett (2022), resulting in a tighter bound: $O((\Lambda + \sqrt{\log \log \log T})\sqrt{T \gamma_T})$.

2. Adaptive Batch Lower Bounds:

   • First derivation of lower bounds for adaptive batch sizes in kernelized bandits.
   • Proves that adaptive batches are not more powerful than fixed batches in the minimax sense; both require $B = \Omega(\log \log T)$ to achieve near-optimal regret.

3. Robust Optimization Extension:

   • Introduces Robust-BPE for adversarial settings.
   • Achieves cumulative regret matching the non-robust setting.
   • Derives a simple regret bound of $O^*(\sqrt{\gamma_T/T})$, which improves upon the previous $O^*(\gamma_T/\sqrt{T})$ bound by removing an unnecessary $\sqrt{\gamma_T}$ factor.

4. Results

• Upper Bounds:

  • For SE Kernel: With $B = O(\log \log T)$, the algorithm achieves $O^*(\sqrt{T \gamma_T})$ regret.
  • For Matérn Kernel: The optimal $B$ scales as $\log_{1/\eta} \log_2 T$. The regret bound is $O^*(\sqrt{T \gamma_T})$.
  • The bounds hold for both fixed and adaptive batches (in terms of achievability).

• Lower Bounds:

  • For adaptive batches, the expected cumulative regret is lower bounded by $\Omega(B^{-2} T^{\frac{1-\eta}{1-\eta B}} (\log T)^{\dots})$ for SE kernels and $\Omega(B^{-(2\eta+1)} T^{\frac{1-\eta}{1-\eta B}})$ for Matérn kernels.
  • These bounds confirm that reducing $B$ below $O(\log \log T)$ leads to a significant degradation in regret (super-linear or non-sublinear).

• Experiments:

  • Synthetic experiments on 2D functions with SE and Matérn kernels validate the theory.
  • Results show that tuning the parameter $a$ (and thus the batch sizes) can reduce the number of batches $B$ while maintaining or improving cumulative regret compared to the original fixed-size strategy.

5. Significance

• Theoretical Tightness: The paper closes the gap between upper and lower bounds for batched kernelized bandits, providing the first precise characterization of the optimal number of batches including constant factors.
• Practical Efficiency: By showing that fewer batches are sufficient for harder problems (Matérn with low $\nu$), the work offers practical guidelines for parallelizing expensive experiments (e.g., in hyperparameter tuning or clinical trials) without sacrificing optimality.
• Robustness: The extension to robust settings provides a theoretically sound method for optimizing systems subject to adversarial noise or perturbations, improving upon existing simple regret guarantees.
• Adaptivity vs. Fixed: The finding that adaptive batches offer no minimax advantage simplifies the design of batched algorithms, suggesting that pre-specified batch schedules are sufficient for optimal performance.