Technical Summary: Near-Optimal Regret in Adversarial Kernel Bandits

1. Problem Formulation

The paper addresses the adversarial kernel bandit problem, a generalization of adversarial linear bandits where the loss functions belong to a Reproducing Kernel Hilbert Space (RKHS).

• Setting: In each round $t \in [T]$, a learner selects an action $x_t$ from a finite action set $\mathcal{X} \subset \mathbb{R}^d$. Simultaneously, an oblivious adversary selects a vector $w_t$ in the RKHS $\mathcal{H}$.
• Loss: The learner incurs a loss $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$, where $\Phi: \mathcal{X} \to \mathcal{H}$ is the feature map associated with a symmetric positive definite kernel $K$.
• Feedback: The learner observes only the scalar loss $\ell_t(x_t)$, not the vector $w_t$ or the full loss function.
• Goal: Minimize the expected regret $R_T$ against the best fixed action $x^*$ in hindsight:
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• Assumptions: The adversary is bounded ($\|w_t\|_{\mathcal{H}} \le B$), and the kernel is bounded ($K(x,x) \le 1$). Crucially, unlike prior work by Chatterji et al. [2019], the adversary is not restricted to rank-one losses (i.e., $w_t$ need not be of the form $\Phi(z_t)$); $w_t$ can be any element of $\mathcal{H}$ with bounded norm.

2. Methodology and Algorithm

The authors propose an algorithm based on Exponential Weights (Exp2) adapted for infinite-dimensional feature spaces. The core challenge is that standard importance-weighted estimators in linear bandits become unbounded when the feature map lies in an infinite-dimensional RKHS due to vanishing eigenvalues of the covariance operator.

To overcome this, the authors introduce two key modifications:

1. Regularized Importance-Weighted Estimator:
   Instead of inverting the empirical covariance operator $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$, the algorithm uses a ridge-regularized version $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$. The estimator is defined as:
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   This regularization ensures the estimator remains bounded even when $\Sigma_t$ has eigenvalues close to zero. However, this introduces a systematic bias: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$.

2. Explicit Bias Correction Term:
   To compensate for the regularization bias, the algorithm constructs a corrected loss proxy $\hat{\ell}_t(x)$:
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   where the correction term is $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$.

   • Mechanism: The correction term is derived directly from the closed-form bias expression. It acts as a pointwise upper bound on the bias, ensuring that the expected loss proxy underestimates the true loss for the comparator (the best fixed action). This structural choice ensures the comparator-side residual in the regret decomposition is non-positive, leaving only a controllable learner-side residual.

3. Exploration Strategy:
   The algorithm maintains a distribution $p_t$ that is a mixture of the current exponential weights distribution $q_t$ and a fixed exploration distribution $\nu_G$. The exploration distribution is chosen via a regularized G-optimal design to ensure the effective dimension is controlled.

3. Key Contributions

• Algorithm Design: A principled algorithm combining exponential weights with a regularized estimator and an explicit bias correction term. This approach avoids the restrictive rank-one adversary assumption required by Chatterji et al. [2019].
• Regret Analysis via Effective Dimension: The authors derive a regret bound dependent on the effective dimension $d^*(\lambda)$ of the kernel, defined as:
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• Removal of Rank-One Assumption: The framework allows for arbitrary bounded RKHS losses, significantly broadening the applicability compared to previous work that relied on projection-based estimators requiring rank-one constraints.

4. Main Results

The paper establishes a regret bound of the form:
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
where $d^*(\lambda)$ captures the complexity of the kernel. This rate matches the known optimal rates for the stochastic kernel bandit problem (up to logarithmic factors).

Specific Kernel Rates:

• Matérn$(\nu, d)$ Kernel: For a Matérn kernel with smoothness $\nu$ on $\mathbb{R}^d$, the effective dimension yields a regret bound of:
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  This improves upon the prior best-known rate of $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ by Chatterji et al. [2019] and matches the lower bound from concurrent work [Iwazaki, 2026] up to logarithmic factors. Notably, the prior rate was not even sublinear when $\nu < d/2$, whereas the new bound is always sublinear.
• Squared Exponential (SE) Kernel: The bound recovers the near-optimal $\tilde{O}(\sqrt{T})$ rate, matching Chatterji et al. [2019] but without the rank-one restriction.
• General Eigenvalue Decay:
  • Polynomial Decay ($\mu_j \le C j^{-\beta}$): Achieves $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$.
  • Exponential Decay ($\mu_j \le C e^{-\beta j}$): Achieves $R_T = \tilde{O}(\sqrt{T})$.

5. Significance and Claims

The paper claims to close the gap between adversarial and stochastic kernel bandit performance. Specifically:

• Optimality: The derived rates match the optimal rates known for stochastic kernel bandits (e.g., via SupKernelUCB or Bayesian optimization methods) up to logarithmic factors.
• Theoretical Advancement: By removing the rank-one adversary assumption, the results apply to a more general and realistic class of adversarial environments where the loss function is an arbitrary bounded element of the RKHS.
• Comparison to Prior Work: The work improves upon Chatterji et al. [2019] for Matérn kernels and general polynomial decay, providing tighter bounds that are sublinear in $T$ under conditions where the previous bounds were not.
• Concurrent Work: The authors acknowledge independent concurrent work by Iwazaki [2026] which achieves similar results using a closely related approach (exponential weights with regularized estimators and bias correction). The paper notes minor differences in problem setup (e.g., oblivious vs. adaptive adversary, specific complexity measures) but asserts the core algorithmic and analytical contributions are essentially equivalent.

The paper concludes that the proposed method provides a near-optimal solution to the adversarial kernel bandit problem, effectively handling the challenges of infinite-dimensional feature spaces through regularization and explicit bias correction.