Causal Discovery with Reinforcement Learning

Abstract

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.

ICLR 2020 (oral). This version: minor edits in the appendix. Codes, datasets, and training logs have been made available at https://github.com/huawei-noah/trustworthyAI/tree/master/Causal_Structure_Learning/Causal_Discovery_RL

References in corpus (11)

• Sequence to Sequence Learning with Neural Networks
• Neural Architecture Search with Reinforcement Learning
• Learning Combinatorial Optimization Algorithms over Graphs
• Kernel-based Conditional Independence Test and Application in Causal Discovery
• On the Identifiability of the Post-Nonlinear Causal Model
• CAM: Causal additive models, high-dimensional order search and penalized regression
• Identifiability of Gaussian structural equation models with equal error variances
• DAGs with NO TEARS: Continuous Optimization for Structure Learning
• Learning to Learn without Gradient Descent by Gradient Descent
• DAG-GNN: DAG Structure Learning with Graph Neural Networks
• Gradient-Based Neural DAG Learning

Cited by in corpus (26)

• Neurosymbolic Reinforcement Learning and Planning: A Survey
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
• CausPref: Causal Preference Learning for Out-of-Distribution Recommendation
• Learning Neural Causal Models from Unknown Interventions
• gCastle: A Python Toolbox for Causal Discovery
• Towards Efficient Local Causal Structure Learning
• Learning Sparse Interaction Graphs of Partially Detected Pedestrians for Trajectory Prediction
• A Survey of Deep Reinforcement Learning in Recommender Systems: A Systematic Review and Future Directions
• Scalable Causal Structure Learning: Scoping Review of Traditional and Deep Learning Algorithms and New Opportunities in Biomedicine
• Differentiable Causal Discovery from Interventional Data
• CausalVAE: Structured Causal Disentanglement in Variational Autoencoder
• Causally Correct Partial Models for Reinforcement Learning
• Towards Human-like Perception: Learning Structural Causal Model in Heterogeneous Graph
• Learning Neural Causal Models with Active Interventions
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable
• Causal Reasoning in Software Quality Assurance: A Systematic Review
• Ordering-Based Causal Discovery with Reinforcement Learning
• Causal Adversarial Network for Learning Conditional and Interventional Distributions
• On the Convergence of Continuous Constrained Optimization for Structure Learning
• A polynomial-time algorithm for learning nonparametric causal graphs
• Supervised Whole DAG Causal Discovery
• Causal Multi-Agent Reinforcement Learning: Review and Open Problems
• Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching
• Efficient Neural Causal Discovery without Acyclicity Constraints
• Efficient and Scalable Structure Learning for Bayesian Networks: Algorithms and Applications
• Testing Directed Acyclic Graph via Structural, Supervised and Generative Adversarial Learning