Decision Trees for Decision-Making under the Predict-then-Optimize Framework

We consider the use of decision trees for decision-making problems under the\npredict-then-optimize framework. That is, we would like to first use a decision\ntree to predict unknown input parameters of an optimization problem, and then\nmake decisions by solving the optimization problem using the predicted\nparameters. A natural loss function in this framework is to measure the\nsuboptimality of the decisions induced by the predicted input parameters, as\nopposed to measuring loss using input parameter prediction error. This natural\nloss function is known in the literature as the Smart Predict-then-Optimize\n(SPO) loss, and we propose a tractable methodology called SPO Trees (SPOTs) for\ntraining decision trees under this loss. SPOTs benefit from the\ninterpretability of decision trees, providing an interpretable segmentation of\ncontextual features into groups with distinct optimal solutions to the\noptimization problem of interest. We conduct several numerical experiments on\nsynthetic and real data including the prediction of travel times for shortest\npath problems and predicting click probabilities for news article\nrecommendation. We demonstrate on these datasets that SPOTs simultaneously\nprovide higher quality decisions and significantly lower model complexity than\nother machine learning approaches (e.g., CART) trained to minimize prediction\nerror.\n