Regret Minimization in Stackelberg Games with Side Information

Authors: keegan  harris
zhiwei steven wu
maria-florina  balcan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-05 15:10:34

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.

Main paper: 
 introduction: 
 A Stackelberg game [30, 31] is a strategic interaction between two utility-maximizing players in which one player (the leader) is able to commit to a (possibly mixed) strategy before the other player (the follower) takes an action. While Stackelberg's original formulation was used to model economic competition between firms, Stackelberg games have been used to study a wide range of topics in computing ranging from incentives in algorithmic decision-making [15] 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 [18] , and patrol boat schedules for the United States Coast Guard [1] . 1However in many real-world settings which are typically modeled as Stackelberg games, the payoffs of the players often depend on 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 a successful attack to the attacker) depends on factors such as the arrival and departure city of 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 to 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 as the weather and time of year may make certain species of 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 a 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, we 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 a mixed strategy over a finite set of actions, and the follower best-responds to both (1) the leader's strategy and (2) the context in order to maximize their utility. We allow the follower in each round to be one of K types. 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 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 is 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) a 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 is 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 1), 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 to instantiate the leader's estimation procedure so that the regret of Algorithm 1 is O(min{K, A f } T log(T )), where T is the time horizon, K is the number of follower types, and A f is the number of follower actions. In the stochastic context setting, we show the leader can obtain O( KT log(T ) + K) regret by playing Hedge over a finite set of policies (Algorithm 2). An important intermediate result in both settings is that it is (nearly) without loss of generality to consider leader policies which map to a finite set of mixed strategies E z , given context z. 2Next, we extend our algorithms for both types of adversary to the setting in which the leader does not get to observe the follower's type after each round, but instead only gets to observe their action. We refer to this type of feedback as bandit feedback. Both of our extensions to bandit feedback make use of the notion of a barycentric spanner [4] , a 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 a barycentric spanner has low variance, in order to show that a natural extension of our greedy algorithm obtains Õ(T 2/3 ) regret.We also make use of barycentric spanners in the (bandit) stochastic context setting, albeit in a different way. Here, our algorithm proceeds by splitting the time horizon into blocks, and using a barycentric spanner to estimate 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 Õ(T 2/3 ) leader regret. 3 See Table 1 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 to recover the leader's optimal mixed strategy have also been studied in Stackelberg security games [5, 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 4.2 and Appendix C.2 may be viewed as a generalization of their results to the setting in which the payoffs of both players depend on an external context. Roughly speaking, Balcan et al. [5] show that it without loss to play Hedge over a finite set Full Feedback Bandit Feedback Fully Adversarial Ω(T ) (Section 3)Ω(T ) (Section 3) Stochastic Followers, Adversarial Contexts O min{K, A f } √ T log T (Section 4.1) O K 2/3 A 2/3 f T 2/3 log 1/3 T (Appendix C.1) Stochastic Contexts, Adversarial Followers O √ KT log T + K (Section 4.2) O KA 1/3 f T 2/3 log 1/3 T (Appendix C.2)Table 1 : Summary of our results. Under bandit feedback, we consider a 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-chosen sequence of follower types. In order to handle the additional side information available in our setting, we instead play Hedge over a finite set of policies, each of which map to a finite set of (context-dependent) mixed strategies. However, the discretization argument is more nuanced in our setting. In particular, it is not without loss of generality to consider a finite set of policies. As a result, we 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 the effects of non-myopic followers [13] and followers who respond to calibrated predictions [14] .Lauffer et al. [20] study a Stackelberg game setting in which there is an underlying (probabilistic) state space which affects the leader's rewards, and there is a single (unknown) follower type. In contrast, we study a setting in which the sequence of follower types and/or contexts may be chosen adversarially. Sessa et al. [25] study a repeated game setting in which the players receive additional information (i.e. a 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. [33] , Anagnostides et al. [3] study learning dynamics in time-varying game settings, and Harris et al. [16] study a meta-learning setting in which the game being played changes after a fixed number of rounds.Finally, our problem may be viewed is a special case of the contextual bandit setting with adversariallychosen utilities [28, 29, 24] , where the learner gets to observe "extra information" in the form of the follower's type (Section 4) or the follower's action (Section 5). However, there is much to gain from taking 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-shelf adversarial contextual bandit algorithms 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, 29] , Rakhlin and Sridharan [24] ) or (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 et al. [28] ). We require no such assumptions. 
setting and background: 
 Notation. We use [N ] := {1, . . . , N } to denote the set of natural numbers up to and including N ∈ 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(p, q) = 1 2 |p(x) -q(x)|dx is the total variation distance between distributions p and q, and E t [x] = E[x|F t ] is shorthand for the expected value of the random variable x, conditioned on the filtration up to (but not including) time t. All proofs 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 a sequence of followers. In each round t ∈ [T ], Nature reveals a context z t ∈ Z ⊆ R d to both players. 4 The leader moves first by playing some mixed strategy x t ∈ X ⊆ R A over a set of (finite) leader actions A, i.e., x t ∈ ∆(A). The size of A is A := |A|. Having observed the leader's mixed strategy, the follower best-responds to both x t and z t by playing some action a f ∈ A f , where A f is the (finite) set of follower actions and A f := |A f |. Definition 2.1 (Follower Best-Response). Follower f 's best-response to context z and mixed strategyx is b f (z, x) ∈ arg max a f ∈A f a l ∈A x[a l ] • u f (z, a l , a f ), where u f : Z × A × A f → [0, 1] is follower f 's utility function.In the case of ties, we assume that there is a fixed and known ordering over actions which determines how the follower best-responds, i.e. if a > a ′ for a, a ′ ∈ A f then the follower will break ties between a and a ′ in favor of a. 5We allow for the follower in round t (denoted by f t ) to be one of K ≥ 1 follower types {α (1) , . . . , α (K) } (where K ≤ T ). Follower type α (i) is characterized by utility function u α (i) : Z × A × A f → [0, 1], i.e. given a context z, leader action a l , and follower action a f , a follower of type α (i) would receive utility u α (i) (z, a l , a f ). 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 × A × A f → [0, 1]and assume it is known to the leader. We often use the shorthand u(z, x, a f ) = a l ∈A x[a l ]•u(z, a l , a f ) to denote the leader's expected utility of playing mixed strategy x under context z against follower action a f . Follower f t 's expected utility u ft (z, x, a f ) is defined analogously.A leader policy π : Z → X is a (possibly random) mapping from contexts to mixed strategies. If the leader using policy π t in round t and observes context z t , their strategy x t is given by x t ∼ π t (z t ). Definition 2.2 (Optimal Policy). Given a sequence of followers f 1 , . . . , f T and contexts z 1 , . . . , z T , the strategy given by the leader's optimal-in-hindsight policy for contextz is π * (z) ∈ arg max x∈X T t=1 u(z, x, b ft (z, x)) • 1{z t = z}.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 f 1 , . . . , f T and contexts z 1 , . . . , z T , the leader's contextual Stackelberg regret is R(T ) := T t=1 u(z t , π * (z t ), b ft (z t , π * (z t ))) -u(z t , x t , b ft (z t , x t )), where x 1 , . . . , x T is the sequence of mixed strategies played by the leader.If an algorithm achieves regret R(T ) = o(T ), we say that it is a no-regret algorithm. We consider three ways in which Nature can select the sequence of contexts/followers:1. If the sequence of contexts (resp. follower types) are drawn i.i.d. 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 in order to harm the leader (possibly using knowledge of the leader'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 t (resp. follower f t ) before round t 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 3 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 4 hold 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 a non-adaptive adversary and the other sequence is chosen stochastically. 
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 2 if 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 π * to be arbitrarily (1.) the learner observes a point ω t , (2.) the learner takes a guess g t , and (3.) the learner observes the true label y t . Given a regret minimizer for our setting, we show how to use it in a black-box way (by constructing functions h 1 , h 2 , h 3 ) to achieve no-regret in the online linear thresholding problem.complex, we show that this result holds even when the policy class to which π * belongs is highly structured. We show this via a 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 a repeated two-player game between a learner and an adversary. Before the first round, an adversary chooses a cutoff s ∈ [0, 1] which is unknown to the learner. In each round, the adversary chooses a point ω t ∈ [0, 1] and reveals it to the learner. ω t is assigned label y t = 1 if ω t > s and label y t = -1 otherwise. Given ω t , the learner makes a guess g t ∈ [0, 1] (the probability they place on y t = 1), and receives utilityu OLT (ω t , g t ) = g t • 1{y t = 1} + (1 -g t ) • 1{y t = -1}.The learner gets to observe y t after round t is over. The learner's policyπ t : [0, 1] → [0, 1] is a mapping from points in [0, 1] to guesses in [0, 1].The optimal policy π * makes guess π * (ω t ) = 1 if ω t > s and π * (ω t ) = 0 otherwise. The learner's regret after T rounds is given by R OLT (T ) = T -T t=1 u OLT (ω t , g t ), since the optimal policy achieves utility 1 in 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 on regret in the online linear thresholding setting (see e.g. [12] ). Lemma 3.1. Any algorithm suffers regret R OLT (T ) = Ω(T ) in the online linear thresholding problem when the sequence of points ω 1 , . . . , ω T is chosen by an adversary. Theorem 3.2. If an adversary can choose both the sequence of contexts z 1 , . . . , z T and the sequence of followers f 1 , . . . , f T , no algorithm can achieve better than Ω(T ) contextual Stackelberg regret in expectation over the internal randomness of the algorithm, even when π * is restricted to come from the set of linear thresholding functions.The reduction from online linear thresholding proceeds by creating an instance of our setting such that the sequence of contexts z 1 , . . . , z T correspond to the sequence of points ω 1 , . . . , ω T encountered by the learner, and the sequence of follower types f 1 , . . . , f T correspond to the sequence of labels y 1 , . . . , y T . We then show that a no-regret algorithm in the online thresholding problem can be obtained by using an algorithm which minimizes contextual Stackelberg regret on the constructed game instance as a black box. However this is a contradiction, since by Lemma 3.1 the online thresholding problem is not online learnable by any algorithm. See Figure 1 for a visualization of our reduction.Intuitively, this reduction works because the adversary can "hide" information about the follower's type f t in the context z t . 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 3.1. 
limiting the power of the adversary: 
 Motivated by the impossibility result of Section 3, we study two natural relaxations of the fully adversarial setting: one in which the sequence of followers is chosen stochastically but the contexts are chosen adversarially (Section 4.1) and one in which the sequence of contexts is chosen stochastically but followers are chosen adversarially (Section 4.2). In both settings we allow the adversary to be adaptive.An important structural results for both Section 4.1 and Section 4.2 is that for any context z ∈ Z, the leader incurs only negligible regret by restricting themselves to policies which map to mixed strategies in some finite (and computable) set E z . In order to state this result formally, we need to introduce the notion of a contextual best-response region, which is a generalization of the notion of a best-response region in (non-contextual) Stackelberg games (e.g. [21, 5] ). Definition 4.1 (Contextual Follower Best-Response Region). For follower type α (i) , follower action a f ∈ A f , and context z ∈ Z, let X z (α (i) , a f ) ⊆ X denote the set of all leader mixed strategies such that a follower of type α (i) best-responds to all x ∈ X z (α (i) , a f ) by playing action a f under context z, i.e., X z (α(i) , a f ) = {x ∈ X : b α (i) (z, x) = a f }.Definition 4.2 (Contextual Best-Response Region). For a given function σ : {α (1) , . . . , α (K) } → A f , let X z (σ) denote the set of all leader mixed strategies such that under context z, a follower of typeα (i) plays action σ(α (i) ) for all i ∈ [K], i.e. X z (σ) = ∩ i∈[K] X z (α (i) , σ(α (i) )).For a fixed contextual best-response region X z (σ), we refer to the corresponding σ as the bestresponse function for region X z (σ), as it maps each follower type to its best-response for every leader strategy x ∈ X z (σ). We sometimes use σ (z,x) to refer to the best-response function associated with mixed strategy x under context z, and we use Σ z to refer to the set of all best-response functions under context z. Note that |Σ z | ≤ A K f for any context z ∈ Z. This gives us an upper-bound on the number of best-response regions for a 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 ∆ d and (2) the intersection of finitelymany half-spaces. While every X 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 to an extreme point of some 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 to some approximate extreme point of a contextual best-response region. Definition 4.3 (δ-approximate extreme points). Fix a context z ∈ Z and consider the set of all nonempty contextual best-response regions. For δ > 0, E z (δ) is the set of leader mixed strategies such that for all best-response functions σ and anyx ∈ ∆(A l ) that is an extreme point of cl(X z (σ)), x ∈ E z (δ) if x ∈ X z (σ). Otherwise there is some x ′ ∈ E z (δ) such that x ′ ∈ X z (σ) and ∥x ′ -x∥ 1 ≤ δ.Note that Definition 4.3 is constructive. We set δ = O( 1T ) so that the additional regret from only considering policies which map to points in ∪ z∈Z E z (δ) is negligible. As a result, we use the shorthand E z := E z (δ) throughout the sequel. The following lemma is a generalization of Lemma 4.3 in Balcan et al. [5] to our setting, and its proof uses similar techniques from convex analysis. Lemma 4.4. For any sequence of followers f 1 , . . . f T and any leader policy π, there exists a policy π (E) : Z → ∪ z∈Z E z that, when given context z, plays a mixed strategy in E z and guarantees thatT t=1 u(z t , π(z t ), b ft (z t , π(z t ))) -u(z t , π (E) (z t ), b ft (z t , π (E) (z t ))) ≤ 1.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 E z for every z ∈ Z before the game begins. Instead, they can compute E zt in round t before they commit to their mixed strategy. While E zt is computatable, it may be exponentially large in A f and K. However this is to be expected as Li et al. [22] show that in its general form, solving the non-contextual version of the online Stackelberg game problem is NP-Hard.In this setting we allow the sequence of contexts to 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 z t , we allow the adversary to have knowledge of F and f 1 , . . . , f t-1 , but not f t . 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 a sequence of contexts z 1 , . . . , z T , the leader's expected contextual Stackeleberg regret isE[R(T )] := E f1,...,f T ∼F [ T t=1 u(z t , π * (z t ), b ft (z t , π * (z t ))) -u(z t , x t , b ft (z t , x t ))], where π * is the optimal policy given knowledge of z 1 , . . . , z T and F. E f1,...,f T ∼F T t=1 u(z t , π(z t ), b ft (z t , π(z t ))) = T t=1 E f1,...,ft-1∼F [E t [u(z t , π(z t ), b ft (z t , π(z t )))]].EQUATIONand acting greedily with respect to our estimate. Herep t (b ft (z t , π(z t )) = a f ) is the (estimated)probability that the follower's best-response is a f , given context z t and leader mixed strategy π(z t ).As we will see, different instantiations of p t will lead to different regret rates for Algorithm 1. However, before instantiating Algorithm 1 with a specific estimation procedure, we provide a general result which bounds the regret of Algorithm 1 in terms of the total variation distance between the sequence { p t } t∈[T ] and the true distribution p. Theorem 4.6.Let p(z, x) := [p(b ft (z, x) = a f )] a f ∈A f and p t (z, x) := [ p t (b ft (z, x) = a f )] a f ∈A f . The expected contextual Stackelberg regret (Definition 4.5) of Algorithm 1 satisfies E[R(T )] ≤ 1+2 T t=1 E f1,...,ft-1 [TV(p(z t , π (E) (z t )), p t (z t , π (E) (z t )))+TV(p(z t , π t (z t )), p t (z t , π t (z t )))].Theorem 4.6 shows that the regret of Algorithm 1 is proportional to how well it estimates p(z, x) over time (as measured by total variation distance), on (1) the sequence of contexts chosen by the adversary and (2) the sequence of mixed strategies played by Algorithm 1 and the (near-)optimal policy π (E) . While we instantiate Algorithm 1 in the setting where there are finitely-many follower types and follower actions, Theorem 4.6 opens the door to provide meaningful regret guarantees in settings in which there are infinitely-many follower types and/or follower actions. 6 We now instantiate the estimation procedure in Algorithm 1 in two different ways to get end-to-end regret guarantees. First, the leader can get regret O(K √ T log T ) by estimating the distribution of follower types directly.Corollary 4.7.EQUATIONp 1 (f = α (i) ) = 1 K for i ∈ [K], then the regret of Algorithm 1 satisfies E[R(T )] = O(K T log(T )).The leader can obtain a complementary regret bound of O(A f √ T log T ) if they instead estimate the probability that the follower best-responds with action a f ∈ A f , given a particular context z and leader mixed strategy x. 7 In what follows, we use 1 (σ (z,x) =a f ) ∈ {0, 1} K to refer to the indicator vector whose i-th component is 1{σ (z,x) (α (i) ) = a f }, i.e. the indicator that a follower of type α (i) best-responds to context z and mixed strategy x by playing action a f . Corollary 4.8.If p t (z, x) = { p t (1 (σ (z,x) =a f ) )} a f ∈A f , p t+1 (1 (σ (z,x) =a) ) = 1 t t τ =1 1{b fτ (z, x) = a}, and p 1 (1 (σ (z,x) =a) ) = 1 A f for a f ∈ A f , then the regret of Al- gorithm 1 satisfies E[R(T )] = O(A f T log(T )).We now consider the setting in which the sequence of contexts are drawn i.i.d. from some unknown distribution P and the follower f t is chosen by an adversary with knowledge of P and z 1 , . . . , z t-1 , 6 All that is required to run Algorithm 1 in a particular problem instance is an oracle for evaluating Et[u(z, x, b f t (z, x))] and updating pt. 7 In general K has no dependence on A f , and vice versa.Algorithm 2: Learning with stochastic contexts: full feedbackInput: Set of weights Ω Let q 1 [π (ω) ] := 1, p 1 [π (ω) ] := 1 |Π| for all π (ω) ∈ Π := {π (ω) } ω∈Ω for t = 1, . . . , T do Sample π t ∼ p t , a l,t ∼ π t (z t ), receive utility u(z t , a l,t , b ft (π t (z t ))), observe type f t . For each policy π (ω) ∈ Π, compute ℓ t [π (ω) ] := -u(z t , π (ω) (z t ), b ft (z t , π (ω) (z t ))) and set q t+1 [π (ω) ] = exp(-η t s=1 ℓ s [π (ω) ]), p t+1 [π (ω) ] = q t+1 [π (ω) ]/ π (ω ′ ) ∈Π q t+1 [π (ω ′ )]. end but not z t . 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 a distribution over contexts P and a sequence of followers f 1 , . . . , f T , the leader's expected contextual Stackeleberg regret isE[R(T )] := E z1,...,z T ∼P T t=1 u(z t , π * (z t ), b ft (z t , π * (z t ))) -u(z t , x t , b ft (z t , x t )) ,where π * is the optimal policy given knowledge of f 1 , . . . , f T and P.Our key insight is that when the sequence of contexts is generated stochastically, to obtain no-regret it suffices to (1) play a standard, off-the-shelf online learning algorithm (e.g. Hedge) over a finite (albeit exponentially-large) 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 asE z1,...,z T T t=1 u(z t , π(z t ), b ft (z t , π(z t ))) = K i=1 E z [u(z, π(z), b α (i) (z, π(z)))] T t=1 E z1,...,zt-1 [1{f t = α (i) }] .Using Lemma 4.10, we now show that it suffices to play Hedge over a finite set of policies Π in order for the leader to obtain no-regret (Algorithm 2). The key step in our analysis is to show that the discretization error is small for our chosen policy class Π. 8 For a given weight vectorω ∈ R K , let π (ω) (z) := arg max z∈Ez K i=1 u(z, x, b α (i) (z, x)) • ω[i].For a given set of weight vectors Ω, we set Π to be the induced policy class, i.e. Π := {π (ω) } ω∈Ω . Theorem 4.11.If Ω = {ω : ω ∈ ∆ K , T • ω[i] ∈ N, ∀i ∈ [K]} and η = log Π T , then Algorithm 2 obtains expected contextual Stackelberg regret (Definition 4.9) E[R(T )] = O √ KT log T + K .We conclude by briefly comparing our results with those of the non-contextual Stackelberg game setting 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 t also depend on a stochastically-generated context z t . When |Z| = 1, we recover their setting exactly. Under their non-contextual setting, there is only one set of approximate extreme points E z , and so we write the E = E z . Here it suffices to consider the set of constant "policies" which always map to one of the (approximate) extreme points in E. Plugging this choice of Π into Algorithm 2, we recover their algorithm (and therefore also their regret rates) exactly.However, it is also worth noting that more care must be taken to obtain regret guarantees against an adaptive adversary in our setting compared to the non-contextual setting of Balcan et al. [5] . 9 In particular, we need to bound the discretization error due to considering a finite set of policies, but it is without loss of generality to consider a finite set of mixed strategies in the non-contextual setting. We empirically evaluate the performance of Algorithm 1 and Algorithm 2 on synthetically-generated data. We consider a setup in which K = 5, A = A f = 3, and the context dimension d = 3. Utility functions are linear in both the context and player actions, and are sampled u.a.r. from [-1, 1] 3×3×3 .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 a 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 2b , contexts are 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 2c , both contexts and follower types are chosen stochastically. Specifically, contexts are generated as in Figure 2b and follower types are generated as in Figure 2a .We find that Algorithm 1 and Algorithm 2 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 1 (resp. Algorithm 2) performs poorly whenever followers (resp. contexts) are chosen non-stochastically. 
extension to bandit feedback: 
 We have so far assumed that the leader gets to 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 to deduce the organization responsible for a 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 to 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 we say about the leader's ability to learn under bandit feedback when there is side information?While our impossibility result of Section 3 immediately applies to this more challenging setting, our algorithms from Section 4 do not. This is because we can no longer compute quantities such as 1{f t = α (i) } or b ft (z t , x) for an arbitrary mixed strategy x from just follower f t 's action alone. We still assume that the follower is one of K different types, although f t 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 utility function may still depend on the context z t , we assume that the follower's utility is a function of the leader's mixed strategy x t alone, i.e. u f (z, x, a f ) = u f (x, a f ) for all z ∈ Z. This allows us to drop the dependence on z t from both the follower's best response and the set of approximate extreme points, i.e. b f (z, x) becomes b f (x) and E z becomes E. Furthermore, our definitions of contextual follower best-response region (Definition 4.1) and contextual best-response region (Definition 4.2) collapse to their non-contextual counterparts. Depending on the application domain, the assumption that only the leader's utility depends on the side information may be reasonable. For instance, while an institution would prefer that a server with less traffic is hacked compared to one with more, a hacker might only care about the information hosted on the server (which may not be related to network traffic patterns). Second, we design algorithms with regret guarantees which only hold against a non-adaptive adversary. 10 Despite these relaxations, 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 ft (x) = a f ) (i.e. the probability that follower at round t best-responds with action a f when the leader plays mixed strategy x) for allx ∈ E and a f ∈ A f , doing so naively would take exponentially-many rounds, due to the size of E.Building off of results in the non-contextual setting of Balcan et al. [5] , we leverage the fact that the leader's utility for different mixed strategies is 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, it suffices to estimate this linear function (which can be done using as few as K samples) to get an unbiased estimate of p(b ft (x) = a f ) for any x ∈ E and a f ∈ A f . Borrowing from the literature on linear bandits, we use a barycentric spanner [4] to estimate {{p(b ft (x) = a f )} a f ∈A f } x∈E 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, 1].In Appendix C.1, we use the property that estimators constructed using barycentric spanners have low variance to show that an explore-then-exploit algorithm achieves O(K 2/3 A 2/3 f T 2/3 log 1/3 T ) expected contextual Stackelberg regret in the setting with stochastic follower types and adversarial contexts. Specifically, our algorithm (Algorithm 3) plays a special set of K mixed strategies N times each, then uses barycentric spanners to estimate {p t (1 (σ (z,x) =a f ) )} a f ∈A f for all x ∈ X and z ∈ Z, after which Algorithm 3 plays greedily like in Section 4.1.In Appendix C.2, we use the property that estimators constructed using barycentric spanners are bounded to design a reduction to our algorithm in Section 4.2 which achieves O(KA 1/3 f T 2/3 log 1/3 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( √ T ) regret without using barycentric spanners, this would come at the cost of a linear dependence on |E| (and therefore an exponential dependence on K and A f ) in regret. 
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 is not possible even for highly structured policy classes. When either sequence is chosen stochastically, we obtain algorithms with Õ( √ T ) regret. We also explore an extension to bandit feedback, in which we obtain Õ(T 2/3 ) 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 consider, while natural, rule out the leader learning about the follower'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 Littlestone dimension. It would be interesting to further explore this direction to pin down when no-regret learning is possible.2. Õ(T 1/2 ) regret under bandit feedback. Bernasconi et al. [6] obtain O(T 1/2 ) regret when learning in non-contextual Stackelberg games under bandit feedback against an adversarially-chosen 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 Õ(T 1/2 ) contextual Stackelberg regret is possible under bandit feedback as a natural and exciting future direction.A Appendix for Section 3: On the impossibility of fully adversarial no-regret learning Theorem 3.2. If an adversary can choose both the sequence of contexts z 1 , . . . , z T and the sequence of followers f 1 , . . . , f T , no algorithm can achieve better than Ω(T ) contextual Stackelberg regret in expectation over the internal randomness of the algorithm, even when π * 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 o(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 z t and produces a mixed strategy x t .We now describe the family of contextual Stackelberg game instances we reduce to. Consider the setting in which there are two follower types (α (1) and α (2) ) and two leader/follower actions (A = A f = {a 1 , a 2 }). Suppose that the context space is of the form Z = [0, 1], and that regardless of the realized context or leader mixed strategy, the best-response of follower type α (1) is to play action a 1 (b α (1) (z, x) = a 1 , ∀z ∈ Z, x ∈ X ) and the best-response of follower type α (2) is to play action a 2 (b α (2) (z, x) = a 2 , ∀z ∈ Z, x ∈ X ). Since the follower's best-response does not depend on the leader's mixed strategy or the context, we use the shorthand b ft := b ft (z t , x t ). Finally, suppose that the leader's utility function is given by u(z, a l , a f ) = 1{a l = a f }. Note that this is a special case of our general setting (described in Section 2).The reduction from online linear thresholding proceeds as follows. In each round t ∈ [T ],1. Given a point ω t ∈ [0, 1], we give the context z t = ω t as input to ALG. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 or 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 as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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, we hope that our work will one day lead to the design and implementation of better algorithms for solving Stackelberg security games in practice, which would have a positive societal impact in domains such as airport security and the protection of wildlife against poaching.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: In return, we receive mixed strategy x t ∈ ∆({a 1 , a 2 }) from ALG. We set g t = x t [1]. 11 3. Play according to g t , and receive label y t and utility u OLT (ω t , g t ) from Nature. Give follower typef t = α (1) if y t = 1 α (2) if y t = -1 and utility u(z t , x t , b ft ) = x t [1] • 1{b ft = a 1 } + x t [2] • 1{b ft = a 2 } as input to ALG.Observe that under this reduction,EQUATIONsince if z > s, f t = α (1) and otherwise f t = α (0) . By playing according to π * , we can ensure that u(z t , π * (z t ), b ft ) = 1 for all t ∈ [T ]. π * must then be optimal, because 1 is the largest possible per-round utility that the leader can receive.Since ALG achieves no-contextual-Stackelberg-regret, we know by Definition 2.3 thatEQUATIONTo conclude, it suffices to show that R OLT (T ) = o(T ) using Equation (2) and Equation (3). Applying Equation (2), we see thatEQUATIONBy construction, 1{b ft = a 1 } = 1{y t = 1}, 1{b ft = a 2 } = 1{y t = -1}, x t [1] = g t , andx t [2] = 1 -g t . Substituting this into Equation ( 4), we see thatR(T ) = T - T t=1 (g t • 1{y t = 1} + (1 -g t ) • 1{y t = -1}) =: R OLT (T ).(5) 11 Observe that xt[2] = 1 -gt.By Equation (3) and Equation ( 5), we can conclude that R OLT (T ) = o(T ). However, this is a 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 no-contextual-Stackelberg-regret whenever the sequence of contexts and follower types is chosen by an adversary.B Appendix for Section 4: Limiting the power of the adversary Lemma 4.4. For any sequence of followers f 1 , . . . f T and any leader policy π, there exists a policy π (E) : Z → ∪ z∈Z E z that, when given context z, plays a mixed strategy in E z and guarantees thatT t=1 u(z t , π(z t ), b ft (z t , π(z t ))) -u(z t , π (E) (z t ), b ft (z t , π (E) (z t ))) ≤ 1.Moreover, the same result holds in expectation over any distribution over follower types F.Proof. Observe that for any z,π * (z) := arg max x∈∆(A l ) T t=1 1{z t = z} a l ∈A l x[a l ] • u(z, a l , b ft (z, x)) = arg max x∈∆(A l ) K i=1 a l ∈A l x[a l ] • u(z, a l , b α (i) (z, x)) T t=1 1{z t = z, f t = α (i) }The solution to the above optimization may be obtained by first solvingEQUATIONfor every possible setting of a (1) , . . . , a (K) , and then taking the maximum of all feasible solutions. Since Equation ( 6) is an optimization over contextual best-response region X z (a (1) , . . . , a (K) ) and all contextual best-response regions are convex polytopes, π * (z) will be an extreme point of some contextual best-response region, although it may not be attained. Overloading notation, let X z (π * (z)) denote the contextual best-response region corresponding to π * (z), i.e., π * (z) ∈ X z (π * (z)). Since for a fixed context z ∈ Z the leader's utility is a linear function of x over the convex polytope X z (π * (z)), there exists a point x(z) ∈ cl(X z (π * (z))) such thatT t=1 u(z, x(z), b ft (z, π * (z))) • 1{z t = z} ≥ T t=1 u(z, π * (z), b ft (z, π * (z))) • 1{z t = z}.Let x ′ (z) denote the corresponding point in E z such that ∥x ′ (z) -x(z)∥ 1 ≤ δ. (Such a point will always exist by Definition 4.3.) Since u ∈ [0, 1] and is linear in x for a fixed context and follower best-response,T t=1 u(z, x ′ (z), b ft (z, x ′ (z))) • 1{z t = z} = T t=1 u(z, x ′ (z), b ft (z, π * (z))) • 1{z t = z} ≥ T t=1 (u(z, x(z), b ft (z, π * (z))) -δ) • 1{z t = z} ≥ T t=1 (u(z, π * (z), b ft (z, π * (z))) -δ) • 1{z t = z}Summing over all unique z encountered by the algorithm over T time-steps, we obtain the desired result for the policy π (E) which plays mixed strategy π (E) (z) = x ′ (z) when given context z. Finally, observe that the same line of reasoning holds whenever we 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 T t=1 1{z t = z, f t = α (i) } replaced with P(f = α (i) )).E[R(T )] ≤ 1+2 T t=1 E f1,...,ft-1 [TV(p(z t , π (E) (z t )), p t (z t , π (E) (z t )))+TV(p(z t , π t (z t )), p t (z t , π t (z t )))].Proof of Theorem 4.6. For any z ∈ Z and t ∈ [T ],E t [u(z, π (E) (z), b f (z, π (E) (z)))] ≤ E t [u(z, π t (z), b f (z, π t (z)))] + E t [u(z, π t (z), b f (z, π t (z)))] -E t [u(z, π t (z), b f (z, π t (z)))].Since utilities are bounded in [0, 1] and the expectations E t and E t are taken with respect to p and p t respectively, we can upper-boundE t [u(z, π t (z), b f (z, π t (z)))] -E t [u(z, π t (z), b f (z, π t (z)))] by |d p t (z, π t (z)) -dp t (z, π t (z))| = 2TV(p(z, π t (z)), p t (z, π t (z))).Putting everything together, we get thatE t [u(z, π (E) (z), b f (z, π (E) (z)))] ≤ E t [u(z, π t (z), b f (z, π t (z)))]+2TV(p(z, π t (z)), p t (z, π t (z))).We now use this fact to bound the expected regret. By Lemma 4.4,E[R(T )] ≤ 1 + T t=1 E f1,...,ft [u(z t , π (E) (z t ), b ft (z t , π (E) (z t ))) -u(z t , π t (z t ), b ft (z t , π t (z t )))] ≤ 1 + T t=1 E f1,...,ft-1 [E t [u(z t , π (E) (z t ), b ft (z t , π (E) (z t )))] -E t [u(z, π (E) (z), b ft (z, π (E) (z)))] + 2TV(p(z, π t (z)), p t (z, π t (z)))].By repeating the same steps as above, we can upper-boundE t [u(z t , π (E) (z t ), b f (z t , π (E) (z t )))] -E t [u(z, π (E) (z), b f (z, π (E) (z)))]by 2TV(p(z t , π (E) ), p t (z t , π (E) )). This gets us the desired result.Corollary 4.7.EQUATIONp 1 (f = α (i) ) = 1 K for i ∈ [K], then the regret of Algorithm 1 satisfies E[R(T )] = O(K T log(T )). Proof. For t ≥ 2, TV(p(z, x), p t (z, x)) = 1 2 K i=1 |p t (f t = α (i) ) -p t (f t = α (i) )| = 1 2 K i=1 1 t -1 t-1 τ =1 1{f τ = α (i) } -E fτ [1{f τ = α (i) }]for any z ∈ Z and x ∈ X . By Hoeffding's inequality, we know that1 t -1 t-1 τ =1 1{f τ =α (i) } -E fτ [1{f τ =α (i) }] ≤ 2 log(2T ) t -1simultaneously for all t ∈ [T ] and i ∈ [K], with probability at least 1 -1 T 2 . Dropping the dependence of p, p t on z and x, we can conclude thatE f1,...,ft-1 [TV(p, p t )] ≤ K log(2T ) t -1 + 1 2T(since K ≤ T ), and soE[R(T )] ≤ 1 + 4 T t=1 K log(2T ) t -1 + 1 2T = O K T log(T ) . Corollary 4.8. If p t (z, x) = { p t (1 (σ (z,x) =a f ) )} a f ∈A f , p t+1 (1 (σ (z,x) =a) ) = 1 t t τ =1 1{b fτ (z, x) = a}, and p 1 (1 (σ (z,x) =a) ) = 1 A f for a f ∈ A f , then the regret of Al- gorithm 1 satisfies E[R(T )] = O(A f T log(T )). Proof. For t ≥ 2, TV(p(z, x), p t (z, x)) = 1 2 a∈A f |p t (1 (σ (z,x) =a) ) -p t (1 (σ (z,x) =a) )| = 1 2 a∈A f |p(1 (σ (z,x) =a) ) - 1 t -1 t-1 τ =1 1{b fτ (z, x) = a}| = 1 2 a∈A f 1 t -1 t-1 τ =1 1{b fτ (z, x) = a} -E fτ [1{b fτ (z, x) = a}]for any z ∈ Z, x ∈ X . By Hoeffding's inequality,1 t -1 t-1 τ =1 1{b fτ (z, x) = a} -E fτ [1{b fτ (z, x) = a}] ≤ 2 log(2T ) t -1simultaneously for all t ∈ [T ] and i ∈ [K], with probability at least 1 -1 T 2 . Using this fact, we can conclude thatE f1,...,ft-1 [TV(p(z, x), p t (z, x))] ≤ A f log(2T ) t -1 + 1 2T(since K ≤ T ) andE[R(T )] ≤ 1 + 4 T t=1 A f log(2T ) t -1 + 1 2T ≤ 3 + 4A f log(2T ) T t=0 1 √ t dt = O A f T log(T ) .The following regret guarantee for Hedge is a well-known result. (See, e.g. Gupta [11] .)Lemma B.1. Hedge enjoys expected regret rate O( √ T log n) when there are n actions, the learning rate is chosen to be η = log n T , and the sequence of utilities for each arm are chosen by an adversary.Lemma 4.10. When the sequence of contexts is determined stochastically, the expected utility of any fixed policy π may be written asE z1,...,z T T t=1 u(z t , π(z t ), b ft (z t , π(z t ))) = K i=1 E z [u(z, π(z), b α (i) (z, π(z)))] T t=1 E z1,...,zt-1 [1{f t = α (i) }] .Proof. For any fixed policy π,E z1,...,z T T t=1 u(z t , π(z t ), b ft (z t , π(z t ))) = T t=1 E z1,...,zt K i=1 u(z t , π(z t ), b α (i) (z t , π(z t )))1{f t = α (i) } = T t=1 K i=1 E zt [u(z t , π(z t ), b α (i) (z t , π(z t )))]E z1,...,zt-1 [1{f t = α (i) }]where the second line uses the fact that f t cannot depend on z t , and the result follows from the fact that z 1 , . . . , z T are i.i.d. E[R(T )] = E z1,...,z T T t=1 u(z t , π * (z t ), b ft (z t , π * (z t ))) -u(z t , π t (z t ), b ft (z t , π t (z t ))) ≤ E z1,...,z T T t=1 u(z t , π (E) (z t ), b ft (z t , π (E) (z t ))) -u(z t , π t (z t ), b ft (z t , π t (z t ))) + 1Let π (ω * ) denote the optimal-in-hindsight policy in Π.E[R(T )] ≤ E z1,...,z T T t=1 u(z t , π (ω * ) (z t ), b ft (z t , π (ω * ) (z t ))) -u(z t , π t (z t ), b ft (z t , π t (z t ))) + E z1,...,z T T t=1 u(z t , π (E) (z t ), b ft (z t , π (E) (z t ))) -u(z t , π (ω * ) (z t ), b ft (z t , π (ω * ) (z t ))) + 1To conclude, it suffices to bound the discretization error, asE z1,...,z T T t=1 u(z t , π (ω * ) (z t ), b ft (z t , π (ω * ) (z t ))) -u(z t , π t (z t ), b ft (z t , π t (z t ))) ≤ O T log |Π| ,which follows from applying the standard regret guarantee of Hedge (Lemma B.1 in the Appendix). Applying Lemma 4.10,E z1,...,z T T t=1 u(z t , π (E) (z t ), b ft (z t , π (E) (z t ))) -u(z t , π (ω * ) (z t ), b ft (z t , π (ω * ) (z t ))) = K i=1 (E z [u(z, π (E) (z), b α (i) (z, π (E) (z))) -u(z, π (ω * ) (z), b α (i) (z, π (ω * ) (z)))]) T t=1 E z1,...,zt-1 [1{f t = α (i) }] ≤ K i=1 E z [u(z, π (E) (z), b α (i) (z, π (E) (z)))] • T t=1 E z1,...,zt-1 [1{f t = α (i) } -T • ω * [i] + K i=1 E z [u(z, π (ω * ) (z), b α (i) (z, π (ω * ) (z)))] • T • ω * [i] - T t=1 E z1,...,zt-1 [1{f t = α (i) }where the inequality follows from adding and subtractingK i=1 E z [u(z, π (E) (z), b α (i) (z, π (E) (z)))] • T • ω * [i] and K i=1 E z [u(z, π (ω * ) (z), b α (i) (z, π (ω * ) (z)))] • T • ω * [i].Finally, we can upper-bound the discretization error by2 K i=1 T • ω * [i] - T t=1 E z1,...,zt-1 [1{f t = α (i) }] ≤ 2Kby using the fact that the sender's utility is bounded in [0, 1]. Piecing everything together and observing that |Π| ≤ T K gives us the desired regret guarantee.Recall from Section 4.1 that 1 (σ (x) =a f ) ∈ {0, 1} K is the indicator vector whose i-th component is 1{σ (x) (α (i) ) = a f }, i.e. the indicator that a follower of type α (i) best-responds to mixed strategy x by playing action a f . For any fixed policy π, we can write the sender's expected utility in round t asE ft [u(z t , π(z t ), b ft (π(z t )))] = a f ∈A f u(z t , π(z t ), a f ) • p(b f (π(z t )) = a f ) = a f ∈A f u(z t , π(z t ), a f ) • p(1 (σ (π(z t )) =a f ) ) where p(b f (π(z)) = a f ) := E f ∼F [1{b f (z) = a f }],the first line follows from the assumption of a non-adaptive adversary, the second line follows from the fact that f 1 , . . . , f T are drawn i.i.d., andp(b f (π(z)) = a f ) = p(1 (σ (π(z)) =a f ) ) := K i=1 1{b α (i) (π(z)) = a f } • P(f = α (i) ),whereP(f = α (i) ) is the probability that follower f is of type α (i) . Note that (σ (π(z t )) =a f ) ) (and therefore E ft [u(z t , π(z t ), b ft (π(z t )))]) is linear in 1 (σ (π(z t )) =a f ) .Given this reformulation, a natural approach is to estimate p(1 (σ (π(z t )) =a f ) ) as p(1 (σ (π(z t )) =a f ) ) and act greedily with respect to our estimate, like we did in Section 4.1. To do so, we define the set W := {1 (σ=a f ) | ∀a f ∈ A f , σ ∈ Σ} and estimate p(b) for every element b in the barycentric spanner B := {b (1) , . . . , b (K) } of W. 12We estimate p(b) as follows: For every b ∈ B, there must be a mixed strategy x (b) and follower action a (b) such that b = 1 (σ x (b) =a (b) ) . Therefore, if the leader plays mixed strategy x (b) N times, we set p(b) = 1 N t∈[N ] 1{b ft (x (b) ) = a (b) }. Given estimates { p(b)} b∈B , we can estimate p(1 (σ (x) =a f ) ) for any x ∈ E and a f ∈ A f as p(1 (σ (x) =a f ) ) := K i=1 λ i (1 (σ (x) =a f ) ) • p(b (i) ), where λ i (1 (σ (x) =a f ) ) ∈ [-1, 1] for i ∈ [K]are the coefficients from the barycentric spanner. 13 Note that this is an unbiased estimator, due to the fact that p(1 (σ (x) =a f ) ) is a linear function.Algorithm 3 plays each mixed strategy x (b) for b ∈ B N > 0 times in order to obtain an estimate of each p(b). 14 It then uses these estimates to construct estimates for all 1 (σ (x) =a f ) (and thereforealso E f [u(z, x, b f (x))] for all x ∈ E and z ∈ Z). Finally, in the remaining rounds Algorithm 3 acts greedily with respect to its estimate, much like in Algorithm 1.Theorem C.1. If N = O A 2/3 f T 2/3 log 1/3 (T ) K 1/3, then the expected contextual Stackelberg regret of Algorithm 3 (Definition 4.5) satisfiesE[R(T )] = O K 2/3 A 2/3 f T 2/3 log 1/3 (T ) .Proof Sketch. The key step in our analysis is to show that for any best-response function σ ∈ Σ and follower actiona f ∈ A f , Var( p(1 (σ=a f ) )) ≤ K N (Lemma C.3).Using this fact, we can bound the cumulative total variation distance between p(1 (σ (x t ) =a f ) and p(1 (σ (x t ) =a f )) 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.We now turn our attention to learning under bandit feedback when the sequence of contexts is chosen stochastically and the choice of follower type is adversarial. While we still use barycentric spanners to estimate {{ p(1 (σ (x) =a f ) )} a f ∈A f } x∈E , we can no longer do all of our exploration "up front" like in Appendix C.1 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 τ (1 (σ (x (b) ) =a (b) ) ), i.e. the probability that a follower in block B τ best-responds to mixed strategy x (b) 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 a (b) , we set p τ (1(σ (x (b) ) =a (b) ) ) = 1. Otherwise we set p τ (1 (σ (x (b) ) =a (b) ) ) = 0. Since the time-step in which we play x (b) is chosen uniformly from all time-steps in B τ , p τ (1 (σ (x (b) ) =a (b) ) ) is an unbiased estimate of p τ (1 (σ (x (b) ) =a (b) ) ). While p τ (1 (σ (x (b) ) =a (b) )) no longer has low variance since it must be recomputed separately for every block B τ , it is still bounded. Therefore, we can use our estimates { p τ (1 (σ (x (b) ) =a (b) ) )} b∈B , along with the corresponding linear coefficients from the barycentric spanner, to get a bounded (and unbiased) estimate for every p(1 (σ (x) =a f ) ).τ (1 (σ (x) =a f ) )} a f ∈A f } x∈E ,we proceed via a reduction to Algorithm 2. In particular, in every block B τ we use our estimates {{ p τ (1 (σ (x) =a f ) )} a f ∈A f } x∈E to construct an (unbiased and bounded) estimate of the average utility for all policies in our finite policy class Π during block B τ . 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 (σ (x (b) ) =a (b) ) ) for some b ∈ B), we sample the leader's policy according to the distribution over policies given by Hedge from the previous block. This process is summarized in Algorithm 4.Theorem C.2. If N = O(T 2/3 A 1/3f log 1/3 T ), then Algorithm 4 obtains expected contextual Stackelberg regret (Definition 4.9)E[R(T )] ≤ O KA 1/3 f T 2/3 log 1/3 (T ) .Proof Sketch. The analysis proceeds similarly to the analysis of Theorem 6.1 in Balcan et al. [5] . We highlight the key differences here. The first key difference is that while Balcan et al. [5] play Hedge over a finite set of leader strategies, we play Hedge over a finite set of leader policies, each of which map to one of finitely-many leader strategies for a given context. Second, unlike in Balcan et al. [5] it is not sufficient to only estimate {{p τ (1 (σ (x) =a f ) )} a f ∈A f } x∈E to obtain an unbiased estimate of the utility of each policy in Π in each time block-we must also specify a context (or set of contexts) to use in our estimator. We show that it suffices to select a context uniformly at random from the contexts {z t } t∈Bτ encountered in the block.Lemma C.3. For any σ f ∈ Σ and a f ∈ A f , Var( p(1 (σ=a f ) )) ≤ K N .Algorithm 3: Learning with stochastic follower types: bandit feedback Let B = {b (1) , . . . , b (K) } be the Barycentric spanner of W for i = 1, . . . , K do for τ = 1, . . . , N do Play mixed strategy x (b (i) ) , observe best-response af (i-1)•N +τ end Compute p(b (i) ) = 1 N N τ =1 1{b fτ (x (b (i) ) ) = a (b (i) ) } end Compute p(1 (σ=a f ) ) = K i=1 λ i (1 (σ=a f ) ) • p(b (i) ) for all σ ∈ Σ, a f ∈ A f for t = K • N + 1, . . .Observe context z t , commit to mixed strategyx t = π(z t ) = arg max x∈E a f ∈A f p(1 (σ (x) =a f ) ) • u(z t , x, a f ). end Proof. Var( p(1 (σ=a f ) )) := E[( p(1 (σ=a f ) )) 2 ] -E[ p(1 (σ=a f ) )] 2 = E[( p(1 (σ=a f ) )) 2 ] -p 2 (1 (σ=a f ) ) = E      K j=1 λ j (1 (σ=a f ) ) p(b (j) )   2    -p 2 (1 (σ=a f ) ) = E   K j=1 λ 2 j (1 (σ=a f ) ) p 2 (b (j) ) + K i=1 K j=1,j̸ =i λ i (1 (σ=a f ) )λ j (1 (σ=a f ) ) p(b (i) ) p(b (j) )   -p 2 (1 (σ=a f ) ) = K j=1 λ 2 j (1 (σ=a f ) )E[ p 2 (b (j) )] + K i=1 K j=1,j̸ =i λ i (1 (σ=a f ) )λ j (1 (σ=a f ) )E[ p(b (i) ) p(b (j) )] -p 2 (1 (σ=a f ) )Observe that since (1) the follower in each round is drawn independently from F and (2) the rounds used to compute p(b (i) ) do not overlap with the rounds used to compute p(b (j) ) for j ̸ = i, p(b (i) ) and p(b (j) ) are independent random variables for j ̸ = i. ThereforeVar( p(1 (σ=a f ) )) = K j=1 λ 2 j (1 (σ=a f ) )E[ p 2 (b (j) )] + K i=1 K j=1,j̸ =i λ i (1 (σ=a f ) )λ j (1 (σ=a f ) )p(b (i) )p(b (j) ) -p 2 (1 (σ=a f ) ).We now turn our focus to E[ p 2 (b (j) )]. Observe thatE[ p 2 (b (j) )] = E   1 N N τ =1 1{b fτ (x (b (j) ) = a (b (j) f ))} 2   = 1 N 2 E N τ =1 N τ ′ =1 1{b fτ (x (b (j) ) = a (b (j) ) f )} • 1{b f τ ′ (x (b (j) ) = a (b (j) ) f )} = 1 N 2 (N • p(b (j) ) + N (N -1)p 2 (b (j) ))Plugging this into our expression for Var( p(1 (σ=a f ) )), we see thatVar( p(1 (σ=a f ) )) = 1 N K j=1 λ 2 j (1 (σ=a f ) )(p(b (j) ) + (N -1)p 2 (b (j) )) + K i=1 K j=1,j̸ =i λ i (1 (σ=a f ) )λ j (1 (σ=a f ) )p(b (i) )p(b (j) ) -p 2 (1 (σ=a f ) ) = 1 N K j=1 λ 2 j (1 (σ=a f ) )(p(b (j) ) -p 2 (b (j) )) + K i=1 K j=1 λ i (1 (σ=a f ) )λ j (1 (σ=a f ) )p(b (i) )p(b (j) ) -p 2 (1 (σ=a f ) ) = 1 N K j=1 λ j (1 (σ=a f ) )p(b (j) ) • λ j (1 (σ=a f ) )(1 -p(b (j) )) +   K j=1 λ j (1 (σ=a f ) )p(b (j) )   2 -p 2 (1 (σ=a f ) ) = 1 N K j=1 λ j (1 (σ=a f ) )p(b (j) ) • λ j (1 (σ=a f ) )(1 -p(b (j) )) + p 2 (1 (σ=a f ) ) -p 2 (1 (σ=a f ) ) ≤ K Nwhere the last line follows from the fact that λ j (1(σ=a f ) ) ∈ [-1, 1] and p(b (j) ) ∈ [0, 1].Lemma C.4. For any z ∈ Z,a f ∈A f p(1 (σ ( π(z)) =a f ) ) • u(z, π(z), a f ) ≥ a f ∈A f p(1 (σ (π (E) (z)) =a f ) ) • u(z, π (E) (z), a f ) - a f ∈A f | p(1 (σ ( π(z)) =a f ) ) -p(1 (σ ( π(z)) =a f ) )|.Proof. By the definition of π,a f ∈A f p(1 (σ (π (E) (z)) =a f ) ) • u(z, π (E) (z), a f ) ≤ a f ∈A f p(1 (σ ( π(z)) =a f ) ) • u(z, π(z), a f ) = a f ∈A f p(1 (σ ( π(z)) =a f ) ) • u(z, π(z), a f ) + a f ∈A f ( p(1 (σ ( π(z)) =a f ) ) -p(1 (σ ( π(z)) =a f ) )) • u(z, π(z), a f ) ≤ a f ∈A f p(1 (σ ( π(z)) =a f ) ) • u(z, π(z), a f ) + a f ∈A f | p(1 (σ ( π(z)) =a f ) ) -p(1 (σ ( π(z)) =a f ) )|.the desired result may be obtained by rearranging terms.Lemma C.5. For any sequence of mixed strategies x N K+1 , . . . , x T ,T t=N K+1 a f ∈A f | p(1 (σ (x t ) =a f ) ) -p(1 (σ (x t ) =a f ) )| ≤ 2A f T K log(T ) N with probability at least 1 -1 T .Proof. By Lemma C.3 and a Hoeffding bound, we have that| p(1 (σ=a f ) ) -p(1 (σ=a f ) )| ≤ 2K log(1/δ) Nwith probability at least 1 -δ, for any particular (σ, a f ) pair. Taking a union bound over the randomness in estimating p(b (1) ), . . . , p(b (K) ), we see that| p(1 (σ=a f ) ) -p(1 (σ=a f ) )| ≤ 2K log(K/δ) Nwith probability at least 1 -δ, simultaneously for all (σ, a f ). The desired result follows by summing over T and A f , and setting δ = 1 T .Theorem C.1.If N = O A 2/3 f T 2/3 log 1/3 (T ) K 1/3, then the expected contextual Stackelberg regret of Algorithm 3 (Definition 4.5) satisfiesE[R(T )] = O K 2/3 A 2/3 f T 2/3 log 1/3 (T ) .Proof. E[R(T )] := E f1,...,f T ∼F T t=1 u(z t , π * (z t ), b ft (π * (z t ))) -u(z t , π t (z t ), b ft (π t (z t ))) ≤ 1 + E f1,...,f T ∼F T t=1 u(z t , π (E) (z t ), b ft (π (E) (z t ))) -u(z t , π t (z t ), b ft (π t (z t ))) ≤ 1 + KN + E f KN +1 ,...,f T ∼F T t=KN +1 u(z t , π (E) (z t ), b ft (π (E) (z t ))) -u(z t , π(z t ), b ft ( π(z t ))) = 1 + KN + E f ∼F T t=KN +1 u(z t , π (E) (z t ), b f (π (E) (z t ))) -u(z t , π(z t ), b f ( π(z t ))) = 1 + KN + E f ∼F   T t=KN +1 a f ∈A f u(z t , π (E) (z t ), a f ) • 1{b f (π (E) (z t )) = a f } -u(z t , π(z t ), a f ) • 1{b f ( π(z t )) = a f }] = 1 + KN + T t=N K+1 a f ∈A f u(z t , π (E) (z t ), a f ) • p(1 (σ (π (E) (z t )) =a f ) ) -u(z t , π(z t ), a f ) • p(1 (σ ( π(z t )) =a f ) ) By Lemma C.4, E[R(T )] ≤ 1 + KN + T t=N K+1 a f ∈A f u(z t , π (E) (z t ), a f )(p(1 (σ (π (E) (z t )) =a f ) ) -p(1 (σ (π (E) (z t )) =a f ) )) + T t=N K+1 a f ∈A f | p(1 (σ ( π(z t )) =a f ) ) -p(1 (σ ( π(z t )) =a f ) )| ≤ 1 + KN + T t=N K+1 a f ∈A f | p(1 (σ (π (E) (z t )) =a f ) ) -p(1 (σ (π (E) (z t )) =a f ) )| + T t=N K+1 a f ∈A f | p(1 (σ ( π(z t )) =a f ) ) -p(1 (σ ( π(z t )) =a f ) )| ≤ 3 + KN + 4A f T K log(a f ∈A f u(z τ , π(z τ ), a f ) • p τ (1 (σ (π(zτ )) =a f ) ) and u τ (π) := a f ∈A f u(z τ , π(z τ ), a f ) • K j=1 λ j (1 (σ (π(zτ )) =a f ) ) • p τ (b (j) ), where z τ ∼ Unif{z t : t ∈ B τ }, B = {b (1) , . . . , b (K) } is the Barycentric spanner for W, and p (b) = 1 if b f t(b) (x (b) ) = aE {zτ } t∈Bτ E[ u τ (π)] = E zτ ∼P [u τ (π)] = E zτ ∼P [ a f ∈A f u(z τ , π(z τ ), a f ) • p τ (1 (σ (π(zτ )) =a f ) )],where the second expectation is taken over the randomness in selecting the explore time-steps and in drawing z τ ∼ Unif{z t :t ∈ B τ }. Moreover, u τ (π) ∈ [-KA f , KA f ].Algorithm 4: Learning with stochastic contexts: bandit feedback Consider Π := {π (ω) } ω∈Ω Let q 1 [π (ω) ] := 1, p 1 [π (ω) ] := 1 |Π| for all π (ω) ∈ Π Let B = {b (1) , . . . , b (K) } be the Barycentric spanner of W for τ = 1, . . . , Z do Choose random perturbation over B and explore time-steps in B τ uniformly at random Choose a time-step in B τ uniformly at random whose context will be used as z τ for t ∈ B τ do If t is an explore time-step, play the corresponding mixed strategy x (bt) in B. If a ft = a (bt) , set p τ (b t ) = 1. Otherwise, set p τ (b t ) = 0. Otherwise (t is an exploit round), sample π t ∼ p t , a l,t ∼ π t (z t ). end For each policy π(ω) ∈ Π, compute ℓ τ [π (ω) ] := -a f ∈A f K i=1 λ i (1 (σ (π(zτ )) =a f ) ) • p(b (i) ) • u(z τ , π (ω) (z τ ), a f ). Set q τ +1 [π (ω) ] = exp -η τ s=1 ℓ s [π (ω) ] and p t+1 [π (ω) ] = q t+1 [π (ω) ]/ π (ω ′ ) ∈Π q t+1 [π (ω ′ ) ]. end Proof. E {zt} t∈Bτ E[ u τ (π)] = E {zt} t∈Bτ E   a f ∈A f u(z τ , π(z τ ), a f ) • K j=1 λ j (1 (σ (π(zτ )) =a f ) ) • p τ (b (j) )   = E {zt} t∈Bτ E zτ ∼Unif{zt:t∈Bτ }   a f ∈A f u(z τ , π(z τ ), a f ) • K j=1 λ j (1 (σ (π(zτ )) =a f ) ) • E[ p τ (b (j) )]   = E {zt} t∈Bτ E zτ ∼Unif{zt:t∈Bτ }   a f ∈A f u(z τ , π(z τ ), a f ) • K j=1 λ j (1 (σ (π(zτ )) =a f ) ) • p τ (b (j) )   = E {zt} t∈Bτ E zτ ∼Unif{zt:t∈Bτ }   a f ∈A f u(z τ , π(z τ ), a f ) • p τ (1 (σ (π(zτ )) =a f ) )   = E zτ ∼P   a f ∈A f u(z τ , π(z τ ), a f ) • p τ (1 (σ (π(zτ )) =a f ) )   = E zτ ∼P [u τ (π)]The following lemma is analogous to Equation (1) in Balcan et al. [5] .Lemma C.8.E z1,...,z N ∼P N τ =1 u τ (π (E) ) -Eu τ (π τ ) ≤ N κ log |Π|where R N,κ is an upper-bound on the regret of (full-information) Hedge which takes as input a sequence of N losses/utilities which are bounded in [-κ, κ] and are parameterized by z 1 , . . . , z N .Proof.E z1,...,z N ∼P N τ =1 π∈Π p τ [π] • u τ (π) = E z1,...,z N ∼P N τ =1 π∈Π p τ [π] • E[ u τ (π)] = E z1,...,z N ∼P E N τ =1 π∈Π p τ [π] • u τ (π) ≥ E z1,...,z N ∼P E max π∈Π N τ =1 u τ (π) -R N,κ ≥ E z1,...,z N ∼P max π∈Π E N τ =1 u τ (π) -R N,κ = E z1,...,z N ∼P max π∈Π N τ =1 u τ (π) -R N,κ ,where the first line uses Lemma C.7 and the fact that z 1 , . . . , z T ∼ P are i.i.d., and R N,κ is the regret of Hedge after N time-steps when losses are bounded in [-κ, κ]. Rearranging terms and using the fact that the expected regret of Hedge after N time-steps is at most N κ log |Π| gets us the desired result. E[R(T )] ≤ O KA 1/3 f T 2/3 log 1/3 (T ) . Proof. E[R(T )] := EE z1,...,z T ∼P T t=1 u(z t , π * (z t ), b ft (π * (z t ))) -u(z t , π t (z t ), b ft (π t (z t ))) ≤ 1 + EE z1,...,z T ∼P T t=1 u(z t , π (E) (z t ), b ft (π (E) (z t ))) -u(z t , π t (z t ), b ft (π t (z t ))) = 1 + EE z1,...,z T ∼P N τ =1 t∈Bτ u(z t , π (E) (z t ), b ft (π (E) (z t ))) -u(z t , π t (z t ), b ft (π t (z t ))) ≤ 1 + KN + EE z1,...,z T ∼P N τ =1 t∈Bτ u(z t , π (E) (z t ), b ft (π (E) (z t ))) -u(z t , π τ (z t ), b ft (π τ (z t ))) = 1 + KN + EE z1,...,z T ∼P   N τ =1 t∈Bτ a f ∈A f u(z t , π (E) (z t ), a f ) • 1{b ft (π (E) (z t )) = a f } -u(z t , π τ (z t ), a f ) • 1{b ft (π τ (z t )) = a f }] = 1 + KN + E N τ =1 E z1,...,z (τ -1)•|B τ -1 | E zt:t∈Bτ |z1,...,z (τ -1)•|B τ -1 |   t∈Bτ a f ∈A f u(z t , π (E) (z t ), a f ) • 1{b ft (π (E) (z t )) = a f } -u(z t , π τ (z t ), a f ) • 1{b ft (π τ (z t )) = a f } = 1 + KN + E N τ =1 E z1,...,z (τ -1)•|B τ -1 | ∼P E zτ ∼P|z1,...,z (τ -1)•|B τ -1 |   t∈Bτ a f ∈A f u(z τ , π (E) (z τ ), a f ) • 1{b ft (π (E) (z τ )) = a f } -u(z τ , π τ (z τ ), a f ) • 1{b ft (π τ (z τ )) = a f } = 1 + KN + E N τ =1 E z1,...,z (τ -1)•|B τ -1 | ∼P E zτ ∼P|z1,...,z (τ -1)•|B τ -1 |   a f ∈A f u(z τ , π (E) (z τ ), a f ) • t∈Bτ 1{b ft (π (E) (z τ )) = a f } -u(z τ , π τ (z τ ), a f ) • t∈Bτ 1{b ft (π τ (z τ )) = a f }where the second line follows from Lemma 4.4, the third from splitting the time horizon into blocks, the fourth from loss due to exploration, the fifth due to 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 t for all t ∈ B τ and (2) z 1 , . . . , z T are independent.E[R(T )] ≤ 1 + KN + BE N τ =1 E z1,...,z (τ -1)•|B τ -1 | ∼P E zτ ∼P|z1,...,z (τ -1)•|B τ -1 |   a f ∈A f u(z τ , π (E) (z τ ), a f ) • 1 |B τ | t∈Bτ 1{b ft (π (E) (z τ ) = a f }) -u(z τ , π τ (z τ ), a f ) • 1 |B τ | t∈Bτ 1{b ft (π τ (z τ )) = a f } = 1 + KN + BE N τ =1 E z1,...,z (τ -1)•|B τ -1 | ∼P E zτ ∼P|z1,...,z (τ -1)•|B τ -1 |   a f ∈A f u(z τ , π (E) (z τ ), a f ) • p τ (1 (σ (π (E) ) =a f ) ) -u(z τ , π τ (z τ ), a f ) • p τ (1 (σ (πτ (zτ )) =a f ) ) ≤ 1 + KN + BE N τ =1 E z1,...,z (τ -1)•|B τ -1 | ∼P E zτ ∼P|z1,...,z (τ -1)•|B τ -1 | [u τ (π (E) ) -u τ (π τ )] = 1 + KN + B • E z1,...,z N ∼P N τ =1 u τ (π (E) ) -Eu τ (π τ ) ≤ 1 + KN + B • N KA f log |Π| ≤ 1 + KN + T K • A f log(T ) Nwhere the first line comes from multiplying and dividing by |B τ |, the second line comes from the definition of p τ , the third from the definition of u τ , the fourth follows from linearity of expectation and the fact that z 1 , . • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean.• 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 a 96% CI, if the hypothesis of Normality of errors 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 of range (e.g. negative error 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.Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).See[27, 19,2] for an overview of other application domains for Stackelberg security games. 38th Conference on Neural Information Processing Systems (NeurIPS 2024).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 non-contextual setting, although more care must be taken to handle the side information present in our setting.E.g. in airport security, zt may contain information about arrival and departure times, number of passengers, valuable cargo, etc. In cyber-defense, zt may be a list of network traffic statistics.It is without loss of generality to assume that the follower's best-response is a pure strategy.Interestingly, there is no discretization error if the sequence of follower types is chosen by a non-adaptive adversary. To see this, one can repeat the proof of Lemma 4.10, using the fact that f1, . . . , fT is independent from the realized draws z1, . . . , zT when the sequence of follower types is chosen by a non-adaptive adversary.Indeed, our notion of contextual Stackelberg regret is stronger than their non-contextual version of regret.We hypothesize that our results in this section could be extended to hold against an adaptive adversary by using more clever exploration strategies.See Section 6.3 of Balcan et al.[5] for details on how to compute this barycentric spanner.For more details, see Proposition 2.2 in Awerbuch and Kleinberg[4].In other words, we ignore the context in the "explore" rounds. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: This paper lacks experimental results to verify the theoretical analysis.
questions: questions: I do not have any questions for the authors.
limitations: limitations: The limitations have been addressed properly.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The paper could improve by providing numerical experiments or case studies that demonstrate the efficacy of the proposed algorithms.
- 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.
questions: questions: - The paper would definitely benefit from the addition of numerical experiments or case studies.
- 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?
- 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?
- 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?
- 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?
- 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: (-) 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. 

(-) 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.
questions: 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: limitations: The authors didn't seem to have addressed this explicitly, but the work is theoretical anyway, so this is minor.
paper_summary: paper_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.

The authors present several positive and negative results:

1. When the context and the type of players are adversarially selected, there is no $o(T)$-regret algorithm.

2. 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.

3. 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.

4. Finally, the authors extend their results to the bandit case by providing O(T2/3)O(T^{2/3})O(T2/3)-regret algorithms.
strength_weakness: strength_weakness: The regret bounds for the bandit case are not tight. However I believe the paper provides interesting first results for an interesting problem.
questions: questions: What are the main challenges of extending your results in infinite action games with convex structure?
limitations: limitations: Yes

Comments: title: Thank you for your response
Reviewer's Response
comment: Thank you for your response and the numerical simulation. I will keep my score.
I really appreciate your detailed response to my questions and additional experiments. After reading the authors' responses and other reviewers' comments, I will keep my score.
I have read the authors' response and I plan to keep my score.