IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1908.01602.html
   My bibliography  Save this paper

Solving high-dimensional optimal stopping problems using deep learning

Author

Listed:
  • Sebastian Becker
  • Patrick Cheridito
  • Arnulf Jentzen
  • Timo Welti

Abstract

Nowadays many financial derivatives, such as American or Bermudan options, are of early exercise type. Often the pricing of early exercise options gives rise to high-dimensional optimal stopping problems, since the dimension corresponds to the number of underlying assets. High-dimensional optimal stopping problems are, however, notoriously difficult to solve due to the well-known curse of dimensionality. In this work, we propose an algorithm for solving such problems, which is based on deep learning and computes, in the context of early exercise option pricing, both approximations of an optimal exercise strategy and the price of the considered option. The proposed algorithm can also be applied to optimal stopping problems that arise in other areas where the underlying stochastic process can be efficiently simulated. We present numerical results for a large number of example problems, which include the pricing of many high-dimensional American and Bermudan options, such as Bermudan max-call options in up to 5000 dimensions. Most of the obtained results are compared to reference values computed by exploiting the specific problem design or, where available, to reference values from the literature. These numerical results suggest that the proposed algorithm is highly effective in the case of many underlyings, in terms of both accuracy and speed.

Suggested Citation

  • Sebastian Becker & Patrick Cheridito & Arnulf Jentzen & Timo Welti, 2019. "Solving high-dimensional optimal stopping problems using deep learning," Papers 1908.01602, arXiv.org, revised Aug 2021.
    • Handle: RePEc:arx:papers:1908.01602
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1908.01602
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Leif Andersen & Mark Broadie, 2004. "Primal-Dual Simulation Algorithm for Pricing Multidimensional American Options," Management Science, INFORMS, vol. 50(9), pages 1222-1234, September.
    2. Masaaki Fujii & Akihiko Takahashi & Masayuki Takahashi, 2017. "Asymptotic Expansion as Prior Knowledge in Deep Learning Method for high dimensional BSDEs," Papers 1710.07030, arXiv.org, revised Mar 2019.
    3. Longstaff, Francis A & Schwartz, Eduardo S, 2001. "Valuing American Options by Simulation: A Simple Least-Squares Approach," The Review of Financial Studies, Society for Financial Studies, vol. 14(1), pages 113-147.
    4. David A. Goldberg & Yilun Chen, 2018. "Polynomial time algorithm for optimal stopping with fixed accuracy," Papers 1807.02227, arXiv.org, revised May 2024.
    5. J'er^ome Lelong, 2019. "Pricing path-dependent Bermudan options using Wiener chaos expansion: an embarrassingly parallel approach," Papers 1901.05672, arXiv.org, revised Jul 2020.
    6. Michael Kohler, 2008. "A regression-based smoothing spline Monte Carlo algorithm for pricing American options in discrete time," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 92(2), pages 153-178, May.
    7. J'er^ome Lelong, 2016. "Pricing American options using martingale bases," Papers 1604.03317, arXiv.org.
    8. Carriere, Jacques F., 1996. "Valuation of the early-exercise price for options using simulations and nonparametric regression," Insurance: Mathematics and Economics, Elsevier, vol. 19(1), pages 19-30, December.
    9. Bouchard, Bruno & Touzi, Nizar, 2004. "Discrete-time approximation and Monte-Carlo simulation of backward stochastic differential equations," Stochastic Processes and their Applications, Elsevier, vol. 111(2), pages 175-206, June.
    10. Bally, Vlad & Pagès, Gilles, 2003. "Error analysis of the optimal quantization algorithm for obstacle problems," Stochastic Processes and their Applications, Elsevier, vol. 106(1), pages 1-40, July.
    11. Denis Belomestny & Christian Bender & John Schoenmakers, 2009. "True Upper Bounds For Bermudan Products Via Non‐Nested Monte Carlo," Mathematical Finance, Wiley Blackwell, vol. 19(1), pages 53-71, January.
    12. Lord, Roger & Fang, Fang & Bervoets, Frank & Oosterlee, Kees, 2007. "A fast and accurate FFT-based method for pricing early-exercise options under Lévy processes," MPRA Paper 1952, University Library of Munich, Germany.
    13. Bernard Lapeyre & Jérôme Lelong, 2020. "Neural network regression for Bermudan option pricing," Working Papers hal-02183587, HAL.
    14. Christian Bender & Nikolaus Schweizer & Jia Zhuo, 2017. "A Primal–Dual Algorithm For Bsdes," Mathematical Finance, Wiley Blackwell, vol. 27(3), pages 866-901, July.
    15. Christian Bender & Anastasia Kolodko & John Schoenmakers, 2008. "Enhanced policy iteration for American options via scenario selection," Quantitative Finance, Taylor & Francis Journals, vol. 8(2), pages 135-146.
    16. Mark Broadie & Menghui Cao, 2008. "Improved lower and upper bound algorithms for pricing American options by simulation," Quantitative Finance, Taylor & Francis Journals, vol. 8(8), pages 845-861.
    17. Céline Labart & Jérôme Lelong, 2011. "A Parallel Algorithm for solving BSDEs - Application to the pricing and hedging of American options," Working Papers hal-00567729, HAL.
    18. Martin B. Haugh & Leonid Kogan, 2004. "Pricing American Options: A Duality Approach," Operations Research, INFORMS, vol. 52(2), pages 258-270, April.
    19. Anastasia Kolodko & John Schoenmakers, 2006. "Iterative construction of the optimal Bermudan stopping time," Finance and Stochastics, Springer, vol. 10(1), pages 27-49, January.
    20. Denis Belomestny & John Schoenmakers & Fabian Dickmann, 2013. "Multilevel dual approach for pricing American style derivatives," Finance and Stochastics, Springer, vol. 17(4), pages 717-742, October.
    21. Barraquand, Jérôme & Martineau, Didier, 1995. "Numerical Valuation of High Dimensional Multivariate American Securities," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 30(3), pages 383-405, September.
    22. Sören Christensen, 2014. "A Method For Pricing American Options Using Semi-Infinite Linear Programming," Mathematical Finance, Wiley Blackwell, vol. 24(1), pages 156-172, January.
    23. Nan Chen & Paul Glasserman, 2007. "Additive and multiplicative duals for American option pricing," Finance and Stochastics, Springer, vol. 11(2), pages 153-179, April.
    24. Masaaki Fujii & Akihiko Takahashi & Masayuki Takahashi, 2019. "Asymptotic Expansion as Prior Knowledge in Deep Learning Method for high dimensional BSDEs (Forthcoming in Asia-Pacific Financial Markets)," CARF F-Series CARF-F-456, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.
    25. Ludovic Gouden`ege & Andrea Molent & Antonino Zanette, 2019. "Variance Reduction Applied to Machine Learning for Pricing Bermudan/American Options in High Dimension," Papers 1903.11275, arXiv.org, revised Dec 2019.
    26. Jérôme Lelong, 2019. "Pricing path-dependent Bermudan options using Wiener chaos expansion: an embarrassingly parallel approach," Working Papers hal-01983115, HAL.
    27. Justin Sirignano & Konstantinos Spiliopoulos, 2017. "DGM: A deep learning algorithm for solving partial differential equations," Papers 1708.07469, arXiv.org, revised Sep 2018.
    28. Masaaki Fujii & Akihiko Takahashi & Masayuki Takahashi, 2019. "Asymptotic Expansion as Prior Knowledge in Deep Learning Method for High dimensional BSDEs," Asia-Pacific Financial Markets, Springer;Japanese Association of Financial Economics and Engineering, vol. 26(3), pages 391-408, September.
    29. Jèôme Barraquand, 1995. "Numerical Valuation of High Dimensional Multivariate European Securities," Management Science, INFORMS, vol. 41(12), pages 1882-1891, December.
    30. L. C. G. Rogers, 2002. "Monte Carlo valuation of American options," Mathematical Finance, Wiley Blackwell, vol. 12(3), pages 271-286, July.
    31. Broadie, Mark & Glasserman, Paul, 1997. "Pricing American-style securities using simulation," Journal of Economic Dynamics and Control, Elsevier, vol. 21(8-9), pages 1323-1352, June.
    32. Bernard Lapeyre & J'er^ome Lelong, 2019. "Neural network regression for Bermudan option pricing," Papers 1907.06474, arXiv.org, revised Dec 2020.
    33. Daniel R. Jiang & Warren B. Powell, 2015. "An Approximate Dynamic Programming Algorithm for Monotone Value Functions," Operations Research, INFORMS, vol. 63(6), pages 1489-1511, December.
    34. Alexander V. Kulikov & Pavel P. Gusyatnikov, 2016. "Stopping Times for Fractional Brownian Motion," Lecture Notes in Economics and Mathematical Systems, in: Raquel J. Fonseca & Gerhard-Wilhelm Weber & João Telhada (ed.), Computational Management Science, edition 1, pages 195-200, Springer.
    35. Vijay V. Desai & Vivek F. Farias & Ciamac C. Moallemi, 2012. "Pathwise Optimization for Optimal Stopping Problems," Management Science, INFORMS, vol. 58(12), pages 2292-2308, December.
    36. Egorova, Yana, 2017. "Инвестирование Денежных Средств В Условиях Экономического Кризиса В 2017 Году," MPRA Paper 77648, University Library of Munich, Germany.
    37. Denis Belomestny, 2011. "Pricing Bermudan options by nonparametric regression: optimal rates of convergence for lower estimates," Finance and Stochastics, Springer, vol. 15(4), pages 655-683, December.
    38. Longstaff, Francis A & Schwartz, Eduardo S, 2001. "Valuing American Options by Simulation: A Simple Least-Squares Approach," University of California at Los Angeles, Anderson Graduate School of Management qt43n1k4jb, Anderson Graduate School of Management, UCLA.
    39. Rafael Company & Vera Egorova & Lucas J'odar & Fazlollah Soleymani, 2017. "Computing stable numerical solutions for multidimensional American option pricing problems: a semi-discretization approach," Papers 1701.08545, arXiv.org.
    40. Ludovic Gouden`ege & Andrea Molent & Antonino Zanette, 2019. "Machine Learning for Pricing American Options in High-Dimensional Markovian and non-Markovian models," Papers 1905.09474, arXiv.org, revised Jun 2019.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ivan Guo & Nicolas Langren'e & Jiahao Wu, 2023. "Simultaneous upper and lower bounds of American-style option prices with hedging via neural networks," Papers 2302.12439, arXiv.org, revised Nov 2024.
    2. Wei, Wei & Zhu, Dan, 2022. "Generic improvements to least squares monte carlo methods with applications to optimal stopping problems," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1132-1144.
    3. Sebastian Becker & Patrick Cheridito & Arnulf Jentzen, 2020. "Pricing and Hedging American-Style Options with Deep Learning," JRFM, MDPI, vol. 13(7), pages 1-12, July.
    4. Louis Bhim & Reiichiro Kawai, 2018. "Smooth Upper Bounds For The Price Function Of American Style Options," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 21(01), pages 1-38, February.
    5. Jin, Xing & Yang, Cheng-Yu, 2016. "Efficient estimation of lower and upper bounds for pricing higher-dimensional American arithmetic average options by approximating their payoff functions," International Review of Financial Analysis, Elsevier, vol. 44(C), pages 65-77.
    6. Denis Belomestny & John Schoenmakers & Fabian Dickmann, 2013. "Multilevel dual approach for pricing American style derivatives," Finance and Stochastics, Springer, vol. 17(4), pages 717-742, October.
    7. Beveridge, Christopher & Joshi, Mark & Tang, Robert, 2013. "Practical policy iteration: Generic methods for obtaining rapid and tight bounds for Bermudan exotic derivatives using Monte Carlo simulation," Journal of Economic Dynamics and Control, Elsevier, vol. 37(7), pages 1342-1361.
    8. Bradley Sturt, 2021. "A nonparametric algorithm for optimal stopping based on robust optimization," Papers 2103.03300, arXiv.org, revised Mar 2023.
    9. Mark S. Joshi, 2016. "Analysing the bias in the primal-dual upper bound method for early exercisable derivatives: bounds, estimation and removal," Quantitative Finance, Taylor & Francis Journals, vol. 16(4), pages 519-533, April.
    10. Chen Liu & Henry Schellhorn & Qidi Peng, 2019. "American Option Pricing With Regression: Convergence Analysis," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 22(08), pages 1-31, December.
    11. Jain, Shashi & Oosterlee, Cornelis W., 2015. "The Stochastic Grid Bundling Method: Efficient pricing of Bermudan options and their Greeks," Applied Mathematics and Computation, Elsevier, vol. 269(C), pages 412-431.
    12. John Schoenmakers, 2012. "A pure martingale dual for multiple stopping," Finance and Stochastics, Springer, vol. 16(2), pages 319-334, April.
    13. Mark Broadie & Jerome B. Detemple, 2004. "ANNIVERSARY ARTICLE: Option Pricing: Valuation Models and Applications," Management Science, INFORMS, vol. 50(9), pages 1145-1177, September.
    14. John Schoenmakers & Junbo Huang & Jianing Zhang, 2011. "Optimal dual martingales, their analysis and application to new algorithms for Bermudan products," Papers 1111.6038, arXiv.org, revised Feb 2012.
    15. Vikranth Lokeshwar & Vikram Bhardawaj & Shashi Jain, 2019. "Neural network for pricing and universal static hedging of contingent claims," Papers 1911.11362, arXiv.org.
    16. Denis Belomestny & Grigori Milstein & Vladimir Spokoiny, 2009. "Regression methods in pricing American and Bermudan options using consumption processes," Quantitative Finance, Taylor & Francis Journals, vol. 9(3), pages 315-327.
    17. Helin Zhu & Fan Ye & Enlu Zhou, 2013. "Fast Estimation of True Bounds on Bermudan Option Prices under Jump-diffusion Processes," Papers 1305.4321, arXiv.org.
    18. Cosma, Antonio & Galluccio, Stefano & Pederzoli, Paola & Scaillet, Olivier, 2020. "Early Exercise Decision in American Options with Dividends, Stochastic Volatility, and Jumps," Journal of Financial and Quantitative Analysis, Cambridge University Press, vol. 55(1), pages 331-356, February.
    19. Vijay V. Desai & Vivek F. Farias & Ciamac C. Moallemi, 2012. "Pathwise Optimization for Optimal Stopping Problems," Management Science, INFORMS, vol. 58(12), pages 2292-2308, December.
    20. Dragos Florin Ciocan & Velibor V. Mišić, 2022. "Interpretable Optimal Stopping," Management Science, INFORMS, vol. 68(3), pages 1616-1638, March.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:1908.01602. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.