Signature-Kernel Dynamic Programming for Path-Dependent Optimal Stopping

Many decision problems are not Markovian in what you can observe. The value of exercising an option on a rough-volatility asset, or of stopping a process with delayed feedback, depends on the whole history of the path and not on today's price alone. Kernel methods for dynamic programming offer two things deep networks lack here: closed-form fits, and error bounds that track how mistakes compound as one solves backward through time. Their weakness is that they compare states as points in $\mathbb{R}^d$. A path signature, the sequence of iterated integrals that summarizes a trajectory's shape, solves the opposite problem. It compares whole histories, it is unaffected by irregular sampling times, and its kernel can be computed without truncation by solving a small two-dimensional PDE.

We propose backward kernel ridge regression dynamic programming in which the regression at every exercise date uses the untruncated signature kernel on the path observed so far. The proposal rests on one structural observation. A single Goursat PDE solve for a pair of full paths returns the signature kernel between every pair of prefixes. All the Gram matrices needed for the backward recursion therefore cost no more than one Gram matrix of whole paths. The result is a path-dependent stopping solver that is convex at every step and avoids the $O(d^m)$ feature explosion of truncated signatures. Its errors can be decomposed in the same terms already proven for Markovian kernel dynamic programming. The claim is deliberately narrow. We expect gains where no small hand-built Markov state exists and where low-level truncated signatures throw away information: rough volatility, many assets, and irregular monitoring.

Core Claim and Mechanism

Let $X^{(i)}$, $i=1,\dots,N$, be simulated paths on $[0,T]$ with exercise dates $t_1<\dots<t_J$. Let $X^{(i)}_{\le t}$ be the path up to time $t$, augmented with time as an extra channel. Without that channel the signature ignores duration, and duration matters for stopping. Let $g$ be the payoff. The backward recursion fits a continuation value $C_j$ in the signature reproducing-kernel Hilbert space (RKHS) $\mathcal{H}_K$ by

$$C_j = \arg\min_{f \in \mathcal{H}_K} \frac{1}{N}\sum_{i=1}^N \Big(\max\big(g(X^{(i)}_{\le t_{j+1}}),\, C_{j+1}(X^{(i)}_{\le t_{j+1}})\big) - f(X^{(i)}_{\le t_j})\Big)^2 + \lambda_j \|f\|_{\mathcal{H}_K}^2,$$

where $\lambda_j$ is a ridge penalty. By the representer theorem this is one linear solve against the Gram matrix $G_j[i,k]=K(X^{(i)}_{\le t_j}, X^{(k)}_{\le t_j})$.

The method borrows the kernel evaluation from The Signature Kernel Is the Solution of a Goursat PDE. That paper shows the untruncated kernel is the solution $u(s,t)$ of $\partial_s\partial_t u = \langle \dot X_s, \dot Y_t\rangle u$, with $u(0,\cdot)=u(\cdot,0)=1$. The value $u(s,t)$ equals the kernel between $X_{\le s}$ and $Y_{\le t}$. Reading $u$ off the diagonal at $(t_j,t_j)$ for all $j$ therefore yields every $G_j$ from one solve per path pair. A Markovian kernel recomputes nothing across dates either, but it also sees nothing of the past. Truncated signatures update cheaply via Chen's identity, but they pay $O(d^m)$ in feature size. The prefix-reuse property is what makes untruncated path kernels affordable inside a recursion over many dates. We will use the memory-linear tiled solver of Scalable Signature Kernel Computations via Local Neumann Series Expansions (PowerSig). For large $N$ we will add Nyström landmarks, so that only $N\times m$ PDE solves are needed.

Relation to Prior Work

Three lines of work sit closest. Error Propagation in Dynamic Programming: From Stochastic Control to American Option Pricing builds kernel ridge regression dynamic programming (KRR-DP). It splits total error into regression error, Monte Carlo continuation error, and backward propagation error, but only for Euclidean kernels on Markov states. We reuse that decomposition and its algorithm, and replace the state kernel with the prefix signature kernel. Deep Signature Algorithm for Path-Dependent American option pricing solves the same class of problems. It feeds truncated signatures into deep networks at each backward step and reports that the feature dimension becomes the bottleneck above roughly 20 assets. We keep its problem class and benchmarks, but drop both truncation and non-convex training. A path-dependent PDE solver based on signature kernels shows that minimum-norm recovery in the signature RKHS solves linear path-dependent PDEs well. It matches a 100,000-path Monte Carlo on rough Bergomi with 500 collocation points. It has no control, no max operator and no backward recursion, and it leaves convergence rates open. Optimal stopping is the simplest nonlinear control problem, and it is the natural next test of whether that efficiency survives the max operator.

Other work motivates the problem rather than supplying the method. Operator world models (Operator World Models for Reinforcement Learning) and kernel TD analyses (A Non-asymptotic Analysis of Non-parametric Temporal-Difference Learning) give clean RKHS guarantees, but only for memoryless states on uniform time grids. The irregular-observation POMDP results of ODE-based Recurrent Model-free Reinforcement Learning for POMDPs show that history matters and that neural continuous-time models are costly, with 12 to 20 hours of training. We restrict ourselves to optimal stopping instead of general RL on purpose. Stopping has finite horizon and no off-policy bootstrapping, so the backward recursion is exact in structure. That lets the experiments isolate the representation question.

Research Program

The first component is the algorithm. It covers prefix-reuse Gram construction, per-date ridge selection by held-out paths, and Nyström approximation with landmark paths. We will also compare two treatments of the continuation target: the standard regression-on-realized-next-value scheme, and inner Monte Carlo subsampling, which corresponds to Term II of the KRR-DP decomposition.

The second component is analysis. We will carry the three-term decomposition of Error Propagation in Dynamic Programming over to the signature RKHS. The regression term would then be governed by the eigenvalue decay of the signature kernel's integral operator under the path law, rather than by Euclidean dimension and smoothness. We will estimate that eigenvalue decay empirically for Brownian, fractional Brownian and rough Bergomi paths. We will then test whether the measured error-versus-$N$ slopes track it. The kernel TD literature does a comparable check, with an observed slope of -0.72 against a predicted -0.6 in A Non-asymptotic Analysis of Non-parametric Temporal-Difference Learning A Non-asymptotic Analysis of Non-parametric Temporal-Difference Learning. A full finite-sample rate is a stretch goal, not a promised deliverable.

The third component is a robustness study under irregular monitoring. Paths are observed at random, path-specific times. The signature kernel ingests these directly, while every grid-based competitor must interpolate.

Baselines

The naive reference point is Markovian KRR-DP on the current state alone, as in Error Propagation in Dynamic Programming: From Stochastic Control to American Option Pricing Error Propagation in Dynamic Programming: From Stochastic Control to American Option Pricing, together with the European (no early exercise) value. If path information is irrelevant, our method should not beat it. Any gain over it measures the value of history.

The strongest existing method is the Deep Signature algorithm ( Deep Signature Algorithm for Path-Dependent American option pricing). The file reports only that, on a 20-stock basket, it was about four times faster than the state-dependent backward schemes of Huré et al. and gave narrower 95% confidence intervals. No reported price values were found on Lacuna for this method or for KRR-DP on the Goudenege et al. setup. We will therefore rerun it ourselves on identical simulated paths, at the paper's truncation levels and with a matched hyperparameter search budget and wall-clock budget.

The second strong competitor is truncated signature features at levels 2 to 4, fed to ridge regression inside the same backward recursion. This is the cheapest version of our idea and the main threat to it.

The third is a hand-Markovianized KRR-DP. Where a finite sufficient statistic exists, as with the running average for Amerasian options, it is appended to the state, and an RBF kernel is used.

The fourth is a Gaussian kernel over a sliding window of the last $H$ observations.

All methods use the same simulated training paths and fresh evaluation paths, and we report both accuracy and runtime. The ablations isolate each ingredient: untruncated against truncated signature kernels at equal regularization, with and without the time channel, and prefix reuse against per-date recomputation (a compute-only comparison).

We will count a win as follows. On held-out paths, our learned exercise policy produces a lower-bound price higher than every baseline's by more than the Monte Carlo confidence width, with a speed-accuracy trade-off at least as good. This must hold on the non-Markovian benchmarks, with parity allowed on the Markovian ones.

Why not just…?

Why not just use truncated signatures with ridge regression? This is a real threat. For one or two assets, level-3 features number in the tens, and they may capture all the path information a stopping rule needs. We do not argue around it. The truncation ablation sweeps level against asset dimension and Hurst parameter. If truncated ridge matches the untruncated kernel everywhere, including rough Bergomi with $H\approx 0.1$ and baskets of 10 to 20 assets, we will report that the kernel's benefit is purely computational. That benefit arises only where $d^m$ exceeds the number of paths $N$.

Why not just add a hand-crafted Markov state? For Amerasian options a running average makes the problem Markovian, and RBF KRR-DP on the augmented state may be the best possible method. That is why we include it as a baseline. Rough volatility and Shiryaev's delayed problem have no small sufficient statistic, and those are the cases where the claim must hold.

Why not just use a recurrent or neural ODE encoder? Such encoders can represent history. However, they bring non-convex training back into every backward step, and the GRU-ODE results in ODE-based Recurrent Model-free Reinforcement Learning for POMDPs required 12 to 20 hours. The Deep Signature baseline already stands in for the neural route, using an input that the file reports handles path dependence well. Comparing against it under a matched compute budget settles the question more directly than adding another architecture would.

Why not a sliding-window RBF kernel? It needs a fixed grid and grows the input to $H\times d$ dimensions. Diversifying Parallel Ergodic Search found that RBF kernels on trajectories lose order structure, with a diversity score of 7.02 against 10.33 for the signature kernel, though in a planning task rather than value estimation. The irregular-monitoring experiment tests directly whether this matters for value estimation.

Proposed Experiments and Decisive Checks

The benchmarks follow the file. They are the Black-Scholes basket options up to 20 dimensions, Amerasian baskets, and Shiryaev's delayed stopping problem from Deep Signature Algorithm for Path-Dependent American option pricing Deep Signature Algorithm for Path-Dependent American option pricing, the Goudenege et al. American setup used by KRR-DP, and rough Bergomi and fractional Brownian dynamics from A path-dependent PDE solver based on signature kernels A path-dependent PDE solver based on signature kernels, recast as American-style contracts.

Our primary metric is the lower-bound price obtained by running each learned stopping rule on 100,000 fresh paths. This is valid without a reference price, because any rule's realized value bounds the true price from below. Secondary metrics are 95% confidence interval width, wall-clock time and memory, and the error of the fitted continuation value at $t_1$ relative to the policy value.

Three checks decide the proposal. First, on rough Bergomi and Shiryaev the method must beat Markovian KRR-DP clearly, or path kernels add nothing to stopping. Second, at 10 to 20 assets it must match or beat Deep Signature and truncated ridge, at equal or lower cost. Third, under irregular monitoring its lower bound must degrade less than that of every grid-based baseline. If the second check fails while the first succeeds, the conclusion is that history matters but low-order truncation suffices, and we will report that finding.