  We introduce new variants of classical regression-based algorithms for
optimal stopping problems based on computation of regression coefficients by
Monte Carlo approximation of the corresponding $L^2$ inner products instead of
the least-squares error functional. Coupled with new proposals for simulation
of the underlying samples, we call the approach "pseudo regression". A detailed
convergence analysis is provided and it is shown that the approach
asymptotically leads to less computational cost for a pre-specified error
tolerance, hence to lower complexity. The method is justified by numerical
examples.
