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.
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 language | English |
---|---|
Title of host publication | Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence |
Pages | 3613-3619 |
Number of pages | 7 |
Publication status | Published - 2015 |
Event | The Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15) - Texas, Austin, United States Duration: 25 Jan 2015 → 29 Jan 2015 |
Conference
Conference | The Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15) |
---|---|
Country/Territory | United States |
City | Austin |
Period | 25/01/2015 → 29/01/2015 |