Sample-Efficient Multi-Agent RL: An Optimization Perspective
Authors: Nuoya Xiong
Zhihan Liu
Zhaoran Wang
Zhuoran Yang
Venue: ICLR 2024 poster (2024)
Keywords: multi-agent reinforcement learning
theory
general function approximation
general-sum Markov Games
Primary area: learning theory
TL;DR: This paper provide a unified algorithmic framework for general-sum Markov Games under general function approximation.

Abstract: We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under general function approximation. 
    In order to find the minimum assumption for sample-efficient learning, we introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. Using this measure, we propose the first unified algorithmic framework that ensures sample efficiency in learning Nash Equilibrium, Coarse Correlated Equilibrium, and Correlated Equilibrium for both model-based and model-free MARL problems with low MADC. We also show that our algorithm provides comparable sublinear regret to the existing works. Moreover, our algorithm combines an equilibrium-solving oracle with a single objective optimization subprocedure that solves for the regularized payoff of each deterministic joint policy, which avoids solving constrained optimization problems within data-dependent constraints (Jin et al. 2020; Wang et al. 2023) or executing sampling procedures with complex multi-objective optimization problems (Foster et al. 2023), thus being more amenable to empirical implementation.

Published as a conference paper at ICLR 2024
SAMPLE-EFIICIENT MULTI-AGENT RL: AN OPTI-
MIZATION PERSPECTIVE
Nuoya Xiong
Zhihan Liu"
III,, Tsinghua University
Northwestern University
xi xilonnny20mmall h...ssssssigsue edu.cn
Zhaoran Wang
Zhuoran Yang
Northwestern University
Yale University zhuoran, yangeyale.edu
chaoranwangggmaii. com
ABSTRACT
We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under general function approximation. In order find the minimum assumption for sample-efficient learning. we introduce novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. Using this measure, we propose the first unified algorithmic framework that ensures sample efficiency in learning Nash Equilibrium, Coarse Correlated Equilibrium, and Correlated Equilibrium for both model-based and model-free MARL problems with low MADC. We also show that our algorithm provides comparable sublinear regret to the existing works. Moreover, our algo- rithm only requires an equilibrium-solle ized supervised learning, and thus avoids solving constrained optimization prob- lems within data-dependent constraints (Jin et al., 2020a; Wang et al., 2023) or executing sampling procedures with complex multi-objective optimization prob- lems (Foster et al., 2023). Moreover, the model-free version of our algorithms is the first provably efficient model-free algorithm for learning Nash equilibrium of general-sum MGs.
oracle and an oracle that solves regular-
INTRODUCTION
Multi-agent reinforcement learning (MARL) has achieved remarkable empirical successes in solv- ing complicated games involving sequential and strategic decision-making across multiple agents (Vinyals al., 2019; Brown & Sandholm, 2018; Silver et al., 2016). These achievements have cat- alyzed many research efforts focusing on developing efficient MARL algorithms in theoretically principled manner. Specifically, multi-agent system typically modeled as general-sum Markov Game (MG) (Littman, 1994), with the primary aim of efficiently discerning a certain equilibrium notion among multiple agents from data collected via online interactions. Some popular equilibrium notions include Nash equilibrium (NE), correlated equilibrium (CE), and coarse correlated equilib- rium (CCE).
However, multi-agent general-sum Markov Games (MGs) bring forth various challenges. In partic- ular, empirical application suffers from the large state space. Such a challenge necessitates the use of the function approximation and avoid dealing directly with the large state space. Yet, adopting function approximation general-sum MG brings about additional complexities not found in single-agent RL or zero-sum MG. Many prevailing studies on single-agent RL or two-agent zero-sum MGs with the function approximation leverage the special relationships between the optimal policy and the optimal value function (Jin et al., 202 la; Du et al., 2021; Zhong et al.. 2022; Jin et al.. 2022; Huang et al., 2021; Xiong al., 2022). In particular, in single-agent RL, the optimal policy is the greedy policy with respect to the optimal value function. Whereas in a two-agent zero-sum MG, the Nash equilibrium
effective way to extract the essential features of RL problems
a
"Equal contribution

---

Published as a conference paper at ICLR 2024
is obtained by solving a minimax estimation problem based on the optimal value function. Contrast- ingly, in general-sum MG, individual agents possess distinct value functions, and thus there exists no unified optimal value function that characterizes the equilibrium behavior. Moreover, unlike zero-sum MG, a general-sum MG can admit diverse equilibrium notions, where each corresponds to set of policies. Consequently, methodologies developed for single-agent RI. or zero-sum MGs cannot be directly extended to general-sum MGs.
Recently, several works propose sample-efficient RL algorithms for general-sum MGs. In particular, Chen et al. (2022b); Foster et al. (2023) propose model- algorithms for learning NE/CCE/CE based on aaget extensions of the Estimation-to-Dert to-Decision algorithm (Foster al., 2021), and they establish regret upper bounds in terms of complexity metrics that extend Coefficient (Foster et al., 2021) to MGs. In addition, Wang et al. (2023) study model-free RI. for general-sum MGs with the general function approximation. They focus on developing a decentral- ized and no-regret algorithm that finds CCE Thus, it seems unclear how to design a provably sample-efficient MARL algorithm for NE/CCE/CE for general-sum MGs in model-free manner. Furthermore, motivated by the recent development in single-agent RL (Jin et al., 202 la; Du et al., 2021: Zhong et al., 2022: Foster et al., 2021; Liu et al., 2023), we aim to develop a unified algorith- mic framework for MARL that covers both model-free and model- based approaches. Thus, we aim to address the following questions:
Estimatton
Can we design a unified algorithmic framework for general-sum MGs such that (i) it is provably sample-efficient in learning NE/CCE/CE in the context of the function approximation and (ii) it covers both model-free and model-based MARL approaches?
In this paper. we provide an affirmative answer to the above questions. Specifically, we propose a unified algorithmic framework named Multi-Agent Sirimize-to-EXplor (MAMEX) for general- sum MGs with the general function approximation. MAMEX extends the framework of Maximize- to-Explore (Liu et al., 2023) to general-sum MGs by employing it together with an equilibrium solver for general-sum normal-form games defined over the policy space.
Maximize-to-Explot (MEX) is a class of RL algorithms for single-agent MDP and two-agent zero- sum MGs where each new policy is updated by solving optimization problem involving hy- pothesis f. which can be regarded as the action-value function in the model-free version and the transition model in the model-based version. The optimization objective of MEX contains two terms- - (a) the optimal value with respect to the hypothesis f and (b) a loss function computed from data that quantifies how far f is from being the true hypothesis. Here, the term (a) reflects the planning part of online RL and leverages the fact that the optimal policy is uniquely characterized by the given hypothesis. On the other hand, the term (b), which can be the mean-squares Bellman error or log- likeliiiiiood function, reflects the estimation part of online RL. By optimizing the sum of (a) and (b) over the space of hypotheses without any data- deta-de constraints, MEX balances exploitation with exploration in the context of the function approximation.
However, the first term in MEX's optimization objective leverages the fact that the optimal policy can be uniquely constructed from the optimal value function the true model, using greedy step or dynamic programming. Such a nice property cannot extended to general-sum MGs, where the relationship between the equilibrium policies and value function is more complicated, and each agent has its own value function. As a result, it is impractical to construct a single-objective optimization problem in the style of MEX over the hypothesis space for general-sum MGs.
Instead of optimizing over the spaces of hypotheses, MAMEX optimizes over the policy space. Specifically, in each iteration, MAMEX updates the joint policy of all agents by solving for desired equilibrium (NE/CCE/CE) of a normal-form game, where the pure strategies are a class of joint policies of the n agents, e.g., the class of deterministic joint policies. Besides, for each pure strategy of this normal form game, the corresponding payoff function is obtained by solving a regularized optimization problem over the hypothesis space à la MEX. Thus, policy updates in MAMEX involve the following two steps:
(i) For each pure strategy म. construct the payoff function V, (T) for each agent by solving an unconstrained and regularized optimization problem;
(ii) Compute the NE/CCE/CE of the normal-form game over the space of pure strategies with payoff functions (V<(T)) where n is the number of agents.
2

---

Published as a conference paper at ICLR 2024
The implementation of MAMEX only requires an oracle for solving single-objective and un- constrained optimization problem and an oracle for solving NE/CCE/CE of a normal-form game. Compared to existing works that either solve constrained optimization subproblems within data- dependent constraints (Wang et al., 2023), or complex multi-objective or minimax optimization subproblems (Foster et al., 2023; Chen al., 2022b), MAMEX is more amenable to practical im- plementations. Furthermore, step (i) of MAMEX resembles MEX, which enables both model-free and model-based instantiations.
We prove that MAMEX is provably sample-efficient in a rich class of general-sum MGs. To this end, we introduce a novel complexity measure named Multi-Agent Decoupling Coefficient (MADC) to capture the its variants (Dann et al., 2021; Agarwal & Zhang, 2022; Zhong et al., 2022) proposed for the single- agent setting. MADC characterize the hardness of exploration in MGs in terms of the discrepancy between the out-of-sample prediction error and the in-sample training error incurred by minimizing a discrepancy function & on the historical data. MADC is defined based on the intuition that if a hypothesis attains a small training error on a well-explored dataset, it would also incur a small prediction error. When the MADC of an MG instance is small, achieving a small training error ensures a small prediction error, and thus exploration is relatively easy. We prove that MAMEX achieves a sublinear regret for learning NE/CCE/CE in classes with small MADCs, which includes multi-agent counterparts of models with low Bellman eluder dimensions (Jin et al., 2021a; 2022; Huang et al., 2021), Bilinear Classes (Du al., 2021), and models with low witness ranks (Sun al., 2019; Huang et al., 2021). When specialized to specific members within these classes, MAMEX yields comparable regret upper bounds existing works.
tradeoff in MARL. Compared to the decoupling coefficient and
Our Contributions. In summary, our contributions are two-fold.
First, we provide unified algorithmic framework named Multi-Agent Cettmizze-t-EEXploo (MAMEX) for both model-free and model-based MARI., which sample-efficient finding the NE/CCE/CE in general-sum MGs with small MADCs. Moreover, MAMEX leverages an cquilibrium-sobl
oracle for normal-form games defined over a class of joint policies for pol- icy updates, and single-objective optimization procedure that solves for the payoff' functions of these normal-form games. To our best knowledge, the model-free version of MAMEX is the first model-free algorithm for general-sum MGs that learns all three equilibria NE, CCE, and CE with sample efficiency.
Second, introduce complexity measure, Multi-Agent Decoupling Coefficient (MADC), to quantify the hardness of exploration in general-sum MG in the context of the function approxima- tion. The class of MGs with low MADCs includes rich class of MG instances, such multi-agent counterparts of models with low Bellman eluder dimensions (Jin et al., 202 la; 2022; Huang et al., 2021), Bilinear Classes (Du al., 2021), and models with low witness ranks (Sun al., 2019; Huang et al., 2021). When specialized to specific MG instances in these classes, we achieve comparable regret upper bounds to existing works.
Related Works Our paper is closely related to the prior research on Markov Games and MARL with the function approximation. A comprehensive summary of the related literature is in $A.
2
MODELS AND PRELIMINARIES
2.1
MARKOV GAMES
For clarity, certain mathematical notations are provided in Appendix $B.
General-Sum Markov Games In this work, we consider general-sum Markov Games (MGs) in the episodic setting, which is denoted by tuple (8, H, (r( )eE))))e(H) (eT)) P), where n is the number of agents, H is the length of one episode, S is the state set, and A = A; A R is the known reward function of the agent i at step h, PA: S A + A(S) is the transition kernel at the h-th step, and p E ASS) is the distribution of the initial state s1. We assume the n agents
is the joint action set. Here, A; is the action set of the agent i. Moreover, r/
I Our results can he extended to the unknown stnchastic reward case (Agarwal & Zhang, 2022; Zhong et al., 2022). Note that learning the transition kemne is more difficult than learning the reward.
3

---

Published as a conference paper at ICLR 2024
observe the same state each step and each agent i chooses action within its own action set A; simultaneously. In each episode, starting from $1 ~ Po. for each E [H], the agents choose their (1) an (m)) Then, each agent i receives its
joint action on A in state Sh, where on (d)
(8) I'n (sh, an), and the game move to the next state sh+11 ~ (35+1 | 8h, ax). Moreover, we
reward
assume Σ Thh (sh: (sh.an) an) E [0, R] for any possible state-action sequences for some S R S H.
In MGs, the agents' policy can be stochastic and correlated. To capture such property, we introduce the notion of pure policy and joint policy as follows. For each agent i, its local (Markov) policy maps a state to a distribution over the local action space A,. We let 1g S { S + A(A.)) denote subset of the agent i's local policies for step h [H], which is called the set of Markov pure policies. We then define n7 = UNE(H] H T We assume the agent i's policy is a random variable taking values in I1; Specifically, let Q be the random seed. The random policy x0 (5) = =\Tr Meen for the agent i contains mappings ((1) : Q + I1 such that "h
((((w) E Ig pure policy. To execute (5), the agent first samples a random seed w S2 and then follows the policy Th (w) for all E [H]. The joint policy π of the n agents is a set of policies {=
where w (wi,-.. w.) are joint variables. In other words, {m (2) (w:)se E @i=, are random policies of the n agents whose randomness is correlated by the random seed w. Equivalently, can regard ı as a random variable over _ h.5- Furthermore, a special class of the joint policy is the product policy, where each agent executes their own policies independently. In other words, we have w = (Wi....,.44 Wr), where w1,.... Wa are independent, and each (+1) depends on wi only, We let (a 8) denote the probability of taking action in the state s at step h. As result, we have (a 8) = 1 (a) 8) for any product policy т.
Furthermore, using the notion of pure policy and joint policy, we can equivalently view the MG as normal form game over TTpur = 60 TT. That is, each pure policy can be viewed as pure strategy of the normal form game, and each joint policy can be viewed is without loss of gencrality, because we can choose 11.00 to be the set of all possible deterministic policies of the agent i. Meanwhile, using general II. we also incorporate parametric policies as the pure policies, e.g., log-linear policies (Xie et al., 2021; Yuan et al., 2022; Cayci et al., 2021).
mixed strategy. Such view
The value function (((),= is the expected cumulative rewards received by the agent i from step h to step H. when all the agents follow a joint policy π,, which is defined as
A
v
(i)T (s)
( Th Σ
(sw, sn 5)
E
We let ((0).(p)) = ExpplV ( 0. (s)] denote the agent i's expected cumulative rewards within the whole episode. Besides, the corresponding Q-function (action-value function) can be written as
(s,a) Ex
Σ
(6) (0) T (sw, an) 8h = =8,
(2.1)
Wihh
For a joint policy π and any agent i, we let (-+) denote the joint policy excluding the agent i. Given ((-), the best response of the agent is defined as (())t arg max V())xxal ( (p), which is random policy of the agent that maximizes its expected rewards when other agents follow (-)), Besides, we denote (f)), (x.00, r(-1)).
Online Learning and Solution Concepts We focus three common equilibrium notions in the game theory: Nash Equilibrium (NE), Coarse Correlated Equilibrium (CCE) and Correlated Equi- librium (CE).
First, a NE of a game is a product policy that no individual player can improve its expected cumula- tive rewards by unilaterally deviating its local policy.
Definition 2.1 (s-Nash Equilibrium). A product policy π is an E-Nash Equilibrium if
G)x Ghx (p) (i))=(p) + & for all i [n]. where p(0,. (1,t, (-)) and (0,t is the
best response policy with respect to (-())
4

---

Published as a conference paper at ICLR 2024
In other words, product policy is e-Nash Equilibrium if and only if
V(OLe (p) - ()) Se.
max VE[M )EA(D!))
max
In this work, we design algorithms for the online and self-play setting, That is, we control the joint policy all agents, interact with the environment over K episodes, and aim to learn the desired equilibrium notion from bandit feedbacks. To this end, let x denote the joint policy that the agents execute the k-th episode, A E [ We define the Nash-regret as the cumulative suboptimality across all agents with respect to NE.
Definition 2.2 (Nash- Regret,, For all l E [K]] let x denote the product policy deployed in the k-th episode, then the Nash-regret is defined as
n (vOnlor (0)- v(O,=* x* (D)).
RegNE (K)
By replacing the concept of NE to CCE and CE, we can define CCE-regret and CE-regret in a similar way. The detailed definitions are provided in $C.
We note that the definitions of NE, CCE, and CE align with those defined on the normal form game defined on the space of pure policies. That is, each agent i's "pure strategy" is a pure policy (9) I1!" and the "payoff" of the agent when the "mixed strategy" is π is given by V() (p))
2.2 FUNCTION APPROXIMATION
To handle the large state space in MARL, assume the access to hypothesis class F, which captures the Q function in the model-free setting and the transition kernel in the model- based setting.
Model-Based Function Approximation In the model-based setting, the hypothesis class F contains the model (transition kernel) of MGs. Specifically, we let P/- {F.. .H.r} denote the transi- tion kernel parameterized by f E F. When the model parameters are f and the joint policy is n, we
denote the value function and Q-function of the agent at the h-th step as (1)).r (s) and Qi. (s, (s. respectively. We have the Bellman equation Qhiy (s, a) = rh (0 a) + Ea ((1s,)) 1+1, (s')].
(0,0
Model-Free Function Approximation In the model-free setting, we let F 8 F(1
8/ (8 F( be class of Q-functions of the n agents, where F((1 (1(() A is class of Q-functions of the agent i at the f-thh step. For any f e F, we denote (5, (s,a) (s,a) for all i E [r] and h E [H]. Meanwhile, for any joint policy π and any / E F, we define
v (0) f.f (s) Ea U/ a) (1 " (s, mx(- {
For any joint policy म. agent i, and step h. we define the Bellman operator T by letting
(T (T(()))(((())))))) (Jh+1))(s, a) = 1/ 102 (s, + BerePh(e')ee (S', m) 8')),, AS VfE
(2.2)
Note that the Bellman operator depends on the index i of the agent because the reward functions of the agents are different. Such a definition is an extension of the Bellman evaluation operator in the single-agent setting (Puterman, 2014) to the multi-agent MGs. By definition, (2)0). defined in
(2.1) the fixed point of T, (i).r i.e., Q..).. T.(0). (Q())T) for all E (H).
For both the model-based and the model-free settings, we impose the realizability assumption, which requires that the hypothesis space F is sufficiently expressive such that it contains the true transi- tion model or the true Q- Q-ffuctions. Besides, for the model-free setting, we also require that the hypothesis classes be closed with respect to the Bellman operator.
Assumption 2.3 (Realizability and Completeness). For the model-based setting, we assume the true transition model f lies in the hypothesis class F. Besides, for the model-free setting, for any pure policy nt and any E [m]. we assume that (+),= (()) and T (1). 7(t)
h+1 C F(()) for all h E [M].
5

---

Published as a conference paper at ICLR 2024
Covering Number and Bracketing Number. When function class F is infinite, the ò-covering number (5) and the b-bracketing number (6) serve as surrogates of the cardinality F. We put the definitions in $C.2.
Multi-Agent Decoupling Coefficient Now introduce key complexity measure multi-agent decoupling coefficient (MADC)- - which captures the hardness of exploration in MARL. Such a notion an extension of the decoupling coefficient (Dann et al., 2021) to general-sune MGs. Definition 2.4 (Multi- Decoupling Coefficient). The Multi-Agen Agent Decoupling Coefficient of MG is defined as the smallest constant dMADC 2 such that for any i [ni], 1 >> 0, {f" ]KE[K] C F(), and ]RE[K] C
I[pur the following inequality holds:
K
k-1 gl)) (+" xh,, + μ. dMADO + GdMADDHL
(0) (0)-vie V(0 (0)-v(0 (0))
(2.3)
f
1
gap
prediction error
training error
where we define v (p) = Es VV(ia= (s1)]. and (f) Th) is a discrepancy function that
measures the inconsistency between f and n² on the historical data. The specific definitions of (809.*) be(m)ss<([ |] under the model-free and model-basee settings given in (2.4) and (2.5).
Model-Free RL In the model-free setting, for (T*)AEEK) S Ilpuur in (2.3), the discrepancy function
(f,)))) for 1lP is defined
H
(J,x)
Σ
(e bang ((/n - T.(0, (fh+1))) an))?: AA E F(0 A [K]. (2.4) -Th
h=1
That is, (f,((x))) measures agent i's mean mean-squared Bellman error for evaluating x. when the trajectory is sampled by letting all agents follow policy Ç".
Model-Based RL We choose the discrepancy function g(),s in Assumption 2.5 as
11
Σ
B(sn.ar ),nj (Fn, Sh, PF.][[P... 8h, ax)),
(2.5)
h=1
where Dn denotes the Hellinger distance and (sn,aan)vt bwng means that the expectation is taken with respect to the randomness of the trajectory induced by x" on the true model ft. Intuitively, it represents the expected in-sample distance model fh and true model f*
Note that the discrepancy between fh. Th in (2.3) is summed model-free and model-based settings, the training error can be viewed as the in-sample error of fü on the historical data collected before the k-th episode. Thus, for an MG with finite MADC, the prediction error is small whenever the training error is small. Specifically, when the training error is O(K)) for some 20, then by choosing proper 14, know that the prediction error grows O(VK" dMADC) = o(K). In other words, as K increases, the average prediction error decays to zero. In single-agent RL, when we adopt an optimistic algorithm, the prediction error serves as an upper bound of the regret (Dann et al., 2021; Zhong et al., 2022; Jin al., 2021a). Therefore, by quantifying how the prediction error is related to the training error, the MADC can be used to characterize the hardness of exploration in MARL.
s E [k: 1]. Thus, in both the
Compared to the decoupling coefficient and its variants for the single-agent MDP or the two-player zero-sum MG Dann et al. (2021); Agarwal & Zhang (2022); Zhong et al. (2022); Xiong al. (2022), MADC selects the policy x² in different way. In the single-agent setting, the policy x² is always selected as the greedy policy of ft hence VT, (p) is equivalent to the optimal value function. In the zero-sum MG, the policy pair x* is always selected as the Nash policy and the best response (Xiong al., 2022). On the contrary, in our definition, the policy x is not necessarily the greedy policy of fk In fact, { ]KE(K) can be any pure policy sequence that is unrelated to {f ]ee(k)- Assumption 2.5 (Finite MADC). We assume that the MADC of the general-sum MG of interest is finite, denoted by dMADC. As we will show in Section D, the class of MGs with low MADCs include rich class of MG instances, including multi-agent counterparts of models with low Bellman eluder dimensions (Jin et al., 2021a; 2022; Huang et al., 2021), bilinear classes (Du et al., 2021), and models with low witness ranks (Sun al., 2019; Huang et al., 2021).

---

Published as a conference paper at ICLR 2024
3 ALGORITHM AND RESULTS
In this section, we first introduce a unified algorithmic framework called Multi-Agent Maximize-to- EXplore (MAMEX). Then, present the regret and sample complexity upper bounds of MAMEX, showing that both the model-free and model-based versions of MAMEX are sample-efficiet for learning NE/CCE/CE under the general function approximation.
3.1 ALGORITHM
Algorithm Multi-Agent Maximizz-tt--XXloor (MAMEX)
Input: Hypothesis class F, parameter vi an equilibrium solving oracle EQ.
2: for k = 1,2..... do
3: Compute V. (T) defined in (3.1) for all क E Ie and all E [n].
4: Compute the NE/CCE/CE of the normal-form game defined on Il with payoff functions (V. x* <- EQ(V", (1.
5: Sample a pure joint policy <* ~ x", and collect a trajectory {*h az hee following 5*
6: Update (1,0),4 hi=1 according to (3.2) smodel-free) or (3.3) (model-based).
7: end for
In this subsection, we provide the MAMEX algorithm for multi-agent RI. under the general function approximation, which extends the MEX algorithm (Liu et al., 2023) to general-sum MGs. Recall that the definitions of NE/CCE/CE of general-sum MGs coincide with those defined in the normal- form game with pure strategies being the pure policies in [[pur, Thus, when we know the payoff's (V(), (p) ]ejm for all π E I|p"r we can directly compute the desired NE/CCE/CE given an equi- librium solving oracle for the normal-form game. However, each ((i) (p) is unknown and has to be estimated from data via online learning. Thus, nutshell, MAMEX an iterative algorithm that consists of the following two steps:
(a) Policy evaluation: For each l E [K], construct an estimator V. (Iz) of V(O) (p) for each pure policy I[ and the agent [n] in each episode based on the historical data collected in the previous k k-1 episodes. Here, the policy evaluation subproblem can be solved in both the model-free and model-based fashion.
(b) Equilibrium finding: Compute an equilibrium (NE/CCE/CE) for the normal-form game over the space of pure policies with the estimated payoff functions (V) The joint policy returned by the equilibrium finding step is then executed in the next episode to generate a new trajectory.
By the algorithmic design, to strike a balance between exploration and exploitation, is crucial to construct (V. (T) } in such way that promotes exploration. To this end, solve regularized
optimization problem over the hypothesis class F(()) to obtain V (T)) where the objective function balances exploration with exploitation. We introduce the details of MAMEX as follows.
Policy Evaluation. For each & E [K], before the k-th episode, we have collected &: trajectories T 1i:-1 - ri. ... .HH a'y. }. For any i E [n], E I[P"r and f E ( we can define a data-dependent discrepancy function r, T,(0),-1 (ʃ. π, -1,-1: Such function measures the in-sample error the hypothesis f with respect a policy и, evaluated on the historical data -1:k-1 The specific form of such a function differs under the model-free and model-based settings. In par- ticular, as we will show in (3.2) and (3.3) below, under the model-free setting, A (f.)) (1:k-1)
constructed based on the mean squared Bellman error with respect the Bellman operator ( in (2.2), while under the model- based setting, L ((),k-1( (f, म, 7 -l:k-1) is constructed based on the negative log- likelihoood loss. Then, for each æ E [muu and E [n]]. we define V (TT) as
V (TT)
{D())an()) = v/(h (() (p) ( (f, म. 1:k
sup JEFC
(3.1)
(b)
For ease of notation, under the model-based setting, we denote (() F for all agent E [n].

---

Published as a conference paper at ICLR 2024
Equilibrium Finding. Afterwards, the algorithm utilizes the equilibrium oracle EQ (Line 4 of Algorithm 1) to compute an equilibrium (NE/CCE/CE) for the normal-form game over IIP"r with payoff functions (V (+) The solution to the equilibrium oracle is mixed strategy x² i.e., probability distribution over IlPur.
Finally, we sample random pure policy < from n5 and execute Ç in the k-th episode generate a new trajectory. See Algorithm I for the details of MAMEX. Here, we implicitly assume that Il is finite for ease of presentation. For example, I[P is the set of all deterministie policies. When πuur is infinite, we can replace I[pur by a 1/ -oovr of I with respect to the distance d( (T(0) ()))
max,es (| () - (- |>]]l.
Furthermore, the objective (())).))))))) in (3.1) is constructed by sum of (a) the value function (p) of π under the hypothesis f and (b) a regularized term -1 (0) (f: 11k-11 ) and the payoff function (T) is obtained by solving a maximization problem over F()) The two terms (a) and (b) represent the "exploration" and "exploitation" objectives, respectively, and the parameter > 0 controls the trade-off between them. To see this, consider the case where we only have the term (b) in the objective function. In the model-based setting, (3.1) reduces to the maximum likelihood estimation (MLE) of the model I given the historical data 7 -1:k-1, Then n² returned by Line 4 is the equilibrium policy computed from the MLE model. Thus, without term (a) in (f),, the algorithm only performs exploitation. In addition to fitting the model, the term (a) also encourages the algorithm to find a model with large value function under the given policy т, which promotes exploration. Under the model-free setting, only having term (b) reduces least-squares policy evaluation (LSPE) (Sutton & Barto, 2018), and thus term (b) also performs exploitation only.
Vj vi
Comparison with Single-Agent MEX (Liu et al., 2023). When reduced to the single-agent MDP, MAMEX can be further simplified to the single-agent MEX algorithm (Liu et al., 2023). In par- ticular, when
I, equilibrium finding is reduced to maximizing the function defined in (3.1) over single-agent policies, i.e., max, maxfer ()* By exchanging the order of the two max- imizations, we obtain an optimization problem over the hypothesis class F, which recovers the single-agent MEX (Liu et al., 2023). In contrast, in general-sum MGs, the equilibrium policy can no longer be obtained by singlc-objective optimization problem. Hence, it is unviable to directly extend MEX to optimize over hypothesis space in MARL. Instead, MAMEX solves an optimization over F in the style of MEX for each pure policy æ E I and then computes the NE/CCE/CE of the normal-form game over the space of pure policies.
Comparison with Existing MARL Algorithms with Function Approximation Previous RL al- gorithms for MGs with the general function approximation usually require solving minimax opti- mization (Chen et al., 2022h; Zhan et al., 2022a; Foster al., 2023) or constrained optimization subproblems within data-dependent constraints (Wang et al., 2023). In comparison, the optimiza- tion subproblems of MEX are single-objective and do not have data-dependent constraints, and thus seem easier to implement. For example, in practice, the inner problem can be solved by regularized version of TD learning (Liu et al., 2023), and the outer equilibrium finding can be realized by any fast method to calculate equilibrium (Hart & Mas-Colell, 2000; Anagnostides et al., 2022).
In the following, we instantiate the empirical discrepancy function I ( for both the model-free setting and the model-based setting.
Model-Free Algorithm Under the model-free setting, we define the empirical discrepancy function as follows. For any h [M] and & E [K], let ex { at 1 J. For any i [n]. I[Pur and f E F(O,
we define
1-1
10),-1 1ik-11
Σ 4=1 j=1
( (c))),))))
inf (Eh, (. (3.2)
where 16" (f) = (J,(s//.a) mean-squared Bellman error involving Sn and Dh+1-
f.g.
-r (5/, at)) - (0n+1 (6 Tntil si a)) is the -0
8

---

Published as a conference paper at ICLR 2024
In Lemma E.I, show that L(),8-1(f (,,,, is upper bound of Σ==1 (f T), where g60,s defined in (2.4). Thus, the function k can be used control the training error in the definition of MADC.
Model-Based Algorithm For the model-based setting, we define L as the negative log- likelihood:
H --1
(f,
log Ph,, (8/ a)).
(3.3)
h=
As we will show in Lemma E.3, the function k-) can be used to control the training error in (2.3), where g(o,s is defined in (2.5).
3.2 THEORETICAL RESULTS
In this subsection, we present our main theoretical results and show that MAMEX (Algorithm 1) is sample-efficient for learning NE/CCE/CE in the context of general function approximation.
Theorem 3.1. Let the discrepancy function g(0), in (2.3) defined in (2.4) and (2.5) for model-free and model-based settings, respectively. Suppose Assumptions 2.3 and 2.5 hold. By setting K > 16 and 1 = 4/vK < 1, with probability at least 8, the regret of Algorithm I after K episodes is upper bounded by
ReSNE,CCE.CE(K)) S (NHVKKTF, ndMADC V ndMADCH..
where O(.) hides absolute constants and polylogarithmic terms in H and K, and T is term that quantifies the complexity of the hypothesis class F. In particular, we have F = R² log [max N/ (1/K)- [I]) in the model-free setting and T T log (B)((/))/6) in the model-based setting.
Theorem 3.1 shows that our MAMEX achieves a sublinear v --rreget for learning NEJCCE/CE, where the multiplicative factor depends polynomially on the number of agents n and horizon H. Thus, MAMEX sample-efficient in the context the general function approximation. More- over, the regret depends on the complexity of the hypothesis class via two quantifies the MADC dMADC. which captures the inherent challenge of exploring the dynamics of the MG, and the quan- tity TF,6, which characterizes the complexity of estimating the true hypothesis f" based data. To be more specific, in the model-free setting, since we need to evaluate each pure policy, T=,5 con- tains log [T[pur] due to uniform concentration. When reduced to the tabular setting, T to be the set of deterministic policies, and both Y and dMADC are polynomials of (S] and [A]. Furthermore, when specialized to tractable special cases with function approximation and some special pure policy class such as log-linear policy class Cayci et al. (2021), we show in $D that The- orem D.8 yields regret upper bounds comparable to existing works. Moreover, using the standard online-to-baad bottchh techniques, we can transform the regret bound into sample complexity result. We defer the details to $E.3.
choose
CONCLUSION
In this paper, we study multi-player general-sum MGs under the general function approximation. We propose a unified algorithmic framework MAMEX for both model-free and model-base RL problems with the general function approximation. Compared with previous works that either solve constrained optimization subproblems within data-dependent sub-level sets (Wang et al., 2023). or complex multi-objective minimax optimization subproblems (Chen et al., 2022b; Foster et al., 2023), the implementation of MAMEX requires only oracle for solving a single-objective unconstrained optimization problem with an equilibrium oracle of a normal-form game, thus being more amenable to empirical implementation. Moreover, we introduce complexity measure MADC to capture the exploration-exploittiee tradeoff for general-sum MGs. We prove that MAMEX is provably sample- efficient in learning NE/CCE/CE RL problems with small MADCs. which covers rich class of MG models. When specialized to the special examples with small MADCs, the regret of MAMEX comparable existing algorithms that designed for specific MG subclasses.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports. Zhuoran Yang acknowledges Simons Institute (Theory of Reinforcement Learning) for its support.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Alekh Agarwal and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. In Advances in Neural Information Processing Systems, 2022.
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pp. 1638-1646. PMLR, 2014.
Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Andrea Celli, and Tuomas Sandholm. Faster no-regret learning dynamics for extensive-form correlated and coarse correlated equilib- ria. arXiv preprint M.Xiv:2202.054444 2022.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Inter- national conference on machine learning, pp. 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play, Advances in neural information processing systems, 33:2159-21700 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:25799-25811, 2021.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374)4418 4224 2018.
Semih Cayci, Niao He, and Rayadurgam Srikant. Linear convergence of retropy-re natural policy gradient with linear function approximation. arXiv preprint 1XXi:22066040966 2021.
Fan Chen, Yu Bai, and Song Mei. Partially observable rl with b-stability: Unified structural condition and sharp sample-efficient algorithms. arXiv preprint arXiv:2209. /4990, 2022a.
Fan Chen, Song Mei, and Yu Bai. Unified algorithms for rl with decision-estimation coefficients: No-regret, pac, and reward-free learning. arXiv preprint arXiv:2209.11745, 2022b.
Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael Jordan. A general framework for sample-efficient function approximation reinforcement learning. arXiv preprint arXiv:2209.1556 2022c.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero- sum linear mixture markov games. In International Conference on Algorithmic Learning Theory, pp. 227-261. PMLR, 2022d.
Qiwen Cui, Kaiqing Zhang, and Simon Du. Breaking the curse of multiagents in large state space: RI in markov games with independent linear function approximation. arXiv preprint arXiv:2302.03663, 2023.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. 2008.
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:12040-12051 2021.
10

---

Published as a conference paper at ICLR 2024
Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang, The complexity of markov equilib- rium in stochastic games. arXiv preprint arXiv:2204.03991, 2022.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint
2021.
Dylan J Foster, Dean P Foster, Noah Golowich, and Alexander Rakhlin. On the complexity of multi-agent decision making: From learning in games partial monitoring. arXiv preprint arXiv:2305.00684, 2023.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127-1155) 2000.
Baihe Huang. Jason Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approx- imation in zero-sum markov games. In International Conference Learning Representations, 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low bellman rank are pac-leamable. International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete pomdps. Advances in Neural Information Processing Systems, 33: 18539, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34, 2021a.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentral- ized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555: 2021b.
Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent in large state spaces. In International Conference on Machine Learning, pp. 10251-10279, PMLR,, 2022.
Avetik Karagulyan. Sampling with the Langevin Monte-Carlo. PhD thesis, Institut polytechnique de Paris, 2021.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent rein- forcement learning. Advances neural information processing systems, 30, 2017.
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforce- ment learning with self-play. In International Conference on Machine Learning, pp. 7001-7010. PMLR, 2021.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforce- ment learning not scary? arXiv preprint arXiv:2204.0899) 2022a.
Qinghua Liu, Csaba Szepesvári, and Chi Jin. Sample-efficient reinforcement learning of partially observable markov games. arXiv preprint arXiv:2206.013/5, 2022b.

---

Published as a conference paper at ICLR 2024
Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. One objective to rule them all: A maximization objective fusing estimation and planning for exploration. arXiv preprint arXiv:2305.18258 2023.
Luke Marris, Paul Muller, Mare Lanctot, Karl Tuyls, and Thore Graepel. Multi-agent training be- yond zero-sum with correlated equilibrium meta-solvers. In International Conference on Machine Learning. pp. 7480-7491. PMLR, 2021.
Chengzhuo Ni, Yuda Song, Xuezhou Zhang, Chi Jin, and Mengdi Wang. Representation learning for general-sum low-rank markov games. arXiv preprint arXiv:2210.1691 2022.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances Neural Information Processing Systems, 26, 2013.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwisser, loannis Antonoglou, Veda Panneershelvam,, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484449 2016.
Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum markov games with a large number of players sample-efficienlly? arXiv preprint arXiv:2110.04184, 2021.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. Conference on learning theory, pp. 2993-2933. PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning An introduction. MIT press, 2018.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning in unknown markov games. In International conference on machine learning, pp. 10279-10288. PMLR, 2021.
Oriol Vinyals, Igor Babuschkin, Wojeiech Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3350-354 2019.
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint arXiv:2005. 10800 2020a.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neurul Information Processing Systems, 33:6123 2161123-11363 3135, 2020b.
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv: 1912.0:: 2019.
Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably effi- cient decentralized multi-agent rl with function approximation. arXiv preprint arXiv:2302. 06606, 2023.
Chen-Yu Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning in stochastic games. Advances in Neural Information Processing Systems, 30, 2017.
Michael P Wellman. Methods for empirical game-theoretic analysis. In AAAI, volume 980, pp- 1552-1556, 2006.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. Conference on learning theory, pp. 3674-3682. PMLR, 2020.
Tengyang Xie, Ching- An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consisted pessimism for offline reinforcement learning. Advances neural information processing systems, 34:6683-6694, 2021.
12

---

Published as a conference paper at ICLR 2024
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, and Tong Zhang. A self-play posterior sam- pling algorithm for zero-sum markov games. In International Conference on Machine Learning, pp. 24496-24523, PMLR, 2022.
Rui Yuan, Simon S Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprinl arXiv:2210.01 10.01400, 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference Machine Learning, pp. 10978-10989, PMLR, 2020.
Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic meth- ods for offine reinforcement learning. Advances in neural information processing systems, 34: 15626-13640) 2021.
Wenhao Zhan, Jason D Lee, and Zhuoran Yang. Decentralized optimistic hyperpolicy mirror de- scent: Provably no-regret learning in markov games. arXiv preprint arXiv:2206.011 01588, 2022a.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee. Pac reinforcement learning for predictive state representations. arXiv preprint arXiv:2207.05738, 2022b.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent in zero-sum markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33:1 16661178,, 2020.
Yulai Zhao, Yuandong Tian, Jason D Lee, and Simon Du. Provably efficient policy optimization for two-player zero-sum markov games. arXiv preprint arXiv:2102.08900; 2021.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang. and Tong Zhang. A posterior sampling framework for interactive decision making, arXiv preprint arXiv:2211.01962 2022.
13

---

Published as a conference paper at ICLR 2024
Supplementary Material
CONTENTS
1
Introduction
2 Models and Preliminaries
2.1 Markov Games
2.2 Function Approximation
3
Algorithm and Results
3.1
Algorithm
3.2 Theoretical Results
4
Conclusion
A Related Work
16
Notation
17
Additional Definitions
17
C.1 NE/CCE/CCE-Regeet
17
C.2 Covering Number and Bracketing Number
18
D Relationships between MADC and Tractable RL Problems
18
D.I Model-Free MARL Problems
18
D.2 Model-Based RL Problems
22
Proof of Main Results
23
E.1 Proof of Model-Free Version of Theorem 3.1
23
E,2 Proof of Model-Based Version of Theorem 3.1
27
E.3 Sample Complexity Results..
30
Proof of Theorems and Lemmas
30
F.1 Proof of Theorem D.4
30
F2 Proof of Theorem D.5
32
F3 Proof of Theorem D.8
33
F4 Proof of Theorem D.12
35
F.5
Proof of Theorem D.14
38
F6
Proof of Lemma E.1
39
F.7 Proof of Lemma E.2
F8 Proof of Lemma E.3
41
F.9 Proof of Corollary E.4
42
14

---

Published as a conference paper at ICLR 2024
Technical Tools
43
Computational Efficiency
43
15

---

Published as a conference paper at ICLR 2024
Appendix
A RELATED WORK
Markov Games Markov Game (MG) (Littman, 1994) is popular model of multi-agent reinforce- ment learning, which generalizes the Markov decision process to multiple agents. A series of recent works design the sample-efficient algorithm for two-agent zero-sum games (Wei al., 2017: Zhang et al., 2020; Xie et al., 2020; Bai et al., 2020: Bai & Jin, 2020; Bai et al., 2021; Zhao et al., 2021; Huang et al., 2021; Jin et al.. 2022; Chen et al., 2022b;d). For instance, Bai & Jin (2020) provide a sample-efficient algorithm in an episodic MG based on optimistic value iteration. Xie et al. (2020); Chen et al. (2022d) mainly focus on zero-sum MGs with a linear structure. Huang et al. (2021); Jin et al. (2022); Chen et al. (2022b) further consider the two-player zero-sum MGs under general function approximation, and provide algorithms with a sublinear regret. Another line of research focuses general-sum MGs with multiple players (Jin et al., 2020a; Liu et al., 2021; Tian et al., 2021; Jin et al., 2021b; Song et al., 2021; Liu et al., 2022b; Daskalakis et al., 2022; Zhan et al., 2022a; Cui et al., 2023; Wang et al., 2023). Some of previous works (Liu et al., 2021; Tian al., 2021; Liu et al.. 2022b) consider learning all three equilibrium notions - NE, CCE, and CE and their regret or sample complexity results are exponential in the number of agents. To break this exponential curse, some existing works propose decentralized algorithms for learning CCE or CE rather than NE (Jin et al., 2021b; Daskalakis et al., 2022; Zhan et al., 2022a; Cui et al., 2023; Wang et al., 2023).
Moreover, there are also some works to study how to learn the equilibrium from a practical per- spective. The EGTA (Wellman, 2006) uses graph to represent the deviation for all profiles and identify the Nash equilibrium and whether a profile is relatively stable. Note if we want to evaluate all profiles and construct the whole graph, we need many samples to estimate the payoff functions for each profile, and then identify all the deviations and construct the graph. The author also men- tions that one may apply machine learning techniques to fit payoff function over the entire profile space given the available data. In fact, we use the function approximation technique to derive an estimate of all the profiles without estimating all the profiles. Thus, our approach can be considered as a learning approach to evaluate all the profiles.
Some previous works (Lanctot et al., 2017; Marris et al., 2021) propose a practical algorithm PSRO to compute the equilibrium in Markov Games, which also needs an equilibrium-sovvig oracle to learn the equilibrium. To be more specific, the PSRO learns the equilibrium in the following way: At first, every player chooses a uniform policy as their strategy. The algorithm then calculates the equilibrium by a meta-solver and trains an oracle that outputs the best response म; of the equilibrium for player i. After that, the algorithm adds тe into the strategy space of the player i. Last, the algorithm simulates all the new joint policy and construct a new normal-form game for the next iteration. However, in each iteration, it should simulate all the new joint policies and estimate the return. Consequently, the sample complexity increases exponentially as the iteration rounds increase. Different from PSRO, MAMEX utilizes the function approximation technique to the value function. The precise characterization of the structure the value function can help us to evaluate the policy without actually simulating the environment with more samples. To be more specific, at each round, instead of simulating the environment and getting a Monte-Carlo return of each joint policy, MAMEX only needs to solve regularized optimization problem over the function space of the value function. The solution of the optimization problem is used to be a payoff for the normal-form game, Since solving this optimization subproblem does not need to additional samples, MAMEX bypasses the requirement for exponential samples to simulate the environment and estimate the value for each joint policy æ. This characteristic enhances its sample efficiency in comparison to PSRO.
MARL with Function Approximation There are many papers working on multi-player general- sum MGs with the function approximation (Zhan et al., 2022a; Ni et al., 2022: Chen et al., 2022b; Wang et al., 2023; Cui et al., 2023; Foster et al., 2023) that build upon previous works for function setting (Jiang
approximation in the single-agen Wang et al., 2020b; Dann et al., 2021; Du et al., 2021; Jin et al., 2021a; Foster et al., 2021; Chen et al., 2022e; Agarwal & Zhang, 2022; Zhong et al., 2022; Liu al., 2023). In recent years, Xiong
al., 2017; Sun et al., 2019; Jin et al.. 2020b;
16

---

Published as a conference paper at ICLR 2024
et al. (2022) consider the multi--gent decoupling coefficient in the two-player zero-sum MGs, and provide the posterior sampling algorithm. However, unlike a zero-sum MG, a general-sum MG can have various equilibrium concepts, each of which aligns with a specific set of policies. Hence, their definition of the multi-agent decoupling coefficient cannot be extended to the general-sum setting. Chen et al. (2022b) and Foster et al. (2023) generalize the complexity measure Decision- Estimation Coefficient (DEC), and learn the equilibria in model-based general-sum MGs. Ni et al. (2022) provide both model-based algorithm and a model-free algorithm for the low-rank MGs. Some previous works (Zhan et al., 2022a; Wang et al., 2023; Cui et al., 2023) provide model-free algorithms that learn CCE and CE with polynomial sample complexity. Compared to their works, this paper provides a unified algorithmic framework for both model-free and model-based MARL problems, which learns NE/CCE/CE efficiently under general function approximation and provides comparable regret to existing works. In particular, our work provides the first model-free algorithm for learning NE/CCE/CE of general-sum MGs in the context of the general function approximation.
B NOTATION
For n sets Fn. we let W denote Fi ... Fn. For set A, denote A(A) as a set of probability distributions over A. For a vector x E R", we denote || = > [
max==1 [2a]. For function f X + V. we denote If = [f(x) as the infinity norm. For two functions f.g : A + I. we denote (f.9)A= (z)g((())g(2]] as the inner product with respect to the set A. For a Hilbert space V and f,g E V. we denote (f- g)v as the inner product defined in the Hilhert space V. and ||ílv the norm defined in Hilbert space V. For two distributions over P, Q E A(X), the Hellinger dis- Ple=p((((P()))
| VΣ 2? and ||]||
tance is defined as (PIIQ)
1) For a vector r E R., the softmax mapping denoted by Softmax (1) E Rd with (Softmax(z)), = e. /ieeg e
C ADDITIONAL DEFINITIONS
C.I SEECCE/CE-RGGREE
In the following, we provide the definitions of Coarse Correlated Equilibrium (CCE), Correlated Equilibrium (CE), and the corresponding regret CCE-regret and CE-regret. A Coarse Correlated Equilibrium is a joint policy π such that no agent can achieve higher rewards by only changing its local policy. Compared with NE, a CCE allows different agents be correlated, while NE only considers product policies.
Definition C.1 (e-Coarse Correlated Equilibrium). joint policy π is a e-Coarse Correlated Equi- librium if (i),a (p) < v(0,= (p) + for all E [n].
Here, the definition of e- c-CCE is similar to that of an e-NE. But here π is a joint policy, i.e., the randomness of the local policies of the n agents can be coupled together. As result, CCE is a more general equilibrium notion than NE. Similarly, cumulative suboptimality across all agents with respect to CCF.
can define the CCE-regret, which represents the
Definition C.2 (CCE-Regret) For all & E [K]. let nh denote the joint policy that is deployed in the k-th episode, then the CCE-regret is defined as
K
Regcce (K)
Σ Σ
(VOn (p) v()+** (p)).
-
Rm 1=1
Last, the Correlated Equilibrium has been extensively studied in previous works for MARL (Jin al., 2020a; Chen et al., 2022b; Cui et al., 2023; Wang et al., 2023). To introduce the concept of CE, we need first to introduce the strategy modification. A strategy modification for the i-th agent a mapping Φ, 11." + 11,100 Given any random policy n, the best strategy modification for i-th agent is defined as arg max,, (ioe=((V(o""")))<<))) can achieve higher rewards by only changing its local policy through strategic modification.
(p)]. A CE is a joint policy such that no agent
Definition C.3 (e-Correlated Equilibrium). A joint policy π is a e-Correlated Equilibrium if (p)) & V (p) E for any agent i [n].
maxo, E (urr(VV((v()) xx((())))
17

---

Published as a conference paper at ICLR 2024
We can similarly define CE-regret the sum of suboptimality terms with respect to CE.
Definition C.4 (CE-Regret), For any k E [K], let x denote the joint policy that is deployed in the k-th episode, the CE-regret is defined as
(v (0)) - -V(0,= (p)
RegeE! (K) =
max BuNt $1
Compared to the NE/CCE regret, the strategy modification of one agent in CE can be correlated to the policies of other agents. Instead, the best response is independent the other agents.
C.2 COVERING NUMBER AND BRACKETING NUMBER
When a function class F is infinite, the d-covering number and the ò-bracketing number serve as surrogates of the cardinality of F. Intuitively, the ò-covering number is the minimum number of balls of radius ó required to cover a set.
Definition C.5 (ô-Covering Number). The d-covering number of a function class F with respect to distance metric d, denoted (6, d). is the minimum integer 9 satisfying the following property: there exists a subset F S FF with |F'| q such that for any fi E we can find f2 E F with f2) S To simplify the notation, we write (6 || Il as NF
Definition C.6 (6- (6-Bracketing Number). A 8-bracket size N is bracket foi. 92 N where gi and 92 are functions mapping any policy π and trajectory T to R, such that for all i E [N]. E II we have |[g (T. - g5(TT, ) S 6. Also, for any S E F, there must exist an E [N] such that of (T, TH) S (TH) D2 (T, TH) for all possible and æ. The 5-bracketing number of F, denoted
by (6), is the minimum size of ò-bracket.
D RELATIONSHIPS BETWEEN MADC AND TRACTABLE RL PROBLEMS
In this section, we show that the class of MGs with finite MADCs contains a rich class of models. Thus, when applied to these concrete MARL models, Theorem 3.1 shows that MAMEX learns NE/CCE/CE with provable sample efficiency.
In the sequel, we instantiate the discrepancy function g(o). for both model-free and model-based MARL, and introduce some concrete general-sum MG models that satisfy Assumption 2.5.
D.1 MODEL-FREE MARL PROBLEMS
Now provide function classes with small MADCs including multi-agent counterparts of models with low Bellman eluder dimensions (Jin et al., 2021a; Huang et al., 2021) and Bilinear Classes (Du al., 2021). Then, introduce some concrete examples in these members and show that the regret upper bound of MAMEX in Theorem 3.1, when specialized to these special cases, are comparable to existing works.
Multi-Agent Bellman Eluder Dimension Recently, Jin et al. (2021a) introduce model-free complexity measure called Bellman Eluder dimension (BE dimension)and show that function classes with low BE dimensions contain wide range of RL problems such linear MDP (Jin et al., 2020b), kerne MDP (Jin et al., 2021a) and function classes with low eluder dimension (Wang al., 2020a). In this subsection, we extend the notion of BE dimension MARL. First, intro- duce the definition of E-independence between distributions and the concept of distribution eluder dimension.
Definition D.1 (s- Indepeeendett Distributions). Let G be a function class on X, and P...... M/ are probability distributions over X. We called v is e-independent of {f] ... 4o with respect to g if there exists function g E G such that v // i- (IE,, [d) and [L, [g]| E.
By this definition, if is e-dependent of [,4.-.. ...) p... then whenever we have v E (E (g)) for some g G. we also have [E.[g]] S e.
18

---

Published as a conference paper at ICLR 2024
Definition D.2 (Distribution Eluder Dimension). Let & be function class on X' and D be family of probability measures over X. The distributional eluder dimension dimpe(G, D.E) ) is the length of the longest sequence Pi.-." P S D such that there exists e' 2 where P; is e'-independent of (Pi.".. .P-11 } for all E [x].
In other words, distributional eluder dimension dimpp(G, s, is the length of the longest quences of distributions in D such that each clement is e'-independent of its predicessors with respect to G. from some e' 2 e. Such notion generalizes the standard eluder dimension Russo & Van Roy (2013) to the distributional setting. When we set 'D to be the set of Dirac measures ()) the distributional eluder dimension dimpe D.E) reduces to the standard eluder dimension introduced in Russo & Van Roy (2013). Here, G G = {gi 9 91 92 G).
For any agent and any pure policy æ E I[pur, we denote the function class of the Bellman residual as [()). = {fh - -() f f E F( J. Now we introduce the definition of the multi-agent BE dimension with respect to a class of distributions.
Definition D.3 (Multi-Agent Bellman Eluder Dimension). Let D (Daheet be set of H classes of distributions over A, one for each step of an episode. The multi-agent Bellman eluder (BE) dimension with respect to D is defined
diMMABE F,D)
max max bE[H] (E[n)
/dimee
U TETTu
(D.1)
In other words, the multi-agent BE dimension is defined the maximum of the distribution eluder dimensions with respect to Dr. based on the agent-specific Bellman residue classes URETTeor F(0.. Compared with the BE dimension for single-agent RL (Jin et al., 202 the multi-agent version takes the maximum over the agent index E [n]. and the function class involves the union of the function class =(),= for all I In comparison, leveraging the facts that the optimal policy is the greedy policy of the optimal value function, and that the optimal value function is the fixed point of the Bellman optimality operator, suffices only consider residues of the Bellman optimality operator in the definition of single-agent BE dimension. In contrast, for general-sum MGs, finding a single-objective policy optimization problem, and the notion
the desired equilibrium policies of the Bellman optimality operator is not well-defined. As a result, to extend the concept of Bellman eluder dimension general-sum MGs, in the function class, we take into account ((), for all E I[ which correspond to evaluating the performance of all the pure policies. Besides, in (D.1), we also take the maximum over all agents [n] and all steps h [H], which aligns with the definition of single-agent BE dimension.
Furthermore, in the definition multi-agent BE dimension, we need specify a set of distributions D = (Dr hε|H] over S' x A. We consider two classes. First, let Da = {Da he(H] { denote a class of probability measures over S x A with Da = (d(s.a))) (+) (s, a) E S x A), which contains all the Dirac measures that put mass one to a state-action pair step h. Second, given the set of pure policies IIP" we let Dn {DILA (e( denote a class of probability measures induced I[ as follows. For any E I[Pur, when all the agents follow π on the true MG model, they generate a Markov chain (sh, an he whose joint distribution is determined by denoted by 1rt Then, for any h E [H]. we define DIT,I {p E A(S x A) p(-) (s an) = -), π E 11Pur), i.e., DIL denotes the collection of all marginal distributions of (sh, an) induced by pure policies.
In the following, to simplify the notation, we denote
dimMABE (F,E) min dimmABE (F, DA,E), dimMABE(F, =).
(D.2)
The following theorem shows that, when F satisfies realizability and completeness (Assumption 2.3), for general-sum MG with finite multi-agent BE dimension given by (D.2), its multi-agent decoupling coefficient (Definition 2.4) is also bounded. In other words, Assumption 2.5 holds any general-sum MG model with a low multi-agent BE dimension. As result, the class of MGs with fi- nite multi-agent BE dimensions is a subclass of MGs with finite multi-agent decoupling coefficients.
Theorem D.4 (Low Multi-Agent Agent BE Dimension C Low MADC). Let K any integer and let F be hypothesis class under the model-free setting, i.c., a class of Q-functions. Assume that J satisfy the realizability and completeness condition specified in Assumption 2.3. Suppose that F has a finite multi-agent BE dimension d = dimMABE 1/K), then with the discrepancy function g00.s given
19

---

Published as a conference paper at ICLR 2024
in (2.4), the multi-agent decoupling coefficient of F satisfies dMADC O log K), where O()
omits absolute constants.
Proof. See $F.1 for a detailed proof.
Combining Theorem 3.1 and Theorem D.4, we obtain that MAMEX achieves a sublinear Ondd / n +nH R² /K Klo TT,6) regret for function classes with a finite multi-agent BE dimension d. It remains to see that that function classes with low multi-agent BE dimensions contain a wide range of RL problems. To this end, we prove that the eluder dimension (Russo Van Roy, 2013) of the function class F/ is small for all h E [ and E [nt,, then F @ F F has low multi-agent BE dimension. Function classes with finite eluder dimension contains linear, generalized linear, and kernel functions (Russo & Van Roy, 2013), and thus contains wide rage of MG models. On these MG problems, the model-free version of MAMEX achieve sample efficiency provably.
Theorem D.5. Suppose F satisfies Assumption 2.3. For any i E [ni] and h E [H]. let cimm (Fx (1) denote the eluder dimension F(()) which is special case of the distributional eluder dimension introduced in Definition D.2. That is, dimg (F()) (e) e) is equal dimpa(F - -/ Da, where
F(() -
( = {g: = fi f2, fi, f2 E F and Da contains the class of dirac measures on S A. Then, the multi-agent BE dimension defined in (D.2) satisfy
diMMABE (F,E)
max max (fimg(F())) E). he[H] iE(n]
Proof. See $F.2 for a detailed proof.
Multi-Agent Bilinear Classes Bilinear Classes (Du et al., 2021) consists of MDP models where the Bellman error admits a bilienar structure. On these models, Du et (2021) propose online RI. algorithms that are provably sample-efficient. Thus, Bilinear Classes is family of tractable MDP models with general function approximation. the sequel, we extend Bilinear Classes to general- sum MGs and show that such extension covers some notable special cases studied in the existing works. Then, we prove that multi-agent Bilinear Classes have small MADC, thus satisfying the Assumption 2.5. Therefore, when applied to these problems, MAMEX provably achieves sample efficiency.
Definition D.6 (Multi-Agent Bilinear Classes). Let V be a Hilbert space and let (:- and || lly denote the inner product and norm V. Given a multi-agent general-sum MG with a hypothesis class F satisfying Assumption 2.3, belongs to multi-agent Bilinear Classes if there exist H func-
P such that the Bellman error of each agent can be factorized using W(() and X₁,- That is, for each i E [n]. E F(O), 19,he E [H] N, x' E I[pur, we have
tions (w/(0) F(() x l[pur + / for each agent E [n] and {X, 1[pur + V)
E (s [fn (sngan)) an) -1( (shsan) E (s (o (futil5 Th4T [s])
= (w (f, (F())a0 (0.0)) Xn(')))
(D.3)
where y (0,0 (,((),tt (1()) is the best response for i-th agent given that the other agents all follow π. Here, the function f(),ulth is the fixed point of (1) (le
i...
M M0 (1)
(D.4)
Moreover, require that (w/() Xn Xnhaej satisfy a regularity condition
sup
[ $1,
sup vem), (emm
|| [ (f. S Bw.
(D.5)
TETIM [
where By is constant.
20

---

Published as a conference paper at ICLR 2024
In this definition, for any E Il and f F())
(0) (Sh, 0h) - h (8h, oN) - EerwPa(d ss) (fn+1( (6', Th+1 (=16))
is the Bellman enror of f at (sh, aA) for evaluating policy on behalf of agent i. On the left-hand side of (D.3), we evaluate such Bellman error with respect to the distribution induced by another policy r. Equation (D.3) shows that this error can be factorized into the inner product between W and x where both ( only involves (f, π) while x only involves x'. Thus, multi-agent Bilinear Classes specifies family of Markov games whose Bellman error satisfies a factorization property.
Furthermore, recall that the best response न (f).f maX V= is attained at some pure
policy, thus we have μ())== E IIP"r. Under Assumption 2.3, the fixed point f(aa in (D.4) is guaranteed to exist and belongs to F.
F, 3] and X = - Xr The complexity of the multi- agent bilinear class essentially is determined by the complexity of the Hilbert space V. To allow V be infinite-dimensional, we introduce the notion of information gain, which characterizes the intrinsic complexity of V in terms of exploration.
We define X, (T)
Definition D.7 (Information Gain). Suppose V is a Hilbert space and X C V. For >> and integer K 0, the information gain yx (e, X) is defined by
K Σ
YK (E, x) =
max log det I+ EEXE
DKTK
The following theorem shows that multi-agent Bilinear Classes with small information gain have low MADCs.
Theorem D.8 (Multi-Agent Bilinear Classes C Low MADC). For a general-sum MG in the multi- agent bilinear class with hypothesis class F, let 7x, = Σ 7x (E, X,)) be the information gain. Then, Assumption 2.5 holds with the discrepancy function g(t),s given in (2.4). In particular, we have
dMADC S max {1,81² 7k (x (1/(KBW),
where Bw is given in (D.5) and R E (0, H] is an upper bound on Σdx Th-
Proof. See $F3 for a detailed proof.
Now we introduce some concrete members multi-agent Bilinear Classes, which are general-sum MGs with linear function approximation. In single-agent RL, linear Bellman complete MDPs (Wang et al., 2019) assume that the MDP model satisfies the Bellman completeness condition with respect to linear Q-functions. We extend such model to general-sum MGs.
Example D.9 (Linear Bellman Complete MGs). We say Markov Game is linear Bellman com- plete MG of dimension d, if for any step h E [H] there exists a known feature Φn : S A + Rd with (| a)ll < for all (s E S A such that Assumption 2.3 holds for linear functions of on. In other words, the Markov game satisfies Assumption 2.3 with F(() C ( 8 E Rd ||0]|a < dg for all i E [n] and E [H), where do > is parameter.
is easy to see that Linear Bellman complete MGs belong to multi-agent Bilinear Classes by choos- ing
(f. = =,, -in (1) where O fnd satisfies that [(8,, 0T T. an), and w satisfies that?
(x(T)) = E, (Ō(sk, an)l E Rdd
(1)) on (Sn, an) (1) (sp, an) + E.r ( (f ) Thanell 8'))
= =700 =T00(((++))) (
'I' there multiple 0 satisfying the requirement, we break the tie arhitrarily.
21

---

Published as a conference paper at ICLR 2024
Then, we have X3 S V fo R² 1lol22 1) for all h E [H] and Bw = =2vd. It can be shown that the logarithm of 1/K-covering number of J is (og(K)(L/K)) Ö(d), and the information gain can bounded by
H
H
7K (k K = Σ 7x 7x(1/ K X,)
S
Tk (x(1 (x/4/, O(Hd).
h=1
where O omits absolute constants and logarithmic factors (Du al.. 2021; Wang et al., 2020b). Thus, by Theorem 3.1, MAMEX achieves a OndHH + nH It2 /K log [MP ndHf2 re- gret. For the single-agent setting, comparing to the state-of-the-ar O(dH VK) regret when R = (Zanette al., 2020; Chen et al., 2022c), our result matches their results terms of d, H and K with an extra factor [I[Pur] in the logarithmic term. Note that when the pure policy set of i-th agent selected as some particular policy classes such as log- linear policy
A (To To(: (: 8) Softmax(() (0 (1s )), |10 1, 1IV( S 1, E ER*
select cover by
e - ( 0. [0./s] e, |0112 1, R.
Zanette et al. (2021) prove that the logarithm cardinality the induced covering (मH : 0 E θ is bounded by Ön d and then MAMEX provides a (((d H² V + nddl2 regret.
In partieular, as one of the examples of Linear Bellman Complete MGs, Xie et al. (2020) consider similar linear structure for two-player zero-sum games.
Example D.10 (Zero-Sum Linear MGs (Xie et al., 2020)). In a zero-sum linear MG, for each (s, a, b) E S x A x B and h E [H) we have reward ra rn a, b) E [0, 1]. and there is a known feature map S A B Rd. H known vectors 0n Rd and vector of d unknown measures vd and 8, a, b) = (0ss a, b) ps (-)-
14 (M Ja S such that || : 12 S 1|0a|l Vd. (S)]
Th a, b) = (0s, a, TT,,,,
On, PPa(
Zemo-sum linear MGs is special case of linear Bellman complete MG with two players and do 2H Vd, and our algorithm provides O(HHH
I))(( regret by choosing R H and the fact that 1o (1/K)= = =(d). The previous work provides a 2( sublinear regret (Xie et al., 2020) and a (dHH//2 information theooretic lower bound (Chen et al., 2022d) for zero-sum linear MGs. Thus, our regret matches the lower bound in terms of d, has a higher order in H compared to Xie et al. (2020) and an extra factor log [[[pr]] Again, we can adopt the class of log-linear policies with policy cover, which leads to log [[[pr (dz)). Thus, MAMEX yields ((dH3 + d H*) K) regret.
D.2 MODEL-BASER RL PROBLEMS
Sun et al. (2019) provide a complexity measure - witness rank to characterize the exploration hardness of the model-based RI. problems. In the following, we extend the notion of the witness rank to MARL.
[0, 1] denote a class of discriminators and let F be hypothesis class such that the true model, denoted by f*, belongs to F. We say multi-agent witness rank of general-sum MG is at most d, if for any model I F and any policy π E [ there exist mappings (X,, I[pur + R = and {W, F H
Example D.11 (Multi-Agent Witness Rank), Let V (Vr, : S X
R Th=1
max (Be VEVa
Ee' (-len ( on, s')) (W Xn(=)),
-
(D.6)
Kwit ((ess (lan.)))) - Ey' (* (1on,
h+ (s')] (O) (D.7)
(0), for all h E [H]. where swit is parameter. Here, VitLy is the value function of associated with agent i under model f. Moreover, these mappings satisfy the following regularity condition:
sup
[[a(=)|| 1,
sup hE(MM,EET,KE(
[ (f)ll & Bw
he H Tel
22

---

Published as a conference paper at ICLR 2024
Compared with the single-agent witness rank (Sun al., 2019), the policy in the mapping X (T) and the expectation (x,,,.,) )orr in (D.6) and (D.7) can be an arbitrary pure policy instead of the opti- mal policy T of the model f. This stricter assumption is essential for general-sum MGs because are interested various equilibrium notions and each equilibrium can be non-unique. The following theorem shows that model classes with small multi-agent witness ranks have small MADCs.
Theorem D.12 (Multi-Agent Witness Rank Low MADC). Let F be class of general-sum MGs whose multi-agent witness rank is no more than d. Then, for any f E F, we have dMADC = O(Hd) ((d//wi), where dMADC is the multi-agent decoupling coefficient of f*
Proof. See $F.4 for detailed proof.
This theorem shows that the multi-agent decoupling coefficient is upper bounded by the multi-agent witness rank, which shows that the class of MG models with finite multi-agent decoupling coef- ficient contains models with a finite multi-agent witness rank. Hence, many concrete MG models such as the multi-agent version of factor MDP and linear kernel MDP all have finite multi-agent decoupling coefficients. Therefore, applying Theorem 3.1 to models with a finite Multi-Agent wit- ness rank, the model-based version of MAMEX achieves On K / + nH VK) regret with witness rank d. Note that for the model- RL problems, our regret does not have the term because the discrepancy function g(3), in 2.5 is independent with n² When applying our results to the single-agent setting, Theorem D.12 provides similar regret result as in previous works (Sun et al., 2019; Zhong al., 2022).
Another example of model-based RL problems is the linear mixture MG (Chen et al., 2022d), which assumes that the transition kernel (s' s, a) is a linear combination of d feature mappings (de(s', 8, a) )))ieed)) i.e. (s(s' 8, 0) = Ei= 0s0s(s', s, a), where a is a joint action.
Example D.13 (Multi-Agent Linear Mixture MGs). We call one general-sum MG a linear mixture MG with dimension d, if there exist h vectors {6, E IR )eE(H)))))) and known feature ő(s' s, s,a) Rd
such that |l0nll I vd and Pa(s' s, = (0h. (fs' ss a)) for any state-action pair (s', 8, a) e S S x A.
The following theorem shows that a linear mixture general-sum MG has a finite multi-agent decou- pling coefficient. Thus, MAMEX can be readily applied to these models with sample efficiency. Theorem D.14 (Multi-Agent Linear Mixture MGs C Low MADC). For a linear mixture MG with dimension d, we have dMADC = Ö(dHR*), where R is an upper bound on Σ Th-
Proof. See $F.5 for a detailed proof.
Chen et al. (2022d) provides minimax-optimal OdH regret for two-player zero-sum MGs for Ta [0, 1]. Now choose F, {0,, E ]Rd). Combining with Theorem D.14 and Theorem 3.1, and the fact that log(BB(1/1g)) ((] = ((Hd) (Liu et al., 2022a), MAMEX achieves a Ond /K + mdHH) regret, where set R H. Compared with their regret upper bound, when applying our
result to two-player zero-sum MGs by choosing n = 2, the leading term of our regret O(dH*VK) matches the minimax-optimal result in terms of d and K but with an extra multiplicative factor H
E PROOF OF MAIN RESULTS
E. PROOF MODEL-FREE VERSION OF THEOREM 3.1
Proof. We first consider learning Nash equilibrium and coarse correlated equilibrium.
NE/CCE First, by Assumption 2.3, for any pure joint policy u, there exists function f(),, e (7()) satisfies that it has Bellman error with Bellman operator (5), for any pure purejoint policy v, i.e.
T ()
(0).
f(( (1).0
(E.1)
J441
23

---

Published as a conference paper at ICLR 2024
Hence, (/ 1,00 Jnel is the Q-function of the agent when all agents follow the policy v. Thus, have
( (s, a)] = Es (ss (0 (s, (Q)"" - (p). 1ii, (p) = Er Bssnppaatsss 11
(E.2)
Also, denote fl arg argsu))eF()) V.y (f) the optimal function with respect to the regularized value ((0,a()) for the pure joint policy and agent i. Now we have
Benat Voon (p) (1)k - (FU).. U, 111 }] = Ennoo
(f)
sup SEF(
max Ellel
sup 8EFO
(E.3)
The inequality holds because of the property of Nash Equilibrium Coarse Correlated Equilibrium. Then, since the best response (8).k.) is pure policy, we have
max E xx(- eller
sup [OO.(S]
JEFO
p( =
sup
SEFO
2 E Eunusti [rt (p) - n/ (1,x-1 (F(0),) (1,0)t1((((0)) ,0, -,,, 1sk -
(E.4)
where v E TT (())* (T((), (-1),)) and π (f)kkt is the best response given the action of other agents π. ((-)),k Thus, combining (E.3) and (E.44, we can derive [v(i), fo.. (D)
vemplts (ycbh (e)) Evnar
[ (0))- (03,01((((1))))) (p(0))) u, T 11 -) (19.M-(FFO (0,0,,,,-11-111
$ B/ unuutthan
(E.5)
Now we provide the concentration lemma, which shows that the empirical discrepancy function (() (f, n, 7lok) is an estimate of the true discrepancy function Σ g(0) (f,
Lemma E.1 (Concentration Lemma). For any [K] pure joint policy म, and (5*)/=) be executed Algorithm in the first ls - episodes, with probability at least 1 - 6,
k-1 E Il that
(0) 1 ( 1
1
Σ 8=0
2 - -coucc
4
where Econe max(O log( HK max4e(m) (1/ [Tpur /8)), H) and
H
(),T))== = Σ
Eiss ((sn - (1,0 (sh,))))))))))
h=1
Proof. See $F.6 for a detailed proof.
In other words, if we define the event as
El = 1O0k I (f, (f, n 2:b)
Σ 2l0 (f,
2 Econe, Vf E F(), n E I[Pur (K7]
we have Pr(&)) 2 5. Note that the Eoone contains log( [og[[[[ur|/ 1/8) the logarithmic term, which arises from our policy-search style algorithm.
Lemma E.2 (Optimal Concentration Lemma). For all index i E [n], all æ E I[uu and function f(), E F such that (f), f(0.. = =f(t).s with probability at least 1 - 6, we have
I (,(0) ( -,, 11k) Econc-
24

---

Published as a conference paper at ICLR 2024
Proof. See $F.7 for a detailed proof.
In other words, if we define the event as
& { [n], π E 11 L (p()), T S Econch, have Pr[E2}
Lemma E.2 shows that the empirical discrepancy function T,()), n, (1,,71kk) is small if the function f and the policy и are consistent, i.e. f(0.a Now by (F.5) and Lemma F.2, for any E [n], under the event &g.
1
E Buuptthe [p)
E Ex (((..
V(O) peh (p)
-Eunat
E Buplttin
v(Ohe sius (p)
Ex
vr(t)ee Per. (p)
+Bennt
[v Rag (on
B B
((()(())
(a)
By (B.5) and Lemma E.2, under event Eg, (a) can be bounded by
(a) S n/B vmplt)) (00))-1(((())) u, 111h-1) BuBu
[r,0),A- , (1b-11
(E.6)
S Meonn - BB (00lA-(((r))) u, 1 2(.k-1)
(E.7)
Now by Assumption 2.5, on the events and Eg we have
K
Reg(K) =
(p) - --(0 (0))
k=
1=1
1P Pemgattinn [V()+(o)] BRNNT (p)))()))
K
T) [(0) u, (1:6-11
Mecone
k=
(y1hhin - E Eowet ((())(o))))
+ E EuwoT
(E.8)
Now since flo." arg max fe with respect to the regularized value, under the event &s we have
f (w( - (L. (f, (f is the optimal function
v(0), fro. (p) (1, (FFhi, ,u, 1ik-11 2 vith (0) (0.001 u, -lik-1),
then we have nL (0) (f(0),) U. 1l 2 0 and by 17 S 1,
nL ((t) u, 11 < v (p) fa.r (p) + mp 7 (1kk-1
u,
R + MEcone < 2Econe:
where the last inequality follows the Lemma E.2. If we define
I Ri) (f0.0 u. 11b-11-- = 1(0) (f u. 1
u. 1.b-11 < 2Ecnne }
and the event
1 Ea = (= Vi [n], I 11)))A-1(( rik-11 I, 11), ( 1
we will have Eg C E2. Since the policy &k that algorithm executes is sampled from n then the sequence { that is defined by
100, 7er. (p) (()):(p)
T)Li2scone (1))))--1 (ft0.. u, - 2
Yp E
(v(0, fer.ch (p) - v(0).(
n 2co0m (0).k_((())s' s* 7 ,l1k-1))
25

---

Published as a conference paper at ICLR 2024
is martingale difference sequence. Now by Azuma-Hoeffding inequality and Y2 I R+ 2Econe S coone with probability at least å we have
E pooi (0) v(). 20 (Frhh ; ,2, 1,, 111k-11
- (vith fir.ch for.ct (p) vp):((p) -- (Fisst ,5 ((,r
< OEcone v K). (E.9)
Define the event & the (F.9) holds. Now by choosing 3 = R vK and taking the union bound over the event & E2, Eg and Eg, with probability at least 46, we can get
Reg(K)
Neanne nBBott [1
20, 11 + B [v (o)] fins
Eownt [rronroo)
NJEcon MBBur ( , 21, 1 + BunnT
[v(0), fiss (0)
-Eowst (voomcoo))
Becone (0 (friie (kt,,i + v(0lis
prn.c (p) - p00ic* (0)) +O(nEcone VK).
(E.10)
The first inequality holds because of Eq (E.8). The equality in the second line holds under Lemma E.2 (event &g S &). The second inequality is derived from Azuma- Houma-Hoeffding' inequality (event Eq). Now using Lemma E.1 and MADC assumption, we can get
K
(b) < - - ΣΣ
Σ
(
(0.c Posset (p) -(())(( + 4nvK coon
4
i=
S nu dMADC + 6dMADD H + 4nv KEconc-
The second inequality uses Assumption 2.5. Now the regret can be bounded by
Reg( K) S nvK dMADC + 6dMADCH + 4n K Econe + O V K
OnEcone K ndMADC + mddMAD K).
Hence, we complete the proof by noting that Econe = R log ),,))-
CE By changing the best response the strategy modification, can derive proof for Cor-
related Equilibrium (CE). We simplify the notation of strategy modification as dx(((()) u(-1) as (V)). Now we have
100-t-((F0) [/() (p) (0,0- (F01., u, -1,,,,,,, 16k-1)] Pro.o
Exwaa
sup
SEF())
1(0 (n) fEF()
max E, uNut
sup
(E.11)
di
The second equality holds because of the property of Correlated Equilibrium. Now we have
)x))))())))))))))))))))))))))))) [n] FEF()
max E
sup
V ((())(e))))) (tieetu)()) nb 11 di((), 7 112-1))
max Eunge
(()))))))))) neEone))
max Eynrh
(E.12)
9:
26

---

Published as a conference paper at ICLR 2024
The first equality holds by f())))))) E F()) in (E.1), and the last inequality is derived from Lemma E.2 and (,(v) is pure joint policy. Then, by combining (E.11) and (E.12), we can get
max B poorecto (p) - Eunxa
[v fiu. (e)
[ (iMMM-((P))) (Pohi , 11 )).
cJononc
Hence, we can upper bound the regret of the agent at k-th episode as
max Bun
(() (0)
(p)
= max Bungi
pinnectos [0)
((h
-max Eungr
(iohorlo (0)
BUwxx
v Pio.o (0) Bunnt /yll (p) Eunnt (1lou(o) Pro.
6:
(f 1
11:k-11 + EUNTT
(6) fos. (0)] Benxs (p(0
1]econe
The rest of the proof is the same as in NE/CCE after (E.7).
E.2 PROOF OF NODEL-BASED VERSION OF THEOREM 3.1
Proof. We first consider NE/CCE.
NE/CCE Denote f(),a = argsup,ez (f) as the optimal model with respect to the regularized value (7(0).t (f). Since for model-based RL problems, the empirical discrepancy function I(ff, म. r) and g(9),=(f. (f, T) independent with policy x, we simplify it as L(f,7) and (())))))) Then, from the definition of regularized value function ())) (f), we have
(Vl0 feoS (0) -T,00000- 10000--11(P))) (F(), 1 )
EEwT sup SEF
(()0(1) ult ENww
2
max
sup (
(E.13)
SEF
The inequality holds by the fact that nh the NE/CCE of the regularized value function (00,a (ʃ). Now since the best response (t),kit is pure policy, we have
sup (() [n]
Bx 0.6
f Ellpor
JEF
E B
sup ((N
fEF
E ui ( (p) nI(t)t- 11
(E.14)
Thus, by combining E. and E.14, we have
E Bungttinn [ ( - Evnay 1
I ( -l:k-1) (fri-----1 - Euu (00))-((F()e (1 1
(E.15)
Now provide concentration lemma for model- RL problems.
Lemma E.3 (Concentration Lemma for Model-Basee RL Problems), With probability at least 1 1 for any 1o E [K]. f E F, for the executed policy {{*]k=] in Algorithm 1, we have
1 -ikk,,lkk- lik-1) [,(),k 11, 1:k-)
-
(0sss)) + Keoney
(E.
where Keone max max log HBr(1/K), H), where By (5(1/K) is the 1/ bracketin number the model class F. We also define the event &s as the situation when (6. holds.
27

---

Published as a conference paper at ICLR 2024
Proof. See $F.8 for detailed proof.
By Lemma E.3, for any [n),
B ungltt) (p( - Eu [vthw(p))
Bngdliin [ [()h)(()) Bunst V jiss (0)
+Buwst [yeher (ioiicoo) Eunst (plh (E.17)
(a)
Now substitute into equation (E.15),
(a) S n (f", - )1:k-1) - BBut (10)k-1(f(0))) ;
= Enatt ( - (1((0)--(((()))) , (11k-11
(E.18)
Hence, combining with (E.17) and (E.18), get
E Bnglo. [v(O:(oo]
- E Bengy
(p))
S (a) + Bonan (iono (e)] - Eunat (
I Exnst (n flik-1) - ((ttit + v(0
(p) (p) - -v(00
fiis
(E.19)
By summing over it E [K] and I [n]. the regret can be obtained by
Reg(K)
B (1 " 22 W. (Foh,
11(0)) , + Ro.0 -VW.((p)
v(0, 70.
(E.20)
Now want to Azuma-Hoeffding's inequality to transform n² to executed policy çh. To achieve this goal, note that by Lemma E.3, under event &g, we have
1 lik ((), ((T0), (i0g),,7ikk -lik-1)
Koone-
(E.21)
Moreover, since Fl).v achieves the maximum value of the regularized value function ((),a (() (- (p) ( (f* - 11 we have
10.--111* - (1)k-1 1(()))1((()))))))) (1 > E Bong(s) [V/S)((o] Exnop
[(()))) fla.e (p)
2 - R 2 Keonne
Thus, if we define
c/0.0 (160)-1 ( ((0, (((t), - -11b-11)
If 1(1 (f-,,11k-1)) flik-1)
[0),6-1 (B)) -lik-, SE
have |C((),) < Keone bounded under event Eg. Then, with probability least 6. (().)) = b
(f* 1 ( - (0) (f0)), (f,,,,, Then, we can apply Azuma-Hoefiding 's
inequality transform the expectation the executed policy Ç*
K C Reode
Evert
(1),0 Reouc
(Keono log K).
(B.22)
1=1
1=1
28

---

Published as a conference paper at ICLR 2024
Now by taking the union bound of Azuma-Hoeffding's inequality and event &,, with probability least 1 1 20,
Reg(K)
x
(L" ( 11, (.) (1(0)
(0)k-1
-1tk11) + (
Riol
(p) ((0)(p))
K
E Buwgh Mhiooone
v(t)ar (0)) (p) (2))
[=1
K
M
(eaisol)) visss (0)) +((Niioonc:
1=1 km1
(b)
where the first inequality holds by (E.20), the equality holds under event Eg, and the last inequality holds by (E.22). Then, by Lemma E.3, under event &s, we have
(b) (f*,
+ v(t)e Protet (p) - ((()55 (0)
"
ΣΣ
Σ
+ 1JHccone + V Pea.c (p) -(7+** (0))
i=1
Then, by Assumption 2.5, (b) can be further upper bounded by
K
g00. (FW:s5 + Weonn + v(i,i
fos (p) - v00,5 (p)
(b)
smi
T1 dMADC + GodMAADH
S nn K Keoone
(ntoone v K IdMADDV + ndMADClf).
The first inequality holds by Lemma E.3. The last equality holds by = 4/VK. K. Finally, the regret be bounded by
Reg(K)= S (b) ((Nscome) OnViconnc V + MdMADDV K + ndMADCH).
Thus, we complete the proof by noting that Keome = O(H)
Correlated Equilibrium Similar to model-free problems, we only need to replace the best re- sponse with strategy modification.
E Besr v(O) (p) -2),),,, 11 ((fi)- (
Exnrr sup [())(N)
/EF
max Eywrt sup p(indae))) /EF
91
The last equality uses the property that ot is CE with respect to the payoff function sup (()..()) Then, since 1 E F, can further derive
Exnay
((()) Rit.o
(p) mL (()x) (70, , 11)
> max E Euog 4;
(((0))))))())))
max Ex
E.
(y (0) (1
(1),k 1(, (ik-1)]
(E.23)
The second equality holds by the property of CE. Thus, have
max Ep [ (()0(())) (p)] - Ep [V (0).0
fro. (p)
1 (1A--11 (0-11(((x111111 111--11
E I (t) (ft),e ,lik-1).
(E.24)
29

---

Published as a conference paper at ICLR 2024
Hence, combining with (E.23) and (E.24), upper bound the regret of the agent i at k-th episode as
[p)]
Buunn ( (p)]
max E unnk 6
max E BUNNT ((o)e (iisiaates (ronacto
-Bensh [p))
d:
Vilhor (0) Buwath fio.o (0)] + Bunnt (yooi [polocoo] - Bunnt [riouuco)
=max E Boogl
(
1|Econcc
BB L (F6)), (1
+ E EuNn
Fis. [p)] Beuxx [r(iherp)].
The rest of the proof is the same as NE/CCE after (E.15).
E.3 SAMPLE COMPLEXITY RESULTS
can utilize the standard online-to-batch techniques to transform the regret result in Theorem 3.1 into the sample complexity result.
Corollary E.4. Under the same setting as in Theorem 3.1, with probability at least 1- when 2 Ô (( n 2 n²d dDdMADD F3 .e-2) if we output the mixture policy Tout Uni((f+"Ne<()) (e(())
the output policy Tout E-(NNE, CCE, CE).
Proof. See $F.9 for the proof.
Corollary E.4 shows that MAMEX sample-efficient for learning all three equilibria of general-sum MGs under general function approximation.
F PROOF OF THEOREMS AND LEMMAS
F.1 PROOF OF THEOREM D.4
Proof. The proof follows Proposition 3 Dann al. (2021). First, we provide the following lemma in Dann et al. (2021).
Lemma F.1. For any positive real number sequence 21, .. Tn, we have
E T4 EE ix
S V logn.
Now denote E, dimMAnE E). We fix i E [n], and ignore both h and i for simplicity. Also
denote 2 Ex, [ and eh 2 "n 1(2 > e}. where di (1 T (1),=* Ifr E F We initialize K buckets Bb, BKKK and want to add element e, k.k for
[K] into these buckets one by one. The rule for adding elements is as follows: If ex 0. we do not add to any buckets.
Otherwise go through all buckets from BR to Bk 1 and add ef to Bt whenever
Σ
( < (ex k.
L
A.k into the bucket 1/. Then, for S S by 1, we have (e kkk S
Now assume we add en Eosk- (e Thus,
K
K
K
Σ Σ
(
(e
R.
(F.1)
R
RE DEIUii 1.
Am
Now note that by the definition of e-independent sequence, for the measures in Bj, { .... & is g'inddependent from all predecessors æk ...... n 8-1 such that g > 6. (We can choose
).
30

---

Published as a conference paper at ICLR 2024
6' = Ch c for enough small e such that / Thus, from the definition of BE dimension, the size of each bucket cannot exceed Eg. Now by Jensen's inequality, we can get
LE,, (eh (2 I and E' >
e by k.k
> 6.)
2
K
K-1
K-1
K
Σ
(e 22 Σ i Σ
Σ
Σ
E
Σ
B
E
SEB
jml
(F.2)
where the last inequality uses the fact that |B/| have
I Egg. Let vi EeEBy (c) ). By Lemma F.1,
2
2
K
R-1
iE
E
E
h
Ec + Gog K)
Ch
6.8
#E
B
BA
+E[K]\BR
(F.3
Hence, combining (F.1), (F.2) and (F.3), we can get
1/2
Σ
ch s
Ec(1 log K)
Σ
by
(ch
WE
[E[KVBB
k=1
1/2
Ec log K)
(ep s.kk
Now by the definition
hh
20.k I[e > {} and the fact that [B]] S Eg, we can have
K
ΣΣ
k. hh
HKK
h
kk
k=1k=
H +
HKE+
HK]
Σ
h
h=1
sE[K]]
Then, by (F.3), we can further bounded it by
H HKe + min E, HK)
k-1
1/2
Σ
E1 + log K)
ΣV
k=
H K k-1
1/2
< HKE + H (1 K)
ΣΣ>
(ch
(F44
The last inequality uses the Jensen's inequality Now we can use a similar technique in Xie et al. (2021). Define ())))))s)))))) a) = f (s, - EarwPa(les)) (Thii (s', (,),,)), x (-1 s))). Then, we have
Egrnp (11 (s1)) Ex+
(Ct(sn - 1 The (sn+1)))
Ex
(6', ()) m (sn, - Egr (hit
Σ (s,a)))s)))
Eg
Hence, we can rewrite the regret of the k-th episode as
H1
Egg~p [Uf(01, v(0)=* (s1)) Ex
Σ
- (s)
(F.)
31

---

Published as a conference paper at ICLR 2024
The last inequality uses the fact that Then, substitute into the definition of (0, can get
Exrop (1 7 (s1))
V(O** (s1))]
H
E
Σ (s,
Es t (h (5',
( - -r%((a)))
L=
H T 10) )f%) = Σ
ck h
where the first equality holds by the definition of Mg. the second equality holds by decomposing the value function to the expected cumulative sum of the reward function, and the last equality derived by the definition of en
Now we can get
K
Reg( K)
k.
k=1 h=1
H K k-1
1/2
< lIKE + Hin HK}+ + (E:ll 2og K)
(ex (exth)s)
(FF)
h=1k= k= 1=1
The last inequality holds by (F.4). Now by the definition en the basic inequality Vab S pa + b/ for μ O, derive Reg(K)
s.k
S
En 1(1 Th (8).at
{fh)) and
H
K
Egg (I (1)) )Fh))
x HKK + min HH, + p. (E.H. 2log K) +
H
K
Exs (1 (1- (1),
) )(n)
< HKe + (HE, HK} + n (EcH 2log K)
h=
The last inequality holds by (B[X))² < B[ Thus, by choosing
1/K, K, we can derive
H
K
R-1
(I-Th Wha' )(h))
Reg(K)= < H + HEI,K + ((EiKK H 2og K) +
E R=
h=
==1
H
K
K-1
I 6dMADDCH + udMADC +
Σ μ h=1
E
(1-T ((h))
k=1#=1
where dMADC = max H log K, 1, = (F,,iIMAAE(F,///A/ log K). The last inequality uses the fact that log K and H 1.
F.2 PROOF OF THEOREM D.5
Proof. For any policy x and i E [n]. assume oz,,"., 8_m is an e-independent sequence with Ure ((),)FF where 8z, 1.y. Sem Da, i.c. 6z. Dirichlet probability measure over S A that dr, ò(s.a) (-). Then, for each j E [m]. there exist function fs E F( and policy nd E II such that I(T T()))
respect to Utempe F F(i).a
> and
VE (RR T().mm (2p)) E. Define of a() Pha 1 by Assumption 2.3, have lh E F C Fn. Thus, 1( (z)(1 & and v Ep 10% (zp)) < e. Thus, by the definition of eluder dimension, we have dimg (Fr,e) e). Hence, for all and policy n,
(Fnn 2 m max max dimpE [E[H] se(n)
U TETT
F ().m -r.A.E)
which concludes the proof.
32

---

Published as a conference paper at ICLR 2024
F.3 PROOF OF THEOREM D.8
Proof.
First, by the elliptical potential lemma introduced in Lemma G.3, if we define As, - =e +
Exe nk, . for any ( E 2r we have
K H
H
K Σ
ΣΣ min {I. 1 A } k=1k=1
1 log det 1+
Tk,n = 2nK(E,
(F.7)
k=1
Now denote En,h el Ex=1 (x(TT) (xa Similar to Section F.I, define (r/)) (r)))0(
(s, ExwPP((-aaa ( (5', ,), th+1 (:1 (()))) E [[-,, then we can have
H
ENIog (110 - (0,,a* ($1) Exa
Then, we can substitute the definition of (r1))() and derive
Es Earop
(5). (s1)) - v())=* (s1)
H (dh(s,,)) Ee m (8)) -rh (s,a))
= E
-==1
Σ min (11r (f#, x²) ) w (Putinn 1(00"* [ .22
Then, by min < 2Rmin( 1}, have
Reg(K)= = Bair (Jf( v(nt (01))
min ( w/ (ptt)t what Xu Mi
(xx(t [1]
x 2R
k=1 h=1
2R
K H
Σ
min (1x - w// (patii "M Xx 1xn((
k= h=1
(1 (11xxa073)
s1 +1 +1 11(1118000 begh ( =1))
(F.8)
The last inequality is because = 1183 + 11( 11- for any event. Now we decompose the (F.8) into two terms A + B, where
A = 2R Σ min { (1000 (pt x²) w ( (,00' Na
Mo / 11 ( (|xxactt
$1
(F.9)
#
min (/ ( 1000
1000))) Xa(xt)))))) 11 1
B 2R
>
(F.10)
Now we bound A and B respectively. For A, we can use Cauchy's 's inequality and get
K
2
(f+.
[1xx(=>)\>z3) I[llxa(T"\lzi $1}
Ex.
< 2R
wh (F* x²)) - (Palinn
min
{ 1
k=
(F.11)
The first inequality holds by Cauchy's inequality that (X,
||
33

---

Published as a conference paper at ICLR 2024
Now by the definition ER,h = =l + Ex=1 Xx((T))x(TT))) we expand the term || ( x7))
_h (fulonn* .2(00=") A1linn as
[ ( .-=) - -w," ppllnrt :0000
= - ,- wh'0 (pulomm -atoaa 112 + Σ ( (f",
-wh" (pllie su0san 1, ),
1/2
1/2
Σ ( , who (pulonn -(00a"
Nn (T*)) 1//
SVEBBw
The last inequality holds by Va da+b- S va+ Vb. Then, we can get
K
H
wh/1 (petont 1000)= Iaaa min (xx(TT) 11s2h 1}
(5 )
k=1h=1
1/2
Σ kw/l (5+, ,/ w/ (pulihrt ,((()=*) X,
2 2VBBw* +
min (1xx((())) (1> Mas. 1 s A₁ + A2.
(F.12)
where A1 and A are defined as follows:
H Be
1/2
1/2
A
ΣΣ h=1
min (1 (T))) 1122.
h=1
1/2
( x - -w 1 (pultrnt
sHe sratt Xx(TT)))
A2 =
1/2
ΣΣ
(in
h=
Now we bound A₁ and A2 respectively. First, for A,, using (F.7), we have
A S AAKHBB ()
Then, for A2, we have
K 1-1
1/2 V2Tx(e,
(w ((",T*)) 1100-Whh (yfill
A
K k-1 ()) (f+)(((
1/2
=
==1
The equality holds by the definition of g())s and the definition of multi-agent bilinear class (D.3).
Then, since Vab I op + b/ μ for any μ O. we can further derive
A2 < 2Rμ 27k X2 x)+ + 2Rμ
el.. )*)
Now by adding A₁ and Ag and combining with (F.11) and (F.12), we can finally get
K
h-1 1
A 5 2R(A1 + Az) s v (4KHBB (R + 8R² (x x) +
1
e
K A-1
< 32RBB + +x((, + μ 8R= +
34

---

Published as a conference paper at ICLR 2024
Now have complete the bound of A. For B, by (F.7), since 1fx: 1} I minf1, know that
K H T
K H
ΣΣ
>
>1}
min
{1, 1 1 S (y,
(F.13
k=1k=1
k=
h=1
Thus, by the definition of B in (F.10), derive
K H
B
E
> >1} 27k(e,
1=
Now note that Reg(K) S A + B, then by choosing
1/32RK Biy and dMADE =
max (,, X) we can derive
Reg(K) s A A
K k-1 ΣΣ k=1s=1
s 32RB (7 p. TR
g0)) (f,, m+)
k-1
+3)x(e,,)) - 8R Tkle, x) +
e
k=1==1
K
$ GdMADDH + pdMADD +
( (f* ,T)).
k=
The last inequality uses the fact that dMDDC 1, H 2 1. Hence, we complete the proof.
L
F.4 PROOF OF THEEREM D.12
Proof. In this subsection, we give a detailed proof of Theorem D.12, First, similar to the perfor- mance difference lemma in Jiang et al. (2017), we have
(0).at 1.f
(s1) - ((0,** (81)
Esiro
-Ez [0(0)= (s1, - Exp
(6) (sn, and
A
1=
E
(o (sh,
r/ (sh, an)
an)
Q (8411,
(F.14)
The last equality holds by splitting the term. Now, since
[1(t).+ (s (S1+1, an+2)] = Exx (v(().>+ (Su+1) = Exi E p (188)aa)
(((),
W+is (+++))]
E,
(F.15)
we can rewrite (F.14) as
1(0)=* (i1)
Espop
(51)
1,f
H1
(())* (Q (s))an) an) - (1) (1) (sh, an) PI (na Ntis (suttl)
E,
K
(1())s (E PP (a(-amaan)) Bent (Hon,aw)
E
(F.16)
35

---

Published as a conference paper at ICLR 2024
Then, combining (F.16) and the definition of multi-agent witness rank (D.7), derive
(((t)= 11st (s1) v/(1),0' (s1)
K
H
min R. I(Wa Xx
Rivi
km Am
min
R, 10 X,
(411xx(++9)) $1 + +1 25 2 21)).
Riwit
(F.17)
Now note that
min {I, (n (M >1 S 2d
+ K
D(s).
and I(x > 1) & min (1,x2)
we can derive
H
ΣΣ
> > > D(
(F.18)
k=1h=1
Then, combining (F.17) and (F.18), can get
V.ppe (s1) 1/(0+** (s1)
B ~p
R
K
H
min {1,
Xx
(1III $ +1 (1))) > 11)
Nwit
1= 1=1
min 1, X. (WW. zI)) + D(e)
R
Kovi
(Wa( min II, 11x M1 +D(s)HR.
< R
(F.19)
Kwiit
(A)
The last inequality uses the Cauchy's inequality (X, Y) S ||X|||||||| and the fact that xr xr-1(x S 1} & min 12, Further, by the definition of Σk, we decompose the first term as
1/2
(A) Kiwit
ΣΣ
(1
212
Σ (Wh Xx
min { I, (T
K
H
1/2
VeBw +
Σ
(x())) {
kWW
min { 1, (T (TT"
Kwit
hml
The second inequality derived by the inequality |W - Bw and V S v bb. Now sum over & [K] and h [H), we get
K
H
1/2
(A)
VeBw +
Σ
KWW(F* X,x=))))
min {I, ( }
Kowit
k=
h=
K
BeBw min {1, Ilsso
Nwit
k=lk= h=1
(X)
K
H
1/2
Σ
min { 11 ( (=>))
(F.20)
Kwit
Amm
36

---

Published as a conference paper at ICLR 2024
First, try to give an upper bound for (X). By Cauchy's inequality and (F.18), derive
1/2
1/2
(x) S Nowit
BBW
min { (, s
k= h=1
k= h=1
HK=Bw
HKKBB D(E)
+D(
(F:21)
Kiii
On the other hand, for (Y), we can bound it using Cauchy's inequality that Ea, vab / 6),
1/2
K
(Y) - 1
(ΣEΣ X.
Σ
min 1 [
Kwii
A= h=1s=1
h=1
D(E)H
ΣΣΣ
Kwii
k=1h=1=
The last inequality holds by the definition of D(s) in F.18. Now by the definition of multi-agent witness rank D.6, we note that
x max (s (s you (1E (( (+1sn)aa)) VVVE
Bs SaatrrPh. ((aaa) (ssh, sh+1)]
(1E P - Esn, 12 (1 (s(k an: sh+1)
27
< max E (n) ~ wEVn
27
E (n) w
max DEVi
(BantI~Phn Ba ((s.))))) (1 (u(s) ao. (n+1)
(182)an)) -
The last two incqualities use Jensen's 's incquality. Hence, by the definition total variation distance, can get
( (x(T))) & TV (Pr,,* Sh, an), 8h, an))
(F.22)
S 2D (T (h,, (x), Sh sh.aa)))
(F.23)
where the (V(..) denotes the total variation distance and DH denotes the Hellinger divergence. The inequality (F.22) holds by the fact that uSs an. Sh+1) [0, 1], and the (F.23) holds by the relationship between TV distance and Hellinger distance. Then, we can substitute the inequality (F.23) and get
K
H
(Y) Kiwit
(())
ΣΣ
(s (n) 2D (Ph, Sh, Pn.- (- 8h, an))
H
K
H
S JRR-
Bas J Dj (Pn.st sh, an), Ph, (. shy an))
μR
Wiit
(F.24)
Hence, combining (F.19), (F220), (F.21) and (F:24), can get
Reg(K)=
Σ E Esinp
(())a* 1,f*
(s1) v(0)=T (sr)
< R A HR
< R(X +Y) HR
< / + HR))HR
+RR² 2D(e)H 1
Σ
B
Bl y D (Pn.s 8h, an), Pr.j) oh, sw)))))
p
1=1
(F.25)
37

---

Published as a conference paper at ICLR 2024
Now by the definition of g(0)s of the bosed problem in (2.5), choosing Wwit// / and dMADC= we can get
wit
k R (#
Reg(K) & 6dMADDH + p. dMADC
g(0,s
k=
complete the proof by D(wwit/H (dd)
F.5 PROOF OF THEOREM D.14
Proof. First, we fix an index E [n]. Similar to Section F4,, we can get
ES Rsypp
[(0)=* 1,
(81)
v0)== (51)
Ohij (sh, an) -rh (s): an) - EastiPPa (1bs, ((t)
N+ an+1))
1=1
- (PPPttt - Esn p (1on (0)) h+1, (sh+1]]
E Nk P
k=1
1h=1
Honte I V
Σ
(0n,5=
OW)
Rti (s))ss)
where the last equality is because of the property of the linear mixture MG. Now denote
Wa(f) R(Oh.s 0%)
(F:26)
Ss (n' |s, a) (1)x h+ (s')ds)
x=( = Ex
(F.27)
R
Then, we have [[a(I))I S 2vd, (s, x)]l S and
Espop (v (s1) v(0, (s1)
min (Wn)(WW(())) Xn( m²")) R}.
Now similar to Section F.4, if replace X (T+ (n rk, **), from (F.21) and (F:24) with Bw
2 dR we can get
Eg rop [v()=r (51) ( (s1)
1=
& Xa(P))
< HKREAdR + D()) pk (D(
ΣΣΣ
μR
(F.28)
where D(E) = 2d 2og (s+K), Moreover, by (F.26) and (F.27), note that
(Wh(F*), X*, r²))
(0n,,* 87 /
(. (1)a" @n(s' s, It1.f. dss
Er
(BensimP (+(omma))))) E an h4i (9
(1)xx
22 1 Ollxx drv(Pnggt sh, an |Pnss (. sh, an))
< Ex
2V2RDH (P sh, an)][PP,.- shy an1)
38

---

Published as a conference paper at ICLR 2024
Hence, from (F.28) and Jensen's 's inequality that (B[X])² & B[X²), we can have
Eaipp 1.5² [Vi.,=" (s1) - 1/ v/(0.5* (01)
Reg(K) S
k=1
< HK ReAdR² + D()))HR++ uRt 2D(e)H
K ΣΣΣ
E (s [81ē (Pn, 8h, an), as), Ph, 8h, shhaa))))
RR
h=1s=1
By the definition of discrepancy function g0). in (2.5); and choosing ε = 1/HKd, dMADC = (R) Ö(HdRt), can derive
K k-1
Reg(K) S 4R D(1/HKK)HRR + HdMADD
eiss (fk (fk, x*))
K A-1
S 6dMADOMI + HdMADD +
(
Hence, we complete the proof.
F.6 PROOF OF LEMMA E.I
Proof. The proof is modified from Zhong et (2022). Define Wj.h be the filtration induced by {sf at Ti (6),k 1... , air ji=)) First, for h [ e [m], e F(0 and II, we define the random variable
1 (h, = (Ju(S)) -h) -r 12 a - (fh+1 shiil ) -(T (f)(s) af)) (sh of)) (fo+1(5/ Sh+zll | )
By taking conditional expectation of Y, with respect to of she get
E[y fh, W3,1 = Es <: ((fa - -he (f))(sn,
and
{ (1) (h, (1 | S (b, Wy,n)
where 3R 2 (5 ( h
(0) (0) (sh a - (fn- (5/+ Sh+ ( is the constant upper
bound. Denote Z, y, (h, (+ E , (h,, f.c²) | Wjn1 with |Zyl S 4R². By the
Freedman inequality, for any 0 17
. with probability least 1 1 5,
k Σ
Var Varly (h, Wjn++ 1og(1/5) Σ
2 0
j=1
Ø=1
log(1/5) E((y (1) f. W,,++
0
Σ
3
7
1=1
W3,1 log(1/5)
0
2R E(y, (6) Σ
(h. (k.
"
1og(1/6)
By choosing 7 = min
we will have
4R2
VERV Σh
B|X ( (h.f.)
Σ 73= 0 0
R Σ E(y E (h,,.(*) Wy,1. log(1/8) + R² log(1/5)
J=1
39

---

Published as a conference paper at ICLR 2024
Similarly, if apply the Freedman's 's inequality with Eÿ= Z,. with probability at least -28,
& Σ 23 = j=1
Σ (h,
+ R² 1og((11))
Denote the p-covering set of FF()) as Cyco (p), then for any f E FO0 E II,",, there exists pair Cras (p) such that
( (Ju(sh: an) - 10 (sh, (n) ( ") Shtz(. 8h+1)1
[sh an) Tf (sh, an) (fh41 :) Sh+2(- shtza)i 3p for all (sh, on sh+1) E S x A x S. Now by taking union bound over Cr (p), we have that with probability least 1 8, for all Czca (p),
10 (h.
j=1
-
R
Σ 1=1
B (h, Waale + 122
(F.29)
where . = 2log (p)1/5) S 2og (ogg(HKe (KN
Now note that for all f E F 11 we have
H k-1
(,,
1-1
Σ
Σ
- -r) (5,, - S.42( ( 8)41)))
(T ( of)) (0 a)) (fa+1 (5/ (s/ S44t s)4))))
Σ (fh(sh ob) - (fn-1(5h+1))))))))
s(z))))
inf (T (f) at) - r (0) (s/. a/)) - (frt Setil 1 1)))
M
= - (s, (1
Then, by (F.29) we can get
k-1
ΣΣ
(1 1 S 4T.00-1 (
1=
Now similar to (Jin et al., 2021a), by the definition of p-covering number, for any k [K], f e F(0)
and ( E par
н k-1
ΣΣ
ELY
(h, f.C) W3A1 < 61.A (f,G,
+ + 1. HRkp).
h=1j=0
Now since $/,, ag ~ ç we can have
k-1
k-1
Σ
400 (f,Ct)
Σ ( (h, f, f(ch) WyAd
1=
1=0
< < (0) k- 1 S* 1: +(H) HRkp)
We complete the proof by choosing p = 1/K and choose Econe = O(HRL++HHH = O(HR2)).
40

---

Published as a conference paper at ICLR 2024
F.7 PROOF OF LEMMA E.2
Proof. First, for any / E F(() and π E Nlau we define the random variable
(h. ( o/)) - ~r (o a/) - (fă+1 (o/+1:))) :) Thti(: +/11)))² (s) a() - -h (s), aa)) - (5+t25//42))) Thtil 5 s/)+2))
Then, by similar derivations Lemma E.I, we can get
EIQ [: T) W3,n] on [Un T(), (s)) an) 1) 0,
E| E[(O,) ff))² W3Al S 2R f. x) Wga..
Then, by Freedman's inequality, with probability at least 5, for all elements in f E Crre (p), we have
Σ
9 fm
E (h, f.x) W331
==0
k-1
Σ
B
(1,
W3ake + 1P:,
1=0
then we can have
k-1
5=
Thus, by the definition of Crc (p), for all f E F( and π E 11,5t, we have
Σ
of (h. Rkp).
Thus,
k-
((.k))
Σ
inf
Σ
s SO(HR)+ H ((HR)).
fEPO) 1=0
h=1
Thus, we complete the proof.
F.8 PROOF OF LEMMA E.3
Proof. For simplicity, we first assume finite class. Given model f F and E [H], we define X = -log Pr.y (s)4)15),9))
Thus,
H k
L 1ir (ik) (0,
x
(F.30)
h=
Now we define the filtration 9 as
9j = o a
Sy a.))
Then, by Lemma G.I for all
F, with probability at least have
k
log
exp
2
x
h.f
Gj
+ log H F1
j
41

---

Published as a conference paper at ICLR 2024
Now decompose the first term at the right side
E
exp
x 2 h
9--1
log hr (
16 anp) Ph.s- (8/++1 18/ a//)
Gj
Ph (5/41)
8 an)
(ot, og we Pa (lo2
Gj
Ph.s- (8/44 22 0%)
VPP.r 1h Ph. (
(of aa more DD (IP s 1 a ( 5%)1,1))1
Now by the inequality log S 1, we have
k
&
Σ
x
-
Σ j=l
2 (s), (a (P ah. (s/ 1. af)aa]
1=1
1 +1 log F1/0)
Cog, (g) )
Di((Pn 14 ( 1 cb))
+ log H (1)8).
Sum over E [H] with (F.30), we can complete the proof by
H
(() + Reone
h.f
where Keonc H log HoggHHFFF// (I/8)) For infinite model classes F, we can use 1/ /K--baccktiin number (x(1/K) to replace the cardinality [F] (Liu al., 2022a; Zhong et al., 2022; Zhan al., 2022b).
F.9 PROOF OF COROLLARY E.4
Proof. We provide the proof for NE. The proof for CCE/CE are the same by replacing the NE- regret to the CCE/CE-regret. By taking the minimum of the index of agents rather than adding them together, we can modify the proof of Theorem 3.1 and derive, with probability at least 1- 8.
K
max 1l0 1E
(p) - -(0,* (11) Sō
HT VR
dMADC VK
dMADC H
+
+
K
K
Hence, by choosing K = -000(11 + dMADD) =² + dMADDH ..MADCH..-.) x-t)
with E < 1, we have
max (1(0.1 (p) v(t))ton())) iE(m]
max 1ia (p) -00++ (0)) EE|n
Se.
where the second inequality holds from Tont Unif(((*)) )eE(())
Hence, Tout is e-NE.
n
42

---

Published as a conference paper at ICLR 2024
G TECHNICAL TOOLS
We provide the following lemma to complete the proof of model-based RL problems. The detailed proof can be found in (Foster et al., 2021).
Lemma G.1. For any real-valued random variable sequence {X*]kejk] adapted to filtration (Gx (E(K), with probability at least 1 - 8, for any k [K], we can have
X
log Blexp( F--1] 1|| + log(1/6).
In the next lemma, we introduce the Freedman's inequality, which has been commonly used in previous RI. algorithms. (Jin et al., 2021b; Chen et al., 2022c; Zhong et al., 2022)
Lemma G.2 (Freedman's Inequality (Agarwal et al., 2014)). Let [Z kE[K] be a martingale differ-
ence sequence that adapted to filtration (Fis {F&)kE[K]] If 1 S R for all & E [K], then for E (0, R with probability at least we can have
K Xx=
K En>ELS E|
FR-1]+ log(1/8)
1
The next elliptical potential lemma is first introduced in the linear bandit literature (Dani et al., 2008; Abbasi- Yadkori et al., 201 and then applied to the RL problems with Bilinear Classes (Du et al., 2021) and the general function approximation (Chen et al., 2022a; Zhong et al., 2022). Lemma G.3 (Elliptical Potential Lemma). Let f>x J be sequence of real-valued vector, i.e. Ik E Rd for any l E [K]. Then, if we define A, = el + E TAoT we can get that
Σ min (1. (1m:1112-1) < 2 log
det(AA++)) det(A1)
log det 1+
(1+1 mack
Proof. The proof is provided in Lemma 11 of (Abbasi- Abbkoii-addkori al., 2011).
H COMPUTATIONAL EFFICIENCY
Since the normal-fome game is defined over the pure policy space, the size of this game can be exponentially large, which makes the algorithm not computationally efficient. Actually, the compu- tational complexity of this oracle depends the type of equilibrium.
For CCE, the oracle can be approximately implemented by mirror descent (Wang et al., 2023), where the time of calculating (==) depends the number of iterations. Hence, the computa- tional complexity of this oracle depends only on the number of iterations rather than the pure policy
space [TT To be more specific, by replacing the optimistic value function v(())= in Algorithm 4 (DOPMD) of [1] by the regularized payoff function in 3.1, one get approximated CCE by mirror descent using FTRL analysis. The sampling procedure in Line of DOPMD can im- plemented by Langevin dynamics (Karagulyan, 2021) as long regularized payoff function.
obtain the gradient of the
However, for Nash Equilibrium, calculating the equilibrium is PPAD-complet. So MAMEX is computationally inefficient for learning NE.
43


Reviews:
[{"review_id": "DAxYGX8Hlj", "reviewer": "Reviewer_pi75", "summary": "The paper discusses the challenges and solutions in the context of Multi-Agent Reinforcement Learning (MARL) for general-sum Markov Games (MGs) with a focus on efficient learning of equilibrium concepts such as Nash equilibrium (NE), correlated equilibrium (CE), and coarse correlated equilibrium (CCE). The authors address the complexities of using function approximation in general-sum MGs, which is different from single-agent RL or two-agent zero-sum MGs.\n\nThe paper introduces a unified algorithmic framework called Multi-Agent Maximize-to-EXplore (MAMEX) for general-sum MGs with general function approximation. MAMEX extends the Maximize-to-Explore (MEX) framework to MGs by optimizing over the policy space, and updating the joint policy of all agents to achieve a desired equilibrium. It combines an equilibrium solver for normal-form games defined over the policy space and a regularized optimization problem for payoff functions over the hypothesis space.\n\nThe paper defines a complexity measure called the Multi-Agent Decoupling Coefficient (MADC) to capture the exploration-exploitation tradeoff in MARL. MAMEX is shown to be sample-efficient in finding NE/CCE/CE in MGs with small MADCs, covering a wide range of MG instances, including those with low Bellman eluder dimensions, bilinear classes, and low witness ranks.\n\nThe paper's contributions include the development of MAMEX, a unified algorithmic framework for model-free and model-based MARL, and the introduction of the MADC complexity measure to quantify the exploration difficulty in MGs with function approximation.\n\nThe paper aims to provide a foundation for addressing the challenges of efficient MARL in general-sum MGs with a unified approach, covering both model-free and model-based methods.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally clear.\n\n- The authors provide a novel efficient framework to compute CCE, CE, and NE in general-sum MGs.\n\n- The authors propose a novel interesting complexity measure MADC, which captures the exploration-exploitation tradeoff for general-sum MGs.\n\n- The final regret of the algorithm depends on the introduced MADC measure.", "weaknesses": "- The main weakness of the paper is how to perform the policy evaluation step. It seems to me that it will be computationally expensive to construct an estimator for each pure strategy for each player. Can the authors explain this more in detail? How big is the policy space of the pure strategy? If we are replacing the set with a 1/K-cover how much are we losing?\n\n- There are some typos in the paper (e.g. page 8 solveing )\n   \n- It is not easy to understand the paper without looking at the appendix. For example, it would be better to include the definition of $\\{l^{i,s}\\}_{i \\in [n]}$ in the main paper. \n\n- How do the authors compare the regret results with previous SotA algorithms?", "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": "", "extra_scores": {}}, {"review_id": "SUKfSgFQa9", "reviewer": "Reviewer_cnZv", "summary": "This work studies online learning in general-sum Markov games with general function approximation, and focuses on the centralized learning paradigm. They extend the regret decoupling idea that has been used for the single-player case, and give a new notion, called multi-agent decoupling coefficient (MADC) to quantify the sample complexity. They propose a (conceptually) simple centralized algorithm called multi-agent maximize-to-explore (MAMEX) and show that it is able to achieve a regret upper bound related to MADC.", "questions": "See the weakness part.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The work provides a very general and conceptually simple algorithm to deal with centralized multi-agent reinforcement learning. It nicely extends the prior work on the single-player case. \n- The writing is quite good.", "weaknesses": "- To me, there lacks motivation to study equilibrium learning in a centralized manner, particularly when it does not consider any global value optimization.  Equilibrium seems to be a concept under which selfish players cannot make unilateral move, and is usually used to characterize the steady state when every player plays independently and selfishly. However, if the players are in coordination, perhaps they can aim higher, such as higher social welfare. Can you give more motivations on centralized learning NE/CE/CCE without considering social welfare?  A related questions is: why is the Reg_{NE/CE/CCE} a meaningful measure for the quality of a centralized MARL algorithm? \n- There are some previous works also on quantifying sample complexity of multi-agent RL, including Wang et al. 2023, Foster et al., 2023, Chen et al. 2022b. In this work, the comparisons to these previous works are all about the \"simplicity\" of the objective. The comparisons on \"sample complexity\", however, are missing.  How to compare the new notion MADC with the complexity measure proposed in these works? Do they have any relations?", "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": "", "extra_scores": {}}, {"review_id": "K0FyKQRlgr", "reviewer": "Reviewer_JQUp", "summary": "This paper extends the decoupling coefficient from the single agent setting to the multi-agent setting for general-sum Markov games, termed MADC. The authors then propose an extension of the Maximize-to-Explore family of algorithms from the single agent setting to general-sum Markov games to solve for a variety of equilibrium concepts. By doing so, they construct an approach that relies only on solving an optimization problem and computing the equilibrium of a normal-form game. The authors prove their approach achieves sublinear regret (i.e., exploitability of the equilibrium) where the MADC appears as a constant.", "questions": "**Note I am increasing my score conditioned on some discussion of the limitations of scaling this approach to practical sized games (see my last follow-up comment) as well as including a discussion of a comparison with PSRO in related work**\n\n- Pure Policy: I was confused by the definition of pure policies. You state that the set of pure policies is a subset of each agent's local policies, but this is still to vague. I assume a pure policy is a deterministic mapping from states to actions, but can you clarify / confirm this?\n- Definition 2.4: It might help to state an intuitive definition in words as well, i.e., the $\\delta$-covering number is the minimum number of balls of radius $\\delta$ required to cover a set.\n- Equation 3.1: Can you state somewhere that $\\eta > 0$ is a hyperparameter that you are introducing?\n- Can you please bring Algorithm 1 into the main body?\n- You say \"We prove that MAMEX achieves a sublinear regret for learning NE/CCE/CE in classes with small MADCs\", but haven't you proven sublinear regret regardless of how large the MADC is (as long as it is finite, Assumption 2.7)? Do you have an interesting example in which MADC is infinite?\n- Practicality: If you are going to consider all pure joint policies in a corresponding NFG (called meta-game in PSRO), why bother with function approximation of a value function? Why is it important to have the value function when you're already going to compute an equilibrium of this enormous game (assuming computing an equilibrium is more expensive than reading all the payoff entries)? Why not just deploy the equilibrium policy and be done rather than continue to iterate to learn the best approximation to the value function? In other words, if I have an oracle to solve an NFG of the size you suggest, I can just ask it to return the equilibrium policy assuming the entries in the payoff tensor are the *actual* Monte-Carlo returns of the pure-policies in the Markov game. Is there some setting you have in mind where it is cheaper to approximate a value function and avoid calculating returns for every joint pure policy? Sorry if I'm missing something, but it feels like something big is being swept under the rug here.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors propose a general approach for learning a variety of equilibrium concepts across Markov games. They also define the multi-agent decoupling coefficient (MADC), and show how it relates theoretically to convergence rates to equilibria. All of this is done assuming the difficult setting with function approximation (either the transition kernel or the action-value functions are directly modelled).", "weaknesses": "I would like to see the authors compare / contrast their approach with PSRO [1, 2]. PSRO also consists of two components (single agent optimization to compute a best-response and computing the equilibrium of a normal-form game), applies to Markov games, leverages function approximation, and can learn CCE, CE, and NE.\n\n[1] Lanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\" Advances in neural information processing systems 30 (2017).\n\n[2] Marris, Luke, et al. \"Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers.\" International Conference on Machine Learning. PMLR, 2021.", "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": "", "extra_scores": {}}, {"review_id": "PS2Lf4efXn", "reviewer": "Reviewer_hiyJ", "summary": "The paper provides a general recipe for solving multi-agent reinforcement learning through the notion of decoupling coefficient. The framework allows for various function approximations and encompasses both model-based and model-free approaches. Theoretical results show that if a game enjoys finite MADC then there exists a centralized algorithm for $\\sqrt{K}$ type regret.", "questions": "1. When $n = 1$, the problems are reduced to a single agent RL. In this case, is MADC reduced to DC, or is it more general than DC? (since it is not restricted to greedy policy)\n2. If MADC reduces to DC when $n=1$, does an RL instance with finite DC imply the MG version of the RL instance also has finite MADC (and thus can be solved efficiently?)\n3. How should one compare MADC and MADMSO? We know that tabular MG and linear mixture MG have finite MADMSO and MADC. Are there any classes of games that have finite MADC but not finite MADMSO or vice versa? \n4. It seems that the current framework does not distinguish NE/CCE/CE. It seems that as long as the NE/CCE/CE equilibrium oracle is efficient, it takes the same amount of samples to find NE/CCE/CE?  As NE is a much stricter notion of equilibrium than CCE, for example, on might expect more samples to be needed (or in other words, harder) to learn NE. So are the results tight for each of NE/CCE/CE or is it an upper bound for the worst-case regret needed for finding any equilibrium?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The framework proposed provides a general recipe for solving multi-agent reinforcement learning under various function approximations, and the bounds obtained under this framework are sample efficient. I believe this is the first framework that includes both model-based and model-free methods. \n2. Compared to the previous works (MA - DMSO), the framework only requires solving a single objective optimization, which makes it much more feasible.", "weaknesses": "While I like the results presented in this paper, it is not very clear to me what the relationship between MADC and the existing measures (such as MADMSO, the single agent decoupling coefficient). I believe the paper would benefit from more discussion and comparison on that. Please see the question raised below for more details on this point.", "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": "", "extra_scores": {}}, {"review_id": "XlFgEPfgtq", "reviewer": "Reviewer_FdZN", "summary": "This submission introduces a new algorithm dubbed MAMEX which enjoys regret bounds for the Nash Regret in General Sum Markov Games with low MADC. A metric introduced in this work that measures the complexity of a certain Markov Games.\n\nVia an online to offline conversion the regret bounds can be converted into sample complexity guarantees for learning an $\\epsilon$-approximate Nash Equilibrium. These guarantees hold in expectation.", "questions": "Q1) In the tabular case or in the Linear MDP case would there exist an efficient way to implement MAMEX ?\n\nQ2) Do you think that the MADC are necessary quantities that should appear in lower bounds too ?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think that the paper's idea is well explained in the main text. \nUnderstanding which are the lighter assumptions to enable sample efficient learning in Markov Games is an important theoretical problem which matches the interests of the ICLR community.", "weaknesses": "I think that the paper should make it clearer that MAMEX is not computationally efficient.\nThis is because of (i) the equilibrium computation over the set of pure policies in step 4 of Algorithm 1 is often over combinatorial sets like for example the set of deterministic policies in the tabular setting and (ii) the sup over the function class in the policy evaluation routine.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)