  We extend the Longstaff-Schwartz algorithm for approximately solving optimal
stopping problems on high-dimensional state spaces. We reformulate the optimal
stopping problem for Markov processes in discrete time as a generalized
statistical learning problem. Within this setup we apply deviation inequalities
for suprema of empirical processes to derive consistency criteria, and to
estimate the convergence rate and sample complexity. Our results strengthen and
extend earlier results.
