# Experimental Design for Cost-Aware Learning of Causal Graphs

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2018.

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

- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Learning Neural Causal Models with Active Interventions](https://mlsanity.com/paper/2109.02429/) (2021)
- [Causal Bandits with Unknown Graph Structure](https://mlsanity.com/paper/2106.02988/) (2021)
- [Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizability](https://mlsanity.com/paper/2209.08025/) (2022)
- [Generalizing Goal-Conditioned Reinforcement Learning with Variational Causal Reasoning](https://mlsanity.com/paper/2207.09081/) (2022)
- [Adaptively Exploiting d-Separators with Causal Bandits](https://mlsanity.com/paper/2202.05100/) (2022)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning](https://mlsanity.com/paper/2105.14024/) (2021)
- [Differentiable Multi-Target Causal Bayesian Experimental Design](https://mlsanity.com/paper/2302.10607/) (2023)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models](https://mlsanity.com/paper/2205.10083/) (2022)
- [Collaborative Causal Discovery with Atomic Interventions](https://mlsanity.com/paper/2106.03028/) (2021)
- [Trust Your nabla: Gradient-based Intervention Targeting for Causal Discovery](https://mlsanity.com/paper/2211.13715/) (2022)
- [Confounded Budgeted Causal Bandits](https://mlsanity.com/paper/2401.07578/) (2024)
- [Sample Efficient Bayesian Learning of Causal Graphs from Interventions](https://mlsanity.com/paper/2410.20089/) (2024)
- [New metrics and search algorithms for weighted causal DAGs](https://mlsanity.com/paper/2305.04445/) (2023)
- [Interventional Causal Discovery in a Mixture of DAGs](https://mlsanity.com/paper/2406.08666/) (2024)
- [Active Learning of Continuous-time Bayesian Networks through Interventions](https://mlsanity.com/paper/2105.14742/) (2021)
- [Experimental Design for Causal Effect Identification](https://mlsanity.com/paper/2205.02232/) (2022)
- [Causal Discovery under Off-Target Interventions](https://mlsanity.com/paper/2402.08229/) (2024)
- [Bayesian Intervention Optimization for Causal Discovery](https://mlsanity.com/paper/2406.10917/) (2024)
- [From Observation to Orientation: an Adaptive Integer Programming Approach to Intervention Design](https://mlsanity.com/paper/2504.03122/) (2025)
- [FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions](https://mlsanity.com/paper/2609.32165/) (2026)
- [Certifying Interventional Agreement Among Observationally Equivalent Causal Models](https://mlsanity.com/paper/2609.32247/) (2026)

## Abstract (arXiv)

We consider the minimum cost intervention design problem: Given the essential graph of a causal graph and a cost to intervene on a variable, identify the set of interventions with minimum total cost that can learn any causal graph with the given essential graph. We first show that this problem is NP-hard. We then prove that we can achieve a constant factor approximation to this problem with a greedy algorithm. We then constrain the sparsity of each intervention. We develop an algorithm that returns an intervention design that is nearly optimal in terms of size for sparse graphs with sparse interventions and we discuss how to use it when there are costs on the vertices.