Decision trees are known to be intrinsically interpretable as they can be
inspected and interpreted by humans. Furthermore, recent hardware advances have
rekindled an interest for optimal decision tree algorithms, that produce more
accurate trees than the usual greedy approaches. However, these optimal
algorithms return a single tree optimizing a hand defined
interpretability-performance trade-off, obtained by specifying a maximum number
of decision nodes, giving no further insights about the quality of this
trade-off. In this paper, we propose a new Markov Decision Problem (MDP)
formulation for finding optimal decision trees. The main interest of this
formulation is that we can compute the optimal decision trees for several
interpretability-performance trade-offs by solving a single dynamic program,
letting the user choose a posteriori the tree that best suits their needs.
Empirically, we show that our method is competitive with state-of-the-art
algorithms in terms of accuracy and runtime while returning a whole set of
trees on the interpretability-performance Pareto front.

为了找到最佳的决策树，本文提出了一种新的马尔可夫决策问题 (MDP) 的公式，允许用户在计算一个动态规划的同时选择最适合自身需求的决策树