Learned pursuit policies are now judged by how well they transfer zero-shot to graphs they never saw in training. In these games, pursuers chase an evader across a network, and the policies are neural networks trained on many maps and then run unchanged on new ones. The evidence for transfer comes from a handful of test maps, each reported as one success rate. The overall verdict is reached informally, the way a narrative review averages studies it cannot formally pool. Medical evidence synthesis faced the same problem long ago. When studies differ in population and in how they define the outcome, a single pooled number misleads. The honest summary is an estimate of how much results vary between studies, a model of what explains that variation, and a prediction interval for the next study. This proposal brings that discipline to cross-graph pursuit. Each graph becomes a "study." The variables used to explain its result are the structural graph parameters that complexity theory has shown to govern whether the game is exactly solvable.
The payoff runs in two directions. For the learning side, we replace "works on most maps" with a calibrated statement: on a new graph with these structural properties, expect capture rates in this interval. For the complexity side, we get a first empirical test of whether the parameters that make exact solving tractable, such as vertex cover number, pathwidth, and the gap between monotone and non-monotone search, also predict where learned heuristics break. Theory is silent on that question.
Core Claim
We claim that the between-graph variation in zero-shot performance of current learned pursuers is large. We further claim that most of it is explained by structural parameters drawn from pursuit-evasion complexity theory, not by graph size or diameter. The sharpest version of the hypothesis concerns recontamination, meaning letting the evader re-enter regions already searched. Recontamination Helps a Lot to Hunt a Rabbit proves two relevant facts. First, the monotone hunter number, which counts searchers when no cleared region may be re-entered, is pinned between pathwidth and pathwidth plus one. Second, there are trees where two hunters suffice if recontamination is allowed but arbitrarily many are needed otherwise. We predict that learned policies behave like monotone searchers. If so, their failures will concentrate on graphs where the gap between the monotone and non-monotone hunter numbers is large. That is a specific, falsifiable link between a theorem and a learned system's failure pattern.
Prior Work and How This Differs
Two papers supply the systems under study. Equilibrium Policy Generalization trains an attention model on shortest-path distance matrices, regularized toward an exact dynamic-programming equilibrium. It is trained on 152 procedural Dungeon maps and reports zero-shot results on 10 unseen graphs. R2PS handles partial observability by having pursuers track a probability distribution over where the evader might be, and trains graph neural networks with Soft Actor-Critic. Both evaluate on a small, unstratified set of maps, and each defines success differently. EPG measures success against a dynamic-programming evader and also under a two-pursuer surround rule. R2PS measures success against a best-responding evader and across varied sensing ranges. Neither models why performance varies across maps. We do not propose a better pursuer. We propose the evaluation and explanation layer these papers lack.
The complexity literature supplies both the explanatory variables and exact ground truth. On tractability of Cops and Robbers game shows that computing the cop number is NP-hard and W[2]-hard in the number of cops. That rules out team size as a usable difficulty knob. Parameterized Analysis of the Cops and Robber Game shows the problem becomes tractable when parameterized by vertex cover number, with small kernels for neighborhood diversity and cluster vertex deletion. Hunting a rabbit is hard shows that the invisible-evader hunting number is NP-hard even on bipartite graphs. The Dissaux et al. line supplies polynomial algorithms on trees, split graphs, and cographs, plus tractability in vertex cover number. These results tell us which families admit exact optimal values at the scale we need. They also tell us which structural quantities are the natural candidates for explaining variation. That is the methodological role of the complexity direction here.
The study-heterogeneity literature supplies the lens, and also a warning. PyHealth documents how inconsistent definitions of a task, such as how mortality is computed, make deep-learning results incomparable across papers. Cross-graph pursuit has the same problem: "success rate" changes meaning with the evader model, the win condition, and the observation range. Meta-analytic practice also teaches that when outcomes are too discordant, pooling should be abandoned rather than forced. We therefore standardize outcome definitions before any pooling. We will report when heterogeneity is too large to summarize, instead of hiding it in an average. We are aware of no prior work that applies random-effects meta-regression to cross-environment evaluation of learned game policies, or that ties its explanatory variables to parameterized complexity.
Research Program
The first component is a stratified graph population with exact ground truth. We start from the Dungeon corpus and the 10-graph real-world suite used by EPG and R2PS. We add generated families chosen because exact values are computable on them. These are trees, cographs, split graphs, graphs with small vertex cover number, and grids. Trees and cographs come with polynomial algorithms for monotone hunting. Low vertex cover graphs come with FPT exact solvers. Grids are included because their exact hunter numbers are open, so they act as a held-out family with no oracle. For the visible-evader cops game we compute exact values by standard dynamic programming over joint positions, which is feasible at our sizes for small team counts. For the invisible-evader game, dynamic programming over sets of possibly-contaminated vertices is exponential in graph size. Here the structural algorithms are what make ground truth available, and on small trees we compute the non-monotone hunter number by brute force. For every graph we record vertex cover number, pathwidth (exact on small graphs, upper bounds otherwise), neighborhood diversity, the cop or hunter number, and on trees the monotone-minus-non-monotone gap. We also record size, diameter, and average degree as nuisance covariates.
The second component is a standardized outcome. For each graph we run the released EPG and R2PS policies under one fixed protocol. That protocol fixes the evader model (exact optimal where computable, best-response-trained otherwise), the win condition, and the observation range. We record two quantities. The first is capture rate. The second is the ratio of the policy's capture time to the optimal capture time, which is defined only where an exact oracle exists. Each graph then yields an effect estimate with a within-graph standard error, computed from repeated episodes over random starting positions.
The third component is the analysis. We fit a random-effects meta-regression. Here $y_g$ is the logit capture rate on graph $g$ and $x_g$ its covariate vector:
$$y_g = x_g^\top \beta + u_g + \epsilon_g, \qquad u_g \sim N(0, \tau^2), \quad \epsilon_g \sim N(0, s_g^2),$$
In this model, $\tau^2$ is the true between-graph variance and $s_g^2$ is the known episode-sampling variance on graph $g$. The quantities of interest are three. One is the share of $\tau^2$ removed when complexity parameters are added on top of the nuisance covariates. Another is the coefficient on the recontamination gap. The last is whether the model's prediction intervals cover performance on held-out graph families at the stated rate.
Baselines
The naive reference point is current practice: an unweighted mean success rate over the evaluation maps, with no between-graph variance and no covariates. We run it on exactly the same per-graph outcomes. It "beats" nothing. It is the summary whose prediction-interval coverage on held-out families we expect to be poor, and we report how poor.
The strongest competitor for explaining variation is a size-and-geometry model. This is the same random-effects meta-regression using only node count, diameter, and average degree. It is the explanation a skeptic would reach for first, it costs nothing, and size alone correlates with most structural parameters. It is fit on the same graphs with the same within-graph standard errors and the same cross-validation folds. Our claim is supported only if adding the complexity parameters reduces residual between-graph variance by a clearly non-trivial share. We will pre-register a threshold of at least a quarter of the variance remaining after the size model. It must also improve held-out-family coverage, with the size model's residual variance as the comparison point.
A learned-difficulty competitor regresses performance on a pooled graph-neural-network embedding of each graph. It is trained with the same folds and a matched hyperparameter search budget. It may predict better than our model, and that would be informative. However, it explains nothing about which property drives failure. We count our approach as competitive if it comes within a small margin of the embedding's held-out error while using a handful of interpretable variables.
For the pursuers themselves, the strongest reported numbers from EPG are a 1.0 success rate on the Grid map and 0.98 on Times Square against an optimal dynamic-programming evader. EPG also reports "over 60% across most maps" under the two-pursuer surround condition, where standard dynamic programming drops to near zero. R2PS reports ">50% success rates on most maps" against a best-responding evader. Our standardized protocol should reproduce these on the original maps before any extension; a failure to reproduce would itself be a finding about outcome-definition heterogeneity. The key ablation removes the recontamination-gap covariate on the tree family, which isolates whether that specific theorem-derived quantity carries explanatory weight.
Why not just…?
Why not just report per-graph results and plot them against graph size? If size explains the variation, that is the right answer, and the size-and-geometry baseline exists to find out. The reason to expect otherwise is the Dissaux et al. construction: trees in the same size range can need two hunters or arbitrarily many, depending on whether recontamination is allowed. Size cannot see that difference. If the tree-family ablation shows no added explanatory power from the gap, we drop the claim.
Why not just compute exact dynamic-programming values everywhere and skip the parameterized algorithms? For the visible-evader game at the scale of the Dungeon maps, we do exactly that. This is a real simplification, and we take it. It does not extend to the invisible-evader game, whose natural state space is sets of contaminated vertices and grows exponentially. R2PS also reports dynamic programming taking over two minutes per decision on graphs of about 1,000 nodes even in its simpler setting. The structural algorithms are the only route to ground-truth optimality gaps for the invisible-evader game beyond toy sizes.
Why not just evaluate against a best-response evader, as R2PS does, since worst case is what matters? Best-response evaluation gives a sharper per-graph number, and we adopt it as an outcome wherever no exact oracle exists. It does not answer the cross-graph question of which graphs a policy will fail on before training an adversary for each one. The meta-regression answers that question, and its prediction interval is what a practitioner deploying on a new map would actually use.
Proposed Experiments
The first experiment is a reproduction and standardization pass. We reproduce the EPG and R2PS headline numbers under their own definitions on the original maps. We then re-score the same maps under the single standardized protocol and quantify how much the reported conclusions move. This directly measures outcome-definition heterogeneity.
The second experiment is the main meta-regression over the stratified population. Folds are split by graph family, not by graph, so held-out coverage tests extrapolation to new structural regimes. Grids are always held out because they have no oracle.
The third and decisive check is the recontamination test on trees. We generate size-matched trees spanning a wide range of the monotone-minus-non-monotone gap and give both policies the non-monotone optimal team size. We then test whether capture rate falls with the gap after controlling for size and pathwidth. A clear negative slope would show that learned pursuers inherit the monotone bottleneck the theorem describes. That result would motivate training against recontaminating strategies explicitly. A flat slope would show the theorem does not predict learned behavior, which matters equally for anyone using complexity results to choose benchmarks.
References
- Recontamination Helps a Lot to Hunt a Rabbit
- Equilibrium Policy Generalization: A Reinforcement Learning Framework for Cross-Graph Zero-Shot Generalization in Pursuit-Evasion Games
- R2PS: Worst-Case Robust Real-Time Pursuit Strategies under Partial Observability
- On tractability of Cops and Robbers game
- Parameterized Analysis of the Cops and Robber Game
- Hunting a Rabbit Is Hard
- PyHealth: A Deep Learning Toolkit for Healthcare Applications