Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games

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.

heading: 1 Introduction
text: Real-world problems such as economic design and policy making can often be modeled as multiagent 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], a game modeling a real-world social-economic system involving a leader (e.g. the government) and a group of interacting followers (e.g. citizens). The leader sets a tax rate which determines an 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 is to maximize her own reward (such as overall equality) which is in general different from the followers’ rewards, making these games general-sum [38]. Such two-level thinking appears broadly in other applications as 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 (NeurIPS 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 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 is 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 in 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 Stackelberg equilibria in general-sum games, but restricts attention to either the full observation setting (so that the exact game is observable) or with an 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 Stackelberg 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 a fundamental gap between the exact Stackelberg value and its estimated version from finite samples, which cannot be closed information-theoretically regardless of the algorithm (Section 3.1). We then propose a rigorous definition gapε for this gap, and show that it is possible to sample-efficiently learn the (gapε + ε)-approximate Stackelberg equilibrium with Õ(AB/ε2) samples, where A,B are the number of actions for the two players. We further show a matching lower bound Ω(AB/ε2) (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 action determines an episodic Markov Decision Process (MDP) for the follower. We show that a (gapε + ε) approximate Stackelberg equilibrium for the leader can be found in Õ(H5S2AB/ε2) episodes of play, where H,S are the horizon length and number of states for the follower’s MDP, and A,B are the number of actions for the two players (Section 4). Our algorithm utilizes recently developed reward-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̃(d2/ε2) 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 Õ(d) gap from the lower bound.

heading: 1.1 Related work
text: 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 twoplayer 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 minimax theorem [46]. Results for learning Stackelberg equilibria beyond convex-concave setting are much more recent,
with Rafique et al. [36], Nouiehed et al. [33] considering the nonconvex-concave setting, and Fiez et al. [15], Jin et al. [19], Marchesi et al. [29] considering the nonconvex-nonconcave setting. Marchesi et al. [29] provide sample complexity results for learning Stackelberg with infinite strategy spaces, using discretization techniques that may scale exponentially in 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-sum setting.
Learning Stackelberg equilibria in general-sum games The computational complexity of finding Stackelberg equilibria in games with simultaneous play (“computing optimal strategy to commit to”) is studied in [13, 26, 47, 22, 1, 7]. 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 a “best response oracle” [27, 6, 34], that returns the follower’s exact best response strategy when a leader’s strategy is queried. This oracle and the noisy reward oracle we 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 et al. [39] proposes the StackelUCB algorithm to sample-efficiently learn a Stackelberg game where the opponent’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 et 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 errors. 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 as 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, or 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).

heading: 2 Preliminaries
text: Bandit games A general-sum two-player bandit game can be described by a tuple M = (A,B, r1, r2), which defines the following game played by two players, a leader and a follower:
• The leader plays an action a ∈ A, with |A| = A. • The follower sees the action played by the leader, and plays an action b ∈ B, with |B| = B. • The follower observes a (potentially random) reward r2(a, b) ∈ [0, 1]. The leader also observes
her own reward r1(a, b) ∈ [0, 1].
Note that this is a special case of a general-sum turn-based Markov game with two steps [40, 4]. This game is also a turn-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 µi(a, b) := E[ri(a, b)] (i = 1, 2) denote the mean rewards. For each leader action a, the best response set BR0(a) is the set of follower actions that maximize µ2(a, ·):
BR0(a) := { b : µ2(a, b) = max
b′∈B µ2(a, b
′) } . (1)
Given the best-response set BR0(a), we define the function φ0 : A → [0, 1] as the leader’s value function when the follower plays the worst-case best response (henceforth the“exact φ-function”):
φ0(a) := min b∈BR0(a) µ1(a, b), (2)
This is the value function for the leader action a, assuming the follower plays the best response to a and breaks ties in the best response set against the leader’s favor. This is known as pessimistic tie breaking and provides a 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(a, ·) and (among the maximizers) minimize µ1(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 φ0 [42]:
a? ∈ arg max a∈A φ0(a). (3)
We are interested in finding approximate solutions to the Stackelberg equilibrium, that is, an action â that approximately maximizes φ0(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 ∈ A for the follower. The citizen (follower) then chooses the amount of labor b ∈ B she wishes to perform. The rewards for the two players are different in general: For example, the citizen’s reward r2(a, b) can be her post-tax income per labor, and the government’s reward r1(a, b) can be a weighted average of its tax income and some measure of the citizen’s welfare (e.g. not too much labor). We remark that the actual AI Economist is more similar to a 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 bandit feedback setting, that is, the algorithm cannot directly observe the mean rewards µ1(·, ·) and µ2(·, ·), and can only query (a, b) and obtain random samples (r1(a, b), r2(a, b)). Our goal is to determine the number of samples in order to find an approximate maximizer of φ0(a).
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 a and obtain the exact best response set BR0(a) [27, 34].
Markov 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 defined by a tuple (H,S,B, d1,P, r), where H is the horizon length, S is the state space, B is the action space1, P = {Ph(·|s, b) : h ∈ [H], s ∈ S, b ∈ B} is the transition probabilities, and r = {rh : S × B → [0, 1], h ∈ [H]} are the (potentially random) reward functions. A policy π = { πbh(·|s) ∈ ∆B : h ∈ [H], s ∈ 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 h ∈ {1, . . . ,H}, the agent observes state sh ∈ S, takes an action bh ∼ πh(·|sh), observes her reward rh = rh(sh, bh) ∈ [0, 1], and transits to the next state sh+1 ∼ Ph(·|sh, bh). The initial state is received from the MDP: s1 ∼ d1(·). The overall value function (return) of a policy π is defined as V (π) := Eπ [∑H h=1 rh(sh, bh) ] .
1The notation B indicates that the MDP is played by the follower (cf. Section 4); we reserve A as the leader’s action space in this paper.

heading: 3 Warm-up: bandit games

heading: 3.1 Hardness of maximizing φ0 from samples
text: Given the exact φ-function φ0 (2), a natural notion of approximate Stackelberg equilibrium is to find an action â that is ε near-optimal for maximizing φ0:
φ0(â) ≥ max a∈A φ0(a)− ε. (4)
However, the following lower bound shows that, in the worst case, it is hard to find such â from finite samples.
Theorem 1 (Ω(1) lower bound for maximizing φ0). For any sample size n and any algorithm for maximizing φ0 that outputs an action â ∈ A, there exists a bandit game with A = B = 2 on which the algorithm must suffer from Ω(1) error with probability at least 1/3:
φ0(â) ≤ max a∈A φ0(a)− 1/2.
Theorem 1 shows that, no matter how large the sample size n is, any algorithm in the worst-case have to suffer from an Ω(1) lower bound for maximizing φ0 (i.e. determining the Stackelberg equilibrium for the leader). This result stems from a hardness of determining the best response BR0(a) 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 to the standard 1/ √ n 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.

heading: 3.2 Learning Stackelberg with value optimal up to gap
text: The lower bound in Theorem 1 shows that approximately maximizing φ0 is information-theoretically hard. Motivated by this, we consider in turn a slightly relaxed notion of optimality, in which we consider maximizing φ0 only up to the gap between φ0 and its counterpart using ε-approximate best responses. More concretely, define the ε-approximate versions of the best response set and φ-function as
φε(a) := min b∈BRε(a) µ1(a, b),
BRε(a) := { b ∈ B : µ2(a, b) ≥ max
b′ µ2(a, b
′)− ε } .
These definitions are similar to the vanilla BR0 and φ0 in (1) and (2), except that we allow any ε-approximate best response to be considered as a valid response to the leader action. Observe we always have BRε(a) ⊇ BR0(a) and φε(a) ≤ φ0(a). We then define the gap of the game for any ε ∈ (0, 1) as
gapε := max a∈A φ0(a)−max a∈A φε(a) ≥ 0. (5)
This gapε is discontinuous in ε in general, and can be as large as Θ(1) for any ε > 0 without additional assumptions on the relation between µ1 and µ22. See Figure 1 for an illustration for a typical maxa∈A φε(a) against ε.
With the definition of the gap, we are now ready to state our main result, which shows that it is possible to sample-efficiently learn Stackelberg Equilibria with value up to (gapε + ε). The proof can be found in Appendix C.3.
2This gapε could be small when µ1 and µ2 have certain relations, such as zero-sum or cooperative structure. See Appendix C.6 for more discussions.
Algorithm 1 Learning Stackelberg in bandit games Require: Target accuracy ε > 0. set N ← C log(AB/δ)/ε2 for some constant C > 0.
1: Query each (a, b) ∈ A× B for N times and obtain {r(j)1 (a, b), r (j) 2 (a, b)}Nj=1. 2: Construct empirical estimates of the means µ̂i(a, b) = 1N ∑N j=1 r (j) i (a, b) for i = 1, 2. 3: Construct approximate best response sets and values for all a ∈ A:
φ̂3ε/4(a) := min b∈B̂R3ε/4(a)
µ̂1(a, b), where B̂R3ε/4(a) := { b : µ̂2(a, b) ≥ max
b′∈B µ̂2(a, b
′)− 3ε/4 } .
4: Output (â, b̂), where â = arg maxa∈A φ̂3ε/4(a), b̂ = arg minb∈B̂R3ε/4(â) µ̂1(â, b).
Theorem 2 (Learning Stackelberg in bandit games). For any bandit game and ε ∈ (0, 1), Algorithm 1 outputs (â, b̂) such that with probability at least 1− δ,
φ0(â) ≥ φε/2(â) ≥ max a∈A φ0(a)− gapε − ε,
µ2(â, b̂) ≥ max b′∈B µ2(â, b ′)− ε
with n = Õ ( AB/ε2 ) samples, where Õ(·) hides log factors. Further, the algorithm runs in O(n) =
Õ(AB/ε2) time.
Implications; Overview of algorithm Theorem 2 shows that it is possible to learn â that maximizes φ0(a) up to (gapε + ε) accuracy, using Õ(AB/ε
2) samples. The quantity gapε is not bounded and can be as large as Θ(1) for any ε (see Lemma C.1 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 µ2(a, ·) is at least ε0-better than the second best action, then for ε < ε0 we have gapε = 0 and Theorem 2 implies an ε-optimal Stackelberg guarantee. In general, Theorem 2 presents a “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 φε/2(â) which is slightly stronger than φ0 (since φε/2(â) ≤ φ0(â)), and guarantees the learned b̂ is indeed an ε-approximate best response of 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 ε-approximate Stackelberg, in terms of the scaling with problem parameters. For instance, in the AI Economist example, A is the number of tax rate choices for the government, and B is 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/ε.
The main step in Algorithm 1 is to construct approximate best response sets B̂R3ε/4(a) for all a ∈ A based on the empirical estimates of the rewards. Through concentration, we argue that B̂R3ε/4(a) is a good approximation of the true best response sets in the sense that BRε/2(a) ⊆ B̂R3ε/4(a) ⊆ BRε(a) holds for all a ∈ 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-breaking) constitutes a Nash equilibrium for that Markov game (see Appendix C.5 for a formal statement and proof). However, existing Nash-finding algorithms for general-sum Markov games such as Multi-Nash-VI [28] do not imply an algorithm for finding the Stackelberg equilibrium. This is because general-sum games have multiple Nash equilibria (with different values) in general [38], and these existing Nash-finding algorithms cannot pre-specify which Nash to output.
Lower bound We accompany Theorem 2 by an Ω(AB/ε2) sample complexity lower bound, showing that Theorem 2 achieves the optimal sample complexity up to logarithmic factors.
Theorem 3 (Lower bound for bandit games). There exists an absolute constant c > 0 such that the following holds. For any ε ∈ (0, c), g ∈ [0, c), any A,B ≥ 3, and any algorithm that queries N ≤ c [ AB/ε2 ] samples and outputs an estimate â ∈ A, there exists a bandit game M on which
gapε = g and the algorithm suffers from (g + ε) error:
φε/2(â) ≤ φ0(â) ≤ max a∈A φ0(a)− g − ε
with probability at least 1/3.
This lower bound shows the tightness of Theorem 2, and suggests that (gapε + ε) suboptimality is perhaps a sensible learning goal, as for any algorithm and any value of g ≥ 0 there exists a game with gapε = g, on which the algorithm has to suffer from (g + ε) error, if the number of samples is at most O(AB/ε2). The proof of Theorem 3 is deferred to Appendix C.4.

heading: 4 Bandit-RL games
text: In this section, we investigate learning Stackelberg equilibrium in bandit-RL games, in 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 to 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 AI Economist [53].
Setting A bandit-RL game is described by the leader’s action set A (with |A| = A), and a family of MDPs M = {Ma : a ∈ A}. Each leader action a ∈ A determines an episodic MDP Ma = (H,S,B,Pa, r1,h(a, ·, ·), r2,h(a, ·, ·)) 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 ∈ A. • The follower sees this action and enters the MDP Ma. She observes the deterministic3 initial
state s1, and plays in Ma with exploration feedback for one episode. • While the follower plays in the MDP, she observes reward r2,h(a, sh, bh), whereas the leader
also observes her own reward r1,h(a, sh, bh).
We let πb denote a policy for the follower, and let V1(a, πb) and V2(a, πb) denote its value functions (in Ma) for the leader and the follower respectively.
Similar as in bandit games, we define the ε-approximate best-response set BRε(a) and the εapproximate φ-function φε(a) for all ε ≥ 0 as
φε(a) := min πb∈BRε(a)
V1(a, π b), where BRε(a) := { πb : V2(a, π
b) ≥ max π̃b V2(a, π̃ b)− ε
} .
Define gapε = maxa∈A φ0(a)−maxa∈A φε(a) similarly as in (5). We are interested in the number of episodes in order to find a (gapε + ε) near-optimal Stackelberg equilibrium.

heading: 4.1 Algorithm description
text: At a high level, our algorithm for bandit-RL games is similar as for bandit games – query each leader action a ∈ A sufficiently many times, let the follower learn the best response (i.e. best policy for the MDP Ma) for each a ∈ A, and then choose the leader action that maximizes the best response value function. This requires solving
arg max a∈A φ3ε/4(a) := arg max a∈A min πb∈B̂R3ε/4(a)
V̂1(a, π b),
B̂R3ε/4(a) := { πb : V̂2(a, π
b) ≥ max π̃b V̂2(a, π̃ b)− 3ε/4
} ,
(6)
3The general case where s1 is stochastic reduces to the deterministic case by adding a step h = 0 with a single deterministic initial state s0, which only increases the horizon of the game by 1.
Algorithm 2 Learning Stackelberg in bandit-RL games Require: Target accuracy ε > 0.
1: for a ∈ A do 2: Let the leader pull arm a ∈ A and the follower run the Reward-Free RL-Explore algorithm
for N ← Õ(H5S2B/ε2 +H7S4B/ε) episodes, and obtain model estimate M̂a. 3: Let (V̂1(a, ·), V̂2(a, ·)) denote the value functions for the model M̂a. 4: Compute the empirical best response value V̂ ?2 (a) := maxπb V̂2(a, π
b) by any optimal planning algorithm (e.g. value iteration) on the empirical MDP M̂a.
5: Solve the following program
minimizeπb V̂1(a, π b) s.t. πb ∈ B̂R3ε/4(a) := { πb : V̂2(a, π b) ≥ V̂ ?2 (a)− 3ε/4 }
(7) by subroutine (π̂b,(a), φ̂3ε/4(a))← WorstCaseBestResponse(M̂a, V̂ ?2 (a)− 3ε/4).
output (â, π̂b) where â← arg maxa∈A φ̂3ε/4(a) and π̂b ← π̂b,(â).
where V̂1 and V̂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 own and the leader’s reward over the entire approximate best response set B̂R3ε/4 so as to make sure the estimates V̂i(a, π
b) (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 et al. [18] for the follower to 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 πb∈B̂R3ε/4(a) V̂1(a, π b) in (6) requires minimizing a 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 WorstCaseBestResponse, which adopts efficient solution in poly(HSB) 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.

heading: 4.2 Main result
text: We now state our theoretical guarantee for Algorithm 2. The proof can be found in Appendix D.2. Theorem 4 (Learning Stackelberg in bandit-RL games). For any bandit-RL game and sufficiently small ε ≤ O(1/H2S2), Algorithm 2 with n = Õ(H5S2AB/ε2 +H7S4AB/ε) episodes of play can return (â, π̂b) such that with probability at least 1− δ,
φ0(â) ≥ φε/2(â) ≥ max a∈A φ0(a)− gapε − ε,
V2(â, π̂ b) ≥ max
π̃b V2(â, π̃
b)− ε,
where Õ(·) hides log(HSAB/δε) factors. Further, the algorithm runs in poly(HSAB/δε) 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ε+ε) can be efficiently found with polynomial sample complexity and runtime. In particular, (for small ε) the leading term in the sample complexity scales as Õ(H5S2AB/ε2). Since bandit-RL games include bandit games as a special case, the Ω(AB/ε2) 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 is a new RL setting in between the single-reward setting and the full reward-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 a near-optimal policy. In contrast, in the full reward-free
Algorithm 3 Learning Stackelberg in linear bandit games Require: Target accuracy ε > 0.
1: Find (K, ρ)← CoreSet(Φ) (cf. (10)). Let K = {(aj , bj) : 1 ≤ j ≤ K} where K = |K|. 2: Query each (aj , bj) for N = O(d log(d/δ)/ε2) times. Let (µ̂1,j , µ̂2,j) denote the empirical
mean of the observed rewards over the N queries. 3: Estimate (θ?1 , θ ? 2) via weighted least squares
θ̂i := arg min θ∈Rd K∑ i=1 ρ(aj , bj) ( φ(aj , bj) >θi − µ̂i,j )2 , i = 1, 2. (9)
4: Construct approximate best response sets and values for all a ∈ A:
B̂R3ε/4(a) := { b : φ(a, b)>θ̂2 ≥ max
b′∈B φ(a, b′)>θ̂2 − 3ε/4
} ,
φ̂3ε/4(a) := min b∈B̂R3ε/4(a)
φ(a, b)>θ̂1.
5: Output (â, b̂), where â = arg maxa∈A φ̂3ε/4(a), b̂ = arg minb∈B̂R3ε/4(â) φ(â, b) >θ̂1.
setting (follower wants accurate estimation of any reward), it is known Ω(S2) is unavoidable [18]. Our setting poses a unique challenge in between: The follower wishes to accurately estimate both r1, r2 on all near-optimal policies for r2. 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.

heading: 5 Linear bandit games
text: Setting We consider a bandit game with action space A, B that are finite but potentially arbitrarily large, and assume in addition that the reward functions has a linear form
r1(a, b) = φ(a, b) >θ?1 + z1, r2(a, b) = φ(a, b) >θ?2 + z2, (8)
where φ : A × B → Rd is a d-dimensional feature map, θ?1 , θ?2 ∈ Rd are unknown ground truth parameters for the rewards, and z1, z2 are random noise which we assume are mean-zero and 1-subGaussian. Let Φ := {φ(a, b) : (a, b) ∈ A× B} denote the set of all possible features. For linear bandit games, we define gapε same as definition (5) for bandit games.
Algorithm and guarantee We present our algorithm for linear bandit games in Algorithm 3. Compared with our Algorithm 1 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 a core set K found through the following subroutine
CoreSet(Φ) := (K, ρ) where K ⊂ A× B, ρ ∈ ∆K, such that
max φ∈Φ
φ> ( ∑
(a,b)∈K
ρ(a, b)φ(a, b)φ(a, b)> )−1 φ ≤ 2d and K = |K| ≤ 4d log log d+ 16. (10)
Such a core set is guaranteed to exist for any finite Φ [24, Theorem 4.4], and can be found efficiently in O(ABd2) steps of computation [44, Lemma 3.9]. (2) Rather than estimating the reward at every (a, b) in a tabular fashion, we use a weighted least-squares (9) to obtain estimates (θ̂1, θ̂2) 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 be found in Appendix E.1. Theorem 5 (Learning Stackelberg in linear bandit games). For any linear bandit game, Algorithm 3 outputs a (gapε + ε)-approximate Stackelberg equilibrium (â, b̂) with probability at least 1− δ:
φ0(â) ≥ φε/2(â) ≥ max a∈A φ0(a)− gapε − ε,
in at most n = Õ(d2/ε2) queries.
Sample complexity; computation Theorem 5 shows that Algorithm 3 achieves Õ(d2/ε2) 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,B are large and is desired given the linear structure (8). This sample complexity has at most a Õ(d) gap from the lower bound: An Ω(d/ε2) lower bound for linear bandit games can be obtained by directly adapting Ω(AB/ε2) lower bound for bandit games in Theorem 3 (see Appendix E.2 for a formal statement and proof). We also note that, while the focus of Theorem 5 is on the sample complexity rather than the computation, Algorithm 3 is guaranteed to run in poly(A,B, d, 1/ε2) time, since the CoreSet subroutine, the weighted least squares step (9), and the final optimization step in approximate best-response sets can all be solved in polynomial time.

heading: 6 Conclusion
text: 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 a fundamental gap between the exact and estimated versions of the Stackelberg value, and design sample-efficient algorithms for learning Stackelberg with value optimal up to this gap, in several representative two-player general-sum games. We believe our results open up a number of interesting future directions, such as 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 a small gap.

heading: Acknowledgment
text: 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 at 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.

Review summaries:
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: - 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. - 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. - 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.

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.

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.

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.