论文标题
布朗运动的嘈杂优化的紧密遗憾界限
Tight Regret Bounds for Noisy Optimization of a Brownian Motion
论文作者
论文摘要
我们考虑了贝叶斯优化一维的布朗尼运动的问题，其中$ t $自适应地选择的观察结果被高斯噪音损坏。我们表明，作为最小的预期累积遗憾和最小的预期简单遗憾量表为$ω（σ\ sqrt {t / \ log（t）}）\ cap \ cap \ mathcal {o}（σ\ sqrt {t} \ cdot \ cdot \ log t） \ Mathcal {o}（σ\ log t / \ sqrt {t}）$，其中$σ^2 $是噪声方差。因此，我们的上限和下界紧密至$ \ Mathcal {o}（（\ log t）^{1.5}）$。上限使用基于置信度和布朗运动的马尔可夫特性（除其他有用属性）的算法，并且下限是基于对二元假设检验的降低。
We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the $T$ adaptively chosen observations are corrupted by Gaussian noise. We show that as the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $Ω(σ\sqrt{T / \log (T)}) \cap \mathcal{O}(σ\sqrt{T} \cdot \log T)$ and $Ω(σ/ \sqrt{T \log (T)}) \cap \mathcal{O}(σ\log T / \sqrt{T})$ respectively, where $σ^2$ is the noise variance. Thus, our upper and lower bounds are tight up to a factor of $\mathcal{O}( (\log T)^{1.5} )$. The upper bound uses an algorithm based on confidence bounds and the Markov property of Brownian motion (among other useful properties), and the lower bound is based on a reduction to binary hypothesis testing.
