Fast Reinforcement Learning with Large Action Sets using Error-Correcting Output Codes for MDP Factorization

Gabriel Dulac-Arnold, Ludovic Denoyer, Philippe Preux, Patrick Gallinari

Abstract

The use of Reinforcement Learning in real-world scenarios is strongly limited by issues of scale. Most RL learning algorithms are unable to deal with problems composed of hundreds or sometimes even dozens of possible actions, and therefore cannot be applied to many real-world problems. We consider the RL problem in the supervised classification framework where the optimal policy is obtained through a multiclass classifier, the set of classes being the set of actions of the problem. We introduce error-correcting output codes (ECOCs) in this setting and propose two new methods for reducing complexity when using rollouts-based approaches. The first method consists in using an ECOC-based classifier as the multiclass classifier, reducing the learning complexity from O(A2) to O(Alog(A)). We then propose a novel method that profits from the ECOC's coding dictionary to split the initial MDP into O(log(A)) seperate two-action MDPs. This second method reduces learning complexity even further, from O(A2) to O(log(A)), thus rendering problems with large action sets tractable. We finish by experimentally demonstrating the advantages of our approach on a set of benchmark problems, both in speed and performance.

Introduction: The Scaling Problem in RL

Reinforcement Learning (RL) often hits a wall when faced with hundreds or thousands of discrete actions because standard algorithms scale poorly with the size of the action set. This paper addresses the challenge of large, discrete, and uncorrelated action sets—a common scenario in real-world robotics or complex decision systems where actions do not have a natural sequential or continuous relationship.

Standard "Rollout Classification" methods typically evaluate every possible action for every state to find the optimal one. This "One-vs-All" (OVA) approach is computationally expensive, scaling quadratically ($O(A^2)$) with the number of actions ($A$). As $A$ grows, training becomes intractable, often taking days for even simple benchmarks.

Proposed Methods: ECOC-based MDP Factorization

The authors build upon Rollout Classification Policy Iteration (RCPI), which treats RL as a multiclass classification problem where the "classes" are the possible actions. They propose two novel extensions to overcome the scaling bottleneck:

  1. ERCPI (ECOC-extended RCPI): Instead of training one classifier per action, this method assigns each action a unique binary string (a "code") using Error-Correcting Output Codes (ECOCs). It trains $C \approx \log A$ binary classifiers. To select an action, the agent runs all classifiers and chooses the action whose code most closely matches the predicted bit-string via Hamming distance. This reduces complexity to $O(A \log A)$.
  2. BRCPI (Binary-RCPI): This method factorizes the MDP itself. It creates $C$ independent "sub-MDPs," each focused on a single bit of the optimal action's code. Since each sub-problem only involves two meta-actions (bit 0 vs. bit 1), the simulation cost drops dramatically, achieving a complexity of $O(\log A)$.
Complexity comparison of the proposed methods.

Experimental Evaluation

The methods were evaluated on two benchmarks modified to test scaling:

  • Mountain Car: The standard task discretized into up to 200 distinct actions.
  • Maze: A 50x50 grid-world where sequences of moves were combined into single actions, reaching up to 719 possible actions. This environment is particularly difficult as there is no inherent similarity between action sequences.

Key Results and Scaling Analysis

  • Computational Speedup: On the Mountain Car task with 100 actions, BRCPI was 12.5x faster overall than the standard OVA approach. In terms of simulation time—the primary bottleneck—it was 23.5x faster.
  • Tractability at Scale: In the Maze task with 719 actions, standard RCPI-OVA and ERCPI were intractable. BRCPI successfully learned a policy in hours that significantly outperformed a random baseline.
  • The Power of Independence: In BRCPI, sub-policies are learned independently. The error-correcting nature of the codes ensures that even if some sub-policies are noisy, the overall system can still identify the correct action. Furthermore, these sub-MDPs are "embarrassingly parallel," allowing for massive speedups on multi-core hardware.
Performance on the Maze task across different action set sizes. Standard methods become intractable as the number of actions increases.

Conclusion and Future Directions

By moving from $O(A^2)$ to $O(\log A)$, this work turns the "curse of dimensionality" into a manageable logarithmic scaling. Future work includes exploring "informed" codes—where actions with similar environmental effects share similar bit-strings—and the automatic discovery of optimal codes during the learning process. While BRCPI provides an approximation of the global policy, its empirical performance demonstrates its viability for previously unreachable large-scale discrete action problems.

Summary updated

Abstract

The use of Reinforcement Learning in real-world scenarios is strongly limited by issues of scale. Most RL learning algorithms are unable to deal with problems composed of hundreds or sometimes even dozens of possible actions, and therefore cannot be applied to many real-world problems. We consider the RL problem in the supervised classification framework where the optimal policy is obtained through a multiclass classifier, the set of classes being the set of actions of the problem. We introduce error-correcting output codes (ECOCs) in this setting and propose two new methods for reducing complexity when using rollouts-based approaches. The first method consists in using an ECOC-based classifier as the multiclass classifier, reducing the learning complexity from O(A2) to O(Alog(A)). We then propose a novel method that profits from the ECOC's coding dictionary to split the initial MDP into O(log(A)) seperate two-action MDPs. This second method reduces learning complexity even further, from O(A2) to O(log(A)), thus rendering problems with large action sets tractable. We finish by experimentally demonstrating the advantages of our approach on a set of benchmark problems, both in speed and performance.
BibTeX
@inproceedings{dulacarnold2012fast,
  author = {Gabriel Dulac-Arnold and Ludovic Denoyer and Philippe Preux and Patrick Gallinari},
  title = {{Fast Reinforcement Learning with Large Action Sets using Error-Correcting Output Codes for MDP Factorization}},
  booktitle = {ECML/PKDD},
  year = {2012},
  url = {https://openreview.net/forum?id=aFFNU4V0SH},
}
Figure