Optimal Experiment Design for Causal Effect Identification
TL;DR.
When observational data cannot identify a target causal effect, we ask which interventions should be performed at minimum cost. We prove the exact design problem is NP-complete, connect it to minimum hitting set, and give exact, logarithmic-approximation, and polynomial-time heuristic algorithms. Simulations show the heuristics achieve low regret on random causal graphs.
Why this matters.
The result turns causal identifiability into an actionable experiment-design problem with variable-specific costs and provable guarantees. It tells us how to spend experimental budget specifically on the interventions needed for the causal query of interest.
Abstract
Pearl’s do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the causal effect. In this work, we consider the problem of designing a collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-complete and subsequently propose an algorithm that can either find the optimal solution or a logarithmic-factor approximation of it. This is done by establishing a connection between our problem and the minimum hitting set problem. Additionally, we propose several polynomial time heuristic algorithms to tackle the computational complexity of the problem. Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs.
The paper at a glance
An informal guide to the problem, the idea, and the main results.
1. The problem
When a target effect is not identifiable from observational data, the next question is not theoretical but operational: which interventions should we perform? Naively searching through all intervention combinations is combinatorial and quickly becomes infeasible.
2. The key idea
We convert identification into an optimization problem over candidate experiments. The design criterion targets identifiability itself, so the selected interventions are chosen because they unlock the causal query we care about.
3. Complexity of optimal design
We prove that finding a minimum-cost intervention set for identifying a specific causal effect is NP-complete. We also show that obtaining a sub-logarithmic-factor approximation is NP-hard.
4. Exact and approximate design
We reduce the design problem to minimum hitting set. This yields an algorithm that can recover the exact optimum and, when used approximately, gives a logarithmic-factor approximation. We also develop polynomial-time heuristics and identify special cases that admit efficient exact solutions.
5. How it works
- Specify the target effect and the causal graph.
- Characterize which intervention sets would identify the target.
- Optimize over those sets under a cost criterion.
- Return the cheapest or otherwise best experimental design.
What the simulations show
Where this helps
Good fit
- You know your observational data are not enough and need to plan follow-up experiments.
- You want to spend intervention budget only where it helps identify the causal query.
- You need a principled bridge between identifiability theory and experimental planning.
Keep in mind
- The framework allows interventions to carry different costs and also allows some variables to be unavailable for intervention.
- Beyond the general NP-complete problem, the paper identifies special graph/design regimes that can be solved exactly in polynomial time.
Cite this paper
@article{akbari2025optimal,
author = {Sina Akbari and Jalal Etesami and Negar Kiyavash},
title = {Optimal Experiment Design for Causal Effect Identification},
journal = {Journal of Machine Learning Research},
year = {2025},
volume = {26},
number = {28},
pages = {1--56},
url = {https://www.jmlr.org/papers/v26/22-1516.html}
}