Importance Sampling, Large Deviations, and Differential Games

Abstract

A standard heuristic in the area of importance sampling is that the changes of measure used to prove large deviation lower bounds give good performance when used for importance sampling. Recent work, however, has shown that a naive implementation of the heuristic is incorrect in many situations. The present paper considers the simple setting of sums of independent and identically distributed (iid) random variables, and shows that under mild conditions asymptotically optimal changes of measure can be found if one considers dynamic importance sampling schemes. For such schemes, the change of measure applied to an individual summand can depend on the historical empirical mean of the simulation (i.e. the system state). In analyzing the asymptotic performance of importance sampling, we show that the value function of a differential game characterizes the optimal performance, with player A corresponding to the choice of change of measure and player B arising due to a large deviations analysis. From this perspective, the traditional implementation of the heuristic is shown to correspond to player A choosing a control that is fixed, regardless of the system state or player B's choice of control. This leads to an "open loop" control for player A, which is suboptimal except in special cases. Our final contribution is a method, based on the Isaacs equation associated with the differential game, for constructing dynamic schemes. Numerical examples are presented to illustrate the results.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 147 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.