A quantization algorithm for solving multi-dimensional Optimal Stopping problems

TL;DRAbstract

A new grid method for computing the Snell envelop of a function of a R -valued Markov chain (X k ) 0#k#n is proposed. (This problem is typically non linear and cannot be solved by the standard Monte Carlo method.) Every X k is replaced by a "quantized approximation" X k taking its values in a grid # k of size N k . The n grids and their transition probability matrices make up a discrete tree on which a pseudo-Snell envelop is devised by mimicking the regular dynamic programming formula. We show, using Quantization Theory of probability distributions the existence of a set of optimal grids, given the total number N of elementary R -valued vector quantizers. A recursive stochastic algorithm, based on some simulations of (X k ) 0#k#n , yields the optimal grids and their transition probability matrices. Some a priori error estimates based on the quantization errors are established. These results are applied to the computation of the Snell envelop of a di#usion (assuming t

Chat with Paper

AI Agents for this Paper