2024/05/28 by Masataro Asai, Asai, Masataro, Stephen Wissow +1 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #FOS: Computer and information sciences #Statistical and Computational Modeling #Time Series Analysis and Forecasting
paper · pdf · doi:10.48550/arxiv.2405.18248
openalex publication_date 2024/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (-∞,∞), which we can narrow down. Second, Full Bellman backup (Schulte and Keller 2014), which backpropagates sample max/min, lacks theoretical justification. We use 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.