WIAS Preprint No. 2610, (2019)

Semi-tractability of optimal stopping problems via a weighted stochastic mesh algorithm


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

2010 Mathematics Subject Classification

  • 65C05 60H35 62P05


  • Optimal stopping, American options, Monte Carlo algorithms, complexity




In this article we propose a Weighted Stochastic Mesh (WSM) algorithm for approximating the value of discrete and continuous time optimal stopping problems. It is shown that in the discrete time case the WSM algorithm leads to semi-tractability of the corresponding optimal stopping problem in the sense that its complexity is bounded in order by $varepsilon^-4log^d+2(1/varepsilon)$ with $d$ being the dimension of the underlying Markov chain. Furthermore we study the WSM approach in the context of continuous time optimal stopping problems and derive the corresponding complexity bounds. Although we can not prove semi-tractability in this case, our bounds turn out to be the tightest ones among the complexity bounds known in the literature. We illustrate our theoretical findings by a numerical example.

Appeared in

Download Documents