# Breiman meets Bellman: Non-Greedy Decision Trees with MDPs

arXiv: https://arxiv.org/abs/2309.12701 · HTML: https://mlsanity.com/paper/2309.12701/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 22 Sep 2023.

## Builds on (most cited first, 14 of 14)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Revisiting Deep Learning Models for Tabular Data](https://mlsanity.com/paper/2106.11959/) (2021)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [SAINT: Improved Neural Networks for Tabular Data via Row Attention and Contrastive Pre-Training](https://mlsanity.com/paper/2106.01342/) (2021)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods](https://mlsanity.com/paper/2102.13045/) (2021)
- [Efficient non-greedy optimization of decision trees](https://mlsanity.com/paper/1511.04056/) (2015)
- [Learning Optimal Classification Trees: Strong Max-Flow Formulations](https://mlsanity.com/paper/2002.09142/) (2020)
- [Optimal Decision Tree Policies for Markov Decision Processes](https://mlsanity.com/paper/2301.13185/) (2023)
- [A Reinforcement Learning Approach to Online Learning of Decision Trees](https://mlsanity.com/paper/1507.06923/) (2015)

## Built on by (most cited first, 6 of 6)

- [Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning](https://mlsanity.com/paper/2405.14956/) (2024)
- [Learning Decision Trees as Amortized Structure Inference](https://mlsanity.com/paper/2503.06985/) (2025)
- [Talking Trees: Reasoning-Assisted Induction of Decision Trees for Tabular Data](https://mlsanity.com/paper/2509.21465/) (2025)
- [Empowering Decision Trees via Shape Function Branching](https://mlsanity.com/paper/2510.19040/) (2025)
- [Backward Compatibility in Tree-Based Explanations and Enhanced CART Algorithm](https://mlsanity.com/paper/2608.08674/) (2026)
- [A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees](https://mlsanity.com/paper/2609.38194/) (2026)

## Abstract (arXiv)

In supervised learning, decision trees are valued for their interpretability and performance. While greedy decision tree algorithms like CART remain widely used due to their computational efficiency, they often produce sub-optimal solutions with respect to a regularized training loss. Conversely, optimal decision tree methods can find better solutions but are computationally intensive and typically limited to shallow trees or binary features. We present Dynamic Programming Decision Trees (DPDT), a framework that bridges the gap between greedy and optimal approaches. DPDT relies on a Markov Decision Process formulation combined with heuristic split generation to construct near-optimal decision trees with significantly reduced computational complexity. Our approach dynamically limits the set of admissible splits at each node while directly optimizing the tree regularized training loss. Theoretical analysis demonstrates that DPDT can minimize regularized training losses at least as well as CART. Our empirical study shows on multiple datasets that DPDT achieves near-optimal loss with orders of magnitude fewer operations than existing optimal solvers. More importantly, extensive benchmarking suggests statistically significant improvements of DPDT over both CART and optimal decision trees in terms of generalization to unseen data. We demonstrate DPDT practicality through applications to boosting, where it consistently outperforms baselines. Our framework provides a promising direction for developing efficient, near-optimal decision tree algorithms that scale to practical applications.