# Decentralized Online Learning in General-Sum Stackelberg Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 56 references that are in the map.
- First posted on arXiv 6 May 2024.

## Builds on (most cited first, 30 of 35)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Multi-agent Reinforcement Learning in Sequential Social Dilemmas](https://mlsanity.com/paper/1702.03037/) (2017)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies](https://mlsanity.com/paper/2004.13332/) (2020)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [Complexity of Mechanism Design](https://mlsanity.com/paper/1408.1486/) (2014)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Watch and Learn: Optimizing from Revealed Preferences Feedback](https://mlsanity.com/paper/1504.01033/) (2015)
- [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)
- [No-Regret Learning in Dynamic Stackelberg Games](https://mlsanity.com/paper/2202.04786/) (2022)
- [Optimally Deceiving a Learning Leader in Stackelberg Games](https://mlsanity.com/paper/2006.06566/) (2020)
- [Imitative Follower Deception in Stackelberg Games](https://mlsanity.com/paper/1903.02917/) (2019)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Manipulating a Learning Defender and Ways to Counteract](https://mlsanity.com/paper/1905.11759/) (2019)
- [Decentralized Online Learning for Noncooperative Games in Dynamic Environments](https://mlsanity.com/paper/2105.06200/) (2021)
- [Learning Correlated Stackelberg Equilibrium in General-Sum Multi-Leader-Single-Follower Games](https://mlsanity.com/paper/2210.12470/) (2022)

## Abstract (arXiv)

We study an online learning problem in general-sum Stackelberg games, where players act in a decentralized and strategic manner. We study two settings depending on the type of information for the follower: (1) the limited information setting where the follower only observes its own reward, and (2) the side information setting where the follower has extra side information about the leader's reward. We show that for the follower, myopically best responding to the leader's action is the best strategy for the limited information setting, but not necessarily so for the side information setting -- the follower can manipulate the leader's reward signals with strategic actions, and hence induce the leader's strategy to converge to an equilibrium that is better off for itself. Based on these insights, we study decentralized online learning for both players in the two settings. Our main contribution is to derive last-iterate convergence and sample complexity results in both settings. Notably, we design a new manipulation strategy for the follower in the latter setting, and show that it has an intrinsic advantage against the best response strategy. Our theories are also supported by empirical results.