Polynomial time algorithm for optimal stopping with fixed accuracy

David A. Goldberg and Yilun Chen

Papers from arXiv.org

Abstract: 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.

Date: 2018-07, Revised 2024-05
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://arxiv.org/pdf/1807.02227 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:1807.02227

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().