Bayesian Optimization: How do we compute the maximum increase in information for the next step

If I understand correctly, Bayesian Optimization works by having a prior and choosing the next step by finding the direction that will maximize the mutual information between the prior and posterior. How do we normally compute that maximum on real data? Do we use derivatives?

Bayesian optimization takes place in several steps.

1. Using some data, build a surrogate model $g$ of the objective function $f$.

2. Using some method, select a set of query points.

3. Obtain acquisition function $h$ scores for the query points.

4. Select the query point $\tilde{x}$ optimizing $h$. Depending on how you proceeded in (3), this may itself comprise an additional optimization problem. For example, if (3) is a "rectangle" in $\mathbb{R}^n$, then you'll be optimizing $h$ over that rectangle. On the other hand, if you just selected a finite number of points $x_1, x_2, ... x_m$ at random from some space, then selecting $\tilde{x}$ is a matter of choosing $\max_i h(x_i)$

5. Evaluate $f(\tilde{x})$, append it to the data, return to (1).

It sounds like you are asking about acquisition functions. There are any number of acquisition functions with different properties. The way to compute the value of a particular acquisition function depends on the function.

I do not have experience using acquisition functions based on mutual information. Functions like Expected Improvement or Expected Quantile Improvement (EQI) are based on the predicted mean and variance estimated by $g$ (and some user-specified parameters). One (naïve) way to proceed is to simply randomly sample some number of points and evaluate EQI at each of those points, picking the best as $\tilde{x}$.