Tree search in DAG spacewith an arbitrary ordering of the initial edges with model-based reinforcement learning for causal discovery

Journal article

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.

Authors: Darvariu, V-A; Hailes, S; Musolesi, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Royal Society
• Journal: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
• Volume: 481
• Issue: 2312
• Article number: 20240450
• Publication date: 2025-04-16
• Acceptance date: 2024-10-08
• DOI: 10.1098/rspa.2024.0450
• EISSN: 1471-2946
• ISSN: 1364-5021
• Language: English
• Keywords: causal discovery; reinforcement learning; tree search; combinatorial optimization; causality