Adversarial Causal Bayesian Optimization
Scott Sussex Pier Giuseppe Sessa Anastasiia Makarova Andreas Krause
In Causal Bayesian Optimization (CBO), an agent intervenes on an unknown
structural causal model to maximize a downstream reward variable. In this
paper, we consider the generalization where other agents or external events
also intervene on the system, which is key for enabling adaptiveness to
non-stationarities such as weather changes, market forces, or adversaries. We
formalize this generalization of CBO as Adversarial Causal Bayesian
Optimization (ACBO) and introduce the first algorithm for ACBO with bounded
regret: Causal Bayesian Optimization with Multiplicative Weights (CBO-MW). Our
approach combines a classical online learning strategy with causal modeling of
the rewards. To achieve this, it computes optimistic counterfactual reward
estimates by propagating uncertainty through the causal graph. We derive regret
bounds for CBO-MW that naturally depend on graph-related quantities. We further
propose a scalable implementation for the case of combinatorial interventions
and submodular rewards. Empirically, CBO-MW outperforms non-causal and
non-adversarial Bayesian optimization methods on synthetic environments and
environments based on real-word data. Our experiments include a realistic
demonstration of how CBO-MW can be used to learn users' demand patterns in a
shared mobility system and reposition vehicles in strategic areas.