Discovering State Equivalences in UCT Search Trees By Action Pruning
Created by
- Haebom
Category
Empty
저자
Robin Schmocker, Alexander Dockhorn, Bodo Rosenhahn
개요
몬테카를로 트리 탐색(MCTS)의 효율성을 높이기 위해 상태 또는 상태-행동 쌍을 그룹화/추상화하고 그룹 내에서 통계를 공유하는 접근 방식이 있습니다. On the Go Abstractions in Upper Confidence bounds applied to Trees(OGA-UCT)와 같은 알고리즘에서는 상태-행동 쌍 추상화는 비교적 쉽게 찾을 수 있지만, 노이즈가 많거나 행동 공간이 큰 환경에서는 제약 조건으로 인해 상태 추상화를 거의 찾을 수 없습니다. 본 논문에서는 이러한 주장에 대한 이론적 및 실험적 증거를 제시하고, 많은 수의 추상화를 찾기 위해 정확도의 약간의 손실을 감수하는 더 약한 상태 추상화 조건을 제안하여 이 문제를 약간 완화합니다. 이 기법을 Ideal Pruning Abstractions in UCT (IPA-UCT)라고 명명했으며, 실험적으로 검증된 바와 같이 IPA-UCT는 OGA-UCT(및 파생 상품)보다 다양한 테스트 도메인과 반복 예산에서 성능이 우수합니다. IPA-UCT는 OGA-UCT가 사용하는 Abstraction of State-Action Pairs (ASAP)와는 다른 추상화 프레임워크인 IPA를 사용합니다. 또한, IPA와 ASAP 모두 ASASAP 프레임워크의 특수한 경우인 더 일반적인 프레임워크인 p-ASAP의 특수한 경우임을 보여줍니다.
시사점, 한계점
•
IPA-UCT는 OGA-UCT보다 다양한 테스트 환경에서 우수한 성능을 보입니다.
•
IPA-UCT는 상태 추상화 문제를 해결하기 위해 더 약한 조건을 제시합니다.
•
IPA-UCT는 ASAP와 다른 추상화 프레임워크인 IPA를 사용합니다.
•
IPA와 ASAP 모두 더 일반적인 프레임워크의 특수한 경우로 설명됩니다.
•
논문에서는 노이즈가 많거나 행동 공간이 큰 환경에서의 상태 추상화의 어려움을 해결하는 데 초점을 맞추고 있습니다.
•
정확도의 약간의 손실을 감수해야 할 수 있습니다.
