  The problem of high-dimensional path-dependent optimal stopping (OS) is
important to multiple academic communities and applications. Modern OS tasks
often have a large number of decision epochs, and complicated non-Markovian
dynamics, making them especially challenging. Standard approaches, often
relying on ADP, duality, deep learning and other heuristics, have shown strong
empirical performance, yet have limited rigorous guarantees (which may scale
exponentially in the problem parameters and/or require previous knowledge of
basis functions or additional continuity assumptions). Although past work has
placed these problems in the framework of computational complexity and
polynomial-time approximability, those analyses were limited to simple
one-dimensional problems. For long-horizon complex OS problems, is a polynomial
time solution even theoretically possible? We prove that given access to an
efficient simulator of the underlying information process, and fixed accuracy
epsilon, there exists an algorithm that returns an epsilon-optimal solution
(both stopping policies and approximate optimal values) with computational
complexity scaling polynomially in the time horizon and underlying dimension.
Like the first polynomial-time (approximation) algorithms for several other
well-studied problems, our theoretical guarantees are polynomial yet
impractical. Our approach is based on a novel expansion for the optimal value
which may be of independent interest.
