Lightweight No-Regret Online Learning in Repeated Stackelberg Security Games

2026-01-01

PRE

Chen, Guanda

Ji, Yiding *

Han, Shuo *

DOI：10.1109/LCSYS.2026.3671784

Original

Original request for help

Save

Abstract

En 中文

This work investigates the problem of learning no regret defender strategies in repeated Stackelberg Security Games (SSGs) against an unknown sequence of attackers. We propose an efficient algorithm that combines the Decomposed Optimal Bayesian Stackelberg Solver (DOBSS) with the online combinatorial optimization algorithm Follow the Perturbed Leader (FPL). Specifically, the optimal strategy is dynamically computed by solving a mixed integer linear programing problem where random perturbation is strategically integrated with historical observations of the attacker sequence. Our algorithm provably achieves no-regret with respect to the optimal hindsight strategy and remains resilient against adversarial attacker sequences, even when an adversary is aware of the defender's algorithmic framework and intentionally selects sequences causing a higher regret. Additionally, we prove that our algorithm achieves exponential reductions in both space and time complexity compared with sub-procedure of baseline methods. Comprehensive empirical studies confirm that our algorithm outperforms baseline methods by achieving lower regret bound and reduced computational cost.

Keywords:

Games

Security

Perturbation methods

Optimization

Heuristic algorithms

Bayes methods

Vectors

Computational modeling

Computational efficiency

Upper bound

Stackelberg security games

mixed integer linear programming

online learning

complexity analysis

game theory

Lightweight No-Regret Online Learning in Repeated Stackelberg Security Games

Abstract

Journal

Organization

Cited Papers

Citing Papers