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

Dynamic programming for optimal stopping via pseudo-regression

Author

Listed:
  • Christian Bayer
  • Martin Redmann
  • John Schoenmakers

Abstract

We introduce new variants of classical regression-based algorithms for optimal stopping problems based on computation of regression coefficients by Monte Carlo approximation of the corresponding $L^2$ inner products instead of the least-squares error functional. Coupled with new proposals for simulation of the underlying samples, we call the approach "pseudo regression". A detailed convergence analysis is provided and it is shown that the approach asymptotically leads to less computational cost for a pre-specified error tolerance, hence to lower complexity. The method is justified by numerical examples.

Suggested Citation

  • Christian Bayer & Martin Redmann & John Schoenmakers, 2018. "Dynamic programming for optimal stopping via pseudo-regression," Papers 1808.04725, arXiv.org, revised Apr 2019.
    • Handle: RePEc:arx:papers:1808.04725
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1808.04725
    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. 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.
    3. Denis Belomestny & John Schoenmakers, 2018. "Advanced Simulation-Based Methods for Optimal Stopping and Control," Palgrave Macmillan Books, Palgrave Macmillan, number 978-1-137-03351-2, October.
    4. Daniel Zanger, 2013. "Quantitative error estimates for a least-squares Monte Carlo algorithm for American option pricing," Finance and Stochastics, Springer, vol. 17(3), pages 503-534, July.
    5. 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.
    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. D. Belomestny & M. Kaledin & J. Schoenmakers, 2019. "Semi-tractability of optimal stopping problems via a weighted stochastic mesh algorithm," Papers 1906.09431, arXiv.org.
    2. Christian Bayer & Ra'ul Tempone & Soren Wolfers, 2018. "Pricing American Options by Exercise Rate Optimization," Papers 1809.07300, arXiv.org, revised Aug 2019.
    3. Mike Ludkovski, 2020. "mlOSP: Towards a Unified Implementation of Regression Monte Carlo Algorithms," Papers 2012.00729, arXiv.org, revised Oct 2022.
    4. Christian Bayer & Denis Belomestny & Paul Hager & Paolo Pigato & John Schoenmakers, 2020. "Randomized optimal stopping algorithms and their convergence analysis," Papers 2002.00816, arXiv.org.
    5. Fabian Dickmann & Nikolaus Schweizer, 2014. "Faster Comparison of Stopping Times by Nested Conditional Monte Carlo," Papers 1402.0243, arXiv.org.
    6. Zineb El Filali Ech-Chafiq & Pierre Henry-Labordere & Jérôme Lelong, 2021. "Pricing Bermudan options using regression trees/random forests," Working Papers hal-03436046, HAL.
    7. 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.
    8. A. Max Reppen & H. Mete Soner & Valentin Tissot-Daguette, 2022. "Deep Stochastic Optimization in Finance," Papers 2205.04604, arXiv.org.
    9. Doan, Viet_Dung & Gaikwad, Abhijeet & Bossy, Mireille & Baude, Françoise & Stokes-Rees, Ian, 2010. "Parallel pricing algorithms for multi-dimensional Bermudan/American options using Monte Carlo methods," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 81(3), pages 568-577.
    10. Bünyamin Erkan & Jean-Luc Prigent, 2020. "About Long-Term Cross-Currency Bermuda Swaption Pricing," Computational Economics, Springer;Society for Computational Economics, vol. 56(1), pages 239-262, June.
    11. 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.
    12. David A. Goldberg & Yilun Chen, 2018. "Polynomial time algorithm for optimal stopping with fixed accuracy," Papers 1807.02227, arXiv.org, revised May 2024.
    13. Li, Chenxu & Ye, Yongxin, 2019. "Pricing and Exercising American Options: an Asymptotic Expansion Approach," Journal of Economic Dynamics and Control, Elsevier, vol. 107(C), pages 1-1.
    14. Cosma, Antonio & Galluccio, Stefano & Scaillet, Olivier, 2012. "Valuing American options using fast recursive projections," Working Papers unige:41856, University of Geneva, Geneva School of Economics and Management.
    15. Yi Yang & Jianan Wang & Youhua Chen & Zhiyuan Chen & Yanchu Liu, 2020. "Optimal procurement strategies for contractual assembly systems with fluctuating procurement price," Annals of Operations Research, Springer, vol. 291(1), pages 1027-1059, August.
    16. Mark Broadie & Weiwei Shen, 2016. "High-Dimensional Portfolio Optimization With Transaction Costs," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 19(04), pages 1-49, June.
    17. 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.
    18. Belomestny, Denis & Milstein, Grigori N., 2006. "Adaptive simulation algorithms for pricing American and Bermudan options by local analysis of financial market," SFB 649 Discussion Papers 2006-038, Humboldt University Berlin, Collaborative Research Center 649: Economic Risk.
    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:1808.04725. 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.