Algorithmic and Minimax Complexities in Kernel Bandits
2026-06-09 • Machine Learning
Machine LearningInformation Theory
AI summaryⓘ
The authors compare two approaches for making decisions in learning tasks that involve predicting unknown functions: GP-UCB and DEC. They show both can be explained using a common language based on algorithmic information, which helps understand their differences and strengths. They then combine these ideas to create a new method that benefits from both approaches. Their work also provides an example where simpler algorithmic complexity measures can be more useful than traditional broad guarantees in complex models.
Gaussian ProcessUpper Confidence Bound (UCB)Decision-Estimation-Coefficient (DEC)RKHS BanditsAlgorithmic InformationMinimax AnalysisKernel MethodsBandit AlgorithmsOverparameterization
Authors
Yunbei Xu
Abstract
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.