Bootstrapping Monte Carlo tree search with an imperfect heuristic
Publication Type
Conference Proceeding Article
Publication Date
10-2012
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.
Discipline
Databases and Information Systems
Publication
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II
Volume
II
First Page
164
Last Page
179
ISBN
9783642334856
Identifier
10.1007/978-3-642-33486-3_11
Publisher
Springer-Verlag
City or Country
Bristol, UK
Citation
Nguyen T., Lee W., and Tze-Yun LEONG.
Bootstrapping Monte Carlo tree search with an imperfect heuristic. (2012). European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II. II, 164-179.
Available at: https://ink.library.smu.edu.sg/sis_research/2999