提出对抗环境下近似最优的核化强化学习算法
Nearly-Optimal Algorithm for Adversarial Kernelized Bandits
- 使用指数权重策略实现近似最优后悔率
- 在平方指数和ν-马特恩核下达到理论最优性
- 结合奈斯特伦近似提升计算效率，适合大规模应用
本文研究对抗环境下的核化随机搜索（即高斯过程带宽），其中奖励函数属于已知再生核希尔伯特空间（RKHS），每轮可被敌对选择。我们证明指数权重算法可实现$ ilde{O}( ext{sqrt}{T γ_T})$的对抗后悔率，其中$T$为总轮数，$γ_T$为最大信息增益。对于平方指数（SE）和$ν$-马特恩核，我们还给出了算法无关的下界，表明所提算法在多对数因子内达到最优。此外，我们提出一种基于奈斯特伦近似的高效变体，在保持近似最优后悔率的同时显著降低计算开销。
原文摘要 · Abstract (English)
This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves $\tilde{O}(\sqrt{T γ_T})$ adversarial regret, where $T$ and $γ_T$ denote the number of total rounds and the maximum information gain, respectively. For squared exponential (SE) and $ν$-Matérn kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nyström approximation while maintaining nearly optimal regret guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。