acceptodds
Under review as a conference paper at ICLR 2027

Prior-Guided Monte Carlo Tree Search for Learning Decision Trees Beyond Greedy Splits

Abstract

Decision trees remain widely used in regulated settings because each prediction traces back to an explicit rule. However, the standard greedy top-down induction used by CART commits to one split at a time and therefore misses patterns that only pay off after several coordinated splits. Exact solvers such as GOSDT and DL8.5 remove this myopia, but they rely on binarized features and frequently exhaust memory or time on wider datasets. We present PG-DTS, which casts tree induction as a deterministic Markov decision process and searches over whole tree structures under a fixed compute budget, while the output remains an ordinary axis-aligned decision tree. Split rewards are computed from the affected leaf alone and cached in a Global Leaf Registry, a PUCT prior steers the budget toward promising splits, and transposed states are deduplicated while tree materialization is deferred until needed. On an XOR trap where CART stalls at 53.72% accuracy, PG-DTS reaches 70.42%, matching the exact solvers, and under 20% label noise it is the most accurate method in every synthetic scenario. On 12 OpenML datasets at depth 4, it achieves the highest accuracy on 7 and returns a tree on all 12, whereas GOSDT fails on 3 and removing the leaf registry roughly quadruples runtime. These results suggest that prior-guided global search can reduce the myopia of axis-aligned trees while keeping their rules explicit.

Primary area:
interpretability and explainable AI
Keywords:
Decision trees, Interpretable machine learning, Monte Carlo tree search, Markov decision process, Optimal decision trees

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_nbPAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes PG-DTS which is a decision tree induction framework using prior guided Monte Carlo Tree Search (MCTS). The paper frames the induction problem as a deterministic Markov Decision Process (MDP) with states as partial trees and actions as target leaf, split feature and threshold. The contributions try to plug the gap between sub optimal greedy induction and brittle global solvers.

Critical strengths
  • The problem is well motivated and positioned. The paper tries to find a middle ground between fast & myopic greedy solvers and the brittle & memory hungry exact solvers.

  • Engineering contributions like GLR, leaf level reward, transposition deduplication plausibly help reduce runtime and memory.

  • Targeted ablations help to isolate the effects of some of the contributions.

  • Authors provide the implementation, well-structured pseudo code and dataset details to make the experiments reproducible.

Critical weaknesses
  • Baselines are compared unfairly. CART, DPDT, DL8.5, and GOSDT all get a 300 s time limit, while PG-DTS gets 1200 s. The failures in Table 2 (marked with -) are attributed to OOM or timeout, which makes the results difficult to interpret. Adding the exact reason for the failures and providing similar wall-clock times for all methods would be helpful. Additionally, providing the time to completion (termination under uncapped limit) for exact solvers may also strengthen your argument.
  • PG-DTS discretizes the continuous variables into 5 bins. There is no mention of how this number is reached. On a similar note, the authors do not mention hyperparameter choices in their method, such as the exploration constant “c”, smoothing term “ϵ”, softmax temperature “τ” and their potential impact on the algorithm’s performance. Corresponding sensitivity tests should be added.
  • The baselines were used out of the box with added restrictions like arbitrarily selected regularization and the small regularization option. No justification is provided for these choices, even though the datasets used for comparison are completely different from the ones mentioned in the baseline papers.
  • The choice of datasets is also arbitrary, as the authors never mention how and why these datasets were selected for the experiments.
  • The paper makes strong claims with respect to memory usage, but this is never measured.
  • Possible closely related work/baseline is missing: “Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO” (Chaouki et al. 2025) from the same authors of TSDT, which is cited in the paper.
  • The novelty claims are too strong, as the engineering contributions already exist in most of the related work that is discussed. Deterministic MDP (Kohler et al., 2025; Chaouki et al., 2024); GLR cache is similar to DL8.5.
  • The claims “under 20% label noise it is the most accurate method in every synthetic scenario.” and “On 12 OpenML datasets at depth 4, it achieves the highest accuracy on 7” are too strong, and no statistical testing is present in the paper to defend these.
  • No variability is mentioned in Table 2, unlike Table 1.
  • The ablations do not significantly show any performance improvement except runtime.
Questions for authors
  • How would the performance change when all the methods are given the same budgets?
  • How much effort was spent to find the optimal hyperparameter configurations for your method?
  • Would spending similar effort on tuning the baselines improve their performance?
  • How were the features binarized for exact solvers?
  • How would a 5 bin ordinal encoding similar to the binning in PG-DTS change the performance of GOSDT or other binarized solvers?
  • Can you provide the exact reason for the failure cases in table 2.
  • How were the datasets selected?
  • Why are these combination of (d,M) = (2, 1000), (3, 3000) and (4, 5000) chosen?
  • Can a paired statistical test for PG-DTS and next best methods be added to prove your method’s superiority in different settings?
  • Can the authors also add “Branches” method (Chaouki et al. 2025) to their comparison?
  • Please add the variability in table 2 and mention what the ± values indicate in both the tables.
  • Can you add metrics related to runtime and memory to your analysis, as this is one of the core contributions of the work.
  • Can a sensitivity analysis on the number of bins be added?
  • Can an ablation on the lazy build be provided as well?
  • Why aren’t the exact solvers able to achieve 95% and 80% accuracy for the synthetic data?
  • Could the novelty claims be softened a bit and similar prior work be cited appropriately in these scenarios?
Reviewer_prLVOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

New MCTS algo for decision tree induction. Good empirical performances on toy and real datasets. Lacks novelty (sorry). Indeed, most novelty seems based on caching and transpositioning even those are standard tools in MCTS. Similarly, the MDP + search approach exists in DPDT, Kohler et al. 2025 or Branches Chaouki et al. 2025 . The authors will benefit from writing a more explicit comparison of their MDP with existing works.

Critical strengths

Strong set of baselines and benchmarks.

Critical weaknesses

I think caching tree nodes in MCTS is pretty standard (your section 3.3) and the same goes for transposition tables (your section 4.3) cf. Batch Monte Carlo Tree Search, Cazeneuve 2021 . Instead of contributions those are implementation details that should go in appendix. Section 5.1, why give 1200 seconds time limit to PG-DTS but only 300 seconds for exact solvers ?

Questions for authors

Can you give insights on the time and space complexity of the search ? Cf. DPDT, Kohler et al. 2025 or Branches Chaouki et al. 2025 . Can you give uncertainties in table 2 please ? Why did you present TAO in section 2.2 even though it has nothing to do with RL / MDPs ? Can you compare the MDP of section 3 with the MDPs in DPDT, Kohler et al. 2025 or Branches Chaouki et al. 2025 ? Can ou plot a pareto front time vs test accuracy to support table 2 ?

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

The paper proposes PG-DTS, an MCTS-based method for learning interpretable decision trees beyond greedy splitting. It formulates tree construction as a deterministic MDP and uses Gini-based priors to guide the search. To improve efficiency, the method introduces a Global Leaf Registry to reuse leaf statistics, along with state deduplication and lazy tree construction. Experiments on synthetic tasks and 12 OpenML datasets compare PG-DTS with CART, DPDT, GOSDT, and DL8.5. The results show improvements over CART on several tasks and competitive accuracy against global tree learning methods.

Critical strengths

The paper addresses a relevant problem in decision tree learning: moving beyond greedy splitting while retaining interpretability. It also considers computational efficiency alongside predictive accuracy.

Critical weaknesses
  1. Several components of PG-DTS have close precedents in existing work. MCTS-based decision tree learning has been studied in [1], and DPDT [2] already formulates tree induction as an MDP. More importantly, OSDT [3] uses LeafCache and TreeCache to reuse leaf information and avoid redundant tree search, closely resembling the proposed Global Leaf Registry and state deduplication. The paper does not discuss OSDT or clearly explain what is new about these mechanisms in its PUCT-based framework.
  2. The XOR results raise questions about the quality of the proposed search. Based on Appendix D, a depth-2 tree using the two relevant features would achieve expected accuracies of 95% and 80% under 5% and 20% label noise, respectively. However, PG-DTS reports only 70.42% and 61.53%. The paper provides neither a reference solution nor solver convergence information to explain this gap. It also lacks an XOR ablation for the Gini-based prior, whose definition differs between Equation (2) and Appendix Algorithm 3. These issues make it difficult to assess the benefit of prior guidance.

[1] 2020 – Learning Decision Trees Through Monte Carlo Tree Search: An Empirical Evaluation.

[2] 2025 – KDD – Breiman Meets Bellman: Non-Greedy Decision Trees with MDPs

[3] 2019 – NeurIPS – Optimal Sparse Decision Trees

Questions for authors
  1. What distinguishes PG-DTS from existing MCTS- and MDP-based decision tree methods [1, 2]? In particular, how do the Global Leaf Registry and state deduplication differ from OSDT's LeafCache and TreeCache [3]
  2. Appendix D suggests that a depth-2 XOR tree can achieve expected accuracies of 95% and 80% under the two noise settings. What explains the lower results reported for PG-DTS (70.42% and 61.53%)? Could the authors provide convergence information or a comparison with this reference solution?
  3. How much does the Gini-based prior contribute to XOR performance? Could the authors provide an ablation without the prior and clarify whether the implementation uses Equation (2) or the Softmax formulation in Appendix Algorithm 3?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.