通过动作剪枝发现UCT搜索树中的状态等价，提升采样效率。
Discovering State Equivalences in UCT Search Trees By Action Pruning
- 提出IPA-UCT框架，以弱化条件实现更多状态抽象
- 在多领域测试中优于OGA-UCT，且在不同迭代预算下表现稳定
- 适用于动作空间大或噪声高的复杂决策场景
提升蒙特卡洛树搜索（MCTS）样本效率的一种方法是通过分组/抽象状态或状态-动作对，并在组内共享统计信息。尽管状态-动作对抽象在如上界置信度应用于树（OGA-UCT）等算法中较易实现，但在高噪声或大动作空间设置下几乎无法找到状态抽象，这是由严格约束条件所致。本文提供理论与实证证据支持此观点，并通过提出一种更弱的状态抽象条件，在小幅损失精度的前提下显著增加可发现的抽象数量。该方法命名为理想剪枝抽象于UCT（IPA-UCT），实验验证其在多种测试域和迭代预算下均优于OGA-UCT及其衍生方法。IPA-UCT采用与OGA-UCT不同的抽象框架（即IPA），同时证明IPA与ASAP均为更通用框架p-ASAP的特例，而p-ASAP又是ASASAP框架的特例。
原文摘要 · Abstract (English)
One approach to enhance Monte Carlo Tree Search (MCTS) is to improve its sample efficiency by grouping/abstracting states or state-action pairs and sharing statistics within a group. Though state-action pair abstractions are mostly easy to find in algorithms such as On the Go Abstractions in Upper Confidence bounds applied to Trees (OGA-UCT), nearly no state abstractions are found in either noisy or large action space settings due to constraining conditions. We provide theoretical and empirical evidence for this claim, and we slightly alleviate this state abstraction problem by proposing a weaker state abstraction condition that trades a minor loss in accuracy for finding many more abstractions. We name this technique Ideal Pruning Abstractions in UCT (IPA-UCT), which outperforms OGA-UCT (and any of its derivatives) across a large range of test domains and iteration budgets as experimentally validated. IPA-UCT uses a different abstraction framework from Abstraction of State-Action Pairs (ASAP) which is the one used by OGA-UCT, which we name IPA. Furthermore, we show that both IPA and ASAP are special cases of a more general framework that we call p-ASAP which itself is a special case of the ASASAP framework.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。