Decentralized primal-dual actor-critic with entropy regularization for safe multi-agent reinforcement learning

We thank the reviewer for appreciating our work. We hope our responses below provide further clarity.

[Response to Weakness 1] Thanks for your questions. This property is motivated by the homogeneity of agents. For instance, consider a permutation $M$ that swaps a pair of agents $(i, j)$, where agent $i$ ($j$) executes the local action $a_j$ ($a_i$) based on the local state $s_j$ ($s_i$) after permutation. Due to the homogeneity of agents, agent $i$ ($j$) obtains the local reward $r_j$ ($r_i$) and the local cost $c_j$ ($c_i$) after permutation, which results in the permutation preserving property for the joint reward and the joint cost. In the revised manuscript, an illustrative example of our homogeneous constrained MG model is given in Appendix A.1, and some practical examples are given in Appendix A.2.

[Response to Weakness 2] Thanks for your question. For the indicator cost function satisfying $c_{i,t+1} = 1$ when agent $i$ is unsafe and $c_{i,t+1} = 0$ otherwise, our constraint $E_{s \sim \rho, \pi}[\sum_{t=0}^\infty \gamma^t \bar c_{t+1}] \le 0$ (by setting $b = 0$) is satisfied when $E_{s \sim \rho, \pi}[\sum_{t=0}^\infty \gamma^t c_{i,t+1}] \le 0$ for any $i \in N$. These individual constraints are consistent with those considered in existing safe MARL works [R1], [R2]. Note that the indicator cost function setting is considered in the Aggregation task and the Swapping task in our experiments. Additionally, several physical constraints considering the joint state of agents can be incorporated into our problem setting. For example, in the economic dispatch problem for smart grids, the power outputs of all generators should meet the requirement of the total power demand. In collaborative transportation tasks, the total upward force exerted by all agents must exceed the weight of the cargo.

[Response to Weakness 3] Thanks for your comment. Based on primal-dual optimization theory, the policy update in primal-dual-based safe RL algorithms typically requires a relatively larger learning rate, while the dual variable update requires a smaller one, which could lead to a slower convergence speed. However, combining this approach with deep RL architectures seems to mitigate efficiency concerns, as various primal-dual-based safe RL algorithms have demonstrated effectiveness within an acceptable number of episodes [R1], [R3], [R4]. Note that existing decentralized safe MARL algorithms also use the primal-dual method [R2], [R5]. Realize that these algorithms face severe learning efficiency problems in continuous safe MARL tasks (see the related work section in the manuscript for details). Our practical algorithm is developed based on the deep RL architectures, which preserves the decentralized training setting. Note that the entropy regularization mechanism is employed here considering exploration issues in continuous spaces. Therefore, while our theoretical algorithm may have a slow convergence rate, we enhance its efficiency through practical modifications, which takes a step towards the application of decentralized safe MARL algorithms in challenging safe multi-agent tasks.

Thank you very much for the time and efforts spent on reviewing our paper. We have tried to address all your concerns. Please refer to the following responses for details.

[Response to Weakness 1] We totally agree with your comments on decentralized MARL, where agents partially observe the environment (state, action, reward and cost) and share information with neighbors through a sparse network. Nevertheless, it still remains a huge challenge to design decentralized algorithms considering both theoretical convergence and learning efficiency under this setting. Fortunately, recent decentralized MARL algorithms have empirically demonstrated potential in addressing practical MARL tasks within a fully decentralized setting [R1], [R2], which are introduced in the related work section. Currently, there are two categories of decentralized algorithms: communication for parameter information and communication for state-action information. In the former category, the availability of the global state and action is usually assumed due to the coupled state transition function. Each agent updates its local policy based on the individual reward and cost information as well as the parameter information from its neighbors under practical communication conditions. In the latter category, the assumption on the availability of the global state and action is removed under an additional assumption on the spatial correlation decay property of weakly coupled MDPs. In these algorithms, each agent needs local state and action pairs from its $k$-hop neighbors when updating its local policy. However, existing algorithms in this category are on-policy, which only consider discrete spaces. Note that the spatial correlation decay property does not hold in many multi-robot coordination task. Furthermore, the communication condition is not robust, which cannot deal with link failures. Our work is more pertinent to the former, such that the global observability of the state and the joint action is assumed when providing convergence analysis on our theoretical algorithm. Nevertheless, it is also discussed in the manuscript that the mechanism of sharing local state-action pairs can be effectively combined into our practical algorithm to enable decentralized training without the global state and action information. An experiment considering limited environment information is also conducted in this work. More details can be found in Appendix J.5.

[Response to Weakness 2] Thanks for your comments. In this work, we solve a safe MARL problem under the decentralized training setting, where agents aim to maximize the team-average return and the joint policy’s entropy, while satisfying safety constraints associated to the cumulative team-average cost. Compared with existing decentralized MARL works [R3], [R4], the constraint in this work is centralized, which requires the joint policy and cost function information. Further explanation of our constraint can be found in our response to Weakness 2 for Reviewer bAPC. Even though existing decentralized MARL methods enable any individual agent here to approximate the dual function in this work in a decentralized manner. It remains a huge challenge to design decentralized update formulas for the dual variable $\lambda$ associated to the centralized constraint. One of the technical novelties of this work is the decentralized update design for the dual variable, where theoretical convergence is established based on multi-timescale stochastic approximation theory. Please note that existing decentralized safe MARL works stopped at the theoretical analysis stage [R3], [R4]. Our work further proposes a practical decentralized algorithm which is closely related to our theoretical algorithm. Compared with [R3], [R4], our algorithm can deal with continuous spaces and achieve off-policy training to improve sample efficiency. As mentioned in the response to Weakness 1, our algorithm can also be adapted under the local observability setting. In addition, our work is different from [R5]. In fact, the zero duality gap was discussed in [R5], where the theoretical results also hold for our problem (see the response to Weakness 4 for Reviewer bAPC for more details). However, the algorithm proposed in [R5] is not specific (see Algorithm 2 in [R5]), and no theoretical convergence analysis was provided.

Dear authors,

Thanks for your response; I appreciate your efforts in answering the questions and preparing more experiments. The revised paper has improved a lot and resolved most of my questions. I have some extra questions:

1. Although the availability of the global state and action in decentralized multiagent reinforcement learning is assumed in many published literature [R1, R2], I'm still unconvinced by this setting. Can you give practical examples to explain the motivation of this setting? Since the global state and action are available to all agents, why can't local reward and policy information be available globally, too?
2. At line 184, the policy set $\mathcal{\Theta}$ is compact and context. What is the intuition behind it?
3. At line 215, what is the intuition behind $K_z \ll |S| \times |A|$?

Thanks for reading this, and I am looking forward to your response.

Best

Reviewer

[R1] Zhang, Kaiqing, et al. "Fully decentralized multi-agent reinforcement learning with networked agents." International conference on machine learning. PMLR, 2018.

[R2] Ye, Lintao, et al. "Resilient Multi-Agent Reinforcement Learning With Function Approximation." IEEE Transactions on Automatic Control (2024).

Thank you very much for the time and efforts spent on reviewing our paper. We have tried to address all your concerns. Please refer to the following responses for details.

[Response to Weakness 1] Thanks for your comments. The policy sharing mechanism plays an important role in MARL, which improves scalability of MARL algorithms significantly. It has been studied in [R1] that the optimality of MARL problems can be preserved when agents share the same observation-based policy. However, these results cannot be applied to safe MARL directly as the satisfaction of constraints should be considered jointly. To this end, we extend the model proposed in [R1] under the safe MARL setting, and study the optimality and safety of safe MARL problems under the policy sharing setting (see Theorem 1). Theorem 1 justifies the use of the policy sharing mechanism in the safe MARL algorithm design for the first time, which is a very important contribution for safe MARL. We believe the reviewer will agree that any so-called 'novel' theoretical insight that fails to lead to a significant conclusion cannot truly be considered novel. In decentralized safe MARL, it has remained a huge challenge to deal with the update of the dual variable associated to centralized constraints before our work (please refer to the response to Question 1 for Reviewer bAPC for more details). In this work, a novel decentralized dual variable update step is designed, and the consensus and convergence of the dual variables which incorporate the projection operator in the local update are proven for the first time. Compared with existing decentralized safe MARL works [R2], [R3], the constraint satisfaction of the learned policies is further studied (see Propositions 1 and 2). These results constitute our second contribution. The third contribution of this work is the deign of our practical algorithm, whose novelty will be discussed in the response to Weakness 4.

[Response to Weakness 2] Thanks for your comments. The problem setting of this work is clear. It has been stated in the related work section that our work belongs to one category of decentralized works [R1], [R2], [R4], where each agent has access to the global state and action information, but the agent only knows its local reward and policy information. Here, the observation-based local policy setting is common, which has been widely used in CTDE-based MARL algorithms. Due to the availability of the global state, each agent can get the observation of the agents based on our homogeneous constrained MG model (see lines 242-243 in the revised manuscript). One advantage of using observation-based policies is that our algorithm can be naturally adapted under the local observation setting. Here, the global observation information becomes not available to agents. To obtain a good estimate of the global value functions, the agents can share its local observation-action pairs with its neighbors. Note that this trick has been used in another category of decentralized MARL works [R3]. More discussions on this regard can be found in the related work section and Appendix J.5 in the manuscript.

[Response to Weakness 3] Thanks for your comment. The assumption on the boundedness of the policy parameters is standard, based on which we directly use the estimate of the policy gradient to locally update the policy parameters in our algorithms. Similar settings can be found in various theoretical RL works [R1], [R2], [R4], [R5], [R6]. From a practical perspective, the learning stability of the policy parameters can be improved by setting smaller learning rates. It is worth pointing out that the entropy regularization mechanism employed in this work can further improve the learning stability of our algorithm due to its excellent sample efficiency (see our simulation results), which makes this assumption practical.

Dear Reviewer,

Thanks for your feedback. In practical environments, the communication resources among agents are limited, i.e., there is no all-to-all or centralized communication among agents. Thus, existing centralized-training-based MARL algorithms cannot be applied. This limitation inspires the development of decentralized MARL, where agents only communication through a sparse network. This communication condition has already been used in early distributed control tasks. Again, due to limited communication, each agent in decentralized MARL has no access to the local policy, reward and cost information of other agents. Based on this setting, we provide answers to your major questions or weaknesses:

1. Even the agents can share local reward, it results in extremely high communication costs as all agents should communicate for the reward information at each time step. Additional, even though the agents can obtain the global reward at each time step, they are still unable to update the dual variable which is associated to the joint policy. As a result, our method of sharing local parameter information is practical in decentralized safe MARL. In our rebuttal, we have successfully solved the problem on the decentralized setting raised by Reviewer rR6P (comment 1), and we don't find any additional question on our problem setting in the latest comments.

2. As stated in the responses to your former comments, the dual variable associated to the centralized constraint cannot be updated due to the lack of the joint policy. We thank the reviewer for introducing [1], which provided convergence for the single-agent case. However, in the decentralized MARL, we believe one important issus in this work is how to obtain similar convergence results (which use perfect information) under the decentralized setting (which use imperfect information, e.g., local policy, reward, and cost information). The reviewer may also find that the first decentralized work (zhang et. al, ICML 2018) is developed on the results for sinlge-agent actor-critic, whose main contribution is achieving decentralized learning of the global value function and the policy. The main theoretical of this work is achieving decentralized dual variable update, where we obtain similar convergence results as [1] with imperfect information.

As a result, we believe the reviewer may still have some misunderstandings about decentralized MARL. We feel sorry about this.

We sincerely hope our response can solve your current concerns.

Yours faithfully,

Authors

Thank you very much for your appreciation of our work. Many thanks for your time and efforts in reviewing this paper. Please refer to the following responses for details.

[Response to Weakness 1] Thanks for your comment. The setting of finite state and action spaces is standard, which forms the basis for many significant theoretical results on actor-critic methods [R1], [R2], [R3]. One of the theoretical contribution of this work is a convergent decentralized primal-dual actor-critic algorithm for safe MARL, where we leverage existing analytical analysis tools to obtain our convergence results. Hence, we also assume that the state and action spaces are discrete. However, based on several practical modifications, our algorithm can be directly applied to continuous safe MARL tasks (see Section 5 for details). Please note that the famous RL algorithm SAC [R4] was proposed similarly. In [R4], a soft policy iteration algorithm was proposed at first, which is convergent under the tabular setting. Then, SAC was proposed whose loss functions are developed based on soft policy iteration.

[Response to Weakness 2] Thanks for your interesting comment. Both our practical algorithm and MAPPO-Lag use the primal-dual optimization framework, and are designed to solve continuous safe MARL problems under the fully cooperative setting. However, the essential difference between our algorithm and MAPPO-Lag is the training fashion. As mentioned in the related work section, similar to existing MARL algorithms (e.g., MADDPG, MAPPO), MAPPO-Lag is also a centralized-training-based algorithm. This means it requires centralized or all-to-all communication to gather information (e.g., observations, actions, rewards, costs, and policies) from all agents for policy learning when addressing safe MARL tasks beyond simulation, which demands high communication resources. To overcome the difficulty, decentralized MARL have been investigated recently [R2], [R3]. Decentralized MARL algorithms aim to solve the problem considered by centralized-training-based algorithms over sparse communication networks to meet practical communication conditions. Our algorithm is decentralized, which eliminates the need for centralized or all-to-all communication required by MAPPO-Lag. Please note that it is not straightforward to design decentralized algorithms by simply combining parameter updates in centralized-training-based algorithms with parameter aggregation, as the information obtained by each agent is local. The difference between centralized and decentralized MARL algorithms, along with our contributions to decentralized safe MARL, is discussed in the Introduction and Related Work sections.

[Response to Weakness 4] Thanks for your comment. In fact, the convergence of our theoretical algorithm is obtained under standard assumptions which are commonly used in existing decentralized MARL algorithms [R2], [R3], [R5]. This point of view is also supported by Reviewer b1tN (see the Summary for details). Compared to existing decentralized MARL works without safety [R2], [R3], [R5], the theoretical analysis of our algorithm is more challenging due to the decentralized update of the dual variables. Note that the authors are also clear that these standard assumptions may limit applications of our method when dealing with practical safe MARL tasks. Similar to SAC, practical loss functions for the update of the critic, the actor and the dual variable are designed based on our theoretical algorithm, which allows us to employ deep neural networks during training and reuse samples based on the experience replay mechanism. Moreover, the learning rates of the critic, actor and the dual variable can be tuned depending on specific tasks. Additionally, we are unclear about the reviewer's comment regarding the learning rate. For deep RL algorithms without safety, we always set a relatively larger learning rate for the critic for finding correct parameter update directions for the actor. In primal-dual-based safe RL algorithms (e.g., MAPPO-Lag), the learning rate for the dual variable is typically the smallest to ensure learning stability. Therefore, the learning rate setting in our experiment aligns with our theoretical assumptions to some extent.

Thank you very much for the time and efforts spent on reviewing our paper. Thank you for the great summary on this work. We have tried to address all your concerns. Please refer to the following responses for details.

[Response to Weakness 1(a)] Thanks for your careful reading and constructive comments. Our work is developed based on existing works on decentralized MARL [R1], [R2], where the design of decentralized parameter update steps for both the critic and actor is inspired by those in [R2]. This enables each agent to obtain a decentralized estimate of the global value function associated to the optimized joint policy provided a fixed dual variable. Nevertheless, designing a decentralized update step for the dual variable associated with centralized constraints and establishing convergence for the entire decentralized algorithm have remained significant challenges prior to our work. Under the fully decentralized setting, the joint policy of all agents is not available to any individual agent, such that the gradient of the Lagrangian $L(\theta, \lambda)$ (formula (3) in the manuscript) w.r.t. $\lambda$ cannot be calculated by any individual agent. It is worth pointing out that it still remains an open problem to design decentralized algorithms considering centralized constraints for heterogeneous multi-agent systems. In this work, the decentralized update step for the dual variable is designed based on the policy consensus among agents, where each agent estimates the other agents' policies with its local policy. Further explanation of our centralized constraint can be found in our response to Weakness 2 for Reviewer bAPC.

[Response to Weakness 1(b)] Thanks for your comments. In this work, the convergence of the dual variables cannot be directly established using the analysis tools from [R1] and [R2], due to the incorporation of the projection operator in the local updates of the dual variables. Through the analysis on the projection terms, the convergence of the dual variables is established (Theorem 5). In addition, through the proof of Theorem 5, the reviewers can also observe that designing convergent decentralized algorithms for heterogeneous agents (i.e., agents with different policies) is very challenging.

[Response to Weakness 1(c)] Thanks for you comment. The development of our practical algorithm is inspired by the famous deep RL algorithm SAC [R3]. In [R3], a theoretical algorithm named soft policy iteration was proposed at first, which only considers finite state and action spaces. SAC was then proposed based on the theoretical algorithm for challenging continuous RL tasks, where the loss function for the critic was designed based on the TD error, and the loss function for the actor was designed based on the policy improvement step in soft policy iteration. Even though the modifications (actor/critic neural networks and replay buffer) in SAC were also developed before, we believe the key contribution here is turning the theoretical algorithm into practical loss functions. Note that our practical algorithm is developed similarly, which turns the parameter update formulas in the theoretical algorithm into practical loss functions. It is also worth pointing out that since each agent has not acess to the joint policy in the decentralized setting, existing works are limited to the on-policy training setting. In this work, the policy consensus of this work is leveraged by each agent to esimate the other agents' policy with its local policy. Finally, we show the difference between our work and [R4], [R5], [R6]. Both [R4] and [R5] proposed convergent decentralized safe MARL algorithms. Nevertheless, these algorithms are on-policy, and rely on the vanilla policy gradient for policy improvement. Note that they were only validated in environments with discrete spaces, with some even utilizing Q-tables during training [R4]. Our practical algorithm can deal with continuous tasks, and is sample-efficient by reusing samples, which takes a step towards the applications of decentralized safe MARL methods in practical safe multi-agent tasks. [R6] investigated the sub-optimality gap in primal-dual safe RL methods. However, no theoretically convergent algorithm was proposed in [R6].

Thank you very much for your appreciation of our work. Many thanks for your time and efforts in reviewing this paper. Please refer to the following responses for details.

[Response to Weakness 1] Thanks for your careful reading and constructive comments. In fact, all parts of the manuscript are closely interconnected. In Section 2, the homogeneous constrained MG model is introduced, where the different observation functions allow agents to behave differently under the same state $s_t$ when they are equipped with the same observation-based local policy. Note that sharing the observation-based policy among agents may harm the optimality of the safe MARL problem. This problem is tackled in Section 3. It is shown in Theorem 1 that (observation-based) policy sharing among agents preserve the optimality of our safe MARL problem in homogeneous constrained MGs. This inspires us to incorporate the (decentralized) policy consensus step in our theoretical algorithm design, which is also shown in Section 3. After the convergence analysis in Section 4, a practical decentralized algorithm is proposed in Section 5 to bridge our theoretical algorithm and DRL, whose effectiveness in dealing with continuous safe MARL tasks is shown in Section 6. In addition, similar to existing works on decentralized MARL [R1], [R2], [R3], the observation function is assumed to be bijective in this work. It is stated in the related work section and is also shown in Section 2.2 that the global state is available to each agent. We also discuss the local observation setting in the manuscript (see Appendix J.5 for details), where the observation-action communication mechanism can be incorporated, such that each agent can replace the state and the joint action information with locally obtained information in the critic design.

[Response to Weakness 2] Thanks for your comments. The justifications for our assumptions have already been given in Appendix C. These assumptions are standard for the convergence analysis of the proposed theoretical algorithm, which can be found in existing theoretical works on single-agent actor-critic [R4], [R5], [R6] and multi-agent actor-critic [R1], [R2], [R7].

[Response to Weakness 3] Thanks for your valuable comments. It is stated in the response to Weakness 1 that the optimality analysis for our homogeneous constrained MG model inspires us to incorporate the policy consensus update in our algorithm. Therefore, the policy parameter consensus should be proved in our theoretical analysis. Please refer to the consensus analysis in the proof of Theorem 4. Regarding the entropy regularization setting, the local update step for the critic is designed based on the Bellman function associated to the entropy-regularized value functions [R8] (see (2.7)-(2.8) in [R8]). Moreover, the local update step for the actor is designed based on both the vanilla and the entropy-regularized policy gradients. In the convergence analysis of the critics, the convergence of the critic parameters associated to the reward should be established independently, as the temporal-difference error under the entropy regularization setting is different (see the operators in (9) in the manuscript). In addition, in the convergence analysis of both the critic and policy parameters, the boundedness of the terms associated to the entropy regularizer should also be analyzed. More details can be found in the proof of Theorems 3 and 4.

[Response to Weakness 4] Thanks for your constructive comment. In our practical algorithm, the memory complexity of each agent is $O(H(2P + Q + 3))$, where $H$ denotes the upper bound on the number of the stored experiences, $P$ and $Q$ denote the dimensions of the state and the joint action, respectively. Additionally, the reward, cost, and done signals are also stored. Note that the memory complexity of storing the parameters of both the critic NNs and the actor NN is not included in the memory complexity mentioned above, which is due to that the storage of the replay buffer typically consumes the most memory in practice. The memory complexity of our algorithm is comparable to that of existing practical decentralized MARL algorithms [R1], [R2], which don't take safety into consideration.

Dear all reviewers,

Thank you for raising concerns about the theoretical novelty of this work. Here, we provided a statement of our theoretical contributions through the comparison with existing decentralized MARL works:

The authors in [R4] proposed the first decentralized safe MARL algorithm, where the constraints are functions of the joint policy of all agents. In their algorithm, each agent maintains a local copy of the parameters of the joint policy. When updating the dual variable of agent $i$, all agents must sample trajectories based on the local copy of parameters maintained by agent $i$ to calculate gradients, which in fact violates the decentralized training setting.

The constraint in [R3] is a function of the local state-action occupancy measure only, which cannot be used to model many practical constraints which are closely related to the joint policy.

As a result, the safe MARL problem which considers constraints associated to the joint policy has not been tackled under the decentralized training setting before our work.

Our safe MARL problem is general, whose constraint is associated to the joint policy. This poses a huge challenge for agents which has no access to the joint policy to update the dual variable based on the experiences sampled using its local policy. The theoretical contributions of this work are the design of the decentralized dual variable update step, and the convergence results of the dual variables base on multi-timescale stochastic analysis.

The novelty of this work has also been questioned due to its similarity to some unconstrained decentralized MARL methods [R1], [R2]. To the best of our knowledge, RL and safe RL are closely related, and many representative safe RL and MARL methods are developed based on existing RL and MARL algorithms. For example, CPO (MACPO) is developed based on TRPO (HATRPO), where only an additional condition for the constraint is developed based on the monotonic performance improvement theory. Nevertheless, safe RL still plays an important role in RL as various constrainted should be strictly satisfied in real-world tasks. In addition, it has also been stated in the reponse that the convergence of the dual variable in our algorithm cannot be establised based on existing decentralized methods, as the projector is incorporated into the local update for the dual variable.

We sincerely hope that the clarification of our theoretical contributions enhances your understanding of this work. We thank the reviewers once again for their professional and thoughtful evaluation of our paper.

Yours faithfully,

Authors