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:
- Encoding: Each action in the original space is mapped to a unique binary string of length $d = \lceil \log_2 |A| \rceil$.
- Sequentialization: The agent makes $d$ sequential binary decisions to construct one original action.
- 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.
- 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.
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