# Experimental Design for Causal Effect Identification

arXiv: https://arxiv.org/abs/2205.02232 · HTML: https://mlsanity.com/paper/2205.02232/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 46 references that are in the map.
- First posted on arXiv 4 May 2022.

## Builds on (most cited first, 7 of 7)

- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/2110.12036/) (2021)
- [Experimental Design for Cost-Aware Learning of Causal Graphs](https://mlsanity.com/paper/1810.11867/) (2018)
- [Efficient Intervention Design for Causal Discovery with Latents](https://mlsanity.com/paper/2005.11736/) (2020)
- [Causal Effect Identification from Multiple Incomplete Data Sources: A General Search-based Approach](https://mlsanity.com/paper/1902.01073/) (2019)
- [Intervention Efficient Algorithms for Approximate Learning of Causal Graphs](https://mlsanity.com/paper/2012.13976/) (2020)

## Built on by (most cited first, 2 of 2)

- [Causal Effect Identification in Uncertain Causal Networks](https://mlsanity.com/paper/2208.04627/) (2022)
- [Reasoning Models Are Accurate but Unsound on Identification](https://mlsanity.com/paper/2610.03519/) (2026)

## Abstract (arXiv)

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.