Exact Reduction of Huge Action Spaces in General Reinforcement Learning

Sultan Javed Majeed, Marcus Hutter

Introduction

Reinforcement Learning (RL) provides a robust framework for learning through interaction. However, many real-world applications—ranging from robotics and protein folding to complex games like StarCraft—present "huge" action spaces that cripple standard algorithms. This "curse of dimensionality" often makes finding near-optimal policies computationally or theoretically intractable.

The Challenge: Extreme State Aggregation (ESA)

Extreme State Aggregation (ESA) was developed to provide universal upper bounds on the number of states required for near-optimal performance in non-Markovian environments. While powerful, ESA previously suffered from a significant limitation: the required state-space size grew exponentially with the size of the action space $|\mathcal{A}|$. For environments with thousands of actions, these theoretical bounds became astronomically large, limiting the practical applicability of the framework.

Proposed Method: Action Sequentialization

The authors address this bottleneck by "sequentializing" the action space. Instead of the agent making a single complex choice from a massive set, the decision is broken down into a sequence of simpler binary choices.

The sequentialized agent-environment interaction loop, introducing a surrogate environment to handle bit-by-bit action selection.

This is achieved by inserting a "Sequential Environment" (or Mock Environment) between the agent and the original environment. The agent provides a sequence of bits, and only once a full binary string of length $d = \log_2 |\mathcal{A}|$ is received does the environment execute the corresponding original action.

A tree-based representation of action binarization, where a single decision is decomposed into a sequence of binary choices.

Theoretical Equivalence and Near-Optimality

A critical contribution of this work is the rigorous proof that this transformation preserves the essential properties of the original problem. The authors demonstrate:

  1. Markov Property Preservation: If the original environment was a Markov Decision Process (MDP), the sequentialized version remains an MDP (Theorem 4.2).
  2. Policy Equivalence: A near-optimal policy in the binarized environment translates directly back to a near-optimal policy in the original environment (Theorem 4.6).

Key Results: A Double-Exponential Improvement

By applying binarization to the ESA framework, the authors achieve a massive reduction in the state-space bound. The previous bound, which was exponential in $|\mathcal{A}|$, is replaced by a bound that is logarithmic in $|\mathcal{A}|$. Specifically, the new bound for Binary ESA is: $$|S| \le \frac{4 \lceil 1 - \gamma + \log_2 |\mathcal{A}| \rceil^6}{\gamma^2 \epsilon^2 (1 - \gamma)^6}$$ This represents a double-exponential improvement, moving from $C^{|\mathcal{A}|}$ to $(\log |\mathcal{A}|)^6$. This result makes ESA theoretically viable even for environments with extremely large action sets.

Conclusion

This work provides a fundamental theoretical bridge for handling large action spaces in general RL. While the current bounds still scale significantly with the discount factor and error tolerance, the logarithmic scaling with respect to action space size is a major milestone. Future work will focus on developing practical algorithms to learn these binarized abstractions and further tightening the bounds for the discount factor.

Summary updated

Abstract

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.
BibTeX
@inproceedings{majeed2021exact,
  author = {Sultan Javed Majeed and Marcus Hutter},
  title = {{Exact Reduction of Huge Action Spaces in General Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i10.17074},
}
Figure