Mixed Strategies for Robust Optimization of Unknown Objectives

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

Introduction

Robust Optimization (RO) is a critical framework for decision-making in environments where external conditions are uncertain or adversarial. Traditional RO methods typically seek a single, deterministic "best" action. However, this approach often leads to the "conservatism trap"—where a system becomes so risk-averse that it fails to achieve its goals. Furthermore, RO usually assumes the objective function is known, whereas in many real-world applications, the objective must be learned through trial and error.

To address these challenges, researchers from ETH Zürich have developed GP-MRO (Gaussian Process - Mixed Robust Optimization). By shifting the focus from deterministic choices to randomized mixed strategies, GP-MRO enables systems to hedge their bets, significantly improving performance in worst-case scenarios without becoming paralyzed by uncertainty.

The GP-MRO Algorithm: Learning to Hedge

GP-MRO treats robust optimization as a repeated zero-sum game between a Learner (the decision-maker) and an Adversary (representing worst-case uncertainty). The algorithm integrates two powerful tools:

  1. Gaussian Processes (GP): Since the objective function is unknown, GP-MRO uses a GP to build a statistical model from noisy observations. It employs Upper Confidence Bounds (UCB) to explore the function efficiently.
  2. Multiplicative Weight Updates (MWU): This online learning mechanism allows the algorithm to maintain and update a probability distribution over the adversary’s possible moves.

A key innovation of GP-MRO is its output: instead of a single point, it provides a mixed strategy—a probability distribution over multiple actions. This randomization prevents an adversary from perfectly exploiting a fixed decision, effectively "breaking" the conservatism inherent in deterministic models.

Figure 1: (a) Visualization of selected points on a non-convex objective surface. GP-MRO selects a mixed strategy across multiple points, whereas deterministic methods like StableOpt are restricted to one. (b) Performance comparison showing GP-MRO's superior convergence and higher performance indicator over time.

Case Study: Autonomous Overtaking

The practical benefits of GP-MRO are most evident in autonomous vehicle (AV) navigation. In a car-following scenario involving an unpredictable human driver, the AV must balance progress with safety. Deterministic robust strategies often fail here; because they cannot find a single trajectory that is safe against every possible human maneuver, they simply refuse to overtake.

In 1,000 closed-loop simulations, the deterministic baseline StableOpt never successfully overtook the human driver. In contrast, GP-MRO’s mixed strategy allowed for successful overtaking in 40.8% of cases while maintaining rigorous safety standards. This resulted in a significantly higher average final position (169.4m compared to 123.1m for the deterministic approach).

Figure 2: Trajectory planning for autonomous vehicles. (a) Initial plausible trajectories. (b-c) Strategies computed by GP-MRO that enable safe overtaking by considering a distribution of potential human responses.

Key Results and Future Directions

Beyond the AV case study, GP-MRO demonstrated strong theoretical and empirical performance:

  • Theoretical Guarantees: The authors provided sample complexity bounds, proving that the algorithm converges to a near-optimal mixed strategy based on the complexity of the underlying function.
  • Benchmark Success: GP-MRO consistently outperformed both deterministic robust baselines and standard non-robust algorithms (like GP-UCB) across synthetic and standard optimization benchmarks.

Future research will look to extend this framework to continuous uncertainty sets and explore high-dimensional decision spaces. Additionally, the team plans to validate the learned "scoring functions" with real-world human-in-the-loop trials to further refine the interaction between autonomous systems and human agents.

Summary updated

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