Exact Reduction of Huge Action Spaces in General Reinforcement Learning

Sultan Javed Majeed, Marcus Hutter

Introduction

Presented at AAAI-21, this research addresses a fundamental hurdle in Reinforcement Learning (RL): the "curse of dimensionality" within action spaces. While significant effort has been devoted to managing large state spaces, this work provides a theoretical breakthrough for environments where the set of possible actions is massive. By "binarizing" complex actions into sequences of binary decisions, the authors achieve a double-exponential improvement in theoretical state-space bounds, transforming an exponential dependency on action-space size into a logarithmic one.

The Challenge of Large Action Spaces

Standard RL often assumes a Markov Decision Process (MDP) framework, where the current observation provides sufficient information for decision-making. However, many real-world applications—such as robotics or protein folding—are non-Markovian, requiring agents to account for the entire history of interactions.

A prior framework known as Extreme State Aggregation (ESA) addressed these "General RL" problems by grouping histories with similar optimal values into a finite set of states. Despite its theoretical elegance, ESA suffered from a critical limitation: the number of required states grew exponentially with the size of the action space ($|A|$). In environments with vast action sets, the resulting "compressed" state space remained computationally intractable.

Action Sequentialization and Binarized ESA

To overcome this, the authors propose Action Sequentialization. Instead of selecting a single complex action from a massive set at each environmental time step, the process is decomposed into a series of simpler steps:

  1. Encoding: Each action in the original space is mapped to a unique binary string of length $d = \lceil \log_2 |A| \rceil$.
  2. Sequentialization: The agent makes $d$ sequential binary decisions to construct one original action.
  3. Sequentialized Environment: A "mock" environment is introduced that provides dummy observations and zero rewards during the intermediate bit-selection steps. It only returns a real observation and reward from the original environment once the full bit-string is completed.
The sequentialized environment ($\check{P}$) acts as an intermediary between the agent and the original environment ($P$).
  1. Binarized ESA: The ESA framework is then applied to this sequentialized process. By breaking down the actions, the complexity is shifted from the action space into the state space in a highly efficient manner.
A tree representation of action sequentialization, where a single action is formed through a sequence of binary choices ($x_1, x_2, \dots$).

Theoretical Breakthroughs

The core contribution of this work lies in the rigorous mathematical proof that this shift is not only possible but highly advantageous.

  • Action-to-State Efficiency: The authors prove that the state-space reduction gained by binarization far outweighs the cost of an increased planning horizon.
  • Double-Exponential Improvement: The previous state-space bound for ESA was proportional to $(\text{constant})^{|A|}$. The new "Binary ESA" bound is proportional to $(\log |A|)^6$, a massive reduction in theoretical complexity.
  • Preservation of MDP Properties: Crucially, if the original environment is an MDP, the sequentialized version also retains MDP properties (Theorem 0.4), ensuring that the technique does not introduce unnecessary complexity into simpler problems.

Optimality and Complexity Bounds

The paper establishes two primary results:

  • Optimality Guarantee: Theorem 0.8 demonstrates that a policy nearly optimal in the sequentialized environment (within a specific factor) remains $\epsilon$-optimal in the original environment.
  • The New Bound: Theorem 0.11 provides the definitive bound for the surrogate state space $|S|$: $$|S| \leq \frac{4(1 - \gamma + \log_2 |A|)^6}{\gamma^2 \epsilon^2 (1 - \gamma)^6}$$ This confirms that the state space scales logarithmically with the number of actions, making General RL theoretically feasible even with enormous action spaces.

Discussion and Future Directions

While this work solves the exponential dependency on action space size, several areas for improvement remain. The current bound still scales to the 6th power with the discount factor $\gamma$ and error tolerance $\epsilon$; reducing this to a cubic dependency is a goal for future research. Additionally, while the paper assumes an arbitrary binary encoding, exploring "clever" encodings that group similar actions could further accelerate learning. As a purely theoretical contribution, empirical validation in high-dimensional real-world tasks and the development of algorithms to learn these logarithmic-sized state representations are the next logical steps.

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