Abstract: The fundamental problems of pricing high-dimensional path-dependent options and optimal stopping are central to applied probability, financial engineering, operations research, and stochastic control, and have a vast literature. Modern approaches, often relying on approximate dynamic programming (Tsitsiklis and Van Roy (1999), Farias et al. (2012)) , simulation (Broadie and Glasserman (1997), Juneja et al. (2016)), and/or the martingale duality theory for optimal stopping (Davis and Karatzas (1994), Rogers (2002)), typically have limited rigorous guarantees, which may scale poorly and/or require previous knowledge of good basis functions. A key diculty with many approaches is that to yield stronger guarantees, they would necessitate the computation of deeply nested conditional expectations, with the depth scaling with the timehorizon T.
In the recent work Chen and Goldberg (2018), we overcome this fundamental obstacle by providing an algorithm which can trade-off between the guaranteed quality of approximation and the level of nesting required in a principled manner. We develop a novel pure-dual approach, inspired by a connection to network flows. This leads to a representation for the optimal value as an infinite sum for which: 1. each term is the expectation of an elegant recursively defined infimum; 2. the first k terms only require k levels of nesting; and 3. truncating at the first k terms yields a (normalized) error of 1/k. This enables us to devise simple randomized and data-driven algorithms and stopping strategies whose runtimes are effectively independent of the dimension, beyond the need to simulate sample paths of the underlying process. Our method allows one to elegantly trade-off between accuracy and runtime through a parameter epsilon controlling the associated performance guarantee (analogous to the notion of PTAS in the theory of approximation algorithms), with computational and sample complexity both polynomial in T (and effectively independent of the dimension) for any fixed epsilon, in contrast to past methods typically requiring a complexity scaling exponentially.

References
Broadie, M., and P. Glasserman. Pricing American-style securities using simulation." Journal of economic dynamics and control 21.8-9 (1997): 1323-1352.
Chen, Y., and D. Goldberg. Beating the curse of dimensionality in options pricing and optimal stopping. ArXiv e-prints (2018).
Davis, M., and I. Karatzas, A deterministic approach to optimal stopping." In Probability, Statistics and Optimization: a Tribute to Peter Whittle, ed. F.P. Kelly, Wiley (1994).
Farias, V., V. Desai, and C. Moallemi. Pathwise optimization for optimal stopping problems." Management Science 58.12 (2012): 2292-2308.
Juneja, S., A. Agarwal, and R. Sircar. American options under stochastic volatility: control variates, maturity randomization and multiscale asymptotics." Quantitative Finance 16.1 (2016): 17-30.
Rogers, L.C.G. Monte Carlo valuation of American options." Mathematical Finance 12.3 (2002): 271-286.
Tsitsiklis, J., and B. Van Roy. Optimal stopping of Markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivatives. IEEE Transactions on Automatic Control 44, no. 10 (1999): 1840-1851.