Intuition Behind the Longstaff-Schwartz Implementation

6. Intuition Behind the Longstaff-Schwartz Implementation#

This sections draws significant inspiration from the excellent educational materials by quantgirluk - Understanding Quantitative Finance, whose clear exposition of the Longstaff-Schwartz algorithm provided valuable implementation insights and visualization approaches.

6.1. Geometric Brownian Motion#

We will assume that the dynamics of the prices of the underlying asset follows GBM. That is to say, that the Itô process $\{X_t\}_{t\in\mathbb{N}}$ satisfies the following stochastic differential equation (SDE)

\[ \mathrm{d}X_t = rX_t \, \mathrm{d}t + \sigma X_t \, \mathrm{d}W_t \]

with $X_0 = x_0 > 0$, where $W_t$ denotes a standard Brownian motion, and $r, \sigma$ are known parameters.

6.2. Parameters#

$r = 2\%$,
$\sigma = 15\%$,
$x_0 = 1.0$,
Maturity $T=6$ (6 months),
$N=50$ - simulating $50$ paths on the grid,
$n=120$ - simulating $120$ time-steps (points) [20 days per month].

../_images/75c6f334fe48f19a55b86b4fbb447ac9495921c8d9e1e3aafd7d0808b6d6c031.png

6.3. American Option Contracts#

$S_0 = 1.0$ Initial stock price
We consider American put contract as a writer/seller.
The holder/buyer has the right to exercise the option at any time between today (time $t_0 = 0$) and maturity $t_n = T = 6$.
If the holder decides to exercise at time $t_i$, this means that he will sell the asset (whose market price os $X_{t_i}$ at time $t = t_i$) at price $K= 1.1$ to us (writer).
Why put? Assuming no dividends are being paid, only for the put option it is sometimes optimal to exercise earlier.
- Why? Suppose we have an American call at time $t < T$ with the payoff $[X_t - K]^+$.
  - Alternative strategy: the option holder may short the underlying asset (which gives the payoff $S_t$), and purchase the asset by the most favourable of
    - exercise the American call at maturity, and
    - buying at the market price at time $T$.
  - With the alternative strategy the holder has gained amount $S_t$ at time $t$ and paid out an amount $\leq K$ at time $T$. This is clearly, better than gaining the different $X_t - K$ at time $t$.
  - Hence. it is never optimal to exercise an American call option before the expiry date.
  - American call option must have the same value as a European call option, i.e. $C^{AM} = C^{EU}$.
For a put option, early exercise can be optimal, because:
- We can receive $[K - X_t]$ earlier and invest it,
- If the option is deep in the money (i.e., $S_t \ll K$) and interest rates are positive, early exercise may dominate holding,
- Hence: $P^{AM} \geq P^{EU}$, and strict inequality is possible

K = 1.1

6.4. Discretisation of the domain#

If $S_{t_i} \geq K$, then the holder has no incentive to exercise the option (i.e. selling the asset at price $K$ makes no sense!)
If $S_{t_i} < K$, then the option is In-The-Money (ITM) and rhe holder may want to exercise it. The payoff in case of exercise at time $t_i$ would be $Y(t_i) = [K- S_{t_i}]^+$

Let us visualise the times when the simulated paths have a positive payoff.

../_images/1b3b48ca175df682210f82bc2137f05c8f1a0d629ffb9c273439f3353e70b57b.png

Next, we define the payoff function, recall $[K- S_t]^+ = \max\{(K-S_t, 0)\}$.

../_images/4546b67d14dc38592c80ac8f17696cf83d16a7f4bb3b0014b4cf07d4ebaada5d.png

So, at every time $t_i$, the holder has the right to exercise the option to obtain the payoff, $$ \textrm{Exercise Value} = Y(t_i) = [K - S_{t_i}]^+. $$

Now, the problem is that we do not know if its better to exercise or hold (continue to $t_{i+1}). For this we need to estimate continuation value, that is we need to look one step into the and compare (immediate) exercise value vs. continuation value.

So, how do we estimate continuation value? $$ \textrm{Continuation Value} = C(t_i) = \, \textrm{?} $$

6.5. To exercise or not to exercise - Longstaff-Schwartz Algorithm#

Why is the Monte Carlo computationally infeasible?
- For a fixed $\omega$-path, at each node, we need to decide whether to exercise the option or not, whereas the continuation value is not known without either embedding another MC simulation at each node of each time lattice or a prior exercise strategy, since $$ C(x, t_{n-1}) = e^{-r\Delta t}\mathbb{E}[V(X_{t_n}, t_n) \mid X_{t_{n-1}} = x] $$ V(x, t_{n-1}) = \max\{ \Lambda(x, t_{n-1}, \, C(x, t_{n-1}) \} $$
In order to estimate continuation value, we follow the approach by Longstaff-Schwartz.
The demonstration by Dr D. Santiago’s book provides great intuition.

First, lets plot the discounted cashflows.

cashflow = np.exp(-r * (times[-2] - times[-1])) * exercise_value(X[-1, :]) 
x = X[-2, :]
plt.figure()
plt.plot(x, cashflow, "o", label="Discounted Cashflow")
plt.ylabel("$V(t_{n-1}, t_n)$")
plt.xlabel("Underlying Asset Price $X(t_{n-1})$")
plt.title("At time $t_{n-1}$ we want to approximate the \nContinuation values $C(t_{n-1})$")
plt.legend()
plt.show()

../_images/44b07507dbe2121f80a11575fdb8ecbcc3634f6ef99a0ef2ad2b04ec4369536e.png

Second, in order to estimate the continuation value (or, the conditional expectation), the Longstaff-Schwartz implementation makes use of least-squares method to fit a polynomial function to the pairs

\[ (X(t_{n-1}, \omega), \, V(t_{n-1}, \omega))\]

and then using such polynomials to approximate the continuation value as

\[ C(t_{n-1}) \approx \sum_{j=0}^{\infty} \hat{\alpha}_{ij}L_j(X(t_{i})) \]

So the question is, what if we could do approximation with simple functions (basis functions) multiplied with some weights?

So, we need to make two choices: 1 Polynomial functions e.g. Laguerre (used in paper), Hermite, Chebyshev, Jacobiused as basis functions. 2 Degree of the Polynomial.

6.5.1. Laguerre Polynomials (paper)#

../_images/4cda87d69eccf06a97d7d0714caa00e657d8a977e4ae43b9c7acdc8fa000ee62.png

Where the associated least-sqaures equation takes the following form:

fitted_laguerre

\[x \mapsto \text{-40.33427256}\,{L}_{0}(\text{-0.22920638} + \text{0.46167644}x) + \text{175.93331339}\,{L}_{1}(\text{-0.22920638} + \text{0.46167644}x) - \text{284.7102386}\,{L}_{2}(\text{-0.22920638} + \text{0.46167644}x) + \text{202.52037054}\,{L}_{3}(\text{-0.22920638} + \text{0.46167644}x) - \text{52.77297652}\,{L}_{4}(\text{-0.22920638} + \text{0.46167644}x)\]

../_images/b3cdf90d5ea4d218e170deef69c4ec69d2be306e45c207c6312db201eed36bba.png

../_images/f46e080ad18cc902b3ecbfb1151f040e10d7941110d734d3c2ff135384353a8c.png

\[x \mapsto \text{-0.02912792} + \text{0.01238992}\,\left(\text{-1.45841275} + \text{0.92335288}x\right) + \text{0.35649306}\,\left(\text{-1.45841275} + \text{0.92335288}x\right)^{2} - \text{0.34055114}\,\left(\text{-1.45841275} + \text{0.92335288}x\right)^{3}\]

Now, we focus on only ITM points, i.e. the paths which ended up with non-zero payoff.

../_images/c09e2c020a15b10e28edda2f6fb17323e033890b34c5facdef1c5bd85b3da2be.png

\[x \mapsto \text{0.31672183} - \text{0.2914545}\,\left(\text{-2.66570233} + \text{3.35512271}x\right) - \text{0.0058818}\,\left(\text{-2.66570233} + \text{3.35512271}x\right)^{2} + \text{0.0045486}\,\left(\text{-2.66570233} + \text{3.35512271}x\right)^{3}\]

6.5.2. Iterating Backwards in Time#

Starting at expiry (terminal node) $T = t_n$
At expiry $T$, the payoff is known: $U(t_n) = Y(t_n) = [K- S_{t_n}]^+$.
At time $t_{n-1}$, we need to decide if to exercise or not to exercise, based on: $$ U(t_{n-1}) = \max\{ Y(t_{n-1}, \, C(t_{n-1}) \} $$

where $C(t_{n-1}) \} = e^{-r (t_n - t_{n-1})}\mathbb{E}[U(t_n) \mid \mathcal{F}_{n-1}] $ and $ Y(t_{n-1}) = [K- S_{t_{n-1}}]^+ $.
Notice that if the holder does not exercise, then the option behaves likes an European (the exercise decision has to be made in the next step and there is no early exit choice, so exercise at expiry) over the period $ [t_n, t_{n-1}]$. Thus, we can discount the value $U(t_n)$ and hence obtaining $$ \textrm{Discounted Cashflow} = V(t_{n-1}, t_n) = e^{-r(t_n - t_{n-1})} [K-S_{t_n}]^+.$$

../_images/c1ccb90b75cf36b044e7b34d0e6097fc3096f45b5cede6289008c2808fce3609.png

../_images/dbaa6ed945aa5da544c22ac0c7ac3c347e38d53468ec2b50275d905f3eb5fe79.png

../_images/5cc562a96d5f9b8b59e96c5743e01165ef245010cb1adf7bd5f0019ff1b227be.png

../_images/866e70ecac9f86d30b465659212b9aa10687b4f0768e8785261fbc337ede1519.png

../_images/a09e020ffb961ca771aa8a66743bab8a545e82273f43f47e589cad023d03b2d4.png

What did we learn?

Now, let us go path by path and see if it will be optimal to exercise early.

../_images/e98f436959c1c90e4a6b1c41323d28788e6330b423535418b5aa4c6769260ae1.png

../_images/6b3e1b7166b621ec14d51c4178639f17dc6d563aa4b55d666e1541bfc6d33cc1.png

for idx, path in enumerate(paths[:5]):
    stop = first_exercise_idx[idx]
    (handle_path_before,) = plt.plot(times[:stop], path[:stop], color="lightgreen")
    (handle_path_stop,) = plt.plot(times[stop-1:], path[stop-1:], ':', color="lightgrey")
    if stop < len(times):
        (handle_path_after,) = plt.plot(times[stop-1], path[stop-1], 'r.', zorder=3)
        
strike_line = plt.axhline(y=K, linestyle=':', color="black")
plt.xlabel("Time $t$")
plt.ylabel("$X_t$")
plt.title("Simulated Paths - Continue until Exericise is Optimal")
plt.legend([handle_path_before, handle_path_after, handle_path_stop, strike_line],
            ["Path before Exercise", "First time Exercise Optimal", "Path after Exercise", "Strike $K$"])
plt.show()

../_images/af8ebc112a8f104ae5b8c223375899bd1da99e893f4b4c29fc8a7fc6957ddeae.png