# Learning in Stackelberg Games with Non-myopic Agents

arXiv: https://arxiv.org/abs/2208.09407 · HTML: https://mlsanity.com/paper/2208.09407/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 71 references that are in the map.
- First posted on arXiv 19 Aug 2022.

## Builds on (most cited first, 22 of 22)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Corruption-robust exploration in episodic reinforcement learning](https://mlsanity.com/paper/1911.08689/) (2019)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Efficient Convex Optimization with Membership Oracles](https://mlsanity.com/paper/1706.07357/) (2017)
- [Learning Product Rankings Robust to Fake Users](https://mlsanity.com/paper/2009.05138/) (2020)
- [Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness](https://mlsanity.com/paper/1401.3888/) (2014)
- [Learning Optimal Reserve Price against Non-myopic Bidders](https://mlsanity.com/paper/1804.11060/) (2018)
- [Robust Dynamic Assortment Optimization in the Presence of Outlier Customers](https://mlsanity.com/paper/1910.04183/) (2019)
- [Contextual Search in the Presence of Adversarial Corruptions](https://mlsanity.com/paper/2002.11650/) (2020)

## Built on by (most cited first, 29 of 29)

- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [Fundamental Bounds on Online Strategic Classification](https://mlsanity.com/paper/2302.12355/) (2023)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Learning to Incentivize Information Acquisition: Proper Scoring Rules Meet Principal-Agent Model](https://mlsanity.com/paper/2303.08613/) (2023)
- [Regret Minimization in Stackelberg Games with Side Information](https://mlsanity.com/paper/2402.08576/) (2024)
- [Incentivizing High-Quality Content in Online Recommender Systems](https://mlsanity.com/paper/2306.07479/) (2023)
- [Regret Analysis of Repeated Delegated Choice](https://mlsanity.com/paper/2310.04884/) (2023)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [Should Decision-Makers Reveal Classifiers in Online Strategic Classification?](https://mlsanity.com/paper/2506.01936/) (2025)
- [Learning in Online Principal-Agent Interactions: The Power of Menus](https://mlsanity.com/paper/2312.09869/) (2023)
- [Learning to Manipulate a Commitment Optimizer](https://mlsanity.com/paper/2302.11829/) (2023)
- [Game of Coding With an Unknown Adversary](https://mlsanity.com/paper/2502.07109/) (2025)
- [Computational Intractability of Strategizing against Online Learners](https://mlsanity.com/paper/2503.04202/) (2025)
- [Learning in Structured Stackelberg Games](https://mlsanity.com/paper/2504.09006/) (2025)
- [Collective dynamics of strategic classification](https://mlsanity.com/paper/2508.09340/) (2025)
- [The Burden of Interactive Alignment with Inconsistent Preferences](https://mlsanity.com/paper/2510.16368/) (2025)
- [Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent](https://mlsanity.com/paper/2510.22471/) (2025)
- [mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environments](https://mlsanity.com/paper/2605.07841/) (2026)
- [Riemannian Manifold Learning for Stackelberg Games with Neural Flow Representations](https://mlsanity.com/paper/2502.05498/) (2025)
- [Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition](https://mlsanity.com/paper/2505.17379/) (2025)
- [Learning in Repeated Multi-Objective Stackelberg Games with Payoff Manipulation](https://mlsanity.com/paper/2508.14705/) (2025)
- [Learning from Acceptance: Cumulative Regret in the Game of Coding](https://mlsanity.com/paper/2605.09754/) (2026)
- [Learning Principal-Agent Contracts for Equitable Smallholder Carbon Farming under Moral Hazard and Adverse Selection](https://mlsanity.com/paper/2609.20404/) (2026)
- [Strategic Classification Has a Missing Lever: Audit Risk](https://mlsanity.com/paper/2609.22534/) (2026)

## Abstract (arXiv)

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 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 widetildeO(n) by uncovering a fundamental structural property of these games. The latter result is of independent interest beyond learning with non-myopic agents.