On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning
Authors: Washim Uddin Mondal
Vaneet Aggarwal
Satish Ukkusuri
Venue: Accepted by TMLR ()

Abstract: We show that in a cooperative $N$-agent network, one can design locally executable policies for the agents such that the resulting discounted sum of average rewards (value) well approximates the optimal value computed over all (including non-local) policies. Specifically, we prove that, if $|\mathcal{X}|, |\mathcal{U}|$ denote the size of state, and action spaces of individual agents, then for sufficiently small discount factor, the approximation error is given by $\mathcal{O}(e)$ where $e\triangleq \frac{1}{\sqrt{N}}\left[\sqrt{|\mathcal{X}|}+\sqrt{|\mathcal{U}|}\right]$. Moreover, in a special case where the reward and state transition functions are independent of the action distribution of the population, the error improves to $\mathcal{O}(e)$ where $e\triangleq \frac{1}{\sqrt{N}}\sqrt{|\mathcal{X}|}$. Finally, we also devise an algorithm to explicitly construct a local policy. With the help of our approximation results, we further establish that the constructed local policy is within $\mathcal{O}(\max\{e,\epsilon\})$ distance of the optimal policy, and the sample complexity to achieve such a local policy is $\mathcal{O}(\epsilon^{-3})$, for any $\epsilon>0$. 

Published in Transactions on Machine Learning Research (09/2022)
On the Near-Optimality of Local Policies in Large Coopera- tive Multi-Agent Reinforcement Learning
Washim Uddin Mondal
umondal8purdue.ce edu
School of IE and CE, Purdue University
Vanect Aggarwal
vanectSppurdue..m edu
School of IE and ECE, Purduc University
Satish V. Ukkusuri
subkueur@paurdue.. edu
Lyyles School of Civil Engineering, Purdue University
Reviewed on OpenReview: https: // opwpr//veeeeeeeeeeeommmo net/ forum? id= t5llkgba2p1
Abstract
We show that in a cooperative N-agent network, one can design locally executable policies for the agents such that the resulting discounted sum of average rewards (value) well ap- proximates the optimal value computed over all (including non-local) policies. Specifically, we prove that, if [28, [u]] denote the size of state, and action spaces of individual agents, then for sufficiently small discount factor, the approximation error is given by O(e) where JN [Vx + V Moreover, in special case where the reward and state transition functions are independent of the action distribution of the population, the error improves to O(e) where e - J/v V Finally, we also devise an algorithm to explicitly construct a local policy. With the help of our approximation results, we further establish that the con- structed local policy is within Omaxxfe, <t) distance of the optimal policy, and the sample complexity to achieve such a local policy is O(e=²) for any O.
1 Introduction
Multi-agent system (MAS) is powerful abstraction that models many engineering and social science prob- lems. For example, in a traffic control network, each controller at a signalised intersection can be depicted as an agent that decides the duration of red and green times at the adjacent lanes based on traffic flows (Chen) ltt al. 2020). As flows at different neighboring intersections are interddependent, the decisions taken by one interscction have significant ramifications over the whole network. How can one come up with strategy that steers this tangled mesh to desired direction is one of the important questions in the multi-agent learning literature. Multi-agent, reinforcement learning (MARL) has emerged as one of the popular solutions to this question. Cooperative MARL, which is the main focus of this paper, constructs policy (decision rule) for each agent that maximizes the aggregate cumulative reward of all the agents by judiciously executing exploratory and exploitative trials. Unfortunately, the size of the joint state-space of the network increases exponentially with the number of agents. This severely restricts the efficacy of MARL in the large population regime.
There have been many attempts in the literature to circumvent this curse of dimensionality. For example, one of the approaches is to restrict the policies of cach agent to be local. This essentially means that cach agent ought to take decisions solely based on ils locally observable state. In contrast, the execution of a global policy requires each agent to be aware of network-wide state information. Based on how these local policies are learnt, the existing MARL algorithms can be segregated into two major categories. In independent Q-learning (IQL) (Tan 1993). the local policies of each agent are trained independently. On the other hand, in Centralised Training with Decentralised Execution (CTDE) based paradigm, the training of local policies

---

Published in Transactions on Machine Learning Research (09/2022)
are done in a centralised manner Oliehook et al. 2008
Kraemer and Banerjee 2016 Despite the empirical
success for multiple applications (Han et al.) 2021: Feriani and Hossain 2021). no theoretical convergence guarantees have been obtained for either of these methods.
Recently, mean-field control (MFC) (Ruhhotto et al.) 2020 is gaining popularity as another solution paradigm to large cooperative multi-agent problems with theoretical optimality guarantees. The idea. of MFC hinges on the assertion that in an infinite pool of homogeneous agents, the statistics of the behaviour of the whole population can be accurately inferred by observing only representative agent. However, the optimal policy given by MFC is, in general, non-local. The agents, in addition to being aware of their local states, must also know the distribution of states in the whole population to execute these policies.
To summarize, on one hand, we have locally executable policies that are often empirically sound but have no theoretical guarantees. On the other hand, we have MFC-based policies with optimality guarantees but those roquire global information to be executed. Local exccutability is desirable for many practical application scenarios where collecting global information is either impossible or costly. For example, in a network where the state of the environment changes rapidly (e.g., vehicle-to-vehie et al. 2017)), the latency to collect network-wide information might be larger than the time it takes for the environment to change. Consequently, by the time the global information are gathered, the states are likely to transition to new values, rendering the collected information obsolete. The natural question that arises in this context is whether it possible to come up with locally executable policies with optimality guarantees. Answering this question may provide a theoretical basis for many of the empirical studies in the literature (Chu et al. 2019) that primarily use local policies as the rule book for strategic choice of actions. But, in general, how close are these policies to the optimal one? In this article, we provide an answer this question.
(V2V) type communications (Chen
1.1 Our Contribution
We consider network of N interacting agents with individual state, and action space of size [X',, and M respectively. We demonstrate that, given an initial state distribution, Po: of the whole population, it is possible to obtain a non-stationary locally executable policy-sequence म == (= such that the average time-discounted sum of rewards (value) generated by म closely approximates the value generated by the optimal policy-sequence, MARLL In fact, we prove that the approximation error (e) where
VI*++ V (Theorem 1p. We would like to clarify that the optimal policy-sequence, MMARI. is, in general, not locally executable. In special case where reward and transition functions are independent of the action distribution of the population, we show that the error can be improved to O(e) where e 2 V v
VN
(Theorem 2
Our suggested local solicy-sequence, म is built top of the optimal mean-field policy sequence, TMP that maximizes the infinite-agent value function. It is worth mentioning that л TMP in general, is not local-agent require the state-distribution of the N-agent network at each timc-step in order to exccute it. Our main contribution is to show that if each agent uses infinite-agent state distribution (which can be locally and deterministically computed if the initial distribution, Po is known) as proxy for the N-agent distribution, then the resulting timo-discounted sum of rewards not too far off from the optimal value generated by MARL.
Finally, we devise Natural Policy Gradient (NPG) based procedure (Algorithm I that approximately computes the optimal mean-field policy-sequence, TMF- Subsequently, in Algorithm 2 we exhibit how the desired local policy can be extracted from ThP- Applying the result from (Liu et al. 2020), we prove that the local policy generated from Algorithm yields a value that is at most Omaxx (c,e) distance away from the optimal value, and it requires at most O -3) samples to arrive at the intended local policy for any e > 0.
1.2 Related Works
Single Agent RL: Tabular algorithms such as Q-learning Watkins and Dayan 1992). and SARSA (Rum- mery and Niranjan 1994) were the first RL algorithms adopted in single agent learning literature. Due their scalability issues, however, these algorithms could not be deployed for problems with large state-space.
2

---

Published in Transactions on Machine Learning Research (09/2022)
Recently, neural network based Q-iteration (Mnih et al. 2015). and policy-iteration (Mnih et al. 2016) algorithms have gained popularity as substitute for tabular procedures. However, they are still inadequate for large scale multi-agent problems due to the exponential blow-up of joint state-space.
As discussed before, one way to introduce scalability into multi-agent learning is to restrict the policies to be local. The easiest and perhaps the most popular way to train the local policies is via Independent Q-learning (IQL) procedure which has been widely adapted in many application scenarios. For example, many adaptive traffic signal control algorithms apply some form of IQL (Wei et al. 2019 Chu et al. 2019). Unlike IQL, centralised training with decentralised execution (CTDE) based algorithms train local policies in contralised manner. One of the simplest CTDE based training procodure is obtained via value decomposition network (VDN) (Sunehag et al., 2018) where the goal is to maximize the sum of local Q-functions of the agents. Later, QMIX (Rashid et al., 2018) was introduced where the target was to maximize a weighted sum of local Q-functions. Other variants of CTDE based training procedures include WQMIX (Rashid et al.) 2020), QTRAN (Son et al. 2019) etc. As clarified before, none of these procodures provide any theoretical guarantee. Very recently, there have been some efforts to tcalretically characterize the performance of localised policies. However, these studies either assumne the reward functions themselves to be local, thereby facilitating no agent interaction in the reward model (Qu et al.) 2020), or allow the policies to take state- informatfoon from neighbouring agents as an input, thereby expanding the definition of local policies [Lin et al. 2020: Koppel et al., 2021).
Multi-Agent Local Policy:
Mean- Control: An alternate way to bring scalability into multi-agent learning to apply the con- cept of mean-field control (MFC). Empirically, MFC based algorithms have been applied in many practical scenarios ranging from congestion control (Wang et al.
2020). ride-sharing (Al-Abbasi et al.] 2019) and
epidemic management Watkinn et al. 2016). Theoretically, it has been recently shown that both in homo- geneous (Gu et al., 2021). and heterogeneous Mondal et al. 2022a population of agents, and in population with non-uniform interactions (Mondal et al. 2022b). MFC closely approximates the optimal policy. More- over, various model-free (Angiuli et al., 2022) and model-based (Pasztor et al. 2021) algorithms have been proposed to solve MFC problems. Alongside standard MARL problems, the concept MFC based solutions has also been applied to other variants of reinforcement learning (RL) problems. For example, (Gast and Gaujal 2011) considers system comprising of single controller and N bodics. The controller is solely responsible for taking actions and the bodies are associated with states that change as functions of the chosen action. At each time instant, the controller receives reward that solely is a function of the current states. The objective is to strategize the choice of actions as a function of states such that the cumulative reward of the controller is maximizod. It is proven that the above problem can be approximated via a mean-field process.
2 Model for Cooperative MARL
We consider collection of N interacting agents. The state of i-th agent, i E {1, .N] at time t E 1, , is symbolized as æi E X where X' denotes the collection of all possible states (state-space). Each agent also chooses an action at each time instant from a pool of possible actions, U (action-space). The action of i-th agent at time t is indicated as uf. The joint state and action of all the agents at time are denoted as a;"" A {wi) and uN A { respectively. The empirical distributions of the joint states, Nu and actions, Ni at time are defined as follows.
LV
1 N
(x)
Σ
8(0 = =x), Vx E
(1)
N
1=1
NZ (w)
5(uf u), Yu E 4
(2)
N
where 8(-) denotes the indicator function.
N u. and its state changes according to the following state- transition law: 2141 (ar,", u.²). Note that the reward and the transition function not only depend on the
At time t, the i-th agent receives a reward r (x
3

---

Published in Transactions on Machine Learning Research (09/2022)
state and action of the associated agent but also the states, and actions of other agents in the population. This dependence makes the MARI. problem difficult to handle. In order to simplity the problem, we assume the reward and transition functions to be of the following form for some r: X' x U x P(Z)) P(U) + R, and P: X x u x P(x) x P(U) + P(2) where P()) is the collection of all probability measures defined over its argument sel,
re(af" u = r(ab, uhi ph v P( ) P(a uh uf v
(3)
(4)
Vi E (I,...,, NJ, Vaz" X and Vu," E u.. Two points are worth mentioning. First, (3 and 4 suggest that the reward and transition functions of each agent take the state and action of that agent, along with empirical state and action distributions of the entire population as their arguments. As a result, the agents can influence each other only via the distributions μ²" uy which are defined by 11. (2) respectively. Second, the functions r, P are taken to be the same for every agent. This makes the population homogeneous. Such assumptions are common in the mean-field literature and holds when the agents are identical and exchangeable.
We define a policy to be a (probabilisttc) rule that dictates how certain agent must choose its action for given joint state of the population. Mathematically, a policy π is mapping of the following form, a X + P(4). Let æद denote the policy of i-th agent at time t. Due to (3) and (4), we can, without loss of generality, write the following equation for some π : X x P(X) U.
(5)
In other words, one can equivalently define a policy to be a rule that dictates how an agent should choose its action given its state and the empirical state-distribution of the entire population. Obscrve that, duc to agent-homogeneity, the policy function, т,, each agent are the same. With this revised definition, let the policy of any agent at time be denoted as Te, and the sequence of these policies be indicated as π A (0.,.e For a given joint initial state, ai the population-average value of the policy sequence π is defined as follows.
UMARL (16 T)
N N
Σ am ux²)
X Σ
uN UN))
(6)
N
where the expectation is computed over all state-action trajectories induced by the policy policy-sequence, and 7 E [0, 1) is the discount factor. The target of MARL is to maximize UMARL over all policy sequences, Note that, in order to execute the policy Mi,AAL: in general, the agents must. have knowledge about their own states al time 1 as well as the empirical ditteidistii of the entire population at the same instant. As stated previously, the collection of population- wide state information is a costly process in many practical scenarios. In the subsequent sections of this article, our target, therefore, is to identify (a sequence of) local policies that the agents can execute solely with the knowledge of their own states. Additionally, the policy must be such that its value (expected time-discounted cumulative reward) close that generated by the optimal policy-sequence, MARL
Let the optimal policy sequence be MARL & he
3 The Mean-Field Control (MFC) Framework
Mean-Field Control (MFC) considers scenario where the agent population size is infinite. Due to the homogeneity of the agents, in such a framework, it is sufficient to track only one representative agent. We denote the state and action of the reprosentative agent at time t as Ie E X and u4 E U, respectively, while the state and action distributions of the infinite population at the same instance are indicated as μ1 E P(2) and vfe E P(U), respectively. For given sequence of policies & (Tthe ) and the state distribution 11,0 at time t, the action distribution uºo at the same instant can be computed as follows.
Di0 = MF (141, mT) A
Te (2 pi (a:
(7)
ZEX
4

---

Published in Transactions on Machine Learning Research (09/2022)
In similar fashion, the state-distribution at time t + can be evaluated as shown below.
Mi+1 pMPPpp (Mi Te) Σ
P(r, P(a,u, ui MP (uf (x,) (u)u
(8)
Finally, the average reward at time t can be expressed as follows.
MP (M m²) -
ΣΣ FEX uell
r(z, u, pi: ME (14) (u)) (x:)
(9)
For an initial state distribution, Po, the value of policy sequence = is computed as shown below.
20 Σ t=0
(M σ)
3 MF MF ( Te)
(10)
The goal of Mcan-Ficld Control is to maximize VMF (M: over all policy sequences π. Let the optimal policy sequence be denoted MM-- [Gu et al. 2021 recently established that if the agents execute TMP in the N- agent. MARL system, then the N-agent value function generated by this policy-sequence well-approximates the value function generated by MARI. when N is large. However, to execute the sequence ThP in an N-agent system, each agent must be aware of empirical state distributions, {μz (u,N), (o,...,,...) along with its own states at each time instant. In other words, when the i-th agent an N-agent system executes the policy sequence MMP & (T }, chooses action time according to the following distribution, of ~ Mi,MF (#t, )= As stated in Section [ the computation of empirical state distribution of the whole population at each instant is a costly procedure, In the following subsection, we discuss how we can design ncar-optimal policy that does not require (um he((1...... its exccution.
Designing Local Policies: Note from Eq. that the evolution of rnfinite-populationn state distribution, ii is deterministic equation. Hence, if the initial distribution Mo is disseminated among the agents, then each agent can locally compute the distributions, (n²²) for / >> 0. Consider the following policy sequence, denoted as AMP (fMmhhe (o..... ).
( 11) & TiMr(E, pe), Va E X, P(X), (0,1,...}
(11)
The sequence, TMP A TTiMmhee(o... as mentioned before, the optimal policy-sequence that maximizes the mean-field value function, ( :) for a given initial state distribution, Po Note that, in order to execute the policy-sequence, Mi in an N-agent system, each agent must be aware of its own state well the state distribution of infinite agent system at each time instant-both of which can be obtained locally provided it is aware of the initial distribution, Mo- In other words, the policy-sequence #MF completely disregards the empirical distributions, (ui") )EE(1,,... (instead depends on {ur he(12, }), and therefore is locally executable for t 0.
The above discussion well establishes ØMP as a locally executable policy. However, it not clear at this point how well HMP performs in comparison lo the optimal policy, 7MARL an N-agent system. Must one embrace significant performance deterioration enforce locality? In the next section, we provide an answer to this crucial question.
4
Main Result
Before stating the main result, we shall state a few assumptions that are needed to establish it. Our first assumption is on the reward function, r, and the state-transition function, P. defined in (3) and respectively.
5

---

Published in Transactions on Machine Learning Research (09/2022)
Assumption 1. The reward function, r, is bounded and Lipschitz continuous with respect to the mean-field arguments. Mathemalicully, there exists Mn, Ln > O such that the following holds
(a) UI MR
(b) 1r v1) - r(æ, u2, U2)1 S LR [lle - M221 1 + 11 2211]
Ve E X. Vu E U, 4u P2 E P(X), and YV1, V2 E P(U). The function
|. denotes Lı-norm.
Assumption 2. The bonsstiann function, P, is Lipschilz conlinuous with respect to the mean-field arguments. Mathematically, there exists Lp O such that the following holds
M2, v2)1 (a) U1 P(z, M,
Lp l1me M2l1 + | 12211
Va E X, Vu E E,, Vu 14 E P(X), and Ve E P(U).
Assumptions and ensure the boundedness and the Lipschitz continuity the reward and state transition functions. The very definition of transition function makes bounded. So, is not explicitly mentioned Assumption These assumptions are commonly laken in the mean-field literature (Mondal et al. 2022a
Gu et al. 2021 Our next assumption is on the class of policy functions.
Assumption 3.
The class of admittable policy functions, II, is such that every æ E II satisfies the following
for some LQ > 0,
[T(Z, m2) - x (I,, 122111 S Lolu - p2l1
Vo E X, Wll U2 E P(X).
Assumption 3 states that every policy is presumed to be Lipschitz continuous t. the mean-field state distribution argument. This assumption is also common in the literature (Carmona et al.) 2018 Pasztor let al. 2021 and typically satisfied by Neural Network based policies with bounded weights. Corresponding to the admittable policy class II, we define II & x II ... as the set of all admittable policy-soquences.
We now state our main result. The proof of Theorem T is relegated Appendix
Theorem 1. Let ag be the initial states in an N Naagent system and #4 be its associated empirical distribution. to be policy sequences that mazimize "MF(Hon ) and (MARL(E;) .)) respectively within the class, IT Let सhE be localized policy sequence
Assume π MF & (TMMPtrr((01..-) and MARL & (T..AALL
corresponding to TMP which is defined by 11 If Assumptions and 2 hold, then the following is true whenever 7Sp < 1.
MR
LR
JUMARL MMARI. - UMARL #mP)) 1 (2nCP))
[
1 1
VN
VN
(12)
VN + V
Sp Sp-1)
1-7Sp
The parameters are defined follows Cp A 2 Lp, Sn P (Mn + 2L + Lg (M a LR), and Sp (1+2Lp) + LQ(1+ Lp) where MR, LR, Lp, and LQ are defined in Assumplions
+
Theorem accomplishes our goal of showing that, for large N, there exists a locally exccutable policy whose +
N-agent value function is most O ( J Vxx++/u) distance away from the optimal N-agent value function. Note that the optimality gap decreases with increase in N. We, therefore, conclude that for large population, locally-executable policies are near-optimal. Interestingly, this result also shows that the optimality gap increases with | [4], the sizes of state, and action spaces. In the next section, we prove that, the reward, and transition functions do not depend on the action distribution of the population, then it is possible to further improve the optimality gap.

---

Published in Transactions on Machine Learning Research (09/2022)
5 Optimality Error Improvement in Special Case
The key to improving the optimality gap of Theorem hinges on the following assumption.
Assumption 4. The reward function, r, and transition Junction, P are independent of the action distribution of the population. Mothematically,
(a) r(x, u, U, = =r(z,u, u, 11)
(b) P(x, u. 11,) P(
Vz E X, Yu EU, Vp E P(X), and Vv E P(U).
Assumption eonnidders a scenario where the reward function, r, and the transition function, P is independent of the action distribution. In such case, the agents can influence each other only through the state distribution. Clearly, this is special case of the general model considered in Section 2 We would like to clarify that although r and P are assumed to be independent of the action distribution of the population, they still might depend on the action laken by the individual agents. Assumption 1 is commonly assumed in many mean-field related articles (Tiwari et al. 2019).
Theorem 2 (stated below) formally dictates the optimality gap achioved by the local policics under Assump- tion The proof of Theorem 2 relegated to Appendix B
Theorem 2. Let Lg be the initial states in an N -agent system and Po be its associated empirical distribution. and TMRLL & (TT.MARL to policy sequences that mazimize uMF(Mo:)) -), and UMARI( .)) respectively within the class, 1o.. Let मt RMP be localized policy sequence and hold, then the following is true
Assume TMP & (TM,MFrrE
corresponding to TMF which is defined by 11 If Assumptions whenever SSp <
2
MR VN
( TMARI. UMARL #xTP)
S
1 - 7
(13)
45R
1
1
X
Sp-1
1 1-7S
7
The parameters same as in Theorem
7
Theorem suggests that, under Assumption + the optimality gap for local policies can be bounded as O VN VI). Although the dependence of the optimality gap on N is same as in Theorem its dependence on the size of state, action spaces has been reduced to (Vv(x)) from (V(xx| + VIu) stated previously. This result is particularly useful for applications where Assumption holds, and the size of action-space is large.
A natural question that might arisc in this context is whether it is possible to remove the dependence of the optimality gap the size of state-space, |X| by imposing the restriction that P are independent of the state-distribttion Despite our effort, we could not arrive at such a result. This points towards an inherent asymmetry between the roles played by state, and action spaces in mean-field approximation.
6 Roadmap of the Proof
In this section, we provide outline of the proof of Theorem The proof of Theorem is similar. The goal in the proof of Theorem is to establish the following three bounds.
Go (EM TMARL) UMP(H0) ग MARL)) v X
+
(14)
VN
V + Mu
( G JUMARI, TMF) T=M))=
(15)
VN
V + V M
G2 JUMARL ( a #MP) UMP Tmp)==
(16)
VN

---

Published in Transactions on Machine Learning Research (09/2022)
where UMARL (..-) and .M)(;)) are value functions defined by (6] and 10 respectively, Once these bounds
are established, 130
can be proven easily. For example, observe that,
"MARL ( MARL) "MARL ( APP)
N "MARL (T) MARL) UMF ( (Mo: T MPF + UMF (M TMP) - UMARL (1 ( MP)
"MARL (1) MMARL UMF (MO, MARL) + G2
VIx
Go + G2 =
(17)
VN
Inequality (a) uses the fact that ThP is a maximizer of uMr(Ho: :). Following a similar argument, the term
"MARL(Z)) )MF) "MARL( MARi. can be bounded by G1 + G2 =
v +
14
Combining with
V/
Vixl+
17
we can establish that [UMARL MARRL) - UMARL MiF =
vN
To prove
15
and 16 it is sufficient show that the following holds
Vix + ( V
Jo - UMARL H) UMM x) =
(18)
VN
for suitable choice of poliey-sequences, म, and π. This is achieved as follows.
Note that the value functions defined the dime-discounted sum of average rewards. To bound Jo defined in (18), we therefore focus on the difference between the empirical N-agent average reward, N rātt We Pi N ) at time generated from the policy-sequence म, and the infinite agent average reward, MF (uf), TT) at the same instant generated by The parameters Tt, ni n DN respectively denote state, action of i-th agent, and empirical state, action distributions of N-agent system at time L corresponding to the policy-sequence म. Also, by T. 1 we denote the infinite agent state distributions at time t corresponding to म, π respoctively.
The difference between N E, r ny. f. D and MF MF (4,", me) can be upper bounded by three terms.
The first term is 1 Σ, r(z), up, p DNN) - y MP (Fz #t) which is bounded as O 1 vIu) by Lemma (stated Appendix A.2
The second term is MF (M," ãt) - MF (A. #1) which be bounded as O(p
11 by using
the Lipschitz continuity of y MF established in Lemma 4 in Appendix A.1 The term
p, can
be further bounded as O
VT v
using Lemma stated in Appendix
A.2
Finally, the third term is I MP (1;;" . M (H, Tt)- Clearly, # = n, then this term is zero. Moreover, is localization of ग,, defined similarly as (11) then the term zero as well. This due to the fact that the trajectory of state and action distributions generated by ग,, are exactly the same in infinite agent system. This, however, may not be true in N-agent system.
For the above two cases, i.e., when ग, π are the same or one is localization of another, we can bound 1 E. ui, N. DNN) ,M (HL0, Tt) as O VN [ by taking a sum of the above three bounds. The bound obtained is, in general, t dependent. By taking time discounted sum of those bounds, we can establish
18
Finally, 114).
16 are established by injecting the following pairs of policy-soquences in 18 (म, (AARI MARI.). (TMP- TMP), (#MP Thp). Note that म. π are equal for first two pairs whereas in the third case, मे is a localization of n.

---

Published in Transactions on Machine Learning Research (09/2022)
7 Algorithm to obtain Near-Optimal Local Policy
In section we discussed how near-optimal local policies can be obtained if the optimal mean-field policy sequence MP is known. In this section, we first describe a natural policy gradient (NPG) based algorithm to approximately obtain TMP- Later, we also provide an algorithm to describe how the obtained policy-sequence is localised and executed in a decentralised manner.
Recall from section that, in an infinite agent system, it is sufficient to track only one representative agent which, at instant takes action de the basis of its observation of its own state, Tt, and the state distribution, 14 of the population. Hence, the evaluation of 'MP Problem with state-space X' x P(X), and action space U. One can, therefore, presume TM to be stationary i.e., 'M = MrE, TMr.... ).. hold for the localised policy-scquent optimal policy, TMr. This facilitates a drastic reduction in the search space. With slight abuse of notation, in this section, we shall use Tą to denote policy parameterized by Φ, as well as the stationary sequence generated by it.
be depicted a Markov Decision
( [Puterman 2014). We would like to point out that the same conclusion may not
MMF- Stationarity of the sequence, THP reduces our task to finding an
Let the collection of policies be denoted as II. We shall assume that II is parameterized by t Rd. Consider an arbitrary policy T E II. The Q-function associated with this policy be defined as follows Vo E X. p E P(X), and Vu Eu.
Qo M, 2 rr( ue, p4: vi) = I. 1o = 14, 24p = u
(19)
where U++1 ~ no (11411 11, T++1 P(x,, ue, H4, ve). and pe, Vs are recursively obtained Vt > using respectively from the initial distribution Po = μ. The advantage function associated with mp is defined as shown below.
Ao p1 u) a Q0 B(Qo(I,
(20)
The expectation evaluated over Re (x. p)) To obtain the optimal policy, ThEs we apply the NPG update (Agarwal el al. 2021 Liu et al., 2020) shown below with learning parameter, v). This generates sequence of parameters
{ from arbitrary initial choice, Do-
p Ø + m,,, Wj arg min L v, (w,
(21)
4; The term Sug is the occupancy measure defined as,
Sh (2. A P( z. u. u, u/zo = M4 u, (T, - -7)
T=0
whereas the function L oe is given as follows.
de [ (A0 (1 >)) V log (x, (w)) O]
L L,, (w, 1) A E Sag
Note that in j-th iteration in 21 the gradient direction Wj is computed by solving another minimization problem. We employ a stochastic gradient descent (SGD) algorithm to solve this sub-problem. The update equation for the SGD is as follows: Wj,41 Wy whj Liu al.) 2020 where a is the learning parameter and the gradient direction, hy is defined as follows.
1 As, (x, pe, Ve, log T& (z. (1)
h11 A w Va, log na, (z, p)(u)=
(22)
9

---

Published in Transactions on Machine Learning Research (09/2022)
Algorithm Natural Policy Gradient Algorithm to obtain the Optimal Policy Input: 77, a: Learning rates, J, L: Number of execution steps wo; Pu: Initial parameters, Moi Initial state distribution
Initialization: Φ < D0
1: for j E {0, 1...,......
13 do
W,00 f Wo
for E {0, 1, T. 1) do
4: Sample (I, pe u) ~ Spn and Åo, (2, u. using Algorithm
5: Compute h using
22
W,,+1 t Wyt - ah
end for
7: Wj - I Lim Wjj
8: 24+1 f 22 + i[w
end for
Output: {01, ... " Policy paramcters
where (z, μr ujis sampled from the occupancy measure S and Ås, is a unbiased estimator of As,- We detail the process of obtaining the samples and the estimator in Algorithm| in the Appendix M We would like to clarify that Algorithm 3 of (Agarwal et al. 2021 is the foundation for Algorithm The NPG process is summarised in Algorithm 1
In Algorithm|
describe how the policy obtained from Algorithm can be localised and executed by the agents in decentralised manner. This essentially follows the ideas discussed in scction 3 Note that, in
order lo execute line 3 in Algorithm 2 the agents must be aware of the transition function, P. However, the
knowledge of the reward function, r, is not required.
Algorithm 2 Decentralised Execution of the Policy generated from Algorithm Input: Φ; Policy parameter from Algorithm [I T: Number of Execution Steps Mo: Initial state distribution, zo: Initial state of the agent.
1: for E (0, 1, ,T -T-11 1] do Execute un ~ no (x))
Compute M4+1 via mean-field dynamics (8)
Obscrve the next state l++1 (Updated via N-agent dynamics: F++1 P(xs, ue N.d vNN)
Updale: fe + 1141
6: Update: f- T++1
7: end for
Theorem showed that the localization of the optimal mean-field policy TMP is near-optimal for large N. However, Algorithm I can provide only an approximation of TMP One might naturally ask: is the decentralised version of the policy given by Algorithm [ still near-optimal? We provide an answer to this question in Theorem 3 Lemma [ which follows from Theorem 4.9 of (Liu et al.) 2020), is an essential ingredient this result. The proof Lemma [ however, hinges on the assumptions stated below. These are similar to Assumptions 2.1, 4.2, and 4.4 respectively in (Liu et al., 2020).
A Assumption 5. VΦ E RRd, Vao E P(2),, for some X 0, Frn xla is posilive semi-defiill, where F " (o) is given follows.
F ( A Bee (OTT ()(3}} x (Vo logma(z,
Assumption 6. Vp E Rd Vp E P(X), Ve E X, Vu Eu,
V log To (1, (u)) G
for some posilive constant G.
10

---

Published in Transactions on Machine Learning Research (09/2022)
Assumption 7. v 22 RR, Au P(2), Vr E X, Vu U,
Ve, log næ, (z, (t) V4, log n4, (z, ((()) M D2
for some posilive constant M. Assumption 8. 4Φ E RR, Apo E P(2),
Lee: (wa, 4) S Ebias: w 2 arg min Leg (w, ②)
p4g
where 4* is the parometer of the optimal policy.
The parameter Obias indicates the expressive power of the paramcterized policy class, II. For example. Ebias = 0 for softmax policies, and is small for rich neural network based policies.
Lemma 1. Assume that { is the sequence of policy porameters generated from Algoritho If
Assumptions B hold, then the following inequality holds for some choice of m,, a, J, L, for arbitrary initial parameter To and initial state distribution po (((X)
sup UMF (Mo TT)
Σ j=1
UMF (14: nT,) S V Vbias
1-7 C,
(23)
DER
The sample complexity of Algorithm to achieve
23 is O(E
We now state the following result.
Theorem Let m be the initial states in on Naagent system and Po be its associated empirical distribution.
Assume that { { are the sequences of policy parameters obtained from Algorithm and the set of policies,
II obeys Assumption 3. If Assumptions
5 hold, then for arbitrary >>> O, the following relation holds for certain choices of 1); or, J, T,, and orbitrary initial distribution, 1o E EP(X), and initial parameter, to.
Chias
sup UMARL (H4: TT) SERd
UMARL (Ho, #4,) <
+ Cmaxx(eee).
(24)
[ V
whenever 7Sp < where Sp is given in Theorem 7 The term Tay denoles the localization of the policy no, defined simålarly as in 11 and C is constant. The sample complerity of the process is O(e Additionally, if Assumption is satisfied, then e in 24 can be reduced
V/X//V.
The proof of Theorem 3 is relegated to Appendix N It states that for any > O, Algorithm can generate policy such that if it is localised and executed in decentralised manner in an N-agent system, then the value generated from this localised policy is at most O(maxfc, et) distance away from the optimal value function. The sample complexity to obtain such a policy is O(e
8 Experiments
The setup considered for the numerical experiment is taken from (Subramanian and Mahajan 2019) with slight modifications. We consider network of N collaborative firms that yield the same product but with varying quality, The product quality of i-th firm, E {1, N at time t E {0, 1, } is denoted as of that can take values from the set Q .o.... Q - 11. At each instant, each firm has two choices to make. Either it can remain unresponsive (which we denote as action 0) or can invest some money to improve the quality of its product (indicated as action 1). the action taken by i-th firm at time is denoted as ui. then its state-transition law described by the following equation.
x
if =
#
F Q
(25)
xe
x(Q
1x---1-
-1
elsewhere
11

---

Published in Transactions on Machine Learning Research (09/2022)
where X is uniform random variable in [0, 1], and f is the mean of the empirical state distribution, j4 The intuition behind this transition law can be stated as follows. If the firm remain unresponsive i.e., uș = 0, the product quality does not improve and the state remains the same. In contrast, if the firm invests some money, the quality improves probabilisticall.. However, the average quality, / in the market is high, a
significant improvement difficult to achieve. The factor (1 + describes the resistance to improvement due to higher average quality. The reward function of the i-th firm is defined as shown below.
r(a, uhy uh UN ag BRØG N ARU.
(26)
The first term, agzz is due to the revenue earned by the firm; the second term, BRiZ is attributed to the rosistance to improvement imparted by high average quality; the third term, Anu is due to the cost incurred for the investment. Following our previous convention, let TMr, and RMP denole the optimal mean-field
policy-sequence and its corresponding local policy-sequence respectively. Using these notations, we define the error for a given joint initial state, z as follows.
error |UMARI, T UMARI #MP)
(27)
function of N and Q. Evidently, error decreases with N and increases with Q. We would like to point out that MP, in general, is not maximizer of (2g" However, for the reasons stated in Section 1 it is difficult to evaluate the N-agent optimal policy-sequente large N. On the other hand, π MF can be easily computed via Algorithm and can act as a good proxy for MARL. Fig. [ therefore essentially describes how well the local policies approximate the optimal value function obtained over all policy-sequee volicy-sequences an N-agent system.
Fig. 1 plots
π "MARL: especially for
4-
3-
0-
20
40
100
15
25
35
(b)
Figure 1: Error defined by (27] function of the population size, N (Fig. la and the size of individual state space, (Fig. lbp. The solid line, and the half-widtt of the shaded region respectively denote mean, and standard deviation of error obtained over 25 random seeds. The values of different system parameters are: = 1, åR = AR = 0.5. We use Q = 10 for Fig. Ia whereas N = 50 for Fig. lb Moreover, the values of different hyperparameters used in Algorithm 1 are as follows: a = 17 = 10 -= 102. We use food
forward (FF) neural network (NN) with single hidden layer of size 128 as the policy approximator.
The code used for the numerical experiment can be accessed at:
http://giiuubb.aaappuuuuueeeee /Clan-
Before concluding, we would like to point out that both reward and state transition functions considered in our experimental set are independent of the action distributions. Therefore, the selting described in this section satisfies Assumption | Moreover, due to the finiteness individual state space Q, and action space (0, 1), the reward function bounded. Also, straightforward to verify the Lipschitz continuity of both reward and transition functions. Hence, Assumptions and are satisfied. Finally, we use neural network (NN) based policies (with bounded weights) in our experiment. Thus, Assumption 3 is also satisfied.
12

---

Published in Transactions on Machine Learning Research (09/2022)
9 Conclusions
In this article, we show that, in an N-agent system, can always choose localised policies such that the resulting value function is close to the value function generated by (possibly non-local) optimal policy. We mathematically characterize the approximation error as function of N.. Furthermore, we devise an algorithm to explicitly obtain the said local policy. One intoresting extension of our problem would be to consider the case where the interactions belween the agents are non-uniform. Proving near-optimality local policies appears to be difficult in such a scenario because, due the con-uniformity, the notion of mean-field is hard to define. Although our results pertinent to the standard MARL systems, similar results also be established for other variants of reinforcement learning problems, e.g., the model described in (Gast and Gaujal 2011
Acknowledgments
W. U. M. and S. V. U. were partially funded by NSF Grant No. 1638311 CRISP Type 2/Collaborative Re- search: Critical Transitions the Resilience and Recovery of Interdependent Social and Physical Networks.
References
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22 (98):1-76, 2021.
Abubakr O Al-Abbasi, Arnob Ghosh, and Vaneet Aggarwal. Deeppool: Distributed model free algorithm for ride-sharing using deep reinforcement learning. IEFE Transactions Intelligent. Transportation Systems, 20(12):4714 4727, 2019.
Andrea Angiuli, Yean-Pierre Fouque, and Mathicu Laurière. Unified reinforcement q-learning for mean field game and control problems. Mathemalics of Comtrol, Signals, and Systems, pages 1 1-55, 2022.
René Carmona, François Delarue, al. Probabilistic theory of mean field games with applicalions T-II. Springer, 2018.
Chacha Chen, Hua Wei, Nan Xu, Guanjie Zheng, Ming Yang, Yuanhao Xiong, Kai Xu, and Zhenhui Li. Toward thousand lights: Decentralized deep reinforcement learning for large-scale traffic signal control. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3414-3421, 2020.
Shanzhi Chen, Jinling Hu, Yan Shi, Ying Peng, Jiayi Fang, Rui Zhao, and Li Zhao. Vehieli-to-everythiing (v2x) services supported by Ite-based systems and 5g. IEEE Communications Standards Magazine, 1(2): 70 76, 2017.
Tianshu Chu, Jie Wang, Lara Codecà, and Zhaojian Li. Multi-agent deep reinforcement learning for large- scale traffic signal control. IEEE Transactions on Intelligent. Transporlation Syslems, 21(3):1086-100 1095. 2019.
Amal Feriani and Ekram Hossain. Single and multi-agent deep reinforcement learning for Al-enabled wireless networks: A tutorial. IEEE Communications Surveys & Tutorials, 23(2):1226-12)) 1252, 2021.
Nicolas Gast and Bruno Gaujal. A mean field approach for optimization in discrete time. Discrele Event Dynamic Systems, 21(1):63-100 -01, 2011.
Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mean-fiele controls with g-learning for cooperative marl: convergence and complexity analysis. SIAM Journal on Mathematics of Data Science, 5(4):1168-1196 2021.
Chenchen Han, Haipeng Yao, Tianle Mai, Ni Zhang, and Mohsen Guizani. Qmix aided routing in social based delay-tolerant networks. IEFE Tronsactions Vehicular Technology, 71(2):1952 1963, 2021.
13

---

Published in Transactions on Machine Learning Research (09/2022)
Alec Koppel, Amrit Singh Bedi, Bhargav Ganguly, and Vaneet Aggarwal. Convergence rates of average-reward multi-agent reinforcement, learning via randomized linear programming. arXiv preprinl arXiv:2110.12922 2021.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocompuling, 190:82 94, 2016.
Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman. Multi-agent reinforcement learning in stochastic networked systems. arXiv preprint arXiv:2006.0655 2020.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduccd)) policy gradient and natural policy gradient methods. Advances Neural Information. Processing Systems, 33: 7624-7636, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529 -33-3 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- PMLR, 2016.
national conference on machine learning, pages
Washim Uddin Mondal, Mridul Agarwal, Vaneet Aggarwal, and Satish V. Ukkusuri. On the approximation of cooperative heterogeneous multi-agent reinforcement learning (MARL) using mean field control (MFC). Journal of Machine Learning Research, 23(129): 46, 2022a.
Washim Uddin Mondal, Vaneet Aggarwal, and Satish Ukkusuri. Can mean field control (mfe) approxi- mate cooperative multi agent reinforcement learning (marl) with non-uniform interaction? The 38th Conference on Uncertainty in Artíficial Intelligence, 2022b.
Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-355 2008
Barna Pasztor, Ilija Bogunovic, and Andreas Krause. Efficient model-basod multi-agent mean-field reinforce-
ment learning. arXiv preprint arXiv:2107044055 2021.
Martin L Puterman. Markow decision processes: discrete stochastic dynomic programming. John Wiley & Sons, 2014.
Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable multi-agent reinforcement learning for networked systems with average reward. Advances in Neural Information Processing Systems, 33:2074- 2086, 2020.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International conference on machine learning, pages 4295-40 43044. PMLR, 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in neural information processing systems, 33:10199 10210, 2020.
Gavin A Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems, volume 37.
Citeseer, 1994.
Lars Ruthotto, Stanley J Osher, Wuchen Li, Levon Nurbekyan, and Samy Wu Fung. machine lcarning framework for solving high- dime-dima mean field game and mean field control problems. Proceedings of the National Academy of Sciences, 117(17)9918) 9193, 2020.
14

---

Published in Transactions on Machine Learning Research (09/2022)
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International conference on machine learning, pages 5887 5896. PMLR, 2019.
Jayakumar Subramanian and Aditya Mahajan. Reinforcement learning in stationary mean-field games. Tn Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 251 259, 2019.
Peter Sunchag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnocki, Vinicius Zambaldi, Max Jader- berg, Mare Lanctot, Nicolas Sonnerat, Joel 7. Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning based team reward. In Proceedingss of the 17th International Confer- ence on Autonomous Agents and MulliAgent Systems, pages 2085 2087, 2018.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the lenth international conference on machine learning, pages 330 337, 1993.
Nilay Tiwari, Arnob Ghosh, and Vaneet Aggarwal. Reinforcement learning for mean field game. arXiv preprint 1rXi::1905.13335 2019.
Xiaoqiang Wang, Liangjun Ke, Zhimin Qiao, and Xinghua Chai. Large-scale traflic signal control using novel multiagent reinforcement learning. IEEE transactions on cybernetics, 51(1):174-187, 2020.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3):279 292, 1992.
Nicholas Watkins, Cameron Nowzari, Victor M Preciado, and George J Pappas. Optimal resource alloca- tion for competitive spreading processes on bilayer networks. IEEE Transactions on Control of Network Systems, 5(1):298 307, 2016.
Hua Wei, Chacha Chen, Guanjie Zheng, Kan Wu, Vikash Gayah, Kai Xu, and Zhenhui Li. Presslight: Learning max pressure control to coordinate traffic signals in arterial network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1290-1298, 2019.
15

---

Published in Transactions on Machine Learning Research (09/2022)
A Proof of Theorem j
In order to establish the theorem, the following Lemmas are necessary. The proof of the Lemmas relegated
to Appendix C
A.1 Lipschitz Continuity Lemmas
In the following three lemmas (Lemma n. IT arbitrary admittable policies, and p., Jr P(x) are arbitrary state distributions. Moreover, the following definition is frequently used.
[T(;,)) - 1oo a sup [T 11) (x)
(28)
zEX
Lemma 2. If MF (..)) is defined by then the following holds.
aa (4,, πT) MI (ū, R) 2 44 ūi (T(
(29)
Lemma 3. If PMP (1,)) is defined by 18 then the following holds.
|pMp (1, T) PMF (jz, #) S Splp - F/11 + Spla(.
(30)
where Sp A 1 2bp, and Sp 1 I.p. Lemma 4. If MF (M.)).) (c,:) ) is defined by (9), then the following holds.
MF (H, T) - - MF (i,, T) S 3nlp fa/1 + Snlt(s --, -
(31)
where ÖR A MR 2LR, and SR & MR + LR.
Lemma essentially dictate that the state and action evolution functions, (PMF (s,), and MP (M))) respectively), and the average reward function, (.....) demonstrate Lipschitz continuity property w. r. t. the state distribution and policy arguments. Lemma is an essential ingredient in the proof of Lemma 3
and !
A.2 Large Population Approximation Lemmas
In the following four lemmas (Lemma 8 π & (oe...).....)) E II is an arbitrary admissible policy- sequence, and {ug U he(o.1,... are the -aagent empirical state, and action distributions induced by it from the initial state distribution, pg. Similarly, {æf, u(),e are the states, and actions of i-th agent evolved from the initial distribution, Mo via the policy-sequence, The joint states, and actions at time are denoted by x. u, respectively.
Lemma 5. The following inequality holds VI 1..1,...).
B D
MF
(M
M
(32)
Lemma 6. The following inequality holds Vt E .....
Cp VN [ixx+ viul
E 1
MMP
PMP(HN :0)h <
(33)
where Cp & + Lp.
Lemma 7. The following inequality holds Vt E {0, .....
MR
LR VN
r r(
u NN viN) Mr
(Nrt Te)
<
M
N
VN
16

---

Published in Transactions on Machine Learning Research (09/2022)
Finally, if fi indicates the state distribution of infinite agent system time t induced by the policy-
sequence, π from the initial distribution, Mo then the following result can be proven invoking Lemma 3 and
G
Lemma 8. The following inequality holds Vt {0, (..1,...).
Elu 1 Cp VN
[ vui
(5p-1)
53 5p-1
Sp
where Sp - 5p + LQSp. The terms Sp are defined in Lemma while Cp is given in Lemma 6
A.3 Proof of the Theorem
Let π - (ne , and म A (o,). be two arbitrary policy-sequences in I. Denote by Nu",", ), {nf 2 the state, and action distributions induced by policy-sequence л at time an N- agent system, and infinite agent systems respectively. Also, the state, and action of i-th agent time corresponding to the same policy sequence are indicated as wh, and uf respectively. The same quantities corresponding to the policy-sequence मे are denoted {N v pi D7 2t ut}. Consider the following difference,
|MARL (00 )) - UM (No, m]
E
[ ui p. D - MF M. (ME Te)
1=0
<
E
x - MF (F. TT))
+
L1
MF (FL TT) MF (mL T
1=0
SJ
22
80
MF (M, Tt) MF M mt)
AJ
Inequality (a) follows from the definition of the value functions UMARI UMP(s)) given in respectively. The first term, J1 can be bounded using Lemma as follows.
6 and
10
MR
LR
JI
u
VVN
The second term, J2, can be bounded as follows.
J2
E MF (TI. 7.) - y MF M Ft)
(a)
7 { - - + SR (. =e(. p2,0
(6)
SR
>" "E 1
W
x [
V
SRCP Sp -
Sp
where SR A 5R + LQ.R. Inequality (a) follows from Lemma It remains to bound Jz. Note that, if मे = π, then J3 = 0. Hence,
whereas (b) is consequence of Assumption
Finally, (c) follows from Lemma
(M N TMARL) VMr VMr(Ho TMARL)) S Jo,
(34)
IUMARL TMP) UMF(M ThP) Jo
(35)
17

---

Published in Transactions on Machine Learning Research (09/2022)
where Ju is given follows,
MR
LR VN
M + vRIll (
SnCP
Jo -
vul
+ VN
Sp
SSp
Morcover, if π = MF, and क = MP (or vice versa), then J3 = 0 as well. This is prociscly because the trajectory of state, and action distributions generated by the policy-sequences TMPs 7MP are identical in an infinite agent system. Hence, we have,
IUMARL Mpp) UMP (Mo= Tip) S Jo
(36)
Consider the following incqualitics,
( 7 MARL) UMARL (2r ((F))
UMARL (a TMANL) UMF (Mop π MM) + UMF (p4: TMF) - UMARL (x #Mr)
(37)
(a)
UM T MARL) (M MARL) + Jo S 2Jo
Inequality (a) follows from 36 and the fact that TMP maximizes uMF(Mo:)) Inequality (b) follows from
34
Moreover.
( AMP) UM MARL)
UMARL #MP) UMF UMF(My: (Mo π RFF UMF UMF(My: TMF) UMARL (a TMARL)
(38)
(1)
Jo - (M TMF) UM TMF) S 2Jo
Inequality (a) follows from 36 and the fact that MARL maximizes UMARL +). Inequality (b) follows
from 35
Combining
and we conclude that,
UMARL (Z)) MARLL) - (MARL(Z)) #MP)) < 2Jo
B Proof of Theorem 2
The proof of Theorem is similar to that of Theorem Lemmas are needed to establish the thcorem.
| however, with subtle differences. The following
B.1 Auxiliary Lemmas
In the following (Lemma 11 (TT (Te E Il denotes arbitrary admissible policy-sequence. The terms {uN , h (o.1...... denote the N-agent empirical state, and action distributions induced by π from the initial state distribution, whereas {μ, u² heyo....... indicate the state, and action distributions induced by the same policy-sqquence in an infinite agent system. Similarly, {æt, ut (e denote the states, and actions of i-th agent evolved from the initial distribution, 4o via the policy-sequence, л. The joint states, and actions at time are denoted by æt u respectively.
Lemma The following incquality holds Vt I.......
- PMP (HN" TT)|, S 2
E
N 14+1
vN vIx
(39)
Lemma 10. The following inequality holds VI 10,1,.....
Mr
r ra u/, (N - MF (H+N m.) $
N
VN
18

---

Published in Transactions on Machine Learning Research (09/2022)
Lemma 11. The following inequality holds Vt {0, 1..., }.
Sp
Elu N Me S VN
x
Sp
where Sp Sp + LoSp. The terms Sp, Sp are defined in Lemma
The proofs of the above lemmas are relegated to Appendix J
B.2 Proof of the Theorem
We use the same notations as in Appendix
A.3 Consider the following difference,
UMARI (20 T - UNF (Mo- TT)
r r uit p.))
E 1r (1e mt))
ME
The thz p4,
MF M (TT tx))
+
7TE r MP (Thp" #e)
MP (T. Rt) 2
1=0
1=0
y |r (p. Te) - p (Mz ml)
Inequality (a) follows from the definition of the value functions (MARL(;))) uMr(s,) given in and 10 respectively. The first term, J1 can be bounded using Lemma as follows.
MR
J1 S
VN
The second term, J2, can be bounded follows.
J2
L MF (i mt) MF (TZ. Ft))
7
E [ - 13 + SR Fel-, F.N)
#e(- p2. 10
1=0
SR
"E|po - -
1=0
25n
X
Sp
SS
where Sn & S5R LqSR. Inequality (a) follows from Lemma
whereas (b) is consequence of Assumption
Finally, (c) follows from Lemma It remains to bound J3- Note that, if न then J3 = 0. Hence,
UMARL (2:6", TMARL. VMF (Mo: ग Maml)) S Jo.
(40)
[UMARI TMP) UMF TMP) & Jo
(41)
where Jo is given as follows,
MR
VRjl (
25
1 1 1-7Sp
Jn
1-7
Sp 1
1-7
19

---

Published in Transactions on Machine Learning Research (09/2022)
Moreover, if TMF, and π MMP (or vice versa), then J3 = 0 as well. This is preciscly because the trajectory of state, and action distributions generated by the poliey-sequences TMr AMP are identical in an infinite agent system. Hence, we have,
(UMARL (T #Mp)) - UMF (Mo- MP)) S Jo
(42)
Following the same set of arguments is used in (37 and 138
conclude that,
[UMARI MARL)
UMARL (MO: TMP) S 2Jo
C Proof of Lemma 2
Note the chain of incqualities stated below.
MF (1, π) MF (āe, R)11
Σ T(T,))((x) - - (((
ZE
xEX
Σ wEM
Σ t(z, (())((()))(z)
Σ (1)
ZEX
Σ
[I, (u))p(t) #(o, ())
ZEN WEW
$ Σ
[mx))) [x)) Σ Z(x, pu) Σ x(x)
(x) 5(x, (w)
xEX
xEX
uet
$ 4 111
Σ (ix))
sup LoEk
[Tx p1) #(2, 1111
TE
b F p + n 14) - 7 1o)
Inequality (a) follows from the definition of y (:) as given in 7 On the other hand, equation (b) is consequence of the definition of loo over the space of all admissible policies, II. This concludes the result.
MF
D Proof of Lemma
Obscrve that,
|MF (H,, T)
-PMF (fZ, 7)11
( ΣΣ
P(x, u. ,h, MF (1,, (e) P(x, u, pa, MP (īt, ()) ()())(()))
WEX well
< J + J2
20

---

Published in Transactions on Machine Learning Research (09/2022)
Equality (a) follows from the definition of pMp(;,) depicted in (8) The term J1 satisfies the following bound.
J 2
P(x, u. ,r, MP MM T)) P(x, u, Pr MP (i,, 7)),
(w)
DEX uELl
Lp lIu 14/2 + ( R) - MM ( R)12
Σ u(x) Σ (I,
ZEX
NEW
2Lp1u 10/1 Lp(T(s 12)
Inequality (a) is consequence of Assumption 2 whereas (b) follows from Lemma 2 and the fact that (2. pt) μ. are probability distributions. The second term, J2 obeys the following bound.
J2 -
P(x, u, n. MF (a,, 7))12 x (1) - x(x, ())
EEN wEl
<
Σ
lm(x) - x++r) Σ (1 - Σn a(x))
Σ
- - (w))
EE
ueul
ZEX
uEll
(a)
pal1 + (
sup
|T(2, 14) - #,x, ((t,,)11
Lre
FEX
| Ail + (, 11) T(, 100
Inequality (a) results from the fact that π (Ir, (1) is a probability distribution while (b) utilizes the definition of loo This concludes the result.
E Proof of Lemma 4
Observe that,
MF (1,,T) - MF (IZ,
(a) Σ Σ r(x, u, pe, MF (), (( - r(x, u, T. MF (ī, ()) ())
xEN wEll
J1 + J2
Equality (a) follows from the definition of MF ((5)) as given in 99 The first term obeys the following bound.
J 1 Σ
r(x,, u. pa MF (11,T) r(a,, u, ūz, y MF ( x))
uell
(a)
< LR [|ke 14/1 + MF (AA T) MF (MM +) x Σ n(x) Σ (T
ZEX
uell
(b) 3 2La/u fal1 + -R| -+(;)a)
21

---

Published in Transactions on Machine Learning Research (09/2022)
Inequality (a) is consequence of Assumption [ fact. that nI (2, pa); aa are probability distributions. The second term, J2 satisfies the following.
b) whereas inequality (b) follows from Lemma 2 and the
J2
Σ
|r(x, p. v
MF (f,
R)) x (m( - (4)
ZER' WEL
(a)
MR Σ
Σ
((. ()))((())
#EX NEM
$ MR Σ
|m(z) [(x)
Σ
T(x ()) +MR E
p(x))
Σ
(,( p)(x) - ((x, (u))
TEN
uEld
ZEX
uell
S MR μ 74/1 MR Σ (a())
sup (x(2, ( p))1
SEA
LEE
b
Malp 111 + Mn (T; 14) - 12)
Inequality (a) results from Assumption [a). On the other hand, equality (b) is consequence of the definition of boo, and the fact that is probability distribution. This concludes the result.
F Proof of Lemma 5
The following Lemma. is required to prove the result.
Lemma 12. vm E {1,-... M,, {Xmn (n,, .N are independent random variables that lie in [0, 1], and satisfy Eme(1,--,MM) [[Xmn]] S 1, Vn E (1,"., "o,",,,, NY, then the following holds,
N
E
(Xmm [m)) S VNN
(43)
172=
Lemma 12 is adapted from Lemma 13 of (Mondal al. 2022a
Notice the following relations.
E
MF (HE² mi)l1
1 - v MF (ML² mell [x;"]
E
IE
E
Σ (x ui Dos (xr)
xi
xEX
E
E
Uf (N))
Σ
me(a, M²" (1)) (x)
LEW
zex
N
N
E
Σ
E
Σ
5(14 = u)
Σ
te(a, 14 (1x)
Σ
{a = x)
x.²
N
N
Lue
1=1
x
1=1
E
Σ E
5(m) w)
Σ
n ( 14 (1u)
N
N
wEW
Equality (a) can be established using the definition of MF (:--) as depicted in 7 Similarly, relation (b) is a consequence of the definitions of n V.N. N Finally, (c) uses Lemma 12 Specifically, it utilises the facts that,
22

---

Published in Transactions on Machine Learning Research (09/2022)
(uilie(),...N)) conditionally independent given a." and the followings hold
E
(() u) x melats 14 (u);
o(u) u) bo = 1
ViE (1,-.. Vu
N,, u. This concludes the lemma..
G
Proof of Lemma 6
Notice the following docomposition.
E
PMf
Te)l
Pl,l u. u. ME (N. (F) (u)) 1 N Σ 5(x; = x')
E
6(xt
x)) Σ
Σ
N
x
x'EN wel
N
N
Σ E
Σ
8(1/+1 =x) N
P( U, N MP (M. (z))
N
xEX
T=1 WEW
$ J1
J2 J3
Equality (a) uses the definition of PMF (..-) as shown in
The term, J1 obeys the following bound.
N
J1
E
8(1141 = Σ
P( un u. vz (x))
N
ÆEX
1=1
1=1
N
Σ
EE
E
8( a1141 x)
P uh Ma 2x (x)) x.""
"u"" u²
N
#xX
Vix
N
Inequality (a) is obtained applying Lemma 12 and the facts that { are conditionally inde- pendent given {at"" u,") }, and the following relations hold
8(1)4) = x)) x un Plat, ubs u." v UN (x), | = x)) ae"" un² =1
E
ZEX
e (1, ,N, and Vz E X. The second term satisfies the following bound.
J22
2
1
E
Play u4 p. (x) Σ P uf ph M (N (z)
N
xEX
N
1
E P ui ui .NN) - P(x), w/ uN MP ( .m))
N
(6) Lp
LpE P.N
MF
MMN Te)l,
viu
VN
23

---

Published in Transactions on Machine Learning Research (09/2022)
Inequality (a) is consequence of Assumption while (b) follows from Lemma 5 Finally, the term, Ja be upper bounded as follows.
1
J3
E
P play uh uud" uM
LMPPHH (uL" mz))(z) Σ Σ P(x u, uot .M (ut (z)) p (2)
TEX
1 X
VN
Inequality (a) is result of Lemma 12 In particular, it uses the facts that, (u]be(1,- are conditionally independent given wN,, and the following relations hold
P(at, uhs uE MF (14 (1))
= E
Plat, MP (uf (T)) 14: )())
uEN
E
P(at us uz MF (ui", (x) aF" =1
Vi (1.... N}, and Vz E X. This concludes the Lemma.
H Proof of Lemma 7
Observe the following docomposition.
E
7 (z)
MF (u T&) 14 .NN)
N
1 N
(a)
E
r( u p1 UNN
ΣΣ
r(a, u, ME MF (H. (II /4 (2) N
Σ
5( =x)
N
xEX well
1=1
E
rla un, p. 1N
Σ we
rl u. uu MF (M m.)) μ (u)
< J1 + J2
Equation (a) uses the definition of y MF (..-) as depicted in
g The term, J1, obeys the following bound.
N
J
(a Ug pi N (N - Σ
rle uh un" MF (u TT))
N
|r(p un ph 12²)
raa uhs u MP M TE))
(0)
L L - MF (Nr Tehh
Lg
Viui
VN
24

---

Published in Transactions on Machine Learning Research (09/2022)
Inequality (a) results from Assumption whereas (b) is consequence of Lemma 5 The term, J2, satisfies the following.
N
J2
ra uh pi MF (uL" r+))
Σ
r( u, pe u (u me)) Me (u)
i=1 uEll
E
E
r ( uhs M4 N MP ( T+))
Σ
Σ
r r u. (n. TT) IT (1 u4 ( (w)
|ar
N
==1 well
MR
E
ro(4), u ur MP (ul Tz))
Σ
N
Σ
rolat, u, 14 MP (HL² Te) TT)) 14 (()) |20
N
REN
(a)
MR
where r)() A (/5M Inequality (a) follows from Lemina 12 In particular, it utilises the fact that (ufleeL,....N)) are conditionally independent given Lt, and the following relations hold.
Iro(zis ui ME (u," mz))) S 1, E ( uhi ui MP (FL" n.)) ax;"
Σ weH
u, ur MP (pL m.)))me(at 1z (u)
E (I.
Proof of Lemma 8
Observe that,
B N 14 E | pMP PM -e + E PMM (n (11-17 11,11
(a) Cp [VIz]+ vlui] + pMp (M (11-1, T(-) - pMp (4E=1:
Inequality (a) follows from Lemma and relation
Using Lemma
we get.
pMF (111117011) - PMF (1 1e-1)/1 < Sp 1112111 SplT, 16, (- Th-
T.-1 (:: (.
Splu - -12211
where Sp 25p + Lp Inequality (a) follows from Assumption Combining, we get,
Elp 11 Cp V +
U
SpE N
(44)
Recursively applying the above inequality, we finally obtain,
Cp
St. Sp
E 1
V
+
Vul
VN
25

---

Published in Transactions on Machine Learning Research (09/2022)
J
Proof of Lemma 9
Note that,
N
PMP
(11 N
TT)]1
141
N
N
5 =x) ΣΣ
Pla', u. p4 (I) ,4 N (u)
Σ 1=1
5(x) = x')
N
N
TEX
x'EA NEW
1 N
1 Σ P(u ( N
E
8(5(+1 =))
N
well
S J + J2
Equality (a) follows from the definition of PMF pMF(;,) depicted in bounded as follows.
The first term, J1, be upper
N
N
J1
E
6 = =x) - -
P ui p4 (z)
N
1=1
E
8(1 x)) Σ
P(x ut, 2e (xx)
x." u²²
X
Incquality (a) can be derived using Lemma 12 and the facts that (i are conditionally inde- pendent given {at" u," }, and,
8 = ==)=;"" un
P(at, uss p4 (x))
E
b( = x)) x; un² =1
#E
Wi (1. ... ,N, and Vz E X. The second term can be bounded follows.
N
N
J2
E
Σ
P(ri u (x)
P(af. u, ua (x) of (u)
PEA
2m well
X
VN
Inequality (a) is consequence of Lemina tionally independent given NN and
12
Specifically, it uses the facts that, (u. are condi-
P( ui, ui (a) a;
E u, uf (e) (u),
Σ E P(x ui uh (x) x;" =1 ZEN
Vi (1,... .,,,, and Vo E X. This concludes the Lemma.
26

---

Published in Transactions on Machine Learning Research (09/2022)
K
Proof of Lemma 10
Note that,
E
1
( u/: 14,") - ,,P - (uf (ufimm) m²)
N
N
r ur. 12))
ΣΣ
r(,, (a, ) (1)) N Σ
( x))
N
#Et ueu
N
1
E
( w/s m4
r u, 1a ( (oe( 14 (w)
N
N
:=1 well
N
E
( u/ )
Σ
Σ
r u, ue (oe 2 (ui) an
i=1 wEll
MR
E
E
ro uh u
ro m
mm D 1 (u) xx
N
1=1 uEl
(a)
MR
VN
where r _ r(..''5 's M/M Inequality (a) follows from Lemma 12 (ui are conditionally independent given x;"; and
Specifically, it uses the fact that
Iro(z), ut, m4 ) I 1, ro(uzs ui; u1,) |ar""]
E
Σ wEll
rolots u, u Dnel (u)
Vi E (1,.., ,N,,", Vu Eu.
L Proof of Lemma 11
Observe that,
E p 10 S [4 PMP PMMMMM ((- + +E
| (HH N
( TC-1) 11,01
(a)
| E PMF (1--1, Te-1) PMF (
Inequality (a) follows from Lemma and relation
Using Lemma 3 we gel.
pMM (n (u--1,7-11 PMF (n m
< Sp الب - 1, + Spl -T_ (414411)) Tz (4,
(a) Spluw 12
where Sp 2 Sp LoSp. Inequality (a) follows from Assumption Combining, we get,
E ENN 4i < V + SpE - 11-11
(45)
Recursively applying the above inequality, we finally obtain,
Sp Sp -
E Elp 1 <
This concludes the Lemma.
27

---

Published in Transactions on Machine Learning Research (09/2022)
M
Sampling Algorithm
Algorithm Sampling Algorithm
Input: Po: T P, r
Sample Zu Mo-
Sample up THy (No, Mo)
3: Mo + MF
MM (Ho) T
++0
FLAG < FALSE
while FLAG is FALSE do
FLAG < TRUE with probability 7-
Execute Update
end while
10: T +
11: Accept (IT, Mrr ur) as a sample.
12: Va, + 0, Qo, +0
13: FLAG < FALSE
14: SumRewards <- 0
15: while FLAG is FALSE do
16: FLAG + TRUE with probability -
17: Exccute Update
18: SunRewards < SumRewards + r(ae, ues M4; Uz)
19: end while
20: With probability 1, Pa, + SunRewards.. Otherwise Qo, + SunRewards.
21: As, (IT, pr, uT) +- 2( - Veg).
Output: (IT, pr. ur) and Aoo (Dr, pr, ur)
Procedure Update:
1: T1+1 ~ P(x,, Ut, M4g vt).
2: P411 -- pMF (Mes To,)
3: u141 TT. (1441,
y (M441: )
M+11
1+t+1
EndProcedure
28

---

Published in Transactions on Machine Learning Research (09/2022)
N Proof of Theorem 3
Note that,
sup UMARL (M0, TΦ) DER4
UMARI (4o: T
J
$ sup UMARL TT) - sup
UMF (Mo, TT)
+
sup #EB4
UMF (Mo: Tw))
Σ
UMF (Mu: T4,)
J
4EE4
DER
j=1
12
UMr (M:: TO,) (Mo To,))
==1
AJs
< sup |UMARI (M4: TΦ) &ERU
VMF TT)) +J2 + J3
Using the same argument as used in Appendix
A.3
we can conclude that,
J1 C1
X
u
Cie S C1 max(e,
C3
J3 S
X
+
u
Cze s C22 max e
for some constants C₁ C3. Moreover, Lemma suggests that,
J2 Ebias
tes 1-7 maxffee)
VEblas
Taking C= Cj + C3 + 1, we conclude the result. Under Assumption
using the same argument as is used
in Appendix B.2 we can improve the bounds on J1, J3 as follows.
J1 Ci
V
v N
C3
J3 <
V
N
This establishes the improved result.
29


Reviews:
[{"review_id": "XM4fBCX1rc", "reviewer": "Reviewer_84q8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths* -- The paper is well written. Although I did not check all details of the proofs, the methodology is sound and I believe that the obtained bounds are correct. I believe that the bounds are new, even if I there are more results in the related work on mean field control than what the authors claim.\n\n*Weakness 1: related work* --  most of the paper is focussed on studying the link between the control of a system with N objects and the mean field control problem and to obtain central-limit-theorem like results. While I believe that the bounds presented in the paper are new, these results are really close to the one provided in Theorem 55 and Proposition 12 of (Gast and Gaujal 2011): the fact that deterministic (a.k.a. time-dependent local policies) are optimal is also present in this paper.  Hence, a better discussion with the literature on mean field control and the bounds obtained in such cases is I believe missing. \n\n*Weakness 2: dependence of the bounds on parameters*\n- Also, the authors greatly discuss the dependence in \\sqrt{|X|} or \\sqrt{|U|} in the bounds. Yet, given that the bounds involve Lipchitz constants, the Lipchitz constant might also hide factors that are multiple of \\sqrt{|X|} (e.g. think of L_\\infty, L_2 or L_1 norms).  Is What is the impact of using one norm or another one? \n- When \\gamma is close to 1 the constant is infinity because \\gamma S_P will be larger than 1. I believe that this will essentially always be the case because S_P is likely to be at least 3 (unless L_P is smaller than 1). Moreover the dependence on L_Q seems strong and it seems that it is not present in (Gast and Gaujal 2011): is this dependence needed? Or is it a proof artifact? Or did I miss a difference between the results of (Gast and Gaujal 2011) and this paper? \n\n*Weakness 3: learning part* -- I am a bit puzzled by the learning part and I did not understand what is accessible to the learner and what is assumed to be known. I find the whole part quite unclear. In particular:\n- is Algorithm 1 specific to the current problem or is it just a reminder of an existing algorithm?\n- in Algorithm 2: how does line 3 works? Does each agent need to know the global P?\n- Equation below equation (20): either the notation is wrong or this does not defind a distribution. This might be due to multiple use of the variables (x,\\mu,u) having different meanings.  Similarly in Equation (19), the \"u\" seems to be once a deterministic variable, once a random variables in the expression A(u) = Q(u) - E(Q(u)).\n- sentences like \"The sample complexity of Algorithm 1 to achieve (22) is O(\\epsilon^{-3})\" are not precise enough for me: what is hidden in the O(.)? Do you consider a generative model?\n\n*Other comments* --  In the conclusion, authors talk about \"non-unniform\" interactions. There has been some progress on mean field about what is called \"heterogeneous\" or \"non-uniform\" models. On the topic of optimal control, one can refer to the paper by Brown and Smith (2020). This paper is about restless bandit, which are not the same model as the mean field control considered in this paper because the evolution of agents and constraints on the actions are not the same but they share the same \"mean field interaction\" structure.\n\n\nReferences: \n- (Gast and Gaujal 2011) \"A mean field approach for optimization in discrete time\" N Gast, B Gaujal - Discrete Event Dynamic Systems, 2011\n- (Brown and Smith 2020) Index policies and performance bounds for dynamic selection problems DB Brown, JE Smith - Management Science, 2020\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a multi-agent optimization problem in which the interactions between agents of of mean field type (this means that that the rewards and behavior of one agent depend on other agents only through their empirical distribution of states and actions). A controller wants to optimize the expected discounted reward over all agents. The problem is motivated by multi-agent reinforcement learning problems.\n\nThe paper contains two parts. The first one concerns mean field control. The authors show that there exists a (time-dependent) decentralized controller that attains a performance that is at most C/\\sqrt(N) of the best centralized controller.  An upper bound on the constant C is computed (note that it is likely to be infinite for large discount factors).  The second part concerns learning. The authors show how a natural policy gradient algorithm can be implemented in a decentralized way (although I am not sure to have understood if the algorithm is fully decentralized).\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Correct or discuss the 3 weaknesses mentioned above: \n- Better discuss the relationship with the existing literature on mean field control and the bounds that already exist. \n- Explicit the dependence of the bounds on the parameters \n- Clarify Section 7, notably by using more precise definitions and notations. \n", "broader_impact_concerns": "I do not think that a broader impact statement is needed. The paper is mostly of theoretical interest. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EhRMWtPFsw", "reviewer": "Reviewer_HZgm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe paper innovatively tries to solve the policy optimization problem in MARL under the mean-field control framework. To my best knowledge, there has been some work in the past that exploits the spatial structure of networks to address the curse of dimensionality in large-scale networks control. It provides a new way of thinking to analyze the problem from the perspective of mean-field control.\n2.\tThe article's analysis of the optimality gap is intuitive, and the proof process is solid as well.  \n3.\tThe author gives a very detailed discussion in terms of optimality theory, algorithm and even some special cases. The logic of the article is strict and exhaustive.\nWeaknesses:\n1.\tInterpretation could be deepened regarding the numerical experiment.  There are many assumptions made in the paper, and it would be better for authors to discuss in detail whether these assumptions hold in the current setting of the numerical experiment.\n2.\tFor the additional assumption (assumption 4) in the special case, the author is supposed to give some concrete examples to illustrate their rationality.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper aims to design locally executable policies with optimality guarantees. \n1.\tThe authors demonstrate that given an initial state distribution, it is possible to obtain a non-stationary locally executable policy-sequence $\\tilde{\\pi}$ that the average time-discounted sum of rewards generated by $\\tilde{\\pi}$ closely approximates the value generated by the optimal policy sequence $\\pi^*$.  \n2.\tThe authors use the idea of mean field control to solve the scalability problem in large-scale network. The authors show that, under the conditions that several common assumptions hold, the approximation error between the optimal control policy obtained using mean-field control and the real optimal control policy in MARL is tolerable, which is given by $O(\\frac{1}{\\sqrt{N}}) [\\sqrt{|\\mathcal{X}|} + \\sqrt{|\\mathcal{U}|}]$. Besides, they also prove that if the reward and transition functions do not depends on the action distribution of the population, the optimality gap for local policies can be bounded as $O(\\frac{1}{\\sqrt{N}}) [\\sqrt{|\\mathcal{X}|} ]$. \n3.\tThe authors also discussed how near-optimal polices can be obtained. Firstly, a NPG (natural policy gradient) based algorithm is used to approximately obtain $\\pi_{MF}^*$, then the obtained policy will be localized and executed in a decentralized manner.  The paper also demonstrates a numerical experiment to support the theoretical results.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1.\tPage 7, the equation between equation (16) and (17), it would be better to add absolute value notation. Although the result is correct, adding the absolute value symbol will make it easier for the readers to understand.\n2.\tIn the numerical experiment section, the authors are supposed to clarify whether all the assumptions made in the context are satisfied in the setting. \n3.\tIt would be better to give some concrete examples that satisfy the assumption 4 in the special case (page 5).", "broader_impact_concerns": "The paper illustrates the optimality gap between the optimal control policy obtained using mean-field control and the real optimal control policy in a MARL setting and presents a practical NPG-based algorithm to search for it in a scalable manner.  The case where the interactions between the agents are non-uniform is worth explored as the authors state in Section 9. Besides, the framework can also be exploited in the setting of other problem, such as LQR control. And other gradient methods (like PG case or Gauss-Newton case) can also be considered. This paper also provides theoretical support for potential practical applications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ENHISPOnTy", "reviewer": "Reviewer_1L6s", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe the direction that the paper takes is very important. The paper is well written and easy to follow. To the best of my knowledge, all the proves are rigorous. The observation that each agent can approximate the state distribution of a finite agent system by the infinite agent system in MFC (which can be obtained locally) is intuitive and new. \n\nThe work of Gu et al., (2021) shows the approximation of $O(\\frac{1}{\\sqrt{N}})$ between MF strategy and the optimal MARL strategy. In this paper, by replacing $\\mu_t^N$ with $\\mu_t^{\\infty}$, it can overcome the costly procedure of computing empirical state distribution. Therefore, following the work of Gu et al., (2021), theoretically, this paper only needs to bound the performance of $\\tilde{\\pi}^*_{MF}$ and ${\\pi}^*_{MF}$. However, in order to achieve the local execution, the current approximation error depends on the number of state and action $|X|$ and $|U|$, which will limit the application of the algorithm in many cases where the size of state or action are large. The authors find a way to solve this problem in special case where the reward function and transition function are independent of the action distribution of the population. In this case, the approximation error only depends on the size of state space $|X|$.\n\nIn the experiment section, can the authors provide results when both size of state and action space are large so that we can observe how severely the approximation will be affected?\n\n\nMinors: Equation (2): $(x)$ should be $(u)$.\n\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied the cooperate N-agent network problem in which the agents cooperate to achieve the optimal $\\pi^*_{MARL}$. Previous works require global execution in order to achieve the theoretical guarantee. However, in many applications, global information is impossible to collect and thus it is desirable to have a locally executable policy such as it still has theoretical guarantee. The authors suggest such algorithm which an approximation error of $O(\\frac{1}{\\sqrt{N}}(\\sqrt{|X|}+\\sqrt{|U|}))$.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "There is no major changes needed to make for now. I may need to add more during the discussion phase.", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a mostly theoretical paper about cooperative multiagent reinforcement learning (MARL) with N agents. There are several contribution of the paper: a bound on the distance of reward between local policies (that can be implemented by agents decentrally) compared to the globally optimal policy, an algorithm that computes the approximate optimal mean-field sequence of policies (upon which the local policies are based), and the formal relationships between n-player MARL case and mean-field control.

Every reviewer stated something about that clarity (either the quality of writing or the intuitive flow of the proofs / logic). In addition, I feel the presentation is particularly well-structured. This is especially difficult for a densely technical paper like this one. The contributions being made are clear and important to the growing field of MARL. There were several technical discussions from points brought up by reviewers, that the authors have included detailed responses in the submission system. If they have not already, I encourage them to integrate their responses into the paper text for improved clarity on these points, as readers are likely to have similar questions.
Decision: Accept (poster)