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

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.