# Grouping Nodes With Known Value Differences: A Lossless UCT-based Abstraction Algorithm

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 29 Oct 2025.

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

- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [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)

## Built on by (most cited first, 1 of 1)

- [Discovering State Equivalences in UCT Search Trees By Action Pruning](https://mlsanity.com/paper/2510.26346/) (2025)

## Abstract (arXiv)

A core challenge of Monte Carlo Tree Search (MCTS) is its sample efficiency, which can be improved by grouping state-action pairs and using their aggregate statistics instead of single-node statistics. On the Go Abstractions in Upper Confidence bounds applied to Trees (OGA-UCT) is the state-of-the-art MCTS abstraction algorithm for deterministic environments that builds its abstraction using the Abstractions of State-Action Pairs (ASAP) framework, which aims to detect states and state-action pairs with the same value under optimal play by analysing the search graph. ASAP, however, requires two state-action pairs to have the same immediate reward, which is a rigid condition that limits the number of abstractions that can be found and thereby the sample efficiency. In this paper, we break with the paradigm of grouping value-equivalent states or state-action pairs and instead group states and state-action pairs with possibly different values as long as the difference between their values can be inferred. We call this abstraction framework Known Value Difference Abstractions (KVDA), which infers the value differences by analysis of the immediate rewards and modifies OGA-UCT to use this framework instead. The modification is called KVDA-UCT, which detects significantly more abstractions than OGA-UCT, introduces no additional parameter, and outperforms OGA-UCT on a variety of deterministic environments and parameter settings.