提出新算法，高效解决随时间变化的优化问题。
Near-Optimal Algorithm for Non-Stationary Kernelized Bandits
- 设计基于随机排列的重启分段消除算法
- 首次实现非平稳核函数下的近优上界匹配下界
- 适合需要实时适应变化环境的研究者
本文研究非平稳核化贝叶斯强化学习（非平稳核化带宽，KB）问题，即在随时间变化的未知奖励函数下最小化累计遗憾。针对该问题，我们首次建立了不依赖具体算法的后悔下界，适用于平方指数和Matérn核函数。结果表明，对现有基于优化的算法稍作修改即可达到近最优性能。然而，该方法因计算成本过高而难以实际应用。为此，我们提出一种名为重启分段消除与随机排列（R-PERP）的新算法，有效规避了高昂的计算开销。其核心技术在于查询候选点的简单排列机制，使得可推导出专为非平稳问题设计的更紧致置信区间。
原文摘要 · Abstract (English)
This paper studies a non-stationary kernelized bandit (KB) problem, also called time-varying Bayesian optimization, where one seeks to minimize the regret under an unknown reward function that varies over time. In particular, we focus on a near-optimal algorithm whose regret upper bound matches the regret lower bound. For this goal, we show the first algorithm-independent regret lower bound for non-stationary KB with squared exponential and Matérn kernels, which reveals that an existing optimization-based KB algorithm with slight modification is near-optimal. However, this existing algorithm suffers from feasibility issues due to its huge computational cost. Therefore, we propose a novel near-optimal algorithm called restarting phased elimination with random permutation (R-PERP), which bypasses the huge computational cost. A technical key point is the simple permutation procedures of query candidates, which enable us to derive a novel tighter confidence bound tailored to the non-stationary problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。