Greed is Good: Exploration and Exploitation Trade-offs in Bayesian
  Optimisation
  The performance of acquisition functions for Bayesian optimisation to locate
the global optimum of continuous functions is investigated in terms of the
Pareto front between exploration and exploitation. We show that Expected
Improvement (EI) and the Upper Confidence Bound (UCB) always select solutions
to be expensively evaluated on the Pareto front, but Probability of Improvement
is not guaranteed to do so and Weighted Expected Improvement does so only for a
restricted range of weights.
  We introduce two novel $\epsilon$-greedy acquisition functions. Extensive
empirical evaluation of these together with random search, purely exploratory,
and purely exploitative search on 10 benchmark problems in 1 to 10 dimensions
shows that $\epsilon$-greedy algorithms are generally at least as effective as
conventional acquisition functions (e.g., EI and UCB), particularly with a
limited budget. In higher dimensions $\epsilon$-greedy approaches are shown to
have improved performance over conventional approaches. These results are borne
out on a real world computational fluid dynamics optimisation problem and a
robotics active learning problem. Our analysis and experiments suggest that the
most effective strategy, particularly in higher dimensions, is to be mostly
greedy, occasionally selecting a random exploratory solution.
