Minimax Training Closes the Reconnaissance Gap in Learned Network-Robustness Design

<title>Abstract</title> <p>Reinforcement learning (RL) agents can discover network topologies substantially more robust to targeted attack than classical heuristics produce, and a 2026 study reported such agents spontaneously discover "multi-backbone" structures. Every method in this line of work, learned or heuristic, is trained and evaluated against a single, fixed attack strategy chosen in advance, leaving open whether a design that excels against one attack survives an adversary who reconnoiters the topology and adapts. We introduce a minimax training objective that optimizes a network-redesign agent against the worst of a small attack portfolio, recomputed at every training step, instead of one fixed attack. Across three topology families (Barabási–Albert, Erdős–Rényi, Watts–Strogatz) and eight seeds per family (168 runs), we compare this co-adaptive paradigm against the standard single-attack paradigm, instantiated with a graph-neural-network policy trained via actor-critic RL and with simulated annealing. Minimax training reduces an "Adaptive Degradation Gap" – robustness lost when an attacker switches from the trained-against strategy to its most damaging alternative – by 74–81% (Wilcoxon signed-rank, n=24, Holm-corrected p&lt;0.001, rank-biserial r≈0.94–1.0), while achieving higher worst-case robustness. Optimizer choice makes no significant difference once the objective is fixed. The effect replicates directionally on real US power-grid subgraphs, generalizes to three unseen attack types, is driven specifically by including betweenness attack in training rather than by portfolio size, and persists at double the network scale. The contribution is conceptual rather than architectural: the training objective, not the optimizer, determines whether learned network-robustness design is brittle or robust to a realistic, reconnaissance-capable adversary.</p>