Learning Mean Field Control on Sparse Graphs

We thank the reviewer for the careful reading and constructive evaluation of our work.

The reviewer raised the concern that “[…] in Definition 2.1, it is unclear what the expectation on the right-hand side is defined over. […] the source of randomness needs to be explicitly stated.” Thank you for pointing out the missing clarity in Definition 2.1! The randomness in Definition 2.1 is induced by the randomness in the graph limiting object $G$ which is a random variable over the set of isomorphism classes $\mathcal{G}^*$ and not just an element of $\mathcal{G}^*$ as currently stated in Definition 2.1. The expectation is then over the law of this random variable $G$. We will update Definition 2.1 accordingly to accurately outline the source of randomness.

Furthermore, the reviewer raises the following question: “The reviewer is primarily uncertain about the applicability of the mean-field method in the studied scenarios. Specifically, mean-field theory relies on an assumption that holds when agents are strongly influenced by their neighbors. However, this assumption does not hold in sparse graphs. This raises a fundamental question: What is the rationale for applying mean-field theory in this context? Can it accurately capture the underlying relationships expressed by these graphs?”

For the many low degree agents, as the reviewer indicates, the standard MF assumption does not hold. However, even for these low degree agents, the same local neighborhood configurations appear very often in large graphs, formalized by local weak convergence. The locally weak converging neighborhoods result in an (almost) deterministic evolution of the finite degree mean fields and entail the rigorous theoretical results we derive in the paper.

The rationale of applying MF theory in the context of sparse graphs with finite expected average degree and diverging degree variance lies in the structure of the considered graphs. As we discuss in Example 2, these graphs contain a relatively small fraction of high degree nodes which are crucial for the overall system dynamics as they have many neighbors. Thus, we leverage the MF principle to model the important fraction of high degree agents who are close to the standard MF assumptions. Overall, the LWMFC model and our algorithms bridge the gap between rather dense topologies typically considered in MF setups, and ultrasparse graphs where the maximal degree is bounded. As our evaluations indicate, this gap contains many empirical networks which are modeled more accurately by LWMFC than by existing methods.

Finally, the reviewer comments that “[…] error bars are essential for accurately evaluating the performance of the proposed method.” We do not report error bars in Table 2 because our learning approaches consistently outperform the IPPO benchmark on all problem-network combinations.

We thank the reviewer for the positive evaluation and the constructive feedback.

The reviewer noted that: “While the theoretical analysis of the control problem is interesting, I am not sure if this conference is the best fit. It would be better to develop further the learning aspects.” We agree with the reviewer to the extent that our work is an initial investigation on the topic and that the algorithm performance can likely be improved further. However, the conducted theoretical analysis and our subsequent two systems approximation provide essential insights for the learning algorithm design. As our empirical results indicate, the conceptual insights in the first sections translate into mathematically well-motivated learning algorithms that outperform existing approaches like LPGMFGs, GXMFGs and IPPO. Thus, our framework closes a crucial gap in the existing learning and mean field literature.

The reviewer also raised the question “Is it possible to analyze the theoretical convergence of the proposed algorithms?” In Algorithm 1, we apply RL methods to the limiting LWMFC such that theoretical results from the corresponding RL literature transfer to our case. For Algorithm 2, a theoretical analysis is challenging due to the direct interaction with the empirical networks. We instead focus on the theoretical motivation for our learning approach and the extensive empirical evaluation in comparison to existing methods. For future work, a next step could be to mathematically analyze the error of the two systems approximation in terms of the number of agents.

We thank the reviewer for carefully reading our work and the detailed positive comments.

The answer with respect to the reviewer’s questions on $k^*$ is as follows. In all computational examples we set $k^* = 10$ for the standard LWMFC approximation, and $k^* = 4$ for the extensive LWMFC* approximation due to the considerably higher computational complexity of LWMFC*. In general, the choice of $k^*$ is a trade-off. On the one hand, choosing a higher $k^*$ means that agents with moderately low degrees are depicted more accurately which should enhance the accuracy of the two systems approximation. On the other hand, a higher $k^*$ also entails higher computational costs and an increasing algorithmic runtime as one must sum over more potential neighborhood distributions. While tuning the choice of $k^*$ will likely further improve the performance of our algorithms, we leave it to future work as our initial choice of $k^*$ already outperforms existing methods such as LPGMFGs and GXMFGs in all considered problem-network combinations.