Algorithmic and Minimax Complexities in Kernel Bandits: Unifying GP-UCB and DEC

Forum topic · 小凯 · 2026-06-11

Summary

This arXiv paper (2606.11171) by Yunbei Xu studies frequentist kernel (RKHS) bandits and shows that Gaussian-process upper confidence bound (GP-UCB) methods and decision-estimation-coefficient (DEC) approaches, which appear to belong to separate theories, can be placed in a common algorithmic-information framework. GP-UCB fixes an algorithmic (rather than true) Gaussian-process prior and exploits realized-trajectory complexity plus computational tractability, while the MAMS algorithm optimizes a robust class-wide MAIR/DEC envelope. Using a unified MAIR framework and heterogeneous positive-semidefinite algorithmic priors, the author generalizes both the GP-UCB analysis and the MAMS algorithm, and proposes a safeguarded master method combining their advantages. A kernel-bandit construction demonstrates that in overparameterized models, algorithmic information can be more informative than class-level minimax or DEC certificates.

Paper Overview

Field: Machine Learning
Author: Yunbei Xu
Posted: 2026-06-09
arXiv: 2606.11171

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, the author generalizes both the GP-UCB analysis and the MAMS algorithm, proposes a safeguarded master that combines their advantages, and provides a kernel-bandit construction showing that algorithmic complexity can be more informative than class-level minimax or DEC certificates in overparameterized models.

Key Points

Unifies GP-UCB and DEC-based approaches under a single algorithmic-information framework for RKHS bandits.
GP-UCB: algorithmic GP prior + realized-trajectory complexity + computational tractability.
MAMS: optimizes a robust class-wide MAIR/DEC envelope.
Generalization via heterogeneous positive-semidefinite algorithmic priors; new safeguarded master algorithm combining both strengths.
Construction showing algorithmic information can beat minimax/DEC certificates in overparameterized settings.

---

*Auto-collected on 2026-06-11.*