是的，在无限内存和计算时间的假设下，蒙特卡洛树搜索 (MCTS) 已被证明可以收敛到最优解。也就是说，至少对于完全信息、确定性游戏/MDP 的情况。

也许一些证明也涵盖了其他一些问题（我可以直观地想象这些证明也适用于非确定性游戏，具体取决于实现细节）......但我上面提到的问题类别是我确定的. 最初的经典证明可以在以下位置找到：

• Levente Kocsis, Csaba Szepesvári基于 Bandit 的蒙特卡洛规划
• Levente Kocsis、Csaba Szepesvári、Jan Willemson改进的蒙特卡洛搜索

最近发表在 arXiv 上的论文On Reinforcement Learning Using Monte Carlo Tree Search with Supervised Learning: Non-Asymptotic Analysis出现在 arXiv 上，我看到其中提到那些原始论文可能存在一些缺陷，但它们似乎也能够修复它并为在 MCTS 中结合（深度）学习方法的更“现代”变体添加更多理论。

应该注意的是，通常情况下，所有这些收敛证明都是针对您花费无限时间运行算法的情况。在 MCTS 的情况下，您可以直观地认为，只有在您的算法设法建立完整的搜索树之后，证明才开始成立，然后在此之上有足够的时间充分遍历树中的所有可能路径通常用于反向传播正确的值。对于大多数有趣的问题，这不太可能是现实的（如果可行，更简单的广度优先搜索算法可能是更好的选择）。

在收敛速度方面它与时间差分学习相比如何（假设评估步骤有点慢）？

如果您正在考虑像 Sarsa 这样的标准的表格 TD 学习方法……这些方法实际上与 MCTS 密切相关。就收敛速度而言，我想说的重要区别是：

• MCTS 专注于单一状态的“学习”，即根状态；所有努力都是为了获得该节点（及其直接子节点）的准确值估计，而典型的 TD 实现是关于立即学习完整的状态空间。我想 MCTS 的“焦点”可以提高它对该特定状态的收敛速度......
• 但事实上，搜索树（可以看作是它的“表”）$Q$-您在 Sarsa 中看到的值或$Q$-learning）与表格 TD 学习方法相比，仅缓慢增长也可能是一个缺点，表格 TD 学习方法从一个完整的表格开始，涵盖了完整的状态空间。

请注意，我在上面链接的最后一篇论文显示了 MCTS 如何实际上也可以使用时间差异学习来通过树备份值……所以从“MCTS 与 TD 学习”的角度来看并不是真的当您考虑可以在 MCTS 中使用 TD 学习时，这太有意义了。

有没有办法利用在模拟阶段收集的信息来加速 MCTS？

有很多很多这样的想法往往会根据经验提高性能。不过，理论上很难对它们说太多。我脑海中的一些例子：

• 所有动作为先 (AMAF)
• 快速行动价值估计（RAVE，另见 GRAVE）
• 移动平均抽样技术 (MAST)
• N-Gram 选择技术 (NST)
• Last-Good-Reply 政策
• ...

其中许多可以在本调查报告中找到，但现在有些旧（从 2012 年开始），所以它不包括所有最新的东西。