Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (2) · 1668-1675
DOI: 10.1609/aaai.v40i2.37144 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Shuxin Zhuang und 4 weiteren Autor:innen.
Abstract (Originalsprache)
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 that limit 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 Tree-based Stochastic Optimization (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.
Zitieren
APA
Zhuang, S., Meng, L., Li, S., Li, M., & Zhang, Y. (2026). Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games. Proceedings of the AAAI Conference on Artificial Intelligence, 40(2), 1668-1675. https://doi.org/10.1609/aaai.v40i2.37144
Vancouver
Zhuang S, Meng L, Li S, Li M, Zhang Y. Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(2):1668-1675. doi:10.1609/aaai.v40i2.37144
BibTeX
@article{Zhuang2026,
author = {Zhuang, Shuxin and Meng, Linjian and Li, Shuxin and Li, Minming and Zhang, Youzhi},
title = {Tree-Based Stochastic Optimization for Solving Large-Scale Urban Network Security Games},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {2},
pages = {1668--1675},
doi = {10.1609/aaai.v40i2.37144}
}
EUVIMED