# Online Learning in Stackelberg Games with an Omniscient Follower

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

## 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 (most cited first, 18 of 18)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Learning Latent Representations to Influence Multi-Agent Interaction](https://mlsanity.com/paper/2011.06619/) (2020)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [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)
- [Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2210.11942/) (2022)
- [Learning Correlated Stackelberg Equilibrium in General-Sum Multi-Leader-Single-Follower Games](https://mlsanity.com/paper/2210.12470/) (2022)

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

- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information](https://mlsanity.com/paper/2502.00204/) (2025)
- [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)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [Learning to Play Against Unknown Opponents](https://mlsanity.com/paper/2412.18297/) (2024)
- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)
- [Learning to Play Multi-Follower Bayesian Stackelberg Games](https://mlsanity.com/paper/2510.01387/) (2025)
- [Learning Optimal Tax Design in Nonatomic Congestion Games](https://mlsanity.com/paper/2402.07437/) (2024)
- [The Burden of Interactive Alignment with Inconsistent Preferences](https://mlsanity.com/paper/2510.16368/) (2025)
- [Decentralized Online Learning in General-Sum Stackelberg Games](https://mlsanity.com/paper/2405.03158/) (2024)
- [Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games](https://mlsanity.com/paper/2405.06689/) (2024)
- [Learning in Repeated Multi-Objective Stackelberg Games with Payoff Manipulation](https://mlsanity.com/paper/2508.14705/) (2025)
- [Optimal Budgeted Adaptation of Large Language Models](https://mlsanity.com/paper/2602.00952/) (2026)

## 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.