首次建立时变核化老虎机问题的无算法下界，揭示优化极限。
Lower Bounds for Time-Varying Kernelized Bandits
- 基于函数范数的总变差约束，构建时变场景下通用下界
- 在ℓ∞范数下逼近已有上界，证明优化性能接近理论极限
- 提出开放问题：现有上界是否还能进一步改进
黑箱函数在噪声观测下的优化是广泛应用的基础问题，传统研究多假设函数属于再生核希尔伯特空间（RKHS）。尽管静态场景下已知近最优后悔界，但非平稳场景对某些应用至关重要，目前理解仍不充分。本文首次建立算法无关的下界，时间变化受特定函数范数的总变差预算约束。在ℓ∞范数下，所得下界与现有上界（Hong等, 2023）非常接近；在RKHS范数下，上下界仍较接近，但存在明显差距，引发一个关键开放问题：能否对上界进行非微小改进？
原文摘要 · Abstract (English)
The optimization of black-box functions with noisy observations is a fundamental problem with widespread applications, and has been widely studied under the assumption that the function lies in a reproducing kernel Hilbert space (RKHS). This problem has been studied extensively in the stationary setting, and near-optimal regret bounds are known via developments in both upper and lower bounds. In this paper, we consider non-stationary scenarios, which are crucial for certain applications but are currently less well-understood. Specifically, we provide the first algorithm-independent lower bounds, where the time variations are subject satisfying a total variation budget according to some function norm. Under $\ell_{\infty}$-norm variations, our bounds are found to be close to an existing upper bound (Hong et al., 2023). Under RKHS norm variations, the upper and lower bounds are still reasonably close but with more of a gap, raising the interesting open question of whether non-minor improvements in the upper bound are possible.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。