研究领导者如何利用上下文信息高效学习最优策略，适用于安全与AI对齐场景。
Learning in Structured Stackelberg Games
- 引入结构化斯塔克尔伯格博弈，利用上下文预测跟随者类型
- 提出栈式利特尔斯坦维数，精确刻画在线学习的最优后悔上界
- 适用于需要动态决策的安全与可信AI系统
我们首次研究结构化斯塔克尔伯格博弈，这是一种领导者与跟随者之间的新型战略互动，其中上下文信息可预测跟随者的（未知）类型。受安全博弈和人工智能安全等应用驱动，我们展示了这种额外结构如何帮助领导者在在线和分布设置下学习最大化效用的策略。在在线设置中，我们首先证明标准学习理论中的复杂度度量无法刻画领导者学习任务的难度。值得注意的是，我们发现存在一个类比于在线分类中利特尔斯坦维数的学习理论复杂度度量，能够紧致刻画领导者实例最优后悔。我们将此称为栈式利特尔斯坦维数，并基于它设计了一个可证明最优的在线学习算法。在分布设置中，我们通过展示两个新维度控制样本复杂度的上下界，得到类似结果。
原文摘要 · Abstract (English)
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. Notably, 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。