WIAS Preprint No. 1495, (2010)
On the rates of convergence of simulation-based optimization algorithms for optimal stopping problems
Authors
- Belomestny, Denis
2010 Mathematics Subject Classification
- 60J25 91B28
Keywords
- optimal stopping, simulation-based algorithms, exponential inequalities, empirical processes
DOI
Abstract
In this paper we study simulation-based optimization algorithms for solving discrete time optimal stopping problems. Using large deviation theory for the increments of empirical processes, we derive optimal convergence rates for the value function estimate and show that they can not be improved in general. The rates derived provide a guide to the choice of the number of simulated paths needed in optimization step, which is crucial for the good performance of any simulation-based optimization algorithm. Finally, we present a numerical example of solving optimal stopping problem arising in finance that illustrates our theoretical findings.
Download Documents