On the rates of convergence of simulation-based optimization algorithms for optimal stopping problems (Q627243)

The simplified version of the problem considered consists of finding \[ v^*=\sup_{1\leq\tau\leq K}\text{E}[Z_\tau], \] where \(Z\) is a Markov chain in \(\mathbb R^n\) and \(\tau\) is a stopping time. The standard first step to solve this problem is to describe the stopping times as entrance times in appropriate sets obtained after solving a Bellman type recursion. Once the description is at hand, supposing that we can generate or obtain independent samples of the process and prescribe how to specify the stopping times, we can invoke the law of large numbers to compute the approximate value of the objective function. This is all explained in section two of the paper. Section three is devoted to the solution of the complementary problem: the choice of the ``good'' size of the sample. This is obtained from estimates of the rate of convergence of the above mentioned estimator. After that, several examples of interest in finance are considered, and the last three sections of the paper are devoted to the proofs of the statements.