用大语言模型发现多智能体学习算法 Discovering Multiagent Learning Algorithms with Large Language Models
LLM驱动的进化搜索自动发现并蒸馏CFR和PSRO新算法
前置知识
扩展式博弈 (Extensive-Form Games, EFG)
扩展式博弈是描述序贯决策交互的数学框架，形式化为 $\Gamma = \langle N, H, Z, A, u, I \rangle$。其中 $N$ 是玩家集合，$H$ 是所有可能的历史序列，$Z \subseteq H$ 是终止历史。不完全信息通过信息集 $I_i$ 建模——玩家无法区分同一信息集内的不同历史（如看不到对手的底牌）。策略 $\sigma_i(I)$ 在每个信息集上定义动作的概率分布，纳什均衡 $\sigma^*$ 是没有任何玩家能通过单方面偏离来提高收益的策略组合。可利用度 $\text{Expl}(\sigma) = \frac{1}{N} \sum_{i \in N} \max_{\sigma'_i} u_i(\sigma'_i, \sigma_{-i}) - u_i(\sigma)$ 衡量策略偏离均衡的程度，是本文的核心评估指标。
本文所有算法都在扩展式博弈框架下运行，可利用度是最主要的性能指标，理解这一框架是读懂实验结果的前提。
反事实遗憾最小化 (Counterfactual Regret Minimization, CFR)
CFR 是一种迭代算法，通过最小化反事实遗憾来逼近纳什均衡。它将全局遗憾最小化分解为每个信息集上的局部问题。在迭代 $t$，瞬时反事实遗憾定义为 $r^t_i(I, a) = v_i(\sigma^t, I, a) - \sum_{a'} \sigma^t_i(I, a') v_i(\sigma^t, I, a')$，其中 $v_i$ 是反事实值。标准 CFR 线性累积遗憾 $R^T_i(I, a) = \sum_{t=1}^T r^t_i(I, a)$，通过遗憾匹配（Regret Matching）从累积遗憾派生策略：$\sigma^{t+1}_i(I, a) \propto \max(R^t_i(I, a), 0)$。最终输出的是加权平均策略。已有变体包括 CFR+（下界归零+线性加权）、DCFR（折扣累积）、PCFR+（预测性）等。
CFR 是本文演化的两大范式之一，理解其标准更新规则才能理解 VAD-CFR 和 WOP-CFR 的创新之处。
策略空间响应预言机 (Policy Space Response Oracles, PSRO)
PSRO 是一种元求解器框架，泛化了双预言机算法。它维护每个玩家的策略种群 $\Pi_i = \{\sigma^1_i, \ldots, \sigma^k_i\}$，在元博弈（Meta-Game）上操作，元博弈的收益张量 $M$ 记录策略两两对抗的期望效用。每个 epoch 执行三步：(1) 元策略求解器（MSS）计算种群上的混合策略 $\phi_i$，(2) 训练新策略作为对手元策略的最优响应，(3) 将新策略加入种群并更新收益张量。标准变体使用均匀分布或纳什均衡作为 MSS。本文将训练时和评估时的 MSS 分离为两个可独立演化的类，给予 LLM 最大的设计自由度。
PSRO 是本文演化的另一大范式，SHOR-PSRO 和 PM-PSRO 的核心创新都在元策略求解器的设计上。
AlphaEvolve
AlphaEvolve 是 Google DeepMind 开发的分布式进化编码代理系统，利用大语言模型（本文使用 Gemini 2.5 Pro）进行语义进化。与传统超参数优化或遗传编程不同，它将算法的源代码视为基因组，使用 LLM 作为智能遗传算子——执行变异来重写逻辑、引入新的控制流、注入新的符号操作。系统维护一个种群，按适应度采样父代，将源代码交给 LLM 并提示'修改以下代码以提高适应度'，生成候选解在代理游戏上评估后加入种群。
AlphaEvolve 是本文方法论的核心框架，理解其工作原理才能理解算法发现过程。
IQM 对数改进分数 (Interquartile Mean Log-Improvement Score)
本文提出的消融评估指标。对于每个游戏 $g$，定义对数改进分数 $s_g = \log_{10}(\text{Expl}(g)_{\text{raw}}) - \log_{10}(\text{Expl}(g)_{\text{abl}})$。正分 $s_g > 0$ 表示消融后的算法比原始发现更好，说明被移除的组件是过度参数化的；负分 $s_g < 0$ 表示性能下降。IQM 计算中间 50% 分数的均值，剔除上下各 25% 的极端值，对异常值高度鲁棒。论文分别报告训练集 IQM（诊断过拟合）、测试集 IQM（衡量泛化）和总体 IQM（全局鲁棒性）。
这是本文消融研究的核心评估方法，理解它才能理解 Table 1 和 Table 2 中的消融结果及其含义。
研究动机
多智能体强化学习（MARL）在不完全信息博弈中的算法设计长期以来高度依赖研究者的手工迭代优化。以反事实遗憾最小化（CFR）为例，从标准 CFR 到 CFR+、DCFR、PCFR+ 等变体，每一步改进都需要研究者凭借直觉在巨大的组合空间中探索遗憾折扣方式、策略更新规则等结构性选择，往往默认使用数学上易处理的启发式方法（如线性平均或固定折扣），这些方法未必是最优的。类似地，PSRO 框架中的元策略求解器设计也是一个开放性问题，现有方法如均匀分布、纳什均衡、AlphaRank、投影复制动态（PRD）、遗憾匹配（RM）等各有局限，没有统一的最优解。这种手动设计范式严重限制了算法发现的效率和可能性。
本文的目标是本文的目标是利用大语言模型（LLM）驱动的进化搜索来自动化多智能体学习算法的设计过程。具体而言，作者将 Google DeepMind 的 AlphaEvolve 框架应用于两个不同的博弈论范式——CFR 和 PSRO 的设计空间，期望发现能够与最先进的人工设计基线竞争的新算法。同时，由于 LLM 倾向于在特定训练集上过拟合，作者还希望通过系统性的训练-测试消融研究来识别真正驱动泛化的核心机制，并将原始发现蒸馏为简洁、可解释的最小求解器。
与已有工作不同的是，本文的独特切入角度在于两个关键创新：第一，与以往在受限搜索空间内操作或依赖神经网络参数化的方法不同，本文将算法的完整源代码作为搜索空间，暴露多个可演化的组件类（如 CFR 的 RegretAccumulator、PolicyFromRegretAccumulator、PolicyAccumulator 三个类），使搜索空间足以涵盖所有已知 CFR 变体作为特例。第二，本文提出了一个形式化的训练-测试分割消融方法论来审计 LLM 的发现——通过 IQM 对数改进分数系统性地识别哪些机制是过拟合的装饰、哪些是真正驱动泛化的核心，然后通过蒸馏去除冗余复杂性。这种'LLM 提出候选机制 → 训练-测试消融揭示泛化能力 → 研究者蒸馏幸存者'的人机协作流水线是之前工作所没有的。
核心方法
本文的整体技术路线可以概括为：用 LLM 驱动的进化搜索在算法设计空间中探索，发现原始算法，然后通过训练-测试消融蒸馏出最小核心。具体来说，作者使用 AlphaEvolve 框架，将 CFR 和 PSRO 算法的核心更新循环分解为多个可演化的 Python 类，以标准实现（CFR+ 或 Uniform PSRO）作为种子程序。每轮进化中，按适应度采样父代程序，将其源代码交给 Gemini 2.5 Pro 并提示'修改以下代码以提高适应度（降低可利用度）'，生成候选解在训练游戏集上评估后加入种群。适应度函数包含每个训练游戏的负可利用度和它们的平均值，采用多目标评分。经过进化搜索后，作者通过系统性消融研究识别原始发现中的核心机制，蒸馏出简洁的数学形式。
本文的核心创新在于三个层面：（1）将算法源代码作为进化搜索的基因组，而非传统的超参数或神经网络权重，使 LLM 能够执行语义级别的变异——重写逻辑、引入新控制流、注入新符号操作，从而超越简单参数调优发现非直觉的机制。（2）将 CFR 的更新循环分解为三个独立可演化的类（RegretAccumulator 处理瞬时遗憾的折扣/截断、PolicyFromRegretAccumulator 定义从累积遗憾派生策略的投影机制、PolicyAccumulator 决定当前策略如何被吸收进最终平均策略），将 PSRO 的训练和评估元策略求解器分离为两个独立可演化的类，给予了 LLM 最大的设计自由度。（3）提出训练-测试分割消融方法论，用 IQM 对数改进分数系统性地分离过拟合的复杂性和真正的泛化驱动力，然后通过蒸馏保留最小核心。这与之前直接发布原始产物或一次性手动简化的工作有本质区别。
方法步骤详情
方法分为三个阶段。第一阶段是进化搜索：以 CFR+（CFR 范式）或 Uniform PSRO（PSRO 范式）作为种子程序，将其核心更新循环拆解为可演化的 Python 类（CFR 为 3 个类：RegretAccumulator、PolicyFromRegretAccumulator、PolicyAccumulator；PSRO 为 2 个类：TrainMetaStrategySolver、EvalMetaStrategySolver），每个类有固定的函数签名。AlphaEvolve 维护一个程序种群，每轮按适应度采样父代，将源代码交给 Gemini 2.5 Pro 进行语义变异，候选解在 4 个训练游戏（3 人 Kuhn Poker、2 人 Leduc Poker、4 牌 Goofspiel、5 面 Liar's Dice）上评估负可利用度，有效候选加入种群。第二阶段是消融审计：对原始发现（VAD-CFR 和 SHOR-PSRO）进行逐一特征消融，移除每个组件后在训练集和测试集上计算 IQM 对数改进分数 $s_g = \log_{10}(\text{Expl}(g)_{\text{raw}}) - \log_{10}(\text{Expl}(g)_{\text{abl}})$，区分过拟合的装饰性机制和真正的泛化驱动力。第三阶段是蒸馏：保留消融研究中识别出的核心机制，去除所有次要启发式，产生最小化求解器（WOP-CFR 和 PM-PSRO）。
技术新颖性
本文的技术新颖性体现在多个方面。首先，在算法发现范式上，与 AutoML-Zero 等从基本数学操作进化完整算法、或以往在受限搜索空间内搜索的方法不同，本文在结构化的算法骨架上进行进化，暴露多个相互作用的组件而非单一损失函数或更新规则，使搜索既有结构约束又有足够的表达力。其次，在消融方法论上，之前的工作要么直接发布 LLM 的原始产物，要么进行一次性手动简化，本文首次提出了形式化的训练-测试分割消融框架，用 IQM 统计量系统性地审计每个组件对泛化的贡献。最后，在具体算法发现上，VAD-CFR 的极端非对称折扣（负遗憾指数 $\beta = -0.1$）和硬热启动（500 轮暂停平均策略累积）、PM-PSRO 的切线投影效用作为遗憾信号等都是非直觉的机制创新。
实验结果
本文在 18 个游戏的评估套件上进行了全面实验，涵盖 Poker、Goofspiel、Liar's Dice、Blotto 和 Battleship 五个游戏家族。在 CFR 范式中，进化搜索发现了 VAD-CFR（波动率自适应折扣 CFR），它在所有 18 个游戏中排名前三，在其中 15 个游戏中达到最低可利用度。消融研究揭示了三个真正的泛化驱动力：硬热启动（训练 IQM $s_{\text{train}} = -5.256$，测试 IQM $s_{\text{test}} = -2.003$）、极端非对称折扣（$s_{\text{train}} = -4.192$，$s_{\text{test}} = -1.065$）和乐观预测（$s_{\text{train}} = -7.029$，$s_{\text{test}} = -0.905$），而 EWMA 波动率追踪（$s_{\text{test}} = -0.029$）和瞬时遗憾提升（$s_{\text{test}} = -0.204$）对泛化贡献甚微。蒸馏后的 WOP-CFR 仅保留这三个核心机制，在测试集上实现了 $+0.119$ 的 IQM 改进，在所有 18 个游戏中排名前三，14 个游戏中达到最低可利用度。在 PSRO 范式中，SHOR-PSRO 在所有 18 个游戏中排名前三，12 个游戏中达到最低可利用度。消融发现 ORM+ 循环是不可否认的基础引擎（移除后 $s_{\text{train}} = -2.292$，$s_{\text{test}} = -1.268$），而混合混合和动态调度对泛化有负面影响。蒸馏后的 PM-PSRO 使用切线投影效用替代标准遗憾信号，实现了 $+0.059$ 的测试 IQM 改进。作者还在 1000 个随机采样的 $N$ 人 $A$ 动作常数和标准形式博弈上验证了这些发现。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| CFR 范式 - 训练游戏（3人Kuhn Poker, 2人Leduc Poker, 4牌Goofspiel, 5面Liar's Dice） | 可利用度（Exploitability, 对数尺度, 1000轮迭代） | VAD-CFR 在所有训练游戏中排名顶尖，3人Kuhn Poker中显著低于所有基线 | CFR, CFR+, LCFR, DCFR, PCFR+, DPCFR+, HS-PCFR+(30) | 15/18游戏达到最低可利用度，WOP-CFR蒸馏后测试IQM +0.119 |
| CFR 范式 - 测试游戏（4人Kuhn Poker, 3人Leduc Poker, 5牌Goofspiel, 6面Liar's Dice） | 可利用度（Exploitability, 对数尺度, 1000轮迭代） | WOP-CFR 在测试集上比VAD-CFR更好（IQM +0.119） | VAD-CFR 原始发现 | 3人Leduc Poker中VAD-CFR低于10^-3，多数基线在更高水平停滞 |
| PSRO 范式 - 训练游戏 | 可利用度（Exploitability, 对数尺度, K=100轮PSRO） | SHOR-PSRO 在3人Kuhn Poker中低于10^-3 | Uniform, Nash, AlphaRank, PRD, RM | 比PRD和RM显著更快收敛，PM-PSRO蒸馏后测试IQM +0.059 |
| PSRO 范式 - 测试游戏 | 可利用度（Exploitability, 对数尺度, K=100轮PSRO） | SHOR-PSRO和PM-PSRO在所有18个游戏中排名前三 | Uniform, Nash, AlphaRank, PRD, RM | 12/18游戏达到最低可利用度，6面Liar's Dice中展现明显优势 |
局限与改进
作者在论文中坦诚地列出了六个方面的局限性：(i) 报告的算法反映的是单次 AlphaEvolve 运行轨迹，未刻画独立进化运行之间的方差，蒸馏组件在不同运行间的稳定性尚未经验验证，尽管每个组件都有独立于单次运行的合理动机。(ii) 首页 IQM 主要由训练/测试集之间共享三个游戏家族的族内泛化主导，族外泛化（Blotto、Battleship）仅限于附录中展示的内容。(iii) 蒸馏过程需要人类判断来决定保留或简化哪些组件，流水线是人机协作的而非完全自主的。(iv) 没有提供形式化的收敛保证。PM-PSRO 使用切线投影效用作为标准 RM 中的遗憾信号，与投影动态共享几何步骤但不等价；WOP-CFR 的组件受 DCFR 和 PCFR+ 启发但其特定组合是经验性的而非理论驱动的。(v) 仅与基于表格的基线比较，未包含 Deep CFR 或神经自课程 PSRO。(vi) 精确可利用度计算将评估限制在少于 35 万信息状态的游戏中。此外，从我自己的观察来看，论文未报告计算成本（AlphaEvolve 运行需要多少 LLM 调用和计算时间），也未讨论发现的算法是否具有理论收敛性保证。
独立分析的弱点
本文有几个值得关注的弱点。首先，AlphaEvolve 的搜索效率和计算成本未被充分讨论——进化搜索可能需要大量 LLM 调用和游戏评估，论文未报告总计算量，这使得读者难以评估该方法的实际可行性。改进方向是引入更高效的搜索策略，如基于梯度的代码变异或分层搜索。其次，蒸馏过程高度依赖人类判断来决定保留哪些组件，这限制了方法的自动化程度。可以探索自动化的组件重要性排序和选择方法，如基于信息论的特征选择。第三，评估局限于小规模表格型博弈（少于35万信息状态），未涉及大规模博弈或深度 RL 场景。改进方向是将发现的机制（如极端非对称折扣、切线投影）扩展到函数近似设置。第四，单次运行结果的可靠性存疑——进化搜索的随机性可能导致不同运行发现截然不同的算法，论文未刻画这种方差。
未来方向
作者提出未来工作将把该流水线扩展到深度强化学习代理和合作型广义和博弈。基于本文成果，可以延伸出多个方向：(1) 将发现的核心机制（如 WOP-CFR 的硬热启动+极端非对称折扣+乐观预测、PM-PSRO 的切线投影）形式化分析其理论收敛性质，建立从经验发现到理论保证的桥梁。(2) 将算法发现流水线应用于其他博弈论范式，如均场博弈、动态博弈或机制设计。(3) 探索 LLM 在蒸馏阶段的更多作用——不仅发现算法，还帮助证明其性质或自动生成消融实验。(4) 将 VAD-CFR 和 WOP-CFR 的核心思想（极端非对称折扣、乐观预测）与深度 CFR 结合，处理大规模扑克等实际应用。(5) 研究多目标进化搜索中不同游戏之间的迁移学习——在一种游戏家族上学到的机制能否迁移到另一种。
复现评估
论文的可复现性评估如下：代码方面，论文提供了所有发现算法的完整源代码（VAD-CFR 在 Listing 3，SHOR-PSRO 在 Listing 4，WOP-CFR 在 Listing 5，PM-PSRO 在 Listing 6），以及演化框架使用的接口定义（Listing 1 和 2）。实验使用 OpenSpiel 框架，这是一个开源的游戏库。数据方面，所有实验使用标准的游戏定义，无需额外数据集。算力方面，AlphaEvolve 使用 Gemini 2.5 Pro 作为 LLM 后端，进化搜索的计算成本未报告，但涉及大量 LLM 调用和游戏树遍历，复现成本可能较高。评估协议清晰——18 个游戏的完整列表、训练/测试分割、1000 轮 CFR 迭代、100 轮 PSRO 迭代等参数都已指定。然而，由于仅报告单次运行结果且未提供随机种子，完全精确复现存在困难。消融研究的完整细节在附录中提供，有助于理解和验证核心发现。
论文图表
