Abstract
In complex environments like Real-Time Strategy (RTS) games, the action space is so vast that standard Reinforcement Learning (RL) fails to converge within practical timeframes. This paper demonstrates that learning to select from a pool of specialized algorithms (scripts) is often superior to learning raw actions. We provide a theoretical framework for when this "algorithm selection" pays off and empirical proof by dominating state-of-the-art players in $\mu$RTS.
Introduction: The Curse of Dimensionality
Reinforcement learning agents typically learn a mapping from states to actions. While successful in games like Chess or Go, this approach falters in Real-Time Strategy games where an agent might face over $10^{50}$ possible actions in a single state. Exploring this space is computationally impossible for standard RL.
Many domains already possess "scripts" or specialized algorithms designed by experts for specific tasks (e.g., "rush" strategies). This creates a dilemma: should an agent spend limited training time discovering optimal atomic actions from scratch, or learn to pick the best pre-existing algorithm? This study quantifies when "learning over algorithms" is the superior strategy.
Theoretical Framework: Actions vs. Algorithms
The researchers model two types of agents: $P_1$ (learning over actions) and $P_2$ (learning over algorithms). Theorem 1 derives a sufficient condition showing that $P_2$ outperforms $P_1$ for a finite number of iterations if at least one algorithm in the pool is "strong enough" relative to the ratio of the number of algorithms ($|X|$) to the number of actions ($|A|$).
As the action space ($|A|$) grows, the quality requirement for algorithms to beat raw action learning drops significantly. In massive spaces, even mediocre algorithms outperform random exploration for a long duration.
The Meeting Point ($\tau$)
A central concept in this study is the "meeting point" ($\tau$)—the moment in training when learning raw actions finally catches up to and surpasses learning over algorithms.
While learning over actions is eventually optimal (as algorithms are "one-step options" that may not contain the true optimal policy), the time it takes to reach that optimality ($\tau$) can be so large that it is practically irrelevant for complex games.
Scaling and Complexity
To validate the theory, synthetic experiments using single-state Markov Decision Processes (MDPs) were conducted. Rewards and algorithm quality were sampled from Uniform and Gaussian distributions.
The results show that the meeting point $\tau$ grows exponentially with the problem size ($|A|$). This suggests that for real-world large-scale problems, learning over actions may never realistically catch up to learning over algorithms within a feasible training budget. Interestingly, adding more algorithms ($|X|$) increases the complexity of the selection task, potentially hurting initial performance unless the new algorithms are diverse and strong.
Empirical Validation in $\mu$RTS
The authors implemented a practical agent for $\mu$RTS, a high-performance simulator for RTS research. Instead of raw actions, the agent chooses between six scripts (e.g., Worker Rush, Build Barracks). Using SARSA with linear function approximation, the agent represented game states through features like unit counts and health.
The proposed agents, Specific and Nemesis, achieved win rates higher than 80% against all state-of-the-art opponents, including AHTN, PuppetMCTS, and the 2017 competition winner, StrategyTactics. Unlike previous work that chose one script for an entire match, this approach allows dynamic switching at any state, enabling highly adaptive behavior.
Conclusion
This study highlights that in large-scale RL, the choice of representation—algorithms versus actions—is critical. While algorithm selection is limited by the quality of the provided "building blocks," its efficiency in massive action spaces makes it a powerful tool for complex environments. Future work may focus on "algorithm creation"—automatically generating the scripts that the high-level agent then learns to select.
Summary updated