# AUPO -- Abstracted Until Proven Otherwise: A Reward Distribution Based Abstraction Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 27 Oct 2025.

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

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [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)
- [Decision-Making Technology for Autonomous Vehicles Learning-Based Methods, Applications and Future Outlook](https://mlsanity.com/paper/2107.01110/) (2021)
- [pyRDDLGym: From RDDL to Gym Environments](https://mlsanity.com/paper/2211.05939/) (2022)
- [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)
- [Asymmetric Action Abstractions for Multi-Unit Control in Adversarial Real-Time Games](https://mlsanity.com/paper/1711.08101/) (2017)
- [Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction](https://mlsanity.com/paper/2310.06513/) (2023)

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

- [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)
- [Discovering State Equivalences in UCT Search Trees By Action Pruning](https://mlsanity.com/paper/2510.26346/) (2025)

## Abstract (arXiv)

We introduce a novel, drop-in modification to Monte Carlo Tree Search's (MCTS) decision policy that we call AUPO. Comparisons based on a range of IPPC benchmark problems show that AUPO clearly outperforms MCTS. AUPO is an automatic action abstraction algorithm that solely relies on reward distribution statistics acquired during the MCTS. Thus, unlike other automatic abstraction algorithms, AUPO requires neither access to transition probabilities nor does AUPO require a directed acyclic search graph to build its abstraction, allowing AUPO to detect symmetric actions that state-of-the-art frameworks like ASAP struggle with when the resulting symmetric states are far apart in state space. Furthermore, as AUPO only affects the decision policy, it is not mutually exclusive with other abstraction techniques that only affect the tree search.