mlsanityData to 7 Oct 2026

Decentralized Online Learning in General-Sum Stackelberg Games

arXiv 2405.03158 ↗First posted 6 May 2024cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

35 of 56 references.

References · 35

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  2. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  3. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  4. 2017Multi-agent Reinforcement Learning in Sequential Social Dilemmascited by 206
  5. 2017Cycles in adversarial regularized learningcited by 122
  6. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  7. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  8. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  9. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  10. 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
  11. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  12. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
23 more
  1. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  2. 2015The Sample Complexity of Revenue Maximizationcited by 48
  3. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  4. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  5. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  6. 2013Learning Prices for Repeated Auctions with Strategic Buyerscited by 37
  7. 2014Complexity of Mechanism Designcited by 33
  8. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  9. 2015Watch and Learn: Optimizing from Revealed Preferences Feedbackcited by 17
  10. 2023Online Learning in Stackelberg Games with an Omniscient Followercited by 15
  11. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  12. 2022No-Regret Learning in Dynamic Stackelberg Gamescited by 12
  13. 2020Optimally Deceiving a Learning Leader in Stackelberg Gamescited by 11
  14. 2019Imitative Follower Deception in Stackelberg Gamescited by 9
  15. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  16. 2019Manipulating a Learning Defender and Ways to Counteractcited by 8
  17. 2021Decentralized Online Learning for Noncooperative Games in Dynamic Environmentscited by 4
  18. 2022Learning Correlated Stackelberg Equilibrium in General-Sum Multi-Leader-Single-Follower Gamescited by 4
  19. 2021Zero-Sum Stackelberg Stochastic Linear-Quadratic Differential Gamescited by 3
  20. 2023Learning to Manipulate a Commitment Optimizercited by 3
  21. 2022Optimal Private Payoff Manipulation against Commitment in Extensive-form Gamescited by 2
  22. 2022Zero-Sum Stochastic Stackelberg Gamescited by 2
  23. 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximationcited by 1

Built on by

Not cited yet.