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

<figure><img src="image_1.png" /><figcaption>Figure 1: Pathological dataset and learned depth-2 trees with their scores, complexities, runtimes, and decision boundaries.</figcaption></figure>

## Abstract

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.

## CCS Concepts

* **Computing methodologies → Classification and regression trees; Markov decision processes.**

## Keywords

decision trees, Markov decision processes

## ACM Reference Format:

Hector Kohler, Riad Akrour, and Philippe Preux. 2025. Breiman meets Bellman: Non-Greedy Decision Trees with MDPs. In *Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD '25), August 3-7, 2025, Toronto, ON, Canada*. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3711896.3736868

## 1 Introduction

Decision trees [8, 47, 48] are at the core of various machine learning applications. Ensembles of decision trees such as tree boosting [15, 23, 24, 46] are the state-of-the-art for supervised learning on tabular data [27]. Human users can make sense of decision trees predictions [10, 19, 34] which allows for real-world applications when safety or trust is critical [50]. More recently, decision trees have been used to model sequential decision policies with imitation learning [2, 31] or directly with reinforcement learning (RL) [36, 52, 58, 59].

To motivate the design of new decision tree induction algorithms, Figure 1 exhibits a dataset for which existing greedy algorithms are suboptimal, and optimal algorithms are computationally expensive. The dataset is made up of $N = 10^4$ samples in $p = 2$ dimensions that can be perfectly labeled with a decision tree of depth 2. When running CART [8], greedily choosing the root node yields a sub-optimal tree. This is because greedy algorithms compute locally optimal splits in terms of information gain. In our example, the greedy splits always give two children datasets which themselves need depth 2 trees to be perfectly split. On the other hand, to find

<figure><img src="image_2.png" /></figure>

<footnote>This work is licensed under a Creative Commons Attribution 4.0 International License.
KDD '25, Toronto, ON, Canada
© 2025 Copyright held by the owner/author(s).
ACM ISBN 979-8-4007-1454-2/2025/08
https://doi.org/10.1145/3711896.3736868</footnote>
the root node, an optimal algorithm such as [37] iterates over all possible splits, that is, $N \times p = 20,000$ operations to find one node of the solution tree.

In this work, we present a framework for designing non-greedy decision tree induction algorithms that optimize a regularized training loss nearly as well as optimal methods. This is achieved with orders of magnitude less operations, and hence dramatic computation savings. We call this framework “Dynamic Programming Decision Trees” (DPDT). For every node, DPDT heuristically and dynamically limits the set of admissible splits to a few good candidates. Then, DPDT optimizes the regularized training loss with some depth constraints. Theoretically, we show that DPDT minimizes the empirical risk at least as well as CART. Empirically, we show that on all tested datasets, DPDT can reach 99% of the optimal regularized train accuracy while using thousands times less operations than current optimal solvers. More importantly, we follow [27] methodology to benchmark DPDT against both CART and optimal trees on hard datasets. Following the same methodology, we compare boosted DPDT [22] to boosted CART and to some deep learning methods and show clear superiority of DPDT.

## 2 Related Work

To learn decision trees, greedy approaches like CART [8] iteratively partition the training dataset by taking splits optimizing a local objective such as the Gini impurity or the entropy. This makes CART suboptimal with respect to training losses [41]. But CART remains the default decision tree algorithm in many machine learning libraries such as [15, 30, 45, 62] because it can scale to very deep trees and is very fast. To avoid overfitting, greedy trees are learned with a maximal depth or pruned a posteriori [8, chapter 3]. In recent years, more complex optimal decision tree induction algorithms have shown consistent gains over CART in terms of generalization capabilities [5, 18, 56].

Optimal decision tree approaches optimize a regularized training loss while using a minimal number of splits [1, 5, 14, 17, 18, 37, 53, 57]. However, direct optimization is not a convenient approach, as finding the optimal tree is known to be NP-Hard [28]. Despite the large number of algorithmic tricks to make optimal decision tree solvers efficient [18, 37], their complexity scales with the number of samples and the maximum depth constraint. Furthermore, optimal decision tree induction algorithms are usually constrained to binary-features dataset while CART can deal with any type of feature. When optimal decision tree algorithms deal with continuous features, they can usually learn only shallow trees, e.g. Quant-BnB [37] can only compute optimal trees up to depth 3. PySTreeD, the latest optimal decision tree library [53], can compute decision trees with depths larger than three but uses heuristics to binarize a dataset with continuous features during a pre-processing step. Despite their limitations to binary features and their huge computational complexities, encouraging practical results for optimal trees have been obtained [16, 33, 40, 54]. Among others, they show that optimal methods under the same depth constraint (up to depth four) find trees with 1-2% greater test accuracy than greedy methods.

In this work, we only consider the induction of nonparametric binary depth-constrained axis-aligned trees. By nonparametric

trees, we mean that we only consider tree induction algorithms that optimize both features and threshold values in internal nodes of the tree. This is different from the line of work on Tree Alternating Optimization (TAO) algorithm [12, 13, 61] that only optimizes tree nodes threshold values for fixed nodes features similarly to optimizing neural network weights with gradient-based methods.

There exist many other areas of decision tree research [35] such as inducing non-axis parallel decision trees [29, 42], splitting criteria of greedy trees [54], different optimization of parametric trees [43, 46], or pruning methods [21, 39].

Our work is not the first to formulate the decision tree induction problem as solving a Markov decision process (MDP) [14, 20, 25, 52]. Those works formulate tree induction as solving a partially observable MDP and use approximate algorithms such as Q-learning [25] or deep Q-learning [52] to solve them in an online fashion one datum from the dataset at a time. In a nutshell, our work, DPDT that we present next, is different in that it builds a stochastic and fully observable MDP that can be explicitly solved with dynamic programming. This makes it possible to solve exactly the decision tree induction problem.

## 3 Decision Trees for Supervised Learning

Let us briefly introduce some notations for the supervised classification problem considered in this paper. We assume that we have access to a set of $N$ examples denoted $\mathcal{E} = \{(x_i, y_i)\}_{i=1}^N$. Each datum $x_i$ is described by a set of $p$ features. $y_i \in \mathcal{Y}$ is the label associated with $x_i$.

A decision tree is made of two types of nodes: split nodes that are traversed, and leaf nodes that finally assign a label. To predict the label of a datum $x$, a decision tree $T$ sequentially applies a series of splits before assigning it a label $T(x) \in \mathcal{Y}$. In this paper, we focus on binary decision trees with axis-aligned splits as in [8], where each split compares the value of one feature with a threshold.

Our goal is to learn a tree that generalizes well to unseen data. To avoid overfitting, we constrain the maximum depth $D$ of the tree, where $D$ is the maximum number of splits that can be applied to classify a data. We let $\mathcal{T}_D$ be the set of all binary decision trees of depth $\le D$. Given a loss function $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_+$, we induce trees with a regularized training loss defined by:

$$ 
\begin{aligned}
T^* &= \underset{T \in \mathcal{T}_D}{\operatorname{argmin}} \mathcal{L}_{\alpha}(T), \\
T^* &= \underset{T \in \mathcal{T}_D}{\operatorname{argmin}} \frac{1}{N} \sum_{i=1}^{N} \ell(y_i, T(x_i)) + \alpha C(T),
\end{aligned} 
\quad (1) 
$$

where $C: \mathcal{T} \to \mathbb{R}$ is a complexity penalty that helps prevent or reduce overfitting such as the number of nodes [8, 37], or the expected number of splits to label a data[40]. The complexity penalty is weighted by $\alpha \in [0, 1]$. For supervised classification problems, we use the 0-1 loss: $\ell(y_i, T(x_i)) = 1_{\{y_i \neq T(x_i)\}}$. Please note while we focus on supervised classification problems in this paper, our framework extends naturally to regression problems.

We now formulate the decision tree induction problem 1 as finding the optimal policy in an MDP.
# 4 Decision Tree Induction as an MDP

Given a set of examples $\mathcal{E}$, the induction of a decision tree is made of a sequence of decisions: at each node, we must decide whether it is better to split (a subset of) $\mathcal{E}$, or to create a leaf node.

This sequential decision-making process corresponds to a Markov Decision Problem (MDP) [32] $\mathcal{M} = (S, A, R_\alpha, P, D)$. A state is a pair made of a subset of examples $X \subseteq \mathcal{E}$ and a depth $d$. Then, the set of states is $S = \{(X, d) \in P(\mathcal{E}) \times \{0, \dots, D\}\}$ where $P(\mathcal{E})$ denotes the power set of $\mathcal{E}$. $d \in \{0, \dots, D\}$ is the current depth in the tree. An action $A$ consists in creating either a split node, or a leaf node (label assignment). We denote the set of candidate split nodes $\mathcal{F}$. A split node in $\mathcal{F}$ is a pair made of one feature $i$ and a threshold value $x_{ij} \in \mathcal{E}$. So, we can write $A = \mathcal{F} \cup \{1, \dots, K\}$. From state $s = (X, d)$ and a splitting action $a \in \mathcal{F}$, the transition function $P$ moves to the next state $s_l = (X_l, d+1)$ with probability $p_l = \frac{|X_l|}{|\mathcal{X}|}$ where $X_l = \{(x_i, y_i) \in X : x_i \le x_{ij}\}$, or to state $s_r = (X \setminus X_l, d+1)$ with probability $1-p_l$. For a class assignment action $a \in \{1, \dots, K\}$, the chain reaches an absorbing terminal state with probability 1. The reward function $R_\alpha: S \times A \to \mathbb{R}$ returns $-\alpha$ for splitting actions and the proportion of misclassified examples of $X - \frac{1}{|\mathcal{X}|} \sum_{i=1}^{|\mathcal{X}|} R_\alpha(s_i, \pi(s_i))$ for class assignment actions. $\alpha \in [0, 1]$ controls the accuracy-complexity trade-off defined in the regularized training objective 1. The horizon $D$ limits tree depth to $D$ by forbidding class assignments after $D$ MDP transitions.

The solution to this MDP is a deterministic policy $\pi: S \to A$ that maximizes $J_\alpha(\pi) = \mathbb{E}[\sum_{l=0}^D R_\alpha(s_l, \pi(s_l))]$, the expected sum of rewards where the expectation is taken over transitions $s_{l+1} \sim P(s_l, \pi(s_l))$ starting from initial state $s_0 = (\mathcal{E}, 0)$. Any such policy can be converted into a binary decision tree through a recursive extraction function $E(\pi, s)$ that returns, either a leaf node with class $\pi(s)$ if $\pi(s)$ is a class assignment, or a tree with root node containing split $\pi(s)$ and left/right sub-trees $E(\pi, s_l)/E(\pi, s_r)$ if $\pi(s)$ is a split. The final decision tree $T$ is obtained by calling $E(\pi, s_0)$ on the initial state $s_0$.

**PROPOSITION 4.1 (OBJECTIVE EQUIVALENCE).** Let $\pi$ be a deterministic policy of the MDP and $\pi^*$ be an optimal deterministic policy. Then $J_\alpha(\pi) = -\mathcal{L}_\alpha(E(\pi, s_0))$ and $T^* = E(\pi^*, s_0)$ where $T^*$ is a tree that optimizes Eq. 1.

This proposition is key as it states that the return of any policy of the MDP defined above is equal to the regularized training accuracy of the tree extracted from this policy. A consequence of this proposition is that when all possible splits are considered, the optimal policy will generate the optimal tree in the sense defined by Eq. (1). The proof is given in the Appendix A.

# 5 Algorithm

We now present the Dynamic Programming Decision Tree (DPDT) induction algorithm. The algorithm consists of two essential steps. The first and most computationally expensive step constructs the MDP presented in Section 4. The second step solves it to obtain a policy that maximizes Eq.4 and that is equivalent to a decision tree. Both steps are now detailed.

<figure><img src="image_3.png" /><figcaption>**Figure 2:** Schematics of the MDP to learn a decision tree of depth 2 to classify a toy dataset with three samples, two features (x,y), and two classes (oval, diamond) and using an arbitrary splits generating function.</figcaption></figure>

## 5.1 Constructing the MDP

An algorithm constructing the MDP of section 4 essentially computes the set of all possible decision trees of maximum depth $D$ which decision nodes are in $\mathcal{F}$. The transition function of this specific MDP is a directed acyclic graph. Each node of this graph corresponds to a state for which one computes the transition and reward functions. Considering all possible splits in $\mathcal{F}$ does not scale. We thus introduce a state-dependent action space $A_s$, much smaller than $A$ and populated by a splits generating function. In Figure 2, we illustrate the MDP constructed for the classification of a toy dataset using some arbitrary splitting function.

## 5.2 Heuristic splits generating functions

A split generating function is any function $\phi$ that maps an MDP state, i.e., a subset of training examples, to a split node. It has the form $\phi: S \to P(\mathcal{F})$, where $P(\mathcal{F})$ is the power set of all possible split nodes in $\mathcal{F}$. For a state $s \in S$, the state-dependent action space is defined by $A_s = \{\phi(s) \cup \{1, \dots, K\}\}$.

When the split generating function does not return all the possible candidate split nodes given a state, solving the MDP with state-dependent actions $A_s$ is not guaranteed to yield the minimizing tree of Eq. 1, as the optimization is then performed on the subset of trees of depth smaller or equal to $D$, $\mathcal{T}_D$. We now define some interesting split generating functions and provide the time complexity of the associated decision tree algorithms. The time complexity is given in big-O of the number of candidate split nodes considered during computations.

*Exhaustive function.* When $\mathcal{F} \subseteq \phi(s), \forall s \in S$, the MDP contains all possible splits of a certain set of examples. In this case, the optimal MDP policy is the optimal decision tree of depth at most $D$, and the number of states of the MDP would be $O((2Np)^D)$. Solving the MDP for $A_s = \phi(s)$ is equivalent to running one of the optimal tree induction algorithms [1, 5, 14, 17, 18, 33, 37, 53, 56, 57].

*Top B most informative splits.* [7] proposed to generate splits with a function that returns, for any state $s = (X, d)$, the B most informative splits over $X$ with respect to some information gain measure such as the entropy or the Gini impurity. The number of
<figure><img src="image_4.png" /><figcaption>Figure 3: How CART is used in DPDT to generate candidate splits given the example data in the current state.</figcaption></figure>

states in the MDP would be $O((2B)^D)$. When $B = 1$, the optimal policy of the MDP is the greedy tree. In practice, we noticed that the returned set of splits lacked diversity and often consists of splits on the same feature with minor changes to the threshold value.

Calls to CART. Instead of returning the most informative split at each state $s = (X, d)$, we propose to find the most discriminative split, i.e. the feature splits that best predicts the class of data in $X$. We can do this by considering the split nodes of the greedy tree. In practice, we run CART on $s$ and use the returned nodes as $\phi(s)$. We control the number of MDP states by constraining CART trees with a maximum number of nodes $B: \phi(s) = \text{nodes}(\text{CART}(s, \text{max\_nodes} = B))$. The number of MDP states would be $O((2B)^D)$. When $B = 1$, the MDP policy corresponds to the greedy tree. The process of generating split nodes with calls to CART is illustrated in Figure 3.

## 5.3 Dynamic Programming to solve the MDP

**Algorithm 1: DPDT**

**Data:** Dataset $\mathcal{E}$, max depth $D$, split function $\phi()$, split function parameter $B$, regularizing term $\alpha$

**Result:** Tree $T$

$M \leftarrow build_mdp(\mathcal{E}, D, \phi(), B)$

// Backward induction

$Q^*(s, a) \leftarrow$

$R_{\alpha}^{M}(s, a) + \sum_{s'} P^{M}(s, a, s') \max_{a' \in A_{s'}^{M}} Q^{*}(s', a') \forall s, a \in M$

// Get the optimal policy

$\pi^*(s) = \arg \max_{a \in A_s^M} Q^*(s, a) \forall s \in M$

// Extracting tree from policy

$T \leftarrow E(\pi^*, s_0^M)$

After constructing the MDP with a chosen splits generating function, we solve for the optimal policy using dynamic programming. Starting from terminal states and working backward to the initial state, we compute the optimal state-action values using Bellman's optimality equation [3], and then deducing the optimal policy.

From now on, we write DPDT to denote Algorithm 1 when the split function is a call to CART. We discuss key bottlenecks

when implementing DPDT in subsequent sections. We now state theoretical results when using DPDT with the CART heuristic.

## 5.4 Performance Guarantees of DPDT

We now show that: 1) DPDT minimizes the loss from Eq. 1 at least as well as greedy trees and 2) there exists problems for which DPDT has strictly lower loss than greedy trees. As we restrict the action space at a given state $s$ to a subset of all possible split nodes, DPDT is not guaranteed to find the tree minimizing Eq. 1. However, we are still guaranteed to find trees that are better or equivalent to those induced by CART:

**THEOREM 5.1 (MDP SOLUTIONS ARE NOT WORSE THAN THE GREEDY TREE).** Let $\pi^*$ be an optimal deterministic policy of the MDP, where the action space at every state is restricted to the top $B$ most informative or discriminative splits. Let $T_0$ be the tree induced by CART and $\{T_1, \dots, T_M\}$ all the sub-trees of $T_0$, 1 then for any $\alpha > 0$,

$$ \mathcal{L}_{\alpha}(E(\pi^*, s_0)) \leq \min_{0 \leq i \leq M} \mathcal{L}_{\alpha}(T_i) $$

**PROOF.** Let us first define $C(T)$, the expected number of splits performed by tree $T$ on dataset $\mathcal{E}$. Here $T$ is deduced from policy $\pi$, i.e. $T = E(\pi, s_0)$. $C(T)$ can be defined recursively as $C(T) = 0$ if $T$ is a leaf node, and $C(T) = 1 + p_lC(T_l) + p_rC(T_r)$, where $T_l = E(\pi, s_l)$ and $T_r = E(\pi, s_r)$. In words, when the root of $T$ is a split node, the expected number of splits is one plus the expected number of splits of the left and right sub-trees of the root node. $\square$

It is known that the greedy tree of depth 2 fails to perfectly classify the XOR problem as shown in Figure 1 and in [40, 41]. We aim to show that DPDT is a cheap way to alleviate the weaknesses of greedy trees in this type of problems. The following theorem states that there exist classification problems such that DPDT optimizes the regularized training loss strictly better than greedy algorithms such as CART, ID3 or C4.5.

**THEOREM 5.2 (DPDT CAN BE STRICTLY BETTER THAN GREEDY).** There exists a dataset and a depth $D$ such that the DPDT tree $T_D^{DPDT}$ is strictly better than the greedy tree $T_D^{greedy}$, i.e, $\mathcal{L}_{\alpha=0}(T_D^{greedy}) > \mathcal{L}_{\alpha=0}(T_D^{DPDT})$.

The proof of this theorem is given in the next section.

## 5.5 Proof of Improvement over CART

In this section we construct a dataset for which the greedy tree of depth 2 fails to accurately classify data while DPDT with calls to CART as a splits generating function guarantees a strictly better accuracy. The dataset is the XOR pattern like in Figure 1. We will first show that greedy tree induction like CART chooses the first split at random and the second split in between the two columns or rows. Then we will quantify the misclassification of the depth-2 greedy tree on the XOR gate. Finally we will show that using the second greedy split as the root of a tree and then building the remaining nodes greedily, i.e. running DPDT with the CART heuristic, strictly decreases the misclassification.

<footnote n="1">¹These sub-trees are interesting to consider since they can be returned by common postprocessing operations following a call to CART, that prune some of the nodes from $T_0$. Please see [21] for a review of pruning methods for decision trees.</footnote>
**Definition 5.3 (XOR dataset).** Let us defined the XOR dataset as $\mathcal{E}_{XOR} = \{(X_i, Y_i)\}_{i=1}^N$. $X_i = (x_i, y_i) \sim \mathcal{U}([0, 1]^2)$ are i.i.d 2-features samples. $Y_i = f(X_i)$ are alternating classes with $f(x, y) = (\lfloor 2x \rfloor + \lfloor 2y \rfloor)$ mod 2.

**LEMMA 5.4.** *The first greedy split is chosen at random on the XOR dataset from definition 5.3.*

**PROOF.** Let us consider an arbitrary split $x = x_v$ parallel to the y-axis. The results apply to splits parallel to the x-axis because the XOR pattern is the same when rotated 90 degrees. The split $x_v$ partitions the dataset into two regions $R_{left}$ and $R_{right}$. Since the dataset has two columns and two rows, any rectangular area that spans the whole height $[0, 1)$ has the same proportion of class 0 samples and class 1 samples from definition 5.3. So in both $R_{left}$ and $R_{right}$ the probabilities of observing class 0 or class 1 at random are $\frac{1}{2}$. Since the class distributions in left and right regions are independent of the split location, all splits have the same objective value when the objective is a measure of information gain like the entropy or the Gini impurity. Hence, the first split in a greedily induced tree is chosen at random. □

**LEMMA 5.5.** *When the first split is greedy on the XOR dataset from definition 5.3, the second greedy splits are chosen perpendicular to the first split at $y = \frac{1}{2}$*

**PROOF.** Assume without loss of generality due to symmetries, that the first greedy split is vertical, at $x = x_v$, with $x_v \le \frac{1}{2}$. This split partitions the unit square into $R_{left} = [0, x_v) \times [0, 1)$ and $R_{right} = [x_v, 1) \times [0, 1)$. The split $y = \frac{1}{2}$ further partitions $R_{left}$ into $R_{left-down}$ and $R_{left-up}$ with same areas $x_v \times y = \frac{x_v}{2}$. Due to the XOR pattern, there are only samples of class 0 in $R_{left-down}$ and only samples of class 1 in $R_{left-up}$. Hence the split $y = \frac{1}{2}$ maximizes the information gain in $R_{left}$, hence the second greedy split given an arbitrary first split $x = x_v$ is necessarily $y = \frac{1}{2}$. □

**Definition 5.6 (Forced- Tree).** Let us define the forced-tree as a greedy tree that is forced to make its first split at $y = \frac{1}{2}$.

**LEMMA 5.7.** *The forced-tree of depth 2 has a 0 loss on the XOR dataset from definition 5.3 while, with probability $1 - \frac{1}{|\mathcal{E}_{XOR}|}$, the greedy tree of depth 2 has strictly positive loss.*

**PROOF.** This is trivial from the definition of the forced tree since if we start with the split $y = \frac{1}{2}$, then clearly CART will correctly split the remaining data. If instead the first split is some $x_v \ne \frac{1}{2}$ then CART is bound to make an error with only one extra split allowed. Since the first split is chosen at random, from Lemma 5.5, there are only two splits ($x = \frac{1}{2}$ and $y = \frac{1}{2}$) out of $2^{|\mathcal{E}_{XOR}|}$ that do not lead to sub-optimality. □

We can now formally prove theorem 5.2.

**PROOF.** By definition of DPDT, all instances of DPDT with the CART nodes parameter $B \ge 2$ include the forced-tree from definition 5.6 in their solution set when applied to the XOR dataset (definition 5.3). We know from lemma 5.7 that with high probability, the forced-tree of depth 2 is strictly more accurate than the greedy

tree of depth 2 on the XOR dataset. Because we know by proposition 4.1 that DPDT returns the tree with maximal accuracy from its solution set, we can say that DPDT depth-2 trees are strictly better than depth-2 greedy trees returned by e.g. CART on the XOR dataset. □

## 5.6 Practical Implementation

The key bottlenecks lie in the MDP construction step of DPDT (Section 4). In nature, all decision tree induction algorithms have time complexity exponential in the number of training subsets per tree depth $D$: $O((2B)^D)$, e.g., CART has $O(2^D)$ time complexity. We already saw that DPDT saves time by not considering all possible tree splits but only $B$ of them. Using state-dependent split generation also allows to generate more or less candidates at different depths of the tree. Indeed, the MDP state $s = (X, d)$ contains the current depth during the MDP construction process. This means that one can control DPDT's time complexity by giving multiple values of maximum nodes: given $(B_1, B_2, ..., B_D)$, the splits generating function in Algorithm 1 becomes $\phi(s_i) = \phi(X_i, d = 1) = \text{nodes}(\text{CART}(s, \max\_\text{nodes} = B_1))$ and $\phi(s_j) = \phi(X_j, d = 2) = \text{nodes}(\text{CART}(s, \max\_\text{nodes} = B_2))$.

Similarly, the space complexity of DPDT is exponential in the space required to store training examples $\mathcal{E}$. Indeed, the MDP states that DPDT builds in Algorithm 1 are training samples $X \subseteq \mathcal{E}$. Hence, the total space required to run DPDT is $O(Np(2B)^D)$ where $Np$ is the size of $\mathcal{E}$. In practice, one should implement DPDT in a depth first search manner to obtain a space complexity linear in the size of training set: $O(DNp)$. In practice DPDT builds the MDP from Section 4 by starting from the root and recursively splitting the training set while backpropagating the $Q$-values. This is possible because the MDP we solve has a (not necessarily binary) tree structure (see Figure 2) and because the $Q$-values of a state only depend on future states.

We implemented DPDT<fnref n="2" /> following scikit-learn API [11] with depth-first search and state-depth-dependent splits generating.

## 6 Empirical Evaluation

In this section, we empirically demonstrate strong properties of DPDT trees. The first part of our experiments focuses on the quality of solutions obtained by DPDT for objective Eq.1 compared to greedy and optimal trees. We know by theorems 5.1 and 5.2 that DPDT trees should find better solutions than greedy algorithms for certain problems; but what about real problems? After showing that DPDT can find optimal trees by considering much less solutions and thus performing orders of magnitude less operations, we will study the generalization capabilities of the latter: do DPDT trees label unseen data accurately?

### 6.1 DPDT optimizing capabilities

From an empirical perspective, it is key to evaluate DPDT training accuracy since optimal decision tree algorithms against which we wish to compare ourselves are designed to optimize the regularized training loss Eq.1.

#### 6.1.1 Setup.

<footnote n="2">²https://github.com/KohlerHECTOR/DPDTTreeEstimator</footnote>
<table><caption>Table 1: Comparison of train accuracies of depth-3 trees and number of operations on classification tasks. For DPDT and Top-B, “light” configurations have split function parameters (8, 1, 1) “full” have parameters (8, 8, 8). We also include the mean train accuracy over 5 deep RL runs. Bold values are optimal accuracies and blue values are the largest non-optimal accuracies.</caption><thead><tr><th rowspan="2">Dataset</th><th rowspan="2">N</th><th rowspan="2">p</th><th colspan="5">Accuracy</th><th colspan="5">Operations</th></tr><tr><th>Opt Quant-BnB</th><th>Greedy CART</th><th>DPDT light</th><th>DPDT full</th><th>Top-B light</th><th>Top-B full</th><th>Deep RL Custard</th><th>Opt Quant-BnB</th><th>Greedy CART</th><th>DPDT light</th><th>DPDT full</th><th>Top-B light</th><th>Top-B full</th></tr></thead><tbody><tr><td>room</td><td>8103</td><td>16</td><td><strong>0.992</strong></td><td>0.968</td><td><strong>0.991</strong></td><td><strong>0.992</strong></td><td>0.990</td><td><strong>0.992</strong></td><td>0.715</td><td>10<sup>6</sup></td><td>15</td><td>286</td><td>16100</td><td>111</td><td>16100</td></tr><tr><td>bean</td><td>10888</td><td>16</td><td><strong>0.871</strong></td><td>0.777</td><td>0.812</td><td>0.853</td><td>0.804</td><td>0.841</td><td>0.182</td><td>5·10<sup>6</sup></td><td>15</td><td>295</td><td>25900</td><td>112</td><td>16800</td></tr><tr><td>egg</td><td>11984</td><td>14</td><td><strong>0.708</strong></td><td>0.666</td><td>0.689</td><td>0.706</td><td>0.684</td><td>0.699</td><td>0.549</td><td>2·10<sup>6</sup></td><td>13</td><td>289</td><td>26000</td><td>95</td><td>11000</td></tr><tr><td>avila</td><td>10430</td><td>10</td><td><strong>0.585</strong></td><td>0.532</td><td>0.574</td><td><strong>0.585</strong></td><td>0.563</td><td>0.572</td><td>0.409</td><td>3·10<sup>7</sup></td><td>9</td><td>268</td><td>24700</td><td>60</td><td>38900</td></tr><tr><td>magic</td><td>15216</td><td>10</td><td><strong>0.831</strong></td><td>0.801</td><td>0.822</td><td>0.828</td><td>0.807</td><td>0.816</td><td>0.581</td><td>6·10<sup>6</sup></td><td>15</td><td>298</td><td>28000</td><td>70</td><td>4190</td></tr><tr><td>htru</td><td>14318</td><td>8</td><td><strong>0.981</strong></td><td>0.979</td><td>0.979</td><td>0.980</td><td>0.979</td><td>0.980</td><td>0.860</td><td>6·10<sup>7</sup></td><td>15</td><td>295</td><td>25300</td><td>55</td><td>2180</td></tr><tr><td>occup.</td><td>8143</td><td>5</td><td><strong>0.994</strong></td><td>0.989</td><td>0.991</td><td><strong>0.994</strong></td><td>0.990</td><td><strong>0.992</strong></td><td>0.647</td><td>7·10<sup>5</sup></td><td>13</td><td>280</td><td>16300</td><td>33</td><td>510</td></tr><tr><td>skin</td><td>196045</td><td>3</td><td><strong>0.969</strong></td><td>0.966</td><td>0.966</td><td>0.966</td><td>0.966</td><td><strong>0.966</strong></td><td>0.612</td><td>7·10<sup>4</sup></td><td>15</td><td>301</td><td>23300</td><td>20</td><td>126</td></tr><tr><td>fault</td><td>1552</td><td>27</td><td><strong>0.682</strong></td><td>0.553</td><td>0.672</td><td>0.674</td><td>0.672</td><td>0.673</td><td>0.303</td><td>9·10<sup>8</sup></td><td>13</td><td>295</td><td>24200</td><td>111</td><td>16800</td></tr><tr><td>segment</td><td>1848</td><td>18</td><td><strong>0.887</strong></td><td>0.574</td><td>0.812</td><td>0.879</td><td>0.786</td><td>0.825</td><td>0.137</td><td>2·10<sup>6</sup></td><td>7</td><td>220</td><td>16300</td><td>68</td><td>11400</td></tr><tr><td>page</td><td>4378</td><td>10</td><td><strong>0.971</strong></td><td>0.964</td><td>0.970</td><td>0.970</td><td>0.964</td><td>0.965</td><td>0.902</td><td>10<sup>7</sup></td><td>15</td><td>298</td><td>22400</td><td>701</td><td>4050</td></tr><tr><td>bidding</td><td>5056</td><td>9</td><td><strong>0.993</strong></td><td>0.981</td><td>0.985</td><td><strong>0.993</strong></td><td>0.985</td><td><strong>0.993</strong></td><td>0.810</td><td>3·10<sup>5</sup></td><td>13</td><td>256</td><td>9360</td><td>58</td><td>2700</td></tr><tr><td>raisin</td><td>720</td><td>7</td><td><strong>0.894</strong></td><td>0.869</td><td>0.879</td><td>0.886</td><td>0.875</td><td>0.883</td><td>0.509</td><td>4·10<sup>6</sup></td><td>15</td><td>295</td><td>20900</td><td>48</td><td>1440</td></tr><tr><td>rice</td><td>3048</td><td>7</td><td><strong>0.938</strong></td><td>0.933</td><td>0.934</td><td>0.937</td><td>0.933</td><td>0.936</td><td>0.519</td><td>2·10<sup>7</sup></td><td>15</td><td>298</td><td>25500</td><td>49</td><td>1470</td></tr><tr><td>wilt</td><td>4339</td><td>5</td><td><strong>0.996</strong></td><td>0.993</td><td>0.994</td><td>0.995</td><td>0.994</td><td>0.994</td><td>0.984</td><td>3·10<sup>5</sup></td><td>13</td><td>274</td><td>11300</td><td>33</td><td>465</td></tr><tr><td>bank</td><td>1097</td><td>4</td><td><strong>0.983</strong></td><td>0.933</td><td>0.971</td><td>0.980</td><td>0.951</td><td>0.974</td><td>0.496</td><td>6·10<sup>4</sup></td><td>13</td><td>271</td><td>7990</td><td>26</td><td>256</td></tr></tbody></table>

<figure><img src="image_5.png" /><figcaption>Figure 4: Root splits candidate obtained with DPDT compared to the optimal root split on the Bank dataset. Each split creates a partition of *p*-dimensional data that we projected in the 2-dimensional space using t-SNE.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Root splits candidate obtained with Top-B[7] on the Bank dataset. Each split creates a partition of *p*-dimensional data that we projected using t-SNE.</figcaption></figure>

**Metrics:** we are interested in the regularized training loss of algorithms optimizing Eq.1 with $\alpha = 0$ and a maximum depth $D$. We are also interested in the number of key operations performed by each baseline, namely computing candidate split nodes for subsets of the training data. We disregard running times as solvers are implemented in different programming languages and/or using optimized code: operations count is more representative of an algorithm efficiency. We also qualitatively compare different decision trees root splits to some optimal root split.

**Baselines:** we benchmark DPDT against greedy trees and optimal trees. For greedy trees we compare DPDT to CART [8]. For optimal trees we compare DPDT to Quant-BnB [37] which is the only solver specialized for depth 3 trees and continuous features. We also consider the non-greedy baseline Top-B [7]. Ideally, DPDT should have training accuracy close to the optimal tree while performing

a number of operations close to the greedy algorithm. Furthermore, comparing DPDT to Top-B brings answers to which heuristic splits are better to consider.

We use the CART algorithm implemented in scikit-learn [45] in CPython with a maximum depth of 3. Optimal trees are obtained by running the Julia implementation of the Quant-BnB solver from [37] specialized in depth 3 trees for datasets with continuous features. We use a time limit of 24 hours per dataset. DPDT and Top-B trees are obtained with Algorithm 1 implemented in pure Python and the calls to CART and Top-B most informative splits generating functions from Section 4 respectively. We also include Custard, a deep RL baseline [52]. Custard fits a neural network online one
datum at a time rather than solving exactly the MDP from Section 4
which states are sets of data. Similarly to DPDT, Custard neural
network policy is equivalent to a decision tree. We implement
Custard with the DQN agent from stable-baselines3 [49] and
train until convergence.

Datasets: we us the same datasets as the Quant-BnB paper [37].

6.1.2 *Observations*.

*Near-optimality.* Our experimental results demonstrate that unlike Deep RL, DPDT and Top-B approaches consistently improve upon greedy solutions while requiring significantly fewer operations than exact solvers. Looking at Table 1, we observe several key patterns: first, light DPDT with 16 candidate root splits consistently outperforms the greedy baseline in all datasets. This shows that in practice DPDT can be strictly netter than CART outside of theorem 5.2 assumptions. Second, when comparing DPDT to Top-B, we see that DPDT generally achieves better accuracy for the same configuration. For example, on the bean dataset, full DPDT reaches 85.3% accuracy while full Top-B achieves 84.1%. This pattern holds on most datasets, suggesting that DPDT is more effective than selecting splits based purely on information gain.

Third, both approaches achieve impressive computational effi-
ciency compared to exact solvers. While optimal solutions require
between 10⁴ to 10⁸ operations, DPDT and Top-B typically need
only 10² to 10⁴ operations, a reduction of 2 to 4 orders of magnitude.
Notably, on several datasets (room, avila, occupancy, bidding), full
DPDT matches or comes extremely close to optimal accuracy while
requiring far fewer operations. For example, on the room dataset,
full DPDT achieves the optimal accuracy of 99.2% while reducing
operations from 1.34 × 10⁶ to 1.61 × 10⁴. These results demonstrate
that DPDT provides an effective middle ground between greedy
approaches and exact solvers, offering near-optimal solutions with
reasonable computational requirements. While both DPDT and
Top-B improve upon greedy solutions, DPDT CART-based split
generation strategy appears to be particularly effective at finding
high-quality solutions.

**DPDT splits.** To understand why the CART-based split genera-
tion yields more accurate DPDT trees than the Top-B heuristic, we
visualize how splits partition the feature space (Figures 4, 5). We
run both DPDT with splits from CART and DPDT with the Top-B
most informative splits on the bank dataset. We use t-SNE to create
a two-dimensional representations of the dataset partitions given
by candidates root splits from CART and Top-B. The optimal root
split for the depth-3 tree for bank-obtained with Quant-BnB-is
shown on Figure 4 in the top-left subplot using green and orange
colors for the resulting partitions. On the same figure we can see
that the DPDT split generated with CART $x_0 \le 0.259$ is very similar
to the optimal root split. However, on Figure 5 we observe that no
Top-B candidate splits resemble the optimal root and that in general
Top-B split lack diversity: they always split along the same feature.
We tried to enforce diversity by getting the most informative split
*per feature* but no candidate split resembles the optimal root.

6.2 DPDT generalization capabilities

The goal of this section is to have a fair comparison of generaliza-
tion capabilities of different tree induction algorithms. Fairness of
comparison should take into account the number of hyperparame-
ters, choice of programming language, intrinsic purposes of each
algorithms (what are they designed to do?), the type of data they
can read (categorical features or numerical features). We bench-
mark DPDT using [27]. We choose this benchmark because it was
used to establish XGBoost [15] as the SOTA tabular learning model.

6.2.1 Setup.

*Metrics:* We re-use the code from [27] <fnref n="3" />. It relies on random searches for hyper-parameter tuning [4]. We run a random search of 100 iterations per dataset for each benchmarked tree algorithms. To study performance as a function of the number *n* of random search iterations, we compute the best hyperparameter combination on the validation set on these *n* iterations (for each model and dataset), and evaluate it on the test set. Following [27], we do this 15 times while shuffling the random search order at each time. This gives us bootstrap-like estimates of the expected test score of the best tree found on the validation set after each number of random search iterations. In addition, we always start the random searches with the default hyperparameters of each tree induction aglirthm. We use the test set accuracy (classification) to measure model performance. The aggregation metric is discussed in details in [27, Section 3].

*Datasets:* we use the datasets curated by [27]. They are available on OpenML [55] and described in details in [27, Appendix A.1]. The attributes in these datasets are either numerical (a real number), or categorical (a symbolic values among a finite set of possible values). The considered datasets follow a strict selection [27, Section 3] to focus on core learning challenges. Some datasets are very large (millions of samples) like Higgs or Covertype [6, 60]. To ensure non-trivial learning tasks, datasets where simple models (e.g. logistic regression) performed within 5% of complex models (e.g. ResNet [26], HistGradientBoosting [45]) are removed. We use the same data partitioning strategy as [27]: 70% of samples are allocated for training, with the remaining 30% split between validation (30%) and test (70%) sets. Both validation and test sets are capped at 50,000 samples for computational efficiency. All algorithms and hyperparameter combinations were evaluated on identical folds. Finally, while we focus on classification datasets in the main text, we provide results for regression problems in table 5 in the appendix.

**Baselines:** we benchmark DPDT against CART and STreeD when inducing trees of depth at most 5. We use hyperparameter search spaces from [9] for CART and DPDT. For DPDT we additionally consider eight different splits functions parameters configurations for the maximum nodes in the calls to CART. Surprisingly, after computing the importance of each hyperparameter of DPDT, we found that the maximum node numbers in the calls to CART are only the third most important hyperparametrer behind classical ones like the minimum size of leaf nodes or the minimum impurity decrease (Table 2). We use the CPython implementation of STreeD<fnref n="4" />. All hyperparameter grids are given in table 7 in the appendix.

<footnote n="3">³https://github.com/leogrin/tabular-benchmark</footnote>

<footnote n="4">⁴PySTreeD: https://github.com/AlgTUDelft/pystreed</footnote>
<figure><img src="image_7.png" /><figcaption>(e) Boosting vs Single Tree Num.</figcaption></figure>

<caption>(f) Boosting vs Single Tree Cat.</caption>

<caption>(g) Boosting vs Neural Numerical (h) Boosting vs Neural Categorical</caption>

<caption>**Figure 6:** Benchmark on medium-sized datasets. Dotted lines correspond to the score of the default hyperparameters, which is also the first random search iteration. Each value corresponds to the test score of the best model (obtained on the validation set) after a specific number of random search iterations (a, b) or after a specific time spent doing random search (c, d), averaged on 15 shuffles of the random search order. The ribbon corresponds to the minimum and maximum scores on these 15 shuffles.</caption>

<table><caption>**Table 2:** Hyperparameters importance comparison. A description of the hyperparameters can be found in the scikit-learn documentation: https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html.</caption><thead><tr><th>Hyperparameter</th><th>DPDT (%)</th><th>CART (%)</th><th>STreeD (%)</th></tr></thead><tbody><tr><td>minSamplesLeaf</td><td>35.05</td><td>33.50</td><td>50.50</td></tr><tr><td>minImpurityDecrease</td><td>24.60</td><td>24.52</td><td>-</td></tr><tr><td>cartNodesList</td><td>15.96</td><td>-</td><td>-</td></tr><tr><td>maxFeatures</td><td>11.16</td><td>18.06</td><td>-</td></tr><tr><td>maxDepth</td><td>7.98</td><td>10.19</td><td>0.00</td></tr><tr><td>maxLeafNodes</td><td>-</td><td>7.84</td><td>-</td></tr><tr><td>minSamplesSplit</td><td>2.67</td><td>2.75</td><td>-</td></tr><tr><td>minWeightFractionLeaf</td><td>2.58</td><td>3.14</td><td>-</td></tr><tr><td>maxNumNodes</td><td>-</td><td>-</td><td>27.51</td></tr><tr><td>nThresholds</td><td>-</td><td>-</td><td>21.98</td></tr></tbody></table>

**Hardware:** experiments were conducted on a heterogeneous computing infrastructure made of AMD EPYC 7742/7702 64-Core and Intel Xeon processors, with hardware allocation based on availability and algorithm requirements. DPDT and CART random searches ran for the equivalent of 2-days while PySTreeD ran for 10-days.

### 6.2.2 Observations.

**Generalization.** In Figure 6, we observe that DPDT learns better trees than CART and STreeD both in terms of generalization capabilities and in terms of computation cost. On Figures 6a and 6b, DPDT obtains best generalization scores for classification on

<table><caption>**Table 3:** Depth-10 decision trees for the KDD 1999 cup dataset.</caption><thead><tr><th>Model</th><th>Test Accuracy (%)</th><th>Time (s)</th><th>Memory (MB)</th></tr></thead><tbody><tr><td>DPDT-(4.)</td><td><strong>91.30</strong></td><td>339.85</td><td>5054</td></tr><tr><td>DPDT-(4,4.)</td><td><strong>91.30</strong></td><td>881.07</td><td>5054</td></tr><tr><td>CART</td><td>91.29</td><td>25.36</td><td>1835</td></tr><tr><td>GOSDT-α = 0.0005</td><td>65.47</td><td>5665.47</td><td>1167</td></tr><tr><td>GOSDT-α = 0.001</td><td>65.45</td><td>5642.85</td><td>1167</td></tr></tbody></table>

numerical and categorical data after 100 iterations of random hyperparameters search over both CART and STreeD. Similarly, we also present generalization scores as a function of compute time (instead of random search iterations). On Figures 6c and 6d, despite being coded in the slowest language (Python vs. CPython), our implementation of DPDT finds the best overall model before all STreeD random searches even finish. The results from Figure 6 are appealing for machine learning practitioners and data scientists that have to do hyperparameters search to find good models for their data while having computation constraints.

Now that we have shown that DPDT is extremely efficient to learn shallow decision trees that generalize well to unseen data, it is fair to ask if DPDT can also learn deep trees on very large datasets.

**Deeper trees on bigger datasets.** We also stress test DPDT by inducing deep trees of depth 10 for the KDD 1999 cup dataset<fnref n="5" />. The training set has 5 million rows and a mix of 80 continuous and categorical features representing network intrusions. We fit DPDT

<footnote n="5">⁵http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html</footnote>
with 4 split candidates for the root node (DPDT-(4,)) and with 4 split
candidates for the root and for each of the internal nodes at depth 1
(DPDT-(4,4,)). We compare DPDT to CART with a maximum depth
of 10 and to GOSDT<fnref n="6" /> [38] with different regularization values α.
GOSDT first trains a tree ensemble to binarize a dataset and then
solve for the optimal decision tree of depth 10 on the binarized
problem. In Table 3 we report the test accuracy of each tree on the
KDD 1999 cup test set. We also report the memory peak during
training and the training duration (all experiments are run on the
same CPU). We observe that DPDT can improve over CART even
for deep trees and large datasets while using reasonable time and
memory. Furthermore, Table 3 highlights the limitation of optimal
trees for practical problems when the dataset is not binary. We
observed that GOSDT could not find a good binarization of the
dataset even when increasing the budget of the tree ensemble up to
the point where most of the computations are spent on fitting the
ensemble (see more details about this phenomenon in [38, Section
5.3]). In table 6 in the appendix, we also show that DPDT performs
better than optimal trees for natively binary datasets. In the next
section we study the performance of boosted DPDT trees.

# 7 Application of DPDT to Boosting

In the race for machine learning algorithms for tabular data, boost-
ing procedures are often considered the go-to methods for clas-
sification and regression problems. Boosting algorithms [22–24]
sequentially add weak learners to an ensemble called strong learner.
The development of those boosting algorithms has focused on what
data to train newly added weak learners [23, 24], or on efficient
implementation of those algorithms [15, 46]. We show next that
Boosted-DPDT (boosting DPDT trees with AdaBoost [22]) improves
over recent deep learning algorithms.

## 7.1 Boosted-DPDT

We benchmark Boosted-DPDT with the same datasets, metrics, and
hardware as in the previous section on single-tree training. Second,
we verify the competitiveness of Boosted-DPDT with other models
such as deep learning ones (SAINT [51] and other deep learning
architectures from [26]).

On Figures 6e and 6f we can notice 2 properties of DPDT. First,
as in any boosting procedure, Boosted-DPDT outperforms its weak
counterpart DPDT. This serves as a sanity check for boosting DPDT
trees. Second, it is clear that boosting DPDT trees yields better mod-
els than boosting CART trees on both numerical and categorical
data. Figures 6g and 6h show that boosting DPDT trees using the
default AdaBoost procedure [22] is enough to learn models out-
performing deep learning algorithms on datasets with numerical
features and models in the top-tier on datasets with categorical fea-
tures. This show great promise for models obtained when boosting
DPDT trees with more advanced procedures.

## 7.2 (X)GB-DPDT

We also boost DPDT trees with Gradient Boosting and eXtreme Gra-
dient Boosting [15, 23, 24](X(GB)-DPDT). For each dataset from [27],
we trained (X)GB-DPDT models with 150 boosted single DPDT
trees and a maximum depth of 3 for each. We evaluate two DPDT

<figure><img src="image_8.png" /><figcaption>**Figure 7: Aggregated mean test accuracies of Gradient Boosting models as a function of the number of single trees.**</figcaption></figure>

configurations for the single trees: light (DPDT-(4, 1, 1)) and the
default (DPDT-(4,4,4)). We compare (X)GB-DPDT to (X)GB-CART:
150 boosted CART trees with maximum depth of 3 and default
hyperparameters for each. All models use a learning rate of 0.1. For
each each dataset, we normalize all boosted models scores by the
accuracy of a single depth-3 CART decision tree and aggregate the
results: the final curves represent the mean performance across
all datasets, with confidence intervals computed using 5 different
random seeds.

Figure 7 shows that similarly to simple boosting procedures like
AdaBoost, more advanced ones like (eXtreme) Gradient Boosting
yields better models when the weak learners are DPDT trees rather
than greedy trees. This is a motivation to develop efficient imple-
mentation of (eXtreme) Gradient Boosting with DPDT as the weak
learning algorithm to perform extensive benchmarking following
[27] and potentially claim the state-of-the-art.

# 8 Conclusion

In this paper, we introduced Dynamic Programming Decision Trees (DPDT), a novel framework that bridges the gap between greedy and optimal decision tree algorithms. By formulating tree induction as an MDP and employing adaptive split generation based on CART, DPDT achieves near-optimal training loss with significantly reduced computational complexity compared to existing optimal tree solvers. Furthermore, we prove that DPDT can learn strictly more accurate trees than CART.

Most importantly, extensive benchmarking on varied large and
difficult enough datasets showed that DPDT trees and boosted
DPDT trees generalize better than other baselines. To conclude, we
showed that DPDT is a promising machine learning algorithm.

The key future work would be to make DPDT industry-ready
by implementing it in C and or making it compatible with the most
advanced implementation of e.g. XGBoost.

# 9 Acknowledgments

We acknowledge the Région Hauts-de-France CPER project Cor-
nelIA. Experiments presented in this paper were carried out using
the Grid'5000 testbed (https://www.grid5000.fr). Hector Kohler ac-
knowledges the AI_PhD@Lille ANR funding.

<footnote n="6">⁶Code available at: https://github.com/ubc-systopia/gosdt-guesses</footnote>
## References

[1] Sina Aghaei, Andres Gomez, and Phebe Vayanos. 2020. Learning Optimal Classification Trees: Strong Max-Flow Formulations. arXiv:2002.09142 [stat.ML]

[2] Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. 2018. Verifiable Reinforcement Learning via Policy Extraction. In NeurIPS.

[3] Richard Bellman. 1958. Dynamic programming and stochastic control processes. Information and Control (1958).

[4] James Bergstra, Daniel Yamins, and David Cox. 2013. Making a Science of Model Search: Hyperparameter Optimization in Hundreds of Dimensions for Vision Architectures. In ICML.

[5] Dimitris Bertsimas and Jack Dunn. 2017. Optimal classification trees. Machine Learning (2017).

[6] Jock Blackard. 1998. Covertype. UCI Machine Learning Repository.

[7] Guy Blanc, Jane Lange, Chirag Pabbaraju, Colin Sullivan, Li-Yang Tan, and Mo Tiwari. 2023. Harnessing the power of choices in decision tree learning. In NeurIPS.

[8] L Breiman, JH Friedman, R Olshen, and CJ Stone. 1984. Classification and Regression Trees. Wadsworth.

[9] Brent Komer, James Bergstra, and Chris Eliasmith. 2014. Hyperopt-Sklearn: Automatic Hyperparameter Configuration for Scikit-Learn. In Proceedings of the 13th Python in Science Conference.

[10] Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen. 2024. A Theory of Interpretable Approximations. In COLT.

[11] Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. 2013. API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning.

[12] Miguel Á Carreira-Perpiñán and Arman Zharmagambetov. 2020. Ensembles of Bagged TAO Trees Consistently Improve over Random Forests, AdaBoost and Gradient Boosting. In FODS.

[13] Miguel A. Carreira-Perpiñan and Pooya Tavallali. 2018. Alternating optimization of decision trees, with application to learning sparse oblique trees. In NeurIPS.

[14] Ayman Chaouki, Jesse Read, and Albert Bifet. 2025. Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees. In ICML.

[15] Tianqi Chen and Carlos Guestrin. 2016. XGBoost: A Scalable Tree Boosting System. In KDD.

[16] Vinicius G Costa and Carlos E Pedreira. 2023. Recent advances in decision trees: An updated survey. Artificial Intelligence Review (2023).

[17] Emir Demirović, Emmanuel Hebrard, and Louis Jean. 2023. Blossom: an Anytime Algorithm for Computing Optimal Decision Trees. In ICML.

[18] Emir Demirovic, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J. Stuckey. 2022. MurTree: Optimal Decision Trees via Dynamic Programming and Search. Journal of Machine Learning Research (2022).

[19] Finale Doshi-Velez and Been Kim. 2017. Towards A Rigorous Science of Interpretable Machine Learning. arXiv:1702.08608 [stat.ML]

[20] Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux, and Patrick Gallinari. 2012. Sequential approaches for learning datum-wise sparse representations. Machine Learning (2012).

[21] Floriana Esposito, Donato Malerba, Giovanni Semeraro, and J Kay. 1997. A comparative analysis of methods for pruning decision trees. IEEE transactions on pattern analysis and machine intelligence (1997).

[22] Yoav Freund and Robert E Schapire. 1997. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. J. Comput. System Sci. (1997).

[23] Jerome H. Friedman. 2001. Greedy Function Approximation: A Gradient Boosting Machine. The Annals of Statistics (2001).

[24] Jerome H. Friedman. 2002. Stochastic gradient boosting. Comput. Stat. Data Anal. (2002).

[25] Abhinav Garlapati, Aditi Raghunathan, Vaishnavh Nagarajan, and Balaraman Ravindran. 2015. A Reinforcement Learning Approach to Online Learning of Decision Trees. arXiv:1507.06923 [cs.LG]

[26] Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. 2024. Revisiting deep learning models for tabular data. In NeurIPS.

[27] Léo Grinsztajn, Edouard Oyallon, and Gaël Varoquaux. 2022. Why do tree-based models still outperform deep learning on typical tabular data? Advances in neural information processing systems (2022).

[28] Laurent Hyafil and Ronald L. Rivest. 1976. Constructing optimal binary decision trees is NP-complete. Inform. Process. Lett. (1976).

[29] Rasul Kairgeldin and Miguel Á. Carreira-Perpiñán. 2024. Bivariate Decision Trees: Smaller, Interpretable, More Accurate. In KDD.

[30] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. Lightgbm: A highly efficient gradient boosting decision tree. NeurIPS (2017).

[31] Hector Kohler, Quentin Delfosse, Riad Akrour, Kristian Kersting, and Philippe Preux. 2024. Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning. In Seventeenth European Workshop on Reinforcement Learning.

[32] Martin L. Puterman (Ed.). 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons.

[33] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. 2020. Generalized and scalable optimal sparse decision trees. In ICML.

[34] Zachary C. Lipton. 2018. The Mythos of Model Interpretability: In machine learning, the concept of interpretability is both important and slippery. Queue (2018).

[35] Wei-Yin Loh. 2014. Fifty years of classification and regression trees. International Statistical Review (2014).

[36] Sascha Marton, Tim Grams, Florian Vogt, Stefan Lüdtke, Christian Bartelt, and Heiner Stuckenschmidt. 2024. Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization. In ICLR.

[37] Rahul Mazumder, Xiang Meng, and Haoyue Wang. 2022. Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features. In ICML.

[38] Hayden McTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis, Jacques Chen, Cynthia Rudin, and Margo Seltzer. 2022. Fast Sparse Decision Tree Optimization via Reference Ensembles. AAAI (2022).

[39] W Nor Haizan W Mohamed, Mohd Najib Mohd Salleh, and Abdul Halim Omar. 2012. A comparative study of reduced error pruning method in decision tree algorithms. In 2012 IEEE International conference on control system, computing and engineering.

[40] Sreerama Murthy and Steven Salzberg. 1995. Decision tree induction: how effective is the greedy heuristic? In KDD.

[41] Sreerama Murthy and Steven Salzberg. 1995. Lookahead and Pathology in Decision Tree Induction. In IJCAI.

[42] Sreerama K Murthy, Simon Kasif, and Steven Salzberg. 1994. A system for induction of oblique decision trees. Journal of artificial intelligence research (1994).

[43] Mohammad Norouzi, Maxwell Collins, Matthew A Johnson, David J Fleet, and Pushmeet Kohli. 2015. Efficient Non-greedy Optimization of Decision Trees. In NeurIPS.

[44] Steven W. Norton. 1989. Generating Better Decision Trees. In IJCAI.

[45] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Courneaupe, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research (2011).

[46] Liudmila Prokorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorgogush, and Andrey Gulin. 2018. CatBoost: unbiased boosting with categorical features. In NeurIPS.

[47] J. R. Quinlan. 1986. Induction of Decision Trees. Machine Learning (1986).

[48] J Ross Quinlan. 1993. C4.5: Programs for machine learning. Elsevier (1993).

[49] Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervost, Maximilian Ernestus, and Noah Dormann. 2021. Stable-BASELINES3: Reliable Reinforcement Learning Implementations. Journal of Machine Learning Research (2021).

[50] Patrick Saux, Pierre Bauvin, Violeta Raverdy, Julien Teigny, Hélène Verkind, Tomy Soumphonphakdy, Maxence Debert, Anne Jacobs, Daan Jacobs, Valerie Monpellier, Phong Ching Lee, Chin Hong Lim, Johanna C Andersson-Assarsson, Lena Carlsson, Per-Arne Svensson, Florence Galtier, Guelareh Defzoulian, Michaela Moldovanu, Severine Andrieux, Julien Couster, Marie Lepage, Erminia Lembo, Ornella Verrastro, Maud Robert, Paulina Salminen, Geltrude Mingrone, Ralph Peterli, Ricardo V Cohen, Carlos Zerrweck, David Nocca, Carel W Le Roux, Robert Caiazzo, Philippe Preux, and François Pattou. 2023. Development and validation of an interpretable machine learning-based calculator for predicting 5-year weight trajectories after bariatric surgery: a multinational retrospective cohort SOPHIA study. The Lancet Digital Health (2023).

[51] Gowthami Somepalli, Micah Goldblum, Avi Schwarzschild, C. Bayan Bruss, and Tom Goldstein. 2021. SAINT: Improved Neural Networks for Tabular Data via Row Attention and Contrastive Pre-Training. arXiv:2106.01342 [cs.LG].

[52] Nicholas Topin, Stephanie Milani, Fei Fang, and Manuela Veloso. 2021. Iterative bounding mdps: Learning interpretable policies via non-interpretable methods. In AAAI.

[53] Jacobus van der Linden, Mathijs de Weerdt, and Emir Demirović. 2023. Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming. In NeurIPS.

[54] Jacobus G. M. van der Linden, Daniël Vos, Mathijs M. de Weerdt, Sicco Verwer, and Emir Demirović. 2024. Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance. arXiv:2409.12788 [cs.LG].

[55] Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo. 2014. OpenML: networked science in machine learning. KDD.

[56] Sicco Verwer and Yingqian Zhang. 2017. Learning decision trees with flexible constraints and objectives using integer optimization. In Integration of AI and OR Techniques in Constraint Programming: 14th International Conference.

[57] Sicco Verwer and Yingqian Zhang. 2019. Learning optimal classification trees using a binary linear program formulation. In AAAI.
[58] Daniël Vos and Sicco Verwer. 2023. Optimal decision tree policies for Markov decision processes. In *IJCAI*.

[59] Daniël Vos and Sicco Verwer. 2024. Optimizing Interpretable Decision Tree Policies for Reinforcement Learning. arXiv:2408.11632 [cs.LG]

[60] Daniel Whiteson. 2014. HIGGS. UCI Machine Learning Repository.

[61] Arman Zharmagambetov, Magzhan Gabidolla, and Miguel É. Carreira-Perpiñán. 2021. Improved Boosted Regression Forests Through Non-Greedy Tree Optimization. In *IJCNN*.

[62] Arman Zharmagambetov, Suryabhan Singh Hada, Magzhan Gabidolla, and Miguel A. Carreira-Perpiñán. 2021. Non-Greedy Algorithms for Decision Tree Optimization: An Experimental Comparison. In *IJCNN*.

## A Proof of Proposition 4.1

For the purpose of the proof, we overload the definition of $J_\alpha$ and $\mathcal{L}_\alpha$, to make explicit the dependency on the dataset and the maximum depth. As such, $J_\alpha(\pi)$ becomes $J_\alpha(\pi, \mathcal{E}, D)$ and $\mathcal{L}_\alpha(T)$ becomes $\mathcal{L}_\alpha(T, \mathcal{E})$. Let us first show that the relation $J_\alpha(\pi, \mathcal{E}, 0) = -\mathcal{L}_\alpha(T, \mathcal{E})$ is true. If the maximum depth is $D = 0$ then $\pi(s_0)$ is necessarily a class assignment, in which case the expected number of splits is zero and the relation is obviously true since the reward is the opposite of the average classification loss. Now assume it is true for any dataset and tree of depth at most $D$ with $D \ge 0$ and let us prove that it holds for all trees of depth $D+1$. For a tree $T$ of depth $D+1$ the root is necessarily a split node. Let $T_l = E(\pi, s_l)$ and $T_r = E(\pi, s_r)$ be the left and right sub-trees of the root node of $T$. Since both sub-trees are of depth at most $D$, the relation holds and we have $J_\alpha(\pi, X_l, D) = \mathcal{L}_\alpha(T_l, X_l)$ and $J_\alpha(\pi, X_r, D) = \mathcal{L}_\alpha(T_r, X_r)$, where $X_l$ and $X_r$ are the datasets of the “right” and “left” states to which the MDP transitions—with probabilities $p_l$ and $p_r$—upon application of $\pi(s_0)$ in $s_0$, as described in the MDP formulation. Moreover, from the definition of the policy return we have

$$ 
\begin{aligned}
J_{\alpha}(\pi, \mathcal{E}, D+1) &= -\alpha + p_l * J_{\alpha}(\pi, X_l, D) + p_r * J_{\alpha}(\pi, X_r, D) \\
&= -\alpha - p_l * \mathcal{L}_{\alpha}(T_l, X_l) - p_r * \mathcal{L}_{\alpha}(T_r, D) \\
&= -\alpha - p_l * \left( \frac{1}{|X_l|} \sum_{(x_i, y_i) \in X_l} \ell(y_i, T_l(x_i)) + \alpha C(T_l) \right) \\
&\quad - p_r * \left( \frac{1}{|X_r|} \sum_{(x_i, y_i) \in X_r} \ell(y_i, T_r(x_i)) + \alpha C(T_r) \right) \\
&= -\frac{1}{N} \sum_{(x_i, y_i) \in X} \ell(y_i, T(x_i)) - \alpha(1 + p_l C(T_l) + p_r C(T_r)) \\
&= -\mathcal{L}(T, \mathcal{E})
\end{aligned}
$$

## B Additional Experiments and Hyperparameters

In this section we provide additional experimental results. In Table 5, we compare DPDT trees to CART and STreeD trees using 50 train/test splits of regression datasets from [27]. All algorithms are run with default hyperparameters. The configuration of DPDT is (4, 4, 4) or (4,4,4,4,4). STreeD is run with a time limit of 4 hours per tree computation and on binarized versions of the datasets. Both for depth-3 and depth-5 trees, DPDT outperforms other baselines in terms of train and test accuracies. Indeed, because STreeD runs on “approximated” datasets, it performs pretty poorly.

In Table 6, we compare DPDT(4, 4, 4, 4, 4) to additional optimal decision tree baselines on datasets with binary features. The optimal decision tree baselines run with default hyperparameters and

<table><caption>Table 4: Train accuracies of depth-3 trees (with number of operations). Lookahead trees are trained with a time limit of 12 hours.</caption><thead><tr><td>Dataset</td><td>DPDT</td><td>Lookahead-1</td></tr></thead><tbody><tr><td>avila</td><td>57.22 (1304)</td><td>OoT</td></tr><tr><td>bank</td><td>97.99 (699)</td><td>96.54 (7514)</td></tr><tr><td>bean</td><td>85.30 (1297)</td><td>OoT</td></tr><tr><td>bidding</td><td>99.27 (744)</td><td>98.12 (20303)</td></tr><tr><td>eeg</td><td>69.38 (1316)</td><td>69.09 (10108)</td></tr><tr><td>fault</td><td>67.40 (1263)</td><td>67.20 (32514)</td></tr><tr><td>htru</td><td>98.01 (1388)</td><td>OoT</td></tr><tr><td>magic</td><td>82.81 (1451)</td><td>OoT</td></tr><tr><td>occupancy</td><td>99.31 (1123)</td><td>99.01 (15998)</td></tr><tr><td>page</td><td>97.03 (1243)</td><td>96.44 (16295)</td></tr><tr><td>raisin</td><td>88.61 (1193)</td><td>86.94 (9843)</td></tr><tr><td>rice</td><td>93.44 (1367)</td><td>93.24 (37766)</td></tr><tr><td>room</td><td>99.23 (1196)</td><td>99.04 (5638)</td></tr><tr><td>segment</td><td>87.88 (871)</td><td>68.83 (24833)</td></tr><tr><td>skin</td><td>96.60 (1300)</td><td>96.61 (1290)</td></tr><tr><td>wilt</td><td>99.47 (862)</td><td>99.31 (36789)</td></tr></tbody></table>

a time-limit of 10 minutes. The results show that even on binary datasets that optimal algorithms are designed to handle well; DPDT outperforms other baselines. This is likely because optimal trees are slow and/or don't scale well to depth 5.

In Table 4 compare DPDT to lookahead depth-3 trees when optimizing Eq.1. Unlike the other greedy approaches, lookahead decision trees [44] do not pick the split that optimizes a heuristic immediately. Instead, they pick a split that sets up the best possible heuristic value on the following split. Lookahead-1 chooses nodes at depth $d < 3$ by looking 1 depth in the future: it looks for the sequence of 2 splits that maximizes the information gain at depth $d+1$. Lookahead-2 is the optimal depth-3 tree and Lookahead-0 would be just building the tree greedily like CART. The conclusion are roughly the same as for Table 1. Both lookahead trees and DPDT<fnref n="7" /> are in Python which makes them slow but comparable.

We also provide the hyperparameters necessary to reproduce experiments from section 6.2 and 7.1 in Table 7.

<footnote n="7">⁷https://github.com/KohlerHECTOR/DPDTTreeEstimator</footnote>
<table><caption>Table 5: Mean train and test scores (with standard errors) for regression datasets over 50 cross-validation runs.</caption><thead><tr><th rowspan="3">Dataset</th><th colspan="6">Depth 3</th><th colspan="6">Depth 5</th></tr><tr><th colspan="2">DPDT</th><th colspan="2">Optimal</th><th colspan="2">CART</th><th colspan="2">DPDT</th><th colspan="2">Optimal</th><th colspan="2">CART</th></tr><tr><th>Train</th><th>Test</th><th>Train</th><th>Test</th><th>Train</th><th>Test</th><th>Train</th><th>Test</th><th>Train</th><th>Test</th><th>Train</th><th>Test</th></tr></thead><tbody><tr><td>nyc-taxi</td><td>39.0 ± 0.0</td><td>38.9 ± 0.2</td><td>33.8 ± 0.0</td><td>33.8 ± 0.1</td><td>39.0 ± 0.0</td><td>38.9 ± 0.2</td><td>45.8 ± 0.0</td><td>45.7 ± 0.2</td><td>33.8 ± 0.0</td><td>33.8 ± 0.1</td><td>42.7 ± 0.0</td><td>42.6 ± 0.2</td></tr><tr><td>medical_charges</td><td>95.2 ± 0.0</td><td>95.2 ± 0.0</td><td>90.1 ± 0.0</td><td>90.1 ± 0.1</td><td>95.2 ± 0.0</td><td>95.2 ± 0.0</td><td>97.7 ± 0.0</td><td>97.7 ± 0.0</td><td>90.1 ± 0.0</td><td>90.1 ± 0.1</td><td>97.7 ± 0.0</td><td>97.7 ± 0.0</td></tr><tr><td>diamonds</td><td>93.0 ± 0.0</td><td>92.9 ± 0.1</td><td>90.1 ± 0.0</td><td>90.1 ± 0.1</td><td>92.7 ± 0.0</td><td>92.6 ± 0.1</td><td>94.2 ± 0.0</td><td>94.0 ± 0.1</td><td>90.1 ± 0.0</td><td>90.1 ± 0.1</td><td>94.1 ± 0.0</td><td>93.9 ± 0.1</td></tr><tr><td>house_16H</td><td>39.9 ± 0.1</td><td>38.1 ± 2.5</td><td>32.8 ± 0.1</td><td>29.4 ± 1.6</td><td>35.8 ± 0.1</td><td>35.8 ± 1.9</td><td>59.4 ± 0.1</td><td>35.2 ± 4.1</td><td>32.8 ± 0.1</td><td>29.4 ± 1.6</td><td>51.5 ± 0.1</td><td>41.3 ± 3.1</td></tr><tr><td>house_sales</td><td>67.0 ± 0.0</td><td>66.0 ± 0.4</td><td>65.1 ± 0.0</td><td>64.4 ± 0.4</td><td>66.8 ± 0.0</td><td>66.1 ± 0.4</td><td>77.6 ± 0.0</td><td>76.1 ± 0.3</td><td>65.1 ± 0.0</td><td>64.4 ± 0.4</td><td>76.8 ± 0.0</td><td>75.3 ± 0.4</td></tr><tr><td>superconduct</td><td>73.1 ± 0.0</td><td>72.7 ± 0.5</td><td>70.9 ± 0.0</td><td>70.5 ± 0.5</td><td>70.4 ± 0.0</td><td>69.7 ± 0.5</td><td>83.0 ± 0.0</td><td>81.7 ± 0.4</td><td>70.9 ± 0.0</td><td>70.5 ± 0.5</td><td>78.2 ± 0.0</td><td>76.5 ± 0.5</td></tr><tr><td>houses</td><td>51.7 ± 0.0</td><td>50.7 ± 0.7</td><td>48.5 ± 0.1</td><td>47.3 ± 0.7</td><td>49.5 ± 0.0</td><td>48.4 ± 0.7</td><td>69.1 ± 0.0</td><td>67.6 ± 0.5</td><td>48.5 ± 0.1</td><td>47.3 ± 0.7</td><td>60.4 ± 0.1</td><td>58.5 ± 0.6</td></tr><tr><td>Bike_Sharing</td><td>55.2 ± 0.0</td><td>54.7 ± 0.5</td><td>45.1 ± 0.1</td><td>44.8 ± 0.7</td><td>48.1 ± 0.0</td><td>47.9 ± 0.5</td><td>65.2 ± 0.0</td><td>63.3 ± 0.5</td><td>45.1 ± 0.1</td><td>44.8 ± 0.7</td><td>59.1 ± 0.0</td><td>58.6 ± 0.5</td></tr><tr><td>elevators</td><td>48.0 ± 0.0</td><td>46.8 ± 1.1</td><td>40.2 ± 0.1</td><td>38.2 ± 1.0</td><td>46.8 ± 0.0</td><td>45.5 ± 1.2</td><td>65.6 ± 0.0</td><td>61.2 ± 1.0</td><td>40.2 ± 0.1</td><td>38.2 ± 1.0</td><td>61.9 ± 0.0</td><td>58.0 ± 1.2</td></tr><tr><td>pol</td><td>72.2 ± 0.0</td><td>71.3 ± 0.6</td><td>67.8 ± 0.1</td><td>67.5 ± 0.9</td><td>72.0 ± 0.0</td><td>71.2 ± 0.8</td><td>93.3 ± 0.0</td><td>92.4 ± 0.3</td><td>67.8 ± 0.1</td><td>67.5 ± 0.9</td><td>92.1 ± 0.0</td><td>91.7 ± 0.3</td></tr><tr><td>MiamiHousing2016</td><td>62.3 ± 0.0</td><td>60.4 ± 0.8</td><td>60.8 ± 0.0</td><td>58.3 ± 0.8</td><td>62.3 ± 0.0</td><td>60.6 ± 0.8</td><td>79.8 ± 0.0</td><td>77.5 ± 0.5</td><td>60.8 ± 0.0</td><td>58.3 ± 0.8</td><td>77.3 ± 0.1</td><td>74.7 ± 0.6</td></tr><tr><td>Ailerons</td><td>63.5 ± 0.0</td><td>62.6 ± 0.7</td><td>61.6 ± 0.0</td><td>60.3 ± 0.7</td><td>63.5 ± 0.0</td><td>62.6 ± 0.7</td><td>76.0 ± 0.0</td><td>72.9 ± 0.6</td><td>61.6 ± 0.0</td><td>60.3 ± 0.7</td><td>75.5 ± 0.0</td><td>73.2 ± 0.5</td></tr><tr><td>Brazilian_houses</td><td>90.7 ± 0.0</td><td>90.3 ± 0.8</td><td>89.2 ± 0.0</td><td>89.4 ± 0.8</td><td>90.7 ± 0.0</td><td>90.4 ± 0.8</td><td>97.6 ± 0.0</td><td>96.6 ± 0.4</td><td>89.2 ± 0.0</td><td>89.4 ± 0.8</td><td>97.3 ± 0.0</td><td>96.4 ± 0.4</td></tr><tr><td>sulfur</td><td>72.5 ± 0.1</td><td>66.6 ± 2.2</td><td>35.7 ± 0.1</td><td>19.1 ± 6.7</td><td>72.0 ± 0.1</td><td>68.0 ± 2.2</td><td>89.0 ± 0.0</td><td>68.4 ± 6.7</td><td>35.7 ± 0.1</td><td>19.1 ± 6.7</td><td>81.8 ± 0.1</td><td>74.0 ± 2.2</td></tr><tr><td>yprop_41</td><td>6.3 ± 0.0</td><td>2.3 ± 0.7</td><td>3.6 ± 0.0</td><td>1.5 ± 0.4</td><td>6.2 ± 0.0</td><td>2.1 ± 0.8</td><td>13.2 ± 0.0</td><td>1.2 ± 1.7</td><td>3.6 ± 0.0</td><td>1.5 ± 0.4</td><td>10.8 ± 0.0</td><td>-1.7 ± 1.4</td></tr><tr><td>cpu_act</td><td>93.4 ± 0.0</td><td>92.0 ± 0.6</td><td>89.0 ± 0.0</td><td>86.5 ± 1.9</td><td>93.4 ± 0.0</td><td>92.0 ± 0.6</td><td>96.5 ± 0.0</td><td>94.7 ± 0.5</td><td>89.0 ± 0.0</td><td>86.5 ± 1.9</td><td>96.3 ± 0.0</td><td>95.1 ± 0.4</td></tr><tr><td>wine_quality</td><td>27.9 ± 0.0</td><td>23.3 ± 0.9</td><td>25.2 ± 0.0</td><td>23.7 ± 0.8</td><td>27.7 ± 0.0</td><td>24.5 ± 0.8</td><td>37.4 ± 0.0</td><td>26.7 ± 1.0</td><td>25.2 ± 0.0</td><td>23.7 ± 0.8</td><td>35.9 ± 0.1</td><td>26.7 ± 0.9</td></tr><tr><td>abalone</td><td>46.3 ± 0.0</td><td>39.6 ± 1.6</td><td>42.5 ± 0.0</td><td>40.4 ± 1.4</td><td>43.3 ± 0.0</td><td>39.2 ± 1.2</td><td>58.6 ± 0.0</td><td>44.7 ± 1.8</td><td>42.5 ± 0.0</td><td>40.4 ± 1.4</td><td>54.5 ± 0.0</td><td>46.3 ± 1.4</td></tr></tbody></table>

<table><caption>Table 6: Train/test accuracies of different decision tree induction algorithms. All algorithms induce trees of depth at most 5 on 8 classification datasets. A time limit of 10 minutes is set for OCT-type algorithms. The values in this table are averaged over 3 seeds giving 3 different train/test datasets.</caption><thead><tr><th rowspan="2">Names</th><th colspan="3">Datasets</th><th colspan="5">Train Accuracy depth-5</th><th colspan="5">Test Accuracy depth-5</th></tr><tr><th>Samples</th><th>Features</th><th>Classes</th><th>DPDT</th><th>OCT</th><th>MFOCT</th><th>BinOCT</th><th>CART</th><th>DPDT</th><th>OCT</th><th>MFOCT</th><th>BinOCT</th><th>CART</th></tr></thead><tbody><tr><td>balance-scale</td><td>624</td><td>4</td><td>3</td><td>90.9%</td><td>71.8%</td><td>82.6%</td><td>67.5%</td><td>86.5%</td><td>77.1%</td><td>66.9%</td><td>71.3%</td><td>61.6%</td><td>76.4%</td></tr><tr><td>breast-cancer</td><td>276</td><td>9</td><td>2</td><td>94.2%</td><td>88.6%</td><td>91.1%</td><td>75.4%</td><td>87.9%</td><td>66.4%</td><td>67.1%</td><td>73.8%</td><td>62.4%</td><td>70.3%</td></tr><tr><td>car-evaluation</td><td>1728</td><td>6</td><td>4</td><td>92.2%</td><td>70.1%</td><td>80.4%</td><td>84.0%</td><td>87.1%</td><td>90.3%</td><td>69.5%</td><td>79.8%</td><td>82.3%</td><td>87.1%</td></tr><tr><td>hayes-roth</td><td>160</td><td>9</td><td>3</td><td>93.3%</td><td>82.9%</td><td>95.4%</td><td>64.6%</td><td>76.7%</td><td>75.4%</td><td>77.5%</td><td>77.5%</td><td>54.2%</td><td>69.2%</td></tr><tr><td>house-votes-84</td><td>232</td><td>16</td><td>2</td><td>100.0%</td><td>100.0%</td><td>100.0%</td><td>100.0%</td><td>99.4%</td><td>95.4%</td><td>93.7%</td><td>94.3%</td><td>96.0%</td><td>95.1%</td></tr><tr><td>soybean-small</td><td>46</td><td>50</td><td>4</td><td>100.0%</td><td>100.0%</td><td>100.0%</td><td>76.8%</td><td>100.0%</td><td>93.1%</td><td>94.4%</td><td>91.7%</td><td>72.2%</td><td>93.1%</td></tr><tr><td>spect</td><td>266</td><td>22</td><td>2</td><td>93.0%</td><td>92.5%</td><td>93.0%</td><td>92.2%</td><td>88.5%</td><td>73.1%</td><td>75.6%</td><td>74.6%</td><td>73.1%</td><td>75.1%</td></tr><tr><td>tic-tac-toe</td><td>958</td><td>24</td><td>2</td><td>90.8%</td><td>68.5%</td><td>76.1%</td><td>85.7%</td><td>85.8%</td><td>82.1%</td><td>69.6%</td><td>73.6%</td><td>79.6%</td><td>81.0%</td></tr></tbody></table>

<table><caption>Table 7: Hyperparameter search spaces for tree-based models. More details about the hyperparameters meaning are given in [9].</caption><thead><tr><th>Parameter</th><th>CART</th><th>Boosted-CART</th><th>DPDT</th><th>Boosted-DPDT</th><th>STreeD</th></tr></thead><tbody><tr><td colspan="6"><strong>Common Tree Parameters</strong></td></tr><tr><td>max_depth</td><td>{5: 0.7,<br>2.3,4: 0.1}</td><td>{2: 0.4,<br>3: 0.6}</td><td>{5: 0.7,<br>2.3,4: 0.1}</td><td>{2: 0.4,<br>3: 0.6}</td><td>5</td></tr><tr><td>min_sample Split</td><td>{2: 0.95,<br>3: 0.05}</td><td>{2: 0.95,<br>3: 0.05}</td><td>{2: 0.95,<br>3: 0.05}</td><td>{2: 0.95,<br>3: 0.05}</td><td>-</td></tr><tr><td>min impurity decrease</td><td>{0.0: 0.85,<br>0.01,0.02,0.05: 0.05}</td><td>{0.0: 0.85,<br>0.01,0.02,0.05: 0.05}</td><td>{0.0: 0.85,<br>0.01,0.02,0.05: 0.05}</td><td>{0.0: 0.85,<br>0.01,0.02,0.05: 0.05}</td><td>-</td></tr><tr><td>min_sample Leaf</td><td>Q(log-U[2, 51])</td><td>Q(log-U[2, 51])</td><td>Q(log-U[2, 51])</td><td>Q(log-U[2, 51])</td><td>Q(log-U[2, 51])</td></tr><tr><td>min weight fraction Leaf</td><td>{0: 0.95,<br>0.01: 0.05}</td><td>{0: 0.95,<br>0.01: 0.05}</td><td>{0: 0.95,<br>0.01: 0.05}</td><td>{0: 0.95,<br>0.01: 0.05}</td><td>-</td></tr><tr><td>max_features</td><td>{"sqrt": 0.5,<br>"log2": 0.25,<br>10000: 0.25}</td><td>{"sqrt": 0.5,<br>"log2": 0.25,<br>10000: 0.25}</td><td>{"sqrt": 0.5,<br>"log2": 0.25,<br>10000: 0.25}</td><td>{"sqrt": 0.5,<br>"log2": 0.25,<br>10000: 0.25}</td><td>-</td></tr><tr><td colspan="6"><strong>Model-Specific Parameters</strong></td></tr><tr><td>maxurst</td><td>{32: 0.85,<br>5,10,15: 0.05}</td><td>{8: 0.85,<br>5: 0.05,<br>7: 0.1}</td><td>-</td><td>-</td><td>-</td></tr><tr><td>cart_nodes_list</td><td>-</td><td>-</td><td>8 configs<br>(uniform)</td><td>5 configs<br>(uniform)</td><td>-</td></tr><tr><td>learning_rate</td><td>-</td><td>log N(ln(0.01), ln(10))</td><td>-</td><td>log N(ln(0.01), ln(10))</td><td>-</td></tr><tr><td>n_estimators</td><td>-</td><td>1000</td><td>-</td><td>1000</td><td>-</td></tr><tr><td>max_num_nodes</td><td>-</td><td>-</td><td>-</td><td>-</td><td>{3,5,7,11,<br>17,25,31}<br>(uniform)</td></tr><tr><td>n_thresholds</td><td>-</td><td>-</td><td>-</td><td>-</td><td>{5,10,20,50}<br>(uniform)</td></tr><tr><td>cost_complexity</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td></tr><tr><td>time_limit</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1800</td></tr></tbody></table>