lemLemma propProposition thmTheorem rmkRemark assAssumption defnDefinition
proProblem ††thanks: Y. Dong was supported by the National Natural Science
Foundation of China (No. 12071333 & No. 12101458)

# Randomized Optimal Stopping Problem in Continuous time and reinforcement
learning algorithm

Yuchao Dong School of Mathematical Sciences, Tongji University, Shanghai
200092, China<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the optimal stopping problem in the so-called
exploratory framework, in which the agent takes actions randomly conditioning
on current state and an entropy-regularized term is added to the reward
functional. Such a transformation reduces the optimal stopping problem to a
standard optimal control problem. For the American put option model, we derive
the related HJB equation and prove its solvability. Furthermore, we give a
convergence rate of policy iteration and compare our solution to the classical
American put option problem. Our results indicate a balance between the
convergence rate and bias in the choice of the temperature constant. Based on
the theoretical analysis, a reinforcement learning algorithm is designed and
numerical results are demonstrated for several models.

###### keywords:

Optimal Stopping; Exploratory Framework; Reinforcement Learning

91G20, 91G60, 68T07, 35R35

##  1 Introduction

Reinforcement learning (RL, for short) is about how software agents choose
actions in an environment to achieve some goals or to maximize rewards.
Recently, it became one of the most active and fast developing areas of
machine learning, due to its success in playing go [20, 21], achieving human-
level performance in video games [14], controlling robotics [3], designing
autonomous driving [11] and so on. Applications of RL in the financial
industry such as algorithmic trading and portfolio management also have
attracted more attention in recent years, see [18, 7, 16, 15] for instance.

One distinguishing feature of reinforcement learning is that the model or
dynamic for the environment may not be known priorly. The agent is not told
what to do, but instead, discover which action yields the best result through
the interaction with the environment. This is a case of ”kill two birds with
one stone”: the agent’s actions serve both as a mean to explore (learn) and a
way to exploit (optimize). Since the exploration is inherently expensive in
terms of resources, time and opportunity, the agent must balance between
greedily exploiting what has been learned so far to choose actions that yield
near-term higher rewards and continuously exploring the environment to acquire
more information for potential long-term benefits. Extensive studies have been
carried out to find the best strategies for the trade-off between exploration
and exploitation. Most past works do not include exploration as a part of the
optimization objective, but treat exploration separately as an ad-hoc chosen
exogenous part, see [22]. On the other hand, [26, 17, 6] propose and applies
the discrete-time entropy-regularized RL formulation that incorporates
exploration into the optimization objective as a regularization term with a
trade-off weight imposed on the entropy on the exploring strategy. Recently,
Wang et al [24] proposed and developed a continuous-time entropy regularized
relaxed control framework. They called it an exploratory formulation, where
the actions are chosen to be probability measures. Moreover, the entropy of
the random action is added to the utility functional so as to encourage
exploration. They showed that the optimal distributions of the exploratory
control policies must be Gaussian for LQ control problem, thereby providing an
interpretation for the Gaussian exploration widely used both in RL algorithm
design and in practice, see [17]

In this paper, one motivation is to extend the exploratory framework to the
optimal stopping problem. The classical decision problem of optimal stopping
has found a amazing range of applications from finance, statistics, marketing,
phase transitions to engineering. In many cases, the state space is decomposed
into stopping region and continue region and the optimal stopping strategy is
to stop whence the state hits the stopping region. These regions are separated
by graph of a function which is also called stopping boundary. Theoretical
analysis indicates that this boundary is closely related to the value function
of the problem. In low dimensions, one can accurately compute the boundary by
methods based on PDE and dynamic programming. In high dimensions, one faces
the curse of dimensionality and people resort to machine learning techniques.

For machine learning method, neural networks are used to approximate either
the stopping time [1] or the stopping boundary [19]. Gradient descent is the
usual method for finding the optimal parameters. However, it is not possible
to apply gradient descent directly over these ’stop-or-go’ strategies as the
lack of smoothness. Thus, a soft stopping rule or fuzzy stopping boundary is
used during the learning. In some sense, it means that the agent stops with a
probability related to the distance to the boundary, see [19]. Then, one
natural question is that what is the effect of such fuzziness on the learning
procedure and obtained strategy.

Our major contributions are summarized as follows.

  1. (i)

We extend the exploratory framework to the optimal stopping problem. The
randomness in the strategy is modelled by introducing an additional state,
which represents the surviving probability in some sense. Such a
transformation reduces the optimal stopping problem to a standard optimal
control problem.

  2. (ii)

The reduction to standard optimal control problem gives us mathematical tools
for theoretical analysis. We derive the related HJB equation and prove its
solvability. Furthermore, we give a convergence rate of policy iteration (see
Theorem 3) and the comparison to classical optimal stopping problem (see
Theorem 3.2 and 3.3). These results give some quantitative answers to our
previous question on the effect of fuzziness.

  3. (iii)

We design an RL algorithm for optimal stopping problem. Although the
theoretical analysis is under American put option model, the algorithm is
applicable for general settings. We demonstrate numerical results for several
models.

The paper is organized as follows. In Section 2, we introduce the exploratory
formulation. Section 3 contains the related analytical results on policy
iteration and comparison with classical optimal stopping problem. We design a
reinforcement learning algorithm and demonstrate some numerical results in
Section 4. Finally, all the detailed proofs are put in Section 6.

##  2 Problem Formulation

For theoretical analysis, we mainly focus on the American put option problem
with one risky asset. Under risk neutral measure, the stock price $S_{t}$
satisfies the following

$dS_{t}=S_{t}\left[rdt+\sigma dW_{t}\right],$

with $r$ and $\sigma$ representing risky-free rate and volatility of the stock
respectively. Denote by $\mathbb{F}=\\{\mathcal{F}_{t}\\}_{0\leq t\leq T}$ the
filtration generated by Brownian motion $W$. The price of an American put
option is related to an optimal stopping problem, i.e. to choose a stopping
time $\tau^{*}$ such that

$\mathbb{E}\left[e^{-r\tau^{*}}(K-S_{\tau^{*}})^{+}\right]=\sup_{\tau\in\mathcal{T}[0,T]}\mathbb{E}\left[e^{-r\tau}(K-S_{\tau})^{+}\right],$

where $\mathcal{T}[0,T]$ is the totality of all the stopping time less than
$T$. It is well-known that, for such kind problem, the state space can be
decomposed into two regions: continue and stopping region, and the optimal
stopping strategy is to execute the option whenever state process hits
stopping region.

Notations For any region $\Omega$, $C(\Omega)$ represents the set of
continuous functions defined on $\Omega$. $C_{b}(\Omega)$ is the totality of
bounded continuous functions equipped with the supreme norm
$\|\cdot\|_{\infty}$. $C^{2+\alpha,1+\alpha}(\mathbb{R}\times[0,T))$ presents
a subset of $C(\mathbb{R}\times[0,T))$ with functions that are $\alpha$-Hölder
continuous up to second derivative in space and first derivative in time. In
this paper, we use $C$ to represent a constant, but may be different from line
to line.

###  2.1 Exploratory Formulation

In the so-called exploratory framework, the investor should choose her
strategy randomly. In our case, she flip a biased coin to decide whether to
execute or continue the option. This biased coin should be our control. For
classical stochastic control problems, such a framework means that the control
should be distribution-valued and is closely related to the relaxed control
theory, see [4] and [25] for details. However, the extension to optimal
stopping problem seems not to be straightforward. To our best knowledge, there
seem no papers on the ’relaxed’ optimal stopping problem in continuous time.

Instead of considering one person, we treat the agent as a population of
investors. The randomness in strategy means that, facing the same situation,
part of the population choose to execute while the others do not. As a whole,
the population of remaining investors decreases by a rate. This rate is the
control variable in our model. For the mathematical setup, let us denote by
$p_{t}$ the population of the investors that still hold the option at time
$t$. Then, its dynamic can be modeled as

$dp_{t}=-\pi_{t}p_{t}dt,p_{0}=1.$

Here $\pi_{t}$ represent the fraction of current population that choose to
execute. Then, at time $T$, the accumulated expected wealth of the whole
population will be

$\mathbb{E}\left[\int_{0}^{T}e^{-rt}g(S_{t})\pi_{t}p_{t}dt+e^{-rT}g(S_{T})p_{T}\right]$

with $g(S)=(K-S)^{+}$.

Part of our goal is to maximize the accumulated wealth. If one tries to
optimize this goal solely, it finds that the resulting strategy will be
deterministic, i.e. all the population choose to execute at the same time.
This goes back to the classical American option problem. Similar to the
framework of [24], we have to add a term in the reward functional to encourage
randomness/exploration. In previous studies, this term is related to entropy.
What is the ’entropy term’ in our case? To give a hint, let us consider the
discrete-time case and take the limit. In time interval $[t,t+\Delta t]$,
there will be a fraction of $\pi_{t}\Delta t$ that choose to execute and a
fraction of $(1-\pi_{t}\Delta t)$ choose to hold. Then, the corresponding
entropy will be

$-\pi_{t}\Delta t\log{\pi_{t}\Delta t}-(1-\pi_{t}\Delta
t)\log{(1-\pi_{t}\Delta t)}=-\pi_{t}\Delta t\log\Delta
t+(\pi_{t}-\pi_{t}\log\pi_{t})\Delta t+o(\Delta t).$

Summing the entropy over all intervals, the $\Delta t\log\Delta t$ term
diverges no matter what strategy we choose and the $o(\Delta t)$ term
disappears. These two terms are not of particular interest. This motives us to
consider the following reward functional

(2.1) $\mathbb{E}\left[\int_{0}^{T}e^{-rt}g(S_{t})\pi_{t}p_{t}+\lambda
e^{-rt}R(\pi_{t})p_{t}dt+e^{-rT}g(S_{T})p_{T}\right]$

with $R(\pi)=\pi-\pi\log\pi$ and $\lambda$ being the temperature constant.

To sum up, an admissible control $\\{\pi_{t}\\}_{t}$ is a positive
$\mathbb{F}$-adapted process. The controlled dynamic is

$dp_{t}=-\pi_{t}p_{t}dt,p_{0}=1,$

and

$dS_{t}=S_{t}\left[rdt+\sigma dW_{t}\right].$

The optimal control problem is to maximize

$J(\pi)=\mathbb{E}\left[\int_{0}^{T}e^{-rt}g(S_{t})\pi_{t}p_{t}+\lambda
e^{-rt}R(\pi_{t})p_{t}dt+e^{-rT}g(S_{T})p_{T}\right]$

over all admissible control $\pi$.

###  2.2 An Equivalent Formulation

In this subsection, we introduce an equivalent formulation for our model. Let
$\Theta$ be a random variable, which is exponential distributed and
independent from Brownian motion. Given $\\{\pi_{t}\\}_{t}$, define a random
time $\tau$ as

$\tau:=\inf\left\\{t\in[0,T]:\int_{0}^{t}\pi_{s}ds\geq\Theta\right\\}{\bigwedge}T,$

where we adopt the convention that the infimum of an empty set is infinity.
This construction is referred as the Cox process model, which has been
extensively studied in credit risk modelling. The readers are referred to [9]
for details. One key feature is that, given the $\sigma$-algebra
$\mathcal{F}_{t}$, the conditional distribution function of $\tau$ is

(2.2) $P(\tau>s|{\mathcal{F}}_{t})=\exp(-\int_{0}^{s}\pi_{u}du)=p_{s},$

for $s\leq t$. Moreover, from [9, Lemma 7.3.4.3], if $h$ is an
$\mathbb{F}$-predictable bounded process, then

$\mathbb{E}\left[h_{\tau\wedge
t}\right]=\mathbb{E}\left[\int_{0}^{T}h_{u}\pi_{u}p_{u}du+h_{T}p_{T}\right].$

Hence, we see that the reward functional (2.1) is equivalent to

$\mathbb{E}\left[e^{-r\tau}g(S_{\tau})+\lambda\int_{0}^{\tau}e^{-rt}R(\pi_{t})dt\right].$

From this formulation, we can treat the random time $\tau$ as the execution
time. Note that $\tau$ is not a $\mathbb{F}$-stopping time. Hence, given
$\mathcal{F}_{t}$, one can not know whether or not the execution has happened.
In fact, conditioned on that the execution does not take place before time $t$
and given $\mathcal{F}_{t}$, the probability that $\tau\in[t,t+\Delta t]$ is
$\pi_{t}\Delta t$. In this point of view, our model resembles to the
exploratory framework of [24] that the investors choose to act randomly.

##  3 HJB equation for the related problem

It is straightforward to derive that the optimal value function
$\tilde{V}(S,p,t)$ satisfies the following HJB equation

$\partial_{t}\tilde{V}+\mathcal{L}_{S}\tilde{V}+\sup_{\pi\in[0,\infty)}-\pi
p\partial_{p}\tilde{V}+g(S)\pi p+\lambda R(\pi)p=0,V(S,p,T)=g(S)p.$

with
$\mathcal{L}_{s}=\frac{1}{2}\sigma^{2}S^{2}\partial_{SS}+rS\partial_{S}-r$. We
make the ansatz that $\tilde{V}(S,p,t)=pV(S,t)$. Then, we have

(3.1) $\partial_{t}V+\mathcal{L}_{S}V+\sup_{\pi\in[0,\infty)}(g-V)\pi+\lambda
R(\pi)=0,V(S,T)=g(S).$

To emphasize its dependence on $\lambda$, we denote by $V^{\lambda}$ as the
solution of (3.1) and still call it the optimal value function. From the
optimality condition, the optimal intensity should be
$\bar{\pi}^{\lambda}:=\exp(-\frac{V^{\lambda}-g}{\lambda})$. Then, we can
rewrite (3.1) as

(3.2)
$\partial_{t}V^{\lambda}+\mathcal{L}_{S}V^{\lambda}+\lambda\exp(-\frac{V^{\lambda}-g}{\lambda})=0,V^{\lambda}(S,T)=g(S).$

Finally, let $S=e^{x}$ and $u^{\lambda}(x,t)=V^{\lambda}(S,t)$. It is easy to
see that $u^{\lambda}$ solves

(3.3)
$\partial_{t}u^{\lambda}+\mathcal{L}_{x}u^{\lambda}+\lambda\exp(-\frac{u^{\lambda}-h}{\lambda})=0,u^{\lambda}(x,T)=h(x),$

with
$\mathcal{L}_{x}=\frac{1}{2}\sigma^{2}\partial_{xx}+(r-\frac{1}{2}\sigma^{2})\partial_{x}-r$
and $h(x)=g(e^{x})$. For this equation, we shall have the following theorem
for the solvability.

######  Theorem 1.

For any $\lambda>0$, there exists a unique classical solution $u^{\lambda}\in
C^{2+\alpha,1+\alpha}_{loc}(\mathbb{R}\times[0,T))\cap
C(\mathbb{R}\times[0,T])$ for (3.3). Moreover,

(3.4) $0\leq u^{\lambda}(t,x)\leq K+\lambda(T-t).$

In this paper, we adopt the terminology from RL literature and call the value
function of an optimal control problem as optimal value function. Given a
feedback strategy $\pi$, the expected reward functional under this strategy is
called the value function and denoted as $V^{\pi}(p,S,t)$. We can make a
similar ansatz as before that $V^{\pi}(p,S,t)=pu^{\pi}(\log S,t)$ with
$u^{\pi}(x,t)$ being a function defined on $\mathbb{R}\times[0,T]$. With a
little bit of abuse of terminology, we also call $u^{\pi}$ the value function.

###  3.1 Policy Iteration

In reinforcement learning, one method to learn the optimal strategy is policy
iteration in which the optimal strategy is approximated by iteratively
updating. More precisely, given a feedback strategy $\pi^{n}(x,t)$, the
corresponding value function $u^{n}(x,t)$ (see Remark 3) satisfies

(3.5)
$\partial_{t}u^{n}+\mathcal{L}_{x}u^{n}+H(x,\pi^{n}(x,t),u^{n})=0,u^{n}(x,T)=h(x),$

with the Hamiltonian $H$ being defined as

$H(x,\pi,u)=(h(x)-u)\pi+\lambda R(\pi).$

Having a value function $u^{n}$, one can construct a feedback strategy
$\pi^{n+1}$ as

(3.6)
$\pi^{n+1}(x,t)=\mathop{\text{argmax}}_{\pi\in(0,\infty)}H(x,\pi,u^{n}(x,t))=\exp(-\frac{u^{n}(x,t)-h(x)}{\lambda})$

We continue this iteration and obtain a sequence of pairs of strategy and
value function. The following theorem states that the performance of the
policies is improved during the iteration.

######  Theorem 2.

Give any initial guess $u^{0}\in C_{b}(\mathbb{R})$ for the optimal value
function. $\\{u^{n},\pi^{n}\\}_{n=1,2,...}$ are defined iteratively according
to (3.6) and (3.5). Then, we have that $u^{\lambda}\geq u^{n+1}\geq u^{n}$,
for $n=1,2,...$.

One should expect that the value functions $\\{u^{n}\\}$ converge to the
optimal value function $u^{\lambda}$. This is indeed the case. Furthermore, we
can give an estimation for the convergence speed of value iteration.

######  Theorem 3.

Define by $M:=\|(h-u^{1})^{+}\|_{\infty}$. There exists a constant $C$
independent of $\lambda$ such that $\|u^{n+1}-u^{\lambda}\|_{\infty}\leq
C^{n}\frac{T^{n}}{n!}\exp(n(\frac{M}{\lambda}+rT))$.

  1. i)

In [10], the authors proved an exponential convergence rate $Cq^{n}$ for
policy iteration. Our rate here is faster than exponential with respect to
$n$. We think that the main reason for this is that the optimal $\pi$ smoothly
depends on other variables of the Hamiltonian $H$, see (3.6). For general
optimal control problem, such a property does not hold.

  2. ii)

Note that $u^{1}$ is defined by (3.5). Thus, $M$ should also depend on
$\lambda$. In fact, one can get an estimation of $M$, which is decreasing with
respect to $\lambda$. But, for the special initial value function $u^{0}=g$,
$M$ is independent of $\lambda$.

###  3.2 Comparison between classical problem and randomized problem

For the classical American put option pricing problem, it is well-known that
the option price is given by $u^{*}(\log S,t)$ with the function $u^{*}$ being
the soluion of the following variational inequality

(3.7)
$\min\\{-\partial_{t}u^{*}-\mathcal{L}_{x}u^{*},u^{*}(x,t)-h(x)\\}=0,u(x,T)=h(x).$

It is easy to see that (3.7) is formally the limit of (3.2) as $\lambda$ going
to $0$. In other words, (3.2) can be seen as a penalized equation for (3.7).
Thus, it is reasonable to believe that $u^{\lambda}$ should converge to
$u^{*}$ as $\lambda$ going to $0$. To prove this, the following lemma is
needed.

######  Lemma 3.1.

We have, for some constant $C$,

$u^{\lambda}(x,t)\geq h(x)-\lambda\log\frac{CrK}{\lambda}.$

Then, we have the following theorem.

######  Theorem 3.2.

We have

$u^{\lambda}(x,t)-\lambda\log(1+(T-t))\leq u^{*}(x,t)\leq
u^{\lambda}(x,t)+\lambda\log\frac{CrK}{\lambda},$

where $C$ is the constant in Lemma 3.1.

Having the value function $u^{\lambda}$ or $V^{\lambda}$ equivalently, how one
can construct a stopping strategy for the optimal stopping problem? Maybe the
most straight forward way is to execute at the stopping time

$\tau^{\lambda}:=\inf\\{t|V^{\lambda}(S_{t},t)\leq g(S_{t})\\}\wedge T.$

Clearly, $\tau^{\lambda}$ is sub-optimal for the American option problem. Note
that if we replace $V^{\lambda}$ by $V^{*}$, then the corresponding stopping
time $\tau^{*}$ is optimal. We have shown that $V^{\lambda}$ will converge to
$V^{*}$. Thus, the performance of $\tau^{\lambda}$ should be close to the
optimal. As a consequence of Theorem 3.2, we are able to quantify the
difference.

######  Theorem 3.3.

$\mathbb{E}\left[e^{-r\tau^{\lambda}}g(S_{\tau^{\lambda}})\right]\geq\mathbb{E}\left[e^{-r\tau^{*}}g(S_{\tau^{*}})\right]-O(\lambda\log\frac{1}{\lambda})$.

  1. i)

Recently, Tang et al [23] studied the exploratory HJB equation arising from
the entropy-regularized exploratory control problem. For some special case,
they also proved an convergence rate of $O(-\lambda\log\lambda)$ for the value
functions as $\lambda\rightarrow 0^{+}$.

  2. ii)

We show that the convergence rate is controlled by
$\frac{(CT)^{n}}{n!}\exp(\frac{nM}{\lambda})$ which is decreasing in
$\lambda$. On the other hand, the bias is dominated by
$O(-\lambda\log(\lambda))$. This implies a balance between convergence speed
and bias in the choice of $\lambda$.

###  3.3 Numerical Solution for (3.3)

In this subsection, we numerically solve (3.3) for illustration. To deal with
the nonlinear term, we adopt the method in [5] which combines finite-
difference method with generalized Newton iteration. The grid of mesh points
is taken to be $(t_{i},x_{j})=(i\Delta t,j\Delta x)$ with $i=0,1,...,M$ and
$j=0,\pm 1,...,\pm N$, where $M=\frac{T}{\Delta t}$. Let $U_{i,j}$ be the
discrete solution at mesh point $(t_{i},x_{j})$ and $A$ be the discretization
of the second order operator $-\mathcal{L}_{x}$. The iteration is as follows

Algorithm 1 Finite-difference Iterative Algorithm

$\Delta t,\Delta x$, $\lambda$ and tolerance $tol$

Compute $A$

Initialize $U_{M,j}=(K-e^{x_{j}})^{+}$

for $t=M-1,M-2,...,1,0$ do

Set $U^{0}_{\cdot}=U_{t-1,\cdot}$

for $k=1,2,3,...$ do

Solve the linear equation  $\frac{1}{\Delta
t}(U^{k}_{j}-U_{t+1,j})+[AU^{k}_{\cdot}]_{j}=\lambda\exp(-\frac{U^{k-1}_{j}-U_{0,j}}{\lambda})+\exp(-\frac{U^{k-1}_{j}-U_{0,j}}{\lambda})(U^{k-1}_{j}-U^{k}_{j})$
for $j=0,\pm 1,...,\pm(N-1)$, and  $U^{k}_{\pm N}=(K-e^{x_{\pm N}})^{+}.$

If
$\frac{\|U^{k}_{\cdot}-U^{k-1}_{\cdot}\|_{\infty}}{\max\\{1,\|U^{k-1}_{\cdot}\|_{\infty}\\}}<tol$,
Quit

end for

Set $U_{t,\cdot}=U^{k}_{\cdot}$.

end for

For numerical experiment, we set $r=5\%,\sigma=0.4,k=1,T=1$ and
$\lambda=0.005$. In Fig 1, we plot the value function $u^{\lambda}$ at time
$t=0$ and compare it with $u^{*}$, which is computed by using penalty (see
[5]). The difference between two functions is very small. In fact, numerical
result shows that the maximum error is about $0.0023$ which is of the same
scale as $-\lambda\log\lambda=0.0038$.

Figure 1: Value functions $u^{\lambda}$ and $u^{*}$ at $t=0$

In Figure 2, we plot continue regions for $u^{\lambda}$ and $u^{*}$. It is
easy to see that the regions are of similar shape and both separated by
stopping boundary.

(a) $\\{u^{\lambda}>h\\}$

(b) $\\{u^{*}>h\\}$

Figure 2: Continue regions for two functions

For further comparison, we plot these two boundaries in Figure 3. One can
observe that the stopping boundary of $u^{*}$ is lower than that of
$u^{\lambda}$. This is probably due to the fact that the investor is
compensated by the entropy-regularized term and thus tends to be continue when
the price is relatively higher.

Figure 3: Comparison of the stopping boundaries

##  4 Reinforcement Learning Algorithm

In this section, we propose an reinforcement learning algorithm for the
optimal stopping problem. Note that our formulation transforms the optimal
stopping problem into a standard optimal control problem. Thus, we could use
well-developed reinforcement learning algorithms to learn the execution
strategy from the data. In this paper, we adopt an algorithm based on policy
iteration. It consists of two iterating steps: policy evaluation and policy
update.

###  4.1 Policy Iteration

In numerical implementation, we discretize the time interval $[0,T]$ into $L$
points: $0=t_{0}<t_{1}<...<t_{L}=T$ with equal distance $\Delta t$. In policy
iteration step, our task is to calculate the value function $V^{\pi}$ for a
given feedback policy $\pi=\pi(S,t)$. It is clear that $V^{\pi}(S,T)=g(S)$. At
other point $t<T$, it is characterized by the PDE:

$\partial_{t}V^{\pi}+\mathcal{L}_{S}V^{\pi}+(g-V^{\pi})\pi+\lambda R(\pi)=0.$

One can not direct compute this equation as we assume that the model
information is not available. Instead, we shall use a parameterized function
$V_{\theta}(\cdot)$ to approximate the value function $V^{\pi}(\cdot,t)$ with
a data set. Denote by $\theta^{l}$ the corresponding parameters at time
$t_{l}$. For reinforcement learning algorithm, the available data are samples
of the stock prices $\\{S^{m}_{t_{l}}\\}_{l=0,1,...,L,m=1,2,...,M}$. Given a
policy $\pi=\pi(S,t)$, one can calculate the state $p$ at time point $t_{l}$
iteratively by the following rule:

$p^{m}_{t_{l+1}}=\left(1-\pi(t_{l},S^{m}_{t_{l}})\Delta
t\right)p^{m}_{t_{l}},p^{m}_{0}=1.$

From Itô-formula, we have that

(4.1)
$\begin{split}&\mathbb{E}\left[\int_{t_{l}}^{t_{l+1}}e^{-ru}g(S_{u})\pi_{u}p_{u}+\lambda
e^{-ru}R(\pi_{u})p_{u}du+e^{-rt_{l+1}}V^{\pi}(S_{t_{l+1}},t_{l+1})p_{t_{l+1}}\big{|}\mathcal{F}_{t_{l}}\right]\\\
=&e^{-rt_{l}}V^{\pi}(S_{t_{l}},t_{l})p_{t_{l}}.\end{split}$

Recall that conditional expectation can be treated as an $L^{2}$-projection in
certain Hilbert space. This motivates us to choose $\theta^{l}$ that minimizes
the following quantity

$\sum^{M}_{m=1}\left(g(S^{m}_{t_{l}})\pi^{m}_{t_{l}}p^{m}_{t_{l}}\Delta
t+\lambda R(\pi^{m}_{t_{l}})p^{m}_{t_{l}}\Delta
t+e^{-r\Delta}V_{\theta^{l+1}}(S^{m}_{t_{l+1}})p^{m}_{t_{l+1}}-V_{\theta^{l}}(S^{m}_{t_{l}})p^{m}_{t_{l}}\right)^{2}.$

If we subtract $p_{t_{l}}$ on both sides of (4.1), one can propose
minimization of a similar term

(4.2) $\delta_{l}:=\sum_{m=1}^{M}\left(g(S^{m}_{t_{l}})\pi^{m}_{t_{l}}\Delta
t+\lambda R(\pi^{m}_{t_{l}})\Delta
t+e^{-r\Delta}V_{\theta^{l+1}}(S^{m}_{t_{l+1}})(1-\pi^{m}_{t_{l}}\Delta
t)-V_{\theta^{l}}(S^{m}_{t_{l}})\right)^{2},$

which is simpler than previous without the need to compute $p_{t_{l}}$. This
term is also called TD-error in the context of RL, see [22]. During each
iteration, one can update $\theta^{l}$ by taking one gradient descent step.

In the policy update step, having calculate value function $V^{\pi}$, our task
is to give an improvement of $\pi$. In general, this can be obtained by the
optimality condition in the HJB equation, which involves another optimization
problem. However, in our problem, we see that the minimization problem can be
explicitly solved as in (3.6). This greatly simplifies the policy update
procedure.

To summarize, we propose the following algorithm

Algorithm 2 Policy Iteration for Optimal Stopping Problem

Number of Iterations $N$, Batch Size $M$, Learning Rate $lr$

for $n=1,2,...,N$ do

Generate a batch of stock price
$\\{S^{m}_{t_{l}}\\}_{l=0,1,...,L,m=1,2,...,M}$ with batch size $M$

for $t=L-1,L-2,...,0$ do

Calculate
$\pi^{m}_{t_{l}}=\exp(-\frac{V_{\theta^{l}}(S^{m}_{t_{l}})-g(S^{m}_{t_{l}})}{\lambda})$

Calculate the TD-error $\delta_{h}$ according to (4.2)

Update $\theta_{l}$ by taking one gradient descent step on $\delta_{l}$ with
learning rate $lr$

end for

end for

###  4.2 Numerical Examples

In this subsection, we shall present some numerical examples for our RL
algorithm. Although our theoretical analysis is based on American put option
model, the algorithm is applicable for other models.

####  4.2.1 American Put Option

We consider a standard American put option with
$s_{0}=K=40,r=6\%,\sigma=40\%$. The price has been computed by Becker et al
[2] as $5.311$. We use previous RL algorithm to compute the price. Choose
$L=50$. Instead of approximating the value function by neural networks
directly, we find that it is more efficient to approximate it by the payoff
$g$ plus a neural network. The neural network that we employ consists of $2$
hidden layers with ReLU activation function. In additional to stock price, we
also take the payoff of the option as input of the neural network. The width
of hidden layers is $21$. The training procedure consists of $N=3000$ steps
with a batch size of $M=2^{10}$. We also generate a test data set with size
$2^{18}$. Every $10$ steps, we test the learned strategy on the test data set
to get an estimation $\mathcal{P}$ of the expected reward. The relative error
is computed as $\frac{|\mathcal{P}-5.311|}{5.311}$.

To compare the effect for different $\lambda$, we train three neural network
with $\lambda=10$,$10^{-1}$,$10^{-4}$ at the same time. The final performance
is $5.067,5.270,5.296$ respectively. The learning curves are plotted in Figure
4. It clearly shows the balance between convergence speed and bias. With a
larger $\lambda$, the learning curve tends to decrease and converge earlier.
But, this also leads to a larger bias for the final performance.

Figure 4: Learning Curves for different $\lambda$

####  4.2.2 Bermudan Max-Call Option

Bermudan max-call are one of the most studied examples in the numerical
literature on optimal stopping problem, see, for example, [13] and references
therein. The payment is decided by the maximum of $d$ underlying assets. More
precisely, the risk neutral dynamics of the assets are characterized by a
multi-dimensional Black-Scholes model:

$S^{i}_{t}=S_{0}^{i}\exp(\big{(}r-\delta_{i}-\frac{\sigma^{2}_{i}}{2}\big{)}t+\sigma^{i}W^{i}_{t}),i=1,2,...,d,$

for initial prices $S_{0}^{i}\in(0,\infty)$, risk free rate $r>0$, dividend
rates $\delta_{i}>0$, volatilities $\sigma_{i}>0$ and a $d$-dimensional
Brownian motion with constant correlations $\rho_{ij}$ between components
$W^{i}$ and $W^{j}$. A Bermudan max-call option on $S^{1},S^{2},...,S^{d}$ has
payoff $(\max_{i}S^{i}_{t}-K)^{+}$. In the numerical examples, the option can
be executed by at any time of a time grid $0=t_{0}<t_{1}<...<t_{N}=T$. Then,
the price of the option can be give as

$\sup_{\tau}\mathbb{E}\left[e^{-r\tau}(\max_{i}S^{i}_{\tau}-K)^{+}\right].$

We employ the same architecture of the neural network as in American put
option case. The width of the hidden layer is taken to be $d+20$. The training
procedure consists of $N=20000$ steps with a batch size $M=2^{10}$. For the
case $d=500$, we need $N=25000$ steps. The test data set is of the size
$2^{18}.$ We set the temperature constant $\lambda=10^{-2}$. For the
coefficients of the model, we consider two cases and compare the results with
that in [1].

Symmetric Case
We first consider a symmetric case, where
$S^{i}_{0}=s_{0},\delta_{i}=\delta,\sigma_{i}=\sigma$ for $i=1,2,...,d$ and
$\rho_{ij}=\rho$. The results are represented in Table 1(a).

Asymmetric Case
We next consider an asymmetric case. All the coefficients except $\sigma_{i}$
are the same as in symmetric case. For $d<5$, we set
$\sigma_{i}=0.08+0.32\times(i-1)/(d-1),i=1,2...,d$. For $d>5$,
$\sigma_{i}=0.1+i/(2d),i=1,2,...,d$. The results are represented in Table
1(b).

Table 1: Summary result for Bermudan max-Call option with
$r=5\%,\delta=10\%,\sigma=20\%,\rho=0,K=100,N=9$.

$d$ | $s_{0}$ | Our Method |  Price in [1]
---|---|---|---
2 | 90 | 8.065 | 8.074
2 | 100 | 13.852 | 13.903
2 | 110 | 21.332 | 21.349
5 | 90 | 16.620 | 16.644
5 | 100 | 26.083 | 26.159
5 | 110 | 36.608 | 36.772
10 | 90 | 26.168 | 26.240
10 | 100 | 38.257 | 38.337
10 | 110 | 50.761 | 50.886
50 | 90 | 53.844 | 54.057
50 | 100 | 69.539 | 69.736
50 | 110 | 85.156 | 85.463
100 | 90 | 66.340 | 66.556
100 | 100 | 83.299 | 83.584
100 | 110 | 100.375 | 100.663
200 | 90 | 79.086 | 79.174
200 | 100 | 97.871 | 97.612
200 | 110 | 115.989 | 116.088
500 | 90 | 95.588 | 96.147
500 | 100 | 116.086 | 116.425
500 | 110 | 136.749 | 136.765
(a) Symmetric Case

$d$ | $s_{0}$ | Our Method |  Price in [1]
---|---|---|---
2 | 90 | 14.312 | 14.339
2 | 100 | 19.799 | 19.808
2 | 110 | 27.0529 | 27.158
5 | 90 | 27.684 | 27.662
5 | 100 | 37.984 | 37.985
5 | 110 | 49.265 | 49.499
10 | 90 | 85.712 | 85.987
10 | 100 | 104.462 | 104.741
10 | 110 | 123.363 | 123.745
50 | 90 | 196.245 | 196.321
50 | 100 | 277.303 | 277.886
50 | 110 | 259.114 | 259.321
100 | 90 | 263.522 | 263.579
100 | 100 | 302.086 | 302.765
100 | 110 | 341.463 | 341.575
200 | 90 | 344.165 | 345.146
200 | 100 | 392.225 | 392.958
200 | 110 | 439.741 | 440.815
500 | 90 | 475.684 | 477.102
500 | 100 | 538.042 | 539.577
500 | 110 | 601.230 | 602.252
(b) Asymmetric Case

####  4.2.3 Optimal Stopping for fractional Brownian Motions

In this part, we consider a optimal stopping for fractional Brownian motions.
A fractional Brownian motion with Hurst parameter $H\in(0,1]$ is a continuous
centered Gaussian process $(W^{H}_{t})_{t\geq 0}$ with covariance

$\mathbb{E}\left[W^{H}_{t}W^{H}_{s}\right]=\frac{1}{2}\left(|t|^{H}+|s|^{H}-|s-t|^{H}\right).$

For $H=1/2$, $W^{H}$ is a standard Brownian motion. But, when
$H\neq\frac{1}{2}$, it is neither a martingale nor a Markov process. We want
ot approximate the supreme

$\sup_{0\leq\tau\leq 1}\mathbb{E}\left[W^{H}_{\tau}\right],$

over all $W^{H}$-stopping time $\tau$.

Denote by $t_{n}=n/100,n=0,1,...,100$. As the model is non-Markovian in
general, the value function $V$ should be path-dependent, i.e.
$V(\cdot,t_{n})$ not only depends on current state $W_{t_{n}}$, but also the
whole historical path. For this reason, we approximate the value function
$V(\cdot,t_{n})$ by a neural network with $n$-dimensional input. It also
consists of two hidden layer with width $n+20$. The training procedure
consists of $N=6000$ steps with a batch size $M=2^{11}$. The test data set is
of the size $2^{15}$. The temperature constant $\lambda$ is chosen to be
$10^{-5}$. We consider different values of $H$ and these results are shown in
Table 2.

Table 2: Summary result for fraction Brownian motion H | Our Method | Price in [1]
---|---|---
0.01 | 1.511 | 1.519
0.05 | 1.286 | 1.293
0.10 | 1.043 | 1.049
0.15 | 0.834 | 0.839
0.20 | 0.649 | 0.658
0.25 | 0.495 | 0.503
0.30 | 0.368 | 0.370
0.35 | 0.241 | 0.255
0.40 | 0.145 | 0.156
0.45 | 0.057 | 0.071
0.50 | 0.000 | 0.002
0.55 | 0.050 | 0.061
0.60 | 0.106 | 0.117
0.65 | 0.156 | 0.164
0.70 | 0.193 | 0.207
0.75 | 0.233 | 0.244
0.80 | 0.263 | 0.277
0.85 | 0.297 | 0.308
0.90 | 0.325 | 0.337
0.95 | 0.355 | 0.366
1.00 | 0.395 | 0.395

##  5 Conclusion

In this paper, we study the randomized optimal stopping time problem in the
so-called exploratory framework. By introducing an additional state, we reduce
it to a standard optimal control problem. Using PDE techniques, we are able to
give some quantitative results, especially on the balance between convergence
speed and bias. Although we mainly focus on American put option with one risky
asset, these theoretical results can be extended to more general Markovian
models as long as some regularity conditions hold. For non-Markovian cases, we
believe that there will be similar results. But one may need the theory of
backward stochastic differential equations to give a rigorous proof. We also
adjust well-developed RL algorithm to learn the optimal stopping strategy.
Computational results show that our algorithm achieves comparable performance
as that in [1, 19]. Noting that the algorithm here is offline, one can also
apply an online algorithm to study the strategy.

Our future research is to extend this framework to other optimal control
problems in mathematical finance. For optimal switching problem, the extension
is straightforward. Instead of introducing an additional scalar-valued state,
one needs a vector-valued state to represent the distribution of the
population in different modes, Moreover, the optimal strategy will be a soft-
max type. But, it requires more effort to give some rigorous theoretical
results. For optimal trading problem with transaction cost and tax, the
situation is more complicated as the free boundary is also determined by the
derivatives of the value function.

##  6 Proofs of the main results

###  6.1 Proofs for Theorem 1

The proof is rather standard in parabolic PDEs theory. One has to deal with
the unboundedness of the exponential function. Let $\\{h_{\varepsilon}(x)\\}$
be a sequence of smooth functions such that approximating $h(x)=(K-e^{x})^{+}$
increasingly and uniformly. Given $M>0$, consider a smooth cut-off function
$\phi_{M}$ such that $\phi_{M}(x)=e^{x}$ for $x\leq M$ and
$\phi_{M}(x)=e^{M+1}$ for $x\geq M+1$. Hence, $\phi_{M}$ is bounded and
Lipschitz continuous. Denote by $\Omega_{N}:=(-N,N)\times[0,T)$. Consider the
following PDEs

(6.1)
$\left\\{\begin{split}&\partial_{t}u^{\lambda,N,\varepsilon}+\mathcal{L}_{x}u^{\lambda,N,\varepsilon}+\lambda\phi_{M}(-\frac{u^{\lambda,N,\varepsilon}-h_{\varepsilon}}{\lambda})=0,(x,t)\in\Omega_{N},\\\
&u^{\lambda,N,\varepsilon}(-N,t)=g_{\varepsilon}(-N)+\lambda(T-t),u^{\lambda,N,\varepsilon}(N,t)=g_{\varepsilon}(N)+\lambda(T-t),t\in[0,T]\\\
&u^{\lambda,N,\varepsilon}(x,T)=h_{\varepsilon}(x),x\in[-N,N].\\\
\end{split}\right.$

Applying Schauder fixed point theorem [12, Theorem 8.1], there exists a unique
solution $u^{\lambda,N,\varepsilon}\in
C^{2+\alpha,\frac{1+\alpha}{2}}(\Omega_{N})\cap C(\bar{\Omega}_{N})$. Noting
that $0$ is a sub-solution, classical maximum principle [12, Theorem 2.4]
implies that $u^{\lambda,N,\varepsilon}\geq 0$. Define
$w(x,t):=u^{\lambda,N,\varepsilon}(x,t)-\big{(}K+\lambda(T-t)\big{)}$. Then,
we see that $w$ satisfies the following equation in $\Omega_{N}$

$\partial_{t}w+\mathcal{L}_{x}w+\lambda\phi_{M}(-\frac{u^{\lambda,N,\varepsilon}-h_{\varepsilon}}{\lambda})=\lambda+rK+r\lambda(T-t),$

with $w(x,T)\leq 0$. We can rewrite it as

$\begin{split}\partial_{t}w+\mathcal{L}_{x}w+\lambda\phi_{M}(-\frac{u^{\lambda,N,\varepsilon}-h_{\varepsilon}}{\lambda})-\lambda\phi_{M}(-\frac{K+\lambda(T-t)-h_{\varepsilon}}{\lambda})\\\
=\lambda-\lambda\phi_{M}(-\frac{K+\lambda(T-t)-h_{\varepsilon}}{\lambda})+rK+r\lambda(T-t).\end{split}$

Since $(K+\lambda(T-t))\geq h(x)\geq h_{\varepsilon}(x)$, we have that the
right hand side is non-negative. Using maximum principle again, we have that
$w\leq 0$, i.e. $u^{\lambda,N,\varepsilon}(x,t)\leq K+\lambda(T-t)$. Now, we
see that the bound is independent of $M$. Choosing $M$ sufficient large,
$u^{\lambda,N,\varepsilon}$ solves (6.1) with $\phi_{M}(\cdot)$ replaced by
$\exp(\cdot)$. Classical $L^{p}$ estimates [12, Theorem 7.32] yields that, for
any $R$ and $N>R+1$,

$\|u^{\lambda,N,\varepsilon}\|_{W^{2,1}_{p}(\Omega_{R})}\leq C_{\varepsilon}$

with the constant $C$ independent of $N$. Since $W^{2,1}_{p}(\Omega_{R})$ can
be compactly embedded into $C^{1+\alpha,\frac{1+\alpha}{2}}(\bar{\Omega}_{R})$
[8, Theorem 3.14], it yields that, subtracting a subsequence if needed,
$\\{u^{\lambda,N,\varepsilon}\\}$ locally uniformly convergent and also weakly
convergent in $W^{2,1}_{p,loc}(\mathbb{R}\times(0,T])$ to a function
$u^{\varepsilon}$. One can verify that $u^{\varepsilon}$ solves the following
equation

(6.2)
$\left\\{\begin{split}&\partial_{t}u^{\varepsilon}+\mathcal{L}_{x}u^{\varepsilon}+\lambda\exp(-\frac{u^{\varepsilon}-h_{\varepsilon}}{\lambda})=0,(x,t)\in\mathbb{R}\times(0,T),\\\
&u^{\varepsilon}(x,0)=h_{\varepsilon}(x).\end{split}\right.$

and satisfies the estimation (3.4). For any compact set
$D\subset\mathbb{R}\times(0,T)$, interior Schauder estimates yields that

$\|u^{\varepsilon}\|_{C^{2+\alpha,1+\frac{\alpha}{2}}(D)}\leq C$

with the constant $C$ independent $\varepsilon$. Hence,
$\\{u^{\varepsilon}\\}$ locally uniformly converges to a function $u$.
Clearly, $u$ satisfies the equation (3.3) in $\mathbb{R}\times(0,T)$. Let us
check that it also satisfies the terminal condition. Denote by $\varphi(x,t)$
the value of European put option at time $t$ in our model setup with stock
price $e^{x}$, which can be explicitly given, see [9, Section 2.3]. It is also
the solution for the following PDE

$\left\\{\begin{split}&\partial_{t}\varphi+\mathcal{L}_{x}\varphi=0,(x,t)\in\mathbb{R}\times(0,T),\\\
&\varphi(x,0)=h(x).\end{split}\right.$

Since $u^{\varepsilon}$ is uniformly bounded, the nonlinear term
$\lambda\exp(-\frac{u^{\varepsilon}-h_{\varepsilon}}{\lambda})$ in (6.2) has a
bound independent of $\varepsilon$. Using maximum principle again, it is not
hard to prove that $|u^{\varepsilon}(x,t)-\varphi(x,t)|\leq
C((T-t)+\|h-h_{\varepsilon}\|_{\infty})$. Letting $\varepsilon$ go to zero and
$t$ go to $T$, we verify the terminal condition for $u$.

###  6.2 Proofs for Theorem 2

Recall that $\\{u^{n},\pi^{n}\\}$ are defined iteratively by the following
equation

(6.3)
$\partial_{t}u^{n}+\mathcal{L}_{x}u^{n}+H(x,\pi^{n}(x,t),u^{n})=0,u^{n}(x,T)=h(x),$

and

(6.4)
$\pi^{n+1}(x,t)=\mathop{\text{argmax}}_{\pi\in(0,\infty)}H(x,\pi,u^{n}(x,t))=\exp(-\frac{u^{n}(x,t)-h(x)}{\lambda}).$

Hence, it is east to obtain that both $u^{n}$ and $\log\pi^{n}$ are bounded by
induction. Define $\Delta^{n}:=u^{n+1}-u^{n}$. We see that it satisfies

(6.5)
$\partial_{t}\Delta^{n}+\mathcal{L}_{x}\Delta^{n}+H(x,u^{n+1},\pi^{n+1})-H(x,u^{n},\pi^{n})=0,\Delta^{n}(x,T)=0.$

From the definition of the Hamiltonian $H$, it can be also rewritten as

(6.6)
$\partial_{t}\Delta^{n}+\mathcal{L}_{x}\Delta^{n}-\pi^{n+1}\Delta^{n}=H(u^{n},\pi^{n})-H(u^{n},\pi^{n+1})$

By the definition of $\pi^{n+1}$, we see that
$H(u^{n},\pi^{n})-H(u^{n},\pi^{n+1})\leq 0$. Hence, $0$ is a sub-solution of
(6.6), which implies that $\Delta^{n}\geq 0$. Thus, we show that $u^{n+1}\geq
u^{n}$.

Next, consider the difference between $u^{\lambda}$ and $u^{n}$. Define
$w^{n}:=u^{\lambda}-u^{n}$. Note that $u^{\lambda}$ satisfies

(6.7)
$\partial_{t}u^{\lambda}+\mathcal{L}_{x}u^{\lambda}+H(x,u^{\lambda},\pi^{\lambda})=0,u^{\lambda}(x,T)=h(x).$

with

$\pi^{\lambda}(x,t)=\mathop{\text{argmax}}_{\pi\in(0,\infty)}H(x,\pi,u^{\lambda}(x,t))=\exp(-\frac{u^{\lambda}(x,t)-h(x)}{\lambda}).$

Thus,

$\partial_{t}w^{n}+\mathcal{L}_{x}w^{n}+H(x,u^{\lambda},\pi^{\lambda})-H(x,u^{n},\pi^{n})=0,w^{n}(x,T)=0.$

This is equivalent to

(6.8)
$\partial_{t}w^{n}+\mathcal{L}_{x}w^{n}-\pi^{n}w^{n}=H(u^{\lambda},\pi^{n})-H(u^{\lambda},\pi^{\lambda})$

By the definition of $\pi^{\lambda}$, the right hand side is less than $0$.
Applying maximum principle, we shall have that $w^{n}\geq 0$. At this stage,
we have proved that $u^{n}\leq u^{\lambda}$.

###  6.3 Proof for Theorem 3

We have shown that $u^{1}\leq u^{n}\leq u^{\lambda}$. Hence, $\\{u^{n}\\}$ is
uniformly bounded. Moreover, $u^{\lambda}(x,t),u^{n}(x,t)\geq h(x)-M$ with
$M:=\|(h-u^{1})^{+}\|_{\infty}$. To prove the convergence rate, we define a
function $f^{n}(t)$ as

$f^{n}(t):=\sup_{x}u^{\lambda}(x,t)-u^{n}(x,t).$

By the definition of $\pi^{\lambda}$ and $\pi^{n}$, we compute that

$\begin{split}&H(x,u^{\lambda},\pi^{n+1})-H(x,u^{\lambda},\pi^{\lambda})\\\
=&(u^{n}-u^{\lambda})\exp(-\frac{u^{n}-h}{\lambda})+\lambda(\exp(-\frac{u^{n}-h}{\lambda})-\exp(-\frac{u^{\lambda}-h}{\lambda}))\end{split}$

Then, it holds that

$|H(x,u^{\lambda},\pi^{n+1})-H(x,u^{\lambda},\pi^{\lambda})|\leq
C\exp(\frac{M}{\lambda})|u^{n}(x,t)-u^{\lambda}(x,t)|\leq
C\exp(\frac{M}{\lambda})f^{n}(t).$

Define $\phi(t):=C\exp(\frac{M}{\lambda}+rt)\int_{t}^{T}f^{n}(s)ds$. It solves
$\partial_{t}\phi-r\phi=-C\exp(\frac{M}{\lambda}+rt)f^{n}(t)$. Then, we see
that $W:=u^{\lambda}-u^{n+1}-\phi$ satisfies

$\partial_{t}W+\mathcal{L}_{x}W=(u^{\lambda}-u^{n+1})\pi^{n+1}+H(u^{\lambda},\pi^{n+1})-H(u^{\lambda},\pi^{\lambda})+C\exp(\frac{M}{\lambda}+rt)f^{n}(t),$

with terminal condition $W(x,T)=0$. Previous argument shows that

$H(u^{\lambda},\pi^{n+1})-H(u^{\lambda},\pi^{\lambda})+C\exp(\frac{M}{\lambda}+rt)f^{n}(t)\geq
0.$

Combining with the fact that $u^{\lambda}-u^{n+1}\geq 0$, it holds that

$\partial_{t}W+\mathcal{L}_{x}W\geq 0,$

which will implies that $W\leq 0$ from maximum principle. This also means that

$u^{\lambda}(x,t)-u^{n+1}(x,t)\leq\phi(t)=C\exp(\frac{M}{\lambda}+rt)\int_{t}^{T}f^{n}(s)ds.$

Taking supreme with respect to $x$ on the left hand side, we have that

$f^{n+1}(t)\leq C\exp(\frac{M}{\lambda}+rt)\int_{t}^{T}f^{n}(s)ds\leq
Ce^{rT}\exp(\frac{M}{\lambda})\int_{t}^{T}f^{n}(s)ds.$

It is easy to see that $f^{1}$ is bounded in $t$. Proving by induction, we see
that there exists a constant $C$ such that $f^{n+1}(t)\leq
C^{n}\frac{(T-t)^{n}}{n!}\exp(n(\frac{M}{\lambda}+rT))$.

###  6.4 Proof for Lemma 3.1

Let $\kappa$ be a smooth, increasing, convex function such that $\kappa(x)=x$
for $x\geq 1$ and $\kappa(x)=0$ for $x\leq 0$. Denote by $C_{1}$, the supreme
of $\kappa^{\prime}$. Given $\varepsilon>0$, define
$\kappa_{\varepsilon}(x):=\frac{1}{\varepsilon}\kappa(\frac{K-e^{x}}{\varepsilon})$.
It is easy to check that $\|\kappa_{\varepsilon}(x)-h(x)\|_{\infty}\rightarrow
0$ as $\varepsilon\rightarrow 0$.

For any $\delta>0$, let us prove that $u^{\lambda}(x,t)\geq
h(x)-\lambda\log\frac{(2+C_{1})rK+\delta}{\lambda}$. Assume the contrary, i.e.
$\inf_{(x,t)\in\mathbb{R}\times[0,T]}u^{\lambda}(x,t)-(h(x)-\lambda\log\frac{(2+C_{1})rK+\delta}{\lambda})<0$.
Since $\kappa_{\varepsilon}$ uniformly convergent to $h(x)$, we also have that
$\inf_{(x,t)\in\mathbb{R}\times[0,T]}u^{\lambda}(x,t)-(\kappa_{\varepsilon_{1}}(x)-\lambda\log\frac{(2+C_{1})rK+\delta}{\lambda})<0$
for sufficiently small ${\varepsilon_{1}}$. Choose another sufficient small
constant $\varepsilon_{2}$. It will hold that
$\inf_{(x,t)\in\mathbb{R}\times[0,T]}u^{\lambda}(x,t)-(\kappa_{\varepsilon_{1}}(x)-\lambda\log\frac{(2+C_{1})rK+\delta}{\lambda}-\frac{\varepsilon_{2}}{2}e^{rt}(|x|^{2}+\frac{1}{t}))<0$
and the infimum is achieved at some point $(x^{*},t^{*})$ with
$t^{*}\in(0,T)$. Since $u^{\lambda}$ and $\kappa_{\varepsilon_{1}}$ are
bounded, we shall have that
$\frac{\varepsilon_{2}}{2}(|x^{*}|^{2}+\frac{1}{t^{*}})\leq C$ with the
constant $C$ independent of $\varepsilon_{1}$ and $\varepsilon_{2}$. Denote by
$w(x,t)=\kappa_{\varepsilon_{1}}(x)-\lambda\log\frac{(2+C_{1})rK+\delta}{\lambda}-\frac{\varepsilon_{2}}{2}e^{rt}(|x|^{2}+\frac{1}{t})$.
It holds that

$\partial_{x}w=-\kappa^{\prime}(\frac{K-e^{x}}{\varepsilon_{1}})e^{x}-\varepsilon_{2}e^{rt}x,$
$\partial_{xx}w=\kappa^{\prime\prime}(\frac{K-e^{x}}{\varepsilon_{1}})e^{2x}-\kappa^{\prime}(\frac{k-e^{x}}{\varepsilon_{1}})e^{x}-\varepsilon_{2}e^{rt},$

and
$\partial_{t}w=\frac{\varepsilon_{2}}{2}\frac{e^{rt}}{t^{2}}-r\frac{\varepsilon_{2}}{2}\frac{e^{rt}}{t}$.
At $(x^{*},t^{*})$, we have

$\partial_{x}u^{\lambda}(x^{*},t^{*})=\partial_{x}w(x^{*},t^{*}),\partial_{xx}u^{\lambda}(x^{*},t^{*})\geq\partial_{xx}w(x^{*},t^{*}),$

$\partial_{t}u^{\lambda}(x^{*},t^{*})=\partial_{t}w(x^{*},t^{*})$ and
$u^{\lambda}(x^{*},t^{*})<w(x^{*},t^{*})$. Then, at $(x^{*},t^{*})$

(6.9)
$\begin{split}0=&\partial_{t}u^{\lambda}+\mathcal{L}_{x}u^{\lambda}+\lambda\exp(-\frac{u^{\lambda}(x^{*},t^{*})-g(e^{x^{*}})}{\lambda})\\\
>&\partial_{t}w+\mathcal{L}_{x}w+\lambda\exp(-\frac{u^{\lambda}(x^{*},t^{*})-g(e^{x^{*}})}{\lambda}).\end{split}$

Since $\kappa$ is convex, we have

$\partial_{t}w(x^{*},t^{*})+\mathcal{L}_{x}w(x^{*},t^{*})\geq-r\kappa^{\prime}(\frac{K-e^{x^{*}}}{\varepsilon_{1}})e^{x^{*}}-\varepsilon_{2}(r-\frac{\sigma^{2}}{2})e^{rt}x^{*}-\frac{\sigma^{2}}{2}\varepsilon_{2}e^{rt}-r\kappa_{\varepsilon_{1}}(x^{*}).$

Note that $\kappa^{\prime}(\frac{K-e^{x^{*}}}{\varepsilon_{1}})$ is non-zero
only if $e^{x^{*}}\leq K$ and $\frac{\varepsilon_{2}}{2}|x^{*}|^{2}\leq C$.
Since $\kappa_{\varepsilon_{1}}(x)\leq K$, we shall have that

(6.10)
$\partial_{t}w(x^{*},t^{*})+\mathcal{L}_{x}w(x^{*},t^{*})\geq-(1+C_{1})rK-C\varepsilon_{2}.$

At $(x^{*},t^{*})$, it has that

$\begin{split}&h(x^{*})-u^{\lambda}(x^{*},t^{*})\\\
\geq&h(x^{*})-w(x^{*},t^{*})\\\
\geq&h(x^{*})-\kappa_{\varepsilon_{1}}(x^{*})+\lambda\log\frac{(2+C_{1})rK+\delta}{\lambda}.\end{split}$

Thus,

(6.11)
$\lambda\exp(-\frac{u^{\lambda}(x^{*},t^{*})-h(x^{*})}{\lambda})\geq((2+C_{1})rK+\delta)\exp(\frac{h(x^{*})-\kappa_{\varepsilon_{1}}(x^{*})}{\lambda})$

Combining (6.10) and (6.11), we see that the right hand side of (6.9) will be
strictly positive for $\varepsilon_{1}$ and $\varepsilon_{2}$ sufficiently
small. This leads to a contradiction. Thus, we prove that, for any $\delta>0$,
$u^{\lambda}(x,t)\geq h(x)-\lambda\log\frac{(2+C_{1})rK+\delta}{\lambda}$.
Letting $\delta\rightarrow 0$, we have the desired result.

###  6.5 Proof for Theorem 3.2

It is well-known that $u^{*}$ is smooth in the region $\\{u^{*}>h\\}$. Assume
the contrary that
$\sup_{(x,t)\in\mathbb{R}\times[0,T]}u^{*}(x,t)-u^{\lambda}(x,t)-\lambda\log\frac{CrK}{\lambda}>0$.
Similar as in the proof of Lemma 3.1, one can choose $\varepsilon$
sufficiently small such that
$\sup_{(x,t)\in\mathbb{R}\times[0,T]}u^{*}(x,t)-u^{\lambda}(x,t)-\lambda\log\frac{CrK}{\lambda}-\varepsilon(\frac{1}{2}|x|^{2}+\frac{1}{t})>0$
and the supreme is attained at $(x^{*},t^{*})$. By the terminal condition of
$u^{*}$ and $u^{\lambda}$, it holds that $t^{*}\in(0,T)$. Denote by
$w=u^{\lambda}+\lambda\log\frac{CrK}{\lambda}+\varepsilon(\frac{1}{2}|x|^{2}+\frac{1}{t})$.
Then, at $(x^{*},t^{*})$, it holds that

$\partial_{xx}u^{*}(x^{*},t^{*})\leq\partial_{xx}w(x^{*},t^{*}),\partial_{x}u^{*}(x^{*},t^{*})=\partial_{x}w(x^{*},t^{*})\text{
and }\partial_{t}u^{*}(x^{*},t^{*})=\partial_{t}w.$

We also have that

$\partial_{xx}w(x^{*},t^{*})=\partial_{xx}u^{\lambda}(x^{*},t^{*})+\varepsilon,\partial_{x}w(x^{*},t^{*})=\partial_{x}u^{\lambda}(x^{*},t^{*})+\varepsilon
x^{*},$

and
$\partial_{t}w(x^{*},t^{*})=\partial_{t}u^{\lambda}(x^{*},t^{*})-\varepsilon\frac{1}{(t^{*})^{2}}$.
Since
$u^{*}(x^{*},t^{*})>u^{\lambda}(x^{*},t^{*})+\lambda\log\frac{CrK}{\lambda}$
and Lemma 1, we have $u^{*}(x^{*},t^{*})>h(x^{*})$. This implies that, at
$(x^{*},t^{*})$

$\partial_{t}u^{*}+\mathcal{L}_{x}u^{*}=0.$

Then, from the relation between the derivatives of $u^{*}$ and $w$, we deduce
that, at $(x^{*},t^{*})$

$\partial_{t}u^{\lambda}+\mathcal{L}_{x}u^{\lambda}\geq-\frac{1}{2}\sigma^{2}\varepsilon-(r-\frac{1}{2}\sigma^{2})\varepsilon
x^{*}+\varepsilon\frac{1}{(t^{*})^{2}}.$

We also have $\frac{\varepsilon}{2}|x^{*}|^{2}\leq C$ with the constant
independent of $\varepsilon$. This implies that $\varepsilon
x^{*}=O(\varepsilon^{1/2})$. In Theorem 1, we have shown that $u^{\lambda}$ is
bounded, which yields $\lambda\exp(-\frac{u^{\lambda}-h}{\lambda})$ is
uniformly larger than some small constant. Hence, we shall have that
$\partial_{t}u^{\lambda}+\mathcal{L}_{x}u^{\lambda}+\lambda\exp(-\frac{u^{\lambda}-h}{\lambda})>0$
at $(x^{*},t^{*})$ for $\varepsilon$ sufficiently small. This leads to a
contradiction. Hence, we have prove the second inequality.

Let $f(t):=\log(1+(T-t))$. It is easy to see that

$\partial_{t}f+\exp(-f)=0.$

Denote by $w(x,t)=u^{*}(x,t)+\lambda f(t)$. Then, we see that
$\exp(-\frac{w-h}{\lambda})\leq\exp(-f)$ as $u^{*}\geq h$. Combining with the
fact that $\partial_{t}u^{*}+\mathcal{L}_{x}u^{*}\leq 0$, it holds that $w$
solves the following inequality

$\partial_{t}w+\mathcal{L}_{x}w+\lambda\exp(-\frac{w-h}{\lambda})<0,$

with terminal condition $w(x,T)=u^{\lambda}(x,T)$. Then, applying maximum
principle, we shall have that $u^{\lambda}\leq w$, which is equivalent to the
first inequality of our theorem.

###  6.6 Proof for Theorem 3.3

Applying Itô formula, we see that

$\begin{split}&e^{-r\tau^{\lambda}}g(S_{\tau^{\lambda}})\\\
=&e^{-r\tau^{\lambda}}V^{\lambda}(S_{\tau^{\lambda}},\tau^{\lambda})\\\
=&V^{\lambda}(S_{0},0)+\int_{0}^{\tau^{\lambda}}e^{-ru}(\partial_{t}+\mathcal{L}_{S})V^{\lambda}(S_{u},u)du+\sigma\int_{0}^{\tau^{\lambda}}e^{-ru}\partial_{S}V(S_{u},u)dW_{u}\\\
=&V^{\lambda}(S_{0},0)-\lambda\int_{0}^{\tau^{\lambda}}e^{-ru}\exp(-\frac{V^{\lambda}(S_{u},u)-g(S_{u})}{\lambda})du+\sigma\int_{0}^{\tau^{\lambda}}e^{-ru}\partial_{S}V(S_{u},u)dW_{u}\\\
\geq&V^{\lambda}(S_{0},0)-\lambda
T+\sigma\int_{0}^{\tau^{\lambda}}e^{-ru}\partial_{S}V(S_{u},u)dW_{u}.\end{split}$

Taking expectation, we have

$\mathbb{E}\left[e^{-r\tau^{\lambda}}g(S_{\tau^{\lambda}})\right]\geq
V^{\lambda}(S_{0},0)-\lambda T\geq
V^{*}(S_{0},0)+\inf_{S}(V^{\lambda}(\cdot,0)-V^{*}(\cdot,0))-\lambda T.$

Previous lemma indicates that
$\inf_{S}(V^{\lambda}(\cdot,0)-V^{*}(\cdot,0))\geq-\lambda\log{\frac{CrK}{\lambda}}$.
Hence,

$\mathbb{E}\left[e^{-r\tau^{\lambda}}g(S_{\tau^{\lambda}})\right]\geq
V^{*}(S_{0},0)-(\lambda\log\frac{CrK}{\lambda}+\lambda T).$

This implies that using learned strategy leads to a loss of wealth
approximately of the order $O(\lambda\log\frac{1}{\lambda})$.

## References

  * [1] S. Becker, P. Cheridito, and A. Jentzen, Deep optimal stopping, Journal of Machine Learning Research, 20 (2019), p. 74.
  * [2] S. Becker, P. Cheridito, A. Jentzen, and T. Welti, Solving high-dimensional optimal stopping problems using deep learning, European Journal of Applied Mathematics, 32 (2021), pp. 470–514.
  * [3] M. P. Deisenroth, G. Neumann, J. Peters, et al., A survey on policy search for robotics, Foundations and Trends® in Robotics, 2 (2013), pp. 1–142.
  * [4] W. H. Fleming and M. Nisio, On stochastic relaxed control for partially observed diffusions, Nagoya Mathematical Journal, 93 (1984), pp. 71–108.
  * [5] P. A. Forsyth and K. R. Vetzal, Quadratic convergence for valuing american options using a penalty method, SIAM Journal on Scientific Computing, 23 (2002), pp. 2095–2122.
  * [6] R. Fox, A. Pakman, and N. Tishby, Taming the noise in reinforcement learning via soft updates, arXiv preprint arXiv:1512.08562, (2015).
  * [7] D. Hendricks and D. Wilcox, A reinforcement learning extension to the almgren-chriss framework for optimal trade execution, in 2014 IEEE Conference on Computational Intelligence for Financial Engineering & Economics (CIFEr), IEEE, 2014, pp. 457–464.
  * [8] B. Hu, Blow-up theories for semilinear parabolic equations, Springer, 2011.
  * [9] M. Jeanblanc, M. Yor, and M. Chesney, Mathematical methods for financial markets, Springer Science & Business Media, 2009.
  * [10] B. Kerimkulov, D. Siska, and L. Szpruch, Exponential convergence and stability of howard’s policy improvement algorithm for controlled diffusions, SIAM Journal on Control and Optimization, 58 (2020), pp. 1314–1340.
  * [11] S. Levine, C. Finn, T. Darrell, and P. Abbeel, End-to-end training of deep visuomotor policies, The Journal of Machine Learning Research, 17 (2016), pp. 1334–1373.
  * [12] G. M. Lieberman, Second order parabolic differential equations, World scientific, 1996.
  * [13] F. A. Longstaff and E. S. Schwartz, Valuing american options by simulation: a simple least-squares approach, The review of financial studies, 14 (2001), pp. 113–147.
  * [14] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., Human-level control through deep reinforcement learning, Nature, 518 (2015), p. 529.
  * [15] J. Moody and M. Saffell, Learning to trade via direct reinforcement, IEEE transactions on neural Networks, 12 (2001), pp. 875–889.
  * [16] J. Moody, L. Wu, Y. Liao, and M. Saffell, Performance functions and reinforcement learning for trading systems and portfolios, Journal of Forecasting, 17 (1998), pp. 441–470.
  * [17] O. Nachum, M. Norouzi, K. Xu, and D. Schuurmans, Bridging the gap between value and policy based reinforcement learning, in Advances in Neural Information Processing Systems, 2017, pp. 2775–2785.
  * [18] Y. Nevmyvaka, Y. Feng, and M. Kearns, Reinforcement learning for optimized trade execution, in Proceedings of the 23rd international conference on Machine learning, ACM, 2006, pp. 673–680.
  * [19] A. M. Reppen, H. M. Soner, and V. Tissot-Daguette, Neural optimal stopping boundary, arXiv preprint arXiv:2205.04595, (2022).
  * [20] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al., Mastering the game of go with deep neural networks and tree search, nature, 529 (2016), p. 484.
  * [21] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al., Mastering the game of go without human knowledge, Nature, 550 (2017), p. 354.
  * [22] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction, Cambridge, MA: MIT Press, 2011.
  * [23] W. Tang, P. Y. Zhang, and X. Y. Zhou, Exploratory HJB equations and their convergence, arXiv preprint arXiv:2109.10269, (2021).
  * [24] H. Wang, T. Zariphopoulou, and X. Y. Zhou, Reinforcement learning in continuous time and space: A stochastic control approach., J. Mach. Learn. Res., 21 (2020), pp. 198–1.
  * [25] X. Y. Zhou, On the existence of optimal relaxed controls of stochastic partial differential equations, SIAM Journal on Control and Optimization, 30 (1992), pp. 247–261.
  * [26] B. D. Ziebart, A. Maas, J. A. Bagnell, and A. K. Dey, Maximum entropy inverse reinforcement learning, (2008).