为什么 Monte Carlo Tree Search 会重置 Tree
Why does Monte Carlo Tree Search reset Tree
我有一个关于 Monte Carlo Tree Search 的小问题，但可能很愚蠢。我了解其中的大部分内容，但一直在研究一些实现，并注意到在给定状态的 MCTS 为 运行 并且返回最佳移动后，树被丢弃了。所以对于下一步，我们必须 运行 在这个新状态上从头开始 MCTS 以获得下一个最佳位置。
我只是想知道为什么我们不保留旧树中的一些信息。似乎有关于旧树中状态的有价值信息，特别是考虑到最好的一步是 MCTS 探索最多的一步。我们不能以某种有用的方式使用这些旧信息有什么特别的原因吗？
一些实现确实保留了信息。
例如，the AlphaGo Zero paper表示：
The search tree is reused
at subsequent time-steps: the child node corresponding to the played action becomes the new root
node; the subtree below this child is retained along with all its statistics, while the remainder of
the tree is discarded
嗯，原因可能如下。
转出是截断值估计，最大长度后的贡献被丢弃。
假设最大展开深度为 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 和 value approximation 并且还重用了树..但是没有新版本不使用 rollouts..可能是这个原因。此外，Alpha Go Zero 和 Alpha Go 都不使用操作的值，而是使用搜索期间选择的次数。这个值可能受长度偏差的影响较小，至少在平均奖励为负的情况下
希望这是清楚的..
我有一个关于 Monte Carlo Tree Search 的小问题，但可能很愚蠢。我了解其中的大部分内容，但一直在研究一些实现，并注意到在给定状态的 MCTS 为 运行 并且返回最佳移动后，树被丢弃了。所以对于下一步，我们必须 运行 在这个新状态上从头开始 MCTS 以获得下一个最佳位置。
我只是想知道为什么我们不保留旧树中的一些信息。似乎有关于旧树中状态的有价值信息，特别是考虑到最好的一步是 MCTS 探索最多的一步。我们不能以某种有用的方式使用这些旧信息有什么特别的原因吗？
一些实现确实保留了信息。
例如，the AlphaGo Zero paper表示：
The search tree is reused at subsequent time-steps: the child node corresponding to the played action becomes the new root node; the subtree below this child is retained along with all its statistics, while the remainder of the tree is discarded
嗯，原因可能如下。
转出是截断值估计，最大长度后的贡献被丢弃。
假设最大展开深度为 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 和 value approximation 并且还重用了树..但是没有新版本不使用 rollouts..可能是这个原因。此外，Alpha Go Zero 和 Alpha Go 都不使用操作的值，而是使用搜索期间选择的次数。这个值可能受长度偏差的影响较小，至少在平均奖励为负的情况下
希望这是清楚的..