This paper explores a fascinating intersection between Reinforcement Learning (RL) and Theoretical Computer Science (TCS). While RL is frequently deployed to solve complex games or continuous control robotics tasks, the authors ask a more fundamental question: Can RL rediscover the "classic" algorithms that human researchers spent decades deriving?
By training on carefully constructed "adversarial" data distributions, researchers successfully trained RL agents to rediscover theoretically optimal algorithms for classic online optimization problems. The agents learned robust, "uniform" strategies that generalize to any input length—essentially finding the same "pen-and-paper" solutions used in traditional computer science.
Bridging the Gap: Uniformity and Worst-Case Performance
In traditional algorithm design, computer scientists seek uniform algorithms: a single piece of logic that works reliably regardless of whether the input size is 10 or 10 million. However, most Machine Learning models are non-uniform. They are often brittle, heavily tied to the specific input dimensions or sequence lengths they observed during training.
Furthermore, ML usually optimizes for average-case performance on a specific dataset. In contrast, TCS focuses on worst-case performance (often measured by the competitive ratio). The authors aimed to determine if RL could bridge this gap, learning strategies that are both independent of input length and robust against adversarial inputs.
Framing Classic Problems as MDPs
The authors framed three classic online optimization problems as Markov Decision Processes (MDPs):
- AdWords (Online Matching): Allocating ad slots to advertisers with limited budgets.
- Online Knapsack: Deciding whether to accept or reject items to maximize value without exceeding a weight limit.
- Secretary Problem: Selecting the single best candidate from a sequence of unknown values.
To force the RL agent to find "classic" optimal strategies rather than lazy heuristics, they introduced key training techniques:
- Adversarial Distributions: Training sets were based on "Universal Training Sets" (derived from Yao’s Lemma), mathematically designed to be the "hardest" possible inputs for any algorithm.
- High-Entropy Training: Using distributions with high variance prevented the agent from "cheating" by memorizing specific sequence patterns.
- Relative State Representation: To achieve "uniformity," the agents were fed relative features (e.g., "fraction of budget remaining" instead of "dollars remaining"). In some cases, the state was augmented with histograms of past inputs.
Instead of static datasets, the researchers utilized synthetic procedural generators. For AdWords, they used "Adversarial" and "Thick-z" graphs designed to defeat greedy strategies. Knapsack items were drawn from uniform and custom "X vs Y" distributions to test thresholding logic, while the Secretary problem used binary, percentile, and i.i.d. value sequences.
Key Insights and Results
The RL agents didn't just solve the problems; they effectively "became" the classic algorithms. The authors noted a deep connection between the Online Primal-Dual framework (a staple of TCS) and RL. The way an RL agent learns to value its resources (like budget or knapsack space) mirrors how classic algorithms update "dual variables" to make decisions.
- Secretary Problem: The agent perfectly rediscovered the theoretical 1/e rule (waiting for the first 37% of candidates before picking), achieving performance nearly identical to the mathematical optimum.
- Online Knapsack: The agent learned a "Bang-per-Buck" thresholding strategy, automatically adjusting its acceptance criteria based on the remaining capacity and time.
- AdWords: The models successfully learned the Balance and MSVV strategies, which are the gold standards for online budgeted allocation.
- Extreme Scaling: Because the agents learned generalized policy curves through relative state representations, an agent trained on sequences of length 100 was able to maintain its performance when tested on sequences of 1,000,000 items, proving it had learned a truly uniform algorithm.
Limitations and Future Work
While groundbreaking, the approach has limitations. In some cases (like the Knapsack problem), the agent couldn't find the optimal strategy without a "hint" in the form of a histogram of past items. Future work aims to develop agents that can learn to maintain these memory summary statistics on their own.
Additionally, while the authors "decoded" the network by plotting its decision boundaries, the process of converting a trained neural network back into human-readable code remains manual. Finally, this study focused on problems where the optimal algorithm is relatively simple; it remains to be seen if RL can find optimal strategies for problems requiring complex data structures.
Summary updated