Polynomial-Time Algorithm for Optimal Stopping with Fixed Accuracy

Abstract

The optimal stopping (OS) problem is important to multiple academic communities and applications. Modern OS tasks often have long horizons and complicated, high-dimensional dynamics, making them especially challenging. Many past approaches have computational cost scaling exponentially in the horizon and/or underlying dimension in the worst case, suffering from the curse of dimensionality. In this work, we develop a novel expansion representation for the OS value. We prove that truncating this expansion yields a simulation-based algorithm that implements an [Formula: see text]-optimal stopping policy with computational complexity scaling polynomially in the time horizon and the underlying dimension (for any fixed [Formula: see text]). We also explore some connections between our expansion and the martingale duality theory for OS. Funding: Y. Chen acknowledges support from the National Natural Science Foundation of China (NSFC) [Grants NSFC-72501250 and NSFC-72394361] and the Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence. Supplemental Material: The online companion is available at https://doi.org/10.1287/stsy.2024.0075 .