A quantization algorithm for solving multidimensional discrete-time optimal stopping problems

A new grid method for computing the Snell envelope of a function of an R-d-valued simulatable Markov chain (X-k)(0less than or equal tokless than or equal ton) is proposed. (This is a typical nonlinear problem that cannot be solved by the standard Monte Carlo method.) Every X-k is replaced by a 'quantized approximation' (X) over cap (k) taking its values in a grid Gamma(k) of size N-k. The n grids and their transition probability matrices form a discrete tree on which a pseudo-Snell envelope is devised by mimicking the regular dynamic programming formula. Using the quantization theory of random vectors, we show the existence of a set of optimal grids, given the total number N of elementary R-d-valued quantizers. A recursive stochastic gradient algorithm, based on simulations of (X-k)(0less than or equal tokless than or equal ton), yields these optimal grids and their transition probability matrices. Some a priori error estimates based on the L-p-quantization errors \\X-k - (X) over cap (k)\\(p) are established. These results are applied to the computation of the Snell envelope of a diffusion approximated by its (Gaussian) Euler scheme. We apply these results to provide a discretization scheme for reflected backward stochastic differential equations. Finally, a numerical experiment is carried out on a two-dimensional American option pricing problem.