<p>That paper is good but pretty old, many things happened since then.</p>

<p>In the literature of Bayesian Optimization what you are trying to do is to come up with a new <em>acquisition function</em> $\alpha(x)$, where $x$ is a point in the domain to be optimized (Jones et al. use Expected Improvement as their acquisition function) and $\alpha$ is some metric that takes into account exploration vs exploitation. People have been working on this problem for a long time.</p>

<p>You might want to check the literature review papers that I listed in <a href="https://stats.stackexchange.com/questions/193306/optimization-when-cost-function-slow-to-evaluate/193391#193391">my answer to this other question</a>. In particular, you'll see that there are several common acquisition functions that people use in Bayesian Optimization:</p>

<ol>
<li>Probability of Improvement (PI).</li>
<li>Expected improvement (EI), as per Jones et al.</li>
<li>Lower confidence bound (LCB), or UCB for maximization (Srinivas et al., 2010)</li>
<li>Expected information gain (ES, or Entropy Search); see Hennig and Schuler (2012) and Hernández-Lobato et al. (2014).</li>
</ol>

<p>Note that 1 and 2 belong to a more general class of generalized expected-improvement measures (see Schonlau et al., 1998).</p>

<p>Metrics based on entropy are somewhat more principled but much harder to compute. EI is the "standard" choice nowadays, although it is not always the best choice. Sometimes it is good to use a combination of acquisition functions (see Hoffman et al., 2011).</p>

<hr>

<p><strong>References:</strong></p>

<p>[1] Srinivas, N., Krause, A., Kakade, S. M., &amp; Seeger, M. (2009). Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995.</p>

<p>[2] Hennig, P., &amp; Schuler, C. J. (2012). Entropy search for information-efficient global optimization. The Journal of Machine Learning Research, 13(1), 1809-1837.</p>

<p>[3] Hernández-Lobato, J. M., Hoffman, M. W., &amp; Ghahramani, Z. (2014). Predictive entropy search for efficient global optimization of black-box functions. In Advances in Neural Information Processing Systems (pp. 918-926).</p>

<p>[4] Schonlau, M., Welch, W. J., &amp; Jones, D. R. (1998). Global versus local search in constrained optimization of computer models. Lecture Notes-Monograph Series, 11-25.</p>

<p>[5] Hoffman, M. D., Brochu, E., &amp; de Freitas, N. (2011). Portfolio Allocation for Bayesian Optimization. In UAI (pp. 327-336).</p>
