Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning

We thank reviewer PDRU for their feedback. Please find our response below:

While the paper discusses extension to heterogeneity, the algorithm assumes mostly homogeneous agent types.

Indeed, while the current algorithm can only work for the homogeneous setting, we add two caveats:

1. As the reviewer points out, we mention an extension to a partially heterogeneous-agent setting by modeling types as a part of the state/action spaces of the local agents, in the “capturing heterogeneity” paragraph in page 4 and Remark 4.7.
2. There has been a line of recent work on extending mean-field MARL using a graphon-based framework that supports a continuum of distinct transition probabilities (which is also a form of heterogeneity). It may be possible to extend our subsampling framework to graphon mean-field MARL. Adapting this to our sampling framework may be highly non-trivial, and we leave this as an open problem for future works. Nonetheless, we can add a detailed discussion on this as part of Remark 4.7.

Can the authors provide more comprehensive experiments on common MARL benchmarks (e.g., MAgent, PettingZoo, SMAC) to evaluate practical performance?

As our work is a theoretical framework to the NeurIPS theory track submission, we only provided sufficient experiments to numerically validate the theory. That being said, an even more thorough empirical study of cooperative multi-agent RL algorithms is an interesting avenue for future research for empirical research, however, this is outside of the scope of our current work. Moreover, the above benchmarks (MAgent, PettingZoo, SMAC) do not fit our MARL setting (for instance, SMAC requires heterogeneous agents, MAgent requires competitive agents, and PettingZoo does not support our global-agent/local-agent setup).

How does the method scale/degrade with increasing agent heterogeneity? Can you support this with empirical results?

Increasing the agent heterogeneity using our “type-formulation” makes the algorithm somewhat more expensive since it factors into the query complexity via the state space of the local agents. However, since the optimality gap of the learned policy is on the order of $\tilde{O}(1/\sqrt{k})$ (modulo very small $\sqrt{\log(|\mathcal{S}_l| |\mathcal{A}_l|)}$ factors), increasing the amount of agent heterogeneity does not degrade the quality of the learned policy as the theoretical bound does not get worse.

Could the authors discuss how the learned policies can be implemented with function approximators like neural networks in practical settings?

Learning the policy and sharing it to all the agents is the computational bottleneck in practical settings. After this, it is efficient to implement the learned policies since the empirical distribution only takes $O(k)$ time to compute, and this dependency is tight. In Appendix J, we extended our algorithm to continuous spaces. In this set-up, the learned policy could be implemented with neural operators and other function approximators to parameterize and evaluate the policy.

Is there any guidance on how to select k in real-world tasks to balance performance and computational efficiency? How does SUBSAMPLE-MFQ compare empirically to recent centralized training and decentralized execution (CTDE) methods?

Theoretically, $k = O(\log n)$ suffices to have a decaying error rate with best efficiency, as we mention in Remark 4.6, and as is validated by our experiments. To the best of our knowledge, there is no previous CTDE method that utilized a similar parameterized (with respect to $k$) method for learning a MARL policy in the full-observation setting.

We hope this answers your questions, and look forward to further discussions.

Thank you,

Authors

We thank reviewer 1oj9 for their feedback. Please find our response below:

The paper may require a simulator to generate samples, and the number of samples per iteration could be very large, scaling exponentially with the size of the local state and action spaces. The method might be limited to the homogeneous setting.

Our algorithm assumes the existence of a simulator to generate samples. As the reviewer points out, this adds an $O(1)$ cost per iteration, resulting in a large query complexity. However, this query complexity was previously exponential in the number of local agents and in the state/action spaces, whereas our work reduces this to a polynomial dependence with the number of local agents and a sub-exponential dependence on the state/action spaces. Moreover, Remark 4.5 and Appendix I details a version of the algorithm that relaxes the assumption of having a generative oracle by only utilizing historical data (by reducing to off-policy $Q$-learning).

The algorithm's sample complexity appears to be less relevant to the time horizon , which is unusual in RL theory literature. If I understand correctly, it may be due to the large number of samples used in the Bellman updates. It would be beneficial to provide a detailed discussion on this topic.

In Appendix G.1, we show that a necessary condition of $T>\frac{2}{1-\gamma} \log \frac{\tilde{r}\sqrt{k}}{1-\gamma}$ is sufficient to allow the Bellman error to be on the order of $\tilde{O}(1/\sqrt{k})$. This enables Lemma 4.3 in the main body which allows us to abstract away the dependence on the time-horizon. We can add a parallel derivation that retains the $T$ factor via a $\gamma^T$ dependence in the final bound (which shows an exponentially decaying error with the time horizon $T$). Moreover, in Lemma G.10, we show that the query complexity is on the order of $O(mT|S_g||S_l|^k|A_g||A_l|^k)$, and we bound $T$ and set $m={\text{poly}}(1/(1-\gamma))$ to attain the $1/\sqrt{k}$ rate. We can make these dependencies more explicit in Theorem 4.2 in the final version of this paper.

Additionally, we can explain that our polynomial dependence on $\frac{1}{1-\gamma}$ may be loose since we do not use more complicated variance reduction techniques as in [1, 2, 3, 4] to optimize the number of samples $m$ which is used, in turn, to bound the Bellman error $\epsilon_{k,m}$. This was primarily because our goal was to analyze the necessary number of sampled agents as well as to keep complex algorithms as simple as possible (and incorporating variance reduction would significantly complicate the algorithm and intuition).

In the learning period, the algorithm still seems to require a centralized way to do value iteration and (greedy) policy improvement; it would be better to explain how it can be implemented in a practical setting.

Centralized learning is the only provable way for a multi-agent system to learn the true optimum policy in the full-information setting, as the optimum policy $\pi^*$ lives in a set whose cardinality depends on the joint state/action space. To clarify, there exists decentralized-training MARL algorithms with provable convergence guarantees to some equilibrium policy; however, these algorithms generally do not converge to the optimum policy. Since our algorithm only requires centralized training on $k\leq n$ agents, it is more scalable than previous optimum-searching policies. One practical suggestion that exploits the homogeneity of the local agents is to allow each local agent to compute the joint $Q$-function instead of having a controller share the learned policy with all the agents: this leads to a natural trade-off between the communication complexity and the sample complexity of the algorithm which can be optimized for in various practical settings, and we can add this as a discussion in Remark 4.8 in the main body.

While the proposed method is designed for homogeneous agents, it would be valuable for the paper to discuss how the approach might be extended to heterogeneous settings, especially when the agent types are numerous or drawn from a continuous space. Even a discussion of potential challenges or directions would strengthen the broader applicability of the work.

Indeed, while the current algorithm can only work for the homogeneous setting, we add two caveats:

1. As the reviewer points out, we mention an extension to a partially heterogeneous-agent setting by modeling types as a part of the state/action spaces of the local agents, in the “capturing heterogeneity” paragraph in page 4 and Remark 4.7.
2. There has been a line of recent work on extending mean-field MARL using a graphon-based framework that supports a continuum of distinct transition probabilities (which is also a form of heterogeneity). It may be possible to extend our subsampling framework to graphon mean-field MARL. Adapting this to our sampling framework may be highly non-trivial, and we leave this as an open problem for future works. Nonetheless, we can add a detailed discussion on this as part of Remark 4.7.

We hope this answers your questions, and look forward to further discussions.

Thank you,

Authors

====================

References:

[1] Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes (Sidford et. al., SODA 2018)

[2] Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model (Sidford et. al., NeurIPS 2018)

[3] Truncated Variance Reduced Value Iteration (Jin et. al., NeurIPS 2024)

[4] Variance-reduced Q-learning is minimax optimal (Mainwright, arXiV 2019)

We thank reviewer GLs2 for their feedback on our work.

While this is tractable from a computational perspective, the decentralized execution assumes a communication or observation network that can support this random sampling at scale. In a massively distributed system, this requirement could itself become a communication bottleneck, which complicates the "decentralized execution" claim.

Thanks for pointing this out. We can add some discussion on heuristics that derandomize the decentralized execution method, which may be more conductive for practical settings. Specifically, one practical implementation of the algorithm involves allowing the agents to share some randomness by only sampling within pre-defined fixed blocks of size $k$. We can add more detail on this and add this as a new section in the appendix.

To better contextualize their impact, could you discuss how you expect SUBSAMPLE-MFQ to perform on standard, complex MARL benchmarks like the StarCraft Multi-Agent Challenge (SMAC)? How does the structural assumption of your model (a global agent and non-interacting local agents) map to such environments, and what challenges would arise in applying your method there?

As the reviewer points out, the primary contributions of our work are theoretical, and we only provided simulations sufficient to numerically validate the theoretical result. For instance, the “Gaussian squeeze” experiment is similar to one conducted in the foundational mean-field MARL paper [1] which we ablate against. An even more thorough empirical study of cooperative multi-agent RL algorithms would be an interesting avenue for future research for empirical research, however, this is outside of the scope of our current work which focuses on some theoretical bottlenecks of MARL. At the present, some structural assumptions which resist applications of our methods in some standard MARL benchmarks involve the fact that our method only incorporates weak heterogeneity, as well as the fact that it is designed for cooperative multi-agent learning rather than more competitive/game environments.

Regarding the optimality gap, do we have any intuition on whether this rate is tight for this problem? Or could a different sampling or estimation strategy potentially achieve a faster rate, such as O(1/k)?

The algorithmic bottleneck in achieving a faster rate than $O(1/\sqrt{k})$ is actually from learning the $\hat{Q}_k$ function, rather than the online execution strategy; however, when $k = n$, our algorithm reduces to mean-field learning which has a rate of $O(1/\sqrt{n})$ (and is known to be tight in light of [1]). Thus, at least when $k =n$, our $O(1/\sqrt{k})$ rate is tight. This illustrates a natural obstacle against uniformly improving our $O(1/\sqrt{k})$ rate and perhaps suggests intuition for why our result might be tight.

We would be happy to answer any further questions.

Thank you,

Authors

========================

References:

[1] Mean Field Multi-Agent Reinforcement Learning, Yang et. al. (ICML 2018)

We thank reviewer APLY for their feedback on our work.

We did provide two experiments in Appendix B (page 16) corresponding to the motivating examples (Gaussian squeeze and constrained exploration) in Lines 126-145, to numerically validate the theoretical advantages of our SUBSAMPLE-MFQ algorithm. Across these experiments, we also provided figures that plot the log reward optimality gap as a function of $k$, the time taken for SUBSAMPLE-MFQ to compute its learned policy for varying $k$, and the cumulative discounted reward seen by the algorithm for different $k$.

We could plan to use the extra page in the camera-ready version to move some of the experiments to the main body. We hope this eases any concerns about the experimental validity of the algorithm, and we would be happy to answer any further questions.

Thank you,

Authors