Optimal Stopping via Pathwise Dual Empirical Maximisation

The optimal stopping problem arising in the pricing of American options can be tackled by the so called dual martingale approach. In this approach, a dual problem is formulated over the space of adapted martingales. A feasible solution of the dual problem yields an upper bound for the solution of the original primal problem. In practice, the optimization is performed over a finite-dimensional subspace of martingales. A sample of paths of the underlying stochastic process is produced by a Monte-Carlo simulation, and the expectation is replaced by the empirical mean. As a rule the resulting optimization problem, which can be written as a linear program, yields a martingale such that the variance of the obtained estimator can be large. In order to decrease this variance, a penalizing term can be added to the objective function of the pathwise optimization problem. In this paper, we provide a rigorous analysis of the optimization problems obtained by adding different penalty functions. In particular, a convergence analysis implies that it is better to minimize the empirical maximum instead of the empirical mean. Numerical simulations confirm the variance reduction effect of the new approach.