Learning in Stackelberg Games with Non-myopic Agents

• 成果类型: Article; Early Access
• 署名作者: Haghtalab, Nika; Lykouris, Thodoris; Nietert, Sloan; Wei, Alexander
• 署名单位: University of California System; University of California Berkeley; Massachusetts Institute of Technology (MIT); Cornell University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0423
• 发表日期: 2026
• 关键词: multiarmed bandit

摘要

We study Stackelberg games where a principal repeatedly interacts with a non-myopic long-lived agent without knowing the agent's payoff function. Although learning in Stackelberg games is well understood when the agent is myopic, dealing with non-myopic agents poses additional complications. In particular, non-myopic agents may strategize and select actions that are inferior in the present in order to mislead the principal's learning algorithm and obtain better outcomes in the future. We provide a general framework that reduces learning in the presence of non-myopic agents to robust bandit optimization in the presence of myopic agents. Through the design and analysis of minimally reactive bandit algorithms, our reduction trades off the statistical efficiency of the principal's learning algorithm against its effectiveness in inducing near-best responses. We apply this framework to Stackelberg security games (SSGs), pricing with unknown demand curve, general finite Stackelberg games, and strategic classification. In each setting, we characterize the type and impact of misspecifications present in near-best responses and develop a learning algorithm robust to such misspecifications. On the way, we improve the state-of-the-art query complexity of learning in SSGs with n targets from O(n3) to a near-optimal O(n) by uncovering a fundamental structural property of these games.