- 论文题目：Watch The Unobserved：A Simple Approach To Parallelizing Monte Carlo Tree Search
所解决的问题
提出一种并行化的MCTS算法，该算法实现了线性加速，并随着Workers的增加，性能只有些许损失。
背景
MCTS的缺点就是无法并行，但是并行之后没有性能损失是比较困难的，主要的原因就是MCTS的探索-利用的平衡会依赖于之前的采样信息。作者提出一种新奇的并行化MCTS算法，WU-UCT(Watch the Unovserved in UCT)，在有限的性能损失下实现了线性加速。
MCTS
MCTS不断重复以下四个步骤：
- Selection
- Expansion
一旦选择过程到达搜索树的一个叶子节点（或满足其他终止条件），我们将根据事先的策略，通过增加一个新的子节点来扩展该节点。
- Simulation
基于策略π ，进行simulation，评估累计奖励(cumulative reward) 
- Backpropagation
虽然最新树展开过程中的数据的要求不是强制执行的，但在实践中，为了实现有效的勘探-开采权衡，它是必须的。
从一个节点下来，并行展开rollout计算。当采用并行化的方法，确保每个worker都能使用最新的统计数据(V s 和N s )将大大影响性能。由于expansion和simulation这两步比其它两步所耗费的时间要多，因此想要worker同步更新是比较困难的。并且并行化由于statistic信息整体一样，并行化展开会选择到相同节点。
经典的MCTS并行方法
LeafP缺乏探索性，而TreeP这种方法可能会导致exploitation失败，因为其即使知道了某个节点是最优的，也会减少这个节点的模拟次数。RootP通过worker独立的tree search来减少上述两个问题，但是这减少了每个worker的rollout数量，并且会减少UCT的准确性。
所采用的方法？
作者采取的办法是，如果有某个节点被选中，那么在不久的将来一定会得到它的Simulation Return，因此可以看作其已经被选择过了。设计 O s 去计算已经被初始化rollouts但是并没有做完(simulation完)的数量。
WU-UCT的核心思想是通过a set of statistics来平衡探索利用，同时还没有得到simulation返回值的访问节点来做 (named as unobserved samples)。
取得的效果？
在Atari games游戏上的性能。
所出版信息？作者信息？
ICLR2020上的一篇文章，来自Tencent AI Lab，第一作者刘安吉,本科毕业于北京航空航天大学自动化系。于2018年12月-2019年6月在快手实习，现兼职快手顾问。
参考资料
- Code：https://github.com/liuanji/WU-UCT
- UCT：Levente Kocsis, Csaba Szepesv´ari, and Jan Willemson. Improved monte-carlo search. Univ. Tartu,
Estonia, Tech. Rep, 1, 2006. - UCB：Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit
problem. Machine learning, 47(2-3):235–256, 2002.
