{"id":"45273aab-50d4-44be-a149-6109ebff4040","arxiv_id":"2502.01527","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"MCTS-BN uses tree search over variable orderings, seeded by existing learning algorithms, to produce Bayesian networks with higher training-data BDeu scores than standard structure learners.","lead":"This paper adapts Monte Carlo tree search, an algorithm from game playing, to learn Bayesian network structures from data. The method searches over variable orderings, guided by existing learning algorithms, and improves the training-data BDeu scores of standard structure learners on six benchmark networks.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No control baseline isolates MCTS-BN's tree-search contribution; reported BDeu gains may come from sampling many base-guided orders rather than from the MCTS mechanism.","rationale":"The reader's weakest assumption is that training-data BDeu is equated with structural quality. That is a real concern, but the more load-bearing issue for the paper's central contribution is the absence of a control that isolates MCTS's search mechanism. Since MCTS-BN's rollout and expansion are heavily guided by the base algorithm's orders, the observed BDeu improvements could plausibly arise from the large number of evaluated candidate orders rather than from the UCT tree search. This would not make the algorithm useless, but it would weaken the claim that the paper's specific MCTS adaptation is what matters. The paper deserves credit for releasing code and datasets and for describing the algorithm precisely enough that the control is straightforward to implement. The issues are addressable with additional experiments, so the CONDITIONAL verdict remains appropriate; no adjustment is needed.","tokens_in":9652,"tokens_out":4462,"duration_ms":44688,"concrete_test":"Run MCTS-BN on the six bnlearn networks with the UCT selection in Section 3.2 replaced by a control that, at each iteration, picks an available action uniformly at random (or samples a complete order from the base BN), keeping the same guided rollout and the same 10,000 + n order-constrained HC evaluations, and then takes the best BDeu found. Compare final BDeu distributions over the 10 datasets. If the control matches or exceeds MCTS-BN's score, the MCTS tree-search component is not the source of the reported gains. Additionally, report held-out log-likelihood and structural Hamming distance to the gold standard for both variants, with means and standard deviations over the 10 datasets.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim in Section 4.3 ('MCTS-BN consistently proves beneficial across all base networks and algorithms used') is not supported by the experiments as reported, because the evaluation never isolates the MCTS component. In Section 3.3, MCTS-BN uses the base algorithm's topological order both to complete rollouts (σ+ = σ · σ↓X\\vars(σ)GES) and to decide the order of node expansions, and then runs 10,000 iterations of order-constrained HC, picking the best BDeu score. The natural control is to apply the same number of rollouts using random partial-order completion, or simply to sample many topological orders from the base BN and retain the best HC result. Without this control, the reported improvements are exactly what any 'try many candidate orders, keep the best' procedure would produce. The novelty claim — that the UCT-based tree search itself contributes to the improvement — therefore rests on an untested assumption. Even accepting BDeu as the objective, the paper does not show that MCTS-BN's exploration-exploitation balance is better than cheap random sampling of the same guided orders. Separately, all evaluation uses the training BDeu score that MCTS optimizes; no held-out likelihood, no structural accuracy against the gold standard, and no error bars are reported, so the size of the improvement is not tied to a validated quality measure. The 'gold standard upper bound' in Section 4.1 is also not a true upper bound: HC on one true topological order does not necessarily find the global optimum for that order, let alone over all orders, and the paper itself acknowledges that the true order may not be optimal for a finite sample.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MCTS-BN, a Monte Carlo Tree Search approach for Bayesian Network structure learning. MCTS-BN searches over topological orders of the variables; for each partial order, a rollout is completed using a topological order sampled from a base structural learning algorithm (GES, fGES, PC, or HC), and a Hill Climbing procedure restricted to the resulting order is run to produce a network whose BDeu score serves as the reward. The method is evaluated on six bnlearn networks with 10 datasets each, reporting training-data BDeu scores and execution times. The central claimed result is that MCTS-BN consistently improves the BDeu score of the base algorithms and sometimes exceeds the score of HC constrained to a true topological order of the gold-standard network.","tokens_in":9946,"tokens_out":3959,"duration_ms":36677,"significance":"If the claims are supported, MCTS-BN would be a generally applicable wrapper that improves upon base BN structure learners at the cost of additional computation, with the notable strengths of a reproducible implementation (code and datasets released) and a clear algorithmic description. However, the evidence as presented is weakened by (i) evaluating only the same training-data BDeu score that MCTS-BN optimizes, (ii) lacking a control condition that isolates the UCT tree-search component from merely sampling many guided orders, and (iii) reporting no error bars, significance tests, or independent quality metrics such as held-out likelihood or structural accuracy. The paper makes no theoretical guarantees, and its contribution is empirical; therefore these evaluation gaps are load-bearing for the central claim.","major_comments":[{"comment":"The evaluation metric is the training-data BDeu score, which is exactly the reward that MCTS-BN maximizes (Section 3.2). The claim in Section 4.3 that 'MCTS-BN consistently proves beneficial' is therefore only a statement about within-objective score optimization on the training sample. No held-out likelihood, edge-level comparison to the gold standard, or error bars/significance tests over the 10 datasets are reported. Because a heuristic with 10,000 iterations and a favorable initialization would be expected to raise the training score even without discovering genuinely better structures, this evidence does not by itself establish improved structural learning. I request per-dataset results with variance, a significance test, and ideally an independent metric (e.g., held-out likelihood or structural Hamming distance to the gold standard).","section":"§4.1 and §4.3"},{"comment":"The experimental design never isolates the contribution of the MCTS tree-search mechanism. In the guided-search procedure, rollouts are completed by concatenating the current partial order with a projection of a base-algorithm order, and node expansions are also reordered according to that base order. A natural and necessary control is to compare MCTS-BN against an equally cheap procedure that samples random partial-order completions or simply samples many base-algorithm orders and runs order-constrained HC on each, keeping the best result. Without such a control, the reported BDeu improvements may be entirely attributable to 'try many guided orders and keep the best', and the specific UCT exploration-exploitation balance -- which is the paper's claimed novelty -- remains untested. This is a load-bearing issue for the central contribution.","section":"§3.3"},{"comment":"The comparison against 'the gold standard's upper bound' is not well defined. The paper runs HC restricted to a true topological order and calls this an upper bound, but because BDeu is computed on a finite sample, the true ordering need not yield the maximum possible BDeu for that sample -- a fact the authors themselves acknowledge in the same paragraph ('the gold standard may no longer be the optimal model for that data'). Thus the statement in Section 4.3 that MCTS-BN 'surpasses the gold standard's upper bound in 4/6 BNs' is not a meaningful achievement unless the reference point is described accurately. Please relabel this as one reference baseline and explain what its violation indicates.","section":"§4.1"}],"minor_comments":[{"comment":"In the definition of σ+, 'σ↓A i produces the projection of σi over A' appears to be a typo; it should read 'the projection of σ over A'.","section":"§3.3"},{"comment":"The Tetrad version is given as '7.1.2-24' in the text and 'v7.1.2-2' in the footnote; please harmonize these references.","section":"§4.2"},{"comment":"Execution times are shown as averaged bars without error bars or a table of per-dataset values; given the 10 datasets, adding variance information would help assess the stability of the timing comparison.","section":"§4.3 / Figure 5"},{"comment":"The choice of the exploration constant C = sqrt(2)/100 is motivated by 'a good balance', but no sensitivity analysis is provided. Since the paper highlights the difficulty of tuning MCTS parameters, a brief study of the effect of C on the results would strengthen the presentation.","section":"§3.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript includes a DOI and a statement that the Version of Record is published in LNCS vol 1174. The editor may wish to verify how this arXiv submission relates to the already-published version and whether the review process here should account for that prior publication. The evaluation gaps described in the major comments are addressable with additional experiments (a control baseline without UCT, per-dataset variance/significance tests, and an independent metric), so a major revision seems appropriate rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know two things about this one. The MCTS-BN combination is genuinely new — MCTS over topological orders for BN structure learning, with rollouts and expansions seeded by orders sampled from GES, PC, or HC. And the empirical claims are plausible on their face: across six real-world BNs, the method improves the training BDeu score over the base algorithms, and the authors release code and data. But the central mechanism is not tested. There is no control that isolates the tree search itself.\n\nWhat the paper does well is specific. The adaptation of UCT to BDeu scores — normalizing by dataset size and standardizing rewards — is sensible. The guided rollout trick that completes a partial order using a base algorithm's order is clearly described and likely efficient. The experimental setup covers small and very large networks and reports iteration curves and timing. The authors also have the good sense to note that the true topological order may not be optimal on a finite sample, which many papers miss.\n\nThe soft spots are real, and the reader's report and stress-test note are on target. The missing control is the main one. MCTS-BN uses the base algorithm's order to complete every rollout and to decide expansion order, then runs 10,000 iterations of order-constrained HC and keeps the best BDeu. A natural baseline is: sample many topological orders from the base algorithm's DAG (or random partial completions), run the same HC, and keep the best. If that baseline matches MCTS-BN, the tree search's exploration-exploitation balance adds nothing beyond a more expensive way of sampling orders. The paper does not run this control, so the claim that MCTS-BN's search is the source of improvement is unsupported.\n\nA second issue is measurement. Evaluation is entirely on training BDeu, the very objective the method maximizes. There are no error bars, significance tests, held-out likelihood, or edge-level accuracy against the gold standard. The \"gold standard's upper bound\" label is misleading — HC on one true order is not a global optimum for that order, let alone over all orders.\n\nThese are fixable. Add the sampling control, add error bars, maybe one structural comparison, and the paper would be much stronger. As published, it is a useful practical heuristic with a clear mechanism and reproducibility, but the headline claim about MCTS benefits is overstated.\n\nIf you work on BN structure learning, this is worth engaging. It deserves serious peer review, though it needs revision before it should be accepted. I'd bring it to a reading group if the group cares about search heuristics for graphical models.","headline":"A genuinely new MCTS-over-orders heuristic for BN structure learning, with reproducible code and plausible BDeu gains, but the evaluation misses a key control and only measures the objective being optimized.","tokens_in":10497,"tokens_out":2733,"would_cite":false,"duration_ms":24315,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Monte Carlo tree search can be repurposed to search over variable orderings, and this paper shows that doing so raises the BDeu score of every standard Bayesian-network learner tested, sometimes above the score obtained from the true…","keywords":["Monte Carlo Tree Search","Bayesian network structure learning","topological order search","BDeu score","guided rollout","Hill Climbing","Greedy Equivalent Search","UCT"],"falsifier":"Compute held-out log-likelihood or edge recovery (e.g., structural Hamming distance to the gold-standard network) for MCTS-BN versus its base algorithms on the same ten datasets per network; if the higher training BDeu scores do not come with better generalization or better edge recovery, the paper's central benefit claim is refuted. Alternatively, a paired test across the ten datasets showing the BDeu gain over GES is not consistently positive would contradict the 'consistently beneficial' claim.","tokens_in":9472,"feed_emoji":"📈","tokens_out":10648,"duration_ms":84917,"temperature":0.7,"pith_summary":"This paper claims that a Monte Carlo Tree Search adapted to explore variable orderings—not network structures directly—reliably improves the Bayesian networks found by standard structural-learning algorithms. The method, MCTS-BN, builds partial orders of variables, completes each one with orders sampled from a base algorithm's learned network, and scores the result by running order-constrained Hill Climbing under the BDeu metric. On six real-world networks with ten datasets each, the authors report that MCTS-BN raises the starting BDeu score of every base algorithm used (GES, fGES, PC, HC). When seeded with GES orders, it even exceeds the score of Hill Climbing run with the true gold-standard topological order in four of the six networks. A sympathetic reader would take the paper as evidence that order-space search is a cheap, generic complement to DAG-space greedy search.","feed_headline":"Order search beats the true-order gold standard in 4 of 6 networks","feed_subtitle":"It lifts training-data BDeu scores for GES, fGES, PC, and HC on every benchmark network.","key_machinery":"The central mechanism is the MCTS tree over partial topological orders, driven by a modified UCT formula whose reward is the standardized normalized BDeu score (snBDeu) of an order-constrained Hill Climbing. Because random rollouts over n! orders are impractical for large networks, the paper introduces \"guided search\": topological orders sampled from the base algorithm's learned network are used both to complete partial orders during rollout (σ+ = σ concatenated with the projection of the sampled order over the remaining variables) and to fix the expansion order of actions at each node. This semi-randomized rollout is what makes the search feasible on networks of up to 1,041 variables, and it is the component that converts a generic MCTS into a structural-learning booster.","core_discovery":"The central claim is that optimizing the topological order is an effective lever for score-based Bayesian network structure learning, and that MCTS is a practical way to do that optimization at scale. In MCTS-BN each tree node is a partial variable order; an action appends one variable; and a rollout completes the order by concatenating the projection of a base algorithm's sampled order over the remaining variables. The completed order is handed to an order-constrained Hill Climbing, whose BDeu score—normalized by dataset size and standardized across the initial expansion—is backpropagated as the reward. The paper reports that this guided search consistently improves the starting BDeu score across all base algorithms and all six networks, that it narrows the gap when the base algorithm is weak, and that paired with GES it surpasses the score of Hill Climbing given a true topological order from the gold standard in 4/6 cases.","pith_inferences":["A plausible unstated corollary is that the order-search wrapper is score-agnostic: swapping BDeu for BIC or a held-out-likelihood criterion should preserve the mechanism, and we would expect similar score gains if order-constrained GES replaced order-constrained HC inside the rollouts.","The fact that the true topological order is beaten on training-data BDeu suggests that on finite samples the highest-scoring order is not the causal order; we would predict that under held-out evaluation the gap between MCTS-BN and the gold-standard order shrinks or reverses.","Because many rollouts complete different partial orders with projections of the same base order, the same complete orders are scored repeatedly; caching their BDeu values is an obvious optimization the paper does not explore and could cut runtime on the largest networks.","Seeding MCTS-BN with orders from several base algorithms at once, rather than one, is a natural diversity-increasing variant that the experiments do not test; it could make the search more robust when no single base algorithm is reliable."],"forward_implications":["On all six networks, every base algorithm's BDeu score increases after MCTS-BN refinement, so the method behaves as a generic score-boosting post-processor for order-based structural learners.","With GES as the seed, the final MCTS-BN network outscores Hill Climbing run under the true gold-standard topological order on four of the six domains.","Runtime remains practical because each rollout only executes a fast order-constrained Hill Climbing; the time added by MCTS stays modest relative to the base algorithm, and better base orders shorten it further.","The gains are largest from weak starting orders (HC, PC on large networks), but even then MCTS-BN rarely reaches the level of a strong GES seed, indicating the seed order quality sets a practical ceiling."],"supporting_citations":[{"why":"Supplies the UCT selection formula the MCTS-BN tree policy uses to balance exploration and exploitation.","marker":"[13]"},{"why":"Defines the Hill Climbing score+search procedure whose order-constrained variant produces the network scored in each rollout.","marker":"[7]"},{"why":"Introduces the BDeu score used both as the reward inside MCTS-BN and as the evaluation metric across all experiments.","marker":"[8]"},{"why":"Provides GES, the main base algorithm whose learned networks are sampled for guiding orders, and the score-equivalence theory behind it.","marker":"[5]"},{"why":"Supplies the PC constraint-based algorithm, one of the base learners whose orders seed and guide MCTS-BN.","marker":"[27]"},{"why":"Supplies fGES, another base learner used both as a seed order source and as a baseline in the experiments.","marker":"[21]"},{"why":"Provides the six gold-standard benchmark networks and their true topological orders used in evaluation.","marker":"[23]"},{"why":"Establishes the order-constrained structural learning framework that MCTS-BN relies on to convert a completed order into a network.","marker":"[17]"}],"fun_headline_variants":["MCTS guides Bayesian network order search to beat gold standard","Monte Carlo tree search finds better Bayesian network orders","Order optimization with MCTS boosts Bayesian network learning","MCTS-BN: smarter variable orders for Bayesian structure learning","Search over orders boosts Bayesian net score and beats gold"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a higher score on the training data (the BDeu metric the method optimizes) means a better learned network; the paper offers no held-out likelihood, edge-accuracy check, or significance test to support that identification.","fun_headline_variants_meta":{"raw":{"variants":["MCTS guides Bayesian network order search to beat gold standard","Monte Carlo tree search finds better Bayesian network orders","Order optimization with MCTS boosts Bayesian network learning","MCTS-BN: smarter variable orders for Bayesian structure learning","Search over orders boosts Bayesian net score and beats gold"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000729,"raw_usage":{"total_tokens":3250,"prompt_tokens":918,"completion_tokens":2332,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":534,"completion_tokens_details":{"reasoning_tokens":2254}},"tokens_in":534,"tokens_out":2332,"duration_ms":14477,"temperature":1.0,"reasoning_tokens":2254,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:01:16.703981+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute held-out log-likelihood or edge recovery (e.g., structural Hamming distance to the gold-standard network) for MCTS-BN versus its base algorithms on the same ten datasets per network; if the higher training BDeu scores do not come with better generalization or better edge recovery, the paper's central benefit claim is refuted. Alternatively, a paired test across the ten datasets showing the BDeu gain over GES is not consistently positive would contradict the 'consistently beneficial' claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the UCT selection formula the MCTS-BN tree policy uses to balance exploration and exploitation."},{"cited_title":"Data Mining and Knowledge Discovery22(1), 106–148 (Jan 2011)","cited_arxiv_id":null,"evidence_quote":"Defines the Hill Climbing score+search procedure whose order-constrained variant produces the network scored in each rollout."},{"cited_title":"Machine Learning20(3), 197–243 (Sep 1995)","cited_arxiv_id":null,"evidence_quote":"Introduces the BDeu score used both as the reward inside MCTS-BN and as the evaluation metric across all experiments."},{"cited_title":"Journal of Machine Learning Research3(Nov), 507–554 (2002)","cited_arxiv_id":null,"evidence_quote":"Provides GES, the main base algorithm whose learned networks are sampled for guiding orders, and the score-equivalence theory behind it."},{"cited_title":"Springer- Verlag, New York, USA (1993)","cited_arxiv_id":null,"evidence_quote":"Supplies the PC constraint-based algorithm, one of the base learners whose orders seed and guide MCTS-BN."},{"cited_title":"International Journal of Data Science and Analytics3, 121 – 129 (2017)","cited_arxiv_id":null,"evidence_quote":"Supplies fGES, another base learner used both as a seed order source and as a baseline in the experiments."},{"cited_title":"Journal of Statistical Software 35(3), 1–22 (2010)","cited_arxiv_id":null,"evidence_quote":"Provides the six gold-standard benchmark networks and their true topological orders used in evaluation."},{"cited_title":"In: Kratochvíl, V., Studený, M","cited_arxiv_id":null,"evidence_quote":"Establishes the order-constrained structural learning framework that MCTS-BN relies on to convert a completed order into a network."}],"review_version":1}