Regret Minimization in Stackelberg Games with Side Information
Authors: Keegan Harris
Steven Wu
Maria Florina Balcan
Venue: NeurIPS 2024 poster (2024)
Keywords: Stackelberg game
context
online learning
Primary area: algorithmic_game_theory
TL;DR: We introduce the problem of learning in Stackelberg games where each players' utility depends on an external context.

Abstract: Algorithms for playing in Stackelberg games have been deployed in real-world domains including airport security, anti-poaching efforts, and cyber-crime prevention. However, these algorithms often fail to take into consideration the additional information available to each player (e.g. traffic patterns, weather conditions, network congestion), a salient feature of reality which may significantly affect both players' optimal strategies. We formalize such settings as Stackelberg games with side information, in which both players observe an external context before playing. The leader commits to a (context-dependent) strategy, and the follower best-responds to both the leader's strategy and the context. We focus on the online setting in which a sequence of followers arrive over time, and the context may change from round-to-round. In sharp contrast to the non-contextual version, we show that it is impossible for the leader to achieve good performance (measured by regret) in the full adversarial setting.  Motivated by our impossibility result, we show that no-regret learning is possible in two natural relaxations: the setting in which the sequence of followers is chosen stochastically and the sequence of contexts is adversarial, and the setting in which the sequence of contexts is stochastic and the sequence of followers is chosen by an adversary.

Regret Minimization in Stackelberg Games with Side Information
Keegan Harris
Zhiwei Steven Wu School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 zhiweivêcs, cmu cmu.edu
Maria-Florina Balean
School of Computer Science
School of Computer Science Carnegie Mellon University
Carnegic Mellon University Pittsburgh, PA 15213 keeganhecs. cmu.emmee edu
Pittsburgh, PA 15213 ninamf@cs cmu. edu
Abstract
Algorithms for playing in Stackelberg games have been deployed in real-world do- mains including airport security, anti-poaching efforts, and cyber-crime prevention. However, these algorithms often fail to take into consideration the additional infor- mation available to each player (c.g. traffic patterns, weather conditions, network congestion), which may significantly affect both players' optimal strategies. We for- malize such settings as Stackelberg games with side information, in which both play- ers observe an external context before playing. The leader commits a (context- dependent) strategy, and the follower best-responds to both the leader's 's strategy and the context. We focus on the online setting in which sequence of followers arrive over time, and the context may change from round-to-round to-noudd.. In sharp contrast to the non-contextual version, we show that it impossible for the leader achieve no- regret in the full adversarial setting. Motivated by this result, we show that no-regret learning possible two natural relaxations: the setting in which the sequence of followers is chosen stochastically and the sequence of contexts is adversarial, and the setting in which contexts are stochastic and follower types are adversarial.
Introduction
is a strategic interaction between two utility- melitt-maximizing players in which one player (the leader) is able to commit to (possibly mixed) strategy before the other player (the follower) takes an action. While Stackelberg's 's original formulation was used to model economic competition between firms, Stackelberg games have been used to study wide range of topics in computing ranging from incentives in algorithmic decision-making [5] to radio spectrum utilization [32]. Perhaps the most successful application of Stackelberg games to solve real-world problems is in the field of security, where the analysis of Stackelberg security games has led to new methods in domains such as passenger screening at airports (8), wildlife protection efforts in conservation areas [10), the deployment of Federal Air Marshals on board commercial flights [8]. and patrol boat schedules for the United States Coast Guard M
Stackelberg game [30 31
However in many real-world settings which are typically modeled as Stackelberg games, the payoffs of the players often depend additional contextual information which is not captured by the Stackelberg game framework. For example, in airport security the severity of an attack (as well as the "benefit" of successful attack to the attacker) depends factors such the arrival and departure city a flight, the whether there are VIP passengers on board, and the amount of valuable cargo on the aircraft. Additionally, there may be information in the time leading up the attack attempt which may help the security service determine the type of attack which is coming
[17] For instance, in
wildlife protection settings factors such the weather and time of year may make certain species of
See 27 for an overview of other application domains for Stackelberg security games.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

wildlife easier or harder to defend from poaching, and information such as the location of tire tracks may provide context about which animals are being targeted. As result, the optimal strategy of both the leader and the follower may change significantly depending on the side information available.
Overview of our results. In order to capture the additional information that the leader and follower may have at their disposal, we formalize such settings as Stackelberg games with side information. Specifically, consider a setting in which a leader interacts with a sequence of followers in an online fashion. At each time-step, the leader gets to see payoff-relevant information about the current round in the form of a context. After observing the context, the leader commits to mixed strategy over finite set of actions, and the follower best-responds to both (I) the leader's ' strategy and (2) the context in order to maximize their utility. We allow the follower in each round be one of K rypes. Each follower type corresponds to a different mapping from contexts, leader strategies, and follower actions to utilities. While the leader may observe the context before committing to their mixed strategy, they do not get to observe the follower's 's type until after the round is over. Under this setting, the goal of the leader is to minimize their regret with respect to the best policy (i.e. the best mapping from contexts to mixed strategies) in hindsight, with respect to the realized sequence of followers and contexts.
We show that in the fully adversarial setting (i.e. the setting in which both the sequence of contexts and follower types is chosen by an adversary), no-regret learning is not possible, even when the policy class highly structured. We show this via a reduction from the problem of online linear thresholding, for which it is known that no no-regret learning algorithm exists. Motivated by this impossibility result, we study two natural relaxations: (1) setting in which the sequence of contexts is chosen by an adversary and the sequence of follower types is chosen stochastically, and (2) a setting in which the sequence of contexts chosen stochastically and the sequence of follower types is chosen by an adversary.
In the stochastic follower setting we show that the greedy algorithm (Algorithm [T. which estimates the leader's expected utility for the given context and plays the mixed strategy which maximizes their estimate, achieves no-regret as long as the total variation distance between their estimate and the true distribution is decreasing with time. We then show how instantiate the leader's estimation procedure so that the regret of Algorithm 1 is (min K, A } / T (T))(T)) where T the time horizon, K is the number of follower types, and Ay is the number of follower actions. In the stochastic context setting, we show the leader can obtain O ((/TT l''llog(T (T') + K) regret by playing Hedge over finite set of poli- cies (Algorithm D. An important intermediate result in both settings is that it is (nearly) without loss of generality to consider leader policies which map to finite set of mixed strategies &g. given context z
Next, we extend our algorithms for both types of adversary to the setting in which the leader does not get to observe the follower's 's type after each round, but instead only gets to observe their action. We refer to this type of feedback as bandit feedbuck. Both of our extensions to bandit feedback make use of the notion of a barycentric spanner [4] special basis under which bounded loss estimators may be obtained for all leader mixed strategies. In the bandit stochastic follower setting, we use the fact that in addition to being bounded, a loss estimator constructed using barycentric spanner has low variance, in order to show that natural extension of our greedy algorithm obtains ( regret. We also make use of barycentric spanners in the (bandit) stochastic context setting, albeit in different way. Here, our algorithm proceeds by splitting the time horizon into blocks, and using barycentric spanner to es- timate the leader's utility from playing according to a set of special policies in each block. We then play Hedge over these policies to obtain (12333) leader regret 3) See Table
for a summary of our results.
Related work. Letchford et al. 21 consider the problem of learning the leader's optimal mixed strategy in the repeated Stackelberg game setting against a perfectly rational follower with an unknown payoff matrix. Peng et al. 23 study the same setting as Letchford et al. [21]. They provide improved rates and prove nearly-matching lower bounds. Learning algorithms recover the leader's optimal
mixed strategy have also been studied in Stackelberg security games S 7 26 6].
Our work builds off of several results established for online learning in (non-contextual) Stackelberg games in Balcan et al. [5]. In particular, our results in Section and Appendix (C.2 may be viewed as a generalization of their results to the setting in which the payoffs of both players depend an external context. Roughly speaking, Balcan et al. ( show that it without loss to play Hedge over a finite set
?Specifically, a leader who is restricted to playing such policies incurs negligible additional regret. 'This is similar to how Balcan et al. [5] use barycentric spanners to obtain no-regret in the contexttll setting, although more care must be taken to handle the side information present in our setting.
2

---

Full Feedback
Bandit Feedback
Q(T)
(2(T)
Fully Adversarial
(Section
(Section
Stochastic Followers, Adversarial Contexts
O (min (K, A (Section 4.1
log
KK2/3/ A A 1 log
[
(Appendix C.1
Stochastic Contexts,
(VKKT log + K)
0 K | /2/3///// log 1/3
Adversarial Followers
(Section 4.2
(Appendix C.2
Table I: Summary of our results. Under bandit feedback, we consider relaxed setting in which only the leader's utility depends on the side information.
of mixed strategies in order to obtain no-regret against an adversarially- sequence of follower types. In order to handle the additional side information available our setting, we instead play Hedge over finite set of policies, each of which map to finite set of (context-dependent) mixed strategies. However, the discretization argument is more nuanced in our setting. In particular, it not without loss of generality to consider a finite set of policies. As result, need to bound the additional regret incurred by the leader due to the discretization. More recent work on learning in Stackelberg games provides improved regret rates in the full feedback [9] and bandit feedback [6] settings, and considers 13 and followers who respond to calibrated predictions [4].
the effects of non-myopic followers
Lauffer et al. (20) study a Stackelberg game setting in which there is an underlying (probabilistic) state space which affects the leader's s rewards, and there is a single (unknown) follower type. In contrast, we study setting in which the sequence of follower types and/or contexts may be chosen adversarially. Sessa et al. (55 study a repeated game setting in which the players receive additional information (i.e. context) at each round, much like in our setting. However, their focus is on repeated normal-form games, which require different tools and techniques to analyze compared to the repeated Stackelberg game setting we consider. Other work has also considered repeated normal-form games which change over time in different ways. In particular, Zhang et al. [3], Anagnostides et al. B study learning dynamics in time-varying game settings, and Harris al. [16] study meta- meta-learning setting in which the game being played changes after a fixed number of rounds.
Finally, our problem may be viewed is special case of the contextual bandit setting with adversarially- chosen utilities [28] (29 24], where the learner gets to observe "extra information" the form of the fol- lower's type (Section 4 or the follower's action (Section 5). However, there is much to gain from tak- ing advantage of the additional information and structure that is present in our setting. Besides having generally worse regret rates, another reason not to use off-the-sheil adversarial contextual bandit algo- rithms in our setting is that they typically require either (1) the learner to know the set of contexts they will face beforehand (the transductive setting; Syrgkanis et al. (28 22), Rakhlin and Sridharan (24) (2) for there to exist a small set of contexts such that any two policies behave differently on at least one context in the set (the small separator setting: Syrgkanis al. (28) We require such assumptions.
2 Setting and background
Notation. We use [N] == f1....,NY to denote the set of natural numbers up to and including
N T N and cl(P) to denote the closure of the set P. x[a] denotes the a-th component of vector x, and ((A) denotes the probability simplex over the set A. TV q)
[<<):)<(<<)) is the total variation distance between distributions p and q, and T. [r] R[x] Ft. shorthand for the expected value of the random variable conditioned on the filtration up to (but not including) time t. All proof' may be found in the Appendix. Finally, while we present our results for general Stackelberg games with side information, our results are readily applicable to the special case of Stackelberg security games with side information.
Our setting. We consider a game between a leader and sequence of followers. In each round t E [T', Fl The leader moves first by playing some mixed strategy x, X C R over set of (finite) leader actions A, i.e., x, E A(A). The size of A
Nature reveals a context 2 E Z S Rdd to both players
'E.g in airport security, 2: may contain information about arrival and departure times, number of passengers, valuable cargo, etc. In cyber-defense, 2; may be list of network traflic statistics.
3

---

is A == [A]. Having observed the leader's mixed strategy, the follower best-responds to both x; and Z, by playing some action a E Ay, where A is the (finite) set of follower actions and A, := Ayyl Definition 2.1 (Follower Best-Response). Follower f's best-response context z and mixed strategy E arg EAy Emex x uy (z, at, at). where us 2 x A X A₁ + [0, 1] is
x is follower f utility function.. In the case of fies, we assume that there is a fixed and known ordering over actions which determines how the follower best-responds, i.e. if > a' for follower will break ties between a and a' in favor of a
a, a' E As then the
We allow for the follower in round & (denoted by (t) to be one of K 2 1 follower types (a ........k).... {aK)} (where K < T). Follower type at)) is characterized by utility function (at0) 2 A A + [0, 1), i.e. given context z, leader action at and follower action af- follower of type (1)) would receive utility (g (z, a, ay). We assume that the set of all possible follower types and their utility functions are known to the leader, but that the follower's type at round t is not revealed to the leader until after the round is over. We denote the leader's utility function by u Z x A x As + [0, 1] and assume it is known to the leader. We often use the shorthand u(z, x. ay) = Em x [ai] a(z at a ) to denote the leader's i expected utility of playing mixed strategy x under con- text z against follower action a,. Follower ft 's expected utility u (z, x, af) is defined analogously.
leader policy π: 2 + X is a (possibly random) mapping from contexts to mixed strategies. If the leader using policy ni in round and observes context 22, their strategy x₁ is given by x, (r())). Definition 2.2 (Optimal Policy). Given sequence of followers fi.....fr frr and contexts Z1 2I, the strategy given by the leader's 's optimal-in-hine hinniissighh policy for context z is x (z) E arg maxxex Et= u(z, by, x)) (z, = 2].
We measure the leader's performance against the optimal policy via the notion of contextual Stackelberg regret (regret for short).
Definition 2.3 (Contextual Stackelberg Regret). Given a sequence of followers fi...., fr and contexts Z1,...,5 Zr, the leader's contextual Stackelberg regret R(T)
Ee ulzz,==" (2,), by, (Zi, ",, (Z+))) - u u(z,; Xt, by (Zt, x.)), where XI. xI....,XX XT is the sequence of mixed strategies played by the leader.
If an algorithm achieves regret R(T) = o()), we say that it is a no-regret algorithm. We consider three ways in which Nature can select the sequence of contexts/folloowrss:
1. If the sequence of contexts (resp. follower types) are drawn i..dd from some fixed distribution, we say that the sequence of contexts (resp. follower types) are chosen stochastically.
2. If Nature chooses the sequence of contexts (resp. follower types) before the first round order to harm the leader (possibly using knowledge of the leader's 's algorithm), we say that the sequence of contexts (resp. follower types) are chosen by a non-adaptive adversary.
3. If Nature chooses context z, (resp. follower fe) before round in order to harm the leader (possibly using knowledge of the leader's algorithm and the outcomes of the prior t - 1 rounds), we say that the sequence of contexts (resp. follower types) are chosen by an adaptive adversary.
Our impossibility results in Section Iitiiionnhoo. hold when both the sequence of contexts and the sequence of follower types are chosen by either type of adversary. Our positive results in Section hhold when either the sequence of contexts or the sequence of follower types are chosen by either type of adversary (and the other sequence is chosen stochastically). Our extension to bandit feedback (Section 5] where the leader only gets to observe the follower's best-response instead of their type) holds whenever one sequence is chosen by non-adaptive adversary and the other sequence is chosen stochastically.
3 On the impossibility of fully adversarial no-regret learning
We begin with a negative result: no-regret learning is not possible in the setting of Section 2i the sequence of contexts and the sequence of followers is chosen by an adversary. While this is not necessarily surprising given that Definition 2.3 allows for the optimal policy x² to be arbitrarily
'It is without loss of generality to assume that the follower's best-response pure strategy.

---

Regret Minimizer Online
Linear Thresholding
2. = h2((e)
Regret Miniimierr for Stackelberg Games with Side Information
N2 (1))
Noture
4 = by(t))
3.y.
Figure 1: Summary of our reduction from the online linear thresholding problem. At time E [T]. (1.) the learner observes point w/. (2.) the learner takes a guess 9t. and (3.) the learner observes the true label 3t- Given regret minimizer for our setting, we show how use in a black-box way (by constructing functions h1, h22 h3) to achieve no-regret the online linear thresholding problem.
complex, we show that this result holds even when the policy class to which n² belongs is highly structured. We show this via reduction to the online linear thresholding problem, for which it is known that no-regret learning is impossible.
Online linear thresholding. The online linear thresholding problem is repeated two-player game between a learner and an adversary. Before the first round, an adversary chooses cutoff E [0. 1] which is unknown to the learner. In each round, the adversary chooses a point Wt E [0. 1] and reveals to the learner. Wt assigned label y/: 1 if Wt > 8 and label y: = -1 otherwise. Given was the learner makes guess 9r E [0, 1] (the probability they place 3/+ = 1). and receives utility WOLT (Wi, 9t) 9: 1/ = 1] +
gc) (, = -1}. The learner gets to observe ye after round t is over. The learner's policy TT [0, 1] - [0, 1] is mapping from points in [0. 1] to guesses in [0, 1]. The optimal policy n² makes guess π (w)) = wr > s and π (ww) = otherwise. The learner's regret after 7 rounds is given by (our(7)= -T T Ei= uoLT (We, since the optimal policy achieves utility every round. In order to prove a lower bound on contextual Stackelberg regret in our setting, we make use of the following well-known lower bound regret in the online linear thresholding setting (see e.g. (2)..
Lemma 3.1. Any algorithm suffers regret ROLT(T) SI(T) in the online linear thresholding problem when the sequence of points wI....,wy .T chosen by an adversary.
Theorem 3.2. If an adversary can choose both the sequence of contexts Zi...., Zr and the sequence followers f1....: fr. algorithm achieve better than Q(T)) contextual Stackelberg regret in expectation over the internal randomness of the algorithm, even when π." is restricted to come from the sel of linear thresholding functions.
The reduction from online linear thresholding proceeds by creating an instance of our setting such that the sequence of contexts 21..... 21 correspond to the sequence of points wi,... ,.r encountered by the learner, and the sequence follower types fi...., fr correspond the sequence of labels .1;-.., ,rr We then show that no-regret algorithm in the online thresholding problem can be ob- tained by using an algorithm which minimizes contextual Stackelherg regret on the constructed game instance as a black box. However this is contradiction, since by Lemma 3.1 the online thresholding problem is not online learnable by any algorithm. See Figure for a visualization our reduction.
Intuitively, this reduction works because the adversary can "hide" information about the follower's type fe the context ž₁ However, there exists a family of problem instances in which learning this relationship between contexts and follower types as hard as learning the threshold in the online linear thresholding problem, for which no no-regret learning algorithm exists by Lemma
4 Limiting the power of the adversary
Motivated by the impossibility result of Section B we study two natural relaxations the fully adver- sarial setting: one in which the sequence of followers is chosen stochastically but the contexts cho- sen adversarially (Section[4.) I and one in which the sequence contexts is chosen stochastically but followers are chosen adversarially (Section[4.2) In both settings allow the adversary to be adaptive.
important structural results for both Section 4.1 and Section 4.2 is that for any context E 2, the leader incurs only negligible regret by restricting themselves to policies which map to mixed
5

---

strategies in some finite (and computable) set Ez. In order to state this result formally, we need to introduce the notion of a contextual best-response region, which is generalization of the notion of best-response region in (non-contextual) Stackelberg games (e.g. (1 5))-
Definition 4.1 (Contextual Follower Best-Response Region). For follower type a follower action as E As. and context z E Z, let Xz(a aa) S X denote the set of all leader mixed strategies such that a follower of rype (1) best-responds to all x E X2(a .a)) by playing action as under context 2, iee, (a af) = {x E X' bat (2, x) = at}
Definition 4.2 (Contextual Best--Rsponne Region). For a given function a : (a(1))... ....,,a(k)) [k)] + AJ. let (d) denote the set of all leader mixed strategies such that under context z, a follower of type (0) plays action a ( for all E [K], i.e. X²(o) ( ((a())).
For a fixed contextual best-response region X₂ (a), we refer to the corresponding a as the best- response function for region X₂ (o), as it maps each follower type to its best-response for every leader strategy (x) ). We sometimes use ((2.x) to refer to the best-response function associated with mixed strategy x under context z, and we use Eg to refer to the set of all best-response functions under context z. Note that |g1 S AA for any context z E Z. This gives us an upper-bound on the number of best-response regions for given context.
One useful property of all contextual best-response regions is that they are convex and bounded polytopes. To see this, observe that every contextual follower best-response region (and therefore every contextual best-response region) is (1) a subset of A and (2) the intersection of finitely- many half-spaces. While every (z) is convex and bounded, it is not necessarily closed. If every contextual best-response region were closed, it would be without loss of generality for the leader to restrict themselves to the set of policies which map every context contextual best-response region. In what follows, we show that the leader does not "lose too much" (as measured by regret) by restricting themselves to policies which map some approximate extreme point of a contextual best-response region.
extreme point of some
Definition 4.3 (ō- (6-aproxxmmate extreme points). Fix context 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 E (AAi) that is an extreme point of cl( (o)),
(6) if x E X2(a). Otherwise there is some x' E (6) such that x' E (o) and ||x' x|11 S 6.
Note that Definition 4.3 is constructive, We set d = ((+) so that the additional regret from only considering policies which map to points in 2 is negligible. As result, we use the shorthand &g == Ez(g) throughout the sequel. The following lemma is a generalization of Lemma 4.3 in Balcan al. [5] to our setting, and its proof uses similar techniques from convex analysis.
Lemma 4.4. For any sequence of followers fr. and any leader policy π, there exists a policy [() Z + UzEZ&z that, when given context z, plays a mixed strategy in Eg and guarantees that Et=
by, (zi, x (()))) u(z,, x(E) (Z)). bj, (Zi, ((E) (z:)) S Moreover, the same result holds in expectation over any distribution over follower types F.
Since we do not restrict the context space to be finite, the leader cannot pre-compute Eg for every z E Z before the game begins. Instead, they can compute Ex, in round t before they commit to their mixed strategy. While Ex, is computatable, it may be exponentially large in A, and K. However this is to be expected as Li et al. [2 show that in its general form, solving the non-contextual version of the online Stackelberg game problem is Na-Hard.
4.1 Stochastic follower types and ad adversarial contexts
In this setting we allow the sequence of contexts be chosen by an adversary, but we restrict the sequence of followers to be sampled i.i.d. from some (unknown) distribution over follower types F. When picking context 2,, we allow the adversary to have knowledge of F and f1...., : ft-1, 1. but not ft. Under this relaxation, our measure of algorithm performance is expected contextual Stackelberg regret, where the expectation is taken over the randomness in the distribution over follower types.
Definition 4.5 (Expected Contextual Stackelberg Regret). Given a distribution over followers F and sequence of contexts Zı..... .Zr. the leader's 's expected contextual Stackeleberg regret is E. [[( := R.f.y...-r=r [Ei u(z,, x" (Zx), by. (Zt, x² (z:)) - u(2;, xt, by, (Ze, x,)),, where nt is the optimal policy given knowledge of ......, ZT and F.

---

Algorithm I: Learning with stochastic follower types: full feedback
Input: P1
for 1 = I....,,? do
Observe 2,, commit to Xt (Ze))) arg maxxess E, [[(uzzz, by, (zz, x)] (Equation I Receive utility u(ze, ai, by. (z)) where di X2, and observe follower type fc.
Update P. + Pi+1
end
setting, the utility for policy π may be written as Be.....n Σ u(ze, (()), by. (2e, ((()))) proceeds by
Under
this
Σi= E f [Ra [u(ze, x (2+), ) by. (Z,, x (z+)))]
Our algorithm (Algorithm
estimating the inner expectation
Ee(u(ze, π (2z),b, (Ze, (Zx)))] as
Belu(ze, (2z)) by, (ze, (2.))) f [(zz,=(())) (zz)) as ay) (dp (2), T- (z))) aa)
(1)
and acting greedily with respect to our estimate. Here (b (z,, क (2,)) - ay) is the (estimated) probability that the follower's best-response is a,. given context z, and leader mixed strategy π (z,). As we will see, different instantiations of Pe will lead to different regret rates for Algorithm However, before instantiating Algorithm| [ with a specific estimation procedure, we provide general result which bounds the regret of A Algorithm] Tin terms of the total variation distance between the sequence { cejr) and the true distribution p.
Theorem 4.6. Let p(z, x) == [p(b,, (z,x) = ay)]aa EA, and (z. x) == pe (z.x) = a a))layEAr
The expected contextual Stackelberg regret (Definition 4.5) of Algorithm 7 satisfies
B[R(T) S 1+2 Σ By A
(E))), [V(p(z, n [TVpt,
(z n TVV())
Pr T. (z,))))
Theorem 4.6 shows that the regret of Algorithm|] is proportional to how well it estimates p(z, x) over time (as measured by total variation distance), (1) the sequence of contexts chosen by the adversary and (2) the sequence of mixed strategies played by Algorithm and the (uear-)opting policy (F) While we instantiate Algorithm [ follower actions, Theorem 4.6 opens the door provide meaningful regret guarantees in settings in which there are infinitelymmany follower types and/or follower actions. estimation procedure in Algorithm iin in two different ways to get end-to-end regret guarantees. First, the leader can get regret O(K /Tlo T) by estimating the distribution of follower types directly.
in the setting where there are finitely-mant
follower types and
T We now instantiate the
Corollary 4.7. If p: = (fe = (NEKK) Pf+1(f = (9) Er 1(fr = a.0,, and (i(f = a (1)
for E [K]. then the regret of Algorithm satisfies [[R(T))
The leader can obtain a complementary regret bound of O(A, T log T) if they instead estimate the probability that the follower best-responds with action a, Ay. given particular context z and leader mixed strategy x In what follows, we use 1 (
{0, 1] refer to the indicator vector whose i-th component is 1 (a(x))((a = aay.iie i.c. the indicator that a follower of type (i) best-responds context and mixed strategy x by playing action aj.
Corollary 4.8. If (z(
(e+1(A(otnn)=a)
=
E 1 (b,, a), and pi (1(o))))))) As for as A,, then the regret of Al-
gorithm 7 Satisfies E[R(T)) O(A,yTlog(T)
4.2 Stochastic contexts and adversarial follower types
We now consider the setting in which the sequence of contexts are drawn i.i.d. from some unknown distribution P and the follower ft is chosen by adversary with knowledge of P and Zi...., 2;-1,
AAll that is required to run Algorithm in particular problem instance is an oracle for evaluating Eg [u(z,, x, by, (z, x)] and updating p..
In general K has dependence Ay. and vice versa.

---

Algorithm 2: Learning with stochastic contexts: full feedback
Input: Set of weights Ω
Let qı [ [-) == 1. Pil [1 [-[]]]=== == [ for all (l E 11 == (T(W)) JWEB
for t = ... do
Sample Te Pt. are To (Zz), receive utility u(ze, 01,2, by, (TT (Zi)),, observe type f..
For each policy x(0) E II, compute [][T[[]] == -u(ze, (((w) (1)) by. (Zt, (rw) (2+)) and set
q:+1 [rr (W) = exp(-1 -p E le( ()),))))) p [3] = q++1 (a // Enwwee a1+1 ( (w))).
end
but not Z,. As was the case in Section 4.1 we consider a relaxed notion of regret which compares the performance of the leader to the best policy in expectation, although now the expectation is taken with respect to the distribution over contexts P.
Definition 4.9 (Expected Contextual Stackelberg Regret, II), Given distribution over contexts P and a sequence of followers JI....;JT. ST, the leader's 's expected contextual Stackeleberg regret is
B(R(()) :- EE
Σ u(zi, xt" (Zx), by, (Ze; (Zx))) - ulzz, Xe, by (Zt, xx))
where मO is the optimal policy given knowledge of J IT and P.
Our key insight is that when the sequence of contexts is generated stochastically, to obtain no-regret it suffices to (1) play standard, aff-the-shelf online learning algorithm (e.g. Hedge) over a finite (albeit sroonentially-lagee set of policies in order to find one which is approximately optimal and then (2) bound the resulting discretization error.
Lemma 4.10. When the sequence of contexts is determined stochastically, the expected utility of any fixed policy π may be written as
T
K Σ
T Σ
Ex ZT Σ
u(ze, (Z.), by (e. 7 (2))))
Ex(u(z, T b (2, (())))
Ex
[1 - a(11)
Using Lemma 4.10 we now show that it suffices to play Hedge over finite set of policies II in order for the leader to obtain no-regret (Algorithm 2 The key step in our analysis to show that the discretization error is small for our chosen policy class II For a given weight vector w E R let ( (z) ;= arg maX ΣX1 u(z, x, boto (z, x)) wli]. For given set of weight vectors Ω we set TT to be the induced policy class, i.e. IT (T(W)]WER
Jwen-
Theorem 4.11. !fQ = {w : w WEAK, T wii N, Vi E [K] and 11 V log II
T then Algorithm
obtains expected contextual Stackelberg regret (Definition 4.9 B[R(T)) O (VKTlog log + K).
We conclude by briefly comparing our results with those of the non-contextual Stackelberg game set- ting of Balcan et al. [5] In particular, the setting of this subsection may be viewed as a generalization of the setting of Balcan et al. [5) in which the leader and follower utilities at time also depend on aerchastically-geeraate
context 2,. When |z| 1, we recover their setting exactly. Under their non-contextual setting, there is only one set of approximate extreme points &x, and so we write the = &g. Here it suffices to consider the set of constant "policies" which always map to of the (approximate) extreme points in E. Plugging this choice of II into Algorithm 2 algorithm (and therefore also their regret rates) exactly.
we recover their
However, it is also worth noting that more care must be taken to obtaín regret guarantees against an adaptive adversary in our setting compared to the non-contextual setting of Balcan et al. [5] In particular, we need to bound the discretization error due to considering a finite set of policies, but is without loss of generality to consider finite set of mixed strategies in the non-contextual setting.
'Interestingly, there is discretization error if the sequence of follower types is chosen by non-adaptive adversary. To see this, one can repeat the proof of Lemma using the fact that fi...., fo is independent from realized draws .., zr when the sequence follower types chosen by a non-adaptive adversary. Indeed, our notion of contextual Stackelberg regret stronger than their non contexxttl version of regret.
8

---

Openten)
(a) Non-stochastic contexts, stochas- (b) Stochastic contexts, non- (c) Stochastic contexts, stochastic follower types.
tic follower types.
stochastic follower types.
Figure 2: Cumulative average reward of Algorithm 1, Algorithm 2, and the algorithm of Balcan et al. S
(which does not take side information into consideration) over five runs in synthetic data setup. Shaded regions represent one standard deviation.
4.3 Simulations
We empirically evaluate the performance of Algorithm and Algorithm 2 on synthetically generated eeenerrte data. We consider setup in which K = 5, = A, 3, and the context dimension 3. Utility functions are linear in both the context and player actions, and are sampled u.a.r. from [-1, 1]ax3x3
We compare the cumulative reward of our algorithms to each other and the algorithm of Balcan et al. [5] (which does not leverage side information) as baseline. We simulate non-stochastic context arrivals in Figure 2a by displaying the same context for T/4 time-steps in a row. Follower types are chosen u.a.r. from each of the five follower types. In Figure [bb] contexts
generated stochastically by sampling each component u.a.r. from [-1, 1]. Followers are chosen non-stochastically by deterministically cycling over the five types. In Figure [c] both contexts and follower types
chosen stochastically. Specifically, contexts are generated as in Figure 2b and follower types are generated as in Figure
We find that Algorithm and A perform similarly across instances, and both significantly out-perform the baseline of Balcan et al. [5]. It would be interesting to find instances for which Algorithm (resp. Algorithm 2 performs poorly whenever followers (resp. contexts) are chosen non-stochastically
5 Extension to bandit feedback
We have far assumed that the leader gets observe the follower's type after each round. However this assumption may not always hold in real-world Stackelberg game settings. For example, in cyber security domains it may be hard deduce the organization responsible for failed cyber attack. In wildlife protection, a very successful poacher may never be seen by the park rangers. Instead, the leader may only be able observe the action the follower takes at each round. Following previous work on learning in non-contextual Stackelberg games, we refer to this type of feedback as bandit feedback. What can say about the leader's ability learn under bandit feedback when there side information?
While our impossibility result of Section 3 iimmediately applies this more challenging setting, our algorithms from Section not. This because we can no longer compute quantities such as 1 (f: = a ( or by, (ze, x) for an arbitrary mixed strategy x from just follower ft's action alone. We still assume that the follower is one of K different types, although f. is now never revealed to the leader.
We allow ourselves two relaxations when designing learning algorithms which operate under bandit feedback. First, while the leader's 's utility function may still depend on the context Z,, we assume that the follower's utility is function of the leader's mixed strategy X; alone, i.e. (z, x, ay) 2 a for all 2. This allows us to drop the dependence on Z₁ from both the follower's best response and the set of approximate extreme points, i.e. by(2, x) becomes by(x) and & becomes E. Furthermore, our definitions of contextual follower best-response region (Definition 4.1 and contextual best-response region (Definition 4.2) collapse their non-contextual counterparts. Depending the application domain, the assumption that only the leader's 's utility depends the side

---

information may be reasonable. For instance, while an institution would prefer that a server with less traffic is hacked compared one with more, hacker might only care about the information hosted on the server (which may not be related to network traffic patterns). Second, we design algorithms [0 Despite these relaxations,
with regret guarantees which only hold against a non-adaptive adversary
the problem of learning under bandit feedback still remains challenging because of the exponentially large size of E. While a natural first step is to estimate p(b,, (x) = ay) (i.e. the probability that follower at round t best-responds with action as when the leader plays mixed strategy x) for all x &E& & and a E Ay, doing so naively would take exponentially-man many rounds, due to the size of E.
Building off of results in the non-contextual setting of Balcan et al. [S), we leverage the fact that the leader's 's utility for different mixed strategies not independent. Instead, they are linearly related through the frequency of follower types which take a particular action, given a particular leader mixed strategy. Therefore, suffices to estimate this linear function (which can be done using as few as K samples) to get an unbiased estimate of p(b,, f. (x) = =a)) for any x E & and a AA-- Borrowing from the literature on linear bandits, we use a barycentric spanner Hp(b,, (x) = aa)) Ixeg in both partial adversarial settings we consider. A barycentric spanner for compact vector space W is a special basis such that any vector in W may be expressed as a linear combination of elements in the basis, with each linear coefficient being in the range !-1,
to estimate
In Appendix C.1 we use the property that estimators constructed using barycentric spanners have algorithm achieves O(K2/3 A2 log2/3 T) expected contextual Stackelberg regret in the setting with stochastic follower types and adversarial contexts. Specifically, our algorithm (Algorithm 3 plays special set of K mixed strategies N times each, then uses barycentric spanners to estimate (p:(1 (a(xx)=a ( Ja,EA, for all x E X' and z E 2, after which Algorithm
low variance to show that an
3 plays greedily like in Section 4.1
In Appendix C.2 we use the property that estimators constructed using barycentric span- ners are bounded to design a reduction to our algorithm in Section 4.2 which achieves O(KA)/5 T)) expected contextual Stackelberg regret whenever the sequence of contexts is chosen stochastically and the sequence of follower types is chosen by an adversary. Finally, while it may be possible to obtain O(vT) regret without using barycentric spanners, this would come at the cost of linear dependence on |E] (and therefore an exponential dependence on K and Ay) in regret.
6 Conclusion
We initiate the study of Stackelberg games with side information, which despite the presence of side information in many Stackelberg game settings, has not received attention from the community. We focus on the online setting in which the leader faces a sequence of contexts and follower types. We show that when both sequences are chosen adversarially, no-regret learning not possible even for highly structured policy classes. When either sequence is chosen stochastically, we obtain algorithms with Ó ((VT) regret. We also explore an extension to bandit feedback, in which we obtain ( regret in both settings. There are several exciting avenues for future research; we highlight two below.
1. Intermediate forms of adversary. The two relaxations of the fully adversarial setting that we con- sider, while natural, rule out the leader learning about the follower's 's type from the context. Although we prove that learning is impossible in the fully adversarial setting, our lower bound does not rule out, e.g. settings where the mapping from contexts to follower types has finite I Littlestone dimension. It would be interesting further explore this direction to pin down when no-regret learning is possible.
O(T)/2) regret under bandit feedback. Bernasconi et al. 6 obtain O(T1/2) regret when learning in non-contextual Stackelberg games under bandit feedback against an adversarially-chose sequence of follower types via a reduction to adversarial linear bandits. However, applying similar steps to Bernasconi et al. in our setting results in a reduction to a generalization of the (adversarial) contextual bandit problem for which we are not aware of any regret minimizing algorithm. Nevertheless, we view exploring whether Ö(T2/2) contextual Stackelberg regret is possible under bandit feedback natural and exciting future direction.
We hypothesize that our results in this section could be extended to hold against an adaptive adversary by using more clever exploration strategies.
10

---

Acknowledgements
This work was supported in part by NSF Grants CCF-1910322 #1763786, and by an NDSEG fellow- ship. The authors would like to thank the anonymous reviewers for valuable feedback, and Martino Bernasconi, Matteo Castiglioni, and Andrea Celli for helpful discussions surrounding related work.
References
[1] Bo An, Fernando Ordóñez, Milind Tambe, Eric Shieh, Rong Yang. Craig Baldwin, Joseph DiRenzo III, Kathryn Moretti, Ben Maule, and Garrett Meyer. A deployed quantal response- based patrol planning system for the us coast guard. Interfaces, 43(5):400-444 2013.
[2] Bo An, Milind Tambe, and Arunesh Sinha. Stackelberg security games (ssg) basics and application overview. Improving Homeland Security Decisions, page 485, 2017.
[3] Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On the convergence of no-regret learning dynamics in time-varying games. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Ad- vances in Neural Information Processing Systems 36: Annual Conference on Neural In- formation Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL httpt:/ppppprrrs witeerrssnnssss...........se nips cc/ ccppaper_r.. faaperfflest. wiwes/lllppppe faapsffflleepppper/aaaapeasa 2223//2222///// htt.ceeer5aabb.eeeeeeaaaa2222aa.
Conference html
[4] Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing.
J. Compul. Syst. Sci., 74(1):97-114, 2008, doi: 10.1016/J.JCSS. (0016//.JCSS.2000.44.00000 2007.04.016. URL https
7 //doi.org/10.. 1016/]111jjj- jcas 2007 04.
[5] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Commitment Online learning in stackelberg security games. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015, pages 61-78.
without regrets:
ACM, 2015. doi: 01114452774448.27744777 URLhttps::/ //doi org/ 1145/2764468
2764478
[6] 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 Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23- 29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 2164 2183. PMLR, 2023. StRhhtps:: /ttp:::///rrcooe http:///poeeee..s.eeeee/ mlr press/v202/ bernascon laannasconi2aa...m 23a. html
[7] Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Learning optimal commitment to overcome insecurity. pages 1834, 2014. URL https://procceciing wtw.oedddinnnnn...iis..... www.ies..p.... cc/ paper/2004/hash// catpaahhccccaa4442771111155
(wte33991169eea. Awwtract..ttttt. html
[8] Matthew Brown, Arunesh Sinha, Aaron Schlenker, and Milind Tambe. One size does not fit
all: A game-theone thee-ttheretic approach for dynamically and effectively screening for threats. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12- 17, 2016, Phoenix, Arizona, USA, pages 425 431. AAAI Press, 2016. doi: 10. 16099/AAALV3011 10023. URL https:://do:ooi org 10. 1609/ aaaii 10023
[9] Constantinos Daskalakis and Vasilis Syrgkanis. Learning in auctions: Regret hard, envy is easy. Games Econ. Behav. 134:308-3433 2022. doi: 1.11016J..EBB.2022.0000000 URL
htttps://dot httpp::///oi.o///1.... 1016/0016jji0 geb. 2022. 00.22.33.00 03.001
[10] Fei Fang, Peter Stone, and Milind Tambe. When security games go green: Designing defender strategies to prevent poaching and illegal fishing. In Qiang Yang and Michael J. Wooldridge, editors, Pruceedings of the Twenty- Fourth International Joint Conference on Artificial Intelli- gence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 2589-2595. AAAI Press, 2015. URL http: //ijcaia....//////// org/ Abstract/15/355
[11] Anupam Gupta. 14: Online learning: Experts and bandits. 15850: Advanced Algorithms course notes, 2023.
11

---

[12] Nika Haghtalab. Lecture 12:
Introduction to online learning 2. CS6781: Theoretical Foundations of Machine Learning course notes, 2020.
[13] Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. Learning in stackelberg games with non-myopic agents. In David M. Pennock, llya Segal, and Sven Seuken, editors, EC :22 The 23rd ACM Conference on Economics and Computation, Boulder, CO. USA, July 11- 15, 2022, pages 917-918. ACM, 2022.
doi: 10.1 10.1145/3494486333833000 URL
https: //dps:://doii org/10. /4944/44 3538308
[14]
Nika Haghtalab,
Chara Podimata, and Kunhe Yang. Learning optimal commitments against calibrated agents.
Calibrated stack-
elberg games:
2023.
URL http://papers.ee Conf html
ct/ http:/pppr__fffeeee wttpeee/ppppe////////eeeee wwwp:/ssbb--tttaat----o--
[15] Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, and Mary Wootters. Strategic
classification. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations
in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 111-122. ACM, 2016. doi: 10.1 10.1145/284072. 2840030 JtLttts:::/doo org/10/ 10. 1145/2840728 2840730
[16] Keegan Harris, loannis Anagnostides, Gabriele Farina, Mikhail Khodak, Steven Wu, and Tuomas Sandholm. Meta-learning in games. In The Eleventh International Conference on Learning Representaaiions, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. www.rruiainiuuHaaaaahahhDD
URL httppss//oppeneevii..eeett//////
[17]
Indiana Intelligence Fusion Center lifc. 8 signs of terrorism, Jul 2022. URL hattps://wwzz in
[18] Manish Jain, Jason Tsai, James Pita, Christopher Kiekintveld, Shyamsunder Rathi, Milind Tambe, and Fernando Ordóñez. Software assistants for randomized patrol planning for the LAX airport police and the federal air marshal service. Interfaces, 40(4):267-29) 2010. doi:
10.1 10.1287/INEE. 100.0505. URL httts:ts:://dot org/ 10. 1287/inttttt 1100.0505
[19] Debarun Kar, Thanh H Nguyen, Fei Fang, Matthew Brown, Arunesh Sinha, Milind Tambe, and Albert Xin Jiang. Trends and applications stackelberg security games. Handboook of dynamic game theory, pages 1 1-47,201 2017.
[20] Niklas T. Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz. Savas, and Ufuk Topcu. No-regret learning in dynamic stackelberg games. IEEE Trans. Autom. Control, 6963)1418-1441, 2024. doi: 10.1 T09/TAC220 0..00227...377.... URL https::///ooo org/10. 1ww./11C9CC.... T 3330797
[21] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Marios Mavronicolas and Vicky G. Papadopoulou, editors, Algorithmic Game Theory, Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009. Proceedings, volume 5814 of Lecture Notes in Computer Science, pages 250-262. Springer, 2009. doi: 00.1009777---6600 1007/978- 3- 010e-04445--222
23. https:::::/ org/o0 10
[22] Yuqian Li, Vincent Conitzer, and Dmytro Korzhyk, Catcher-evader games. pages 329-337, 2016. http:://w/w.wttt
[23] 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-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Hon- oluiu, Hawaii, USA, January 27 February 1, 2019, pages 2149-2156 AAAI Press, 2019. doi: (0.1609/AAAALV33300...33 33012149
URL httth::///oooiiioo wrg/10. 1609/ 1609/aaai 1.aai11
[24] Alexander Rakhlin and Karthik Sridharan. BISTRO: an efficient relaxation baased method for contextual bandits. In Aaria-Florina Balcan and Kilian Q. Weinberger, editors, 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, pages 1977- 1985. JoLR.org, 2016. pol.htttp://procediimg
mlr. wal.r.rree/////rrrataee rakhlini6 html
[25] Pier Giuseppe Sessa, Ilija Bogunovic, Andreas Krause, and Maryam Kamgarpour. Contextual games: Multi-agent learning with side information. 2020. URL ctttps:/pproceedingg
12

---

wwurips.cc/paporr... http://c....po//o////////csssaa.
html
[26] Arunesh Sinha, Debarun Kar, and Milind Tambe. aaamiingaadverrarryyyyyyaavaav in security games:
A PAC model perspective. pages 214-222, 2016. ubtphtt..//...cc..oorr//aaaattat cfm?
1d=2936958
[27] Arunesh Sinha. Fei Fang, Bo An, Christopher Kickintveld, and Milind Tambe. Stackelberg security games: Looking beyond a decade of success. In Jéröme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pages 5494-5501. ijcai.org, 2018.
doi: 10.24963/CCAL221187775
https:s::///di org/ 10 2wt.3/22c9aaaa... /tt.:aaai...1117/.
[28) Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert E. Schapire. Efficient algorithms for adversarial contextual learning. Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference
Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Pro- ceedings, pages
JMLR.org. 2016. URL BeLLhtttp//proceeiinng mml mlr press/v48/
syrgkanis16. html
[29] Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, and Robert E. Schapire. Improved regret bounds for oracle-based adversarial contextual bandits. pages
3135-3143, 2016. URL www.re-ttsttttttthhh..
www..nnurrpp... httppppp.cpppppe//1///////
[30] Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 1934.
[31] Bernhard Stengel and Shmuel Zamir. Leadership games with convex strategy sets. Games Econ. Behav,, 69 2010. doi: 10.1016/).GE.3.2000. 1.008. URL https///:
org/10. 1016/j j. geb. 2009. 11.008
[32] Jin Zhang and Qian Zhang. Stackelberg game for atility-based cooperative cognitiveradio networks. In Edward W. Knightly, Carla-Fabiana Chiasserini, and Xiaojun Lin, editors, Proceed- ings of the 10th ACM Interational Symposium Mobile Ad Hoc Networking and Computing, MobiHoc 2009, New Orleans, LA, USA, May 18-21, 2009, pages 23-32, ACM, 2009. doi: 10.1145/1530748, 1530755,, URL https: //t///dooii 10. 1111/11307740 1530753
[33] Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time- varying zero-sum games. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 26772-26808. PMLR, 2022. URL https: https:///proceedingg press/v162/ press/v162/zhangg2aa zhang22an. html
13

---

A Appendix for Section 3 On the impossibility of fully adversarial no-regrel learning
Theorem 3.2. If an adversary can choose both the sequence of contexts Zi...., Zr and the sequence of followers J1,...: Jr, algorithm can achieve better than Q?(T) contextual Stackelberg regret in expectation over the internal randomness of the algorithm, even when xt" is restricted to come from the set of linear thresholding functions.
Proof. We proceed via proof by contradiction. Assume that there exists an algorithm ALG which achieves (T)) contextual Stackelberg regret against an adversarially-chosen sequence of contexts and follower types. Note that at every time-step, ALG takes as input a context 2, and produces a mixed strategy X,-
We now describe the family of contextual Stackelberg game instances we reduce to. Consider the setting in which there are two follower types (a(1) and (²2)) and two leader/follower actions (A4 = A, {{i, (2)). Suppose that the context space is of the form 2 = [0, 1], and that regardless of the realized context or leader mixed strategy. the best-response of follower type a is to play action (bac) (2. x) = Vz E 2, x X) and the best-response of follower type (2)) is to play action d2 (b (z. x) = 02, E 2, x E X). Since the follower's best-response does not depend on the leader's mixed strategy or the context, we use the shorthand b,. == by. (z,, xx). Finally, suppose that the leader's utility function is given by u(z, dz af) = {a - a.}. Note that this is special case of our general setting (described in Section 2
The reduction from online linear thresholding proceeds follows. each round E [T].
1. Given a point wi [0, 1], we give the context 2 = Wt as input to ALG.
2. In return, we receive mixed strategy x, E A(fa1, (2}) from ALG. We set 9r x,
3. Play according It, and receive label y/ and utility uoLr(Wi, from Nature. Give follower type
St = (a()) (2) if ye --1
yr =1
and utility u(z,, X4, by,) = x, [1] 1(b, = a1} + xx l(,, = a2) as input to ALG.
Observe that under this reduction.
[1 0] if >>> and [10 1] otherwise.
" (z) =
(2)
since if 8, ft = (1) and otherwise ft = (0). By playing according to x we can ensure that m(22, TT" (z)), by,)) = for all t E [7]. x² must then be optimal, because 1 is the largest possible
per-round utility that the leader can receive.
Since ALG achieves no-contextual-Strce bo--ommtctuaaSttacellllrrgggg we know by Definition 2.3 that
(Zi),bf,) by.) - u(z,, Xx, by.) = o(T). R(T) = Σ u(ze, x (Z:),
(3)
To conclude, suffices to show that ROLT(T) = o(T) using Equation 2 and Equation 3). Apply-
ing Equation ( we see that
R(T) =T
Σ [x[1] 1lb, =1 x, 1(b,, = =2))).
(4)
By construction, 1(b, } (v 1}.1 1(b, a2) 1(3. -1}, xx[1]
Sr. and
x = 1 - 9t- Substituting this into Equation 4 we see that
R(T) = Σ(e
(a: 1 1m 1) + (1 (1)))) 1 1 - 1}) =: Ro)T(T).
(5)
1m1l
O'serve that xx|2] 1 gt.
14

---

By Equation (3) and Equation 5), we can conclude that (OLT(T) o(T). However, this is contradiction since no no-regret learning algorithm exists for the online linear thresholding problem by Lemma 3.1, Therefore it must not be possible to achieve whenever sequence of contexts and follower types chosen by an adversary.
Stacckelher--regree
B Appendix for Section 4 Limiting the power of the adversary
Lemma 4.4. For any sequence followers fI....fT fr and any leader policy n, there exists a policy π (E) : Z + Usez&z that, when given context z, plays mixed strategy in &g and guarantees that Et= u(ze: u(ze: b,, (Zi, m(z))) u(z,, ( (Zz). by, (Z,, x(E((z))) S 1. Moreover, the same result holds expectation over any distribution over follower types F.
Proof. Observe that for any
T
π (z) = arg max
Σ
1lze =2}
Σ x(ai] ulz, by,
xEA(AA)
t=1
agEAi
K
T
arg max (EI(A
x(ai| u(z, at aoco (z, x))
Σ
1(z Ze a00}
a,EAi
The solution the above optimization may be obtained by first solving
Xu..K (z) arg max
Σ
Σ 1=1 a.A.i.
x(ai] ulz, a1,))
E1(z =2, (0)
XEA(AA)
s.t. (z,) = a0) E [K]
(6)
for every possible setting of (".))...,aa" and then taking the maximum of all feasible solutions.
Since Equation (6) is an optimization over contextual best-response region X (a)),, kkk)) and all contextual best-response regions are convex polytopes, x x²(z) will be an extreme point of some contextual best-response region, although it may not be attained. Overloading notation, let (xT denote the contextual best-response region corresponding to (z), i.e., x (z) E (=(x"(z)) Since for a fixed context E Z the leader's utility is linear function of over the convex polytope X₂ (T (z)). there exists a point x(z) E cl(X2 (z))) such that
T Σ (z)
1lz: z
u(z, nt (z). (z, (z))) 1fz = z}.
Let x'zz) denote the corresponding point in Eg such that [|x x(z)il1 < 8. (Such point will always exist by Definition 4.3) Since u E [o, 1] and is linear in x for fixed context and follower best-response.
Σ u(z, (z 1fz, z} =
Σ u(z,xx(22 (2,, 1lz = z}
Σ (u(2, x(z). by (2, - 8) 1(z, 2)
2 Σ (u(a, (()) by (2, x (z))) 6) 1 = 2)
Summing over all unique z encountered by the algorithm over T time-steps, we obtain the desired
result for the policy (()) which plays mixed strategy r(f)(z) = x'(z) when given context z. Finally,
observe that the same line of reasoning holds whenever are interested in the optimal policy in
expectation with respect to some distribution F over followers, as is the case in, e.g. Section 4.1 (with
Ex 1l ft (0)) replaced with If a ()))
15

---

B.1 Section 4.1 Stochastic follower types and adversarial contexts
Theorem 4.6. Lerp(z, x) := [p(b,, (z, x) = ay)lafEA, and P. x)
p g. (z. a as)latEAr
The expected contextual Stackelberg regret (Definition 4.5) of Algorithm 7 satisfies
B[R(T)) & 142
B 1-1 (TV(p(2,
TVV)) (r,,
t (2))))
Proof of Theorem 4.6 For any z E 2 and / [7].
E,[u(z, (8) (z). by(2, (8) (2))) ) E,/u(z, n. (z) by T. (2))))
E. (u, me (z), by(2, n. (z)))) - E, (u(z, me(2), (2 ग. (z)))
Since utilities are bounded in [0, 1] and the expectations E, and E. are taken with respect to p and P. respectively, we can upper-boune bound E, [u(2, Te (2), by n. (z)))) - E. [u(z, Th (2), (y Te (z))) by
/ (2pule, nH (z))
me _
Putting everything together, we get that
Ee[u(z, - (0 (2, ( (z))) I E,[u(z, ni (z),, (y =()))))+2IV(((xxxxx)) (()
We now use this fact to bound the expected regret. By Lemma
B[R(T) +++1
(z:), Σ f S. [u(ze, x (Z)), by, (Ze. x (2:))) v uzz,, To(2)) (z. Te(Z))))
Σ B, B (E (Z))) (ze, x (z:)))
S--
E, [z( n (0) (z), bj. (z, π (z) (p( n. (z)), Pr n. (z))).
By repeating the same steps as above, we can upper-bound
Ey [u[u(ze; n (E) (z)) by (Ze, (8) (z,))) Be[u(2, x (E) (2, n (E) (x)))
by 2pV(p(Z, n (e)), Po (2,, n ())) This gets the desired result.
Corollary 4.7. If p: = (pe(fi = a (EEKy Pr41 = ( = Σe 1 = (0) and
(f ()) for E [K], then the regret of Algorithm satisfies B[R(TT] OK ((K
Proof. For 1 2 2,
V(p(z.x),P.(1z. = Σ
pilft = (0)) -e(fe = (3))
2 i=1
Σ
1l = - - a()))
r=
for any z E Z and x E X. By Hoeffding's inequality, we know that
1
Σ
-f - E, 2 log (T))
t
simultaneously for all t [T] and i E [K], with probability at least of p. P. on z and x, we can conclude that
+ Dropping the dependence
log(2T) 1
Ey... -- ST P.)l < K
2T
16

---

T and the sequence of utilities for each arm chosen by (since K T), and so
E|R(T)) $ Σ K
(og((2))
+
1
0 (KVT (KVTlog(T))
t-1
2T
Corollary 4.8. If (z(
(a Deti (L(texi))))
E 1(by, (z, x) = a). and Pi (11 (olootaa))))) = Iy for as E As, then the regret of Al- gorithm satisfies [[((T)) O
Proof. For t 2 2,
1 Σ
TV(p(z, x), xx(zxxx) =
pe ( (1(00)))))))) Pe (((t0)))))
aeAd
Σ
pp (
1b, (2, -a]
2
aEdy
Σ Σ
a} E, [1, ttf
2
acdy
for any z E x, x E X. By Hoeffding's inequality,
log(2T)) (T))
Σ
(2, = a} 1b,, - -of] s 2
simultaneously for all t [T] and E [K], with probability at least conclude that
Using this fact,
72
log(2T)
1
E E ft (V P. & Ar
+
2T
(since K < T) and
log(2T)) A
E[R(T)) < 1+44
t-
2T
1
<3 + 4A, Saarvologi (2T))
log(2T)
dt
Vt"
1=
= =0 (A Tlg((T)
B.2 Section 4.2 Stochastic contexts and adversarial follower types
The following regret guarantee for Hedge is well-known result. (See, e.g. Gupta 11
Lemma B.1. Hedge enjoys expected regret rate TT when there are actions, the learning rate is chosen to be n V log adversary.
Lemma 4.10. When the sequence of contexts is determined stochastically, the expected utility of any fixed policy π may be written as
Exp....
Σ u(ze, T (2x), by (Ze, ((x)))
(llu(z,(22)) boc0 (2, ((2)))
Σ Ex
[1( = =a(1))
17

---

Proof. For any fixed policy n
K u(ze, (ate) (T (1) (1)
Exx,..... Σ 1 (a
Σ
En
Exi
T
Ex, [u(ze, x (2:), bato (Ze, (Z)))) [1 ac
where the second line uses the fact that fi cannot depend on 24, and the result follows from the fact that ,1,..., ZT are i.idd.
Theorem 4.11. If = {w : E w|1 E N, E [K] and rj = V
log TI then Algorithm
obtains expected contextual Stackelberg regret (Definition 4.9 E[R(T)) KT log + K).
Proof. By Lemma 4.4
[T)) E. Ex....... Be
u(ze, xt (ze), (2e; "T" (2+))) u(z,, (.))) (Zt, m(
E Exz.....x
Σ u(ze, (E) (z+), (z,, (2) (2x)))
u(z) ne by me +
Let n (w") denote the optimal-in-hindsight policy in TT.
B[R(T)] S E EZE
u(ze, n (w ((''((z)) (z:), by. (Ze, क (w-) (2x))) u(ze, Te by (Zr, Te n((2))))
T
+ Eg Ezi....rr Br
u(z,, π (8) (z.), (E))),
(Z,, π (8) (z:))) u(z,, uZz,, (1=))()))))) (2)) by, (Ze, ग. (w (((")((z)) (zi)))
+1
To conclude, it suffices to bound the discretization error, as
Ex Ber...... Zr
Σ u(ze, n (w") (ww) (2x), by. (Ze, n (w0) (z:))) u(Zz, mi (T() by (2e, Te Te(2)))) < 0 (VTTlog
which follows from applying the standard regret guarantee of Hedge (Lemma B.I in the Appendix). Applying Lemma 4.10
Eg,
Σ ulze, (()) (z)), by, (Ze, n (E) (2)()) - ulzi, π (w (()))(()))) (Zz) by. (Ze, n ?!w0 (zx)))
K
EE/lu(z (2)) baro (2, n (E)(2) u(z, :(w (2), bacol (z, (n( (2x))()))
E
1....,,,1111 [1 = 11ff a!!1)
K
Ey [u(2,, n (1) (2) 1,00 (z, (E) (2)))]
R
= (a())) T w(]l -w
1=1
K
T
+
Σ
Ex [u(z, (w)) b (1 (z, n. (w (z))))
T w
...... [1ffe = a1))
1=1
where the inequality follows from adding and subtracting ΣK E2 [u(z, t (E) (z). b,.0) (2, (z)))] T. [i and Σ Ez [u(z, n (((")()), the discretization error by
(z)))
(z), bato (z, < (w") (z)))] T [i]. Finally,
upper-bound
K
Σ
T
w [1]
Σ
F
[1/ a (1)) <
by using the fact that the sender's utility is bounded in [0, 1]. Piecing everything together and observing that [II| < K gives the desired regret guarantec.
D
18

---

C Appendix for Section 5 Extension to bandit feedback
C.1 Stochastic follower types and adversarial contexts
Recall from Section 4.1 that =ay) E {0, 1) K is the indicator vector whose i-th component is (a a i.. the indicator that follower of type (*) best-responds to mixed strategy by playing action ay. For any fixed policy x. we can write the sender's 's expected utility in round as
y, [u(2,, n (2x). bn (T(22)))
Σ ayEA,
ulze क (2)))aa)) plby (T()) = =a))
Σ
ulze, (Z)), ( (((oo))))))
ayEA,
where (T))(T(2)) = ==):= (2) non-adaptive adversary, the second line follows from the fact that fa,..., are drawn i.i.d., and
a H. the first line follows from the assumption of a
(Tb)(T(2)) a,) p(((orm()=za))
Σ
1lb2r (T(Z)) a,} Pff (
where P(f ()) the probability that follower f is of type (t) Note that p( (o(-(er)) (and therefore [,[[u(z π (2z), by. (T(2)))) is linear in (((x))))==)))
Given this reformulation, a natural approach to estimate p( (ot(r)))))))) as (0 (a(rtx))))))) and act greedily with respect to our estimate, like we did in Section 4.1 To so, we define the set W = (1 (o=ay) Vuy As, E Σ} and estimate p(b) for every element b in the barycentric spanner = (b(),... ,..., b(k) of !
We estimate p(b) as follows: For every b B. there must be mixed strategy (bb) and follower action (b) such that b 1 -0000) Therefore, if the leader plays mixed strategy x()) N times, set p(b) N ELEIN] (b,, (x(b)) abl).. Given estimates (b(b)) can estimate p(1 (o()==a)) for any x E and as E As
=nbby--
K
((((o()=a)))
Σ X1 (1 ((b()),
where >4 (o(0))) E [[1, for i [K] are the coefficients from the barycentric spanner Note that this an unbiased estimator, due to the fact that ((1(()00==))) a linear function.
13
Algorithm plays each mixed strategy x (b)) for b E B N > O times in order to obtain an estimate
of each p It then uses these estimates to construct estimates for all 1 [ (and therefore
also E, [u(z, x. (x))] for all x E & and z E Z). Finally, in the remaining rounds Algorithm acts greedily with respect to its estimate, much like in Algorithm T
Theorem C.1. 1N = o
A 22/372/3 log. (T)
then the expected contextual Stackelberg regret
K173
of Algorithm Definition
4.5)
satisfies
E E[R(T)) =0
0Kx2K 2/3 (2/11A///T70 2/3
log log2/ 1/)((T)
Proof Sketch. The key step in our analysis is to show that for any best-response function a E Σ and follower action a Ay, Var(p(1l (==0))) < (Lemma C.3 Using this fact, can bound the cumulative total variation distance between p1 (o()))=a)) and p(1 (a(t))))))= )) for any sequence of
mixed strategies and follower actions in the "exploit" phase (Lemma C.5 The rest of the analysis follows similarly to the proof of Corollary 4.7
12See Section 6.3 of Balcan al. 55] for details how compute this barycentric spanner.
For more details, see Proposition 2.2 in Awerbuch Kleinberg 4 In other words, ignore the context in the "explore" rounds.
19

---

C.2 Stochastic contexts and adversarial follower types
We now turn our attention to learning under bandit feedback when the sequence contexts is chosen stochastically and the choice of follower type is adversarial. While still use barycentric spanners Jiee, we can no longer do all of our exploration "up front" like in Appendix C.T because the follower types are now adversarially chosen. Instead, we follow the technique of Balcan et al. [5] and split the time horizon into Z consecutive, evenly-sized blocks. In block B,, we pick a random time-step to estimate p~ (a(x)))))(()))>>> i.e. the probability that a
to estimate { (a
follower in block B, best-responds to mixed strategy xbb) by playing action a!b), for every element in our barycentric spanner B. If whenever the leader plays x(b) the follower best-responds with action (b),, we set P+ (a(x()))=a(ti)) = Otherwise we set pr (a(x(())=((b)) = Since the time which we play x(b) is chosen uniformly from all time-steps B,, P, (a( is an unbiased estimate of p- (1 (o)))) While P- (a(x("))) no longer has low variance since it must be recomputed separately for every block Br, is still bounded. Therefore, we can use our estimates {p- (I (o<a(t) J beB, along with the corresponding linear coefficients from the barycentric spanner, to get a bounded (and unbiased) estimate for every p(1 (oW)=a))
Once we have estimates for { {pr (L( In particular, in every block B, we use our estimates {(p, (1 (a(w=a))) (oy EA, Ixes to construct an (unbiased and bounded) estimate of the average utility for all policies in our finite policy class II during block By. At the end of each block, we feed this estimate into the Hedge update step, which updates the weights of all policies for the next block. Finally, when we are not exploring (i.e. estimating P+(1 (o()())))a())) for some b E B), sample the leader's policy according to the distribution over policies given by Hedge from the previous block. This process summarized in Algorithm
IxEE, we proceed via a reduction to Algorithm
Theorem C.2. IfN O(T2/3A) log 1/3 T), then Algorithm 4 obtains expected contextual Stack-
elberg regret (Definition 4.9
E E[R(T)) S 5 (KA/3T2/ log (3(())))))
Proof Sketch. The analysis proceeds similarly to the analysis of Theorem 6.1 in Balcan et al. [ We highlight the key differences here. The first key difference is that while Balcan et al. [5] play Hedge over finite set of leader strategies, play Hedge over finite set of leader policies, each of which map to one of finitely-mant not sufficient to only estimate {(p-(1 (a())= EaA,, Ixes to obtain unbiased estimate of the utility of each policy in 1l in each time block we must also specify context (or set of contexts) to use our estimator. We show that it suffices to select a context uniformly at random from the contexts (z, heB, encountered in the block.
leader strategies for a given context. Second, unlike in Balcan et al. [5]
C.3 Proofs for Appendix C.I: Stochastic follower types and adversarial contexts
Lemma C.3. For any of E End as E Ay. Var(5(4((==a))) K.
20

---

Algorithm 3: Learning with stochastic follower types: bandit feedback
Let B = (b()) ((k) be the Barycentric spanner of W for 1,..., do
for r = ......,N
.N do
Play mixed strategy x(b (1), observe best-response ((s-
end
Compute ((b()) N ET= 1lb,, 11b,, (x((())) =a(()))
end
Compute ((((0=)))) = K \ı(1((=a))) ((b(0) for all o E E. E E,
for t 1-=KK1. N + ,,...,, do
Observe context Z₁, commit to mixed strategy
X, = (zz) arg maxxes EayEA, (((()))))))) ulz,, x, aq).
end
Proof.
Var(F(1(azaa)) = E[(p(L E[(((L(0=))) (
= -E[ 1 ( })9] - p² (²((0==)))
K
X₂ ((l0=a)))0b000
E
p² (1 (o=ar)
K
X3 ()
E
K
K
Σ /=1
>:(1
(P - -22 (1(=a)))
1=1
K
j=
K
K
Σ
Σ
(o (bb()) - ()((o)=)))
i= j=ljji
Observe that since (1) the follower in each round is drawn independently from F and (2) the rounds used compute (()()) do not overlap with the rounds used to compute p(b(3) for j * i, ((b()) and (((()) are independent random variables for j A Therefore
Var(6(1
Σ (16
K X ( - x²2 (((oz)))))
#=1 j=
21

---

We now turn our focus to Elp² (b())). Observe that
27
(b = E
16,, (x(66)) = =a
=afb00)) 1111
N
1
1[by, (x((6))) = aa ) 11b,, (x(1b))
=af a220011))
E
N2
(N p(b(()) + N(N - 1)p?(b(1))
N2
Plugging this into our expression for (ar(p(1 (o=aa))) we see that
Var(p(1 (o=az)))
(1
(0=a)))(((b(1)))))) + (N -N 11)p((b0))
N
j=1
K
K
Σ
X1(1((=a))) (1=0))) (o
- p²(
(0==))))
2 [((0))))00(())))p)0
K
X (1 p² (1==a)))
Xj ((((()))))((()) 23 (1 (1= p(b()))
N
K
p² (L(oza)))
1
Xy ((((())))))(())
(100))())))))))((000)))))))))))) (11((=)))( p(bbb)) + p1((1 - p² (1=aa))
N
K
N
where the last line follows from the fact that (y (o=za)) [-1, 1] and p(b()) E [0, 1].
Lemma C.4. For any z E Z,
Σ p(((o(tte)zap)) (() ayEd,
Σ pl (())))) u(z, (2),
ayEd,
Σ
pi (((((())))=a1)) - pl ((010(000==))))1
ayEA,
22

---

Proof. By the definition of म.
Σ agEAs
p(1 (a
(0)
(2).
Σ
M1 (((0))))))))) u(z, ((2),
asEA,
Σ p(((o(RM)=)))) u(z, (2))
eyEA,
Σ
(p
(p(1(c (2(1))())))=)) - -((((rro)))))) u(z, (1)
ayEd,
Σ p(((o((())=a)) u(z, 17 (2),
ayEAs
Σ ayEd,
p0 ((((o(())=)))) - - (((()())))=))))
the desired result may be obtained by rearranging terms.
Lemma C.5. For any sequence of mixed strategies XNK+1;..., XT,
K log(T))
Σ Σ
|0 ((((ooo)zaj) - p(l (o(0)))))))))) = 2A
N
with probability at least T
Proof. By Lemma C.3 and Hoeffding bound, we have that
2K log(1/8)
p ((L(o=a))) - p( p(((o=aa))) s
N
with probability at least - 8, for any particular (a,ay) pair. Taking union bound the randomness in estimating p(b("),. ((b())....,p(bbb we see that
2K (K/)
(o=a)) p( (o=ay))] S
N
with probability at least 1 8, simultaneously for all (a, ay). The desired result follows by summing over T and Ay, and setting 5 7
Theorem C.1. IfN = N ( 12/3 log (3()) of Algorithm 3 (Definition
then the expected contextual Stackelberg regret
R179
satisfies
E [(((T)) = 0 (K2/3 22/3T/2/ (K313A2/$T2111 log (T))
23

---

Proof.
E[R(T)] = E FooF
uiz xt (zi). (x²( a(zi, (e(z)))) (x
T
Σ 1 + Front
u(z π (E) (zt), by, (8) (2)()) m( (Te
1 + KN + EE E
u(z,, n (2) ( (z)))) m(z,, #(ze), by (T(2))))
L(=KN+1
T
1 + KN + Ez~F
Σ
Zt x (E) (z)), ( by
-KN++
T
= 11 KN + EYnF
Σ
Σ
u(Z,, x
(0)). (0)
(T - =a
u(z,, A(z1), ap)
((b)(((2)) =
T
=1 Σ
Σ
u(zz, (() (2i), aq) p(1 (a)()))))))))))) - u(z, a(z)), pl p(((otto)))))))
NK
By Lemma C.4
E[R(T)) $1+ 51+ KN
Σ
Σ
ulze, (2)) - P(1 (001))))))))))
T
Σ
Σ
((((otta)))))) p(
NK+
<1+KN+
Σ
p (ota()))a))))))) p(( (oiht))))
NK+aayddd
T
Σ Σ ((((o(te)))))) - )(
K Klog(T)
< K3 MKN++AATT
N
where the last line follows from Lemma
C.5
The desired result follows by the setting of N.
C.4 Proofs for Appendix C.2: Stochastic contexts and adversarial follower types
Definition C.6. Let ur (T) = Eayes u(z,, (Zz),, - Pr (1((tteee)))))))) and Ū (T) = Enre,, u(2r, ((T), ΣØ 20(((ot(aa))aa)) Pr (b((), where 2, ~ Uniffz: 1 E Br}. (b)
((1),..,b(()) B = (b()), ...., b(ki) is the Barycentric spanner for W, and p(b) = -1 if (x(b)) a and
p(b) 0 otherwise.
Lemma C.7. For any fixed policy n, JEB (T) En,~p EafEA, ulz,, a((z),aa)) (1 where the second expectation is taken over the randomness in selecting the explore time-steps and drawing 2, Unif : E Bz). Moreover, (T) E K-KA,
By (x((r((((T)))
24

---

Algorithm 4: Learning with stochastic contexts: bandit feedback
Consider 1I = { SWEf
Let qı [ [w) : 1, P1 1r [ := [i] for all ((m) E II
Let = [b (1) ..................... b(*)))))))))) {k)} be the Barycentric spanner of W
for 7 1, ... Z do
Choose random perturbation over and explore time-steps B, uniformly at random Choose time-step in B, uniformly at random whose context will be used as 2, for B, do
If is an explore time-step. play the corresponding mixed strategy x(b:) in B. If a (bb),, set pr (b,b) 1. Otherwise, set f. (b,) O. Otherwise (t is an exploit round), sample Ne ~ Pt. di, (z.).
end
For each policy ((w) E 11, compute
[x( = Eayed, E ): (a(x()))==aa) ((b(t)) u(t,, (lw) (2r),
Set [x]]][[(w]]] = exp
-17 Ex= Le (1(T(1))) and
[+41|((W)] (1t2(T/w)1// Enwhen 94+1 (T+l)
end
Proof.
K 21((( Pr (b()))
E(:))en, [T]]
E [x.)enn
Σ
u(zr, (2+),
OgEAt
K
Elzhee Unil
u(z,, T(z),,
Xy(1 (olota))i=a)) (B
ayEA,
#=1
K
EE (tiifaat
Σ ayEA,
u(z,, 1 (Z+),
Σ ( (((((orte)))aa)) .pp.))pp(00 (b(1))
= =Ejahee Unf
Σ ayEd,
u(zr, T(Zr), pr (1rri)ee)))a)))
E ayEAs
((1r,, pr ((g) (uy
The following lemma is analogous to Equation (1) in Balcan et al. [
Lemma C.8.
N Σ
E
ur (z)) - Eur (TTT)
S / No [T]]
x
where RN, an upper-bound on the regret of (full-information) Hedge which takes as input sequence of N losses/utilities which are bounded in [-R, x) and are parameterized by Zi.... ZN.
25

---

Proof.
N Σ
N
Ey P
Σ
|r ur (T)
En Ey
Pr (((r((T)
L= xEll
mell
By
Pr(m] (T(
N
Ey
max mEll
úr (TT -NNN
T=1
E
BN
max well
ūr (TT)
RNN
L==1
E
max Tell
Σ ur (r(x)) RNN..
where the first line uses Lemma C.7 and the fact that Zi...., Zr P are i.i.d., and RN is the regret of Hedge after N time-steps when losses are bounded in [-x, xl. Rearranging terms and using the fact that the expected regret of Hedge after N time-steps is most / NN: log TI] gets us the desired result.
A/1////////oo/"""/ 'log 1/3 13),, then Algorithm 4 obtains expected contextual Stack- Theorem C.2. IfN O A/2 elberg regret (Definition 4.9
E(R(T)) 5o OKKA//3/22 log" (3())
Proof.
B[R(T)) = EE p
(2t, TT (2t). by (mx()))) - u(2,, my))
< EE
u(zi, (6) (zz), (m (E u(zi, (n
EE
(Z,, n (8) (E) by. (2
(
r=tteB
< KN EE
u(zt, (() u(ze, oH (ze), by
11
26

---

N
=1+ + KN + EE
ΣΣ Σ
u(ze, (8) (z)), 1[b (1 (T =a,
p
B EyEd
- u(z, To (2:), as)-
11b = aayl
N
ΣΣ LEB, agEds
=1 KN + E
E2
11-1))187-11 Be. 26 1118-11
u(Zt, π (E) (ze),ar af) 1(bs (z)) = =as} - u(2t, Tr (ze),
( (T+((E))
N
= =1 KN + E
Σ
E
tir 13 1) 11 B2, ~ M/la.. 11-1)))
Σ Σ LEB, ayEd,
u(Zr, π (E) aay) 1lbr, (1(0)())))))) = a,} u(zr n (g)) 1lby, (z,)) = =aa
N
=1+ KN + E
E2
ber 1) 11 ~ -
Σ arEAs
u(z x18) (2+)
(Tb = orl)
Σ (1b = =a,) u(z,, T7 (2.)) MEB,
Σ MEB.
where the second line follows from Lemma 4.4 the third from splitting the time horizon into blocks, the fourth from loss due exploration, the fifth due reformulating the reward as a function of different follower actions, the sixth due to linearity of expectation, and the seventh line follows from the fact that (1) ,. is independent of z for all t B, and (2) Z1...... Zr are independent.
[() $ 14 KN BE
E
( 1) ppEE Pla
Σ ayyEd
ulz,, ((() (2,))),))
1 Σ
1(by (z)))))))) =0/1)
u(Z,, (TTr),
1
Σ
(T,,( ]
B, IE
[Br
+ KN
BE
Ez (r-1)) IN
Σ
u(z,, T( (8) (2r), - Pr (1 (o)(t))))))))
1111 11-11,
ayEA,
u(2,, T. (2+), pr (1 ((())(er))=a)))
N
31+ KN + BE
m Pl Pla ir D11 [ur (T(()) - ur (T+))
N
=1+ KN + B. Ex PNOP
Σ (T) - Eer (TTT)
<1+KN+B V /NKA, log [IT]
/ Ay (Tg
<1+KN + TK
N
where the first line comes from multiplying and dividing by [By] the second line comes from the definition of pr, the third from the definition of u,, the fourth follows from linearity of expectation and the fact that .i,... ZT are i.i.d., the fifth follows from applying Lemma and the sixth line
follows from the definition of B and the fact that |I| < N Setting N gets us the final result. O
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.ccppullc//uuuii wwwiicccguie//eeeeeeeeeii CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
30

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://rripscccpullll/////e/eeee scc/public/Bthiiccccdeeeel.
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As our work is theoretical, there are no positive or negative societal impacts. However, hope that our work will one day lead the design and implementation of better algorithms for solving Stackelberg security games in practice, which would have positive societal impact in domains such airport security and the protection of wildlife against poaching.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "0yAXpzxfeC", "reviewer": "Reviewer_C9HM", "summary": "This paper studied the regret minimization in Stackelberg games with side information which consider the additional information available to each player. The paper found that achieving no-regret learning is impossible in fully adversarial settings. However, it demonstrated that no-regret learning is achievable in scenarios where either the sequence of contexts or followers is chosen stochastically.", "questions": "I do not have any questions for the authors.", "limitations": "The limitations have been addressed properly.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The idea of using side-information to learn to play Stackelberg games is interesting.\nCompared to previous work on learning in Stackelberg games, this paper takes into consideration the additional information available to both the leader and followers at each round, which is more complicated and realistic.\nThe paper provide an impossibility result and also identifies a setting where no-regret learning is possible. An algorithm is also provided to achieve no-regret.", "weaknesses": "This paper lacks experimental results to verify the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*”This paper lacks experimental results to verify the theoretical analysis.”*]\n\nWe hope our numerical simulations address your concerns regarding the lack of experimental results.", "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": "jGaLjvYQCH", "reviewer": "Reviewer_YfNJ", "summary": "The paper presents a study of Stackelberg games with contextual side information, impacting their strategies in a game theoretic setting. The authors introduce a framework for analyzing online Stackelberg games, where a leader faces a sequence of followers, and both or either sequences—contexts and follower types—can be adversarially chosen. The paper contributes by showing the limitations of traditional non-contextual strategies and offering new algorithms that can handle stochastic elements in either the context or the follower sequences.", "questions": "- The paper would definitely benefit from the addition of numerical experiments or case studies.\n- Could the authors provide more clarity on how the adversarial model for context selection was validated? Are there empirical data or specific scenarios where this model reflects real-world conditions?\n- How would the author compare the results with existing methods for handling contextual information in game theory, such as contextual bandits or online learning with expert advice? Can the authors comment on how their approach compares to existing methods in terms of computational efficiency and practical deployability in real systems?\n- How does the proposed algorithm perform if the model of side information is mis-specified? For instance, if the actual distribution of contexts or follower types deviates significantly from the stochastic model assumed, what is the impact on the regret bounds?\n- Several theoretical assumptions are crucial and well presented in the paper. How sensitive are the main results to these assumptions? If some of these assumptions might not hold, how would this affect the applicability of the results?\n- The paper could benefit from a deeper discussion on the limitations regarding the scalability of the algorithms when the number of contexts or follower types is large. What are the computational implications?", "limitations": "The authors have not explicitly addressed limitations or potential negative societal impacts of their work. A clearer identification of potential limitations, such as dependency on the accurate modeling of side information and follower behavior, would strengthen the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses a novel aspect of Stackelberg games by incorporating side information, which is realistically present in many practical applications but often ignored in theoretical models.\n- The paper is technically sound with rigorous proofs and a clear exposition of both theoretical and practical implications of the findings.\n- The paper is well-written and organized. Concepts are introduced systematically, and the flow from problem statement to results is logical and easy to follow.", "weaknesses": "- The paper could improve by providing numerical experiments or case studies that demonstrate the efficacy of the proposed algorithms.\n- The practical implications are clear for certain fields, but the paper could further elaborate on how these findings might influence other areas of research or industry applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*“The paper would definitely benefit from the addition of numerical experiments or case studies.”*]\n\nWe hope our numerical simulations address your concerns regarding the lack of experimental results.\n\n[*“Could the authors provide more clarity on how the adversarial model for context selection was validated? Are there empirical data or specific scenarios where this model reflects real-world conditions?”*]\n\nThe common motivation for studying adversarial models in online learning is not that we believe that the data-generating process is adversarial, but that we believe it is not i.i.d. If an algorithm can handle adversarially-generated data, then it can also handle data which is not i.i.d. in some way, while being agnostic as to how the data is generated. In Stackelberg games with side information, there are many examples of settings in which the contexts would not be i.i.d. In the wildlife protection and patrol boat examples, weather conditions for each day are not sampled i.i.d. from some distribution; instead, there is some dependence from day-to-day. \n\n[*“How would the author compare the results with existing methods for handling contextual information in game theory, such as...”*]\n\nWe would like to emphasize that existing methods for handling contextual information (e.g. contextual bandit algorithms, online learning with expert advice) are usually not studied in strategic settings where there is more than a single agent. In general, such single-agent methods would perform poorly in game-theoretic settings, since they do not take the other strategic agents into consideration when making decisions. While our problem may be viewed as a special case of online contextual adversarial learning, applying algorithms for this problem out-of-the-box to our setting generally results in worse regret rates and would require more stringent assumptions on the data-generating process than what we require. (See line 485 for more details.)\n\nOthers have also studied various forms of side information in different game settings. We include a discussion on these works in Appendix A.\n\n[*“Can the authors comment on how their approach compares to existing methods in terms of computational efficiency...”*]\n\nThe computational complexity of our algorithms essentially match those for no-regret learning in Stackelberg game settings without contexts (up to small differences in polynomial factors). While both contextual and non-contextual algorithms for no-regret learning in Stackelberg games have exponential per-round complexity, this is unavoidable due to an existing hardness result for the non-contextual setting (see Li et al. [23]). With that being said, we believe that studying special cases of both the contextual and non-contextual settings where efficient learning is possible is an interesting and important direction for future research. \n\n[*“How does the proposed algorithm perform if the model of side information is mis-specified? For instance...”*]\n\nThanks for the interesting question. While our impossibility result of Section 3 rules out the ability to learn when the distributions are arbitrarily misspecified, no-regret learning may still be possible under other, intermediary, forms of adversary (such as the one you propose). We highlight this as an interesting direction for future work in Section 6 (Conclusion).  \n\n[*“Several theoretical assumptions are crucial and well presented in the paper. How sensitive are the main results to these assumptions?”*]\n\nThe assumptions made through Section 4 (e.g. known utility functions, follower being one of K types, finite leader/follower actions, full feedback) are standard in the literature on no-regret learning in (Stackelberg) games and are reasonable under many settings. \n\nIf you are referring to the assumptions which are unique to Section 5, the results are mixed. We believe that our results in Section 5 could be extended to handle adaptive adversaries by using a more clever exploration strategy. However, our algorithmic ideas in Section 5 do not readily extend to the setting in which the follower’s utility also depends on the context. We view relaxing this assumption as an interesting direction for future research. \n\n[*“The paper could benefit from a deeper discussion on the limitations regarding the scalability of the algorithms when the number of contexts or follower types is large. What are the computational implications?”*]\n\nWe are happy to add a deeper discussion on computational runtime in our next revision. In short, our runtimes have no dependence on the number of contexts, and we inherit the exponential-in-K runtime from the non-contextual Stackelberg game setting (where K is the number of follower types). The implication of this is that while our results scale well to settings with a large (or infinitely-many) number of contexts, the number of different follower types should be small/constant. \n\n[*“The authors have not explicitly addressed limitations or potential negative societal impacts of their work. A clearer identification of..”*]\n\nWe discuss (what we view as) the most important limitations of our work (allowing intermediate forms of adversary, better regret rates in the bandit setting) in the Conclusion as directions for future work. However, we would be happy to add additional discussions on the topics you propose. \n\nWe chose not to discuss the societal implications of our work because our results are largely theoretical. With that being said, we anticipate that any societal implications of our work will be positive, since algorithms for learning in Stackelberg games are usually deployed in socially-beneficial domains. For example, in airport security, patrol strategies for drug-sniffing dogs could be modified to take factors such as the time of year, airport congestion, etc. into consideration. In wildlife protection domains, park rangers’ patrol schedules can be informed by things like observed tire tracks, or the current weather conditions.", "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": "cA3Q0uskmD", "reviewer": "Reviewer_8oy3", "summary": "The paper studies an online Stackelberg game, where the leader plays with a different follower type in a different context in each time step. The paper takes an online learning approach to solving this problem. It first that given that the context space is infinite, it is not possible to achieve sublinear regret via a reduction to an online linear threasholding problem. Therefore, the authors consider relaxed cases, where either the context or the follower type is chosen stochastically in each round. In both cases, the authors present algorithms that guanrantee sublinear regret, both for the full feedback and bandit feedback settings.", "questions": "Would the impossiblity result change if the context space is finite, or if the players' utility functions are linear w.r.t. the context.", "limitations": "The authors didn't seem to have addressed this explicitly, but the work is theoretical anyway, so this is minor.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(+) The model is well motivated.\n\n(+) The paper is clear and well presented. All analyses look sound and rigorous.\n\n(+) The results presented are very complete, covering all cases of the model and both positive and corresponding negative results.", "weaknesses": "(-) The main impossibility result appears to reply on the fact that the context space is infinite and the model is non-linear w.r.t. the context. \n\n(-) The analysis of the relaxed cases (stochastic follower type, or stochastic context) looks fairly standard and the results are expected. So overall the paper is more like an application of existing techniques to a problem motivated by a new context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*“The main impossibility result appears to reply on the fact that the context space is infinite and the model is non-linear w.r.t. the context.” and “Would the impossiblity result change if the context space is finite, or if the players' utility functions are linear w.r.t. the context.”*]\n\nWe would like to emphasize that most work on learning in contextual settings focuses on the setting where the context space is infinite or large. With that being said, our impossibility result should carry over to the setting where the number of contexts is finite, but exponential-in-T. (This is because the impossibility result for no-regret learning in online linear thresholding carries over to the setting where the adversary can only select from an exponentially-large grid of uniformly-spaced points in [0, 1].)\n\nWe would like to clarify that the leader’s utility function is not non-linear with respect to the context in our impossibility result. While we allow non-linear relationships in all of our positive results, the leader and follower utility functions actually have no explicit dependence on the context in our lower bound (see line 518). The intuition for the lower bound is that while the leader’s utility may not explicitly depend on the context, the adversary can “hide” information in the context about the receiver’s type. This ability to “hide” information makes it hard for the leader to compete with the best-in-hindsight policy. \n\n[*“The analysis of the relaxed cases (stochastic follower type, or stochastic context) looks fairly standard and the results are expected. So overall the paper is more like an application of existing techniques to a problem motivated by a new context.”*]\n\nWe would like to clarify that our positive results do not follow from existing techniques. We will update the paper to better explain the technical innovation based on the reviewer’s feedback. There are several reasons why this is not the case. The setting of Section 4.1 (and its bandit analogue) have not been studied in the literature on non-contextual Stackelberg games. As such, there is no existing technique to apply in this setting. Our algorithm in Section 4.2 plays Hedge over a finite set of policies, while previous work on non-contextual Stackelberg games plays Hedge over a finite set of mixed strategies. While the two ideas may seem similar at this level of abstraction, showing that it suffices to consider a finite set of policies (each of which map to a finite set of context-dependent actions) is non-trivial and requires bounding a discretization error which does not appear in the setting without side information. We will update the final version to better explain the technical innovation.\n\n[*[On limitations]: “The authors didn't seem to have addressed this explicitly, but the work is theoretical anyway, so this is minor.”*]\n\nWe discuss (what we view as) the most important limitations of our work (allowing intermediate forms of adversary, better regret rates in the bandit setting) in the Conclusion as directions for future work. However, we would be happy to add further discussion on other limitations in our next revision.", "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": "7MHVb5MItq", "reviewer": "Reviewer_zDTp", "summary": "The paper examines online learning within Stackelberg games, incorporating additional contextual information. Specifically, at each round $t$, both the follower and the leader observe a shared context $z_t$, which impacts their respective utilities. The leader, who is also the learner in this online learning framework, then selects a mixed strategy $x_t$​ from its set of possible actions. Following this, the follower observes the leader's actions and chooses a best-response action based on both the leader's action and the given context. The learner's objective is to choose a sequence of probability distributions that maximizes overall utility. The authors evaluate the performance of no-regret algorithms using the concept of *\"policy regret,\"* aiming to achieve sublinear regret relative to the optimal *\"fixed contextual policy\"* that assigns a probability distribution to each context.\n\nThe authors present several positive and negative results:\n\n1. When the context and the type of players are adversarially selected, there is no $o(T)$-regret algorithm.\n\n2. When the types of players arrive according to a fixed probability distribution but the contexts are adversarially selected, the authors provide an $O(T^{1/2})$-regret algorithm.\n\n3. When the contexts arrive according to a fixed probability distribution but the types of followers arrive according to a fixed probability distribution, the authors provide an $O(T^{1/2})$-regret algorithm.\n\n4. Finally, the authors extend their results to the bandit case by providing O(T2/3)O(T^{2/3})O(T2/3)-regret algorithms.", "questions": "What are the main challenges of extending your results in infinite action games with convex structure?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I find the problem of online learning in Stackelberg games, where both the follower and the leader observe contextual side information, to be well-motivated and of significant interest to the game theory and learning community. The authors have thoroughly examined several aspects of the problem. Despite the negative results in the case of adversarially selected contexts and types, they provide positive results in the stochastic case. Furthermore, the results appear solid and present considerable technical interest.", "weaknesses": "The regret bounds for the bandit case are not tight. However I believe the paper provides interesting first results for an interesting problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[*“The regret bounds for the bandit case are not tight. However I believe the paper provides interesting first results for an interesting problem.”*]\n\nWe would like to point out that it is actually unclear whether or not an algorithm exists for the bandit settings which achieves better than O(T^{2/3}) regret. While we hypothesize that getting O(T^{1/2}) regret should be possible, the algorithmic ideas used to get O(T^{1/2}) regret in the online Stackelberg setting without side information do not extend to our setting in a straightforward way. \n\n[*“What are the main challenges of extending your results in infinite action games with convex structure?”*]\n\nSince the leader’s strategy is a probability distribution over actions, one could view the leader as picking from infinitely-many actions. If you are asking about how one would extend our results to settings in which the leader’s strategy is not a probability simplex but is instead some general convex set, the problem becomes more tricky. To generalize to this setting, one would need to be able to reason about how different follower types would best-respond to different leader strategies. One could then hope to leverage the structure of this best-response in order to derive a computationally-tractable algorithm (i.e. in a way analogous to how we use Lemma 4.4).", "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:
Thanks for taking the time and effort to review our submission. To summarize, we initiate the study of Stackelberg games with side information, which despite the presence of side information in many Stackelberg game settings, has not received attention from the community so far. We provide algorithms for regret minimization in Stackelberg games with side information, whose analysis requires new ideas and techniques when compared to algorithms for learning in Stackelberg games without side information.

 At the request of reviewers C9HM and YfNJ, we have included numerical experiments (summarized in the attached pdf) which show that our algorithms compare favorably to algorithms for learning in Stackelberg games which do not take side information into consideration. If you would like to see our code, we are happy to provide an anonymized link to the AC (as per the NeurIPS rebuttal instructions). Please find our responses to your other questions below.

Meta-review: This paper studied the regret minimization in Stackelberg games with side information which consider the additional information available to each player. The paper found that achieving no-regret learning is impossible in fully adversarial settings. However, it demonstrated that no-regret learning is achievable in scenarios where either the sequence of contexts or followers is chosen stochastically.

The idea of using side-information to learn to play Stackelberg games is interesting and well-motivated.
The paper is technically sound with rigorous proofs and a clear exposition of both theoretical and practical implications of the findings.
On the other side many doubts have been raised both on the practicality and applicability in real system of current results, and on the apparent difficulty of generalizing results to more general settings.
The authors should also revise the paper by including more detailed comments on the computational complexity, on the similarities and differences of the proposing method with contextual bandit learning, and possibly include numerical results, as highlighted in the reviews.
Decision: Accept (poster)