Learning Optimal Prescriptive Trees from Observational Data

We consider the problem of learning an optimal prescriptive tree (i.e., an interpretable treatment assignment policy in the form of a binary tree) of moderate depth from observational data. This problem arises in numerous socially important domains, such as public health and medicine, where interpretable and data-driven interventions are sought based on data gathered in deployment rather than from randomized trials. We propose a method for learning optimal prescriptive trees using mixed-integer optimization technology assuming that our data satisfy standard causal inference assumptions (conditional exchangeability and positivity) and are discrete/discretized. We show that under mild conditions, our method is asymptotically exact (i.e., it converges to an optimal out-of-sample treatment assignment policy as the number of historical data samples tends to infinity). Contrary to the existing literature, our approach (a) does not require data to be randomized, (b) does not impose stringent assumptions on the learned trees, and (c) has the ability to model domain-specific constraints. Through extensive computational experiments, we demonstrate that our asymptotic guarantees translate to significant performance improvements in finite samples as well as showcase our uniquely flexible modeling power by incorporating budget and fairness constraints.

This paper was accepted by Chung Piaw Teo, optimization.

Funding: N. Jo acknowledges support from the Epstein Institute at the University of Southern California. N. Jo, S. Aghaei, and P. Vayanos acknowledge support from the Home for Good Foundation [Grant C.E.S. Triage Tool Research & Refinement], the Conrad N. Hilton Foundation [Grant C.E.S. Triage Tool Research & Refinement], and the Homeless Policy Research Institute [Grant C.E.S. Triage Tool Research & Refinement]. S. Aghaei and P. Vayanos are funded in part by the National Science Foundation [Grant 2046230]. A. Gómez is funded in part by the National Science Foundation [Grant 2006762]. A. Gómez and P. Vayanos are also supported by the National Science Foundation [NRT Grant 2346058].

Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2021.02813.