Learning in Stackelberg Games with Non-myopic Agents

New Framework for Learning Against Long-Lived, Forward-Looking Agents Repeated Stackelberg games are a canonical model for strategic principal-agent interactions. Learning in these games is well studied against myopic agents who greedily maximize their per-round payoff. However, complications arise with nonmyopic agents because they may strategically deviate from best responding to mislead the principal. In “Learning in Stackelberg Games with Nonmyopic Agents,” Haghtalab, Lykouris, Nietert, and Wei provide a general framework that reduces learning in the presence of nonmyopic agents to robust bandit optimization against myopic agents. This leads to a challenge of designing minimally reactive bandit algorithms, which balance the statistical efficiency of the principal’s learning algorithm against its effectiveness at inducing near-best responses. The authors tackle this challenge across problem domains, including security games, dynamic pricing, and strategic classification. Along the way, they uncover a structural property for learning in security games, enabling them to improve the state-of-the-art query complexity with n targets from [Formula: see text] to a near-optimal [Formula: see text].