Causal Discovery with Reinforcement Learning

By Shengyu Zhu, Ignavier Ng, Zhitang Chen. 2019

293 citations recorded by the source corpus.

Discovering causal structure among a set of variables is a fundamental problem in many empirical sciences. Traditional score-based casual discovery methods rely on various local heuristics to search for a Directed Acyclic Graph (DAG) according to a predefined score function. While these methods, e.g., greedy equivalence search, may have attractive results with infinite samples and certain model assumptions, they are usually less satisfactory in practice due to finite data and possible violation of assumptions. Motivated by recent advances in neural combinatorial optimization, we propose to use Reinforcement Learning (RL) to search for the DAG with the best scoring. Our encoder-decoder model takes observable data as input and generates graph adjacency matrices that are used to compute rewards. The reward incorporates both the predefined score function and two penalty terms for enforcing acyclicity. In contrast with typical RL applications where the goal is to learn a policy, we use RL as a search strategy and our final output would be the graph, among all graphs generated during training, that achieves the best reward. We conduct experiments on both synthetic and real datasets, and show that the proposed approach not only has an improved search ability but also allows a flexible score function under the acyclicity constraint.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning, Causal Inference & Discovery

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Reinforcement Learning

In Causal Inference & Discovery

Citations in the corpus

Bayesian Structure Learning with Generative Flow Networks (2022, background): “Zhu et al. (2020) learn a single high-scoring structure using RL; however, unlike our approach, the creation of this graph does not involve sequential decisions.”
Differentiable Causal Discovery from Interventional Data (2020, background): “Zhu and Chen [46] also rely on the acyclicity constraint, but use reinforcement learning as a search strategy to estimate the DAG.”
A theory of independent mechanisms for extrapolation in generative models (2020, background): “Deep neural network have been leveraged in causal inference for learning causal graphs between observed variables (Lopez-Paz and Oquab 2016) and associated causal effects (Louizos et al. 2017; Shalit, Johansson, and Sontag 2017; Kocaoglu et al. 2017; Lachapelle et al. 2019; Zhu, Ng, and Chen 2019).”
Causally Correct Partial Models for Reinforcement Learning (2020, background): “…interest in combining causal inference with RL research in the directions of non-model-based bandit algorithms (Bareinboim et al., 2015; Forney et al., 2017; Zhang & Bareinboim, 2017; Lee & Bareinboim, 2018; Bradtke & Barto, 1996; Lu et al., 2018) and causal discovery with RL (Zhu & Chen, 2019).”
Learning Neural Causal Models from Unknown Interventions (2019, methodology): “Score-based methods search through the space of all possible directed acyclic graphs (DAGs) representing the causal structure based on some form of scoring function for network structures [9, 22, 23, 24, 25, 26, 27].”
CausalVAE: Disentangled Representation Learning via Neural Structural Causal Models (2020, methodology): “[36] proposed a flexible and efficient Reinforcement Learning (RL) based method to search over a DAG space for a best graph with a highest score.”
Masked Gradient-Based Causal Structure Learning (2019, methodology): “Setup Our setup here is similar to Zhu et al. [45].”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, methodology): “The authors of RL-BIC [272] take a reinforcement learning approach to causal discovery.”