The Second Type of Uncertainty in Monte Carlo Tree Search
  Monte Carlo Tree Search (MCTS) efficiently balances exploration and
exploitation in tree search based on count-derived uncertainty. However, these
local visit counts ignore a second type of uncertainty induced by the size of
the subtree below an action. We first show how, due to the lack of this second
uncertainty type, MCTS may completely fail in well-known sparse exploration
problems, known from the reinforcement learning community. We then introduce a
new algorithm, which estimates the size of the subtree below an action, and
leverages this information in the UCB formula to better direct exploration.
Subsequently, we generalize these ideas by showing that loops, i.e., the
repeated occurrence of (approximately) the same state in the same trace, are
actually a special case of subtree depth variation. Testing on a variety of
tasks shows that our algorithms increase sample efficiency, especially when the
planning budget per timestep is small.
