Fast upper bounds for optimal stopping problems
by
Christian Bender
TU Braunschweig, Institute for Mathematical Stochastics
Coauthors: Denis Belomestny (WIAS Berlin), John Schoenmakers (WIAS Berlin)

We present a generic non-nested Monte Carlo procedure for computing true upper bounds for optimal stopping problems, given an approximation of the Snell envelope. The pleonastic “true” stresses that, by construction, the estimator is biased above the Snell envelope. The key idea is a regression estimator for the Doob martingale part of the approximative Snell envelope, which preserves the martingale property. The so constructed martingale may be employed for computing dual upper bounds without nested simulation. In general, this martingale can also be used as a control variate for simulation of conditional expectations. In this context, we develop a variance reduced version of the nested primal-dual estimator (Andersen-Broadie method). Numerical experiments in the financial context of Bermudan option pricing indicate the efficiency of the non-nested Monte Carlo algorithm and the variance reduced nested one.

Date received: March 12, 2007