Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games
Authors: Runyu Lu
Peng Zhang
Ruochuan Shi
Yuanheng Zhu
Dongbin Zhao
Yang Liu
Dong Wang
Cesare Alippi
Venue: NeurIPS 2025 poster ()
Keywords: Nash equilibrium
zero-shot generalization
pursuit-evasion game
reinforcement learning
dynamic programming
policy decomposition
shortest path distance
graph neural network
Primary area: reinforcement_learning

Abstract: Equilibrium learning in adversarial games is an important topic widely examined in the fields of game theory and reinforcement learning (RL). Pursuit-evasion game (PEG), as an important class of real-world games from the fields of robotics and security, requires exponential time to be accurately solved. When the underlying graph structure varies, even the state-of-the-art RL methods require recomputation or at least fine-tuning, which can be time-consuming and impair real-time applicability. This paper proposes an Equilibrium Policy Generalization (EPG) framework to effectively learn a generalized policy with robust cross-graph zero-shot performance. In the context of PEGs, our framework is generally applicable to both pursuer and evader sides in both no-exit and multi-exit scenarios. These two generalizability properties, to our knowledge, are the first to appear in this domain. The core idea of the EPG framework is to train an RL policy across different graph structures against the equilibrium policy for each single graph. To construct an equilibrium oracle for single-graph policies, we present a dynamic programming (DP) algorithm that provably generates pure-strategy Nash equilibrium with near-optimal time complexity. To guarantee scalability with respect to pursuer number, we further extend DP and RL by designing a grouping mechanism and a sequence model for joint policy decomposition, respectively. Experimental results show that, using equilibrium guidance and a distance feature proposed for cross-graph PEG training, the EPG framework guarantees desirable zero-shot performance in various unseen real-world graphs. Besides, when trained under an equilibrium heuristic proposed for the graphs with exits, our generalized pursuer policy can even match the performance of the fine-tuned policies from the state-of-the-art PEG methods.

Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Games
Generalization in
Runyu Lu Peng Zhang", Ruochuan Shi Yuanheng Zh
Dongbin 21. Yang Liu", Dong Wang", Cesare Alippi 4.5
1urumyu17 /aaaiyulmmmmall.mmm www.. an.cn
njzhanggeng@mmil..due dlut. edu. cn
(shiruochuan2025 yuanheng. zzu, w zha.zizaaaaaaaaa
{ly sdice)@dlur edu. cn
cesare .alipplpppp.. malippi@usi... @usi ch
School of Artificial Intelligence, University of Chinese Academy of Sciences"
2 Institute of Automation, Chinese Academy of Sciences Dalian University of Technology The Swiss AI Lab IDSIA, Università della Svizzera italiana PPolitecnico di Milano
*Coreepponding Authors
Abstract
Equilibrium learning in adversarial games is an important topic widely examined in the fields of game theory and reinforcement learning (RL). Pursuit-evasion game (PEG), as an important class of real-world games from the fields of robotics and security, requires exponential time to accurately solved. When the underlying graph structure varies, even the ttate-of-the-ar art RL methods require recomputa- tion or at least fine-tuning, which can be time-consuming and impair real-time applicability. This paper proposes Equilibrium Policy Generalization (EPG) framework to effectively learn a generalized policy with robust cross-graphe zero- shot performance. In the context of PEGs, our framework is generally applicable to both pursuer and evader sides in both no-cxit and multi-cxit scenarios. These two generalizability properties, to our knowledge, The core idea of the EPG framework is to train an RL policy across different graph structures against the equilibrium policy for each single graph. To construct equilibrium oracle for ainglegraph policies, we present dynamic programming (DP) algorithm that provably generates pure-strategy Nash equilibrium with near- optimal time complexity. To guarantee scalability with respect to pursuer number, we further extend DP and RL by designing grouping mechanism and sequence model for joint policy decomposition, respectively. Experimental results show that, using equilibrium guidance and distance feature proposed for goos-ggrpp PEG training, the EPG framework guarantees desirable zero-shot performance in various unseen real-world graphs. Besides. when trained under an equilibrium heuristic proposed for the graphs with exits, our generalized pursuer policy can even match the performance of the fine-tume tnn-ttned policies from the state-of-the-ar PEG methods.
the first to appear in this domain.
"This work was supported in part by the National Natural Science Foundation of China under Grants 62293541, 62293542, and 62476044; in part by the Beijing Natural Science Foundation under Grant 4232056; part by the Beijing Nova Program under Grant 20240484514; and in part by the International Partnership Program Chinese Academy Sciences under Grant IMGJJZ2022013GC.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Real-world environments are variable, and the dynamics for real-world games can be time-evolving. As an important class of real-world games, pursuit-evasion games (PEGs) can model variety of real- world problems (e.g., in robotics and security domains [30 B). Typically with a team of pursuers and adversarial evader, PEGs can be formulated with complex graph structures, where nodes and edges can be temporarily removed or added as the game proceeds. An intelligent game agent should be robust such changes. In other words, an ideal pursuer or evader policy should be robust to different map or graph inputs. Classical differential game [23] 38 and dynamic programming
32 [4] methods, while accurate, require recomputation under potential changes to game dynamics. In view of this gap, recent works on graph-based PEGs 18 34 35 employ deep reinforcement learning (RL) obtain a more flexible policy. Among the sfate-of-the-art methods, Grasper (see (17) can pretrain a generalized multi-agent pursuer policy robust to different initial conditions (e.g.. exit positions). Given an actual game situation, subsequent fine-tuning through game- tene-theoretic approaches like PSRO [66] can be used to improve the policy without recomputing from scratch.
However, the state-of-the-arr methods still exhibit two practical limitations. First, real-time applica- bility remains questionable due to the requirement of computationally intensive policy fine-tuning. Recent work (40) points out that existing methods may struggle adapt to rapid changes in urban settings (e.g., traffic jams, emergencies, and unexpected social events). To make it worse, when the graph structure significantly changes, the pretrained policy will lose the guarantee be good starting point for subsequent tuning. Second, existing training processes heavily rely on certain behavior patterns of the opponent policy, which impairs the robustness of the methods. For example, Grasper requires the evader to consistently follow the shortest path to the chosen exits. As result, the method is not applicable no-exit PEGs and not general enough for both sides of the players. Besides, such simplifications can make the RI. policy more exploitable by an intelligent opponent.
For the first problem, expect the trained policy exhibit desirable zero-shot performance across different graph structures. For the second problem, we expect the training process to be generally applicable and take strong adversaries into account. Therefore, we ask the following question:
Is there a general RL framework that can train generalized PEG policies with robust zero-shot performance in unseen graph structures?
This paper provides positive answer to this question through the following major contributions:
We propose Equilibrium Policy Generalization (EPG), a novel reinforcement learning framework that enables zero-shot generalization in Markov PEGs across different graph structures. For the first time, we show that reinforcement learning on a corpus of graphs with equilibrium policies serving as adversaries (and also guidance) can lead to generalized pursuer (or evader) policy with robust zero-shot performance in unseen real-world graphs.
For no-exit graphs, we present a dynamic programming (DP) algorithm to efficienlly construct an oracle that generates the single-graph equilibrium policies in Markov PEGs. We prove that the proposed algorithm can compute pure-strategy Nash equilibrium under a near-optimal O([S)) time complexity. We further extend this algorithm with a grouping mechanism for scalability with respect to pursuer number.
We design decentralized network architecture with a novel shortest path distance feature as state inputs represent gros-ggaph multi-agent PEG policies. Through ablation studies, verify that the distance feature, along with our reinforcement learning loss, plays an important role in cross-graph EPG training. Source code can be found in our supplementary material (with DP implementation and test files) and at http://ggtbbbooo///aaeeee//////e
For graphs with exits, we provide heuristic approach based on bipartite graph matching as an effective substitute for an exact equilibrium oracle. Directly utilizing this heuristic and approximate equilibrium oracle, we verify that the EPG framework still guarantees strong zero-shot performance that matches or outperforms the fine-tuned results from the ofte-of-theean art methods like Grasper [7]

---

2 Preliminaries
2.1 Markoy Game and Nash Equilibrium
To formulate PEG solving, introduce two-player zero-sum Markov games and Nash equilibrium.
Two-player zero-sum Markov game. An infinite-horizon two-player zero-sum Markov game is represented by tuple AS, B, p,r,7) 7), where S is the state space, A is the action space of the max-player (i.e., the team of pursuers in PEG) who aims to maximize the cumulative reward, is the action space of the min-playe (i.e., the evader in a PEG) who aims to minimize the cumulative reward, E [0, 1] 11|1|||]1]]xss is the transition probability matrix, E [0, 1] ||/||111 vector, and E (0, 1) is the discount factor.
the reward
Policy and value function. Following common notations, we denote by (a, v)) the joint policy of the two players, where is the policy of the max-player (pursuers) and v is the policy of the min-player (evader). p(s) (AA) (resp., v(s) ABB) is the max-player's (resp., min-player's s) action distribution at state E S, and μtss, a) (resp., v(s, b)) is the probability of selecting action E A (resp.. E B). Define value functions (i.((s E Di 7'r(st, a, b,) |so s: p, and Q"" a, b) = E 1 7r((st, d2, be) |so 8, 0g a, by = b; p4, v in single-agent MDPs.
joint policy where each individual player cannot benefit from unilaterally deviating from his/her own policy. Specifically, in two-player zero-sum MG, an NE (n* (n","") satisfies V < VV .²" I VV for any and v at all states. As is well known, every MG with finite states and actions has least one NE, and all NEs in a two-player zero-sum MG share the same Nash value (s) = Vi (s) = max, (s) = max, (s) [26]. In two-player zero-sum games, Nash equilibrium can be viewed as the optimal joint policy since both players cannot be exploited by their worst-case opponents. Besides, (I) 21) and (M2, (2) are both NEs, then ( 12) and (12, (1) are NEs as well [25]. To guarantee the optimality, it suffices find an equilibrium policy for each player.
Nash equilibrium. A Nash equilibrium (NE) in a game
2.2 Graph-Based Persuit-Evasion Game
In the context of pursuit-evasion games (PEGs), the transition is usually considered as deterministic, with P E {0, 1} (|]AA|[[\\ss]]] As we have mentioned, the max-player is the team of multi-agent pursuers, and the min-player is the single-agent evader. A general target in PEGs is to approximate the Nash equilibrium under the formulation of two-player zero-sum games.
To formulate large-scale problems, PEG can be represented with graph G = (V, E), where V is the set of nodes, and E is the set of undirected edges (which could indicate streets in an urban scenario). When there are pursuers, the state can be represented by the locations of all + agents, i.c.,
p E y and s, = Ug E V. The valid actions for each agent are to move to any node within the current node's neighborhood (including itself). To describe the states where the pursuit has been successful, define a termination function f V x V - {0. 1}. When f (sp. se) 1, the game is terminated, and a reward of +1 is received. Note that the discount factor < encourages the pursuers to capture the evader as soon as possible in the no-exit scenario. If there are exits in the graph, then another termination function g V {0, 1} should be defined. When ((*)) = 1, the game is terminated as well, but a reward of -1 will be received.
s = (sp. se), where sp = (i:). o2
3 Equilibrium Policy Generalization
As we have mentioned, existing PEG methods can have difficulty adapting to the changes of graph structures or extending to different scenarios. Here, we propose a general reinforcement learning framework called Equilibrium Policy Generalization (EPG) that facilitates cross-graph zero-shot generalization for diverse PEG settings. The overall training pipeline is shown in Figure [
Intuitively, training set (right) consisting of a variety of graphs with different structures is first generated. For each graph G,, an equilibrium policy (HTī, vī") is derived from an equilibrium oracle. Then, reinforcement learning (left) is conducted to learn generalized policy. with the dynamics constructed through each graph G and opponent detailed construction of the reinforcement learning process established upon soft actor-critic (SAC).
the training set. Section 3.1 introduces a
3

---

Reference Policy j
(+( Policy Loss
Ban
Positions
G (1f
G ( 1
Policy Model x
m(e)
G (1
(V.E)
State
Training Set
Opponent Policy o²
(T
Figure 1: Training pipeline of Equilibrium Policy Generalization
Section 3.2
presents a theoretically sound equilibrium oracle based on dynamic programming (DP). designs a multi-agent pursuer policy representation specified for cross-graph PEG tasks.
Section 3.3
3.1 Reinforcement Learning with Equilibrium Adversary
SAC [12 6 is well- known off-po reinforcement learning framework that maximizes expected return regularized under a policy entropy term. Specifically, the value function in discrete-action SAC (6) is defined as V(s) (s) (Q a) log (s,, a)). The losses of the value network Q+
and the policy network Ty are computed Jq (Ø) Es,a (Qo(s, a) - (r T (v()))) and (0) Bs [o: log (s, a) ((s, a)). respectively. Besides, the temperature under target entropy H adaptively updated under loss J(a) E.,a [-ar (log ((, a) + H) Here, we use SAC as the foundation algorithm to introduce the RL pipeline in Equilibrium Policy Generalization.
In order to train generalized policy, our reinforcement learning process goes through the different PEG graphs in the training set. The major difference between our method and the common multi-task learning methods is that we use the equilibrium 1* as the opponent policy to construct an adversarial environment for each graph. As is shown in Figure [ the equilibrium opponent offers an action b that directly serves to generate the transition (s, a, b, r, ss) in the current PEG graph To our knowledge, this is novel approach not yet considered in the game RL domain. Because D² is hardly exploitable by any strategy, reinforcement learning against such a policy avoids overly exploiting a specific behavior pattern and makes the training process generally focus on wross-graph policy robustness. Since a truly robust policy should not perform poorly against the corresponding equilibrium opponent in any of the graphs, policy space. Cross-gra grash reinforcement learning can be regarded as an efficient way of fulfilling such exclusions. When the training set is diverse enough, only small area in the parameter space will be left after RL training, where we expect to derive a policy with robust zero-shot generalization.
this necessary condition to exclude the weak strategies from the entire
However, since the equilibrium opponent is hardly exploited and the PEG is sparse reward environ- ment, the original SAC algorithm can suffer from inefficient exploration even under a single graph. To deal with this problem, the equilibrium μ² can also be used as a policy guidance for the training process. Specifically, we regard 2 as a reference policy and append an additional KL-divergence term DRL. (n",, T) to the original policy loss. When μ. is pure strategy, it holds that DKL. (n² (s), x (s)) - -log T (ss a²) where a" is the deterministic action of 4 (s). In this case, the divergence-rrgullaize policy loss can be computed as J₂ (0) Eg [ log (s, a²) + log Te a) ( a)), where 3 a hyperparameter that keeps a balance between policy guidance and reinforcement learning.
As is shown in Figure global state s is sampled under randomly selected graph G from the training set. The reference policy μ² and the model To generate a deterministic action a" and strategy T (s), respectively. The updated through gradient descent. For transition generation, a joint action (a, b) under s is sampled and sent into the graph to compute the reward and the subsequent state s'. In the training phase, is sampled randomly, and (r, s') is used to train the value network Qo under (Ø). In the testing phase, is sampled from the learned policy na. and (r, s') is used for trajectory generation and evaluation.
reggulaiiee policy loss (=) is then computed, and my is

---

3.2 Single-Graph Equilibrium Oracle Construction
As our EPG framework requires the equilibrium policy (n²', v²) for each graph in the training set, equilibrium oracles should be provided to guarantee upplicability in PEGs. In this section, present effective methods to construct accurate or approximate equilibrium oracles for different scenarios.
3.2.1 Dynamic Programming for No-Exit Markoy PEGs
Determining whether the pursuers can always capture the evader in a no-exit PEG is proved to be an EXPTIME-complet problem (see M... This result suggests that an accurate equilibrium oracle could incur a time complexity of 2 SI), where |S] is the number of all game states, which is exponential in the agent number + For sequential PEGs under no-exit graphs, [32] proposes an efficient method to compute the minimum steps for the pursuers to capture the evader. The idea is to iteratively expand the set states where the pursuit guaranteed to be successful under the optimal strategy. During the O(SS)) state expansion, the equilibrium policy is also generated. For Markov games, however, the method is not applicable since the moves for both players are simultaneous.
On the other hand, the classical marking algorithm (see ( can have a worst-case time complexity of ((S))) in practical Markov PEGs. Even when the pursuer number is small (e.g., two or three), the algorithm cannot scale with the number of nodes in the graph, which can be large in the real world. In view of this gap. we first show how to apply the idea of state expansion simultaneous games and provide a more efficient dynamic programming (DP) algorithm for Markov PEGs.
Algorithm 1: Dynamic programming (DP) for Markov PEGs in no-exit graphs
Input: graph = (V. E), pursuer number m, and termination function f y x V + {0,1) Initialize empty queue Q and array D 2 for pursuer state (positions) 8p E y do for evader state 8e V do if [8p, Se) = 1 then DSpp 8e)
6
Push (8p, 8e) into º
end
end
end
10
while Q is not empty do
11
Pop the first element (sp. se) from 2
for evader neighbor ni E Neighbor(se) An', E V. (ne. E E, D(s, n².) ) > D(sp. se) do
12
13
for pursuer neighhor np E Neighbor(sp C Vm, (mp: ne) = oo do
14
(Tp.p ne) < D(sp. 8c) +1
15
Push (mps ne) into Q
16
end
end
18
end
19
for global state (sps Se) E Vm x V do
(0ps 86)
arg min neighbor u, of sy
max neighbor ne of Bc
D(np, ne)
21
((p: Se) f
arg max neighbor ne of de
min neighbor n. sp
D(np, mee)
end
Output: pursuer policy μ n x V pm and evader policy v : ym x -V
The proposed DP algorithm is shown in Algorithm | Intuitively. D(sp. se) is the minimum number of pursuit steps under the optimal pure strategy and is computed through a new form of state expansion (lines 10-18) using a queue Q. Based on D(.), a joint policy (μ, v)) is generated through minimax computation (lines 19-22). When pure-strategy Nash equilibrium exists, the following theorem shows that the computed D(-) induces the Nash value, and the joint policy must be an exact Nash equilibrium. That is to say, the DP algorithm can generate the optimal pure strategies for both players.
5

---

Theorem 1 (Near- eetrroppiimllty of DP policy). If there exists a pure-strategy Nash equilibrium in the no-exit PEG, then the DP algorithm induces the Nash value (* (Sp, se)) = 7 ((5).se) and the corresponding Nash equilibrium (n,, = (H,
The detailed proof of Thcorem I jis based on mathematical induction and reserved in Appendix A Actually, Algorithm Deeimmmeefffiiii Tefficiently solves the Bellman minimax equation (see (39] under the existence of pure-strategy Nash equilibrium. Note that the update condition D(sp. Se)
guarantees that
every state (sp.Se) Se) is pushed into and popped from Q at most once. Therefore, the time complexity of Algorithm| is near-optimal (IS)),, where Ô hides the logarithm factors required for picking each (Np, ne) through preserving data structures like balanced trees. Also note that the computation of (((s) and (s) can be reserved online and thus does not affect the overall time complexity.
Algorithm I suggests that the Nash value admits efficient estimation when the PEG only admits a one-sided termination function. Compared to direct value iteration (see [14). the DP algorithm can exactly compute the equilibrium policy within finite iterations. The existence of pure-strategy Nash equilibrium implies that a successful pursuit is guaranteed for all E S (i.e., D(s) < oo). For example, the optimal strategy in any free-form G is a pure-strategy Nash equilibrium if regard adjacency as the condition of a successful pursuit. Even when this assumption does not globally hold in PEG, Algorithm [ still induces a near-optimal pursuit strategy for the states with finite (-)).
3.2.2 Heuristic Approach for Multi-Exit PEGs and Grouping Extension of DP Approach
For PEGs with exits, it can be more difficult to design a DP-like equilibrium oracle with rigorous guarantees due to the existence of the other termination function g. Nevertheless, we observe that the cooperative behaviors among pursuers can be approximately abstracted as one-to-one exit allocation. Based on this observation, we provide equilibrium heuristic featuring bipartite graph matching to approximately generate equilibrium policies. The detailed construction reserved Appendix B due to space limitations. Compared to the DP approach in no-exit scenarios, the hcuristic approach computes the current policy for each state independently and can be directly exccuted during RL training, with time complexity polynomial in the pursuer number for any current state. Note that the polynomial time guarantee also implies its scalability with respect to agent number.
In order to facilitate the scalability of the DP approach in no-exit graphs with many pursuers, here we further extend DP with a grouping mechanism to trade optimality for applicability. Note that the DP algorithm is directly applicable when there are two or three pursuers. For large pursuer number m, we can express it as the summation of twos and threes. For example, if there are m = pursuers, we have that 6- = 2 + 2 + 2 and can thus group them into three sub-teams, each with two pursuers. For the pursuer side, we can simply use the exact 2-pursuer policies under an arbitrary grouping result to construct 6- 6-pursuer policy, which is empirically strong due to the optimality of the DP algorithm.
For the evader side, we expect that it should not be easily exploited by the grouping- based pursuers. However, it does not know the exact result of grouping. Therefore, we follow minimax criteria to construct the evader policy at any current state s. We use Sy = (s' (s), se), .s = (s)- s2)) E Sy to denote the in-team states for the global state s under any possible grouping result with k sub- teams. Then, we compute 8. = arg min {max=_ D(s))) }. where ((s))) D(sp 8e) is the computed result from the DP algorithm. The evader policy to follow the DP policy v² (s!). where j = arg max Dss.). Intuitively, the DP-based evader always considers the worst-case grouping and ensures that it is hard for at least one sub-team to capture it in this case. While introducing an extra online time complexity, the grouping mechanism avoids the exponentially growing complexity of running Algorithm I and makes the DP approach applicable to the scenarios with many pursuers.
3.3 Cross-Graph Representation of PEG Policy
To represent a generalized PEG policy, the network architecture should be capable of encoding the meaningful state information across different graph structures. Besides, since the policy should be applicable to the team of homogeneous pursuers, it is appealing to design decentralized architecture with shared parameters. Such a network architecture can be robust to the change of agent number and allow for decentralized execution when necessary. Under the principle of sequential decision-making, a joint policy can be decomposed as π (a), 022 ... am ss) = I < |8, @1," 1), where (s, ".."". .4-1) indicates the global state after the first I - 1 < pursuers take actions (a.)

---

State
Shortest Puth Distince Festure
Encoder
112,11
U.J.11
P.L.0J
[0,2,21
U.JI1
[,0,1]
(T|ss)
Adjacent Matrix
Notaton ner Nedde
Foraae
.|. s, (1
0::0
rT- |8 d1,
Pointer
(a:)
Next (6,9g)
Figure 2: Sequence model with cross-graph policy representation
With the mooee-meniooeed considerations, we present sequence model with an attention-based architecture (see Figure 2 to represent the cross-graph joint policy. For a team of pursuers with m agents, the sequence model queries the policy network m times under a fixed adjacent matrix M E {0, 1) ) (n (VI) for the current graph. The input is composed of a state feature 8, that describes the current global state and the information of node index for the current acting agent. To uniformly capture the state information across different graphs,
use the shortest path distances to the m + agents (including the evader) and the exits (if existing) as the initial feature of each node E V. The state feature 8 is composed of the normalized features of all nodes. The shortest path an important and well-examined concept in graph theory [2], and the distance between any two nodes can be preprocessed using the (nn)) Floyd algorithm. In Appendix A.2 further prove that the input (sy, c) is dense enough to identify the current global state in sequential decision decision-making. making.
Given the state feature input 8f, we borrow the ideas from the existing works robot exploration 19 to construct a policy network (on the right of Figure 2). We first embed s into Rdxx and send into an encoder composed of multiple self-attention [29] layers, where d is the embedding dimension. Each layer takes the output h of the last layer as the input and outputs h' using masked attention:
k Va wij Σe Σt-
q. -Whh, k Wkh,, 0 Wyh,, Uy
min (wi,, My) vy.
where Wo. WK, Wy E Rddd are the weights to be learned. Theoretically. it requires Diameter(C) (G) layers to globally broadcast the local information of node since M is the adjacent matrix. However, in contrast to using a low-level node feature with indicators (see Grasper (17),, using high-level distance feature allows the node itself to encode long-term information. With the shortest path distance feature, we can use fixed number of attention layers (6 in practice) for information transmission.
Denote by h the output of the encoder, and recall that e is the node index corresponding to the current acting agent. We further use a decoder without masking to gather global information. Specifically, the decoder uses he to query in the output features all nodes, with the keys equal to the values:
q WQhe k; Wxr,, v, Wyhn Uj Vd W Ei-re" h Ei= WyUj. The decoder output he is further concatenated with hi and projected into Rdd Then, it is used as a query for a pointer network [33], which takes the features of the neighbor nodes Ane for the current agent as the keys and values. The pointer network directly outputs the attention vector as the current policy (i.e., क (a|s) = wa) since the number of the neighbors aligns with the number of the valid actions.
kg
233
After the first query through the policy network, an action an for the first agent is sampled from (a]s), and the state updated as s' (s. a1). The subsequent queries follow the same process described above. Under the decomposition of sequential decision-making, while the process generates the joint action (a, (c))e) sequentially, is equivalent to a direct sampling from the joint policy, Note that querying the policy model is practically efficient, especially with the help of GPUs. When the graph structure changes, simply rerun the Floyd algorithm, instead of the m+1) DP algorithm.
7

---

Table 1: Performance of RL pursuer / evader against DP oracle in no-exit PEGs with 2 pursuers
Pursuit Success Rate f
Evasion Timestep t
Graph Structure
DP DP
DP
SPS
DP
DP DP
DP RL,
Grid Map
1.00
1.00
1.00
12.29 + 2.06
11.88 + 2.39
Scotland- Yard Map
1.00
0.99
0.17
15.13 + 2.77
12.57 +: 2.96
Downtown Map
1.00
0.99
0.17
14.22
3.27
11.83
3.122
Times Square
1.00
0.98
0.14
16.47 =323
14.68 = 3.11
Hollywood Walk of Fame
1.00
0.62
0.02
25.56 + 5.03
20.00 + 4.99
Sagrada Familia
1.00
0.66
0.04
21.88
4.82
17.89
4.59
The Bund
1.00
0.60
0.13
25.26 - 6.17
20.59 = 5.59
Eiffel Tower
1.00
0.97
0.81
23.42 + 6.48
18.47 1 6.12
Big Ben
1.00
0.91
0.13
27.89
6.35
21.58 = 6.38
Sydney Opera House
1.00
0.74
0.13
26.92 + 5.89
22.37 + 6.16
Experiments
In this section, we verify that our EPG framework can train a generalized policy with robust zero-shot performance under unseen graph structures. Using 76 procedurally generated maps in the Dungeon environment [5]. we construct a heterogeneous training set by discretizing each map into small- scale (100-node) and large-scale (500-node) graphs. The policy training follows the cross cross-graph graph reinforcement learning pipeline in Section 3.1 In no-exit scenarios with 2 or 3 pursuers, we directly use the DP algorithm (Algorithm [ in Section 3.2 as an accurate equilibrium oracle. When there are more pursuers, we use the grouping extension of the DP approach to construct an approximate equilibrium oracle. In multi-exit scenarios, we the heuristic approach to construct the approximate oracle. Besides, we use the sequence policy model in Section 3.3 to represent either pursuer or evader policy. For the evader side, the policy model is reduced The training time costs are reported in Appendix
single policy network, with μ²' and n²
exchanged in Figure [ performance of the learned pursuer or evader policy under unseen graphs without further fine-tuning
C.3 We test the zero-shot
4.1 Performance Tests in Woald No-Exit Graphs
In no-exit graphs, the DP policy generated by Algorithm ii the optimal pure strategy for both players when the pursuit is guaranteed for all states. With this theoretical guarantee, we can use the DP oracle to construct the adversarial opponent and benchmark the zero-shot performance of the RL pursuer or evader. Our test graphs include Grid Map (a 10 x 10 grid). Scotland- Yard Map (from the board game Scotland- Yard), Downtown Map (a real-world location from Google Maps), and famous real- world spots (from Times Square to Sydney Opera House). The real-world graph structures for testing illustrated in Figure g We set the termination function f(s) to be when half of the pursuers are simultaneously adjacent to the evader. This moderate success condition guarantees pursuit for all synthetic and real-world graphs described in the main paper when the pursuer number is more than 1.
We first evaluate the zero-shot performance of the trained RL policies against the accurate DP oracle in no-exit PEGs with 2 pursuers. The result under each graph is averaged over 500 tests, each of which is forced to terminate after 128 steps (corresponding to the length of an episode). The pursuit guaranteed to be successful under the DP pursuer, while the DP evader attempts to avoid capture by maximizing the termination (evasion) timesteps. As is shown in Table when we use the RL pursuer trained through EPG to replace the DP pursuer, the pursuit success rates are still kept over 0.6. In comparison, if we simply use a shortest path strategy (SPS) to directly approach the DP evader, the success rates can be sensitive to graph structures and low on average. On the other hand, when we use the RL evader to replace DP, the evasion timesteps do not drop significantly. The results demonstrate that our RL policies generalize well across graphs against the unexploitable DP opponent policies.
Now we evaluate the zero-shot performance of the trained RL policies against different opponents. Besides the DP opponent, we show the results of our RL pursuer against our RL evader Table 2 The success rate of RI. RL is always 1 and thus omitted. Furthermore, we include the results of the approximately best-responding (BR) policies directly trained against our RL policies on the test graphs. Ideally, such results could reflect the worst-case performance of our RL policies. However,
8

---

Table 2: Performance comparison of RL pursuer evader against different opponents
Pursuit SR
Evasion Timestep
Graph Structure
RL
BR
RL -L-10 DP
RL RL
BR RL
DP-Re RL
Grid Map
1.00
1.00
14.34 + 5.08
11.67 + 2.60
11.88 + 2.39
Scotland- Yard Map
1.00
0.99
17.82 +: 7.31
13.12 + 3.65
12.57 + 2.96
Downtown Map
0.99
0.99
17.65 + 8.72
13.81 + 5.83
11.83 3.12
Times Square
0.95
0.98
20.29 = 9.65
16.20 5.16
14.68 = 3.11
Walk of Fame
0.67
0.62
34.34 20.18
20.22 + 9.60
20.00 4.99
Sagrada Familia
0.76
0.66
26.87 11.00
18.83 6.30
17.89 4.59
The Bund
0.56
0.60
30.66 + 17.27
21.91 + 10.58
20.59 + 5.59
Biffel Tower
0.98
0.97
28.41 + 16.80
19.28 + 10.48
18.47 + 6.12
Big Ben
0.94
0.91
33.24 = 18.71
23.07 = 12.91
21.58 6.38
Sydney Opera House
0.80
0.74
32.94 + 14.72
25.78 + 16.79
22.37 + 6.16
the BR policies are generally hard to train in practice, possibly because the EPG policies are fairly strong. We record their best results during 20000 training episodes. As is shown in Table while the BR policies are better at exploiting our RL policies comparison with our RL opponent policies, they show no advantage in comparison with DP. Therefore, considering the results in Table [ we can say that EPG policies have robust cross- graph sero-shot performance under unseen graph structures.
4.2 Ablation Study and Extended Evaluations
Here we analyze the important aspects of our cross-graph policy training. We use 10 unseen Dungeon maps and their corresponding graphs testing set. We conduct the ablation study by comparing the termination timesteps of different pursuer policies against the DP evader in no-exit PEGs.
Guidance
120
120
Tarinnston Timeslop
Terminstoo Timeslop
100
80
80
60
5000
10000
15000
20000
5000
10000
15000
20000
Episode
Episode
Figure Termination timesteps pursuer policies under training set (left) and testing set (right)
As is shown in Figure bars representing standard deviations), when we remove the equilibrium guidance from our framework, it less efficient to train the generalized pursuer policy under the remaining SAC loss (orange). This phenomenon verifies that the policy exploration of SAC itself can have low efficiency under the sparse reward environment with an equilibrium adversary. When we remove the original SAC loss, the training becomes kind of supervised learning, and the learned policy suffers from a clear performance decline due to the lack of the reward signal (blue). Therefore, it is reasonable to combine equilibrium guidance with reinforcement learning against an equilibrium adversary for effective policy generalization (black). If we directly use the 2-dimensional position and the agent indicators to replace the shortest path distances as the feature of each node, the learned policy suffers from a significant performance decline and cannot guarantee zero-shot performance (red). This verifies that our distance feature is suitable for cross-graph generalization of PEG policies.
We have also conducted some extended evaluations under no-exit PEGs. We consider the scenario with 6 pursuers and use the proposed grouping mechanism to construct an approximate DP oracle. The corresponding results are provided Table 3 showing even higher success rates RL pursuit in comparison with Table I In Appendix F we further show that our RL pursuers can have a zero-shot performance even better than DP when the pursuit not globally guaranteed. Additionally, while the pursuer policy is trained graph set with an average node number of 152.24, we find that

---

1.0
MT-PSRD-Ag
Ukit spatraa Evarter
0.0
R. Tuzaer aebareeba..oo 6OL
1.20
Ged
1:00
Scolland Vardi Map
0.6
0.25
0.25
0.4
0.50
0.50
0.23
0.25
0.2
0.00
0.00
0.0
+0.25
-0.25
+0.00
-0.50
-04
-0.75
-2.5
5020
10020 Episodo
15000
20092
-1.20
200
400
500
500
-1.00
200
400
900
802
Runtime (5)
Runtim (5)
Figure 4: Zero-shot performance in 8-exit PEGs during training (left) and testing (mid & right)
can directly generalize to large-scale graphs possibly with more than 1000 nodes (Appendix F. Besides, we find that our policies significantly outperform the PSRO policies directly trained on the test graphs (Appendix F.2). These results further demonstrate the versatility of our EPG framework.
4.3 Performance Comparisons in Graphs with Exits
Since the state-of-the-art approaches in graph-based PEGs (including Grasper [1 and multi-task PSRO (MT-PSRO) (18) deal with multi-exit PEGs, we also apply our EPG framework to the same problem setting of pursuers, 1 evader, and 8 exits described in the paper of Grasper [17]. As is mentioned in Section 3.2 we design an equilibrium heuristic based on bipartite graph matching (see
Appendix B to construct an approximate equilibrium oracle. As is shown in Figure 4 (left), our EPG framework steadily trains the RL pursuers under different hyperparameters E (0.01, when using the heuristic approach. Mere supervised learning (green) without SAC loss can no longer guarantee a steady improvement unseen graphs, though it can simply work in the no-exit scenario.
Since 17 also uses Grid Map and Scotland- Yard Map as two fixed testing graphs, it is direct to evaluate the zero-shot performance of our RL pursuers under the same game rules. The comparative methods of Grasper, MT-PSRO, and MT-PSRO with augmentation (MT-PSRO-Aug all train their policies given the graph structure. Nevertheless, Figure (mid & right: with results from (17) shows that our zero-shot performance (the dashed lines) under the unseen graphs (0.637 for Grid Map and 0.652 for Scotland- Yard Map) significantly outperforms their zero-shot performance (the starting points), which is with respect to unseen initial conditions. Even after a 10-minute fine-tuning process using PSRO [16), only Grasper in the Scotland- Yard Map can match the zero-shot performance of our policy. This result further demonstrates the generalization capability of our EPG framework.
Conclusion
This paper proposes Equilibrium Policy Generalization (EPG), novel reinforcement learning framework for training generalized PEG policies with robust zero-shot performance across graph structures. Established upon the idea of constructing adversary and guidance with equilibrium policies, EPG features general cross-graph RL pipeline applicable to both pursuer and evader sides in both no-exit and multi-exit scenarios. For no-exit PEGs, we propose dynamic programming (DP) algorithm as equilibrium oracle and theoretically prove that it generates pure-strategy Nash equilibrium with near-optimal time complexity. We further extend DP with grouping mechanism and equip RL with sequence model to facilitate scalability. Experiments and ablation studies verify that our EPG framework can effectively train a generalized pursuer or evader policy with robust zero-shot performance in unseen real-world graphs. When trained with matching- based equilibrium heuristic that we propose for multi-exit PEGs, the RL pursuer policy exhibits a strong zero-shot performance that matches or outperforms the fine-tuned results from the state-of-the-ar art methods.
Although this paper focuses on pursuit-evasion games and thus introduces handcrafted DP/heuristic equilibrium oracles, the EPG framework is in principle applicable to any other game scenario through the use of general and approximate oracles like PSRO. One limitation of this work that we only focus on the case where both players have perfect information of the game state. It can be interesting to further examine whether the perfect-information equilibrium oracles are still beneficial for robust policy learning under an imperfect-infoomaatie partially observable game setting.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China under Grants 62293541, 62293542, and 62476044; in part by the Beijing Natural Science Foundation under Grant 4232056; in part by the Beijing Nova Program under Grant 20240484514; and in part by the Interna- tional Partnership Program of Chinese Academy of Sciences under Grant 104GJHZ20220130 3GG. We also thank all the reviewers for providing valuable comments that helped us improve this paper.
References
[1] Álbert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-511 1999.
[2] John Adrian Bondy and Uppaluri Siva Ramachandra Murty. Graph theory. Springer Publishing Company, Incorporated, 2008.
[3] Yuhong Cao, Tianxiang Hou, Yizhuo Wang, Xian Yi, and Guillaume Sartoretti. Ariadne: reinforcement learning approach using attention- based deep networks for exploration. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 10219-10225. IEEE, 2023.
[4] Jiajun Chai, Zijie Zhao, Yuanheng Zhu, and Dongbin Zhao. A survey of cooperative multi-agent reinforcement learning for multi-task scenarios. Artificial Intelligence Science and Engineering, 121, 2025.
[5] Fanfei Chen, Shi Bai, Tixiao Shan, and Brendan Englot. Self-leaming exploration and mapping for mobile robots via deep reinforcement learning. In Aiaa scitech 2019 forum, page 0396, 2019.
[6] Petros Christodoulou. Soft actor-critic for discrete action settings. 1xXiv:9910007205 2019.
arXiv preprint
[7] Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoc V Le, Sergey Levine, and Yi Ma. SFT memorizes, RL generalizes: A comparative study of foundation model post-training In Forty-second International Conference on Machine Learning, 2025.
[8] Timothy H Chung, Geoffrey A Hollinger, and Volkan Isler. Search and pursuit-evasion in mobile roboties: survey. Autonomous robots, 31:299-311 216, 2011.
[9] Wojeiech M Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafici. David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. Advances in Neural Information Processing Systems, 33:17443-1745 2020.
[10] M Fromme and M Aigner, A game of cops and robbers. Discrete Appl. Math, 8:1-12, 1984.
[11] Arthur Goldstein and Edward Reingold. The complexity of pursuit on graph. Theoretical computer science, 143(1):93-112, 1995.
[12] Tuomas Haamooja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint 1rXiv:1812.05905. 2018.
[13] Hado Hasselt. Double Q-learning. Advances in Neural Information Processing Systems, 23, 2010.
[14] Karel Horák and Branislav Bošanský. Dynamic programming for one-sided partially observable pursuit-evasion games. In International Conference on Agents and Artificial Intelligence. volume 2, pages 503-510. SCITEPRESS, 2017.
[15] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. GraphMAE: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD conference knowledge discovery and data mining, pages 594-604, 2022.
11

---

[16] Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls. Julien Pérolat, David Silver, and Thore Graepel. A unified game- teeeettheoeetc approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
[17] Pengdeng Li, Shuxin Li, Xinrun Wang. Jakub Cerný, Youzhi Zhang, Stephen McAleer, Hau Chan, and Bo An. Grasper: A generalist pursuer for pursuit-evasion problems. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 1147-1155, 2024.
[18) Shuxin Li, Xinrun Wang. Youzhi Zhang, Wanqi Xue, Jakub Černý, and Bo An. Solving large- scale pursuit-evasion games using pre-trained strategies. In Proceedings the on Artificial Intelligence, volume 37, pages 11586-1183 11544, 2023.
the AAAI Conference
[19] Yang Liu, Peng Zhang, Hangyou Yu, Pingping Zhang, Jie Zhao, Dong Wang, and Huchuan Lu. Two heads are better than one: Collaboration-orientte multi-agent exploration system. IEEE Transactions on Cognitive and Developmental Systemx, 2025.
[20] Runyu Lu, Yuanheng Zhu, and Dongbin Zhao. Constrained exploitability descent: An offline reinforcement learning method for finding mixed-strategy Nash equilibrium. In Forty-second International Conference on Machine Learning. 2025.
[21] Runyu Lu, Yuanheng Zhu, and Dongbin Zhao. Divergence-regularize discounted aggregation: Equilibrium finding in multiplayer partially observable stochastic games. In The Thirteenth International Conference on Learning Representations, 2025.
[22] Runyu Lu, Yuanheng Zhu, Dongbin Zhao, Yu Liu, and You He. Last-iterate convergence to approximate Nash equilibria in multiplayer imperfect information games. IEEE Transactions on Neural Networks and Learning Systems, 36(8):13859 13889911333999998,,3333833339831 2025.
[23] Kostas Margellos and John Lygeros. Hamilton-Jacobi formulation for reach-avoid differential games. IEEE Transactions on Automatic Control, 1649):1849-1861 2011.
[24] Rongjun Qin, Feng Chen, Tonghan Wang, Lei Yuan, Xiaoran Wu, Yipeng Kang, Zongzhang Zhang, Chongjie Zhang, and Yang Yu. Multi-agent policy transfer via task relationship modeling. Science China Information Sciences, 6788)182101, 2024.
[25] Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.
[26] Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):0095-1100 1953.
[27] Jingbo Sun, Songjun Tu, Haoran Li, Xin Liu, Yaran Chen, Ke Chen, Dongbin Zhao, et al. Unsupervised zero-shot reinforcement learning via dual-value forward-backwerr representation. In The Thirteenth International Conference on Learning Representations, 2025.
[28] Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv: 1706. 05296. 2017.
[29] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[30] Rene Vidal, Shahid Rashid, Cory Sharp. Omid Shakernia, Jin Kim, and Shankar Sastry. Pursuit- evasion games with unmanned ground and aerial vehicles. In Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164), volume 3, pages 2948-2955. IEFF, 2001.
[31] Rene Vidal, Omid Shakernia, H Jin Kim, David Hyunchul Shim, and Shankar Sastry. Proba- bilistic pursuit-evasion games: Theory, implementation, and experimental evaluation. IEEE Transactions on Robotics and Automation, (8(5):662-661 2002.
12

---

[32] Marcos AM Vieira, Ramesh Govindan, and Gaurav S Sukhatme. Optimal policy in discrete pursuit-evasion games. Department of Computer Science, University of Southern California. Tech. Rep, 2008
[33] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. Advances in Neural Information Processing Systems, 28, 2015.
[34] Wanqi Xue, Bo An, and Chai Kiat Yeo. NSGZero: Efficiently learning non-exploitable policy in large-scale network security games with neural Monte Carlo tree search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4646-4653, 2022.
[35] Wanqi Xue, Youzhi Zhang, Shuxin Li, Xinrun Wang, Bo An, and Chai Kiat Yeo. Solving large-scale extensive-form network security games via neural fictitious self-play. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2021.
[36] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of PPO in cooperative multi-agent games. Advances in Neural Information Processing Systems, 15:24611-246224 2022.
[37] Zijie Zhao, Honglei Guo, Shengqian Chen, Kaixuan Xu, Bo Jiang, Yuanheng Zhu, and Dongbin Zhao. Empowcring multi-robot cooperation via sequential world models. arXiv preprint arXiv:2509. 13095, 2025.
[38] Zhengyuan Zhou, Ryo Takei, Haomiao Huang, and Claire Tomlin. A general, open-loop formulation for reach-avoid games. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pages 6501-6506. IEEE, 2012.
[39] Yuanheng Zhu and Dongbin Zhao. Online minimax Q network learning for two-player zero-sum Markov games. IEEE Transactions on Neurul Networks and Learning Systems, 33(3):1228- 1228- 1241, 2020.
[40] Shuxin Zhuang, Shuxin Li, Tianji Yang, Muheng Li, Xianjie Shi, Bo An, and Youzhi Zhang. Solving urban network security games: Learning platform, benchmark, and challenge for Al research. arXiv preprint arXiv:2501.15559 2025.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and Section 1, emphasize the major contribution of proposing the Equilibrium Policy Generalization (EPG) framework.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In Section discuss the limitation of this work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

For the two theoretical results (Theorem and Proposition 1), we provide their proofs in Appendix A.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: In Appendices and D, we include the information needed to reproduce our main experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the data and code as well as the instructions the Supplementary Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/ccppplliiggudeeeeeeeeeeeee Coaee///ddeeebmmmcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Appendices C and D, we specify all the training and test details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report error bars for all the learning curves and the termination timesteps in the tables.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix C.3, we report the computer resources and detailed time costs. In the last paragraph of Section 3.3, we also compare the inference time complexity of tabular DP and parameterized RL policies under varying graph structures.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: tttttp:://nerrissccoom http://wwwrrr.eccupuul/cccaaaaaa
Answer:
[Yes]
Justification:
We confirm that the research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the broader impacts in Appendix G.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We confirm that the paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: In Section 4, cite the paper that introduces the Dungeon environment, where we derive various graph structures from the procedurally generated maps.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does formally release any new assets. While reusable in future research, the generated data (including the graphs and policies) are mainly for evaluation purposes in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We confirm that the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We confirm that the paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We confirm that this research does not involve L.MSs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurl)) htttree//eerrpp.cc/oooffeeeeeeee /0//////eoeeeeece//22////1/ for what should or should not be described.
20

---

A Omitted Proofs
A.1 Proof of Theorem
Proof. For no-exit PEGs, the Nash value satisfies the following Bellman minimax equation:
(r(s.a.b) +Y Σ P(s.a.b,s)V)'(())) f(s) =0
max min Σ a)s,a) (())E((A) BEB aEA
(*())=
3EES
1, f(s) =1
Since the transition is deterministic and a non-zero reward is received only when a termination state is reached, we can simplify the Bellman equation as follows:
max min E p(s,a) b))s,, [()) 0
(*())
(())EA(A) BEB aEA
1, f(s)= =1
The equilibrium policy for the max-player satisfies:
1e (s) E arg max ((A)E((A)
min BEB aEA
(s
When there is pure-strategy Nash equilibrium in the game, the arg max has a pure-strategy solution, and the Bellman equation can be further simplified:
V
y max min (*'''= = P(s,a,
(I)
a bEB
Note that the Nash value has the form of V*(s) (d E N). Therefore, we consider using
mathematical induction. We assume that V* (s) D(s) holds for all states s that satisfies either V*(s) = - D(s) d when d < k (7d ))) We want to prove that V*(s) D holds for all states that satisfies either (s) 7*th or D(s) k. Clearly, our initialization guarantees that the proposition holds for = 0. Our update condition D(ny, n2) = oc guarantees that every state E S is pushed into and popped from Q at most once. Note that the following proof reverses the notations of s and in (I to better align with = (sp: in Algorithm
Now, we prove the first half of the proposition. For an arbitrary state s' = (np: that satisfies V*(s")= = - the simplified Bellman equation b s, E B(n,)) such that (s')') = >V*(s P(s', .a,b)). Therefore, there exists s (sp. such that (s) D(s) k - co, which implies that the algorithm once pushed s' into Q. Besides, the Bellman equation guarantees that VV E (, V* V*(P(s', a, b)) > V*(P(s', aa,b), (*) = k-1 7 By induction hypothesis, ((pp.n') I D(sp, se) holds for any neighbor n' of nl. Therefore, the algorithm must enumerate ne when popping s (sp, sc). If we have D(np. ne) = oc at the moment, then np will be enumerated in the inner loop, and we will have D(np. ne) = (e)p. +
I guarantees that there exists a = 8p E A(nn)) and
kh- According to the first half of the induction hypothesis, we have that
Now we complete the proof by showing that (np, n.) < 30 implies D(n,, n.) = k. Actually, if D(n, ne)) < co, then ((s') must be computed by adding to some D(s 2 k: Since s" must
be popped from Q no later than 8, it is contradictory to the fact that D(s") D(s) = k - If D(np, Re)) < k, then the second half of the induction hypothesis implies that (*( = D(np.ma) which is contradictory to the fact that V*(s'= =
Then, prove the second half of the proposition. For arbitrary state s' = (Np: ne) that satisfies D(s') k. the (ss) must be computed by adding 1 to some D(s) = k - 1, where & = (8px 8e). According to the first half of the induction hypothesis, we have V*(() = 2 The algorithm guarantees that DS5 n²') < D(Sp 8.) -k-1 holds for any neighbor n' of nz. By induction hypothesis, it holds
that Vb' E B((ne,, , (P(s', (ffs",,,1 a.a,0, ()) 2 V=(P(s', a, b)) when a = 8p E A(ri,) and b = 8. E B(ne)). Therefore, min (P(((s', a, b)) = k-1 when a = 8p E A(np). If there exists at = E A(np) bEB(T.))
such that min V- (P(s', b)) bEB(R..
then we let b² = arg min (P((s',,'t > x-1 beB(n.)
21

---

and let st = (s/, st bt). According to the first half of the induction hypothesis, s n²)) - D(s .t) 1--11 holds for any neighbor n' of ne- Since (ss st] (spp, Se), st must be popped from Q earlier than 8, which means that (ss) = oo when sf popped. Therefore, s' = (Mps ne) must be enumerated when st is popped, which contradictory the fact that D(s') = 2o when popped. Therefore, (s') = max min (*(P(s', a, b)) -
aEA BEB
For now, we have proved that (*(s) D()), Therefore:
pkspp se) = arg min
max neighhor ne
Dmpp. me) / plss = arg maxmin V (P((s,,,,)) aEAA
neighbor ny of 8p
BEB
u(8p; 56)
arg max neighbor n, se
min neighbor of
Dmps ma) u(s) = arg min max V (P(,sa,,))
aEA
As there exists pure-strategy Nash equilibrium v"), ) it is directly guaranteed that (1, v) is Nash equilibrium.
A.2 Proof of Proposition 1
Proposition (Basic property of the shortest path distance feature). When the game is collision-fre with respect to the agents' node indexes, the input (sy, c) is sufficient reconstruct the global state with the current agent order 1. for sequential decision saciision-making.
Proof. Recall that the global state (Sp: 8e) =8p- (1)) up: ". P ve), where m is the number of pursuers.
Note that sy E R (mx+))xn contains the normalized shortest path distances of all = |V] nodes to all m + 1 agents. Since the distance is zero only when the agent is at the node, s (ks, v) = 0 implies = oh when k Σ m and implies v = when & m 1. Therefore, the global state (sp: 8e) can be reconstructed by checking the zeros 8y-
When the game is collision-free with respect to the agents' node indexes, there is at most one zero in each column of sy. Since is the index of the current pursuer agent, there must be exactly one zero in the e-th column. Let v. be the e-th node in the graph. Since sy (1, ve) = 0, the current agent order I also be obtained by checking the in the e-th column of 8y.
22

---

B Equilibrium Heuristic for PEGs with Exits
In no-exit graphs, the termination function f(sp, s.) 1 when a number of pursuers are adjacent to the evader. Since there is no termination condition about exits, the pursuers only care about how soon they can capture the evader, In graphs with exits, however, the pursuers lose when g(Sp, $e) 1. and a successful pursuit requires strict overlapping rather than adjacency (see [7].. Therefore, to block the exits around the evader more reasonable than to block all possible actions of the evader and capture it. For the evader, it is in turn reasonable to select an exit that cannot be blocked in time.
In the multi-exit scenario, single pursuer is enough block a single exit if it is at least as close as the evader with respect to the shortest path distance. Also, it is theoretically impossible for multiple pursuers block the exit if none of them is as close. since the evader can simply follow the shortest path towards the exit. Actually, if there exists one pursuer who can block the evader on its shortest path in time, it directly implies that the pursuer has a path to the exit no longer than the evader's, ss which contradicts the premise. Therefore, the cooperative behaviors among pursuers can be approximately abstracted as one-to-one exit allocation, which can be further formulated by bipartite graph matching.
With the above-mentioned considerations, we construct an equilibrium heuristic based on bipartite graph matching efficiently generate reasonable policies for both players in multi-exit PEGs. Given the current state of the game, the heuristic algorithm can be described by the following four steps:
Under the current state 8, construct a bipartite graph G2 = ((Vezit, Vpursuer), ). Ea). where the nodes in Vezit correspond to the exits in the PEG graph G and the nodes in V Vpursuer correspond to the pursuers. There is an edge c E E, between an exit and a pursuer and only if the pursuer's shortest path distance to the exit is not longer than the evader's. s. Intuitively, the existence of an exit-pursuer edge means that the pursuer can reach the exit no later than the evader and thus block the exit in time.
If a pursuer node has no related edges, which means it cannot block any exit, then it is removed from Gs, and this pursuer's current policy is to follow the shortest path towards the evader. If an exit node has related edges, which means it cannot be blocked by any pursuer, then it is also removed from G2, For the remaining exit nodes, sort them by their distance the evader in ascending order.
Compute the maximum l that guarantees the existence of a perfect matching in G. for the first k nodes {u,li - k} C Vezit- This can be simply fulfilled by running the O(m²) (m max [[Vezal) [Vpursuer]] })) Hungarian Algorithm for each & < [Venit). Intuitively, the existence of a perfect matching means that the closest & exits to the evader can be blocked simultancously.
For the pursuers involved in the perfect matching, their current policies are to follow the shortest path towards the matched exits. For any remaining pursuer indicated by v, the current policy is to follow the shortest path towards the exit with the minimum index i that satisfies (r., v) E Es. For the evader, at least one exit is removed from G., its current policy is to follow the shortest path to the closest removed exit. Otherwise, its current policy is to follow the shortest path to the closest exit that has not been occupied by any pursuer.
Note that the heuristic algorithm encourages the pursuers to increase the (lower-bound) steps for a worst-case evader to reach an exit. This can be viewed as approximating the equilibrium policy via minimax mechanism. Besides, since the heuristic evader can flexibly switch to a better exit when the game situation changes, it is also hard to exploit in practice.
Compared to the DP approach in no-exit scenarios, the heuristic approach can compute the current policy for each state independently. At the price of being more exploitable in certain handerafted cases, the heuristic policy can be directly computed during RL training, with a time complexity polynomial in the agent number for any current state. Since it avoids a preprocessing stage that traverses the state space, the heuristic approach also guarantees a better applicability of our EPG framework in multi-exit scenarios.
23

---

C Training Details
C.1
Implementation Details
For the training of Q functions, which not specified in Section 3.3 we employ the common technique of double target networks to avoid overestimations [13] When there are two three pursucrs, we simply use centralized value networks to directly represent Q functions. In the scenarios with more pursuers, the joint Q functions. As the pursuers are homogeneous agents, we have a direct decomposition Qs(s,a) Σi= Qo(s, 0;), where is the number of the pursuers.
value-decomposition networks (28] simple way decompose
In either the no-exit or multi-exit scenario, we use the same hyperparameter setting shown in Table throughout the EPG training for either pursuer or evader policy, Note that the target entropy in SAC [6] is defined in the form of log (1/ [A]] log A multiplied by predetermined coefficient.
Table Hyperparameter setting
discount factor y
0.99
embedding dimension d
128
number of attention heads
8
equilibrium guidance coefficient
0.1
pursuer target entropy coefficient
0.05
evader target entropy coefficient
0.1
batch size
128
learning rate
10 5
update epoch
C.2 Learning Curves
Besides the 2-pursuer case shown in the main paper, we have also verified the EPG framework in the 3-pursuer no-exit scenario using the exact equilibrium oracle from the DP approach (Algorithm I The learning curves of pursuer policy are shown in Figure 3
120
Traning Set Teeting Set
100
Termination Timestep
60
0
2500
5000
7500
10000
12500
15000
17500
20000
Episode
Figure 5: Pursuer learning curves in 3-pursuer no-exit PEGs
Figure provides the learning curves of pursuer policy when trained with the grouping-extended DP approach in the 6-pursuer scenario. Note that the difficulty of pursuit is not reduced when it comes to pursuers since a success pursuit requires 3 pursuers simultaneously adjacent to the evader. Also note that our RL policy eventually demonstrates better performance in the testing set than in the training set. This shows the strong zero-shot generalizability of our approach in the 6-pursuer scenario and also explains the strong performance of the RL pursuer in Table 5
Figure 7 shows the training process of the evaders in 2-pursuer and 6-pursuer scenarios, respectively. In contrast to pursuers, the evader aims to maximize the termination timesteps in no-exit scenarios.
24

---

120
Traninn Set
Teeting Set
100
Termination Timesiep
80
0
2500
5000
7500
10000 Episode
12500
15000
17500
20000
Figure 6: Pursuer learning curves in 6-pursuer no-exit PEGs
pursuers pursuaar
18
Termination Timestep
15
13
12
11
10
5000
10000
15000
20000
25000
30000
Episode
Figure 7: Evader learning curves in 2- 2-pursuer and 6-pursuer scenarios
Note that in practical implementation, the pursuer side receives positive reward of +30 when capturing the evader, which aligns with the hyperparameters in Table During training of the evader, reward of -0 is in turn received upon pursuit, which corresponds to the adversarial game setting.
C.3
Compute Resources and Time Costs
For no-exit graphs, EPG requires preprocessing the Nash value (or, equivalently, the array D DP algorithm) for each graph contained in the training set. Since our DP algorithm has near-optimal time complexity, for 2-pursuer 500-node graph, only takes around seconds to run Algorithm T without the last loop, using single 12th Gen Intel Core 17-12700F CPU. For multi-exit graphs, the matching-baad based heuristic algorithm is directly exccuted online and has no preprocessing requirement.
For the reinforcement learning process, Table 4 provides our recorded time for running 1000 EPG episodes, using two NVIDIA A100-SXM4-4000 GPUs. Intuitively, the training time grows sublin- early in the number of agents involved in the policy.
Table 4: Time requirement for 1000 EPG episodes
Game Scenario
Training Object
Time
2-pursuer no-exit PEG
2-pursuer policy
99 min
6-pursuer no-exit PEG
6-pursuer policy
180 min
2-pursuer no-exit PEG
evader policy
75 min
6- 6-pursuer no-exit PEG
evader policy
75 min
5-pursuer 8-exit PEG [17]
5 5-pursuer policy
159 min
25

---

D Experimental Details
D.1 Further Tests in Real-World Graphs
Figure provides the illustrations of the real-world graphs used in Section 4.1
Figure 8: Illustrations of Scotland- Yard Map, Downtown Map, and 7 famous real-world locations (following the order in Tables aannd
Table 5: Performance of RL pursuer / evader against DP oracle in no-exit PEGs with pursuers
Pursuit Success Rate
Evasion Timestep f
Graph Structure
DP DP
RL
DP
SPS
DP
DP DP
DP RL
Grid Map
1.00
1.00
1.00
7.73 + 2.75
6.28 2.57
Scotland Yard Map
1.00
0.98
0.00
10.28 3.70
7.60 + 2.77
Downtown Map
1.00
0.98
0.01
10.44 = 3.37
7.77 + 2.83
Times Square
1.00
0.99
0.01
18.06 6.67
14.54 4.84
Hollywood Walk of Fame
1.00
0.95
0.00
34.90 + 16.32
24.15 + 10.20
Sagrada Familia
1.00
0.96
0.00
27.11 + 11.77
19.11 + 5.90
The Bund
1.00
0.91
0.02
32.14 1 16.98
22.01 7.95
Eiffel Tower
1.00
0.99
0.21
26.15 = 9.29
20.96 + 7.70
Big Ben
1.00
0.96
0.00
32.61 + 14.09
24.45 9.77
Sydney Opera House
1.00
0.85
0.00
33.23 + 13.56
24.60 10.88
Table 5 presents the results of our further tests in the 6-pursuer no-exit PEGs under the real-world graphs. As is shown in the table, the pursuit is still guaranteed by the grouped DP policy. This is reasonable because every sub-team of pursuers guarantees the eventual adjacency for half of the pursuers (i.e., one pursuer). Besides, our MARL pursuer exhibits high rate of success against the DP-based evader under the grouping mechanism.
The shortest path strategy (SPS), however, has very low success rates against the DP-based evader in the real-world graphs. This reflects the strength of our DP policies under grouping extension that trades off the optimality. Besides, our RL evader maintains a stable performance against the DP pursuer, with acceptable decline of evasion steps as the 2-pursuer case.
D.2
Test Details
As stated Section our zero-shot testing graphs are differentiated from the 152 Dungeon training graphs: Section 4.1 (Table T uses 10 unseen real-world graph structures. Section 4.2 (Figure 3 uses 10 unseen Dungeon graphs. Section 4.3 (Figure D uses the 10 unseen Dungeon graphs (left, zero-shot evaluations during training), Grid Map (mid), and Scotland- Yard Map (right).
26

---

For the tests in no-exit PEGs, the initial positions for the agents in the testing graphs are randomly generated under the restriction that the shortest path distance between the pursuers and the evader is greater than 5. This restriction serves to rule out certain easy pursuits.
For multi-exit PEGs, randomly generated 1000 initial positions for the exits and agents, strictly following the descriptions and code from Grasper [17] for Grid Map and Scotland- Yard Map. For example, the minimum length of the evader's shortest path to any exit is 5 for the brotland-Yard Map. While [77 claims that they rule out the trivial cases that are either too difficult or too simple, the specific restrictions on the initial conditions are related their method and hard to replicate. Therefore, we simply rule out the cases where it is clearly impossible for the pursuers or the evader win. For the evader, we require that its distance the closest exit be no greater than 10 (the time horizon of the game). For the pursuers, we require that, for any exit that the evader can reach in 10 steps, there is at least one pursuer who is closer than or as close as the evader with respect to the shortest path distance towards the exit.
6 for the Grid Map and
All of the tests for the zero-shot performance of our RL policies are conducted after 30000 EPG episodes (each with at most 128 transitions) within the training set that contains a total of 152 graphs.
D.3 Pursuit and Evasion Examples No-Exit Graphs
Figures and 10 a PEG example in the 2-pursuer no-exit scenario illustrate how our RL policy succeeds in capturing the DP evader while SPS is stuck in a loop (from step 9 to step 29) under the same initial condition. The graph is abstracted from procedurally generated Dungeon map unseen during the training process. The circles represent the pursuers, and the square represents the evader.
Figure 9: Successful pursuit against DP evader by RL pursuers
Figure 10: Failed pursuit against DP evader by shortest path strategy
27

---

Figure I1 shows aursuit-vvssion example between 6 grouped DP pursuers and the RL evader trained through EPG. The number of pursuers the same node explicitly shown on the circle when is more than one. While surrounded by the pursuers, the RI. evader seeks to maximize the timesteps before being captured by 3 adjacent pursuers (i.e., half of the pursuers).
Figure 11: DP pursuers versus RI. evader in 6-pursuer no-exit graph
Figure 12 shows how the RL evader manages to evade SPS pursuers just like the DP evader. Although the evader policy does train against SPS, it manages find how create a loop that can make similar pursuer strategies fail. The emergence of such behaviors could also reflect the generalization capability of our EPG framework.
+
Figure 12: Shortest path strategy versus RL evader in 6-pursuer no-exit graph
28

---

D.4 Pursuit Examples in Multi-Exit Graphs
While the time horizon for no-exit PEGs is 128, is only set to 10 in multi-exit PEGs to align with [7]. Therefore, we show more pursuit examples in graphs with exits from the Dungeon environment. Figures [3] 14 and [3 provide three examples show the sero performance of our 5-pursuer policy trained through EPG with equilibrium heuristic. The light stars represent the 8 exits.
Figure 13: Pursuit example one in 5-pursuer 8-exit graph
Figure 14: Pursuit example two in 5-pursuer 8-exit graph
2
E
E3
E
E
Figure 15: Pursuit example three in 5-pursuer 8-exit graph
Intuitively, in the first example, the two pursuers on the right manage to block the two exits in time. In the second example, the four pursuers near the evader manage surround it from all directions. In the third example. the yellow pursuer guards one nearby exit, while the red pursuer and the purple pursuer cooperate guard the other exit close to the evader.
29

---

E Can Zero-Shot RL Pursuers Outperform DP?
While our previous results demonstrate the optimality of the DP policies, which maintain the pursuit success rate of I whenever possible, the mixed-strategy RL pursuers trained through EPG can actually outperform the pure-strategy DP pursuers when the pursuit not globally guaranteed. We use the no-exit PEG results under two other real-world graph structures to show this.
E.1 Results in Scale-Free Graph
Figure 16: Illustration of Scale-Free Graph
Figure provides an illustration of Scale-Free Graph, which is generated using Garabási-Albeen preferential attachment (I) With maximum degree of 21 and diameter of 11, Scale-Free Graph has very strong connectivity that can make evasion easier. As the pursuit not guaranteed for pursuers this graph, we find that the DP pursuer policy only has a success rate of 0.1 against the DP evader. With a success rate of 0.44, our RL policy clearly outperforms DP under this graph.
E.2 Results under Singapore Graph and Success Condition Shift
Figure 17: Illustration of Singapore Graph
Figure 17 provides an illustration of Singapore Graph, which is high-level abstraction for the map of Singapore. With maximum degree of 13 and diameter of 41, the connectivity of the Singapore Graph is not good as that of the Scale-Free Graph. While the pursuit is guaranteed for 2 pursuers under success condition that one pursuer is adjacent
no longer guaranteed when evader,
we strengthen the condition to be both pursuers. In this case, the success rate of DP drops from 1 to 0.04, while the success rate RL drops from 0.78 to 0.49. This comparative result suggests that the RL policy trained through our EPG framework could be robust against certain shifts of game rules.
30

---

Actually, we have further verified such robustness of our RL policy in the testing graphs that we used the main paper. compares the percentages successful pursuit maintained by DP and RL pursuers after strengthening the success condition under the 10 graph structures. Compared with the DP pursuer, the RI. pursuer demonstrates clear advantage of robustness, with the maintenance rates over 60% (under 1000 tests for each graph) in 9 out of the 10 graphs.
Table 6: Percentages of successful pursuit maintained after success condition shift
Graph Structure
DP pursuer
RL pursuer
Grid Map
28.9%
90.6%
Scotland- Yard Map
27.9%
90.4%
Downtown Map
17.0%
84.6%
Times Square, New York
20.7%
68.4%
Hollywood Walk of Fame, LA
4.7%
93.6%
Sagrada Familia, Barcelona
1.7%
78.1%
The Bund, Shanghai
2.0%
65.9%
Fiffel Tower, Paris
9.1%
40.3%
Big Ben, London
6.3%
66.1%
Sydney Opera House, Sydney
8.6%
79.5%
F Additional Evaluations
F.1
Performance under Large-Scale Graphs
Here conduct additional experiments to further show that trained policy can directly generalize to large-scale graphs. We increase both map range and discretization accuracy to derive significantly larger graphs for the eight real-world locations in Table [ Specifically, the larger graphs generated by doubling the discretization accuracy and increasing the map range. For Sydney Opera House, we actually double the map range to create graph with at least 1000 nodes.
Table 7: Performance comparison across different maps at original and large scales
Original Scale
Large Scale
Location
Node Number
Success Rate
Node Number
Success Rate
Downtown Map
206
0.99
907
0.99
Times Square
171
0.98
768
0.89
Hollywood Walk of Fame
201
0.62
892
0.71
Sagrada Familia
231
0.66
899
0.57
The Bund
200
0.60
952
0.54
Eiffel Tower
202
0.97
616
0.82
Big Ben
192
0.91
675
0.78
Sydney Opera House
183
0.74
1074
0.83
The success rates of two RI. pursuers against the DP evader under the original graphs and the large graphs are compared Table 7 While the node number increases significantly, the pursuit success rates do not suffer from significant decline under large-scale graphs. In scenarios like Hollywood Walk of Fame and Sydney Opera House, they are even higher because of the structural changes.
Note that we do not fine-tune tune our policy on the larger graphs. We only adjust the termination function keep the difficulty of the real-world pursuit task under the new graphs close the original one. Specifically, one pursuer succeeds when its distance to the evader is no greater than 1 on the original graph and when the distance is no greater than 2 on the larger graph. Since the discretization accuracy doubles, the two conditions correspond to roughly the same real-world pursuit condition despite some local structural changes. Under the new graphs with the new success condition, we rerun the DP algorithm (Algorithm to generate the optimized policies correspondingly.
31

---

F.2 Performance against PSRO Policies
Besides DP, we also test the results of our EPG pursuer and evader policies against the PSRO [6 policies directly trained on the testing graphs. As is shown in Table 8 our EPG policies guarantee to capture the PSRO evader and survive significantly longer against the PSRO pursuers (except for Grid Map). This further verifies the benefit of using EPG for cross-graph zero-shot generalization.
Table 8: Performance comparison between EPG and PSRO policies
Termination Timestep [Success Rate] EPG, PSRO,
Graph Structure
PSRO, EPG
Grid Map
14.04 + 6.88 1.00
11.87 + 2.39
1.000
Scotland- Yard Map
17.45 = 9.17
1.00
25.48
16.80
[1.00]
Downtown Map
14.14 + 7.37
1.00
38.39
30.50
0.97
Times Square, New York
17.72 = 7.86
1.00
37.87 - 29.94
00.97
Hollywood Walk of Fame, LA
30.93 17.67
1.00
60.71
39.21
0.86
Sagrada Familia, Barcelona
26.06 + 12.43
[1.00]
39.50 + 28.25
0..97
The Bund, Shanghai
24.76 + 13.01
11.00
34.97 + 24.75
0.99
Biffel Tower, Paris
19.10 10.69
[1.00]
25.24 + 14.07
[1.0
Big Ben, London
23.70 = 13.00
1.00
53.67 = 36.41
0.90
Sydney Opera House, Sydney
26.14 12.81 [1.00]
67.23 + 43.37
[0.77]
G Broader Impacts
As this work presents a general framework that leads to robust RL pursuer or evader policies with desirable zero-shot performance across different real-world graphs, it can be directly applied to real-world PEG solving under varying graph structures. The EPG framework in principle allows for an arbitrary amount of pursuers, exits, and graph nodes and thus guarantees applicability to diverse PEG settings in the real world. Since the inference time negligible under GPUs, the trained policy model guarantees real-time applicability even when the graph structure dynamically changes, only need to recompute the shortest path distances as inputs.
From a security perspective, through our approach, pursuit policy under urban streets can be readily generated for any traffic conditions that may lead to quite different graph connectivity. When trained under more diverse set of graphs and larger scale of parameters, "large" policy model for general security purposes can be obtained. Such a model can save huge amount of computation for solving different real-world PEGs. For example, while it can take hours to compute equilibrium policies in 500-node no-exit graphs with 3 pursuers through Algorithm this time consumption is only required during preprocessing and training through EPG rather than during execution.
Also, our trained models can efficiently generate reasonable pursuit and evasion examples that may relate to real-world pursuit and evasion behaviors. This could help people better understand and predict the motivations of both the pursuers and the evader. Besides, due to its generality, the EPG training pipeline can also be extended for robust policy learning in other adversarial game domains. The idea constructing equilibrium adversaries through preprocessed or preconstructed (accurate or approximate) oracles could have further impacts on subsequent reinforcement learning research.
32


Reviews:
[{"review_id": "QPE9QC1xlu", "reviewer": "Reviewer_BGj6", "summary": "This paper proposes the Equilibrium Policy Generalization (EPG) framework for pursuit-evasion games (PEGs), aiming to enable zero-shot generalization across graph structures. The core idea is to train reinforcement learning (RL) policies against equilibrium strategies of individual graphs using dynamic programming (DP) and a grouping mechanism for scalability. The authors claim that EPG outperforms state-of-the-art methods in zero-shot performance, supported by experiments on real-world graphs. While the framework shows promise, several critical limitations and theoretical gaps warrant discussion.", "questions": "See Weakness.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**  \nThe work addresses a critical gap in real-world PEG applications: existing methods struggle with dynamic graph changes and require extensive fine-tuning, limiting real-time applicability. EPG’s focus on zero-shot generalization via equilibrium guidance is innovative and practical.  \n\n **Weaknesses**  \n- The method requires pre-solving Nash equilibria for all training graphs, which is computationally intractable for large-scale scenarios. This limits applicability to real-world problems with dynamic or large graphs.  \n\n- The use of KL divergence between the current policy and precomputed equilibria as a loss raises a fundamental question: If the goal is to mimic equilibrium strategies, why not use direct supervised learning instead of RL? The paper lacks a clear justification for combining RL with equilibrium guidance over pure supervised training, which would be more efficient if equilibria are known.  \n\n- The training paradigm assumes that optimizing against Nash equilibria yields robust policies, but this is theoretically unsound. In zero-sum games, Nash equilibria are optimal against any strategy, but training an RL agent against an equilibrium does not guarantee the agent will converge to a NE. For instance, in rock-paper-scissors (a simple 3x3 game), RL training against this NE without constraints could yield arbitrary policies (e.g., a pure strategy).  \n\n - The evaluation focuses on performance against precomputed NE, but the standard security metric for policies is *exploitability* (i.e., the maximum gain an opponent can achieve by best-responding to the policy). Failing to report exploitability results leaves uncertainty about whether EPG policies are truly robust or merely performant against a fixed NE.  \n - The framework is evaluated in simplified scenarios , lacking scalability tests on large-scale graphs or complex real-world environments.", "was_revised": true, "final_justification": "The authors have addressed all my concerns, thus I raise my score from 3 to 4.", "rebuttal": "Dear reviewer,\n\nThank you very much for reviewing our paper. We definitely agree that it is important to clearly discuss the points in the weaknesses section. Here we provide our justifications and additional experiment results.\n\n**Point 1**\n\n> The method requires pre-solving Nash equilibria for all training graphs, which is computationally intractable for large-scale scenarios. This limits applicability to real-world problems with dynamic or large graphs.\n\nThanks for the question about the real-world applicability of our method. In Line 158, we mention that directly solving PEGs requires time exponential in the agent number. Nevertheless, when the pursuer number is no more than 3, the time complexity of our DP algorithms is at most $\\tilde{O}(|V|^4)$. Using CUDA acceleration, the computation for a 3-pursuer 500-node graph can be completed in several minutes. Also, EPG does not rely on the exact computation of Nash equilibrium. When the pursuer number is more than 3, our grouping extension decomposes the problem to the cases with 2 or 3 pursuers, guaranteeing the same time complexity and a desirable performance (Table 4). For multi-exit cases, we actually employ a very fast heuristic algorithm in place of exact equilibrium oracles while achieving the best results (Figure 4). Our additional experiments in response to the weakness on scalability (Point 5) further show that policies trained under relatively small graphs can generalize to large-scale scenarios through EPG. This could further reduce the need of pre-solving Nash equilibrium for the graphs with a large scale.\n\n**Point 2**\n\n> The use of KL divergence between the current policy and precomputed equilibria as a loss raises a fundamental question: If the goal is to mimic equilibrium strategies, why not use direct supervised learning instead of RL? The paper lacks a clear justification for combining RL with equilibrium guidance over pure supervised training, which would be more efficient if equilibria are known.\n\nThanks for the question on supervised learning. In the experiments, we have tried mere supervised learning and found that it is consistently outperformed by RL with equilibrium guidance. In Section 4.2, we compare RL with mere supervised learning (blue lines in Figure 3), which suffers from a clear performance drop in no-exit scenarios. In Figure 4 (left), we show that mere supervised learning (green line) simply fails to generalize in multi-exit scenarios. Besides, even without equilibrium guidance, RL can still find good policies eventually (orange lines in Figure 3). These results suggest that RL is a better choice for cross-graph policy generalization than simply mimicking equilibrium strategies. Existing research in domains like LLMs [1] also suggests that RL has significantly better generalization capability than SL.\n\n**Point 3**\n\n> The training paradigm assumes that optimizing against Nash equilibria yields robust policies, but this is theoretically unsound. In zero-sum games, Nash equilibria are optimal against any strategy, but training an RL agent against an equilibrium does not guarantee the agent will converge to a NE. For instance, in rock-paper-scissors (a simple 3x3 game), RL training against this NE without constraints could yield arbitrary policies (e.g., a pure strategy).\n\nThank you for providing this theoretical insight. We definitely agree that simply optimizing against equilibrium does not guarantee robust policies in a game. However, our approach has multiple differences: First, we establish EPG upon an entropy-regularized RL algorithm, SAC, which applies an indirect policy constraint that discourages pure strategies. For an RPS game, the policy regularization actually encourages the convergence to the NE $(1/3,1/3,1/3)$. Second, the robustness of EPG policies is assumed to benefit from training against the policies that are hard to exploit **across a diverse set of graphs**. This is quite different from learning against NE in single dynamics. While the preprocessed equilibrium adversaries can be generated by the same algorithm, they are essentially different policies under different dynamics. Therefore, EPG allows the generalized policy to train with a diverse set of opponents while avoiding overly exploiting certain behavior patterns. This eventually leads to a robust high-level policy across graphs. Third, the equilibrium guidance further facilitates efficient exploration and keeps the single-graph behavior of the generalized policy close to NE. From our understanding, these elements will compound to make the learned policy itself hard to exploit.\n\n**Point 4**\n\n> The evaluation focuses on performance against precomputed NE, but the standard security metric for policies is exploitability (i.e., the maximum gain an opponent can achieve by best-responding to the policy). Failing to report exploitability results leaves uncertainty about whether EPG policies are truly robust or merely performant against a fixed NE.\n\nThank you for mentioning the exploitability of EPG policies. In our experiments for multi-exit scenarios in Figure 4 (mid & right), we report the utility against the worst-case opponent (higher value meaning lower exploitability) and compare with the state of the art under the same metric. The worst-case utility of the pursuer policies in the multi-exit tests can be exactly computed because the policy space of the evader is restricted to align with Grapser [2] (i.e., choosing an exit and following the shortest path to it). When there is no reasonable way to simplify the opponent (e.g., in no-exit scenarios), computing an exact best response can be intractable. In our experiments for no-exit scenarios, we use the DP policies as a substitute since they are near-optimal and, at the same time, effectively punish the policies that are not optimal. Actually, we have also approximated the best responses to EPG policies through reinforcement learning on the testing graphs. The approximate best-response (BR) policies are generally hard to train (since EPG policies are fairly strong) and not better at exploiting our policies in comparison with DP:\n\n| Map/Location | \\| | Pursuit Success Rate | | \\| | Evasion Timestep | |\n|---|---|---|---|---|---|---|\n| | \\| | RL[p] vs DP[e] | RL[p] vs BR[e] | \\| | DP[p] vs RL[e] | BR[p] vs RL[e] |\n| Grid Map | \\| | 1.00 | 1.00 | \\| | 11.88 ± 2.39 | 11.67 ± 2.60 |\n| Scotland-Yard Map | \\| | 0.99 | 1.00 | \\| | 12.57 ± 2.96 | 13.12 ± 3.65 |\n| Downtown Map | \\| | 0.99 | 0.99 | \\| | 11.83 ± 3.12 | 13.81 ± 5.83 |\n| Times Square, New York | \\| | 0.98 | 0.95 | \\| | 14.68 ± 3.11 | 16.20 ± 5.16 |\n| Hollywood Walk of Fame, LA | \\| | 0.62 | 0.67 | \\| | 20.00 ± 4.99 | 20.22 ± 9.60 |\n| Sagrada Familia, Barcelona | \\| | 0.66 | 0.76 | \\| | 17.89 ± 4.59 | 18.83 ± 6.30 |\n| The Bund, Shanghai | \\| | 0.60 | 0.56 | \\| | 20.59 ± 5.59 | 21.91 ± 10.58 |\n| Eiffel Tower, Paris | \\| | 0.97 | 0.98 | \\| | 18.47 ± 6.12 | 19.28 ± 10.48 |\n| Big Ben, London | \\| | 0.91 | 0.94 | \\| | 21.58 ± 6.38 | 23.07 ± 12.91 |\n| Sydney Opera House, Sydney | \\| | 0.74 | 0.80 | \\| | 22.37 ± 6.16 | 25.78 ± 16.79 |\n\n**Point 5**\n\n> The framework is evaluated in simplified scenarios, lacking scalability tests on large-scale graphs or complex real-world environments.\n\nThanks for the comment on scalability. In our training set that contains $152$ graphs, the maximum node number is $295$, and the average node number is $152.24$. Currently, we have conducted additional experiments to further show that our trained policy can directly generalize to large-scale graphs. We increase both map range and discretization accuracy and derive significantly larger graphs for the real-world locations in Table 1. The pursuit success rates for $\\mathrm{RL_{p}-DP}$ under the original graphs and the large graphs are shown as follows:\n\n| Map/Location | \\| | Original Scale | | | \\| | Large Scale | | |\n|---|---|---|---|---|---|---|---|---|\n| | \\| | Node Number | \\| | Success Rate | \\| | Node Number | \\| | Success Rate |\n| Downtown Map | \\| | 206 | \\| | 0.99 | \\| | 907 | \\| | 0.99 |\n| Times Square, New York | \\| | 171 | \\| | 0.98 | \\| | 768 | \\| | 0.89 |\n| Hollywood Walk of Fame, LA | \\| | 201 | \\| | 0.62 | \\| | 892 | \\| | 0.71 |\n| Sagrada Familia, Barcelona | \\| | 231 | \\| | 0.66 | \\| | 899 | \\| | 0.57 |\n| The Bund, Shanghai | \\| | 200 | \\| | 0.6 | \\| | 952 | \\| | 0.54 |\n| Eiffel Tower, Paris | \\| | 202 | \\| | 0.97 | \\| | 616 | \\| | 0.82 |\n| Big Ben, London | \\| | 192 | \\| | 0.91 | \\| | 675 | \\| | 0.78 |\n| Sydney Opera House, Sydney | \\| | 183 | \\| | 0.74 | \\| | 1074 | \\| | 0.83 |\n\nAs is shown in the table, the success rates do not suffer from a significant decline under large-scale graphs. In scenarios like Hollywood Walk of Fame and Sydney Opera House, the success rates are even higher because of the structural changes.\n\nThank you again for providing the insightful comments. We hope our response properly addresses your concerns. We are looking forward to having further discussions with you.\n\n**References**\n\n[1] Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoc V. Le, Sergey Levine, and Yi Ma. SFT memorizes, RL generalizes: A comparative study of foundation model post-training. In Forty-second International Conference on Machine Learning, 2025.\n\n[2] Pengdeng Li, Shuxin Li, Xinrun Wang, Jakub Cerny, Youzhi Zhang, Stephen McAleer, Hau Chan, and Bo An. Grasper: A generalist pursuer for pursuit-evasion problems. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 1147–1155, 2024."}, {"review_id": "D8ureG9a1f", "reviewer": "Reviewer_dxFV", "summary": "This paper introduces the Equilibrium Policy Generalization (EPG) framework, a reinforcement learning method aimed at achieving robust zero-shot generalization for pursuit-evasion games (PEGs) across varying graph structures. The authors present a novel approach wherein reinforcement learning is guided by equilibrium policies obtained through dynamic programming (DP) or heuristic approximation. Specifically, an efficient DP algorithm is designed to find pure-strategy Nash equilibria for no-exit PEGs, and a heuristic based on bipartite matching is proposed for multi-exit scenarios. Experimental results demonstrate strong zero-shot performance and detailed ablation studies are provided to validate various components of the proposed method.", "questions": "- Have you tried using Graph Neural Networks (GNNs) to model the scenarios? If yes, how do they compare to your proposed sequence model with shortest path features? If no, can you clarify why such an approach was not considered?\n\n- Why is the proposed approach limited specifically to pursuit-evasion games (PEGs)? It appears that the basic idea could also be applicable to more general two-player adversarial games (for example, two-player Texas Hold'em poker or simplified board games). Could you clarify the reasons behind focusing exclusively on PEGs?\n\n- Could you further discuss the scalability of your equilibrium oracle methods (DP and heuristic)? Specifically, how realistic would it be to apply these methods to larger-scale games, and what practical considerations or limitations would arise?", "limitations": "see weaknesses", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n \n- The paper is well-organized, and the figures clearly illustrate the proposed ideas and framework.\n- The core idea is intuitive and the motivation for equilibrium-guided reinforcement learning is well explained.\n- The experiments and ablation studies are thorough and insightful, providing solid empirical evidence supporting the method’s effectiveness.\n\nWeaknesses\n \n\n- The proposed framework critically depends on the availability of an equilibrium opponent policy, which could be a strong assumption. Although the paper discusses two approaches (DP and heuristic) for constructing such equilibrium oracles, these solutions might be difficult to transfer to larger-scale or more general game scenarios, such as Atari environments or complex board/card games (e.g., chess).\n\n- In essence, the method leverages a model-based or expert prior (guidance opponent), and thus the innovation from a purely RL-algorithm perspective is somewhat limited. Other RL methods such as PSRO, SAC, or even simple Q-learning could similarly benefit from having such a guidance opponent. Therefore, the comparisons presented in Figure 4 may not be entirely fair or balanced.\n\n- The claimed zero-shot generalization capability is demonstrated primarily in scenarios with relatively modest variations. Even conventional RL methods, provided with a sufficiently large graph corpus (e.g., > 100 graphs), may achieve reasonable generalization. It would have been more convincing if the proposed approach could generalize beyond graph-based games.", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you very much for reviewing our paper and providing the insightful comments. Here we provide a response to the weaknesses section and your questions.\n\n**Weakness 1**\n\n> The proposed framework critically depends on the availability of an equilibrium opponent policy, which could be a strong assumption. Although the paper discusses two approaches (DP and heuristic) for constructing such equilibrium oracles, these solutions might be difficult to transfer to larger-scale or more general game scenarios, such as Atari environments or complex board/card games (e.g., chess).\n\nThank you for mentioning the transferability of our method. Actually, the EPG framework does not rely on an exact equilibrium oracle for good performance. In the multi-exit case, we only construct a heuristic that is intuitive and very fast to compute while still achieving current best results. The basic requirements of EPG are only twofold: First, the training corpus is diverse enough. Second, the opponents cannot be easily exploited. In principle, EPG is applicable to any other game scenarios through the use of general and approximate oracles like PSRO [1].\n\n**Weakness 2**\n\n> In essence, the method leverages a model-based or expert prior (guidance opponent), and thus the innovation from a purely RL-algorithm perspective is somewhat limited. Other RL methods such as PSRO, SAC, or even simple Q-learning could similarly benefit from having such a guidance opponent. Therefore, the comparisons presented in Figure 4 may not be entirely fair or balanced.\n\nThank you for the comment on the innovation. Robust policy generalization in adversarial games requires considerations from a game-theoretic perspective. Simply optimizing against equilibrium opponents does not guarantee robust policies, which is also mentioned by Reviewer BGj6. As is clarified in our response to this point, EPG benefits from the compounding effect of SAC loss, cross-graph training, and equilibrium guidance. Essentially, EPG combines two complementary components, cross-graph/dynamics training and equilibrium adversary, each of which is not guaranteed to work individually. The robustness of EPG policies is assumed to benefit from training against the policies that are hard to exploit across a diverse set of graphs. This is quite different from learning against certain guidance policies in single dynamics. EPG essentially allows the generalized policy to train with a diverse set of opponents while avoiding overly exploiting certain behavior patterns. This eventually leads to a robust high-level policy across graphs.\n\n**Weakness 3**\n\n> The claimed zero-shot generalization capability is demonstrated primarily in scenarios with relatively modest variations. Even conventional RL methods, provided with a sufficiently large graph corpus (e.g., > 100 graphs), may achieve reasonable generalization. It would have been more convincing if the proposed approach could generalize beyond graph-based games.\n\nThank you for the insight on zero-shot generalization. Here we should emphasize that policy generalization in multi-agent adversarial games like PEGs is more difficult than in single-agent cases. Recent work [2] mentions that even the state-of-the-art PEG methods (including Grasper [3], which already pretrains the policy in a set containing $1,000$ PEGs) struggle to adapt to rapid dynamic changes and do not guarantee cross-graph zero-shot performance. Our paper shows that robust cross-graph generalization requires proper adversaries (e.g., equilibrium policy) and high-level features (e.g., shortest path distance feature). Besides, the principle of sequential decision-making can give rise to a sequence model that maintains in-team cooperation during policy generalization. These findings may guide subsequent algorithm designs aimed at robust policy generalization in the broader domain of game RL.\n\n**Question 1**\n\n> Have you tried using Graph Neural Networks (GNNs) to model the scenarios? If yes, how do they compare to your proposed sequence model with shortest path features? If no, can you clarify why such an approach was not considered?\n\nThanks for the question. Actually, the policy network part (on the right of Figure 2) of our sequence model is itself in the form of a graph neural network. The masked self-attention in the encoder has the same function as the aggregation layers in common GNNs. Furthermore, we use a novel shortest path distance feature as the initial node feature and embed the GNN into a multi-agent framework to form the sequence model. Without a GNN architecture, it would be difficult to encode the game states in graph-based PEGs.\n\n**Question 2**\n\n> Why is the proposed approach limited specifically to pursuit-evasion games (PEGs)? It appears that the basic idea could also be applicable to more general two-player adversarial games (for example, two-player Texas Hold'em poker or simplified board games). Could you clarify the reasons behind focusing exclusively on PEGs?\n\nYes, the EPG framework can definitely be applied to other adversarial game settings. We focus on PEGs because they are quite important in real-world security but theoretically very hard to solve (EXPTIME-complete). Our proposed DP algorithm and grouping extension contribute to improving the scalability of existing methods with respect to both node number and agent number, while maintaining the theoretical foundation (Theorem 1). For more game types, general algorithms like PSRO can directly serve as equilibrium oracles in place of DP. However, applying them in PEGs does not guarantee the good performance of our approach since the game involves both cooperation among pursuers and competition between two teams.\n\n**Question 3**\n\n> Could you further discuss the scalability of your equilibrium oracle methods (DP and heuristic)? Specifically, how realistic would it be to apply these methods to larger-scale games, and what practical considerations or limitations would arise?\n\nThanks for the question, and here we provide a further discussion. For the DP algorithm, our grouping extension guarantees its scalability with respect to agent number. When the node number is extremely large (e.g., 10000), we clearly need to function-approximate the $D(\\cdot)$ table, which serves to construct the exact equilibrium oracle. For the heuristic algorithm, it is itself an approximate oracle and runs efficiently even in very large PEGs. Whether to use exact oracles like DP or approximate oracles like heuristic and PSRO in larger-scale games depends on the actual demand. If the game requires to be accurately solved, then the DP approach is a better choice. Besides, our additional experiments show that EPG trained under relatively small graphs can generalize well to larger-scale scenarios. This further enhances the applicability of DP in larger-scale games, as it is sufficient to use DP to presolve the games with moderate scales for training a policy that performs well in large scales.\n\n**Additional experiments**\n\nWe increase both map range and discretization accuracy and derive significantly larger graphs for the real-world locations in Table 1. The pursuit success rate of $\\mathrm{RL_{p}-DP}$ under the original graphs and the large graphs are shown as follows:\n\n| Map/Location | \\| | Original Scale | | | \\| | Large Scale | | |\n|---|---|---|---|---|---|---|---|---|\n| | \\| | Node Number | \\| | Success Rate | \\| | Node Number | \\| | Success Rate |\n| Downtown Map | \\| | 206 | \\| | 0.99 | \\| | 907 | \\| | 0.99 |\n| Times Square, New York | \\| | 171 | \\| | 0.98 | \\| | 768 | \\| | 0.89 |\n| Hollywood Walk of Fame, LA | \\| | 201 | \\| | 0.62 | \\| | 892 | \\| | 0.71 |\n| Sagrada Familia, Barcelona | \\| | 231 | \\| | 0.66 | \\| | 899 | \\| | 0.57 |\n| The Bund, Shanghai | \\| | 200 | \\| | 0.6 | \\| | 952 | \\| | 0.54 |\n| Eiffel Tower, Paris | \\| | 202 | \\| | 0.97 | \\| | 616 | \\| | 0.82 |\n| Big Ben, London | \\| | 192 | \\| | 0.91 | \\| | 675 | \\| | 0.78 |\n| Sydney Opera House, Sydney | \\| | 183 | \\| | 0.74 | \\| | 1074 | \\| | 0.83 |\n\nAs is shown in the table, the success rates do not suffer from a significant decline under large-scale graphs. In scenarios like Hollywood Walk of Fame and Sydney Opera House, the success rates are even higher because of the structural changes.\n\nThank you again for the insightful comments. We hope our response properly addresses your concerns. We are looking forward to having further discussions with you.\n\n**References**\n\n[1] Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.\n\n[2] Shuxin Zhuang, Shuxin Li, Tianji Yang, Muheng Li, Xianjie Shi, Bo An, and Youzhi Zhang. Solving urban network security games: Learning platform, benchmark, and challenge for AI research. arXiv preprint arXiv:2501.17559, 2025.\n\n[3] Pengdeng Li, Shuxin Li, Xinrun Wang, Jakub Cerny, Youzhi Zhang, Stephen McAleer, Hau Chan, and Bo An. Grasper: A generalist pursuer for pursuit-evasion problems. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 1147–1155, 2024."}, {"review_id": "Hm76ErZtBF", "reviewer": "Reviewer_m6zW", "summary": "This work describes a framework to generally solve pursuit-evasion graph games. These are games where pursuer and evader agents exist on a graph and the pursuers must catch the evaders in a zero-sum setting. The authors propose an equilibrium policy generation method to learn generalized policies than can work zero-shot on unseen graph structures. They train RL agents against oracle policies which are discovered using dynamic programming. \n\nMy current rating is borderline reject. I would be willing to increase this score is better statistical data is provided, and if the paper is updated with a proper comparison of EPG in the no-exit scenarios against appropriate baselines, or if at least a good justification is provided for not comparing against them.", "questions": "1. Why are there no deviation data provided for the data in Table 1? additionally, what do the error bars in Figure 3 represent? There is a huge difference in the significance of standard error, standard deviation, and confidence intervals.\n2. Why are the testing generalization plots in Figure 4 plotted over time in seconds? Why not flops, or timesteps? This would make for a computationally fair comparison.", "limitations": "See above", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The use of RL in this problem is well-motivated, as existing methods for PEGs are computationally intensive to fine-tune, and are not guaranteed to generalize across different graph structures.\n2. The construction of oracle policies for training using DP is well-explained: the authors walk through a logical progression of the near-optimality of their DP approach with no-exit graphs, then an extension to exits, and then an extension to many pursuers. I have not rigorously checked the proof of Theorem 1.\n3. The use of an attention mechanism to encode the observations of changing graph structures is well explained.\n4. The experiments evince good results for EPG with the proposed training scheme and policy loss and distance features.\n\nWeaknesses:\n1.  Definition of the NE on pg 3 should include 'at all states'. Also, a Markov game must be finite to guarantee the existence of a NE. Suitable citations should also be provided for the Nash value and the 2 last claims in the NE paragraph.\n2. The experiments are unfortunately a bit lacking as the authors only present ablations of their own method and comparisons to the DP solution. While the use of RL was well-motivated as other PEG solving algorithms would be difficult to generalize, it still would be useful to see if a naive implementation of PSRO in no-exit PEGs. \n3. As the authors mention in the conclusion, a test with partial observability would also greatly improve the viability of this method, since this is a typical assumption in MARL. Since the observation encodings use an attention mechanism, it should not be too difficult to implement this.", "was_revised": true, "final_justification": "Additional experiments, improved statistical data, references, and a better proof in the main body of the work have convinced me that the work is in an acceptable state to be recommended for acceptance.", "rebuttal": "Dear reviewer,\n\nThank you very much for reviewing our paper and providing the detailed comments. Here is our response to the weak points as well as your questions.\n\n**Weakness 1**\n\n> Definition of the NE on pg 3 should include 'at all states'. Also, a Markov game must be finite to guarantee the existence of a NE. Suitable citations should also be provided for the Nash value and the 2 last claims in the NE paragraph.\n\nThank you for this comment. We have now included 'at all states' in the NE definition and specified the restrictions of finite states and actions. We have also added reference [1] for the Nash value and reference [2] for the last 2 claims in the NE paragraph.\n\n**Weakness 2**\n\n> The experiments are unfortunately a bit lacking as the authors only present ablations of their own method and comparisons to the DP solution. While the use of RL was well-motivated as other PEG solving algorithms would be difficult to generalize, it still would be useful to see if a naive implementation of PSRO in no-exit PEGs.\n\nThanks for this suggestion. Currently, we have additionally tested the result of our RL pursuer and evader policies against PSRO policies directly trained on the testing graphs (10 iterations, 1000 episodes per iteration):\n\n| Map/Location | \\| | Timestep (Success Rate) | | | |\n|---|---|---|---|---|---|\n| | \\| | RL[p] vs PSRO[e] | \\| | PSRO[p] vs RL[e] | |\n| Grid Map | \\| | 14.04 ± 6.88 (1.00) | \\| | 11.87 ± 2.39 (1.00) | |\n| Scotland-Yard Map | \\| | 17.45 ± 9.17 (1.00) | \\| | 25.48 ± 16.80 (1.00) | |\n| Downtown Map | \\| | 14.14 ± 7.37 (1.00) | \\| | 38.39 ± 30.50 (0.97) | |\n| Times Square, New York | \\| | 17.72 ± 7.86 (1.00) | \\| | 37.87 ± 29.94 (0.97) | |\n| Hollywood Walk of Fame, LA | \\| | 30.93 ± 17.67 (1.00) | \\| | 60.71 ± 39.21 (0.86) | |\n| Sagrada Familia, Barcelona | \\| | 26.06 ± 12.43 (1.00) | \\| | 39.50 ± 28.25 (0.97) | |\n| The Bund, Shanghai | \\| | 24.76 ± 13.01 (1.00) | \\| | 34.97 ± 24.75 (0.99) | |\n| Eiffel Tower, Paris | \\| | 19.10 ± 10.69 (1.00) | \\| | 25.24 ± 14.07 (1.00) | |\n| Big Ben, London | \\| | 23.70 ± 13.00 (1.00) | \\| | 53.67 ± 36.41 (0.90) | |\n| Sydney Opera House, Sydney | \\| | 26.14 ± 12.81 (1.00) | \\| | 67.23 ± 43.37 (0.77) | |\n\nAs is shown in the table above, our RL policies guarantee to capture the PSRO evader and survive significantly longer against the PSRO pursuers (except for Grid Map). This further verifies the benefit of using EPG for cross-graph zero-shot generalization. Besides, we have also approximated the best responses (worst-case opponents) through reinforcement learning against EPG policies on the testing graphs. The approximate best-response policies are generally not better at exploiting EPG policies in comparison with DP:\n\n| Map/Location | \\| | Pursuit Success Rate | | \\| | Evasion Timestep | |\n|---|---|---|---|---|---|---|\n| | \\| | RL[p] vs DP[e] | RL[p] vs BR[e] | \\| | DP[p] vs RL[e] | BR[p] vs RL[e] |\n| Grid Map | \\| | 1.00 | 1.00 | \\| | 11.88 ± 2.39 | 11.67 ± 2.60 |\n| Scotland-Yard Map | \\| | 0.99 | 1.00 | \\| | 12.57 ± 2.96 | 13.12 ± 3.65 |\n| Downtown Map | \\| | 0.99 | 0.99 | \\| | 11.83 ± 3.12 | 13.81 ± 5.83 |\n| Times Square, New York | \\| | 0.98 | 0.95 | \\| | 14.68 ± 3.11 | 16.20 ± 5.16 |\n| Hollywood Walk of Fame, LA | \\| | 0.62 | 0.67 | \\| | 20.00 ± 4.99 | 20.22 ± 9.60 |\n| Sagrada Familia, Barcelona | \\| | 0.66 | 0.76 | \\| | 17.89 ± 4.59 | 18.83 ± 6.30 |\n| The Bund, Shanghai | \\| | 0.60 | 0.56 | \\| | 20.59 ± 5.59 | 21.91 ± 10.58 |\n| Eiffel Tower, Paris | \\| | 0.97 | 0.98 | \\| | 18.47 ± 6.12 | 19.28 ± 10.48 |\n| Big Ben, London | \\| | 0.91 | 0.94 | \\| | 21.58 ± 6.38 | 23.07 ± 12.91 |\n| Sydney Opera House, Sydney | \\| | 0.74 | 0.80 | \\| | 22.37 ± 6.16 | 25.78 ± 16.79 |\n\n**Weakness 3**\n\n> As the authors mention in the conclusion, a test with partial observability would also greatly improve the viability of this method, since this is a typical assumption in MARL. Since the observation encodings use an attention mechanism, it should not be too difficult to implement this.\n\nThanks for the suggestion on the tests with partial observability. Actually, our subsequent studies have already verified that EPG also works in imperfect-information PEGs. The perfect-information DP oracle can be extended to imperfect-information scenarios by preserving beliefs on the opponent's position. Under either perfect-information or imperfect-information DP guidance, EPG under belief predictions can learn a generalized policy through the same cross-graph training paradigm as in perfect-information scenarios. While the actual learning curves converge at larger termination timesteps (over 30 under either guidance), the overall trends are similar to the black curves in Figure 3.\n\n**Question 1**\n\n> Why are there no deviation data provided for the data in Table 1? additionally, what do the error bars in Figure 3 represent? There is a huge difference in the significance of standard error, standard deviation, and confidence intervals.\n\nThanks for the question. We have now rerun the experiments and updated the results with standard deviations for the \"Evasion Timestep\" columns in Table 1 (2 pursuers) and Table 4 (6 pursuers) under 500 tests. Following the suggestion from Reviewer LAVP, we have also added the result of $\\mathrm{RL_{p}-RL_{e}}$ in the tables.\n\n| Map/Location | \\| | 2-Pursuer Case | | | \\| | 6-Pursuer Case | | |\n|---|---|---|---|---|---|---|---|---|\n| | \\| | DP[p] vs DP[e] | DP[p] vs RL[e] | RL[p] vs RL[e] | \\| | DP[p] vs DP[e] | DP[p] vs RL[e] | RL[p] vs RL[e] |\n| Grid Map | \\| | 12.29 ± 2.06 | 11.88 ± 2.39 | 14.34 ± 5.08 | \\| | 7.73 ± 2.75 | 6.28 ± 2.57 | 8.67 ± 4.38 |\n| Scotland-Yard Map | \\| | 15.13 ± 2.77 | 12.57 ± 2.96 | 17.82 ± 7.31 | \\| | 10.28 ± 3.70 | 7.60 ± 2.77 | 11.17 ± 6.04 |\n| Downtown Map | \\| | 14.22 ± 3.27 | 11.83 ± 3.12 | 17.65 ± 8.72 | \\| | 10.44 ± 3.37 | 7.77 ± 2.83 | 10.98 ± 5.44 |\n| Times Square, New York | \\| | 16.47 ± 3.23 | 14.68 ± 3.11 | 20.29 ± 9.65 | \\| | 18.06 ± 6.67 | 14.54 ± 4.84 | 14.79 ± 7.58 |\n| Hollywood Walk of Fame, LA | \\| | 25.56 ± 5.03 | 20.00 ± 4.99 | 34.34 ± 20.18 | \\| | 34.90 ± 16.32 | 24.15 ± 10.20 | 21.03 ± 10.99 |\n| Sagrada Familia, Barcelona | \\| | 21.88 ± 4.82 | 17.89 ± 4.59 | 26.87 ± 11.00 | \\| | 27.11 ± 11.77 | 19.11 ± 5.90 | 18.18 ± 8.30 |\n| The Bund, Shanghai | \\| | 25.26 ± 6.17 | 20.59 ± 5.59 | 30.66 ± 17.27 | \\| | 32.14 ± 16.98 | 22.01 ± 7.95 | 19.47 ± 9.46 |\n| Eiffel Tower, Paris | \\| | 23.42 ± 6.48 | 18.47 ± 6.12 | 28.41 ± 16.80 | \\| | 26.15 ± 9.29 | 20.96 ± 7.70 | 19.86 ± 10.04 |\n| Big Ben, London | \\| | 27.89 ± 6.35 | 21.58 ± 6.38 | 33.24 ± 18.71 | \\| | 32.61 ± 14.09 | 24.45 ± 9.77 | 21.31 ± 10.25 |\n| Sydney Opera House, Sydney | \\| | 26.92 ± 5.89 | 22.37 ± 6.16 | 32.94 ± 14.72 | \\| | 33.23 ± 13.56 | 24.60 ± 10.88 | 21.32 ± 10.78 |\n\nWhile the RL pursuers are generally weaker than the DP oracle in the 2-pursuer case, they actually outperform DP against the RL evader in part of the 6-pursuer scenarios, where DP only constructs an approximate oracle under grouping extension.\n\nFor the error bars in Figure 3, we clarify that they represent standard deviations.\n\n**Question 2**\n\n> Why are the testing generalization plots in Figure 4 plotted over time in seconds? Why not flops, or timesteps? This would make for a computationally fair comparison.\n\nThanks for the question. In Figure 4, the results besides EPG are cited from the paper of Grasper [3]. Since EPG requires no time for fine-tuning, we directly show the original time cost of the comparative methods reported in [3].\n\nThank you again for the insightful comments and helpful suggestions. We hope our response properly addresses your concerns. We are looking forward to having further discussions with you.\n\n**References**\n\n[1] Lloyd S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):1095–1100, 1953.\n\n[2] Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.\n\n[3] Pengdeng Li, Shuxin Li, Xinrun Wang, Jakub Cerny, Youzhi Zhang, Stephen McAleer, Hau Chan, and Bo An. Grasper: A generalist pursuer for pursuit-evasion problems. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 1147–1155, 2024."}, {"review_id": "ta0i3x8sX0", "reviewer": "Reviewer_LAVP", "summary": "This paper proposes using reinforcement learning (RL) to learn pursuit-evasion game (PEG) policies that generalize across different graph environments. The authors simulate the adversary's policy using a dynamic programming (DP) algorithm for no-exit Markov PEGs and a heuristic for multi-exit cases. They then train a soft-actor-critic agent against this equilibrium adversary. Experiments on real-world graphs demonstrate zero-shot generalization of the learned policy.", "questions": "1) How does the RL algorithm perform when tested against non-equilibrium policies (e.g., random or heuristic agents)? Also, what is the performance of $\\text{RL}_p$–$\\text{RL}_e$ in Table 1?\n2) Please provide more details on the graphs used in Table 1 (e.g., number, average degree, diameter). Also, the authors could explain why $\\text{RL}_p$–DP underperforms on graphs like Hollywood Walk of Fame, Sagrada Familia, and The Bund, to help the readers have a full understand of the proposed method.\n3) There is an inconsistency in Table 3: Line 572 mentions 1,000 trials, while the caption states 100 episodes. Please clarify the correct number. Additionally, since computational efficiency is a key contribution, it would be more informative to report and compare the average computation time per episode for EPG and DP in the main text rather than in the appendix.", "limitations": "The proposed method’s scalability is constrained by the shortest-path-based state representation, which incurs O($n^3$) complexity.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n1) The paper shows that training RL agents against an equilibrium adversary on a graph corpus enables generalization to unseen graphs.\n2) Experiments on diverse real-world maps demonstrate the method's strong zero-shot performance.\n3) A sequential decision-making framework is proposed to address the large joint action space, enabling decentralized execution.\n\n**Weaknesses**:\n1) The claim that the RL method is computationally more efficient than traditional DP is not supported. The DP baseline reaches equilibrium in just 10 seconds (as mentioned in Line 569), raising questions about the RL method’s efficiency given its additional training cost.\n2) The second claim—that the RL approach avoids overfitting to specific behaviors—would benefit from further evidence. As both training and testing rely on Nash equilibrium policies, it remains unclear how the method performs against other types of adversaries, such as random, SPS, or alternative RL agents in testing environments.\n3) The training and test graphs are insufficiently differentiated, making the claimed generalization unclear.\n4) The method is tested on a limited number of agents; its scalability to larger settings (e.g., >10 pursuers) is untested.", "was_revised": true, "final_justification": "Thanks to the authors for their response. The rebuttal has addressed some of my concerns regarding training details and the advantages of RL over DP. However, I still have reservations about applying the proposed EPG policies to more complex scenarios with larger agent scales. As noted in the rebuttal, grouping pursuers under six is more reasonable, yet in the results provided for Question 1, RL pursuers generally underperform compared to DP in the 2-pursuer case. However, I still acknowledge the strength of the proposed RL method in cross-graph generalization and therefore maintain my initial positive score.", "rebuttal": "Dear reviewer,\n\nThank you very much for your review. We are glad to provide more details to clarify the weak points and answer your questions.\n\n**Weakness 1**\n\n> The claim that the RL method is computationally more efficient than traditional DP is not supported. The DP baseline reaches equilibrium in just 10 seconds (as mentioned in Line 569), raising questions about the RL method’s efficiency given its additional training cost.\n\nThank you for the question on the RL method's efficiency. Actually, the DP algorithm that we propose in this paper already significantly improves over the traditional methods, guaranteeing a near-optimal time complexity of $\\tilde{O}(|S|)$ (rather than $O(|S|^2)$). That said, our RL method has a range of advantages: First, when facing a new graph with 1000 nodes, DP will suffer from a significant slowdown (about 10 times slower than the 500-node case). In comparison, RL trained under 500-node graphs can immediately provide good policies, whose quality is verified by the scalability tests in our response to Reviewer BGj6. Under 1000 nodes, the necessary running of the $O(|V|^3)$ Floyd algorithm for RL is still finished within 1 second (since it has no extra constant factor), which is much faster than the $\\tilde{O}(|V|^3)$ DP even under 2 pursuers. Second, in multi-exit cases, exact and efficient equilibrium oracles like DP are hard to construct. While simply following the heuristic pursuer policy to finish a game guarantees an average worst-case utility around 0.5 in our training corpus, the RL policy achieves an average worst-case utility over 0.65 after training. This additional result could further demonstrate the necessity of RL when only equilibrium heuristics are available.\n\n**Weakness 2**\n\n> The second claim—that the RL approach avoids overfitting to specific behaviors—would benefit from further evidence. As both training and testing rely on Nash equilibrium policies, it remains unclear how the method performs against other types of adversaries, such as random, SPS, or alternative RL agents in testing environments.\n\nCurrently, we have conducted additional experiments against alternative RL agents like PSRO [1] and approximate best responses to our policies. The result is reserved in our response to Reviewer m6zW (Weakness 2) and further demonstrates the strength of EPG policies.\n\n**Weakness 3**\n\n> The training and test graphs are insufficiently differentiated, making the claimed generalization unclear.\n\nThanks for mentioning the training and testing differentiation. As is stated in Lines 264-266, our training graphs are always the 152 Dungeon graphs. Our zero-shot testing graphs are differentiated from the training graphs: Section 4.1 (Table 1) uses 10 unseen real-world graph structures. Section 4.2 (Figure 3) uses 10 unseen Dungeon graphs. Section 4.3 (Figure 4) uses the 10 unseen Dungeon graphs (left, zero-shot evaluations during training), Grid Map (mid), and Scotland-Yard Map (right). Currently, we have added further clarifications in our paper.\n\n**Weakness 4**\n\n> The method is tested on a limited number of agents; its scalability to larger settings (e.g., >10 pursuers) is untested.\n\nThank you for the comment on the agent number. There is actually a theoretical reason behind our choice of conducting experiments under 6 pursuers. [2] proves that in any planar graph, 3 pursuers are efficient to capture the evader. Therefore, when the pursuer number is overly large (e.g., >10 pursuers), it is less meaningful to learn a completely joint policy for real-world pursuit. A more reasonable substitute is to group the pursuers and use the 6-pursuer policies (or less) separately. For the evader side, it is also intuitively difficult to learn an effective evasion policy against too many pursuers. Besides, when compared to Table 1 and Figure 5, Table 4 and Figure 6 suggest that EPG could have even stronger zero-shot generalization capability in games with more agents.\n\n**Question 1**\n\n> How does the RL algorithm perform when tested against non-equilibrium policies (e.g., random or heuristic agents)? Also, what is the performance of $\\mathrm{RL_{p}-RL_{e}}$ in Table 1?\n\nCurrently, we have further tested EPG policies against PSRO [1]. Our policies guarantee to capture the PSRO evader and survive significantly longer against the PSRO pursuers. Besides, we find that directly training best responses against our policies does not lead to the policies that are better at exploiting ours in comparison with DP. The detailed results are reserved in our response to Reviewer m6zW.\n\nHere we provide the results of $\\mathrm{RL_{p}-RL_{e}}$ for the \"Evasion Timestep\" in Table 1 and Table 4:\n\n| Map/Location | \\| | 2-Pursuer Case | | | \\| | 6-Pursuer Case | | |\n|---|---|---|---|---|---|---|---|---|\n| | \\| | DP[p] vs DP[e] | DP[p] vs RL[e] | RL[p] vs RL[e] | \\| | DP[p] vs DP[e] | DP[p] vs RL[e] | RL[p] vs RL[e] |\n| Grid Map | \\| | 12.29 ± 2.06 | 11.88 ± 2.39 | 14.34 ± 5.08 | \\| | 7.73 ± 2.75 | 6.28 ± 2.57 | 8.67 ± 4.38 |\n| Scotland-Yard Map | \\| | 15.13 ± 2.77 | 12.57 ± 2.96 | 17.82 ± 7.31 | \\| | 10.28 ± 3.70 | 7.60 ± 2.77 | 11.17 ± 6.04 |\n| Downtown Map | \\| | 14.22 ± 3.27 | 11.83 ± 3.12 | 17.65 ± 8.72 | \\| | 10.44 ± 3.37 | 7.77 ± 2.83 | 10.98 ± 5.44 |\n| Times Square, New York | \\| | 16.47 ± 3.23 | 14.68 ± 3.11 | 20.29 ± 9.65 | \\| | 18.06 ± 6.67 | 14.54 ± 4.84 | 14.79 ± 7.58 |\n| Hollywood Walk of Fame, LA | \\| | 25.56 ± 5.03 | 20.00 ± 4.99 | 34.34 ± 20.18 | \\| | 34.90 ± 16.32 | 24.15 ± 10.20 | 21.03 ± 10.99 |\n| Sagrada Familia, Barcelona | \\| | 21.88 ± 4.82 | 17.89 ± 4.59 | 26.87 ± 11.00 | \\| | 27.11 ± 11.77 | 19.11 ± 5.90 | 18.18 ± 8.30 |\n| The Bund, Shanghai | \\| | 25.26 ± 6.17 | 20.59 ± 5.59 | 30.66 ± 17.27 | \\| | 32.14 ± 16.98 | 22.01 ± 7.95 | 19.47 ± 9.46 |\n| Eiffel Tower, Paris | \\| | 23.42 ± 6.48 | 18.47 ± 6.12 | 28.41 ± 16.80 | \\| | 26.15 ± 9.29 | 20.96 ± 7.70 | 19.86 ± 10.04 |\n| Big Ben, London | \\| | 27.89 ± 6.35 | 21.58 ± 6.38 | 33.24 ± 18.71 | \\| | 32.61 ± 14.09 | 24.45 ± 9.77 | 21.31 ± 10.25 |\n| Sydney Opera House, Sydney | \\| | 26.92 ± 5.89 | 22.37 ± 6.16 | 32.94 ± 14.72 | \\| | 33.23 ± 13.56 | 24.60 ± 10.88 | 21.32 ± 10.78 |\n\nWhile the RL pursuers are generally weaker than DP in the 2-pursuer case, they actually outperform DP against the RL evader in part of the 6-pursuer scenarios, where DP only constructs an approximate oracle under grouping extension.\n\n**Question 2**\n\n> Please provide more details on the graphs used in Table 1 (e.g., number, average degree, diameter). Also, the authors could explain why $\\mathrm{RL_{p}-DP}$ underperforms on graphs like Hollywood Walk of Fame, Sagrada Familia, and The Bund, to help the readers have a full understand of the proposed method.\n\nHere we provide more detailed information on the graphs used in Table 1:\n\n| Map/Location | \\| | Node Number | \\| | Average Degree | \\| | Diameter | \\| |\n|---|---|---|---|---|---|---|---|\n| Grid Map | \\| | 100 | \\| | 3.60 | \\| | 18 | \\| |\n| Scotland-Yard Map | \\| | 200 | \\| | 3.91 | \\| | 19 | \\| |\n| Downtown Map | \\| | 206 | \\| | 2.98 | \\| | 19 | \\| |\n| Times Square, New York | \\| | 171 | \\| | 2.58 | \\| | 22 | \\| |\n| Hollywood Walk of Fame, LA | \\| | 201 | \\| | 2.42 | \\| | 31 | \\| |\n| Sagrada Familia, Barcelona | \\| | 231 | \\| | 2.60 | \\| | 25 | \\| |\n| The Bund, Shanghai | \\| | 200 | \\| | 2.53 | \\| | 29 | \\| |\n| Eiffel Tower, Paris | \\| | 202 | \\| | 2.34 | \\| | 38 | \\| |\n| Big Ben, London | \\| | 192 | \\| | 2.48 | \\| | 34 | \\| |\n| Sydney Opera House, Sydney | \\| | 183 | \\| | 2.33 | \\| | 37 | \\| |\n\nIn planar graphs, a larger average degree generally implies the existence of small cycles. For example, in Grid Map, all minimal cycles' length is 4. Since successful evasions rely more on large cycles, graphs like Grid Map, Scotland-Yard Map, and Downtown Map are easier for pursuit. Note that while the Scale-Free Graph in Appendix E.1 has a very large average degree, the cycles in the graph are large as well since it is not a planar graph. Besides, Eiffel Tower, Big Ben, and Sydney Opera House all have large diameters, which implies the existence of long \"branches\" that have poor connectivity with other nodes (see Figure 8). Therefore, these graphs also benefit pursuit since the structures are closer to trees.\n\nSince Hollywood Walk of Fame, Sagrada Familia, and The Bund do not have the mentioned characteristics, these graphs are relatively hard for pursuers. This accounts for the comparatively low success rates of RL and SPS pursuers on these graphs. While Times Square shares a similar structure with these three graphs (also see Figure 8), the success rate of the RL pursuer is high. This suggests that our RL agents could have discovered near-optimal strategies even for some graph structures that do not ease pursuit.\n\n**Question 3**\n\n> There is an inconsistency in Table 3: Line 572 mentions 1,000 trials, while the caption states 100 episodes. Please clarify the correct number. Additionally, since computational efficiency is a key contribution, it would be more informative to report and compare the average computation time per episode for EPG and DP in the main text rather than in the appendix.\n\nThanks for this comment. We are sorry for the typo on the caption and have made a revision. The correct number is 1,000 rather than 100. In the main paper, we have also added a comparison between the execution time of DP and RL and reported the average training time cost for EPG.\n\nThank you again for providing the detailed review and helpful suggestions. We hope our response properly addresses your concerns. We are looking forward to having further discussions with you.\n\n**References**\n\n[1] Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.\n\n[2] Fromme and M. Aigner. A game of cops and robbers. Discrete Appl. Math, 8:1–12, 1984."}]

Author rebuttal:

Meta-review: This paper proposes using reinforcement learning to learn pursuit-evasion game policies that generalize across different graph environments. The authors simulate the adversary's policy using a dynamic programming algorithm for no-exit Markov PEGs and a heuristic for multi-exit cases. They then train a soft-actor-critic agent against this equilibrium adversary. Experiments on real-world graphs demonstrate zero-shot generalization of the learned policy. Reviewers stated many strengths of the paper, such as that EPG’s focus on zero-shot generalization via equilibrium guidance is innovative and practical, the core idea is intuitive and the motivation for equilibrium-guided reinforcement learning is well explained, and experiments on diverse real-world maps demonstrate the method's strong zero-shot performance. The authors did a great job during the rebuttal phase and addressed many of the concerns raised by the reviewers, which led to a significant increase in the rating. Although some reviewers still have reservations about applying the proposed EPG policies to more complex scenarios with larger agent scales, I believe the work deserves a chance to be evaluated by a much broader readership in the future, and the results presented in the paper could benefit researchers in related fields. Therefore, I recommend acceptance.
Decision: Accept (poster)