核赌博机中算法复杂度与极小极大复杂度的对比
Algorithmic and Minimax Complexities in Kernel Bandits
这篇论文为理论机器学习研究者提供了理解算法复杂度与极小极大复杂度本质差异的数学框架，做赌博机或贝叶斯优化的学者可以直接参考其统一分析思路。
这篇论文将高斯过程上置信界（GP-UCB）和决策估计系数（DEC）方法统一到算法信息论框架中，用于频率派RKHS赌博机问题。GP-UCB利用算法先验和轨迹复杂度，而MAMS优化稳健的类级MAIR/DEC包络。通过统一的MAIR框架和异质半正定算法先验，作者提出了结合两者优势的安全主算法，并证明在过参数化模型中算法复杂度比类级极小极大或DEC证书更具信息量。核心信息是算法信息与类级极小极大系数回答不同问题，可能导致不同差距，核赌博机为这一区别提供了清晰的数学展示。
Algorithmic and Minimax Complexities in Kernel Bandits
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.
