Optimal Observation-Intervention Trade-Off in Optimisation Problems with Causal Structure

Kim Hammar, Neil DhirarXiv 2023 · DOI · arXiv

Introduction

In high-stakes optimization tasks—such as medical treatment discovery or chemical process tuning—evaluating the objective function is often prohibitively expensive. Traditional "black-box" methods ignore the underlying causal structure, leading to inefficient budget allocation. While "causal" optimization methods exist, they typically suffer from myopia and unrealistic assumptions regarding the cost of observational data. This paper introduces OSCO (Optimal Stopping for Causal Optimisation), a framework that treats the choice between cheap observations and expensive interventions as a strategic optimal stopping problem.

The OSCO Framework

OSCO models the optimization process as a sequence of Markovian optimal stopping problems. At each step, the agent decides whether to continue collecting observational data or to "stop" and perform a definitive intervention. This decision is governed by a Bellman equation that balances expected information gain against remaining budget and costs.

Causal graph $\mathcal{G}$ and its manipulated versions under different interventions.

A key component of OSCO is the use of the causal graph to identify the Minimal Observation Set (MOS)—the smallest set of variables required to identify a specific causal effect. By focusing only on the MOS, the algorithm minimizes the cost of passive data collection. Furthermore, the authors demonstrate that under certain conditions, such as supermodularity of the reward function, the optimal strategy simplifies to a computationally efficient one-step lookahead rule.

Experimental Evaluation

The framework was evaluated across several Structural Causal Models (SCMs), including synthetic chain benchmarks and a real-world healthcare scenario involving prostate cancer (PSA level SCM). In these tests, "observations" represented low-cost diagnostic tests, while "interventions" represented expensive medical procedures.

Key Results

  • Cost-Efficiency: OSCO-enhanced algorithms consistently reached global optima at a lower total cost than standard Causal Bayesian Optimization or Multi-Armed Bandit baselines.
  • Regret Reduction: The framework achieved significantly lower simple regret within fixed budgets, outperforming common heuristics like $\epsilon$-greedy.
  • Robustness: The optimal stopping logic proved robust to Gaussian noise in causal effect estimations, maintaining performance even with imperfect data.

Conclusion

By framing the observation-intervention trade-off as an optimal stopping problem, OSCO provides a non-myopic strategy for "grey-box" optimization. While currently requiring a known causal structure, future extensions could integrate causal discovery to learn the graph dynamically. This approach marks a significant step toward more sample-efficient and cost-effective optimization in complex, real-world systems.

Summary updated

BibTeX
@misc{hammar2023optimal,
  author = {Kim Hammar and Neil Dhir},
  title = {{Optimal Observation-Intervention Trade-Off in Optimisation Problems with Causal Structure}},
  year = {2023},
  eprint = {2309.02287},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.02287},
}
Figure