# Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization

Source: [Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization](<https://www.sota2.com/research/paper/68fa60a01e209131ce9f0479>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T19:43:33.656Z

Authors: Thomas Desautels, Andreas Krause, Joel Burdick

Published: 2012-06-27T19:59:59.000Z

## Abstract

Can one parallelize complex exploration exploitation tradeoffs? As an example, consider the problem of optimal high-throughput experimental design, where we wish to sequentially design batches of experiments in order to simultaneously learn a surrogate function mapping stimulus to response and identify the maximum of the function. We formalize the task as a multi-armed bandit problem, where the unknown payoff function is sampled from a Gaussian process (GP), and instead of a single arm, in each round we pull a batch of several arms in parallel. We develop GP-BUCB, a principled algorithm for choosing batches, based on the GP-UCB algorithm for sequential GP optimization. We prove a surprising result; as compared to the sequential approach, the cumulative regret of the parallel algorithm only increases by a constant factor independent of the batch size B. Our results provide rigorous theoretical support for exploiting parallelism in Bayesian global optimization. We demonstrate the effectiveness of our approach on two real-world applications.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Flowshop Scheduling Problem on FSP-car5](<https://www.sota2.com/research/sota/flowshop-scheduling-problem-on-fsp-car5.md>): Flowshop Scheduling Problem; FSP-car5; Mean Objective Value: 7887.

- [Quadratic Assignment Problem on QAP-chr12a](<https://www.sota2.com/research/sota/quadratic-assignment-problem-on-qap-chr12a.md>): Quadratic Assignment Problem; QAP-chr12a; Mean Cost: 18105.

- [Traveling Salesman Problem on TSP burma14](<https://www.sota2.com/research/sota/traveling-salesman-problem-on-tsp-burma14.md>): Traveling Salesman Problem; TSP burma14; Mean Tour Length: 4184.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1206.6402>)

[PDF](<https://arxiv.org/pdf/1206.6402.pdf>)