The Snell envelope and analysis of various approximation schemes

OMI Seminar Series

We analyze the robustness properties of the Snell envelope backward evolution equation for the discrete time optimal stopping problem. By providing a single and general robustness property of Snell envelope semigroups, we deduce estimates for different approximation schemes. In particular,  this analysis allows us to recover existing convergence results for the quantization tree method and to improve significantly the rates of convergence obtained for the Stochastic Mesh estimator of Broadie-Glasserman. We propose a new particle algorithm based on a genealogical tree approximation model. In addition to these general analysis, we also present a new algorithm to compute the Snell envelope in the specific case where the criteria to optimize is associated with a small probability or a rare event. This new approach combines the Stochastic Mesh approach of Broadie and Glasserman with a particle approximation scheme based on a specific change of measure designed to concentrate the computational effort in regions pointed out by the criteria. The theoretical analysis of this new algorithm provides non asymptotic convergence estimates. Finally,  the numerical tests confirm the practical interest of this approach.


Peng Hu (University of Bordeaux)

Friday, March 2, 2012 - 14:15
to 15:15