核赌博机遗憾下界大突破：首次对一般核证明接近最优，Matérn等核达Θ(√Tγ_T)！
A General $\widetilde{\Omega}(\sqrt{T \gamma_T})$ Lower Bound for Kernel Bandits
📖 AI 总结
本文研究核赌博机（kernel bandits）问题，即在再生核希尔伯特空间中序贯优化未知函数并承受噪声反馈。该问题的遗憾分析核心量是最大信息增益γ_T，已有最优上界在忽略对数因子时按√(Tγ_T)增长，且针对平方指数核、Matérn核等特定核已有近乎匹配的下界，但一般核的下界一直缺失，导致上界的普适最优性不明。本文针对紧致域上的非恒定连续核，建立了通用的Ω(√(Tγ_T/log T))极小极大遗憾下界，证明上界在非常一般的意义下已达到近乎最优（相差对数因子）。作者进一步指出该对数因子在一般情况下不可避免，但在特定条件下可去除。这一结果意味着，对于ν∈(0,2)的Matérn-ν核、γ∈(0,2)的γ指数核以及某些分段多项式核，极小极大最优尺度恰为Θ(√(Tγ_T))，即在常数因子内精确匹配。该工作填补了一般核下界理论的空白，明确了核赌博机遗憾最优性的适用范围。
🔑 关键词速览
| 核赌博机 | 一种序列决策问题，在噪声反馈下优化未知函数，函数属于再生核希尔伯特空间。 |
| 最大信息增益 | 衡量在T轮中通过观测获得的最大信息量，常用于核赌博机的遗憾分析。 |
| 再生核希尔伯特空间 | 一种函数空间，具有再生核性质，常用于非参数统计和机器学习。 |
| 极小极大遗憾 | 衡量算法在最坏情况下的性能损失，是衡量算法最优性的标准。 |
| Matérn核 | 一种常用的平稳核函数，参数ν控制平滑度，广泛应用于高斯过程。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅