Numerical Methods

Bagaria, Sarthak

Chapter 19 Numerical Methods

Almost every model in these notes was chosen for the same reason, and it was not realism. Affine dynamics give Riccati equations — closed-form bonds for Gaussian short rates, a characteristic function for Heston — SABR gives an expansion, and each of those buys a price in microseconds, which is what made calibration possible on the hardware the models were designed for. That constraint shaped the canon, and it has largely lifted. This chapter is about what replaced it: what a lattice and a simulation actually cost, why early exercise is where the difficulty concentrates, and what becomes available once a model is no longer required to have a formula. We measure the costs rather than assert them, including two biases in the standard method for early exercise that pull in opposite directions and are usually discussed as one.

19.1 The Constraint That Chose the Models

Model	What it was built to give in closed form
Affine models: Vasicek, Hull-White, Heston	Bonds, or a characteristic function, via Riccati
(ch. 14)	equations — bonds become swaptions by chapter 8’s
	Jamshidian decomposition
SABR (ch. 10)	An asymptotic expansion for implied volatility
Quasi-Gaussian (ch. 12)	A finite Markov state, so a low-dimensional grid

None of these was selected because the world behaves that way. Each was selected because a calibration needs thousands of model prices, and a model that takes a second to price cannot be calibrated at all if a second is what one has for the whole exercise.

Remark (What the constraint cost).

The earlier chapters have already itemised the bill without presenting it as one. Chapter 10’s local volatility model fits every European price and predicts the wrong dynamics. Chapter 10’s SABR fits one expiry and is not consistent across expiries. Chapter 12’s quasi-Gaussian models buy a finite state by insisting the volatility structure decay exponentially, which nothing in the market requires. Chapter 18’s Gaussian copula is the extreme case: chosen because it is easy to simulate and calibrate, and structurally unable to represent the one quantity it was used for.

In each case a functional form was adopted because it was solvable, and the market then declined to agree. That is not an argument against the models — they are still what one reaches for, and most of this chapter’s alternatives are slower and less understood. It is an argument for knowing which of a model’s properties are markets and which are convenience.

Structure (Which constraint is binding now).

The models of chapter 5 through chapter 12 were selected under a constraint: a price had to be computable by hand, or by a machine far weaker than the one on any desk today. That constraint chose affine dynamics, exponential volatility structures and one-factor curves, and it chose them for tractability rather than for realism — which is what chapter 14 spends a chapter making precise.

That constraint has lifted. What has not lifted, and what this chapter argues is now the binding one, is identification. A model can be solved numerically at almost any complexity; it cannot be told apart from its neighbours by the instruments the market quotes. These notes have measured that three times over — SABR’s $\beta$ against its correlation, local-stochastic volatility’s mixing weight, and quasi-Gaussian’s mean reversion — and in each case the flatness was a property of the quoted instruments rather than of the optimiser. Compute stopped binding and data started.

So the question is not whether a solvable model is still necessary. It is not. The question is what solvability was providing besides speed, and the answer turns out to be two things: prices that are arbitrage-free for structural rather than statistical reasons, and errors one can bound in advance. The next section is about the first and §19.7 about the second.

19.2 Two Ways to Compute

Everything that is not a closed form is one of two things, and their weaknesses are complementary in a way that decides most practical choices.

Lattices and grids

Backward induction on a tree, or a finite difference solution of the pricing equation of chapter 5. Chapter 9’s Dupire forward equation can be run the other way for a whole strike surface at once.

The virtues are exactness and early exercise. There is no sampling error — refine the grid and the answer converges, at a rate that is second order in the spacing for a decent scheme — and early exercise is free, because backward induction already knows the continuation value when it needs to compare against intrinsic. That is why chapter 20’s model selection table sends callables to short rate models: not because those models are more realistic, but because their small state fits on a grid.

The vice is dimension. A tensor grid with $n$ points per axis in $d$ dimensions has $n^{d}$ points:

$d$	points	$d$	points
$1$	$10^{2}$	$4$	$10^{8}$
$2$	$10^{4}$	$5$	$10^{10}$
$3$	$10^{6}$	$6$	$10^{12}$

at a hundred points an axis. Three dimensions is comfortable, four is a project, and five is not happening. A basket over ten underlyings, or a market model with twenty forward rates, is not a large grid — it is no grid at all.

Simulation

Monte Carlo has exactly the opposite profile. Its error depends on the number of paths and not on the dimension, and it handles path dependence without any special effort because it has the path.

Calculation 19.1 (The rate, measured).

The standard error of a Monte Carlo estimate falls as $1/\sqrt{N}$ . Pricing a one year European put in quant/src/numerics.rs:

Paths	Standard error	Error $\times\sqrt{N}$
$10^{3}$	$0.349$	$11.02$
$10^{4}$	$0.107$	$10.67$
$10^{5}$	$0.0343$	$10.85$
$10^{6}$	$0.0109$	$10.89$

The last column is flat across three decades, which is the rate confirmed rather than assumed.

The second half of that claim decides which method a problem gets. Doing it honestly needs an integral whose dimension can be varied while everything else is held still, so build one: drive a single lognormal with $d$ independent normals combined into one,

Z=\frac{z_{1}+\cdots+z_{d}}{\sqrt{d}},\qquad F_{T}=F\exp\left(-\tfrac{1}{2}% \sigma^{2}T+\sigma\sqrt{T}\,Z\right).

(19.1)

$Z$ is standard normal for every $d$ , so a call on $F_{T}$ has the same Black-76 price at every $d$ , and its payoff has the same distribution — and therefore the same variance. Only the dimension of the integral changes. Anything that varies with $d$ is then a property of the method and not of the problem.

Calculation 19.2 (The dimension, measured).

A one year at-the-money call, $F=K=100$ , $\sigma=20\%$ , worth $7.9656$ at every dimension. Both methods are given the same budget of $10^{5}$ payoff evaluations: the grid spends it as $n^{d}$ nodes with $n$ as large as that allows, the simulation as $10^{5}$ paths.¹¹1numerics::DimensionTest.

$d$	nodes an axis	grid error	simulation error
$1$	$100000$	$0.00000$	$0.025$
$2$	$316$	$0.00001$	$0.033$
$3$	$46$	$0.026$	$0.039$
$4$	$17$	$0.007$	$0.039$
$5$	$10$	$0.294$	$0.012$
$6$	$6$	$6.134$	$0.016$
$7$	$5$	$5.942$	$0.028$

The grid is not merely better in one and two dimensions, it is in a different league — a deterministic rule converges in the mesh, not in the square root of a sample. By six dimensions it is wrong by three quarters of the price. The simulation column has no trend in it at all.

The middle rows wobble because $n$ moves in integer steps and the payoff’s kink lands between nodes differently each time; the collapse is the signal, not the ordering of $d=3$ against $d=4$ .

The cliff has a location and a reason. The grid gets $n=\lfloor B^{1/d}\rfloor$ nodes an axis out of a budget $B$ , so a budget spread over more axes leaves too few points on each to resolve anything: a hundred thousand evaluations is a hundred thousand nodes on one axis and five nodes on each of seven. Equivalently, to hold the mesh fixed the cost is $n^{d}$ , which is the table at the top of this section read as an error rather than as a point count.

The simulation’s flatness is exactly true here and only approximately true in practice. The standard error is $\sigma_{\text{payoff}}/\sqrt{N}$ , and the dimension appears nowhere in it. Measured across $d=1,2,4,8,16$ it is $0.0416$ every time, to three figures. But (19.1) was built so that the payoff’s own standard deviation is the same at every dimension, and that is the part a real problem does not give you: a basket over ten assets, or a market model with twenty rates, generally has a payoff whose variance grows with the number of factors. Dimension independence is a statement about the exponent. The constant is still the payoff’s standard deviation, and that is a modelling quantity, not a numerical one.

Remark (What the rate means for a desk).

Four times the work to halve the error. A price good to a cent needs a hundred times the paths of one good to ten cents, and a Greek computed by bumping needs the difference of two such numbers, which is why Greeks are the expensive part of a simulation and why pathwise and adjoint methods exist.

Variance reduction — antithetics, control variates, importance sampling — improves the constant, sometimes by a large factor, and leaves the exponent alone. Quasi-Monte Carlo is the one technique that changes the rate, approaching $1/N$ when the effective dimension is low, which is a genuinely different proposition and worth reaching for when it applies.

Structure (Both methods are applying the same semigroup).

The two techniques look unrelated and are two ways of computing $P_{t}f=\mathbb{E}[f(X_{t})]$ , the semigroup of chapter 3.

A lattice or a grid discretises the operator: replace $\mathcal{L}$ by a matrix and $P_{t}=e^{t\mathcal{L}}$ by repeated multiplication. The error is a discretisation error, it is deterministic, and it shrinks with the mesh — and the matrix has one row per grid point, which is where the dimensional cost comes from.

A simulation samples the measure instead: draw from the law of $X_{t}$ and average $f$ . Where that law is exactly samplable — a lognormal terminal price, a noncentral chi-square draw for a CIR-type variance — nothing is discretised at all, and the error is a sampling error that shrinks with the square root of the count. Most models and most payoffs need a path rather than one terminal draw, and then time is stepped, Euler or otherwise, which adds a second and deterministic error from that discretisation — the one the third discipline below, correct the discretisation, is about. Either way nothing costs $n^{d}$ : a time grid is refined along one axis, in time, whatever $d$ is, which is the asymmetry with the lattice that survives.

Written that way the trade is not a matter of taste. One method pays for accuracy in dimensions and the other in variance, and early exercise is hard for simulation for a structural reason: the exercise decision needs $P_{t}f$ at an intermediate state, which is exactly the object a lattice computes and a simulation does not.

19.3 Arbitrage-Free Becomes a Property of the Estimator

A closed form has a property that is easy to overlook because it is never stated: its prices are mutually consistent by construction. Black-Scholes cannot produce a negative butterfly, because it is an expectation under a measure, and an expectation of a convex function of a random variable is convex. There is nothing to check.

Once the expectation is estimated rather than evaluated, that guarantee has to be earned, and it is not automatic.

Calculation 19.3 (A butterfly priced two ways).

Take three strikes with $K_{2}$ midway between $K_{1}$ and $K_{3}$ , and price each call by simulation. The payoff is convex in the strike, so for any single path

\big{(}S-K_{1}\big{)}^{+}-2\big{(}S-K_{2}\big{)}^{+}+\big{(}S-K_{3}\big{)}^{+}% \;\geq\;0.

(19.2)

Price the three on a common set of paths and (19.2) is inherited term by term: the estimated butterfly is an average of non-negative numbers and cannot be negative. Ten thousand paths — far too few for an accurate price — give exactly zero violations across every width tried.²²2measured.

Price them on independent paths, which is what pricing each option separately amounts to, and nothing preserves it. Each price carries its own sampling error, the butterfly is a difference of nearly equal numbers, and at the same ten thousand paths over a quarter of narrow triples come out negative.³³3measured. The price set admits a static arbitrage: one could buy the butterfly for a negative amount.

Remark (Why more paths is the wrong answer).

The instinct is to spend more. It does not work: sampling error falls as $N^{-1/2}$ while a butterfly’s true value falls as the square of the strike spacing, so for any path budget there is a spacing at which the violations return.⁴⁴4measured at two budgets and two widths. Sixteen times the paths buys four times the resolution in strike, and a desk quoting a surface always wants more resolution than that.

Note also which direction the failure hides in. Widening the butterfly makes its value large against the noise and the violations disappear, so a check on widely spaced strikes passes while the surface a desk actually shows — adjacent strikes, tightly spaced — fails. A validation that samples coarsely will not find this.

Structure (Three disciplines in place of one guarantee).

Calculation 19.3 generalises.

Arbitrage-freeness in a solvable model is a structural property: it follows from the price being an expectation under a measure. In a numerical model it is an estimator property, and it survives only if three things are done deliberately.

-

Price from a model, not from prices. A surface interpolated or learned directly from quotes has no measure behind it and no reason to be convex in strike or monotone in maturity. A simulation of an arbitrage-free process does, whatever else is wrong with it.
-

Share the randomness. Common random numbers across strikes, maturities and scenarios is what carries pathwise relations like (19.2) through to the estimates. The same discipline is what makes a bumped Greek meaningful, since a delta from two independent simulations is mostly noise.
-

Correct the discretisation. A discrete scheme does not preserve the martingale property exactly, so numeraire-relative assets drift. Chapter 8 measures the consequence: a Gaussian forward curve model simulated with the wrong drift stops repricing its own initial curve, by five basis points at a year and half a per cent at ten. The repair is to force the known quantities to reprice, which is what a control variate or a martingale correction does.

None of the three is expensive. All three are easy to omit, and each omission produces prices that look like prices.

19.4 Early Exercise, Where the Difficulty Concentrates

The two methods divide the world neatly except at one point, where most of the practical difficulty lives.

Early exercise needs the continuation value: at each exercise date, the holder compares what the option is worth if kept against what it pays if stopped. A lattice knows the continuation value exactly, because it has already solved the layer after. A simulation does not, because it runs forwards and the future of a path is not known when the decision is made — and using it anyway is not merely inaccurate, it is a different and much more valuable contract, one exercised with foresight.

The standard resolution is Longstaff and Schwartz’s: estimate the continuation value by regressing realised discounted cashflows on functions of the current state, across paths, and exercise where intrinsic beats the estimate. It works, it is what essentially every desk uses for Bermudans, and it is biased.

Remark (Two biases, not one).

They are usually discussed as though there were one, and they have different causes, different signs, and different remedies.

Foresight bias, upwards. If the same paths are used to fit the regression and to value the option, the exercise rule has seen the outcomes it is deciding about. It is fitted to the noise as well as to the signal, and a rule fitted to noise flatters itself on the data it was fitted to. This is a finite sample effect and it decays as paths are added.

Policy bias, downwards. The estimated rule is not the optimal stopping rule — a quadratic in the spot cannot be — and any suboptimal rule undervalues the option. This has nothing to do with sample size. It is the basis’s fault, and adding paths does not touch it.

The usual implementation contains both. Which one dominates depends on how many paths there are, and that is exactly what makes the situation confusing.

Regress and exercise on the same paths
Rule fitted on one set, applied to another
The exact answer

Figure 19.1: Longstaff-Schwartz against an exact lattice answer, averaged over two hundred and forty independent runs at each path count. The upper curve reuses its paths and starts fifteen cents high, falling through the exact answer as the foresight it enjoyed is priced out. The lower curve fits the rule on one set of paths and applies it to another, which removes the foresight and leaves only the loss from an imperfect exercise rule — so it stays below, and flattens rather than converging, because more paths cannot repair a basis that is too poor. The distance between the curves at any path count is the foresight; the distance from the lower curve to zero is the policy.

Show the model behind this figure (2 functions)

longstaff_schwartzquant/src/numerics.rs

/// Price a Bermudan put by Longstaff-Schwartz.
///
/// The method every desk uses when the state is too large for a tree: simulate
/// forward, then step backwards estimating the continuation value by regressing
/// discounted future cashflows on functions of the current state, and exercise
/// where intrinsic beats the estimate.
///
/// The regression is on `1, S, S^2` over the in-the-money paths only, which is
/// the original recipe. Out-of-the-money paths carry no information about the
/// exercise boundary and including them spends the fit on the wrong region.
pub fn longstaff_schwartz(
    m: &Market,
    exercises: usize,
    paths: usize,
    mode: Lsm,
    seed: u64,
) -> f64 {
    let dt = m.expiry / exercises as f64;
    let discount = (-m.rate * dt).exp();

    let simulate = |seed: u64| -> Vec<Vec<f64>> {
        let mut rng = Rng::new(seed);
        let drift = (m.rate - 0.5 * m.vol * m.vol) * dt;
        let diffusion = m.vol * dt.sqrt();
        (0..paths)
            .map(|_| {
                let mut s = m.spot;
                (0..exercises)
                    .map(|_| {
                        s *= (drift + diffusion * rng.next_normal()).exp();
                        s
                    })
                    .collect()
            })
            .collect()
    };

    let fitting = simulate(seed);
    // The rule is fitted on `fitting` and, out of sample, applied to `pricing`.
    let pricing = match mode {
        Lsm::InSample => fitting.clone(),
        Lsm::OutOfSample => simulate(seed ^ 0x5DEE_CE66_D5B1_1F17),
    };

    let intrinsic = |s: f64| (m.strike - s).max(0.0);

    // Cashflow carried backwards along each path, on both sets.
    let mut fit_value: Vec<f64> = fitting.iter().map(|p| intrinsic(p[exercises - 1])).collect();
    let mut price_value: Vec<f64> = pricing.iter().map(|p| intrinsic(p[exercises - 1])).collect();

    for step in (0..exercises - 1).rev() {
        for v in fit_value.iter_mut() {
            *v *= discount;
        }
        for v in price_value.iter_mut() {
            *v *= discount;
        }

        // Fit the continuation value on the in-the-money paths of the fitting set.
        let mut rows: Vec<[f64; 3]> = Vec::new();
        let mut targets: Vec<f64> = Vec::new();
        for (path, &carried) in fitting.iter().zip(&fit_value) {
            let s = path[step];
            if intrinsic(s) > 0.0 {
                rows.push([1.0, s, s * s]);
                targets.push(carried);
            }
        }
        let beta = match least_squares(&rows, &targets) {
            Some(b) => b,
            // Nothing in the money at this date: nobody exercises, carry on.
            None => continue,
        };
        let continuation = |s: f64| beta[0] + beta[1] * s + beta[2] * s * s;

        // Apply the rule. On the fitting set this is the in-sample estimator; on
        // a fresh set it is the out-of-sample one.
        let apply = |paths: &Vec<Vec<f64>>, values: &mut Vec<f64>| {
            for (path, v) in paths.iter().zip(values.iter_mut()) {
                let s = path[step];
                let exercise = intrinsic(s);
                if exercise > 0.0 && exercise > continuation(s) {
                    *v = exercise;
                }
            }
        };
        apply(&fitting, &mut fit_value);
        if mode == Lsm::OutOfSample {
            apply(&pricing, &mut price_value);
        }
    }

    let values = match mode {
        Lsm::InSample => &fit_value,
        Lsm::OutOfSample => &price_value,
    };
    discount * values.iter().sum::<f64>() / paths as f64
}

binomial_bermudanquant/src/numerics.rs

/// A Bermudan put on a Cox-Ross-Rubinstein tree.
///
/// Backward induction handles early exercise exactly: at each node the value is
/// the larger of exercising and continuing, and continuing is known because the
/// step after has already been solved. There is no estimation anywhere in it,
/// which is what makes this the reference.
///
/// `exercises` is the number of equally spaced exercise dates, the last at
/// expiry. The step count is rounded up so every exercise date lands on a step.
pub fn binomial_bermudan(m: &Market, exercises: usize, steps_per_exercise: usize) -> f64 {
    let steps = exercises * steps_per_exercise;
    let dt = m.expiry / steps as f64;
    let up = (m.vol * dt.sqrt()).exp();
    let down = 1.0 / up;
    let discount = (-m.rate * dt).exp();
    let p = ((m.rate * dt).exp() - down) / (up - down);

    // Terminal layer.
    let mut value: Vec<f64> = (0..=steps)
        .map(|j| {
            let s = m.spot * up.powi(j as i32) * down.powi((steps - j) as i32);
            (m.strike - s).max(0.0)
        })
        .collect();

    for step in (0..steps).rev() {
        let exercisable = (step + 1) % steps_per_exercise == 0 && step + 1 != steps;
        for j in 0..=step {
            let continuation = discount * (p * value[j + 1] + (1.0 - p) * value[j]);
            value[j] = if exercisable {
                let s = m.spot * up.powi(j as i32) * down.powi((step - j) as i32);
                continuation.max((m.strike - s).max(0.0))
            } else {
                continuation
            };
        }
        value.truncate(step + 1);
    }
    value[0]
}

Example 19.1 (The numbers).

A one year Bermudan put, ten exercise dates, struck at the money, at a $25\%$ volatility. The lattice answer is $7.915$ against a European value of $7.459$ , so early exercise is worth about forty-six cents. Averaged over two hundred and forty runs:

Paths	Same paths	Fresh paths
$500$	$+0.156$	$-0.096$
$2{,}000$	$+0.058$	$-0.046$
$8{,}000$	$+0.004$	$-0.031$
$16{,}000$	$-0.008$	$-0.024$

Read the two columns against each other. The left one falls by a factor of twenty and changes sign; the right one falls by a factor of four and is levelling off. That is the two biases behaving as their causes predict.

Remark (One run cannot see its own bias).

The practical warning, and the reason the table above needed two hundred and forty runs per entry rather than one.

At a thousand paths the bias is about ten cents and the standard deviation of a single estimate is several times that. So a single Longstaff-Schwartz run compared against a lattice tells you nothing about which way the method leans — the answer will be above or below according to the seed, and both happen. A desk that validates its Bermudan pricer by running it once and eyeballing the difference has not validated anything, and the test that pins this exists because it is easy to believe otherwise.

Remark (The harder problem is choosing what to regress on).

The biases above are measurable, which makes them the easy part. The difficulty that actually decides whether a Bermudan price is any good is upstream of them: what should the continuation value be regressed on?

The method needs variables in which the continuation value is a function of the current state — Markovian in them — and it needs a basis in which that function is close to linear. For a Bermudan put on one asset both are easy: the state is the spot and a quadratic is adequate, which is why the example above behaves. For anything real neither is obvious.

A Bermudan swaption in the market model of chapter 13 has twenty forward rates as its state. One cannot regress on twenty variables with any hope of conditioning, so the modeller picks summary variables — the underlying swap rate, perhaps a slope, perhaps the first two principal components — and hopes the continuation value depends on the rest only weakly. A callable range accrual depends on the whole path of accruals so far, and the natural summary, the accrual accumulated to date, is an extra state variable that must be carried and regressed on. A callable with a barrier depends on whether the barrier has been touched, which is not a function of the current level at all.

And the error this causes is invisible from inside the run. If a relevant state variable has been left out, the regression still fits, the fit statistics still look reasonable, and the price comes out low by an amount nothing in the calculation reveals. It is the policy bias of the previous section with a cause that adding paths cannot touch and adding basis functions cannot touch either, because the missing information is not in the variables being regressed on.

The only real defences are a dual upper bound, which brackets whatever the policy lost, and pricing the same trade with a genuinely different state — for instance on a lattice in a low-factor model — and treating the gap as the model risk it is. Which is chapter 20’s discipline again, arriving from a numerical direction rather than a statistical one.

Remark (Neither is an upper bound).

A tempting conclusion from the figure is that the two curves bracket the answer. They do here, and it is not a bracket one can rely on: the upper curve’s position depends on the path count, and at sixteen thousand paths it has already crossed below.

A genuine upper bound needs a different idea.

Fix the notation for what follows: exercise dates $t_{1}<\dots<t_{K}$ , state $X_{t_{k}}$ , discount factor $D_{k}$ to $t_{k}$ , intrinsic payoff $h$ , and

V_{0}\;=\;\sup_{\tau}\,\mathbb{E}\big{[}D_{\tau}\,h(X_{\tau})\big{]},

(19.3)

the supremum over stopping times $\tau$ valued in $\{t_{1},\dots,t_{K}\}$ . Longstaff-Schwartz attacks (19.3) from below: any implementable rule is one particular $\tau$ , so its price is one term of the supremum and a lower bound. The dual formulation attacks it from the other side.

Theorem 19.4 (Weak duality: any martingale bounds it).

For any martingale $M$ adapted to the same filtration with $M_{0}=0$ ,

V_{0}\;\leq\;\mathbb{E}\Big{[}\max_{1\leq k\leq K}\big{(}D_{k}\,h(X_{t_{k}})-M% _{k}\big{)}\Big{]}.

(19.4)

Proof.

Optional stopping gives $\mathbb{E}[M_{\tau}]=0$ for every stopping time $\tau$ valued in the finite set $\{t_{1},\dots,t_{K}\}$ , so

\mathbb{E}\big{[}D_{\tau}h(X_{\tau})\big{]}\;=\;\mathbb{E}\big{[}D_{\tau}h(X_{% \tau})-M_{\tau}\big{]}\;\leq\;\mathbb{E}\Big{[}\max_{k}\big{(}D_{k}h(X_{t_{k}}% )-M_{k}\big{)}\Big{]},

the inequality because $D_{\tau}h(X_{\tau})-M_{\tau}$ is one of the terms maximised over, whichever date $\tau$ happens to land on. The right side does not depend on $\tau$ , so taking the supremum over $\tau$ on the left proves (19.4) for that $M$ — and the argument used nothing about $M$ beyond $M_{0}=0$ , so it holds for every martingale at once. ∎

Theorem 19.5 (Strong duality: the right martingale is exact).

Let $Y_{k}=D_{k}V_{k}$ be the discounted value process, $V_{k}$ the true continuation-or-exercise value at $t_{k}$ — the Snell envelope of $D_{\cdot}h(X_{\cdot})$ , and $V_{0}$ its value at the start. Then $Y$ is a supermartingale, $Y_{k-1}\geq\mathbb{E}[Y_{k}\mid\mathcal{F}_{k-1}]$ , because continuing is by definition worth at least what any one choice, in particular waiting one more step and then following the optimal rule, would give. Its Doob decomposition $Y_{k}=Y_{0}+M^{*}_{k}-A_{k}$ , with $M^{*}$ a martingale and $A$ increasing, $A_{0}=0$ , $M^{*}_{0}=0$ , is

M^{*}_{k}-M^{*}_{k-1}\;=\;Y_{k}-\mathbb{E}[Y_{k}\mid\mathcal{F}_{k-1}],\qquad A% _{k}-A_{k-1}\;=\;Y_{k-1}-\mathbb{E}[Y_{k}\mid\mathcal{F}_{k-1}]\;\geq\;0.

(19.5)

Equality holds in (19.4) for $M=M^{*}$ .

Proof.

$V_{k}$ dominates the intrinsic payoff pointwise, $Y_{k}\geq D_{k}h(X_{t_{k}})$ , since exercising is one of the choices continuation is worth at least as much as. So for every $k$ ,

D_{k}h(X_{t_{k}})-M^{*}_{k}\;\leq\;Y_{k}-M^{*}_{k}\;=\;Y_{0}-A_{k}\;\leq\;Y_{0% }\;=\;V_{0},

using (19.5) for the middle equality and $A_{k}\geq 0$ for the last inequality. This holds pathwise, so the maximum over $k$ is at most $V_{0}$ , and taking expectations gives $\mathbb{E}[\max_{k}(\cdots)]\leq V_{0}$ . Theorem 19.4 gives the reverse inequality for this $M^{*}$ in particular, so the two meet. ∎

Remark (What the two theorems divide between them).

Theorem 19.4 is cheap and universal: write down any martingale and get a valid bound, no matter how bad. Theorem 19.5 says the bound can be made exact, but the martingale that does it is built from $V$ , the very function the whole chapter is about not having. Practice therefore substitutes an approximation for $V$ in (19.5) and inherits both theorems separately: the bound stays valid by theorem 19.4, whatever the approximation, and stops being exact by theorem 19.5, to a degree that depends on how good the approximation is. That is the sense in which the passage’s “rough” is doing real work: rough buys validity for free and tightness not at all, and the two have to be assessed separately.

Calculation 19.6 (Andersen and Broadie’s construction).

Take $\hat{V}_{k}(x)=\max\big{(}h(x),\,\hat{C}_{k}(x)\big{)}$ for $k<K$ and $\hat{V}_{K}(x)=h(x)$ , with $\hat{C}_{k}$ the Longstaff-Schwartz continuation-value fit at $t_{k}$ — the same quadratic already sitting in the regression, nothing further done to it. Equation (19.5) applied to $\hat{Y}_{k}=D_{k}\hat{V}_{k}(X_{t_{k}})$ in place of $Y_{k}$ defines a martingale $\hat{M}$ by the same formula, and theorem 19.4 makes it valid whether or not $\hat{V}$ is any good.

The one thing (19.5) needs that is not already in hand is the conditional expectation $\mathbb{E}[\hat{Y}_{k}\mid\mathcal{F}_{k-1}]$ , and $\hat{V}$ has no closed form to take it in. Andersen and Broadie’s move is to estimate it by simulation: from each outer path’s state at $t_{k-1}$ , draw a handful of inner one-step continuations to $t_{k}$ , average $\hat{Y}_{k}$ over them, and use that average in place of the conditional mean. The inner draws are independent of the outer path’s own step to $t_{k}$ , which is what keeps $\mathbb{E}[\Delta\hat{M}_{k}]=0$ exactly, whatever the inner sample size — more inner paths reduce the variance of the estimated bound, not a bias in it.⁵⁵5the construction, including the one detail that is not in the two-paragraph sketch above: $\hat{C}_{k}$ was fitted only on paths in the money, exactly as longstaff_schwartz restricts its own regression, and evaluating it out of the money — where the inner sampling and every date after the first go wandering regardless — extrapolates a quadratic fitted on one side of the strike to the other, which came out wrong by tens of dollars before it was floored at the payoff itself. The primal never notices this, since its exercise test starts from “intrinsic $>0$ ” before it ever consults the continuation estimate; the dual evaluates $\hat{V}$ everywhere, so it notices immediately.

Example 19.2 (The bracket, on the same put).

The Bermudan put of this section’s earlier table, priced at the money for one year on ten exercise dates: the lattice value is $7.915$ . The Longstaff-Schwartz rule, fitted on one set of paths and priced out of sample on sixteen thousand fresh ones, gives a lower bound of $7.886$ . The martingale with no information in it at all, $M\equiv 0$ , gives an upper bound of $12.370$ — valid by theorem 19.4, and useless, since it is simply the value of stopping with perfect foresight of the whole path. The same quadratic fit that produces the lower bound, run through calculation 19.6, gives an upper bound of about $8.2$ : an order of magnitude closer than the martingale with nothing in it, from a martingale built out of a continuation-value estimate nobody trusted enough to call exact.⁶⁶6the naive bound, and that it is loose; the fitted one, and the comparison; lower and upper measured together.

$7.886$ and $8.2$ are both computable without ever knowing the answer, and $7.915$ sits inside them. That is what the passage means by converting “our Bermudan number is probably about right” into an interval: not a tighter point estimate, but a certificate that the true value cannot be outside a range, built from the same regression the point estimate already required.

19.5 What Lifting the Constraint Permits

Now the constructive half. If a model no longer needs a formula, what can it be?

Models with more parameters than quotes

Neural stochastic differential equations, market generators, and non-parametric local-stochastic volatility all abandon the idea that a model is a handful of interpretable numbers. The dynamics are specified by something with thousands or millions of parameters, fitted to whatever data is available, and priced by simulation because nothing else is possible. The first and third keep the form of a diffusion and learn its coefficients; a market generator gives that up too. It is typically a network trained — adversarially, or by some other distributional-matching objective — to output entire simulated paths directly from noise, fitted to reproduce a historical sample rather than to solve any equation at all.

Where the parameters are put matters more than how many there are, and whether a learned model is arbitrage-free depends entirely on it. A network fitted directly to a price surface, or a market generator fitted to reproduce simulated paths, has no structural guarantee: chapter 4 established that a price system without a martingale measure admits a money pump, and nothing in a training loss enforces one — a constraint can be added as a penalty, but a penalty is a preference and not a guarantee.

A network placed inside the coefficients of a stochastic differential equation is in a completely different position. Chapter 2 established that a continuous arbitrage-free price has no choice but to be an Itô diffusion, and chapter 4 that its discounted value must be a local martingale under the pricing measure — which fixes the drift and leaves only the diffusion coefficient free. So writing

\frac{dS_{t}}{S_{t}}=r\,dt+\sigma_{\theta}(t,S_{t},v_{t})\,dW_{t}

(19.6)

with $\sigma_{\theta}$ a neural network produces an arbitrage-free model for every value of $\theta$ , the constraint carried by the form of the equation rather than by the loss. Nothing has been given up in flexibility either: by chapter 2 the equation is not a restriction on the model class, it is the model class. The remaining requirements are mild — $\sigma_{\theta}$ positive and regular enough for a solution to exist — and the remaining problem is not this one: chapter 21 works out why a finite set of quotes still does not determine a function, however it is parametrised. It also explains why these methods are simulation methods necessarily: a learned coefficient admits no closed form by construction, so the model is defined by the equation and priced by solving it.

The calibration problem then changes shape rather than disappearing. What is needed is not a closed form but a fast approximation of the map from parameters to prices, which can be learned once, offline, and then evaluated in microseconds — so the model is free to be slow, provided its price map is smooth enough to be learned. Chapter 21 discusses that technique under deep calibration; here the point is what it unlocks, which is the freedom to choose dynamics on their merits.

Learning the exercise rule instead of the continuation value

The regression above estimates a continuation value and derives a policy from it. Reinforcement learning inverts that: the policy is the object being optimised, and the value is whatever the policy achieves.

This is a genuine improvement in one respect — a policy can be represented by something far richer than a quadratic, so the policy bias above can be made small — and it changes nothing structural. A learned policy is still a policy, so the estimate is still biased low, and it still needs a dual bound to be turned into an interval. The bias moves; it does not go away.

Optimising the hedge instead of the price

The methods above still price first and hedge afterwards. Deep hedging drops that order, and it is the one item on this list that changes what is being computed rather than how.

Fix a risk measure $\rho$ — expected shortfall, from chapter 24, is the usual choice and the one its axioms recommend. Parametrise the hedging strategy directly as a function of whatever is observable, hand it a simulated market, and choose its parameters to minimise $\rho$ of the terminal profit and loss. The price falls out as the cash that makes the optimised risk acceptable, which is an indifference price rather than a replication cost.

What that buys is everything the replication argument had to assume away. Transaction costs, position limits, discrete rebalancing and an incomplete market are not obstructions to be handled afterwards but terms in the objective, so the strategy is optimised against the market it will actually trade in. Chapter 5 measured what discrete rebalancing alone leaves behind — a residual whose spread falls only as the square root of the rebalancing count — and the delta it was rebalancing was optimal for a market with none of these features.

Two things it does not do, and both matter more than the machinery.

It does not produce a no-arbitrage price, and cannot. Replication is what pinned the Black-Scholes price down uniquely. Take away frictionless, continuous trading — with transaction costs, position limits or only finitely many rebalancing dates — and some payoffs are no longer attainable at zero residual risk. Chapter 6’s structure The middle row and its theorem work out what that buys: no unique martingale measure, and so no single arbitrage-free price, only an interval bounded by the cost of super-replicating the payoff above and sub-replicating it below. The answer depends on the risk measure and on how much risk is being tolerated, so two desks with different objectives get different numbers and neither is wrong. That is not a defect of the method; it is what an incomplete market means, and that theorem said as much long before anyone trained a network. What the method supplies is a principled way to pick a point in the interval the theorem leaves open.

And it inherits the market it was trained on. A strategy optimised against simulated paths learns the measure that generated them, so every defect of the generator becomes a defect of the hedge — which is why the market generators of the first subsection are not a separate topic from this one. The calibration problem has been moved rather than removed, and it has been moved somewhere harder to inspect: a mis-specified parameter is visible, and a mis-specified simulator is a distribution nobody has plotted.

Remark (What a market generator is free to learn, and what that has to do with statistical arbitrage).

A market generator is fitted to history under the physical measure, with no no-arbitrage constraint built into its form the way a neural SDE’s drift has one. So it is free to reproduce whatever predictable structure the historical sample contains — and real markets do contain some, which is not the contradiction it looks like. Chapter 4’s theorem requires only that an equivalent martingale measure exist; it says nothing about the drift under the physical measure, which is free to carry a risk premium, or — chapter 22’s term — a statistical arbitrage: a position with a genuine expected return that is not an arbitrage because it still holds a risk the model does not span. A generator that reproduces history faithfully reproduces that residual along with everything else.

What it cannot supply is chapter 22’s other requirement: a structural reason. Finding that a generated path’s conditional mean is not flat is a statistical fact; identifying why — a regulatory flow, a financing constraint, a named mechanism — is not something a distributional match can do for you. That is the sense in which a market generator could point at a candidate statistical arbitrage without ever validating one, and it is a narrower and riskier use than the deep hedging above, which asks only that the generator’s paths look like the market a hedge will actually trade in, not that any pattern found in them survives beyond the sample that produced it.

Solving high-dimensional equations directly

The dimensional wall is where the newer numerical methods have most clearly earned their place, and the leading one says something about pricing that the partial differential equation hides.

Definition 19.7 (The pricing problem as a backward equation).

A European claim’s value $Y_{t}$ and its hedge satisfy the backward stochastic differential equation

Y_{t}=g(X_{T})+\int_{t}^{T}f\big{(}s,X_{s},Y_{s},Z_{s}\big{)}\,ds\;-\;\int_{t}% ^{T}Z_{s}\cdot dW_{s},

(19.7)

where $g$ is the payoff, $f$ carries the discounting and any funding or default term, and $Z_{t}$ is whatever integrand makes the equation hold.

Two features of (19.7) deserve emphasis. It runs backwards — the terminal condition is given and the initial value is the unknown — which is why it is the natural form of a pricing problem. And $Z$ is not an auxiliary variable: by comparison with chapter 4’s replication argument, $Z_{t}=\sigma^{\top}\nabla_{x}Y_{t}$ is the hedge. So (19.7) states the price and the hedging strategy as one object, which the pricing equation does only implicitly.

Remark (What a deep solver does with it).

The construction of E, Han and Jentzen turns (19.7) into a fitting problem, and does it by reading the equation forwards.

Parametrise the unknown initial value $Y_{0}$ as a number and the integrand $Z_{t}=\zeta_{\theta}(t,X_{t})$ as a network. Then simulate $X$ forward and propagate $Y$ alongside it using (19.7) as a recursion,

Y_{t+\Delta}=Y_{t}-f\big{(}t,X_{t},Y_{t},Z_{t}\big{)}\Delta+Z_{t}\cdot\Delta W% _{t},

which requires no knowledge of the answer. At the horizon the equation demands $Y_{T}=g(X_{T})$ , and in general the propagated $Y_{T}$ will not equal the payoff. So minimise

\mathbb{E}\Big{[}\big{(}Y_{T}-g(X_{T})\big{)}^{2}\Big{]}

(19.8)

over $Y_{0}$ and $\theta$ . The loss is the terminal condition’s failure, the fitted $Y_{0}$ is the price, and the fitted network is the hedge.

What has been bought is that nothing is discretised in the state. The cost is $O(\text{paths}\times\text{steps})$ regardless of dimension, which is why this works at fifty factors and a grid does not. What has been given up is the subject of the next section.

The honest test of such a solution is the same as for anything else in these notes: report the residual of the equation at points the fit never saw. A network that satisfies its equation only where it was trained has learned the training set.

States that are not vectors

Some problems have a state that is a graph rather than a list of numbers — a portfolio of counterparties with exposures between them, a limit order book, a network of related instruments. Graph neural networks are the natural representation, and this is the least mature of the strands here: the applications are real but the track record is short, and it is worth treating claims in this area with more suspicion than the rest.

Of the three, the order book is the furthest along. A market maker’s quote depends on the whole depth of the book, not on the best bid and offer alone, and the book’s natural representation is a graph: a node per price level, an edge to its neighbours, and a message-passing step that lets a shock several levels away — a large resting order cancelled, a burst of activity on one side — reach the level actually being quoted before it arrives there through price alone. What makes this the more advanced case is not the architecture, which is standard, but the feedback loop: a quote is filled or it is not, within milliseconds, so the model is trained against an outcome the market supplies immediately and constantly, unlike a counterparty network or a relative-value graph, where the analogous signal — a default, a reversion — arrives rarely and late. Chapter 23 is where a quote actually gets set from a state like this.

19.6 Why This Matters for Trading and Not Only for Pricing

A natural objection to everything above is that a model which cannot be calibrated in milliseconds cannot be used. That is true for a market making desk quoting a screen, and it is not true generally.

Chapter 22’s trades do not need a model that prices in microseconds. They need a model whose view of the future is better than the market’s, because the entire proposition is that the market’s price implies something implausible and the position collects when it stops doing so. For that, being right matters and being fast does not.

Remark (The division of labour).

This suggests a use of models that the earlier chapters have not needed. A desk can reasonably run two: a tractable one for marking, quoting and hedging, where consistency with the market and speed are everything, and a slower and more honest one for deciding what to hold, where realism is everything.

They will disagree, and the disagreement is not a bug to be reconciled. It is the trade. Chapter 20’s discipline applies directly — price it in two models that disagree about the thing the payoff is sensitive to — with the difference that here the disagreement is being sought rather than reserved against.

19.7 What Computation Does Not Fix

Two limits, both of which the earlier chapters have already established and neither of which more compute touches.

The first is identifiability. Chapter 20 measured a SABR calibration in which the quotes fixed the level of the smile to one percent and left the correlation free to move across most of its range — with the model exactly right and the data noiseless. That flatness is a property of the instruments quoted, not of the fitting procedure, and a model with a million parameters fitted to forty quotes is that problem in its extreme form. A richer model does not extract information the market did not supply; it distributes the same information over more unknowns.

That is the complaint against fitting a single day’s quotes specifically, and chapter 21’s Calibrating to Prices and to History at Once is the escape a richer model can take that a small one cannot use as well: fit to the smile and to the price history at once, and by Girsanov the diffusion coefficient is shared between the two measures, so the history is a second, genuinely independent source of information about exactly the parameters a cross-section leaves flat. More parameters make room to use it — there is more diffusion structure to be pinned down and more history to pin it with. It is not a free upgrade: what the history identifies well is the diffusion coefficient and not the drift, so a slow parameter like a mean reversion still needs a long history rather than a rich model, and where the two sources disagree — implied against realised volatility routinely do — that disagreement is information a joint fit has to model rather than average away.

The second is that every estimate of an exercise policy is biased, by the argument of this chapter, and no amount of computation makes a policy optimal without knowing the optimal policy. Compute changes the size of the bias and the tightness of the bound. It does not remove either.

The third is the one this chapter’s argument turns on, and it is not about accuracy but about knowing the accuracy.

Structure (Bounded and unbounded errors).

A grid’s error can be bounded before it is run. A finite difference scheme of order $p$ has error $O(h^{p})$ with a constant depending on derivatives of the solution, so halving the mesh and watching the answer move by a factor of $2^{p}$ is a check that the bound is operative — and Richardson extrapolation turns two runs into an estimate of the error itself. The same is true of a Monte Carlo: the central limit theorem supplies a standard error from the sample, and it is a genuine confidence statement about the number produced.

A network fitted to (19.8) offers neither. The loss is a residual, and a small residual does not bound the error in the solution: the map from residual to error involves a stability constant for the equation that is not available in the high-dimensional problems the method exists to solve. Refining does not help, because there is no mesh to refine — one trains longer, or with more capacity, and the answer moves by an amount with no theory attached.

So the asymmetry is not that one method is more accurate. Over four dimensions the network is more accurate, sometimes by a wide margin. The asymmetry is that one method’s error is a quantity and the other’s is a hope, and that difference lands squarely on chapter 24: a valuation uncertainty has to be reserved against, and a reserve requires a number. An unbounded error cannot be reserved for; it can only be provisioned against by judgement, which is the same as saying it is carried as model risk.

That is the residual value of solvability. A solvable model is not more realistic. It is not faster in any way that matters now. What it has is that its answer comes with an error one can write down, and a desk that has to reserve against being wrong finds that this is worth something. The trade is realism for auditability, and stating it that way makes it a decision rather than a habit.

Remark (The rule that survives).

The methods in this chapter will date faster than anything else in these notes. What will not is the habit of asking, of any number produced by a numerical method, three questions: what is its standard error, which way does it lean, and what would it look like if the method were wrong.

References

-

Longstaff, F. A., & Schwartz, E. S. (2001). Valuing American options by simulation: a simple least-squares approach. Review of Financial Studies, 14(1), 113–147.
-

Glasserman, P. (2004). Monte Carlo Methods in Financial Engineering. Springer.
-

Andersen, L., & Broadie, M. (2004). Primal-dual simulation algorithm for pricing multidimensional American options. Management Science, 50(9), 1222–1234.
-

Rogers, L. C. G. (2002). Monte Carlo valuation of American options. Mathematical Finance, 12(3), 271–286.
-

Tavella, D., & Randall, C. (2000). Pricing Financial Instruments: The Finite Difference Method. Wiley.
-

Han, J., Jentzen, A., & E, W. (2018). Solving high-dimensional partial differential equations using deep learning. PNAS, 115(34), 8505–8510.