For decades, decision trees have been the bedrock of interpretable machine learning. Algorithms like CART and C4.5 are ubiquitous because they are fast and produce models that humans can easily inspect. However, these classic methods are "greedy": they make the best local split at each node without considering how that choice affects the rest of the tree. This often leads to trees that are unnecessarily deep, complex, or less accurate than they could be.
The ideal is an Optimal Decision Tree (ODT)—the mathematically best tree for a given dataset, depth, and sparsity constraint. While finding such a tree is an NP-hard problem, a surge of research has moved ODTs from theoretical curiosities to practical tools by leveraging advanced optimization techniques.
The Combinatorial Explosion
The fundamental challenge in building an optimal tree is the search space. To find the best tree of depth $d$, an algorithm must theoretically consider every possible combination of features and split points across all nodes. As Florent Avellaneda and Gaël Aglin note, this combinatorial explosion makes standard optimization techniques fail as the number of features or observations grows.
Historically, this forced a binary choice: use greedy heuristics that are fast but suboptimal, or use exact solvers (like Mixed-Integer Programming) that provide optimality but fail to scale beyond tiny datasets. Modern research aims to break this trade-off.
Pruning the Search Space with Dynamic Programming
One of the most successful strategies for scaling ODTs is Dynamic Programming (DP) combined with sophisticated caching. The intuition is that many sub-problems in tree induction are redundant. If we have already found the optimal subtree for a specific subset of data, we should never have to calculate it again.
Jimmy Lin, Cynthia Rudin, and their colleagues introduced GOSDT (Generalized and Scalable Optimal Sparse Decision Trees), which uses DP and a custom "dependency graph" to identify and skip redundant computations. By using analytical bounds to prune branches of the search space that cannot possibly contain the optimal solution, GOSDT can find provably optimal trees for datasets with thousands of samples in seconds. Similarly, the DL8.5 algorithm by Gaël Aglin and Siegfried Nijssen integrates itemset mining techniques with caching to achieve similar speedups.
Branch and Bound for Continuous Features
While DP works well for categorical data, continuous features introduce an infinite number of potential split points. Rahul Mazumder and Xiang Meng addressed this with Quant-BnB, a branch-and-bound framework that uses a quantile-based decomposition. Instead of checking every possible split, they intelligently partition the search space, allowing the solver to "bound" the potential error and ignore large swaths of suboptimal feature thresholds. This approach has been extended to regression tasks by Cristóbal Heredia in RS-ORT, which reduces the search space specifically for continuous outcomes.
Bridging the Gap with Hybrid Heuristics
Despite these advances, provable optimality remains expensive for very deep trees. This has led to "near-optimal" methods that use optimization to improve upon greedy algorithms without the full cost of an exact search.
- Look-ahead Search: Guy Blanc and Li-Yang Tan proposed Top-$k$, which considers the $k$ best attributes for a split rather than just one, effectively widening the greedy "vision."
- MDP Formulations: Hector Kohler and Riad Akrour framed tree induction as a Markov Decision Process (MDP). Their DPDT framework uses CART as a heuristic to guide a DP search, achieving near-optimal results with significantly less computation.
- Strategic Switching: The SPLIT algorithm by Varun Babbar and Margo I. Seltzer uses rigorous branch-and-bound for the critical top levels of the tree and switches to greedy methods for the leaves, where the impact of suboptimality is lower.
Beyond Accuracy: Personalization and Robustness
The shift toward global optimization isn't just about higher accuracy; it's about enabling new types of constraints that greedy algorithms cannot handle.
Nathan Kallus and Sina Aghaei have applied these techniques to Prescriptive Trees, which don't just predict an outcome but recommend an action (like a medical treatment). Because these models must account for counterfactuals and observational bias, greedy splits are often misleading. Global optimization allows the model to maximize the "value" of the treatment policy across the entire tree structure.
Similarly, Daniël Vos and Sicco Verwer developed ROCT, which uses discrete optimization to guarantee that a decision tree is robust against adversarial perturbations. By incorporating robustness directly into the objective function, they can find the most accurate tree that is also mathematically guaranteed to be stable.
By moving from "good enough" greedy splits to rigorous global search, this field is transforming decision trees from simple heuristics into high-performance, provably optimal models for high-stakes decision-making.