$\epsilon$-shotgun: $\epsilon$-greedy Batch Bayesian Optimisation
  Bayesian optimisation is a popular, surrogate model-based approach for
optimising expensive black-box functions. Given a surrogate model, the next
location to expensively evaluate is chosen via maximisation of a cheap-to-query
acquisition function. We present an $\epsilon$-greedy procedure for Bayesian
optimisation in batch settings in which the black-box function can be evaluated
multiple times in parallel. Our $\epsilon$-shotgun algorithm leverages the
model's prediction, uncertainty, and the approximated rate of change of the
landscape to determine the spread of batch solutions to be distributed around a
putative location. The initial target location is selected either in an
exploitative fashion on the mean prediction, or -- with probability $\epsilon$
-- from elsewhere in the design space. This results in locations that are more
densely sampled in regions where the function is changing rapidly and in
locations predicted to be good (i.e close to predicted optima), with more
scattered samples in regions where the function is flatter and/or of poorer
quality. We empirically evaluate the $\epsilon$-shotgun methods on a range of
synthetic functions and two real-world problems, finding that they perform at
least as well as state-of-the-art batch methods and in many cases exceed their
performance.
