Publication
Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the Unknown
Cedric Derstroff; Jannis Brugger; Jannis Blüml; Mira Mezini; Stefan Kramer; Kristian Kersting
In: Computing Research Repository eprint Journal (CoRR), Vol. abs/2402.08511, Pages 1-10, arXiv, 2024.
Abstract
Monte-Carlo tree search (MCTS) is an effective
anytime algorithm with a vast amount of applica-
tions. It strategically allocates computational re-
sources to focus on promising segments of the
search tree, making it a very attractive search al-
gorithm in large search spaces. However, it of-
ten expends its limited resources on reevaluating
previously explored regions when they remain the
most promising path. Our proposed methodology,
denoted as AmEx-MCTS, solves this problem by
introducing a novel MCTS formulation. Central
to AmEx-MCTS is the decoupling of value up-
dates, visit count updates, and the selected path
during the tree search, thereby enabling the exclu-
sion of already explored subtrees or leaves. This
segregation preserves the utility of visit counts for
both exploration-exploitation balancing and qual-
ity metrics within MCTS. The resultant augmen-
tation facilitates in a considerably broader search
using identical computational resources, preserv-
ing the essential characteristics of MCTS. The ex-
panded coverage not only yields more precise esti-
mations but also proves instrumental in larger and
more complex problems. Our empirical evaluation
demonstrates the superior performance of AmEx-
MCTS, surpassing classical MCTS and related ap-
proaches by a substantial margin.