Year: 2021

Abstract:
We study multi-player general-sum Markov games with one of the players designated as the leader and the rest regarded as the followers. In particular, we focus on the class of games where the state transitions are only determined by the leader’s action while the actions of all the players determine their immediate rewards. For such a game, our goal is to find the Stackelberg-Nash equilibrium (SNE), which is a policy pair (π∗, ν∗) such that (i) π∗ is the optimal policy for the leader when the followers always play their best response, and (ii) ν∗ is the best response policy of the followers, which is a Nash equilibrium of the followers’ game induced by π∗. We develop sample efficient reinforcement learning (RL) algorithms for solving SNE for both the online and offline settings. Respectively, our algorithms are optimistic and pessimistic variants of least-squares value iteration and are readily able to incorporate function approximation for handling large state spaces. Furthermore, for the case with linear function approximation, we prove that our algorithms achieve sublinear regret and suboptimality under online and offline setups respectively. To our best knowledge, we establish the first provably efficient RL algorithms for solving SNE in general-sum Markov games with leader-controlled state transitions.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has achieved striking empirical successes in solving complicated realworld sequential decision-making problems (Mnih et al., 2015; Duan et al., 2016; Silver et al., 2016; 2017; 2018; Agostinelli et al., 2019; Akkaya et al., 2019). Motivated by these successes, multi-agent extensions of RL algorithms recently have gained great popularity in decision-making problems involving multiple interacting agents (Busoniu et al., 2008; Hernandez-Leal et al., 2018; 2019; OroojlooyJadid & Hajinezhad, 2019; Zhang et al., 2019). Multi-agent RL is often modeled as a Markov game (Littman, 1994) where, at each time step, each player (agent) takes an action simultaneously at each state of the environment, observe her own immediate reward, and the environment evolves into a next state. Here both the reward of each player and the state transition depends on the actions of all players. From the perspective of each player, her goal is to find a policy that maximizes her expected total reward in the presence of other agents.
In Markov games, depending on the structure of the reward functions, the relationship among the players can be either collaborative, where each player has the same reward function, or competitive, where the sum of the reward function is equal to zero, or mixed, which corresponds to a general-sum game. While most of existing theoretical results focus on the collaborative or two-player competitive settings, the mixed setting is oftentimes more pertinent to real-world multi-agent applications.
Moreover, in addition to having diverse reward functions, the players might also have asymmetric roles in the Markov game — the players might be divided into leaders and followers, where the leaders’ joint policy determines a general-sum game for the followers. Games with such a leaderfollower structure is popular in applications such as mechanism design (Conitzer & Sandholm, 2002; Roughgarden, 2004; Garg & Narahari, 2005; Kang & Wu, 2014), security games (Tambe, 2011; Korzhyk et al., 2011; Balcan et al., 2015), incentive design (Zheng et al., 1984; Ratliff et al., 2014; Chen et al., 2016; Ratliff & Fiez, 2020), and model-based RL (Rajeswaran et al., 2020). Consider a simplified economic system that consists of a government and a group of companies, where the
companies purchase or sell goods, and the government collects taxes from transactions. Such a problem can be viewed as a multi-player general-sum game, where the government serves as the leader and the companies are followers (Zheng et al., 2020). In particular, when the government sets a tax rate, the companies form a general-sum game themselves, whose reward functions depend on the tax rate. Each company aims to maximize their own revenue, and thus ideally they achieve a Nash equilibrium (NE) of the induced game. Whereas the goal of the government might be achieving the social welfare, which might be measured via certain fairness metrics computed by the revenues of the companies.
In multi-player Markov games with such a leader-follower structure, the desired solution concept is the Stackelberg-Nash equilibrium (SNE) (Başar & Olsder, 1998). In the setting where there is a single leader, SNE corresponds to a pair of leader’s policy π∗ and followers’ joint policy ν∗ that satisfies the following two properties: (i) when the leader adopts π∗, ν∗ is the best-response policy of the followers, i.e., ν∗ is a Nash equilibrium of the followers’ subgame induced by π∗; and (ii) π∗ is the optimal policy of the leader assuming the followers always adopt the best response.
We are interested in finding an SNE in a multi-player Markov game when the reward functions and Markov transition kernel are unknown. In particular, we focus on the setting with a single leader and the state transitions only depend on the leader’s actions. That is, the followers’ actions only affect the rewards received by the leader and followers. For such a game, we are interested in the following question: Can we develop reinforcement learning methods that provably find Stackelberg-Nash equilibria in leader-controlled general-sum games with sample efficiency? To this end, we consider both online and offline RL settings, where in the former, we learn the SNE in a trial-an-error fashion by interacting with the environment and generating data, and in the latter, we learn the SNE from a given dataset that is collected a priori. For the online setting, as the transition model is unknown, to achieve sample efficiency, the equilibrium-finding algorithm also needs to take the exploration-exploitation tradeoff into consideration. Although the similar challenge has been studied in zero-sum Markov game, it seems unclear how to incorporate popular exploration mechanisms such as optimism in the face of uncertainty (Sutton & Barto, 2018) into SNE finding. Meanwhile, under the offline setting, as the RL agent has no control of data collection, it is ideal to design an RL algorithm with theoretical guarantees for an arbitrary dataset that might not be sufficiently explorative.
Our contributions Our contributions are three-fold. First, for the episodic leader-controlled general-sum game, under the online and offline settings respectively, we propose optimistic and pessimistic variants of the least-squares value iteration (LSVI) algorithm. In particular, in a version of LSVI, we estimate the optimal action-value function of the leader via least-squares regression and construct an estimate of the SNE by solving the SNE of the multi-matrix game for each state, whose payoff matrices are given by the leader’s estimated action-value function and the followers’ reward functions. Moreover, we add a UCB exploration bonus to the least-squares solution to achieve optimism in the online setting. Whereas in the offline setting, pessimism is achieved by subtracting a penalty function constructed using the offline data, which is equal to the negative bonus function. Moreover, these algorithms are readily able to incorporate function approximators and we showcase the version with linear function approximation. Second, under the online setting, we prove that our optimistic LSVI algorithm achieves a sublinear Õ(H2 √ d3K) regret, where K is the number of
episodes, H is the horizon, d is the dimension of the feature mapping, and Õ(·) omits logarithmic terms. Finally, under the offline setting, we establish an upper bound on the suboptimality of the proposed algorithm for an arbitrary dataset with K trajectories. Our upper bound yields a sublinear Õ(H2 √ d3/K) rate as long as the dataset has sufficient coverage over the trajectory induced by the desired SNE.
Related work In the sequel, we discuss the related works on learning Stackelberg games. We defer more related works on RL for solving NE in Markov games and single-agent RL to §A. Learning Stackelberg games As for solving Stackelberg-Nash equilibrium, most of the existing results focus on the normal form game, which is equivalent to our Markov game with H = 1. Letchford et al. (2009); Blum et al. (2014); Peng et al. (2019) study learning Stackelberg equilibrium with a best response oracle. In addition, Fiez et al. (2019) study the local convergence of firstorder methods for finding Stackelberg equilibria in general-sum games with differentiable reward functions, and Ghadimi & Wang (2018); Chen et al. (2021a); Hong et al. (2020) analyze the global convergence of first-order methods for achieving global optimality of bilevel optimization. A more
related work is Bai et al. (2021), which studies the matrix Stackelberg game with bandit feedback. This work also studies an RL extension where the leader has a finite action set and the follower is faced with an MDP specified by the leader’s action. In comparison, we assume the leader knows the reward functions and the main challenge lies in the unknown and leader-controlled transitions. Thus, our setting is different from that in Bai et al. (2021). Furthermore, a more relevant work is (Bucarey et al., 2019b), which establishes the Bellman equation and value iteration algorithm for solving SNE in leader-controlled Markov games. In comparison, we establish modifications of least-squares value iteration that are tailored to online and offline settings.
Notation See §B for details.

heading: 2 PRELIMINARIES
text: In this section, we introduce the formulation of the general-sum simultaneous-move Markov games, Stackelberg-Nash equilibrium, and the linear structure we use in this paper.

heading: 2.1 GENERAL-SUM SIMULTANEOUS-MOVE MARKOV GAMES
text: In this setting, two levels of hierarchy in decision making are considered: one leader l and N followers {fi}i∈[N ]. Specifically, we define an episodic version of general-sum simultaneousmoves Markov game by the tuple (S,Al,Af = {Afi}i∈[N ], H, rl, rf = {rfi}i∈[N ],P), where S is the state space, Al and Af are the sets of actions of the leader and the followers respectively, H is the number of steps in each episode, rl = {rl,h : S × Al × Af → [−1, 1]}Hh=1 and rfi = {rfi,h : S × Al × Af → [−1, 1]}Hh=1 are reward functions of the leader and the followers respectively, and P = {Ph : S × Al × Af × S → [0, 1]}Hh=1 is a collection of transition kernels. Here Al ×Af = Al ×Af1 × · · · × AfN . Throughout this paper, we also let ? be some element in {l, f1, · · · , fN}. Moreover, for any (h, x, a) ∈ [H]× S ×Al and b = {bi ∈ Afi}i∈[N ], we use the shorthands r?,h(x, a, b) = r?,h(x, a, b1, · · · , bN ) and Ph(· |x, a, b) = Ph(· |x, a, b1, · · · , bN ).
Policy and Value Function. A stochastic policy π = {πh : S → ∆(Al)}Hh=1 of the leader is a set of probability distributions over actions given the state. Meanwhile, a stochastic joint policy of the followers is defined by ν = {νfi}i∈[N ], where νfi = {νfi,h : S → ∆(Afi)}Hh=1. We use the notation πh(a |x) and νfi,h(bi |x) to denote the probability of taking action a ∈ Al or bi ∈ Afi for state x at step h under policy π, νfi respectively. Throughout this paper, for any ν = {νfi}i∈[N ] and b = {bi}i∈[N ], we use the shorthand νh(b |x) = νf1,h(b1 |x)× · · · × νfN ,h(bN |x).
Given policies (π, ν = {νfi}i∈[N ]), the action-value (Q) and state-value (V) functions for the leader and followers are defined by
Qπ,ν?,h(x, a, b) = Eπ,ν,h,x,a,b [ H∑ t=h r?,h(xt, at, bt) ] , V π,ν?,h (x) = Ea∼πh(· | x),b∼νh(· | x)Q π,ν ?,h(x, a, b), (2.1)
where the expectation Eπ,ν,h,x,a,b is taken over state-action pairs induced by the policies (π, ν = {νfi}i∈[N ]) and the transition probability, when initializing the process with the triplet (s, a, b = {bi}i∈[N ]) at step h. For notational simplicity, when h, x, a, b are clear from the context, we omit h, x, a, b from Eπ,ν,h,x,a,b. By the definition in (2.1), we have the Bellman equation
V π,ν?,h = 〈Q π,ν ?,h , πh × νh〉Al×Af , Q π,ν ?,h = r?,h + PhV π,ν ?,h+1, ∀? ∈ {l, f1, · · · , fN}, (2.2)
where πh × νh represents πh × νf1,h × · · · × νfN ,h. Here Ph is the operator which is defined by (Phf)(x, a, b) = E[f(x′) |x′ ∼ Ph(x′ |x, a, b)] (2.3)
for any function f : S → R and (x, a, b) ∈ S ×Al ×Af .

heading: 2.2 STACKELBERG-NASH EQUILIBRIUM
text: Given a leader policy π, a Nash equilibrium (Nash, 2016) of the followers is a joint policy ν∗ = {ν∗fi}i∈[N ], such that for any x ∈ S and (i, h) ∈ [N ]× [H]
V π,ν ∗
fi,h (x) ≥ V
π,νfi ,ν ∗ f−i
fi,h (x), ∀νfi . (2.4)
Here −i represents all indices in [N ] except i. For each leader policy π, we denote the set of bestresponse policies of the followers by BR(π), which is defined by
BR(π) = {ν = {νfi}i∈[N ] | ν is the NE of the followers given the leader policy π}. (2.5)
Given the best-response set BR(π), we denote ν∗(π) the worst-case responses, which break ties against favor of the leader 1. Specifically, we define ν∗(π) by
ν∗(π) = {ν ∈ BR(π) |V π,νl,h (x) ≤ V π,ν′ l,h (x),∀x ∈ S, h ∈ [H], ν ′ ∈ BR(π)}. (2.6)
The Stackelberg-Nash equilibrium for the leader is the “best response to the best response”, that is,
SNEl = {π |V π,ν ∗(π) l,h (x) ≥ V π′,ν∗(π′) l,h (x),∀x ∈ S, h ∈ [H], π ′} (2.7)
A Stackelberg-Nash equilibrium of the general-sum game is a policy pair (π∗, ν∗ = {ν∗fi}i∈[N ]) such that ν∗ ∈ ν∗(π∗) and π∗ ∈ SNEl. Our goal is to find the Stackelberg equilibrium: the leader’s optimal strategy, assuming the followers play their best response (Nash equilibrium) to the leader. We study this challenging bilevel optimization problem in both the online setting (Section 3) and the offline setting (Section 4).

heading: 2.3 LEADER-CONTROLLER LINEAR MARKOV GAMES
text: Inspired by the linear MDP studied in Jin et al. (2020b) for the single-agent RL, we study the linear Markov games (Xie et al., 2020), where the transition dynamics are linear in a feature map. Specifically, there exists a feature map φ′ : S ×Al ×Af → Rd such that
Ph(· |x, a, b) = 〈φ′(x, a, b), µh(·)〉
for any (x, a, b) ∈ S × Al × Af and h ∈ [H]. Here µh = (µ(1)h , µ (2) h , · · · , µ (d) h ) are d unknown signed measures over S. Moreover, throughout this paper, we focus on the leader-controller game (Filar & Vrieze, 2012; Bucarey et al., 2019a), where the future state only depends on the current state and the leader’s action, that is,
Ph(· |x, a, b) = Ph(· |x, a)
for any (x, a, b) ∈ S ×Al×Af and h ∈ [H]. Hence, it is naturally to define leader-controller linear Markov games as follows.
Assumption 2.1. Markov game (S,Al,Af = {Afi}i∈[N ], H, rl, rf = {rfi}i∈[N ],P) is a leadercontroller linear Markov game if there exists a feature map φ : S ×Al → Rd such that
Ph(· |x, a, b) = 〈φ(x, a), µh(·)〉
for any (x, a, b) ∈ S × Al × Af and h ∈ [H]. Here µh = (µ(1)h , µ (2) h , · · · , µ (d) h ) are d unknown
signed measures over S. Without loss of generality, we assume that ‖µh(S)‖ ≤ √ d for all h ∈ [H].
The linear Markov game above is an extension of linear MDP studied in Jin et al. (2020b) for the single-agent RL. Specifically, when the followers play fixed and known policies, the linear Markov games reduce to the linear MDP.

heading: 3 MAIN RESULTS FOR THE ONLINE SETTING
text: In this section, we study the online setting, where a central controller controls one leader l and N followers {fi}i∈[N ]. Our goal is to learn a Stackelberg-Nash equilibrium. In what follows, we formally describe the setup and learning objectives, and then present our algorithm and provide theoretic guarantees.
1This is also known as pessimistic tie breaking (Conitzer & Sandholm, 2006). We also remark that our subsequent analysis still holds for the optimistic setting (Breton et al., 1988; Bucarey et al., 2019a).

heading: 3.1 SETUP AND LEARNING OBJECTIVE
text: We consider the setting where the reward functions rl and rf = {rfi}i∈[N ] are revealed to the learner before the game. This is reasonable since in practice the reward functions are usually artificially designed. Moreover, we focus on the episodic setting. Specifically, a Markov game is played for K episodes, each of which consists ofH timesteps. At the beginning of the k-th episode, the leader and followers determine their policies (πk, νk = {νkfi}i∈[N ]), and a fixed initial state x k 1 = x1 is chosen. Here we assume the fixed initial state just for ease of presentation, and our subsequent results can be generalized to the setting where xk1 is picked from a fixed distribution. Then the game proceeds as follows. At each step h ∈ [H], the leader and the followers observe state xkh ∈ S and pick their own actions akh ∼ πkh(· |xkh) and bkh = {bki,h ∼ νkfi,h(· |x k h)}i∈[N ]. Subsequently, the environment transitions to the next state xkh+1 ∼ Ph(· |xkh, akh, bkh). Each episode terminates after H timesteps. Learning Objective. By the definition in (2.5), given a leader’s policy, the best response for the followers is the Nash equilibrium of followers’ game induced by this leader’s policy. Recall the definition of Nash equilibrium in (2.4), for any policies (π, ν = {νfi}i∈[N ]), it is natural to define the following objective to measure the suboptimality of νfi :
SubOptfi(x) = V π,ν∗(π) fi,1 (x)− V π,νfi ,ν ∗ −i(π) fi,1 (x).
Meanwhile, we evaluate the performance of the leader’s policy π by the following suboptimality gap:
SubOptl(x) = V π∗,ν∗ l,1 (x)− V π,ν∗(π) l,1 (x).
Putting these two suboptimality gaps together, we formally define the regret as follows. Definition 3.1 (Regret). Let (πk, νk = {νkfi}i∈[N ]) denote the policies executed by the algorithm in the k-th episode. After a total of K episodes, the regret is defined as Regret(K) = K∑ k=1 V π ∗,ν∗ l,1 (x k 1)− V πk,ν∗(πk) l,1 (x
k 1)︸ ︷︷ ︸
Regretl(K)
+ N∑ i=1 K∑ k=1 V πk,ν∗(πk) fi,1 (xk1)− V πk,νkfi ,ν∗f−i (πk)
fi,1 (xk1)︸ ︷︷ ︸
Regretf (K)
.
(3.1)
The goal is to design algorithms with regret that is sublinear in K, and polynomial in d,H . Here K is the number of episodes, d is the dimension of the feature map φ, and H is the episode horizon.

heading: 3.2 ALGORITHM
text: We now present our algorithm, Optimistic Value Iteration to Find Stackelberg-Nash Equilibrium (OVI-SNE), which is given in Algorithm 1.
At a high level, in each episode, our algorithm first construct the policies for all players through backward induction with respect to the timestep h (line 4-11), and then execute the policies to play the game (line 12-16).
In detail, at h-th step of k-th episode, OVI-SNE estimates leader’s Q-function based on the (k − 1) historical trajectories. Inspired by previous optimistic least square value iteration (LSVI) algorithms (Jin et al., 2020b), for any h ∈ [H], we estimate the linear coefficients by solving the following ridge regression problem:
wkh ← argmin w∈Rd k−1∑ τ=1 [V kh+1(x τ h+1)− φ(xτh, aτh)>w]2 + ‖w‖2,
where V kh+1(·) = 〈Qkh+1(·, ·, ·), πkh+1(· | ·)× νkh+1(· | ·)〉Al×Af .
(3.2)
By solving the ridge regression problem in (3.2), we have wkh = (Λ k h) −1 (k−1∑ τ=1 φ(xτh, a τ h) · V kh+1(xτh+1) ) ,
where Λkh = k−1∑ τ=1 φ(xτh, a τ h)φ(x τ h, a τ h) > + I.
(3.3)
To encourage exploration, we additionally adds a bonus function to estimate the leader’s Q-function:
Qkh(·, ·, ·)← rl,h(·, ·, ·) + ΠH−h{φ(·, ·)>wkh + Γkh(·, ·)}, where Γkh(·, ·) = β · √ φ(·, ·)>(Λkh)−1φ(·, ·).
(3.4)
Here Γkh : S × Al → R is a bonus function and β > 0 is a parameter which will be specified later. This form of bonus function is common in the literature of linear bandits (Lattimore & Szepesvári, 2020) and linear MDPs (Jin et al., 2020b).
Then, we construct policies for the leader and followers by the subroutine -SNE (Algorithm 2). Specifically, let Qkh be the class of functions Q : S ×Al ×Af → R that takes form
Q(·, ·, ·) = rl,h(·, ·, ·) + ΠH−h { φ(·, ·)>w + β · ( φ(·, ·)>Λ−1φ(·, ·) )1/2} , (3.5)
where the parameters (w,Λ) ∈ Rd × Rd×d satisfy ‖w‖ ≤ H √ dk and λmin(Λ) ≥ 1. Moreover, let Qkh, be a fixed -covering ofQkh with respect to the `∞ norm. By Lemma C.10, we have Qkh ∈ Qkh, which allows us to pick a Q̃ ∈ Qkh, such that ‖Q̃−Qkh‖∞ ≤ and calculate policies by
(πkh(· |x), {νkfi,h(· |x)}i∈[N ])← SNE(Q̃(x, ·, ·), {rfi,h(x, ·, ·)}i∈[N ]), ∀x. (3.6)
When there is only one follower, such a problem can be transformed to a linear programming (LP) problem (Conitzer & Sandholm, 2006; Von Stengel & Zamir, 2010), and thus can be solved efficiently. For the multi-follower case, however, solving such a matrix game in general is hard (Conitzer & Sandholm, 2006; Basilico et al., 2017a;b; Coniglio et al., 2020). Given this computational hardness, we focus on the sample complexity and explicitly assume access to the following computational oracle: Assumption 3.2. We assume access to an oracle that implements Line 3 of Algorithm 2 when there are multiple followers (i.e., N ≥ 2). Now we explain the motivation for using the subroutine -SNE to construct policies instead of solving the matrix games with payoff matrices (Qkh(x, ·, ·), {rfi,h(x, ·, ·)}i∈[N ]) directly. By the definition of Qkh in (3.4), we know Q k h relies on the previous data via the estimated value function V k h+1 and feature maps {φ(xτh, aτh, bτh)} k−1 τ=1. Similar to the analysis for linear MDPs (Jin et al., 2020b), we need to use a covering argument to establish uniform concentration bounds for all value V kh+1. Jin et al. (2020b) directly constructs an -net for the value functions and establishes a polynomial log-covering number for this -net. This analysis, however, relies on that the policies executed by the players are greedy (deterministic), which is not valid for our setting. To overcome this technical issue, we construct an -net for Q-functions and solve an approximate matrix game. Fortunately, by choosing a small enough , we can handle the errors caused by this approximation. See §C for more details. Moreover, as shown in Xie et al. (2020), this subroutine can be implemented efficiently without explicitly computing the exponentially large -net.
Finally, the leader and the followers play the game according to the obtained policies. 3.3 THEORETICAL RESULTS
Our main theoretical result is the following bound on the regret incurred by Algorithm 1. Recall that the regret is defined in Definition 3.1 and T = KH is the total number of timesteps. Theorem 3.3. Under Assumptions 2.1 and 3.2, there exists an absolute constant C > 0 such that, for any fixed p ∈ (0, 1), by setting β = C · dH √ ι with ι = log(2dT/p) in Line 7 of Algorithm 1 and = 1KH in Algorithm 2, then with probability at least 1 − p, the regret incurred by OVI-SNE satisfies that
Regret(K) ≤ O( √ d3H3Tι2).
Proof. See §C for a detailed proof.
Learning Stackelberg Equilibria. When there is only one follower, Stackelberg-Nash equilibrium reduces to the Stackelberg equilibrium (Simaan & Cruz, 1973; Conitzer & Sandholm, 2006; Bai et al., 2021). Thus, we partly answer the open problem in Bai et al. (2021) on how to learn Stackelberg equilibria in (leader-controller) Markov games.
Algorithm 1 Optimistic Value Iteration to Find Stackelberg-Nash Equilibria 1: Initialize Vl,H+1(·) = Vf,H+1(·) = 0. 2: for k = 1, 2, · · · ,K do 3: Receive initial state xk1 . 4: for step h = H,H − 1, · · · , 1 do 5: Λkh ← ∑k−1 τ=1 φ(x τ h, a τ h)φ(x τ h, a τ h) > + I .
6: wkh ← (Λkh)−1 ∑k−1 τ=1 φ(x τ h, a τ h) · V kh+1(xτh+1). 7: Γkh(·, ·)← β · (φ(·, ·)>(Λkh)−1φ(·, ·))1/2. 8: Qkh(·, ·, ·)← rl,h(·, ·, ·) + ΠH−h{φ(·, ·)>wkh + Γkh(·, ·)}. 9: (πkh(· |x), {νkfi,h(· |x)}i∈[N ])← -SNE(Q k h(x, ·, ·), {rfi,h(x, ·, ·)}i∈[N ]), ∀x. (Alg. 2)
10: V kh (x)← Ea∼πkh(· | x),b1∼νkf1,h(· | x),··· ,bN∼νkfN ,h(· | x)Q k h(x, a, b1, · · · , bN ), ∀x. 11: end for 12: for h = 1, 2, ·, H do 13: Sample akh ∼ πkh(· |xkh), bk1,h ∼ νkf1,h(· |x k h), · · · , bkN,h ∼ νkfN ,h(· |x k h). 14: Leader takes action akh; Followers take actions b k h = {bki,h}i∈[N ]. 15: Observe next state xkh+1. 16: end for 17: end for
Algorithm 2 -SNE 1: Input: Qkh, x, and parameter . 2: Select Q̃ from Qkh, satisfying ‖Q̃−Qkh‖∞ ≤ . 3: For the input state x, let (πkh(· |x), {νkfi,h(· |x)}i∈[N ]) be the Stackelberg-Nash equilibrium for
the matrix game with payoff matrices (Q̃(x, ·, ·), {rfi,h(x, ·, ·)}i∈[N ]). 4: Output: (πkh(· |x), {νkfi,h(· |x)}i∈[N ]).
Optimality of the Bound. Assuming that the action of the follower won’t affect the transition kernel and reward function, the linear Markov games reduces to the linear MDP (Jin et al., 2020b). Meanwhile, the lower bound established in Azar et al. (2017); Jin et al. (2018) for tabular MDPs and the lower bound established in Lattimore & Szepesvári (2020) for linear bandits directly imply a lower bound Ω(dH √ T ) for the linear MDPs, which further yields a lower bound Ω(dH √ T ) for our setting. Ignoring the logarithmic factors, there is only a gap of √ dH between this lower bound and our upper bound. We also point out that, by using the “Bernstein-type” bonus (Azar et al., 2017; Jin et al., 2018; Zhou et al., 2020), we can improve our upper bound by a factor of √ H . Here we don’t apply this technique for the clarity of the analysis.
Misspecification. For ease of presentation, we assume the Markov games are leader-controller in Assumption 2.1. When the transitions do not ideally satisfy the leader-controller assumption, we can potentially consider cases that transitions satisfy, for instance, |Ph(· |x, a, b) − Ph(· |x, a)‖∞ ≤ % for any (h, x, a, b) ∈ [H] × S × Al ×Af , Here % is the misspecification error. We can still follow the above method to tackle the misspecified cases. However, because of the misspecification error cumulated during T steps, an extra term O(%T ) will appear in the final result. In particular, When % is small, that is the Markov games have approximately leader-controller transitions, the extra term O(%T ) should be small, which further indicates that we can find SNEs efficiently in some misspecified general-sum Markov games.
Unknown Reward Setting. At a high level, we first conduct a reward-free exploration algorithm (Algorithm 4 in §D), a variant of Reward-Free RL-Explore algorithm in Jin et al. (2020a), to obtain estimated reward functions {r̂l, r̂f1 , · · · r̂fN }. As asserted before, we can use Algorithm 1, to find the SNE with respect to the known estimated reward functions {r̂l, r̂f1 , · · · r̂fN }. Hence, we can obtain the approximate SNE if the value functions of estimated value functions are good approximation of the true value functions. See §E for more details.

heading: 4 MAIN RESULTS FOR THE OFFLINE SETTING
text: In this section, we study the offline setting, where the central controller aims to find a StackelbergNash equilibrium by an offline dataset. Below we describe the setup and learning objective, followed by our algorithm and theoretical results.

heading: 4.1 SETUP AND LEARNING OBJECTIVE
text: We study the offline setting, where the learner has access to the reward functions (rl, rf = {rfi}Ni=1) and a dataset D = {(xτh, aτh, bτh = {bτi,h}Ni=1)} K,H τ,h=1, which is collected a priori by some experimenter. Then we make a minimal assumption for the offline dataset. Assumption 4.1 (Compliance of Dataset). We assume that the dataset D is compliant with the underlying Markov game (S,Al,Af , H, rl, rf ,P), that is, for any x′ ∈ S at step h ∈ [H] of each trajectory τ ∈ [K],
PD(x τ h+1 = x ′ | {xjh, a j h, b j h, x j h+1} τ−1 j=1 ∪ {x τ h, a τ h, b τ h}) = P (xh+1 = x′ |xh = xτh, ah = aτh).
Here the probability on the left-hand side is with respect to the joint distribution over dataset D and the probability on the right-hand side is with respect to the underlying Markov game.
Assumption 4.1 is adopted from Jin et al. (2020c), which indicates the Markov property of the dataset D and that xτh+1 is generated by the underlying Markov game conditioned on (xτh, aτh, bτh). As a special case, Assumption 4.1 holds when the experimenter follows fixed behavior policies. More generally, Assumption 4.1 allows the experimenter to choose actions aτh and b τ h arbitrarily, even in an adaptive or adversarial manner. In particular, we can assume that aτh and b τ h are interdependent across each trajectory τ ∈ [K]. For instance, the experimenter can sequentially improve the behavior policy using any online algorithm for Markov games.
Learning Objective. Similar to the online setting, we define the following performance metric
SubOpt(π, ν, x) = V π ∗,ν∗ l,1 (x)− V π,ν∗(π) l,1 (x)︸ ︷︷ ︸
SubOptl
+ N∑ i=1 [V π,ν∗(π) fi,1 (x)− V π,νfi ,ν ∗ f−i (π)
fi,1 (x)︸ ︷︷ ︸
SubOptf
], (4.1)
which evaluates the suboptimality of policies (π, ν = {νfi}Ni=1) given the initial state x ∈ S.

heading: 4.2 ALGORITHM AND THEORETICAL RESULTS
text: As is known to us, the key challenge of online setting is the the tradeoff between exploration and exploration. In the online setting. by following the “optimism in the face of uncertainty” principle (Sutton & Barto, 2018), we use bonus functions to incentivize exploration and thus achieve sampleefficient. This intrinsic challenge of online setting disappears in the offline setting because we do not need exploration any more. But another challenge arises: we only have access to the limited data. To tackle this challenge, we need add some penalty functions to achieve robustness against the uncertainty due to the finite data. This is also known as pessimism (Yu et al., 2020; Jin et al., 2020c; Liu et al., 2020b; Buckman et al., 2020; Kidambi et al., 2020; Kumar et al., 2020; Rashidinejad et al., 2021). Here we simply flip the sign of bonus functions defined in (3.4) to serve as penalty functions. See Algorithm 3 for details.
Suppose that (π̂, ν̂) are the output policies of Algorithm 3. Then we evaluate the performance of (π̂, ν̂) by establishing an upper bound for the optimality gap defined in (4.1). Theorem 4.2. Under Assumptions 2.1, 3.2, and 4.1, there exists an absolute constant C > 0 such that, for any fixed p ∈ (0, 1), by setting β′ = C · dH √ log(2dHK/p) in Line 6 of Algorithm 3 and
= dKH in Algorithm 2, then with probability at least 1− p, we have
SubOpt(π̂, ν̂, x) ≤ 3β′ H∑ h=1 Eπ∗,x [( φ(sh, ah) >(Λh) −1φ(sh, ah) )1/2] , (4.2)
where Eπ∗,x is taken with respect to the trajectory incurred by π∗ in the underlying leader-controller Markov game when initializing the progress at x. Here Λh is defined in Line 4 of Algorithm 3.
Proof. See §F for a detailed proof.
Algorithm 3 Pessimistic Value Iteration to Find Stackelberg-Nash Equilibria 1: Input: D = {xτh, aτh, bτh = {bτi,h}i∈[N ]} K,H τ,h=1 and reward functions {rl, rf = {rfi}i∈[N ]}.
2: Initialize V̂H+1(·) = 0. 3: for step h = H,H − 1, · · · , 1 do 4: Λh ← ∑K τ=1 φ(x τ h, a τ h)φ(x τ h, a τ h) > + I .
5: wh ← (Λh)−1 ∑K τ=1 φ(x τ h, a τ h) · V̂h+1(xτh+1). 6: Γh(·, ·)← β′ · (φ(·, ·)>(Λh)−1φ(·, ·))1/2. 7: Q̂h(·, ·, ·)← rl,h(·, ·, ·) + ΠH−h{φ(·, ·)>wh − Γh(·, ·)}. 8: (π̂h(· |x), {ν̂fi,h(· |x)}i∈[N ])← -SNE(Q̂h(x, ·, ·), {rfi,h(x, ·, ·)}i∈[N ]), ∀x. (Alg. 2) 9: V̂h(x)← Ea∼π̂h(· | x),b1∼ν̂f1,h(· | x),··· ,bN∼ν̂fN ,h(· | x)Q̂h(x, a, b1, · · · , bN ), ∀x.
10: end for 11: Output: (π̂ = {π̂h}Hh=1, ν̂ = {ν̂fi = {νfi,h}Hh=1}Ni=1).
Minimal Assumption Requirement: Theorem 4.2 only relies on the compliance of the dataset with linear Markov games. Compared with existing literature on offline RL (Bertsekas & Tsitsiklis, 1996; Antos et al., 2007; 2008; Munos & Szepesvári, 2008; Farahmand et al., 2010; 2016; Scherrer et al., 2015; Liu et al., 2018; Chen & Jiang, 2019; Fan et al., 2020; Xie & Jiang, 2020), we impose no restrictions on the coverage of the dataset. Meanwhile, we need no assumption on the affinity between (π̂, ν̂) and the behavior policies that induce the dataset, which is often employed as a regularizer (Fujimoto et al., 2019; Laroche et al., 2019; Jaques et al., 2019; Wu et al., 2019; Kumar et al., 2019; Wang et al., 2020; Siegel et al., 2020; Nair et al., 2020; Liu et al., 2020b).
Dataset with Sufficient Coverage: In what follows, we specialize Theorem 4.2 to the setting where we assume the dataset with good “coverage”. Note that Λh is determined by the offline dataset D and acts as a fixed matrix in the expectation, that is, the expectation in (4.2) is only taken with the trajectory induced by π∗. As proofed in the following theorem, when the trajectory induced by π∗ is “covered” by the dataset D sufficiently well, we can establish that the suboptimality incurred by Algorithm 3 diminishes at rate of Õ(1/ √ K).
Corollary 4.3. Suppose it holds with probability at least 1− p/2 that Λh I + c ·K · Eπ∗,x[φ(sh, ah)φ(sh, ah)>]
for all (x, h) ∈ S × [H]. Here c > 0 is an absolute constant and Eπ∗,x is taken with respect to the trajectory incurred by π∗ in the underlying leader-controller Markov game when initializing the progress at x. Under Assumptions 2.1, 3.2 and 4.1, there exists an absolute constant C > 0 such that, for any fixed p ∈ (0, 1), by setting β′ = C · dH √ log(4dHK/p) in Line 6 of Algorithm 3 and
= dKH in Algorithm 2, then it holds with probability at least 1− p that SubOpt(π̂, ν̂, x) ≤ C̄ · d3/2H2 √ log(4dHK/p)/K
for all x ∈ S. Here C̄ is another absolute constant that only depends on c and C.
Proof. See §G for a detailed proof.
Note that, unlike the previous literature (Antos et al., 2007; Munos & Szepesvári, 2008; Farahmand et al., 2010; 2016; Scherrer et al., 2015; Liu et al., 2018; Chen & Jiang, 2019; Fan et al., 2020; Xie & Jiang, 2020) which relies on the “uniform coverage” assumption, Corollary 4.3 only assumes that the dataset has a good coverage of the trajectory incurred by the policy π∗.
Optimality of the Bound: Assuming the dummy followers, that is, the actions taken by the followers won’t affect the reward functions and transition kernels, the Markov games reduces to the linear MDP (Jin et al., 2020b). Together with the information-theoretic lower bound Ω( ∑H h=1 Eπ∗,x[(φ(sh, ah)>(Λh)−1φ(sh, ah))1/2]) established in Jin et al. (2020c) for linear MDPs, we immediately obtain the same lower bound for our setting. In particular, our upper bound established in Theorem 4.2 matches this lower bound up to β′ and absolute constants and thus implies that our algorithm is nearly minimax optimal.

Review summaries:
The paper studies the problem of multi-agent Markov games with one leader and multiple followers. Moreover, the games considered are controlled by the leader, meaning that the transition function only depends on the action of the leader. The goal is to find the Stackelberg-Nash equilibrium of the game by means of reinforcement learning-based algorithms, both for the offline and online setting. The algorithms proposed have guarantees in terms of regret which is sub-linear in the number of episodes for the online setting and converges to zero in the offline setting in the size of the dataset.