arXiv 2607.08892v1 · 发布 2026-07-09

离线纳什求解器与在线树搜索在图上多智能体博弈中的结合

Offline Nash Solvers Meet Online Tree Search in Multi-Agent Games on Graphs

AUTHORS Mukesh Kumar, Yue Guan, Panagiotis Tsiotras

EVIDENCE 多智能体追逃博弈中的纳什均衡求解与树搜索

SCORE 0.8

CATEGORIES TASK mas

PDF ↗ 2607.08892v1.pdf

GENERATED 2026-07-13 21:45:06 UTC

📝 TLDR

多智能体追逃博弈中联合状态与动作空间随智能体数量呈指数增长，单纯依赖离线均衡近似缺乏执行时适应性，而在线规划又面临庞大分支因子。为此提出原语引导的树搜索（PGTS）混合框架：离线求解若干小子博弈的精确纳什均衡与值函数，在线部署时以这些最优子博弈策略指导树扩展并估计叶节点值。在多种图拓扑及真实网络上的实验表明，PGTS显著优于当前最优的学习与启发式基线方法，面对对抗方仍保持鲁棒性能。

🧭 速览

动机

多智能体追逃博弈联合状态与动作空间随智能体数指数增长，离线均衡近似缺乏执行适应性，在线规划分支因子过大，难以高效求取纳什均衡策略。

方法

提出PGTS混合框架：离线精确求解若干小子博弈的纳什均衡及值函数，在线树搜索中以这些最优原语策略引导扩展并估计叶节点值。

结果

在多种图拓扑与真实网络场景下显著优于现有学习与启发式基线方法，且面对对抗策略仍保持稳定鲁棒的性能。

结论

证明离线精确纳什求解与在线树搜索的融合可有效应对多智能体图博弈的高维挑战，为兼顾均衡精度与执行可扩展性提供了新思路。

📊 论文图表(共 3 张)

展开查看 3 张图

TL;DR

这篇论文针对多智能体追逃博弈中联合状态与动作空间随智能体数量指数爆炸导致的均衡策略计算难题，提出了一种将离线精确纳什均衡求解与在线树搜索相结合的混合框架 PGTS。其核心思路是预先离线求解若干小子博弈（1v1、2v1）的精确均衡与值函数，在线搜索时利用这些最优子博弈策略引导树扩展并估计叶节点值。在 Grid、Scotland Yard、Atlanta 等多种图拓扑上的实验表明，PGTS 在最坏情况效用指标上显著优于 MT-PSRO、NSGZero 等当前最优方法，且对多种逃逸策略保持鲁棒性能。

研究背景与动机

多智能体追逃博弈（PEG）是人工智能与博弈论交叉领域的经典问题，其中追捕方（Pursuer）需要协调行动以捕获逃逸方（Evader），而逃逸方则试图在图结构环境中避免被抓获。这类问题在网络安全、机器人协作、无人系统拦截等场景中具有广泛的应用价值。从博弈论角度而言，[[纳什均衡]]是此类零和博弈的标准解概念——在均衡状态下，任何一方单方面偏离当前策略都无法获得更高的期望收益。

然而，随着智能体数量的增加，联合状态空间 $S = V^{n_{r}} \times V^{n_{b}}$ 与联合动作空间 $A_{r} \times A_{b}$ 呈指数级增长。以一个包含 200 个节点的 Scotland Yard 网络为例，2v1 子博弈的状态空间即可达到百万数量级。这种组合爆炸使得直接求解精确纳什均衡变得不可行。

现有方法主要分为三类，各有其固有限制。离线学习方法如 PSRO（Policy Space Response Oracle）和 MAPPO 通过反复训练与策略更新来近似均衡，但训练成本高昂，且对训练过程中未曾见过的对手行为泛化能力差，在执行时缺乏适应性。在线规划方法如 SM-MCTS（Secure Multi-Agent Monte Carlo Tree Search）虽然具有灵活性，但需要在庞大的分支因子空间中搜索，效率低下。神经[[蒙特卡洛树搜索]]类方法（如 AlphaZero、NSGZero）虽然结合了学习与规划，但依赖神经网络近似，需要大量训练数据，且解释性较差。

这篇论文的切入点在于：能否找到一种方法，既能保证均衡策略的理论正确性，又能在线执行时具备足够的适应性？作者观察到，虽然完整博弈难以求解，但若干小子博弈（如单追捕者对单逃逸者、两个追捕者对一个逃逸者）的均衡是可以精确计算的。如果将这些小子博弈的最优策略作为"原语"嵌入在线搜索过程，或许能够兼顾精度与效率。

方法

PGTS 的核心设计哲学是"离在线解耦、协同互补"：离线阶段利用精确求解器的理论保证获取小子博弈的最优策略；在线阶段则借助这些策略来压缩搜索空间，同时通过树搜索实现跨子博弈的团队级协调。

在博弈建模方面，论文将追逃问题形式化为两队零和随机博弈。追捕方最大化累积折扣奖励，逃逸方则最小化同一目标函数。捕获条件定义为逃逸者与最近追捕者的距离不超过捕获半径 $r_{c}$ ，逃脱条件则为其与最近出口的距离不超过逃脱半径 $r_{e}$ 。[[零和博弈]]的结构使得纳什均衡与最大最小解等价，为后续求解提供了理论依据。

离线阶段的核心任务是计算子团队博弈（primitive sub-team games）的精确纳什均衡。具体而言，论文分解原博弈为两类子问题：1v1 博弈（ $S_{1 v 1} = V \times V$ ，共 $n_{r} \times n_{b}$ 个）和 2v1 博弈（ $S_{2 v 1} = V^{2} \times V$ ，共 $(2 n _{r}) \times n_{b}$ 个）。对于每个小子博弈，作者采用 Shapley 值迭代方法求解精确均衡。Shapley 算子的更新形式为：

Q_{k + 1} (s, a_{r}, a_{b}) = R (s, a_{r}, a_{b}) + β \cdot Nash (Q_{k} (s^{'}))

其中 $s^{'} = P (s, (a_{r}, a_{b}))$ 是确定性转移后的状态， $β$ 是折扣因子。通过迭代直至收敛，可以获得每个小子博弈的最优策略 $π_{1 v 1}^{*}, π_{2 v 1}^{*}$ 以及对应的值函数 $V_{1 v 1}^{*}, V_{2 v 1}^{*}$ 。这些离线计算的结果将被存储并在在线阶段复用。

在线阶段是 PGTS 的关键创新所在。作者在 SM-MCTS 框架基础上引入了三项核心改进。

第一项是原语引导扩展（Primitive-Guided Expansion）。传统树搜索在每个状态节点需要枚举所有可能的联合动作，分支因子极大。PGTS 则利用离线求解的 1v1 和 2v1 策略来构造受限的候选动作集。具体而言，对于每个逃逸者 $j$ ，算法选取 $k_{r}$ 个最近的红方邻居构成追捕子集，然后利用对应的 1v1 或 2v1 策略采样局部联合动作。这种方式将搜索聚焦于"战略相关"的动作组合，同时通过补充最短路径启发式和随机动作来保持探索性。

第二项是叶节点值估计（Leaf Value Estimation）。当搜索树扩展到终止节点时，需要估计该叶节点的值函数。PGTS 采用优先级匹配策略：首先尝试匹配 2v1 交互（因为 2v1 能够捕获"联合围捕"等高阶协同行为），剩余的智能体再按 1v1 匹配。这一分配问题通过匈牙利算法在多项式时间内求解：

V_{leaf} (s) = \frac{1}{n _{2 v 1}} ({i, j}, k) \in M_{2 v 1} \sum V_{2 v 1}^{*} ((s_{i}, s_{j}), s_{k}) + \frac{1}{n _{1 v 1}} (i, j) \in M_{1 v 1} \sum V_{1 v 1}^{*} (s_{i}, s_{j})

其中 $M_{2 v 1}$ 和 $M_{1 v 1}$ 分别是由匈牙利算法求得的最优 2v1 和 1v1 匹配集合。

第三项是动作选择算子的模块化设计。PGTS 支持两种可插拔的算子：Regret Matching（RM）通过累积反事实遗憾来计算混合策略，这是扑克等不完全信息博弈中的经典技术；Decoupled UCT（DUCT）则对两队的边际动作值独立施加上置信界，红方最大化、蓝方最小化，实现对抗性搜索。

实验与结果

实验在 GraphChase 基准平台上进行，覆盖四种差异显著的图拓扑：两个 7×7 Grid（简单图，49 节点）、Scotland Yard（200 节点）和 Atlanta（151 节点，真实城市路网）。追捕方配置为 3 追捕者对 1 逃逸者，时间步设置为 6 或 9 步。

主要评估指标包括 WCU（Worst-Case Utility，对所有可行逃逸轨迹的最坏情况效用）和 SP-WCU（对最短路径逃逸者的最坏效用）。前者衡量策略的对抗鲁棒性，后者则反映对标准逃逸行为的拦截效果。

实验结果呈现出几个值得关注的发现。在 Grid1 等简单图上，子团队分解方法尚能与 PGTS 竞争，但随着图规模增大和拓扑复杂度提升，PGTS 的优势愈发明显。在 Scotland Yard 上，PGTS（RM）的 WCU 达到 0.73，而子团队分解方法骤降至 0.25 以下，NSGZero 和 MT-PSRO 的 WCU 更是接近于零。Atlanta 上的结果更加悬殊：PGTS 的 WCU 维持在 0.87–0.94，而 NSGZero 完全失效，WCU 为 0.00。

消融实验揭示了各组件的贡献度。原语引导扩展在所有图上均带来正向收益。2v1 高阶原语的作用尤为显著——在 Scotland Yard 上，仅使用 1v1 原语时 WCU 从 0.73 骤降至 0.15，表明高阶协同对于复杂环境下的有效围捕至关重要。动作选择算子的对比则显示，RM 与 DUCT 在不同场景下各有优劣，但两者都显著优于纯启发式方法。

一个有趣的发现是学习方法的过拟合现象。MT-PSRO 和 NSGZero 在 SP-WCU 指标上表现优异，但对非最短路径逃逸策略的适应能力极差。这恰恰说明了离线近似与在线适应性之间的张力——PGTS 通过将精确均衡作为先验知识嵌入搜索，有效缓解了这一问题。

讨论与可借鉴点

PGTS 最有价值的贡献在于其"精确均衡作为可复用知识"的设计思路。将小子博弈的纳什均衡预计算并作为原语嵌入在线搜索，这一做法在概念上类似于强化学习中通过子问题分解降低计算复杂度，但不同的是，PGTS 的子问题解是精确的而非近似的。这为如何桥接理论最优性与实践可行性提供了一个可借鉴的范式。

然而，论文的实验覆盖存在明显局限。与 SOTA 基线的对比仅在 Nv1（多追捕者对单逃逸者）场景下进行，而实际应用中 NvM（多追捕者对多逃逸者）场景可能更为常见。GraphChase 平台本身的限制使得更大规模场景的对比难以开展。此外，2v1 原语的离线求解在 Scotland Yard 规模图上需要约 6.5 小时，计算代价已相当可观；扩展到 3v2、3v3 等更高阶原语时，状态空间将进一步膨胀，精确求解的可行性存疑。

论文在完全可观测与确定性转移假设下进行验证。部分可观测、随机转移或通信受限等更复杂的实际场景尚未得到实验支持。超参数（ $k_{r}$ 、 $M$ 、 $D$ 等）对不同环境的敏感性也意味着方法的可迁移性需要进一步论证。

尽管如此，PGTS 的模块化设计为后续改进留出了充足空间：更复杂的原语定义、更高效的叶值估计、更灵活的对手建模，都可以在现有框架上叠加。对于研究[[树搜索]]与博弈论求解器融合的学者而言，PGTS 展示了一条不依赖大规模训练数据的可行路径。

摘要

在多智能体追逃博弈（PEG）中，计算纳什均衡策略由于联合状态和动作空间随智能体数量呈指数级增长而极具挑战性。现有方法要么依赖离线均衡近似，可能在执行时缺乏适应性；要么依赖在线规划方法，受限于较大的分支因子。本文提出了原始策略引导的树搜索（PGTS），一种将离线精确纳什均衡计算与在线树搜索相结合的混合框架：PGTS 首先离线求解一系列较小的、可处理的子博弈；在部署时，PGTS 在每个时间步执行在线树搜索，利用最优子博弈策略和值函数来引导树扩展并估计叶节点的值。在包括真实网络在内的多种图拓扑上的大量实验表明，PGTS 显著优于当前最先进的基于学习和启发式的方法，同时对对手保持稳健的性能。

Abstract

Computing Nash equilibrium policies in multi-agent Pursuit-Evasion games (PEG) is challenging due to the exponential growth of the joint state and action spaces with the number of agents. Existing approaches either rely on offline equilibrium approximations, which may lack adaptability during execution, or online planning methods, which suffer from large branching factors. In this work, we propose Primitive-Guided Tree Search (PGTS), a hybrid framework that integrates offline exact Nash equilibrium computation with online tree search: PGTS first solves a collection of smaller, tractable sub-games offline; at deployment, PGTS performs online tree search at each time step, using the optimal sub-game policies and value functions to guide tree expansion and estimate leaf-node values. Extensive experiments on varied graph topologies, including real-world networks, demonstrate that PGTS significantly outperforms state-of-the-art learning and heuristic baselines, while maintaining robust performance against adversaries.

论文详细总结（自动生成）

论文总结：离线纳什求解器与在线树搜索在图上多智能体博弈中的结合

1. 核心问题与研究动机

研究背景：在多智能体追逃博弈（PEG）中，红方（追捕者 Pursuers）与蓝方（逃逸者 Evaders）在图结构环境中对抗；标准解概念是纳什均衡，其存在性已得到证明（Fink, 1964），但精确计算受限于状态与动作空间的指数爆炸。
核心挑战：随着智能体数量增加，联合状态空间 $S = V^{n_{r}} \times V^{n_{b}}$ 与联合动作空间 $A_{r} \times A_{b}$ 急剧增长，即使中等规模环境也难以直接使用 Shapley 值迭代精确求解。
现有方法局限：
离线方法（如 PSRO、MT-PSRO、MAPPO）训练成本高，且对训练时未见的对手行为泛化性差。
在线方法（如 SM-MCTS）需在指数级分支因子中搜索，依赖人工启发式。
混合方法（如 AlphaZero、NSGZero）依赖神经网络近似，训练数据需求大。
本文定位：提出兼顾均衡精度与执行可扩展性的离线-在线融合框架。

2. 方法论

2.1 博弈建模

两队零和随机博弈，状态转移确定性，奖励团队级零和。
捕获/逃脱条件：蓝方距红方 ≤ $r_{c}$ 跳被捕获，距出口 ≤ $r_{e}$ 跳逃脱。
纳什均衡定义（红方最大化、蓝方最小化）：

V^{π_{r}, π_{b}} (s) = E [t = 0 \sum \infty β^{t} R (s_{t}, a_{r}^{t}, a_{b}^{t}) s_{0} = s]

V^{π_{r}, π_{b}^{*}} (s) \leq V^{π_{r}^{*}, π_{b}^{*}} (s) \leq V^{π_{r}^{*}, π_{b}} (s), \forall s \in S

2.2 离线阶段：原始子博弈求解

分解原博弈为子团队博弈（primitive sub-team games）：1v1（ $S_{1 v 1} = V \times V$ ）与 2v1（ $S_{2 v 1} = V^{2} \times V$ ）。
利用文献 [9] 的纳什求解器通过 Shapley 值迭代精确计算 $π_{1 v 1}^{*}, V_{1 v 1}^{*}$ 与 $π_{2 v 1}^{*}, V_{2 v 1}^{*}$ 。
Shapley 算子更新：

Q_{k + 1} (s, a_{r}, a_{b}) = R (s, a_{r}, a_{b}) + β \cdot Nash (Q_{k} (s^{'})), s^{'} = P (s, (a_{r}, a_{b}))

2.3 自适应子团队分解（作为基线）

寻找最优分配 $d^{*} (s_{t}) = ar g max_{d \in D} \overset{ˉ}{V} (d, s_{t})$ ，其中：

\overset{ˉ}{V} (d, s_{t}) = g_{ℓ} \in d (s_{t}) \sum V_{g_{ℓ}}^{*} (s_{g_{ℓ}}^{t})

缺点：各子博弈独立求解，缺乏团队级协调。

2.4 在线阶段：原语引导树搜索（PGTS）

PGTS 基于 SM-MCTS 框架，每个时间步构建搜索树，主要创新点：

(a) 原语引导扩展（Primitive-Guided Expansion）：
每个蓝方 $j$ 选取 $k_{r}$ 个最近红方邻居 $N^{k_{r}} (j)$ 。
利用 1v1 与 2v1 策略采样局部联合动作，构造受限候选动作集 $\tilde{A} (s_{n}) = \tilde{A}_{r} \times \tilde{A}_{b} \subseteq A (s_{n})$ 。
补充最短路径启发式与随机动作以保持探索性。

(b) 叶节点值估计（Leaf Value Estimation）：
优先匹配 2v1 交互（捕获"联合围捕"等高阶协同），剩余智能体再匹配 1v1。
通过匈牙利算法求解最大权和分配问题：

V_{leaf} (s) = \frac{1}{n _{2 v 1}} ({i, j}, k) \in M_{2 v 1} \sum V_{2 v 1}^{*} ((s_{i}, s_{j}), s_{k}) + \frac{1}{n _{1 v 1}} (i, j) \in M_{1 v 1} \sum V_{1 v 1}^{*} (s_{i}, s_{j})

(c) 动作选择（两种模块化算子）：
Regret Matching (RM)：累积反事实遗憾，计算混合策略。
Decoupled UCT (DUCT)：对每队边际动作值独立施加 UCB（红方最大化、蓝方最小化 LCB）。
(d) 终止与回溯：最大搜索深度 $D$ ，模拟次数 $M$ ，按 SM-MCTS 流程选择-扩展-评估-回溯。

3. 实验设计

3.1 平台与环境

使用开源 GraphChase 基准平台 [24]。
4 种图拓扑：
Grid 1（Easy）： $7 \times 7$ 网格，49 节点
Grid 2（Hard）： $7 \times 7$ 网格，49 节点
Scotland Yard：200 节点
Atlanta：151 节点（真实城市路网）
时间步 $T = 6$ （网格）或 $T = 9$ （Scotland Yard/Atlanta）。

3.2 评估指标

WCU（Worst-Case Utility）：对所有可行逃逸轨迹的最坏情况效用。
SP-WCU：对最短路径逃逸者的最坏效用。
ER（Expected Reward）：与采样逃逸者交互的期望奖励。

3.3 对比基线

基线	类型	描述
Intercepting	启发式	沿最短路径拦截
Decomposition	分解式	第 3 节子团队分解
MT-PSRO [13]	离线学习	PSRO + MAPPO
NSGZero [22]	神经 MCTS	网络安全博弈

4. 资源与算力

硬件：24 核 5.7 GHz Intel Core Ultra 9 285K CPU + NVIDIA RTX 5090 GPU。
离线计算时间（单个 1v1/2v1 原语博弈）：
Grid（49 节点）：1v1 ≈ 70.9 s，2v1 ≈ 56–65 s
Atlanta（151 节点）：1v1 ≈ 922 s，2v1 ≈ 2949 s
Scotland Yard（200 节点）：1v1 ≈ 1033 s，2v1 ≈ 23501 s（约 6.5 小时）
在线规划：单步决策时间约 0.5 秒（向量化加速），最大模拟数 $M \leq 2000$ ，最大搜索深度 $D \leq 4$ 。
折扣因子 $β = 0.95$ （所有环境统一）。

5. 实验数量与充分性

主实验：4 个图 × 2 个时间步 × 6 种方法 = 约 48 组配置；另含对 PGTS 逃逸者的对抗测试（Table 2），共覆盖 2 个时间步。
消融研究（Table 3）：对比完整 PGTS、移除原语引导扩展、仅使用 1v1 原语三个版本，在 4 个图上对比 RM/DUCT 两类算子，共 6 × 4 = 24 组配置。
公平性考量：
调参与对比均在 GraphChase 统一平台进行。
PGTS 超参数针对 SP 逃逸者调优后固定用于 WCU 评估。
对比 NSGZero/MT-PSRO 时，承认二者依赖 SP 逃逸者训练，PGTS 在此指标上不一定占优。
评价：实验设计较为系统，覆盖不同复杂度图与多种基线；但仅在 Nv1 场景下与 SOTA 对比（因 GraphChase 限制），NvM（ $M \geq 2$ ） 场景的实验相对薄弱。

6. 主要结论与发现

PGTS 在所有图拓扑上一致优于现有基线，尤其在 Scotland Yard 与 Atlanta 大图上 WCU 提升显著（如 Atlanta 上 WCU 从 NSGZero 的 0.00 提升至 0.87–0.94）。
学习基线（MT-PSRO、NSGZero）存在过拟合：对 SP 逃逸者表现良好（SP-WCU 高），但面对非常规逃逸策略时性能急剧下降。
子团队分解方法有限：在简单图（Grid 1）有竞争力，但缺乏团队级协同，在复杂图上明显劣于树搜索。
消融结论：
原语引导扩展对所有图都有正向贡献。
2v1 高阶原语在大图（Scotland Yard/Atlanta）上尤其关键：仅用 1v1 时 WCU 从 0.73 降至 0.15（Scotland Yard, RM）。
PGTS 对抗 PGTS 逃逸者仍维持高胜率（多数场景 0.95+），表明策略鲁棒。

7. 优点与亮点

方法论创新：首次将"原始子博弈精确纳什解"作为先验嵌入 SM-MCTS 的扩展与叶值评估阶段，无需训练神经网络，规避了对大规模训练数据的依赖。
兼顾精度与效率：离线精确求解与在线协调规划结合，使搜索既能聚焦战略相关动作，又能通过完整联合动作 rollout 捕获团队协同。
模块化设计：动作选择算子（RM / DUCT）可插拔，便于扩展。
叶值估计机制：优先 2v1 匹配的顺序分配策略，是对组合优化 $max_{d} \overset{ˉ}{V} (d, s)$ 的有效可扩展近似。
跨域验证：在 4 种差异显著的图（含真实城市路网）上验证，证据较充分。
强对抗鲁棒性：在多类逃逸策略与不同时间步下均维持稳定性能。

8. 不足与局限

实验配置受限：与 SOTA 基线（MT-PSRO、NSGZero）对比仅在 Nv1 场景进行，GraphChase 平台本身不支持 NvM 场景下的对比，限制了结论的广泛性。
算力需求大：Scotland Yard 的 2v1 原语求解需 ~6.5 小时；最大图（200 节点）状态空间达 $∣ S_{2 v 1} ∣ \sim 1 0^{6}$ 数量级，进一步扩展到 3v2、3v3 等高阶原语代价急剧上升。
依赖子博弈精确解：方法假设 1v1/2v1 可精确求解，当智能体数增大或图结构更复杂时，该假设难以满足。
完全可观测与确定性转移假设：实际应用中常涉及部分可观测、随机转移或通信受限场景，论文仅在结论中提及未来扩展，未提供实验验证。
超参数敏感性： $k_{r}$ 、 $M$ 、 $D$ 、 $γ_{r m}$ 、 $C$ 等参数需针对不同环境调优（见 Table 5），跨环境的迁移性未充分讨论。
公平性争议：调参基于 SP 逃逸者完成后再用于 WCU 评估，但对手为 PGTS 时（Table 2）未重新调参，可能存在对己方有利的偏差。
子团队数受限：仅演示 1v1 与 2v1 两类原语；团队规模进一步扩大时（如 5v3），原语设计与组合空间将更复杂。

（完）

✨ 编译论文

点「✨ 编译」开始,LLM 会按 Polaris 风格翻译并把图片/表格嵌到对应位置。结果存到浏览器 localStorage,下次访问自动加载。