Low-rank kernel methods for American option pricing

Technical Summary: Low-Rank Kernel Methods for American Option Pricing

Problem Statement
The pricing of American derivatives represents a fundamental challenge in mathematical finance and requires solving an optimal stopping problem under a risk-neutral measure. Unlike European options, American options allow exercise at any time prior to maturity, necessitating the estimation of conditional continuation values at every potential exercise time. While the regression-based Least-Squares Monte Carlo (LSM) method, introduced by Longstaff and Schwartz [2001], has become the industry standard due to its conceptual simplicity, it suffers from significant computational limitations in high-dimensional settings. Specifically, LSM requires fitting a new regression model at each exercise time during backward dynamic programming. This "stepwise" regression dominates computational costs and scales poorly with the number of simulated paths and exercise times. Furthermore, dependence on explicit, often ad-hoc chosen basis functions limits the method's ability to capture complex nonlinear dependencies without overfitting or underfitting.

Methodology
The authors propose a scalable, theoretically grounded alternative that reformulates the estimation of continuation values as a learning problem within a Reproducing Kernel Hilbert Space (RKHS). The core of the methodology relies on the Conditional-Mean-Embedding (CME) operator, which represents the conditional expectation as a linear operator acting on future payoffs.

1. Offline-Online Decomposition: By treating the conditional expectation as a single linear operator on the RKHS, the method decouples the learning phase from the pricing phase. The operator is learned once from simulated data in an Offline phase and subsequently reused across all exercise times and strikes in the Online backward recursion. This eliminates the need to recompute regression models at every step, a primary bottleneck in standard LSM and many deep learning approaches.
2. Low-Rank Approximation: Naive kernel methods typically incur a computational complexity of $O(n^3)$ with respect to the number of simulated paths $n$. To restore scalability, the authors introduce a low-rank approximation based on pivoted Cholesky decomposition. This technique exploits the spectral decay of the relevant kernel matrices ($K_X$ and $K_Y$) to construct a reduced subspace representation.
   • The algorithm constructs a low-rank Cholesky factorization ($K \approx LL^\top$) and an associated biorthogonal basis transformation.
   • This yields a closed-form estimator in a reduced subspace, where computational costs scale linearly with $n$ ($O(nm^2)$ for training and $O(m^2)$ for evaluation, where $m \ll n$ is the rank).
   • The approximation error is controlled by a stopping tolerance $\varepsilon$.

Main Contributions
The paper makes four primary contributions:

1. Reformulation as Operator Learning: The estimation of the continuation value is reformulated as learning a Conditional-Mean-Embedding in a tensor product RKHS. This yields an algorithm that learns the conditional expectation operator once and reuses it, providing a clean offline-online decomposition.
2. Scalable Low-Rank Estimator: The authors introduce a low-rank approximation of the kernel system via pivoted Cholesky factorization. This provides a closed-form estimator in a reduced subspace with significantly lower computational costs than the dense kernel solution, while maintaining a controlled approximation error.
3. Convergence and Error Analysis: The paper establishes convergence guarantees for the proposed scheme. It derives explicit bounds quantifying the approximation errors that propagate through the backward recursion. These results extend the existing convergence theory of LSM-like algorithms to nonparametric kernel estimators with low-rank truncation.
4. Numerical Validation: Comprehensive numerical experiments on the Heston stochastic volatility model demonstrate that the proposed method (CME-LR) either matches or exceeds the Longstaff-Schwartz benchmark in accuracy while offering substantial acceleration, particularly as the number of simulation paths increases.

Results
Numerical experiments were conducted on American put options under the Heston model with varying maturities, strikes, and numbers of simulation paths ($n \in \{10^2, \dots, 10^5\}$).

• Computational Efficiency: The CME-LR method is systematically faster than the Longstaff-Schwartz (LS) baseline across all tested configurations. The acceleration is most pronounced for smaller $n$, attributed to the sparsity of the low-rank basis and the elimination of repeated coefficient recomputation.
• Accuracy: CME-LR achieves a uniformly lower mean relative implied volatility error compared to LS across all maturities and sample sizes.
• Error Profile: The error analysis reveals a complementary profile: CME-LR is more accurate for out-of-the-money options (positive log-moneyness), while LS retains a slight advantage for in-the-money options.
• Rank Behavior: The rank of the kernel matrix $K_Y$ grows sublinearly with $n$, confirming that the low-rank structure automatically adapts to data complexity. The rank of $K_X$ remains very small (e.g., 2–6) due to the strong negative correlation in the Heston model, which concentrates the joint distribution near a low-dimensional manifold.

Significance and Claims
The authors position this work as a bridge between the theoretical transparency of regression-based LSM and the data-driven flexibility of modern machine learning methods. The significance of the approach lies in its ability to:

• Eliminate Stepwise Regression: By learning a single operator once in an offline phase, the method avoids the dominant computational costs of LSM and the often required costly retraining steps of deep learning schemes at each exercise time.
• Provide Theoretical Rigor: Unlike many deep learning approaches where statistical properties are less understood, this method offers explicit convergence rates and error bounds that account for both statistical error and low-rank approximation error.
• Scale to High Dimensions: The linear scaling with respect to the number of paths and the offline-online structure make the method computationally tractable for problems involving asset baskets, stochastic volatility, and stochastic interest rates, where classical grid or PDE methods fail.

The paper concludes that the proposed low-rank kernel method offers a robust, efficient, and theoretically grounded alternative for pricing high-dimensional American options, with the total pricing error growing at most linearly with the number of exercise times.