Can Reinforcement Learning Efficiently Find Stackelberg-Nash Equilibria in General-Sum Markov Games?
Authors: Han Zhong
Zhuoran Yang
Zhaoran Wang
Michael Jordan
Venue: ICLR 2022 Submitted (2022)

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 $(\pi^*, \nu^*)$ such that (i) $\pi^*$ is the optimal policy for the leader when the followers always play their best response, and (ii) $\nu^*$ is the best response policy of the followers, which is a Nash equilibrium of the followers' game induced by $\pi^*$. 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. 

Under review as a conference paper at ICLR 2022
CAN REINFORCEMENT LEARNING EFFICIENTLY FIND STACKELBERG-NASH EQUILIBRIA IN GENERAL-SUM MARKOV GAMES?
Anonymous authors Paper under double-blind review
ABSTRACT
We study multi-player general-sum Markov games with one of the players des- ignated 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-Nant (SNE), which a policy pair (T* , v²") such that (i) x" the optimal policy for the leader when the followers always play their best response, and (ii) D* is the best response policy of the followers, which is Nash equilibrium of the followers' game induced by n". 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 itera- tion 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 prov- ably efficient RL algorithms for solving SNE in general-sum Markov games with center-controlled state transitions.
equilibrium
INTRODUCTION
Reinforcement learning (RL) has achieved striking empirical successes in solving complicated real- world sequential decision-making problems (Mnih et al., 50 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 RI. algorithms recently have gained great popularity in decision-making problems in- volving multiple interacting agents (Busoniu et al., 2008: Hernandez-Leal et al., 2018; 2019; Oroo- jlooyJadid & Hajinezhad, 2019; Zhang et al., 2019). Multi-agent RL is often modeled as Markov game (Littman, 1994) where, 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, 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 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 leader- follower 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 al., 2011; Balcan al., 2015), incentive design (Zheng et al., 1984; Ratliff et al., 2014;
Chen et al., 2016; Ratliff & Fiez, 2020), and model-based RI (Rajeswaran et al., 2020). Consider simplified economic system that consists of government and a group of companies, where the

---

Under review as a conference paper at ICLR 2022
companies purchase sell goods, and the government collects taxes from transactions. Such 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-Naat equilibrium (SNE) (Baş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 v* that satisfies the following two properties: (i) when the leader adopts nτ, 1²" is the best-response policy of the followers, i.e., v= is a Nash equilibrium of the followers' subgame induced by n²; 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 game, we are interested in the following question:
Can we develop reinforcement learning methods that provably find Stackelberg- Nash equilibria in
leader-controlledd 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 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, also needs to take the exploration-exploiie challenge has been studied in zero-sum 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. Mcanwhile, under the offline setting, as the RL agent has 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.
achieve sample efficiency, the equilibrium-fiddin algorithm
tradeoff into consideration. Although the similar
Our contributions Our contributions are three-fold. First, for the episodic controlen 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, version LSVI, we estimate the optimal action-value function of the leader via 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 UCB exploration bonus to the least-squares solution to achieve op- timism 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 sublinear Q(H2V/B regret, where K is the number of episodes, H is the horizon, d is the dimension of the feature mapping, and Ö(-) omits logarithmic terms. Finally, under the offline setting, we establish an upper bound the suboptimality of the proposed algorithm for an arbitrary dataset with trajectories. Our upper bound yields a sublinear 0/H22//' ()) rate as long as the dataset has sufficient coverage over the trajectory induced by the desired SNE.
regression and
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 SA.
Learning Stackelberg games As for solving Stackelberg-No
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 first- order methods for finding Stackelberg equilibria in general-sum games with differentiable reward functions, and Ghadimi & Wang (2018) 8); 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
2

---

Under review as a conference paper at ICLR 2022
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 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 online and offline settings.
Notation See }B for details.
2
PRELIMINARIES
In this section, we introduce the formulation of the general-sum simultaneous-move Markov games, Stackelberg-Nast equilibrium, and the linear structure we use in this paper.
2.1 GENERAL-SUM SIMULTANEOUS-MOA MOVEE MARKOV GAMES
In this setting, two levels of hierarchy in decision making are considered: one leader / and N followers (filEE]N)- Specifically, we define an episodic version of general-sum simultaneous- moves Markov game by the tuple (S, As = {Ar lig[N] H.r,yy = fr [e P), where S is the state space, At and A the sets of actions of the leader and the followers respec- tively, H is the number of steps in each episode, rı {ri, S x A x A, ry (reAh S x A x A, respectively, and P = (Px S x A x A, x S - [o, 1))-= is collection of transition kernlss. Here A x A Ai A₁, x... Alv. Throughout this paper, we also let * be some element in f1, ... f.]. Moreover, for any (h, x, a) [H] x S x A and b = {b, E A he([,, we use the shorthands (2, a, b) = (I,, a, b1. bN) and P x, a, b) = PA(- x. b1, bb,.
[- 1) and []], are reward functions of the leader and the followers
Policy and Value Function. A stochastic policy क = { : S + >(AA)] of the leader is a set of probability distributions over actions given the state. Meanwhile, stochastic joint policy of the followers is defined by V = {vy, (y)ee. where V/5, = (V),. S - ((AA) ) We use the notation (a ()) and v (b: 2²) to denote the probability of taking action a E At or b, E As, for state x at step h under policy π,, Vy. respectively. Throughout this paper, for any V (Vg and
b = [b:] we use the shorthand v/ (b) x) = M/2. |x) x ... X & (bN (r)
Given policies (T,, V= = {rr, he(N))) the action-value (Q) and vtate-value (V) functions for the leader and followers are detined by
#1 Σ
QT, a, a.
Er.a r+. (2,,, bi) V. (x) Buwnyl (e), (1 Q. (z, a, b)b,, (2.1) t=h
where the expectation Er..,b.,,a.b is taken over state-action pairs induced by the policies (T, v
{V JEE(N)) and the transition probability, when initializing the process with the triplet (s, a, b = (eihel))) at step h. For notational simplicity, when h, I, a, are clear from the context, we omit h, N, a, 6 from B.,.A,,,,.... By the definition in (2.1), we have the Bellman equation
VT. *.
(Q.K, TA UR)AIAAS
TT = r., + PA V 1
V* fI, fN].
(2.2)
where Th X uA represents TA X Pfi.h X ... X VSN.n. Here Ph. is the operator which is defined by (Pnf) a, b) = E[[(=') Pa Ixx b)) for any function| f: RR and az) S A x Ay.
(2.3)
2.2 STACKELBERG-NASHI EQUILIBRIUM
Given a leader policy ग, a Nash equilibrium (Nash, 2016) of the followers is joint policy 1² (v), JEEN]. such that for any & E S and hi,h) E [N] x [H]
VT." fih (x) 2 V T. 77 (2),
Vyy.
(2.4)
fish
3

---

Under review as a conference paper at ICLR 2022
Here -i represents all indices in [N] except For each leader policy и,, we denote the set of best- response policies of the followers by (R(T), which defined by
(R( (v - {u hEIN v is the NE of the followers given the leader policy T).
(2.5)
Given the best-response set (R(()), denote y² =²(TT the worst-case responses, which break ties against favor of the leader Specifically, define v/ (T)) by
'" (T( {v e (R( V. (a) S ViA (z), S [H], v/ BR(T)).
(2.6)
The Stackelberg- Nash equilibrium for the leader is the "best response to the best response", that is,
SNE, ( Lih (x)
VLA
(*) (z),
Vo S, [M],
(2.7)
A Stackelberg-Ner Nash equilibrium of the general-sum game is policy pair (n", v {v/ hE(() such that v* E u² (=*" and x² E SNE,
Our goal to find the Stackelberg equilibrium: the leader's optimal strategy. assuming the fol- lowers 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).
2.3 HEADER-CONTROLES LINEAR MARKOV GAMES
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 feature map. Specifically, there exists a feature map o' x A x As + I such that
Pa(: a,, (d' (2, a, b).
(d) are d unknown for any (x. b) E S x Ar x As and h E [H]. Here μh = (m/ Ph . S. Moreover, throughout this paper, focus 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,
signed measures
Pa(- 2, PA( xx,a)
for any (Ir, a, b) S x Ay and E [H]. Hence, is naturally to define leader-controller linear Markov games follows.
Assumption 2.1. Markov game AS, (A H,,,, (r hejyj P) is leader- controller linear Markov game if there exists feature map Φ Ai TRdd such that
( 2. a, b) (0(x, (n.))
(1) (2) for any (z, b) E S x A x A, and h E [M]. Here μa = (ug .Ph , Mhh
(d) are d unknown
signed measures over S. Without loss of generality, assume that [| (S)] s Vd 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 RI. Specifically, when the followers play fixed and known policies, the linear Markov games reduce to the linear MDP.
MAIN RESULTS FOR THE ONLINE SETTING
In this section, we study the online setting, where central controller controls one leader / and N' followers (fi)EIN)) Our goal is to leamn Stackelberg-Nase equilibrium. In what follows, we formally describe the setup and learning objectives, and then present our algorithm and provide theoretic guarantees.
"This is also known pessimistic tie breaking (Conitzer & Sandholm, 2006). We also remark that subsequent analysis still holds for the optimistic setting (Breton et al., 1988; Bucarey al., 2019a).
4

---

Under review as a conference paper at ICLR 2022
3.1 SETUP AND LEARNING OBJECTIVE
We consider the setting where the reward functions ri and fry, hE[[] are revealed to the learner before the game. This is reasonable since in practice the reward functions usually artificially designed. Moreover, we focus on the episodic setting. Specifically, a Markov game is played for K episodes, each of which consists of H timesteps, At the beginning of the k-th episode, the leader and followers determine their policies (T* .² = { (1), he(N)), and a fixed initial state vf = æi 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 -f is picked from a fixed distribution. Then the game proceeds as follows. At each step h E [H] the leader and the followers observe state 2 E S and pick their own actions ax. ~ ( xx)) and 0% = (O ~ (. [= Subsequently, the environment transitions to the next state 2 Pa(. 1 42 b.). Each episode terminates after H timesteps.
Learning Objective. By the definition in (2.5), given 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 (TT, {vg )EE(N)), is natural to define the following objective to measure the suboptimality of Vf:
SubOpt,, (x) = Vi.l va.."(()) (x) Vi.l ". (x).
Meanwhile, we evaluate the performance of the leader's policy x by the following suboptimality gap:
SubOpt, = Vi1 . (x) (=))
Putting these two suboptimality gaps together, formally define the regret follows.
Definition 3.1 (Regret). Let (T* vh {ur hE(N)) denote the policies executed by the algorithm in the k-th episode. After total of K episodes, the regret is defined as
K
(x+))
Regret( K)=
V
(af)
Vi -
(m
(x/)
V
(xf).
Sull
fill
Regret, (KC)
Regret, (R)
(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.
3.2 ALGORITHM
We now present our algorithm, Optimistic Value Iteration to Find Stackelberg-No Equilibrium (OVI-SNE), which is given in Algorithm 1.
At high level, in each episode, our algorithm first construct the policies for all players through backward induction with respect to the timestep f (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 E [H), we estimate the linear coefficients by solving the following ridge regression problem:
k-1 Vi (1h41) 6(0%/ ah)) J Tw] + ||wl12
+ argmin
Σ
w WERd r=1
(3.2)
where Vhl
( (35)), (.1.) (-1)))))))
By solving the ridge regression problem in (3.2), we have
w = (A
MaT V (
(3.3)
1-1
where A
Σ
Maz Moth aR) +1
5

---

Under review as a conference paper at ICLR 2022
To encourage exploration, additionally adds bonus function to estimate the leader's O-function: Qh + (t, (1, - --==-((((;)))
+) w + I (:,-))
(3.4)
where [..)--) = 3 V -
Here 1% S Ar + R is a bonus function and 3 > 0 is a parameter which will be specified later. This form of bonus function is common in the literature of linear bandits (Lattimore Szepesvári, 2020) and linear MDPs (Jin et al., 2020b).
Then, we construct policies for the leader and followers by the subroutine c-SNE (Algorithm 2). Specifically, let 2 be the class of functions Q S A x A - R that takes form
@(::))) ( -H -T w + B (o(:,)) --
(3.5)
where the parameters (w, A) E I2d Raddd satisfy || < H v dk and Amin (A) 2 1. Moreover, let Oh.c be a fixed e-covering of 2 with respect to the loo norm. By Lemma C.10, we have Q 2 which allows us to pick @ 2h, such that I|: - Q oc S e and calculate policies by (x ( (=11))))(N)) + SNE(Q( :)
)E))))) Vz.
(3.6)
When there is only one follower, such problem can be transformed to linear programming (LP) problem (Conitzer & Sandholm, 2006; Von Stengel & Zamir, 2010), and thus can be solved ef- ficiently. For the multi-follower case, however, solving such matrix game in general is hard (Conitzer & Sandholm, 2006; Basilico et al., 2017;;b; Coniglio et al., 2020). Given this computa- tional hardness, we focus on the sample complexity and explicitly assume access to the following computational oracle:
Assumption 3.2. We assume access an oracle that implements Line 3 of Algorithm 2 when there are multiple followers (i.e., N 2 2).
Now we explain the motivation for using the subroutine e-SNE to construct policies instead of solv- ing the matrix games with payoff matrices (x, (r :)) (EvV))) directly. By the defini- tion of Q in (3.4), we know Q relies on the previous data via the estimated value function V.& and feature maps {o(2), ah b-))==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 1 Jin al. (2020b) directly constructs an e-net for the value functions and establishes a polynomial log-covering number for this e-net. This analysis, however, relies on that the policies executed by the players are greedy (deterministic), which is not valid for setting. To overcome this technical issue, we construct an e-net for Q-functions and solve an approximate matrix game. Fortunately, by choosing small enough e, 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 e-net.
Finally, the leader and the followers play the game according to the obtained policies. 3.3 THEORETICAL RESULTS
Our main theoretical result the following bound on the regret incurred by Algorithm Recall that the regret is defined in Definition 3.1 and T = K H is the total number of timesteps.
Theorem 3.3. Under Assumptions 2.1 and 3.2, there exists an absolute constant >> such that, log(2dT/p) in Line 7 of Algorithm K in Algorithm 2, then with probability at least - the regret incurred by OVI-SNE satisfies that
for any fixed E (0, 1), by setting / = F-dH /i with
and e 1
Regret(K) K) s S0(V0
Proof. See SC for detailed proof.
Learning Stackelberg Equilibria. When there is only one follower, Stackelberg-Nash equilib- rium reduces 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 Stackelherg equilibria in (leader-controller) Markov games.

---

Under review as a conference paper at ICLR 2022
Algorithm Optimistic Value Iteration to Find Stackelberg-Nasl Equilibria
1: Initialize v(,H+1())
(),H+1(-) =
2: for k 1. 2.... K do
3: Receive initial state o².
4: for step h H. H ,,..,, do
5:
A
Σr= kー o( 00) 0) +1.
6:
w + (AA) E 0(5% (+112%711
7:
(x t (((:,)) ((.)))
8:
t r...,,,
-IH=Λ(((.-) wh + ().)).
9:
(T)(11)), ( (E) (N) + e- (1, ) fr (2,, DiE Va. (Alg. 2)
10:
(x) E Baatt (-12), b, (112),- ww ( 2) 2 (2, a, ... bw), Vx.
11:
end for
for h 1,2, H do
13:
Sample of ~ (- (2 T.n
........ .bN. (1
Leader takes action of Followers take actions bjt = (b,NNENN
15:
Observe next state x h+-1 end for
16:
17:
end for
Algorithm 2 6-NNE
1: Input: Q x, and parameter e.
2: Select Q from 2h satisfying I2 Qi Sc.
3: For the input state x, let (+ (2), ( [)] be the Stackelberg -ash equilibrium for the matrix game with payoff matrices (Q(z,,, :),
4: Output: (- æ), ( (1) ())E)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 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 & Szepesvári (2020) for linear bandits directly imply lower bound QdH VT) for the linear MDPs, which further yields lower bound Q(HH vT) for our setting. Ignoring the logarithmic factors, there is only gap of / /d 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 v 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 1. When the transitions do not ideally satisfy the leader-comtroller assumption, can potentially consider cases that transitions satisfy, for instance, (P x. a, b) - P.. xx a)lloo S for any (h, a. b) E [H] x S x At x Ay. 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 OggI') will appear in the final result. In particular, When @ is small, that is the Markov games have approximately lcader-controller transitions, the extra term ( should be small, which further indicates that we can find SNEs efficiently in some misspecified general-sum Markov games.
Unknown Reward Setting.
At high level, we first conduct reward-free exploration algorithm (Algorithm (D), variant of Reward-Fres RL-Explore algorithm in Jin al. (2020a), to obtain estimated reward functions {fr, f,, F }. As asserted before, we can use Algorithm 1, to find the SNE with respect to the known estimated reward functions (Fi, F Fíx ). Hence, 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.

---

Under review as a conference paper at ICLR 2022
4 MAIN RESULTS FOR THE OFFLINE SETTING
In this section, we study the offline setting, where the central controller aims to find a Stackelberg- Nash equilibrium by an offline dataset. Below we describe the setup and learning objective, followed by our algorithm and theoretical results.
4.1 SETUP AND LEARNING OBJECTIVE
We study the offline setting, where the learner has access to the reward functions (ri.Ty fry, (r and a dataset D { 0h, b% ((=)) menter. Then make minimal assumption for the offline dataset.
which is collected a priori by some experi-
Assumption 4.1 (Compliance of Dataset). We assume that the dataset D is compliant with the underlying Markov game As, As, H,,,, P), that is, for any x' S at step h E [H] of each trajectory 7 [K].
PD xo {1r a: 1/ o + U (1% ah b7)) P(x x' bn 1h a2 a5))-
Here the probability on the left-hand side with respect to the joint distribution over dataset DD and the probability the right-hand side is with respect to the underlying Markov game.
Assumption 4. adopted from Jín et (2020c), which indicates the Markov property of the dataset DD and that 4//41 is generated by the underlying Markov game conditioned on (2% a b7,) As special case, Assumption 4.1 holds when the experimenter follows fixed behavior policies. More generally. Assumption 4.1 allows the experimenter to choose actions aj and bf, arbitrarily, even in an adaptive or adversarial manner. In particular, we can assume that aj and bj, are interdependent across each trajectory E [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(T, v,, V
(x)
V
(TT)
(m) f.11
(x)
(x)
Vin
" (x)
(z)],
(4.1)
SubOpt,
SubOpt,
which evaluates the suboptimality of policies (H, ( given the initial state x E S.
4.2 ALGORITHM AND THEORETICAL RESULTS
As is known to us, the key challenge of online setting is the the tradeoff between exploration and exploration. 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 sample- efficient. 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, uncertainty due to the finite data. This is also known as pessimism (Yu et al., 2020; Jin et al., 2020c; Liu al., 2020b; Buckman 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.
need add some penalty functions to achieve robustness against the
al., 2020; Kidambi et al., 2020; Kumar et al., 2020; Rashidinejad
Suppose that (7, D) are the output policies of Algorithm Then we evaluate the performance of (7, D) by establishing upper bound for the optimality gap defined in (4.
Theorem 4.2. Under Assumptions 2.1, 3.2, and 4.1, there exists an absolute constant C such that, for any fixed p E (0, 1), by setting 3' = C dHf / [og(2dH p) in Line 6 of Algorithm 3 and d in Algorithm 2, then with probability at least P. we have
KH
H E. F.r [(5b(5), (n) (An) (Ss)) (z))
Sub S 3,3'
(4.2)
/=1
where Er v is taken with respect to the trajectory incurred by x' in the underlying leader-controller Markov game when initializing the progress Here A₁ is defined in Line 4 of Algorithm 3.
8

---

Under review as a conference paper at ICLR 2022
Proof. See 8F for detailed proof.
Algorithm Pessimistic Value Iteration to Find Stackelberg-Natt Equilibria
1: Input: D= = = 0/o b7 = (1ENNN) K.H and reward functions {ri,ry = fr IEEN))
2: Initialize VH+11 (-) =
3: for step h H, H 1,.... do
4: An - (5 af ()) a)) +
5: wh + An)--Ea ((5%) a,) (1+1
6:
[n(::)) 4 3' (o(.-))
))2/2
7:
( t ()))))))))) + H1 - -T "w, -on,-a(())) l'(t,))).
8:
fr MENN), Vo. (Alg. 2) (x( E Es (:1 2)),, ~B, w.), by B / a Qn (z, bi, ,NN,, Vx.
(Tal. r), ( x)) (E(N)) + --SNE(QU
9:
end for
11:
Output: (f = ( J = (D, = (UNNEE D
Minimal Assumption Requirement: Theorem 4.2 only relies on the compliance of the dataset with linear Markov games. Compared with existing literature offline RL (Bertsekas & Tsitsiklis, 1996; Antos et al., 2007; 2008; Munos & Szepesvá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. Mcanwhile, we need no assumption on the affinity between (#t 9) and the behavior policies that induce the dataset, which is often employed regularizer (Fujimoto et al., 2019; Laroche al., 2019; Jaques et al., 2019; Wu 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 the setting where we assume the dataset with good "coverage". Note that A, is determined by the offline dataset D and acts 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 DD sufficiently well, can establish that the suboptimality incurred by Algorithm diminishes at rate of ((1/VK). Corollary 4.3. Suppose it holds with probability at least 1 - pp/2 that
A = 7 + c K Er. [=r==( on ())) a1)"]
for all (z, e S [H. Here e > an absolute constant and Ex,., is taken with respect to the trajectory incurred by л² in the underlying leader-controller Markov game when initializing the progress at æ. Under Assumptions 2.1, 3.2 and 4.1, there exists an absolute constant >> such that, for any fixed p E (0, 1), by setting 3r = C dHH, /Tog( K/p) in Line 6 of Algorithm 3 and d in Algorithm 2, then it holds with probability at least 1 pp that
<= KH
SubOpt(f, x,x) S C d H² /log(AdH
for all x E S. Here Č is another absolute constant that only depends on e and C.
Proof. See 8G for detailed proof.
Note that, unlike the previous literature (Antos et al., 2007; Munos & Szepesvári. 2008; Farahmand al., 2010; 2016; Scherrer et al., 2015; Liu 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 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 duces to the linear MDP (Jin et al., 2020b). Together with the information-theorret lower bound ( h= MDPs, 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 8 and absolute constants and thus implies that our algorithm is nearly minimax optimal.
(x T(A,) (AA))= (=)()) //22) established in Jin et al. (2020c) for lin-

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pp. 2312-2320, 2011.
Alckh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a gener- ative model is minimax optimal. In Conference on Learning Theory, pp. 67-83, PMLR, 2020.
Forest Agostinelli,, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356-363, 2019.
Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's cube with robot hand. arXiv preprint arXiv:1910.0711. 2019.
András Antos. Rémi Munos, and Csaba Szepesvári. Fitted q-iteration in continuous action-space mdps. 2007.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near- mear-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-122 1299, 2008.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax PAC bounds the sample complexity of reinforcement learning with a generative model. Machine learning, 91()): 325-349 2013.
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Inter- national Conference on Machine Learning, pp. 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. arXiv preprint arXiv:2006. 12007, 2020.
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-effciien learning of stackelberg equilibria in general-sum games. arXiv preprint arXiv:2102. 1494, 2021.
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the sixleenth ACM conference on economics and computation, pp. 61-78, 2015.
Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
Nicola Basilico, Stefano Coniglio, and Nicola Gatti. Methods for finding leader-followe equilibria with multiple followers. arXiv preprint TrXiv:1707.02177 2017a
Nicola Basilico, Stefano Coniglio, Nicola Gatti, and Alberto Marchesi. Bilevel programming ap- proaches to the computation of optimistic and pessimistic www.eee-mmlii--olollllooll equilibria. In SEA, volume 75, pp. 1-14. Schloss Publishing, 2017b.
fur Informatik GmbH, Dagstuhl
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment to overcome insecurity. 2014.
Michele Breton, Abderrahmane Alj, and Alain Haurie. Sequential stackelberg equilibria in two- person games. Journal of Optimization Theory and Applications, 59(1):11997 1988.
10

---

Under review as a conference paper at ICLR 2022
Victor Bucarey. Eugenio Della Vecchia, Alain Jean-Marie, and Fernando Ordóñez. Stationary Strong Stackelberg Equilibrium in Discounted Stochastic Games, PhD thesis, INRIA, 2019a.
Víctor Bucarey, Alain Jean-Marie, Eugenio Della Vecchia, and Fernando Ordóñiez. On the value iteration method for dynamic strong stackelberg equilibria. In ROADEF 2019-20ème congrès annuel de la société Française de Recherche Opérationnelle et d d'di à la Décision, 2019b.
Jacob Buckman, Carles Gelada, and Mare G Bellemare. The importance of pessimism in fixed- dataset policy optimization. arXiv preprint arXiv:2009.06799 2020.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent rein- forcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):55--77,, 2008.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti-
mization. In International Conference on Machine Learning, pp. 1283-1294, PMLR, 2020.
Jinglin Chen and Nan Jiang. anformation-theoreel considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051, PMLR, 2019.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:21022 00.717 2021a.
Zhuoqun Chen, Yangyang Liu, Bo Zhou, and Meixia Tao. Caching incentive design in wireless d2d networks: A stackelberg game approach. In 2016 IEEE International Conference on Communi- cations (ICC), pp. 1-6. IEEE, 2016.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv preprint
2021b.
Stefano Coniglio, Nicola Gatti, and Alberto Marchesi. Computing pessimistic stackelberg equi-
librium with multiple followers: The mixed-pure case. Algorithmica, 8265):1189-1238, 2020.
Vincent Conitzer and Tuomas Sandholm. Complexity of mechanism design. arXiv preprint cx/0205075, 2002.
Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceed- ings of the 7th ACM conference Electronic commerce, pp. 82-90, 2006.
Qiwen Cui and Lin F Yang. Minimax sample complexity for turn-based stochastic game. arXiv preprint arXiv:201 1. 14267, 2020.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. arXiv preprint XXiv:2101.04233, 2021.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In International conference on machine learning, pp. 1329-1338. PMLR, 2016.
Yonathan Efroni, Lior Shani, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. arXiv preprint arXiv:2002.08244, 2020.
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q- learning. In Learming for Dynamics and Control, pp. 486 PMLR, 2020.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
Amir-massoud Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Reg- ularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research, (1()):8899-44 4874, 2016.
11

---

Under review as a conference paper at ICLR 2022
Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Convergence of learning dynamics in stack- elberg games. arXiv preprint arXiv: 1906.01217, 2019.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
Scott Fujimoto, David Meger, and Doina Precup. Off-po deep reinforcement learning without exploration. International Conference on Machine Learning, pp. 2052-2062. PMLR, 2019.
Dinesh Garg and Yadati Narahari. Design of incentive compatible mechanisms for stackelberg problems. In International Workshop on Internet and Network Economics, pp. 718-727. Springer, 2005.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246. 2018.
Amy Greenwald, Keith Hall, and Roberto Serrano. Correlated q-learning. In ICML, volume 3, pp- 242-249, 2003.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly poly- nomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1-16, 2013.
Pablo Hernandez-Leal, Bital Kartal, and Matthew E Taylor. Is multiagent deep reinforcement learn- ing the answer the question? brief survey. Learning, 21:22, 2018.
Pablo Hernandez-Leal Bilal Kartal, and Matthew E Taylor. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 33(6))750-793 7970 2019.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint 20f1:20007.05700. 2020.
Junling Hu and Michael P Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov):1039-106) 2003.
Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of 2019.
implicit human preferences in dialog. arXiv preprint
Zeyu Jia, Lin F Yang. and Mengdi Wang. Feature- based q-learning for two-player stochastic games. arXiv preprint 1906:009900002. 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? arXiv preprint arXiv: 10X7vv8807.033333 807.03365, 2018
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-fres free exploration for reinforcement learning. In International Conference on Machine Learning, pp. 4870-4879 PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? arXiv preprint arXiv:2012.15085, 2020c.
Xin Kang and Yongdong Wu. Incentive mechanism design for heterogeneous peer-to-peer networks:
A stackelberg game approach. IEEE Transactions Mobile Computing, 1415):1018-1030, 2014.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05951 2020.
Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe. Stackelberg vs. Nash in security games: An extended investigation of interchangeabiliyy equiva- lence, and uniqueness. Journal of Artificial Intelligence Research, 41:297-327, 2011.
12

---

Under review as a conference paper at ICLR 2022
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off off-policy q-learning via bootstrapping error reduction. arXiv preprini arXiv: 1906.00999 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. O0KV:2900.00779, 2020.
Michail Lagoudakis and Ron Parr. Value function approximation in zero-sum markov games. arXiv preprint arXiv:1301.005 2012.
Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning, pp. 3652-3661. PMLR, 2019.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the opti- mal strategy commit to. In International Symposium Algorithmic Game Theory, pp. 250- 262. Springer, 2009.
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In
Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Michael L Littman. Friend-or-foe q-learning in general-sum games. In JCML, volume 1, pp. 322- 328, 2001.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. arXiv preprint
2018.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. arXiv preprint arXiv:2010.016000 2020a.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202. 2020b.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski. et al. Human-level control through deep reinforcement learning, nature, 5 8(7540)
2015. 2015.
Rémi Munos and Csaba Szepesvári. Finite-time time bounds for fitted value iteration. Journal of Machine Learning Research, 95),, 2008
Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.09359, 2020.
John Nash. Non-Cooperative Games. Princeton University Press, 2016.
Afshin OroojlooyJadid and Davood Hajinezhad. A review of cooperative multi-agent deep rein- forcement learning. arXiv preprint arXiv:1908.03000 2019.
Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategics to commit to. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 2149-2156, 2019.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, pp. 1321-1329, PMLR, 2015.
Aravind Rajeswaran, Igor Mordatch, and Vikash Kumar. A game theoretic framework for model based reinforcement learning. In International Conference on Machine Learning, pp. 7953-7963. PMLR, 2020.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: tale of pessimism. arXiv preprint arXiv: 12021, 2021.
13

---

Under review as a conference paper at ICLR 2022
Lillian J Ratliff and Tanner Fiez. Adaptive incentive design. IEEE Transactions Automatic Control, 2020.
Lillian J Ratliff, Ming Jin, Ioannis C Konstantakopoulos, Costas Spanos, and S Shankar Sastry. Social game for building energy efficiency: Incentive design. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1011-1018. IEEE, 2014.
journal Tim Roughgarden. Stackelberg scheduling strategies. SIAM journal on computing, 33(2):332-350, 2004.
Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, and Matthieu Geist. Approximate modified policy iteration and its application to the game of tetris. J. Mach. Learn. Res., 16:1629-1676, 2015.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference Artificial Intelligence and Statistics, pp. 2992-3002. PMLR, 2020.
Noah Y Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Ne- unert, Thomas Lampe, Roland Hafner, Nicolas Heess, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint 2xXiv:2002.08396, 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam,, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):4844455
2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nalure, 550(7676):354335) 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanetot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140- 1144, 2018
Marwaan Simaan and Jose B Cruz. On the stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications, 11(5):533-555, 1973.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, al. Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pp. 1057- 1063. Citeseer, 1999.
Milind Tambe.
Security and game theory: algorithms, deployed systems, lessons learned. Cam- bridge university press, 2011.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Provably efficient online agnostic learning in markov games. arXiv preprint arXiv:2010.15020. 2020.
Berhhard Von Stengel and Shmuel Zamir. Leadership games with convex strategy sets. Games and Economic Behavior, 69(2):446 2010.
Ziyu Wang, Alexander Novikov, Konrad Żoina, Jost Tobias Springenberg, Scott Reed, Bobak Shahriari, Noah Siegel, Josh Merel, Caglar Gulcehre, Nicolas Heess, et al. Critic regularized regression. arXiv preprint XXix:2006.15134 2020.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-29) 1992.
Chen-Yu Wei, Yi-Te Hong and Chi-Jen Lu. Online reinforcement learning in stochastic games. arXiv preprint arXiv: 1712.0059. 2017.
14

---

Under review as a conference paper at ICLR 2022
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint 19X1v:111.113000 2019.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultancous- move markov games using function approximation and correlated equilibrium. In Conference Learning Theory, pp. 3674-3682. PMLR, 2020.
Tengyang Xie and Nan Jiang. Q* Qr-approximation schemes for batch reinforcement learning: A theoretical comparison. arXiv preprint arXiv:2003. 039244, 2020.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pp. 10746-10756. PMLR, 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. Bridging exploration and general function approximation reinforcement learning: Provably efficient kernel and neu- ral value iterations. arXiv preprint arXiv:2011.06222, 2020.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005.13239 2020.
Andrea Zanette and Emma Brunskill. Tighter
regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1954-1964. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning op- timal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020b.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint 1911v 2019.
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin Yang. Model-based multi-agent in zero-sum markov games with near-optimal sample complexity. urXiv preprint arXiv:2007.074611 2020a.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. arXiv preprint arXiv:2009. 13503, 2020b.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems, 33, 2020c.
Yulai Zhao, Yuandong Tian, Jason D Lee, and Simon S Du. Provably efficient policy gradient methods for two-player zero-sum markov games. arXiv preprint 10Xiv:2102.08900, 2021.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C Parkes, and Richard Socher. The Al economist: Improving equality and productivity with AI-driven tax policies. arXiv preprint urXiv:2004. 13332, 2020.
Ying-Ping Zheng, Tamer Basar, and Jose B Cruz. Stackelberg strategies and incentives in multiper- son deterministic decision problems. IEEE transactions Systems, Man, and Cybernetics, (1); 10-24, 1984.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. arXiv preprint arXiv:2012.088500 2020.
15


Reviews:
[{"review_id": "wmEULpb8WfC", "reviewer": "Reviewer_cJRF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: The paper provides a near-optimal and, to my knowledge, novel regret bound for learning Stackelberg equilibria in the chosen setting.\n\nWeaknesses: The setting is not very well motivated. The authors stipulate very significant assumptions on the problem (the existence of a normal-form SNE oracle, and the followers not affecting the state transitions) without justifying them. Why should we care about this very specific setting? Are there interesting problems that fall into it? \n\nAlso, the above two assumptions together seem to immediately sidestep everything difficult and interesting about Stackelberg equilibria and multiplayer games. Indeed, the followers' strategy at each time step is now a function of the leader's strategy (because the followers cannot control the transitions), and that function is given by an oracle (by assumption). As such, the problem is reduced immediately to a (single-player) MDP.\n\nIn some sense, given the above, what is really going on is that the authors have developed algorithms for solving a class of MDPs perhaps more general than linear MDPs. If that class of MDPs can be isolated and is significant or interesting in its own right, perhaps it would be a good idea to frame the paper in that light instead. I also wonder if directly framing the problem as an MDP results in a simplification of the algorithms or analyses via known tools for MDPs. ", "summary_of_the_paper": "The paper studies the problem of computing Stackelberg-Nash equilibria in a certain restricted family of Markov games, in which the followers do not control the transitions. Assuming an oracle that solves each stage game, the authors develop an algorithm for solving for Stackelberg-Nash equilibria in the overall game. ", "summary_of_the_review": "A perhaps interesting theoretical result, but poorly motivated and very narrow. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "qO_bvSrY7GL", "reviewer": "Reviewer_JEih", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper requires a considerable revision and re-organization. There are many details and remarks, but the setting, the challenges and the proposed solutions are unclear.\n\n- First of all, the notion of linear function approximation is unclear. In Algorithm 1 (Line 10) and Algorithm 3 (Line 9), it is seen that the algorithm keeps and updates the value function for each state $x\\in\\mathcal{S}$ in an $|\\mathcal{S}|$-dimensional array. We observe the same thing for the policies also, i.e., Line 8 in Algorithm 3 indicates that policies are kept for all $x\\in\\mathcal{S}$. This looks tabular, and for large state spaces, it is intractable. If there is an underlying parameterization, then storing and updating policies and value functions at each iteration is inefficient, the algorithms should indicate that only the corresponding value function (and policy) is computed. This should be clarified.\n\n- The paper closely follows (Jin et al., '18; Jin et al., '20b) and the technical contributions seem a little incremental.\n\n- The algorithm requires a matrix inversion at each iteration, and requires solving Line 2 of Algorithm 3, as the authors also indicate. I understand that the paper focuses on sample efficiency, but computational feasibility is an important concern especially in RL, especially in the function approximation setting where there is a large-scale problem. Could it be possible to solve the least-squares problem in Equation (3.2) by using SGD? How would that impact the sample complexity?\n\n- What is the prevalence of the problem that is considered in this paper? There is a structural assumption on the transition dynamics, i.e., the transition kernel is linear with a given kernel. How broad is this class of problems?\n\n- The literature review and notation are deferred to the supplementary material, and the paper is missing a conclusion. I think some space can be saved for these important discussions by deferring some of the technical details to the supplementary material instead.\n\n- The paper considers structured (i.e., linear) Markov games, which is stated in Section 2.1. This important aspect can be emphasized for the sake of clarity earlier, perhaps in the abstract also.", "summary_of_the_paper": "The paper investigates leader-controlled multi-player general-sum games in the episodic setting. Based on optimistic and pessimistic LSVI, the paper proposes algorithms that achieve sublinear regret in the online and offline setting, respectively. ", "summary_of_the_review": "The problem setting, the algorithms and the results require considerable clarification. The proposed methods can have large memory and computational complexities, which may be problematic for large state spaces. The technical contributions seem a little incremental.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "V49EDeXIgvU", "reviewer": "Reviewer_MweZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper seems to consider the interesting problem of computing SNE for linear MDPS, which seems to be a novel problem. The technical level of the paper seems to be of high quality. However, the structure of the paper would benefit from some adjustments. In particular, the related work section is of paramount importance in this work, as it is not obvious how much of the presented work is already in the literature. I would suggest moving the related works section to the main paper. Also, the algorithms presented in the paper are hard to follow: it is hard to understand the meaning of instantiating a function.\n\nThe main idea of the work is not well transmitted. Since the case of H=1 is already solved in the literature, does your method just recursively use such oracle recursively on a game with optimistic estimates? What is the main difficulty of computing such equilibrium, w.r.t. the case H=1?\n\nThe paper would greatly benefit from an empirical evaluation of the algorithm. As a benchmark, I think you could employ a solver of normal form Stackelberg games on the normal form formulation of the sequential game. This could be done in small games. Since such analysis is expected a motivation on why it is missing would be welcomed. The related work section of the work misses a work that the reviewer is familiar with, namely: Balcan et al. \"Commitment Without Regrets: Online Learning in Stackelberg Security Games\" (2015). In that case, the horizon is H=1 and there are no externalities (the best response to the leader is a joint NE for the followers). However, the paper underlines that the problem poses many difficult features, such as non-convexity, and non-continuity of the payoffs, and, hence, a careful analysis of the strategy space is needed. In this work, such specific analysis seems missing. A discussion around this topic is hence welcomed.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper would benefit from more discussion on the related works and analysis similar to the one presented in the work by Balcan (2015).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OtEjdXrylZc", "reviewer": "Reviewer_9LtG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, I enjoy the paper while as every MDP paper has an unlimited preliminaries dense section.\nI strongly believe that I will praise with large acceptance the first paper that will provide a more intuitive way of description of the RL/MDP notions. Of course this is not an issue of this specific problem but of the whole community.\n\nSo, let's go to my main questions\n\nIssue #1. I feel that there is a huge lack of motivation in the problem. Can you give three nowadays good examples of Leader/Followers General-Sum MDP games in practice?\n\nIssue #2. What are the novel parts of your algorithms? More precisely, what are the intuitive steps of the proposed algorithms and your novel introductions in a typical MDP scheme? I would like a extent answer in this issue because honestly I felt that the proposed algorithms were just plug-and-play folklore tools that we employ in practice.", "summary_of_the_paper": "The paper studies 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. ", "summary_of_the_review": "Interesting paper with important theoretical contributions. There are issues about the motivation of the model.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a Markov game with a single leader and multiple followers, where the state transitions are independent of the actions of the followers.  The paper studies online and offline RL methods for this subclass of the Markov game, and establishes a sublinear regret bound for the online RL method and sublinear suboptimality of the offline RL methods.

Although the paper appears to contain interesting ideas and contributions, the responses and revisions have not sufficiently addressed some of the major concerns of reviewers.  The reviewers and AC thus agree that the paper is not ready for publication.  For example, the issue of motivation and the myopic-follower setting has not been resolved yet.  Also, the discussion on the issues studied in Balcan et al. (2015) is not provided.  Please also note that (Jin et al., '20b) also proposes an optimistic variant of LSVI, and the exact algorithmic contributions still have some unclarity.
Decision: Reject