acceptodds
Under review as a conference paper at ICLR 2027

Causal Structure Refinement with Warm-Start Reinforcement Learning and Finite-Sample Guarantees

Abstract

Causal structure learning from observational data is challenging due to the combinatorial search over directed acyclic graphs and the difficulty of reliable model selection under finite samples. Reinforcement learning (RL) offers a flexible framework for exploring the space of graph structures, but remains largely heuristic and lacks statistical guarantees. We propose a warm-start RL framework that recasts causal structure learning as refinement of an existing graph. Starting from an initial graph, the method performs a sequence of local edge modifications guided by a learned policy, while maintaining a dynamically constructed candidate set for selection. We adopt a copula-based BIC score that extends BIC to data with non-Gaussian marginals through a rank-based Gaussian-copula construction. We establish two results. First, under a monotone progress-potential condition, we bound the expected number of proposals required to reach a 1-optimal graph, with the bound scaling linearly in the warm-start depth. Second, the population-best fitted candidate in the explored archive is selected, using independent data, with high probability under a variance-adaptive Bernstein bound. Empirically, refinement improves the composite score of its initializer on all six benchmarks without increasing SHD, including the 100- and 223-node benchmarks where most baselines do not converge. Compared to RL without warm start, our approach achieves over improvement in Score, up to gains in TPR, and up to 50% reduction in structural error (SHD) on the two networks where this ablation was run.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Causal Structure Learning, Warm Start, RL

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_PAcYOpenReview ↗
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
  1. 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).

  2. The authors include simpler search controls, which help assess whether the learned agent is needed.

Critical weaknesses
  1. 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.

  2. 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
  1. Which guarantees actually apply to the graphs in Table 1, given that they were chosen using training data?
  2. What happens if hill climbing starts from GraN-DAG on Sachs with the same score, edits, and search budget as the learned method?
  3. What time and memory limits produced the “NC” results, and what settings were used for each baseline?
2 comments
AuthorsOpenReview ↗

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

AuthorsOpenReview ↗

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 ε\varepsilon-greedy hill climbing achieves SHD 11 at a matched budget of 10510^5 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.

Reviewer_SgPeOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
2(+1)
Read review
Paper summary

Problem task:

  • causal discovery/structure learning, starting with an initial graph

Approach:

  • refinement (adding/removing/flipping edges within space of DAGs) using reinforcement learning. All proposed graphs are taken, and then a final graph is selected using fresh data

Experiments:

  • 6 datasets with several baselines and some control/ablation methods.
Critical strengths

None

Critical weaknesses

Writing:

  • This submission does not adequately cite prior work. There are almost no citations outside of the related work section, which is clearly AI generated and very confusing. It is therefore very hard to tell which parts of the paper are novel.
  • The rest of the paper is also clearly AI generated, and fails to introduce, contextualize or explain its method and theory.

Novelty:

  • The algorithm appears to be a collection of established techniques, and it appears that almost all of the algorithm appears in https://arxiv.org/pdf/2510.20106, which is not cited.

Significance of the theoretical guarantees:

  • it is unclear to me that the theoretical guarantees have any significance, as e.g. the RL results clearly will not be worse than the initial graph as the initial graph is automatically included in the RL outputs.
  • Similarly, I think the hitting time guarantees would apply equally well with and without the warm start, and include essentially uncomputable terms (the longest path of improvements within the DAG space)
Questions for authors

None.

3 comments
AuthorsOpenReview ↗

Response to Reviewer SgPe (Part 1)

W1. “This submission does not…”

We wrote the Related Work section and used AI assistance only for editing and formatting, as disclosed. Concentrating citations in a dedicated Related Work section is an established practice in page-limited ML conferences. Kingma and Welling’s Auto-Encoding Variational Bayes (ICLR 2014), winner of the 2024 ICLR Test of Time Award, has zero citations in its Introduction and cites five distinct sources elsewhere in the main text outside Related Work. DeepLIFT (ICML 2017), Task-based End-to-end Model Learning in Stochastic Optimization (NeurIPS 2017), and Learning Through Dialogue Interactions by Asking Questions (ICLR 2017) also have citation-free introductions and few citations outside Related Work. Similarly, our work also has a short introduction with no citation.

As far as our work is concerned, Section 2 cites 19 papers. Section 3 credits Liu et al. (2009) for rank Gaussianization, Schwarz (1978) for BIC, and Van Hasselt et al. (2016) for Double DQN where we use each component. Beyond the main text, Appendix B gives the full derivations and proofs. The appendices also contain seven citations to distinct references, covering Markov equivalence and the six benchmark datasets.

Contribution. Our main contribution is a causal graph refinement framework with provable search and selection guarantees. It starts from a DAG returned by an existing discovery algorithm and uses a learned policy to prioritize edge edits under a finite search budget. We bound the expected number of proposals needed to reach a training-score 1-optimum under a progress condition. We also bound the probability of selecting a population-suboptimal candidate from the frozen archive using independent data. A second contribution is the construction and analysis of Copula-BIC. With the clipped rank transform and regression fits frozen, each candidate’s per-observation score is quadratic in the transformed variables. We derive explicit Lipschitz and score-difference bounds and use the latter in the finite-sample selection theorem.

W2. “The rest of the…”

As mentioned above, we wrote the manuscript, including the methodology, theoretical analysis, and proofs. As disclosed, we used AI assistance only for editing and formatting.

Theory. Section 4 states the assumptions, guarantees, and proof sketches in the main text. Theorem 1 bounds the expected number of proposals needed to reach a local optimum of the training score under the stated progress and exploration assumptions. Theorem 2 bounds the probability of selecting a population-suboptimal graph from the frozen candidate archive using independent evaluation data. To fit the main-text page limit, we provided the complete derivations and proofs in Appendix B.

Method. Section 1 and Figure 1 introduce the causal graph refinement pipeline, and Section 2 situates it within classical, prior-guided, and RL-based causal discovery. Section 3 defines the Copula-BIC score, the feasible graph edits, and the Double DQN proposal, reward, and acceptance rules. Algorithm 1 gives the full update sequence. Appendix A provides additional details such as the observational model, notation, implementation details, and training settings.

Connection between method and theory. Algorithm 1 explicitly annotates the steps used by each theoretical result. It marks the champion reset (line 6), persistent exploration (line 9), and score-monotone acceptance (lines 13–14) as the mechanisms underlying Theorem 1. Line 11 identifies the Copula-BIC score in the reward and links it to Lemmas 1–2. Line 12 archives every proposal, including rejected proposals. Lines 29–31 show exactly what is frozen and how the archive is evaluated on independent data for Theorem 2. Table 4 summarizes these dependencies.

W3. “The algorithm appears to…”

The algorithmic overlap with arXiv:2510.20106 reflects its relationship to this submission. We have clarified that relationship with the AC, SAC, and PC. Our response to Weakness 1 identifies the contributions of the submission, including the separate search and selection guarantees and the analysis of Copula-BIC.

Response continued in next comment

AuthorsOpenReview ↗

Response to Reviewer SgPe (Part 2)

W4. “it is unclear to…”

While it is true that retaining the initializer in the archive ensures that the selected graph scores at least as well as the initializer on the score used for selection, Theorem 1 quantifies how many proposals the search needs, in mean sense, to reach a training-score 1-optimum under the stated progress and persistent-exploration conditions. The initial progress depth enters the bound explicitly, so a shallower starting point tightens the bound on expected search effort. Similarly, Theorem 2 addresses the final selection step. It bounds the probability that finite-sample noise causes the held-out selector to choose a population-suboptimal graph from the frozen archive. We derive explicit Lipschitz and score-difference bounds for the fitted Copula-BIC score and use the score-difference bounds in the selection analysis.

Appendix E.3 (Tables 22–23) reports exact progress depths and observed proposal counts with and without warm starts. Appendix C.1 (Tables 9–10) reports the held-out selection results and plug-in sample-size estimates.

W5. “Similarly, I think the…”

Theorem 1 establishes the following bound on the expected number of proposals needed to reach a 1-optimal DAG under the training score (Eq. (12)).

\le \sum_{k=1}^{h(G_0)}\frac{A_k}{\varepsilon_\star\phi_k} \le \frac{h(G_0)A_{\max}}{\varepsilon_\star}.$$ A cold start is a special case obtained by setting $G_0=\varnothing$. The initializer enters the bound through $h(G_0)$. With a common action-count bound and exploration rate, a larger cold-start depth increases the hitting-time upper bound in direct proportion. For the longest-path potential in Appendix B.1, this increase is guaranteed whenever the warm-start graph is reachable from the empty graph by $L$ strictly score-improving edits. In that case, $h^\star(\varnothing)\ge L+h^\star(G_{\mathrm{warm}})$. Appendix B.1 uses the longest improving path to establish the existence of a valid potential. The longest path can be exponentially large. Appendix E.3 computes it exactly on enumerable instances and measures hitting times directly on Sachs and Alarm. On enumerable instances, the mean exact depth is 25.6 from the empty graph and 19.4, 16.7, and 15.1 from PC, GES, and GraN-DAG starts, respectively (Table 22). On Sachs, all five DDQN runs reach certified 1-optimality from both initializations, and the median proposal count falls from 8,200 with the empty graph to 3,500 with the GraN-DAG warm start. On Alarm, DDQN reaches certified 1-optimality within the proposal cap in 4/5 runs from GES and 2/5 runs from the empty graph (Table 23).

Thank you for the detail response.

I acknowledge that my original review was unnecessarily strongly and bluntly worded. My concerns relate to the clarity, novelty and significance of the contributions, rather than the text's provenance. I also note the clarification to the earlier preprint.

I still believe the writing is not at a high enough standard, especially in the Related Works section. This is particularly relevant as the paper draws on techniques and works at the intersection of several prior works & fields.

At the moment, this section lists existing methods tersely, with little-to-no explicit description of what these methods have in common, and mixes this with negative statements, the defensive limitations of the current paper. The motivations for this paper are not clearly placed in context of the prior work. This makes it very hard to identify the contributions of the paper and to place these in context of prior work.

To effectively relate this work to the literature and argue that this work is novel, this section should explain the core concepts within relevant lines of research, and how these relate to each other. Further, the trade-offs and research gaps can be introduced here, and then how the current work addresses these gaps and builds on prior work.

Turning to the theory, I appreciate the added content about hitting times, which is good to place the theory in context better. I think my general point still stands, though, that the theoretical guarantees are not very related to the algorithm/practical scenarios. My understanding is that Theorem 1 would apply equally well to the hill-climbing baseline, which means that it does not effectively set the new method apart from it. Further, the monotone improvement condition is only assumed and not proved, which limits its usefulness to theoreticians. Theorem 2 does indeed also apply to any method that produces a set of proposals, though this is reasonable as it is intended to show that empirical selection performs well. This makes these theorems weak evidence in support of developing a new algorithm.

I have updated my initial review with a new score of 2. Thank you for the responses again.

Reviewer_ri6WOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a warm-start reinforcement learning framework for causal structure discovery, aiming to refine an existing DAG rather than learning the graph from scratch. The method employs a Double DQN policy to propose local edge modifications, uses a copula-based BIC score to accept improvements, and maintains an archive of candidate graphs. The authors establish a conditional hitting-time bound for reaching local optimality and a finite-sample selection guarantee for a frozen candidate set evaluated on independent observations.

Critical strengths
  • Refining existing causal graphs is a useful direction, especially when established discovery methods provide reasonable but imperfect initial structures. The proposed framework is flexible enough to incorporate different initializers without requiring causal discovery to restart from an empty graph.

  • The separation of graph initialization, RL-based proposal generation, score-based acceptance, and candidate selection makes the overall framework relatively easy to follow.

  • The experimental section includes several relevant baselines and component-level ablations. In particular, the Alarm results show that learned refinement can improve structural accuracy beyond the GES initializer and the reported hill-climbing controls.

Critical weaknesses
  • The central framework combines several established ideas: warm-starting from an existing solution, local graph editing, monotone score-based acceptance, Double DQN, and rank-based Gaussian-copula scoring. While their integration is reasonable, I find it difficult to identify a sufficiently distinctive algorithmic contribution beyond applying these components together. More importantly, the paper does not convincingly establish why reinforcement learning is essential for the refinement process. The central advantage could plausibly arise from better initialization and additional local search under a modified scoring function. It seems the major contribution is still simply integrate different algorithms and blocks.

  • Theorem 1 relies on Assumption 2, which requires a monotone progress potential and improving actions that reduce this potential. However, the analysis applies equally to randomized hill climbing and does not depend on learning a Q-function. Appendix B.1 further shows that an appropriate potential can be defined using the longest improving path, whose length may be exponentially large.

  • The comparison with hill climbing is particularly important because it directly tests whether DDQN offers an advantage over conventional local refinement. However, these controls are reported only for Sachs and Alarm. On Sachs, the strongest result uses a GraN-DAG initializer, whereas the reported hill-climbing controls start from GES. This prevents a direct attribution of the improvement to the learned policy. The Alarm results are encouraging, but one strong matched-initializer comparison is insufficient to establish a consistent advantage across different graph structures and problem sizes. More comprehensive evaluations with identical initial graphs, scoring functions, proposal budgets, and computational resources are needed.

  • Section 3.1 motivates Copula-BIC through continuous marginal transformations and a Gaussian-copula model, but several benchmark networks, including Child, Alarm, Hepar2, and Andes, are commonly defined as discrete Bayesian networks. The manuscript does not sufficiently explain whether its experiments use their original categorical distributions or alternative continuous data-generating mechanisms.

Questions for authors
  • What is the specific advantage of DDQN over simpler refinement policies? Could the authors provide comparisons against other basic way, such as hill climbing, stronger greedy or beam-search variants, and other modern score-based search methods using identical initial graphs and matched computation, particularly for the GraN-DAG initializer and larger benchmarks?

  • How informative is the warm-start hitting-time bound in practice? Can the authors characterize or estimate the progress potential and warm-start depth for any experimental setting? Is there theoretical or empirical evidence that these quantities are smaller under warm starts than under cold starts?

  • Why is the held-out selection procedure from Theorem 2 not used in the primary experiments? Would it preserve the reported improvements in SHD and TPR? Can the authors quantify the evaluation sample size required for the bound to become informative on representative benchmarks?

  • How are the observations generated and represented for the discrete Bayesian-network benchmarks? If categorical observations are used, what justifies the Gaussian-copula regression score and its causal interpretation? If continuous data are generated from the benchmark graph structures, the underlying structural equations and sampling procedure should be specified.

Based on those unresolved questions, my initial score is 2.

4 comments
AuthorsOpenReview ↗

Response to Reviewer ri6W (Part 1)

Thanks for all insightful comments. We provide response below:

W1. “The central framework combines…”

Our contribution is a warm-start causal graph refinement framework that learns to prioritize admissible edge edits and provides separate guarantees for search and final selection. While it is true that retaining the initializer in the archive ensures that the selected graph scores at least as well as the initializer on the score used for selection, it is important to quantify how many proposals the search needs, in means sense, to reach a training-score 1-optimum under the stated progress and persistent-exploration conditions. Theorem 1 quantifies this effort. The initial progress depth enters the bound explicitly, so a shallower starting point tightens the bound on expected search effort. Similarly, Theorem 2 addresses the final selection step. It bounds the probability that finite-sample noise causes the held-out selector to choose a population-suboptimal graph from the frozen archive. We derive explicit Lipschitz and score-difference bounds for the fitted Copula-BIC score and use the score-difference bounds in the selection analysis.

The new controls also help isolate the value of the learned policy. From the same initializer, with the same Copula-BIC score and admissible edits, and at the same score-request budget, DDQN achieves SHD 10 vs. 11 on Sachs, 26 vs. 31 on Alarm, and 84 vs. 88 on Hepar2 against the strongest reported classical comparator for each start (Appendix D.4, Table 15). Setting the discount to zero increases SHD from 26 to 31 on Alarm and from 10 to 11 on Sachs (Appendix D.5, Table 17). The guarantees apply to the framework, and these comparisons show where learning and multi-step credit assignment improve its empirical performance.

W2. “Theorem 1 relies on…”

Theorem 1 is indeed policy-agnostic. Under Assumption 2, it applies to any proposal policy that supplies persistent exploration within our monotone-acceptance and champion-reset framework, including randomized hill climbing. This generality is a strength. A future proposal policy can replace DDQN and inherit the same hitting-time guarantee as long as it satisfies the exploration condition. We use DDQN to prioritize edits within a finite budget, and the matched comparisons in Appendix D.4 evaluate the empirical benefit of that choice.

Appendix B.1 constructs a valid progress potential from the longest improving path. Under persistent exploration, this gives a finite expected hitting-time bound for the continuing search. The longest path can be large, so a polynomial bound requires additional control of the progress depth and exploration rate. Appendix E.3 (Tables 22–23) shows why the initializer matters in practice. On the enumerable instances, warm starts reduce the mean exact depth from 25.6 to 15.1–19.4. On Sachs, all five DDQN runs reach certified 1-optimality under both initializations, and the median proposal count falls from 8,200 with the empty graph to 3,500 with the GraN-DAG warm start.

W3. “The comparison with hill…”

We agree that comparison with hill climbing is important for isolating the contribution of the learned proposal policy. Accordingly, we have added the missing GraN-DAG-matched comparison on Sachs and extended the evaluation to Hepar2, a 70-variable network (Appendix D.4, Tables 15–16). Within each benchmark, the refiners start from the same graph and use the same Copula-BIC score and admissible edits. Each method has a common budget of 100,000 candidate-score requests, including requests made during neighborhood scans.

On Sachs, the shared GraN-DAG initializer has SHD 12. Hill climbing, best-improvement greedy search, and beam search each reach 11, while DDQN reaches 10. On Alarm, DDQN reaches 26, compared with 31 for beam search, the strongest classical comparator in the matched evaluation. On Hepar2, at 10510^5 score requests, DDQN reaches 84, compared with 88 for best-improvement greedy search and 94 for beam search. The SHD advantage also holds under matched wall-clock budgets on Sachs and Hepar2. The original GES-start comparison on Sachs still favors hill climbing in SHD (the only case). The new GraN-DAG control shows a learned-policy benefit from the same starting graph under the matched protocol, and the Hepar2 comparison extends the evidence to a larger graph.

(Continued in next comment)

AuthorsOpenReview ↗

Response to Reviewer ri6W (Part 2)

W4. “Section 3.1 motivates Copula-BIC…”

For Child, Alarm, Hepar2, and Andes, we use the original categorical benchmark distributions and sampling procedures. All methods receive the same integer-coded observations. Copula-BIC uses midranks to handle ties and serves as a working score for ranking graph edits on these data.

Appendix C.2 (Table 11) reports two empirical comparisons. With the original encoding, DDQN with Copula-BIC achieves lower SHD than DDQN with BDeu on Child (21 vs. 24) and Alarm (26 vs. 30). Under BDeu, DDQN still improves SHD over hill climbing on Child (24 vs. 26) and Alarm (30 vs. 36), showing that the benefit of learned proposals extends to a discrete score.

One possible explanation for the Copula-BIC results is that its additive regression pools information across parent configurations. A discrete conditional probability table has separate parameters for each configuration, so the number of parameters can grow rapidly with the number of parents. The more parsimonious regression may give more stable score comparisons when some configurations are sparsely observed. For binary variables, the midrank transform is an affine recoding of the two levels, so this explanation concerns the regression score and its parameterization. The continuous Gaussian-copula assumptions in Sec 3.1 delimit the causal interpretation.

Q1. “What is the specific…”

DDQN uses transitions collected during refinement to update which feasible edits it proposes next. Appendix D.4 now compares it with uniform proposals, hill climbing, best-improvement greedy search, and beam search from matched initial graphs. On Sachs, DDQN reaches SHD 10 at 10410^4 score requests, while the strongest reported classical result is 11. On Hepar2, at a common budget of 10510^5 requests, DDQN reaches SHD 84, best-improvement greedy search reaches 88, and beam search reaches 94. Increasing the classical methods’ budgets to 10610^6 requests brings greedy search to 86 and beam search to 88 (Table 16). The equal-time comparisons also favor DDQN in SHD on both datasets.

Q2. “How informative is the…”

To empirically quantify the effect of warm starts on progress depth and hitting time, Appendix E.3 now reports both exact depths and observed hitting times. On enumerable instances, the mean exact longest-improving-path depth is 25.6 from the empty graph and 19.4, 16.7, and 15.1 from PC, GES, and GraN-DAG starts, respectively (Table 22). The theoretical comparison is conditional. If a warm start G0G_0 is reachable from the empty graph in ℓ\ell strictly improving edits, then h⋆(∅)≥ℓ+h⋆(G0)h^\star(\emptyset)\ge \ell+h^\star(G_0). With the exploration rate and action-count bound fixed, the upper bound in Eq. (12) scales linearly with this depth.

On Sachs, all five DDQN runs reach certified 1-optimality from both initializations. The median falls from 8,200 to 3,500 proposals with the GraN-DAG start. On Alarm, DDQN reaches certified 1-optimality within the proposal cap in 4/5 warm-start runs and 2/5 cold-start runs (Table 23).

Q3. “Why is the held-out…”

In the original submission, we used the training score for final selection to keep the data available to the compared methods the same. This protocol did not satisfy the independence requirement of Theorem 2. In revised Table 1, the WS-GD and WS-GES entries report the winners selected using the score specified in Theorem 2 on independent evaluation data, after freezing the candidate archive, rank transform, fitted regressions, and penalty.

Held-out selection preserves the structural gains. Appendix C.1 (Table 9) compares both selectors on the same frozen archives. On Alarm, mean SHD falls from 56 for the initializer to 24.4 with training-score selection and 25.2 with held-out selection. This retains about 97% of the SHD improvement, and mean TPR is 0.74, 0.82, and 0.81, respectively. On Sachs, both selectors attain mean SHD 10.8 from an initializer mean of 13.4, and mean TPR is 0.53 for the initializer, 0.56 for training-score selection, and 0.58 for held-out selection.

The available held-out samples exceed the plug-in estimates from Eq. (15) on Sachs (1,489 available vs. 380–382 estimated), Alarm (2,000 vs. 851–1,190), and Hepar2 (1,000 vs. 563–888). The smaller original datasets leave fewer observations for held-out evaluation on Child (200 available vs. 533–984 estimated) and DREAM (20 vs. 1,315). The formal error bound uses population score gaps and variances and a valid bound on centered score differences.

AuthorsOpenReview ↗

Response to Reviewer ri6W (Part 3)

Q4. “How are the observations…”

The observations for Child, Alarm, Hepar2, and Andes are categorical samples from the original benchmark distributions defined by their published conditional probability tables. The additional 2,000 Alarm observations used for held-out selection were forward-sampled from the published tables (Appendix F.3). All methods receive the same integer-coded observations. We use Copula-BIC as a working score for ranking graph edits and evaluate structural recovery against the benchmark DAGs. The causal interpretation in Sec 3.1 requires the stated continuous Gaussian-copula assumptions.

With DDQN fixed, Copula-BIC yields lower SHD than BDeu on Child (21 vs. 24) and Alarm (26 vs. 30). A plausible explanation is that the additive regression in Copula-BIC pools information across parent configurations, which can stabilize score comparisons when some configurations are sparsely observed. For binary variables, the midrank transform is an affine recoding, so this explanation rests on the regression parameterization. With BDeu fixed, DDQN improves SHD, TPR, and FDR over hill climbing on both benchmarks, showing that the empirical benefit of learned proposals extends to a discrete score (Appendix C.2, Table 11).

I thank the authors for their extensive clarifications and additional explanations. The empirical evidence has been substantially improved in the revised version. However, the algorithmic novelty and RL-specific theoretical contributions remain limited. In particular, the proposed method still appears to be largely an integration of several existing frameworks and techniques, rather than a sufficiently distinctive algorithmic contribution. As a result, I remain unconvinced of the paper's broader significance and practical value. Therefore, while I appreciate the authors' efforts in addressing my concerns, I will maintain my original score.

Comments on the paper

1 comment

Dear authors and reviewers,

The author-reviewer discussion period closes on November 18 (AoE). Please engage in response periods so that we have our issues discussed thoroughly.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.