Optimal Stopping for Non-Markovian Asset Price Processes

Optimal stopping problems form an important class of problems within the wider realm of stochastic optimal control. A prime example in finance is the pricing of American options. Unlike European options, American options may be exercised (by the owner) at any time t before a terminal time T, in which case the counterparty has to pay the owner a payoff \(\phi (S_t)\) given in terms of the current price \(S_t\) of the underlying. For example, in the case of an American put option, we have \(\phi (S_t) = (K - S_t)^+ = \max (K-S_t, 0)\), where K is a fixed threshold value, the strike price.

When we mathematically model an American option, we obviously need to allow the owner to stop at a random time \(t = t(\omega )\), to accommodate reasonable strategies such as “stop at the first time when S is lower than a given level L”. At the same time, our model must not allow arbitrary random exercise times, to reflect that the owner’s decision to exercise at time t has to be taken at (or before) time t—i.e., the owner cannot “look into the future”. This, in particular, excludes trivial “solutions”, such as exercising at time \( \operatorname *{\mbox{arg max}}_{t \in [0,T]} \phi (S_t)\)—the pathwise optimal time.

“Not looking into the future” is a statement about the flow of information, which is modeled by filtrations in probability theory. Given a filtration, exercise times conforming to the above-mentioned restrictions are then modeled as stopping times. In what follows, we will in parallel consider stopping times taking values in a set \(\mathcal {T}\) of possible times, where we restrict ourselves to either of the following important cases:

We can now define the optimal stopping problem, where we, for simplicity, assume that interest rates are \(r=0\), or, equivalently, all cash-flows are already properly discounted.

For concreteness’ sake, we will usually consider the filtration to be generated by a (continuous) stochastic process \(X = (X_t)_{t \in \mathcal {T}}\) taking values in \(\mathbb {R}^d\). A natural class of stopping times are first hitting times of a process w.r.t. a set.

As we shall see later, for optimal stopping we can essentially restrict ourselves to stopping times, which are hitting times.

How can we compute the value \(\sup _{\tau \in \mathcal {S}} \mathbb {E}\left [ Y_{\tau \wedge T} \right ]\) of the optimal stopping problem as well as an optimal stopping time \(\tau ^\ast \)? Several possibilities come to mind. We could, for instance, hope that optimal stopping times are, indeed, hitting times of the underlying driving process X w.r.t. sets A, parameterize a sufficiently large class of such sets \(A_\theta \), and optimize over \(\mathbb {E}[Y_{\tau _{A_\theta } \wedge T}]\). This approach forms the basis of the first signature-based method suggested in Sect. 3.

There are two important systematic approaches for solving optimal stopping problems, sometimes called primal and dual methods.

On the primal side, numerical methods are usually based on the dynamic programming principle, which we shall formulate in discrete time for simplicity. Let us first introduce the value process (also known as the Snell envelope) which serves as the backbone for most of the theory of the optimal stopping problem. In particular, V  is a super-martingale, and is, in fact, the smallest super-martingale dominating the reward process Y . In discrete time, it is easy to see that it satisfies a semi-explicit backward recursive formula. Indeed, we have see, for instance, [15, Section 1.1]. Note that (2) implies an explicit formula of the optimal stopping time (as a first hitting time): Note that we can solve (2), provided we can compute the conditional expectation, i.e., solve a regression problem. We will come back to this approach in the context of signatures in Sect. 3. Note that the process V  is a supermartingale.

From a computational point of view, it is very convenient to have primal and dual formulations (without duality gap) of the same problem, since this enables us to sandwich the unknown value \(V_0\).

For the optimal stopping problem, it turns out that the dual problem presented in [16] is a minimization problem over martingales. More precisely, we have where \(\mathcal {M}_0\) contains all (say, square integrable) martingales starting in \(M_0 = 0\).

Finally, let us comment on the role of the Markov property for both the dynamic programming problem and the dual problem. As already pointed out above, the main computational challenge in the dynamic programming principle is the computation of the continuation value, i.e., the conditional expectation \(\mathbb {E}[ V_{t_{n+1}} \mid \mathcal {F}_{t_n}]\). In the Markovian case, this can be expressed as \(\mathbb {E}[ V_{t_{n+1}} \mid X_{t_n}]\), and we can make an ansatz reducing the problem to a standard least-squares problem. If the Markov property does not hold, we can still re-express but this corresponds to an (infeasible) regression problem in \(\mathbb {R}^{d(n+1)}\).

In the dual approach, we can often prove the existence of an optimal martingale expressible in terms of some function of X under the Markov property—e.g., in the Brownian setting, some optimal martingale is given by Again, we are left with a (low-dimensional) functional approximation problem.

The optimal stopping problem consists of finding a rule that tells us at every time instance whether it is favourable to stop a stochastic process now or to let it still run to maximize a certain gain. The information available to us is the whole past of the process until the present time. If the process satisfies the Markov property, the problem simplifies a lot since the past simply does not matter here. Consequently, most of the work that was done in the field of optimal stopping concentrates on the Markovian case, cf. e.g. the classical text [18]. However, one can argue that in many situations, assuming the Markov property leads to an oversimplification of the problem. In the general path-dependent case, the history of the process can be encoded using the signature, and it should not be too surprising that the optimal stopping problem can be reformulated in terms of the signature, too. This will lead to a computational convenient way to solve the optimal stopping problem in a very general form.

In this chapter, we will consider exclusively the continuous-time case \(\mathcal {T} = [0,T]\). We will always assume that \(\mathcal {F} = (\mathcal {F}_t)_{t \in \mathcal {T}}\) is a filtration generated by a continuous stochastic process \(X = (X_t)_{t \in \mathcal {T}}\), i.e. \(\mathcal {F}_t = \sigma (X_s \, |\, s \in \mathcal {T}, s \leq t)\). Let \(\tau \) be an \(\mathcal {F}\)-stopping time. Note that for any continuous \(\mathbb {R}\)-valued process Y , we have the identity For any \(\mathcal {F}\)-adapted stochastic process U and any \(z > 0\), the random variable defines a stopping time, and thus The idea is now to approximate by where the supremum runs over a sufficiently rich class of \(\mathcal {F}\)-adapted stochastic processes U. To see that (5) and (6) can indeed be equal, we can informally define for any given stopping time \(\tau \) an adapted process U by setting that clearly satisfies Using the signature, we will be able to parametrize a subclass of adapted processes that will still be large enough to attain the supremum in (5).

One key point for using the signature method in optimal stochastic control theory is to model the notion of adaptedness via a suitable factorization over a space of path segments or stopped paths. To illustrate the idea, recall that if U is a random variable that is \(\sigma (Z)\)-measurable for another random variable Z, there is a measurable map f such that \(U = f(Z)\). Therefore, if \((U_t)_{t \in \mathcal {T}}\) is \(\mathcal {F}\)-adapted, we know (all technicalities aside) that for every \(t \in \mathcal {T}\), there is a measurable map \(f_t\) such that \(U_t = f_t(X|_{[0,t]})\). Here, the maps \(f_t\) are defined on suitable path spaces where the paths are defined on the interval \([0,t]\). We would now like to remove the dependency of the map f on the time point t. To do this, we need to find a suitable space that contains paths that are defined on all different time intervals \([0,t]\), \(t \in \mathcal {T}\), i.e. on path segments. From now, we assume that X is a continuous stochastic process taking values in \(\mathbb {R}^d\). The following definition first appeared in Dupire’s work on functional Itō-calculus [8].

It is not hard to show that \((\mathscr {C}_T,d_{\mathscr {C}_T})\) is a metric space. With a bit more work, one can show that \(\mathscr {C}_T\) is complete and separable, i.e. a Polish space. The following proposition shows that the space \(\mathscr {C}_T\) indeed serves as a suitable space for the desired factorization.

We shifted the proof of this Proposition to the appendix. Let us note that the left-continuity assumption can actually be dropped in the case when U is progressively measurable. A proof of this more general result can be found in the forthcoming work [1].

Proposition 2.2 will not be useful for us since not every continuous path has a well-defined signature. Instead, we will first consider the smaller space of bounded variation paths in the next section for which the signature always exists.

We now give a more detailed look at three different approximation methods for the optimal stopping problem.

Having provided a cursory look at three approximation methods for general optimal stopping problems based on the path-signature, we will now give an in-depth exposition for one of these methods, namely the dual martingale method from [3].

As explained above, the strategy is to approximate generic adapted processes by linear functionals of the signatures. The universality results for the standard signature, typically are formulated in terms of uniform convergence on compacts subsets of (rough) path-space. However, as explained in chapter “The Signature Kernel” of this book, there is a robust signature obtained by normalizing the standard signature, which is, in fact, uniformly bounded w.r.t. the underlying paths, and, hence, allows global universality—in the set of bounded continuous functions of (rough) path space—when considering the correct topology. Using this machinery, we can provide full convergence results (Theorem 4.1 below), and are not limited to local results—i.e., convergence “on compacts” or “with high probability”. In what follows, we consider a tensor normalization \(\lambda \) and the corresponding robust signature \(\lambda (\widehat {\mathbb {X}}^{<\infty }_{s,t})\) in the sense of chapter “The Signature Kernel”.

We start by presenting a key technical lemma required in the analysis, which is a consequence of Theorem 8.4 in chapter “The Signature Kernel”. Denote the linear functionals of the robust signature by where \(\lambda \) denotes an appropriate signature normalization, see chapter “The Signature Kernel”, and we recall the definition of the space of stopped p-rough paths, see Definition 2.12.

The following result generalizes the universal approximation property of the signature in \(L^p\) w.r.t. some measure \(\mu \), extending Proposition 2.14. Note that measures \(\mu \) on \(\widehat {\Omega }^p_T\) can be extended to measures on the space of stopped rough paths \(\Lambda ^p_T\) by restriction. We will denote its extension by \(\mu \), as well. Conversely, every measure \(\mu \) on \(\Lambda ^p_T\) also induces a measure on \(\widehat {\Omega }^p_T\), which we will again denote by \(\mu \).

The proof is left to the readers as an exercise, see also [3, Lemma 2.8]. The following lemma is a slight generalization of [3, Lemma 2.9].

As a corollary of Theorem 4.1, we will see that all (square integrable) martingales can be approximated by integrals of linear functionals of the signature against the driving Brownian motion provided that the filtration is generated by Brownian motion. More concretely, we assume that X satisfies (21) driven by a d-dimensional Brownian motion W s.t. the diffusion matrix \(\sigma \) is invertible everywhere, implying that the filtrations generated by X and W coincide.

We can now apply this result to the dual martingale formulation of the optimal stopping problem, see (19). Indeed, Lemma 4.5 implies that for any \(M \in \mathcal {M}_0^2\) where the limit is understood in the \(L^2\) sense. We conclude that A simple argument then yields

We are now left with turning the duality formula (25) into a numerical algorithm. Several issues immediately come to mind: (25) includes several integrals (the stochastic integrals, but also the signature itself) which require discretization. This also applies to computing \(\sup \) over an infinite set of times. The expectation needs to be computed. Finally, we need to minimize over linear functionals of the signature.

We start with time discretization. Let us first introduce a grid \(0 = t_0 < t_1 < \cdots < t_N = T\), and restrict the \(\sup \) inside the expectation to a \(\max \) over the grid, i.e., The martingale duality formula (19) for the discrete time stopping problem, provided that we still use the continuous-time filtration \((\mathcal {F}_{t_n})_{n=0}^N\)—i.e., not the filtration generated by \((X_{t_n})_{n=0}^N\). Hence, the error \(\left \lvert V_0 - V^N_0\right \rvert \) only depends on the underlying processes \(W, X, Y\), but not on the method, and we shall assume that \(\left \lvert V_0 - V^N_0\right \rvert \) as \(N \to \infty \), see, for instance, [9].

Next, let us truncate the signature at level I, which turns an infinite dimensional minimization problem into a finite-dimensional one, i.e., It is not difficult to see that \(\lim _{I \to \infty } V^{I,N}_0 = V^N_0\): Indeed, note that \(V^{I,N}_0\) is increasing in I. Besides, for every \(\epsilon >0\) we can find \(I_\epsilon \) such that an \(\epsilon \)-optimal solution \((\ell ^1, \ldots , \ell ^d)\) is contained in \(\bigoplus _{i=0}^{I_\epsilon } (\mathbb {R}^{1+d})^{\otimes i}\). This, however, already implies convergence.

Note that the infimum in (27) is attained, i.e., we can find minimizers \(\ell ^{1,\ast }, \ldots , \ell ^{d,\ast } \in \bigoplus _{i=0}^I (\mathbb {R}^{1+d})^{\otimes i}\). Indeed, we note that the functional is convex as an expectation of the pointwise maximum of affine (and, hence, convex) functions, see, e.g., [6, Section 3.2.1 together with Section 3.2.3]. The functional also grows to infinity as \(\left \lvert \ell ^i\right \rvert \to \infty \) and is continuous by dominated convergence (note the use of the robust signature). This implies the existence of minimizers.

If we now replace the exact truncated signature \(\widehat {\mathbb {X}}^{\le I}_{0,s}\) by a discretized version \(\widehat {\mathbb {X}}^{\le I,J}_{0,s}\) based on a grid \(0 = s_0 < \cdots < s_J = T\) (containing \(t_1, \ldots , t_N\))—think of \(J \ll N\)—and similarly approximate the stochastic integrals in (27) by approximation based on the same grid, i.e., A similar argument as above shows that \(\lim _{J \to \infty } V^{I,N,J}_0 = V^{I,N}_0\).

This leaves the final approximation necessary, namely replacing the expectation by a finite sample (Monte Carlo) approximation. We are finally given an approximation problem where \(Y^{(m)}\), \(\widehat {\mathbb {X}}^{\le I,J,(m)}_{0,s_j}\), \(W^{i,(m)}_{s_j}\) are i.i.d. samples from the respective random variables, \(m=1, \ldots , M\).

The problem (29) is an example of a sample average approximation to a stochastic optimization problem. In order to streamline the discussion, let us denote all the sources of randomness in (28) by \(\xi {=} \left ( (Y_{t_n})_{n=0}^N, (\widehat {\mathbb {X}}^{\le I,J}_{0,s_j})_{j=0}^J, (W^i_{s_j})_{j{=}0, \ldots , J, i=1, \ldots , d} \right )\). The we have for a function F implicitly defined by (28), whereas (29) is its sample average approximation The convergence theory for such approximations is well understood. We cite a (slightly modified) result from [17, Chapter 6, Theorem 4].

Since all the conditions of Lemma 4.6 are easily verified for (28), we can conclude that \(\lim _{M\to \infty } V_0^{I,N,J,M} = V_0^{I,N,J}\) a.s. Hence, we obtain (as claimed earlier in Sect. 3.3) with the caveat that some restrictions between the parameters exist—i.e., we can only choose \(J \ge N\).

The aim of this section is to illustrate the performance of the signature stopping methodology in numerically approximating optimal stopping values. We therefore investigate the optimal stopping of fractional Brownian motions. This choice allows us to explore a wide range of underlying path regularities, including scenarios involving non-Markovianity, all within a unified model.

A one-dimensional fractional Brownian motion is a zero-mean Gaussian process X with a covariance function described by where \(H \in (0,1]\) is referred to as the Hurst parameter. The sample paths of X are almost surely \(\alpha \)-Hölder continuous for any \(\alpha < H\). When \(H=\frac {1}{2}\), X represents a standard Brownian motion. However, when \(H \neq \frac {1}{2}\), X is neither a Markov process nor a semimartingale. Figure 1 illustrates the regularity of fractional Brownian sample paths for different Hurst parameters. As a one-dimensional process, X can be trivially lifted to a geometric rough path \(\mathbb {X}\in \Omega ^p_T(\mathbb {R}^d)\) for any \(p > \frac {1}{H}\), defined as \(\mathbb {X} = \pi _{\le \lfloor p \rfloor }\exp _\otimes (X_{s,t})\). In the particular example we consider, the stopped process and the underlying process are identical, i.e., \(Y = X\) is the fractional Brownian motion itself. For all following experiments we fix a unit time horizon \(T = 1.0\).

Full size image

In Table 1, we present estimates of the optimal stopping values corresponding to various values of H. These estimates were obtained using the signature stopping time parametrizations introduced in Sect. 3.1. Specifically, we assess the performance of both linear and deep signature stopping rules, employing different signature truncation levels for each. The architecture of the deep neural networks consists of 2 hidden layers with 30 additional neurons each, using ReLU activation functions. The observations indicate a significant improvement when employing higher truncation levels and transitioning from linear to deep signature strategies. Note that, as a consequence of Doob’s optimal sampling theorem, the optimal stopping value for standard Brownian motion is 0. Therefore, the values obtained for \(H=0.5\) are consistent with this theoretical benchmark.

Figure 2 illustrates the estimates of optimal stopping values for a range of Hurst parameters using time discretizations with \( N = 100, 1000, 10{,}000 \) steps. These values were obtained using a deep signature stopping rule with a fixed signature truncation level of \( I=3 \). For comparison, we have also included the benchmark values from [4]. In their work, the authors translated the problem into a Markovian setting by lifting the discretized fractional Brownian motion to a high-dimensional process, which includes its running history. We observe that when using the same time discretization (\( n=100 \)), our signature methods yield comparable results to [4]. It is worth noting, however, that for the signature methodology, increasing the number of time steps does not lead to an increase in the number of model parameters, as the input dimension of the network remains equal to the dimension of the truncated signatures. This contrasts starkly with the lifting approach used in [4]. Particularly for small Hurst parameters, we observe a significant improvement gained from choosing a finer discretization grid. This observation aligns with the theoretical insight from [2] stating that the optimal stopping value of fractional Brownian motion diverges as the Hurst parameter \( H \) approaches zero.

Full size image

Let us now focus on the case of a Bermudan option with \(N=100\) equidistant exercise opportunities \(0 = t_0 < t_1 < \dots < t_N = T\), where the payoff process \(Y = X\) is again a fractional Brownian motion. In this case, we can utilize the Longstaff-Schwartz method described in Sect. 3.2 and the dual martingale method described in Sect. 3.3 to compute lower and upper bounds. Note that, apart from the signature truncation level I, we have an additional parameter to consider: the number of time grid points, denoted as J, used to approximate the signature of the fractional Brownian motion. In Table 2, we present the results obtained for the choices \(J=100=N\) and \(J=500>N\) for various Hurst parameters. The values from [4] were also obtained on a grid with \(N=100\) points, providing comparable benchmarks for the discrete problem. We observe that the lower bounds obtained with the signature Longstaff-Schwartz method are comparable to those in [4] for \(J=100\), while for \(J=500\), we see a significant improvement. To obtain comparable upper bounds, it appears that choosing a finer grid for signature computation is necessary. We emphasize that even for discrete-time stopping problems with an underlying filtration generated by a non-Markovian continuous-time process, the ability to enhance results by increasing J, thereby incorporating more information about the underlying path without increasing the number of model parameters, is an inherent feature of the signature methodology. There seems to be no evident extension of methods such as those in [4] to incorporate such a feature.

Signatures can serve as a natural set of basis functions for the numerical approximation of functions on path-space, analogous to polynomials on finite-dimensional spaces. In this chapter, we show how this conjecture can be used in the numerics of optimal stopping problems, when the underlying stochastic process is not a Markov process. More precisely, we derive non-Markovian extensions of some classical algorithms, namely the Longstaff–Schwartz algorithm and Rogers’ dual algorithm. In addition, we also present a direct algorithm based on parameterization of a rich class of stopping times defined in terms of the signature.

Hence, signature based methods for optimal stopping provide a very rich and efficient class of methods, as also supported by numerical examples. On the other hand, they can be challenging to implement, due to the large number of terms present in the signature, as well as the cost of computing the signature itself from time-series of the underlying process.

There are many open problems and largely unresolved questions in the context of the signature method for optimal stopping and, more generally, stochastic optimal control. Possibly the most prominent problem is to establish quantitative error bounds and rates of convergence for the proposed algorithms and other algorithms based on the signature. Note that the methods presented here require several numerical approximations (truncation of the signature, finite sample, discretization of the iterated integrals constituting the signature), and we would like to obtain sharp error estimates and rates for the total error in terms of these numerical parameters. Note that these approximations interact with each other, e.g., higher degree of truncation may lead to larger discretization errors or variances. Functional Taylor expansions as presented in chapter “Signature and the Functional Taylor Expansion” could serve as important tools for analyzing the approximation errors.

From a more applied point of view, it would be highly desirable to improve the performance of the signature methods if possible. To this end, dimension reduction techniques such as randomized signatures, see, for instance, [7], can be useful. Moreover, detailed case studies for important applications, such as pricing American options in rough volatility models, with an emphasis on obtaining tight upper and lower bounds would be desirable.