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.
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