Interpretable Optimal Stopping

By Dragos Florin Ciocan, Velibor V. Misic. 2018

50 citations recorded by the source corpus.

Optimal stopping is the problem of deciding when to stop a stochastic system to obtain the greatest reward, arising in numerous application areas such as finance, healthcare, and marketing. State-of-the-art methods for high-dimensional optimal stopping involve approximating the value function or the continuation value and then using that approximation within a greedy policy. Although such policies can perform very well, they are generally not guaranteed to be interpretable; that is, a decision maker may not be able to easily see the link between the current system state and the policy’s action. In this paper, we propose a new approach to optimal stopping wherein the policy is represented as a binary tree, in the spirit of naturally interpretable tree models commonly used in machine learning. We show that the class of tree policies is rich enough to approximate the optimal policy. We formulate the problem of learning such policies from observed trajectories of the stochastic system as a sample average approximation (SAA) problem. We prove that the SAA problem converges under mild conditions as the sample size increases but that, computationally, even immediate simplifications of the SAA problem are theoretically intractable. We thus propose a tractable heuristic for approximately solving the SAA problem by greedily constructing the tree from the top down. We demonstrate the value of our approach by applying it to the canonical problem of option pricing, using both synthetic instances and instances using real Standard & Poor’s 500 Index data. Our method obtains policies that (1) outperform state-of-the-art noninterpretable methods, based on simulation regression and martingale duality, and (2) possess a remarkably simple and intuitive structure. This paper was accepted by Chung Piaw Teo for the Special Issue on Data-Driven Prescriptive Analytics.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, background): “MIP formulations have also been leveraged to design decision trees for decision-and policy-making problems, see Azizi et al. (2018) and Ciocan and Miši´c (2018), and for optimizing decisions over tree ensembles, see Mišic (2017).”
Market Segmentation Trees (2019, methodology): “Decision trees provide a simple way to visualize the decision-making stream and have been used in a variety of settings (Kallus 2017, Elmachtoub et al. 2017, Ciocan and Mišić 2022, Bertsimas et al. 2019, Aghaei et al. 2019).”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, unknown): “We remark that the use of decision trees for decision-making problems has seen increased attention in practice and recent literature due to their interpretability (Kallus 2017, Elmachtoub et al. 2017, Ciocan and Miˇsi´c 2018, Bertsimas et al. 2019, Aghaei et al. 2019, Aouad et al. 2019).”