Weighted Gaussian Process Bandits for Non-stationary Environments
Weighted Gaussian Process Bandits for Non-stationary Environments
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Yuntian Deng-;Xingyu Zhou;Baekjin Kim;Ambuj Tewari;Abhishek Gupta;N. Shroff
中科院分区：
文献类型：
--
作者：
Yuntian Deng-;Xingyu Zhou;Baekjin Kim;Ambuj Tewari;Abhishek Gupta;N. Shroff
在本文中，我们考虑了非平稳环境中的高斯过程（GP）强盗优化问题。为了捕获外部更改，允许在复制的内核Hilbert Space（RKHS）中使用黑框函数。为此，我们开发了基于加权高斯过程回归的新型UCB型算法WGP-UCB。一个关键的挑战是如何应对无限维特征图。为此，我们利用内核近似技术证明了统一的遗憾，这是第一个（常见的）sublinear遗憾保证，并保证具有一般非线性奖励的加权时间变化的土匪。该结果概括了非平稳的线性匪徒和标准的GP-UCB算法。此外，对于用一般权重的加权高斯过程回归，还达到了新的浓度不等式。我们还提供了通用的上限和权重依赖性上限，以实现加权最大信息收益。对于新闻排名和自适应定价等应用程序，这些结果具有独立的兴趣，可以采用权重以捕获数据的重要性或质量。最后，与现有方法相比，在许多情况下，我们进行了实验，以强调所提出的算法的有利收益。
In this paper, we consider the Gaussian process (GP) bandit optimization problem in a non-stationary environment. To capture external changes, the black-box function is allowed to be time-varying within a reproducing kernel Hilbert space (RKHS). To this end, we develop WGP-UCB, a novel UCB-type algorithm based on weighted Gaussian process regression. A key challenge is how to cope with infinite-dimensional feature maps. To that end, we leverage kernel approximation techniques to prove a sublinear regret bound, which is the first (frequentist) sublinear regret guarantee on weighted time-varying bandits with general nonlinear rewards. This result generalizes both non-stationary linear bandits and standard GP-UCB algorithms. Further, a novel concentration inequality is achieved for weighted Gaussian process regression with general weights. We also provide universal upper bounds and weight-dependent upper bounds for weighted maximum information gains. These results are of independent interest for applications such as news ranking and adaptive pricing, where weights can be adopted to capture the importance or quality of data. Finally, we conduct experiments to highlight the favorable gains of the proposed algorithm in many cases when compared to existing methods.