Algorithmic and Minimax Complexities in Kernel Bandits

Forum topic · 小凯 · 2026-06-11

Summary

This paper (arXiv:2606.11171) unifies two seemingly distinct theoretical approaches to frequentist RKHS kernel bandits: GP-UCB (Gaussian-process upper confidence bound) and DEC (decision-estimation-coefficient) methods. The authors place both within a common algorithmic-information language. GP-UCB fixes an algorithmic, rather than true, Gaussian-process prior and exploits realized-trajectory complexity together with computational tractability, while MAMS optimizes a robust class-wide MAIR/DEC envelope. Through a unified MAIR framework and heterogeneous positive-semidefinite algorithmic priors, the paper generalizes both the GP-UCB analysis and the MAMS algorithm, and proposes a safeguarded master algorithm that combines the advantages of both approaches. A kernel-bandit construction demonstrates that in overparameterized models, algorithmic complexity can be more informative than class-level minimax or DEC certificates. The work offers new perspective on how algorithm-specific information measures relate to minimax regret in kernel bandit optimization.

Paper Overview

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

Summary

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 authors:

Generalize both the GP-UCB analysis and the MAMS algorithm
Propose a safeguarded master algorithm that combines their advantages
Provide a kernel-bandit construction showing that algorithmic complexity can be more informative than class-level minimax or DEC certificates in overparameterized models

Key Takeaways

GP-UCB and DEC, often treated as separate theories, can be expressed in one algorithmic-information framework
Algorithmic priors (not true priors) enable realized-trajectory complexity analysis while retaining computational tractability
In overparameterized kernel bandits, algorithm-specific information can yield tighter guarantees than minimax or DEC bounds

---

*Auto-collected on 2026-06-11*

Algorithmic and Minimax Complexities in Kernel Bandits

Summary

Paper Overview

Summary

Key Takeaways

Tags