通过动作修剪在UCT搜索树中发现状态等价关系

于红博

摘要: 一种增强蒙特卡洛树搜索（MCTS）的方法是通过对状态或状态-动作对进行分组/抽象，共享组内统计信息，从而提高其采样效率。尽管在算法中很容易找到状态-动作对的抽象，比如在应用于树的上限置信界（OGA-UCT）中，但在噪声较大或动作空间较大的情况下几乎找不到状态的抽象，因为受到了约束条件的限制。我们提供了理论和实证证据支持这一说法，并通过提出一个较弱的状态抽象条件，稍微缓解了这一问题，牺牲了一定准确性以换取更多的抽象。我们将这一技术命名为理想修剪抽象在UCT（IPA-UCT），在大范围的测试领域和实验验证的迭代预算中，IPA-UCT优于OGA-UCT（及其任何衍生物）。IPA-UCT使用与OGA-UCT使用的状态-动作对抽象（ASAP）不同的抽象框架，我们将其命名为IPA。此外，我们展示了IPA和ASAP都是更一般框架的特例，我们称之为p-ASAP，它本身是ASASAP框架的一个特例。

更新时间: 2025-10-30 10:54:43

领域: cs.AI

下载: http://arxiv.org/abs/2510.26346v1