Polynomial-Time Algorithm for Optimal Stopping with Fixed Accuracy

References

• Andersen L, Broadie M (2004) Primal-dual simulation algorithm for pricing multidimensional American options. Management Sci. 50(9):1222–1234.Link, Google Scholar
• Balkanski E, Rubinstein A, Singer Y (2017) The limitations of optimization from samples. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1016–1027.Google Scholar
• Bayer C, Redmann M, Schoenmakers J (2021) Dynamic programming for optimal stopping via pseudo-regression. Finance 21(1):29–44.Google Scholar
• Becker S, Cheridito P, Jentzen A (2019) Deep optimal stopping. J. Machine Learn. Res. 20(74):1–25.Google Scholar
• Becker S, Cheridito P, Jentzen A, Welti T (2021) Solving high-dimensional optimal stopping problems using deep learning. Eur. J. Appl. Math. 32(3):470–514.Google Scholar
• Belomestny D (2011) On the rates of convergence of simulation-based optimization algorithms for optimal stopping problems. Ann. Appl. Probab. 21(1):215–239.Google Scholar
• Belomestny D, Milstein GN (2006) Monte Carlo evaluation of American options using consumption processes. Internat. J. Theoret. Appl. Finance 9(4):455–481.Google Scholar
• Belomestny D, Bender C, Schoenmakers J (2009) True upper bounds for Bermudan products via non-nested Monte Carlo. Math. Finance 19(1):53–71.Google Scholar
• Belomestny D, Hildebrand R, Schoenmakers J (2019) Optimal stopping via pathwise dual empirical maximisation. Appl. Math. Optim. 79(3):715–741.Google Scholar
• Belomestny D, Ladkau M, Schoenmakers J (2015) Multilevel simulation based policy iteration for optimal stopping—Convergence and complexity. SIAM/ASA J. Uncertainty Quantification 3(1):460–483.Google Scholar
• Belomestny D, Schoenmakers J, Dickmann F (2013) Multilevel dual approach for pricing American style derivatives. Finance Stochastics 17(4):717–742.Google Scholar
• Belomestny D, Schoenmakers J, Spokoiny V, Zharkynbay B (2020) Optimal stopping via deeply boosted backward regression. Comm. Math. Sci. 18(1):109–121.Google Scholar
• Bezerra SC, Ohashi A, Russo F, de Souza F (2020) Discrete-type approximations for non-Markovian optimal stopping problems: Part II. Methodology Comput. Appl. Probab. 22(3):1221–1255.Google Scholar
• Bouchard B, Warin X (2012) Monte-Carlo valuation of American options: Facts and new algorithms to improve existing methods. Carmona R, Del Moral P, Hu P, Oudjane N, eds. Numerical Methods in Finance (Springer, Berlin), 215–255.Google Scholar
• Brown DB, Smith JE, Sun P (2010) Information relaxations and duality in stochastic dynamic programs. Oper. Res. 58(4-part-1):785–801.Link, Google Scholar
• Chen Y (2021) Efficient algorithms for high-dimensional data-driven sequential decision-making. Ph.D. thesis, Cornell University, Ithaca, NY.Google Scholar
• Chen N, Glasserman P (2007) Additive and multiplicative duals for American option pricing. Finance Stochastics 11(2):153–179.Google Scholar
• Chen Y, Wang M (2017) Lower bound on the computational complexity of discounted Markov decision problems. Preprint, submitted May 20, https://arxiv.org/abs/1705.07312.Google Scholar
• Chow Y, Robbins H, Siegmund D (1971) Great Expectations: The Theory of Optimal Stopping (Houghton Mifflin, Boston).Google Scholar
• Christensen S (2014) A method for pricing American options using semi-infinite linear programming. Math. Finance 24(1):156–172.Google Scholar
• Ciocan DF, Mišić VV (2022) Interpretable optimal stopping. Management Sci. 68(3):1616–1638.Link, Google Scholar
• Clément E, Lamberton D, Protter P (2002) An analysis of a least squares regression method for American option pricing. Finance Stochastics 6(4):449–471.Google Scholar
• Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms (MIT Press, Cambridge, MA).Google Scholar
• Davis MH, Karatzas I (1994) A deterministic approach to optimal stopping. Kelly FP, ed. Probability, Statistics and Optimisation (John Wiley & Sons Ltd, New York), 455–466.Google Scholar
• De Klerk E (2008) The complexity of optimizing over a simplex, hypercube or sphere: A short survey. Central Eur. J. Oper. Res. 16(2):111–125.Google Scholar
• Desai VV, Farias VF, Moallemi CC (2012) Pathwise optimization for optimal stopping problems. Management Sci. 58(12):2292–2308.Link, Google Scholar
• Du SS, Kakade SM, Wang R, Yang LF (2019) Is a good representation sufficient for sample efficient reinforcement learning? Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Egloff D (2005) Monte Carlo algorithms for optimal stopping and statistical learning. Ann. Appl. Probab. 15(2):1396–1432.Google Scholar
• Glasserman P, Yu B (2004) Number of paths versus number of basis functions in American option pricing. Ann. Appl. Probab. 14(4):2090–2119.Google Scholar
• Halman N, Nannicini G, Orlin J (2015) A computationally efficient FPTAS for convex stochastic dynamic programs. SIAM J. Optim. 25(1):317–350.Google Scholar
• Halman N, Klabjan D, Li CL, Orlin J, Simchi-Levi D (2014) Fully polynomial time approximation schemes for stochastic dynamic programs. SIAM J. Discrete Math. 28(4):1725–1796.Google Scholar
• Haugh MB, Kogan L (2004) Pricing American options: A duality approach. Oper. Res. 52(2):258–270.Link, Google Scholar
• Hill TP, Kertz RP (1983) Stop rule inequalities for uniformly bounded sequences of random variables. Trans. Amer. Math. Soc. 278(1):197–207.Google Scholar
• Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125(1):191–207.Google Scholar
• Ibáñez A, Velasco C (2020) Recursive lower and dual upper bounds for Bermudan-style options. Eur. J. Oper. Res. 280(2):730–740.Google Scholar
• Jamshidian F (2007) The duality of optimal exercise and domineering claims: A Doob–Meyer decomposition approach to the Snell envelope. Stochastics 79(1–2):27–60.Google Scholar
• Kohler M (2008) A regression-based smoothing spline Monte Carlo algorithm for pricing American options in discrete time. AStA Adv. Statist. Anal. 92(2):153–178.Google Scholar
• Kohler M, Krzyżak A, Todorovic N (2010) Pricing of high-dimensional American options by neural networks. Math. Finance 20(3):383–410.Google Scholar
• Kolodko A, Schoenmakers J (2004) Upper bounds for Bermudan style derivatives. Monte Carlo Methods Appl. 10(3–4):331–343.Google Scholar
• Kolodko A, Schoenmakers J (2006) Iterative construction of the optimal Bermudan stopping time. Finance Stochastics 10(1):27–49.Google Scholar
• Lai TL, Wong SS (2004) Valuation of American options via basis functions. IEEE Trans. Automatic Control 49(3):374–385.Google Scholar
• Lelong J (2018) Dual pricing of American options by wiener chaos expansion. SIAM J. Financial Math. 9(2):493–519.Google Scholar
• Longstaff FA, Schwartz ES (2001) Valuing American options by simulation: A simple least-squares approach. Rev. Financial Stud. 14(1):113–147.Google Scholar
• Nemirovsky AS, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics (John Wiley and Sons, New York).Google Scholar
• Rockafellar RT, Wets RJB (1991) Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1):119–147.Link, Google Scholar
• Rogers LC (2002) Monte Carlo valuation of American options. Math. Finance 12(3):271–286.Google Scholar
• Schoenmakers J, Zhang J, Huang J (2013) Optimal dual martingales, their analysis, and application to new algorithms for Bermudan products. SIAM J. Financial Math. 4(1):86–116.Google Scholar
• Shapiro A, Nemirovski A (2005) On complexity of stochastic programming problems. Jeyakumar V, Rubinov A, eds. Continuous Optimization (Springer, Boston), 111–146.Google Scholar
• Sidford A, Wang M, Wu X, Yang L, Ye Y (2018) Near-optimal time and sample complexities for solving Markov decision processes with a generative model. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Red Hook, NY), 5186–5196.Google Scholar
• Solan E, Tsirelson B, Vieille N (2012) Random stopping times in stopping problems and stopping games. Preprint, submitted November 25, https://arxiv.org/abs/1211.5802.Google Scholar
• Stentoft L (2004) Convergence of the least squares Monte Carlo approach to American option valuation. Management Sci. 50(9):1193–1203.Link, Google Scholar
• Sturt B (2023) A nonparametric algorithm for optimal stopping based on robust optimization. Oper. Res. 71(5):1530–1557.Google Scholar
• Swamy C, Shmoys DB (2012) Sampling-based approximation algorithms for multistage stochastic optimization. SIAM J. Comput. 41(4):975–1004.Google Scholar
• Traub JF, Werschulz AG (1998) Complexity and Information. Lezioni Lincee, vol. 26862 (Cambridge University Press, Cambridge, UK).Google Scholar
• Tsitsiklis JN, Van Roy B (1999) Optimal stopping of Markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivatives. IEEE Trans. Automatic Control 44(10):1840–1851.Google Scholar
• Tsitsiklis JN, Van Roy B (2001) Regression methods for pricing complex American-style options. IEEE Trans. Neural Networks 12(4):694–703.Google Scholar
• van der Vaart AW (2000) Asymptotic Statistics, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 3 (Cambridge University Press, Cambridge, UK).Google Scholar
• Wang D, Han Z (2015) Basics for sublinear algorithms. Sublinear Algorithms for Big Data Applications, SpringerBriefs in Computer Science (Springer, Cham, Switzerland), 9–21.Google Scholar
• Wang Y, Wang R, Kakade SM (2021) An exponential lower bound for linearly-realizable MDPs with constant suboptimality gap. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY).Google Scholar
• Ye J, Wong HY (2025) DeepMartingale: Duality of the optimal stopping problem with expressivity. Preprint, submitted October 13, https://arxiv.org/abs/2510.13868.Google Scholar
• Zhou Z, Wang G, Blanchet J, Glynn PW (2023) Unbiased optimal stopping via the MUSE. Stochastic Processes their Appl. 166(2023):104088.Google Scholar