Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
Maria-Florina Balcan *, Martino Bernasconi *, Matteo Castiglioni *, Andrea Celli *, Keegan Harris, Zhiwei Steven Wu * · 2025
Read Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information by Maria-Florina Balcan *, Martino Bernasconi *, Matteo Castiglioni *, Andrea Celli *, Keegan Harris, Zhiwei Steven Wu * (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-00204.txt.
Introduction
Maria-Florina Balcan and co-authors wrote this machine learning theory paper, published in two thousand twenty-five, on games where one player commits first and the other answers. In a Stackelberg game, a leader picks a mixed strategy each round after seeing context, and a follower then best-responds.
The team gives the leader learning algorithms whose regret grows only with the square root of the number of rounds, beating the best known rates. The trick is a detour: a linear bandit method proposes a target utility each round, and the algorithm works backward to the strategy that yields it. The setup also works when the leader's own payoff must be learned. The same ideas carry to bidding in second-price auctions and to online persuasion tasks. Simulations back the theory, with the new methods ahead of prior ones.
Catalog record
| CREATOR | Maria-Florina Balcan *, Martino Bernasconi *, Matteo Castiglioni *, Andrea Celli *, Keegan Harris, Zhiwei Steven Wu * |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-00204
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information Maria-Florina Balcan *, Martino Bernasconi *, Matteo Castiglioni *, Andrea Celli *, Keegan Harris, Zhiwei Steven Wu * Abstract 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 ~ ( T 1 / 2 ) \tilde{O}(T^{1/2}) regret under bandit feedback , an improvement from the previously best-known rates of O ~ ( T 2 / 3 ) \tilde{O}(T^{2/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. 1 Introduction Many real-world strategic settings take the form of Stackelberg games , in which the leader commits to a (randomized) strategy and the follower(s) best-respond . For example, in security domains (e.g. airport security, wildlife protection) the leader (federal officers with drug-sniffing dogs, park rangers) chooses a patrol strategy, which the follower (drug smuggler, poacher) observes before choosing an area to exploit. In such settings, the leader may face different follower types over time, each with their own goals and objectives. We study a generalization of the traditional Stackelberg game setting in which the payoffs of the players depend on additional contextual information (or side information ) that is not captured in the players’ actions and may vary over time. Such contextual information naturally arises in many Stackelberg game settings: In airport security, different parts of the airport may be more crowded during different parts of the day, which may make it easier or harder to smuggle items through security in those areas. In wildlife protection, different animal species may be easier or harder to poach at different times of the year, due to factors such as migration patterns and weather. More generally, side information may appear in the form of (an embedding of) natural language, such as threat reports, incident descriptions, or intelligence briefings, which can alter the leader’s optimal commitment and/or the follower’s strategic response. Harris et al. (2024) formalize this setting and provide online learning algorithms for the leader when the followers and contextual information change over time. Their algorithms obtain \tilde{O}(T^{1/2}) regret 1 1 1 Regret is the cumulative difference between the best possible policy’s utility and the leader’s utility. under full feedback (i.e. when information about the follower is revealed to the leader after each round) where T is the number of time-steps, but only \tilde{O}(T^{2/3}) regret under the more challenging (and more realistic) bandit feedback setting, where only the follower’s action is revealed. Our contributions We close the gap from \tilde{O}(T^{2/3}) to \tilde{O}(T^{1/2}) regret under bandit feedback, which matches known lower bounds up to logarithmic factors. As in Harris et al. (2024) , we study two settings: one in which the sequence of contextual information is chosen adversarially and the sequence of followers is chosen stochastically, and the setting where the contextual information is chosen stochastically and the followers are chosen adversarially. Moreover, the algorithms of Harris et al. (2024) are not applicable when the follower’s utility depends on the contextual information, an assumption which we do not need. In both settings (adversarial contextual information and adversarial follower types), our algorithm ( Algorithm 1 ) is a reduction to linear contextual bandits. While the leader’s utility is a non-linear function of their strategy, we can linearize the problem by playing in the leader’s “utility space”. In each round, a linear contextual bandit algorithm plays a vector in the image of the leader’s utility, where the i -th component of the vector is the leader’s expected utility when facing the i -th follower type. The leader then plays the strategy which induces this utility vector and gives their observed reward as feedback to the contextual bandit algorithm. By reformulating the problem in this way, we can take advantage of the rich literature on linear contextual bandits. Indeed, by instantiating Algorithm 1 with different contextual bandit algorithms, we obtain regret guarantees for both settings. Next we study an extension to the setting where the leader’s utility function is unknown and must be learned over time. We show that a similar reduction to contextual bandits holds in this setting under a linearity assumption on the leader’s utility function. This reduction still obtains \tilde{O}(T^{1/2}) regret, albeit at the cost of additional polynomial factors in the size of the problem instance in the regret bound. In Section 4 we show how to apply our algorithm to learning in other settings which exhibit the same type of structure; specifically (i) learning in second-price auctions with side information and (ii) online Bayesian persuasion with side information. We are the first to study either of these settings, to the best of our knowledge, despite the fact that side information naturally arises in both auctions and Bayesian persuasion settings. Our results largely carry over to these applications as-is, although we need to discretize the learner’s action space in a different way than we do for Stackelberg games. Our work is conceptually related to Bernasconi et al. (2023) , who use a similar reduction to obtain \tilde{O}(T^{1/2}) regret in online Bayesian persuasion, learning in auctions, and learning in Stackelberg games without side information. While their main result is a reduction to adversarial linear bandits, our problem reduces to a linear contextual bandit problem with an infinite action set. Furthermore, either the action set or the sequence of contexts will be chosen adversarially, depending on which setting we are in. While such contextual bandit problems are generally intractable, we leverage the special structure present in our setting to obtain positive results. In particular, we observe that the optimal strategy at each time-step will always belong to a time-varying, but finite, set. Therefore, we can discretize the utility space in a way that allows us to apply our reduction with two specific linear contextual bandit algorithms that allow for both time-varying action sets and adversarially-chosen contexts/action sets. Additionally, while both our reduction and theirs leverage the linear structure which is induced from having finitely-many follower types, our extension to unknown leader utilities in Section 3.3 uses a more general version of this linear structure in order to compensate for the additional uncertainty from unknown utilities. Our reduction is also more streamlined, as it does not require a per-round application of Caratheodory’s Theorem, due to our discretization step. 1.1 Related work Learning in Stackelberg games Conitzer and Sandholm (2006) provide algorithms and prove NP-Hardness results for the problem of computing equilibrium in various Stackelberg game settings when all parameters of the problem are known. A line of work on learning Stackelberg games Letchford et al.