Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discovery

• URL: http://arxiv.org/abs/2310.13576v2
• Date: Tue, 13 Feb 2024 16:18:04 GMT
• Title: Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discovery
• Authors: Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi
• Abstract summary: CD-UCT is a model-based reinforcement learning method for causal discovery based on tree search. We formalize and prove the correctness of an efficient algorithm for excluding edges that would introduce cycles. The proposed method can be applied broadly to causal Bayesian networks with both discrete and continuous random variables.
• Score: 6.772856304452474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Identifying causal structure is central to many fields ranging from strategic decision-making to biology and economics. In this work, we propose CD-UCT, a model-based reinforcement learning method for causal discovery based on tree search that builds directed acyclic graphs 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 in DAG space. 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 reinforcement learning technique and greedy search, constituting a promising advancement for combinatorial methods.

Related papers

• BPP-Search: Enhancing Tree of Thought Reasoning for Mathematical Modeling Problem Solving [11.596474985695679]
  We release the StructuredOR dataset, annotated with comprehensive labels that capture the complete mathematical modeling process. We propose BPP-Search, a algorithm that integrates reinforcement learning into a tree-of-thought structure. BPP-Search significantly outperforms state-of-the-art methods, including Chain-of-Thought, Self-Consistency, and Tree-of-Thought.
  arXiv  Detail & Related papers  (2024-11-26T13:05:53Z)
• Technical Report: Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1-like reasoning approach is challenging, and researchers have been making various attempts to advance this open area of research. We present a preliminary exploration into enhancing the reasoning abilities of LLMs through reward-guided tree search algorithms.
  arXiv  Detail & Related papers  (2024-11-18T16:15:17Z)
• ALIAS: DAG Learning with Efficient Unconstrained Policies [30.67987131971867]
  We introduce ALIAS, a novel approach to causal discovery powered by the reinforcement learning machinery. Our method features an efficient policy for generating DAGs in just a single step with an optimal quadratic complexity. We provide compelling empirical evidence for the strong performance of ALIAS in comparison with state-of-the-arts in causal discovery.
  arXiv  Detail & Related papers  (2024-08-24T03:12:21Z)
• Discovering Dynamic Causal Space for DAG Structure Learning [64.763763417533]
  We propose a dynamic causal space for DAG structure learning, coined CASPER. It integrates the graph structure into the score function as a new measure in the causal space to faithfully reflect the causal distance between estimated and ground truth DAG.
  arXiv  Detail & Related papers  (2023-06-05T12:20:40Z)
• Causality Learning With Wasserstein Generative Adversarial Networks [2.492300648514129]
  A model named DAG-WGAN combines the Wasserstein-based adversarial loss with an acyclicity constraint in an auto-encoder architecture. It simultaneously learns causal structures while improving its data generation capability. We compare the performance of DAG-WGAN with other models that do not involve the Wasserstein metric in order to identify its contribution to causal structure learning.
  arXiv  Detail & Related papers  (2022-06-03T10:45:47Z)
• DAG-WGAN: Causal Structure Learning With Wasserstein Generative Adversarial Networks [2.492300648514129]
  This paper proposes DAG-WGAN, which combines the Wasserstein-based adversarial loss, an auto-encoder architecture together with an acyclicity constraint. It simultaneously learns causal structures and improves its data generation capability by leveraging the strength from the Wasserstein distance metric. Our experiments have evaluated DAG-WGAN against the state-of-the-art and demonstrated its good performance.
  arXiv  Detail & Related papers  (2022-04-01T12:27:27Z)
• BCDAG: An R package for Bayesian structure and Causal learning of Gaussian DAGs [77.34726150561087]
  We introduce the R package for causal discovery and causal effect estimation from observational data. Our implementation scales efficiently with the number of observations and, whenever the DAGs are sufficiently sparse, the number of variables in the dataset. We then illustrate the main functions and algorithms on both real and simulated datasets.
  arXiv  Detail & Related papers  (2022-01-28T09:30:32Z)
• Learning Neural Causal Models with Active Interventions [83.44636110899742]
  We introduce an active intervention-targeting mechanism which enables a quick identification of the underlying causal structure of the data-generating process. Our method significantly reduces the required number of interactions compared with random intervention targeting. We demonstrate superior performance on multiple benchmarks from simulated to real-world data.
  arXiv  Detail & Related papers  (2021-09-06T13:10:37Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• Ordering-Based Causal Discovery with Reinforcement Learning [31.358145789333825]
  We propose a novel RL-based approach for causal discovery, by incorporating RL into the ordering-based paradigm. We analyze the consistency and computational complexity of the proposed method, and empirically show that a pretrained model can be exploited to accelerate training.
  arXiv  Detail & Related papers  (2021-05-14T03:49:59Z)
• Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning [93.1435980666675]
  We show how optimistic exploration can be easily combined with state-of-the-art reinforcement learning algorithms. Our experiments demonstrate that optimistic exploration significantly speeds-up learning when there are penalties on actions.
  arXiv  Detail & Related papers  (2020-06-15T18:37:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.