Tree search in DAG space with model-based reinforcement learning for causal discovery

Identifying causal structure is central to many fields ranging from strategic decision making to biology and economics. In this work, we propose Causal Discovery Upper Confidence Bound for Trees (CD-UCT), a model-based reinforcement learning (RL) method for causal discovery based on tree search that builds directed acyclic graphs (DAGs) incrementally. We also formalize and prove the correctness of an efficient algorithm for excluding edges that would introduce cycles, which enables deeper discrete search and sampling. The proposed method can be applied broadly to causal Bayesian networks with both discrete and continuous random variables. We conduct a comprehensive evaluation on synthetic and real-world datasets showing that CD-UCT substantially outperforms the state-of-the-art model-free RL technique that operates in DAG space and greedy search, constituting a promising advancement for combinatorial methods.