Towards General Function Approximation in Zero-Sum Markov Games
Authors: Baihe Huang
Jason D. Lee
Zhaoran Wang
Zhuoran Yang
Venue: ICLR 2022 Poster (2022)

Abstract: This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. The study focuses on the challenging settings where the value
function or the model is parameterized by general function classes. Provably efficient
algorithms for both decoupled and coordinated settings are developed. In the decoupled setting where the agent controls a single player and plays against an arbitrary opponent, we propose a new model-free algorithm. The sample complexity is governed by the Minimax Eluder dimension—a new dimension of the function class in Markov games. As a special case, this method improves the state-of-the-art algorithm
by a $\sqrt{d}$ factor in the regret when the reward function and transition kernel are parameterized with d-dimensional linear features. In the coordinated setting where both
players are controlled by the agent, we propose a model-based algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample complexity can
be bounded by a generalization of Witness rank to Markov games. The model-free
algorithm enjoys a  $\sqrt{K}$-regret upper bound where $K$ is the number of episodes. Our
algorithms are based on new techniques of alternate optimism

Published as a conference paper at ICLR 2022
TOWARDS GENERAL FUNCTION APPROXIMATION IN ZERO-SUM MARKOV GAMES
Baihe Huang
Jason D. Lee
School Mathematical Sciences Peking University
Department of Electrical and Computer Engincering
Princeton University
ba baihehuung@@pku.ce .dw.kkuuedd.coo.
Jasond @esondd@priii www.dldddniintnnncoommmmm wnw.ooneeee.
Zhaoran Wang
Departments of Industrial Engineering & Management Sciences
Northwestern University
zhaoranwang8gmaii
Zhuoran Yang
Department of Statistics and Data Science
Yale University
zhuoran. yanggyall..eeeee .dd
ABSTRACT
This paper considers two-player zero-sum finite-horizon Markov games with si- multaneous moves. The study focuses on the challenging settings where the value function or the model is parameterized by general function classes. Provably effi- cient algorithms for both decoupled and coordinated settings are developed. In the decoupled setting where the agent controls a single player and plays against an ar- bitrary opponent, propose new model-free algorithm. The sample complexity is governed by the Minimax Eluder dimension-4 new dimension of the function class in Markov games. As special case, this method improves the state-of-the-art algorithm by a vdl factor in the regret when the reward function and transition kernel are parameterized with d-dimensional linear features. In the coordinated setting where both players are controlled by the agent, we propose a model- -ased algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample complexity can be bounded by generalization of Witness rank to Markov games. The model-free algorithm enjoys a V K-regret upper bound where K is the number of episodes.
INTRODUCTION
In competitive reinforcement learning, there are two agents competing against each other by taking actions. Their actions together determine the state evolutions and rewards. Function approximation. especially deep neural networks (LeCun et al. 2015), contributes to the success of RL many real world applications, such Atari (Mnih et al. 2013). Go Siiver et al.) 2015), autonomous driving Shalev-Shwarte et al. 2016), Texas holdem poker (Sandholm 2017), and Dota (Berner et al. 2019).
The goal of competitive reinforcement learning aims to learn the Nash Equilibrium (NE) policy in trial-and-crron fashion. In a NE, no agent can be better off by unilaterally deviating from her policy. Most of the existing sample efficient competitive RL algorithms focus the tabular linear function approximation cases (Pérolat et al.) 2017; Bai & Jin. 2020 Bai et al. 2021 2020 Xie et al.) 2020 Zhang al. 2020). The huge empirical success of neural network based RL methods has remained largely unexplained. Thus, there exists a wide gap between theory and practice in competitive RL with general function approximation. One demanding question ask is:
Can establish provably efficient competitive RI algorithms with general function approximation?

---

Published as a conference paper at ICLR 2022
In this paper, make step towards answering this question by providing structural conditions and complexity measures of Markov Games and function classes that allow for efficient learning. We focus on episodic zero-sum Markov Game (MG) with simultancous move, where each episode consists of H time steps and two players act simultaneously at each time step. The state space is arbitrarily large and can be infinite. We consider two function approximation settings: 1) use general function class F' to approximate the action-value function (Q function); 2) use a general function class M to approximate the environment.
To this end, we introduce algorithms based on optimistic principles. Due to subtle game-theoretic issues, naive optimism is no longer working in Markov games where minimax optimization is per- formed. To deal with this issue, we use the algorithmic idea called 'alternate optimism' Specifically, we develop algorithms for both coordinated and decoupled setting. the decoupled setting, the agent controls one player and plays against an arbitrary and potentially adversarial opponent. The sample efficiency is measured by the gap between the learned value and value of the Nash Equilibrium. In the coordinated setting, the agent controls both players and the goal is to find the approximate Nash Equilibrium, i.e. with small duality gap. We identify key complexity measures of function classes to examine the effectiveness of elimination. By doing so, we prove upper bounds on sample complexity and regrets of the presented procedures that are independent of the number of states.
Our contributions are summarized into the following two folds:
In the decoupled setting, we introduce Minimax Eluder dimension-a new complexity measure for competitive RL problems. We propose an algorithm that incurs at most O(HVārKlogyy
regret in K episodes where de denotes the Minimax Eluder di- mension NY= denotes the covering number of function class, with probability least 1 p. As a special case, this result improves Xie et al. (2020) by vd multiplicative factor in their setting when the reward function and transition kernel are linearly parameterized and d is the dimension of feature mapping.
In coordinated settings, we propose both model- and model free algorithms. In the model-based setting, we generalize the witness rank (Sun et al.) (2019) to competitive
RL. We prove that O(H$W2/e") samples enough to learn a policy e-close to the Nash Equilibrium, where W is witness rank. In the model-free setting, we develop algo- rithm for agnostic learning with candidate policy class II. The algorithm incurs at most Õ(H / log(W=N11) regret. Here is variant of Minimax Eluder dimension and Ni denotes the covering number of policy class.
1.1 RELATED WORKS
There is rich literature studying the learning and decisionnmakingg of Markov Games
|Lttmmnn &
Szepesvari] 1996; Greenwald et al. 2003 Grau- et al., 2018 Pérolat et al., 2018 Srinivasan
et al. 2018 8, Sidford et al. 2020; Wei et al. 2017 Pérolat et |l.7 Bai & Jin. 2020 Bai et al.
2021 2020 Zhang ct al. 2020 Zhao et al. 2021). The most related to us are perhaps (Xie et al.
2020 Chen et al. 202 1 Jin et al. [b2 where the authors address the challenge of exploration-
exploitation tradeoff in large state spaces. Due to space constraint, a detailed literature discussion is
deferred to Appendix
PRELIMINARIES
We consider two-player zero-ssunerruun zem simultaneous-mover episodic Markov game, defined by the tuple (S,A1, Ag, r, H),, where S is the state space, A, is a finite set of actions that player i 2) can take, r is the reward function, IP is the transition kernel and H/ is the number of time steps. At each time step h E [.f]. player Pl and P2 take actions E Ag and 6 E A₂ respectively upon observing the state x E S, and then both receive the reward rh (I, a, b). The system then transitions to a new state x' ~ PA (- |z. a, b) according to the transition kernel I.. Throughout this paper, assume for simplicity that Ai = A = A and that the rewards rn (x, a, b) are deterministic functions of the tuple (xr, a, b) taking values in [-1, 1]. Turn-based games are special cases of simultaneous games in the
We use ① to hide logarithmic terms in H, 1/p and K.
2

---

Published as a conference paper at ICLR 2022
sense that at each state the reward and transition are independent of one player's action (Xie et al. 2020). Generalizations to A1 # Ag and stochastic reward are also straightforward.
Denote by == == ((A) the probability simplex over the action space A. A stochastic policy of P1 is a length- H sequence functions π := {TA : + A [ At each step E [H] and state æ E S, PI takes an action sampled from the distribution Ty (a:) over A. Similarly, a stochastic policy of P2 is given by the sequence ;= { S + A [ The learning happens in K episodes. In each episode ki each player P1 and P2 proposes policy & and v* respectively based history up the end of episode k and then executes the policy to observe the trajectories {2% dh y/1 hJh=1
For fixed policy pair (TT, p), the value function and Q functions for zero-sum game defined by
V
hg (x)
Σ
Th (a one 2 = x
ho
b
Qhe (z, = E
Σ
Th (Tn, ahe bn) 2, aho a, bho b)
Lh=ba
where the expectation is over ap Th (Thh), by ~ 1% (2x) and #h+1 ~ Pa((|ar4,, ah, bn). V and QT are often abbreviated to V* and Q In zero-sum games, PI aims to maximize V* (x1) and P2 aims to minimize (x1). Given policy æ of Pl, the best response policy P2 is defined by V argmin, V*." (21). Similarly given policy y of P2, the best response policy of P1 is defined by T. == argmax, Va. (21). Then from definitions,
(x1))(z)) & V* M² (x1) S (x1)
and the equality holds for the Nash Equilibrium (NE) of the game (r* v²). We abbreviate V PM (x1) V and Q (xr as Q'. V* is often referred as the value of the game. As common in Markov games literature (Pérolat et al. 2013), we will use the following Bellman operator
ThQu+1 (2, a. b) == r(x, a. +
E
[max min E e (ntr(a'....))
"²
and the following Bellman operator for fixed PI's policy Tx T#Q a, b) == r(x, a, b) +
mmi E Qutile',' ((
(2)
For a finite set S, |S] denotes its cardinality. For matrix A E Rd, A,,, x and A,, denote the i-th row and j-th column of A respectively. For function f S R. |] denotes sup.es (f()). We use (F,,)) e) to denote the e-covering number of F under metric ((f.9) max, Ilfn Iol.
Notations For a integer H, [H] denotes the set {1, 2, .,., H..
3 DECOUPLED SETTING
In decoupled setting, the algorithm controls P1 to play against P2. In k-th episode, P1 chooses a policy n and P2 chooses a policy x based on R² Then P1 and P2 interact in the Markov Game by playing x² and r² respectively, and observe the rewards and states in this episode. Notice that P2 can be adversarial and its policy is never revealed, meaning that PI can only maximize its reward by playing n². The goal is to thus minimize the following "value regret'
K
Reg = -v V (x1)).
(3)
k=1
small value regret indicates that we learn the value of MG. If an algorithm obtains an upper bound on value regret that scales sublinearly with K for all v* then it can not be exploited by opponents.
3.1 FUNCTION APPROXIMATION
We consider function class F= F1 x ... FH where Fú S X (0, to provide function approximations for Q" the fuuuctio of Nash Equilibrium. For policy pair (I, and function ff we abuse the notations and use f (a, म. v) = [f a, b)] to denote the expected reward of executing (H, v) in function We make the following assumptions about F.
3

---

Published as a conference paper at ICLR 2022
Assumption 3.1 (Realizability). We assume Qi for all h E [H]. Assumption 3.2 (Completeness). We assume for all E [H]] and f E Fh+1. Taf E Fi.
Realizability means the function class contains the target Q function. Completeness says the function class is closed under the Bellman operator. These assumptions are common in value function approximation literature (e.g. JJin et al. (2020); WWang et al. (2220b); Jin et al. (202Ia)). Note that they are weaker than Xie et al. (2020). as their setting satisties 7JJ E F for any action-value function f.
For function
F, we denote the max-min policy of P1 by TT. Specifically, (TT))(())= == arginax, min fn (1,, n, v), vh E [H].
Similarly we denote the min-max policy of P2 by vy. Given policy of P1, the best response policy of P2 in terms of function f is defined by
(v4) (z) == argmin,, (z, TA. v), wh [H]
Similarly given policy v of P2, the best response policy of P1 in terms of function f is denoted by xt/- When there is no confusion, we will drop the subscript h for simplicity.
Learnability requires the function class to have bounded complexity. We introduce Minimax Eluder dimension to capture the structural complexity of function classes in zero-sum games. To define. we use e-independence of distributions and Distributional Eluder dimension (DE) from Russo & Van Roy (2013): Jin et al. 12)
Definition 3.3 (e-nddependence of distributions). Let G be a function class defined on X, and v, Mi..... Mn be probability measures over X. We say that is e-independent of ( Fn with respect to G if there exists g E 9 such that V (E ( S but [B]] 2
Definition 3.4 (Distributional Eluder dimension (DE)). Lei G be a function class defined on X, and D be a family of probubility measures over X. The distributional Eluder dimension dimpr(G, DD, is the length of the longest sequence {P1,-... PPa} C 'D such that there exists e' 2 6 where Ps is e' t-independent of (PI....,PP-11 for all E [n).
Now we introduce Minimax Eluder dimension. Recall the minimax Bellman operator from Eq ( Tafn+1 (z, a. b) == r(z, a. s'~Pa(( b. s/
E
[max min fa+1(=', (1',,','',,, n', ,/)]
thus Minimax Eluder dimension is the Eluder dimension on the Bellman residues with respect to the above minimax Bellman operator.
Definition 3.5 (Minimax Eluder dimension). Let (I (I=T {fn - Taff++ FE be the class of minimax residuals induced by function class F at level h and Da (DA,,) HE(H where Da,k {8(z, b) S.a E A1, b E A2} is the set of Dirac measures state-action pair (I, a, b). The Minimax Eluder dimension of F is defined by dimme
== max dimpe( ([I-))([[)FF F,, c).
3.2 OPTIMISTIC NASH ELIMINATION FOR MARKOV GAMES
Now introduce Optimistic Nash Elimination for Markov Games (ONEMG), presented in Algo- rithm 1 This algorithm maintains a confidence set y that always contains the Q", and sequentially eliminates inaccurate hypothesis from it. In k-th episode, P1 first optimally chooses a value function f* in kー that maximizes the value of the game. Intuitively, this step performs optimistic planning in the pessimistic scenarios, i.c. assuming P2 plays the best response. Next, it plays against P2 and augments the data from this episode into replay buffer B. The confidence set y is then updated by keeping the functions with small minimax Bellman errors fn Trfh+1, in Line 12 To estimate fn - ThJt+,, we use εB, (Jh, fn+1) ge,, &s, (g, fn+1), standard variance reduction trick to avoid the double-sample issue. can be shown that when the value function class is complete, Ep,
inf F, EB, (g. f(+1) is unbiased estimator of fn Twfh+1 (Lemmaa B.I.
Notice that unlike many previous works that add optimistic bonus on every state-action pairs XXi et al. 2020 Chen et al.) 2021), Algorithm| | only takes optimism in the initial state. Instead, the constraint set contains every function that has low Bellman residue on all trajectories in the replay buffer. This 'global optimism' technique trades computational efficiency for better sample complexity, and can be found in many previous work in Markov Decision process (Zanette et al.) 2020; Jin et al. 2021ab. As will see later, it is also useful in the coordinated setting.
4

---

Published as a conference paper at ICLR 2022
Algorithm Optimistic Nash Elimination for Markov Games (ONEMG)
1: Input: Function class FF
2: Initialize B, = E [H], Vo
+F
3: Set B <- Colog(N( 1/K) HK/p) for some large constant C
4: for = 1,2..... K do
5: Compute f argmax fe TT, let Th xz
6: for step = 1, 2, 2,..., H do
7:
Interact with environment by playing action at (x(())))))) Observe reward r opponent's action bf, and move next state x² 1/+1 end for
8:
9:
10:
Update B₁ BB U {(a oi Uh rh, +1)) wh E (H]
11:
For all E and h [H) let
EB, (En, Sh++1) =
Σ [En(ah oh b%) r - TC 1. )]
Set
vb + IfF (hn fn+1) S inf EB, (g. fa+1) + + e [M]
getn
end for
3.3 THEORETICAL RESULTS
In this section we present the theoretical guarantee for Algorithm Appendix [
The proof is deferred to
Theorem 3.6. Under Assumption 3.1 and Assumption 3.2 the regret Eq of Algorithm Tis upper bounded by
Reg( ()) s o H HVK dME log(HK()
with probability at least 1 p. Here dME dimMe(F, VI/K) and < (/(,,1/KK)/p
As this theorem suggests, as long as the function class has finite Minimax Eluder dimension and covering number, Pl can achieve VK-regret against P2. Notice that when P2 always plays the best response of Pl's policies, this regret guarantee indicates that algorithm eventually learns the Nash Equilibrium, In this case, the algorithm takes 2 ddH2dlog(e (lo((())))) samples to learn a policy æ that e-close to =.
When the opponent plays dummy actions, the Markov Game can be seen as an MDP and the value of the Markov Game is the maximum cumulative sum of rewards one can achieve in this MDP. In this case, our result reduces to Ö(H /K- dBE (og(N(FF,1KK) where dBE is the Bellman eluder dimension in Jin et al. (021a))
In particular, when the function class is finite, the regret becomes O(H / /KME log(H FF)/)) that depends logarithmically on cardinality of F. Moreover, when the reward and transition kernel have linear structures, i.e. Tha (2, a, b) 6(x, a, b) 0,, and PA a, b) d(x, a, b) (%,()) log (FF,
where Φxx, a,
Rd. then dME(F, 1/KK Ō O(Hdy K) Thus we improve Xie et al. (020) by a v factor. We also provide simpler algorithm tailored for this setting, see Appendix B.I for details.
(dd and the regret becomes
Algorithm solves non-convex optimization problem in Line 5 with highly non-convex constraint computationally inefficient. Even when reduced to linear MDP, ie. the opponent plays dummy actions and the transition matrices and the rewards have low rank structures, it is not known if the same Ö(H regret can be achieved with computationally efficient algorithms (Zanette et al., 2020). Designing computationally efficient algorithms with near-optimal sample efficiency is interesting further direction.
(Line [2p. In general,
Here use θ to omit the logarithm factors in K, d, H and 1/p.

---

This Published as a conference paper at ICLR 2022
4 COORDINATED SETTING
In the coordinated setting, the agent can control both P1 and P2. The goal is to find the e-approximate Nash equilibrium (T, v) in the sense that
V (21)
c
(4)
by playing PI and P2 against each other in the Markov game, In the following sections, we propose both model-based and model-free methods to deal with this problem.
4.1 MODEL-BASED ALGORITHM
In model-based methods, we make use of model class M of candidate models to approximate the true model M We are also given test function class G to track model misfit. Given model M E M, we use Q² (z, a, b), r- (x, a, b) and Ip-d (-Jar, a, b) to denote the Q-function, reward function and transition kernel of executing action and b at state in model M. For simplicity, use (r, x) ~ M to represent r ~ rM (z, a, b) and x ~ IPM (-|x, a, b). We denote the NE policy in model M as π and yM For policy and model M, we use D to denote the best response of in model M and M is defined similarly.
4.1.1 ALTERNATE OPTIMISTIC MODEL ELIMINATION (AOME)
The model-based method, Alternte Optimistic Model Elimination (AOME), is presented in Algo- rithm 4 It maintains a constraint set M* of candidate models. Throughout K iterations, AOME makes sure that the true model M always belongs M for all k: E [K], and sequentially eliminates incorrect models from M
However, the idea of being optimistic only initial state (Zanette al. 2020 Jin al. 2021a) is not directly applicable to this scenario. Since the objective to be optimized is the duality gap, the target policies being considered are thus policies pairs (Iī, 2/) and (π, v/) However, म. and V are not available to the agents. Therefore, the performances of proposed policies are evaluated on -iitt--distiitttion trajectories, meaning that optimism can not be guaranteed. This causes the distribution shift issue. In worst cases, low Bellman errors in the collected trajectories provide no information for the trajectories collected by π., v and æ, V
To address this issue, the algorithm performs global planning by applying the idea of alternate optimism to model-based methods. In k-th episode, the algorithm first solves the optimization problem M = arg maxMeM QM (I1, TM, D and let x² = _M, This optimization problem corresponds finding the optimistic estimate of the value of the game. Indeed, notice that M E MM M implies QM (x1, * v*) 2 QM' (I1, nh 1x* 2 V (21)), by optimality of MP. Next, it solves the second optimization problem M = arg MinMEM QM (x), Mf (M) and let v + 1 MM corresponds to finding the pessimistic estimate of V** M"* (æ1). In fact, we see that M E _M implies ( - n²² < -** Pi (z by optimality of M.. This approach appears in Wei et al.
(201)) to guarantee convergence to Nash equilibrium, where it is referred to as 'Maaximn-EVI..
In Line 8 the algorithm checks if the values of model M and Ma are close to the value of the true model 1 when executing policy T and v If the condition holds, we have
(=(x1) y= 2 (x1) S QMM (II, Th , Q Ma (II, " ,1,)
which means that AOME finds policy -² that is e-close the NE. One can also switch the order of alternate optimism and obtain 5² that is e-close the NE. We then terminate the process and output T² and k If the algorithm does not terminate Line 8 it applies the witnessed model misfit checking method in Sun al. (2019a). It starts by computing the empirical Bellman error of Markov games defined as follows
Z(M, M,
10 (1h, b/) - (ri. + QN (ch+1, nT MM, )}.
(5)
n2

---

Published as a conference paper at ICLR 2022
As proved in Appendix D in this case L(M MM MM, hh*) must be greater than (/(8) for some j E [2] and h E [H]. Then the algorithm samples additional trajectories at level h* and shrinks the constraint set by eliminating models with large empirical model misfit, which is defined as follow
E(M M2 M,
sup Σ n (THMA))
E
Is(an M ohs Uig Thy m6) - g( anp b/ The ++1])
(6)
SEG
We will show that this constraint set maintains more and more accurate models of the environment. Due to space constraints, the algorithm and theory of our model- bosell-baedd method are deferred to Appendix C
4.2 MODEL FREE ALGORITHM
In this section we propose model-free algorithm. We consider more general agnostic learning, where The algorithm is given a policy class II II, x xI. with II, C {TA + A}, h II
[H]. Notice by letting II to be the class of NE policies induced by the action-value function class F, we recover the original setup. The goal is to find policy π and V from II to minimize the duality gap: max Va' v min VaL', by playing only policies from IT. Since only policies from II are considered, we overload the notation and define the optimal solution in II as v² arg ea min Va."" and v² arg minvgn m V When II contains all possible policies, π² and v² is then the Nash equilibrium.
FH where Fn C {f S x A x A + []] We overload the notations in Section and use vf to de- note the best response of π from II, namely vf (x) argmin (z, n, v). Similarly, we use Ty T == argmax, een mniineuu f(z, क. v). We also use v² == argmin ven Va." to denote the best
Similar Section
consider general function class J Fi
response of i in the true model.
4.2.1 ALTERNATE OPTIMISTIC VALUE ELIMINATION (AOVE)
Notice that the duality gap be decomposed as follows
gap V
V R2"
V
V
Vx
P2
Optimal
P1
where the optimal part V V* is fixed. Therefore we can consider only the P1 part here and the follows by symmetry. We are interested in the following policy regret
K
Reg(K) = Σ -
k=1
Policy regret measures the extent that P1 can be exploited by policies in II. Our algorithm Alternate Optimistic Value Elimination (AOVE), presented in Algorithm 2 works minimizing this regret. Similar to Algorithm [] it also uses optimism in the initial state to address exploration and exploitation trade-off and constructs series of confidence sets of hypotheses with small Bellman errors. The differences primarily lie in a different choice of optimism and a different series of confidence sets constructed with the Bellman operator in Eq Since the policy class 11 is taken into consideration. the algorithm maintains a constraint set B C x F of policy-function pairs. We use the Bellman operator with regard fixed P1's 's policy, Eq (2) Thus intuitively, this constraint set maintains (r,, f) pairs such that fn TT." fa+1 is small for all ha E [H].
We apply the 'alternate optimistic principle, presented in Line Line and Line
Intuitively, the algorithm finds an optimistic planning of π and pessimistic planning of together corresponding to max-min procedure. As such, we form an upper bound (11, π,, v 91 (æ1, n* v² of the duality gap. Note that it is different from the 'alternate optimistic' used in model-based settings Wei et al. (017)) in that the hypothesis chosen in Line constrained by the policy chosen in Line This is because in model- based methods, 'plausible' models in the confidence set guarantee small simulation errors (Lemma C.6). However, this is not true for 'plausible' value functions in the confidence set.
The rest of the algorithm aims at minimizing this upper bound sequentially by eliminating bad hypothesis in the constraint set. The elimination process occurs in Line [3] where the algo- rithm uses history data to eliminate functions with large Bellman emror. To estimate Bellman
7

---

Published as a conference paper at ICLR 2022
error, use the similar method in Algorithm 1 i.c. subtracting the variance of Tk fi+t1 by = arg ingggff,FF ED, (g. fh-1. r). Notice that a smaller value fn - T7," fi+1 indicates that function approximation f is not easily exploited by P2 when Pl plays π.
As shown in Appendix D T (*) is always in the constraint set, and the Bellman errors of the rest hypothesis keep shrinking. Thus in the presented algorithm of AOVE, the regret of P1 part V= - V=. is controlled. By symmetry, obtain upper bound on V Va Combining these together, we show sublinear regret rate of V=..."" V "**., By regret to PAC conversion, this means that we find the policies that is the best achievable in II.
can perform the same procedures on P2 part and
Algorithm 2 Alternate Optimistic Value Elimination (AOVE)
1: Input: Function class F, policy class II
2: Initialize 13" + II x F
3: Set B
HK/p) p) for some large constant C
4: for k = 1,
K do
5: Find (T fk) argmax (x, (aa.iiev-iii(a (1 v
6: Let < argmin 91 (11,Th Th v and set v + 2
(n (1 g)v
7:
for step 1,2 H do
8:
Pl takes action of ~ (*))) P2 takes action by ~ v (27))
9:
Observe reward r and move to next state oftt1 end for
10:
11:
Update B₁ + BB U (12h a by, rhe 2h wh E [H]
12:
For all E, E F R E Il and h E [H], let
k
EB, Sh+1,
En (17 ah bT) r -h (f 1)
13:
Update
U < F: EB, (Jho 11+1, S inf EB, (g. Sa+1, + B, wh (H])
geFr
14: end for
4.2.2 THEORETICAL RESULTS
This section presents our theoretical guarantees of Algorithm 2 First, we introduce two assumptions that take the policy class II into consideration. Variants of these assumptions also common in batch RI. (Jin et al. 2021c Xie et al. (021).
Assumption 4.1 (T--ralizabilltty) For all II, QT F.F
Assumption 4.2 (IIccompleteness), For all h E [H], II and f Fitz, T E Fv holds.
Notice that Assumption 4.2 reduces to Q" realizability in MDP. Both two assumptions hold for Linatt-paramettriieed Markov games studied in Xie et al. (2020). In fact, Xie al. (2020) satisfies stronger property: for any policy pair and any h E [H]. there exists a vector w E R such that
2 (x, a, b) = w ToTT(z, b)b), V(z,a Ex A2.
First, introduce the complexity measure in coordinated setting, which is a variant of Minimax Eluder dimension by replacing the Bellman operator Eq ① with Eq (2). This Minimax Eluder dimension also allows a distribution family induced by function class F which is cheap to evaluate in large state space (Jin et al.) 2021a).
Now we present the theory of Algorithm 2
Definition 4.3 (Minimax Eluder dimension in Coordinated setting). Let (1-T) (1-Thll4ty T.Il++ Uh T fa+t : E F.T E 11++1} be the class of residuals induced by the Bellman operator T Consider the following distribution families: 1) DA (Da,nhel where DAn () S,a E b A2) is the set of Dirac measures on state-action
8

---

Published as a conference paper at ICLR 2022
pair (z. a, 2) Dz {D helm which is generated by executing (IT,, ) for f.g E F. The e-Minimax Eluder dimension (in coordinated setting) of F is defined by dimmE (F,)) ==
ma minDe (Pa.p(PPaPs) dimpe
FF, -h -
Now we present our main theory of Algorithm 2 where we make use of a variant of Minimax Eluder dimension that depends on policy class II. We use (III c) to denote the covering number of II under metric d(n x') == [ J..x).FF.EEE
(I, ग. b) - f(z T'bb).
Theorem 4.4. Suppose Assumption 4.1 and Assumption 4.2 holds. With probability at least 1 p
have the regret (Eq. ( of Algoritim upper bounded by
Reg( K) O (HVK K daa log [
where dME = dimme (F, /)/K) K) and Ç
1/K)/P
As shown in this theorem, the regret is sub-linear in number of episodes K and Eluder dimen- sion dME which match the regret bound in Markov decision process, e.g. in Jin al. (2021a) Through regret-to-PAC conversion, with high probability the algorithm can find c-optimal policy with O (H K log[N(FF 1/ (II,, 1/ H k/pl/²²) sample complexity. When the reward and transition kernel have linear structures, we also recover the Ö(vd* K) regret Xie et al. 22200).
Although our upper bound depends on the logarithm of covering number of I1, there are some cases when it is small. For example, when the value-function class F is finite and II is the induced policy class of JF defined by II { v g/ f.g F}, then logNN((e) log [F] and the regret is
OHH v KdME log" [F). Similarly, if the model class M is finite and II is induced policy class of M defined by II {TM, a M' E Mj. then log (n) log [M] and the regret is Ö( KdMEy log" [M). In agnostic setting which allows II to have arbitrary structure, the term log (TI, / reflects the difficulty of learning with complex candidate policy sets and conjecture that this term is inevitable.
Similar to Algorithm I Algorithmm solves non-convex optimization problem in Line 5 with highly non-convex constraint set (Line [3) This step is particularly difficult when the function class has complex structures. Algorithm 2 in general computationally inefficient, even in cases of linear function approximations. Indeed, even when the model is known, solving for the NE is PPAD complete. Developing decentralized and provably efficient RL algorithm for multi-agent Markov game seems challenging but interesting future direction.
5 DISCUSSION
In this paper we study function approximations in zero-sum simultaneous move Markov games. We design sample efficient algorithms for both decoupled and coordinated learning settings and propose Minimax Eluder dimension to characterize the complexity of decision making with value function approximation. The analysis shows vT regret bounds and half-order dependence on the Minimax Eluder dimension, matching the results in MDPs and improving the linear function approximations. Our algorithms for coordinated setting are based on the idea of the 'alternate optimism', which also shows applicability in model-bag based methods.
ACKNOWLEDGEMENTS
BH is supported by the Elite Undergraduate Training Program of School of Mathematical Sciences at Peking University. JDL acknowledges support of the ARO under MURI Award W91 101IN-111- 0304, the Sloan Research Fellowship. NSF CCF 2002272, NSF IIS 2107304, and an ONR Young Investigator Award.
REFERENCES
Yasin Abbasi- Yadkori, Nevena Lazic, Csaba Szepesvari, and Gellert Weisz, Exploration-enhane POLITEX. arXiv preprint -ix:11908 10479, 2019.

---

Published as a conference paper at ICLR 2022
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert E. Schapire. Contextual bandit learning with predictable rewards. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), 2012.
Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradi- ent methods: Optimality, approximation, and distribution shift. arXiv preprint arXiv: 1akiv:190..00 190800021,, 2020.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via paramcterization. In International Conference on Machine Learning (ICML), pp. 242-252, 2019.
Mohammad Gheshlaghi Azar, lan Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 263-272. JMLR. org, 2017.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning, arXiv preprint arXiv:2002.04017, 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-effiientt learning of stackelberg equilibria in general-sum games. arXiv preprint arXiv:2102.1 1494, 2021.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the 12th International Conference on Machine Learning, 1995.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, and Chris Hesse. Dota with large scale deep reinforcement learning. arXiv preprint 19iv:1912.06666 2019.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in neural information processing systems (NeurIPS), 2019.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv preprint 11X1v2210..07404, 2021. 2021.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), pp. 1675-1685. PMLR, 2019a.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning. pp. 1665-16744 PMLR, 2019b.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-paraan peeeraaraattee neural networks. In International Conference on Learning Representations (ICLR), 2019c.
Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint arXiv:2103.10897, 2021.
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pp. 486 489. PMLR, 2020.
Jordi Grau-Moya, Felix Leibfried, and Haitham Bou-Ammar. Balancing two-player stochastic games with soft Q-learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 268-274, 2018
Amy Greenwald, Keith Hall, and Roberto Serrano. Correlated Q-learning. In International Conference Machine Learning, volume 20, pp. 242, 2003.
10

---

Published as a conference paper at ICLR 2022
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems (NeurIPS), pp. 8571-85888 2018.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, volume 11, pp. 1563-1600, 2010.
Zeyu Jia, Lin F. Yang, and Mengdi Wang. Feature-based Q-learning for two-player stochastic games. arXiv preprint arXiv: 19990000422, 2019.
Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert E. Schapire. Contex- tual decision processes with low bellman rank are pac-learnable arXiv preprint arXiv:1610.09512, 2016.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are PAC-leamable. In Proceedings of the 34th International Conference Machine Coarning-Volumme 70, pp. 1704-1713, JMLR. org, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 48644443444 4873, 2018.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Thheory pp. 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00875. 2021a.
Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent rl in large state spaces. arXiv preprint mrXiv:2106.03352, 2021b.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference Machine Learning (ICML), 2021c
Michail G. Lagoudakis and Ronald Parr. Value function approximation in zero-sum markov games. In Proceedings of the Eighteenth conference on Uncertainty in artificial intelligence, pp. 283-292. Morgan Kaufmann Publishers Inc., 2002.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
Michael L. Littman and Csaba Szepesvari. generalized reinforcement-leamine model: Convergence and applications. In 13th International Conference Machine Learning, 1996.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint 1tXiv:1906.10300 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learningep reinforcement learning. arXiv preprint w.X.vv1112..50. 2013.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems (NeurIPS), 2014.
Julien Pérolat, 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 2015.
Julien Pérolat, Florian Strub, Bilal Piot, and Olivier Pietquin. Learning nash equilibrium for general- sum markov games from batch data. In Artificial Intelligence and Statistics, pp. 232-241. PMLR, 2017.
Julien Pérolat, Bilal Piot, and Olivier Pietquin. Actor-critic fictitious play in simultancous move multistage games. International Conference on Artificial Intelligence and Statistics, pp. 919-928, 2018.
11

---

Published as a conference paper at ICLR 2022
Daniel Russo. Corst-case regret bounds for exploration via randomized value functions. In Advances in Neural Information Processing Systems, pp. 14410-14420, 2019.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, 2013.
Tuomas Sandholm. Super-human ai for strategic reasoning: Beating top pros in heads-up no-limit texas hold'em. In International Joint Conference on Artificial Intelligence, pp. 24 24-25, 2017.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.032295, 2016.
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.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, and Marc Lanctot. Mastering the game of go with deep neural networks and tree search. Applied and Computational Harmonic Analysis, 529(7587):484 489, 2015.
Sriram Srinivasan, Mare Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environments. In Advances Neural information Processing Systems, pp. 3422-3435, 2018
Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. PAC model- free reinforcement learning. In Proceedings of the 23rd International Conference Machine Learning, pp. 881-888, 2006.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. Xiv preprint arXiv:1811.08..
2019a.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theory (COLT). arXiv preprint 1:Xiv:1811:085555 2019b.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global
optimality and rates of convergence. arXiv preprint arXiv: 150, 2020a.
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005.1000 10804, 2020b.
Yining Wang, Ruosong Wang, Simon S. Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. In International Conference on Learning Representations, 2021.
Chen-Yu Yu Wei, Yi-Te Hong, and Chi-Jen Lu, Online reinforcement learning in stochastic games, In Advances in Neural Information Processing Systems. pp. 4987-4997, 2017.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. In Conference on Learning Theory (COLT), arXiv preprint arXiv:2002.07066, 2020.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. In Advances in neural information processing systems (NeurIPS), 2021.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:201 I. 04622, 2020.
12

---

Published as a conference paper at ICLR 2022
Andrea Zanette and Emma Brunskill. Tighter problem-dependeed regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. arXiv preprint arXiv:2003.00153, 2020.
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprint arXiv:2007.07461. 2020.
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 arXiv:2102.08903, 2021.
13

---

Published as a conference paper at ICLR 2022
A ADDITIONAL RELATED WORKS
There is rich literature on sample complexity for single agent RL, mostly focusing on the tabular
cases (Strehl et al. 2006; Jaksch et al.) 2010 Azar et al.
2017; Jin et al. 2018 Russo 2019
Zanette & Brunskill 2019) and the linear function approximations Yang & Wang 2020 Wang et al.
20bas Yadkori et al. 2019 Jin et al. 2020 Du et al. 2019b). For neural network function approximations, Agarwal et al. (2020] Liu et al. (2019); Wang et al. (2020a); Yang et al. (2020) builds provably efficient algorithms on over wwrrpparaeeteiiee models. The issue is complicated for general function approximation,
the Q function is hard to learn due to the double-sample issue (Baird 1995). In recent years, a line of work studies the structural properties and corresponding complexity measures that allow generalization in RL. These work can be roughly grouped with two catagories. One studies structures with low information gain. Jiang et al. (2017) proposes Bellman rank and designs sample efficient algorithm for a large family MDPs. Later, Sun et al. (2019b) proposes Witness rank and uses this notion to provide a provably efficient model-based RL algorithm. Recently, Du et al. (202T) proposes Bilinear family and the corresponding Bilinear rank that encapsulates wide variety of structural properties, spanning from both model-based to model-free function approximations. The other studies structures with low Eluder dimension (Russo & Van Roy| 2013). Osband & Van Roy (2014) extends Eluder dimension to reinforcement learning and provides unified analysis of model based methods where the regret is controlled by the Kolmogorov dimension and Eluder dimension of model function class. Waan et al. (2020b) designs model-free algorithm and shows that regret can be controlled by the Eluder dimension of the value function class. Recently, Jiin et al. (2021a) proposes Bellman Eluder dimension and builds new framework to capture large amount of structures. It is noted that although lots of structures, such as linear MDP (Jin et al. 2020), fit in both two viewpoints, they not equivalent. Among the above work, Jin al. (202 a): Zanette iet al. (020)) are more related. The method of placing uncertainty quantification on only imitial states, previously appeared in Zanette et al. (2020); Jin et al. (2021a). greatly simplifies the argument and improves sample complexity. The Minimax Eluder dimension is inspired by the Bellman Eluder dimension in iin et al. (2021a).
In competitive RL, the setting with access to a sampling oracle or well explored policies is well studied (Littman & Szepesvari 1996. Greenwald et al. 2003 Grau-Moya et al., 2018: 8 Pérolat et al. 2018 SSriivasan et al.) 2018 8 Sidford et al. 2020). Under these assumptions, many works consider function approximations (Lagoudakis & Parr 2002: Pérolat et al. 2015 Fan et al. 2020 Jia et al., 2019 Zhao et al. 2021). However, without strong sampling model a well explored policy, the issue of
tradeoff must be addressed. Most of these work focus on tabular setting
(Wei al. 2017 Pérollat et al. 2017 Bai & Jin., 2020 Bai et al.. 2021 2020 Zhang al. 2020 Zhao
jet al. 2021 or linear function approximation settings (Xie et al. 2020 Chen et al. 2021). Among
them. (Wei al. 2017 Xie et al. (2020) are more related. The regret-decomposition method used in the decoupled setting is inspired by Xie et al. (2020). The 'alternate optimism' used in A Algorithm 4 was previously used as Maximin-EVil in Wei al. (017)) although the 'alternate optimism' used in Algorithm 2 is different. Moreover, the concurrent work Ji et al. (0222) studies competitive
RL with general function approximation. They reach a sublinear O(VK) K) regret for MGs with low minimax Eluder dimensions in the decoupled setting. Their results in the coordinated setting are based on different assumptions and complexity measures. Specifically, they assume finite function class and an additional class of exploiters. It is noted that by letting the policy class be the class of optimal policies induced by the value function class, have [II| F and our algorithm achieves on-par guarantee in their setup in terms of the covering numbers of function classes. In addition, we propose a first provably sample efficient and model-basee algorithm for the coordinated setting with general function approximation.
A.1 TECHNICAL CHALLENGES
Previous work (Xie et al. 2020) imposes optimistic bonus on the action-value functions in every state- action pairs and performs planning by the Coarse Correlated Equilibrium (CCE) on the optimistic value functions. To achieve improved rates, we leverage the idea of 'global optimism' (Zanette et al.) 2020; Jin et al. 2021a Du et al. 2021), which maintains a constraint set of candidate functions that do not deviate much from the empirical estimates and performs optimistic planning the initial state. However, going beyond MDPs towards MGs, two problems arise. First, the concentration property of functions in constraint set is hard to characterize due to multi-agent interplay. For this,
14

---

Published as a conference paper at ICLR 2022
use the concentration methods in Jin et al. (2021a) and extend it from MDPs to MGs. The second and more prominent issue the exploration and exploitation tradeoff. Since "global optimism only obtains optimism along the trajectories of behaviour policies, it may not guarantee optimism on the trajectories of target policies (i.e. NE). As a result, directly using CCE to plan will cause the duality gaps to diverge. To deal with this problem, we apply 'alternate optimism' which was previously used in Wei et al. (2017) for model-based methods. The 'alternate optimism' used in this work slightly different for value-based methods. We prove two regret decomposition lemmata to support this optimism principle.
guide explorations,
B PROOF OF THEOREM 3.6
We prove the Theorem 3.6 in the following five steps. In the first step, we show that Bellman error is small for function in the constraint set. In the second step, we show that Q* stays in the constraint set throughout the algorithm. In the third step, we decompose the regret into a summation of Bellman error and Martingale difference. We can then bound the summation of Bellman error using Minimax Eluder dimension in step 4. Finally we combine the aforementioned steps and complete the proof of Theorem 3.6
We define 'optimistic" value function in step / and episode & as follows
VA (=x)) == fh (1%, The x/))
where 87 is the best response of T in value function f i.e., 1 == argmin, f (a x v). We use n² = [vx to denote the policy adopted by P2 in the k-th episode. Notice that the agent obtains knowledge from y only through its actions b/t, E [H].
Step 1: Low Bellman error in the constraint set We first use standard concentration procedure (Agarwal et al., 2012; Jin et al., (021a) to bound the Bellman error in constraint sets. Bellman error). Let p 0 be arbitrary fixed number. With probability at least 1 - for all (k, E [K] x [H] we have
Lemma B.1 (Concentration
k-1
E Σ (Jh oh. b)) rh. se (f
fhii (2, th oh4)))
+ 033).
Proof. Consider a fixed (k, h. f) sample, let
Ui(h, = (fr (2/,, ar, 61)) - r min max f1+1
- (Tnfh+i ahi bh,) rh min max fatz ( w/12
and Fr,h be the filtration induced by { af fi, o M (2f bi ri...., 2 ah B.J.
Recall the minimax Bellman operator
Trfn+1 a, b) = r(x, a, xt 2'
[min max (n (d', ,//,
We have
BlU,Ch, F(1.
= [(h Tn a/. b()) -Bffa ah, (),) + Tn. Tn.ti (2), ah b/.) 2r 2 mij In41(444as 33)
" at
[[h -Tnf++1) (2 ah. 11.
and
VarlUe(h, f) (l f))
1[hh Tr. (arh ahh 1/
(F((F ai, b))) + Tr.fn+t (2f, ah, bb.) - 2rf, 2mm max fa41 x x2,11)))13 Frm 366(fn-Trrhf Tw.fkt)) af, 06,11 36E F(.F
15

---

Published as a conference paper at ICLR 2022
By Freedman's 's inequality, we have with probability at least p.
5o( log(1/p)
Σ f1,
Σ (1,
Σ 1 log(L//)))
Let (FF P) be p-cover F. Taking a union bound for all (ki, h g) E [K] x [H] x (FF .).
then with probability least 1 p for all (ki g) [K] x [H]] N (FF, p)
Σ U.(h.g) Σ Kgn Thgh+1)(ah aj. )
Iian
50
Vin Thgn+))(f b/)) + +1)
(8)
where = log(HK (FF ..lpp))ppppp..)))) Let g ger maxne(H] I152 - I We immedi-
ately have
Σ Ut(h,gg)) - Σ Uigh TTgh+t ab. b1)1
$ 50
E 1oth -Thok Mrho 0,11 + 1).
(9)
For all (h, k) E [H] x [K], by the definition v and I E yk we have
k
Σ Uh, fh) = = Σ (#h ah, 0%) - rh min max fa+ (2h+1: HT, ,1)²
(h ag 1/)) rh. min max fh+1 T', v))2
(fh ai b%,) -rh min max f n', v'))
inf BEF t=1 s 00(1 kp).
Σ
(gn(s ahe by) rh min max Sn+1 w/)²
(10)
It thus follows that,
Σush - Tnthht ah, b1,)1 <
Σ
l9gh
(rhh 6,11 + O(1
1=1
0
+ k
Ue(h,g*)
1=1
0
U +
<((+
where the first step due to g is an p-approximation to f* the second step comes from Eq (9), the third step is due to g is p-approximation to fk, and the final step comes from Eq (0).
By definition of k and i* we have
ThS (x, a, = r(x, a, +
E (12,0,)))
J (2L, m/+1 Dh+1))
thus conclude the proof.
16

---

Published as a conference paper at ICLR 2022
Step 2: Q" is always in constraint set.
Lemma B.2. With probability at least - P. we have Q" Ve for all & E [K].
all
Proof. Consider fixed (k:, h f) sample, let
U,(h, = (Jn (1f, ois bi)) r/. min max Q% 11 TT, 1²
(Q% ohe bl:) r min max Qi+1 v/))
and Frn be the filtration induced by {2) aj bf ri.................... u b/
We have
ElUi(h, = 10hh (1h oj. b8)1
and
S 36(( - (hJ =6 f)
Let ( p) be p-cover of J. By Freedman's 's inequality, for all (k, f) [K] x [M]] x (FF,)) we have with probability at least - p.
k
Unh n) Eiv - (2) -i)a af b/
t=1
$ 50(1
k log(1/ /p)
Σ
105h -1) o/, [1))2 +00))
where = log(H (F, p)1/p)) Since [(fr - Qi) di b012 0, this implies
Σ (1
Therefore for all (k. h) E [K] [H] x (FF
(Qi(1 ahs (bh) - r/ min max Qi+1 ( ,')))
(Fa(o), af b%) rh min max Qh+1 (4 w/)) O(1 kp).
Thus we have proven that Q* E V* vk E [K] with probability at least
Remark B.3. This step implies that
V
(+
(11)
which ensures optimism from the beginning state ('global optimism') ").
The following result is key to our analysis. It decomposes the deviation from the value of the game into Bellman errors across time steps and a martingale difference sequence.
Step 3: Regret decomposition
Lemma B.4. Define
8/ = (xtt)) - Vir. (x)))
k Eloh il jatt att U/1 -
A E.
Uh (ath a ot)1 (wr att 1t)
am
10t w (a a, b)] - Q w (ot o
2h =
IR
a
17

---

Published as a conference paper at ICLR 2022
Then we have
8% S 0
Sh +
7% 2%
(12)
where ex is the bellman error defined by &o := (= ohs b%t
rh
E z- btt
sh+ (ar, -h D ph+1).
Proof. By definition of x argmin, ff (af = v), we have
s (wh nh vh) S 1 (ahh th bk:) 1 (ah ax bb)) + 7h-
thus follows that
0% 2 1 (1 ah, b%)) Qh "
(ahhahh b1t) + 7 - -
r + E
c. l th+1 ph+1) + chi
- (rh +
WN#1 1411 (x)la% an b/()) + 7h 7%
a
Sh (4t T ph x
V (chi+t) ch ch 7h k
7
= +1 ch + 7 7h + ch
Therefore we complete the proof.
Step 4: Bounding cumulative Bellman error using Minimax Eluder dimension. Recall that
Lemma B.I gives:
Σ (1h oh. bb) rh
E
fh (2 mh x11))) 0(3).
- P
Combining this and Lemma FI with gh (2()))
oh+1)
a-F(he))
and Pk 5( ar, 6%)), we have come to the following result.
Lemma B.5, For any (k, h)) E [K] x [H] we have
1 (ath ah Ma) -
E P- aattt) (t)
Sh+z1 (x. m wht1 Ph+1)l
1=1
0
K dimme /1/K) (T
Thus
K
o K dimme (gg 1/KK/))
(13)
Am
Step 5: Putting everything together
By Eq 11 and Eq 12
K
(v)(())) - Virt""" wnth (x Σ (m)
(w1)
V. w/th (x1)
K
ch
+
24h
+
Am1
1/
1=
18

---

Published as a conference paper at ICLR 2022
Notice that Ei= (- + + -%) is martingale difference sequence and can be bounded by O(H / KK HoggoHHH//p with probability at least
p.
By Eq 13 the term Ex=1 Ex=1 c can be bounded by
o H K d.dimmm,FF, V1/K) (FF.)///)E)
with probability at least p. thus follows that regret can be bounded by
Reg( K) S O HV K dimme(F,
B.I LINEAR FUNCTION APPROXIMATION
In the linear function approximation setting of Xie al. (2020).
Th (I, a, b) = 6(x, a, b) On Pa(-|2, a, b) Ø(x a, b) (n.())
where .(:---) E 1Rd known feature vector and 0n E Hd and pn(-) E Rd are unknown with ||0||2 < dd, (-)le S vd and (6((,))]l I 1. In this case Algorithm Algorithm 3 Notice that this algorithm can also be seen a generalization Zanette et al. (2020) to Markov games.
| reduces to the following
Algorithm 3 ONEMG for linear function approximation.
1: Input: Function class JF
2: Set f CVddlog(H for some large constant C
(H 3: for episode = 1,
K do
4: Receive initial state z
5: Set w = 6 0 =
6: Find m o ME[H] VIN (xf) such that for all E [H]:
(1) / = (A Σ (x a7 bylr + VA (2%+
(2) |10h w S C HB
(3) () =00)) o(.,)-)
(4) (T Bo) =NE(
(5) V/²()) = anark Bo ( a.,
7:
for step h = 1, H do
8:
Pl plays action o (x
9:
P2 takes action by
10: Observe reward r and move next state xx
11: end for
end for
We will prove the following theoretical result of Algorithm Algorithm 3 is d while the dependency on d of Xie et al. 2020 is d3/2 thus this result improves theirs by vd factor.
Notice the dependency on d of
Theorem B.6. Regret (Eq in Algorithm is bounded by Old H log(dH with proba- bility at least
p.
B. PROOF OF THEOREM B.6
We prove Theorem B.6 in the following five steps similar to the previous section.
19

---

Published as a conference paper at ICLR 2022
Step 1: Low Bellman error in the constraint set We some standard results from previous work. Notice that the W <) = (odlogg1//r and our inherent Bellman error is zero, thus these lemmata can be directly adapted into our setting.
Lemma B.7 (Concentration, adapted from Lemma of Zanette al. 2020 least 1 - p. the following holds for all (k, E [K] x [
With probability at
Σ rE(K-1 11
0h 1h (0%+1)
V V++ (x:)
$ H3
(A
where 3 = ( V (lo(ddKH/p))
Lemma B.8 (Least square error bound, adapted from Lemma 3 of Xie et al. (202 On the event of
Lemma B.7 the following holds for all (z,a,b, S x A H
[ and any policy pair
(TT,
(,(z,,,b), (x,
E a~P(12,0
(V (x)
S a,
Step 2: Q" always stays in the constraint set
Lemma B.9 (Optimism). Let ())).))) o6 .)) Lemma B. there exists w7. h E [H] such that wh 0% h [H] satisfies the constraints of Line in Algorithm
) To then on the event of Lemma B.8 and
Proof. We prove by backward induction on h. The claim trivially holds for h = H + 1. Now assume the inductive hypothesis holds at h + 1. Let
wf = (A
6z o 111 + V (2%_1))
( T ry p x=P((p
V (2) n))
where 0% 6(2% 0% b)) and 1/ ( E Ea V (x). Notice that inductive
hypothesis implies rf + Eg (117 (7.5)) 1 = 60H 0%, b7) 0% therefore
wh ((())) +1)
tो ((p)) 0% + tmm)
7=1
0 (AA) + (A
It thus suffices to bound the following
A-1
R-1
([(At) - + (A
Σ
oanull = 110 +
Σ
ten nh lanyy
7=1
< Vd H3
C H3
where the penultimate step comes from |10 S vd and Lemma B.7
Remark B.10. This fact implies that
(i(1)) S (at))
(14)
20

---

Published as a conference paper at ICLR 2022
Step 3: Recursive decomposition of regret
Lemma B.11 (Regret decomposition), Define
8% = (ar)) - Vit". (x/)
Sh 1 |a 2 1/1 -
7h E
(art a, 1/31 Qh b/
am))()))
th =
10 =² (a a b]] - 2t
(o b/)
am*k (o (sxk,)
Then we have
8 S h- - 5h + m %h
(15)
where ex is the width defined by
ch = = ( (AA) -
Proof. By definition of Bo = argmin, /f (0 , v/, we have
(x+,)) = (x t Bo)
< Q (att m bb)
= (at at bb) + Th-
It thus follows that
x% S (2 ah bb) Qt n² (a a
b%) 7h 3 E
S -> B(1a.1 1b2)
E
1 [x:]] 2~ (4))
| -0 (x)] + ch 7h 7/
Vh+ (xx+1) vxt"."" (2ltta) - ch: + ei + 2 th
ohf41 - ch + 7h
nk Th
+ ch
where the second step comes from Lemma B.8 by letting (z, a, = (a at bb) (notice that (6(a)) a b)t), 0 = Q (2t a b))).
Step 4: Bounding width by Elliptical Potential Lemma This step directly makes of the following standard result.
Lemma B.12 (Elliptical Potential Lemma, Lemma 10 of Xie et al. 2020 Suppose t0ete2o is a sequence in IRd satisfying || < 1t,t. Let Ao E gazd be a positive definite matrix, and A Au Eierg 0:0, the smallest eigenvalue of Ao is lower bounded by 1, then
detAA, detAA
s log detA,
log(
Σ aE|t]
o. STA
detAn
Step 5: Putting everything together
By Eq
(44 and Eq 15
K
Viri""" wn (o
Σ (m)
VI (x1)
K
ch
+
t4
+
Am1
1/
1=
21

---

Published as a conference paper at ICLR 2022
Notice that Σi= Ek=1 Sh + - -%) is martingale difference sequence and can be bounded by H / KH log HK/p) with probability at least p.
By Lemma B.12 the term Eh=l Ex=1
k= <x can be bounded as follows
23
(0%)
k=
H
K
K
25(0%) T (AA))
hm
kml
H
detA 4 detA
- 2/3
K
2 log(
h=1
(A + K max 13)
< 23
VK-
22
A
O(dH v K log(dHK/p)).
with probability at least 1 p-p. p.
It thus follows that with probability at least p regret can be upper bounded by
Old H log(dHH/p))
C MODEL-BASED METHOD FOR THE COORDINATED SETTING
C.I ALTERNATE OPTIMISTIC MODEL ELIMINATION (AOME)
Algorithm 4 Alternate Optimistic Model Elimination (AOME)
I: Input: Model class M, test function class G, precision failure probability
2: Initialize M < M
3: for k = 1,2, K do
4: Find M +- argmax CEEEEMMMMM
QM(1, (I1, M,M ,,A,,, ), let x +- AM 5: Find M <- argmin Me QM (m1, nt, vn)), let wb &- Mr
6: Execute * n and collect ni rewards (ridnetH))HEEmmn)
7:
Let V L EE (E r/)
if maxx QMI (I1, Th )1 V Q ( )1 S e/2 then
8:
9:
Terminate and output ah
10:
else
11:
Find & such that max [CM MR, MK, ((, 2 e/(4H) by Eq (5)
12:
Collect trajectories { af. bb, "
1 by executing an, by ~ x M vh E [H]
13:
Update constraint set, where E is given by Eq 66
M + (M L.MEMAL 1 :((M M M
14:
end if end for
15:
C.2 THBORY FOR ALTERNATE OPTIMISTIC MODEL ELIMINATION (AOME)
In this section we prove that Algorithm terminates in finite rounds. The technique bulk is then showing that in Step 13 the constraint set can only shrink for finite times. This is dependent on the complexity of model class M and discriminator function class g. We first generalize Witness rank (Sun et al. 2019b) to Markov games.
22

---

Published as a conference paper at ICLR 2022
Definition C.1 (Witnessed model misfit in Markov games), For discriminator class G S x A1 x Ag x x + R. models M1, M2, M E M and level h E [H], the witnessd model misfit of Markov game level h is defined follow
E(M1, M, h) == =sup
(0( ar, r, - g( On bno The Ib++1)] (16) 9E9 M (r,))
E
where (I, a, ~ Mi
denotes +++1 ~ P(-|ar, ar, br), ar ~ Ms and by ~ qhn for all T E [M]
Using g( On bb. T,, 2.) r rZ aj. by.) + Qm (I, TM, 1 w we can also give generalization of Bellman error (Jiang et al. 2016) in Markov games by the following
C(M,, M2, M,h)= =
E
Lgtann on, ba r,))] (naz)~
(g(nnn an, bn, T; a:) (1z))~
(r,a,)))-P
M2
(17)
The final components in our theory are two assumptions from Sun et al. (0019b). Define rank(A, 3) to be the smallest integer it such that A = UV with U, V E > and [1U,-l2 [VV 1 B for any pair of rows Us,,, Vg.-- Assumption C.2 (Realizabilitt). Assume M E M.
Assumption C.3 (Witness misfit domination). Assume G is finite, l|o| S 2, Vg E g and VM1, M2, M E M: EMM, M, 2 L(M,, M2, M, h).
Now we introduce the Witness rank for Markov games. Definition C.4 (Witness rank for Markov games). Given a model class M, a test function class G and K. E (0, 1]. For h [H], we define No. C IR MMMMM as the set of matrices such that any matrix A E Nx,h satisfies
(M,, M2, M,)) S A((M1, M) S E(M1, M2, M,,), VM1, M2. M M.
The Witness rank for Markov games is defined by
W 3,,
min AEN
rank(A, A, 3).
We are in the position state the main theorem of this section.
Ke Theorem C.5. Under Assumption C.2 and Assumption C.3 set Φ /0 where W.
maxдε[и] W(s, 8, 9, h),, let T HW, log(3/2gg set n C H² (og(HT/p)/e² and
C. C-H logT probability least Algorithmm outputs a policy π such that V*(x1) V (x1) S c within at most O H" [Al M/)))) trajectories.
for large enough constant C. Then all e, (0, 1]. with
x2/2
As seen in the above theorem, Algorithm haas sample complexity that scales quadratic with Witness rank and logarithnically with cardinality of model class. This matches the sample complexity results in the Markov decision process setting (Sun et al. 2019b). When the test function Q-function, the Witnessed model misfit reduced to Bellman error as seen in Eq (17) and witness rank reduce to Bellman rank.
C.3 PROOFS
We prove Theorem C.5 in the following steps. In the first step, show simulation lemma that generalize Diang et al. (2017) to Markov games. In the second step we show concentration empirical estimates of Bellman error, model misfit and value functions. In the third step we show that M always stays in the constraint set. We examine the conditions when Algorithm terminaaes or not in the fourth step. Using these conditions, bound the number of rounds in the fifth step. Finally combine everything and complete the proof of Theorem C.5
From Definition C.4 we know that there exists A E NN., such that
ks| <s M2, M, < Ax((M,, M2), M) S (MM, M, h). VM1, M2, M E. (M, M2). (2) where
and we can factorize (b),
=
[| (M1, Ma)lla, (lx())]1 < B.
23

---

Published as a conference paper at ICLR 2022
Step 1: Simulation Lemma The analysis begins with useful Lemma that decouples the value difference into a sum of Bellman errors across time steps.
Lemma C.6 (Simulation Lemma). Fix model MI, M2, M E M. Let π = NM,, N u1 Under
Ma
Assumption C.3
we have
QM( - (x))
Σ hm1
C(M1, M2, h)
Proof. Let (x. 0, ~ PM, denote 2++1 ~ P(- a,, d,,b,), a ~ x Mr and by ~ A for all
T E [h]. Using definition Bellman error in Eq (17). we have
QMI(II, VT (z1)
[ri + (22,
E (M
In + QM- (22,
M2 (2.0,b))P
Mi
E (M1N2))M
[11 + (M2,
E (M1
Iri + (12,
(r,a, afj
Mr
E
E
[ri Q2r [T)]
E (m)2z)~~1*
Ini + (M2,
(x,a,b)/PP))
Ma
(M
L(M,, M2. M,
E
(12, TT (x²))
Σ C(M1, M2, M,...
A=1
We thus complete the proof.
Step Concentrations this part we show some standard concentration results.
Lemma C.7. With probability at least 1 we have the following event
1. E(MR M2, M,h)) E(M Mg. M,k)] db for all M M and [H].
2. Z(MP MM2, M h) - C(MP Mr. M ni) s 8H for all h E [H] and i E [2].
3. yatuu PM| S e/8
holds for all l < T rounds.
Proof. Fix one iteration. By Hoeffding's inequality, with probability at least 1 - -p/3,
log(2H/p)
|(MM My M h) L(M) Mr M .)) <
(18)
T2
Thus (2) follows from #ı = C H² log (og(HT/p)) and union bound on all T iterations. Similarly we can verify (3). For (1), fix model M M and G. by Hoeffding's inequality, with probability at least 1 - p//3.
[g( an Dn,r,x) g(an, an, bn The I1+1)] (2.0, Mr (r,e)~M
E
(19)
Σ
(raa) Lo ahe r,')) glath aih U/r rhe mh+1))]
(20)
log(2/p)
(21)
24

---

Published as a conference paper at ICLR 2022
Thus (1) follows from C. H [A] log [og(T)]M and union bound all & E [T] M E M and g E g. We complete the proof.
Step 3: M stays in the constraint set while it shrinks In this step, we show that the constraint set always contains the true environment. The result is displayed in the following.
Lemma C.8. Suppose for each round k the event in Lemma holds. Then M E M for all
k. Furthermore, let M = {M& E M Ap (M M2. M) S 26} with M = M. We have M M" for all k.
Proof. Since E(M+, Mn, M,, = 0, E [I]. we have E(M Mi, M", n1a) S
E(Mf, Mb. M ,h) + S o. Thus M is not eliminated. We prove the second result by induction. Firstly M -M. Assume M C MM-1, For all M E M we have Aaa (M&, Mg M) S E(MF. (MM,MM,, M, S E(MP, MB, M, + S 26 by Line 13 of Al- gorithm Therefore M E M we complete the proof.
Step 4: Terminate or rank increase The following Lemma is key to the 'alternate pessimism principle'. Intuitively, it indicates that the algorithm either terminates and outputs pair of policies with small duality gap, or detects a time step that provides useful information (large Bellman error).
Lemma C.9. Suppose for round k, the event in Lemma C.7 holds and M not eliminated. Then if the algorithm terminate, it outputs policy pair xh such that V* (x1) y with (x1) S e; otherwise A ((MP, M5), M 2 sec for some i E [2]. 88
Proof. Consider the situation that the algorithm does not terminate. Then with out loss of generality we can assume V Quit (I11 n r²) 2 e/2. By Lemma C.7 C.7 and Lemma C.6 we have
H
L(M M2, M h)) = 1Qas (21, TT, V7T:((11)
2 5 QMr (x1, " - | PK
23c/8.
By pigeonhole principle, these exists h E [H] such that [CMM) MA. Mt, h)1 2 3c For this h we 3e
8H
have (2(M}, MY, Mf. h)] 2
अH . thus the & in Line 11 is well defined and we have
8H
[2(M) MB. Mf. ) N e/ (/H)).
Using Lemma C.7 again, we have
An ((M), M,),MM 2 k- 1C(M MR. MR. h 2
KE
SH
If the algorithm terminates, we have
Q Mr (01, , 2 QMI MM (21, th D ) V2(11)
M²
and Q (I1, Th v² S Va 2it (x1). Therefore
(- va w (01) s Mi (01, * ( QM3 (2), n ,2k)
< Q Mt (II, (,,) 1--- Portee + 1o Mb (x1, x ,
Sc. c
We thus complete the proof.
Step 5: Bounding the number of iterations. This step uses the technique of Jiang et al. (2017); Sun et al. (011a)), which uses the volume of minimum volume enclosing ellipsoid as a potential function to bound the number of iterations. The key result is presented in Lemma
Lemma C.10. Suppose for every round k the event in Lemma C.7 holds, then the number of iterations of Algorithm 4 is most HW,, x log( //ooog(5) log(5/3) for certain i [2].
25

---

Published as a conference paper at ICLR 2022
Proof. If the algorithm does not terminate (M,,, M2), Xi* (MF)) = A ((M). M M?) 2 8H = 6,W Let Of denote the
round k, then by Lemma C.9 Re
origin-centered minimum volume enclosing ellipsoid of (xx(M) : M E M&]. Let O denote the origin-centered minimum volume enclosing ellipsoid of {o O (MMP M2). u) - 20). By Lemma F2 we have
vol OO A+)
vol(O li
S 3/5.
v b+
v0l b
Define = MU (MM,, M2)ll2 and v sup (lxx(M)ll2 Then we have vol(OR) < Vw, (1) wo where Vw. (ft) is the volume of Euclidean ball in I Wn with radius R. On the other hand, we have
vol(O%) 2 vol(fq E R llll s 26/ Vw (1) (26/$)
thus follows that the number of iterations for each most Wi log( 24 /////ooge 1og(5/3). Using vV, this completes the proof.
Step 6: Putting everything together. From Lemma C.7 with high probability the events holds. Therefore for the first T rounds, we can apply Lemma C.10 and know that the algorithm indeed terminates in at most I rounds. The number of trajectories thus upper bounded by (n1 n) 0 #* LAl log(T(g))M///)).
D THEORY FOR ALTERNATE OPTIMISTIC VALUE ELIMINATION (AOVE)
We prove Theorem 4.4 in the following five steps. In the first step we show that the functions in the constraint has low Bellman error. Notice that different from Lemma [.] here we consider different Bellman operator in Eq ( and consider all policies in policy class II. In the second step we show that QT."²" belongs to the constraint set for all क E II and in particular Q" belongs to the constraint set. In the third step we perform a regret decomposition. Notice that here we consider two Bellman errors. We then bound the summation of these Bellman errors by Minimax Eluder dimension in step and complete the proof in step 5.
Step 1: Low Bellman errors in the constraint set.
Lemma D.1 (Concentration on Bellman error). Let p O be an arbitrary fixed number. With probability at least - for all (k, E [K] x [H] we have
(fh (z), at., bb) rí.
E x p(-a af
fht1 (I, th (W (=2)))+)))) s 0(3)
(b)
(oh, at. (),) rh.
gi (a, ahen (vg (wz))+ < 0(3)
Proof. For simplicity we only proof (a), and (b) follows similarly.
Consider fixed (k, h, f, m) tuple, let
U., T) = (z ah, bb)) - r/, fn+1 vz)2)²
(rh 2-P(-1of, Jn+1(2, a,, vf) rh (1:
and Fth be the filtration induced by {0f af. bf rf..r.........
26

---

Published as a conference paper at ICLR 2022
We have
-1(n(zh An. b//) - r p))())))) Jn+1 (2, n, (T, (z), oi, 18,1
Elfn (ahh dr. b/:) + rh +
x- (I, vzx 2r - 22 T, 1f)1
E [f oh b/)) r -~P(1 ag (,,,
and
(ar TT) F) (,
=I(A- -Th amp()..))) Jo+1(z, n,, vz (a ah )
:E[(fn (2/ a/. b/,) + +rh +
E w Pt b1)
Ih+1 (I, n. vf) 2r,, 2f 1 uz)) 2 F
E < (2), oh by)) - 1. (
fh+1 n, wf)1= ft)
By Freedman's inequality, we have with probability at least - P.
U,l f,) 50( log(1/p)
&
Σ (og((1/))
Let LK, x S be p-cover of F 11. The covering of 11 is in-terms of the distance of two policies defined as
d(T, )) =
max JEF.EES
[f म. b) - f(z, b)].
Taking a union bound for all (ke, h.
f.p)
[K]
[ x No yp we have that with probability at
least 1 - for all (k, h. f) E [K] H x No
y
&
U.(h, p.p) Σ
Fa (1/. oh bl:) - r
E
int (2s, P, nf))²
s0(,
Iin (a b6) r/ a-B(-1a (1,00) f p, uf))2 +
(22)
where i (og(H)) (. For an arbitrary (h, kb) [H] x [K] pair, by the definition of y and (Tt*, fh) E 4 we have
Ui(
(rh
E a.
f fhtz (t ( - rh - (h Th vnf
(fll oh 6%) r
1=1
inf
Σ
(oh(zh, - r/ f aht a )(t))²
9EF
< ( + kp)
(23)
where in the first step we Assumption 3.2
27

---

Published as a conference paper at ICLR 2022
Define f argminge.r, [ I1fh - folloo p* argmin pE: d(r", ((Th)))) Since Ny is p-cover of F,
Uelh, ft x Urlh, fr ,²) - SO(kp).
(24)
Therefore combining Eq 23 and Eq
Σ U.(,, ph. pp)) S 0(1+ kp).
(25)
Recall Eq 22
indicates
Uhhh, p*)
Σ I1 oh rh
E x lo bf)
th- (x, 10th
pt 112
k
$ 50
I1% (2h, 0/2 b))) r s Thta (z.,
(x, pt, 1 +1)
(26)
Combining Eq
25 and Eq 26 we have
Σ
6% (ah, o/ b/)) rh x-P(1lu 101
(e+ p". uffi < O(1 + kp).
Since 1 is an p-approximation to f and p is an p-approximation to nh we can conclude the proof of (a) with
(fh at, b(,) - -rh p of)
fhti ( ( (w2e))))))) s 0(3).
Step 2: (T,, QT..) ), Vx E Il is always in constraint set.
Lemma D.2. With probability at least 1 we have (T*,Q') Q*) and (T, "T**),),= VT E Il all belong to y for all ls [K].
Proof. Consider fixed (ks h, TT) tuple, let
U.(h, f,x) = (Ju ahs by)) - rh. - Q Q (2h41, n., vz))
- -Q (1h oh 1/)) r Q (#1+1) v
and F.,. be the filtration induced by fzt af by. rf................. 2 M= u azj
a/.
We have
(hU f, F m, = 11fn ( ai b6,1
and
(h, S 36((S, t5 oi, 11)1 (,,
By Freedman's 's inequality, we have with probability at least p.
U. (h, f.t) Σ
Uhh
O7 (x at, b/)1
1=1
b
50(1
log(1/p) (5h
2 (x at, 66)12 + log(1/p)
28

---

Published as a conference paper at ICLR 2022
Let Ng M be p-cover of F x II. Taking union bound for al (k,, h, f. f.p)
E [K] x [H]
No y.
we have that with probability at least p for all (k, E [K] x [ x Np x 3
U.(h,f.)) - 0())
where log [K]] (.ggH)/)////p)) This implies for all (k, h, f.p) E [K] [H]] x No "
4
Oh 2 (ah (ohh oh. b/)) - r.. -
(faaarhs bi) r/
Oa++ kp).
Since N, x V be p-cover of F x II, for all pK e v//
(0 "h (rhh bh) - r - n. 2 (.
(9 o/. r/. Chi + O(l kp).
inf SEF
Again using. No x 3 be a p-cover of F II, we have for all
Σ
i or bb) ri. - (1h+1: x,,,,,
inf gEF
(gh( ah, bhh) - r - Q (2/+1, x12)) + O(l + kp).
Therefore we have (TT, )). Vn II all belong to D for all E [K] with probability at least
1 1- p.
Remark D.3. An important implication of this fact is the following
V -*- -- 1ith S ft (at R² w/th) of (af, n² 2 which gives an upper bound of the one-side duality gap.
Step 3: Bounding the regret by Bellman error and martingale.
Lemma D.4. Define
8% = (ath Thi (v(()a)) gf Th. v/:)
ch Elsk la ah bt] 5/
2h E
[1h (h a, b)] fh oi 8%.)
2/ E
(o) a, b)] (x ot b
Then we have
8/ < 8
ct + ch 2t + 2/ 7
where &i 2) are the bellman error defined by
# = (x 0/,, b)) - +/
E
ft The (wi)))))
amF( o oo
き of ot, (b)) rh
E (2, witn
29

---

Published as a conference paper at ICLR 2022
Proof. By definition of (e=*)) argmiin Sh (a/t m/; v), we have
(h Thi (oft)n)) - 1 (a nh v/) = fh ah 6%) 7h
It thus follows that
0% = fh The (1ft))) (hh
S (2 oh bh)) (h ah bh) mh 7%
(ri +
E
(2,
(1 )++1) + cxh)
(r +
gh ( + 2%) + 7h 5%
an at
E
(2, Th Thi1 (1 (1 )0+)) a
gh a Rht vh+2)
+ c 2 7/
7h
0 ch + ch
Ch
+ Th
Th-
Thus we complete the proof.
Step 4: Bounding cumulative Bellman error using Minimax Eluder dimension.
Lemma D.5 (Bounding Bellman error). For any hk, [K] [H] have
Σ c S <<(v
VV- dimMe (F, 1o/ -V(1, HK/p)
Σ 1 S 0
k- (OC
HK/pp]
Proof. Let
1(5%))) = f1(()))) -m())))))))))))))))))))))))))))) =-F(s)))) Sh+res, n², vff)
E
and Pt =(1h at, b,)). Similarly, also let pt be generated by (Tt UO), Then Lemma D.1 indicates
k
Σ ((()) 0(())
Based on this, we can apply Lemma obtain the first inequality. The second follows similarly.
Step 5: Putting them all together.
We can upper bound the regret as follows:
K
Σ
V
<
of (at * (
km
km 1
(ch
ct 2
-
k= 1 h=l
K
H
K
7h
2t)
(27)
where the first step comes from Lemma D.2 the second step comes from Lemma D.4 and the last step comes from Fubini's theorem. Notice that the first term in Eq (27) is a martingale difference sequence and can be bounded by O(H, KH log (KggH/p)) with probability at least p and the We thus complete the proof.
second term can be bounded by Lemma D.5
30

---

Published as a conference paper at ICLR 2022
E EXAMPLES
In this section we give several examples of Markov games that possess low Minimax Eluder dimension, including tabular Markov Games, linear function approximation, reproducing kernel Hilbert space (RKHS) function approximation, overparameterized neural networks, and generalized linear models. We first consider reproducing kemel Hilbert space (RKHS) function approximation, which captures many existing models.
Reproducing kernel Hilbert space (RKHS) function approximation. In this setting, the function class of interest is given by
Fn = [ón a, b), 0n) ((. E Bn())))
Here ((:...)) A A H. feature map zero with radius R in a Hilbert space H. The effective dimension of a set D C H. is characterized by the critical information gain d(7,, D). Specifically, for 0 and D C H. we define (7,7, D)
0 H. and (R the ball centered at
max. ....... ED log det(I+ Ei= T, ). The critical information gain (Du et al. 2021 is thus
defined by d(yy, D) = minkeNa22. (Y.D) k. The main result is given in the following theorem.
Theorem E.1. In kernel function approximation, the Minimax Eluder dimensions dimme( eF and dimmE (F,e) are upper bounded by maxne(H) 7( gR Fr), where 4n, (1,(2, b, S, b A).
Proof. We only show dimmE (F,c) S [ 99. 1x), and the other part is totally sim- ilar. Fix an h E [H]. Due to completeness. for any π E II and f F we have (fa T, fI+1)(1, b) (Øn(x, a, b), On T 0n+1) where T, 0h+ the unique feature in H such that Th fh+1 (I, a, +1)) Consider the longest sequence 1/,,..,, 14 E DD such that each one item e-independent of its precedents, distinguished by sequence of features gf2)) ...., (())
To simplify notations, we define o, E.,, (o, (z, a, b)] and Ag o%e TN for all i [k]. Let A = Σ p. DR Then Definition 3.3 gives
1 2 Il - 10:l|A 2 - 16, 0.)1 2 1.
where the first step comes from 04 E (R(H) and Σ (0,, 0, s e, the second step comes from Hölder's inequality and the final step comes from (0i, 0:)1 2 Thus we have
9R2 log(1 1 + (10=ll = log (T
k
2
1=1
1=1
By the definition of critical information gain, k must be less or equal than (5.. Dn).
This result implies several important cases in general function approximation.
Linear function approximation. (.(-,r, a. b) Φ(x, a. (.))) where ő(x, a, b) E Rd. We have shown that this set- ting satisfies all the realizability and completeness assumptions in the previous sections. By standard Ellipsoid potential arguments, the critical information gain is upper bounded by (d log(R/))). Therefore, this setting also has low Minimax Eluder dimensions.
In this setting rh (x, b) 6(x, a, b) To, and
Tabular Markov Games. This setting can be seen as a special case of linear function approximation where the feature vectors are chosen to be one-hot representations of state- actions pairs. In this case, = [S) |A[2 and thus Minimax Eluder dimensions is upper bounded by -
Overparameterizedd neural networks. In overparameterized neural network function approximations, the functions are given by h((((, a, 6)) where h is the Neural Tangent Random Feature space defined in Cao & Gu (2019). We rewrite the information gain
Nonxx,,......65 dy, D) as max,, .....,,.27 ED log det(I 7 K,n)) where (K,)i, K (z,, 2.)) and K is the
Neural Tangent Kernel. It has been shown (Jacot et 2018 Du al. 2019c
Allen-Zhu
31

---

Published as a conference paper at ICLR 2022
et al. 2019) that with proper initialization and learning rates, the function approximations approximately lie in the Reproducing kernel Hilbert space given by the neural tangent feature as above. Therefore the Minimax Eluder dimensions bounded by 55 4n) + X, where is the critical information gain defined by the d, (7; D) rewritten above and is term that vanishes width tends infinity.
Generalized linear models. Finally, we consider generalized linear model as an extension of the linear function approximations.
Theorem E.2. Suppose (fn (hh-Th fn+1)(a) b) g(ó(x, a, b) 0p.) for any a E and f F, where g a differentiable and strictly increasing function and Φ, 0n Rd. Assume g' (c1, and 11 |10 S foror C12 c22 R 0. Then dimmE (F,e) e) I ((d(c2/c1) log( (22R)
Proof. The proof mirrors those in Theorem F.1 For the longest sequence M,,..., u Da such that each one item is e-independent of its precedents, distinguished by sequence of features
( .....,h. .(()). we define Φ; E (on(r, a. b)] and 0 2 I. Then Definition 3.3 gives
T 0%²² Th ht1 for all i [k]. Let
A E 2.07 नरे
||6alll," |0. 2 91
1(0 0.)
02
This means det(AA) 2 (1 --| But by Elliptic potential lemma, det (At) S ( it'
)
2
d g
Combining these inequalities gives & < O(d(e2/c1) log( (aR)
ose
F TECHNICAL CLAIMS
This section lists the facts
from the previous work.
Lemma F.1 (Cumulative error control, Lemma 26 of al. (2021a)). Given function class G
defined on X with [g(x)] I C for all (g. x) G x and a family of probability measures 'D over X. Suppose sequence [gx } K k=1 C G and {Pk k=1 C DD such that for all k E [K], Σ (Bp. [9h])² $ B.
H
Then for all le E [K] and
Σ E[g.]| s o (di G,D,D,,),, D,c)Bk + min dimpe(G, (Ge) + kw)
Lemma F.2 (Lemma 11 of Jiang et al. 2017)). Consider closed and bounded set V B
and vector p E Rd. Let be any origin-centere enclosing ellipsoid of V. Suppose there and define B4, as the minimum volume enclosing ellipsoid of With vol(.) denoting the (Lebesgue) volume, we have:
exists E V such that p p.v. v " {u E B 1p" cl & 3/0
vol(B+) 3
S
vol(B) 5"
32


Reviews:
[{"review_id": "pzIXZNv39Ci", "reviewer": "Reviewer_s7Lf", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths:\nThe paper is well organized and properly presented. Both intuitive design and technical proofs are easy to follow.\n\nWeaknesses:\n1. My major concern is about the difference between the model-free algorithms and the work by Jin et al. 2021b. It seems that they share almost the same idea of the algorithm design, similar analysis and results for sampling complexity, especially extending the same measure of Eluder dimension (named minimax Eluder dimension in this paper while multi-agent Eluder dimension in Jin et al. 2021b) without any comparison. Can the auther highlight any technical contribution beyond Jin et al. 2021b?\n2. The assumptions of realizability and completeness are not well-motivated. It would be better to provide more convicing evidence that these assumptions are realisitc.\n3. One minor question is that whether the sample complexity of the model-based algorithm can be compared with the model-free one? ", "summary_of_the_paper": "This paper studies efficient function approxiamtion in two-player zero-sum Markov games with general function classes. Both decoupled and coordinated settings for learning agents are considered. Model-free algorithms for both settings and model-based algorithm for the leter are provided, all with proved sample complexities.", "summary_of_the_review": "I think this paper is blow the bar of acceptance.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "h1gPbCkWS6h", "reviewer": "Reviewer_VsQZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths: \n\nThe presentation is mostly clear and to the point. The main results are related to the relevant literature. A particular strong feature of this paper is a detailed appendix containing the main proofs of the paper. The appendix is mostly well written and one obtains a good overview \n\nWeaknesses: \nI See a couple of issues with the references. Some entries seem to be duplicated, or not cited properly. This seems to be the case here: \nJulien 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, 2015a. \nJulien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. International Conference on Machine Learning, 37:1321–1329, 2015b. \nIan Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. arXiv preprint arXiv:1406.1853, 2014.  (This is a NIPS2014) paper \nAnd at many more places. Note that reference Yulai Zhao, Yuandong Tian, Jason D. Lee, and Simon S. Du. Provably efficient policy gradient methods for two-player zero-sum markov games, 2021. \nIs not even properly referenced. \n\n-) I do not understand the „Bellman operator“ defined in eq. (1). Usually, the value is computed outside of the expectation, and not inside. I would also not know what value iteration applied to this operator would deliver. Note that the Bellman operator your introduce is not the one defined in the paper you are citing at this stage: Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. International Conference on Machine Learning, 37:1321–1329, 2015b. In that reference you clearly see that the operator approach of stochastic games is follows, which is the mathematically correct way to define equilibrium in Markov games. \n\n-) Why is v_{\\pi}^* or \\pi^*_{\\nu} unique? \n\n-)The definition of the measures \\pi_{f})_{h} is confusing. First, I belief there is a typo on the sentence preceding sentence: It should now be f\\in F_{h}, but rather f\\in F, doesn’t it? Only then I would understand that you want to construct a sequence of measure-valued policies indexed by the approximating function sequence f and the time horizon.\n\n-) The proposed minimax Eluder dimension looks like a special case of the Bellman Eluder dimension on, previously introduced in the context of MDPs. What is the rational of looking at Dirac measures in this definition? Also, if the state space is not compact, I am wondering if this notion is a suitable concept. What is the minimax Eluder dimension on the real line? \n\n-) Algorithm 1 is a cutting-plane method in the sequence space of reward functions. If I understood it correctly, the round k profile of rewards is chosen as the best reward function at time 1 of the Markov game, when all per-period policies are myopically min-maxed. I am wondering how this is computed. To me the argmax defining $f^{k}$ reads like an optimization problem over a space of functions, and I do not see how this can be done efficiently in the present setting. Note that you do not assume the state space to the finite (unless I missed something). This looks to me like an extremely challenging task and some more explanation would be needed to understand the hardness of this step.\n\n-) After eq. (8) the set \\mathcal{Z}_{\\rho} has not been defined before I think.\n", "summary_of_the_paper": "This paper considers zero-sum Markov games in a general regime where the model is parameterized by general function classes. The goal of this research is to investigate reinforcement learning algorithms that learn a Nash policy in a trial-and-error fashion. The level of generality is achieved by introducing two complexity measures: The minimax Eluder dimension and the witness rank. The main result three algorithms with provable regret upper bounds involving covering numbers and the minimax Eluder dimension. ", "summary_of_the_review": "The paper comes with a very detailed appendix containing all the necessary proofs. This is a big plus of the paper. I am not quite sure, though, how novel the presented results are. At the same time I am admitting that I am not an expert on MDPs or RL. From an algorithmic perspective I have some doubts about the computational complexity of the algorithms presented here, but it seems this is a general problem in this literature, so again I would not put much weight on my critique here. \n\nWhat I find quite confusing is the use of classical concepts, like the Shapley operator (the analogue of the Bellman operator in stochastic games), is defined in a way that I have not seen before. In the operator approach to stochastic games, it is used to define an extension of dynamic programming to competitive settings. A key property is that the Shapley operator is a contraction, and this drives a value iteration kind of algorithm. I am not sure how these classical results translate in the present formulation, as the operator is different and it is not clear whether contraction properties can be used. The question is then to me how one can relate regret and equilibrium. Note that we know that regret minimization and Nash equilibrium are not the same, and even in zero sum games usually regret minimization implies something about the ergodic average, but not the last iterate. This confuses me quite a bit in this paper (and the cited references, to be fair).\n\n", "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": "CASs1MhnQnT", "reviewer": "Reviewer_mNjL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The former works under a (new) notion of Eluder dimension that is appropriate for games, and the algorithm itself is a variant of Jin et al 2021.\n\nThe second works under a notion similar to the witnessed rank of Sun et al 2019a, and the algorithm is also inspired by theirs.\n\nI have few remarks.\n- The work alludes to general function approximation; I advise caution with the wording, as we do not have yet a full characterization of general function approximation in RL. Besides, the notion of Eluder dimension does not seem to give rise to models much more general than generalized linear models to the best of my understanding.\n- The work seems to be a `collage’ of different ideas, namely the Bellman Eluder dimension and witnessed rank. The authors should explain in much better depth why they use one instead of the others in the two different settings.\n- Most of the ideas in this work have been introduced previously (in non games)\n- The lack of computational tractability should be emphasized much better.\n", "summary_of_the_paper": "The paper discussed Markov games with `general’ function approximation. They consider two settings: the decoupled one where the player does not observe the opponent’s policy and the coordinated one where `optimistic planning is performed for both. \n\n", "summary_of_the_review": "While I listed several critical comments to this work, on the whole I liked the work because it still makes a non-trivial contribution to the theory of Markov games.\n", "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": "77KjCKdbcyf", "reviewer": "Reviewer_cKpw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors develop algorithms for optimistic nash eliminated \nfor zero-sum two-player markov games\nbased on value-function elimination (Zhang 2017).\nThe contributions are clear in the introduction and the technical challenges section provide good explanation of which concentration bounds and ideas of optimism are employed in the paper.\n\nIt would be useful to have some clear definition of what decoupled and coordinated means in this case.\nHow do those results relate to similar settings in single agent learning?\n\nThe discussion feels lacking. I would expect some more commentary comparing the various algorithms. Currently they are treated mostly as separate algorithms. Is there a unifying framework of the three algorithms that you could expand on? Or comment on how the regret bounds compare with each other? When to use one over the other. I think addressing this could make the story more cohesive.\n\nThe contributions seem significant for the zero-sum markov games settings.\nThe motivation for constructing the algorithms in section\n3.2, 4.1.1 and 4.2.1 is a bit lacking. What are you trying to do and why are you doing this way? Perhaps some transition sentences could help with clarity.\nA minor but related comment: adding line number references in those sections can help make it more clear.\n\nIt would be nice to see commentary on the significance of the informal theorems since the proof is omitted. Perhaps comment on whether it is a surprising or expected result.\n\n", "summary_of_the_paper": "This paper presents sample efficient algorithms for learning in two-player zero-sum markov games.\nThe algorithms are for decoupled and coordinated settings, the latter of which is based on 'alternate optimism'.\nThe authors also extend the Eluder dimension of MDPs to to zero-sum markov games using the minimax Bellman operator.\n", "summary_of_the_review": "The authors present a wide range of results on efficient algorithms for zero-sum markov games.\nThese results leverage several previous works on value-function elimination using the Bellman factorization and Bellman Eluder Dimension.\nThe contributions seem to be significant. The correctness seems good but it is possible i did not understand some parts of the submission and unfamiliar with some piece of relate work. The technical novelty seem high, providing new theoretical insights into minimax markov games.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary: The paper discusses Markov games with general function approximation, and investigates in particular reinforcement learning algorithms that learn a Nash policy in a trial-and-error fashion. They consider two settings: the decoupled one where the player does not observe the opponent’s policy and the coordinated one where optimistic planning is performed for both. The main contribution is a new complexity measure called Minimax Eluder dimension which is used to control the regret of the proposed algorithms. 

Discussions: The reviewers raised many minor concerns regarding the writing (typos of missing notation) and the clarity (missing discussions and explanations), which were addressed during the discussion phase. In light of this revision, the committee and myself judge that the paper should be accepted to ICLR.

Decision: Accept
Decision: Accept (Poster)