  We consider testing and learning problems on causal Bayesian networks as
defined by Pearl (Pearl, 2009). Given a causal Bayesian network $\mathcal{M}$
on a graph with $n$ discrete variables and bounded in-degree and bounded
`confounded components', we show that $O(\log n)$ interventions on an unknown
causal Bayesian network $\mathcal{X}$ on the same graph, and
$\tilde{O}(n/\epsilon^2)$ samples per intervention, suffice to efficiently
distinguish whether $\mathcal{X}=\mathcal{M}$ or whether there exists some
intervention under which $\mathcal{X}$ and $\mathcal{M}$ are farther than
$\epsilon$ in total variation distance. We also obtain sample/time/intervention
efficient algorithms for: (i) testing the identity of two unknown causal
Bayesian networks on the same graph; and (ii) learning a causal Bayesian
network on a given graph. Although our algorithms are non-adaptive, we show
that adaptivity does not help in general: $\Omega(\log n)$ interventions are
necessary for testing the identity of two unknown causal Bayesian networks on
the same graph, even adaptively. Our algorithms are enabled by a new
subadditivity inequality for the squared Hellinger distance between two causal
Bayesian networks.
