A segment-wise dynamic programming algorithm for BSDEs

Abstract

We introduce and analyze a family of linear least-squares Monte Carlo schemes for backward SDEs, which interpolate between the one-step dynamic programming scheme of Lemor, Warin, and Gobet (Bernoulli, 2006) and the multi-step dynamic programming scheme of Gobet and Turkedjiev (Mathematics of Computation, 2016). Our algorithm approximates conditional expectations over segments of the time grid. We discuss the optimal choice of the segment length depending on the ‘smoothness’ of the problem and show that, in typical situations, the complexity can be reduced compared to the state-of-the-art multi-step dynamic programming scheme.

Keywords

Backward stochastic differential equations / Empirical regression / Dynamic programming / Monte Carlo methods.

References

[1] Bender, C. and Denk, R., A forward scheme for backward SDEs, Stochastic Processes and their Applications, 2007, 117(12): 1793-1812.

[2] Bouchard, B. and Touzi, N., Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations, Stochastic Processes and their Applications, 2004, 111(2): 175-206.

[3] Chessari, J., Kawai, R., Shinozaki, Y. and Yamada, T., Numerical methods for backward stochastic differential equations: A survey, Probability Surveys, 2023, 20: 486-567.

[4] Crisan, D. and Delarue, F., Sharp derivative bounds for solutions of degenerate semi-linear partial differential equations, Journal of Functional Analysis, 2012, 263(10): 3024-3101.

[5] Douglas, J., Ma, J. and Protter, P., Numerical methods for forward-backward stochastic differential equations, The Annals Applied Probability, 1996, 6(3): 940-968.

[6] E, W., Hutzenthaler, M., Jentzen, A. and Kruse, T., Multilevel Picard iterations for solving smooth semilinear parabolic heat equations, Partial Differential Equations and Applications, 2021, 2: 80.

[7] El Karoui, N., Peng, S. and Quenez, M. C., Backward stochastic differential equations in finance, Mathematical Finance, 1997, 7(1): 1-71.

[8] Gobet, E. and Labart, C., Error expansion for the discretization of backward stochastic differential equations, Stochastic Processes and their Applications, 2007, 117(7): 803-829.

[9] Gobet, E., Lemor, J.-P. and Warin, X., A regression-based Monte Carlo method to solve backward stochastic differential equations, The Annals Applied Probability, 2005, 15(3): 2172-2202.

[10] Gobet, E., López-Salas, J. G., Turkedjiev, P. and Vázquez, C., Stratified regression Monte-Carlo scheme for semilinear PDEs and BSDEs with large scale parallelization on GPUs, SIAM Journal on Scientific Computing, 2016, 38(6): C652-C677.

[11] Gobet, E. and Turkedjiev, P., Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions, Mathematics of Computation, 2016, 85(299): 1359-1391.

[12] Guyon, J. and Henry-Labordère, P., Nonlinear Option Pricing, Chapman & Hall/CRC Financial Mathematics Series, CRC Press, Boca Raton, 2014.

[13] Györfi, L., Kohler, M., Krzyżak, A. and Walk, H., A Distribution-Free Theory of Nonparametric Regression, Springer Series in Statistics, Springer, New York, 2002.

[14] Hutzenthaler, M., Jentzen, A., Kruse, T. and Nguyen, T. A., Overcoming the curse of dimensionality in the numerical approximation of backward stochastic differential equations, Journal of Numerical Mathematics, 2023, 31(1): 1-28.

[15] Kallenberg, O., Foundations of Modern Probability, Springer, Cham, 1997.

[16] Karatzas, I. and Shreve, S., Brownian Motion and Stochastic Calculus, Springer, New York, 2012.

[17] Kloeden, P. E. and Platen, E., Numerical Solution of Stochastic Differential Equations, Springer, Berlin, Heidelberg, 1992.

[18] Lemor, J.-P., Gobet, E. and Warin, X., Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations, Bernoulli, 2006, 12(5): 889-916.

[19] Ma, J., Protter, P. and Yong, J. M., Solving forward-backward stochastic differential equations explicitly—a four step scheme, Probability Theory and Related Fields, 1994, 98(3): 339-359.

[20] Ma, J., Shen, J. and Zhao, Y., On numerical approximations of forward-backward stochastic differential equations, SIAM Journal on Numerical Analysis, 2008, 46(5): 2636-2661.

[21] Milstein, G. N. and Tretyakov, M. V., Numerical algorithms for forward-backward stochastic differential equations, SIAM Journal on Scientific Computing, 2006, 28(2): 561-582.

[22] Pardoux, E. and Peng, S., Backward stochastic differential equations and quasilinear parabolic partial differential equations, In: RozovskiiB. L. and SowersR. B.( Stochastic Partial Differential Equations and their Applications (Charlotte, NC, 1991),eds.), Lecture Notes in Control and Information Sciences, Springer, Berlin, 1992, 176: 200-217.

[23] Zhang, J., A numerical scheme for BSDEs, The Annals Applied Probability, 2004, 14(1): 459-488.