Reproduce “Batched Gaussian Process Bandit Optimization via Determinantal Point Processes” on OpenResearch

About this paper

Tarun Kathuria, Amit Deshpande, Pushmeet Kohli

Microsoft Research introduced a methodology for Batched Gaussian Process Bandit Optimization that leverages Determinantal Point Processes (DPPs) to explicitly promote diversity in batch selection. This approach yields improved theoretical regret bounds and consistently demonstrates superior empirical performance on various synthetic and real-world black-box optimization tasks, particularly with sampling-based DPP variants.

Key insights

• Determinantal Point Processes provide a theoretically sound and effective mechanism to explicitly model and promote diversity within batches, leading to better exploration-exploitation trade-offs in parallel optimization.
• Sampling-based DPP methods (DPP-SAMPLE) demonstrate theoretically superior regret bounds compared to maximization-based approaches (DPP-MAX) and other baselines, suggesting that incorporating uncertainty through sampling improves long-term performance.
• The popular UCB-Pure Exploration (UCB-PE) algorithm can be formally reinterpreted as a greedy approximation to (B-1)-DPP maximization, providing a new theoretical perspective on its operation.

Summary by alphaXiv.