R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability
Authors: Runyu Lu
Ruochuan Shi
Yuanheng Zhu
Dongbin Zhao
Venue: ICLR 2026 Poster (2026)
Keywords: pursuit-evasion game
partial observability
dynamic programming
belief preservation
reinforcement learning
real-time pursuit strategy
worst-case robustness
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Computing worst-case robust strategies in pursuit-evasion games (PEGs) is time-consuming, especially when real-world factors like partial observability are considered. While important for general security purposes, real-time applicable pursuit strategies for graph-based PEGs are currently missing when the pursuers only have imperfect information about the evader's position. Although state-of-the-art reinforcement learning (RL) methods like Equilibrium Policy Generalization (EPG) and Grasper provide guidelines for learning graph neural network (GNN) policies robust to different game dynamics, they are restricted to the scenario of perfect information and do not take into account the possible case where the evader can predict the pursuers' actions. This paper introduces the first approach to worst-case robust real-time pursuit strategies (R2PS) under partial observability. We first prove that a traditional dynamic programming (DP) algorithm for solving Markov PEGs maintains optimality under the asynchronous moves by the evader. Then, we propose a belief preservation mechanism about the evader's possible positions, extending the DP pursuit strategies to a partially observable setting. Finally, we embed the belief preservation into the state-of-the-art EPG framework to finish our R2PS learning scheme, which leads to a real-time pursuer policy through cross-graph reinforcement learning against the asynchronous-move DP evasion strategies. After reinforcement learning, our policy achieves robust zero-shot generalization to unseen real-world graph structures and consistently outperforms the policy directly trained on the test graphs by the existing game RL approach.

Published as a conference paper at ICLR 2026
R2PS: WORST-CASE ROBUST REAL-TIME PURSUIT STRATEGIES UNDER PARTIAL OBSERVABILITY
Runyu Lu Ruochuan Shi Yuanheng Zhu Dongbin Zhao
1 School of Artificial Intelligence. University of Chinese Academy of Sciences*
2 State Key Laboratory of Multimodal Artificial Intelligence Systems, Institute of Automation, Chinese Academy of Sciences 1urunyu1 7@mailm 1ss ucas ac. cn (ruochuan. shi, yuanheng. 2hu, dongbin. zhao wcngppn..hhollia..c..
ABSTRACT
Computing worst-case robust strategies in pursuit-evasion games (PEGs) is time- consuming, especially when real-world factors like partial observability are consid- ered. While important for general security purposes, real-time applicable pursuit strategies for graph- PEGs are currently missing when the pursuers only have imperfect information about the evader's ' position. Although state-of-the-art reinforcement learning (RL) methods like Equilibrium Policy Generalization (EPG) and Grasper provide guidelines for learning graph neural network (GNN) policies robust to different game dynamics, they are restricted to the scenario perfect information and do not take into account the possible case where the evader can predict the pursuers' actions. This paper introduces the first approach to worst-case robust real-time pursuit strategies (R2PS) under partial observability. We first prove that a traditional dynamic programming (DP) algorithm for solving Markov PEGs maintains optimality under the asynchronous moves by the evader. Then, we propose a belief preservation mechanism about the evader's possible positions, extending the DP pursuit strategies to a partially observable setting. Finally, we embed the belief preservation into the state-of-the-ar EPG framework to finish our R2PS learning scheme, which leads to real-time pursuer policy through cross- graph reinforcement learning against the asynchronous-mot move DP evasion strategies. After reinforcement learning, our policy achieves robust zero-shot generalization to unseen real-world graph structures and consistently outperforms the policy directly trained on the test graphs by the existing game RL approach.
INTRODUCTION
Pursuit-evasion game (PEG) is an important topic long examined in the fields of robotics and security (Vidal et al.) 2001 2002 Chung et af.) 201T). Many real-world tasks can benefit from the solution to an abstracted PEG, e.g.. guiding team of cops capture robber and aligning team of guards to defend against an intruder. In comparison with traditional differential games (Margellos & Lygeros) 2011 Zhou et al. 2012). graph-based PEGs are convenient for describing complicated scenarios, possibly with a large scale. When we use graphs as a common structural representation, the actions of the pursuers and the evader can be abstracted moving from vertex to an adjacent one each discrete timestep. The edges between the vertices can possibly represent urban streets in reality.
However, exactly solving bbapd PEGs is computationally expensive (see Gioldstein & Reingold (1995). Even under a slight structural change, the worst-case robust pursuit strategies can be different and thus require large amount of time to be recomputed. For example, when traffic jam happens in the city, the related edges in the PEG graph can be frequently removed and added. This severely limits the real-time applicability of the existing methods featuring mathematical programming (Vieira et al. 2008 Horák & Bosansky 2017). Besides, real-world factors like partial observability, which
"This work was supported in part by the National Natural Science Foundation of China under Grants 62293541 and 621 22136008 and in part by the Beijing Nova Program under Grant 20240484514.

---

Published as a conference paper at ICLR 2026
leads to PSPACE-hardness even under fixed opponent (see Papadimitriou & Tsitsiklis (1987)) further increase the difficulty of deriving a well-performing pursuit strategy within a time limit.
Reinforcement learning (RL), which has demonstrated strong generalization capabilities in domains like large language models (sce/Chu et al. (2025)), provides an alternative solution to this problem. We may train parameterized policy represented by suitable neural network, e.g., graph neural network (GNN) (Wu et al. 2020), on a diverse set of graphs and then generalize it to the unseen graph structures. Unfortunately, while RL has been applied to solving large-scale PEGs (Xue et al.) 2022 202T), existing research focuses more on its scalability rather than generalization capability, The methods like MT-PSRO (Li et al., 2023) and Grasper (Li et al., 2024) are limited to few-shot generalization to unseen opponent strategies and initial conditions. As is pointed out by ZZuang et al. 2025), they still have difficulty adapting to rapid changes of graph structures. The state-of-the- art method, Equilibrium Policy Generalization (EPG) (Lu et al. 2025a), first examines zero-shot generalization at the level of graphs. However, whether the paradigm of EPG works under partial observability remains underexplored. Besides, all of the mentioned works do not consider the possible case that the evader may have stronger observation capabilities than the pursuers. This makes the strength of the learned pursuit strategies less convincing for real-world security purposes.
In this paper, we present an approach to finding pursuit strategies that are both worst-case robust and real-time applicable under partial observability. We start by analyzing dynamic programmiin (DP) algorithm for efficiently solving Markov PEGs and proving that it also finds optimal strategies when the evader can predict the pursuer's action and move asynchronously. With belief update mechanism, we further extend the DP policies to partially observable setting. The belief preservation serves avoid the complexity of recording all observation histories through abstracting opponent information for effective decision-making. Finally, we embed the belief preservation mechanism into the reinforcement learning framework of EPG and train generalized GNN pursuer policy under partial observability. We then evaluate the worst-case robustness of our real-time RL pursuer policy.
Specifically, the contributions of this paper are threefold:
We theoretically analyze a dynamic programming (DP) algorithm and extend the optimal strategies induced by this algorithm to asynchronous-move and partially observable scenarios. We prove that the DP algorithm induces strictly optimal pursuit and evasion strategies when the evader moves asynchronously and design a belief preservation mechanism against the possibly unobserved evaders. Under belief preservation, we verify that the extended pursuer policy remains strong against the provably optimal perfect-information evader.
We practically train an observation- pursuer policy across different graph structures, deriving the first worst-case robust real-time pursuit strategies (R2PS) applicable to dy- namically changing PEGs with partial observations. We combine our belief preservation mechanism with the state-of-the-ar robust policy generalization paradigm, EPG, and provide an inference time complexity bound for our rep-eeeeedd RL pursuer policy.
Through extensive experiments, we verify that under partial observability, our RL training against the asynchronous-mon move DP evaders under a diverse set of graphs leads to robust zero- shot performance in unseen real-world graphs. Comparative results reveal the superiority of our RL approach over the standard game RL approach, PSRO (Lanctot et al., (017).
2 PRELIMINARIES
2.1 PROBLEM FORMULATION
Adversarial games with partial observability can be generally represented by partially observable stochastic games (POSGs), where equilibrium learning has been rigorously examined in existing game-theoretic research (e.g., Lu et al. (2025b)c). ch). However, this formulation considers all possible observation histories and leads to a large set of decision points whose size is possibly exponential in the time horizon of the game. For the worst scenario of pursuit-evasion, while the pursuers have limited observation capabilities, the evader could still obtain the global information of the game. Since at least one side of the players possesses perfect information, consider first expressing PEGs as swo-player sum Markov games and then extending the definitions to incorporate practical adversarial factors like partial observability and asynchronous moves of the evader.
2

---

Published as a conference paper at ICLR 2026
Two-player zero-sum Markoy game. An infinite-horizon two-player zero-sum Markov game is represented by a tuple A, rr r),, where S is the state space, A is the action space of the max-player (who aims to maximize the cumulative reward), B is the action space of the min-player (who aims to minimize the cumulative reward), P E [o, || is the transition probability matrix, [o. 1] |||| is the reward vector, and E (0, 1) is the discount factor. In PEGi, the max-player the team of m pursuers, and the min-player the evader. We use a termination function f S + {0, } to mark the states where the pursuit is successful. When f(s) 1, the game is terminated, and a reward of +1 is received. Otherwise, a reward of 0 is received. The discount factor y encourages the pursuers to capture the evader soon as possible.
Graph-based pursuit-evasion game. Considering the requirements of formulating large-scale real-world scenarios, we describe states and actions set of vertices v. The global state s = (sp, se) in a game is an clement of y x V, where sp = (o), ep. pp.... :.: upp) E Vr",, and 8, = Ue E V. An edge = (v, v") E E defines the adjacency between two vertices v, o' E V. For example, when we represent an urban scenario by a graph G, an edge e can be used to describe a unit length of streets. The valid actions of the m + 1 agents in graph-based PEG are either moving to an adjacent vertex via an edge or staying at the current node.
graph structure G = (V, Ey): V is the
Policy and value function. Following common notations, we denote by (H, the joint policy of the two players, where ju is the policy of the max-player (pursuers) and is the policy of the min-player (evader): jus) ((A) (resp., vss) A(B)) is the max-player's (resp.. min- min-player's) s) action distribution at state s E S. Since ((A) is the probability simplex over A, ju(s, a) corresponds to the probability of selecting action A at state 8. Given the joint policy, we further define the value function VH.P (s) = E Σ 7 (r(2, 0t, by) |80 = 8; Ht, v as in Markov decision processes.
Solution concept. A Nash equilibrium (NE) in a game is joint policy where each individual player cannot benefit from unilaterally deviating from his/her own policy (Roughgarden) (016). Specifically, in a two-player zero-sum MG, an NE (f²,v") satisfies Vu." I <VR s I VV' for any j and v at all states. As is well known, every MG with finite states and actions has at least one NE, and all NEs in two-player zero-sum MG share the same value (s) V*" .v" (s) max, min, VRP (s) min,mmx,, p (s) (Shapley 1953). In two-player zero-sum Markov games, Nash equilibrium can be viewed as a globally optimal joint policy since both players cannot be exploited by their worst-case opponents when the players move synchronously (simultaneously))
Game extension. Since Markov games only take into account synchronous moves and full observa- tions, we further allow for two variations concerning asynchronous moves and partial observability. In reality, the worst evader (from the pursuers' perspective) may have good predictions of the pursuit actions. Therefore, we allow it to decide after the pursuers' move a at each timestep. In this case, the evader policy v(s) is transformed into an asynchronous one v(s, a). and we say that a strategy is optimal for the pursuer/evader side at state if the worst-case termination timesteps of all possible trajectories starting from are maxiiizee//miimizze. Besides, the availability of sensors may not allow the pursuers to observe an agent that is far away (while the worst evader can). In this case, the pursuer policy p(8) is transformed into p(o), where o is the history the pursuers' local observations.
2.2 DYNAMIC PROGRAMMING FOR MARKOV PEGS
The traditional marking algorithm (Chung et al. 2011) provides general idea of recursively finding optimal strategies in perfect-informatie have been marked, then we can also mark the current state, which means the pursuers can capture the evader starting from this state. However, direct implementation of the marking algorithm incurs a time complexity much higher than the theoretical lower bound (([S)). In view of this gap. Lu et al. (2025a) introduce dynamic programming (DP) algorithm (see Algorithm 1 that guarantees near-optimal time complexity for solving Markov PEGs.
PEGs. If all possible evading actions lead to the states that
Algorithm I computes distance table D through preserving queue Q. Intuitively, the distance value (ss) indicates the worst-case timestep for the pursuer side to capture the evader starting from the global state (5p;8e)) which is guaranteed through the use of minimax policy
11" (8p: 8c) neighbor ny of tp noighhor ne of ds
arg min
max
D(pps me)
(1)
3

---

Published as a conference paper at ICLR 2026
Algorithm 1: Dynamic Programming for Markov PEGs
Input: Graph G E), Pursuer Number m, and Termination Function f 1m - {0.1) Initialize an empty queue Q and the distance table D for pursuer state (positions) 8p E ym do for evader state 8 V do if [8ps Se) = then Sspp 5e)
Push (Sp. Se) into Q
end
end
end
while Q is not empty do
11
Pop the first element (.) from Q
for evader neighbor ne Neighbor(s.) (s.) An's V. (ne, n2) E, (sp, n2)) (ssp, se) do
13
for pursuer neighbor np E Neighbor(sp) c Vmm D(np, ne) = 0o do
(mp ne) (spp 8e)
15
Push (np, ne) into Q
16
end
17
end
18
end
Output: Distance Table D
Under synchronous moves, the evader's policy is symmetrically defined as
(sp: se)
arg max neighbor e.
min neighbor nu of op
Dmp nee)
(2)
Using mathematical induction, Lu et al. (2025a) prove that the joint policy (n² vv") is near-optimal pure strategy (the proof can be found in Appendix II
Theorem 1. there exists pure-strategy Nash equilibrium in the Markov PEG, then the joint policy (μ², v²) defined by (7) and (2) is a Nash equilibrium.
EXTENDING DYNAMIC PROGRAMMING POLICIES TO ASYNCHRONOUS MOVES AND PARTIAL OBSERVABILITY
In this section, we further show that the distance table D generated by the DP algorithm (Algorithm 1 can also be used to construct the optimal evader policy under asynchronous moves, well the observation-baue pursuer policies under partial observability.
3.1 ASYNCHRONOUS-MOOS SETTING
When the evader moves asynchronously, we define the DP policy for the evader as
v" (sps Se: np))
arg max neighbor a.
(D(np. me)}
where np is the neighbor of that the pursuers choose to move to in the current decision step, which perceived or predicted by the evader in advance. With this information an additional input, the evader can decide based on the pursuers' positions after their decision rather than before. As result, the policy no longer requires the inner enumeration in
In this case, we can show that the pursuer policy | and evader policy induced by the distance table D are strictly optimal all states. We start our analysis by proving Lemma which reveals the minimax essence of the distance table D. The detailed proof can be found in Appendix A.2
Lemma 1. When D(np: ne)) O, Algorithm guarantees that
D(n ne)
min neighbor op
max noighbor of D(8p) +
4

---

Published as a conference paper at ICLR 2026
Using Lemma we can further prove that D(s) implies the best possible worst-case timesteps starting from state s for both pursuer and evader sides under the asynchronous move setting. The main results are shown as follows, and the omitted proofs be found in Appendix A.3
Theorem 2. Starting from any state s = (Sp, se) satisfying D(s) = d < oc, μ¹ guarantees pursuit within d steps against any evasion strategy, and v² avoids being captured in less than d steps by any pursuit strategy.
Based on the definition of optimal strategies in the asynchronous-move setting (see Section 2.1), Theorem 2 directly implies the following corollary:
Corollary 1. For any state s = (8p, se) with D(s) < oc, both μ and 1 are optimal strategies.
Furthermore, we use Theorem show that whether m perfect-information pursuers are sufficient to capture the evader starting from state & can be determined by whether ((s) < oo:
Theorem 3. Starting from any state (Sp, 8,) with ((s) co, V* can never be captured by any pursuil strategy.
3.2 PARTIALLY OBSERVABLE SETTING
Since the DP algorithm provably generates optimal strategies when both pursuer and evader sides have full observations, it is appealing to reuse the distance table D construct pursuit strategy under partial observability for real-world security purposes. We expect that the Obseervttion-aasee pursuer policy, which is extended from the DP policy under perfect information, should effectively extract history information and align with the original policy when the observation range is infinity.
We consider the following partially observable setting for the pursuers, who may serve as guards in a large area. The PEG begins because an intruder is observed, whose initial position is revealed to the pursuers. Once the game starts, the position of the evader (intruder) can no longer be detected unless it is in the observation range of at least one pursuer. For example, setting the observation range to be 2 means that the evader can be detected only when its distance to one pursuer is less than 3.
Under the partially observable setting, the observation history induces the possible positions of the evader, which we denote by a set Pos. This set is initialized as {se) ), where se is the initial position of the evader. As the game proceeds, it is updated based on the pursuers' observations each timestep:
{se}
evader is observed at Se, evader not observed.
Posnew
Remove (Neiohbee (Neighbor(Pos..aa))
where the operator Remove(.) excludes all currently observed positions (since the evader is currently unobserved) from the possible evader positions represented by Neighbor(Posala), which corresponds to the set of one-step neighbors of the nodes in Posøld.
Given Pos, can express u(o) μ(sp; Pos) and construct minimax policy that bounds the worst-case pursuit timesteps if we assume that the pursuers resume full observability after this step:
(s Pos) arg min neighhor nyy of
arg min neighhor ny sp
max Se EPo neighhor n. s
max
D(n ne)
D(rps me)
max (.eeNiighoorPPo
While this policy is applicable to the case of partial observability, it based on an assumption that the observation limitation continual. Under continual partial observability, we find that averaging the timesteps through preserving belief about the evader's 's position can further encourage effective pursuit, especially when the set Pos large. The bevief-averaged pursuer policy expressed as
bslief(ss.)
max
D(np. De)
neighbor of
p(pps belief)
arg min
(6)
Σ
belief
neighhor n.. sq
where the belief function is initialized to be O except for the initial evader position and updated by & Pos,
O
belief new (se)
Σ
v(v, se belleffataa))
8, E Pos.
(7)
neighbor 1 of
5

---

Published as a conference paper at ICLR 2026
Since the pursuer side cannot obtain the evader's policy when no prior knowledge is available, (0(v) is set to be a uniform distribution over Neighbor(u) by default.
As the original DP policy (s) 1) is provably optimal, Lemma guarantees that both the position- extended policy ju(sp, Pos) and the belief-averaged policy ju(pp belief) maintain the pursuit optimal-
ity when there is unlimited observation capability. The proof can be found in Appendix [A.6
Lemma 2. When Pos is always a singleton, both pursuer policies perfect-information counterpart (
and
will be reduced to their
Note that the time complexity of preserving Pos and belief is only ((V)) at each timestep, where Ô hides the additional factor of enumerating the neighbors. Since the average degree in the real-world graphs can be small (see Table D in Section 5), the computation is practically efficient. In Appendix we provide the illustrations of the belief preservation process for a more intuitive understanding.
4 FINDING ROBUST REAL-TIME PURSUIT STRATEGIRS (R2PS) VIA ADVERSARIAL REINFORCEMENT LEARNING ACROSS GRAPHS
4.1 ADVERSARIAL REINFORCEMEN LEARNING
Since the DP algorithm has a lower-bound time complexity exponential in the agent number, can be impractical to directly apply the DP policies in real time when the graph structure of the game dynamically changes. In view of this problem, we further combine our belief preservation mechanism with the idea of Equilibrium Policy Generalization (EPG) (Lu et al. (025a) to construct a reinforcement learning method, which makes use of some preprocessed D tables and the induced policies train a generalized pursuer policy across diverse set of graphs. We the cross-graph RL policy for zero-shot generalization under unseen graph structures, aiming to derive worst-case robust real-time pursuit strategies (R2PS) under partial observability.
Training Set
Reference Policy μ
G (M)
((0|s) Policy Loss
VC
G: (+)
Policy Model To
G2 (#س m3
(V,
(r,s')
Opponent Policy 2²
Figure 1: Cross-Graph Reinforcement Learning of Generalized Pursuer Policy
Figure I illustrates the cross-graph reinforcement learning pipeline, which features unexploitable evader policies as adversaries. The training set contains graphs with various topologies G₁ and the DP policies (M] uz") induced by the preprocessed 1) tables. In each iteration, a graph G; along with the policy (n4 vz) is sampled. Under graph G = G,, we use μ³ = 1r as the reference policy to guide policy training and use /² = 1/," the adversarial policy. Following the principle of EPG, train a cross-graph pursuer policy through reinforcement learning against y/* with the guidance of μt"
Specifically, for a transition (s, b, s') in the replay buffer: is randomly generated global state in the sampled graph; a is the pursuers' joint action sampled from the current policy model Re, which ideally graph neural network (Wu al. 2020's with parameter 0 that enables real-time inference; b is the evader's action generated from the asynchronous-ne move opponent policy 1/ (3); the instant reward and the next state s' are generated by the PEG dynamics under graph structure G (V, F).

---

Published as a conference paper at ICLR 2026
Given state the reference policy μ² generates deterministic reference action a' (²(ss) serves to construct the policy loss
and (O|ss) log log=o(s,
C (0]ss) J (01s) + 3LL
(8)
where (+ Is) is the original policy loss of any backbone (multi-agent) reinforcement learning algorithm (e.g., MAPPO (Yu et al., 2022)), and 3 is a hyperparameter that balances policy guidance (for efficient exploration) and reinforcement learning loss (for policy optimization).
When training pursuers under partial observability, we transform the input of the policy model me by
(Spr Pos, belief)
and use the observation based policy sk Pos) 5 μ(sp. belief) (6) to replace f (*(() where Pos and belief are the preserved evader information under partial observability.
For dynamic games like PEGs, the policy space has certain transitivity structures. Czarnecki et al. (2020) show that the strategies in real-world games have different levels of transitive strength, with Nash equilibrium being the strongest. In single-grapl PEG, reinforcement learning against the optimal evader policy 2 helps to exclude the pursuer policies that are transitively weaker. Cross- graph training is similar finding the joint part of the remaining strategies and abstracting them to a worst-case robust policy under a diverse set of graph structures, where the divisions on the policy space through adversarial RL can be different. Imagine that a half space is excluded after each single-graph division and that the division criteria of different graphs are independent due to structural distinctions. In this ideal case, the cross-graph policy will be improved an exponential level across a diverse training corpus, leading to robust pursuit strategies even under partial observability.
4.2 IMPLEMENTATION AND COMPLEXITY ANALYSIS
Technically, we use soft-actor critic (SAC) HHarnoja et al. 2018: Christodoulou 2019) as the backbone RL algorithm and employ decentral lized architecture with parameter-sharing graph neural network (GNN) (Cao et al. 2023) Lu et al. 2025a) to represent the graph-based policy of the homogeneous pursuers. The SAC algorithm features a self-adaptive entropy regularization that balances exploration and exploitation, with double Q-learning (Hasselt) 2010) employed to avoid overestimation. The GNN architecture combines multi-head self-attention (Vaswani et al. 2017) with adjacent-matie matrix masks to encode graph-based states. The state embedding is then sent into a decoder followed by pointer network (Vinyals et al., 2015) for graph-based policy output.
The implementation details and hyperparameter setting are reserved in Appendix to save space" I According to the corresponding analysis, the overall time complexity of computing the graph- state feature is (n²m), where |V] is the number of vertices in the graph, and m is the number of pursuers. Since the complexity of GNN queries is also O(n"m), and the complexity of preserving Pos and belief is On)) the overall inference time complexity of the RL pursuer policy at each timestep is only O(n2m) + (n?m) + (n)) = On)m)) In comparison, the time complexity of recomputing DP policies is On under dynamically changing graph structures (see Lu et al. (2025a)). as Algorithm| D Ineeds to repeatedly executed. Here we briefly show the inference time gap arising from this complexity distinction. When n = 1000 and m = 2, it takes over 2 minutes to run Algorithm D each timestep using an Intel Core 13900XX CPU. The inference time of our GNN-represented RL policy, however, is less than second under the same condition. Our subsequent tests further show this inference can be reduced below 0.01 seconds under GPU accelerations.
EVALUATIONS
Here we provide our experimental evaluations of single-graph DP pursuers and cross- graph RL pursuers under partial observability. We assume that there are two pursuers (m = 2) against the single evader. This is reasonable setting view of the graph-theoretic result that 3 pursuers with full observations can always capture the evader in any planar graph (Fromme & Aigner) 1984). The initial position is randomly generated under the restriction that the distance between the evader and the pursuers is larger than the observation range of 2. Besides, observation sensors except for the
Code he found http::/gtthii.comm/CCaeeee///// code.
7

---

Published as a conference paper at ICLR 2026
pursuers themselves are allowed. The 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 7 famous real-world spots (from Times Square to Sydney Opera House). The graph details are shown in Appendix D.I] and the statistics of these graphs are shown in Table (left).
Table Graph Data (Total Node Number, Average Degree, Diameter) and Success Rate Comparison
Node
Degree
Diameter
Shortest Path
DPPos
belief
Grid Map
100
3.60
18
0.00
0.59
0.78
Scotland- Yard Map
200
3.91
19
0.00
0.44
0.63
Downtown Map
206
2.98
0.02
0.73
0.90
Times Square
171
2.58
22
0.01
0.41
0.69
Hollywood Walk of Fame
201
2.42
31
0.01
0.25
0.48
Sagrada Familia
231
2.60
25
0.00
0.24
0.36
The Bund
200
2.53
29
0.03
0.30
0.57
Eiffel Tower
202
2.34
38
0.29
0.69
0.94
Big Ben
192
2.48
34
0.08
0.54
0.74
Sydney Opera House
183
2.33
37
0.05
0.47
0.87
5.1 EVALUATIONS OF EXTENDED DP PURSUERS
We first evaluate the strength of the extended DP pursuers under partial observability (Section 3.2). We denote by Dos the position-extended pursuer (5) and by Debelief the belief-averaged pursuer (6). The pursuers succeed (f(s) = 1) when at least one of them adjacent to the evader on the graph within 128 timesteps, and the success rates
averaged over 500 tests. To simulate the difficult case for security purposes, the evader is set to be the provably optimal DP evader 3 with global observations and asynchronous moves. For an intuitive comparison, we also include the result of directly following the shortest path to the evader under full observability.
As shown Table (right), the thortest-path strategy can hardly capture the optimal DP evader. In comparison, though under a limited observation range of 2, the extended DP pursuers demonstrate significantly higher success rates. Besides, Debelief consistently outperforms DP This result verifies that the direct minimax policy (5) can be improved through belief averaging. Actually, since equation (5) treats all possible positions as equal, the result of the inner max can very large when the size of Pos is large, leading to pessimistic pursuit behaviors like staying at certain "rest points."
We further take look at how observation capabilities could affect success rates. We increase the observation range and evaluate the performance of DPbelief 66). As is shown in Table 6 (Appendix D.2). the success rates monotonically increase with the observation range and reach 100% when the range exceeds 5. While ((-) is accurate estimator of the worst-case pursuit distance in Markov PEGs, it becomes an optimistic one under partial observability. Nevertheless, the experimental results show that combining this optimistic estimator with belief information maintain the strength of the DP-based pursuit strategies, even under very limited observation capabilities.
5.2 EVALUATIONS OF GENERALIZED RL PURSUERS
Now, we implement and evaluate our cross-graph reinforcement learning method aimed at R2PS (Section 4). We discretize the maps from the Dungeon environment (Chen et al., 2019) to construct synthetic training set containing 150 graphs and further include 150 random urban locations from Google Maps to create large training set with a total of 300 graphs, where the maximum node number is no more than 500. We apply the R2PS learning scheme the synthetic training set and the large training set. Appendix C.4 provides Cr4vviiddes the learning curves of the pursuer policies under partial observability. As is shown in Figure 4 using the extended DP pursuers as guidance (3 0.1) helps to improve the training efficiency over pure reinforcement learning (f = 0) under either training set.
Jalicy-Space Response Oracles (PSRO) (Lanctot et al., 2017) a general reinforcement learning method extended from the came-theoretic approach of double oracle (DO) (McMahan et al. 2003) for equilibrium finding. Here we compare the zero-shot performance of our generalized pursuer policy with PSRO policy that is directly trained the 10 test graphs using 10 iterations (10000
8

---

Published as a conference paper at ICLR 2026
Table 2: Success Rate Comparison across Different Graphs and Strategies
Evader Policy
Stay
DP
DP
BR async
asyuc
Pursuer Policy
Ours
PSRO
Ours
PSRO
Ours
PSRO
Ours
Grid Map
1.00
1.00
1.00
0.94
1.00
0.88
1.00
Scotland- Yard Map
1.00
1.00
1.00
0.47
0.76
0.00
0.73
Downtown Map
1.00
0.99
1.00
0.88
0.99
0.03
0,92
Times Square
1.00
0.93
1.00
0.16
0.95
0.04
0.27
Hollywood Walk of Fame
1.00
0.95
0.90
0.00
0.38
0.00
0.10
Sagrada Familia
0.99
0.93
0.96
0.07
0.20
0.00
0.20
The Bund
1.00
0.95
0.92
0.31
0.25
0.04
0.23
Eiffel Tower
1.00
0.99
1.00
0.97
1.00
0.52
0.55
Big Ben
1.00
0.99
1.00
0.29
0.82
0.24
0.65
Sydney Opera House
1.00
0.98
1.00
0.07
0.95
0.11
0.31
episodes per iteration). Our RL policy aimed at R2PS, however, is pretrained under the synthetic training set with 150 graphs for 30000 episodes (3 0.1) and then trained under the 150 random urban graphs for 70000 episodes. Since our training process never comes across the test graphs, our RL policy has zero-shot generalize these unseen graph structures during evaluations.
As is shown in Table 2 our pursuer policy consistently outperforms the PSRO pursuer policy in the real-world graphs against variety of opponents, where:
evader that stays the initial position. Since the initial distance between the pursuers and the evader is larger than the observation range, and the pursuers have no prior knowledge about the evader's policy, staying still is a reasonable strategy and leads to the occasional failure of these RL pursuers.
Stay corresponds
DP Dasyue corresponds to the DP evader policy under synchronous moves, and DP Dassnc corresponds to the strictly optimal policy (3) under asynchronous moves. It is clear that the ssynchronous-movv evaders are much stronger than the synchronous-move ones due to the advantage of forecasting the pursuers' decisions. Against DP asyncs the PSRO pursuers struggle under most of the test graphs in comparison with ours.
gagne corresponds to the best-responding asynchronous move evader directly trained against our RL pursuers in the test graphs for 30000 episodes (converged). Even under this worst case, the success rates of our generalized pursuers are over 50% half of the graphs.
Since our worst-case zero-shot performance is clearly better than the PSRO policy directly trained on the test graphs, graph structures, which implies that our approach achieves R2PS under partial observability.
say that our real-time strategies are worst-case robust even under varying
5.3 SCALABILITY TESTS AND ABLATION STUDIES
Table 3: RL Success Rate (against DP asynee) and Comparison of Inference Time in Large Graphs
Node Number
Sucess Rate
RI Time (s)
DP Time (s)
Times Square
1805
0.56
0.009837
101
Hollywood Walk of Fame
1251
0.46
0.007917
33
Sagrada Familia
2065
0.33
0,009895
139
The Bund
1723
0.46
0.008117
83
Eiffel Tower
1825
0.41
0.009616
96
Big Ben
1681
0.49
0.007752
79
Sydney Opera House
744
0.76
0.007648
6
Now further verify the real-time pursuit capability under the graphs with higher complexity. We create another set of test graphs based on the seven famous locations in Table (from Times
Square to Sydney Opera House). Compared to the original graphs, the new graphs double both

---

Published as a conference paper at ICLR 2026
the map range and the discretization accuracy, leading significantly larger node numbers. The success rates of our RL pursuer policy against the optimal evader DP asyuc and the inference time comparisons under NVIDIA GeForce RTX 2080 Ti GPU shown in Table Clearly, RL policy requires significantly smaller inference time in comparison with DP and maintains desirable overall performance under large graphs in comparison with the results in Table 2 D.2) provides the scaling plots of our GNN-based RL policy inference and DP computation time.
Figure (Appendix
We are also curious about whether our RL policy trained under the limited observation range of can demonstrate better performance when the observation range is larger during inference time. As is shown Table (A (Appendix D.2), the success rates of our RL pursuers monotonically increase with the observation range. This additional result implies that our RL policy trained with the minimum observability can be directly applied to the cases with better sensing capabilities.
Finally, we examine how the belief updates affect pursuit performance. As we have mentioned, our belief preservation 7 always employs a uniform evader policy v since we could not access prior information about the true opponent. However, if we manage to obtain such information in reality, we can instantly improve the pursuit performance by replacing with actual evader policy, As is shown in Table 4 utilizing known opponent information improves success rates against the best-responding evader Basynne On the other hand, if we reduce the belief update frequency from every single step (original) to every This result further demonstrates the benefits of our belief update mechanism.
steps, then the pursuit success rates will instantly decline.
Table 4: RL Success Rate (against BR Comparison under Different Belief Update Conditions
Belief Update Condition
Known Opponent
Original
Every Steps
Every 3 Steps
Grid Map
1.00
1.00
0.60
0.42
Scotland- Yard Map
0.99
0.73
0.34
0.28
Downtown Map
1.00
0.92
0.61
0.39
Times Square
0,42
0.27
0.18
0.17
Hollywood Walk of Fame
0.13
0.10
0.04
0.03
Sagrada Familia
0.28
0.20
0.12
0.05
The Bund
0.54
0.23
0.13
0.12
Eiffel Tower
0,81
0.55
0.32
0.29
Big Ben
0.82
0.65
0,40
0.25
Sydney Opera House
0.54
0.31
0.22
0.15
CONCLUSION
This paper presents a general approach to worst-case robust real-time pursuit strategies under partial observability and varying graph structures. We first theoretically examine dynamic programming (DP) algorithm and prove that can unify the solutions to Markov PEGs with either synchronous asynchronous moves. Then, propose belief preservation mechanism to efficiently abstract evader information from the observation histories of the pursuers and thus construct the observation-basse pursuer policies. Finally, we embed the belief preservation mechanism into the framework of EPG (Lu et al.) 2025a) to find robust real-time pursuit strategies, fulfilling cross- graph reinforcement learning against the asynchronous-movv DP evader under partial observability. Experiments show that our observation-bast efficient policy exploration during RL training. Under unseen real-world graph structures, our eross- graph policy manages to generate real-time pursuit strategies with worst-case robustness, consistently outperforming the PSRO policy directly trained under the test graphs. Comparative results also reveal that the pursuers can benefit from belief updates, while the evader benefits from asynchronous moves.
DP pursuers can be used as guidance to facilitate
In this work, the belief preservation mechanism provides an affordable way to handle partial observ- ability in real time. We show that this mechanism can be effectively combined with the existing PEG methods like DP and EPG. After adversarial reinforcement learning across graphs, generalized pursuer policy under belief preservation is eventually derived, leading to the first worst-case robust real-time pursuit strategies under partial observability. Hopefully, the current research on PEGs could encourage subsequent works the broader research topics concerning real-world security.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported in part by the National Natural Science Foundation of China under Grants 62293541 and 621 22036088 and in part by the Beijing Nova Program under Grant 20240484514, We also thank all the reviewers for their helpful suggestions during the ICLR review process.
REFERENCES
Yuhong Cao, Tianxiang Hou, Yizhuo Wang, Xian Yi, and Guillaume Sartoretti. Ariadne: rein- forcement learning approach using attention-based deep networks for exploration. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 10219-10225. IEEE, 2023.
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, (2):98-12)) 121, 2025. 160:10.23919//ASE.2222...2
Fanfei Chen, Shi Bai, Tixiao Shan, and Brendan Englot. Self-learning exploration and mapping for mobile robots via deep reinforcement learning. In Aiaa scitech 2019 forum, pp. 0396, 2019.
Petros Christodoulou. Soft actor-critic for discrete action settings. arXiv preprint arXiv:1910.07200 2019.
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.
Timothy Chung, Geoffrey A Hollinger, and Volkan Isler. Search and pursuit-evasion in mobile robotics: A survey. Autonomous robots, 31:299-316, 2011.
Wojciech M Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafiei, David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. Advances in Neural Information Processing Systems, 33:17443-17454 2020.
M Fromme and M Aigner. A game of cops and robbers. Discrete Appl. Math, 8:1-12, 1984.
Arthur S Goldstein and Edward M Reingold. The complexity of pursuit on a graph. Theoretical computer science, 143(1):93-12,, 1995.
Tuomas Haarnoja, 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 arXiv: 18/2.05905. 2018.
Hado Hasselt. Double Q-learning. Advances in Neural Information Processing Systems, 23, 2010.
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, pp. 503 510. SCITEPRESS, 2017.
Mare Lanetot, Vinieius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Pengdeng Li, Shuxin Li, Xinrun Wang, Jakub Cemny, Youzhi Zhang, Stephen McAleer, Hau Chan, and Bo An. Grasper: A generalist pursuer for pursuit-evasion problems. In Proceedings of the 23rd International Conference Autonomous Agents and Multiagent Systems, pp. 1147-1155, 2024.
Shuxin Li, Xinrun Wang, Youzhi Zhang, Wangi Xue, Jakub Černy, and Bo An. Solving large-scale pursuit-evasion games using pre- mreitraneed strategies. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 11586-1 1594, 2023.
Runyu Lu, Peng Zhang, Ruochuan Shi, Yuanheng Zhu, Dongbin Zhao Yang Liu, Dong Wang, and Cesare Alippi. Equilibrium policy generalization: A reinforcement learning framework for cross- graph zero-shot generalization in pursuit-evasion games. In The Thirty Annual Conference Newral Information Processing Systems, 2025a.

---

Published as a conference paper at ICLR 2026
Runyu Lu, Yuanheng Zhu, and Dongbin Zhao. Divergence-regullaized discounted aggregation: Equilibrium finding in multiplayer partially observable stochastic games. In The Thirteenth International Conference Learning Representations, 2025b.
Runyu Lu, Yuanheng Zhu, Dongbin Zhao, Yu Liu, and You He. Last-iterate convergence to approxi- mate Nash equilibria in multiplayer imperfect information games. IEEE Transactions on Neural Networks and Learning Systems, 36(8): 138931 2025c. doi 10..1119//NN 16693
Kostas Margellos and John Lygeros. Hamiltoo-Jacobii formulation for reach-avoid differential games. IEEE Transactions on Automatic Control, 56(8): 1 849-1861, 2011.
H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03)), pp- 536-543, 2003.
Christos H Papadimitriou and John N Tsitsiklis. The complexity of Markov decision processes. Mathematics of operations research, 12(3):441-450, 1987.
Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Rene Vidal, Shahid Rashid, Cory Sharp, Omid Shakernia, Jin Kim, and Shankar Sastry. Pursuit- evasion games with unmanned ground and acrial vehicles. In Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164), volume 3, pp. 2948 2955. IEEE, 2001.
Rene Vidal, Omid Shakernia, H Jin Kim, David Hyunchul Shim, and Shankar Sastry. Probabilistic pursuit-evasion evasion games: Theory, implementation, and experimental evaluation. IEEE Transactions on Robotics and Automation, 18(5):662-666 -699, 2002.
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.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Informa- tion Processing Systems, 28, 2015.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2020.
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.
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. Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 4646 2022.
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, 35:24611 11-24211,22624, 2022.
Zijie Zhao, Honglei Guo, Shengqian Chen, Kaixuan Xu, Bo Jiang, Yuanheng Zhu, and Dongbin Zhao. Empowering multi-robot cooperation via sequential world models. In The Thirteenth International Conference Learning Representations, 2026.
12

---

Published as a conference paper at ICLR 2026
Zhengyuan Zhou, Ryo Takei, Haomiao Huang, and Claire J Tomlin. A general, open-loop formulation for reach-avoid games. 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp- 6501-6506. IEEE, 2012.
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 17155 2025.
13

---

Published as a conference paper at ICLR 2026
A OMITTED PROOFS
A.1 PROOF OF THEOREM
Proof. For no-exit PEGs, the Nash value satisfies the following Bellman minimax equation:
max min Σ pls.a) (r(s,a.)) +2 E P(s.a...s))V' (())EA(A) BEB aEA
f(s) 0,
v*(s)=
dES
1
f(s) 1.
Since the transition is deterministic and non-zero reward is received only when termination state is reached, we can simplify the Bellman equation as follows:
max min Σ pls, = (())A((A) BEB aEA
= P(s,a,b)
S(+) = 0,
(+)
f(s)
The equilibrium policy for the max-player satisfies:
1² (*)s) arg max (())E((A)
min [s
aEA
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:
(s) = max min = P(s.
(9)
EEA BEB
Note that the Nash value has the form of V*(s) = 2d E N). Therefore, we consider using
mathematical induction. We assume that V (8) 7 D(s) holds for all states s that satisfies either V*(s) = 7 or D(s) = when d < le (7 )² We want to prove that V*(() = D(*) holds for all states that satisfies either (s) 7h or D(s) k. Clearly, our initialization guarantees that
the proposition holds for = O. Our update condition D(np: nie) = oe 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 (9 to better align with s = (sp: 8e) in Algorithm
Now, prove the first half of the proposition. For arbitrary state s' = (np: ne) that satisfies (*((")= = >*, the simplified Bellman equation (9) guarantees that there exists Sp A(n,)) and b = Se E B(nn) such that (s')'= = >V*(s = P(s', a, a,))). Therefore, there exists s = (Sp, Sc) such that (s) = k-1 According to the first half of the induction hypothesis, we have that D(s) = k oo, which implics that the algorithm once pushed s' into Q. Besides, the Bellman equation guarantees that V E (, V'(P(s a, b') 2 VP a, b)) = V*) =+ k nk By induction hypothesis, D(sp,n')
D(sp, Se) holds for any neighbor n' of ne- Therefore, the algorithm must enumerate ne when popping s = (sp, se). If we have D(np, ne) = oc at the moment, then np will be enumerated in the inner loop, and we will have D(u,, ne) D(sp. + k. Now we complete the proof by showing that D(np. ne) < do implies D(np. me) = =k. Actually, if k D(n,, n.e) < co. then D(s') must be computed by adding 1 some D(s") ) 2 k. Since s" must be popped from Q no later than s, it is contradictory to the fact that D(s") > D(s) = k - 1. If
D(mp, Re)) < k, then the second half of the induction hypothesis implies that V*('') = =1 D(np.ne) which is contradictory to the fact that V**'') =*
Then, we prove the second half of the proposition. For an arbitrary state = (np. n.) that satisfies D(s') k, the Dss) must be computed by adding 1 to some D(s) = k - 1, where s = (sp, se). According to the first half of the induction hypothesis, we have V*(s) = A.=. The algorithm guarantees that D(sp. n/))= < (Spp. S.) = k-1 holds for any neighbor n', of n.. By induction hypothesis, it holds
that 4b' E B(nn), V' a. b)) 2 VP(P(s', a, b)) when a Sp E A(n,) and b = s, E B(n.).
Therefore, min Va (*(P(s', b)) = k-1 when 8p A(np). ). If there exists at = A(np) bEB(ne)
such that min V (' .', 6-1, then we let D² min (P at.b)) > A bEB(n.)
beB(n.)
14

---

Published as a conference paper at ICLR 2026
and let sf (sp= st b5). According to the first half of the induction hypothesis, D( n²) I D(s), st) k- holds for any neighbor ni of ne- Since D(s s() D((pp) st must be popped from Q earlier than 8, which means that ((s) = oo when sf is popped. Therefore, s' = (np. ne) must be enumerated when of is popped, which contradictory to the fact that D(s') = Do when is popped. Therefore, (s') y max min V (P a, b)) =
aEA bEB
For now, we have proved that (*(s) 7 D()), Therefore:
1² (sp: sp)
arg min
max
(n na)
7 (5() arg maxmin V (P(ss,,,)) b)). aEA
neighhor of
neighbor se
BEB
v" (8pp 8e)
arg max neighhor n. of
min neighbor of sp.
D(pps ne)
- (8)
arg min max (P,(s,, b)).
aEA
As there exists pure-strategy Nash equilibrium, it is directly guaranteed that (x", ,²) is a Nash equilibrium.
15

---

Published as a conference paper at ICLR 2026
A.2 PROOF OF LEMMA
Proof. We consider the cases of D(up, ne) - oo and < (mp, ne) < oc, separately.
The first case (np: Re) 20, which implies that (n2, De) is never enqueued:
Suppose that
min neighbor op up
max neighbor on of mae
Dipps sa) < co. Then, we let
D(sp. 8e) J.
Sp
arg min neighbor ep up
max neighbor Sa of the
arg max (isp, neighbor ne
((sp. se) co, (Spr Se) is once enqueued.
Since (spp Se)
min neighbor sp of np
max neighhor se ne
Since Se = arg max
D(sps Se), we have that fn's E V, (ne E E, D(sp. m'd) > D sc).
meighbor 8e of tee
Since (np, me) DO, state (Np: ne) will be enumerated when (Spx 8e) is dequeued. Then, (np, ne) enqueued, which leads to contradition.
Therefore, have min neighbor By of np. in the first case.
max (eeighbor aa of The
(66 = oc, which means the equation holds
The second case is D(ns ne) co, which implies that (np. n2) once enumerated when a state (sp, se) E Neighbor(Mp. ne) is dequeued. According to the enumeration rule, we have Amm' V. (Me, n/)) E E,, (spp n()) > ((pp, Se), which implies &e arg max (spp Se). Since
neighbor s,
D(np. me) = Dspp 8e) + 1, we have:
Desp1 +1
Dinp, 2
min neighbor up up
max neighbar
Now redefine Sp
arg min neighbor 9y of nn
D(sp 80) ,8 ,80== max neighboe se The
arg max neighhor of n. D(sp: se).
Then, we have D(sp, se) =
((sp and in', E V, (ne, n()) E Since the D values in Q do not decrease, we have D( ne) S
min neighhor up neighhbr s. of
max
E, D(pp: m()) > D(8p580) 8c).
D(sp, se) +1=
min neighbor op of up
max neighbor s. of the
Disps 8e) +1
Therefore, D( ne)
min neighbor Sp of np
max neighbor s. nh
D0p 8e) I holds in the second case.
To conclude, the equation always holds when D(1 ne) > 0.
16

---

Published as a conference paper at ICLR 2026
A.3 PROOF OF THEOREM!
2
Proof.
First, we prove that for any state - (sp; 8e) satisfying D(s) d < <c, μ² guarantees pursuit within d steps against any evasion strategy:
Clearly, the proposition holds true when = 0. Assume that the proposition holds for all d < k.
When k, we let up
Dm Ne) ne arg max neighbor n. 9, By Lemma I. we have (np, n²)) S. (m me) = =s(pp se) - - k. Vn', E Neighbor(s.. By induction hypothesis, μ guarantees pursuit within 1 steps for the states (Np, that satisfies n E Neighbor(se). Therefore, μ¹" (s) ny guarantees pursuit within io steps. By induction, the proposition holds true for all d < oc.
arg min neighber up of 8p neighbor ni 8f
max
D(pp: ne).
Second, we prove that for any state = (sp, se) satisfying D(s) = d < oc, ve avoids being captured in less than steps by any pursuit strategy:
Suppose there exists pursuit movement sequence {ng p n within T < steps under policy v². Then, denote by sequence, where 5g = 5 and (s By Lemma
T-1 that captures the evader the corresponding state
82
s
D Sppp se) neighbur vi of ( Ses 1p)}
min
which implies that (8ps 8e) 2 D(pps v² (8ps Sez 7p)) 1, Vnp. Therefore, D(s") (s st) 2 (n v" (s) s/ net,)) + D(s $6 x+1) + = D(s +1. This leads to contradiction:
D(s) = ()*))= 2 D(st) + 1 ((s²) + 2 2 ((x²) )) + =T <d= = D()). Therefore, '² always
avoids being captured in less than steps when D(s) = d co.
A.4 PROOF OF COROLLARY
Proof. By Theorem 2
For (&p: 8e) with (s) < co, since μr" guarantees pursuit within d steps against any evasion strategy, no evader can guarantee evasion for d steps against worst-case pursuit strategy. Since v avoids being captured less than steps by any pursuit strategy, v* is the optimal evasion strategy.
For (8p, se) 8e) with (ss) d < co, since v" avoids being captured in less than d steps by any pursuit strategy, no pursuer can guarantee pursuit in less than steps against a worst-case evasion strategy. Since μ² guarantees pursuit within steps against any evasion strategy, μ* is the optimal pursuit strategy.
A.5 PROOF OF THEOREM 3
Proof. Suppose that there exists pursuit strategy that captures v² within T steps.
In this case, we denote by (s",s) ......, s²} the state sequence of a successful pursuit, where
{D(np. 2² (np)) + 1, which so = and D(sT) = O. By Lemma 11 (spp, sc) neighbor np of of
min
implies D(pp. v" (np)) oc, Vnp Neighbor(sp). Then, we have D(s = x = ((* 0o
+ D(s ) = 0o, which leads to contradiction.
Therefore, for s Se) with (ss) co, can never be captured by any pursuit strategy.
17

---

Published as a conference paper at ICLR 2026
A.6 PROOF OF LEMMA 2
Proof. When Pos is a singleton, we have Pos = {SoJ. Therefore,
(spp Pos)
arg min
max Eniighioor (os)
Dmp Re)
neighbor nn of Sp
arg min neighbor n sp
max neighbor ne of &e
(rps me)
1i (sp: sc).
Besides, we have
belicf(s) =
$ Pos
Σ
u(u, s)belielata())
8 E Pos
neighbor of I
se] neliefnew new (Sa)-
Therefore, it holds that
belief (ew (8e) neighbor n, of
max
D(pp: De)
plpps belief) arg min neighbor ny of by
belief new (8%)
arg min neighhor my of 8p
max
(m ne) = p (5 se).
neighbor na of 8x
18

---

Published as a conference paper at ICLR 2026
B ILLUSTRATION OF BELIEF PRESERVATION
Evader (Node 225)
Pursuers (187, 112] Obs Nodes
Observation Range
High Probability
-10
Time: 1/13
Observed nodes:
Max belief: 1.0000
Distance: 36
-15
5
15
Figure 2: Pursuit Initialization under Limited Observation Range (Nodes with Blue Outlines)
Figure 2 iillsstrates the initial state of one pursuit episode. Two green pursuers with an observation range of 2 are going to capture the red evader that stays still within a total of 13 steps. The purple nodes are some auxiliary sensors that provide additional information for the pursuers (also with an observation range of 2). Therefore, all of the nodes with dark blue outlines can be observed by the pursuers, while the other nodes cannot. At the first step, only the red node has non-zero belief and marked as high probability (represented by the yellow star).
Figure illustrates the pursuit process under belief preservation, where the black or shadowed area around the evader corresponds to belief and the darkness of the nodes indicates the current belief distribution. Following (7). the belief is spread as the game proceeds (see timesteps 2, 4, 6, 8, 10) and used to generate the pursuit strategy (6) under partial observability. At timestep 12, the evader is eventually observed. Since Pos becomes a singleton by (4), the shadowed area disappears, and the observed evader node is marked as high probability again.
Note that when the observed area covers all nodes, the game will be reduced to its perfect-informatie counterpart, where the DP pursuer policy is provably optimal.
19

---

Published as a conference paper at ICLR 2026
A 2000
Puade Flare
Racte
Hip
Detanie 27
Calane
The 3203
DOMKONE FORRE
Figure 3: Pursuit Mustration under Belief Preservation (Shadowed Area around Evader)
20

---

Published as a conference paper at ICLR 2026
C IMPLEMENTATION DETAILS
C.I SOFT ACTOR-CRITEE (SAC)
To fulfill R2PS training, use discrete-action soft-actor critic (SAC) (Christodoulou 2019) the backbone RL algorithm, where:
The value function defined as
((s) (sw [Q(s,a) a) log (s,
The loss of the value network Q is computed as
Jo( = Es,a
(Qo(s,a) (r (V('))))
The loss of the policy network Ta is computed as
Jn (0)= = E, (s)))(((s) [a log (o(s a) Q(s
The temperature a under target entropy H is adaptively updated under loss
J(a) = E,,a a-a (log (s. + +H]
C.2 GRAPH NEURAL. NETWORK (GNN)
We employ sequence model with parameter-sharing graph neural network (GNN) architecture (Lu et al. 2025a) to represent the graph-based policy of the homogeneous pursuers:
Under the principle of sequential decision-making joint policy be decomposed
π (a1, 02, am (s)
-
(aal 8, 01, "0,,""","""11 ,(L-1);
where (s, " 11-1) indicates the global state after the first I pursuers take actions (a:)
For 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 = [V]) for the current graph. The input composed of state feature s and the information of node index for the current acting agent. Note that under partial observability, the global state distances to the pursuers as the initial feature of each node E V. The normalized features of all n nodes are concatenated with (Pos, belief) to construct the state feature sy. Also note that the distances between one node and all other nodes can be computed using the Onn)) Dijkstra algorithm.
replaced by (sp: Pos, belief). We use the shortest path
Given the state feature input 8y. we embed it into Bdx- and send the result into an encoder composed of 6 self-attention layers, where d is the embedding dimension. Each layer takes the output of the last layer as the input and outputs h using masked attention, whose time complexity is also O(n?):
of kj
E
= Wohs, k; = Wkh Wvh, Uny
Vd
Wij
Σ ehee M
min (wij. Mij } Uj
==1
where Wo, WK, Wy e Iddd are the weights to be learned.
Given the output of the encoder h, we employ decoder without masks gather global information. The decoder uses he query in the output features h of all nodes, with the keys equal to the values:
Waho, K; = Wxh,, U. Wyh, u,
47 kg Vd wy
e4
he Σ 1= WyUj.
E
The decoder output he is further concatenated with he and projected into Rdd Then, it is used as query for pointer network, which takes the features of the neighbor nodes ine for the current agent as the keys and values. The pointer network directly outputs the attention vector w as the current policy πt (--ss) since the number of the neighbors aligns with the number of the valid actions. After the first query through the policy network, an action a for the first agent is sampled from x (-Is), and the state is updated s' (8, a1). The subsequent m queries follow the same process as above.
21

---

Published as a conference paper at ICLR 2026
C.3 HYPERPARAMETER SETTING
Table shows the detailed hyperparameter setting used in the training of our RL pursuer policy.
Table 5: Hyperparameter Setting of R2PS Training
Discount factor
0.99
SAC target entropy coefficient
0.05
GNN emhedding dimension d
128
GNN attention heads
8
Batch size
128
Learning rate
10
Update epoch
8
C.4
LEARNING CURVES OF RL PURSUERS
Synthetic Training Set (8= 0.1)
Large Training Set (8 0.1)
Synthetic Training Set (8 = 0)
Large Training Set (8 0)
1.0
120
Teminaatio Timestep
0.8
Success Rate
0.6
80
0.4
60
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
1,0
Episode
x10"
Episode
x10"
Figure 4: Cross-Graph Learning Curves Generalized Pursuer Policies
During the cross-graph R2PS training, we consider use of 3 = 0.1 and 8 = the policy loss L(0) (8). For the former, employ the belief-average DP policy (6) the reference policy. For the latter, it means that the training process is without policy guidance. Figure 4 shows the learning curves of our RL pursuer policies. Clearly, training with policy guidance is more efficient than pure reinforcement learning under SAC loss. This comparison verifies that the DP pursuer policy can serve guidance to facilitate efficient exploration of the cross-graph RL policy. Besides, training under the synthetic training set is relatively easier than under the large one that contains more real-world graph structures. Nevertheless, our R2PS learning scheme gradually improves the quality of the RL pursuer policies under all of the four settings, using very limited observation range of 2.
22

---

Published as a conference paper at ICLR 2026
D EXPERIMENTAL DETAILS
D.1 DETAILS OF TEST GRAPHS
Figure 5: Illustration of Test Graphs (Starting from Scotland- Yard Map)
The test graphs for both DP and RL pursuers include Grid Map x grid), Scotland- Yard Map (from the board game SootlandYYarde Downtown Map (a real-world location from Google Maps), and 7 famous real-world spots (from Times Square to Sydney Opera House). The graph structures illustrated in Figure 5 following the order in Table T
The real-world graphs are generated through a program designed for discretizing the regions around the location centers in Google Maps. The map range is set to be 600 by default (corresponding to a radius of 600 meters). Nodes correspond to actual road intersections, endpoints, and geometry- defined shape points along roadways. Edges represent the physical road segments connecting these nodes, typically encoded as polylines that capture the true geometry of each street. To ensure a topologically coherent intersection structure, closely spaced intersection points (within 20 meters of one another) are abstracted into single representative nodes. After establishing the intersection-level skeleton, the program further adjusts the spatial resolution by subdividing any road segment whose length exceeds 100 (discretization granularity) meters. For such long segments, the program inserts additional intermediate points at regular intervals along the original road geometry. These newly added points are treated supplementary nodes, and the original long segment is replaced by several shorter segments. The resulting graph therefore adopts hybrid granularity: true intersections are preserved primary nodes, while long road segments discretized into shorter units of no more than 100 (discretization granularity) meters.
D.2 ADDITIONAL RESULTS
Table 6: Success Rates of Belief-Averaged DP Pursuers under Different Observation Ranges
Observation Range
4
Grid Map
0.78
0.92
0.99
1.00
1.00
Scotland- Yard Map
0.63
0.95
1.00
1.00
1.00
Downtown Map
0.90
1.00
1.00
1.00
1.00
Times Square, New York
0.69
0.88
1.00
1.00
1.00
Hollywood Walk of Fame, LA
0.48
0.79
0.94
0.98
1.00
Sagrada Familia, Barcelona
0.36
0.70
0.92
0.96
1.00
The Bund, Shanghai
0.57
0.87
0.97
0.99
1.00
Eiffel Tower, Paris
0.94
0.98
0.99
1.00
1.00
Big Ben, London
0.74
0.94
1.00
1.00
1.00
Sydney Opera House, Sydney
0.87
0.96
0.99
0.99
1.00
23

---

Published as a conference paper at ICLR 2026
Table 7: Success Rates of RL Pursuers under Different Observation Ranges
Observation Range
4
Grid Map
1.00
1.00
1.00
1.00
1.00
Scotland- Yard Map
0.76
0.98
0.99
0.99
1.00
Downtown Map
0.99
0.99
1.00
1.00
1.00
Times Square, New York
0.95
0.98
1.00
1.00
1.00
Hollywood Walk of Fame, LA
0.38
0.59
0.96
1.00
1.00
Sagrada Familia. Barcelona
0.20
0.72
0.88
0.95
0.96
The Bund, Shanghai
0.25
0.55
0.82
0.82
0.83
Fiffel Tower, Paris
1.00
1.00
1.00
1.00
1,00
Big Ben, London
0.82
0.95
0.98
0.99
0.99
Sydney Opera House, Sydney
0.95
0.98
1.00
1.00
1.00
We may find that Hollywood Walk of Fame, Sagrada Familia, and The Bund are relatively more difficult for the pursuers, especially under small observation ranges. Based the statistics of the test graphs in Table (left), here we provide a rough analysis this phenomenon. In planar graphs, large average degree generally implies the existence of small cycles. For example, in Grid Map, all minimal cycles' length is only 4. Since successful evasions benefit more from large cycles, graphs like Grid Map, Scotland- Yard Map, and Downtown Map are easier for pursuit. Besides, Eiffel Tower, Big Ben, and Sydney Opera House all have large diameters, which implies the existence of long "links" that have poor connectivity with other nodes (see the last three graphs in Figure 5). Therefore, these graphs also benefit pursuit rather than evasion. As Hollywood Walk of Fame, Sagrada Familia, and The Bund do have the mentioned characteristics, these graphs are harder for the pursuers.
Figure provides the scaling plots of the computation (inference) time of DP and RL policies under an NVIDIA GeForce RTX 2080 Ti GPU, with the log-log plots on the right. Clearly, the time of DP computations significantly increases with the graph sizes. In comparison, the inference time of our GNN- RL policy only slightly longer large graphs than in small graphs.
RL Inference Time
RL Inference Time
120
DP Inference Time
DP Inference Time
Time (seconds)
Time (seconds)
100
1.07
90
104
10:1
20
500
1250
1750
2000
10a
Node Number
Node Number
Figure 6: Scaling Plots of RL and DP Inference Time
24

---

Published as a conference paper at ICLR 2026
D.3 RL PERFORMANCE UNDER MORE PURSUERS
Table 8: Success Rates of RL Policy under Different Pursuer Numbers
Pursuer Number
m =
2
m
m
6
Grid Map
1.00
1.00
1.00
Scotland- Yard Map
0.76
0.99
1.00
Downtown Map
0.99
1.00
1.00
Times Square, New York
0.95
0.97
1.00
Hollywood Walk of Fame, LA
0.38
0.82
0.93
Sagrada Familia, Barcelona
0.20
0.74
0.94
The Bund, Shanghai
0.25
0.99
1.00
Fiffel Tower, Paris
1.00
1.00
1.00
Big Ben, London
0.82
1.00
1.00
Sydney Opera House, Sydney
0.95
0.99
1.00
As our R2PS training is established upon the framework of EPG (Lu al., 2025a), we can also employ the grouping mechanism proposed by Lu et al. (025aa) to derive pursuer and evader policies when the pursuer number m is large. Table compares the pursuit success rates the multi-agent RL policies against the asynchronous-mon the 4-pursuer policy can significantly increase the original success rates for m = 2. When m = the success rates close to even under the fixed observation range of 2. Figure 7 further illustrates the FL.OPs our RI. inference under different graph sizes and pursuer numbers.
Clearly, DP evader under different pursuer numbers
m=4
17.5
m=
15.0
12.5
G5
10.0
2.5
0.0
250
500
750
1000
1250
1500
1750
2000
Node Number
Figure 7: Scaling Plots of Sosating-Poine Operations under Different RL Pursuer Numbers
25

---

Published as a conference paper at ICLR 2026
E RELATED WORK
Finding optimal strategies in PEGs. Graph-based pursuit-evasion games (PEGs) can be categorized into no-exit PEGs and multi-exit PEGs. The former is the primary form of pursuit-evasion and also the focus of this paper, while the latter is sometimes referred to as network security games, For no-exit PEGs, the early theoretical work (Goldstein & Reingold 1995) proves that it requires exponential time to determine whether m pursuers are sufficient to capture one evader on a given graph under perfect information. Vieira et al. (2008) provide the provably optimal method for solving sequential PEGs, [huug et al. (2011) I show that the basic idea behind PEG solving can be represented by marking algorithm featuring state expansion. HHoáák & Bošanský (2017) consider the case where the pursuers only have partial observation and provide dynamic programming algorithm in the form of value iteration for finding Nash equilibrium. Lu et al. (2025a) show that an expansion-base -based dynamic programming algorithm
solve Markov PEGs under a near-optimal time complexity. Recent works (Xue et al.] 2021] (022)) combine neural networks with fictitious self-play and Monte-Carle tree search construct scalable deep reinforcement learning (RL) algorithms for finding robust pursuit strategies in network security games.
Policy generalization in PEGs. Policy-Space Response Oracles (PSRO) Lanccoo et al. 2017) is
a standard game RL paradigm extended from the game-theoretic approach of double oracle (DO) (McMahan et al. 2003) for robust policy learning. While the approach itself general, can only solve PEGs on designated graph structure, just like the methods above. As we have mentioned, policy generalization crucial
applications under real-world PEGs, becoming a focus of recent research. MT-PSRO (Li et al. (023)) combines multi-task policy pre-training with PSRO fine-tuning to enable few-shot generalization to unseen real-world opponents. Grasper (Li al. 2024) proposes two-stage pre-training method to facilitate few-shot generalization to unseen initial conditions of the game. Equilibrium Policy Generalization (EPG) (Lu et al. 2025a) provides a fundamentally novel paradigm to learn generalized policies across the underlying structures of PEGs through the construction equilibrium oracles, guarantceing robust zero-shot generalization to unseen graph structures in Markov PEGs. As EPG does not require the time-consuming PSRO tuning, the pursuit strategies are real-time applicable under full observability. However, as mentioned in Lu al. (2025a), whether such kind of generalization can be applied to the case of imperfect information remains unclear. Since partial observability leads to the inherent PSPACE-hardnes (see Papadimitriou & Tsitsiklis (1877) and exponentially many information sets (see Lu et al. (2025b)). constructing equilibrium oracles directly under partial observability can be intractable.
26


Reviews:
[{"review_id": "Why37MpkYt", "reviewer": "Reviewer_N27S", "summary": "R2PS is a framework for computing worst-case robust, real-time pursuit strategies in graph-based pursuit–evasion games under partial observability. It extends dynamic programming to handle asynchronous movements and limited observations, providing theoretical guarantees of pursuit optimality. By incorporating a belief preservation mechanism to maintain uncertainty over the evader’s position and embedding this process into an Equilibrium Policy Generalization reinforcement learning framework with graph neural network policies, R2PS achieves efficient and transferable learning. Experiments across diverse graph environments show zero-shot generalization and consistent outperformance over existing game-theoretic RL baselines.", "questions": "1. How does R2PS scale with an increasing number of pursuers or higher graph complexity (e.g., connectivity, degree, presence of cycles)? Can the theoretical guarantees extend to multi-pursuer settings as $m$ increases?\n\n2. Is there a quantifiable bound on the sub-optimality of belief-averaged or RL-derived policies relative to the ideal DP baseline, particularly under reduced observation windows?\n\n3. Could the authors provide detailed wall-clock runtime and scaling plots comparing GNN inference and DP computation across a wider range of graph sizes and hardware setups?\n\n4. Since the reward is binary (0/1, line 108), should the reward definition be refined or generalized for more nuanced pursuit outcomes?\n\n5. How does Theorem 1 differ from the results in Lu et al., and is the proof in Appendix A.1 itself a novel contribution? Additionally, Equation (3) requires clearer explanation or motivation.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper extends the classical Markov PEG dynamic programming framework to asynchronous movement and partial observability settings, providing clear proofs of optimality.\n\n2. It leverages belief-based DP guidance to inform an adversarial reinforcement learning process and introduces a cross-graph training mechanism that enables zero-shot structural generalization.\n\n3. The empirical study spans both synthetic and real-world graph environments (e.g., Downtown, Eiffel Tower), incorporating analyses of observation range, runtime efficiency, and time complexity.\n\n4. The proposed method achieves notable improvements in computational efficiency and real-time responsiveness compared to traditional DP-based replanning approaches.", "weaknesses": "1. The related work section is underdeveloped.\n\n2.  The test set is not particularly large or diverse, and key sensitivity analyses (e.g., observation range effects on trained RL policies) are missing.\n\n3. The paper’s writing quality is uneven. Some abbreviations are undefined, and the structure is occasionally confusing (e.g., placing time complexity analysis within the evaluation section rather than methodology).\n\n4. Although the mathematical derivations for belief updates are technically sound, they would benefit from clearer illustrations or explanatory examples to improve accessibility for readers unfamiliar with partially observable multi-agent systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VHozGyzQ3w", "reviewer": "Reviewer_WtQk", "summary": "In the paper the authors presents a method for learning worst-case robust real-time pursuit strategies (R2PS) in graph-based pursuit-evasion games under partial observability. The authors extend a dynamic programming (DP) approach to handle asynchronous moves and partial observability via belief preservation and integrate it into a reinforcement learning framework for cross-graph generalization. Experimental results demonstrate that the proposed method outperforms existing baselines in both synthetic and real-world graphs.", "questions": "Have you considered scenarios where the evader also operates under partial observability? This could better model symmetric real-world pursuit-evasion problems.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a solid theoretical foundation, extending DP-based policies to asynchronous and partially observable settings with proofs of optimality under certain conditions. It looks that the analysis is thorough and well-supported.\n2. The proposed R2PS framework is highly applicable to real-world security and robotics scenarios where graph structures may change dynamically and full observability is unrealistic.\n3. The combination of belief preservation with adversarial RL and cross-graph training is novel and effectively addresses the challenge of zero-shot generalization to unseen graphs.\n4. The method outperforms baselines like PSRO.", "weaknesses": "It has an assumption that the evader’s policy is known or can be approximated. In real world settings, the evader’s strategy may be non-stationary or adversarial in a more complex sense.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N2yZI3welh", "reviewer": "Reviewer_gW73", "summary": "The paper investigates robust cross-graph strategies for pursuit-evasion games (PEGs) in the partial-observability setting. It is assumed that the evader can move asynchronously with perfect knowledge, while the pursuers are uncertain about the evaders location. The paper introduces two methods, one provably optimal dynamic programming formulation and an RL-based formulation based on the Equilibrium Policy Generalization (EPG) (Lu et al. 2025). It is shown that these methods are more robust and successful compared to baseline heuristics and general RL methods.", "questions": "1. Can you emphasize the novel aspects of this work compared to Lu et al. (2025a)?\n\nTypos:\n- line 141 and 145: do you mean \"worst-case\" evader?\n- line 262, 264, 269, 333: Pos and belief are set in math mode", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is generally well-written. It appears to be sound (at least as far as I can judge as a non-expert). The one-sided partial observability setting is natural for pursuit-evasion games and treated both theoretically and practically in the paper. The extension of the EPG framework to the partial-observability setting is novel. The simulations show convincing improvements over various baselines.", "weaknesses": "The paper is an extension of Lu et al. (2025a) to the partially observed setting. Both the DP and the EPG approach seem to be slight extensions of this earlier work. The paper does not seem to develop any fundamentally novel techniques. \n\nThe simulations show improvements in comparison with simple baselines and the competing PSRO approach. In particular, Lu et al. (2025a) already reported clear improvements of EPG against the PSRO policies in the cross-graph setting for PEGs and thus the performance improvements appear to mainly stem from the advantages of this framework in this setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AKZGZfoMBo", "reviewer": "Reviewer_9jAS", "summary": "This paper introduces R2PS, a novel algorithm designed to generate worst-case robust strategies for real-time pursuit under partial observability. The authors formulate the pursuit-evasion interaction as a two-player zero-sum game where the pursuer must act with limited information about the evader’s state and policy. By leveraging a lookahead-based game tree, R2PS computes strategies that minimize the maximum possible regret regardless of the evader’s behavior. The method incorporates a pessimistic planning approach over belief states and ensures the pursuer’s strategy remains effective even against adaptive or adversarial evaders. Through empirical evaluation in grid-world environments, the results demonstrate that R2PS significantly outperforms baseline approaches such as QMDP and other belief-based planners in terms of robustness and capture rate, especially under strong observation uncertainty.", "questions": "- R2PS leverages a DP‑guided teacher term, while PSRO does not. This extra signal can improve both sample efficiency and final performance. Do you think the absence of teacher guidance contributes to PSRO’s weaker results in Table 2?\n- Could the authors elaborate on how the real-time lookahead tree is constructed under partial observability? Specifically, how are the belief nodes expanded and pruned, and how does the algorithm manage the exponential growth of possible observation histories?\n- Given that the method involves repeated regret minimization over a belief tree at each step, how does R2PS scale with larger grids or more complex environments? Are there any runtime metrics or profiling results that show it can be deployed in real-time?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Theory–practice bridge: Proves a clean minimax recursion for the DP table and upgrades it to asynchronous evader moves; then embed this belief-preservation mechanism into RL.\n\n- Real-time, cross-graph generalization: The R2PS training scheme yields zero-shot gains on unseen real-world graphs and large runtime advantages over recomputing DP online.", "weaknesses": "- Modelling assumption (no exits): While this choice enables Algorithm 1’s near‑optimal time‑complexity guarantees for Markov PEGs, it departs from many real‑world reach‑avoid settings where evaders succeed by reaching designated exits. R2PS is also based on algorithm 1. The no‑exit assumption may therefore limit practical relevance.\n- Need more baselines: Table 2 compares against PSRO, which is too narrow to convincingly demonstrate the advantage of the proposed method. Moreover, capture rates are limited on several graph, making it unclear whether the graphs are difficult or the R2PS is not good enough. More stronger baselines would clarify this.\n- Ablations on teacher guidance: Given the sparse SAC reward, the DP‑guided teacher signal may be the dominant factor behind R2PS’s performance. Ablations that remove or vary the teacher signal are needed to identify the main source of gains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Lkgd5zZDjz", "reviewer": "Reviewer_U4A6", "summary": "This paper addresses the challenging problem of pursuit-evasion games on graphs under partial observability, adversarial evaders, and real-time decision constraints. The authors propose R2PS, a framework that combines theoretically grounded dynamic programming for worst-case evader modeling with belief-state-based reinforcement learning using GNNs and pointer networks. The method is evaluated on a diverse set of synthetic and real-world graphs, demonstrating strong generalization to unseen environments and outperforming baselines.", "questions": "1) While the belief mechanism is central, the paper lacks ablation studies on how belief is encoded (e.g., histogram vs. learned embedding) or how belief update frequency affects performance. Is the gain primarily from belief averaging, or from the specific network architecture?\n2) Graph construction from real-world locations (e.g., “Downtown Map”) lacks methodological detail: How were nodes/edges extracted from Google Maps? What’s the granularity?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Well-Motivated and Practical Problem:\n   The focus on partially observable PEGs with worst-case adversaries is highly relevant to real-world security applications. The use of real-world map data (Google Maps, Scotland Yard board game) strengthens the practical grounding.\n\n2. Strong Theoretical Foundation:\n   The paper provides a formal justification for using DP-based evaders under asynchronous move assumptions (Theorem 1), which is non-trivial and crucial for modeling a truly adversarial opponent. This theoretical anchor elevates the work beyond purely empirical RL approaches.\n\n3. Innovative Integration of Belief and RL:\n   The belief preservation mechanism—which maintains a distribution over possible evader locations and integrates it into the policy network—is elegantly designed and effectively addresses partial observability without resorting to full POMDP solvers (which are intractable at scale).\n\n4. Real-Time Feasibility:\n   The use of GNNs + pointer networks enables fast inference, making the approach suitable for deployment—a notable advantage over planning-based POMDP methods.", "weaknesses": "1. Limited Ablation on Belief Representation:\n   While the belief mechanism is central, the paper lacks ablation studies on how belief is encoded (e.g., histogram vs. learned embedding) or how belief update frequency affects performance. Is the gain primarily from belief averaging, or from the specific network architecture?\n\n2. Scalability Beyond ~200 Nodes Unclear:\n   All test graphs have ≤231 nodes. It’s unclear how R2PS scales to larger urban or infrastructure networks (e.g., city-scale road graphs with 10⁴–10⁵ nodes). GNNs may suffer from over-smoothing or memory bottlenecks.\n\n3. Assumption on Evader Observability:\n   The DP evader is assumed to have global observation, which is realistic for a worst-case adversary. However, the paper does not explore asymmetric information settings where the evader also has limited sensing—a more balanced and arguably more realistic scenario.\n\n4. Reproducibility Concerns:\n   Graph construction from real-world locations (e.g., “Downtown Map”) lacks methodological detail: How were nodes/edges extracted from Google Maps? What’s the granularity?\n\n5. Comparison to Modern MARL Methods:\n   While Grasper and EPG are cited, the paper does not compare against recent multi-agent RL baselines that handle partial observability (e.g., QMIX, MAVEN, or RODE). It’s unclear whether the gains are due to the belief mechanism or simply better architecture.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)