Source-linked AI summary
Deep optimal stopping
Sebastian Becker, Patrick Cheridito, Arnulf Jentzen
TL;DR
The paper addresses optimal stopping problems whose traditional numerical methods face dimensionality challenges. It directly learns stopping rules from Monte Carlo samples using recursively parameterized neural networks, and reports accurate results across three problems, including high-dimensional settings, with short computing times.
Problem
Optimal stopping is difficult in high dimensions because standard tree- and lattice-based methods have exponentially increasing complexity.
Method
The method recursively approximates 0-1 stopping decisions with multilayer feedforward neural networks trained through stochastic gradient ascent, supplemented by a dual upper bound.
Results
The approach produces very accurate results with short computing times across Bermudan max-call, callable multi barrier reverse convertible, and fractional Brownian motion problems.
Takeaways & Limitations
The experiments demonstrate applicability to simulated-randomness settings and stopping problems with dimensions reaching d = 500.
Takeaways & Limitations
The formulation assumes discrete stopping opportunities and a Markov state representation, with past information potentially increasing the state dimension.
Abstract
from arXiv · showhide
In this paper we develop a deep learning method for optimal stopping problems which directly learns the optimal stopping rule from Monte Carlo samples. As such, it is broadly applicable in situations where the underlying randomness can efficiently be simulated. We test the approach on three problems: the pricing of a Bermudan max-call option, the pricing of a callable multi barrier reverse convertible and the problem of optimally stopping a fractional Brownian motion. In all three cases it produces very accurate results in high-dimensional situations with short computing times.
1 Introduction
The paper develops a deep-learning approach that directly approximates optimal stopping times and evaluates it on several high-dimensional and fractional Brownian motion problems. It addresses the dimensional limitations of traditional methods while providing lower and upper bounds for the optimal value.
- Traditional tree- and lattice-based methods suffer from exponential complexity in dimension and typically perform well only up to three dimensions.
- The method decomposes an optimal stopping time into sequential 0-1 decisions approximated recursively by multilayer feedforward neural networks.
- The resulting neural-network policies can approximate optimal stopping times to any desired accuracy.
- A stochastic-gradient-ascent policy produces a lower bound, while a dual method provides an upper bound for the optimal value.
- The approach is tested on Bermudan max-call options, callable multi barrier reverse convertibles, and optimally stopping fractional Brownian motion.
- Experiments cover Bermudan max-call dimensions from d = 2 through d = 500 and callable multi barrier reverse convertible dimensions from d = 2 through d = 30.
2 Deep learning optimal stopping rules
The method represents optimal stopping rules as sequential binary decisions and approximates those decisions with neural networks trained by backward induction. Universal approximation results establish that sufficiently wide networks can achieve arbitrarily near-optimal stopping values.
- Scope and assumptions: The formulation assumes a finite-horizon discrete-time Markov process and integrability of the reward, with stronger integrability required for confidence intervals.Continuous-time problems can be approximated through time discretization, and the stronger condition holds in the paper’s examples.
- Stopping-time representation: Optimal stopping times can be represented by measurable binary decisions f_n(X_n) at each time, rather than the full observed path.For Markov processes, the decision at time n depends only on the current state X_n.
- Stopping-time representation: The recursive construction starts from the terminal decision f_N ≡ 1 and computes earlier stopping decisions backward in time.Theorem 1 relates an approximate stopping time from time n+1 to a decision function at time n, with the optimal decision comparing immediate reward and continuation value.
- Neural-network approximation: For any depth I ≥ 2 and ε > 0, sufficiently wide neural networks can make stopping decisions whose expected reward is within ε of the optimal continuation-step value.The approximation argument establishes the required flexibility for each recursive stopping decision.
- Overall approximation guarantee: For the full problem, there exist network parameters Θ such that E g(τ^Θ, X_τ^Θ) ≥ sup_τ∈T E g(τ, X_τ) − ε.The parameter vector collects the network parameters for the decisions at times 0 through N−1.
3 Bounds, point estimates and confidence intervals
The section develops lower and upper bounds, point estimates, and asymptotically valid confidence intervals for the optimal value V0. The lower estimate evaluates the learned stopping rule, while the upper estimate uses a martingale-based dual formulation.
- Lower bound: The trained stopping decisions define a stopping time whose expected reward provides a lower bound L for V0.The lower-bound estimate is unbiased and converges to L as the number of independent evaluation paths KL increases.
- Upper bound: The upper bound is based on a dual formulation in which martingales and conditionally mean-zero errors yield an upper bound for V0.The bound is tight when the martingale equals MH and the estimation errors vanish.
- Upper bound: The method constructs a martingale from the candidate stopping time by estimating continuation values with independent conditional continuation paths.The continuation paths are generated independently across simulated starting paths and continuation-path indices.
- Upper bound: The resulting upper-bound estimator is unbiased and converges to U as the number of independent upper-bound paths KU increases.The independent realizations used for upper-bound estimation are separate from those used to train the stopping decisions.
- Confidence intervals: Under square-integrability, central-limit-theorem intervals for L and U combine to give an asymptotically valid 1 − α confidence interval for V0.The interval validity is stated for sufficiently large KL and KU.
4 Examples
The method is tested on Bermudan max-call options, callable multi barrier reverse convertibles, and optimal stopping of fractional Brownian motion, including high-dimensional settings. The experiments use simulated asset or process paths and report bounds, estimates, confidence intervals, and computation times.
- Bermudan max-call options: The experiments cover Bermudan max-call options on symmetric and asymmetric multi-dimensional assets.The symmetric case uses common volatilities, while the asymmetric case uses increasing volatilities across assets.
- Bermudan max-call options: The max-call option payoff depends on the maximum of d underlying assets and is evaluated on an equidistant exercise grid.The model is specified under multi-dimensional Black–Scholes dynamics, chosen to enable comparisons with methods in the literature.
- Callable multi barrier reverse convertibles: Callable multi barrier reverse convertibles are tested with multiple underlying assets, barriers, coupons, redemption opportunities, and worst-performing-asset conversion.The issuer’s problem is formulated as a minimization problem; the learned stopping time provides an upper bound and the dual method a lower bound.
- Callable multi barrier reverse convertibles: The callable MBRC experiments compare learned bounds with fair values of otherwise identical non-callable securities.The non-callable fair values are estimated from 4,096,000 Monte Carlo payoff samples, taking 5 to 44 seconds for dimensions 2 to 30.
- Optimally stopping a fractional Brownian motion: For fractional Brownian motion, the method estimates supτ∈{0,t1,...,1} E W^H_τ across Hurst parameters from 0.01 to 1.For H = 1/2 and H = 1, the 95% confidence intervals contain the exactly calculable true values; estimates are up to three times higher than heuristic values for H > 1/2 and up to five times higher for H < 1/2.