Research map / Reinforcement learning / Visual and representation RL
Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Equilibrium Policy Generalization (EPG), training an RL pursuit-evasion policy across many graphs against per-graph equilibrium oracles (a DP algorithm for no-exit graphs, a bipartite-matching heuristic for exit graphs), giving zero-shot cross-graph generalization.
Problem
Pursuit-evasion games on graphs require exponential time to solve exactly, and existing RL methods need recomputation or fine-tuning when the graph structure changes; they also rely on opponent behavior patterns and fail for no-exit graphs.
Approach
Train a cross-graph SAC policy against the single-graph Nash equilibrium opponent (used as adversary and as KL-regularized guidance), with a dynamic-programming equilibrium oracle for no-exit graphs, a grouping extension for many pursuers, a bipartite-matching heuristic for exit graphs, and shortest-path distance node features with an attention sequence model.
Key results
- With 2 pursuers in no-exit real-world graphs, the RL pursuer trained by EPG keeps pursuit success rates of 0.60 to 1.00 against the DP evader, versus 0.02 to 0.81 for the shortest path strategy.
- In 8-exit PEGs with 5 pursuers, zero-shot performance under unseen Grid Map and Scotland-Yard Map is 0.637 and 0.652, outperforming the zero-shot starting points of Grasper and MT-PSRO.
- The DP oracle runs in about 10 seconds on a 500-node 2-pursuer graph on a single CPU core.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add equilibrium guidance to SAC training (ablation) | EPG pursuer · unseen Dungeon maps, no-exit | termination timestep | Helped |
| add the SAC reward loss alongside equilibrium guidance (ablation) | EPG pursuer · unseen Dungeon maps, no-exit | termination timestep | Helped |
| use shortest-path distance features instead of 2D positions and agent indicators (ablation) | EPG policy · unseen Dungeon maps, no-exit | termination timestep | Helped |
| replace the equilibrium-guided SAC objective with SAC loss only (ablation) | EPG pursuer · unseen Dungeon maps, no-exit | termination timestep | Hurt |
| remove the SAC reward loss and retain supervised equilibrium guidance (ablation) | EPG pursuer · unseen Dungeon maps, no-exit | termination timestep | Hurt |
| replace shortest-path distance features with 2D positions and agent indicators (ablation) | EPG policy · unseen Dungeon maps, no-exit | termination timestep | Hurt |
| train EPG pursuer against DP rather than use shortest-path strategy | 2-pursuer no-exit PEG · Scotland-Yard Map | pursuit success rate: $0.17$ -> $0.99$ | Helped |
| train EPG pursuer against DP rather than use shortest-path strategy | 2-pursuer no-exit PEG · Hollywood Walk of Fame | pursuit success rate: $0.02$ -> $0.62$ | Helped |
| train EPG pursuer for cross-graph zero-shot use instead of relying on fine-tuned baseline policies | 5-pursuer EPG pursuer · Grid Map and Scotland-Yard Map, 8-exit | zero-shot performance: $0.637$ for Grid Map and $0.652$ for Scotland-Yard Map | Helped |
Surprising findings
- Only Grasper on Scotland-Yard Map matches the zero-shot EPG pursuer after a 10-minute PSRO fine-tuning.
- RL pursuers can outperform the pure-strategy DP pursuer when pursuit is not globally guaranteed.
Limitations
- Only perfect-information games are considered; partially observable settings are not studied.
- Best-response opponents trained against EPG policies are hard to train and do not clearly outperform DP opponents.
- Multi-exit oracle is a heuristic without optimality guarantees.
Experimental setup
Datasets: Dungeon procedurally generated maps Grid Map Scotland-Yard Map
Benchmarks: Grid Map Scotland-Yard Map Downtown Map Times Square Hollywood Walk of Fame
Metrics: pursuit success rate evasion timestep
Baselines: Grasper MT-PSRO MT-PSRO-Aug shortest path strategy PSRO
Builds on: soft actor-critic Grasper PSRO pointer network value decomposition networks
Closest papers by meaning
- R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability (ICLR 2026 · similarity 0.91)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.88)
- Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium (ICML 2025 · similarity 0.87)
- Learning Mean Field Games on Sparse Graphs: A Hybrid Graphex Approach (ICLR 2024 · similarity 0.87)
- Provable Zero-Shot Generalization in Offline Reinforcement Learning (ICML 2025 · similarity 0.86)
- Robust Adversarial Reinforcement Learning via Bounded Rationality Curricula (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.