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

Flexible forward improvement iteration for infinite time horizon Markovian optimal stopping problems

Author

Listed:
  • Soren Christensen
  • Albrecht Irle
  • Julian Peter Lemburg

Abstract

In this paper, we propose an extension of the forward improvement iteration algorithm, originally introduced in Irle (2006) and recently reconsidered in Miclo and Villeneuve (2021). The main new ingredient is a flexible window parameter describing the look-ahead distance in the improvement step. We consider the framework of a Markovian optimal stopping problem in discrete time with random discounting and infinite time horizon. We prove convergence and show that the additional flexibility may significantly reduce the runtime.

Suggested Citation

  • Soren Christensen & Albrecht Irle & Julian Peter Lemburg, 2021. "Flexible forward improvement iteration for infinite time horizon Markovian optimal stopping problems," Papers 2111.13443, arXiv.org.
    • Handle: RePEc:arx:papers:2111.13443
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Isaac Sonin, 1999. "The Elimination algorithm for the problem of optimal stopping," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 49(1), pages 111-123, March.
    2. Christensen, Sören & Irle, Albrecht, 2020. "The monotone case approach for the solution of certain multidimensional optimal stopping problems," Stochastic Processes and their Applications, Elsevier, vol. 130(4), pages 1972-1993.
    3. Christensen, Sören & Sohr, Tobias, 2020. "A solution technique for Lévy driven long term average impulse control problems," Stochastic Processes and their Applications, Elsevier, vol. 130(12), pages 7303-7337.
    4. Anastasia Kolodko & John Schoenmakers, 2006. "Iterative construction of the optimal Bermudan stopping time," Finance and Stochastics, Springer, vol. 10(1), pages 27-49, January.
    5. 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.
    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. Miclo, Laurent & Villeneuve, Stéphane, 2019. "On the forward algorithm for stopping problems on continuous-time Markov chains," TSE Working Papers 19-1009, Toulouse School of Economics (TSE).
    2. 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.
    3. repec:hum:wpaper:sfb649dp2006-051 is not listed on IDEAS
    4. 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.
    5. 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.
    6. Soren Christensen & Jan Kallsen & Matthias Lenga, 2020. "Are American options European after all?," Papers 2002.05571, arXiv.org.
    7. Sonin, Isaac M., 2008. "A generalized Gittins index for a Markov chain and its recursive calculation," Statistics & Probability Letters, Elsevier, vol. 78(12), pages 1526-1533, September.
    8. David A. Goldberg & Yilun Chen, 2018. "Polynomial time algorithm for optimal stopping with fixed accuracy," Papers 1807.02227, arXiv.org, revised May 2024.
    9. 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.
    10. Dan Andrei Iancu & Nikolaos Trichakis & Do Young Yoon, 2021. "Monitoring with Limited Information," Management Science, INFORMS, vol. 67(7), pages 4233-4251, July.
    11. Ivan Guo & Nicolas Langren'e & Jiahao Wu, 2023. "Simultaneous upper and lower bounds of American option prices with hedging via neural networks," Papers 2302.12439, arXiv.org, revised Apr 2024.
    12. D. Ramsey, 2007. "A model of a 2-player stopping game with priority and asynchronous observation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 66(1), pages 149-164, August.
    13. Amod J. Basnet & Isaac M. Sonin, 2022. "Parallel computing for Markov chains with islands and ports," Annals of Operations Research, Springer, vol. 317(2), pages 335-352, October.
    14. Armerin, Fredrik, 2024. "A Comment on “The effectiveness of carbon pricing: The role of diversification in a firm’s investment decision”," Energy Economics, Elsevier, vol. 132(C).
    15. 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.
    16. Denis Belomestny & John Schoenmakers, 2021. "From optimal martingales to randomized dual optimal stopping," Papers 2102.01533, arXiv.org.
    17. José Niño-Mora, 2007. "A (2/3) n 3 Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 596-606, November.
    18. 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.
    19. 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.
    20. Joerg Kampen & Anastasia Kolodko & John Schoenmakers, 2008. "Monte Carlo Greeks for financial products via approximative transition densities," Papers 0807.1213, arXiv.org.
    21. Christian Bender & Christian Gaertner & Nikolaus Schweizer, 2016. "Pathwise Iteration for Backward SDEs," Papers 1605.07500, arXiv.org, revised Jun 2016.

    More about this item

    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:2111.13443. 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.