Minimum Cost Intervention Design for Causal Effect Identification
TL;DR.
When a target causal effect is not identifiable from observations alone, we design the cheapest set of permitted interventions that makes it identifiable. We prove the problem is NP-hard, connect it to minimum hitting set, and give exact, logarithmic-approximation, and polynomial-time heuristic algorithms.
Why this matters.
This turns causal-effect identification into an experiment-planning problem with a real cost objective. The output is not just a statement that more experiments are needed, but a concrete low-cost intervention plan.
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 the collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-hard 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
Once observational data fail to identify the target effect, the key practical question is which experiments to run. Without a cost model, the answer is incomplete because some interventions are far more expensive than others.
2. The key idea
We optimize over interventions with an explicit cost objective. That lets us return a concrete, budget-aware plan rather than only saying that some intervention somewhere would suffice.
3. Complexity of minimum-cost identification
We prove that the minimum-cost intervention-design problem is NP-hard and connect its combinatorial structure to minimum hitting set.
4. Exact, approximate, and heuristic solvers
The hitting-set formulation yields an algorithm that can recover the optimum or a logarithmic-factor approximation. We also develop polynomial-time heuristics for settings where a very fast design is preferred.
5. How it works
- Specify the target effect, graph, and intervention costs.
- Characterize which intervention sets identify the target.
- Optimize over feasible intervention designs.
- Return the minimum-cost design and the resulting identification guarantee.
What the simulations show
Where this helps
Good fit
- You need to plan interventions under a real experimental budget.
- You want a concrete design recommendation rather than a generic identifiability statement.
- You care about which experiments are worth paying for when observational data are insufficient.
Keep in mind
- The design objective supports variable-specific intervention costs and can respect interventions that are unavailable or prohibited.
- The method targets one causal query directly, avoiding the extra cost of designing experiments to identify every possible effect in the graph.
Cite this paper
@InProceedings{pmlr-v162-akbari22a,
title = {Minimum Cost Intervention Design for Causal Effect Identification},
author = {Akbari, Sina and Etesami, Jalal and Kiyavash, Negar},
booktitle = {Proceedings of the 39th International Conference on Machine Learning},
pages = {258--289},
year = {2022},
volume = {162},
series = {Proceedings of Machine Learning Research},
publisher = {PMLR},
url = {https://proceedings.mlr.press/v162/akbari22a.html}
}