{'fraction_non_alphanumeric': 0.056384126157622644, 'fraction_numerical': 0.016346189608360918, 'mean_word_length': 3.9685854199390187, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games

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.


Introduction
Real-world problems such as economic design and policy making can often be modeled as 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], 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.
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(H 5 S 2 AB/ε 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(d 2 /ε 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.

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

Preliminaries
Bandit games A general-sum two-player bandit game can be described by a tuple M = (A, B, r 1 , r 2 ), 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.
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[r i (a, b)] (i = 1, 2) denote the mean rewards. For each leader action a, the best response set BR 0 (a) is the set of follower actions that maximize µ 2 (a, ·): Given the best-response set BR 0 (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"): 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]: 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 r 2 (a, b) can be her post-tax income per labor, and the government's reward r 1 (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 (r 1 (a, b), r 2 (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 BR 0 (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 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 s h ∈ S, takes an action b h ∼ π h (·|s h ), observes her reward r h = r h (s h , b h ) ∈ [0, 1], and transits to the next state s h+1 ∼ P h (·|s h , b h ). The initial state is received from the MDP: s 1 ∼ d 1 (·). The overall value function (return) of a policy π is defined as 3 Warm-up: bandit games 3.1 Hardness of maximizing φ 0 from samples 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 : 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: 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 BR 0 (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.

Learning Stackelberg with value optimal up to gap
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 These definitions are similar to the vanilla BR 0 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) ⊇ BR 0 (a) and φ ε (a) ≤ φ 0 (a). We then define the gap of the game for any ε ∈ (0, 1) as 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 µ 2 2 . See Figure 1 for an illustration for a typical max a∈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.
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 − δ, 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 BR 3ε/4 (a) for all a ∈ A based on the empirical estimates of the rewards. Through concentration, we argue that BR 3ε/4 (a) is a good approximation of the true best response sets in the sense that BR ε/2 (a) ⊆ BR 3ε/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

1: Query each (a, b) ∈ A × B for N times and obtain {r
3: Construct approximate best response sets and values for all a ∈ A: 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: 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.

Bandit-RL games
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 = {M a : a ∈ A}. Each leader action a ∈ A determines an episodic MDP M a = (H, S, B, P a , r 1,h (a, ·, ·), r 2,h (a, ·, ·)) that contains H steps, S states, B actions, with two reward functions r 1 and r 2 . In each episode of play, • The leader plays action a ∈ A.
• The follower sees this action and enters the MDP M a . She observes the deterministic 3 initial state s 1 , and plays in M a with exploration feedback for one episode.
• While the follower plays in the MDP, she observes reward r 2,h (a, s h , b h ), whereas the leader also observes her own reward r 1,h (a, s h , b h ).
We let π b denote a policy for the follower, and let V 1 (a, π b ) and V 2 (a, π b ) denote its value functions (in M a ) for the leader and the follower respectively.
Similar as in bandit games, we define the ε-approximate best-response set BR ε (a) and the ε- Define gap ε = max a∈A φ 0 (a) − max a∈A φ ε (a) similarly as in (5). We are interested in the number of episodes in order to find a (gap ε + ε) near-optimal Stackelberg equilibrium.

Algorithm description
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 M a ) for each a ∈ A, and then choose the leader action that maximizes the best response value function. This requires solving 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 BR 3ε/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 ∈ BR 3ε/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.

Main result
We now state our theoretical guarantee for Algorithm 2. The proof can be found in Appendix D.2.

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(H 5 S 2 B/ε 2 + H 7 S 4 B/ε) episodes, and obtain model estimate 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 .
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(H 5 S 2 AB/ε 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 setting (follower wants accurate estimation of any reward), it is known Ω(S 2 ) is unavoidable [18]. Our setting poses a unique challenge in between: The follower wishes to accurately estimate both r 1 , r 2 on all near-optimal policies for r 2 . 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 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 where φ : A × B → R d is a d-dimensional feature map, θ 1 , θ 2 ∈ R d are unknown ground truth parameters for the rewards, and z 1 , z 2 are random noise which we assume are mean-zero and
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 4: Construct approximate best response sets and values for all a ∈ A: 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 Such a core set is guaranteed to exist for any finite Φ [24, Theorem 4.4], and can be found efficiently in O(ABd 2 ) 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 − δ: Sample complexity; computation Theorem 5 shows that Algorithm 3 achieves O(d 2 /ε 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.

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 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.
[24] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR, 2020.
[26] Joshua Letchford and Vincent Conitzer. Computing optimal strategies to commit to in extensiveform games. In Proceedings of the 11th ACM conference on Electronic commerce, pages 83-92, 2010.
A Results with optimistic tie-breaking In this section, we present alternative versions of our main results where the Stackelberg equilibrium is defined via optimistic tie-breaking.

A.1 Bandit games
The setting is exactly the same as in Section 3, except that now we consider optimistic versions of the φ-functions that take the max over best-response sets (henceforth the ψ-functions): for all ε ≥ 0. Notice that now ψ ε ≥ ψ 0 , and we consider the following new definition of gap: Our desired optimality guarantee is We now state our sample complexity upper bound for learning Stackelberg in bandit games under optimistic tie-breaking. The proof can be found in Section F.1.
Theorem A.1 (Bandit games with optimistic tie-breaking). For the two-player bandit game and any ε ∈ (0, 1), Algorithm 4 outputs ( a, b) such that with probability at least 1 − δ, Intuitions about new gap We provide some intuitions about why-in contrast to the gap ε defined in Section 3-our sample complexity depends on this newly defined gap ε here. Observe that, gap ε measures the max gap between ψ ε (a) − ψ 0 (a), over all possible a's whose ψ ε can compete with Let the leader pull arm a ∈ A and the follower run the Reward-Free RL-Explore algorithm for N episodes, and obtain model estimate 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 by subroutine ( π b,(a) , ψ 3ε/4 (a)) ← BestCaseBestResponse( M a , V 2 (a) − 3ε/4). 6: end for output ( a, π b ), where a ← arg max a∈A ψ 3ε/4 (a) and π b ← π b,( a) . the best ψ 0 . For any of these a's, statistically (if we only have O(AB/ε 2 ) samples), the best response set BR ε (a) is indistinguishable from BR 0 (a), and we may well pick these a's as the Stackelberg equilibrium. However, their true ψ 0 can be (much) lower than the ψ ε , and thus picking one of these a's we may have to suffer from the so-defined gap ε in the worst case.

A.2 Bandit-RL games
The setting is exactly the same as in Section 4, except the definition of the ψ-functions takes the max over best-response sets: for all ε ≥ 0. Similar as in Section A.1, we consider the following new definition of gap: We now state our sample complexity upper bound for learning Stackelberg in bandit-RL games under optimistic tie-breaking. The proof is analogous to Theorem 4, and can be found in Section F.2.

B Matrix game with simultaneous play
In this section, we consider a variant of the two-player bandit game, in which the leader and follower instead play a matrix game simultaneously, and the follower cannot see the leader's action. The problem of finding Stackelberg in this setting is also known as learning the "optimal strategy to commit to" [13].
Setting A general-sum matrix game with simultaneous play can be described as M = (A, B, r 1 , r 2 ) with |A| = A, |B| = B, and r 1 , r 2 : A × B → [0, 1], which defines the following game: • The leader pre-specifies a policy π a ∈ ∆ A and reveals this policy to the follower.
• The leader plays a ∼ π a , and the follower plays an action b ∈ B simultaneously without seeing a.
• The leader receives reward r 1 (a, b) and the follows receives reward r 2 (a, b).
(Above, ∆ A denotes the probability simplex on A.) Let µ i (π a , b) = a ∈A π a (a )E[r i (a , b)], i = 1, 2 denote the mean rewards (for mixed policies), and φ ε (π a ) := min b∈BRε(π a ) µ 1 (π a , b), denote the ε-approximate best response sets and best response values for any ε ≥ 0, similar as in bandit games. We also overload notation to let φ ε (a 1 ) := φ ε (δ a 1 ) to denote the φ ε value at pure strategies (δ a is the pure strategy of always taking a).
The main difference between this setting and bandit games is that now the Stackelberg equilibrium for the leader may be achieved at mixed strategies only, so that we can no longer restrict attention to pure strategies a ∈ A for the leader. To see why this is true, consider 2x2 game of [13] shown in Table 1. In this game, the two pure strategies {a 1 , a 2 } achieve φ 0 (a 1 ) = 2 (since the best response is b 1 ) and φ 0 (a 2 ) = 3 (since the best response is b 2 ). However, if we take π a p = pδ a 1 + (1 − p)δ a 2 , then the follower's best response is b 2 whenever p < 1/2. Taking p → (1/2) − , the leader can achieve value φ 0 (π a p ) = 4p + 3(1 − p) → 3.5, which is higher than both pure strategies. For p ≥ 1/2, the follower's best response is b 1 , and φ 0 (π a p ) ≤ 2. Therefore the Stackelberg equilibrium for the leader is to take π a p with p → (1/2) − 4 .

B.1 Main result
Let gap ε := sup π a ∈∆ A φ 0 (π a ) − sup π a ∈∆ A φ ε (π a ) denote the gap. The following result shows that O(AB/ε 2 ) samples suffice for learning the Stackelberg up to (gap ε + ε) in simultaneous matrix games, similar as in bandit games. The proof can be found in Appendix G.1.

1: Query each (a, b) ∈ A × B for N times and obtain {r
i (a , b) for i = 1, 2. 3: Construct approximate best response sets and values for all π a ∈ ∆ A : Theorem B.1 (Learning Stackelberg in simultaneous matrix games). For any matrix game with simultaneous play, Algorithm 6 queries for n = O(AB log(AB/δ)/ε 2 ) = O(AB/ε 2 ) samples, and outputs ( π a , b) such that with probability at least 1 − δ, which studied the sample complexity assuming a best response oracle (can query BR 0 (π a ) for any π a ∈ ∆ A ).

Comparison between learning Stackelberg and Nash
We compare Theorem B.1 with existing results on learning Nash equilibria in general-sum matrix games. On the one hand, when we have O(AB/ε 2 ) samples, with only a (gap ε + ε) near-optimal Stackelberg equilibrium, but we can learn an ε-approximate Nash equilibrium [28]. On the other hand, the Stackelberg value is uniquely defined (as the max of φ 0 ), whereas there can be multiple Nash values [38] for general-sum games. Additionally, at the Stackelberg equilibrium, the leader's payoff is guaranteed to be at least as good as any Nash value (the leader can pre-specify any Nash policy). This makes Stackelberg a perhaps better solution concept in asymmetric games where the learning goal focuses more on the leader.
Runtime In Algorithm 6, the step of approximately maximizing φ 3ε/4 (π a ) in (13) requires optimizing a discontinuous function over a continuous domain. It is unclear whether this program can be reformulated to be solved efficiently in polynomial time 56 . However, we remark that this is special to the pessimistic tie-breaking we assumed [27]. Learning the Stackelberg equilibrium with optimistic tie-breaking has the same O(AB/ε 2 ) sample complexity while admitting an efficient polynomial-time algorithm via linear programming (see Section B.2 for the formal statement and proof).

B.2 Optimistic tie-breaking
We also study simultaneous matrix games with optimistic tie-breaking. The setting is exactly the same as above except the definition of the ψ-functions takes the max over best-response sets: for all ε ≥ 0. Similar as in bandit games (Section A.1), we consider the following new definition of gap: Theorem B.2 (Learning Stackelberg in simultaneous matrix games with optimistic tie-breaking).
For any matrix game with simultaneous play, Algorithm 7 queries for n = O(AB log(AB/δ)/ε 2 ) = O(AB/ε 2 ) samples, and outputs ( π a , b) such that with probability at least 1 − δ, Further, the algorithm runs in poly(n) time.
The proof can be found in Section G.2.
Efficient runtime Theorem B.2 shares the same sample complexity O(AB/ε 2 ) as its pessimistic tie-breaking counterpart (Theorem B.1), albeit with a slightly different definition of the gap. However, an additional advantage of the optimistic version is that it is guaranteed to have a polynomial runtime. The core reason behind this is that with optimistic tie-breaking now ( π a , b) solves a maxmax problem (instead of a max-min problem), for which we can exchange the order of maximization. Concretely, we can now first maximize over π a for each b, which admits a linear programming formulation (cf. the BestMixedLeaderStrategy subroutine in Algorithm 10, also in [13]).
1: Query each (a, b) ∈ A × B for N times and obtain {r (a , b) for i = 1, 2. 3: Construct approximate best response sets and values for all π a ∈ ∆ A : µ 1 (π a , b).

C Proofs for Section 3 C.1 Proof of Theorem 1
To prove Theorem 1, we will construct a pair of hard instances, and use Le Cam's method [49, Section 15.2] to reduce the estimation error into a testing problem between the two hard instances. Consider the following two games M 1 and M −1 , where the rewards follow Bernoulli distributions: r i (a, b) ∼ Ber(µ i (a, b)) with means shown in Table 2, where δ ∈ (0, 1) is a parameter to be determined:  1 (a, b), Based on Table 2, it is straightforward to check that φ M 1 0 (a 1 ) = 1, φ For any algorithm that outputs a (possibly randomized) estimator a ∈ A of the Stackelberg equilibrium, let π denotes its querying policy, that is, given prior queries and observations ) denotes the distribution of the next query. Let P M 1 ,π and P M −1 ,π denote the distribution of all n observations generated by the querying policy π. For these two instances, we have where the second-to-last step used Le Cam's inequality, and the last step used Pinsker's inequality.
Choosing δ = 1/ (27/2)n, the above is upper bounded by 2/9, and thus plugging back to the preceding bound yields Therefore, choosing the problem class to be M n = {M 1 , M −1 } with δ = 1/ (27/2)n, the above is the desired lower bound.
Near-optimality of a On the one hand, because a maximizes µ 1 (a, b(a)), we have for any a ∈ A that where (i) is because b minimizes µ 1 ( a, ·) within BR 3ε/4 ( a), and (ii) is because b(a) ∈ BR 3ε/4 (a) ⊆ BR ε (a). By the uniform convergence (22), we get that Since the above holds for all a ∈ A, taking the max on the right hand side gives where (i) is because BR 3ε/4 ( a) ⊇ BR ε/2 (a). This yields that which is the first part of the bound for a.
On the other hand, since φ ε (a) is increasing as we decrease ε, we directly have This is the second part of the bound for a.
Construction of hard instance In our construction below, the rewards follow Bernoulli distributions: r i (a, b) ∼ Ber (µ i (a, b)), so that it suffices to specify µ i (a, b). Without loss of generality assume B/3 is an integer, and let B = [B] = {1, . . . , B} for notational simplicity.
For this game, we have φ 0 (a ) = 1/2 + g + ε, φ ε (a ) = 1/2 + ε, and φ 0 (a ) = φ ε (a ) = 1/2 for all a = a . Therefore, Further, notice that as long as a = a , we have φ 0 ( a) = max a φ 0 (a) − (g + ε). Proof of lower bound Under the mixture P M , we have We now show that ( ) ≤ 1/3 if N ≤ c[AB/ε 2 ] for some small absolute constant c > 0. Using the divergence decomposition (16), we have Above, (i) used the fact that for the null game M 0 and the game M a ,b 1 ,b 2 , only the actions (a , b 1 ) and (a , b 2 ) will lead to different observation distributions. (ii) used the fact that r 2 (a , b 1 ) has mean 1/2 + 2ε under M a ,b 1 ,b 2 and mean 1/2 under M 0 (and the other Bernoulli means correspondingly), and the fact that r 1 (a, b) are equally distributed in the two games and thus do not contribute to the KL, and finally the KL bound (17) for small enough ε such that 2ε < 1/2 √ 2. (iii) used the power mean inequality and the equality a ,b T a ,b (N ) = N for any algorithm.
The above implies that, as long as ε < 1/4 √ 2 and g ≤ 1/4, for N ≤ AB/(864ε 2 ), we have ( ) ≤ 1/3, and thus Therefore there must exist a game M a ,b 1 ,b 2 on which the error probability is at least 1/3. This is the desired lower bound.

C.5 Equivalence to turn-based Markov game
We consider the following general-sum turn-based Markov game 7 with two steps and state space S = {s a : a ∈ A}: • (h = 1) Leader receives deterministic initial state s 1 and plays action a ∈ A. No reward for both players.
• (h = 2) The game transits deterministically to s a . The follower plays action b ∈ B and observes reward r 2 (s a , b) = r 2 (a, b). The leader observes reward r 1 (s a , b) = r 1 (a, b).
• The game terminates.
It is straightforward to see that the bandit game M = (A, B, r 1 , r 2 ) is equivalent to the above turn-based Markov game. Note that the Markov game has |S| = A states. Now, let a be the leader's exact Stackelberg equilibrium (as defined in (3)). For any a, let b (a) = arg min b∈BR 0 (a) µ 1 (a, b) be the best response of a with the worst µ 1 . Define the deterministic follower policy π b as π b (s a ) = b (a) for all s a ∈ S.
We claim that (a , π b ) is a Nash equilibrium of the above Markov game. Indeed, π b is clearly a 's best response on the follower's reward. Also, if we fix π b , then a is also the leader's best response to π b , as we have and thus the leader's best response is exactly the argmax of φ 0 (a), i.e. a .

C.6 Additional discussions on the gap
Here we show that for bandit games, gap ε is small for two special kinds of games: zero-sum games and cooperative games.
Zero-sum games Here r 1 ≡ −r 2 and thus µ 1 ≡ −µ 2 . In such games, by definition we have Notice that now the minimum over b ∈ BR ε (a) is always taken at the exact minimizer of b → µ 1 (a, b). Therefore we have φ ε (a) = min b∈B µ 1 (a, b) does not depend on ε, and thus gap ε = max a∈A φ 0 (a) − max a∈A φ ε (a) = 0.
Cooperative games Here r 1 ≡ r 2 and thus µ 1 ≡ µ 2 . In such games, by definition we have Thus for each a ∈ A, the difference between µ 1 (a, b) for any b ∈ BR 0 (a) and any b ∈ BR ε (a) is at most ε. This shows that φ 0 (a) − φ ε (a) ≤ ε for all a ∈ A and thus gap ε ≤ ε.

D Proofs for Section 4 D.1 Subroutine WorstCaseBestResponse
We describe the WorstCaseBestResponse subroutine in Algorithm 8.
Above, ∆ B denotes the probability simplex on B (which is a set of B + 1 linear constraints). Let d h denote the solution and V 1 denote the value of the above program.

D.2 Proof of Theorem 4
Correctness of subroutine We first show that the WorstCaseBestResponse subroutine (Algorithm 8) with input ( M a , V 2 (a) − 3ε/4) indeed solves the nominal problem (7). To see this, observe that in the nominal problem (7), both the objective function and the constraint are linear functions of the visitation distribution P π b h (s, b) induced by π b . Therefore, maximizing over all visitation distributions is equivalent to maximizing over all π b . To ensure that a general {d h (s, b)} h,s,b is a visitation distribution, it suffices for it to satisfy the constraints d 1 (s 1 , ·) ∈ ∆ B , d 1 (s 1 , ·) = 0 for s 1 = s 1 , and at each h ≥ 2 and each state s the in-flow is equal to the out-flow, meaning that for all h ≥ 1, s ∈ S. These are exactly the constraints specified in the linear program (18). Finally, for a visitation distribution d h , notice that π b h (b|s) = d h (s, b)/ b∈S d h (s, b) (with the convention 0/0 = 1/B) defines a policy π b whose visitation distribution is exactly d h . This shows that the linear program (18) is indeed a correct algorithm for solving (7).
Properties of reward-free exploration For each a ∈ A, Algorithm 2 played the Reward-Free RL-Explore algorithm of Jin et al. [18] for N = O(H 5 S 2 B/ε 2 + H 7 S 4 B/ε) episodes and obtained an estimate of the transition dynamics P a . (More specifically, it ran N 0 = O(H 7 S 4 B/ε) episodes in its exploration phase and N data = O(H 5 S 2 B/ε 2 ) episodes in its data-gathering phase.) Further, let { r 1,h (a, s, b), r 2,h (a, s, b)} denote the empirical mean of the observed rewards in the data-gathering phase.
Let V 1 (a, π b ) and V 2 (a, π b ) denote the value functions of the empirical MDPs (P a , r 1 ) and (P a , r 2 ) (note that these MDPs combine the true models and the empirical rewards). With our choice N , by [18,Theorem 3.1], we have with probability at least 1 − δ that We now argue that the Reward-Free RL-Explore algorithm can correctly estimate the rewards, along with estimating transitions. Indeed, we have the following Lemma D.1. Suppose we run the Reward-Free RL-Explore algorithm where the data gathering phase contains N data ≥ O(H 3 S 2 B/ε 2 ) trajectories, and we in addition receive (stochastic) reward signals r 1,h , r 2,h along the trajectories. Then with probability at least 1 − δ, the empirical reward estimates r 1,h , r 2,h and the associated value functions V 1 and V 2 satisfy that We defer the proof of Lemma D.1 to Appendix D.3. As we have N data = O(H 5 S 2 B/ε 2 ), we can apply Lemma 6 and get (by choosing a large absolute constant in the choice of N data ) that Combining (19) and (20) (and noticing those are true for all a ∈ A), we get Guarantees on BR 3ε/4 (a) Now, for any a ∈ A, recall Algorithm 2 constructed the empirical best-response set (cf. (7)) We claim that BR ε (a) ⊇ BR 3ε/4 (a) ⊇ BR ε/2 (a) for all a ∈ A.
Indeed, fixing any a ∈ A, let π denote the optimal policy for V 2 (a, ·) and π denote the optimal policy for V 2 (a, ·) (dropping dependence on a for notational simplicity). Suppose π b ∈ BR 3ε/4 (a), then we have This shows that BR 3ε/4 (a) ⊆ BR ε (a). Notably, this implies that the output π b ∈ BR ε ( a), the desired optimality guarantee for π b .
Similar as above, take any π b ∈ BR ε/2 (a), we have This shows that BR ε/2 (a) ⊆ BR 3ε/4 (a), the other part of the claim.
Stackelberg guarantee for a Finally, we show the Stackelberg guarantee for a. This part is similar as in the proof of Theorem 2. First, because a maximizes φ 3ε/4 (a) = min π b ∈ BR 3ε/4 (a) V 1 (a, π b ), we have for any a ∈ A that min where (i) is because BR 3ε/4 (a) ⊆ BR ε (a) for all a. By the uniform convergence (21), we get min Since the above holds for all a ∈ A, taking the max on the right hand side gives where (i) is because BR 3ε/4 ( a) ⊇ BR ε/2 (a). In other words, we have This is the first part of the bound for a.
On the other hand, since φ ε (a) is increasing as we decrease ε, we directly have This is the second part of the bound for a.

D.3 Proof of Lemma D.1
We consider estimating a single reward r h = r 1,h . The bound for two rewards can be obtained by setting δ → δ/2 and applying a union bound. Consider the MDP M a which consists of S states, B actions, and H steps. Let V (a, π b ; r) denote the value function using the true MDP, policy π b and reward function r, and V (a, π b ; r) denote the value function using the estimated reward r. Further, let S δ h := s : max denote the set of δ-significant states. By [18], the data gathering phase of Reward-Free RL-Explore obtains data where the h-th step is sampled i.i.d. from some policy µ h , such that for any s ∈ S δ h we have We have for any π b that For any h, by the Cauchy-Schwarz inequality, we have Above, (i) used the fact that P π b h (s)1 {b = ν(s)} ≤ 2SBH · µ h (s, b) as π b h h ≤h−1 ∪ {ν} is a valid policy. (ii) used the Hoeffding inequality (and a union bound) for the reward estimates, and the fact that the visitation of the reward-free algorithm is independent of the observed reward. (iii) used the multiplicative Chernoff bound for the visitation count N h (s, b) ∼ Bin (N, µ h (s, b)) and a union bound over (s, b), which requires N ≥ O (1/ min s,b µ h (s, b)). Recall that Reward-Free RL-Explore used Further, plugging in the choice of N (with a sufficiently large constant) into the above bound yields

This further implies that
the desired result.

E Proofs for Section 5 E.1 Proof of Theorem 5
First by the guarantee (10) for the CoreSet subroutine, we have K = |K| ≤ 4d log log d + 16. At each j ∈ [K] and associated (a j , b j ) ∈ K, as we queried the rewards for N times, the empirical means satisfy (letting φ j := φ(a j , b j ) for shorthand) µ i,j = φ j θ i + z i,j , i = 1, 2, where z i,j is the empirical mean of N i.i.d. 1-sub-Gaussian noises, and thus is 1/N -sub-Gaussian. Therefore, the weighted least squares estimator (9) can be expressed as (letting ρ j := ρ(a j , b j ) for shorthand) This implies the following guarantee (recall Φ = {φ(a, b) : (a, b) ∈ A × B}): Above, (i) uses Jensen's inequality (over the distribution induced by ρ j ), and (ii) used the property (10) of the core set. Now, as z i,j is 1/N -sub-Gaussian, with probability at least 1 − δ, we have Substituting this into the preceding bound yields Choosing N = Cd log(d/δ)/ε 2 guarantees that max φ∈Φ φ ( θ i − θ i ) ≤ ε/8. When this happens, we have for any (a, b) ∈ A × B and any i = 1, 2 that the estimated mean reward is close to the true reward: φ(a, b) θ i − φ(a, b) θ i ≤ ε/8.
We can then proceed analogously to the proof of Theorem 2 to conclude that the output ( a, b) satisfies φ 0 ( a) ≥ φ ε/2 ( a) ≥ max a∈A φ 0 (a) − gap ε − ε and b ∈ BR ε ( a). Further, notice that the total amount of queries is This proves Theorem 5.

E.2 Lower bound
We present a Ω(d/ε 2 ) lower bound for linear bandit games. This shows that the sample complexity upper bound in our Theorem 5 has at most an O(d) factor from the lower bound.
Theorem E.1 (Lower bound for linear bandit games). There exists an absolute constant c > 0 such that the following holds. For any ε ∈ (0, c), g ∈ [0, c), and any algorithm that queries n ≤ c[d/ε 2 ] samples and outputs an estimate a ∈ A, there exists a linear bandit game M with feature dimension d, on which gap ε = g and the algorithm suffers from (g + ε) error: Proof. This lower bound is a direct corollary of the Ω(AB/ε 2 ) lower bound in Theorem 3. Specifically, we can pick the size of the action spaces A , B so that d/2 ≤ A B ≤ d, and take φ(a, b) = 1 a,b ∈ R d where 1 a,b is the standard basis vector with one at index (a, b) (this index is understood as an index in [d]). This family of linear bandit games is equivalent to the family of bandit games with A B ≥ d/2, for which any algorithm has to suffer from at least (g + ε ε ) error if the number of queries n ≤ cd/ε 2 ≤ cA B /ε 2 by (the hard instance construction of) Theorem 3. This proves Theorem E.1.
Since the above holds for all a ∈ A, taking the max on the right hand side gives Solve the following linear program over π a ∈ ∆ A : Let π a (b), u(b) denote the solution and the value at the solution respectively. 4: end for 5: Output b = arg max b∈B u(b) and π a = π a ( b). where e b ∈ ∆ B denotes the standard basis vector in B (1 at b and 0 at b = b). For each b, the above problem is exactly the same as the linear program (25). Then, the above problem requires maximizing the value over b ∈ B, which is done in the output step of Algorithm 10. This shows that the BestMixedLeaderStrategy subroutine (Algorithm 10) is correct for solving (14). Note this also proves that the arg max in (14) is attainable (instead of the sup in Theorem B.1 which may not be attainable in general).
The rest of the proof is analogous to Theorem B.1 where we can again establish the uniform convergence (24) and obtain the suboptimality guarantee in terms of ψ and gap ε instead of φ and gap ε , similar as in Theorem A.1.