--- title: "Optimal Decision Tree Policies for Markov Decision Processes" authors: - "Daniël Vos" - "Sicco Verwer" doi: "10.24963/ijcai.2023/606" url: "https://ijcai.org/proceedings/2023/606" pdf: "https://ijcai.org/proceedings/2023/0606.pdf" venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence" year: 2023 pages: "5457-5465" track: "Main Track" keywords: - "Planning and Scheduling: PS: Markov decisions processes" - "Search: S: Combinatorial search and optimisation" - "Machine Learning: ML: Explainable/Interpretable machine learning" --- # Optimal Decision Tree Policies for Markov Decision Processes Daniël Vos, Sicco Verwer *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 5457-5465. DOI: [10.24963/ijcai.2023/606](https://doi.org/10.24963/ijcai.2023/606) ## Abstract Interpretability of reinforcement learning policies is essential for many real-world tasks but learning such interpretable policies is a hard problem. Particularly, rule-based policies such as decision trees and rules lists are difficult to optimize due to their non-differentiability. While existing techniques can learn verifiable decision tree policies, there is no guarantee that the learners generate a policy that performs optimally. In this work, we study the optimization of size-limited decision trees for Markov Decision Processes (MPDs) and propose OMDTs: Optimal MDP Decision Trees. Given a user-defined size limit and MDP formulation, OMDT directly maximizes the expected discounted return for the decision tree using Mixed-Integer Linear Programming. By training optimal tree policies for different MDPs we empirically study the optimality gap for existing imitation learning techniques and find that they perform sub-optimally. We show that this is due to an inherent shortcoming of imitation learning, namely that complex policies cannot be represented using size-limited trees. In such cases, it is better to directly optimize the tree for expected return. While there is generally a trade-off between the performance and interpretability of machine learning models, we find that on small MDPs, depth 3 OMDTs often perform close to optimally. ## Full text ## 1 Introduction Advances in reinforcement learning using function approximation have allowed us to train powerful agents for complex problems such as the games of Go and Atari [Schrittwieser et al., 2020]. Policies learned using function approximation often use neural networks, making them impossible for humans to understand. Therefore reinforcement learning is severely limited for applications with high-stakes decisions where the user has to trust the learned policy. Recent work has focused on explaining opaque models such as neural networks by attributing prediction importance to the input features [Ribeiro et al., 2016; Lundberg and Lee, 2017]. However, these explanation methods cannot capture the full complexity of their models, which can mislead users when attempting to understand the predictions [Rudin, 2019]. Concurrently, there has been much work on interpretable machine learning in which the model learned is limited in complexity to the extent that humans can understand the complete model. Particularly decision trees have received much attention as they are simple models that are capable of modeling non-linear behavior [Lipton, 2018]. Decision trees are difficult to optimize as they are nondifferentiable and discontinuous. Previous works have used different strategies to overcome the hardness of optimizing trees: using assumptions or relaxations to make the trees differentiable [Gupta et al., 2015; Silva et al., 2020; Likmeta et al., 2020], reformulating the MDP into a metaMDP that exclusively models decision tree policies [Topin et al., 2021] or extracting trees from a complex teacher [Bastani et al., 2018]. While these methods are increasingly successful in training performant trees they do not offer guarantees on this performance. Our work takes a first step at bridging the gap between the fields of optimal decision trees and reinforcement learning. Existing formulations for optimal decision trees assume a fixed training set with independent samples. This cannot be used in a dynamic setting where actions taken in one state influence the best actions in others. Instead, we formulate the problem of solving a Markov Decision Process (MDP) using a policy represented by a size-limited decision tree (see Figure 1) in a single MILP. We link the predictions of the decision tree policy to the state-action frequencies in the dual linear program for solving MDPs. The dual allows us to reason over policies explicitly, which results in a more efficient formulation. Our formulation for Optimal MDP Decision Trees, OMDTs, optimizes a decision tree policy for a given MDP and a tree size limit. OMDT produces increasingly performant policies as runtime progresses and eventually proves the optimality of its policy under the size constraint. Existing methods for training size-limited decision trees in reinforcement learning such as VIPER [Bastani et al., 2018] make use of imitation learning, where a student tries to learn from a powerful teacher policy. We compare the performance of OMDT and VIPER on a variety of MDPs. Interestingly, we show that, when training interpretable size-limited trees, imitation learning performs significantly worse as capacity of the learned decision tree is wasted on parts of the state space that are never reached by the policy. Moreover, VIPER cannot prove optimality even if it identifies the optimal solution. Regarding the performance-interpretability trade-off, we show that decision trees of 7 decision nodes are enough to perform close to unrestricted optimal policies in 8 out of 13 environments. Such trees are orders of magnitude smaller than size-unrestricted trees created by methods that replicate the unrestricted policy such as dtcontrol [Ashok et al., 2020]. ## 2 Background ## 2.1 Decision Trees Decision trees [Breiman et al., 1984; Quinlan, 1986] are simple models that execute a series of comparisons between a feature value and a threshold in the nodes to arrive at a leaf node that contains the prediction value. Due to their simple descriptions, size-limited decision trees are easy to understand for humans [Molnar, 2020]. Particularly, size-limited decision trees admit simulatability [Lipton, 2018]: humans can use the model to make predictions by hand in reasonable time and decomposability: humans can understand each individual aspect of the model. The method proposed in this paper, OMDT, also offers algorithmic transparency: we can trust the learning algorithm to produce models that fulfill certain qualities such as global optimality. Therefore decision trees are an attractive model class when interpretable policies are required. ## 2.2 Markov Decision Processes Markov Decision Processes (MDPs) [Bellman, 1957] are the processes underlying reinforcement learning problems. An MDP models a decision-making process in a stochastic environment where the agent has some control over the state transitions. An MDP can be described by a tuple ⟨S,A, P,R⟩, where S contains all states, A the set of actions an agent can take, Ps,s′ ,a the probabilities of transitioning from state s to state s′ when taking action a, and Rs,s′ ,a the reward the agent receives when going from state s to state s′ under action a. When solving an MDP, we want to find a policy π : S → A such that, when executing its actions, the expected sum of rewards (the return) is maximized. In this work we define policies (w.l.o.g.) as a mapping from states and actions to an indicator for whether or not action a is taken in state s: π : S × A → {0, 1}. Figure 1: Depth 2 OMDT on the stochastic Frozenlake 4x4 environment. OMDT proves that no better depth 2 decision tree policy exists (discounted return 0.37 with γ = 0.99). ![Image](https://ijcai.org/proceedings/2023/fulltext/606/image_000000_c4757c0ec39b88d93cdb6ac3707e8723dc39065264896dfb0455f87f883e6496.png) ## Value Iteration When solving MDPs we generally discount future rewards in each step by a user-defined value of 0 < γ < 1 to ensure that the optimal policy will generate a finite return. The most common approach for optimally solving MDPs is by using one of many dynamic programming variants. In this work, we focus on value iteration. Value iteration finds a value Vs for each state s that holds the expected discounted return for taking optimal greedy actions starting from that state. These values can be found by iteratively updating Vs until the Bellman equation [Bellman, 1957] is approximately satisfied. We will refer to this optimal solution found with value iteration as the unrestricted optimal solution as the computed policy can be arbitrarily complex. ## 3 RelatedWork ## 3.1 Learning Decision Tree Policies Decision trees have appeared at various parts of the reinforcement learning pipeline [Glanois et al., 2021] for example in modeling the Q-value function or in modeling the policy. In this work, we are interested in modeling the policy with a decision tree as this gives us an interpretable model that we can directly use at test time. Decision trees make predictions using hard comparisons between a single feature value and a threshold. The learned models can be discontinuous and non-differentiable, which makes optimization with gradients challenging. One line of research focuses on overcoming the non-differentiability of decision trees to allow for the use of gradient-based optimization methods. Gupta et al. [2015] train decision trees that contain linear models in their leaves that can be optimized with gradients but this results in models that are hard to interpret. Silva et al. [2020] first relax the constraints that decision nodes select one feature, that leaves predict one value, and that thresholds are hard step functions. Such relaxed trees are differentiable and can be trained with policy gradient methods. By discretizing the relaxed tree they end up with an interpretable model that approximates the relaxed model. However, the relaxed tree can get stuck in local minima and the discretized tree offers no performance guarantees. Likmeta et al. [2020] consider decision tree policies for autonomous driving tasks. To make the decision tree parameters easily optimizable, they fix the tree structure along with the features used in the decision nodes. By learning a differentiable hyper-policy over decision tree policies they are then able to approximately optimize the models with gradient descent. With Iterative Bounding MDPs, Topin et al. [2021] reformulate the underlying MDP into one where the agent implicitly learns a decision tree policy. The method can be thought of as a tree agent learning to take actions that gather information and a leaf agent learning to take actions that work well given the gathered information of the tree agent. By reformulating the MDP, its decision tree policy can be optimized using differentiable function approximators and gradient-based optimizers. In a separate line of work, the goal is to represent a specific, usually optimal, policy as a decision tree that is unbounded in size. These techniques have been developed for policies with a single goal state [Br´azdil et al., 2015] and as a tool for general controllers [Ashok et al., 2020]: dtcontrol. ## Imitation Learning (VIPER) Instead of directly optimizing a decision tree, one can also try to extract a decision tree policy from a more complex teacher policy using imitation learning. These imitation learning algorithms turn reinforcement learning into a supervised learning problem for which we have successful decision tree learning algorithms [Breiman et al., 1984; Quinlan, 1986]. DAGGER [Ross et al., 2011] (dataset aggregation) is an algorithm that iteratively collects traces from the environment using its current policy and trains a supervised model on the union of the current and previous traces. Since DAGGER only uses information on the predicted action of the teacher policy, it ignores extra information on Q-values that modern Q-learning algorithms provide. VIPER [Bastani et al., 2018] focuses on learning decision trees and improves on DAGGER by including Q-value information into the supervised learning objective. While VIPER generates significantly smaller decision trees than DAGGER, we will show that these trees are not yet optimal with respect to the tradeoff in size and performance. ## 3.2 Optimal Decision Trees The standard algorithms for training decision trees in supervised learning are greedy heuristics and can learn trees that perform arbitrarily poorly [Kearns, 1996]. Therefore in recent years there has been increasing interest in the design of algorithms that train decision trees to perform optimally. Early works formulated training decision trees for classification and regression and used methods such as dynamic programming to find optimal decision trees [Nijssen and Fromont, 2007]. Mixed-Integer Linear Programming based formulations [Bertsimas and Dunn, 2017; Verwer and Zhang, 2017] have since become popular. These methods are flexible and have been extended to optimize performance under fairness constraints [Aghaei et al., 2019] or directly optimize adversarial robustness [Vos and Verwer, 2022]. Generally, the size of the tree is limited to provide regularization and aid interpretability, then the solver is tasked with finding a decision tree that maximizes training performance given the size limits. The field has since worked on increasingly efficient optimization techniques using a variety of methods such as MILP [Verwer and Zhang, 2019], dynamic programming [Demirovi´c et al., 2020; Lin et al., 2020], constraint programming [Verhaeghe et al., 2020], branch-andbound search [Aglin et al., 2020; Aglin et al., 2021] and Boolean (maximum) satisfiability [Narodytska et al., 2018; Hu et al., 2020; Schidler and Szeider, 2021]. ## 4 OMDT: Optimal MDP Decision Trees As a first step in bridging the gap between optimal decision trees for supervised and reinforcement learning, we introduce OMDTs: Optimal MDP Decision Trees. OMDT is a Mixed-Integer Linear Programming formulation that encodes the problem of identifying a decision tree policy that achieves maximum discounted return given a user-defined MDP and tree size limit. Our formulation can be solved using one of many available solvers, in this work we use the state-of-theart solver Gurobi 1 . ![Image](https://ijcai.org/proceedings/2023/fulltext/606/image_000001_d94cb55375f4dfb1528fb12a7d84711894a808dd7067fb6e50f8a9510fd57843.png) Figure 2: Overview of OMDT's formulation. We maximize the discounted return in an MDP under the constraint that the policy is represented by a size-limited decision tree. ![Image](https://ijcai.org/proceedings/2023/fulltext/606/image_000002_0759479fff12dff50c2ec5d6a9eaaaf952a081e54e8ad47bdbee7308dfa62739.png) Intuitively the OMDT formulation consists of two parts: a (dual) linear programming formulation for solving MDPs and a set of constraints that limits the set of feasible policies to decision trees. Figure 2 summarizes OMDT's formulation in natural language. All the notation used in OMDT is summarized in Table 1. ## 4.1 Constraints It is well known that MDPs can be solved using linear programming, the standard linear program is [Puterman, 2014]: It is not easy to efficiently add constraints to this formulation to enforce the policies to be size-limited decision trees because it reasons abstractly over policies, i.e. by reasoning over the policy's state values. To create a formulation for decision tree policies, we resort to the standard dual program: [1 https://www.gurobi.com/](https://www.gurobi.com/) This program uses a measure xs,a of how often the agent takes action a in state s. This allows us to add efficient constraints that control the policy of the agent. Intuitively the program maximizes the rewards ∑s′ Ps,s′ ,aRs,s′ ,a weighted by this xs,a. The constraints enforce that the frequency by which a state is exited is equal to the frequency that the agent is initialized in the state p0(s) or returns to it following the discounted transition probabilities γPs,s′ ,a. To enforce the policy to be a size-limited decision tree we will later constrain the xs,a values to only be non-zero when the agent is supposed to take action a in state s according to a tree policy. We will first introduce the variables and constraints required to model the decision tree constraints. ## Modeling Decision Nodes Our decision tree formulation is roughly based on OCT [Bertsimas and Dunn, 2017] and ROCT [Vos and Verwer, 2022], MILP formulations for optimal (OCT) and robust (ROCT) classification trees. In these formulations, the shape of the decision tree is fixed. Like ROCT, we describe a decision node m by binary threshold variables bm,j,k, indicating whether the kth threshold of feature j is chosen. 2 Unlike ROCT, we only allow one of these variables to be true over all features and possible thresholds: We follow paths through the tree to map observations to leaves. In each node mwe decide the direction ds,m that the observation of state s takes (left=0 or right=1 of the threshold k). ROCT uses two variables per state-node pair to model directions ds,m to account for perturbations in the observations. Since we are optimizing for an MDP without uncertainty in the observations we only require one variable ds,m per statenode pair. We further improve over ROCT by determining ds,m using only one constraint per state-node pair instead of a separate constraint per state-node-feature triple. For this, we pre-compute a function side(s, j, k) which indicates for each feature-threshold pair (j, k) and every observation s the side of k that s is on for feature j (left=0 or right=1), i.e. whether Xsj > k holds. This formulation is not limited to the predicates '≤' or '>' however and can be easily extended to other predicates in the pre-computation of side(s, j, k). The following then forces the direction ds,m to be equal to the direction of the indicated threshold: 2 In practice, the possible values for threshold k depends on the chosen feature j. We do not model this for convenience of notation. The variables ds,m represent the direction of an observation's path at a decision node. Together, the d variables allow us to follow an observation's path through the tree which we use to identify the leaf that it reaches. Important in this formulation, compared to existing binary encodings, is that it requires no big-M constraints to describe these paths. This makes the relaxation stronger and therefore the solver gives much better bounds than using the big-M style formulations from ROCT. ## Modeling Policy Actions Decision leaves only have one set of binary decision variables: ct,a encoding whether or not leaf t predicts action a. We want each leaf to select exactly one action: As mentioned before we can follow an observation's path through the tree by using their ds,m path variables. One can linearize an implication of a conjunction of binary variables as follows: If an observation reaches leaf t and the leaf predicts action a then we want to force the policy πs,a to take that action in the associated state s. Using the aforementioned equivalence we add the constraint: This constraint forces the agent to take the action indicated by the leaf. To prevent the agent from taking other actions that were not indicated we force it to only take a single action in each state (giving a deterministic policy): Now we have indicators πs,a that mark what action is taken by the agent. To link this back to the MDP linear programming formulation that we use to optimize the policy, we set the xs,a variables. We need to set xs,a = 0 if πs,a = 0, else xs,a should be unbounded. We encode this using a big-M formulation: M should be chosen as small as possible, but larger or equal to the largest value that xs,a can take. We use the fact that we are optimizing the MDP using discount factor γ to compute an upper bound on xs,a and set M = 1 1-γ , proof is given in the appendix. ## 4.2 Complete Formulation The runtime of MILP solvers grows worst-case exponentially with respect to formulation size so it is important to limit the scale of the formulation. The number of variables in our formulation grows with O(|S||J||TD|+|A||TL|+|S||A|) which | Name | Kind | Description | |-----------------|---------------|---------------------------------------------------------------------------------| | bm,j,k | bin. bin. | Tree uses feat. j and threshold k in node m | | ct,a | | Tree selects action a in leaf t | | ds,m | bin. | Observation of s goes left / right in node m | | πs,a | bin. | Policy takes action a in state s | | xs,a | cont. | Frequency of action a taken in state s | | Ps,s′ ,a | const. | Probability of transition s→s′ with action a | | Rs,s′ ,a | const. | Reward for transition s→s′ with action a | | p0(s) | const. | Probability of starting in state s | | γ | const. | Discount factor | | Xij side(s,j,k) | const. const. | Feature j's value of observation i Side state s is on for thresh. k and feat. j | a ∈ A set Set of actions in MDP s ∈ S set Set of states in MDP i=1..|S| set Observation and state indices j ∈ J set Set of feature indices k = 1..K set Indices of all possible feature thresholds m ∈ TD set Set of decision nodes in the tree t ∈ TL set Set of leaves in the tree A(t) set Set of ancestors of leaf t Al(t) set ... that have t in their left path Ar (t) set ... that have t in their right path Table 1: Summary of notation used in OMDT. follows from their indices in Table 1. The number of constraints grows with the order O(|S||TD|+|S||A||TL|) as it is dominated by the constraints that determine ds,m at each node (Equation 4) and constraints that force πs,a according to the tree (Equation 6). We summarize OMDT below: s.t. ## 5 Results We present experiments comparing the performance of OMDTs with VIPER and dtcontrol. Viper uses imitation learning to extract a size-limited decision tree from a teacher policy and dtcontrol learns an unrestricted tree that exactly copies the teacher's behavior. To provide a fair comparison we have trained VIPER and dtcontrol with an unrestricted optimal teacher by first solving the MDP with value iteration and then extracting all Q values, both methods ran with default parameters. We also implemented and ran experiments on interpretable Differentiable Decision Trees [Silva et al., 2020] but excluded these models from our analysis as they did not outperform a random policy. The full code for OMDT and our experiments can be found on GitHub 3 . All of our experiments ran on a Linux machine with 16 Intel Xeon CPU cores and 72 GB of RAM total and used Gurobi 10.0.0 with default parameters. Each method ran on a single CPU core. ## 5.1 Environments For comparison we implemented 13 environments based on well-known MDPs from the literature, the sizes of these MDPs are given in Table 2. All MDPs were pre-processed such that states that are unreachable from the initial states are removed. We briefly describe the environments below but refer to the appendix for complete descriptions. In 3d navigation the agent controls a robot in a 5×5×5 world and attempts to reach from start to finish with each voxel having a chance to make the robot disappear. blackjack is a simplified version of the famous casino game where we assume an infinite-sized deck and only the actions 'skip' or 'hit'. frozenlake is a grid world where the agent attempts to go from start to finish without falling into holes, actions are stochastic so the agent will not always move in the intended direction (e.g. the action 'up' will only not send the agent 'down'). inventory management models a company that has to decide how many items to order to maximize profit while minimizing cost. system administrator refers to a computer network where computers randomly crash and an administrator has to decide which computer to reboot. A crashed computer has an increased probability of crashing a neighboring computer. tictactoe vs random is the well-known game of tic-tac-toe when played against an opponent that makes random moves. In tiger vs antelope the agent attempts to catch an antelope that randomly jumps away from the tiger in a grid world. traffic intersection describes a perpendicular intersection where traffic flows in at different rates and the operator decides when to switch the traffic lights. xor is an MDP constructed with states randomly distributed on a plain, the agent gets 1 reward for taking the action according to an XOR function and -1 for a mistake. The XOR problem is notoriously difficult for greedy decision tree learning algorithms. ## 5.2 Performance-Interpretability Trade-off It is often assumed that there is a trade-off in the performance and interpretability of machine learning models [Gunning and Aha, 2019], since interpretable models necessarily lack complexity but this assumption is not always true [Rudin, 2019]. We aim to answer whether the performance-interpretability trade-off occurs in a variety of MDPs by training size-limited decision trees and comparing their performance to the optimal solutions that were not restricted in complexity. We visualize the normalized return of depth 3 OMDTs and unrestricted dtcontrol trees in Figure 3. Returns were normalized such that 0 corresponds to a random policy and 1 to an optimal one. Since small deterministic decision tree policies are limited in the number of distinct actions an optimal tree can perform worse than a random policy. Experiments were repeated 3 times and runs were limited to 2 hours. We consider an OMDT optimal when the relative gap between its objective and bound is proven to be less than 0.01%. [3 https://github.com/tudelft-cda-lab/OMDT](https://github.com/tudelft-cda-lab/OMDT) Table 2: Comparison of depth 3 trees trained with VIPER and OMDT on 13 MDPs, experiments were repeated 3 times, means and standard errors are given. All runs were limited to 2 hours. OMDT solves some MDPs in 5 minutes but significantly improves when given 2 hours of runtime. While 2 hours are enough for OMDT to achieve greater or equal scores to VIPER in most MDPs, OMDT needs more time to outperform VIPER on the large tictactoe MDP. OMDT was able to identify the optimal size-limited tree and prove its optimality on 7 MDPs. | MDP | |S| | |A| | normalized return - VIPER | normalized return - OMDT 5 mins. | normalized return - OMDT 2 hrs. | MILP - vars. | MILP - constrs. | trees | runtime (s) - VIPER | runtime (s) - OMDT optimal | |--------------------|-----------------|-----------------|-----------------------------|------------------------------------|-----------------------------------|----------------|-------------------|---------|-----------------------|------------------------------| | 3d navigation | 125 | 6 | 1.00 ±.00 | .81 ±.10 | 1.00 ±.00 | 2,528 | 7,890 | 1014 | 2,090 ±55 | 315 ±89 | | blackjack | 533 | 2 | 1.00 ±.00 | 1.00 ±.00 | 1.00 ±.00 | 6,187 | 14,406 | 1014 | 2,248 ±27 | 408 ±85 | | frozenlake 4x4 | 16 | 4 | .67 ±.00 | .96 ±.00 | .96 ±.00 | 328 | 735 | 1010 | 74 ±3 | 2 ±0 | | frozenlake 8x8 | 64 | 4 | .83 ±.06 | .95 ±.00 | .95 ±.00 | 1,104 | 2,895 | 1013 | 178 ±5 | 98 ±30 | | frozenlake 12x12 | 144 | 4 | .19 ±.09 | .63 ±.03 | .68 ±.04 | 2,360 | 6,495 | 1014 | 196 ±38 | timeout | | inv. management | 101 | 100 | 1.00 ±.00 | .37 ±.37 | 1.00 ±.00 | 22,414 | 91,824 | 1030 | 2,254 ±86 | 2,533 ±540 | | sysadmin 1 | 256 | 9 | .88 ±.01 | .85 ±.01 | .92 ±.00 | 6,584 | 23,055 | 1014 | 2,265 ±37 | timeout | | sysadmin 2 | 256 | 9 | .59 ±.00 | .23 ±.06 | .58 ±.01 | 6,584 | 23,055 | 1014 | 2,257 ±7 | timeout | | sysadmin tree | 128 | 8 | .57 ±.04 | .48 ±.07 | .70 ±.09 | 3,106 | 10,383 | 1013 | 2,136 ±72 | timeout | | tictactoe vs rand. | 2,424 | 9 | .80 ±.01 | -.06 ±.00 | .43 ±.18 | 61,239 | 218,175 | 1020 | 21 ±3 | timeout | | tiger vs antelope | 626 | 5 | -.10 ±.02 | -.17 ±.19 | .52 ±.03 | 10,850 | 33,819 | 1015 | 490 ±243 | timeout | | traffic intersec. | 361 | 2 | .98 ±.00 | .99 ±.00 | 1.00 ±.00 | 4,127 | 9,762 | 1011 | 2,188 ±121 | 1,219 ±177 | | xor | 200 | 2 | .34 ±.06 | 1.00 ±.00 | 1.00 ±.00 | 5,016 | 5,415 | 1021 | 1,999 ±123 | 50 ±0 | While it is debatable what the precise size limits are for decision trees to be interpretable [Lipton, 2018] we use trees of depth 3 which implies that a tree has at most 8 leaves. Note that this also limits the number of distinct actions in the policy to 8. We find that in all environments, OMDTs of depth 3 improve on the performance of random policies, and in 8 out of 13 environments the policy gets close to optimal. Decision trees trained with dtcontrol always achieve the optimal normalized return of 1 since they exactly mimic the optimal policy. However, dtcontrol produces large trees that are not interpretable to humans. When run on 3d navigation for example, dtcontrol produces a tree of 68 decision nodes which is very complex for humans to understand. OMDT produces a tree of 7 decision nodes which performs equally well. Overall, our results demonstrate that for small environments there is no performance-interpretability trade-off: simple policies represented by size-limited trees perform approximately as well as the unrestricted optimal policy. ## 5.3 Direct Optimization versus Imitation Learning The above conclusion holds when the policy is learned to optimality under the constraint that it has to be a small tree, e.g., using OMDT. Techniques such as VIPER enforce the size constraint but aim to imitate the unrestricted optimal policy. We now show that this comes at a cost when the unrestricted policy is too complex to be represented using a small tree. Figure 3: (top) Normalized return and bounds for OMDT trees of depth 3, optimal policies score 1 while uniform random policies score 0. (bottom) Log of tree sizes for OMDT (maximum depth 3) and dtcontrol. Dtcontrol always produces an optimal policy but the trees are orders of magnitude larger than OMDT. ![Image](https://ijcai.org/proceedings/2023/fulltext/606/image_000003_cba1ac8bb7a6336bcb72d237bd65db19d98b1670d6e629ed68dea4f955e7b226.png) VIPER trains trees by imitating high Q values of the optimal policies while OMDT directly maximizes expected return. In Table 2 we list the normalized return (0 for random policies, 1 for optimal policies) for VIPER and OMDT with respectively 5 minutes and 2 hours of runtime. After 5 minutes OMDT improves performance over random policies but often needs more time to improve over VIPER. After 2 hours OMDT's policies win on 11 out of 13 environments. For instances with large state space such as tictactoe vs random OMDT needs more than 2 hours to improve over VIPER. Figure 4: Paths taken on 10,000 Frozenlake 12x12 runs. The agent starts at (0, 0) and attempts to reach the goal tile 'G' while avoiding holes. Actions are indicated by arrows and are somewhat stochastic, i.e. an action of 'up' will send the agent 'left', 'up', or 'right' (but never down) with equal probability. VIPER fails to produce a good policy because it spends capacity of its tree mimicking parts of the complex teacher policy that its simple student policy will never reach. OMDT achieves a greater success rate by directly optimizing a simple policy. ![Image](https://ijcai.org/proceedings/2023/fulltext/606/image_000004_e79ba75afc4517565097a8b08492e2a02c71ee8590de589607ea8fbfe00dfa27.png) ## Shortcomings of Imitation Learning Overall, given sufficient runtime, OMDT produces better policies than VIPER. This cannot be easily solved by giving VIPER more runtime but is an inherent problem of imitation learning. To illustrate this, we investigate the results on the frozenlake MDPs as Table 2 demonstrates that imitation learning can perform far from optimal in these environments. In theory, imitation learning performs optimally in the limit [Ross et al., 2011] but this result requires the student policy to be as expressive as the teacher policy. This is not the case for size-limited decision trees. When VIPER learns a policy for frozenlake 12x12 it tries to imitate a complex policy using a small tree that cannot represent all teacher policy actions. This results in VIPER spending capacity of its decision tree on parts of the state space that will never be reached under its student policy. In Figure 4 we visualize the paths that the agents took on 10,000 runs and indicate the policies with arrows. VIPER creates leaves that control action in the right section of the grid world (indicated in red). The optimal teacher policy often visits this section but the simple student does not. By directly optimizing a decision tree policy using OMDT, the policy spends its capacity on parts of the state space that it actually reaches. As a result, VIPER cannot prevent actions that send its agent into holes on the left part of the grid world (indicated in red). OMDT actively avoids these. ## 5.4 Runtime Runtime for solving Mixed-Integer Linear Programming formulations scales worst-case exponentially which makes it important to understand how solvers operate on complex formulations such as OMDT. We solved OMDTs for a depth of 3 for a maximum of 2 hours and display the results in Table 2. The table compares the runtimes of VIPER and solving OMDT to optimality. If the solver does not prove optimality within 2 hours we denote it as 'timeout'. We also denote the number of possible decision tree policies computed as: |TB|possible splits ×|TL||A| . It provides an estimate of howmany decision tree policies are possible and shows that enumerating trees with brute force is intractable. OMDT solves a simple environment such as Frozenlake 4x4 (16 states, 4 actions) to optimality within 2 seconds but runtime grows for larger environments such as inventory management (101 states, 100 actions) which took on average 2533 seconds. VIPER needs roughly 2250 seconds of runtime for every MDP and runs significantly faster on some MDPs. This is because VIPER spends much time evaluating policies on the environment and some environments quickly reach terminal states which results in short episodes. While OMDT was able to prove optimality on only 7 out of 13 environments within 2 hours, OMDT finds good policies before this time on 12 out of 13 environments. ## 6 Conclusion We propose OMDT, a Mixed-Integer Linear Programming formulation for training optimal size-limited decision trees for Markov Decision Processes. Our results show that for simple environments such as blackjack, we do not have to trade off interpretability for performance: OMDTs of depth 3 achieve near-optimal performance. On Frozenlake 12x12, OMDT outperforms VIPER by more than 100%. OMDT sets a foundation for extending supervised optimal decision tree learning techniques to the reinforcement learning setting. Still, OMDT requires a full specification of the Markov Decision Process. Imitation learning techniques such as VIPER can instead also learn from a simulation environment. Therefore, future work should focus on closing the gap between the theoretical bound supplied by OMDT and the practical performance achieved by algorithms that require only simulation access to optimize interpretable decision tree policies in reinforcement learning. Additionally, future work can incorporate factored MDPs into OMDT's formulation to scale up to larger state spaces. ## References 1. [Aghaei et al., 2019] Sina Aghaei, Mohammad Javad Azizi, and Phebe Vayanos. Learning optimal and fair decision trees for non-discriminative decision-making. In Proceed- ings of the AAAI Conference on Artificial Intelligence, vol- ume 33, pages 1418-1426, 2019. 2. [Aglin et al., 2020] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3146-3153, 2020. 3. [Aglin et al., 2021] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. PyDL8.5: a library for learning optimal decision trees. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artifi- cial Intelligence, pages 5222-5224, 2021. 4. [Ashok et al., 2020] Pranav Ashok, Mathias Jackermeier, Pushpak Jagtap, Jan Křetínskỳ, Maximilian Weininger, and Majid Zamani. dtcontrol: Decision tree learning algo- rithms for controller representation. In Proceedings of the 23rd international conference on hybrid systems: Compu- tation and control, pages 1-7, 2020. 5. [Bastani et al., 2018] Osbert Bastani, Yewen Pu, and Ar- mando Solar-Lezama. Verifiable reinforcement learning via policy extraction. Advances in neural information pro- cessing systems, 31, 2018. 6. [Bellman, 1957] Richard Bellman. A Markovian decision process. Journal of mathematics and mechanics, pages 679-684, 1957. 7. [Bertsimas and Dunn, 2017] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039-1082, 2017. 8. [Brázdil et al., 2015] Tomáš Brázdil, Krishnendu Chatterjee, Martin Chmelík, Andreas Fellner, and Jan Křetínskỳ. Counterexample explanation by learning small strategies in Markov decision processes. In International Conference on Computer Aided Verification, pages 158-177. Springer, 2015. 9. [Breiman et al., 1984] L Breiman, JH Friedman, R Olshen, and CJ Stone. Classification and Regression Trees. Wadsworth, 1984. 10. [Demirović et al., 2020] Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christo- pher Leckie, Kotagiri Ramamohanarao, and Peter J Stuckey. MurTree: optimal classification trees via dynamic programming and search. arXiv preprint arXiv:2007.12652, 2020. 11. [Glanois et al., 2021] Claire Glanois, Paul Weng, Matthieu Zimmer, Dong Li, Tianpei Yang, Jianye Hao, and Wulong Liu. A survey on interpretable reinforcement learning. arXiv preprint arXiv:2112.13112, 2021. 12. [Gunning and Aha, 2019] David Gunning and David Aha. DARPA's explainable artificial intelligence (XAI) pro- gram. AI magazine, 40(2):44-58, 2019. 13. [Gupta et al., 2015] Ujjwal Das Gupta, Erik Talvitie, and Michael Bowling. Policy tree: Adaptive representation for policy gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015. 14. [Hu et al., 2020] Hao Hu, Mohamed Siala, Emmanuel He- brard, and Marie-José Huguet. Learning optimal decision trees with MaxSAT and its integration in AdaBoost. In IJCAI-PRICAI 2020, 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim Interna- tional Conference on Artificial Intelligence, 2020. 15. [Kearns, 1996] Michael Kearns. Boosting theory towards practice: Recent developments in decision tree induction and the weak learning framework. In Proceedings of the national conference on artificial intelligence, pages 1337- 1339, 1996. 16. [Likmeta et al., 2020] Amarildo Likmeta, Alberto Maria Metelli, Andrea Tirinzoni, Riccardo Giol, Marcello Restelli, and Danilo Romano. Combining reinforcement learning with rule-based controllers for transparent and general decision-making in autonomous driving. Robotics and Autonomous Systems, 131:103568, 2020. 17. [Lin et al., 2020] Jimmy Lin, Chudi Zhong, Diane Hu, Cyn- thia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pages 6150-6160. PMLR, 2020. 18. [Lipton, 2018] Zachary C Lipton. The mythos of model interpretability: In machine learning, the concept of in- terpretability is both important and slippery. Queue, 16(3):31-57, 2018. 19. [Lundberg and Lee, 2017] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017. 20. [Molnar, 2020] Christoph Molnar. Interpretable machine learning. Lulu. com, 2020. 21. [Narodytska et al., 2018] Nina Narodytska, Alexey Ignatiev, Filipe Pereira, Joao Marques-Silva, and I Ras. Learning optimal decision trees with sat. In IJCAI, pages 1362- 1368, 2018. 22. [Nijssen and Fromont, 2007] Siegfried Nijssen and Elisa Fromont. Mining optimal decision trees from itemset lat- tices. In Proceedings of the 13th ACM SIGKDD interna- tional conference on Knowledge discovery and data min- ing, pages 530-539, 2007. 23. [Puterman, 2014] Martin L Puterman. Markov decision pro- cesses: discrete stochastic dynamic programming. John Wiley & Sons, 2014. 24. [Quinlan, 1986] J. Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81-106, 1986. 25. [Ribeiro et al., 2016] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should I trust you?" Explain- ing the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowl- edge discovery and data mining, pages 1135-1144, 2016. 26. [Ross et al., 2011] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceed- ings of the fourteenth international conference on artificial intelligence and statistics, pages 627-635. JMLR Work- shop and Conference Proceedings, 2011. 27. [Rudin, 2019] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019. 28. [Schidler and Szeider, 2021] André Schidler and Stefan Szeider. SAT-based decision tree learning for large data sets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3904-3912, 2021. 29. [Schrittwieser et al., 2020] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering Atari, Go, chess and shogi by planning with a learned model. Nature, 588(7839):604-609, 2020. 30. [Silva et al., 2020] Andrew Silva, Matthew Gombolay, Tay- lor Killian, Ivan Jimenez, and Sung-Hyun Son. Optimiza- tion methods for interpretable differentiable decision trees applied to reinforcement learning. In International confer- ence on artificial intelligence and statistics, pages 1855- 1865. PMLR, 2020. 31. [Topin et al., 2021] Nicholay Topin, Stephanie Milani, Fei Fang, and Manuela Veloso. Iterative Bounding MDPs: Learning interpretable policies via non-interpretable meth- ods. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9923-9931, 2021. 32. [Verhaeghe et al., 2020] Hélene Verhaeghe, Siegfried Ni- jssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus. Learning optimal decision trees using constraint programming. Constraints, 25(3):226-250, 2020. 33. [Verwer and Zhang, 2017] Sicco Verwer and Yingqian Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 94-103. Springer, 2017. 34. [Verwer and Zhang, 2019] Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using a binary linear program formulation. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 1625-1632, 2019. 35. [Vos and Verwer, 2022] Daniël Vos and Sicco Verwer. Ro- bust optimal classification trees against adversarial exam- ples. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8520-8528, 2022.