Denis Belomestny: “Semitractability of optimal stopping problems via a weighted stochastic mesh algorithm”

On February 27 the Global Online Seminar “Financial Mathematics” was held at the MSE MSU.

The key speaker at the seminar:

Denis Belomestny (University of Duisburg-Essen).

Topic of his presentation: “Semitractability of optimal stopping problems via a weighted stochastic mesh algorithm” https://disk.yandex.ru/i/5ztbShoaJK24Cg.

Abstract: In this paper, we propose a Weighted Stochastic Mesh (WSM) algorithm for approximating the value of discrete- and continuous-time optimal stopping problems. In this context, we consider tractability of such problems via a useful notion of semitractability and the introduction of a tractability index for a particular numerical solution algorithm. It is shown that in the discrete-time case the WSM algorithm leads to semitractability of the corresponding optimal stopping problem in the sense that its complexity is bounded in order by −4 log +2(1∕ ) with 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 сorresponding complexity bounds. Although we cannot 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.