WIAS Preprint No. 2884, (2021)

Solving optimal stopping problems via randomization and empirical dual optimization


Authors

  • Belomestny, Denis
  • Bender, Christian
  • Schoenmakers, John G. M.
    ORCID: 0000-0002-4389-8266

2020 Mathematics Subject Classification

  • 91G60 65C05 60G40

Keywords

  • Optimal stopping, duality, stochastic average approximation, randomization

DOI

10.20347/WIAS.PREPRINT.2884

Abstract

In this paper we consider optimal stopping problems in their dual form. In this way we reformulate the optimal stopping problem as a problem of stochastic average approximation (SAA) which can be solved via linear programming. By randomizing the initial value of the underlying process, we enforce solutions with zero variance while preserving the linear programming structure of the problem. A careful analysis of the randomized SAA algorithm shows that it enjoys favorable properties such as faster convergence rates and reduced complexity as compared to the non randomized procedure. We illustrate the performance of our algorithm on several benchmark examples.

Appeared in

Download Documents