Nonasymptotic Analysis of Monte Carlo Tree Search
研究了无限期折扣马尔可夫决策过程中蒙特卡洛树搜索的收敛性，发现使用多项式而非对数奖励项能保证收敛，并证明其结合最近邻监督学习可迭代改进价值函数近似。
In “Nonasymptotic Analysis of Monte Carlo Tree Search,” D. Shah, Q. Xie, and Z. Xu consider the popular tree-based search strategy, the Monte Carlo Tree Search (MCTS), in the context of the infinite-horizon discounted Markov decision process. They show that MCTS with an appropriate polynomial rather than logarithmic bonus term indeed leads to the desired convergence property. The authors derive the results by establishing a polynomial concentration property of regret for a class of nonstationary multiarm bandits. Furthermore, using this as a building block, they demonstrate that MCTS, combined with nearest neighbor supervised learning, acts as a “policy improvement” operator that can iteratively improve value function approximation.