Discovering state equivalences in UCT search trees by action pruning

## Abstract

Abstract 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.

## 1 Introduction

Despite the fact that machine learning (ML) methods are state-of-the-art in many decision-making tasks such as playing Go, or Dota 2 as demonstrated by AlphaGo Silver et al. (2016) and OpenAI Five Berner et al. (2019), they require a resource intensive training phase, an undesired property for some domains.
For example, Game Studios rarely employ ML-based non-player characters because they would have to be costly retrained every time the game and its rules are significantly altered such as in patches or during the development cycle.
Therefore, research into non-learned methods such as MCTS, which is state-of-the-art in some applications like MahJong Tang et al. (2025), still has merit.

One research area to improve MCTS is to enhance the Upper Confidence Bounds (UCB) during the tree policy by first grouping states and state-action pairs with similar values and then using the groups’ aggregate statistics instead of single-node statistics for UCB to ultimately reduce variance.
However, one key weakness of state-of-the-art abstraction algorithms such as On the Go Abstractions in Upper Confidence bounds applied to Trees (OGA-UCT) (Anand et al., 2016) is that they struggle to find meaningful state abstractions given a reasonable computational budget even when the environment has a moderate action space size and stochastic branching factor as will be later illustrated in Section [3](https://arxiv.org/html/2510.26346v1#S3). Hence, they are essentially action abstractions for 1-step Markov Decision Processes (MDP) (Sutton & Barto, 2018) that are applied layerwise.

In this paper, we tackle exactly this problem by proposing a novel algorithm that directly aims at finding correct state abstractions that are not detected by Abstraction of State-Action Pairs in UCT (ASAP-UCT) (Anand et al., 2015) or OGA-UCT to enable the detection of more Q node abstractions to ultimately boost the performance.
The contributions of this paper can be summarized as follows:

1. Based on a theoretical justification and an empirical analysis we demonstrate the serious drawback of current SOTA approaches of finding sufficient state abstractions.

2. We propose Ideal Pruning Abstractions in UCT (IPA-UCT), an OGA-UCT modification that detects more state abstractions, improves the MCTS performance by increasing the sample efficiency as more state abstractions lead to more action abstractions, which improve the sample efficiency. This modification only has a minor runtime overhead (see Tab. [2](https://arxiv.org/html/2510.26346v1#A1.T2)).

3. We formulate two new abstraction frameworks, namely, p(runed)-ASAP and Ideal Pruning Abstractions (IPA) abstractions. Fig. [1](https://arxiv.org/html/2510.26346v1#S1.F1) visualizes their hierarchy. In particular, both IPA and ASAP are special cases of p-ASAP and ASASAP (Schmöcker et al., 2025b). Though p-ASAP already encompasses both IPA and ASAP, we believe that it further helps understand the core principles behind these abstractions and would help categorize future abstractions.

Figure: Figure 1: The hierarchy of abstraction frameworks proposed by us that related Ideal Pruning Abstractions (IPA), Abstraction of State-Action Pairs (ASAP), p(runed)-ASAP, and Alternating State And State-Action Pair Abstractions (ASASAP). The leftmost diagram shows an IPA abstraction on an MDP with 5 states, which are black circles that are connected by deterministic actions that are illustrated with black arrows. The red circles show which actions and states IPA groups/abstracts. The same MDP is shown on the right, but with ASAP abstractions that do not manage to detect the equivalence of the two uppermost states.
Refer to caption: images/teaser_ipa.png

The paper is structured as follows. Firstly, in Section [2](https://arxiv.org/html/2510.26346v1#S2), the theoretical groundwork for this paper is laid. Next, in Section [3](https://arxiv.org/html/2510.26346v1#S3), it is first illustrated why OGA-UCT and ASAP-UCT struggle to find state abstractions, after which in Subsection [3](https://arxiv.org/html/2510.26346v1#S3) we propose our IPA framework and show how to modify OGA-UCT to approximate IPA abstractions in Subsection [2](https://arxiv.org/html/2510.26346v1#S3.F2). We call this modification IPA-UCT. After having described our methodology,
the experiment setup is described in Section [4](https://arxiv.org/html/2510.26346v1#S4). The experimental results and presented and discussed in Section [5](https://arxiv.org/html/2510.26346v1#S5) where evaluate and analyze IPA-UCT on various domains to verify its capability to boost performance. At the end, in Section [6](https://arxiv.org/html/2510.26346v1#S6) we briefly summarise our findings and provide an outlook for future work.

## 2 Foundations of automatic abstractions

Problem model and optimization objective:
To model sequential decision-making tasks, we use
finite MDPs (Sutton & Barto, 2018). In the following, $\Delta(X)\subseteq\mathbb{R}^{|X|}$ denotes the probability simplex of a finite, non-empty set $X$ and $\mathcal{P}(X)$ denotes the power set of $X$.

Definition:
An MDP is a 6-tuple $(S,\mu_{0},\mathbb{A},\mathbb{P},R,T)$ where the components are as follows:

- •
$S\neq\emptyset$ is the finite set of states, $T\subseteq S$ is the (possibly empty) set of terminal states, and $\mu_{0}\in\Delta(S)$ is the probability distribution for the initial state.
- •
$\mathbb{A}\colon S\mapsto A$ maps each state $s$ to the available actions $\emptyset\neq\mathbb{A}(s)\subseteq A$ at state $s$ where $|A|<\infty$.
- •
$\mathbb{P}\colon S\times A\mapsto\Delta(S)$ is the stochastic transition function where we use $\mathbb{P}(s^{\prime}|\>s,a)$ to denote the probability of transitioning from $s\in S$ to $s^{\prime}\in S$ after taking action $a\in\mathbb{A}(s)$ in $s$.
- •
$R\colon S\times A\mapsto\mathbb{R}$ is the reward function.

For the remainder of this section, let $M=(S,\mu_{0},\mathbb{A},\mathbb{P},R,T)$ be an MDP and
$P\coloneqq\{(s,a)\>|\>s\in S,a\in\mathbb{A}(s)\}$
be the set of all state-action pairs. The optimization objective is to find an agent $\pi$ (formally, a mapping $\pi\colon S\mapsto\Delta(A)$)
such that $\pi$ maximizes the expected episode’s return where the (discounted) return for of episode $s_{0},a_{0},r_{0},\dots,s_{n},a_{n},r_{n},s_{n+1}$ with $s_{n+1}\in T$ is given by $\gamma^{0}r_{0}+\ldots+\gamma^{n}r_{n}$.

Abstraction frameworks:
First, the main abstraction framework that IPA will build upon is defined. Anand et al. (2015) introduced the so-called Abstractions of State-Action Pairs (ASAP) framework which provides a method to detect value equivalent states and state-action pairs in an MDP.
An example of an ASAP abstraction on a small state graph can be seen in Fig. [1](https://arxiv.org/html/2510.26346v1#S1.F1). The core idea of ASAP is to alternatingly construct a state abstraction (which is simply an equivalence relation over the state space) given a state-action pair abstraction and vice versa.

ASAP: From state-action pair abstraction to state abstraction:
Let $\mathcal{H}^{\prime}_{\text{ASAP}}\subseteq P\times P$ be a state-action pair abstraction, i.e. an equivalence relation over $P$. The corresponding ASAP state abstraction $\mathcal{E}\subseteq S\times S$ is then given by the following:

$$ $\displaystyle(s_{1},s_{2})\in\mathcal{E}_{\text{ASAP}}\iff$ (1) $\displaystyle\forall a_{1}\in\mathbb{A}(s_{1})\,\exists a_{2}\in\mathbb{A}(s_{2}):((s_{1},a_{1}),(s_{2},a_{2}))\in\mathcal{H}^{\prime}_{\text{ASAP}}$ $\displaystyle\forall a_{2}\in\mathbb{A}(s_{2})\,\exists a_{1}\in\mathbb{A}(s_{1}):((s_{1},a_{1}),(s_{2},a_{2}))\in\mathcal{H}^{\prime}_{\text{ASAP}}.$ $$

In contrast the predecessors of ASAP, like the work by Jiang et al. (2014), two states can be abstracted even if their sets of legal actions differ. However, there is still room to relax this state condition, for example, by having requiring only a subset of the legal action space to have a match. This is the key idea behind IPA which we will be described in Section [3](https://arxiv.org/html/2510.26346v1#S3).

ASAP: From state abstraction to state-action pair abstraction
The second component of ASAP defines how one obtains a state-action pair abstraction $\mathcal{H}_{\text{ASAP}}$ given a state abstraction $\mathcal{E}^{\prime}_{\text{ASAP}}$. Concretely,
any state-action-pair $(s_{1},a_{1}),(s_{2},a_{2})\in P$ is equivalent i.e. $((s_{1},a_{1}),(s_{2},a_{2}))\in\mathcal{H}_{\text{ASAP}}$ if and only if the state-action pairs have identical immediate rewards and transition distributions:

$$ $\displaystyle\quad|R(s_{1},a_{1})-R(s_{2},a_{2})|$ $\displaystyle\leq\varepsilon_{\text{a}}$ (2) $\displaystyle\quad\textrm{and }F\coloneqq\sum\limits_{x\in\mathcal{X}}\bigg|\sum\limits_{s^{\prime}\in x}\mathbb{P}(s^{\prime}|\>s_{1},a_{1})-\mathbb{P}(s^{\prime}|\>s_{2},a_{2})\bigg|$ $\displaystyle\leq\varepsilon_{\text{t}},$ $$

where $\mathcal{X}$ are the equivalence classes of $\mathcal{E}^{\prime}_{\text{ASAP}}$ and $\varepsilon_{\text{t}}=\varepsilon_{\text{a}}=0$.

If one starts with the state abstraction that groups all terminal nodes and repeats these two construction steps until convergence, the final thus-obtained abstraction is called the ASAP abstraction of the given MDP. ASAP abstractions are a special case of ASASAP abstractions (Schmöcker et al., 2025b) which formalize the working principle of repeatedly constructing a state abstraction from a state-action pair abstraction and vice versa.

Building and using abstractions to enhance search:
Since, the state and state-action pair spaces can be arbitrarily large, constructing an ASAP on the MDP $M$ is mostly infeasible.
Therefore, ASAP-based abstraction algorithm such as
ASAP-UCT (Anand et al., 2015), OGA-UCT (Anand et al., 2016), and IPA-UCT (see Section [2](https://arxiv.org/html/2510.26346v1#S3.F2)) construct their abstraction
on the local-layered MDP rooted at the state $s_{\text{d}}$ where the decision has to be made. The local-layered MDP is given as the current MCTS search graph (the MCTS version used here is specified in Section [A.11](https://arxiv.org/html/2510.26346v1#A1.SS11)).
In this simplified setting, one can use dynamic programming to compute the ASAP abstraction since one only needs to have access to the abstraction at layer/depth $i+1$ of the search graph to compute those at depth $i$.
While ASAP-UCT pauses MCTS in regular intervals to construct the ASAP abstraction, the current state of the art that follows this working principle, is OGA-UCT Anand et al. (2016) which keeps a recency counter for each state-action pair and once its passed, updates tests if its abstraction changes, and if so propagates that change to its parent which might in turn also update their abstraction. This allows one to continuously have access to an up-to-date ASAP abstraction without an enormous runtime overhead.

OGA-UCT for multi-agent settings: In the experiments, we will also evaluate OGA-based algorithms on board games, which are not MDPs as they feature two players. The only modification needed for OGA is to optimize and keep track of the Q values for the player at the turn at the corresponding node.

OGA-UCT extensions to high stochasticity settings: In practice, OGA-UCT is slightly modified to better handle high stochasticity. Two modifications exist with which IPA-UCT will be tested.
Firstly, pruned OGA is identical to OGA-UCT except that
when building the state-action pair abstractions certain successors are ignored. Concretely, for a state-action pair with $n$ successors with respective probabilities $p_{1},\dots,p_{n}$ those with $p_{i}<\alpha\cdot\max\{p_{1},\dots,p_{n}\},\ \alpha\in[0,1]$ are ignored.
Furthermore, there is $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA (Schmöcker et al., 2025d) which allows $\varepsilon_{\text{a}},\varepsilon_{\text{t}}$ values greater than zero. Schmöcker et al. (2025d) describes the implementation details as larger than zero values do not necessarily induce an equivalence relation, i.e. a non-overlapping partition.

RSTATE-OGA: Later, when the different OGA variants are experimentally investigated, one ablation that will also be conducted is to test the performance of random state abstractions to ensure that any performance gains due to the usage of abstractions are better than if random abstractions were used. OGA-UCT that uses random state abstractions is called RSTATE-OGA and functions as follows. Whenever a state node $\mathcal{S}$ is visited for the $K$-th time and its current abstract node consists only of itself, then with the probability $p_{\text{abs}}\in[0,1]$, $\mathcal{S}$’s abstract node is changed with uniform probability to any of the abstract nodes of the same depth. Initially, at creation, any Q node is its own abstract node.

Abstraction usage: A state-action pair abstraction can also be viewed as a partition over $P$. During the tree policy, instead of using the statistics (i.e. cumulative returns and visits) of a single node, the aggregate statistics of the node’s group are used to ultimately reduce variance. This is the key abstraction usage mechanism that all methods that are considered in this paper use, e.g. AS-UCT (Jiang et al., 2014) (predecessor of ASAP-UCT), ASAP-UCT, OGA-UCT, $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA, pruned OGA, and IPA-UCT.

Other automatic abstraction algorithms:
The literature on abstraction algorithms includes abstractions for Sparse Sampling trees (Hostetler et al., 2015), abstractions of the transition function, (Sokota et al., 2021; Yoon et al., 2008; 2007; Saisubramanian et al., 2017), purely statistical-based abstractions (Schmöcker et al., 2025a) which do not require an equality check operator like OGA, or abstractions that deliberately group states or state-action pairs with differing $V^{*}$ or $Q^{*}$ values (Schmöcker et al., 2025c). Another area of research is the abstraction usage, which might involve dynamically abandoning the abstraction (Xu et al., 2023; Schmöcker et al., 2025d) or defining an intra-abstraction policy Schmöcker et al. (2025b).
Abstractions have also been investigated for other problem settings, such as continuous and/or partially observable problems (Hoerger et al., 2024), learning-based methods, such as learning and planning on abstract models (Ozair et al., 2021; Kwak et al., 2024; Chitnis et al., 2020).
An in-depth overview of the non-learning-based abstraction literature has been created by Schmöcker & Dockhorn (2025).

## 3 Method

In this Section, we will be introducing our novel IPA-UCT algorithm by first showing that ASAP struggles with finding state abstractions. Then we will be introducing a new abstraction framework called IPA, which IPA-UCT tries to approximate. Lastly, we illustrate on a concrete example how the IPA framework detects state equivalences that ASAP does not.

Why ASAP finds (nearly) no state abstractions:
In the following, we will first give theoretical arguments why ASAP finds few state abstractions, only after which we show experimental evidence to support these claims.

Theory: Let us consider a simplified model where two states $s_{1},s_{2}$ with $n$ and $l$ actions respectively are given. Furthermore, assume that each of $s_{1}$’s and $s_{2}$’s actions are assigned to an abstract Q node from a pool of $m$ abstract Q nodes with uniform probability. Using elementary combinatorial arguments, the probability $p_{\text{abs}}$ of $s_{1}$ and $s_{2}$ being abstracted according to the ASAP framework can be exactly denoted and then upper bounded by

$$ $p_{\text{abs}}=\frac{\sum\limits_{k=1}^{c\coloneqq\min\{n,l,m\}}\binom{m}{k}f(n,k)f(l,k)}{m^{n+l}}\leq\left(\frac{2c}{m}\right)^{n+l}$ (3) $$

where $f(n,k)$ is the number of surjections from a set of $n$ elements to a set of $k\leq n$ elements (proof is provided in the supplementary materials Section [A.6](https://arxiv.org/html/2510.26346v1#A1.SS6)). This shows that once there is a critical amount of possible abstractions $m$, then the probability decays at least exponentially in the number of actions $n$ and $l$. The method IPA that we propose won’t depend on $m$.

Empirical results: Aside from these theoretical arguments, we empirically measured the abstraction rate for OGA-UCT. The measurements can be seen in the supplementary materials in Tab.[3](https://arxiv.org/html/2510.26346v1#A1.T3) in the OGA column with $\varepsilon_{\text{a}}=\varepsilon_{\text{t}}=0$. Clearly, with a few exceptions, nearly no state abstractions are built despite the fact that at least value-equivalent states have to exist in some environments due to symmetry reasons such as Game of Life and SysAdmin. There are two notable exceptions, namely Crossing Traffic and Skills Teaching where standard OGA detects a notable number of state abstractions. However, these are arguably trivial: In Skills Teaching, to simulate the student’s learning process, every other turn has only a single action, hence these state abstractions are essentially action abstractions. In Crossing Traffic, once the agent has been hit by an obstacle, the game reaches a non-terminal states in which all the agent’s actions have no effect. These trivial dead states are detected.

The p-ASAP and IPA abstraction frameworks:
First, we introduce an abstraction framework that we call p(runed)-ASAP of which ASAP is a special case. Given a state-action-pair abstraction $\mathcal{H}$, some action pruning function $J\colon S\mapsto\mathcal{P}(A)$ such that $J(s)\subseteq\mathbb{A}(s)$ for all $s$, we can define a symmetric and reflexive (but not necessarily transitive) relation $\sim_{J}$ with $s_{1}\sim_{J}s_{2}$ if and only if

$$ $\displaystyle\forall a_{1}\in J(s_{1})\ \exists a_{2}\in\mathbb{A}(s_{2}):\quad$ $\displaystyle((s_{1},a_{1}),(s_{2},a_{2}))\in\mathcal{H},$ (4) $\displaystyle\forall a_{2}\in J(s_{2})\ \exists a_{1}\in\mathbb{A}(s_{1}):\quad$ $\displaystyle((s_{1},a_{1}),(s_{2},a_{2}))\in\mathcal{H}.$ (5) $$

If $\sim_{J}$ is an equivalence relation, then we call the abstraction using $f(\mathcal{H})=\sim_{J}$ a p-ASAP abstraction.

ASAP is obtained from p-ASAP by using $J_{\text{ASAP}}(s)=\mathbb{A}(s)$ for all $s$. As illustrated in Section [3](https://arxiv.org/html/2510.26346v1#S3), the ASAP framework is practically unable to detect any state abstractions, hence, the goal is to find a $J$ that does as much pruning as possible whilst keeping value-invariance of the resulting abstraction. This is already guaranteed by ASAP because when all actions have an equivalent match, then it is also the case for the optimal action which determines the $V^{*}$ value.

If one chooses $J^{*}(s)$ to be the set of optimal actions (i.e., those with the maximal $Q^{*}$ value), then the maximal number of action pruning is performed whilst ensuring value equivalence of any two abstracted states. Note that $\sim_{J^{*}}$ is an equivalence relation. We refer to the $p$-ASAP abstraction using $J^{*}$ as Ideal-Pruning-Abstractions (IPA) as only those states are grouped that have the same value under optimal play. However, this framework still does not capture all value equivalent states, as two states may be value equivalent but have no ASAP-equivalent actions.

IPA versus ASAP on Navigation:
In this section, we will demonstrate a motivating example in which the ASAP framework is unable to detect some state abstractions that are encompassed by the IPA framework.
Consider the Navigation instance that is illustrated in Fig. [2](https://arxiv.org/html/2510.26346v1#S3.F2) and whose definition is given in the supplementary materials [A.12](https://arxiv.org/html/2510.26346v1#A1.SS12). Counterintuitively, the optimal policy is to continuously attempt the straight path $3\to 8\to 13\to 18$ which yields an average return of $-3$. Going around cell $8$, either left or right, has a lower average return of $-5$. To decrease the chance of MCTS to take one of these suboptimal paths, it would be of benefit if states 2 and 4 are abstracted as that would imply the actions $3\to 2$ and $3\to 4$ could be abstracted too, thus allowing MCTS to average their Q values and therefore decrease this suboptimal-path probability.

However, according to the ASAP framework, states 12 and 14 cannot be abstracted, since the action 14 $\to$ 15, does not have an ASAP-equivalent action in state 12 (this can be checked using that ASAP-equivalent actions must also be value-equivalent). Consequently, states 7,9 and ultimately 2,4 won’t be abstracted. On the contrary, the IPA framework does find all of these abstractions, as going from 12 to 13 or from 14 to 13 are the unique optimal actions which are abstracted since they result in the same ground state.

Figure: Figure 2: A 5$\times$4 Navigation instance to illustrate an example where the IPA framework (our method) detects the value equivalencies of states 2,4 and 7,9 and 12,14 which cannot be done with ASAP. The circle indicates the initial position, G indicates the goal cell, white cells have a reset probability of 0, and black cells have a reset probability of $0.5$.

IPA-UCT:
Next, we will discuss how the IPA abstraction framework can be integrated with OGA-based methods, which we then call IPA-UCT. The full pseudocode for this modification is provided in the supplementary materials in Pseudocode [1](https://arxiv.org/html/2510.26346v1#alg1), which highlights the differences to $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA in blue.
IPA-UCT will only modify the state abstraction component of OGA; hence, we regard either using the mechanism of pruned OGA or $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA for the state-action pair abstraction simply as a parametrization of IPA-UCT. We proceed as follows. Firstly, we will introduce an approximation for $J^{*}$. Since this approximation $J_{\text{UCB}}$ does not induce an equivalence relation, we will show how we can transform it into one such that it can be incorporated into OGA in the supplementary materials in Section [A.10](https://arxiv.org/html/2510.26346v1#A1.SS10). Our idea is to approximate $J^{*}(s)$ using current search tree information. The approximation $J_{\text{UCB}}$ for $J^{*}$ for a state $s$ is

$$ $J_{\text{UCB}}(s)=\{a\in\mathbb{A}(s)\>|\>\text{UCB}(a)\geq Q_{\text{max}}\}$ (6) $$

where $Q_{\text{max}}=\max\limits_{a\in\mathbb{A}(s)}Q(s,a)$ is the maximum Q value statistic at node $s$ and UCB$(a)$ denotes the current UCB value of action $a$ in state $s$. The idea is that, mostly, one cannot tell what the optimal action is; however, given enough visits, one can oftentimes exclude some actions which are almost certainly not optimal. We parametrize this technique by some $\lambda_{\text{p}}\in\mathbb{R}\cup\{\mathbb{\infty}\}$ which is used as the exploration constant for the UCB values that are used for this pruning procedure.
If one chooses $\lambda_{\text{p}}=0$, then only those actions are kept that have the current maximum Q value. If one selects $\lambda_{\text{p}}=\infty$, then no pruning takes place, hence $J_{\text{UCB}}=J_{\text{ASAP}}$. Hence, $\lambda_{\text{p}}$ controls the riskiness when building the state abstractions. As will be later shown, the best performances are reached with non-trivial $\lambda_{\text{p}}$ values that have an optimal tradeoff between finding additional correct state abstractions that are built at the cost of faulty new ones.
Since the state abstractions now do no longer exclusively depend on the abstractions of the Q nodes, we introduce a recency counter for state nodes as well. The recency count’s threshold is set for simplicity to the same value that is used for the Q nodes. As with the Q nodes, whenever that recency counter reaches the threshold, we update the state abstraction along with the current value for $J_{\text{UCB}}$.

Though heuristical in nature, IPA-UCT has the same soundness guarantee as OGA-UCT as specified in the following theorem, which is proven in the supplementary materials in Section [A.1](https://arxiv.org/html/2510.26346v1#A1.SS1).

Soundness theorem: The abstraction on IPA-UCT’s search tree will become sound (i.e. group only states with the same $V^{*}$ value and state-action pairs with the same $Q^{*}$ value) almost surely in the iteration limit when using OGA-UCT as the state-action pair abstraction mechanism.

## 4 Experiment setup

In this section, we describe the general experiment setup. Any deviations from this setup will be explicitly mentioned.

Parameters:
Originally, OGA (Anand et al., 2016) used the absolute value of the abstract Q value as the exploration constant. However, this technique has been improved by the dynamic, scale-independent exploration factor Global-Std (Schmöcker et al., 2025e). The Global-Std exploration constant
has the form $C\cdot\sigma$ where $\sigma$ is the standard deviation of the Q values of all nodes in the search tree and $C\in\mathbb{R}^{+}$ is some fixed parameter. Furthermore, we always use $K=3$ as the recency counter, which was proposed by Anand et al. (Anand et al., 2016).

Problem models:
For this paper, we ran our experiments on a variety of MDPs, all of which are either from the International Probabilistic Planning Conference (Grzes et al., 2014), are well-known board games, or are commonly used in the abstraction algorithm literature (Anand et al., 2015; 2016; Hostetler et al., 2015; Yoon et al., 2008; Jiang et al., 2014).
All experiments were run on the finite-horizon versions of the considered MDPs with a default horizon of 50 steps and 100 for the board games with a planning horizon of 50 and a discount factor $\gamma=1$. The board games are zero-sum evaluated by inserting standard MCTS with 500 iterations as the opponent.
If the reader is not familiar with any of the domains that were used for the experiments, a brief description for each MDP is provided in the supplementary materials in Section [A.12](https://arxiv.org/html/2510.26346v1#A1.SS12).

Evaluation:
Each data point that we denote in the remaining sections of this paper (e.g. agent returns) is the average of at least 2000 runs. Whenever we denote a confidence interval for a data point, then this is always a confidence interval with a confidence level of 99% provided by $\approx 2.33$ times the standard error. Furthermore, we use a borda-like ranking system to quantify agents’ performances; in particular, we use pairings and relative improvement scores. For details, see supplementary Section [A.4](https://arxiv.org/html/2510.26346v1#A1.SS4).

Reproducibility:
For reproducibility, we released our implementation (Schmöcker, 2025). Our code was compiled with g++ version 13.1.0 using the -O3 flag (i.e. aggressive optimization).

## 5 Experiments

First, we compare the overall performances of IPA-UCT, pruned OGA, and $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA, and RSTATE-OGA (to ensure any performance gains come from non-trivial sources) by computing their pairings and relative improvement for different iteration budgets obtained from the performance values of all $>20$ considered environments. The parameters we varied are the following: For all methods, we used $C\in\{0.5,1,2,4,8,16\}$
For $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA, we tested $\varepsilon_{\text{a}}\in\{0,\infty\}$, $\varepsilon_{\text{t}}\in\{0,0.2,0.4,0.8\}$, for pruned OGA we used $\alpha\in\{0,0.1,0.2,0.5,0.75,1.0\}$, and for RSTATE-OGA we used $p_{\text{abs}}\in\{0.1,0.2,0.5,1.0\}$. We varied the pruning constant $\lambda_{\text{p}}\in\{0,0.25,0.5,1,2,4,\infty\}$ where $\lambda_{\text{p}}=\infty$ corresponds to doing no pruning at all i.e. defaulting to standard pruned OGA or $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA.
Each parameter combination was run with 100, 200, 500, and 1000 iterations.

Bar charts  [4](https://arxiv.org/html/2510.26346v1#S5.F4) compare the pairings and relative improvement scores for the best parameter-combinations for each iteration budget. This shows that using IPA-UCT clearly has better generalization capabilities than not using the modified state abstraction that IPA-UCT introduces, with a sweet spot in performance being the 500 iterations setting where an average 5% performance increase over the best OGA parameter combination can be found. Except for the relative improvement score in the 1000 iterations setting, IPA-UCT attained higher scores in all iteration budgets than standard OGA-based methods.
IPA-UCT can however, only gain a clear advantage over OGA-based techniques in this generalization setting as the per-environment parameter-optimized yield only minor (if any) improvements except for Cooperative Recon, which we visualized and discuss in the supplementary materials Section [A.2](https://arxiv.org/html/2510.26346v1#A1.SS2). Nonetheless, these results show that IPA-UCT can be a valuable drop-in improvement for OGA-based algorithms, offering a clear advantage when one cannot afford to fine-tune parameters per task. In the next section, we discuss how $\lambda_{\text{p}}$ can be chosen.

Figure: Figure 3: The pairings scores of the best IPA-UCT parameter combination compared to the best parameter combination of RSTATE-OGA, and both pruned OGA and $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA (summarized as OGA). The overall generalization performance of IPA-UCT for all iteration settings was achieved using pruned OGA with $\lambda_{\text{p}}=2$, $C=2$, and $\alpha=0.75$.
Refer to caption: images/ipa_results/pairings.png

Ablation: Performance as a function of $\bm{\lambda_{\text{p}}}$:
Next, we investigate the relative performance between the $\lambda_{\text{p}}$ values. Fig. [5](https://arxiv.org/html/2510.26346v1#S5.F5) shows the performance curve when varying $\lambda_{\text{p}}$ for the here-considered iteration budgets in terms of the pairings and relative improvement score for all environments (the performance graphs for each individual environment can be found in the supplementary materials in Fig. [7](https://arxiv.org/html/2510.26346v1#A1.F7). The following observations can be made:

1) First and foremost, all curves feature a clear downwards trend as $\lambda_{\text{p}}$ approaches the largest here-considered value $4$. All curves have a peak at less than $4$. This further validates the positive impact that the UCB-based pruning has on the performance, as the higher the $\lambda_{\text{p}}$ value, the closer IPA-UCT is to standard OGA.

2) For both scores, the curves for 500 and 1000 iterations have a single peak, which is either $\lambda_{\text{p}}=0.5$ or $\lambda_{\text{p}}=1$, depending on the score type.

3) Surprisingly, even for small iteration counts of 100 or 200 iterations, there are still clear peaks which are at either $\lambda_{\text{p}}=0$ or $\lambda_{\text{p}}=0.25$ (except for the 200 iterations pairings score). This makes sense as in lower iteration budgets, IPA-UCT needs to be more risk-taking in the abstraction building as there aren’t enough visits to have confidence in the pruning, hence the $\lambda_{\text{p}}$ peaks are at lower values than for the higher iteration budgets.

Figure: Pairings scores
Refer to caption: images/ipa_results/filter_pairings.png

Alternative pruning methods:
Though we found most success with the proposed $J_{\text{UCB}}$ function of pruning actions that relies on the UCB and Q values only, we also conducted preliminary experiments on two different approaches that are described in the following, and whose performances are shown in Tab. [5](https://arxiv.org/html/2510.26346v1#A1.T5). However, both approaches performed worse than $J_{\text{UCB}}$, whose downsides we will briefly cover, and why we ultimately presented IPA-UCT instead of these.

Confidence-based pruning: For this method, we kept track of a confidence interval with confidence level $p_{\text{c}}\in[0,1]$ for each Q value. We then used $J_{\text{conf}}$ which prunes all actions at a state $s$ whose upper confidence bound are lower than the highest lower bound.
We call this method CONF-UCT.
In our observation, the Q values were much too noisy to perform any meaningful pruning.

Hard pruning: For this method $J_{\text{top}}$, one only keeps the best $n_{\text{matches}}$ actions when ordered by their current Q value. To avoid the risk of faulty prunings, $J_{\text{top}}=J_{\text{ASAP}}$ if the node has less than $n_{\text{min}}$ visits. This method, which we name TOPN-UCT, performed nearly on PAR with $J_{\text{UCB}}$, however, it has two parameters to configure rather than just one.

## 6 Conclusion and Future Work

In this paper, we first defined the IPA abstraction framework and generalized best IPA and ASAP
by introducing p-ASAP which itself is a special case of ASASAP abstractions (Schmöcker et al., 2025b). Next, we showed both empirically and theoretically that OGA-UCT effectively finds no state abstractions. We proposed IPA-UCT to alleviate this issue and showed that IPA-UCT yields a consistent performance improvement over OGA-based methods.

One limitation of IPA-UCT is that there is no single $\lambda_{\text{p}}$ value that performs well for all environment. One avenue for future work is to automatically detect the correct value for $\lambda_{\text{p}}$. While for some environments $\lambda_{\text{p}}=0$ is best, this can be harmful to others. Furthermore, some environments prefer neither $\lambda_{\text{p}}=\infty$ (i.e. no pruning) nor $\lambda_{\text{p}}=0$ but rather some value in between.
Also, IPA-UCT is clearly not optimal in that still many state abstractions, especially those arising due to symmetry (e.g., in Game of Life or SysAdmin), are not detected because as OGA-UCT, IPA-UCT relies on the detection of action abstractions. We believe that this near-exact abstraction that is being built in IPA-UCT and OGA-UCT is not the path forward to resolve this issue, as it requires too many Q nodes to have sampled nearly all their possible outcomes which is mostly infeasible when the stochasticity has more than binary outcomes. A new automatic abstraction paradigm is required.
Lastly, since IPA-UCT is a modification of OGA-UCT is suffers from the same limitation in that a directed acyclic search graph is required for any abstractions to be detected because if no two state-action-pairs result in the same state, then no action abstraction can be built.

## References

- Anand et al. (2015)
Ankit Anand, Aditya Grover, Mausam, and Parag Singla.
ASAP-UCT: Abstraction of State-Action Pairs in UCT.
In Qiang Yang and Michael J. Wooldridge (eds.), *Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015*, pp. 1509–1515. AAAI Press, 2015.
URL [http://ijcai.org/Abstract/15/216](http://ijcai.org/Abstract/15/216).
- Anand et al. (2016)
Ankit Anand, Ritesh Noothigattu, Mausam, and Parag Singla.
OGA-UCT: on-the-go abstractions in UCT.
In *Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling*, ICAPS’16, pp. 29–37. AAAI Press, 2016.
ISBN 1577357574.
- Berner et al. (2019)
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang.
Dota 2 with Large Scale Deep Reinforcement Learning.
*CoRR*, abs/1912.06680, 2019.
URL [http://arxiv.org/abs/1912.06680](http://arxiv.org/abs/1912.06680).
- Chitnis et al. (2020)
Rohan Chitnis, Tom Silver, Beomjoon Kim, Leslie Pack Kaelbling, and Tomás Lozano-Pérez.
Camps: Learning context-specific abstractions for efficient planning in factored mdps.
In Jens Kober, Fabio Ramos, and Claire J. Tomlin (eds.), *4th Conference on Robot Learning, CoRL 2020, 16-18 November 2020, Virtual Event / Cambridge, MA, USA*, volume 155 of *Proceedings of Machine Learning Research*, pp. 64–79. PMLR, 2020.
URL [https://proceedings.mlr.press/v155/chitnis21a.html](https://proceedings.mlr.press/v155/chitnis21a.html).
- Grzes et al. (2014)
Marek Grzes, Jesse Hoey, and Scott Sanner.
International Probabilistic Planning Competition (IPPC) 2014.
In *Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)*, 2014.
- Hoerger et al. (2024)
Marcus Hoerger, Hanna Kurniawati, Dirk P. Kroese, and Nan Ye.
Adaptive discretization using voronoi trees for continuous pomdps.
*Int. J. Robotics Res.*, 43(9):1283–1298, 2024.
doi: 10.1177/02783649231188984.
URL [https://doi.org/10.1177/02783649231188984](https://doi.org/10.1177/02783649231188984).
- Hostetler et al. (2015)
Jesse Hostetler, Alan Fern, and Thomas G. Dietterich.
Progressive Abstraction Refinement for Sparse Sampling.
In Marina Meila and Tom Heskes (eds.), *Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI 2015, July 12-16, 2015, Amsterdam, The Netherlands*, pp. 365–374. AUAI Press, 2015.
URL [http://auai.org/uai2015/proceedings/papers/81.pdf](http://auai.org/uai2015/proceedings/papers/81.pdf).
- Jiang et al. (2014)
Nan Jiang, Satinder Singh, and Richard L. Lewis.
Improving UCT planning via approximate homomorphisms.
In Ana L. C. Bazzan, Michael N. Huhns, Alessio Lomuscio, and Paul Scerri (eds.), *International conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’14, Paris, France, May 5-9, 2014*, pp. 1289–1296. IFAAMAS/ACM, 2014.
URL [http://dl.acm.org/citation.cfm?id=2617453](http://dl.acm.org/citation.cfm?id=2617453).
- Kwak et al. (2024)
Yunhyeok Kwak, Inwoo Hwang, Dooyoung Kim, Sanghack Lee, and Byoung-Tak Zhang.
Efficient monte carlo tree search via on-the-fly state-conditioned action abstraction.
In Negar Kiyavash and Joris M. Mooij (eds.), *Uncertainty in Artificial Intelligence, 15-19 July 2024, Universitat Pompeu Fabra, Barcelona, Spain*, volume 244 of *Proceedings of Machine Learning Research*, pp. 2076–2093. PMLR, 2024.
URL [https://proceedings.mlr.press/v244/kwak24a.html](https://proceedings.mlr.press/v244/kwak24a.html).
- Ozair et al. (2021)
Sherjil Ozair, Yazhe Li, Ali Razavi, Ioannis Antonoglou, Aäron van den Oord, and Oriol Vinyals.
Vector quantized models for planning.
In Marina Meila and Tong Zhang (eds.), *Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event*, volume 139 of *Proceedings of Machine Learning Research*, pp. 8302–8313. PMLR, 2021.
URL [http://proceedings.mlr.press/v139/ozair21a.html](http://proceedings.mlr.press/v139/ozair21a.html).
- Saisubramanian et al. (2017)
S. Saisubramanian, S. Zilberstein, and P. Shenoy.
Optimizing Electric Vehicle Charging Through Determinization.
In *ICAPS Workshop on Scheduling and Planning Applications*, 2017.
- Schmöcker & Dockhorn (2025)
Robin Schmöcker and Alexander Dockhorn.
A Survey of Non-Learning-Based Abstractions for Sequential Decision-Making.
*IEEE Access*, 13:100808–100830, 2025.
doi: 10.1109/ACCESS.2025.3572830.
URL [https://doi.org/10.1109/ACCESS.2025.3572830](https://doi.org/10.1109/ACCESS.2025.3572830).
- Schmöcker (2025)
Robin Schmöcker.
IdealPruningAbstractions, 2025.
Repository available at: [https://github.com/codebro634/IdealPruningAbstractions.git](https://github.com/codebro634/IdealPruningAbstractions.git).
- Schmöcker et al. (2025a)
Robin Schmöcker, Alexander Dockhorn, and Bodo Rosenhahn.
Aupo - abstracted until proven otherwise: A reward distribution based abstraction algorithm, 2025a.
URL [https://arxiv.org/abs/2510.23214](https://arxiv.org/abs/2510.23214).
- Schmöcker et al. (2025b)
Robin Schmöcker, Alexander Dockhorn, and Bodo Rosenhahn.
Investigating intra-abstraction policies for non-exact abstraction algorithms, 2025b.
URL [https://arxiv.org/abs/2510.24297](https://arxiv.org/abs/2510.24297).
- Schmöcker et al. (2025c)
Robin Schmöcker, Alexander Dockhorn, and Bodo Rosenhahn.
Grouping nodes with known value differences: A lossless uct-based abstraction algorithm, 2025c.
URL [https://arxiv.org/abs/2510.25388](https://arxiv.org/abs/2510.25388).
- Schmöcker et al. (2025d)
Robin Schmöcker, Lennart Kampmann, and Alexander Dockhorn.
Time-critical and confidence-based abstraction dropping methods.
In *2025 IEEE Conference on Games (CoG)*, 2025d.
doi: 10.1109/CoG64752.2025.11114261.
- Schmöcker et al. (2025e)
Robin Schmöcker, Christoph Schnell, and Alexander Dockhorn.
Investigating scale independent uct exploration factor strategies, 2025e.
URL [https://arxiv.org/abs/2510.21275](https://arxiv.org/abs/2510.21275).
- Silver et al. (2016)
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.
Mastering the game of Go with deep neural networks and tree search.
*Nat.*, 529(7587):484–489, 2016.
doi: 10.1038/NATURE16961.
URL [https://doi.org/10.1038/nature16961](https://doi.org/10.1038/nature16961).
- Sokota et al. (2021)
Samuel Sokota, Caleb Ho, Zaheen Farraz Ahmad, and J. Zico Kolter.
Monte Carlo Tree Search With Iteratively Refining State Abstractions.
In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), *Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual*, pp. 18698–18709, 2021.
URL [https://proceedings.neurips.cc/paper/2021/hash/9b0ead00a217ea2c12e06a72eec4923f-Abstract.html](https://proceedings.neurips.cc/paper/2021/hash/9b0ead00a217ea2c12e06a72eec4923f-Abstract.html).
- Sutton & Barto (2018)
Richard S. Sutton and Andrew G. Barto.
*Reinforcement Learning: An Introduction*.
The MIT Press, 2nd edition, 2018.
- Tang et al. (2025)
Shih-Chieh Tang, Jr-Chang Chen, and I-Chen Wu.
Applying Importance Sampling to MCTS for Mahjong.
*IEEE Transactions on Games*, pp. 1–10, 2025.
doi: 10.1109/TG.2025.3535740.
- Xu et al. (2023)
Linjie Xu, Alexander Dockhorn, and Diego Perez-Liebana.
Elastic Monte Carlo Tree Search.
*IEEE Transactions on Games*, 15(4):527–537, 2023.
doi: 10.1109/TG.2023.3282351.
- Yoon et al. (2007)
Sung Wook Yoon, Alan Fern, and Robert Givan.
FF-Replan: A Baseline for Probabilistic Planning.
In Mark S. Boddy, Maria Fox, and Sylvie Thiébaux (eds.), *Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS 2007, Providence, Rhode Island, USA, September 22-26, 2007*, pp. 352. AAAI, 2007.
URL [http://www.aaai.org/Library/ICAPS/2007/icaps07-045.php](http://www.aaai.org/Library/ICAPS/2007/icaps07-045.php).
- Yoon et al. (2008)
Sung Wook Yoon, Alan Fern, Robert Givan, and Subbarao Kambhampati.
Probabilistic Planning via Determinization in Hindsight.
In Dieter Fox and Carla P. Gomes (eds.), *Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13-17, 2008*, pp. 1010–1016. AAAI Press, 2008.
URL [http://www.aaai.org/Library/AAAI/2008/aaai08-160.php](http://www.aaai.org/Library/AAAI/2008/aaai08-160.php).

## Appendix A Supplementary Materials

### A.1 Proof of soundness theorem

In IPA-UCT using standard OGA-UCT, every state-action pair of the MDP will be expanded, and its visits converge in probability to $\infty$ due to UCB’s exploration term. Hence, in the limit, every state-action pair successor will have also been sampled almost surely. Next, assuming that this is the case, one shows inductively, starting from the bottom layer, that the built abstraction will become sound almost surely.

Induction start: The fully expanded search tree’s bottom layer contains only terminal states, which are grouped by default. This abstraction is sound as terminal states have a $Q^{*}$ value of 0.

Induction step: Assume that the state abstraction at layer $L+1$ becomes sound almost surely. Consequently, the state-action pairs’ Q-values in layer $L$ will converge in probability to their $Q^{*}$ values as UCB is used as the tree-policy. Also, independent of the state-action pair’s Q-values, their abstractions almost surely become sound as they are built with the standard ASAP rules. The $V^{*}$ value of any state is defined as the maximum $Q^{*}$ value of its actions. Since the Q-values of the state-action pairs in layer $L$ converge in probability to their $Q^{*}$ values, the Q value of any optimal action $a^{*}$ for any state $s$ at layer $L$ and therefore its UCB value will almost surely be greater than the Q value of any suboptimal action of $s$. Therefore, all the optimal actions of $s$ will almost surely never be pruned simultaneously. Hence, the state abstraction at layer $L$ will also almost surely become sound. ∎

### A.2 Parameter-optimized performances

Fig. [6](https://arxiv.org/html/2510.26346v1#A1.F6) compares the parameter-optimized performances of IPA-UCT, pruned OGA and $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA (summarized simply as OGA) as well as RSTATE-OGA using the same parameters as in the main experimental section [5](https://arxiv.org/html/2510.26346v1#S5).

The key observation that can be made is that IPA-UCT has only limited use in improving the parameter-optimized, as the gains (if any) are only marginal and could be explained due to noise, except for the Cooperative Recon environment where IPA-UCT can a clear advantage. In Manufacturer, Racetrack, Sailing Wind, Tamarisk, Connect 4, Pylos, and Othello, there seems to be a significant, however extremely small gain.

Though IPA-UCT will show more promise in the generalization experiments presented in the main section, the reasons for the negligible impact of IPA in this setting will be discussed, which can be attributed to three criteria that have to be satisfied for IPA-UCT to have a significant impact, which altogether can be quite rare.

- 1.
The domain must have a small action space. For $J_{\text{UCB}}$ to prune an action, it must have a low enough exploration term, which shrinks only with the number of visits. If there are too many actions, the visits will be spread too much. This explains the lack of impact in Academic Advising, Game of Life, or SysAdmin. Of course, using $\lambda_{\text{p}}=0$ does pruning even with no visits; however, we consider performance gains by pruning under such uncertainty as simply lucky.
- 2.
Ultimately, IPA (as well as ASAP) requires state-action pair abstractions to bootstrap off of. Hence, if almost no action abstractions are found, then IPA cannot detect any state abstractions. Due to its extremely high stochasticity, this is the case for Earth Observation where with reasonable $\varepsilon_{\text{t}}$ values, no action abstractions are found.
- 3.
There must be state equivalences in the first place. Some environments like Sailing Wind or the here-considered Navigation instance feature almost no state-equivalences (for reference, check their corresponding abstraction rate Tab. [4](https://arxiv.org/html/2510.26346v1#A1.T4))

Figure: (a) Academic Advising
Refer to caption: images/ipa_results/ipa_aa.png

Figure: (p) Chess
Refer to caption: images/ipa_results/ipa_che.png

**Table 1: A list of the environment-specific $\varepsilon_{\text{a}}$ values that were used for the parameter-optimized experiments that used $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA. All single-agent domains that are not explicitly listed here use the default values $\varepsilon_{\text{a}}\in\{0,1,2,\infty\}$ and all two-player domains use the values $\varepsilon_{\text{a}}\in\{0,\infty\}$. The values were chosen to be equal to rewards (except 0 and $\infty$) that occur in these environments, to avoid the effect of different $\varepsilon_{\text{a}}$ inducing identical behavior.**
| Environment | $\varepsilon_{\text{a}}$ values |
| --- | --- |
| Academic Advising | 0, $\infty$ |
| Cooperative Recon | 0, 0.5, 1.0, $\infty$ |
| Crossing Traffic | 0, $\infty$ |
| Manufacturer | 0, 10, 20, $\infty$ |
| Skill Teaching | 0, 2, 3, $\infty$ |
| Tamarisk | 0, 0.5, 1.0, $\infty$ |
| Default (Single Agent) | 0, 1, 2, $\infty$ |
| Default (Multi Agent) | 0, $\infty$ |

### A.3 Parameter-optimized performance split by λ p \lambda_{\text{p}} values

Figure: (a) Academic Advising
Refer to caption: images/ipa_results/ipa_bonus_aa.png

Figure: (p) Chess
Refer to caption: images/ipa_results/ipa_bonus_che.png

### A.4 Definition of the relative improvement and pairings score

In the main experimental section, we evaluated IPA-UCT with respect to the relative improvement and pairings score, which are formalized here. These scores are Borda-like rankings to score the ability of an agent to perform well in a large number of tasks and these were already used in Schmöcker et al. (2025a; b). The relative improvement score quantifies the average improvement percentages over other agents and the pairings score simply quantifies the number of tasks some agent outperformed another agent but does not take the magnitude of the improvement into consideration.

Definition:
Let $\{\pi_{1},\dots,\pi_{n}\}$ be $n$ agents (e.g., concrete parameter settings) where each agent was evaluated on $m$ tasks (e.g. a given MCTS iteration budget and an environment) where $p_{i,k}\in\mathbb{R}$ denotes the performance of agent $\pi_{i}$ on the $k$-th task.
The pairings score matrix $M^{\text{pairings}}\in\mathbb{R}^{n\times n}$ is defined as

$$ $M^{\text{pairings}}_{i,j}=\frac{1}{m-1}\sum\limits_{1\leq k\leq m}\text{sgn}(p_{i,k}-p_{j,k})$ (7) $$

where sgn is the signum function.
The pairings score $s^{\text{pairings}}_{i},i\leq n$ is given by

$$ $s^{\text{pairings}}_{i}=\frac{1}{n-1}\sum\limits_{1\leq l\leq n,l\neq i}M^{\text{pairings}}_{i,l}.$ (8) $$

The relative improvement matrix $M^{\text{rel}}\in\mathbb{R}^{n\times n}$ is defined as

$$ $M^{\text{rel}}_{i,j}=\frac{1}{m-1}\sum\limits_{1\leq k\leq m}\frac{p_{i,k}-p_{j,k}}{\max(|p_{i,j}|,|p_{j,k}|)}$ (9) $$

and the relative improvement score $s^{\text{rel}}_{i},i\leq n$ is given by

$$ $s^{\text{rel}}_{i}=\frac{1}{n-1}\sum\limits_{1\leq l\leq n,l\neq i}M^{\text{rel}}_{i,l}.$ (10) $$

### A.5 Runtime measurements

Tab. [2](https://arxiv.org/html/2510.26346v1#A1.T2) lists the average decision-making times for each environment of IPA-UCT compared to OGA-UCT for 100 and 2000 iterations on states sampled from a distribution induced by random walks. This shows that while UCT adds only a minor overhead, despite having to execute more UCB evaluations. In particular, we are using highly optimized environment implementations that could be the runtime bottleneck in more complex environments.

**Table 2: Average decision-making times of IPA-UCT versus OGA-UCT in milliseconds for 100 and 2000 iterations. This data was obtained using an Intel(R) Core(TM) i5-9600K CPU @ 3.70GHz. The data shows a median runtime overhead of $\approx$5% for 100 iterations and $\approx$9% for 2000 iterations.**
| Domain | IPA-UCT-100 | OGA-UCT-100 | IPA-UCT-2000 | OGA-UCT-2000 |
| --- | --- | --- | --- | --- |
| Academic Advising | 2.22 | 2.01 | 164.63 | 125.61 |
| Cooperative Recon | 4.14 | 3.91 | 267.31 | 232.49 |
| Crossing Traffic | 2.85 | 2.62 | 382.01 | 378.96 |
| Connect4 | 1.77 | 1.69 | 112.21 | 98.94 |
| Chess | 18.01 | 18.40 | 454.55 | 421.35 |
| Constrictor | 4.96 | 4.71 | 347.41 | 316.53 |
| Earth Observation | 7.61 | 7.92 | 367.06 | 345.02 |
| Game of Life | 4.14 | 4.02 | 273.46 | 260.22 |
| Manufacturer | 10.46 | 10.75 | 332.33 | 323.48 |
| Navigation | 2.57 | 2.34 | 104.53 | 82.99 |
| NumbersRace | 2.26 | 1.33 | 1012.79 | 876.50 |
| Othello | 8.18 | 7.77 | 328.30 | 333.46 |
| Pylos | 4.78 | 4.84 | 229.06 | 206.96 |
| Quarto | 2.96 | 2.89 | 226.28 | 219.62 |
| Racetrack | 1.60 | 1.46 | 85.47 | 82.78 |
| Sailing Wind | 2.23 | 2.15 | 185.44 | 169.06 |
| Saving | 1.48 | 1.37 | 249.19 | 246.40 |
| Skills Teaching | 3.95 | 4.08 | 262.31 | 218.11 |
| SysAdmin | 1.90 | 1.81 | 173.24 | 156.65 |
| Tamarisk | 2.94 | 2.87 | 145.57 | 134.80 |
| Traffic | 3.94 | 3.81 | 171.77 | 167.41 |
| Triangle Tireworld | 4.43 | 3.85 | 143.73 | 125.15 |
| Tic Tac Toe | 1.06 | 0.98 | 54.46 | 47.35 |

### A.6 Proof of state-abstraction theorem

Here, we will prove the following theorem from the main section:

Theorem: Assume $s_{1},s_{2}$ are two states with $n$ and $l$ actions respectively. Furthermore, assume that each of $s_{1}$’s and $s_{2}$’s actions is assigned to an abstract Q node from a pool of $m$ abstract Q nodes with uniform probability. The probability $p_{\text{abs}}$ of $s_{1}$ and $s_{2}$ being abstracted according to the ASAP framework can be exactly denoted and then upper bounded by

$$ $p_{\text{abs}}=\frac{\sum\limits_{k=1}^{c\coloneqq\min\{n,l,m\}}\binom{m}{k}f(n,k)f(l,k)}{m^{n+l}}\leq\left(\frac{2c}{m}\right)^{n+l}$ (11) $$

where $f(n,k)$ is the number of surjections from a set of $n$ elements to a set of $k\leq n$ elements.

Proof: Let us denote $s_{1}$’s actions by $A=\{a_{1},\dots,a_{n}\}$ and $s_{2}$’s actions by $B=\{b_{1},\dots,b_{l}\}$. The set of abstract nodes is denoted as $\mathbb{A}_{1},\dots,\mathbb{A}_{m}$.
We denote the abstraction that has uniformly been assigned to an action $c\in\{a_{1},\dots,a_{n},b_{1},\dots,b_{l}\}$ by $\text{abs}(c)$. Using the ASAP framework definition, it holds that

$$ $p_{\text{abs}}=\mathbb{P}[\{\text{abs}(a_{i})\>|\>1\leq i\leq n\}=\{\text{abs}(b_{i})\>|\>1\leq i\leq l\}].$ (12) $$

Since by assumption the abstraction assignment is uniform, $p_{\text{abs}}$ can be denoted as the ratio of abstraction assignments for $s_{1}$ and $s_{2}$ that result in the same set of abstract nodes divided by all possible abstraction assignments. Furthermore, assignments that result in the same set of abstract nodes can be split by the size of that abstract node set. Hence,

$$ $\displaystyle p_{\text{abs}}$ $\displaystyle=\frac{\sum\limits_{k=1}^{c\coloneqq\min(n,l,m)}\left|\left\{f\colon A\mapsto X,\ g\colon B\mapsto X\ \middle|\ f,g\text{ surjective, }X\subseteq\mathbb{A},\ |X|=k\right\}\right|}{m^{n+l}}$ $\displaystyle=\frac{\sum\limits_{k=1}^{c}\binom{m}{k}f(n,k)f(l,k)}{m^{n+l}}$ (13) $$

where $\mathbb{A}=\{\mathbb{A}_{1},\dots,\mathbb{A}_{m}\}$. This proves the first part of this theorem. Next, using that $f(n,k)\leq k^{n}$ yields

$$ $\sum\limits_{k=1}^{c}\binom{m}{k}f(n,k)f(l,k)\leq\sum\limits_{k=1}^{c}\binom{m}{k}k^{n+l}\leq c^{n+l}\sum\limits_{k=1}^{c}\binom{m}{k}\leq c^{n+l}2^{c}\leq(2c)^{n+l}$ (14) $$

from which the theorem directly follows. ∎

### A.7 Number of state abstractions built by OGA and IPA

**Table 3: Comparison of abstraction statistics for different state abstractions and models to show that OGA almost never finds any state abstractions in contrast to our method IPA. Each column denotes the measured ratio of size one state abstractions to the number of total abstractions (excluding trivial abstractions, i.e. those that group all terminal states or size-one abstractions that did not yet receive an update). Hence, the value $1.00$ corresponds to no non-trivial state abstractions, while a value close to 0 means that almost all states are grouped into node abstract node. The states whose statistics were averaged come from the state distribution of standard OGA-UCT (see Section [4](https://arxiv.org/html/2510.26346v1#S4)). For IPA-UCT, we used $\lambda_{\text{p}}=0$. The results were averaged from 100 episodes each. The epsilon values $\varepsilon_{\text{t}}$ denote the transition function threshold defined in Section [2](https://arxiv.org/html/2510.26346v1#S2).**
| Domain | $\varepsilon_{\text{t}}=0$ | $\varepsilon_{\text{t}}=0.4$ |  |  |
| --- | --- | --- | --- | --- |
| OGA | IPA | OGA | IPA |  |
| Academic Advising | 1.00 | 1.00 | 1.00 | 0.96 |
| Crossing Traffic | 0.50 | 0.55 | 0.50 | 0.55 |
| Cooperative Recon | 1.00 | 0.88 | 0.99 | 0.82 |
| Connect4 | 0.99 | 0.95 | 0.99 | 0.95 |
| Constrictor | 0.99 | 0.99 | 0.99 | 0.99 |
| Earth Observation | 1.00 | 1.00 | 0.94 | 0.92 |
| Game of Life | 1.00 | 1.00 | 0.96 | 0.91 |
| Manufacturer | 1.00 | 1.00 | 1.00 | 0.93 |
| Navigation | 1.00 | 0.95 | 1.00 | 0.90 |
| NumbersRace | 1.00 | 0.91 | 1.00 | 0.91 |

### A.8 Ratio of value equivalences

**Table 4: A list of the ratios of local state pairs and action pairs that are value-equivalent to explain why IPA did not improve the performance in Triangle Tireworld or Sailing Wind because these environments contain very few value-equivalent states. These ratios were determined by randomly sampling $10^{5}$ states. We then applied $i\in\{1,2,3\}$ random actions to each state and a copy of each state. We then counted how many times out of these $10^{5}$ states, the resulting states after applying $i$ actions, had the same value or the same Q-value for the $i$-th action. We denote these ratios by $V_{\text{abs}}(i)$ and $Q_{\text{abs}}(i)$. Hence, a ratio of $1.00$ would mean that all states in a search tree layer have the same optimal value, while a ratio of $0.00$ means that no two states have the same $V^{*}$ value.**
| Model | $V_{\text{abs}}(0)$ | $Q_{\text{abs}}(0)$ | $V_{\text{abs}}(1)$ | $Q_{\text{abs}}(1)$ | $V_{\text{abs}}(2)$ | $Q_{\text{abs}}(2)$ |
| --- | --- | --- | --- | --- | --- | --- |
| Crossing Traffic | 0.83 | 0.89 | 0.84 | 0.88 | 0.85 | 0.88 |
| Navigation | 0.05 | 0.05 | 0.05 | 0.13 | 0.05 | 0.12 |
| Racetrack | 0.38 | 0.53 | 0.37 | 0.42 | 0.34 | 0.37 |
| Sailing Wind | 0.04 | 0.01 | 0.03 | 0.01 | 0.03 | 0.01 |
| Skill Teaching | 0.29 | 0.11 | 0.17 | 0.11 | 0.06 | 0.04 |
| Triangle Tireworld | 0.03 | 0.67 | 0.03 | 0.61 | 0.03 | 0.59 |

### A.9 Performances of Alternative Pruning Methods

In Section [5](https://arxiv.org/html/2510.26346v1#S5) it was mentioned that preliminary experiments on alternative pruning methods were conducted which showed most promise for IPA-UCT compared to TOPN-UCT and CONF-UCT. These results are shown here. Concretely, the following Table [5](https://arxiv.org/html/2510.26346v1#A1.T5) lists the parameter-optimized performances of IPA-UCT, TOPN-UCT, and CONF-UCT for 500 iterations using the following parameters.
For $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA, the environment specific $\varepsilon_{\text{a}}$ values (see Table [1](https://arxiv.org/html/2510.26346v1#A1.T1)) that include $\{0,\infty\}$ and $\varepsilon_{\text{t}}\in\{0,0.2,0.4,0.8\}$ were tested. For pruned OGA $\alpha\in\{0,0.1,0.2,0.5,0.75,1.0\}$ was tested. The table lists the best performances out of these two techniques. If IPA-UCT is used, then $\lambda_{\text{p}}\in\{0,0.25,0.5,1,2,4,\infty\}$ was varied, for CONF-UCT, we varied $p_{\text{c}}\in\{0.1,0.25,0.5,0.75,0.9\}$, and for TOPN-UCT, $(n_{\text{matches}},n_{\text{min}})\in\{1,2\}\times\{0,50\}$ was used. All methods were run with $C=2$.

**Table 5: The performances various pruning methods as alternatives for the UCB-based pruning in IPA-UCT.**
|  | IPA-UCT | CONF-UCT | TOPN-UCT |
| --- | --- | --- | --- |
| Academic Advising | $\bm{-67.0\pm 0.9}$ | $-67.3\pm 0.9$ | $-68.0\pm 0.9$ |
| Chess | $\bm{0.2\pm 0.0}$ | $0.1\pm 0.0$ | $0.1\pm 0.0$ |
| Connect4 | $\bm{0.2\pm 0.0}$ | $0.2\pm 0.0$ | $0.1\pm 0.0$ |
| Constrictor | $\bm{0.1\pm 0.0}$ | $0.1\pm 0.0$ | $0.1\pm 0.0$ |
| Cooperative Recon | $\bm{13.3\pm 0.3}$ | $11.2\pm 0.4$ | $10.7\pm 0.4$ |
| Crossing Traffic | $\bm{-25.0\pm 1.2}$ | $-25.9\pm 1.3$ | $-25.9\pm 1.3$ |
| Earth Observation | $\bm{-8.4\pm 0.2}$ | $-8.5\pm 0.3$ | $-8.5\pm 0.2$ |
| Game of Life | $565.1\pm 2.4$ | $\bm{566.0\pm 2.3}$ | $565.1\pm 2.3$ |
| Manufacturer | $-1214.4\pm 12.9$ | $\bm{-1212.8\pm 12.9}$ | $-1303.0\pm 14.4$ |
| Navigation | $-15.9\pm 0.4$ | $\bm{-15.9\pm 0.4}$ | $-17.5\pm 0.5$ |
| NumbersRace | $\bm{0.2\pm 0.0}$ | $-0.0\pm 0.0$ | $0.1\pm 0.0$ |
| Othello | $0.2\pm 0.0$ | $\bm{0.2\pm 0.0}$ | $0.2\pm 0.0$ |
| Pylos | $0.2\pm 0.0$ | $\bm{0.2\pm 0.0}$ | $0.2\pm 0.0$ |
| Quarto | $\bm{0.2\pm 0.0}$ | $0.1\pm 0.0$ | $0.2\pm 0.0$ |
| Racetrack | $-8.7\pm 0.0$ | $-8.7\pm 0.0$ | $\bm{-8.6\pm 0.0}$ |
| Sailing Wind | $\bm{-64.0\pm 1.2}$ | $-64.3\pm 1.3$ | $-64.5\pm 1.3$ |
| Saving | $\bm{49.4\pm 0.2}$ | $49.4\pm 0.2$ | $49.3\pm 0.2$ |
| Skills Teaching | $\bm{65.4\pm 7.5}$ | $63.7\pm 7.6$ | $31.9\pm 7.5$ |
| SysAdmin | $\bm{396.2\pm 2.0}$ | $395.8\pm 2.0$ | $395.4\pm 2.0$ |
| Tamarisk | $\bm{-562.9\pm 8.5}$ | $-573.2\pm 8.6$ | $-604.8\pm 8.8$ |
| TicTacToe | $0.0\pm 0.0$ | $0.0\pm 0.0$ | $\bm{0.0\pm 0.0}$ |
| Traffic | $\bm{-15.1\pm 0.3}$ | $-15.1\pm 0.3$ | $-15.2\pm 0.3$ |
| Triangle Tireworld | $80.5\pm 1.2$ | $\bm{80.8\pm 1.2}$ | $80.6\pm 1.1$ |

### A.10 How IPA-UCT transforms J UCB J_{\text{UCB}} into an equivalence relation

Since $J_{\text{UCB}}$ does not induce an equivalence relation, we cannot simply place any two states $s_{1},s_{2}$ such that $s_{1}\sim_{J_{\text{UCB}}}s_{2}$ into the same abstract node. We will handle this similarly to how the epsilon greater than zero case for the state-action-pairs (i.e. $(\varepsilon_{\text{a}},\varepsilon_{\text{t}})$-OGA) case was handled. Again, the aim of the following heuristic is to produce an equivalence relation for states whilst creating as big and stable as possible abstract nodes. The subsequent technique corresponds to the method compute_state_abstraction in the Pseudocode [1](https://arxiv.org/html/2510.26346v1#alg1).

Each abstract state node now also keeps track of its representative, which is one of its original nodes. Furthermore, it is assigned a unique and constant ID at its creation. At its creation, an abstract node is assigned an ID equal to the total number of abstract state nodes that have been created so far. Whenever a state node $s$ with abstract node $\mathcal{N}$ is updated, the set $J_{\text{UCB}}(s)$ is updated. Then, if either $s$ is the representative of $\mathcal{N}$ or if the equations [4](https://arxiv.org/html/2510.26346v1#S3.E4), [5](https://arxiv.org/html/2510.26346v1#S3.E5) do not hold (with respect to the representative of $\mathcal{N}$), then the abstract node of $s$ is updated by choosing the largest abstract node (tie breaks by using the ID) with a representative $s^{\prime}$ such that $s\sim_{J_{\text{UCB}}}s^{\prime}$. In case this leads to a different abstract node than the current one of $s$, a new representative for the old abstract node is chosen at random. In the case $s^{\prime}=s$, then the equations [4](https://arxiv.org/html/2510.26346v1#S3.E4), [5](https://arxiv.org/html/2510.26346v1#S3.E5) are checked with the old value $J_{\text{UCB}}$ for $s^{\prime}$.

### A.11 Monte Carlo Tree Search

All abstraction algorithms presented here rely on Monte Carlo Tree Search (MCTS). In the following we are going to specify the MCTS version used here.

- 1.
Since this is a necessary requirement for ASAP and IPA to detect abstractions in the first place, our MCTS version builds a directed acyclic graph, i.e. two state-action pairs have the same successor node if it represents the same MDP state.
- 2.
The tree policy is the Upper Confidence Bounds (UCB) policy which chooses the action that maximizes the UCB value
$\text{UCB}(a)=\underbrace{\frac{V_{a}}{N_{a}}}_{\text{Q term}}+\underbrace{\lambda\sqrt{\frac{\log\left(\sum\limits_{a^{\prime}\in\mathbb{A}(s)}N_{a^{\prime}}\right)}{N_{a}}}}_{\text{Exploration term}}.$
(15)
Here, $s$ is the state at which the decision has to be made, $V_{a}$ is the sum of returns of the action under consideration, and $N_{a}$ are its visits.
- 3.
The greedy decision policy is used, i.e. the root action with the maximal Q value is chosen as the final decision.

### A.12 Problem descriptions

All the problem domains that appeared in this paper are described in Schmöcker et al. (2025c) as well as in Schmöcker et al. (2025e).
Furthermore, most environments are parametrizable (e.g., the racetrack choice in Racetrack). The concrete parameter choices used for the experiments can be found in the ExperimentConfigs folder of the repository accompanying this paper Schmöcker (2025).

### A.13 IPA-UCT Pseudocode

Figure: Algorithm 1 IPA-UCT

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: 1. Could the authors provide more concrete examples or visualizations showing how IPA-UCT’s discovered state abstractions differ qualitatively from those of OGA-UCT?
2. Is there a principled or heuristic way to learn the hyperparameters (e.g., lambda) adaptively during search to improve generalization across domains?
3. Could the authors include standard deviations in the main experiments?
soundness: 2
strengths: - The motivation of the proposed framework is intuitive and understandable. The paper also provides a principled extension of the abstraction hierarchy which is reasonable.
- The authors demonstrate why prior methods struggle to discover meaningful state abstractions and how their framework mitigates this limitation.
- Experiments show the effectiveness of the proposed method. The authors also include ablations on a few hyperparameters. Finally, the paper is well written and easy to follow.
summary: The paper proposes a framework for relaxed state abstraction that can be flexibly applied to noisy or large action space. The authors propose Ideal Pruning Abstractions in UCT (IPA-UCT) that prunes suboptimal actions to reveal additional state equivalences. They formalize the underlying theoretical framework by introducing IPA, p-ASAP, and ASASAP abstractions, generalizing existing abstraction schemes. Empirically, IPA-UCT consistently improves sample efficiency and planning performance across diverse decision-making domains.
weaknesses: - I think it is good to include more intuition or visualization on how the discovered abstractions influence search behavior in more complex domains.
- It is questionable that the proposed framework could be extended to more complex high-dimensional environments. Could the authors include discussions on this?

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: ### Questions for Authors

1. Can you provide empirical pruning error rates? How often does J_UCB prune an actually optimal action at typical visit counts (100, 500, 1000) across several domains? Even without a formal bound, this data would help assess practical risk.

2. How stable are state clusters under your equivalence closure heuristic (A.11)? Can you report "cluster churn"—how often states switch abstract nodes as search progresses?

3. Why not compare against PARSS or Elastic-MCTS on a few domains? This would help situate IPA's contribution relative to other recent abstraction methods.

4. The Navigation example is compelling, but it seems somewhat cherry-picked. Can you identify which environments from your test suite have similar structure where IPA should theoretically help, and which don't, then show this correlates with your empirical results?

### Suggestions for Improvement

- **Add finite-time analysis**: Even a simplified analysis would substantially strengthen the paper.

- **Move A.11 to main text**: The equivalence closure heuristic is essential to understanding what IPA-UCT actually does. Summarize it in the main paper with discussion of trade-offs.

- **Clarify positioning**: Add a paragraph explicitly connecting to distance-based and bisimulation-style abstractions as complementary approaches that also relax strict equivalence. You don't need new experiments—just help readers understand where IPA fits.

- **Method section**: Can be restructured or writing can be improved to remove weird phrase switches like "theory:" / "empirical results".

### Recommendation

The core idea is sensible and the experimental work is careful. However, the paper sits uncomfortably between theory and practice: the theory is limited to asymptotic guarantees that don't address the finite-sample regime where the method operates, and the empirical gains over strong OGA baselines are modest when parameters are tuned per-environment. 

I could move toward acceptance if the authors provide: (1) finite-sample analysis or at least empirical pruning error rates, (2) evidence that adaptive λ_p can achieve robust performance, or (3) clearer positioning and comparison against other recent abstraction methods. The current contribution feels incremental.
soundness: 3
strengths: - **Clear problem diagnosis**: The combinatorial bound (Equation 7) and toy example effectively demonstrate why OGA finds almost no state abstractions. Table 2 in the appendix backs this up empirically.

- **Simple, practical solution**: The UCB-based pruning (Equation 10) is easy to implement and aligns naturally with how UCT allocates samples.

- **Thorough empirical evaluation**: Testing on many domains with multiple budgets, proper confidence intervals (99%), and generalization-focused metrics (pairings/relative improvement) rather than just per-environment tuning.

- **Low overhead**: The ~5-9% runtime cost (Table 1) is reasonable for the gains achieved.
summary: The paper identifies a problem with ASAP/OGA-UCT: they rarely find state abstractions because they require matching *all* actions between states. The authors propose IPA (Ideal Pruning Abstractions), which only compares near-optimal actions, and implement this as IPA-UCT by using a UCB-based pruning set within OGA-UCT. The theoretical motivation is a combinatorial bound (Equation 7) showing ASAP's strictness, illustrated with a Navigation example. Experiments across 20+ domains show consistent but modest improvements in aggregate metrics (pairings and relative improvement), with 5-9% runtime overhead. Soundness is proven asymptotically.
weaknesses: **Major issues:**

1. **Missing finite-sample analysis**: The soundness guarantee is only asymptotic. There's no analysis of how often J_UCB prunes optimal actions at realistic visit counts (100-1000). This is critical since the method specifically targets low-sample regimes.

2. **Modest empirical gains**: While aggregate improvements are consistent, per-environment parameter-optimized results (Figures 6-7, Appendix A.2) often show ties or minimal improvements. The authors acknowledge gains are small even in the best cases. For ICLR, I'd expect either stronger empirical results or more substantial theory.

3. **Parameter sensitivity without adaptive solution**: Performance depends heavily on λ_p (Figure 5), but there's no adaptive scheduling mechanism—just grid search. The paper notes this as a limitation but doesn't attempt simple solutions like annealing λ_p with depth or visit counts.

**Minor issues:**

4. **Equivalence relation approximation**: J_UCB doesn't induce an equivalence relation, requiring the heuristic representative/tie-break mechanism (Appendix A.11). This is central to making the method work but relegated to the appendix.

5. **Limited positioning**: Related work mentions refinement-based abstractions (PARSS) and Elastic-MCTS but doesn't compare against them or clearly delineate where IPA fits in the landscape of approximate abstraction methods.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: - What is the meaning of the sentence in line 147 “Hence, any abstraction algorithms using these, need to be slightly modified”?
- What could be the definition of the words “correct abstractions” in line 149? (feels a bit ambiguous)
- Did IPA handle stochastic environments well?
soundness: 3
strengths: The problem statement is clearly described. The proposed method is simple and directly complement the baseline (ASAP) and is theoretically well established. Empirical results show constant improvements compared to the baseline. Limitations of IPA are well discussed.
summary: Authors propose IPA, a novel MCTS abstraction mechanism to foster more state abstraction than in the ASAP baseline. While ASAP abstracts state nodes when all their actions are equivalent, IPA abstracts state nodes just when their expected optimal actions are equivalent. IPA is merged with OGA-UCT into IPA-UCT, which constantly outnumbers the states OGA-UCT abstracted and constantly outperforms OGA-UCT for various iteration budgets on diverse board games. Authors also propose conceptual categorization of abstraction methods, positioning IPA and ASAP branched from p(runed)-ASAP whose parent is ASASAP.
weaknesses: ### Major Weaknesses

- Writing and Readability Issues: The main idea of this paper is novel and sound, but the most degrading part is the writing. Once understood, the theoretical and empirical results are convincing, but reaching that level of understanding required several careful readings. Some sentences are overly lengthy or colloquial, making the paper unnecessarily exhausting to read.

- Delayed Introduction of the Main Method (IPA): The exact mechanism of the proposed method, IPA, does not appear until page 6. While several preliminary explanations are understandable, the excessive focus on foundations and previous methods distracts from the main contribution. Since the main suggestion of the paper is IPA, providing a brief abstract explanation of the IPA mechanism earlier (e.g., in the Introduction) would improve readability and focus.

- Structural and Organizational Issues: The new formulations of ASASAP and p-ASAP on pages 2–3 are difficult to follow due to repetitive and unfamiliar terminology. These parts may be theoretically useful, but positioning them later in the Method or Discussion section would improve clarity. Section 2 also includes paragraphs (“OGA-UCT for multi-agent settings,” “OGA-UCT extensions to high stochasticity,” and “RSTATE-OGA”) that seem more appropriate for the Experimental Setup. In the Method section, describing IPA first and then comparing it to ASAP would create a smoother and more logical flow.

### Minor Weaknesses
- Although it is not necessarily a weakness, I suggest adding some actual state abstraction examples that ASAP could not detect but IPA did, based on the environments used in experiments. While a conceptual example is already described on page 6 with the grid navigation task, presenting actual examples would more effectively support the proposed claims. Additionally, showing faulty abstraction examples from IPA would help illustrate its potential limitations.
- Line 277, Self-reference error (“Section 3”)

---

confidence: 4
contribution: 1
initial_rating: 0
presentation: 1
questions: - You state that you plot the 99% confidence intervals. I do not see any error bars or anything. Is it because the intervals are too small at the scale at which the figures are plotted?
- What is a pairing value?
- What is an abstract Q node?
- Why are you stating that $s$ is a successor to $s'$ when conventionally it goes the other way? This adds to the unreadability of Sec 2.
- "Later, when the different OGA variants are experimentally investigated, one ablation that will also be conducted is to test the performance of random state abstractions to ensure that any performance gains due to the usage of abstractions are better than if random abstractions were used." Where do you do this? Is this in Figs 3 and 4? Are they improvements over random abstractions or no abstractions?
soundness: 2
strengths: - The evaluation design was done well. The authors ran their experiments on a wide array of problem domains and with a suitably high number of random seeds to demonstrate statistical significance.
- The motivation for the paper is strong. State abstraction remains a challenging problem in planning and methods to do so are of great interest to the community.
- Although, I only skimmed the proof, the claim of why ASAP finds few abstractions seems to supported by their theory.
summary: This paper is tries to improve on abstractions used for reducing the search space in Monte Carlo tree search (MCTS). Typically, in large, sequential decision spaces MCTS employs abstraction methods to aggregate states to reduce the search space. However, the authors claim that little work is done in stochastic settings or settings with large action spaces.  They show how one such abstraction technique, On the Go Abstractions in Upper Confidence bounds applied to trees (OGA-UCT) fails in these settings. The authors then provide a remedy to this problem by introducing IPA-UCT that addresses a key issue that causes OGA-UCT to fail. The authors then provide experimental results in a number of domains to show how their approach improves on OGA-UCT.
weaknesses: - The main weakness with the paper is its lack of significance. The method the authors propose, pruning actions with UCB values less than $Q_{max}$, seems to effectively boil down to considering only the $k$ actions with the highest UCB values for search and abstraction for some arbitrary value of $k$. This minor change is not enough to be considered a significant contribution.
- If we consider the argument they show for why ASAP fails, the authors do not clearly explain how IPA-UCT explicitly overcomes this nor do they link it back to the theory (Eq (7)) they provide.
- Another reason, I believe the contributions are not clear is because they discuss their contributions only briefly. The authors spend almost 3 pages describing the background (Sec 2). The space could be better used to focus on their contributions.
- Additionally, the background section was a tough read. It was difficult to understand. I did not quite understand the intent behind how they structured the section but there was no flow in information. They do not formally define equivalence, or equivalence classes. The definition of equivalence relations is really confusing as it defined double-recursively and the authors do not provide any base cases (see Eqs 1, 2 and 3).
- I also do not see how what they describe is different from the concept of bisimilarity. If it is the same, why do they not base their description using that formalism?
- The example using the Navigation problem domain does not seem to be correct. Firstly, while the optimal path is to follow 3->8->13->18, this path does not yield an average return of -3. It would do so if cell 8 had a 0.0 probablity of a reset. However, with a non-zero reset chance, the average return will be < -3. Secondly, according to the definition of ASAP-equivalence in Eq (6), the two suboptimal paths would indeed be abstracted. The definition states that as long as each state has at least one action leading to an identical outcome, they
would be abstracted. For this example, 12->13 would be equivalent to 14->13 according to Eq (6). Am I missing or misunderstanding something?
- In the experiments, Figs 3 and 4 show plots for three algorithms. However, the description discusses four algorithms. Is one missing or are two plots joined together?
- Maybe I missed it, but I could not find an explanation of what pairing values are.
- In figures 5 and 6, the authors state there is a downward trend with the value of $\lambda_p$. Given what the plots look like, I do not think that is a statement that can confidently be made. If we were to make that statement anyway, it would only apply to pairing values. The improvement value plots seem to get flat with an increase in the number of iterations. It seems the pruning factor makes no difference if we give search enough samples, which makes sense. Overall, the plots are very erratic and I don't know what to make of the results described.