Semitractability of optimal stopping problems via a weighted stochastic mesh algorithm

Denis Belomestny, Maxim Kaledin and John Schoenmakers

Mathematical Finance, 2020, vol. 30, issue 4, 1591-1616

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 ε−4logd+2(1/ε) 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 cannot prove semitractability 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.

Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1111/mafi.12271

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:mathfi:v:30:y:2020:i:4:p:1591-1616

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0960-1627

Access Statistics for this article

Mathematical Finance is currently edited by Jerome Detemple

More articles in Mathematical Finance from Wiley Blackwell
Bibliographic data for series maintained by Wiley Content Delivery ().