Nested Monte-Carlo Tree Search for Online Planning in Large MDPs

Hendrik Baier; Mark H.M. Winands

doi:10.3233/978-1-61499-098-7-109

Nested Monte-Carlo Tree Search for Online Planning in Large MDPs

Hendrik Baier
, Mark H.M. Winands

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

15 Citations (Scopus)

Abstract

Monte-Carlo Tree Search (MCTS) is state of the art for online planning in large MDPs. It is a best-first, sample-based search algorithm in which every state in the search tree is evaluated by the average outcome of Monte-Carlo rollouts from that state. These rollouts are typically random or directed by a simple, domain-dependent heuristic. We propose Nested Monte-Carlo Tree Search (NMCTS), in which MCTS itself is recursively used to provide a rollout policy for higher-level searches. In three large-scale MDPs, SameGame, Clickomania and Bubble Breaker, we show that NMCTS is significantly more effective than regular MCTS at equal time controls, both using random and heuristic rollouts at the base level. Experiments also suggest superior performance to Nested Monte-Carlo Search (NMCS) in some domains.

Original language	English
Title of host publication	ECAI
Publisher	IOS Press
Pages	109-114
Number of pages	6
ISBN (Electronic)	978-1-61499-098-7
ISBN (Print)	978-1-61499-097-0
DOIs	https://doi.org/10.3233/978-1-61499-098-7-109
Publication status	Published - 2012
Externally published	Yes
Event	20th European Conference on Artificial Intelligence, ECAI 2012 - Montpellier, France Duration: 27 Aug 2012 → 31 Aug 2012

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Publisher	IOS Press
Volume	242
ISSN (Print)	0922-6389
ISSN (Electronic)	1879-8314

Conference

Conference	20th European Conference on Artificial Intelligence, ECAI 2012
Abbreviated title	ECAI 2012
Country/Territory	France
City	Montpellier
Period	27/08/12 → 31/08/12

Access to Document

10.3233/978-1-61499-098-7-109

Cite this

@inproceedings{018a8855f1664744b445723c291d9c0e,

title = "Nested Monte-Carlo Tree Search for Online Planning in Large MDPs",

abstract = "Monte-Carlo Tree Search (MCTS) is state of the art for online planning in large MDPs. It is a best-first, sample-based search algorithm in which every state in the search tree is evaluated by the average outcome of Monte-Carlo rollouts from that state. These rollouts are typically random or directed by a simple, domain-dependent heuristic. We propose Nested Monte-Carlo Tree Search (NMCTS), in which MCTS itself is recursively used to provide a rollout policy for higher-level searches. In three large-scale MDPs, SameGame, Clickomania and Bubble Breaker, we show that NMCTS is significantly more effective than regular MCTS at equal time controls, both using random and heuristic rollouts at the base level. Experiments also suggest superior performance to Nested Monte-Carlo Search (NMCS) in some domains.",

author = "Hendrik Baier and Winands, \{Mark H.M.\}",

year = "2012",

doi = "10.3233/978-1-61499-098-7-109",

language = "English",

isbn = "978-1-61499-097-0",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "109--114",

booktitle = "ECAI",

address = "Netherlands",

note = "20th European Conference on Artificial Intelligence, ECAI 2012, ECAI 2012 ; Conference date: 27-08-2012 Through 31-08-2012",

}

TY - GEN

T1 - Nested Monte-Carlo Tree Search for Online Planning in Large MDPs

AU - Baier, Hendrik

AU - Winands, Mark H.M.

PY - 2012

Y1 - 2012

N2 - Monte-Carlo Tree Search (MCTS) is state of the art for online planning in large MDPs. It is a best-first, sample-based search algorithm in which every state in the search tree is evaluated by the average outcome of Monte-Carlo rollouts from that state. These rollouts are typically random or directed by a simple, domain-dependent heuristic. We propose Nested Monte-Carlo Tree Search (NMCTS), in which MCTS itself is recursively used to provide a rollout policy for higher-level searches. In three large-scale MDPs, SameGame, Clickomania and Bubble Breaker, we show that NMCTS is significantly more effective than regular MCTS at equal time controls, both using random and heuristic rollouts at the base level. Experiments also suggest superior performance to Nested Monte-Carlo Search (NMCS) in some domains.

AB - Monte-Carlo Tree Search (MCTS) is state of the art for online planning in large MDPs. It is a best-first, sample-based search algorithm in which every state in the search tree is evaluated by the average outcome of Monte-Carlo rollouts from that state. These rollouts are typically random or directed by a simple, domain-dependent heuristic. We propose Nested Monte-Carlo Tree Search (NMCTS), in which MCTS itself is recursively used to provide a rollout policy for higher-level searches. In three large-scale MDPs, SameGame, Clickomania and Bubble Breaker, we show that NMCTS is significantly more effective than regular MCTS at equal time controls, both using random and heuristic rollouts at the base level. Experiments also suggest superior performance to Nested Monte-Carlo Search (NMCS) in some domains.

U2 - 10.3233/978-1-61499-098-7-109

DO - 10.3233/978-1-61499-098-7-109

M3 - Conference contribution

SN - 978-1-61499-097-0

T3 - Frontiers in Artificial Intelligence and Applications

SP - 109

EP - 114

BT - ECAI

PB - IOS Press

T2 - 20th European Conference on Artificial Intelligence, ECAI 2012

Y2 - 27 August 2012 through 31 August 2012

ER -

Nested Monte-Carlo Tree Search for Online Planning in Large MDPs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this