Solving Optimal Stopping Problem with Approximate Dynamic Programming

Traditional methods for solving optimal stopping problems like finite differences become ineffective when dealing with high dimensional setting, therefore it is common to use Monte-Carlo methods for such problems. Most popular Monte-Carlo techniques involve regression and approximation while going through dynamic programming steps. The quality of the solution depends crucially on the choice of basis functions for regression. In this paper we present a new approach to improve existing regression methods where on each step of backward dynamic programming the regression basis is augmented by previously estimated functions. Such basis functions depend non-linearly on the whole set of information obtained during backward regression, but the algorithm doesn't require expensive non-linear optimization. In the first part of the paper we present the reinforced regression algorithm and consider in detail its implementation. Further we study computational costs and theoretical properties of reinforced regression. Numerical performance of reinforced regression is presented for benchmark problems from mathematical finance. In the second part we show how in the Ito-Wiener environment the suggested approach also helps to build the basis of the optimal martingale required for the dual solution of optimal stopping problem. Specifically we use the stochastic integrals computed for derivatives of previously estimated continuation functions and show their effectiveness in numerical experiments.