Learning in Structured Stackelberg Games
We study structured Stackelberg games, in which both players (the leader and the follower) observe information about the state of the world at time of play. Importantly, this information may contain information about the follower, which the leader may use when deciding her strategy. Under this setting, we show that no-regret learning is possible if and only if the set of mappings from contexts to follower types that the leader uses to learn is not ``too complex''. Specifically, we find that standard learning theoretic measures of complexity do not characterize learnability in our setting and we give a new dimension which does, which we term the Stackelberg-Littlestone dimension. In the distributional setting, we give analogous results by showing that standard complexity measures do not characterize the sample complexity of learning, but a new dimension called the Stackelberg-Natarajan dimension does. We then show that an appropriate empirical risk minimization procedure achieves the corresponding sample complexity.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
LLM-Stackelberg Games: Conjectural Reasoning Equilibria and Their Applications to Spearphishing
We introduce the framework of LLM-Stackelberg games, a class of sequential decision-making models that integrate large language models (LLMs) into strategic interactions between a leader and a follower. Departing from cl…
Decision MakingMisinformationRecommendation SystemsSequential Decision MakingConvex-Concave Zero-Sum Stochastic Stackelberg Games
Zero-sum stochastic Stackelberg games can be used to model a large class of problems, ranging from economics to human robot interaction. In this paper, we develop policy gradient methods to solve these games from noisy g…
Convergence of Learning Dynamics in Stackelberg Games
This paper investigates the convergence of learning dynamics in Stackelberg games. In the class of games we consider, there is a hierarchical game being played between a leader and a follower with continuous action space…
Neural Operators Can Play Dynamic Stackelberg Games
Dynamic Stackelberg games are a broad class of two-player games in which the leader acts first, and the follower chooses a response strategy to the leader's strategy. Unfortunately, only stylized Stackelberg games are ex…
Computation of Stackelberg Equilibria of Finite Sequential Games
The Stackelberg equilibrium solution concept describes optimal strategies to commit to: Player 1 (termed the leader) publicly commits to a strategy and Player 2 (termed the follower) plays a best response to this strateg…