Title: Optimal Experiment Design for Causal Discovery from Fixed Number of Experiments,
Abstract: We study the problem of causal structure learning over a set of random
variables when the experimenter is allowed to perform at most $M$ experiments
in a non-adaptive manner. We consider the optimal learning strategy in terms of
minimizing the portions of the structure that remains unknown given the limited
number of experiments in both Bayesian and minimax setting. We characterize the
theoretical optimal solution and propose an algorithm, which designs the
experiments efficiently in terms of time complexity. We show that for bounded
degree graphs, in the minimax case and in the Bayesian case with uniform
priors, our proposed algorithm is a $\rho$-approximation algorithm, where
$\rho$ is independent of the order of the underlying graph. Simulations on both
synthetic and real data show that the performance of our algorithm is very
close to the optimal solution.