中国科学技术大学：《信息检索与数据挖掘》课程教学资源（研讨汇报）Memory - Augmented Monte Carlo Tree Search

Memory-Augmented Monte Carlo Tree Search* SA18033015夏秋冬 Xiao C,Mei J,Muller M.Memory-augmented monte carlo tree search[C]//Thirty-Second AAAI Conference on Artificial Intelligence.2018

1 Memory-Augmented Monte Carlo Tree Search* SA18033015 夏秋冬 * Xiao C, Mei J, Müller M. Memory-augmented monte carlo tree search[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018

ABSTRART 这篇论文提出了记忆增强的蒙特卡洛树搜索算法 (Memory-Augmented Monte Carlo Tree Search M-MCTS),为在线实时搜索提供了一个新的利用泛 化性的方法。 M-MTCS的核心思想是为MCTS增加了一个记忆结 构，该结构的每一个入口都含有一个特殊状态信息。 记忆结构结合相似状态的估计产生一个近似的值估计

ABSTRART 这篇论文提出了记忆增强的蒙特卡洛树搜索算法 （Memory-Augmented Monte Carlo Tree Search， M-MCTS），为在线实时搜索提供了一个新的利用泛 化性的方法。 M-MTCS 的核心思想是为 MCTS 增加了一个记忆结 构，该结构的每一个入口都含有一个特殊状态信息。 记忆结构结合相似状态的估计产生一个近似的值估计

ABSTRART 作者发现，基于记忆的值估计结果比温和条件下高 概率的普通蒙特卡洛算法估计结果更好。 作者在围棋游戏中评测了M-MCTS的性能。实验 结果表明，在相同模拟次数下，M-MCTS优于原 来的MCTS

ABSTRART • 作者发现，基于记忆的值估计结果比温和条件下高 概率的普通蒙特卡洛算法估计结果更好。 • 作者在围棋游戏中评测了 M-MCTS 的性能。实验 结果表明，在相同模拟次数下，M-MCTS 优于原 来的 MCTS

背景介绍 蒙特卡罗树搜索(Monte Carlo Tree Search) 蒙特卡罗树搜索是一种基于树数据结构、能权衡 探索与利用、在搜索空间巨大仍然比较有效的的 搜索算法 MCTS是一种找到逼近纳什均衡衡的搜索策略，一般 用于通用游戏的对弈问题中

背景介绍 蒙特卡罗树搜索（Monte Carlo Tree Search） • 蒙特卡罗树搜索是一种基于树数据结构、能权衡 探索与利用、在搜索空间巨大仍然比较有效的的 搜索算法 • MCTS是一种找到逼近纳什均衡的搜索策略,一般 用于通用游戏的对弈问题中

背景介绍 MCTS: ·选举selection)是根据当前获得所 BaCK-PF008B8T16 有子步骤的统计结果，选择一个 最优的子步骤。 Select tne pest action ang reture 扩展(expansion)在当前获得的统 计结果不足以计算出下一个步骤 时，随机选择一个子步骤。 模拟(simulation)模拟游戏，进入 下一步。 ingry.Stay Foolis 反向传播Back-Propagation)根据 游戏结束的结果，计算对应路径 上统计记录的值

背景介绍 MCTS: • 选举(selection)是根据当前获得所 有子步骤的统计结果，选择一个 最优的子步骤。 • 扩展(expansion)在当前获得的统 计结果不足以计算出下一个步骤 时，随机选择一个子步骤。 • 模拟(simulation)模拟游戏，进入 下一步。 • 反向传播(Back-Propagation)根据 游戏结束的结果，计算对应路径 上统计记录的值

背景介绍 蒙特卡罗树搜索(Monte Carlo Tree Search) ·MCTS的一种经典实现：UCB算法 Q(w'） 21n N(v) arg max u'∈children ofvN(u') +cy N() 其中v表示当前树节点，V表示父节点，Q表示这个树节点的 累计qualityf值，N表示这个树节点的visit)次数，C是一个常 量参数（可以控制exploitation和exploration权重）

背景介绍 蒙特卡罗树搜索（Monte Carlo Tree Search） • MCTS的一种经典实现：UCB算法 • 其中v'表示当前树节点，v表示父节点，Q表示这个树节点的 累计quality值，N表示这个树节点的visit次数，C是一个常 量参数（可以控制exploitation和exploration权重）

Motivation 然而，对于巨大的状态空间，MCTS值估计的准确率不能得 到有效保证，因为在有限的搜索时间内，平均值估计容易呈 现较高方差。这种不准确的估计会误导搜索树的构建方向， 从而严重影响算法的性能。 近期提出了几个新的机器学习算法，旨在解决MCTS的这 一缺点。例如，使用深度神经网络来学习域知识，并近似状 态值函数。它们与MCTS的结合为实践中提高搜索样本效 率带来了启发式算法

Motivation • 然而，对于巨大的状态空间，MCTS值估计的准确率不能得 到有效保证，因为在有限的搜索时间内，平均值估计容易呈 现较高方差。这种不准确的估计会误导搜索树的构建方向， 从而严重影响算法的性能。 • 近期提出了几个新的机器学习算法，旨在解决 MCTS 的这 一缺点。例如，使用深度神经网络来学习域知识，并近似状 态值函数。它们与 MCTS 的结合为实践中提高搜索样本效 率带来了启发式算法

Motivation 目前已有大量的研究从离线学习中发现泛化能力，相比之下 很少有人关注在线实时搜索时如何利用算法泛化带来的好处。 这篇论文提出了记忆增强的MCTS算法，为利用在线泛化 提供了一个不一样的方法。 作者设计了一个记忆结构(memory), 每一个入口包含某 一个特定状态的信息，作为构建在线值近似的基础。论文从 理论和实践（围棋游戏实验）上证实了该基于记忆的框架对 MCTS性能的提升

Motivation • 目前已有大量的研究从离线学习中发现泛化能力，相比之下 很少有人关注在线实时搜索时如何利用算法泛化带来的好处。 这篇论文提出了记忆增强的 MCTS 算法，为利用在线泛化 提供了一个不一样的方法。 • 作者设计了一个记忆结构（memory），每一个入口包含某 一个特定状态的信息，作为构建在线值近似的基础。论文从 理论和实践（围棋游戏实验）上证实了该基于记忆的框架对 MCTS 性能的提升

M-MCTS 增强的蒙特卡洛树的主要思想就是：在一个记忆 的帮助下，去接近变量的估计。每个元素都包含 着特征的代表和一个特殊状态的模拟统计 M-MCTS搜索树的每一个节点都会存储统计的一 个扩展集合： IN(s),V(s),NM(s),VM(s)}

M-MCTS 增强的蒙特卡洛树的主要思想就是：在一个记忆 的帮助下，去接近变量的估计。每个元素都包含 着特征的代表和一个特殊状态的模拟统计 M-MCTS 搜索树的每一个节点都会存储统计的一 个扩展集合：

M-MCTS 近似估计如下进行：给定一个记忆μ和一个状态x, 我们根据距离度量d(,)找到M个最相似的状 态梨x,并且计算一下基于记忆的变量估计值： 立M(x)=∑1(x)V(),s.t.∑1w(x)=1

M-MCTS 近似估计如下进行：给定一个记忆μ和一个状态x， 我们根据距离度量d（·，x）找到M个最相似的状 态μx，并且计算一下基于记忆的变量估计值：