mlsanityData to 14 Oct 2026

Online Learning in Stackelberg Games with an Omniscient Follower

arXiv 2301.11518 ↗First posted 27 Jan 2023cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

We study the problem of online learning in a two-player decentralized cooperative Stackelberg game. In each round, the leader first takes an action, followed by the follower who takes their action after observing the leader's move. The goal of the leader is to learn to minimize the cumulative regret based on the history of interactions. Differing from the traditional formulation of repeated Stackelberg games, we assume the follower is omniscient, with full knowledge of the true reward, and that they always best-respond to the leader's actions. We analyze the sample complexity of regret minimization in this repeated Stackelberg game. We show that depending on the reward structure, the existence of the omniscient follower may change the sample complexity drastically, from constant to exponential, even for linear cooperative Stackelberg games. This poses unique challenges for the learning process of the leader and the subsequent regret analysis.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 18 of its 41 references that are in the map. First posted on arXiv 27 Jan 2023.

Builds on

18 of 41 references.

References · 18

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  3. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  4. 2015Strategic Classificationcited by 257
  5. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 225
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  7. 2017Strategic Classification from Revealed Preferencescited by 128
  8. 2020Learning Latent Representations to Influence Multi-Agent Interactioncited by 93
  9. 2014Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problemscited by 46
  10. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  11. 2022The Sample Complexity of Online Contract Designcited by 35
  12. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
6 more
  1. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  2. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  3. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  4. 2022No-Regret Learning in Dynamic Stackelberg Gamescited by 12
  5. 2022Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learningcited by 12
  6. 2022Learning Correlated Stackelberg Equilibrium in General-Sum Multi-Leader-Single-Follower Gamescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 7; 2025: 5; 2026: 1.

15 papers.

Sort:

By area:

  1. 2023Strategic Apple Tastingcited by 10
  2. 2025Nearly-Optimal Bandit Learning in Stackelberg Games with Side Informationcited by 6
  3. 2023Regret Analysis of Repeated Delegated Choicecited by 5
  4. 2024Impact of Decentralized Learning on Player Utilities in Stackelberg Gamescited by 5
  5. 2024Contractual Reinforcement Learning: Pulling Arms with Invisible Handscited by 5
  6. 2024Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactionscited by 5
  7. 2024Learning to Play Against Unknown Opponentscited by 3
  8. 2025Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failurecited by 2
  9. 2025Learning to Play Multi-Follower Bayesian Stackelberg Gamescited by 2
  10. 2024Learning Optimal Tax Design in Nonatomic Congestion Gamescited by 1
  11. 2025The Burden of Interactive Alignment with Inconsistent Preferencescited by 1
  12. 2024Decentralized Online Learning in General-Sum Stackelberg Gamescited by 0
3 more
  1. 2024Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Gamescited by 0
  2. 2025Learning in Repeated Multi-Objective Stackelberg Games with Payoff Manipulationcited by 0
  3. 2026Optimal Budgeted Adaptation of Large Language Modelscited by 0