# Discovering State Equivalences in UCT Search Trees By Action Pruning

arXiv: https://arxiv.org/abs/2510.26346 · HTML: https://mlsanity.com/paper/2510.26346/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 30 Oct 2025.

## Builds on (most cited first, 10 of 10)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Vector Quantized Models for Planning](https://mlsanity.com/paper/2106.04615/) (2021)
- [CAMPs: Learning Context-Specific Abstractions for Efficient Planning in Factored MDPs](https://mlsanity.com/paper/2007.13202/) (2020)
- [Adaptive Discretization using Voronoi Trees for Continuous POMDPs](https://mlsanity.com/paper/2302.10439/) (2023)
- [Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction](https://mlsanity.com/paper/2406.00614/) (2024)
- [Time-critical and confidence-based abstraction dropping methods](https://mlsanity.com/paper/2507.02703/) (2025)
- [Investigating Scale Independent UCT Exploration Factor Strategies](https://mlsanity.com/paper/2510.21275/) (2025)
- [AUPO -- Abstracted Until Proven Otherwise: A Reward Distribution Based Abstraction Algorithm](https://mlsanity.com/paper/2510.23214/) (2025)
- [Investigating Intra-Abstraction Policies For Non-exact Abstraction Algorithms](https://mlsanity.com/paper/2510.24297/) (2025)
- [Grouping Nodes With Known Value Differences: A Lossless UCT-based Abstraction Algorithm](https://mlsanity.com/paper/2510.25388/) (2025)

## Abstract (arXiv)

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.