提出新算法，让带噪函数优化更适应局部结构，提升学习效率。
Instance-dependent Stochastic Lipschitz bandit
- 基于水平集的子优性间隙积分，刻画函数局部生长特性。
- 当最优解集维数为d* > 0时，达到优于经典缩放边界的自适应率。
- 适用于需高效探索高维非凸函数的强化学习与优化任务。
研究在域 $\mathcal{X} \subset [0,1]^d$ 上通过带噪声点评估来序列最大化未知Lipschitz函数 $f$ 的问题。现有结果要么是最坏情况下的界，为 $\tilde{\Theta} \left( T^{d+1/d+2} \right)$，要么是基于缩放维数 $d_z$ 的自适应界，为 $\tilde{\Theta} \left( T^{d_z+1/d_z+2} \right)$。但这些缩放边界仅部分依赖实例，仅关注近优水平集的渐近增长，未能捕捉函数的精细结构。本文通过积分函数水平集上的子优性间隙，提供新分析与算法，使误差界能适应水平集的局部增长而非仅渐近行为。作为推论，当最大值集合维度 $d^\star > 0$ 时，获得改进的自适应率 $\tilde{\mathcal{O}} \left( T^{d_z+1 / \max(d_z,d^\star)+2} \right)$，严格优于经典缩放边界。最后，将分析扩展至全信息设置（Lipschitz专家），并放松部分正则性假设。
原文摘要 · Abstract (English)
We study the Lipschitz bandit problem, where a learner sequentially maximizes an unknown Lipschitz function $f$ over a domain $\mathcal{X} \subset [0,1]^d$ using noisy pointwise evaluations. Existing regret bounds are either worst-case, scaling as $\tildeΘ \left ( T^{d+1/d+2}\right )$, or adaptive via the zooming dimension $d_z$, yielding $\tildeΘ \left ( T^{d_z+1/d_z+2}\right )$. However, such zooming-based guarantees are only partially instance-dependent, as they depend solely on the asymptotic growth of near-optimal level sets and fail to capture finer structural properties of $f$. We provide an analysis and an algorithm that characterizes the regret through integrals of the suboptimality gap of $f$ over its level sets. This yields regret bounds that adapt to the local growth of level sets, rather than only their asymptotic behavior. As a corollary, when the set of maximizers has dimension $d^\star>0$, we obtain improved adaptive rates of order $\tilde{\mathcal{O}} \left ( T^{d_z+1 / \max(d_z,d^\star)+2}\right )$ strictly improving over classical zooming bounds in this regime. Finally, we extend our analysis to the full-information setting (Lipschitz experts) and show how some of the regularity assumptions can be relaxed.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。