Learning in Structured Stackelberg Games

摘要

We initiate the study of *structured Stackelberg games*, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the follower's (unknown) type. Motivated by applications such as security games and AI safety, we show how this additional structure can help the leader learn a utility-maximizing policy in both the online and distributional settings. In the online setting, we first prove that standard learning-theoretic measures of complexity do not characterize the difficulty of the leader's learning task. We find that there exists a learning-theoretic measure of complexity, analogous to the Littlestone dimension in online classification, that *tightly* characterizes the leader's instance-optimal regret. We term this the *Stackelberg-Littlestone dimension*, and leverage it to provide a provably optimal online learning algorithm. In the distributional setting, we provide analogous results by showing that two new dimensions control the sample complexity upper- and lower-bound.