Convex Hull Monte-Carlo tree search

Conference item

This work investigates Monte-Carlo planning for agents in stochastic environments, with multiple objectives. We propose the Convex Hull Monte-Carlo Tree-Search (CHMCTS) framework, which builds upon Trial Based Heuristic Tree Search and Convex Hull Value Iteration (CHVI), as a solution to multi-objective planning in large environments. Moreover, we consider how to pose the problem of approximating multi-objective planning solutions as a contextual multi-armed bandits problem, giving a principled motivation for how to select actions from the view of contextual regret. This leads us to the use of Contextual Zooming for action selection, yielding Zooming CHMCTS. We evaluate our algorithm using the Generalised Deep Sea Treasure environment, demonstrating that Zooming CHMCTS can achieve a sublinear contextual regret and scales better than CHVI on a given computational budget.

Authors: Painter, M; Lacerda, B; Hawes, N

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: AAAI Press
• Host title: Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling
• Volume: 30
• Pages: 217-225
• Publication date: 2020-05-29
• Acceptance date: 2020-01-20
• Event title: 30th International Conference on Automated Planning and Scheduling
• Event series: ICAPS
• Event location: Nancy, France
• Event website: https://icaps20.icaps-conference.org/calls/call-for-papers/
• Event start date: 2020-10-26
• Event end date: 2020-10-30
• EISSN: 2334-0843
• ISSN: 2334-0835
• ISBN: 978-1-57735-824-4
• Language: English