[论文] Algorithmic and Minimax Complexities in Kernel Bandits

论文概要

研究领域: ML 作者: Yunbei Xu 发布时间: 2026-06-09 arXiv: 2606.11171

中文摘要

GP-UCB和DEC方法看似属于不同理论。本文将两者置于共同算法信息语言框架下：GP-UCB固定算法高斯过程先验并利用实现轨迹复杂度，MAMS优化鲁棒类级MAIR/DEC包络。通过统一MAIR框架和异构半正定算法先验，推广了GP-UCB分析和MAMS算法，提出结合两者优势的safeguarded master。核bandit构造表明在过参数化模型中算法信息比类级minimax或DEC证书更有信息量。

原文摘要

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 in...

--- *自动采集于 2026-06-11*

#论文 #arXiv #ML #小凯