In this thesis, we study how reinforcement learning algorithms can tackle classical board games without recourse to human knowledge. Specifically, we develop a framework and algorithms which learn to play the board game Hex starting from random play. We first describe Expert Iteration (ExIt), a novel reinforcement learning framework which extends Modified Policy Iteration. ExIt explicitly decomposes the reinforcement learning problem into two parts: planning and generalisation. A planning algorithm explores possible move sequences starting from a particular position to find good strategies from that position, while a parametric function approximator is trained to predict those plans, generalising to states not yet seen. Subsequently, planning is improved by using the approximated policy to guide search, increasing the strength of new plans. This decomposition allows ExIt to combine the benefits of both planning methods and function approximation methods. We demonstrate the effectiveness of the ExIt paradigm by implementing ExIt with two different planning algorithms. First, we develop a version based on Monte Carlo Tree Search (MCTS), a search algorithm which has been successful both in specific games, such as Go, Hex and Havannah, and in general game playing competitions. We then develop a new planning algorithm, Policy Gradient Search (PGS), which uses a model-free reinforcement learning algorithm for online planning. Unlike MCTS, PGS does not require an explicit search tree. Instead PGS uses function approximation within a single search, allowing it to be applied to problems with larger branching factors. Both MCTS-ExIt and PGS-ExIt defeated MoHex 2.0 - the most recent Hex Olympiad winner to be open sourced - in 9 × 9 Hex. More importantly, whereas MoHex makes use of many Hex-specific improvements and knowledge, all our programs were trained tabula rasa using general reinforcement learning methods. This bodes well for ExIt’s applicability to both other games and real world decision making problems.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Expert iteration


    Beteiligte:

    Erscheinungsdatum :

    2021-03-28


    Anmerkungen:

    Doctoral thesis, UCL (University College London).


    Medientyp :

    Hochschulschrift


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    006 / 629



    Manipulating the Distributions of Experience used for Self-Play Learning in Expert Iteration

    Soemers, Dennis / Piette, Eric / Stephenson, Matthew et al. | BASE | 2020

    Freier Zugriff

    Iteration

    Dixon, John C. | Wiley | 2009


    SPACE STATION: THE NEXT ITERATION

    Foley, Theresa M. | Online Contents | 1995


    Comparison of Value Iteration, Policy Iteration and Q-Learning for solving Decision-Making problems

    Hamadouche, Mohand / Dezan, Catherine / Espes, David et al. | IEEE | 2021


    Space Station: The Next Iteration

    Foley, T. M. | British Library Online Contents | 1995