Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games
Shuxin Zhuang, Linjian Meng, Shuxin Li, Minming Li, Youzhi Zhang · 2025
Read Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games by Shuxin Zhuang, Linjian Meng, Shuxin Li, Minming Li, Youzhi Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-10072.txt.
Introduction
Shuxin Zhuang, Linjian Meng, Shuxin Li, Minming Li, and Youzhi Zhang tackle urban network security games, where defenders allocate scarce patrol resources across a city road network against an adversary. Finding a Nash equilibrium is hard because the action space is enormous and combinatorial. Standard oracle approaches need best responses each round, and computing them exactly is impractical at this scale.
Their approach, Tree-based Stochastic Optimization, maps the whole action space onto a tree that neural networks can represent. It then folds that representation into a loss shown equivalent to the unbiased loss used for equilibrium finding. A sample-and-prune step reduces the risk of settling into poor local optima. Tests showed the method beating baseline methods on these large security games.
Catalog record
| CREATOR | Shuxin Zhuang, Linjian Meng, Shuxin Li, Minming Li, Youzhi Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-10072
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games Shuxin Zhuang, Linjian Meng, Shuxin Li, Minming Li, Youzhi Zhang Abstract Urban Network Security Games (UNSGs), which model the strategic allocation of limited security resources on city road networks, are critical for urban safety. However, finding a Nash Equilibrium (NE) in large-scale UNSGs is challenging due to their massive and combinatorial action spaces. One common approach to addressing these games is the Policy-Space Response Oracle (PSRO) framework, which requires computing best responses (BR) at each iteration. However, precisely computing exact BRs is impractical in large-scale games, and employing reinforcement learning to approximate BRs inevitably introduces errors, which limits the overall effectiveness of the PSRO methods. Recent advancements in leveraging non-convex stochastic optimization to approximate an NE offer a promising alternative to the burdensome BR computation. However, utilizing existing stochastic optimization techniques with an unbiased loss function for UNSGs remains challenging because the action spaces are too vast to be effectively represented by neural networks. To address these issues, we introduce T ree-based S tochastic O ptimization (TSO), a framework that bridges the gap between the stochastic optimization paradigm for NE-finding and the demands of UNSGs. Specifically, we employ the tree-based action representation that maps the whole action space onto a tree structure, addressing the challenge faced by neural networks in representing actions when the action space cannot be enumerated. We then incorporate this representation into the loss function and theoretically demonstrate its equivalence to the unbiased loss function. To further enhance the quality of the converged solution, we introduce a sample-and-prune mechanism that reduces the risk of being trapped in suboptimal local optima. Extensive experimental results indicate the superiority of TSO over other baseline algorithms in addressing the UNSGs. 1 Introduction The strategic allocation of limited security resources is crucial for public safety, with applications focused on preventing, deterring, and detecting illicit activities to enhance urban security ( Tsai et al. 2010 ; Jain et al. 2011 ; Jain, Conitzer, and Tambe 2013 ; Iwashita et al. 2016 ; Zhang et al. 2017 ; Zhang et al. 2019 ; Li et al. 2024 ) . Many real-world security challenges, including the protection of critical infrastructure ( Jain et al. 2011 ) and the interdiction of urban criminals ( Zhang et al. 2017 ; Zhang et al. 2019 ; Xue et al. 2021 ) , can be effectively modeled as UNSGs. In these games, a team of defender strategically deploys resources, such as police patrols or security checkpoints, across a city’s road network to interdict the adversary. The adversary, in turn, aims to traverse the network from a source to a destination while minimizing the probability of being caught. However, a fundamental challenge in solving UNSGs lies in their computational complexity. As urban networks scale, the exponential growth of possible adversary paths and defender resource allocations leads to massive action spaces ( Jain et al. 2011 ) , making exact solutions computationally intractable. A prominent line of research for solving UNSGs relies on iterative and oracle-based algorithms to approximate a Nash equilibrium (NE) ( Nash 1951 ; McMahan, Gordon, and Blum 2003 ; Jain et al. 2011 ) . A foundational method in this domain is the double-oracle algorithm ( McMahan, Gordon, and Blum 2003 ; Jain et al. 2011 ; Zhang et al. 2017 ; Zhang et al. 2019 ) . It begins with a small, restricted set of pure strategies for each player. In each iteration, it computes an equilibrium for this restricted game and then expands the strategy sets by adding each player’s best response (BR) to the opponent’s current strategy. This process continues until convergence. While the classic double-oracle algorithm relies on linear programming, it loses its effectiveness in large-scale UNSGs. To overcome this limitation, PSRO ( Lanctot et al. 2017 ) was introduced as a generalization of the double-oracle framework, embedding deep reinforcement learning (DRL) to handle immense strategy spaces, and it inherits the convergence guarantees of the double-oracle method. However, a critical bottleneck shared by these approaches is their dependence on best-response computation. Finding a best response in UNSGs is an NP-hard problem ( Jain et al. 2011 ) . Indeed, recent work ( Xue et al. 2021 ; Xue, An, and Yeo 2022 ; Li et al. 2023 ; Li et al. 2024 ; Zhuang et al. 2025 ) employs DRL to approximate the BR oracle for solving UNSGs, but these RL-based oracles often suffer from low accuracy. The resulting imprecise best responses hamper the effectiveness of PSRO framework, and lead to convergence towards suboptimal policies. In parallel, another line of research ( Gemp et al. 2022 ; Gemp, Marris, and Piliouras 2024 ; Meng et al. 2025 ) , primarily developed for normal-form games, reframes the NE-finding problem as a non-convex stochastic optimization task. In this paradigm, a loss function is constructed whose minimization corresponds to finding an NE. Player policies, often parameterized as neural networks, are then updated directly via gradient descent using batches of data from sampled gameplay, thereby bypassing the need for an explicit BR oracle. While this paradigm is promising, its direct application to large-scale UNSGs remains challenging. Its core mechanism requires representing a player’s policy as an explicit probability distribution over the entire action space to facilitate action sampling. Such an enumeration-based representation becomes intractable in typical UNSGs, where the action space is vast and combinatorial. In this paper, we propose a novel framework, Tree-based Stochastic Optimization (TSO), to solve large-scale UNSGs. Our approach bridges the gap between the stochastic optimization paradigm for NE-finding and the practical demands of large-scale security games. First, we introduce a tree-based action sampling process where each action is mapped to a unique path in a decision tree. This structure decomposes the probability of selecting an action into a product of conditional probabilities at sequential decision points, thereby enabling efficient action sampling without enumerating the full action space. We then incorporate tree-based action representation into the Nash Advantage Loss (NAL) ( Meng et al. 2025 ) and theoretically demonstrate its equivalence to the unbiased loss function. Furthermore, to enhance the quality of the converged solution, we introduce a sample-and-prune mechanism. This technique diversifies exploration by pruning the initially sampled high-probability action and forcing a re-sample from the remaining action space, thereby mitigating the risk of premature convergence to a suboptimal local optimum. Extensive experiments demonstrate that TSO significantly outperforms established baselines in UNSGs with both small and large action spaces. 2 Preliminaries 2.1 Game Definition UNSGs involve a defender strategically placing security resources on city roads to protect against an adversary who selects a path through the city. Following the game definition from ( Jain et al. 2011 ; Tsai et al. 2010 ) , we model the UNSGs on a graph G=(V,E) as a one-shot and simultaneous-move game between an attacker and a team of N defenders. The attacker’s action, a_{\text{attacker}} , is a simple path from a start vertex s\in V_{\text{start}} to a target vertex t\in V_{\text{target}} , with the action space \mathcal{A}_{\text{attacker}} being the set of all such paths. Each defender m\in\{1,\dots,N\} selects an edge e_{m} from their individual action space \mathcal{E}_{m}\subseteq E . The team’s action a_{\text{defender}} is a