Tight Regret Bounds for Noisy Optimization of a Brownian Motion

Type: Article

Publication Date: 2022-01-01

Citations: 1

DOI: https://doi.org/10.1109/tsp.2022.3144939

Abstract

We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> adaptively chosen observations are corrupted by Gaussian noise. We show that the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\Omega (\sigma \sqrt {T / \log (T)}) \cap \mathcal {O}(\sigma \sqrt {T} \cdot \log T)$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\Omega (\sigma / \sqrt {T \log (T)}) \cap \mathcal {O}(\sigma \log T / \sqrt {T})$</tex-math></inline-formula> respectively, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sigma ^2$</tex-math></inline-formula> is the noise variance. Thus, our upper and lower bounds are tight up to a factor of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O} ((\log T)^{1.5})$</tex-math></inline-formula> . 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.

Locations

  • IEEE Transactions on Signal Processing - View
  • arXiv (Cornell University) - View - PDF

Similar Works

Action Title Year Authors
+ Tight Regret Bounds for Noisy Optimization of a Brownian Motion 2020 Zexin Wang
Vincent Y. F. Tan
Jonathan Scarlett
+ Tight Regret Bounds for Bayesian Optimization in One Dimension 2018 Jonathan Scarlett
+ Tight Regret Bounds for Bayesian Optimization in One Dimension 2018 Jonathan Scarlett
+ Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations 2012 Nando de Freitas
Masrour Zoghi
Alex Smola
+ Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations 2012 Nando de Freitas
Alex Smola
Masrour Zoghi
+ Regret Bounds for Deterministic Gaussian Process Bandits 2012 Nando de Freitas
Alexander J. Smola
Masrour Zoghi
+ Regret Bounds for Deterministic Gaussian Process Bandits 2012 Nando de Freitas
Alex Smola
Masrour Zoghi
+ Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization 2017 Jonathan Scarlett
Ilijia Bogunovic
Volkan Cevher
+ PDF Chat Regret-Optimal Filtering for Prediction and Estimation 2022 Oron Sabag
Babak Hassibi
+ Sharp regret bounds for empirical Bayes and compound decision problems 2021 Yury Polyanskiy
Yihong Wu
+ Adaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization 2017 Kinjal Basu
Souvik Ghosh
+ Communication-Constrained Bandits under Additive Gaussian Noise 2023 Prathamesh Mayekar
Jonathan Scarlett
Vincent Y. F. Tan
+ PDF Chat Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization 2024 Kwang-Sung Jun
Jungtaek Kim
+ Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs 2020 Bo Xue
Guanghui Wang
Yimu Wang
Lijun Zhang
+ Tracking the Best Expert in Non-stationary Stochastic Environments 2017 Chen-Yu Wei
Yi-Te Hong
Chi-Jen Lu
+ Minimax filtering regret via relations between information and estimation 2013 Albert No
Tsachy Weissman
+ PDF Chat Optimal Minimization of the Covariance Loss 2022 Vishesh Jain
Ashwin Sah
Mehtaab Sawhney
+ Regret Bounds for Gaussian-Process Optimization in Large Domains 2021 Manuel Wuethrich
Bernhard Schölkopf
Andreas Krause
+ PDF Chat Stopping Bayesian Optimization with Probabilistic Regret Bounds 2024 James T. Wilson
+ PDF Chat Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding 2023 Amrit Singh Bedi
Dheeraj Peddireddy
Vaneet Aggarwal
Brian M. Sadler
Alec Koppel