  Despite being successful in board games and reinforcement learning (RL), UCT,
a Monte-Carlo Tree Search (MCTS) combined with UCB1 Multi-Armed Bandit (MAB),
has had limited success in domain-independent planning until recently. Previous
work showed that UCB1, designed for $[0,1]$-bounded rewards, is not appropriate
for estimating the distance-to-go which are potentially unbounded in
$\mathbb{R}$, such as heuristic functions used in classical planning, then
proposed combining MCTS with MABs designed for Gaussian reward distributions
and successfully improved the performance. In this paper, we further sharpen
our understanding of ideal bandits for planning tasks. Existing work has two
issues: First, while Gaussian MABs no longer over-specify the distances as
$h\in [0,1]$, they under-specify them as $h\in [-\infty,\infty]$ while they are
non-negative and can be further bounded in some cases. Second, there is no
theoretical justifications for Full-Bellman backup (Schulte & Keller, 2014)
that backpropagates minimum/maximum of samples. We identified \emph{extreme
value} statistics as a theoretical framework that resolves both issues at once
and propose two bandits, UCB1-Uniform/Power, and apply them to MCTS for
classical planning. We formally prove their regret bounds and empirically
demonstrate their performance in classical planning.
