Multi-Agent Meta-Reinforcement Learning: Sharper Convergence Rates with Task Similarity
Authors: Weichao Mao
Haoran Qiu
Chen Wang
Hubertus Franke
Zbigniew Kalbarczyk
Ravi Iyer
Tamer Basar
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement learning
game theory
multi-agent systems
meta-learning
TL;DR: For multi-agent reinforcement learning, we prove that meta-learning can help achieve sharper convergence rates than individual learning when the learning tasks are similar according to natural similarity metrics.

Abstract: Multi-agent reinforcement learning (MARL) has primarily focused on solving a single task in isolation, while in practice the environment is often evolving, leaving many related tasks to be solved. In this paper, we investigate the benefits of meta-learning in solving multiple MARL tasks collectively. We establish the first line of theoretical results for meta-learning in a wide range of fundamental MARL settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games, as well as learning coarse correlated equilibria in general-sum Markov games. Under natural notions of task similarity, we show that meta-learning achieves provable sharper convergence to various game-theoretical solution concepts than learning each task separately. As an important intermediate step, we develop multiple MARL algorithms with initialization-dependent convergence guarantees. Such algorithms integrate optimistic policy mirror descents with stage-based value updates, and their refined convergence guarantees (nearly) recover the best known results even when a good initialization is unknown. To our best knowledge, such results are also new and might be of independent interest. We further provide numerical simulations to corroborate our theoretical findings.

Multi-Agent Meta-Reinforcemeni Learning: Sharper Convergence Rates with Task Similarity
Weichao Mao
Haoran Qiu
University of Illinois Urhmna-Champaign weichao2011linoi. edu
University of Illinois Urbana- TrrbanaChhampagh haorang40illinon edu
Chen Wang
Hubertus Franke
Zbigniew Kalbarezyk University of Illinois Srbana-Champae
IBM Research chen. wang1 @0ibm.0iim.mmm bm. com
IBM Research frankeh@us imm. com
kalbarcz0illinois edu
Ravishankar K. Iyer
Tamer Başar
University of Illinois Jhhana-Champaiin rkiyer@ill wiweriiiliiii......mimmmmmmmiill edu
University of Illinois Urbana-Chann Chaan--Champaign basar fillinoiii inois.edu
Abstract
Multi-agent reinforcement learning (MARL) has primarily focused on solving a single task in isolation, while in practice the environment is often evolving, leav- ing many related tasks be solved. In this paper, we investigate the benefits of meta-learning in solving multiple MARL tasks collectively. We establish the first line of theoretical results for meta-learning settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games, as well as learning coarse correlated equilibria general-sum Markov games. Under natural notions of task similarity, show that meta- leat-lee achieves provable sharper convergence to various came-thcoretical solution concepts than learning each task separately. As important intermediate step, we develop multiple MARL algorithms with initialization-depa deepedddn con- vergence guarantees. Such algorithms integrate optimistic policy mirror descents with stage-based value updates, and their refined convergence guarantees (nearly) recover the best known results even when good initialization is unknown. To best knowledge, such results are also new and might be of independent interest. We further provide numerical simulations corroborate theoretical findings.
wide range of fundamental MARL
Introduction
Many real-world sequential decision-making problems involve multiple agents interacting in shared environment, a scenario commonly captured by game theory and addressed using multi-agent reinforcement learning (MARL). Existing research in MARL has primarily focused solving practice, however, one often needs to collectively solve a single task (i.c., a game) independently. evolving environment. For example, in sponsored search set of similar tasks due to the dynamically auctions 48). the advertising spaces and search results are dynamic, and each bidder with an active bid will participate in sequence of related auctions. In multi-robot cooperation [31 26). the learning agents are often first pre-trained in simplified environments and are then asked to quickly adapt to more complicated ones. In cloud computing
[53] 77). learning based autoscaling policy needs to achieve fast model adaptation to deal with varied application workloads or constantly evolving cloud infrastructures. All of these intriguing applications call for the development of intelligent multi-agent systems that can continuously build on previous experiences to enhance the learning of new tasks.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Meta-learning, or learning-to- to-learn 66 56 65, 58 is rapidly developing approach that is particu- larly suitable for learning set of related tasks. In essence, meta-learning studies the use of data from existing tasks to learn representations or model parameters that enable quick adaptation to new tasks. By exploiting the knowledge obtained from prior tasks, the meta-learner can ideally solve an unseen task using much fewer training samples than learning from scratch, especially when the tasks share some inherent similarities. Despite many empirical successes [71 [1 (26), the theoretical results of meta-learning in multi-agent scenarios are still relatively lacking. It remains elusive whether meta-learning can provably expedite the convergence of MARL, and if so, what the proper task similarity assumptions impose are. In fact, is even unclear whether meta-learner converges at all in highly non- -tatiiooi system with loosely-couplee learning agents and diverse task setups.
In this paper, we make an initial attempt toward characterizing some of the central theoretical properties of meta-learning in a wide range of fundamental MARL settings. We focus on the classic madel-agnostic meta-learning (MAML) [20] type of algorithms that aim to learn a good initialization for quick adaptation to new tasks. To study the convergence rate of MAML, an important prerequisite is to understand how the convergence of MARL algorithms depends on the quality of policy initialization. However, the convergence guarantees of most existing MARL They fail to track how the sub-optimality of the initial
algorithms are initialization-nneeeene policy propagates during the learning process, and only provide pessimistic guarantees with respect to worst-case initialization. As crucial intermediate step to meta-MARL. we need to establish refined initialization derindenn convergence guarantees for MARL. Our main contributions are thus summarized as follows.
Contributions. 1) For learning Nash equilibria (NE) in two-player zero-sum Markov games, we first propose an MARL algorithm blessed with a refined convergence analysis that explicitly characterizes the dependence on policy initialization (Section 3.1). Our algorithm runs optimistic online mirror descent for policy optimization and performs stage-based value function updates. Even when initialized with random policies, our algorithm still matches the best-known convergence rates in the literature except for an extra logarithmic term. Our algorithm and analysis appear to be new and might be of independent interest. 2) Based on such refined analysis. we show that meta-learning provably achieves faster convergence to NE when learning sequence of "similar" zero-sum games collectively, where our similarity metric naturally depends on the closeness of the games' NE policies (Section (32)) 3) For learning NE in Markov potential games (MPGs), we show that simple refinement of an existing algorithm suffices to provide inttalization-depeeneen guarantees. We establish sharper convergence rates of meta-learning when the MPGs have similar potential functions (Section 4.1) In addition, with a properly chosen policy update rule, we prove the non-asymptotic convergence of the exact MAML algorithm in MPGs (Section 4.2). despite the convoluted learning dynamics of multiple loosely-coupled agents. 4) For learning coarse correlated equilibria (CCE) in general-sum Markov we analogously start by designing an wellliiattionddpeedeeeee MARL algorithm. and then establish the sharper convergence rate of meta-learning under natural similarity metrics. 5) We provide numerical results to corroborate our theoretical findings (Section (6)
games (Section 55.
Related Work. Gradient-based meta-learning is a simple and effective approach that can be easily applied to any learning problem trained with gradient descent. The seminal MAML method [20 tries to learn a good model parameter initialization that leads to quick model adaptation. Theoretical properties of MAML have been investigated in series of works [5 66 [8 30). In particular,
17 30 have established the convergence of MAML to first-order stationarity for non-convex
objectives. [8]] has designed an unbiased gradient estimator for MAML in reinforcement learning
tasks. Various first-order approximations (20 49 17 of MAML have been proposed to avoid the heavy computation of the Hessian. Meta-learnin has also been studied in online convex optimization [21] 4 35). where regret bounds have been established under different metrics of task similarity. Another line of research [2] 5T 4T views meta-learning through the lens of task inference, where an RL policy is conditioned on a belief over tasks and perform Bayesian updates through interactions to adapt to different tasks.
MARL has been widely studied under the formulation of stochastic games (i.e., Markov games) Due to the fundamental difficulty of computing NE in generic games [10], most MARL
57
research has focused on learning NE in games with special structures (such as zero-sum Markov
games (67 2 69 3 12 68
7
72 73 and Markov potential games [43 38
76
25
22
13
78) or
learning weaker solution concepts such as (coarse) correlated equilibria
44 59 33
I6 [3]
The most relevant works are [77 72 which have studied the convergence of optimistic no-regret
2

---

learning and smooth value updates in MARL with full-information feedback. For learning NE in MPGs. [8 76 [5] have studied independent policy gradient methods and established their sample complexity results. These works have focused on learning single game in isolation but have not considered exploiting the connections between multiple games to expedite the learning process.
Most related to ours, [27 has studied meta-learning in normal-form games. Under different notions of game similarities, [27 has shown faster convergences of meta-learning in zero-sum, general-sum, and Stackelberg games. 775 has investigated no-regret learning in time-varying zero-sum normal-
we consider meta heta-le in the more generic and challenging Markov game setup with state transitions. Other related works include meta-learning for regret minimization in a distribution of games [6]] and meta-safe RL for quick adaptation in constrained
form games. Compared to [2 755,
Markov decision processes (CMDPs) under task similarity [34]. Finally, meta-learning has also been empirically applied to many important MARL scenarios, including multi-intersection traffic signal control 77], multi-agent communication with natural language [26). and multi-agent collaboration
with first-person pixel observations in open-ended tasks
2 Preliminaries
Markow game. An N-player episodic Markov game is defined by tuple G (N, H.S, (A)),, {r P), where (1) N = =1,22...,
is the set of agents; (2) E N+ is the number of time steps in each episode; (3) S is the finite state space; (4) A, is the finite action space for agent i E N; (5) r. [M] x S x Aall - [0, 1] is the reward function for agent i, where Aall = A; is the joint action space; and (6) P [H] x S x Aall A(S) is the transition kemel. The agents interact in an unknown environment for episodes. Without loss of generality, we make standard assumption 59] that each episode starts from a fixed initial state $1- Our results can be easily generalized to the setting where the initial state is sampled from a fixed distribution. At each time step h [H], the agents observe the state 8 S, and take actions ax,i A,, E W simultaneously. Agent then receives its reward Th. an). where On = (a ON.N ). and the environment transitions to the next state -h-1 Pa (-),;, a.). Let S = 5). A; |.). Vi E A, and Amax maxieN A,-
Policy and Nash equilibrium. A (Markov) policy E II, : [M] S + A(A:) for agent i E N a mapping from the time index and state space to distribution over its own action space. Each agent seeks to find policy that maximizes its own cumulative reward. A joint, product policy π = (TI...., NT) E II induces a probability measure over the sequence of states and joint actions. We use the subscript -i to denote the set of agents excluding agent i, i.e., ./A .Nf(i). We can rewrite π = (T,, π x-1) using this convention. For a joint policy π, and for any h E [H). s E S, and a E Aall. define the value function and Q-function for agent i
H
(s) = Ex] Σ h/=h
Tw asw (sh) = s), Qh,(ss = EET
Σ M=hh
Twi ((sss,aw))e)) (s = s, as = =a]-
For agent i, a policy क. is best response TT; if (".;:"-(ss) (product) policy π (m,,)=;) m-) II is Nash equilibrium (NE) if स. is best response to m- for all i E N. Similarly, for any & > 0, a joint policy क = (T) is an e-approximate NE V.TT ((s1) 2 (s1) E, E.
sup V1, Vit. (s1). A joint
Correlated policy and coarse correlated equilibrium. We define {TA R (S AY--1
+ (e))) as a (non-Markov) correlated policy. where for each h E [H] The maps from coordination device = E IR and a history of length h to distribution over the joint action space. Let गं and T- be the proper marginal distributions of ι whose outputs are restricted to A (AA) and ((A-.), respectively. The value functions for non-Markov correlated policies at step h are defined in a similar way as for product policies. Given the PPAD-hardness of calculating NE in general (II, people often study relaxed solution concept named coarse correlated equilibrium (CCE), which allows possible correlations in the policies: In particular, for any > 0, correlated
policy π = (T,, - is an E-approximate CCE if TT TT. (ss1) 2 Vi - (s1) - E, Vi e N.
Two-player zero-sum Markov game, An important special case of Markov games (two-player) zero-sum Markov games, where there are two players (N 2) with exactly opposite rewards
3

---

(1=-12) In a zero-sum sum game, we simply use V, and Q to denote the reward and (Q-)value functions for the max player, i.e. agent Correspondingly, the min-player has -r, V, and Q. For notational convenience, we denote the action space for the max-player (resp. min-player) by A (resp. B), and let = |A, B [3]. We also write their policies (TT, w2) as (1,,2) for short. In zero-sum games, it is known that although the NE policy (μ²,
may not be unique, all the NE have the same values. We use Vi, and Q to denote the NE value function and the NE Q-function. For any fixed (h, s) E [H] S and an arbitrary function Q 8 X A B - R. we may consider Qs,,,,)) as an x B matrix. Then, for any policy pair (Uu, 1%) at step h E [H]] we can write shorthand:
[uh Qui. (s) == E. Ea-nnt bo). (11)) (Q a, b)] = (uun Qun) (s);
[n] Q] (s. Bu-pa (-1s) [Q( (8, a, )), and [Qua] (s, = Eowns (41,))Q(s,, [Q(s,,)))
Given the transition function P and an arbitrary function V SS - R. we define
[P, (s, a, 6) (. [V (s')].
The Bellman equations can hence be rewritten more succinetly as
(s) [nT] 21""',, vn] (s), and (s,
(s, a, b) + [PA 1 (s,
Markov potential game. Another important class of games Markov potential games [43 39 76]. MPGs cover Markov teams (36), fully cooperative setting where all agents share the same rewards. A Markov game is an MPG if there exists a global potential function & II x S + [0, mmax that can capture the variations of the agents' individual values: Specifically, Vi E N and s S.
D (T; 4, (T -
V,, V. (s) ( (8), VT,, T. E I1, --; E I1
Throughout the paper, consider the classic full-information feedback setting 23 g
68
where the players are assumed to have exact information of the consequences of each of their candidate actions. In the case of zero-sum games, this implies that for any (h, s). the max-player and min- min-player can query [Qnvn((s,)) and [u] Qn respectively. Our meta-learning results can be easily extended to the stochastic bandit feedback setting using standard techniques as in
3 44
33 15
Meta-learning, Let G (G*} be a set of different Markov games. Each game is defined by G* (Wr S, [A:))= (r Ji=1, p*),, where we assume without loss of generality that the games share the same agent set and state & action spaces, but can have different transition and reward functions. Most of our results are established in the online learning setting where we encounter a sequence of K games (G), ..... GK) one by one. To achieve faster convergence, the learning agents should use the knowledge obtained from previous games to expedite the learning process in future games.
The underlying principle of MAML 20 is to learn good initialization such that running a few training steps from this initialization can lead to well-performing model parameters on any new task. An MAML-lype algorithm in the context of RL typically involves two nested stages. The inner stage (or "base algorithm") &p performs T iterations of policy updates optimize for an individual task Ck.
ket (,,,.t,, Vt [T].
(1)
When task G is completed. the outer stage (or "meta-algorithm"" Te learns form good initializa- tion n ++1,0 for a new task Gk+1 using all the knowledge obtained from all previous tasks:
nf A+
V'(T
"" (E "!...,,""" G*).
In this paper, we seek to properly instantiate both the base algorithm y and the meta-algorithm V for variety of MARL problems. We aim to show that proper design of the meta-learning procedure (1b, W can largely reduce the number of iterations T required to find NE or CCE in a new game.
3 Meta-Learning for Two-Player Zero-Sum Markov Games
In this section, we study meta-learning for Nash equilibria in zero-sum Markov games, where players are fully competitive. Since MAML-type algorithms seek to learn good initialization for quick adaptation, it is crucial to explicitly characterize how the convergence behavior of an MARL algorithm depends on the initial policy. To our best knowledge, such results are not directly achievable using existing algorithms. For this reason, in Section 3.1 we start by proposing new base algorithm for zero-sum Markov games that has a refined infiaaizzation-deeedeen convergence guarantee. Based on that, present meta-algorithm 2 in Section 3.2 and establish its sharper convergence rates.

---

3.1 InitializatonnDeeendeel Convergence in an Individual Zero-Sum Markov Game
Algorithm I presents our optimistic online mirror descent algorithm with stage-based value updates for learning NE in a zero-sum Markov game. To establish initializationddeendenr convergence, for policy updates (Lines 6), in contrast to the popular optimistic follow the regularized leader (FTRL) method in recent MARL policy optimization [77 [2]. We choose the negative entropy as our regularizer R, in which case the Bregman divergence DR(-)) :) reduces to the HellbackkLeiblle divergence and optimistic OMD becomes an optimistic variant of the classic multiplicative weights update (MWU) algorithm.
Algorithm I performs optimistic online mirror descent (OMD) [55 62
Algorithm I: Optimistic Online Mirror Descent for Zero-Sum Markov Games
Input:
Initial policies jı [F] x [ x S + ((A) and i: [7] H X A(B);
Set stage index <- 1, 1-mm 1. and L, f- H:
Initialize: μ4 p. ph. 1h o h and QT 0, vh [M]]
for iteration t <- 1 to T do
Auxiliary policy update: for each step h E [H] and state s E S:
A < argmax (A. 10.%% REA(A)
( [(s,))) - DR(A, P (+1s));
(-1s) + argmax 1/ (D, ((4) TT]((s,))) DR(C, 0r (1s)); ((s));
DEA(B)
Policy update: for each step h E [H] and state S:
p1(-1s) arginx (e, 107 "(.,,)))(s)>)))>)>>>>>>))))))" DR(u,p(((1)))
HED(A)
argmax (v.((1) TTQ)(s, Dalu, (-sss) MEA(B)
7
if Astart + +1 L, then
8
1TT L, 1411 - 1+ b,+1 + 111+1/H)L
9
Value update: for each [H] E S, E A.be B:
(s, + L p' fi=toon
Σ
(rn + Palkh (T+ (s)
10
T + 1; 11,- = 111, +- 1h, V/ = 11 + 1h 4h E [A]
Output policy: pan (m)(-1s) + Ei= 1 11, (-1s) and in (-1s) トΣ (11s), E
In order to establish convergence to (approximate) NE, we need to show that our optimistic OMD policy updates achieve "no regret" with respect to the value estimate sequence at each state, i.e., to upper bound 3 If we were to use the celebrated a, = H++ learning rate 332 to update the value function estimates, we will inevitably need to show no-weighted-regret guarantee for optimistic OMD, because such a time-varye varying learning rate assigns non-um -onifoofrm weights to each history step. However, incorporating OMD with a dynamic learning rate is known to be challenging and can easily lead linear regret [50]. While a stabilization technique [9] has been introduced tackle this challenge, we take different route by resorting to an alternative value update method, namely stage-bused value updates [9]. Specifically, we divide the total T iterations into multiple stages and only update our value estimates at the end of a stage (Line 9. We let the lengths of the stages grow exponentially at a rate (1+ 1/H) (Line g (79 45). The exponential growth ensures that the total T' iterations can be covered by small number of stages, while the (1 1/Hf) growth rate guarantees that the value estimation error does not blow up during the steps of recursion #+1 update rule that modifies the value estimates (Lemma 9). Compared with the incremental a₁ # at every step, maagebbased updates are more stationary and allow us to assign uniform weights to each history step. This leads to a simpler no(-average)-regret problem 47 that can be easily addressed by (optimistic) OMD.
#+1
5

---

We introduce few notations before presenting the convergence analysis of Algorithm Let rt)) denote the index of the stage that iteration belongs to. We denote by the total number of stages, i.e., 7 := (T"). For any (T, h, E [F] x [H] S, define the per-state regrets for the max-player as
regh, (8)== =
max PT (AA)E(AA TT
T. - 1/,, Qheh) 1h
(3)
The per-state regret regī.2 (5) for the min-player can be defined symmetrically (see (4 in Ap- pendix B). We define the maximal regret (over the states and the two players) as regā maxses 1,, (regg, (+)) An upper bound for the per-state regrets provided in Lemma of Appendix which is useful in the analysis of Algorithm [ We use the standard notion of
NE-gap(u, v) = Vi (sa)
to measure the optimality of a policy pair (1,, v). The intraalization-deeendeen convergence rate of Algorithm| is as follows.
is run two-player zero-sum Markov game for ' iterations with learning rate 7j S 1/(8H²) the output policy pair (H,D) satisfies:
Theorem 1. If Algorithm 7
192H
NE-gap(n, D)
max
(DR( (1s), (Ts)) + DR(PR' (1s),
T
In addition, if the players' policies are initialized to be uniform policies, i.e., (11s) 1/A and Ty (11s) = 1/B, E [F), E [H], we further have
NE-gap(ī, 768H log T log( (AB)
(4)
T
Compared to existing results 77
72 Theorem I directly associates the convergence rate with the quality of the initial policy (ūz, 2) Even when a good policy initialization is unknown and the algorithm is initialized with uniformly random policies, our convergence rate in (4) still matches the best kesttnnowwn result in the literature 722 except for an extra factor of Ollog T). When suppressing the
logarithmic terms, Theorem I
jimmediately implies that for any > 0, Algorithm taakes no more than T' = ((15//)) /s) steps to learn an a- e-approximate NE in an individual zero-sum Markov game.
3.2 Sharper Convergence with Meta-Learning
Having settled the initialization-depeee dependeen convergence in a zero-sum game, we proceed show how meta-learning can learn set of related games collectively and more rapidly. We consider an online setting with sequence of K games G (G'...., GK). ). For the max-player, let je and μ² respectively, denote the initial policy and output policy of Algorithm
1 on game G By putting
together v1, (-Is) over all (r, h, s) E [F] [H] x S, we let f [F] [H] x S - A(A) denote the best fixed policies in hindsight on G Define i* z² and wha analogously for the min-player. Let μ² = R Σx= kit and V* = k k= whit be the empirical averages of the best response policies. To ensure that the knowledge gained from previous games is useful for learning future tasks, need to impose some similarity assumptions on the games G. We consider the following similarity metric:
Σ (KL (1**)1lp²*) KL (1*+t(l²*))
Intuitively, since (u"t)re(T) fixed responses jut can be considered as an approximation of the max-player's NE policy on G In this sense, A,, essentially measures the distances between the NE policies of different games. It considers set of games 9 to be "similar" their NE policies lie in a close neighborhood of each other. We remark that there might be multiple NE policies (with the same value) in a zero-sum game, and A,,, only takes into account the NE policy pairs that Algorithm aactually delivers.
)e([T] converges to an equilibrium policy for @ when is large, the best
Our meta-learning procedure proceeds as follows: Within each game G we run Algorithm as our base algorithm I to find a NE of Gk In new game G++1 the initial policy of Algorithm is given

---

by the following meta upddtess in the outer loop 2 which essentially averages the best response policies of the previous tasks under a-greedy parameterization:
and
(5)
In particular, for any vector x E R we define its a-greedy parameterization := aax 21 to be weighted average with uniform vector 1/d I of a proper dimension, where E (0, 1/2). Since μ&a denotes set of vectors, we apply the operator [ element-wise to each of the vectors. The reason for using a-greedy is mainly technical: KT (-I1-) is not Lipschitz continuous near the boundary of the probability simplex, and a-greedy parameterization helps to stay a-distance away from the boundary. We are now ready to present our sharper convergence rates for meta-learning.
Theorem 2. In sequence of K two-player zero-sum Markov games, if Algorithm 7 is run for TT' with 1/VK as the meta-updates, we have
iterations as the base algorithm and (5)
K
19211
A A.P.
10(A + B) log 16 log T log((
NE-gap( (²)) k=1
(6)
K
T
KH2
VKH²
VK
Consequently, for any e 0, T Ō 0f (A
A+
steps on average suffice to find an vK
E-upproximate Nush equilibrium each game.
When the number of games K is large, the last two terms on the RHS of (6) become negligible, Hence, compared to the best-known results O(H /T) of learning each game individually, Theorem 2 implies a significantly sharper convergence rate when the games are similar, i.c., when An < KHI..
Meta-Learning for Markov Potential Games
In this section, we study meta-learning for NE in Markov potential games. We show that straight- forward refinement to the analysis of an existing algorithm [1] provides initialization depeddent bounds. Building on it, in Section we first investigate the sharper convergence of meta-learning in a sequence similar MPGs. Further, since there exists an optimization objective universally agreed can formulate the meta-learning problem in the same way as MAML [20]. In Section 4.2, by choosing a proper base algorithm, establish the non-asymptotic convergence of MAML in the highly non-stationary multi-agent scenario, without even imposing any smoothness assumptions as in existing works [I7 18 30].
on by all the players in an MPG (i.e., the potential function),
4.1 Sharper Rates Similar Games
To be consistent with existing results in the literature, in this section, we consider an infinite-horizon
y y-discounted reward setting for MPGs 43
[5]. A detailed description the setup provided in Appendix C for completeness. Equivalent results for the finite- episodic setting (as we defined in Section 2) can derived a straightforward way. We choose an existing state-of-the-art algorithm, namely independent projected Q-descent (15), our base algorithm (I.. Specifically, in an MPG G each agent independently runs policy gradient ascents update its own policy for T iterations:
39 76
k.t (-1s))) <- ProjA(A:) (+Is) + + ((s.)) VV [T],
T.
where Q is the "averaged" Q-function formally defined in Appendix C Let o( (+*) denote the potential function of &* Through simple refinement of the analysis in [55, we can establish the following intializatioonddeeeddneee bound for our base algorithm (7).
Proposition 1. (Theorem I in (15)) Suppose that all players in Markov potential game G run independent projected Q-descent for T iterations with a S
(1-7)*
8x N Then, we have
(( (K) 11T (+))
Σ NE-gap(zh1))
aT(1 7)2
where x(G))) is the standard distribution mismatch coefficient for Gk formally defined in Appendix C
7

---

Proposition 1 immediately implies that if we learn each MPG individually, it takes T O( Amaxi (1-7)0g2 steps find an s-approximate NE. To show the effectiveness of meta-learning we consider the following similarity metric for sequence of K games, which measures the maximal point-wise deviations of the potential functions:
K
max (*(T;; G*) (1T;; G++))).
(8)
x
1=1
As for the meta-updates, we simply instantiate as T < xx 1 1.1" which lets each agent play the converged policy in the previous game. The intuition is that after rumning T' steps on G the agents will converge to be close, the converged policy * should serve as a good starting point to search for NE in G We formally characterize such intuition in the following theorem, which shows the sharper convergence of meta-learning in a large set of similar MPGs (i.e., when K is large and As is small):
approximate NE policy of G Since (8) requires the potential functions
Theorem 3. In sequence of K Markov potential games, if 7 is run for T iterations as the base algorithm and <-,,- 1-1,T as the meta-updates, then, for any ε > 0, T = O N Nmma (amay An) steps on average suffice to find an E-approximate Nash equilibrium in each game.
k(1-7))²²
4.2 Convergence to MAML Objective
In this subsection, we study meta-learning for MPGs under exactly the same formulation as in the seminal work of MAMI. [20]. Let G = (G') } be set of different MPGs, where the games are now drawn from fixed distribution p that we can sample from. We consider parametric policy classes where agent i's policy is parameterized by 0; = {0,(ss))) E RR)SS parameterization where
We focus on softmax
To, (a:ls) = exp(Oi(a,)s))
Eates, exp(O.(a(|ss)
Let (( G)
denote the operator of performing one step of policy gradient update on game G, i.e., 0 + (0V G), where > 0 is the learning rate. The T-step MAML objective
C(0:
G
20
18
30
can be formulated as
max (T) == Ex) ( (C(... (C.)) dE@
where 8 = (f1...... , 0N) O, and the operator Ç(- ; G) is applied T times. Intuitively, MAML tries to find good parameter initialization from which running T steps of gradient ascents on any new task G leads to well-performing policy parameters.
Similar to Section 2 the MAML procedure consists of two nested stages. For the inner stage I. we let each agent independently run T steps of policy gradient ascents to update its policy parameter e(() on each encountered MPG. It is known (Theorem of (78) that T = O(1/e²) steps will find an E- approximate NE for each individual MPG. For the outer stage (2), MAML directly performs gradient ascents with respect to the meta-objective (9). The gradient of Frr can be written in closed-form as
T-1
(II ())) (O()
v Fr EE)D(G)
(10)
t=0
detailed discussion of MAML and its instantiation in our problem are provided in Appendix D Most importantly, Appendix D shows that both the policy gradient ( and the policy Hessian
(24(0) can be written closed-form, which allows us to construct unbiased estimators of (IO) from samples. Despite the fact that the learning agents update their policies independently in an intertwined multi-agent system, our next result shows that the MAMI. updates converge to a stationary point of the meta-objective (9) in asymtttiic manner. A key step of the proof is to prove (rather than assume, as in existing works [17 30) that the meta-objective Lipschitz smooth in the policy parameter 0. The smoothness constant can also be written in closed form (Lemmal 14p.
Theorem 4. Suppose that the agents run independent policy gradient ascents with softmax parame- terization each encountered MPG as the inner stage, and perform gradient ascents w.r.t the MAML objective as the outer stage. For any E > 0, K (1-7)a²
ANLF iterations of MAML updates can find a
policy 6* such that || Fr )| < where LF is given in Lemma 14 of Appendix D
8

---

Meta-Learning for General-Sum Markov Games
In this section, we consider learning coarse correlated equilibria in general-sum Markov games with no assumption on reward structures. Similar Section we start by developing an initialization- dependent algorithm, followed by investigating the sharper convergence of meta-learning.
Our base algorithm for learning CCE also uses optimistic OMD with stage-based value updates. Detailed descriptions are deferred to Algorithm 2 Appendix(Equue to space limitations. Algorithm follows similar structure Algorithm []] but the output policy ा of Algorithm 2 is no longer state-wist average policy and instead a correlated policy 3 33
For any correlated policy л,
use the notion
CCE-gap(T) == max Vi (1.-"((1) - (1. VEN
to measure its distance to a CCE. Let denote the total number of stages of Algorithm 2 Similar to zero-sum games (3. for any (T, h, [7] x [H] x S, we define the per-state regret for each player
i N
prdd
(s) = T
1
Σ j=
T-l Rho - Th (h.rhhh
max (AA))
LT
where Th is player i's Q-function estimate at stage We define the maximal regret (over all states and players) as regī, max,es max4eN ; The iniiaaliaation-deendeen convergence rate of Algorithm is established in the following theorem.
Theorem 5. If Algorithm is run general-sum Markov game for T iterations with learning rate 1j > O, the output policy ā satisfies:
3 CCE-gap(a) nT
(1)), 3 iEN..ES
In addition, if the players' policies are initialized to be uniform policies (h,,(-s)) 1/A,, Vie and v chosen as r == H 2/333//-1///// - 1)-2/3, then we have
CCE-gap(#) 12N 3 H log T log Amax
(1I)
T
Compared existing results, Theorem 5 directly associates the convergence rate with the quality of the initial policy #. With uniform initialization, the convergence rate in (TT) has a slightly worse dependence on T than the best known result O( /T/9//1 [77]. Such deterioration is due to the potential lack of smoothness condition for optimistic OMD that directly connects the stability of policies to the stability of utility functions (Lemma 18 unlike in optimistic FTRL. Although we believe that our rate (TT) can almost certainly be improved via refined stability analysis, we leave the tightening of it to our future work as it would be departure from the main focus of this work.
Let * and * respectively, denote the initial policy and output policy Algorithm 2 on game Ck For player i E N, by putting together 7 -, (-Is) over (r, h, s), we use / x XS A(A,) to denote the best fixed policies in hindsight on G We consider game similarity metric defined as
K
A
KL(T) TT (m7)), where ग.
k
The following theorem presents the convergence rate of meta-learning, which again is sharper than learning each game individually when the games are similar, i.e., when A, is sufficiently small.
Theorem 6. In a sequence of K general-sum Markov games, if Algorithm 2 is run T iterations as the base algorithm and the meta-updates के - Σ k-1
Ja, Vi E - are used with
-
= 1/VK for policy initializations, then, for any > = Ō HN average suffice to find an e-approximate CCE in each game.
3/2
A3/2 +H² )) steps on
3772
K1z2

---

6 Simulations
We numerically evaluate our meta-learning algorithms from Sections 3 and on sequence of K games. In this section, we evaluate on a sequence of K 10 zero-sum Markov games and Markov potential games with two states, two players, and two candidate actions for each player. In Appendix we further demonstrate the scalability of our methods by providing numerical results on larger-scale tasks, including a simplified version of the Poker endgame considered [27] and a ID linear- quear-quadratic tracking problem [37] with 4 cooperative players.
F
1.5
1.00
Individual NE-gap
Individual NE-gao
Meta-kcarnin NE-gap
Meta-leaming NE-gap
0.75-
NE
* 0.50
State State Hg
0.25-
0.00
250
500
750
1000
500
0.6
1.0
Iterations
Iterations
P6
(a) Zero-sum Markov game
(b) Markov potential game
(c) NE visualization
NE-gap of policies output by individual learning and meta- meta-learning in (a) zero-sum Markov games, and (b) Markov potential games. Shaded areas denote the standard deviations. (c) visualizes the NE policies of the K games in the normalized space [0, x [o, 1] to illustrate their closeness.
Figure 1:
We generate the K = 10 games by first specifying "base game" and then adding random pertur- bations to its reward function to get K slightly different games. Each of the K games is run for T = 1000 iterations. To better visualize the similarity level of these games, in Figure [(c) the NE policies of the perturbed zero-sum matrix games at each of the two states for the K = 10 games. We remark that due to the existence of state transitions, the NE policies with respect to the stage Q-functions can be more diversified than Figure T(c) Detailed descriptions of the simulation setup are deferred Appendix F
plot
We evaluate the convergences of the algorithms in terms of NE-gap. Figures [(a] and [ compare the average NE-gap over the K games between individual learning and meta-learning for zero-sum Markov games and Markov potential games, respectively. We see that meta-learning can utilize knowledge from previous tasks to attain better policy initialization in new task and converges to an approximate NE policy using much fewer iterations.
Concluding Remarks
In this paper, we have introduced meta-learning solve multiple MARL tasks collectively. Under natural similarity metrics, we have shown that meta-nen achieves provably sharper convergence for learning NE in zero-sum and potential games and for learning CCE in general-sum games. Along the way, we have proposed new MARI algorithms with fine-grained inttaaiizaiion-deeeneen convergence guarantees. Our work appears to be the first investigate the theoretical properties of meta- meta-lcarning in MARL and provide reliable justifications for its usage. As for the limitations, our convergence rate for learning CCE (Theorem (5) is slightly less competitive than the best-known results when our policies are initialized conservatively, which might be improved via refined policy stability analysis. Other future directions include further generalization of our results to alternative game similarity metrics and broader types of games (e.g., stochastic Stackelberg games).
Acknowledgments and Disclosure of Funding
This work was partially supported by the National Science Foundation (NSF) under grant CCF 20-29049; by the IBM-ILLINOIS Center for Cognitive Computing Systems Research (C3SR), research collaboration that is part of the IBM AT Horizon Network; by the IBM-ILLINOIS Discovery Accelerator Institute (IIDAI); and by the Air Force Office of Scientific Research (AFOSR) under grant PA9550-19-1-053 Any opinions, findings or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF or IBM or AFOSR.
10

---

References
[1] A. Agarwal, S. M. Kakade, J. D. Lec, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22: 1-76, 2021.
[2] Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pages 551-560, 2020.
[3] Y. Bai, C. Jin, and T. Yu. Near-optimal reinforcement learning with self- Advances in Neural Information Processing Systems, 33, 2020.
[4] M.-F. Balcan, M. Khodak, and A. Talwalkar. Provable guarantees for gradient-based meta- learning. In International Conference on Machine Learning, pages 424-433. PMLR. 2019.
[5] A. Banerjee, S. Merugu, S. Dhillon, J. Ghosh, and J. Lafferty. Clustering with Bregman divergences. Journal of Machine Learning Research, 6(10), 2005.
[6] N. Brown and T. Sandholm. Superhuman Al for heads-up no-limit Poker: Libratus beats top professionals. Science, 35966374):418-44,, 2018.
[7] S. Cen, Y. Wei, and Y. Chi. Fast policy extragradient methods for competitive games with entropy regularization, Advances in Neural Information Processing Systems, 34:27952-27964, 2021.
[8] N. Cesa- Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[9] G. Chen and M. Teboulle. Convergence analysis of a proximal like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-54) 1-338-53,,11 1993.
[10] X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):1-57, 2009.
2009.
[11] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a Nash equilibrium. Communications of the ACM, 52(2):89-97, 2000.
[12] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Processing Systems, 33: 5527-5540, 2020.
[13] C. Daskalakis, N. Golowich, and K. Zhang. The complexity of Markov equilibrium in stochastic games. arXiv preprint arXiv:2204 03099,, 2022.
[14] G. Denevi, C. Ciliberto, R. Grazzi, and M. Pontil. Learning-to-lent stochastic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566-1575. PMLR, 2019,
[15] D. Ding, C.-Y. Wei, K. Zhang, and M. Jovanovic. Independent policy gradient for large- scale Markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning, pages 5166-5220. PMLR, 2022.
[16] I. Erez, Lancewicki, U. Sherman, T. Koren, and Mansour. Regret minimization and convergence to equilibria in general-sum Markov games. arXiv preprint arXiv:2207.1422) 2022.
[17] A. Fallah, A. Mokhtari, and A. Ozdaglar. On the convergence theory of gradient- model- agnostic meta-learning algorithms. In International Conference Artificial Intelligence and Statistics, pages 1082-1092, 2020.
[18] A. Fallah, K. Georgiev, A. Mokhtari, and A. Ozdaglar. On the convergence theory of debiased model-agnostic meta-reinforeemmet learning. Advances Neural Information Processing Systems, 34:3096-3107 2021.

---

[19] H. Fang, N. Harvey, V. S. Portella, and M. P. Friedlander. Online mirror descent and dual averaging: Keeping pace in the dynamic case. Journal of Machine Learning Research, 23(1): 5271-5308, 2022.
[20] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. International Conference on Machine Learning, pages 1126-1133 1135, 2017.
[21] C. Finn, A. Rajeswaran, S. Kakade, and S. Levine. Online meta-learning. In International Conference Machine Learning, pages 1920-1930. PMLR, 2019.
[22] R. Fox, S. M. Mcaleer, W. Overman, and I. Panageas. Independent natural policy gradient always converges in Markov potential games. In International Conference on Artificial Intelligence and Statistics, pages 4414-4425, 2022.
[23] Y. Freund and R. E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29)1-2)77,,10,, 1999.
[24] T. Furmston, G. Lever, and D. Barber. Approximate Newton methods for policy search in Markov decision processes. Journal of Machine Learning Research, 17, 2016.
[25] Z. Gao, Q Ma, T. Başar, and R. Birge. Finite-sample analysis of decentralized Q-learning for stochastic games. arXiv preprint arXiv:2112.07859) 2021.
[26] A. Gupta, M. Lanctot, and A. Lazaridou. Dynamic population-based meta-learning for multi- agent communication with natural language. Advances Neural Information Processing Systems, 34: 14:16899-16912, 2021.
[27] K. Harris, I. Anagnostides, G. Farina, M. Khodak, Z. S. Wu, and T. Sandholm. Meta-learning in games. arXiv preprint arXiv:2209. 14110, 2022.
[28] E. Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optimization, (55-4)::77-235 2016.
[29] J. Humplik, A. Galashov, L. Hasenclever, P. A. Ortega, Y. W. Teh, and N. Heess. Meta reinforcement learning as task inference. arXiv preprint M.Kiv:1905.00444 2019.
[30] K. Ji, J. Yang, and Y. Liang. Theoretical convergence of multi-step model-agnostic meta- learning, Journal of Machine Learning Research, 2022.
[31] H. Jia, B. Ding, H. Wang. X. Gong, and X. Zhou. Fast adaptation via meta learning in multi- agent cooperative tasks. In Symposia and Workshops on Ubiquitous, Autonomic and Trusted Computing, pages 707-714, 2019.
[32] C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is Q-learning provably efficient? Advances in Neural Information Processing Systems, 31, 2018.
[33] C. Jin, Q. Liu, Y. Wang, and T. Yu. V-learning-A simple, efficient, decentralized algorithm for multiagent RL. In ICLR Workshop Gamification and Multiagent Solutions, 2022.
[34] V. Khattar, Y. Ding, B. Sel, Lavaei, and M. Jin. A CMDP-within-onlline framework for meta-safe reinforcement learning. In International Conference on Learning Representations, 2022.
[35] M. Khodak, M.-F. F. Balcan, and A. S. Talwalkar. Adaptive gradient-bante meta- neta-leerning methods. Advances in Neural Information Processing Systems, 32, 2019.
[36] M. Lauer and M. Riedmiller. An algorithm for distributed reinforcement learning in cooperative multi-agent systems. International Conference on Machine Learning, 2000.
[37] M. Lauriere, S. Perrin, Girgin, Muller, A. Jain, T. Cabannes, G. Piliouras, J. Pérolat, R. Elie, O. Pietquin, et al. Scalable deep reinforcement learning algorithms for mean field games. In International Conference on Machine Learning, pages
PMLR, 2022.
[38] Leonardos, W. Overman, I. Panageas, and Piliouras. Global convergence multi-agent policy gradient in Markov potential games. arXiv preprint arXiv:2106.01966 01969, 2021.
12

---

[39] S. Leonardos, W. Overman, I. Panageas, and G. Piliouras. Global convergence of multi- agent policy gradient Markov potential games. In International Conference on Learning Representations, 2021.
[40] Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, 2021.
[41] S. Liu, M. Lanctot, L. Marris, and N. Heess. Simplex neural population learning: Any- bayes-optimality in symmetric zero-sum games. In International Conference on Machine Learning, pages 13793-13806 PMLR, 2022.
[42] R. Lowe, Y. I. Wu, A. Tamar, J. Harb, O. Pieter Abbeel, and Mordatch. Multi-agent actor-critic for mixed cooperaive--ommpettvve environments. Advances in Neural Information Processing Systems, 30, 2017.
[43] S. V. Macua, J. Zazo, and S. Zazo. Learning parametric closed-loop policies for Markov potential games, In International Conference on Learning Representations, 2018.
[44] W. Mao and T. Başar. Provably efficient reinforcement learning in decentralized general-sum Markov games. Dynamic Games and Applications, 13:165-186, 2023.
[45] W. Mao, K. Zhang, R. Zhu, D. Simchi-Levi, and T. Başar. Near-optimal model-free rein- forcement learning in non-stationary episodic MDPs. In International Conference on Machine Learning, pages 7447-7458. PMLR, 2021.
[46] W. Mao, H. Qiu, C. Wang. H. Franke, Z. Kalbarezyk, R. Iyer, and T. Basar. A mean-field game approach cloud resource management with function approximation. Advances in Neural Information Processing Systems, 35:36243-36258, 2022.
[47] W. Mao, L. Yang, K. Zhang, and T. Başar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In International Conference on Machine Learning, pages 15007-15049, 2022.
[48] D. Nekipelov, V. Syrgkanis, and E. Tardos. Econometrics for learning agents. In Proceedings of the 16th ACM Conference Economics and Computation, pages 1-18, 2015.
[49] A. Nichol, Achiam, and J. Schulman. On first-order meta-learning algorithms. arXiv preprint arXiv:1803.02999 2018.
[50] Orabona and Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69. 2018.
[51] P. A. Ortega, J. X. Wang, M. Rowland, T. Genewein, Z. Kurth-Nelson, R. Pascanu, N. Heess, J. Veness, A. Pritzel, P. Sprechmann, et al. Meta-learning of sequential strategies. arXiv preprint 2019.
arXiv:
[52] S. Perrin, J. Pérolat, M. Laurière, M. Geist, R. Elic, and O. Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 1399319--3, 2020.
[53] H. Qiu, W. Mao, C. Wang. H. Franke, A. Youssef, 7. T. Kalbarczyk, T. Başar, and R. K. Iyer. AWARE: Automate workload autoscaling with reinforcement learning in production cloud systems. In USENIX Annual Technical Conference, 2023.
[54] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. Advances in Neural Information Processing Systems, 32, 2019.
[55] S. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[56] A. Santoro, S. Bartunov, M. Botvinick, D. Wierstra, and T. Lillicrap. Meta-learning with memory-augmenter neural networks. In International Conference on Machine Learning, pages 1842-1850. PMLR, 2016.
13

---

[57] L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences. 39(10): 1095-1100, 1953.
[58] J. Snell, K. Swersky, and R. Zemel. Prototypical networks for few-shot learning. Advances in Neural Information Processing Systems, 30, 2017.
[59] Z. Song, S. Mei, and Y. Bai. When can we learn general-sum Markov games with large number of players sample-efficienly In International Conference on Learning Representations, 2022.
[60] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for rein- forcement learning with function approximation. Advances in Neural Information Processing Systems, 12, 1999.
[61] D. Sychrovsky, M. Sustr, E. Davoodi, M. Lanctot, and M. Schmid. Learning not to regret. arXiv preprint arXiv22303.01074 2023.
[62] V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
[63] A. A. Team, J. Bauer, K. Baumli, S. Baveja, F. Behbahani, A. Bhoopchand. N. Bradley-Schmieg M. Chang, N. Clay, A. Collister, et al. Human-timescale adaptation in an open-ended task space. arXiv preprint arXiv:2301006608 2023.
[64] S. Thrun and L. Pratt. Learning Learn. Springer Science & Business Media, 1998.
[65] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, al. Matching networks for one shot learning. Advances in Neural Information Processing Systems, 29, 2016.
[66] L. Wang, Q Cai, Z. Yang, and Z. Wang. On the global optimality of model-agnostic meta- learning. In International Conference on Machine Learning, pages 9837-9846, 2020.
[67] C.-Y. Wei, Y.-T. Hong, and C.-J. Lu. Online reinforcement learning in stochastic games. In International Conference on Neural Information Processing Systems, pages 4994-5004, 2017.
[68] C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive Markov games. In Conference on Learning Theory, pages 4259 4299, 2021.
[69] Q. Xie, Y. Chen, Z. Wang, and Z. Yang. Learning zero-sum simultaneous-move Markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pages 3674-3682, 2020.
[70] S. Xue, C. Qu, X. Shi, C. Liao, S. Zhu, X. Tan, L. Ma. S. Wang. S. Wang, Y. Hu, et al. A meta reinforcement learning approach for predictive autoscaling in the cloud. In ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 4290-4299 2022.
[71] S. Yang and B. Yang. A meta multi-agent reinforcement learning algorithm for multi-intersection traffic signal control. In IEEE International Symposium on Dependable, Autonomic and Secure Computing, pages 18-25, 2021.
[72] Y. Yang and C. Ma. O(T-²) convergence of oettmnsiie--olooooleeeeellrrraad in two- player zero-sum Markov games. arXiv preprint arXiv:2209.12430 2022.
[73] S. Zeng, T. Doan, and Romberg. Regularized gradient descent ascent for two-player zero-sum Markov games. Advances in Neural Information Processing Systems, 35:34446-34558, 2022.
[74] K. Zhang, A. Koppel, H. Zhu, and T. Başar. Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv preprint arXiv:1906.08.0 2019.
[75] M. Zhang, P. Zhao, H. Luo, and Z.-H. Zhou. No-regret learning in time-varying zero-sum games. In International Conference on Machine Learning, pages 26772-26808, 2022.
[76] R. Zhang, Z. Ren, and Li. Gradient play in stochastic games: Stationary points, convergence, and sample complexity. arXiv preprint arXiv:2106.00119 2021.
14

---

[77] R. Zhang, Q. Liu, H. Wang. C. Xiong, N. Li, and Y. Bai. Policy optimization for Markov games: Unified framework and faster convergence. In Advances in Neural Information Processing Systems, 2022.
[78] R. Zhang, J. Mei, B. Dai, D. Schuurmans, and N. Li. On the global convergence rates of decen- tralized softmax gradient play in Markov potential games. In Advances in Neural Information Processing Systems, 2022.
[79] Z. Zhang, Y. Zhou, and X. Ji. Almost optimal model-free reinforcement learningvia reference- advantage decomposition. Advances in Neural Information Processing Systems, 33:15198- 15207, 2020.
15


Reviews:
[{"review_id": "yyrjYv1hWy", "reviewer": "Reviewer_8vaQ", "summary": "The authors introduce theoretical results on Model-Agnostic Meta-Learning in a multi-agent reinforcement learning setting. In particular they show that meta-learning can achieve stronger convergence guarantees than an RL baseline when tasks are similar. The results hold for zero-sum, potential and general-sum games. In order to establish this, they provide theoretical results on convergence for online mirror descent which are dependent on initial conditions. Finally they conduct some small-scale experiments to validate the faster convergence empirically.", "questions": "On lines 94-95, the authors may want to cite another recent paper using meta-learning in the context of a distribution over multi-agent cooperative tasks: https://arxiv.org/abs/2301.07608.", "limitations": "See Weaknesses.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Well motivated and timely article: meta-learning is becoming increasingly prevalent in the multi-agent setting, and theoretical results are lagging behind empirical ones, to the best of my knowledge.\n- The notation is consistent and clear throughout. \n- The theoretical results seem convincing, although I haven't checked the proofs in detail. \n- There is an interesting and intuitive definition of game similarity, which may well find use in other algorithms in the future.", "weaknesses": "- The empirical results are quite small scale, and it would be useful to have a little more explanation about the environment in the main text. \n- It would be nice to have at least one sketch proof in the main text. Perhaps there is a reorganisation of some other material to the Appendix that might permit this.\n- There are a few places where more discussion or justification would be beneficial, for example: why is this \"without loss of generality\" on line 102; to what extent is it standard to neglect the logarithmic terms in line 201, and what is the reason that these terms show up.\n- The limitations / future work section could have a little more detail. Would the authors be happy to comment on scaleability, and to discuss how similar results might be obtained for other meta-learning approaches outside MAML?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of our work and the valuable feedback. Our detailed responses are as follows.\n\n1. We thank the reviewer for the comments on our empirical results. The focus of our work is mostly theoretical, and the simulations were primarily used as proof of concept. But given the reviewer’s interests in the empirical performances of our results, we have added new and larger-scale simulations in this rebuttal to further evaluate the empirical performances of our algorithms. These new simulations include a task with more than 1.7 million states and a task with 4 agents, 625 states and 81 joint actions, both of which are significantly larger than our previous simulations. Please refer to our “global” response to all the reviewers for details of the new simulations.\n\n2. We appreciate the reviewer’s advice on the organization of the paper. We will follow these guidelines to include more discussions of the simulation setup as well as a proof sketch in the main text when preparing for the camera-ready version (where one extra page is allowed).\n\n3. In Line 102, our results readily extend to the setting where the initial state is sampled from an arbitrary distribution. Assuming a fixed initial state is without loss of generality because one can imagine that there exists an extra step $h=0$ where the agent starts from a fixed state $s_0$. The transition probabilities from $s_0$ to any other state $s_1$ can be made arbitrary, which equivalently allows us to start from an arbitrary state distribution at $s_1$. This is a very common assumption in existing works, e.g., [Jin et al., 2022; Song et al., 2022]. In Line 201, suppressing logarithmic terms is also common in the literature as the log terms grow much more slowly than the polynomial terms. In fact, most existing results do have this logarithmic term, e.g., [Zhang et al., 2022]. In our work, the direct reason of this log term is that we divide the $T$ iterations into $\\bar{\\tau}=O(\\log T)$ stages. We have added more discussions in our paper to make these points clear to the reader.\n\n4. For the limitations / future work section, we believe that our methods will not suffer much from scalability issues because our algorithms are essentially designed to be decentralized (in the same sense as discussed in [Mao et al., 2022]): The agents only use local information to update their policies and rarely need to exchange information with others. In addition, while our proofs do not directly generalize to other meta-learning approaches outside MAML, we believe that our analytical methodology (properly defining a similarity metric and then tracking how the policy trajectories on different tasks deviate according to the metric) could still be helpful. \n\n5. We thank the reviewer for reminding us of the recent paper that applies meta-learning to cooperative tasks. We have properly included the reference in the Related Work section.\n"}, {"review_id": "GG0CRxD97t", "reviewer": "Reviewer_kvor", "summary": "This paper establish theoretical results for meta-learning in a wide range of fundamental MARL settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games. Numerical results are shown to demonstrate the advantages of meta-learning. ", "questions": "The simulation part is relatively simple since only toy examples are given. Is it possible to have much more sophisticated examples (at least more than two player) to demonstrate the theoretical results?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper establish theoretical results for meta-learning in a wide range of fundamental MARL settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games. Numerical results are shown to demonstrate the advantages of meta-learning. ", "weaknesses": "The simulation part is relatively simple since only toy examples are given. The advantages of meta-learning are not fully demonstrated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback. The focus of our work is mostly theoretical, and the simulations were primarily used as proof of concept. But given the reviewer’s interests in the empirical performances of our results, we have added new and larger-scale simulations in this rebuttal to further evaluate the empirical performances of our algorithms. These new simulations include a task with more than 1.7 million states and a task with 4 agents, 625 states and 81 joint actions, both of which are significantly larger than our previous simulations. Please refer to our “global” response to all the reviewers for details of the new simulations."}, {"review_id": "RWEoyXK4dz", "reviewer": "Reviewer_CSow", "summary": "The authors proposed a meta-learning approach based on MAML for multi-agent domains where tasks with similar NE policies, when learned sequentially, converges faster to desired equilibria solutions. ", "questions": "L82-83: \" ... weaker solution concepts such as (C)CE ...\", perhaps clarify that in general-sum games NE would not allow for coordination and is therefore restrictive in such games? By \"weaker\" perhaps you meant computationally tractable beyond two-player zero-sum games?\n\nL49: \"... convergence guarantees for MARL.\", do you mean convergence to equilibria specifically? Perhaps clarify in writing that convergence bounds are wrt equilibria upfront? \n\nRelated Works: \"meta-learning\" is overloaded in the RL literature and another line of work in meta-learning follows from prior works such as  [1-3] where a policy is conditioned on prior belief over tasks and can infer Bayes-optimally through interaction at test time to adapt to different tasks. This idea is then extended to multi-agent setting [3-4], with a focus on faster convergence / transfer learning via shared representation learning. Would it make sense to include a brief discussion of this line of meta-learning works in related works? \n\n[1] Meta-learning of Sequential Strategies: https://arxiv.org/abs/1905.03030\n[2] Meta reinforcement learning as task inference: https://arxiv.org/abs/1905.06424\n[3] Meta-Learning with Memory-Augmented Neural Networks: https://proceedings.mlr.press/v48/santoro16.pdf\n[3] NeuPL: Neural Population Learning: https://arxiv.org/abs/2202.07415\n[4] Simplex NeuPL: https://arxiv.org/abs/2205.15879", "limitations": "Please see my comments on the choice of task similarity metric which may be a limitation on when and where the proposed method could be effectively applied. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* Originality \nThe authors investigated theoretical convergence properties of multi-agent learning through the lens of meta-learning of a sequence of similar tasks. This is novel and the problem setting is relevant as non-stationarity is inherent to multi-agent learning that may benefit from the MAML family of methodologies.  \n\n* Quality\nI find the theoretical results thorough but the work could benefit significantly with more substantial results on a few more standard benchmark domains. \n\n* Clarity\nThe paper is generally well written and easy to follow. ", "weaknesses": "* Task similarity metric: my main reservation with the proposed approach is related to the proposed task similarity metric (Sec 3.2) which translates to measuring similarity in different tasks' NE policy. Wouldn't selecting tasks in such way naturally promote faster convergence to NE policies when learning on \"similar\" tasks sequentially? I would appreciate further clarification on why this metric is used and if alternatives have been considered. \n\n* Multi-agent learning inherently deals with non-stationarity during learning as the environment dynamics (from the perspective of any one player) is non-stationary. Quite often such non-stationarity does not translate to similar NE policy though (e.g. rock-paper-scissors, where NE polices would be quite different). Could you clarify if the proposed method should be applicable to such \"similar tasks\" of this nature?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments and the valuable suggestions on improving our work from multiple different perspectives. Our detailed responses are as follows.\n\n1. We appreciate the reviewer’s concern of our task similarity metric. In Section 3.2, we choose the closeness of the NE policies of different games as the similarity metric because we believe it is most natural and comparably less restrictive. Such a metric also resonates existing works [Harris et al., 2022] for matrix games, which allows for direct comparisons. An important alternative metric that we have considered is the $L_1$ norm of the transition function together with the $L_{\\infty}$ norm of the reward function; that is, two games are considered “similar” under this metric if their transition and reward functions are pointwise close. However, we believe that such a metric is more restrictive than the NE closeness metric we consider.  This is because, intuitively, in finite zero-sum games every saddle-point solution (NE) in mixed strategies is the solution to a linear program, and the optimal solutions of two LPs are very likely to be attained at neighboring points if these two LPs have similar constraints and objectives. In this sense, closeness of reward functions tends to imply closeness of NE, but not vice versa because if the optimal solutions of two LPs happen to be attained at the same point, this does not imply that their constraints or objectives are similar. Our NE closeness metric is hence less restrictive in this sense. We would be happy to learn if the reviewer can find any other natural and possibly less restrictive metric, which can be greatly helpful to improve our work. \n\n2. For the “non-stationarity” part, if we understand it correctly, the reviewer’s concern is that there could be multiple NE in a game that are quite different, and there is no guarantee which one the learning algorithm will converge to due to the “non-stationary” learning dynamics. Our method should not be affected by such a case because our similarity metric only assumes one of the NE (not all of them) to be close to those of other games. In fact, the exact advantage of meta-learning is to be able to quickly find a particular NE that is close to the meta-initialization.\n\n3. L82-83: By “a weaker solution concept”, we simply mean that every NE is automatically a (C)CE but not vice versa. As the reviewer has pointed out, NE is in general not computationally efficient beyond two-player zero-sum games, but (C)CE requires an additional public signal to correlate the players’ policies, which might not exist in practical scenarios. L49: Yes, we mean convergence to equilibria specifically. We thank the reviewer for calling attention to these points, and we have revised the paper to make these points clear.\n\n4.  We thank the reviewer for sharing the references. These works tackle “meta-learning” from a slightly different perspective than ours, but we totally agree that they are very relevant and can help provide a more comprehensive viewpoint of the background to the readers. We have included a discussion of this line of research in our Related Work section. \n\n5. We would also like to refer the reviewer to our “global” response section for new simulation results added during the rebuttal based on the feedback from the other reviewers. These new simulations include a task with more than 1.7 million states and a task with 4 agents, 625 states and 81 joint actions, both of which are significantly larger than our previous simulations.\n"}, {"review_id": "4ptvbYI8hg", "reviewer": "Reviewer_wdob", "summary": "The paper introduces a meta-learning method to initialize the OOMD algorithm. Combined with the introduced initialization-dependent convergence guarantees, authors then can show faster convergence when the meta-learning initialization is close.", "questions": "Did you have a chance to run the algorithm on larger games than the small ones included in the current version of the submission?", "limitations": "Sufficient", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, and the prior work is well referenced. \n\n\nThe authors also provide extensive theoretical analysis of their algorithms. I think the most interesting result is Theorem 1 (other theorems often seem like an application of Theorem 1). I believe that the result is novel and interesting.\n\n\nI also appreciate that authors analyze two-player zero-sum markov games as well as markov potential games\n", "weaknesses": "First, I agree that “closest to this work” is Harris, Keegan, et al. \"Meta-learning in games.\" arXiv preprint arXiv:2209.14110 (2022). More recently, a closely related (also meta learning in games and regret minimization) paper presents an algorithm combining meta-learning and regret guarantees: Sychrovsky, David, et al. \"Learning not to Regret.\" arXiv preprint arXiv:2303.01074 (2023). I believe that paper should be included in the related work.\n\n\nMy biggest issue though is the empirical analysis (Section 6 - Simulations).\nThere are no details in the main text and one can only find it in the appendix. It is fine to move details to the appendix, but the authors do not even mention the size of the games in the main text.\nLooking into the appendix, I think the games are trivially small (2x2 matrix games). Furthermore, the games in the meta-learning sequence seem very similar (the epsilon noisy seems very small). I think this is rather confirmed by Figure 1c. It is then not a big surprise that the convergence is so fast, when the games are so small and the Nash Equilibria very similar/close. I think the authors should to evaluate substantially more interesting/diverse/larger games (e.g. some epsilon/noisy parametrization of small poker games).\n\n\nIf the authors add experiments in larger games than the trivially small currently included, I am happy to move my score to \"Accept\" as otherwise I think the paper is good.\n\n\n----------------------------------------------------------------------------------------------------\nAuthors addressed my comments and included more experiments, increasing the score.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback. Our detailed responses are as follows.\n\n1. We thank the reviewer’s appreciation of our Theorem 1, which is indeed one of our most interesting results. While we agree that Theorem 2 can be considered as an application of Theorem 1 (as the reviewer mentioned), we would like to point out that our Theorem 4 (for potential games) and Theorems 5/6 (for general-sum games) are built upon quite different techniques and might be of interest to the reader as well.\n\n2. We thank the reviewer for sharing the recent reference [Sychrovsky et al., 2023]. It focuses more on the empirical side of meta-learning in games, which is a bit different from our theoretical focus but is still a relevant and very interesting work. We have properly included [Sychrovsky et al., 2023] in our Related Work section. In addition, in this rebuttal, we have also added new simulations similar to the “kuhn_poker” example considered in [Sychrovsky et al., 2023]. The kuhn_poker task in [Sychrovsky et al., 2023] only considers 3 poker cards while our new simulation considers a full set of poker with 52 cards, which leads to a significantly larger state space. We would like to refer the reviewer to our “global” response for the details. \n\n3. We appreciate the reviewer’s concern of our empirical analysis and for suggesting alternative experimental setups. We would like to remark that the focus of our work is mostly theoretical, and the simulations were primarily used as proof of concept. But given the reviewer’s interests in our empirical performances, we have added new and larger-scale simulations in this rebuttal to further evaluate the empirical performances of our algorithms. These new simulations include a task with more than 1.7 million states and a task with 4 agents, 625 states and 81 joint actions, both of which are significantly larger than our previous simulations. Please refer to our “global” response to all the reviewers for details of the new simulations.\n"}, {"review_id": "Cv3Sc1JGGP", "reviewer": "Reviewer_Mmgh", "summary": "This paper studies the interdependence between the convergence of MARL and the quality of policy initialization. ", "questions": "No.", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. It proposes a new algorithm that has an initialization-dependent convergence guarantee.\n2. It establishes several theoretical results that connect policy initialization and convergence of MARL in various types of games.", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of our work. We would be happy to discuss if the reviewer has any questions about the paper."}]

Author rebuttal:
We thank all the reviewers for the insightful feedback. In this “global” response, we would like to share some new and larger-scale simulations that we conducted in this rebuttal phase following some of the reviewers’ advice. We believe these new simulations can help address the reviewers’ questions on the empirical performances of our algorithms. 

We added two sets of new simulations. The first task is a Poker endgame similar to the one considered in [Harris et al., 2022]. We use a public River endgame that was released by the authors [Brown and Sandholm, 2018] in the Brains vs AI competition. This task is a zero-sum game with 2 players, ~1.7 million states, and 2 actions (calling or folding) for each player. Poker is a partially observable game, but we found that our algorithm still performs well if each agent simply uses its local observation as the state. We generated similar games by adding $\mathcal{N}(0, 0.5)$ perturbations to the normalized stack amounts of the players, which essentially perturbates the reward function. Figure 1 in the attached PDF file shows that our method can handle such a large state space well, and our meta-learning method can converge to an approximate NE policy faster than individual learning.

In the second task, we consider a 1D linear-quadratic tracking problem where each agent tries to track and state close to the other agents. We adopt the discrete setting as has been utilized in a few recent works [Perrin et al., 2020; Laurière et al., 2022]. The tracking task we consider is a Markov potential game with 4 players, 625 states, and a joint action space of size 81. For each agent $i$, its location transition is given by $s_{t+1,i}=s_{t,i}+a_{t,i} \Delta_t +\epsilon_t \sqrt{\Delta_t}$, where $\Delta_t$ is the time duration, and $\epsilon_t$ is the i.i.d. noise taking values from $\{-2, -1, 0, 1, 2\}$ following a normal distribution. Let $\mu_t$ denote the empirical mean of all the agents’ locations at time $t$. The reward function for agent $i$ is specified as $(-\frac{1}{2}a_{t,i}^2-\frac{1}{4}(\mu_t – s_{t,i})^2)\Delta_t$. Intuitively, this reward function incentivizes agents to track and stay close to the population (despite the random drift $\epsilon_t$), but discourages agents from taking large-magnitude actions. We generated similar games by adding $\mathcal{N}(0, 0.5)$ perturbations to the location transition drift magnitude and the reward functions. Figures 2 and 3 in the attached PDF file demonstrate that our meta-learning method achieves faster NE-gap and value convergences.

References:

M. Laurière, S. Perrin, S. Girgin, P. Muller, A. Jain, T. Cabannes, G. Piliouras, J. Pérolat, R. Élie, O. Pietquin, et al. Scalable deep reinforcement learning algorithms for mean field games. arXiv preprint arXiv:2203.11973, 2022.

S. Perrin, J. Pérolat, M. Laurière, M. Geist, R. Elie, and O. Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 33:13199–13213, 2020.


Meta-review: This paper studied meta-learning in several fundamental MARL settings (learning NE in zero-sum Markov games and Markov potential games, learning CCE in general-sum Markov games) via learning a good policy initialization to adapt to similar tasks. As the core contribution, the paper demonstrated sharper convergence results with meta-learning in theory and illustrated its numerical advantages in several examples. While the main analysis heavily build on existing convergence results for learning zero-sum games, MPGs, and general-sum games, most reviewers agree that the meta-learning results are interesting and novel. The additional large-scale experiments provided during the rebuttal phase also help strengthen the contribution. Therefore, I am recommending for acceptance and ask authors to provide implementation details and discussions on these additional experiments in the revision.
Decision: Accept (poster)