  In this work, we propose a smart idea to couple importance sampling and
Multilevel Monte Carlo (MLMC). We advocate a per level approach with as many
importance sampling parameters as the number of levels, which enables us to
compute the different levels independently. The search for parameters is
carried out using sample average approximation, which basically consists in
applying deterministic optimisation techniques to a Monte Carlo approximation
rather than resorting to stochastic approximation. Our innovative estimator
leads to a robust and efficient procedure reducing both the discretization
error (the bias) and the variance for a given computational effort. In the
setting of discretized diffusions, we prove that our estimator satisfies a
strong law of large numbers and a central limit theorem with optimal limiting
variance, in the sense that this is the variance achieved by the best
importance sampling measure (among the class of changes we consider), which is
however non tractable. Finally, we illustrate the efficiency of our method on
several numerical challenges coming from quantitative finance and show that it
outperforms the standard MLMC estimator.
