Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds

Monte Carlo Tree Search with Sampled Information Relaxation Dual Bounds
复制标题

具有采样信息松弛双界的蒙特卡洛树搜索

DOI：
--
复制
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
通讯作者：
Warrren B Powell
Warrren B Powell
中科院分区：
--
文献类型：
--
作者：
Daniel R. Jiang;L. Al;Warrren B Powell

文献摘要

被引文献

相似文献

蒙特卡洛树搜索 (MCTS) 最著名地用于游戏人工智能（例如围棋游戏），是一种众所周知的构建顺序决策问题近似解的策略。其主要创新是使用启发式（称为默认策略）来获取决策树中状态下游值的蒙特卡洛估计。此信息用于迭代地将树扩展到最佳策略可能访问的状态和操作区域。然而，为了保证收敛到最优动作，MCTS 需要渐近扩展整个树。在本文中，我们提出了一种称为 Primal-Dual MCTS 的新技术，该技术利用潜在操作的采样信息松弛上限，从而创建“忽略”源自高度次优选择的树部分的可能性。这使我们能够证明，尽管在极限情况下收敛到部分决策树，Primal-Dual MCTS 推荐的操作是最优的。当用于优化单个驾驶员在乘车共享平台上操作时导航图表的行为时，新方法显示出巨大的前景。对新泽西州 7,000 次行程的真实数据集进行的数值实验表明，Primal-Dual MCTS 通过生成更深的决策树来改进标准 MCTS，并表现出对动作空间大小的敏感性降低。
Monte Carlo Tree Search (MCTS), most famously used in game-play artificial intelligence (e.g., the game of Go), is a well-known strategy for constructing approximate solutions to sequential decision problems. Its primary innovation is the use of a heuristic, known as a default policy, to obtain Monte Carlo estimates of downstream values for states in a decision tree. This information is used to iteratively expand the tree towards regions of states and actions that an optimal policy might visit. However, to guarantee convergence to the optimal action, MCTS requires the entire tree to be expanded asymptotically. In this paper, we propose a new technique called Primal-Dual MCTS that utilizes sampled information relaxation upper bounds on potential actions, creating the possibility of "ignoring" parts of the tree that stem from highly suboptimal choices. This allows us to prove that despite converging to a partial decision tree in the limit, the recommended action from Primal-Dual MCTS is optimal. The new approach shows significant promise when used to optimize the behavior of a single driver navigating a graph while operating on a ride-sharing platform. Numerical experiments on a real dataset of 7,000 trips in New Jersey suggest that Primal-Dual MCTS improves upon standard MCTS by producing deeper decision trees and exhibits a reduced sensitivity to the size of the action space.