# No-Regret Learning in Dynamic Stackelberg Games

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 38 references that are in the map.
- First posted on arXiv 10 Feb 2022.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Online learning in MDPs with linear function approximation and bandit feedback](https://mlsanity.com/paper/2007.01612/) (2020)
- [Dynamic Games with Asymmetric Information: Common Information Based Perfect Bayesian Equilibria and Sequential Decomposition](https://mlsanity.com/paper/1510.07001/) (2015)

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

- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Regret Minimization in Stackelberg Games with Side Information](https://mlsanity.com/paper/2402.08576/) (2024)
- [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)
- [Computational Intractability of Strategizing against Online Learners](https://mlsanity.com/paper/2503.04202/) (2025)
- [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)
- [Distributionally Safe Reinforcement Learning under Model Uncertainty: A Single-Level Approach by Differentiable Convex Programming](https://mlsanity.com/paper/2310.02459/) (2023)
- [Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds](https://mlsanity.com/paper/2301.11802/) (2023)
- [Decentralized Online Learning in General-Sum Stackelberg Games](https://mlsanity.com/paper/2405.03158/) (2024)

## Abstract (arXiv)

In a Stackelberg game, a leader commits to a randomized strategy, and a follower chooses their best strategy in response. We consider an extension of a standard Stackelberg game, called a discrete-time dynamic Stackelberg game, that has an underlying state space that affects the leader's rewards and available strategies and evolves in a Markovian manner depending on both the leader and follower's selected strategies. Although standard Stackelberg games have been utilized to improve scheduling in security domains, their deployment is often limited by requiring complete information of the follower's utility function. In contrast, we consider scenarios where the follower's utility function is unknown to the leader; however, it can be linearly parameterized. Our objective then is to provide an algorithm that prescribes a randomized strategy to the leader at each step of the game based on observations of how the follower responded in previous steps. We design a no-regret learning algorithm that, with high probability, achieves a regret bound (when compared to the best policy in hindsight) which is sublinear in the number of time steps; the degree of sublinearity depends on the number of features representing the follower's utility function. The regret of the proposed learning algorithm is independent of the size of the state space and polynomial in the rest of the parameters of the game. We show that the proposed learning algorithm outperforms existing model-free reinforcement learning approaches.