Improved LinUCT and Its Evaluation on Incremental Random-Feature Tree
Improved LinUCT and Its Evaluation on Incremental Random-Feature Tree
复制标题
增量随机特征树的改进LinUCT及其评估
DOI：
10.1109/cig.2016.7860440
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Y. Mandai and T. Kaneko
中科院分区：
文献类型：
--
作者：
浅野旬吾;伊藤毅志;Y. Mandai and T. Kaneko
UCT是蒙特卡洛树搜索（MCTS）算法的标准方法，已应用于各个领域并取得了显着的成功。本研究提出了一系列 Leaf-LinUCT，它们是将 LinUCB 合并到 MCTS 中的改进的 LinUCT 算法。由于采用岭回归的在线学习，LinUCB 在上下文多臂老虎机问题上的表现优于 UCB1。然而，由于博弈树的极小极大结构，LinUCB 中的岭回归在树搜索中并不总是能很好地工作。在本文中，我们解决了这个问题，并通过两种方式扩展了我们之前在 LinUCT 上的工作：（1）将用于回归的教师数据限制到当前搜索树中的前沿节点，以及（2）将每个内部节点的特征向量调整为后代节点特征向量的加权平均值。我们还通过扩展标准增量随机树模型，提出了一种新的综合模型，增量随机特征树。在我们的模型中，每个节点都有一个特征向量，表示相应位置的特征。节点中特征向量的元素随着每次移动而从其父节点中的元素随机改变，就像标准增量随机树模型中节点的启发式分数随着每次移动而随机改变一样。实验结果表明，在增量随机特征树和[1]中研究的合成游戏中，我们的 Leaf-LinUCT 优于 UCT 和现有的 LinUCT 算法。
UCT is a standard method of Monte Carlo tree search (MCTS) algorithms, which have been applied to various domains and have achieved remarkable success. This study proposes a family of Leaf-LinUCT, which are improved LinUCT algorithms incorporating LinUCB into MCTS. LinUCB outperforms UCB1 in contextual multi-armed bandit problems, owing to a kind of online learning with ridge regression. However, due to the minimax structure of game trees, ridge regression in LinUCB does not always work well in the context of tree search. In this paper, we remedy the problem and extend our previous work on LinUCT in two ways: (1) by restricting teacher data for regression to the frontier nodes in a current search tree, and (2) by adjusting the feature vector of each internal node to the weighted mean of the feature vector of the descendant nodes. We also present a new synthetic model, incremental-random-feature tree, by extending the standard incremental random tree model. In our model, each node has a feature vector that represents the characteristics of the corresponding position. The elements of a feature vector in a node are randomly changed from those in its parent node by each move, as the heuristic score of a node is randomly changed by each move in the standard incremental random tree model. The experimental results show that our Leaf-LinUCT outperformed UCT and existing LinUCT algorithms, in the incremental-random-feature tree and a synthetic game studied in [1].