Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-33486-3_11
Title: Bootstrapping Monte Carlo tree search with an imperfect heuristic
Authors: Nguyen, T.-H.D.
Lee, W.-S. 
Leong, T.-Y. 
Issue Date: 2012
Source: Nguyen, T.-H.D.,Lee, W.-S.,Leong, T.-Y. (2012). Bootstrapping Monte Carlo tree search with an imperfect heuristic. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7524 LNAI (PART 2) : 164-179. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-33486-3_11
Abstract: We consider the problem of using a heuristic policy to improve the value approximation by the Upper Confidence Bound applied in Trees (UCT) algorithm in non-adversarial settings such as planning with large-state space Markov Decision Processes. Current improvements to UCT focus on either changing the action selection formula at the internal nodes or the rollout policy at the leaf nodes of the search tree. In this work, we propose to add an auxiliary arm to each of the internal nodes, and always use the heuristic policy to roll out simulations at the auxiliary arms. The method aims to get fast convergence to optimal values at states where the heuristic policy is optimal, while retaining similar approximation as the original UCT at other states. We show that bootstrapping with the proposed method in the new algorithm, UCT-Aux, performs better compared to the original UCT algorithm and its variants in two benchmark experiment settings. We also examine conditions under which UCT-Aux works well. © 2012 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/41606
ISBN: 9783642334856
ISSN: 03029743
DOI: 10.1007/978-3-642-33486-3_11
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Dec 13, 2017

Page view(s)

57
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.