We propose a new
diffusion-asymptotic analysis for sequentially randomized experiments. Rather
than taking sample size n to infinity while keeping the problem
parameters fixed, we let the mean signal level scale to the
order 1/n‾√ so as to preserve the difficulty of the learning task
as n gets large. In this regime, we show that the behavior of a class
of methods for sequential experimentation converges to a diffusion limit. This
connection enables us to make sharp performance predictions and obtain new
insights on the behavior of Thompson sampling. Our diffusion asymptotics also
help resolve a discrepancy between the Θ(log(n)) regret predicted by
the fixed-parameter, large-sample asymptotics on the one hand, and the Θ(n‾√) regret
from worst-case, finite-sample analysis on the other, suggesting that it is an
appropriate asymptotic regime for understanding practical large-scale
sequential experiments.
Stefan Wager is an assistant professor of
Operations, Information and Technology at Stanford University’s Graduate School
of Business, and an assistant professor of Statistics (by courtesy). He
received his Ph.D. in Statistics from Stanford University in 2016, and also
holds a B.S. (2011) degree in Mathematics from Stanford. Professor Wager’s
research lies at the intersection of causal inference, optimization, and
statistical learning. He is particularly interested in developing new solutions
to classical problems in statistics, economics and decision making that
leverage recent developments in machine learning.