pith. sign in

arxiv: 1906.09431 · v1 · pith:5YA2XUA6new · submitted 2019-06-22 · 💱 q-fin.CP · cs.NA· math.NA

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

D. Belomestny , M. Kaledin , J. Schoenmakers This is my paper

Pith reviewed 2026-05-25 18:11 UTC · model grok-4.3

classification 💱 q-fin.CP cs.NAmath.NA
keywords optimal stoppingstochastic meshsemi-tractabilitycomplexity boundsweighted algorithmMarkov chaindiscrete timecontinuous time
0
0 comments X

The pith

A weighted stochastic mesh algorithm achieves semi-tractability for discrete optimal stopping problems with complexity bounded by ε^{-4} log^{d+2}(1/ε).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Weighted Stochastic Mesh algorithm to approximate values of optimal stopping problems for Markov chains in discrete and continuous time. It proves that in discrete time the algorithm's complexity stays bounded by ε^{-4} log^{d+2}(1/ε), where d is the dimension of the chain, which means the work grows only logarithmically with dimension as accuracy improves. This establishes semi-tractability, a property that lets the method remain practical for higher-dimensional problems. In continuous time the derived bounds improve on prior results even though semi-tractability is not shown. The claims rest on a numerical illustration that supports the theoretical rates.

Core claim

The WSM algorithm leads to semi-tractability of the corresponding optimal stopping problems in the sense that its complexity is bounded in order by ε^{-4} log^{d+2}(1/ε) with d being the dimension of the underlying Markov chain. In the continuous-time setting the approach yields complexity bounds that are the tightest among those known for existing algorithms.

What carries the argument

The Weighted Stochastic Mesh (WSM) algorithm, which approximates continuation values via a weighted collection of simulated paths drawn from the underlying Markov chain.

If this is right

  • Discrete-time optimal stopping problems become solvable with work that grows only logarithmically in dimension.
  • Explicit complexity estimates apply uniformly to both discrete- and continuous-time formulations.
  • The continuous-time bounds improve on all previously published estimates for comparable algorithms.
  • The method supplies a concrete route to high-dimensional computation without exponential dependence on dimension.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The discrete-time result indicates that similar mesh-weighting ideas could control complexity in related stochastic control tasks.
  • Combining the weighting scheme with standard variance-reduction steps might further tighten the observed rates.
  • The bounds suggest that high-dimensional American-style contracts could be priced at polynomial cost in accuracy once the mesh is constructed.

Load-bearing premise

The semi-tractability bound holds only when the weighting scheme and the discrete-time Markov chain satisfy the regularity conditions used in the error analysis.

What would settle it

Finding a discrete-time optimal stopping problem on a Markov chain where the WSM method requires more than order ε^{-4} log^{d+2}(1/ε) operations to reach accuracy ε would falsify the complexity claim.

Figures

Figures reproduced from arXiv: 1906.09431 by D. Belomestny, J. Schoenmakers, M. Kaledin.

Figure 1
Figure 1. Figure 1: Lower bounds for the price of a one-dimensional American put op [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
read the original 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 $\varepsilon^{-4}\log^{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a Weighted Stochastic Mesh (WSM) algorithm for approximating solutions to discrete- and continuous-time optimal stopping problems. For the discrete-time case it claims to prove semi-tractability, i.e., that the complexity is bounded by O(ε^{-4} log^{d+2}(1/ε)) where d is the dimension of the underlying Markov chain; for the continuous-time case it derives complexity bounds that are the tightest known in the literature but do not achieve semi-tractability. The claims are illustrated by a numerical example.

Significance. If the discrete-time complexity bound is rigorously established under clearly stated assumptions, the result would constitute a meaningful advance for high-dimensional Bermudan-style problems in computational finance, because the only polynomial dependence on dimension appears inside a logarithm. The paper also supplies the first explicit comparison of continuous-time bounds across existing mesh-type algorithms.

major comments (2)
  1. [§4 and main theorem] §4 (discrete-time complexity analysis) and the statement of the main theorem: the claimed rate ε^{-4} log^{d+2}(1/ε) is derived under a weighting scheme whose variance and bias control must rely on regularity of the transition kernel (existence of a density bounded near mesh points, or at least local Lipschitz continuity). The manuscript does not list these conditions explicitly in the theorem statement, so it is unclear whether the bound survives for the minimal setting of finite-moment Markov chains that is standard for high-dimensional option pricing.
  2. [Dynamic-programming recursion] Dynamic-programming recursion (Eq. (12) or equivalent): the proof must show that the recursion does not accumulate extra polynomial factors in d when the payoff is merely integrable. If the integrability assumption is only L^1 or L^2 without higher moments, the log^{d+2} term may be lost; the paper should state the precise moment condition used to close the induction.
minor comments (2)
  1. [Numerical example] The numerical example should report the observed empirical complexity (wall-clock time versus ε) for at least two values of d and compare it directly with the theoretical exponent.
  2. [Notation] Notation for the mesh points and the weighting function should be introduced once and used consistently; several symbols appear to be redefined between the discrete and continuous sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major comments point by point below. Both can be resolved by making the underlying assumptions explicit in the theorem statements and proofs; we will incorporate these clarifications in a revised version of the manuscript.

read point-by-point responses

  1. Referee: [§4 and main theorem] §4 (discrete-time complexity analysis) and the statement of the main theorem: the claimed rate ε^{-4} log^{d+2}(1/ε) is derived under a weighting scheme whose variance and bias control must rely on regularity of the transition kernel (existence of a density bounded near mesh points, or at least local Lipschitz continuity). The manuscript does not list these conditions explicitly in the theorem statement, so it is unclear whether the bound survives for the minimal setting of finite-moment Markov chains that is standard for high-dimensional option pricing.

    Authors: We agree that the regularity conditions should be stated explicitly. The variance and bias analysis in §4 relies on the transition kernel admitting a density that is bounded in a neighborhood of the mesh points (or satisfying local Lipschitz continuity). The semi-tractability bound is proved under these conditions together with finite second moments. We will revise the statement of the main theorem to list these kernel regularity assumptions explicitly and add a remark clarifying that the result does not claim to hold under only finite-moment assumptions without the density/Lipschitz control. revision: yes

  2. Referee: [Dynamic-programming recursion] Dynamic-programming recursion (Eq. (12) or equivalent): the proof must show that the recursion does not accumulate extra polynomial factors in d when the payoff is merely integrable. If the integrability assumption is only L^1 or L^2 without higher moments, the log^{d+2} term may be lost; the paper should state the precise moment condition used to close the induction.

    Authors: The induction in the dynamic-programming recursion is closed under the assumption of finite second moments of the payoff and the weighted continuation-value estimators. With this L^2 integrability the error propagation introduces no additional polynomial factors in d; the log^{d+2}(1/ε) dependence originates exclusively from the mesh-size choice and the weighting. We will add an explicit statement of the second-moment condition in the theorem and in the paragraph following the recursion to make the induction closure transparent. revision: yes

Circularity Check

0 steps flagged

No circularity: complexity bound derived from algorithm analysis

full rationale

The paper derives the semi-tractability bound ε^{-4}log^{d+2}(1/ε) for the discrete-time WSM algorithm via explicit error analysis on the weighted mesh estimator and dynamic programming recursion. The bound follows from controlling bias and variance terms under stated Markov chain and weighting assumptions; it is not obtained by fitting parameters to data or by renaming an input quantity. No self-citation is load-bearing for the central claim, and the derivation does not reduce to a tautology or self-referential definition. The result is therefore self-contained as a mathematical proof rather than a re-expression of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5676 in / 1057 out tokens · 42367 ms · 2026-05-25T18:11:08.880810+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Comparing optimal convergence rate of stochastic mesh and least squares method for bermudan option pricing

    Ankush Agarwal and Sandeep Juneja. Comparing optimal convergence rate of stochastic mesh and least squares method for bermudan option pricing. In Proceedings of the 2013 Winter Simulation Conference: Simu- lation: Making Decisions in a Complex World , pages 701–712. IEEE Press, 2013

    work page 2013

  2. [2]

    Densit´ e des diffusions en temps petit: d´ eveloppements asymptotiques

    Robert Azencott. Densit´ e des diffusions en temps petit: d´ eveloppements asymptotiques. I. In Seminar on probability, XVIII, volume 1059 of Lecture Notes in Math. , pages 402–498. Springer, Berlin, 1984

    work page 1984

  3. [3]

    A quantization tree method for pricing and hedging multidimensional American options

    Vlad Bally, Gilles Pag` es, and Jacques Printems. A quantization tree method for pricing and hedging multidimensional American options. Math. Finance, 15(1):119–168, 2005

    work page 2005

  4. [4]

    Advanced Simulation-Based Methods for Optimal Stopping and Control: With Applications in Finance

    Denis Belomestny and John Schoenmakers. Advanced Simulation-Based Methods for Optimal Stopping and Control: With Applications in Finance . Springer, 2018

    work page 2018

  5. [5]

    Broadie and P

    M. Broadie and P. Glasserman. A stochastic mesh method for pricing high-dimensional American options. Journal of Computational Finance , 7(4):35–72, 2004

    work page 2004

  6. [6]

    An analysis of a least squares regression method for american option pricing

    Emmanuelle Cl´ ement, Damien Lamberton, and Philip Protter. An analysis of a least squares regression method for american option pricing. Finance and Stochastics, 6(4):449–471, 2002

    work page 2002

  7. [7]

    Dacunha-Castelle and D

    D. Dacunha-Castelle and D. Florens-Zmirou. Estimation of the coefficients of a diffusion from discrete observations. Stochastics, 19(4):263–284, 1986

    work page 1986

  8. [8]

    On estimating the diffusion coefficient from dis- crete observations

    Dani´ ele Florens-Zmirou. On estimating the diffusion coefficient from dis- crete observations. J. Appl. Probab., 30(4):790–804, 1993

    work page 1993

  9. [9]

    Beating the curse of dimensionality in options pricing and optimal stopping

    David A Goldberg and Yilun Chen. Beating the curse of dimensionality in options pricing and optimal stopping. arXiv preprint arXiv:1807.02227, 2018. 22

    work page arXiv 2018

  10. [10]

    Variational in- equalities and the pricing of american options

    Patrick Jaillet, Damien Lamberton, and Bernard Lapeyre. Variational in- equalities and the pricing of american options. Acta Applicandae Mathe- matica, 21(3):263–289, 1990

    work page 1990

  11. [11]

    A simple numerical method for pricing an american put option

    Beom Jin Kim, Yong-Ki Ma, and Hi Choe. A simple numerical method for pricing an american put option. Journal of Applied Mathematics , 2013, 02 2013

    work page 2013

  12. [12]

    Maximum-likelihood estimation for diffusion processes via closed-form density expansions

    Chenxu Li. Maximum-likelihood estimation for diffusion processes via closed-form density expansions. Ann. Statist., 41(3):1350–1380, 2013

    work page 2013

  13. [13]

    Longstaff and E.S

    F.A. Longstaff and E.S. Schwartz. Valuing american options by simulation: a simple least-squares approach. Review of Financial Studies , 14(1):113– 147, 2001

    work page 2001

  14. [14]

    Erich Novak and Henryk Wo´ zniakowski.Tractability of multivariate prob- lems. Vol. 1: Linear information , volume 6 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Z¨ urich, 2008

    work page 2008

  15. [15]

    Using randomization to break the curse of dimensionality

    John Rust. Using randomization to break the curse of dimensionality. Econometrica: Journal of the Econometric Society , pages 487–516, 1997

    work page 1997

  16. [16]

    Tsitsiklis and B

    J. Tsitsiklis and B. Van Roy. Regression methods for pricing complex american style options. IEEE Trans. Neural. Net., 12(14):694–703, 2001

    work page 2001

  17. [17]

    Quantitative error estimates for a least-squares monte carlo algorithm for american option pricing

    Daniel Z Zanger. Quantitative error estimates for a least-squares monte carlo algorithm for american option pricing. Finance and Stochastics , 17(3):503–534, 2013. 23

    work page 2013