Monte Carlo Algorithms for Optimal Stopping and Statistical Learning - Convergence Rates and Sample Complexity

In this article we extend the by now classical Longstaff-Schwartz algorithm for approximately solving high dimensional optimal stopping problems. We reformulate the problem of optimal stopping in discrete time as a generalized statistical learning problem. Within this setup we apply modern concentration inequalities for empirical means to study consistency criteria, convergence rates, and sample complexity estimates. Our results strengthen and extend earlier results obtained by Clement, Lamberton and Protter