arXiv：cs.LG· Chenkai Ma, Jonathan Scarlett·· 3 小时前
核赌博机问题的一般 Ω̃(√(T γ_T)) 下界
A General $\widetilde{\Omega}(\sqrt{T \gamma_T})$ Lower Bound for Kernel Bandits
AI 导读
该论文为紧致域上的非恒定连续核建立了通用 Ω(√(Tγ_T/log T)) minimax 遗憾下界，证明现有上界在极一般意义上已达近最优（仅差 log 因子）。
正文
Abstract:The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain $\gamma_T$. In particular, the best existing upper bounds scale as $\sqrt{T\gamma_T}$ up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general $\Omega(\sqrt{T\gamma_T/\log T})$ minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly $\Theta(\sqrt{T\gamma_T})$ (i.e., within constant factors) for the Matérn-$\nu$ kernel with $\nu \in (0,2)$, $\gamma$-exponential kernel with $\gamma \in (0,2)$, and certain piecewise-polynomial kernels.
| Subjects: | Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.11082 [stat.ML] |
| (or arXiv:2610.11082v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.11082 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Chenkai Ma [view email]
[v1]
Thu, 8 Oct 2026 01:44:31 UTC (38 KB)
来源：arXiv：cs.LG · arxiv.org