arXiv:2508.01681cs.LGstat.ML2025-08被引 6

提出新型核化贝叶斯优化算法,实现更优的后悔界控制。

Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds

  • 设计GKB-UCB算法,结合自适应正则化不等式处理非线性奖励模型。
  • 理论证明后悔上界为$ ilde{O}(γ_T oot{T/κ_*})$,对时间与信息增益最优。
  • 适用于核方法与广义线性场景,适合需高效探索的强化学习任务。

我们研究广义核化贝叶斯优化(GKB)中的后悔最小化问题,目标是优化一个属于再生核希尔伯特空间(RKHS)的未知函数 $f^*$,其观测来自均值为非线性函数 $μ(f^*)$ 的指数族(EF)奖励模型。该设置统一了核化贝叶斯(KBs)与广义线性贝叶斯(GLBs),并提出乐观后悔最小化算法 GKB-UCB。由于现有自正则化浓度不等式无法提供紧致后悔界,我们引入一种新的希尔伯特空间上自正则化伯努利型维度无关不等式,具有独立意义。基于此,我们分析 GKB-UCB,得到 $ ilde{O}(γ_T oot{T/κ_*})$ 的后悔界,其中 $T$ 为学习时长,$γ_T$ 为最大信息增益,$κ_*$ 表征期望奖励非线性程度。该结果在 $T$、$γ_T$、$κ_*$ 上均达到最优。进一步提出可计算版本 Trac-GKB-UCB,保持相近性能,并讨论其时空复杂度。

原文摘要 · Abstract (English)

We study the regret minimization problem in the novel setting of generalized kernelized bandits (GKBs), where we optimize an unknown function $f^*$ belonging to a reproducing kernel Hilbert space (RKHS) having access to samples generated by an exponential family (EF) reward model whose mean is a non-linear function $μ(f^*)$. This setting extends both kernelized bandits (KBs) and generalized linear bandits (GLBs), providing a unified view of both settings. We propose an optimistic regret minimization algorithm, GKB-UCB, and we explain why existing self-normalized concentration inequalities used for KBs and GLBs do not allow to provide tight regret guarantees. For this reason, we devise a novel self-normalized Bernstein-like dimension-free inequality that applies to a Hilbert space of functions with bounded norm, representing a contribution of independent interest. Based on it, we analyze GKB-UCB, deriving a regret bound of order $\widetilde{O}( γ_T \sqrt{T/κ_*})$, being $T$ the learning horizon, $γ_T$ the maximal information gain, and $κ_*$ a term characterizing the magnitude of the expected reward non-linearity. Our result is tight in its dependence on $T$, $γ_T$, and $κ_*$ for both KBs and GLBs. Finally, we present a tractable version GKB-UCB, Trac-GKB-UCB, which attains similar regret guarantees, and we discuss its time and space complexity.

贝叶斯优化在线学习核方法后悔界

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。