Learning in Structured Stackelberg Games

Maria Florina Balcan, Kiriaki Fragkia, Keegan Harris
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:5786-5810, 2026.

Abstract

We initiate the study of structured Stackelberg games, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the follower’s (unknown) type. Motivated by applications such as security games and AI safety, we show how this additional structure can help the leader learn a utility-maximizing policy in both the online and distributional settings. In the online setting, we first prove that standard learning-theoretic measures of complexity do not characterize the difficulty of the leader’s learning task. We find that there exists a learning-theoretic measure of complexity, analogous to the Littlestone dimension in online classification, that tightly characterizes the leader’s instance-optimal regret. We term this the Stackelberg-Littlestone dimension, and leverage it to provide a provably optimal online learning algorithm. In the distributional setting, we provide analogous results by showing that two new dimensions control the sample complexity upper- and lower-bound.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-balcan26a, title = {Learning in Structured Stackelberg Games}, author = {Balcan, Maria Florina and Fragkia, Kiriaki and Harris, Keegan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {5786--5810}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/balcan26a/balcan26a.pdf}, url = {https://proceedings.mlr.press/v306/balcan26a.html}, abstract = {We initiate the study of structured Stackelberg games, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the follower’s (unknown) type. Motivated by applications such as security games and AI safety, we show how this additional structure can help the leader learn a utility-maximizing policy in both the online and distributional settings. In the online setting, we first prove that standard learning-theoretic measures of complexity do not characterize the difficulty of the leader’s learning task. We find that there exists a learning-theoretic measure of complexity, analogous to the Littlestone dimension in online classification, that tightly characterizes the leader’s instance-optimal regret. We term this the Stackelberg-Littlestone dimension, and leverage it to provide a provably optimal online learning algorithm. In the distributional setting, we provide analogous results by showing that two new dimensions control the sample complexity upper- and lower-bound.} }
Endnote
%0 Conference Paper %T Learning in Structured Stackelberg Games %A Maria Florina Balcan %A Kiriaki Fragkia %A Keegan Harris %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-balcan26a %I PMLR %P 5786--5810 %U https://proceedings.mlr.press/v306/balcan26a.html %V 306 %X We initiate the study of structured Stackelberg games, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the follower’s (unknown) type. Motivated by applications such as security games and AI safety, we show how this additional structure can help the leader learn a utility-maximizing policy in both the online and distributional settings. In the online setting, we first prove that standard learning-theoretic measures of complexity do not characterize the difficulty of the leader’s learning task. We find that there exists a learning-theoretic measure of complexity, analogous to the Littlestone dimension in online classification, that tightly characterizes the leader’s instance-optimal regret. We term this the Stackelberg-Littlestone dimension, and leverage it to provide a provably optimal online learning algorithm. In the distributional setting, we provide analogous results by showing that two new dimensions control the sample complexity upper- and lower-bound.
APA
Balcan, M.F., Fragkia, K. & Harris, K.. (2026). Learning in Structured Stackelberg Games. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:5786-5810 Available from https://proceedings.mlr.press/v306/balcan26a.html.

Related Material