🤖 AI

Discovering Multiagent Learning Algorithms with Large Language Models

This paper demonstrates that Large Language Models can automate the discovery of competitive Multi-Agent Reinforcement Learning algorithms for imperfect-information games, and shows that distilling these complex, environment-specific findings into minimal algorithmic cores yields superior generalization and reduced structural complexity.

Original authors: Zun Li, John Schultz, Daniel Hennes, Marc Lanctot

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zun Li, John Schultz, Daniel Hennes, Marc Lanctot

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a group of robots how to play poker, Go, or even a game of "Liar's Dice." For decades, humans have been the coaches, manually tweaking the robots' brains, trying different math formulas, and hoping they get better. It's a slow, tedious process of trial and error.

This paper describes a new way to coach: instead of a human tweaking the code, the researchers let a Large Language Model (LLM)—a super-smart AI that understands code—act as an evolutionary biologist. They call this system AlphaEvolve.

Here is the story of what they found, broken down into simple concepts.

1. The Evolutionary Lab

The researchers set up a digital "lab" with two different types of game-playing algorithms:

CFR (Counterfactual Regret Minimization): Think of this as a student who learns by looking at every mistake they made and asking, "If I had done something else, would I have won?"
PSRO (Policy-Space Response Oracles): This is like a coach who builds a team of different players, pits them against each other, and constantly adds new, smarter players to the roster to beat the current best.

The LLM was given the source code for these algorithms and told: "Make these better. Reduce the mistakes (exploitability) the robots make."

The LLM didn't just tweak a few numbers; it rewrote the logic of the code itself, mutating the algorithms like DNA. After many generations of "survival of the fittest," the LLM produced two new, highly complex algorithms:

VAD-CFR: A version of the "Regret" student that adapts wildly to how chaotic the game feels.
SHOR-PSRO: A version of the "Team Coach" that mixes different strategies in a very specific, complex way.

2. The "Over-Engineered" Trap

When they tested these new AI-discovered algorithms, they were amazing. They beat all the human-designed champions in the specific games they were trained on.

However, the researchers noticed something suspicious. The LLM had built these algorithms like a master chef creating a dish specifically for one very picky eater. The code was full of complex, tangled mechanisms that worked perfectly for the training games but were likely just "overfitting"—memorizing the training data rather than learning the general rules of the game.

It was like the LLM built a car with a turbocharger, a nitro system, and a special suspension tuned only for a specific racetrack. It would win that track, but if you took it to a bumpy dirt road, it might fall apart.

3. The "Ablation" Surgery (The Detective Work)

To find out what was actually making these algorithms smart, the researchers performed "surgery." They systematically removed parts of the code to see what happened. This is called ablation.

They found that the fancy, complex parts (like tracking volatility or blending strategies in specific ways) were mostly fluff. They helped the algorithm win on the training track, but they didn't help it generalize to new games.

When they stripped away the "fancy dress," they found the bare bones that actually made the engine run.

4. The Distilled Winners

By keeping only the most essential, fundamental principles and throwing away the over-complicated code, they created two new, simpler algorithms:

WOP-CFR (Warm-started Optimistic Predictive CFR):
- The Analogy: Imagine a student who refuses to take notes for the first 500 days of class (a "warm start") to avoid writing down bad habits. Then, they start taking notes, but they are "optimistic"—they assume the next move will be slightly better than it is, which helps them learn faster.
- The Result: This simple version was actually better at generalizing to new games than the complex original. It was less likely to be confused by new situations.
PM-PSRO (Projection Matching PSRO):
- The Analogy: Imagine a coach who ignores the "noise" of the crowd. Instead of looking at every single score, they look at how a player performs relative to the average of the whole team. If a player is below average, they are instantly forgotten. If they are above average, they get the spotlight.
- The Result: This stripped-down version was also superior to the complex original, proving that the LLM's complex blending logic wasn't necessary.

5. The Big Takeaway

The paper concludes that LLMs are great at proposing ideas, but humans are needed to distill them.

The LLM acted like a creative inventor who builds a machine with 500 moving parts. The researchers acted like engineers who realized, "Hey, we only need 3 of these parts to make it work, and removing the other 497 makes it faster and more reliable."

Summary of the Claim:
The researchers successfully used an AI to discover new game-playing algorithms that beat human experts. However, the AI's raw discoveries were too complex and specialized. By surgically removing the unnecessary complexity, they created simpler, cleaner algorithms that were even better at handling new, unseen games. This proves that AI can be a powerful tool for scientific discovery, provided humans are there to simplify and interpret the results.

Technical Summary: Discovering Multiagent Learning Algorithms with Large Language Models

Problem Statement

Historically, advancements in Multi-Agent Reinforcement Learning (MARL) for imperfect-information games have relied on the manual, iterative refinement of algorithmic baselines. Researchers navigate vast combinatorial spaces of update rules and structural choices (e.g., regret discounting, equilibrium derivation) largely through intuition and trial-and-error, often defaulting to mathematically tractable heuristics that may not be optimal. This paper addresses the limitation of manual design by proposing the automation of the algorithm discovery process itself using Large Language Models (LLMs).

Methodology

The authors deploy AlphaEvolve, a distributed evolutionary coding agent powered by LLMs (specifically Gemini 2.5 Pro), to automate the design of MARL algorithms. The framework treats the source code of an algorithm as a genome, using the LLM as an intelligent genetic operator to perform semantic mutations, rewrite logic, and inject novel symbolic operations.

The study focuses on two distinct game-theoretic paradigms:

Counterfactual Regret Minimization (CFR): The search space is defined by three evolvable Python classes: RegretAccumulator (how regrets are processed/discounted), PolicyFromRegretAccumulator (how policies are derived from regrets), and PolicyAccumulator (how policies are weighted for the final average).
Policy-Space Response Oracles (PSRO): The search space involves two separate, evolvable classes: TrainMetaStrategySolver (for generating meta-strategies during oracle training) and EvalMetaStrategySolver (for computing strategy profiles for evaluation). This separation allows the LLM to discover dynamic, asymmetric schedules between training and evaluation.

Experimental Protocol:

Training Set: Algorithms are evolved on a set of four games (3-player Kuhn Poker, 2-player Leduc Poker, 4-card Goofspiel, 5-sided Liar's Dice) to maximize fitness (negative exploitability).
Evaluation: The fixed, evolved algorithms are tested on a broader suite of 18 games, including larger variants and different game families (Poker, Goofspiel, Liar's Dice, Blotto, Battleship).
Distillation via Ablation: Recognizing that LLMs may overfit by layering complex, synergistic mechanisms on top of core principles, the authors employ a rigorous train-test split ablation methodology. They use the Interquartile Mean (IQM) of log-improvement scores to isolate which components drive generalization versus those that merely maximize training fitness.

Key Contributions

1. Discovery of High-Performance Algorithms

The evolutionary search successfully discovered two novel algorithms that are competitive with state-of-the-art human-designed baselines:

VAD-CFR (Volatility-Adaptive Discounted CFR): A CFR variant featuring adaptive discounting based on volatility tracking, instantaneous regret boosting, and optimistic prediction.
SHOR-PSRO (Smoothed Hybrid Optimistic Regret PSRO): A meta-solver blending Optimistic Regret Matching+ (ORM+) with smoothed best pure strategies, utilizing asymmetric solvers for training and evaluation.

2. Identification of Over-Specialization

Through systematic ablation studies, the paper demonstrates that while the raw LLM discoveries are highly effective on training distributions, they often contain "over-engineered" components (e.g., specific volatility tracking, complex blending schedules) that are tightly coupled to the training set but do not contribute to generalization. In some cases, these complex mechanisms act as generalization penalties.

3. Distillation of Minimal Solvers

By stripping away the over-specialized heuristics and retaining only the foundational structural shifts identified in the ablation studies, the authors produce two minimal, mathematically pure solvers:

WOP-CFR (Warm-started Optimistic Predictive CFR): This distilled version retains three core mechanics from VAD-CFR:
1. Hard Warm-Start: A strict 500-iteration suspension of policy averaging to prevent early high-variance noise from polluting the cumulative strategy.
2. Extreme Asymmetric Discounting: Using a negative exponent ( $\beta = -0.1$ ) for negative regrets to act as an instantaneous "forget-gate," decaying them faster than human-tuned baselines.
3. Optimistic Prediction: Deriving policies via a non-linear projection (exponent 1.5) with a decaying optimism factor.
  Result: WOP-CFR achieves superior generalization (higher Test IQM) than the raw VAD-CFR while significantly reducing structural complexity.
PM-PSRO (Projection Matching PSRO): This distilled version replaces the complex hybrid blending and annealing schedules of SHOR-PSRO with a single core mechanism:
1. Tangent-Projected Utility: Replacing the regret signal in Regret Matching with the tangent projection of the expected utility vector (centering utilities by the population mean).
2. Dynamic Budget: Scaling the inner solver iterations linearly with the empirical game size.
3. Unified Solver: Using a time-averaged solver for both training and evaluation.
  Result: PM-PSRO outperforms the raw SHOR-PSRO on generalization tasks with a simplified, interpretable structure.

Results

Performance: Both the raw discoveries (VAD-CFR, SHOR-PSRO) and the distilled minimal solvers (WOP-CFR, PM-PSRO) consistently rank in the top three across an 18-game evaluation suite.
Generalization: The distilled solvers often outperform their raw LLM counterparts on held-out test games. For instance, WOP-CFR achieves the lowest exploitability on 14 of the 18 games, compared to 15 for the raw VAD-CFR, but with a +0.119 Test IQM improvement over the raw version. Similarly, PM-PSRO shows a +0.059 Test IQM improvement over SHOR-PSRO.
Robustness: The distilled algorithms maintain high performance across diverse game families (Poker, Goofspiel, Liar's Dice, Blotto, Battleship) and varying scales (from 2 to 347,810 information states).
Random NFGs: In evaluations on randomly generated $N$ -player normal-form games, both SHOR-PSRO and PM-PSRO dominate established baselines (Uniform, AlphaRank, PRD, RM), with the performance gap widening as iterations increase.

Significance and Claims

The paper claims that LLM-driven evolutionary search is a powerful proposal mechanism for algorithmic discovery, but it is most effective when embedded in a human-in-the-loop pipeline. The LLM proposes complex candidate combinations of mechanisms, but systematic train-test ablation is required to surface which components truly generalize. The researcher then distills these survivors into minimal solvers.

The authors emphasize that their work bridges the gap between expressive neural meta-learning and symbolic discovery by evolving interpretable code skeletons. They explicitly state that their results do not provide formal convergence guarantees for the distilled algorithms (which are empirically motivated rather than theoretically proven) and that the evaluation is restricted to tabular-based baselines and games with less than 350k information states due to the requirement for exact exploitability computation. The study concludes that the true value of the LLM lies in its ability to navigate design spaces to find non-intuitive mechanisms, which can then be simplified into robust, generalizable algorithms.