Robust decision trees optimize costs despite prediction uncertainty
Largest Rashomon sets of decision trees for robust contextual optimization
Machine Learning
Summary
Many decision trees can fit the same data well but make different decisions for the same point, which leads to uncertainty. The authors study how to make decisions that meet cost or risk goals even when predictions vary across these trees. They developed a method that finds both the best decision and all trees that give similar fits, ensuring targets are met under any scenario represented by these trees. Their approach speeds up computations and improves robustness on real-world data like restaurant demand.
What this means in practice
- •For supply chain planners: Ensure ordering decisions meet cost and risk targets under uncertain demand predictions using robust decision trees.
- •For restaurant operations managers: Improve demand forecasting and ordering robustness to reduce costly overstock and shortages using optimized decision trees.
Authors
Lorenzo Bonasera, David Pisinger
Abstract
Many decision trees fit the same data almost equally well, yet they can route a query point to different leaves and induce different local empirical distributions. We study decisions that meet prescribed cost, shortage or risk targets despite this predictive multiplicity. We propose the joint Rashomon and robustness optimization framework for optimal decision trees. It jointly selects an operational decision and the largest Rashomon set of trees, so that the targets hold under the local empirical distribution that every tree in this set induces at the query point. We specialize the framework to the regression setting, and we show that a tree affects the decision only through the training observations sharing the query leaf, which we call its query neighborhood. As a result, the robust problem involves only finitely many distinct constraints, which can be examined in order of increasing estimation loss. We develop a constraint generation algorithm that combines query-path pricing with dynamic programming to identify violating neighborhoods without enumerating trees. On synthetic newsvendor instances, the algorithm typically needs few neighborhoods and runs substantially faster than full neighborhood enumeration. On restaurant demand data, the robust orders increase the mean tolerated excess estimation loss by 17.6% and reduce the empirical conditional value-at-risk of the worst 10% of realized costs by 8.3% relative to the sample average approximation orders of the optimal tree, while the mean cost difference is not statistically significant. An interpretability analysis further shows how the retained neighborhoods explain the decision and its robustness limit.