  Entropy Search (ES) and Predictive Entropy Search (PES) are popular and
empirically successful Bayesian Optimization techniques. Both rely on a
compelling information-theoretic motivation, and maximize the information
gained about the $\arg\max$ of the unknown function; yet, both are plagued by
the expensive computation for estimating entropies. We propose a new criterion,
Max-value Entropy Search (MES), that instead uses the information about the
maximum function value. We show relations of MES to other Bayesian optimization
methods, and establish a regret bound. We observe that MES maintains or
improves the good empirical performance of ES/PES, while tremendously
lightening the computational burden. In particular, MES is much more robust to
the number of samples used for computing the entropy, and hence more efficient
for higher dimensional problems.
