mlsanityData to 14 Oct 2026

Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information

arXiv 2502.00204 ↗First posted 31 Jan 2025cs.LG cs.GTcited by 6

Not on the map. Why?

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.

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

22 of 33 references.

References · 22

  1. 2020Performative Predictioncited by 327
  2. 2015Strategic Classificationcited by 257
  3. 2017Strategic Classification from Revealed Preferencescited by 128
  4. 2023Performative Prediction: Past and Futurecited by 53
  5. 2019Strategizing against No-regret Learnerscited by 50
  6. 2014Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problemscited by 46
  7. 2017Selling to a No-Regret Buyercited by 43
  8. 2017Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimizationcited by 37
  9. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 33
  10. 2015Learning in Auctions: Regret is Hard, Envy is Easycited by 23
  11. 2016BISTRO: An Efficient Relaxation-Based Method for Contextual Banditscited by 20
  12. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
10 more
  1. 2023Optimal Rates and Efficient Algorithms for Online Bayesian Persuasioncited by 16
  2. 2023Online Learning in Stackelberg Games with an Omniscient Followercited by 15
  3. 2019Semi-bandit Optimization in the Dispersed Settingcited by 14
  4. 2016Improved Regret Bounds for Oracle-Based Adversarial Contextual Banditscited by 13
  5. 2022Meta-Learning in Gamescited by 10
  6. 2023Strategic Apple Tastingcited by 10
  7. 2024Regret Minimization in Stackelberg Games with Side Informationcited by 7
  8. 2024Impact of Decentralized Learning on Player Utilities in Stackelberg Gamescited by 5
  9. 2024The Sample Complexity of Stackelberg Gamescited by 4
  10. 2016Catcher-Evader Gamescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 3.

6 papers.

  1. 2025Learning in Structured Stackelberg Gamescited by 2
  2. 2025Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivalscited by 2
  3. 2025Learning to Play Multi-Follower Bayesian Stackelberg Gamescited by 2
  4. 2026Learning in Bayesian Stackelberg Games With Unknown Follower's Typescited by 2
  5. 2026Optimal Budgeted Adaptation of Large Language Modelscited by 0
  6. 2026Learning to Price with Persuasioncited by 0