Least-Squares Monte Carlo for Early-Exercise Options

Quants who value Bermudan-style products, and the risk managers who validate those valuations, sometimes need to check how the exercise decision is made path by path. Monte Carlo simulation values an option from simulated paths, and a right that can be exercised before expiry needs a way to make the exercise decision on each path.

Why paths alone cannot settle exercise

The holder of an American option or a Bermudan option compares, at each date when exercise is allowed, the amount received by exercising now (the exercise value) with the value of keeping the option. The latter is the continuation value: the expected value of the discounted future cash flows, given the information at that time¹.

Let the exercise dates be $t_1 < t_2 < \dots < t_n = T$, let $S$ be the price of the underlying asset on the $k$-th date, and let the interest rate $r$ be constant. The continuation value $C_k(S)$ is given by the following formula. Here the cash flow $CF_j$ is received at $t_j$ when the option is exercised optimally after $t_k$, and the expectation $E^Q$ is taken under the risk-neutral probability².

$$C_k(S) = E^Q\left[\sum_{j>k} e^{-r(t_j - t_k)}\, CF_j \mid S_{t_k} = S\right]$$

The policy that maximizes the option value is to exercise on the first date when the exercise value is positive and at least the continuation value². But the continuation value cannot be known from generated paths alone. A single path alone cannot settle whether to exercise. So least-squares Monte Carlo (LSM) uses information across paths. It takes the future cash flows of many paths that sit at similar prices on the same date, and estimates the continuation value as a function of the underlying price by least squares³.

There are a finite number $n$ of exercise dates, so the option is Bermudan. With $n$ large enough, it approximates an American option that can be exercised continuously⁴.

The backward regression procedure

LSM steps back through the exercise dates one at a time, from expiry to today⁵. The cash flow at expiry $t_n$ starts from $\max(K - S, 0)$ for a put option, where $K$ is the strike price and $S$ is the underlying price. On exercise date $t_k$, the procedure is as follows.

1. On each path, discount the cash flows received after $t_k$ to $t_k$, and call the result $Y$.
2. Select only the paths whose exercise value $K - S$ is positive (the in-the-money paths), and regress $Y$ on a set of functions of the price $S$ (basis functions) to get the estimate $\hat{C}_k(S)$ of the continuation value.
3. For each selected path, exercise if $K - S > \hat{C}_k(S)$. Delete the path's cash flows after $t_k$ and set its cash flow at $t_k$ to $K - S$.
4. Move to the previous exercise date and repeat from step 1.

When the first exercise date has been processed, let $\tau_i$ be the exercise time on path $i$. The price is the average over all paths of the cash flows discounted to today⁵. A path that is never exercised counts as 0.

$$V_0 = \frac{1}{N}\sum_{i=1}^{N} e^{-r\tau_i}\,\bigl(K - S_i(\tau_i)\bigr)$$

The regression in step 2 writes the continuation value as a linear combination of basis functions $\phi_0, \dots, \phi_d$, and finds the coefficients $a_j$ that minimize the squared error over the in-the-money paths. The highest index $d$ is the degree.

$$\hat{C}_k(S) = \sum_{j=0}^{d} a_j\,\phi_j(S/K), \qquad \min_{a}\sum_{i:\,K - S_i > 0}\Bigl(Y_i - \sum_{j=0}^{d} a_j\,\phi_j(S_i/K)\Bigr)^2$$

Polynomials such as $1, S/K, (S/K)^2, \dots$ can serve as basis functions. Dividing the price by the strike puts it on a common scale. The Longstaff and Schwartz (2001) paper gives weighted Laguerre polynomials as an example, and reports that simple powers and trigonometric series also gave accurate results⁶. The simulator on this page also uses the powers $(S/K)^j$.

Three points in the procedure drive the result.

• The dependent variable $Y$ is not the payoff at expiry. A path exercised on a later date loses its cash flow at expiry, so $Y$ uses the discounted cash flows actually received under the policy.
• Only the in-the-money paths enter the regression. The exercise decision matters only on those paths, and using all paths needs more basis functions for the same accuracy⁷.
• The fitted value $\hat{C}_k$ is used only to decide whether to exercise. The cash flow is $K - S$ on a path that exercises and the realized value fixed by later steps on a path that continues. Discounting and adding the fitted values would bias the price upward⁸.

A worked example with eight paths

Consider a hypothetical example in which an American put with a strike price of 1.10, exercisable at $t = 1, 2, 3$ (with $t = 3$ the expiry), is valued with an interest rate of 6% (continuously compounded), a current price of 1.00, no dividends, and eight paths⁹. The one-period discount factor is $e^{-0.06} = 0.941765$. The basis functions in this example are the price itself, $1, S, S^2$, without rescaling.

At expiry $t = 3$, paths 3, 4, 6, and 7, where the exercise value $1.10 - S$ is positive, receive 0.07, 0.18, 0.20, and 0.09. The other paths receive 0.

At $t = 2$, five paths are in the money (price below 1.10): paths 1, 3, 4, 6, and 7. Here $Y$ is the cash flow at $t = 3$ discounted by one period. Regressing it on $1, S, S^2$, where $S$ is the price at $t = 2$, gives $\hat{C}_2(S) = -1.06999 + 2.98341S - 1.81358S^2$¹⁰.

Paths 4, 6, and 7 exercise at $t = 2$, so their cash flows at $t = 3$ disappear and their cash flows at $t = 2$ become 0.13, 0.33, and 0.26. Path 3 continues, so its 0.07 at $t = 3$ remains.

At $t = 1$, five paths are in the money: paths 1, 4, 6, 7, and 8. Paths 2, 3, and 5 have prices of 1.10 or more, so they do not enter the regression. Here $Y$ is the cash flow left after the decisions at $t = 2$, discounted to $t = 1$. Paths 4, 6, and 7 use their cash flow at $t = 2$ discounted by one period, and paths 1 and 8 use 0. The regression is $\hat{C}_1(S) = 2.03751 - 3.33544S + 1.35646S^2$¹⁰.

Paths 4, 6, 7, and 8 exercise at $t = 1$, so their cash flows at $t = 2$ and later disappear. The cash flow on path 4 changes from 0.13 to 0.17, on path 6 from 0.33 to 0.34, and on path 7 from 0.26 to 0.18.

The decisions at $t = 1$ can turn out wrong on individual paths. On path 7, continuing gives $Y$ of 0.2449, above the exercise value of 0.18, but the fitted value of 0.117 is low, so the path exercises. On path 1, the exercise value is 0.01, but the fitted value of 0.013 is higher, so the path continues, and it still ended at 0. The fitted value is an estimate averaged across paths, so the rule is chosen to do best on average across paths. Path 8 is an example of a correct decision: continuing would have paid 0, so exercising for 0.22 was right.

Finally, discount the first cash flow on each path to today.

The present values sum to 0.91547, and their average over eight paths is the price, 0.1144. On the same eight paths, a European option that can be exercised only at expiry is worth 0.0564: the cash flows at expiry on paths 3, 4, 6, and 7 total 0.54, multiplied by the three-period discount factor of 0.835270 and divided by 8. The American put is worth about twice as much¹⁰.

Prices and the exercise boundary under the default conditions

Consider a hypothetical example in which an American put with a current price of 100, a strike price of 110, a term of 1 year, an interest rate of 6%, volatility of 20%, and no dividends is valued with 50 exercise dates, 5,000 paths, and a degree-2 basis. As in the eight-path example, the strike is 1.10 times the current price and the interest rate is 6%. The paths follow a geometric Brownian motion under the risk-neutral measure, and the benchmarks are a binomial tree of about 1,000 steps and the Black-Scholes formula¹¹.

The difference between LSM and the Bermudan binomial tree is 0.0031, about 3% of the standard error. The continuously exercisable American is 0.0225 higher than the Bermudan with 50 exercise dates. The 1.6070 that LSM adds over the European option is the value of being able to exercise before expiry (the early exercise premium), about 16% of the European price.

The price where the fitted continuation value curve from each date's regression crosses the exercise value line $K - S$ is that date's exercise boundary. Among the in-the-money paths, those with prices below the boundary are exercised. Under the default conditions, the boundary is about 93.6 on exercise date 10 (0.2 years) and about 92.0 on exercise date 25 (0.5 years). The paths that finally exercise on those dates are about 4.0% and about 0.6% of all paths.

Effects of the degree, the exercise dates, and the paths

A higher degree lets the regression curve represent more shapes of the continuation value, and the exercise policy moves closer to the optimal one. Averaging over 20 sets of random numbers, with the same market inputs as the simulator's defaults but 50 exercise dates and 12,000 paths, gives the following¹². The table sets the price on the regression paths (in-sample) beside the price on separate paths (out-of-sample). The price on separate paths is 0.147 below the Bermudan binomial tree (11.6353) at degree 1, and within 0.004 of the tree at degree 3 and above.

The number of exercise dates $n$ follows the exercise dates of the product. With the same 5,000 paths and degree 2, LSM and the Bermudan binomial tree change with $n$ as follows¹¹. A single exercise date ($n = 1$) is the European option.

The price rises with the number of exercise dates and approaches 11.6578 for the continuously exercisable American. In every row with two or more exercise dates, the difference between LSM and the tree is within the standard error.

The number of paths affects the standard error. With 1,000, 5,000, and 12,000 paths, the standard error is 0.2496, 0.1206, and 0.0749¹¹. With 12 times the paths, the standard error shrinks by about 3.3 times, close to the factor of about 3.5 (the square root of 12) expected because the standard error is inversely proportional to the square root of the number of paths. How the standard error is found is covered in Monte Carlo Simulation.

The lower bound and the in-sample bias

LSM decides the exercise rule from the regression on each exercise date. The optimal policy maximizes the value, so the value obtained from the LSM policy does not exceed the true price. With the number of basis functions and the number of exercise dates chosen and the coefficients on each date fixed, the Longstaff and Schwartz paper shows that the average of the values from the LSM policy is at most the true price as the number of paths grows without limit¹³. This is why the price on separate paths runs low. The point where the price stops rising as basis functions are added is a guide to convergence¹³.

On the other hand, if the price is evaluated on the same paths used for the regression, the policy follows the noise in those paths and the price tends to run high. This is look-ahead bias, and it runs in the opposite direction to the downward bias from a suboptimal policy. The LSM estimate contains both¹⁴. The standard way to avoid it is to evaluate on separate paths, which doubles the cost of generating paths¹⁴.

Earlier studies find that look-ahead bias grows with fewer paths and a higher degree¹⁴. The following table averages 20 sets of random numbers, with the regression paths and the evaluation paths generated from different random numbers¹². The difference is the price on the regression paths minus the price on separate paths. In these averages it is positive in every row, though it can be negative for individual sets of random numbers.

The Bermudan binomial tree is 11.6353, and the fewer the paths, the further the price on separate paths falls below it. With 1,000 paths and degree 4 it is 0.152 lower, and with 12,000 paths and degree 4 the two nearly coincide. The difference shrinks as the number of paths grows, and with 12,000 paths it is within the standard error. At every number of paths, the difference at degree 4 is larger than at degree 2, but the gap between them is about the size of the standard error of the difference. With the screen's default random numbers, switching 5,000 paths and degree 2 to "separate paths" changes the price from 11.6384 to 11.6287.

The standard error is the statistical error from the spread of the path values. It includes neither the downward bias from a suboptimal policy nor the upward bias from using the same paths.

Assumptions and limits

An American call on a stock that pays no dividends, when the interest rate is positive, gives up time value if exercised before expiry, so its price equals that of the European call¹⁵. There is no need to estimate a continuation value by regression, and the simulator on this page handles only the American put. Early exercise of a put can pay when the stock has fallen sharply, because receiving the strike now can be worth more than waiting¹⁵.

The simulator on this page holds the interest rate and volatility constant, builds paths as a geometric Brownian motion, and handles only continuous dividend yields. One assumption is that the only state variable is the underlying price. With two state variables, the basis functions include both variables and their cross terms⁵. Changing the degree from 2 to 1 lowers LSM from 11.6384 to 11.5037 under the default conditions, because the basis can no longer represent the curvature of the continuation value and the policy gets worse.

In implementation, basis functions that resemble one another do not change the result, because the algorithm uses the fitted value, not the individual coefficients. But when the matrix of cross-products of the basis functions is close to singular, numerical errors appear. The Longstaff and Schwartz paper divides prices and cash flows by the strike to put them on the same scale, and solves the regression in double precision¹⁶.

For Bermudan swaptions, deciding early exercise needs a technique such as least-squares Monte Carlo, and the computational load rises further¹⁷. The product itself is covered in Bermudan Swaptions. The paths are built with an interest rate model such as the LIBOR market model.

Notes

1. Lyuu, "American Option Pricing by Simulation" (external site), Page 927. The continuation value is the conditional expectation of the payoff from keeping the option alive now, and the holder compares the exercise value with it. ↩

2. Longstaff and Schwartz (2001) (external site), page 121 (Section 2.1), equation (1) and the text just after it. Exercising as soon as the exercise value is positive and at least the continuation value maximizes the value. ↩ ↩²

3. Lyuu's lecture notes (external site), Pages 927–928. A single path is not enough for the exercise decision, so the continuation value is estimated from information across paths by least squares. The paper presents the same idea on page 115 (Section 1) and page 120. ↩

4. Longstaff and Schwartz (2001) (external site), page 121 (Section 2.1). It treats the exercise dates as $n$ discrete points in time, and approximates continuous exercise by making $n$ sufficiently large. ↩

5. Longstaff and Schwartz (2001) (external site), pages 122–123 (Section 2.2). It regresses backward on each exercise date, then discounts the cash flows from the first exercise time and averages over all paths. ↩ ↩² ↩³

6. Longstaff and Schwartz (2001) (external site), pages 122–123 (equations (2)–(6) and the sentences after them). The paper says that simple powers and trigonometric series also give accurate results. ↩

7. Longstaff and Schwartz (2001) (external site), page 123 (Section 2.2) and its footnote 8. Using all paths needed two to three times as many basis functions or more in some cases for the same accuracy. ↩

8. Longstaff and Schwartz (2001) (external site), page 118 (Section 1) and footnote 9 on page 125. Discounting the estimated value can bias the price upward, because the maximum operator is convex. ↩

9. Longstaff and Schwartz (2001) (external site), pages 116–120 (Section 1). The paths, the strike of 1.10, the 6% rate, and exercise at times 1 to 3 follow this example, which generates the paths under the risk-neutral measure. ↩

10. Longstaff and Schwartz (2001) (external site), pages 117, 119, and 120. The paper shows the regressions as −1.070 + 2.983S − 1.813S² and 2.038 − 3.335S + 1.356S², a price of 0.1144, and a European value of 0.0564. The paper's continuation values were computed with coefficients rounded to three digits, so they differ from the tables here by up to 0.0005. ↩ ↩² ↩³

11. The results come from the same calculation as this site's lsm simulator. The random paths use a fixed seed, and the binomial tree has about 1,000 steps. ↩ ↩² ↩³

12. This is the average of 20 pairs of random numbers (seeds 1–20 for the regression paths, and separate random numbers for the evaluation paths). It uses 50 exercise dates and a Bermudan binomial tree value of 11.6353, and the other conditions are the defaults. ↩ ↩²

13. Longstaff and Schwartz (2001) (external site), pages 124–125 (Proposition 1 in Section 2.3 and the explanation after it). The value of an LSM policy with fixed coefficients is at most the true price, and adding basis functions until the value stops increasing serves as a guide. ↩ ↩²

14. Woo, Liu, and Choi (external site), pages 2–4 (Section 1.1). Two kinds of bias run in opposite directions. The standard remedy of separate paths doubles the cost. Earlier studies find look-ahead bias rising with fewer paths and a higher polynomial order. ↩ ↩² ↩³

15. Courant Institute lecture notes "American Options" (external site) (Lecture 8). For calls, Section 1.1, items 3 and 4 with notes (a) and (b) (pages 1–2); for puts, item 3 of the same section with its note (page 3). ↩ ↩²

16. Longstaff and Schwartz (2001) (external site), pages 142–143 (Section 8.3). The fitted value is unaffected by correlation among basis functions; numerical error arises when the cross-product matrix is nearly singular; prices are normalized by dividing by the strike. ↩

17. Haruyasu Ota, "マルコフ関数モデルによる金利オプションの価格付けの実用化" (external site) (Putting the Markov-functional model into practice for pricing interest rate options; tentative translation), Kinyu Kenkyu, Institute for Monetary and Economic Studies, Bank of Japan (October 2010), page 132, "1. はじめに" (1. Introduction) (in Japanese). Options with early exercise rights need a technique such as the least-squares Monte Carlo method of Longstaff and Schwartz, which raises the computational load further. ↩