Convergence of a Least-Squares Monte Carlo Algorithm for Bounded Approximating Sets

摘要

We analyse the convergence properties of the Longstaff–Schwartz algorithm forapproximately solving optimal stopping problems that arise in the pricing of American(Bermudan) financial options. Based on a new approximate dynamic programming principleerror propagation inequality, we prove sample complexity error estimates for this algorithm forthe case in which the corresponding approximation spaces may not necessarily possess any linearstructure at all and may actually be any arbitrary sets of functions, each of which is uniformlybounded and possesses finite VC-dimension, but is not required to satisfy any further materialconditions. In particular, we do not require that the approximation spaces be convex or closed,and we thus significantly generalize the results of Egloff, Clement et al., and others. Using ourerror estimation theorems, we also prove convergence, up to any desired probability, of thealgorithm for approximating sets defined using L~2orthonormal bases, within a frameworkdepending subexponentially on the number of time steps. In addition, we prove estimates on theoverall convergence rate of the algorithm for approximation spaces defined by polynomials.