POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with\n Non-Asymptotic Analysis

Abstract

Monte-Carlo planning, as exemplified by Monte-Carlo Tree Search (MCTS), has\ndemonstrated remarkable performance in applications with finite spaces. In this\npaper, we consider Monte-Carlo planning in an environment with continuous\nstate-action spaces, a much less understood problem with important applications\nin control and robotics. We introduce POLY-HOOT, an algorithm that augments\nMCTS with a continuous armed bandit strategy named Hierarchical Optimistic\nOptimization (HOO) (Bubeck et al., 2011). Specifically, we enhance HOO by using\nan appropriate polynomial, rather than logarithmic, bonus term in the upper\nconfidence bounds. Such a polynomial bonus is motivated by its empirical\nsuccesses in AlphaGo Zero (Silver et al., 2017b), as well as its significant\nrole in achieving theoretical guarantees of finite space MCTS (Shah et al.,\n2019). We investigate, for the first time, the regret of the enhanced HOO\nalgorithm in non-stationary bandit problems. Using this result as a building\nblock, we establish non-asymptotic convergence guarantees for POLY-HOOT: the\nvalue estimate converges to an arbitrarily small neighborhood of the optimal\nvalue function at a polynomial rate. We further provide experimental results\nthat corroborate our theoretical findings.\n