  Optimal stopping is a class of stochastic dynamic optimization problems with
applications in finance and operations management. In this paper, we introduce
a new method for solving stochastic optimal stopping problems with known
probability distributions. First, we use simulation to construct a robust
optimization problem that approximates the stochastic optimal stopping problem
to any arbitrary accuracy. Second, we characterize the structure of optimal
policies for the robust optimization problem, which turn out to be simple and
finite-dimensional. Harnessing this characterization, we develop exact and
approximation algorithms for solving the robust optimization problem, which in
turn yield policies for the stochastic optimal stopping problem. Numerical
experiments show that this combination of robust optimization and simulation
can find policies that match, and in some cases significantly outperform, those
from state-of-the-art algorithms on low-dimensional, non-Markovian optimal
stopping problems from options pricing.
