# Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 33 references that are in the map.
- First posted on arXiv 31 Jan 2025.

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

- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)
- [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)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion](https://mlsanity.com/paper/2303.01296/) (2023)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Semi-bandit Optimization in the Dispersed Setting](https://mlsanity.com/paper/1904.09014/) (2019)
- [Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits](https://mlsanity.com/paper/1606.00313/) (2016)
- [Meta-Learning in Games](https://mlsanity.com/paper/2209.14110/) (2022)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Regret Minimization in Stackelberg Games with Side Information](https://mlsanity.com/paper/2402.08576/) (2024)
- [Impact of Decentralized Learning on Player Utilities in Stackelberg Games](https://mlsanity.com/paper/2403.00188/) (2024)
- [The Sample Complexity of Stackelberg Games](https://mlsanity.com/paper/2405.06977/) (2024)
- [Catcher-Evader Games](https://mlsanity.com/paper/1602.01896/) (2016)

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

- [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)
- [Learning to Play Multi-Follower Bayesian Stackelberg Games](https://mlsanity.com/paper/2510.01387/) (2025)
- [Learning in Bayesian Stackelberg Games With Unknown Follower's Types](https://mlsanity.com/paper/2602.00771/) (2026)
- [Optimal Budgeted Adaptation of Large Language Models](https://mlsanity.com/paper/2602.00952/) (2026)
- [Learning to Price with Persuasion](https://mlsanity.com/paper/2608.16699/) (2026)

## Abstract (arXiv)

We study the problem of online learning in Stackelberg games with side information between a leader and a sequence of followers. In every round the leader observes contextual information and commits to a mixed strategy, after which the follower best-responds. We provide learning algorithms for the leader which achieve O(T1/2) regret under bandit feedback, an improvement from the previously best-known rates of O(T2/3). Our algorithms rely on a reduction to linear contextual bandits in the utility space: In each round, a linear contextual bandit algorithm recommends a utility vector, which our algorithm inverts to determine the leader's mixed strategy. We extend our algorithms to the setting in which the leader's utility function is unknown, and also apply it to the problems of bidding in second-price auctions with side information and online Bayesian persuasion with public and private states. Finally, we observe that our algorithms empirically outperform previous results on numerical simulations.