Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization

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.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (6)

• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
• Near-optimal Nonmyopic Value of Information in Graphical Models
• Efficient Optimal Learning for Contextual Bandits
• Hybrid Batch Bayesian Optimization
• Batch Active Learning via Coordinated Matching

Cited by in corpus (11)

• Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions
• Spectral bandits for smooth graph functions
• Gaussian Process Optimization with Mutual Information
• Bayesian optimization for computationally extensive probability distributions
• Is novelty predictable?
• $\epsilon$-shotgun: $\epsilon$-greedy Batch Bayesian Optimisation
• Impatient Bandits: Optimizing Recommendations for the Long-Term Without Delay
• Computational catalyst discovery: Active classification through myopic multiscale sampling
• Sampling Acquisition Functions for Batch Bayesian Optimization
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Some performance considerations when using multi-armed bandit algorithms in the presence of missing data