# Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 57 references that are in the map.
- First posted on arXiv 23 Feb 2021.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Multi-agent Reinforcement Learning in Sequential Social Dilemmas](https://mlsanity.com/paper/1702.03037/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies](https://mlsanity.com/paper/2004.13332/) (2020)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Complexity of Mechanism Design](https://mlsanity.com/paper/1408.1486/) (2014)
- [Convergence of Learning Dynamics in Stackelberg Games](https://mlsanity.com/paper/1906.01217/) (2019)
- [Learning Nash Equilibrium for General-Sum Markov Games from Batch Data](https://mlsanity.com/paper/1606.08718/) (2016)
- [Learning to Play Sequential Games versus Unknown Opponents](https://mlsanity.com/paper/2007.05271/) (2020)
- [Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness](https://mlsanity.com/paper/1401.3888/) (2014)
- [Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces](https://mlsanity.com/paper/1911.07755/) (2019)
- [From Duels to Battefields: Computing Equilibria of Blotto and Other Games](https://mlsanity.com/paper/1603.00119/) (2016)
- [Computing Stackelberg Equilibria of Large General-Sum Games](https://mlsanity.com/paper/1909.03319/) (2019)

## Built on by (most cited first, 30 of 40)

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [LLM Economist: Large Population Models and Mechanism Design in Multi-Agent Generative Simulacra](https://mlsanity.com/paper/2507.15815/) (2025)
- [Representation Learning for General-sum Low-rank Markov Games](https://mlsanity.com/paper/2210.16976/) (2022)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2210.11942/) (2022)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [Constrained Meta-Reinforcement Learning for Adaptable Safety Guarantee with Differentiable Convex Programming](https://mlsanity.com/paper/2312.10230/) (2023)
- [Learning Optimal Contracts: How to Exploit Small Action Spaces](https://mlsanity.com/paper/2309.09801/) (2023)
- [Regret Analysis of Repeated Delegated Choice](https://mlsanity.com/paper/2310.04884/) (2023)
- [Impact of Decentralized Learning on Player Utilities in Stackelberg Games](https://mlsanity.com/paper/2403.00188/) (2024)
- [Learning Correlated Stackelberg Equilibrium in General-Sum Multi-Leader-Single-Follower Games](https://mlsanity.com/paper/2210.12470/) (2022)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [Population-size-Aware Policy Optimization for Mean-Field Games](https://mlsanity.com/paper/2302.03364/) (2023)
- [Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games](https://mlsanity.com/paper/2502.09780/) (2025)
- [Efficient Morphology-Control Co-Design via Stackelberg Proximal Policy Optimization](https://mlsanity.com/paper/2603.15388/) (2026)
- [Learning in Bayesian Stackelberg Games With Unknown Follower's Types](https://mlsanity.com/paper/2602.00771/) (2026)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [DeCOM: Decomposed Policy for Constrained Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2111.05670/) (2021)
- [Analyzing Micro-Founded General Equilibrium Models with Many Agents using Deep Reinforcement Learning](https://mlsanity.com/paper/2201.01163/) (2022)
- [Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation](https://mlsanity.com/paper/2211.15792/) (2022)
- [Distributionally Safe Reinforcement Learning under Model Uncertainty: A Single-Level Approach by Differentiable Convex Programming](https://mlsanity.com/paper/2310.02459/) (2023)
- [Sample-Efficient Multi-Agent RL: An Optimization Perspective](https://mlsanity.com/paper/2310.06243/) (2023)

## Abstract (arXiv)

Real world applications such as economics and policy making often involve solving multi-agent games with two unique features: (1) The agents are inherently asymmetric and partitioned into leaders and followers; (2) The agents have different reward functions, thus the game is general-sum. The majority of existing results in this field focuses on either symmetric solution concepts (e.g. Nash equilibrium) or zero-sum games. It remains open how to learn the Stackelberg equilibrium -- an asymmetric analog of the Nash equilibrium -- in general-sum games efficiently from noisy samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium, in the bandit feedback setting where we only observe noisy samples of the reward. We consider three representative two-player general-sum games: bandit games, bandit-reinforcement learning (bandit-RL) games, and linear bandit games. In all these games, we identify a fundamental gap between the exact value of the Stackelberg equilibrium and its estimated version using finitely many noisy samples, which can not be closed information-theoretically regardless of the algorithm. We then establish sharp positive results on sample-efficient learning of Stackelberg equilibrium with value optimal up to the gap identified above, with matching lower bounds in the dependency on the gap, error tolerance, and the size of the action spaces. Overall, our results unveil unique challenges in learning Stackelberg equilibria under noisy bandit feedback, which we hope could shed light on future research on this topic.