Representation Learning for Low-rank General-sum Markov Games
Authors: Chengzhuo Ni
Yuda Song
Xuezhou Zhang
Zihan Ding
Chi Jin
Mengdi Wang
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement Learning
Multi Agent
Representation Learning

Abstract: We study multi-agent general-sum Markov games with nonlinear function approximation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation. The goal is to design an algorithm that (1) finds an $\varepsilon$-equilibrium policy sample efficiently without prior knowledge of the environment or the representation, and (2) permits a deep-learning friendly implementation. We leverage representation learning and present a model-based and a model-free approach to construct an effective representation from collected data. For both approaches, the algorithm achieves a sample complexity of poly$(H,d,A,1/\varepsilon)$, where $H$ is the game horizon, $d$ is the dimension of the feature vector, $A$ is the size of the joint action space and $\varepsilon$ is the optimality gap. When the number of players is large, the above sample complexity can scale exponentially with the number of players in the worst case. To address this challenge, we consider Markov Games with a factorized transition structure and present an algorithm that escapes such exponential scaling. To our best knowledge, this is the first sample-efficient algorithm for multi-agent general-sum Markov games that incorporates (non-linear) function approximation. We accompany our theoretical result with a neural network-based implementation of our algorithm and evaluate it against the widely used deep RL baseline, DQN with fictitious play.

Published as a conference paper at ICLR 2023
REPRESENTATION LEARNING FOR GENERAL-SUM LOW-RANK MARKOV GAMES
Chengzhuo Ni Princeton University en1 men1@@riinceton.. edu
Yuda Song
Xuezhou Zhang
Carnegie Mellon University yudas and cmu, edu
Princeton University
xz x 92@r ieeerrnnnttnnne. edd
Zihan Ding Princeton University zi rihand@princetoom edu
Chi Jin
Mengdi Wang Princeton University
Princeton University chijeprincetton edu
mengdii@@prinneton.cc edu
ABSTRACT
We study multi-agent general-sum Markov games with nonlinear function approx- imation. We focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure on top of an unknown non-linear representation. The goal to design an algorithm that (1) finds an E-equilibrium policy sample effi- ciently without prior knowledge of the environment or the representation, and (2) permits a deep-learning friendly implementation. We leverage representation learn- ing and present a model-based and model-free approach construct effective representation from collected data. For both approaches, the algorithm achieves sample complexity of poly H, d, A, 1/s). where H is the game horizon, d is the dimension of the feature vector, A is the size of the joint action space and is the optimality gap. When the number of players is large, the above sample complexity can scale exponentially with the number of players in the worst case. To address this challenge, we consider Markov Games with factorized transition structure and present an algorithm that escapes such exponential scaling. To our best knowlede ledge, this is the first sample-efficient algorithm for multi-agent general-sum Markov function approximation. We accompany our
games that incorporates theoretical result with neural network-based implementation of our algorithm and evaluate it against the widely used deep RI. baseline, DQN with fictitious play.
INTRODUCTION
multi-agent reinforcement learning (MARL) studies the problem where multiple agents learn to make sequential decisions in unknown environment to maximize their (own) cumulative rewards. Recently, MARL has achieved remarkable empirical success, such as traditional games like GO (Silver et al., 2016, 2017) and Poker (Moravčík et al., 2017), real-time video games such as Starcraft and Dota 2(Vinyals al., 2019; Berner et al., 2019), decentralized controls or multi-agent robotics systems (Brambilla et al., 2013) and autonomous driving
Shwartz et al., 2016).
On the theoretical front, however, provably sample-efficient algorithms for Markov games have been largely restricted to either two-player zero-sum games (Bai et al., 2020; Xie et al., 2020; Chen et al., 2021: Jin et al., 2021c) or general-sum games with small and finite state and action spaces (Bai and Jin, 2020; Liu et al., 2021; Jin et al., 2021b). These algorithms typically do not permit scalable implementation applicable to real-world games, due to either (1) they only work for tabular or linear Markov games which rich non-linear function approximation (Jin et al., 2021c) are not computationally efficient. This motivates us ask the following question:
restrictive model real-world games, (2) the ones that do handle
Can we design an efficient algorithm that (1) provably learns multi-player general-sum Markov games with rich nonlinear function upproximation and (2) permits scalable implementations?
This paper presents the first positive answer to the above question. In particular, we make the following contributions:

---

Published as a conference paper at ICLR 2023
1. We design new centralized self-play meta algorithm for multi- aggntt low-rank Markov games: General Representation Learning for Multi-player General -um Markov Game (GERL (GRL_MG)). We present model-based and model-free instantiation of BERL_MGS which differ by the way function approximation is used, and a clean and unified analysis for both approaches.
2. We show that the model-based variant requires access to an MLE oracle and a NE/CE/CCE oracle for matrix games, and enjoys a Ô (H&d' A2 log( | ()/)") sample complexity to learn an 6-NE/CE/CCE, equilibrium policy, where d the dimension of the feature vector, A is the size of the joint action space, H is the game horizon, & and v/ are the function classes for the representation and emission process. The model-free variant replaces model-learning with solving a minimax optimization problem, and enjoys a sample complexity of Ó (Hod² A M (g((())/e"*) for slightly restricted class of Markov game with latent block structure.
Both of the above algorithms have sample complexities scaling with the joint action space size, which is exponential in the number of players. This unfavorable scaling is referred to as the curse of mullti-a agent, and is unavoidable in the worst case under general function approximation. We consider spatial factorization structure where the transition of each player's local state is directly affected only by at most = O(1) players in its adjacency. Given this additional structure, we pro- vide an algorithm that achieves Ô(M* ( /2(L+1) /E²) sample complexity. where Á is the size of a single player's action space, thus escaping the exponential scaling to the number of agents. Finally, we provide an efficient implementation of our reward-free algorithm, and show that it achieves superior performance against traditional deep RL baselines without principled representation learning.
1.1 RELATED WORKS
Markov games Markov games (Littman, 1994; Shapley, 1953) is an extensively used framework introduced for game playing with sequential decision making. Previous works (Littman, 1994; Hu and Wellman, 2003; Hansen et al., 2013) studied how to find the Nash equilibrium of Markov game when the transition matrix and reward function are known. When the dynamic of the Markov game is unknown, recent works provide a line of finite-sample guarantees for learning Nash equilibrium in two-player zero-sum Markov games (Bai and Jin, 2020; Xie et al., 2020; Bai et al., 2020; Zhang et al., 2020; Liu et al., 2021; Jin et al.. 202 Huang et al.. 2021) and learning various equilibriums (including NE, DE,CE, CCE, which are standard solution notions in games (Roughgarden, 2010)) in general-sum Markov games (Liu et al., 2021; Bai et al., 2021; Jin et al., 2021b). Some of the analyses these works are based on the techniques for learning single-agent Markov Decision Processes (MDPs) (Azar et al., 2017; Jin et al., 2018, 2020).
RL with Function Approximation Function approximation in reinforcement learning has been extensively studied in recent years. For the single-agent Markov decision process, function approxi- mation is adopted to achieve better sample complexity that depends on the complexity of function approximators rather than the size of the state-action space. For example, (Yang and Wang, 2019; Jín et al., 2020; Zanette et al., 2020) considered the linear MDP model, where the transition probability function and reward function are linear in some feature mapping over state-action pairs. Another line of works (see, e.g., Jiang et al., 2017; Jin et al., 2021 a; Du et al., 2021; Foster et al., 2021) studied the MDPs with general nonlinear function approximations.
When it comes to Markov game, (Chen et al., 2021; Xie et al., 2020; Jia et al., 2019) studied the Markov games with linear function approximations. Recently, (Huang et al., 2021) and (Jin et al., 2021c) proposed the first algorithms for two-player zero-sum Markov games with general function approximation, and provided a sample complexity governed by the minimax Eluder dimension. However, technical difficulties prevent extending these results to multi multi-player player general-sum Markov games with nonlinear function approximation. The results for linear function approximation assume a known state-action feature, and are unable to solve the Markov games with more general non-linear approximation where both the feature and function parameters are unknown, For the general function class works, their approaches rely heavily on the two-player nature, and it's not clear how to apply their methods to the general multi-player setting.
Representation Learning in RL Our work is closely related to representation learning in single- agent RL, where the study mainly focuses the low-rank MDPs, A low-rank MDP is strictly more
2

---

Published as a conference paper at ICLR 2023
general than linear MDP which assumes the representation is known a priori. Several related works studied low-rank MDPs with provable sample complexities. (Agarwal et al., 2020b; Ren et al., 2021) and (Uchara et al., 2021) consider the model-based setting, where the algorithm learns the representation with the model class of the transition probability given. (Modi et al., 2021) provided a representation learning algorithm under the model-free setting and proved its sample efficiency when the MDP satisfies the minimal reachability assumption. (Zhang et al., 2022) proposed a model-free method for the more restricted MDP class called Block MDP, but does not rely on the reachability assumption, which is also studied in papers including (Du et al., 2019) and (Misra et al., 2020). A concurrent work (Qiu et al., 2022) studies representation learning in RL with contrastive learning and extends their algorithm to the Markov game setting. However, their method requires strong data assumption and does not provide any practical implementation in the Markov game setting.
PROBLEM SETTINGS
A general-sum Markov game with M players is defined by tuple (S, [Ai Pt, (ri) H, di).
Here S is the state space, A, the action space for player i, H is the time horizon of each episode and d1 is the initial state distribution. We let A = A1 X x Aas and use a to denote the joint actions by all M players. Denote Å max; |A: and A |A|. P {P% hh is a collection of transition probabilities, so that (-Is, a) gives the distribution of the next state actions a are taken at state s and step h. And r, = {mr.a h is a collection of reward functions, so that Th,s (s. a) gives the reward received by player i when actions a are taken state s and step h.
(01, (0, (2,...... aM)
2.1 SOLUTION CONCEPTS
The policy of player is denoted as π. := {mp,:: SS - AA, he([ We denote the product policy of all the players := Ti X .... X TM, here "product" means that conditioned the same state, the action of each player is sampled independently according to their own policy. We denote the policy of all the players except the ith player as πー=- We define V (s) as the expected cumulative reward that
will be received by the ith player if starting at state at step h and all players follow policy For
any strategy T-i, there exists a best response of the ith player, which is a policy jut ( satisfying
(x-))))) (s) = max V V.T..T-(s) (s) for any (s, h) E S x [M]]. We denote VA vi.T- : Vi, (T-1).T-1
Let 0. f- == Egndy Vi (s) o7 Eand, [VT]())].
" Vi E [M]. And Definition 2.1 (NE). product policy π is a Nash equilibrium (NE) if = =.! - 1.
we call π an e-approximate NE if max (v.
" <.
The coarse correlated equilibrium (CCE) is relaxed version of Nash equilibrium in which consider general correlated policies instead of product policies.
Definition 2.2 (CCE). A correlated policy x is a CCE if vi.= ((s) S (s) for all s E S,h e [H].i E [M]. And we call π an E-approximate CCE if max f. 27 <E
The correlated equilibrium (CE) is another relaxation of the Nash equilibrium. To define CE, we first introduce the concept of strategy modification: A strategy modification W; := (we,shee(r for player i is set of H functions from S x A, to A,, Let Ω4 (Sn,))e(H) denote the set of all possible strategy modifications for player i. One can compose a strategy modification w; with any Markoy policy π and obtain a new policy wi o π such that when policy л chooses to play a == (ai...., aM)
at state s and step h, policy Wi o π will play (a1...., 0;-1; (s, az), ai+l...., ....))))))))))..) instead.
Viuoo (s) S (s), for Definition 2.3 (CE). A correlated policy is CE if maxie (M]] max Vii
all (s, h) E S x [H. And we call π an E-approximate CE if max fmax of of} < E. Remark 2.1. For general-sum Markov Games, we have (NE} C {CE] C (CCE), so that they form a nested set of notions of equilibria (Roughgarden, 2010). While there exist algorithms to approximately compute the Nash equilibrium (Berg and Sandholm, 2017), the computation of NE for general-sute sum games in the worst case is still PPAD-hard (Daskalakis, 2013). On the other hand, CCE and CE can be solved in polynomial time using linear programming (Examples include Papadimitriou and Roughgarden (2008); Blum et al. (2008)). Therefore, in this paper we study both NE and these weaker equilibrium concepts that permit more computationally efficient solutions.
3

---

Published as a conference paper at ICLR 2023
2.2 LOW-RANK MARKOV GAMES
In this paper, we consider the class of low-rank Markov games. A Markov game is called low-rank Markov game if the transition probability any time step has a latent low-rank structure. Definition 2.4 (Low-Rand Markov Game). We call a Markov game a low-rank Markov game if for any 8 E S,a E A, E [M] E [M], we have (s (s.ssss,)) (7,3,0) (.(('))) where [10% as) | s 1 and [1oo S for all (8,0, 8').
special case of low-rank Markov Game is the Block Markov game:
Definition 2.5 (Block Markov Game), Consider any E [H]. A Block Markov game has an emission As and latent state space transition (2'12, a), such that for any s
distribution on(- (11-)2)
S, (8)2) > 0 for unique latent state 2 E 2, denoted as (8). Denote Z = 2 Together with the ground truth decoder v/ it defines the transitions P7 (s) Er'ez on (s' 1 (5), a).
With the definition of the Block Markov game, one can naturally derive feature vector that in addition takes the one-hot form: we just need to let the ground truth o (s. a) at step h be Z A-ddimensional vector C(w- (s).a) where 6; is the i-th basis vector. Correspondingly, for any s E S, w (s) is Z A a). Then (s ss,a) 6j (s, a) wi (s'). so that the Block Markov game a low-rank Markov game with rank Z A.
dimensional vector such that the (z, a-h entry is Exez o (
Learning Objective The goal of multi-agen reinforcement learning is to design algorithms for Markov games that find an E-approximate equilibrium (NE, CCE, CE) from small number of interactions with the environment. We focus on the low-rank Markov games whose feature vector ø and transition probability P* are both unknown, and the goal identify e-approximate equilibrium policy with a number of interactions scaling polynomially with d, A, H, 1 and the log- -orrddiaina of the function class, without depending on the number of raw states which could be infinite.
ALGORITHM DESCRIPTION
In this section, we present our algorithm PERI_MMG' (see Alg. 1). The algorithm mainly consists of two modules: the representation learning module and the planning module. We develop the representation learning module base the past works on the single agent MDP (e.g. Agarwal et al. (2020b); Uehara et al. (2021); Modi et al. (2021)), and but modify them to work with UCB-style planning module. Here denote d'p,, the state distribution under transition probability P and policy at step h, and U (AA as the uniform distribution over the joint action space.
3.1 REPRESENTATION LEARNING
In the representation learning module, the main goal is to learn a representation function I to approximate e¹ using the data collected so far. In each episode, the algorithm first collects some new data using the policy derived from the previous episode. Note that in our data collection scheme, for each time step h, we maintain two buffers ((n)) and ()()) of transition tuples (s, a, s') (line 7 of Alg. 1) which draw the state s from slightly different distributions. Based on the data collected in history. the representation learning module estimates the feature (()) and transition probability p(m), We propose two versions of the representation learning algorithm (model-based, Alg. 2: model-free. Alg. 3) based on whether we are given the full model class M₁ of the transition probability, or only the function class of the state-action features +
Model-based Representation Learning In the model-based setting, we assume the access to realizable model class M₁, {(w), Φ1) : Wa Vn dy E Φn). h [H] such that the true model is included in this class, i.c., WT E Un of E (h, Vh E [H]. Following the norm bounds on oh, W we assume that the same norm bounds hold for our function approximator, i.c., for any Φn E Pn, wh E Vn. we have [s, a)ll2 < 1 and [[w,, (s') I Vd for all (s, a, s'), and I (n(s,, a) TT, (s')ds' l = 1. Given the dataset D = DJ") UD((") MBBREPLEARN learns the features and transition probability using maximum likelihood estimation (MLE):
(n) h 3(m)) arg max Ep [log (o(s, a) ( (M
a) 31.) (s.
(n) 1h T (s'). (s))..
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 General Representation Learning for Multi-player General-sum Low-Rank Markov Game with UCB-driven Exploration (GERL_MG22
1: Input: Regularizer X, iteration N, parameter (x((x) 1.V
Jn= J
2: Initialize π. (0)) to be uniform; set ( = 0, D 0. wh {
3: for episode n 1, 2, .N do
4: Set v/m) #+1,i 0, k(n)
5: for step h H, H l..., do
6: Collect two triples (s, 8'), (3', 8") with
fa dpp. a U(A), s' (s,
la 8 d- à U(A,, 5'~ (5, à' U(A), ~
7: Update datasets: D DI--1) ((s, a, s.) DIth! = - a'"","
8:
Learn representation via model-based or model-free methods:
% (m)
p(m) MBREPLEARN (D UD! ,h) or MFREPLEARN (D).) UD (4,))
Compute 3(m) Ph from equation 5, for each (s, E ESX A,i [M], set
9:
(s, a) t (s) + (p(u h+1,8 (s, 3(m) (s.a)
2l1l (s, a) rh, a) (p(x) Lb+1, p(1)) (8, a) //4 (s, a).
10:
Compute Ti
(m) from equation 2 equation 3 or equation 4. For each S, i [M].
set
(s) t D (m 2 (s), (s) + m 1D (s). s
Th
11: end for
12:
Let A (n) max
(o! _11)
+2H 2H Aç(m), where ग. Js (n) (s)d1 (s)ds, and
(m) Is 1 (s)d1 (s)ds
13: end for
Return
(nn) where n² arg minne A (x))
Model-free Representation Learning In the model-free setting, we are only given the function class of the feature vectors, 4n. which assume also includes the true feature Φ1 Given the dataset
D := D(") U Dim). MFREPLEARN aims to learn a feature vector that is able to linearly fit the Bellman backup of any function f (s) in an appropriately chosen discriminator function class Fr. To
be precise, we aim to optimize the following objective:
min max min ED [(o(s, a) -
min B((T)) o,
@E JEPA
where the first term the empirical squared loss and the second term is the conditional expectation of fss') given (s, a), subtracted for the purpose of bias reduction. Once we obtain an estimation Ø we can construct non-parametric transition model defined as:
p(m) (s'ss. (1" (s)
30th az. (s,a) (3.G)ED
Σ
Ala
Σ
(5 (3.ā) (I)
(8.6.F")
We show that doing Least-square Value Iteration (LSVI) is equivalent doing model-based planning inside p(m) (line 10 of Alg. 1), and thus the model-free algorithm can be analyzed in the same way the model-based algorithm. In practice, for applications where the raw observation states high-dimensional,, e.g. images, estimating the transition is often much harder than estimating the one-directional feature function. In such cases, we expect the V class be much larger than the class and the model-free approach to be more efficient.
3.2 PLANNING
Based on the feature vector and transition probability computed from the representation learning phase, new policy of (n+1) is computed using the planning module. The planning phase is conducted
5

---

Published as a conference paper at ICLR 2023
Algorithm 2 Model-based Representation Learning, MBRepLeam
Input: Dataset 2, step h.
2: Compute (w, Φ) == arg (m,)) (MMMM, Ep [log (ssssss(ssssl
((s, a)].
3: Return 3, P. P(s'ls,a) w(s') @(s
Algorithm 3 Model-free Representation Learning, MFRepLeern
Input: Dataset D, step h, regularization A.
2: Denote least squares loss: Lx, 8, == ED (()) 111013.
3: Compute = arg min maxzeF, [ming (x, - minjeo, (x,(0,0,f)
4: Return P where P is calculated from equation 1.
with www---ooonddeee-BBoiiie (UCB) style approach, and we maintain both optimistic and pessimistic estimation of the value functions and the Q-value functions
(in)
h,f h, hu 2i,"" which
are computed recursively through the Bellman's 's equation with the bonus function 3(r)) (Line and 10 of Alg. 1). Here the operator D is defined by (s) == Ba>)(() [f a)] Vf S $ A R, and (m) Th is the policy computed from M induced Q-value functions Q For the model-based setting,
we simply let ( be the optimistic estimator Qha For the model-free setting, for technical reasons,
we instead let ( be the nearest neighbor of Q in Mr. with respect to the || Ib metric, where
Ny C 5xA is properly designed set of functions, whose construction is deferred the appendix.
(n) takes either one of the following formulations:
Depending on the problem settings, the policy
For the NE, we compute Th 1h11 A,.......
(n) (n() (n) (n)
(n) "A.M
such that Vs S, i E [M].
Th (-1s) = arg max D
2 (s).
(n)
(2)
Wh.s
T (n) such that Vs S, E [M].
For the CCE, we compute
max Wh,s
I
2(a) h.. (s) s (Dz..) 0 (s).
(3)
h--
For CE, we compute T (1) such that Vs S,i [M]
(DWa.sooT (m) ((m) (8) S (Irm (s).
(D
max EBR,
Without loss of generality we assume the solution to the above formulations is unique, if there are multiple solutions, one can always adopt deterministic selection rule such that it always outputs the same policy given the same inputs.
Note that although the policy is computed using only the optimistic estimations, we still maintain a pessimistic estimator, which used estimate the optimality gap (n)) of the current policy. The algorithm's 's output policy स is chosen to be the one with the minimum estimated optimality gap.
The bonus term (()) is linear bandit style bonus computed using the learned feature à:
8(mh (s, a) = "n) (s, a)ll (s)))) -1, H..
(5)
((n) where 2h
E E(saten( 0h
(()) (s, a)o (s,a)T + Ala is the empirical covariance matrix.
THEORETICAL RESULTS
In this section, provide the theoretical guarantees of the proposed algorithm for both the model- based and model-fre approaches. We denote |M := maX [M,] and ( := m [dx]- The first theorem provides guarantee of the sample complexity for the model-based method.

---

Published as a conference paper at ICLR 2023
Algorithm 4 Model-based Representation Learning for Factored MG (MBREPLEARN_FACT))
Input: Dataset 2, step h.
(((()s(((((())))))))) 2: Compute (w,, Φi) = arg max (w. Ep [log (ss) ((s a.)], for each i [M].
3: Return { M P: a(s II
Theorem 4.1 (PAC guarantee Algorithm 1 (model-based)), When Alg. is applied with model- based representation learning algorithm Alg. 2, with parameters À O
aa(")
@ Hd log((M((NN/8) - e (n- log log((M(AN)66) by setting the number of episodes N to be at most
A log² (HaAAMM/==)),
with probability 1 - 6, the output policy á is an E-approximate (NE, CCE, CE}.
Theorem 4.1 shows that HERL_MGE can find an e-approximate {NE, CCE, CE} by running the algorithm for at most Ô (H 22g-2) episodes, which depends polynomially the parameters H, A, = and only has logarithmic dependency on the cardinality of the model class [M]. In particular, when reducing the Markov game to the single-agent MDP setting, the sample complexity of the model-basee approach matches the result provided in (Uehara al., 2021), which is known to have the best sample complexity among all oracle efficient algorithms for low-rank MDPs.
For model- free representation learning, we have the following guarantec:
Theorem 4.2 (PAC guarantee of Algorithm (model-free)). When Alg. 1 is applied with model-free representation learning algorithm Alg. 3, and X θ (dlog(NHH)//)) a( <(m) = θ An log logdaN
H Ad /M/MMe M log(dNHAM100)/))
and the Markov game
a Block Markov game. When we set the number of episodes N to be at most
O A log? (HdAM(&\/s))
for an appropriately designed function class (Na) and discriminator class (Fr) with probability 5, the output policy î is an E-approximate {NE, CCE,
For the model-free frree block Markov game setting, the number of episodes required to find an approximate {NE, CCE, CЕ} becomes Ô dd A While it has a worse dependency compared with the model-based approach, the advantage of the model-free approach is it doesn't require the full model class of the transition probability but only the model class of the feature vector, which applies to a wider range of RL problems.
The proofs of Theorem 4.1 and Theorem 4.2 are deferred to Appendix B and C. Theorem 4.1 and Theorem 4.2 show that oracle-efficient manner. We also remark that our modular analysis can be of independent theoretical interest. Unlike prior works that make heavy distinctions between model-based and model-free approaches, e.g. (Liu et al., 2021), we show that both approaches can be analyzed in unified manner.
learns low-rank Markov games in a statistically efficient and
FACTORED MARKOV GAMES
The result in Theorem 4.1 is tractable games with moderate number of players. However, in applications with a large number of players, such as the scenario of autonomous traffic control, the total number of players in the game can be so large that the joint action space size A = AM dominates all other factors in the sample complexity bound. This exponential scaling with the number of players is sometimes referred to as the curse of multi-player. The only known class of algorithms that overcomes this challenge in Markov games is V-learning (see, e.g., Bai et al., 2020; Jin et al., 2021b), value-based method that fits the V-function rather than the Q-function, thus removing the dependency on the action space size. However, V-learning only works for tabular Markov games with finite state and action spaces. Extending V-learning to the function approximation setting is extremely
7

---

Published as a conference paper at ICLR 2023
non-trivial, because even in the single agent setting, no known algorithm can achieve sample efficient learning in MDPs while only performing function approximation on the V-function.
In this section take different approach that relies the following observation. In a setting where the number of agents is large, there is often a spatial correlation among the agents, such that each agent's local state is only immediately affected by the agent's own action and the states of agents in its adjacency. For example, in smart traffic control, a vehicle's s local environment only immediately affected by the states of the vehicles around it. On the other hand, it takes time for the course of actions of a vehicle from afar to propagate its influence on the vehicle of reference. Such spatial structure motivates the definition of a factored Markov Game
In factored Markov Game, each agent i has its local state 8;, whose transition is affected by agent i's action a, and the state of the agents in its neighborhood Zz. We remark that the factored Markov Game structure still allows an agent to be affected by all other agents in the long run, as long as the directed graph defined by the neighborhood sets Z; is connected. In particular, we have
Definition 5.1 (Low-Rank Factored Markov Game). We call Markov game low-rank factored E [H, E [M]. we have
Markov game if for any 8, s' E S, a E A,
M II
Ph
0 (s/2,) a.) (wp,,
where Z; E [M], (s[,), a,), wT. Rd, (s[,,, a:)ll 1 and (, vd for all (s[7,), ai, s.). We assume [7g S Li E [M]. And we are given group of model classes Mn.;, h E [H), E [M] such that (0h, wh.)) Ma,i
We are now ready to present our algorithm and result in the low-rank factored Markov Game setting. Surprisingly, the same algorithm GERL_ _G2 works in this setting, with the representation learning module Alg. replaced by Alg. 4, and a few changes of variables. For simplicity, we focus on the model-based version. Define ((n) Kronecker product. Let
j2 (s, a) jeez ( (s|Z,) a,)
Rd where @ means the
M a) Σ
36 (s.
min (1)
(1)) (s.
(2. a)l (s!:)) -1, HJ. (n)
max (of-)) (E(M)
(1)
2HM Açtn)
where 5(m) = E (()))) (s, (),,, + Then, h,s
with and the
newly defined B(m), A (m) achieves the following guarantee:
Theorem 5.1 (PAC guarantee of GERL MG2 in Low-Rank Factored Markov Game). When Alg. is applied with model-based representation learning algorithm Alg. 4, with L = O(1) and parameters = θ (Ldt log(NHM((*/1)) .a(") = θ AH /Log((MM)NMM))) (ct))
(o by setting the number of episodes to be at most
[ ((L+1)) -2(L+1) (HdALM)M1/$s))
with probability 5, the output policy â is an e-approximate (NE, CCE, CE).
Remark 5.1. This sample complexity only scales with exp(T.) where I. the degree of the connection graph, which is assumed be O(1) in Definition 5.1 and in general much smaller than the total number of agents in practice. We remark that the factored structure also previously studied in single-agent tabular MDPs (examples include Chen al. (2020); Kearns and Koller (1999); Guestrin et al. (2002, 2003); Strehl et al. (2007)). Chen et al. (2020) provided a dower-bound showing that the exponential dependency on L is unimprovable in the worst case. Therefore, our bound here is also nearly light, upto polynomial factors
6 EXPERIMENT
In this section we investigate our algorithm with proof-of- empirical studies. We design our testing bed using rich observation Markov game with arbitrary latent transitions and rewards. To
8

---

Published as a conference paper at ICLR 2023
Table 1: Top: Short Horizon (H=3) exploitability of the final policy of DQN and GERL MG2. Bottom: Long Horizon (H=10) exploitability of the final policy of DQN and GERL_MG2 Note that lower exploitability implies that the policy closer to the NE policy.
H=3 Environment 1
H=3 Environment' 2
H=3 Environment 3
DQN
0,0851 (0.1152)
0.0877 (0.1961)
0.0090 (0,0200)
GERL MG2
0.0013 (0.0018)
0.0032 (0.0032)
0.0004 (0.0009)
H=10 Environment 1
H=10 Environment 2
H=10 Environment 3
DQN GERL MG2
0.2730 (0.3270)
0.0340 (0.0760)
0.0320 (0,0170)
0.0780 (0.1560)
0.0070 (0.0160)
0.0060 (0.0130)
solve the rich observation Markov game, an algorithm must correctly decode the latent structure (thus learning the dynamics) as well as solve the latent Markov game to find the NE/CE/CCE strategies concurrently. Below, we first introduce the setup of the experiments and then make comparisons with prior baselines the two-player zero-sum setting. We then follow by showing the efficiency of GERL_M _G2 in the general-sum setting. All further experiment details can be found in Appendix. F. Here we focus on the model-free version of GERL_ _G2. Specifically, we implement Algorithm. with deep learning libraries (Paszke al., 2017). We defer more details Appendix. F.2.
Block Markov game Block Markov game is a multi-agent extension of single agent Block MDP, as defined in Def. 2.5. We design our Block Markov game by first randomly generating tabular Markov game with horizon H, 3 states, 2 players each with 3 actions, and random reward matrix RA E (0, 1133333xx H and random transition matrix (8 0x) E As. We provide more details (e.g., generatiin of rich observation) Appendix F.I.
Zero-sum Markov game In this section we first show the empirical evaluations under the two-player zero-sum Markov game setting. For an environment with horizon H, the randomly generated matrix R denotes the reward for player 1 and Rt' denotes the reward for player 2, respectively. For the zero-sum game setting, we designed two variants of Block Markov games: one with short horizon (H 3) and one with long horizon (H 10). We show in the following that GERL GG2 works in both settings where the other baseline could only work in the short horizon setting.
Baseline We adopt one open-sourced implementation of DQN (Silver al., 2016) with fictitious self-play (Heinrich et al., 2015).
We keep track of the exploitability of the returned strategy evaluate the practical performances of the baselines. In the zero-sum setting, we only need to fix one agent (e.g.. agent 2), train the other single agent (the exploiter) maximize its corresponding return until convergence, and report the difference between the returns of the exploiter and the final return of the final policies. We include the exploitability in Table. 1. We provide training curves in Appendix. F.3 for completeness. We note that compared with the Deep RL bascline, GERL_MC shows a faster and more stable convergence in both environments, where the baseline unstable during training and has much larger exploitability.
General-sum Markov game. In this section we move on to the general-sum setting. To our best knowledge, our algorithm is the only principled algorithm that can implemented on scale under the general-sum setting. For the general sum setting, we can not just compare returned value to the oracle NE values, because multiple NE/CCE values may exist. Instead, we keep track of the exploitability of the policy and plot the training curve the exploitability in Fig. 2 (deferred to Appendix. F). Note that in this case we need to test both policies since their reward matrices are independently sampled.
7 DISCUSSION AND FUTURE WORKS
In this paper, we present the first algorithm that solves general-sum Markov games under function approximation. We provide both a model-based and a model-free variant of the algorithm and present unified analysis. Empirically, we show that our algorithm outperforms existing deep RL baselines in a general benchmark with rich observation. Future work includes evaluating more challenging benchmarks and extending beyond the low-rank Markov game structure.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
For theory, we provide proof and additional results in the Appendix. For empirical results, we provide implementation and environment details and hyperparameters in the Appendix. We also submit anonymous code in the supplemental materials.
ACKNOWLEDGMENTS
Mengdi Wang acknowledges the support by NSF grants DMS-1953686, IIS-2107304, CMMI1653435, ONR grant 1006977, and http:://C..A. Chi Jin gratefully acknowledges the support by Office of Naval Research Grant N00014-22-1-2253
REFERENCES
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in Neural Information Processing Systems, 33: 13399-13412, 2020a.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-201 20107, 2020b.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference Machine Learning, pages 263-272. PMLR, 2017.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
Yu Bai, Chi Jin, Huan Wang. and Caiming Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34, 2021.
Kimmo Berg and Tuomas Sandholm. Exclusion method for finding nash equilibrium in multiplayer games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint arXiv:1912.0668) 2019.
Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimization and the price of total anarchy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 373 372-382, 2008
Manuele Brambilla, Eliseo Ferrante, Mauro Birattari, and Marco Dorigo. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1):144,, 2013.
Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang, Efficient reinforcement learning in factored mdps with application constrained rl. arXiv preprint arXiv:2008. 2020.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv preprint arXiv:2102.07404, 2021.
Constantinos Daskalakis. On the complexity of approximating nash equilibrium. ACM Transactions on Algorithms (TALG), 933):-355, 2013.
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 Machine Learning, pages 1665-1674, PMLR, 2019.
10

---

Published as a conference paper at ICLR 2023
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference Machine Learning, pages 2826-2836. PMLR, 2021.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint vrXiv:2212.134433 2021.
Carlos Guestrin, Relu Patrascu, and Dale Schuurmans. Algorithm-direeted exploration for model- based reinforcement learning in factored mdps. In ICML, pages 235-242. Citeseer, 2002.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research, 19:399-468, 2003.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with constant discount factor. Journal of the ACM (JACM), 60(1):1-16, 2013.
Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games, In International conference on machine learning, pages 805-813. PMLR, 2015.
Junling Hu and Michael P Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov):1039-1000 2003.
Baihe Huang, Jason D Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approxima- tion in zero-sum markov games. arXiv preprint arXiv:2107.14702 2021.
Zeyu Jia, Lin F Yang, and Mengdi Wang. Feature-based q-learning for two-player stochastic games.
arXiv preprint 1xXiv:/906.000 00423, 2019.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. In International Conference Machine Learning, pages 1704-1713. PMLR, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficiet algorithms. Advances in Neural Information Processing Systems, 34, 2021a.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:21 10. 14555, 2021b.
Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent in large state spaces. arXiv preprint 1XXV:22006.03322. 2021c.
Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored mdps. In IJCAI, volume 16, pages 740-747, 1999.
Michael L. Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model--ased reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
11

---

Published as a conference paper at ICLR 2023
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstrac- tion and provably efficient rich-observation reinforcement learning. In International conference on machine learning, pages 6961-6971. PMLR, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-55 -1088855132220 2017.
Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3):1-29, 2008.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary De Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Shuang Qiu, Lingxiao Wang, Chenjia Bai, Zhuoran Yang, and Zhaoran Wang. Contrastive ucb: Prov- ably efficient contrastive self-supervised learning in online reinforcement learning. In International Conference on Machine Learning, pages 18 181101 PMLR, 2022.
Tongzheng Ren, Tianjun Zhang, Csaba Szepesvári, and Bo Dai. A free lunch from the noise: Provable and practical exploration for representation learning. arXiv preprint arXiv:2111 2021.
Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):88-86, 2010.
Shai
Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittiesser, loannis Antonoglou, Veda Panncershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-22 359, 2017.
Alexander L Strehl, Carlos Diuk, and Michael L Littman. Efficient structure learning in factored-state mdps. In AAAI, volume 7, pages 645-650, 2007.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline rl in low-rank mdps. arXiv preprint arXiv:2110.04653 2021.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-2 354, 2019.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. In Conference learning theory, pages 6682-3682. PMLR, 2020.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1966 1964. PMLR, 2020.
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference on Learning Theory, pages 4473 4525. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2023
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based augti- rl in zero-sum markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33:1166-1178 2020.
Xuezhou Zhang, Yuda Song, Masatoshi Uehara, Mengdi Wang. Wen Sun, and Alekh Agarwal. Efficient reinforcement learning in block mdps: A model-free representation learning approach. arXiv preprint arXiv:2202.00063, 2022.
13

---

Published as a conference paper at ICLR 2023
A ADDITIONAL NOTATIONS
Given a (possibly not normalized) transition probability P: A S x [H] - [0, 1] and a policy S x [H] A. define the the density function of the state-action pair (s, a) step under transition P and π by
d (8, a) = di (s))s))))), (8,+1(8,0)- = Σ
BES,aEA
We abuse the notations bit and denote (s) as the marginalized state distribution, i.e., d (5) EaEa dp a). For any [N], h [H), define
(a) Ph (s, a Σ
e p (s)ua((a),
i=1
Ph (8, a) = Sudp!) aaNl(A) ((((3,,)uu(())
t=1
Th (1) (s, a)
dp (s.
When the expectation ((s.a)~plf(s. a)] (or (or Eyr=)((ss) for some (possibly not normalized) distribution and function ʃ. we simply mean Eses.ee p(s, a)) a) (or Exes (s)) so that the expectation can be naturally extended to the unnormalized distributions. For an iteration n, distribution P and feature Φ, we denote the expected feature covariance as
En.o. (s.)~~ [0(s, (ss,))o(s,a " Ala-
Meanwhile, define the empirical covariance by
(a)
((s,a)b(s,a) TT + Ala- (s.a)ED
Σ
h.
B ANALYSIS OF THE MODEL-BASED METHOD
B. HIGH PROBABILITY EVENTS
We define the following event
E Vn E [N], E [M] E { (m) ,ph
((n), Bieaarp (1 -P a0ll s s(w))
= - [10x(s,
E Vn E [N], E [H] on th E S, (l)(ss (2io),) (202)))
mith (w)
3 ===
To prove E holds with high probability, we first introduce the following MLE guarantee, whose original version can be found in (Agarwal et al., 2020b):
Lemma B.1 (MLE guarantee). For a fixed episode n and any step h, with probability 5,
p(0) (-1s, a) - (7 a1) 111"" S log
M
(0.5)~(0055) "0 )
8
As straightforward corollary, with probability 1 5,
Vn N+, Vh E [H].
E (o.a))
((m) -1ssa))PP;((ssaa]]
<
log
nHM
n
(6)
Proof. See Agarwal (Agarwl al., 2020b) (Theorem 21).
14

---

Published as a conference paper at ICLR 2023
Based on Lemma B.1 and Lemma E.1 in Appendix E, directly get the following guarantee:
Lemma B.2. When p(m) is computed using Alg. 2, if we set
A= lo NH
M
((m) +
log 6
then & holds with probability at least 1 8.
B.2 STATISTICAL GUARANTEES
Lemma B.3 (One-step back inequality for the learned model), Suppose the event & holds. Consider a set of functions {9h 1h=1 that satisfies gh A RR, s.t. 19th lo S B. For any given policy
have
B(s,a) a
[on as)
AE (saa)p) (f(ss))), h h=1
p( E E(z,a)nd p(o),
min 1 (5, à)
INAE (m.a)pp)))) [o](s, + B +Bng(m),
h22
x-1 (3) 2(m)
--Ph-1-0h-
Recall Σ (m) 3(m) nil (s.a)~p))) (n) (s, ())
Al.-
Proof. For step h 1, have
E ((s.a)d pon,, [s) =B a (s,
max (s))T(((a)s)) (e.a)
(st a')p"" (m) lof a')l
pi (s, a)
( (a|s)
(s.a) di (s)uuA( (3% (1" (m) (o)(s',a')
max
AEE (s,0)~a(")
l9f a)).
For serptep h = 2, H 1, we observe the following one-step-bact back decomposition:
B(sa)~ar a
[gn (s, a)]
=B (R.a)dd (2.))-d7 (-0)
p(m) (a.ā),
[9n as)
(8) / Σ
= =B( (d ((a))) x-)
aEd
a)ds, B }]
=B(3.)) A-1
min Ph- a)
Σ
wh (12
aEA
11 Σ o0 (
<B(3,a)-d p00
min
(() oh
(3, a)
B
anp!
(n) (())
aed
(w) 201 Rin
where we the fact that ga is bounded by B. Then,
V/ Σ (a aEA
-1 11-1
15

---

Published as a conference paper at ICLR 2023
1h 1 (0)a " [o a 1 a)7] a12a)
(1 aEA
Σ
() a)ds
aed
[1 10 (0 ' Bd
<nl (2
(n)
aea aEd
[[uu (hals)gnnn
s and by assumption (10_ s vd.)
27
=n13 (5.0)-p
(n)
E (nsharea) (o) (s,
+ Bd
L9n (s, all 27
Snl (2.0)=p))) (n)
E Baapx P (3.0)
B² Ad nB²
(Event E)
P SnB (2,0)-p) (n) / (, ams [9h a)] B² Bddd+ + B²
(Jensen)
SnAB (3,))~
g (s. a)l + Bd + B²
(Importance sampling)
SnAB (ma))pp)))) min) [gt (s, a Ad B²
(Definition of p(,))
Combing the above results together, we get
((s.a)= ((m)) pln),
[gh (s, a)]
11 Σ (sm(( as)
<B(Ba) p
min a(m) (8, à)
mith b- h-1
aEd
(n)
1 (.))
<B(Bd))dd --1
min
(m) (8, ④
a)] + B2Ad + B2nç(n), (8,( (0.0)
which has finished the proof.
Lemma B.4 (One-step back inequality for the true model). Consider set of functions {ghh 1 that satisfies Ih S x A + R4, s.t. 11aalloo S B. Then for any given policy π, we have
E (e as)
AIE (s.0)~/f") (n)
(of(s. a)), h=1
B(aa))a7 110h (3, a)]l
()) [92(5, (a.))))))
+ B2Xd,
h 2 2
Recall 3 (6) (0) .0 nB ( (s) + Ala-
Proof. For step h = 1, we have
E(s.a/d77,, (s, a)] =E EEnd (m) (s)
di (1))T(((as))
(saa))) lof a')
(a.a) p (s,
(n)
di (s)TT (als)
(x.a) (s) ((" lof(s',
max
AE (s.0)~>()) (m) (gf(ss a)).
For step 2.... H 1, we observe the following one-step- back decomposition: B((.a)=d,,, Ign (s, a))
16

---

Published as a conference paper at ICLR 2023
(A))) (s,
- a
0% (8, / Σ (1m
-B(
aEA
<B(g,a)-dpra-1 1 (3,
Σ aEd
nith M----1 11---
Then.
1 Σ wh (0
aEd
nith 1
Σ wh winn(()ma(ass)anns.co a)ds)
nE (1.))) (oh-1(s, (s))))))))s(s)))) + +Ma)
(155)
Bwwh (ommaaaaa as)
aEA
aEA
(155 acd
(s) 0h-1 (5, ( (aaaaaaa /
<nB (1))))
(n)
Σ
+ B²Ad
(Use the assumption EEaed (als))g (s. a)l S B and ( S va.)
(Eewpy (Eewpy (4.0) (s,, a)l] 2
=n (3,0)18--) (n)
+ Bd
SnB (1.ā)- P (1. (~)
( (s, a)] + B²
(Jensen)
SnAB (- - (a
(n)
[9 a)) - Bd
(Importance sampling)
SnAB ((a))=p))) (n) (s, a B² Bd
(Definition ())
Combing the above results together, we get
Essa)rdy a (9n(s, a)]
ee Ph -
anma(() (8,(8,
<T <BBBBa) | (8, a) =--
Σ
with- 19
aEd
h- 18
<B(,,)) (100
a)
nAB (s,a)-p
(8, a)) + B2
mith
which has finished the proof.
Lemma B.5 (Optimism for NE and CCE). Consider an episode n E [N] and set (a)
θ (H)n))(") + dd). When the event & holds and the policy (!1) is computed by solving NE or CCE, we have
(m) (5)
0
(()()))
-HVAÇ(n)
Vn E E
(D Murr 2 (x) as the best response policy for player
Proof. Define / (-18) = arg max,
i at step h. and let m pi! x Th-i Let ((m) ((
(s, a) = (- a) - (7)((ss then (-1s,
according to the event E, we have
(s,"(),)) s ((()),
E (( (1 (s,aa)) s <((m),
E. (((.)))((")) (m)
Vn [H),
17

---

Published as a conference paper at ICLR 2023
|l (s, a)ll (str)) ) @lien(s.
a)
vn E [N], E [H], on E Ph-
mich on
direct conclusion of the event & is we can find an absolute constant c, such that
( (8, a)
min
a (n)
((m) Ph
(8,
a)
H
I(n)
min
ca (m)
|0
(3, a)
H.
Vn E [N], h E [H]
E-1 mipb
Next, we prove by induction that
1.m (m) (s)
11
E sondttn) p(n),) d
Vinii
2
E
(s.a)
(n) p(
g(m) (s, a) H min (s. (s))).
vh e [n].
W=
(7)
First, notice that 4/h E [H]]
E (n) (1n)
(s) - h,
(xx
(s)
=B
sned((n) pin)
(D. (D
2h. ( (s) (Dacoett stri???
(s)
p()),
g S (8) D (Dago) Qha
t
> enddain) pin)
(8)
(m) (s,
1. (n) -Qhi (8,
=F =B (s.a)matln)
p(n))
(n) ) M (n) is the NE (or CCE) solution for ( S i=1
where the inequality uses the fact that mh ready prove equation 7:
Now we are
When h = H1 we have
v11==1)) " (8)
(n) (s,
I
Hs))s)
E
(s.a)aataa)
p(r),
((()) (s.
(s,a)mat(0)) (1)
p(n),
((a) (s, a) H min { (s.
>B
(s.a)nddit))
(n) p(n),
Suppose the statement is true for step h + 1, then for step h, we have
- (n) h, (s)
E smadlaa)
Ma),
Q (8, a) - 2 (s.
21 (a.a))a((1) p(n),
((m) (s, a) (P( mitl)) (8, - ( (PAviaa?? V (s.
= (0, (dett)
p(n),a
((m) (s, a)
(p/w)) (Vii) Vutti Vol (11
)) (s, (s,
((A)))
Pt)) vil (s a))
E (a())
(s, pin),
3(m) (s, a)
(P/m)) -P;) Vilti,3 (s, (s,aa +
(nn)) (ir))((s)
v (s)
(s.a) ((())
p(n), A
pin),a
((()) (s, a) H min { (1()) (s, (s..a))))
((n) [s) - v (s)
(s.a)
+ smdt(n)
pin), x
p(m),441 A+1
18

---

Published as a conference paper at ICLR 2023
H
3(1) h (s, - H Hiin [1 (8, (s)),,)))
2 (n)
(s.a)aa
pln),a
M==h
where we use the fact
(P)))) Px)
H, p(x) (11s, P% a) 11
11, (m)
h+1,
(8) Smin
h
h+1,2
SH min {1, p(m))) (1s,a) a) P)())s, |1
{ 1, (s.
=H min
and the last row uses the induction assumption.
Therefore, we have proved equation
We then apply h to equation 7, and get
Egwdi V (n) i. (s)
V/,5 -
(in - -vi,,
1 (s)
(s)
E
stn)
pim).1
H
[(()) (s, H min (s.
(s,a)mat(n)
pln),a
h=1
Σ
E
(s.a)aatim)
(n)) plm),
g(m) ph (s,a) . Σ E
(s.a)
min (shh
pin),
Next we are going to bound the second term, let (s, = minks ((m) (s, a), 13 and apply Lemma B.3 to gh, we have for h = 1,
min (s s\ AB ( (1 S VA((m).
E
And wh 2 2, we have
min (m) (s, a) 1)
E (sa))arii))
pin),a
+ dl mc(m),1) }
(m) hh (5, a)
nAA (s.a)) (()) (sh (s. )²
27
<B (3.0) a-1)
min
11
SB (B.d))adetn
min
hh (3, à)
(())
VnAç(n) dd + n((w),
A-1)
((1)
Note that we here use the fact min (z)
(s, a), 13 < 1, E (e:))~/f))
(n) (1 (15
(s, a))
) 27
S ((x)) and
(1 (1))() < (1)), Then according to our choice of a (1), we get
E (((a)~/!
(1)
E. (s.a)maz(n) (n)) p(n),a
min
f/ p(m) (s,
s E (s.a)
min
(n) hh- (5, à)
(in)
p(N),
H
8-1 (m) (n)
Combining all things together,
(n)
0
1.0
Eandi
V (1) 1 (s)
(. (s)
H
H > hm
(8(m) (s)
min (1 (s. .), a),
(el))~ p(N).
(
h=1
p(n)
19

---

Published as a conference paper at ICLR 2023
H-
3l (8, - min { c 1 (5, a)
.
H v Aç
dd pln) &
(0) (
H AÇ which proves the inequality.
Lemma B.6 (Optimism for CE). Consider an episode
E [N] and set a
θ H (HVnA(()) + dx). When the event & holds, we have
(s)
max of wel;
(s) 2 -2-H -HVAC()) Vn [
Proof. Denote [6.0. arg max (D. Puron (n) max 2h2
(s) and let //-²) oo (n)
(s, a) = (//)) (-1s, a) - --((-,,, |)) then according to the event &, we have Let (s,
E ((aa)-of (m) (1s <((m),
((a.))afi0) (s,)( S ((m), An [N
E
(s (5500) ) 2
(10)((0,))
Vn E [N], E [H] on on-
with (m) ,0.
direct conelusion of the event & is we can find an absolute constant c, such that
( (s,a) a) min
(n)
((m) Ph
(5, a)
-1 .
min
(" (m)
| (3, a)
H
Vn E [N], [H].
(n)
Piph 1b
Next, we prove by induction that
H
V (rrl(e)
max VOOO (1n)
(s)
[B00 (s, a) 11 min { (s a), 1)]] (s,
vh [M].
(s.a) (s.a)aatie)
p(n), b.
WER;
h-=h
(8)
First, notice that wh E [H].
E
(Ndd(()) p(n),)
has
max (nwon())
h2s
(8)
=
snnda())
TD (m) Q
(n)
(s)
D (m max Quor wesl
(8)
WEs,
E souetffi)
1 (n) 2
[n)
(s)
D Decos max Quor(()
(5)
p(a),h
west
=R
(s.a)at(n)
(ns)
Phil (s,
a)
max Queom(() (m) (s, a)) well
pen).
where the inequality uses the fact that Th prove equation 8:
(x)
is the CE solution for
Q
Now are ready to 1
When h H, we have
E
(nn p(n),
(s)
max (wor(() (1) WEBt
H.
(s)
>
E
(s.a)~aat))
(s,
max QuoT wel,
(s, a)
pin),
[(m)) (s, a))
p(n),
> E
(s (s
(((m) (s, a) -H min { (d))) (s,
{
p(o),
20

---

Published as a conference paper at ICLR 2023
Suppose the statement is true for h + 1, then for step h, we have
Viln (s)
V (n)
snidaln) p(n),
max Wenn
Q (s, a) max ThA west
QuOTiIn (s,a)
>B (s.a)~dt(()) pin), de
((m) (s, 0) + (P/ h+1,2) (8, (8,
Py max Visor( (n) WEnt
(s,
(d
p(u) de
3(m) (s, a) + (p((a) (vin))
)) (s,a) + (1/ wEn, hii,s
(m)
-Pp
max Vieat well;
h+1.8 (s. (3.a)
(s,aa (s.a)~a (()(
max
pin),
=B
(s.a)
3(m) (8, a)
-Pi) max Vitpri (8.a) wesh
-Ph)
pin),b
Vil) Vitti1() weit;
Vivar,"" (6)
B anda(n)
max
p(n),441
>E
(d.a))da)())
(5 (s,a) -Hmin {1h (s.
and (n))
(m) (s)
mmx V (1)
(s)
p
welli
H1
[Bpt (s, H min (s,,,,))
(x.a)~deln)
p(n),a
M=h
where use the fact
(p(m) h
Ph)
max (woa(()) (n)
(s, mmin
H, pr (-|s, a) - Pi(-1s, a)
11,
max (worln) (n)
wen, h+,,i
LES;
<H min 1 p (1s, a)
=H min 112
and the last row uses the induction assumption.
Therefore, we have proved equation 8. We then apply h = 1 to equation 8, and get
Egndi
V 1, (s)
wEl, 1,5
max (wwor()) (r))
(s)
=
snga(() M(n),
V 1,
(s)
1,$ wes,
max (mwon(n)
(s)
(3(m) (s, a) H min {1h (sl 13]
(s pln),
H
H
(((1) (s,a)] - H h=1
>
min { (s..).
(s.a)
(s.a)aan(a)
p(n),
Ma)
h=1
Next we are going bound the second term, let gn a) = min(fl ((m) (s, a), 1} and apply Lemma B.3 to gh. we have for h = 1,
min (s) s
AB (B (11 S /AAC (n
E
And Yh 2, we have
E
min ((()) (s, a),
(aa))az(o)
<B (2.))=
min
(n) o h (3, à)
nAE (s.0)))(())
(11 as)
+ dl + nc(m),
-1
21

---

Published as a conference paper at ICLR 2023
SB
( (l))
A00, A00
min
(3, a)
VnAç(n) + dd + n((m), .1
Note that we here use the fact min(sh (s. a), 13 S 1, E (sa))~
(1h
(s, a)) s <(n) and
[11 (2)) s (())) Then according to our choice of a (n), we get
B ((aa))
(x)
B
(s.a)natll) pla),a
(s, S B (a.))mat())) p(n),a-1
min
ph-
((m
H
(n)
Combining all things together,
(n) max 0/
E
Byndd
Vin (8)
max Vinalln west 1,
(5)
wEft
[Blu (s, (s)
min {Thh
(s, a). }]]
(t)a) p(n),
E
(e a (d)
pln)a
1- 1
15.0a-azion
(m)) p
((4) (s, - min
ca
(())) |0h (3,
H
V AÇ(m))
4=1
(1) .0h
H Acim)
which proves the inequality.
Lemma B.7 (Pessimism). Consider an episode E [N] and set a()) θ (HV/AA(()) + dx).
When the event & holds, we have
(n) (8) U. (n)) (8) S SHVAÇ()) AÇim), Vn E [M], i (M]
Proof. Let f(a) (s, a) = pk(n) (-1s,a) - - a))|, then according to the event E, we have
E ((ra))/( (11) 2 $((m), E ((sa)))p??) (s.")s s((m), Vn [N],h [H].
[Ion(s, a) m
|l a)ll (3) (
Vn E [N], h E [H] on e o,.
A direct conclusion of the event E is we can find an absolute constant such that
(s, a) min
(n)
Ph
(3,
H
2 min
(n)
(n)
|
(3,
a)
H
Vn E [N], h e [4].
(n)
(())
miph
Again, we prove the following inequality by induction:
H
[s) - Vir (8)
|-
3(m) (s. a) + H min {1K (s, a), 13]]
wh E [H].
(n)) p(n), d
(a.a) (o.a)~ar(n) (n)
pln),
h
(9)
22

---

Published as a conference paper at ICLR 2023
When h H, we have
(i) VH,i (s)
[ a) - Qhi (s.a)
E
soodpfe)
(n) p(n),,1
=E (s.a)maplnn
H1
pin),
=E (s.a)radp(a))
3/m)
H (8,())))) (s.
p(n) p(n), 11
SE (s.a)ro p(o))
B(m) a) + H min { { (s, [
,1
Suppose the statement is true for h + 1, then for step h, we have
[x) (s)
Vh.s (s)
snadlan) Maa),
[o ()) - -Qh a)
(d pin) &
- (s, + ( (s, a) - (PXV (ittiss) (s. [)
(9)
p(N).. A (s.a))drt
(s, a) + (P/ (Wnti, Vislis)) (s, + ((P)m))
pi: V (s)
E
p(N)
[ + ((P)-) -Pk Vitt.:) (s,a) +B Bondrl))
[[ [K Vittt.) (s)
=B=
(d. (n) pin),
pin) a+1
[B8 a) + H min { (1 +E smatla))
[ khtli
(v(())
- vatt.:) ) (s)
<E
(n) (s.0)~de(m)) p
p(ni,a+1
11
[- (s, a) + H min {1h (s)
(s.a)mar p(o) p(n),aa
M=h
where we use the fact
(P%))) h - Phi
var(m)) V
(8,a) S min { H, p(x) (11s, a) P7 a)
|
Vottie
1 SH min { 1, p(x) (116,a) (1 a))
|11
=I1 min
(1) 1, 5/ (s, })}
and the last row uses the induction assumption. The remaining steps are exactly the same as the proof in Lemma B.5 or Lemma B.6, we may prove
min (s, a), a). s VAC!),
E
(s.a))aatlo (n) ((0)
and
(n)
B (eea)aapta) a
[1ht an) < E
(3,a) p
min
(n)
())
4h 2 2.
H
(m)
Combining all things together, we get
(n)
(s) (s) VI,"" (s)
= =Bardd
H
[- (/ph a) + H min { (1 (s, (s.
F3 do(n)
p
h=1
H-1
<
E (s.a))dn(())
(o)
3(mm) (s,
a) (s,a) min (m) (ساي0) (5, --ع (0) (n)
.H
+ H v Ac(n)
pla),
h=1
<H (A(i))
which has finished the proof.
23

---

Published as a conference paper at ICLR 2023
Lemma B.8. For the model-based algorithm, when we pick X = @ (dlog N ) ((
[MHHN) ) and (n)) = (nnn + dd)). with probability - 6, we have
log 8
M
Σ A (n) H log 8
Proof. With our choice of À and 1 8. Furthermore, we have
(("), according to Lemma B.2, we know & holds with probability
MHN
N
HN
( = HH
A log
d² log 5
dH
Alog
5
Let 1/ (s, a) = (-1s, a) PP a)/l
According to the definition of the event &, we have
(1))) s (1))
(Sth.on) )- θ @1en(ss,0)s
mobh .0n )
snpp (n)
Vn [N], [H], Φn 2
(10)
By definition, we have
(n)
max
{ (n)
vi
2H / Açtx).
iE[M]
For each fixed [M]. h E [ and n E [N], we have
Frl) h (s) V (5)
E
(ndd
[ 1. (
0..1 (n)
(s) [D (D..o (s)
E
snmpp())
E
Q (s, a) (f/
(sa))apin) p
2)²(1) (8, (8,a) + (P()) (V(n) Vit1. - -iitt.)) (s, (s.
(s.a)~dz()) (m)
2,3(m)) (s, a) + ((Pk (pp(")Pp?) -P:) (itt1, kotl.)) (s.aa + anapla)
V(n)
(htz((() -((a) (s)
(8.0)~ap(m)
p
(1)) (s, a) + 2112 f((1) (s, a)} + E
[ - (x) (s)
<B
(s.)) p..
Note that we use the fact T/
easily using induction using the fact that B(m)) (s, a) H. Applying the above formula recursively (m) L41,, (s) is upper bounded by 2H12, which can be proved
(s) v (s) one gets the following result (or more formally, one can prove by induction, just like what we did in Lemma B.5, Lemma B.6 and Lemma B.7):
to E
(n) s P 11l
H
H
V (s) - [.) <
Σ
(n) [3(0) (s, a) +2H²
(s. a)
(n)
(a)1))
(s.a))ap())) pa
h=1
(11)
First, we calculate the first term (a) in Inequality equation 11. Following Lemma B.4 and noting the [(n)
bonus Pp O(H), we have
H
[ (s, a)
(2.0))dr(1))
24

---

Published as a conference paper at ICLR 2023
11
(s.a)~ d (n) pr
min (m) |0
(s, a)
(From equation 10)
h=1
H
(3, a)| (m)
n. (alv)) 2
( (s, a)
2
+ Hadd
(5. a
(pp)) (m)
1=1
(aln))) 2
|10 (s, a)
+
(s.a)>/f())
x=1 (n)
Note that we use the fact that B H when applying Lemma B.4. addition, we have
|108%(..000
n. (s.a)mpp))))
mich (ff
(Braa)ms(") (oh (s, a) (s, (n
(2))) 9h (8, a) (s, (s) + +laa)
)
=nTr
(aa))pp))))
(n)
Sd.
Then,
"
Σ
E8
(Bf0 (s, a)} s E (x.a) (sa))ap(h))
(5, a)ll=
v dA (almi)) + Hadh vdA dA (a(m))²/n
(s.a)aapt))
1=1
Second, calculate the term (b) in inequality equation 11. Following Lemma B.4 and noting that
(*) (s, a is upper-bounded by 2 (i.e., B = 2 in Lemma B.4), we have
H
(((") pc,
(s, a]]
(n) (s
(s,)) dd + v AB (B(aaa)pp (s,)) 27
E
(8.a)
pa
(n)
(,,5,)))l with
c0) mn
nABE (s,a)rp))
(3.a)~dp())
(n)
(5 اللا
VnAcim) + +d VA((m)
pr,h
niTh 16
(a)
H
(1)
+ VAC(),
H
(1.5 a)) s c(m), and in the last line,
where in the second inequality, we use ((a))=(())
recall V nA((()) dd (n /H. Then, by combining the above calculation of the term (a) and term (b) in inequality equation 11, we have:
(m) 2.
(n)
Vil (s) (s)
=E
sndp(n))
dA (aln))² 2
E (3.)) (ec)
(o
V dA (a((ml)) + H2dX +
n
with
H-1
(n)
2
E
(3.0)~ (n)
110 ا)
+ v Aç(n)
Taking maximum over i on both sides and using the definition of A (m)) we get
(n) max 3E M
{ (m)
mnn + 2H 2HH Acim)
AA(i)
25

---

Published as a conference paper at ICLR 2023
H-1
dA (all))
E (8.0)_dph.
(w)
110% (8, ".,a)ll-
VdA VdA (a(n)) + HHdd +
1 .8
h=1
H-1
(n)
2
18
(3.0)~apt))
(3, a))
AAçtn)
(1)
h=1
nith
Hereafter, we take the dominating term out. Note that
Σ
E
11= (5, (a)
N
E
07, a)
T
(5, a)
(3.0)~dp()) pr.k
(d pe,
mith o
with
(CS inequality)
N
N
log det
Σ
E
(a aa - (n) 10% (0)
log dett
(Lemma E.2)
==1
N
dN log
1
dA
(Potential function bound, Lemma E.3 noting (1, a)l1a I for any (s, a).)
Finally,
N
(JaNlos [+ )) dA (a(ov)) + HadA+
N
dA (a(x)) )²
Σ
a (m) S11
Σ n=1
12
N
+ H
dN dN log
[1
N
(
Σ
Aç(n)
H
dA
n=1
<1&d
NAlog
1+ (N))
N dA
(Some algebra. We take the dominating term out. Note that (n) is increasing in n)
[MHN
oH log 5
This concludes the proof.
Proof of Theorem 4.1
Proof. For any fixed episode and agent by Lemma B.5, Lemma B.6 and Lemma B.7, we have 1a
(m) max won
(n)
2i (n)
+ 2H V Açtm) < (m))
WEn;
Taking maximum over i on both sides, we have
(m)
(n) Har
of (prt(())
(1z(m)) }) Sa(m) (m).
max [E[M]
max <E[M]]
max
(12)
WER.
From Lemma B.8, with probability 6, we can ensure
MMHN
Σ HH log
8
Therefore, according to Lemma E.4, when pick N to be
Hdd 1
A
(HdAMM)
0
log²
2
2
8
26

---

Published as a conference paper at ICLR 2023
have
N
(K)
Se.
N
On the other hand, from equation 12, we have
}
max M
or max iE|M]
max of WEll,
2/
(n
(n-)
max 0. uuootnn WElh;
- -0gite))
max ic[M]]
U;
or max
iEIM
[n(n)
min nE[M]
(n)
(1) Se
N
n=1
which has finished the proof.
C ANALYSIS OF THE MODEL-FREE METHOD
For the model-free method, throughout this section we assume the Markov game is a block Markoy game.
C.I CONSTRUCTION OF M₁ AND Fn.
ax)TToa E Tn, E [N], 8k E S,a a E A, vk E [1] Fix a variable L, for each h [H], define function class Fn E ERSxAby
Let CΛ = (Ex : Σ, = AIa + Ek (sk,,,
Fr f(s rs. a) + (s, To min (cllo(s, (s,,a))))) ر)ا
i [M] on E tn 110| < 2H V E LJ, En Cx)
For given parameter E, let Nú. be é-net of Fr, under the I metric. Define II, as the set of all possible policies produced by equation (or equation or equation 4, according to the problem setting). We then define the discriminator function class Fn, as followings:
Fi.b =
{ {(() EA-U(A) [1) (s. T
dn. &h t,, max [10112] s vaj.
Th+1, a) 15 a) To
i [M] Th4 E Th+1. 0n+1 1 11112 s val
F2. =
f(s) = Eawassi(e)
H
Th+ H
Fan =
((s) = max E
Bhtt,
i [M], Th41 E Uh+1,
# 1011| S Vd
(For NE and CCE)
Th+1,
Fa, = f({) =
E Ba-
max
+ (1,
H
i E [M], mh41 E M1+1 1 |0|| S Vd!
(For CE)
min ((lon+2(s,,)) a)
FA. = f(s) = Ea-ah (1(4)
+ (n,1
H²
CE [0, L), Tht1 E Mot.. Eatt E Ch+1. Oh-1 E & 10112 s vd
G== (f= (0,
FA UFIAUFFA UFa U.F.)n
27

---

Published as a conference paper at ICLR 2023
C.2 HIGH PROBABILITY EVENTS
We define the following event
E Vn E [N] [ E {ph) -ph J
Ep [(( - -p;) f) (s, s((u),
& Vn E [N], E [H] on E th. 100(s,a))( (Smnon)) )- Q
[Iōn(s, (0p(1,,)lls-- a)lاs;- (m)) (a)
8 : 7
Similar to the procedure of the model-based case, we first prove a few lemmas which lead to the conclusion that & holds with high probability.
Lemma C.1. For any n E [N], E [H), we have p(m) (s'(s, a)
T(t) (s, a) wh (s') for some wh (n) S + Rd. For any function f S + [0.1] and n [M], h E [H]. we
have
2 I Vd. and there exist 0,0 E Ra such that (PP)) (s, = (s, T) 0, (Plm)) f) (s, a) = 3 (s. T and max [0112] s Vd. Furthermore, we have |0 S.
|ss 00 1h) (s)
Proof. By definition, we have
(z, = / P)(d'ss,))S(11)
as, / wf(ss)s(s''ds'
(s T.,
where 0 = fs (s()ss(ss)dds' who we have
Furthermore, note that || I 1, according to the assumption on
S <vd.
(p(m)) /) (s, let
which implies |00||2 < dd. For
Wh (n)
(5')
Σ
(d) (5)
(n) ( (5) Ala
Σ
(0 (5. 1x-s
(F.A)ED) ((
(5 (D(
(s, a) is an one-hot vector, one has (5)) $ 1, E S. It follows that @h (8,
Since
(s') have
[ wi (x)
1, and therefore, || (s')(('s)' S Vd. By definition, we
(p(nt) 1) (s.
((() (s1ss,)))) Js
= = (1 (s. T)T / (s)((()
=
(n) (s. a)TT TØ
where Ø == fs fs vi(h)) (s') Due to the property we just derived for (/(.), similar the proof of the true model, we also have |101]2 < vd. Meanwhile, one can easily see that ||0| S 1, using the fact [Ss (..h))())) (6))(("')ds')) < 1.
(n))
28

---

Published as a conference paper at ICLR 2023
Lemma C.2 (Covering Number of Fr). When dn is the set of one-hot vectors and X 2 1, it's possible to construct the ě-net Nn. such that [Wn S M
( (12811224
3d
| vh E [H]. Furthermore,
we have [T,]| S Wa M S MM
[12H"
3Md
|
Proof. Recall that
Fn =
an) + min(cllon(s, a)| m
i (, E t 1012 - Vd, (0, -1 E.))
Note that when P the set of one-hot vectors, Σn will be diagonal matrix. In this case, Fn the subset of the following function class:
F = f(s,, a) = (n) + minfcon (s. T H) - (s (s) To
E [M], on Pn 0 S L, max [100 2, 12 S 2112 Vd).
Let θ be an f2-coerr the set {0- Rd |00|| S 2112 vd at scale ē. Then we know |0) S 1H2v/) Let W be la -over of the set [0. L] at scale E' == 2H have [W S LH'LVV
Define the covering set by
Fn f(s.a)= =- -s,iis, a) + minfcon TO,, 1I + (n a) 0 iE [M] & W, 0' eo
Then, for any Fr, by definition, suppose f takes the following form:
f(s.a) = (s, a) minfeon(s, as) T H) + on a) To, 0, 0s S L, max ( |20 [0]11]] s 2H2 Vd.
Then we can find 0, 0 E O, W such that ||0 - 0||2 1, - 0'112 S and Ic - य S E" Let
:- : a) + (s l) + on (8, a)
then we have
[[ a) [(s a)l
(l a) 0 0|
(s, | c0'
<e + j2 cl |00 + c celor 0'
<8 2H2 de V + L
<3LE,
which implies F, is 3LE-ooerrin of F (therefore, is 3 of Fi). and we have
2 3d |
F S
12HH2 3d
Replacing by 3L. we get an Ê-covering of Fr, whose size is no larger than M
|$b.
For l1g, since each policy is determined by M members from No. we have [Ia [ which has finished the proof.
Lemma C.3 (Covering Number of Fi). When dn is the set of one-hot vectors and 2 1. The
--ooering number of Fr. is most 4M [1
GLPd
/
Proof. We cover Fi,,, F2, F Fsh Fa, separately. For Fi.ho let O be an fy-cover of the set (0
Rd |101|2 S vdl at scale y. Then we know |0| < 2v/d d'
Define the covering set of Fi,
Fia = [(s) = Eanucal [on(s,a) TO & (s. a) [0] dh, & E tn, E,, 0,0' E )
29

---

Published as a conference paper at ICLR 2023
For any f E Fi,h, suppose
[()) = (a) [l (, (T on 0/ E 2n max 1101 s Vd,
Then find 0, 0' E O such that |0 0112 7, - 811|2 n. Let
f(s) Ba) (bn(), - (3 T
Then we have
f(s)
Σ
1 a)12 1
+
Σ acA
(1, (s, a)1la 00-8
A aEA
S2n;
which implies FI, is 27y covering of Fi. Furthermore, we have
2d 2d
|i S
|0/2.
For F2, and Fs,h. we construct
F2,n = { ((0)= 1 (ane
1h a)
[M] E 0p41, E O, ah41 E eTa+1
H
Similar to the proof of Fi,h, we may verify F2,1 is y-covering of F2 and
2d d |
F & M
For F3.h. we only prove the case NE or CCE, the case of CE can be proved in a similar manner. We construct
(8,
Jah:= : f(s)= = max Ba- X044,, pa+ia
+ ( T)
H
i E on+1 E tp+1, 0,0, Ila+1
For any f E Fs,h. suppose
f(s) = max (a XTA1...))) Th+1,a(s.a) Pa11i
+ on (nt iE [M, E Th+1, 6441 E Cha11, 1|012 s Vd.
H
Then find / E O such that ||0 - 0112 7. Let
+ )0+1(1,)) 0)
f(8) max Bao-(Ben,, Phti,
H
we have
f(s) - f(s) = max
Th+1,1(8,a) a)
+ (st To
Pat1.1
H
max E Ea
+ (),
Bh+t,
H
Th41, a)
< max PM41,
E Bo-
+ (s,
H
r141,,(s, a)
+ 00
H
EA (Fa-(Ph11,XXR11 (1()) ( a) TO an) To)
max
Pi 1.;
<|00 0||
30

---

Published as a conference paper at ICLR 2023
S7
and
rh+1,((,, a)
f(s) - f(8) = max Ba (a-0
H + 1s,
7h+1,)(,,))
+ +0)
max Sa-(f211,, e)())
Ph41,
H
(h+1,i(8,0)
< max
Ba-
+ (s,)
1.111,
H
(1411a(s,)) a)
+ 0
Pa--(in11.
H
(Fa-((the,, (00 (0, T) 1n a) a)To) 0))
max
Ph41.
0 0||2
S%
which implies
[(s) -(s)- s.
Therefore, conclude Fo, is y-covering of F3, and
2d
Fanll s M|
|+]
For Fi,h, note that when P is the of one-hot vectors, Σn will be a diagonal matrix. In this case. FLn is the subset of the following function class:
minfcon+1 To, H) + (0,
Fin = S(8) (awxn+1
H²
0 0 L, Th+1 E 11441, max 110 S Vd, Φht1 E Sntl.
In this case, let W be an lo cover of the set [0, L] at scale 7= Ja. we have IW] < Lvd
Let
min(coh+1 (s, T)T 0111, H} (5,
J4, = f(5)== = Eartat1())
1²
EE W, Th+1 E 1l+41,0,0- E dn-1 E Snt13.
Then, for any f Fa,ho suppose
minfcon (s, a) TO, .II + on (s, a)To
f(s) = (aNTA+1
H²
C L, Tht1 L 11, max 10'112) S Vd, Φht1 E Ph-1-
Then find 0, e O, e W such that 1|0 0|12 - 7, 1 00 I y and c ol S.. Let
m
0', H}
f(s) = Ea Eawasa
+ のn (1
H²
then we have
1ʃ(s) - [(s)
SBanner()) (10)+1(0,0))22 0-0
-6
E Barana (8)
(s, a)ll 20 c0/l]
H2
31

---

Published as a conference paper at ICLR 2023
+ 1
1T2 (o- ( c/ 101 + c =011)
5 + Vd L
H²2
+
H2 ?
S3L7,
which implies Fa, is cLoy-cre of Fi,hs and we have
2Ld
3d
Fa,n S |
|
7
In summary, we know ;= == Fi, U Fe.n Fo,n
U.A.A. 3Ln-covrin of Fh. And
2Ld
3d
FN & 41
Replacing y by 3.. get 7-covering of Fh whose size is larger than
4M| (6Ld)) |ob?, which has finished the proof.
Below we omit the superscript and subscript h when clear from the context. Denote
(x.0(0,0,f)
1
(é(s. f(s')) 2 + (s,0,)")ED
Σ
[ 00
(13)
D
CD(
Σ
( 5(5'))
(14)
D
(s.D
C,(0,0,5) B(ssa)=
(15)
Lemma C.4 (Uniform Convergence for Square Loss), Let there be a dataset D= {(s, a; ) collected in n episodes. Denote that the data generating distribution in iteration by de and p= -'E di. Note that di can depend on the randomness in episodes 1,....i - For a finite feature class & and a discriminator class show that, with probability at least 1 - 6:
+ [0, 1] with 7-covering number [| we will
|[ 0) C,(d", [] - (L 0, ,D(0",0,,J11
- 0, Lp(0", ,7, 64 log( 2(4n)* 1F11
1
for all o E &, 100 S 1 and f E F, where recall that o* is the true feature and 0' is defined as Eg (s)))(() ( (s, a), 07).
Proof. To start, we focus on a given f E F. We first give a high probability bound on the following deviation term:
(c. - -,
(Co(o, f) Lo(ø", (o(0",8,.f) f)).
Denote g(5,, a:) = Φ(si, a;) and g" (si,a;) = "'(si, T At episode i, let Fi be the a-field generated by all the random variables over the first i episodes, for the random variable
Y; = (g(si, a;) fs())) (g' a.) ((s)))²
2 we have
E FY =E (o(s), a:) - f(s()) (g" a:) a;) f(()))²)
f(())))
= E [gg(s), a.) + g (st, a.) - (f()))) (g(s,, a.) 9" (st, a.))
=E (o(s;) a.) 9" (s a.)) =
Here the conditional expectation taken according to the distribution F-IFF-1. The last equality is due to the fact that
IF. [(g (8i, a.) f(x)) (g(s;, a.) g" (si, az))
32

---

Published as a conference paper at ICLR 2023
s.
[Bg ((g a.) f((()) (g(s;, a.) g"(ss, a:)) 8t a:l
=0.
Next, for the conditional variance of the random variable, we have:
V[Y] SB ( E [o((s a.) 9" (82, 2f(s)))² (g(s), -9 as))
<16B (g(s), a.) (8,,,,;)) [i-1] [F-1)
Noticing Y; E [-4,4]. Applying Lemma in (Foster and Rakhlin, 2020), we get with probability at least 1 - 8", we bound the deviation term above as:
6. 0. f) L f f) (Colo, 0, f)
D VIV 1)
log
16 16log
n²
3n
32
E E| -
log
log 2
87
n²
3n
Further, consider finite point-wise cover of the function class G =- {g(ss a) olss a 0 o $ ||0||m S 1}. Note that, with cover W of W {1101|> S 1] at scale y, have for all (s, a) and ø E 4, there exists E W. 1(,(s a),8 - 0) S y, and we have [W] = (2) d
Let F be
y-covering set of F. For any f E F, there exists f F such that I| f|loo I 7. Then, applying union bound over elements in 1 W x F. with probability 1 | W| [|0', for all 0 W. F. we have:
Cp( C,(0".07 .). (Colo, f) L
< C,(0,0,f) - L,(0", .0
(Co(o, f, - Co 07 f) + 167
32 Ei_ E| log 2
16 log & 3n
167
n
16 2 8
2 16 16 8
B|
167
2n
3n
1
16log g
2 16 8 32%
E|Y;|F,-111
2n
3n
i=1
32 log 5
2 2 (Colo.0.f) - (.(0".07..)) +
+ 32y
n
1
64 log &
2 (Cp(0,0,5) - Cp((s" "'.""00;]10 f)) +
(setting 7 1/n)
n
where Y. (o(s), TO ) ((s) a.)TT 10 F(s)) Finally, setting 8
/ (11) get log 3/2 < log 1 This completes the proof.
Lemma C.5 (Deviation Bounds for Alg. 3). Let e' 128 2(tm)d (01-1
If Alg. 3 is called
with dataset D of size n, then with probability at least 1 8. for forany E F [0, 1]s, we have
Ep ( 1500000(ss.0
27 < (3)
2Ad
Proof. We begin by using the result in Lemma C.4 such that, with probability at least 8, for all |0]|,0 11, d. t and f E F, we have
[[ f. Lo(o".07 .7,, Lo(e, f) - Lo(ø", C0 f.l < cc(0. 0. - (0(00,7:11 + 1
33

---

Published as a conference paper at ICLR 2023
Thus, with probability at least - å we have:
Bp (5(s.a) a 0, o (s, (x;)
-c f) f) , f.
(since (s.PP((sa) [f(s)) 60 a) 07)
22 Co f) LD(00 .0, +
(Lemma C.4, and 110,11=0 S
according the proof in Lemma C.1)
52 (r (x 13 - 110 +
n
2Ad Se' +
(by the optimality of J. O, under (x,
which means the inequality in the lemma statement holds. Here, we use |10}10 d.
Lemma C.6. When p(n) is computed using Alg, and the Markov games is a block Markov game, we
x = = (llog NH
d log
HNHML
((n) =
68
8
n2
then & holds with probability at least 1 - 8.
Proof. Combining Lemma C.5 and Lemma C.3, we have that
max Ep [) JEF,
- d'(s,a) <e' 2\d <((n) ((())= = d
log
4LL
65
n
which shows & holds with high probability. Combining this result with Lemma E.1, we have proved Lemma C.6.
C.3 STATISTICAL GUARANTEES
To ensure the algorithm is well-defined, first prove the following lemma which implies the optimistic Q-value estimators always belong to the function class Fr.-
Lemma C.7. When (n) < L, have Q Fr. vh [H] [M],
Proof. Because ((n) is upper bounded by H, by induction one can easily get V(n) Then according the result of Lemma C.I, we know (f(") of h+1, S 2H² |00| S 2H2 We conclude Q Fr.
(s.a))
as. with
We will show later that our choice of (r) and L always satisfies the condition (n) < L. Lemma C.8. We have
For NE and CCE,
2i..) (s) < (D.go ) (s) + 28:
(n))
max Whes
(w)
* For CE,
max T Wh,,EOa.
(.11)) (8) S
(1))
(ID (m) ((1) (s) + 28.
34

---

Published as a conference paper at ICLR 2023
Proof. We only prove the case of NE and CCE, the of CE can be proved similarly. Let Q be the nearest neighbour of Qha in Wa. we have
max [D Kh.i.Th,
(1)
(s) S max
Thaihh. 2
(s) +
D
(m) (n)
(s) +
(Definition of =
(s) 25,
which has finished the proof.
Lemma C.9 (One-step back inequality for the learned model), Suppose the event & holds. Consider h=1 that satisfies 9h A R,, s.t. 1 llee S B. For a given policy n,
a set of functions {gh }H
suppose (a) Len (na(=aa)= E Fi, then we have
(s.a) MN)
[on(s,a)]
AB (( (n)
jof a)l,
h=1
E( p(
min | a)
NAZE (saa) (o,( + Ba + mAZ B
h
x-1 (n)
Recall 2 Mn,p(" (n) n.ph, .600 = niEE (s.a)~p)
(s) (s, Ala.
Proof. For step h 1, have
E ((s.a)adamn, p(n),, [g, a)] Baadd (91
di (s) (aas))
(oraa) (m) lof a'))
max (v,a)
Pi (s,
(m)
di (s) (als)
max (e.a)
(s) (s) (0) lof a')l
ALE (..a)~p/") (of a)).
For step h = =,2 H 1, we observe the following one-step-back decomposition:
B(ssa)dd ((,),
[gn (s)
a
= (8, (8.a)=d (.
on p(n) p(m) (ama)) [gh as)
p
(n) (3) / Σ
(x)
E -B(,,a)-d p()))
5 aEA
/ Σ ( B }
(10 0h (3, a)
-E(3,))-d a-
min
aEA
| Σ
<B(za)= (-
min
(((m) (3, a)
mn (n) (01)
aea
(n) (()
where we use the fact that gn is bounded by B. Then.
V Σ (f aEd
-1 11-1
35

---

Published as a conference paper at ICLR 2023
Th - (e) (( ( ( a (s, a)7 + +a12)
(1 aEA
())aaaooaaalllllleeee... a)ds
aEd
(15Σ 262
7
SnB
(2
(5, (1
+ B²Ad
aEd
Dped TA (a(a)))a((3,a)
& B and by Lemma C.1
[| "0 (
s v for a [0, 11.)
=n (5.0)~ph-) (n)
E
+ B3
SnA'B (2.0)-//1) (n)
[ (B (1 (sn(s
B² Ad
(Importance sampling)
(En-Pi (1.0) (s, 27
SnA' (3.0)-p(1)) (n)
Bd nA?
(Assumption ga)
SnA"B (3.0) (m) (8. (8.6), (o((s + B² Ad nAZg(a))
(Jensen)
SnA'E (1))) (s. a)] B² + mm)
(Definition of Ph.
Combing the above results together, we get
(( p,00,
[gh (8, a)]
1
<B(g,)) ((0 a-1
min 0 (3, a)
Σ
miph (n) (mm)
aEd
(n) 1
min
(8,
a)
V /nA²B
1o a)) + B (x.a)~p())
mi
which has finished the proof.
The following lemma is exact copy Lemma B.4, and here we state it again just for completeness. Lemma C.10 (One-step back inequality for the true model). Consider of functions {gh h= that satisfies In E x A + RR,,, s.f. [|gh||oo S. B. Then for any given policy n, we have
B(s,a)>dz., a (9n(s,
AB (s.a)~of))) (n) (of(3, a)}, h 1=1
B(g.a)md
110 (5, ,)
|nAA (o)(s, + B2Xd, h 2
(n) 1
Recall Σ (6) = =nE (..a)~+)))
(n) (s, a) + Ala-
n,7h 46
Lemma C.11 (Optimism for NE and CCE). Consider an episode n [N] and set (n)
@ H (nAC((()) dx).
When the event & holds and the policy ne (n) computed by solving NE or
CCE, we have
f,((1)
(s) -U; (s) -H Aç(m) 2HE, Vn [N], [M].
Proof. Denote (n)) (-|s) = arg max,
DD po ttar(") )
(s) and let a(()) = plo x Th-- Let
(n)
((0) (s. a)
1 H
p(x) Pi) -
(s, note that by definition, we have 1 1
# h+1. (s) is
h+1,1
36

---

Published as a conference paper at ICLR 2023
bounded by 1, and
1,m (m) H h+1, =B =B)
(0+1,(0,0) a)
Ph virg? (0)
(8,
(m))
+
H
H
Th+1, a)
1
v (s.0a) E Fs.
max E H4+
be (s)
H
+
H
Ph+ Ph+i
where the result of Lemma C.I and get H ( (P
t-ta 1+2,
(s, a) is linear function in t
and the 2-norm of the weight is upper bounded by vd. Then according to the event e, we have
E ((.a)=p!"" (n)) (11 sc(m,
(11 (()), An [N], he E [H]
E
((aa))a(
(
(1on(s, a))(s,))lı
(sio2a)
-
Vn E [N], [H], on E t
mich
(2)
A direct conclusion of the event & is we can find an absolute constant such that
8 (s, a) min
a (n)
((m) 9h (5,
(xin))
-1, -
kio(())
min
(n) 10 ($. a)
m(m)
H
Vn E [N], E [H].
(a) (())
Next, we prove by induction that
(s) - yyta" (m) (8)
E Srdd p(m),,
E (a
(o0))) (s) HH (r.xx((s,))) 2(H - h 11),
vh e [M]. (16)
First, notice that Wh E [.]].
V [i) (s)
(( (m)
D (D (n)) (s)
x 2h.3
(Deco tial?
E
(n)
(s)
=E
snde(n)
(s)
p(a))a
p
> sngginn snndtt) p(
(Decu 2111 (8)
Degn Qha
Qhis
(n)
(8)
25
d (s, a) - 2
taa (s,
(a.a)matan) p(a),a
2E,
where the inequality uses the result of Lemma C.8. Now we are ready to prove equation 16,
When h = H, we have
Vin - (i (s)
(H, (s, a) - Q1it"" (s,ai) -2
E smat(()) p(1),
E
(s.a) (s.a)~atth) ma(())
p00., x (s.a))
((m) (3. (s. 2
p(N) (s, (d)
( (s, - -H -H ((n) (| (s)
E
2E.
p(N).R
Suppose the statement is true for h + 1, then for step h, we have
Viin) hh (s)
( (n) h. (s)
(o) p(n))n
37

---

Published as a conference paper at ICLR 2023
(r) Q (s, a) - - (s,a) -
pin),b &
((m) (s, + (p ht1.1) (8, - PPi
( (9.a) -28
=R (s.a)
hot1,
p(n) d
5/m) (s. + ((()) (Titfis - vitril )) (s,
((D//)) - P/) vita??
(s, (8, - -2
(s,a) (d ve)(m)
p
((m) (s, (1/!0) - Pi) vilti (s,a)
(n())
(l - v
=R (s. p(n),
+ R
snattin)
h+1, (s) 22
pin)), (101
((0)) (s, -H5h (s, a)) + E
Vin) [ - 1 (6)
2F
(s,a)-dd vdddt))
smatiin
-2
p(n),
p(m),al1
H
[B/r (s, a) (1)
(s, a)] - 2((H h 1)5,
(a.a)mat(n)
p(n),a' a
N/mh
where the last row uses the induction assumption.
Therefore, we have proved equation 16. We then apply h 1 to equation 16, and get
Vir2 (s) vitar (m)
Egndi
(s)
Vin (5) - Vi (m) (8)
=E ande(e)) p(N),1
((()) (s, 11 (s, 2HÉ
E (a.)) pin),a
1=1
(3(m) (8, (8,00)
H Σ (s.a) pin)
[1tt (s,aa) 2HE
p
For the second term, since #.2 p(()) v. t.al? is linear in 0/x)) and +P h+1, is linear in o% and according to the result of Lemma C.I, the 2-norm of their weights are both upper bounded by vd. Therefore, we have Ea-U(A)
fh (,, a) E Finh By Lemma C.9, we have for h 1,
[1( (s.00) sV
(s,))) S VA(w).
AR (ara)~a())
(s,a)adat)) p(m),1
And wh 2 2, we have
E (c.a)~at(m) (
(3)
}
SR (8.0))=d(()) pin),a-1
min
[mm] ph-1 (5, a)
V |nA2R (aaa)=pt ((m) (s.aa) 27
/
+dd dd + m
+
minh 1
VnA2ç(m) + dA, }
SR (aa))aa())) p-1
min
(()] ph- (3, à)
aip ((m)
Note that we here use f (s,a) a)
< 1. E
((.))~
(m))
[1 (s, al (s.)))
27
2 ((x) and
E ((aa)~of(0) (119)) )
< <(())) Then according to our choice of (m)), we get
(n)
(n)
[1 (s, a)]
(n)
E. (s.a))af()) p(a),a
$ SE (((aa)mat()) (()) p(m)
min
0 h
(3, à
H
38

---

Published as a conference paper at ICLR 2023
Combining all things together,
1, (n)
(s)
V/, -mm
1/
=
=Bouds
(s)
11
11
E
(s.a)
3(m) B(m) (8,
11
E8
(3.0)
[s, a)
(8,
211
pin)a
pin
1=1
h=1
H-1
8(m) (s, - min
caal [1
(1)) (3, a
H
H V Aç 2HE
(3
hm
p(n),
mikk
(n) (m)))())) (m)
HV Aç 2HE,
which proves the inequality.
Lemma C.12 (Optimism for CE). Consider an episode n E [N] and a
@ H (HVnAR( d
When the event & holds, have
nd
(s)
max of WEi;
of (s) - Actm) - 2HE, Vn E [N],2 [M].
Proof. Denote Whi arg max Elhi. (Dusorri)) maxwEn; Q235 (m)
(n)
(s) and let nx Wh.
Th
(n) Let
((m) (s. #
(wwz(") (P(()) Pht max h+1,1
(s, a), note that by definition, we have
i max Vi (s) is bounded by 1, and
1
max V4lli H WEn,
1
(s)=
max Wh 10
E
(h+1,((,,)
1
Ph max (wor(()
WED; h42,4
(0,0)) E Fa
H
H
where we use the result of Lemma C.I and get (Pi+1 maxwen,
Vioor()) (n)
(s, a) linear function
h+2,4
in of and the 2-norm of the weight is upper bounded by vd. Then according to the event E, we have
E ( [1 (s.))) s s((m),
Vn E [N], E [H] (s))()).))) S (()),
E ((a))p!"))
I1o% (0)l (s(o).) + (10n(s, a))s
Vn E [M], E [H) e dn.
A direct conclusion of the event E is can find an absolute constant such that
((20 (s, a) min
(n)
3(m) Ph
(5, a)
(n())
-1,
h,
min
(n) | (3, a))
H.
Vn [N], [M].
(n) ((m)
miph
Next, we prove by induction that
smng pln),
(n) hid
(8)
max Vwon (n)
(s)
well
H
(3()) PR
(s, (s) - H1 (s," as. -((H 22H - vh e [H]. (17)
E (a
p(n),ar
Wi=k
First, notice that Vh E [H]].
snggstnn p
Th. (s) max ((won()) (n)
(s)
=E
(I. )h.1) (s) ((Dgo)
max Q (wo
(5)
WEn;
p(n),
west
39

---

Published as a conference paper at ICLR 2023
E soudan)
( ( (m1) (8)
(D)-(Dacs
max Quoor(n)
(5) 2
wesh
R (8,
=R (xa)))etr p(o))a
max WERt
(8, - 28.
where the inequality uses the result of Lemma C.8. Now we are ready to prove equation 17,
When h = H, we have
E
Vi,(s))
Vi, WEst
max Viwot( (N)
(s)
E
(s.a))dd))))
max QuA
(s, a)
p(0),
p(n),
WER;
-E (0.0)
3/(m (s, [s)
p(n),
((m)) (s, a) -HSH -15 (s, a) - 25.
> E (s.a) p(n),
Suppose the statement is true for h + 1, then for step h, we have
biln) hid (s) max Vwor (n)
sndt(a) p(a),
WEn,
>F
(s)a)ma (s.a) pin) pin),a &
T (s, a) west
max QiA
(s,a) - -25
(0)
=I
((m) (s) + (p h+111) (8, a))
max
Vitt1, (s, -2
p(n), (at))
(s,a) (d
wElh
=B
@(m) (s, + ((()) (Vitpl.:
max WeR,
htli
)) (s,aa-
-(P).)
-Pr)
max wEl:
h+l.
(s, (s.a)
p(
2
3(m) (s,a)
((P)))
((()) - Phi
max w (m) (s,a)
-E (s.a)
/+1,1
p(n),)
wEn,
((n) vi7))((s) max west
+ E3 (mdt(n)
Vit1,i
(s)
2
pin),
(34m) (s) -H (m) (s. a))
(n) (o
max (wor(n)
>B (s
+ EE
snnd(()
h+l, (8) 25
p(u),s
pin),at1
well
H
(s. a) -1)
H (())
-((H - -h+ 1)E,
p(n)aa'
h/=h
where the last row uses the induction assumption.
Therefore, we have proved equation 17, We then apply h = 1 to equation 17, and get
V (n) 1 (s) max Vi
(") (n)
Eg
(8)
welt;
=E snn)(())
1. (s) max (woo(()) WEll
(s)
p(a),1
(g()) (s,a) -HS (1) (s, 2H
p(i),
k=1
(3( (s, a))
[f(h] (s, [s as) 2Hé
(n) ((.a))d)()))
H
(s ( p(n)
p
For the second term, since 1 ((n) is linear in oi and according to the result of Lemma C. the 2-norm of their weights are both upper
max Vwon (mn) 1,t is linear in (6m") and 1 Pt. maxwen, (wor(() (n)
40

---

Published as a conference paper at ICLR 2023
bounded by vd. Therefore, we have Ea-U(A)) [1 E Fi... By Lemma C.9, we have for
h=1,
[1 (s.
s (a(am)))) (1*"(o)a))) (A((m))
(s
Ma))
And wh 2, we have
fr (s.
E
(s.a) (m))
p(m),
(s. / da + mAP + }
SE
(3.))ratti)) p(N)
min
9h-1 (3. a)
2(m]
|AAEE (s:a))pph)
minh 2
V VnA2ç(1) + +dd,1 ||
SB BB( (s.a)matto)) ( a-
min
ph- (3, à)
1--
Note that
here f/ (s, S
E (s.a)=ph (1)
(1f aa)
((*) and
E (((a)))f/))) (s)))) (())) Then according to choice of a (m), get
(n)
(n)
E (I,a)aat(a) pln),
(s, (s, a1]
s F. (()a))artin)..
min
ca
p
(m)
(5, à
pim),a-1
H
Combining all things together, (no
(n) max of WRB
Egands
Vin)
(s)
max Vi (woon()) (s)
WER;
H
H
E
(s, -
E
(s. - 2H5
(s.0) p(
(s.0)
p(n),
h=l
H
2
E
P ((1 min (a)
2(m)
(3, ā)
.H
H v Açtn) - 2HE
h=1
(5.a)
p(o)
5--1
minh
(w) ((())
H /AAC( 2HE
which proves the inequality.
Lemma C.13 (pessimism). Consider an episode ri E [N] and set a( =0 = + d
When the event & holds, we have
(s) Us (()) (s) < HV Ac
Vn E [N], E [M].
Proof. Let 7(m) (s, # (stt Ph Var(nn (s, a), note that by definition, have I (in(n)
H Vittt,(s)) (3) is bounded by 1, and
(ng V =E (*)
Th+1, a)
1
Pii Vatzi (s, a) E F2.
+
H
H
H
where we the result of Lemma C.1 and get и
1 (Pt vit2.s (s, a) is linear function in d
and the 2-norm of the weight is upper bounded by Vd. Then according to the event E, we have
(11 s <(()),
(11 a))) < c(()) e (H]
E (((a))=/!"'
((a))~a()))
41

---

Published as a conference paper at ICLR 2023
(Ion(es, (Ien(s,,))l
ll (s, a)ll (st (322))
a)
vn
[M, E (H) on E Ph-
mohk
direct conclusion of the event & is we can find an absolute constant c, such that
8/ (8, a)
min
(n)
Oh
((m) (),a)
-,, H
min
(n (m)
| (3,
a)
H.
Vn E 1 E [H].
(1)
Again, we prove the following incquality by induction:
H
E
eodda()) (n) p(n),
[v/ (s) - Vinl (s)
S
Σ W==h
E
(e)))
8(m)) [- (s. a) + H (s,
vh E [M]
pin),
(18)
When h = H, we have
E
(n)
p(m),,1
[n(r
VH
(s) vs)
=E (s.a)
p(n),1
(2()) (s,a) a) - -hh (n) (s, (s)
H1
1Bgm) (s, a)]
= (sa))ario))
p(0),,
300 (8, a) + HS (s.
(s.))aati))
(n)
pln)
Suppose the statement is true for h + 1, then for step h, we have
(s) - VA (s)
(n)
snate(a) A(m),a
(s, a)
o at
(saa)da(()) p(n))
(s, a) (p.")itaa (s, - (P
((00)-((p)))))) (itttt (s, (s.
(s.a) (n)
p(n),
1(0 (s,a) a) + (A (V - vatt.e)) (s) + ((P - -P;) vatu.:) (s, ai)
E
(s.a))d (n)
p(n) A
360m) (s, a) + ((P(m) - -Px) V (8.0) + Baanla)
[[ (Kritt - voti.) (8)
(s.0) 60)
pin),a &
pin) h+1
pin)
(5 a) + Hs ai] + E
(v(n)
b Vitt1.) (8)
(n)
(s.a) (n) p(n)
p41)
H
[-8 (s. H (s.a)
E
(n)
p(
M=h
where the last row uses the induction assumption.
The remaining steps are exactly the same as the proof in Lemma C.11 or Lemma C.12, we may prove
min (m) (s, $ VAcim),
E
(sa))ar(a)) (n) p(m),1
and
(1)
E. ((aa)arraa)
[ a)]
< E (8)))
min
0/
(n)
(5, a)
1
Vh 2 2.
H
(n) mip
(n)
42

---

Published as a conference paper at ICLR 2023
Combining all things together, get
(n)
1/
-Bendh
Li (s)
V1, (s)
H
18
[- (/ a) + (s. a)
(s.aa
(5, (s.a)rdaat
Min)
h=1
E (s.a)rddo
3(m) (s, min ca!")) (5mh (5,
.H
+ H V Aç(n)
p(r)),
x-1 minh
h=
<H AA(m),
which has finished the proof.
Lemma C.14. For the model-free algorithm, suppose N is large enough, when pick X
θ dlog NH + ((m) = = 6 log
HNLL L A(NHAMd), È 2HN and (!
26
θ H nA2gin) + dd
with probability 1 - 5, we have
Σ
A S H log
ANHAM
8
Proof. With our choice of x and ((m), according to Lemma C.6, we know & holds with probability 1- 8. Furthermore, with a proper choice of the absolute constants, have
dN HN + d2 log
NH +
a =
H d A log
5
8
dNHMA
50
HdA M log
8
00 (NHAMd) S L.
Let
(m)
(s, (() a)
=
27
(p(m)_pt) PP)
h+2,1 (((l11) (s,
We first
verify
2H
((n)
h+1,1
[(n]
E F4Ah By definition, we have
1
(v(m)
((n) E (m) (+)
((m) H 1 (s, + 2H2 Ph+z1 (Tiit -V
(n) - (s, a)
2H
/+11i
Kht1s)
(e)
The first term is equal to म min
( (s) T)T (5(())
3/mml (s, a), H which is exactly
the same as that the definition of F4,h (note that we use the property (a)) L, Vn E [W]. For the second term, note that have 0 S 217
(V (w) - =!! 1, vh. Therefore, by Lemma C.I. 2H Pitz (Vi)) h+2,5 Viri..) (s, a) is linear function in ob whose weight's 2-norm is upper bounded by Vd. Combing the above arguments, we conclude 1 (V vizt1.) e Fa,
According to the definition of the event &, have
(( s ((m), [l ()),s)))((ss))) (s )- -=== θ
[100(s,
)
E B
Vn E [N], Øn &r [H].
(m) mich
(19)
By definition, we have
A (n)
max ME[M]
[(n) (n)
(n)
2H
AC(1).
43

---

Published as a conference paper at ICLR 2023
For each fixed i [M], h E [H] and n E [NT, we have
(i v (s)
E (n) arvdyi
[
[ID Q (s) - [D (D Q (s)
[1 m
-(D
E suddp
E
(s.a))apph))
(m)
Qn 88 a)) -2 ( [s)
(m)
+ (p(m) (v / (oti.) )) [s
=B,
(8.0)) -d
2) + ((P)m) - PP) (Vittl: - k
(1
(s, a) + E V (s) - [s)
smaphits
2,3(m²) (s, a) + 2H² 1/m (s, a)
( (0)) v(() (s)
(m) SE. (s.a)~api))
+ E
pe.k
H
[B as) H² (s.aa)
B (ela))appin pa
N/=h
where the last inequality is calculated using induction. In particular,
H
E Sonde
(s) (0) 2 h=1
(s. (ap)) pe,
(s, a)
+2H
E
(s.a)app (n)
(s,
(s. a))
(a)
(20)
First, we calculate the first term (a) in Inequality equation 20. Following Lemma C.10 and noting the bonus 3(m) is O(H), we have
H
( (s, a)
1
(s.0)-dp())
(1)
pt
H
min a a (0000//000 ((m)
((m) (s, a)
(s (n)
(From equation 19)
E
(m) ((0)
H
(3, x>للx=
nA (a(n)) "E
(s,a)~p( (0)
(mm) (s, a)
+ HAdA
18 (8,
mith (: .0
x-1
A= 1
m.Ph
(alw)) 2
| (s, a)
+
Note that we use the fact that B H when applying Lemma D.3. In addition, we have
||
n. (a.a)mof (m)
mich (m) a(m)
=nTr
(Beeammp"") (ohn a) (s,.a))
nE
(ea)mp(()) (1) (((m) (s, (s, a))l" (s, _ + +aa)) -
<d.
Then,
Σ
E
(n) (a.))ate pa
(( (s) a)) < E (3
(n)
(3,
a)llx (m))
v ddlam))) + H2d VdA (a(m))//n.
mith .07
44

---

Published as a conference paper at ICLR 2023
Second, we caleulate the term (b) in inequality equation 23. Following Lemma D.3 and noting (
is upper-bounded by (i.e., Lemma D.3), we have (s,
2
H
1 (s.
E
H
(
(11 (s,
(f))
(s.a))dppo (1)
1 a)|bx with (m)
nAR (s.a)~ppp))
(n)
dd + v A (B(
#
13, a}
(n((m)) + +d++ A(((m)
(3.0)~dpa. (m)
h=1
(())
(8, (18,a)lls
VA((m,
11
aink 107
(s, S ((m), and in the last line,
where in the second inequality, we use (sa))pp)))
recall (nAg(") + dx (n1)/L /H. Then, by combining the above calculation of the term (a) and term (b) in inequality equation 23, we have:
(n) D
V (+) [s)
=B
pt.1
H-1
dA (a(m))²
VdA (a(l)))) + H2dx+
$
E (3.0)-aph))
n
h=1
H-1
(x))
2
| a) minh"" ,0h
+ AA(())
(3.0))
H
hml
Taking maximum over i on both sides and use the definition of A (m), we get
A (n)
(n) 1
(n)
2H Aç(m)
max iE[M]
2 dA (a)
E (2.0))d) (2)
(1,
VdA (a(a)))) H2dd
n
h=1
H-1
a (m)
1107 a)lه
2
+ Açin)
(3.a)~ap(()
(n)
n.th 10
Hereafter, we take the dominating term out. Note that
N
(3, a5)
S
E (3,0) (d
(3, T
of a)
um .oz
n=1
(CS inequality)
N
S
N leg
Σ
E
B
log dee((Aa))
(Lemma E.2)
N dA
dN log
1+
(Potential function bound, Lemma E.3 noting [1 (8, a)l12 S for any as))
Finally,
N
(Javios (1+ M Vdd HAdE+ H22 Σ
N
dA (a(m))
Σ #=1
(n) SH
45

---

Published as a conference paper at ICLR 2023
dN d log (1+
N
NV aa()
+ H
+ Σ AA(mm) n=1
+ 2HNE
H
dA
<12 NAlog
1+ ((v))
N dA
(Some algebra. We take the dominating term out. Note that ( is increasing n))
A log
dNHAM
This concludes the proof.
Proof of Theorem 4.2
Proof. For any fixed episode and agent i, by Lemma C.11, Lemma C.12 and Lemma C.13, we
have
t (m) 0
(n)) 2;
or max worl)))
S v(-)
2i (n)
+2 Açt") 2HE A + 2HE.
WeR,
Taking maximum over i on both sides, have
( (n)
(1))
{or max (E[M]
max U/ g (1)
2.7 (m) })
- A +HE.. (21)
max
[E[M]
WEn,
From Lemma C.14, with probability 8, we can ensure
dNHAM
(A(m) (m) 2HE S H log
Therefore, according to Lemma E.4, when pick N to be
H d
A
HdAM L
0
log"
g2
8z
we have
N Σ
(A
+ 2HE) S e.
N
n=1
On the other hand, from equation 21, we have
max
f
{
max sE(M]
max U WEB:
uf
MM[M]
(n))
max (oo)
max
U;
max (E[M]
MM[M]
wED;
<A(n)) 2HE
min
A (n) + 2HE
Σ (A +2H18 S
RE
which has finished the proof.
D ANALYSIS OF THE FACTORED MARKOV GAMES
D.1 HIGH PROBABILITY EVENTS
Define the set & (s, a) := Øjez (s[,( az)lon. E 2b Let 4 maxi,y |Ph
and | = maxi,; /1. Clearly, we have |bb < ( Define the following event
& : Vn E [N], E [H] E [M]PE (p/m) PP }
(n) (n)
E, [| h, (-1s at) - (1,,(1)(22), a.) 11/0 ((())
46

---

Published as a conference paper at ICLR 2023
8 vn E [N], & (M) E tnas [ a)ll (smmo..)) ) +
mich Bon
: =
The following lemma shows that the event & holds with high probability with proper choices the parameters.
Lemma D.1. When ((()) is computed using Alg. 2, if we sea
== (Ld' Ldd log 8
N ) -(m)==
M HNM
=
log
6
then & holds with probability at least
The proof of Lemma D.I is follows a similar procedure that of Lemma B.2, with minor changes on the notations as well as some modifications on the union bound.
D.2 STATISTICAL GUARANTEES
Lemma D.2 (One-step back inequality for the learned model). Suppose the event & holds. Consider set of functions {gh h=1 that satisfies S[Zi] x A; + R_,, s.t. ll I B. For given policy have
(s/,,) a.)
AB (s.a)mof") 0f(s/2.)...)) h h=1
E (22.a) ((m)) N-11
min
3l T(n) hh- h0 (3, a)
nR
(na))p()) (n) [+]( a.)] + B + nB4g(n) B
h
x-1
m ((10)
where
((n) (s)
jEZ. h- (s|2,]))
((m)
and
Σ 2 ((0)
nF
(n) pha (s) a (s,
2
(s.a)rpp)))
Proof.
For step h = 1, we have
B(s.ai)ndboo, (8) Zc), a:)) =E a (m) (s|2,,, a:)]
(1:s)(((a(ss)
(a (1) [of(s'(Z)), a4)
(s,a:)
max
P (s. as)
(n))
di (s) (a:ls)
(1' (s at)
max (s.a;)
di (2) (a))
AE (s.0))~'p~)) laf (s[2.),
For h 2 2, we observe the following one-step-back decomposition: E(R,a a (s(z), a.)
-E (1,o) p(n)) p(n)
a ppr (1.0)) (s).),
-E - a
(o) (3 a,) (لاا Σ m.(aals)on(((2))). a.)ds
a. a.EA,
M /
-E( (00)) a-
min
T (5|Z,), a T w (m) _
((m)
Σ
(s/3,, )s, B
R.E.d
47

---

Published as a conference paper at ICLR 2023
}
< (f) p(
min
A Jf
Ph-1, (312,),,,) T [
1
Σ (s a.jds, B
Js f=1
|Ail a,Ed
-E(z,))dd a-
min
A f
II
(10) (8(2,). a5)
I (n(s(2)),.)ddsf22))
[As
s(1,]
JEZ;
aged;
=f a-1
min
A Jsiz
hh 1-11. (5 (6(2)), a,))
X
20 (
[A Σ gn(s(2r), as)ss Z,), B a.ed,
SEZ,
2n (d)))))) }
-E( ((0) a--
min
A f s(2,]
Pn 11,1,, a
10 m (())
Σ
MA
,EZ,
a,ed;
A 1 Ph-1, (3, a)
<E pln),n
min
W 1 (85) (n( a.)dss
m.th
(n) (n)
s(2,)
Ail
a.EA:
JEZ
(n) ((m)
h-1.1
.B
Then,
Veran Ail a:Ed
2 ا (i(ss
JEZ,
(n) (10)
(Lore)
27
<nB (s,0)-pp1))))) (1)
II
(1 (1,)
31 on (5, gn (s(2,),,,
+ 132 Adh
Ai
a.EAjEZ,
( | La 9n (s(2,,)) az)
s B and
(.)
|| S Vvd)
27 (B len (s (s(Zz), ai))
=n (1
(n)
B2dd
SnB InBB3,aanplo (3/0)/p11))
(Bowph (3.0)) Ign (5 Lon (s|2.),
27
+ B²Xdd dd + nB2g(m))
(Event 8)
<nE (s,a),p)))))) 13 (s(2)), ai) + B² Ad' + Bn
(Jensen)
=nB (..a)) (s a.)] + xd + (n)
(Definition of =(n),
Combing the above results together, get E B00,
Ion (s( a.)]
min
1 (m) h
(5, a)
Σ
(n) (03) 0n(olZ))...dds222
As
(n) (m)
as
a.GA
Jez
h 1 4 1.
1 1-1
BBB
<E(a,o) p
min
(5.
nE VIB (naa)> (n)
[o](s( [Z., a;)) + B²Ad B2n B
mof
which has finished the proof.
Lemma D.3 (One-step back incquality for the true model). Consider a set of functions {gh, H h= that satisfies Gh S[Z.] X A, + R4, s.t. Ilgnlls B. Then for any policy n, we have
Els.a.)d Ion (s [2], a:)]
48

---

Published as a conference paper at ICLR 2023
V İE (aa))pp))))) (nn)
[s]]] a:)l; h h=1,
AlE Al
1 (3, a) 0)
V nilB (s.a)pph (m) (s]ii, a:)l + B²Adt, h 2.
nith 1
where (s,a)
JE JZ (s|2,], a,).
and 2 2n 3h.
n. (1a))()))) (2) (hhl(s,)) a) (s, a)T] + 21
Proof.
For step h 1, we have
B(s.a))d3., (s1,) a,)l =B (6) (s1(s a;)l
d1 (S)TT((()13))) (s]
(or a(mpp (n) (s,()' af))
max (s,0:)
Pi (s, a.)
(1)
(
(s.0:) di (i (8) U (a:) (s' a()ppp (n) ( [()]
max
AE (s
(s a:)]
For step h h= 2 - 1, we observe the following one-step- back decomposition:
E( (s a:)l
-B. an ( (T))) 19n (s/Ze). a:)]
T
X
o 1 (812y), (111)1))111
1
Σ
X jEZz
wx (.((,))))
(x(aa)s)gn((/(3),, a.)s
JEZi
a,EAi
<AB(s,a)
1
Σ
X jEZ
w (
) gn (,
Ali
JEZ
a.EA:
<AB(5,a)-df..n-
1 o (g))
JEZ
mich 18
Σ
1
wh (
gs(s/Zi), (a)s/Z)...)dds/22 [2,]
Are
O,EA,
JEZ,
Then.
1/
Σ 1
X
wh wh
(ss[2))...)ds/44
L,,,, Adil
5E
(1
27
SnB (m)))
(n))
8
Ail
wh-11
(15s) (1)))
Φh-1. (z(Z)),,) a.) (n(z)))), a.)ds(Zi]
B² Xd
jEZ
JEZ,
(Use the assumption
Eaaed 9h [s[2,), a:)
S and - s vd.)
=nB (1.0)-((1) (n)
19n (s|2z)) a:)1) 27 )}
+ B² Ad
SnB (2.0)-(()) (n) (1,0), (U(AA)
(s(2,], + B² Ad
(Jensen)
49

---

Published as a conference paper at ICLR 2023
SnB (..:)) (m) (s(i),)), a.)
Ad",
(Definition of pb
which has finished the proof.
Lemma D.4 (One-step back inequality for the true model). Consider a set of functions 3 that
satisfies Ih S(U)E, x AlZ.] + R, s.t. I1 B. Then for any policy have
E (ss .. 21
A A'E (sa))mp
(f( 2, al aZ21),, h= 1,
À B'( [
a)
nF (s.a)>ph)))
[sh(s(U)e2, a/2,)) + Ba
h h
(n)
where (8, =
OkEUSCz 23 2f 1. Zz), ax),
and
E Enggit) (n) Bi..
n. (s.a)~n) (w)
(s. + A U32
Proof. This Lemma can be proved using similar steps as those in the proof Lemma D.3, noting that in this case the dimension Φ7,; is at most 2
Lemma D.5 (Optimism for NE and CCH). Consider episode E [N] and set (n)
θ (HAvnn + d' When the event & holds and the policy T(1) is computed by solving NE or CCE, we have
(s) - -HMV Ac(m) Vn [N], [M]. (n) (s) Uz
Proof. Denote
(m) (-1s)
=
arg max,
D Pamgh Q (s) and let x
A x (n)
Let ((() (8, a) = p/ (118, - (1(.1s, a) a)1, and S/ (s(2), a;) =
pla) (+b((2)), a;) - (1,,(11/(2)) ai) Then according to the event E, we have
E ((aa)=p
(1 a.) 27 <((m), E
B(o.a))
(1112
(()) Vn [N], [H]ie [M]
[
-
(s...(s.a)ll>>>
Vn [M] E [H) ōn, & E [M].
((()) h.on,s
mith (o .n..
A direct conclusion of the event & is we can find an absolute constant such that
g (s, a)
Σ min
a (m)
(5,
a)
-1,
pin)
(n)((n)
M min
ca
(n)
7(m) Phúe (3,
a
H
Vn E [N], E (H].
(n)
(n)
mich
Next, similar to the proof in Lemma B.5, we may prove
Eawds (n() (s)
(n)
11,5
E
(z p
Σ
E (s.
min
p(n),,
h=1
For the second term, note
that we have the relation min (s, a),
ΣM min (s|Za), 1}. By Lemma D.2, we have for h - 1.
min { ( (s[Za) (s)Za).)).3] < AE (s.a)>p("")
(117 s <Vāg(n)
E (1.0)) ((6),
(n)
50

---

Published as a conference paper at ICLR 2023
And v/ 2 2, we have
E (sa)) p(N)
min
(( [ (s)),),
1}]
<B (z.))aatto)). p(n),a-1
min
A
(m) h
(3, a)
nl (s))))p!))) (1 (s|2a), an))
) / + d + n5(n),
}1
SB (8.)) p(n),a-1
min
i
(m) 1
(5, ②)
Vncim) + dhi, 1
x-1
mich
1
(11 a.)) )² S ((m) and
Note that we here use min (s[Z,), a;), 13 S 1, (.a))~))))))
(111))))))) < ((m), Then according to our choice of (n we get E (((a))mp(")
(n)
min { (s/2s) a.), S (3(0)
1 1, (5, a)
E ((ea))aatin)
min
p(m),a
p(o),
H
(m)
Combining all things together,
(1)
E Bands
(s)
Vi,
y. (s)
E3
3(()) (s,a)
11
Σ
E3
min 1 (s, a).
(3.0) (o(n)
(s.a)daa Min)
h=1
H-1
M Σ
(s.0)~d)(())
(s,
min (a
(m) |
(s. a)
.H
HM v Aç(m)
p(N),
j=1
E (n) [
HMV Aç(m),
which proves the inequality.
Lemma D.6 (Optimism for CE). Consider an episode n E [N] and set (x))
HAAnginn + d'x). When the event holds, we have
(()(() (s)
max of
QUo (m)
(s) 2 -HM Ac(m), Vn E [N],eE [M].
wEn;
(D) (Danon maxwen, Q Quar(n)) (s) and let m || (+1s,,)) Ph((ss,)) a))l and Sk (s|Z,), az)
Proof. Denote Whis
arg max Ela,
(n)
Let f(()) (s, a)
Wh,i Th
| (116[2)) as) - (-,,(1o[[z)) 7z), ai)]|
Then according to the event E, we have
(+12),,))))) <((m), B(aa)rpff (127(1122)))))) ((m)) Vn E E [M]
B B(eaa)pf(
[M]
(10on.(6s.
|
(
Vn E [N], E [H], Øn. E &n E [M].
(s(()) 'nosn.)
mith .nn..
(n)
A direct conclusion of the event & is we can find an absolute constant such that
M
a(*) (s, a) = min (m)
Σ
(3,
a)
Din -1 H.
51

---

Published as a conference paper at ICLR 2023
Zemin
(n)
hha
(n) (5,
a
Vn e E
(m)
Next, similar to the proof in Lemma B.6, we may prove
H
H
Bawds
Vi 1, (s)
WERt 1,3
max (won(()
(s)
Σ
E
(e)a)dat()) p(m),,
g0m (s,
H
Σ
E (e
( p(n),a
min { 1h (s, (s,,a,, 1].
h=1
h=1
Note that we can use exactly the same steps in the proof of Lemma D.5 to bound the second term. and we get for 1,
E
(daa) Man),
min
(s|z),, a.)), (11),, $ v Actw)
And wh 2.
ca(
E (a.))
min (s(z,,,
HI
(3,0) p(m)
b (5. I-
mi
Combining all things together,
(n)
max of op wel,
max ViOoT(") (n)
Eonds
(8)
WERt
11
H1
E
H1
Σ
E
[ii 1h (s, as) 1}]
(s,a)
(s,a)
p(n),h
p(m)
h=1
h=1
H-1
. ]
E (s.a)rdt(in
(s,
Σ j=1
min car(x)
(n) /n
(8, a)) x (m)
HM v Aç(n)
h=1
2 HM V Ac
which proves the inequality.
Lemma D.7 (pessimism). Consider an episode n E [N] and set (n) = =0 (HHAVHC( + t'
When the event & holds, we have
(8) - 2/ (1)) (s) < HMM W.HHHAACK Açtm), Vn E [N], [M].
Proof. Let (s, =
# (11s - (1 a)]1 and (>(2),) =
(18(2)a)) - (P,,(- a:)
Then according to the event E, we have
(117 5 s((m),
(112()))2))
/ ((m), Vn e e [H] e [M]
E ((ea)/p
E (((a))=ff""
())
Vn [N] E [H], on e i [M].
minhy (1)) .mn.s
A direct conclusion of the event E is we can find an absolute constant such that
M (x)
a(m) (s, a) = D min
|
(3,
a)/l
-1, H.
Dini m.
52

---

Published as a conference paper at ICLR 2023
M
Σ
min
3 (5,
a
H {
Vn V e [N], [H).
(m) 2
Next, similar to the proof in Lemma B.7, we may prove
H
sangeln) pin),b .b
[s)
Via
(s)
1// (s, a) H min { [Iw (s, a), 1)]
wh [M].
p
h/=h
(22)
and we get for h
[17 (s|Z,), (s) $ V Aç(w).
E
(0.a)
min
p(m),
And vh 2 2,
ca(")
E
(aa)map(o)
min
B (s,)) Ma)
1000 1 (3,
H
Finally, we get
(n)
(n)
Bands 11, (8)
Vi (s)
1-1 1
((m) (s, a)
M
min (aa 13 | (8, a
+ HM v Aç(n)
+
pin),
h=1
1=1
<HMV Aç(n),
which has finished the proof.
Lemma D.8. When the event & holds and (x)) = (HÂv (Hāvnç()) d(xx) satisfies (1)) S a2)
S (N), we have
MH AL, N N (1+ )) dA )aim.
A (n)
#=1
Jh f(m) (s,
p(() - - and (s|Zal a.)
Proof. Let
(1bs(a)), - P7,((1s[[s), an)
Then according to the event E, we have
E (((a)=(( (m) ( (1h
< <((m),
E ((aa))
(11)) ((1)) Vn e [N], e [M, E [M]
||
-1 -1= θ
(12m.(3.0))]
Vn E [1,, [H) on, & E [M].
((()) _
(m) minh .
By definition, we have
A (n) max
(n)
(n))
+ 2HM v Ac(m).
ic[M]
With similar steps as those in the proof of Lemma B.8 (note that V v (s) - (n)(s) (s) is upper bounded by 2H²M). we have
H <
H
1. (5) - (s)
(n)
[B(h) (s. a) +2H² D
E
(0.0) (n)
[f( (s
h=
(a)
(8)
(23)
53

---

Published as a conference paper at ICLR 2023
First, calculate the first term (a) in Inequality equation 23, Following Lemma D.4, we have
((m) (s, a)
(s,a)rdp
H M
a
o ( (s,
min
(s.a (.aa)app.
E mich hhh
1=1 1=
H-1 M
ALE
(5,
(3.a)/dp1))
x
h=1 ==
mith 1
n (a(x)) 2 (1 (n)
@ [ (s.
1lm)
H2d12 X
c (n)
2(0)
| (s, a)
E
(m)
(m)
Note that use the fact that B H when applying Lemma D.3. In addition, we have
| a)
n.E (s
mith slm
=nIr
((sa))o (n)
( (s, (s, as,
[ nE (nB (s.))))
1 (s, as) a) + Marz))"))
<d".
Then,
(s,
E
(s.a)~apfa) (n)
M
A (2()))
(02.((5,0)
Vaz di (ala))² + H2
8-1 (n) n.th
26,
AL (aln))²/ /n.
Second, we calculate the term (b) in inequality equation 23, Following Lemma D.3 and noting ((2) (s[Ze), a:) is upper-bounded by (i.e., B in Lemma D.3), have
(s,a)
E
(s.a) pe,a
(e)
M
H
E
(a.a)
(s|2)) an)
H-1
( (s/Za), + +d'
AE
(5) a)
nE
(s.a)>pp() (m)
(n) .g.
(110))
ÀE
54

---

Published as a conference paper at ICLR 2023
M H
AE
18, (8,
1 a)
Vng(n) + dd + Aç(n)
1-1
with this (1)
k=1
(m)
E (8,))_)p (x)
(5, a)
V Aç(m),
mith ,t
.0h.
[ ai) ) S ((m), and in the last line,
where in the second inequality, we use E ((a))~p")))
recall //n((n) d= S (n) /H. Then, by combining the above calculation of the term (a) and term (b) in inequality equation 23, we have:
12)
(n)
[.) -V (s)
B
snd pa
M
|
dl ÀL (n)))
À
V dl (alm))² + H2 X
(3.a)map
x-1
A=1
(m)) .8,
H
(x)
H
(3 a)
+ Aç(n)
(n) (s.a)aap())
pt
h=1
Taking maximum over i on both sides and use the definition of A (x)) we get
(m)
(n)) + 2HM Aç(n)
max iE[M
M H-1
A (a(m))
ALE (5.0)
(3
Vas de (aln))² + H2dd
5:-1 (n) with 3h
n
M H-1
(x(1
H
ΣΣ
E
(3.0))ap(m)
1 (5, a))l pech
V Aç(a)
H
1=1 h=1
nith AP
Hereafter, we take the dominating term out. Note that
| a))
E
(1.a))dp(a) pr,
N
E (aa))apl) p
o a5)
mith .hh (3.
(CS incquality)
n=1
N (log det
Al (lausee
Σ
E (n)
log det A1 a 1152, (11)),33))
(3 (3
(Lemma E.2)
sv g N Nlog 1+ dd
N)
(Potential function bound, Lemma E.3 noting (s[z,, a.)ll S for any (s, a).)
Similarly, have
E
11 a))l
d' log
1+
-
N
(s. (p.))
dA
nith ag
(1)
Finally,
N
(n)
SHM
(yar
(1 N
A V dh (a(N))2 + 12 A+
N
A (a(n)) 2
n=l
==1
55

---

Published as a conference paper at ICLR 2023
M)
NV aa
+ H2
dl Nlog
1+ dA
+ Σ
Açim)
H
n=1
N 1+
M2 AL
Noog
N log
a(M)
dA
(Some algebra. We take the dominating term out. Note that ( is increasing n))
This concludes the proof.
D.3 PROOF OF THE MAIN THEOREMS
Lemma D.9. For the model-based algorithm, when we pick X θ (T.L log NHA (+)
a
[HAVngin + d(>) and ((x) θ ( log
[ MHHM with probability 5, we have
MMHHN
Σ Am) (n) & M
A N log
Proof. The result of Lemma D.1 implies with our choice of x and ((,), the event & holds with probability least 1 5. In this case, we have
MMHNN
NHM +
a (m) θ HHÁ log
La22 log
(24)
8
which is constant unrelated with Therefore, using the result of Lemma D.8, we get
Σ (m) $ H2 M2
N
V N
N (1
a (N) S N2 (L+)) L log
MMHNN
dx
n=1
which has finished the proof.
Proof of Theorem 4.1
Proof. For any fixed episode and agent i, by Lemma D.5, Lemma D.6 and Lemma D.7, we have
( (nn)
max (m)
m(m))
2i + +2HM Aç()) < A (n)
wERl U
< 0.
Taking maximum over i on both sides, we have
max
1.m (m)
(n)
{ar or max xE(M]]
(1) WEn,
max
of
((1)
1)
< م (n)
(25)
vE[M]]
From Lemma B.8, with probability 6, we can ensure
(x) S H LiI A log
MMHNN
Therefore, according to Lemma E.4, when we pick N to be
L M H ((.+)) (2(++1)
HdALM M
log?
5E
we have
1
Σ
A
SE.
N
n=1
56

---

Published as a conference paper at ICLR 2023
On the other hand, from equation 25, we have
}
max QNOR WED:
max [d]
1
or max
dE|M
(n>)
(mn)
- -02600))
max M
Ui
or max
max U, wEll
<A(n (n")
min (m)
(n) Se
mE
M
N
which has finished the proof, noting our assumption that I= 0())
E AUXILIARY LEMMAS
Lemma E.1 (Concentration of the bonus term (Zanette et al. (2021), Lemma 39)), Set A(m) 2
Oddlog(nHH ( for any Define
n
(n) =nE. (aa))pp (d(s, a)d (s. + 1 S(m)
(lsh a
T aa)) + 1
With probability 1 - 8, we have
Vn E N+, vh [H]] VĀ Φ, cill((, a)m 10
S 1Io(s, (1)())
S c2llØ(s a)lbx
of
Lemma E.2 (Agarwal et al. (2020a), Lemma G.2). Consider the following process. For n Mn Mn-1 + Gn with Mo A and G, being a positive semidefinite matrix with eigenvalues upper bounded by 1. We have
I,..., N.
N
log deu(Mx) log 2
Σ
Lemma E.3 (Potential function lemma).
Suppose Tr(G,,) S B
NB²
log (NW) llg S dlog 1
dAu
Proof. Le, oa be the set of singular values of MN recalling Mx is positive semidefinite matrix. Then, by the AM-GM inequality,
log det (et())) log (a. s log d ā ((an/bo))
Since have E. TT(MN) dAo NB, the statement is concluded.
Lemma E.4. For parameters
A, B, such that A
A²B is larger than some absolute constant, when
pick N = log² A²B²
A²
0
A²
log²
AB 8
have
5t
log BN)= SE.
Proof. We have
A
log
ABB log²
2 A
log (BN)
N
log
4 ct
Note that
A
A
A
A
ABB
log
<
+ log
2
<
22
g
E
54
57

---

Published as a conference paper at ICLR 2023
where the right hand side is always true whenever
A²B g²
is larger than given constant. Therefore,
we get
A
(Bg( S 8.
F EXPERIMENT DETAILS
F.I DETAILED ENVIRONMENT SETUP
In this section introduce the details of the environment construction of the Block Markov games. For completeness we repeat certain details already introduced in the main text. We design our Block Markov game by first randomly generating tabular Markov game with horizon H, states, players each with 3 actions, and random reward matrix RA (0, 1)3x3*** and random transition matrix Ta (Sh, 4h) ((S++).. For the reward generalization, for each ass,,,s) entry in the reward matrix, we assign with random number sampled from uniform distribution from -1 For the probability matrix generation, for each conditional distribution T(-ss, a), we randomly sample 3 numbers from a uniform distribution from -1 and form the probability simplex by normalization. For the generation of rich observation (emission distribution), we follow the experiment design of (Misra et al., 2020): the dimension of the observation is 2 [og(H[[S|+1],, For an observation that emitted from state and time step h, we concatenate the one-hot vector of s and h, adding i.i.d. Gaussian noise N/O, 0.1) each entry, pend zero at the end if necessary, and finally multiply with Hadamard matrix. In our setting, we have variants with different horizons H.
F.2 IMPLEMENTATION DETAILS
For the implementation of GERL_MGE we break down the introduction into two parts: the implementation of Alg. 3 and the implementation of game solving algorithm with current features (line. 10 and line. 11 of Algorithm. 1). For the implementation of Algorithm. 3, we follow the same function approximation as (Zhang et al. (2022)) and adapt their open-sourced code at https: httpy/da /und briee. We include overview of the function class for completeness: we adopt a two layer neural network with tanh non-linearity as the function class as the discriminator class. For the decoder, we let (0() = softmax(A (A o), where E R|O|x x3 and we let Φ(o, a) = (0) Here denotes the one-hot encoding in the joint action space.
gi thub. com
Different from Zhang et al. (2022), we solve the optimization problem by directly solving the min- max-min problem instead of using iterative method. We show the implementation in Algorithm. 5. We first perform minibatch stochastic gradient descent aggressively on the discriminator selection step (line. 5, on å and f) and the feature selection step (line. 6, on Φ), where in each step we first compute the linear weight w and ú closed-formi and then perform gradient descent/ascend on the features and discriminators. Note that here the number of iteration T is very small.
For solving the Markov games, in addition to following Algorithm. to solve line. 10 (i.e., solving equation 2 or equation 3 or equation 4), we implement the NE/CCE solvers based the public repos- itory: https: : //gg thub. com/ quantttn um racle e /MRRS. Note that the essential difference lies in that (Xie et al., 2020) assumes that the algorithm has the access to the ground-truth feature but algorithm needs to utilize the different features we learn for each iteration. We also adopt the Deep RL baseline from the same public repository.
F.3 ZERO-SUM EXPERIMENT TRAINING CURVES
In this section we provide the training curves of GERL MG2 and Deep RL baseline in the zero-sum setting in Figure.
F.4 GENERAL-SSE SUM EXPERIMENT DETAILS
In this section we complete the remaining details for the general-sum experiment. We include the training curve in Fig. 2.
58

---

Published as a conference paper at ICLR 2023
Zero sum
Zero sum HB env3
Crock
Omie
now
0.4
0
-0.3
03
-0.4
Zero-sun encl
Zero-zum H10
1.0
5.
0.6
0.8
0.6
0.5
0.0
-02
-0.4
-08
DQM
20000 40000 10000
00000
100000
20000
40000
00000
80000
100000
43000 10000 00000 100000
in the zero-sum setting. We evaluate each method over random seeds and report the mean and standard deviation of the moving average of evaluation returns, wherein for each evaluation we perform 1000 runs. We use "Oracle" denote the ground truth NE values the Markov game. The x-axis denotes the number of episodes and the y-axis denotes the value of returns.
Figure 1: Training
Goneral
General emx
1.5
General Sum enva
175
Apmi
1.25
1.00
0.8
0.75
0.75
0.7
0.00
10000
20000
30002
10000
20020
20200
42000
100000
70000
300000
40000
Figure Training curve of GERL_MG2 in the general sum setting. this setting, the y-axis denotes exploitability instead of raw returns.
F.5
HYPERPARAMETERS
In this section, we include the hyperparameter for GERL MG2 in Table. 2, and the hyperparameter for DQN in Table, and Table.
Table 2: Hyperparameters for GGRL_MG2.
Value Considered
Final Value
Decoder ø learning rate
[le-2]
le-2
Discriminator learning rate
[le-}
le-2
Diseriminator f hidden layer size Replearn Iteration T
(128,256.512)
256
(10,20,30,50)
10
Decoder & number of gradient steps
[64,128,256)
256
Discriminator number of gradient steps
[64.128.256)
256
Decoder batch size Discriminator f batch size RepLeam regularization coefficient A
[128,256.512]
512
[128,256.512]
512
[0.01]
0.01
Decoder softmax temperature
(1,0.5.0.1)
LSVI bonus coefficient 3
(0.1.0.5,1)
0.1
LSVI regularization coefficient À
(1)
1
Warm up samples
(0,200)
0
59

---

Published as a conference paper at ICLR 2023
Algorithm 5 Model-free Representation Learning in Practice
1: Input: Dataset D, step h, regularization A, iterations T.
2: Denote least squares loss: Lx,D(0, 8, f) == Ep (o(s. f-())) + 1/10112
3: Initialize Φn 2, arbitrarily;
4: for t = 0, .,, T do
5: Discriminator selection: ft arg faF, [ming Lx, (dr, f) je Lx, Cx. f)l
6: Feature selection: Pt+1 arg min ΦE Σi= ming, (o, 8,, fi), t Øst1
7: end for
8: Return 3 where P is calculated from equation 1.
Table 3: Hyperparameters for DQN in short horizon environment.
Value considered
Final Value
Target update interval
{1000)
1000
cu
(1)
1
eN
(0.01)
0.01
decay frequency
(8000)
8000
Batch size
{8000)
8000
Optimizer
[Adam]
Adam
Learning Rate
{0.0001}
0.0001
Hidden layer
[[32,32,3]]
[32,32,32]
Self Self-play 5
{1.5)
1.5
Table Hyperparameters for DQN in long horizon environment.
Value considered
Final Value
Target update interval
(1000)
1000
6o
(1)
1
(0.01)
0.01
decay frequency
(8000)
8000
Batch size
{8000)
8000
Optimizer
[Adam]
Adam
Learning Rate
(0.0001]
0.0001
Hidden layer
([32,32,32]]
[32,32.32]
Self-pli play 5
{1.5,2)
2
60


Reviews:
[{"review_id": "k_KJ8y0w9_Y", "reviewer": "Reviewer_H4wD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the low raw rank General sum Markov games, and provides two algorithms, model based and model free for finding the Nash equilibrium. In the model based algorithm, we sample state-action-next state tuples from the environment, and we estimate the transition probability directly from these tuples. In the model-free setting, however, we first estimate the feature vectors, and then we estimate the transition probability from these feature vectors. After estimating the transition probability, the algorithm performs the planning step, which is  conducted with a UCB style approach. \nAt the end, the authors provide the sample complexity of their algorithm in both model based and model free settings. \nFurthermore, the authors argue that their sample complexity for general MDP settings can be exponentially bad in terms of the number of agents. Hence, the authors provide the sample complexity of their algorithm for the Low-Rank Factored Markov Game. At the end the authors provide experimental results for proof-of-concept.", "summary_of_the_review": "The paper is interesting and well written. It is comprehensive and studies a broad range of settings with providing tight sample complexity bounds for all of them. Beside some minor issues, I believe it is a good paper. ", "strength_and_weaknesses": "Strength: \n- The authors study a general setting of Markov games fir linear MDPs. The problem formulation is novel and interesting, and the sample complexities are tight. \n- paper is well-written and easy to follow.\nWeakness:\n- In order to run the algorithm 1 and 2, we need to assume access to optimization oracles for calculating max and min-max-min. I was wondering if the authors can comment on the hardness of access to these oracles. \n- The definition of Low-Rank Factored Markov Game is slightly strong. I believe according to this definition, you are assuming that only L number of agents around each agent us can affect an agent. \n- Although the sample complexity is improved under Low-Rank Factored Markov Game setting, but the authors still require to save a large vector of parameters, in the size exponential in the number of agents. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IQxIYUiqUfa", "reviewer": "Reviewer_oMoF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies multi-agent general-sum Markov games with nonlinear function approximation. They focus on low-rank Markov games whose transition matrix admits a hidden low-rank structure. The authors provide a model-based and a model-free approach to learning the Nash equilibrium under such a transition model. The proposed algorithm achieves a sample complexity of $poly(H, d, A, 1/\\epsilon)$. They further consider Markov Games with a factorized transition structure.  The authors present the empirical results to verify their theoretical results.", "summary_of_the_review": "See the section of Strength And Weaknesses.", "strength_and_weaknesses": "Strength:\n\n1. This paper provides novel theoretical results for representation learning in general-sum Markov games with a low-rank transition structure, which extends the previous single-agent MDP setting to the multi-agent general-sum Markov game setting. \n\n2. This paper presents a new result for low-rank representation learning in RL with a model-free learning algorithm, which is different from the existing model-based algorithm.\n\n2. This paper also provides an extension from the general transition case to the factored transition setting. \n\n4. The theoretical analysis is clear and this paper is well structured.\n\nWeaknesses:\n\n1. I feel that the proof of this paper largely depends on the recent work [Uehara et al., 2021]. Most of the proof can be directly modified from [Uehara et al., 2021] by setting the action a to $(a_1, a_2,...)$. To handle the proof with CCE, CE, and NE in the general sum game setting, one can also use the proof techniques in recent advances in general-sum Markov games. \n\n2. In Theorem 5.1, there is a $L^2$ in the exponential term, which does not appear in Theorem 4.1. In my understanding, this can be a problem in the upper bound. Can the authors provide a more detailed discussion on this? What is the major technical reason for obtaining this factor?\n\n3. The authors may need to further provide a detailed comparison between the results in Theorem 4.1 and Theorem 5.1, and show whether there are advantages of using the factored transition modeling.  ", "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": {}}, {"review_id": "Fj96iYMWcp", "reviewer": "Reviewer_xksf", "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": "", "summary_of_the_paper": "The paper studies representation learning for Markov games with low-rank structures. Under the low-rank assumption, the authors develop two representation learning methods to learn the underlying transitions: model-based and model-free representation learning and add the UCB bonus into the estimated Q-value functions for computing explorative policies. In theory, the authors show sample complexity PAC guarantees for two methods for obtaining near-optimal equilibria. Moreover, the authors study a special case of factored Markov games by showing a similar PAC guarantee while improving the exponential dependence on the number of players. Finally, the authors provide a series of experiments to compare the performance of the proposed method with DQN. ", "summary_of_the_review": "The paper studies a class of Markov games with low-rank structure and provides representation learning methods for learning equilibria with PAC guarantees. Although the setting is useful, many assumptions in algorithm design and analysis need to be further justified. The novelty in the analysis needs to be discussed in detail. The experiments only consider small-scale Markov games that are not very sufficient to demonstrate the effectiveness of the proposed methods.\n\n\n============================\n\nPOST-REBUTTAL. Thank you for your response. I have read other reviews. I am inclined to recommend acceptance. The score has been increased.", "strength_and_weaknesses": "Strengths\n\n- The studied setting considers a general nonlinear representation of transition dynamics of Markov games. This setting is interesting and useful since it is often the case in practice that the model features are unknown, which brings the approach of representation learning to Markov games.\n\n- Under some assumptions on the model and the planning oracle, the provided representation learning methods enjoy polynomial sample complexities for learning equilibria, although it has an exponential dependence on the number of players. In the case of low-rank factored Markov games, the proposed method enjoys a polynomial dependence on the number of players.  \n\nWeaknesses\n\n- The application of representation learning to Markov games is more straightforward under assumptions on the realizability of model class or feature mapping and access to policy planning oracles. These assumptions could be too strong to hold, for example, exact solutions from policy planning oracles and real games do not satisfy your realizability assumptions. \n\n- The established PAC bounds are sub-optimal in terms of state/action space sizes, especially when we specialize it to the tabular case. It is important to compare it with some model-based MARL algorithms in the literature. Recovering the optimal sample complexity in the tabular case should be a sanity check of the efficiency of the proposed methods.\n\n -  The proposed methods are not decentralized, which prevents them to work in many real-world games that prohibit information sharing, especially policies. \n\n- The provided computational experiments only consider small-scale Markov games, which are not very sufficient to demonstrate the scalability of proposed methods under different low-rank structures. \n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AZQjd7UkzU", "reviewer": "Reviewer_tHaH", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies general-sum Markov games where the probability transition admits a low-rank structure, and proposes algorithms that exploit the underlying structure via representation learning to efficiently learn the (approximate) equilibrium policy. Both model-based and model-free methods are provided and theoretically analyzed in a unified way. Quantitative regret bounds are provided for the general case and also the special case of factored Markov game, where for the latter case, the dependence on the number of players is shown to avoid the exponential scaling. Numerical experiments are also provided to show the advantage of the proposed approach over the DQN baseline.", "summary_of_the_review": "I think this paper studies an important setting of multi-agent general-sum Markov games and the results are solid. This is a good submission as a complete work with both theoretical analysis and numerical simulations. Some aspects of the writing can be improved as I've discussed above.\n\n---\nOther minor problems:\n\n- In the fourth line under Algorithm 3, what's the meaning of 'M induced'?\n- In the last line of Remark 5.1, 'up to'.", "strength_and_weaknesses": "Strength:\n\n- Overall this paper is well-written and easy to follow. \n- The authors have clearly explained the goal of this paper and their contributions. The difference between the problem setting in the current paper and those in the existing literature is properly discussed.\n- The description of the proposed algorithm is clear and easy to understand.\n- The theoretical analysis is solid, and numerical simulations are provided in complement to the theoretical results.\n\nWeaknesses:\n\n- This is mainly a theory paper, and in the main context, the authors should discuss more the technical challenges and novelties compared with the existing works. It seems not clear to me what are the difficulties caused by the more general setting considered in this paper. A high-level description of the proof idea in Section 4 would also be appreciated. It would also be helpful to compare the results in Theorem 4.1 and 4.2 with existing results for Markov games when restricting the setting to two-player.\n- Some notations should be clarified in Section 2. For example, the definition of the function classes for the features should be provided. In line 6 of Algorithm 1, I guess $d_{P^*,h}^{\\pi^{(n-1)}}$ means the induced distribution on the state space and $U(\\mathcal{A})$ is the uniform distribution on the action space. Please define these notations (or let me know if I've missed anything).\n- When describing the components of the main algorithms, please provide references if a certain approach has been proposed in some related work. \n- It is remarked that the proposed algorithm is oracle-efficient, but it is unclear to me how to implement certain steps in Algorithm 1 and what are the computational costs. For example, line 6 of Algorithm 1 seems to require a certain simulator of the environment, instead of executing the policy to get the trajectory of an episode. I'd like the authors to provide more discussion about what oracles are needed and the corresponding implementations, especially since it is claimed that the proposed algorithm is scalable.\n- The organization of the experiment section is a bit weird. It seems that the description of the three different environments should be grouped together. Also, it should be clarified what Environment 1, 2 and 3 refer to.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster