# Interpretable Optimal Stopping

arXiv: https://arxiv.org/abs/1812.07211 · HTML: https://mlsanity.com/paper/1812.07211/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2018.

## Built on by (most cited first, 15 of 15)

- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [The Best Decisions Are Not the Best Advice: Making Adherence-Aware Recommendations](https://mlsanity.com/paper/2209.01874/) (2022)
- [A Framework for Inherently Interpretable Optimization Models](https://mlsanity.com/paper/2208.12570/) (2022)
- [Loss Functions for Discrete Contextual Pricing with Observational Data](https://mlsanity.com/paper/2111.09933/) (2021)
- [Deep Reinforcement Learning for Optimal Stopping with Application in Financial Engineering](https://mlsanity.com/paper/2105.08877/) (2021)
- [Interpretable Machine Learning for Resource Allocation with Application to Ventilator Triage](https://mlsanity.com/paper/2110.10994/) (2021)
- [Deep Optimal Timing Strategies for Time Series](https://mlsanity.com/paper/2310.05479/) (2023)
- [Randomized Policy Optimization for Optimal Stopping](https://mlsanity.com/paper/2203.13446/) (2022)
- [Feature-Based Interpretable Surrogates for Optimization](https://mlsanity.com/paper/2409.01869/) (2024)
- [Soft regression trees: a model variant and a decomposition training algorithm](https://mlsanity.com/paper/2501.05942/) (2025)
- [Robust and Heterogenous Odds Ratio: Estimating Price Sensitivity for Unbought Items](https://mlsanity.com/paper/2106.11389/) (2021)
- [A Hybrid Statistical-Machine Learning Approach for Analysing Online Customer Behavior: An Empirical Study](https://mlsanity.com/paper/2212.02255/) (2022)
- [How much Data do We Need? Sequential Data Collection for Stochastic Programming](https://mlsanity.com/paper/2607.10207/) (2026)
- [CC-AOS: Cost- and Horizon-Conditioned Amortized Backward Induction for Finite-Horizon Optimal Stopping](https://mlsanity.com/paper/2607.22774/) (2026)

## Abstract (arXiv)

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 S&P-500 data. Our method obtains policies that (1) outperform state-of-the-art non-interpretable methods, based on simulation-regression and martingale duality, and (2) possess a remarkably simple and intuitive structure.