Extreme Value Monte Carlo Tree Search for Classical Planning

View PDF HTML (experimental)

Abstract:Despite being successful in board games and reinforcement learning (RL), Monte Carlo Tree Search (MCTS) combined with Multi Armed Bandits (MABs) has seen limited success in domain-independent classical planning until recently. Previous work (Wissow and Asai 2024) showed that UCB1, designed for bounded rewards, does not perform well as applied to cost-to-go estimates in classical planning, which are unbounded in $\R$, and showed improved performance using a Gaussian reward MAB instead. This paper further sharpens our understanding of ideal bandits for planning tasks. Existing work has two issues: first, Gaussian MABs under-specify the support of cost-to-go estimates as $(-\infty,\infty)$, which we can narrow down. Second, Full Bellman backup (Schulte and Keller 2014), which backpropagates sample max/min, lacks theoretical justification. We use \emph{Peaks-Over-Threashold Extreme Value Theory} to resolve both issues at once, and propose a new bandit algorithm (UCB1-Uniform). We formally prove its regret bound and empirically demonstrate its performance in classical planning.

Comments: Accepted in AAAI-26. arXiv admin note: substantial text overlap with arXiv:2305.09840 (background section)

Subjects:

Artificial Intelligence (cs.AI)

Cite as: arXiv:2405.18248 [cs.AI]

(or arXiv:2405.18248v3 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2405.18248

arXiv-issued DOI via DataCite

Submission history

From: Masataro Asai [view email] [v1] Tue, 28 May 2024 14:58:43 UTC (1,567 KB) [v2] Mon, 17 Nov 2025 16:42:45 UTC (1,858 KB) [v3] Thu, 26 Mar 2026 19:08:54 UTC (164 KB)