What is it about?

As our title suggests, we use theory of Markov decision processes to design a new decision tree induction algorithm. Decision trees are good models for supervised learning and tabular data: they often outperform deep learning approaches and are interpretable. In our article, we show that existing decision tree induction algorithms have either low accuracy or high computational complexity. We propose the Dynamic Programming Decision Trees algorithm that have both high accuracy and fast compute.

Featured Image

Why is it important?

This work is important because the proposed decision tree induction algorithm DPDT learns trees that generalize better to unseen data than standard CART trees. Similarly, when boosting DPDT trees, the resulting ensembles generalize better to unseen data than standard AdaBoost ensembles of CART trees. Indeed, we extensively benchmark DPDT in terms generalization, runtime, and hyperparameter optimization, and find that we outperform many standard baselines used in industry and research. We put great emphasis on open sourcing clean code that follow the scikit-learn API, check the code link below to try DPDT.

Perspectives

DPDT performances could be greatly improve by writing an industry-standard code for it. Indeed, right now DPDT is coded in pure python when most baselines have a C or C++ backend. Furthermore, the XGBoost library and CATBoost library that are more advance boosting procedures than AdaBoost, are currently not interfacable with DPDT while in theory DPDT trees could be boosted with CATBoost or XGBoost. From a theory perspective, the formal proof of performance improvement guarantees over greedy trees could be generalize to other supervised learning problems than the simple checkers board pattern.

Hector Kohler
Université de Lille

Read the Original

This page is a summary of: Breiman meets Bellman: Non-Greedy Decision Trees with MDPs, August 2025, ACM (Association for Computing Machinery),
DOI: 10.1145/3711896.3736868.
You can read the full text:

Read

Resources

Contributors

The following have contributed to this page