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

DOI10.1111/MAFI.12271MaRDI QIDQ6320884arXivFDO

Authors D. Belomestny, Maxim Kaledin, John Schoenmakers

Publication date 22 June 2019

Published in arXiv

Full work available at URL https://doi.org/10.1111/MAFI.12271

Mathematics Subject Classification ID

Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Derivative securities (option pricing, hedging, etc.) (91G20) Numerical methods (including Monte Carlo methods) (91G60)

arXiv classification

cs.NAmath.NAq-fin.CP

Abstract: In this article we propose a Weighted Stochastic Mesh (WSM) Algorithm for approximating the value of a discrete and continuous time optimal stopping problem. We prove that in the discrete case the WSM algorithm leads to semi-tractability of the corresponding optimal problems in the sense that its complexity is bounded in order by $varepsilo{n}^{-4}lo{g}^{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 bounds known for the existing algorithms in the literature. We illustrate our theoretical findings by a numerical example.

This page was built for publication: Semi-tractability of optimal stopping problems via a weighted stochastic mesh algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320884)