IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v36y2019i06ns0217595919400098.html
   My bibliography  Save this article

Simulation-Based Algorithms for Markov Decision Processes: Monte Carlo Tree Search from AlphaGo to AlphaZero

Author

Listed:
  • Michael C. Fu

    (Robert H. Smith School of Business & Institute for Systems Research, University of Maryland, College Park, Maryland 20742, USA)

Abstract

AlphaGo and its successors AlphaGo Zero and AlphaZero made international headlines with their incredible successes in game playing, which have been touted as further evidence of the immense potential of artificial intelligence, and in particular, machine learning. AlphaGo defeated the reigning human world champion Go player Lee Sedol 4 games to 1, in March 2016 in Seoul, Korea, an achievement that surpassed previous computer game-playing program milestones by IBM’s Deep Blue in chess and by IBM’s Watson in the U.S. TV game show Jeopardy. AlphaGo then followed this up by defeating the world’s number one Go player Ke Jie 3-0 at the Future of Go Summit in Wuzhen, China in May 2017. Then, in December 2017, AlphaZero stunned the chess world by dominating the top computer chess program Stockfish (which has a far higher rating than any human) in a 100-game match by winning 28 games and losing none (72 draws) after training from scratch for just four hours! The deep neural networks of AlphaGo, AlphaZero, and all their incarnations are trained using a technique called Monte Carlo tree search (MCTS), whose roots can be traced back to an adaptive multistage sampling (AMS) simulation-based algorithm for Markov decision processes (MDPs) published in Operations Research back in 2005 [Chang, HS, MC Fu, J Hu and SI Marcus (2005). An adaptive sampling algorithm for solving Markov decision processes. Operations Research, 53, 126–139.] (and introduced even earlier in 2002). After reviewing the history and background of AlphaGo through AlphaZero, the origins of MCTS are traced back to simulation-based algorithms for MDPs, and its role in training the neural networks that essentially carry out the value/policy function approximation used in approximate dynamic programming, reinforcement learning, and neuro-dynamic programming is discussed, including some recently proposed enhancements building on statistical ranking & selection research in the operations research simulation community.

Suggested Citation

  • Michael C. Fu, 2019. "Simulation-Based Algorithms for Markov Decision Processes: Monte Carlo Tree Search from AlphaGo to AlphaZero," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(06), pages 1-25, December.
    • Handle: RePEc:wsi:apjorx:v:36:y:2019:i:06:n:s0217595919400098
    DOI: 10.1142/S0217595919400098
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595919400098
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0217595919400098?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Mark Broadie & Paul Glasserman, 1996. "Estimating Security Price Derivatives Using Simulation," Management Science, INFORMS, vol. 42(2), pages 269-285, February.
    2. Hyeong Soo Chang & Michael C. Fu & Jiaqiao Hu & Steven I. Marcus, 2005. "An Adaptive Sampling Algorithm for Solving Markov Decision Processes," Operations Research, INFORMS, vol. 53(1), pages 126-139, February.
    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. Guangwu Liu & Liu Jeff Hong, 2009. "Kernel estimation of quantile sensitivities," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(6), pages 511-525, September.
    2. Galai, Dan & Raviv, Alon & Wiener, Zvi, 2007. "Liquidation triggers and the valuation of equity and debt," Journal of Banking & Finance, Elsevier, vol. 31(12), pages 3604-3620, December.
    3. Xiaoqun Wang, 2016. "Handling Discontinuities in Financial Engineering: Good Path Simulation and Smoothing," Operations Research, INFORMS, vol. 64(2), pages 297-314, April.
    4. Lingyan Cao & Zheng-Feng Guo, 2012. "A Comparison Of Delta Hedging Under Two Price Distribution Assumptions By Likelihood Ratio," The International Journal of Business and Finance Research, The Institute for Business and Finance Research, vol. 6(1), pages 25-34.
    5. Silvana M. Pesenti & Pietro Millossovich & Andreas Tsanakas, 2023. "Differential Sensitivity in Discontinuous Models," Papers 2310.06151, arXiv.org.
    6. Lingyan Cao & Zheng-Feng Guo, 2012. "A Comparison Of Gradient Estimation Techniques For European Call Options," Accounting & Taxation, The Institute for Business and Finance Research, vol. 4(1), pages 75-81.
    7. Lim, Terence & Lo, Andrew W. & Merton, Robert C. & Scholes, Myron S., 2006. "The Derivatives Sourcebook," Foundations and Trends(R) in Finance, now publishers, vol. 1(5–6), pages 365-572, April.
    8. N. Hilber & N. Reich & C. Schwab & C. Winter, 2009. "Numerical methods for Lévy processes," Finance and Stochastics, Springer, vol. 13(4), pages 471-500, September.
    9. Arturo Kohatsu-Higa & Miquel Montero, 2001. "An application of Malliavin Calculus to Finance," Papers cond-mat/0111563, arXiv.org.
    10. F Bourgey & S de Marco & Emmanuel Gobet & Alexandre Zhou, 2020. "Multilevel Monte-Carlo methods and lower-upper bounds in Initial Margin computations," Post-Print hal-02430430, HAL.
    11. F Bourgey & S de Marco & Emmanuel Gobet & Alexandre Zhou, 2020. "Multilevel Monte-Carlo methods and lower-upper bounds in Initial Margin computations," Working Papers hal-02430430, HAL.
    12. J. Lars Kirkby & Duy Nguyen, 2020. "Efficient Asian option pricing under regime switching jump diffusions and stochastic volatility models," Annals of Finance, Springer, vol. 16(3), pages 307-351, September.
    13. Dan Pirjol & Lingjiong Zhu, 2023. "Sensitivities of Asian options in the Black-Scholes model," Papers 2301.06460, arXiv.org.
    14. Wensheng Yang & Jingtang Ma & Zhenyu Cui, 2021. "Analysis of Markov chain approximation for Asian options and occupation-time derivatives: Greeks and convergence rates," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(2), pages 359-412, April.
    15. Louis-Pierre Arguin & Nien-Lin Liu & Tai-Ho Wang, 2018. "Most-Likely-Path In Asian Option Pricing Under Local Volatility Models," International Journal of Theoretical and Applied Finance (IJTAF), World Scientific Publishing Co. Pte. Ltd., vol. 21(05), pages 1-32, August.
    16. Adrien Nguyen Huu & Nadia Oudjane, 2014. "Hedging Expected Losses on Derivatives in Electricity Futures Markets," Papers 1401.8271, arXiv.org.
    17. Guillaume Bernis & Emmanuel Gobet & Arturo Kohatsu‐Higa, 2003. "Monte Carlo Evaluation of Greeks for Multidimensional Barrier and Lookback Options," Mathematical Finance, Wiley Blackwell, vol. 13(1), pages 99-113, January.
    18. John Board & Charles Sutcliffe & William T. Ziemba, 2003. "Applying Operations Research Techniques to Financial Markets," Interfaces, INFORMS, vol. 33(2), pages 12-24, April.
    19. Vasile BRÄ‚TIAN, 2018. "Evaluation of Options using the Monte Carlo Method and the Entropy of Information," Expert Journal of Economics, Sprint Investify, vol. 6(2), pages 35-43.
    20. Michael C. Fu, 2008. "What you should know about simulation and derivatives," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(8), pages 723-736, December.

    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:wsi:apjorx:v:36:y:2019:i:06:n:s0217595919400098. 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: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    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.