Time-critical and confidence-based abstraction dropping methods

Robin Schmöcker, Lennart Kampmann, Alexander Dockhorn · 2025

Read Time-critical and confidence-based abstraction dropping methods by Robin Schmöcker, Lennart Kampmann, Alexander Dockhorn (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-02703.txt.

Introduction

Robin Schmöcker and co-authors refine when game-playing search algorithms should drop their shortcuts, in a 2025 paper. Monte Carlo tree search can be sped up by grouping similar states into abstractions. Inexact groupings, though, poison the endgame: the search can never settle on the truly best move while they last. Dropping the abstraction late is the standard cure, but the known dropping rule sometimes hurts.

Two new schemes are proposed. One targets time-critical play, the other squeezes more strength from a fixed iteration budget. Both improved performance clearly in tests. Unlike the earlier method, neither ever caused a notable drop when the abstraction was lifted. Safe dropping makes abstraction a free lunch more often.

Catalog record

CREATORRobin Schmöcker, Lennart Kampmann, Alexander Dockhorn
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-02703

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Time-critical and confidence-based abstraction dropping methods Robin Schmöcker, Lennart Kampmann, Alexander Dockhorn Abstract One paradigm of Monte Carlo Tree Search (MCTS) improvements is to build and use state and/or action abstractions during the tree search. Non-exact abstractions, however, introduce an approximation error making convergence to the optimal action in the abstract space impossible. Hence, as proposed as a component of Elastic Monte Carlo Tree Search by Xu et al., abstraction algorithms should eventually drop the abstraction. In this paper, we propose two novel abstraction dropping schemes, namely OGA-IAAD and OGA-CAD which can yield clear performance improvements whilst being safe in the sense that the dropping never causes any notable performance degradations contrary to Xu’s dropping method. OGA-IAAD is designed for time critical settings while OGA-CAD is designed to improve the MCTS performance with the same number of iterations. I Introduction Monte Carlo Tree Search (MCTS) [ 3 ] is a popular on-the-fly applicable decision-making algorithm. In contrast to other tree searches like MiniMax or MaxiMax, MCTS is capable of dealing with environments with large action spaces whilst requiring only a simulator of an environment. Due to its popularity and effectiveness, a lot of research effort is dedicated to improving MCTS. One such research area is using abstractions that aim at reducing the MCTS search space by grouping states and actions in the current MCTS search tree to enable an intra-layer information flow [ 9 , 1 , 2 ] . Non-exact abstractions, however, introduce an approximation error making convergence to the optimal action in the abstract space impossible. Recently, Xu et al. [ 17 ] proposed a new paradigm for MCTS-based abstraction algorithms, which is to drop/abandon the abstraction mid-search to guarantee convergence to the optimal action. Another reason one might want to drop an abstraction is when it has no impact on the performance but its usage and calculation only hampers the runtime. In this paper, we further investigate this technique and propose two novel dropping abstraction methods as well as provide a concrete theoretical setting in which dropping schemes provably yield performance increases. The contributions of this paper can be summarized as follows: 1) We generalize On-The-Go abstractions in Upper Confidence Trees (OGA-UCT) [ 2 ] to non-exact abstractions which we call (\varepsilon_{a},\varepsilon_{t}) -OGA. OGA-UCT is a technique that enables ASAP abstractions [ 1 ] to be updated after every MCTS iteration. 2) We propose OGA-IAAD , an OGA-UCT extension that significantly reduces its runtime whilst keeping the same performance. 3) We propose OGA-CAD , an abstraction dropping scheme that operates on a node level basis and dynamically drops an abstraction based on the benefits it provides for estimating a node’s true Q value. 4) We reinvestigate a dropping scheme introduced by Xu et al. [ 17 ] on stochastic Markov Decision Processes (MDP) and show that the improvements found for Strategy games cannot be reproduced in this setting. The paper is structured as follows. Firstly, in Section II we give an overview of other abstraction algorithms and abstraction dropping methods. Then, in Section III we lay the theoretical groundwork for this paper, in particular, we formulate the abstraction framework on which we evaluate dropping methods. In Section IV we describe our experiment setup that applies to all experiments in this paper. The subsequent main body is split into two parts. In the first part in Section V we will introduce and evaluate OGA-IAAD, a dropping method for time-critical applications. In the second part, in Section VI , we consider abstraction-dropping methods aimed at increasing the final performance. In particular, we investigate Xu’s dropping method on stochastic MDPs as well as propose and evaluate a new dropping method named OGA-CAD. At the end, in Section VII we briefly summarise our findings and provide an outlook for future work. II Related Work II-A MCTS-based abstractions Firstly, we will give an overview of MCTS-based abstraction algorithms as these are almost exclusively used in this paper. Jiang et al. [ 9 ] were the first to propose a technique to automatically detect state abstractions in parallel to running a tree search. In regular intervals, they pause MCTS (more concretely UCT [ 10 ] , but we will use UCT and MCTS synonymously) and group states within a layer when each action is pairwise approximately equivalent in the sense that their immediate reward differences as well as their transition probability differences to the node groups of the subsequent layer are below a threshold. To be able to detect any abstractions at all, they optimistically group all partially explored nodes within a layer and use a directed acyclic graph (DAG), allowing different state-action pairs to have the same successors, which is the basis for the abstraction build-up. Though the authors did not name this technique themselves, others refer to it as Abstraction of States UCT (AS-UCT) [ 1 ] . The computed abstraction is only used in the tree policy by improving the UCB value where instead of an action’s true visits and values, one instead inserts the sum of visits and values of all corresponding actions of nodes in the same abstract node. AS-UCT can be improved by using different grouping conditions that allow for the detection of more symmetries, for example, by grouping states if, for each action in a node, there is at least one equivalent action in the other node and vice versa, a condition introduced by Ravindran et al. [ 11 ] . Furthermore, one can abstract nodes and actions independently. Though they are primarily state abstractions, one can also implicitly view AS-UCT as an action abstractions; however, two actions can only ever be abstracted if their parents are in the same abstract node. These ideas are combined in Abstraction of State-Action Pairs in UCT (ASAP-UCT) [ 1 ] , which was also proposed by Anand et al. The successor of ASAP-UCT is called On the Go Abstractions in UCT (OGA-UCT) [ 2 ] which improves the runtime and accuracy of ASAP-UCT by recomputing the abstraction only for frequently visited nodes thus ensuring the information contained in the abstraction does not lag behind the current search tree. The ASAP abstraction framework is exact (i.e., the optimal policy is invariant under ASAP abstractions) and when approximated in MCTS, it introduces almost no abstraction errors (the only source for errors is missing successors of state-action-pairs). This makes it unsuitable for abstraction dropping if one wants to only enhance the performance and not reduce the runtime. This exactness, however, comes with the downside that many correct abstractions are not detected. II-B Abstraction dropping Elastic Monte Carlo Tree Search (EMCTS) was proposed by Xu et al. [ 17 ] , which was the first algorithm to explicitly drop/abandon the abstraction during MCTS. EMCTS first finds and utilises state abstractions in parallel to MCTS using the approximate-homomorphism framework exactly as done by Jiang et al. [ 9 ] with their AS-UCT technique. At some fixed point, however, EMCTS drops the abstraction to continue the search in the original tree. Hostetler et al. [ 8 ] introduced PARSS, another state abstraction algorithm, which uses Forward Search Sparse Sampling (FSSS) [ 16 ] , a Sparse Sampling based tree search. PARSS constructs its abstraction by

Read the complete text