Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling

It was established in Dupuis and Wang (2004, 2005) that importance sampling algorithms for estimating rare–event probabilities are intimately connected with two–person zero–sum differential games and the associated Isaacs equation. This game interpretation shows that dynamic or state–dependent schemes are needed in order to attain asymptotic optimality in a general setting. The purpose of the present paper is to show that classical subsolutions of the Isaacs equation can be used as a basic and flexible tool for the construction and analysis of efficient dynamic importance sampling schemes. There are two main contributions. The first is a basic theoretical result characterizing the asymptotic performance of importance sampling estimators based on subsolutions. The second is an explicit method for constructing classical subsolutions as a mollification of piecewise affine functions. Numerical examples are included for illustration and to demonstrate that simple, nearly asymptotically optimal importance sampling schemes can be obtained for a variety of problems via the subsolution approach.