A note on sample complexity of multistage stochastic programs

We derive a lower bound for the sample complexity of the Sample Average Approximation method for a certain class of multistage stochastic optimization problems. In previous works, upper bounds for such problems were derived. We show that the dependence of the lower bound with respect to the complexity parameters and the problem's data are comparable to the upper bound's estimates. Like previous results, our lower bound presents an additional multiplicative factor showing that it is unavoidable for certain stochastic problems. (C) 2016 Elsevier B.V. All rights reserved.