Loss-Guided Stochastic Exploration for Learning a Single Decision Tree

Decision trees provide predictions through compact decision paths, but greedy construction often commits to locally optimal splits, creating a performance gap between single trees and ensembles. We introduce a loss-guided stochastic node exploration method for learning stronger single-tree structures. The method augments original features with data-derived directions, generates randomized and criterion-guided split candidates, and evaluates their downstream utility through staged search. This allows later splits to inform earlier decisions while using only one tree at inference time. Across diverse tabular classification datasets, the resulting trees outperform conventional and recent single-tree baselines, achieving state-of-the-art performance among the evaluated methods. Their mean Macro-F1 was approximately 1–2 percentage points lower than that of the tuned tree ensembles. These results suggest that improving feature representation and tree-construction search can narrow the performance gap between single trees and ensembles while retaining an explicit decision structure.