DECENTRALIZED MULTI-AGENT REINFORCEMENT LEARNING VIA ANTICIPATION SHARING

Thank you for your positive feedback on our paper. We appreciate your recognition of the clarity and rigor in our explanations and proofs, and we're pleased that our figures effectively showcase our research findings.

Motivation for AS and comparison with existing methods. Thanks for pointing out that the proposed methodology has not been motivated sufficiently. We have taken this important observation into account in our revised manuscript.

In summary, the primary motivation for developing AS was to address the limitations of existing decentralized MARL methods, which often rely on sharing rewards, values, or model parameters. These conventional methods can lead to challenges such as privacy concerns and computational inefficiencies. AS offers a novel approach by focusing on sharing action distributions, which we argue is potentially less invasive and more privacy-preserving for agents compared to exposing detailed model parameters or reward functions directly. This shift in information sharing paradigm is central to AS's proposed contribution. We hypothesize that by sharing anticipated actions instead of full internal model details, agents may be able to achieve more effective coordination while maintaining a greater degree of autonomy and privacy.

We also wish to emphasise that anticipation sharing was undertaken in a distributed manner during training only. The resulting learned policy networks of other agents are not activated at test time. In the revised manuscript (Appendix.E, page 17), we have included a system diagram to help explain the distributed, private nature of the AS approach visually.

Why sharing action distributions is a better assumption. Sharing action distributions, as opposed to rewards, values, or model parameters, strikes a balance between the need for effective coordination and maintaining individual agents' privacy. While it does involve sharing a significant amount of information, it circumvents the direct exposure of an agent's internal decision-making process, which can be sensitive in many applications. We believe that this approach can be particularly advantageous in scenarios where privacy and security are paramount, and where the sharing of detailed internal states or policies is not feasible. We have stressed this point more in the revised version.

Definition 2. We appreciate your attention to Definition 2 and the opportunity to clarify it further given its importance. It appears there may have been a misunderstanding regarding the expectation over individual anticipated advantages. This expectation is indeed calculated over the anticipated joint actions, denoted as $\tilde{\pi}^i$, not over $\pi'$. The key distinction here is that each agent in our framework optimizes based on its anticipated joint policy ($\tilde{\pi}^i$), rather than $\pi'$. This is a crucial aspect of our approach, as it enables decentralized optimization - each agent individually anticipates and adapts to the actions of others without the need for central coordination or access to the true joint policy. This decentralized nature of policy anticipation and adaptation is what allows our method to be applicable in settings where sharing detailed internal models or policies is not feasible. In the revised manuscript, we have elucidated this point more clearly to avoid any confusion.

We are pleased that our AS approach in decentralized MARL is recognized as innovative. We are also glad that our approach of combining theoretical analysis with simulated environment tests has been acknowledged.

Scalability and robustness. Our simulated tests in relatively simple environments are intended as preliminary validations of the fundamental approach. We recognize that demonstrating scalability and robustness requires evaluation across more heterogeneous, dynamic scenarios.

Per your insightful guidance, in the revised Appendix of the manuscript (page 16), we have expanded the manuscript to include experiments regarding scalability study. Please let us know if the revised experiments help assuage the concerns over scalability and robustness testing.

Redundancy in writing. We have taken your feedback about the occasional redundancy in our writing into consideration. The revised manuscript has been edited accordingly.

Handling non-stationarity. Our method addresses this challenge by incorporating a mechanism designed to predict and adapt to changes in agents' policies over time. This approach is proactive in nature, aiming to stabilize the learning process and enhance coordination among agents by reducing the unpredictability that arises from these continuous updates. By anticipating potential policy shifts of other agents, each agent can adjust its strategy more effectively, leading to a more stable learning environment. However, fully addressing the complexities of non-stationarity in MARL remains an open challenge requiring further research. This will be a focus as we continue developing the anticipation sharing approach.

Credit assignment in conflicting goals. Credit assignment in multi-agent reinforcement learning typically arises in settings where a singular team reward is shared among agents. Our research, however, focuses on decentralized learning environments where such a team reward is not available, and each agent only has knowledge of its individual reward. In these scenarios, rewards may often be in conflict, meaning an increase in one agent's reward could potentially lead to a decrease in another's.

In our setting, the challenge is not so much about assigning credit from a collective reward, but about maximizing individual returns in a way that also contributes to the overall system's effectiveness. This is where our anticipation sharing framework plays a crucial role. It aims to improve coordination among agents by enabling them to balance their own objective and other agents’ objectives via constraining the policy with the anticipations from others, since the anticipations from others contribute to maximizing other agents’ objectives.

While our approach focuses on enhancing coordination to potentially reach a maximal total return, it does not directly solve the credit assignment problem typical in environments with shared team rewards. Instead, it addresses the unique challenges of decentralized learning where independent reward maximization might lead to a Nash Equilibrium, rather than a collective optimum. This distinction is critical to understanding the context and objectives of our research in decentralized multi-agent systems.

We have edited the manuscript to make these points clearer, such as the second paragraph of the Introduction, and the two paragraphs after Eq.11 in Section 4.2.

Related work on opponent modelling. Your suggestion to include related works on opponent modeling is well-received. Indeed, our approach shares some similarities with opponent modeling in the context of solving other agents' policies. However, the anticipations are fundamentally different from predictions or estimations of other agents’ decisions used in opponent modelling. Specifically, the anticipation of agent $i$ to agent $j$, i.e., $\pi^{ij}$, is solved to optimize agent $i$’s objective (Eq.11). The constrains in Eq.11 include the discrepancy between the anticipations $\pi^{ij}$ and the true action distribution of other agents, $\pi^{jj}$, which causes a similarity to opponent modelling. However, the discrepancy is not the primary optimization objective, but instead a constraint when maximizing the agent’s own objective. The anticipation $\pi^{ij}$ is then sent to agent j, so that when agent j maximizes its objective, it can balance agent i’s objective.

For opponent modelling, agent i estimates agent j’s action or other information in order to take them into account when solving its (agent i’s) policy. However, in our method, the anticipations is solved together with agent i’s own policy to maximize agent i’s objective. It is agent j who takes into the anticipations from agent i to solve its (agent j’s) policy.

It should also be noted that agent $i$’s own policy $\pi^{ii}$ is adjusted in accordance with the discrepancy between it and $\pi^{ji}$, the anticipation of the other agent $j$ about agent $i$ policy. This constraint is taken into account for the purpose of further enforcing the agreement between what is locally learned and what other anticipates, which is not the objective in opponent modeling.

In the revised manuscript, we have expanded the Related work in Section 2, and included a relevant paragraph (the last paragraph in Section 4.2) to explain the above points.

Real social dilemmas and partial observability. We believe that, in more challenging scenarios, particularly those involving dilemmas, our method's capacity to facilitate agent coordination through shared anticipations is critical. The anticipation sharing mechanism equips agents with insights into other agents’ objectives, aiding in navigating complex dilemma situations. However, we acknowledge the need for further empirical studies in these environments to validate the efficacy of our approach under such conditions.

Regarding partially observable settings, our current theoretical framework is primarily oriented towards fully observable environments. Extending our approach to partially observable settings would require adaptations to account for the uncertainties and incomplete information inherent in such environments. While the core principles of anticipation sharing remain relevant, their application in partially observable scenarios would necessitate additional mechanisms to handle the lack of complete information. We recognize this as an important direction for future research to ensure the robustness of our method across a broader spectrum of multi-agent settings.

Typo in Theorem 1. Thanks for pointing it out. We have revised \E_s^\prime as \E_{s^\prime} in proof for Theorem 1, after Eq.20 (Eq.22 in the revised paper).

General comments. Thank you for your positive remarks on our mathematical approach and the intuitive appeal of our proposed clipping method. We share your optimism that, given the success of PPO in various settings, our method is likely to yield performance improvements in decentralized MARL scenarios.

Centralisation issue. In addressing your concerns regarding the centralization aspect of our method, we firmly assert that our approach fundamentally diverges from conventional centralized learning systems. Firstly, each agent in our system operates with autonomy, learning policies based on their own reward signals and shared anticipations, without any central unit aggregating all information. This decentralized framework inherently differs from traditional centralized methods where a single entity controls or processes all information.

Secondly, the sharing of policy information in our model does not equate to full centralization. Agents exchange only their action distributions for the states they encounter, rather than sharing entire policy parameters. This partial information sharing, coupled with the individual reward knowledge each agent possesses, ensures that our method maintains a decentralized essence. The theoretical proofs are based on a fully-connected network topology, which gives a condition of the optimality. Our practical algorithm provides a general setup where the network topology does not need to be fully-connected. Experimental results demonstrate descent performance in several different tasks.

We emphasized these two points in our revised paper. Specifically in the last paragraph in Section 4.2 and the first paragraph in Section 4.3.

Local Nash equilibria. This question is critical to understand the problem we solved in this work. When each agent optimizes its own return without considering other agents, they will reach Nash equilibira, which might be local optimum. Social dilemma examplifies this problem. However, the aim of our method is to achieve global optimality (Eq.1) instead of local Nash equilibria. In a decentralized multi-agent system, no single agent has access to global information about the full joint policy or other agents' exact policies. Our method derives a lower bound of the global objective, which can be decomposed into individual objectives that involve the agent’s own policy and policy anticipations to other agents. The anticipations are different from predictions or estimations of other agents’ decisions used in opponent modelling. Specifically, the anticipation of agent i to agent j, i.e., $\pi^{ij}$, is solved to optimize agent i’s objective (Eq.11). By maximizing the lower bound of the global objective, the global optimality rather than local Nash equilibria can be achieved.

Based on the theoretical results, we proposed a practical algorithm to solve Eq.11. Deriving rigorous guarantees for convergence is notoriously challenging in decentralized multi-agent reinforcement learning problems because of this complexity. In future work, we aim to explore alternative optimization strategies that may allow us to leverage existing theoretical support and attempt to derive convergence results. While the current algorithm represents an initial practical approach grounded in our theoretical framework, we believe that investigating other techniques with more established guarantees represents an important research direction.

Response to Questions:

Difference between value estimation and anticipation: Thank you for giving us the opportunity to clarify the important difference between value estimation and anticipation.

Calculating the value function of other agents involves estimating the expected returns or outcomes of their actions, typically based on observed behaviors and strategies. The focus is on understanding what outcomes other agents aim to achieve.

In contrast, as defined in our work, anticipation goes beyond mere outcome estimation. The anticipation $\pi^{ij}$ is solved to optimize agent i's objective (Eq. 11). $\pi^{ij}$ is then sent to agent j, so agent j can balance agent i's objective when maximizing its own. Additionally, agent i's policy $\pi^{ii}$ is adjusted based on the discrepancy with $\pi^{ji}$, agent j's anticipation of agent i. This constraint further enforces agreement between local learning and others' anticipations.

Therefore, the anticipations include the information about individual objectives implicitly. By exchanging the anticipations, individual agents can balance others' objectives and thus the collective performance when optimizing its own objective. We highlighted this point in our revisded manuscript, see the two paragraphs after Eq.11 in Section 4.2.

We hope that the revised manuscript does a better job at highlighting this conceptual nuance.

Advantage of using the surrogate optimization objective: In the original objective (Eq.1), the optimization target is the true joint policy, which is infeasible in decentralized settings where each agent does not have access to other agents' true policies and cannot dictate to others how to update their policies.

The surrogate objective stems from the lower bound (Eq.9) of the original objective, which can be decomposed into individual objectives that optimize the anticipated joint policy consisting of the agent’s own policy and policy anticipations to other agents. The anticipated joint policy is solved by each agent, which is not the true joint policy composed of the true individual policy of each agent, as defined in Definition 1.

The surrogate optimization objective introduced in Section 4.2 offers a more tractable solution to the complex problem of multi-agent coordination under uncertainty. It simplifies the optimization landscape, making it feasible to find solutions that, while not globally optimal, are practically effective. This objective also helps in balancing the computational complexity with the benefits of improved coordination, which is particularly valuable in environments where exact solutions are computationally prohibitive.

We believe that the revised manuscript (Section 4.2) is significantly clearer about these key aspects.

Motivation and derivation of constraints in Section 4.2: Thank you for allowing us to clarify the origins of the constraints presented in Section 4.2 (Eq.10 and Eq.11). We appreciate you highlighting this component for further discussion.

You raise an excellent point - the constraints are directly motivated by the lower bound in Section 4.1, Eq. 9. Specifically, the constraints in Eq. 10 derive directly from Eq. 9, with the focus on optimizing $\pi_{new}$ while fixing $\pi_{old}$. They ensure the surrogate optimization aligns with multi-agent practicalities.

Further, Eq. 11 stems from separating out the agents in Eq. 10's constraints and anticipations. This separation is key for decentralized optimization where each agent acts based on its policy and anticipations of others.

We have expanded the manuscript to provide a detailed, step-by-step explanation of how these constraints emerge from the underlying optimization formulation. We aim to elucidate their motivations and relevance to the MARL setting.

Explanation of Results in Figure 1: Figure 1 illustrates the performance of our method in various simulated environments. We have enhanced this Figure's explanation by detailing the specific characteristics of each environment and how they interact with our method. This includes a discussion on the factors contributing to the observed performance trends, providing a clearer understanding of the effectiveness of our approach in different settings. Please see Section 5.2 in the revised manuscript.

Performance for certain environments: Our approach is especially relevant in settings where agents cannot exchange values or rewards due to privacy constraints. In such scenarios, our method offers a means of coordination without compromising individual agent privacy. Therefore, the aim of our study is not to outperform the baseline algorithms in every scenario but to provide a viable alternative in such challenging settings. Additionally, our method is underpinned by a theoretical framework designed for stability across a variety of tasks. This theoretical basis may contribute to more consistent performance, as opposed to methods like VS, which might excel in certain tasks but struggle in others.

Clarification of theoretical statement: You are correct that this statement (”theoretically, we established that the difference between agents”) stems from our theoretical framework, particularly Theorem 3 and Eq. 9 as described in the manuscript. The LHS of Eq.9 represents the original multi-agent collective objective. The first term on the RHS is the summation of individual objectives from Definition 2 and Eq.6.

Critically, the last term in Eq.9 encapsulates the difference between actual action distributions and anticipations from others. Therefore, as you noted, Eq.9 establishes that this difference bounds the discrepancy between individual and collective goals. This highlights the significance of anticipation sharing for aligning behaviors with group objectives.

Per your helpful feedback, we have significantly revised the presentation of the methodology in the new version of the manuscript to address this point more clearly. Please let us know if the updated explanation provides adequate clarification on how this key theoretical result relates agents' anticipations to collective outcomes. We appreciate you highlighting this opportunity to strengthen the clarity of our framework.

Response to Weakness:

Mathematical underpinnings and proofs. Thank you for your careful reading of our paper and for raising these important points. We appreciate you taking the time to provide such thoughtful feedback.

Regarding Section 4.1, we want to clarify that the key inequalities were already defined and proved in the original Appendix. We have aimed to improve the presentation and clarity of the corresponding theorems in the main text, to better highlight their role in building our proposed solution and strengthen the logical flow. The detailed proofs remain in the Appendix. Please let us know if the revised framing of the theorems makes their implications and connectivity clearer, given that the foundational inequalities were established in the first submission.

We also appreciate you noting the need for more background on the surrogate optimization objective introduced in Section 4.2. In our revised manuscript, we have worked to motivate and explain this component more completely, in order to elucidate its rationale and benefits.

Surrogate Objectives and Constraints in Section 4.2 and 4.3. Thank you for your suggestions regarding the presentation of the surrogate objective and the constraints in Section 4.3. Upon reflection, we agree the original drafting could be improved for clarity and accessibility.

In Section 4.2, we leverage the lower bound given by Theorem 3 to maximize the orginal collective return, since the collective return is intractable without a global view. By omitting irrelevant terms, we have a surrogate objective Eq. 10. Further, to make it feasible in decentralized MARL, we reformulate it from each agent's limited perspective. Remarkably, we can distill the relevant components into a local objective and constraints for each individual agent, which leads to Eq.11. To practically solve Eq. 11, in Section 4.3, we propose an algorithm, involving specific steps, each targeting different aspects of the optimization challenge. In the revised manuscript, we have rewritten Sections 4.2 and 4.3 to explain the surrogate objective and the constraints in a more intuitive, step-by-step manner. Please let us know if the revised explanation provides adequate insight into how the surrogate objective and the constraints emerge from the optimization problem. We welcome any additional feedback on making this section clear and complete.

Evaluation results: In our revised manuscript (Section 5.2), we delve into a more detailed analysis to explain the varying performance levels of different methods, including our own.

However, it is important to note that the primary aim of our study is not to outperform the baseline algorithms in every scenario but to provide a viable alternative in more complex and heterogeneous environments. Our approach is especially relevant in settings where agents cannot exchange values or rewards due to privacy constraints. In such scenarios, our method offers a means of coordination without compromising individual agent privacy.

Additionally, our method is underpinned by a theoretical framework designed for stability across a variety of tasks. This theoretical basis may contribute to more consistent performance, as opposed to methods like VS, which might excel in certain tasks but struggle in others.

Performance in the Predation task: Thank you for raising this insightful point regarding the similar performance observed in the Predation (Pred.) task compared to value sharing (VS). We acknowledge that this outcome warrants further investigation in our revisions.

Our initial hypothesis is that the characteristics of the Pred. task, where agents are homogeneous with a common target, might inherently lend themselves to approaches like VS, thereby explaining the similarity in performance.

In the revised manuscript (Section 5.2) , we have included a more comprehensive analysis of the performance in the Pred. task, exploring why our approach shows similar effectiveness to VS in this particular scenario and highlighting the distinct advantages our method offers in diverse and privacy-sensitive environments.