  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.
