---
abstract: |
    In this paper, we propose deep learning algorithms for ranking response surfaces, with applications to optimal stopping problems in financial mathematics.  The problem of ranking response surfaces is motivated by estimating optimal feedback policy maps in stochastic control problems, aiming to efficiently find the index associated to the minimal response across the entire continuous input space ${\mathcal{X}}\subseteq {\mathbb{R}}^d$. By considering points in ${\mathcal{X}}$ as pixels and indices of the minimal surfaces as labels, we recast the problem as an image segmentation problem, which assigns a label to every pixel in an image such that pixels with the same label share certain characteristics.  This provides an alternative method for efficiently solving the problem instead of using sequential design in our previous work \[R. Hu and M. Ludkovski, SIAM/ASA Journal on Uncertainty Quantification, 5 (2017), 212–239\]. 

    Deep learning algorithms are scalable, parallel and model-free, [*i.e.*]{}, no parametric assumptions needed on the response surfaces.  Considering ranking response surfaces as image segmentation allows one to use a broad class of deep neural networks, [*e.g.*]{}, UNet, SegNet, DeconvNet, which have been widely applied and numerically proved to possess high accuracy in the field.  We also systematically study the dependence of deep learning algorithms on the input data generated on uniform grids or by sequential design sampling, and observe that the performance of deep learning is [*not*]{} sensitive to the noise and locations (close to/away from boundaries) of training data.  We present a few examples including synthetic ones and the Bermudan option pricing problem to show the efficiency and accuracy of this method. 
author:
- 'Ruimeng Hu[^1]'
bibliography:
- 'Reference.bib'
title:  Deep Learning for Ranking Response Surfaces with Applications to Optimal Stopping Problems
---

**Keywords:** Response surfaces ranking, deep learning, UNet, optimal stopping, Bermudan option

Introduction {#sec_intro}
============

We start by introducing the general setup of ranking surface response problems, and then describe the connection to stochastic control problems and related literature.  For the purpose of consistency, we shall use the same notions as in our previous work [@HuLudkovski17] and refer the interested readers to it for more details of the problem background. 

Denote $\mu_\ell : {\mathbb{R}}^d \supseteq {\mathcal{X}}\to {\mathbb{R}}$, $\ell \in {\mathfrak{L}} \equiv \{1,2, \ldots, L\}$ as smooth functions over a subset ${\mathcal{X}}$ of ${\mathbb{R}}^d$. The surface ranking problem consists in assigning the index of the minimal surface to every input $x$ in the entire (usually continuous) space ${\mathcal{X}}$, namely, in finding the classifier $$\label{def_cal}
\mathcal{C}(x) := \arg\min_\ell \left\{\mu_\ell(x)\right\} \in {\mathfrak{L}}, \quad \forall x \in {\mathcal{X}}\subseteq {\mathbb{R}}^d.$$ The functions $\mu_\ell$ are [*a priori*]{} unknown but can be noisily sampled, [*i.e.*]{}, for any $x \in {\mathcal{X}}, \ell \in {\mathfrak{L}}$, one can access $\mu_\ell(x)$ through its stochastic sampler $Y_\ell(x)$: $$\label{def_Y}
Y_\ell(x) = \mu_\ell(x) + {\epsilon}_\ell(x), \ \ell \in {\mathfrak{L}},$$ where ${\epsilon}_\ell$’s are independent random variables with mean zero and variance $\sigma_\ell^2(x)$. In other words, one can sample by Monte Carlo the $L$ smooth hyper-surfaces on ${\mathcal{X}}$.

We are interested in accurately estimating ${\mathcal{C}}(x)$ using deep learning algorithms.  Let ${\mathcal{C}}_{dl}(x)$ be the classifier produced by deep learning algorithms, and to study the performance of different network architectures and experiments designs, we evaluate the difference by the following loss metric: $$\label{def_loss}
{\mathcal{L}}({\mathcal{C}}, {\mathcal{C}}_{dl}) = \int_{{\mathcal{X}}}  \mathds{1}_{\{{\mathcal{C}}(x) \neq {\mathcal{C}}_{dl}(x)\}}\lambda(\mathrm{d}x),$$ where $\lambda(\mathrm{d}x) \in \mathcal{P}({\mathcal{X}})$ is a probability measure on ${\mathcal{X}}$ specifying the relative importance of ranking different regions.  Note that when $\lambda(\mathrm{d}x) = \mathcal{U}({\mathcal{X}})$ is the uniform measure, ${\mathcal{L}}$ gives the mis-labeled percentage.  This is essentially the *accuracy* metric in deep learning, often appearing as the first metric one uses to judge the performance of a neural network model/architecture. 

To interpret in the context of dynamic programming, one can think $x$ as system states, $\ell$ as indices of various actions available to the controller, $\mu_\ell(\cdot)$ as the expected costs-to-go and ${\epsilon}_\ell(\cdot)$ as simulation noises arising from pathwise evaluation of the underlying stochastic system and corresponding costs.  In what follows, we will clarify this relation. 

**Motivation.**  We consider the following stochastic control problems, and let $X_{(\cdot)} \equiv X_{(\cdot)}^u$ be a discrete-time stochastic state process controlled by a Markovian strategy $u \in {\mathfrak{L}}$, following $$X_{t+1}^u = F(X_t, u_t, \varepsilon_{t+1}), \quad t \in {\mathfrak{T}} \equiv [0,1, \cdots, T],$$ for some map $F: {\mathcal{X}}\times {\mathfrak{L}} \times R \to {\mathcal{X}}$, and some centered independent noise source $\varepsilon_{t+1}$. In general, the cost to be minimized is of the form $$\label{def_cost}
 c(0,u_{0:T}) = \sum_{t = 0}^T g(t, X_t, u_t),$$ where $g(t,\cdot, u_t)$ represents the running cost at stage $t$ using the strategy $u_t$. For notations, we use a single subscript $t$ to represent the value of the process at time $t$ , and use $t:T$ to emphasis the whole process from $t$ to T. By defining the value function $$\label{def_V}
V(t,x) := \inf_{u_{t:T} \in {\mathfrak{L}}^{\bigotimes (T-t)}} {\mathbb{E}}_{t,x}[c(t, u_{t:T})],$$ with $E_{t,x}[\cdot] = E[\cdot \vert X_t = x]$ denoting the expectation given condition $x$, the minimized cost is represented by $V(0,x)$ and the corresponding optimal strategy is given by the minimizer $u^\ast_{0:T}$. Using dynamic programming, $V(t,x)$ satisfies: $$\label{eq_V}
V(t,x) = \inf_{u \in {\mathfrak{L}}} \{g(t,x,u) + {\mathbb{E}}_{t,x}[V(t+1,X_{t+1}^u)]\}.$$

By introducing the term $\mu_u(t,x)$: $$\label{def_muu}
\mu_u(t,x) = g(t,x,u) + {\mathbb{E}}_{t,x}[V(t+1, X_{t+1}^u)], \quad  \forall u \in {\mathfrak{L}},$$ the connection to problem – now becomes clear.  For each $u \in {\mathfrak{L}}$, the Q-value $\mu_u(t,x)$, representing the expected cost-to-go corresponding to action $u$, is a response surface in .  For fixed $t$, finding the optimal strategy map $x \mapsto u^\ast(t,x)$ is equivalent to identify the classifier in , as $V(t,x) = \inf_{u \in {\mathfrak{L}}}\left\{\mu_u(t,x)\right\}$. Then, this stochastic control problem $V(0,x)$ can be solved by backwardly identifying $u^\ast(s,\cdot)$, namely, by solving $T$ ranking problems of the form from stage $T$ to 1.  More precisely, assuming strategy maps after time $t$, denoted by $\left\{\hat u(s,\cdot)\right\}_{s=t+1}^T$, are already generated, then $\hat u(t, \cdot)$ is determined by ranking across different $u$, where ${\mathbb{E}}_{t,x}[V(t+1, X_{t+1}^u)]$ is estimated by averaging the cost along trajectories $X_{(t+1):T}$ that follow the strategy $\left\{\hat u(s,\cdot)\right\}_{s=t+1}^T$.

In principle, this approach is applicable to any stochastic control problem, even under continuous-time framework with a continuum of strategies, since both time and strategy space can be approximated by discretization.  However, it is especially attractive when the number of actions is finite and small.  For instance, in optimal stopping problems [@GL13], the action space has only two elements ${\mathfrak{L}} = ${stop, continue} and the immediate reward $\mu_{stop}$ is usually obtained at no cost, leading to only the continuation value $\mu_{cont.}(t,x)$ to be simulated.  A canonical example in this case is pricing Bermudan-type options [@ludkovski2015kriging].  Applications that need to evaluate multiple surfaces $\mu_\ell$ arise from pricing swing options [@MeinshausenHambly04], decision makings in energy markets [@AidLangrene12; @Secomandi11] ([*i.e.*]{}, deciding whether to expand the productivity, to explore new energy resources or do nothing), epidemic management [@LudkovskiLin14; @LN10; @LN11wsc; @MerlGramacy09], to name a few. 

**Main approach and contribution.**  Our main contribution is to propose an alternative strategy to solve by deep learning algorithms.  The key idea is to build up a neural network (NN) and let it learn to solve the problem of interest by itself via simulated data.  This learning process, which is called the training of an NN, can be time-consuming.  However, once this is accurately done, it will be computationally efficient to solve a problem of the same type.  In our case, this is to say, once we use certain simulated data $Y_\ell(x)$ and its labels to train the neural network and obtain the desired accuracy, the predicted classifier ${\mathcal{C}}_{dl}$ of a new location $x$ will be instantaneous and accurate by mainly operations of matrix-vector multiplication.  For this reason, NN is a desired approach to solve . 

The problem of ranking response surfaces is equivalent to partition the entire input space ${\mathcal{X}}$ into parts distinguished by labels (indices of the minimal surface).  We observe that, if one treats ${\mathcal{X}}$ as an image, then the labeling function $\mathcal{C}$ essentially divides the image into disjoint parts.  This means that one can phrase the problem as image segmentation, where deep learning has been successful and become a primary and powerful tool in modern machine learning community [@LeCunBengioHinton15; @ShelhamerLongDarrell15; @RonnebergerFischerBrox15].  In the meantime, mathematical theory on deep neural networks (NN), *e.g.*, whether results produced by NN converges to the ground truth as the number of neural/layers tends to infinity, has also been developed by analyzing the corresponding mean-field optimal control problem [@EHanLi19].  Compared to our previous work [@HuLudkovski17] where response surfaces are modeled by Gaussian process, the advantage of deep learning algorithms is that it is model-free, that is, they make the predicted labels $\hat {\mathcal{C}}$ no more depend on specific parameterizations of $\mu_\ell$. Moreover, through numerical studies, we find that NN also has the following advantages:

-   It is insensitive to sampling locations.  The loss ${\mathcal{L}}$ are comparable when $C_{dl}$ are produced using uniform samples versus sequentially designed samples [@HuLudkovski17] over ${\mathcal{X}}\times {\mathfrak{L}}$. Then regarding implementation complexity and the ability of parallelism, uniform samples are more preferable. 

-   It can auto-detect wrong inputs.  Since $\mu_\ell$ is only accessible by its stochastic sampler $Y_\ell$, the training input labels are $\arg\min_{\ell \in {\mathfrak{L}}} Y_\ell$, which certainly contain wrong labels especially around the boundaries.  The NN will try not to learn those labels correctly, and can automatically ignore those inputs. 

**Related Literature.**  Mathematically, one can view as a partition over the input ${\mathcal{X}}= \cup_{i=1}^L {\mathcal{C}}_i$: $${\mathcal{C}}_i := \{x \in {\mathcal{X}}, {\mathcal{C}}(x) = i\}, i \in {\mathfrak{L}}.$$ The problem is related to contour-finding of $\partial {\mathcal{C}}_i$, which has been extensively studied by numerous sequential methods [@GL13; @Picheny10; @RanjanBingham08].  For each $x$, the goal of identifying the minimal response $\arg\min_\ell\mu_\ell(x)$ corresponds to multi-armed bandits (MAB) problems.  Consider the surfaces $\mu_\ell(x)$ as $L$ arms’ rewards of the bandit, then is equivalent to explore the extreme bandit [@BubeckMunos11; @BubeckMunos11X; @GabillonBubeck11; @GrunewalderAudibert10].  Statistically, for a tractable approximation of $\mu_\ell$, various models have been proposed, including Gaussian process (GP) [@HuLudkovski17], BART [@chip:geor:mccu:2010], Dynamic trees [@GTP-trees11], treed GPs [@tgpPackage], local GPs [@gramacy:apley:2013], particle based Gaussian process [@GramacyPolson11], GPs with Student-$t$ noise and $t$-processes [@lyu2018evaluating]. 

Let us mention two recent work that are related to our paper.  In our previous work [@HuLudkovski17], the problem was tackled under the GP modeling for $\mu_\ell$ with a different loss metric: $$\label{eq:loss}
{\mathcal{L}}(\hat{{\mathcal{C}}}, {\mathcal{C}}) := \int_{\mathcal{X}}\left\{ \mu_{\hat{{\mathcal{C}}}(x)}(x) -\mu_{{\mathcal{C}}(x)}(x) \right\} \; \lambda(\mathrm{d} x).$$ This is a blended criterion between marginally estimation of $\mu_\ell$ and classification.  The loss is proportional to the difference between the true minimal surface and the estimated minimal one, which tolerates estimation errors of $\mu_\ell$ as long as the minimal response does not change.  While in this paper, we make no model assumption on $\mu_\ell$ and treat as a pure classification/segmentation problem.  In [@BeChJe:18], Becker, Cheridito, and Jentzen directly address the optimal stopping problem using deep learning by learning the optimal stopping rule from Monte Carlo samples via a feedforward NN with three fully connected layers.  Compared to the results in [@BeChJe:18], our work distinguishes for two reasons.  On the one hand, our problem setup is more general, and optimal stopping problems is just an application of ranking response surfaces; on the other hand, the emphasis of our work is on the architecture of neural networks, [*i.e.*]{}, by recasting optimal stopping as the image segmentation problem, one is allowed to use more delicate architecture of networks (e.g. convolutional neural networks [@ShelhamerLongDarrell15], UNet [@RonnebergerFischerBrox15; @HaRoMyYa:18], SegNet [@BadrinarayananKendallCipolla17]), which can yield better learning performance; see Section \[sec:numerics\] for more details. 

**Organization of the paper.**  The rest of the paper is organized as follows: In Section \[sec:nn\], we introduce the design of network models and deep learning algorithms.  In Section \[sec:numerics\], we test the performance of deep learning by one- and two-dimensional examples of ranking response surfaces, and systematically study the dependence of deep learning algorithms on the quality of input data generated on uniform grids or by sequential design sampling.  We apply the deep learning algorithms to Bermudan option pricing in Section \[sec:Bermudan\], and make conclusive remarks in Section \[sec:conclusion\]. 

Neural networks and deep learning algorithms {#sec:nn}
============================================

Inspired by neurons in human brains, neural networks (NNs) are designed for computers to learn from observational data.  Deep learning algorithms are techniques for accurate and efficient learning in neural networks.  For interesting problems including image recognition, natural language processing, boundary detection, image classification and segmentation, neural networks and deep learning currently provide the best solutions.  In what follows, we give a brief introduction to basic concepts in neural networks and how it works.  Section \[sec:algorithm\] is dedicated to the algorithms for our ranking problem . 

Preliminaries on deep learning
------------------------------

We start with some terminology.  Basically, NNs are built up by [layers]{}.  Each layer contains a number of [neurons]{}.  Layers with different functions or neuron structure are called differently, including fully-connected layer, constitutional layer, pooling layer, recurrent layers, etc.  Figure \[fig:ffnn\] below is a simple feed-forward NN with three fully-connected layers, where nodes represent neurons and arrows represent the information flow.  As shown in the figure, information is constantly “fed forward” from one layer to the next.  The first layer (leftmost column) is called the input layer, and the last layer (rightmost column) is called the output layer.  Layers in between are called hidden layers, as they have no connection with the external world.  In this case, there is only one hidden layer with four neurons. 

![ An illustration of a simple feedforward neural network. []{ data-label="fig:ffnn"}](feedforward.png){width="60.00000%"}

We now explain how NN learns from data.  For fully-connected layers, every neuron has two kinds of parameters, the weights $w$ and the bias $b$. An input $x$ goes through a neuron outputs $f(w \cdot x + b)$, where $f$ is an activation function.  In the above illustrated NN, $x_1$, $x_2$ and $x_3$ are the input of neural network.  Nodes in the hidden layer take ${\boldsymbol{x}}=(x_1,x_2,x_3)$ as inputs and output $y_j = f({\boldsymbol{w}}_j \cdot {\boldsymbol{x}} + {b}_j)$, $j=1,\cdots,4$, ${\boldsymbol{w}}_j=(w_{j,1},w_{j,2},w_{j,3})$. Then they are considered as inputs for the output layer, and $z_1=f({\boldsymbol{w}}_z \cdot {\boldsymbol{y}} + {b_z})$. Based on the training data set, [*i.e.*]{}, known pairs of input and desired output $z(x)$, the [learning]{} of an NN is to find the optimal weights and biases, so that the output from the network well approximates $z$ for all training inputs $x$. Mathematically, this is done by minimizing some loss function, for instance, the mean square loss: $$\label{def_costfunctional}
c(w,b) = \frac{1}{2n}\sum_x \left\lVert z(x) - z\right\rVert^2,$$ where $(w,b)$ denotes the collection of all weights and biases in the network and $n$ is the total number of training inputs.  Depending on the depth and size of the NN, training can take hours.  However, when this is done, that is, the optimal or near-optimal parameters are obtained, prediction from new input $x_0$ is efficient as it will be only matrix-vector multiplication. 

**Activation function.**  Popular types are sigmoid, Tanh, ReLU, Leaky ReLu, softmax, etc.  The activation functions are not necessarily the same from layer to layer, while for the output layer, some types generally work better than others.  For instance, in binary classification problems, a common choice is the [sigmoid]{} function $f(x) = \frac{1}{1 + e^{-x}}$, as it maps real-valued inputs to $[0,1]$. For multiple-class classification, the [softmax]{} function, mapping ${\mathbb{R}}^d$ to a probability simplex, is usually preferred.  In both cases, outputs are interpreted as the probability of being in one of the categories. 

**Loss function.**  Depending on the different goals, the form of loss function can be different, varying from mean squared error (MSE), mean absolute error, Kullback Leibler (KL) Divergence, $\ell_2$ norm, $\ell_1$ norm, cross entropy, hinge to squared hinge.  The MSE loss is generally better suited to regression problems, while cross entropy and hinge are commonly used in classification problems.  Besides, $L_1$ or $L_2$ regularization are sometimes added to the loss function, to help to reduce overfitting. 

**Optimizer.**  Finding the optimal weights and biases in is in general a high-dimensional optimization problem.  This is so-called the training of NN, which is commonly done based on stochastic gradient descent method ([*e.g*]{}.,  Adam [@Adam; @Adamcvg], NADAM [@Dozat16]). 

Deep learning algorithms {#sec:algorithm}
------------------------

In computer vision, images segmentation is the process of partitioning a digital image into multiple segments.  Each pixel in an image will be labeled for a class it belongs to.  The training data consist of the RGB values of each pixel and its desired label.  Considering ranking response surfaces as the segmentation of images, the “image” is then the entire input space ${\mathcal{X}}$ while the class label is the index of the minimal surface.  Each point in ${\mathcal{X}}$ is treated as our “pixels”, and the “color” of each “pixel” is then the coordinates of the location.  With the concepts introduced above, we describe the deep learning algorithm with details in this subsection, which includes the input, output, and architecture of neural networks. 

[**Input and output**]{}.  The design of the input and output layers in a network is often straightforward.  Recall our problem , we aim at training an NN using noisily sampled data $Y_\ell(x)$ at some locations $x$, so that after training it can efficiently and accurately label each location $x$ in ${\mathcal{X}}$ by the index of the minimal surface.  The input to the network is $x^{1:J}\in{\mathbb{R}}^{J\times d}$ where $J$ corresponds to the number of points and $d$ is the dimensionality of the problem.  The desired output should take the form: $$\mathcal{C}_{{\text{dl}}}=(p_{j\ell}),\quad j=1,\cdots,J,\; \ell=1,\cdots,L,$$ where $L$ is the number of response surfaces, and $p_{j\ell}$ is the probability that the $\ell^{\text{th}}$ surface is the minimal at the $j^{\text{th}}$ point.  This is usually achieved by implementing the softmax activation function for the output layer.  For example, if one gets the following output $$\left(
\begin{matrix}
    0.1 & 0.2 & 0.7 \\
    0.8 & 0.1 & 0.1
\end{matrix}\right),$$ then it means that the network believes the $3^{\text{rd}}$ surface is minimal with probability $70\%$ at the $1^{\text{st}}$ point, and that the $1^{\text{st}}$ surface is minimal with probability $80\%$ at the $2^{\text{nd}}$ point.  The predicted labels for the corresponding points will be given by taking the row-wise argmax of the matrix, which produces a column vector in ${\mathbb{R}}^J$. In the above example, the input contains two points $x^1$ and $x^2$, and the corresponding labels are $[3,1]^\dagger$.

During the training stage, the network is told what the true labels should be for the inputs $x^{1:J}$, and it adjusts its belief according to this information via minimizing some loss function (cf. ).  In the generalization stage, only locations in ${\mathcal{X}}$ are given, and one uses the network output as the final result.  In both stages, the accuracy will be evaluated by the percentage of correctly predicted labels against the ground truth, and results are called the *training accuracy* and the *generalization accuracy*.  This is also the loss metric with uniform measure $\lambda(\mathrm{d}x) = \mathrm{d}x/{\left|{\mathcal{X}}\right|}$.

When training with noisy data, the ground truth is unknown and the true labels are up to our best knowledge.  That is, the “ true” label is produced by simulating $Y_\ell(x)$ for each $\ell \in {\mathfrak{L}}$ and take $\arg\min_\ell Y_\ell(x)$. Of course, this leads to mis-labeling and affects both training and generalization accuracies.  In Section \[sec:numerics\], we present numerical studies on synthetic examples with known ground truth and study the accuracies of deep learning algorithms. 

  -- --
     
  -- --

[**Architecture**]{}.  Although the design of the input/output layers of an NN is usually straightforward, it can be quite sophisticated to find a good architecture for the hidden layers.  In particular, it is unlikely to summarize the design strategies for the middle layers with a few simple rules, for instance, how to trade off the number of hidden layers against the time required to train the network.  The global topology of the network consists of blocks and the interactions between them, which are in general described by the meta-architecture.  Designing proper meta-architecture can improve the performance of networks, and in the context of ranking response surfaces, recasting the problem as image segmentation will allow us to use the meta-architecture of Unet [@RonnebergerFischerBrox15], which has been considered and widely used as an efficient network structure for image segmentation. 

We now visualize two architectures in Figure \[fig:arch\], which will be used for the two-dimensional numerical examples in Sections \[sec:numerics\] and \[sec:Bermudan\].  They are built using Keras [@Keras], a high-level neural networks API.  Main blocks are fully-connected (shown as dense in Figure \[fig:arch\]) layers and convolutional layers.  The first (left) one is built up by dense blocks.  We add an $\ell_1/\ell_2$ activity regularizer (shown as Activation) to help reduce the generalization error, which may not always be needed.  ReLu is chosen as the activation function for hidden layers, while sigmoid or softmax is used for the output layer depending on the number of classifiers.  In the second (right) architecture, we use a 2D convolutional layer (shown as Conv2D) with $3 \times 3$ kernel as the first hidden layer, which outputs 4D tensor.  It expands the number of feature channels, which help to reduce the number of necessary feature maps leading to an improvement of computational efficiency [@HeZhReSu:15; @SpDoBrRi:14]. “ MaxPooling2D” is for downsampling, and “Concatenate” merges outputs from different dense blocks, with one before downsampling and one after upsampling so that their dimension is matched.  The “concatenate” action makes the architecture have a “U”-shape.  Activation functions are chosen the same as in the first architecture.  We remark that, such a UNet structure can be applied for problems with any dimensionality, by merely adjusting the dimensionality of convolutional and down/up sampling layers. 

Let us also mention that the neural networks used in [@BeChJe:18] are a feed-forward NN with two fully-connected hidden layer, whose convergence is easier to be analyzed.  While by recasting the optimal stopping problems as image segmentation, one is allowed to use a broader class of neural networks with more delicate architecture ([*e.g.*]{} UNet), which produces better learning efficiency, although the corresponding theory for convergence is still unclear based on the best of my knowledge. 

Numerical experiments {#sec:numerics}
=====================

In this section, we analyze the performance of deep learning algorithms (both feed-forward NNs and UNet) by studying the one- and two-dimensional examples used in [@HuLudkovski17].  We also systematically analyze the dependence of deep learning algorithms on the input data generated on uniform grids or by sequential design sampling.  As a consistency, we shall use the same notations as in [@HuLudkovski17 Section 4]. 

One-dimensional example
-----------------------

We consider the one-dimensional toy model used in [@HuLudkovski17], originally from [@kmPackage-R Section 4.4].  Let $L = 2, {\mathcal{X}}= [0, 1]$ in , and define the noisy responses $Y_1(x)$ and $Y_2(x)$ as $$\begin{aligned}
Y_1(x) &= \mu_1(x) + {\epsilon}_1(x) \equiv \frac{5}{8}\left(\frac{\sin(10x)}{1+x} + 2x^3\cos(5x)+0.841\right) + \sigma_1(x)Z_1, \\
Y_2(x) &= \mu_2(x) + {\epsilon}_2(x) \equiv 0.5 + \sigma_2(x)Z_2,\end{aligned}$$ where $Z_\ell$ are independent standard Gaussians, with the noise strengths fixed at $\sigma_1(x) \equiv 0.2$ and $\sigma_2(x) \equiv 0.1$, homoscedastic in $x$ but heterogenous in $\ell=1,2$. We take the uniform weights $\lambda(\mathrm{d} x)={\,\mathrm{d}}x$ in the loss function on ${\mathcal{X}}$, which is interpreted as the percentage of mis-labeled locations. 

![ The true response surfaces $\mu_1$ and $\mu_2$ and the corresponding ranking classifier ${\mathcal{C}}$ for the one-dimensional example.  The entire input space $[0, 1]$ is divided into three parts, with ranking classifier equal to $1$ in the middle, and equal to $2$ otherwise.[]{data-label="fig:1d_fun"}](funcvalue_1d_2.png){width="50.00000%"}

Then the true ranking classifier ${\mathcal{C}}(x)$ is computed as $$\label{def_label1d}
{\mathcal{C}}(x) = \left\{ {\begin{array}{*{20}{l}}
    {2}& \quad \text{for } x \in [0,r_1] \cup [r_2,1], \\
    {1}& \quad \text{for } {r_1 < x < r_2, } \\
            \end{array}} \right.$$ where $r_1 \approx 0.3193, r_2 \approx 0.9279.$ We visualize the true responses $\mu_1$ and $\mu_2$ and the corresponding ranking classifier ${\mathcal{C}}$ in Figure \[fig:1d\_fun\]. 

We first investigate the performance of feed-forward NNs, and test them for the following four cases of training data generated on uniform grids or the points produced by sequential design. 

[|l|c|c|]{} Name of Method & Method to generate $x \in {\mathcal{X}}$ & Method to generate labels\
UNIF & uniform grids & True label $\arg\min_\ell \mu_\ell(x)$\
UNIF + NL & uniform grids & Noisy label $\arg\min_\ell y_\ell(x)$\
SD & sequential design & True label $\arg\min_\ell \mu_\ell(x)$\
SD + NL & sequential design & Noisy label $\arg\min_\ell y_\ell(x)$\

Let $M$ be the size of training data.  For a comprehensive study, we conduct our experiments under different $M = 128, 256, 512$. Points generated by sequential design use “Gap-SUR” method developed in [@HuLudkovski17], and are mainly concentrated near the boundaries $\partial {\mathcal{C}}_i$, namely, around $r_1$ and $r_2$, as well as the “fake” boundary $x=0$, where the two lines are quite close but do not touch each other.  Then labels are generated by taking the argmin of true surfaces $\mu_\ell$ or realizations $y_\ell$ of the noisy sampler $Y_\ell$ at those points $x^{1:M}$.

To focus on the performance of data designs in Table \[tbl:datadesign\], we fix the network architecture to be a feed-forward NN with two fully-connected hidden layers.  Number of neurons in each hidden layer is set at $M/8$. For this binary classification problem, the output layer contains one neuron and produces the probability of Surface $1$ being the minimum it believes, by using the sigmoid activation function.  The network is trained for 1500 epochs with updating each gradient using $M/2$ data.  One epoch is an iteration over the entire data.  We remark that all above settings can be altered for a suitable trade-off between accuracy and efficiency.  However, for a purpose of comparison, we fix them in the way we explained above.  Meanwhile, we do adjust the learning rate and other parameters in the optimizer, in order to better train the network within 1500 epochs. 

In deep learning, two numbers are of most importance, the training accuracy and the generalization accuracy.  The first one indicates how well the network learns from the training data set, calculated based on $M$ points, while the latter one measures the accuracy of the prediction for new locations $x \notin x^{1:M}$, calculated on a finer grid on ${\mathcal{X}}$. Also, note that the latter one is a discretized version of $1 - {\mathcal{L}}({\mathcal{C}}, {\mathcal{C}}_{dl})$ where ${\mathcal{L}}$ is the loss defined in with uniform measure.  For these two reasons, we report accuracies instead of loss in Table \[tbl:1d\] for different computational budget $M = 128, 256, 512$ and different designs listed in Table \[tbl:datadesign\]. 

[|l|cc|cc|cc|]{} & & &\
& Train.  Acc. &  Gen. Acc. &  Train.  Acc. &  Gen. Acc. &  Train.  Acc. &  Gen. Acc.\
UNIF & 99.9%& 99.7%& 99.9%&99.9%&99.9%& 99.9%\
UNIF + NL &81.25%&98.5%&79.3%&98.8%&81.0%&99.5%\
SD&99.5%&98.3%&96.1%&98.9%&98.1%& 99.5%\
SD + NL &64.1%&97.3%&57.2%&92.3%&58.2%&94.2%\

The first observation is, the usage of noisy labels decreases the training accuracy, evidenced by comparing UNIF to UNIF+NL; however, it influences much less on the generalization accuracy.  Ideally, when there are errors in the training data set, we want the NN to auto-detect these errors and avoid learning from them.  This is exactly the case in this example.  By a careful examination, the misclassified locations in the training data set are mainly mis-labeled points due to the low signal-to-noise ratio, with a small number of points around the boundary, which are originally hard to learn.  This can be understood in the sense that, although the training data with noisy labels do not contain $100\%$ accurate information, networks “learn” to minimize the effect of the wrong labels by not training them correctly.  Secondly, by comparing UNIF+NL to SD+NL, we observe that the usage of SD further decreases the training accuracy.  This is due to the fact that the input data of SD contain more errors, as points $x^{1:M}$ generated by SD are mostly concentrated around the boundaries $r_1 = 0.3193$, $r_2 = 0.9279$ and the fake boundary $x = 0$, where the signal-to-noise ratio is low, leading to a large number of mis-labeling points.  Thirdly, we observe that there exists a threshold on the proportion of error in training data so that they can be auto-detect and will not influence the network’s predicting accuracy.  For instance, comparing SD with SD+NL at $M = 256$, the generalization accuracy significantly decreases.  We interpret this phenomenon as the fact that there have been enough wrong labels which make the network believe they (the wrong labels) are the truth. 

Finally, we comment that, as increasing the budget for the simulation of training data set, the results are better in the UNIF case, which is consistent with common sense: the more data, the better the learning.  While in the SD case, there is a turning point in both training and generalization accuracy, *i.e.*, $64.1\% \to 57.2\% \to 58.2\%$, and $97.3\% \to 92.3\% \to 94.2\%$. This is because of the Gap-SUR criterion we use, where $x^{1:M}$ are sequentially selected by reducing stepwise uncertainty.  When adaptively grow $x^{1:M}$, the algorithm will mostly pick points around the boundaries first.  The additional budget from $M = 128$ to $M = 256$ mostly goes to the boundary points, which increases the percentage of wrong labels, leading to a decrease in accuracy.  Once the points there become saturated (the uncertainty reduction becomes very small), Gap-SUR favors locations that have large posterior variance, usually interior points of $\partial{\mathcal{C}}_i$. Therefore, the additional 256 points in $M = 512$ case go to interior points more than the boundary ones, which increases the accuracy. 

Below, we also plot the training and generalization accuracy versus epoch in Figure \[fig:1dacc\].  The predicted ranking classifiers and corresponding difference from true values are given in Figures \[fig:1d\] for UNIF, UNIF+NL, SD, and SD+NL using a size of $M=128$ training data. 

  ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![ The training and generalization accuracy versus epoch for UNIF, UNIF+NL, SD, SD+NL in the one-dimensional example, respectively. []{ data-label="fig:1dacc"}](trainacc_1d.png "fig:"){width="45.00000%"}   ![ The training and generalization accuracy versus epoch for UNIF, UNIF+NL, SD, SD+NL in the one-dimensional example, respectively. []{ data-label="fig:1dacc"}](genacc_1d.png "fig:"){width="45.00000%"}
  ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

One can also notice that, in Figure \[fig:1d\], the network predicts wrong classifiers not only near the boundaries but also at the faked boundary $x=0$ where the two response surfaces are close to each other.  This is because, the training data points generated by SD are often near the boundaries or faked boundaries, and using noisy labels will lead to the points near boundaries or faked boundaries having wrong classifiers, which makes the networks predict wrong classifiers at these places. 

Two-dimensional example
-----------------------

In this subsection, we further study the sensitivity of deep learning algorithms on noisy labels, sampling locations and budget by a two-dimensional (2D) example used in [@HuLudkovski17].  It treats a more complex setting with $L=5$ surfaces and a 2D input space ${\mathcal{X}}=[-2,2]^2$, with a constant homoscedastic observation noise ${\epsilon}_\ell(x_1,x_2) \sim \mathcal{N}(0, \sigma_\ell^2)$, $\sigma_\ell=0.5, \; \forall \ell=1,\cdots,5$. The specific response functions for each surface and true classifier ${\mathcal{C}}$ of problem is shown in Figure \[fig:2d\_fun\]. 

$$\begin{array}{lr}
                \hline
                \\[-0.8em]
                \text{Surface}& \text{Response}  \\ \hline\hline
                \\ [-0.8em]
                \mu_1(x_1,x_2) &  2-x_1^2 - 0.5 x_2^2 \\
                \\[-0.8em]
                \mu_2(x_1,x_2) &  2(x_1-1)^2 + 2x_2^2 -2 \\
                \\[-0.8em]
                \mu_3(x_1,x_2) &  2 \sin(2x_1)+2  \\
                \\[-0.8em]
                \mu_4(x_1,x_2) &  8(x_1-1)^2 + 8x_2^2 -3 \\
                \\[-0.8em]
                \mu_5(x_1,x_2) &  0.5(x_1+3)^2 +16x_2^2 -6  \\ \hline
                \end{array}$$

![ image](class_true_2d.png){width="90.00000%"}

\[fig:2d\_fun\]

[|l|cc|cc|cc|]{} & & &\
& Train.  Acc. &  Gen. Acc. &  Train.  Acc. &  Gen. Acc. &  Train.  Acc. &  Gen. Acc.\
UNIF &99.9% & 94.7%&99.7%&96.6%&99.5%& 97.7%\
UNIF + NL &98.4%&92.8%&93.2%&95.1%&90.8%&96%\
SD&96.9%&94.4%&96.1%&96.4%&96.1%& 97.4%\
SD + NL &82.0%&94.1%&71.8%&94.6%&66.8%&96.8%\

We perform the same four types of training data (cf.  Table \[tbl:datadesign\]) as in the 1D example, and show the results of accuracy in Table \[tbl:2d\].  We also plot the training and generalization accuracy versus epoch in Figure \[fig:2dacc\].  The predicted ranking classifiers and corresponding difference from true values are given in Figures \[fig:2d\] for UNIF, UNIF+NL, SD, and SD+NL using a size of $M=576$ training data.  These testing results show a consistent conclusion with the 1D example, [*i.e.*]{}, the generalization accuracy is not very sensitive to the noise in the training data set; using SD for generating sampling locations $x^{1:M}$ potentially decrease the training accuracy due to more errors in the learning data set, and increasing the budget $M$ will make it even lower before points around the boundaries get saturated. 

Moreover, we also implement the UNet architecture (right panel in Figure \[fig:arch\]) using $M=576$ uniform grid points with noisy labels, and show the predicted classifier in Figure \[fig:UNet\].  The UNet has a generalization accuracy of $96.44\%$, presenting a better performance than feed-forward NNs (corresponding to the $95.1\%$ in Table \[tbl:2d\]).  It is also visualized by comparing Figure \[fig:UNet\] to Figure \[fig:2d\] (b) (d). 

  ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![ The training and generalization accuracy versus epoch for UNIF, UNIF+NL, SD, SD+NL in the two-dimensional example, respectively. []{ data-label="fig:2dacc"}](trainacc_2d.png "fig:"){width="45.00000%"}   ![ The training and generalization accuracy versus epoch for UNIF, UNIF+NL, SD, SD+NL in the two-dimensional example, respectively. []{ data-label="fig:2dacc"}](genacc_2d.png "fig:"){width="45.00000%"}
  ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

![ Predicted 2-D ranking classifiers on ${\mathcal{X}}= [-2, 2]^2$ using UNet.  The solid black lines are the true classifier ${\mathcal{C}}(x_1, x_2)$, the colored regions indicates the estimated minimal index using $M = 576$ training data.[]{data-label="fig:UNet"}](class_unif_noise_2d_unet.png){width="60.00000%"}

Bermudan option pricing {#sec:Bermudan}
=======================

An important problem in computational finance is pricing Bermudan/American-type options.  It has been studied extensively in the literature, for instance, via regression methods [@Carriere96; @Longstaff; @tsitsiklis2001regression; @kohler2010review; @Belomestny11; @letourneau2014refining] and variance reduction [@juneja2009variance; @hepperger2013pricing; @jain2015stochastic], primal-dual formulation [@andersen2004primal; @broadie2008improved; @Bender11], adaptive experiment designs for optimal stopping [@GL13; @ludkovski2015kriging] and counter-finding [@lyu2018evaluating], to list a few. 

For Bermudan-type options, the buyer has the right to exercise at a set number of times.  Assume they are discretely spaced, denoted by $\{t_0 = 0, t_1, t_2, \ldots, t_{N-1}, t_N = T\}$ bounded by the maturity date $T$, the price is determined by the maximum expected payoff over all possible $t_i$. To maximize (or optimize) buyer’s profit, one wants to execute/stop the option in a way that the largest payoff will be received, based on the information known up to today.  Therefore, this can be formulated as an optimal stopping problem, and is typically solved by backward induction.  In other words, one first computes a value function at the expiration date, and then recursively works backward, computing value functions and making a decision on whether to execute for preceding periods.  At each possible executing time $t_i$, the decision space is small, containing only two elements ${\mathfrak{L}} = ${stop, continue}, which makes it a natural application of ranking problems.  Therefore, in this section, we apply the deep learning algorithms to price Bermudan-type options. 

Let $X_t \in {\mathcal{X}}\subset {\mathbb{R}}^d$ be the price of underlying assets, ${\mathcal{F}}_n = \sigma(X_{t_{0:n}})$ be the $\sigma-$algebra generated by $(X_{t_i})_{i=1}^n$ and ${\mathcal{S}}$ be the collection of all $({\mathcal{F}}_n)$ stopping times.  Then pricing Bermudan option is essentially to maximize the expected reward $h(\tau, X_\tau)$ over all stopping times $\tau \in {\mathcal{S}}$. Mathematically, denoting by $V(t,x)$ the value of such an option at time $t$ with current price $X_t = x$: $$V(t,x) := \sup_{\tau \geq t, \tau \in {\mathcal{S}}} {\mathbb{E}}_{t,x}[h(\tau, X_\tau)],$$ the price is given by $V(0,X_0)$. By dynamic programming, $$V(t_i,x) = \max\{h(t_i, x), C(t_i, x)\},$$ where $C(t_i, x)$ is the continuation value, corresponding to the action “[continue]{}” in ${\mathfrak{L}}$: $$\label{def_cont}
C(t_i, x) :=  {\mathbb{E}}_{t_i, x}[V(t_{i+1}, X_{t_{i+1}})]\},$$ and $h(t_i,x)$ is the immediate payoff if one chooses to exercise the option at $t_i$, related to the action “[stop]{}” in ${\mathfrak{L}}$. Denote by $\tau^\ast(t,x)$ the stopping time when the supremum is attained, it is identified by $$\{\tau^\ast(t_i,x) = t_i\} = \{x \in {\mathcal{X}}: h(t_i, x) \geq C(t_i,x)\}.$$ Using the above formulation, one can estimate $\tau^\ast$ recursively from $t_N$ to $t_0$.

Rephrasing it in terms of our ranking problem setup, fixing time $t_i$, the choice between “stop” or “continue” is equivalent to find ${\mathcal{C}}(t_i, x) := \arg\max \{\mu_{stop}(t_i, x), \mu_{cont}(t_i, x)\}$ over ${\mathcal{X}}$, a segmentation of the input space between continuation and stopping regions.  Here $\mu_{stop} = h$ can be evaluated deterministically, while closed-form formula for $ \mu_{cont} = C$ is typically not available, but accessible through simulations.  Moreover, its evaluation also depends on all further classifiers ${\mathcal{C}}(t_j, x)$, $i+1 \leq j \leq N$. To be more precise, for a given collection of estimated classifier $\hat{{\mathcal{C}}}(t_{i+1:N}, \cdot)$, define the pathwise stopping strategy: $$\label{def_tau}
 \hat{\tau}(t_i,x)(\omega) := \inf\{t_j > t_i: \hat{\mathcal{C}}(t_j, X_{t_j}(\omega)) = stop\} \wedge T,$$ for every path $X_{(\cdot)}(\omega)$ with initial position $X_{t_i} = x$. Now, by simulating $R$ independent paths $x^r_{t_{i:N}}$ starting from $x^r_{t_i} = x$, $r = 1, \ldots, R$, the continuation value is estimated by $$\label{def_approxcont}
\hat C(t_i, x) := \frac{1}{R} \sum_{r=1}^R h(\hat\tau(t_i, x_{(\cdot)}^r), x^r_{\hat{\tau}(t_i, x_{(\cdot)}^r)}),$$ producing the estimated classifier $\hat {\mathcal{C}}(t_i, \cdot)$ at location $x$ $$\begin{aligned}
\label{def_cal_fm}
 \hat{\mathcal{C}}(t_i, x) &:= \arg\max\{\mu_{stop}(t_i, x), Y_{cont}(t_i, x)\} , \\
 Y_{cont}(t_i, x) &:= C(t_i, x) + {\epsilon}_{cont}(t_i, x), \quad {\epsilon}_{cont} := \hat C - C. 
 \end{aligned}$$ The term ${\epsilon}_{cont} = \hat C - C$ summarizes the simulation noise from two approximations: the usage of estimated classifiers $\hat {\mathcal{C}}(t_{i+1:N}, \cdot)$ that determines the exercise strategy and the action of replacing the expectation in by the average over sample paths .  Once the decision maps $\hat {\mathcal{C}}(t_{1:N}, \cdot)$ are obtained, $V(0,X_0)$ is estimated on a out-of-sample set of $M'$ realizations of $X_{(\cdot)}$.

We use deep learning algorithms for the purpose of efficient and accurate learning of $\hat {\mathcal{C}}$ over the entire input ${\mathcal{X}}$ through finite samples.  Starting from the maturity time $t_N = T$, the learning is done recursively back to $t_0=0$, with each $\hat{{\mathcal{C}}}(t_i, \cdot)$ produced by a neural network.  In practice, one can improve the label quality in the training set by increasing the number of simulations $R$ which can reduce the magnitude of ${\epsilon}_{cont}$. However, we remark that errors are tolerated and $R$ does not need to be too large, as long as they do not affect the ordering of $Y_{cont}$ and $h$. We describe the pricing procedure in Algorithm \[def\_algorithm\]. 

$M$ = \# of sampling locations, $R$ = \# of sample paths at each grid, $M'$ = \# of out-of-sample paths for pricing, $X_0$ = initial price Define the classifier at maturity $t_N = T$: $\hat {\mathcal{C}}(t_N, x) = stop$ Generate sampling locations $x \in {\mathcal{X}}$ of size $M$ Sample $R$ paths $x^r_{t_{i:N}}$ with $x^r_{t_i} = x$, $r = 1, 
        \ldots, R$ Construct the pathwise stopping strategy $\hat{\tau}^r(t_i, x) := \inf\{t_j > t_i: \hat{\mathcal{C}}(t_j, x^r_{t_j}) = stop\}$ \[algo\_strategy\] Compute the continuation value by $\hat C(t_i, x) := \frac{1}{R} \sum_{r=1}^R h(\hat\tau^r(t_i, x), x^r_{\hat{\tau}^r(t_i,x)})$ \[algo\_cont\] $z(x) \leftarrow continue$ $z(x) \leftarrow stop$

Construct the classifier $\hat {\mathcal{C}}(t_i, \cdot)$ by training a neural network using $(x, z(x))$ of size $M$

Generate $M'$ out-of-sample paths $x^r_{t_{0:N}}$ with $x_{t_0}^r = X_0$, $r = 1, \ldots, M'$ Compute $\hat C(t_0, X_0)$ by repeating Step \[algo\_strategy\] and \[algo\_cont\] for $(t_0, X_0)$ Estimated price $\hat V(t_0, X_0) = \max\{h(t_0, X_0), \hat C(t_0, X_0)\}$.

Let us also remark that, this specific application of ranking response surfaces by deep learning actually has the same setup as the problem studied in [@BeChJe:18], where the backward recursive stopping decisions are approximated by a feed-forward NN.  In some sense, [@BeChJe:18] uses the feed-forward NN as interpolation to approximate the function with values $0$ and $1$ representing “continuation” and “stopping”.  In our work, by recasting the problem as image segmentation, one is allowed to use the more delicate architecture of neural networks ([*e.g.*]{} UNet), which increases computational efficiency. 

With all above efforts on reformulating Bermudan option pricing as ranking response surfaces, we perform a numerical study of 2-D max-Call $h(t,x) = e^{-rt}(\max(x_1, x_2) - K)_+$. The underlying assets $X = (X_1, X_2)$ are modeled by geometric Brownian motions, $${\,\mathrm{d}}X_i(t) = (r-\delta) X_i(t) {\,\mathrm{d}}t + \sigma X_i(t) {\,\mathrm{d}}W_i(t), \quad i = 1, 2,$$ where $(W_1, W_2)$ is a 2-D standard BM, with the parameters from [@andersen2004primal]: $$r = 5\%, \quad \delta = 10\%, \quad \sigma = 20\%, \quad X_0 = (90, 90), \quad K = 100, \quad T = 3, \quad N = 9, \quad t_i = i\frac{T}{N} .$$

From the numerical tests in Section \[sec:numerics\], one can notice that the generalization accuracy of UNIF (or UNIF+NL) is higher than that of SD (or SD+NL).  Moreover, implementation of the UNet on uniform grids is easier than using the points generated by sequential design.  Therefore, we will only use neural networks trained by data generated on uniform grids for computing the Bermudan option price.  Figure \[fig:fm\] shows the decision maps estimated recursively by deep learning algorithms for different time slices.  They are plotted backward in time, in the order of being generated.  The trivial decision map at $t_N = 3$ is not included.  A map at time $0$ is not needed, as we know the $X(0)$. $\hat{{\mathcal{C}}}$ are generated by a uniform $32\times 32$ grids on $[50, 150]^2$ with $R = 100$ replication at each location.  In the red area, the continuation value is higher, and thus it is optimal to keep holding the option; while in yellow regions, immediate rewards are higher, making it optimal to exercise right away.  The estimated price $\hat V(0, X(0))$ is 8.05 with a standard deviation 0.029, based on $M' = 160,000$ out-of-sample paths repeating 100 times.  This estimation is quite close to the true value of the option $8.08$, computed using a 2-D binomial lattice for this case [@Belomestny11]. 

  ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_0_3.png "fig:"){width="23.00000%"}   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_1_3.png "fig:"){width="23.00000%"}   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_2_3.png "fig:"){width="23.00000%"}   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_3_3.png "fig:"){width="23.00000%"}
   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_4_3.png "fig:"){width="23.00000%"}   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_5_3.png "fig:"){width="23.00000%"}   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_6_3.png "fig:"){width="23.00000%"}   ![ Deep learning of the decision maps $\hat {\mathcal{C}}(t_i, \cdot)$ with the training data generated by UNIF+NL (cf.  Table \[tbl:datadesign\]).  Black solid lines show the estimate boundaries of $\{\text{continue}, \text{stop}\}$. The colorbar indicates the probability that the neural network outputs for the decision of “continuation”.  Darker color means more confidence of the neural network feels about the classification.[]{data-label="fig:fm"}](class_unif_noise_fm_7_3.png "fig:"){width="23.00000%"}
  ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Conclusion and future works {#sec:conclusion}
===========================

By recasting ranking response surfaces as image segmentation, we propose to use deep neural networks (NNs) with various architectures ([*e.g.*]{}, feed-forward NNs, UNet) as computational tools.  Specifically, we consider labeling the entire input space using the index of the minimal surface, which segments the input space into distinct parts and allows one to use deep neural networks for efficient computation.  This gives an alternative way of efficiently solving the problem instead of using sequential design in our previous work [@HuLudkovski17].  In particular, deep learning algorithms provide a scalable model and makes the predicted results no more depend on the assumptions used in Gaussian process (GP) metamodels, for example, the assumptions on local/non-local kernels.  Moreover, considering ranking response surfaces as image segmentation allows one to use a broad class of neural networks([*e.g.*]{},  CNNs, UNet, and SegNet).  Compared to the work of computing Bermudan option price using feed-forward NNs [@BeChJe:18], the usage of networks with more delicate architectures ([*e.g.*]{} UNet) will improve the computational efficiency, although it is more difficult to analyze the convergence of networks rigorously.  A few examples including synthetic tests and the Bermudan option pricing are presented to show the success of deep neural networks in ranking response surfaces, which makes it possible to tackle more complicated problems, [*e.g.*]{}, optimal stopping game.  Noticing that samples around the partition boundaries usually has low signal-to-noise level and potentially increase the chance of mislabeling, a natural extension is to consider replication/batching at those locations.  Recent work [@binois2018replication] by Binois [*et al.*]{}  addresses this issue using GP metamodels, and we plan to study this problem by deep learning in the future.  Meanwhile, the theoretical convergence of networks with delicate structures is also interesting and needs to be analyzed in the future. 

Acknowledgment {#acknowledgment .unnumbered}
==============

We are grateful to Prof. Marcel Nutz for brining the reference [@BeChJe:18] into our attention, and Jay Roberts and Kyle Mylonakis for useful discussions. 

[^1]: Department of Statistics, Columbia University, New York, NY 10027-4690, [*rh2937@columbia.edu*]{}.