Networked Communication for Decentralised Agents in Mean-Field Games

Thank you very much for reviewing our paper. We are pleased that you find it 'a very nice contribution' with the theoretical result 'particularly interesting'. Given this praise, we are surprised that you have initially rejected our paper.

Weakness 1/2/4/12/14: The ICLR page limit for the main text is 10 pages, so as you can appreciate, it is not possible to keep all the details in the main text even if we would like to (without moving something else to the appendix instead). $**None of the other reviewers**$ share your concerns regarding readability being affected by the placement of details in the appendix or on different pages of the main paper, and in fact reviewer HFSn says '$**the paper is well-written and easy to follow. The authors provide all the necessary theories and experimental settings in the main text,**$ with more detailed proofs and specifics included in the appendix' and 'the theoretical analysis in the paper is comprehensive'. Meanwhile reviewer y6Sh says 'The paper is $**very well written and very clear**$ … The theoretical results from analyzing the number of independent learned policies are $**elegant, interesting and significant**$ … The discussion of related work and placement of contribution is very extensive and good'. We always refer to the relevant section of the appendix / lines of the algorithms / definitions where items are fully defined, accompanied with hyperlinks to aid navigation. It is very common to leave full details of experimental settings to the appendix.

Weakness 3: As clearly stated, this is a temporal difference update, a very common method in reinforcement learning. Here it is augmented with the regulariser $h$ that we have already defined ourselves in Lines 134-135.

Weakness 5: We will update this in the manuscript.

Weakness 6: Having moved Alg.1 as per your suggestion, the prose description is now on the same page as the terms to which it refers. We give a line-by-line reference from the prose description to the relevant line of the algorithm. Our definitions are numbered and our section titles describe which element of the algorithm we are discussing. As mentioned above, other reviewers praise our paper's writing, clarity and comprehensiveness.

Weakness 7: Our prose description of the algorithm in Sec. 3.2 has line-by-line references to the part of the algorithm being described. Having moved Alg. 1 as you suggested, these descriptions are now on the same page as the algorithm as well as being hyperlinked. We think that comments in the algorithm itself will make things harder to understand due to cluttering, as well as pushing us over the page limit. You say that the algorithm has '$*so many*$ symbols that were not clearly defined in the main text'. What are the symbols that have not been introduced in the text? $\sigma^i_{k}$ is indeed a scalar which we have introduced in Lines 268-271; we then also devote all of Sec 3.4.1 to discussing it. These lines specifically discuss the arbitrary choice of this scalar for the theoretical results, so we find this criticism unfounded. As mentioned above, other reviewers praise our paper's writing, clarity and comprehensiveness.

Weakness 8: As indicated in Thm. 2, $\varepsilon$ has the same meaning as in Thm. 1, but we will clarify this in the manuscript.

Weakness 9: The diameter of a network is commonly defined as being the maximum length of the shortest path between any pair of nodes in the graph. We will clarify this in the manuscript.

Weakness 10: In what way does Sec. 3.4.2 not precisely describe the buffer? We provide a colour-coded version of the algorithm highlighting the modifications for the buffer, and give a line-by-line prose description of how it works with hyperlinks to the relevant lines. We do not believe this criticism to be well-founded, and other reviewers praise our paper's writing and clarity.

Continued in next comment...

Thank you very much for reviewing our paper. We are pleased that you find it 'novel','very well written' and 'very clear', with theoretical results that are 'elegant, interesting and significant', and 'very extensive and good' placement of contribution and discussion of related work.

Weakness 1: The grid-world games we choose are similar to those used in related works on MFGs, as we note in Lines 470-472 (for those that include experiments at all, which many theoretical works do not!). In fact, our tasks, where agents must coordinate on one of numerous possible equilibria, are more complex to solve than those in other works, which often focus on 'exploration' games, where agents must simply spread throughout the environment. The definitions of the tasks are given in Appx. E.1, though please do let us know if we can clarify these further. You are right that the transition function does not depend on the mean-field distribution in our examples here; we will add this to Appx. G as an element to explore in future work.

Weakness 2: When we ran our original networked algorithm (as well as the centralised and independent alternatives) without the replay buffer, we did not find any discernable learning or improvement in return/exploitability at all, despite leaving the algorithms running for several days and many thousands of $k$ iterations. We are currently rerunning the original versions of the algorithms without the buffers to provide empirical evidence of this lack of learning in practical time. We will update the manuscript with these ablation results when they are ready, hopefully by the end of this discussion period, or otherwise in time for the final version (since they are inherently slow to run).

Weakness 3: Please note that our robustness results do not consider failures in the communication network, but rather failures of the learners to update their policies in a given iteration (see Lines 482-484, 1561-1600, and also 028, 055, 116). As elaborated in Lines 1561-1600 and the captions to Figs. 2 and 5, when independent learners fail to update, the improvement of the whole population is slowed. In contrast, networked communication provides redundancy in case of these failures, with the updated policies of any agents that have managed to learn spreading through the population to those that have not. This feature thus ensures that improvement can continue for potentially the whole population even if a high number of agents do not manage to learn at a given iteration. We can see this benefit in Figs. 2 and 5, where networked learners outperform the independent learners, and generally also the centralised learners (where if the central learner fails to update, none of the population can improve, unlike in our networked case).

Question 1: See Weakness 3 for discussion of the benefit of our networked architecture over the others in terms of robustness to failures to learn an updated policy in a given iteration. Regarding robustness to population increase, in Fig. 3, the networked case with the largest broadcast radius (pink, 1.0) $*does not experience any shock at all*$. The centralised case also appears to experience a far greater initial shock than the networked cases, getting as bad as the independent curve, albeit quickly recovering. Similarly in Fig. 6, the centralised case has a shock doubly as large as most networked cases (apart from that with the smallest broadcast radius (green, 0.2)), while the largest broadcast radius (pink, 1.0) again has no shock at all. Recall also that in our experiments the networked agents use only $*a single communication round*$ per $k$ iteration to demonstrate the benefit of even minimal communication; having more $C$ rounds would further reduce the shock observed by the networked cases by ensuring that learnt policies reached all the newly joined agents before the next iteration. Meanwhile the centralised and independent cases would still observe their large shocks, (if independent learners have managed to improve at all in the first place). Moreover, a centralised learner may in any case be an unrealistic assumption in real-world scenarios.

Question 2: As we note in Lines 079-083: "We focus on 'coordination games', i.e. where agents can increase their individual rewards by following the same strategy as others and therefore have an incentive to communicate policies, even if the MFG setting itself is technically non-cooperative."

Continued in next comment...

... Continued from above.

Question 3: Our work inherently also considers robustness to poor local estimation of the Q-function (i.e. model errors), where we find that with fewer samples / TD updates, the margin by which our networked architecture outperforms the alternatives increases. This is due to our method for spreading policies that are estimated to receive a higher return in reality despite being generated from poorly estimated Q-functions - we note this in Lines 019, 417-420, 1870 and 2173. One could of course consider other types of robustness, and we do discuss scenarios such as you suggest in Lines 2144-2153 of our future work section. We hope that the fact that our work opens ideas for further potentially fruitful research avenues is not a reason for a low score.

Question 4: Nejad et al. (2009) [1] investigates the convergence rate of max-consensus algorithms such as that occurring under these conditions. In their Corollary 4.2, they prove that to achieve max-consensus, "the required number of communication instants is the maximum of the shortest path length between any pair of nodes", which is the definition of the diameter of the network. We denote this diameter as $d_\mathcal{G}$; they use $l$. They then give $\frac{1}{l}$ ($\frac{1}{d_\mathcal{G}}$ in our notation) as "the convergence rate of the max-consensus algorithm". In other words, if we start with $N$ policies in the population and finish with 1, the reduction in the number of policies with each round is equal on average, i.e. the reduction is linear. If the number of policies in the population decreases at a rate of $\frac{1}{d_\mathcal{G}}$, we can also say that the policy divergence

(defined as $\Delta_{k} := \sum_{i=1}^N \|\|\pi^i_k -\pi^{\mathrm{max}}_k\|\|_1$, for the consensus policy $\pi^{\mathrm{max}}_k$)

decreases at a rate of approximately $\frac{1}{d_{\mathcal{G}}}$. We can clarify this in the manuscript if deemed helpful.

Question 5: Apologies for this: the small size was necessary to fit the page count, but we will reproduce these plots larger in the appendices to aid visibility. As noted in Appx. E.2, the shaded regions are 2-sigma error bars, i.e. a 95.4% confidence interval.

Thank you again for your time and input; we hope that our answers to your questions will encourage you to raise your score.

[1] B. M. Nejad, S. A. Attia and J. Raisch, "Max-consensus in a max-plus algebraic setting: The case of fixed communication topologies," 2009 XXII International Symposium on Information, Communication and Automation Technologies, Sarajevo, Bosnia and Herzegovina, 2009, pp. 1-7, doi: 10.1109/ICAT.2009.5348437.

Thank you very much for reviewing our paper. We are really pleased that you find it 'well-written and easy to follow' and 'very interesting', with theoretical analysis that is 'comprehensive' and intuitive, and experimental results that are 'consistent' with this.

Weakness 1: Within our specific setting of learning with the finite empirical population through a single continuous evolution of the system, the only existing algorithms are those of Yardim et al. (2023) for the centralised and decentralised cases. However, as we discuss in our paper, while these algorithms are amenable to theoretical analysis (sample guarantees), they do not learn in computationally practical time. Specifically, when we tried to run these algorithms with their theoretically required hyperparameters, $*we did not find any discernable learning or improvement in return/exploitability at all*$, let alone convergence, despite leaving the algorithms running for several days and many thousands of $k$ iterations. Yardim et al. (2023) also do not provide any empirical demonstrations of their algorithms. Therefore, as we mention in Lines 467-470 and elsewhere, we also update the centralised and independent theoretical algorithms with replay buffers (as well as doing so for our own networked algorithm), so that we can compare with at least existing 'architectures' if not the algorithms themselves (which would simply show no noticeable learning at all). Nevertheless, we are currently rerunning the original versions of the algorithms without the buffers to provide empirical evidence of this lack of learning in practical time. This will serve both as a comparison with existing algorithms, and should also address your Question 1. We will update the manuscript with these results when they are ready, hopefully by the end of this discussion period, or otherwise in time for the final version (since they are inherently slow to run).

Weakness 2: Please note that our algorithms are not themselves MARL algorithms; we are using MFG algorithms to approximate the solution of finite-player games with large populations, since MARL struggles to scale computationally in such scenarios. As you suggest, agents in MARL algorithms might, for example, communicate the 'learnable vector' representing their local estimate of the global shared Q-function, so as to average their local estimates. Since in our MFG setting we are ultimately interested in finding high-performing equilibrium policies, we directly privilege the spread of Q-functions that lead to higher-performing policies (where each agent's policy is computed directly from its learnt Q-table as per Def. 8), rather than simply averaging them regardless of quality. In order to estimate the quality of an estimated Q-function, we compute the policy maximising it and observe the return of the policy in the environment (Lines 17-23 of Algorithm 2). Having already computed the policy from the Q-function for evaluation purposes, it is more computationally efficient to communicate the policy rather than the learnable vector from which it is derived, only to have to derive the policy from it again in the next iteration. You are right that our approach has parallels with evolutionary algorithms, and we ourselves discuss this similarity at length in Lines 2106-2122 of Appx. F.

Given that we explain our approach explicitly and you praise our paper as being 'well-written and easy to follow', we are surprised that you find this 'may cause confusion for readers'. This criticism seems speculative, especially as no other reviewers have raised this as a concern. We therefore hope this is not a cause for a lower rating, but we are nevertheless happy to clarify this in the paper if deemed useful.

Question 1: (See also Weakness 1 above.) When we ran our original networked algorithm (as well as the centralised and independent alternatives) without the replay buffers, we did not find any discernable learning or improvement in return/exploitability at all, despite leaving the algorithms running for several days and many thousands of $k$ iterations. Therefore by enabling discernable learning and indeed convergence, the replay buffer is a very significant improvement. We are currently rerunning the original versions of the algorithms without the buffers to provide empirical evidence of this lack of learning in practical time. We will update the manuscript with these results when they are ready.

Question 2: In our grid-world environment, the current location of an agent in the environment is its local state. For these tabular algorithms, we convert the location coordinates into a scalar value (such that the top-left gridpoint is 0, and the bottom-right is $\left(\mathrm{dimension} \times (\mathrm{dimension} - 1)\right)$. These values are then indices for the rows of the Q-table, with a row for each state.

Thank you again for your time and input. We hope that our clarifications will encourage you to raise your score.

Thank you for taking the time to review our paper, and we are very pleased that you find our approach ‘interesting'.

Main concerns: We are surprised and confused by this criticism, since we do indeed prove theoretically that the sample complexity of the networked case is better than the independent case when there is communication, as you state yourself in your summary. This is not criticism expressed by any of the other reviewers, many of whom in fact specifically highlight this theoretical result: they say that we 'demonstrate that this is … true in terms of sample efficiency and convergence speed, which is $**very interesting**$' (HFSn); 'the main contribution is theoretical, implying that communication should result in better sample complexity … The theoretical results from analyzing the number of independent learned policies are $**elegant, interesting and significant**$, as they imply the usefulness of communication in the field of learning in MFGs' (y6Sh); 'the main theoretical result is $**particularly interesting**$ … proving that this is so is $**a very nice contribution**$' (yxK2).

Why is the assumption that $\tau_k \rightarrow 0$ too restrictive? $\tau_k$ is a hyperparameter for which the value can be chosen by the person running the algorithm. We assume to begin with in Thm. 3 that $\tau_k \rightarrow 0$ to ease the mathematical analysis, before specifically discussing the loosening of this assumption in Remark 5 (other assumptions are loosened in Remark 4).

What do you mean for the gap to be 'small' - small with respect to what? Even if this were true, it would directly contradict your statement that we 'do not show the superiority over independent learning', since there nevertheless is a gap even if 'small'. In fact, please recall that the term $\mathcal{O}\left(\left(\frac{1}{d_\mathcal{G}}\right)^C\right)$ does not represent a specific or fixed numerical difference, but rather describes the asymptotic scaling behaviour of the difference with respect to $d_\mathcal{G}$ and $C$. So this term indicates the dependence of the size of the gap on size of the network and the amount of communication, rather than indicating its exact size, so the gap may not be small at all.

Minor weakness 1: In Lines 268-272, we do indeed already have a brief explanation of $\sigma^{i}_{k+1}$ when we first introduce it, as you suggest. Please let us know if there is something specific that can be clarified here.

Minor weakness 2: We wrote it this way for simplicity, but you are technically correct. We can instead write the term $\left(\frac{1}{d_\mathcal{G}}\right)^C$ in the bound in Line 373 as the piecewise function $f(C, d_\mathcal{G})$, defined as the following:

$f(C, d_\mathcal{G}) = \begin{cases} \left(\frac{1}{d_\mathcal{G}}\right)^C &\text{if } C < d_\mathcal{G},\\\\ 0 &\text{if } C \geq d_\mathcal{G} \end{cases}$ .

Question 1: This is not the case - the gap does indeed grow larger as $C$ grows larger. Larger $C$ means $\left(\frac{1}{d_\mathcal{G}}\right)^C$ gets smaller, which in turn means that $\left(1 - \left(\frac{1}{d_\mathcal{G}}\right)^C\right)$ gets larger, and hence also the gap. I.e. when $C=0$, $\left(\frac{1}{d_\mathcal{G}}\right)^C = 1$, and hence $\left(1 - f(C, d_\mathcal{G})\right) = 0$, while when $C \geq d_\mathcal{G}$, $f(C, d_\mathcal{G})=0$ and hence $\left(1 - f(C, d_\mathcal{G})\right) = 1$, with the term increasing monotonically between 0 and 1 as $C$ increases from 0 to $d_\mathcal{G}$.

Question 2: Recall that the piecewise function $f(C, d_\mathcal{G})$ is such that when $d_\mathcal{G}$ is 1, $f(C, d_\mathcal{G}) = 0$ for any case other than $C=0$. Thus if there is any communication when $d_\mathcal{G} = 1$, the difference term between the centralised and networked cases reduces to 0, indicating no difference, as is expected. Likewise, the difference term between the independent and networked cases reduces to $\mathcal{O}(1-0) = \mathcal{O}(1)$, i.e. the difference is non-decaying.

Question 3: When we ran our original networked algorithm (as well as the centralised and independent alternatives) without the replay buffer, we did not find any discernable learning or improvement in return/exploitability at all, despite leaving the algorithms running for several days and many thousands of $k$ iterations. We are currently rerunning the original versions of the algorithms without the buffers to provide empirical evidence of this lack of learning in practical time. We will update the manuscript with these ablation results when they are ready, hopefully by the end of this discussion period, or otherwise in time for the final version (since they are inherently slow to run).

We hope that our clarifications show that our work is ready for acceptance, and that this will encourage you to significantly raise your score.

Thank you for reading our response.

Question 1: Nejad et al. (2009) [1] gives $\frac{1}{d_\mathcal{G}}$ ($\frac{1}{l}$ in their notation) as "the convergence rate of the max-consensus algorithm" affecting the $*number of policies*$ in the population. I.e., if we start with $N$ policies in the population and finish with 1, it will take $d_\mathcal{G}$ rounds, with the reduction in the number of policies with each round being $*approximately*$ $N/d_\mathcal{G}$. The exact amount will depend on the exact structure of the network and the exact initial distribution of policies, so we can only give an approximate decrease. If the number of policies in the population decreases by approximately a factor of $\frac{1}{d_\mathcal{G}}$ with each round, we can also say that the policy divergence

(defined as $\Delta_{k} := \sum_{i=1}^N \|\|\pi^i_k -\pi^{\mathrm{max}}_k\|\|_1$, for the consensus policy $\pi^{\mathrm{max}}_k$)

decreases by $*approximately*$ a factor of $\frac{1}{d_\mathcal{G}}$ with each round. We can clarify this in the manuscript if deemed helpful.

Question 2: Thank you for pointing this out. Thm. 3 should instead have

$ub_{cent} + \Theta\left(1-\left(f(C, d_\mathcal{G})\right)\right) \\;\\; \approx \\;\\; ub_{net} \\;\\; \approx \\;\\; ub_{ind} - \Theta\left(f(C, d_\mathcal{G})\right),$

where $f(C, d_\mathcal{G})$ is the piecewise function defined as the following:

$f(C, d_\mathcal{G}) = \begin{cases} \left(\frac{C}{d_\mathcal{G}}\right) &\text{if } C \leq d_\mathcal{G},\\\\ 1 &\text{if } C > d_\mathcal{G} \end{cases}$.

The $\Theta$ still contains the term $\xi\sum_{k=1}^{K-1}L_{\Gamma_{\eta}}^{K-k-1}\mathbb{E}\left[\Delta_{k,0}\right]$, which multiplies the term in the brackets.

We will update the proof appropriately, beginning from Lines 1424-1428, which should instead read:

$\mathbb{E}\left[\Delta_{k,c+1}\right] \approx \mathbb{E}\left[\Delta_{k,c}\right] \times \left(1 - \frac{1}{d_\mathcal{G}}\right) \text{, giving}$

Thank you again for engaging with our rebuttal; we hope that these changes will convince you that our paper is ready to accept.

[1] B. M. Nejad, S. A. Attia and J. Raisch, "Max-consensus in a max-plus algebraic setting: The case of fixed communication topologies," 2009 XXII International Symposium on Information, Communication and Automation Technologies, Sarajevo, Bosnia and Herzegovina, 2009, pp. 1-7, doi: 10.1109/ICAT.2009.5348437.

As per the previous comment, the number of policies in the population decreases from $N$ to 1 over the $d_\mathcal{G}$ communication rounds, so the policy divergence decreases by approximately a factor of $\frac{1}{d_\mathcal{G}}$ with each round, on average. Therefore we can say that

$\mathbb{E}\left[\Delta_{k,c+1}\right] \approx \mathbb{E}\left[\Delta_{k,c}\right] - \left(\mathbb{E}\left[\Delta_{k,c}\right] \times \frac{1}{d_\mathcal{G}}\right) \text{, simplifying to}$

$\mathbb{E}\left[\Delta_{k,c+1}\right] \approx \mathbb{E}\left[\Delta_{k,c}\right] \times \left(1 - \frac{1}{d_\mathcal{G}}\right). \\;\\; \text{(1)}$

As above, this is approximate, with the exact decrease depending on the structure of the network and distribution of the policies. The induction from (1) would give

$\mathbb{E}\left[\Delta_{k,C}\right] \approx \mathbb{E}\left[\Delta_{k,0}\right] \times \left(\left(1 - \frac{1}{d_\mathcal{G}}\right)^C\right),$

which does not exactly give rise to (2) below, which is the (more important) approximately linear relation regarding the decrease in the number of policies averaged over the total number of communication rounds. Hence we can remove (1) if this is confusing.

This more important (and cumulatively accurate) relation for our purposes is the second one given in the comment above, namely:

This holds for $C\leq d_\mathcal{G}$; when $C = d_\mathcal{G}$ we have $\mathbb{E}\left[\Delta_{k,C}\right] = 0$ as expected. The divergence cannot be negative so there is no further change for $C> d_\mathcal{G}$.

We hope that this answers your question.

Thank you very much for reviewing our paper and for noting its 'extensive' experimental results.

Weakness 1: We are surprised that you both praise our 'extensive' experimental results while taking issue with us 'only' experimenting on two games. Experiments on two games is very typical for works on MFGs (for those that include experiments at all, which many - especially theoretical works - do not!), and indeed the games we choose are very similar to those used in similar works, as we note in Lines 470-472. It is also not clear to us whether your statement that 'the insights are more on the practical side' is a point of praise or a point of criticism that we should be responding to - can you please clarify this?

Weakness 2: You assert that our theoretical contribution is unclear and that where the theoretical contribution lies is not well motivated. This is in stark contrast with the other reviewers, who praise it as: 'novel','very well written' and 'very clear', with theoretical results that are 'elegant, interesting and significant', and also with 'very extensive and good' placement of contribution and discussion of related work ($**y6Sh**$); 'a very nice contribution' with the theoretical result 'particularly interesting' ($**yxK2**$); and 'well-written and easy to follow', with theoretical analysis that is 'comprehensive' and intuitive ($**HFSn**$). We state precisely the nature of our theoretical contribution in Lines 100-104 and summarise it again in Lines 300-305. We find your criticism regarding the theoretical contribution unfairly vague - can you please state more precisely what about the contribution you find unclear and what you would like to be better motivated?

Questions:

Again, your criticism that 'the statements are not clear' is very general and goes against the impression of the other reviewers - can you please let us know which specific statements you find unclear so that we can try to clarify them?

The statement in your question that an MFG has an 'N-player limit' is wrong or misleading. The MFG framework assumes an $*infinite*$ number of players, as we state in both Lines 036-037 and Lines 162-164. Our work does not directly study MARL and we do not present MARL algorithms. Instead, as we describe at the beginning of our introduction, we use the scalability issue facing MARL as a $*motivation*$ for our work on MFGs, as do many other works on MFGs. Since they assume an infinite population, MFGs do not face a scalability issue, and at the same time the solution of the MFG can be used as an approximate solution to the finite-player game in which we may have originally been interested but which is difficult to solve in itself. We already state this in the paper in Lines 042-047 and 182-190. Our algorithms are fundamentally MFG algorithms (they assume an infinite population of symmetric anonymous agents) and relate to other works on MFGs such as Yardim et al. (2023); this is not a concern raised by any other reviewers. To summarise, we learn the solution to the MFG by approximating the assumed infinite population using the finite empirical population of $N$-agents - in turn, we can use the solution to the MFG as an approximate solution to the finite $N$-player game.

We hope that these explanations are helpful, and will encourage you to raise your score significantly.