Hierarchical Monte-Carlo Planning

Authors

  • Ngo Anh Vien University of Stuttgart
  • Marc Toussaint University of Stuttgart

DOI:

https://doi.org/10.1609/aaai.v29i1.9687

Keywords:

Monte-Carlo Tree Search, Hierarchical Monte-Carlo Planning, Bayesian hierarchical RL, POSMDP

Abstract

Monte-Carlo Tree Search, especially UCT and its POMDP version POMCP, have demonstrated excellent performanceon 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 atask hierarchy into the MCTS framework, specifically lead-ing 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.

Downloads

Published

2015-03-04

How to Cite

Vien, N. A., & Toussaint, M. (2015). Hierarchical Monte-Carlo Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9687

Issue

Section

AAAI Technical Track: Reasoning under Uncertainty