证明了无噪声高斯过程上置信界算法近乎最优的后悔上界。
Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits
- 基于高斯过程上置信界选择查询点，实现自适应优化。
- 首次在平方指数和马特恩核下获得常数累积后悔。
- 理论结果解释了其实际表现优于其他近优算法的原因。
研究无噪声高斯过程（GP）带宽问题，学习者通过无噪声观测黑箱目标函数，该函数属于已知再生核希尔伯特空间（RKHS）。高斯过程上置信界（GP-UCB）是一种经典算法，其查询点基于基于高斯过程的上置信界得分自适应选择。尽管已有工作报告了GP-UCB的实践成功，但现有理论表明其性能次优。然而，相比依赖非自适应采样方案的其他近优算法，GP-UCB在实践中表现更佳。本文通过分析证明了无噪声环境下GP-UCB的近乎最优后悔上界，具体而言，首次在平方指数核与某些光滑度的马特恩核设定下，获得了常数级累积后悔。
原文摘要 · Abstract (English)
We study the noise-free Gaussian Process (GP) bandits problem, in which the learner seeks to minimize regret through noise-free observations of the black-box objective function lying on the known reproducing kernel Hilbert space (RKHS). Gaussian process upper confidence bound (GP-UCB) is the well-known GP-bandits algorithm whose query points are adaptively chosen based on the GP-based upper confidence bound score. Although several existing works have reported the practical success of GP-UCB, the current theoretical results indicate its suboptimal performance. However, GP-UCB tends to perform well empirically compared with other nearly optimal noise-free algorithms that rely on a non-adaptive sampling scheme of query points. This paper resolves this gap between theoretical and empirical performance by showing the nearly optimal regret upper bound of noise-free GP-UCB. Specifically, our analysis shows the first constant cumulative regret in the noise-free settings for the squared exponential kernel and Matérn kernel with some degree of smoothness.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。