Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global State
Authors: Washim Uddin Mondal
Vaneet Aggarwal
Satish Ukkusuri
Venue: Accepted by TMLR ()

Abstract: Mean Field Control (MFC) is a powerful approximation tool to solve large-scale Multi-Agent Reinforcement Learning (MARL) problems. However, the success of MFC  relies on the presumption that given the local states and actions of all the agents, the next (local) states of the agents evolve conditionally independent of each other. Here we demonstrate that even in a MARL setting where agents share a common global state in addition to their local states evolving conditionally independently (thus introducing a correlation between the state transition processes of individual agents), the MFC can still be applied as a good approximation tool. The global state is assumed to be non-decomposable i.e., it cannot be expressed as a collection of local states of the agents. We compute the approximation error as $\mathcal{O}(e)$ where $e=\frac{1}{\sqrt{N}}\left[\sqrt{|\mathcal{X}|} +\sqrt{|\mathcal{U}|}\right]$.  The size of the agent population is denoted by the term $N$, and $|\mathcal{X}|, |\mathcal{U}|$ respectively indicate the sizes of (local) state and action spaces of individual agents. The approximation error is found to be independent of the size of the shared global state space. We further demonstrate that in a special case if the reward and state transition functions are independent of the action distribution of the population, then the error can be improved to $e=\frac{\sqrt{|\mathcal{X}|}}{\sqrt{N}}$. Finally, we devise a Natural Policy Gradient based algorithm that solves the MFC problem with $\mathcal{O}(\epsilon^{-3})$ sample complexity and obtains a policy that is within $\mathcal{O}(\max\{e,\epsilon\})$ error of the optimal MARL policy for any $\epsilon>0$.

Published in Transactions on Machine Learning Research (05/2023)
Mean-Field Control based Approximation of Multi-Agent Reinforcement Learning in Presence of a Non-decomposable Shared Global State
Washim Uddin Mondal
umondal@yurdue.c edu
School of IE and CE, Purdue University
Vanect Aggarwal
vanect@ppurduc.cm edu
School of IE and ECE, Purdue University
Satish V. Ukkusuri
sutbueur@purducc.ommm edu
Lyles School of Civil Engineering, Purdue University
Reviewed on OpenReview: https: // openreview. net/ forum? id= ZME2nZNTUY
Abstract
Mean Field Control (MFC) is powerful approximation tool to solve large-scale Multi- Agent Reinforcement Learning (MART) problems. However, the success of MFC relies on the presumption that given the local states and actions of all the agents, the next (local) states of the agents evolve conditionally independent of each other. Here we demonstrate that even in a MARL setting where agents share a common global state in addition to their local states evolving conditionally independently (thus introducing correlation between good
the state transition processes of individual agents), the MFC can still be applied approximation tool. The global state is assumed to be non-decomposable i.e., it cannot be expressed as collection of local states of the agents. We compute the approximation error as O(e) where e VN V + vu(.. The size of the agent population is denoted by the term N, and |x) U respectively indicate the sizes of (local) state and action spaces of individual agents. The approximation error is found be independent of the size of the shared global state space. We further demonstrate that in special case if the reward and state transition functions are independent of the action distribution of the population,
x/xi
VN Finally, we devise Natural Policy Gradient based algorithm that solves the MFC problem with O(e-3) sample complexity and obtains policy that is within O(max (c, e)) error of the optimal MARL policy for any > 0.
then the error can be improved
1 Introduction
Adaptive decision- makinn by a large number of cooperative autonomous entities in the presence of a changing environment frequently appearing theme many areas of modern human endeavor such as transporta- tion, telecommunicationss and internet networks. For example, consider the ride-hailing service provided by large fleet of vehicles. Not only those vehicles needed to be strategically placed to allow the maximum number of passengers to be served but such formidable task needs to be performed even in the presence of spatio-temporal variation of passenger demand. In this and many other similar scenarios, the central question is how a large number of agents can learn lo cooperatively achieve desired target. The framework of cooperative multi-agent reinforcement learning (MARL) has been developed to answer such questions. However, in comparison to the single-agent learning framework, the task of cooperative MARL is signifi- cantly more challenging since as the number of agents increases, the size of the joint state space increases exponentially.

---

Published in Transactions on Machine Learning Research (05/2023)
Several heuristic approaches have been designed to circumvent the aforementioned curse of dimensionality, Based on how the agents are trained, these approaches can be primarily classified into two categories. Tn Independent Q Learning (IQL) (Tan [993), the agents are trained independently. In contrast, centralized training with decentralized execution (CTDE) based methods (Rashid et al., 2018) train the agents in a centralized fashion. Both approaches avoid the problem of stale-space explosion by restricting the policies of each agent to depend only on its local state. Despite having empirical success, none of the above approaches can be shown to have an optimality guarantee. Another approach that has recently emerged as an excellent approximation tool for cooperative MARL with theoretical optimality guarantee is called mean-field control (MFC). It works on the premise that in an infinite collection of homogeneous and exchangeable agents, the behavior of an arbitrarily chosen representative accurately reflects the behavior of the entire population.
The guarantee of MFC as an approximation tool of MARL primarily relies on the law of large numbers which dictates that the empirical average of a large number of independent and identically distributed random variables, with high probability, is very close to their mean value. To utilize this property, it is commonly assumed in the mean-field literature, often implicitly, that the agents are each associated with a local state that evolves conditionally independently of each other (Gu et al. 2021). Unfortunately, in many of the practical scenarios, such an assumption might appear to be too restrictive. As an example, consider the ride-sharing problem discussed before. Assume that the local state perceived by a vehicle is the location of the potential riders in its immediate vicinity. Tf two vehicles are located far apart, their local states might be assumed to evolve conditionally independently. However, if they are so close such that their pickup areas intersect, then the presumption of independent evolution of states might not hold.
Does MFC-based approximation still hold if the local state evolution processes of different agents are cor- related? This is one of the most crucial questions that need to be addressed if mean-field-based techniques are to be adopted in a wide array of real-world MARL problems. In this paper, we establish that if each agent, in addition to their conditionally independently evolving local states, also possesses a common global state, the mcan-ficld approach can still be shown to be a good approximation of MARL. The global state is assumed to be non-decomposable i.e., in general, it cannot be expressed as a collection of some agent-specific local components. Note that, as the global state is common to all agents, the combined state perceived by each agent can now no longer be considered to be evolving independently. As a result, the techniques that are commonly applied to show mean-field approximations can no longer be directly used. We address this challenge by showing that instead of naively applying the previously developed methods, if the problems are transformed to an equivalent but slightly different representation, then we can find new variables that evolve conditionally independently of cach other and help us break the correlation barrier.
1.1 Our Contribution
We consider a network comprising N number of agents, each associated with a local state space of size X)), a non-decomposable global state space of size [G] and an action space of size [u]] (all are assumed to be of finite size). Given the global state, local states, and actions of all agents at time 4, local states at ++I are presumed to evolve conditionally independently of each other. The combined (local, global) states of each agent, however, do not evolve conditionally independently. We prove that the mean-field control- based approximation results can be applied even in the presence of such a correlation. We quantify the approximation error to be O(e) where e A VN + viu]. Note that the expression of e is independent of (9), the size of the global state-space. In a special case where the reward function and both the local and global state transition functions are assumed to not depend on the action distribution of the agent
i.e., it becomes independent of the population, the approximation error is shown to improve to e = VN
size of the action space.
In traditional MFC (with no non-decomposable global state), one of the crucial steps in proving the MARL- MFC approximation error is upper bounding the term Elu - Mula as ((1/VN) where μa² and μ, are the state-distributiinn of the N-agent and the infinite agent systems respectively at time The key intuition in proving this bound comes from the fact that ya (z) can be written as the average of the random variables (d(x)- = = where of is the state of the ith agent at time t. Moreover, the above-mentioned random
2

---

Published in Transactions on Machine Learning Research (05/2023)
variables are independent conditioned on -o-1- This allows one to use the law of large numbers and obtain the desired bound.
If we follow the same footsteps in our setting (with a non-decomposable global state), we will end up with the term Ex,g N-agent and the infinite agent systems respectively. Note that, we can write μ (x))(ge) g) as the average of the random variables {ő(z) z, g. = ;; Due to the common factor 8(g," = g), the above-mentioned random variables are now correlated, and hence the law of large numbers can no longer be applied. This is essentially the primary challenge addressed by our paper. We invent new techniques to prove approximation guaranlees even in the presence of a uon-decomposable state. The details are provided in section G
= 9) ue (z) = g)1 where g." and Ii are the non-decomposable states in the
Finally, we develop natural policy gradient (NPG) based algorithm and using the result of (Liu et al, 20200, and our own approximation guarantee, establish that the proposod algorithm generates a policy that is within (e, +)) error of the optimal MARL policy for any >> O. Moreover, the sample complexily bound for obtaining such a solution is shown to be Oce
1.2 Related Works
Single Agent Learning: Pioncering works in the single agent learning setup includes various finite state/tabular algorithms such as Q-learning (Watkins and Dayan 1992) and SARSA (Rummery and Ni- ranjan 1994). Despite having theoretical guarantees, these algorithms did not get adopted in large-scale applications due to the huge memory requirement. Recently, neural network (NN) based Deep Q Learning (DQL) (Mnih ct al. (015)) and policy gradient-basod algorithms (Mnih et al.] 2016) have garnerod popularity due the large expressive powers of NNs. Nevertheless, due to the exponential increase in the size of the joint state space with the number of agents, these algorithms are far from being the panacea for large-scale
MARL problems.
As stated before, the idea behind centralized training and de- centralized execution (CTDE) based approaches is to restrict the policies to solely take the local state of the associated agent as an input. Depending on how such local policies are trained, various algorithms have been constructed. For example, VDN (Sunehag et al.] 2017], trains the local policies by minimizing the Bellman error corresponding to the sum of individual Q-functions of each agent. QMIX (Rashid et al., 2018), on the other hand, computes the Bellman error corresponding to the state-dependent weighted sum of the Q-functions of each agent. Various other CTDE-based algorithms are WQMIX (Rashid et al. 2020), QTRAN (Son et al. 2019) etc. Parallel to CTDE, IQL-based algorithms have also garnered popularity in large-scale MARL (Wei et al.] 2019). Alongside these houristics, there have been some recent offorts to theoretically characterize the ellicacy of the local policies Qu et al. (2020) ; Lin el al. [2021) Mondal et al. 2022c However, none of them include a common global state.
CTDE-based Approaches for MARL:
Mcan- Control (MFC): MFC is relatively recent development that solves MARL with thcoretical optimality guarantees. Gu et al. 2021 exhibited that if all the agents are homogencous and exchangeable, MFC can be used as good approximation of an N-agent problem. Later, similar approximation results were proved for K-class of heterogeneous agents (Mondal et al. 2022a) and non-exchangeable agents (Mondal et al. 2022b). Morcover, various model-based (Pasztor et al. 2021 and model-free (Angiuli et al., 2022) algorithmss have been developed to solve the MFC problem. We would like to point out that our framework is closely aligned with the framework of MFC with common noise (Motte and Pham 2022; Carmona et al., 2019). However, (Motte and Pham| 2022) only considers open-loop policies which are essentially sequences of actions, rather than state-to-actin (Carmona et al.] 2019) do consider closed-loop policies, they do not show the convergence between MARL and MFC as a function of the number of agents. Empirically, MFC has found its application in a diverse range of scenarios, including epidemic management. (Watkins et al. 2016), congestion control (Wang et al. 2020), and ride-sharing (Al-Abbasi et al. 2019
maps (also known closed-loop policies). On the other hand, although
Beyond Mean-Field Control: The presumption of homogeneity of the agents turns out to be too restric- tive in many practical scenarios. Graphon mean-field control (Caines and Huang 2019) is an emerging new
3

---

Published in Transactions on Machine Learning Research (05/2023)
area that attempts to do away with the presumption of homogencity. However, explained in Mondal et al. 2022b), such approaches also come with their own set of restrictions.
Bean-Field Games: Similar to MFC, mean-field games (MFG) attempt to characterize the behavior of an infinite number of agents in a non-cooperative setup. In contrast to MFC, the goal of MFG to identify the Nash equilibrium of the system (Flie al. 2020 Yang et al. 2017
2 MARL with Shared Global State
We consider a collection of N interacting agents each with a local state space X' and an action space U. At instant t, the local state and action of the ith agent are respectively indicated by z4. uf. In addition to the local state, at time I, each agent also observes a global state ge whose realizations space, G. The collection of local states and actions of all agents are expressed as a; u respectively. Given the tuple (xr)) . u the local state of ith agent at time ++ 1 is given by the following transition law, 2it1 ~ (1 96 It is assumed that the random variables { /==1- At time t, the (expected) reward received by the ith agent is denoted as r; . w²"). Let μ vi indicate the empirical state and iction distributions of N agents at instant I which are defined respectively as follows.
from the global state
N ). Similarly, the transition law for the global state is given as g ~ Pa(x, N gf u.). 1N 1- are independent, conditioned on {æ Ii u
A
1 N
Σ
vx EX (xt = x), Vx
(1)
i=1
N
A
8
(ut u) Yu Eu
(2)
1=1
where 5(-) is an indicator function. We assumee the agents to be homogeneous and exchangeable. Hence, the reward and state transition functions can be writlen as follows.
N N N N ) = r- ugy Mi 96 V ( It (= N gi u. Plat, ui Hi N
(3)
Ii N )²²)
(4)
Pa gf. u PolH, Ii ,NN)
(5)
where r, P, Pa are given as follows: r x xxxx)xxxAAAC A(U) R, x: + A(X)
and Pa: A(X) x G x A(U) + AG)). The symbol A(S) defines the probability simplex defined over the set S. Note that 5 is written with a slight abuse of notations.
A policy ग. is a function of the form, ne X' A(X) x G + A()). In simple terms, a policy is recipe for the agents to (probabilistically) choose actions based on their current local states, the empirical local state distribution of all the agents, and the global state [ Let π 2 (Te)e } be a sequence of policies. The value generated by the sequence π corresponding to the initial state (x 96 is defined as follows.
N
Vi :
g6t
π
E
Mnla of ux²)
N
(6)
1 N
Ar( un uf of vNa)
E
where the expectation is taken over all trajectories generated by the policy sequence л starting from the initial states SeN.g." and 7 E (0.1) is the discount factor. The target of MARL is to compute policy sequence that maximizes (m: 96 .)) over the set of admissible policy sequences Te A IxIIx.... where IT is the set of admissible policies. In the next section, we shall discuss the mcan-field control (MFC) framework that can be used lo approximately solve the MARL problem.
Here we implicitly assume that all agents execute the same policy. This is primarily hecause the agents presumed have the same reward function and ttate-transition function (Gu al. 2021 Pasztor al. 2021
4

---

Published in Transactions on Machine Learning Research (05/2023)
3 Mean-Field Control (MFC) Framework
In this setting, consider the size of the agent population to be infinite. Due to homogeneity, we arbitrarily select representative agent whose local state and action at time t are defined as 2,, and respectively. In addition, let Sr indicate the global state at time Let Pe Mr be the distributions of local states and actions at time over the infinite agent population. For a given sequence π = {Te define the following.
Vr = MF (1e, St, TT)
Σ ZEX
The above relation demonstrates how the action distribution Ds can be obtained from the local state distri- bution Me and the global state dr. Now we quantilatively describe how Pe+1 the local state distribution at + 1, can be obtained from ba an 9t-
Ml+1 = Σ ΣEU TEX NEll
P(x, u, pe: 9t, MF (H4, 9t, (1. mz)) x Tela, (1) a pMF (p,:
(8)
Define X A P 9t- Vt-1), 1 12 and A - 1(go) where 1(g)) indicates a one-hot vector with a nonzero element at the position corresponding to go- Intuitively, A, denotes the conditional distribution of 9t given (14-1::9-1,, Note that the following relation holds AI 2 0.
MM A411 = PG (Pr. Te)
Po(me: 91, v MF (11.9t. nz))
(9)
Finally, the average reward at time t is expressed as follows.
MP (1:: xT)
Σ
Σ
(e(2, M2, (.)( x p,(x) r(x, u, Mes Sc. MP (p. T())
(10)
*EZ' wEM
The mean-field value generated by ग = {me)ee(0,1...) for a local state distribution M4 and global state go is expressed as follows.
Voo (Mo 9o. πT)
" MF (H,, St. nz)]
(11)
where the expectation obtained over {gt (g where gt+1 ~ Pa (Me It, Te), M4+1 = pMF (M 9t. Tt), 2 The goal of MFC is maximize the function V (Mo- Io over the of admissible policy soquences, Ie In the following section, show that the optimal value of MARL is approximately equal to its associated optimal MFC value.
4 Approximation Result
We shall first dictate some assumptions that are needed to establish the main result. Assumption 1. The functions r, P and Pa are assumed to follow the following relations Vpn, 12 E A(X), v2,,02 E A(U), Vr X, Vu E U, and Vg E g
(a) |r(,, u U,r, 9, s MR
(( r(z, u, pzz g, v2)l S LR( - H2l1 + l 22213
(c) (( P(æ, u, p2 9 v2)1 < Lp(1 12l1 +| v2211 (d) (Po(M),9,11) Po 12) Lolly Mela + |11 12111
The conslands La, Lp are arbitrary positive numbers. The function
|. denotes the I -norm.
5

---

Published in Transactions on Machine Learning Research (05/2023)
Assumption aa states that the reward function is bounded within the finite interval [-MR. MR]. On the other hand, assumption [b), [e), and dd) respectively dictates that the reward function, r, the local state transition function, P and the global state transition function, Pg are all Lipschitz contimuous with respect to their local state distribution and action distribution arguments. Such assumptions are common in the
literature (Paszlor et al. 2021; Hinderer 2005 Gu et al. 202T). We would like to point out that although the state and action distributions are treated as continuous variables, in an N-agent problem, they can only take finite number of values in their respective probability simplexes. In the MFC problem, however, these variables can be arbitrary. Therefore, while comparing the N-agent and the MFC problem, are implicitly extending the domain of definition for the reward and the state transition functions.
Assumption 2. The set of admissible policies, II is such that any π II satisfies the following inequality Vz E X, V2, H2 E ((2), and Vg g.
(I(z,11.91 9) T(E, U2: 92: S Lo 14 12l1
Assumption 2 states that the set of admissible policies is selected such that each of its elements is Lipschitz continuous with respect to their local state distribution argument. Such assumption typically holds for
neural network (NN) based policies with bounded weights (Mondal et al. 2022a. Pasztor et al. 2021 Cui and Koeppl p021p.
We now ready to state the main result. The proof of the theorem stated below is relegated to Appendix
Theorem 1. Let Do of æg. If Assumption 1 holds and the set of admissible policies, II satisfies Assumption g then the following relation is true whenever 7Sp < 1.
(= and 90 be the initial states and Po denote the empirical distribution
sup Vx 90, T) sup Vx (Mor go: T))
MR + LRV
1
M MnLay
sup [Vv(2o, 20. T) Vo (Mo: 90.
+
1 1-7 7
N (1 7)2
n
+((C=) ) [
MRSC + +R 1p
{1-75p
{
1
1
MMRS 7)
[
Viul
1-7
VN
where Sp e 1 (1 + Tp), Sn 2 Mn + 2T TQ + IR),, Sa A La - LQ) and Cp 2 Suprema are performed over the class of all admissible policy sequences, 1
Theorem states that if the discount factor y is sufficiently small, then under assumptions I and 2 the optimal N-agent value function is at most O VN Vixi + vul) error away from the optimal mean-field value function. In other words, if the number of agents, N is large and the sizes of local states and actions of individual agents is sufficiently small, then an optimal solution of MFC well approximates the optimal solution of a MARL problem as described in section 2 Interestingly, notice that the approximation error does not depend on the size of global state space [9]. Thus, the approximation error can be kept small even when [9] dramatically large or even potentially infinite.
Let, TMF E ! be an admissible policy sequence that solves the MFC problem with accuracy. Note that,
sup VN (0. So. T) - VN So. न
MF < sup Vw
9o, 9o. π) - sup Voo (Mys 9o. m)
+ sup Voo (p So. T) Voo (M 9o. π MF | + (Mp: 9o. n MF)
VN 9o. ग MF
AJ
The terms J3 can be bounded by Theorem I while J2 can be bounded by e. This result suggests that if we come up with way to approximately solve the MFC problem, then that solution must be good proxy

---

Published in Transactions on Machine Learning Research (05/2023)
for the optimal MARL solution. Before discussing the algorithmic aspects of solving the MFC problem, we would like to first discuss special case where the approximation error can be lower in comparison to that stated in Theorem [
5 Improvement in a Special Case
In this section, we shall demonstrate that certain structural restrictions are imposed on the reward and state transition functions, then the approximation error statod in Theorem | can be improved further. In particular, the assumption imposed the stated functions be mathematically described as follows. Assumption 3. The following relations hold Vu E ( Ae E A(U), Vo E X, Vy E G, Vu E U,
(a) r(z, p.g. = =r r,,, 14
(6) P(æ, U., = u,
(c) Pelu.g.v) = Palu,
Note that the above relations are stated with a slight abuse of notations.
Assumption dictates that the reward function, r, the local state transition function, P, and the global state transition function, Pg are independent of the action distribution of the population. We would like to point out that the functions and P may still depend the action of the associated agent even if they are independent of the actions of others. In Theorem 2 we discuss the implication of Assumption 3 The proof of Theorem 2 is relegated to Appendix
Theorem 2. Let wo
and go be the inilial states and pg indicate the empirical distribution of & hold and the set of admissible policies, II obeys assumption then the following relation is true whenever 7Qp 1,
(ri
Co. If assumptions
1 and
MR
X
sup VN T sup Voo (4t T])
1-7
VN
x Qp ) [ ( + QR)) { [T- 1-7
MRLL
Qp -
71-
where Qr _ + Lpp + LQ and Qn & Mn(1 + LQ) + LnR- Suprema are computed over the set of all admissible
policy sequences, _
Theorem 2 dictates that if the reward, r, and state transition functions, P and Pe are independent of the action distribution of the entire agent population, then the approximation error can be improved to
O v x
Therefore, in addition to large global state space, such system can also afford to have large action space without compromising the MFC based approximation accuracy.
6 Proof Outline
Here we present brief outline of the proof of Theorem The proof of Theorem 2 similar. In order describe the proof steps, the infinite agent value function given in [1] needs to be written in an equivalent but slightly different representation.
6.1 An Equivalent Representation
Let us focus on the expected infinite-agent reward at time 4, denoted by the expression MP (M St. mt)). Note that, starting from Po.90. the sequence of local state distribution and global states ((),))) I {1,".,,t f} can be recursively obtained as follows.
P1+1 = pMF (p419t, mi)
(12)
g++1 PMF (1, m)), LE ....... ,t-1)
(13)

---

Published in Transactions on Machine Learning Research (05/2023)
where PMF, P are defined in |/. (9) respectively. Note that (12 is deterministic relation. Therefore, if
we fix particular realization of the global states {mi), / E (,,',, - 1}, then, by recursively applying 112
M141 can be written as follows, vI E {0,
1}.
P141 PMF (Mo. 90:1: Todl
(14)
è PMF (s,9t, m.) o pMp (s, T1-1) PMF
(,,91, (M PMF (s,90: m14
where indicales fuuction composition, 90d - (yo.... 91 and mod - (To, ... m.. On the other hand, recur- sively using (13), the probability of occurrence of particular realisation of the sequence gitt - - .ge can be written follows.
P(gna Po: So. -0a & PMP (Mos 9o: (g1 x ... x PMF (1, Te- Te-)
(15)
For notational convenience, we denote this conditional joint probability as PMF 1, In- voking 14h
this can be alternatively written as follows.
PM (Mo: 90:111 90 PM (1o: 9o: (9)(1) x P (PMP (pos J0:0: 91, (1)
(16)
x ... x PMF (PMP (Ho: 90:t-; To.-22) It-1; -t
Using these notations, we define MM (Mo: 9o. Tox) & ElrMF (H, It, Tx)] as follows.
MM
(No: Jo, Toa) A
Σ
P (Mo, 90xt (99)) x MF (PMP (Nos 90--1, mo: St, Te)
(17)
1:t
where E1et is the summation operation over Iıa E G' for t 2 1. For = 0, we define MF (Mg: 9o. Taa) A
n.MF (po: 90: mo).
6.2 Proof Outline
With the new representation defined above, we are now ready sketch brief outline of the proof.
Step 0: Recall from the definitions 6 and that both N-agent and infinite agent value functions are 7-discounted sum of expected rewards. To obtain their difference corresponding to a given policy sequence, π { (o. J we therefore must calculate the difference between the expected N-agent reward at time and the expected infinite agent reward at time f. Mathematically, this difference can be expressed as follows.
AR
A
E [r
ui ui of DN - E (P (1,
N
==1
where all the notations are the same as used in sections and g
Step 1: We upper bound AR, as AR < SR + ARE. The first term is given as follows.
N
AR
A
E
r r uhs N G vNN) - MF (,,"" . mT)
N
1=1
We show that AR. O (VIu1/N) in Lemma
13 (Appondix A.30.
The second term AR the following.
AR? A MF (NN gf TT] Ely (m Gt. TT)]
(18)
8

---

Published in Transactions on Machine Learning Research (05/2023)
Step 2: Using the definition of FMP in section 6.1
can write, BFr (uf 96 -T)) B[ (HÂ gi T&a)
and BB (14, St, πz)] FMF
(Mo: Do: To:t) = E (oo Jo, mo+t)]. We now further bound ARE as follows.
A
BETME (uf² oft Tea)l B[GMF (Mus 9u. To:e]l
ET (u gh T++1+)] 1EG (N gh Tk:t]]
(19)
[B[ (1i+1 Pe+1, 1++1:)] - E[AMF (uÉ IN mml)
k=
BARG,
In the above inequality, we implicitly use the convention that 1 = No: 9n NN = 90- Equality (a) is essentially a telescoping series.
Step 3: We shall now focus on the first term ARE Note that,
E
(HE+1)
Ph+11 #K+1:t)]
E
MF
(1 Be Tb+1a)) uk gh 2
E
E
MF
9 of u (o) .f Ih v
DEG
E
MF
(kk+1:9 1e+a)) Ih v IN (g)
gEg
where (a) follows from the fact that u oht are conditionally independent given n gh Va and ghtz Pa(u ah ).
Step 4: Using Lemma
9 (stated in Appendix A.2
expand the second term of AR k follows.
BB MF (H I Taa)) = E Σ
Pa N MP ( 9k N mx))(g) x MP (PMF (M 9h (k). m.)1a)
DEG
Step 5: Lemma 8 (Appendix A.2 shows that 5MF (M Tk) ) is Lipschitz continuous with a (k, te-eeedndent Lipschitz parameter for any 9, 1x- Therefore, one can write the following.
MF (p T&+1a) MF (PMF (pr Ie Tk). me)4a)))) = O (1u PMF (pL Ik mx))i)
N
The leading constants in the above bound are (k,t) dependent. In Lemma 12 (Appendix A.3 show that,
further
9 N TR) - (+ Mix M
E
M++1
N PMF pM
Using Assumption [d), one can write the following for any choice of p 2h ux and mes
IPolu N gh U Pa( gh v
MF (HE gh mz)) S La NN - MF (HE de Tw))
Moreover, in Lemma
(Appendix A.3), show that,
V
E D MF (ML oh mw)1, =0
VN

---

Published in Transactions on Machine Learning Research (05/2023)
Combining all these results with the expansions obtained in steps 3 and 4, we finally conclude that,
A ARE. = (
1 [
+ vRu))
where the leading constants are (k. dedeennett
can obtain bound for ARi which, combined with the previously obtained bound for AR yields a bound for AR, We finally obtain the difference between N-agent and infinite agent value corresponding to æ by computing the upper bound of the sum E 7 AR. We would like to point out here that the leading coefficient of AR, turns out to be exponential function of I. In order for the sum to converge, one must have Y to be sufficiently small.
Step 6: Substituting the bound of AR in 19
Step 7: We establish the desired result by observing that |sup (x 90, π sup, Vo (My 9o, TT| S supx (Zo, go: π - Va 9u, π) where the suprema are calculated over the class of all admissible policy sequences 11
(u:
We would like to conclude this section by pointing out how our proof technique fundamentally differs from the techniques used in the existing papers such as Mondal et al. (2022a); Gu et al. (2021) where the common global state is not considered. Note that in absence] of the shared state-space G. the infinite agent state distributions (pelre(o.1...) are all deterministic and the error AR, defined in (18) can be bounded as,
AR A BB (m Te)] Efr-MF (14 Tz)l
(20)
E MF (14 N TT) MF (14, Tb)
(a) O (ElN Mol1))
Relation (a) is proven by establishing that rM (e) is Lipschitz continuous. The error term Blu," - Hel shown in (20) is bounded by establishing a recursion on t. Unfortunatcly, such simplified recursion does not hold once the global state space is introduced. In our analysis, we rather need to keep track of the whole The need to trace out convoluted trajectories and
trajectory induced by the policy sequence, Taa for the lack of any simplified recursion makes our analysis much more difficult and incompatible with the proof techniques available in the literature.
7 Algorithm to solve MFC
In this section, present natural policy gradient (NPG) based algorithm to obtain an optimal policy for the mean-field control (MFC) problem. As clarified in section 3 the size of the agent population is presumed to be infinite in an MFC framework and we can arbitrarily select any agent to be representative. Assume that at time / the representative agent chooses an action u, E l after observing its local state 24 E X, the global state 9t E G, and the distribution local states all agents denoted by H, E ( The goal of MFC, therefore, reduces to maximizing the discounted expected reward of this representative agent. Clcarly, it is a single agent. Markov Decision Process (MDP) with a state space of X' A
and action space U.
Without loss of generality, we assume that the optimal policy sequence is stationary PPtterman 2014 Thcorem 6.2.12). Note that the collection of admissible policies is denoted by the set II. We assume that the elements of II are characterized by a ad d-dimensional parameter 4 E Rd. In the forthcoming discussion, a policy with the parameter will be denoted as To whereas, with a slight abuse of notations, the stationary sequence generated by it will also be denoted as Tạ. Let the Q-value corresponding to the policy कe defined as follows Vz, p. g, u.
Q0(2.
E Σ rrr ue, p2s St, vz) xo = x, M4 = μ4, 9o = 9, 24 = u
(21)
where the quantitics b4 and Vs are recursively calculated by applying (8) and 7 respectively. Morcover, the
expectation is taken over Z ~ P(x,, Wt Pt: Mt); 4s ~ Th (We, p4p )r and gt+1 ~ Pa(u v.), Vt 2
2This can considered special case of our model by imposing [G]
10

---

Published in Transactions on Machine Learning Research (05/2023)
The advantage function corresponding to nh is defined follows.
As s4 1. u) - (x u4 g, (I
(22)
where the expectation is over v' ~ (T,
Let 14 E (A)) be the distribution of initial local states and go be the initial global state. Define V (Ho 90) - supøErd Vo (M 90: mT) to be the optimal mean-field value obtained over the collection of admissible policies, II corresponding to the initial state (fo: 9o). Assume that { | is a sequence of dimicnssional paramcters
generated by the NPG algorithm (Liu al. 2020 Agarwal et al. 2021) as follows.
23 + j, W arg min WERd
min L
(w, 22)
(23)
S(gg.90)
where y > O is the learning parameter. The function L below.
and the occupancy measure (pp..o)) are defined
(40
[[ (A 14, u) 7) V log N u4, s.)))
Leg (w, D) SE BB (0,1.,)))) - (10:900)
(24)
(0 u. (o.
(2,
Y P(e, =I,,, p. = =. = u/20 = Ma = g0
g, 40 = TT. 7)
(25)
Note that order calculate the update direction, Wy at the j-th NPG update 23 we must solve another optimization problem over Rd. The second minimization problem can be handled via stochastic gradient
descent (SGD) approach. Particularly, for given 2y E wd the minimizer of L ey ((a
(-, b) can be obtained
via the following SGD updates: W,.+1 Waa- a,, Liu et al. 2020 where a >> 0 is the learning parameter for the sub-problem and hy2, the gradient at the 1-th iteration is given as follows.
h
w T Wi Vo, log To, (I, ()) 1 As, (2, p. u. V log To, (z, (u)
(26)
where the tuple (z. g. u) is sampled from the occupancy mcasure X and As, (I. p. u) denotes a unbi- ased estimator of As, (xr, 11 9, u). The sampling procedure and the method to obtain the estimator has been
described in Algorithm 2 in Appendix V It is to be clarified that Algorithm 2 is based on Algorithm 3 of
AAgarwal et al. 2021). The whole NPG procedure is summarized in Algorithm
Based on the result (Theorem 4.9) of (Liu et al. 2020), in Lemma | we establish the convergence of Algorithm and characterize its sample complexity. However, the following assumptions are needed to prove the Lemma. The assumptions stated below are respectively similar to Assumptions 2.1, 4.2, 4.4 of [Liu et al. 2020).
Assumption 4. vD Rd, Y(po go) E A(X) G, for some x 0, Fi (8) xla is posilive semi-de defile where (1)) is defined stated below.
F F( (Φ)
A (E
u. (V) x (v log (2 (2.
Assumption 5. VD E Rd, Vp E A(X), VI E Ag E EG, Vu E u, the following holds
V na (z, u. (1)) S
for some positive constant G. Assumption 6. ve,, t2 E IRd, Vp E A(X), Vr X, Vg e, Vu EU, the following holds,
V log T4, (I, 4. (u) Va, log (I, u. (1)) & M - 2211
for some posilive constant M.
11

---

Published in Transactions on Machine Learning Research (05/2023)
Algorithm Natural Policy Gradient
1: Input: n, Learning rates, J, L: Number of exccution steps
Wo, Po: Initial parameters,
Ho: Initial local state distribution
96: Initial global state
Initialization: + 20 , 1} do
for {0, 1,
5,0 Wu
for / E {0, 1,
161-1 1) do
Sample (I., H4 9: u) (0) and Ao, (x. p. u) using Algorithm
7: Compute b using 26
8: W,J+1 t WjJ - ahj,
end for
10: Wj f I Σ1= Wjj
11: 1 t 23 + 1/W
12: end for
13: Output: {#1, ... . Policy parameters
Assumption 7. vΦ e Rd, Y(uo: go) A(X) x G,
L (Mguse)
(wip, 1) bblas: wg. - arg min Lu
(w, (
Smmp 90)
where 4² is the parometer the optimal policy-
Remark 1. Nole that Assumplion 7 is trivially salisfied with ebas
2M 2MR/(1-7)) Assume that, U (1,2),
and restricted class of parameterized policies is defined as follows.
cxp($) Te (x (. = + exp(4) 1 exp((1)
where (x. (1 E X' A(X) x 9, and + E [-C, for some constant, & >> 0. One can check that, for the set of policies stated above, assumptions are satisfied with X exp((2)/(L exp(E)) G G= 1, and M 1/4.
We are now ready state the convergence result which is a direct application of Theorem 4.9 of [Luu al. 2020).
Lemma 1. Let { be the sequence of policy parameters obtoined from Algorithm
If Assumptions 4
(1->)?x
hold, then the following inequality holds for 4G' a , J O (1-))
L = (1-9]tt)
J
VO (Mo: 90)
Σ
E V (Mo: 9o. no,)
Ebias
+ 6,
for arbitrary initial parometer 2o, initial local state distribution My A(X) and initial global state go- The parameters {MR, x, M} are defined in Assumptions
respectively. The term Cias is positive
constant. The sample complerity of Algorithm 1 is O(e
The term Cbias introduced in Lemma is termed the expressivity error of the policy class II parameterized by the d-dimensional parameter. For dense neural network-bascd policies, Obias appears to be small LLu
et al. 2020
Lemma I states that Algorithm I can approximate the optimal mean-field value, V (Mps go) for any (Ho.90 9o) e
( G with an error bound of c, and a sample complexity of (c--3). The constant term hiding O(.) is dependent on the parameters (MR, X, G, M) defined in Assumptions Theorem
Combining Lemma with
arrive at the following result.
12

---

Published in Transactions on Machine Learning Research (05/2023)
Theorem 3. Let To _ (20),e(1,...,)) and gu be the initial local ond global states respectively and Mo be the empirical distribulion of To. Assume that { are the policy porameters generaled from Algorithm 7 corresponding to the initial condition (Hu, 9o, 2o), and and the set of policies, 11 follows Assumption @ I
assumptions 1 4 7 are true, then, Ve 0, the following inequality holds for the choice of the parometers {1, ax J, L) staled in Lemma
J
(a 90)
Σ ==1
E Vo (Mu. TT,)
5
v
Ebias
+ C' max
1
1
where (Z0. go) sup (2o. 90:
[ + V
$ERJ
VN
whenever SSp < where Sp is defined in Theorem 1 The parameter, C is a constant and the parameter Obias is defined in Lemma 1 The sample complerity of the process is ()e-3).
Proof. Note that,
1 j Vv j=1
V2(20, 90)
Σ 1=1
vo (Nos 9o: no,)) $ ( g0) - V2 90)1 + V (Mo 90)
Voc (Mo: 90, To,)
Applying Theorem the first term be bounded by C'e for some constant C². The second term can be bounded by VEblas/ 7) + with sample complexity of ((e-5) (Lemma D Using C' max 1}, we conclude.
Theorem states that Algorithm generates policy such that its associated N N-agent value is at most ((maxfe,c)) error away from the optimal N-agent value. Additionally, it also guarantees that such a policy can be obtained with a sample complexity of ((c))) where e is an arbitrarily chosen positive number.
We would like to point out that in Theorem 3 [ + viui /VN. However, we assume that Assumption B holds in addition all the assumptions mentioned in Theorem 3 then using Theorem ? one can similarly show that the average difference between the optimal MARL value and the sequence of values generated by Algorithm is O(max (e,6)) where = VIT/vVN and such error can be achieved with sample complexity of O(c where > 0 is tunable paramcter.
8 Experiments
For numerical experiment, we shall consider a variant the model described in Subramanian and Mahajan (2019h. The model consists of N collaborative firms operated by a single company. All of them produces the same product but with different quality. At time i, the i-th firm may decide to improve the current quality of its product (denoted by xt) by investing AR amount of money. The action corresponding to investment is denoted as of = 1 whereas no investment is indicated as of = 0. Clearly, the action space is l {0, 1). On the other hand, the state space is assumed to be X = {0, 1, ... . - 1}. The state transition model of the i-th firm is as follows.
x
if o 0
2 =
x x x x 1 1-x:) | elsewhere
(27)
where X is uniform random variable in [0. 1), ni is the empirical distribution of x; & (xi)ie(),.. .N). and N. the mean of μºa. The intuition for (27) is that the product quality does not change when no investment is made and it improves probabilisticall otherwise. However, the improvement also depends on the average product quality, i. of the economy. Specifically, it is harder to improve the quality when 7 is high. The
13

---

Published in Transactions on Machine Learning Research (05/2023)
1.4
1.2
0.8
Error
0.6
20
40
80
100
Number Agents
The error as a function of N. The bold line and half-width of the shaded region respectively denote the mean and standard deviation of the error obtained over 25 experiments conducted with different random seeds. The chosen model parameters are as follows: = Å = 0.5, BR = 0.5, AR = 0.5, Q = 10.
Figure 1:
term (1 - / /Q) signifies the resistance to improvement. The reward experienced by the i-th firm at time is expressod as follows.
r(z,, uh H,"" az²) = ax BRR - ARu
(28)
The first term at of is the revenue carned by the i-th firm. One can interpret aj the price per unit quality at time l. Clearly, of plays the role of shared global state. In (Subramanian and Mahajan 2019). af was taken to be constant. Here we assume it to be linearly dependent on the average product quality at 1 i.c. af = Aa A1 (/Q)) where Ån a are arbitrary positive constants. The intuition is that the average quality L 1 influences the price at Specifically, as P4-1 rises, the firms can charge less price per quality, ag" The second term, ARĀ, denotes the cost incurred due to the average product quality, Ø. Finally, the third term, Anu, indicates the investment cost. Let π be the policy given by the Algorithm We define the error as,
error [V oo: T²) - (Ho, 0o, [T)]
where æo (=0))e( is the initial local states, 14 is its empirical distribution and og is the initial
global price. Moreover, Vy and Vso are defined via 66 and [11 respectively. Fig. [ plots the error as a function of N. We can observe that the error decreases with N.
9 Conclusions
In this paper, introduce MARL framework where the agents, in addition to their local states that transitions conditionally independently, also possess shared global state. As a result, the combined state transition processes of each agent becomes correlated with each other. Our contribution is to show that mcan-field based approximations are valid even in presence of such correlation. We obtain the expression for the approximation error as a function of different parameters of the model and surprisingly observe that it is not dependent on the size of the global state-space. Furthermore, we designed an algorithm that ap- proximately obtains an optimal solution the MARL problem. Although our work shows approximation
TTe code be accessed https:/ htwp:///ww..aaaooooaoaoaaaaaaaaa
14

---

Published in Transactions on Machine Learning Research (05/2023)
results in presence of correlated evolution, the presumed structure of correlation is not in the most generic form. Specifically, assumed that the states of each agent can be segregated into two part-one evolving conditionally independently and the other being identical to every agent. Whether mean-field control tech- niques work in presence more general form of correlated evolution is an important question that needs to be investigated the future.
A Proof of Theorem
The following helper lemmas needed to establish the main result.
A.1 Continuity Lemmas
In the following lemmas, IT is arbitrary policy and jA E A(X) are arbitrary local state distributions. Lemma 2. If MF (,) is defined by
(7), then the following relation holds Vy G.
| (μ, 9, σ) MM (ū,g, T) (1 LQ)lu Øō/1
Lemma 3. If pMpp ((...)) is defined by (8) then the following relation holds Vi G.
|pMp (M. g. pMP (p. 9. x)11 S Splp- 1il1
where Sp A 1=1422 2 + LQ(1 Lp).
Lemma 4. If PMF (1,5)) is defined by 99, then the following relation holds Vg E G.
| (,,,, Pa (7.9. I Salua Ta
where So - LG(2 LQ).
Lemma 5. If pMMp(,, is defined by 10 then the following relation holds Vig G.
MF (n, 9. T)) , MF (1,9. x1] S Sn 4 Øa/2
where Sn A MR 2L + LQ(M + Ln).
The lemmas stated above exhibit that the functions MF (.,.,-), PMF (s,.)), ") PMF (1).)) and MM (..:-) defined
in section 3 are Lipschitz continuous. Proofs of Lemma are relegated to Appendix B E
A.2 Continuity of Some Relevant Functions
Let (mi)eet,1,...) I be an arbitrary policy sequence and (9thet0,1,... G be given sequence of global states. Recall the definition of PMF given in (8). For every 14 E A(X), we define the following.
PMF (Pt.9atr: ))++)) A pMF ( PMF 1,90++-1,,T4+-11 ....o PMF (1,9), ( (14)
(29)
where denotes function composition and I e 1......... Note that, using r in 29 we get PMF (mi, Il.,, TT) pMP pMP(H m)). Similarly, using the definition of PMF given in we define the following Viy A(X).
PMF Ihttr Tla M
PMF (H4 9t, (9)()))) PMP (PMF (m) Ita ma) -1- (
(30)
... x PMr (MMP (14, (14-0ttrr111 Ttt 9t T4t) (9(+++))
Finally, using the definition of y MM given in 10
define the following Auy E A(X).
MF (pr, Ml, Th(T))
Σ MN (PMP (1 91d44-11 Tal4r-1) gitr, T4+ PMF (Hi -1dtr-11 ((:4+-1)(g++))
if 1
141:47
n MF (141, 91. T()
if rf==0 0
(31)
15

---

Published in Transactions on Machine Learning Research (05/2023)
where E4s144 indicates summation operation over (9141.-.. (1s41.""...99r)" g". We prove the continuity
property of these newly defined functions in the following lemmas. Proofs of Lemma g are relegated to
Appendix F H
Lemma 6. The following relations hold vl,r r E 10,1,-m }. Vp, Py E A(2), Agutr E gr+1 and Vaute E II++1
JPMP (Hi Mid+tr Teltr) PMF (m Ild+r; mad+r)l2 S 1m Mxl1
where Sp defined in Lemma
Lemma 6 @stablishes the Lipschitz continuity of PMF with respect to its first argunent.
Lemma The following relations hold vl,r E {0, 1,,1,, J. Vp, A(X), Aguetr gr+t and Vautr e I|r+1.
Σ PMF (Pt,
(utt)) PG (Pi Mittr, matr)) S So(1 + Sp + ... Sp)lm 1411
I-t 1+lttr
where Ex+r4tr indicates a summation operation over f9++1. ... g E g" for r 2 and an identity operalion for The terms Sp,SG are defined in Lemma and respectively.
Lemma 7 establishes the Lipschitz continuity of PMF with respect its first argument. Finally we establish the Lipschitz continuity of GMF with respect to its first argument in the following lemma.
Lemma 8. The following relations hold Vl, {0, (,,,, }, Vp4, fly E A(X), Ag: E g and Voster E IT".
[
(MnSc
| (Hi 9ts (1.+T)))) ,MF (T,, 9t. altt))
Sp - (S% - 1) + Sn ||: - P1l
where Sp, Sg and Sn are defined in Lemma 3 4 and 3 respectively.
Finally, we prove an important property of the function FMF that directly follows from its definition.
Lemma 9. The following relations hold vI E 10, Vr E (1,2,...), Ai E A(X), Agt E 9 and VTTae E II".
MMF (1) It. T.l+r) = Σ MP (pMP (Hi Mt. m)). M++1. A411-)) PMF (H1. (9)(1)1))
11G
where PMF and PMr are defined in and respectively.
Proof of Temma is relegated to Appendix
A.3 Approximation Lemmas
First would like to state an important result that will be useful in proving the following lemmas.
Lemma 10. Tm E (1..... ... M), {Xmn Fomnine( NY are independent random variables that lie in 10, 1}, and satisfy Eme(L,-..u) .M3 [[Xmm]] < 1, Vn E (1,-.. ". .N,, then the following holds,
Σ E
(Xmn E[Xma]) S SVMN
(32)
In the following, A (Te))c(0.1.))
arbitrary sequence of policies, {u," Va gi denote the empirical state distribution, action distribution and global state of N agent system at time and {2), ut} are the state and action of ith agent at time t induced by from initial states Ep
Lemma 11. The following inequality holds Vt E 1.........
E D
MF (NN gi mm) S
(33)
16

---

Published in Transactions on Machine Learning Research (05/2023)
Lemma 12. The following inequality holds Vt {0, (0,1....} J.
Cp VN [
E B - pMF (Hi NN mi)l S
(34)
where Cp _ Lp.
Lemma 13. The following inequality holds Vt E {0, ..
MR
LR
E
r(a,, un Mi Si utt) MP (ut Ht mT)
u
N
The proofs Lemma
10
13
are relegated to Appendix
M
A.4 Proof of the Theorem
Let, π ho. be an arbitrary policy sequence. We shall use the notations introduced in section A.3 Additionally, we shall consider {Mt, 3r as the local state distribution and the global state of the infinite agent system at time t. Consider the following.
( No: π
Voo (Mo: 90: m)
8 +
r (at, ut, fi Ii ,N²) MF (HE of, xe)
yd E[r MF (H," 9 xx)1
E[ (He, It. a
N
1=0
(a)
MR + LR
U
Je
1 1-7
t=
(35)
Inequality (a) follows from Lemma 13 Note that, using the definition 31 we can write the following.
J. = B (1i) :et mese)] E[ (wo: 9o. Jo, T0:)]]
B[ (1 Set Tx+1:))] - BI (n Sh Teae)
IM
FF MP 9 - E
Σ
MF (pMP (NL N TK). 9. TK+1:) P ( N TW)
9Eg
IA
E MM (H
( ght u I1
Σ OEG
RM (PMF (HL gh (k). Th+ PMP (NÉ gh Tx)
E
E
Σ
MF
g. Po oh vx (()) x Iht u
5EG
E
FM (PMF (HÉ dhd Tk). TK TK41H) PPM (HÉ o. (g)
9Eg
E. jMr (M 9. ) Dh D (g) MMP (pMP (N oh mx), g. #k+1;)) PMT ( , ;x)
A=09EG
Σ Jh. Jz.2
17

---

Published in Transactions on Machine Learning Research (05/2023)
where use the notation that u Mo and g0 9u- Inequality (a) follows from Lemma whereas (b) is result of the fact that Mi+1 and g are conditionally independent given ax 9h u Moreover, 9k+1 Pa(uk oh ). The first term Jkz can be bounded as follows.
-
Σ [| (KE+In Tk+11: JMP (pMP (uÉ gh ma) g, *K+1:01 x Pa(uk of v [o)]
DEG
(a)
[ Sp -1
10)
x E - pad (uE gh aw))l x |Polu gh v )
(0)
(( Sp -1
)
$ Cp
(Sp 1) SRSp St-
(5p
x
[ + V
Inequality (a) follows from Lemma can be bounded as follows.
whereas (b) results from Lemma 12
Using
9
the second term J.
Σ E P
oh Us Ko) Po(u Di M.MF (u Dh Tk))(O)) x | (PMF (HL "6 mk) g, mx+1a)]]
DEG
.R E
Pa(M N N v PolmE 9k N MP ( Ie N
9
Tx)))
(6)
1/
MR LG E DN - MP (HE ght mx)l S MaLay
10)
u
N
Inequality (a) is consequence of Assumption a) and the definition of pMF given in (31. Incquality (b)
follows from Assumption [ d). Finally, (c) is consequence of Lemma 11 Combining, we obtain,
[
MRSC Sp
Sp 5 Sp
MRSC
4 [v1x+ +v/ + MRLLV
J S Cp
+ SR
t
x
Sp
VN
N
Substituting in 35
obtain the following result.
MR + LRV U
1
U4
(N No: π²
Voc (Mo: 90, T)
+ MRLay
1-7
VN
N (1 71-
Cp Sp
) [ + +n {
yMRSa (1 7)²
V u
+
SS
- )
We conclude by noting that suup Vx Io. π) s Voo (My 9o. T) S sup, (Zo. 9o. πT) Voo (Hrp Po. T)) where the suprema taken the set of all admissible policy sequences 17
18

---

Published in Transactions on Machine Learning Research (05/2023)
B
Proof of Lemma 2
Note the inequalities stated below.
1 (,, M. (f,gg:4)1 (0)
Σ TT, (() E T(,
Σ
Σ x(., - E T(, (.
wEul TE
ZEX
Σ (x uo (u) - (,, jr g)
DEA uELl
(m(x) ((x) Σ (9) +
Σ p(x)
|, (,,,), л(x, F. (v))
sex
wEd
mEX
WEM
T + Σ (x)) TQlm 17l1
DEN
(1 + LQ)lH 1bl1
Inequality (a) follows from the definition of y MF of Assumption 2 and the fact that (x. f4, g) is a valid probability distribution. Finally, (c) uses the fact that p is a distribution. This concludes the lemma.
(M (---) as given in 7 On the other hand, (b) is a consequence
C Proof of Lemma 3
Observe that,
|PMF (p, - pMP T)
(0)
(4..9.)))((cmmmm000))e)) P... P(x, u, p.. MB
Ui M. MF
#EX wEll
J1 + J2
Equality (a) follows from the definition of PMF (,,))) as depicted in bound.
g
The term Jr satisfies the following
J1 2 Σ Σ
u, p4, Ul
MF (1,g,,))) P(x,, u, Tr,g, MF (ū, (Z.
NEN NEll
(a)
Lp [|+e fa/1 + MF g, - MF [T x Σ u(z) Σ
π(., ())
TEX
ueud
(
Lp(2+ + Lo)lu - Ø1
19

---

Published in Transactions on Machine Learning Research (05/2023)
Inequality (a) is consequence of Assumption n (z. 9): la are probability distributions. The second term, J2 obeys the following bound.
[[c] whereas (b) follows from Lemma 2 and the fact that
J2
Σ
Σ
P(z, u, n. g.v MI (ū, 9. x x/T (((U))))(())) ((., (1)((()(((
aEX Nell
Σ
((x) p(x)
H,
Σ
Σ
-
क (1,,
#EA
ZEX
wEUl
=1
1
11
+ Σ
ú(x)
LQlu Øb (8) (1 LQ) a 1b/2
tEX
Inequality (a) results from Assumption 2 and the fact that (2, p. g) is probability distribution whereas (b) utilizes the fact that is distribution. This concludes the result.
D Proof of Lemma 4
Note the following relations.
PM (1, PM (T,, 1. 1)11
| g, MF (M. T)) -
[R.g. (.F. (p,,g,)))
(b)
LG 1| 11l1 + an (M.. g, σ) MF (1. (1.g. I L2 + LQ) #il1
Equality (a) follows from the definition 9 while (b) follows from Assumption [d). Finally, (c) is a result of Lemma
E Proof of Lemma 5
Observe that,
|.F (u.g, ,M (fa, 9, 11
( ΣΣ
r(x, M, MF (1, r(x, u, To 2, MF (Te 9, (), (
REX NEl
J1 + J2
Equality (a) follows from the definition of MF (...)) as depicted in 10 The term J1 satisfies the following bound.
J 4 Σ Σ
r(x, u. p4 g. MF ()) - r u, p. g. MF (TI, x)) x (TE g)
xEX well
(a)
LR [|me- 1b)1 + MF (u. ( x)
Σ p(x) Σ 7(, p(c, LR(2 + LQ)lu Ç
20

---

Published in Transactions on Machine Learning Research (05/2023)
Inequality (a) is consequence of Assumption (bb) whereas (b) follows from Lemma 2 and the fact that n (z. M4, 9): la are probability distributions. The second term, J2 obeys the following bound.
J2 _ ΣV
Σ
|r,, u, p. v MP (i. x))l (z
ZER well
(a)
MR
Σ
[m(x)) (x(x)]
Σ (z, +MR Σ
A(x)) Σ
(.) (x,,
#EX
3Et
well
Mulu 1i1 + MR Σ ((x) Lolu- 1112 12)
MR(1 + LQ)lu 14/1
Inequality (a) results from Assumption [ aa where (b) follows from Assumption 2 and the fact that (( μ. g) is a probability distribution. Finally, (c) utilizes the fact that jı valid distribution. This concludes the result.
F Proof of Lemma 6
Fix e {0, ". We shall prove the lemma via induction on r. Note that, for O, we have,
(a) ma) pMF (m Ihs, ma)l = |PMF (Hi St. mi) pMF (m I1, m))l S Splm - 1
dMP (p Ihi, gha
Inequality (a) follows from Lemma Assume that the lemma holds for some r E 1..,. We shall demonstrate below that the relation holds for r + as well. Note that,
iMF (p: M1++++; (bt+r1) PMF (T Wetgtt++1 mti+r+1)l1
= 1IMMF (jMF (pt. Tbl-r) 91+++1 m44++1) - pMF (PMM ( W4ltt: Titte)) 9++++1, 71+++1)
Sp/pMF (m Muttey (init4 Tht4r) PMF (M (it (ur) Sp 14 Pcli
Inequality (a) follows from Lemma and (b) is a consequence of the induction hypothesis.
G Proof of Lemma 7
Fix LE (0,1,..)). We shall prove the lemma via induction on Note that, for == O, we have,
(a) PMF (Pg Ita, ma) Pal (T Ita, ma)h PM (pr.9t, mi) PM (ī Mt mi)l S Salm Fyll
(36)
Equality (a) follows from Lemma Assume that the lemma holds for some r E {0, 1..... }. We shall now show that the lemma holds for r well. Note that,
Σ
PMF (m) 9w-4r+1 (7444)) - PMF (i 9614r+1 Aw+r+1)h
Hllttt
Σ
PMF (p, (utt, THIT) ((4t) PMP (PMF (n gults m.st)) 91 m++++1)
PMF (āi, gha4r, ((l4r) PMP
MM (PMP (īi, gut-, mi44)) gree Meres)) < +
21

---

Published in Transactions on Machine Learning Research (05/2023)
Equality (a) follows from 30 The first term J1 can be upper bounded follows.
J1
Σ
PO (Mt Hiltr #ettr
1+1+t1+1
PM (PMF (p: :: Tw++r) get Fl+T+1) PMP (PMP (m 9ut+r Tiste): 9 +++++1)
x
(a)
SG
Σ
PMF (14, Medtr ma++)
PMP (14, Illtr, muatr)
PMP (1,,0ttt,, Mattr
411:t4+1
(6) Sp
14
Pcl
Σ
PMF Mutt
(c)
SoSp- F411
4114++11
Inequality (a) follows from Lemma while (b) results from Lemma
0 Finally, (c) can be shown following
the definition 30 The second term J2 can be bounded follows.
J2
E
PG (MF (pi Uld+r Thstr), g1+r+1, +++r+1))1
111++++1
I (m, (1:9 Mider PMF (Paggt (
(a)
Σ
PMF (pg M TuLT)) - PMF (pi Mhate matr)) S So(1 + Sp + .... - |1 - -M,
41t4++
Incquality (a) follows from induction hypothesis. This concludes the lemma.
H Proof of Lemma 8
Note that the result readily follows for r 0 from Lemma Therefore, we assume 2 1.
JPM
( (1i St, Ta4tr - MM (īt (1,,,99 Thtte)
(
MF (PMF (Pi 11 m PMP (Pi 1:
1+1:+r
(PMF (ā 10t-rr11-111t---10 M(t) PM P 91 S 11 +
PMF
Inequality (a) follows from the definition 31 The first term can be bounded as follows.
J1
J (PMF (pts 11:441111:444-111111111 914,, T(+))
+i1d+r
JPM (Mi 914tr-1
PMM (āū, (h 114
(0)
MR
P (pr.9
PMF 11
41itt111
(b)
MRSc
MnSo(1 (1 Sp ... SS- Sp-1))m4
Sp (8% (8%-1))144 -
22

---

Published in Transactions on Machine Learning Research (05/2023)
The bound (a) can be proven using Assumption [ and the definition of y MP given in (10 The bound (6)
follows from Lemma 7
The term J2 can be bounded as follows.
J2
E
PMF
G
H11++
x In MF (PMP (Mi: 9utrr1+ -1111 T(+r.
T(tr) - -r (PMP (Ft, 1, Mt+ri m(+r)
Σ
Pe (p b
SR| PMI (H I, PMF (i 1, (ll4rr-)))
1+1:tr
1 SnSplm P4l1
Σ 111+r
Pe (Tt, (pt. MMttr (M4 SnSplm- F7
Inequality (a) follows from Lemma 5 while (b) results from Lemma. 6 Finally, (c) can be proven from the
definition 30 This concludes the lemma.
Proof of Lemma 9
FMF
(1r: 91, Tlate)
Σ
MF (PMP) (pi (ttt-tttt---11ttt------ M4r PMF ( 11
1+:44
(0)
Σ
MF (FMP (PMP (pt, mT),
m(+))
H1N+r
PMP (PMF (pt.gi,
PM ( (1, (g++1)
Σ
FMF (PMF (p4 91 91+1; 714 PMI (Mr, 14 (()((11)))
Equality (a) follows from the definitions
29 and
30
J Proof of Lemma 10
Let Ymn Xmn E E mn ? {1, M), we get,
E[Xmn], Vm (1.... M}, Vn E (1....,N) N). E mmnl1 < E[Xma]. Using independence of {Ymn) (Ymn)ne(l,...)) for any given m e
Note that, as Xmm [0, 1], have,
N
N
N
N Σ
N
N
N EEV = Σ
Y Yma
E
Σ
Y
Ym.n Ym,ng
E
y2 m,n.
+
Σ B1 =1 ma
Σ
122
1
Using the above relation, we finally obtain the following.
(a)
M
E
Y
m.n
S
M
m.
VM
2
mm
mL
mim
N M Σ
M
[X
K VMN
M= m=
23

---

Published in Transactions on Machine Learning Research (05/2023)
K Proof of Lemma ii
Notice the following relations.
E
D v MP (u .h me)1
Σ Te (2, ui 96t Jun (x)
V
E
E
Vi (u)
Σ
Tel 14= d6 (w) (x)
xiz De
LEE
#EX
E
E
5(u) u)
E
me(E, pi N
ri 2f (u)
63x x)
Fi It
N
N
N
N
LUEUI
sex
N
N
E
E
5(u = u)
Te (e
p ge (u)
M
N
N
EEW
Equality (a) follows from the definition of y MF (:...)) .) given in 7 while (b) is consequence of the definitions of p&, vf Finally, (c) uses Lemma 10 Specifically, it utilises the facts that, {uikeeti.... ,N} are conditionally independent given x;²; gā and the following holds
E
N) = Te ne(ats m4 . (u), 6(u = u0)ar" N 2t
Σ E ((u) = u.) x² oi" =1
vi E (1, ,N, Vu u. This concludes the lemma.
L
Proof of Lemma 12
Notice the following docomposition.
E
PMF
(He)" .gt L.N ,,))1
(a)
E
P(x', u, 2h Si. MF (HN ,it (x)))((a' ur of (w) (z)
X'E NEM
E
8 x) =x)- --EE
Σ
1 P( u, N. Ih MF (nN 96 (x)) (') N Play u, p. .ee MF (n, .ht (z) u. sf
Σ ,( xa)
well
N
N
Σ
E
8(r241 =x) N
N
xEX
1=1
ueu
< J1 + J2 Js
Equality (a) uses the definition of PMf (1.5))) as shown in and equality (b) uses the definition of n. The term Jr obeys the following.
J 4
E
8(1 x)) Σ
P ut, pr of. vi (a))
N
REX
N
(a)
E
E
6(1 = =x)-
P(x ui ui ot M()
x
N
ui
N
x
N
VN
TEX
1=1
1
24

---

Published in Transactions on Machine Learning Research (05/2023)
Inequality (a) is obtained from Lemma 10 In particular, it uses the facts that ( are condi- tionally independent given {=n "6" ui 3, and the following relations hold
N
E 5( pof Fi u P( uho ui N (x),
Σ E |6 =x) xe .6. un²
xEX
Vie ",.,,,,,, and Vz E X.
The second term satisfies the following bound.
N
N
J2
E
P
u M oi oi (x)
Σ
P(x uh ui Ie MF (M, 96 (x))
N
MEN
E
Pl
Mi N Ii UN - P(at, uhe My N oe MP (u oft me)) u
N
- LpB Li MF (u st me))
(6) LP Vuu
Incquality (a) is consoquence of Assumption can be upper bounded as follows.
[(c) while (b) follows from Lemma 11 Finally, the term, J3
J3
E
Play u u Ie MF (nt If (x)
N
P(at, u, ph ge MB (M," ()))))))m ui (w)
1=
uEN
(0)
|
Incquality (a) is a result of Lemma 10 In particular, it uses the facts that, (ui are conditionally independent given a. ,o, and the lollowing relations hold
E P(a) uh ui ge Mr (ul N Ie m))( x; 9e N = Ep(as u, uh Mr (uL ge ()))()) ui g. (w),
NEl
". N g. =1 Σ E P(ay, uh, ph It MF (u,. ... (1) xEX
Vi (1,.., N), and Vo E X. This concludes the Lemma.
M Proof of Lemma 13
Observe the following decomposition.
E
rats wi M N U - MF (ui ge m
E
r uhs p N vNN)
Σ
Σ
r(z, u, u. N IN y MF (uN gi" me)))))) u. IN (uiju (z)
N
NEX well
(
(att ue, ph gt. uN
Σ
Σ
r(a, u, uh g. MF (n N ge m))) pf gi N (u)) Σ
6(0) = x)
FEX well
1=1
N
E
Σ r ui s .f. xNN)
Σ
rl u, u gº. Mr (uN of m))) uº gf (2)
< + J2
N
N
1= NEN
25

---

Published in Transactions on Machine Learning Research (05/2023)
Equation (a) uses the definition of MM (:,:s:) as shown in 100. Inequality (6) uses the definition of u The term, J1, obeys the following.
N
J1
-
E
r
9: vN
r r whe ph ge MF (Mi NN N. m.))
N
1=1
N
1
R.
r(
14 :i u
N N
r(a,
N Wes Mi Di MMP (nL Ii TT))
N
N
(4) LR
(b)
LR
MP (uf g. Te)l
u
Inequality (a) results from Assumption [b,, whereas (b) is a consequence of Lemma 11 The term, J2, obeys the following.
J2
E
7 (ats u f Ih, MM (uf" 96 9i, m))
r(z u, uº g¹ .MM (uf" of m)))m((ate ui" of (u)
N
1=1 wEM
N
E
E
( ui, pe gf MF (1L, 96t m)))
N
r(a Mh Di v MF (ML Ih mm)m "f (w) xi "
1= 1 wEW
M
Σ To ra uey ue oh MP (HL Di me))
(a)
MR VN
ro(st, u, 14 Dh Mr (ni gi a)) , (x)
x De'
1= weld
where ro()))))) f r(s ( D/M Inequality (a) follows from Lemma 10 Tn particular, uses the fact that (uffiet1.... .N} are conditionally independent given at gb. and the following relations hold.
Inola,, uf N Ih Mr (u,,,, ,0"" ;,",=)))l= $
E (ro(zh uh pi" gi MP (u 96" T.)) xi 9.
Σ well
ro(at, u, ui" oht MF (Hi, .²² (x))) Hr, ,9" gf)) (u)
vi (1, (I,...,,,,,VVEE
N Proof of Theorem 2
The following results are needed to prove the theorem.
N.1 Continuity Lemmas
In the following Jemmas, E 11 is an arbitrary policy and Ja E A(X) are arbitrary local state distributions. Lemma 14. If PMf (1,))) is defined by then the following relation holds Vg E g.
ppMF (u.g.T) pMF (ī,g, 7))1 S 1plu-1uu 7h)
where Qp 1+ Lp LL. Lemma 15. If MF (..::) is defined by (10 then the following relation holds Vig E G.
MF (1, π) - MF (,7,gT)) m) S Qnlu 1.l1
where Qn A Mn(1 + TQQ) T.n-
26

---

Published in Transactions on Machine Learning Research (05/2023)
The proofs of Lemma 15 are relegated to Appendix
0 P
In the following three lemmas, show
the continuity of the functions defined in Appendix A.2 Proofs of the following lemmas are relegated to
Appendix Q S
Lemma 16. The following relations hold Vl, E (0,1,-. ... J, Vp, M, E A(X), Vguir E Gr and Vitar e I1++1
dapl (14, GiltT, PMP (mt tr mattr)11 S QF 14 F4/11
where Qp is defined in Lemma 14
Lemma 17. The following relations hold Vl,r E (0.1,...h Pr E A(X), Vguuer E gr+l and VTLaer E I1++1
Σ b+1++
| (Mr T(str) PMF (F,, 9ht4 muttm & La(1+ -...... + +Q)) Ril1
where Emtratr indicates a sunmation operation over {g++1. g1+tl g' for r and an identity operalion forr=
r= 0. The term Qp is defined in Lemmal 14
Lemma 18. The following relations hold vl,r E {0, 10,1,.-..h J. VH 4 A(X), Vgl E g and VTuHr E II".
Qr (
|AME (pi, It, Tult)) MF (īt, Di Ma4r)) <
11 1 |1 - -ar1
where Qp and QR are defined in Lemma 14 and 15 respeclively.
N.2 Approximation Lemmas
We use the same notation introduced in Lemma 19. The following inequality holds Vt {0, 1,,....
2
E
p1+1 PMF (HL , .m))11
x
(37)
VN
Lemma 20.
The following inequality holds Vt {0, J..1......
MR
E
(o gi MF (ML 9b m²))
S
VN
The proofs Lemma 19
20
are relegated Appendix
N.3
Proof of the Theorem
Let. π (m.het.. be an arbitrary policy sequence. We shall use the notations introduced in section Additionally, we shall consider {pr }r} as the local state distribution and the global state of the infinite agent system at time t. Consider the following.
A.3
V (2 Io. π)
Voo (Ma- Fo: m
EE
r(zzs ui N gi:) )- MF (HI "6" Tz)
MF
+
B MF (NN g6 TT)] MF (M St. TT)]
N
t=0
t=0
3.
(a)
MR
J
1 1-ク
V
t=
(38)
27

---

Published in Transactions on Machine Learning Research (05/2023)
Inequality (a) follows from Lemma 20 Note that, using the definition 31 we can write the following.
Jr B B (pL. of. Te:)) B[TMP (1o: 90, To:e)]
[R[rMM (1 I6 T[+1=)] BlTMe (N 9ht mx=+)]
MMi
wn
Blr Mr (u : m++1:e)] - IE Σ
Mr (pMr (HE Hh (R), P P (uf ohth (g)
(phr
gEG
VA iMI
( MP (1 I6+1 T2+1s)
a gh u
MP (pMMF (ME Sh mk). th+ Tk+ PG Pd (m gh Tx)
999
E
E
Σ
MF
( I. Th+ 1 oh (e) zh gh uu
9E99
E
Σ
(NL Dh T (x Pd (m gh mL)(o) MM (PMF
DEG
MP (1 9. IT41)) . g (()) -ii (pbr (uy gh mx) g, the an) oh (o)
k=0 gEg
8.M (1 Tk+1:)) FMF (PMF (H gh Tx). 9, Tx+1:)) x Pa &h (9)
k=0
(
|MRaa 11)
Qpp -1
x E E PMF CHR mw)), Pa oh >
MnLi 10- - 1) + QnQQ
x
VN x
Qp -
0=
2 2
MRLC [
Qp (pp-1)
QP + QR -1) -0)-1)-MaLOC)) -MRLot
|
where we use the notation that - = Mo and g6 go. Incquality (a) follows from Lemma whercas (b) is
consequence of the fact that pa and gi conditionally independent given a I u Moreover,
gh Po(u N g ). Inequality (c) follows from Lemma 18 while (d) is a consequence of Lemma
Substituting in 35 we obtain the following result.
MR
1
VN So. T) V.0 (Hy: Fo. 7)
1-7)
VN
+
Qp [(--1) )
2
Qp- + QR
1
}
MMRLG
7 1
VIx
1-7Qpp
1Qp
1 1-7
Qp 11) (1 71-
VN
We conclude by noting that > Va Io. - sup, Voo (My 9o. T) S sup, (=o 90. π)) Voo (Ho. 9o. T)) where the suprema are taken over the set of all admissible policy sequences 17
28

---

Published in Transactions on Machine Learning Research (05/2023)
O
Proof of Lemma 14
Observe that,
|PMF| (4. 9. T) PMF (á, 9, m1)2 (a) ΣΣ
P(x, u, (0 P(x, u, (.
TEN wEl
$ J1 + J2
Equality (a) follows from the definition of PMF (1,:5)) as depicted in bound.
The term J1 satisfies the following
J1 _ Σ
P(z, u. H. P(r, u, (., p.0)
<T (1)
NEW
(0) 2 Lppl - 1111 x
Σ TEX
Σ
(b) (,
Lplp 1111
Inequality (a) is consequence of Assumption (c) whereas (b) follows from the fact that ((. (4, p4, 9), are probability distributions. The second term, J2 obeys the following bound.
J2 - ΣΣ
Σ
P(x, u, g1g
(I.. (1.
REN wel
=1 [m(x)= [(x) Σ π(. u, gu))
$ Σ
Σ ū(x))
Σ
|T u. (.) - (.
#EX
uell
ZEX
wEdl
(0)
pa|1 + Σ ((x) Lolu /al1 (b) (1+ LQ) 1111
1
ZEX
Inequality (a) results from Assumption 2 and the fact that (æ, 14,9) is probability distribution whereas (b) utilizes the fact that p is a distribution. This concludes the result.
P Proof of Lemma 15
Observe that,
MF (H. - MF (ū, g, m))2
(a)
Σ
r(a, (. u, (,)
xEX well
< J1 + J2
Equality (a) follows from the definition of y MF (.,,,)) depicted in 10 bound.
The term J1 satisfies the following
(a) r(x, u. g) r(x, u, (..g) 9) x (I, ())) & Lalu
J1 2 Σ Σ
1l Σ p(x) Σ ( μ. (u)
ZEX well
nEX
weld
L pl pa/1
29

---

Published in Transactions on Machine Learning Research (05/2023)
Inequality (a) is consequence of Assumption ( whereas (b) follows from the fact that T(., pc 9). are probability distributions. The second term, J2 obeys the following bound.
J2 _ Σ
Σ
rr, u. p.9) x (T, u. (.) ((, p. (.))())((()
ZEN NEM
(0)
MR Σ
[m(x)) (x)x) Σ (l, +MR Σ [(x)) Σ
(t(a, (.g)(u) n fr, (u))
TEX
=EX
nel
(6)
MRlp 711 + MR Σ (())
Tolu 7 (
MR(1 + TQ)lu 10/1
TEX
Inequality (a) results from Assumption Maa where (b) follows from Assumption 2 and the fact that ((x μ4: g) is a probability distribution. Finally, (c) utilizes the fact that f valid distribution. This concludes the result.
Proof of Lemma 16
Fix E (0,1, We shall prove the lemma via induction on r. Note that, for r= 0, we have,
(a)
papl (Pis Giat ma) PMF (īt Ia. ma)) |PM (J4rs I1: mi) PMF (Th Mi m))li Qrlp 77y1
Incquality (a) follows from Lemma 14
Assume that the lemma holds for some E f0, 1, ... We shall demonstrate below that the relation holds for r well. Note that,
GMF (M) g4r4++1: mh4+++1) PMF (pt M4ttrr1+1 -l1--++)]1
= iIPMF (MM (pL. ILLtT, m.l+r), 91+++1 74+++1 - PMF (BME (ār. (1t:9ttr:: Tll+r) 91t++1, +1+++))
(b) (2 QplppMy (p (14 PMF Mite mb147)11 S
Op 14 P1l1
Inequality (a) follows from Lemma 14 and (b) consequence of the induction hypothesis.
R Proof of Lemma 17
Fix E (0,1,...) ... We shall prove the lemma via induction on r. Note that, for O, we have,
[MF ma) PMP (Fi Ihit Tu)li
|PM (Ho 91, mi) PMF
(1,,
(39)
(a)
= =IPa(P PPl(P S Lalu, Fyl1
Equality (a) follows from Assumption [d). Assume that the lemma holds for some E (0, 1..). We shall now show that the lemma holds for + 1 as well. Note that,
Σ
PMF (m 9w-rr+1 ((444) - PMF (i, 9614r+1 #w+r+1)h
H1lttt
(a)
Σ
PMF (p (tt4, TLIT) ((4t) PMP (PMF (n gultrs mast)) 01 mi+r+1)
PMF (āi, gha4r, ((d4r) PMM
MM (PMF (ii,gut mi44)) gree Meres)) < +
30

---

Published in Transactions on Machine Learning Research (05/2023)
Equality (a) follows from 30 The first term J1 can be upper bounded follows.
J1 A Σ
P (m) Moltes (
+1++T+
x PMP (PMP (uager Thd+r) -0+ m++++1) PG (PMP (1 -(++1))
E
PMF (Pr Wid M1147)
=
411t+1+1
Pa(PMM (p: ghlt:r (t Pc (Pt, gud+rr Teltr),
9ltr+1) ((ttr))++++1)))
(a)
LG
Σ
(p Ihatrr Alttr) PMF (pr, Mudtrr mlatr) x PMP Mtstr: (our))
++11+++11
(6) LaQpt p4
Σ
PMF (Hr 9tter (14+r)944+11) LoQpt -4/
41dtr+1
Inequality (a) follows from Assumption 1 d) while (b) results from Lemma 16 Finally, (c) can be shown
following the definition 30
The second term J2 can be bounded as follows.
J2 A
Σ
PMF (PMP (Pi, Pistrs Tel 914 #4r+1))
1i1d+r+1
| (p4 Better Thet (94rr1)))))))) PM (Tu Muter matrr(
x
(a)
Σ
PP 9t mdtr)) PPMP PMP (Fr, Mattr matr)h S Lo(1 Qp+ ........................ + 14, P.l
1i14r41
Inequality (a) follows from induction hypothesis. This concludes the lemma.
S Proof of Lemma 18
Note that the result readily follows for r = 0 from Lemma 15
Therefore, we assume 2 1.
MF (ii St, )(LT)) - MF (Āi, Rt (((++))
MF (PMI (USSEELTT-L 1, tr mitr) PM (Ht, (Mt
+11:+r
- MF M (i 1a Pitr: T14)) PM
PMF (ū 11 $ J1 + J2
Inequality (a) follows from the definition 31 The first term can be bounded as follows.
J1 A Σ
MF (PMF (m), 91d---11 Mh:4r-1)) 944 T(r))
++1l+r
x
P.
PMF (1 - PM (āis 1ut
(0)
MR
Σ
IPMP (1, 91 PMF (F,, 11
++1:1r-11
MRbg (Q) -1) 1/11
MnLo(1 Qp ... + F4y12
QP
31

---

Published in Transactions on Machine Learning Research (05/2023)
The bound (a) can be proven using Assumption a and the definition of y MP given in (10) The bound (b)
follows from Lemma 17
The term J2 can be bounded as follows.
J2 A Σ
PMF (P,. ( Mul
Hi1+r
MF (pMr (Ht. (Mt.9tttr-1, (1 Ml+r: T(tr) - -DM (PME (f4, 9:1.,, T1.tr--) T+++)]
(a)
Σ
PMF (Pt gultr- 1utr--)) x QR| (pt, giltr-11 T(i-r-1) PMF 91:4r
1-1+t
QRQPIum P.l x
PM Σ 1411-r
QAQEIm 1yl1
Inequality (a) follows from Lemma 15 while (b) results from Lemma 16 Finally, (c) can be proven from the
definition (30 This concludes the lemma.
T Proof of Lemma 19
Notice the following decomposition.
E
pit1
PMF
(u,, 96 x4t)
(n)
1
E
Σ
P(x', u, ph If )m((d' of g Hu)
E'EX wEM
E
8 =x) Σ Σ
P(a,, u. P. oe Df (2)) NN .g (u)
1
Σ
ب( x²)
N
N
x x'Ex' wEl
N
N N
Σ xEX
Σ
5 =x)
Σ
Pla u oh (2) MN ae (u)
- J1 + J2
N
1=1
1=1 NEL
Equality (a) uses the definition PMF (c::)) as shown in ( and equality (b) uses the definition of u The term J1 obeys the following.
N
J A
8 = =2)
Σ
P( uiy M ,
N (xx)
N
TEX
1=1
1
N
(a) z
1
E
E
8(1441 x) Σ ul u. .ft (z)
x g²a una
x
N
SEX
Inequality (a) is obtained applying Lemma 10 and the facts that { are conditionally inde- u, pendent given {x," ,u,,,N,, and the following relations hold
E 5(1/2) x)) x;
=>/=="" g.. uu² = P(æt, ui, u gh (z),
Σ E M6r44 = 2:) an vi uu² =1 FEX
We We(1.... (1....,,)) and Vr E X. The second term satisfies the following bound.
N
(a) P(x u, p. .6 (x) AN oi (u)
JØ
7 E
P(
ui nN (x)
S
VN V x
N
BEX
1
==1 nell
32

---

Published in Transactions on Machine Learning Research (05/2023)
Inequality (a) is result of Lemma 10 In particular, it uses the facts that, (uilee(1....)) conditionally independent given at" st and the lollowing relations hold
E Mi ot (a) sf
Σ uEUl
P u, u (x)) u (u),
Σ E P(ab ui ui of (x) oe gf
=1
Vi E (,,,,,,, and Vz E X. This concludes the Lemma.
U Proof of Lemma 20
Observe the following decomposition.
E
ra u M1 ge MP (me 1 mT)
N
(a)
(a uey pi ge.
r(x, u, ph D )ol( ui gt (u)
NE uEEl
E
r un pi .2")
Σ>
r(x, u, ph De (ol uN ot (2) 1 N r u. ub .9 (m(() u. ot (w)
Σ 8( =
NEll
N
N
E
raa) u Mi ,9
N
N
t= WEN
E
E
ra uh ph , )
r(z), u, pi I. mm NN 9e (u)
2i N
N
wEll
(c)
MR
E
E
ro(at, ui, p." )
Σ 1=1 wew
ro(a u pi gt mel H. ot (u)
x
N
9t
S
N
VN
Equation (a) uses the definition of MF (.,)) as shown in (10) while inequality (b) uses the definition of N The function ro is given as, ro(::3'5)) A 3/MM Finally, relation (c) follows from Lemna 10 In particular, it uses the fact that (ui relations hold.
conditionally independent given x; gf and the following
Iro(si uisn ui" g6 S I,
E (ro(ato uh, the oe0 x 96
Σ weld
rolat of )m M. . (u)
We (1,..,,, NN,
33

---

Published in Transactions on Machine Learning Research (05/2023)
V Sampling Procedure
Algorithm 2 Sampling Algorithm
1: Input: Po: 90, Th: P, PG.
2: Sample up ~ T4, (To, Mo.90)
3: Mo + MMP (Mos 90: na,) where MM is defined in
++0
FLAG < FALSE
6: while FLAG is FALSE do
7: FLAG < TRUE with probability -
8: Execute Update
9: end while
10: t
11: Accept (IT, 9r, ur) as sample.
12: Va, <- 0, Q4y + 0
13: FLAG t FALSE
14: SumRewards: <-
15: while FLAG is FALSE do
16: FLAG < TRUE with probability 7.
17: Execute Update
18: SunRewards SunRewards + r(se, ut, 14 9t, vi)
19: end while
20: With probability 1, Vo, + +Sumneewrds. Otherwise Qu, + Sunnewards..
21: Ås (IT, (TT, MT,9r, wT) 2(Q,, Vo,))
22: Output: (IT, prr9r, ur) and Ao (FT, pr, wr)
Procedure Update:
23: T1+1 P(xs, Ut, p4 It; v2).
24: 9++1 Polar, We, Me: Ut).
25: P++1 - pMF (H, where PMF is defined in 8
26: u+11 ~ Tq. (I+41 14441:444::9441
27: Vi+1 t y MF (H (1441:9411,00) TT,) )
28: |+1+1
EndProcedure
34

---

Published in Transactions on Machine Learning Research (05/2023)
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 Al-Abbasi, Arnob Ghosh, and Vaneet Aggarwal. Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(12):4714-4727, 2019.
Andrea Angiuli, Jean-Pierre Fouque, and Mathieu Laurière. Unified reinforcement q-learning for mean field game and control problems. Malhemalics of Comtrol, Signals, and Systems, pages 1 1-55, 2022.
Peter Caines and Minyi Huang. Graphon mean field games and the gmfg equations: g-nash equilibria. In 2019 IEEE 58th conference decision and control (CDC), pages 286 286-292. TEFF, 2019.
René Carmona, Mathieu Laurière, and Zongjun Tan. Model-free mean-fiele reinforcement learning: mean- field mdp and mean-field q-lcarning. arXiv preprint arXiv:1910. wwt.it.911.......... 12802, 2019.
Kai Cui and Heinz Koeppl. Learning graphon mean field games and approximate nash equilibria. arXiv preprinl trXiv:2112.0120 2021.
Romuald Elie, Julien Perolat, Mathicu Laurière, Matthieu Geist, and Olivier Pictquin. On the convergence of model free learning in mean field games. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 34, pages 7143 7150, 2020.
Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis. SIAM Journal on Mathematics of Data Science, 3(4):1168- 1196, 2021.
Karl Hinderer. Lipschitz continuity of value functions markovian decision processes. Mathematicaa Methods of Operations Research, 62:3 22, 2005.
Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman. Multi-agent reinforcement learning in stochastic networked systems. Advances in Newral Information Processing Systems, 34:7825-7837, 2021.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduuced) policy gradient and natural policy gradient methods. Advances Neural Information. Processing Systems, 33: 7621-7636, 2020.
Volodymyr Mnih, Koray Kavukeuoglu, 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 533, 2015.
Volodymyr Mnih, Adria Puigdomenoch Badia, Mchdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- national conference machine learning, pages 1928-1937. PMLR, 2016.
Washim Uddin Mondal, Mridul Agarwal, Vaneet Aggarwal, and Satish V Ukkusuri. On the approximation of cooperative heterogencous multi-agent reinforcement learning (marl) using mean field control (mfc). Journal of Machine Learning Research, 23(129):1 (:99):1-000 46, 2022a.
Washim Uddin Mondal, Vancet Aggarwal, and Satish Ukkusuri. Can mean field control (mfc) approxi- mate cooperative multi agent reinforcement learning (marl) with non-uniform interaction? Tn The 38th Conference on Uncertainty in Artificial Intelligence, 2022b.
Washim Uddin Mondal, Vancet Aggarwal, and Satish Ukkusuri. On the near-optimality of local policies large cooperative multi-agent reinforcement learning. Transactions on Machine Learning Research, 2022c.
URL http://wwwwaaaeeeeee..oooonddaaa
35

---

Published in Transactions on Machine Learning Research (05/2023)
Médéric Motte and Huyen Pham. Mean-field markov decision processes with common noise and open-loop controls. The Annals of Applied Probabilll,, (2(2))1421-1455, 2022.
Barna Pasztor, Lija Bogunovic, and Andreas Krause. Efficient model- multi-agent mean-field reinforce- ment. learning. arvi preprint vrXiv22077044055 2021.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic 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
PMLR, 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement lcarning. Advances in neural information processing systems, 33:10199 10210, 2020.
Gavin A Rummery and Mahesan Niranjan. On-line Q-learning using conmectionisl systems, volume 37.
Citeseer, 1994.
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. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 251-20 259, 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jader- berg, Mare Lanctot, Nicolas Sonnerat, Joel 7. Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning, arXiv preprint arXiv:1706.055: 052966, 2017.
Ming Tan. Multi-agent reinforcement learning: Independent cooperative agents. Tn Proceedings of the tenth international conference machine learning, pages 330-337, 1993.
Xiaoqiang Wang, Liangjun Ke, Zhimin Qiao, and Xinghua Chai. Large-scale traffic signal control using a 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): -92, 1992.
Nicholas Watkins, Cameron Nowzari, Victor M Preciado, and George Pappas. Optimal resource alloca- tion for competitive spreading processes bilayer networks. IEEE Transactions 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 coordinate traffic signals arterial network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1290-1298. 2019.
Jiachen Yang, Xiaojing Ye, Rakshit Trivedi, Huan Xu, and Hongyuan Zha. Learning deep mean field games for modeling large population behavior. Xixiv preprint ar Xix::1711.03166, 2017.
36


Reviews:
[{"review_id": "1fGkCwU4Wg", "reviewer": "Reviewer_BwjS", "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: \n    - The paper is generally well written. \n    - The proposed MFC setting with common state seems relevant for applications. \n\n- Weaknesses: \n    - Some notations and concepts need to be clarified. \n    - It seems that the MFC setting with common state can fit in the more general setting of MFC with common noise, which has been studied in a few works already, so the link between the two settings (and the existing results) need to be clarified. \n    - There seem to be several gaps that are not even discussed between the initial setting and the algorithm so it is not clear to what extent the convergence result of Theorem 3 really addresses the initial problem. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 mean field control (MFC) problems in discrete time in which there is a common state. The MFC framework has been developed to approximate control problems with a large number of indistinguishable agents. Here, on top of the individual state for each agent, there is a common state which influences all the agents and, hence, the population distribution. There are two main contributions. \n\n- First, the authors study the connection between this MFC problem and the N-agent problem. They show (Theorem 1) that the optimal values are close and obtain an upper bound of order $\\frac{\\sqrt{|\\mathcal{X}|} + \\sqrt{|\\mathcal{U}|}}{\\sqrt{N}}$, where $\\mathcal{X}$ and $\\mathcal{U}$ are respectively the state space and the action space, and $N$ is the number of agents. \n\n- Second, they propose a natural policy gradient algorithm for this MFC problem, analyze its convergence (Theorem 3), and illustrate it on an example.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical points:\n\n**Question 1:** Is your setting a special case of MFC with common noise and, if yes, are your results special cases of existing ones?\n\nTo be specific, let us write the evolution in terms of transition functions instead of transition kernels. Imagine that $P(x,u, \\boldsymbol{\\mu},g,\\boldsymbol{\\nu})$ is the law of $F_x(x,u, \\boldsymbol{\\mu},g,\\boldsymbol{\\nu},\\epsilon)$ for some transition function $F_x$ and some random variable $\\epsilon$, and $P_G(\\boldsymbol{\\mu},g,\\boldsymbol{\\nu})$ is the law of $F_G(\\boldsymbol{\\mu},g,\\boldsymbol{\\nu},\\epsilon^0)$ for some transition function $F_G$ and some random variable $\\epsilon^0$, in such a way that \n\n$$x_{t+1} = F_x(x_t, u_t, \\boldsymbol{\\mu}_t,g_t,\\boldsymbol{\\nu}_t, \\epsilon_t),$$ \n\nand \n\n$$g_{t+1} = F_G(\\boldsymbol{\\mu}_t,g_t,\\boldsymbol{\\nu}_t,\\epsilon^0_t).$$ \n\nNow, define \n$\nX_t = (x_t, g_t), \n$\nwhose transition is given by:\n\n$$\nX_{t+1} = F(X_t, u_t, \\mathbb{P}^0_{(X_t,u_t)}, \\epsilon_t, \\epsilon^0_t)\n$$\n\nwhere $\\mathbb{P}^0_{(X_t,u_t)}$ denotes the conditional joint state-action distribution given the common noise $\\epsilon^0$, and the transition function $F$ is given by:\n\n$$\nF((x,g), u, \\boldsymbol{\\theta},\\epsilon,\\epsilon^0) = \\Big( F_x(x,u, \\boldsymbol{\\theta}_x,g,\\boldsymbol{\\theta}_u, \\epsilon), F_G(\\boldsymbol{\\theta}_x,g,\\boldsymbol{\\theta}_u, \\epsilon^0)\\Big),\n$$\n\nwith $P$ and $P_G$ defined as in your work, and $\\boldsymbol{\\theta}_x$ and $\\boldsymbol{\\theta}_u$ denote the marginals of the joint distribution on $x$ and $u$ respectively. \n\nWith this new state $X=(x,g)$, it seems that the MFC problem fits in the framework of e.g.:\n- Motte, M. and Pham, H., 2022. Mean-field Markov decision processes with common noise and open-loop controls. The Annals of Applied Probability, 32(2), pp.1421-1458.\n- Carmona, R., Laurière, M. and Tan, Z., 2019. Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-learning. arXiv preprint arXiv:1910.12802.\n\n**Question 2**: How does the output of Algorithm 1 _really_ relates to the original problem? In particular: \n\n- In the original problem, the optimization is over all policies and not stationary ones. On Page 10, you claim that it is sufficient to consider stationary policies by invoking Puterman's book, but could you clarify which result exactly you use? It does not seem to me that the MFC setting easily fits in the one covered by Puterman's results. \n\n- How does the result of Theorem 3 reflects the fact that you only allow a specific class of parameterized policies instead of all possible policies? On page 10 again, you claim that you \"characterize the elements of $\\Pi$ by a $d$-dimensional vector $\\Phi$\". However, since policies take the state distribution as an input, it does not seem that we can characterize all such policies using a finite dimensional vector. So we can expect a gap between the original problem (with optimization over $\\Pi$), and the problem with optimization over a class of parameterized policies. \n\n- The Algorithm 1 relies on samples, so the policies $\\Phi_j$ are stochastic. Does the bound in Theorem 3 hold for any realization of the samples? Or should it be understood in expectation or in an other probabilistic sense? (Please also check below for further questions that could help improve the statements of Lemma 1 and Theorem 3.)\n\n\nOther questions (less critical or just to improve the paper):\n\n- Page 2: “comprising of N number of agents”\n\n- Page 3: Are the state and action spaces assumed to be finite?\n\n- Page 3: Equation (6): Please clarify how the policy is used. In particular, are all the agents using the same policy, and if yes, why?\n\n- Page 3: “admittable”: “admissible”? How is defined the set $\\Pi$ of “allowable policies”?\n\n- Page 4: “for the agents to (probabilistically) choose actions based on its current local state”: “their current”?\n\n- Page 5: For Assumption 1, when you say that “Such assumptions are common in the mean-field literature”, could you please specify in which part of the books (Carmona et al., 2018) is the same assumption used? The books are quite long and they deal mostly with the continuous setting, which is not the same as yours. \n\n- Page 6: Theorem 1: Here, it is written “max” over policies $\\pi$, which implicitly means that there is a policy achieving the maximum value. Could you please clarify why such a policy exists, for $V_N$ and $V_\\infty$? \n\n- Page 6: “the function r and P”: “the functions r and P”\n\n- Page 7: “this can be compactly written as follows”: It is not clear that (15) is more compact that (14).\n\n- Page 7: after (15): “we denote this conditional joint probability as”: This notation is a bit strange because it is supposed to represent the conditional probability of a sequence of $g$ but it is actually evaluated at $g_t$. So it looks more like the probability of $g_t$ given the past. Please clarify. \n\n- Page 7: after (16), “we can now re-write ...”: Here and at a few other places, it is not very clear which symbol you are defining because the equality symbol with a triangle can go both ways. Please clarify each instance and define the symbols appropriately.\n\n- Page 7: after (17): What do you mean “the summation operation over $g_{1:t}$”? Do you sum over all possible trajectories?\n\n- Page 8, step 2: In the equality in line 1 of this step: Please clarify the definition of the right-hand side with $\\tilde{r}^{MF}$ and $\\pi_{t:t}$. In the equality in line 2: Why is there an expectation around $\\tilde{r}^{MF}$? Just above (17), the same expression did not have any expectation, so it is not clear to me whether $\\tilde{r}^{MF}$ is deterministic or stochastic. This seems to be related to the symbol defined in (31) but this is in the Appendix. \n\n- Page 8: I am not sure how inequality (19) is obtained. Could you please explain further?\n\n- Page 8: “with a (k, t)-dependent Lipschitz parameter”: Do you need this parameter to satisfy some boundedness or growth condition? Otherwise, it is not clear what happens when you sum over time steps up to infinity in order to obtain the full value function. As far as I understand, the bound in Lemma 8 for instance involves $S_P^{t-k}$, and I do not see how you can sum over $t$ up to infinity in Step 6 of the proof (page 9) without having the constant in the big $\\mathcal{O}$ going to infinity. I imagine that the condition $\\gamma S_P$ can be helpful but this is not very clear from your proof. (Actually I think this clearer when reading Appendix A.4, but this point should also be clarified in the main text.)\n\n- Page 9: “reward of this representative”: missing word?\n\n- Page 10: “Without loss of generality, we assume that the optimal policy sequence is stationary (Puterman, 2014).” Could you please provide the exact result that you use in Puterman? Notice that here the state space has a continuous component due to the distribution, and the set of policies that you use is not of the classical form  (functions of the state taking values in the action space). \n\n- Page 10: “We characterize the elements of $\\Pi$ ...”: Could you please clarify what you mean? The set of policies $\\Pi$ is a set of functions which take an element of $\\Delta{\\mathcal{X}}$ as one of its inputs. So it seems that the set $\\Pi$ is infinite-dimensional and it is not clear how you can have a bijection to a set of finite-dimensional vectors. I can imagine that the set of functions parameterized by $\\Phi$ can approximate the set of all policies $\\Pi$ up to some precision (bounded away from $0$ as long as $d$ is finite). Could you please provide more details on this point?\n\n- Page 10, line below (21): “the deterministic quantities”: It seems that $\\mu_t$ should be stochastic due to the effect of $g_t$. Please clarify.\n\n- Page 10, two lines below (21): I am not sure why the subscript $\\Phi$ in this line looks bold while the one in (21) and the one in the line below (22) do not. Please double-check all the instances of $\\Phi$, $\\Phi_j$, etc.\n\n- Page 10, three lines below (22): “over the set of feasible policies”: I don't think this is correct since here the optimization is only over the set of parameterized policies. \n\n- Page 10: Could you please provide some intuition for equations (24) and (25)? It seems that (25) gives a kind of occupancy measure but with a discount and I am not sure why this is a relevant quantity for the problem. Did it appear (implicitly) in the original formulation of the MFC problem?\n\n- Page 10: Below (26) you explain that the sampling procedure is provided in Algorithm 2. Could you please clarify (perhaps in the appendix) how Algorithm 2 indeed generates sample according to this distribution? Does it generate samples exactly according to this distribution or is there an approximation? \n\n- Page 10 and 11: The assumptions 4 to 7 are quite abstract. Could you please provide at least one example that fits in your assumptions? It seems that Assumptions 5 and 6 only impose constraints on the class of parameterized policies, while Assumptions 4 and 7 also involve the MFC model (in particular the transitions).\n\n- Page 11, Lemma 1: I have mainly four questions. (1) In the statement, you first fix the sequence of outputs of the algorithm and then say “for some $\\eta, \\alpha, J, L$” but these parameters are used in the algorithm, so the output of the algorithm depends on these parameters. I would suggest to first fix the parameter and then take the sequence output by the algorithm. (2) Furthermore, it is not clear whether the initial values $\\Phi_0, \\mu_0,g_0$ need to be fixed before the algorithm's parameters or if there are parameters that will work for any initial values. Please rewrite this statement with a clear order of the quantifiers. (3) Also, what does the “constant” in the big $\\mathcal{O}$ depend on? (4) Last, if I understand correctly, the sequence of $\\Phi_j$ is stochastic in the sense that it depends on the samples that used for the NPG updates. So does the inequality hold only “with high probability”? Or does it hold for any sequence of $\\Phi_j$, independently of the samples used in the algorithm? \n\n- Page 12, Theorem 3: I have the same questions as for Lemma 1. Furthermore, is there a gap between $V_N^*$ as defined here and $\\max_{\\pi} V_N$ as it appears in Theorem 2? I would imagine that this is the case because the set of parameterized policies is a (strict) subset of the set of all policies. Furthermore, I imagine that the gap between the two can be quite large if the set of parameterized policies has to satisfy Assumptions 4 to 7. If this is true, then it is a bit misleading to claim that Algorithm 1 solves the original problem. Could you please comment on this point?\n\n- Page 16: Lemmas 2 to 5: The quantifiers over the policies and the distributions are missing. \n\n- Page 17, below (31), “indicates a summation operation over”: The summation should be over integers so I am not sure what you mean here. ", "broader_impact_concerns": "I don't think there are any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L8mwo8YqFj", "reviewer": "Reviewer_UELm", "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:\n* Global (non-decomposable) states are commonly seen in reality but existing mean-field approximation theory has ignored this, especially when both global and local states are present. This paper tries to address this issue for the first time, which is good. \n* A computational algorithm is provided to solve the MFC with both local and global states.\n\nWeaknesses (see the requested changes below for more details):\n* The technical challenge mentioned at the bottom of page 2 for the additional global state is not that convincing. \n* The assumptions are too restrictive, especially the contractivity related ones in all these theorems. \n* The NPG algorithm and analysis seem to have nothing really new, and is merely a direct application/restatement of existing results.  \n* On a higher level, I'm not sure about how important it is to study the MFC approximation problem given many evidences from the recent literature that we don't need to take the mean-field limit in order to utilize the symmetry in (cooperative) MARL problems. See e.g., [1,2]. \n\n\n[1] Gu, H., Guo, X., Wei, X., & Xu, R. (2021). Mean-field multi-agent reinforcement learning: A decentralized network approach. arXiv preprint arXiv:2108.02731.\n\n[2] Chen, M., Li, Y., Wang, E., Yang, Z., Wang, Z., & Zhao, T. (2021). Pessimism meets invariance: Provably efficient offline mean-field multi-agent RL. Advances in Neural Information Processing Systems, 34, 17913-17926.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "In this paper, the authors establish mean-field control (MFC) approximation theory to allow for both local and (non-decomposable) global states, whereas the existing MFC approximation theory only allows for local/agent states. The approximation bound is independent of the global state space sizes. An improved bound when the rewards and transitions are independent of the mean-field action distributions is obtained, which does not depend on the local action space sizes. A natural policy gradient (NPG) algorithm is also proposed and the convergence guarantee is established. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Here we detail some of the weaknesses above and provide some suggestions for potential changes and improvements.\n* The challenge mentioned at the bottom of page 2 seems artificial, since if I understand correctly, the global and local states $g_t^N$ and $x_t^i$ are conditionally independent, and hence it's more natural to consider $(\\delta(x_t^i=x))_{i=1}^N$ and $\\delta(g_t^N=g)$ (OpenReview markdown does not recognize curly brackets for some reason, so I use parentheses here) separately, in which case these $N+1$ indicators are conditionally independent, and there is no mean-field approximation for the last state. I understand that there might still be other challenges, but the motivation here is weird and not convincing. The authors should provide a more convincing explanation on the challenge of the non-decomposable global state.\n* The assumption that the policy is Lipschitz in the mean-field term is stringent, in that it's unclear when the globally optimal policy for the MFC is Lipschitz continuous. This is even more severe as we are also comparing against the $N$-player Lipschitz continuous policies in the main theorems, and it's more unclear when the globally optimal policy for the original $N$-player game is a restriction of a Lipschitz policy on the empirical state distribution (or how close they are). This is essentially critical as here we consider finite state and action spaces, in which case Lipschitz continuity for the $N$-player policies does not even make sense in general (without extension/restriction).\n\n ", "broader_impact_concerns": "None. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z0VFgg7Mvc", "reviewer": "Reviewer_dGHi", "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:\n* Game problems with both global and local states are ubiquitous and are important topics that are not (sufficiently) addressed in the existing mean-field control approximation theory. And to my knowledge, this is the first paper attempting at establishing the mean-field control approximation theory for Markov games with both local and (non-decomposable) global states.\n* The analysis that considers policy history in a Markov game in Section 6 seems to be novel and interesting. \n\nWeaknesses:\n* The result requires lots of stringent assumptions such as Lipschitz policy class (which may not cover or not even close to the optimal N-player policy) and some sort of contractivity like $\\gamma S_P<1$ in Theorem 1. Although these are typically assumed in the MFC approximation literature (which is not good for the future of this direction in general), they still largely restrict the applicability and meaningfulness of the results. \n* On a related point, this paper is a variant of a series of papers [A-D] in MFC approximation beyond the classical MFC setting, but all these papers including this one follow the same routine, despite some technical differences and novelties due to the variations like the global states in this paper. No efforts are made to address the significant limitations of the assumptions in the literature as mentioned above, and the NPG convergence analysis seem to be mostly the same except for some slight differences. \n\n\n[A] Mondal, W. U., Agarwal, M., Aggarwal, V., & Ukkusuri, S. V. (2022). On the approximation of cooperative heterogeneous multi-agent reinforcement learning (marl) using mean field control (mfc). Journal of Machine Learning Research, 23(129), 1-46.\n\n[B] Mondal, W. U., Aggarwal, V., & Ukkusuri, S. V. (2022, August). Can mean field control (mfc) approximate cooperative multi agent reinforcement learning (marl) with non-uniform interaction?. In Uncertainty in Artificial Intelligence (pp. 1371-1380). PMLR.\n\n[C] Mondal, W. U., Aggarwal, V., & Ukkusuri, S. V. (2022). On the near-optimality of local policies in large cooperative multi-agent reinforcement learning. arXiv preprint arXiv:2209.03491.\n\n[D] Uddin Mondal, W., Aggarwal, V., & Ukkusuri, S. V. (2022). Mean-Field Approximation of Cooperative Constrained Multi-Agent Reinforcement Learning (CMARL). arXiv e-prints, arXiv-2209.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 multi-agent reinforcement learning (MARL, or more precisely, Markov N-player games) with both agent states and global states, and extends the mean-field control (MFC) approximation theory (which originally only works without global states) to this setting. When the dynamics and rewards are independent of the action mean-field, an approximation error bound independent of the action space is also obtained. The authors then propose a natural policy gradient (NPG) algorithm for solving MFC with global states and provides an error bound against the original N-player game problem. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some suggested changes (that won't affect the essential weaknesses mentioned above):\n* If I understand correctly, the authors assume the conditional independence among the global states and local states. If so, this should be made clearer.\n* The results of the paper are not stated in a very useful manner. In practice, people apply the MFC policy to the original N-player problem, and hence the results should all be stated in terms of such kind of plug-in errors. For example, in Theorem 1, it should state something like if we solve the MFC with local and global states to an $\\epsilon$-error and get a policy $\\pi$, then what is the upper bound on $\\max_{\\pi'} V_N(x_0,g_0,\\pi') - V_N(x_0,g_0,\\pi)$. Similarly for Theorems 2 and 3.\n* The contractivity assumptions that $\\gamma S_P<1$ and $\\gamma Q_P<1$, etc. make the results only applicable to those problems with small Lipschitz constants or small discount factors, which can be easily violated in practice. This is even more stringent considering the limitation of Lipschitz continuity of the policies mentioned above. And just curious, do we need these contractivity assumptions for finite-horizon problems as well?\n* The NPG algorithm is applied to MFC models, but since the original problem is the $N$-player games, it's impractical to get samples from the mean-field transitions. So this is not really reinforcement learning (RL) but some \"artificial\" RL with a mean-field control sampling oracle. See e.g., [E] for more explanations on the difference between using an $N$-player simulator vs. a mean-field simulator. \n* Is Lemma 1 a direct application of Theorem 4.9 in Liu et al., (2020)? If so, the authors should make this clearer.\n* The dependency on $J$, the number of iterations should be made explicit in Theorem 3.\n\n[E] Yardim, B., Cayci, S., Geist, M., & He, N. (2022). Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games. arXiv preprint arXiv:2212.14449.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends the scope of mean-field control (MFC) to a natural setting of multi-agent RL where each agent has a non-decomposable global state in addition to the local states. As is standard in MFC, local states are assumed to be conditionally independent of each other, but in this case the global state is observed by all the agents, which can condition their policy. The main contribution is then that MFC can still be used as a good approximation framework accompanied by a natural policy gradient algorithm with bounds on the approximation error (wrt. the optimal policy). 

The reviewers had some mixed thoughts about this paper, and the overall points are summarized:

1. There are some limitations that are inherited by MFC required by the proof (e.g. Lipshitz continuity), so the proof has similar restrictions in applicability to the MFC domain. (Both UELm and dGHi)

2. Clarifications remain (both UELm and BwjS). In particular, some connections to previous work (identified by BwjS).

3. Remaining concerns can be addresses as future work (UELm).

4. Concerns about novelty (all reviewers) and scope (BwjS).


Despite outstanding concerns:

- I believe the limitations are a minor problem, since they are inherited by MFC, and the approximation from MFC is what allows the scalability in the first place.
- Novelty (and in particular, technical novelty mentioned by dGHi) is not a requirement for acceptance to TMLR
- Two of three reviewers lean toward accept, one sentiment was particularly well-expressed: "it does touch a useful topic with practical relevance" (dGHi). This point, in addition to the topic being one addressing scaling of MARL, means it will be of interest to at least a few individuals in TMLR's audience. 

The authors' verbose replies were appreciated by the reviewers. Still, there are clarifications that remain. In particular, in the latest communication with BjwS, they admit that the similarities (and differences) to past work [1], [2] in Questions 1 & 3, but I do not see any text on this added to the paper. The authors should add (perhaps in an appendix) a discussion of how their work relates to [1], [2] and cite these relevant previous works. (The authors state that they address this on Page 12, but I still don't see any references nor discussion to past work nor how their framework is related to [1], [2])

[1] Motte, M. and Pham, H., 2022. Mean-field Markov decision processes with common noise and open-loop controls. The Annals of Applied Probability, 32(2), pp.1421-1458.

[2] Carmona, R., Laurière, M. and Tan, Z., 2019. Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-learning. arXiv preprint arXiv:1910.12802.

Decision: Accept (poster)