  Importance sampling is often used in machine learning when training and
testing data come from different distributions. In this paper we propose a new
variant of importance sampling that can reduce the variance of importance
sampling-based estimates by orders of magnitude when the supports of the
training and testing distributions differ. After motivating and presenting our
new importance sampling estimator, we provide a detailed theoretical analysis
that characterizes both its bias and variance relative to the ordinary
importance sampling estimator (in various settings, which include cases where
ordinary importance sampling is biased, while our new estimator is not, and
vice versa). We conclude with an example of how our new importance sampling
estimator can be used to improve estimates of how well a new treatment policy
for diabetes will work for an individual, using only data from when the
individual used a previous treatment policy.
