Factored MCTS for Large Scale Stochastic Planning
Factored MCTS for Large Scale Stochastic Planning
复制标题
用于大规模随机规划的分解 MCTS
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Prasad Tadepalli
中科院分区：
文献类型：
--
作者：
Hao Cui;R. Khardon;Alan Fern;Prasad Tadepalli
研究了具有大因子状态和行动空间的随机规划问题。我们表明，即使现有挑战问题的规模适度增加，最先进算法的性能也会迅速恶化，使其失效。为了解决这个问题，我们提出了一系列简单但可扩展的在线规划算法，这些算法将抽样（如蒙特卡洛树搜索）与“聚合”相结合，其中聚合通过其边际的乘积近似随机变量的分布。这些算法在一些较强的技术条件下是正确的，在条件不成立时可以作为一种不健全但有效的启发式。一项广泛的实验评估表明，在解决许多挑战基准领域的大型问题时，新算法比现有算法有了显著的改进。
This paper investigates stochastic planning problemswith large factored state and action spaces. We show that even with moderate increase in the size of existing challenge problems, the performance of state of the art algorithms deteriorates rapidly, making them ineffective.To address this problem we propose a family of simple but scalable online planning algorithms that combine sampling, as in Monte Carlo tree search, with “aggregation,” where the aggregation approximates a distribution over random variables by the product of their marginals. The algorithms are correct under some rather strong technical conditions and can serve as an unsound but effective heuristic when the conditions do not hold. An extensive experimental evaluation demonstrates that the new algorithms provide significant improvement over the state of the art when solving largeproblems in a number of challenge benchmark domains.