提出新算法，实现对抗性核函数强化学习的近最优后悔率。
Near-Optimal Regret in Adversarial Kernel Bandits
- 用正则化重要性加权估计器结合显式修正项消除偏差。
- 后悔率达$ ilde{O}(\ oot{T d_*(λ) \log|X|}$)，接近理论最优。
- 适用于光滑核如Matérn，且无需假设对手为秩一扰动。
研究对抗性核函数强化学习问题，其中每轮损失由再生核希尔伯特空间（RKHS）中的任意有界元素诱导。提出一种基于指数权重的算法，结合正则化重要性加权损失估计器，并引入显式修正项以消除正则化带来的偏差。主要结果表明，后悔率上界为$ ilde{O}(\ oot{T bsp;d_*(λ) bsp;\log|{X}|}$)，其中$d_*(λ)$是衡量核复杂度的常用有效维度。在对数因子内，该结果与相关随机核强化学习问题的已知最优率一致。特别地，对于$R^d$上的Matérn$(ν,d)$核，其后悔率退化为$ ilde{O}(T^{(ν+d)/(2ν+d)})$，优于此前Chatterji等[2019]的最优率，同时不再需要其分析中依赖的秩一对手假设。该速率与随机核强化学习的已知最优率一致，并与同期工作给出的下界仅差$\ ext{log} bsp{T}$因子。
原文摘要 · Abstract (English)
We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose an exponential-weights algorithm built on a regularized importance-weighted loss estimator, together with an explicit correction term that cancels the bias introduced by the regularization. Our main result bounds the regret by $\widetilde{O}\big(\sqrt{T\, d_*(λ)\,\log|{X}|}\big)$, where $d_*(λ)$ is a widely-adopted notion of effective dimension that captures the complexity of the kernel. Up to logarithmic factors, this matches the known rate achieved in the related stochastic kernel bandit problem. A notable application is the Matérn$(ν,d)$ kernel with smoothness parameter $ν$ on $\mathbb{R}^d$, for which our bound specializes to $\widetilde{O}\big(T^{(ν+d)/(2ν+d)}\big)$, improving over the best-known prior rate of Chatterji et al. [2019] while simultaneously removing the rank-one adversary assumption required by their analysis. Moreover, this rate is the same as the known optimal rate for stochastic kernel bandits, and also matches a lower bound from concurrent work up to a $\log T$ factor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。