💻 computer science

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

This paper introduces Primitive-Guided Tree Search (PGTS), a hybrid framework that combines offline exact Nash equilibrium computations on tractable sub-games with online tree search to effectively solve multi-agent Pursuit-Evasion games on graphs, significantly outperforming existing learning and heuristic baselines.

Original authors: Mukesh Kumar, Yue Guan, Panagiotis Tsiotras

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mukesh Kumar, Yue Guan, Panagiotis Tsiotras

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a high-stakes game of tag played on a giant, twisting map of city streets. You have a team of "Taggers" (the Red team) trying to catch a team of "Runners" (the Blue team) before they reach a secret exit. The problem? As you add more players to the field, the number of possible moves explodes. It's like trying to predict every single move in a game of chess, but with a million pieces moving at once. If you try to calculate the perfect move for every single player at the same time, your brain (or computer) crashes from the sheer math overload.

For a long time, researchers tried two main ways to solve this, and both had big flaws. The first way was to pre-calculate the perfect strategy for every possible situation before the game even started. But this is like memorizing every possible path in a maze before you enter it; if the maze changes even a tiny bit, or if the other players do something weird you didn't expect, your memorized map becomes useless. The second way was to think on the fly during the game, simulating millions of future scenarios to pick the best move. But with so many players, the number of branches to explore is so huge that the computer gets stuck in the weeds and can't find the best path in time.

Enter the new hero of this story: Primitive-Guided Tree Search (PGTS). Think of PGTS as a smart coach who combines the best of both worlds.

The Coach's Secret Weapon: The "Mini-Game" Library

Instead of trying to solve the whole massive game at once, the PGTS coach goes into the library before the game starts and solves a bunch of tiny, simple versions of the game. These are called "primitive sub-team games."

Imagine solving a 1-on-1 game of tag.
Then solving a 2-on-1 game (two taggers vs. one runner).

The coach solves these tiny games perfectly and writes down the answers in a "cheat sheet" (a cache of policies and values). This is the offline part. It's fast because the games are small.

The Game Day: Smart Tree Search

When the real game starts, the coach doesn't just guess, and they don't just rely on the old cheat sheet. They use a Tree Search, which is like looking down a fork in the road to see where it leads. But here's the magic:

Guided Expansion: Instead of looking at every possible move (which would take forever), the coach uses the cheat sheet to only look at the moves that look promising based on those tiny 1-on-1 and 2-on-1 games. It's like the coach saying, "Hey, in a 2-on-1 situation, the taggers usually do this, so let's focus our thinking there."
Leaf Value Estimation: When the coach reaches the end of a thought path (a "leaf" on the tree), they don't need to simulate the whole game to the end. They just look at the current positions, break the big team back down into those tiny 1-on-1 and 2-on-1 groups, and use the pre-calculated cheat sheet to guess the final score.

This allows the team to coordinate perfectly as a whole group, while still using the speed of the pre-solved mini-games.

What the Paper Says (and Doesn't Say)

The authors tested this new coach on several different maps, including a 7x7 grid, a complex "Scotland Yard" map, and a real-world map of Atlanta with 151 nodes. They ran simulations where the game lasted for 6 time steps on the grids and 9 time steps on the larger maps.

The results were impressive. In these simulations, the PGTS team (using either a "Regret Matching" or "Decoupled UCT" decision style) consistently outperformed the best existing methods.

On the tricky "Grid 2" map, the old methods scored a worst-case utility of around 0.25 to 0.37, while PGTS scored 0.40 to 0.46.
On the Scotland Yard map, the difference was huge: the old methods scored as low as 0.00 or 0.05, while PGTS scored 0.68 to 0.73.
Even against a "smart" runner who wasn't just running in a straight line, PGTS held its ground, whereas the other methods (which were trained on simple runners) fell apart.

The paper explicitly argues against relying only on the pre-calculated mini-games (decomposition) without the tree search. They found that while the mini-games are good, they fail to capture how the whole team should work together. If you just use the mini-games, the team coordination breaks down, and performance drops significantly. The tree search is the glue that holds the team coordination together.

The Verdict

This isn't a magic wand that solves every problem in the universe, but in the world of these specific simulations, it's a game-changer. The authors show that by breaking a giant, scary problem into small, solvable pieces and then using those pieces to guide a smart search, you can beat the best current strategies. They proved this through extensive computer simulations on various graph topologies, showing that their method is robust even when the other team tries to be tricky.

The paper suggests that this approach could be extended to other types of multi-agent games and even situations where you can't see everything (partial observability), but for now, they have only demonstrated it in these specific pursuit-evasion simulations. It's a clever trick that turns a math nightmare into a manageable puzzle, proving that sometimes, the best way to win the big game is to master the small ones first.

Technical Summary: Primitive-Guided Tree Search in Multi-Agent Pursuit-Evasion Games

1. Problem Formulation

The paper addresses the challenge of computing Nash equilibrium policies in multi-agent Pursuit-Evasion Games (PEGs) on graphs. In these games, a team of Pursuers (Red) attempts to capture a team of Evaders (Blue) before the Evaders reach designated exit nodes. The core difficulty lies in the exponential growth of the joint state and action spaces as the number of agents increases.

Existing approaches face a trade-off:

Offline methods (e.g., PSRO, MAPPO) train policies offline but often lack adaptability to adversarial behaviors unseen during training and suffer from high training complexity.
Online planning methods (e.g., MCTS) adapt to current states but struggle with the massive branching factors inherent in simultaneous multi-agent games, making deep search computationally infeasible.
Hybrid methods (e.g., AlphaZero variants) often rely on learning accurate value/policy approximations requiring extensive data, or are limited to two-player settings.

The goal is to develop a scalable, robust framework that combines the strategic depth of offline equilibrium computation with the adaptability of online search.

2. Methodology: Primitive-Guided Tree Search (PGTS)

The authors propose Primitive-Guided Tree Search (PGTS), a hybrid framework that decomposes the complex multi-agent game into tractable sub-games offline and integrates these solutions into an online Simultaneous-Move Monte Carlo Tree Search (SM-MCTS).

2.1 Offline Phase: Primitive Sub-Team Games

Instead of solving the full game directly, PGTS pre-computes exact Nash equilibria for small, representative "primitive" sub-games involving subsets of agents:

1v1: One Pursuer vs. One Evader.
2v1: Two Pursuers vs. One Evader.
These are solved using Shapley value iteration on the restricted state spaces ( $V \times V$ and $V^2 \times V$ ). The output includes optimal mixed policies ( $\pi^*$ ) and value functions ( $V^*$ ) for these primitives, which are cached for runtime use.

2.2 Online Phase: Tree Search

At each time step, PGTS performs a tree search from the current joint state. The algorithm modifies standard SM-MCTS in two critical ways:

Primitive-Guided Expansion:
To mitigate the exponential branching factor, the algorithm does not expand all possible joint actions. Instead, it uses the offline primitive policies to guide the search:
- For each Evader, the algorithm identifies its $k_r$ nearest Pursuers.
- It samples joint actions for local interactions (1v1 and 2v1 groups) based on the pre-computed Nash policies ( $\pi^*_{1v1}, \pi^*_{2v1}$ ).
- These samples form a restricted candidate action set, augmented with heuristic shortest-path actions and random exploration to prevent over-commitment to priors.
Leaf Value Estimation via Sub-team Surrogates:
Instead of running expensive Monte Carlo rollouts to the horizon, the algorithm estimates the value of leaf nodes using the offline primitive value functions.
- The algorithm approximates the full game value by decomposing the current state into a set of primitive sub-teams.
- It employs a sequential matching strategy: First, it greedily matches agents to form 2v1 interactions (capturing higher-order coordination like joint trapping) using the Hungarian algorithm on the 2v1 value matrix.
- Remaining agents are matched into 1v1 interactions.
- The leaf value is the aggregated sum of these primitive values, allowing the search to terminate at shallower depths while maintaining accurate outcome estimates.

2.3 Action Selection

The framework supports two selection operators for traversing the tree:

Regret Matching (RM): Applies regret matching to the estimated matrix game at each node to compute mixed policies.
Decoupled UCT (DUCT): Applies Upper Confidence Bounds independently to each team's marginal action values.

3. Key Contributions

Hybrid Framework: The introduction of PGTS, which uniquely integrates exact offline Nash solutions of small sub-games into an online tree search for multi-agent coordination.
Structured Expansion: A mechanism to reduce branching factors by sampling actions based on strategic priors derived from offline equilibrium computations rather than random or purely heuristic sampling.
Scalable Leaf Evaluation: A surrogate value estimation method that leverages offline primitive value functions and a sequential matching algorithm (prioritizing 2v1 over 1v1) to evaluate leaf nodes without deep rollouts.
Coordination Preservation: Unlike simple decomposition methods that treat sub-teams independently, PGTS maintains team-level coordination by performing joint action rollouts in the full action space, guided by the primitives.

4. Experimental Results

The authors evaluated PGTS on four graph topologies: two 7x7 grids (Easy/Hard), a 200-node Scotland Yard graph, and a 151-node real-world Atlanta graph. The Pursuer team was tested against various Evader behaviors.

Baselines:

MT-PSRO: Multi-Task Policy Space Response Oracles (learning-based).
NSGZero: Neural-guided MCTS for network security.
Decomposition: A baseline using only the sub-team decomposition without tree search.
Intercepting: A heuristic shortest-path baseline.

Findings:

Robustness: PGTS (both RM and DUCT variants) consistently achieved the highest Worst-Case Utility (WCU) across all topologies, significantly outperforming learning-based baselines (MT-PSRO, NSGZero) which showed signs of overfitting to shortest-path Evaders.
Coordination: PGTS outperformed the pure "Decomposition" baseline, demonstrating that the tree search component effectively captures team-level coordination that static decomposition misses.
Ablation: Removing primitive-guided expansion or the 2v1 primitives resulted in significant performance drops, particularly on larger, complex graphs (Scotland Yard, Atlanta), confirming the necessity of both components for effective exploration and value estimation.

5. Significance and Claims

The paper claims that PGTS offers a scalable solution to the "curse of dimensionality" in multi-agent PEGs. By leveraging exact solutions for small, recurring local interactions (primitives) to guide a global search, the method achieves:

Computational Tractability: It manages the branching factor and search depth effectively.
Adaptability: It retains the ability to reason about coordinated policies in the full joint action space, unlike static decomposition.
Robustness: It performs well against diverse adversarial strategies, including those not seen during any training phase, as it relies on game-theoretic principles rather than learned distributions.

The authors conclude that this approach bridges the gap between the theoretical optimality of offline equilibrium computation and the practical adaptability of online planning, providing a robust framework for multi-agent decision-making in adversarial environments. Future work is suggested to extend this to partial observability and broader multi-agent game classes.