Generalized mean estimation in monte-carlo tree search

Tuan Dam, Pascal Klink, Carlo D'Eramo, Jan Peters, Joni Pajarinen

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

We consider Monte-Carlo Tree Search (MCTS) applied to Markov Decision Processes (MDPs) and Partially Observable MDPs (POMDPs), and the well-known Upper Confidence bound for Trees (UCT) algorithm. In UCT, a tree with nodes (states) and edges (actions) is incrementally built by the expansion of nodes, and the values of nodes are updated through a backup strategy based on the average value of child nodes. However, it has been shown that with enough samples the maximum operator yields more accurate node value estimates than averaging. Instead of settling for one of these value estimates, we go a step further proposing a novel backup strategy which uses the power mean operator, which computes a value between the average and maximum value. We call our new approach Power-UCT, and argue how the use of the power mean operator helps to speed up the learning in MCTS. We theoretically analyze our method providing guarantees of convergence to the optimum. Finally, we empirically demonstrate the effectiveness of our method in well-known MDP and POMDP benchmarks, showing significant improvement in performance and convergence speed w.r.t. state of the art algorithms.

Original languageEnglish
Title of host publicationProceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020
EditorsChristian Bessiere
PublisherInternational Joint Conferences on Artificial Intelligence
Pages2397-2404
Number of pages8
ISBN (Electronic)9780999241165
DOIs
Publication statusPublished - 2020
Publication typeA4 Article in conference proceedings
EventInternational Joint Conference on Artificial Intelligence - Yokohama, Japan
Duration: 1 Jan 2021 → …

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2021-January
ISSN (Print)1045-0823

Conference

ConferenceInternational Joint Conference on Artificial Intelligence
Country/TerritoryJapan
CityYokohama
Period1/01/21 → …

Funding

This project has received funding from SKILLS4ROBOTS, project reference #640554, and, by the German Research Foundation project PA 3179/1-1 (ROBOLEAP), and from the European Union’s Horizon 2020 research and innovation programme under grant agreement No. #713010 (GOAL-Robots).

Publication forum classification

  • Publication forum level 2

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Generalized mean estimation in monte-carlo tree search'. Together they form a unique fingerprint.

Cite this