Skip to main content
2026ICML 2026 (PMLR 306)

自动机条件化的协作多智能体强化学习

Automata-Conditioned Cooperative Multi-Agent Reinforcement Learning

UC Berkeley 团队提出 ACC-MARL 框架，利用确定性有限自动机（DFA）表示多智能体协作任务，通过马尔可夫化重构、势函数奖励塑形和预训练 RAD Embeddings 三项技术解决历史依赖、信用分配和表示瓶颈三大挑战，实现运行时动态任务分配下的去中心化协作策略学习。

Beyazit Yalcinkaya, Marcell Vazquez-Chanlatte, Ameesh Shah, Hanna Krasowski, Sanjit A. Seshia
AI解读多智能体强化学习形式化规约自动机理论MARL

论文概览

多智能体强化学习（MARL）中的核心难题之一：如何让智能体团队在运行时接受事先未知的任务，无需重新训练即可协作完成具有时序约束的团队目标？这篇发表于 ICML 2026 的论文给出了系统性的回答。

论文信息：Beyazit Yalcinkaya 等人（UC Berkeley）提出 ACC-MARL（Automata-Conditioned Cooperative MARL）框架。该框架使用确定性有限自动机（DFA） 表示任务，在集中训练、去中心化执行（CTDE）设定下学习任务条件化的去中心化团队策略。核心贡献包括：(1) 识别并解决 ACC-MARL 的三大可行性挑战，并证明方法的最优性；(2) 利用学习到的值函数实现测试时最优任务分配；(3) 开发了基于 JAX 的工具链 DFAx，支持自动机的并行化操作；(4) 实验验证了框架的有效性，并定性分析了涌现的协作行为。

ACC-MARL 框架总览
ACC-MARL 框架总览

核心问题与挑战

ACC-MARL 的目标是在马尔可夫博弈 M=⟨S,A,P,ι⟩M = \langle S, A, P, \iota \rangle 中，学习去中心化策略 πi:Si∗×Dn→Δ(Ai)\pi_i: S_i^* \times \mathcal{D}^n \to \Delta(A_i)，最大化所有 DFA 任务同时被满足的概率：

J(π)=PA∼ιDn[⋀i=1nτi⊨LiA[i]]J(\pi) = \mathbb{P}_{A \sim \iota_D^n} \left[ \bigwedge_{i=1}^{n} \tau_i \models_{L_i} A[i] \right]

作者识别出阻碍该问题求解的三大挑战：

三大挑战与解决方案
三大挑战与解决方案

挑战一：历史依赖。策略需要依赖历史轨迹来推断每个 DFA 的当前状态（任务进度），使得增强后的博弈不再具有马尔可夫性，导致样本效率低和次优策略。

挑战二：信用分配。团队目标仅提供稀疏奖励——"团队是否完成了所有任务？"——智能体难以判断自身行为对整体目标的贡献。

挑战三：表示瓶颈。在学习 DFA 潜在表示的同时学习条件化策略，控制与表示学习耦合，在大团队中成为性能瓶颈。

方法论详解

解决方案一：马尔可夫化重构

利用 DFA 的操作语义，通过DFA 前进（progression） 操作将非马尔可夫博弈转化为马尔可夫博弈。给定 DFA AA 和词 ww：

A/w≜min⁡(⟨Q,Σ,δ,δ∗(q0,w),F⟩)A/w \triangleq \min(\langle Q, \Sigma, \delta, \delta^*(q_0, w), F \rangle)

即读取词 ww 后最小化 DFA。每一步用最新的最小化 DFA 增广状态空间，构造乘积 DFA 空间 Dn\mathcal{D}^n 及其诱导的 MDP MDnM_{\mathcal{D}^n}。新的博弈在乘积空间 S×DnS \times \mathcal{D}^n 中进行，策略变为 πi′:Si×Dn→Δ(Ai)\pi_i': S_i \times \mathcal{D}^n \to \Delta(A_i)，无需历史轨迹。

定理 3.1 证明：当 γ→1−\gamma \to 1^- 时，马尔可夫化重构与原问题具有相同的最优策略：

lim⁡γ→1−max⁡π′Jγ′(π′)=max⁡πJ(π)\lim_{\gamma \to 1^-} \max_{\pi'} J_\gamma'(\pi') = \max_\pi J(\pi)

解决方案二：势函数奖励塑形（PBRS）

为缓解稀疏奖励问题，定义每个智能体的势函数 Φi(A)=1[A[i]=A⊤]\Phi_i(A) = \mathbb{1}[A[i] = A^\top]，塑形奖励为：

RPBRS(i)(A,σ)=RDn(A,σ)+γΦi(TDn(A,σ))−Φi(A)R_{PBRS}^{(i)}(A, \sigma) = R_{\mathcal{D}^n}(A, \sigma) + \gamma \Phi_i(T_{\mathcal{D}^n}(A, \sigma)) - \Phi_i(A)

智能体完成自身 DFA 时获得正向反馈，同时团队奖励不变。基于状态势函数的塑形保证了最优性不变（Devlin & Kudenko, 2011）。

解决方案三：预训练 RAD Embeddings

使用预训练且冻结的 GATv2 编码器 Ψ:D→Z\Psi: \mathcal{D} \to \mathcal{Z}，将 DFA 映射到潜在空间。该编码器保证唯一性：

min⁡(A)=min⁡(A′)  ⟺  Ψ(A)=Ψ(A′)\min(A) = \min(A') \iff \Psi(A) = \Psi(A')

即两个 DFA 在最小化后相同当且仅当其嵌入相同。这使策略可以条件化于乘积潜在空间 Zn\mathcal{Z}^n，解耦表示学习与控制学习。在四智能体环境中，这一解耦对策略收敛至关重要。

测试时最优任务分配

训练完成后，利用学习到的值函数 ViV_i 构造代理值函数 V(A)=E[∑iVi(τi,A)]V(A) = \mathbb{E}[\sum_i V_i(\tau_i, A)]，通过枚举排列找到帕累托最优分配：

A⋆∈arg⁡max⁡A′∈perm(A)V(A′)A^\star \in \arg\max_{A' \in \text{perm}(A)} V(A')

实验设计与结果

实验在全新的 TokenEnv 环境中进行，包含四种布局：Buttons-2/4 和 Rooms-2/4，分别测试 2 智能体和 4 智能体的协作。训练使用 IPPO 算法，RAD DFA 任务（≤5 状态），1000 万时间步。

实验结果
实验结果

消融实验关键发现

配置Buttons-2Buttons-4效果
RAD Embd + PBRS（完整方案）~0.87~0.76四智能体环境最优
no RAD + PBRS~0.92~0.73二智能体略优，四智能体退化
RAD Embd + no PBRS~0.45~0.28无法逃脱贫次优解
no RAD + no PBRS~0.15~0.11完全失败
LSTM（历史依赖）<0.50—全部失败

关键结论：PBRS 是学习最优策略的必要条件，无 PBRS 的策略均无法逃脱贫次优解。RAD Embeddings 在四智能体环境中不可或缺，且展现出更稳定的收敛行为。

泛化能力

策略在 Reach、ReachAvoid、RAD 三类任务上均展现泛化性，OOD 测试（10 状态 DFA）中两智能体环境在 Reach 任务上仍有明显泛化。最优任务分配在 Rooms-2 和 Rooms-4 中显著提升性能，验证了值函数驱动的分配方法的有效性。

涌现的协作行为

定性分析揭示了两种典型的涌现协作模式：

  1. "Hold the Door"（守门）：Agent 1 站在按钮上保持门开，Agent 2 同步进入房间完成任务，节省时间。
  2. "Short-Circuit"（短路捷径）：Helper agent 打开另一扇门，使伙伴选择更短的 DFA 路径（到达单个 token 而非两个），实现任务最优完成。

启示与思考

DFA 作为任务表示的优势体现在三个方面：操作语义支持高效的前进操作以实现马尔可夫化；组合性允许复杂任务分解为子任务分配给个体智能体；表达能力足以编码有限时域行为。这使得 ACC-MARL 在可扩展性和表达性上具备坚实基础。

框架的局限性同样值得关注：固定标记函数的假设限制了任务语义的动态变化；全可观测假设在真实场景中难以满足；任务分配的排列枚举在大团队中不可行；实验仅在离散域验证，连续域和真实机器人平台的迁移仍是开放问题。

对 MARL 研究的启示：这项工作首次将形式化规约引入多任务协作 MARL，证明了"表示与控制解耦"在多智能体设定中的关键价值。RAD Embeddings 从单智能体到多智能体的扩展，尤其是在四智能体环境中表现出的决定性作用，提示我们：当协作复杂度上升时，预训练的结构化任务表示比端到端联合学习更为可靠。值函数驱动的任务分配方法为实际部署中的动态任务调度提供了可行路径。

参考链接

研究