Lower Bounds for Time-Varying Kernelized Bandits
This work addresses the less understood non-stationary setting in kernelized bandits, which is crucial for applications requiring adaptation to changing environments, representing an incremental theoretical advancement.
The paper tackles the problem of optimizing black-box functions with noisy observations in non-stationary scenarios, providing the first algorithm-independent lower bounds for time-varying kernelized bandits under total variation budgets, with results showing closeness to existing upper bounds under ℓ∞-norm variations and a gap under RKHS norm variations.
The optimization of black-box functions with noisy observations is a fundamental problem with widespread applications, and has been widely studied under the assumption that the function lies in a reproducing kernel Hilbert space (RKHS). This problem has been studied extensively in the stationary setting, and near-optimal regret bounds are known via developments in both upper and lower bounds. In this paper, we consider non-stationary scenarios, which are crucial for certain applications but are currently less well-understood. Specifically, we provide the first algorithm-independent lower bounds, where the time variations are subject satisfying a total variation budget according to some function norm. Under $\ell_{\infty}$-norm variations, our bounds are found to be close to an existing upper bound (Hong et al., 2023). Under RKHS norm variations, the upper and lower bounds are still reasonably close but with more of a gap, raising the interesting open question of whether non-minor improvements in the upper bound are possible.