We derive a \emph{lower bound} for the \emph{sample complexity} of the Sample Average Approximation method for a certain class of multistage stochastic optimization problems. In previous works, \emph{upper bounds} for such problems were derived. We show that the dependence of the \emph{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 \emph{lower bound} presents an additional multiplicative factor showing that it is unavoidable for certain stochastic problems.
Article
View A note on sample complexity of multistage stochastic programs