标题： 蒙特卡罗树搜索的非渐近分析 显示英文标题

标题： Non-Asymptotic Analysis of Monte Carlo Tree Search

摘要： 在本工作中，我们考虑在无限时域折扣成本马尔可夫决策过程（MDP）框架内的强化学习中流行的基于树的搜索策略，即蒙特卡洛树搜索（MCTS）。 虽然认为MCTS在足够模拟的情况下可以为给定状态提供近似值函数，但早期工作的声称证明是不完整的。 这是由于先前工作中分析的变体，即基于树的上界置信度（UCT），在树搜索中使用了“对数”奖励项来平衡探索与利用，这源于随机多臂老虎机（MAB）文献中的见解。 实际上，这种方法假设了底层递归依赖的非平稳MAB的遗憾在步骤数上以指数方式集中在均值附近，正如文献中指出的那样，即使对于平稳MAB来说，这种情况也很可能不成立。 作为本工作的关键贡献，我们建立了非平稳MAB类的遗憾的多项式集中性质。 反过来，这证明了在UCB中使用适当的多项式而非对数奖励项的MCTS具有所声称的性质。 以此为基础，我们论证了MCTS结合最近邻监督学习起到了“策略改进”算子的作用：由于结合了监督学习，它迭代地改进所有状态的值函数近似，尽管只评估有限数量的状态。 实际上，我们建立了为了在$\ell_\infty$范数下学习值函数的$\varepsilon$近似，MCTS结合最近邻所需的样本量按$\widetilde{O}\big(\varepsilon^{-(d+4)}\big)$增长，其中$d$是状态空间的维度。 由于存在$\widetilde{\Omega}\big(\varepsilon^{-(d+2)}\big)$的最小最大下界，这是几乎最优的。 显示英文摘要

摘要： In this work, we consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of infinite-horizon discounted cost Markov Decision Process (MDP). While MCTS is believed to provide an approximate value function for a given state with enough simulations, the claimed proof in the seminal works is incomplete. This is due to the fact that the variant, the Upper Confidence Bound for Trees (UCT), analyzed in prior works utilizes "logarithmic" bonus term for balancing exploration and exploitation within the tree-based search, following the insights from stochastic multi-arm bandit (MAB) literature. In effect, such an approach assumes that the regret of the underlying recursively dependent non-stationary MABs concentrates around their mean exponentially in the number of steps, which is unlikely to hold as pointed out in literature, even for stationary MABs. As the key contribution of this work, we establish polynomial concentration property of regret for a class of non-stationary MAB. This in turn establishes that the MCTS with appropriate polynomial rather than logarithmic bonus term in UCB has the claimed property. Using this as a building block, we argue that MCTS, combined with nearest neighbor supervised learning, acts as a "policy improvement" operator: it iteratively improves value function approximation for all states, due to combining with supervised learning, despite evaluating at only finitely many states. In effect, we establish that to learn an $\varepsilon$ approximation of the value function with respect to $\ell_\infty$ norm, MCTS combined with nearest neighbor requires a sample size scaling as $\widetilde{O}\big(\varepsilon^{-(d+4)}\big)$, where $d$ is the dimension of the state space. This is nearly optimal due to a minimax lower bound of $\widetilde{\Omega}\big(\varepsilon^{-(d+2)}\big)$.