提出新抽象方法,让不同价值的状态也能合并,提升搜索效率。
Grouping Nodes With Known Value Differences: A Lossless UCT-based Abstraction Algorithm
- 基于已知价值差进行状态分组,突破传统等值要求
- 在多种环境下比OGA-UCT发现更多抽象,性能更优
- 无需新增参数,适用于各类确定性环境
蒙特卡洛树搜索(MCTS)的核心挑战是采样效率低。现有最优算法OGA-UCT基于状态-动作对抽象框架(ASAP),通过分析搜索图识别最优策略下价值相同的节点。但ASAP要求两个状态-动作对具有相同即时奖励,这一严格条件限制了可发现的抽象数量,从而制约采样效率。本文提出新的抽象框架Known Value Difference Abstractions(KVDA),不再要求价值相等,只要能推断出价值差异即可进行分组。通过分析即时奖励来推断价值差,并将该机制融入OGA-UCT,得到新算法KVDA-UCT。该方法显著提升了可抽象节点数量,未引入额外参数,在多种确定性环境和参数设置下均优于OGA-UCT。
原文摘要 · Abstract (English)
A core challenge of Monte Carlo Tree Search (MCTS) is its sample efficiency, which can be improved by grouping state-action pairs and using their aggregate statistics instead of single-node statistics. On the Go Abstractions in Upper Confidence bounds applied to Trees (OGA-UCT) is the state-of-the-art MCTS abstraction algorithm for deterministic environments that builds its abstraction using the Abstractions of State-Action Pairs (ASAP) framework, which aims to detect states and state-action pairs with the same value under optimal play by analysing the search graph. ASAP, however, requires two state-action pairs to have the same immediate reward, which is a rigid condition that limits the number of abstractions that can be found and thereby the sample efficiency. In this paper, we break with the paradigm of grouping value-equivalent states or state-action pairs and instead group states and state-action pairs with possibly different values as long as the difference between their values can be inferred. We call this abstraction framework Known Value Difference Abstractions (KVDA), which infers the value differences by analysis of the immediate rewards and modifies OGA-UCT to use this framework instead. The modification is called KVDA-UCT, which detects significantly more abstractions than OGA-UCT, introduces no additional parameter, and outperforms OGA-UCT on a variety of deterministic environments and parameter settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。