Efficient importance sampling under partial information

Importance sampling is widely perceived as an indispensable tool in Monte Carlo estimation for rare-event problems. It is also known, however, that constructing efficient importance sampling scheme requires in many cases a precise knowledge of the underlying stochastic structure. This paper considers the simplest problem in which part of the system is not directly known. Namely, we consider the tail probability of a monotone function of sum of independent and identically distributed (i.i.d.) random variables, where the function is only accessible through black-box simulation. A simple two-stage procedure is proposed whereby the function is learned in the first stage before importance sampling is applied. We discuss some sufficient conditions for the procedure to retain asymptotic optimality in well-defined sense, and discuss the optimal computational allocation. Simple analysis shows that the procedure is more beneficial than a single-stage mixture-based importance sampler when the computational cost of learning is relatively light.