Primal and dual optimal stopping with signatures

Bayer, Christian; Pelizzari, Luca; Schoenmakers, John Article — Published Version Primal and dual optimal stopping with signatures Finance and Stochastics Provided in Cooperation with: Springer Nature Suggested Citation: Bayer, Christian; Pelizzari, Luca; Schoenmakers, John (2025) : Primal and dual optimal stopping with signatures, Finance and Stochastics, ISSN 1432-1122, Springer, Berlin, Heidelberg, Vol. 29, Iss. 4, pp. 981-1014, https://doi.org/10.1007/s00780-025-00570-8 This Version is available at: https://hdl.handle.net/10419/330659 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Finance and Stochastics (2025) 29:981–1014 https://doi.org/10.1007/s00780-025-00570-8 Primal and dual optimal stopping with signatures Christian Bayer1·Luca Pelizzari1,2 ·John Schoenmakers1 Received: 7 December 2023 / Accepted: 4 November 2024 / Published online: 16 June 2025 © The Author(s) 2025 Abstract We propose two signature-based methods to solve an optimal stopping problem – that is, to price American options – in non-Markovian frameworks. Both methods rely on a global approximation result for Lp-functionals on rough-path spaces, using linear functionals of robust, rough-path signatures. In the primal formulation, we present a non-Markovian generalisation of the famous Longstaff–Schwartz algorithm, using linear functionals of the signature as regression basis. For the dual formulation, we parametrise the space of square-integrable martingales using linear functionals of the signature and apply a sample average approximation. We prove convergence for both methods and present first numerical examples in non-Markovian and nonsemimartingale regimes. Keywords Signature ·Optimal stopping ·Rough paths ·Monte Carlo ·Rough volatility Mathematics Subject Classification 60L10 ·60L20 ·91G20 ·91G60 JEL Classification C63 ·G12 All authors gratefully acknowledge funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+(EXC-2046/1, project ID: 390685689). ✉L. Pelizzari [email protected] C. Bayer [email protected] J. Schoenmakers [email protected] 1Weierstrass Institut, Mohrenstrasse 39, 10117 Berlin, Germany 2Institut für Mathematik, Technische Universität Berlin, Str. des 17. Juni 136, 10587 Berlin, Germany 982 C. Bayer et al. 1Introduction Stochastic processes with memory play a more and more important role in the modelling of financial markets. In the modelling of equity markets, rough stochastic volatility models are now part of the standard toolbox; see e.g. Gatheral et al. [27] and Bayer et al. [4]. In the same area, path-dependent stochastic volatility models (e.g. Guyon et al. [30]) are a very powerful alternative for capturing memory effects. Processes with memory are also an essential tool for modelling the microstructure of financial markets, driven by the market practice of splitting large orders into many medium-size ones, as well as by the reaction of algorithmic traders to such orders. Seen from outside, this materialises as self-excitation of the order flow and, consequently, Hawkes processes are a fundamental tool for modelling order flows; see e.g. Bouchaud et al. [15, Chap. 9.4]. Beyond finance, processes with memory play an important role in the modelling of many natural phenomena (e.g. earthquakes, see Ogata et al. [35]) or social phenomena. In this paper, we study optimal stopping problems in non-Markovian frameworks, that is, the underlying price is possibly a stochastic process with memory. For concreteness’ sake, let us introduce two processes determining the optimal stopping problem: an underlying state process X, together with its natural filtration 𝔽X, and a reward process Z, which is 𝔽X-adapted – think about X=(S, v) for a stock price process Sdriven by a stochastic variance process vand Zt=ϕ(t,St). The optimal stopping problem then consists of solving the optimisation problem y0=sup τ∈𝒮0 E[Zτ],(1.1) where 𝒮0denotes the set of 𝔽X-stopping times valued in [0,T]for some T>0. We merely assume α-Hölder-continuity for Xin our framework, see Sect. 3.1 below, in particular allowing non-Markovian and non-semimartingale state processes X. The lack of a Markov property leads to severe theoretical and computational challenges in the context of optimal control problems, and thus in particular in the optimal stopping problem (1.1). Indeed, the primary analytical and numerical framework for stochastic optimal control problems arguably is the associated Hamilton– Jacobi–Bellman (HJB) PDE, which in the context of optimal stopping leads to socalled free-boundary problems; see Peskir and Shiryaev [36, Chap. 4]. When the state process is not a Markov process, such PDEs do not exist a priori. As noted above, infinite-dimensional (BS)PDE formulations can be given; see for instance Bayer et al. [6] for a BSPDE description of the American option price in rough volatility models. When the underlying dynamics is of stochastic Volterra type, pathdependent HJB PDEs could probably be derived following the approach of Bonesini and Jacquier [14]. However, most numerical approximation methods crucially rely on the Markov property as well. It should be noted that at least intuitively, all processes with memory can be turned into Markov processes by adding the history to the current state – but see e.g. Carmona and Coutin [16] for a more sophisticated approach in the case of fractional Brownian motion. Hence theoretical and numerical methods from the Markovian world are in principle available, but at the cost of having to work in infinitedimensional (often very carefully drafted, see e.g. Cuchiero and Teichmann [21]) Primal and dual optimal stopping with signatures 983 state spaces. On the other hand, Markovian approximations, i.e., finite-dimensional Markov processes closely mimicking the process with memory, can sometimes be a very efficient surrogate model, especially when high accuracy is achievable with low-dimensional Markovian approximations; see e.g. Bayer and Breneis [3]. Inspired by many successful uses in machine learning (for time-series data), Kalsi et al. [31] introduced a model-free method for numerically solving a stochastic optimal execution problem. The method is based on the path signature, see e.g. Friz and Victoir [26, Chap. 7], and is applicable in non-Markovian settings. This approach was extended to optimal stopping problems in Bayer et al. [5], where stopping times were parametrised as first hitting times of affine hyperplanes in the signature space. A rigorous mathematical analysis of that method was performed and numerical examples verifying its efficiency were provided. The signature X<∞of a path X:[0,T]→ℝdis given (at least formally) as the infinite collection of iterated integrals, that is, for 0 ≤t≤s≤T, X<∞ s,t ={︃∫︂t s∫︂tk s···∫︂t2 s dXi1 t1···dXik tk:i1,...,i k∈{1,...,d},k ≥0}︃. The signature characterises the history of the corresponding trajectory and hence provides a systematic way of “lifting” a process with memory to a Markov process by adding the past to the state. Relying only on minimal regularity assumptions, the corresponding encoding is efficient and has nice algebraic properties. In many ways, (linear functionals of) the path signature behaves like an analogue of polynomials on path space and can be seen as a canonical choice of basis functions on path space. For example, a Stone–Weierstrass type result shows that when restricted to compacts, continuous functionals on path spaces can be approximated by linear functionals of the signature, that is, by linear combinations of iterated integrals; see for instance Kalsietal.[31, Lemma 3.4]. As a first contribution, we provide in Sect. 2an abstract approximation result on α-Hölder rough-path spaces by linear functionals of the robust signature, with respect to the Lp-norm; see Theorem 2.8 below. As a direct consequence and under very mild assumptions, we can show that for any 𝔽X-progressive process (ξt)t∈[0,T ], we can find a sequence (ℓn)n∈ℕof linear functionals on the state space of the signature such that lim n→∞E[︃∫︂T 0(ξt−⟨X<∞ 0,t ,ℓ n⟩)2dt]︃=0;(1.2) see Corollary 2.9 below for details. This result is in marked contrast to the standard universal approximation result for signatures as usually formulated, which only provides uniform convergence on compact subsets of the path space. Let us mention two related works on global approximation with signatures. First, in Cuchiero et al. [20], the authors study global signature approximations based on a version of the Stone–Weierstrass result for so-called weighted spaces;see[20, Theorem 3.6]. Compared to our theory, while they do not require a robust version of the signature, such weighted spaces need to be crafted carefully. Secondly, in the recent work by Alaifari and Schell [1], the authors obtain (independently from us) a similar global Lp-approximation result for robust signatures of bounded variation paths, see [1, 984 C. Bayer et al. Proposition 4.5], but based on a monotone class rather than a Stone–Weierstrass argument. Returning to the optimal stopping problem (1.1), we generalise in Sect. 3two standard techniques from the Markovian to the non-Markovian case by using signatures, namely the Longstaff–Schwartz algorithm [33] and Rogers’ dual martingale method [37]. Denoting by Ythe Snell envelope for the optimal stopping problem, see Sect. 3.2 below for more details, the Longstaff–Schwartz algorithm is based on the dynamic programming principle, that is, Yt=max(Zt,E[Yt+Δt |ℱX t]). If Xis a Markov process, then E[Yt+Δt |ℱX t]=E[Yt+Δt |Xt], which can be efficiently computed by using regression (least-squares Monte Carlo). In the nonMarkovian case, an application of the global approximation result in Theorem 2.8, i.e., the convergence in (1.2), shows that (under minimal assumptions) a Longstaff– Schwartz algorithm converges when the conditional expectation is approximated by linear functionals of the signature, that is, t↦→ E[Yt+Δt |ℱX t]≈⟨X<∞ 0,t ,ℓ⟩; see Proposition 3.3. Regarding the dual method, we rely on Rogers’ characterisation that y0=inf M∈ℳ2 0 E[︂sup t∈[0,T ](Zt−Mt)]︂, where the inf is taken over all square-integrable martingales Mstarting at 0. If the underlying filtration is Brownian, such martingales can be written as stochastic integrals with respect to a Brownian motion W, that is, Mt=∫︁t 0ξsdWsfor some 𝔽X-progressive process ξ. The approximation result in Theorem 2.8, i.e., the convergence in (1.2), suggests to approximate the integrand by linear functionals of the signature, that is, t↦→ ξt≈⟨X<∞ 0,t ,ℓ⟩, and we prove convergence after taking the infimum over all linear functionals ℓ, i.e., y0=inf ℓE[︃sup t∈[0,T ](︃Zt−∫︂t 0⟨X<∞ 0,s ,ℓ⟩dWs)︃]︃;(1.3) see Proposition 3.8. For numerically solving the dual problem (1.3), we carry out a sample average approximation (SAA) with respect to the coefficients of the linear functional of the signature. For a Markovian environment, a related SAA procedure was earlier proposed in Desai et al. [22] and recently refined in Belomestny and Schoenmakers [11] and Belomestny et al. [10] by using a suitable randomisation. An important feature of the SAA method is that it relies on non-nested Monte Carlo simulation and thus is very fast in comparison to the classical nested Monte Carlo method by Andersen and Broadie [2]. Primal and dual optimal stopping with signatures 985 For both the Longstaff–Schwartz and dual signature methods, we also prove convergence of the finite-sample approximations when the number of samples grows to infinity; see Propositions 3.4 and 3.10. It is worth noting that after independent resimulations, the Longstaff–Schwartz algorithm yields lower-biased, whereas the dual method gives upper-biased values to the optimal stopping problem (1.1), and thus applying both methods produces confidence intervals for the true value of y0. Finally, in Sect. 4, we provide first numerical examples based on the primal and dual signature-based approaches in two non-Markovian frameworks. First, in Sect. 4.1, we study the task of optimally stopping fractional Brownian motion for a wide range of Hurst parameters H∈(0,1), representing the canonical choice of a state process outside of the Markov regime. The same problem was already studied in Becker et al. [8] and later in Bayer et al. [5], and we compare our lower (resp. upper) bounds with the results therein. Secondly, in Sect. 4.2, we consider the problem of computing American option prices in the rough Bergomi model (see Bayer et al. [4]), and we compare our price intervals with Bayer et al. [7] (resp. Goudenege et al. [29]), where lower bounds were computed in the same model. 1.1 Notation For d,K ∈ℕ, we define the so-called extended tensor algebra and the K-step truncation thereof by T(︁(ℝd))︁=∏︂ k≥0 (ℝd)⊗k,T ≤K(ℝd)= K ∏︂ k=0 (ℝd)⊗k, where we use the convention (ℝd)⊗0=ℝ. For more details, including natural operations such as sum +and product ⋆on these spaces, see for instance Friz and Victoir [26, Sect. 7.2.1]. For any word w=i1... i nfor some n∈ℕwith letters i1,...,i n∈{1,...,d}, we define the degree of was the length of the word, that is, deg(w) =n, and denote by ∅the empty word with deg(∅)=0. Moreover, for a∈T((ℝd)), we denote by ⟨a,w⟩the element of a(n) ∈(ℝd)⊗ncorresponding to the basis element ei1⊗···⊗ein, where {e1,...,e d}is the standard basis of ℝd. Denoting by 𝒲dthe linear span of words, the pairing above can be extended linearly to ⟨·,·⟩:T((ℝd))×𝒲d→ℝ. For an element ℓ∈𝒲d, i.e., ℓ=λ1w1+···+λnwn for some words w1,...,w nand scalars λ1,...,λ n∈ℝ, we define the degree of ℓby deg(ℓ) := max1≤i≤ndeg(wi), and for K∈ℕ, we denote by 𝒲d ≤K⊆𝒲dthe subset of elements ℓwith deg(ℓ) ≤K. For two words wand v, we denote by ∃ the shuffle product given by w ∃ ∅=∅ ∃ w=w, wi ∃ vj := (w ∃ vj )i +(wi ∃ v)j, i,j ∈{1,...,d},(1.4) which bilinearly extends to the span 𝒲dof words. We further define the free nilpotent Lie group over ℝdby G(︁(ℝd))︁={︁a∈T(︁(ℝd))︁\{0}:⟨a,w⟩⟨a,v⟩=⟨a,w ∃ v⟩,∀w,v ∈𝒲d}︁; 986 C. Bayer et al. see [26, Chap. 7.5] for details. For α∈(0,1), we denote by Cα([0,T];ℝd)the space of α-Hölder-continuous paths X, that is, X:[0,T]→ℝdsuch that ∥X∥α;[0,T ]=sup 0≤s<t≤T |Xt−Xs| |t−s|α<∞, where |·|denotes the Euclidean norm on ℝd. Denote by Δ2 [0,T ]the standard simplex Δ2 [0,T ]:= {(s, t) ∈[0,T]2:0≤s≤t≤T}.ForL∈ℕand any two-parameter function on the truncated tensor algebra, Δ2 [0,T ]∋(s, t) ↦→ Xs,t =(1,X(1) s,t ,...,X(L) s,t )∈T≤L(ℝd), we denote by ||| ·|||(α,L) the norm given by |||X|||(α,L) := max 1≤ℓ≤L(︃sup 0≤s<t≤T |X(ℓ) s,t | |t−s|ℓα )︃1/ℓ . We denote by Cα g([0,T];ℝd)the space of geometric α-Hölder rough paths Xvalued in ℝd, which is the ||| ·|||(α,L)-closure of L-step signatures of Lipschitz-continuous paths X:[0,T]→ℝdfor L=⌊1/α⌋. More precisely, for every X∈Cα g, there exists a sequence (Xn)n∈ℕ⊆Lip([0,T];ℝd)such that |||Xn−X|||(α,L) →0 as n→∞, where Xnis the L-step signature of Xn, that is, Xn s,t := (︃∫︂s<t1<···<tℓ<t ⊗dXn t1···⊗dXn tℓ:0≤ℓ≤L)︃∈G≤L(ℝd), where the integrals are defined in the Riemann–Stieltjes sense. For the rest of the paper, we always fix L=⌊1/α⌋and use the shorter notation ||| ·|||α:= ||| ·|||(α,⌊1/α⌋). For any X∈Cα g, we denote by X<∞the rough-path signature, which is the unique (up to tree-like equivalence ∼t, see Boedihardjo et al. [12] for details) path from Lyons’ extension theorem (Lyons [34, Theorem 3.7]), that is, Δ2 [s,t]:[0,T]∋(s, t) ↦→ X<∞ s,t =(1,X(1) s,t ,...,X(L) s,t ,X(L+1) s,t ,...)∈G(ℝd), such that ∥X(k)∥kα <∞,∀k≥0,X<∞ s,t =X<∞ s,u ⋆X<∞ u,t ,s≤u≤t, where the latter is called Chen’s relation. Finally, by considering time-augmented paths (ˆ︁ Xt)=(t, Xt)and their geometric rough-path lifts ˆ︁ X, the signature map becomes unique due to the strictly monotone time component. We denote by ˆ︁ Cα g([0,T];ℝd+1)the space of geometric α-Hölder rough-path lifts of (ˆ︁ Xt)=(t, Xt), X∈Cα([0,T];ℝd). We often use the shorter notation ˆ︁ Cα gwhen it is clear from the context that we are working on the fixed time interval [0,T]. Primal and dual optimal stopping with signatures 987 2 Global approximation with rough-path signatures In this section, we present the theoretical foundation of this paper, which consists of a global approximation result based on robust rough-path signatures. 2.1 The space of stopped rough paths For α∈(0,1), we consider an α-Hölder-continuous path X:[0,T]→ℝdstarting at X0=x0∈ℝdand denote by Xa geometric rough-path lift of the time-augmentation (t, Xt), that is, X∈ˆ︁ Cα g([0,T];ℝd+1). Definition 2.1 For any α∈(0,1)and T>0, the space of stopped ˆ︁ Cα g-paths is defined by the disjoint union Λα T:= ⋃︂ t∈[0,T ]ˆ︁ Cα g([0,t];ℝd+1). Moreover, we equip the space Λα Twith the final topology induced by the map ϕ:[0,T]× ˆ︁ Cα g([0,T];ℝd+1)→Λα T,ϕ(t,x)=x|[0,t]. The reason to work on this space is the following. If Xis a stochastic process and Xdenotes the random geometric lift of (t, Xt), we define ℱX t=σ(X0,s :s≤t) for 0 ≤t≤T, i.e., the natural filtration generated by X. In Lemma 2.4 below, we show that any 𝔽X-progressive process (At)t∈[0,T ]can be written as At=f(X|[0,t]), where fis a measurable function on Λα T. Thus progressively measurable processes can be thought of as measurable functionals on Λα T, and we discuss approximation results for the latter below. Similar spaces have already been considered in relation with functional Itô calculus in Cont and Fournié [19] and Dupire [23], for p-rough paths in Kalsi et al. [31], and more recently in relation with optimal stopping in Bayer et al. [5]. Remark2.2 One can also introduce a metric dΛon the space Λα T.Lety∈Λα T, that is, there exists 0 ≤s≤Tsuch that y=y|[0,s]∈ˆ︁ Cα g([0,s]).Nowforanyt≥s, we can extend y|[0,s]to a geometric rough path ˜ y|[0,t]∈ˆ︁ Cα g([0,t])as follows. By geometricity, there exists a sequence of smooth paths (u, yn u)u∈[0,s]such that the (canonical) rough-path lifts converge to y|[0,s]. Then we define ˜ y|[0,t]to be the rough-path limit of the canonical lift of u↦→ (u, yn u∧s)for 0 ≤u≤t. This construction can be used to define dΛ(x|[0,t],y|[0,s]):= x−˜ yα:[0,t]+|t−s|,s≤t. It has been proved in [5, Lemma A.1] that the topology of the metric space (Λp T,d Λ), where Λp Tdenotes the space of stopped p-rough paths (see [5, Sect. 3]), coincides with the final topology, and the space of stopped geometric rough paths is Polish. A similar argument can be done for the α-Hölder case by replacing the p-variation norm by the α-Hölder-norm and using the fact that ˆ︁ Cα gis Polish; see Friz and Victoir [26, Proposition 8.27]. 988 C. Bayer et al. Remark 2.3 Let Xbe a stochastic process valued in ˆ︁ Cα g([0,T];ℝd+1).Itisdiscussed in [26, Appendix A.1] that Xcan be regarded as a random variable valued in ˆ︁ Cα g([0,T];ℝd+1), and its law μXis then a Borel measure on the Borel σ-algebra ℬαwith respect to ||| ·|||α. Moreover, define the product measure dμ := dt ⊗dμX. For the surjective map ϕ:[0,T]× ˆ︁ Cα g([0,T];ℝd+1)→Λα Tdefined above, we can define the pushforward measure ˆ︁μon Λα T, in symbols ˆ︁μ:= ϕ#μ=μ◦ϕ−1, which is given by ˆ︁μ(A) := μ(︁ϕ−1(A))︁for all A∈ℬ(Λα T). Consider the space ℍ2of 𝔽X-progressive processes Asuch that ∥A∥2 ℍ2:= E[︃∫︂T 0A2 sds]︃<∞.(2.1) The following result justifies the consideration of the space Λα T. Lemma 2.4 For any process A∈ℍ2and α∈(0,1),there exists a measurable function f:(Λα T,ℬ(Λα T)) →(ℝ,ℬ(ℝ)) such that At=f(X|[0,t])almost everywhere. Proof Consider the space of elementary 𝔽X-progressive processes, that is, processes of the form An t(ω) := ξn 0(ω)1{0}(t) + mn−1 ∑︂ j=1 1(tn j,tn j+1](t)ξn tj(ω), (2.2) where 0 ≤tn 0<··· <t n mn≤Tand ξn tjis an ℱX tj-measurable, square-integrable random variable. A standard result for the construction of stochastic integrals shows that this space is dense in ℍ2; see e.g. Karatzas and Shreve [32, Lemma 3.2.4]. Thus we can find Anof the form (2.2) such that An→Afor almost every (t, ω). Since the random variable ξn tjis measurable with respect to the σ-algebra ℱX tj:= σ(X0,s :s≤tj)=σ(X|[0,tj]), there exists by the Doob–Dynkin lemma a Borel-measurable function Fn j:ˆ︁ Cα g([0,t j];ℝd+1)→ℝ such that ξn tj(ω) =Fn j(X|[0,tj](ω)). Then the functions [0,T]× ˆ︁ Cα g∋(t, x)↦→ 1(tn j,tn j+1](t)F n j(x|[0,tj]) are (ℬ([0,T])⊗ℱX T)-measurable, and therefore such is the function Fn(t, x):= Fn 0(x0)1{0}(t) + mn−1 ∑︂ j=1 1(tn j,tn j+1](t)F n j(x|[0,tj]). Primal and dual optimal stopping with signatures 995 3.1 Framework and problem formulation Suppose we have a complete filtered probability space (Ω, ℱ,𝔽=(ℱt)t∈[0,T ],P) for some T>0, fulfilling the usual conditions, and fix α∈(0,1). For any 𝔽-adapted and α-Hölder-continuous stochastic process (Xt)t∈[0,T ]taking values in ℝdwith X0=x0, we consider –X∈ˆ︁ Cα g, a geometric α-Hölder rough-path lift of (t, Xt)such that its law μX fulfils Assumption 2.6; –X<∞, the robust rough-path signature introduced in Sect. 2.3; –(Zt)t∈[0,T ], a real-valued 𝔽X-adapted process such that supt∈[0,T ]|Zt|∈L2. The optimal stopping problem then reads y0=sup τ∈𝒮0 E[Zτ],(3.1) where 𝒮0denotes the set of 𝔽X-stopping-times valued in [0,T]. Remark 3.1 Notice that the framework described above is very general in two ways. First, we only assume α-Hölder-continuity for the state process X, including in particular non-Markovian and non-semimartingale regimes which one encounters for instance in rough volatility models; see Sect. 4.2. Secondly, by considering the projection X↦→ (t, Xt)onto the first coordinate, our framework includes for any payoff function ϕ:[0,T]×ℝd→ℝthe more common form of the optimal stopping problem y0=sup τ∈𝒮0 E[ϕ(τ,Xτ)]. Remark 3.2 In general, there is no canonical way of lifting a process (t, Xt)to a random rough path X, and often careful justification is required, for instance based on a rough-path version of the Kolmogorov criterion; see Friz and Hairer [25, Theorem 3.1]. However, for a big class of processes (e.g. semimartingales, Gaussian processes, one-dimensional processes), there are canonical choices for random geometric rough-path lifts, and we explain below in Sect. 4how to do it. Moreover, we always look at lifts such that 𝔽X=𝔽X, that is, the optimal stopping problem has the same underlying information when observing Xor X. 3.2 Primal optimal stopping with signatures First, we present a method to compute a lower-biased approximation yL 0≤y0to the optimal stopping problem (3.1). More precisely, we construct a regression-based approach, generalising the famous algorithm from Longstaff and Schwartz [33], returning a suboptimal exercise strategy. Let us first quickly describe the main idea of most regression-based approaches. Replacing the interval [0,T]by a finite grid {0=t0<t 1<···<t N=T},the discrete optimal stopping problem reads yN 0=sup τ∈𝒮N 0 E[Zτ], 996 C. Bayer et al. where 𝒮N nis the set of stopping times taking values in {tn,...,t N}for n=0,...,N, with respect to the discrete filtration 𝔽X,N =(ℱX tn)n=0,...,N . We define the discrete Snell envelope by YN tn=esssup τ∈𝒮N n E[Zτ|ℱX tn],0≤n≤N, (3.2) and one can show that YNsatisfies the discrete dynamic programming principle (DPP) YN tn=max(Ztn,E[YN tn+1|ℱX tn]), n =0,...,N −1;(3.3) see for instance Peskir and Shiryaev [36, Theorem 1.2]. Now the key idea of most regression-based approaches, such as for instance Longstaff and Schwartz [33], is that by assuming that Xis a Markov process, one can choose a suitable family of basis functions (bk)and apply least-squares regression to approximate E[YN tn+1|ℱX tn]≈ D ∑︂ k=0 αkbk n(Xtn), 0≤n≤N−1,α k∈ℝ,∀k≤D, (3.4) and then make use of the DPP to recursively approximate YN 0=yN 0. Of course, the approximation of the conditional expectations in (3.4) heavily relies on the Markov property, and thus one cannot expect such an approximation to converge in nonMarkovian settings. Returning to our framework, we need to replace (3.4) by a suitable approximation for the conditional expectations E[YN tn+1|ℱX tn]=fn(X|[0,tn]), 0≤n≤N−1. The universality result in Theorem 2.8 now suggests approximating fnby a sequence of linear functionals of the robust signature, that is, fn(X|[0,tn])≈⟨X<∞ 0,tn,ℓ⟩,ℓ∈𝒲d+1, where 𝒲d+1is the linear span of words introduced in Sect. 1.1. 3.2.1 Longstaff–Schwartz with signatures In this section, we present a version of the Longstaff–Schwartz (LS) algorithm [33], using signature-based least-squares regression. A convergence analysis for the LS algorithm was presented in Clément et al. [18], and combining their techniques with the universality of the signature allows us to recover a convergent algorithm. The main idea of the LS algorithm is to reformulate the DPP (3.3) for stopping times by taking advantage of the fact that optimal stopping times can be expressed in terms of the Snell envelope. More precisely, it is proved in Peskir and Shiryaev [36, Theorem 1.2] that the stopping times τn:= min{tm≥tn:YN tm=Ztm}for 0 ≤n≤N are optimal in (3.2), and hence one recursively defines τN=tN, τn=tn1{Ztn≥E[Zτn+1|ℱX tn]} +τn+11{Ztn<E[Zτn+1|ℱX tn]},n=0,...,N −1. Primal and dual optimal stopping with signatures 997 Now for any truncation level K∈ℕfor the signature and some fixed n=0,...,N −1, assume we are given an approximation τK n+1of τn+1. Then we approximate the conditional expectation E[ZτK n+1|ℱX tn]by solving the minimisation problem ℓ∗:=ℓ∗,n,K =argmin ℓ∈𝒲d+1 ≤K ∥ZτK n+1−⟨X≤K 0,tn,ℓ⟩∥L2,n=0,...,N −1.(3.5) Setting ψn,K (x)=⟨x≤K,ℓ ∗,n,K ⟩∈Lλ sig, we define the approximating sequence of stopping times τK N=tN, τK n=tn1{Ztn≥ψn,K (X|[0,tn])}+τK n+11{Ztn<ψn,K (X|[0,tn])},n=0,...,N −1. The following result shows convergence as the depth of the signature goes to infinity, and the proof is given in Appendix A.1. Proposition 3.3 For all n=0,...,N,we have lim K→∞E[ZτK n|ℱX tn]=E[Zτn|ℱX tn]in L2. In particular,we have yK,N 0=max(Zt0,E[ZτK 1])→yN 0as K→∞. Let us now describe how to numerically solve (3.5) by using Monte Carlo simulations. Besides the truncation of the signature at some level K, we introduce two further approximations steps. First, we replace the signature X<∞by some discretised version X<∞(J ), for example piecewise linear approximation of the iterated integrals, on some fine grid s0=0<s 1<··· <s J=T, such that ⟨X<∞ 0,t (J ), v⟩→⟨X<∞ 0,t ,v⟩in L2as J→∞for all words vand t∈[0,T]. Second, for i=1,...,M i.i.d. sample paths of Zand the discretised and truncated signature X≤K=X≤K(J ), assuming that τK,J n+1is known, we estimate ℓ∗by solving (3.5)via linear least-squares regression. This yields an estimator ℓ∗=ℓ∗,n,J,K,M . Defining ψn,J,K,M (x)=⟨x≤K,ℓ ∗,n,J,K,M ⟩leads to a recursive algorithm for stopping times, for i=1,...,M, τK,J,(i) N=tN, τK,J,(i) n=tn1{Z(i) tn≥ψn,J,K,M (X(i)|[0,tn])}+τK,J,(i) n+11{Z(i) tn<ψn,J,K,M (X(i)|[0,tn])}.(3.6) Then the following law-of-large-numbers-type result holds true, which almost directly follows from Clément et al. [18, Theorem 3.2]; see Appendix A.1. Proposition 3.4 For fixed K,J,we have lim M→∞ 1 M M ∑︂ i=1 Z(i) τK,J,(i) n=E[ZτK,J n]a.s. 998 C. Bayer et al. Moreover,setting yN,K,J,M 0:=max(Zt0,1 M∑︁M i=1Z(i) τK,J,(i) 1 ),we have lim K→∞ lim J→∞ lim M→∞yK,N,J,M 0=yN 0, where the convergence with respect to Mis almost sure convergence. Remark 3.5 The recursion (3.6) of stopping times, resp. the resulting linear functionals of the signature ψn,K,M , provide a stopping policy for each sample path of Z.By re-simulating ˜ Mi.i.d. samples of Zand the signature X<∞, we can notice that the resulting estimator yK,N,J, ˜ M 0is lower-biased, that is, yK,N,J, ˜ M 0≤yN 0, since yN 0is defined by taking the supremum over all possible stopping policies. 3.3 Dual optimal stopping with signatures In this section, we approximate solutions to the optimal stopping problem in its dual formulation, leading to upper bounds yU 0≥y0for (3.1). The dual representation goes back to Rogers [37], where the author shows that under the assumption sup0≤t≤T|Zt|∈L2, the optimal stopping problem (3.1) is equivalent to y0=inf M∈ℳ2 0 E[︂sup t≤T (Zt−Mt)]︂,(3.7) where ℳ2 0denotes the space of square-integrable 𝔽X-martingales starting from 0. Assuming that 𝔽Xis generated by a Brownian motion W, we can prove the following equivalent formulation of (3.7). Remark 3.6 From a financial modelling perspective, assuming that the filtration is generated by an m-dimensional Brownian motion Wis natural in the context of diffusive or rough volatility modelling. In this setting, Wrepresents the driver of m/2assets (semimartingales) and their corresponding m/2 variance processes. Theorem 3.7 Assume 𝔽Xis generated by an m-dimensional Brownian motion W. Then for all M∈ℳ2 0,there exist sequences ℓi=(ℓi n)n∈ℕ⊆𝒲d+1for i=1,...,m such that ∫︂· 0⟨X<∞ 0,s ,ℓ n⟩⊤dWs:= m ∑︂ i=1∫︂· 0⟨X<∞ 0,s ,ℓ i n⟩dWi s−→ M·ucp as n→∞. In particular,the minimisation problem (3.7)can be equivalently formulated as y0=inf ℓ∈(𝒲d+1)mE[︃sup t≤T(︃Zt−∫︂t 0⟨X<∞ 0,s ,ℓ⟩⊤dWs)︃]︃ =inf ℓ1,...,ℓm∈𝒲d+1E[︃sup t≤T(︃Zt− m ∑︂ i=1∫︂t 0⟨X<∞ 0,s ,ℓ i⟩dWi s)︃]︃.(3.8) Primal and dual optimal stopping with signatures 999 Proof By the martingale representation theorem, any square-integrable 𝔽X-martingale can be written as Mt=∫︂t 0α⊤ sdWs= m ∑︂ i=1∫︂t 0αi sdWi s, where (αs)s∈[0,T ]is 𝔽X-progressively measurable and square-integrable. Moreover, since M∈ℳ2 0, it follows that E[M2 T]=E[∫︁T 0|αt|2dt]<∞. From Corollary 2.9, we know that there exist sequences ℓi=(ℓi n)n∈ℕ⊆𝒲d+1for i=1,...,m such that for αi,n t:= ⟨X<∞ 0,t ,ℓ i n⟩,wehave∥αi,n −αi∥ℍ2→0asn→∞. Using Doob’s inequality, we in particular have E[︃(︃sup t≤T∫︂t 0(αn s−αs)⊤dWs)︃2]︃≤C m ∑︂ i=1 E[︃∫︂T 0|αi,n s−αi s|2dt]︃ = m ∑︂ i=1∥αi,n −αi∥2 ℍ2−→ 0. But this readily implies the first claim, that is, ∫︂· 0⟨X<∞ 0,s ,ℓ n⟩⊤dWs−→ ∫︂· 0αsdWs=M·ucp. To show (3.8), since ∫︁· 0⟨X<∞ 0,s ,ℓ n⟩⊤dWsare clearly square-integrable 𝔽X-martingales, we can notice that inf ℓ∈(𝒲d+1)mE[︃sup t≤T(︃Zt−∫︂t 0⟨X<∞ 0,s ,ℓ⟩⊤dWs)︃]︃≥inf M∈ℳ2 0 E[︂sup t≤T (Zt−Mt)]︂=y0. On the other hand, for any fixed square-integrable martingale M, we know there exist sequences of words ℓi=(ℓi n)n∈ℕ⊆𝒲d+1such that lim n→∞sup t≤T(︃Zt−∫︂t 0⟨X<∞ 0,s ,ℓ n⟩⊤dWs)︃=sup t≤T (Zt−Mt)in L2. Therefore E[︂sup t≤T (Zt−Mt)]︂=lim n→∞E[︃sup t≤T(︃Zt−∫︂t 0⟨X<∞ 0,s ,ℓ n⟩⊤dWs)︃]︃ ≥inf ℓ∈(𝒲d+1)mE[︃sup t≤T(︃Zt−∫︂t 0⟨X<∞ 0,s ,ℓ⟩⊤dWs)︃]︃. Taking the infimum over all M∈ℳ2 0yields the claim. □ Next, similarly to the primal case, we translate the minimisation problem (3.8) into a finite-dimensional optimisation problem by discretising the interval [0,T]and 1000 C. Bayer et al. truncating the signature to some level K. More precisely, for 0 =t0<···<t N=T and some K∈ℕ, we reduce the minimisation problem (3.8)to yK,N 0=inf ℓ∈(𝒲d+1 ≤K)m E[︂max 0≤n≤N(Ztn−Mℓ tn)]︂,(3.9) where for any ℓ=(ℓ1,...,ℓ m)∈(𝒲d+1 ≤K)m, we define Mℓ t=∫︂t 0⟨X≤K 0,s ,ℓ⟩⊤dWs= m ∑︂ i=1∫︂t 0⟨X≤K 0,s ,ℓ i⟩dWi s. The discrete version of the dual formulation (3.7) is given by yN 0=inf M∈ℳ2,N 0 E[︂max 0≤n≤N(Ztn−Mtn)]︂, where ℳ2,N 0denotes the space of discrete square-integrable 𝔽X,N -martingales. The following result shows that the minimisation problem (3.9) has a solution and the value converges to yN 0as the level Kof the signature goes to infinity. The proof can be found in Appendix A.2. Proposition 3.8 There exists a minimiser ℓ⋆to (3.9)and |yN 0−yK,N 0|−→0as K→∞. Remark3.9 In a financial context, Propositions 3.3 and 3.8 tell us that yK,N 0converges to the Bermudan option price as K→∞. Moreover, the triangle inequality gives |y0−yK,N 0|≤|y0−yN 0|+|yN 0−yK,N 0|, and hence the finite-dimensional approximations converge to y0as K,N →∞ whenever the Bermudan price converges to the American price. For our numerical examples, we always approximate yN 0for some fixed N, and therefore we do not further investigate the latter convergence here. 3.3.1 Sample average approximation (SAA) We now present a method to approximate the value yK,N 0in (3.9) by using Monte Carlo simulations. This procedure is called sample average approximation (SAA) and we refer to Shapiro [38] for a general and extensive study of this method. Similarly to the primal case, we introduce two further approximation steps. First, let 0=s0<···<s J=Tbe a finer discretisation of [0,T]and denote by Mℓ,J , resp. X<∞(J ), an approximation of the stochastic integral ∫︁⟨X<∞ 0,s ,ℓ⟩dWs, resp. the signature X<∞, by using an Euler scheme. Second, we consider i=1,...,M i.i.d. Primal and dual optimal stopping with signatures 1001 sample paths Z(i),M(i),ℓ,J and replace the expectation in (3.9) by a sample average, leading to the empirical minimisation problem yK,N,J,M 0=inf ℓ∈(𝒲d+1 ≤K)m 1 M M ∑︂ i=1 max 0≤n≤N(Z(i) tn−M(i),ℓ,J tn). (3.10) The following result can be deduced from Shapiro [38, Theorem 4] combined with Proposition 3.8. We refer to Appendix A.2 for the details. Proposition 3.10 For Mlarge enough,there exists a minimiser β⋆to (3.10), and lim K→∞ lim J→∞ lim M→∞yK,N,J,M 0=yN 0, where the convergence with respect to Mis almost sure convergence. Remark 3.11 Let us quickly describe how we solve (3.10) numerically. Consider the number D:= ∑︁K k=0(d +1)k, which corresponds to the number of entries of the K-step signature. Notice that for any element ℓ∈𝒲d+1 ≤K, we have the representation ℓ=λ1w1+···+λDwD, where w1,...,w Dare all possible words of length at most K. Since ⟨X≤K 0,t ,ℓ⟩=∑︁D r=1λr⟨X≤K 0,t ,w r⟩, the minimisation (3.10) has the equivalent formulation yK,N,J,M 0=inf λ∈(ℝD)m 1 M M ∑︂ i=1 max 0≤n≤N(︃Z(i) tn− D ∑︂ r=1 λrM(i),wr,J tn)︃. As described in Desai et al. [22], the above minimisation problem is equivalent to the linear program min x∈ℝM+D 1 M M ∑︂ j=1 xjsubject to Ax ≥b, where A∈ℝM(N+1)×(M+D) with A=[A1,...,A M]⊤, and Ax ≥brepresents the constraints xi≥Z(i) tn− D ∑︂ r=1 M(i),wr,J tn,i=1,...,M,n=0,...,N. Remark 3.12 A solution ℓ⋆to (3.10) yields the square-integrable 𝔽X,N -martingale Mℓ⋆, and by re-simulating ˜ Mi.i.d. samples of Z, the Brownian motion Wand the signature X<∞, we can notice that the resulting estimator yK,N,J, ˜ M 0is upperbiased, that is, yK,N,J, ˜ M 0≥yN 0, since the latter is defined by taking the infimum over all square-integrable 𝔽X,N -martingales. 1002 C. Bayer et al. 4 Numerical examples In this section, we study two non-Markovian optimal stopping problems and test our methods to approximate lower and upper bounds for the optimal stopping value. The details for the implementations and examples can be found at https://github.com/ lucapelizzari/Optimal_Stopping_with_signatures. Remark 4.1 In all the numerical experiments performed below, we did not observe any significant difference when using the normalised signature (choosing the same normalisation the authors introduce in Chevyrev and Oberhauser [17, Sect. 3]) and when using the standard, non-normalised signature. Since the tensor normalisation increases the complexity of the algorithms, all the results presented here were obtained using the standard signature. 4.1 Optimal stopping of fractional Brownian motion We start with the task of optimally stopping a fractional Brownian motion (fBm), which represents the canonical choice of a framework leaving the Markov and semimartingale regimes. Recall that an fBm with Hurst parameter H∈(0,1)is the unique continuous Gaussian process (XH t)t∈[0,T ]with E[XH t]=0,∀t≥0, E[XH sXH t]=1 2(|s|2H+|t|2H−|t−s|2H), ∀s,t ≥0; see e.g. Friz and Hairer [25, Chap. 9] for more details. We wish to approximate the value yH 0=sup τ∈𝒮0 E[XH τ],H∈(0,1), (4.1) from below and above. This example has already been studied in Becker et al. [8, Sect. 4.3] as well as in Bayer et al. [5, Sect. 8.1], and we compare the results below. Since XHis one-dimensional and α-Hölder-continuous for any α<H, its (scalar) rough-path lift is given by (︃1,XH s,t,1 2(XH s,t)2,..., 1 L!(XH s,t)L)︃∈Cα g([0,T];ℝ), where L=⌊1 α⌋. We can extend it to a geometric rough-path lift XH∈ˆ︁ Cα g([0,T];ℝ2) of the time-augmentation (t, XH t), as for instance described in [5, Example 2.4]. To numerically solve (4.1), we replace the continuous-time interval [0,T]by some finite grid points 0 =t0<t 1<···<t N=T. Below we compare our results with [8, Sect. 4.3], where the authors chose N=100. Before doing so, an important remark about the difference of our problem formulation is in order. Primal and dual optimal stopping with signatures 1003 Remark 4.2 In [8], the authors lift XHto a 100-dimensional Markov process of the form ˆ︁ Xtk=(XH tk,...,XH t1,0,...,0)∈ℝ100, and they consider the corresponding discrete (!) filtration ˆ︁ ℱk=σ(XH tk,...,XH t1),k=0,...,100. Notice that this differs from our setting as we consider the bigger filtration ℱk=σ(XH s:s≤tk)(see Sects. 3.2 and 3.3) that contains the whole past of XH, not only the information at the past exercise dates. Thus in general yH 0dominates the lower bounds from [8], simply because our filtration contains more stopping times. Similarly, the (very sharp) upper bounds in [8] were obtained by using a nested Monte Carlo approach, which constructs (ˆ︁ ℱk)-martingales that are not martingales in our filtration, and thus their upper bounds are not necessarily upper bounds for (4.1). In Table 1, we present intervals for the optimal stopping values yH 0for Hurst parameters H∈{0.01,0.05,...,0.95}, where the lower (resp. upper) bounds were approximated by using Longstaff–Schwartz with signatures, resp. the SAA approach described in Sect. 3. We truncate the signature at the level K=6 and apply the primal approach using M=106samples for both the regression and the re-simulation, and for the dual approach, we choose M=15’000 to solve the linear program from Remark 3.11 and re-simulate with M=105samples. In the first column, we choose the time discretisation for the signature equal to the number of exercise dates as J=N=100. While the lower bounds are very close, our upper bounds exceed those from [8]. This observation matches with the comments made in Remark 4.2 as Table 1 Intervals for optimal stopping of fBm: we show H↦→yH 0with N=100 exercise dates and discretisation J=100 (left column), J=500 (middle column), and intervals from [8] (right column). The overall Monte Carlo error is below 0.003 HJ=100 J=500 Becker et al. [8] 0.01 [1.518,1.645][1.545,1.631][1.517,1.52] 0.05 [1.293,1.396][1.318,1.382][1.292,1.294] 0.1 [1.045,1.129][1.065,1.117][1.048,1.05] 0.15 [0.83,0.901][0.847,0.895][0.838,0.84] 0.2 [0.654,0.706][0.663,0.698][0.657,0.659] 0.25 [0.507,0.538][0.510,0.533][0.501,0.505] 0.3 [0.363,0.396][0.371,0.392][0.368,0.371] 0.35 [0.248,0.272][0.255,0.270][0.254,0.257] 0.4 [0.153,0.168][0.155,0.165][0.154,0.158] 0.45 [0.069,0.077][0.068,0.076][0.066,0.075] 0.5 [−0.001,0][−0.002,0][0,0.005] 0.55 [0.061,0.071][0.060,0.066][0.057,0.065] 0.6 [0.112,0.133][0.112,0.124][0.115,0.119] 0.65 [0.163,0.187][0.163,0.175][0.163,0.166] 0.7 [0.203,0.234][0.205,0.220][0.206,0.208] 0.75 [0.242,0.273][0.240,0.260][0,242,0.245] 0.8 [0.275,0.306][0.281,0.298][0.276,0.279] 0.85 [0.306,0.335][0.301,0.324][0.307,0.31] 0.9 [0.331,0.357][0.337,0.356][0.335,0.339] 0.95 [0.367,0.381][0.366,0.381][0.365,0.367] 1004 C. Bayer et al. we consider the filtrationˆ︁ 𝔽in this case for the lower bounds; but our upper bounds are by construction upper bounds for the continuous problem with filtration 𝔽, and the continuous martingale is approximated only at the exercise dates. By increasing the discretisation to J=500 and thereby adding information to the filtration between exercise dates, one can see for small H(≤0.2) that the lower bounds exceed the intervals from [8], showing that even for N=100 points in [0,1], the information between exercise dates is relevant for optimally stopping the fBm. 4.2 American options in rough volatility models The second example we present is the problem of pricing American options in rough volatility models. More precisely, we consider the one-dimensional asset-price model X0=x0,dX t=rXtdt +Xtvt(ρdWt+√︂1−ρ2dBt), 0<t≤T, where Wand Bare two independent Brownian motions, the volatility (vt)t∈[0,T ]is an 𝔽W-adapted continuous process, ρ∈[−1,1]and r>0 is the interest rate. For any payoff function ϕ:[0,T]×ℝ→ℝ, we want to approximate the optimal stopping problem y0=sup τ∈𝒮0 E[e−rτϕ(τ,Xτ)],(4.2) where 𝒮0is the set of 𝔽:= (𝔽W∨𝔽B)-stopping times valued in [0,T].Itisworth noting that our method does not depend on the specification of v, and as soon as we can sample from (X, v), we can apply the method to approximate values of American options. In the following, we focus on the rough Bergomi model (see Bayer et al. [4]), that is, we specify the volatility as vt=ξ0ℰ(︃η∫︂t 0(t −s)H−1 2dWs)︃, where ℰdenotes the stochastic exponential, and we consider the parameters x0=100, r=0.05, η=1.9, ρ=−0.9, ξ0=0.09. Moreover, we consider put options with ϕ(t,x) =(K −x)+for different strikes K∈{70,80,...,120}, with maturity T=1 and N=12 exercise dates. Thus we write (4.2) as the discrete optimal stopping problem yN 0=sup τ∈𝒮N 0 E[e−rτ(K −Xτ)+], where 𝒮N 0is described at the beginning of Sect. 3.2. Moreover, for some finer grid s0=0<s 1<··· <s J=1, J∈ℕ, and fixed signature level Kand sample size M, we denote by yLS 0the value yK,N,J,M 0defined in Proposition 3.4 and by ySAA 0the value yK,N,J,M 0defined in (3.10). We compare our results with the lower bounds obtained in Bayer et al. [7]forH=0.07, resp. in Goudenege et al. [29] with H=0.07 and H=0.8. Primal and dual optimal stopping with signatures 1011 age approximation of y0is then given by yM 0=min x∈𝒳FM(x). (A.7) The following result provides sufficient conditions for the convergence yM 0→y0 as M→∞, and a more general version can be found in [38, Theorem 4]. Theorem A.2 Suppose that (1) Fis measurable and x↦→ F(x,η)is lower semicontinuous for all η∈ℝd; (2) x↦→ F(x,η)is convex for almost every η∈ℝd; (3) 𝒳is closed and convex; (4) f(x):= E[F(x,ξ)]is lower semicontinuous and f(x)<∞for all x∈𝒳; (5) the set Sof solutions to (A.6)is non-empty and bounded. Then yM 0→y0as M→∞. Similarly as in the proof of Proposition 3.4, for a fixed truncation level K∈ℕ, we denote by Dthe number of components of the truncated signature, which is given by D=∑︁K k=0(d +1)k. Now every ℓ∈𝒲d+1 ≤Kis of the form ℓ=∑︁D i=1βiwifor some β∈ℝD, where w1,...,w Dare all words of length at most K. In particular, for every ℓ∈(𝒲d+1 ≤K)m, there is a β∈ℝm×Dand our usual notation reads Mℓ t=∫︂t 0⟨X≤K 0,s ,ℓ⟩⊤dWs= D ∑︂ j=1 (βj)⊤∫︂t 0⟨X≤K 0,s ,w j⟩dWs, so that instead of minimising over ℓ, we can minimise over β. Let us now formulate the minimisation problem in Proposition 3.10 in the language of Theorem A.2 as E[︂max 0≤n≤N(Ztn−Mℓ tn)]︂=E[︃max 0≤n≤N(︃Ztn− m ∑︂ i=1 D ∑︂ j=1 βij ∫︂t 0⟨X≤K 0,s ,w j⟩dWi s)︃]︃ =E[︂max 0≤n≤N(Ztn−𝜷⊤Mtn)]︂, where we identify β∈ℝm×D∼ =ℝmD and Mtis the (mD)-dimensional vector (︃∫︂t 0⟨X≤K 0,s ,w j⟩dWi s:1≤i≤m, 1≤j≤D)︃. Finally, defining the random vector ξ:= (Zt0,M⊤ t0,...,Z tN,M⊤ tN)∈ℝ(D+1)(N+1)m, we notice that inf ℓ∈(𝒲d+1 ≤K)m E[︂max 0≤n≤N(Ztn−Mℓ tn)]︂=min x∈ℝmD E[F(x,ξ)],(A.8) 1012 C. Bayer et al. where F(x,η) := max 0≤n≤N(︃ηn(mD+1)−x⊤⎛ ⎜ ⎝ ηn(mD+1)+1 . . . ηn(mD+1)+1+mD ⎞ ⎟ ⎠)︃.(A.9) Therefore, setting 𝒳=ℝDm and d=(D +1)(N +1)m, the minimisation problem for yK,N,J,M 0in Proposition 3.10 can simply be written in the SAA formulation (A.7), where additionally the stochastic integrals in Mare replaced by the discretised versions MJ. Proof of Proposition 3.10 First, it is possible to rewrite the proof of Lemma A.1 for FMinstead of the expectation, to show that there exists a minimiser ℓ⋆to (3.10). Moreover, denote by yK,N,J 0the minimisation problem (A.8), where we replace Mℓ by the discretised version Mℓ,J described in Sect. 3.3.1. By the same reasoning as in Proposition 3.8, we can show the limit limK→∞ limJ→∞ yK,N,J 0=yN 0.Now for fixed K,J,N, we are left with showing almost sure convergence of yK,N,J,M 0 to yK,N,J 0. But this can be deduced from Theorem A.2 if we can show that (1)–(5) hold true for our Fin (A.9). Clearly, Fis measurable and it is easy to see that x↦→ F(x,η) is continuous and convex; thus (1) and (2) readily follow. Moreover, (3) holds true, and in order to show (4), set f(x) =E[F(x,ξ)]and notice that for x1,x 2∈𝒳,wehave |f(x 1)−f(x 2)|≤E[︂max 0≤n≤N(︁(x1−x2)⊤MJ tn))︁]︂≤|x1−x2|E[︂max 0≤n≤N|MJ tn|]︂, where we simply applied the triangle and Cauchy–Schwarz inequalities. Since we have Mℓ∈L2for all ℓ, an application of Doob’s inequality shows for the righthand side that E[max0≤n≤N|MJ tn|] <∞, and therefore (4) follows. Finally, nonemptyness of Sfollows from Lemma A.1, and the proof of the latter reveals that E[F(x,ξ)]→∞as |x|→∞. Thus Smust be bounded, which finishes the proof. □ Acknowledgements The authors would like to thank C. Cuchiero and S. Breneis for valuable remarks and helpful discussions about the global approximation in Sect. 2. Funding information Open Access funding enabled and organized by Projekt DEAL. Declarations Competing interests The authors declare no competing interests. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/ 4.0/. Primal and dual optimal stopping with signatures 1013 References 1. Alaifari, R., Schell, A.: Nonparametric regression of stochastic processes via signatures. SAM Research Report, 2023-45, (2023). Available online at https://www.sam.math.ethz.ch/sam_reports/ reports_final/reports2023/2023-45.pdf 2. Andersen, L., Broadie, M.: Primal–dual simulation algorithm for pricing multidimensional American options. Manag. Sci. 50, 1222–1234 (2004) 3. Bayer, C., Breneis, S.: Efficient option pricing in the rough Heston model using weak simulation schemes. Quant. Finance 24, 1247–1261 (2024) 4. Bayer, C., Friz, P., Gatheral, J.: Pricing under rough volatility. Quant. Finance 16, 887–904 (2016) 5. Bayer, C., Hager, P.P., Riedel, S., Schoenmakers, J.: Optimal stopping with signatures. Ann. Appl. Probab. 33, 238–273 (2023) 6. Bayer, C., Qiu, J., Yao, Y.: Pricing options under rough volatility with backward SPDEs. SIAM J. Financ. Math. 13, 179–212 (2022) 7. Bayer, C., Tempone, R., Wolfers, S.: Pricing American options by exercise rate optimization. Quant. Finance 20, 1749–1760 (2020) 8. Becker, S., Cheridito, P., Jentzen, A.: Deep optimal stopping. J. Mach. Learn. Res. 20, 2712–2736 (2019) 9. Belomestny, D., Bender, C., Schoenmakers, J.: True upper bounds for Bermudan products via nonnested Monte Carlo. Math. Finance 19, 53–71 (2009) 10. Belomestny, D., Bender, C., Schoenmakers, J.: Solving optimal stopping problems via randomization and empirical dual optimization. Math. Oper. Res. 48, 1454–1480 (2023) 11. Belomestny, D., Schoenmakers, J.: From optimal martingales to randomized dual optimal stopping. Quant. Finance 23, 1099–1113 (2023) 12. Boedihardjo, H., Geng, X., Lyons, T., Yang, D.: The signature of a rough path: uniqueness. Adv. Math. 293, 720–737 (2016) 13. Bogachev, V.I., Ruas, M.A.S.: Measure Theory, vol. 1. Springer, Berlin (2007) 14. Bonesini, O., Jacquier, A.: 𝔛PDE for 𝔛∈{bs,fbs,p}: a rough volatility context. Working paper (2023). Available online at https://arxiv.org/abs/2309.11183 15. Bouchaud, J.-P., Bonart, J., Donier, J., Gould, M.: Trades Quotes and Prices: Financial Markets Under the Microscope. Cambridge University Press, Cambridge (2018) 16. Carmona, P., Coutin, L.: Fractional Brownian motion and the Markov property. Electron. Commun. Probab. 3, 95–107 (1998) 17. Chevyrev, I., Oberhauser, H.: Signature moments to characterize laws of stochastic processes. J. Mach. Learn. Res. 23, 7928–7969 (2022) 18. Clément, E., Lamberton, D., Protter, P.: An analysis of a least squares regression method for American option pricing. Finance Stoch. 6, 449–471 (2002) 19. Cont, R., Fournié, D.-A.: Functional Itô calculus and stochastic integral representation of martingales. Ann. Appl. Probab. 41, 109–133 (2013) 20. Cuchiero, C., Schmocker, P., Teichmann, J.: Global universal approximation of functional input maps on weighted spaces. Preprint (2023). Available online at https://arxiv.org/abs/2306.03303 21. Cuchiero, C., Teichmann, J.: Generalized Feller processes and Markovian lifts of stochastic Volterra processes: the affine case. J. Evol. Equ. 20, 1301–1348 (2020) 22. Desai, V.V., Farias, V.F., Moallemi, C.C.: Pathwise optimization for optimal stopping problems. Manag. Sci. 58, 2292–2308 (2012) 23. Dupire, B.: Functional Itô calculus. Quant. Finance 19, 721–729 (2019) 24. Friz, P.K., Hager, P.P., Tapia, N.: Unified signature cumulants and generalized Magnus expansions. Forum Math. Sigma 10:e42, 1–60 (2022) 25. Friz, P.K., Hairer, M.: A Course on Rough Paths. Springer, Berlin (2020) 26. Friz, P.K., Victoir, N.B.: Multidimensional Stochastic Processes as Rough Paths: Theory and Applications. Cambridge University Press, Cambridge (2010) 27. Gatheral, J., Jaisson, T., Rosenbaum, M.: Volatility is rough. Quant. Finance 18, 933–949 (2018) 28. Giles, R.: A generalization of the strict topology. Trans. Am. Math. Soc. 161, 467–474 (1971) 29. Goudenege, L., Molent, A., Zanette, A.: Machine learning for pricing American options in highdimensional Markovian and non-Markovian models. Quant. Finance 20, 573–591 (2020) 30. Guyon, J., Lekeufack, J.: Volatility is (mostly) path-dependent. Quant. Finance 23, 1221–1258 (2023) 31. Kalsi, J., Lyons, T., Perez Arribas, I.: Optimal execution with rough path signatures. SIAM J. Financ. Math. 11, 470–493 (2020) 1014 C. Bayer et al. 32. Karatzas, I., Shreve, S.: Brownian Motion and Stochastic Calculus, 2nd edn. Springer, Berlin (1991) 33. Longstaff, F.A., Schwartz, E.S.: Valuing American options by simulation: a simple least-squares approach. Rev. Financ. Stud. 14, 113–147 (2001) 34. Lyons, T.J.: Differential equations driven by rough signals. Rev. Mat. Iberoam. 14, 215–310 (1998) 35. Ogata, Y.: Statistical models for earthquake occurrences and residual analysis for point processes. J. Am. Stat. Assoc. 83(401), 9–27 (1988) 36. Peskir, G., Shiryaev, A.: Optimal Stopping and Free-Boundary Problems. Springer, Berlin (2006) 37. Rogers, L.C.: Monte Carlo valuation of American options. Math. Finance 12, 271–286 (2002) 38. Shapiro, A.: Monte Carlo sampling methods. In: Ruszczynski, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 353–425. Elsevier, Amsterdam (2003) Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.