Abstract: 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 expensive computation, e.g., for estimating entropy. We propose a new criterion, Max-value Entropy Search (MES), that instead uses the information about the maximum value. 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 entropy, and hence more efficient. We show relations of MES to other BO methods, and establish a regret bound. Empirical evaluations on a variety of tasks demonstrate the good performance of MES.