On the Hardness of Constrained Cooperative Multi-Agent Reinforcement Learning

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review comments. We have submitted a revised version with all revisions marked in "red". Please let us know if further clarifications are needed.

Q1: The hardness results are loose.

A: Thanks for pointing this out. We realize that our statement of hardness is not consistent with the actual contributions of the paper, as also pointed out by Reviewer WbB4. Therefore, in the revised paper, we follow the reviewers' suggestions and have changed the emphasis of our claim. Specifically, we changed "hardness" to "duality gap" in the title, and changed it to "challenging" or "challenges" throughout the paper. We also changed the emphasis of our main contribution, focusing on the nonzero duality gap and development of algorithms and their convergence results. We agree that it is challenging to figure out the specific complexity class of such a problem, and we think this is an interesting and fundamental problem deserving future research.

Q2: Does the hardness come from the safety constraints or the product constraints? Is the problem known to be hard without the safety constraints (with only the product constraints)? How much is known about this in the literature?

A: Great question. The hardness comes from both safety constraints and the product constraints. This is because if we remove either the safety constraints or the product constraints, the constrained cooperative MARL reduces to either cooperative MARL or single-agent constrained RL, both having polynomial time algorithms. We have clarified this in the second paragraph of Section 1.1 and at the end of Section 2.

Q3: Computational complexity and time complexity of the algorithms are not discussed.

A: Thanks for the great suggestion. We have added the complexity results to Theorems 3 and 4 in the revised paper. In these results we derive sample complexity (the total number of required samples), as it is a standard metric used in finite-time analysis of RL algorithms and is also proportional to computation and time complexities. We sketch the derivation as follows.

The sample complexity of Algorithm 1 (Primal-Dual algorithm) is $\mathcal{O}(\epsilon^{-5}\ln\epsilon^{-1})$. To elaborate, based on Theoren 3, Algorithm 1 takes $T=\mathcal{O}(\epsilon^{-2})$ iterations, and each iteration requires $\mathcal{O}(\epsilon_1^{-3}\ln\epsilon_1^{-1})$ and $\mathcal{O}(\epsilon_2^{-2})$ samples to obtain $\pi_t$ and $\widehat{V}_k(\pi_t)$ with precisions $\epsilon_1=\mathcal{O}(T^{-1/2})=\mathcal{O}(\epsilon)$ and $\epsilon_2=\mathcal{O}(T^{-1/2})=\mathcal{O}(\epsilon)$ respectively [1,2]. Therefore, the sample complexity of Algorithm 1 is

The sample complexity of Algorithm 2 (Primal algorithm) is $\mathcal{O}[T(\epsilon_2^{-2}+\epsilon_3^{-2})]=\mathcal{O}(\epsilon^{-4})$. To elaborate, based on Theorem 4, Algorithm 2 takes $T=\mathcal{O}(\epsilon^{-2})$ iterations, and each iteration requires $\mathcal{O}(\epsilon_2^{-2})$ and $\mathcal{O}(\epsilon_3^{-2})$ samples to obtain $\widehat{V} _ k(\pi_t)$ and $\widehat{Q } _{k_t}^{(m)}(\pi_t;s,a^{(m)})$ with precisions $\epsilon_2=\mathcal{O}(T^{-1/2})=\mathcal{O}(\epsilon)$ and $\epsilon_3=\mathcal{O}(T^{-1/2})=\mathcal{O}(\epsilon)$ respectively [2]. Therefore, the sample complexity of Algorithm 2 is

[1] Chen, Z., Zhou, Y., Chen, R. R., & Zou, S. (2022). Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis. In International Conference on Machine Learning (pp. 3794-3834). PMLR.

[2] Li, G., Wei, Y., Chi, Y., Gu, Y., & Chen, Y. (2020). Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 33, 12861-12872.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review comments. We have submitted a revised version with all revisions marked in "red". Please let us know if further clarifications are needed.

Q1: The bound seems to be trivial? It just comes from the geometric sum and assuming that the risk at each step is less than 1?

A: Yes, the simple bound $\Delta\le \frac{1}{1-\gamma}$ directly comes from the geometric sum and the assumption that the risk at each step is less than 1. In the revision, we have moved this result to the remark after Theorem 2. The main result of Theorem 2 is to prove the non-zero duality gap.

Q2: I'm not sure I see the only if part of Theorem 7.

A: Thanks for pointing this out. In the revised paper, we have added multiple bold subtitles to highlight the parts of "if" and "only if" in the proof of Theorem 7.

Q3: It would be good to offer some advice on when to use which type of algorithm.

A: Thanks for the suggestion. When the Q function can be approximated by a factorized form, the primal algorithm is preferred since the advantage gaps $\zeta_k$ in the convergence rate are small. Otherwise, there is no significant difference between these two algorithms based on our current understanding.

Q4: Some simulation would be helpful to illustrate the results.

A: Thanks for the suggestion. We are currently conducting MARL experiments in a real world environment and will keep the reviewer posted once the results are available.

Q5: The paper seems to want to say that the problem is NP-hard but stops short. It seems that the quadratic equality is more of an analogy rather than equivalence to standard optimization problems. It would be good to make this more precise.

A: Thanks for the great suggestion. We agree that it is challenging to figure out the specific complexity class of such a problem, and we think this is an interesting and fundamental problem deserving future research. We also realize that our statement of hardness does not reflect the actual contribution of the paper, as also pointed out by Reviewer WbB4. Therefore, in the revised paper, we have changed the emphasis of our claim. Specifically, we changed "hardness" to "duality gap" in the title, and changed it to "challenging" or "challenges" throughout the paper. We also changed the emphasis of our main contribution, focusing on the nonzero duality gap and development of algorithms and their convergence results.

Regarding the quadratic equality, our Theorem 1 strictly proved that the original RL problem (1) on the policy $\pi$ is equivalent to the optimization problem (4) on the occupation measure $\nu$. So this is not an analogy.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review comments. We have submitted a revised version with all revisions marked in "red". Please let us know if further clarifications are needed.

Q1: For the duality, the authors didn't discuss the connection to the duality of constrained Markov potential games: Provably Learning Nash Policies in Constrained Markov Potential Games. Since constrained cooperative Markov games are a particular case, a non-zero duality gap directly follows.

A: Thank you very much for pointing out this related work [1], which studies constrained Markov potential game with competing agents. In the case where all the agents share the same reward function $r_0$, the potential function $\Phi$ of the constrained Markov potential game reduces to the value function $V_0$ associated with $r_0$. Thus, we agree that the non-zero duality gap result in their Proposition 3 also applies to our case. In the revision, we have cited this work and added a remark after Theorem 2 to mention the related results.

We also want to highlight the differences between our work and this related work [1]. To elaborate, their work focuses on Nash equilibrium of constrained Markov potential game, which is very different from the optimal product policy of constrained cooperative MARL studied in our work. More specifically, in the special case where all the agents share the same reward (i.e., cooperative case), their Nash equilibrium corresponds to a feasible product policy $\pi$ where each agent's policy $\pi^{(m)}$ is optimal fixing all the other agents' policies $\pi^{(\backslash m)}$. Such a notion of agent-wise optimal product policy is weaker than the global optimal product policy studied in our work.

[1] Alatur, P., Ramponi, G., He, N., & Krause, A. (2023). Provably Learning Nash Policies in Constrained Markov Potential Games. ArXiv:2306.07749.

Q2: Experiments are done with artificial examples. It is favorable to check the performance of the two actor-critic algorithms for solving real constrained tasks, and compare it with existing methods as mentioned.

A: Thanks for the suggestion. We are currently conducting MARL experiments in a real constrained task
and will keep the reviewer posted once the results are available.

Q3: Is the product form of optimal policy the only reason for the nonzero duality gap? Does there exist a more fundamental metric that can characterize the cause of the nonzero duality gap?

A: Yes. In fact, even partially product form of optimal policy (e.g., only one agent is independent from all the other agents) can lead to nonzero duality gap. For example, the policy $\pi(a|s)=\pi^{(1,2)}(a^{(1,2)}|s)\pi^{(3)}(a^{(3)}|s)$ is a partially product policy for three agents, where agents 1 and 2 take joint action $a^{(1,2)}$ that is independent from the action $a^{(3)}$ taken by agent 3. Such a (partial) product form of the policy is the only reason that causes the nonzero duality gap.

Q4: Is it possible to remove such gap dependence? Which gap is better, duality gap and advantage gap? As shown in convergence analysis, the effect of the duality gap in different algorithms can be different. Does this suggest a better way to design algorithms?

A: Great questions. Our current analysis cannot avoid the duality gap for the primal-dual algorithm and the advantage gap for the primal algorithm. We think the dependence of the primal-dual algorithm on the duality gap is unavoidable due to the nature of primal-dual updates. In general, we believe this is a challenging problem that deserves future research.

On the other hand, we find that it is possible to remove the advantage gap for the primal algorithm by carefully selecting the initialization point. Specifically, in Example 1, all the advantage gaps $\zeta_0, \zeta_1, \zeta_2>0$, but the primal algorithm can still converge to the optimal solution under certain choices of initialization. Hence, the primal algorithm can be very sensitive to the initialization, indicating that the dependence of the convergence on the advantage gap $\zeta_k$ may not necessarily be tight. This indicates the possibility to address this issue by carefully selecting the initialization, which we leave for future study.

It is unclear whether the duality gap or the advantage gap is better, as neither of the primal-dual and primal algorithms strictly outperform the other one.

Thank you for the response. I have a few more questions.

For Q1, the difference with the work [1] is a bit vague to me. As I see, [1] also considers the product policy, and illustrates non-zero duality in a constrained QP problem.

For Q3, do partially product policies also introduce certain quadratic constraints in the occupancy measure?

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review comments. We have submitted a revised version with all revisions marked in "red". Please let us know if further clarifications are needed.

Q1: The contribution would be much more significant if the authors could also propose a solution to successfully solve this identified problem about the previous primal-dual algorithms for constrained cooperative MARL.

The proposed decentralized primal algorithm's convergence is hindered by a gap induced by the advantage functions, which can be seen as a major limitation. The comparison of the proposed decentralized primal-dual algorithm with the existing primal-dual algorithm doesn't seem to clearly indicate that the proposed new approach is a consistently superior approach, which makes the paper's contribution less significant.

A: Great comment. We agree that our current analysis cannot avoid the duality gap for the primal-dual algorithm and the advantage gap for the primal algorithm. This is a challenging problem that deserves future research. On the other hand, it is possible to address this issue by carefully selecting the initialization point. Specifically, in Example 1, all the advantage gaps $\zeta_0, \zeta_1, \zeta_2>0$, but the primal algorithm can still converge to the optimal solution under certain choices of initialization. Hence, the primal algorithm can be very sensitive to the initialization, indicating that the dependence of the convergence on the advantage gap $\zeta_k$ may not necessarily be tight. This indicates the possibility to address this issue by selecting the initialization, which we leave for future study.

Q2: The paper is highly theoretical, and comprehensive empirical validation/comparison of the proposed solutions are mostly missing. It would be great to also see some more comprehensive empirical experiment analysis on broad representative tasks (rather than just some very limited extreme case examples in current manuscript).

A: Thanks for the suggestion. We are currently conducting MARL experiments in a real constrained task and will keep the reviewer posted once the results are available.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review comments. We have submitted a revised version with all revisions marked in "red". Please let us know if further clarifications are needed.

Q1: Is the problem guaranteed to have a solution? Does it belong to PPAD, PPA, CLS, PLS? Change the emphasis of the paper to the main contribution rather than the hardness, since there is no definitive answer of the computational complexity..

A: Good question. The optimization problem in Theorem 1 has a solution since the feasible set is compact and the objective function is continuous. However, we do agree that it is challenging to figure out the complexity class of such a problem, and we think this is an interesting and fundamental problem deserving future research.

We really appreciate the reviewer's great suggestion on changing the emphasis of our claim. We do agree that our statement of hardness does not reflect the actual contribution of the paper. In the revised paper, we have changed "hardness" to "duality gap" in the title, and changed it to "challenging" or "challenges" throughout the paper. We also changed the emphasis of our main contribution, focusing on the nonzero duality gap and development of algorithms and their convergence results.

Q2: What were the main challenges you faced in proving a definitive refined hardness result?

A: The main challenge is to transform a known hard problem, e.g., NP-hard, into the optimization problem presented in Theorem 1, which has specific and complicated forms. This is necessary to prove that our problem is NP-hard (or belongs to some other complexity classes).

Q3: What would be the advantage gap if the reward functions admitted a network-separable structure and the transitions were additive?

A: Great question. For example, in the case where the reward functions and transition kernel are separable, i.e.,

$\overline{r}_k(s,a)=\frac{1}{M}\sum _ {m=1}^M r_k^{(m)}(s,a^{(m)})$

and

$\mathcal{P}(s'|s,a)=\sum _ {m=1}^M \theta_m \mathcal{P} _ m(s'|s,a^{(m)}),$

where $\theta_m\ge 0$ and $\sum _ {m=1}^M\theta_m=1$, the Q function is decomposable as follows.

where $\widetilde{Q}_k^{(m)}(\pi;s,a^{(m)}):=\frac{1}{M}r_k^{(m)}(s,a^{(m)})+\gamma\sum _ {s'}\theta_m \mathcal{P} _ m(s'|s,a^{(m)})V_k(\pi;s')$. Therefore, the advantage gap vanishes.

Q4: Do you think that the dependence on the advantage gap is tight? Can it be improved, or is it yet another indication of the hardness of approximation of solutions of constrained cooperative MARL problem solutions?

A: Great question. We think the dependence on the advantage gap is not tight and may be improved by carefully tuning the initialization. To explain, in Example 1, all the advantage gaps $\zeta_0, \zeta_1, \zeta_2>0$, but the primal algorithm can still converge to the optimal solution under certain choices of initialization. This indicates that the primal algorithm can be very sensitive to initialization and that the constrained cooperative MARL problem is challenging. We believe this is an interesting problem for future research.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review comments. We have submitted a revised version with all revisions marked in "red". Please let us know if further clarifications are needed.

Q1: The assumption of the decomposition scheme of the Q-function, that the advantage gaps depend on, seems limiting. Is the assumption necessary to ensure the computational tractability of the problem? Moreover, in practice, similar assumptions (on the linear decomposition of the Q-function) can harm performance, even in the unconstrained setting (e.g. see the comparison between VDN and QMIX (Rashid et al. 2020)).

A: Great question. Note that the convergence result in Theorem 4 does not rely on this assumption. Moreover, we showed in Appendix H that this assumption is necessary and sufficient to ensure a vanishing advantage gap $\zeta_k$. We agree with the reviewer that this assumption is restricted and may fail to hold in practical scenarios, and this echos our key point that constrained cooperative MARL problems can be challenging to solve.

Q2: It is not clear by the authors if the paper can be compared with other state-of-the-art algorithms (if exist) in terms of the optimality gap (in the constrained cooperative MARL setting).

A: Good question. To the best of our knowledge, no existing approaches for constrained cooperative MARL has convergence guarantee on the optimality gap. Specifically, as we discussed after Q1 in the introduction, the existing works only obtained either convergence of gradient norm (weaker than the optimality gap), or convergence of only part of the policy instead of the full algorithm. In the revision, we have added Table 1 to summarize this comparison.

Q3: In the proof of Theorem 3, why can we assign $\widetilde{\lambda} _ k$ to a larger value $2\lambda _ {k,\max}$ in the primal-dual algorithm.

A: Thank you very much for pointing out this and we have fixed it in the revised paper. Specifically, we changed the value of $\widetilde{\lambda} _ k$ from $2\lambda _ {k,\max}I\{V_k(\pi_t)\le \xi_k\}$ to $\lambda_{k,\max}I\{V_k(\pi_t)\le \xi_k\}$. Accordingly, we have doubled the value of $\lambda _ {k,\max}$ in Lemma 1 and showed that the optimal dual variable $\lambda_k^*\le \frac{1}{2}\lambda_{k,\max}$ (not $\lambda _ {k,\max}$).

Q4: In the proof of Theorem 7, can the authors be more explicit about the proof steps and explain what $\pi_{\omega}$ and $\omega$ are?

A: Thanks for checking our proof so carefully. In our revised paper, we have added bold subtitles to highlight the proofs of "if" and "only if" parts. We also added more intermediate steps and explanations to the proof of ``if'' part (i.e. the Q-function decomposition implies $\zeta_k=0$). We have also changed $\pi_{\omega}$ and $\omega$ to $\pi$. Thanks for pointing out this inconsistent notation.

Q5: In the proof of Lemma 3, can the authors be more explicit about the last inequality of page 33?

A: Thanks for checking our proof so carefully. We think the reviewer was referring to the following inequality. $\sum_a \Big|\prod_{m=1}^M\pi_{t+1}^{(m)}(a^{(m)}|s)-\prod_{m=1}^M \pi_t^{(m)}(a^{(m)}|s)\Big|$ $\le\sum_a \sum_{m'=1}^M\Big|\prod_{m=1}^{m'}\pi_{t+1}^{(m)}(a^{(m)}|s)\prod_{m=m'+1}^{M}\pi_t^{(m)}(a^{(m)}|s)-\prod_{m=1}^{m'-1}\pi_{t+1}^{(m)}(a^{(m)}|s)\prod_{m=m'}^{M}\pi_t^{(m)}(a^{(m)}|s)\Big|$ To exlain, for any fixed action $a$, denote $C_{m'}(a):=\prod_{m=1}^{m'}\pi_{t+1}^{(m)}(a^{(m)}|s)\prod_{m=m'+1}^{M}\pi_t^{(m)}(a^{(m)}|s)$ and then the above inequality can be obtained by the following triangle inequality $|C_M(a)-C_0(a)|=\Big|\sum_{m'=1}^M [C_{m'}(a)-C_{m'-1}(a)]\Big|\le \sum_{m'=1}^M |C_{m'}(a)-C_{m'-1}(a)|.$ We have added this clarification to the revised paper.

Thank you for adding an illustrating experiment. It looks the nonzero duality gap of optimal product policy doesn't make difference between two algorithms. Is this also characterized in their convergence rates?