A huge impetus to the development of optimal stopping theory was provided by option pricing theory, developed in the late 1960s and the 1970s. According to the modern financial theory, pricing an American option in a complete market is equivalent to solving an optimal stopping problem (with a corresponding generalization in incomplete markets), the optimal stopping time being the rational time for the option to be exercised. Due to the enormous importance of the early exercise feature in finance, this line of research has been intensively pursued in recent times.
Solving the optimal stopping problem and hence pricing an American option is
straightforward in low dimensions. However, many problems arising
in practice have high dimensions, and these applications
have motivated the development of Monte Carlo methods for pricing American option.
Solving a high-dimensional optimal stopping problems or pricing American style derivatives with Monte Carlo is a challenging task because
the determination of the optimal value function requires a backwards dynamic
programming algorithm that appears to be incompatible with the forward nature
of Monte Carlo simulation. Much research was focused on the development of
fast methods to compute approximations to the optimal value function.
Notable examples include
mesh method of [1]}, the regression-based approaches of [2]}, [3]}, [4]} and [5]}.
All these methods aim at approximating the so called continuation values that can be used later
to construct suboptimal strategies and to produce lower bounds for the optimal value function.
The convergence analysis for this type of methods was performed in several papers including
[5]}, [7]} and [8]}.
An alternative to trying to approximate the continuation values is to find the best
value function within a class of stopping rules. This reduces
the optimal stopping problem to a much more tractable finite dimensional
optimization problem. Such optimization
problems appear naturally if one considers finite dimensional or parametric
approximations for the corresponding stopping regions. The latter type of algorithms became
particularly popular among practioneers (see e.g. [9]} or [10]}).
However, the practical success of simulation-based optimization algorithms
has not been yet fully explained by existing theory, and our analysis here
represents a further step toward an improved understanding. The main goal of this work is to provide rigorous convergence analysis of simulation based optimization algorithms
for discrete time optimal stopping problems.
