  We design a numerical scheme for solving a Dynamic Programming equation with
Malliavin weights arising from the time-discretization of backward stochastic
differential equations with the integration by parts-representation of the
$Z$-component by (Ann. Appl. Probab. 12 (2002) 1390-1418). When the sequence of
conditional expectations is computed using empirical least-squares regressions,
we establish, under general conditions, tight error bounds as the time-average
of local regression errors only (up to logarithmic factors). We compute the
algorithm complexity by a suitable optimization of the parameters, depending on
the dimension and the smoothness of value functions, in the limit as the number
of grid times goes to infinity. The estimates take into account the regularity
of the terminal function.
