Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel
This work addresses a gap in Bayesian optimization for permutation-based combinatorial problems, which are important in practical applications like scheduling and routing, but it appears incremental as it extends existing batch methods to a specific domain.
The authors tackled the problem of expensive-to-evaluate combinatorial optimization on permutations by proposing a batch Bayesian optimization method called LAW2ORDER, which uses an acquisition weighted kernel and determinantal point processes to enable parallel evaluations, resulting in theoretical guarantees of sublinear regret and empirical performance on tasks like quadratic assignment and traveling salesman.
In this work we propose a batch Bayesian optimization method for combinatorial problems on permutations, which is well suited for expensive-to-evaluate objectives. We first introduce LAW, an efficient batch acquisition method based on determinantal point processes using the acquisition weighted kernel. Relying on multiple parallel evaluations, LAW enables accelerated search on combinatorial spaces. We then apply the framework to permutation problems, which have so far received little attention in the Bayesian Optimization literature, despite their practical importance. We call this method LAW2ORDER. On the theoretical front, we prove that LAW2ORDER has vanishing simple regret by showing that the batch cumulative regret is sublinear. Empirically, we assess the method on several standard combinatorial problems involving permutations such as quadratic assignment, flowshop scheduling and the traveling salesman, as well as on a structure learning task.