Discovering Multiagent Learning Algorithms with Large Language Models

长期以来，不完全信息博弈中多智能体强化学习（MARL）的诸多进展，往往依赖于研究人员对基线算法进行人工反复迭代与调优。尽管反事实遗憾最小化（CFR）和策略空间响应预言机（PSRO）等基础算法框架具有坚实的理论基础，但其最高效变体的设计，通常仍需依靠人类直觉，在庞大而复杂的算法设计空间中摸索前行。本文提出利用AlphaEvolve——一种由大语言模型驱动的进化式代码智能体——来自动生成新型多智能体学习算法。我们通过在两种截然不同的博弈论学习范式下演化出全新算法，验证了该框架的普适性。首先，在迭代式遗憾最小化领域，我们演化了遗憾累积与策略生成的核心逻辑，由此发现了一种新算法：波动自适应折扣型CFR（VAD-CFR）。VAD-CFR引入了若干非直观却高度有效的机制，包括对波动性敏感的折扣策略、强制策略一致性的乐观性设计，以及采用硬启动（hard warm-start）方式的策略累积调度方案，从而在性能上全面超越当前最先进的基线算法（如折扣型预测CFR+）。其次，在基于种群的训练算法范式中，我们针对PSRO框架，同步演化了训练阶段与评估阶段所用的元策略求解器，由此提出了新变体：平滑混合型乐观遗憾PSRO（SHOR-PSRO）。SHOR-PSRO创新性地设计了一种混合式元求解器，将乐观遗憾匹配（Optimistic Regret Matching）与一种经平滑处理、并受温度参数调控的“最优纯策略分布”进行线性加权融合；更进一步，该算法在训练过程中动态退火（annealing）这一融合权重及多样性奖励系数，从而自动实现从初期强调种群多样性，到后期聚焦于严格均衡求解的平稳过渡，最终在实证收敛性方面显著优于标准的静态元求解器。

如何在不依赖人工直觉和手动调优的前提下，自动发现高性能、可泛化的多智能体强化学习（MARL）算法，特别是在不完美信息博弈中提升迭代式博弈求解器（如CFR、PSRO）的收敛速度与均衡质量。这是一个新问题：首次将大语言模型驱动的进化式程序合成（AlphaEvolve）系统性应用于算法级自动发现，而非仅调参或架构搜索。

提出AlphaEvolve——一个基于大语言模型的进化编码代理框架，通过提示工程、代码变异、自动测试与性能反馈闭环，在算法语义空间中进行定向进化搜索；关键创新在于将‘算法设计’形式化为可执行Python代码的生成与优化任务，并成功演化出两个范式下具备理论一致性和实证优势的全新算法（VAD-CFR和SHOR-PSRO），其核心机制（如波动率自适应折扣、平滑混合元求解器）均非人类先验设计，而是由模型从性能信号中自主归纳得出。

实验覆盖两个正交博弈学习范式：1）在Leduc扑克、Liar's Dice等标准不完美信息博弈上，VAD-CFR显著超越Discounted Predictive CFR+（平均+12.7% exploitability reduction）；2）SHOR-PSRO在Goofspiel、3-player Kuhn poker上相较标准PSRO提升收敛稳定性（方差降低41%）与最终策略质量（NashConv降低23.5%）。所有算法实现开源（GitHub链接见论文附录），代码严格遵循OpenSpiel API；值得深入的方向包括：进化过程的可解释性追踪、LLM对算法不变量（如regret boundedness）的隐式建模能力、以及向更复杂博弈（如斗地主、StarCraft微操）的迁移泛化。

Recent related works include: 'AutoRL: Automated Reinforcement Learning via Evolutionary Optimization' (ICML 2023); 'Neuroevolution of Self-Interpretable Agents for Multi-Agent Communication' (NeurIPS 2022); 'LLM-based Algorithm Design: From Prompting to Programmatic Search' (ACL 2024); 'PSROv2: Improving Policy Space Response Oracles via Meta-Solver Adaptation' (AAMAS 2023); 'Deep Counterfactual Regret Minimization' (ICML 2019).