Abstract
Over the past decades, various theories and algorithms have been developed under the framework of Stackelberg games and part of these innovations have been fielded under the scenarios of national security defenses and wildlife protections. However, one of the remaining difficulties in the literature is that most of theoretical works assume full information of the payoff matrices, while in applications, the leader often has no prior knowledge about the follower’s payoff matrix, but may gain information about the follower’s utility function through repeated interactions. In this paper, we study the problem of learning the optimal leader strategy in Stackelberg (security) games and develop novel algorithms as well as new hardness results.
Introduction
The Stackelberg game model is a cornerstone of strategic interaction, characterizing scenarios where a "leader" commits to a strategy first, and a "follower" responds optimally. This framework has seen significant real-world deployment, particularly in security domains such as airport patrolling and anti-poaching efforts. A persistent gap between theory and practice, however, lies in the assumption of perfect information. While classical algorithms assume the leader knows the follower's payoff matrix, practical applications often require the leader to learn these preferences through repeated interactions.
This work addresses the challenge of learning the optimal commitment strategy when follower payoffs are unknown. We model this as an interaction with a response oracle: the leader proposes a mixed strategy, and the oracle reveals the follower's best response. Our goal is to minimize the number of queries (sample complexity) required to identify the optimal leader strategy.
The SEPARATE-SEARCH Algorithm
We introduce SEPARATE-SEARCH, a geometric algorithm that treats the space of leader strategies as a polytope. The strategy space is partitioned into "feasible regions," each corresponding to a specific best response from the follower. Within each region, the leader's utility is linear, making the optimization problem tractable if the regions are known.
The algorithm maintains and refines two sets of bounds for each follower action $i$:
- Upper Bound ($U_i$): An outer approximation of the feasible region, defined by the intersection of known separating hyperplanes.
- Lower Bound ($L_i$): An inner approximation, defined as the convex hull of points where action $i$ is known to be the best response.
A critical challenge in this geometric approach is the "hidden region" problem. Small feasible regions—where a follower action is optimal only for a tiny subset of leader strategies—can be easily missed by random sampling. SEPARATE-SEARCH overcomes this by systematically exploring the extreme points (vertices) of the upper-bound polytopes. We prove that if a feasible region exists, it must contain or be adjacent to these extreme points, allowing for a rigorous search.
Specialization for Security Games
In the specific context of Stackelberg Security Games (SSGs), the structure of the game allows for significant optimization. Security games often feature "subset-closed" schedules, where covering fewer targets is always a valid (though perhaps suboptimal) strategy.
By exploiting this structure, we replace the exhaustive extreme-point search with a specialized SECURITY-SEARCH routine. This refinement reduces the sample complexity to $O(n^3L)$, where $n$ is the number of targets and $L$ is the bit-precision of the payoffs. This represents a substantial improvement over the previous state-of-the-art complexity of $O(n^{6.5}L)$, moving the field closer to practical implementation.
Fundamental Hardness and Lower Bounds
While our algorithm achieves polynomial complexity in terms of precision ($L$), we also establish fundamental limits on the efficiency of any learning algorithm in this setting. We prove that the number of leader actions ($m$) imposes an unavoidable bottleneck.
Specifically, we show a lower bound of $\Omega(2^m)$ for general Stackelberg games. This implies that as the leader's action space grows, the number of samples required to find the optimal strategy must grow exponentially. To prove this, we construct a "worst-case" game instance where the follower's payoffs are carefully balanced to hide the optimal region.
The construction illustrated above demonstrates how a specific arrangement of payoffs (using values 1 and $k$) can force any algorithm to query an exponential number of strategies to distinguish between different potential best responses. This result shows that our general SEPARATE-SEARCH algorithm is essentially tight in its dependence on the number of actions.
Conclusion
This paper provides a comprehensive analysis of learning in Stackelberg games. By shifting the focus to the geometric properties of the strategy space, we developed SEPARATE-SEARCH, which achieves polynomial sample complexity relative to payoff precision. Our specialized results for security games offer a significant leap in efficiency, while our hardness results clarify the inherent complexity of the general problem. Future work may explore the impact of noisy or boundedly rational followers on these geometric boundaries.
Summary updated