Guaranteed bounds for optimal stopping problems using kernel-based non-asymptotic uniform confidence bands

Martin Glanzer, Sebastian Maier and Georg Ch. Pflug

European Journal of Operational Research, 2025, vol. 327, issue 1, 162-173

Abstract: In this paper, we introduce an approach for obtaining probabilistically guaranteed upper and lower bounds on the true optimal value of stopping problems. Bounds of existing simulation-and-regression approaches, such as those based on least squares Monte Carlo and information relaxation, are stochastic in nature and therefore do not come with a finite sample guarantee. Our data-driven approach is fundamentally different as it allows replacing the sampling error with a pre-specified confidence level. The key to this approach is to use high- and low-biased estimates that are guaranteed to over- and underestimate, respectively, the conditional expected continuation value that appears in the stopping problem’s dynamic programming formulation with a pre-specified confidence level. By incorporating these guaranteed over- and underestimates into a backward recursive procedure, we obtain probabilistically guaranteed bounds on the problem’s true optimal value. As a byproduct we present novel kernel-based non-asymptotic uniform confidence bands for regression functions from a reproducing kernel Hilbert space. We derive closed-form formulas for the cases where the data-generating distribution is either known or unknown, which makes our data-driven approach readily applicable in a range of practical situations including simulation. We illustrate the applicability of the proposed bounding procedure by valuing a Bermudan put option.

Keywords: Stochastic programming; Optimal stopping; Finite sample guarantees; Reproducing kernel Hilbert spaces; Approximate dynamic programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725004126
Full text for ScienceDirect subscribers only

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:eee:ejores:v:327:y:2025:i:1:p:162-173

DOI: 10.1016/j.ejor.2025.05.028

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().