Decision Tree Learning is a fundamental problem for Interpretable Machine Learning, yet it poses a formidable optimization challenge. Despite numerous efforts dating back to the early 1990's, practical algorithms have only recently emerged, primarily leveraging Dynamic Programming (DP) and Branch & Bound (B&B) techniques. These breakthroughs led to the development of two distinct approaches. Algorithms like DL8.5 and MurTree operate on the space of nodes (or branches), they are very fast, but do not penalise complex Decision Trees, i.e. they do not solve for sparsity. On the other hand, algorithms like OSDT and GOSDT operate on the space of Decision Trees, they solve for sparsity but at the detriment of speed. In this work, we introduce , a novel algorithm that integrates the strengths of both paradigms. Leveraging DP and B&B,  achieves exceptional speed while also solving for sparsity. Central to its efficiency is a novel analytical bound enabling substantial pruning of the search space. Furthermore,  does not necessitate binary features. Theoretical analysis demonstrates that  has a lower complexity bound compared to state-of-the-art methods, a claim validated through extensive empirical evaluation. Our results illustrate that  outperforms the state of the art in terms of speed and number of iterations while consistently yielding optimal Decision Trees.

§ INTRODUCTION

While black-box models have demonstrated effectiveness across numerous applications, they are ill-suited for contexts where decisions carry substantial ramifications. In healthcare, for instance, an erroneous negative diagnosis prediction could delay crucial treatment, leading to severe outcomes for patients. Likewise, in the criminal justice system, black-box models may obscure biases associated with factors such as race or gender, potentially resulting in unjust and discriminatory rulings. These considerations underscore the importance of adopting interpretable models in sensitive domains.

Decision Trees (DTs) are valued for their ability to generate simple decision rules from data, making them highly interpretable models. Unfortunately, DT optimization poses a significant challenge due to its NP-completeness, as established by [14]. Consequently, heuristic methods, such as ID3 [22], C4.5 [21] and CART [9], have been favoured historically. These methods construct DTs greedily by maximising some local purity metric, however, while they are fast and scalable, their greedy nature often leads to suboptimal and overly complex DTs, detracting from their interpretability.

This suboptimality issue spurred researchers into investigating alternatives since the early 1990's, these alternatives are mainly based on Mathematical Programming, they range from Continuous Optimisation [5, 20, 8] to Mixed Integer Programming (MIP) [6, 26, 12] and Satisfiability (SAT) [7, 17]. However, solving these Mathematical Programs scales poorly with large datasets and many features. Moreover, these approaches often fix the DT structure and only optimise the internal splits and leaf predictions, which is a much less challenging problem than optimising both accuracy and DT structure (sparsity). Nonetheless, breakthroughs based on Dynamic Programming (DP) and Branch & Bound (B&B) have emerged recently [13, 1, 15, 11, 16, 24] and they provided the first practical algorithms for DT optimisation.

In this work, we introduce a new DP and B&B algorithm, called , that leverages a novel analytical bound to prune the search space effectively. For a comprehensive presentation of our approach, we frame it within a Reinforcement Learning (RL) framework [23], capitalizing on its convenient terminology for defining our recursive DP strategy. We analyze the complexity of  and demonstrate its superiority over existing literature. Furthermore,  we extensively compare  with state-of-the-art methods OSDT [13], DL8.5 [1] and GOSDT/PyGOSDT [15], MurTree [11] and STreeD [24].  not only achieves faster optimal convergence than competing algorithms in most cases, it also always terminates in fewer iterations, thus validating our complexity analysis. These findings position  as a serious practical DT optimisation algorithm for practitioners. Our contributions are summarized as follows:

* We derive a novel analytical bound to prune the search space effectively.

* We develop , a new DP and B&B algorithm for DT optimisation.  is based on our novel analytical bounds.

*  is not exclusively applicable to binary features.

* We analyse 's complexity and show its superiority compared to the complexity bounds derived in the literature.

* We show that  outperforms state of the art methods on various real-world datasets with regard to optimal convergence, speed and number of iterations.

§ RELATED WORK

To seek optimal DTs, a significant body of literature was devoted to the Mathematical Programming approach. We will first review these before delving into DP and B&B methods. Early approaches tackled the problem within a Continuous Optimization framework. [3, 4, 5] formulated a Multi-Linear Program to optimize a non-linear and non-convex objective function over a polyhedral region. [20] derived a smooth convex-concave upper bound on the empirical loss, which serves as a surrogate objective amenable to minimization via Stochastic Gradient Descent. In a recent development, [8] introduced soft (randomized) decision rules at internal nodes and formulated a Non-Linear Program for which they minimise the expected misclassification cost. However, except for [5], the solvers employed by these methods are locally optimal. Furthermore, Continuous Optimization lacks the flexibility needed to model univariate Decision Trees (DTs), where each internal split tests only one feature. These are of particular interest because of their interpretability. To address this limitation, a Mixed Integer Programming (MIP) framework was rather considered in a multitude of research papers [6, 25, 26, 27, 12], and alternatively, some studies have explored the Satisfiability (SAT) framework [7, 17, 2]. Despite the rich literature of Mathematical Programming approaches, they suffer from serious limitations. The number of variables involved in the Mathematical Programs increases with the size of the dataset and the number of features, slowing down the solvers and severely limiting scalability. In addition, these methods often fix a DT structure a priori and only optimise its internal splits and leaf predictions. While this simplifies the problem, it may miss out on the true optimal DT unless the optimal structure has been fixed in advance. And finally, SAT methods seek DTs that perfectly classify the dataset, often leading to overtraining.

In the last five years, DP and B&B offered the first practical algorithms for Optimal DTs, and as such, triggered a paradigm shift from Mathematical Programming. The first of these algorithms is OSDT [13], it seeks to minimise a regularised misclassification error objective on the space of DTs; to do so, it employs a series of analytical bounds to prune the search space. OSDT was followed shortly after by GOSDT [15] to generalise the approach to other objective functions. In contrast, DL8.5 [1] is a fundamentally different approach, it is based on ideas from the earlier DL8 algorithm [18, 19]. DL8 operates on a lattice of itemsets as its search space, from which it mines the optimal DT, this is fundamentally distinct from the search space of DTs employed by OSDT and GOSDT. However, DL8 is a purely DP algorithm, and as such it is computationally and memory inefficient. DL8.5 addressed this issue by incorporating B&B to DL8. DL8.5 offers high speed and scalability, albeit without addressing sparsity (it fixes a maximum depth but does not actively minimise the depth or the number of leaves). Additionally, DL8.5's B&B strategy is based on the best solution found so far rather than more sophisticated analytical bounds, hindering its pruning capacity of the search space. Meanwhile, OSDT and GOSDT solve for sparsity but are comparatively slower. Our work is motivated by this landscape, aiming to leverage the speed and scalability of methods like DL8.5 while addressing sparsity concerns in similar fashion to methods like OSDT and GOSDT.

Additional recent advancements in the field include MurTree [11], which enhances DL8.5 with similarity bounds and a tailored method for handling DTs of depth 2. [16] introduce a guessing strategy to navigate the search space, seeking solutions with performance akin to a reference ensemble model. [24] investigate separable objectives and constraints and introduce a generalised DP framework called STreeD.

§ PROBLEM FORMULATION

We consider classification problems with categorical features $X = \left( X^{\left( 1\right)}, \ldots, X^{\left( q\right)}\right)$ and class variable $Y=\{ 1, \ldots, K\}$ such that $\forall{i \in \{ 1, \ldots q\}}: X^{\left( i\right)} \in \{ 1, \ldots, C_i\}$ where $C_i \ge 2, \; q \ge 2$ and $K \ge 2$. We are provided with a dataset $\mathcal{D} = \{ \left( X_m, Y_m\right)\}_{m=1}^n$ of $n \ge 1$ examples.

§.§ Branches

A branch (or leaf) $l$ is a conjunction of clauses on the features of the following form:

\[
l = \bigwedge_{v=1}^{\splits\left( l\right)}\ind\Big\{ X^{\left( i_v\right)} = j_v\Big\}
\]

Such that $\forall{v \in \{ 1, \ldots, \splits\left( l\right)\}}: i_v \in \{ 1, \ldots, q\},\, j_v \in \{ 1, \ldots, C_{i_v}\}$ and:

\begin{align}
\forall{v, v' \in \{ 1, \ldots \splits\left( l\right)\}}: v \neq v' \implies i_v \neq i_{v'} \label{eq:branch-condition}
\end{align}

This condition states that no feature is used in more than one clause within $l$. We refer to these clauses as rules or splits. $\splits\left( l\right)$ is the number of splits in $l$.

For any datum $X$, the valuation of $l$ for $X$ is denoted $l\left( X\right) \in \{ 0, 1\}$ and defined as follows:

\[
l\left( X\right) = 1 \iff \bigwedge_{v=1}^{\splits\left( l\right)}\ind\Big\{ X^{\left( i_v\right)} = j_v\Big\} = 1
\]

When $l\left( X\right) = 1$, we say that $X$ is in $l$ or that $l$ contains $X$. The branch containing all possible data is called the root and denoted $\Omega$. Since the valuation of $l$ for any datum is invariant when reordering its splits, we uniquely represent $l$ by ordering its splits from the smallest feature index to the highest, i.e. we impose $1 \le i_1 < \ldots < i_{\splits\left( l\right)} \le q$. This unique representation is at the core of DP's memoisation.

In the following, we define the notion of splitting a branch. Let $i \in \{ 1, \ldots, q\} \setminus \{ i_1, \ldots, i_{\splits\left( l\right)}\}$ be an unused feature in the splits of $l$. We define the children of $l$ that stem from splitting $l$ with respect to $i$ as the set $\children\left( l, i\right) = \{ l_1, \ldots, l_{C_i}\}$ where:

\[
\forall{j \in \{ 1, \ldots, C_i\}}: l_j = l \wedge \ind\Big\{ X^{\left( i\right)} = j\Big\}
\]

The dataset $\mathcal{D}$ provides an empirical distribution of the data. The probability that a datum is in $l$ is:

\[
\prob\left[ l\left( X\right) = 1\right] = \frac{n\left( l\right)}{n}
\]

Where $n\left( l\right) = \sum_{m=1}^n l\left( X_m\right)$ is the number of data in $l$. Likewise, we want to define the probability that a datum is in $l$ and correctly classified. For this purpose, we define the predicted class in $l$ as:

\[
k^*\left( l\right) = \mathrm{Argmax}_{1 \le k \le K} \{ n_k\left( l\right)\}
\]

Where $n_k\left( l\right) = \sum_{m=1}^n l\left( X_m\right)\ind\{ Y_m = k\}$ is the number data in $l$ that are of class $k$. $k^*\left( l\right)$ is the majority class in $l$. Then the probability that a datum is in $l$ and correctly classified is:

\[
\objective\left( l\right) = \prob\left[ l\left( X\right) = 1, Y = k^*\left( l\right)\right] = \frac{n_{k^*\left( l\right)}\left( l\right)}{n}
\]

§.§ Decision Trees

Let $l$ be a branch, a sub-DT rooted in $l$ is a collection of branches $T = \big\{ l_1, \ldots, l_{|T|}\big\}$ that partition $l$.

\begin{align*}
l = \bigvee_{u=1}^{|T|}l_u, \; \; \; \forall{u, u' \in \{ 1, \ldots, |T|\}}: u \neq u' \implies l_u \wedge l_{u'} = 0
\end{align*}

$T$ stems from a series of successive splittings of $l$, its children and so on. We denote $\splits\left( T\right)$ the number of these splits it took to construct $T$ from $l$.

For any datum $X$ in $l$, $T$ predicts the majority class of the branch $l_u$ containing $X$:

\[
T\left( X\right) = \sum_{u=1}^{|T|}l_u\left( X\right)k^*\left( l_u\right)
\]

Now we can define the proportion of data in $\mathcal{D}$ that is in $l$ and is correctly classified by $T$:

\[
\objective\left( T\right) = \prob\left[ l\left( X\right) = 1, T\left( X\right) = Y\right] = \sum_{i=1}^{|T|}\objective\left( l_u\right)
\]

The additivity property is due to $\{ l_1, \ldots, l_{|T|}\}$ forming a partition of $l$.

A DT is a sub-DT that is rooted in $\Omega$. Let $T$ be a DT, since $\Omega\left( X\right) = 1$ for any datum $X$, then:

\[
\objective\left( T\right) = \prob\left[ T\left( X\right) = Y\right]
\]

In this case, $\objective\left( T\right)$ is the accuracy of $T$. Maximising accuracy is not a suitable objective, it overlooks the sparsity portion of the problem and likely leads to overtraining issues. For instance, the complete DT that uses all possible splits has maximum accuracy, yet it is a very complex DT that just corresponds to point-wise classification of all data in $\mathcal{D}$. Such solution is of no interest. To incorporate sparsity, we rather consider the following regularised objective:

\[
\objectiver\left( T\right) = -\lambda\splits\left( T\right) + \objective\left( T\right)
\]

$\lambda \in \left[ 0, 1\right]$ is a penalty parameter penalising DTs with too many splits. This objective is employed by CART during the pruning phase, it was also considered by [6] and recently by [10]. OSDT employs a slightly different version, where the total number of leaves is penalised instead, the two versions are equivalent when all features share the same number of categories, albeit for slightly different values of $\lambda$.

§.§ Markov Decision Process (MDP)

To frame the problem within a Reinforcement Learning framework, we define the following MDP.

State space: The set of all possible sub-DTs. A state with only one branch $T = \{ l\}$ is called a unit-state. To make the notation lighter, we just denote it $l$. There are special types of states called absorbing states. A state is absorbing if all actions transition back to it and yield $0$ reward, a non-absorbing state that can only transition to an absorbing state is called a terminal state.

Action space: $\action\left( l\right)$ is the set of permissible actions in a unit-state $l$. There are two types of actions:

* The terminal action $\overline{a}$. It transitions from $l$ to an absorbing state $\overline{l}$. We denote $l \overset{\overline{a}}{\longrightarrow} \overline{l}$.

* Split actions. Consider a unit-state $l = \bigwedge_{v=1}^{\splits\left( l\right)}\ind\{ X^{\left( i_v\right)} = j_v\}$, the set of possible split actions at $l$ is $\{ 1, \ldots, q\} \setminus \{ i_1, \ldots, i_{\splits\left( l\right)}\}$. Let $i$ be a split action, taking $i$ transitions $l$ to state $T = \children\left( l, i\right)$. We denote the transition with $l \overset{i}{\longrightarrow} T = \children\left( l, i\right)$.

Thus $\action\left( l\right) = \{ \overline{a}\} \cup \{ 1, \ldots, q\} \setminus \{ i_1, \ldots, i_{\splits\left( l\right)}\}$. When $\splits\left( l\right) = q$, then $\action\left( l\right) = \{ \overline{a}\}$ and we can only transition to $\overline{l}$. We now define the set of permissible actions for any state $T = \{ l_1, \ldots l_{|T|}\}$ as $\action\left( T\right) = \action\left( l_1\right)\times \ldots \times \action\left( l_{|T|}\right)$. Taking action $a = \left( a_1, \ldots, a_{|T|}\right) \in \action\left( T\right)$ in $T$ is equivalent to taking each action $a_u$ in $l_u$ for $1 \le u \le |T|$, thus performing the transition:

\[
T \overset{a}{\longrightarrow} T' = \bigcup_{u=1}^{|T|}T'_u, \; \; \forall{u \in \{ 1, \ldots, |T|\}}: l_u \overset{a_u}{\longrightarrow}T'_u = \children\left( l_u, a_u\right)
\]

Reward function: Let $l$ be a unit-state and $a \in \action\left( l\right)$. We denote $r\left( l, a\right)$ the reward of taking $a$ in $l$.

* If $a$ is a split action, then $r\left( l, a\right) = -\lambda$ regardless of $l$.

* If $a = \overline{a}$, then $r\left( l, \overline{a}\right) = \objective\left( l\right)$.

* If $l = \overline{l}$, i.e. $l$ is an absorbing state, then $r\left( \overline{l}, a\right) = 0$.

For any state $T = \{ l_1, \ldots, l_{|T|}\}$ and action $a = \left( a_1, \ldots, a_{|T|}\right) \in \action\left( T\right)$, we define the reward:

\[
r\left( T, a\right) = \sum_{u=1}^{|T|}r\left( l_u, a_u\right)
\]

A policy $\pi$ maps each state $T$ to one of its actions $\pi\left( T\right) \in \action\left( T\right)$. The trajectory of $\pi$ starting from $T$ is the series of states $\left( T_t\right)_{t=0}^\infty$ such that $T_0 = T$ and $\forall{t \ge 0}: T_t \overset{\pi\left( T_t\right)}{\longrightarrow} T_{t+1}$, the return of policy $\pi$ from $T$ is the cumulative reward of following $\pi$ starting from $T$:

\[
\rf^\pi\left( T\right) = \sum_{t=0}^\infty r\left( T_t, \pi\left( T_t\right)\right)
\]

For any policy $\pi$ and unit-state $l$, there exists $\tau \ge 0$ such that for any $t \ge \tau$, $T_t = \{ \overline{l_1}, \ldots, \overline{l_{|T_\tau|}}\}$ is an absorbing state. In which case we call $T_l^{\pi} = \{ l_1, \ldots, l_{|T_\tau|}\}$ the sub-DT of $\pi$ rooted in $l$. If $l=\Omega$ we abbreviate the notation $T_\Omega^{\pi} \equiv T^\pi$ and call $T^\pi$ the DT of $\pi$.

<ref> states that all policies arrive in an absorbing state after a finite number of steps, regardless of where they start. Therefore all policies have finite returns.

For any policy $\pi$ and unit-state $l$, the return of $\pi$ from $l$ satisfies:

\[
\rf^\pi\left( l\right) = \objectiver\left( T_l^\pi\right) = -\lambda\splits\left( T_l^\pi\right) + \objective\left( T_l^\pi\right)
\]

In particular $\rf^\pi\left( \Omega\right) = \objectiver\left( T^\pi\right) = -\lambda\splits\left( T^\pi\right) + \objective\left( T^\pi\right)$.

<ref> links the return of a policy to the regularised accuracy of its sub-DT. On the other hand, since any DT $T$ is constructed with successive splits starting from $\Omega$, there always exists a policy $\pi$ such that $T^\pi = T$, and therefore $\rf^\pi\left( \Omega\right) = \objectiver\left( T\right)$. This result provides the equivalence between finding the optimal DT and the optimal policy:

\[
T^* = \mathrm{Argmax}_T\{ \objectiver\left( T\right)\}, \; \pi^* = \mathrm{Argmax}_\pi \{ \rf^\pi\left( \Omega\right)\}
\]

In which case the optimal DT is the DT of $\pi^*$, i.e. $T^* = T^{\pi^*}$. To conclude this section, our objective is now is to find $\pi^*$ and then deduce $T^*$ as $T^{\pi^*}$. We abbreviate the notation $\rf^{\pi^*} \equiv \rf^*$.

§ THE ALGORITHM:

is a Value Iteration algorithm that is enhanced with a structured B&B search. To describe this algorithm, it is convenient to further introduce the state-action return quantity. For any policy $\pi$, state $T$ and action $a \in \action\left( T\right)$, let $T \overset{a}{\longrightarrow} T_1 = \{ l_1, \ldots, l_{|T_1|}\}$ and $\left( T_t\right)_{t=1}^\infty$ be the trajectory of $\pi$ starting from state $T_1$. Then the state-action return of $\pi$ from $T$ is the cumulative reward of taking action $a$ first, then following $\pi$:

\[
\qf^{\pi}\left( T, a\right) = r\left( T, a\right) + \sum_{t=1}^\infty r\left( T_t, \pi\left( T_t\right)\right) = r\left( T, a\right) + \rf^\pi\left( T_1\right)
\]

Given the optimal state-action returns $\qf^{*}\left( T, a\right) = \qf^{\pi^*}\left( T, a\right)$, we can deduce the optimal policy as:

\[
\pi^*\left( T\right) =\mathrm{Argmax}_{a \in \action\left( T\right)}\qf^{*}\left( T, a\right)
\]

In the next section, we show how  estimates these optimal state-action returns.

§.§ Estimating the optimal state-action returns $\qf^*\left( l, a\right)$

Let $l$ be a non-absorbing unit-state and $a \in \action\left( l\right)$, we denote $\qf\left( l, a\right)$ the estimate of $\qf^*\left( l, a\right)$. For the terminal action $\overline{a}$, $\qf^*\left( l, \overline{a}\right)$ is directly accessible from the data:

\[
\qf\left( l, \overline{a}\right) = \qf^*\left( l, \overline{a}\right) = r\left( l, \overline{a}\right) = \objective\left( l\right) = \frac{n_{k^*\left( l\right)}\left( l\right)}{n}
\]

For a split action $a \in \action\left( l\right)\setminus \{ \overline{a}\}$, such that $l \overset{a}{\longrightarrow} T = \{ l_1, \ldots, l_{|T|}\}$, $\qf\left( l, a\right)$ is defined according to the Bellman Optimality Equations below.

Let $l$ be a non-absorbing unit-state, $a \in \action\left( l\right) \setminus \{ \overline{a}\}$ a split action such that $l \overset{a}{\longrightarrow} T = \{ l_1, \ldots, l_{|T|}\}$. Then we have:

\begin{align}
\qf^*\left( l, a\right) &= -\lambda + \rf^*\left( T\right) =  -\lambda + \sum_{u=1}^{|T|}\rf^*\left( l_u\right)\nonumber \\
\forall{u \in \{ 1, \ldots, |T|\}}: \rf^*\left( l_u\right) &= \qf^*\left( l_u, \pi^*\left( l_u\right)\right) = \max_{a \in \action\left( l_u\right)}\qf^*\left( l_u, a\right) \nonumber
\end{align}

<ref> suggests the following recursive estimates for $\qf^*\left( l, a\right)$:

\begin{align}
\qf\left( l, a\right) &= -\lambda + \sum_{u=1}^{|T|}\rf\left( l_u\right) \label{eq:state-action-estimate}\\
\forall{u \in \{ 1, \ldots, |T|\}}: \rf\left( l_u\right) &= \max_{a \in \action\left( l_u\right)}\qf\left( l_u, a\right)\label{eq:state-estimate}
\end{align}

The estimate $\qf\left( l, a\right)$ in <ref> can only be calculated if the estimates $\rf\left( l_u\right)$ in <ref> are available. Otherwise we initialise $\qf\left( l, a\right)$ with <ref> according to <ref>.

For any non-absorbing unit-state $l$ and $a \in \action\left( l\right)\setminus \{ \overline{a}\}$ a split action, we define the Purification Bounds estimates:

\begin{align}
\qf\left( l, a\right) &= -\lambda + \prob\left[ l\left( X\right) = 1\right] = -\lambda + \frac{n\left( l\right)}{n} \label{eq:upper-bound-state-action-return}\\
\rf\left( l\right) &= \max\{ \objective\left( l\right), -\lambda + \prob\left[ l\left( X\right) = 1\right]\} \label{eq:upper-bound-state-return}
\end{align}

Then the estimates $\qf\left( l, a\right)$ and $\rf\left( l\right)$ are upper bounds on $\qf^*\left( l, a\right)$ and $\rf^*\left( l\right)$ respectively:

\begin{align*}
\qf\left( l, a\right) &\ge \qf^*\left( l, a\right)\\
\rf\left( l\right) &\ge \rf^*\left( l\right)
\end{align*}

If the split action $a$ yields $l \overset{a}{\longrightarrow} T = \{ l_1, \ldots, l_{|T|}\}$ such that all the data in the resulting children branches $l_u$ are correctly classified (in which case we can call branches $l_u$ as pure), then:

\[
\qf^*\left( l, a\right) = -\lambda + \objective\left( T\right) = -\lambda + \prob\left[ T\left( X\right) = Y, l\left( X\right) = 1\right] = -\lambda + \prob\left[ l\left( X\right) = 1\right]
\]

Thus the bound in <ref> coincides exactly with the optimal state-action return of an action that purifies $l$ (if it exists), hence the name Purification Bounds.

In the following section, we explain the different steps that  takes during each iteration. For a full pseudo-code description, please refer to <ref> in the Appendix.

§.§ Algorithmic steps of an iteration

Initially, all the non-terminal unit-states $l$ are labelled as unvisited and incomplete, which means that we do not know $\rf^*\left( l\right)$ yet. Moreover, the state-action pairs $\left( l, a\right)$ are also labelled as incomplete, i.e. we do not know $\qf^*\left( l, a\right)$ yet. For the DP part of the algorithm, we initialise an empty memo. At each iteration,  follows the steps below:

* Selection: Initialise an empty list path. Starting from the root $l = \Omega$. Choose the action maximising the optimal state-action return estimate:

\[
a = \mathrm{Argmax}_{a' \in \action\left( l\right)} \qf\left( l, a'\right)
\]

Append $\left( l, a\right)$ to path and transition $l \overset{a}{\longrightarrow} T = \{ l_1, \ldots, l_{|T|}\}$. Choose an incomplete unit-state $l_u$ with lowest $\objective\left( l_u\right)$ and make it the current state $l = l_u$. Repeat this process until reaching an unvisited or terminal unit-state $l$.

* Expansion: We set $\qf\left( l, \overline{a}\right) = \objective\left( l\right)$ and label $\left( l, \overline{a}\right)$ as complete.

If $l$ is a terminal state, we have $\action\left( l\right) = \{ \overline{a}\}$ and therefore:

\[
\rf\left( l\right) = \qf\left( l, \overline{a}\right) = \qf^*\left( l, \overline{a}\right) = \objective\left( l\right) = \frac{n_{k^*\left( l\right)}\left( l\right)}{n}
\]

We label $l$ as visited and complete.

On the other hand, if $l$ is not terminal, then for each split action $a \in \action\left( l\right) \setminus \{ \overline{a}\}$ such that $l \overset{a}{\longrightarrow} T=\{ l_1, \ldots, l_{|T|}\}$, we set:

\begin{align*}
\qf\left( l, a\right) &= -\lambda + \sum_{u=1}^{|T|}\rf\left( l_u\right)\\
\rf\left( l\right) &= \max_{a \in \action\left( l\right)}\qf\left( l, a\right)
\end{align*}

Where $\rf\left( l_u\right)$ is retrieved from the memo in case $l_u$ is labelled as visited, otherwise $\rf\left( l_u\right)$ is initialised according to <ref>:

\[
\rf\left( l_u\right) = \max\{ \objective\left( l_u\right), -\lambda + \prob\left[ l_u\left( X\right) = 1\right]\}
\]

If all children $l_u$ are complete, then we label $\left( l, a\right)$ as complete and we have $\qf\left( l, a\right) = \qf^*\left( l, a\right)$. If $a^* = \mathrm{Argmax}_{a \in \action\left( l\right)}\qf\left( l, a\right)$ is such that $\left( l, a^*\right)$ is complete, then we label $l$ as complete and we have $\rf^*\left( l\right) = \rf\left( l\right) = \qf\left( l, a^*\right) = \qf^*\left( l, a^*\right)$. We store $\rf\left( l\right)$ in the memo and label $l$ as visited.

* Backpropagation: Update the $\qf\left( l, a\right)$ and $\rf\left( l\right)$ for all $\left( l, a\right)$ in path by a Backward recursion. For $j=length(path)-1, \ldots, 0$, let $\left( l, a\right) = path\left[ j\right]$ with $l \overset{a}{\longrightarrow} T=\{ l_1, \ldots, l_{|T|}\}$, then we update $\qf\left( l, a\right)$ and $\rf\left( l\right)$ with:

\begin{align*}
\qf\left( l, a\right) &= -\lambda + \sum_{u=1}^{|T|}\rf\left( l_u\right)\\
\rf\left( l\right) &= \max_{a \in \action\left( l\right)}\qf\left( l, a\right)
\end{align*}

If all children $l_u$ are complete, we label $\left( l, a\right)$ as complete. If $a^* = \mathrm{Argmax}_{a \in \action\left( l\right)}\qf\left( l, a\right)$ is such that $\left( l, a^*\right)$ is complete, then we label $l$ as complete. We update $\rf\left( l\right)$ in the memo.

The algorithm runs until the root $\Omega$ is complete. The proposed policy solution is then:

\[
\Tilde{\pi}\left( T\right) =\mathrm{Argmax}_{a \in \action\left( T\right)}\qf\left( T, a\right)
\]

We note that, in this section, we have presented the algorithmic idea behind . During implementation, we use priority queues for computational efficiency, the full implementation details and pseudo-code are provided in <ref>.

§.§ Theoretical analysis

In this section, we first prove the optimality of  in <ref>, then we analyse its complexity in <ref> and <ref>. The objective of our complexity analysis is to compare the bounds we derive with those provided in the literature.

When  terminates, its proposed policy solution $\Tilde{\pi}$ is optimal, i.e. $\Tilde{\pi} = \mathrm{Argmax}_\pi\rf^\pi\left( \Omega\right)$.

To the best of our knowledge, [13] are the only authors providing a complexity analysis of their algorithm in the DP and B&B literature. In Theorem E.2, the authors derive an upper bound on the total number of DT evaluations performed by OSDT. There is a slight mistake in the formula, the maximum depth cannot exceed the number of features $q$ not $2^q$. We provide a corrected version of that result and discuss it in <ref>.

Let $\Gamma\left( q, C, \lambda\right)$ denote the total number of branch evaluations performed by  for an instance of the classification problem with $q \ge 2$ features, $0 < \lambda \le 1$ the penalty parameter, and $C \ge 2$ the number of categories of each feature. Then, $\Gamma\left( q, C, \lambda\right)$ is bounded by the following:

\[
\Gamma\left( q, C, \lambda\right) \le \sum_{h = 0}^\kappa \left( q - h\right)C^{h+1}\binom{q}{h}; \; \kappa = \min\Bigg\{ \floor*{\splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}}, \frac{C^q - 1}{C-1} \Bigg\}
\]

Let $\Gamma\left( q, \lambda, C\right)$ be defined as in <ref>, then we have:

\[
\Gamma\left( q, C, \lambda\right) \le \sum_{h = 0}^\kappa \left( q-h\right)C^{h+1}\binom{q}{h}; \; \kappa = \min\Bigg\{ \floor*{\frac{K-1}{K\lambda}}-1, \frac{C^q - 1}{C-1} \Bigg\}
\]

<ref> compares the bounds on the complexities of OSDT and  using <cit.> and <ref>. It clearly shows the vast computational gains that  offers over OSDT. This claim is further validated in our experiments. We note however, that the immense numbers upper bounding the complexity of OSDT do not reflect OSDT's true complexity but rather that the bound is too loose. Indeed, the reasoning behind OSDT's complexity bound pertains to counting all the possible DTs which depths do not exceed the maximum depth of the optimal DT, it does not analyse OSDT's pruning capacity. In fact, it is unclear how such analysis could be performed with OSDT's bounds. The Purification bounds on the other hand, <ref>, offer a natural pruning strategy that allows for such analysis.

<ref> and <ref> are sufficient to emphasize ' computational efficiency. Nonetheless, a more careful analysis yields further tighter bounds, albeit at the cost of more complicated formulae. These tighter bounds are provided in <ref> and <ref>.

Comparing the complexity bounds of  and OSDT for binary features and for different values of $\lambda$ and $q$. $\mathrm{INF}$ means that the number is so large that it leads to overflow issues.

2c?$q=10$     2c?$q=15$     2c?$q=20$

1?c?1*$\lambda$         OSDT         OSDT         OSDT
$0.1$     $\bm{5.70\times 10^4}$     $5.61\times10^{13}$     $\bm{5.80\times 10^5}$     $6.86\times 10^{16}$     $\bm{2.82\times 10^6}$     $8.35 \times 10^{18}$

$0.05$     $\bm{3.94\times 10^5}$     $7.52\times10^{271}$     $\bm{7.53\times 10^7}$     $1.53\times 10^{473}$     $\bm{3.01\times 10^9}$     $5.69\times 10^{576}$

$0.01$     $\bm{3.94\times 10^5}$     $1.64\times10^{392}$     $\bm{1.43\times 10^8}$     $\mathrm{INF}$     $\bm{4.65\times 10^{10}}$     $\mathrm{INF}$

§ EXPERIMENTS

Comparing  with OSDT, PyGOSDT and GOSDT, objective here refers to the regularised objective $\objectiver$. $TO$ refers to timeout.

1?c?2*Dataset     3c?OSDT     3c?PyGOSDT     3c?GOSDT     3c?

90objective     90time (s)     90iterations     90objective     90time (s)     90iterations     90objective     90time (s)     90iterations     90objective     90time (s)     90iterations
monk1-l     $\bm{0.93}$     $71$     $2\mathrm{e}6$     $\bm{0.93}$     $181$     $3\mathrm{e}6$     $\bm{0.93}$     $0.71$     $3\mathrm{e}{4}$     $\bm{0.93}$     $\bm{0.11}$     $\bm{617}$
monk1-f     $0.97$     $TO$     $2\mathrm{e}4$     $0.97$     $TO$     $2\mathrm{e}3$     $\bm{0.983}$     $4.02$     $9\mathrm{e}4$     $\bm{0.983}$     $\bm{1.31}$     $\bm{1\mathrm{e}4}$
monk1-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.9}$     $\bm{0.02}$     $\bm{64}$
monk2-l     $0.95$     $TO$     $7\mathrm{e}4$     $0.95$     $TO$     $400$     $\bm{0.97}$     $10$     $1\mathrm{e}{5}$     $\bm{0.97}$     $\bm{2.8}$     $\bm{3\mathrm{e}4}$
monk2-f     $0.90$     $TO$     $4\mathrm{e}4$     $0.90$     $TO$     $3\mathrm{e}4$     $\bm{0.93}$     $11.1$     $1\mathrm{e}5$     $\bm{0.93}$     $\bm{5.9}$     $\bm{7\mathrm{e}4}$
monk2-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.95}$     $\bm{0.14}$     $\bm{1\mathrm{e}3}$
monk3-l     $0.979$     $TO$     $596$     $0.979$     $TO$     $123$     $\bm{0.981}$     $7.38$     $8\mathrm{e}{4}$     $\bm{0.981}$     $\bm{1.20}$     $\bm{9\mathrm{e}3}$
monk3-f     $0.975$     $TO$     $1\mathrm{e}4$     $0.973$     $TO$     $9\mathrm{e}3$     $\bm{0.983}$     $2.13$     $5\mathrm{e}4$     $\bm{0.983}$     $\bm{1.14}$     $\bm{9\mathrm{e}3}$
monk3-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.987}$     $\bm{0.04}$     $\bm{156}$
tic-tac-toe     $0.765$     $TO$     $40$     $0.808$     $TO$     $37$     $\bm{0.850}$     $\bm{41}$     $1.6\mathrm{e}6$     $\bm{0.850}$     $68$     $\bm{2.6\mathrm{e}5}$
tic-tac-toe-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.832}$     $\bm{0.95}$     $\bm{3479}$
car-eval     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.799}$     $\bm{18}$     $9\mathrm{e}5$     $\bm{0.799}$     $62$     $\bm{3\mathrm{e}5}$
car-eval-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.812}$     $\bm{0.11}$     $\bm{632}$
nursery     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $0.765$     $TO$     $7\mathrm{e}5$     $\bm{0.820}$     $TO$     $3\mathrm{e}5$
nursery-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.822}$     $\bm{0.34}$     $\bm{244}$
mushroom     $\bm{0.945}$     $TO$     $4\mathrm{e}6$     $\bm{0.945}$     $TO$     $2\mathrm{e}6$     $0.925$     $TO$     $1\mathrm{e}6$     $0.938$     $TO$     $2\mathrm{e}4$
mushroom-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.975}$     $\bm{0.17}$     $\bm{6}$
kr-vs-kp     $\bm{0.900}$     $TO$     $6\mathrm{e}4$     $\bm{0.900}$     $TO$     $2\mathrm{e}4$     $0.815$     $TO$     $4\mathrm{e}5$     $\bm{0.900}$     $TO$     $8\mathrm{e}4$
kr-vs-kp-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.900}$     $TO$     $8\mathrm{e}4$
zoo     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.992}$     $34$     $3\mathrm{e}5$     $\bm{0.992}$     $\bm{15}$     $\bm{3\mathrm{e}4}$
zoo-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.993}$     $\bm{0.94}$     $\bm{1456}$
lymph     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $0.784$     $TO$     $1\mathrm{e}6$     $\bm{0.808}$     $TO$     $1\mathrm{e}5$
lymph-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.852}$     $\bm{18}$     $\bm{2\mathrm{e}4}$
balance     $\bm{0.693}$     $TO$     $1\mathrm{e}5$     $\bm{0.693}$     $TO$     $3\mathrm{e}4$     $\bm{0.693}$     $\bm{21}$     $1\mathrm{e}6$     $\bm{0.693}$     $62$     $\bm{3\mathrm{e}5}$
balance-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.661}$     $\bm{0.02}$     $\bm{130}$

Comparing  with DL8.5, MurTree and StreeD, objective here refers to the regularised objective $\objectiver$. $TO$ refers to timeout.

1?c?2*Dataset     2c?DL8.5     2c?MurTree     2c?STreeD     2c?

90objective     90time (s)     90objective     90time (s)     90objective     90time (s)     90objective     90time (s)
monk1-l     $0.71$     $0.007$     $0.78$     $0.002$     $\bm{0.93}$     $2.74$     $\bm{0.93}$     $\bm{0.11}$
monk1-f     $0.958$     $0.008$     $0.963$     $0.001$     $0.978$     $0.11$     $\bm{0.983}$     $\bm{1.31}$
monk1-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.9}$     $\bm{0.02}$
monk2-l     $0.955$     $0.001$     $0.964$     $0.18$     $0.964$     $0.25$     $\bm{0.97}$     $\bm{2.8}$
monk2-f     $0.887$     $0.04$     $0.877$     $0.46$     $0.877$     $0.62$     $\bm{0.93}$     $\bm{5.9}$
monk2-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.95}$     $\bm{0.14}$
monk3-l     $0.955$     $0.007$     $0.964$     $0.04$     $0.96$     $0.06$     $\bm{0.981}$     $\bm{1.20}$
monk3-f     $0.957$     $0.009$     $0.966$     $0.02$     $\bm{0.983}$     $\bm{0.2}$      $\bm{0.983}$     $1.14$
monk3-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.987}$     $\bm{0.04}$
tic-tac-toe     $0.782$     $1.09$     $0.787$     $5.08$     $0.849$     $45$     $\bm{0.850}$     $\bm{68}$
tic-tac-toe-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.832}$     $\bm{0.95}$
car-eval     $0.680$     $0.419$     $0.720$     $6.29$     $0.795$     $54$     $\bm{0.799}$     $\bm{62}$
car-eval-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.812}$     $\bm{0.11}$
nursery     $0.396$     $1.90$     $0.547$     $93$     0.4cm0.3mm     $TO$     $\bm{0.820}$     $TO$
nursery-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.822}$     $\bm{0.34}$
mushroom     $0.730$     $0.05$     $0.850$     $3.2$     0.4cm0.3mm     $TO$     $\bm{0.938}$     $TO$
mushroom-o      0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.975}$     $\bm{0.17}$
kr-vs-kp     $0.434$     $28$     $0.583$     $122$     0.4cm0.3mm     $TO$     $\bm{0.900}$     $TO$
kr-vs-kp-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.900}$     $TO$
zoo     $0.988$     $0.007$     $0.989$     $0.23$     $\bm{0.992}$     $\bm{0.012}$     $\bm{0.992}$     $15$
zoo-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.993}$     $\bm{0.94}$
lymph     $0.640$     $1.02$     $0.700$     $4.89$     0.4cm0.3mm     $TO$     $\bm{0.808}$     $TO$
lymph-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.852}$     $\bm{18}$
balance     $0.410$     $0.519$     $0.440$     $5.66$     $\bm{0.693}$     $69$     $\bm{0.693}$     $\bm{62}$
balance-o     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     0.4cm0.3mm     $\bm{0.661}$     $\bm{0.02}$

We compare  with the state of the art based on the following metrics: optimal convergence, execution time and number of iterations. Our implementation is available at <https://github.com/Chaoukia/branches.git>. The experimental setup is described in <ref>.

We employ 11 datasets from the UCI repository, which we chose because of their frequent use in benchmarking optimal Decision Tree algorithms. For each dataset, different types of encodings are considered: Suffix -l indicates a One-Hot Encoding where the last category of each feature is dropped, likewise -f indicates a One-Hot Encoding that rather drops the first category, while -o is for an Ordinal Encoding (which is the most faithful to the original dataset). We chose different encodings because they yield problems with varying degrees of difficulty. Moreover, the state of the art algorithms exclusively consider binary features, which necessitates a preliminary binary encoding. This seemingly benign detail can significantly harm performance by introducing unnecessary splits to the problem, we discuss this in depth in <ref>.  can sidestep this issue since it is directly applicable to an Ordinal Encoding of the data. We set a time limit of 5 minutes.

We compare  with OSDT, PyGOSDT and GOSDT in <ref> because these methods solve for sparsity. Nonetheless, we still include a comparison with DL8.5, MurTree and STreeD in <ref>. <ref> shows that  outperforms OSDT, PyGOSDT and GOSDT on almost all the experiments, with GOSDT being the most competitive method. On the monk datasets, while both GOSDT and  are always optimal,  is faster, sometimes significantly, especially when applied to the Ordinal Encoding. On the other hand, OSDT and PyGOSDT are only optimal for monk1-l, and they are prohibitively slow. There are a few datasets where  does not perform the best. On Mushroom, OSDT and PyGOSDT surprisingly outperform both  and GOSDT; on tic-tac-toe, car-eval and balance, GOSDT and  terminate but GOSDT is faster. However, we suspect that this is mainly due to GOSDT's optimised C++ implementation, which confers it an advantage over 's Python implementation. In fact, the impact of the difference between these programming languages is very evident from the large gap in execution times between GOSDT and PyGOSDT. We note however, that  always converges in fewer iterations than GOSDT, around 10 times less. This corroborates our complexity analysis of <ref>, and indicates that a future implementation of  in a low level programming language, such as C++, has immense potential, especially since it is amenable to true parallel computing. Indeed, the Algorithmic steps Selection, Expansion and Backpropagation can all be run through parallel synchronous threads. Unfortunately, Python is limited in its parallel computing capacity, it does not permit multithreading, and its multiprocessing module requires copying the data, which greatly slows down the algorithm and loses all the computational benefits of parallel computing.

The main take-away from <ref> is that DL8.5, MurTree and STreeD do not truly solve for sparsity. DL8.5 and MurTree maximise accuracy under constraints on maximum depth or maximum number of nodes but they do not minimise the number of nodes. STreeD, on the other hand, offers more flexibility in this regard, it supports the use of $\objectiver$, however <ref> shows its suboptimality in many cases even when it terminates, this never happens with  by virtue of <ref> nor does it happen with OSDT and GOSDT either. As a consequence, even when STreeD is optimal, as with monk1-l, monk2-f, zoo and balance, we cannot be sure whether STreeD proved optimality or terminated early while it happened to have already encountered the optimal solution.

§ CONCLUSION, LIMITATIONS AND FUTURE WORK

We introduced , a new DP and B&B algorithm for constructing optimal Decision Trees.  leverages the Purification bound in <ref> to prune the search space more effectively than state of the art algorithms. We analysed 's complexity and proved that our complexity bound is significantly smaller than those provided in the literature. This claim was further substantiated through our experiments, we showed that  always achieves optimal convergence in fewer iterations than GOSDT, leading to faster execution times in most cases. Moreover, unlike the state of the art,  is not limited to datasets with binary features, which yields substantial gain in performance compared to cases with binary encoded data.

For now  is limited to categorical features, we will generalise it to numerical features in the future. Furthermore,  is currently implemented in Python, which hinders its execution times sometimes compared to the C++ implementations. The large gap in performance between PyGOSDT and GOSDT motivates a future implementation of  in C++. Since  far outperforms the existing Python methods and is even competitive and often better than GOSDT, a future implementation of  in C++ is expected to be groundbreaking.

[1]
Aglin, G., Nijssen, S., and Schaus, P. (2020).
Learning optimal decision trees using caching branch-and-bound search.
In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3146–3153.

[2]
Avellaneda, F. (2020).
Efficient inference of optimal decision trees.
In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3195–3202.

[3]
Bennett, K. P. (1992).
Decision tree construction via linear programming.
Technical report, University of Wisconsin-Madison Department of Computer Sciences.

[4]
Bennett, K. P. (1994).
Global tree optimization: A non-greedy decision tree algorithm.
Computing Science and Statistics, pages 156–156.

[5]
Bennett, K. P. and Blue, J. A. (1996).
Optimal decision trees.
Rensselaer Polytechnic Institute Math Report, 214(24):128.

[6]
Bertsimas, D. and Dunn, J. (2017).
Optimal classification trees.
Machine Learning, 106:1039–1082.

[7]
Bessiere, C., Hebrard, E., and O’Sullivan, B. (2009).
Minimising decision tree size as combinatorial optimisation.
In International Conference on Principles and Practice of Constraint Programming, pages 173–187. Springer.

[8]
Blanquero, R., Carrizosa, E., Molero-Río, C., and Morales, D. R. (2021).
Optimal randomized classification trees.
Computers & Operations Research, 132:105281.

[9]
Breiman, L., Friedman, J., Stone, C. J., and Olshen, R. A. (1984).
Classification and regression trees.
CRC press.

[10]
Chaouki, A., Read, J., and Bifet, A. (2024).
Online learning of decision trees with Thompson sampling.
In Dasgupta, S., Mandt, S., and Li, Y., editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 2944–2952. PMLR.

[11]
Demirović, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., and Stuckey, P. J. (2022).
Murtree: Optimal decision trees via dynamic programming and search.
Journal of Machine Learning Research, 23(26):1–47.

[12]
Günlük, O., Kalagnanam, J., Li, M., Menickelly, M., and Scheinberg, K. (2021).
Optimal decision trees for categorical data via integer programming.
Journal of global optimization, 81:233–260.

[13]
Hu, X., Rudin, C., and Seltzer, M. (2019).
Optimal sparse decision trees.
Advances in Neural Information Processing Systems, 32.

[14]
Laurent, H. and Rivest, R. L. (1976).
Constructing optimal binary decision trees is NP-complete.
Information processing letters, 5(1):15–17.

[15]
Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. (2020).
Generalized and scalable optimal sparse decision trees.
In International Conference on Machine Learning, pages 6150–6160. PMLR.

[16]
McTavish, H., Zhong, C., Achermann, R., Karimalis, I., Chen, J., Rudin, C., and Seltzer, M. (2022).
Fast sparse decision tree optimization via reference ensembles.
In Proceedings of the AAAI conference on artificial intelligence, volume 36, pages 9604–9613.

[17]
Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva, J., and Ras, I. (2018).
Learning optimal decision trees with sat.
In Ijcai, pages 1362–1368.

[18]
Nijssen, S. and Fromont, E. (2007).
Mining optimal decision trees from itemset lattices.
In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 530–539.

[19]
Nijssen, S. and Fromont, E. (2010).
Optimal constraint-based decision tree induction from itemset lattices.
Data Mining and Knowledge Discovery, 21:9–51.

[20]
Norouzi, M., Collins, M., Johnson, M. A., Fleet, D. J., and Kohli, P. (2015).
Efficient non-greedy optimization of decision trees.
Advances in neural information processing systems, 28.

[21]
Quinlan, J. (2014).
C4. 5: programs for machine learning.

[22]
Quinlan, J. R. (1986).
Induction of decision trees.
Machine learning, 1(1):81–106.

[23]
Sutton, R. S. and Barto, A. G. (2018).
Reinforcement learning: An introduction.
MIT press.

[24]
van der Linden, J., de Weerdt, M., and Demirović, E. (2024).
Necessary and sufficient conditions for optimal decision trees using dynamic programming.
Advances in Neural Information Processing Systems, 36.

[25]
Verwer, S. and Zhang, Y. (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, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings 14, pages 94–103. Springer.

[26]
Verwer, S. and Zhang, Y. (2019).
Learning optimal classification trees using a binary linear program formulation.
In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 1625–1632.

[27]
Zhu, H., Murali, P., Phan, D., Nguyen, L., and Kalagnanam, J. (2020).
A scalable mip-based method for learning optimal multivariate decision trees.
Advances in neural information processing systems, 33:1771–1781.

§ TABLE OF NOTATION

Table of Notation

$X$     $=$     $\left( X^{\left( 1\right)}, \ldots, X^{\left( q\right)}\right)$, an input of features.

$X^{\left( i\right)}$     $\in$     $\{1, \ldots, C_i\}$, an feature.

$Y$     $\in$     $\{ 1, \ldots, K\}$, a class.

$\mathcal{D}$     $=$     $\{\left( X_m, Y_m\right)\}_{m=1}^n$, Dataset of examples.

$l$     $=$     $\bigwedge_{v=1}^{\splits\left( l\right)}\ind\Big\{ X^{\left( i_v\right)} = j_v\Big\}$ a branch. Also, a unit-state in our MDP.

$\splits\left( l\right)$     $\triangleq$     The size of branch $l$, the number of splits in $l$, the number of clauses in $l$.

$l\left( X\right)$     $\triangleq$     Valuation of $l$ for input $X$. When $l\left( X\right) = 1$, we say that $X$ is in $l$.

$\Omega$     $\triangleq$     The root. Branch that valuates to $1$ for all possible inputs.

$\children\left( l, i\right)$     $\triangleq$     Children of $l$ when splitting with respect to feature $i$.

$\children\left( l, i\right)$     $=$     $\{ l_1, \ldots, l_{C_i}\}$, $l_j = l \wedge \ind\Big\{ X^{\left( i\right)} = j\Big\}$

$n\left( l\right)$     $\triangleq$     Number of examples in $l$.

$n_k\left( l\right)$     $\triangleq$     Number of examples in $l$ of class $k$.

$k^*\left( l\right)$     $=$     $ \mathrm{Argmax}_{1 \le k \le K} \{ n_k\left( l\right)\}$, majority class in $l$

$\prob\left[ l\left( X\right) = 1\right]$     $\triangleq$     Empirical probability that $X$ is in $l$.

$\objective\left( l\right)$     $=$     $\prob\left[ l\left( X\right) = 1, Y = k^*\left( l\right)\right]$, probability that an example is in $l$ and is correctly classified.

sub-DT rooted in $l$     $\triangleq$     Collection of branches partitioning $l$. Also a state in our MDP.

DT     $\triangleq$     A sub-DT rooted in $\Omega$.

$T\left( X\right)$     $\triangleq$     Predicted class of $X$ by $T$. Majority class of the branch containing $X$.

$\objective\left( T\right)$     $=$     $\prob\left[ T\left( X\right) = Y\right]$, accuracy of DT $T$.

$\objectiver\left( T\right)$     $\triangleq$     Regularized Objective function of DT $T$.

$\objectiver\left( T\right)$     $=$     $\prob\left[ T\left( X\right) = Y\right] - \lambda\splits\left( T\right)$.

$\splits\left( T\right)$     $\triangleq$     Number of splits to construct $T$ from the branch it is rooted in.

$\lambda$     $\in$     $\left[ 0, 1\right]$, penalty parameter.

$T^*$     $=$     $\mathrm{Argmax}_T\{ \objectiver\left( T\right)\}$, optimal DT.

$\action\left( T\right)$     $\triangleq$     Action space at state $T$.

$\overline{a}$     $\triangleq$     Terminal action.

$T \overset{a}{\longrightarrow} T'$     $\triangleq$     Transition from $T$ to $T'$ through action $a$.

$\overline{l}$     $\triangleq$     Absorbing state, $l \overset{a}{\longrightarrow} \overline{l}$.

$r\left( T, a\right)$     $\triangleq$     Reward of taking action $a$ in state $T$.

$\pi$     $\triangleq$     Policy, maps each state $T$ to an action $\pi\left( T\right) \in \action\left( T\right)$.

$\rf^\pi\left( T\right)$     $\triangleq$     Return of policy $\pi$ from $T$. Cumulative reward of following $\pi$ from $T$.

$\qf^\pi\left( T, a\right)$     $\triangleq$     State-action return of policy $\pi$. Cumulative reward of taking action $a$ in state $T$ first, and then following $\pi$.

$T^\pi_l$     $\triangleq$     Sub-DT of $\pi$ rooted in $l$. See <ref>.

$T^\pi$     $\equiv$     $T^\pi_\Omega$

$\pi^*$     $=$     $\textrm{Argmax}_\pi\rf^\pi\left( \Omega\right)$, the optimal policy.

$T^*$     $=$     $T^{\pi^*}$

$\rf^*$     $\equiv$     $\rf^{\pi^*}$

$\qf^*$     $\equiv$     $\qf^{\pi^*}$

§ EXPERIMENTS AND IMPLEMENTATION DETAILS

§.§ Experimental setup

Number of examples $n$, number of features $q$, number of classes $K$ and penalty parameter $\lambda$ for the different datasets used in our experiments.

Dataset     $n$     $q$     $K$     $\lambda$
monk1-l     124     11     2     $0.01$
monk1-f     124     11     2     $0.001$
monk1-o     124     6     2     $0.01$
monk2-l     169     11     2     $0.001$
monk2-f     169     11     2     $0.001$
monk2-o     169     6     2     $0.001$
monk3-l     122     11     2     $0.001$
monk3-f     122     11     2     $0.001$
monk3-o     122     6     2     $0.001$
tic-tac-toe     958     18     2     $0.005$
tic-tac-toe-o     958     9     2     $0.005$
car-eval     1728     15     4     $0.005$
car-eval-o     1728     6     4     $0.005$
nursery     12960     19     5     $0.01$
nursery-o     12960     8     4     $0.01$
mushroom     8124     95     2     $0.01$
mushroom-o     8124     22     2     $0.01$
kr-vs-kp     3196     37     2     $0.01$
kr-vs-kp-o     3196     36     2     $0.01$
zoo     101     20     7     $0.001$
zoo-o     101     16     7     $0.001$
lymph     148     18     4     $0.01$
lymph-o     148     41     4     $0.01$
balance     576     16     2     $0.01$
balance-o     576     4     2     $0.01$

* All of the experiments were run on a personal Machine (2,6 GHz 6-Core Intel Core i7), they are easily reproducible.

* Code for DL8.5 <https://github.com/aia-uclouvain/pydl8.5.git>

* Code for MurTree <https://github.com/jurra/pymurtree.git>

* Code for STreeD <https://github.com/AlgTUDelft/pystreed.git>

* Code for OSDT <https://github.com/xiyanghu/OSDT.git>

* Code for PyGOSDT and GOSDT, we used <https://github.com/ubc-systopia/gosdt-guesses.git>. There is also the repository <https://github.com/Jimmy-Lin/GeneralizedOptimalSparseDecisionTrees.git>

* Code for  <https://github.com/Chaoukia/branches.git>

* OSDT and PyGOSDT are only applicable to binary classification problems, hence why we could not report their performances on multiclass classification datasets in <ref>.

* <ref> describes the details of each dataset and the penalty parameter values we used.

* All the experiments with DL8.5, MurTree and STreeD were conducted with maximum depth $6$ and maximum number of nodes $40$.

* On the experiments nursery, mushroom, kr-vs-kp and lymph, STreeD hits a timeout and it does not seem to propose a solution unless it terminates, hence why we could not report STreeD's results on these datasets.

§.§ Drawbacks of Binary Encoding

Optimal DT depicting the class variable that satisfies $Y=1$ if and only if $X^{\left( 1\right)} = 1$ or $X^{\left( 1\right)} = 3$ on the space $\mathcal{X} = \{1, 2, 3\}$.

<ref> and <ref> show that the optimal DT is always achieved significantly faster when we consider the Ordinal Encoding (Except for kr-vs-kp, this is because this dataset is already in binary form). Interestingly,  is the only method that can be directly applied with Ordinal Encoding, which makes it even more practical and broadly applicable than the state of the art. The central question of this section is: Why does Ordinal Encoding provide such great leaps in efficiency compared to Binary Encoding?

To answer this question, let us consider the following simple binary classification problem. Suppose there is only one feature $X^{\left( 1\right)}$ with $3$ categories, i.e. $\mathcal{X} = \{1, 2, 3\}$, and that the class $Y$ satisfies $Y=1$ if and only if $X^{\left( 1\right)} = 1$ or $X^{\left( 1\right)} = 3$. The optimal solution in this case consists of only one split, which is to split the root $\Omega$ with respect to feature $X^{\left( 1\right)}$, as shown in <ref>. In this setting,  only needs one iteration to terminate. Indeed, on its first iteration, it expands $\Omega$, estimates $\qf\left( \Omega, \overline{a}\right)$ and $\qf\left( \Omega, a\right)$ where $a$ is the split action with respect to $X^{\left( 1\right)}$. In this case,  can already deduce that:

\[
\qf^*\left( \Omega, a\right) = \qf\left( \Omega, a\right) = -\lambda + \underbrace{\prob\left[ \Omega\left( X\right) = 1\right]}_{=1} > \prob\left[ \Omega\left( X\right) = 1, k^*\left( \Omega\right) = Y\right] = \qf^*\left( \Omega, \overline{a}\right)
\]

and therefore that $\Omega$ is complete and $a = \mathrm{Argmax}_{a' \in \action\left( \Omega\right)}\qf^*\left( \Omega, a'\right)$.

Let us consider a Binary encoding of $\mathcal{X}$, this yields a new feature space $\mathcal{X}' = \{0, 1\}\times \{0, 1\} \times \{0, 1\}$ where features the new features $X'^{\left( 1\right)}, X'^{\left( 2\right)}, X'^{\left( 3\right)}$ express the existence of a category or the other:

\[
\forall{i \in \{ 1, 2, 3\}}: X'^{\left( i\right)} = \ind\{ X^{\left( 1\right)} = i\}
\]

<ref> depicts the new optimal Decision Tree on $\mathcal{X}'$. Now  cannot deduce this solution from the first iteration only, because the first iteration only explores branches of size $1$ and the optimal DT includes also branches of sizes 2 and 3. Moreover, Binary encoding introduces unnecessary branches that make the search space larger than it should, thereby wasting the search time. To see this, consider the branch:

\[
l' = \ind\{ X'^{\left( 1\right)} = 1\}\wedge \ind\{ X'^{\left( 2\right)} = 1\}
\]

This branch exists on $\mathcal{X}'$ and it could be explored at some point by the search algorithm. However, this would be a waste of time because $l'$ does not describe a possible subset of $\mathcal{X}$. Indeed, translating $l'$ to its corresponding branch on $\mathcal{X}$ yields:

\[
l = \ind\{ X^{\left( 1\right)} = 1\}\wedge \ind\{ X^{\left( 1\right)} = 2\}
\]

Which always valuates to $0$ for any datum $X \in \mathcal{X}$. As a consequence, $l$ can never be part of the optimal solution, in fact, it can never be part of any Decision Tree on $\mathcal{X}$, $l$ is not even a proper branch, it violates the condition in <ref>. Therefore exploring $l'$ while solving the DT optimisation on $\mathcal{X}'$ is a waste of time.

The Binary Encoding we considered in the last paragraph keeps all the categories of $X^{\left( 1\right)}$. In general, a more clever Binary Encoding is used based on the following:

\[
X'^{\left( 1\right)} = 0 \; \mathrm{and} \; X'^{\left( 2\right)} = 0 \iff X'^{\left( 3\right)} = 1
\]

This allows us to drop the last feature from $\mathcal{X}'$, yielding a smaller new feature space $\mathcal{X}' = \{ 0, 1\}\times \{ 0, 1\}$ where the features $X'^{\left( 1\right)}, X'^{\left( 2\right)}$ are the same as before. The new optimal solution is depicted in <ref> and it only includes two splits instead of three, unlike in the previous Binary Encoding, thus allowing the search to be more efficient but still less efficient than when operating on the original feature space $\mathcal{X}$. Moreover, the issue of unnecessary branches still holds here,
the branch $l' = \ind\{ X'^{\left( 1\right)} = 1\}\wedge \ind\{ X'^{\left( 2\right)} = 1\}$ is still present in this setting. The computational inefficiency induced by Binary Encoding can be evaluated by the number of these introduced unnecessary branches. <ref> provides this number for the case where all features have and equal number categories.

The new optimal Decision Tree on the full new feature space $\mathcal{X}'$.

Consider a classification problem where all features share the same number of categories $C$, i.e. $\mathcal{X} = \{ 1, \ldots, C\}^q$. Suppose we perform a Binary Encoding on $\mathcal{X}$ where the last category of each feature is dropped, this yields the new feature space $\mathcal{X}' = \{ 0, 1\}^{\left( C-1\right)^q}$. We define an unnecessary branch $l$ on $\mathcal{X}'$ as a branch that valuates to $0$ for any input vector $X \in \mathcal{X}$:

\[
\forall{X \in \mathcal{X}}: l\left( X\right) = 0
\]

Then the number of these unnecessary branches that Binary Encoding introduces is equal to:

\[
\mathcal{U}\left( q, C\right) = 3^{\left( C-1\right)q} - \left[ 2\left( C-1\right) + 1\right]^q
\]

The new optimal Decision Tree on the reduced new feature space $\mathcal{X}'$.

The number of unnecessary branches introduced by Binary Encoding.

There is a subtlety here. We define $l$ on $\mathcal{X}'$, which means that it involves clauses defined with the features of $\mathcal{X}'$, and yet the definition in <ref> pertains to valuating $l$ on inputs from the feature space $\mathcal{X}$. There is no mistake or lack of rigour in this definition, we are allowed to do this because the Binary Encoding is an injective map from $\mathcal{X}$ to $\mathcal{X}'$, thus implicitly, valuating $l$ on an input $X \in \mathcal{X}$ is defined as valuating $l$ on the image of $X$ in $\mathcal{X}'$ with this map.

<ref> draws the number of unnecessary branches, derived in <ref>, as a contour function of $q$ and $C$ in Logarithmic scale. It shows how immense this number becomes as $q$ and $C$ increase. We should note that, not all of these unnecessary branches, that Binary Encoding introduces, will be explored by , in fact most them will not be due to the algorithm's pruning capacity. Nevertheless, there are so many that they will inevitably hinder the search's efficiency as it is clearly demonstrated in <ref>. This inefficiency is most apparent on the mushroom dataset. All algorithms that solve for sparsity hit a timeout (after 5 minutes) when applied to the binary encoded version of the data. In contrast, when applied to the Ordinal Encoding of mushroom,  achieves an extremely fast optimal convergence in only $0.17s$ and $6$ iterations!

Optimal Decision Tree for monk1-l, it has $7$ splits.

Optimal Decision Tree for monk1-f, it has $17$ splits.

The introduction of unnecessary branches is not the only drawback of Binary Encoding. To perform Binary Encoding, we also have to decide which category to drop from each feature, however different choices lead to different feature spaces with different optimal Decision Trees. Furthermore, these different solutions do not necessarily share similar complexities, and these choices can lead to problems with vastly different levels of challenge. A pertinent example of this is the contrast between monk1-l and monk1-f. While all algorithms that solve for sparsity achieve optimal convergence for monk1-l, only GOSDT and  find the optimal solution for monk1-f. This is because monk1-l yields an optimal DT with $7$ splits only while monk1-f yields an optimal solution with $17$ splits, which is much more challenging to find. These optimal Decision Trees are depicted in <ref> and <ref>.

§.§ Memoisation

Our DP strategy relies on caching the estimates $\rf\left( l\right)$ for the encountered branches. Our caching scheme is similar to [1]. Each branch is uniquely identifies with its clauses regardless of their order. As such, we identify a branch $l = \bigwedge_{v=1}^{\splits\left( l\right)}\ind\Big\{ X^{\left( i_v\right)} = j_v\Big\}$ with the string $\left( i_1, j_1\right)\ldots\left( i_{\splits\left( l\right)}, j_{\splits\left( l\right)}\right)$, which is unique since $i_1 < \ldots < i_{\splits\left( l\right)}$. This caching is different from the one employed by [15] for GOSDT, where the authors rather identify branches with their support sets, i.e. each branch is identified with the indices of the data it contains. While this scheme could offer more pruning by identifying branches with different clauses as the same, there might be cases however, where it fails. Indeed, [15] claim that if two branches (in our terminology) share the same support set, then they identify the same subproblems. However, there are cases where this is not true, for instance, when these branches are of different depths, then one branch can be split more than the other, hence identifying a different subproblem. Our caching strategy favours caution, it avoids these sorts of misidentification issues.

§.§ Limitations

We have seen that  can sometimes be slower than GOSDT. This mostly happens when there are many features and relatively large datasets like tic-tac-toe and car-eval, as shown in <ref>. We suspect that this is due to 's Python implementation as all the Python methods struggle with this issue. Nevertheless,  always achieves optimality in fewer iterations than GOSDT, which is a promising sign.  can greatly benefit from true parallel computing. During Expansion, multiple splits and evaluations can be run in parallel. The Selection step can also run in parallel by following multiple paths through different branches at once. However, for Backpropagation, we have to be careful and perform it in a synchronous manner.

is also limited to categorical features. However, standard discretisation of numerical features could be used with  already. We have not tested this idea yet, we leave it for a future work.

Execution times of GOSDT and  for different values of $\lambda$.

Number of iterations of GOSDT and  for different values of $\lambda$.

§ PROOFS

For any policy $\pi$ and unit-state $l$, there exists $\tau \ge 0$ such that for any $t \ge \tau$, $T_t = \{ \overline{l_1}, \ldots, \overline{l_{|T_\tau|}}\}$ is an absorbing state. In which case we call $T_l^{\pi} = \{ l_1, \ldots, l_{|T_\tau|}\}$ the sub-DT of $\pi$ rooted in $l$. If $l=\Omega$ we abbreviate the notation $T_\Omega^{\pi} \equiv T^\pi$ and call $T^\pi$ the DT of $\pi$.

Let $l$ be a unit-state, $\pi$ a policy, and $\left( T_t\right)_{t=0}^{\infty}$ such that:

\begin{align*}
\begin{cases}
T_0 = l\\
\forall{t \ge 0}: T_t \overset{\pi\left( T_t\right)}{\longrightarrow} T_{t+1}
\end{cases}
\end{align*}

The proof is conducted by induction on $q - \splits\left( l\right) \in \{ 0, \ldots, q\}$, where we recall that $q$ is the number of features.

If $q - \splits\left( l\right) = 0$, then $\action\left( l\right) = \{ \overline{a}\}$ and $\pi\left( l\right) = \overline{a}$. Therefore $T_1 = \overline{l}$ and we deduce that the proposition holds with $\tau = 1$.

Inductive hypothesis: Suppose that the proposition is true for $q - \splits\left( l'\right) = n \in \{ 0, \ldots, q-1\}$, and let us show that it is true for $q - \splits\left( l\right) = n+1$.

If $\pi\left( l\right) = \overline{a}$, then $T_1 = \overline{l}$ and the proposition holds.

Otherwise $\pi\left( l\right)$ is a split action, and we have $l \overset{\pi\left( l\right)}{\longrightarrow} T_1 = \{ l_1, \ldots, l_{|T_1|}\}$ where:

\[
\forall{u \in \{ 1, \ldots, |T_1|\}}: q - \splits\left( l_u\right) = n
\]

Therefore, the proposition is true for all $l_u$.

Let us now denote the following:

\begin{align*}
\begin{cases}
T_1^{\left( u\right)} = l_u\\
\forall{t \ge 1}: T_t^{\left( u\right)} \overset{\pi}{\longrightarrow} T_{t+1}^{\left( u\right)}
\end{cases}
\end{align*}

According to the proposition:

\[
\exists{\tau_u \ge 0}, \forall{t \ge \tau_u}: T_t^{\left( u\right)} = \Big\{ \overline{l_1^{\left( u\right)}}, \ldots, \overline{l_{|T_{\tau_u}^{\left( u\right)}|}^{\left( u\right)}}\Big\}
\]

By taking $\tau = \max_{1 \le u \le |T_1|} \{ \tau_u\}$, we get:

\[
\forall{t \ge \tau}, \forall{u \in \{ 1, \ldots, |T_1|\}}: T_t^{\left( u\right)} = \Big\{ \overline{l_1^{\left( u\right)}}, \ldots, \overline{l_{|T_{\tau_j}^{\left( u\right)}|}^{\left( u\right)}}\Big\} = \Big\{ \overline{l_1^{\left( u\right)}}, \ldots, \overline{l_{|T_{\tau}^{\left( u\right)}|}^{\left( u\right)}}\Big\}
\]

On the other hand $ \forall{t \ge 1}: T_t = \bigcup_{u=1}^{|T_1|}T_t^{\left( u\right)}$, thus:

\[
\forall{t \ge \tau}: T_t = \bigcup_{u=1}^{|T_1|}\Big\{ \overline{l_1^{\left( j\right)}}, \ldots, \overline{l_{|T_{\tau}^{\left( u\right)}|}^{\left( u\right)}}\Big\}
\]

Which concludes the inductive proof.

For any policy $\pi$ and unit-state $l$, the return of $\pi$ from $l$ satisfies:

\[
\rf^\pi\left( l\right) = \objectiver\left( T_l^\pi\right) = -\lambda\splits\left( T_l^\pi\right) + \objective\left( T_l^\pi\right)
\]

In particular $\rf^\pi\left( \Omega\right) = \objectiver\left( T^\pi\right) = -\lambda\splits\left( T^\pi\right) + \objective\left( T^\pi\right)$.

Let $l$ be a unit-state, $\pi$ a policy, and $\left( T_t\right)_{t=0}^{\infty}$ such that:

\begin{align*}
\begin{cases}
T_0 = l\\
\forall{t \ge 0}: T_t \overset{\pi\left( T_t\right)}{\longrightarrow} T_{t+1}
\end{cases}
\end{align*}

By Induction on $\splits\left( T_l^\pi\right)$:

If $\splits\left( T_l^\pi\right) = 0$, then $\pi\left( l\right) = \overline{a}$ and $\forall{t \ge 1}: T_t = \overline{l}$. Thus:

\[
\rf^\pi\left( l\right) = \underbrace{r\left( l, \overline{l}\right)}_{=\objective\left( l\right)} + \sum_{t \ge 1}\underbrace{r\left( \overline{l}, \overline{l}\right)}_{=0} = \objective\left( l\right)
\]

On the other hand $T_l^\pi = l$, therefore:

\[
\objectiver\left( T_l^\pi\right) = -\lambda\underbrace{\splits\left( T_l^\pi\right)}_{=0} + \objective\left( l\right) = \objective\left( l\right)
\]

Hence $\rf^\pi\left( l\right) = \objectiver\left( T_l^\pi\right)$

Inductive hypothesis: Suppose the proposition is true up to $\splits\left( T_l^\pi\right) = n \ge 0$ and let us prove it for $\splits\left( T_l^\pi\right) = n+1$

If $\pi\left( l\right) = \overline{a}$ then we have again:

\[
\rf^\pi\left( l\right) = \underbrace{r\left( l, \overline{l}\right)}_{=\objective\left( l\right)} + \sum_{t \ge 1}\underbrace{r\left( \overline{l}, \overline{l}\right)}_{=0} = \objective\left( l\right)
\]

Since $T_l^\pi = l$, then:

\[
\objectiver\left( T_l^\pi\right) = -\lambda\underbrace{\splits\left( T_l^\pi\right)}_{=0} + \objective\left( l\right) = \objective\left( l\right)
\]

Hence $\rf^\pi\left( l\right) = \objectiver\left( T_l^\pi\right)$

Now suppose that $\pi\left( l\right)$ is a split action. We have the following:

\begin{align*}
\rf^\pi\left( l\right) &= r\left( l, \pi\left( l\right)\right) + \sum_{t=1}^\infty r\left( T_t, T_{t+1}\right)\\
&= r\left( l, \pi\left( l\right)\right) + \rf^\pi\left( T_1\right)\\
&= r\left( l, \pi\left( l\right)\right) + \sum_{u=1}^{|T_1|}\rf^\pi\left( l_u\right)
\end{align*}

Where $T_1 = \{ l_1, \ldots, l_{|T_1|}\}$. We know that:

\begin{align*}
\forall{u \in \{ 1, \ldots, |T_1|\}}: \rf^\pi\left( l_u\right) &= \objectiver\left( T_{l_u}^\pi\right)\\
\implies \rf^\pi\left( l\right) &= -\lambda + \sum_{u=1}^{|T_1|}\Big\{ -\lambda\splits\left( T_{l_u}^\pi\right) + \objective\left( T_{l_u}^\pi\right)\Big\}\\
&= -\lambda\Big\{ 1 + \sum_{u=1}^{|T_1|}\splits\left( l_u\right)\Big\} + \objective\left( T_l^\pi\right)
\end{align*}

We know that the total number of splits to construct $T_l^\pi$ is $1$ (corresponding to the split $\pi\left( l\right)$) plus the sum of the number of splits required to construct each sub-DT $T_{l_u}^\pi$, i.e.

\[
\splits\left( T_l^\pi\right) = 1 + \sum_{u=1}^{|T_1|}\splits\left( T_{l_u}^\pi\right)
\]

Therefore we deduce that:

\[
\rf^\pi\left( l\right) = -\lambda\splits\left( T_l^\pi\right) + \objective\left( T_l^\pi\right) = \objectiver\left( T_l^\pi\right)
\]

Which concludes the inductive proof.

Let $l$ be a non-terminal unit-state, $a \in \action\left( l\right) \setminus \{ \overline{a}\}$ a split action such that $l \overset{a}{\longrightarrow} T = \{ l_1, \ldots, l_{|T|}\}$. Then we have:

\begin{align}
\qf^*\left( l, a\right) &= -\lambda + \rf^*\left( T\right) =  -\lambda + \sum_{u=1}^{|T|}\rf^*\left( l_u\right)\nonumber \\
\forall{u \in \{ 1, \ldots, |T|\}}: \rf^*\left( l_u\right) &= \qf^*\left( l_u, \pi^*\left( l_u\right)\right) = \max_{a \in \action\left( l_u\right)}\qf^*\left( l_u, a\right) \nonumber
\end{align}

Let $l$ be a non-terminal unit-state, $a \in \action\left( l\right) \setminus \{ \overline{a}\}$ a split action and $\left( T_t\right)_{t=0}^{\infty}$ such that:

\begin{align*}
\begin{cases}
T_0 = l\\
l \overset{a}{\longrightarrow} T_1 = \{ l_1, \ldots, l_{|T_1|}\}\\
\forall{t \ge 1}: T_t \overset{\pi\left( T_t\right)}{\longrightarrow} T_{t+1}
\end{cases}
\end{align*}

Then we have:

\begin{align*}
\qf^\pi\left( l, a\right) &= \sum_{t=0}^\infty r\left( T_t, T_{t+1}\right) = r\left( l, a\right) + \rf^\pi\left( T\right) = -\lambda + \sum_{u=1}^{|T|}\rf^\pi\left( l_u\right)
\end{align*}

Therefore, for the special case of the optimal policy $\pi^*$, we have:

\[
\qf^*\left( l, a\right) = -\lambda + \rf^*\left( T\right) =  -\lambda + \sum_{u=1}^{|T|}\rf^*\left( l_u\right)
\]

We define:

\begin{align*}
\begin{cases}
T_1^{\left( u\right)} = l_u\\
\forall{t \ge 1}: T_t^{\left( u\right)} \overset{\pi}{\longrightarrow} T_{t+1}^{\left( u\right)}
\end{cases}
\end{align*}

We get:

\begin{align*}
\rf^\pi\left( l_u\right) &= \sum_{t=1}^\infty r\left( T_t^{\left( u\right)}, T_{t+1}^{\left( u\right)}\right) \\
&= r\left( T_1^{\left( u\right)},T_{2}^{\left( u\right)}\right) + \sum_{t=2}^\infty r\left( T_t^{\left( u\right)}, T_{t+1}^{\left( u\right)}\right)\\
&= r\left( T_1^{\left( u\right)},\pi\left( l_u\right)\right) + \sum_{t=2}^\infty r\left( T_t^{\left( u\right)}, T_{t+1}^{\left( u\right)}\right)\\
&= \qf^\pi\left( l_u, \pi\left( l_u\right)\right)
\end{align*}

This holds for $\pi^*$ as well, and we get:

\[
\rf^*\left( l_u\right) = \qf^*\left( l_u, \pi^*\left( l_u\right)\right)
\]

By definition, $\pi^*$ is the optimal policy, hence:

\begin{align*}
\forall{\pi}: \rf^\pi\left( l_u\right) &\le \rf^*\left( l_u\right)\\
\qf^\pi\left( l_u, \pi\left( l_u\right)\right) &\le \qf^*\left( l_u, \pi^*\left( l_u\right)\right)\\
\implies \forall{\pi, a \in \action\left( l_u\right)}: \qf^\pi\left( l_u, a\right) &\le \qf^*\left( l_u, \pi^*\left( l_u\right)\right)\\
\implies \forall{a \in \action\left( l_u\right)}: \qf^*\left( l_u, a\right) &\le \qf^*\left( l_u, \pi^*\left( l_u\right)\right)\\
\implies \qf^*\left( l_u, \pi^*\left( l_u\right)\right) &= \max_{a \in \action\left( l_u\right)}\qf^*\left( l_u, a\right)
\end{align*}

For any non-terminal unit-state $l$ and $a \in \action\left( l\right)\setminus \{ \overline{a}\}$ a split action, we define the Purification Bounds estimate:

\begin{align*}
\qf\left( l, a\right) &= -\lambda + \prob\left[ l\left( X\right) = 1\right] = -\lambda + \frac{n\left( l\right)}{n}\\
\rf\left( l\right) &= \max\{ \objective\left( l\right), -\lambda + \prob\left[ l\left( X\right) = 1\right]\}
\end{align*}

Then the estimates $\qf\left( l, a\right)$ and $\rf\left( l\right)$ are upper bounds on $\qf^*\left( l, a\right)$ and $\rf^*\left( l\right)$ respectively:

\begin{align*}
\qf\left( l, a\right) &\ge \qf^*\left( l, a\right)\\
\rf\left( l\right) &\ge \rf^*\left( l\right)
\end{align*}

Let $l$ be a non-terminal unit-state, $a\in \action\left( l\right)\setminus \{ \overline{a}\}$ and:

\[
\qf\left( l, a\right) = -\lambda + \prob\left[ l\left( X\right) = 1\right]
\]

Let us show that $\qf\left( l, a\right) \ge \qf^*\left( l, a\right)$. Consider $l \overset{\pi\left( l\right)}{\longrightarrow} T_1 = \{ l_1, \ldots, l_{|T_1|}\}$, we have the following:

\[
\qf^*\left( l, a\right) = -\lambda + \sum_{u=1}^{|T_1|}\rf^*\left( l_u\right)
\]

According to <ref>, we have:

\begin{align*}
\forall{u \in \{ 1, \ldots, |T_1|\}}: \rf^*\left( l_u\right) &= \objectiver\left( T_{l_u}^*\right)\\
\qf^*\left( l, a\right) &= - \lambda + \sum_{u=1}^{|T_1|}\objectiver\left( T_{l_u}^*\right)
\end{align*}

On the other hand, we have:

\begin{align*}
\forall{u \in \{ 1, \ldots, |T_1|\}}: \objectiver\left( T_{l_u}^*\right) &= -\lambda\splits\left( T_{l_u}^*\right) + \objective\left( T_{l_u}^*\right)\\
&\le \objective\left( T_{l_u}^*\right)\\
&\le \prob\left[ l_u\left( X\right) = 1, T_{l_u}^*\left( X\right) = Y\right]\\
&\le \prob\left[ l_u\left( X\right) = 1\right]
\end{align*}

Which implies the following:

\[
\qf^*\left( l, a\right) \le -\lambda + \sum_{u=1}^{|T_1|}\prob\left[ l_u\left( X\right) = 1\right] \le -\lambda + \prob\left[ l\left( X\right) = 1\right] = \qf\left( l, a\right)
\]

For the optimal value function, we have:

\begin{align*}
\rf^*\left( l\right) &= \max_{a \in \action\left( l\right)}\qf^*\left( l, a\right)\\
&= \max_{a \in \action\left( l\right)\setminus \{ \overline{a}\}}\Big\{ \qf^*\left( l, \overline{a}\right), \qf^*\left( l, a\right)\Big\}\\
&\le \max_{a \in \action\left( l\right)\setminus \{ \overline{a}\}}\Big\{ \objective\left( l\right), \qf\left( l, a\right)\Big\}\\
&\le \max\Big\{ \objective\left( l\right), -\lambda + \prob\left[ l\left( X\right) = 1\right]\Big\}
\end{align*}

For any unit-state $l$ and action $a \in \action\left( l\right)$, let $\qf\left( l, a\right)$ be the estimate defined in <ref>. Then these estimates are upper bounds on the optimal state values.

\[
\qf\left( l, a\right) \ge \qf^*\left( l, a\right)
\]

For the terminal action, we always have:

\[
\qf\left( l, \overline{a}\right) = \objective\left( l\right) = \qf^*\left( l, \overline{a}\right)
\]

Let us now consider a split action $a \in \action\left( l\right)\setminus \{ \overline{a}\}$. We have the following:

\[
\qf\left( l, a\right) = -\lambda + \sum_{u=1}^{|T_1|}\rf\left( l_u\right)
\]

Where $l \overset{a}{\longrightarrow} T_1 = \{ l_1, \ldots, l_{|T_1|}\}$. It suffices to show that:

\[
\forall{u \in \{ 1, \ldots, |T_1|\}}: \rf\left( l_u\right) \ge \rf^*\left( l_u\right)
\]

We define the following policy:

\[
\begin{cases}
\pi\left( l'\right) = \mathrm{Argmax}_{a' \in \action\left( l'\right)}\qf\left( l', a'\right)\; \textrm{for $l'$ that have been visited.}\\
\pi\left( l'\right) = \overline{a}\; \textrm{for $l$ that have never been visited.}
\end{cases}
\]

The proof now proceeds by induction on the number of visits of $l$ which we denote here $v\left( l\right) \ge 0$.

If $v\left( l\right) = 0$, then:

\[
\rf\left( l\right) = \max\big\{ \objective\left( l\right), -\lambda + \prob\left[ l\left( X\right) = 1\right]\big\} \ge \rf^*\left( l\right)
\]

Induction hypothesis: Suppose that this is true for any number of visits $\le n$ where $n \ge 0$, and let us show that the result still holds for $v\left( l\right) = n+1$. We have

\begin{align*}
\rf\left( l\right) = \max\{ \objective\left( l\right), -\lambda + \sum_{u=1}^{|T_1|}\rf\left( l_u\right)\}
\end{align*}

On the other hand

\begin{align*}
\forall{u \in \{ 1, \ldots, |T_1|\}}: v\left( l_u\right) &\le n\\
\implies \forall{u \in \{ 1, \ldots, |T_1|\}}: \rf\left( l_u\right) &\ge \rf^*\left( l_u\right)
\end{align*}

\[
\rf\left( l\right) \ge \max\{ \objective\left( l\right), -\lambda + \sum_{u=1}^{|T_1|}\rf^*\left( l_u\right)\} = \rf^*\left( l\right)
\]

Which concludes the inductive proof, and we get that:

\[
\forall{u \in \{ 1, \ldots, |T_1|\}}: \rf\left( l_u\right) \ge \rf^*\left( l_u\right)
\]

\[
\qf\left( l, a\right) = -\lambda + \sum_{u=1}^{|T_1|}\rf\left( l_u\right) \ge \qf^*\left( l, a\right)
\]

Remark: During the inductive reasoning, we used the fact that the number of visits of children branches is lower than the number of visits of their parent branch. However, this is not true when Dynamic Programming is considered. Indeed, due to memoisation, some children branches could have been visited more than their parents. The result still stems from a similar induction, albeit through a more technical proof. The general idea is that, for children branches $l_u$ that are visited more than $n+1$ times, we consider their children, and so on, until we arrive at descendant branches that are either visited less than $n$ times or that are terminal. In both cases $\rf\left( l_u\right) \ge \rf^*\left( l_u\right)$, and we backpropagate this result to $\rf\left( l\right)$.

When  terminates, its proposed policy solution $\Tilde{\pi}$ is optimal, i.e. $\Tilde{\pi} = \mathrm{Argmax}_\pi\rf^\pi\left( \Omega\right)$.

First, we show that for any unit-state $l$, if $l$ is complete and $a^* = \mathrm{Argmax}_{a \in \action\left( l\right)}\qf\left( l, a\right)$, then $a^* = \pi^*\left( l\right)$

Since $l$ is complete, we have $\qf\left( l, a^*\right) = \qf^*\left( l, a^*\right)$. By <ref>, we get

\begin{align*}
\forall{a \in \action\left( l\right)}: \qf^*\left( l, a^*\right) = \qf\left( l, a^*\right) \ge \qf\left( l, a\right) \ge \qf^*\left( l, a\right)\\
\implies a^* = \mathrm{Argmax}_{a \in \action\left( l\right)}\qf^*\left( l, a\right) = \pi^*\left( l\right)
\end{align*}

On the other hand, $l$ is complete if and only if $\left( l, \pi^*\left( l\right)\right)$ is complete, which is satisfied if and only if for all $u \in \{ 1, \ldots, |T|\}: l_u$ is complete, where $l \overset{\pi^*\left( l\right)}{\longrightarrow} T = \{ l_1, \ldots, l_{|T|}\}$.

terminates when $\Omega$ is complete. Let us define the following:

\[
\begin{cases}
T_0 = \Omega\\
\forall{t \ge 0}: T_t \overset{\Tilde{\pi}\left( T_t\right)}{\longrightarrow} T_{t+1}; \; T_t = \big\{ l^{\left( t\right)}_1, \ldots, l^{\left( t\right)}_{|T_t|}\big\}
\end{cases}
\]

Since $\Omega$ is complete, we have shown $\Tilde{\pi}\left( \Omega\right) = \pi^*\left( \Omega\right)$, and it follows that:

\begin{align*}
\forall{u \in \{ 1, \ldots, |T_1|\}}: &l_u^{\left( 1\right)} \; \textrm{is complete}\\
\implies \forall{u \in \{ 1, \ldots, |T_1|\}}: &\Tilde{\pi}\left( l_u^{\left( 1\right)}\right) = \pi^*\left( l_u^{\left( 1\right)}\right)\\
\implies \forall{u \in \{ 1, \ldots, |T_t|\}}: &l_u^{\left( t\right)} \; \textrm{is complete}\\
\implies \forall{u \in \{ 1, \ldots, |T_t|\}}: &\Tilde{\pi}\left( l_u^{\left( t\right)}\right) = \pi^*\left( l_u^{\left( t\right)}\right)\\
\end{align*}

Thus $\Tilde{\pi}$ is optimal:

\begin{align*}
\rf^*\left( \Omega\right) &= \sum_{t=0}^\infty r\left( T_t, \pi^*\left( T_t\right)\right)\\
&= \sum_{t=0}^\infty\sum_{u=1}^{|T_t|} r\left( l_u^{\left( t\right)}, \pi^*\left( l_u^{\left( t\right)}\right)\right)\\
&= \sum_{t=0}^\infty\sum_{u=1}^{|T_t|} r\left( l_u^{\left( t\right)}, \Tilde{\pi}\left( l_u^{\left( t\right)}\right)\right)\\
&= \sum_{t=0}^\infty r\left( T_t, \Tilde{\pi}\left( T_t\right)\right)\\
&= \rf^{\Tilde{\pi}}\left( \Omega\right)
\end{align*}

A branch $l$ can be chosen for Expansion only if there exists a DT $T$ such that:

\[
\begin{cases}
l \in T\setminus L\\
-\lambda\splits\left( T\right) + \sum_{l' \in L}\objective\left( l'\right) + \sum_{l' \in T\setminus L}\big\{ -\lambda + \prob\left[ l'\left( X\right) = 1\right]\big\} \ge -\lambda\splits\left( T^*\right) + \objective\left( T^*\right)
\end{cases}
\]

Where $L = \{ l' \in L: \objective\left( l'\right) \ge -\lambda + \prob\left[ l'\left( X\right) = 1\right]\}$.

Let $\Tilde{\pi}$ be the Selection policy, i.e. for any unit-state $l$:

\[ \Tilde{\pi}\left( l\right) =
\begin{cases}
\overline{a} \; \textrm{If $l$ has never been visited}\\
\mathrm{Argmax}_{a \in \action\left( l\right)}\qf\left( l, a\right) \; \textrm{Otherwise.}
\end{cases}
\]

For the current Selection policy $\Tilde{\pi}$, a branch $l$ is chosen for Expansion only if $l \in T^{\Tilde{\pi}}$, thus let us analyse the properties of $T^{\Tilde{\pi}}$.

By the definition of $\Tilde{\pi}$, $T^{\Tilde{\pi}}$ maximising $\rf\left( T\right)$:

\begin{align*}
\forall{\, \textrm{DT} \; T}: \rf\left( T\right) &\le \rf\left( T^{\Tilde{\pi}}\right)\\
\implies \rf\left( T^*\right) &\le \rf\left( T^{\Tilde{\pi}}\right)\\
\implies \rf^*\left( T^*\right) &\le \rf\left( T^{\Tilde{\pi}}\right)\\
\implies -\lambda\splits\left( T^*\right) + \objective\left( T^*\right) &\le \rf\left( T^{\Tilde{\pi}}\right)\\
\end{align*}

On the other hand we have:

\begin{align*}
\rf\left( T^{\Tilde{\pi}}\right) = \sum_{l \in T^{\Tilde{\pi}}}\rf\left( l\right)
\end{align*}

Let $L = \{ l \in L: \objective\left( l\right) \ge -\lambda + \prob\left[ l\left( X\right) = 1\right]\}$. For any $l \in L$ we have $\rf\left( l\right) = \objective\left( l\right)$ and for any $l \in T \setminus L$ we have $\rf\left( l\right) = -\lambda + \prob\left[ l\left( X\right) = 1\right]$. Therefore we deduce that:

\[
-\lambda\splits\left( T^{\Tilde{\pi}}\right) + \sum_{l' \in L}\objective\left( l'\right) + \sum_{l' \in T^{\Tilde{\pi}}\setminus L}\big\{ -\lambda + \prob\left[ l'\left( X\right) = 1\right]\big\} \ge -\lambda\splits\left( T^*\right) + \objective\left( T^*\right)
\]

The first condition for a branch $l$ to be considered for Expansion is $l \in T^{\Tilde{\pi}}$. For the second condition, $l$ cannot be in $L$, because all branches in $L$ are complete and satisfy $\overline{a} = \mathrm{Argmax}_{a \in \action\left( l\right)}\qf^*\left( l, a\right)$. Indeed this is due to the following:

\[
\qf^*\left( l, \overline{a}\right) = \objective\left( l\right) \ge -\lambda + \prob\left[ l\left( X\right) = 1\right] \ge \qf^*\left( l, a\right) \; \forall{a \in \action\left( l\right)}
\]

where the last inequality comes from <ref>. Now we deduce that the second condition for $l$ to be considered for Expansion is $l \in T \setminus L$.

Let $\Gamma\left( q, C, \lambda\right)$ denote the total number of branch evaluations performed by  for an instance of the classification problem with $q \ge 2$ features, $0 < \lambda \le 1$ the penalty parameter, and $C \ge 2$ the number of categories of each feature, i.e.

\[
\forall{i \in \{ 1, \ldots, q\}}: C_i = C
\]

Then, given $T^*$ the optimal DT, $\Gamma\left( q, C, \lambda\right)$ is bounded by the following:

\[
\Gamma\left( q, C, \lambda\right) \le \sum_{h = 0}^\kappa \left( q - h\right)C^{h+1}\binom{q}{h}; \; \kappa = \min\Bigg\{ \floor*{\splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}}, \frac{C^q - 1}{C-1} \Bigg\}
\]

Let $l$ be a branch. According to <ref>, for $l$ to be considered for Expansion, there has to exist a DT $T$ such that:

\[
\begin{cases}
l \in T\setminus L\\
-\lambda\splits\left( T\right) + \sum_{l' \in L}\objective\left( l'\right) + \sum_{l' \in T\setminus L}\big\{ -\lambda + \prob\left[ l'\left( X\right) = 1\right]\big\} \ge -\lambda\splits\left( T^*\right) + \objective\left( T^*\right)
\end{cases}
\]

Where $L = \{ l' \in L: \objective\left( l'\right) \ge -\lambda + \prob\left[ l'\left( X\right) = 1\right]\}$. Suppose $l$ is such a branch, then we have:

\begin{align*}
-\lambda\splits\left( T\right) + \sum_{l' \in L}\underbrace{\objective\left( l'\right)}_{\le \prob\left[ l'\left( X\right) = 1\right]} + \sum_{l' \in T\setminus L}\big\{ -\lambda + \prob\left[ l'\left( X\right) = 1\right]\big\} &\ge -\lambda\splits\left( T^*\right) + \objective\left( T^*\right)\\
\implies -\lambda\Big\{ \splits\left( T\right) + |T \setminus L|\Big\} + \sum_{l' \in T}\prob\left[ l'\left( X\right)=1\right] &\ge -\lambda\splits\left( T^*\right) + \objective\left( T^*\right)
\end{align*}

Since $l \in T \setminus L$, then $|T \setminus L| \ge 1$ and we get:

\begin{align*}
-\lambda\Big\{ \splits\left( T\right) + 1\Big\} + 1 &\ge -\lambda\splits\left( T^*\right) + \objective\left( T^*\right)\\
\implies \splits\left( T\right) &\le \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}\\
\implies \splits\left( l\right) &\le \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}
\end{align*}

Let $\mathcal{C} = \Big\{ l \; \textrm{branch}: \splits\left( l\right) \le \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}\Big\}$. Then the number of branches that are expanded is upper bounded by $|\mathcal{C}|$.

We recall that we rather seek to upper bound the number of branches that are evaluated, i.e. for which we calculate $\objective\left( l\right)$. These evaluations happen during the Expansion step of . When a branch $l$ is expanded, we evaluate all of its children. There are $q-\splits\left( l\right)$ features left to use for splitting $l$, and for each split, $C$ children branches are created. Thus, there $\left( q-\splits\left( l\right)\right)*C$ children of $l$, hence $\left( q-\splits\left( l\right)\right)*C$ evaluations during the expansion of $l$. Let us now upper bound $\Gamma\left( q, C, \lambda\right)$.

For each branch $l \in \mathcal{C}$:

* We choose $\splits\left( l\right) \in \Big\{ 0, \ldots, \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}\Big\}$

* For each $h = \splits\left( l\right)$, we construct $l$ by choosing $h$ features among the total $q$ features, there are $\binom{q}{h}$ such choices.

* For each choice among the $\binom{q}{h}$ choices, for each feature among the $h$ features, there are $C$ choices of values, therefore there are $C^h\binom{q}{h}$ branches with depth $h$.

* For each branch of depth $h$, when it is expanded, $\left( q-h\right)C$ evaluations occur.

With these considerations, we deduce that:

\[
\Gamma\left( q, C, \lambda\right) \le \sum_{h = 0}^\kappa \left( q - h\right)C^{h+1}\binom{q}{h}; \; \kappa = \floor*{\splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}}
\]

On the other hand, the maximum number of splits any branch can have is $\frac{C^q - 1}{C-1}$, we prove it next.

Let $f\left( n\right)$ be the number of branches in a DT with $n$ splits. A DT with no split has only one branch, thus $f\left( 0\right) = 1$. On the other hand, when splitting a branch in a DT with $n$ splits, the resulting DT has $n+1$ splits, $C$ additional branches and one less (the branch that has been split). Thus $f\left( n+1\right) = f\left( n\right) - 1 + C$, which leads to:

\begin{align*}
f\left( n\right) - f\left( 0\right) &= \sum_{k=1}^n \Big\{ f\left( k\right) - f\left( k - 1\right)\Big\} = n\left( C - 1\right)\\
\implies f\left( n\right) &= n\left( C-1\right) + 1\\
\implies n &= \frac{f\left( n\right) - 1}{C-1}
\end{align*}

We know that the maximum number of branches that a DT could have is $C^q$, therefore the maximum number of splits possible is $\frac{C^q - 1}{C - 1}$, no branch can have more splits than this limit. We deduce that:

\[
\Gamma\left( q, C, \lambda\right) \le \sum_{h = 0}^\kappa \left( q - h\right)C^{h+1}\binom{q}{h}; \; \kappa = \min\Bigg\{ \floor*{\splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}}, \frac{C^q - 1}{C-1} \Bigg\}
\]

Let $\Gamma\left( q, \lambda, C\right)$ be defined as in <ref>, then we have:

\[
\Gamma\left( q, C, \lambda\right) \le \sum_{h = 0}^\kappa \left( q-h\right)C^{h+1}\binom{q}{h}; \; \kappa = \min\Bigg\{ \floor*{\frac{K-1}{K\lambda}}-1, \frac{C^q - 1}{C-1} \Bigg\}
\]

To make the bound problem-independent, let us upper bound $\kappa$ and make it independent of $T^*$. We know that:

\begin{align*}
\objectiver\left( T^*\right) = -\lambda\splits\left( T^*\right) + \objective\left( T^*\right) &\ge \objectiver\left( \Omega\right) = \objective\left( \Omega\right) = \prob\left[ Y = k^*\left( \Omega\right)\right] \ge \frac{1}{K}\\
\implies \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda} &\le \frac{K-1}{K\lambda} - 1
\end{align*}

Which concludes the proof.

Let $\Gamma\left( q, \lambda, C\right)$ be defined as in <ref>, then we have:

\begin{align*}
\Gamma\left( q, C, \lambda\right) &\le \sum_{h = 0}^{\kappa_-} \left( q - h\right)C^{h+1}\binom{q}{h} + \sum_{h=\kappa_- + 1}^\kappa \left( q - h\right)\left( h - \kappa_-\right)C^h\binom{q}{h}\\
\kappa_- &= \min\Bigg\{ \splits\left( T^*\right) - C + \floor*{\frac{1 - \objective\left( T^*\right)}{\lambda}}, \frac{C^q - 1}{C-1}\Bigg\}\\
\kappa &= \min\Bigg\{ \splits\left( T^*\right) - 1 + \floor*{\frac{1 - \objective\left( T^*\right)}{\lambda}}, \frac{C^q - 1}{C-1}\Bigg\}
\end{align*}

Let $\Tilde{\pi}$ be the Selection policy, i.e. for any unit-state $l$:

\[ \Tilde{\pi}\left( l\right) =
\begin{cases}
\overline{a} \; \textrm{If $l$ has never been visited}\\
\mathrm{Argmax}_{a \in \action\left( l\right)}\qf\left( l, a\right) \; \textrm{Otherwise.}
\end{cases}
\]

As we saw in the proof of <ref>, a branch $l$ can only be considered for Expansion if $l \in T^{\Tilde{\pi}}$. Let us denote $T^{\Tilde{\pi}} = \{ l_1, \ldots, l_{T^{\Tilde{\pi}}}\}$ in the order that these branches are considered for Expansion. From <ref> and the proof of <ref>, $l_1$ can only be considered for Expansion if:

\[
\splits\left( T^{\Tilde{\pi}}\right) \le \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}
\]

However, since $l_2$ can only be considered for Expansion after $l_1$, the condition becomes tighter for $l_2$:

\[
\splits\left( T^{\Tilde{\pi}}\right) \le \splits\left( T^*\right) - 2 + \frac{1 - \objective\left( T^*\right)}{\lambda}
\]

And so on, $l_{|T^{\Tilde{\pi}}|}$ can only be expanded if:

\[
\splits\left( T^{\Tilde{\pi}}\right) \le \splits\left( T^*\right) - |T^{\Tilde{\pi}}| + \frac{1 - \objective\left( T^*\right)}{\lambda}
\]

In the proof of <ref>, we counted all branches of depth $\splits\left( l\right) = \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}$ as potential candidates for Expansion, however, here we will show that this number is much lower. Indeed, consider a branch $l$ with:

\[
\splits\left( l\right) = \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}
\]

For $l$ to be considered for Expansion, there has to be a DT $T$ satisfying:

\[
\splits\left( T\right) \le \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}
\]

Since $l \in T$ then $\splits\left( l\right) \le \splits\left( T\right)$, and thus:

\[
\splits\left( T\right) = \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}
\]

\[
\splits\left( T\right) > \splits\left( T^*\right) - 2 + \frac{1 - \objective\left( T^*\right)}{\lambda}
\]

There can only be one branch that is expanded in $T$. Therefore, if $l$ is expanded, non of its sibling branches (i.e. branches that differ from $l$ by only one clause) can be expanded. This reduces the number of such branches $l$ that can be considered for Expansion to one branch from each siblings set. Let us now count these branches of depth $h = \splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}$ fulfilling these conditions:

* There are $\binom{q}{h}$ choices for the features.

* For the first $h-1$ chosen features, there are $C$ choices of values, but the last one can only take one value, otherwise a sibling branch will also be counted.

* Each Expansion incurs $q - h$ branch evaluations.

In fact, these new considerations are valid for all depths $h > \splits\left( T^*\right) - C + \frac{1 - \objective\left( T^*\right)}{\lambda}$, let us generalise:

* There are $\binom{q}{h}$ choices for the features.

* The first $h-1$ features can take $C$ values, the last one can only take $k = h - \splits\left( T^*\right) + C - \floor*{\splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda}}$ values.

* Each Expansion incurs $q - h$ branches

As for branches with depths $h \le \splits\left( T^*\right) - C + \frac{1 - \objective\left( T^*\right)}{\lambda}$, the count stays the same as in <ref>. Thus we deduce that:

\begin{align*}
\Gamma\left( q, C, \lambda\right) &\le \sum_{h = 0}^{\kappa_-} \left( q - h\right)C^{h+1}\binom{q}{h} + \sum_{h=\kappa_- + 1}^\kappa \left( q - h\right)\left( h - \kappa_-\right)C^h\binom{q}{h}\\
\kappa_- &= \min\Bigg\{ \splits\left( T^*\right) - C + \floor*{\frac{1 - \objective\left( T^*\right)}{\lambda}}, \frac{C^q - 1}{C-1}\Bigg\}\\
\kappa &= \min\Bigg\{ \splits\left( T^*\right) - 1 + \floor*{\frac{1 - \objective\left( T^*\right)}{\lambda}}, \frac{C^q - 1}{C-1}\Bigg\}
\end{align*}

Let $\Gamma\left( q, \lambda, C\right)$ be defined as in <ref>, then we have:

\begin{align*}
\Gamma\left( q, C, \lambda\right) &\le \sum_{h = 0}^{\kappa_-} \left( q - h\right)C^{h+1}\binom{q}{h} + \sum_{h=\kappa_- + 1}^\kappa \left( q - h\right)\left( h - \floor*{\frac{K-1}{K\lambda}} + C\right)C^h\binom{q}{h}\\
\kappa_- &= \min\Bigg\{ \floor*{\frac{K-1}{K\lambda}} - C, \frac{C^q - 1}{C-1}\Bigg\}\\
\kappa &= \min\Bigg\{ \floor*{\frac{K-1}{K\lambda}} - 1, \frac{C^q - 1}{C-1}\Bigg\}
\end{align*}

The Corollary follows immediately in similar fashion to <ref> by using:

\[
\splits\left( T^*\right) - 1 + \frac{1 - \objective\left( T^*\right)}{\lambda} \le \frac{K-1}{K\lambda} - 1
\]

In <cit.>, the authors derive an upper bound on the number of DT evaluations performed by OSDT. However, in the sum $\sum_{k=1}^K N_k$, $K$ is set to be the maximum number of leaves that $T^*$ could have while it should its maximum depth, because in their proof, the authors reason with the terms $N_k$ that are the number of all possible DTs of depth $k$. Therefore $K$ should rather be:

\[
K = \min\Bigg\{\floor*{\frac{1}{2\lambda}}, M \Bigg\}
\]

Consider a classification problem where all features share the same number of categories $C$, i.e. $\mathcal{X} = \{ 1, \ldots, C\}^q$. Suppose we perform a Binary Encoding on $\mathcal{X}$ where the last category of each feature is dropped, this yields the new feature space $\mathcal{X}' = \{ 0, 1\}^{\left( C-1\right)^q}$. We define an unnecessary branch $l$ on $\mathcal{X}'$ as a branch that valuates to $0$ for any input vector $X \in \mathcal{X}$:

\[
\forall{X \in \mathcal{X}}: l\left( X\right) = 0
\]

Then the number of these unnecessary branches that Binary Encoding introduces is equal to:

\[
\mathcal{U}\left( q, C\right) = 3^{\left( C-1\right)q} - \left[ 2\left( C-1\right) + 1\right]^q
\]

The proof of this Theorem proceeds by counting the total number of branches possible on $\mathcal{X}'$ and subtracting the total number of branches that are not unnecessary.

Let us start with the total number of branches on $\mathcal{X}'$. Any branch on $\mathcal{X}'$ has the form:

\[
l = \bigwedge_{v=1}^w \ind\{ X'^{\left( i_v\right)} = z_v\}
\]

Where $X'^{\left( i_v\right)}$ are the features on the space $\mathcal{X}'$, $w \in \{ 0, \ldots, \left( C-1\right)q\}, i_v \in \{ 1, \ldots, \left( C-1\right)q\}, z_v \in \{ 0, 1\}$. We note that $w=0$ corresponds to $l = \Omega$ by definition.

* There $\left( C-1\right)q$ possibilities for choosing $w$.

* For each possible value $w$, there are $\binom{\left( C-1\right)q}{w}$ possible combinations $\{ i_1, \ldots, i_w\}$.

* For each combination $\{ i_1, \ldots, i_w\}$, there are $2^w$ possible assignments $\left( z_1, \ldots, z_w\right)$

Therefore the total number of branches on $\mathcal{X}'$ is:

\begin{equation}
\label{eq:total-branches}
\mathcal{A}\left( q, C\right) = \sum_{w=0}^{\left( C-1\right)q}\binom{\left( C-1\right)q}{w}2^w = 3^{\left( C-1\right)q}
\end{equation}

Let us now count the number of non-unnecessary branches. To do this, we consider a slightly different notation of the features on $\mathcal{X}'$.

\[
\forall{i \in \{ 1, \ldots, q\}}, \forall{j \in \{ 1, \ldots, C - 1\}}: X'^{\left( i, j\right)} = \ind\{ X^{\left( i\right)} = j\}
\]

A branch $l = \bigwedge_{v=1}^w \ind\{ X'^{\left( i_v, j_v\right)} = z_v\}$ is not unnecessary if and only if $w \in \{ 0, \ldots, q\}, i_v \in \{ 1, \ldots, q\}, j_v \in \{ 1, \ldots, C-1\}, z_v \in \{ 0, 1\}$.

* For each possibility value $w \in \{ 1, \ldots, q\}$, there are $\binom{q}{w}$ possible combinations $\{ i_1, \ldots, i_w\}$.

* For each combination $\{ i_1, \ldots, i_w\}$, there are $\left( C-1\right)^w$ possible assignments $\left( j_1, \ldots, j_w\right)$.

* For each assignment $\left( j_1, \ldots, j_w\right)$, there are $2^w$ possible assignments $\left( z_1, \ldots, z_w\right)$.

The total number of branches that are not unnecessary is therefore:

\begin{equation}
\label{eq:total-branches-non-unnecessary}
\mathcal{B}\left( q, C\right) = \sum_{w=0}^q \binom{q}{w}2^w \left( C-1\right)^w = \left[ 2\left( C-1\right) + 1\right]^q
\end{equation}

From <ref> and <ref> we deduce that the total number of unnecessary branches is:

\[
\mathcal{U}\left( q, C\right) = \mathcal{A}\left( q, C\right) - \mathcal{B}\left( q, C\right) = 3^{\left( C-1\right)q} - \left[ 2\left( C-1\right) + 1\right]^q
\]

[1]
Input: Dataset $\mathcal{D}=\{\left( X_m, Y_m\right)\}_{m=1}^n$, penalty parameter $\lambda \ge 0$.
$\mathrm{memo} \gets \{ \}$ Initialise an empty memo
$\Call{Initialise}{\Omega, \mathcal{D}}$
not $\Omega.\mathrm{complete}$
$\left( l, \mathrm{path}\right) \gets \Call{Select}{\null}$
$\Call{Expand}{l, \mathcal{D}}$
$l \gets \Omega$
$\mathrm{path} \gets \left[ l\right]$
$l.\mathrm{expanded}$ and (not $l.\mathrm{complete}$)
$\left( \qf\left( l, i\right), \mathrm{return\_complete}, i, \mathrm{children\_incomplete}\right) \gets l.\mathrm{queue}[0]$
$l \gets \mathrm{children\_incomplete}\left[ 0\right]$
$\mathrm{path}.\mathrm{append}\left( l\right)$
$\left( l, \mathrm{path}\right)$
Expand$l, \mathcal{D}$
$l.\mathrm{expanded} \gets True$
$i \in \action\left( l\right)\setminus \{ \overline{a}\}$
$\Call{Split}{l, i, \mathcal{D}}$
$\rf\left( l\right) \gets \max\big\{ \qf\left( l, \overline{a}\right), l.\mathrm{queue}\left[ 0\right][0]\big\}$ This update comes from <ref>
$\rf\left( l\right) = \qf\left( l, \overline{a}\right)$ In this case $\rf^*\left( l\right) = \qf^*\left( l, \overline{a}\right) = \objective\left( l\right)$
$l.\mathrm{complete} \gets True$ $\rf^*\left( l\right)$ is known
$l.\mathrm{terminal} \gets True$ Label $l$ terminal if the optimal action at $l$ is $\pi^*\left( l\right) = \overline{a}$
$N \gets \mathrm{length}\left( \mathrm{path}\right)$
$t = N - 2$ to $0$
$l \gets \mathrm{path}\left[ t\right]$
$\left( \qf\left( l, i\right), \mathrm{return\_complete}, i, \mathrm{children\_incomplete}\right) \gets l.\mathrm{queue}.\mathrm{pop}\left( \right)$
$\qf\left( l, i\right) \gets \mathrm{return\_complete}$ Initialise $\qf\left( l, i\right)$
$l' \in \mathrm{children\_incomplete}$
$\qf\left( l, i\right) \gets \qf\left( l, i\right) + \rf\left( l'\right)$
$l'.\mathrm{complete}$ Check if $l'$ is complete now
$\mathrm{children\_incomplete}.\mathrm{discard}\left( l'\right)$ Delete $l'$ from $\mathrm{children\_incomplete}$
$l.\mathrm{queue}.\mathrm{push}\left( \left( \qf\left( l, i\right), \mathrm{return\_complete}, i, \mathrm{children\_incomplete}\right)\right)$
$\left( \qf\left( l, i^*\right), \mathrm{return\_complete}, i^*, \mathrm{children\_incomplete}\right) \gets l.\mathrm{queue}\left[ 0\right]\left[ 0\right]$
$\rf\left( l\right) \gets \qf\left( l, i^*\right)$
($\rf\left( l\right) = \qf\left( l, \overline{a}\right)$) or ($\mathrm{children\_incomplete}$ is empty)
$l.\mathrm{complete} \gets True$
$l.\mathrm{terminal} \gets True$ Label $l$ terminal if the optimal action at $l$ is $\pi^*\left( l\right) = \overline{a}$

[1]

Initialise$l, \mathcal{D}$
$l.\mathrm{expanded} \gets False$ Label $l$ as not expanded yet
$l.\mathrm{children} \gets \mathrm{dict}\left( \right)$ Initialise the dictionary of children
$l.\mathrm{queue} \gets \mathrm{queue}\left( \left[ \right]\right)$ Initialise the priority queue of $l$
$\qf\left( l, \overline{a}\right) \gets \objective\left( l\right)$ $\objective\left( l\right)$ is calculated with $\mathcal{D}$
$\action\left( l\right) = \{ \overline{a}\}$
$l.\mathrm{terminal} \gets True$ Label $l$ as terminal if it cannot be split
$l.\mathrm{complete} \gets True$ $\rf^*\left( l\right)$ is known
$\rf\left( l\right) \gets \qf\left( l, \overline{a}\right)$ In this case $\rf^*\left( l\right) = \qf^*\left( l, \overline{a}\right) = \objective\left( l\right)$
$l.\mathrm{terminal} \gets False$
Initialise $\rf\left( l\right)$ according to <ref> and <ref>
$\rf\left( l\right) = \qf\left( l, \overline{a}\right)$
$l.\mathrm{complete} \gets True$ $\rf^*\left( l\right)$ is known, $\rf^*\left( l\right) = \qf^*\left( l, \overline{a}\right) = \objective\left( l\right)$
$l.\mathrm{terminal} \gets True$ Label $l$ terminal if the optimal action at $l$ is $\pi^*\left( l\right) = \overline{a}$
$l.\mathrm{complete} \gets False$ $\rf^*\left( l\right)$ is still unknown
$\mathrm{memo}.\mathrm{add}(l)$ Add the initialised branch to the memo
Split$l, i, \mathcal{D}$
$l.\mathrm{children}[i] \gets \left[ \right]$ Initialise the list of children that stem taking split action $i$ in $l$
$\qf\left( l, i\right) \gets -\lambda$ Initialise the Upper Bound $\qf\left( l, i\right)$
$\mathrm{return\_complete} \gets -\lambda$ Initialise the return due to complete children
$\mathrm{children\_incomplete} \gets \left[ \right]$ Initialise the list of incomplete children
$j \in \{ 1, \ldots, C_i\}$
$l_{ij} \gets l \wedge \ind\{ X^{\left( i\right)} = j\}$
$l_{ij} \notin \mathrm{memo}$ Only initialise the branches that are not in the memo
$\Call{Initialise}{l_{ij}, \mathcal{D}}$
$l.\mathrm{children}[i].\mathrm{append}\left( l_{ij}\right)$
$\qf\left( l, i\right) \gets \qf\left( l, i\right) + \rf\left( l_{ij}\right)$ Update the Upper Bound $\qf\left( l, i\right)$
$\mathrm{return\_complete} \gets \mathrm{return\_complete} + \rf\left( l_{ij}\right)$
$\mathrm{children\_incomplete}.\mathrm{append}\left( l_{ij}\right)$
$l.\mathrm{queue}.\mathrm{push}\left( \left( \qf\left( l, i\right), \mathrm{return\_complete}, i, \mathrm{children\_incomplete}\right)\right)$
$T \gets \left[ \right]$
$Q \gets \mathrm{queue}\left( \right)$
$Q.\mathrm{put}\left( \Omega\right)$
$Q$ is not empty
$l \gets Q.\mathrm{pop}\left( \right)$
$T.\mathrm{append}\left( l\right)$
$\left( \qf\left( l, i\right), \mathrm{return\_complete}, i, \mathrm{children\_incomplete}\right) \gets l.\mathrm{queue}[0]$
$l' \in l.\mathrm{children}\left[ i\right]$
$Q.\mathrm{put}\left( l'\right)$