Introduction

A European option is simple: you buy the right to sell a stock at a fixed price on one specific date in the future. If the stock is above that price on expiry day, you exercise; otherwise you don't.

An American option is harder. You have the same right, but you can exercise it any day between now and expiry. Every morning you must ask: is it better to exercise today and pocket the payoff, or hold on in case tomorrow's price is even better?

That question — exercise now or wait — cannot be answered by looking at today's price alone. You need to estimate the continuation value: how much the option is worth if you keep holding it. And that value depends on all the random paths the stock might take in the future.

This is exactly what the Longstaff-Schwartz algorithm (LSM, 2001), invented by Francis Longstaff and Eduardo Schwartz, is designed to do. It simulates thousands of random price paths, then uses least-squares regression — the same tool you use to fit a line through scattered data — to estimate the continuation value at each point along each path. The result is a decision rule: exercise if the immediate payoff exceeds the estimated continuation value, hold otherwise.

The algorithm is a solved method, not an open problem. LSM is the industry standard for American option pricing and is used daily in quantitative finance.

Exercise or Hold

Below is a simplified LSM simulation. The stock starts at $100, the strike price is $100 (a put option: you profit when the stock falls below the strike). There are 5 time steps and a small number of paths.

<!-- LSM American option demo layout -->
<div class="controls">
  <label>Paths: <input id="nPaths" type="range" min="4" max="12" value="8" step="1"> <span id="nPathsVal">8</span></label>
  <label>Strike: lt;input id="strike" type="range" min="90" max="110" value="100" step="1"> <span id="strikeVal">100</span></label>
</div>
<canvas id="chart" width="560" height="220"></canvas>
<div id="status" class="status"></div>
<div class="btns">
  <button id="runBtn" type="button">Run LSM</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div id="legend" class="legend">
  <span class="dot exercised"></span>Early exercise
  <span class="dot held"></span>Held to expiry
  <span class="dot strike-line"></span>Strike price
</div>

/* Demo styles for LSM American option simulation */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .5rem; font-size: .85rem; }
label { display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 100px; }
canvas { display: block; width: 100%; max-width: 560px; border: 1px solid #cdd9e3; border-radius: 8px; margin-bottom: .4rem; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { display: flex; align-items: center; gap: .9rem; font-size: .8rem; flex-wrap: wrap; }
.dot { display: inline-block; width: 14px; height: 4px; border-radius: 2px; margin-right: 3px; vertical-align: middle; }
.dot.exercised { background: #e63946; }
.dot.held { background: #457b9d; }
.dot.strike-line { background: #999; border-top: 2px dashed #999; height: 0; width: 18px; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Longstaff-Schwartz (LSM) algorithm: price American put by backwards
// induction + least-squares regression to estimate continuation value

const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');
const statusEl = document.getElementById('status');
const nPathsIn = document.getElementById('nPaths');
const nPathsVal = document.getElementById('nPathsVal');
const strikeIn = document.getElementById('strike');
const strikeVal = document.getElementById('strikeVal');

// Model parameters: S0=initial price, r=risk-free rate, sigma=volatility
const S0 = 100;
const r = 0.05;
const sigma = 0.2;
const T = 1.0;
const STEPS = 5;
const dt = T / STEPS;
const discount = Math.exp(-r * dt);

function setStatus(msg, cls) {
  statusEl.textContent = msg;
  statusEl.className = 'status ' + (cls || '');
}

// Simulate stock price paths under geometric Brownian motion (GBM)
function simulatePaths(nPaths, seed) {
  const paths = [];
  let rng = seed;
  // simple deterministic RNG for reproducibility
  const rand = () => { rng = (1664525 * rng + 1013904223) & 0xffffffff; return (rng >>> 0) / 0xffffffff; };
  const randn = () => {
    // Box-Muller transform for standard normal samples
    const u = rand() + 1e-10, v = rand();
    return Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * v);
  };
  for (let i = 0; i < nPaths; i++) {
    const path = [S0];
    for (let t = 0; t < STEPS; t++) path.push(path[t] * Math.exp((r - 0.5 * sigma * sigma) * dt + sigma * Math.sqrt(dt) * randn()));
    paths.push(path);
  }
  return paths;
}

// Put payoff: max(K - S, 0)
function putPayoff(s, K) { return Math.max(K - s, 0); }

// Simple OLS linear regression for continuation value estimation
function ols(xs, ys) {
  // Basis: 1 + S (linear; sufficient for this small demo)
  const n = xs.length;
  if (n < 3) return () => 0;
  let sx = 0, sy = 0, sx2 = 0, sxy = 0;
  for (let i = 0; i < n; i++) { sx += xs[i]; sy += ys[i]; sx2 += xs[i] * xs[i]; sxy += xs[i] * ys[i]; }
  const denom = n * sx2 - sx * sx;
  if (Math.abs(denom) < 1e-10) return () => sy / n;
  const b1 = (n * sxy - sx * sy) / denom;
  const b0 = (sy - b1 * sx) / n;
  return (x) => b0 + b1 * x;
}

// LSM backward induction: work from STEPS-1 down to t=1
function runLSM(paths, K) {
  const nPaths = paths.length;
  // cashflow[i] = discounted future payoff along path i
  const cashflow = paths.map(p => putPayoff(p[STEPS], K));
  const exerciseStep = new Array(nPaths).fill(STEPS);

  for (let t = STEPS - 1; t >= 1; t--) {
    // In-the-money paths at step t (immediate payoff > 0)
    const itmIdx = paths.map((p, i) => [i, p[t], putPayoff(p[t], K)]).filter(([, , pf]) => pf > 0);
    if (itmIdx.length < 2) continue;

    const xs = itmIdx.map(([, s]) => s);
    const ys = itmIdx.map(([i, , pf]) => discount * cashflow[i]);
    const contFn = ols(xs, ys);

    for (const [i, s, immPay] of itmIdx) {
      if (immPay > contFn(s)) {
        cashflow[i] = immPay;
        exerciseStep[i] = t;
      }
    }
  }
  return exerciseStep;
}

let lastPaths = null;
let lastExercise = null;
let lastK = 100;

function run() {
  const nPaths = parseInt(nPathsIn.value);
  const K = parseInt(strikeIn.value);
  lastK = K;
  // fixed seed for reproducibility
  lastPaths = simulatePaths(nPaths, 42 + nPaths * 7);
  lastExercise = runLSM(lastPaths, K);
  draw(lastPaths, lastExercise, K);
  const exercised = lastExercise.filter(s => s < STEPS).length;
  setStatus(i18nFmt('LSM complete: %exercised% of %total% paths exercise early.', { exercised, total: nPaths }), 'ok');
}

function draw(paths, exerciseStep, K) {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  const pad = { top: 18, bottom: 28, left: 40, right: 12 };
  const allPrices = paths.flat();
  const minS = Math.min(...allPrices, K) * 0.97;
  const maxS = Math.max(...allPrices, K) * 1.03;
  const xOf = (t) => pad.left + (t / STEPS) * (W - pad.left - pad.right);
  const yOf = (s) => pad.top + (1 - (s - minS) / (maxS - minS)) * (H - pad.top - pad.bottom);

  // vertical grid lines at each time step
  ctx.strokeStyle = '#e0e7ef';
  ctx.lineWidth = 1;
  for (let t = 0; t <= STEPS; t++) {
    ctx.beginPath(); ctx.moveTo(xOf(t), pad.top); ctx.lineTo(xOf(t), H - pad.bottom); ctx.stroke();
  }
  // dashed horizontal line at strike price
  ctx.strokeStyle = '#aaa';
  ctx.setLineDash([4, 4]);
  ctx.lineWidth = 1.2;
  ctx.beginPath(); ctx.moveTo(pad.left, yOf(K)); ctx.lineTo(W - pad.right, yOf(K)); ctx.stroke();
  ctx.setLineDash([]);

  // draw each simulated path
  paths.forEach((path, i) => {
    const es = exerciseStep[i];
    const color = es < STEPS ? '#e63946' : '#457b9d';
    ctx.strokeStyle = color;
    ctx.lineWidth = 1.5;
    ctx.globalAlpha = 0.7;
    ctx.beginPath();
    path.forEach((s, t) => { if (t === 0) ctx.moveTo(xOf(t), yOf(s)); else ctx.lineTo(xOf(t), yOf(s)); });
    ctx.stroke();
    // mark early exercise point
    if (es < STEPS) {
      ctx.globalAlpha = 1;
      ctx.fillStyle = '#e63946';
      ctx.beginPath(); ctx.arc(xOf(es), yOf(path[es]), 4.5, 0, 2 * Math.PI); ctx.fill();
    }
  });
  ctx.globalAlpha = 1;

  // axis labels
  ctx.fillStyle = '#555';
  ctx.font = '11px system-ui, sans-serif';
  ctx.textAlign = 'center';
  for (let t = 0; t <= STEPS; t++) ctx.fillText('t=' + t, xOf(t), H - 8);
  ctx.textAlign = 'right';
  const ticks = 4;
  for (let i = 0; i <= ticks; i++) {
    const s = minS + (i / ticks) * (maxS - minS);
    ctx.fillText('


At each time step the algorithm regresses the immediate payoff (if positive) against the simulated stock price to estimate the continuation value. A path exercises at the first step where the immediate payoff exceeds the estimated continuation value. Notice how different paths exercise at different times — or not at all. This is the key insight of LSM: early exercise is path-dependent, and regression approximates the value of waiting.

 + Math.round(s), pad.left - 3, yOf(s) + 4);
  }
}

nPathsIn.addEventListener('input', () => { nPathsVal.textContent = nPathsIn.value; });
strikeIn.addEventListener('input', () => { strikeVal.textContent = strikeIn.value; });

document.getElementById('runBtn').addEventListener('click', run);
document.getElementById('resetBtn').addEventListener('click', () => {
  nPathsIn.value = 8; nPathsVal.textContent = 8;
  strikeIn.value = 100; strikeVal.textContent = 100;
  lastPaths = null; lastExercise = null;
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  setStatus('Adjust sliders and click Run LSM.', 'info');
});

setStatus('Adjust sliders and click Run LSM.', 'info');
Result
Console

At each time step the algorithm regresses the immediate payoff (if positive) against the simulated stock price to estimate the continuation value. A path exercises at the first step where the immediate payoff exceeds the estimated continuation value. Notice how different paths exercise at different times — or not at all. This is the key insight of LSM: early exercise is path-dependent, and regression approximates the value of waiting.

The Real Complexity

LSM looks deceptively simple but hides several layers of computational thinking.

The backwards induction structure. At expiry, the payoff is known exactly. LSM works backwards in time: at each step tt it uses the paths that are in the money (immediate payoff >0> 0) to regress payoff against the current stock price StS_t, estimating the continuation value C^(St)\hat{C}(S_t). A path exercises at step tt if the immediate payoff exceeds C^(St)\hat{C}(S_t).

Regression and basis functions. The continuation value is approximated by a linear combination of basis functions — typically low-degree polynomials like 1,St,St21, S_t, S_t^2. The coefficients are fitted by ordinary least squares at each time step. More basis functions give a better fit but increase cost.

Cost. With NN simulated paths, TT time steps, and BB basis functions, the dominant cost is O(N⋅T⋅B2)O(N \cdot T \cdot B^2) — roughly, fitting a small regression at each of TT steps across NN paths. In practice NN is tens of thousands and TT is dozens to hundreds.

Bias and variance. The regression introduces a small downward bias (the estimated continuation value is a lower bound on the true one). Increasing NN reduces variance; increasing BB reduces bias but risks overfitting. The method converges to the true price as N→∞N \to \infty with appropriate basis functions.

Why not dynamic programming? A grid-based approach works for one underlying asset but suffers the curse of dimensionality: the state space explodes exponentially when the payoff depends on multiple assets (e.g., basket options). Monte Carlo scales to hundreds of dimensions; grid methods do not. This is the key advantage of Monte Carlo over deterministic methods for high-dimensional option pricing.

Where It Matters

"Hold or exercise now?" is one of the most universal decision problems in finance and beyond:

  • American equity options: millions of contracts traded daily on exchanges like the CBOE are American-style — LSM or its variants price them and manage their risk.
  • Bermudan options: exercise is allowed on a discrete set of dates (e.g., once a month). LSM handles these naturally since it already works on a discrete time grid.
  • Mortgage prepayment: homeowners can repay their mortgage early when interest rates drop. Modelling this as an optimal stopping problem uses exactly the same regression trick.
  • Real options analysis: a company deciding whether to delay, expand or abandon a capital project faces an American-style option on real assets. LSM is used in corporate finance and energy project valuation.
  • Executive stock options: employees can exercise vesting shares during a window — the optimal exercise policy is computed with variants of LSM.

The deeper pattern is optimal stopping: given a stochastic process, when should you stop to maximize expected reward? LSM turns this into a sequence of regressions, making it tractable wherever Monte Carlo simulation is feasible.

Conclusion

The Longstaff-Schwartz algorithm is a beautiful meeting point of simulation, linear algebra, and financial economics. The insight — that the optimal exercise boundary can be learned by regressing future cash flows against today's state — turned an apparently intractable high-dimensional problem into a handful of ordinary least-squares fits.

Every morning, quant desks around the world run variants of LSM to price American options, stress-test portfolios, and hedge risk. The next time you hear that someone "exercised their option early," there is a good chance a backward-induction regression decided exactly when that moment should be.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/american-option-lsm/Content licensed under CC BY-NC 4.0.