Cost-Optimal Learning of Causal Graphs
We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.
Code (1)
Tasks
Graph LearningSimilar Papers 제목 키워드 기반
Experimental Design for Cost-Aware Learning of Causal Graphs
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 ca…
Experimental DesignConfounded Budgeted Causal Bandits
We study the problem of learning 'good' interventions in a stochastic environment modeled by its underlying causal graph. Good interventions refer to interventions that maximize rewards. Specifically, we consider the set…
Experimental Design for Causal Effect Identification
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 inte…
Experimental DesignAn Identifiable Cost-Aware Causal Decision-Making Framework Using Counterfactual Reasoning
Decision making under abnormal conditions is a critical process that involves evaluating the current state and determining the optimal action to restore the system to a normal state at an acceptable cost. However, in suc…
counterfactualCounterfactual ReasoningDecision MakingMulti-Objective Causal Bayesian Optimization
In decision-making problems, the outcome of an intervention often depends on the causal relationships between system components and is highly costly to evaluate. In such settings, causal Bayesian optimization (CBO) can e…
Bayesian OptimizationDecision Making