DeepMartingale: Duality of the Optimal Stopping Problem with Expressivity and High-Dimensional Hedging

This paper introduces \textit{DeepMartingale}, a deep-learning framework that solves high-dimensional discrete-monitoring optimal stopping problems by directly optimizing parameterized martingales to produce tight dual upper bounds and scalable hedging strategies, while theoretically proving its ability to avoid the curse of dimensionality through specific expressivity guarantees.

The Gist

The Big Picture: Predicting the Future in a Chaotic World

Imagine you are a financial trader trying to price a very complex insurance policy (an option) that lets you sell a basket of 100 different stocks at a specific price, but you can choose to sell them on any of the next 50 days.

This is a classic "Optimal Stopping Problem." You want to know: When is the perfect moment to stop waiting and cash out to make the most money?

The problem is that the stock market is chaotic (like a stormy ocean), and with 100 stocks, the number of possible future scenarios is so huge that it breaks traditional computers. This is known as the "Curse of Dimensionality." It's like trying to find a single specific grain of sand on a beach that keeps getting bigger every time you add a new dimension.

The Solution: DeepMartingale

The authors, Junyan Ye and Hoi Ying Wong, propose a new method called DeepMartingale. Think of it as a super-smart AI detective that solves this problem from a completely different angle.

1. The Two Ways to Solve a Puzzle

Usually, people try to solve this problem in two ways:

• The Primal Way (The "Guess and Check" Method): You try to simulate millions of future paths and guess the best time to sell. It's like trying to find the exit of a maze by running through every possible path. In high dimensions, this gets messy and inaccurate.
• The Dual Way (The "Safety Net" Method): Instead of guessing the exit, you build a safety net (a mathematical "martingale") that guarantees you won't lose money, no matter what happens. If you can build a tight safety net, you know the true value of the option is just below that net.

DeepMartingale is a Pure-Dual approach. It doesn't try to guess the best time to sell. Instead, it focuses entirely on building the perfect, tightest possible safety net using Artificial Intelligence.

2. The Magic of the "Safety Net" (Martingale)

In finance, a Martingale is like a perfectly balanced scale. If you are betting on a fair coin flip, your expected wealth tomorrow is exactly what you have today.

The authors use a deep neural network (a type of AI) to learn how to balance this scale perfectly across 100 different stocks.

• The Analogy: Imagine you are juggling 100 balls in the rain. If you drop one, you lose money. Traditional methods try to predict exactly where each ball will land. DeepMartingale instead learns the perfect rhythm to keep all 100 balls in the air simultaneously, ensuring you never drop one.

3. Beating the "Curse of Dimensionality"

The biggest breakthrough in this paper is Expressivity.

• The Problem: Usually, as you add more stocks (dimensions), the computer needs exponentially more power to solve the problem. It's like needing a library the size of the universe to store the rules for a game with 100 players.
• The DeepMartingale Fix: The authors proved mathematically that their AI doesn't need a library the size of the universe. It only needs a library that grows polynomially (like a gentle curve) rather than exponentially (like a rocket ship).
• The Metaphor: Imagine you are trying to paint a picture of a forest.
  • Old Method: You need a separate brush for every single leaf. If the forest doubles in size, you need double the brushes. If it gets 100 times bigger, you need 100 times more brushes, and you run out of space.
  • DeepMartingale: You discover a "magic brush" that can paint any tree, any leaf, and any forest, no matter how big, using the same amount of paint. The complexity of the forest doesn't break the brush.

4. The "Hedging" Strategy (The Insurance Policy)

Once the AI learns the perfect safety net, it automatically tells you how to hedge (protect) your money.

• The Analogy: If the AI says, "To stay safe, you need to hold 0.5 shares of Stock A and -0.2 shares of Stock B," that is your Delta Hedge.
• Why it matters: In high dimensions (100+ stocks), previous methods failed to give reliable instructions. DeepMartingale gives clear, stable instructions on how to rebalance your portfolio, even when the market is chaotic.

How It Works (The "Secret Sauce")

1. Backward Thinking: The AI starts from the very end (the last day) and works backward to today. It asks, "If I am at the end, what is the value? Now, what was the value yesterday?"
2. Neural Networks as Math Tools: Instead of using simple formulas, they use deep neural networks to approximate the complex math needed to balance the scale.
3. Pure Dual Optimization: They train the AI to minimize the "slack" in the safety net. The tighter the net, the more accurate the price. They don't need to know the "true" answer beforehand; the math guarantees that if the net is tight, the price is correct.

The Results: What Did They Find?

They tested this on "Bermudan Options" (complex financial contracts) with up to 100 dimensions (100 stocks).

• Accuracy: Their method produced very accurate price estimates (upper bounds) where other methods failed or gave wild guesses.
• Stability: The hedging strategy (the instructions on how to trade) remained stable and reliable, even as the number of stocks increased.
• Scalability: They showed that you can predict how much computing power you need just by looking at small problems (e.g., 5 stocks) and scaling up the rules. This means you don't need to guess; you can design the AI architecture specifically for the problem size.

Summary in One Sentence

DeepMartingale is a new AI framework that solves complex financial puzzles by building a perfect mathematical "safety net" instead of guessing the future, allowing it to handle massive, high-dimensional problems (like 100+ stocks) without getting overwhelmed by the complexity.

Technical Summary

1. Problem Formulation

The paper addresses the optimal stopping problem for continuous-time Itô diffusion processes where exercise opportunities are monitored at discrete time points. This setting is fundamental for pricing and hedging Bermudan options (which can be exercised at specific dates) in high-dimensional markets (e.g., baskets of assets).

• Primal Problem: Maximize the expected discounted payoff over all admissible stopping times $\tau$:
  $$Y^*_0 = \sup_{\tau \in \mathcal{T}^N} \mathbb{E}[g(\tau, X_\tau)]$$
• The Challenge: In high dimensions ($d \gg 1$), traditional methods suffer from the curse of dimensionality.
  • Primal methods (e.g., Least-Squares Monte Carlo) rely on basis functions or policy iteration, which become unstable or computationally intractable as $d$ increases.
  • Existing Dual methods often require nested Monte Carlo simulations or accurate approximations of the Snell envelope (primal value), which are difficult to achieve in high dimensions.
  • Deep Learning approaches have shown promise but often lack rigorous theoretical guarantees regarding dimension scalability (expressivity) and fail to provide reliable hedging strategies in high dimensions.

2. Methodology: DeepMartingale

The authors propose DeepMartingale, a pure-dual deep learning framework. Unlike hybrid primal-dual methods, it does not approximate the value function (primal) first. Instead, it directly optimizes over a parameterized class of martingales to find the tightest upper bound.

Core Components:

1. Dual Formulation: Leveraging the duality theory (Rogers, Haugh & Kogan), the value function is represented as:
   $$Y^*_n = \inf_{M \in \mathcal{M}_n} \mathbb{E}_n \left[ \max_{n \le m \le N} (g(t_m, X_{t_m}) - M_{t_m} + M_{t_n}) \right]$$
   where $M$ is a martingale. The optimal martingale is the Doob martingale associated with the Snell envelope.

2. Numerical Approximation of the Doob Martingale:

   • The Doob martingale $M^*$ is represented via the martingale representation theorem as a stochastic integral: $M^*_t = \int_0^t Z^*_s dW_s$.
   • The integrand $Z^*$ is linked to the delta hedge strategy.
   • The authors discretize the integral over sub-intervals within each monitoring period using a numerical scheme involving $K$ sub-steps.

3. Neural Network Architecture:

   • The integrand $Z^*$ is approximated by a Deep Neural Network (DNN) $z_\theta(t, x)$.
   • The martingale increments are constructed as: $\xi^\theta_n = \sum_{k} z_\theta(t^k_n, X_{t^k_n}) \cdot \Delta W_{t^k_n}$.
   • The training objective minimizes the dual upper bound loss (first moment) or the second-moment loss (variance minimization) of the dual functional.

4. Pure-Dual Training:

   • The algorithm trains the network parameters $\theta$ backward in time (from $N-1$ to $0$) to minimize the expected value of the dual functional.
   • It requires no primal information (no approximation of the stopping rule or value function is needed during training).

3. Key Contributions

A. Theoretical Expressivity and Dimension Scalability

The paper's most significant contribution is a rigorous expressivity theorem proving that DeepMartingale avoids the curse of dimensionality.

• Theorem 4.30: Under structural assumptions (specifically for Affine Itô Diffusions with "1/2-log growth" conditions), the size of the neural network required to approximate the value function to accuracy $\varepsilon$ scales as:
  $$\text{Size} \le \tilde{c} d^{\tilde{q}} \varepsilon^{-\tilde{r}}$$
  where constants $\tilde{c}, \tilde{q}, \tilde{r}$ are independent of the dimension $d$.
• This implies that the computational resources grow polynomially with dimension, rather than exponentially.
• The theory relies on Random Neural Networks (RanNN) and Reproducing Kernel Banach Spaces (RKBS) to establish universal approximation properties in infinite-dimensional settings.

B. Dimension Scaling Law Estimation

The authors propose a practical methodology to guide architecture design in high dimensions:

• By running experiments on low-dimensional cases ($d=2$ to $10$), one can regress the error against dimension to estimate the empirical scaling order $p$ (where $\text{Error} \propto d^p$).
• This estimated order is then used to scale up the network width, depth, and training epochs for high-dimensional problems ($d=100+$), ensuring memory feasibility and accuracy.

C. High-Dimensional Hedging Strategy

• The learned martingale integrand $Z^*$ directly yields a Deep Delta Hedging strategy: $\vartheta(t, x) = b^{-1}(t, x) z_\theta(t, x)$.
• This provides a dimension-scalable hedging policy that is theoretically grounded and practically implementable, addressing a gap where previous deep learning methods failed to produce stable hedges in high dimensions.

4. Numerical Results

The authors validate the framework on Bermudan Max-Call options with dimensions up to $d=100$.

• Accuracy: DeepMartingale produces tight, computable dual upper bounds that are significantly more accurate than competing methods (e.g., Guo-DeepPrimalDual, Alfonsi-PureDual) in high dimensions.
• Scalability: While competing methods often run out of memory (OOM) or degrade in performance as $d$ increases, DeepMartingale maintains stability and accuracy up to $d=100$ when scaled according to the derived dimension scaling law.
• Hedging Performance:
  • In low dimensions ($d=2$), DeepMartingale's delta hedge is competitive with state-of-the-art methods.
  • In high dimensions ($d=50$), DeepMartingale delivers a reliable and stable hedging strategy, whereas the primal-dual baseline (Guo-DeepPrimalDual) fails to produce a reliable hedge, often degenerating to a zero-martingale solution.
• Convergence: The numerical experiments confirm the theoretical convergence of the upper bounds and the stability of the hedging error under worst-case exercise scenarios.

5. Significance

• Theoretical Breakthrough: It provides the first rigorous proof that a deep learning-based dual approach can overcome the curse of dimensionality for optimal stopping problems, establishing a dimension-independent complexity bound.
• Practical Impact: It offers a viable solution for pricing and hedging complex, high-dimensional financial derivatives (like basket options) where traditional Monte Carlo methods fail.
• Methodological Shift: By operating as a pure-dual method, it avoids the error propagation inherent in primal-dual approaches, leading to more robust results in high-dimensional settings.
• Guidance for Industry: The proposed "dimension scaling law" estimation provides a concrete, data-driven protocol for practitioners to design neural network architectures for high-dimensional financial problems without trial-and-error.

In summary, DeepMartingale bridges the gap between deep learning expressivity theory and practical financial engineering, offering a theoretically sound and numerically robust framework for high-dimensional optimal stopping and hedging.