Paper deep dive
Discovering Multiagent Learning Algorithms with Large Language Models
Zun Li, John Schultz, Daniel Hennes, Marc Lanctot
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 7/21/2026, 12:56:55 AM
Summary
This paper introduces a methodology for discovering multi-agent reinforcement learning algorithms using Large Language Models (LLMs) via the AlphaEvolve framework. The authors automated the design of Counterfactual Regret Minimization (CFR) and Policy-Space Response Oracles (PSRO) algorithms, resulting in complex variants VAD-CFR and SHOR-PSRO. Through ablation studies, they identified that these LLM-discovered algorithms overfit to training games. By distilling the core mechanisms, they produced minimal, highly generalizable solvers: WOP-CFR and PM-PSRO, which outperform state-of-the-art baselines in generalization while maintaining structural simplicity.
Entities (13)
Relation Signals (11)
AlphaEvolve → discovers → SHOR-PSRO
confidence 95% · This automated search yielded two algorithms: ... Smoothed Hybrid Optimistic Regret (SHOR-) PSRO
AlphaEvolve → discovers → VAD-CFR
confidence 95% · This automated search yielded two algorithms: Volatility-Adaptive Discounted (VAD-) CFR
VAD-CFR → distilledto → WOP-CFR
confidence 95% · By distilling the LLM’s discoveries down to their most fundamental principles, we produce two minimal solvers: ... WOP-)CFR
SHOR-PSRO → distilledto → PM-PSRO
confidence 95% · ...we produce two minimal solvers: ... and Projection Matching (PM-)PSRO.
WOP-CFR → implements → CFR
confidence 95% · Warm-started Optimistic Predictive (WOP-)CFR
PM-PSRO → implements → PSRO
confidence 95% · Projection Matching (PM-)PSRO
AlphaEvolve → evaluateson → Leduc Poker
confidence 90% · evaluation suite spanning... Leduc Poker
AlphaEvolve → evaluateson → Kuhn Poker
confidence 90% · evaluation suite spanning Poker... 3-player Kuhn Poker
WOP-CFR → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2602.16928v3
- Canonical: https://arxiv.org/abs/2602.16928v3
Trouble viewing inline? Open PDF directly →
Full Text
113,591 characters extracted from source content.
Expand or collapse full text
2026-5-11 Discovering Multiagent Learning Algorithms with Large Language Models Zun Li 1 , John Schultz 1 , Daniel Hennes 1 and Marc Lanctot 1 1 Google DeepMind 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. Keywords: Multi-Agent Reinforcement Learning, Game Theory, Large Language Models, Meta-Learning 1. Introduction The field of Multi-Agent Reinforcement Learning has achieved remarkable milestones in recent years, reaching superhuman performance in domains ranging from Poker to real-time strategy games. These advances have been driven by a diverse array of methods, including game-theoretic regret minimization (Brown and Sandholm, 2019a) and population-based league training (Vinyals et al., 2019). The practical performance of these algorithms relies heavily on specific structural choices—such as how regret is discounted over time or how a specific equilibrium solution concept is derived. Historically, the refinement of these choices has been a largely manual endeavor. Researchers must rely on intuition and trial-and-error to navigate a vast combinatorial space of potential update rules, often defaulting to mathematically tractable heuristics (e.g., linear averaging or fixed discounting) that may not be optimal. In this work, we propose to overcome this limitation by automating the design process itself with Large Language Models (LLMs). We apply AlphaEvolve (Novikov et al., 2025), a distributed evolutionary system powered by LLMs, to the domain of multi-agent learning. Unlike traditional hyperparameter optimization or genetic programming, AlphaEvolve leverages the code-generation capabilities of LLMs to perform semantic evolution. By treating the algorithm’s source code as the genome, the system uses LLMs to act as intelligent genetic operators—performing mutation to rewrite logic, introduce new control flows, and inject novel symbolic operations. This allows to search beyond simple parameter tuning and discover new non-intuitive mechanisms for equilibrium finding. This Corresponding author(s): lizun@google.com © 2026 Google DeepMind. All rights reserved arXiv:2602.16928v3 [cs.GT] 7 May 2026 Discovering Multiagent Learning Algorithms with Large Language Models automated search initially yielded two highly performant variants: Volatility-Adaptive Discounted (VAD-)CFR and Smoothed Hybrid Optimistic Regret (SHOR-)PSRO, both consistently competitive with state-of-the-art human-designed baselines across an 18-game suite covering five game families. However, our analysis reveals that evolutionary agents can layer complex, specialized logic over foundational discoveries to maximize fitness on specific training games. For example, the namesake volatility-tracking in VAD-CFR operates in tight conjunction with regret boosting; while highly effective on training games, this complexity is unnecessary for generalization. To isolate the fundamental principles driving performance, we conduct systematic train-test split ablation studies. By distilling the algorithm down to its most important core components, we introduce two minimal, mathematically pure solvers: Warm-started Optimistic Predictive (WOP-)CFR and Projection Matching (PM-)PSRO. These distilled variants achieve superior generalization while reducing the heuristic complexity present in the raw discoveries. Our main contributions are threefold: (1) We demonstrate that LLM-driven evolutionary search can navigate the design spaces of two distinct multi-agent learning paradigms (CFR and PSRO) to discover algorithms — VAD-CFR and SHOR-PSRO, which are consistently competitive with state-of- the-art human-designed baselines across an 18-game evaluation suite. (2) Through rigorous train-test ablations, we identify how LLMs construct specialized mathematical complexity to overfit algorithmic structures to their training distributions. (3) We introduce WOP-CFR and PM-PSRO—succinct, highly interpretable algorithms that strip away over-specialized complexity to achieve competitive empirical performance compared to their raw LLM counterparts. 2. Game Theoretic Preliminaries We formulate our problem within the framework of Extensive-Form Games (EFGs) with imperfect information, which models sequential interactions involving multiple agents and hidden information. 2.1. Extensive-Form Games and Exploitability An푁-player extensive-form game isΓ= ⟨N,H,Z,A,푢,I⟩, whereN=1, . . . , 푁denotes the set of players (Shoham and Leyton-Brown, 2008).His the set of all possible histories (sequences of actions), whereZ ⊆ Hrepresents terminal histories. For푖 ∈N, letH 푖 ⊆ 퐻represent the subset of histories where player푖acts. For any non-terminal historyℎ,A(ℎ)is the set of legal actions. The utility function푢 푖 :Z → ℝassigns a payoff to player푖at a terminal node. Crucially, imperfect information is modeled via Information Sets퐼 ∈I 푖 . Specifically,I 푖 partitions the historiesH 푖 such that player푖cannot distinguish between historiesℎ, ℎ ′ ∈ 퐼(e.g., due to hidden cards). It is required thatA(ℎ)= A(ℎ ′ ) for allℎ, ℎ ′ ∈ 퐼 , so for simplicity we denote the legal actions at퐼,A(퐼). A strategy (or policy)휎 푖 (퐼)assigns a probability distribution over actions푎∈ A(퐼)for each information set. A strategy profile휎= (휎 1 , . . . , 휎 푁 )determines the expected utility푢 푖 (휎). A Nash Equilibrium (NE) is a strategy profile휎 ∗ such that no player can increase their utility by deviating unilaterally: 푢 푖 (휎 ∗ 푖 , 휎 ∗ −푖 ) ≥ 푢 푖 (휎 ′ 푖 , 휎 ∗ −푖 ) ∀휎 ′ 푖 ,∀푖 ∈ N. To measure the performance of our evolved algorithms, we use Exploitability. The exploitability of a strategy profile휎is the average of the incentives for players to deviate to their Best Response (BR):Expl(휎)= 1 푁 Í 푖∈N max 휎 ′ 푖 푢 푖 (휎 ′ 푖 , 휎 −푖 )− 푢 푖 (휎) . In small or medium-sized games, we can compute this value exactly by traversing the full game tree. 2.2. Counterfactual Regret Minimization (CFR) CFR is an iterative algorithm that minimizes counterfactual regret (Zinkevich et al., 2007). It decomposes the global regret minimization problem into independent local regret minimization 2 Discovering Multiagent Learning Algorithms with Large Language Models problems at each information set. Let휋 휎 (ℎ)be the probability of reaching historyℎunder strategy profile휎. We define휋 휎 −푖 (ℎ)as the contribution of all players except푖(including chance) to reaching ℎ. The counterfactual value of player푖reaching information set퐼and playing action푎is the expected utility given that player푖played to reach퐼:푣 푖 (휎, 퐼, 푎)= Í ℎ∈퐼 휋 휎 −푖 (ℎ) Í 푧∈Z,ℎ⊏푧 휋 휎 (푧 | ℎ, 푎)푢 푖 (푧). The instantaneous counterfactual regret for not playing action푎at iteration푡is the difference between the counterfactual value of action푎and the expected value at퐼:푟 푡 푖 (퐼, 푎)= 푣 푖 (휎 푡 , 퐼, 푎) − Í 푎 ′ ∈A(퐼) 휎 푡 푖 (퐼, 푎 ′ )푣 푖 (휎 푡 , 퐼, 푎 ′ ). Standard CFR accumulates these values linearly over iterations 푇: 푅 푇 푖 (퐼, 푎)= 푇 ∑︁ 푡=1 푟 푡 푖 (퐼, 푎)(1) The current policy휎 푡+1 푖 is derived from accumulated regret, typically using Regret Matching (RM), which assigns probabilities proportional to positive regret: 휎 푡+1 푖 (퐼, 푎)= max(푅 푡 푖 (퐼, 푎), 0) Í 푎 ′ max(푅 푡 푖 (퐼, 푎 ′ ), 0) (2) The strategy휎 푡 푖 at any single iteration may not converge to NE. Instead, CFR outputs the average strategy ̄휎 푇 푖 , computed by weighting the iteration strategy휎 푡 푖 by the player’s contribution to the reach probability휋 휎 푡 푖 (퐼) . Several variants modify these update rules. For example, CFR+ (Tammelin, 2014) replaces the regret accumulation푅 푡 푖 with floor boundingmax(푅 푡−1 푖 + 푟 푡 푖 , 0)and uses linear averaging weights (푤 푡 = 푡) for the average policy. Our work uses AlphaEvolve to search for optimal variations of these accumulation and derivation functions. 2.3. Policy Space Response Oracles (PSRO) PSRO (Bighashdel et al., 2024; Lanctot et al., 2017) acts as a meta-solver that generalizes the Double Oracle algorithm (McMahan et al., 2003). It operates on a higher level of abstraction called the Meta-Game (or Empirical Game (Wellman et al., 2025)). PSRO maintains a population of policiesΠ 푖 =휎 1 푖 , . . . , 휎 푘 푖 for each player. The meta-game is represented by a payoff tensor푀, where entries푀 푗 1 ...푗 푁 푖 = 푢 푖 (휎 푗 1 1 , . . . , 휎 푗 푁 푁 )correspond to the expected utility of player푖when policies from the population are pitted against each other. At each epoch 푘, the algorithm performs three steps: 1.Meta-Strategy Solver (MSS) at training-time: A solver computes a meta-strategy휙 푖 (a probability distribution over the populationΠ 푖 ). Common solvers include Uniform휙 푗 푖 푖 =1/|Π 푖 |and Nash휙which is a Nash Equilibrium of the current meta-game 푀. 2.Oracle (Best Response): A new policy휎 푘+1 푖 is trained via Reinforcement Learning (or exact solving) to be a Best Response to the opponent’s meta-strategy:휎 푘+1 푖 ∈ argmax 휎 푖 피 휎 −푖 ∼휙 −푖 [ 푢 푖 (휎 푖 , 휎 −푖 ) ] . In this work, we utilize an exact oracle that computes the optimal best response to the meta-strategy, isolating the performance of the meta-solver from the variance of reinforcement learning. 3.Expansion: The new policy is added to the populationΠ 푖 ←Π 푖 ∪휎 푘+1 푖 , and the payoff tensor푀 is updated. In this work, we calculate the exact expected payoff value for each entry푀 푗 1 ...푗 푁 푖 , thereby eliminating the stochastic noise associated with Monte Carlo sampling. To quantify performance, exploitability must be calculated using a meta-strategy distribution over the current population. Standard PSRO typically relies on a single, fixed meta-solver (e.g., Uniform or Nash) for both the training-time oracle generation and the evaluation-time metric calculation. By exposing both the training and evaluation solvers as completely separate, evolvable classes, we allow AlphaEvolve to explore whether unified mathematical frameworks or decoupled, asymmetric schedules yield optimal learning dynamics. 3 Discovering Multiagent Learning Algorithms with Large Language Models 3. Automating Algorithm Discovery for Multiagent Learning via LLMs We utilize AlphaEvolve (Novikov et al., 2025), an evolutionary coding agent that leverages Large Language Models (LLMs) to automate the design of multi-agent learning algorithms. We apply this framework to two distinct paradigms: Regret Minimization (CFR) and Population-based Training (PSRO). 3.1. The AlphaEvolve Framework AlphaEvolve combines LLM code generation with evolutionary selection. We initialize a population P with the standard implementation of the baseline algorithm (e.g., CFR or Uniform PSRO). In each generation, a parent퐴 ∈P is sampled by fitness; AlphaEvolve supports multi-objective scoring, so one objective is randomly selected per round and parents are sampled in favor of high values on that objective. The parent’s source code is fed to an LLM (Gemini 2.5 Pro (Comanici et al., 2025)) with the prompt "Modify the following code to improve fitness (reduce exploitability)," yielding a candidate 퐴 ′ . The candidate is executed on a set of proxy games and scored by final negative exploitability; valid candidates are added to P and the loop repeats. 3.2. Evolving Regret Minimization Code To discover novel variants of Counterfactual Regret Minimization (CFR) without constraining the evolutionary agent to predefined mathematical structures, we expose the algorithm’s core update loop as the search space. Rather than prompting the LLM to write an entire solver from scratch, we extract the CFR framework into three distinct, evolvable Python classes with fixed function signatures in Listing 1 in the Appendix: 1. RegretAccumulator : Dictates how instantaneous counterfactual regrets are processed, dis- counted, or bounded before being added to the historical cumulative regret. 2. PolicyFromRegretAccumulator: Defines the projection mechanism (e.g., Regret Matching) used to derive the current iteration’s strategy from the accumulated regrets. 3. PolicyAccumulator : Determines how the current iteration’s policy is weighted and absorbed into the final average strategy used for evaluation. This search space is expressive enough to encompass the entire family of known CFR variants as special cases; for instance, standard CFR uses eq (1) forRegretAccumulatorand eq (2) for PolicyFromRegretAccumulator. 3.3. Evolving Meta-Strategy Solvers Code For PSRO, we evolve python classesTrainMetaStrategySolverfor generating the mixed strategies used during the oracle training phase, andEvalMetaStrategySolverfor computing a strategy profile over population to report exploitability. This interface (Listing 2 in the Appendix) supports the representation of all standard baselines as special cases: for example, standard double oracle algorithm solves for a Nash equilibrium in theget_meta_strategymethod for both solver classes. By exposing the training and evaluation steps as two completely separate, evolvable Python classes, we grant the LLM the maximum degree of freedom to discover dynamic, asymmetric schedules between training and evaluation. 4 Discovering Multiagent Learning Algorithms with Large Language Models 02505007501000 CFR Iteration 10 16 10 14 10 12 10 10 10 8 10 6 10 4 10 2 10 0 Exploitability Kuhn Poker (Players=3) 02505007501000 CFR Iteration 10 5 10 4 10 3 10 2 10 1 10 0 Leduc Poker 02505007501000 CFR Iteration 10 16 10 14 10 12 10 10 10 8 10 6 10 4 10 2 10 0 Goofspiel (Num Cards=4) 02505007501000 CFR Iteration 10 6 10 5 10 4 10 3 10 2 10 1 10 0 Liars Dice (Dice Sides=5) Training Games Performance CFRCFR PLUSLCFRDCFRPCFR PLUSDPCFR PLUSHS PCFR PLUS 30VAD CFRWOP CFR 02505007501000 CFR Iteration 10 16 10 13 10 10 10 7 10 4 10 1 Exploitability Kuhn Poker (Players=4) 02505007501000 CFR Iteration 10 4 10 3 10 2 10 1 10 0 Leduc Poker (Players=3) 02505007501000 CFR Iteration 10 4 10 3 10 2 10 1 10 0 Goofspiel (Num Cards=5) 02505007501000 CFR Iteration 10 4 10 3 10 2 10 1 10 0 Liars Dice (Dice Sides=6) Test Games Performance CFRCFR PLUSLCFRDCFRPCFR PLUSDPCFR PLUSHS PCFR PLUS 30VAD CFRWOP CFR Figure 1 | CFR variants performances. 3.4. Meta-Training Objective We manually select a setG 푡푟푎푖푛 of training games for AlphaEvolve to compute|G 푡푟푎푖푛 |+1 fitness scores. These are the negative exploitability−Expl(퐴(푔) 퐾 )of the final strategy profile after퐾iterations for each 푔 ∈ G 푡푟푎푖푛 , as well as their average − 1 |G 푡푟푎푖푛 | ∑︁ 푔∈G 푡푟푎푖푛 Expl(퐴(푔) 퐾 ). Here퐴(푔) 퐾 denotes the strategy produced by algorithm퐴on game푔at iteration퐾. The reported algorithms are selected based on their average scores. 4. Experimental Evaluation 4.1. Experimental Setup To test the robustness and generalizability of the algorithms we discover, we adopted a rigorous evalu- ation protocol involving two distinct sets of games. The algorithm’s architecture and hyperparameters were developed and tuned on a Training SetG 푡푟푎푖푛 of four games. For both CFR and PSRO discoveries, we choose this set to be 3-player Kuhn Poker, 2-player Leduc Poker, 4-card Goofspiel, and 5-sided Liars Dice. Subsequently, the fixed algorithm was evaluated on a Test SetG 푡푒푠푡 . In the main body of this paper, we present results on four larger and more difficult games as a representative subset of test games: 4-player Kuhn Poker, 3-player Leduc Poker, 5-card Goofspiel, and 6-sided Liar’s Dice. The results of a full-sweep of four training games and fourteen test games are provided in Appendix 7.4. We utilized the OpenSpiel (Lanctot et al., 2019) framework for all experiments. For all experiments 5 Discovering Multiagent Learning Algorithms with Large Language Models Table 1|Ablation of VAD-CFR Components. Results are reported as IQM Log-Improvement Scores (푠 푔 ). A negative score of an individual ablation indicates that removing the component degrades performance. VariantTotal IQM 풔 풕풐풕풂풍 Train IQM 풔 풕풓풂풊풏 Test IQM 풔 풕풆풔풕 WOP-CFR (Distilled)-0.073-0.802+0.119 Individual VAD-CFR Ablations: no_volatility-0.120-0.842-0.029 no_boost-0.275-0.954-0.204 no_predication-1.584-7.029-0.905 no_asym_discount-1.637-4.192-1.065 no_warmstart-2.733-5.256-2.003 we use a uniform policy as the initial point. Our implementation of AlphaEvolve is backboned by Gemini 2.5 pro (Comanici et al., 2025). All evaluated algorithms are fully deterministic and metrics are computed exactly by exhaustively traversing the game-tree. 4.2. Ablation Methodology AlphaEvolve may exhibit a tendency to over-engineer solutions, interleaving profound algorithmic discoveries with symbolic complexity. To rigorously isolate the true engines of performance from these over-specialized heuristics, we introduce a comprehensive algorithmic auditing pipeline via train-test split ablations. We adopt the Interquartile Mean (IQM) (Agarwal et al., 2021; Oh et al., 2025), a robust statistical aggregator that is highly resistant to outlier domains. For a given set of gamesG, letExpl (푔) raw andExpl (푔) abl denote the final exploitability of the raw LLM algorithm and its ablated counterpart on game푔 ∈ G, respectively. We first define the log-improvement score푠 푔 for each game:푠 푔 = log 10 Expl (푔) raw − log 10 Expl (푔) abl . Under this formulation, a positive score푠 푔 >0 indicates that the ablated (simplified) algorithm achieves lower exploitability than the raw discovery, identifying the removed component as an over-parameterized generalization penalty. Conversely, a negative score푠 푔 <0 indicates a degradation in performance. To aggregate these scores across the diverse game tasks, the IQM computes the mean of the central 50% of the scores, systematically trimming the top 25% and bottom 25% of extreme variations. To isolate generalization effects, we report the IQM across three distinct splits: Train IQM (onG 푡푟푎푖푛 ) serves as our primary diagnostic for overfitting, Test IQM (onG 푡푒푠푡 ) acts as our ultimate metric for generalization, and Total IQM provides a global measure of algorithmic robustness across all evaluated domains. 4.3. Experimental Evaluation: Discovering and Distilling State-of-the-Art CFR The evolutionary search over the CFR design space yielded a remarkably sophisticated algorithm we term Volatility-Adaptive Discounted (VAD-)CFR, whose source code is provided in Listing 3. We benchmarked evolved VAD-CFR against a suite of state-of-the-art regret minimization algorithms: standard CFR (Zinkevich et al., 2007), CFR+ (Tammelin, 2014), Linear CFR (LCFR), Discounted CFR (DCFR) (Brown and Sandholm, 2019b), Predictive CFR+ (PCFR+) (Farina et al., 2021), Discounted Predictive CFR+ (DPCFR+) (Xu et al., 2024b), and a Hyperparameter Schedule-powered PCFR variant HS-PCFR+(30) (Zhang et al., 2026). Performance was quantified using exploitability (measured on a logarithmic scale) over a fixed horizon of퐾=1000 iterations. We use CFR+ as the seed program. The prompt we use is shown in Listing 7 in the Appendix. 6 Discovering Multiagent Learning Algorithms with Large Language Models As shown in Figure 1, VAD-CFR ranks among the top performers across both the training set and the test set. For 3-player Kuhn Poker, VAD-CFR achieves significantly lower exploitability than all baselines. For Leduc Poker and 4-card Goofspiel, the algorithm maintains a steeper convergence slope compared to DPCFR+ and other state-of-the-art variants. In 5-sided Liars Dice, VAD-CFR exhibits robust performance, effectively managing the larger state space through its adaptive discounting and boosting mechanisms. Results illustrated in test games highlight its generalization. In 3-player Leduc Poker, VAD-CFR reaches exploitability levels below 10 −3 while most baselines plateau at higher levels. In 6-sided Liar’s Dice, VAD-CFR continues to match established baselines like DCFR, suggesting that its evolved mechanisms for managing regret scaling and noise are highly effective across different tasks. Overall, VAD-CFR demonstrates efficient convergence rate and generalization across a broad variety of domains: as shown in Figure 3 in the Appendix, compared with baselines, VAD-CFR ranks in the top three on every one of the 18 games, and achieves the lowest exploitability on 15 of them. 4.3.1. Identifying Foundational Mechanics The raw VAD-CFR discovery (Listing 3) operates as a highly synergistic ecosystem of update rules. To isolate the true engines of performance from the LLM’s over-specialized heuristics, we conducted individual feature ablations using our IQM log-improvement score (푠 푔 ). The details of all ablations are in Appendix 7.2.1. Crucially, removing secondary features such as EWMA volatility tracking (no_volatility,푠 푡푟푎푖푛 = −0.842, 푠 푡푒푠푡 =−0.029) or instantaneous regret boosting (no_boost,푠 푡푟푎푖푛 =−0.954, 푠 푡푒푠푡 =−0.204) degrades training fit while having only marginal effects on held-out generalization (Table 1). This indicates that the LLM evolved a tightly coupled system where these secondary features matter for in-distribution synergy but contribute little to generalization. However, while this synergistic complexity maximizes fitness on the training domains, our audit reveals that the true capacity for generalization rests entirely on three foundational structural shifts. Removing any of these causes a catastrophic collapse in exploitability: • Hard Warm-Start (푠 푡푟푎푖푛 =−5.256, 푠 푡푒푠푡 =−2.003): The most critical feature discovered by the LLM is a strict 500-iteration suspension of all policy averaging. By enforcing a hard delay, it ensures that early-stage, high-variance exploration noise does not pollute the final cumulative strategy profile. •Extreme Asymmetric Discounting (푠 푡푟푎푖푛 =−4.192, 푠 푡푒푠푡 =−1.065): While standard DCFR estab- lishes the value of decoupling positive and negative regret discounting, the LLM pushes this to a mathematical extreme. It assigns a negative exponent (훽=−0.1) for negative regrets. Because the discount multiplier is driven by a negative exponent, it rapidly decays toward zero, acting as an almost instantaneous “forget-gate” that prevents regret lock-in significantly faster than human-tuned DCFR baselines. •Optimistic Prediction (푠 푡푟푎푖푛 =−7.029, 푠 푡푒푠푡 =−0.905): VAD-CFR abandons standard linear Regret Matching, instead deriving the policy using a non-linear prediction with an exponent of 1.5 and a decaying optimism factor. This allows the policy to “anticipate” opponent shifts while aggressively correcting major strategic deficits. 4.3.2. Distillation: Warm-started Optimistic Predictive (WOP-) CFR While single-feature ablations destabilize the solver’s synergy, simultaneously stripping away all secondary heuristics reveals a highly distilled algorithmic core. By preserving only the three founda- tional components identified in the audit, we produce Warm-started Optimistic Predictive (WOP-) CFR (Listing 5). Unlike the raw discovery, WOP-CFR can be defined purely through three formal mathematical modifications to the standard CFR framework. First, it applies the discovered extreme 7 Discovering Multiagent Learning Algorithms with Large Language Models 0255075100 PSRO Iteration 10 5 10 4 10 3 10 2 10 1 10 0 Exploitability Kuhn Poker (Players=3) 0255075100 PSRO Iteration 10 1 10 0 Leduc Poker 0255075100 PSRO Iteration 10 3 10 2 10 1 10 0 Goofspiel (Num Cards=4) 0255075100 PSRO Iteration 10 1 10 0 Liars Dice (Dice Sides=5) Training Games Performance UNIFORMNASHALPHARANKPRDRMSHORPM 0255075100 PSRO Iteration 10 4 10 3 10 2 10 1 10 0 Exploitability Kuhn Poker (Players=4) 0255075100 PSRO Iteration 10 1 10 0 Leduc Poker (Players=3) 0255075100 PSRO Iteration 10 0 2 × 10 1 3 × 10 1 4 × 10 1 6 × 10 1 Goofspiel (Num Cards=5) 0255075100 PSRO Iteration 10 1 10 0 Liars Dice (Dice Sides=6) Test Games Performance UNIFORMNASHALPHARANKPRDRMSHORPM Figure 2 | PSRO variants performances. asymmetric discounting to the accumulated regret 푅 푡 푖 (퐼, 푎): 푅 푡 푖 (퐼, 푎)= 푑 (±) 푡 · 푅 푡−1 푖 (퐼, 푎)+ 푟 푡 푖 (퐼, 푎) where푑 (+) 푡 = 푡 1.5 푡 1.5 +1 if푅 푡−1 푖 (퐼, 푎) ≥ 0 and푑 (−) 푡 = 푡 −0.1 푡 −0.1 +1 otherwise. Second, it derives the current policy using a non-linear, optimistic predication for the next target: 휎 푡+1 푖 (퐼, 푎) ∝ max 0, 푑 (±) 푡 · 푅 푡 푖 (퐼, 푎)+ 1 1+ 푡/100 · 푟 푡 푖 (퐼, 푎) 1.5 where푑 (±) 푡 now depends on the sign of푅 푡 푖 (퐼, 푎) rather than푅 푡−1 푖 (퐼, 푎) . Finally, it enforces the strict hard warm-start, suspending average policy accumulation entirely for the first 500 iterations, after which it accumulates using a static polynomial weight푤 푡 = 푡 2 . By discarding the LLM’s overfitted training heuristics and structurally enforcing these three core mechanics, this distilled variant achieves a +0.119 Test IQM improvement over the raw VAD-CFR discovery. As shown in Figure 3 in the Appendix, compared with baselines, WOP-CFR ranks in the top three on every one of the 18 games, and achieves the lowest exploitability on 14 of them. In certain games like 3-player Leduc or 4-card limited information Goofspiel, it even outperforms VAD-CFR by non-negligible margins. 4.4. Experimental Evaluation: Discovering and Distilling State-of-the-Art PSRO Next, we evaluated the performance of the evolved Smoothed Hybrid Optimistic Regret (SHOR)-PSRO algorithm, comparing its ability to reduce exploitability against standard meta-solver baselines. We use the exploitability at the퐾=100-th PSRO iteration as the metric. We employ an exact best response oracle via value iteration, where at each state it distributes probability mass uniformly among actions 8 Discovering Multiagent Learning Algorithms with Large Language Models with the same optimal values. We benchmarked SHOR-PSRO against standard established meta-solver baselines: Uniform, Nash equilibrium via linear program for 2-player games, AlphaRank (Muller et al., 2020), Projected Replicator Dynamics (PRD) (Lanctot et al., 2017), and Regret Matching (RM) executed for 10 4 steps per PSRO iteration. We use Uniform as the initial program for both solver classes. The prompt we use is shown in Listing 9 in the Appendix. As shown in Figure 2, SHOR-PSRO ranks among the top performers across both the training set and the test set. In simpler domains like 3-player Kuhn Poker, SHOR-PSRO achieves exploitability levels (<10 −3 ) significantly faster than PRD or RM. In 3-player Leduc Poker, the meta-game landscape becomes significantly more chaotic due to multi-agent dynamics. Despite this, SHOR-PSRO consistently matches or outperforms the best-performing baselines. In the most demanding test case, Liar’s Dice (6 sides), SHOR-PSRO also demonstrates a clear advantage. 4.4.1. Identifying Foundational Mechanics The raw SHOR-PSRO algorithm (Listing 4) contains several highly synergistic mechanisms, most notably an optimistic regret matching+ (ORM+) engine, a hybrid blending module that actively interpolates between the ORM+ output and a smoothed best pure strategy, and asymmetric solvers that utilize distinct logic for training versus evaluation. To isolate the core drivers of performance, we conducted a systematic train-test split ablation study (with exhaustive configurations detailed in Appendix 7.2.3). As shown in Table 2, the audit exposes the fragility of the LLM’s asymmetric design and blending schedules. First, the result identifies the ORM + loop as the undeniable foundational engine. Removing the ORM + loop entirely to rely solely on the smoothed pure strategy (no_blending_pure) causes a catastrophic collapse in both training and testing environments (푠 푡푟푎푖푛 =−2.292, 푠 푡푒푠푡 =−1.268). In contrast, disabling the hybrid pure-strategy blending (no_blending_orm,푠 푡푟푎푖푛 =−0.069) and removing the dynamic scheduling (no_annealing,푠 푡푟푎푖푛 =−0.104) have negligible effects on training fit, indicating these components do not even drive in-distribution performance. Test IQM corroborates this diagnosis on held-out games:no_blending_purecollapses Test IQM by -1.268, while removing the hybrid blending and dynamic scheduling each independently improves Test IQM (+0.020, +0.016), confirming they are overfitted artifacts rather than generalization drivers. 4.4.2. Distillation: Projection Matching (PM-)PSRO To isolate the true engine of performance, we bypass the LLM’s entangled heuristics and distill the solver down to its mathematical core: Projection Matching (PM-)PSRO (in Listing 6). By stripping away annealing schedules, hybrid blending, and complex evaluation logic, PM is defined strictly by three essential mechanics. First, PM replaces the regret signal in regret matching with a tangent- projected utility. At each inner step푡, given the expected-utility vector푢 푡 푖 ∈ ℝ |Π 푖 | over the population of player 푖, we project it onto the tangent space of the probability simplexTΔ 푔 푡 푖 =P TΔ (푢 푡 푖 )= 퐼− 1 |Π 푖 | 11 ⊤ 푢 푡 푖 , i.e.,푢 푡 푖 centered by its mean. We then run standard regret matching on푔in place of푟(equations (1)(2) at the normal-form level). The tangent-projection step is the same geometric operation that defines the continuous-time Projection Dynamic Lahkar and Sandholm (2008); Sandholm et al. (2008) in evolutionary game theory literature, but the discrete update we use is RM-style rather than the projection-dynamic rule. Second, PM scales its inner iteration budget linearly with the empirical-game size, so the solver budget tracks population growth. Third, PM uses a unified time-averaged solver for both training and evaluation, since our ablations (Table 2) found it better than a single last-iterate solver. 9 Discovering Multiagent Learning Algorithms with Large Language Models Centering utilities by the population mean evaluates each policy strictly relative to the population average; paired with RM’s positive bounding, the solver instantly "forgets" below-average strategies, providing geometric immunity to extreme payoff outliers. Combining this core mechanism with the dynamic optimization budget yields a +0.059 Test IQM log-improvement over the raw SHOR-PSRO discovery. As shown in Figure 4 in the Appendix, compared with baselines, both SHOR-PSRO and PM-PSRO rank in the top three on every one of the 18 games, and achieve the lowest exploitability on 12 of them. We further validate these findings on 1000 randomly sampled푁- player퐴-action constant-sum normal-form games per(푁, 퐴)configuration (see Appendix 7.5), where SHOR-PSRO and PM-PSRO dominate all baselines across every (푁, 퐴) tested. 5. Related Work Significant research effort has been dedicated to improving the convergence speed of CFR through specific weighting schemes and regret targets. Notable variants include CFR+ (Tammelin, 2014), strategy-based warm starting (Brown and Sandholm, 2016), Discounted CFR (DCFR) (Brown and Sandholm, 2019b), and Predictive CFR+ (PCFR+) (Farina et al., 2021); these were derived through human intuition over a vast design space. Policy Space Response Oracles (PSRO) (Bighashdel et al., 2024) generalizes the Double Oracle algorithm (McMahan et al., 2003) by iteratively expanding a population of policies via exact or reinforcement learning best responses. While PSRO rests on solid theoretical ground (Zhang and Sandholm, 2024), its practical convergence and population-quality remain open challenges (Bighashdel et al., 2024). Research on automating machine learning algorithm design has been evolving for both neural- based approaches and symbolic-based approaches. Meta-learning approaches such as meta-RL (Oh et al., 2025; Xu et al., 2018) and meta-learning optimizers (Metz et al., 2019) have parameterized update rules using neural networks to optimize learning dynamics. For symbolic ML discovery, a foundational work in this domain is AutoML-Zero (Real et al., 2020), which demonstrated that complete machine learning algorithms could be evolved from scratch using basic mathematical operations. Subsequent work applies program search to discover optimizers (Chen et al., 2023) and symbolic RL algorithms (Co-Reyes et al., 2021), and LLM-driven search to discover isolated preference-optimization losses (Lu et al., 2024). Our contribution differs along two axes: we evolve structured algorithmic skeletons with multiple interacting components rather than a single loss or update rule, and we introduce a formal train-test ablation methodology to distill raw discoveries into minimal solvers — whereas prior work either ships the raw artifact (Co-Reyes et al., 2021; Lu et al., 2024) or applies one-off manual simplification (Chen et al., 2023). Within the specific domain of multi-agent learning, there has been prior work on automating algorithm design (Feng et al., 2021; Sychrovsk’y et al., 2024; Xu et al., 2022, 2024a). However, these approaches often faced limitations: they either operated within a relatively constrained search space or relied on neural parameterizations that hindered interpretability. Our work builds directly on AlphaEvolve (Novikov et al., 2025), utilizing Large Language Models (LLMs) to perform semantic mutation on interpretable code, bridging the gap between expressive neural meta-learning and symbolic discovery. This approach has already shown great success in the field of math (Georgiev et al., 2025) and combinatorial algorithms (Nagda et al., 2025). 6. Conclusion We applied LLM-driven evolutionary search to automate the design of multi-agent learning algorithms in two paradigms — CFR and PSRO. The raw discoveries VAD-CFR and SHOR-PSRO are consistently competitive with state-of-the-art human-designed baselines across an 18-game evaluation suite. 10 Discovering Multiagent Learning Algorithms with Large Language Models Through systematic train-test ablations, we distilled both into minimal solvers, WOP-CFR and PM- PSRO, that retain or improve generalization with substantially reduced complexity. Our results suggest LLM-driven evolutionary search is most useful as a proposal mechanism embedded in a human-in-the-loop pipeline: the LLM proposes candidate combinations of mechanisms, train-test ablation surfaces which generalize, and the researcher distills the survivors. Future work will extend this pipeline to deep reinforcement learning agents and cooperative general-sum games. Limitations. Our results have several caveats. (i) The reported algorithms reflect a single AlphaE- volve trajectory; we do not characterize variance over independent evolutionary runs, and the stability of the distilled components across runs remains empirically unverified, although each is well-motivated independent of any single run. (i) Our headline IQM is dominated by within-family generalization across train/test sets that share three game families; out-of-family generalization (Blotto, Battleship) is scoped to what Appendix 7.4 shows. (i) Distillation requires human judgment to identify which components to retain or simplify; the pipeline is human-in-the-loop, not fully autonomous. (iv) We provide no formal convergence guarantees. PM-PSRO uses tangent-projected utilities as the regret signal in standard RM, which shares a geometric step with the projection dynamic Lahkar and Sandholm (2008) but is not equivalent to it; WOP-CFR’s components are inspired by DCFR Brown and Sandholm (2019b) and PCFR+ Farina et al. (2021) but the specific combination is empirically rather than theoretically motivated. (v) We only compare with previous tabular-based baselines and do not include deep CFR Brown et al. (2019) or neural auto-curricula PSRO Feng et al. (2021); claims of competitive performance are scoped to the baselines tested. (vi) Exact exploitability restricts evaluation to games with less than 350K information states; scaling behavior and dependence on the specific LLM backbone and prompt design remain open. Acknowledgements We thank Ian Gemp and Xidong Feng for their valuable discussions and comments on this work. References R. Agarwal, M. Schwarzer, P. S. Castro, A. C. Courville, and M. Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In Thirty-Fifth Conference on Neural Information Processing Systems, volume 34, pages 29304–29320, 2021. A. Bighashdel, Y. Wang, S. McAleer, R. Savani, and F. A. Oliehoek. Policy space response oracles: A survey. In Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) Survey Track, 2024. E. Borel. The theory of play and integral equations with skew symmetric kernels. Econometrica: journal of the Econometric Society, pages 97–100, 1953. N. Brown and T. Sandholm. Strategy-based warm starting for regret minimization in games. In Thirtieth AAAI Conference on Artificial Intelligence, volume 30, 2016. N. Brown and T. Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):885–890, 2019a. doi: 10.1126/science.aay2400. N. Brown and T. Sandholm. Solving imperfect-information games via discounted regret minimization. In Thirty-Third AAAI Conference on Artificial Intelligence, volume 33, pages 1829–1836, 2019b. 11 Discovering Multiagent Learning Algorithms with Large Language Models N. Brown, A. Lerer, S. Gross, and T. Sandholm. Deep counterfactual regret minimization. In Thirty- Sixth International Conference on Machine Learning, pages 793–802, 2019. X. Chen, C. Liang, D. Huang, E. Real, K. Wang, H. Pham, X. Dong, T. Luong, C.-J. Hsieh, Y. Lu, et al. Symbolic discovery of optimization algorithms. In Thirty-Seventh International Conference on neural information processing systems, pages 49205–49233, 2023. J. D. Co-Reyes, Y. Miao, D. Peng, E. Real, Q. V. Le, S. Levine, H. Lee, and A. Faust. Evolving reinforcement learning algorithms. In Ninth International Conference on Learning Representations, 2021. G. Comanici, E. Bieber, M. Schaekermann, I. Pasupat, N. Sachdeva, I. Dhillon, M. Blistein, O. Ram, D. Zhang, E. Rosen, et al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261, 2025. G. Farina, C. K. Ling, F. Fang, and T. Sandholm. Correlation in extensive-form games: Saddle- point formulation and benchmarks. In Thirty-third International Conference on Neural Information Processing Systems, volume 32, 2019. G. Farina, C. Kroer, and T. Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Thirty-Fifth AAAI Conference on Artificial Intelligence, volume 35, pages 5363–5371, 2021. X. Feng, O. Slumbers, Z. Wan, B. Liu, S. M. McAleer, Y. Wen, J. Wang, and Y. Yang. Neural auto-curricula in two-player zero-sum games. In Thirty-Fifth International Conference on Neural Information Processing Systems, 2021. B. Georgiev, J. Gómez-Serrano, T. Tao, and A. Z. Wagner. Mathematical exploration and discovery at scale. arXiv preprint arXiv:2511.02864, 2025. H. W. Kuhn. Simplified two-person poker. Contributions to the Theory of Games, pages 97–103, 1950. R. Lahkar and W. H. Sandholm. The projection dynamic and the geometry of population games. Games and Economic Behavior, 64(2):565–590, 2008. M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Péréat, D. Silver, and T. Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In Thirty-First International Conference on Neural Information Processing Systems, pages 4190–4203, 2017. M. Lanctot, E. Lockhart, J.-B. Lespiau, V. Zambaldi, S. Upadhyay, J. Pérolat, S. Srinivasan, F. Timbers, K. Tuyls, S. Omidshafiei, et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv:1908.09453, 2019. V. Lis ` y, M. Lanctot, and M. H. Bowling. Online monte-carlo counterfactual regret minimization for search in imperfect information games. In Fourteenth International Conference on Autonomous Agents and Multiagent Systems, pages 27–36, 2015. C. Lu, S. Holt, C. Fanconi, A. J. Chan, J. Foerster, M. van der Schaar, and R. T. Lange. Discovering preference optimization algorithms with and for large language models. In Thirty-Sixth Conference on Neural Information Processing Systems, volume 37, pages 86528–86573, 2024. H. B. McMahan, G. J. Gordon, and A. Blum. Planning in the presence of cost functions controlled by an adversary. In Twentieth International Conference on Machine Learning, pages 536–543, 2003. 12 Discovering Multiagent Learning Algorithms with Large Language Models L. Metz, N. Maheswaranathan, J. Nixon, C. D. Freeman, and J. Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. In Thirty-Sixth International Conference on Machine Learning, pages 4556–4565, 2019. P. Muller, S. Omidshafiei, M. Rowland, K. Tuyls, J. Perolat, S. Liu, D. Hennes, L. Marris, M. Lanctot, E. Hughes, et al. A generalized training approach for multiagent learning. In Ninth International Conference on Learning Representations, 2020. A. Nagda, P. Raghavan, and A. Thakurta. Reinforced generation of combinatorial structures: Hardness of approximation. arXiv preprint arXiv:2509.18057, 2025. A. Novikov, N. V ̃ u, M. Eisenberger, E. Dupont, P.-S. Huang, A. Z. Wagner, S. Shirobokov, B. Kozlovskii, F. J. Ruiz, A. Mehrabian, et al. Alphaevolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, 2025. J. Oh, G. Farquhar, I. Kemaev, D. A. Calian, M. Hessel, L. Zintgraf, S. Singh, H. Van Hasselt, and D. Silver. Discovering state-of-the-art reinforcement learning algorithms. Nature, pages 1–2, 2025. E. Real, C. Liang, D. So, and Q. V. Le. Automl-zero: Evolving machine learning algorithms from scratch. In Thirty-Seventh International Conference on Machine Learning, pages 8007–8019, 2020. S. M. Ross. Goofspiel—the game of pure strategy. Journal of Applied Probability, 8(3):621–625, 1971. W. H. Sandholm, E. Dokumacı, and R. Lahkar. The projection dynamic and the replicator dynamic. Games and Economic Behavior, 64(2):666–683, 2008. Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, New York, NY, USA, 2008. F. Southey, M. Bowling, B. Larson, C. Piccione, N. Burch, D. Billings, and C. Rayner. Bayes’ bluff: opponent modelling in poker. In Twenty-First Conference on Uncertainty in Artificial Intelligence, pages 550–558, 2005. D. Sychrovsk’y, M. Šustr, E. Davoodi, M. Bowling, M. Lanctot, and M. Schmid. Learning to not regret. In Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024. O. Tammelin. Solving large imperfect information games using cfr+. arXiv preprint arXiv:1407.5042, 2014. O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, et al. Grandmaster level in starcraft i using multi-agent reinforcement learning. Nature, 575(7782):350–354, 2019. M. P. Wellman, K. Tuyls, and A. Greenwald. Empirical game theoretic analysis: A survey. Journal of Artificial Intelligence Research, 82:1017–1076, 2025. H. Xu, K. Li, H. Fu, Q. Fu, and J. Xing. Autocfr: Learning to design counterfactual regret minimization algorithms. In Thirty-Sixth AAAI Conference on Artificial Intelligence, pages 5244–5251, 2022. H. Xu, K. Li, H. Fu, Q. Fu, J. Xing, and J. Cheng. Dynamic discounted counterfactual regret minimiza- tion. In Twelfth International Conference on Learning Representations, 2024a. H. Xu, K. Li, B. Liu, H. Fu, Q. Fu, J. Xing, and J. Cheng. Minimizing weighted counterfactual regret with optimistic online mirror descent. In Thirty-Third International Joint Conference on Artificial Intelligence, pages 5272–5280, 2024b. 13 Discovering Multiagent Learning Algorithms with Large Language Models Z. Xu, H. van Hasselt, and D. Silver. Meta-gradient reinforcement learning. In Thirty-Second International Conference on Neural Information Processing Systems, volume 31, 2018. B. H. Zhang and T. Sandholm. Exponential lower bounds on the double oracle algorithm in zero-sum games. In Thirty-Third International Joint Conference on Artificial Intelligence, pages 3032–3039, 2024. N. Zhang, S. McAleer, and T. Sandholm. Faster game solving via hyperparameter schedules. In Fortieth AAAI Conference on Artificial Intelligence, 2026. M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Twenty-First International Conference on Neural Information Processing Systems, pages 1729–1736, 2007. 14 Discovering Multiagent Learning Algorithms with Large Language Models 7. Appendix 7.1. Code skeleton Listing 1|The Python CFR code skeleton used as the search space for AlphaEvolve. The highlighted methods update_accumulate_regret, get_updated_current_policy, and update_accumulate_policy represent the evolvable components of the CFR algorithm. class RegretAccumulator: """A class that updates cumulative regret at an information set.""" def update_accumulate_regret(self, info_state_node, iteration_number, cfr_regrets): """ Args: info_state_node: Data structure with cumulative_regret and cumulative_policy. iteration_number: Current CFR iteration. cfr_regrets: Counterfactual regrets (not yet added to node). Returns: Updated cumulative regret dictionary for each action. """ ... class PolicyFromRegretAccumulator: """A class that derives the current policy from regret.""" def get_updated_current_policy(self, info_state_node, iteration_number, cfr_regrets, ↩→ previous_policy): """ Args: info_state_node: Data structure with cumulative_regret. iteration_number: Current CFR iteration. cfr_regrets: Counterfactual regrets (already added to node). previous_policy: Previous policy at this info set. Returns: Updated current policy dictionary. """ ... class PolicyAccumulator: """A class that updates the average policy during tree traversal.""" def update_accumulate_policy(self, info_state_node, iteration_number, info_state_policy, ↩→ cfr_regrets, reach_prob, counterfactual_reach_prob): """ Args: info_state_node: Data structure with cumulative_policy. iteration_number: Current CFR iteration. info_state_policy: Current policy at this info set. cfr_regrets: Counterfactual regrets (already added to node). reach_prob: Probability of reaching current history (player’s contribution). counterfactual_reach_prob: Probability of reaching current history (opponents’ contribution) ↩→ . Returns: Updated cumulative policy dictionary. """ ... Listing 2|The Python PSRO code skeleton used as the search space for AlphaEvolve. The highlighted methods TrainMetaStrategySolver and EvalMetaStrategySolver represent the evolvable components of the PSRO algorithm. class TrainMetaStrategySolver: """Returns meta strategies to train against in PSRO.""" 15 Discovering Multiagent Learning Algorithms with Large Language Models def get_meta_strategy(self, game, policy_sets, meta_games): """Returns meta strategies to train against in policy-space response oracles. Args: game: The pyspiel game object. policy_sets: A list of lists of policies, one list per player. policy_sets[p][i] is player p’s i-th policy. len(policy_sets[p]) == meta_games[0].shape[p]. meta_games: A list of n-dimensional numpy arrays, one per player. Each array has shape (num_strats_p0, num_strats_p1, ..., num_strats_pn-1) and meta_games[p][i0, i1, ..., in-1] is the payoff of player p when player k chooses strategy ik. Returns: A list of mixed-strategies, one for each player. Each mixed strategy is a list of non-negative weights (not necessarily normalized). It is used to train best response against. """ ... class EvalMetaStrategySolver: """Returns meta strategies for evaluation in PSRO.""" def get_meta_strategy(self, game, policy_sets, meta_games): """Returns meta strategies for evaluation in policy-space response oracles. Args: game: The pyspiel game object. policy_sets: A list of lists of policies, one list per player. policy_sets[p][i] is player p’s i-th policy. len(policy_sets[p]) == meta_games[0].shape[p]. meta_games: A list of n-dimensional numpy arrays, one per player. Each array has shape (num_strats_p0, num_strats_p1, ..., num_strats_pn-1) and meta_games[p][i0, i1, ..., in-1] is the payoff of player p when player k chooses strategy ik. Returns: A list of mixed-strategies, one for each player. Each mixed strategy is a list of non-negative weights (not necessarily normalized). It is used for evaluation of the current PSRO policies. E.g., computing exploitability. """ ... 7.2. Source code of discovered algorithms Listing 3 | VAD-CFR class RegretAccumulator: """A class that updates cumulative regret using Adaptive Discounting with separate discounting for positive and negative regrets, and instantaneous regret boosting. """ @staticmethod def _calculate_adaptive_params( iteration_number, cfr_regrets, base_alpha, base_beta, volatility_sensitivity, max_expected_instantaneous_regret, ewma_decay_factor, current_ewma_magnitude, ): """Calculates adaptive discounting parameters for a given iteration. This static method centralizes the logic for EWMA volatility, adaptive 16 Discovering Multiagent Learning Algorithms with Large Language Models alpha/beta, and discount factors to ensure consistency across components. """ t_plus_one = float(iteration_number + 1) instantaneous_regret_magnitude = max( (abs(r) for r in cfr_regrets.values()), default=0.0 ) if iteration_number == 0: projected_ewma = instantaneous_regret_magnitude else: projected_ewma = ( ewma_decay_factor * instantaneous_regret_magnitude + (1.0 - ewma_decay_factor) * current_ewma_magnitude ) if max_expected_instantaneous_regret > 0: normalized_volatility = min(1.0, projected_ewma / max_expected_instantaneous_regret) else: normalized_volatility = 0.0 effective_alpha = max(0.1, base_alpha - volatility_sensitivity * normalized_volatility) effective_beta = base_beta - volatility_sensitivity * normalized_volatility effective_beta = min(effective_alpha, effective_beta) discount_factor_positive = (t_plus_one**effective_alpha) / (t_plus_one**effective_alpha + 1.0) discount_factor_negative = (t_plus_one**effective_beta) / (t_plus_one**effective_beta + 1.0) return projected_ewma, normalized_volatility, discount_factor_positive, ↩→ discount_factor_negative def __init__(self, base_alpha=1.5, base_beta=-0.1, volatility_sensitivity=0.5, max_expected_instantaneous_regret=2.0, instantaneous_regret_boost_factor=1.1, ewma_decay_factor=0.1, negative_regret_cap=-20.0): """Initializes the regret accumulator with adaptive discounting parameters. Args: base_alpha: The baseline exponent for discounting positive cumulative regrets. base_beta: The baseline exponent for discounting negative cumulative regrets. volatility_sensitivity: Controls how strongly the instantaneous regret magnitude influences the adaptive alpha/beta. A higher value means the exponents will be more reduced by high volatility. max_expected_instantaneous_regret: An estimate of the maximum possible instantaneous regret magnitude, used for normalizing the volatility. instantaneous_regret_boost_factor: Boost factor for positive instantaneous regrets. A factor > 1.0 makes the algorithm more reactive to current good actions. ewma_decay_factor: Decay factor for the EWMA of instantaneous regret magnitude. negative_regret_cap: The minimum value for cumulative regret, to prevent regret lock-in and improve adaptability. """ self._base_alpha = base_alpha self._base_beta = base_beta self._volatility_sensitivity = volatility_sensitivity self._max_expected_instantaneous_regret = max_expected_instantaneous_regret self._instantaneous_regret_boost_factor = instantaneous_regret_boost_factor self._ewma_decay_factor = ewma_decay_factor self._negative_regret_cap = negative_regret_cap self._ewma_instantaneous_regret_magnitude = 0.0 def update_accumulate_regret( self, info_state_node, iteration_number, cfr_regrets ): """Updates cumulative regret for each action at an information set. Cumulative regrets are now signed. Args: info_state_node: a data structure corresponding to an information set with cumulative_regret and cumulative_policy stored. iteration_number: the current CFR iteration (0-indexed). cfr_regrets: the instantaneous counterfactual regrets of the current policy at the 17 Discovering Multiagent Learning Algorithms with Large Language Models current information set. cfr_regrets haven’t been added to info_state_node. ↩→ cumulative_regret. Returns: updated cumulative regret for each action at the current information set (signed). """ # Centralize adaptive parameter calculation to ensure consistency and reduce redundancy. ( self._ewma_instantaneous_regret_magnitude, _, # normalized_volatility is not used here discount_factor_positive, discount_factor_negative, ) = RegretAccumulator._calculate_adaptive_params( iteration_number=iteration_number, cfr_regrets=cfr_regrets, base_alpha=self._base_alpha, base_beta=self._base_beta, volatility_sensitivity=self._volatility_sensitivity, max_expected_instantaneous_regret=self._max_expected_instantaneous_regret, ewma_decay_factor=self._ewma_decay_factor, current_ewma_magnitude=self._ewma_instantaneous_regret_magnitude, ) updated_cumulative_regret = for action in cfr_regrets: old_regret = info_state_node.cumulative_regret[action] instantaneous_regret_component = cfr_regrets[action] if instantaneous_regret_component > 0: instantaneous_regret_component *= self._instantaneous_regret_boost_factor # Apply different discount factors based on the sign of the old regret. if old_regret >= 0: discounted_old_regret = discount_factor_positive * old_regret else: discounted_old_regret = discount_factor_negative * old_regret new_regret = discounted_old_regret + instantaneous_regret_component # Cap the negative regret to prevent lock-in and improve adaptability. new_regret = max(self._negative_regret_cap, new_regret) # Crucially, regrets are NOT clipped to zero here. They can be negative. updated_cumulative_regret[action] = new_regret return updated_cumulative_regret class PolicyFromRegretAccumulator: """A class that obtains a current policy from a consistent optimistic projection of regrets. It aligns the policy generation with the adaptive, asymmetric, and boosted logic from ↩→ RegretAccumulator. """ def __init__(self, initial_optimism_factor=1.0, optimism_decay_factor=100.0, positive_policy_exponent=1.5, base_alpha=1.5, base_beta=-0.1, volatility_sensitivity=0.5, max_expected_instantaneous_regret=2.0, instantaneous_regret_boost_factor=1.1, ewma_decay_factor=0.1): """Initializes the PolicyFromRegretAccumulator with parameters consistent with ↩→ RegretAccumulator. Args: initial_optimism_factor: The initial weighting for the instantaneous regret component in the ↩→ projection. optimism_decay_factor: Controls how quickly the optimism weight decays. 18 Discovering Multiagent Learning Algorithms with Large Language Models positive_policy_exponent: Exponent for non-linear scaling of positive regrets. base_alpha: The baseline exponent for discounting positive regrets. base_beta: The baseline exponent for discounting negative regrets. volatility_sensitivity: Controls influence of volatility on both discounting and optimism dampening. max_expected_instantaneous_regret: Used for normalizing volatility. instantaneous_regret_boost_factor: Boost factor for positive instantaneous regrets. ewma_decay_factor: Decay factor for the EWMA of volatility. """ self._initial_optimism_factor = initial_optimism_factor self._optimism_decay_factor = optimism_decay_factor self._positive_policy_exponent = positive_policy_exponent self._base_alpha = base_alpha self._base_beta = base_beta self._volatility_sensitivity = volatility_sensitivity self._max_expected_instantaneous_regret = max_expected_instantaneous_regret self._instantaneous_regret_boost_factor = instantaneous_regret_boost_factor self._ewma_decay_factor = ewma_decay_factor self._ewma_instantaneous_regret_magnitude = 0.0 def get_updated_current_policy(self, info_state_node, iteration_number, cfr_regrets, ↩→ previous_policy): """Obtains the current policy using a projection that is consistent with the RegretAccumulator ↩→ ’s update rule. This method creates a tighter feedback loop by basing the current policy on a projection of what the regrets will be *after* the current iteration’s update. This projection uses the same adaptive, asymmetric discounting and boosting logic as the main regret accumulation step. """ # Centralize adaptive parameter calculation, ensuring consistency with RegretAccumulator. ( self._ewma_instantaneous_regret_magnitude, normalized_volatility, discount_factor_positive, discount_factor_negative, ) = RegretAccumulator._calculate_adaptive_params( iteration_number=iteration_number, cfr_regrets=cfr_regrets, base_alpha=self._base_alpha, base_beta=self._base_beta, volatility_sensitivity=self._volatility_sensitivity, max_expected_instantaneous_regret=self._max_expected_instantaneous_regret, ewma_decay_factor=self._ewma_decay_factor, current_ewma_magnitude=self._ewma_instantaneous_regret_magnitude, ) base_optimism = self._initial_optimism_factor / (1.0 + float(iteration_number) / self. ↩→ _optimism_decay_factor) # Dampen optimism during volatile periods to increase stability. optimism_dampening_factor = max(0.0, 1.0 - self._volatility_sensitivity * ↩→ normalized_volatility) optimism_strength = base_optimism * optimism_dampening_factor action_to_projected_regret = for action in info_state_node.legal_actions: old_cumulative_regret = info_state_node.cumulative_regret.get(action, 0.0) instantaneous_regret = cfr_regrets.get(action, 0.0) instantaneous_regret_component = instantaneous_regret if instantaneous_regret_component > 0: instantaneous_regret_component *= self._instantaneous_regret_boost_factor if old_cumulative_regret >= 0: discounted_old_regret = discount_factor_positive * old_cumulative_regret else: discounted_old_regret = discount_factor_negative * old_cumulative_regret projected_regret = discounted_old_regret + optimism_strength * ↩→ instantaneous_regret_component 19 Discovering Multiagent Learning Algorithms with Large Language Models action_to_projected_regret[action] = projected_regret positive_scaled_projected_regrets = action: (max(0.0, regret) ** self._positive_policy_exponent) for action, regret in action_to_projected_regret.items() sum_positive_scaled_projected_regrets = sum(positive_scaled_projected_regrets.values()) info_state_policy = if sum_positive_scaled_projected_regrets > 0: for action, scaled_regret in positive_scaled_projected_regrets.items(): info_state_policy[action] = scaled_regret / sum_positive_scaled_projected_regrets else: num_legal_actions = len(info_state_node.legal_actions) for action in info_state_node.legal_actions: info_state_policy[action] = 1.0 / num_legal_actions return info_state_policy class PolicyAccumulator: """A class that updates cumulative policy using regret-informed weighted averaging with a warmup period.""" def __init__(self, base_gamma=2.0, gamma_max=4.0, gamma_volatility_sensitivity=1.5, warmup_iterations=500, stability_exponent=1.5, max_expected_instantaneous_regret=2.0, regret_magnitude_weighting_exponent=0.5): # New parameter """Initializes the PolicyAccumulator with adaptive gamma parameters and regret-magnitude ↩→ weighting. Args: base_gamma: The baseline exponent for polynomial weighting of policies. gamma_max: The maximum value the adaptive gamma can reach. gamma_volatility_sensitivity: Controls how strongly volatility influences gamma. warmup_iterations: Number of initial iterations to skip for policy averaging. stability_exponent: Exponent for the stability factor based on regret magnitude. max_expected_instantaneous_regret: Normalization factor for instantaneous regret magnitude. regret_magnitude_weighting_exponent: Exponent for up-weighting policies based on the absolute magnitude of instantaneous regrets. Higher values give more emphasis to policies from iterations with large regrets. """ self._base_gamma = base_gamma self._gamma_max = gamma_max self._gamma_volatility_sensitivity = gamma_volatility_sensitivity self._warmup_iterations = warmup_iterations self._stability_exponent = stability_exponent self._max_expected_instantaneous_regret = max_expected_instantaneous_regret self._regret_magnitude_weighting_exponent = regret_magnitude_weighting_exponent # Stored def update_accumulate_policy( self, info_state_node, iteration_number, info_state_policy, cfr_regrets, reach_prob, counterfactual_reach_prob, ): """Updates cumulative policy using delayed, regret-informed, and regret-magnitude weighted ↩→ averaging. """ if iteration_number < self._warmup_iterations: return info_state_node.cumulative_policy # Calculate instantaneous regret magnitude (L-infinity norm) for this iteration instantaneous_regret_magnitude = max( (abs(r) for r in cfr_regrets.values()), default=0.0 ) 20 Discovering Multiagent Learning Algorithms with Large Language Models # Normalize volatility using the shared parameter if self._max_expected_instantaneous_regret > 0: normalized_volatility = min(1.0, instantaneous_regret_magnitude / self. ↩→ _max_expected_instantaneous_regret) else: normalized_volatility = 0.0 # Adapt gamma based on volatility: higher volatility -> higher gamma effective_gamma = self._base_gamma + self._gamma_volatility_sensitivity * ↩→ normalized_volatility effective_gamma = min(self._gamma_max, effective_gamma) # Standard polynomial weighting gives more weight to later iterations, now with adaptive gamma ↩→ . temporal_weight = (float(iteration_number) + 1.0) ** effective_gamma # Calculate a stability factor from the L-infinity norm of instantaneous regrets. # Higher regret magnitude -> lower stability factor, using L-infinity norm for consistency. regret_stability_factor = 1.0 / (1.0 + instantaneous_regret_magnitude**self. ↩→ _stability_exponent) # NEW: Regret Magnitude Weighting Factor # Policies from iterations with higher regret magnitude contribute more to the average. # This factor boosts the weight, with higher values of the exponent giving more emphasis. # Ensure it’s never zero to avoid division by zero or completely nullifying weight. regret_magnitude_factor = ( 1.0 + (instantaneous_regret_magnitude / self._max_expected_instantaneous_regret) ) ** self._regret_magnitude_weighting_exponent regret_magnitude_factor = max(0.1, regret_magnitude_factor) # Ensure minimum value to avoid ↩→ zero weight if normalization results in very small number # The final weight combines the temporal, stability, and regret-magnitude-based components. weight = temporal_weight * regret_stability_factor * regret_magnitude_factor return action: ( info_state_node.cumulative_policy[action] + weight * reach_prob * info_state_policy[action] ) for action in info_state_policy Listing 4 | SHOR-PSRO import numpy as np def _smoothed_best_pure_strategy(payoff_vec, temperature=1.0): """Computes a smoothed distribution biased towards the best pure strategy. The softmax function ensures that strategies with higher payoffs are given higher probability, with ’temperature’ controlling the sharpness of the distribution. A lower temperature makes the distribution more concentrated on the best strategy, while a higher temperature leads to a more uniform distribution. """ # Subtract max payoff for numerical stability (standard softmax trick) stable_payoffs = payoff_vec - np.max(payoff_vec) exp_payoffs = np.exp(stable_payoffs / temperature) sum_exp_payoffs = np.sum(exp_payoffs) if sum_exp_payoffs > 1e-12: # Avoid division by zero return exp_payoffs / sum_exp_payoffs else: # Fallback to uniform distribution if all exponentiated payoffs are # effectively zero (e.g., due to very low temperature and negative payoffs, # or all payoffs being identical after stabilization). return np.ones_like(payoff_vec) / len(payoff_vec) 21 Discovering Multiagent Learning Algorithms with Large Language Models def _hybrid_orm_solver(meta_games, iterations, blending_factor=0.0, temperature=0.1, momentum_beta=0.0, gain_normalization=True, diversity_bonus_coeff=0.0, return_average_strategy=True): # New: Flag to return average or last- ↩→ iterate strategy """Computes meta-strategies using Optimistic Regret Matching+ enhanced with optimistic updates, gain normalization, and a diversity bonus, then blended with a smoothed best pure strategy. This solver combines the stability and convergence properties of Optimistic Regret Matching+ (ORM+) with an explicit pull towards highly rewarding pure strategies, smoothed by a temperature-controlled softmax. This hybrid approach aims to leverage ORM+’s ability to find mixed equilibria while also quickly identifying and exploring strong pure-strategy modes in the meta-game, thereby potentially accelerating the discovery of low-exploitable policies in PSRO. The blending factor controls the trade-off between these two dynamics. Args: meta_games: A list of n-dimensional numpy arrays, one per player. iterations: Number of internal solver iterations. blending_factor: Weight (0 to 1) for blending ORM+ output with the smoothed best pure strategy. A factor of 0 means pure ORM+; 1 means pure smoothed best pure strategy. temperature: Temperature for softmax smoothing when calculating the smoothed best pure strategy. Lower values make the smoothing sharper. momentum_beta: Momentum parameter for optimistic updates to payoff gains. gain_normalization: If True, normalizes payoff gains to make learning rate more robust across games. diversity_bonus_coeff: Coefficient for diversity bonus, encouraging exploration of less-chosen policies. return_average_strategy: If True, returns time-averaged strategies. If False, returns last-iterate strategies. Returns: A list of mixed-strategies, one for each player, as numpy arrays. """ num_players = len(meta_games) num_strats = [m.shape[i] for i, m in enumerate(meta_games)] if any(n_s == 0 for n_s in num_strats): return [np.array([]).tolist() for _ in range(num_players)] strategies = [np.ones(s, dtype=float) / s for s in num_strats] cum_regrets = [np.zeros(s, dtype=float) for s in num_strats] avg_strategies = [np.zeros(s, dtype=float) for s in num_strats] prev_centered_payoff_gains = [np.zeros(s, dtype=float) for s in num_strats] for t in range(iterations): current_centered_payoff_gains = [np.zeros(s, dtype=float) for s in num_strats] orm_strategies_this_iter = [np.zeros(s, dtype=float) for s in num_strats] for p in range(num_players): payoff_vec = meta_games[p] for other_p in reversed(range(num_players)): if other_p != p: payoff_vec = np.tensordot(payoff_vec, strategies[other_p], axes=([other_p], [0])) centered_payoff_gains = payoff_vec - np.mean(payoff_vec) current_centered_payoff_gains[p] = centered_payoff_gains optimistic_payoff_gains = (1 + momentum_beta) * centered_payoff_gains - \ momentum_beta * prev_centered_payoff_gains[p] diversity_bonus = diversity_bonus_coeff * (1.0 - strategies[p]) gains_for_regret_update = optimistic_payoff_gains + diversity_bonus 22 Discovering Multiagent Learning Algorithms with Large Language Models if gain_normalization: max_abs_gain = np.max(np.abs(gains_for_regret_update)) if max_abs_gain > 1e-8: gains_for_regret_update /= max_abs_gain cum_regrets[p] += gains_for_regret_update cum_regrets[p] = np.maximum(0, cum_regrets[p]) sum_pos_regret = cum_regrets[p].sum() if sum_pos_regret > 1e-12: orm_strategies_this_iter[p] = cum_regrets[p] / sum_pos_regret else: orm_strategies_this_iter[p] = np.ones(num_strats[p]) / num_strats[p] smoothed_best_pure = _smoothed_best_pure_strategy(payoff_vec, temperature) strategies[p] = (1 - blending_factor) * orm_strategies_this_iter[p] + \ blending_factor * smoothed_best_pure prev_centered_payoff_gains[p] = current_centered_payoff_gains[p] if return_average_strategy: # Accumulate blended strategy only if average is requested avg_strategies[p] += strategies[p] if return_average_strategy: final_strategies = [] for p in range(num_players): sum_avg_strat = np.sum(avg_strategies[p]) if sum_avg_strat > 0: final_strategies.append(avg_strategies[p] / sum_avg_strat) else: final_strategies.append(np.ones(num_strats[p]) / num_strats[p]) return final_strategies else: # If not returning average, return the last-iterate strategies return strategies class TrainMetaStrategySolver: """A hybrid meta-solver for training that blends ORM+ with smoothed best pure strategies. This solver aims to accelerate convergence to low-exploitable strategies by dynamically balancing regret-minimization with a pull towards high-performing (but smoothed) pure strategies. Optimistic updates, gain normalization, and a diversity bonus are incorporated for improved learning dynamics. The blending factor, temperature, and diversity bonus are annealed over the outer PSRO iterations. """ def __init__(self, base_solver_iterations=1000, # Base number of internal iterations iterations_per_policy_scale=20, # How much iterations scale per added policy max_solver_iterations=5000, # Max internal solver iterations initial_blending_factor=0.3, final_blending_factor=0.05, initial_temperature=0.5, final_temperature=0.01, momentum_beta=0.5, gain_normalization=True, initial_diversity_bonus_coeff=0.05, final_diversity_bonus_coeff=0.001, max_psro_iterations_for_annealing=75): """Initializes hybrid ORM solver parameters for training. Args: base_solver_iterations: Base number of internal solver iterations for _hybrid_orm_solver. iterations_per_policy_scale: Amount to increase internal solver iterations per added policy. max_solver_iterations: Maximum internal solver iterations. initial_blending_factor: Initial weight for the smoothed best pure strategy component. final_blending_factor: Final weight for the smoothed best pure strategy component. initial_temperature: Initial temperature for softmax smoothing. 23 Discovering Multiagent Learning Algorithms with Large Language Models final_temperature: Final temperature for softmax smoothing. momentum_beta: Momentum for optimistic updates. gain_normalization: Normalizes gains for scale-invariance. initial_diversity_bonus_coeff: Max initial diversity bonus coefficient. final_diversity_bonus_coeff: Min initial diversity bonus coefficient across PSRO iterations. max_psro_iterations_for_annealing: PSRO iterations over which outer annealing occurs. """ self._base_solver_iterations = base_solver_iterations self._iterations_per_policy_scale = iterations_per_policy_scale self._max_solver_iterations = max_solver_iterations self._initial_blending_factor = initial_blending_factor self._final_blending_factor = final_blending_factor self._initial_temperature = initial_temperature self._final_temperature = final_temperature self._momentum_beta = momentum_beta self._gain_normalization = gain_normalization self._initial_diversity_bonus_coeff = initial_diversity_bonus_coeff self._final_diversity_bonus_coeff = final_diversity_bonus_coeff self._max_psro_iterations_for_annealing = max_psro_iterations_for_annealing self._current_psro_iteration = 0 def get_meta_strategy(self, game, policy_sets, meta_games): """Returns blended meta strategies for training. Args: game: The pyspiel game object. policy_sets: A list of lists of policies, one list per player. policy_sets[p][i] is player p’s i-th policy. len(policy_sets[p]) == meta_games[0].shape[p]. meta_games: A list of n-dimensional numpy arrays, one per player. Each array has shape (num_strats_p0, num_strats_p1, ..., num_strats_pn-1) and meta_games[p][i0, i1, ..., in-1] is the payoff of player p when player k chooses strategy ik. Returns: A list of blended mixed-strategies. """ del game, policy_sets # Unused self._current_psro_iteration += 1 current_psro_iter = self._current_psro_iteration # Adaptive solver iterations: scale with current population size num_current_policies_p0 = len(meta_games[0]) # Assuming symmetric populations solver_iterations = int(self._base_solver_iterations + self._iterations_per_policy_scale * (num_current_policies_p0 - 1)) solver_iterations = np.clip(solver_iterations, self._base_solver_iterations, self. ↩→ _max_solver_iterations) annealing_progress = min(1.0, current_psro_iter / self._max_psro_iterations_for_annealing) blending_factor = (self._initial_blending_factor * (1.0 - annealing_progress) + self._final_blending_factor * annealing_progress) temperature = (self._initial_temperature * (1.0 - annealing_progress) + self._final_temperature * annealing_progress) diversity_bonus_coeff = (self._initial_diversity_bonus_coeff * (1.0 - annealing_progress) + self._final_diversity_bonus_coeff * annealing_progress) blending_factor = np.clip(blending_factor, self._final_blending_factor, self. ↩→ _initial_blending_factor) temperature = np.clip(temperature, self._final_temperature, self._initial_temperature) diversity_bonus_coeff = np.clip(diversity_bonus_coeff, self._final_diversity_bonus_coeff, self ↩→ ._initial_diversity_bonus_coeff) strategies = _hybrid_orm_solver( meta_games, iterations=solver_iterations, # Use adaptive iterations blending_factor=blending_factor, 24 Discovering Multiagent Learning Algorithms with Large Language Models temperature=temperature, momentum_beta=self._momentum_beta, gain_normalization=self._gain_normalization, diversity_bonus_coeff=diversity_bonus_coeff, return_average_strategy=True # Training always uses averaged strategies for stability ) return [s.tolist() for s in strategies] class EvalMetaStrategySolver: """Returns meta strategies for evaluation in PSRO. This solver uses a hybrid approach, blending Optimistic Regret Matching+ with a smoothed best pure strategy, tailored for robust and accurate exploitability measurement. The parameters are set to emphasize exploitation for evaluation purposes, including optimistic updates and gain normalization for stability, while keeping diversity bonus minimal. Crucially, it returns the *last-iterate* strategy for a reactive estimate of exploitability. """ def __init__(self, base_solver_iterations=8000, # Base number of internal iterations iterations_per_policy_scale=50, # How much iterations scale per added policy max_solver_iterations=15000, # Max internal solver iterations blending_factor=0.01, temperature=0.001, momentum_beta=0.2, gain_normalization=True, diversity_bonus_coeff=0.0): """Initializes hybrid ORM solver parameters for evaluation meta-strategies. Args: base_solver_iterations: Base number of internal solver iterations for _hybrid_orm_solver. iterations_per_policy_scale: Amount to increase internal solver iterations per added policy. max_solver_iterations: Maximum internal solver iterations. blending_factor: Weight (0 to 1) for the smoothed best pure strategy component. temperature: Temperature for softmax smoothing. momentum_beta: Momentum for optimistic updates. gain_normalization: Normalizes gains for scale-invariance. diversity_bonus_coeff: Diversity bonus, kept very low for evaluation. """ self._base_solver_iterations = base_solver_iterations self._iterations_per_policy_scale = iterations_per_policy_scale self._max_solver_iterations = max_solver_iterations self._blending_factor = blending_factor self._temperature = temperature self._momentum_beta = momentum_beta self._gain_normalization = gain_normalization self._diversity_bonus_coeff = diversity_bonus_coeff def get_meta_strategy(self, game, policy_sets, meta_games): """Returns blended meta strategies for evaluation in policy-space response oracles. Args: game: The pyspiel game object. policy_sets: A list of lists of policies, one list per player. policy_sets[p][i] is player p’s i-th policy. len(policy_sets[p]) == meta_games[0].shape[p]. meta_games: A list of n-dimensional numpy arrays, one per player. Each array has shape (num_strats_p0, num_strats_p1, ..., num_strats_pn-1) and meta_games[p][i0, i1, ..., in-1] is the payoff of player p when player k chooses strategy ik. Returns: A list of mixed-strategies, one for each player. Each mixed strategy is a list of non-negative weights (not necessarily normalized). It is used for evaluation of the current PSRO policies. E.g., computing exploitability. """ 25 Discovering Multiagent Learning Algorithms with Large Language Models del game, policy_sets # Unused num_current_policies_p0 = len(meta_games[0]) # Assuming symmetric populations solver_iterations = int(self._base_solver_iterations + self._iterations_per_policy_scale * (num_current_policies_p0 - 1)) solver_iterations = np.clip(solver_iterations, self._base_solver_iterations, self. ↩→ _max_solver_iterations) strategies = _hybrid_orm_solver( meta_games, iterations=solver_iterations, # Use adaptive iterations blending_factor=self._blending_factor, temperature=self._temperature, momentum_beta=self._momentum_beta, gain_normalization=self._gain_normalization, diversity_bonus_coeff=self._diversity_bonus_coeff, return_average_strategy=False # Eval explicitly requests last-iterate strategy ) return [s.tolist() for s in strategies] 7.2.1. Detailed Specification of VAD-CFR Ablation Components To understand the contribution of each mechanism discovered by AlphaEvolve within the Volatility- Adaptive Discounted (VAD-) CFR, we conducted a systematic ablation study. Each ablation removes or reverts a specific evolved component to its standard Counterfactual Regret Minimization (CFR) or Discounted CFR (DCFR) equivalent. The following variants correspond to the empirical results presented in Table 1. Regret Accumulation Variants •VAD-CFR (no_asym_discount): VAD-CFR utilizes highly asymmetric discounting factors for positive and negative regrets. This ablation forces a symmetric baseline discount factor by settingbase_beta = 1.5(matchingbase_alpha), testing the hypothesis that an aggressive “forget-gate” (훽=−0.1) is necessary for recovery in non-stationary multi-agent environments. •VAD-CFR (no_boost): This variant removes the “Exploration Boost” mechanism by reverting instantaneous_regret_boost_factorto 1.0. In the full algorithm, the 1.1 boost accelerates the accumulation of regrets for under-explored, high-potential actions. Policy Accumulation and Strategy Distillation •VAD-CFR (no_predication): VAD-CFR uses a non-linear projection when deriving the current iter- ation policy from accumulated regrets. This ablation reverts thePolicyFromRegretAccumulator to a standard linear Regret Matching mapping by settingpositive_policy_exponent = 1.0 and removing the anticipatory initial_optimism_factor = 0.0. • VAD-CFR (no_warmstart): One of the most significant discovered features is a hard warm-start delay. This ablation bypasses thewarmup_iterations = 500condition, forcing the algorithm to begin policy averaging from푡=1. This tests whether a “burn-in” period is critical for preventing early, high-variance policies from polluting the final average strategy. Environmental Adaptation • VAD-CFR (no_volatility): The core dynamic of VAD-CFR is its ability to adjust discounting parame- ters based on the perceived volatility of the game state, tracked via an Exponential Weighted Moving Av- erage (EWMA) of instantaneous regrets. This ablation disables thecalculate_adaptive_params 26 Discovering Multiagent Learning Algorithms with Large Language Models Listing 5 | WOP-CFR class WOPRegretAccumulator: def update_accumulate_regret(self, node, iter_num, cfr_regrets): t = float(iter_num + 1) d_pos, d_neg = (t**1.5)/(t**1.5 + 1.0), (t**-0.1)/(t**-0.1 + 1.0) return a: (d_pos if node.cumulative_regret[a] >= 0 else d_neg) * node.cumulative_regret[a] + ↩→ cfr_regrets[a] for a in cfr_regrets class WOPPolicyFromRegretAccumulator: def get_updated_current_policy(self, node, iter_num, cfr_regrets, previous_policy): t = float(iter_num + 1) d_pos, d_neg = (t**1.5)/(t**1.5 + 1.0), (t**-0.1)/(t**-0.1 + 1.0) opt_s = 1.0 / (1.0 + float(iter_num) / 100.0) proj = for a in node.legal_actions: d = d_pos if node.cumulative_regret.get(a, 0.0) >= 0 else d_neg r = d * node.cumulative_regret.get(a, 0.0) + opt_s * cfr_regrets.get(a, 0.0) proj[a] = max(0.0, r) ** 1.5 total = sum(proj.values()) return a: v/total if total > 0 else 1.0/len(proj) for a, v in proj.items() class WOPPolicyAccumulator: def update_accumulate_policy(self, node, iter_num, policy, cfr_regrets, reach, cf_reach): if iter_num < 500: return node.cumulative_policy # Hard Warm-Start weight = (float(iter_num) + 1.0) ** 2.0 # Static Polynomial Weight return a: node.cumulative_policy[a] + weight * reach * policy[a] for a in policy logic, replacing the adaptive volatility scaling with static hyperparameters. This directly tests the value of the meta-adaptation dynamics discovered by the LLM versus a fixed discount schedule. 7.2.2. Code of WOP-CFR See Listing 5. 7.2.3. Detailed Specification of SHOR-PSRO Ablation Components To understand the contribution of each mechanism discovered by AlphaEvolve within the Smoothed Hybrid Optimistic Regret (SHOR-) PSRO framework, we conducted a comprehensive ablation study. The raw SHOR-PSRO algorithm relies on a highly parameterized, asymmetric design. Each ablation isolates a specific heuristic by either neutralizing its parameters or reverting the logic to standard baselines. The following variants correspond to the empirical results presented in Section 4.4, with direct references to the algorithmic components defined in Listing 4. Train/Eval Asymmetry Ablations The raw LLM discovery evolved two distinct, highly specialized solvers for the training-time Oracle generation and the evaluation-time exploitability measurement. • SHOR-PSRO (train_as_eval): This ablation forces the evaluation phase to utilize theSHORTrainMetaStrategySolver. It tests whether the exploratory, high-temperature heuristics used to generate new policies are funda- mentally detrimental when used to measure exact exploitability. •SHOR-PSRO (eval_as_train): This ablation forces the training phase to utilize theSHOREvalMetaStrategySolver, stripping away the dynamic annealing and diversity bonuses during population expansion to test if the training solver’s complexity is genuinely necessary for exploration. Blending and Annealing Ablations SHOR-PSRO’s core innovation is the active interpolation between an Optimistic Regret Matching+ 27 Discovering Multiagent Learning Algorithms with Large Language Models (ORM+) loop and a smoothed best pure strategy, guided by automated schedules. •SHOR-PSRO (no_blending_pure): Removes the ORM+ engine entirely by strictly settinginitial_blending_factor=1.0 andfinal_blending_factor=1.0. The solver relies exclusively on the temperature-smoothed pure strategy. • SHOR-PSRO (no_blending_orm): Removes the pure strategy bias by strictly settinginitial_blending_factor=0.0 and final_blending_factor=0.0. The solver relies exclusively on the ORM+ update loop. •SHOR-PSRO (no_annealing): Disables the dynamic scaling of hyperparameters across PSRO epochs. It freezes theblending_factorat 0.05,temperatureat 0.01, anddiversity_bonus_coeff at 0.001, preventing the solver from transitioning from exploration to exploitation as the population grows. •SHOR-PSRO (fixed_iterations): Disables theiterations_per_policy_scalemechanism, testing whether scaling the internal solver iterations dynamically with the size of the empirical game tensor is a critical mechanism or an over-parameterized heuristic. ORM Engine Heuristic Ablations The underlying ORM+ loop discovered by the LLM contains several specialized micro-mechanics intended to accelerate convergence. • SHOR-PSRO (no_diversity): Removes the uniform exploration incentive by strictly settingdiversity_bonus_coeff=0.0. •SHOR-PSRO (no_momentum): Disables the optimistic update of the payoff gains by setting momentum_beta=0.0, reverting the update rule closer to standard Regret Matching. • SHOR-PSRO (no_gain_norm): Setsgain_normalization=False, disabling the adaptive scal- ing of the optimistic gains matrix, which tests the algorithm’s vulnerability to extreme payoff magni- tudes. Table 2|Exhaustive Algorithmic Audit of SHOR-PSRO Components. Results are reported as IQM Log-Improvement Scores (푠 푔 ). VariantTotal IQM Train IQM Test IQM Distilled Solver PM-PSRO+0.032-0.038+0.059 Train/Eval Asymmetry Ablations train_as_eval+0.048+0.224+0.021 eval_as_train-0.557-0.584-0.541 Blending & Annealing Ablations no_blending_pure (Removes ORM entirely) -1.525-2.292-1.268 no_blending_orm (Removes pure blend)+0.012-0.069+0.020 no_annealing+0.013-0.104+0.016 fixed_iterations-0.038-0.070-0.031 ORM Engine Heuristic Ablations no_diversity+0.007-0.015+0.012 no_momentum-0.017-0.018-0.016 no_gain_norm-0.012+0.012-0.017 7.2.4. Code of PM-PSRO See Listing 6. 28 Discovering Multiagent Learning Algorithms with Large Language Models Listing 6 | PM-PSRO. import numpy as np class PMMetaStrategySolver: """Projection Matching (PM) PSRO Solver. A minimal meta-solver utilizing geometric tangent projection, and a dynamic iteration budget. """ def __init__(self, base_iterations=1000, iter_scale=20): self.base_iterations = base_iterations self.iter_scale = iter_scale def get_meta_strategy(self, game, policy_sets, meta_games): num_players = len(meta_games) num_strats = [m.shape[i] for i, m in enumerate(meta_games)] num_current_policies = num_strats[0] iterations = self.base_iterations + self.iter_scale * (num_current_policies - 1) strategies = [np.ones(s) / s for s in num_strats] duals = [np.zeros(s) for s in num_strats] avg_strategies = [np.zeros(s) for s in num_strats] for _ in range(iterations): for p in range(num_players): payoff_vec = meta_games[p] for other_p in reversed(range(num_players)): if other_p != p: payoff_vec = np.tensordot( payoff_vec, strategies[other_p], axes=([other_p], [0]) ) projected_grad = payoff_vec - np.mean(payoff_vec) duals[p] += projected_grad positive_duals = np.maximum(duals[p], 0) sum_duals = np.sum(positive_duals) if sum_duals > 0: strategies[p] = positive_duals / sum_duals else: strategies[p] = np.ones(num_strats[p]) / num_strats[p] avg_strategies[p] += strategies[p] final_strategies = [] for avg, s in zip(avg_strategies, num_strats): sum_avg = np.sum(avg) if sum_avg > 0: final_strategies.append((avg / sum_avg).tolist()) else: final_strategies.append((np.ones(s) / s).tolist()) return final_strategies 29 Discovering Multiagent Learning Algorithms with Large Language Models 7.3. Evaluated Game Suite We evaluate all algorithms on a suite of 18 game instances from the OpenSpiel framework (Lanctot et al., 2019), spanning five game families. The suite is designed to cover a wide range of structural properties: sequential vs. simultaneous moves, 2–4 players, and game trees ranging from 2 to 347,810 information states with branching factors from 1 to 66. All games in our suite involve imperfect information. Table 3 provides a summary; detailed descriptions follow. Table 3|Summary of the 18 evaluated game instances. All games involve imper- fect information. “Seq” = sequential, “Sim” = simultaneous (converted to sequential via turn_based_simultaneous_game). Information state counts and branching factors are exact, computed by full game tree traversal. Game InstanceFamilyPlayers Type Info States Avg. Actions Action Range Kuhn PokerPoker2Seq122.02 Kuhn Poker (3p)Poker3Seq482.02 Kuhn Poker (4p)Poker4Seq1602.02 Leduc PokerPoker2Seq9362.32–3 Leduc Poker (3p)Poker3Seq25,8002.32–3 Universal PokerPoker2Seq20,1602.42–4 Goofspiel-3Goofspiel2Sim1142.12–3 Goofspiel-4Goofspiel2Sim6,0562.12–4 Goofspiel-5Goofspiel2Sim347,8102.12–5 Goofspiel-3 (limited info) Goofspiel2Sim902.12–3 Goofspiel-4 (limited info) Goofspiel2Sim3,6082.12–4 Goofspiel-5 (limited info) Goofspiel2Sim236,4502.12–5 Liar’s Dice (4-sided)Liar’s Dice2Seq1,0242.01–8 Liar’s Dice (5-sided)Liar’s Dice2Seq5,1202.01–10 Liar’s Dice (6-sided)Liar’s Dice2Seq24,5762.01–12 Colonel BlottoBlotto2Sim266.066 Battleship (2×2)Battleship2Seq10,1984.04 Battleship (3×2)Battleship2Seq160,4916.06–7 7.3.1. Poker Variants Kuhn Poker (Kuhn, 1950). A simplified poker game played with a three-card deck (Jack, Queen, King). Each player is dealt one card and places a single ante. Players then engage in a single round of betting with check/bet/call/fold actions. Despite its simplicity, Kuhn Poker has a non-trivial mixed Nash equilibrium and serves as a canonical benchmark for imperfect-information game-solving algorithms. We evaluate on the standard 2-player version (12 information states) and extended variants with 3 players (48 information states, 4-card deck) and 4 players (160 information states, 5-card deck). Leduc Poker (Southey et al., 2005). A two-round poker game using a deck of six cards (two suits×three ranks). Each player is dealt a single private card, followed by a round of betting; then a single community card is dealt, followed by a second betting round. Hands are ranked by pair (private card matches community card) and then by card rank. Leduc Poker is a standard benchmark for imperfect-information algorithms as it is small enough for exact Nash equilibrium computation yet complex enough to test key algorithmic properties. We evaluate on the 2-player version (936 30 Discovering Multiagent Learning Algorithms with Large Language Models information states) and a 3-player variant (25,800 information states). Universal Poker. OpenSpiel’s parameterized poker game that can represent arbitrary limit and no-limit hold’em variants through the ACPC (Annual Computer Poker Competition) protocol. In its default configuration, it implements a small limit hold’em game with a 4-card deck, a single betting round, and fixed bet sizes. With 20,160 information states, it provides a more complex poker benchmark than Leduc while remaining computationally tractable for tabular methods. 7.3.2. Goofspiel (The Game of Pure Strategy) Goofspiel (Ross, 1971). A simultaneous-move card game in which two players compete to win “prize” cards using their “bid” cards. Each player holds a hand of cards numbered 1 through푛, and a sequence of prize cards (also 1 through푛) is revealed one at a time. In each round, both players simultaneously play a bid card; the higher bid wins the current prize (ties result in the prize being discarded). The player who accumulates the highest total prize value wins. Since players choose actions simultaneously, the game inherently involves imperfect information—each player must commit to a bid without knowing the opponent’s choice. We convert the simultaneous-move game to sequential form via theturn_based_simultaneous_gamewrapper for compatibility with CFR-based algorithms. We evaluate on six variants organized along two dimensions: •Scale:푛∈ 3,4,5cards, yielding progressively larger game trees (114 to 347,810 information states). •Information structure: In the standard version, both players observe each other’s bids after each round. In the limited information version (imp_info=True), players only observe whether they won or lost each round, but not the opponent’s specific bid. Interestingly, the limited-information variant has fewer information states (e.g., 236,450 vs. 347,810 for푛=5) because more game histories are observationally equivalent from each player’s perspective. 7.3.3. Liar’s Dice Liar’s Dice (Lis ` y et al., 2015). A bluffing game in which each player secretly rolls a single die, then players alternate making increasingly higher claims about the total count of a specific face value across all dice. A player may either raise the current claim or challenge (“call liar”) the previous player’s claim. If challenged, all dice are revealed: the challenger wins if the claim was false, and the claimant wins if it was true. We evaluate on variants with 푑 ∈ 4, 5, 6 die faces, yielding 1,024, 5,120, and 24,576 information states respectively. 7.3.4. Colonel Blotto Colonel Blotto (Borel, 1953). A classic resource-allocation game in which two players simultane- ously distribute a fixed budget of units across multiple battlefields. Each battlefield is won by the player who allocates more units to it (ties broken randomly). The player who wins the most battlefields wins the game. In the default OpenSpiel configuration, each player has 10 units to distribute across 3 battlefields (66 possible allocations per player). As a single simultaneous decision, the game has only 2 information states (one per player) but a rich 66×66 payoff matrix with complex mixed Nash equilibria. The game is converted to sequential form via turn_based_simultaneous_game. 31 Discovering Multiagent Learning Algorithms with Large Language Models 7.3.5. Battleship Battleship (Farina et al., 2019). A parametric two-player game inspired by the classic board game, formalized for game-theoretic analysis. Each player secretly places ships on a grid, then players alternate taking shots to locate and sink the opponent’s ships. The game has imperfect information (players do not observe the opponent’s ship placement) and is parameterized by board dimensions, ship configurations, and scoring rules. We evaluate on two configurations: • Battleship 2×2: A 2×2 board with one ship of size 2 and value 2.0, with 3 shots allowed (10,198 information states). •Battleship 3×2: A 3×2 board with the same ship and shot configuration (160,491 information states). 7.3.6. Game Selection Rationale The suite is designed to stress-test algorithm performance across several axes: 1. Number of players: Two-player (most games) vs. multi-player (Kuhn 3p/4p, Leduc 3p). 2.Game tree scale: From 2 information states (Blotto) to 347,810 (Goofspiel-5), testing scalability. 3.Strategic depth: From pure bluffing (poker, Liar’s Dice) to resource allocation (Blotto) to bidding under uncertainty (Goofspiel). 4.Move structure: Sequential (poker, Liar’s Dice, Battleship) vs. simultaneous converted to sequential (Goofspiel, Blotto). 5.Observability: Varying degrees of information—from fully observable bids (Goofspiel) to hidden bids with outcome feedback only (Goofspiel limited info) to hidden card placement (Battleship). 7.4. Results on 18 Games Figures 3 and 4 show full per-game exploitability curves for all 18 games in our evaluation suite for CFR and PSRO variants respectively. 7.5. Additional PSRO Evaluation on Randomly Generated Normal-Form Games To complement the OpenSpiel benchmark with an evaluation that is structurally independent of any specific extensive-form game, we evaluate all PSRO meta-solvers on randomly generated푁- player normal-form games (NFGs). This setting tests the meta-solver itself in isolation, removing any influence of the underlying extensive-form structure that AlphaEvolve might have implicitly overfit to during training. Sampling 1000 NFGs per configuration also provides a large-sample statistical complement to the deterministic per-game evaluation in the main body. Game generation. For each configuration(푁, 퐴), we sample 1000 random푁-player NFGs with퐴 actions per player. Each game is constructed by drawing independent payoff tensors푢 푖 ∈ ℝ 퐴 푁 for each player from eitherN(0,1)(Gaussian) orU[−1,1](Uniform), and then centering across players to enforce constant-sum structure: 푢 푖 ← 푢 푖 − 1 푁 ∑︁ 푁 푗=1 푢 푗 . After centering, Í 푖 푢 푖 (푎)=0 for every joint action profile푎, generalizing two-player zero-sum to the푁-player setting. Distinct random seeds are used across the 1000 sampled games and the two distributions. 32 Discovering Multiagent Learning Algorithms with Large Language Models Why푁 ≥3. We restrict the NFG evaluation to푁 ≥3 because two-player zero-sum NFGs admit a polynomial-time exact solution via linear programming. In that regime the LP-Nash baseline trivially dominates all other meta-solvers and the comparison contains no signal about meta-solver design choices. Experimental setup. Each PSRO run starts from a single random pure strategy per player, expands the population by one exact best response per iteration, and terminates after퐾= 퐴outer iterations (full population growth). We benchmark Uniform, AlphaRank, PRD, RM, SHOR-PSRO, and PM- PSRO under identical conditions; the LP-Nash baseline is omitted as it does not extend to푁 ≥3. Following Agarwal et al. (2021), we report the per-iteration interquartile mean (IQM) of exploitability across the 1000 sampled games, with 95% confidence intervals computed by 50,000 bootstrap resamples at the run level (i.e., resampling games rather than individual iterations, which preserves within-trajectory correlation). Results. Figures 5 and 6 show per-iteration IQM exploitability under Gaussian and Uniform payoffs respectively, across six(푁, 퐴)configurations spanning 3-, 4-, and 5-player games with퐴ranging from 20 to 100 actions. The qualitative pattern is identical across all configurations and both distributions: SHOR-PSRO and PM-PSRO consistently reach lower exploitability than every established baseline, with the gap widening as iteration count grows. Established baselines (Uniform, AlphaRank, PRD, and RM) plateau early — typically before iteration퐴/2 — while SHOR-PSRO and PM-PSRO continue to descend. PM-PSRO begins more slowly during the first∼5 iterations, since its tangent-projected utility signal requires several iterations to accumulate, but matches or surpasses SHOR-PSRO by mid-run in the larger configurations (3P/50A, 3P/100A, 4P/50A). The 95% bootstrap CIs are tighter than line width across most of each curve, indicating that the observed gaps are statistically significant rather than artifacts of game-level variance. Insensitivity to the payoff distribution (Gaussian vs. Uniform results are qualitatively identical) suggests that the discovered solvers’ advantage is not specific to any particular generative model. 7.6. Prompts Listing 7 | Prompt for Evolving CFR Act as an expert in game theory, multiagent learning, online learning and optimization. Your task ↩→ is to iteratively improve a new variant of counterfactual regret minimization. The primary ↩→ goal is to speed up convergence to low-exploitable strategies. Always adhere to best practices in Python coding. A key data structure that is used is infostate_node: ‘python @attr.s class _InfoStateNode(object): """An object wrapping values associated to an information state.""" # The list of the legal actions. legal_actions = attr.ib() index_in_tabular_policy = attr.ib() # Map from information states string representations and actions to the # counterfactual regrets, accumulated over the policy iterations cumulative_regret = attr.ib(factory=lambda: collections.defaultdict(float)) # Same as above for the cumulative of the policy probabilities computed # during the policy iterations cumulative_policy = attr.ib(factory=lambda: collections.defaultdict(float)) ‘ 33 Discovering Multiagent Learning Algorithms with Large Language Models You are allowed to modify three key components of CFR: (1) how are the regret values accumulated ↩→ at each infoset (RegretAccumulator) (2) how to obtain a current policy at the current ↩→ iteration from the current cumulative_regret (PolicyFromRegretAccumulator) and (3) how to ↩→ accumulate policies across iterations to compute an average policy (PolicyAccumulator). # Prior programs Previously we found that the following programs performed well on the task at hand: previous_programs # Current program Here is the current program we are trying to improve (you will need to propose a modification to ↩→ it below): code # *SEARCH/REPLACE block* Rules: Every *SEARCH/REPLACE block* must use this format: 1. The opening fence: ‘python 2. The start of search block: <<<<<<< SEARCH 3. A contiguous chunk of up to 4 lines to search for in the existing source code 4. The dividing line: ======= 5. The lines to replace into the source code 6. The end of the replace block: >>>>>>> REPLACE 7. The closing fence: ‘ Every *SEARCH* section must *EXACTLY MATCH* the existing file content, character for character, ↩→ including all comments, docstrings, etc. *SEARCH/REPLACE* blocks will replace *all* matching occurrences. Include enough lines to make the SEARCH blocks uniquely match the lines to change. Keep *SEARCH/REPLACE* blocks concise. Break large *SEARCH/REPLACE* blocks into a series of smaller blocks that each change a small ↩→ portion of the file. Include just the changing lines, and a few surrounding lines if needed for uniqueness. Do not include long runs of unchanging lines in *SEARCH/REPLACE* blocks. To move code within a file, use 2 *SEARCH/REPLACE* blocks: 1 to delete it from its current ↩→ location, 1 to insert it in the new location. Make sure that the changes you propose are consistent with each other. For example, if you refer ↩→ to a new config variable somewhere, you should also propose a change to add that variable. Example: ‘python <<<<<<< SEARCH return total_loss ======= # Add sparsity-promoting regularization to the loss. total_loss += self.hypers.l1_reg_weight * l1_reg return total_loss replace ‘ and ‘python <<<<<<< SEARCH return hyper.zipit([ ======= return hyper.zipit([ hyper.uniform(’l1_reg_weight’, hyper.interval(0.0, 0.01)), replace ‘ lazy_prompt ONLY EVER RETURN CODE IN A *SEARCH/REPLACE BLOCK*! 34 Discovering Multiagent Learning Algorithms with Large Language Models # Task task_instruction focus_sentence trigger_chain_of_thought Describe each change with a *SEARCH/REPLACE block*. Listing 8 | Prompt Config for Evolving CFR "template": "prompt_sampler_type": "TemplatePromptSampler", "probability": 1.0, "template_path": "meta_cfr_prompt.md", "format_args": "lazy_prompt": [ [" are diligent and tireless! NEVER leave comments describing code without ↩→ implementing it! always COMPLETELY IMPLEMENT the needed code!", 0.5], ["", 0.5] ], "task_instruction": [ ["Propose modifications to current program that combine the strengths of all the programs ↩→ above and achieved high scores on the task.", 0.25], ["Suggest an unconventional modification to improve our implementation.", 0.25], ["Suggest a new idea to improve the code.", 0.25], ["Suggest a new idea to improve the code that is inspired by your expert knowledge of game ↩→ theory, multiagent reinforcement learning, economics, stochastic processes, machine ↩→ learning, and optimization.", 0.25] ], "focus_sentence": [ ["Focus on simplifying the code, instead of adding new functionality.", 0.2], ["", 0.8] ], "trigger_chain_of_thought": [ [" with providing a comprehensive explanation for the proposed changes including\ ↩→ n* The specific issue or limitation it addresses. * The underlying rationale and expected ↩→ impact. need to specify this *before providing code*. ", 0.5], [" ", 0.5] ] Listing 9 | Prompt for Evolving PSRO Act as an expert in game theory, multiagent learning, online learning and optimization. Your task ↩→ is to iteratively improve a variant of Policy-Space Response Oracles (PSRO). The primary ↩→ goal is to speed up convergence to low-exploitable strategies. # PSRO Overview PSRO iteratively builds a population of policies for each player and computes meta-strategies ( ↩→ distributions over policies) to guide training and evaluation. **Each iteration:** 1. **Empirical game**: Simulate payoffs between all policy combinations to form a game tensor. 2. **Train-time meta-strategy**: Compute a distribution over current policies for each player. ↩→ This determines what opponents the best-response oracle trains against. 3. **Best response**: Add a new policy for each player that best responds to opponents’ train-time ↩→ meta-strategies. 4. **Eval-time meta-strategy**: Compute a (possibly different) distribution for evaluation, e.g., ↩→ to measure exploitability. **Your task**: Improve both the **train-time** and **eval-time** meta-strategy solvers. These ↩→ serve different purposes: train-time guides population growth, eval-time assesses solution ↩→ quality. # Available Utilities **Best Response** 35 Discovering Multiagent Learning Algorithms with Large Language Models - ‘BestResponsePolicy(game, player_id, policy)‘: Returns a best-response policy for ‘player_id‘ ↩→ against ‘policy‘. - Use ‘.value(game.new_initial_state())‘ to get the BR value. **Policy Aggregation** - ‘PolicyAggregator(game).aggregate(pids, policy_sets, weights)‘: Creates a mixed policy from ↩→ weighted pure policies. - ‘pids‘: ‘list(range(game.num_players()))‘ - ‘weights‘: ‘[weights_p0, weights_p1, ...]‘, each matching ‘len(policy_sets[p])‘ **Policy Evaluation** - ‘expected_game_score.policy_value(state, joint_policy)‘: Returns expected payoffs (list, one per ↩→ player). - ‘joint_policy‘: ‘[policy_p0, policy_p1, ...]‘ Always adhere to best practices in Python coding. # Prior programs Previously we found that the following programs performed well on the task at hand: previous_programs # Current program Here is the current program we are trying to improve (you will need to propose a modification to ↩→ it below): code # *SEARCH/REPLACE block* Rules: Every *SEARCH/REPLACE block* must use this format: 1. The opening fence: ‘python 2. The start of search block: <<<<<<< SEARCH 3. A contiguous chunk of up to 4 lines to search for in the existing source code 4. The dividing line: ======= 5. The lines to replace into the source code 6. The end of the replace block: >>>>>>> REPLACE 7. The closing fence: ‘ Every *SEARCH* section must *EXACTLY MATCH* the existing file content, character for character, ↩→ including all comments, docstrings, etc. *SEARCH/REPLACE* blocks will replace *all* matching occurrences. Include enough lines to make the SEARCH blocks uniquely match the lines to change. Keep *SEARCH/REPLACE* blocks concise. Break large *SEARCH/REPLACE* blocks into a series of smaller blocks that each change a small ↩→ portion of the file. Include just the changing lines, and a few surrounding lines if needed for uniqueness. Do not include long runs of unchanging lines in *SEARCH/REPLACE* blocks. To move code within a file, use 2 *SEARCH/REPLACE* blocks: 1 to delete it from its current ↩→ location, 1 to insert it in the new location. Make sure that the changes you propose are consistent with each other. For example, if you refer ↩→ to a new config variable somewhere, you should also propose a change to add that variable. Example: ‘python <<<<<<< SEARCH return total_loss ======= # Add sparsity-promoting regularization to the loss. total_loss += self.hypers.l1_reg_weight * l1_reg return total_loss replace ‘ and ‘python 36 Discovering Multiagent Learning Algorithms with Large Language Models <<<<<<< SEARCH return hyper.zipit([ ======= return hyper.zipit([ hyper.uniform(’l1_reg_weight’, hyper.interval(0.0, 0.01)), replace ‘ lazy_prompt ONLY EVER RETURN CODE IN A *SEARCH/REPLACE BLOCK*! # Task task_instruction focus_sentence difficulty_hint exploration_nudge ↩→ trigger_chain_of_thought Describe each change with a *SEARCH/REPLACE block*. Listing 10 | Prompt Config for Evolving PSRO "template": "prompt_sampler_type": "TemplatePromptSampler", "probability": 1.0, "template_path": "meta_psro_prompt.md", "format_args": "lazy_prompt": [ [" are diligent and tireless! NEVER leave comments describing code without ↩→ implementing it! always COMPLETELY IMPLEMENT the needed code!", 0.5], ["", 0.5] ], "task_instruction": [ ["Propose modifications to current program that combine the strengths of all the programs ↩→ above and achieved high scores on the task.", 0.25], ["Suggest an unconventional modification to improve our implementation.", 0.25], ["Suggest a new idea to improve the code.", 0.25], ["Suggest a new idea to improve the code that is inspired by your expert knowledge of game ↩→ theory, multiagent reinforcement learning, economics, stochastic processes, machine ↩→ learning, and optimization.", 0.25] ], "focus_sentence": [ ["Focus on simplifying the code, instead of adding new functionality.", 0.2], ["", 0.8] ], "trigger_chain_of_thought": [ [" with providing a comprehensive explanation for the proposed changes including\ ↩→ n* The specific issue or limitation it addresses. * The underlying rationale and expected ↩→ impact. need to specify this *before providing code*. ", 0.5], [" ", 0.5] ] 37 Discovering Multiagent Learning Algorithms with Large Language Models 02505007501000 CFR Iteration 10 16 10 14 10 12 10 10 10 8 10 6 10 4 10 2 10 0 Exploitability Kuhn Poker 02505007501000 CFR Iteration 10 5 10 4 10 3 10 2 10 1 10 0 Leduc Poker 02505007501000 CFR Iteration 10 16 10 14 10 12 10 10 10 8 10 6 10 4 10 2 10 0 Kuhn Poker (Players=3) 02505007501000 CFR Iteration 10 4 10 3 10 2 10 1 10 0 Leduc Poker (Players=3) 02505007501000 CFR Iteration 10 16 10 13 10 10 10 7 10 4 10 1 Kuhn Poker (Players=4) 02505007501000 CFR Iteration 10 65 10 56 10 47 10 38 10 29 10 20 10 11 10 2 Goofspiel (Num Cards=3) 02505007501000 CFR Iteration 10 16 10 14 10 12 10 10 10 8 10 6 10 4 10 2 10 0 Goofspiel (Num Cards=4) 02505007501000 CFR Iteration 10 4 10 3 10 2 10 1 10 0 Goofspiel (Num Cards=5) 02505007501000 CFR Iteration 10 65 10 56 10 47 10 38 10 29 10 20 10 11 10 2 Goofspiel (Num Cards=3,Lim. Info.) 02505007501000 CFR Iteration 10 7 10 6 10 5 10 4 10 3 10 2 10 1 10 0 Goofspiel (Num Cards=4,Lim. Info.) 02505007501000 CFR Iteration 10 4 10 3 10 2 10 1 10 0 Goofspiel (Num Cards=5,Lim. Info.) 02505007501000 CFR Iteration 10 16 10 13 10 10 10 7 10 4 10 1 Liars Dice (Dice Sides=4) 02505007501000 CFR Iteration 10 6 10 5 10 4 10 3 10 2 10 1 10 0 Liars Dice (Dice Sides=5) 02505007501000 CFR Iteration 10 4 10 3 10 2 10 1 10 0 Liars Dice (Dice Sides=6) 02505007501000 CFR Iteration 10 5 10 4 10 3 10 2 10 1 Blotto 02505007501000 CFR Iteration 10 15 10 13 10 11 10 9 10 7 10 5 10 3 10 1 Battleship 2X2 1 2 02505007501000 CFR Iteration 10 7 10 6 10 5 10 4 10 3 10 2 10 1 10 0 Battleship 3X2 1 2 02505007501000 CFR Iteration 10 2 10 1 10 0 10 1 10 2 Universal Poker 0.00.20.40.60.81.0 0.0 0.2 0.4 0.6 0.8 1.0 0.00.20.40.60.81.0 0.0 0.2 0.4 0.6 0.8 1.0 All Games Performance CFRCFR PLUSLCFRDCFRPCFR PLUSDPCFR PLUSHS PCFR PLUS 30VAD CFRWOP CFR Figure 3 | CFR variants performances on All Games. 38 Discovering Multiagent Learning Algorithms with Large Language Models 0255075100 PSRO Iteration 10 10 10 8 10 6 10 4 10 2 10 0 Exploitability Kuhn Poker 0255075100 PSRO Iteration 10 1 10 0 Leduc Poker 0255075100 PSRO Iteration 10 5 10 4 10 3 10 2 10 1 10 0 Kuhn Poker (Players=3) 0255075100 PSRO Iteration 10 1 10 0 Leduc Poker (Players=3) 0255075100 PSRO Iteration 10 4 10 3 10 2 10 1 10 0 Kuhn Poker (Players=4) 0255075100 PSRO Iteration 10 37 10 32 10 27 10 22 10 17 10 12 10 7 10 2 Goofspiel (Num Cards=3) 0255075100 PSRO Iteration 10 3 10 2 10 1 10 0 Goofspiel (Num Cards=4) 0255075100 PSRO Iteration 10 0 2 × 10 1 3 × 10 1 4 × 10 1 6 × 10 1 Goofspiel (Num Cards=5) 0255075100 PSRO Iteration 10 37 10 32 10 27 10 22 10 17 10 12 10 7 10 2 Goofspiel (Num Cards=3,Lim. Info.) 0255075100 PSRO Iteration 10 2 10 1 10 0 Goofspiel (Num Cards=4,Lim. Info.) 0255075100 PSRO Iteration 10 0 2 × 10 1 3 × 10 1 4 × 10 1 6 × 10 1 Goofspiel (Num Cards=5,Lim. Info.) 0255075100 PSRO Iteration 10 2 10 1 10 0 Liars Dice (Dice Sides=4) 0255075100 PSRO Iteration 10 1 10 0 Liars Dice (Dice Sides=5) 0255075100 PSRO Iteration 10 1 10 0 Liars Dice (Dice Sides=6) 0255075100 PSRO Iteration 10 11 10 9 10 7 10 5 10 3 10 1 Blotto 0255075100 PSRO Iteration 10 12 10 10 10 8 10 6 10 4 10 2 10 0 Battleship 2X2 1 2 0255075100 PSRO Iteration 10 0 Battleship 3X2 1 2 0255075100 PSRO Iteration 10 1 10 2 Universal Poker 0.00.20.40.60.81.0 0.0 0.2 0.4 0.6 0.8 1.0 0.00.20.40.60.81.0 0.0 0.2 0.4 0.6 0.8 1.0 All Games Performance UNIFORMNASHALPHARANKPRDRMSHORPM Figure 4 | PSRO variants performances on All Games. 39 Discovering Multiagent Learning Algorithms with Large Language Models 5101520 PSRO Iteration 10 0 Exploitability (IQM) 3P / 20A / Gaussian Payoffs 0153045 PSRO Iteration 10 1 10 0 3P / 50A / Gaussian Payoffs 0255075100 PSRO Iteration 10 1 10 0 3P / 100A / Gaussian Payoffs 5101520 PSRO Iteration 10 1 10 0 Exploitability (IQM) 4P / 20A / Gaussian Payoffs 0153045 PSRO Iteration 10 1 10 0 10 1 4P / 50A / Gaussian Payoffs 5101520 PSRO Iteration 10 1 10 0 10 1 5P / 20A / Gaussian Payoffs PSRO on Random NFG IQM Exploitability with 95% Bootstrap CI UNIFORMALPHARANKPRDRMSHORPM Figure 5 | PSRO variants performances on Gaussian payoff games. 5101520 PSRO Iteration 10 1 10 0 Exploitability (IQM) 3P / 20A / Uniform Payoffs 0153045 PSRO Iteration 10 1 10 0 3P / 50A / Uniform Payoffs 0255075100 PSRO Iteration 10 1 10 0 3P / 100A / Uniform Payoffs 5101520 PSRO Iteration 10 1 10 0 Exploitability (IQM) 4P / 20A / Uniform Payoffs 0153045 PSRO Iteration 10 1 10 0 4P / 50A / Uniform Payoffs 5101520 PSRO Iteration 10 1 10 0 5P / 20A / Uniform Payoffs PSRO on Random NFG IQM Exploitability with 95% Bootstrap CI UNIFORMALPHARANKPRDRMSHORPM Figure 6 | PSRO variants performances on Uniform payoff games. 40