Discovering State Equivalences in UCT Search Trees By Action Pruning
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Policy-Space Search: Equivalences, Improvements, and Compression
Fully-observable non-deterministic (FOND) planning is at the core of artificial intelligence planning with uncertainty. It models uncertainty through actions with non-deterministic effects. A* with Non-Determinism (AND*)…
Heuristic SearchSymbolic Physics Learner: Discovering governing equations via Monte Carlo tree search
Nonlinear dynamics is ubiquitous in nature and commonly seen in various science and engineering disciplines. Distilling analytical expressions that govern nonlinear dynamics from limited data remains vital but challengin…
Building and Exploring Semantic Equivalences Resources
Language resources that include semantic equivalences at word level are common, and its usefulness is well established in text processing applications, as in the case of search. Named entities also play an important role…
Information RetrievalOpinion MiningQuestion AnsweringGaussian Processes and Reproducing Kernels: Connections and Equivalences
This monograph studies the relations between two approaches using positive definite kernels: probabilistic methods using Gaussian processes, and non-probabilistic methods using reproducing kernel Hilbert spaces (RKHS). T…
Gaussian ProcessesNumerical IntegrationThe Pascal Triangle of a Discrete Image: Definition, Properties and Application to Shape Analysis
We define the Pascal triangle of a discrete (gray scale) image as a pyramidal arrangement of complex-valued moments and we explore its geometric significance. In particular, we show that the entries of row k of this tria…