[Paper] Algorithmic and Minimax Complexities in Kernel Bandits

Source: arXiv - 2606.11171v1

Overview

Gaussian-process upper confidence bound (GP-UCB) and decision-estimation-coefficient (DEC) methods may appear, at first sight, to belong to different theories. This paper places the two viewpoints in a common algorithmic-information language for frequentist RKHS bandits. GP-UCB fixes an algorithmic, rather than true, Gaussian-process prior and exploits realized-trajectory complexity together with computational tractability, whereas MAMS optimizes a robust class-wide MAIR/DEC envelope. Through the unified MAIR framework and heterogeneous positive-semidefinite algorithmic priors, we generalize both the GP-UCB analysis and the MAMS algorithm, propose a safeguarded master that combines their advantages, and provide a kernel-bandit construction showing that algorithmic complexity can be more informative than class-wide minimax or DEC certificates in overparameterized models. The resulting message is that algorithmic information and class-wide minimax coefficients answer different questions and can lead to different gaps; kernel bandits provide a clean setting in which this distinction becomes mathematically visible.

Key Contributions

This paper presents research in the following areas:

• cs.LG
• cond-mat.stat-mech
• cs.IT
• math.OC
• math.ST

Methodology

Please refer to the full paper for detailed methodology.

Practical Implications

This research contributes to the advancement of cs.LG.

Authors

• Yunbei Xu

Paper Information

• arXiv ID: 2606.11171v1
• Categories: cs.LG, cond-mat.stat-mech, cs.IT, math.OC, math.ST
• Published: June 9, 2026
• PDF: Download PDF