Simple regret upper bounded by average regret

[chrisyeh96]

Describe the erratum

On page 215, the phrase

As the mean of a vector is a lower bound on its maximum

should probably be replaced with

As the mean of a vector is an upper bound on its minimum

because the next line writes $r\tau \leq \frac{R\tau}{\tau}$ where $r\tau$ (simple regret) is the minimum over the vector of instantaneous regrets, whose average is given by $\frac{R\tau}{\tau}$.

Version and Location

• Book version: downloaded from https://bayesoptbook.com/book/bayesoptbook.pdf on 2024-02-14.
• Page #: 215

[bayesoptbook]

I think the book is correct here, at least as I intended when I wrote this. The vector I am referring to here is the vector of function values φₜ appearing in (10.1) with a max. Then we have that the mean of this vector is a lower bound on its maximum:

1/τ ϕₜ ≤ max ϕₜ

thus we are subtracting off a smaller quantity from f* in Rₜ / τ than in rₜ, leading to the given inequality.