Least squares Monte Carlo for American options

Definition Fix exercise dates $t_k = k\,\Delta t$ for $k = 1, \dots, K$, with $t_K = T$, and a constant continuously compounded rate $r$, so that the money-market account is $B_t = e^{rt}$. Let $\mathbb{Q}$ be a pricing measure for this numeraire, and let the state $X_k = X_{t_k}$, with values in $\mathbb{R}^d$, be a Markov chain under $\mathbb{Q}$ with respect to the information $\mathcal{F}_{t_k}$ available on the exercise dates. The state contains every quantity that the payoff and the later dynamics depend on, for example a running average when the payoff needs one, and $X_0$ is known at time $0$. Write $\mathbb{E}^{\mathbb{Q}}_k[\,\cdot\,] = \mathbb{E}^{\mathbb{Q}}[\,\cdot \mid \mathcal{F}_{t_k}]$, which by the Markov property is a function of $X_k$ when it is applied to a function of the later states. A Bermudan option with exercise payoff $g(X_k) \ge 0$ lets its holder choose one stopping time $\tau$ with values in $\{t_1, \dots, t_K\}$ and pays $g(X_{\tau})$ at $\tau$. In this lesson $\tau$ always denotes a stopping time, not a time to maturity. Assume $\mathbb{E}^{\mathbb{Q}}[g(X_k)^2] < \infty$ for every $k$, which the regressions of the later cards need. The value at time $0$ is

where $\mathcal{T}$ is the set of these stopping times. Under these hypotheses the value follows from dynamic programming, a result proved for finite models in American options and optimal stopping and stated here in general. Set $V_K = g(X_K)$ and, for $k = K - 1, \dots, 1$,

where $C_k$ and $V_k$ are functions of $X_k$, written $C_k(x)$ and $V_k(x)$ at a state $x$. Here $C_k$ is the continuation value, the value at $t_k$ of keeping the option and acting optimally afterward. Date $0$ is not an exercise date, so $V_0^{\mathrm{Berm}} = e^{-r t_1}\,\mathbb{E}^{\mathbb{Q}}[V_1]$, and the rule that stops at the first $t_k$ with $g(X_k) \ge C_k$, or at $t_K$ if there is none, is optimal. If date $0$ were also an exercise date, the value would be $\max\bigl(g(X_0), V_0^{\mathrm{Berm}}\bigr)$. An American option with the same payoff can be exercised at every time in $[0, T]$, so it is worth at least as much. A Bermudan grid approximates it, and the limit as the grid is refined is not treated here.

Definition Fix an exercise date $t_k$ with $k < K$ and a later exercise rule, a stopping time $\tau_{k+1}$ with values in $\{t_{k+1}, \dots, t_K\}$ that decides from the states $X_{k+1}, X_{k+2}, \dots$ as they arrive, for example the optimal rule or one already fitted at the later dates. The regression target is the cash flow of that rule discounted to $t_k$,

and the continuation value of the rule is $C_k = \mathbb{E}^{\mathbb{Q}}_k[Y_k]$, a function of $X_k$ by the Markov property. For the optimal later rule it is the continuation value of the recursion. Choose basis functions $\psi_1, \dots, \psi_J$ of the state, collect them in the vector $\psi(x)$, and assume that $\mathbb{E}^{\mathbb{Q}}[Y_k^2]$ and every $\mathbb{E}^{\mathbb{Q}}[\psi_j(X_k)^2]$ are finite and that the matrix $A = \mathbb{E}^{\mathbb{Q}}[\psi(X_k)\psi(X_k)^{\top}]$ is invertible. For every function $h$ with $\mathbb{E}^{\mathbb{Q}}[h(X_k)^2] < \infty$ the tower rule gives $\mathbb{E}^{\mathbb{Q}}[(Y_k - C_k)\,h(X_k)] = 0$, so for every $\beta \in \mathbb{R}^J$

The first term on the right does not depend on $\beta$, so the least-squares coefficient

makes $\beta^{*\top}\psi(X_k)$ the $L^2(\mathbb{Q})$ projection of $C_k$ onto the span of the basis, and this projection equals $C_k$ when $C_k$ lies in the span. With $N$ training paths, let $\Psi$ be the $N \times J$ matrix with rows $\psi(X_k^{(n)})^{\top}$ and $y$ the vector of their targets. Setting the gradient of $\lVert y - \Psi\beta \rVert^2$ to zero gives the normal equations

with a unique solution when $\Psi$ has full column rank, and the estimate $\widehat{C}_k(x) = \widehat{\beta}^{\top}\psi(x)$. A singular or ill-conditioned $\Psi^{\top}\Psi$ calls for a QR or singular value solve, a rescaled basis or a stated regularization, since forming $\Psi^{\top}\Psi$ squares the condition number of $\Psi$. Many implementations fit only the paths with $g(X_k) > 0$, where exercise is possible. That replaces the law of $X_k$ in the projection by its conditional law given $g(X_k) > 0$, and it needs enough paths in that region.

Definition Least-squares Monte Carlo values a Bermudan option by simulation, replacing each continuation value with a regression estimate. In the setting of the first card, simulate $N$ independent training paths of $X$ under $\mathbb{Q}$ from the known $X_0$ and run the following backward pass.

1. At $t_K$, give each path the cash flow $g(X_K^{(n)})$ paid at $t_K$.
2. For $k = K - 1, \dots, 1$, discount each path’s current cash flow to $t_k$ to get its target, solve the normal equations for $\widehat{\beta}_k$, and on every path with $g(X_k^{(n)}) > 0$ and $g(X_k^{(n)}) \ge \widehat{C}_k(X_k^{(n)})$ replace the cash flow by $g(X_k^{(n)})$ paid at $t_k$.
3. Keep the coefficients $\widehat{\beta}_1, \dots, \widehat{\beta}_{K-1}$, which define the exercise policy of the next card.

The average over the training paths of the final cash flows, discounted to time $0$, is the in-sample estimate $\widehat{V}^{\,\mathrm{in}}$. The targets are realized cash flows of the rule already fitted at the later dates, not fitted values, which is the version usually credited to Longstaff and Schwartz. Each target has conditional mean equal to the continuation value of that later rule, so step 2 is the continuation regression of the previous card. The result carries several separate errors. The basis may not contain $C_k$, the coefficients carry sampling noise, errors in later decisions enter earlier targets, and a finite set of exercise dates only approximates continuous exercise. Convergence as $N$ and $J$ grow needs further conditions and is not treated here.

Definition An exercise policy is a rule that decides on each exercise date, from the information available on that date, whether to exercise. The policy fitted by least-squares Monte Carlo uses the exercise regions $E_k$, which are sets of states, and the stopping time

with $\widehat{\tau} = t_K$ when no such date exists, where it collects $g(X_K)$. It is an admissible exercise time, that is a stopping time with values in the exercise dates, when the coefficients are frozen, meaning fixed before the paths it is applied to are drawn and independent of them. Then the event $\{\widehat{\tau} = t_k\}$ depends only on $X_1, \dots, X_k$ and the fixed coefficients, so it belongs to $\mathcal{F}_{t_k}$. On a path that was used to fit the coefficients, the decisions depend on that path’s own future through $\widehat{\beta}$, and the rule is not a stopping time there. The condition $g > 0$ keeps the rule from exercising for nothing, which matters because a fitted value can be negative while the true value of waiting on a nonnegative payoff never is. Ties $g = \widehat{C}_k$ are broken toward exercise here, and another convention defines another rule. The value of the frozen policy, computed with the coefficients held fixed, is

Definition Independent policy evaluation freezes the coefficients from the training paths, simulates $M$ new paths of $X$ under $\mathbb{Q}$ independent of the training paths, follows $\widehat{\tau}$ on each, and averages the discounted cash flows. Writing $Z^{(m)} = e^{-r\widehat{\tau}} g(X_{\widehat{\tau}})$ on the new path $m$, the estimate is

Given the training paths, the $Z^{(m)}$ are independent and identically distributed with mean $V_0^{\widehat{\tau}}$, so the estimate is unbiased for the value of the frozen policy. When $\mathbb{E}^{\mathbb{Q}}[(Z^{(m)})^2] < \infty$, its standard error is estimated by the sample standard deviation of the $Z^{(m)}$ divided by $\sqrt{M}$, and this measures sampling error only. The policy lower bound states that for every fixed value of the coefficients

where $V_0^{\mathrm{Am}}$ is the value of the American option with the same payoff and continuous exercise, when the model defines one. The first inequality holds because $\widehat{\tau}$ is one of the stopping times in the supremum that defines $V_0^{\mathrm{Berm}}$, and the second because every Bermudan stopping time is also allowed for the American option. Averaging over the training paths gives $\mathbb{E}[\widehat{V}^{\,\mathrm{ind}}] = \mathbb{E}[V_0^{\widehat{\tau}}] \le V_0^{\mathrm{Berm}}$, so the estimate is biased low or unbiased. The bound concerns expectations. A realized estimate can exceed $V_0^{\mathrm{Berm}}$ through sampling error, and an upper bound needs a separate construction, such as a dual martingale method, which is further study. A low value may come from the basis, from too few training paths or from a wrong model of the transition law, and the number alone does not say which.

Definition Fitting bias is the error that an in-sample least-squares Monte Carlo estimate $\widehat{V}^{\,\mathrm{in}}$ gets from fitting the exercise rule on the same paths whose cash flows it averages,

with expectations over the random training paths. On a training path the coefficients depend on that path’s own future, so its decisions partly see that future, and the averaged cash flows do not come from a stopping time. The policy lower bound does not apply to $\widehat{V}^{\,\mathrm{in}}$. Fitting bias is often positive, and in small samples or with flexible bases it can push $\mathbb{E}[\widehat{V}^{\,\mathrm{in}}]$ above $V_0^{\mathrm{Berm}}$. It is separate from the policy gap $V_0^{\mathrm{Berm}} - \mathbb{E}[V_0^{\widehat{\tau}}] \ge 0$, which comes from fitting a suboptimal rule, and from the sampling error of either average. More basis functions can reduce the approximation error of $\widehat{C}_k$ while increasing the variance of $\widehat{\beta}$ and the fitting bias, and a smaller training residual does not imply a better exercise rule. Independent evaluation, or cross-fitting, in which the rule is fitted on one part of the sample and valued on another, keeps fitting bias out of the reported number.