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

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

TL;DR

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 introduces a way to factorize a large Markov Decision Process (MDP) into a logarithmic number of binary sub-problems using Error-Correcting Output Codes (ECOCs), slashing computational complexity from $O(A^2)$ to $O(\log A)$.

What Problem Does This Paper Address?

In RL, an agent learns to make decisions by interacting with an environment. While we have great tools for small action sets (like "move left" vs. "move right") and continuous spaces (where we assume similar actions have similar results), we struggle with large, discrete, and uncorrelated action sets.

Imagine a robot with 1,000 distinct, non-sequential commands. Standard "Rollout Classification" methods usually try to evaluate every single action for every state to find the best one. This "One-vs-All" (OVA) approach is computationally expensive—scaling quadratically with the number of actions ($A$). As $A$ grows into the hundreds or thousands, training becomes "intractable," taking days or weeks for even simple benchmarks.

Methods

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:

  1. ERCPI (ECOC-extended RCPI): Instead of training one classifier per action, they assign each action a unique $C$-bit binary string (a "code") using Error-Correcting Output Codes (ECOCs). They then train $C$ binary classifiers (where $C \approx \log A$). To pick an action, the agent runs all classifiers and chooses the action whose code most closely matches the predicted bit-string (using Hamming distance). This reduces complexity to $O(A \log A)$.
  2. BRCPI (Binary-RCPI): This is the paper's heavy hitter. Instead of just changing the classifier, they factorize the MDP itself. They create $C$ independent "sub-MDPs," each having only two meta-actions: "is the $i$-th bit of the optimal action's code a 0 or a 1?" Because each sub-problem only has two actions, the simulation cost drops dramatically. This achieves a complexity of $O(\log A)$.

Datasets

The authors evaluated their methods on two classic RL benchmarks, modified to test scaling:

  • Mountain Car: The standard "get the car up the hill" problem, but with the acceleration range discretized into up to 200 distinct actions.
  • Maze: A 50x50 grid-world. To create large action sets, they combined sequences of moves (e.g., "up-up-right") into single actions, reaching up to 719 possible actions. This environment is particularly tough because there is no inherent "similarity" between these action sequences.

Key Insights and Ideas

  • The Power of Logarithms: By moving from $A$ to $\log A$, the authors turn the "curse of dimensionality" on its head. In the Maze task with 719 actions, standard methods were essentially impossible to run, while BRCPI handled it with ease.
  • Independence is a Feature, not a Bug: In BRCPI, the sub-policies for each bit are learned independently. While this sounds like it might lose information, the "Error-Correcting" nature of the codes means that if a few sub-policies output noise, the overall system can still identify the correct action.
  • Parallelization: Because the sub-MDPs in BRCPI are independent, they are "embarrassingly parallel," meaning they can be trained simultaneously on multi-core systems or GPUs for even greater speedups.

Key Results

  • Speed: On the Mountain Car task (100 actions), BRCPI was 12.5x faster overall than the standard OVA approach. When looking strictly at simulation time (the biggest bottleneck in RL), it was 23.5x faster.
  • Performance: In the Maze task with 719 actions, standard RCPI-OVA and ERCPI were "intractable" (taking days for a single iteration). BRCPI not only finished in hours but successfully learned a policy that outperformed a random baseline, whereas standard methods failed to find any meaningful signal due to the sparsity of positive examples for each action.
  • Scaling: The complexity results were confirmed: $O(A^2)$ for OVA, $O(A \log A)$ for ERCPI, and $O(\log A)$ for BRCPI.

Limitations and Future Work

  • Code Design: The authors used randomly generated codes. They suggest that "informed" codes—where actions that have similar effects in the environment are assigned similar bit-strings—could lead to even better performance.
  • Sub-optimality: Because BRCPI learns bit-policies independently, the combined global policy is an approximation. There is a theoretical gap in understanding exactly how the error in a sub-policy translates to the sub-optimality of the final agent.
  • Automatic Discovery: A promising future direction is the automatic discovery of these codes during the learning process, rather than pre-defining them.

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 $\mathcal{O}(A^2)$ to $\mathcal{O}(A \log(A))$ . We then propose a novel method that profits from the ECOC’s coding dictionary to split the initial MDP into $\mathcal{O}(\log(A))$ separate two-action MDPs. This second method reduces learning complexity even further, from $\mathcal{O}(A^2)$ to $\mathcal{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},
}

Loading related content...

Figure