Variational approach to rare event simulation using least-squares regression

Abstract

ABSTRACT We propose an adaptive importance sampling scheme for the simulation of rare events when the underlying dynamics is given by diffusion. The scheme is based on a Gibbs variational principle that is used to determine the optimal (i.e., zero-variance) change of measure and exploits the fact that the latter can be rephrased as a stochastic optimal control problem. The control problem can be solved by a stochastic approximation algorithm, using the Feynman–Kac representation of the associated dynamic programming equations, and we discuss numerical aspects for high-dimensional problems along with simple toy examples. When computing small probabilities associated with rare events by Monte Carlo, it so happens that the variance of the estimator is of the same order as the quantity of interest. Importance sampling is a means to reduce the variance of the Monte Carlo estimator by sampling from an alternative probability distribution under which the rare event is no longer rare. The estimator must then be corrected by an appropriate reweighting that depends on the likelihood ratio between the two distributions and, depending on this change of measure, the variance of the estimator may easily increase rather than decrease, e.g., when the two probability distributions are (almost) nonoverlapping. The Gibbs variational principle links the cumulant generating function (or free energy) of a random variable with an entropy minimization principle, and it characterizes a probability measure that leads to importance sampling estimators with minimum variance. When the underlying probability measure is the law of a diffusion process, the variational principle can be rephrased as a stochastic optimal control problem, with the optimal control inducing the change of measure that minimizes the variance. In this paper, we discuss the properties of the control problem and propose a numerical method to solve it. The numerical method is based on a nonlinear Feynman–Kac representation of the underlying dynamic programming equation in terms of a pair of forward–backward stochastic differential equations that can be solved by least-squares regression. At first glance, solving a stochastic control problem may be more difficult than the original sampling problem; however, it turns out that the reformulation of the sampling problem opens a completely new toolbox of numerical methods and approximation algorithms that can be combined with Monte Carlo sampling in an iterative fashion and thus leads to efficient algorithms