Mixed Strategies for Robust Optimization of Unknown Objectives

Abstract

We consider robust optimization problems, where the goal is to optimize an unknown objective function against the worst-case realization of an uncertain parameter. For this setting, we design a novel sample-efficient algorithm GP-MRO, which sequentially learns about the unknown objective from noisy point evaluations. GP-MRO seeks to discover a robust and randomized mixed strategy, that maximizes the worst-case expected objective value. To achieve this, it combines techniques from online learning with nonparametric confidence bounds from Gaussian processes. Our theoretical results characterize the number of samples required by GP-MRO to discover a robust near-optimal mixed strategy for different GP kernels of interest. We experimentally demonstrate the performance of our algorithm on synthetic datasets and on human-assisted trajectory planning tasks for autonomous vehicles. In our simulations, we show that robust deterministic strategies can be overly conservative, while the mixed strategies found by GP-MRO significantly improve the overall performance.

References in corpus (10)

• A Tutorial on Bayesian Optimization
• Certifying Some Distributional Robustness with Principled Adversarial Training
• Max-value Entropy Search for Efficient Bayesian Optimization
• Adversarially Robust Optimization with Gaussian Processes
• Time-Varying Gaussian Process Bandit Optimization
• Minimizing the Maximal Loss: How and Why?
• Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Bayesian optimisation under uncertain inputs
• Distributionally Robust Submodular Maximization