Batched Gaussian Process Bandit Optimization via Determinantal Point Processes
Gaussian Process bandit optimization has emerged as a powerful tool for optimizing noisy black box functions. One example in machine learning is hyper-parameter optimization where each evaluation of the target function may require training a model which may involve days or even weeks of computation. Most methods for this so-called "Bayesian optimization" only allow sequential exploration of the parameter space. However, it is often desirable to propose batches or sets of parameter values to explore simultaneously, especially when there are large parallel processing facilities at our disposal. Batch methods require modeling the interaction between the different evaluations in the batch, which can be expensive in complex scenarios. In this paper, we propose a new approach for parallelizing Bayesian optimization by modeling the diversity of a batch via Determinantal point processes (DPPs) whose kernels are learned automatically. This allows us to generalize a previous result as well as prove better regret bounds based on DPP sampling. Our experiments on a variety of synthetic and real-world robotics and hyper-parameter optimization tasks indicate that our DPP-based methods, especially those based on DPP sampling, outperform state-of-the-art methods.
The problem of  optimizing an unknown function is considered, where at each time step, one can sample a batch of B points where to evaluate the function. The problem is considered from a Bayesian standpoint, assuming the unknown function is sampled from a Gaussian process.  Borrowing ideas from the rich literature on this topic, the paper proposes a novel algorithm, based on determinantal point processes (DPP). A DPP samples sets of indices proportionally to the determinant of a submatrix formed by this set.  The paper introduces several variants, and shows the equivalence between the actions sampled by the algorithm and other strategies. In Section 3.1, a batch version of EST is considered, and is shown to be equivalent to a batch version of UCB. In Section 3.2,   Another variant based on DPP sampling, as opposed to maximization is considered and analyzed (Theorem 3.4).  Section 4 provides illustrative numerical experiments on a number of problems with both synthetic and real-world datasets.  
Overall, this is an interesting algorithmic contribution, supported by both a regret analysis and extensive numerical experiments. The writing of the paper is not very clear and does not help understanding the exact contributions.  The noise is assumed to be exactly Gaussian with known variance \sigma^2.  Although this is a standard assumption in the Bayesian world, this is also a restrictive assumption. It would be interesting to study the case when the sigma^2 is unknown, at least.  In the literature, there is another body of work related to the algorithms DOO, SOO, STOSOO, POO, etc. that is not cited here. I believe these are relevant works and should be discussed, at least briefly.  The contribution should be clarified. First, I think it is important to distinguish better between the existing algorithms from the literature, and  the ones that are introduced specifically here. Then, you should clarify the real benefit of using DPP in the end, both in terms of regret performance and numerical efficiency. It seems to me that the key result is Theorem 3.4; perhaps this can be highlighted.  Theorem 3.4 is interesting, as it shows some possible improvement one can get using DPP sampling. Do you think you can provide a few hints at the proof in the main material?  A natural side question is the computational complexity of the sampling scheme for DPP over other methods, and the effect of possible errors (when using MCMC for instances).   The numerical experiments are convincing and reported in a reproducible way.   L46: reference? L90: reference?