Mixed Strategies for Robust Optimization of Unknown Objectives

Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, Andreas Krause

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 algorithm, GP-MRO, which leverages Gaussian Processes and game-theoretic principles to find robust, randomized (mixed) strategies. We demonstrate that randomized strategies can significantly outperform traditional deterministic approaches, particularly in complex scenarios like autonomous driving trajectory planning.

Introduction

In many real-world applications, from financial portfolio management to robotics, decision-makers aim to maximize a reward while remaining robust against worst-case uncertainties, such as market crashes or sensor failures. This challenge falls under the domain of Robust Optimization (RO). However, traditional RO methods face two significant hurdles: the objective function is often unknown and must be learned through noisy observations (the bandit setting), and deterministic strategies tend to be overly conservative and predictable.

This paper addresses these issues by seeking a mixed strategy—a probability distribution over actions—that maximizes the worst-case expected reward for an unknown function. By embracing randomization, the proposed method avoids the sub-optimal, overly cautious behavior typical of deterministic robust methods.

Methodology: GP-MRO

The authors introduce GP-MRO (Gaussian Process Mixed Robust Optimization), which frames the problem as a repeated zero-sum game between a Learner (the optimizer) and an Adversary (representing uncertainty).

GP-MRO selects multiple points to form a mixed strategy, outperforming deterministic methods like StableOpt in 1D benchmarks.

The algorithm integrates several key components:

  • Gaussian Processes (GP): To model the unknown objective function $f(x, \theta)$, GP-MRO uses a GP based on past observations. It employs Upper Confidence Bounds (UCB) to maintain an optimistic view of poorly explored regions, guiding exploration.
  • Multiplicative Weight Updates (MWU): This serves as the engine for the adversary. At each iteration, the algorithm updates a distribution over uncertain parameters, effectively learning which realizations are most damaging to the learner's current strategy.
  • Best Response: The learner selects an action that performs best against the adversary's current distribution, utilizing the GP's optimistic estimates. Since the true function is unknown, the algorithm uses the GP-UCB to emulate the full-information feedback required by standard MWU.
  • Final Output: Instead of a single point, GP-MRO returns a uniform distribution over all actions taken during the learning phase, providing a robust mixed strategy.

Experimental Results

The performance of GP-MRO was evaluated across synthetic benchmarks and a complex autonomous driving simulation.

Synthetic Benchmarks

In tests using 1D functions sampled from a GP prior and a 2D non-convex function ($g_{poly}$), GP-MRO consistently achieved higher worst-case rewards than state-of-the-art deterministic methods like StableOpt and standard GP-UCB. The ability to randomize allowed the learner to explore and exploit the function landscape more effectively under uncertainty.

Performance comparison on the 2D non-convex g_poly function, showing GP-MRO's superior convergence to higher performance indicators.

Autonomous Driving Simulation

A key highlight is the "human-assisted trajectory planning" task. An autonomous vehicle (AV) must navigate around a human-driven vehicle (HV) with uncertain intentions.

  • Deterministic Conservatism: The deterministic robust strategy (StableOpt) consistently chose to brake, as it was the only guaranteed safe move. It failed to complete a single overtake in 1,000 trials.
  • Mixed Strategy Success: In contrast, GP-MRO successfully overtook the HV in 40.8% of cases. By using a mixed strategy, the AV could take calculated risks that improved average performance while maintaining a robust safety profile, reaching an average final position of 169.4m compared to 123.1m for the deterministic baseline.

Key Insights and Theoretical Guarantees

The core insight of this work is that randomization is a strength. In adversarial or highly uncertain settings, being unpredictable prevents the learner from being trapped in overly conservative local optima. Furthermore, the authors provide rigorous proofs of sample efficiency, establishing the number of evaluations required to reach an $\epsilon$-optimal mixed strategy for common GP kernels like Squared Exponential and Matérn.

Limitations and Future Work

While promising, GP-MRO currently assumes a finite set for the uncertain parameter $\theta$. Future iterations could explore native continuous-parameter versions to avoid discretization. Additionally, the computational cost of updating the GP and running the MWU/Best-Response loop increases with the number of samples, suggesting a need for more efficient implementations. Finally, testing with real-time human feedback would further validate the algorithm's utility in human-robot interaction scenarios.

Summary updated

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 nov...
BibTeX
@inproceedings{sessa2020mixed,
  author = {Pier Giuseppe Sessa and Ilija Bogunovic and Maryam Kamgarpour and Andreas Krause},
  title = {{Mixed Strategies for Robust Optimization of Unknown Objectives}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=SwtMO2txfGB},
}
Figure