Answers are grounded in this paper and cite their sources.
Study derives a polynomial-time algorithm for optimal stopping, suggesting practical improvements for high-dimensional problems.
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 .
No takes yet. Share an insight, caveat, or question.
Chen et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: