为什么蒙特卡罗树搜索会重置树？

Question

我有一个关于蒙特卡罗树搜索的小问题，可能有些愚蠢。我理解大部分内容，但看了一些实现后发现，在给定状态下运行MCTS并返回最佳移动后，树会被丢弃。因此，对于下一步，我们必须从头开始在这个新状态下运行MCTS以获取下一个最佳位置。

我只是想知道为什么我们不保留旧树中的一些信息。似乎旧树中有关状态的有价值信息，尤其是考虑到最佳移动是MCTS探索最多的移动之一。我们不能以某种有用的方式使用这些旧信息吗？

- gowrath

---

可能是由于随机依赖关系。根本问题已经改变，因此可能会遍历不同的路径。在minmax中，我认为，在做出50步决策时，我们可以重复使用我们已经预先计算的数据的1/50（简化；损失巨大），但在MCTS中，这可能不是数学证明方面的轻松事情，如果我们要重新使用这些数据。我认为这篇论文正在分析这个问题（第5章）。这是一个有趣的问题，但我相信它不适合在StackOverflow上讨论，因为这个主题远离编码，更多的是数学。 - sascha

仅供将来参考（上面的评论太长了）：我链接的那篇论文名为“信息获取和重用策略在蒙特卡罗树搜索中的应用，适用于隐藏信息的游戏。”（Powley, Edward J., Peter I. Cowling, and Daniel Whitehouse. "Information capture and reuse strategies in Monte Carlo Tree Search, with applications to games of hidden information." Artificial Intelligence 217 (2014): 92-116.） - sascha

Answer 1

有些实现确实会保留信息。

例如，AlphaGo Zero 论文中提到：

搜索树在后续时间步骤中被重复使用：对应于已执行动作的子节点成为新的根节点；该子树以及所有统计信息均被保留，而其余部分则被丢弃。

- Peter de Rivaz

---

为什么树的余数被丢弃？考虑到策略是固定的，MCTS运行期间收集的信息根本不会过时。数据被丢弃只是为了释放RAM吗？ - HappyFace

我同意通过转换保持可达位置可能会有所帮助，特别是在像围棋这样的游戏中。这听起来像是一个潜在的改进。 - Peter de Rivaz

Answer 2

原因可能是以下几点。

Rollouts是截断的价值估计，超过最大长度的贡献将被丢弃。

假设最大Rollout深度为N。

如果您考虑的环境中平均奖励不等于0（假设>0）。

在采取行动并获得观察结果后，树的子节点可以被选择。

现在，分支的最大长度和参与评估节点值的Rollout的最大长度为N-1，因为根节点已被丢弃。

然而，新的模拟显然仍然具有长度N，但它们必须与长度为N-1的模拟相结合。

较长的模拟将具有偏差的值，因为平均奖励不等于0。

这意味着使用混合长度评估的节点将具有偏差，具体取决于具有不同长度模拟的比例。

避免使用较短的旧模拟的另一个原因是由于对抽样产生的偏差。想象一下T型迷宫，在左侧的深度d处，最大奖励为R/2，而在右侧的深度d+1处，最大奖励为R。所有到达深度d处的R/2奖励的路径在第一步时都能够到达，这些路径将在第二步中使用回收树时得到优先考虑，而通向右侧的路径将不太常见，达到奖励R的机会更小。从空树开始将给迷宫两侧相同的概率。

Alpha Go Zero（请参见Peter de Rivaz的答案）实际上不使用rollouts，而是使用价值估计（由深度网络生成）。值不是截断估计。因此，Alpha Go Zero不受此分支长度偏差的影响。

Alpha Go是Alpha Go Zero的前身，结合了rollouts和价值估计，并且重用了树形结构。但是新版本不使用rollouts，也许就是出于这个原因。Alpha Go Zero和Alpha Go都不使用动作的值，而是使用搜索期间选择该动作的次数。在平均奖励为负数的情况下，该值可能不太受长度偏差的影响。

希望这很清楚。

- Dimitri Ognibene