We analyse the convergence properties of the Longstaff-Schwartz algorithm for approximately solving optimal stopping problems that arise in the pricing of American (Bermudan) financial options. Based on a new approximate dynamic programming principle error propagation inequality, we prove sample complexity error estimates for this algorithm for the case in which the corresponding approximation spaces may not necessarily possess any linear structure at all and may actually be any arbitrary sets of functions, each of which is uniformly bounded and possesses finite VC-dimension, but is not required to satisfy any further material conditions. 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 our error estimation theorems, we also prove convergence, up to any desired probability, of the algorithm for approximating sets defined using L2 orthonormal bases, within a framework depending subexponentially on the number of time steps. In addition, we prove estimates on the overall convergence rate of the algorithm for approximation spaces defined by polynomials.
