Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
Authors: Maria Florina Balcan
Martino Bernasconi
Matteo Castiglioni
Andrea Celli
Keegan Harris
Steven Wu
Venue: ICLR 2026 Poster (2026)
Keywords: stackelberg games
bandit learning
side information
Primary area: learning theory

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}) regret under bandit feedback, an improvement from the previously best-known rates of 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.

Published as a conference paper at ICLR 2026
NEARLY-OPTIMAL BANDIT LEARNING IN STACKELBERG GAMES WITH SIDE INFORMATION
Maria-Florina Balcan"
Martino Bernasconi
Matteo Castiglioni Politecnico di Milano
Carnegie Mellon University
Bocconi University
Andrea Celli Bocconi University
Keegan Harris*
Zhiwei Steven Wu Carnegie Mellon University
University of California, Berkeley
ABSTRACT
We study the problem of online learning Stackelberg games with side in- formation between a leader and 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 Ó(T)/2) regret under bandit feedback, an improvement from the previously best-known rates of ( Our algorithms rely on reduction linear contextual bandits in the utility space: In each round, a linear contextual bandit algorithm recommends a utility vector, which our algorithm inverts 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-pric -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.
INTRODUCTION
Many real-world strategic settings take the form of Stackelberg games, in which the leader commits (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 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 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 migration patterns and weather.
Harris et al. (204)) formalize this setting and provide online learning algorithms for the leader when the followers and contextual information change over time. Their algorithms obtain ( regre 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 ((12/3) regret under the more challenging (and more realistic) bandit feedback setting, where only the follower's action is revealed.
We close the gap from O(T2/3) to O(T1/2) regret under bandit feedback, which matches known lower bounds up to logarithmic factors. As in Harris al. (2024). we study two settings: one in which the sequence of contextual information is chosen adversarially and the
Our contributions
Authors are listed in alphabetical order. Corresponding author: keegan. harri s@berkel leeerkeely.... edu. Regret is the cumulative difference between the hest possible policy's utility and the leader's utility.

---

Published as a conference paper at ICLR 2026
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. (024) are not applicable when the follower's utility depends the contextual information, an assumption which we do not need.
In both settings (adversarial contextual information and adversarial follower types), our algorithm (Algorithm [ 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 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 Al- gorithm I with different contextual bandit algorithms, we obtain regret guarantees for both settings.
Next we study extension to the setting where the leader's utility function is unknown and must be learned over time. We show that similar reduction to contextual bandits holds in this setting under linearity assumption on the leader's utility function. This reduction still obtains Ö(T1/2) regret, albeit at the cost of additional polynomial factors in the size of the problem instance in the regret bound.
In Section Twe show how to apply our algorithm to learning in other settings which exhibit the same type of structure; specifically (i) learning in second-pric proicd-picee auctions with side information and (ii) online Bayesian persuasion with side information. We are the first 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 similar reduction to obtain Ö(TL/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 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 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-choss contexts/action sets. Additionally, while both reduction and theirs leverage the linear structure which is induced from having finitely-man follower types, our extension to unknown leader utilities in Section 3.3 uses 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 discretization step.
1.1 RELATED WORK
Learning in Stackelberg games Conitzer & Sandholm (2066) 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 Letch- ford et al. (2009): Peng et al. 2 Bacchiocchi et al. (0255 relaxes the assumption that all pa- rameters of the problem are known to the leader, and instead posits that they are given number of (player actions, outcome) tuples to learn from.
Our work falls under the category of online learning in Stackelberg games, where the sequence of data arrives sequentially instead of all at once. This setting was first introduced by Balcan et al. (015)) and was generalized to handle settings with side information in Harris et al. (2024). Other recent work on learning in Stackelberg games includes learning in cooperative Stackelberg games (e.g. Zhao et al. (2023); Donahue al. (2024)), strategizing against a follower who plays no- regret learning algorithm (e.g. [Braverman et al. (2018); Deng et al. (2019)), and learning various structured Stackelberg games such as strategic classification (e.g. Hardt al. (2016): Dong et al.
2

---

Published as a conference paper at ICLR 2026
2018), performative prediction (e.g. Perdomo et al. (2020): Hardt & Hendler-Dünnee (2023) ))
and
principal- agget problems (e.g. Ho et al. (2016)).
Online learning in Stackelberg games is conceptually related to the online optimization of piecewise Lipschitz functions, as the underlying reward function after fixing any fixed follower type (and piece of side information) is piecewise linear Dick et al. (2020); [Sharma al. (2020); Balcann et al. (2018). However the techniques used in this line of work are not applicable to our setting, since the follower type and contextual information change from round-to-round.
Learning in auctions and persuasion Our algorithms are also applicable to generalizations of the problems of online learning in simultaneous second-price auctions Daskalakis & Syrgkanis) (2022) and online Bayesian persuasion Casstiglini et al. (2020). Flajolet & Jailler
also study online learning in second-price auctions with side information. They consider single-item auction settings with a budget constraint, while we consider combinatorial auctions with no budget constraints. We also consider a more general form of adversarial feedback than they consider.
Contextual bandits Finally, one may view our setting as a special type of contextual bandit prob- lem with continuous action spaces and non-linear rewards. While one could, in principle, attempt to apply a black-box contextual bandit algorithm to our setting (e.g. Syrgkanis et al. (2016a b); Rakhlin Sridharan (2016)), are not aware of any algorithms which obtain meaningful performance guarantees under this reward structure without (1) making additional assumptions about the learner's s knowledge of the sequence of contexts they will face and (2) obtaining generally worse rates.
PRELIMINARIES
We use ((A) to denote the probability simplex over the (finite) set A, and [N] == {I...., N to denote the set of integers from 1 to N E Nyo-
We study a repeated interaction between a leader and a sequence of followers over T rounds. In round E [T'. both players observe context 2, E Z S Rd which represents the side information available (e.g. information about weather patterns, airport congestion levels) in the current round. The leader then commits to mixed strategy X, E (AAi), where A is the leader's action set and A : |Ai < cp. After observing the context Z, and the leader's mixed strategy Xr, follower fe plays action a,,t E As, where Ay is the follower's action and A, [Ayl < co. The leader's action 01, is then sampled according to their mixed strategy Xt.
After the round is over, the leader receives utility u(ze, at,e, af,)), according their utility func-
tion u Z x Ai X A, + |-1, 1]. Similarly, follower ft receives utility uy, (Ze, d1,t, af,a) according to utility function ds : Z x Ai Af + [-1,1]. We often use the shorthand u(2;, X4, (x)) := Ex,,,x, [u(z,, a1, a)))) (resp. Uf, (z,, xt,af,t) = Ex,,,x (Ze, at,, af.))) to denote the leader's (resp. follower's) expected utility with respect to the randomness in the leader's mixed strategy.
We assume that the follower each round is one of K < oo types Se E [K]. where follower type i E [K] corresponds to utility function uy. We assume that ......; UK are known to the leader, but the identity of follower fe is never revealed This setting is referred to as bandit feedback in the literature online learning in Stackelberg games Balcan et al. (2015): Harris et al. (2024).
Given a context 2, and leader mixed strategy X,, follower ft's best-response is by, (Zr,x)) := arg ma U, (z,, X,,0,), where ties are broken in an unknown- but--bbuttteeeee way. We measure the performance of the leader via the notion of regret:
Definition 2.1 (Contextual Stackelberg Regret). The leader's contextual Stackelberg re- gret with respect to context sequence Zi...., ZT and follower sequence fi....,f fr R(T) = Σt u(zr, xi, by, (2. x;)) - u(zz, Xx, b.bb,, (z,(2x,)))) where x = π (Z:) == arg maxxEA(A) LTz =n, w(Zr, x, by, (Zr, is the mixed strategy played by the optimal-in- hindsight policy πt at time t.
Balcan al. (0155) show that learning is impossible when K = oc in (non-contextual) Stackelherg games, which implies an impossibility result for our setting.
3

---

Published as a conference paper at ICLR 2026
Algorithm 1: Reduction to Linear Contextual Bandits
Input: Linear contextual bandit algorithm R
for f = .' do
Observe n₁. compute U/ := (u(z,, x) x E
Let V; < RR. recoommend
Commit to the mixed strategy X, which induces Ve
Play action at ~ X, and call R.observoUhhlityyww u(ze, ares by. (Ze, x,))
end
Since previous work Harris et al. 2024) shows that no-regret learning is impossible (i.e. there exists no algorithm for which R(T) = (T)) when the sequence of contexts and the sequence of followers are chosen jointly by an adversary with knowledge of the leader's ' algorithm, we focus on two natural relaxations: the setting where the sequence of contexts is chosen by an adversary and the sequence of follower types are drawn from an unknown (stationary) distribution (Section [3.1] and the setting where the sequence of follower types are chosen by an adversary and the sequence of contexts are drawn from an unknown distribution (Section 3.2 b.2 All of our results are applicable to the simpler setting where both the contexts and follower types are chosen stochastically.
While the leader's ' action space (AAr) is infinitely large, follow the lead of previous work and consider a discretization which is nearly wothout loss of generality. The following two definitions from Harris et al. (2024).
Definition 2.2 (Contextual Follower Best-Response Region). For follower type i E [K], follower action af As, and context E 2, let Xi,i, C A(Ai) denote the set of all leader mixed strategies such that a follower of type i best-responds to all x E X2(i, af) by playing action aj under context z, i.e. Nx ai)) = {x X (, = =a
Definition 2.3 (Contextual Best Best-Response Region). For given function [K] + Aj, let (o(or denote the set of all leader mixed strategies such that under context z, a follower of type i plays action (i) for all i E [K), i.e. (z = (at,
straightforward to show that all contextual best-response regions are convex and bounded (but not necessarily closed). Because of this, the loss in performance is negligible from restricting the leader's s strategy space to be the set of approximate extreme points of all contextual best-response regions. Formally, define & as follows.
Definition 2.4 (6-approximate extreme points). Fix a context z E Z and consider the set of all non- empty contextual best-response regions. For ô > 0. (8) is the set of leader mixed strategies such that for all best-response functions a and any x E A(Ai) that is an extreme point of cl()x(o)), E (5) x E (a).). Otherwise there is some x' E (6) such that x' E Xx(a) and |x' x||1 < 8. With slight abuse of notation, we define the set of approximate extreme points & to be
E, = Ez.(7) (7).
Balcan et al. 2015) show that & = O(((A))) By Lemma 4.4 in Harris et al. 2024 restricting the learner to policies which only play strategies in & at round leads to at most O(1) additional regret. We will use fact throughout the sequel.
3 A REDUCTION TO LINEAR CONTEXTUAL BANDITS
Our main result is an algorithm (Algorithm that achieves O(T)/2) regret in both the setting where contexts are chosen adversarially and follower types are chosen stochastically (Section 3.1) and the setting where the contexts are chosen stochastically and follower types are chosen adversarially (Section 3.2). While the leader's utility is a non-lincar function of their mixed strategy x, in any given round (due to the follower's 'ss best-response b(z,, x))), can "lincarize" the problem by leveraging the fact that the leader's 's utility can be written as u(z,, Xx, by. (Zz, x+)) = (u(z, x,), 1,,), where u(z, x) := [u(z, x, by (z, x)).... u(z, x, bx (z, x)]] E R is the vector of utilities the leader would receive against each follower type given context and mixed strategy x, and 1,, R is a one-hot vector with a 1 in the fe-th component and zeros elsewhere. Since u(z,, Xg (2(, is linear function of u2, xz), one can an off-the-shelff linear contextual bandit algorithm to
4

---

Published as a conference paper at ICLR 2026
pick vector v, in the image of u(z;.)) then invert the mapping to find the mixed strategy x such that V, = u(z,,x)).
Algorithm| takes as imput linear contextual bandit algorithm R, which, (1) when given a (finite) set of actions Uz. returns an element V; E Ug (R.recommend(() and (2) updates its internal parame- ters when given action v, and realized utility We [-1,1] 1] (RoobserveUtilitt()) Finally, while the leader's action space (AAi) infinitely large (and thus, so the dual space Ü, := {u(ze, x) : E A(A))).. the leader incurs essentially no loss in utility by restricting themselves to a finite (but exponentially-large
set of context-depente metexx--eeenneet points &,, which roughly correspond the set of extreme points of convex polytopes which are induced by the followers' best-responses.At such, our algorithm operates on the set of utility vectors U. (u(z,, x) x E & in each round
3.1 ADVERSARIAL CONTEXTS AND STOCHASTIC FOLLOWER TYPES
To get no-regret guarantees when the sequence of contexts is chosen adversarially and the sequence of follower types is chosen stochastically, we instantiate Algorithm T with the Optimism in the Face of Uncertainty for Linear models (OFUL) linear contextual bandit algorithm of Abbasi- Yadkori jet al. (2011). T). OFUL. leverages the principle of optimism under uncertainty to balance exploration and exploitation. Specifically, it assumes a linear relationship between utilities and actions such that B[up] = (v,, 0*) where V, E RK is an action from some exogenously -iginnnnlyynnnnnnneee set Us, and 0 E R an unknown parameter. OFUL maintains confidence set C₁ over O* in round such that 0 E Ce with high probability, which updates based on the noisy observed utility Ug. In each round, it then selects the action that maximizes the upper confidence bound on the expected reward, i.e. it plays action V, E arg maxvet, (v.
We show that when follower types are chosen stochastically, the leader's ' utility at time t can be writ- ten as u(z,, Xx, by, (Z+, xx)) = (u(,,, x.), p²) + ét, where p" E A is the true (unknown) distribu- tion over follower types, and 6t E [-4,4] is zero-mean random variable. Therefore by instantiat- ing Algorithm 1 with OFUL, we can optimistically learn p* and attain Ó regret this setting.
AbbaiiYYadkori Theorem 3.1. When R is instantiated as the OFUL algorithm of Abbasi Yadkori et al. 2077), Al-
gorithm | obtains expected contextual Stackelberg regret E[R(T)] O(K VT (oo (T)( when the sequence of contexts is chosen adversarially and the sequence of follower types is chosen stochas- tically. The expectation is taken with respect to both the randomness Algorithm 7 as well as the distribution over follower types.
3.2 STOCHASTIC CONTEXTS AND ADVERSARIAL FOLLOWER TYPES
When the sequence of follower types chosen adversarially, there will be no underlying distribution P' over follower types for the algorithm to learn. As such, instantiating R with OFUL will not provide meaningful regret guarantees in this setting. Instead, we instantiate R using a modified version of Algorithm in Liu et al. 2023 (Algorithm 2
Algorithm in Liu et al. (2023) (henceforth referred to as logdet-FTRL) uses a variant of Follow- with the log- log-determinant barrier the regularizer to solve variant of the linear contextual bandit problem with adversarial losses. In their setting, the learner receives a set of actions U? in each round which are drawn from some distribution over the unit ball and plays an action v E Ug The learner then receives loss & such that E[4] = (v/, where y: is chosen adversarially.
Laa-Regularize--Laaaeee
In our setting, the set of leader mixed strategies & is deterministically determined by the context 2;- Therefore, whenever the sequence of contexts {2. hejry is drawn from fixed distribution, so is the also drawn from some fixed distribution. to (1) transform
sequence {&, [e([)) which then implies that (77 )<((T)
The last steps in order to apply logdet-FTRL.
action space from [-1. 1 1| to the K -ddmenssional unit ball and (2) convert utilities to losses. We handle this in Algorithm 2 by rescaling our actions by vR
and negating the observed utilities before passing them logdet-FTRL.
"This important, as the regret minimizers we instantiate Algorithm I with Section 3.1 and Section 3.2 hoth require the action set to he finite. logdet-FFRI. requres [T&| I oc in order to have finite per-round runtime.
5

---

Published as a conference paper at ICLR 2026
Theorem 3.2. When R is instantiated the regret minimizer of Algorithm 2 Algorithm 2 ob- tains expected contextual Stackelberg regret [[[[T)] O(K2' / log(T)) when the sequence of contexts is chosen stochastically and the sequence of follower types is chosen adversarially. The well the distribution
expectation is taken with respect both the randomness in Algorithm over contexts.
3.3 EXTENSION TO UNKNOWN UTILITIES
So far we have assumed that the leader's 's utility function u is known. In this section, we relax this assumption and show that a modification of Algorithm obtains Õ(vT) regret when u is unknown, under an additional linearity assumption (Assumption 3.3
Assumption 3.3. Given context z E Z, leader action as A,, and follower action aj E Ag the leader's 's utility is u(z, 0t, az) (z. U (a) af)) where U (as, az) E TRd is unknown to the leader.
This setting may be thought of as both generalization of Stackelberg games (to settings where there side information) and generalization of linear contextual bandits (to settings where another player's action influences the utility of the learner).
Our key insight that under Assumption 3.3 the leader's utility can still written as a linear function of some known vector h(z, x., albeit in larger (d K x A₁ Ay) Adddiennsso space (hheorem3.4) Theorem 3.4 is stated in terms of generie distribution y over follower types. This distribution y corresponds to either the true underlying distribution over follower types p (when follower types are chosen stochastically), or the empirical distribution in hindsight over follower types (when they are chosen adversarially).
Theorem 3.4. Under Assumption 3.3 the leader's expected utility (with respect to distribution ? over follower types) can be written as Ey~zlu(z, x, (y(2, x))] (h(z, x), for some h(z, E BdxXXXAxx which is known to the leader and 0 E Rdx K XxxxA which is not.
The proof of Theorem 3.4 is constructive, but the closed-form expression of h(z, x) is somewhat cumbersome, so we relegate it Appendix
Given the results of Theorem 3.4 we can immediately obtain regret guarantees for the unknown
utilities setting by running Algorithm using the action set U, (h(z,, E & (instead of U-- = (u(z,, x) : x E } in round t. Since h(zt, x) E R X AxXA, our regret will scale as (poly (dK (apoolydK.Aa
A VT), compared to the (poly T)) rates Section 3.1 and Section 3.2
Thus, a poly (5 term is the price we pay for handling unknown utilities in our setting.
Corollary 3.5. Under Assumption 3.3 when R. is instantiated the OFUL algorithm of Abbasi- obtains expected contextual Stackelberg regret E[R(T)) = OdKK (oogg(()) when the sequence of contexts is chosen adversarially and the sequence of follower types chosen stochastically.
Yadkori et al. 2017] and U, == (((z, x) x E Et}, Algorithm 1
when R instantiated as the regret minimizer of Algo- rithm 2 and U2 := xh( x E EtJ. Algorithm 7 obtains expected contextual Stackelberg regret E[R(T)) O(dd AtA,) 22. VT log(T)) when the sequence of contexts is chosen stochastically and the sequence of follower types is chosen adversarially.
Corollary 3.6. Under Assumption
3.4 BETTER RUNTIMES IN SPECIAL CASES
In all previous sections, the per-round runtime of Algorithm I is Oppoly K, Ar,Ad, In general &, is exponentially- instantiation of Algorithm/ is exponential. This is to be expected, since we inherit the rou-round NP- harddddesss results from the non-contextual Stackelberg game setting of et al. (2016), combined with the offline to online reduction of Roughgarden & Wang (2019). With that being said, there are several interesting cases for which the runtime of Algorithm
in the size of the problem, and so the worst-case runtime of each
be improved.
1. Small number of effective follower types Consider setting with three follower types, where u, (z, x, ay) and Uz uz(z, x, ay) are arbitrary and uz(2, ay) = 1(z E Z'} uy ay) + 1(z & z') u2(2, x, a for some subset of contexts 2' Z. While K 3, the number of approximate

---

Published as a conference paper at ICLR 2026
de2. Km4, leader actions, owerr actions
[dm2. Kmm, leader actions, follower actions)
160
140
122
10-
200
100
Figure I: Left: Cumulative utility of the optimal policy, Algorithm| innstantiated with OFUL (Algl- OFUL), and the random baseline over T = 200 rounds in setting with 4 follower types, where each player has actions and the context dimension also 2. Right: Cumulative regret of Alg1-OFUl and the random baseline over T 200 rounds in the same setting. Results are averaged over 10 rums.
extreme points at each round only |&, O((2A)) A7), since the best-response regions of follower type 3 always overlap with those of either follower type 2. Such overlap between follower best-response regions can happen in more general settings; we capture this through the notion of effective follower types.
Definition 3.7 (Effective follower types). We say that there are K' followrr types in round t if. fixing 2t, there are K' unique follower utility functions.
When there are K' effective follower types in round f, there are at most [& = O((')))) ) approximate extreme points, which may be much less than the worst-case bound of (((AA)))
A/) K' is small or constant.
Few non-dominated leader actions per round Similarly, it could be the case that for context there exists two leader actions a and aj such that u(zt, at, at, I u(Zz, di af) for all a E A When this happens, we say that action a; is dominated by action of in round If there are A/ non-dominated actions in round f, then |& = O((KA)) A3).
Exogeenuully-supplie leader strategies Suppose that instead of defining &, according to Def-
inition 2.4 external algorithm supplies a set of extreme points E c E, in each round t [T] such that [g = (pooyy(A,, A,, K)). If & в arg maxxeε, Elu( Zt, x, fe(,,, x))] with probability at least 6, then the expected regret of running Algorithm Jusing {E/}T-, instead of (E, is
OEE ((E)(T) [T) 8T), where E[R(T)] is the expected regret of running Algorithm using (E))-
3.5 EXPERIMENTS
We empirically evaluate the performance of Algorithm instantiated with OFUL (henceforth Algo- rithm OFFUL) synthetically-generaae contextual Stackelberg games. In this setting, there are follower types, each of whose utility function is randomly generated. Note that since the followers' utilities depend on the contextual information, algorithms from previous work on bandit learning in Stackelberg games with side information (e.g. Algorithm: 3 in Harris et al. (2024)) are not applicable in this setting. The leader's utility function is also random and linear the context, whose dimen- sion is d 2. Both the leader and followers have actions. Finally, both the sequence of contexts and followers are generated stochastically.
In Figure I we plot the cumulative utility (left) and regret (right) of Algorithm[ and random baseline over = 200 time-steps. In the Appendix, we compare the performance of Algorithm I OFUL with that of Algorithm 3 in Harris et al. (2024) in the special case where follower utilities do not depend on the side information. Even in this setting, we find that Algorithm OFUU signifi- cantly outperforms the other alternatives.

---

Published as a conference paper at ICLR 2026
4 OTHER APPLICATIONS
Algorithm [leverages the fact that there are a finite number of follower types to transform the prob- lem into the utility space of the leader, before applying an off-the-shelf linear contextual bandit algo- rithm. Interestingly, the only parts of Algorithm I that are specific to Stackelberg games are how the sets of extreme points and leader utilities computed. As such, it is possible to apply Algorithm []] to other settings where the learner has a finite number of possible utility functions. We highlight two such applications here: learning in auctions with side information (Section 4.1) and online Bayesian persuasion with side information (Section 4.2). Despite the prevalence of side information both auctions and persuasion, we are the first to study either setting, the best of our knowledge.
Since our definition of approximate extreme points & is specific to Stackelberg games, we instead ensure that |U,] oo in both settings by discretizing the policy space. Specifically, in both auctions and persuasion
(re-)define & be { (z:) w S2}, where f2 is (finite) uniform grid and T (w) is policy parameterized by w. After bounding the discretization error, our analyses for the
results in this section are analogous to those in Section 3.1 and Section 3.2
4.1 LEARNING TO BID AUCTIONS WITH SIDE INFORMATION
Daskalakis & Syrgkanis 2022 consider the problem of no-regret learning in second-price auction setting where in each round E [T]. bidders simultaneously bid on a bundle of m items. Taking the
perspective of a single bidder. they play bid vector b, E [0, 1 in round and receive the bundle of items S(b, 0,) ti brli 2 O,Li], where O, E θ c [0. 1] is a threshold vector corresponding to the item-wise maximum of the other players' bids. Having received bundle of items S(b, O.), the bidder receives utility u(b,, 0,) == ((S(,,, 0:)) - Ejes(b..... P[j). where v(S(b, 0z)) E R is their valuation for item bundle S(b,, O.) and Ejes(b,o, Ø[i] is the cumulative price of the items in S(b, 0.). Daskalakis & Syrgkanis (2022) provide a no-regret learning algorithm for this setting when each threshold vector Or can take only one of K different values (i.e. |0] = K). In the bandit feedback setting, the threshold vector O, is never revealed to the learner.
We apply slightly more general version of Algorithm D (Algorithm 3) to generalization of this problem. where the bidder's valuation is allowed to depend on additional contextual information (i.e. v: 2 x [0, 11THT x θ + R). Such contextual information is often present in auction settings. For example, shoppers' valuations for bundles of clothing items often depend on external factors such as the season current fashion trends.
In this setting, utilities are now a function of the context Zy the bid vector b,, and the threshold vector O, and a policy is a mapping from contexts to bids for each item (i.e. : 2 + [0, I)m".. Instead of discretizing the learner's action space like in Section 3, we instead discretize their policy space follows.
Definition 4.1 (Discretized Policy for Auctions). Let Ω = (w E AK T. EN, ViE [K]]. Σ wlil b(()) and
We define policy w(w) as (x()(z) = arg maxbe
: (-()(() W S2.
Armed with this policy discretization, we are ready to state our results for running Algorithm in repeated auctions with side information. Analogous to Definition 2.1 we define regret to be the cumulative difference in utility between the optimal policy and the sequence of bid vectors played by the learner.
Corollary 4.2. When U. == (u(z,, : E Ee} and R is instantiated as the OFUL algorithm of Abbasi- Yadkori et al. (2011). 1. the expected regret of Algorithm is B[R(T)] = OKK /T log(T)) when the sequence of contexts chosen adversarially and the sequence of threshold vectors
chosen stochastically.
Corollary 4.3. When U. = bu( b b E and R is instantiated as the regret mini- mizer of Algorithm 2 Algorithm [ obtains expected regret E[R(T)] O(K2.5 /TlogT) when the sequence of contexts is chosen stochastically and the sequence of threshold vectors is chosen adversarially.
8

---

Published as a conference paper at ICLR 2026
4.2 BAYESIAN PERSUASION WITH PUBLIC AND PRIVATE STATES
Bayesian persuasion (BP: Kamenica & Gentzkow (2011) is canonical setting in information de- sign which studies how provision of information by an informed designer (the sender) influences the strategic behavior of agents (receivers) in a game.
We study generalization of the online BP setting, in which a sender learns to play against a se- quence of I'' receivers, which was first introduced by Castiglioni et al. (2020). The novelty in our setting is that context Z E is revealed to both the sender and receiver in each round E [T]. This context may be thought of as "public state", which contains contextual information that is available both players. After observing the context, the sender commits to signaling policy + A. which maps privale states from some finite set f to receiver actions in finite set Ahe private state is drawn from a publicly-known prior distribution and revealed to the sender (but not the receiver). After the private state is realized, the sender signals according to their policy and the follower takes an action (possibly different from the one recommended to them by the sender).
The sender faces a sequence of receivers TI,..,, where each receiver is one of K types (T(12, ((k). Our notion of receiver type is analogous to our definition of follower type in Sec- tion 2 i.e each receiver type has a different utility function which maps contexts, private states, and receiver actions to utilities. As is standard in most BP settings, we assume that receivers are Bayes-rational and pick their action to maximize their expected utility with respect to the posterior distribution over states induced by the sender's ' signal realization.
is possible to show that the set of leader signaling policies can be represented by a convex polytope P (see, e.g. Section 4 in Bernasconi et al. (2023), ). As such, the leader can solve for the optimal signaling policy to play given a context z and distribution over receiver types by optimizing over P. The leader's goal is to maximize their own cumulative utility u ZxPx (7(1), ( ((k)) [-1, which is function of the context (i.c. public state), the private state, and the receiver's s type (through
the action they take). Under bandit feedback, the sequence of receiver types ri,..., Pr is never revealed to the sender.
We discretize the policy space analogously to Section 4.1 the only difference is the form of the leader's 's utility function and the action space they optimizing over.
Definition 4.4 (Discretized Policy for Persuasion). Let Ω == {w E AK T wlil EN Vi E [K]] We define policy ((W) as ( (z) == arg maxHep Σ wli] u(z,p, and = ( E !t}.
We obtain results for two persuasion settings with side information: one in which the sequence of public states is chosen adversarially and the receiver types are chosen stochastically, and one where the sequence of contexts is stochastic and the follower types are chosen stochastically.
Corollary 4.5. When U. == (u(ze,H ()) : i E E.} and R is instantiated as the OFUL algorithm of Abbasi- Yadkori et al. (2011). the expected regret of Algorithm Dis B[R(T)]= = O(K K /T log(T)) when the sequence of public states is chosen adversarially and the sequence of receiver types chosen stochastically.
Corollary 4.6. When U, == (u(ze.H) E Er} and R is instantiated as the regret minimizer of Algorithm 2 Algorithm obtains expected regret E, B[R(T)] = 2 when the sequence of public states chosen stochastically and the sequence of receiver types is chosen adversariall.
5 CONCLUSION
We study the problem of bandit learning in Stackelberg games with side information, where we improve upon the previously best-known ( regret rates to Ó(T2/2), Our results rely on reduction to linear contextual bandits in the leader's utility space. Extensions to unknown leader utilities, auctions with side information, and Bayesian persuasion with public and private states are also considered.
TThis is without loss of generality due to revelation principle-style argument (see, e.g. Kamenica & Gentzkow 201T)).

---

Published as a conference paper at ICLR 2026
There are several exciting directions for future work. While our results for known utilities extend to auctions and persuasion, our results for unknown utilities do not. It would be interesting to see if Algorithm can be (further) generalized to handle such settings. Given the exponential expooe worst-case computational complexity of Algorithm a more in depth study of its runtime using tools from, e.g. smoothed analysis Spielman & Teng 2004) would also be interesting.
ACKNOWLEDGEMENTS
We would like to thank the anonymous reviewers for their helpful feedback. For part of this work, KH Ph.D. student at Carnegie Mellon University. This work was supported in part by NSF Grant CCF-1910321, an ERC grant (Project 101165466 - PLA-STEER), the FAIR (Fu- ture Artificial Intelligence Research) project PE0000013, and the EU Horizon project ELIAS (No. 101120237).
The work of MB and AC was partially funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Yasin Abbusi-Yadkori, Dávid Pál. and Csaba Szepesvári. Improved algorithms for lin- car stochastic bandits. In John Shawe-Taylor, Richard S. Zemel, Peter L. Bartlett, Fer- nando C. N. Pereira, and Kilian Q. Weinherger (eds.), Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Sys- tems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain, pp. 2312-2320, 2011. URL htttps::/prroeeeeteetet newrips......................... cC/ hccppaper/221//aaaii html
Francesco Bacchiocchi, Matteo Bollini, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. The sample complexity of stackelberg games. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Mohammad Emtiyaz Khan (eds.), International Conference
Artificial Intelligence and Statistics, AISTATS 2025, Mai Khao, Thailand, 3-5 May 2025, volume 258 of Proceedings of Machine Learning Research, pp. 2053-2061. PMLR, 2025. URL https://procedinges
mlr. www.ppeessssve. https///22///acccccccccc2322 html
Paria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Tim Roughgarden, Michal Feldman, and Michael Schwarz (eds.), Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15 Portland, OR, USA, June 15-19, 2015, pp. 61-78. ACM, 2015. doi: 10. 1144/2764468.2764477 URL https: /oiiiiii...o http:///oco.o..ooooo.oo wtt.://.11..111275551 27647777777777
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In Mikkel Thorup (ed.), 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pp. 603- 614. IEEE Computer Society, 2018. doi: 109FF00/00 2018.00044,, URL https: stttps::/doi... //doi. org/19 00g/10.1109/FOCC 201..0018.00 00064
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online bayesian persuasion. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scar- lett (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Hon- olulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 2164-2183. PMLR, 2023. URL /tttp:://proceedee
mlr. pwwss/ /wwes///222... /20/ btt.2////eernaccnn22......
html
Mark Braverman, Jieming Mao, Jon Schneider, and S. Matthew Weinberg. Selling to a no-regret buyer. In Éva Tardos, Edith Elkind, and Rakesh Vohra (eds.), Proceedings of the 2018 ACM Con- ference Economics and Computation, Ithaaa, NY, USA, June 18-22, 2018 pp. 523-538. ACM,
10

---

Published as a conference paper at ICLR 2026
2018. doi: 10.1144//229116:3219233. URL 3219233
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online bayesian per- suasion. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiee Lin (eds.), Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL http:httts///ppceeeeeeet Absbbcc---bbttttttt .t.ml
neur ips cct/papper/2222/has
Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy commit to. In Joan Feigenbaum, John C.-I. Chuang, and David M. Pennock (eds.), Proceedings 7th ACM Confer- ence Electronic Commerce (EC-2006), Ann Arbor, Michigan, USA, June 11-15, 2006, pp. 82-90. ACM, 2006. doi: 10.1455/134707.144411 URL
1134707 1134717
Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret is hard, envy is easy. Games Econ. Behav. 144:308-343, 2022. doi: 10. 00.10166..GEBB.222..0.... URL https:
//doi. 101.110661111 (tw.:///6...bb...
2r0ooooorrr11..000033..62.222220 2022 03.
Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against regret learners. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Flo- rence d'Alché- Buc, Emily B. Fox, and Roman Garnett (eds.), Advances Neural In- formation Processing Systems 32: Anmual Conference on Neural Information Process- ing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. neur imnrrips... CC httpppaae//229/hssii html
1577-1585, 2019. URL
8b6dd7db9a 350 neur
Travis Dick, Wesley Pegden, and Maria-Florina Balcan. Semi-bandit optimization in the dispersed setting. Ryan Adams and Vibhav Gogate (eds.), Proceedings the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2020, virtual online, August 3-6, 2020, volume 124 of Proceedings of Machine Learning Research, pp. 909-918, AUAI Press, 2020. URL http: html
ppoceediiggs..o mlr www.sswwww............... sereas/v124/dics.e
Kate Donahue, Nicole Immorlica, Meena Jagadeesan, Brendan Lucier, and Aleksandrs Slivkins. Impact of decentralized learning player utilities in stackelberg games. In Forty-first Interna- tional Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. Open- Review.net, 2024. URLlhttps: hwwp///wwpe...e.eppepppp. www.:ttttr/tat. Mat.rrrmmmmddddMMMMaaaaaaaaa
/
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Éva Tardos, Edith Elkind, and Rakesh Vohra (eds.), Proceedings of the 2018 ACM Conference Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pp. 55-70. ACM, 2018. doi: 10.11455/211166.3219993 URL https: //doi.org// 10 1114/21///16111 3219193
Arthur Flajolet and Patrick Jaillet. Real-time bidding with side information. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Confer- ence Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5162-5172, 5172, 2017. URL wttp///ttttee//eoeeeeeiaaee netripeerppp. cc/ cc/paper/2017/
Moritz Hardt and Celestine Mendler-Dünner. Performative prediction: Past and future. CoRR, abs/2310. 16608 2023. doi: 10.4850/ARRXIV.310..660 URL httph: org/10. 48550/arXiv wwt.xxii.i1v.....
Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, and Mary Wootters. Strategic classi- fication. In Madhu Sudan (ed.), Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16. 2016, pp. 111-122. ACM, 2016. doi: 10.14552340728.2447733
URL 2ttp:///2aa..ooo...1114444424000
org
2840730

---

Published as a conference paper at ICLR 2026
Keegan Harris, Zhiwei Steven Wu, and Maria-Florina Balcan. Regret minimization in stack- elberg games with side information. In Amir Globersons, Lester Mackey, Danielle Bel- grave. Angela Fan, UIrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Newral Information Processing Systems 38: Annual Conference on Neural Informa- fion Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15, 2024, 2024. URL 178b6ca14 www.aaafeeee00eee7eee33aa -t
nips. wwtpssss.ppp.ccpppppppppppppp files//aperr2222/ Abstract
cronferencehhtm Coteeeetntttteeeeeeeeeeeeeeeee
Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. J. Artif. Intell.
Res., 55:317-359, 2016. doi: 10.1613/AARR.9440 URL /ttt:s::/aii.or/110.110..0
jair. 4940
Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101
(6):25902261,,2) 2011.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the op- timal strategy to commit to. In Marios Mavronicolas and Vicky G. Papadopoulou (eds.), Algo- rithmic Game Theory, Second International Symposium, SAGT 2009, Paphos, Cyprus. October 18-20, 2009. Proceedings, volume 5814 of Lecture Notes in Computer Science, pp. 250-262. Springer, 2009. doi: 10.
URL https: pestps://doi.. org/10................oo........ org/10.1007/
978-3-642-04645-222
Yuqian Li, Vincent Conitzer, and Dmytro Korzhyk. Catcher-evader games. In Subbarao Kamb- hampati (ed.), Proceedings of the Twenty-Fift International Joint Conference Artificial Intel- ligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016,1 pp. 329-337. IJCAI/AAAI Press, 2016.
URL http: ifcai. org/ htt///bsttrat.cc 054
Haolin Liu, Chen-Yu Yu Wei, and Julian Zimmert. Bypassing the simulator: Near-optimal adversarial linear contextual bandits. In Alice Oh, Tristan Naumann, Amir Glober- son, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural formation Processing Systems 36: Annual Conference on Neural Information Pro- cessing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL a3a661
nips. cc/paper Abssaaaacat1112A-taatttaata Corttttooffeeecccee html
Binghui Peng. Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-Firss Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Sym- posium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, Jamuary 27 - February 1, 20/9, pp. 2156-2156. AAAI Press, 2019. doi: 10. A..09//AAAL..3300...... 33012149. URL https: http://oo...rg....
1699 aaai. v33i01. 033101.33012111 33012149
Juan C. Perdomo, Tijana Zmic. Celestine Hendler-Dünnedd and Moritz Hardt. Performative pre- diction. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Re- search, pp. 7599-7609. PMLR, 2020. URL perdomo20e html
mlr wtt.spt..s..i1///////
Alexander Rakhlin and Karthik Sridharan. BISTRO: an efficient relaxation-based method for con- textual bandits. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML. 2016, New York City, NY, USA, June 19- 24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1977-1985. JMLR.org. 2016. URLpttp: httpt::://pcceeeinggs mlr htw.:/pees////////// stteess//vv//rahhiiin.... h.tmmm
Tim Roughgarden and Joshua R. Wang. Minimizing regret with multiple reserves. ACM Truns. Economics and Comput., 13):17:1117:18, 2019. doi: 10.1145/3355900 Utttts/s::///ot
org/10. wet.11115355900
Dravyansh Sharma, Maria-Florina Balcan, and Travis Dick. Learning piecewise lipschitz func- tions in changing environments. In Silvia Chiappa and Roberto Calandra (eds.), The 23rd In- fernational Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August
12

---

Published as a conference paper at ICLR 2026
2020, Online [Palermo, Sicity, Italy], volume 108 of Proceedings of Machine Learning Re- search, pp. 3567-3577. PMLR, 2020. URL http:::/proceedngggs..... mir /
sharma20a. html
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):8854400 2004, doi: 10.1 145/999083 990310. URL https:: //oii org/10.
10. 111.//1111119999000000000 09001311330999000000
Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert E. Schapire. Efficient algorithms for ad- versarial contextual learning. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Pro- ceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA. June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceed- ings, pp. 2159-2168 JMLR.org. 2016a. URL http://proceecings mir wwl..press/vee syrgkani s html
Vasilis Syrgkanis. Haipeng Luo, Akshay Krishnamurthy, and Robert Schapire. Im- proved regret bounds for oracle-based adversarial contextual bandits. In Daniel D. Lee, Masashi Sugiyama. Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 29: Annual Conference Neural In- formation Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3135- 3143, 2016b. URL https:: neur ips hoc//paperr2216/hassss (fEa2228.111ee500faaaaaaaaa...
763cf Abstract html
Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. Online learning in stackel- herg games with omniscient follower. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Confer- ence on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 42304-42316. PMLR, 2023. URL https: http::://ppoceeeiigge mlr, www.....r.........m....memmmme.e press/ v202 zhao html
13

---

Theorem 3.1. When R is instantiated as the OFUL algorithm of Abbasi Yadkori et al. (211)) Al- gorithm 1 obtains expected contextual Stackelberg regret [[R(T)] O(K log(T) when the sequence of contexts is chosen adversarially and the sequence of follower types is chosen stochas- Published as a conference paper at ICLR 2026
A APPENDIX FOR SECTION 3 A REDUCTION TO LINEAR CONTEXTUAL BANDITS
Algorithm 2: Regret Minimizer R
Let R' be logdet-FTRe (Algorithm Liu et al. (2023) Recommend (U+): begin
Create scaled action set U. - :.zVveUl)
V R' recoommmnddUUU)
return VK- V/;
end
Observeutility (Ve, ut):
begin
Set v
VR and u/z نيب Call R' .observe.osss VV,, 14)):
end
tically. The expectation is taken with respect to both the randomness in Algorithm 7 as well as the distribution over follower types.
Proof. Let p* E A(K) be the distribution over follower types. Define u(z, x) vector in RKK where for each k E [K]:
u(z, x) u uz, x, (z. x))
Observe that for a fixed z, x, we have that
u(z,xx x. bj. ()) (p" u(z, + (u(z,x,br) (z, x)) (p", u(z, x)))
Let N u(z,x, by, (z,x)) (p" u(2, x)). Observe that since Efu(z, x, by, (z, x))]
(p" u(z, x)), T/. is zero-mean random variable bounded in [-2, 2). Similarly we have that for
a
u(z, an by. (2,x)) ulz, (2, x)) + (u(z, at, by (z, x)) u(zz x, by (2, x))x))),
where T/ = u(z, at bn. (z, x)) u(z, x, by. (z, x)) is a zero-mean random variable bounded in [-2, 2]. Putting both terms together, we have that
u(z, 0,, by, (z, x)) (p", u(z, x)) + C2s where = 77 + is zero-men mean random variable bounded in [-4,4] 4).
E E [T) E, E fr
u(2,, n (z,), x" (2,, (2.))) - u(ze, xt, by (2z, xt))
< 11+
F...... fi (u(2z, n (8) (z:), by, (2t, n (8) (z+))) u xx, by, (Zc, x())
T
= 1+
En [[][u(ze, n (8) (E)) (2t, (+1 Es [uluuee xx. by (2r, xx x+))
Am1
T
1 + Σ
(p" u(z,, n (8) (() - (p", E /ul
t=1
1 + E
(p" u(z,, / (E) (2+))) u(,, x:))
2 + 4 TK log A + T)( AK + 4 4 (Tg + K log + T/A))
14

---

Published as a conference paper at ICLR 2026
where x(6) is the optimal policy which is restricted to & in round t, the second line follows from
Lemma 4.4 in Harris et al. (2024) and the last line follows from applying the regret guarantee of Algorithm in Abbasi- Yadkori et al. (201T).
M
Theorem 3.2. When R is instantiated as the regret minimizer of Algorithm 2 Algorithm 7 ob-
tains expected contextual Stackelberg regret [[R(T)] = (TK2s/TTlogTTT when the sequence of contexts is chosen stochastically and the sequence of follower rypes is chosen adversarially. The
expectation is taken with respect to both the randomness in Algorithm 2 as well as the distribution over contexts.
Proof.
B[R(T)] = Bn ur
u Ze: n (zi), bj. (z,, (z:))) u(zz, X,, (2, xt))
t=1
< 1 + E
u(z,, n (() by. (ze, n (Z)()) u xe. by, (Ze, x:)]
2x
E
(z (5) (2)). 15.) x(), 1
T
= -1+ + Eg
(u(ze, π (z))), 1x,) (ve, 1
T
= 1 + E
(UU), 1 - (vr. 1,,1
BT
T
# (U,) K
1 + VK Eg
11,) - ( VK 1,
t=1
= OKK VTr2..//oogii (og((T)
where ((E is the optimal policy which is restricted to & in round f. ((U)) := u(z,, (()) (z,)), the second line follows from Lemma 4.4 in Harris et al. (2024) and the last line follows from the regret guarantee of Algorithm in Liu et al. (2023). To apply this result, we use the fact that the K- -d-imensional unit cube with side length 2 is contained in the K -idiiensional unit ball with radius VK.
Theorem 3.4. Under Assumption 3.3 the leader's expected utility (with respect to distribution " over follower types) can be written as Ey-zlu(z, x, by(2, x)) (h(z, x), 0) for some h(z, x) E Bd X which is known to the leader and 0 E R R A(X which is not.
R
Proof.
K
E (ux,,ul(,,,,/zzz,..
Σ
u(z x (11,, =i)
i=1
K
Σ
Σ
Σ
zJ [x(a]]1faa- b(l, =i)
A.E EAA
ie [K], E ay, E Ay. and j [d]] Define
a(,,a = (i 1)- (Ar d) (qi-1): (A, d) + (as - 1) -d j
Let Og Oaayay = Ula (r i) Rd and define 0 E mRdxKxAIX such that ay == 0i [5].
Similarly, let
((z,x))n((,,0,,,,,)))) == 2 2151x(a]11 b.(z. x)).
15

---

Published as a conference paper at ICLR 2026
dm3, Km5, leader actions. follower actions
dm4, Km4, leader actions, Tollower actions
Aganklmn
2500
1500
2000
Cumu
2500
1000
1000
500
1000
1250
1500
1750
2000
1000 1500 2000
(a) Cumulative utility of Algorithm instantiated with
(b) Cumulative utility of Algorithm instanttaated with OFUL (Algorithm] (egoorthhm-OFUn 1-OFUL)
OFUL (Algorithm1-O0 --FUU),, Algorithm
Harris
the random baseline over 2, 000 rounds in a setting with 4 follower types, where each player has actions and the context dimension is also 4. Results are averaged over 10 runs. Algorithm 3 of al. (202) is not applicable in this setting because follower's utility depends on the context.
at 2024), and the random baseline over 2, 000 rounds in a setting with 5 follower types, where each player has 3 actions and the context dimension is also 10 runs. The hyperparam- eter of Algorithm Harris et al. (2024) was tuned to maximize performance.
Results averaged
Figure 2: Additional empirical results.
A. APPENDIX FOR SECTION 3.5 EXPERIMENTS
Here we compare Algorithm Harris al. (2024) (henceforth Barycentric Explore-Then Commit), which obtains (TT233) regret in the special case where the follower's utility does not depend on the context. At high level, Barycentric Explore-Then-Coree number leader mixed strategies to estimate the frequency of follower best-responses, before acting greedily with respect these estimates for the remaining rounds. We also compare both algorithms to a baseline which plays by sampling leader mixed strategies uniformly-at-rame at-ramdom in each round (henceforth Random Baseline).
repeatedly plays small
In Figure 2a we compare the performance of the three algorithms on synthetic data. There are follower types, each of whose utility function is randomly generated and does not depend the contextual information. The leader's utility function is also random and is linear the context, whose dimension is 3. Both the leader and followers have actions. Finally, both the sequence of contexts and followers are generated stochastically.
In Figure 2b
compare the performance of Algorithm OFUL. with that of Random Baseline in setting where follower utilities do depend on contextual information. As result, Barycentric Mintore-Then-ooiie
not applicable. this setting, both leader and follower utility functions random linear functions of the context player actions. d = K = 4, and both players have 4 actions. We find that in both settings Algorithm OFUL significantly outperforms Random Baseline and Barycentric Explore-Theer Thwn-Thhnnnnnnnee (where applicable).
B APPENDIX FOR SECTION 4 OTHER APPLICATIONS
Corollary 4.2.
When U, == (u(z,, b) : b Ee} and R is instantiated as the OFUL algorithm
Abbbasi Yadkori et al. (2011), the expected regret of Algorithm 3 is E(R(T)) = O(K / log(T)) when the sequence of contexts chosen adversarially and the sequence of threshold vectors is chosen stochastically.
Proof. Observe that
K Σ
n (z) = arg max Ea<p|u(z, b, 0)] arg max pld u b, )()),
bE[0,1]m
be 1
16

---

Published as a conference paper at ICLR 2026
Algorithm 3: Reduction for Auctions and Persuasion
Input: Linear contextual bandit algorithm R
for f = ,, do
Observe Z,, compute utility set U²
Let V, < re)oommeedd(U))
Play the action which induces Vz
Receive utility ue and call R.observeUtiiltyy(w.e..
end
where P is an unknown distribution with support on (0(")... ..... O(Ki). Let n' == ((()) be the optimal policy in the discretization and let P' be the corresponding distribution over O. We have that
R(T) = E Ea-p
u(z (Zz x (ze). uzz, br, 0)]
K
K
p (u (Z:)) (()) - u(z,, b., )())) + Σ [p pli)) u(zz, be, 0(0)
(=1
[p[d] p((]) ulzz TT (Z)), 0(0) +
(il x 0(1) u(ze, T (ze), ((()))
1=1
1=1
S 2K Eo,,... Orap
u(ze, n (zz), 0.) ulz by, 0:)
The rest of the proof follows identically to the proof of Theorem 3.1 but without the discretization step.
Corollary 4.3. When U, == {u(z,, b) E E and R is instantiated as the regret mini- when the sequence of contexts is chosen stochastically and the sequence of threshold vectors is chosen adversarially.
mizer of Algorithm 2 Algorithm 3 obrains expected regret E[R(T)] =
Proof. The proof follows identically to the proof of Theorem 3.2 but without the loss in utility due to discretization. To see why, let N = Σr,,= 0 I and observe that
π (2) = arg max Ez-p P
(zz b, 0.)]
(0 1|
t=1
K
N
EEwD b, 0(0)
arg
bE
T
17


Reviews:
[{"review_id": "AAcZvmFhBa", "reviewer": "Reviewer_w4MJ", "summary": "This paper treats the problem of online learning in Stackelberg games between a learner and a follower whose type changes over time. Both the leader and the follower have access to a $d$-dimensional side / contextual information variable $z_t$, and their payoffs are determined as follows:\n- For the leader, as a function $u(z_t,a_t,b_t)$ of the context $z_t$ at time $t$ and the actions $a_t$ and $b_t$ of the leader and follower respectively.\n- For the follower, as a time-varying function $u_t(z_t,a_t,b_t)$ of the context $z_t$ at time $t$ and the actions $a_t$ and $b_t$ of the leader and follower respectively. [The variability of $u_t$ over time is what the authors dub as the leader facing \"a sequence of followers\"]\n\nThe authors assume that the context $z_t$ or the follower's payoff function $u_t$ can be determined adversarially—but not both, as in that case, it is not possible to attain sublinear (Stackelberg) regret. In terms of information available to the players, they assume that the ensemble of the follower's payoff functions is known to the leader (though not the identity of each payoff function at each instance), the leader's payoff function could be either known or unknown to the follower, and the follower observes the leader's mixed strategy at each instance (so they can best-respond to it).\n\nThe authors provide a reduction to linear contextual bandits and, depending on whether the sequence of followers or contexts is adversarial, they provide the following guarantees:\n1. *For adversarial contexts and stochastic followers:* an $\\mathcal{O}(K\\sqrt{T} \\log T)$ regret bound when the recommendation subroutine in Algorithm 1 is the OFUL algorithm of Abbasi-Yadkori et al (2011).\n2. *For adversarial follower sequences and stochastic contexts:* an $\\mathcal{O}(K^2.5 \\sqrt{T} \\log T)$ when the regret-minimizing subroutine in Algorithm 1 is instantiated to the logdet-FTRL algorithm of Liu et al (2024).\nThe authors also provide a version of these theorems for the case where the leader's utility is unknown. In that case, the above bounds continue to hold in expectation with $K$ replaced by $d A_l A_f$, where $A_l$ is the number of actions available to the leader, and $A_f$ to the follower.\n\nFinally, the authors describe how their results could be applied to the context of bidding in auctions with side information (Section 4.1) and Bayesian persuasion (Section 4.2).\n\nOverall, I found the paper's topic to be on the fringe of ICLR topics—too specialized on a setting that is not central to generalist ML/AI audiences. My \"weak accept\" recommendation reflects my cautiously optimistic belief that the paper *could* be accepted if it garners sufficient support from experts in the domain. [I am knowledgeable in the general field but not an expert; still, I am skeptical regarding the difficulty of the reduction to contextual bandits or the novelty behind the meta-use of the .recommend subroutine in Algorithm 1.]\n\nOtherwise, if the paper's contribution is not championed by an expert in the field, I believe this paper would be much better suited to a more specialized venue like EC. I will wait for the authors' rebuttal and the discussion with the rest of the review panel to converge.", "questions": "None; see above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and, as far as I could tell, the analysis is sound and the results correct. I am not a dedicated expert in this literature but, as far as I can tell, the authors' contributions are positioned properly within the relevant literature.", "weaknesses": "My main objection to the paper is the paper's learning setting: I understand that the paper's framework may be sometimes referred to as \"bandit learning\" in the context of Stackelberg games but, otherwise, the assumptions made in the paper are fairly stringent and exacting. In particular, as was mentioned above, the authors assume that the ensemble of the follower's payoff functions is known to the leader, and the follower observes the leader's mixed strategy at each instance (so they can best-respond to it). Both assumptions go against the spirit of the partial information setting in bandits where it is assumed that players only observe their payoffs / losses—and even if this term is used in a part of the Stackelberg literature, it is a misnomer, which should not be propagated in a generalist venue like ICLR (or any of the other generalist learning venues, like NeurIPS, COLT, or ICML).\n\nOther than that, as I said above, I found the paper's topic to be on the fringe of ICLR topics—too specialized on a setting that is not central to generalist ML/AI audiences.\n\nIf the paper's contributions are deemed sufficiently impactful by an expert in the field (I am not an expert on Stackelberg games and/or contextual bandits), I wouldn't find either of the above weakenesses as an obstacle to acceptance. Come what may however, I would insist on the authors' changing the \"bandit learning\" terminology to avoid clashing with established terminology in online / game-theoretic learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DW6xFnvkzA", "reviewer": "Reviewer_mHpn", "summary": "This paper studies contextual Stackelberg games with multiple follower types under bandit feedback. The authors propose a reduction to linear contextual bandits in the leader’s utility space, enabling near-optimal learning algorithms for two settings: (i) adversarial contexts with stochastic followers, and (ii) stochastic contexts with adversarial followers. In both cases, the algorithm achieves $\\tilde{\\mathcal{O}}(T^{1/2})$ regret, improving upon the previous best-known $\\tilde{\\mathcal{O}}(T^{2/3})$ rate. The framework also extends to second-price auctions and Bayesian persuasion with side information through discretized action spaces.", "questions": "1) In limitations, it is mentioned that a possible path forward towards reducing the runtime by means of smoothed analysis. Could the authors comment on the conceptual idea and how promising might be?\n\n2) How restrictive is the leader assumptions on the followers, i.e., cardinality, types, and utility, in practice? Do the authors see any path forward at relaxing these assumptions (cardinality and types)?\n\n3) Is it possible to say antyhing about the $\\mathcal{O}(1)$ approximation error in the regret due to the discretization?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work closes the gap between lower and upper regret bounds for bandit-feedback contextual Stackelberg games, achieving the optimal rate up to logarithmic factors.\n\n- The reduction to linear contextual bandits in utility space is conceptually clean and broadly applicable as shown by examples.\n\n- Extension to unknown utilities: Maintains near-optimal regret under a linearity assumption, showing robustness of the reduction.\n\n- The paper is well structured and the main theorems and algorithmic structure are well organized and technically sound.", "weaknesses": "- The per-round time of the proposed algorithm is exponential which limits the practicability of the algorithm, which is also evident from the small toy example of Sec. 3.5. \n\n- The authors assume a finite and known set of follower types and full knowledge of their utility functions (except in the linear “unknown utility” variant). \n\n- The discretization of the leader’s strategy space $\\mathcal{E}_t$ is important to keep the action space finite but introduces an approximation error on the regret that is only bounded asymptotically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BvFMflr4YW", "reviewer": "Reviewer_dzah", "summary": "This paper studies online learning for contextual Stackelberg games under bandit feedback. This paper uses a reduction that lets the leader act in a utility space and then plug in linear contextual bandits algorithms. Instantiating the reduction with OFUL gives $\\tilde{O}(\\sqrt{T})$ regret when contexts are adversarial and follower types are stochastic; a logdet-FTRL instantiation gives $\\tilde{O}\\left(K^{2.5}\\sqrt{T}\\right)$ regret when contexts are stochastic and follower types are adversarial. The paper also extends to unknown leader utilities  with $\\tilde{O}\\bigl(\\mathrm{poly}(d,K,A_\\ell,A_f)\\sqrt{T}\\bigr)$ regret.", "questions": "No specific questions", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "A clean reduction that operates in the leader’s utility space, enabling off-the-shelf contextual bandit algorithms to close the bandit-feedback gap to $\\tilde{O}(\\sqrt{T})$, with extensions to unknown utilities and applications such as auctions and Bayesian persuasion.", "weaknesses": "1. The paper restricts the leader’s strategy space to the set of approximate extreme points of contextual best-response regions. It would be more interesting to allow approximate follower responses, i.e., followers who play $\\delta$-suboptimal best responses, and analyze how such deviations affect the reduction and regret guarantees.\n2.  The main results rely heavily on prior techniques—off-the-shelf linear contextual bandit algorithms, the Contextual Follower Best-Response Region framework, and $\\delta$-approximate extreme points—so the paper’s technical novelty is unclear; overall, the contribution appears incremental, primarily composing existing components.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)