MARLIN: Multi-Agent Reinforcement Learning for Incremental DAG Discovery

Dong Li; Zhengzhang Chen; Xujiang Zhao; Linlin Yu; Zhong Chen; Yi He; Haifeng Chen; Chen Zhao

cs.LGMar 19, 2026

MARLIN: Multi-Agent Reinforcement Learning for Incremental DAG Discovery

Authors: Dong Li, Zhengzhang Chen, Xujiang Zhao, Linlin Yu, Zhong Chen, Yi He, Haifeng Chen, Chen Zhao

Organizations: Department of Computer Science, Baylor University · NEC Labs America · School of Computer and Cyber Sciences, Augusta University · School of Computing, Southern Illinois University ·

Abstract

Uncovering causal structures from observational data is crucial for understanding complex systems and making informed decisions. While reinforcement learning (RL) has shown promise in identifying these structures in the form of a directed acyclic graph (DAG), existing methods often lack efficiency, making them unsuitable for online applications. In this paper, we propose MARLIN, an efficient multi agent RL based approach for incremental DAG learning. MARLIN uses a DAG generation policy that maps a continuous real valued space to the DAG space as an intra batch strategy, then incorporates two RL agents state specific and state invariant to uncover causal relationships and integrates these agents into an incremental learning framework. Furthermore, the framework leverages a factored action space to enhance parallelization efficiency. Extensive experiments on synthetic and real datasets demonstrate that MARLIN outperforms state of the art methods in terms of both efficiency and effectiveness.

Figures & tables

Figure 1: Comparison of the learning processes of offline (top) and online (bottom) RL-based DAG learning methods in an online data stream. The gradient colors on the RL agent represent its learning progress, with white indicating the initial state. When the color aligns with a data batch, it signifies that the agent has learned the current causal mechanism. Instead of learning from scratch, online DAG learning needs to incrementally and efficiently adapt to continuously arriving data batches and non-stationary data distributions.

Figure 2: (a) The pipeline of MARLIN across three consecutive system states. For each batch, MARLIN learns the DAG using the intra-batch single-step RL algorithm, which includes state-specific and state-invariant RL agents optimizing their policies through an actor-critic approach. Detailed network architecture and variables are explained in Section Incremental Multi-Agent Reinforced DAG Learning . MARLIN facilitates efficient incremental DAG learning by disentangling state-specific and state-invariant causal relationships.

Panel of Figure 3 — Figure 3: Average performance of DAG learning across all states on synthetic Linear-Gaussian datasets, varying (a) DAG scale ( $d=\{20,50,100\}$ ) and (b) transition noise rate ( $e=\{0,1,5\}$ ) for MARLIN and other baselines. The shaded area represents the standard deviation; $\uparrow$ indicates that higher values are better, while $\downarrow$ indicates that lower values are better.

		TPR $\uparrow$	FDR $\downarrow$	SHD $\downarrow$	AUROC $\uparrow$	SID $\downarrow$	ATB $\downarrow$
QR	PC	0.30(0.01)	0.65(0.02)	83.2(1.3)	0.58(0.00)	330.0(6.8)	$-$
	NOTEARS	0.28(0.01)	0.15(0.03)	78.0(1.9)	0.63(0.00)	270.0(6.5)	$-$
	GOLEM	0.36(0.01)	0.35(0.02)	78.2(1.4)	0.65(0.01)	245.0(8.6)	$-$
	D-GNN	0.31(0.00)	0.38(0.05)	86.5(3.1)	0.63(0.01)	264.0(5.9)	$-$
	RL-BIC	0.84(0.02)	0.30(0.02)	26.3(2.1)	0.89(0.01)	102.0(6.1)	330(60)
	CORL	0.88(0.01)	0.25(0.01)	21.1(0.7)	0.92(0.01)	78.1(11.1)	416(38)

Table 1: DAG learning performance on synthetic QR and GP datasets with standard deviations reported in parentheses. A dash (

-

) for ATB indicates methods with notably poor performance. Bold indicates the best performance;

\uparrow

indicates higher is better, and

\downarrow

indicates lower is better.

Figure 4: Overall performance on the SWaT dataset across (a) PR@ $K$ , (b) AP@ $K$ , and (c) MRR metrics.

	PR@1	PR@3	PR@5	AP@1	AP@3	AP@5	MRR	ATC $\downarrow$
PC	16.7%	33.3%	50.0%	16.7%	27.8%	36.7%	35.2%	51
NOTEARS	38.9%	55.6%	72.2%	38.9%	50.0%	57.8%	54.4%	88
GOLEM	11.1%	27.8%	61.1%	11.1%	18.5%	32.2%	30.1%	227
D-GNN	33.3%	50.0%	72.2%	33.3%	40.7%	51.1%	47.9%	315
RL-BIC	33.3%	44.4%	72.2%	33.3%	40.7%	52.2%	49.7%	171
CORL	27.8%	72.2%	88.9%	27.8%	51.9%	65.6%	52.8%	141

Table 2: RCA Performance on OB dataset. All metrics except ATC are better when their values are higher.

		TPR $\uparrow$	SHD $\downarrow$	AUROC $\uparrow$	SID $\downarrow$	ATB $\downarrow$
$d=20$	MARLIN	0.99(0.01)	5.24(0.8)	0.99(0.00)	9.6(2.4)	26(2)
$d=20$	MARLIN-S	0.96(0.01)	14.5(1.1)	0.97(0.00)	22.4(1.5)	16(2)
$d=50$	MARLIN	0.92(0.02)	38.9(8.4)	0.95(0.01)	302(41.9)	182(23)
$d=50$	MARLIN-S	0.88(0.02)	82.1(11.8)	0.90(0.01)	401.6(46.1)	195(18)
$d=100$	MARLIN	0.85(0.03)	105.5(10.1)	0.93(0.01)	1713.0(85.9)	1321(105)
$d=100$	MARLIN-S	0.82(0.02)	180.6(6.2)	0.86(0.01)	2240.3(67.7)	1687(111)

Table 3: Ablation study results on synthetic LG datasets with varying DAG scales (

d={20,50,100}

Causal Discovery

Causal discovery infers cause-and-effect structures from observational and interventional data, distinguishing causal relationships from correlation.

See all 221 papers

Tags for DAGs: Graph Refinement with Meta-Informed Relations
Jun 24, 2025Florian Peter Busch, Moritz Willig, Florian Guldan +2Causal Discovery Causal Structure Learning
Computer Science Department, Technical University of Darmstadt · Hessian Center for AI (hessian.AI) · German Research Center for AI (DFKI) +2
From Causal Graphs to Markovian States: Multi-Order State Exposure for Deep RL
May 8, 2026Jiamin Xu, Jacqueline Maasch, Kyra GanMarkov Decision Processes Causal Representation Learning
Cornell Tech, New York, NY
Sparse Additive Model Pruning for Order-Based Causal Structure Learning
Feb 17, 2026Kentaro Kanamori, Hirofumi Suzuki, Takuya TakagiCausal Structure Learning Causal Discovery
Artificial Intelligence Laboratory, Fujitsu Limited

Jun 24, 2025J/K move · Enter open · S save

Tags for DAGs: Graph Refinement with Meta-Informed Relations

Florian Peter Busch, Moritz Willig, Florian Guldan, Kristian Kersting+1

Computer Science Department, Technical University of Darmstadt · Hessian Center for AI (hessian.AI) · German Research Center for AI (DFKI)+2

Causal Discovery Causal Structure Learning

Open paper AskPDF arXiv

Causal discovery has shifted from data-centric methods to hybrid strategies that integrate semantic knowledge from experts or large language models (LLMs). Such external information is vital for identifying causal structures beyond the Markov Equivalence Class (MEC), which data alone cannot resolve. However, expert availability is often limited, and LLMs frequently misidentify causal directions in specialized domains. To overcome such shortcomings, we propose a tag-based approach that leverages semantically meaningful labels while deriving causal directionality directly from data. Using variable-level tag assignments from available sources (e.g., LLMs), our tags for DAGs method learns from identifiable data structures to extract higher-level causal relations. These are then used to orient undirected edges, enabling causal discovery to move beyond the MEC without reliance on fallible external knowledge.

Abstract

Causal Discovery

Explore similar work

Tags for DAGs: Graph Refinement with Meta-Informed Relations

From Causal Graphs to Markovian States: Multi-Order State Exposure for Deep RL

Sparse Additive Model Pruning for Order-Based Causal Structure Learning