R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability

Dongbin Zhao; Runyu Lu; Ruochuan Shi; Yuanheng Zhu

arxiv: 2511.17367 · v2 · pith:ZYGI7GDFnew · submitted 2025-11-21 · 💻 cs.LG

R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability

Runyu Lu , Ruochuan Shi , Yuanheng Zhu , Dongbin Zhao This is my paper

Pith reviewed 2026-05-17 20:15 UTC · model grok-4.3

classification 💻 cs.LG

keywords pursuit-evasion gamespartial observabilityreinforcement learningrobust strategiesgraph neural networkszero-shot generalizationdynamic programmingasynchronous moves

0 comments

The pith

Belief preservation extends dynamic programming to partial observability for real-time robust pursuit policies.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops the first method for worst-case robust real-time pursuit strategies in graph-based pursuit-evasion games when pursuers hold only imperfect information about the evader. It first proves that a dynamic programming algorithm for Markov games preserves optimality even under asynchronous evader moves. A belief preservation mechanism then tracks the set of possible evader positions, allowing the dynamic programming strategies to operate under partial observability. The mechanism is embedded in an equilibrium policy generalization framework so that reinforcement learning produces a graph neural network policy trained across multiple graphs against asynchronous dynamic programming evaders. If correct, the resulting policy runs in real time and delivers zero-shot generalization to unseen graphs while outperforming policies trained directly on those graphs by prior reinforcement learning methods.

Core claim

The paper introduces R2PS as the first approach to worst-case robust real-time pursuit strategies under partial observability. It proves that a traditional dynamic programming algorithm for solving Markov PEGs maintains optimality under the asynchronous moves by the evader. A belief preservation mechanism about the evader's possible positions extends the DP pursuit strategies to a partially observable setting. Embedding the belief preservation into the state-of-the-art EPG framework produces a real-time pursuer policy through cross-graph reinforcement learning against the asynchronous-move DP evasion strategies. After reinforcement learning, the policy achieves robust zero-shot general

What carries the argument

The belief preservation mechanism, which maintains information about the evader's possible positions to extend dynamic programming strategies from full observability to partial observability while preserving worst-case robustness.

If this is right

The policy operates in real time on graph-based pursuit-evasion problems with imperfect information.
The policy generalizes zero-shot to previously unseen real-world graph structures.
The policy consistently outperforms policies trained directly on the test graphs using prior game reinforcement learning approaches.
The approach retains the optimality properties of dynamic programming in the presence of asynchronous evader moves.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same belief preservation step could support extension to multi-evader settings by expanding the tracked position set.
Testing the policy on graphs with systematically varied connectivity or size would provide a concrete check on the claimed generalization.
The real-time property opens application to online security tasks such as dynamic area monitoring where full information is unavailable.

Load-bearing premise

The belief preservation mechanism successfully extends the optimality properties of the dynamic programming strategies to the partially observable setting while preserving worst-case robustness against asynchronous evader moves.

What would settle it

A direct comparison showing that the learned policy either fails to outperform a policy trained directly on the target graphs by existing game RL methods or exhibits no reliable zero-shot generalization when tested on a collection of unseen real-world graph structures.

Figures

Figures reproduced from arXiv: 2511.17367 by Dongbin Zhao, Runyu Lu, Ruochuan Shi, Yuanheng Zhu.

**Figure 2.** Figure 2: Pursuit Initialization under Limited Observation Range (Nodes with Blue Outlines) [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗

**Figure 3.** Figure 3: Pursuit Illustration under Belief Preservation (Shadowed Area around Evader) [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗

**Figure 4.** Figure 4: Cross-Graph Learning Curves of Generalized Pursuer Policies [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗

**Figure 5.** Figure 5: Illustration of Test Graphs (Starting from Scotland-Yard Map) [PITH_FULL_IMAGE:figures/full_fig_p022_5.png] view at source ↗

**Figure 6.** Figure 6: Scaling Plots of RL and DP Inference Time [PITH_FULL_IMAGE:figures/full_fig_p024_6.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves a DP result for asynchronous evader moves in full-information Markov PEGs and folds a belief-preservation step into the EPG framework to reach partial observability, but the worst-case guarantee does not obviously survive the extension.

read the letter

The clearest new piece is the claim that a standard dynamic-programming algorithm for Markov pursuit-evasion games stays optimal when the evader is allowed asynchronous moves. That is a modest but concrete clarification of existing DP methods. The second step—introducing a belief-preservation mechanism so that the same strategies can be used under partial observability—is presented as a direct lift, and the whole construction is then dropped into the EPG cross-graph RL pipeline to produce a real-time GNN policy. If the belief step works as described, the result is a practical route to policies that generalize across unseen graphs without retraining on each one.

Referee Report

2 major / 2 minor

Summary. The paper introduces R2PS for computing worst-case robust real-time pursuit strategies in graph-based pursuit-evasion games (PEGs) under partial observability. It first proves that a standard dynamic programming (DP) algorithm for Markov (full-information) PEGs remains optimal under asynchronous evader moves. It then proposes a belief-preservation mechanism to lift these strategies to the partially observable setting and embeds the construction inside the Equilibrium Policy Generalization (EPG) reinforcement-learning framework, training graph neural network policies via cross-graph RL against the asynchronous DP evasion strategies. The central empirical claim is that the resulting policy achieves robust zero-shot generalization to unseen real-world graph structures and outperforms policies trained directly on the test graphs by existing game RL methods.

Significance. If the belief-preservation step correctly inherits the min-max optimality and worst-case robustness of the underlying DP strategies, the work would constitute a meaningful extension of EPG-style methods to the partial-observability regime that is common in security applications. The explicit proof that the DP algorithm remains optimal under asynchronous moves is a concrete technical contribution that could be reused beyond the RL setting.

major comments (2)

The manuscript states that the belief-preservation mechanism extends the DP pursuit strategies to the partially observable case while preserving worst-case robustness, yet supplies no separate proof, value-function bound, or inductive argument showing that the min-max guarantee is maintained once the evader can condition on both the pursuers’ policy and the current belief state. Because the zero-shot generalization and outperformance claims rest on the learned policy inheriting this robustness, the absence of such a guarantee is load-bearing for the central contribution.
The integration into the EPG framework is described at a high level; it is unclear whether the belief update is performed inside the GNN policy network or as an external state augmentation, and whether the resulting state representation remains Markovian with respect to the worst-case value function derived from the DP step.

minor comments (2)

Notation for the belief state and the asynchronous-move transition is introduced without an explicit comparison to the standard POMDP belief update; a short table or paragraph contrasting the two would improve readability.
The abstract and introduction refer to “real-world graph structures,” but the experimental section should explicitly list the families of graphs used for training versus testing and report the precise metrics (e.g., capture time, success rate) that support the “consistently outperforms” claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the referee's insightful comments. We address the major concerns regarding the formal guarantees of the belief-preservation mechanism and the details of its integration into the EPG framework. We will revise the manuscript to include additional proofs and clarifications as detailed below.

read point-by-point responses

Referee: The manuscript states that the belief-preservation mechanism extends the DP pursuit strategies to the partially observable case while preserving worst-case robustness, yet supplies no separate proof, value-function bound, or inductive argument showing that the min-max guarantee is maintained once the evader can condition on both the pursuers’ policy and the current belief state. Because the zero-shot generalization and outperformance claims rest on the learned policy inheriting this robustness, the absence of such a guarantee is load-bearing for the central contribution.

Authors: We acknowledge that a formal proof of min-max optimality preservation under the belief-preservation mechanism was not provided in the original submission. The mechanism works by maintaining a belief set over possible evader positions and selecting the DP-derived action that is optimal against the worst-case position in the belief. To address this, we will add an inductive argument in the revised manuscript showing that if the DP strategy is min-max optimal for full information, then applying it to the belief state preserves the worst-case robustness even when the evader conditions on the belief and the policy. This will support the generalization claims. revision: yes
Referee: The integration into the EPG framework is described at a high level; it is unclear whether the belief update is performed inside the GNN policy network or as an external state augmentation, and whether the resulting state representation remains Markovian with respect to the worst-case value function derived from the DP step.

Authors: We clarify that the belief update is computed externally as a state augmentation: the belief distribution is updated based on observations and then concatenated as input features to the GNN policy. This design keeps the overall state Markovian with respect to the worst-case value function, because the belief encapsulates the necessary history, and the value function is defined over the belief states derived from the DP. We will expand the description in Section 4 with pseudocode and a figure to make this explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on explicit proof and new mechanism

full rationale

The paper states it first proves DP optimality under asynchronous moves, then proposes a belief preservation mechanism to extend strategies to partial observability, and finally embeds the result into the EPG framework for RL training. No quoted step reduces a claimed prediction or optimality guarantee to a fitted input, self-definition, or unverified self-citation chain by construction. The central robustness and generalization claims are presented as outcomes of the RL process against the DP-based evader, with the extension treated as a proposed mechanism rather than a tautological renaming or fit. This is a standard self-contained construction against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Review is based solely on the abstract; specific free parameters, axioms, and invented entities cannot be extracted in detail. The paper appears to rely on standard Markov PEG assumptions and introduces belief preservation as a new mechanism.

axioms (1)

domain assumption Traditional dynamic programming algorithm for Markov PEGs maintains optimality under asynchronous evader moves
Stated as proved in the paper for the base case before extension to partial observability.

invented entities (1)

belief preservation mechanism no independent evidence
purpose: Tracking possible evader positions to extend DP strategies to partial observability
Introduced to handle imperfect information; no independent evidence provided in abstract.

pith-pipeline@v0.9.0 · 5579 in / 1392 out tokens · 83941 ms · 2026-05-17T20:15:50.816748+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages · 1 internal anchor

[1]

Self-learning exploration and mapping for mobile robots via deep reinforcement learning

Fanfei Chen, Shi Bai, Tixiao Shan, and Brendan Englot. Self-learning exploration and mapping for mobile robots via deep reinforcement learning. InAiaa scitech 2019 forum, pp. 0396,

work page 2019
[2]

arXiv:1910.07207 [cs, stat] , author =

Petros Christodoulou. Soft actor-critic for discrete action settings.arXiv preprint arXiv:1910.07207,

work page arXiv 1910
[3]

Soft Actor-Critic Algorithms and Applications

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:1812.05905,

work page internal anchor Pith review Pith/arXiv arXiv
[4]

Pursuit-evasion games with unmanned ground and aerial vehicles

Rene Vidal, Shahid Rashid, Cory Sharp, Omid Shakernia, Jin Kim, and Shankar Sastry. Pursuit-evasion games with unmanned ground and aerial vehicles. InProceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164), volume 3, pp. 2948–2955. IEEE,

work page 2001
[5]

Solving urban network security games: Learning platform, benchmark, and challenge for AI research.arXiv preprint arXiv:2501.17559,

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,

work page arXiv
[6]

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). Theref...

work page 2080
[7]

(Lu et al., 2025a) shows that an expansion-based dynamic programming algorithm can solve Markov PEGs under a near-optimal time complexity

considers the case where the pursuers only have partial observation and provides a dynamic programming algorithm in the form of value iteration for finding Nash equilibrium. (Lu et al., 2025a) shows that an expansion-based dynamic programming algorithm can solve Markov PEGs under a near-optimal time complexity. Recent works (Xue et al., 2021,

work page 2021
[8]

proposes a 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 completely novel paradigm to learn generalized policies across the underlying structures of PEGs through the construction of equilibrium oracles, guaranteeing robust ...

work page 1987

[1] [1]

Self-learning exploration and mapping for mobile robots via deep reinforcement learning

Fanfei Chen, Shi Bai, Tixiao Shan, and Brendan Englot. Self-learning exploration and mapping for mobile robots via deep reinforcement learning. InAiaa scitech 2019 forum, pp. 0396,

work page 2019

[2] [2]

arXiv:1910.07207 [cs, stat] , author =

Petros Christodoulou. Soft actor-critic for discrete action settings.arXiv preprint arXiv:1910.07207,

work page arXiv 1910

[3] [3]

Soft Actor-Critic Algorithms and Applications

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:1812.05905,

work page internal anchor Pith review Pith/arXiv arXiv

[4] [4]

Pursuit-evasion games with unmanned ground and aerial vehicles

Rene Vidal, Shahid Rashid, Cory Sharp, Omid Shakernia, Jin Kim, and Shankar Sastry. Pursuit-evasion games with unmanned ground and aerial vehicles. InProceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164), volume 3, pp. 2948–2955. IEEE,

work page 2001

[5] [5]

Solving urban network security games: Learning platform, benchmark, and challenge for AI research.arXiv preprint arXiv:2501.17559,

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,

work page arXiv

[6] [6]

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). Theref...

work page 2080

[7] [7]

(Lu et al., 2025a) shows that an expansion-based dynamic programming algorithm can solve Markov PEGs under a near-optimal time complexity

considers the case where the pursuers only have partial observation and provides a dynamic programming algorithm in the form of value iteration for finding Nash equilibrium. (Lu et al., 2025a) shows that an expansion-based dynamic programming algorithm can solve Markov PEGs under a near-optimal time complexity. Recent works (Xue et al., 2021,

work page 2021

[8] [8]

proposes a 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 completely novel paradigm to learn generalized policies across the underlying structures of PEGs through the construction of equilibrium oracles, guaranteeing robust ...

work page 1987