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

arXiv: https://arxiv.org/abs/2511.17367 · HTML: https://mlsanity.com/paper/2511.17367/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Adversarial robustness and RL in finance, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 37 references that are in the map.
- First posted on arXiv 21 Nov 2025.

## Placed in

- Deep reinforcement learning methods / [Adversarial robustness and RL in finance](https://mlsanity.com/deeprl/adversarial-robustness-and-rl-in-finance/)

## Builds on (most cited first, 17 of 17)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Soft Actor-Critic Algorithms and Applications](https://mlsanity.com/paper/1812.05905/) (2018)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training](https://mlsanity.com/paper/2501.17161/) (2025)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Soft Actor-Critic for Discrete Action Settings](https://mlsanity.com/paper/1910.07207/) (2019)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [ARiADNE: A Reinforcement learning approach using Attention-based Deep Networks for Exploration](https://mlsanity.com/paper/2301.11575/) (2023)
- [Empowering Multi-Robot Cooperation via Sequential World Models](https://mlsanity.com/paper/2509.13095/) (2025)
- [Solving Large-Scale Extensive-Form Network Security Games via Neural Fictitious Self-Play](https://mlsanity.com/paper/2106.00897/) (2021)
- [Grasper: A Generalist Pursuer for Pursuit-Evasion Problems](https://mlsanity.com/paper/2404.12626/) (2024)
- [Dynamic Programming for One-Sided Partially Observable Pursuit-Evasion Games](https://mlsanity.com/paper/1606.06271/) (2016)
- [NSGZero: Efficiently Learning Non-Exploitable Policy in Large-Scale Network Security Games with Neural Monte Carlo Tree Search](https://mlsanity.com/paper/2201.07224/) (2022)
- [Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games](https://mlsanity.com/paper/2511.00811/) (2025)
- [GraphChase: A Platform and Benchmark for Urban Network Security Games](https://mlsanity.com/paper/2501.17559/) (2025)

## Abstract (arXiv)

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.