Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning

Comment 1: I think Lemma 4.2 is not correct. The authors use the stationary distribution $\nu(\theta)$ to take the expectation. This is for infinite horizon ergodic RL without discount (the objective average of rewards through the trajectory). For objective with a discount factor, the distribution should be the cumulative discounted distribution.

Response: Thanks for catching this. We confirm that the citation in Lemma 4.2 is a typo and we should use cumulative visitation distribution. Fortunately, this typo will not affect the overall analysis in our paper. Denoting $\zeta(\cdot)$ as the state visitation distribution, we know that under Assumption 5.2, the stationary distribution $\nu(\cdot)$ not only exists but also satisfies the proportional relation $\nu(\cdot) \propto \zeta(\cdot)$ (See [1]). Therefore, by modifying Lemma 4.2 to

$\nabla_{\theta^i}J(\theta)=\mathbb{E}[\nabla_{\theta^i}\log\pi_{\theta^i}^i(a^i|s)\cdot\text{Adv}_{\theta}(s,a)|s\sim\zeta(\theta)],$

where $a\sim\pi_{\theta}(s)$, we only need to adjust $\kappa$ in Lemma 5.4 to a different $\kappa'$. With this modification, the subsequent analysis remains valid. We will correct Lemma 4.2 in our revision.

Comment 2: I have a personal concern about Assumption 5.5 where the authors assume a uniform upper bound for the score function and uniform positive lower bound for the Fisher information matrix. I am not sure if there exists (at least some simple) examples that satisfy these assumptions.

Response: Thanks for your insightful comment. Most related works in this area assumed $||\nabla_\theta\log\pi_\theta(a|s)|| \le M_g$, where $M_g$ is a positive constant [2-4] instead of $1$. Our intention in using $1$ was just to simplify the notations like [5,6]. But we agree with the reviewer that this simplification may lead to some unnecessary confusion. Upon carefully checking our analysis, we have identified the occurrences of $M_g$ in the following equations: Eqs. (17,26,29,32,34). We confirm that this simplification does not affect our main conclusion, as the notation $\mathcal{O}(\cdot)$ appropriately absorbs all instances of $M_g$. We thank the reviewer again for the careful reading. We will remove this somewhat unnecessary simplification and revise Assumption 5.5 and the related analysis in our revision.

[1] Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: An introduction (Vol. 1, No. 1, pp. 9-11). Cambridge: MIT press.

[2] Fatkhullin, I., Barakat, A., Kireeva, A., & He, N. (2023, July). Stochastic policy gradient methods: Improved sample complexity for fisher-non-degenerate policies. In International Conference on Machine Learning (pp. 9827-9869). PMLR.

[3] Ding, Y., Zhang, J., and Lavaei, J. (2022). On the global optimum convergence of momentum-based policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 1910–1934. PMLR.

[4] Yuan, R., Gower, R. M., and Lazaric, A. (2022). A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332–3380. PMLR.

[5] Xu, T., Wang, Z., & Liang, Y. (2020). Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems, 33, 4358-4369.

[6] Hairi, F. N. U., Liu, J., & Lu, S. (2022). Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward," in Proc. ICLR, Virtual Event, April 2022. Proc. ICLR.

Comment 1: My main concern lies in Lemma 4.2…

Response: Thanks for your comments. Please refer to our response to Comment 1 of Reviewer DPFS.

Question 2: Are $|\mathcal{S}|$ or $|\mathcal{A}|$ finite? Besides, in right column of Line 168, the dimension seems to be derived from softmax…

Response: Thanks for your question. This confusion is caused by a typo. The $|\mathcal{S}|$ and $|\mathcal{A}|$ in Line 168 right column should represent dimension of each state and dimension of each action, respectively. This implies that the dimension of each $\theta^i$ is at most $m(Dm+2d)$. Therefore, we do not need to assume a finite $|\mathcal{S}|$ or $|\mathcal{A}|$, and it is not related to Softmax layer as well. We hope this clarifies the confusion. We will fix it in our revision.

Comment 3: The rationale behind Assumption 5.1 and 5.8 is unclear to me. Besides, Assumption 5.8 appears to be a Lipschitz condition.

Response: Thanks for your comments. We'd further clarify as follows:

1. Assumption 5.1 is regarding the consensus matrix: The communication only occurs between neighbor agents in the graph, and their neighbor "is taken seriously with at least a weight of $\eta$". This ensures consensus convergence. Assumption 5.1 is a common assumption in the consensus optimization literature (e.g., see Assumption 3 in [R2], Assumption 1 in [R3]).

2. We agree with reviewer that we have made a typo in Assumption 5.8, and the terms "L-smooth" should be changed to "Lipschitz continuous." We thank the reviewer for catching this and will fix it in the revision.

Comment 4: The issue about bound in Theorem 5.10 increases with $N$.

Response: Thanks for your comments. We'd like to further clarify as follows:

1. We have checked and confirmed that the bound in Theorem 5.10 increasing with $N$ is correct. We note that this result is not surprising, since similar results also occur in many related works in the MARL literature [R2,R4-R5].

2. We respectfully disagree with the reviewer's assertion that "The purpose of using a multi-agent algorithm is to enhance speed." In our humble opinion, the need for modeling with multi-agent systems comes from the underlying real-world applications (e.g., autonomous swarm, drones, robotics networks, etc.), which may or may not be related to computation speedup. In other words, "computation speedup" may not and should not be the only purpose of using multi-agent systems. In fact, due to the loss of a central server in fully decentralized MARL systems, the computation speed could be negatively affected. Thus, in this sense, the $N$-dependence result in Theorem 5.10 can be viewed as a "price" to pay for the full decentralization.

On the other hand, we note that computation speedup in multi-agent systems often occurs in scenarios with centralized servers (e.g., federated RL with multiple agents coordinated by a server). In these scenarios, the reviewer is correct that linear convergence speedup with respect to $N$ is highly desirable. However, the focus of this paper is on decentralized MARL.

Comment 5: The numerical results in this paper…

Response: Thanks for your comments. However, we suspect that the reviewer might have missed our experimental results in the appendix. Indeed, all results regarding the trends of the key factors can be found in the appendix. More specifically, as stated in Sec. 6.1.(2), "More numerical results of ablation studies, which verify Theorem 5.10, can be found in Appendix B.1." Please see Fig. 5-10 in Appendix B.1 for more numerical results.

Question 6: In addition, I found the paper to be poorly written…

Response: Thanks for your comments. We'd like to clarify as follows:

1. We agree that $\nu(\theta)$ indeed occurs before its formal definition. However, we did this largely because of the necessity of introducing MSBE. To mitigate any potential confusion, we have explicitly reminded the reader after Eq. (6) with the following statement in Line 176, right column: "$x$ follows stationary distribution $\nu(\theta)$, which will be introduced in Lemma 5.4".

2. Regarding $A_{ij}$ and $A_{i,j}$, thanks for catching this inconsistency. This is indeed a typo and $A_{i,j}$ should be corrected to $A_{ij}$.

[R1] Sutton & Barto. Reinforcement learning: An introduction, Cambridge: MIT press, 1998.

[R2] Hairi et al. Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward, ICLR 2022.

[R3] Nedic & Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, Information Processing Systems, 2009.

[R4] Chen et al. Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis, ICML 2022.

[R5] Hairi et al. Sample and communication efficient fully decentralized marl policy evaluation via a new approach: Local td update. arXiv preprint 2024.

Due to the space limitation, we could only respond to a subset of more critical comments in this rebuttal. But we are happy to continue to complete our responses to your remaining comments in the discussion stage when new space opens up.

Comment 1: The introduction said works including (Chen et al., 2022) only ensures…

Response: Thanks for pointing out a related work. After reviewing [1], we acknowledge that their dec-NAC approach indeed guarantees global convergence. However, [1] is based on linear function approximation, while we consider nonlinear function approximation. Thus, our work remains the first in the MARL literature that achieves global convergence under nonlinear function approximation. We will clarify this in Sec. 1 (technical barrier) and Sec. 2 (global convergence) in the revision.

Question 2: Technical typos and Grammar mistakes.

Response: Thanks for catching: (1) In Theorem 5.10, we agree that it should be $\exp(-\Omega(\log^2m))$. (2) We will replace "due to" with "since". (3) Indeed, there is a typo, and the sample complexity should be $\Omega(N^2\epsilon^{-3})$. (4) the correct value is $\frac{1^\top}{N}$. We thank the reviewer’s careful reading and will fix these mistakes in the revision.

Question 3: In Algorithm 2, should the radius $B<\mathcal{O}(\epsilon)$? If not… How to explain?

Response: Thanks for your question and we'd like to clarify as follows:

1) Rigorously, the reviewer's statement should be written as $B=\mathcal{O}(\epsilon)$, which we fully agree with. However, this does not necessarily imply $B\leq\epsilon$, since the Big-O notation hides constant factors.

2) We confirm that the updated parameter $W^i$ for each agent $i$ remains within the projection ball centered at $W(0)$ in each critic loop according to Alg.2. However, this does not affect the correctness of Theorem 5.10. In our analysis, we are only required to show the estimated value function $\hat{Q}(\cdot;W^i)$ converges to $Q(\cdot;W^*)$, rather than the convergence of $W^i$. This analytical approach is also used by [2].

Question 4: Why are $H$ and $b$ fixed in DNN?

Response: To characterize the accuracy of the DNN, we follow the convention in the literature (e.g., [2,4]), which characterized the DNN capability under a fixed $H$ and $b$ setup. In our analysis, it is used for deriving Eq. 23 in Appendix.A.

Question 5: In Assumption 5.3, is there lower bound for reward?

Response: Thanks for catching this. We indeed want to assume $r_t^i \in [0, r_{\max}]$. We will fix this in the revision.

Question 6: Could you cite at least one paper that provides Lemma 5.4…?

Response: Thanks for your question. Lemma 5.4 is a mild condition widely used in the literature (e.g., [1,3]). $\kappa,\rho$ are dependent on the policy since they characterize the mixing time of the MDP under the policy.

Question 7: What's the intuition behind Eq. (14) of Fact A.3…?

Response: Thanks for your questions and we'd like to further clarify:

1. Intuition behind Eq. (14): The condition in Eq. (14) is analogous to the notion of stationary point in optimization, since $\delta\cdot\nabla_WQ$ serves as the gradient of $W$. Thus, Eq. (14) means that "there is no descent direction at $W^*$".

2. Understanding of Assumption 5.9: This assumption states that for all policy $\theta$, there exists some stationary $W^*$ satisfying the definition in Fact A.3, such that the $\epsilon_{\text{critic}}$ condition holds.

Question 8: What is $W_t^i$ in Fact A.2? Does "for the outer loop indexed by $t$" mean "at the $t$-th outer loop of Algorithm 1"?

Response: Thanks for your questions and we'd further clarify. Your understanding is correct: $W_t^i$ is $W^i$ after $K$ iterations in Alg.2 during its $t$-th leveraging in Alg.1. Since Alg.2 is a component of Alg.1, we refer to the $t$-th round of Alg.1 as "the outer loop indexed by $t$". Fact A.2 implies that the consensus process does not impact the average value. We will add these clarifications in the revision.

Question 9: Is there any theoretical result demonstrating that the total number of DNN parameters can be far less than the total number of state-action pairs?

Response: The answer is yes, which has been shown in [2,3] for single-agent RL. In this work, we generalize this insight to MARL. Please also refer to Response to Question 2 of Reviewer HEYR.

[1] Chen et al. Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis, ICML 2022.

[2] Cai et al. Neural temporal-difference and Q-learning provably converge to global optima, NeurIPS 2019.

[3] Gaur et al. Closing the gap: Achieving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization, ICML 2024.

[4] Gao et al. Convergence of adversarial training in over-parametrized neural networks, NeurIPS 2019.

We thank the reviewer for the constructive comments! We address the reviewer's comments point by point as follows:

Comment 1: The evaluation criteria are missing a comparison of the method to existing MARL algorithms to show performance differences. It would be great to discuss the differences with these in related works (such as MAPPO, MATD3, and COMA).

Response: The algorithms mentioned by the reviewer all follow a centralized training decentralized execution (CTDE). By contrast, our approach is based on consensus-based decentralized training. Since our work executes learning without any centralized task, it fundamentally differs from these related works and hence is not directly comparable.

Comment 2: The structure and presentation of the paper make it unclear which contributions are from previous work and which are from this work (such as Lemma 5.7).

Response: We would like to clarify that Lemma 5.7 is directly cited from a prior work. We have explicitly stated, “These two assumptions provide the following key lemma (Agarwal et al., 2021).” To further improve clarity, we will underline all citations in the next revision.

Comment 3: The authors argue that based on the results increasing the depth of the DNN improves performance, however, that is not the case in Figure 7.

Response: We confirm that our theorem indeed suggests that increasing the depth of the DNN benefits performance. Although it may not be easy to see this from Fig. 7, the overall trend aligns with our theoretical predictions: deeper networks $D$ generally perform better. To further explain this phenomenon, we note that certain theoretical conditions may not strictly hold in numerical experiments, which could account for the inconspicuous gap between our theoretical results and empirical observations.

Comment 4: Abstract unclear for which setting the global convergence is for. Besides, clarify the “non-competing” nature of the rewards, otherwise, the statements are wrong.

Response: We confirm that our work considers the cooperative setting, where multiple agents collaborate to maximize the long-term global cumulative reward. We acknowledge that our convergence result is specifically derived for this non-competing scenario. We thank the reviewer for pointing out this and will clarify this in Abstract in our revision.

Question 5: Agents learn independently, but the algorithm uses all agents’ actions. In particular, the critic has access to global actions. This affects the relevance of the considered problem. Could you give examples of applications that satisfy the considered setting where the critic has access to all agents’ actions, but agents operate independently?

Response: One example can be found in the carrier sensing multiple access (CSMA) protocol for wireless random access networks, where participating devices (agents) can listen to packet signals transmitted over the channel and be aware of the actions other devices have taken. In general, applications may include any system where the agents can observe one another (this is also needed for consensus) for information sharing, e.g., robotics, drones, vehicles, etc. In addition, we’d like to point out that joint action is widely assumed in the MARL literature [1-3].

[1] Zhang et al. Fully decentralized multi- agent reinforcement learning with networked agents, ICML 2018. [2] Zeng et al. Learning to coordinate in multi-agent systems: A coordinated actor-critic algorithm and finite-time guarantees. In Learning for Dynamics and Control Conference, 2022. [3] Wai et al. Multi-agent reinforcement learning via double averaging primal-dual optimization, NeurIPS 2018.

Question 6: How do your obtained results compare to the state of the art of 1-3 relevant settings? Besides, What were the main challenges in extending the results from the above settings?

Response: We appreciate the reviewer’s suggestions. While these are indeed interesting new directions for future work, establishing a global optimality theory for these new decentralized optimization problems is highly non-trivial and deserves dedicated papers. To provide some high-level intuition, we believe that the new handling of nonlinear approximation and consensus techniques: (1) will be important to the analysis for reasons similar to those illustrated in our Fig. 1; (2) can potentially be combined with other techniques, such as momentum, to further enhance performance.

Question 7: What are the benefits of using a decentralized algorithm over CTDE algorithms, and more broadly what is the motivation behind proposing a new decentralized algorithm?

Response: CTDE algorithms require that there must exist an entity for executing centralized tasks. Such a requirement may render the algorithms only applicable to a limited number of real-world scenarios. A fully decentralized algorithm on the other hand does not require a central entity.