Gaussian Process Bandit Optimization with Few Batches
Gaussian Process Bandit Optimization with Few Batches
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Zihan Li;J. Scarlett
中科院分区：
文献类型：
--
作者：
Zihan Li;J. Scarlett
在这篇文章中，我们考虑了使用高斯过程(GP)的小批量黑箱优化问题。假设未知函数在再生核Hilbert空间(RKHS)中具有低范数，我们引入了一种受批处理有限臂Bandit算法启发的批处理算法，并证明了它在时间域$T$内使用$O(\log\log T)$批处理获得了累积遗憾上限$O^\ast(\SQRT{T\Gamma_T})$，其中$O^\ast(\CDOT)$记号隐藏了与维度无关的对数因子，$\Gamma_T$是与核相关的最大信息增益.对于几个感兴趣的核，这个界是接近最优的，并且改进了典型的$O^ast(\SQRT{T}\Gamma_T)$界，而我们的方法可以说是实现这种改进的算法中最简单的。此外，在批次数不变(不依赖于$T$)的情况下，我们提出了一种改进的算法，并刻画了批次数对遗憾的影响，重点研究了平方指数核和Mat‘ern核，通过类似的算法无关的下界，证明了算法的上界是近似极小极大最优的。
In this paper, we consider the problem of black-box optimization using Gaussian Process (GP) bandit optimization with a small number of batches. Assuming the unknown function has a low norm in the Reproducing Kernel Hilbert Space (RKHS), we introduce a batch algorithm inspired by batched finite-arm bandit algorithms, and show that it achieves the cumulative regret upper bound $O^\ast(\sqrt{T\gamma_T})$ using $O(\log\log T)$ batches within time horizon $T$, where the $O^\ast(\cdot)$ notation hides dimension-independent logarithmic factors and $\gamma_T$ is the maximum information gain associated with the kernel. This bound is near-optimal for several kernels of interest and improves on the typical $O^\ast(\sqrt{T}\gamma_T)$ bound, and our approach is arguably the simplest among algorithms attaining this improvement. In addition, in the case of a constant number of batches (not depending on $T$), we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches, focusing on the squared exponential and Mat\'ern kernels. The algorithmic upper bounds are shown to be nearly minimax optimal via analogous algorithm-independent lower bounds.