Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies a single timescale decentralized actor-critic algorithm. The setting is as follows. Each agent attain their respective action, and reward. There is also a global state which is observed by all the agents. Each of the agents attain a low low dimensional approximation of the rewards function, the value function, and the policy. At each time step the agents update these parameters using a single sample from the environment, either iid or Markovian. The authors show the sample complexity of their algorithm for both iid and Markovian sampling, and show that it attains the lower bound for such sample complexity. 
strengths_and_weaknesses: - My main criticism of this work is that I do not see much advantages of the results in this paper over the one in [5]. The authors argue that they study a single timescale algorithm compared to [5] which studies a two timescale algorithm. However, I have two comments about that. First of all, I believe the result in [5] is not two timescale. In particular, the step sizes for both actor and critic are constant. The only issue with [5] might be the need to have an inner loop and an outer loop. But I do not see a significant problem with this structure. The reason is that the sampling is not affected during the move from inner loop and outer loop. In [5] the sampling is through a single trajectory throughout the performance of the algorithm. Can the authors explain why their results are better than [5], or why their algorithm has an advantage over [5]? I am willing to increase my score if this is addressed.
- The main strength of the paper is a convergence bound which attains the lower bound up to logarithmic factors.
questions: - You did not define what is \lambda_max in line 205. 
- Can you express the communication cost of the algorithm and compare it with the related work along with the sample complexity?
- Why not characterize the convergence for natural actor critic as well? I believe establishing the result should be straightforward given the current results. Note that natural actor-critic can guarantee global convergence.
limitations: The main suggestion for improvement has already been suggested. I suggest to include the convergence of the natural actor critic as well as the communication cost of the algorithm.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper develops the finite-time analysis of a single-timescale multiagent actor-critic algorithms. The sample complexity is $O(\epsilon^{-2}$, which matches with the sota. Many existing studies use approaches e.g., double loop, minibatch to simplify the analysis, which introduces additional parameters in practice, and thus are not preferred. This paper shows that a single time scale update can also achieve the same order of sample complexity for the problem of decentralized MARL.

strengths_and_weaknesses: Strengths:
1. The analysis in this paper is of more practical interest as it focuses on the single-timescale update rule, which does not involve additional tuning parameters e.g., batch size, inner loop iterations.

2. The complexity of the single-time scale method matches with those double-loop, mini-batch methods in the literature.


Weaknesses:

1. This is not essentially a weaknesses, more like a suggestion. It shall be highlighted in the paper why those double-loop and minibatch approaches with inner loop iterations =1, minibatch size =1, fail to obtain a complexity of $O(\epsilon^{-2}$; and what term needs a tighter bounds than those approaches?


questions: There is one paper in the literature also shows that a single-time scale update can also achieves the same sample complexity as those approaches using minibatch or double loop. Their algorithm does not need a double-loop structure not a mini-batch approach, and only uses one single sample at each time step. The analysis is novel in that they bound the tracking error, (or equivalently, the critic error in this paper) using the gradient norm of the objective so that they can obtain a tighter complexity bound. How does the approach in this paper compare to that one?
Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation, NeurIPS 2021. 


limitations: The algorithm in this paper requires the action to be globally observable, which may not be possible in practice.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The submission solves corporated MARL via decentralized AC. Specifically, the authors consider single timescale update of AC (i.e., the actor, critic, and reward estimation take stepsizes of the same order). In theory, the authors show that under linear function approximation, AC converges to a stationary point under i.i.d. and Markovian sample schemes, respectively. 

strengths_and_weaknesses: Strengths:
 - Single timescale AC is widely adopted in practice but lack of theoretical understanding, even in the scenario of single agent with linear function approximation. Most theoretical works aiming to show convergence of AC end up considering two-timescale or bilevel updates, which ensure the approximate convergence of critic update before the update of actor. The submission not only consider the single-timescale AC, but also establish the convergence of such algorithm in MARL setting, which closes the gap between practice and theory for the first time, to the best of my knowledge. 
 - As pointed out by the authors, previous works [8] use LSTD in critic update to study single timescale AC. The naive sample complexity of [8] is $O(\varepsilon^{-4})$. Further, they propose to use off-policy to improve the sample complexity to $O(\varepsilon^{-2})$, which matches the sample complexity in the submission. In comparison, the submission uses TD(0) in the critic update, which is more similar to the practical use. 

Weaknesses:
 - The submission only shows convergence to a saddle point, instead of an optimal point. Previous work [5] seems to have a stronger result showing optimality, though adopting a bilevel scheme. 

questions: Questions:
 - A discussion on the communication frequency $K_c$ with the final rate of convergence would be interesting. The choice of $K_c$ seems only appear in the introduction (line 71) without much further explanation in the paper. 
 - I checked other single timescale methods, especially ALSET [3] and STABLE (Chen, Tianyi, et al.). Compared with the two-timescale algorithm TTSA (Hong, Mingyi, et al.), both ALSET and STABLE seem to put much effort into a careful design of the update formulae, especially on the upper level (eqs (8)(9) in STABLE and eqs (9)&(10) in ALSET). And they claim that this is why they can achieve convergence under single timescale updates (sec 2.2 in (Chen, Tianyi, et al.)). In comparison, Algorithm 1 in the submission seems to be simple yet efficient, since it only consists of a TD(0) in the critic update and an advantage actor in the actor update. It will be great if the authors can explain more on such a comparison, which will definitely bring more intuition to the proof idea. 
 - Can the authors also compare with [18] in terms of the proof technique used for single agent AC?

Minor issues:
 - The definition of the function $\omega^*$ seems first appear in the appendix (line 613) but is used before in the paper (line 145). 

 - Line 206: $\varphi(s_{|\mathcal S|}, a_{|\mathcal A|})$

 - Algorithm 1 line 4: $s_k \sim \mu_{\theta_k}(\cdot)$

 - Eq (5): should be $\omega_{k+1}^i$ instead of $w_{k+1}^i$

 - The supp material seems to be a little bit different to the paper? E.g., reference [2] is different. 


Chen, Tianyi, et al. "A single-timescale method for stochastic bilevel optimization." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

Hong, Mingyi, et al. "A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic." arXiv preprint arXiv:2007.05170 (2020).

limitations: Yes. The authors can also have a more detailed comparison with the works that prove convergence to a saddle point / global optimality.
review_title: null

Meta-review: metareview: This paper proposes and analyzes the convergence rate of a single-timescale actor-critic algorithm. The reviewers reached the consensus that it is above the borderline-acceptance bar. However, after an in-depth discussion during the reviewer-metareviewer discussion period, the reviewers pointed out some critical problems: although the superiority of the proposed algorithm over classic double-loop algorithms is validated, that over previous single-timescale single-loop is not discussed. One reviewer carefully checked both the original and the revised version of the paper but still claimed that extending the proof technique adopted in this paper would lead to a worse convergence rate compared with previous work. In general, I agree with the reviewer. Thus, I think the current version of the paper does not make a compelling case for its archive value due to the lack of a more rigorous discussion of related issues.

confidence: Certain
Decision: Reject