How Andersen–Broadie Primal–Dual Algorithms Bound American-Option Values: Exercise Policies, Martingale Upper Bounds, Nested Simulation and Gap Diagnostics

Reader question: Monte Carlo can simulate complex option payoffs, but an American or Bermudan option also lets the holder choose when to exercise. How can a simulation algorithm tell whether an approximate exercise rule is close to the true optimal value?

The Andersen–Broadie primal–dual method answers with two numbers rather than one. A feasible exercise rule produces a lower bound. A carefully constructed martingale produces a dual upper bound. When the two bounds are close relative to their statistical error, the remaining value of better exercise timing is tightly constrained.

This article owns the simulation-based lower/upper bounding problem for American and Bermudan optimal stopping. It does not own the Longstaff–Schwartz regression algorithm itself, binomial trees, finite-difference free-boundary solvers or a specific underlying stochastic model.

This is public mathematical and computational education. It is not financial advice, a recommendation to trade options, or a claim that a narrow numerical bound eliminates model risk.

1. The American-option problem is an optimal-stopping problem

Consider exercise dates:

0 = t₀ < t₁ < … < t_M = T.

Let Z_j be the discounted payoff available if the option is exercised at t_j.

For a Bermudan option, exercise is allowed only on these dates. Its value is:

V₀ = sup_τ E[Z_τ],

where τ ranges over stopping times that use only information available up to the chosen exercise date.

The phrase stopping time is essential. A valid exercise rule cannot look into the future and then pretend it made the decision earlier.

2. Why ordinary Monte Carlo is not enough

For a European option, simulate a path, evaluate the payoff at maturity, average across paths.

For an American/Bermudan option, each path presents repeated choices:

exercise now, or continue and retain the option?

The continuation value is a conditional expectation of future optimal cash flows. It is not directly observed on one simulated path.

This is why early-exercise pricing becomes a dynamic-programming or optimal-stopping problem rather than a simple expectation.

3. The primal idea: any admissible exercise policy gives a lower bound

Suppose we construct some exercise policy τ̂—even an imperfect one.

Because the true option value is the supremum over all admissible policies:

E[Z_τ̂] ≤ V₀.

This is the primal lower-bound principle.

It is powerful because the policy does not have to be optimal. It only has to be admissible: at each date, it must use information available at that date.

4. Longstaff–Schwartz is one way to build the policy

A common approach simulates training paths and regresses realised future discounted cash flows on basis functions of the current state.

The estimated continuation value Ĉ_j(X_j) is compared with immediate exercise payoff Z_j.

A simple exercise policy is:

exercise if Z_j ≥ Ĉ_j(X_j).

See Longstaff–Schwartz least-squares Monte Carlo algorithms for the regression mechanics.

Andersen–Broadie begins after such a policy exists. Its distinctive job is to ask: how far could the true value still be above our lower-bound policy value?

5. Avoid look-ahead contamination in the lower bound

If a regression policy is trained and evaluated on the same paths, future information can leak indirectly through fitted continuation values and pathwise selection. The resulting number may no longer behave like a clean out-of-sample lower bound.

A robust implementation separates:

• policy-training paths;
• independent policy-evaluation paths.

On each evaluation path, the policy acts exactly as it would in production: using only current/past state information and fixed model coefficients learned earlier.

6. The dual idea: penalise perfect foresight with a martingale

If we were allowed to look at the entire future path before choosing the exercise date, we could take:

max_j Z_j.

That is generally too valuable because it uses impossible foresight.

Optimal-stopping duality says this foresight can be penalised with a martingale M satisfying M₀ = 0.

For a broad class of Bermudan problems:

V₀ = inf_M E[max_j(Z_j − M_j)].

Therefore, for any admissible martingale M:

V₀ ≤ E[max_j(Z_j − M_j)].

This is the dual upper-bound principle developed by Rogers and independently by Haugh–Kogan, then made into a practical primal–dual simulation algorithm by Andersen and Broadie.

7. Why a martingale is the right penalty

A martingale has zero expected future increment conditional on current information.

Subtracting it does not systematically change expected value under an admissible stopping time, but it can remove the artificial advantage of choosing an exercise date after seeing the entire future.

The optimal dual martingale is related to the martingale part of the Snell envelope—the dynamic-programming value process of the optimal-stopping problem.

If we knew that exact martingale, the dual upper bound would equal the true price.

8. The Snell-envelope recursion

Define the option value at the final exercise date:

Y_M = Z_M.

Working backward:

Y_j = max(Z_j, E[Y_j+1|F_j]).

This value process is the Snell envelope.

The continuation term:

C_j = E[Y_j+1|F_j]

is exactly the quantity that is hard to compute in high dimension.

The dual martingale can be built from conditional-expectation increments associated with this process. Andersen–Broadie approximates these increments using simulation around an approximate exercise policy.

9. A conceptual primal–dual workflow

1. Calibrate the underlying stochastic model.
2. Simulate a training set of paths.
3. Build an approximate continuation/exercise policy.
4. Freeze the policy.
5. Simulate independent outer paths.
6. Apply the policy to outer paths to estimate a lower bound.
7. At relevant outer path states, run nested inner simulations to estimate conditional expectations.
8. Use those conditional estimates to construct approximate martingale increments.
9. Calculate the pathwise dual maximum payoff minus martingale.
10. Average dual payoffs to estimate an upper bound.
11. Report Monte Carlo uncertainty for both estimates and the primal–dual gap.

10. Why nested simulation appears

To build the approximate Doob martingale, the algorithm needs conditional expectations at states visited by the outer simulation.

If no analytical formula is available, it can start many inner paths from an outer-path state and average their future policy cash flows.

That means the algorithm has two simulation levels:

• outer paths generate candidate option histories;
• inner paths estimate conditional continuation information needed for the dual martingale.

This nested structure is the main computational cost of the original Andersen–Broadie implementation.

11. Lower bound and upper bound answer different questions

The lower bound asks:

What value can this actual feasible exercise rule achieve?

The upper bound asks:

How much could an optimal rule possibly be worth, given this dual penalty?

If the lower bound is 10.12 and the upper bound is 10.18, the true model value lies between them, subject to statistical confidence treatment.

If the bounds are 8.5 and 13.7, the algorithm has not learned enough to make a tight valuation claim.

12. The primal–dual gap is a diagnostic, not merely an error bar

Define the estimated gap:

Gap = Upper − Lower.

A large gap can indicate:

• a poor exercise policy;
• a poor approximate martingale;
• too few inner simulations;
• unstable continuation regressions;
• a high-dimensional state representation missing key variables;
• large Monte Carlo variance.

The gap therefore tells us where to investigate. It is not only a reporting statistic.

13. Inputs and outputs

Inputs can include:

• exercise dates;
• discounting convention;
• payoff function;
• state-transition model;
• correlation/volatility parameters;
• approximate exercise policy;
• basis functions or value approximator;
• outer path count;
• inner path count;
• random-number seeds;
• variance-reduction settings;
• confidence level.

Outputs can include:

• primal lower-bound estimate;
• dual upper-bound estimate;
• standard errors;
• confidence intervals;
• primal–dual gap;
• exercise frequencies by date/state;
• nested-simulation variance;
• martingale diagnostics;
• benchmark differences.

14. Statistical uncertainty must be separated from approximation gap

Suppose:

Lower = 10.10 ± 0.03

and:

Upper = 10.16 ± 0.04.

The raw 0.06 gap is not the whole uncertainty picture. Each estimator has Monte Carlo sampling error.

A robust report preserves:

• the point lower bound;
• the point upper bound;
• their standard errors;
• a statistically justified interval construction;
• the numerical approximation assumptions used to claim bound validity.

15. Evidence polarity

Evidence for confidence includes:

• lower and upper bounds are close;
• both have small Monte Carlo error relative to the gap;
• the lower-bound policy is evaluated out-of-sample;
• dual martingale increments pass conditional-mean diagnostics;
• bounds tighten as policy quality improves;
• results agree with tree/PDE benchmarks in low-dimensional test cases;
• bounds are stable as outer/inner path counts increase;
• variance reduction changes precision but not the central conclusion.

Evidence against confidence includes:

• a wide primal–dual gap;
• upper bound falling below a credible lower bound beyond statistical error;
• lower bound changing materially when evaluation paths are made independent;
• large martingale residuals;
• strong dependence on basis functions or random seeds;
• nested-simulation noise dominating the upper bound;
• failure against a known binomial/PDE benchmark.

16. Counterexample: an in-sample “lower bound” that is not cleanly lower

A regression policy is estimated from a set of simulated paths. If those same paths are then used to choose and evaluate exercise in a way that allows fitted future information to influence decisions, the estimate can contain look-ahead bias.

Falsifier: freeze the policy and evaluate it on independent paths. A material downward move reveals that the earlier estimate was contaminated by in-sample optimism.

17. Counterexample: a terrible policy still gives a valid lower bound

Consider a Bermudan put with valuable early exercise, but the chosen policy always waits to maturity.

That policy is admissible. Its European-style value is therefore a legitimate lower bound.

But the gap to the dual upper bound may be large.

This illustrates an important logic point: valid does not mean useful. A lower bound can be mathematically correct yet too loose for valuation.

18. Counterexample: a poor martingale creates a useless upper bound

If M = 0, the dual expression becomes:

E[max_j Z_j],

the value of exercising with perfect foresight. This is an upper bound but can be extremely loose.

Falsifier: improve the continuation approximation. A competent dual construction should reduce the upper bound substantially toward the lower bound.

19. Counterexample: nested simulation is too noisy

Suppose only two inner paths are used to estimate each conditional continuation value. The approximate martingale increments can be extremely noisy.

The resulting upper estimator may have high variance and a wide confidence interval even if the policy is good.

Falsifier: increase inner simulation counts or use variance reduction. If the upper bound moves or its error collapses materially, inner-path noise was a weak link.

20. Counterexample: state variables are missing

A Bermudan swaption’s exercise decision may depend on multiple points of the yield curve. A policy that conditions only on one swap rate may omit curve-shape information.

The lower bound may then be poor and the dual gap wide.

Falsifier: enrich the state representation or basis functions. Systematic tightening of the bounds indicates the omitted state carried exercise information.

21. Counterexample: narrow numerical bounds, wrong financial model

Suppose the primal lower bound is 10.15 and dual upper bound 10.17. Numerically, the optimal-stopping problem under the chosen model is tightly solved.

But if the underlying volatility/correlation model is misspecified, both bounds can tightly surround the wrong model price.

Falsifier: separate stopping-rule/numerical error from model calibration error. The primal–dual gap diagnoses the former, not the latter.

22. Benchmark hierarchy

Before trusting a high-dimensional primal–dual engine, benchmark simpler cases:

1. European option where early exercise is irrelevant;
2. one-dimensional American option against a fine tree;
3. finite-difference benchmark;
4. low-dimensional Bermudan benchmark;
5. then high-dimensional cases where the bounds become especially useful.

See American-option binomial-tree algorithms and finite-difference option-pricing algorithms for low-dimensional benchmark machinery.

23. Why the method matters most in high dimension

Trees and Cartesian PDE grids become expensive as the number of state variables grows. Monte Carlo scales more gracefully with dimension.

The historical weakness of Monte Carlo for American options was early exercise. Primal–dual methods turn that weakness into a bounding problem:

simulate a feasible policy from below and penalised foresight from above.

This makes multidimensional equity, interest-rate and real-option problems more tractable.

24. Alternatives and extensions

Longstaff–Schwartz: efficient lower-bound policy construction through regression.

Stochastic mesh: approximates continuation values using cross-path transition weights.

Binomial/trinomial trees: natural for low-dimensional Markov models.

Finite differences / complementarity solvers: strong for low-dimensional PDE formulations.

Regression-based dual methods: approximate martingales without the full cost of nested simulation.

Deep optimal stopping: neural policies/value approximators can handle complex state spaces but require independent bounding/validation to distinguish optimisation success from approximation error.

25. Variance reduction

Nested simulation can be expensive. Useful techniques include:

• common random numbers;
• control variates;
• antithetic variates;
• quasi-Monte Carlo where justified;
• policy-based path pruning;
• better conditional-expectation approximators.

Variance reduction should be validated by convergence behaviour, not assumed safe because runtime falls.

26. Martingale diagnostics

For an approximate martingale increment ΔM_j+1:

E[ΔM_j+1 | F_j] = 0

should hold under the model, up to simulation/estimation error.

Diagnostics can regress realised increments on current state variables. Significant predictable structure can indicate that the constructed penalty is not behaving like the intended martingale.

27. How this page differs from neighbouring owners

Longstaff–Schwartz owns continuation regression and policy construction.

The American binomial-tree page owns backward induction on a lattice.

Finite differences own PDE discretisation and complementarity constraints.

This page owns the two-sided Monte Carlo certification idea: feasible stopping from below, martingale duality from above.

28. Weak links

• training/evaluation leakage in the primal policy;
• poor continuation basis;
• too few outer paths;
• too few inner paths;
• incorrect discounting;
• non-martingale dual penalty;
• correlated random-number handling errors;
• exercise dates mis-specified;
• state variables omitted;
• narrow numerical gap mistaken for low model risk.

29. What would falsify confidence?

Confidence should be withdrawn if the upper estimate falls below an independently evaluated lower bound beyond statistical error; if bounds do not converge as simulation effort grows; if martingale increments contain predictable drift; if a simple benchmark lies outside the claimed interval; if the gap remains wide despite large simulation effort; or if the result is highly sensitive to policy basis/state representation.

30. Verification and update triggers

Preserve model parameters, exercise dates, payoff code, policy-training data, fixed policy coefficients, outer/inner seeds, path counts, variance-reduction settings, lower/upper samples and martingale diagnostics.

Revalidate when:

• the underlying model is recalibrated materially;
• payoff or exercise terms change;
• the policy architecture/basis changes;
• the state vector changes;
• random-number or simulation libraries change;
• the primal–dual gap widens;
• benchmark discrepancies appear.

31. Primary and high-quality references

• Leif Andersen and Mark Broadie, A Primal-Dual Simulation Algorithm for Pricing Multidimensional American Options, Management Science, 2004.
• L. C. G. Rogers, Monte Carlo Valuation of American Options, Mathematical Finance, 2002.
• Martin B. Haugh and Leonid Kogan, Pricing American Options: A Duality Approach, Operations Research, 2004.
• Francis A. Longstaff and Eduardo S. Schwartz, Valuing American Options by Simulation: A Simple Least-Squares Approach, Review of Financial Studies, 2001.
• For recent research continuing the regression-dual efficiency problem, see Efficient Upper Bounds for American Options: Regression-Based Duals from Backward Primals, 2026.

Educational boundary: Primal–dual bounds certify an optimal-stopping calculation only under the chosen stochastic model and numerical assumptions. They do not certify that the market model, parameters or future dynamics are correct.