Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions

Authors: Emmanuel Gobet and Plamen Turkedjiev
Journal: Math. Comp. 85 (2016), 1359-1391
MSC (2010): Primary 49L20, 62Jxx, 65C30, 93E24
Published electronically: August 6, 2015
MathSciNet review: 3454368
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We design a numerical scheme for solving the Multi-step Forward Dynamic Programming (MDP) equation arising from the time-discretization of backward stochastic differential equations. The generator is assumed to be locally Lipschitz, which includes some cases of quadratic drivers. When the large sequence of conditional expectations is computed using empirical least-squares regressions, under general conditions we establish an upper bound error as the average, rather than the sum, of local regression errors only, suggesting that our error estimation is tight. Despite the nested regression problems, the interdependency errors are justified to be at most of the order of the statistical regression errors (up to logarithmic factor). Finally, we optimize the algorithm parameters, depending on the dimension and on the smoothness of value functions, in the limit as the time mesh size goes to zero and we compute the complexity needed to achieve a given accuracy. Numerical experiments are presented illustrating theoretical convergence estimates.

References [Enhancements On Off] (What's this?)

  • [1] Vlad Bally, Gilles Pagès, and Jacques Printems, A quantization tree method for pricing and hedging multidimensional American options, Math. Finance 15 (2005), no. 1, 119-168. MR 2116799 (2005k:91142),
  • [2] Tarik Ben Zineb and Emmanuel Gobet, Preliminary control variates to improve empirical regression methods, Monte Carlo Methods Appl. 19 (2013), no. 4, 331-354. MR 3139313,
  • [3] Christian Bender and Robert Denk, A forward scheme for backward SDEs, Stochastic Process. Appl. 117 (2007), no. 12, 1793-1812. MR 2437729 (2009d:65012),
  • [4] Christian Bender and Thilo Moseler, Importance sampling for backward SDEs, Stoch. Anal. Appl. 28 (2010), no. 2, 226-253. MR 2739557 (2012a:65015),
  • [5] C. Bender and J. Steiner, Least-squares Monte Carlo for BSDEs, Numerical Methods in Finance (R. Carmona, P. Del Moral, P. Hu, and N. Oudjane, eds.), Series: Springer Proceedings in Mathematics, Vol. 12, 2012, pp. 257-289.
  • [6] E. Benhamou, E. Gobet, and M. Miri, Smart expansion and fast calibration for jump diffusions, Finance Stoch. 13 (2009), no. 4, 563-589. MR 2519844 (2010j:60209),
  • [7] Bruno Bouchard and Nizar Touzi, Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations, Stochastic Process. Appl. 111 (2004), no. 2, 175-206. MR 2056536 (2005b:65007),
  • [8] Philippe Briand and Céline Labart, Simulation of BSDEs by Wiener chaos expansion, Ann. Appl. Probab. 24 (2014), no. 3, 1129-1171. MR 3199982,
  • [9] J. F. Chassagneux and A. Richou, Numerical simulation of quadratic BSDEs, Available at (2013).
  • [10] Dan Crisan and François Delarue, Sharp derivative bounds for solutions of degenerate semi-linear partial differential equations, J. Funct. Anal. 263 (2012), no. 10, 3024-3101. MR 2973334,
  • [11] D. Crisan and K. Manolarakis, Solving backward stochastic differential equations using the cubature method: application to nonlinear pricing, SIAM J. Financial Math. 3 (2012), no. 1, 534-571. MR 2968045,
  • [12] F. Delarue and G. Guatteri, Weak existence and uniqueness for forward-backward SDEs, Stochastic Process. Appl. 116 (2006), no. 12, 1712-1742. MR 2307056 (2008b:60125),
  • [13] N. El Karoui, S. Hamadène, and A. Matoussi, Backward stochastic differential equations and applications, Indifference Pricing: Theory and Applications (R. Carmona, ed.), Springer-Verlag, 2008, pp. 267-320.
  • [14] N. El Karoui, S. Peng, and M. C. Quenez, Backward stochastic differential equations in finance, Math. Finance 7 (1997), no. 1, 1-71. MR 1434407 (98d:90030),
  • [15] Christel Geiss, Stefan Geiss, and Emmanuel Gobet, Generalized fractional smoothness and $ L_p$-variation of BSDEs with non-Lipschitz terminal condition, Stochastic Process. Appl. 122 (2012), no. 5, 2078-2116. MR 2921973,
  • [16] Emmanuel Gobet and Céline Labart, Error expansion for the discretization of backward stochastic differential equations, Stochastic Process. Appl. 117 (2007), no. 7, 803-829. MR 2330720 (2008h:60279),
  • [17] Emmanuel Gobet and Céline Labart, Solving BSDE with adaptive control variate, SIAM J. Numer. Anal. 48 (2010), no. 1, 257-277. MR 2608369 (2011d:65017),
  • [18] E. Gobet and J. P. Lemor, Numerical simulation of BSDEs using empirical regression methods: theory and practice, Proceedings of the Fifth Colloquium on BSDEs (29th May - 1st June 2005, Shangai) (Available at, 2006.
  • [19] Emmanuel Gobet, Jean-Philippe Lemor, and Xavier Warin, A regression-based Monte Carlo method to solve backward stochastic differential equations, Ann. Appl. Probab. 15 (2005), no. 3, 2172-2202. MR 2152657 (2006c:60078),
  • [20] Emmanuel Gobet and Azmi Makhlouf, $ {\bf L}_2$-time regularity of BSDEs with irregular terminal functions, Stochastic Process. Appl. 120 (2010), no. 7, 1105-1132. MR 2639740 (2011k:60201),
  • [21] E. Gobet and P. Turkedjiev, Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions, Available on (2013).
  • [22] E. Gobet and P. Turkedjiev, Approximation of BSDEs using Malliavin weights and least-squares regression, To appear in Bernoulli (2015).
  • [23] Gene H. Golub and Charles F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720 (97g:65006)
  • [24] L. Gyorfi, M. Kohler, A. Krzyzak, and H. Walk, A Distribution-free Theory of Nonparametric Regression, Springer Series in Statistics, 2002.
  • [25] Ying Hu, Peter Imkeller, and Matthias Müller, Utility maximization in incomplete markets, Ann. Appl. Probab. 15 (2005), no. 3, 1691-1712. MR 2152241 (2006b:91071),
  • [26] Peter Imkeller and Gonçalo Dos Reis, Path regularity and explicit convergence rate for BSDE with truncated quadratic growth, Stochastic Process. Appl. 120 (2010), no. 3, 348-379. MR 2584898 (2011d:60162),
  • [27] Jean-Philippe Lemor, Emmanuel Gobet, and Xavier Warin, Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations, Bernoulli 12 (2006), no. 5, 889-916. MR 2265667 (2007m:60201),
  • [28] Jin Ma, Philip Protter, Jaime San Martín, and Soledad Torres, Numerical method for backward stochastic differential equations, Ann. Appl. Probab. 12 (2002), no. 1, 302-316. MR 1890066 (2003d:60126),
  • [29] T. Moseler, A Picard-type iteration for backward stochastic differential equations: convergence and importance sampling, Ph.D. thesis, Fachbereich Mathematik und Statistik der Universität Konstanz, 2010.
  • [30] Marc Potters, Jean-Philippe Bouchaud, and Dragan Sestovic, Hedged Monte-Carlo: low variance derivative pricing with objective probabilities, Phys. A 289 (2001), no. 3-4, 517-525. MR 1805291 (2001j:91100),
  • [31] A. Richou, étude théorique et numérique des équations différentielles stochastiques rétrogrades, Ph.D. thesis, Université Rennes 1, 2010.
  • [32] Adrien Richou, Numerical simulation of BSDEs with drivers of quadratic growth, Ann. Appl. Probab. 21 (2011), no. 5, 1933-1964. MR 2884055 (2012m:60149),
  • [33] Richard Rouge and Nicole El Karoui, Pricing via utility maximization and entropy, Math. Finance 10 (2000), no. 2, 259-276. INFORMS Applied Probability Conference (Ulm, 1999). MR 1802922 (2001m:91066),
  • [34] P. Turkedjiev, Numerical methods for backward stochastic differential equations of quadratic and locally Lipschitz type, Ph.D. thesis, Mathematisch-Naturwissenschaftlichen Fakultät II der Humboldt-Universität zu Berlin, available at, 2013.
  • [35] P. Turkedjiev, Two algorithms for the discrete time approximation of Markovian backward stochastic differential equations under local conditions, In revision for Electronic Journal of Probability, available on (2013).
  • [36] Jianfeng Zhang, A numerical scheme for BSDEs, Ann. Appl. Probab. 14 (2004), no. 1, 459-488. MR 2023027 (2004j:65015),

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 49L20, 62Jxx, 65C30, 93E24

Retrieve articles in all journals with MSC (2010): 49L20, 62Jxx, 65C30, 93E24

Additional Information

Emmanuel Gobet
Affiliation: Centre de Mathématiques Appliquées, Ecole Polytechnique and CNRS, Route de Saclay, F 91128 Palaiseau cedex, France

Plamen Turkedjiev
Affiliation: Centre de Mathématiques Appliquées, Ecole Polytechnique and CNRS, Route de Saclay, F 91128 Palaiseau cedex, France

Keywords: Backward stochastic differential equations, dynamic programming equation, empirical regressions, non-asymptotic error estimates
Received by editor(s): June 28, 2013
Received by editor(s) in revised form: July 6, 2013, March 18, 2014, and October 31, 2014
Published electronically: August 6, 2015
Additional Notes: This first author’s research was part of the Chair Financial Risks of the Risk Foundation and of the FiME Laboratory
A significant part of the second author’s research was done while at Humboldt University. This research benefited from the support of the Chair Finance and Sustainable Developement, under the aegis of Louis Bachelier Finance and Sustainable Growth Laboratory, a joint initiative with École Polytechnique.
An earlier unpublished version of this work was circulated under the title “Approximation of discrete BSDE using least-squares regression”, \url{}. The current version is shorter and includes significantly improved estimates.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society