# Regret Minimization in Stackelberg Games with Side Information

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 13 Feb 2024.

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

- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion](https://mlsanity.com/paper/2303.01296/) (2023)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits](https://mlsanity.com/paper/1606.00313/) (2016)
- [No-Regret Learning in Dynamic Stackelberg Games](https://mlsanity.com/paper/2202.04786/) (2022)
- [Contextual Games: Multi-Agent Learning with Side Information](https://mlsanity.com/paper/2107.06327/) (2021)
- [Meta-Learning in Games](https://mlsanity.com/paper/2209.14110/) (2022)
- [Catcher-Evader Games](https://mlsanity.com/paper/1602.01896/) (2016)
- [Learning Adversary Behavior in Security Games: A PAC Model Perspective](https://mlsanity.com/paper/1511.00043/) (2015)

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

- [Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information](https://mlsanity.com/paper/2502.00204/) (2025)
- [Impact of Decentralized Learning on Player Utilities in Stackelberg Games](https://mlsanity.com/paper/2403.00188/) (2024)
- [Learning in Structured Stackelberg Games](https://mlsanity.com/paper/2504.09006/) (2025)
- [Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals](https://mlsanity.com/paper/2505.23124/) (2025)
- [Optimal Budgeted Adaptation of Large Language Models](https://mlsanity.com/paper/2602.00952/) (2026)
- [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026)
- [Constrained Contextual Bandits with Adversarial Contexts](https://mlsanity.com/paper/2605.06190/) (2026)

## Abstract (arXiv)

Algorithms for playing in Stackelberg games have been deployed in real-world domains including airport security, anti-poaching efforts, and cyber-crime prevention. However, these algorithms often fail to take into consideration the additional information available to each player (e.g. traffic patterns, weather conditions, network congestion), which may significantly affect both players' optimal strategies. We formalize such settings as Stackelberg games with side information, in which both players observe an external context before playing. The leader commits to a (context-dependent) strategy, and the follower best-responds to both the leader's strategy and the context. We focus on the online setting in which a sequence of followers arrive over time, and the context may change from round-to-round. In sharp contrast to the non-contextual version, we show that it is impossible for the leader to achieve no-regret in the full adversarial setting. Motivated by this result, we show that no-regret learning is possible in two natural relaxations: the setting in which the sequence of followers is chosen stochastically and the sequence of contexts is adversarial, and the setting in which contexts are stochastic and follower types are adversarial.