# Exact Reduction of Huge Action Spaces in General Reinforcement Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2020.

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

- [Towards Robust Active Feature Acquisition](https://mlsanity.com/paper/2107.04163/) (2021)
- [Distribution Guided Active Feature Acquisition](https://mlsanity.com/paper/2410.03915/) (2024)
- [Action Space Reduction Strategies for Reinforcement Learning in Autonomous Driving](https://mlsanity.com/paper/2507.05251/) (2025)
- [Optimization without Future Compromises? Decentralized Coordination via Collective and Reinforcement Learning](https://mlsanity.com/paper/2509.18088/) (2025)
- [Partial GFlowNet: Accelerating Convergence in Large State Spaces via Strategic Partitioning](https://mlsanity.com/paper/2602.11498/) (2026)
- [Reinforcement Learning with Information-Theoretic Actuation](https://mlsanity.com/paper/2109.15147/) (2021)
- [Reducing Planning Complexity of General Reinforcement Learning with Non-Markovian Abstractions](https://mlsanity.com/paper/2112.13386/) (2021)
- [AutoIndexer: A Reinforcement Learning-Enhanced Index Advisor Towards Scaling Workloads](https://mlsanity.com/paper/2507.23084/) (2025)
- [Multi-Timescale Latent-Action DRL for Joint Optimization in Edge-Cloud Networks](https://mlsanity.com/paper/2607.18288/) (2026)
- [Revisiting Overestimation Bias Problem of Q-learning: Settling Large Discrete Action Space via Action Intersection](https://mlsanity.com/paper/2608.12912/) (2026)

## Abstract (arXiv)

The reinforcement learning (RL) framework formalizes the notion of learning with interactions. Many real-world problems have large state-spaces and/or action-spaces such as in Go, StarCraft, protein folding, and robotics or are non-Markovian, which cause significant challenges to RL algorithms. In this work we address the large action-space problem by sequentializing actions, which can reduce the action-space size significantly, even down to two actions at the expense of an increased planning horizon. We provide explicit and exact constructions and equivalence proofs for all quantities of interest for arbitrary history-based processes. In the case of MDPs, this could help RL algorithms that bootstrap. In this work we show how action-binarization in the non-MDP case can significantly improve Extreme State Aggregation (ESA) bounds. ESA allows casting any (non-MDP, non-ergodic, history-based) RL problem into a fixed-sized non-Markovian state-space with the help of a surrogate Markovian process. On the upside, ESA enjoys similar optimality guarantees as Markovian models do. But a downside is that the size of the aggregated state-space becomes exponential in the size of the action-space. In this work, we patch this issue by binarizing the action-space. We provide an upper bound on the number of states of this binarized ESA that is logarithmic in the original action-space size, a double-exponential improvement.