## Optimal stopping III: a comparison principle

The following is the last in a series of posts on optimal stopping. In the previous post, we showed that the value function satisfied a particular partial differential equation (PDE) in the viscosity sense, thereby positing the existence of a solution to that PDE. In this post, we derive a comparison principle for the optimal stopping problem, which in turn guarantees uniqueness of solutions to the PDE. It follows that, roughly speaking, the value function and the solution to the PDE are one and the same.

We now look to transcribe the PDE of the previous post along with the relevant Cauchy data (i.e., terminal condition). Let $\rho > 0$ be arbitrary and $$F(w,r,q,A)=-\operatorname{trace}(\sigma(w)\sigma(w)^{\top}A)-b(w)\cdot q+\rho r\text{ where }w=(t,x).$$ We can write the Cauchy problem as \begin{align} \min\left\{ -\partial_{t}v+F(\cdot,v(\cdot),Dv(\cdot),D_{x}^{2}v(\cdot)),(v-g)(\cdot)\right\} & =0 & \text{on }[0,T)\times\mathbb{R}^{d};\nonumber \\ (v-g)(T,\cdot) & =0 & \text{on }\mathbb{R}^{d}.\tag{1}\label{eq:pde_boundary} \end{align}

Note that we have introduced a discounting term $\rho$ into the PDE. We can go from the PDE of the previous post to one of the form above by picking an arbitrary (positive) discount term and performing a change of variables (in particular, the $g$ is not the same as the $g$ of the previous post; it is scaled by a factor of the form $e^{\rho t}$). The reader should be able to convince themselves that uniqueness in the setting $\rho > 0$ implies uniqueness in the setting $\rho = 0$ whenever the change of variables can be performed.

For completeness, we extend (in the obvious manner) our notion of viscosity solution from the previous post to take into account the boundary:

Let $\mathcal{O}=[0,T)\times\mathbb{R}^{d}$. A locally bounded function $v\colon\mathcal{O}\rightarrow\mathbb{R}$ is a viscosity subsolution (resp. supersolution) of \eqref{eq:pde_boundary} if \begin{align*} & \min\left\{ -\partial_{t}\varphi(w)+F(w,v^{*}(w),D_{x}\varphi(w),D_{x}^{2}\varphi(w)),(v^{*}-g)(w)\right\} & \leq0 & & \text{if }0 \leq t < T;\\ & (v^{*}-g)(w) & \leq0 & & \text{if }t=T.\\ \text{(resp. } & \min\left\{ -\partial_{t}\varphi(w)+F(w,v_{*}(w),D_{x}\varphi(w),D_{x}^{2}\varphi(w)),(v_{*}-g)(w)\right\} & \geq0 & & \text{if }0 \leq t < T;\\ & (v_{*}-g)(w) & \geq0 & & \text{if }t=T. & \text{ )} \end{align*} for all $(w=(t,x),\varphi)\in\mathcal{O}\times C^{1,2}(\mathcal{O})$ such that $(v^{*}-\varphi)(y)=\max_{\mathcal{O}}(v^{*}-\varphi)=0$ (resp. $(v_{*}-\varphi)(y)=\min_{\mathcal{O}}(v_{*}-\varphi)=0$) and the maximum (resp. minimum) is strict. We say $v$ is a viscosity solution of \eqref{eq:pde_boundary} if it is both a subsolution and supersolution of \eqref{eq:pde_boundary}.
The reader familiar with the theory will note that for ease of presentation, we have decided not to incorporate the boundary conditions in the "strong sense" (see [1 Section 7.A]), so that some sort of a priori continuity needs to be established up to the boundary to establish the results of the previous post with the added boundary condition. A simple solution is to require that $g$ be Lipschitz in the previous posts.

Uniqueness for elliptic (resp. parabolic) equations in the classical setting is often established via a maximum principle. Such a maximum principle often states that if two solutions $u$ and $v$ satisfy $u\leq v$ on the boundary $\partial\Omega$ of the bounded domain $\Omega$ on which the PDE is defined, then $u\leq v$ on the closure of the domain $\overline{\Omega}$ (i.e., everywhere). However, maximum principles are often derived by considering the case of $u$ and $v$ smooth, so that the first and second derivatives of $u-v$ satisfy the usual conditions for maxima (i.e., $D(u-v)=0$ and $D^{2}(u-v)\preceq0$).

However, in the context of viscosity solutions, no smoothness is assumed. The main tool to circumvent this apparent problem is the celebrated Crandall-Ishii Lemma [1]. We use the notation $|A|=\sup\left\{ A\xi\cdot\xi\colon\left|\xi\right|\leq1\right\}$ for $A\in\mathscr{S}(d)$, along with the parabolic semijets $\overline{\mathscr{P}}^{2,\pm}$ as defined in [1]. The semijets give an alternative characterization of viscosity solutions which we will not discuss here. We mention that we are unable to use the "parabolic" Crandall-Ishii Lemma [1 Theorem 8.3] directly due to an issue with the boundedness of the derivatives. We rely instead on the "elliptic" version [1 Theorem 3.2] and a variable-doubling argument.

We consider here the case of bounded solutions (e.g., $g$ is bounded in the first post of the series). We leave it to the reader to derive conditions for more interesting cases (e.g., solutions of sublinear growth).

Let $u$ be a bounded subsolution and $v$ be a bounded supersolution of \eqref{eq:pde_boundary}. Suppose $\rho>0$ and that $b=b(x)$ and $\sigma=\sigma(x)$ are independent of time $t$ and Lipschitz continuous in $x$. Then, $u\leq v$.

It follows from the above that a viscosity solution $u$ (i.e., sub and super) of \eqref{eq:pde_boundary} satisfies $u^{*}\leq g\leq u_{*}$ on $\{T\}\times\mathbb{R}^{d}$ and hence $u^{*}\leq u_{*}$ everywhere. Moreover, the inequality $u_{*}\leq u^{*}$ is trivial from the definition of semicontinuous envelopes. Therefore, $u_{*}=u^{*}$, so that the function $u$ is continuous. Moreover, since for any two viscosity solutions $u$ and $v$ we have $u\leq v$ and $v\leq u$, it follows that $u=v$.

Without loss of generality, we can assume that $u$ (resp. $v$) is upper (resp. lower) semicontinuous (otherwise, replace $u$ and $v$ by their semicontinuous envelopes). To arrive at a contradiction, suppose $$\delta = \sup_{\mathcal{O}} \left\{ u - v \right\} > 0.$$ Letting $\nu > 0$, we can find $(t^\nu, x^\nu) \in \mathcal{O}$ such that $(u - v)(t^\nu, x^\nu) \geq \delta - \nu$. Let $\alpha>0$, $0 < \epsilon\leq1$, and $$\varphi(t,x,s,y)=\frac{\alpha}{2}\left(\left|x-y\right|^{2}+\left|t-s\right|^{2}\right)+\frac{\epsilon}{2}\left(\left|x\right|^{2}+\left|y\right|^{2}\right).$$ Note that \begin{align*} M_{\alpha} & =\sup_{(t,x,s,y)\in([0,T]\times\mathbb{R}^{d})^2}\left\{ u(t,x)-v(s,y)-\varphi(t,x,s,y)\right\} \\ & \geq\sup_{(t,x)\in[0,T]\times\mathbb{R}^{d}}\left\{ (u-v)(t,x)-\varphi(t,x,t,x)\right\} \\ & =\sup_{(t,x)\in[0,T]\times\mathbb{R}^{d}}\left\{ (u-v)(t,x)-\epsilon|x|^{2}\right\} \\ & \geq(u-v)(t^\nu,x^\nu)-\epsilon|x^\nu|^{2}\\ & \geq\delta-\nu-\epsilon|x^\nu|^{2}. \end{align*} We henceforth assume $\epsilon$ is small enough so that $\delta - \nu - \epsilon|x^\nu|^2$ is positive. Since $u$ and $v$ are trivially of subquadratic growth, for each $\alpha>0$, there exists $(t_{\alpha},x_{\alpha},s_{\alpha},y_{\alpha})\in([0,T]\times\mathbb{R}^{d})^2$ such that $$M_{\alpha}=u(t_{\alpha},x_{\alpha})-v(s_{\alpha},y_{\alpha})-\varphi(t_{\alpha},x_{\alpha},s_{\alpha},y_{\alpha}).$$ It follows that $$\left\Vert u\right\Vert _{\infty}+\left\Vert v\right\Vert _{\infty}\geq u(t_{\alpha},x_{\alpha})-v(s_{\alpha},y_{\alpha})\geq\delta-\nu-\epsilon|x^\nu|^{2}+\varphi(t_{\alpha},x_{\alpha},s_{\alpha},y_{\alpha})\geq$$ and hence $$\alpha\left(\left|x_{\alpha}-y_{\alpha}\right|^{2} + \left|t_{\alpha}-s_{\alpha}\right|^{2}\right) + \epsilon(|x_{\alpha}|^{2}+|y_{\alpha}|^{2})$$ is bounded independently of $\alpha$ and $\epsilon$. Now, for fixed $\epsilon$, consider an increasing sequence of $\alpha$, say $(\alpha_{n})_{n}$. To each $\alpha_{n}$ is associated a maximum point $(t_{n},x_{n},s_n,y_{n})=(t_{\alpha_{n}},x_{\alpha_{n}},s_{\alpha_n},y_{\alpha_{n}})$. Since $|x_{\alpha}|^{2}+|y_{\alpha}|^{2}$ is bounded independently of $\alpha$ (for fixed $\epsilon$), it follows that $\{(t_{n},x_{n},y_{n})\}_{n}$ is contained in a compact set. Therefore, $(\alpha_{n},t_{n},x_{n},s_n,y_{n})_n$ admits a subsequence whose four last components converge to some point $(\hat{t},\hat{x},\hat{s},\hat{y})$. It follows that $\hat{x}=\hat{y}$ since otherwise $|\hat{x}-\hat{y}|>0$ and $$\limsup_{n\rightarrow\infty}\left\{ \alpha_{n}\left|x_{n}-y_{n}\right|^{2}\right\} =\limsup_{n\rightarrow\infty}\alpha_{n}\left|\hat{x}-\hat{y}\right|^{2}=\infty,$$ contradicting the boundedness in the discussion above. Similarly, $\hat{t}=\hat{s}$. Moreover, letting $\varphi_n=\varphi(t_n,x_n,s_n,y_n;\alpha_n)$, \begin{align*} 0\leq\limsup_{n\rightarrow\infty}\varphi_n & \leq\limsup_{n\rightarrow\infty}\left\{ u(t_{n},x_{n})-v(s_{n},y_{n})\right\} -\delta+\nu+\epsilon|x^\nu|^{2}\\ & \leq\limsup_{n\rightarrow\infty}u(t_{n},x_{n})-\liminf_{n\rightarrow\infty}v(s_{n},y_{n})-\delta+\nu+\epsilon|x^\nu|^{2}\\ & \leq(u-v)(\hat{t},\hat{x})-\delta+\nu+\epsilon|x^\nu|^{2} \end{align*} and hence $$0 < \delta-\nu-\epsilon|x^\nu|^{2}\leq(u-v)(\hat{t},\hat{x}).$$ Since the left-hand side of the above is positive, it follows that $(\hat{t},\hat{x})\in\mathcal{O}$ (otherwise we would contradict $u\leq v$ on the boundary). Therefore, we can, without loss of generality, assume $(t_{n},x_{n},s_n,y_{n})\in\mathcal{O}$ for all $n$.
We can now apply the Crandall-Ishii Lemma (with $u_{1}=u$ and $u_{2}=-v$) to find $A_{n},B_{n}\in\mathscr{S}(d)$ and $a_{n}\in\mathbb{R}$ such that$$\left(a_{n},D_x\varphi(x_{n},y_{n}),A_{n}+\epsilon I_d \right)\in\mathscr{\overline{P}}_{\mathcal{U}}^{2,+}u(t_{n},x_{n})\text{ and }\left(a_{n},-D_y\varphi(x_{n},y_{n}),B_{n}-\epsilon I_d \right)\in\mathscr{\overline{P}}_{\mathcal{U}}^{2,-}v(t_{n},x_{n})$$ and $$-3\alpha_{n}I_{2d}\preceq\left(\begin{array}{cc} A_{n}\\ & -B_{n} \end{array}\right)\preceq3\alpha_{n}\left(\begin{array}{cc} I_{d} & -I_{d}\\ -I_{d} & I_{d} \end{array}\right).$$
Since $u$ is a subsolution and $v$ is a supersolution, it follows that \begin{align*} \min\left\{ -a_{n}+F(t_{n},x_{n},u(t_{n},x_{n}),\alpha(x_{n}-y_{n})+\epsilon x_{n},A_{n}+\epsilon I_d),(u-g)(t_{n},x_{n})\right\} & \leq0;\\ \min\left\{ -a_{n}+F(s_{n},y_{n},v(s_{n},y_{n}),\alpha(x_{n}-y_{n})-\epsilon y_{n},B_{n}-\epsilon I_d),(v-g)(t_{n},y_{n})\right\} & \geq0. \end{align*} With an abuse of notation, suppose $(u-g)(t_{n},x_{n})\leq0$ along some subsequence $(t_{n},x_{n},s_n,y_{n})_{n}$. Then, since $(v-g)(s_{n},y_{n})\geq0$ by the supersolution property, we have that $$\delta-\nu-\epsilon|x^\nu|^{2}+\varphi_n \leq u(t_{n},x_{n})-v(s_{n},y_{n})-\left(g(t_n,x_{n})-g(s_n,y_{n})\right)\leq0.$$ If we take $n$ large enough and $\epsilon$ small enough, the left-hand side of the above becomes strictly positive, yielding a contradiction. Therefore, with yet another abuse of notation, we can pick a subsequence $(t_{n},x_{n},s_n,y_{n})_n$ on which $(u-g)(t_{n},x_{n})>0$ for all $n$. On this subsequence, \begin{align*} -a_{n}+F(t_{n},x_{n},u(t_{n},x_{n}),\alpha(x_{n}-y_{n})+\epsilon x_{n},A_{n}+\epsilon I_d) & \leq0;\\ -a_{n}+F(s_{n},y_{n},v(s_{n},y_{n}),\alpha(x_{n}-y_{n})-\epsilon y_{n},B_{n}-\epsilon I_d) & \geq0. \end{align*} We now claim that if $$\left(\begin{array}{cc} A\\ & -B \end{array}\right)\preceq \operatorname{const.} \alpha\left(\begin{array}{cc} I_{d} & -I_{d}\\ -I_{d} & I_{d} \end{array}\right),$$ then \begin{multline*} F(s,y,r^{\prime},\alpha(x-y)-\epsilon y,B-\epsilon I_d)-F(t,x,r,\alpha(x-y)+\epsilon x,A+\epsilon I_d)\\ \leq\rho\left(r^{\prime}-r\right)+\operatorname{const.}(\alpha\,|x-y|^{2}+\epsilon\,(1+|x|^{2}+|y|^{2})). \end{multline*} $\operatorname{const.}$ denotes some nonnegative constant. We leave this as an exercise to the reader (use the Lipschitz continuity and linear growth of $b$ and $\sigma$). Using this claim, \begin{align*} 0 & \leq F(s_{n},y_{n},v(s_{n},y_{n}),\alpha(x_{n}-y_{n})-\epsilon y_{n},B_{n}-\epsilon I_{d})\\ & \qquad-F(t_{n},x_{n},u(t_{n},x_{n}),\alpha(x_{n}-y_{n})+\epsilon x_{n},A_{n}+\epsilon I_{d})\\ & \leq\rho\,(v(s_{n},y_{n})-u(t_{n},x_{n}))+\operatorname{const.}\,(\varphi(x_{n},y_{n})+\epsilon)\\ & \leq\rho\,(-\delta+\nu+\epsilon|x^\nu|^{2})+\operatorname{const.}\,(\varphi_n+\epsilon) \end{align*} Taking the limit superior of both sides as $n\rightarrow\infty$ and moving some terms around, we get $$\delta\leq\operatorname{const.}\,(\nu+\epsilon+\epsilon|x^\nu|^{2})$$ where $\operatorname{const.}$ is not necessarily the same as it was above. Now, simply take $\epsilon$ small enough to arrive at a contradiction.

## Bibliography

1. Crandall, Michael G., Hitoshi Ishii, and Pierre-Louis Lions. "User’s guide to viscosity solutions of second order partial differential equations." Bulletin of the American Mathematical Society 27.1 (1992): 1-67.

## Optimal stopping II: a dynamic programming equation

The following is a continuation of a previous post on optimal stopping. In this post, we derive a dynamic programming equation (which turns out to be a partial differential equation (PDE) to be interpreted in the viscosity sense) for the optimal stopping problem.

As before, we consider a filtered probability space (with filtration $(\mathcal{F}_{t})_{t\geq0}$) satisfying the usual conditions, on which a standard Brownian motion $W_{t}$ is defined. Let $X_{s}^{t,x}$ denote the strong solution of the stochastic differential equation (SDE) $$dX_{s}=b(s,X_{s})ds+\sigma(s,X_{s})dW_{s}\text{ for }s>t\text{ and }X_{t}=x.$$ Let $T<\infty$ and $\mathscr{T}_{[t,T]}$ be the set of $[t,T]$ stopping times independent of $\mathcal{F}_{t}$. Consider the problem $$u(t,x)=\sup_{\tau\in\mathscr{T}_{[t,T]}}J(t,x;\tau)\text{ where }J(t,x;\tau)=\mathbb{E}\left[g(\tau,X_{\tau}^{t,x})\right]$$ and $g$ is some given function.

All assumptions of the previous post hold.

The PDE we will derive (in the viscosity sense) is $$\min\left\{ -\left(\partial_{t}+\mathcal{A}\right)u,u-g\right\} =0\text{ on }[0,T)\times\mathbb{R}^{d},\label{eq:pde}\tag{1}$$ where $\mathcal{A}$ is the infinitesimal generator of the SDE above. Let's now define the notion of viscosity solution for this specific problem:

Let $\mathcal{O}=[0,T)\times\mathbb{R}^{d}$. A locally bounded function $v\colon\mathcal{O}\rightarrow\mathbb{R}$ is a viscosity subsolution (resp. supersolution) of \eqref{eq:pde} if \begin{align*} & \min\left\{ -\left(\partial_{t}+\mathcal{A}\right)\varphi(t,x),(v^{*}-g)(t,x)\right\} \leq0\\ \text{(resp. } & \min\left\{ -\left(\partial_{t}+\mathcal{A}\right)\varphi(t,x),(v_{*}-g)(t,x)\right\} \geq0\text{)} \end{align*} for all $(t,x,\varphi)\in\mathcal{O}\times C^{1,2}(\mathcal{O})$ such that $(v^{*}-\varphi)(t,x)=\max_{\mathcal{O}}(v^{*}-\varphi)=0$ (resp. $(v_{*}-\varphi)(t,x)=\min_{\mathcal{O}}(v_{*}-\varphi)=0$) and the maximum (resp. minimum) is strict. We say $v$ is a viscosity solution of \eqref{eq:pde} if it is both a subsolution and supersolution of \eqref{eq:pde}.
Suppose $u\colon\mathcal{O}\rightarrow\mathbb{R}$ is locally bounded. Then, $u$ is a viscosity solution of \eqref{eq:pde}.
We first prove that $u$ is a subsolution. Let $(t,x,\varphi)\in\mathcal{O}\times C^{1,2}(\mathcal{O})$ be such that $$(u^{*}-\varphi)(t,x)=\max_{\mathcal{O}}(u^{*}-\varphi)=0$$ where the maximum is strict. Assume, in order to arrive at a contradiction, that $$\min\left\{ -\left(\partial_{t}+\mathcal{A}\right)\varphi(t,x),(u^{*}-g)(t,x)\right\} >0.$$ Equivalently, this can be expressed as $$(\varphi-g)(t,x)=(u^{*}-g)(t,x)>0\text{ and }-\left(\partial_{t}+\mathcal{A}\right)\varphi(t,x)>0.$$ By continuity, we can find $h>0$ (with $t+h<T$) and $\delta>0$ such that $$\varphi-g\geq\delta\text{ and }-\left(\partial_{t}+\mathcal{A}\right)\varphi\geq0\text{ on }\mathcal{N}_{h}=\left( (t-h,t+h)\times B_{h}(x) \right) \cap \mathcal{O}$$ where $B_{h}(x)$ is the ball of radius $h$ centred at $x$. Since $(t,x)$ is a strict maximizer, $$-\gamma=\max_{\partial\mathcal{N}_{h}}\left(u^{*}-\varphi\right)<0.$$ Let $(t_{n},x_{n})$ be a sequence in $\mathcal{O}$ such that $$(t_{n},x_{n})\rightarrow(t,x)\text{ and }u(t_{n},x_{n})\rightarrow u^{*}(t,x).$$ Let $$\theta_{n}=\inf\left\{ s>t_{n}\colon(s,X_{s}^{t_{n},x_{n}})\notin\mathcal{N}_{h}\right\} .$$ Note that for $n$ large enough, $(t_{n},X_{t_{n}}^{t_{n},x_{n}})=(t_{n},x_{n})\in\mathcal{N}_{h}$ (we will always assume $n$ is large enough for this to occur). Let $$\eta_{n}=u(t_{n},x_{n})-\varphi(t_{n},x_{n}).$$ Let $\tau_n\in\mathscr{T}_{[t_n,T]}$ be arbitrary. By Ito's lemma, \begin{align*} u(t_{n},x_{n}) & =\eta_{n}+\varphi(t_{n},x_{n})\\ & \begin{gathered}=\eta_{n}+\mathbb{E}\left[\varphi(\tau_{n}\wedge\theta_{n},X_{\tau_{n}\wedge\theta_{n}}^{t_{n},x_{n}})-\int_{t_{n}}^{\tau_{n}\wedge\theta_{n}}\left(\partial_{t}+\mathcal{A}\right)\varphi(s,X_{s}^{t_{n},x_{n}})ds\right]\\ +\mathbb{E}\left[\int_{t_{n}}^{\tau_{n}\wedge\theta_{n}}\nabla_{x}\varphi(s,X_{s}^{t_{n},x_{n}})\cdot\sigma(s,X_{s}^{t_{n},x_{n}})dW_{s}\right] \end{gathered} \\ & =\eta_{n}+\mathbb{E}\left[\varphi(\tau_{n}\wedge\theta_{n},X_{\tau_{n}\wedge\theta_{n}}^{t_{n},x_{n}})-\int_{t_{n}}^{\tau_{n}\wedge\theta_{n}}\left(\partial_{t}+\mathcal{A}\right)\varphi(s,X_{s}^{t_{n},x_{n}})ds\right]. \end{align*} The Ito integral vanishes due to $t\mapsto(t,X_{t}^{t_{n},x_{n}})$ being bounded on the interval $[t_{n},\tau_{n}\wedge\theta_{n}]$ so that $$u(t_{n},x_{n})\geq\eta_{n}+\mathbb{E}\left[\varphi(\tau_{n}\wedge\theta_{n},X_{\tau_{n}\wedge\theta_{n}}^{t_{n},x_{n}})\right].$$ Due to the inequalities established on $\mathcal{N}_{h}$, \begin{align*} u(t_n,x_n) & \geq\eta_n+\mathbb{E}\left[\varphi(\tau_n\wedge\theta_n,X_{\tau_n\wedge\theta_n}^{t_n,x_n})\right]\\ & =\eta_n+\mathbb{E}\left[\varphi(\tau_n,X_{\tau_n}^{t_n,x_n})\mathbf{1}_{\left\{ \tau_n <\theta_n\right\} }+\varphi(\theta_n,X_{\theta_n}^{t_n,x_n})\mathbf{1}_{\left\{ \tau_n \geq\theta_n \right\} }\right]\\ & \geq\eta_n+\mathbb{E}\left[\left(g(\tau_n,X_{\tau_n}^{t_n,x_n})+\delta\right)\mathbf{1}_{\left\{ \tau_n <\theta_n\right\} }+\left(u^{*}(\theta_n,X_{\theta_n}^{t_n,x_n})+\gamma\right)\mathbf{1}_{\left\{ \tau_n\geq\theta_n\right\} }\right]\\ & \geq\eta_n+\gamma\wedge\delta+\mathbb{E}\left[g(\tau_n,X_{\tau_n}^{t_n,x_n})\mathbf{1}_{\left\{ \tau_n<\theta_n\right\} }+u^{*}(\theta_n,X_{\theta_n}^{t_n,x_n})\mathbf{1}_{\left\{ \tau_n\geq\theta_n \right\} }\right]. \end{align*} Since $\tau_n\in\mathscr{T}_{[t_n,T]}$ is arbitrary and $\eta_n+\gamma\wedge\delta>0$ for $n$ sufficiently large, this contradicts the $\leq$ inequality in the dynamic programming principle established in the previous post.
We now prove that $u$ is a supersolution. The inequality $u-g\geq0$ follows from the value function since $$u(t,x)=\sup_{\tau\in\mathscr{T}_{[t,T]}}J(t,x;\tau)\geq J(t,x;t)=\mathbb{E}[g(t,X_{t}^{t,x})]=g(t,x).$$ Taking the lower semicontinuous envelope on both sides of the inequality, we get $u_{*}-g\geq0$ (recall that $g$ is presumed to be continuous). Let $(t,x,\varphi)\in\mathcal{O}\times C^{1,2}(\mathcal{O})$ be such that $$(u_{*}-\varphi)(t,x)=\min_{\mathcal{O}}(u_{*}-\varphi)=0.$$ Let $(t_{n},x_{n})$ be a sequence in $\mathcal{O}$ such that $$(t_{n},x_{n})\rightarrow(t,x)\text{ and }u(t_{n},x_{n})\rightarrow u_{*}(t,x).$$ Let $$\eta_{n}=u(t_{n},x_{n})-\varphi(t_{n},x_{n})$$ and $$h_{n}=\sqrt{\eta_{n}}\mathbf{1}_{\left\{ \eta_{n}\neq0\right\} }+\mathbf{1}_{\left\{ \eta_{n}=0\right\} }/n.$$ Also let $$\theta_{n}=\inf\left\{ s>t_{n}\colon(s,X_{s}^{t_{n},x_{n}})\notin[t_{n},t_{n}+h_{n})\times B_{1}(x)\right\}$$ where we always assume $n$ is large enough for $t_n+h_n < T$ and $x_n \in B_1(x)$. Calling upon the $\geq$ inequality in the dynamic programming principle established in the previous post (with $\theta=\theta_{n}$), we have $$\eta_{n}+\varphi(t_{n},x_{n})=u(t_{n},x_{n})\geq\mathbb{E}\left[u_{*}(\theta_{n},X_{\theta_{n}}^{t_{n},x_{n}})\right]\geq\mathbb{E}\left[\varphi(\theta_{n},X_{\theta_{n}}^{t_{n},x_{n}})\right].$$ Applying Ito's lemma and dividing by $h_{n}$ yields $$\frac{\eta_{n}}{h_{n}}\geq\mathbb{E}\left[\frac{1}{h_{n}}\int_{t_{n}}^{\theta_{n}}\left(\partial_{t}+\mathcal{A}\right)\varphi(s,X_{s}^{t_{n},x_{n}})ds\right].$$ As usual, the Ito integral has vanished due to $t\mapsto(t,X_{t}^{t_{n},x_{n}})$ being bounded on the interval $[t_{n},\theta_{n}]$. For any fixed sample $\omega$ in the sample space and $n$ sufficiently large, note that $\theta_{n}(\omega)=t_{n}+h_{n}$ (since $h_{n}\rightarrow0$). By the mean value theorem for integrals, the random variable in the expectation converges almost surely. Applying the dominated convergence theorem, we get \begin{align*} 0=\lim_{n\rightarrow\infty}\frac{\eta_{n}}{h_{n}} & \geq\lim_{n\rightarrow\infty}\mathbb{E}\left[\frac{1}{h_{n}}\int_{t_{n}}^{\theta_{n}}\left(\partial_{t}+\mathcal{A}\right)\varphi(s,X_{s}^{t_{n},x_{n}})ds\right]\\ & =\mathbb{E}\left[\lim_{n\rightarrow\infty}\frac{1}{h_{n}}\int_{t_{n}}^{\theta_{n}}\left(\partial_{t}+\mathcal{A}\right)\varphi(s,X_{s}^{t_{n},x_{n}})ds\right]\\ & =\mathbb{E}\left[\left(\partial_{t}+\mathcal{A}\right)\varphi(t,x)\right]\\ & =\left(\partial_{t}+\mathcal{A}\right)\varphi(t,x). \end{align*} Multiplying both sides of the inequality by $-1$ yields the desired result.

## Optimal stopping I: a dynamic programming principle

The following is an expository post in which a dynamic programming principle is derived for an optimal stopping problem. The exposition is inspired by a proof in N. Touzi's textbook [1], an invaluable resource.

Before we begin, let's give some motivation. As an example, consider a risk-neutral stock given by the process $(X_t)_{t\geq 0}$. Optimal stopping describes the price of an American option paying off $g(X_t)$ at time $t$. Through this three-part series of posts, the reader is shown that the value of such an option is the unique viscosity solution of a partial differential equation (in particular, a single-obstacle variational inequality).

Consider a filtered probability space (with filtration $(\mathcal{F}_{t})_{t\geq0}$) satisfying the usual conditions, on which a standard Brownian motion $W_{t}$ is defined. Let $X_{s}^{t,x}$ denote the strong solution of the stochastic differential equation (SDE) $$dX_{s}=b(s,X_{s})ds+\sigma(s,X_{s})dW_{s}\text{ for }s>t\text{ and }X_{t}=x.$$ To ensure its existence and uniqueness, we need:

$b$ and $\sigma$ are Lipschitz and of linear growth in $x$ uniformly in $t$.

Let $T<\infty$ and $\mathscr{T}_{[t,T]}$ be the set of $[t,T]$ stopping times independent of $\mathcal{F}_{t}$. Consider the problem $$u(t,x)=\sup_{\tau\in\mathscr{T}_{[t,T]}}J(t,x;\tau)\text{ where }J(t,x;\tau)=\mathbb{E}\left[g(\tau,X_{\tau}^{t,x})\right]$$and $g$ is a given function. To ensure this is well-defined, we take the following:

$g:[0,T]\times\mathbb{R}^d$ is continuous and of quadratic growth (i.e., $|g(t,x)|\leq K(1+|x|^2)$ for some constant $K>0$ independent of $(t,x)$).

The above assumption implies that for all $s$ and $\tau\in\mathscr{T}_{[s,T]}$, the function $(t,x)\mapsto J(t,x;\tau)$ is continuous on $[0,s]\times\mathbb{R}^{d}$ by the following argument. Let $(t_{n}^\prime,x_{n}^\prime)_{n}$ be a sequence converging to $(t^\prime,x^\prime)\in[0,s]\times\mathbb{R}^{d}$. If we can show that $(g(\tau,X_{\tau}^{t_{n}^\prime,x_{n}^\prime}))_n$ is dominated by an integrable function, we can apply the dominated convergence theorem to get \begin{align*} \lim_{n\rightarrow\infty}J(t_{n}^\prime,x_{n}^\prime;\tau) & =\lim_{n\rightarrow\infty}\mathbb{E}\left[g(\tau,X_{\tau}^{t_{n}^\prime,x_{n}^\prime})\right]\\ & =\mathbb{E}\left[\lim_{n\rightarrow\infty}g(\tau,X_{\tau}^{t_{n}^\prime,x_{n}^\prime})\right]\\ & =\mathbb{E}\left[g(\tau,\lim_{n\rightarrow\infty}X_{\tau}^{t_{n}^\prime,x_{n}^\prime})\right]\\ & =\mathbb{E}\left[g(\tau,X_{\tau}^{t^\prime,x^\prime})\right]\\ & =J(t^\prime,x^\prime;\tau). \end{align*} Moreover, since $g$ is of quadratic growth, \begin{align*} \mathbb{E}\left[\left|g(\tau,X_{\tau}^{t_{n}^\prime,x_{n}^\prime})\right|\right] & \leq\mathbb{E}\left[K\left(1+\left|X_{\tau}^{t_{n}^\prime,x_{n}^\prime}\right|^{2}\right)\right]\\ & =K\left(1+\mathbb{E}\left[\left|X_{\tau}^{t_{n}^\prime,x_{n}^\prime}\right|^{2}\right]\right)\\ & \leq K_{0}\left(1+\left|x_{n}^\prime\right|^{2}\right) \end{align*} where $K_{0}$ can depend on $T$ (by the usual argument for Ito processes using Gronwall's lemma). Since $x_{n}^\prime\rightarrow x^\prime$, domination follows.

We denote by $f^{*}$ and $f_{*}$ the upper and lower semicontinuous envelopes of a function $f\colon Y\rightarrow[-\infty,\infty]$, where $Y$ is a given topological space.

Let $\theta\in\mathscr{T}_{[t,T]}$ be a stopping time such that $t < \theta < T$ and $X_{\theta}^{t,x}\in\mathbb{L}^{\infty}$. The following dynamic programming principle holds: \begin{align*} u(t,x) & \leq\sup_{\tau\in\mathscr{T}_{[t,T]}}\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }u^{*}(\theta,X_{\theta}^{t,x})\right].\\ u(t,x) & \geq\sup_{\tau\in\mathscr{T}_{[t,T]}}\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }u_{*}(\theta,X_{\theta}^{t,x})\right]. \end{align*}

Note that if $u$ is continuous, the above dynamic programming principle becomes, by virtue of $u=u_{*}=u^{*}$, $$u(t,x)=\sup_{\tau\in\mathscr{T}_{[t,T]}}\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }u(\theta,X_{\theta}^{t,x})\right].$$

Intuition behind proof: The $\leq$ inequality is established by the tower property (see the formal proof below). The $\geq$ inequality requires more work. Intuitively, we can take an $\epsilon$-optimal control $\tau^{\epsilon}(\theta)$ as follows: $$u(\theta,X_{\theta}^{t,x})\leq J(\theta,X_{\theta}^{t,x};\tau^{\epsilon}(\theta))+\epsilon.$$ Now, let $\tau$ be an arbitrary stopping time and $$\hat{\tau}=\tau\mathbf{1}_{\left\{ \tau<\theta\right\} }+\tau^{\epsilon}(\theta)\mathbf{1}_{\left\{ \tau\geq\theta\right\} }.$$ Then, \begin{align*} u(t,x) & \geq J(t,x;\hat{\tau})\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\tau^{\epsilon}(\theta),X_{\tau^{\epsilon}(\theta)}^{t,x})\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\tau^{\epsilon}(\theta),X_{\tau^{\epsilon}(\theta)}^{t,x})\mid\mathcal{F}_{\theta}\right]\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }J(\theta,X_{\theta}^{t,x};\tau^{\epsilon}(\theta))\right]\\ & \geq\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }u(\theta,X_{\theta}^{t,x})\right]-\epsilon. \end{align*} The desired result follows since $\tau$ and $\epsilon$ are arbitrary (take a sup over $\tau$ on both sides of the inequality). However, $\hat{\tau}$ is not a $\mathscr{T}_{[t,T]}$ stopping time, so the first inequality fails. In the proof below, this apparent issue is dealt with rigorously. We also mention another, perhaps less grave, issue: in the event that $u$ is not continuous, we cannot say anything about its measurability so that the expectation involving $u$ at a future time is ill-defined (this is the reason we use upper and lower semicontinuous envelopes in the above).

The $\leq$ inequality follows directly from the tower property: \begin{align*} J(t,x;\tau) & =\mathbb{E}\left[g(\tau,X_{\tau}^{t,x})\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\tau,X_{\tau}^{t,x})\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\tau,X_{\tau}^{t,x})\mid\mathcal{F}_{\theta}\right]\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }J(\theta,X_{\theta}^{t,x};\tau)\right]\\ & \leq\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }u^{*}(\theta,X_{\theta}^{t,x})\right]. \end{align*} Now, take the supremum over all stopping times $\tau$ on both sides to arrive at the desired result. The $\geq$ inequality requires more work. For brevity, let $\mathcal{O}=(t,T)\times\mathbb{R}^{d}$ for the remainder. Let $\epsilon>0$ and $\varphi\colon[0,T]\times\mathbb{R}^d\rightarrow\mathbb{R}$ be an upper semicontinuous function satisfying $u\geq\varphi$. For each $(s,y)\in \mathcal{O}$, there exists $\tau^{s,y}\in\mathscr{T}_{[s,T]}$ such that $$u(s,y)\leq J(s,y;\tau^{s,y})+\epsilon.$$ Using the upper semicontinuity of $\varphi$ and the continuity of $J$ (see above), we can find a family $(r^{s,y})$ of positive constants such that $$\epsilon\geq\varphi(t^{\prime},x^{\prime})-\varphi(s,y)\text{ and }J(s,y;\tau^{s,y})-J(t^{\prime},x^{\prime};\tau^{s,y})\leq\epsilon \text{ for }(t^{\prime},x^{\prime})\in B(s,y;r^{s,y})$$ where $$B(s,y;r)=(s-r,s)\times\left\{ x\in\mathbb{R}^d\colon\left|x-y\right| < r\right\}.$$ This seemingly strange choice for the sets above is justified later. Since $$\left\{ B(s,y;r^{s,y})\colon(s,y)\in \mathcal{O}\right\}$$ forms a cover of $\mathcal{O}$ by open sets, Lindelöf's lemma yields a countable subcover $\{B(t_{i},x_{i};r_{i})\}$. Let $C_{0}=\emptyset$, and $$A_{i+1}=B(t_{i+1},x_{i+1};r_{i+1})\setminus C_{i}\text{ where }C_{i+1}=A_{1}\cup\cdots\cup A_{i+1}\text{ for }i\geq0.$$ Note that the countable family $\{A_{i}\}$ is disjoint by construction, and that $X_{\theta}^{t,x}\in\cup_{i\geq1}A_{i}$ a.s. (recall that $X_{\theta}^{t,x}\in\mathbb{L}^{\infty}$ and $t < \theta < T$ by definition). Moreover, letting $\tau^{i}=\tau^{t_{i},x_{i}}$ for brevity, \begin{align*} J(t^{\prime},x^{\prime};\tau^{i}) & \geq J(t_{i},x_{i};\tau^{i})-\epsilon\\ & \geq u(t_{i},x_{i})-2\epsilon\\ & \geq\varphi(t_{i},x_{i})-2\epsilon\\ & \geq\varphi(t^{\prime},x^{\prime})-3\epsilon & \text{for }(t^{\prime},x^{\prime})\in B(t_{i},x_{i};r_{i})\supset A_{i}. \end{align*} Now, let $A^{n}=\cup_{i\leq n}A_{i}$ for $n\geq1$. Given a stopping time $\tau\in\mathscr{T}_{[t,T]}$, let $$\hat{\tau}^{n}=\tau\mathbf{1}_{\left\{ \tau<\theta\right\} }+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\left(T\mathbf{1}_{\mathcal{O}\setminus A^{n}}(\theta,X_{\theta}^{t,x})+\sum_{i=1}^{n}\tau^{i}\mathbf{1}_{A_{i}}(\theta,X_{\theta}^{t,x})\right).$$ In particular, since $B(t_{i},x_{i};r_{i})\supset A_{i}$ was picked such that for all $(t^{\prime},x^{\prime})\in B(t_{i},x_{i};r_{i})$, $t^{\prime}\leq t_{i}$, we have that $\hat{\tau}^n\in\mathscr{T}_{[t,T]}$. If we had instead chosen the open sets $B_{r_{i}}(t_{i},x_{i})$ to form our cover, we would not be able to use $\tau^{i}$ in the above definition of $\hat{\tau}^{n}$ without violating--roughly speaking--the condition that "stopping times cannot peek into the future." We first write \begin{align*} u(t,x) & \geq J(t,x;\hat{\tau}^{n})\\ & =\mathbb{E}\left[\left(\mathbf{1}_{\left\{ \tau<\theta\right\} }+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\mathbf{1}_{\mathcal{O}\setminus A^{n}}(\theta,X_{\theta}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right)g(\hat{\tau}^{n},X_{\hat{\tau}^{n}}^{t,x})\right] \end{align*} and consider the terms in the summation separately. It follows from our choice of $A^{n}$ and the tower property that \begin{align*} \mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\hat{\tau}^{n},X_{\hat{\tau}^{n}}^{t,x})\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right] & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\tau^{i},X_{\tau^{i}}^{t,x})\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right]\\ & =\mathbb{E}\left[\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\tau^{i},X_{\tau^{i}}^{t,x})\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\mid\mathcal{F}_{\theta}\right]\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }J(\theta,X_{\theta}^{t,x};\tau^{i})\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right]\\ & \geq\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\left(\varphi(\theta,X_{\theta}^{t,x})-3\epsilon\right)\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right]\\ & \geq\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\varphi(\theta,X_{\theta}^{t,x})\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right]-3\epsilon. \end{align*} Moreover, $$\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(\hat{\tau}^{n},X_{\hat{\tau}^{n}}^{t,x})\mathbf{1}_{\mathcal{O}\setminus A^{n}}(\theta,X_{\theta}^{t,x})=\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(T,X_{T}^{t,x})\mathbf{1}_{\mathcal{O}\setminus A^{n}}(\theta,X_{\theta}^{t,x})\leq|g(T,X_{T}^{t,x})|$$ and hence the dominated convergence theorem yields $$\lim_{n\rightarrow\infty}\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(T,X_{T}^{t,x})\mathbf{1}_{\mathcal{O}\setminus A^{n}}(\theta,X_{\theta}^{t,x})\right] =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }g(T,X_{T}^{t,x})\lim_{n\rightarrow\infty}\mathbf{1}_{\mathcal{O}\setminus A^{n}}(\theta,X_{\theta}^{t,x})\right]=0$$ since we can (a.s.) find $i$ such that $(\theta,X_{\theta}^{t,x})\in A_{i}$. By Fatou's lemma, \begin{align*} \liminf_{n\rightarrow\infty}\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\varphi(\theta,X_{\theta}^{t,x})\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right] & \geq\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\varphi(\theta,X_{\theta}^{t,x})\liminf_{n\rightarrow\infty}\mathbf{1}_{A^{n}}(\theta,X_{\theta}^{t,x})\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\varphi(\theta,X_{\theta}^{t,x})\right]. \end{align*} Note that we were able to use Fatou's lemma since $\varphi(\theta,X_\theta^{t,x})$ is bounded due to the assumption $X_{\theta}^{t,x}\in\mathbb{L}^{\infty}$. Since $\tau$ and $\epsilon$ were arbitrary, we have that $$u(t,x)\geq\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\varphi(\theta,X_{\theta}^{t,x})\right] \text{ for } \tau\in\mathscr{T}_{[t,T]}.$$ For the last step, let $r>0$ such that $|X_{\theta}^{t,x}|\leq r$ a.s. (recall $X_{\theta}^{t,x}\in\mathbb{L}^{\infty}$). We can find a sequence of continuous functions $(\varphi_{n})$ such that $\varphi_{n}\leq u_{*}$ and converges pointwise to $u_{*}$ on $[0,T]\times B_{r}(0)$. Letting $\varphi^N = \min_{n\geq N} \varphi_n$ denote a nondecreasing modification of this sequence, by the monotone convergence theorem, we get \begin{align*} u(t,x) & \geq\lim_{N\rightarrow\infty}\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }\varphi^N(\theta,X_{\theta}^{t,x})\right]\\ & =\mathbb{E}\left[\mathbf{1}_{\left\{ \tau<\theta\right\} }g(\tau,X_{\tau}^{t,x})+\mathbf{1}_{\left\{ \tau\geq\theta\right\} }u_{*}(\theta,X_{\theta}^{t,x})\right] & \text{ for } \tau \in \mathscr{T}_{[t,T]}.\end{align*} Now, simply take supremums on both sides to arrive at the desired result.

## Bibliography

1. Touzi, Nizar. Optimal stochastic control, stochastic target problems, and backward SDE. Vol. 29. Springer Science & Business Media, 2012.