Ant-based approach for determining the change of measure in importance sampling

Importance Sampling is a potentially powerful variance reduction technique to speed up simulations where the objective depends on the occurrence of rare events. However, it is crucial to find a change of the underlying probability measure yielding estimators with significantly reduced variance compared to direct estimators. In this paper, we present a new dynamic and adaptive method for this purpose. The method is inspired by ant-based systems that are in widespread use for solving optimization problems. No intimate knowledge of the model under consideration is necessary. Instead, the method adapts to it. Different commonly used modeling paradigms such as queueing and reliability models, amongst many others, are supported by describing the new method in terms of a transition class formalism. Simulation results demonstrate the accuracy of the obtained estimates, and details of the adapted change of measure are investigated to gain insights into the inner workings of the method.