A modified MSA for stochastic control problems

Stochastic control problems appear naturally in a range of applications in engineering, economics and finance. With the exception of very specific cases such as the linear-quadratic control problem in engineering or Merton portfolio optimization task in finance, stochastic control problems typically have no closed form solutions and have to be solved numerically. In this work, we consider a modification to the method of successive approximations (MSA), see Algorithm 1. The MSA is essentially a way of applying the Pontryagin’s optimality principle to get numerical solutions of stochastic control problems.

We will consider the continuous space, continuous time problem where the controlled system is modelled by an $\mathbb{R}^{d}$-valued diffusion process. Let $W$ be a $d^{\prime}$-dimensional Wiener martingale on a filtered probability space $(\Omega,\mathcal{F},(\mathcal{F}_{t})_{t\geq 0},\mathbb{P})$. We will provide exact assumptions we need in Section 2. For now, let us fix a finite time $T\in(0,\infty)$ and consider the controlled stochastic differential equation (SDE) for given measurable functions $b:[0,T]\times\mathbb{R}^{d}\times A\to\mathbb{R}^{d}$ and $\sigma:[0,T]\times\mathbb{R}^{d}\times A\rightarrow\mathbb{R}^{d\times d^{\prime}}$

Here $\alpha=(\alpha_{s})_{s\in[0,T]}$ is a control process belonging to the space of admissible controls $\mathcal{A}$, valued in a separable metric space $A$ and we will write $X^{\alpha}$ to denote the unique solution of (1) which starts from $x$ at time $0$ whilst being controlled by $\alpha$. Furthermore let $f:[0,T]\times\mathbb{R}^{d}\times A\to\mathbb{R}$ and $g:\mathbb{R}^{d}\to\mathbb{R}$ be given measurable functions and consider the gain functional

for all $x\in\mathbb{R}^{d}$ and $\alpha\in\mathcal{A}$. We want to solve the optimisation problem i.e. to find the optimal control $\alpha^{*}$ which achieves the minimum of (2) (or, if the infimum cannot be reached by $\alpha\in\mathcal{A}$ then an $\varepsilon$-optimal control $\alpha^{\varepsilon}\in\mathcal{A}$ such that $\inf_{\alpha\in\mathcal{A}}J(x,\alpha)\leq J(x,\alpha^{\varepsilon})+\varepsilon$).

In the present paper, we study an approach based on Pontryagin’s optimality principle, see e.g. [4], [7] or [25]. The main idea is to consider optimality conditions for controls of the problem (2). Given $b,\sigma$ and $f$ we define the Hamiltonian $\mathcal{H}:[0,T]\times\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}^{d\times d^{\prime}}\times A\rightarrow\mathbb{R}$ as

Consider for each $\alpha\in\mathcal{A}$, the BSDE, called the adjoint equation

It is well known from Pontryagin’s optimality principle that, if an admissible control $\alpha^{*}\in\mathcal{A}$ is optimal, $X^{\alpha^{*}}$ is the corresponding optimally controlled dynamic (1) and $(Y^{\alpha^{*}},Z^{\alpha^{*}})$ is the solution to the associated adjoint equation (4), then $\forall a\in A$ and $\forall s\in[0,T]$ the following holds

We now define the augmented Hamiltonian $\mathcal{\tilde{H}}:[0,T]\times\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}^{d\times d^{\prime}}\times A\times A\rightarrow\mathbb{R}$ for some $\rho\geq 0$ by

Notice that when $\rho=0$ we have exactly the definition of Hamiltonian (3). Given the augmented Hamiltonian, let us introduce the modified MSA in Algorithm 1 which consists of successive integrations of the state and adjoint systems and updates to the control. Notice that the backward SDE depends on the Hamiltonian $\mathcal{H}$, while the control update step comes from minimizing the augmented Hamiltonian $\tilde{\mathcal{H}}$.

The method of successive approximations (i.e. case $\rho=0$) for numerical solution of deterministic control problems was proposed already in [5]. Recent application of the modified MSA to a deep learning problem has been studied in [32], where they formulated the training of deep neural networks as an optimal control problem and introduced the modified method of successive approximations as an alternative training algorithm for deep learning. For us, the main motivation to explore the modified MSA for stochastic control problems is to obtain convergence, ideally with rate, of an iterative algorithm, applicable to problems with the control in the diffusion part of the controlled dynamics. This is in contrast to [36] where convergence rate of an the Bellman–Howard policy iteration is shown but only for control problems with no control in the diffusion part of the controlled dynamics.

In Lemma 2.3, which can be established using careful BSDE estimates, we can see the estimate on the change of $J$ when we do a minimization step of Hamiltonian as in (8). If the sum of the last three terms of (14) is bigger than the first term, then for classical MSA algorithm (i.e. case $\rho=0$) we cannot guarantee that we do an update of the control in optimal descent direction of $J$. That means that the method of successive approximations may diverge. To overcome this, we need to modify the algorithm in such way so that we ensure convergence. With this in mind the desirability of the the augmented Hamiltonian (6) for updating the control becomes clear, as long as it still characterises optimal controls like $\mathcal{H}$ does. Theorem 2.4 answers this question affirmatively which opens the way to the modified MSA. In Theorem 2.5 we show that the modified method of successive approximations, converges for arbitrary $T$, and in Corollary 2.6, we show logarithmic convergence rate for certain stochastic control problems.

We observe that the forward and backward dynamics in (7) are decoupled, due to the iteration used. Therefore, it can be efficiently approximated, even in high dimension, using deep learning methods, see [31] and [30]. However, the minimization step (8) might be computationally expensive for some problems. A possible approach circumventing this is to replace the full minimization of (8) by gradient descent. A continuous version of this gradient flow is analyzed in [37].

The main contributions of this paper are the probabilistic proof of convergence of the modified method of successive approximations and establishing convergence rate for a specific type of optimal control problems.

This paper is organised as follow: in Section 1.1 we compare our results with existing work. In Section 2 we state the assumptions and main results. In Section 3 we collect all proofs. Finally, in Appendix A we recall an auxiliary lemma which is needed in the proof of Corollary 2.6.

We fix a finite horizon $T\in(0,\infty)$. Let $A$ be a separable metric space. This is the space where the control processes $\alpha$ take values. We fix a filtered probability space $(\Omega,\mathcal{F},\mathbb{F}=(\mathcal{F}_{t})_{0\leq t\leq T},\mathbb{P})$. Let $W=(W_{t})_{t\in[0,T]}$ be a $d^{\prime}$-dimensional Wiener martingale on this space. By $\mathbb{E}_{t}$ we denote the conditional expectation with respect to $\mathcal{F}_{t}$. Let $|\cdot|$ denote any norm in a finite dimensional Euclidean space. By $\|\cdot\|_{L^{\infty}}$ we denote the norm in $L^{\infty}(\Omega)$. Let $\|Z\|_{\mathbb{H}^{\infty}}:=\text{ess}\sup_{(t,\omega)}|Z_{t}(\omega)|$ for any predictable process $Z$. We understand the following as $D_{x}\sigma=D_{x_{l}}\sigma^{ij}$, $D_{x}^{2}b=D^{2}_{x_{l}x_{n}}b^{i}$ and $D_{x}^{2}\sigma=D^{2}_{x_{l}x_{n}}\sigma^{ij}$, where $i,l,n=1,2,\dots,d$ and $j=1,2,\dots,d^{\prime}$. By $Z^{\top}$ we denote the transpose of $Z$. The state of the system is governed by the controlled SDE (1) . The corresponding adjoint equation satisfies (4).

Clearly the assumption (12) implies that $\forall x,x^{\prime}\in\mathbb{R}^{d},\forall a\in A,\forall t\in[0,T]$ we have

The assumption that $D_{x}^{2}\sigma(t,x,a)=0$ $\forall x\in\mathbb{R}^{d},\forall a\in A,\forall t\in[0,T]$ is needed so that (21), in the proof of Lemma 3.1, holds. Without this assumption (21) would only hold if we could show that $\|Z^{\alpha}\|_{\mathbb{H}^{\infty}}<\infty$. Without additional regularization of the control problem this is impossible. Indeed, with [13, Proposition 5.3] we see that $Z^{\alpha}_{t}$ is a version of $D_{t}Y_{t}^{\alpha}$ (the Malliavin derivative of $Y_{t}^{\alpha}$) and $D_{t}Y_{t}^{\alpha}$ itself satisfies an a linear BSDE. However, to obtain the estimates using this representation, one term that arises is $D_{t}\alpha_{s}$ where $t\in[0,T]$ and $s\in[t,T]$. So we would need $\text{ess}\sup_{\omega\in\Omega,t\in(0,T),s\in(t,T)}|D_{t}\alpha_{s}(\omega)|<\infty$. This is not necessarily the case here.

Under these assumptions, we can obtain the following estimate.

The proof will be given in Section 3. We now state a necessary condition for optimality for the augmented Hamiltonian.

The proof of Theorem 2.4 will come in Section 3. We are now ready to present the main result of the paper.

Theorem 2.5 will be proved in Section 3. It can be seen from the proof that $\rho$ needs to be two times larger than the constant appearing in Lemma 2.3, which itself depends increases with $T,d$ and constants from Assumption 2.1 and 2.2.

We cannot guarantee that the Algorithm 1 converges to the optimal control which minimizes (2), since the extended Pontryagin’s optimality principle, see Theorem 2.4, is the necessary condition for optimality. The sufficient condition for optimality tells us that to get the optimal control we need to assume convexity of the Hamiltonian in state and control variables, and need to assume convexity of the terminal cost function. To that end, we need to assume convexity of $b,\sigma,f$ and $g$ in $x$ and $a$.

In the following corollary, we show that under a particular setting of the problem we have logarithmic convergence of the modified method of successive approximations to the true solution of the problem.

The proof of Corollary 2.6 will be given in Section 3. Theorem 2.5 and Corollary 2.6 are extensions of the result in [5] to the stochastic case.

We start working towards the proof of Theorem 2.5. Recall the adjoint equation for an admissible control $\alpha$:

From now on, we shall use Einstein notation, so that repeated indices in a single term imply summation over all the values of that index.