Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
Authors: Yu Bai
Chi Jin
Huan Wang
Caiming Xiong
Venue: NeurIPS 2021 Poster (2021)
Keywords: Stackelberg equilibria
general-sum games
reinforcement learning theory
multi-agent RL

Abstract: Real world applications such as economics and policy making often involve solving multi-agent games with two unique features: (1) The agents are inherently *asymmetric* and partitioned into leaders and followers; (2) The agents have different reward functions, thus the game is *general-sum*. The majority of existing results in this field focuses on either symmetric solution concepts (e.g. Nash equilibrium) or zero-sum games. It remains open how to learn the *Stackelberg equilibrium*---an asymmetric analog of the Nash equilibrium---in general-sum games efficiently from noisy samples.
  This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium, in the bandit feedback setting where we only observe noisy samples of the reward. We consider three representative two-player general-sum games: bandit games, bandit-reinforcement learning (bandit-RL) games, and linear bandit games. In all these games, we identify a fundamental gap between the exact value of the Stackelberg equilibrium and its estimated version using finitely many noisy samples, which can not be closed information-theoretically regardless of the algorithm. We then establish sharp positive results on sample-efficient learning of Stackelberg equilibrium with value optimal up to the gap identified above, with matching lower bounds in the dependency on the gap, error tolerance, and the size of the action spaces. Overall, our results unveil unique challenges in learning Stackelberg equilibria under noisy bandit feedback, which we hope could shed light on future research on this topic.

Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games
Yu Bai
Chi Jin
Salesforce Research yu. bai@salesforce. com
Princeton University chi 2hi.@princeton. edu
Huan Wang
Caiming Xiong
Salesforce Research huan. www..aaa@@alleeoree.ccomm
Salesforce Research cxi cxion@@aalesforce com
Abstract
Real world applications such as economics and policy making often involve solv- ing multi-agent games with two unique features: (1) The agents inherently asymmetric and partitioned into leaders and followers; (2) The agents have dif- ferent reward functions, thus the game general sum. The majority of existing results in this field focuses on either symmetric solution concepts (c.g. Nash equilibrium) or zero-sum games. It remains open how learn the Stackelberg equilibrium--n an asymmetric analog of the Nash equilibrium- general-sum games efficiently from noisy samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium, in the bandit feedback setting where we only observe noisy samples the reward. We consider three representative two-player general-sum games: bandit games, bandit-eeinforcement learning (bandit-RL) games, and linear bandit games. identify fundamental gap between the exact value of the Stackelberg equilibrium and its estimated version using finitely many noisy samples, which can not be closed information eiformation-thhooreiialll theoretically regardless of the algorithm. We then establish sharp positive results on sample-efficient learning value optimal up to the gap identified above, with matching lower bounds in the dependency on the gap, error tolerance, and the size of the action spaces. Overall, results unveil unique challenges in learning Stackelberg equilibria under noisy bandit feedback, which we hope could shed light on future research on this topic.
all these games, we
Stackelberg equilibrium with
Introduction
Real-world problems such economic design and policy making often be modeled multi- agent games that involves two levels of thinking: The policy maker-as a player in this game- needs to reason about the other player's optimal behaviors given her decision, in order to inform her own optimal decision making. Consider for example the optimal taxation problem in the AI Economist [53], game modeling real-world social-economic system involving a leader (e.g. the government) and group of interacting followers (e.g. citizens). The leader sets a tax rate which determines economics-like game for the followers; the followers then play in this game with the objective to maximize their own reward (such as individual productivity). However, the goal of the leader maximize her own reward (such overall equality) which in general different from the followers' rewards, making these games general-sum [38]. Such two-level thinking appears broadly in other applications well such as in automated mechanism design [11, 12], optimal auctions [10, 14], security games [43], reward shaping [25], and so on.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Another key feature in such games is that the players are asymmetric, and they act in turns: the leader first plays, then the follower sees the leader's 's action and then adapts to it. This makes symmetric solution concepts such as Nash equilibrium [30] not always appropriate. A more natural solution concept for these games the Stackelberg equilibrium: the leader's optimal strategy, assuming the followers play their best response to the leader [42, 13]. The Stackelberg equlibrium is often the desired solution concept in many of the aforementioned applications. Furthermore, it is of compelling interest to understand the learning of Stackelberg equilibria from samples, as it is often the case that we can only learn about the game through interactively deploying policies and observing the (noisy) feedback from the game [53]. This may be the case even when the game rules are perfectly known but not yet represented in a desired form, as argued in the line of work on empirical game theory [50, 48, 20].
Despite the motivations, theoretical studies of learning Stackelberg equilibria general-sum games remain open, in particular when we can only learn from noisy samples of the rewards. A line of work provides guarantees for finding Stackelherg equilibria in general-sum games, but restricts attention to either the full observation setting (so that the exact game is observable) or with exact best-response oracle [13, 27, 47, 34]. These results lay out a foundation for analyzing the Stackelberg equilibrium, but do not generalize to the bandit feedback setting in which the game can only be learned from random samples of the rewards. Another line of work considers the sample complexity of learning the Nash equilibrium in Markov games [35, 4, 5, 28, 51, 52], which also do not imply algorithms for finding the Stackelberg equilibrium in these games as the Nash is in general different from the Stackelberg equilibrium in general-sum games.
In this work, we study the sample complexity of learning Stackellerg equilibrium in general-sum games. We focus on general-sum games with two players (one leader and one follower), in which we wish to learn an approximate Stackelberg equilbrium for the leader from random samples. Our contributions can be summarized as follows.
As a warm-up, we consider bandit games in which the two players play an action in turns and observe their own rewards. We identify fundamental gap between the exact Stackelberg value and its estimated version from finite samples, which cannot be closed information theoreeil regardless of the algorithm (Section 3.1). We then propose rigorous definition gap; for this gap, and show that it is possible to sample-efficiently learn the (gap, + -)aaprooximate Stackelberg equilibrium with (ABBE²) samples, where A, B are the number of actions for the two players. We further show matching lower bound 52 ((AA//e)) (Section 3.2). We also establish similar results for learning Stackelberg in simultaneous matrix games (Appendix B).
We consider bandit-RL. games in which the leader's 's action determines an episodic Markov Decision Process (MDP) for the follower. We show that (gap; + E) approximate Stackelberg equilibrium for the leader can be found in 52 AB episodes of play, where H, are the horizon length and number of states for the follower's 's MDP, and A, B are the number of actions for the two players (Section 4). Our algorithm utilizes recently developed reward-free free reinforcement learning techniques to enable fast exploration for the follower within the MDPs.
Finally, we consider linear bandit games in which the action spaces for the two players can be arbitrarily large, but the reward is a linear function of a d-dimensional feature representation of the actions. We design an algorithm that achieves O(e)/e²) sample complexity upper bound for linear bandit games (Section 5). This only depends polynomially on the feature dimension instead of the size of the action spaces, and has at most an Ö(d) gap from the lower bound.
1.1 Related work
Since the seminal paper of [46], notions of equilibria in games and their algorithmic computation have received wide attention [see, e.g., 9, 41]. For the scope of this paper, this section focuses on reviewing results that related to learning Stackelberg equilibria.
Learning Stackelberg equilibria in zero-sum games The first category of results study two- player zero-sum games, where the rewards of the two players sum to zero. Most results along this line focus on the bilinear or convex-concave setting [see, e.g., 21, 32, 31, 37, 16), where the Stackelberg equilibrium coincide with the Nash equilibrium due to Von Neumann's 's minimax theorem [46]. Results for learning Stackelberg equilibria beyond convex-concave setting are much more recent,

---

with Rafique et al. Nouiched et al. [33] considering the nonconvex eenccee setting, and Fiez et al. [15], Jin et al. [19]. Marchesi et al. [29] considering the nonconvex-noncooeet setting. Marchesi et al. [29] provide sample complexity results for learning Stackelberg with infinite strategy spaces, using discretization techniques that may scale exponentially the dimension without further assumptions on the problem structure.
We remark that a crucial property of zero-sum games is that any two strategies giving similar rewards for the follower will also give similar rewards for the leader. This is no longer true in general-sum games, and prevents most statistical results for learning Stackelberg equilibria in the zero-sum setting from generalizing to the general-sun sum setting.
Learning Stackelberg equilibria in general-sum games The computational complexity of finding Stackelberg equilibria in games with simultancous play ("computing optimal strategy to commit to") studied in [13, 26, 47, 22, 7J. These results assume full observation of the payoff' function, and show that several versions of matrix games and extensive-form (multi-step) games admit polynomial time algorithms. Vasal [45] designs computationally efficient algorithms for computing Stackelberg in certain "conditionally independent controlled" Markov games.
Another line of work considers learning Stackelberg with "best response oracle" [27, 34], that returns the follower's exact best response strategy when a leader's strategy is queried. This oracle and the noisy reward oracle assume are in general incomparable (cannot simulate each other regardless of the number of queries), and thus our sample complexity results do not imply each other. The recent work of Sessa al. [39] proposes the StackeIUCB algorithm to sample-efficiently learn Stackelberg game where the opponent's 's response function has a linear structure in a certain kernel space, and the observation noise is added in the action space instead of the reward (thus a different noisy feedback model from ours).
Lastly, Fiez al. [15] study the local convergence of first-order algorithms for finding Stackelberg equilibria in general-sum games. Their result also assumes exact feedback and do not allow sampling enrors. The AI Economist [53] studies the optimal taxation problem by learning the Stackelberg equilibrium via a two-level reinforcement learning approach.
Learning equilibria in Markov games A recent line of results [4, 5, 51, 52] consider learning Markov games [40]-a generalization of Markov decision process to the multi-agent setting. We remark that all three settings studied in this paper can be cast special cases of general-sum Markov games, which is studied by [28]. In particular, Liu et al. [28] provides sample complexity guarantees for finding Nash equilibria, correlated equilibria, coarse correlated equilibria of the general-sum Markov games. These Nash-finding algorithms are related to our setting, but do not imply results for learning Stackelberg (see Section 3.2 and Appendix C.5 for detailed discussions).
2 Preliminaries
Bandit games A general-sum two-player bandit game can be described by tuple M (A, B, ri, r2), which defines the following game played by two players, a leader and a follower:
The leader plays an action a E A, with |A| A.
The follower sees the action played by the leader, and plays an action b e B, with |B| = B.
The follower observes (potentially random) reward (2 b) E [0, 1]. The leader also observes her own reward r1 (a, b) E 1].
Note that this is a special case of general-sum turn-based Markov game with two steps [40, 4]. This game is also based variant of the simultaneous matrix game considered in [13, 27] (for which we also provide results in Appendix B).
Best response, Stackelberg equilibrium Let (1 b) = E[rr(a, 6)] (i = 1,2) denote the mean rewards. For each leader action a, the best response set (Ro(a) is the set of follower actions that maximize (2(a,)):
(a) = 6: u2(a,)) max (2((,
(I)
beB
3

---

Given the best-response set BRo(a), we define the function Φu - [0. as the leader's 's value function when the follower plays the worst-case best response (henceforth the"exact ø-function"),
(o(a) == min Jon (u(a,)) b);
(2)
(EBRa(a)
This is the value function for the leader action assuming the follower plays the best response to and breaks ties in the best response set against the leader's favor. This known as pessimistic tie breaking and provides worst-case guarantee for the leader [13]. We remark that here restricting b to pure strategies (deterministic actions) is without loss of generality, as there is at least one pure strategy that maximizes (2( .) and (among the maximizers) minimize in (a, among all mixed strategies.
The Stackelberg Equilibrium (henceforth also "Stackelberg") for the leader is the "best response to the best response", i.e. any action a, that maximizes Φ [42]:
a2 E arg max (a).
aEA
We are interested in finding approximate solutions to the Stackelberg equilibrium, that is, an action ā that approximately maximizes do (a). Note that as the leader's action is seen by the follower, it suffices to only consider pure strategies for the leader too (this is equivalent to the "optimal committment to pure strategies" problem of [13]). We also remark that, while we consider pessimistic tie breaking (definition (2)) in this paper, similar results hold in the optimistic setting as well in which the follower breaks ties in favor of the leader. We defer the statements and proofs of these results to Appendix A.
Real-world example (AI Economist): Consider the following (simplified) optimal taxation problem in the AI Economist [53] as an example of a bandit game. The government (leader) determines the tax rate A for the follower. The citizen (follower) then chooses the amount of labor b E B she wishes to perform. The rewards for the two players are different in general: For example, the citizen's 's reward (a b) can be her post-tax income per labor, and the govermment' is reward rn (a, b) can be a weighted average of its tax income and some measure of the citizen's 's welfare (e.g. not too much labor). We remark that the actual AI Economist is more similar to bandit-RL game where the follower plays sequentially in an MDP determined by the leader, which we study in Section 4.
Sample-efficient learning with bandit feedback In this paper we consider the handit feedback setting, that is, the algorithm cannot directly observe the mean rewards (41 (---) and μzz(;, +), and can only query (a, b) and obtain random samples (ri (a, b), r2 b)). Our goal is to determine the number of samples in order to find an approximate maximizer of ())
Note that the bandit feedback setting assumes observation noise in the rewards. As we will see in Section 3, this noise turns out to bring in a fundamental challenge for learning Stackelberg equilibria that is not present in (and thus not directly solved by) existing work on learning Stackelberg, which assumes either exact observation of the mean rewards [13, 26), or the best-response oracle that can query and obtain the exact best response set (a)
(a) [27, 34].
Markoy decision processes We also present the basics of a Markov Decision Processes (MDPs), which will be useful for the bandit-RL games in Section 4. We consider episodic MDPs de- fined by a tuple (H.S. S, B,
the action space', PP- S, d S.,,,,Prr) r), where H is the horizon length, S is the state space, B is (Px h [H). S. E B} is the transition probabilities, and r = (rk : S x B - [0, 11, E [M]] are the (potentially random) reward functions. A policy т = (-1s) E As: h E [H] s E S} for the player is a set of probability distributions over actions given the state.
In this paper we consider the exploration setting as the protocol of interacting with MDPs, similar as in [3, 17]. The learning agent is able to play episodes repeatedly, where in each episode at step E {1..... H}. the agent observes state sh. E S, takes an action by ~ TA (-(s)). observes her reward Fy (Sp. by) E [0, 1], and transits to the next state Sp+1 ~ PA, (-Isn, b,.. The initial state
received from the MDP: 81 ~ (-). The overall value function (return) of policy π is defined as
((=) == E, E, Σ hh Ph (5n, bn)
'The notation & indicates that the MDP is played by the follower (cf. Section 4): we reserve A as the leader's action space this paper.

---

Warm-up: bandit games
3.1 Hardness of maximizing @o from samples
Given the exact o-function Φp (2), natural notion of approximate Stackelberg equilibrium is to find an action à that is s near-optimal for maximizing do:
do max @o(a) -.
(4)
aEAA
However, the following lower bound shows that, in the worst case, it is hard find such ā from finite samples.
Theorem (22(1) lower bound for maximizing Φo). For any sample size n and any algorithm for maximizing do that ouiputs an action A. there exists bandit game with A B 2 which the algorithm must suffer from 12(1) error with probability at least 1/3:
s (ā) S max 60 1/2.
aEA
Theorem shows that, matter how large the sample size is, any algorithm in the worst-case have to suffer from an (2(1) lower bound for maximizing do (i.c. determining the Stackelberg equilibrium for the leader). This result stems from hardness of determining the best response (R) exactly from samples. (See Table 2 for the construction of the hard instance and Appendix C.1 for the full proof of Theorem 1.) This is in stark contrast the standard 1/v/ type learning result in finding other solution concepts such as the Nash equilibrium [4, 28), and suggests a new fundamental challenge to learning Stackelberg equilibrium from samples.
3.2 Learning Stackelberg with value optimal up gap
The lower bound in Theorem I shows that approximately maximizing du is cetematioon-hhoretiieee hard. Motivated by this, we consider in turn a slightly relaxed notion of optimality, in which consider maximizing de only up to the gap between Φv and its counterpart using e-approximate best responses. More concretely, define the e-approximate versions of the best response set and Ø-function as
(a == min (1(a,,) b), (aBR,
BR, (a) == b bE : 2 max u2(a, =
These definitions similar to the vanilla BR, and in (1) and (2), except that we allow any E-approximate best response be considered as valid response to the leader action. Observe we always have (a) 2 (R) and (a) S (o(a). We then define the gap of
m00.. di (c)
gaPa
the game for any E (0, 1) as
gap: := max (a) max &e (a) 2 0. a
(5)
aε-À
This gap. is discontinuous in E in general, and can be as large as ((1) for any ε > 0 without additional assumptions on the relation between #1 and uzz See Figure for an illustration for a typical max.e.4 &e (a) against
0
6n
Figure 1: Illustration of max A de (a) and gap, as function of s. The quantity gap can be I(1) for arbitrarily small Eg.
With the definition of the gap. we are now ready to state main result, which shows that it is possible to sample-efficiently learn Stackelherg Equilibria with value up to (gap, + +). The proof can be found in Appendix C.3.
"This gap, could be small when and have certain relations, such as zero-sum cooperative structure. See Appendix C.6 for more discussions.
5

---

Algorithm/ Learning Stackelberg in bandit games
Require: Target accuracy E 0.
set N + Cloo(AA//)/e for some constant C > O.
1: Query each (a, A x B for N times and obtain {rl ( (a, (a, 6), r/ b))
2: Construct empirical estimates of the means fi(a, b) #/2 2==1 T, ( (a, for 1,2.
3: Construct approximate best response sets and values for all A:
(3)) == min (i b), where BR35/a(a) = b: (22 b) 2 max u2( - 33/4
(e(
WEB
4: Output (7, b). where ā = arg max (a), b = arg min be bR (a) ihi ( b).
Theorem 2 (Learning Stackelberg in bandit games). For any bandit game and E E (0, 1), Algorithm I
oufputs (a.b) such that with probability at least
6,
Φo (ā) 2 (²) 2 max (a) gap: E:
aed
(a max WEB
(2
with = (AABe²) samples, where (c) hides log factors. Further, the algorithm runs in O(n) O(AB/²²) time.
Implications; Overview of algorithm Theorem 2 shows that it is possible to learn @ that maxi- mizes (a(a) up to (gap, + =) accuracy, using Ō(AB/e* samples. The quantity gap; is not bounded and can be as large as (11 for any E (see Lemma C. for a formal statement); however the gap is non-increasing as we decrease In the situation where for every a the best follower action for N2( :) is at least bo-better than the second best action, then for E < Eg we have gap; = 0 and Theorem implies c-optimal Stackelberg guarantee. In general, Theorem 2 presents "best-effort" positive result for learning Stackelberg under this relaxed notion of optimality. To the best of our knowledge, this is the first result for sample-efficient learning of Stackelberg equilibrium in general-sum games with noisy bandit feedbacks. We remark that Theorem 2 also provides a near-optimality guarantee for &e (ā) which is slightly stronger than Φn (since /2/2( (a) S (o))) and guarantees the learned is indeed an e-approximate best response a.
From a more practical point of view, Theorem 2 (and our later results on bandit-RL games and linear bandit games) spells out concretely the sample size required to learn an s-approximate Stackelberg, in terms of the scaling with problem parameters. For instance, in the Al Economist example, A is the number of tax rate choices for the government, and the number of actions for the citizen, and our results show that there exist an algorithm with sample complexity polynomial in A. B, and 1/e.
The main step in Algorithm I is to construct approximate best response sets (Rae/a(a) for all a E A based on the empirical estimates of the rewards. Through concentration, we argue that BRae/a (4) is good approximation of the true best response sets in the sense that (R) S (BRae/a(a) C BRR (a) holds for all A. from which the Stackelberg guarantee follows.
Irreducibility to Nash-finding algorithms We also remark that our bandit game is equivalent to a turn-based general-sum Markov game with two steps, A states, and (A, B) actions [4]. Further, the Stackelberg equilibrium a, along with a follower policy that plays the best response (with pessimistic tie- beebrekk constitutes Nash equilibrium for that Markov game (see Appendix C.5 for a formal statement and proof). However, existing Nash-finding algorithms for general-sumt Markov games such as is because general-sum games have multiple Nash equilibria (with different values) in general [38], and these existing Nash-finding algorithms cannot pre- pre-specify which Nash to output.
[28] do not imply an algorithm for finding the Stackelberg equilibrium. This
Lower bound We accompany Theorem by an M(AB/e²) sample complexity lower bound, showing that Theorem 2 achieves the optimal sample complexity up to logarithmic factors.

---

Theorem (Lower bound for bandit games). There exists an absolute constant с > such that the following holds. For any (0,c), 9 E [0, c). any A, 3. and any algorithm that queries N I c [[AB/=²] samples and outputs an estimate ā A, there exists a bandit game M on which gap; g and the algorithm suffers from (g + E) enror:
/ - Φ I max do (a) aEA
with probability at least 1/3.
This lower bound shows the tightness of Theorem 2, and suggests that (gap- + +e) suboptimality is perhaps a sensible learning goal, as for any algorithm and any value of g 2 there exists a game with gap; 9. which the algorithm has to suffer from (o + E) error, if the number of samples is at most (AB/E²) The proof of Theorem is deferred to Appendix C.4.
Bandit-RL games
In this section, we investigate learning Stackelberg equilibrium in bandit-RL games, which each leader's action determines an episodic Markov Decision Process (MDP) for the follower. This setting extends the two-player bandit games by allowing the follower play sequentially, and has strong practical motivations in particular in policy making problems involving sequential plays for the follower, such as the optimal taxation problem in the Al Economist [53].
Setting A bandit-Ro RL game is described by the leader's action set A (with |A| A), and family MDPs M {M* E A). Each leader action a E A determines an episodic MDP M = S, B, Ipa (1, :), r, -))) that contains H steps, S states, B actions, with two reward functions r1 and r2. In each episode of play,
The leader plays action A.
The follower sees this action and enters the MDP M She observes the deterministic' initial state 81, and plays in M with exploration feedback for one episode.
While the follower plays in the MDP, she observes reward 12,a(a, sh, bu), whereas the leader also observes her own reward 11,A (a, Sh, b).).
We let " denote policy for the follower, and let (i T²) and (2 x²) denote its value functions (in M) for the leader and the follower respectively.
Similar as in bandit games, we define the e-approximate best-response set (R.(a) and the s- approximate é-function (a) for all as
(a)
min (a,,7") where BRa(a) n" V2(a, 2 max V22 (2 xhEBR, (a)
7
Define gap; = m (a) max (a) similarly as (5). We are interested in the number of episodes in order to find (gap: + near-optimal Stackelberg equilibrium.
4.1 Algorithm description
At a high level, our algorithm for bandit-RL games is similar for bandit games query each leader action a E AA sufficiently many times, let the follower learn the best response (i.e. best policy for the MDP Md for each a E A. and then choose the leader action that maximizes the best response value function. This requires solving
arg max (3)/4(a) arg max aEA
min T'E
7((a,7))
(6)
BR (R)
V2(a, 7
2 max V2(a, 32/
'The general case where is stochastic reduces to the deterministic case by adding step h = with single deterministic initial state so, which only increases the horizon of the game by 1.
7

---

Algorithm 2 Learning Stackelberg in bandit-RL games
Require: Target accuracy 0.
1: for a E A do
2: Let the leader pull arm E A and the follower run the Reward-Free RL-Explore algorithm
for N + O B/e) episodes, and obtain model estimate M
3: Let (a,,,,, (2(aa)) denote the value functions for the model M
4: Compute the empirical best response value (a) == max,* V2 7²) by any optimal plan- ning algorithm (e.g. value iteration) on the empirical MDP M
5: Solve the following program
minimize, (i s.t. T² BR = { 12 T²) 2 (2) 3c/4]
(7)
by subroutine (ah(aa,, /35//4 (a)) t VorstCaasBBestReppose M V22 (a) -3c44)
output (a, where t arg max,eA (3)/4(0) and n fb.(a)
where V1 and 1/2 are empirical estimates of the true value functions.
Two technical challenges emerge as we instantiate (6). First, the follower not only needs to find her own best policy during the exploration phase, but also has to accurately estimate both her and the leader's reward over the entire approximate best response set BR3e/4 so as make sure the estimates Vi(a, x²) (i 1, 2) reliable. Standard fast PAC-exploration algorithms such as those in [3, 17] do not provide such guarantees. We resolve this by applying the reward-free learning algorithm of Jin al. [18] for the follower explore the environment efficiently while providing value concentration guarantees for multiple rewards and policies. We remark that we slightly generalize the guarantees of [18] to the situation where the rewards are random and have to be estimated from samples.
Second, the problem min = (BRaaaaaa (a 7²) in (6) requires minimizing value function over the near-optimal policy set of another value function. We build on the linear programming reformulation in the constrained MDP literature [2] to translate (6) into a linear program
which adopts efficient solution in poly(HS time [8]. (the description of this subroutine can be found in Algorithm 8 in Appendix D.1). Our full algorithm is described in Algorithm 2.
4.2
Main result
We now state our theoretical guarantee for Algorithm 2. The proof can be found Appendix D.2. Theorem 4 (Learning Stackelberg in bandit-RL games). For any bandit-RU RL game and sufficiently 52 + 5* episodes of play can return (a, 7*) such that with probability at least 1-16- 8,
small < S22 Algorithm 2 with
(a(a) 2 (a) 2 max do(a) gap; -
aEA
1/2 (a, N max V2(a,
where Ö(-) hides log( (5)) factors. Further, the algorithm runs poly(HS time.
Sample complexity, relationship with reward-free RL Theorem 4 shows that for bandit-RL games, the approximate Stackelberg Equilibrium (with value optimal up to gap. +E) can be efficiently found with polynomial sample complexity and runtime. In particular, (for small e) the leading term Since bandit-RL games include bandit games
in the sample complexity scales as a special case, the ((AB/e²) lower bound for bandit games (Theorem 3) apply here and implies that the A, B dependence in Theorem 4 is tight, while the H dependence may be slightly suboptimal.
We also remark the learning goal for the follower in our bandit-RL game a new RL setting in between the single-reward setting and the full eward-free setting, for which the optimal S dependence is currently unclear. In the single-reward setting, existing fast exploration algorithms such as UCBVI [3] only require linear in S episodes for finding near-optimal policy. In contrast, in the full reward-free
8

---

Algorithm 3 Learning Stackelberg in linear bandit games
Require: Target accuracy 0.
1: Find (K. p) <- CoreSet ( (ef. (10)). Let = ((aa,bb):153 K) where K = -K]--
2: Query each (aj, b2) for
Odd (2/g///////))))))))))))))))))))/ times. Let (fn.,) denote the empirical
mean of the observed rewards over the N queries.
3:
Estimate (2) via weighted least squares
0: arg min
Σ (d(la,;) -mmas) i 1,2.
(9)
DER
4: Construct approximate best response sets and values for all A:
BRse/((a) = b: ((a b) TO 2 max ol, 6) b0T - 35/4
WEB
Φ3</1(a)== min /E
((a 1-
5:
Output (a, b), where ā = arg max (s//s((), arg minl be 6(0, b)T
setting (follower wants accurate estimation of any reward), is known (2S22) is unavoidable [18]. Our setting poses a unique challenge in between: The follower wishes to accurately estimate both 71,72 on all near-optimal policies for 72. This further renders recent linear in S algorithms for reward-free learning with finitely many rewards [28] not applicable here, as they only guarantee accurate estimation of each reward on near-optimal policies for that reward. We believe the optimal sample complexity for bandit- RL games is an interesting open question.
Linear bandit games
Setting We consider bandit game with action space A. B that are finite but potentially arbitrarily large, and assume addition that the reward functions has a linear form
(8) where A B Rdd is d d-dimensional feature map, 8 85 Id are unknown ground truth parameters for the rewards, and 21, are random noise which we assume are mean-zero and 1-sub- Gaussian. Let + { b)= (a, b) A x B) denote the set of all possible features. For linear bandit games, we define gap, same as definition (5) for bandit games.
7 (a, b) = ((a TT;
01 + 21, T2(a, b) = aa, 0-
Algorithm and guarantee We present our algorithm for linear bandit games in Algorithm 3. Compared with our Algorithm for bandit games, Algorithm 3 takes advantage of the linear structure through the following important modifications: (1) Rather than querying every action pair, we only query (a, b) in core set K. found through the following subroutine
CoreSet ( == (K, where K AC B, PE Ax. such that
max TT ( Σ ((,
2d 2d and K= |C| 4d log log d 16. (10)
(a.D)EK
Such a core set is guaranteed to exist for any finite + [24, Theorem 4.4), and can be found efficiently in Od) steps of computation [44, Lemma 3.9]. (2) Rather than estimating the reward every (a, b) in a tabular fashion, we use weighted least-squares (9) to obtain estimates (0,, 0z) which are then used to approximate the true reward for all (a, b).
We now state our main guarantee for Algorithm 3. The proof can found in Appendix E. Theorem 5 (Learning Stackelberg in linear bandit games). For any linear bandit game, Algorithm 3 oufputs (gap, E) -upproximatte Stackelberg equilibrium (ā, b) with probability at least 1 - 8:
Φo (a) 2 (2)2(() 2 max do do(a) gap: 8, aeA
in at most = Ō(dP/E?) queries.

---

Sample complexity; computation Theorem 5 shows that Algorithm achieves Dsd2/=?) sample complexity for learning Stackelberg equilibria in linear bandit games. This only depends polynomially on the feature dimension d instead of the size of the action spaces A. B, which improves over Algorithm 1 when A, are large and is desired given the linear structure (8). This sample complexity has at most a (dd) gap from the lower bound: An (2(/E²²) lower bound for linear bandit games can be obtained by directly adapting R(AB/E" lower bound for bandit games in Theorem (see Appendix E.2 for a formal statement and proof). We also note that, while the focus of Theorem the sample complexity rather than the computation, Algorithm is guaranteed to in poly(A A, B, d, 1 ) time, since the CoreSet subroutine, the weighted least squares step (9), and the final optimization step in approximate best-response sets all be solved in polynomial time.
6 Conclusion
This paper provides the first line of sample complexity results for learning Stackelberg equilibria in general-sum games with bandit feedback of the rewards and sampling noise. We identify fundamental gap between the exact and estimated versions of the Stackelberg value, and design sample-efficient algorithms for learning Stackelberg with value optimal up this gap, in several representative two-player general-sum games. We believe our results open up a number of interesting future directions, such the optimal sample complexity for bandit-RL games and linear-bandit games, learning Stackelberg in more general Markov games, or further characterizations on what kinds of games admit small gap.
Acknowledgment
The authors would like to thank Alex Trott and Stephan Zheng for the inspiring discussions on the AI Economist. The authors also thank the Theory of Reinforcement Learning program the Simons Institute (Fall 2020) for hosting the authors and incubating our initial discussions.
Funding transparency statement
YB, HW, CX are funded through employment with Salesforce.
References
[1] A. Ahmadinejad, S. Dehghani, M. Hajiaghayi, B. Lucier, H. Mahini, and S. Seddighin. From duels to battlefields: Computing equilibria of blotto and other games. Mathematics of Operations Research, 1444):1304-1325 2019.
[2] E. Altman. Constrained Markov decision processes, volume 7. CRC Press, 1999.
[3] M. Azar, Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[4] Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning, In International Conference on Machine Learning, pages 551-560. PMLR, 2020.
[5] Y. Bai, C. Jin, and T. Yu. Near-optimal reinforeement learning with self-play, arXiv preprint arXiv:2006. 12007, 2020.
[6] A. Blum, N. Haghtalab, and A. D. Procaccia. Learning optimal commitment to overcome insecurity. 2014.
[7] A. Blum. N. Haghtalab, M. Hajiaghayi, and S. Seddighin. Computing stackelberg equilibria of large general-sume games. In International Symposium on Algorithmic Game Theory, pages 168-182 Springer, 2019.
[8] S. P. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[9] N. Cesa-Bian Desa-Bianchi and Lugosi, Prediction, learning, and games. Cambridge university press,
2006.
10

---

[10] R. Cole and T. Roughgarden. The sample complexity of revenue maximization. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing, pages 243-252, 2014.
[11] V. Conitzer and T. Sandholm. Complexity of mechanism design. arXiv preprini cs/0205075, 2002.
[12] V. Conitzer and T. Sandholm. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference Electronic Commerce, pages 132-141, 2004.
[13] V. Conitzer and T. Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM conference on Electronic commerce, pages 82-90, 2006.
[14] P. Dütting, Z. Feng, H. Narasimhan, D. Parkes, and S. S. Ravindranath. Optimal auctions through deep learning. International Conference on Machine Learning, pages 1706-1715. PMLR, 2019.
[15] Fiez, B. Chasnov, and L. J. Ratliff. Convergence of learning dynamics in stackelberg games. arXiv preprint
2019.
[16] D. J. Foster, Z. Li, T. Lykouris, K. Sridharan, and E. Tardos. Learning in games: Robustness of fast convergence. arXiv preprint arXiv:1606.0624 2016.
[17] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? arXiv preprint arXiv: 1807,0337 2018.
[18] C. Jin, A. Krishnamurthy, M. Simchowitz, and T. Yu. Reward-free exploration for reinforcement learning, arXiv preprint arXiv:2002.02794 2020.
[19] C. Jin, P. Netrapalli, and M. Jordan. What is local optimality in nonconve--nonconcau minimax optimization? In International Conference on Machine Learning, pages 4880 4889. PMLR, 2020.
[20] R. Jordan, Y. Vorobeychik, and M. P. Wellman. Searching for approximate equilibria in empirical games. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems- Volume 2, pages 1063-1070, 2008
[21] G. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[22] D. Korzhyk, Z. Yin, C. Kiekintveld, V. Conitzer, and M. Tambe. Stackelberg vs. nash security games: An extended investigation of interchangeabilityy equivalence, and uniqueness. Journal of Artificial Intelligence Research, 41:297-327, 2011.
[23] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[24] Lattimore, Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning. pages 3662-5670. PMLR, 2020.
[25] J. Z. Leibo, V. Zambaldi, M. Lanctot. J. Marecki, and T. Graepel. Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint vrXiv:1702.0303: 2017.
[26] J. Letchford and V. Conitzer. Computing optimal strategies to commit to in extensive-form games. In Proceedings of the 11th ACM conference on Electronic commerce, pages 83-92, 2010.
[27] J. Letchford, V. Conitzer, and K. Munagala. Learning and approximating the optimal strategy to commit to. International Symposium on Algorithmic Game Theory, pages 250-262, Springer, 2009.
[28] Q. Liu, Yu, Y. Bai, and C. Jin. sharp analysis of model-based reinforcement learning with self-play arXiv preprint arXiv:2010.0164,, 2020.

---

[29] A. Marchesi, F. Trovò, and N. Gatti. Learning probably approximately correct maximin strategies in simulation- based games with infinite strategy spaces. In Proceedings of the 19th International Conference Autonomous Agents and MultiAgemt Systems, pages 834-842, 2020.
[30] Nash. Non-cooperative games. Annals of mathematics, pages 286-28862900822 265, 1951.
[31] A. Nemirovski. Prox-method with rate of convergence o (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[32] A. S. Nemirovski and D. B. Yudin. Cesari convergence of the gradient method of approximating saddle points of convex- concave functions. In Doklady Akademii Nauk, volume 239, pages 1059. Russian Academy of Sciences, 1978.
[33] M. Nouiched, M. Sanjabi, J. D. Lee, and M. Razaviyayn. Solving class of non-convex min-max games using itcrative first order methods. arXiv preprint (902::::902002299 2019.
[34] B. Peng, W. Shen, P. Tang, and S. Zuo. Learning optimal strategies to commit to. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 2149-2156, 2019.
[35] Pérolat, F. Strub, Piot, and O. Pietquin. Learning nash equilibrium for general-sum markov games from batch data. In Artificial Intelligence and Statistics, pages 232-241. PMLR, 2017.
[36] H. Rafique, M. Liu, Q. Lin, and T. Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060, 2018.
[37] A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. arXiv preprint arXiv:1311.186) 2013.
[38] Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78-86, 2010.
[39] G. Sessa, I. Bogunovic, M. Kamgarpour, and A. Krause. Learning to play sequential games versus unknown opponents. arXiv preprini urXiv:2007.0527/ 2020.
[40] L. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
[41] Y. Shoham and K. Leyton-Browe Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008
[42] M. Simaan and B. Cruz. On the stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications, 11(5):533-555, 1973.
[43] M. Tambe. Security and game theory: algorithms, deployed systems, lessons learned. Cam- bridge university press, 2011.
[44] M. J. Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.
[45] D. Vasal. Stochastic stackelberg games. arXiv preprint urXiv:2005.019%) 2020.
[46] J. von Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295-320, 1928.
[47] B. Von Stengel and S. Zamir. Leadership games with convex strategy sets. Games and Economic Behavior, 69(2):446 457, 2010.
[48] Y. Vorobeychik, M. P. Wellman, and S. Singh. Learning payoff functions in infinite games. Machine Learning, 67(1-2):145-168, 2007.
[49] M. J. Wainwright. High-dimenssionl statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[50] M. P. Wellman. Methods for empirical game-theoretic analysis. In proceedings of the s
national conference Artificial intelligence-dae Volume 2, pages 1552-1555, 2006.
12

---

[51] Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultaneous move markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 1684-3622. PMLR, R, 2020.
[52] K. Zhang, S. M. Kakade, T. Başar, and L. F. Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprint arXiv:2007.07466 2020.
[53] S. Zheng, A. Trott, S. Srinivasa, N. Naik, M. Gruesbeck, D. C. Parkes, and R. Socher. The ai economist: Improving equality and productivity with ai-driven tax policies. arXiv preprint arXiv:2004. 13332, 2020.
13


Reviews:
[{"review_id": "n1XN8OjViPh", "reviewer": "Reviewer_82ud", "summary": "The paper considers learning Stackelberg equilibria in unknown games with noisy bandit feedback of the rewards obtained by leader and follower, respectively. The authors prove an information theoretic gap between the value of the true Stackelberg equilibrium and the one learned from finitely many data points. However, they show that approximate Stackelberg equilibria (defined according to a $\\epsilon$-best response of the follower) can be learned efficiently using empirical reward estimates. Upper and matching lower bounds are provided on the number of required samples. Results are instantiated for bandit games, bandit reinforcement learning games, and linear bandit games.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem considered is relevant and I believe the contributions are novel, as previous work has mostly considered learning Nash equilibria. Moreover, the paper is well written and organized. Hence, my accept score.\nHowever, I think that the authors should not claim (in Conclusions): \"This paper provides the first line of sample complexity results for learning Stackelberg equilibria in general-sum game\", since previous work has already considered learning Stackelberg equilibria under different assumptions (as discussed in related work section). Moreover, I believe some related works have been overlooked. \nFor instance, the StackelUCB algorithm by [Sessa et at., Learning to Play Sequential Games versus Unknown Opponents, NeurIPS 2020] also computes the optimal strategy for the leader, under noisy (albeit different) bandit feedback, by building an approximate best-response set. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "How do the obtained upper bounds compare with previous works, e.g. [26,33] which consider learning Stackelberg equilibria from best-response oracle? It is not clear which feedback model is less restrictive (since in practice we may not have access to the follower's reward and we could only observe the actions played), so I believe the obtained bounds deserve a fair comparison with these works. \n\nMoreover, it would be nice to see some experimental results which can illustrate whether the derived bounds hold in practice.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "NuWICyaoyZj", "reviewer": "Reviewer_79oc", "summary": "The authors study the problem of learning Stackelberg equilibria from random samples in general sum games. The work will be of interest to both theoreticians of Stackelberg games and those who work on applications. The main contributions are:\n- In bandit games, which are two-step Markov games where the leader and follower only observe their own rewards, the authors show that there is a constant gap between the optimal and the best strategy the leader can attain with a finite number of samples. This gap is a central feature of the paper—it exists in all settings that are analyzed by the authors, and the sample complexity results give you performance that approaches the best possible up to the gap. The authors give a tight bound on the number of samples required which is linear in the size of the action sets of the leader and follower and quadratic in the approximation ratio relative to the gap. The algorithm queries each leader action a fixed number of times (which is the same across all actions) to construct an estimate of the follower's best response function that has the desired properties.\n- For bandit-RL games, where the leader selects an action that induces an MDP for the follower, the authors show that a quite similar algorithm can be applied. The main challenge is that the follower has to learn the optimal policy for each MDP (this is an RL setting with bandit feedback to the follower), and this requires an application of some recent work to yield appropriate estimates. The bandit-RL game setting reduces to bandit games when the horizon is of length 1. The derived sample complexity matches that of the bandit game for the horizon = 1 subcase, showing that the dependence on these parameters is tight. However, the scaling in horizon length is extreme—more than quintic. There is no known lower bound for the dependence on horizon.\n- In linear bandit games, which are bandit games, but where the rewards are a linear function of the features of each action. The algorithm the authors state for this setting scales quadratically in the dimension of the feature space and quadratically in the approximation ratio. There is a factor of the dimension between this and the lower bound they derive.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found the paper to be clear and well-written throughout, even in the supplemental material. The authors relate their work to prior work well and explain these connections extensively. The sample complexity results are original and useful to other researchers in this area. Bandit-RL games look like the most challenging of the settings and the most significant open questions come from this setting (the required dependence on states and horizon).\n\nI don't have a firm basis for this, but I suspect the result about the constant gap for the bandit game setting was \"known\" in the Stackelberg general sum setting—it might be a consequence of other results or not stated directly. I suspect there is some kind of explanation in terms of the standard literature that could be added, but I don't have a citation. Even if this is the case, I don't think this is a major issue for the paper—I see the main contributions as analyzing the sample complexity \"up to the gap.\"\n\nThe magnitude of the gap diminishes the interest of the authors' results to some extent—you would want some kind of guarantee that the gap would not be too large for a class of problems of interest.\n\nPost-response edit:\n- To clarify, I did not deduct any points for my suspicion that the constant gap result is \"known\" (more likely, a consequence of a known result). I do not have a specific reference for this and no reference was raised by the other reviewers either.\n- The papers specific novelty are suspect. Specifically, 1. \"To the best of our knowledge, this is the first result for sample-efficient learning of Stackelberg equilibrium in general-sum games with bandit feedbacks.\" (top of page 6) and 2. \"This paper provides the first line of sample complexity results for learning Stackelberg equilibria in general-sum games.\" (conclusion, bottom of page 9). The pg. 9 claim is clearly false—the authors acknowledge other work in their related work section. The pg. 6 claim—I believe the authors intend to say that they are the first to provide results in their specific bandit feedback model, which is true to the best of my knowledge. Nevertheless, there are other bandit-style feedback models in the literature—for example, the learning model that assumes best responses by the adversary _is_ a bandit feedback model—it is just a different one from the authors'. These claims need to be revised.\n- I still find the central claims of the paper to merit acceptance. The paper would benefit from integrating a stronger motivation about what kinds of games have a small gap—the point the authors made in their response.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors don't spend a lot of time on limitations, but I found their treatment adequate—they identify gaps in knowledge (e.g., between upper and lower bounds) as well as fundamental limitations in the learning process.\n\nNegative societal impact is not a concern for this theoretical paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "KgjqxdBALy", "reviewer": "Reviewer_pAwo", "summary": "The paper considers the problem of online learning the Stackelberg Equilibrium in general-sum games. The authors identify a fundamental gap between the exact and the estimated version of the Stackelberg value. Then they consider three general-sum games setting: bandit games, bandit-RL games, and linear bandit games, designing algorithms for these settings and providing sample complexity results.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies an important problem in the online learning literature, analyzing the problem of learning Stackelberg Equilibrium in general-sum games. Although many works study this problem in the exact setting, the authors show that the problem becomes informationally-theoretically hard when we cannot observe the exact estimates of the rewards but only noisy samples. Moreover, the authors study the problem of learning epsilon-Stackelberg equilibrium in three settings: bandit games, bandit RL games, and linear bandit games. In my opinion, this paper shows important results for the game theory and online learning communities. \nMoreover, these results leave out interesting future directions for the considered setting (for example, studying the optimal sample-complexity for bandit-RL games) and other settings as Leader-Follower MDPs, or Turn-based Markov Games.\n\n\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, this paper has not particular limitations. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6-e2GEBm5Yp", "reviewer": "Reviewer_c7dP", "summary": "This paper provides sample complexity results and analysis of algorithms that learn Stackelberg equilibria for three types of games: general bandit games, bandit-RL games, and linear bandit games. The novelty of this paper lies in the fact that it studies a different solution concept, Stackelberg game, in general-sum games without assumptions regarding the convexity or concavity of the reward functions. To the best of my knowledge, this is the first paper that studies the sample complexity for learning Stackelberg equilibria under such games.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. This paper focus on learning with bandit feedback for Stackelberg equilibria in static general-sum games, instead of general-sum stochastic (Markov) games. As the authors remarked, bandit games and bandit-RL games can be considered special cases of general-sum stochastic games (line 108). The significance of the paper is confined since only static games are considered (the bandit-RL is similar to a static game considering that the value functions are pre-computed using a reward-free learning algorithm.) It would be better if the authors can shed more light on (discuss related works about) learning Stackelberg equilibria for dynamic games (stochastic Stackelberg game and Stackelberg differential game) in which the leader and the follower make their decisions sequentially.\n\n\n2. There exists literature that studies Stackelberg equilibria for stochastic games which the authors want to include in ‘related works’.\n        *  Vasal, Deepanshu. \"Stochastic Stackelberg games.\" arXiv preprint arXiv:2005.01997 (2020). .\n\n3.The real-world application of the proposed algorithms is not well demonstrated. The authors did mention the optimal taxation problem by learning the Stackelberg equilibrium studied by another work [48], which is a problem that often times be formed as a Stackelberg game problem (Wang, You-Qiang. \"Commodity taxes under fiscal competition: Stackelberg equilibrium and optimality.\" American Economic Review 89.4 (1999): 974-981.). This application is discussed at a problem formulation level. It is not clear how the results (sample complexity results) can offer insights for the potential applications. Hence, the current draft seems somewhat dry, overloaded with complexity metrics and math equations. Discussions in \"Implications; Overview of Algorithms\" does not offer two much practical interpretation. It requires effort for the reader on interpreting their practical meaning. It would be better if the authors can explain the results in the context of a practical application.\n\n4. I did not thoroughly check all the proofs due to time constraint. I took a quick a look and no mistakes were identified.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The discussion mainly centered on the authors' claims of novelty.  While (to our knowledge) the technical contributions are indeed novel, there was consensus that the informal claims need to be significantly toned down -- there are too many variants of "initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium" and everything being "vastly open" which is simply not true given the references cited by the authors themselves.  (There is sometimes a qualifier about samples / a bandit model, but prior work could also be considered to involve samples and a bandit model -- this isn't exactly what sets this paper apart, though maybe the noise does, which is sometimes, but not always, mentioned in the qualifier.  As pointed out by one of the reviewers, there are also places where there isn't even any qualifier at all.)  The fact that this is claimed again and again, and the fact that this issue was apparently already raised in the ICML submission of an earlier version of this paper and apparently wasn't fully addressed (I wasn't involved in reviewing that version so I do not know the details), do honestly leave us a bit worried about just accepting the paper.  That seems unfortunate because it really wasn't necessary.  Still I think acceptance is the right decision, but the authors should appreciate that this really involves trusting them that they will truly fix this this time.  The same goes for any talk/poster about the material of course.

I wonder if the line of work on empirical game theory by Wellman and others should be cited here somewhere.
Decision: Accept (Poster)