  Causal graph discovery is a significant problem with applications across
various disciplines. However, with observational data alone, the underlying
causal graph can only be recovered up to its Markov equivalence class, and
further assumptions or interventions are necessary to narrow down the true
graph. This work addresses the causal discovery problem under the setting of
stochastic interventions with the natural goal of minimizing the number of
interventions performed. We propose the following stochastic intervention model
which subsumes existing adaptive noiseless interventions in the literature
while capturing scenarios such as fat-hand interventions and CRISPR gene
knockouts: any intervention attempt results in an actual intervention on a
random subset of vertices, drawn from a distribution dependent on attempted
action. Under this model, we study the two fundamental problems in causal
discovery of verification and search and provide approximation algorithms with
polylogarithmic competitive ratios and provide some preliminary experimental
results.
