PaperlayerView exact revision on arXiv

Source-linked AI summary

Discovering Multiagent Learning Algorithms with Large Language Models

Zun Li, John Schultz, Daniel Hennes, Marc Lanctot

arXiv:2602.16928v3cs.GTcs.AIcs.MA

TL;DR

The paper addresses the manual burden of designing multi-agent learning algorithms for imperfect-information games. It applies AlphaEvolve to search CFR and PSRO design spaces, then distills the resulting algorithms through train-test ablations. The raw discoveries are competitive across 18 games, while minimal distilled solvers improve generalization with lower complexity.

  • Problem

    Manual, iterative refinement has dominated algorithm design for multi-agent reinforcement learning, motivating automated discovery methods for CFR and PSRO.

  • Method

    AlphaEvolve performs LLM-driven evolutionary code search over CFR and PSRO, followed by systematic train-test ablations and distillation of generalizing mechanisms.

  • Results

    VAD-CFR and SHOR-PSRO were consistently competitive with human-designed baselines across an 18-game suite, while WOP-CFR and PM-PSRO achieved superior generalization with reduced complexity.

  • Takeaways & Limitations

    The paper supports using LLM evolutionary search as a proposal mechanism within a human-in-the-loop pipeline that ablates and distills candidate mechanisms.

  • Takeaways & Limitations

    The results reflect a single AlphaEvolve trajectory, and the stability of distilled components across independent runs remains empirically unverified.

Abstract

from arXiv · show

Much of the advancement in Multi-Agent Reinforcement Learning (MARL) for imperfect-information games has historically depended on the manual, iterative refinement of algorithmic baselines. Recently, evolutionary coding agents powered by Large Language Models (LLMs) have emerged as powerful tools to automate this discovery process. In this work, we deploy one of such agentic frameworks, AlphaEvolve, to navigate the design spaces of two distinct game-theoretic paradigms: counterfactual regret minimization (CFR) and policy-space response oracles (PSRO). This automated search yielded two algorithms: Volatility-Adaptive Discounted (VAD-) CFR and Smoothed Hybrid Optimistic Regret (SHOR-) PSRO, which are consistently competitive with state-of-the-art human-designed baselines across an 18-game evaluation suite spanning Poker, Goofspiel, Liar's Dice, Blotto, and Battleship variants. However, because the LLM optimizes for fitness on a specific training set, it often constructs highly synergistic, complex mechanisms tailored to those environments. Through systematic ablation studies, we demonstrate that while these mechanisms are tightly coupled, the true driver of generalization lies in a minimal algorithmic core. By distilling the LLM's discoveries down to their most fundamental principles, we produce two minimal solvers: Warm-started Optimistic Predictive (WOP-)CFR and Projection Matching (PM-)PSRO. These distilled versions achieve superior performance on generalization with greatly reduced structural complexity, providing a clear methodology for using LLMs in algorithmic discovery.

1. Introduction

The paper uses LLM-driven evolutionary search to automate multi-agent algorithm design, discovering competitive CFR and PSRO variants and distilling them into simpler solvers that generalize better.

  • Manual refinement of structural algorithmic choices has historically guided multi-agent reinforcement learning progress.The relevant choices include how regret is discounted and how equilibrium solution concepts are derived.
  • AlphaEvolve uses LLM code generation and semantic evolution to automate algorithm design rather than relying solely on hyperparameter optimization or genetic programming.The algorithm’s source code is treated as the genome, while LLMs mutate and extend its logic.
  • VAD-CFR and SHOR-PSRO were consistently competitive with state-of-the-art human-designed baselines across an 18-game suite spanning five game families.The suite covered Poker, Goofspiel, Liar’s Dice, Blotto, and Battleship variants.
  • Train-test ablations identified specialized mechanisms that improved training fitness but were unnecessary for generalization.The analysis found that evolutionary agents could layer complex logic over foundational discoveries and tailor it to training games.
  • WOP-CFR and PM-PSRO distilled the discoveries into minimal solvers with superior generalization and reduced heuristic complexity.The distilled algorithms retain the fundamental principles while removing over-specialized structure.

2. Game Theoretic Preliminaries

The paper frames imperfect-information multi-agent learning with extensive-form games, exploitability, CFR, and PSRO, emphasizing their strategy representations and iterative update procedures.

  • 2.1. Extensive-Form Games and Exploitability: Extensive-form games represent sequential multi-agent interactions with hidden information through histories, actions, utilities, and information sets.An information set groups histories that a player cannot distinguish, while strategies assign action probabilities at each information set.
  • 2.1. Extensive-Form Games and Exploitability: Exploitability measures the average incentive for players to deviate from a strategy profile to a best response.For small or medium-sized games, exploitability can be computed exactly by traversing the full game tree.
  • 2.2. Counterfactual Regret Minimization (CFR): CFR minimizes counterfactual regret by decomposing global regret minimization into independent local problems at information sets.CFR variants modify regret accumulation, policy derivation, or averaging rules, and the evaluated output is typically an average strategy.
  • 2.3. Policy Space Response Oracles (PSRO): PSRO maintains policy populations and a payoff tensor, then repeatedly solves a meta-game, trains a best-response oracle, and expands the population.The meta-strategy solver produces a distribution over policies, while the oracle generates a new policy against opponents’ meta-strategies.
  • 2.3. Policy Space Response Oracles (PSRO): The study separates training-time and evaluation-time meta-solvers because exploitability requires a meta-strategy distribution over the current population.This separation allows the search to explore unified or asymmetric solver schedules.

3. Automating Algorithm Discovery for Multiagent Learning via LLMs

AlphaEvolve searches modular CFR and PSRO code interfaces, evaluates candidates by exploitability on proxy games, and evolves algorithmic components rather than complete solvers from scratch.

  • AlphaEvolve combines LLM code generation with evolutionary selection across the CFR and PSRO paradigms.Candidates are generated from selected parents, executed on proxy games, and scored by final negative exploitability.
  • The evolutionary loop samples parents by fitness, prompts an LLM to modify their source code, and retains valid candidates in the population.Multi-objective scoring can select different objectives across rounds.
  • CFR discovery exposes regret accumulation, policy derivation, and policy averaging as separate evolvable classes.These interfaces cover how regrets are processed, how strategies are projected from regret, and how policies are accumulated.
  • The CFR search space includes known CFR variants as special cases, including standard CFR’s accumulation and regret-matching components.This lets the evolutionary system explore broad update-rule variations without requiring complete solver generation.
  • PSRO discovery separates training and evaluation meta-strategy solvers to permit dynamic, asymmetric schedules.The interface represents standard baselines such as double oracle while exposing both solver stages to evolution.
  • Training games are scored using final negative exploitability, with algorithms selected according to average scores across the manually chosen game set.For each training game, the score is computed after K iterations, alongside the average across games.

4. Experimental Evaluation

The evaluation tests AlphaEvolve-discovered CFR and PSRO variants on fixed training and held-out games, then uses ablations to distinguish specialized mechanisms from generalizable algorithmic cores. The distilled WOP-CFR and PM-PSRO solvers retain the core mechanisms and improve held-out performance while remaining competitive across the 18-game suite.

  • Evaluation protocol: The evaluation uses four-game training and held-out test sets, with exploitability measured exactly by exhaustive game-tree traversal.The same train-test protocol is used to assess robustness and generalization of both CFR and PSRO discoveries.
  • Ablation methodology: IQM log-improvement scores compare raw and ablated algorithms across train, test, and total splits, with positive values indicating lower exploitability after ablation.The IQM averages the central 50% of scores, trimming the top and bottom 25% of variations.
  • CFR discovery: VAD-CFR ranks in the top three on all 18 games and achieves the lowest exploitability on 15, while maintaining strong training and test performance.It reaches exploitability below 10^-3 in 3-player Leduc Poker, where many baselines plateau higher.
  • CFR ablations: Removing volatility tracking or regret boosting worsens training fit but has marginal held-out effects, whereas removing foundational mechanics causes major performance collapse.The results identify secondary heuristics as in-distribution synergies rather than primary generalization drivers.
  • WOP-CFR distillation: WOP-CFR improves Test IQM by +0.119 over raw VAD-CFR, ranks in the top three on every game, and achieves the lowest exploitability on 14 games.It preserves three foundational mechanics while discarding overfitted training heuristics.
  • PSRO discovery and distillation: SHOR-PSRO performs among the strongest methods on training and test games, while PM-PSRO improves Test IQM by +0.059 and both rank in the top three across all 18 games.PM-PSRO removes annealing schedules, hybrid blending, and complex evaluation logic while retaining its mathematical core.

5. Related Work

Prior work has automated algorithm design through neural meta-learning and symbolic search, but multi-agent approaches have often used constrained search spaces or neural parameterizations that limit interpretability.

  • Meta-learning approaches parameterize update rules with neural networks to optimize learning dynamics.
  • AutoML-Zero established a symbolic approach to discovering machine-learning algorithms.
  • Prior multi-agent algorithm-design methods often used constrained search spaces or neural parameterizations that hindered interpretability.
  • This work builds on AlphaEvolve to use LLMs for semantic mutation in multi-agent algorithm design.

6. Conclusion

The paper applies LLM-driven evolutionary search to CFR and PSRO, evaluates the resulting algorithms against human-designed baselines, and distills them through ablations into simpler solvers. The authors frame the resulting pipeline as human-in-the-loop rather than fully autonomous.

  • LLM-driven evolutionary search discovers algorithms in the CFR and PSRO paradigms.
  • VAD-CFR and SHOR-PSRO are consistently competitive with state-of-the-art human-designed baselines across an 18-game evaluation suite.
  • Systematic train-test ablations distill the discoveries into WOP-CFR and PM-PSRO, which retain or improve generalization with substantially reduced complexity.
  • The reported algorithms reflect a single AlphaEvolve trajectory, and stability across independent evolutionary runs remains empirically unverified.
  • Competitive-performance claims are scoped to the tested tabular baselines and exclude deep CFR and neural auto-curricula PSRO.

7. Appendix

The appendix documents the CFR and PSRO code skeletons and the discovered update mechanisms, including adaptive regret discounting and smoothed strategy construction.

  • CFR code skeleton: The CFR skeleton separates cumulative-regret updates, current-policy derivation, and cumulative-policy averaging into evolvable components.
  • PSRO code skeleton: The PSRO skeleton exposes separate training and evaluation meta-strategy solvers over policy sets and payoff tensors.
  • CFR variants: CFR regret accumulation uses separate positive and negative discount factors with adaptive parameters based on regret volatility.
  • CFR variants: The adaptive-discounting implementation updates volatility estimates and returns positive and negative discount factors for regret accumulation.

Regret Accumulation Variants

The VAD-CFR ablations test whether asymmetric discounting and instantaneous regret boosting are necessary components of the discovered algorithm.

  • The no_asym_discount ablation replaces VAD-CFR’s asymmetric discounting with a symmetric factor by setting base_beta equal to base_alpha.
  • The no_boost ablation removes the exploration-boost mechanism by setting the instantaneous regret boost factor to 1.0.

Policy Accumulation and Strategy Distillation

VAD-CFR ablations test whether nonlinear policy projection and a 500-iteration warm-start are responsible for its behavior. The warm-start ablation begins policy averaging at iteration 1 instead of delaying it.

  • Policy projection: VAD-CFR’s no_predication ablation replaces nonlinear policy projection with standard linear Regret Matching.It sets positive_policy_exponent = 1.0 and removes anticipatory initial optimism.
  • Warm-start: VAD-CFR’s no_warmstart ablation bypasses the warmup_iterations = 500 condition and starts policy averaging at t = 1.This tests whether a burn-in period prevents early high-variance policies from affecting the final average strategy.
  • Ablation design: The ablations isolate nonlinear projection and delayed policy averaging as distinct discovered mechanisms.

Environmental Adaptation

The evaluation spans diverse imperfect-information games and examines how specialized mechanisms, solver design, and adaptation affect generalization. PM-PSRO uses tangent projection with an iteration budget that grows with empirical-game size.

  • SHOR-PSRO adaptation: SHOR-PSRO ablations test train/evaluation asymmetry, blending between ORM+ and a smoothed pure strategy, annealing, diversity, momentum, and gain normalization.The raw discovery uses separate specialized solvers for training-time oracle generation and evaluation-time exploitability measurement.
  • PM-PSRO: PM-PSRO applies tangent projection, uses a regret-matching-style discrete update, and scales inner iterations linearly with empirical-game size.Its solver design tracks population growth and uses a unified time-averaged solver for training and evaluation.
  • Evaluation environment: The 18-game suite spans five game families, with sequential and simultaneous-move settings, 2–4 players, and 2 to 347,810 information states.All games involve imperfect information, and branching factors range from 1 to 66.

7.3.1. Poker Variants

The evaluation includes poker, Goofspiel, Liar’s Dice, and Colonel Blotto variants with differing scales and information structures. These environments range from small canonical poker benchmarks to larger simultaneous or bluffing games.

  • Poker variants: Kuhn Poker is evaluated in 2-player, 3-player, and 4-player forms, ranging from 12 to 160 information states.The variants use progressively larger decks and player counts.
  • Poker variants: Leduc Poker includes a 2-player version with 936 information states and a 3-player variant with 25,800 information states.It remains small enough for exact Nash equilibrium computation while testing key algorithmic properties.
  • Non-poker games: Goofspiel evaluation varies scale across n ∈ {3, 4, 5} cards and compares standard with limited-information observation structures.The resulting game trees range from 114 to 347,810 information states.
  • Non-poker games: Liar’s Dice variants use d ∈ {4, 5, 6} die faces, while Colonel Blotto distributes 10 units across 3 battlefields.These games test bluffing and simultaneous resource-allocation settings.

7.3.5. Battleship

Battleship is evaluated as a parametric two-player imperfect-information game with hidden ship placements and alternating shots. The suite uses two board configurations with different information-state counts.

  • Game setting: Battleship models hidden ship placement, alternating shots, and parameters including board dimensions, ship configurations, and scoring rules.
  • Evaluated configurations: The Battleship 2×2 configuration has 10,198 information states, while Battleship 3×2 has 160,491.Both use one ship of size 2, value 2.0, and allow 3 shots.

7.3.6. Game Selection Rationale

The evaluation suite is designed to stress-test multi-agent learning algorithms across player counts, game-tree scales, strategic depths, move structures, and observability. Additional normal-form-game experiments isolate PSRO meta-solver behavior from extensive-form structure while comparing solvers under identical sampling and reporting conditions.

  • Evaluation suite: Normal-form-game evaluation removes influence from any specific extensive-form structure, testing PSRO meta-solvers in isolation.The experiments sample 1000 games per configuration from Gaussian or Uniform payoff distributions and enforce constant-sum structure.
  • Evaluation suite: The normal-form-game study restricts evaluation to N≥3 because two-player zero-sum games have polynomial-time exact linear-programming solutions.In that regime, the LP-Nash baseline would dominate and provide no signal about meta-solver design choices.
  • Evaluation protocol: PSRO solvers are benchmarked under identical conditions, using one random pure strategy initially, exact best-response expansion, full population growth, and per-iteration IQM exploitability.Confidence intervals are computed with 50,000 run-level bootstrap resamples to preserve within-trajectory correlation.
  • Evaluation protocol: Across Gaussian and Uniform payoff games, SHOR-PSRO and PM-PSRO consistently reach lower exploitability than established baselines, with widening gaps as iterations grow.PM-PSRO starts more slowly for roughly five iterations but matches or surpasses SHOR-PSRO by mid-run in larger configurations.
  • Search design: The discovery process exposes distinct CFR components and separate PSRO training and evaluation solvers as evolvable design spaces.The CFR interface covers regret accumulation, current-policy construction, and average-policy accumulation; PSRO separates oracle-training and evaluation meta-solvers.
Loading 2602.16928v3…