Numerical methods for controlled stochastic delay systems.

*(English)*Zbl 1219.93001The book deals with numerical methods for nonlinear continuous time stochastic control systems with delays. The technique proposed here is an extension to the model with delays of the Markov chain approximation methods, which constitute a widely used and powerful class of numerical approximations for no-delay problems.

The usefulness of this work is due to the fact that in practical applications it is necessary to introduce numerous sources of delays in the modeling of realistic physical and biological systems, e.g. when dealing with ecological interactions, financial mathematics and mechanics. In particular the delays may have a particular relevance in the approximation of the optimal cost and control for such systems.

The book appears of particular importance for the practical solution to stochastic control problems for systems with delays. However it does not contain only results, but also ideas and suggestions so that it can be considered as an important source of inspiration for further work in this field.

The models considered are the diffusion and reflected diffusion processes, but the methods can be extended to cover also jump-diffusions. In particular, models with delays of boundary reflection terms have not been treated previously. As far as the cost functionals are concerned, the book covers the discounted cost, the stopping on reaching a boundary, the optimal stopping and the ergodic cases.

The general idea of the proposed method is based on the following steps. The Markov chain approximation is chosen so that the associated control or optimal control problem can be solved with a reasonable amount of computation and the approximation errors are acceptable. The optimal control for the approximating chain leads to a suitable continuous time interpolation such that a subsequence converges to an optimally controlled process of the original diffusion. No tools from PDE theory or classical numerical analysis are used.

The probabilistic approach just described is particularly useful for the case of delays since nothing is known about the analytical properties of the associated Bellman equation for nonlinear problems.

The proofs of convergence are based on weak convergence methods and use the techniques and results developed by the author and his co-authors for the no delay case. They consist in the interpolation of the Markov chain by a continuous-time process associated to a Bellman equation which is the same as for the chain and then showing that such process converges to an optimal diffusion for vanishing approximating parameter.

For numerical calculations it is useful that the system is bounded. There are two standard ways of bounding a state space: stopping a process on leaving a specified region or confining the process on a given region using a reflecting boundary. Both methods are treated in the book. Although only diffusion models with uncontrolled noise variance are explicitly considered, the methods can be extended to cover jump diffusions as well as controlled variance and jumps.

Notice also that for delay systems the state space must incorporate the path of the delayed quantities over the delay intervals and these ‘memory segments’ result in an infinite dimensional problem so that an effective numerical method has to approximate them in a finite way.

The book is organized as follows:

Chapter 1 illustrates the instabilities connected to delayed control actions and describes a class of examples for which there is a state transformation that reduces the problem to a finite-dimensional one. It appears that such class of examples is definitely rather narrow.

Chapter 2 provides background material on weak convergence and on the so-called martingale problem. The latter plays a relevant role in characterizing the limit of a weakly convergent sequence and, under this respect, there is no alternative to this method in the case of delay systems.

Chapter 3 describes the various controlled dynamical systems models used in the book. In view of their numerical approximation it is required that the paths take values in some compact subset \(G\) of a Euclidean space. To this end it is necessary to consider the corresponding processes stopped on first hitting the boundary of \(G\) or reflected by the boundary itself. Results on stochastic differential equations with path and control delays are then examined and finally relaxed controls and the Girsanov transformation are discussed here.

Chapter 4 is devoted to a set of model simplifications and approximations that have considerable promise when the path and/or control are delayed. It is worth noticing that a good numerical approximation depends heavily on the relative sensitivity of the model to small variations and this is due to the fact that the numerical algorithm itself is an approximation to the original model. For this reason, in the case of delay systems it is necessary to proceed with special attention to the choice of the numerical methods in view of the particular sensitivity of such systems to model variations. Under this respect the model simplifications suggested in this chapter are carefully analyzed and discussed.

Chapter 5 is concerned with the ergodic cost problem where only the path is delayed and it is shown that the issues of model complexity and simplification are particularly relevant in this case. Some important results on the ergodic theory for delay equations needed for the related numerical problems are derived here using techniques based on the Girsanov transformation and the Doeblin condition. It is also shown that the model simplifications developed in Chapter 4 can be used also for the ergodic cost problem.

Chapter 6 is concerned with the study of the methods proposed by the author and co-workers for the no-delay case, as described in the book by H. J. Kushner and P. Dupuis [Berlin-New York: Springer Verlag (2001; Zbl 0968.93005)]. Such methods are adapted in the following chapters to the control problem with delays.

The procedures proposed consist in approximating the controlled process by a simpler one such that the cost function for a fixed control or the optimal cost can be explicitly computed. The approximating process proposed here is a Markov chain and it is expected that, if the approximation is good enough and the cost function is also suitably approximated, then the optimal value for the approximating process and possibly the optimal control itself will be close to those for the original model.

The quality of the approximation to the diffusion model is guaranteed by imposing the so-called local consistency condition which requires that the conditional mean and covariance changes in the state of the approximating model are proportional to the drift and covariances of the original diffusion except for negligible terms.

The approximating chains for the no-delay model can be derived by two different, though asymptotically equivalent, methods called ‘explicit’ and ‘implicit’ methods. The second is very useful for memory requirement reduction in the case of delay systems.

The Markov chain approximations allow the development of suitable numerical algorithms for the control problems, while the proofs of convergence are based on continuous-time interpolations of the approximating chains.

Chapter 7 extends the Markov chain approximation methods introduced in Chapter 6 for the no-delay problems to the delay case. Similarly to the no-delay case the local consistency is the main assumption. Taking into account that the state of the problem is given by the ‘memory segment’ of the trajectory and (possibly) of the control path, the local consistency condition has now to consider such segments in the argument of the drift and diffusion functions. For this reason it turns out that the continuous-time interpolations are in this case more complicated than those of the no-delay case.

The algorithms suggested here for the delay problem are well motivated and possess interesting mathematical properties. Nevertheless, they should be considered as a first step offered also with the aim of stimulating further work in these subjects. Various numerical approximations to the original model are considered, paying particular attention to the important issues that should always be kept in mind when constructing approximation methods and numerical algorithms. The first is numerical feasibility and the second is concerned with the fact that a proof of convergence, as the approximating parameter goes to zero, must be available. It is also shown that variations of the implicit approximation method of Chapter 6 can be advantageous as far as the memory requirement problem is concerned.

Since the state space of the problem with delays is infinite dimensional it is necessary to work with approximations. This can be done in two ways. One consists in using a Markov chain approximation that converges to the original model in such a way that the optimal value functions converge to that of the original model. The other consists in first approximating the original model so that he resulting problem is finite-dimensional and then using a further approximation for numerical purposes. Both approaches are examined in the book and it turns out that for the second less memory is required.

Take into account that the quality of the approximation to the original model depends heavily on the sensitivity of the values and controls to the quantities that are being approximated. In fact, in case of a high sensitivity it is necessary to proceed with a finer approximation. This is often the case with delay systems since their behavior can be quite sensitive to the delay.

Chapter 8 adapts the approximation methods examined in Chapter 4 to the numerical problem, with the aim of reducing the memory requirement. To this end, when only the path is delayed, the periodic model is first introduced and then the periodic-Erlang model is employed with the result that a further memory reduction is obtained. It is also shown that the relaxed control representation can provide a useful approximation approach. This idea is developed for the periodic and periodic-Erlang models. It should be pointed out, however, that the memory requirement can become onerous if the reflection process and/or the Wiener process appear in delayed form or if the space of control values has more than a few points.

The proofs of the results stated in Chapter 7 and in the first part of Chapter 8 are also provided here. They follow the scheme consisting in the interpolation of the chain by a continuous-time process, then showing that the Bellman equation for the interpolation is the same as for the chain and finally that the continuous-time process converges to an optimal diffusion as the approximating parameter vanishes.

The final part of the chapter examines also the singular control and ergodic cost problems.

Finally, Chapter 9 considers situations where the memory requirements of the numerical procedures can be prohibitive. This happens in particular when the control and/or reflection terms are delayed and the control takes more than two or three values, since in this case it is necessary to keep track of the values of these quantities over the delay intervals and approximate them by finite-valued, discrete-time processes. The book considers a possible approach to reduce the memory requirement which consists in replacing the delay equation with a type of stochastic wave equation with no delays whose numerical solution provides the optimal costs and controls for the original model. The method appears promising for a consistent reduction of the required memory. However, it requires further work to gain a suitable level of numerical experience about its potentiality.

The usefulness of this work is due to the fact that in practical applications it is necessary to introduce numerous sources of delays in the modeling of realistic physical and biological systems, e.g. when dealing with ecological interactions, financial mathematics and mechanics. In particular the delays may have a particular relevance in the approximation of the optimal cost and control for such systems.

The book appears of particular importance for the practical solution to stochastic control problems for systems with delays. However it does not contain only results, but also ideas and suggestions so that it can be considered as an important source of inspiration for further work in this field.

The models considered are the diffusion and reflected diffusion processes, but the methods can be extended to cover also jump-diffusions. In particular, models with delays of boundary reflection terms have not been treated previously. As far as the cost functionals are concerned, the book covers the discounted cost, the stopping on reaching a boundary, the optimal stopping and the ergodic cases.

The general idea of the proposed method is based on the following steps. The Markov chain approximation is chosen so that the associated control or optimal control problem can be solved with a reasonable amount of computation and the approximation errors are acceptable. The optimal control for the approximating chain leads to a suitable continuous time interpolation such that a subsequence converges to an optimally controlled process of the original diffusion. No tools from PDE theory or classical numerical analysis are used.

The probabilistic approach just described is particularly useful for the case of delays since nothing is known about the analytical properties of the associated Bellman equation for nonlinear problems.

The proofs of convergence are based on weak convergence methods and use the techniques and results developed by the author and his co-authors for the no delay case. They consist in the interpolation of the Markov chain by a continuous-time process associated to a Bellman equation which is the same as for the chain and then showing that such process converges to an optimal diffusion for vanishing approximating parameter.

For numerical calculations it is useful that the system is bounded. There are two standard ways of bounding a state space: stopping a process on leaving a specified region or confining the process on a given region using a reflecting boundary. Both methods are treated in the book. Although only diffusion models with uncontrolled noise variance are explicitly considered, the methods can be extended to cover jump diffusions as well as controlled variance and jumps.

Notice also that for delay systems the state space must incorporate the path of the delayed quantities over the delay intervals and these ‘memory segments’ result in an infinite dimensional problem so that an effective numerical method has to approximate them in a finite way.

The book is organized as follows:

Chapter 1 illustrates the instabilities connected to delayed control actions and describes a class of examples for which there is a state transformation that reduces the problem to a finite-dimensional one. It appears that such class of examples is definitely rather narrow.

Chapter 2 provides background material on weak convergence and on the so-called martingale problem. The latter plays a relevant role in characterizing the limit of a weakly convergent sequence and, under this respect, there is no alternative to this method in the case of delay systems.

Chapter 3 describes the various controlled dynamical systems models used in the book. In view of their numerical approximation it is required that the paths take values in some compact subset \(G\) of a Euclidean space. To this end it is necessary to consider the corresponding processes stopped on first hitting the boundary of \(G\) or reflected by the boundary itself. Results on stochastic differential equations with path and control delays are then examined and finally relaxed controls and the Girsanov transformation are discussed here.

Chapter 4 is devoted to a set of model simplifications and approximations that have considerable promise when the path and/or control are delayed. It is worth noticing that a good numerical approximation depends heavily on the relative sensitivity of the model to small variations and this is due to the fact that the numerical algorithm itself is an approximation to the original model. For this reason, in the case of delay systems it is necessary to proceed with special attention to the choice of the numerical methods in view of the particular sensitivity of such systems to model variations. Under this respect the model simplifications suggested in this chapter are carefully analyzed and discussed.

Chapter 5 is concerned with the ergodic cost problem where only the path is delayed and it is shown that the issues of model complexity and simplification are particularly relevant in this case. Some important results on the ergodic theory for delay equations needed for the related numerical problems are derived here using techniques based on the Girsanov transformation and the Doeblin condition. It is also shown that the model simplifications developed in Chapter 4 can be used also for the ergodic cost problem.

Chapter 6 is concerned with the study of the methods proposed by the author and co-workers for the no-delay case, as described in the book by H. J. Kushner and P. Dupuis [Berlin-New York: Springer Verlag (2001; Zbl 0968.93005)]. Such methods are adapted in the following chapters to the control problem with delays.

The procedures proposed consist in approximating the controlled process by a simpler one such that the cost function for a fixed control or the optimal cost can be explicitly computed. The approximating process proposed here is a Markov chain and it is expected that, if the approximation is good enough and the cost function is also suitably approximated, then the optimal value for the approximating process and possibly the optimal control itself will be close to those for the original model.

The quality of the approximation to the diffusion model is guaranteed by imposing the so-called local consistency condition which requires that the conditional mean and covariance changes in the state of the approximating model are proportional to the drift and covariances of the original diffusion except for negligible terms.

The approximating chains for the no-delay model can be derived by two different, though asymptotically equivalent, methods called ‘explicit’ and ‘implicit’ methods. The second is very useful for memory requirement reduction in the case of delay systems.

The Markov chain approximations allow the development of suitable numerical algorithms for the control problems, while the proofs of convergence are based on continuous-time interpolations of the approximating chains.

Chapter 7 extends the Markov chain approximation methods introduced in Chapter 6 for the no-delay problems to the delay case. Similarly to the no-delay case the local consistency is the main assumption. Taking into account that the state of the problem is given by the ‘memory segment’ of the trajectory and (possibly) of the control path, the local consistency condition has now to consider such segments in the argument of the drift and diffusion functions. For this reason it turns out that the continuous-time interpolations are in this case more complicated than those of the no-delay case.

The algorithms suggested here for the delay problem are well motivated and possess interesting mathematical properties. Nevertheless, they should be considered as a first step offered also with the aim of stimulating further work in these subjects. Various numerical approximations to the original model are considered, paying particular attention to the important issues that should always be kept in mind when constructing approximation methods and numerical algorithms. The first is numerical feasibility and the second is concerned with the fact that a proof of convergence, as the approximating parameter goes to zero, must be available. It is also shown that variations of the implicit approximation method of Chapter 6 can be advantageous as far as the memory requirement problem is concerned.

Since the state space of the problem with delays is infinite dimensional it is necessary to work with approximations. This can be done in two ways. One consists in using a Markov chain approximation that converges to the original model in such a way that the optimal value functions converge to that of the original model. The other consists in first approximating the original model so that he resulting problem is finite-dimensional and then using a further approximation for numerical purposes. Both approaches are examined in the book and it turns out that for the second less memory is required.

Take into account that the quality of the approximation to the original model depends heavily on the sensitivity of the values and controls to the quantities that are being approximated. In fact, in case of a high sensitivity it is necessary to proceed with a finer approximation. This is often the case with delay systems since their behavior can be quite sensitive to the delay.

Chapter 8 adapts the approximation methods examined in Chapter 4 to the numerical problem, with the aim of reducing the memory requirement. To this end, when only the path is delayed, the periodic model is first introduced and then the periodic-Erlang model is employed with the result that a further memory reduction is obtained. It is also shown that the relaxed control representation can provide a useful approximation approach. This idea is developed for the periodic and periodic-Erlang models. It should be pointed out, however, that the memory requirement can become onerous if the reflection process and/or the Wiener process appear in delayed form or if the space of control values has more than a few points.

The proofs of the results stated in Chapter 7 and in the first part of Chapter 8 are also provided here. They follow the scheme consisting in the interpolation of the chain by a continuous-time process, then showing that the Bellman equation for the interpolation is the same as for the chain and finally that the continuous-time process converges to an optimal diffusion as the approximating parameter vanishes.

The final part of the chapter examines also the singular control and ergodic cost problems.

Finally, Chapter 9 considers situations where the memory requirements of the numerical procedures can be prohibitive. This happens in particular when the control and/or reflection terms are delayed and the control takes more than two or three values, since in this case it is necessary to keep track of the values of these quantities over the delay intervals and approximate them by finite-valued, discrete-time processes. The book considers a possible approach to reduce the memory requirement which consists in replacing the delay equation with a type of stochastic wave equation with no delays whose numerical solution provides the optimal costs and controls for the original model. The method appears promising for a consistent reduction of the required memory. However, it requires further work to gain a suitable level of numerical experience about its potentiality.

Reviewer: Giovanni Di Masi (Padova)

##### MSC:

93-02 | Research exposition (monographs, survey articles) pertaining to systems and control theory |

93E20 | Optimal stochastic control |

93E25 | Computational methods in stochastic control (MSC2010) |

34K50 | Stochastic functional-differential equations |

34K28 | Numerical approximation of solutions of functional-differential equations (MSC2010) |

65C30 | Numerical solutions to stochastic differential and integral equations |

60J75 | Jump processes (MSC2010) |