Hierarchical Monte-Carlo Planning

Vien Ngo, Marc Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)

Abstract

Monte-Carlo Tree Search, especially UCT and its POMDP version POMCP, have demonstrated excellent performance on many problems. However, to efficiently scale to large domains one should also exploit hierarchical structure if present. In such hierarchical domains, finding rewarded states typically
requires to search deeply; covering enough such informative states very far from the root becomes computationally expensive in flat non-hierarchical search approaches. We propose novel, scalable MCTS methods which integrate a task hierarchy into the MCTS framework, specifically leading
to hierarchical versions of both, UCT and POMCP. The new method does not need to estimate probabilistic models of each subtask, it instead computes subtask policies purely sample-based. We evaluate the hierarchical MCTS methods on various settings such as a hierarchical MDP, a Bayesian
model-based hierarchical RL problem, and a large hierarchical POMDP.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
Pages3613-3619
Number of pages7
Publication statusPublished - 2015
EventThe Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15) - Texas, Austin, United States
Duration: 25 Jan 201529 Jan 2015

Conference

ConferenceThe Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15)
CountryUnited States
CityAustin
Period25/01/201529/01/2015

Fingerprint Dive into the research topics of 'Hierarchical Monte-Carlo Planning'. Together they form a unique fingerprint.

  • Cite this

    Ngo, V., & Toussaint, M. (2015). Hierarchical Monte-Carlo Planning. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (pp. 3613-3619) https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9608/9802