Learning Tree-Based Models with Gradient Descent

Sascha Marton

cs.LGMar 11, 2026

Learning Tree-Based Models with Gradient Descent

Authors: Sascha Marton

Organizations: UNIVERSITY OF MANNHEIM

Abstract

Tree-based models are widely recognized for their interpretability and have proven effective in various application domains, particularly in high-stakes domains. However, learning decision trees (DTs) poses a significant challenge due to their combinatorial complexity and discrete, non-differentiable nature. As a result, traditional methods such as CART, which rely on greedy search procedures, remain the most widely used approaches. These methods make locally optimal decisions at each node, constraining the search space and often leading to suboptimal tree structures. Additionally, their demand for custom training methods precludes a seamless integration into modern machine learning (ML) approaches. In this thesis, we propose a novel method for learning hard, axis-aligned DTs through gradient descent. Our approach utilizes backpropagation with a straight-through operator on a dense DT representation, enabling the joint optimization of all tree parameters, thereby addressing the two primary limitations of traditional DT algorithms. First, gradient-based training is not constrained by the sequential selection of locally optimal splits but, instead, jointly optimizes all tree parameters. Second, by leveraging gradient descent for optimization, our approach seamlessly integrates into existing ML approaches e.g., for multimodal and reinforcement learning tasks, which inherently rely on gradient descent. These advancements allow us to achieve state-of-the-art results across multiple domains, including interpretable DTs rees for small tabular datasets, advanced models for complex tabular data, multimodal learning, and interpretable reinforcement learning without information loss. By bridging the gap between DTs and gradient-based optimization, our method significantly enhances the performance and applicability of tree-based models across various ML domains.

Figures & tables

Figure 1: Exemplary DT. This is an example of a simple DT trained on a simulated dataset to predict whether a bank should approve a credit application. The decision process begins by checking if the Loan Status is greater than or equal to

0.5

, indicating whether the customer already holds a personal loan with the bank. If the customer already has a loan (

1

), the bank should not grant additional credit. If the customer does not hold a loan (

0

), the model proceeds to assess the customer’s Balance , comparing it to a threshold of

10{,}354.5

. If the balance is below the threshold, the credit application is denied. For higher balances, the model further evaluates the applicant’s Age : If the customer is older than 26.5 years, the credit is approved and otherwise, it is denied.

Panel of Figure 2 — Figure 2: Decision Boundary Comparison. This figure illustrates the decision boundaries, i.e., the hypersurface that separates different classes in the input space based on the learned function, of a DT (A) and an NN (B) on a simulated credit dataset. The decision boundary of the DT in Figure 1 clearly partitions the data along axis-aligned splits. In contrast, the NN exhibits a more flexible decision boundary, which lacks a similarly interpretable structure. Notably, the DT effectively captures the underlying patterns in the data, such as the distinct separation between Loan Status values of 0 and 1. The NN, however, introduces artificial variance by treating values between 0 and 1 differently, even though such values are not present in the dataset. This highlights the advantageous inductive bias of axis-aligned splits, which efficiently capture the relevant structure of the Loan Status variable.

Panel of Figure 3 — Figure 3: Greedy vs. Gradient-Based DT. Two DTs trained on the Echocardiogram dataset. The CART DT (A) sequentially performs only locally optimal splits, thereby constraining the search space, whereas the non-greedy algorithm (B) explores the entire search space, enabling the discovery of a solution that achieves significantly better performance.

Panel of Figure 1 — Figure 1: Visualization of a DT’s Decision-Making Process. (A) shows how the DT partitions the 2D feature space ( Age and Fare ) into regions, with each region corresponding to a prediction of whether a passenger survived. (B) shows the corresponding tree structure, detailing the decision rules at each node.

Figure 4: SDT as Mixture of Experts. This image visualizes the concept of a soft DT as a hierarchical mixture of expert model.

Table 1: Exemplary 2D Titanic Datasets.

\mathcal{D}_{L}=\{\bm{x}\in\mathcal{D}\mid x_{\iota^{*}}\geq\tau^{*}\},\quad\mathcal{D}_{R}=\{\bm{x}\in\mathcal{D}\mid x_{\iota^{*}}<\tau^{*}\}

Algorithm 2 Greedy Decision Tree Algorithm

Threshold	Left Gini	Right Gini	Weighted Gini	Gini Gain
Fare Category	0.463	0.444	0.455	0.000
Age $\geq$ 0 8.0	0.000	0.465	0.442	0.013
Age $\geq$ 10.5	0.500	0.444	0.450	0.005
Age $\geq$ 12.0	0.444	0.415	0.420	0.035
Age $\geq$ 18.5	0.375	0.375	0.375	0.080
Age $\geq$ 24.5	0.480	0.391	0.413	0.042

Table 2: Split Summary CART. Gini Values and Gini Gain for each possible split of the root node.

Figure 1: DT learned with CART. The DT achieves an accuracy of 85% on the training data and covers a total of 4 splits. It encodes the rule that if a passenger is older than 18.5, it is checked if the passenger is also older than 81.5. Those older survived and those younger did not survive, but with different certainties based on the fare category. If passengers are younger than 18.5, the tree splits based on Fare Category, where those with a low fare did survive, while those with a higher fare survived.

Figure 2: DT learned with Lookahead CART. The DT was learned using CART with a lookahead depth of 2, i.e. looking one additional step forward. It achieves an accuracy of 90% compared to 85% for plain CART (Figure 1 ) and includes 5 splits. The root node splits passengers by whether they are older than 18.5 years or not. In the second level, the tree splits on the fare for both branches and in the left branch additionally on the age. Essentially, the tree encodes three rules to decide whether a passenger survived or not. If a passenger is older than 18.5 years, paid a low fare and is older than 81.5 years, it is predicted to survive. Similarly, a passenger is predicted to survive if they are older than 18.5 years, paid a high fare and are older than 38.5 years. If a passenger is younger than 18.5 years and paid a low fare, they are also predicted to survive. In all other cases, the passenger is predicted not to survive.

Figure 3: DT learned with a Genetic Algorithm. The DT learned with a GA achieves an accuracy of 95% compared to 85% for CART (Figure 1 ) and includes 5 splits. The root node splits on the fare, and subsequent splits are made on the age attribute. Essentially, the tree encodes three rules to decide whether a passenger survived or not. If a passenger paid a low fare, is older than 80.5 years, they are predicted to survive. Similarly, a passenger is predicted to survive if they paid a low fare and are younger than 13.5 years. If a passenger paid a high fare, is older than 29.5 years, but younger than 55.5 years, they are also predicted to survive. In all other cases, the passenger is predicted not to survive.

Figure 4: DT learned with an Optimal DT Algorithm. The optimal DT achieves a perfect accuracy of 100% compared to 85% for CART (Figure 1 ) and includes 5 splits. The root node splits on the fare, and subsequent splits are made on the continuous age attribute. Essentially, the tree encodes three rules to decide whether a passenger survived or not. If a passenger paid a low fare, is older than 81.5 years, they are predicted to survive. Similarly, a passenger is predicted to survive if they paid a low fare and are younger than 18.5 years. If a passenger paid a high fare, is older than 38.5 years, but younger than 55.5 years, they are also predicted to survive. In all other cases, the passenger is predicted not to survive.

ID	Fare $=$ ’Low’	Age $\geq$ 8.0	Age $\geq$ 10.5	Age $\geq$ 12.0	$\cdots$	Age $\geq$ 71.5	Age $\geq$ 77.0	Age 81.5 $\geq$	Survived
1	1	1	1	1	$\cdots$	0	0	0	No
2	0	1	1	1	$\cdots$	0	0	0	Yes
3	0	1	1	1	$\cdots$	0	0	0	No
4	1	1	0	0	$\cdots$	0	0	0	Yes
5	0	1	1	1	$\cdots$	0	0	0	No
6	1	1	1	1	$\cdots$	0	0	0	No

Table 3: Exemplary Titanic 2D Dataset (Binarized).

Panel of Figure 5 — Figure 5: Comparison of Standard and Oblivious DTs. (A) shows a standard DT for the exemplary Titanic dataset and (B) shows a similar oblivious DT, where all nodes at a certain level share the same splitting feature and threshold.

Figure 4: DT learned with GradTree. GradTree achieves a perfect accuracy of 100% compared to 85% for CART (Figure 1 ) and includes 5 splits, similar to the optimal DT (Figure 4 ). The root node splits on the fare, and subsequent splits are made on the continuous age attribute. Essentially, the tree encodes three rules to decide whether a passenger survived or not. If a passenger paid a low fare and is older than 80.5 years, they are predicted to survive. Similarly, a passenger is predicted to survive if they paid a low fare, are younger than 80.5 yearns and younger than 18.5 years. If a passenger paid a high fare, is older than 34.5 years and younger than 56.5 years, they are also predicted to survive. In all other cases, the passenger is predicted not to survive.

	SDTs ( Jordan and Jacobs, 1994 )	NODE ( Popov et al., 2020 )	Axis-Aligned Decision Forests ( Bruch et al., 2020 )	Norouzi et al. (2015)	Karthikeyan et al. (2022)	Argmin Differentiation ( Zantedeschi et al., 2021 )	DNDT ( Yang et al., 2018 )	GradTree (ours)
Decision Boundary	oblique	oblique	axis-aligned	oblique	oblique	oblique	axis-aligned	axis-aligned
Split Type	soft	soft	hard	hard	hard	hard	soft	hard
Learnable Split Choice	-	-	no	-	-	-	no	yes
Back-propagation	yes	yes	no	yes	yes	no	yes	yes

Table 1: Gradient-Based Decision Tree Comparison. Comparison of gradient-based DT learning methods based on characteristic aspects.

	Greedy (Section 2 )	Lookahead (Section 2 )	Optimal (Section 4 )	Evolutionary (Section 3 )	Vanilla SDT (Section 1 )	GradTree (ours)
Optimization	Local	Local	Global	Global	Global	Global
Optimality (based on training data)	✗	✗	✓	✗	✗	✗
Decision Boundary	axis-aligned	axis-aligned	axis-aligned (oblique)	axis-aligned (oblique)	oblique	axis-aligned
Split Type	hard	hard	hard	hard	soft	hard
Overfitting Potential	$\mathbf{\circ}$	$\mathbf{+}$	$\mathbf{++}$	$\mathbf{--}$	$\mathbf{-}$	$\mathbf{--}$
Continuous Features	✓	✓	✗	✓	✓	✓

Table 2: Comparison of Different Types of Decision Tree Learning. In this table, we compare the different types of methods for DT learning based on their most characteristic aspects. A checkmark (✓) indicates that a characteristic is present, while a cross (✗) denotes its absence or infeasibility and

\bm{\sim}

indicated that an integration is possible but by default not implemented. Additionally, we assess methods using an ordered scale:

[\mathbf{--},\mathbf{-},\mathbf{\circ},\mathbf{+},\mathbf{++}]

. Although this evaluation is grounded in the theoretical properties of each method as introduced in the previous sections, it is important to note that the ratings inherently involve a degree of subjectivity.

Figure 5: GRANDE Architecture. This figure visualizes the structure and weighting of GRANDE for an exemplary ensemble with two trees of depth two. For each tree in the ensemble, and for every sample, we determine the weight of the leaf which the sample is assigned to. Subsequently, a softmax is applied on these chosen weights. Multiplying the post-softmax weights by the predictions equates a weighted average of the individual estimators.

Figure 1: Tabular Data. This figure visualizes the straightforward structure of tabular data, with rows as observations and columns as features.

	Gradient-Based		Non-Greedy		Greedy
	GradTree (ours)	DNDT	GeneticTree	DL8.5 (Optimal)	CART
Blood Transfusion	0.628 $\pm$ .036 (1)	0.543 $\pm$ .051 (5)	0.575 $\pm$ .094 (4)	0.590 $\pm$ .034 (3)	0.613 $\pm$ .044 (2)
Banknote Auth.	0.987 $\pm$ .007 (1)	0.888 $\pm$ .013 (5)	0.922 $\pm$ .021 (4)	0.962 $\pm$ .011 (3)	0.982 $\pm$ .007 (2)
Titanic	0.776 $\pm$ .025 (1)	0.726 $\pm$ .049 (5)	0.730 $\pm$ .074 (4)	0.754 $\pm$ .031 (2)	0.738 $\pm$ .057 (3)
Raisins	0.840 $\pm$ .022 (4)	0.821 $\pm$ .033 (5)	0.857 $\pm$ .021 (1)	0.849 $\pm$ .027 (3)	0.852 $\pm$ .017 (2)
Rice	0.926 $\pm$ .007 (3)	0.919 $\pm$ .012 (5)	0.927 $\pm$ .005 (2)	0.925 $\pm$ .008 (4)	0.927 $\pm$ .006 (1)

Table 1: Binary Classification Performance. We report macro F1-scores (mean

\pm

stdev over

10

trials) on test data with optimized hyperparameters. The rank of each method is presented in brackets. The datasets are sorted by the number of features.

	Gradient-Based		Non-Greedy		Greedy
	GradTree (ours)	DNDT	GeneticTree	DL8.5 (Optimal)	CART
Iris	0.938 $\pm$ .057 (1)	0.870 $\pm$ .063 (5)	0.912 $\pm$ .055 (3)	0.909 $\pm$ .046 (4)	0.937 $\pm$ .046 (2)
Balance Scale	0.593 $\pm$ .045 (1)	0.475 $\pm$ .104 (5)	0.529 $\pm$ .043 (3)	0.525 $\pm$ .039 (4)	0.574 $\pm$ .030 (2)
Car	0.440 $\pm$ .085 (3)	0.485 $\pm$ .064 (2)	0.306 $\pm$ .068 (4)	0.273 $\pm$ .063 (5)	0.489 $\pm$ .094 (1)
Glass	0.560 $\pm$ .090 (3)	0.434 $\pm$ .072 (5)	0.586 $\pm$ .090 (2)	0.501 $\pm$ .100 (4)	0.663 $\pm$ .086 (1)
Contraceptive	0.496 $\pm$ .050 (1)	0.364 $\pm$ .050 (3)	0.290 $\pm$ .048 (5)	0.292 $\pm$ .036 (4)	0.384 $\pm$ .075 (2)

Table 2: Multi-Class Classification Performance. We report macro F1-scores (mean

\pm

stdev over

10

trials) on test data with optimized hyperparameters and the rank of each method in brackets. The datasets are sorted by the number of features.

	Binary	Multi
GradTree	0.051	0.174
DNDT	0.039	0.239
GeneticTree	0.204	0.258
DL8.5	0.202	0.260
CART	0.183	0.247

Table 3: Train-Test Difference. Mean difference between train and test performance as overfitting indicator. Detailed results are in Table 4 .

	Gradient-Based		Non-Greedy		Greedy
	GradTree (ours)	DNDT	GeneticTree	DL8.5 (Optimal)	CART
Blood Transfusion	0.627 $\pm$ .056 (1)	0.558 $\pm$ .059 (5)	0.574 $\pm$ .093 (3)	0.590 $\pm$ .034 (2)	0.573 $\pm$ .036 (4)
Banknote Auth.	0.980 $\pm$ .008 (2)	0.886 $\pm$ .024 (5)	0.928 $\pm$ .022 (4)	0.962 $\pm$ .011 (3)	0.981 $\pm$ .006 (1)
Titanic	0.782 $\pm$ .035 (1)	0.740 $\pm$ .026 (4)	0.763 $\pm$ .041 (2)	0.754 $\pm$ .031 (3)	0.735 $\pm$ .041 (5)
Raisins	0.850 $\pm$ .025 (2)	0.832 $\pm$ .026 (4)	0.859 $\pm$ .022 (1)	0.849 $\pm$ .027 (3)	0.811 $\pm$ .028 (5)
Rice	0.926 $\pm$ .006 (2)	0.902 $\pm$ .018 (5)	0.927 $\pm$ .005 (1)	0.925 $\pm$ .008 (3)	0.905 $\pm$ .010 (4)

Table 4: Performance Comparison Default Hyperparameters. We report macro F1-scores (mean

\pm

stdev over

10

trials) with default parameters and the rank of each approach in brackets. The datasets are sorted by the number of features. The top part comprises binary classification tasks and the bottom part multi-class datasets.

	Binary	Multi
GradTree	0 54	0 86
DNDT	887	907
GeneticTree	00 7	0 20
DL8.5	0 28	0 29
CART	0 67	0 76

Table 5: Tree Size Summary. Average tree size. Detailed results are in Table 5 .

		ST Entmax (ours)	ST Gumbel	Temp. Annealing
Default	Binary	0.764	0.560	0.757
Default	Multi	0.638	0.272	0.602
Optimized	Binary	0.771	0.569	0.759
Optimized	Multi	0.699	0.297	0.601

Table 6: Ablation Study. We compare our approach to deal with the non-differentiable nature of DTs with alternative methods, reporting the average macro F1-scores over

10

trials with optimized and default hyperparameters. The complete results are listed in Table 2 - 3 .

	Samples	Features	Categorical Features	Features (preprocessed)	Minority Class	OpenML ID
dresses-sales	500	12	11	37	42.00%	23381
climate-simulation-crashes	540	18	0	18	8.52%	40994
cylinder-bands	540	37	19	82	42.22%	6332
wdbc	569	30	0	30	37.26%	1510
ilpd	583	10	1	10	28.64%	1480
tokyo1	959	44	2	44	36.08%	40705

Table 7: Datasets. A list of tabular datasets along with their characteristics used for the evaluation.

	Standard DTs	Oblivious DTs
Tree-based	XGBoost	CatBoost
Gradient-based	GRANDE	NODE

Table 8: Categorization of Approaches.

	GradTree	GRANDE	CART	RandomForest
dresses-sales	0.528 $\pm$ .037 (4)	0.596 $\pm$ .014 (1)	0.550 $\pm$ .039 (3)	0.576 $\pm$ .037 (2)
climate-simulation-crashes	0.540 $\pm$ .059 (4)	0.758 $\pm$ .065 (1)	0.705 $\pm$ .050 (2)	0.558 $\pm$ .040 (3)
cylinder-bands	0.697 $\pm$ .051 (4)	0.813 $\pm$ .023 (1)	0.713 $\pm$ .034 (3)	0.794 $\pm$ .033 (2)
wdbc	0.925 $\pm$ .033 (3)	0.962 $\pm$ .008 (1)	0.922 $\pm$ .033 (4)	0.958 $\pm$ .021 (2)
ilpd	0.613 $\pm$ .073 (2)	0.646 $\pm$ .021 (1)	0.568 $\pm$ .042 (4)	0.584 $\pm$ .018 (3)
tokyo1	0.917 $\pm$ .010 (3)	0.922 $\pm$ .014 (1)	0.908 $\pm$ .009 (4)	0.921 $\pm$ .017 (2)

Table 9: Ensembling Performance Comparison. This table compares the base learners GradTree and CART along with their basic ensembling counterparts GRANDE and RandomForest respectively. We report the test macro F1-score (mean

\pm

stdev over 10 trials) with default parameters and the ranking of each approach in parentheses. The datasets are sorted based on the data size.

	GRANDE	XGB	CatBoost	NODE
dresses-sales	0.612 $\pm$ .049 (1)	0.581 $\pm$ .059 (3)	0.588 $\pm$ .036 (2)	0.564 $\pm$ .051 (4)
climate-simulation-crashes	0.853 $\pm$ .070 (1)	0.763 $\pm$ .064 (4)	0.778 $\pm$ .050 (3)	0.802 $\pm$ .035 (2)
cylinder-bands	0.819 $\pm$ .032 (1)	0.773 $\pm$ .042 (3)	0.801 $\pm$ .043 (2)	0.754 $\pm$ .040 (4)
wdbc	0.975 $\pm$ .010 (1)	0.953 $\pm$ .030 (4)	0.963 $\pm$ .023 (3)	0.966 $\pm$ .016 (2)
ilpd	0.657 $\pm$ .042 (1)	0.632 $\pm$ .043 (3)	0.643 $\pm$ .053 (2)	0.526 $\pm$ .069 (4)
tokyo1	0.921 $\pm$ .004 (3)	0.915 $\pm$ .011 (4)	0.927 $\pm$ .013 (1)	0.921 $\pm$ .010 (2)

Table 10: Optimized Parameter Performance Comparison. We report the test macro F1-score (mean

\pm

stdev for a 5-fold CV) with optimized parameters. The datasets are sorted based on the data size.

	GRANDE	XGB	CatBoost	NODE
dresses-sales	0.596 $\pm$ .014 (1)	0.570 $\pm$ .056 (3)	0.573 $\pm$ .031 (2)	0.559 $\pm$ .045 (4)
climate-simulation-crashes	0.758 $\pm$ .065 (4)	0.781 $\pm$ .060 (1)	0.781 $\pm$ .050 (2)	0.766 $\pm$ .088 (3)
cylinder-bands	0.813 $\pm$ .023 (1)	0.770 $\pm$ .010 (3)	0.795 $\pm$ .051 (2)	0.696 $\pm$ .028 (4)
wdbc	0.962 $\pm$ .008 (3)	0.966 $\pm$ .023 (1)	0.955 $\pm$ .029 (4)	0.964 $\pm$ .017 (2)
ilpd	0.646 $\pm$ .021 (1)	0.629 $\pm$ .052 (3)	0.643 $\pm$ .042 (2)	0.501 $\pm$ .085 (4)
tokyo1	0.922 $\pm$ .014 (1)	0.917 $\pm$ .016 (4)	0.917 $\pm$ .013 (3)	0.921 $\pm$ .011 (2)

Table 11: Default Parameter Performance Comparison. We report the test macro F1-score (mean

\pm

stdev over 10 trials) with default parameters and the ranking of each approach in parentheses. The datasets are sorted based on the data size.

	Adam + SWA	Adam	RMSprop	SGD
dresses-sales	0.596 $\pm$ .014 (1)	0.586 $\pm$ .038 (2)	0.507 $\pm$ .012 (3)	0.457 $\pm$ .042 (4)
climate-simulation-crashes	0.758 $\pm$ .065 (1)	0.740 $\pm$ .068 (2)	0.528 $\pm$ .101 (3)	0.406 $\pm$ .075 (4)
cylinder-bands	0.813 $\pm$ .023 (2)	0.814 $\pm$ .034 (1)	0.706 $\pm$ .038 (3)	0.452 $\pm$ .071 (4)
wdbc	0.962 $\pm$ .008 (2)	0.964 $\pm$ .016 (1)	0.950 $\pm$ .027 (3)	0.321 $\pm$ .096 (4)
ilpd	0.646 $\pm$ .021 (1)	0.621 $\pm$ .056 (2)	0.518 $\pm$ .034 (3)	0.438 $\pm$ .051 (4)
tokyo1	0.922 $\pm$ .014 (2)	0.926 $\pm$ .014 (1)	0.918 $\pm$ .009 (3)	0.516 $\pm$ .122 (4)

Table 12: Optimizer Comparison for GRANDE. In this table, we compare different optimizers for GRANDE. We report the test macro F1-score (mean

\pm

stdev over 10 trials) with default parameters and the ranking in parentheses.

	Differentiable Split Function			Weighting Technique
	Softsign	Entmoid	Sigmoid	Leaf Weights	Estimator Weights
Normalized Mean $\uparrow$	0.7906 (1)	0.4188 (2)	0.2207 (3)	0.8235 (1)	0.1765 (2)
MRR $\uparrow$	0.8246 (1)	0.5526 (2)	0.4561 (3)	0.9211 (1)	0.5789 (2)

Table 13: Ablation Study Summary. Left: Comparison of differentiable split functions. Right: Comparison of our instance-wise weighting with a global weight for each estimator. Complete results in Table 10 and Table 11 .

Figure 3: Highest-Weighted Estimator. This figure shows the DT from GRANDE (1024 estimators) with the highest weight for an example instance.

Figure 4: Anchors Explanations. This figure shows the local explanations generated by Anchors for the given instance. The explanation for GRANDE only comprises a single rule. In contrast, the corresponding explanations for the other methods have substantially higher complexity, which indicates that these methods are not able to learn simple representations within a complex model.

		ROC $\uparrow$	ACC $\uparrow$	Balanced ACC $\uparrow$	F1 $\uparrow$
tabular	MLP	0.921	0.761	0.622	0.636
	ResNet	0.889	0.712	0.528	0.526
	GRANDE	0.943	0.792	0.675	0.690
image	ConvNeXt	0.870	0.670	0.518	0.534
multimodal	ConvNeXt + MLP	0.940	0.791	0.689	0.703
	ConvNeXt + ResNet	0.933	0.778	0.676	0.693

Table 14: PAD-UFES Multi-Class Performance Comparison. We report the scores for multi-class skin lesion classification on the PAD-UFES dataset with image and tabular component. Pretrained Image Model

Figure 2: Exemplary MDP. A schematic representation of the decision-making process in an MDP for daily activity choices from Silver (2015) . Each node represents an action (e.g., Study , Social Media , Pub , Quit , and Sleep ), with associated rewards (

r

) and transition probabilities (

p

) indicated. Arrows illustrate the possible state transitions and their respective probabilities.

Figure 3: Agent-Environment Interaction Cycle. This figure demonstrates how the agent interacts with the environment through observations, actions, transitions, and rewards, forming a feedback loop that drives learning in RL.

Panel of Figure 4 — Figure 4: On-Policy vs. Off-Policy RL. This figure illustrates the differences in data generation and reuse between on-policy methods (A), which rely on fresh interactions, and off-policy methods (B), which leverage past experiences for greater sample efficiency.

Figure 5: Actor-Critic Architecture. The actor selects actions based on its policy, while the critic evaluates these actions to provide feedback in the form of value estimates or advantages, which are used to update the policy.

Figure 6: SYMPOL overview. This is an overview of SYMPOL, with its two main components: (1) An interpretable DT policy and (2) a neural network as critic.

Figure 7: Rollout Size Factor by Global Timestep. This figure shows how the factor by which the rollout buffer size (= the number of environment steps per training iteration) is multiplied increases at a stepwise exponential rate over time.

	CP	AB	LL	MC-C	PD-C
SYMPOL (ours)	500	- 0 80	- 0 57	- 94	- 0 323
D-SDT	128	-205	-221	-10	-1343
SA-DT (d=5)	446	-97	-197	- 97	-1251
SA-DT (d=8)	476	- 0 75	-150	- 96	- 0 854
MLP	500	- 0 72	- 241	- 95	- 0 191
SDT	500	- 0 77	-124	- 0 4	- 0 310

Table 1: Control Performance. We report the average undiscounted cumulative test reward over 25 random trials. The best interpretable method, and methods not statistically different, are marked bold.

	E-R	DK	LG-5	LG-7	DS
SYMPOL (ours)	0.964	0.959	0.951	0.953	0.939
D-SDT	0.662	0.654	0.262	0.381	0.932
SA-DT (d=5)	0.583	0.958	0.951	0.458	0.952
SA-DT (d=8)	0.845	0.961	0.951	0.799	0.954
MLP	0.963	0.963	0.951	0.760	0.951
SDT	0.966	0.959	0.839	0.953	0.954

Table 2: MiniGrid Performance. We report the average undiscounted cumulative test reward over 25 random trials. The best interpretable method, and methods not statistically different, are marked bold.

Panel of Figure 8 — Figure 8: Selected Training Curves. Shows the training reward of the full-complexity policy (e.g., MLP in the case of SA-DT) as solid line and the test reward of the interpretable policy as dashed line for three control environments. Additional, more detailed results are in Appendix 7 .

	SYMPOL (ours)	SA-DT (d=5)	SA-DT (d=8)	D-SDT	MLP	SDT
Cohen’s D $\downarrow$	-0.019	- 3.449	- 2.527	- 3.126	- 0.306	- 0.040

Table 3: Information Loss. We calculated Cohen’s D to measure effect size between the validation reward of the trained model and the test reward of the applied model. Typically, values

>0.8

are considered as a large effect. Detailed results are listed in Appendix 2

	SYMPOL (ours)	SDT	MLP
CP	28.8	23.9	25.2
AB	35.5	37.7	33.8
MC-C	23.4	19.4	18.4
PD-C	28.7	28.2	18.5
Mean $\downarrow$	29.1	27.3	24.0

Table 4: Runtime SYMPOL. We report the average runtime over 25 trials with 1mio timesteps each. We excluded LL, as this is the only non-vectorized environment.

Figure 9: SYMPOL Policy for MC-C. The main rule encoded by this tree is that the car should accelerate to the left if its velocity is negative and to the right if it is positive, which essentially increases the speed of the car over time, making it possible to reach the goal at the top of the hill. The magnitude of the acceleration is mainly determined by the current position, reducing the cost of the actions.

	SYMPOL (ours)	D-SDT	SA-DT (d=5)	SA-DT (d=8)
CP	39.4	14.2	61.8	315.0
AB	78.6	17.0	56.5	173.0
LL	55.0	19.8	59.8	270.2
MC-C	23.4	0 3.0	61.0	311.8
PD-C	56.2	28.6	62.2	388.2
Mean $\downarrow$	50.5	16.5	60.3	291.6

Table 5: Tree Size. We report the average size of the learned DT for each environment.

Figure 10: Ablation Study. We report the mean normalized performance over all control environments. Detailed results are reported in Table 8 .

Figure 1: DT learned with Hunt’s Algorithm and Misclassification Error as Impurity Measure. The tree achieves an accuracy of

80\%

on the training data and involves two decisions. The main rule encoded by the tree is that a passenger is predicted to survive if he is young and has paid a low fare, and is unlikely to survive otherwise. The right branch of the root does not split further, as the misclassification error does not decrease when splitting on fare (0.250 before and after).

Appendix figures & tables73 assets

Supplementary material from the paper’s appendix.

Appendix

Operation	Explanation
$\sum$	Summation
$\prod$	Product
$\cdot$	Dot product
$\otimes$	Outer product (Kronecker product)
$\odot$	Element-wise multiplication (Hadamard product)
$\bmod$	Modulo operation (remainder after division)

Appendix

Table 1: Relevant Mathematical Operations

Function	Explanation
$\mathbb{E}[\cdot]$	Expected value
$\mathbb{L}(\cdot)$	Indicator function
$\nabla$	Gradient
$\mathrm{clip}(\cdot)$	Clipping function
$\mathrm{min}(\cdot)$	Minimum value
$\mathrm{exp}(\cdot)$	Exponential function

Appendix

Table 2: Relevant Functions

Figure 2: DT learned with ID3. The tree achieves an accuracy of

80\%

on the training data and involves three decisions. The main rule encoded by the tree is that a passenger is predicted to survive if he is young and has paid a low fare, and is unlikely to survive otherwise. While the misclassification error does nor decrease with the additional split on the right branch of the root node (still both leafs are ’Not Survived’), the impurity still decreases significantly justifying this additional split, resulting in additional information on the likelihood of survival which is significantly worse fore passengers that are old and paid a low fare.

Split	Info Gain	Split Info	Gain Ratio
Fare Category	0.001	0.993	0.001
Age $\geq$ 0 8.0	0.032	0.286	0.112
Age $\geq$ 10.5	0.008	0.469	0.016
Age $\geq$ 12.0	0.053	0.610	0.088
Age $\geq$ 18.5	0.123	0.722	0.170
Age $\geq$ 24.5	0.064	0.811	0.079

Appendix

Table 1: Split Summary C4.5. Information Gain, Split Information and Gain Ratio for each possible split of the root node.

Figure 3: DT learned with C4.5. The tree achieves an accuracy of 80% on the training data and includes 3 decisions. It encodes the rule that if a person is older than 81.5, the person survived, otherwise, if the passenger is older than 55.5, they did not survive. If Age is less than 55.5, those older than 44.5 survived, while those younger did not survive.

Threshold	Left Gini	Right Gini	Weighted Gini	Gini Gain
Fare Category	0.463	0.444	0.455	0.000
Age $\geq$ 0 8.0	0.000	0.465	0.442	0.013
Age $\geq$ 10.5	0.500	0.444	0.450	0.005
Age $\geq$ 12.0	0.444	0.415	0.420	0.035
Age $\geq$ 18.5	0.375	0.375	0.375	0.080
Age $\geq$ 24.5	0.480	0.391	0.413	0.042

Appendix

Table 2: Split Summary CART. Gini Values and Gini Gain for each possible split of the root node.

Figure 4: DT learned with CART. The DT achieves an accuracy of 85% on the training data and covers a total of 4 splits. It encodes the rule that if a passenger is older than 18.5, it is checked if the passenger is also older than 81.5. Those older survived and those younger did not survive, but with different certainties based on the fare. If passengers are younger than 18.5, the tree splits based on Fare Category, where those with a low fare did survive, while those with a higher fare survived.

	ID3 (Section 8.A )	C4.5 (Section 8.A )	CART (Section 8.B )
Impurity Measures	Information Gain	Gain Ratio	Gini Impurity
Continuous Attributes	-	yes	yes
Pruning Strategy	-	post-pruning	cost-complexity pruning
Splitting Strategy	multi-way	multi-way	binary
Missing Values	-	probabilistic	surrogate splits

Appendix

Table 3: Comparison of ID3, C4.5 and CART. In this table, we compare common greedy, purity-based DT induction methods based on the most relevant aspects.

Dataset Name	Number of Features	Number of Samples	Samples by Class	Number of Classes	Link
Blood Transfusion	4	748	178 / 570	2	https://archive.ics.uci.edu/ml/datasets/Blood+Transfusion+Service+Center
Banknote Authentication	4	1372	610 / 762	2	https://archive.ics.uci.edu/ml/datasets/banknote+authentication
Titanic	7	891	342 / 549	2	https://www.kaggle.com/c/titanic
Raisin	7	900	450 /450	2	https://archive.ics.uci.edu/ml/datasets/Raisin+Dataset
Rice	7	3810	1630 / 2180	2	https://archive.ics.uci.edu/ml/datasets/Rice+%28Cammeo+and+Osmancik%29
Echocardiogram	8	132	107 / 25	2	https://archive.ics.uci.edu/ml/datasets/echocardiogram

Appendix

Table 1: Dataset Specifications.

	ST Entmax (ours)	ST Gumbel Softmax	Temperature Annealing
Blood Transfusion	0.628 $\pm$ .036 (1)	0.482 $\pm$ .083 (3)	0.606 $\pm$ .073 (2)
Banknote Authentication	0.987 $\pm$ .007 (1)	0.770 $\pm$ .144 (3)	0.946 $\pm$ .041 (2)
Titanic	0.776 $\pm$ .025 (1)	0.543 $\pm$ .093 (3)	0.762 $\pm$ .036 (2)
Raisins	0.840 $\pm$ .022 (2)	0.792 $\pm$ .069 (3)	0.846 $\pm$ .028 (1)
Rice	0.926 $\pm$ .007 (2)	0.859 $\pm$ .058 (3)	0.927 $\pm$ .006 (1)
Echocardiogram	0.658 $\pm$ .113 (1)	0.574 $\pm$ .108 (3)	0.619 $\pm$ .151 (2)

Appendix

Table 2: Ablation Study Optimized Parameters. We report macro F1-scores (mean

\pm

stdev over

10

trials) with optimized parameters and the rank of each approach in brackets. The datasets are sorted by the number of features. The top part comprises binary classification tasks and the bottom part multi-class datasets.

	ST Entmax (ours)	ST Gumbel Softmax	Temperature Annealing
Blood Transfusion	0.627 $\pm$ .056 (1)	0.497 $\pm$ .086 (3)	0.618 $\pm$ .045 (2)
Banknote Authentication	0.980 $\pm$ .008 (1)	0.722 $\pm$ .126 (3)	0.970 $\pm$ .007 (2)
Titanic	0.782 $\pm$ .035 (1)	0.623 $\pm$ .096 (3)	0.769 $\pm$ .033 (2)
Raisins	0.850 $\pm$ .025 (2)	0.802 $\pm$ .055 (3)	0.853 $\pm$ .016 (1)
Rice	0.926 $\pm$ .006 (1)	0.802 $\pm$ .101 (3)	0.926 $\pm$ .006 (1)
Echocardiogram	0.648 $\pm$ .130 (1)	0.571 $\pm$ .093 (3)	0.595 $\pm$ .121 (2)

Appendix

Table 3: Ablation Study Default Parameters. We report macro F1-scores (mean

\pm

stdev over

10

	Gradient-Based		Non-Greedy		Greedy
	GradTree (ours)	DNDT	GeneticTree	DL8.5 (Optimal)	CART
Blood Transfusion	0.686 $\pm$ .032 (3)	0.552 $\pm$ .085 (5)	0.615 $\pm$ .122 (4)	0.711 $\pm$ .045 (2)	0.832 $\pm$ .040 (1)
Banknote Authentication	0.995 $\pm$ .003 (2)	0.907 $\pm$ .012 (5)	0.933 $\pm$ .016 (4)	0.967 $\pm$ .003 (3)	0.999 $\pm$ .001 (1)
Titanic	0.761 $\pm$ .128 (5)	0.791 $\pm$ .025 (4)	0.908 $\pm$ .023 (3)	0.970 $\pm$ .006 (1)	0.949 $\pm$ .012 (2)
Raisins	0.892 $\pm$ .024 (1)	0.829 $\pm$ .027 (5)	0.863 $\pm$ .004 (4)	0.889 $\pm$ .004 (2)	0.866 $\pm$ .004 (3)
Rice	0.925 $\pm$ .003 (3)	0.913 $\pm$ .012 (5)	0.920 $\pm$ .002 (4)	0.930 $\pm$ .002 (1)	0.927 $\pm$ .002 (2)

Appendix

Table 4: Train Performance Comparison. We report macro F1-scores (mean

\pm

stdev over

10

trials) on the training data and the rank of each approach in brackets. The datasets are sorted by the number of features. The top part comprises binary classification tasks and the bottom part multi-class datasets.

	Gradient-Based		Non-Greedy		Greedy
	GradTree (ours)	DNDT	GeneticTree	DL8.5 (Optimal)	CART
Blood Transfusion	0 29.20 $\pm$ 00 8.22 (3)	0.0 24.00 $\pm$ 0.00 0.00 (2)	0 5.20 $\pm$ 0 3.03 (1)	24.00 $\pm$ 0 1.61 (3)	165.60 $\pm$ 0 21.84 (5)
Banknote Authentication	0 60.00 $\pm$ 0 11.22 (5)	0.0 24.00 $\pm$ 0.00 0.00 (2)	12.80 $\pm$ 0 5.33 (1)	26.80 $\pm$ 0 0.60 (3)	0 44.80 $\pm$ 00 4.69 (4)
Titanic	0 39.60 $\pm$ 0 10.17 (3)	0. 142.00 $\pm$ 0.00 0.00 (5)	10.40 $\pm$ 0 3.11 (1)	28.20 $\pm$ 0 0.98 (3)	0 21.60 $\pm$ 00 0.92 (2)
Raisins	114.80 $\pm$ 0 33.69 (4)	0. 142.00 $\pm$ 0.00 0.00 (5)	0 3.60 $\pm$ 0 1.80 (2)	29.40 $\pm$ 0 1.50 (3)	00 3.00 $\pm$ 00 0.00 (1)
Rice	0 41.00 $\pm$ 0 10.05 (4)	0. 142.00 $\pm$ 0.00 0.00 (5)	0 3.00 $\pm$ 0 0.00 (2)	30.20 $\pm$ 0 0.98 (3)	00 3.00 $\pm$ 00 0.00 (1)

Appendix

Table 5: Tree Size Comparison. We report the average tree size based on the optimized hyperparameters (mean

\pm

stdev over

10

trials) and the rank of each approach in brackets. The datasets are sorted by the number of features. The top part comprises binary classification tasks and the bottom part multi-class datasets.

	Gradient-Based		Non-Greedy		Greedy
	GradTree (ours)	DNDT	GeneticTree	DL8.5 (Optimal)	CART
Blood Transfusion	0.627 $\pm$ .056 (1)	0.558 $\pm$ .059 (5)	0.574 $\pm$ .093 (3)	0.590 $\pm$ .034 (2)	0.573 $\pm$ .036 (4)
Banknote Authentication	0.980 $\pm$ .008 (2)	0.886 $\pm$ .024 (5)	0.928 $\pm$ .022 (4)	0.962 $\pm$ .011 (3)	0.981 $\pm$ .006 (1)
Titanic	0.782 $\pm$ .035 (1)	0.740 $\pm$ .026 (4)	0.763 $\pm$ .041 (2)	0.754 $\pm$ .031 (3)	0.735 $\pm$ .041 (5)
Raisins	0.850 $\pm$ .025 (2)	0.832 $\pm$ .026 (4)	0.859 $\pm$ .022 (1)	0.849 $\pm$ .027 (3)	0.811 $\pm$ .028 (5)
Rice	0.926 $\pm$ .006 (2)	0.902 $\pm$ .018 (5)	0.927 $\pm$ .005 (1)	0.925 $\pm$ .008 (3)	0.905 $\pm$ .010 (4)

Appendix

Table 6: Performance Comparison Default Hyperparameters. We report macro F1-scores (mean

\pm

stdev over

10

	Gradient-Based		Non-Greedy		Greedy
	GradTree (ours)	DNDT	GeneticTree	DL8.5 (Optimal)	CART
Blood Transfusion	0 13.01 $\pm$ 0 1.00 (5)	0 3.70 $\pm$ 0 1.00 (3)	0 10.51 $\pm$ 0 4.00 (4)	00 0.03 $\pm$ 0.00 (2)	0.00 $\pm$ 0.00 (1)
Banknote Authentication	0 13.21 $\pm$ 0 2.00 (4)	34.43 $\pm$ 0 1.00 (5)	0 10.32 $\pm$ 0 3.00 (3)	00 0.03 $\pm$ 0.00 (2)	0.00 $\pm$ 0.00 (1)
Titanic	0 29.58 $\pm$ 0 1.00 (5)	0 6.82 $\pm$ 0 0.00 (4)	00 3.68 $\pm$ 0 1.00 (3)	00 0.26 $\pm$ 0.00 (2)	0.00 $\pm$ 0.00 (1)
Raisins	0 30.61 $\pm$ 0 2.00 (5)	0 8.50 $\pm$ 0 1.00 (4)	00 0.62 $\pm$ 0 0.00 (3)	00 0.20 $\pm$ 0.00 (2)	0.00 $\pm$ 0.00 (1)
Rice	0 21.49 $\pm$ 0 4.00 (5)	11.96 $\pm$ 0 1.00 (4)	00 1.33 $\pm$ 0 0.00 (3)	00 0.48 $\pm$ 0.00 (2)	0.01 $\pm$ 0.00 (1)

Appendix

Table 7: Runtime Comparison. We report runtime without restarts based on the optimized hyperparameters (mean

\pm

stdev over

10

trials) and the rank of each approach in brackets. The datasets are sorted by the number of features. The top part comprises binary classification tasks and the bottom part multi-class datasets.

	Binary		Multi
	Penalty	No Penalty	Penalty	No Penalty
F1-Score	0.671	0.713	0.546	0.573
Tree Size	0,00 7	1,600	0,0 20	2,201

Appendix

Table 8: GeneticTree Comparison. We compare GeneticTree with and without complexity penalty.

Dataset Name	depth	lr_index	lr_values	lr_leaf	activation	loss	polyLoss	epsilon
Blood Transfusion	8	0.010	0.100	0.010	entmax	crossentropy	False	2
Banknote Authentication	7	0.050	0.050	0.100	entmax	focal_crossentropy	True	2
Titanic	10	0.005	0.010	0.010	entmax	crossentropy	False	2
Raisins	10	0.005	0.005	0.100	entmax	crossentropy	True	5
Rice	7	0.050	0.010	0.010	entmax	crossentropy	False	2
Echocardiogram	8	0.010	0.050	0.100	entmax	crossentropy	True	5

Appendix

Table 9: GradTree Hyperparameters

Dataset Name	learning_rate	temperature	num_cut
Blood Transfusion	0.050	0.100	1
Banknote Authentication	0.001	0.100	1
Titanic	0.050	0.001	1
Raisins	0.050	0.001	1
Rice	0.100	0.010	1
Echocardiogram	0.005	1.000	1

Appendix

Table 10: DNDT Hyperparameters

Dataset Name	n_thresholds	n_trees	max_iter	cross_prob	mutation_prob
Blood Transfusion	10	500	500	1.0	0.2
Banknote Authentication	10	500	500	0.8	0.6
Titanic	10	500	250	0.2	0.3
Raisins	10	100	50	1.0	0.6
Rice	10	100	250	0.4	0.3
Echocardiogram	10	50	100	0.8	0.4

Appendix

Table 11: GeneticTree Hyperparameters

Dataset Name	max_depth	criterion	max_features	samples_leaf	samples_split	ccp_alpha
Blood Transfusion	9	entropy	None	1	5	0.0
Banknote Authentication	9	gini	None	1	5	0.0
Titanic	7	entropy	None	1	50	0.0
Raisins	8	gini	None	5	2	0.2
Rice	8	gini	None	5	2	0.2
Echocardiogram	9	entropy	None	1	5	0.0

Appendix

Table 12: CART Hyperparameters

	Number Internal Nodes	Number Leaf Nodes	Percentage Highest Estimator	Percentage Highest Estimator Top 5%	Count Highest Estimator	Count Highest Estimator Top 5%
dresses-sales	1.12	2.12	0.470	0.667	10.20	2.40
climate-model-simulation	3.12	4.12	0.241	0.467	15.80	4.00
cylinder-bands	5.44	6.44	0.124	0.400	31.20	4.00
wdbc	1.16	2.16	0.587	0.733	4.20	1.60
ilpd	3.96	4.96	0.319	0.600	15.00	3.40
tokyo1	3.20	4.20	0.273	0.780	19.80	2.00

Appendix

Table 1: Weighting Statistics Estimator. This table shows summarizing statistics on the instance-wise weighting for each dataset.

	Skewness	Skewness Top 5%	Kurtosis	Kurtosis Top 5%
dresses-sales	0.946	1.187	0.617	1.597
climate-model-simulation	1.259	1.909	0.742	3.095
cylinder-bands	0.853	1.199	-0.562	0.230
wdbc	0.082	0.251	-1.084	-0.980
ilpd	0.180	0.385	-0.649	-0.528
tokyo1	0.975	1.839	1.322	4.919

Appendix

Table 2: Weighting Statistics Distribution. We provide the skewness, as measure of the asymmetry of a distribution, and kurtosis, as measure of the tailedness of a distribution, for all datasets. The measures are split in an average over all samples and an average over the top 5% of the samples with the highest maximum weight.

	Very skewed $(-\infty,-1.0)$ or $(1.0,\infty)$	Skewed $[-1.0,-0.5)$ or $(0.5,1.0]$	Slight skew $[-0.5,0.5]$	Sum
Left skew	0	1	1	2
Right skew	6	9	2	17
Sum	6	10	3

Appendix

Table 3: Skewness Summary. This table summarizes the skewness of estimator weights in different categories based on the magnitude of skewness on each dataset.

	Very skewed $(-\infty,-1.0)$ or $(1.0,\infty)$	Skewed $[-1.0,-0.5)$ or $(0.5,1.0]$	Slight skew $[-0.5,0.5]$	Sum
Left skew	0	1	1	2
Right skew	13	1	3	17
Sum	13	2	4

Appendix

Table 4: Skewness Top 5%. This table summarizes the skewness of estimator weights in different categories based on the magnitude of skewness on each dataset, considering only the top 5% of samples with the highest weight for a single estimator.

Excess Kurtosis	Count	Count Top 5%
Very leptokurtic $(3.0,\infty)$	4	8
Moderately leptokurtic $(0.5,3.0]$	7	6
Mesokurtic $[-0.5,0.5]$	5	3
Platykurtic $(-\infty,-0.5)$	3	2

Appendix

Table 5: Kurtosis. This table categorizes the kurtosis of the weighting distribution for each dataset.

Figure 1: Performance Profile (HPO 250 Trials) . The performance profile is based on the macro F1-Score with optimized hyperparameters (complete grids, 250 trials). The x-axis represents a tolerance factor, and the y-axis is a proportion of the evaluated datasets.

	GRANDE	XGB	CatBoost	NODE
dresses-sales	0.623 $\pm$ 0.049 (2)	0.589 $\pm$ 0.060 (4)	0.607 $\pm$ 0.040 (3)	0.632 $\pm$ 0.041 (1)
climate-simulation-crashes	0.958 $\pm$ 0.031 (1)	0.923 $\pm$ 0.031 (4)	0.938 $\pm$ 0.036 (2)	0.933 $\pm$ 0.030 (3)
cylinder-bands	0.896 $\pm$ 0.032 (1)	0.872 $\pm$ 0.019 (3)	0.879 $\pm$ 0.046 (2)	0.837 $\pm$ 0.037 (4)
wdbc	0.993 $\pm$ 0.006 (1)	0.990 $\pm$ 0.010 (4)	0.990 $\pm$ 0.010 (3)	0.993 $\pm$ 0.007 (2)
ilpd	0.748 $\pm$ 0.046 (1)	0.721 $\pm$ 0.047 (4)	0.728 $\pm$ 0.055 (3)	0.745 $\pm$ 0.048 (2)
tokyo1	0.983 $\pm$ 0.005 (2)	0.982 $\pm$ 0.006 (3)	0.984 $\pm$ 0.005 (1)	0.980 $\pm$ 0.005 (4)

Appendix

Table 6: ROC-AUC Performance Comparison (HPO 250 Trials). We report the test ROC-AUC (mean

\pm

stdev for a 5-fold CV) with optimized parameters (complete grids, 250 trials) and the ranking of each approach in parentheses. The datasets are sorted based on the data size.

	GRANDE	XGB	CatBoost	NODE
dresses-sales	0.613 $\pm$ 0.048 (1)	0.585 $\pm$ 0.060 (3)	0.589 $\pm$ 0.037 (2)	0.581 $\pm$ 0.037 (4)
climate-simulation-crashes	0.875 $\pm$ 0.079 (1)	0.762 $\pm$ 0.060 (4)	0.832 $\pm$ 0.035 (2)	0.773 $\pm$ 0.052 (3)
cylinder-bands	0.817 $\pm$ 0.032 (1)	0.777 $\pm$ 0.045 (3)	0.798 $\pm$ 0.042 (2)	0.751 $\pm$ 0.040 (4)
wdbc	0.973 $\pm$ 0.010 (1)	0.952 $\pm$ 0.029 (4)	0.963 $\pm$ 0.023 (3)	0.963 $\pm$ 0.017 (2)
ilpd	0.709 $\pm$ 0.046 (1)	0.673 $\pm$ 0.042 (3)	0.689 $\pm$ 0.062 (2)	0.548 $\pm$ 0.054 (4)
tokyo1	0.925 $\pm$ 0.002 (2)	0.918 $\pm$ 0.012 (4)	0.932 $\pm$ 0.010 (1)	0.920 $\pm$ 0.007 (3)

Appendix

Table 7: Accuracy Performance Comparison (HPO 250 Trials). We report the test balanced accuracy (mean

\pm

stdev for a 5-fold CV) with optimized parameters (complete grids, 250 trials) and the ranking of each approach in parentheses. The datasets are sorted based on the data size.

	GRANDE	XGB	CatBoost	NODE
dresses-sales	0 11.121 $\pm$ 0 1.0 (3)	0.052 $\pm$ 0.0 (1)	0 4.340 $\pm$ 2.0 (2)	0 31.371 $\pm$ 0 17.0 (4)
climate-simulation-crashes	0 16.838 $\pm$ 0 3.0 (3)	0.077 $\pm$ 0.0 (1)	0 8.740 $\pm$ 9.0 (2)	0 97.693 $\pm$ 0 10.0 (4)
cylinder-bands	0 20.554 $\pm$ 0 2.0 (3)	0.093 $\pm$ 0.0 (1)	0 4.887 $\pm$ 2.0 (2)	0 38.983 $\pm$ 0 12.0 (4)
wdbc	0 29.704 $\pm$ 0 4.0 (3)	0.151 $\pm$ 0.0 (1)	0 1.046 $\pm$ 0.0 (2)	0 83.548 $\pm$ 0 16.0 (4)
ilpd	0 11.424 $\pm$ 0 1.0 (3)	0.049 $\pm$ 0.0 (1)	0 3.486 $\pm$ 3.0 (2)	0 59.085 $\pm$ 0 24.0 (4)
tokyo1	0 21.483 $\pm$ 0 3.0 (3)	0.078 $\pm$ 0.0 (1)	0 1.485 $\pm$ 1.0 (2)	0 84.895 $\pm$ 00 5.0 (4)

Appendix

Table 8: Runtime Performance Comparison. We report the runtime (mean

\pm

stdev for a 5-fold CV) with optimized parameters (complete grids, 250 trials) and the ranking of each approach in parentheses. The datasets are sorted based on the data size. For all methods, we used a single NVIDIA RTX A6000.

	GRANDE - GradTree	RandomForest - CART
dresses-sales	0.0683	0.0266
climate-simulation-crashes	0.2185	-0.1475
cylinder-bands	0.1156	0.0805
wdbc	0.0369	0.0367
ilpd	0.0333	0.0168
tokyo1	0.0046	0.0129

Appendix

Table 9: Dataset Differences. This table summarizes the performance difference between the base learners GradTree and CART along with their basic ensembling counterparts GRANDE and RandomForest respectively. We report the difference in test macro F1-score (mean

\pm

stdev over 10 trials) with default parameters.

	Softsign	Entmoid	Sigmoid
dresses-sales	0.612 $\pm$ 0.049 (1)	0.580 $\pm$ 0.047 (2)	0.568 $\pm$ 0.052 (3)
climate-simulation-crashes	0.853 $\pm$ 0.070 (1)	0.840 $\pm$ 0.038 (2)	0.838 $\pm$ 0.041 (3)
cylinder-bands	0.819 $\pm$ 0.032 (1)	0.802 $\pm$ 0.028 (3)	0.807 $\pm$ 0.020 (2)
wdbc	0.975 $\pm$ 0.010 (1)	0.970 $\pm$ 0.007 (3)	0.972 $\pm$ 0.008 (2)
ilpd	0.657 $\pm$ 0.042 (2)	0.652 $\pm$ 0.047 (3)	0.663 $\pm$ 0.047 (1)
tokyo1	0.921 $\pm$ 0.004 (1)	0.920 $\pm$ 0.010 (3)	0.921 $\pm$ 0.008 (2)

Appendix

Table 10: Ablation Study Split Activation. We report the test macro F1-Score (mean

\pm

stdev for a 5-fold CV) with optimized parameters (complete grids, 250 trials) and the ranking of each approach in parentheses. The datasets are sorted based on the data size.

	Leaf Weights	Estimator Weights
dresses-sales	0.612 $\pm$ 0.049 (1)	0.605 $\pm$ 0.050 (2)
climate-simulation-crashes	0.853 $\pm$ 0.070 (1)	0.801 $\pm$ 0.040 (2)
cylinder-bands	0.819 $\pm$ 0.032 (1)	0.787 $\pm$ 0.051 (2)
wdbc	0.975 $\pm$ 0.010 (1)	0.970 $\pm$ 0.009 (2)
ilpd	0.657 $\pm$ 0.042 (1)	0.612 $\pm$ 0.064 (2)
tokyo1	0.921 $\pm$ 0.004 (2)	0.922 $\pm$ 0.016 (1)

Appendix

Table 11: Ablation Study Weighting. We report the test macro F1-Score (mean

\pm

stdev for a 5-fold CV) with optimized parameters (complete grids, 250 trials) and the ranking of each approach in parentheses. The datasets are sorted based on the data size.

	Correct DT	Incorrect DT	Total
Correct GRANDE	2012	128	2140
Incorrect GRANDE	15	56	71
Total	2027	184

Appendix

Table 12: Pairwise Confusion Matrix PhishingWebsites. We compare the predictions of each approach with the predictions of a CART DT. It becomes evident, that a simple model is not sufficient to solve the task well, as CART makes more than twice as many mistakes as state-of-the-art models.

	GRANDE	XGB	CatBoost	NODE	ExtraTree	RandomForest
dresses-sales	0.612 (1)	0.581 (4)	0.588 (3)	0.564 (5)	0.589 (2)	0.559 (6)
climate-model-simulation	0.853 (1)	0.763 (4)	0.778 (3)	0.802 (2)	0.754 (5)	0.751 (6)
cylinder-bands	0.819 (1)	0.773 (4)	0.801 (2)	0.754 (6)	0.762 (5)	0.782 (3)
wdbc	0.975 (1)	0.953 (4)	0.963 (3)	0.966 (2)	0.951 (5)	0.949 (6)
ilpd	0.657 (1)	0.632 (5)	0.643 (3)	0.526 (6)	0.645 (2)	0.640 (4)
tokyo1	0.921 (3)	0.915 (5)	0.927 (1)	0.921 (2)	0.916 (4)	0.909 (6)

Appendix

Table 13: Extended Performance Comparison (HPO 250 trials). We report the test macro F1-score (mean for a 5-fold CV) with optimized parameters based on a HPO with 250 trials. The datasets are sorted based on the data size.

	GRANDE	XGB	CatBoost	NODE	ExtraTree	RandomForest	SAINT
dresses-sales	0.596 (1)	0.567 (5)	0.592 (2)	0.564 (6)	0.583 (3)	0.570 (4)	0.516 (7)
climate-model-simulation-crashes	0.841 (1)	0.764 (6)	0.782 (5)	0.802 (3)	0.802 (2)	0.793 (4)	0.744 (7)
cylinder-bands	0.799 (1)	0.769 (4)	0.787 (3)	0.754 (6)	0.766 (5)	0.753 (7)	0.791 (2)
wdbc	0.966 (2)	0.959 (4)	0.964 (3)	0.966 (1)	0.955 (5)	0.951 (7)	0.952 (6)
ilpd	0.656 (1)	0.625 (5)	0.650 (2)	0.526 (6)	0.650 (3)	0.642 (4)	0.425 (7)
tokyo1	0.933 (1)	0.919 (6)	0.925 (3)	0.921 (4)	0.929 (2)	0.920 (5)	0.915 (7)

Appendix

Table 14: Extended Performance Comparison (HPO 30 trials). We report the test macro F1-score (mean for a 5-fold CV) with optimized parameters (30 trials). The datasets are sorted based on the data size.

	GRANDE	XGB	CatBoost	NODE	ExtraTree	RandomForest	SAINT
dresses-sales	0.596 (1)	0.570 (3)	0.573 (2)	0.559 (4)	0.545 (6)	0.554 (5)	0.422 (7)
climate-model-simulation-crashes	0.758 (5)	0.781 (2)	0.781 (3)	0.766 (4)	0.728 (6)	0.714 (7)	0.850 (1)
cylinder-bands	0.813 (1)	0.770 (5)	0.795 (2)	0.696 (7)	0.780 (4)	0.787 (3)	0.733 (6)
wdbc	0.962 (3)	0.966 (1)	0.955 (4)	0.964 (2)	0.940 (7)	0.942 (6)	0.945 (5)
ilpd	0.646 (1)	0.629 (3)	0.643 (2)	0.501 (6)	0.582 (5)	0.592 (4)	0.416 (7)
tokyo1	0.922 (1)	0.917 (6)	0.917 (5)	0.921 (2)	0.917 (3)	0.917 (4)	0.907 (7)

Appendix

Table 15: Extended Performance Comparison (Default Parameters). We report the test macro F1-score (mean for a 5-fold CV) with default parameters. The datasets are sorted based on the data size.

	Without tuning estimators	With tuning estimators	Difference
dresses-sales	0.5755	0.5813	-0.0058
climate-model-simulation-crashes	0.7932	0.7626	0.0306
cylinder-bands	0.7670	0.7734	-0.0064
wdbc	0.9568	0.9531	0.0037
ilpd	0.6316	0.6321	-0.0005
tokyo1	0.9147	0.9147	0.0000

Appendix

Table 16: Comparison XGB HPO (250 Trials). We compare a HPO for XGBoost with and without tuning the number of estimators based on 250 trials. Tuning the estimators does not improve the performance, and using early stopping in addition to setting the number of estimators to a high number is sufficient.

	Without tuning estimators	With tuning estimators	Difference
dresses-sales	0.5611	0.5880	-0.0270
climate-model-simulation-crashes	0.7902	0.7775	0.0127
cylinder-bands	0.8080	0.8014	0.0066
wdbc	0.9551	0.9625	-0.0074
ilpd	0.6379	0.6428	-0.0049
tokyo1	0.9249	0.9274	-0.0025

Appendix

Table 17: Comparison CatBoost HPO (250 Trials). We compare a HPO for CatBoost with and without tuning the number of estimators based on 250 trials. Tuning the estimators does not improve the performance, and using early stopping in addition to setting the number of estimators to a high number is sufficient.

	GRANDE	XGB	CatBoost	NODE
dresses-sales	0.596 $\pm$ 0.047 (1)	0.567 $\pm$ 0.055 (3)	0.592 $\pm$ 0.046 (2)	0.564 $\pm$ 0.051 (4)
climate-model-simulation	0.841 $\pm$ 0.058 (1)	0.764 $\pm$ 0.073 (4)	0.782 $\pm$ 0.057 (3)	0.802 $\pm$ 0.035 (2)
cylinder-bands	0.799 $\pm$ 0.037 (1)	0.769 $\pm$ 0.040 (3)	0.787 $\pm$ 0.044 (2)	0.754 $\pm$ 0.040 (4)
wdbc	0.966 $\pm$ 0.019 (2)	0.959 $\pm$ 0.026 (4)	0.964 $\pm$ 0.022 (3)	0.966 $\pm$ 0.016 (1)
ilpd	0.656 $\pm$ 0.044 (1)	0.625 $\pm$ 0.052 (3)	0.650 $\pm$ 0.059 (2)	0.526 $\pm$ 0.069 (4)
tokyo1	0.933 $\pm$ 0.011 (1)	0.919 $\pm$ 0.012 (4)	0.925 $\pm$ 0.011 (2)	0.921 $\pm$ 0.010 (3)

Appendix

Table 18: HPO 30 Trials Performance Comparison. We report the test macro F1-score (mean

\pm

stdev over 10 trials) based on a reduced HPO with only 30 trials. The datasets are sorted based on the data size.

	GRANDE	XGB	CatBoost	NODE
dresses-sales	0.590 $\pm$ 0.042 (1)	0.581 $\pm$ 0.059 (3)	0.588 $\pm$ 0.036 (2)	0.564 $\pm$ 0.051 (4)
climate-model-simulation	0.800 $\pm$ 0.055 (2)	0.763 $\pm$ 0.064 (4)	0.778 $\pm$ 0.050 (3)	0.802 $\pm$ 0.035 (1)
cylinder-bands	0.783 $\pm$ 0.040 (2)	0.773 $\pm$ 0.042 (3)	0.801 $\pm$ 0.043 (1)	0.754 $\pm$ 0.040 (4)
wdbc	0.964 $\pm$ 0.007 (2)	0.953 $\pm$ 0.030 (4)	0.963 $\pm$ 0.023 (3)	0.966 $\pm$ 0.016 (1)
ilpd	0.645 $\pm$ 0.030 (1)	0.632 $\pm$ 0.043 (3)	0.643 $\pm$ 0.053 (2)	0.526 $\pm$ 0.069 (4)
tokyo1	0.928 $\pm$ 0.017 (1)	0.915 $\pm$ 0.011 (4)	0.927 $\pm$ 0.013 (2)	0.921 $\pm$ 0.010 (3)

Appendix

Table 19: HPO Reduced Grid Performance Comparison (250 Trials). We report the test macro F1-score (mean

\pm

stdev over 10 trials) based on a HPO with a reduced parameter grid for GRANDE (only one overall learning_rate, focal_factor, cosine_decay_steps and dropout) and 250 trials for all methods. The datasets are sorted based on the data size.

	depth	n_estimators	lr_weights	lr_index	lr_values	lr_leaf
dresses-sales	4	512	0.0015	0.0278	0.1966	0.0111
climate-simulation-crashes	4	2048	0.0007	0.0243	0.0156	0.0134
cylinder-bands	6	2048	0.0009	0.0084	0.0086	0.0474
wdbc	4	1024	0.0151	0.0140	0.1127	0.1758
ilpd	4	512	0.0007	0.0059	0.0532	0.0094
tokyo1	6	1024	0.0029	0.1254	0.0056	0.0734

Appendix

Table 20: Hyperparameters GRANDE (Part 1). We report the hyperparameters for GRANDE based on the extensive HPO with 250 trials.

	dropout	selected_variables	data_fraction	focal_factor	cosine_decay_steps
dresses-sales	0.25	0.7996	0.9779	0	0.0
climate-simulation-crashes	0.00	0.6103	0.8956	0	1000.0
cylinder-bands	0.25	0.5309	0.8825	0	1000.0
wdbc	0.50	0.8941	0.8480	0	0.0
ilpd	0.50	0.6839	0.9315	3	1000.0
tokyo1	0.50	0.5849	0.9009	0	1000.0

Appendix

Table 21: Hyperparameters GRANDE (Part 2). We report the hyperparameters for GRANDE based on the extensive HPO with 250 trials.

	learning_rate	max_depth	reg_alpha	reg_lambda
dresses-sales	0.1032	3	0.0000	0.0000
climate-simulation-crashes	0.0356	11	0.5605	0.0000
cylinder-bands	0.2172	11	0.0002	0.0057
wdbc	0.2640	2	0.0007	0.0000
ilpd	0.0251	4	0.3198	0.0000
tokyo1	0.0293	3	0.2910	0.3194

Appendix

Table 22: Hyperparameters XGBoost. We report the hyperparameters for GRANDE based on the extensive HPO with 250 trials.

	learning_rate	max_depth	l2_leaf_reg
dresses-sales	0.0675	3	19.8219
climate-simulation-crashes	0.0141	2	19.6955
cylinder-bands	0.0716	11	19.6932
wdbc	0.1339	3	0.7173
ilpd	0.0351	4	5.0922
tokyo1	0.0228	5	0.5016

Appendix

Table 23: Hyperparameters CatBoost. We report the hyperparameters for GRANDE based on the extensive HPO with 250 trials.

	num_layers	total_tree_count	tree_depth
dresses-sales	2	2048	6
climate-simulation-crashes	2	1024	8
cylinder-bands	2	1024	8
wdbc	2	2048	6
ilpd	4	2048	8
tokyo1	4	1024	8

Appendix

Table 24: Hyperparameters NODE. We report the hyperparameters for GRANDE based on the grid suggested by the authors Popov et al., 2020 .

	CP	AB	LL	MC-C	PD-C
SYMPOL (ours)	500	- 0 84	- 0 85	- 58	- 0 502
D-SDT	11	-427	-396	-0	-1137
SA-DT (d=5)	295	-102	-348	-0 0	-1467
SA-DT (d=8)	223	- 0 99	-367	-0 2	-1526
MLP	500	- 0 78	- 208	-0 0	- 0 202
SDT	500	- 0 85	-159	-0 0	- 0 201

Appendix

Table 1: A2C Control Performance. We report the average undiscounted cumulative test reward over 25 random trials. The best interpretable method, and methods not statistically different, are marked bold.

	MLP		SDT		SYMPOL (ours)		SA-DT (d=5)		SA-DT (d=8)		D-SDT
	A2C	PPO	A2C	PPO	A2C	PPO	A2C	PPO	A2C	PPO	A2C	PPO
CP	500	500	500	500	500	500	295	446	223	476	11	128
AB	-78	-72	-85	-77	-84	-80	-102	-97	-99	-75	-427	-205
LL	208	241	-159	-124	-85	-57	-348	-197	-367	-150	-396	-221
MC-C	0	95	0	-4	58	94	0	97	-2	96	0	-10
PD-C	-202	-191	-201	-310	-502	-323	-1467	-1251	-1526	-854	-1137	-1343

Appendix

Table 2: A2C Control Performance Comparison. We report the average undiscounted cumulative test reward over 25 random trials, comparing A2C with PPO using optimized hyperparameters. A number is marked bold if the performance achieved with the underlying RL algorithm (PPO or A2C) is significantly better or not statistically different from the best result.

	MLP		SDT		SYMPOL (ours)		SA-DT (d=5)		SA-DT (d=8)		D-SDT
	valid	test	valid	test	valid	test	valid	test	valid	test	valid	test
CP	500	500	500	500	500	500	500	446	500	476	500	128
AB	-71	-72	-89	-77	-79	-80	-71	-97	-71	-75	-89	-205
LL	256	241	-91	-124	-9	-57	256	-197	256	-150	-91	-221
MC-C	95	95	-4	-4	87	94	95	97	95	96	-4	-10
PD-C	-169	-191	-295	-310	-305	-323	-169	-1251	-169	-854	-295	-1343

Appendix

Table 3: Information Loss (Comparison) . We report the validation reward of the trained model and the test reward of the applied model.

	MLP	SDT	SYMPOL (ours)	SA-DT (d=5)	SA-DT (d=8)	D-SDT
CP	0.000	0.000	0.000	0.632	1.214	4.075
AB	0.035	-0.630	0.104	0.728	0.338	0.982
LL	0.341	0.750	0.370	4.776	8.155	2.254
MC-C	-0.042	-0.002	-1.035	-2.011	-1.172	0.745
PD-C	1.195	0.081	0.468	13.120	4.101	7.573
Mean $\downarrow$	0.306	0.040	-0.019	3.449	2.527	3.126

Appendix

Table 4: Information Loss (Cohen’s D) . We calculated Cohen’s D to measure effect size between the validation reward of the trained model and the test reward of the applied model. Typically, values

>0.5

are considered a medium and values

>0.8

a large effect. positive effects that are at least medium are marked as bold.

	CP	AB	LL	MC-C	PD-C
SYMPOL (ours)	500	- 0 80	- 0 57	- 94	- 0 323
D-SDT	128	-205	-221	-10	-1343
SA-DT (d=5)	446	-97	-197	- 97	-1251
SA-DT (d=8)	476	- 0 75	-150	- 96	- 0 854
VIPER (d=5)	457	- 0 77	-200	-	-
VIPER (d=8)	480	- 0 75	-169	-	-

Appendix

Table 5: Control Performance. We report the average undiscounted cumulative test reward over 25 random trials. The best interpretable method, and methods not statistically different, are marked bold. Please note that VIPER cannot be applied to continuous environments.

	E-R	DK	LG-5	LG-7	DS
SYMPOL (ours)	0.964	0.959	0.951	0.953	0.939
D-SDT	0.662	0.654	0.262	0.381	0.932
SA-DT (d=5)	0.583	0.958	0.951	0.458	0.952
SA-DT (d=8)	0.845	0.961	0.951	0.799	0.954
VIPER (d=5)	0.651	0.958	0.948	0.456	0.954
VIPER (d=8)	0.845	0.963	0.948	0.801	0.954

Appendix

Table 6: MiniGrid Performance. We report the average undiscounted cumulative test reward over 25 random trials. The best interpretable method, and methods not statistically different, are marked bold.

	SYMPOL (ours)	D-SDT	SA-DT (d=5)	SA-DT (d=8)
CP	39.4	14.2	61.8	315.0
AB	78.6	17.0	56.5	173.0
LL	55.0	19.8	59.8	270.2
MC-C	23.4	0 3.0	61.0	311.8
PD-C	56.2	28.6	62.2	388.2
Mean $\downarrow$	50.5	16.5	60.3	291.6

Appendix

Table 7: Tree Size . We report the average size of the learned DT for each environment.

Figure 1: Exemplary large CartPole DT. This figure visualizes a larger tree with

59

nodes learned by SYMPOL on the CartPole environment.

Figure 2: Exemplary SDT for CartPole. This figure visualizes a soft / differentiable DT learned on CartPole. The tree involves oblique decisions involving multiple features at each split. Additionally, there is no hard decision on which path is selected, but multiple paths are taken with an associated probability. The final prediction is obtained by weighting the leaf outputs with the corresponding path probability.

Figure 3: Exemplary SDT for MountainCar. This figure visualizes a soft / differentiable DT learned on MountainCar. The tree involves oblique decisions involving multiple features at each split. Additionally, there is no hard decision on which path is selected, but multiple paths are taken with an associated probability. The final prediction is obtained by weighting the leaf outputs with the corresponding path probability.

Agent Type	CP	AB	LL	MC-C	PD-C	Normalized Mean ( $\uparrow$ )
SYMPOL	500.0	- 0 79.9	- 0 57.4	94.3	- 0 323.3	0.988
w/o separate architecture	135.6	-196.4	-276.8	-552.4	-1219.4	0.080
w/o dynamic rollout	456.1	- 0 92.0	-178.2	-144.1	- 0 434.4	0.598
w/o batch size adjustment	498.8	- 0 81.7	-320.7	-1818.8	- 0 434.4	0.372
w/o adamW	416.1	- 0 78.3	- 0 97.3	0.0	- 0 393.5	0.865

Appendix

Table 8: Ablation Study . We report the average test performance over a total of 25 random trials. This normalized performance consists in normalizing each reward between 0 and 1 via an affine renormalization between the top- and worse-performing models. Instead of the worse-performing model, we use the 20% test reward quantile to account for outliers.

	SYMPOL (ours)	SDT	MLP
CP	28.8	23.9	25.2
AB	35.5	37.7	33.8
MC-C	23.4	19.4	18.4
PD-C	28.7	28.2	18.5
Mean $\downarrow$	29.1	27.3	24.0
LL	402.3	394.0	405.6

Appendix

Table 9: Runtime. We report the average runtime over 25 trials. One trial spans 1mio timesteps for each environment. We excluded LL from the mean runtime calculation, as this is the only non-vectorized environment. To provide a fair comparison of different methods, we aligned the step and batch size.

Panel of Figure 6 — Figure 6: DistShift SYMPOL. This figure visualizes the path taken by the SYMPOL agent trained on the basic DistShift environment (see Figure 12 in the main part or tree_function(obs) defined below) from left to right and top to bottom. The agent follows the wall and reaches the goal at the top right corner.

Panel of Figure 7 — Figure 7: DistShift (Domain Randomization) SYMPOL Example 1. This figure visualizes the path taken by the SYMPOL agent trained on the basic DistShift environment (see Figure 12 in the main part or tree_function(obs) defined below) from left to right and top to bottom. The agent follows the wall gets stuck by the lava.

Panel of Figure 9 — Figure 9: DistShift (Domain Randomization) SYMPOL Example 2. This figure visualizes the path taken by the SYMPOL agent trained on the basic DistShift environment (see Figure 14 in the main part or tree_function(obs) defined below) from left to right and top to bottom. The agent follows the wall until there is no empty space on the left. Instead of an empty space there is the goal, but instead of walking into the goal, the agent surpasses it and again gets stuck at the lava.

Panel of Figure 10 — Figure 10: DistShift (Domain Randomization) SYMPOL (Retrained) Example 2. This figure visualizes the path taken by the SYMPOL agent trained on the randomized DistShift environment (see Figure 14 in the main part or tree_function_retrained(obs) defined below) from left to right and top to bottom. The agent avoids the lava, identifies the goal, and walks into the goal.

hyperparameter	values
learning_rate_actor_weights	[0.0001, 0.1]
learning_rate_actor_split_values	[0.0001, 0.05]
learning_rate_actor_split_idx_array	[0.0001, 0.1]
learning_rate_actor_leaf_array	[0.0001, 0.05]
learning_rate_actor_log_std	[0.0001, 0.1]
learning_rate_critic	[0.0001, 0.01]

Appendix

Table 10: HPO Grid SYMPOL

hyperparameter	values
neurons_per_layer	[16, 256]
num_layers	[1, 3]
learning_rate_actor	[0.0001, 0.01]
learning_rate_critic	[0.0001, 0.01]
minibatch_size	{64, 128, 256, 512}
n_update_epochs	[1, 10]

Appendix

Table 11: HPO Grid MLP

hyperparameter	values
critic	{’MLP’, ’SDT’}
depth	[4, 8]
temperature	{0.01, 0.05, 0.1, 0.5, 1.0}
learning_rate_actor	[0.0001, 0.01]
learning_rate_critic	[0.0001, 0.01]
minibatch_size	{64, 128, 256, 512}

Appendix

Table 12: HPO Grid SDT

	CP	AB	LL	MC-C	PD-C
ent_coef	0.200	0.000	0.000	0.500	0.100
gae_lambda	0.950	0.950	0.900	0.990	0.800
gamma	0.990	0.990	0.999	0.999	0.999
learning_rate_actor_weights	0.048	0.003	0.072	0.000	0.022
learning_rate_actor_split_values	0.000	0.000	0.001	0.000	0.000
learning_rate_actor_split_idx_array	0.026	0.052	0.010	0.000	0.010

Appendix

Table 13: Best Hyperparameters SYMPOL (Control)

	E-R	DK	LG-5	LG-7	DS
ent_coef	0.100	0.200	0.100	0.100	0.500
gae_lambda	0.990	0.950	0.900	0.900	0.950
gamma	0.900	0.990	0.950	0.990	0.999
learning_rate_actor_weights	0.063	0.042	0.055	0.001	0.036
learning_rate_actor_split_values	0.001	0.001	0.006	0.001	0.000
learning_rate_actor_split_idx_array	0.001	0.001	0.012	0.001	0.009

Appendix

Table 14: Best Hyperparameters SYMPOL (MiniGrid)

	CP	AB	LL	MC-C	PD-C
adamW	False	False	False	False	False
ent_coef	0.200	0.000	0.100	0.100	0.100
gae_lambda	0.900	0.900	0.900	0.950	0.950
gamma	0.999	0.990	0.999	0.999	0.990
learning_rate_actor	0.001	0.000	0.001	0.005	0.000
learning_rate_critic	0.003	0.005	0.003	0.001	0.002

Appendix

Table 15: Best Hyperparameters MLP (Control)

	E-R	DK	LG-5	LG-7	DS
adamW	False	False	False	False	False
ent_coef	0.100	0.100	0.100	0.100	0.100
gae_lambda	0.950	0.900	0.950	0.950	0.990
gamma	0.990	0.900	0.990	0.900	0.990
learning_rate_actor	0.000	0.000	0.002	0.000	0.000
learning_rate_critic	0.001	0.000	0.003	0.001	0.001

Appendix

Table 16: Best Hyperparameters MLP (MiniGrid)

	CP	AB	LL	MC-C	PD-C
adamW	False	False	False	False	False
critic	mlp	mlp	mlp	mlp	mlp
depth	7	6	8	7	7
ent_coef	0.000	0.100	0.200	0.000	0.200
gae_lambda	0.950	0.950	0.990	0.900	0.900
gamma	0.990	0.990	0.999	0.990	0.900

Appendix

Table 17: Best Hyperparameters SDT (Control)

	E-R	DK	LG-5	LG-7	DS
adamW	False	False	False	False	False
critic	sdt	mlp	sdt	sdt	sdt
depth	7	6	7	8	7
ent_coef	0.100	0.100	0.200	0.100	0.100
gae_lambda	0.900	0.950	0.990	0.950	0.900
gamma	0.990	0.900	0.999	0.950	0.950

Appendix

Table 18: Best Hyperparameters SDT (MiniGrid)

Straight-Through Estimator

See all 11 papers

May 8, 2026

Approximation-Free Differentiable Oblique Decision Trees

Decision Trees (DTs) are widely used in safety-critical domains such as medical diagnosis, valued for their interpretability and effectiveness on tabular data. However, training accurate oblique DTs is challenging due to complex optimization landscapes and overfitting risks, particularly in regression. Recent advances have introduced differentiable formulations that enable gradient-based training and joint optimization of decision boundaries and leaf regressors. Yet, existing approaches typically rely on approximations, either through probabilistic softening of boundaries (soft DTs) or quantized gradients such as the Straight-Through Estimator (STE). To overcome these limitations, we propose DTSemNet, a novel, semantically equivalent, and invertible representation of hard oblique DTs as neural networks. DTSemNet enables end-to-end training with standard gradient descent, eliminating the need for approximations in both classification and regression. While classification aligns naturally with this formulation, regression remains challenging due to the joint optimization of internal nodes and leaf regressors. To address this, we analyze the limitations of STE and introduce an annealed Top-k method that provides accurate gradient signals without approximation. Extensive experiments on classification and regression benchmarks show that DTSemNet-trained oblique DTs outperform state-of-the-art differentiable DTs. Furthermore, we demonstrate that DTSemNet can serve as programmatic DT policies in reinforcement learning environments, thereby broadening their applicability.

Subrat Prasad Panda, Blaise Genest, Arvind Easwaran

College of Computing and Data Science Nanyang Technological University Singapore

Interpretable ML Tabular ML Differentiable Optimization

Ask PDF

Sep 1, 2026

Learning Sparse Decision Trees via Transformer Variational Auto-Encoders

Decision trees are among the most widely used models in machine learning, largely due to their transparent decision logic, making them well-suited for high-stakes decision-making contexts. However, most existing learning algorithms focus on predictive performance, overlooking the joint optimization of other desirable properties, such as structural sparsity. In this work we propose TREVIS, an approach for learning decision trees with respect to complex objectives, based on the exploration of the latent space of a Tree Transformer Variational Auto-Encoder (TTVAE). By mapping decision trees onto latent representations, TREVIS replaces the discrete search space with a continuous one, enabling gradient-based optimization via a differentiable surrogate model. We experiment with TREVIS for learning decision trees that jointly optimize predictive performance and sparsity. Results show that TREVIS discovers decision trees matching the predictive performance of existing near-optimal algorithms while improving their structural sparsity.

Giacomo Fidone, Alessio Cascione, Riccardo Guidotti

University of Pisa · ISTI-CNR

Variational Autoencoders Structured Sparsity Decision Tree Learning

Ask PDF

Jun 30, 2026

Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again

Recent work has shown that well-optimized individual decision trees can match complex black box models in some settings, primarily in noisy domains. For the remaining settings, however, complex ensembled compositions of trees often achieve higher accuracy at the cost of interpretability, leaving practitioners with difficult modeling decisions along an accuracy-interpretability tradeoff. Ideally, we would like to classify as much of the data as possible with one or a small number of trees, achieving interpretability for most samples while maintaining state-of-the-art accuracy. We introduce Multistage Defer Trees: a sequence of sparse decision trees that each make predictions for most samples, while deferring a small proportion to the next tree in the sequence or, ultimately, to a black box. We demonstrate that we can train this model class to match the performance of complex tree-based ensembles while routing most samples through only one or a small number of sparse decision trees. We discuss a range of techniques for training these models while maintaining simplicity. Our method expands the accuracy--interpretability frontier in settings where single-tree methods remain insufficient, demonstrating that even when complex models are necessary, they need not be fully opaque.

Zakk Heile, Hayden McTavish, Margo Seltzer +1

Department of Computer Science · Duke University · Durham, USA +2

Ensemble Learning Learning to Defer Interpretable ML Decision Tree Learning Classification

Ask PDF

Abstract

Straight-Through Estimator

Explore similar work

Approximation-Free Differentiable Oblique Decision Trees

Learning Sparse Decision Trees via Transformer Variational Auto-Encoders

Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again