- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper starts with a causal graph produced by an existing method and tries to improve it one edge at a time. A reinforcement-learning agent suggests changes, a graph score decides whether to accept them, and an archive keeps the candidates. The paper gives one result about how long it may take to reach a graph that cannot be improved by a single edit, and another about choosing from a saved set of graphs using fresh data. It tests the approach on six datasets.
Critical strengths
-
Improving an existing graph is a practical goal. On Alarm, the method reduces the graph's structural Hamming distance from 56 to 26 after starting from GES (Table 1).
-
The authors include simpler search controls, which help assess whether the learned agent is needed.
Critical weaknesses
-
The mathematical guarantees do not show that the tested learning method recovers the right causal graph. Keeping the starting graph among the candidates automatically prevents the method from returning a lower-scoring graph. The first theorem applies to any search rule that keeps trying possible edits, not specifically to reinforcement learning; it also depends on an unspecified measure of how far the start is from a local stopping point. A graph where no single edit improves the score can still be causally wrong. The second theorem requires choosing among candidates using fresh data, but Section 5.1 says the main experiments choose using the same data used for search. The paper should state clearly which guarantees apply to its reported results.
-
The results do not clearly show what the learned search agent adds beyond a good starting graph and simpler search. On Sachs, starting from GES, hill climbing gets a graph distance of 26 while the learned method gets 28 (Table 10). The much better result of 10 starts from GraN-DAG, but the paper does not try hill climbing from that same starting point. The learned method does better on Alarm, so the evidence is mixed. A fair comparison on Sachs needs the same starting graph, score, allowed edits, and search budget. The paper also needs to justify its custom combined evaluation score and specify the limits behind the many “NC” (no result) entries.
Questions for authors
- Which guarantees actually apply to the graphs in Table 1, given that they were chosen using training data?
- What happens if hill climbing starts from GraN-DAG on Sachs with the same score, edits, and search budget as the learned method?
- What time and memory limits produced the “NC” results, and what settings were used for each baseline?
2 comments
Response to Reviewer PAcY (Part 2)
Q1. “Which guarantees actually apply…”
In revised Table 1, the WS-GD and WS-GES graphs are selected from their frozen candidate archives using independent held-out data (§5.1 and Appendix F.3).
- Eq. (8) guarantees that the selected graph’s held-out score is at least as high as the retained initializer’s score, because both are evaluated using the same score.
- Theorem 1 bounds the expected number of proposals until the continuing search first reaches a training-score 1-optimum, under the stated progress and exploration assumptions. This bound concerns the search trajectory. Certifying 1-optimality of a particular Table 1 graph requires checking its admissible single-edge neighbors.
- Theorem 2 governs the final choice from the frozen archive using independent data. It bounds the probability of choosing a population-suboptimal archive candidate when the sample-size condition in Eq. (15) holds. Appendix C.1 (Table 10) reports plug-in estimates. Table 1 reports structural accuracy separately through SHD, TPR, and FDR.
Q2. “What happens if hill…”
DDQN achieves SHD 10 and -greedy hill climbing achieves SHD 11 at a matched budget of candidate-score requests on Sachs. Both start from the same GraN-DAG graph (SHD 12), use the same training Copula-BIC score, and have the same admissible single-edge edits (Appendix D.4, Tables 15–16). Against the strongest classical comparator in each of the other matched comparisons, DDQN achieves SHD 26 vs. 31 on Alarm and 84 vs. 88 on Hepar2.
Q3. “What time and memory…”
The Table 1 baselines ran on a single 40 GB A100 with a 12-hour wall-clock limit per run. NC indicates that a run returned no result within those resource limits.
We have added the implementation and settings for each baseline to Appendix F.2 (Tables 25–26 and the accompanying text). The appendix lists the configurations used with gCastle 1.0.4 and documents the separate KCRL implementation, which uses TensorFlow 1.13.
Response to Reviewer PAcY (Part 1)
Thanks for insightful comments. We have carried out additional study (included in revised version). We provide response below:
W1. “The mathematical guarantees do…”
Exact causal recovery. Agreed. Score-monotone single-edge search methods, such as greedy hill climbing and the greedy phase of Max-Min Hill-Climbing, certify 1-optimality when no admissible single-edge edit strictly improves the score. A 1-optimum can still be causally wrong. Corollary 1 states the additional condition under which a reachable 1-optimum belongs to the target Markov equivalence class. The advance over RL-BIC (Zhu et al., 2020) and KCRL (Hasan and Gani, 2022) is a guarantee on the RL-guided search itself. Their published search procedures do not establish that they reach a 1-optimum. Under the stated conditions, Theorem 1 bounds the expected number of proposals until our search first reaches one.
Retaining the initializer. Agreed. Keeping the initializer in the archive guarantees that the selected graph scores at least as well as the initializer on the score used for selection. We state this deterministic property separately in Eq. (8). Theorem 1 quantifies the effort to reach a 1-optimum. Theorem 2 bounds the probability of selecting a population-suboptimal graph from the frozen archive.
Generality of Theorem 1 and the role of DDQN. We designed the framework so that any proposal policy that maintains persistent exploration can be used within the same score-monotone search. DDQN is our choice for prioritizing promising edits, and a future policy can replace it while retaining the guarantee under the same conditions. The new matched comparisons against hill climbing, greedy search, and beam search show the empirical value of DDQN (Appendix D.4). Appendix E.3 also makes the progress measure concrete. On enumerable instances, warm starts reduce the mean exact longest-improving-path depth from 25.6 to 15.1–19.4 (Table 22). On Sachs, from the same GraN-DAG initializer, DDQN reaches certified 1-optimality in 3,500 median proposals, compared with 7,000 for hill climbing (Table 23).
Applicability of Theorem 2 to Table 1. In the original submission, we reused the search data for final selection to keep the data available to the compared methods the same. We agree that this protocol did not meet Theorem 2’s independent-evaluation requirement. In revised Table 1, the WS-GD and WS-GES entries report the winners selected using the score in Theorem 2 on independent evaluation data. Before scoring those data, we freeze the candidate archive, rank transform, fitted regressions, and penalty (§5.1 and Appendix F.3). The protocol meets the theorem’s independence requirement. SHD, TPR, and FDR report structural recovery empirically.
W2. “The results do not…”
We now provide detailed comparisons with hill climbing, best-improvement greedy search, and beam search using matched initial graphs, scoring functions, and admissible edits (Appendix D.4, Tables 15–16). At a common budget of 100,000 candidate-score requests, DDQN achieves the lowest SHD in all three new matched comparisons. It reaches 10 vs. 11 on Sachs from GraN-DAG, 26 vs. 31 on Alarm from GES, and 84 vs. 88 on Hepar2 from GraN-DAG, against the strongest classical comparator in each case. The SHD advantage also holds at matched wall-clock budgets on Sachs and Hepar2. The only exception across the comparisons discussed here is the original GES-start experiment on Sachs, where hill climbing reaches SHD 26 versus 28 for DDQN. The new GraN-DAG comparison directly tests the initializer used for the strongest Sachs result.
The composite score in Eq. (16) gives equal weight to recall, precision, and a bounded SHD term so readers can summarize the three metrics on a common scale. We report each metric separately to show trade-offs. For example, on Hepar2, DDQN improves SHD and raises TPR from .35 to .54 relative to best-improvement greedy search, while FDR also rises from .32 to .51. The composite score plays no role in search or candidate selection.
Appendix F.2 lists the per-method baseline settings and specifies the 12-hour wall-clock limit on a 40 GB NVIDIA A100. NC denotes that a run returned no result within those compute limits.
Response continued in next comment